Continuous Collision Detection for Deformable Solids with Topological Changes
As part of our surgical simulation efforts and in collaboration with UNC, our work on a continuous collision detection for deformable solids algorithm was presented at the ACM SIGGRAPH Symposium on Interactive 3D Graphics and Games (I3D), which was held in San Francisco, CA, from February 27 to March 1, 2015.
Background
Collision detection is a fundamental problem in surgical simulations where there are significant interactions between blood vessels, organs, and instruments. Developing a robust collision detection and response algorithm is vital for providing force fields used by the FEM framework to produce realistic visual and force feedback to the user of the simulator. With large numbers of primitives in a neurosurgical simulation virtual world, a brute-force method is not suitable for an interactive simulator application. Our goal is to compute fast and accurate collision detection between the mesh elements. As forces are applied, meshes deform and nodes or points inside the object move.
New approach
We developed a fast algorithm for continuous collision detection between deformable models. Our approach performs no precomputation and can handle general triangulated models undergoing topological changes. We present a fast decomposition algorithm that represents the mesh boundary using hierarchical clusters composed of triangle primitives that only need to perform inter-cluster collision checks. One of the main contributions of this work is a scheme that computes such clusters quickly and merges them to generate a dynamic bounding volume hierarchy (BVH). The overall approach reduces the overhead of computing the hierarchy and also reduces the number of false positives. This work is complementary to other collision culling approaches and can be used along those techniques.
Video (prepared by Liang He, Gamma group at UNC)
Results
A comparision with a state-of-the-art collision detection method (Self-CCD) was made using multiple benchmarks, providing an up to five times speed-up.
The tables show how much time is spent in each of the algorithm; the time displayed includes the dynamic generation of clusters, the BVH computation, and all collision queries performed using tree traversal. As the tables indicate, the time spent in the dynamic clustering phase is relatively small compared to the time required for the other two phases. This is because the cluster-computation algorithm only needs to perform orientation tests, which simply involve a few arithmetic operations and a dot product. Also, our approach results in fewer boundary volume tests and fewer elementary tests.
Future Work
We would like to parallelize our dynamic clustering algorithm on multicore processors or GPUs. Furthermore, we would like to integrate our CCD algorithm into a Fininte Element simulator and evaluate its performance. Finally, we would like to design dynamic simulation algorithms that can exploit the capabilities of the CCD algorithm in terms of collision response.
ACKNOWLEDGMENT: Research reported in this publication was supported by the Office Of The Director, National Institutes Of Health of the National Institutes of Health under Award Number R44OD018334. The content is solely the responsibility of the authors and does not necessarily represent the official views of the National Institutes of Health.