Fast frictional dynamics for rigid bodies

ABSTRACT

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.

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.
• 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.
• 3: D. Baraff, Analytical methods for dynamic simulation of non-penetrating rigid bodies, Proceedings of the 16th annual conference on Computer graphics and interactive techniques, p.223-232, July 1989
• 4: David Baraff, Coping with friction for non-penetrating rigid body simulation, Proceedings of the 18th annual conference on Computer graphics and interactive techniques, p.31-41, July 1991
• 5: David Baraff, Fast contact force computation for nonpenetrating rigid bodies, Proceedings of the 21st annual conference on Computer graphics and interactive techniques, p.23-34, July 1994 [doi>10.1145/192161.192168]
• 6: Brogliato, B. 1999. Nonsmooth Mechanics. Springer-Verlag.
• 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.
• 8: Chatterjee, A., and Ruina, A. L. 1998. Two interpretations of rigidity in rigid body collisions. Journal of Applied Mechanics 65, 4, 894--900.
• 9: Chatterjee, A., 1999. On the realism of complementarity conditions in rigid body collisions. Nonlinear Dynamics 20, 159--168.
• 10: Delassus, E. 1923. Sur les lois du froittement de glissement. Bulletin de la Societe Mathematique de France 51, 22--23.
• 11: Erdmann, M. E. 1984. On Motion Planning with Uncertainty. Master's thesis, Massachusetts Institute of Technology.
• 12: S. Gottschalk , M. C. Lin , D. Manocha, OBBTree: a hierarchical structure for rapid interference detection, Proceedings of the 23rd annual conference on Computer graphics and interactive techniques, p.171-180, August 1996 [doi>10.1145/237170.237244]
• 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.
• 14: Eran Guendelman , Robert Bridson , Ronald Fedkiw, Nonconvex rigid bodies with stacking, ACM Transactions on Graphics (TOG), v.22 n.3, July 2003
• 15: James K. Hahn, Realistic animation of rigid bodies, Proceedings of the 15th annual conference on Computer graphics and interactive techniques, p.299-308, June 1988
• 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.
• 17: Paul G. Kry , Dinesh K. Pai, Continuous contact simulation for smooth surfaces, ACM Transactions on Graphics (TOG), v.22 n.1, p.106-129, January 2003 [doi>10.1145/588272.588280]
• 18: Lin, M. C., and Gottschalk, S. 1998. Collision detection between geometric models: a survey. In IMA Conference on Mathematics of Surfaces, 37--56.
• 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.
• 20: Matthew T. Mason, Mechanics of robotic manipulation, MIT Press, Cambridge, MA, 2001
• 21: Megiddo, N., and Tamir, A. 1993. Linear time algorithms for some separable quadratic programming problems. Operations Research Letters 13, 203--211.
• 22: Victor J. Milenkovic , Harald Schmidl, Optimization-based animation, Proceedings of the 28th annual conference on Computer graphics and interactive techniques, p.37-46, August 2001 [doi>10.1145/383259.383263]
• 23: Brian Mirtich , John Canny, Impulse-based simulation of rigid bodies, Proceedings of the 1995 symposium on Interactive 3D graphics, p.181-ff., April 09-12, 1995, Monterey, California, United States [doi>10.1145/199404.199436]
• 24: Brian Mirtich, Fast and accurate computation of polyhedral mass properties, Journal of Graphics Tools, v.1 n.2, p.31-50, February 1996
• 25: Matthew Moore , Jane Wilhelms, Collision detection and response for computer animationr3, Proceedings of the 15th annual conference on Computer graphics and interactive techniques, p.289-298, June 1988
• 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.
• 27: Moreau, J. J. 1966. Quadratic programming in mechanics: One-sided constraints. Journal SIAM Control 4, 1, 153--158.
• 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.
• 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.
• 30: Richard M. Murray , S. Shankar Sastry , Li Zexiang, A Mathematical Introduction to Robotic Manipulation, CRC Press, Inc., Boca Raton, FL, 1994
• 31: Mark Pauly , Dinesh K. Pai , Leonidas J. Guibas, Quasi-rigid objects in contact, Proceedings of the 2004 ACM SIGGRAPH/Eurographics symposium on Computer animation, August 27-29, 2004, Grenoble, France [doi>10.1145/1028523.1028539]
• 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.
• 33: Rockafellar, R. T. 1970. Convex Analysis. Princeton University Press.
• 34: Harald Schmidl , Victor J. Milenkovic, A Fast Impulsive Contact Suite for Rigid Body Simulation, IEEE Transactions on Visualization and Computer Graphics, v.10 n.2, p.189-197, March 2004 [doi>10.1109/TVCG.2004.1260770]
• 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.
• 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.
• 37: Jeff Trinkle , Jong Pang , Sandra Sudarsky , Grace Lo, On Dynamic Multi-Rigid-Body Contact Problems with Coulomb Friction, Texas A & M University, College Station, TX, 1995
• 38: Verlet, L. 1967. Computer experiments on classical fluids, thermodynamical properties of lennard-jones molecules. Physical Review 159, 98--103.
• 39: K. Yang , K. G. Murty, New iterative methods for linear inequalities, Journal of Optimization Theory and Applications, v.72 n.1, p.163-185, Jan., 1992 [doi>10.1007/BF00939954]

INDEX TERMS

Primary Classification:
  I. Computing Methodologies
  I.3 COMPUTER GRAPHICS
      I.3.5 Computational Geometry and Object Modeling
          Subjects: Physically based modeling

Additional Classification:
  I. Computing Methodologies
  I.6 SIMULATION AND MODELING
      I.6.8 Types of Simulation
          Subjects: Animation

Keywords:
contact, friction, non-smooth dynamics, rigid bodies