Graphics Reference
In-Depth Information
The described algorithm can of course be implemented for the traversal of a 3D
grid. In this case the structure of the main loop becomes:
for (;;) {
VisitCell(i, j, k);
if (tx <= ty && tx <= tz) {
// tx smallest, step in x
if (i == iend) break;
tx += deltatx;
i+=di;
} else if (ty <= tx && ty <= tz) {
// ty smallest, step in y
if (j == jend) break;
ty += deltaty;
j+=dj;
} else {
// tz smallest, step in z
if (k == kend) break;
tz += deltatz;
k+=dk;
}
}
It should be noted that as
tx
and
ty
are float variables it is possible that rounding
errors may cause the cells visited during traversal to be different from those visited by
an algorithm using exact arithmetic. If this is a concern, objects should be considered
as extended by some small epsilon before being assigned to the grid. It is also possi-
ble to turn this algorithm into an all-integer algorithm by using integer-only inputs
and multiplying through
tx
,
ty
,
ty
by the denominators involved in the
initialization code. An all-integer 4-connected line-drawing algorithm is described
in [Barerra03].
If the objects stored in the grid can be concave, it is important to make sure that the
intersection point of a detected intersection lies within the current cell. Otherwise,
when a concave object straddles multiple cells the object could have been hit several
cells away, and there might be a hit with a different object in any of the cells between.
Section 7.7 presents methods for avoiding having to perform multiple intersection
tests against the same objects in such situations as just described.
There are several possible optimizations that can be performed on ray queries on
uniform grids. For example, note that a ray at an angle passes through more cells
than an axis-aligned ray. Therefore, one possible optimization is to have several grids
oriented differently and pick the most aligned one to trace a ray through. Another
optimization is to apply a move-to-front reordering heuristic to objects in a cell. As
intersected objects are likely to be intersected again on the next query, having an early
upper bound on the distance to the nearest intersected object allows more distant
objects within the same cell to be quickly culled using a quick distance test. Additional
optimizations can be found in the ray-tracing literature [Glassner89], [Shirley00].
tx
, and
