Initialization

The initialization phase of the algorithm must determine where in the grid the traversal algorithm starts and ends. The volume through which the traversal takes place is shown in Figure 5. The top and bottom of the space are bounded by triangles, the sides are bounded by bilinear patches.

Before the start and end cells are determined, the subdivision amount $N$ must be found. This can either be fixed for the displacement map, $N = C$, or made adaptive, based on projected screen area. We allow either, and compute the adaptive size based on the area and an estimate of the distance to the camera, with a user defined $N_{\rm max}$.

The initialization phase must determine the correct index $(i,j,k)$ for starting the traversal. In standard grid traversal algorithms the traversal may start anywhere inside the grid. This clearly makes sense and would be ideal, but determining the index given an arbitrary point is equivalent to determining the barycentric coordinates and displacement (height) for the point. The computation involves solving a cubic equation, and the method seemed to have numeric problems. Our solution is to treat the ray as an infinite line and find the place where that line enters the volume and where it exits. This can require a longer traversal than necessary, however unlike uniform space subdivision in ray tracing, where the grid bounds the environment or a complex object, the displaced triangle tends to occupy a relatively small fraction of the scene, so most rays will pass completely through the volumes of most triangles.

The start and end points are the smallest and largest intersections of the ray with the volume. If the intersection point is on one of the bilinear side patches, one of the barycentric coordinates is zero, and the $u$ parametric value found while intersecting the side can be used directly to determine the other two. If the intersection point is on one of the triangular end caps, the barycentric coordinates of the intersection point are exactly what is needed. The index for the grid cell is then $(\lfloor\alpha * N\rfloor, \lfloor\beta * N\rfloor,\lfloor\gamma * N\rfloor)$.

The last part of the initialization is to determine which face of the cell the ray entered from, so that the traversal algorithm can determine the appropriate next cell. This is given if the intersection is on one of the bilinear sides, however it is not given for the top or bottom boundaries. In this case, the bilinear walls of the cell can be checked. As the ray entered either the top or the bottom, the side hit will be the side the ray leaves from. It is valid to assume the ray entered from either of the other two sides. If the ray does not hit any sides, then this cell is the end cell as well, so the parameter does not matter.