Real-Time Deformation and Fracture

Summary

Introduction

This project was part of our final assignment for our Real-Time Physics course. We were asked to choose a research paper and try to implement it. Given my interest for deformation and destruction I came across an interesting paper, Real-Time Deformation and Fracture in a Game Environment” published in 2009 by G.Parker and F. O’Brien and presented at the SIGGRAPH Symposium on Computer Animation. The paper describes a simulation system that has been developed to model deformation and fracture of solid objects in real time context using a corotational finite element method. It was the first engine based on FEM and running in a real-time game environment. It gives a robust and stable approach to unpredictable user interaction and providing realistic material deformation and fractures.

Their work ended up implemented a game, Star Wars: The Force Unleashed. Surprisingly a version was released for consoles too (PS3/XBOX 360), where they achieved smoothly 30 FPS.  Afterwards the algorithm became part of a Maya plugin called DMM (Digital Molecular Matter) and sold by Pixelux Entertainment.

Here below there is a video that shows the game footage from Star Wars: The Force Unleashed:

Excited and impressed by their work I wanted to pick up this paper, trying to make my own implementation. John Dingliana, my lecturer, warned me from the beginning that the paper I chose was a too complex and not feasible to implement, in the time frame of two weeks that we had to complete the assignment. Nonetheless I decided to go for it. I knew that I was not going to implement such engine system but I was too keen and curious to acquire that knowledge and carry out some experiments. I agreed with John to implement just part of the paper on the condition that I would study the whole thing. Eventually I gave a presentation/tutorial to the class.

Deformation and Fractures

To produce deformation and fractures in real time there are a plethora of techniques available. Canned animations, for example, are widely used because they are extremely cheap. Artists prepare the geometry and the resulting fracturing effect is pre-defined. The drawback of this approach is that it does not produce a realistic result in most of the cases. Finite element formulation instead gives a realistic simulation of material deformation. It is a numerical technique for finding approximate solutions to boundary value problems for partial differential equations. It is widely used in engineering analysis, fluid dynamics and to solve complex problem in physical systems. It is very appealing as a technique itself and it has been used in offline renderer for special effect, but never in real time environment, for its computational complexity.

Preparation

When it comes to the process of deforming and fracturing a 3D model there are two main steps involved: the geometry preparation, where the mesh is subdivided using 3d voronoi cells or the Delaunay tetrahedralization and the simulation step, which is composed of broad phase, narrow phase and collision response. The technique used to prepare the geometry for finite element analysis is usually tetrahedralization. In the specific research paper they made use of the same approach to sub-divide the mesh. A tetrahedra is defined by four nodes, labelled 1, 2, 3 and 4, with reference position u1, u2, u3 and u4, see Figure 1 below. A position in the world coordinates, p, and a velocity in world coordinates, v. Tetrahedra can be generated using the high-order delaunay tetrahedralization. The Delaunay tetrahedralization is the 3D equivalent of triangulation. Instead of generating triangles, it generates tetrahedron. The condition is that the four points of each tetrahedron must lie on the perimeter of a circumsphere.

A tetrahedron

Figure 1 – A tetrahedron

Often, given the mesh geometry, the domain boundaries are not respected, e.g. inconsistencies are caused by coplanar vertices, so the Delaunay condition is not satisfied. These inconsistencies
are removed by facet re-meshing and Steiner point insertions (e.g. introducing additional vertices). The elements in the finite element method are represented by tetrahedron, thus when a mesh is generated, the domain of the original mesh is sub-divided into tetrahedral finite elements. Using tetrahedra is in general a good approach to approximate arbitrary volumes, especially when it comes to generate fractures. When tetrahedra are split along a fracture plane, the resulting pieces can be decomposed exactly into more tetrahedra.

Figure 2 shows an example of a tetrahedralized model.

Tetrahedralization example

Figure 2 – Tetrahedralization example

Finite Element Method

A finite element method (FEM) is characterized by a variational formulation, which is a discretization strategy, one or more solution algorithms and post-processing procedures.
The discretization strategy partitions the domain of the material into distinct elements as shown in Figure 3.

Figure 3 - Tetrahedralize rectangle

Figure 3 – Tetrahedralize rectangle (generated with Mathematica)

Within each element, a local function describes the material and then such function is decomposed into a set of orthogonal shape functions that are each associated with one of the nodes on the boundary of the element. Adjacent elements will have nodes in common, so that the mesh defines a piece-wise function over the entire material domain.

FEM is physically more accurate than mass-spring models or position based dynamics but is more expensive to calculate. Thus in real time context (especially gaming) is hard to use.

Formulation

To achieve real time performance some assumptions need to be made:

  • A linear approximation must be used, which means that the partial differential equation solved must be of the first order. Such PDEs are “easily” solved through numerical integration using common approaches like Euler’s integration or Runge-Kutta 4.
  • Using tetrahedral elements with linear basis function. This type of element is used in finite element analysis to provide an approximate solution in a 2D domain to the exact solution of a given differential equation. When applied to plane stress and plane strain problems, this means that the approximate solution obtained for the stress and strain fields are constant throughout the element’s domain.
  • Deformation is a mapping of the initial object configuration to its deformed configuration.

Let’s define:

  • D_u as a 3×3 matrix with columns u_2 - u_1u_3 - u_1, and u_4 - u_1 for position.
  • D_v for velocity.
  • The element basis matrix \beta = D_u^{-1}

Deformation gradient F and its time derivative G given by:

  • F = \frac{\partial x}{\partial u} = D_u \beta
  • G =\frac{\partial v}{\partial u} = D_v \beta

When a force is exerted on a rigid body, the resulting motion (translation and rotation) induces no change of the body shape. The strain of a body is the change in size and shape that the body has experienced during deformation. Cauchy’s infinitesimal tensor is very cheap to compute from F as it approximate linearly the associated partial differential equation and its Jacobian with respect to the x_i is constant.

\epsilon = \frac{1}{2} (F + F^T) - I

The only drawback is that such tensor is not rotation invariant. If large deformations are applied, artifact and ghost forces are generated producing unrealistic and unexpected results or crashing the whole simulation. A corotational method factors out the rotation on a per-element basis (i.e. per-tetrahedral node). It can be implemented by performing a polar decomposition of F into F = QA where Q is orthonormal and A is symmetric.

Figure 4 - Corotational formulation

Figure 4 – Corotational formulation

Conclusion

Implement the whole paper was a non trivial task. I didn’t have enough time to finish implementing the FEM so I didn’t include deformation in the demo but only fractures. Fractures were obtained using a shattering function. I used Delaunay tetrahedralization to discretize the meshes. As you might have already noticed, fracturing the dragon results in a low frame-rate, due to the presence of a lot of rigid bodies (one per fragment). They are held together using constraints and defining a breaking impulse  threshold. Every fragment generates a high number of contacts points, thus collision detection (broad and narrow phases) is the major bottle neck resulting in a very slow simulation.

Video

Future Work

I’m currently working on my dissertation “Implemented and evaluated algorithms for softbody simulation using Finite Element Analysis on Tegra Mobile Processor” where I’m implementing a CUDA version of the finite element method, to evaluate and test the feasibility of using finite element analysis technique on latest generation mobile devices. If time permits I will implement a fracturing algorithm as well.