“Fast frictional dynamics for rigid bodies” by Kaufman, Edmunds and Pai

We describe an efficient algorithm for the simulation of large sets of non-convex rigid bodies. The algorithm finds a simultaneous solution for a multi-body system that is linear in the total number of contacts detected in each iteration. We employ a novel contact model that uses mass, location, and velocity information from all contacts, at the moment of maximum compression, to constrain rigid body velocities. We also develop a new friction model in the configuration space of rigid bodies. These models are used to compute the feasible velocity and the frictional response of each body. Implementation is simple and leads to a fast rigid body simulator that computes steps on the order of seconds for simulations involving over one thousand non-convex objects in high contact configurations.

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. 1989. Analytical methods for dynamic simulation of non-penetrating rigid bodies. In Computer Graphics (SIGGRAPH 89), 223–232. Google ScholarDigital Library
4. Baraff, D. 1991. Coping with friction for non-penetrating rigid body simulation. In Computer Graphics (SIGGRAPH 91), 31–41. Google ScholarDigital Library
5. Baraff, D. 1994. Fast contact force computation for nonpenetrating rigid bodies. In Proceedings of ACM SIGGRAPH 94, 23–34. Google ScholarDigital Library
6. Brogliato, B. 1999. Nonsmooth Mechanics. Springer-Verlag.Google Scholar
7. Chatterjee, A., and Ruina, A. L. 1998. A new algebraic rigid-body collision law based on impulse space considerations. Journal of Applied Mechanics 65, 4, 939–951.Google ScholarCross Ref
8. Chatterjee, A., and Ruina, A. L. 1998. Two interpretations of rigidity in rigid body collisions. Journal of Applied Mechanics 65, 4, 894–900.Google ScholarCross Ref
9. Chatterjee, A., 1999. On the realism of complementarity conditions in rigid body collisions. Nonlinear Dynamics 20, 159–168.Google ScholarCross Ref
10. Delassus, E. 1923. Sur les lois du froittement de glissement. Bulletin de la Societe Mathematique de France 51, 22–23.Google ScholarCross Ref
11. Erdmann, M. E. 1984. On Motion Planning with Uncertainty. Master’s thesis, Massachusetts Institute of Technology.Google Scholar
12. Gottschalk, S., Lin, M. C., and Manocha, D. 1996. OBB-tree: A hierarchical structure for rapid interference detection. In Proceedings of ACM SIGGRAPH 96, 171–180. Google ScholarDigital Library
13. Goyal, S., Ruina, A., and Papadopoulos, J. 1991. Planar sliding with dry friction, Part 1. Limit surface and moment function. Wear 143, 307–330.Google ScholarCross Ref
14. Guendelman, E., Bridson, R., and Fedkiw, R. 2003. Nonconvex rigid bodies with stacking. ACM Transactions on Graphics (SIGGRAPH 03) 22, 3, 871–878. Google ScholarDigital Library
15. Hahn, J. K. 1988. Realistic animation of rigid bodies. In Computer Graphics (SIGGRAPH 88), 299–308. Google ScholarDigital Library
16. Kozlov, M. K., Tarasov, S. P., and Hačijan, L. G. 1979. Polynomial solvability of convex quadratic programming. Soviet Mathematics Doklady 20, 5, 1108–1111.Google Scholar
17. Kry, P. G., and Pai, D. K. 2003. Continuous contact simulation for smooth surfaces. ACM Transactions on Graphics 22, 1, 106–129. Google ScholarDigital Library
18. Lin, M. C., and Gottschalk, S. 1998. Collision detection between geometric models: a survey. In IMA Conference on Mathematics of Surfaces, 37–56.Google Scholar
19. 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
20. Mason, M. T. 2001. Mechanics of Robotic Manipulation. MIT Press. Google ScholarDigital Library
21. Megiddo, N., and Tamir, A. 1993. Linear time algorithms for some separable quadratic programming problems. Operations Research Letters 13, 203–211.Google ScholarDigital Library
22. Milenkovic, V. J., and Schmidl, H. 2001. Optimization-based animation. In Proceedings of ACM SIGGRAPH 01, 37–46. Google ScholarDigital Library
23. Mirtich, B., and Canny, J. F. 1995. Impulse-based dynamic simulation of rigid bodies. In Symposium on Interactive 3D Graphics. Google ScholarDigital Library
24. Mirtich, B. 1996. Fast and accurate computation of polyhedral mass properties. Journal of Graphics Tools 1, 2, 31–50. Google ScholarDigital Library
25. Moore, M., and Wilhelms, J.- 1988. Collision detection and response for computer animation. In Computer Graphics (SIGGRAPH 88), 289–298. Google ScholarDigital Library
26. Moreau, J. J. 1962. Décomposition orthogonale d’un espace hilbertien selon deux cĉnes muteullement polaires. Comptes Rendus Academy Science Paris 255, 238–240.Google Scholar
27. Moreau, J. J. 1966. Quadratic programming in mechanics: One-sided constraints. Journal SIAM Control 4, 1, 153–158.Google ScholarCross Ref
28. Moreau, J. J. 1988. Nonsmooth Mechanics and Applications. No. 302 in CISM Courses and Lectures. Springer-Verlag, New York, ch. Unilateral Contact and Dry Friction in Finite Freedom Dynamics, 1-82.Google Scholar
29. Moreau, J. J. 1994. Some numerical methods in multibody dynamics: application to granular materials. European Journal of Mechanics A/Solids 13, 4, 93–114.Google Scholar
30. Murray, R. M., Li. Z., and Sastry, S. S. 1994. A Mathematical Introduction to Robotic Manipulation. CRC Press. Google ScholarDigital Library
31. Pauly, M., Pai, D. K., and Guibas. L. 2004. Quasi-rigid objects in contact. In ACM SIGGRAPH Symposium on Computer Animation, ACM/Eurographics. Google ScholarDigital Library
32. 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
33. Rockafellar, R. T. 1970. Convex Analysis. Princeton University Press.Google Scholar
34. Schmidl, H., and Milenkovic, V. J. 2004. A fast impulsive contact suite for rigid body simulation. IEEE Transactions on Visualization and Computer Graphics 10, 2, 189–197. Google ScholarDigital Library
35. 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
36. 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
37. 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 ScholarDigital Library
38. Verlet, L. 1967. Computer experiments on classical fluids, thermodynamical properties of lennard-jones molecules. Physical Review 159, 98–103.Google ScholarCross Ref
39. Yang, K., and Murty, K. G. 1992. New iterative methods for linear inequalities. Journal of Optimization Theory and Applications 72, 1, 163–185. Google ScholarDigital Library