Volume contact constraints at arbitrary resolution

ABSTRACT

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.

References

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.
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.
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.
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.
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.
6. Baraff, D., and Witkin, A. 1998. Large steps in cloth simulation. In Proceedings of SIGGRAPH 98, ACM, 43--54.
7. Baraff, D. 1991. Coping with friction for non-penetrating rigid body simulation. Computer Graphics (Proceedings of SIGGRAPH 91) 25, 4, 31--41.
8. Baraff, D. 1994. Fast contact force computation for nonpenetrating rigid bodies. In Proceedings of SIGGRAPH 94, ACM, 23--34.
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.
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.
11. Baumgarte, J. 1972. Stabilization of constraints and integrals of motion in dynamical systems. Computer Methods in Applied Mechanics and Engineering 1, 1--16.
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.
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.
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.
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.
16. Erleben, K. 2007. Velocity-based shock propagation for multi-body dynamics animation. ACM Transactions on Graphics 26, 2, 12.
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.
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.
19. Guendelman, E., Bridson, R., and Fedkiw, R. Nonconvex rigid bodies with stacking. ACM Transactions on Graphics 22, 3, 871--878.
20. Harmon, D., Vouga, E., Tamstorf, R., and Grinspun, E. 2008. Robust treatment of simultaneous collisions. ACM Transactions on Graphics 27, 3, 1--4.
21. Harmon, D., Vouga, E., Smith, B., Tamstorf, R., and Grinspun, E. 2009. Asynchronous contact mechanics. ACM Transactions on Graphics 28, 3.
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.
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.
24. Hubbard, P. M. 1995. Collision Detection for Interactive Graphics Applications. PhD thesis, Brown University.
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.
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.
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.
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.
29. Milenkovic, V. J., and Schmidl, H. 2001. Optimization-based animation. In Proceedings of SIGGRAPH 2001, ACM, 37--46.
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.
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.
32. Nesme, M., Payan, Y., and Faure, F. 2005. Efficient, physically plausible finite elements. In Eurographics 2005 - Short Papers, 77--80.
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.
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.
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.
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.
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.
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.
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.
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.
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.
42. Stewart, D. E. 2000. Rigid-body dynamics with friction and impact. SIAM Review 42, 1, 3--39.
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.
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.
45. van den Bergen, G. 1997. Efficient collision detection of complex deformable models using aabb trees. Journal of Graphics Tools 2, 4, 1--13.
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.
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.
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.

Index Terms

• Computing methodologies

  • Computer graphics

    • Animation

    • Shape modeling

• Theory of computation

  • Randomness, geometry and discrete structures

    • Computational geometry