skip to main content
article

Mesh Ensemble Motion Graphs: Data-driven mesh animation with constraints

Published: 01 October 2007 Publication History

Abstract

We explore the use of space-time cuts to smoothly transition between stochastic mesh animation clips involving numerous deformable mesh groups while subject to physical 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. We formulate the transition computation as an integer programming problem, and introduce a novel randomized algorithm to compute transitions subject to geometric nonpenetration constraints. We present examples for several physically based motion datasets, with real-time display and optional interactive control over wind intensity via transitions between wind levels. We discuss challenges and opportunities for future work and practical application.

References

[1]
Agarwala, A., Zheng, K. C., Pal, C., Agrawala, M., Cohen, M., Curless, B., Salesin, D., and Szeliski, R. 2005. Panoramic video textures. ACM Trans. Graph. 24, 3, 821--827.
[2]
Apt, K. 2003. Principles of Constraint Programming. Cambridge University Press.
[3]
Arikan, O. and Forsyth, D. A. 2002. Synthesizing constrained motions from examples. ACM Trans. Graph. 21, 3, 483--490.
[4]
Baraff, D. 1994. Fast contact force computation for nonpenetrating rigid bodies. In Proceedings of SIGGRAPH 94. (Computer Graphics Proceedings, Annual Conference Series). 23--34.
[5]
Barbič, J. and James, D. 2005. Real-Time subspace integration for St. Venant-Kirchhoff deformable models. ACM Trans. Graph. 24, 3, 982--990.
[6]
Bhat, K. S., Seitz, S. M., Hodgins, J. K., and Khosla, P. K. 2004. Flow-based video synthesis and editing. ACM Trans. Graph 23, 3, 360--363.
[7]
Bridson, R., Fedkiw, R. P., and Anderson, J. 2002. Robust treatment of collisions, contact, and friction for cloth animation. ACM Trans. Graph. 21, 3, 594--603.
[8]
Choset, H., Lynch, K. M., Hutchinson, S., Kantor, G., Burgard, W., Kavraki, L. E., and Thrun, S. 2005. Principles of Robot Motion: Theory, Algorithms, and Implementations. MIT Press, Cambridge, MA.
[9]
Cohen, M. F., Shade, J., Hiller, S., and Deussen, O. 2003. Wang tiles for image and texture generation. ACM Trans. Graph. 22, 3, 287--294.
[10]
Decaudin, P. and Neyret, F. 2004. Rendering forest scenes in real-time. In Eurographics Symposium on Rendering (Rendering Techniques'04). 93--102.
[11]
Deussen, O., Hanrahan, P. M., Lintermann, B., Mech, R., Pharr, M., and Prusinkiewicz, P. 1998. Realistic Modeling and Rendering of Plant Ecosystems. In Proceedings of SIGGRAPH. 275--286.
[12]
Garey, M. R. and Johnson, D. S. 1979. Computers and Intractability: A Guide to the Theory of NP-Completeness. W. H. Freeman, San Francisco, CA.
[13]
Gomes, C. and Selman, B. 2003. Hill climbing search. In Encyclopedia of Cognitive Science, L. Nadel, Ed. Nature Publishing Group, London, UK.
[14]
Grinspun, E., Hirani, A. N., Desbrun, M., and Schröder, P. 2003. Discrete shells. In ACM SIGGRAPH/Eurographics Symposium on Computer Animation. D. Breen and M. Lin, Eds. 62--67.
[15]
Hart, J. C. 1992. The object instancing paradigm for linear fractal modeling. In Proceedings of the Conference Graphics Interface. 224--231.
[16]
James, D. L. and Fatahalian, K. 2003. Precomputing interactive dynamic deformable scenes. ACM Trans. Graph. 22, 3, 879--887.
[17]
James, D. L. and Pai, D. K. 2002. DyRT: Dynamic response textures for real-time deformation simulation with graphics hardware. ACM Trans. Graph. 21, 3, 582--585.
[18]
James, D. L. and Pai, D. K. 2004. BD-Tree: output-sensitive collision detection for reduced deformable models. ACM Trans. Graph. 23, 3, 393--398.
[19]
James, D. L. and Twigg, C. D. 2005. Skinning mesh animations. ACM Trans. Graph. 24, 3, 399--407.
[20]
Kaufman, D. M., Edmunds, T., and Pai, D. K. 2005. Fast frictional dynamics for rigid bodies. ACM Trans. Graph. 24, 3, 946--956.
[21]
Kavraki, L. E., Svestka, P., Latombe, J.-C., and Overmars, M. H. 1996. Probabilistic roadmaps for fast path planning in high-dimensional configuration spaces. IEEE Trans. Robotics Autom. 12, 4, 566--580.
[22]
Kovar, L., Gleicher, M., and Pighin, F. 2002. Motion graphs. ACM Trans. Graph. 21, 3, 473--482.
[23]
Kwatra, V., Schödl, A., Essa, I., Turk, G., and Bobick, A. 2003. GraphCut textures: image and video synthesis using graph cuts. ACM Trans. Graph. 22, 3, 277--286.
[24]
Lai, Y.-C., Chenney, S., and Fan, S. 2005. Group motion graphs. In ACM SIGGRAPH /Eurographics Symposium on Computer Animation. 281--290.
[25]
Latombe, J.-C. 1991. Robot Motion Planning. Kluwer Academic Publishers, Norwell, MA.
[26]
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 Trans. on Graph. 21, 3, 491--500.
[27]
Moll, M. and Kavraki, L. E. 2006. Path planning for deformable linear objects. IEEE Trans. Robotics, To appear.
[28]
Müller, M., Heidelberger, B., Hennix, M., and Ratcliff, J. 2006. Position based dynamics. In Proceedings of Virtual Reality Interactions and Physical Simulations (VRIPhys). 71--80.
[29]
Nemhauser, G. L. and Wolsey, L. A. 1999. Integer and Combinatorial Optimization. Series in Discrete Mathematics and Optimization. John Wiley and Sons, Inc., New York.
[30]
Nocedal, J. and Wright, S. J. 1999. Numerical Optimization. Series in Operations Research. Springer-Verlag, Berlin, Germany.
[31]
O'Sullivan, C., Dingliana, J., Giang, T., and Kaiser, M. K. 2003. Evaluating the visual fidelity of physically based animations. ACM Trans. Graph. 22, 3, 527--536.
[32]
Perbet, F. and Cani, M.-P. 2001. Animating prairies in real-time. In ACM Symposium on Interactive 3D Graphics. 103--110.
[33]
Prusinkiewicz, P. and Lindenmayer, A. 1990. The Algorithmic Beauty of Plants. Springer-Verlag, Berlin, Germany.
[34]
Safonova, A., Hodgins, J. K., and Pollard, N. S. 2004. Synthesizing physically realistic human motion in low-dimensional, behavior-specific spaces. ACM Trans. Graph. 23, 3, 514--521.
[35]
Schödl, A. and Essa, I. A. 2002. Controlled animation of video sprites. In ACM SIGGRAPH Symposium on Computer Animation. 121--128.
[36]
Schödl, A., Szeliski, R., Salesin, D. H., and Essa, I. 2000. Video textures. In Proceedings of ACM SIGGRAPH. (Computer Graphics Proceedings, Annual Conference Series). 489--498.
[37]
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.
[38]
Sung, M., Kovar, L., and Gleicher, M. 2005. Fast and accurate goal-directed motion synthesis for crowds. In ACM SIGGRAPH /Eurographics Symposium on Computer Animation. 291--300.
[39]
Sutherland, I. E. 1963. Sketchpad: A man-machine graphical communication system. Ph.D. thesis, Massachusetts Institute of Technology, Cambridge, MA.
[40]
Zordan, V. B., Majkowska, A., Chiu, B., and Fast, M. 2005. Dynamic response for motion capture animation. ACM Trans. Graph. 24, 3, 697--701.

Cited By

View all

Recommendations

Comments

Information & Contributors

Information

Published In

cover image ACM Transactions on Graphics
ACM Transactions on Graphics  Volume 26, Issue 4
October 2007
139 pages
ISSN:0730-0301
EISSN:1557-7368
DOI:10.1145/1289603
Issue’s Table of Contents

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 01 October 2007
Published in TOG Volume 26, Issue 4

Permissions

Request permissions for this article.

Check for updates

Author Tags

  1. Collision detection
  2. constraint satisfaction
  3. integer programming
  4. motion graphs
  5. nonpenetration

Qualifiers

  • Article

Contributors

Other Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

  • Downloads (Last 12 months)14
  • Downloads (Last 6 weeks)1
Reflects downloads up to 20 Feb 2025

Other Metrics

Citations

Cited By

View all
  • (2023)ViCMA: Visual Control of Multibody AnimationsSIGGRAPH Asia 2023 Conference Papers10.1145/3610548.3618223(1-11)Online publication date: 10-Dec-2023
  • (2017)Botanical materials based on biomechanicsACM Transactions on Graphics10.1145/3072959.307365536:4(1-13)Online publication date: 20-Jul-2017
  • (2017)Example-Based Subspace Stress Analysis for Interactive Shape DesignIEEE Transactions on Visualization and Computer Graphics10.1109/TVCG.2016.261887523:10(2314-2327)Online publication date: 1-Oct-2017
  • (2017)Interactive authoring of bending and twisting motions of short plants using hand gesturesComputer Animation and Virtual Worlds10.1002/cav.174728:6Online publication date: 9-Feb-2017
  • (2015)Hybrid Skeletal-Surface Motion Graphs for Character Animation from 4D Performance CaptureACM Transactions on Graphics10.1145/269964334:2(1-14)Online publication date: 2-Mar-2015
  • (2015)Video Based Animation Synthesis with the Essential GraphProceedings of the 2015 International Conference on 3D Vision10.1109/3DV.2015.60(478-486)Online publication date: 19-Oct-2015
  • (2013)One-to-manyProceedings of the 12th ACM SIGGRAPH/Eurographics Symposium on Computer Animation10.1145/2485895.2485904(145-153)Online publication date: 19-Jul-2013
  • (2013)Interactive authoring of simulation-ready plantsACM Transactions on Graphics10.1145/2461912.246196132:4(1-12)Online publication date: 21-Jul-2013
  • (2013)Dynamic element texturesACM Transactions on Graphics10.1145/2461912.246192132:4(1-10)Online publication date: 21-Jul-2013
  • (2013)Animation Research: Modern TechniquesModern Machine Learning Techniques and Their Applications in Cartoon Animation Research10.1002/9781118559963.ch4(131-194)Online publication date: 2-Apr-2013
  • Show More Cited By

View Options

Login options

Full Access

View options

PDF

View or Download as a PDF file.

PDF

eReader

View online with eReader.

eReader

Figures

Tables

Media

Share

Share

Share this Publication link

Share on social media