Martin Servin
Department of Physics, Umeå University, Sweden
Claude Lacoursiére
HPC2N/VRlab and Computing Science Department, Umeå University, Sweden
Niklas Melin
Department of Physics, Umeå University, Sweden
Download article
Published in: SIGRAD 2006. The Annual SIGRAD Conference; Special Theme: Computer Games
Linköping Electronic Conference Proceedings 19:5, p. 22–32
Published: 2006-11-22
ISBN:
ISSN: 1650-3686 (print), 1650-3740 (online)
A novel; fast; stable; physics-based numerical method for interactive simulation of elastically deformable objects is presented. Starting from elasticity theory; the deformation energy is modeled in terms of the positions of point masses using the linear shape functions of finite element analysis; providing for an exact correspondence between the known physical properties of deformable bodies such as Young’s modulus; and the simulation parameter. By treating the infinitely stiff case as a kinematic constraint on a system of point particles and using a regularization technique; a stable first order stepping algorithm is constructed which allows the simulation of materials over the entire range of stiffness values; including incompressibility. The main cost of this method is the solution of a linear system of equations which is large but sparse. Commonly available sparse matrix packages can process this problem with linear complexity in the number of elements for many cases. This method is contrasted with other well-known point mass models of deformable solids which rely on penalty forces constructed from simple local geometric quantities; e.g.; spring-and-damper models. For these; the mapping between the simulation parameters and the physical observables is not well defined and they are either strongly limited to the low stiffness case when using explicit integration methods; or produce grossly inaccurate results when using simple linearly implicit method. Validation and timing tests on the new method show that it produces very good physical behavior at a moderate computational cost; and it is usable in the context of real-time interactive simulations.
CR Categories: I.3.5 [Computer Graphics]: Physically based modeling—[I.3.7]: Computer Graphics—Virtual reality
deformable simulation; elasticity; constrained dynamics; stability; numerical integration
ALLEN; M. P. 2004. Introduction to molecular dynamics simulation. N. Attig; K. Binder; H. Grubmller; and K. Kremer; editors; Computational Soft Matter: From Synthetic Polymers to Proteins; John von Neumann Institue for Computing; Jlich; Germany;.
BARAFF; D.; AND WITKIN; A. 1998. Large steps in cloth simulation. In SIGGRAPH ’98: Proceedings of the 25th annual conference on Computer graphics and interactive techniques; ACM Press; New York; NY; USA; 43–54.
BARAFF; D. 1996. Linear-time dynamics using lagrange multipliers. In SIGGRAPH ’96: Proceedings of the 23rd annual conference on Computer graphics and interactive techniques; ACM Press; New York; NY; USA; 137–146.
BAUMGARTE; J. 1972. Stabilization of constraints and integrals of motion in dynamical systems. Computer Methods in Applied Mechanics and Engineering 1; 1; 1–16.
BRO-NIELSEN; M.; AND COTIN; S. 1996. Real-time volumetric deformable models for surgery simulation using finite elements and condensation. Computer Graphics Forum 15; 3; 57–66.
ERLEBEN; K.; SPORRING; J.; HENRIKSEN; K.; AND DOHLMANN; H. 2005. Physics-based Animation. Charles River Media; Aug.
FUNG; Y. C.; AND TONG; P. 2001. Classical and Computational Solid Mechanics. World Scientific; Singapore.
HAUTH; M.; GROSS; J.; AND STRASSER; W. 2003. Interactive physically based solid dynamics. Proceedings of the 2003 ACM SIGGRAPH/Eurographics symposium on Computer animation.
KHAREVYCH; L.; WEIWEI; TONG; Y.; KANSO; E.; MARSDEN; J. E.; SCHRDER; P.; AND DESBRUN; M. 2006. Geometric; variational integrators for computer animation. to appear in ACM/EG Symposium on Computer Animation 2006.
LACOURSI`E RE; C. 2006. A regularized time stepper for multibody simulations. Internal report; UMINF 06.04; issn 0348-0542.
LANDAU; L.; AND LIFSCHITZ; E. 1986. Theory of Elasticity. Pergamon Press; Oxford; 3rd ed.
MARSDEN; J. E.; AND WEST; M. 2001. Discrete mechanics and variational integrators. Acta Numerica 10; 357–514.
MULLER; M.; KEISER; R.; NEALEN; A.; PAULY; M.; GROSS; M.; AND ALEXA; M. 2004. Point based animation of elastic; plastic and melting objects. Proceedings of the 2004 ACM SIGGRAPH/ Eurographics symposium on Computer animation 14; 15.
MULLER; M.; HEIDELRBERGER; B.; TESCHNER; M.; AND GROSS; M. 2005. Meshless deformations based on shape matching. ACMTransactions on Computer Graphics (ACMSIGGRAPH 2005).
NEALEN; A.; MULLER; M.; KEISER; R.; BOXERMAN; E.; AND CARLSON; M. 2005. Physically based deformable models in computer graphics. Eurographics State-of-the-Art Report.
RUBIN; H.; AND UNGAR; P. 1957. Motion under a strong constraining force. Communications on Pure and Applied Mathematics X:65-67.
TERZOPOULOS; D.; PLATT; J.; BARR; A.; AND FLEISCHER; K. 1987. Elastically deformable models. Communications on Pure and Applied Mathematics 21; 205–214.
TESCHNER; M.; HEIDELBERGER; B.; MULLER; M.; AND GROSS; M. 2004. A versatile and robust model for geometrically complex deformable solids. In CGI ’04: Proceedings of the Computer Graphics International (CGI’04); IEEE Computer Society; Washington; DC; USA; 312–319. UMFPACK. http://www.cise.ufl.edu/research/sparse/ umfpack/.
WITKIN; A.; GLEICHER; M.; AND WELCH; W. 1990. Interactive dynamics. Computer Graphics 24; 2; 11–21.
