Hive Assault: Implicit Modeling
Dynamic Modeling and Re-Modeling of Complex Surfaces
A Geometry Engine Flexible Enough to Model an Anthill... Automatically
Tao Ju, Andrew Iles, Chendi Zhang 2001.
Email: Tao Ju jutao@rice.edu
Email: Andrew Iles andrewi@rice.edu
Email: Chendi Zhang tenken@rice.edu
1. Implicit Modeling
Generally Speaking, the entire hive is represented by a single implicit function on a 3-dimensional grid of scalar values. The surface of the hive is the locus of those points with zero scalar values. The open space (i.e. space where players can move around) is represented by locus of points with negative scalar values, while close space (i.e., space occupied by rocks and earth) is represented by locus of points with positive scalar values. By specifying the initial scalar values on a 3D grid (of size 128 by 128 by 64, or 64 by 64 by 32), we are able to find the zero-surface by Marching-Cube algorithm, and extract polygons in each voxel that belong to the zero-surface to build the hive. So, the whole problem of creating interesting hive geometry is reduced to setting appropriate scalar values at grid points. As you will see, we incorporated subdivision and constructive techniques in the process of creating random terrain, fractal tunnels and various chambers.
2. Terrain Generation
The technique we used for random terrain generation is 3D fractal subdivision. We will start by discussing fractal subdivision in one dimension, or so called "Midpoint Displacement". Given the scalar value of two end points of a line segment, we repeatedly take the midpoint and divide the whole segment into two smaller segments. The scalar value at the midpoint is taken as the average of the scalar values of the two endpoints plus a small fractal noise. At the end, if we plot the scalar value of each point on the line as the height value, we will get a nice fractal ridgeline. If we do this on a two-dimensional grid (starting off with a square instead of a line segment and taking midpoints in two directions in sequence), we will produce a height map with heights varying in a fractal way. In fact, some most popular terrain generation algorithms, such as Diamond-Square Algorithm, are based on this technique. However, since these algorithms represent terrains by height maps, complex geometry such as caves and bridges cannot be represented. In our approach, we expand the idea of fractal subdivision to three-dimension. Imagine a cube with four vertices on the top having scalar value -1, and the other four vertices at the bottom having scalar value 1. Using fractal subdivision, we obtain a refined grid of size 128 by 128 by 64 with scalar values at the grid points vary from positive (near the top of the cube) to negative (near the bottom of the cube) in a fractal way. The final terrain is represented by the zero-surface of this grid of scalar values. By setting fractal noise to 0, we will get a flat surface in the middle of the cube. By increasing fractal noise, we can get more complicated terrain details such as caves, bridges, or even hidden closets that we can never see in traditional fractal terrains. In order to get satisfactory terrain geometry, as required by a good terrain generation algorithm, we need to be able to add control to the shape of the terrain. For instance, given a certain number of entrances to the underground world, we hope that these outlets open on hillsides. In order to make mountains at certain pre-defined positions, we can specify the scalar values for the first two or three rounds of subdivision process. We can also smooth out the jugged edges of the terrain by specify the fractal noise of the last one or two rounds to be zero.
3. Create Fractal Tunnels
The alien tunnels below the human level are constructed along fractal axes with varying width. Given the positions of two end points of the tunnel, the axis is created by performing mid-point displacement on the line segment connecting the two end points. We repeatedly take the midpoint of the segment and perturb it by some fractal noise (in three dimensions). The new segments are created by connecting the perturbed mid-point with the two original end points. Finally we get a sequence of perturbed points between the end points of the tunnel, and we connect them to be the fractal axis. Starting off from each of these axis points, we modify the scalar values of nearby grid points to be: distance to the axis ¨C tunnel radius. Thus a cylindrical tunnel can be constructed as the zero-surface of the scalar grid. The tunnel radius can be randomized in a similar way as the position of axis points. By distance propagation, we are able to carry out the calculations for each tunnel with blazing speed, regardless of tunnel size.
In order to connect the tunnels to other geometries in the hive, we use the union operation in implicit modeling. Whenever we need to modify the scalar value of grid point, we take the minimum of the original scalar value and the new value to be the modified scalar value of that point. In this way, we are always expanding open space in the hive structure.
4. Create Chambers
We use a similar technique to create chambers as we did in generating random terrain. However, we have a much wider choice of initial scalar values when we come to create chambers. Instead of assigning negative values to the top and positive values to the bottom, we can assign negative values in the center and positive values on the outside to make open space in the middle. By careful selection of initial scalar values, I am able to create smooth and dazzling chamber geometry of different kinds, as you can see in the game. In one of the storage rooms, for instance, there is a huge bulge hanging from the ceiling, supported by four columns at the corner. In the queen's chamber, there are four similar bulges hanging above the central platform, making it a perfect place for flag and bugs fighting. The choice of fractal noise is crucial in chamber creation. A slightly larger noise will drive every piece of geometry to wildness, and turn the whole chamber into a hell of flying rocks. Indeed, fractal noise zero will create nice smooth geometry that is necessary for the game.