“Precomputing interactive dynamic deformable scenes” by James and Fatahalian

  • ©Doug L. James and Kayvon Fatahalian




    Precomputing interactive dynamic deformable scenes



    We present an approach for precomputing data-driven models of interactive physically based deformable scenes. The method permits real-time hardware synthesis of nonlinear deformation dynamics, including self-contact and global illumination effects, and supports real-time user interaction. We use data-driven tabulation of the system’s deterministic state space dynamics, and model reduction to build efficient low-rank parameterizations of the deformed shapes. To support runtime interaction, we also tabulate impulse response functions for a palette of external excitations. Although our approach simulates particular systems under very particular interaction conditions, it has several advantages. First, parameterizing all possible scene deformations enables us to precompute novel reduced coparameterizations of global scene illumination for low-frequency lighting conditions. Second, because the deformation dynamics are precomputed and parameterized as a whole, collisions are resolved within the scene during precomputation so that runtime self-collision handling is implicit. Optionally, the data-driven models can be synthesized on programmable graphics hardware, leaving only the low-dimensional state space dynamics and appearance data models to be computed by the main CPU.


    1. ABRAHAM, R. H., AND SHAW, C. D. 1992. Dynamics – the Geometry of Behavior. Addison-Wesley.Google Scholar
    2. ALEXA, M., AND MÜLLER, W. 2000. Representing Animations by Principal Components. Computer Graphics Forum 19, 3 (Aug.), 411–418.Google ScholarCross Ref
    3. ATKESON, C., MOORE, A., AND SCHAAL, S. 1997. Locally Weighted Learning for Control. AI Review 11, 75–113. Google ScholarDigital Library
    4. BARAFF, D., AND WITKIN, A. P. 1998. Large Steps in Cloth Simulation. In Proceedings of SIGGRAPH 98, 43–54. Google Scholar
    5. BLANZ, V., AND VETTER, T. 1999. A Morphable Model for the Synthesis of 3D Faces. In Proc. of SIGGRAPH 99, 187–194. Google Scholar
    6. 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. Google ScholarDigital Library
    7. CAPELL, S., GREEN, S., CURLESS, B., DUCHAMP, T., AND POPOVIĆ, Z. 2002. A Multiresolution Framework for Dynamic Deformations. In ACM SIGGRAPH Symposium on Computer Animation, 41–48. Google Scholar
    8. COTIN, S., DELINGETTE, H., AND AYACHE, N. 1999. Realtime Elastic Deformations of Soft Tissues for Surgery Simulation. IEEE Trans. on Vis. and Comp. Graphics 5, 1, 62–73. Google ScholarDigital Library
    9. DEBUNNE, G., DESBRUN, M., CANI, M.-P., AND BARR, A. H. 2001. Dynamic Real-Time Deformations Using Space & Time Adaptive Sampling. In Proceedings of SIGGRAPH 2001, 31–36. Google ScholarDigital Library
    10. EVERITT, C., AND KILGARD, M. J. 2002. Practical and Robust Stenciled Shadow Volumes for Hardware-Accelerated Rendering. Tech. rep., NVIDIA Corporation, Inc., Austin, Texas.Google Scholar
    11. GOLUB, G. H., AND LOAN, C. F. V. 1996. Matrix Computations, third ed. Johns Hopkins University Press, Baltimore. Google Scholar
    12. GRINSPUN, E., KRYSL, P., AND SCHRÖDER, P. 2002. CHARMS: A Simple Framework for Adaptive Simulation. ACM Transactions on Graphics 21, 3 (July), 281–290. Google ScholarDigital Library
    13. GRZESZCZUK, R., TERZOPOULOS, D., AND HINTON, G. 1998. NeuroAnimator: Fast Neural Network Emulation and Control of PhysicsBased Models. In Proceedings of SIGGRAPH 98, 9–20. Google Scholar
    14. GUCKENHEIMER, J., AND HOLMES, P. 1983. Nonlinear oscillations, dynamical systems, and bifurcations of vector fields (Appl. math. sci.; v.42). Springer-Verlag New York, Inc.Google Scholar
    15. HEIDRICH, W. 2001. Interactive Display of Global Illumination Solutions for Non-diffuse Environments – A Survey. Computer Graphics Forum 20, 4, 225–244.Google ScholarCross Ref
    16. JAMES, D. L., AND FATAHALIAN, K. 2003. Precomputing Interactive Dynamic Deformable Scenes. Tech. rep., Carnegie Mellon University, Robotics Institute.Google Scholar
    17. JAMES, D. L., AND PAI, D. K. 1999. ARTDEFO – Accurate Real Time Deformable Objects. In Proc. of SIGGRAPH 99, 65–72. Google Scholar
    18. JAMES, D. L., AND PAI, D. K. 2002. DyRT: Dynamic Response Textures for Real Time Deformation Simulation With Graphics Hardware. ACM Trans. on Graphics 21, 3 (July), 582–585. Google ScholarDigital Library
    19. JAMES, D. L., AND PAI, D. K. 2002. Real Time Simulation of Multizone Elastokinematic Models. In Proceedings of the IEEE International Conference on Robotics and Automation, 927–932.Google Scholar
    20. JAMES, D. L., AND PAI, D. K. 2003. Multiresolution Green’s Function Methods for Interactive Simulation of Large-scale Elastostatic Objects. ACM Trans. on Graphics 22, 1, 47–82. Google ScholarDigital Library
    21. KOVAR, L., GLEICHER, M., AND PIGHIN, F. 2002. Motion Graphs. ACM Transactions on Graphics 21, 3 (July), 473–482. Google ScholarDigital Library
    22. KRY, P. G., JAMES, D. L., AND PAI, D. K. 2002. EigenSkin: Real Time Large Deformation Character Skinning in Hardware. In SIGGRAPH Symposium on Computer Animation, 153–160. Google Scholar
    23. KRYSL, P., LALL, S., AND MARSDEN, J. E. 2001. Dimensional model reduction in non-linear finite element dynamics of solids and structures. International Journal for Numerical Methods in Engineering 51, 479–504.Google ScholarCross Ref
    24. LEE, A., MORETON, H., AND HOPPE, H. 2000. Displaced Subdivision Surfaces. In Proc. of SIGGRAPH 2000, 85–94. Google ScholarDigital Library
    25. 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. Google ScholarDigital Library
    26. LENGYEL, J. E. 1999. Compression of Time-Dependent Geometry. In ACM Symposium on Interactive 3D Graphics, 89–96. Google Scholar
    27. LINDHOLM, E., J. KILGARD, M., AND MORETON, H. 2001. A User-Programmable Vertex Engine. In Proceedings of SIGGRAPH 2001, 149–158. Google ScholarDigital Library
    28. LUMLEY, J. L. 1967. The structure of inhomogeneous turbulence. In Atmospheric turbulence and wave propagation, 166–178.Google Scholar
    29. NELLES, O. 2000. Nonlinear System Identification: From Classical Approaches to Neural Networks and Fuzzy Models. Springer Verlag, December.Google Scholar
    30. O’BRIEN, J., AND HODGINS, J. 1999. Graphical Modeling and Animation of Brittle Fracture. In SIGGRAPH 99 Conference Proceedings, 111–120. Google Scholar
    31. OLANO, M., HART, J. C., HEIDRICH, W., AND MCCOOL, M. 2002. Real-Time Shading. A. K. Peters. Google Scholar
    32. PEERCY, M. S., OLANO, M., AIREY, J., AND UNGAR, P. J. 2000. Interactive Multi-Pass Programmable Shading. In Proceedings of SIGGRAPH 2000, 425–432. Google ScholarDigital Library
    33. PENTLAND, A., AND WILLIAMS, J. 1989. Good Vibrations: Modal Dynamics for Graphics and Animation. In Computer Graphics (SIGGRAPH89), vol. 23, 215–222. Google Scholar
    34. POINCARÉ, H. 1957. Les Méthodes Nouvelles de la Mécanique Célèste I, II, III. (Reprint by) Dover Publications.Google Scholar
    35. PROUDFOOT, K., MARK, W. R., TZVETKOV, S., AND HANRAHAN, P. 2001. A Real-Time Procedural Shading System for Programmable Graphics Hardware. In Proceedings of SIGGRAPH 2001, 159–170. Google ScholarDigital Library
    36. PURCELL, T. J., BUCK, I., MARK, W. R., AND HANRAHAN, P. 2002. Ray Tracing on Programmable Graphics Hardware. ACM Transactions on Graphics 21, 3 (July), 703–712. Google ScholarDigital Library
    37. REISSELL, L. M., AND PAI, D. K. 2001. Modeling Stochastic Dynamical Systems for Interactive Simulation. Computer Graphics Forum 20, 3, 339–348.Google ScholarCross Ref
    38. SCHÖDL, A., SZELISKI, R., SALESIN, D. H., AND ESSA, I. 2000. Video Textures. In Proc. of SIGGRAPH 2000, 489–498. Google Scholar
    39. SHABANA, A. 1990. Theory of Vibration, Volume II: Discrete and Continuous Systems, first ed. Springer-Verlag, New York, NY.Google Scholar
    40. SLOAN, P.-P. J., III, C. F. R., AND COHEN, M. F. 2001. Shape by Example. In ACM Symp. on Interactive 3D Graphics, 135–144. Google Scholar
    41. SLOAN, P.-P., KAUTZ, J., AND SNYDER, J. 2002. Precomputed Radiance Transfer for Real-Time Rendering in Dynamic, Low-Frequency Lighting Environments. ACM Transactions on Graphics 21, 3 (July), 527–536. Google ScholarDigital Library
    42. STAM, J. 1997. Stochastic Dynamics: Simulating the Effects of Turbulence on Flexible Structures. Computer Graphics Forum 16(3).Google Scholar
    43. TERZOPOULOS, D., PLATT, J., BARR, A., AND FLEISCHER, K. 1987. Elastically Deformable Models. In Computer Graphics (Proceedings of SIGGRAPH 87), vol. 21(4), 205–214. Google Scholar
    44. WEIL, J. 1986. The Synthesis of Cloth Objects. In Computer Graphics (Proceedings of SIGGRAPH 86), vol. 20(4), 49–54. Google Scholar

ACM Digital Library Publication: