Next: Parallel Collision Detection
Up: Introduction to Advanced Computer
Previous: Sweep and Prune
In this section, we will discuss briefly the approach taken by
hierarchical collision detection methods. These algorithms work on the
face-face level. Given a pair of objects, they check which faces of
the objects overlap, so they are carried out behind a method such as Sweep
and Prune in the collision detection pipeline.
Hierarchical Collision Detection algorithms approximate the objects in
the scene using bounding volumes. Without specifying which type of bounding
volume is used, the approach goes as follows. Given a set of polygons,
calculate the bounding volume of this set. Next we construct a number
of subsets that are maximally separated. For each of the subsets we
calculate the bounding volume and link it to the parent node. This
continues until the set contains some minimal number of polygons,
usually just one.
At collision detection time, intersection is
determined by first checking whether the bounding volumes at the roots
of the trees corresponding to the objects intersect. If they do, we
check the children of one of the nodes against the other node. If the two
nodes being tested are leaves, the faces contained in the leaves are
checked against each other and added to a collision list if they
intersect. Like this, we continue until no more intersections can be
found.
In this implementation, we used Oriented Bounding Boxes (OBB's) and
Axis aligned Bounding Boxes (AABB's) as bounding volumes, since they
are easy and fast to construct and for both types of objects rapid
overlap tests exist ([GLM96],[Ber98]).
With the OBB's we have a further option of
calculating the convex hull when computing the orientation.
Of course, many other types of bounding
volumes exist like spheres and k-DOP's etc. I won't go into this here,
but rather move on to the implementation of the parallel versions of
the OBB and AABB based algorithms.
Next: Parallel Collision Detection
Up: Introduction to Advanced Computer
Previous: Sweep and Prune
Marc Ramaekers
5/17/1999