Optimized spatial hashing for collision detection of deformable objects

We propose a new approach to collision and self-collision detection of dynamically deforming objects that consist of tetrahedrons. Tetrahedral meshes are commonly used to represent volumetric deformable models and the presented algorithm is integrated in a physically-based environment, which can be used in game engines and surgical simulators. The proposed algorithm employs a hash function for compressing a potentially infinite regular spatial grid. Although the hash function does not always provide a unique mapping of grid cells, it can be generated very efficiently and does not require complex data structures, such as octrees or BSPs. We have investigated and optimized the parameters of the collision detection algorithm, such as hash function, hash table size and spatial cell size. The algorithm can detect collisions and self-collisions in environments of up to 20k tetrahedrons in real-time. Although the algorithm works with tetrahedral meshes, it can be easily adapted to other object primitives, such as triangles.