Suppose that a virtual world has been defined with millions of triangles. If two complicated, nonconvex bodies are to be checked for collision, then the computational cost may be high. For this complicated situation, collision detection often becomes a two-phase process:
In the broad phase, 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. Two opposing criteria that guide the selection of the type of bounding region:
The tree is constructed for a body, (or alternatively, ) recursively as follows. For each vertex, consider the set of all points in that are contained in the bounding region. Two child vertices are constructed by defining two smaller bounding regions whose union covers . 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 8.12 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.
Consider the problem of determining whether bodies and are in collision. Suppose that the trees and have been constructed for and , respectively. If the bounding regions of the root vertices of and do not intersect, then it is known that and are not in collision without performing any additional computation. If the bounding regions do intersect, then the bounding regions of the children of are compared to the bounding region of . If either of these intersect, then the bounding region of is replaced with the bounding regions of its children, and the process continues recursively. As long as the bounding regions intersect, lower levels of the trees are traversed, until eventually the leaves are reached. 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 of does not intersect the bounding region from a vertex, , of , then no children of have to be compared to children of . Usually, this dramatically reduces the number of comparisons, relative to a naive approach that tests all pairs of triangles for intersection.
Steven M LaValle 2016-12-31