Traversal

Assuming we will be able to initialize the traversal algorithm, we focus first on how to do an efficient traversal. This traversal is conceptually simple, however the use of triangles complicates the indexing. For each cell entered, the microtriangle is generated. If it is hit, the traversal is over, if it is missed, the next cell must be determined and a new microtriangle generated. The new triangle will differ from the previous triangle by exactly one vertex. This means that for each step through the grid we need only evaluate the expensive displacement function once.

Figure 6: Barycentric indexing for $N=2$ and $N=3$. When moving between adjacent triangles, exactly one index changes by one. For a given triangle, this change has the same sign for all three edges. The ``upper'' triangle for a given $(j,k)$ is the one with the smaller $i$ index.

A position in the grid will be labeled by a triple, $(i,j,k)$, corresponding to the lines of constant barycentric coordinates $\alpha=i/N, \beta=j/N, \gamma=k/N$. The indices sum to either $N-1$ or $N-2$ depending upon whether the triangle is a lower triangle or an upper triangle as shown in Figure 6. The classification into lower and upper determines how the vertices are generated given the indices. For a lower triangle, the barycentric lines corresponding to indices are the edges of the triangle. For an upper triangle, the barycentric lines corresponding to the indices touch the triangle only at the vertices. This is not as neat as other possible numbering schemes, however it means that each triangle differs from its neighbors by one in exactly one index.

Figure: The ray $\mbox{${\bf o}$}$$+ t$$\mbox{${\bf v}$}$ passes between the normals at ${\bf a}$ and ${\bf b}$. It will leave either between the normals at ${\bf a}$ and ${\bf c}$, or between the normals at ${\bf b}$ and ${\bf c}$. This can be tested by whether the ray passes left or right of ${\bf n}$. It goes to the left of the line $\mbox{${\bf c}$}$$+ t$$\mbox{${\bf n}$}$ if $\mbox{${\bf v}$}$$\cdot ($$\mbox{${\bf n}$}$$\times($$\mbox{${\bf o - c}$}$$))$ is negative.

Each microtriangle is represented by three displaced points, ${\bf a}$, ${\bf b}$, and ${\bf c}$, with the order chosen such that the ray is assumed to have entered the cell passing through the side corresponding to edge $\mbox{${\bf a}$}$$,$$\mbox{${\bf b}$}$. The next cell to be tested can be marked based on which index will change and if the index will be incremented or decremented. This flag can be represented as $\{$iplus, jminus, kplus, iminus, jplus, kminus$\}$, and depends upon the orientation of the current triangle and which side of the cell the ray exits through. By knowing how the ray entered the current cell, there are usually only two options for how the ray leaves the cell. The exception for when the ray exits through the face it enters is handled by the initialization code and will be discussed later. These options can be checked by seeing on which side of the line determined by $\mbox{${\bf c}$}$$+ s$$\mbox{${\bf n}$}$$_c$ (the far point and its normal) the ray passes, as shown in Figure 7. If the above list of choices is viewed as a ring, the next possible choice is either the next flag in the ring, or the previous flag in the ring.

The traversal can be terminated by checking if the $(i,j,k)$ values are the same as the stop cell $(i_e,j_e,k_e)$ determined by the initialization phase. We also terminate the traversal if the ray exits the volume. The traversal loop can be expressed in pseudocode as follows: