Hive Assault: Destroyable Geometry
Making Destroyable Environments
A Robust Method for the Dynamic Construction of Implicit Modeling Surfaces
Derek Ruths, 2001. Email: druths@rice.edu
VOXELIZATION
Many of the advanced features in Hive Assault heavily depend on the underlying mathematical representation of the 3D terrain. Fast collision detection, real physics, fluid flow simulation, and artificial intelligence all require special attributes and data structures which can only be provided by voxelization. In this section, we will discuss how the terrain is mathematically represented, leaving detailed discussion of its specific application to other sources.
The fundamental idea behind Hive Assault's terrain representation is implicit surfaces. Implicit surfaces are characterized by an equation which produces a surface when all zero solutions are generated. A simple example of this is the unit sphere: x^2 + y^2 + z^2 -1 = 0. The set of all solutions (combinations of (x,y,z) that satisfy the equation) describe the surface of a sphere, with radius 1, centered at the origin. Contrast this with an inequality such as x^2 + y^2 + z^2 -1 < 0. This formula describes a volume which is inside the bounds of a sphere of radius 1 centered at the origin. I provide this counter example only to emphasize that an implicit surface can be understood as a formula containing an equality. This equality lets us solve the equation and generate a set of solutions which can be graphed. This graph is always a surface.
Within computer graphics, the most important subset of implicit surfaces are those which exist in 3D space. The example implicit surface we just saw was extremely simple. In fact, within the context of gaming, we would characterize it as absolutely boring. A surface that simple would, by itself, contribute very little to an interesting environment. Consider the complexity of the equation that would be required to generate anything interesting - such as a hive of interconnected tunnels. This problem is complex enough that another whole team was dedicated to producing such functions.
The problem we are left with is how to graph these functions. Very critical to accomplishing this is the question how we represent these graphs. In computer science, we frequently favor using discrete models in order to avoid the inherent space and computational complexity of grids with the resolution of real numbers. This is one case where discretizing 3D space will immensely simplify the problem: we start with a 3D grid. The aforementioned function-evaluation-team provides a real number for each grid point - a number which corresponds to the value of the function when evaluated at that (x,y,z) location.
Taking our sphere example, we have the function x^2 + y^2 + z^2 -1. The grid point (0,0,2) is given a value of 3 since 0^2 + 0^2 + 2^2 - 1 = 3, while the grid point (0,1,0) is given a value of 0 since 0^2 + 1^2 + 0^2 - 1 = 0.
Now we have a grid of numbers representing the value of the function sampled at different points in 3D space. Next we need to identify the zero surface - that is, we need to create vertices in this grid which represent where the function would be equal to zero. Since we discretized the grid, we can't depend on just finding the zeros at grid points - most zero solutions won't be on grid points. This is where we can use voxelization.
Voxelization is a technique which uses the fact that zeros of functions occur between points on a grid where at one point the function is positive and at the other point the function is negative. This theory is used to find zero surfaces in 3D volumes by making the fundamental unit of examination a Voxel - one cube taken from the grid.
As described above, there is a function value associated with every point on the grid. Consequently, a voxel is a cube with a function value associated with each of the six vertices. A cube is created by drawing straight lines between vertices on the same faces. We'll call any two vertices on a cube connected when they are attached by a vertical or horizontal line composing part of a face. If the values of two connected vertices are opposite in sign, then a zero lies between them. Where does it lie? We can only estimate using numerical methods. In my implementation, I used linear interpolation - although any other reasonable technique could be used. By applying linear interpolation, we can approximate the location of the zero in the grid. This becomes one point on our surface. If we carry this process out for every set of connected vertices in every voxel, we can generate a pretty good approximation of the surface.
Of course, if we carry this process out for every set of connected vertices in every voxel, we'll also end up with a very slow algorithm. As a brief note of mention, we can optimize this 'voxelization' process by creating a pre-computed look-up for all the possible cases - all the possible different sign configurations a voxel can have. This means that all we have to compute is zero intersections where the definitely exist, rather than first determining if they exist.
At this point, we have successfully generated a list of points lying inside the grid which satisfy the zero surface of the original function. Since we need to transform this into graphics, the next step is to polygonize this surface. Since we already have the zero points for each voxel, all we have to do is group these into polygons. We place a special restriction on the polygons we generate - that they all be convex. This accelerates collision detection by allowing collision detection to be performed only on grid boundaries yet keep collision results accurate between grid boundaries (see the discussion of collision detection for a detailed explanation of how this attribute was used).
DESTRUCTIVE GEOMETRY
A unique and unprecedented feature which is implemented in Hive Assault is Destructive Geometry - the ability to dynamically modify large pieces of the terrain (freely chosen by the player). As difficult as this may seem at first, voxelization actually makes implementation quite easy. Since polygonization is largely voxel based, and since the surface is generated on a voxel by voxel level, we can easily change one voxel and not worry about the effects it will have on other parts of the grid. Therefore, we are confident that we can apply changes to the grid and only deal with the ramifications locally.
Also recall that the location of the surface is determined by the values at grid points. We can change the surface by changing the values at the grid and repolygonizing those voxels as we did to generate the polygons in the first place.
Consequently, voxelization makes destructive geometry wonderfully recursive - employing the same methods that would be required simply to polygonize the mesh in the first place.
As a final example, consider a game using voxel representation in which the user could detonate explosives which have a spherical blast. Assume that negative numbers in the grid represent closed space (rock, inside of walls, places where the player can't go in general), and that positive numbers represent open space (places where the player can go). Between these positive numbers (open space) and negative numbers (closed space) lies the zero surface. Our polygonization routine renders this surface for viewing. If the player detonates a spherical explosion inside the grid somewhere, what happens to the grid? Intuitively, an explosion should create more free space - it's going to blow away some of the wall. Therefore, we expect to see more positive numbers (free space) in the grid after the explosion. This means that we need to make some of the negative numbers positive. We do this by adding to all the numbers in the grid spatially surrounding the location of the explosion. Since the explosion is spherically symmetric, we add the numbers symmetrically around the explosion location. Once we have manipulated the grid's values, we delete the polygons currently associated with the voxels that were manipulated and regenerate (from scratch) the polygons for them. This geometry will reflect the new grid values - which in turn reflect the modifications the explosion made to the geometry.