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

Balanced Spatial Subdivision Method for Continuous Collision Detection

Abstract: A new optimization technique is presented for the spatial subdivision of a three-dimensional (3D) geometric model to improve the overall performance of continuous collision detection between deformable objects. Spatial subdivision methods decompose a spatial geometric region into a number of predefined voxels (the storage of 3D finite space, or a 'cell') that helps to achieve close to linear performance in collision detection. An optimal performance can be achieved when the subdivision is evenly dispersed. If there must be any subsequent re-subdivision the overall performance is substantially hampered due to the overwhelming cost of the re-subdivision and its associated overhead. Typically a spatial hashing technique is chosen to map a large number of 3D cells into finite voxels. But previous spatial hashing approaches are unable to maximize spatial subdivision method because they do not provide an optimal solution when there are conflicts between changing dispersion patterns of cells for deformable objects and the cost of re-subdivision. The problem of uneven concentration of cells is especially prominent when a deformable object is squeezed and far-stretched. Our method can balance them in a simple way to maximize the performance of spatial subdivision.

Paper [PDF]

S. Jung, M. Choi, "Balanced Spatial Subdivision Method for Continuous Collision Detection", Proceedings of 13th International Conference on Geometry and Graphics, 2008.