I recently organized a here. This is about the simulation part of breaking objects, not so much about the rendering. To be honest, I’m still learning about this sub-topic so if you have some experience in this area, please let us know in the comments.
A typical destruction process can be divided in two parts:
- the preparation of the 3D geometry, usually done during the creation of a game
- the breaking of objects when playing the game
There are many different ways to prepare the 3D geometry for fracture. Often this involves 3D content creation tools such as Autodesk Maya, 3ds Max or the open source Blender 3D modeler.
Cutting a 3D model into pieces using voronoi shatter is very popular. For example it is used by the Epic Unreal Engine. You first create particles inside the 3D model. Then you create Voronoi regions that enclose those points. Some good algorithms are developed to compute voronoi regions efficiently, given a closed mesh and enclosed points, for example Fortune’s algorithm.
It is also possible to subdivide the original 3d model into a set of tetrahedra, this process is also called a tetrahedralization. It can be done using Delaunay Triangulation, which is the dual of voronoi regions. There are some open source libraries that can perform this task, such as real-time physics SIGGRAPH course.
Boolean operations, also known as constructive solid geometry (CSG) is a way to perform volumetric operations between 3D models. For example you can add two volumes together, or compute the difference between two objects, or take the intersection. Those operations allow you to break original 3D models into smaller pieces, similar to a cookie cutter.
Cutting, slicing etc
Of course there are many other methods to generate a pre-fractured model, for example an artist can create the parts by hand, or some slicing algorithm can be applied based on polygon clipping.
As this is just a short overview, let’s move on to the runtime breaking methods. Aside from triggering a pre-recorded animation of a destruction sequence, some common approaches are:
The Red Faction games by Volition showed some cool destruction in their worlds. Their
The actual boolean operations are based on the merging of BSP trees, as described by Bruce Naylor, see the pdf here. Although the technique allows a lot of freedom to destroy the environment, it requires an additional physics system to analyse if buildings need to collapse.
Finite element method
The Finite Element Method (FEM) uses continuum mechanics to simulate deformation and fracture. There are several ways of implementing FEM, either using explicit integration or implicit integration. Recomputing the stiffness matrix every simulation frame can be very expensive, and stiffness warping avoids this by using a corotational mapping. Such corotational FEM method is used by Pixelux Digital Molecular Matter (DMM) in Lucas Arts Star Wars games, as described in this github repository it is in the dynamics/corotational_fem folder, here is a screenshot:
Some researchers in Inria, France, accelerated FEM on the GPU using CUDA, and it could simulate 47k tetrahedra at over 200 frames per second on a modern GPU. Their source code is hidden in a SVN repository of the Sofa framework ( svn checkout svn://scm.gforge.inria.fr/svn/sofa/branches/Sofa-1.0 )
Breakable composit rigid body
Some games use a plain rigid body dynamics engine for destruction, such as Angry Birds, which uses the open source Box2d engine. In many cases you want more control over the destruction effect.
Here are some steps that describe the composite rigid body fracture method. First we prepare the geometry into fractured pieces and now we need to ‘glue’ them together. We need to create some connections between those pieces. There are several ways to do this. One way is to define connections between every piece and every other piece. This gives the most control, but the performance can be slow due to the many connections. Another way to compute connections is to automatically compute them based on collision detection: compute the contact points between touching pieces, and only create connections when there is a contact point. Then you can create a breaking threshold for those connections.
Once we glued the pieces into a single rigid body, we can perform the runtime fracture. If there is a collision impact, we compute the impulse. If this impulse is larger than a chosen threshold, we propagate this impulse through the connections. Those connections can be weakened or broken.
After this, we need to determine the disconnected parts, we use the union find algorithm for this, and then create new rigid bodies for each separate part. Of course the inertia matrix needs to be updated properly. In our open source Bullet physics library there is a demo that shows how to implement this, it is under Bullet/Demos/BulletFractureDemo.
Breakable rigid body constraints
We can also simulate the object by using a rigid body for each fracture piece, and connect the pieces using breakable constraints.
For example this can be a fixed rigid body constraint that connects two pieces. You can see that the object is bending a little bit after the collision, because the constraints are not perfectly stiff. This bending effect can be desired in some cases, and this method has been used in some games and movies.
Hybrid and other methods
It is also possible to use a combination of different methods. For example you can use FEM to determine when and where to break and use rigid body simulation to simulate the broken pieces as described in this paper (pdf).
If you have any experience or thoughts of fracture and destruction in games, please reply!