Graphics Reference
In-Depth Information
Figure 37.16: (Left) Large g gives small grid cells. A ray iterator must touch many cells
(shown with solid black borders), but most of those will be empty. This is good if the cost
of testing for a geometric intersection is large compared to the cost of iterating through
(or storing) cells. (Right) Small g gives large grid cells. A ray iterates through few grid
cells, but those contain many elements: The conservative ray-cell test produces many false
positives. This is good if the cost of testing for a geometric intersection is small compared
to that of iterating through cells.
from Figure 37.16 (left). For the coarse grid, there are relatively few ray-grid
intersections, but many more ray-element intersection tests must be performed
within each grid cell.
We describe scenes that contain a mixture of dense and sparse areas as hav-
ing a
nonuniform spatial distribution
of elements. A grid is likely a poor data
structure for ray intersection in a scene of nonuniform density because no single
g
constant can serve both areas well. A tree is a better choice in that case because
it can adapt to varying spatial density.
There are three layers of subtlety that can subvert this conclusion. At first,
it seems that a grid will rarely be a useful data structure. That is because many
graphics scenes represent only surface geometry. This makes their spatial distri-
bution of geometry inherently nonuniform, in the sense that the primitives cluster
at the surfaces of objects and not on their interior.
The second point is that this characterization itself depends on scale, so it is
not a safe generalization. The Manhattan area of New York City comprises tall
buildings on a mostly regular grid. Figure 37.17 shows an idealized top view of
such a layout. If we examined a computer graphics model of the building exte-
riors over a volume about the size of a single room (e.g., choosing
g
so that
Dense Geometry
Comparable density
No geometry
Little geometry
Figure 37.17: Hypothetical top view of a city on an island. (Left) Small grid cells give
inhomogeneous geometric density. (Right) Sufficiently large cells produce approximately
uniform density for this scene.
