THE SHORTEST COLLISION DETECTION SUMMARY EVER

I. INTRODUCTION

Collision detection between virtual objects is one of the bottlenecks in real-time applications.

Unfortunately, after more than 20 years of research, there is not a generic method that can be used in all applications.

The main reason of this is that the objects involved in the collision detection process become more and more complex. Hence, we have passed from using only rigid bodies to use more complex objects such as volumetric deformable bodies, cloths, fluids, etc.

Refer to [1][2][3] as a good starting point. Although most of the available techniques used to detect collision between rigid bodies need to be modified for deformable objects, most of these techniques share a basic approach. This approach divides the collision detection process into 3 steps:

1. Broadphase
2. Middle phase
3. Narrow phase

Next, I will briefly describe this steps. Note that we only consider static collision detection.


II. THE BROADPHASE.

In this stage, bodies are encapsulated in simpler volumes (spheres, boxes) for fast intersections.

This way, non intersecting pairs of complex objects are rapidly culled out from the collision process.

These simpler objects may be spheres, axis aligned bounding boxes (AABB), oriented bounding boxes (OBB) just to mention the most typical ones. They add little extra memory to the simulation but highly increase the performance of our collision detection process.

There is not a best choice between these bounding volumes, and some tests should be done to pick the best for a particular situation.

Decomposing the space into uniform grids and checking the interference between the cells and the simpler volume can additionally be added to this stage to speed up the collision process.


III. THE MIDDLE PHASE

The broadphase identifies the pair of bodies that should be tested for possible collision detection. Instead of directly test the primitives of the bodies (triangles, points) we may add an additional stage that can accelerate the collision detection process.

This additional stage is the middle phase. The main idea is to construct a bounding volume hierarchy of the object: the simpler volume used in the broadphase is subdivided into inner sub-volumes and each sub-volume into inner sub-volumes and so on, until we reach the primitives of the body.

Once the pair of objects are identified in the broadphase, the middle phase uses the bounding volume hierarchy to identify “regions” of the bodies for additional collision detection queries.

As an example, in a bottom-up construction approach of the bounding volume hierarchy, we select a small set of primitives of the object ( say 2 or 3 triangles for example) and we enclose them within a bounding volume. This is a leaf node. We do the same for all the primitives of the object. We end up by enclosing all the primitives of the object with small bounding volumes.

Next, we select a set of these small bounding volumes (2 or more and normally neighbors of each other) and enclosed them within a larger bounding volume. We repeat this for all the small volumes. As a result, we will have a smaller set of larger (middle) bounding volumes. We repeat the process until we have only one bounding volume, which represents our root node. Each level of the hierarchy represents a tighter fit than its parent. The number of level of the hierarchy is usually known as the depth of the tree.

Note that these hierarchies are constructed in an offline process.

The middle phase starts by testing the root bounding volume of bodyA (rootBVA) with the children bounding volumes of the root bounding volume of bodyB (rootBVB). If an interference exists between rootBVA and only one of the children of rootBVB we will know that the collision does not happen with the other children of rootBVB. In the next iteration we will not include them in the intersection tests. We will only test the colliding children with the children of the rootBVB and so on.

Alternatively, there exists a top-bottom approach in which we start by using the simpler bounding volume of the object and subdivide this volume into inner subvolumes in a recursively manner until we reach the primitives of the object.

For rigid bodies, there is not a clear advantage between OBB, AABB or bounding spheres trees. Their efficiency, memory consumption and accuracy depend on the application and on the enclosing body.

The main difference comes out when they are applied to deformable bodies (volumetric, 2D cloths) since these hierarchies need to be updated at each time step to adapt to the new deformed shape of the body.

Van der Bergen compared AABB's and OBB's hierarchies for deformable objects and determined that AABB's are the best option [4]. He also showed that, although hierarchies can also be rebuilt, updating them is almost ten times faster than rebuilding them. Larson et al. [5] compared different methods for the hierarchy updating process based on bottom-up and top-down strategies. They found that these methods depend on the depth of the tree and proposed a method that uses both strategies.

There has not been a comparison between sphere hierarchies and AABB's hierarchies since sphere trees were for long time rejected for its poor tightness to the body. However, latest results have shown that sphere trees can be as tight as AABB's trees and then can be an excellent option for deformable bodies. Their only problem is that their construction is not as simple as AABB's trees but the update can be much faster (note: last sentence is only an empirical personal assumption).

Advance issues concern the update of the trees when the encapsulating body suffers a topology modification, i.e. when the object is broken or cut. If it is a partial fracture or rupture, the tree most probably will need a rebuilt, which is computationally costly. If the object is broken in hundreds of sub-bodies, then the tree hierarchy might result to be obsolete.

Additionally, as an advance issue, auto-collisions might occur, (e.g. cloth self-collisions) and this is a subject in which volume hierarchies haven't present an effective solution.

To handle these two last issues, alternative approaches can be used. Instead of using bounding trees, we can used an optimized spatial hashing for collision detection of deformable objects [6].


IV THE NARROW PHASE

The result of the middle phase is either no collision (i.e. no leaves of body A are colliding with any leaves of body B) or "leaves collision" (i.e. at least one bounding volume leaf of body A is overlapping at least one bounding volume leaf of body B).

We focus here in polygonal models.

The leaves of the bounding volume tree (the smaller boxes and spheres in the hierarchy) are associated to a small set of primitives of the object. Hence, a little sphere will point to 2 or 3 triangles. Associating triangles to little bounding volumes is not a simple task since some aliasing problems may arise (e.g. a triangle may be associated to different bounding volumes under different circumstances).

Therefore, the narrow phase consists on finding the intersection of the primitives (e.g. triangles) enclosed by the bounding volume leaves of body A and B. Finally, we need to find the separation normal and the penetration distance as the minimum information for the collision response. Additional information can be included such as the intersecting triangles or edges. This additional information can be useful to build the Id of the contact.

Alternatively, instead of finding the primitives associated to the each leaf bounding volume, we can use the little leaf bounding volume as a "coarse primitive" of the body and compute the separation normal and penetration distance. We lose accuracy by doing this, however, if the approximation of the object by the deepest level of the hierarchy is good enough (i.e. the leaves were extraordinary calculated) then we can have an acceptable response and we can earn lots of time computations and memory consumption is highly reduced.

Finding contact information for triangles or other primitives is not an easy task. Methods such as the Lin-Canny Closest Feature algorithm may not be well suited since it does not provide penetration information and the well known and complicated to implement GJK seems to be the best option to best measure interpenetration.


BIBLIOGRAPHY

[1] Collision Detection for Deformable Bodies, Teschner. M et al., Proc. of the Star Reports, EG 04, pp 119-140

[2] 3D Collision Detection: A Survey, Jimenez P. et al, Computer And Graphics, 2001 pp 269-285

[3] Real-Time Collision Detection, C Ericson, Elsevier 2005

[4] Efficient Collision Detection Of Complex Deformable Models Using AABB trees, Van den Bergen, G. J Graph Tools, 2,4 (1997)

[5] Collision Detection for continuously deforming bodies, Larsson T. et al, EG Short Presentations 2001, pp. 325-333

[6] Optimized Spatial Hashing for Collision Detection of Deformable Objects, M. Teschner et al. Proc. VMV 2003