“VolCCD: Fast Continuous Collision Culling Between Deforming Volume Meshes” by Tang, Manocha, Yoon, Du, Heo, et al. …

We present a novel culling algorithm to perform fast and robust continuous collision detection between deforming volume meshes. This includes a continuous separating axis test that can conservatively check whether two volume meshes overlap during a given time interval. In addition, we present efficient methods to eliminate redundant elementary tests between the features (e.g., vertices, edges, and faces) of volume elements (e.g., tetrahedra, hexahedra, triangular prisms, etc.). Our approach is applicable to various deforming meshes, including those with changing topologies, and efficiently computes the first time of contact. We are able to perform inter-object and intra-object collision queries in models represented with tens of thousands of volume elements at interactive rates on a single CPU core. Moreover, we observe more than an order of magnitude performance improvement over prior methods.

ABAQUS. 2003. ABAQUS 6.4. Analysis User’s Manual. Hibbitt, Karlsson & Sorensen, Inc.Google Scholar
Allard, J., Faure, F., Courtecuisse, H., Falipou, F., Duriez, C., and Kry, P. G. 2010. Volume contact constraints at arbitrary resolution. In Proceedings of the ACM SIGGRAPH Conference. ACM, 1–10. Google ScholarDigital Library
Bridson, R., Fedkiw, R., and Anderson, J. 2002. Robust treatment of collisions, contact and friction for cloth animation. ACM Trans. Graph. 21, 3, 594–603. Google ScholarDigital Library
Curtis, S., Tamstorf, R., and Manocha, D. 2008. Fast collision detection for deformable models using representative-triangles. In Proceedings of the Symposium on Interactive 3D Graphics and Games. 61–69. Google ScholarDigital Library
Eberly, D. H. 2000. 3D Game Engine Design: A Practical Approach to Real-Time Computer Graphics. Morgan Kaufmann. Google ScholarDigital Library
Erleben, K., Dohlmann, H., and Sporring, J. 2005. The adaptive thin shell tetrahedral mesh. In J. WSCG. 17–24.Google Scholar
Faure, F., Barbier, S., Allard, J., and Falipou, F. 2008. Image-based collision detection and response between arbitrary volume objects. In Proceedings of the Symposium on Computer Animation. 155–162. Google ScholarDigital Library
Fisher, S. and Lin, M. C. 2001. Deformed distance fields for simulation of non-penetrating flexible bodies. In Proceedings of the Eurographic Workshop on Computer Animation and Simulation. Springer, 99–111. Google ScholarDigital Library
Fleissner, F., Eberhard, P., Bischof, C., Bcker, M., Gibbon, P., Joubert, G. R., Mohr, B., (eds, F. P., Fleissner, F., and Eberhard, P. 2007. Load balanced parallel simulation of particle-fluid dem-sph systems with moving boundaries. In Proceedings of Parallel Computing: Architectures, Algorithms and Applications Conference. 37–44.Google Scholar
Gottschalk, S., Lin, M., and Manocha, D. 1996. OBB-Tree: A hierarchical structure for rapid interference detection. In Proceedings of ACM Siggraph Conference. 171–180. Google ScholarDigital Library
Govindaraju, N., Knott, D., Jain, N., Kabul, I., Tamstorf, R., Gayle, R., Lin, M., and Manocha, D. 2005. Interactive collision detection between deformable models using chromatic decomposition. ACM Trans. Graph. 24, 3, 991–999. Google ScholarDigital Library
Hallquist, J. 2006. LS-DYNA Theory Manual. Livermore Software Technology Corporation.Google Scholar
Heidelberger, B., Teschner, M., and Gross, M. 2003. Real-time volumetric intersections of deforming objects. In Proceedings of Vision Modeling Visualization Conference (VMV’03). 461–468.Google Scholar
Heidelberger, B., Teschner, M., Keiser, R., Müller, M., and Gross, M. 2004. Consistent peneration depth estimation for deformable collision response. In Proceedings of Vision Modeling Visualization Conference (VMV’04). 330–346.Google Scholar
Heo, J.-P., Seong, J.-K., Kim, D., Otaduy, M. A., Hong, J.-M., Tang, M., and Yoon, S.-E. 2010. FASTCD: Fracturing-Aware stable collision detection. In Proceedings of the ACM SIGGRAPH /Eurographics Symposium on Computer Animation. Google ScholarDigital Library
Hutter, M. and Fuhrmann, A. 2007. Optimized continuous collision detection for deformable triangle meshes. In Proceedings of the WSCG ’07. 25–32.Google Scholar
Irving, G., Teran, J., and Fedkiw, R. 2004. Invertible finite elements for robust simulation of large deformation. In Proceedings of the Symposium on Computer Animation. 131–140. Google ScholarDigital Library
Klosowski, J., Held, M., Mitchell, J., Sowizral, H., and Zikan, K. 1998. Efficient collision detection using bounding volume hierarchies of k-dops. IEEE Trans. Vis. Comput. Graph. 4, 1, 21–37. Google ScholarDigital Library
Levine, R. 2000. Collisions of moving objects. http://realtime collisiondetection.net/files/levine_swept_sat.txt.Google Scholar
Lombardo, J.-C., paule Cani, M., and Neyret, F. 1999. Real-time collision detection for virtual surgery. In Proceedings of the Symposium on Computer Animation. 26–28. Google ScholarDigital Library
LS-DYNA. 2001. Contact modeling in LS-DYNA. http://www.dynasupport.com/tutorial/contact-modeling-in-ls-dyna/contact-types.Google Scholar
Mathias, E. and Gu, L. 2007. Hierarchical spatial hashing for real-time collision detection. In Proceedings of the IEEE International Conference on Shape Modeling and Applications. 61–70. Google ScholarDigital Library
Müller, M., McMillan, L., Dorsey, J., and Jagnow, R. 2001. Real-time simulation of deformation and fracture of stiff materials. In Proceedings of the Eurographic Workshop on Computer Animation and Simulation. 113–124. Google ScholarDigital Library
National-Crash-Analysis-Center. 2010. Finite element model archive. http://www.ncac.gwu.edu/vml/models.html.Google Scholar
Nealen, A., Müller, M., Keiser, R., Boxerman, E., and Carlson, M. 2006. Physically based deformable models in computer graphics. Comput. Graph. Forum 25, 4, 809–836.Google ScholarCross Ref
O’Brien, J. F. 2000. Graphical modeling and animation of brittle fracture. Ph.D. thesis, Georgia Institute of Technology, Atlanta, GA. Google ScholarDigital Library
O’Brien, J. F. and Hodgins, J. K. 1999. Graphical modeling and animation of brittle fracture. In Proceedings of the 26th Annual Conference on Computer Graphics and Interactive Techniques. 137–146. Google ScholarDigital Library
Parker, E. G. and O’Brien, J. F. 2009. Real-Time deformation and fracture in a game environment. In Proceedings of the Symposium on Computer Animation. 165–175. Google ScholarDigital Library
Plimpton, S., Attaway, S., Hendrickson, B., Swegle, J., Vaughan, C., and Gardner, D. 1998. Parallel transient dynamics simulations: Algorithms for contact detection and smoothed particle hydrodynamics. J. Parall. Distrib. Comput. 50, 1-2, 104–122. Google ScholarDigital Library
Provot, X. 1997. Collision and self-collision handling in cloth model dedicated to design garment. In Proceedings of the Graph. Interface Conference. 177–189.Google ScholarCross Ref
Redon, S., Kheddar, A., and Coquillart, S. 2002. Fast continuous collision detection between rigid bodies. Comput. Graph. Forum. 21, 3, 279–288.Google ScholarCross Ref
Sifakis, E., Der, K. G., and Fedkiw, R. 2007. Arbitrary cutting of deformable tetrahedralized objects. In Proceedings of the ACM SIGGRAPH/Eurographics Symposium on Computer Animation. 73–80. Google ScholarDigital Library
Sud, A., Govindaraju, N., Gayle, R., Kabul, I., and Manocha, D. 2006. Fast proximity computation among deformable models using discrete voronoi diagrams. In Proceedings of the ACM SIGGRAPH Conference. 1144–1153. Google ScholarDigital Library
Tang, M., Curtis, S., Yoon, S.-E., and Manocha, D. 2009. ICCD: Interactive continuous collision detection between deformable models using connectivity-based culling. IEEE Trans. Vis. Comput. Graph. 15, 4, 544–557. Google ScholarDigital Library
Tang, M., Kim, Y. J., and Manocha, D. 2010b. Continuous collision detection for non-rigid contact computations using local advancement. In Proceedings of International Conference on Robotics and Automation.Google Scholar
Tang, M., Manocha, D., Lin, J., and Tong, R. 2011. Collision-streams: Fast GPU-based collision detection for deformable models. In Proceedings of the ACM SIGGRAPH Symposium on Interactive 3D Graphics and Games (I3D’11). 63–70. Google ScholarDigital Library
Tang, M., Manocha, D., and Tong, R. 2010a. Fast continuous collision detection using deforming non-penetration filters. In Proceedings of the ACM SIGGRAPH Symposium on Interactive 3D Graphics and Games (I3D’10). ACM, New York, 7–13. Google ScholarDigital Library
Teschner, M., Heidelberger, B., Müller, M., Pomeranets, D., and Gross, M. 2003. Optimized spatial hashing for collision detection of deformable objects. In Proceedings of Vision Modeling Visualization Conference (VMV’03). 47–54.Google Scholar
Teschner, M., Kimmerle, S., Heidelberger, B., Zachmann, G., Raghupathi, L., Fuhrmann, A., Cani, M.-P., Faure, F., Magnenat-Thalmann, N., Strasser, W., and Volino, P. 2005. Collision detection for deformable objects. Comput. Graph. Forum 19, 1, 61–81.Google ScholarCross Ref
Volino, P. and Magnenat-Thalmann, N. 2006. Resolving surface collisions through intersection contour minimization. ACM Trans. Graph. 25, 3, 1154–1159. Google ScholarDigital Library
Volino, P. and Thalmann, N. M. 1994. Efficient self-collision detection on smoothly discretized surface animations using geometrical shape regularity. Comput. Graph. Forum 13, 3, 155–166.Google ScholarCross Ref
Wojtan, C., Thürey, N., Gross, M., and Turk, G. 2009. Deforming meshes that split and merge. ACM Trans. Graph. 28, 76:1–76:10. Google ScholarDigital Library
Zhang, X., Redon, S., Lee, M., and Kim, Y. J. 2007. Continuous collision detection for articulated models using taylor models and temporal culling. ACM Trans. Graph. 26, 3, 15. Google ScholarDigital Library
Zhu, Y., Sifakis, E., Teran, J., and Brandt, A. 2010. An efficient multigrid method for the simulation of high-resolution elastic solids. ACM Trans. Graph. 29, 2, 1–18. Google ScholarDigital Library