Collision Detection (Advanced Methods in Computer Graphics) Part 6

k-d Trees

A k-dimensional tree, also known as a k-d tree, represents a subdivision hierarchy that is generated by splitting a volume along one axis at a time, and changing the axis in a cyclic fashion at each subdivision step. A three-dimensional volume is commonly split first along the x-axis using a plane parallel to the yz-plane, then along the y-axis using a splitting plane parallel to the xz-plane, and then along the z-axis. The process continues in the next step by again splitting along the x-axis. In our discussion we will assume that the splitting planes are chosen in the x-y-z order. A k-d tree is a special case of a binary space partitioning (BSP) tree where splitting planes can have arbitrary normal directions.

At the root level, every point that has the x-coordinate less than or equal to a chosen value x00 is put into the left child node, and points with x-coordinate greater than x00 goes to the right child. The points in the child nodes are split using y-coordinate values yo1 and y11. Choosing the splitting values xoo, you yn, etc., as the median values of the points within the node gives nearly equal number of points in both child nodes, and results in a well balanced tree. An example showing the binary space partitioning of a planar region using a 2-d tree is shown in Fig. 9.26. The splitting values are shown inside the nodes. The first subscript gives the node’s position within the same level, starting from 0 for the leftmost node. The second subscript indicates the level the node is in.


A three-dimensional k-d tree stores the minimum and maximum extents of the volume it represents at the root using the six coordinate values fxmn, xmx, ymn, y™, zmn, zmx}. The root node also stores the value x00 of the splitting plane used at that level. The AABB of the left child is given by fxmn, xoo, ymn, ymx, zmn, zmx} and that of the right child by {xoo, xmx, ymn, ymx, zmn, zmx}.

A binary partition of a two-dimensional region using a 2-d tree

Fig. 9.26 A binary partition of a two-dimensional region using a 2-d tree

Listing 9.5 Sequential traversal of a k-d tree for locating a point P


Listing 9.5 Sequential traversal of a k-d tree for locating a point P

Child nodes generally store only splitting plane values, but algorithms such as the ray intersection test discussed below require AABB parameters of leaf nodes. Both the construction and the traversal of a k-d tree are done in a top-down fashion, starting from the root node that either represents a three-dimensional scene or the axis-aligned bounding box of a group of objects. The traversal of a k-d tree to leaf node where a point P can be either inserted or located, follows the pattern of the well-known sequential binary tree search algorithm. The pseudo-code for the method is given in Listing 9.5.

Ray intersections with a volume represented by a k-d tree

Fig. 9.27 Ray intersections with a volume represented by a k-d tree

The broad-phase collision detection of objects is done by first identifying the leaf nodes of the k-d tree where an object’s bounding volume is stored. Every node of a k-d tree represents an axis-aligned box, and therefore the methods given in the previous section can be directly used locate the positions of an AABB or a bounding sphere (see Eq. 9.58) within a k-d tree.

A k-d tree is also used for ray tracing acceleration, as it can effectively restrict the computation of ray intersection tests along the direction of the ray. The root of the k-d tree represents the AABB of the scene of objects to be ray traced. The primary ray typically originates from a view point outside the scene. A secondary ray, on the other hand may originate from a point inside the scene. In Fig. 9.27, ray-1 originates at P0, enters the AABB of the root node of the k-d tree at P1 and exits the scene at P4. Ray-2 originates at a point Q1 within the scene and exits the volume at Q3. In the case of ray-1, we can compute the position of P1 as well as the entry and exit distances P0P1, P0P4 using the parametric equation of the ray and the equations of the bounding planes of the AABB (see Sect. 9.2.1). Using the method in Listing 9.5, we can identify the leaf node of the k-d tree where P1 (or Q1 for ray-2) is located. The ray is tested for intersection with the objects stored at this leaf node. If an intersection occurs, the point of intersection closest to the origin of the ray is returned. Otherwise, the ray is compared with the AABB of the leaf node and the next intersection point P2 with the current node is computed. This point is extended further by a small amount e along the direction of the ray to get a point P2′ that lies well within another node of the k-d tree:

tmpf9b3-203_thumb[2][2][2][2][2]

where d is the unit vector along the ray direction. The k-d tree is traversed again from the root to identify the leaf node to which P20 belongs. The objects in this node are then compared with the ray to determine if there is an intersection, and if there is no intersection, the process is continued by extending the ray to the next cell, and so on until the ray exits the AABB of the root node. The algorithm visits all leaf nodes intersected by the ray in a near to far order. Objects and primitives in the remaining leaf nodes are not compared with the ray. The pseudo-code for this method of sequential ray intersection test is given in Listing 9.6.

Listing 9.6 Sequential ray intersection test using a k-d tree

Listing 9.6 Sequential ray intersection test using a k-d tree

A k-d tree based spatial partitioning is useful in finding the point closest to a given point P within a three-dimensional volume. The location of the closest point gives information about the object which could most likely collide with the object or the bounding volume containing P.

As shown in the two-dimensional example in Fig. 9.28, the algorithm for finding the nearest neighbour of P begins with the traversal of the k-d tree to the leaf node containing P and finding the closest point to P within that leaf node. The squared value of the distance between the two points is stored as the current minimum value of r2. The position of P and the value of r2 together are used to compare the sphere centred at P with the AABBs of other leaf nodes of the k-d tree using Eq. 9.58 for possible overlap. If a leaf node overlaps the sphere, the squared distances of points in that node from P are computed and if a value lower than the current minimum is found, then the value of r2 is updated with the lowest found in that node. The process continues as shown in Fig. 9.28, until all nodes that overlap the sphere have been examined. The point that generated the minimum value for r2 is selected as the nearest neighbour of P. The sphere-AABB overlap test excludes a large number of points that are separated from P by a distance greater than r from being compared.

We saw earlier that both an octree and a k-d tree may store the same object in several leaf nodes if the object overlaps the volume of those nodes. For an octree, the splitting planes are fixed, but in a k-d tree, we can select the position of the splitting plane. Several heuristics, such as the surface area heuristics have been proposed in the literature to minimize the amount of object overlap at leaf nodes. The next section introduces a subdivision structure that combines the desirable attributes of a k-d tree and a bounding volume hierarchy.

A sequence of computations performed on a k-d tree to find the nearest neighbour of a point P

Fig. 9.28 A sequence of computations performed on a k-d tree to find the nearest neighbour of a point P

Boundary Interval Hierarchy

A bounding interval hierarchy is a structure similar to a k-d tree, but uses two parallel partitioning planes for each node. For a given node, the plane perpendicular to and passing through the midpoint of the longest axis of the node’s AABB is first chosen as the splitting plane. Assume that this axis is in the x-direction, and the position of the splitting plane is xo. The AABBs of the objects within the node’s volume are then sorted along this axis. The objects whose AABBs have all x-coordinates less than or equal to x0 are assigned to the left child. AABBs that are entirely on the right of the splitting plane are assigned to the right child. Objects whose AABBs intersect the splitting plane are classified as belonging to the left or right child depending on which side of the splitting plane the AABBs have maximum overlap. The left partitioning plane is then defined using the maximum value of the x-coordinates of the AABBs belonging to the left child, and the right plane is defined using the minimum value of the x-coordinates of the AABBs belonging to the right (Fig. 9.29). The process continues by splitting each child node along the longest axis and defining two partitioning planes along that axis. A node containing only a single object is not subdivided further.

Partitioning of objects into “left" and “right” using two parallel partitioning planes

Fig. 9.29 Partitioning of objects into “left" and “right” using two parallel partitioning planes

The primary differences between a k-d tree and a bounding interval hierarchy are listed below.

•    A k-d tree selects axes cyclically and defines a perpendicular splitting plane at the median point along the current axis direction, or alternatively uses a heuristic to position the splitting plane. A bounding interval hierarchy uses the longest axis of the current AABB, and the splitting plane is always positioned at the midpoint.

•    In a k-d tree, the AABBs of the objects in a node are not sorted. A bounding interval hierarchy sorts AABBs along each axis. This speeds up the process of repeated classification of objects as left or right of splitting planes along the same axis.

•    A k-d tree stores only the splitting plane position and optionally the parameters of the node AABB. A bounding interval hierarchy requires the positions of two partitioning planes and the axis information to be stored.

By using two partitioning planes, a bounding interval hierarchy is able to classify each object in a node volume uniquely as either “left" or “right", without the need for placing an object that overlaps the splitting plane in both child nodes. A clear separation of objects is thus achieved, and the AABBs of the child nodes are closely aligned with the object AABBs within the nodes. The interval hierarchy thus provides a hierarchy of axis aligned bounding volumes and also a spatial ordering similar to that of the k-d tree. Bounding interval hierarchies have been found particularly useful for real-time ray tracing.

Summary

This topic has covered the main aspects of collision detection algorithms including the representation of objects using bounding volumes, intersection tests between primitives and bounding volumes (BV) and hierarchical structures that are useful for minimizing the amount of pair-wise object/primitive comparisons required in overlap tests.

The important methods discussed in the context of bounding volume construction are the Welzl’s algorithm for computing the minimum bounding sphere, the computation of oriented bounding boxes, and the incremental construction of three-dimensional convex hulls. Algorithms for primitive-BV intersection tests and BV-BV intersection tests have been presented in detail. The separating axis theorem and the slab-based method are extremely useful for intersection tests involving oriented bounding boxes.

The topic also presented methods for the construction and traversal of bounding volume hierarchies. Spatial partitioning structures such as the octree and the k-d tree are useful for broad-phase collision detection as well as ray tracing algorithms. Both structures use axis aligned splitting planes to facilitate efficient computation of ray intersection tests. The bounding interval hierarchy is a structure that combines the features of a bounding volume hierarchy and a k-d tree.

Next post:

Previous post: