“Staggered projections for frictional contact in multibody systems”
Conference:
Type(s):
Title:
- Staggered projections for frictional contact in multibody systems
Session/Category Title: Physically-based animation
Presenter(s)/Author(s):
Abstract:
We present a new discrete velocity-level formulation of frictional contact dynamics that reduces to a pair of coupled projections and introduce a simple fixed-point property of this coupled system. This allows us to construct a novel algorithm for accurate frictional contact resolution based on a simple staggered sequence of projections. The algorithm accelerates performance using warm starts to leverage the potentially high temporal coherence between contact states and provides users with direct control over frictional accuracy. Applying this algorithm to rigid and deformable systems, we obtain robust and accurate simulations of frictional contact behavior not previously possible, at rates suitable for interactive haptic simulations, as well as large-scale animations. By construction, the proposed algorithm guarantees exact, velocity-level contact constraint enforcement and obtains long-term stable and robust integration. Examples are given to illustrate the performance, plausibility and accuracy of the obtained solutions.
References:
1. Anitescu, M., and Hart, G. D. 2004. A fixed-point iteration approach for multibody dynamics with contact and small friction. Mathematical Programming 101, 1, 3–32.Google ScholarDigital Library
2. Anitescu, M., and Potra, F. R. 1997. Formulating dynamic multirigid-body contact problems with friction as solvable linear complementarity problems. ASME Nonlinear Dynamics 14, 231–247.Google ScholarCross Ref
3. Baraff, D., and Witkin, A. P. 1992. Dynamics simulation of non-penetrating flexible bodies. In Computer Graphics (SIGGRAPH 92), 303–308. Google Scholar
4. Baraff, D. 1989. Analytical methods for dynamic simulation of non-penetrating rigid bodies. In Computer Graphics (SIGGRAPH 89), 223–232. Google Scholar
5. Baraff, D. 1991. Coping with friction for non-penetrating rigid body simulation. In Computer Graphics (SIGGRAPH 91), 31–41. Google Scholar
6. Baraff, D. 1993. Issues in computing contact forces for non-penetrating rigid bodies. Algorithmica 10, 2–4, 292–352.Google ScholarDigital Library
7. Baraff, D. 1994. Fast contact force computation for nonpenetrating rigid bodies. In Proc. ACM SIGGRAPH 94, 23–34. Google Scholar
8. Barbič, J., and James, D. L. 2005. Real-time subspace integration for St. Venant-Kirchhoff deformable models. ACM Trans. Graph. (SIGGRAPH 05) 24, 3, 982–990. Google ScholarDigital Library
9. Bauschke, H. 2000. Projection algorithms: results and open problems. In Inherently Parallel Algorithms in Feasibility and Optimization and their Applications, 11–22.Google Scholar
10. Boyd, S., and Vandenberghe, L. 2004. Convex Optimization. Cambridge. Google Scholar
11. Bridson, R., Fedkiw, R. P., and Anderson, J. 2002. Robust treatment of collisions, contact, and friction for cloth animation. ACM Trans. Graph. (SIGGRAPH 02) 21, 3, 594–603. Google ScholarDigital Library
12. Brogliato, B. 1999. Nonsmooth Mechanics. Springer–Verlag.Google Scholar
13. Cirak, F., and West, M. 2005. Decomposition contact response (DCR) for explicit finite element dynamics. International Journal for Numerical Methods in Engineering 64, 8, 1078–1110.Google ScholarCross Ref
14. Duriez, C., Dubois, F., Andriot, C., and Kheddar, A. 2006. Realistic haptic rendering of interacting deformable objects in virtual environments. IEEE Transactions on Visualization and Computer Graphics. Google Scholar
15. Erdmann, M. E. 1994. On a representation of friction in configuration space. The International Journal of Robotics Research 13, 3, 240–271.Google ScholarCross Ref
16. Erleben, K. 2007. Velocity-based shock propagation for multibody dynamics animation. ACM Trans. Graph. 26, 2. Google ScholarDigital Library
17. Ferris, M. C., and Munson, T. S. 1998. Complementarity problems in GAMS and the PATH solver. Mathematical Programming Technical Report 98–12.Google Scholar
18. Fichera, G. 1964. Problemi elastostatici con vincoli unilaterali: il problema di Signorini con ambique condizioni al contorno. Mem. Ace. Naz. Lincei 8, 7, 91–14.Google Scholar
19. Gibson, S. F., and Mirtich, B. 1997. A survey of de-formable models in computer graphics. Technical Report TR-97-19, MERL.Google Scholar
20. Goldfarb, D., and Idnani, G. 1983. A numerically stable dual method for solving strictly convex quadratic programs. Mathematical Programming 27, 1–33.Google ScholarDigital Library
21. Guendelman, E., Bridson, R., and Fedkiw, R. 2003. Non-convex rigid bodies with stacking. ACM Trans. Graph. (SIGGRAPH 03) 22, 3, 871–878. Google ScholarDigital Library
22. Hahn, J. K. 1988. Realistic animation of rigid bodies. In Computer Graphics (SIGGRAPH 88), 299–308. Google Scholar
23. Harmon, D., Vouga, E., Tamstorf, R., and Grinspun, E. 2008. Robust treatment of simultaneous collisions. ACM Trans. Graph. (SIGGRAPH 08) 27, 3. Google ScholarDigital Library
24. Hauser, K. K., Shen, C., and O’Brien, J. F. 2003. Interactive deformation using modal analysis with constraints. In Graphics Interface, 247–255.Google Scholar
25. Hertz, H. 1882. On the contact of elastic solids. J. Reine und. Angewandte Mathmatik 92, 156, 156–171.Google Scholar
26. Irving, G., Schroeder, C., and Fedkiw, R. 2007. Volume conserving finite element simulations of deformable models. ACM Trans. Graph. (SIGGRAPH 07) 26, 3. Google ScholarDigital Library
27. James, D. L., and Pai, D. K. 2004. BD-Tree: Output-sensitive collision detection for reduced deformable models. ACM Trans. Graph. (SIGGRAPH 04) 23, 3, 393–398. Google ScholarDigital Library
28. Johnson, K. L. 1985. Contact Mechanics. Cambridge.Google Scholar
29. Jourdan, F., Alart, P., and Jean, M. 1998. A Gauss-Seidel like algorithm to solve frictional contact problems. Comput. Methods Appl. Mech. Eng. 155, 31–47.Google ScholarCross Ref
30. Kaufman, D. M., Edmunds, T., and Pai, D. K. 2005. Fast frictional dynamics for rigid bodies. ACM Trans. Graph. (SIGGRAPH 05) 24, 3, 946–956. Google ScholarDigital Library
31. Kikuchi, N., and Oden, J. 1988. Contact Problems in Elasticity: A study of variational inequalities and finite element methods. SIAM Studies in Applied and Numerical Mathematics.Google Scholar
32. Klarbring, A. 1986. A mathematical programming approach to three-domensional contact problems with friction. Comput. Methods Appl. Mech. Eng. 58, 175–200. Google ScholarDigital Library
33. Lö tstedt, P. 1984. Numerical simulation of time-dependent contact friction problems in rigid body mechanics. SIAM Journal of Scientific Statistical Computing 5, 2, 370–393.Google ScholarCross Ref
34. Milenkovic, V. J., and Schmidl, H. 2001. Optimization-based animation. In Proc. ACM SIGGRAPH 01, 37–46. Google Scholar
35. Mirtich, B., and Canny, J. F. 1995. Impulse-based dynamic simulation of rigid bodies. In Symposium on Interactive 3D Graphics. Google Scholar
36. Moore, M., and Wilhelms, J. 1988. Collision detection and response for computer animation. In Computer Graphics (SIGGRAPH 88), 289–298. Google Scholar
37. Moreau, J. J. 1966. Quadratic programming in mechanics: Onesided constraints. Journal SIAM Control 4, 1, 153–158.Google ScholarCross Ref
38. Moreau, J. J. 1973. On unilateral constraints, friction and plasticity. New Variational Techniques in Mathematical Physics, 172–322.Google Scholar
39. Murty, K., and Kabadi, S. 1987. Some NP-complete problems in quadratic and nonlinear programming. Mathematical Programing 39, 117–129. Google ScholarDigital Library
40. Murty, K. G. 1988. Linear Complementarity, Linear and Nonlinear Programming. Helderman Verlag.Google Scholar
41. Nealen, A., Mller, M., Keiser, R., Boxerman, E., and Carlson, M. 2005. Physically based deformable models in computer graphics. In Eurographics 2005.Google Scholar
42. Otaduy, M. A., Germann, D., Redon, S., and Gross, M. 2007. Adaptive deformations with fast tight bounds. In Proc. of the ACM SIGGRAPH/Eurographics Symposium on Computer Animation. Google ScholarDigital Library
43. Painlevé, P. 1895. Sur le lois du frottement de glissemment. C. R. Acad. Sci. Paris 121, 112–115.Google Scholar
44. Pauly, M., Pai, D. K., and Guibas, L. 2004. Quasi-rigid objects in contact. In ACM SIGGRAPH Symposium on Computer Animation, ACM/Eurographics. Google Scholar
45. Raghupathi, L., and Faure, F. 2006. QP-Collide: A new approach to collision treatment. In journées du groupe de travail Animation et Simulation (GTAS), 91–101.Google Scholar
46. Redon, S., Kheddar, A., and Coquillart, S. 2002. Gauss’ least constraints principle and rigid body simulations. In IEEE International Conference on Robotics and Automation.Google Scholar
47. Schittkowski, K. 2005. QL: A Fortran code for convex quadratic programming – user’s guide, Version 2.11. Report, Department of Mathematics, University of Bayreuth.Google Scholar
48. Shabana, A. 2005. Dynamics of Multibody Systems, 3rd ed. Cambridge.Google Scholar
49. Signorini, S. 1933. Sopra akune questioni di elastostatica. Atti della Societa Italiana per il Progresso della Scienze.Google Scholar
50. Smith, R. 2006. Open Dynamics Engine, V0.5, user guide.Google Scholar
51. Song, P., and Kumar, V. 2003. Distributed compliant model for efficient dynamic simulation of systems with frictional contacts. In The 2003 ASME Design Engineering Technical Conferences.Google Scholar
52. Spillmann, J., Becker, M., and Teschner, M. 2007. Non-iterative computation of contact forces for deformable objects. Journal of WSCG 15, 13.Google Scholar
53. Stewart, D., and Trinkle, J. C. 1996. An implicit time-stepping scheme for rigid body dynamics with inelastic collisions and Coulomb friction. International Journal Numerical Methods Engineering 39, 2673–2691.Google ScholarCross Ref
54. Stewart, D. E. 2000. Rigid-body dynamics with friction and impact. SIAM Rev. 42, 1, 3–39. Google ScholarDigital Library
55. Stewart, D. E. 2001. Finite-dimensional contact mechanics. Phil. Trans. R. Soc. Lond. A 359, 2467–2482.Google ScholarCross Ref
56. Terzopoulos, D., and Witkin, A. 1988. Physically based models with rigid and deformable components. IEEE Computer Graphics and Applications 8, 6, 41–51. Google ScholarDigital Library
57. Trinkle, J. C., Pang, J. S., Sudarsky, S., and Lo, G. 1995. On dynamic multi-rigid-body contact problems with Coulomb friction. Tech. rep., Texas A&M University, Department of Computer Science. Google Scholar
58. Wasfy, T. M., and Noor, A. K. 2003. Computational strategies for flexible multibody systems. Applied Mechanics Reviews 56, 6 (November), 553–613.Google ScholarCross Ref
59. Wriggers, P. 2002. Computational Contact Mechanics. John Wiley and Sons, Ltd.Google Scholar
