Physically based deformable models in computer graphics
Nealen, A., Müller, M., Keiser, R., Boxerman, E., & Carlson, M. (2006). Physically based deformable models in computer graphics. Computer Graphics Forum, 25(4), 809–836. doi:10.1111/j.1467-8659.2006.01000.x
Summary
This is a review paper which gives an overview of some of the techniques that have been used to model deformable objects, including cloth, deformable volumes, and fluids. The major division between methods is whether the method is Eulerian or Lagrangian. Lagrangian methods directly model particles or meshes that are subject to forces, and then update the positions/velocities of those particles/meshes. Eulerian methods, in contrast, directly model the velocity field at each point. As they describe it:
[T]he Lagrangian point of view describes an object as a set of moving points (material coordinates) that travel around and change position over time; these points carry their material properties with them as they move through the world. The Eulerian point of view, on the other hand, looks at a stationary est of points and calculates how the material properties stored at those stationary grid points changes over time. (Sec. 6)
The benefit of Lagrangian methods is that it is easy to define a surface boundary for the material. However, in the case of fluids, Eulerian methods are preferred because they ensure velocities are incompressible and thus divergence free.
Many of the techniques in the paper either use implicit or explicit time integration schemes. Explicit schemes involve an explicit equation for the quantity at the next time step. Implicit schemes have terms for the quantity of the next time step on both sides of the equation, thus implicitly defining the value as the solution to a system of equations.
Lagrangian Methods
Lagrangian methods can either be applied to mesh-based models or mesh-free models.
Mesh-based models
For mesh-based models, the two common approaches are either continuum methods or mass-spring systems. Continuum methods assume a continous object and then discretize the PDE describing the behavior of that object. Mass-spring systems assume a discrete object to begin with (i.e., a lattice of point masses connected by springs). There are a number of variants of continuum methods which differ based on the method of discretization:
- Finite Element Method — discretization occurs using an irregular mesh. In the explicit FEM method, the masses and internal/external foces are lumped into the vertices of the mesh and then the mesh is treated like a mass-spring system. Also, as described in Müller et al., when using implicit time integration with FEM, the resulting system of equations is linear, thus introducing artifacts, and additional processing must be done in order to account for these.
- Method of Finite Differences — discretization occurs using a regular mesh. However, this is difficult to achieve when objects have irregular edges.
- Finite Volume Method — forces are computed by integrating over the face of a finite element, rather than the entire volume of the element (this name seems counterintuitive?)
- Boundary Element Method — computations are done on the surface of the object, rather than its volume. This only works for homogenous materials, though.
While continuum methods are usually used for deformable solid objects, mass-spring systems are more frequently used for cloth.
Mesh-free models
Mesh-free models tend to be used for fluids and fuzzy objects, e.g. fire, clouds, water, etc.
- Loosely coupled particle systems — particles are points in 3D space which define the volume of an object and particles interact pairwise with each other. Depending on the parameters of the potential function, particles can be used to model a range of behaviors from something very stiff to fluid-like. To define the surface of the volume, each particle is assigned a Gaussian potential and then these potentials are summed to form a continuous field in space which defines where the boundary is (this is known as coating).
- Smoothed particle hydrodynamics (SPH) — another particle method (described by Müller et al.) where instead of having pairwise interactions, the forces are derived from Navier-Stokes.
- Point-based animations
- Meshless deformations based on shape matching — vertices of a mesh are animated as a particle system, and then correspondences are found between the original mesh and the particles. Points are pulled back to their original positions, allowing the object to recover from severe deformations.
Eulerian Methods
Stam describes a Eulerian method for fluid simulation which uses the semi-Lagrange technique for advection. Other Eulerian techniques have been developed to include temperature and variable viscosity (enabling melting) and also elasticity (allowing for viscoelastic substances). The surface of the fluid can be computed using level sets, which store the signed distance to the surface of the fluid and which are then updated on each step of the simulation based on the velocity field.