Interactive Simulation and Visualization of Volumetric Deformable Objects
by Bertram Wilm, February 2004
modelling of elastic deformation has a long history in mechanical engineering and material science. In those disciplines, the main aim is to model the physical world as accurate as possible. In real-time graphics applications the primary concern still is a compromise between computational effort and the prediction of exact results, although the increasing performance of today's computers and graphics hardware.
Typical applications of elastic modelling are virtual surgery, virtual sculpturing or any application requiring an interactive virtual environment. Additionally a real-time simulator could offer designers the option to create and test animations interactively before rendering their work offline in higher quality.
Early approaches used mass-spring systems to animate deformation in real-time. In mass-spring systems, a deformable body is approximated by a set of masses linked by springs in a lattice structure. Though computationally efficient, mass-spring models don't always provide physically plausible results. Therefore, this work dedicates itself to more accurate models that are based on elasticity theory of continuum mechanics using finite element methods (FEM). In FEM the continuum or object is divided into distinct finite sub-domains, or elements with discrete endpoints. In this case, the deformable body is discretized by tetrahedral elements using linear polynomial shape functions which seem to be the best trade-off between speed and accuracy for real-time simulations.
The practical work of this thesis contains two implementations:
The first one often is called (spatial) explicit finite elements, meaning that the underlying differential equations are solved separately for each finite element. The second implementation, a straight forward FEM approach uses the simplified linear elasticity theory to enable real-time simulation for volumetric meshes (bodies) of reasonable size. Linear elasticity only models small non-rotational deformations accurately but its computational cost is much lower than the cost of a non-linear stress measure as used in the explicit finite element implementation. For the straight forward FEM approach each time-step involves solving a large sparse but ill-conditioned linear algebraic system. To solve this linear system efficiently, I compared matrix-preinversion and conjugate gradient (CG) methods using different preconditioners and also considered the use of geometric multigrid methods.