Graphics Reference
In-Depth Information
Grid
Ray
g
h
y
d
c
e
f
x
a
b
Figure 37.14: Ray traversal of a 2D grid (from [AW87]). To correctly traverse the grid,
a traversal algorithm must visit cells a, b, c, d, e, f, g, and h in that order. (Reprinted
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.)
(ordered)
conservative rasterization
of the line: Find all cells that touch any part
of the line. In 3D, the process is called
conservative voxelization.
Listings 37.17-37.19 give an algorithm for conservative voxelization first pro-
posed by Amanatides and Woo [AW87]. During initialization (Listing 37.17), this
algorithm finds the grid cell containing the ray origin. It then computes several
vector quantities describing the relative rate of motion of a point
Q
(
t
)=
P
+
dt
on
the ray with origin
P
and direction
d
. From these it can iteratively march through
the grid by stepping to the nearest grid line (Listing 37.19).
Listing 37.17: Interface for a 3D grid iterator.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
class
RayGridIterator {
public
:
/
*
Current grid cell
*
/
Index3 index;
/
*
Sign of the direction that the ray moves along each axis; +/-1 or 0
*
/
Index3 step;
/
*
Size of one cell in units of t along each axis.
*
/
Vector3
tDelta;
/
*
Distance along the ray of the first intersection with the
current cell (i.e., that given by index). Initially zero.
*
/
float
tEnter;
/
*
Distance along the ray to the intersection with the next grid
cell. tEnter and tExit can be used to bracket ray ray-primitive
intersection tests within a cell.
*
/
Vector3
tExit;
RayGridIterator(
const
Ray
& ray,
float
cellSize);
/
*
Increment the iterator, stepping exactly one cell along exactly one axis
*
/
RayGridIterator&
operator
++();
};
