Graphics Reference
In-Depth Information
Since the number of operations involved in finding a grid cell is relatively
small, each operation takes a large percentage of the cell dereference time and it
is worth micro-optimizing them from the straightforward version shown here. If
cellSize
is
1.0
, the divisions in
cellIndex
can be completely eliminated. Where
that is not possible, multiplying
P
by a precomputed
1/cellSize
value is faster
on many architectures than performing the division operations. The floor opera-
tion is a relatively expensive floating-point operation that can be replaced with an
intrinsic-supported truncate-and-cast-to-integer operation. When
numCells.x
and
numCells.y
are powers of two, the multiplications in the
cell
method become
faster bit-shift operations. Finally, at the loss of some abstraction, it is sometimes
worth exposing the 1D indexing scheme outside of the data structure. Callers can
then iterate directly through the 1D array in steps chosen to walk along any given
dimension.
By convention, elements in the 1D array varying along the lowest-indexed
dimension (e.g.,
x
) are the ones placed at adjacent memory addresses. When the
iteration order is expected to favor some other axis, arranging to unroll along that
axis first can yield increased cache coherence. For example, if an application is
expected to trace many rays vertically, then making the vertical axis coherent is a
good choice.
Sometimes the dominant ray iteration direction cannot be predicted, or iter-
ation will be across multiple dimensions for volume queries such as ball inter-
section. If memory coherence is a concern for such applications, unrolling the
multidimensional array along a space-filling curve can be a good solution. Curves
such as the Hilbert [Hil91, Voo91] or Morton [Mor66] (a.k.a. “Z,” for its shape)
curves define an indexing scheme that, on average, assign spatially local elements
to spatially local memory addresses. These can typically be implemented with a
few bitwise operations per index computation.
Tuning the extent of each cell, or equivalently, the number of cells for a given
grid extent, requires a good understanding of the kinds of queries that will be
performed and the spatial distribution of the data. This issue is best discussed
after the query algorithms, so we set it aside until Section 37.7.3.
The
inBounds
method is convenient for identifying legal indices, which is
necessary because the grid has finite extent. For some applications data sets have
inherent spatial bounds. For example, in a virtual environment like a video game
level with a well-defined boundary, objects will never move beyond the boundary.
In this case the finite nature of the grid presents no limitation. In other cases, a
scene is known to be very dense in a specific region but contains a few elements
that lie far from that region, possibly without any practical spatial bound. In this
situation one can extend the grid with a single additional list of elements that
lie outside the grid proper. This allows the data structure to represent unbounded
extent yet still provide efficient queries within the dense region. If a data set is
neither spatially bounded nor primarily clustered in a dense region, the simple grid
is likely a poor choice of data structure. However, the sparse
hash grid
described
later in this section may still be appropriate.
To find the first intersection of a ray with the primitives in a grid, the query
algorithm must walk through the cells of the grid in the order in which the ray
enters them, as shown in Figure 37.14. In 2D, this is equivalent to the problem of
