Graphics Reference
In-Depth Information
contains
O(
g
k
)
cells. The longest ray traversal is the
O(
g
)
-length diagonal of the
grid. For a grid containing
n
primitives, in the worst case all of those primitives
cover every grid cell along the diagonal but the ray intersects none of them. The
intersection query cost is thus
O(
g
n
)
.
Of course, for such a scene the grid is a poor choice of data structure, since
even a spatial list beats its performance. So the worst-case bound is very different
from the expected behavior. The grid is better suited to a scene containing roughly
uniformly distributed primitives that tend to fit within a grid cell. Likewise, it
is better suited to cases of the anticipated ray queries that will progress a small
fraction of the scene before striking a primitive.
Trees will exhibit better asymptotic performance under queries than will grids
for large scenes with uneven spatial distributions—we expect to see some kind
of logarithmic versus linear behavior comparing these data structures in the long
run. However, the iteration through
empty
cells in a grid is fairly fast. Thus, the
constant applied to the linear (in the length of the array) time cost term is small
and one can afford to traverse many cells for each ray. For scenes of bounded size,
the grid may outperform the tree on ray-intersection queries, especially if the time
to build the data structure is factored into the net runtime.
·
If we expect to perform many box or ball intersections, then we should size
the grid based on the expected intersection object size so that the intersection
algorithm will typically have to examine only a small number of cells (maybe
one to four).
Ray intersection on a grid takes time linear in the length of the ray because
the number of grid cells to examine is asymptotically proportional to the length of
the ray. It also takes time linear in the number of primitives in the grid cells that
are encountered. This creates a tension between minimizing the number of grid-
intersection tests and the number of element-intersection tests. We assume that
grid-intersection tests are less expensive than element intersections. The cost ratio
for each kind of test is probably constant, but it may vary over a large range—
say, 3:1 for ray-sphere : ray-grid time and 200:1 for ray-implicit-surface : ray-grid
time. We might have millions of each kind of potential intersection with signifi-
cantly varying probability of occurrence. Moreover, changing that ratio affects the
space cost of the data structure, which impacts both viability and memory per-
formance. So it is not obvious which kind of intersection test the data structure
should favor for performance. The answer is that it depends on the structure of the
scene as well as the cost of the intersection tests.
We do know that if we make
g
large, the grid squares are small, as depicted
in Figure 37.16 (left). This reduces the number of elements to be tested in each
nonempty cell, but it increases the number of cells that we need to examine. That
is good for dense scenes. The figure depicts this by highlighting the primitives
that are tested against the ray. That is a small fraction of the elements in the grid
in the figure, but it is a large number of grid borders compared to the number of
elements in the grid.
If we make
g
small, the grid squares are large. This allows the ray to quickly
step through large volumes of empty space, but it increases the number of ele-
ments that must be tested in each nonempty cell encountered. That is good for
sparse scenes. Figure 37.16 (right) shows a coarse grid over the same scene
