Fast simulation of deformable models in contact using dynamic deformation textures

ABSTRACT

We present an efficient algorithm for simulating contacts between deformable bodies with high-resolution surface geometry using dynamic deformation textures, which reformulate the 3D elastoplastic deformation and collision handling on a 2D parametric atlas to reduce the extremely high number of degrees of freedom in such a computationally demanding simulation. We perform proximity queries for deformable bodies using a two-stage algorithm directly on dynamic deformation textures, resulting in output-sensitive collision detection that is independent of the combinatorial complexity of the deforming meshes. We present a robust, parallelizable formulation for computing constraint forces using implicit methods that exploits the structure of the motion equations to achieve highly stable simulation, while taking large time steps with inhomogeneous materials. The dynamic deformation textures can also be used directly for real-time shading and can easily be implemented using SIMD architecture on commodity hardware. We show that our approach, complementing existing pioneering work, offers significant computational advantages on challenging contact scenarios in dynamic simulation of deformable bodies.

References

1. {BFA02} Bridson R., Fedkiw R., Anderson J.: Robust treatment of collisions, contact and friction for cloth animation. In Proc. of ACM SIGGRAPH (2002).
2. {BJ05} Barbič J., James D. L.: Real-time subspace integration of St. Venant-Kirchhoff deformable models. In Proc. of ACM SIGGRAPH (2005).
3. {BNC96} Bro-Nielsen M., Cotin S.: Real-time volumetric deformable models for surgery simulation using finite elements and condensation. Computer Graphics Forum 15, 3 (1996).
4. {CBC*05} Capell S., Burkhart M., Curless B., Duchamp T., Popovic Z.: Physically based rigging for deformable characters. Proc. of Eurographics/ACM SIGGRAPH Symposium on Computer Animation (2005).
5. {CGC*02} Capell S., Green S., Curless B., Duchamp T., Popovic Z.: A multiresolution framework for dynamic deformations. Proc. of ACM SIGGRAPH Symposium on Computer Animation (2002).
6. {CHP89} Chadwick J. E., Haumann D. R., Parent R. E.: Layered construction for deformable animated characters. In Proc. of ACM SIGGRAPH (1989).
7. {COM98} Cohen J., Olano M., Manocha D.: Appearance-preserving simplification. In Proc. of ACM SIGGRAPH (1998).
8. {CW05} Cirak F., West M.: Decomposition contact response (OCR) for explicit finite element dynamics. International Journal for Numerical Methods in Engineering 64, 8 (2005).
9. {DAK04} Duriez C., Andriot C., Kheddar A.: Signorini's contact model for deformable objects in haptic simulations. Proc. of IEEE/RSJ IROS (2004).
10. {DDCB01} Debunne G., Desbrun M., Cani M. P., Barr A. H.: Dynamic real-time deformations using space and time adaptive sampling. Proc. of ACM SIGGRAPH (2001).
11. {EL01} Ehmann S. A., Lin M. C.: Accurate and fast proximity queries between polyhedra using convex surface decomposition. In Proc. of Eurographics (2001).
12. {Gas98} Gascuel M.-P.: Layered deformable models with implicit surfaces. In Proc. of Graphics Interface (1998).
13. {GKS02} Grinspun E., Krysl P., Schröder P.: CHARMS: A simple framework for adaptive simulation. Proc. of ACM SIGGRAPH (2002).
14. {GPS02} Goldstein H., Poole C., Safko J.: Classical Mechanics, 3rd Ed. Addison Wesley, 2002.
15. {GV96} Golub G. H., Van Loan C. F.: Matrix Computations, 3rd ed. Johns Hopkins University Press, 1996.
16. {HFS03} Hirota G., Fisher S., State A.: An improved finite element contact model for anatomical simulations. The Visual Computer 19, 5 (2003).
17. {HSO03} Hauser K. K., Shen C., O'Brien J. F.: Interactive deformation using modal analysis with constraints. Proc. of Graphics Interface (2003).
18. {JP99} James D. L., Pai D. K.: ArtDefo: accurate real time deformable objects. In Proc. of ACM SIGGRAPH (1999).
19. {JP02} James D. L., Pai D. K.: DyRT: Dynamic response textures for real-time deformation simulation with graphics hardware. In Proc. of ACM SIGGRAPH (2002).
20. {KW03} Kruger J., Westermann R.: Linear algebra operators for GPU implementation of numerical algorithms. In Proc. of ACM SIGGRAPH (2003).
21. {MG04} Müller M., Gross M.: Interactive virtual materials. Proc. of Graphics Interface (2004).
22. {Mir96} Mirtich B. V.: Impulse-Based Dynamic Simulation of Rigid Body Systems. PhD thesis, University of California at Berkeley, 1996.
23. {MT92} Metaxas D., Terzopoulos D.: Dynamic deformation of solid primitives with constraints. Proc. of ACM SIGGRAPH (1992).
24. {NMK*05} Nealen A., Müller M., Keiser R., Boxermann E., Carlson M.: Physically based deformable models in computer graphics (state of the art report). Eurographics STAR (2005).
25. {OJSL04} Otaduy M. A., Jain N., Sud A., Lin M. C.: Haptic display of interaction between textured models. In Proc. of IEEE Visualization (2004).
26. {PPG04} Pauly M., Pai D. K., Guibas L. J.: Quasi-rigid objects in contact. In Proc. of ACM SIGGRAPH/Eurographics Symposium on Computer Animation (2004).
27. {Sha89} Shabana A. A.: Dynamics of Multibody Systems. John Wiley and Sons, 1989.
28. {SOH99} Sumner R. W., O'Brien J. F., Hodgins J. K.: Animating sand, mud, and snow. Computer Graphics Forum 18, 1 (1999).
29. {SSGH01} Sander P. V., Snyder J., Gortler S. J., Hoppe H.: Texture mapping progressive meshes. Proc. of ACM SIGGRAPH (2001).
30. {Sta03} Stam J.: Flow on surfaces of arbitrary topology. In Proc. of ACM SIGGRAPH (2003).
31. {TKH*05} Teschner M., Kimmerle S., Heidelberger B., Zachmann G., Raghupathi L., Furhmann A., Cani M.-P., Faure F., Magnenat-Thalmann N., Strasser W., Volino P.: Collision detection for deformable objects. Computer Graphics Forum 24, 1 (2005).
32. {TPBF87} Terzopoulos D., Platt J., Barr A., Fleischer K.: Elastically deformable models. Proc. of ACM SIGGRAPH (1987).
33. {TSIF05} Teran J., Sifakis E., Irving G., Fedkiw R.: Robust quasistatic finite elements and flesh simulation. In Proc. of ACM SIGGRAPH/Eurographics Symposium on Computer Animation (2005).
34. {TW88} Terzopoulos D., Witkin A.: Physically based models with rigid and deformable components. IEEE Computer Graphics and Applications 8, 6 (1988).
35. {WRM05} Wrotek P., Rice A., McGuire M.: Real-time collision deformations using graphics hardware. Journal of Graphics Tools 10, 5 (2005).
36. {WVS90} Wriggers P., Vu Van T., Stein E.: Finite element formulation of large deformation impact-contact problems with friction. Computers & Structures 37, 3 (1990).
37. {ZC99} Zhuang Y., Canny J.: Real-time simulation of physically realistic global deformation. Proc. of IEEE Visualization (1999).
38. {ZSS97} Zorin D., Schröder P., Sweldens W.: Interactive multiresolution mesh editing. In Proc. of ACM SIGGRAPH (1997).

Index Terms

• Computing methodologies

  • Computer graphics

    • Animation

    • Image manipulation

      • Texturing

    • Shape modeling

      • Parametric curve and surface models

      • Volumetric models

  • Modeling and simulation

    • Simulation types and techniques

      • Simulation by animation