Fast Hierarchical Methods to Detect Collisions between Deformable Objects: A Comparison

Abstract

The time complexity of a collision detection algorithm can be reduced to logarithmic in the number of tests performed when the objects are decomposed into a Bounding Volume (BV) tree hierarchy. It is well known that the Sphere Bounding Volume (SBV) and the Axis Aligned Bounding Box (AABB) hierarchies require inexpensive overlapping tests. However, we present a method called the Distance Hierarchy (DH) which is more suitable for deformable objects and is very simple to implement. It uses a hierarchical tree to decompose each object into regions. Each region requires just one parameter, its radius. In this work we compare three methods, AABB hierarchy, Sphere hierarchy, and DH, where the focus is on the intersection test, computation time, and the use of memory.