Sampling plausible solutions to multi-body constraint problems

ABSTRACT

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.

REFERENCES

• 1: Joel Auslander , Alex Fukunaga , Hadi Partovi , Jon Christensen , Lloyd Hsu , Peter Reiss , Andrew Shuman , Joe Marks , J. Thomas Ngo, Further experience with controller-based automatic motion synthesis for articulated figures, ACM Transactions on Graphics (TOG), v.14 n.4, p.311-336, Oct. 1995 [doi>10.1145/225294.225295]
• 2: 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
• 3: Ronen Barzel , John F. Hughes , Daniel N. Wood, Plausible motion simulation for computer graphics animation, Proceedings of the Eurographics workshop on Computer animation and simulation '96, p.183-197, December 1996, Poitiers, France
• 4: D. C. Brogan, Group behaviors for systems with significant dynamics, Proceedings of the International Conference on Intelligent Robots and Systems-Volume 3, p.3528, August 05-09, 1995
• 5: Lynne Shapiro Brotman , Arun N. Netravali, Motion interpolation by optimal control, Proceedings of the 15th annual conference on Computer graphics and interactive techniques, p.309-315, June 1988
• 6: Stephen Chenney, Asynchronous, adaptive, rigid body simulation, ACM SIGGRAPH 99 Conference abstracts and applications, p.233, August 08-13, 1999, Los Angeles, California, United States [doi>10.1145/311625.312121]
• 7: Stephen Chenney , Jeffrey Ichnowski , David Forsyth, Dynamics Modeling and Culling, IEEE Computer Graphics and Applications, v.19 n.2, p.79-87, March 1999 [doi>10.1109/38.749126]
• 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, Proceedings of the 19th annual conference on Computer graphics and interactive techniques, p.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, Proceedings of the 1997 symposium on Interactive 3D graphics, p.139-ff., April 27-30, 1997, Providence, Rhode Island, United States [doi>10.1145/253284.253321]
• 14: Radek Grzeszczuk , Demetri Terzopoulos, Automated learning of muscle-actuated locomotion through control abstraction, Proceedings of the 22nd annual conference on Computer graphics and interactive techniques, p.63-70, September 1995 [doi>10.1145/218380.218411]
• 15: Radek Grzeszczuk , Demetri Terzopoulos , Geoffrey Hinton, NeuroAnimator: fast neural network emulation and control of physics-based models, Proceedings of the 25th annual conference on Computer graphics and interactive techniques, p.9-20, July 1998 [doi>10.1145/280814.280816]
• 16: Jessica K. Hodgins , Nancy S. Pollard, Adapting simulated behaviors for new characters, Proceedings of the 24th annual conference on Computer graphics and interactive techniques, p.153-162, August 1997 [doi>10.1145/258734.258822]
• 17: Jessica K. Hodgins , James F. O'Brien , Jack Tumblin, Perception of Human Motion With Different Geometric Models, IEEE Transactions on Visualization and Computer Graphics, v.4 n.4, p.307-316, October 1998 [doi>10.1109/2945.765325]
• 18: M. Jerrum , Alistair Sinclair, Approximating the permanent, SIAM Journal on Computing, v.18 n.6, p.1149-1178, Dec. 1989 [doi>10.1137/0218077]
• 19: Mark Jerrum , Alistair Sinclair, The Markov chain Monte Carlo method: an approach to approximate counting and integration, Approximation algorithms for NP-hard problems, PWS Publishing Co., Boston, MA, 1996
• 20: Zicheng Liu , Steven J. Gortler , Michael F. Cohen, Hierarchical spacetime control, Proceedings of the 21st annual conference on Computer graphics and interactive techniques, p.35-42, July 1994 [doi>10.1145/192161.192169]
• 21: J. Marks , B. Andalman , P. A. Beardsley , W. Freeman , S. Gibson , J. Hodgins , T. Kang , B. Mirtich , H. Pfister , W. Ruml , K. Ryall , J. Seims , S. Shieber, Design galleries: a general approach to setting parameters for computer graphics and animation, Proceedings of the 24th annual conference on Computer graphics and interactive techniques, p.389-400, August 1997 [doi>10.1145/258734.258887]
• 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 , Joe Marks, Spacetime constraints revisited, Proceedings of the 20th annual conference on Computer graphics and interactive techniques, p.343-350, September 1993 [doi>10.1145/166117.166160]
• 24: Jovan Popović , Steven M. Seitz , Michael Erdmann , Zoran Popović , Andrew Witkin, Interactive manipulation of rigid body simulations, Proceedings of the 27th annual conference on Computer graphics and interactive techniques, p.209-217, July 2000 [doi>10.1145/344779.344880]
• 25: Zoran Popović , Andrew Witkin, Physically based motion transformation, Proceedings of the 26th annual conference on Computer graphics and interactive techniques, p.11-20, July 1999 [doi>10.1145/311535.311536]
• 26: Karl Sims, Evolving virtual creatures, Proceedings of the 21st annual conference on Computer graphics and interactive techniques, p.15-22, July 1994 [doi>10.1145/192161.192167]
• 27: Alistair Sinclair, 1999. Personal communication.
• 28: R. Szeliski , D. Terzopoulos, From splines to fractals, ACM SIGGRAPH Computer Graphics, v.23 n.3, p.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 , Leonidas J. Guibas, Metropolis light transport, Proceedings of the 24th annual conference on Computer graphics and interactive techniques, p.65-76, August 1997 [doi>10.1145/258734.258775]
• 31: Baba C. Vemuri , Chhandomay Mandal , Shang-Hong Lai, A Fast Gibbs Sampler for Synthesizing Constrained Fractals, IEEE Transactions on Visualization and Computer Graphics, v.3 n.4, p.337-351, October 1997 [doi>10.1109/2945.646237]
• 32: Andrew Witkin , Michael Kass, Spacetime constraints, Proceedings of the 15th annual conference on Computer graphics and interactive techniques, p.159-168, June 1988

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.3 PROBABILITY AND STATISTICS
      Subjects: Probabilistic algorithms (including Monte Carlo)

  I. Computing Methodologies
  I.2 ARTIFICIAL INTELLIGENCE
        I.2.10 Vision and Scene Understanding
            Subjects: Modeling and recovery of physical attributes
  I.3 COMPUTER GRAPHICS
      I.3.5 Computational Geometry and Object Modeling
          Subjects: Physically based modeling
  I.6 SIMULATION AND MODELING
      I.6.5 Model Development
          Subjects: Modeling methodologies
      I.6.8 Types of Simulation
          Subjects: Monte Carlo

General Terms:
Design, Measurement, Performance, Theory

Keywords:
Markov chain Monte Carlo, motion synthesis, plausible motion, spacetime constraints