Opinion: Destruction

[In this reprinted #altdevblogaday-opinion piece, AMD physics engineer Erwin Coumans offers an overview of a recent course he organized on destruction and dynamics for game and film production, examining the simulation parts of breaking objects.] I recently organized a SIGGRAPH course on destruction and dynamics for game and film production and I want to give a quick overview of the topic. Actually it is a quick copy and paste of some of my speakers notes of the introduction, the course notes are not online yet. 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:

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. Voronoi Shatter 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. Tetrahedralization 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 Netgen, Tetgen and CGal for example. It is a complicated process, but there is also a much simpler approximation, explained in page 18 of the notes of the excellent real-time physics SIGGRAPH course. Boolean Operations 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: Real-time Booleans The Red Faction games by Volition showed some cool destruction in their worlds. Their Geo Mod technology is based on the application of real-time boolean operations. Recently I encouraged Stan Melax to open source his real-time booleans demo, so you can check it out at http://melax.googlecode.com. Here is a screenshot: 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 SIGGRAPH paper. I recently extracted an open source implementation from the Open Tissue physics library. You can grab the source code from my 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 Composite 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! [This piece was reprinted from #AltDevBlogADay, a shared blog initiative started by @mike_acton devoted to giving game developers of all disciplines a place to motivate each other to write regularly about their personal game development passions.]