Sampling plausible solutions to multi-body constraint problems

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 users 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. CR Descriptors: I.3.7 Computer Graphics: Three-Dimensional Graphics and Realism - Animation; I.3.5 Computer Graphics: Computational Geometry and Object Modeling - Physically based modeling; I.6.5 Simulation and Modeling: Model Development - Modeling methodologies G.3 Probability and Statistics: Probabilistic algorithms; Keywords: plausible motion, Markov chain Monte Carlo, motion synthesis, spacetime constraints 1