Optimization-based animation

ABSTRACT

Current techniques for rigid body simulation run slowly on scenes with many bodies in close proximity. Each time two bodies collide or make or break a static contact, the simulator must interrupt the numerical integration of velocities and accelerations. Even for simple scenes, the number of discontinuities per frame time can rise to the millions. An efficient optimization-based animation (OBA) algorithm is presented which can simulate scenes with many convex three-dimensional bodies settling into stacks and other “crowded” arrangements. This algorithm simulates Newtonian (second order) physics and Coulomb friction, and it uses quadratic programming (QP) to calculate new positions, momenta and accelerations strictly at frame times. Contact points are synchronized at the end of each frame. The extremely small integration steps inherent to traditional simulation techniques are avoided. Non-convex bodies are simulated as unions of convex bodies. Links and joints are simulated successfully with bi-directional constraints. A hybrid of OBA and retroactive detection (RD) has been implemented as well. A review of existing work finds no other packages that can simulate similarly complex scenes in a practical amount of time.

REFERENCES

• 1: William W. Armstrong and Mark W. Green. The dynamics of articulated rigid bodies for purposes of animation. The Visual Computer, 1:231-240, 1985.
• 2: 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
• 3: 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]
• 4: David Baraff , Andrew Witkin, Dynamic simulation of non-penetrating flexible bodies, Proceedings of the 19th annual conference on Computer graphics and interactive techniques, p.303-308, July 1992
• 5: David Baraff , Andrew Witkin, Large steps in cloth simulation, Proceedings of the 25th annual conference on Computer graphics and interactive techniques, p.43-54, July 1998 [doi>10.1145/280814.280821]
• 6: Ronen Barzel , Alan H. Barr, A modeling system based on dynamic constraints, Proceedings of the 15th annual conference on Computer graphics and interactive techniques, p.179-188, June 1988
• 7: Raymond M. Brach. Rigid body collisions. Journal of Applied Mechanics, 56:133-138, March 1989.
• 8: Stephen Chenney , D. A. Forsyth, Sampling plausible solutions to multi-body constraint problems, Proceedings of the 27th annual conference on Computer graphics and interactive techniques, p.219-228, July 2000 [doi>10.1145/344779.344882]
• 9: Jonathan D. Cohen , Ming C. Lin , Dinesh Manocha , Madhav Ponamgi, I-COLLIDE: an interactive and exact collision detection system for large-scale environments, Proceedings of the 1995 symposium on Interactive 3D graphics, p.189-ff., April 09-12, 1995, Monterey, California, United States [doi>10.1145/199404.199437]
• 10: Stephen Ehmann , Ming Lin, SWIFT: Accelerated Proximity Queries Using Multi-Level Voronoi Marching, University of North Carolina at Chapel Hill, Chapel Hill, NC, 2000
• 11: Herbert Goldstein. Klassische Mechanik. AULA Verlag Wiesbaden, 11. Auflage, 1991.
• 12: J.B. Keller. Impact with friction. Journal of Applied Mechanics, 53:1-4, March 1986.
• 13: Iraklis Kourtidis. Distributed rotational polygon compaction. Master's thesis, University of Miami, May 2000.
• 14: Z. Li and Victor Milenkovic. Compaction and separation algorithms for non-convex polygons and their applications. European Journal of Operations Research, 84:539-561, 1995.
• 15: Ming Lin and John Canny. A fast algorithm for incremental distance calculation. International Conference on Robotics and Automation, pages 1008-1014, 1991.
• 16: Per Lotstedt. Coulomb friction in two-dimensional rigid body systems. Zeitschrift fur angewandte Mathematik und Mechanik, 61:605-615, 1981.
• 17: Victor J. Milenkovic, Rotational polygon overlap minimization and compaction, Computational Geometry: Theory and Applications, v.10 n.4, p.305-318, July 1, 1998 [doi>10.1016/S0925-7721(98)00012-1]
• 18: Victor J. Milenkovic, Position-based physics: simulating the motion of many highly interacting spheres and polyhedra, Proceedings of the 23rd annual conference on Computer graphics and interactive techniques, p.129-136, August 1996 [doi>10.1145/237170.237222]
• 19: 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]
• 20: Brian Mirtich, V-Clip: fast and robust polyhedral collision detection, ACM Transactions on Graphics (TOG), v.17 n.3, p.177-208, July 1998 [doi>10.1145/285857.285860]
• 21: Brian Mirtich, Timewarp rigid body simulation, Proceedings of the 27th annual conference on Computer graphics and interactive techniques, p.193-200, July 2000 [doi>10.1145/344779.344866]
• 22: 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
• 23: James F. O'Brien , Jessica K. Hodgins, Graphical modeling and animation of brittle fracture, Proceedings of the 26th annual conference on Computer graphics and interactive techniques, p.137-146, July 1999 [doi>10.1145/311535.311550]
• 24: Jörg Sauer , Elmar Schömer, A constraint-based approach to rigid body dynamics for virtual reality applications, Proceedings of the ACM symposium on Virtual reality software and technology, p.153-162, November 02-05, 1998, Taipei, Taiwan [doi>10.1145/293701.293721]
• 25: David Stewart and Jeff C. Trinkle. An implicit time-stepping scheme for rigid body dynamics with inelastic collisions and coulomb friction. In Zeitschrift fur Angewandte Mathematik und Mechanik, 77(4):267-279, 1997.

INDEX TERMS

Primary Classification:
  I. Computing Methodologies
  I.3 COMPUTER GRAPHICS
      I.3.7 Three-Dimensional Graphics and Realism
          Subjects: Animation

Additional Classification:
  G. Mathematics of Computing
  G.1 NUMERICAL ANALYSIS
      G.1.6 Optimization
          Subjects: Linear programming; Quadratic programming methods

  I. Computing Methodologies
  I.3 COMPUTER GRAPHICS
      I.3.5 Computational Geometry and Object Modeling
          Subjects: Physically based modeling
  I.6 SIMULATION AND MODELING
      I.6.8 Types of Simulation
          Subjects: Animation

General Terms:
Experimentation, Performance

Keywords:
animation, animation w/ constraints, physically based animation, physically based modeling, scientific visualization, solid modeling