“Sampling plausible solutions to multi-body constraint problems” by Chenney and Forsyth

Traditional collision intensive multi-body simulations are difficult to control due to extreme sensitivity to initial conditions or model parameters. Furthermore, there may be multiple ways to achieve any one goal, and it may be difficult to codify a user’s preferences before they have seen the available solutions. In this paper we extend simulation models to include plausible sources of uncertainty, and then use a Markov chain Monte Carlo algorithm to sample multiple animations that satisfy constraints. A user can choose the animation they prefer, or applications can take direct advantage of the multiple solutions. Our technique is applicable when a probability can be attached to each animation, with “good” animations having high probability, and for such cases we provide a definition of physical plausibility for animations. We demonstrate our approach with examples of multi-body rigid-body simulations that satisfy constraints of various kinds, for each case presenting animations that are true to a physical model, are significantly different from each other, and yet still satisfy the constraints.

1. Joel Auslander, Alex Fukunaga, Hadi Partovi, Jon Christensen, Lloyd Hsu, Peter Reiss, Andrew Shuman, Joe Marks, and J. Thomas Ngo. Further Experience with Controller- Based Automatic Motion Synthesis for Articulated Figures. ACM Transactions on Graphics, 14(4):311-336, October 1995.
2. Ronan Barzel and Alan H. Barr. A Modeling System Based on Dynamic Constraints. In Computer Graphics (SIGGRAPH 88 Conf. Proc.), volume 22, pages 179-188, August 1988.
3. Ronan Barzel, John F. Hughes, and Daniel N. Wood. Plausible Motion Simulation for Computer Graphics Animation. In Computer Animation and Simulation ’96, pages 184-197, 1996. Proceedings of the Eurographics Workshop in Poitiers, France, August 31-September 1, 1996.
4. David Brogan and Jessica Hodgins. Group Behaviors for Systems with Significant Dynamics. In Proceedings of the 1995 IEEE/RSJ International Conference on Intelligent Robots and Systems, volume 3, pages 528-534, 1995.
5. Lynne Shapiro Brotman and Arun N. Netravali. Motion Interpolation by Optimal Control. In Computer Graphics (SIG- GRAPH 88 Conf. Proc.), volume 22, pages 309-315, August 1988.
6. Stephen Chenney. Asynchronous, Adaptive, Rigid-Body Simulation. SIGGRAPH 99 Technical Sketch. In Conference Abstracts and Applications, page 233, August 1999.
7. Stephen Chenney, Jeffrey Ichnowski, and David Forsyth. Dynamics Modeling and Culling. IEEE Computer Graphics and Applications, 19(2):79-87, March/April 1999.
8. Jon Christensen, Joe Marks, and J. Thomas Ngo. Automatic Motion Synthesis for 3D Mass-Spring Models. The Visual Computer, 13(3):20-28, January 1997.
9. Michael F. Cohen. Interactive Spacetime Control for Animation. In Computer Graphics (SIGGRAPH 92 Conf. Proc.), volume 26, pages 293-302, July 1992.
10. Afonso G. Ferreira and Janez ~;erovnik. Bounding the Probability of Success of Stochastic Methods for Global Optimization. Computers and Mathematics with Applications, 25(10):1-8, 1993.
11. George S. Fishman. Monte Carlo : concepts, algorithms, and applications. Springer-Verlag, 1996.
12. Walter R Gilks, Sylvia Richardson, and David J Spiegelhalter. Markov Chain Monte Carlo in Practice. Chapman & Hall, 1996.
13. Michael Gleicher. Motion Editing with Spacetime Constraints. In Proceedings 1997 Symposium on Interactive 3D Graphics, pages 139-148, April 1997. Providence, RI, April 27-30.
14. Radek Grzeszczuk and Demetri Terzopoulos. Automated Learning of Muscle-Actuated Locomotion Through Control Abstraction. In SIGGRAPH 95 Conference Proceedings, pages 63-70. ACM SIGGRAPH, August 1995.
15. Radek Grzeszczuk, Demetri Terzopoulos, and Geoffrey Hinton. NeuroAnimator: Fast Neural Network Emulation and Control of Physics-Based Models. In SIGGRAPH 98 Conference Proceedings, pages 9-20. ACM SIGGRAPH, July 1998.
16. Jessica Hodgins and Nancy Pollard. Adapting Simulated Behaviors for New Creatures. In SIGGRAPH 97 Conference Proceedings, pages 153-162. ACM SIGGRAPH, August 1997.
17. Jessica K. Hodgins, James F. O’Brien, and Jack Tumblin. Perception of Human Motion With Different Geometric Models. IEEE Transactions on Visualization and Computer Graphics, 4(4):307-316, 1998.
18. Mark Jerrum and Alistair Sinclair. Approximating the Permanent. SIAM Journal of Computing, 18:1149-1178, 1989.
19. Mark Jerrum and Alistair Sinclair. The Markov Chain Monte Carlo Method: an approach to approximate counting and integration. In D.S.Hochbaum, editor, Approximation Algorithms for NP-hard Problems. PWS Publishing, Boston, 1996.
20. Zicheng Liu, Steven J. Gortler, and Michael F. Cohen. Hierarchical Spacetime Control. In SIGGRAPH 94 Conference Proceedings, pages 35-42. ACM SIGGRAPH, July 1994.
21. J. Marks, B. Andalman, EA. Beardsley, W. Freeman, S. Gibson, J. Hodgins, T. Kang, B. Mirtich, H. Pfister, W. Ruml, K. Ryall, J. Seims, and S. Shieber. Design Galleries: A General Approach to Setting Parameters for Computer Graphics and Animation. In SIGGRAPH 97 Conference Proceedings, pages 389-400. ACM SIGGRAPH, August 1997.
22. Brian Mirtich, Yan Zhuang, Ken Goldberg, John Craig, Rob Zanutta, Brian Carlisle, and John Canny. Estimating Pose Statistics for Robotic Part Feeders. In Proceedings 1996 IEEE International Conference on Robotics and Automation, volume 2, pages 1140-1146, 1996.
23. J. Thomas Ngo and Joe Marks. Spacetime Constraints Revisited. In SIGGRAPH 93 Conference Proceedings, pages 343- 350. ACM SIGGRAPH, August 1993.
24. Jovan Popovi6, Steven Seitz, Michael Erdmann, Zoran Popovi6, and Andrew Witkin. Interactive Manipulation of Rigid Body Simulations. In SIGGRAPH 2000 Conference Proceedings. ACM SIGGRAPH, July 2000.
25. Zoran Popovi6 and Andrew Witkin. Physically Based Motion Transformation. In SIGGRAPH 99 Conference Proceedings, pages 11-20. ACM SIGGRAPH, August 1999.
26. Karl Sims. Evolving Virtual Creatures. In SIGGRAPH 94 Conference Proceedings, pages 15-22. ACM SIGGRAPH, July 1994.
27. Alistair Sinclair, 1999. Personal communication.
28. Richard Szeliski and Demetri Terzopoulos. From Splines to Fractals. In Computer Graphics (SIGGRAPH 89 Conf. Proc.), volume 23, pages 51-60, July 1989.
29. Diane Tang, J. Thomas Ngo, and Joe Marks. N-Body Spacetime Constraints. The Journal of Visualization and Computer Animation, 6:143-154, 1995.
30. Eric Veach and Leonidas J. Guibas. Metropolis Light Transport. In SIGGRAPH 97 Conference Proceedings, pages 65- 76. ACM SIGGRAPH, August 1997.
31. Baba C Vemuri, Chhandomay Mandal, and Shang-Hong Lai. A Fast Gibbs Sampler for Synthesizing Constrained Fractals. IEEE Transactions on Visualization and Computer Graphics, 3(4):337-351, 1997.
32. Andrew Witkin and Michael Kass. Spacetime Constraints. In Computer Graphics (SIGGRAPH 88 Conf. Proc.), volume 22, pages 159-168, August 1988.