“Position-based physics: simulating the motion of many highly interacting spheres and polyhedra” by Milenkovic

This paper proposes a simplified position-based physics that allows us to rapidly generate “piles” or “clumps” of many objects: local energy minima under a variety of potential energy functions. We can also generate plausible motions for many highly interacting objects from arbitrary starting positions to a local energy minimum. We present an efficient and numerically stable algorithm for carrying out position-based physics on spheres and non-rotating polyhedra through the use of linear programming. This algorithm is a generalization of an algorithm for finding tight packings of (non-rotating) polygons in two dimensions. This work introduces linear programming as a useful tool for graphics animation. As its name implies, position-based physics does not contain a notion of velocity, and thus it is not suitable for simulating the motion of free-flying, unencumbered objects. However, it generates realistic motions of “crowded” sets of objects in confined spaces, and it does so at least two orders of magnitude faster than other techniques for simulating the physical motions of objects. Even for unconfined objects, the new algorithm can rapidly generate realistic “piles” and “clumps.”

1. D. Baraff. Analytical methods for dynamic simulation of nonpenetrating rigid bodies. Computer Graphics (Proceedings of SIGGRAPH), 23(3):223-232, 1989.
2. David Baraff. Curved surfaces and coherence for nonpenetrating rigid body simulation. In Forest Baskett, editor, Computer Graphics (SIGGRAPH ’90 Proceedings), volume 24, pages 19-28, August 1990.
3. David Baraff. Coping with friction for non-penetrating rigid body simulation. In Thomas W. Sederberg, editor, Computer Graphics (SIGGRAPH ’91 Proceedings), volume 25, pages 31-40, July 1991.
4. David Baraff. Issues in computing contact forces for nonpenetrating rigid bodies. Algorithmica, 10(2-4):292-352, 1993.
5. David Baraff. Fast contact force computation for nonpenetrating rigid bodies. In Andrew Glassner, editor, Proceedings of SIGGRAPH ’94 (Orlando, Florida, July 24-29, 1994), Computer Graphics Proceedings, Annual Conference Series, pages 23-34. ACM SIGGRAPH, ACM Press, July 1994.
6. David Baraff. Interactive simulation of solid rigid bodies. IEEE Computer Graphics and Applications, 15(3):63-75, May 1995.
7. David Baraff and Andrew Witkin. Dynamic simulation of non-penetrating flexible bodies. In Edwin E. Catmull, editor, Computer Graphics (SIGRAPH ’92 Proceedings), volume 26, pages 303-308, July 1992.
8. R. Barzel and A. H. Barr. A modeling system based on dynamics constraints. Computer Graphics (Proceedings of SIG- GRAPH), 22(4):179-187, 1988.
9. Jim X. Chen and Niels Da Vitoria Lobo. Toward interactiverate simulation of fluids with moving obstacles using navierstokes equations. Graphical Models and Image Processing, 57(2):107-116, March 1995.
10. N. Chiba, S. Sanakanishi, K. Yokoyama, I. Ootawara, K. Muraoka, and N. Saito. Visual simulation of water currents using a particle-based behavioural model. Journal of Visualization and Computer Animation, 6(3):155-172, July 1995.
11. D. Dobkin, J. Hershberger, D. Kirkpatrik, and S. Suri. Implicitly searching convolutions and computing depth of collision. In Proceedings of the Second SIGAL, pages 165-180, 1990.
12. Jeff Goldsmith and Alan H. Barr. Applying constrained optimization to computer graphics. SMPTE Journal – Society of Motion Picture and Television Engineers, 102(10):910-912, October 1993.
13. L. Guibas, L. Ramshaw, and J. Stolfi. A Kinetic Framework for Computational Geometry. In Proceedings of the 24th Annual IEEE Symposium on Foundations of Computer Science, pages 100-111. IEEE, 1983.
14. James K. Hahn. Realistic animation of rigid bodies. In John Dill, editor, Computer Graphics (SIGGRAPH ’88 Proceedings), volume 22, pages 299-308, August 1988.
15. Mikako Harada, Andrew Witkin, and David Baraff. Interactive physically-based manipulation of discrete/continuous models. In Robert Cook, editor, Proceedings of SIGGRAPH ’95, Computer Graphics Proceedings, Annual Conference Series, pages 199-208. ACM SIGGRAPH, ACM Press, August 1995.
16. Vincent Hayward, Stephane Aubry, Andre Foisy, and Yasmine Ghallab. Efficient collision prediction among many moving objects. The International Journal of Robotics Research, 14(2):129-143, April 1995.
17. Michael Kass and Gavin Miller. Rapid, stable fluid dynamics for computer graphics. In Forest Baskett, editor, Computer Graphics (SIGGRAPH ’90 Proceedings), volume 24, pages 49-57, August 1990.
18. A. Kaul, M.A. O’Connor, and V. Srinivasan. Computing Minkowski Sums of Regular Polygons. In Thomas Shermer, editor, Proceedings of the Third Canadian Conference on Computational Geometry, pages 74-77, Vancouver, British Columbia, 1991. Simon Frasier University.
19. Z. Li. Compaction Algorithms for Non-Convex Polygons and Their Applications. PhD thesis, Harvard University, Division of Applied Sciences, 1994.
20. A. Luciani, A. Habibi, and E. Manzotti. A multi scale physical model of granular materials. In Proceedings of Graphics Interface ’95, pages 136-145, May 1995.
21. H. Mallinder. The modelling of large waterfalls using string texture. Journal of Visualization and Computer Animation, 6(1):3-10, January 1995.
22. V. Milenkovic, K. Daniels, and Z. Li. Placement and Compaction of Nonconvex Polygons for Clothing Manufacture. In Proceedings of the Fourth Canadian Conference on Computational GeomeoT, pages 236-243, St. Johns, Newfoundland, August 1992. Department of Computer Science, Memorial University of Newfoundland.
23. V.J. Milenkovic and Z. Li. A Compaction Algorithm for Nonconvex Polygons and Its Application. Eu~vpean Journal of Operations Research, 84:539-560, 1995.
24. H. Minkowski. Volumen und Oberfl~iche. Mathematische Annalen, 57:447-495, 1903.
25. M. Moore and J. Wilhelms. Collision detection and response for computer animation. Computer Graphics (Proceedings of SIGGRAPH), 22(4):289-298, 1988.
26. J. C. Platt and A. H. Barr. Constraint methods for flexible models. Computer Graphics (Proceedings of SIGGRAPH), 22(4):279-287, 1988.
27. J. Serra. Image Analysis and Mathematical Morphology, volume 1. Academic Press, New York, 1982.
28. J. Serra, editor. Image Analysis and Mathematical Morphology, volume 2: Theoretical Advances. Academic Press, New York, 1988.
29. Mikio Shinya and Marie-Claire Forgue. Layout out objects with geometric and pysical constraints. Visual Computer, 11:188-201, August 1995.
30. John Snyder. An interactive tool for placing curved surfaces with interpenetration. In Robert Cook, editor, Proceedings of SIGGRAPH ’95, Computer Graphics Proceedings, Annual Conference Series, pages 209-218. ACM SIGGRAPH, ACM Press, August 1995.
31. Richard Szeliski and David Tonnesen. Surface modeling with oriented particle systems. In Edwin E. Catmull, editor, Computer Graphics (SIGGRAPH ’92 Proceedings), volume 26, pages 185-194, July 1992.
32. Demitri Terzopoulos, John Platt, and Kurt Fleischer. Heating and melting deformable models (from goop to glop). In Proceedings of Graphics Intelface ’89, pages 219-226, June 1989.
33. Andrew P. Witkin and Paul S. Heckbert. Using particles to sample and control implicit surfaces. In Andrew Glassner, editor, Proceedings of SIGGRAPH ’94 (Orlando, Florida, July 24-29, 1994), Computer Graphics Proceedings, Annual Conference Series, pages 269-278. ACM SIGGRAPH, ACM Press, July 1994.