“Mesh ensemble motion graphs” by James, Twigg, Cove and Wang

We describe a technique for using space-time cuts to smoothly transition between stochastic mesh animation clips while subject to physical noninterpenetration constraints. These transitions are used to construct Mesh Ensemble Motion Graphs for interactive data-driven animation of high-dimensional mesh animation datasets, such as those arising from expensive physical simulations of deformable objects blowing in the wind (see Figure 1). We formulate the transition computation as an integer programming problem, and use a novel randomized algorithm to compute transitions subject to noninterpenetration constraints.

1. Bridson, R., Fedkiw, R. P., and Anderson, J. 2002. Robust Treatment of Collisions, Contact, and Friction for Cloth Animation. ACM Transactions on Graphics 21, 3 (July), 594–603.
2. James, D. L., and Twigg, C. D. 2005. Skinning Mesh Animations. ACM Transactions on Graphics 24, 3 (Aug.), 399–407.
3. Kovar, L., Gleicher, M., and Pighin, F. 2002. Motion Graphs. ACM Transactions on Graphics 21, 3 (July), 473–482.
4. Kwatra, V., Schödl, A., Essa, I., Turk, G., and Bobick, A. 2003. GraphCut Textures: Image and Video Synthesis Using Graph Cuts. ACM Transactions on Graphics 22, 3 (July), 277–286.
5. Lee, J., Chai, J., Reitsma, P. S. A., Hodgins, J. K., and Pollard, N. S. 2002. Interactive Control of Avatars Animated With Human Motion Data. ACM Transactions on Graphics 21, 3 (July), 491–500.
6. Selman, B., Kautz, H., and Cohen, B. 1996. Local search strategies for satisfiability testing. In DIMACS Series in Discrete Mathematics and Theoretical Computer Science, vol. 26. American Mathematical Society, 521–532.