“Many-worlds browsing for control of multibody dynamics” by Twigg and James

  • ©Christopher D. Twigg and Doug L. James




    Many-worlds browsing for control of multibody dynamics



    Animation techniques for controlling passive simulation are commonly based on an optimization paradigm: the user provides goals a priori, and sophisticated numerical methods minimize a cost function that represents these goals. Unfortunately, for multibody systems with discontinuous contact events these optimization problems can be highly nontrivial to solve, and many-hour offline optimizations, unintuitive parameters, and convergence failures can frustrate end-users and limit usage. On the other hand, users are quite adaptable, and systems which provide interactive feedback via an intuitive interface can leverage the user’s own abilities to quickly produce interesting animations. However, the online computation necessary for interactivity limits scene complexity in practice.We introduce Many-Worlds Browsing, a method which circumvents these limits by exploiting the speed of multibody simulators to compute numerous example simulations in parallel (offline and online), and allow the user to browse and modify them interactively. We demonstrate intuitive interfaces through which the user can select among the examples and interactively adjust those parts of the scene that do not match his requirements. We show that using a combination of our techniques, unusual and interesting results can be generated for moderately sized scenes with under an hour of user time. Scalability is demonstrated by sampling much larger scenes using modest offline computations.


    1. Assarsson, U., and Möller, T. 2000. Optimized view frustum culling algorithms for bounding boxes. Journal of Graphics Tools 5, 1, 9–22. Google ScholarDigital Library
    2. Baraff, D. 1994. Fast contact force computation for nonpenetrating rigid bodies. In Proceedings of ACM SIGGRAPH 1994, 23–34. Google ScholarDigital Library
    3. Barzel, R., Hughes, J. F., and Wood, D. 1996. Plausible motion simulation for computer animation. In EGCAS ’96: Seventh International Workshop on Computer Animation and Simulation. Google ScholarDigital Library
    4. Chenney, S., and Forsyth, D. A. 2000. Sampling plausible solutions to multi-body constraint problems. In Proceedings of ACM SIGGRAPH 2000, 219–228. Google ScholarDigital Library
    5. Cohen, M. F. 1992. Interactive spacetime control for animation. In Computer Graphics (Proceedings of SIGGRAPH 92), 293–302. Google ScholarDigital Library
    6. Fattal, R., and Lischinski, D. 2004. Target-driven smoke animation. ACM Transactions on Graphics 23, 3 (Aug.), 441–448. Google ScholarDigital Library
    7. Grassia, F. S. 1998. Practical parameterization of rotations using the exponential map. Journal of Graphics Tools 3, 3, 29–48. Google ScholarDigital Library
    8. Guendelman, E., Bridson, R., and Fedkiw, R. P. 2003. Nonconvex rigid bodies with stacking. ACM Transactions on Graphics 22, 3 (July), 871–878. Google ScholarDigital Library
    9. Haugland, D., Heber, J. G., and Husøy, J. H. 1997. Optimisation algorithms for ECG data compression. Medical and Biological Engineering and Computing 35, 420–424.Google ScholarCross Ref
    10. Hochheiser, H., and Shneiderman, B. 2004. Dynamic query tools for time series data sets: Timebox widgets for interactive exploration. Information Visualization 3, 1–18. Google ScholarDigital Library
    11. Kaufman, D. M., Edmunds, T., and Pai, D. K. 2005. Fast frictional dynamics for rigid bodies. ACM Transactions on Graphics 24, 3 (Aug.), 946–956. Google ScholarDigital Library
    12. Laszlo, J., van de Panne, M., and Fiume, E. L. 2000. Interactive control for physically-based animation. In Proceedings of ACM SIGGRAPH 2000, 201–208. Google ScholarDigital Library
    13. Marks, J., Andalman, B., Beardsley, P. A., Freeman, W., Gibson, S., Hodgins, J. K., Kang, T., Mirtich, B., Pfister, H., Ruml, W., Ryall, K., Seims, J., and Shieber, S. 1997. Design galleries: A general approach to setting parameters for computer graphics and animation. In Proceedings of ACM SIGGRAPH 1997, 389–400. Google ScholarDigital Library
    14. McNamara, A., Treuille, A., Popović, Z., and Stam, J. 2004. Fluid control using the adjoint method. ACM Transactions on Graphics 23, 3 (Aug.), 449–456. Google ScholarDigital Library
    15. Mihalef, V., Metaxas, D., and Sussman, M. 2004. Animation and control of breaking waves. In Proceedings of the 2004 ACM SIGGRAPH / Eurographics Symposium on Computer Animation, 315–324. Google ScholarDigital Library
    16. Nygaard, R., and Haugland, D. 1998. Compressing ECG signals by piecewise polynomial approximation. In Proceedings of the 1998 IEEE International Conference on Acoustics, Speech, and Signal Processing, vol. 3, 1809–1812.Google Scholar
    17. O’Sullivan, C., Dingliana, J., Giang, T., and Kaiser, M. K. 2003. Evaluating the visual fidelity of physically based animations. ACM Transactions on Graphics 22, 3 (July), 527–536. Google ScholarDigital Library
    18. Page, L., Brin, S., Motwani, R., and Winograd, T. 1998. The PageRank Citation Ranking: Bringing Order to the Web. Tech. Rep. SIDL-WP-1999-0120, Stanford Digital Libraries.Google Scholar
    19. Pighin, F., Cohen, J. M., and Shah, M. 2004. Modeling and editing flows using advected radial basis functions. In Proceedings of the 2004 ACM SIGGRAPH / Eurographics Symposium on Computer Animation, 223–232. Google ScholarDigital Library
    20. Popović, J., Seitz, S. M., Erdmann, M., Popović, Z., and Witkin, A. P. 2000. Interactive manipulation of rigid body simulations. In Proceedings of ACM SIGGRAPH 2000, 209–218. Google ScholarDigital Library
    21. Popović, J., Seitz, S. M., and Erdmann, M. 2003. Motion sketching for control of rigid-body simulations. ACM Transactions on Graphics 22, 4 (Oct.), 1034–1054. Google ScholarDigital Library
    22. Rasmussen, N., Nguyen, D. Q., Geiger, W., and Fedkiw, R. P. 2003. Smoke simulation for large-scale phenomena. ACM Transactions on Graphics 22, 3 (July), 703–707. Google ScholarDigital Library
    23. Salomon, D. 2004. Data Compression, third ed. Springer-Verlag New York, Inc. Google ScholarDigital Library
    24. Sherbondy, A., Akers, D., Mackenzie, R., Dougherty, R., and Wandell, B. 2004. Exploring connectivity of the brain’s white matter with dynamic queries. In Proceedings of IEEE Visualization 2004, 377–384. Google ScholarDigital Library
    25. Shi, L., and Yu, Y. 2002. Object modeling and animation with smoke. Tech. Rep. UIUCDCS-R-2002-2262, University of Illinois at Urbana-Champaign, Jan.Google Scholar
    26. Shi, L., and Yu, Y. 2005. Controllable smoke animation with guiding objects. ACM Transactions on Graphics 24, 1 (Jan.), 140–164. Google ScholarDigital Library
    27. Shi, L., and Yu, Y. 2005. Taming liquids for rapidly changing targets. In Proceedings of the 2005 ACM SIGGRAPH / Eurographics Symposium on Computer Animation, 229–236. Google ScholarDigital Library
    28. Shoemake, K. 1985. Animating rotation with quaternion curves. In Computer Graphics (Proceedings of SIGGRAPH 85), 245–254. Google ScholarDigital Library
    29. Smith, R. 2006. Open Dynamics Engine v0.5 Users Guide, Feb.Google Scholar
    30. Tang, D., Ngo, J. T., and Marks, J. 1995. N-body spacetime constraints. The Journal of Visualization and Computer Animation 6, 3 (July-Sept.), 143–154.Google ScholarCross Ref
    31. Treuille, A., McNamara, A., Popović, Z., and Stam, J. 2003. Keyframe control of smoke simulations. ACM Transactions on Graphics 22, 3 (July), 716–723. Google ScholarDigital Library
    32. Wasserman, L. 2004. All of Statistics. Springer-Verlag New York, Inc.Google Scholar
    33. Weinstein, R., Teran, J., and Fedkiw, R. 2006. Dynamic simulation of articulated rigid bodies with contact and collision. IEEE Transactions on Visualization and Computer Graphics 12, 3 (May), 365–374. Google ScholarDigital Library
    34. Witkin, A., and Kass, M. 1988. Spacetime constraints. In Computer Graphics (Proceedings of SIGGRAPH 88), 159–168. Google ScholarDigital Library

ACM Digital Library Publication: