5.3.2 Hierarchical Methods

In this section, suppose that two complicated, nonconvex bodies, $E$ and $F$, are to be checked for collision. Each body could be part of either the robot or the obstacle region. They are subsets of ${\mathbb{R}}^2$ or ${\mathbb{R}}^3$, defined using any kind of geometric primitives, such as triangles in ${\mathbb{R}}^3$. Hierarchical methods generally decompose each body into a tree. Each vertex in the tree represents a bounding region that contains some subset of the body. The bounding region of the root vertex contains the whole body.

There are generally two opposing criteria that guide the selection of the type of bounding region:

1. The region should fit the intended body points as tightly as possible.
2. The intersection test for two regions should be as efficient as possible.

Several popular choices are shown in Figure 5.9 for an L-shaped body.

Figure 5.9: Four different kinds of bounding regions: (a) sphere, (b) axis-aligned bounding box (AABB), (c) oriented bounding box (OBB), and (d) convex hull. Each usually provides a tighter approximation than the previous one but is more expensive to test for overlapping pairs.

The tree is constructed for a body, $E$ (or alternatively, $F$) recursively as follows. For each vertex, consider the set $X$ of all points in $E$ that are contained in the bounding region. Two child vertices are constructed by defining two smaller bounding regions whose union covers $X$. The split is made so that the portion covered by each child is of similar size. If the geometric model consists of primitives such as triangles, then a split could be made to separate the triangles into two sets of roughly the same number of triangles. A bounding region is then computed for each of the children. Figure 5.10 shows an example of a split for the case of an L-shaped body. Children are generated recursively by making splits until very simple sets are obtained. For example, in the case of triangles in space, a split is made unless the vertex represents a single triangle. In this case, it is easy to test for the intersection of two triangles.

Figure 5.10: The large circle shows the bounding region for a vertex that covers an L-shaped body. After performing a split along the dashed line, two smaller circles are used to cover the two halves of the body. Each circle corresponds to a child vertex.

Consider the problem of determining whether bodies $E$ and $F$ are in collision. Suppose that the trees $T_e$ and $T_f$ have been constructed for $E$ and $F$, respectively. If the bounding regions of the root vertices of $T_e$ and $T_f$ do not intersect, then it is known that $T_e$ and $T_f$ are not in collision without performing any additional computation. If the bounding regions do intersect, then the bounding regions of the children of $T_e$ are compared to the bounding region of $T_f$. If either of these intersect, then the bounding region of $T_f$ is replaced with the bounding regions of its children, and the process continues recursively. As long as the bounding regions overlap, lower levels of the trees are traversed, until eventually the leaves are reached. If triangle primitives are used for the geometric models, then at the leaves the algorithm tests the individual triangles for collision, instead of bounding regions. Note that as the trees are traversed, if a bounding region from the vertex $v_1$ of $T_e$ does not intersect the bounding region from a vertex, $v_2$, of $T_f$, then no children of $v_1$ have to be compared to children of $v_1$. Usually, this dramatically reduces the number of comparisons, relative to a naive approach that tests all pairs of triangles for intersection.

It is possible to extend the hierarchical collision detection scheme to also compute distance. The closest pair of points found so far serves as an upper bound that prunes aways some future pairs from consideration. If a pair of bounding regions has a distance greater than the smallest distance computed so far, then their children do not have to be considered [638]. In this case, an additional requirement usually must be imposed. Every bounding region must be a proper subset of its parent bounding region [807]. If distance information is not needed, then this requirement can be dropped.