Graphics Reference
In-Depth Information
A
C
I
D
E
F
B
G
HI J
H
A
BC
J
DEF G
(a)
(b)
Figure 7.14
A2D
k
-d tree. (a) The spatial decomposition. (b) The
k
-d tree layout.
region it is in),
nearest neighbor
(find the point in a set of points the query point is
closest to), and
range search
(locate all points within a given region) queries.
The following code illustrates how to visit all nodes of a
k
-d tree a given sphere
overlaps. One interesting problem is correctly rejecting subtree volumes the sphere is
outside of, even when the sphere straddles one or more of the supporting hyperplanes
of the halfspaces forming the volume. The solution adopted here is to maintain the
point inside the volume closest to the sphere center during traversal. Initially this
variable,
volNearPt
, is set to the sphere center. As the traversal recurses the far side
of the splitting plane (the side the sphere is not on), the point is clamped to the
splitting plane to determine the closest point on the volume boundary. The distance
between
volNearPt
and the query sphere center can now be used to cull subtrees.
struct KDNode {
KDNode *child[2];
// 0 = near,1=far
int splitType;
// Which axis split is along (0, 1, 2, ...)
float splitValue;
// Position of split along axis
...
};
// Visit k-d tree nodes overlapped by sphere. Call with volNearPt = s->c
void VisitOverlappedNodes(KDNode *pNode, Sphere *s, Point &volNearPt)
{
if (pNode == NULL) return;
// Visiting current node, perform work here
...
