Graphics Reference
In-Depth Information
(a)
(b)
Figure 7.15
(a) A grid of trees, each grid cell containing a separate tree. (b) A grid indexing
into a single tree hierarchy, each grid cell pointing into the tree at which point traversal
should start.
it suffices to locate the grid cell the object is inside and follow the pointer to the
correct tree node. Using a grid in this manner can help bypass a large portion of the
tree during queries.
To handle the case of going to the correct node when an object is on a grid cell
boundary overlapping two or more cells, the grid cells can be made loose, similar to
the nodes in a loose octree. The grid cell that encompasses the object is now used
to find the entry point into the tree structure.
7.4
Ray and Directed Line Segment Traversals
Particularly common in many applications, games in particular, are
line pick
tests.
These are queries involving rays or directed line segments. Typical uses include line-
of-sight tests and tests for whether or not a fired bullet hits an enemy. They can also
be used as the primary collision query. One such example could be performing line
picks down from the wheels of a vehicle to attach the vehicle to the terrain below.
To accelerate these queries, hierarchical structures are used to minimize the number
of objects that have to be intersected by the ray or segment. The key idea is to first
spatially partition the world into a number of cells. The ray is then traced through
those cells it pierces and intersected against any objects they might contain. The next
two sections illustrate how ray queries are performed on
k
-d trees and uniform grids.
7.4.1
k
-d Tree Intersection Test
The basic idea behind intersecting a ray or directed line segment with a
k
-d tree is
straightforward. The segment
S
(
t
)
=
+
t
d
is intersected against the node's splitting
plane, and the
t
value of intersection is computed. If
t
is within the interval of the
A
