“Volume contact constraints at arbitrary resolution” by Allard, Faure, Courtecuisse, Falipou, Duriez, et al. …

  • ©Jérémie Allard, François Faure, Hadrien Courtecuisse, Florent Falipou, Christian Duriez, and Paul G. Kry




    Volume contact constraints at arbitrary resolution



    We introduce a new method for simulating frictional contact between volumetric objects using interpenetration volume constraints. When applied to complex geometries, our formulation results in dramatically simpler systems of equations than those of traditional mesh contact models. Contact between highly detailed meshes can be simplified to a single unilateral constraint equation, or accurately processed at arbitrary geometry-independent resolution with simultaneous sticking and sliding across contact patches. We exploit fast GPU methods for computing layered depth images, which provides us with the intersection volumes and gradients necessary to formulate the contact equations as linear complementarity problems. Straightforward and popular numerical methods, such as projected Gauss-Seidel, can be used to solve the system. We demonstrate our method in a number of scenarios and present results involving both rigid and deformable objects at interactive rates.


    1. Allard, J., Cotin, S., Faure, F., Bensoussan, P.-J., Poyer, F., Duriez, C., Delingette, H., and Grisoni, L. 2007. SOFA — an open source framework for medical simulation. In Medicine Meets Virtual Reality (MMVR’15), 13–18. http://www.sofa-framework.org.Google Scholar
    2. Anitescu, M., and Hart, G. D. 2004. Constraint-stabilized time-stepping approach for rigid multibody dynamics with joints, contact and friction. International Journal for Numerical Methods in Engineering 60, 14, 2335–2371.Google ScholarCross Ref
    3. Anitescu, M., and Potra, F. 1997. Formulating dynamic multi-rigid-body contact problems with friction as solvable linear complementarity problems. Nonlinear Dynamics 14, 3, 231–247.Google ScholarCross Ref
    4. Ascher, U. M., and Petzold, L. R. 1998. Computer Methods for Ordinary Differential Equations and Differential-Algebraic Equations. Society for Industrial and Applied Mathematics, Philadelphia, PA, USA. Google ScholarDigital Library
    5. Baciu, G., and Wong, W. S.-K. 2004. Image-based collision detection for deformable cloth models. IEEE Transactions on Visualization and Computer Graphics 10, 6, 649–663. Google ScholarDigital Library
    6. Baraff, D., and Witkin, A. 1998. Large steps in cloth simulation. In Proceedings of SIGGRAPH 98, ACM, 43–54. Google ScholarDigital Library
    7. Baraff, D. 1991. Coping with friction for non-penetrating rigid body simulation. Computer Graphics (Proceedings of SIGGRAPH 91) 25, 4, 31–41. Google ScholarDigital Library
    8. Baraff, D. 1994. Fast contact force computation for nonpenetrating rigid bodies. In Proceedings of SIGGRAPH 94, ACM, 23–34. Google ScholarDigital Library
    9. Barbič, J., and James, D. 2007. Time-critical distributed contact for 6-DoF haptic rendering of adaptively sampled reduced deformable models. In Proceedings of the 2007 ACM SIGGRAPH/Eurographics symposium on Computer animation, 171–180. Google ScholarDigital Library
    10. Batty, C., Bertails, F., and Bridson, R. 2007. A fast variational framework for accurate solid-fluid coupling. ACM Transactions on Graphics 26, 3, 100. Google ScholarDigital Library
    11. Baumgarte, J. 1972. Stabilization of constraints and integrals of motion in dynamical systems. Computer Methods in Applied Mechanics and Engineering 1, 1–16.Google ScholarCross Ref
    12. Bridson, R., Fedkiw, R., and Anderson, J. 2002. Robust treatment of collisions, contact and friction for cloth animation. In Proceedings of SIGGRAPH 2002, ACM, 594–603. Google ScholarDigital Library
    13. Cline, M. B., and Pai, D. K. 2003. Post-stabilization for rigid body simulation with contact and constraints. In IEEE International Conference on Robotics and Automation, 3744–3751.Google Scholar
    14. Debunne, G., Desbrun, M., Cani, M.-P., and Barr, A. H. 2001. Dynamic real-time deformations using space and time adaptive sampling. In Proceedings of SIGGRAPH 2001, ACM, 31–36. Google ScholarDigital Library
    15. Duriez, C., Dubois, F., Kheddar, A., and Andriot, C. 2006. Realistic haptic rendering of interacting deformable objects in virtual environments. IEEE Transactions on Visualization and Computer Graphics 12, 1, 36–47. Google ScholarDigital Library
    16. Erleben, K. 2007. Velocity-based shock propagation for multi-body dynamics animation. ACM Transactions on Graphics 26, 2, 12. Google ScholarDigital Library
    17. Faure, F., Barbier, S., Allard, J., and Falipou, F. 2008. Image-based collision detection and response between arbitrary volume objects. In SCA ’08: Proceedings of the 2008 ACM SIGGRAPH/Eurographics Symposium on Computer Animation, 155–162. Google ScholarDigital Library
    18. Gottschalk, S., Lin, M. C., and Manocha, D. 1996. OBB-Tree: a hierarchical structure for rapid interference detection. In Proceedings of SIGGRAPH 96, ACM, 171–180. Google ScholarDigital Library
    19. Guendelman, E., Bridson, R., and Fedkiw, R. Nonconvex rigid bodies with stacking. ACM Transactions on Graphics 22, 3, 871–878. Google ScholarDigital Library
    20. Harmon, D., Vouga, E., Tamstorf, R., and Grinspun, E. 2008. Robust treatment of simultaneous collisions. ACM Transactions on Graphics 27, 3, 1–4. Google ScholarDigital Library
    21. Harmon, D., Vouga, E., Smith, B., Tamstorf, R., and Grinspun, E. 2009. Asynchronous contact mechanics. ACM Transactions on Graphics 28, 3. Google ScholarDigital Library
    22. Heidelberger, B., Teschner, M., and Gross, M. 2003. Real-time volumetric intersections of deforming objects. In Proceedings of Vision, Modeling, Visualization (VMV), 461–468.Google Scholar
    23. Heidelberger, B., Teschner, M., and Gross, M. 2004. Detection of collisions and self-collisions using image-space techniques. In Proceedings of WSCG’04, 145–152.Google Scholar
    24. Hubbard, P. M. 1995. Collision Detection for Interactive Graphics Applications. PhD thesis, Brown University. Google ScholarDigital Library
    25. James, D. L., and Pai, D. K. 2004. BD-tree: output-sensitive collision detection for reduced deformable models. ACM Transactions on Graphics 23, 3, 393–398. Google ScholarDigital Library
    26. Kaufman, D. M., Edmunds, T., and Pai, D. K. 2005. Fast frictional dynamics for rigid bodies. ACM Transactions on Graphics 24, 3, 946–956. Google ScholarDigital Library
    27. Kaufman, D. M., Sueda, S., James, D. L., and Pai, D. K. 2008. Staggered projections for frictional contact in multibody systems. ACM Transactions on Graphics 27, 5, 1–11. Google ScholarDigital Library
    28. Lloyd, J. E. 2005. Fast implementation of Lemke’s algorithm for rigid body contact simulation. In IEEE International Conference on Robotics and Automation, 4538–4543.Google ScholarCross Ref
    29. Milenkovic, V. J., and Schmidl, H. 2001. Optimization-based animation. In Proceedings of SIGGRAPH 2001, ACM, 37–46. Google ScholarDigital Library
    30. Müller, M. 2008. Hierarchical position based dynamics. In VRIPHYS 08: Fifth Workshop in Virtual Reality Interactions and Physical Simulations, Eurographics Association, 1–10.Google Scholar
    31. Nealen, A., Müller, M., Keiser, R., Boxerman, E., and Carlson, M. 2005. Physically based deformable models in computer graphics. In Eurographics 2005 – State of the Art Reports, 71–94.Google Scholar
    32. Nesme, M., Payan, Y., and Faure, F. 2005. Efficient, physically plausible finite elements. In Eurographics 2005 – Short Papers, 77–80.Google Scholar
    33. Otaduy, M. A., Jain, N., Sud, A., and Lin, M. C. 2004. Haptic display of interaction between textured models. In Proceedings of IEEE Visualization Conference, 297–304. Google ScholarDigital Library
    34. Otaduy, M. A., Germann, D., Redon, S., and Gross, M. 2007. Adaptive deformations with fast tight bounds. In Proceedings of the 2007 ACM SIGGRAPH/Eurographics symposium on Computer animation, 181–190. Google ScholarDigital Library
    35. Otaduy, M. A., Tamstorf, R., Steinemann, D., and Gross, M. 2009. Implicit contact handling for deformable objects. Computer Graphics Forum (Proceedings of Eurographics) 28, 2, 559–568.Google ScholarCross Ref
    36. Pabst, S., Thomaszewski, B., and Strasser, W. 2009. Anisotropic friction for deformable surfaces and solids. In SCA ’09: Proceedings of the 2009 ACM SIGGRAPH/Eurographics Symposium on Computer Animation, 149–154. Google ScholarDigital Library
    37. Parker, E. G., and O’Brien, J. F. 2009. Real-time deformation and fracture in a game environment. In SCA ’09: Proceedings of the 2009 ACM SIGGRAPH/Eurographics Symposium on Computer Animation, 165–175. Google ScholarDigital Library
    38. Pauly, M., Pai, D. K., and Guibas, L. J. 2004. Quasi-rigid objects in contact. In SCA ’04: Proceedings of the 2004 ACM SIGGRAPH/Eurographics symposium on Computer animation, 109–119. Google ScholarDigital Library
    39. Provot, X. 1997. Collision and self-collision handling in cloth model dedicated to design garments. In Proceedings of 8th Eurographics Workshop on Animation and Simulation, 177–189.Google ScholarCross Ref
    40. Shi, L., Yu, Y., Bell, N., and Feng, W.-W. 2006. A fast multigrid algorithm for mesh deformation. ACM Transactions on Graphics 25, 3, 1108–1117. Google ScholarDigital Library
    41. Stewart, D. E., and Trinkle, J. C. 1996. An implicit time-stepping scheme for rigid body dynamics with inelastic collisions and coulomb friction. International Journal of Numerical Methods Engineering 39, 15, 2673–2691.Google ScholarCross Ref
    42. Stewart, D. E. 2000. Rigid-body dynamics with friction and impact. SIAM Review 42, 1, 3–39. Google ScholarDigital Library
    43. Sud, A., Govindaraju, N., Gayle, R., Kabul, I., and Manocha, D. 2006. Fast proximity computation among deformable models using discrete voronoi diagrams. ACM Transactions on Graphics 25, 3, 1144–1153. Google ScholarDigital Library
    44. Teschner, M., Kimmerle, S., Heidelberge, B., Zachmann, G., Raghupathi, L., Fuhrmann, A., Cani, M.-P., Faure, F., Magnenat-Thalmann, N., Strasser, W., and Volino, P. 2004. Collision detection for deformable objects. In Eurographics 2004 – State of the Art Reports.Google Scholar
    45. van den Bergen, G. 1997. Efficient collision detection of complex deformable models using aabb trees. Journal of Graphics Tools 2, 4, 1–13. Google ScholarDigital Library
    46. Vassilev, T., Spanlang, B., and Chrysanthou, Y. 2001. Fast cloth animation on walking avatars. Computer Graphics Forum (Proceedings of Eurographics) 20, 3, 260–267.Google ScholarCross Ref
    47. Volino, P., and Magnenat-Thalmann, N. 1995. Collision and self-collision detection: Efficient and robust solutions for higly deformable surfaces. In Computer Animation and Simulation ’95, 55–65.Google Scholar
    48. Wong, W. S.-K., and Baciu, G. 2005. GPU-based intrinsic collision detection for deformable surfaces: Collision detection and deformable objects. Computer Animation and Virtual Worlds 16, 3–4, 153–161. Google ScholarDigital Library

ACM Digital Library Publication:

Overview Page: