Graphics Reference
In-Depth Information
// Figure out which child to recurse into first (0 = near, 1 = far)
int first = s->c[pNode->splitType] > pNode->splitValue;
// Always recurse into the subtree the sphere center is in
VisitOverlappedNodes(pNode-
>
child[first], s, volNearPt);
// Update (by clamping) nearest point on volume when traversing far side.
// Keep old value on the local stack so it can be restored later
float oldValue = volNearPt[pNode-
>
splitType];
volNearPt[pNode-
>
splitType] = pNode-
>
splitValue;
// If sphere overlaps the volume of the far node, recurse that subtree too
if (SqDistPointPoint(volNearPt, s-
>
c)<s-
>
r*s-
>
r)
VisitOverlappedNodes(pNode-
>
child[first
∧
1], s, volNearPt);
// Restore component of nearest pt on volume when returning
volNearPt[pNode-
>
splitType] = oldValue;
}
This code framework is easily extended to, for instance, locate the nearest neighbor
object to the query sphere by starting with a sphere of unbounded size, shrinking the
sphere as objects are encountered within the sphere. Note that the shape of the
regions in a
k
-d tree will affect the number of nodes being visited. For example, if
many narrow regions are next to each other, a wide query is likely to overlap all
regions. To limit the number of nodes being visited, it is best to avoid regions narrow
in one or more dimensions. Such nonnarrow regions are commonly referred to as
fat
regions.
The efficiency of
k
-d trees (in the context of ray tracing) is discussed in
[MacDonald90]. An in-depth treatment of octrees, quadtrees,
k
-d trees, and similar
spatial data structures is found in [Samet90a] and [Samet90b].
7.3.8
Hybrid Schemes
The previously described methods can also form the basis of various hybrid strategies.
For instance, after having initially assigned objects or geometry primitives to a uniform
grid, the data in each nonempty grid cell could be further organized in a tree structure.
The grid now serves as a fast way of locating the appropriate trees (in a forest of trees)
to perform further tests against (Figure 7.15a).
Grids can also be used as “acceleration structures” into a single tree hierarchy.
Consider a uniform grid of tree node pointers in which each pointer has been directed
to the tree node whose volume bounds the corresponding grid cell as tightly as
possible (Figure 7.15b). Instead of traversing from the root to the node an object is in,
