Sparse meshless models of complex deformable solids

Abstract

A new method to simulate deformable objects with heterogeneous material properties and complex geometries is presented. Given a volumetric map of the material properties and an arbitrary number of control nodes, a distribution of the nodes is computed automatically, as well as the associated shape functions. Reference frames attached to the nodes are used to apply skeleton subspace deformation across the volume of the objects. A continuum mechanics formulation is derived from the displacements and the material properties. We introduce novel material-aware shape functions in place of the traditional radial basis functions used in meshless frameworks. In contrast with previous approaches, these allow coarse deformation functions to efficiently resolve non-uniform stiffnesses. Complex models can thus be simulated at high frame rates using a small number of control nodes.

References

1. Adams, B., Ovsjanikov, M., Wand, M., Seidel, H.-P., and Guibas, L. 2008. Meshless modeling of deformable shapes and their motion. In Symposium on Computer Animation, 77--86.
2. Allard, J., Cotin, S., Faure, F., Bensoussan, P.-J., Poyer, F., Duriez, C., Delingette, H., and Grisoni, L. 2007. SOFA - an open source framework for medical simulation. In Medicine Meets Virtual Reality, MMVR 15, 2007, 1--6.
3. Allard, J., Faure, F., Courtecuisse, H., Falipou, F., Duriez, C., and Kry, P. 2010. Volume contact constraints at arbitrary resolution. ACM Transactions on Graphics 29, 3.
4. An, S. S., Kim, T., and James, D. L. 2008. Optimizing cubature for efficient integration of subspace deformations. ACM Trans. Graph. 27, 5, 1--10.
5. Baraff, D., and Witkin, A. 1998. Large steps in cloth simulation. SIGGRAPH Comput. Graph. 32, 106--117.
6. Barbič, J., and James, D. L. 2005. Real-time subspace integration for St. Venant-Kirchhoff deformable models. ACM Transactions on Graphics (SIGGRAPH 2005) 24, 3 (Aug.), 982--990.
7. Bathe, K. 1996. Finite Element Procedures. Prentice Hall.
8. Fries, T.-P., and Matthies, H. 2003. Classification and overview of meshfree methods. Tech. rep., TU Brunswick, Germany.
9. Galoppo, N., Otaduy, M. A., Moss, W., Sewall, J., Curtis, S., and Lin, M. C. 2009. Controlling deformable material with dynamic morph targets. In Proc. of the ACM SIGGRAPH Symposium on Interactive 3D Graphics and Games.
10. Gilles, B., Bousquet, G., Faure, F., and Pai, D. 2011. Frame-based elastic models. ACM Transactions on Graphics.
11. Gross, M., and Pfister, H. 2007. Point-Based Graphics. Morgan Kaufmann.
12. Irving, G., Teran, J., and Fedkiw, R. 2006. Tetrahedral and hexahedral invertible finite elements. Graph. Models 68, 2.
13. James, D. L., and Pai, D. K. 2003. Multiresolution green's function methods for interactive simulation of large-scale elastostatic objects. ACM Trans. Graph. 22 (January), 47--82.
14. Kaufmann, P., Martin, S., Botsch, M., and Gross, M. 2008. Flexible simulation of deformable models using discontinuous galerkin fem. In Symposium on Computer Animation.
15. Kavan, Collins, Zara, and O'Sullivan. 2007. Skinning with dual quaternions. In Symposium on Interactive 3D graphics and games, 39--46.
16. Kharevych, L., Mullen, P., Owhadi, H., and Desbrun, M. 2009. Numerical coarsening of inhomogeneous elastic materials. ACM Trans. Graph. 28 (July), 51:1--51:8.
17. Kim, T., and James, D. L. 2009. Skipping steps in deformable simulation with online model reduction. ACM Trans. Graph. 28 (December), 123:1--123:9.
18. Liu, Y., Wang, W., Lévy, B., Sun, F., Yan, D.-M., Lu, L., and Yang, C. 2009. On Centroidal Voronoi TessellationEnergy Smoothness and Fast Computation. ACM Trans. Graph. 28 (08).
19. Magnenat-Thalmann, N., Laperrière, R., and Thalmann, D. 1988. Joint dependent local deformations for hand animation and object grasping. In Graphics interface, 26--33.
20. Martin, S., Kaufmann, P., Botsch, M., Wicke, M., and Gross, M. 2008. Polyhedral finite elements using harmonic basis functions. Comput. Graph. Forum 27, 5.
21. Martin, S., Kaufmann, P., Botsch, M., Grinspun, E., and Gross, M. 2010. Unified simulation of elastic rods, shells, and solids. SIGGRAPH Comput. Graph. 29, 3.
22. Müller, M., and Gross, M. 2004. Interactive virtual materials. In Graphics Interface.
23. Müller, M., Keiser, R., Nealen, A., Pauly, M., Gross, M., and Alexa, M. 2004. Point based animation of elastic, plastic and melting objects. In Symposium on Computer Animation, 141--151.
24. Müller, M., Heidelberger, B., Teschner, M., and Gross, M. 2005. Meshless deformations based on shape matching. ACM Transactions on Graphics 24, 3, 471--478.
25. Nadler, B., and Rubin, M. 2003. A new 3-d finite element for nonlinear elasticity using the theory of a cosserat point. Int. J. of Solids and Struct. 40, 4585--4614.
26. Nealen, A., Müller, M., Keiser, R., Boxerman, E., and Carlson, M. 2005. Physically based deformable models in computer graphics. In Comput. Graph. Forum, vol. 25 (4), 809--836.
27. Nesme, M., Kry, P., Jerabkova, L., and Faure, F. 2009. Preserving Topology and Elasticity for Embedded Deformable Models. SIGGRAPH Comput. Graph..
28. Powell, M. J. D. 1990. The theory of radial basis function approximation. University Numerical Analysis Report.
29. Sifakis, E., Der, K. G., and Fedkiw, R. 2007. Arbitrary cutting of deformable tetrahedralized objects. In Symposium on Computer Animation.
30. Terzopoulos, D., Platt, J., Barr, A., and Fleischer, K. 1987. Elastically deformable models. In SIGGRAPH Comput. Graph., M. C. Stone, Ed., vol. 21, 205--214.
31. Tournois, J., Wormser, C., Alliez, P., and Desbrun, M. 2009. Interleaving delaunay refinement and optimization for practical isotropic tetrahedron mesh generation. ACM Trans. Graph. 28 (July), 75:1--75:9.

Index Terms

• Computing methodologies

  • Computer graphics

    • Shape modeling

• Theory of computation

  • Randomness, geometry and discrete structures

    • Computational geometry