“Volume contact constraints at arbitrary resolution” by Allard, Faure, Courtecuisse, Falipou, Duriez, et al. …
Conference:
Type(s):
Title:
- Volume contact constraints at arbitrary resolution
Presenter(s)/Author(s):
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.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