Marching Cubes Simulating a Volumetric Destructible Environment
This was a project that I had wanted to do for years. I was
always disappointed when upcoming games would claim to have Fully Destructible
Environments, only to allow very specific objects to be destroyed. I went
in search of a technology that would allow a large scale world to be completely
destructible, allowing the player to do things such as tunnel through the world
or create massive craters. Something like tunnelling could never be
accomplished by using more common approaches, such as using a heightmap, so some
more exotic algorithms were required.
The first potential technique that I came across was something called CSG
(Constructive Solid Geometry). CSG is commonly used in things like 3D
modelling programs and many level editors in order to merge separate 3D models
using several different methods. One of these methods is a perfect
simulation of a destructible environment and was actually used in the Red
Faction series on the Playstation 2. CSG has one major drawback however:
the more destruction that is caused, the more memory that is required.
Because CSG has to re-triangulate meshes when merging them, after several merges
you may end up with tons of triangles in very small areas. This, combined
with the fact that CSG uses increasingly expanding trees to merge objects, means
that after a short while you would start to experience a serious performance hit.
Though CSG would provide the most versatile destruction, I wanted something that you could potentially blow up and
recreate forever with no performance problems.
Marching Cubes was the answer to this problem. It is actually a very
simple concept but sometimes can be hard to get at first. It can be
described as polygonizing a scalar field, or in less technical terms, turning a
3D grid of points, each containing an arbitrary value between something like 0
and 1, into a 3D model. The value that each point contains can be thought
of as the health or hitpoints for that particular point in space. Now how
do we turn that data into a 3D model?
There are two methods that can be used to do this, one with interpolation and
one without. Since it's easier to grasp how the non-interpolated method
works, I'll focus mainly on that. In this method our scalar values at each
point are limited to being either 0 or 1, rather than any value in between.
This means that each point can either be empty space or land. The geometry
that is generated is based on the area inside each set of 8 points, also known
as a cell. Using some nifty bitwise manipulation, the values of these 8
points can be turned into a single number. The resulting number, also
known as the cell's "case", is used as a lookup into a table that stores the
relative location of the vertices for that cell. Because there are 8
points which can each have one of two values the total possible cases is 2 to
the power of 8, or 256 cases.
This is all probably difficult to picture if you're not familiar with the
technique. It's much easier to grasp in 2D so here's an illustration of
the Marching Squares cases, conceptually the same as Marching Cubes only in 2D.
When an explosion occurs, each point in the vicinity of the explosion is checked
for an intersection with the blast radius. If the point is inside, its
value is set to 0, thus destroying the geometry in that area. Of course
this can also be used in the opposite way just as easily to create land, which
also lends itself to some interesting gameplay mechanics.
There is a lot I didn't cover in this explanation so if anything is unclear or
if you are interested in more details such as interpolation or optimization,
feel free to email me with questions.
