Complications

There are some complications created in using a traversal algorithm to walk through an irregular volume filled with many small triangles. The first and most significant is that the sides of the volume are not planar and the ray may intersect one twice. This means that the traversal may exit the grid without reaching the correct stop cell. More importantly, the intersection with the surface may lie in the second interval within the volume. The initialization code can be modified so that if the ray hits one of the bilinear sides twice, and no intersection is found in the first interval, then the traversal is called again with a new start cell determined by the second intersection point.

A second complication occurs due to the sides of the grid cells being non-planar. The first way this could cause problems was briefly mentioned while discussing the traversal. Geometrically, the ray can enter a cell briefly, and then quickly return to the first cell. This does not happen in our algorithm because of the way the traversal chooses the next cell; the ray passes on the same side of both point-normal pairs for that side, so the ray never enters the cell. In terms of Figure 7, although the ray could possibly intersect the bilinear patch along edge $\mbox{${\bf b}$}$$\mbox{${\bf c}$}$ twice, our algorithm ignores the double intersection and chooses the cell on the other side of edge $\mbox{${\bf a}$}$$\mbox{${\bf c}$}$. For certain extreme configurations, it is possible that the ray may actually intersect the microtriangle in the missed cell. Because the cells in general do not exactly bound the microtriangles, it is possible the ray should have hit the neighbor's triangle even if the ray misses the bilinear wall of the cell. Due to the small size of the microtriangles, and the significantly smaller size of the potentially missed piece, we have not noticed any significant errors caused by this problem. One solution would be to grow the triangle slightly in the triangle intersection test, a solution sometimes used to prevent cracking in simple triangle meshes. We chose not to do this because in our experience, expanding geometry eventually causes it's own set of problems.

A final issue to consider is that this method has the potential to create very small triangles. Some of the standard triangle intersection tests use epsilons that may be not be suitable for the size of the input. This can cause microtriangles to be falsely missed.

The intersection algorithm is implemented entirely using four byte floats. Although there are occasional rays that miss the surface, these problems are about the same frequency as those often found in ray tracers using simple polygonal objects.