Graphics Reference
In-Depth Information
Listing 37.20 gives the actual intersection algorithm for the grid, considering
both primitives and cells. It iterates through all cells that are in bounds and along
the ray. For each cell encountered, it uses the underlying list's intersection method
to find the first (if any) intersection.
Listing 37.20: Ray intersection using a 3D grid and iterator.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
class
Grid3D {
...
/
*
Assumes that the ray begins within the grid
*
/
bool
firstRayIntersection(
const
Ray
& ray,
Value
*
& value,
float
& distance)
const
{
for
(RayGridIterator it(ray, cellSize); inBounds(it.index); ++it) {
// Search for an intersection within this grid cell
const
Cell& c = cell(it.index);
float
maxdistance = min(distance, t.tExit);
if
(c.firstRayIntersection(ray, value, maxdistance)) {
distance = maxdistance;
return true
;
}
}
// Left the grid without ever finding an intersection
return false
;
}
};
Because primitives may appear in more than one grid cell, it is essential to test
only for intersections that occur before the end of the cell at each iteration. An
example of a case that depends on this is shown in Figure 37.15. In that figure,
consider the intersection test that occurs when the iterator is at the cell labeled
b
.
Because the cells covered by object
Y
include cell
b
, during this iteration
Y
will
be tested against the ray. There is in fact an intersection—yet it occurs in cell
c
,
not cell
b
. Were the algorithm to return that intersection, it would miss the true
first intersection, which occurs with object
X
in cell
c
.
Intuition indicates that the algorithm will run in time proportional to the num-
ber of grid cells traversed, because that is the cost of the iterator. The constant
overhead of each iteration is very low—a handful of floating-point operations—
so the algorithm is practical for cases where we don't expect the ray to travel
too far before striking something. A grid with
g
subdivisions along
k
dimensions
X
Y
a
b
c
d
Figure 37.15: A case where it is essential only to test for intersections that lie within
each cell during the ray-marching process of ray-triangle intersection accelerated by a
spatial grid. (Redrawn from
Eurographics 1987: Conference Proceedings,
1987 [ISBN
0444702911], Marechal ed., John Amanatides and Andrew Woo, pp. 1-10, “A Fast Voxel
Traversal Algorithm for Ray Tracing,” Figure 1.)
