Game Development Reference

In-Depth Information

The key is to use linear elasticity, as we explained in the previous section,

and handle the artifacts that may arise from its use to keep accurate, fast, and ro-

bust simulations. Finite element methods that assume linear elasticity are usually

known as
linear FEM
. In this section we describe all the needed theory to easily

implement a type of linear FEM and show how to prevent linear-elasticity-related

inaccuracy issues.

10.3.1 Discretization

In order to simulate the deformations of the continuum object, we need to repre-

sent the constitutive equations of the object in a way that the computer can solve

numerically; in other words, we need to discretize the continuum object. There

exist several techniques to this end, but the most widely used is the finite element

method due to its accuracy in modeling deformations on complex bodies.

The idea behind the finite element method is to discretize the object into a

finite set of adjacent and nonoverlapping subdomains that are, in general, either

four-node tetrahedrons or eight-node hexahedrons. The displacement fields of

the continuum matter within the tetrahedrons or hexahedrons are mapped to their

vertices, allowing us to approximate the constitutive equation laws of the object

using the displacements of their nodes. The whole set of finite elements is usually

known as a tetrahedral or hexahedral mesh.

Tetrahedrons are the usual choice for representing finite elements since they

can be constructed from triangular meshes, and they are arguably the best choice.

Hexahedral meshes are, however, more accurate but require more memory re-

sources (information on eight nodes instead of four) and are obviously more com-

putationally expensive, but on the other hand, hexahedral meshes can represent

objects with less elements than can tetrahedral meshes.

We use tetrahedrons in this chapter. Describing the techniques used to gener-

ate tetrahedral meshes are out of the scope of this chapter. The reader can refer to

these works for further details [Spillman et al. 06, Muller and Teschner 03]. Al-

ternatively, there exists a well-documented and simple open-source library known

as TetGen [Si 09]. It is, however, important to remark that the construction of the

tetrahedral mesh is a crucial step since the quality of the tetrahedron, and their

distribution within the object may vary the complexity of the system. Badly dis-

tributed tetrahedral meshes or almost flat tetrahedrons may lead to complex and

harder-to-solve systems.

In order to replace the continuous displacement field with the displacement of

the tetrahedron vertex we use what we call
shape functions
, which in general, for

a tetrahedron, are based on its barycentric coordinates (see
Figure 10.3
)
. Let the

displacement field over the tetrahedron be defined as
ˆ
u
=[
u
x
,u
y
,u
z
], which are