ray_tracing.tex

\chapter{RAY TRACING ALGORITHM}
\label{chap:ray_tracing}


In order to evaluate a path integral through the discrete grid, it
is first necessary to construct a one-dimensional piecewise constant integrand
which is discontinuous at unevenly spaced points corresponding to the
intersections between the path and edges in the spatial grid.

Consider a grid center $\vec{p_1} = (p_{1x},p_{1y},p_{1z})$ and a corresponding path $\vec{l}(\vec{x_1}, \vec{\omega}, s)$.
To find the location of discontinuities in the integrand, we first calculate the
distance from its origin, $\vec{p_0} = \vec{x_0}(\vec{p_1}, \vec{\omega}) = (p_{0x}, p_{0y}, p_{0z})$ (as in \eqref{eqn:x_0}) to grid edges in each dimension
separately.
Given
\begin{align}
  x_i &= p_{0x} + \frac{s_i^x}{\tilde{s}}(p_{1x}-p_{0x}), \\
  y_j &= p_{0y} + \frac{s_j^y}{\tilde{s}}(p_{1y}-p_{0y}), \\
  z_k &= p_{0z} + \frac{s_k^z}{\tilde{s}}(p_{1z}-p_{0z}),
\end{align}
the path lengths at which the ray intersects with edges in each dimension are calculated to be
\begin{align}
  s_i^x &= \tilde{s}\frac{x_i-p_{0x}}{p_{1x}-p_{0x}}, \\
  s_i^y &= \tilde{s}\frac{y_i-p_{0y}}{p_{1y}-p_{0y}}, \\
  s_i^z &= \tilde{s}\frac{z_i-p_{0z}}{p_{1z}-p_{0z}}.
\end{align}
We also keep a variable for each dimension specifying whether the ray increases
or decreases in the dimension. Let
\begin{align}
  \delta_x &= \sign(p_{0x}-p_{1x}), \\
  \delta_y &= \sign(p_{0y}-p_{1y}), \\
  \delta_z &= \sign(p_{0z}-p_{1z}).
\end{align}
For convenience, we also store a closely related quantity, $\sigma$ with a value 1 for
increasing rays and 0 for decreasing rays in each dimension
\begin{align}
  \sigma_x = (\delta_x+1)/2, \\
  \sigma_y = (\delta_y+1)/2, \\
  \sigma_z = (\delta_z+1)/2,
\end{align}
simply as a boolean value to track of the ray direction.

For this algorithm, we keep two sets of indices. $(i,j,k)$ indexes the grid
cell, and is used for extracting physical quantities from each cell along
the path.
Meanwhile, $(i^e,j^e,k^e)$ indexes the edges between grid cells, beginning
after the first cell. That is, $i^e=1$ refers not to the plane $x=\xmin$, but to $x=\xmin+dx$.

Let $(i_0, j_0, k_0)$ be the indices of the grid cell containing $\vec{p_0}$.
That is,
\begin{align}
  i_0 &= \ceil\left(\frac{p_{0x}-\xmin}{dx}\right), \\
  j_0 &= \ceil\left(\frac{p_{0y}-\ymin}{dy}\right), \\
  k_0 &= \ceil\left(\frac{p_{0z}-\zmin}{dz}\right).
\end{align}
Then,
\begin{align}
  i_0^e &= i_0 + \sigma_x, \\
  j_0^e &= j_0 + \sigma_y, \\
  k_0^e &= k_0 + \sigma_z.
\end{align}
Now, we calculate the distance from $p_0$ along the path to edges in each dimension.
\begin{align}
  s_i^x = \hat{s}\frac{x_i^e-p_{0x}}{p_{1x}-p_{0x}}, \\
  s_j^y = \hat{s}\frac{y_j^e-p_{0y}}{p_{1y}-p_{0y}}, \\
  s_k^z = \hat{s}\frac{z_k^e-p_{0z}}{p_{1z}-p_{0z}}.
\end{align}

For each grid cell, we check the path lengths
required to cross the next $x$, $y$, and $z$ edge-planes.
Then, we move to the next grid cell in whichever dimension
is crossed soonest.
As each cell is traversed, the absorption coefficient and effective source are saved for use in the ray integral for the numerical calculation of the asymptotic approximation.
For full implementation details, see the \texttt{traverse\_ray} subroutine in \texttt{asymptotics.f90} in Appendix \ref{chap:fortran}.

% Putting it together, we do the following.
% \begin{enumerate}
%   \item Let $i,j,k$ be fixed (denoting the starting grid cell).
%   \item Set $s=0$.
%   \item
% \begin{align}
%   d = \mbox{argmin}_{x,y,z} \left\{ s_i^x-s, s_j^y-s, s_k^z \right\}
% \end{align}
%
% \begin{align}
%   \begin{cases}
%     i = i+\delta_x, & \mbox{if } d=x \\
%     j = j+\delta_y, & \mbox{if } d=y \\
%     z = k+\delta_z, & \mbox{if } d=z
%   \end{cases}
% \end{align}
%
% and
%
% \begin{align}
%   \begin{cases}
%     i^e = i^e+\delta_x, & \mbox{if } d=x \\
%     j^e = j^e+\delta_y, & \mbox{if } d=y \\
%     z^e = k^e+\delta_z, & \mbox{if } d=z
%   \end{cases}
% \end{align}
%
%
% Then, move to the adjacent grid cell in the dimension which requires the shortest
% step to reach an edge. Save $ds$ of the path through this cell. Also save abs.
% coef. and source.
% % TODO: Improve
%
% As the ray traverses the spatial grids, it crosses $N-2$ spatial grid edges.
% Let the nondecreasing path lengths at which these crossings occur be denoted by
% $\left\{s_\nu\right\}_{\nu=1}^{N}$, with the convention $s_1=0$ and $s_{N}=\tilde{s}$.
% This implies that edge $\nu$ preceeds cell $\nu$.
% $\{s_\nu\}$ is not strictly increasing if the ray directly intersects a grid corner,
% which means that multiple edges are traversed at the same path length.
% Hence, the path lengths through the grid cells, indexed by $\nu=1,\ldots,N-1$, are
%
% * TODO *