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

  • ©Min Tang, Dinesh Manocha, Sung-Eui Yoon, Peng Du, Jae-Pil Heo, and Ruo-Feng Tong

Conference:


Type(s):


Title:

    VolCCD: Fast Continuous Collision Culling Between Deforming Volume Meshes

Presenter(s)/Author(s):



Abstract:


    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.

References:


    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


ACM Digital Library Publication:



Overview Page: