Graphics Reference
In-Depth Information
(a)
(b)
Figure 7.16
Cell connectivity for a 2D line. (a) An 8-connected line. (b) A 4-connected line.
In 3D, the corresponding lines would be 26-connected and 6-connected, respectively.
may border more than just one leaf node, a quadtree or
k
-d tree stored at the
face is used to divide the face area and link each area with the correct neighboring
leaf node.
7.4.2
Uniform Grid Intersection Test
Shooting a ray through a uniform grid is very similar to the rasterization steps per-
formed by, say, the Bresenham line-drawing algorithm [Rogers98]. However, there
is an important difference. In rasterization, the line may intersect cells that are not
filled in (Figure 7.16a). For collision detection, this would be fatal; all pierced cells
must be visited or some objects may not be tested. The traversal method used must
enforce
6-connectivity
of the cells visited along the line. Cells in 3D are said to be
6-connected if they share faces only with other cells (in 2D, the same cells would
be called 4-connected). If cells are also allowed to share edges, they are considered
18-connected. A cell is 26-connected if it can share a face, edge, or vertex with another
cell (called 8-connected in 2D).
Bresenham-like methods are categorized by stepping along the major axis, taking
a step along the minor axis (axes) when an error term has built up. It is possible to
extend these methods to step through the missed cells when the step along the minor
axis is performed. For a thorough derivation of how to do so see [Joy86].
In this section a slightly different method is presented, due to [Amanatides87] and
[Cleary88]. This method is symmetric and does not use the concept of a major stepping
axis. Cells are assumed to be square. In the following, the term
segment
means a
directed line segment and the term
ray
will sometimes be used synonymously. To
simplify the presentation, the grid is assumed to be 2D.
The key idea is that as a ray leaves a cell it pierces a cell boundary. Whether to
step along the
x
axis or the
y
axis depends on whether a vertical or a horizontal
boundary is pierced. This decision is made easy by maintaining two variables,
tx
and
ty
, containing the distance from the ray origin
along the ray
to the next vertical and
