Non-contact Breathing Analysis 3D Scanning and Printing Deformation Object Control Deformable Object Collision Visual Bioinformatics
Animation Computer Graphics Advanced Computer Graphics Game Design Shader and GPU Programming

A Fast Culling Scheme for Deformable Object Collision Detection Using Spatial Hashing

Abstract: Fast culling for collision detection is one of the key components in dynamic simulation. While culling for collision detection works well when there is a smaller number of collisions compared to potential collision pairs in a given scene, it can be inefficient when most objects are close to each other and exact collision detection are required. Culling process must be simple and fast with minimal overheads. We describe a fast culling scheme using a nobel spatial hashing method with inner-voxel culling(a culling process among primitives in each voxel). Previously, spatial hashing techniques have been used for culling, and exact collision detections were performed between all primitive pairs in a voxel. But due to hash collisions and the inefficiency of fixed grids, unnecessary exact collision checks are mandated, which substantially hamper the culling that consists of two levels: primitive level and element level based on 26-discrete oriented polytopes and surface normal. In addition, our algorithm is parallelized to utilize multi-core processors. Our method performs both inner-collision and self-collision in a linear runtime on the input primitives. Moreover, our method needs no preprocessing and has no assumption or limitations on topology and accuracy.

Paper [PDF]

S. Jung and M. Choi, A Fast Culling Scheme for Deformable Object Collision Detection Using Spatial Hashing.Proceedings of 14th International Conference on Geometry and Graphics, 2010.