This paper looks at the various methods available for the implementation of real-time deformation for use in computer game environments. We will analyse a number of published methods and we will examine how these methods can be used to produce real-time deformation in future game developments.

To computer game players, the environment in which they play is all too often no more than an interesting cage. In the real world our environment affects our actions. It would not be wise to sit in a chair made of paper. But in a computer game the distinction between visual properties and physical properties is not so clear cut. In the past this was due to the processing power needed to calculate mathmatical physics. Recently this barrier is being broken with the creation of programs like Math Engine which realistically model physics for games.
However one area of the gaming world still lacks representation. In the real world if you fired a missile into a stone wall, large chunks of stone would be ripped off the wall and scattered in the surrounding area leaving a hole.
The deformation properties of the real world have not been successfully used in game environments.

There are four main methods for building deformable worlds in games. These are height maps, voxels, polygon Constructive Solid Geometry (CSG) operations and implicit surfaces. In the following sections we will discuss the advantages and disadvantages of each method when used to produce deformations in games.

This method of deformation was used most notably about six years ago in "Starfighter 3000" (see figure 1). This game allowed the player to fly her space-ship around and shoot holes through mountains. Although the deformation was not vital to the game it made it more fun to play.


Figure 1: Starfighter 3000 uses deformable height maps.

A terrain model can be represented by a rectangular grid of quadilaterals. To generate this grid we need to store the heights of the grid vertices in an array of the same size, called the height field.
In the case of "Starfighter 3000" this was an array of 512x512 elements. The heights stored in this array can be altered at runtime, thus altering the shape of the terrain. For example, if the player shoots at a hill, the grid square where the missile hits has its height lowered and the surrounding squares have their height adjusted proportionally.
Each element of the texture map stores the colour that relates to the height of the corresponding element of the height map. This allows the program to work out what texture to use based on the height of the square. In the case of "Starfighter 3000" the grid squares were textured from snow to lake depending on the value of the element. The texture artist can add extra features (like roads) to the texture map.

A voxel is a point in space drawn as a pixel or small cube. Environments or objects can be defined by voxels. They are especially useful for creating natural or organic objects like landscapes and plants. Through procedural modelling voxels can display fractal and noisy patterns, immitating those found in nature. There are a few computer games that use voxel modelling to implement expansive gaming environments. These include the "Delta Force" series and "Outcast" (see figure 2) both being for PC. These two games were set in large outdoor environmets where voxels were used to create realistic grass and mountains. This is very hard to achieve using conventional polygon modelling techniques. When artificial objects (buildings) are modelled voxels are unifficient. In "Delta Force" the buildings were built from polygons.


Figure 2: Outcast uses voxels to represent its vast environments.

Voxels are memory intensive and difficult to model with. However voxels could simulate deformable real world objects better than any other modelling technique. A voxel is like a LEGO brick. To build a better representation of the real world requires more, smaller LEGO bricks. If a voxel object requires deformation (e.g. a hole made in it) we delete or move the voxels that define the space of the hole.
However creating geometric objects from voxels is inifficient. A sphere can be represented accurately as a polynomial (for example NURBS). Polygons can be used to approximate a sphere. However defining a sphere as voxels is unattractive. Imagine how many LEGO bricks are required to build a smooth looking LEGO sphere.
Ignoring the smoothness problem for now, how would we build a sphere from voxels. This question is answered by [1], the basic method being as follows.
Divide the sphere into horizontal slices and then convert each slice to voxels. To work out how far from the centre of the sphere each new voxel should be created pythagoras should be used (see figure 3). In OpenGL all the voxels would be stored as an array or linked list of three dimensional points. A draw function could step through the list and draw each point as a cube or sprite. When a hole is made in the voxel sphere, the points around the hole are deleted from the list. An extension of this affect would be not to delete those hole voxels but instead to animate them giving the effect of an explosion.


Figure 3: The pixels located for a circle of radius R = 8.

Further methods for the implemenation of Volumetric/Voxel CSG conversions are presented in [2].
To texture voxels an image map could be projected onto the voxels. Alternatively a procedural method could be used. The renderer would determine the voxels colour based on its position in 3D space.

Boolean operations can be performed on polygonal objects using a series of intersection algorithms. Using the method presented in [3] a polygonal object can be cut into or added onto using other polygonal objects.
Modern computer game enviroments are built from polygons. These polygonal worlds could be deformed using CSG operations, for example, to produce holes in walls. This method of deformation has not been applied in a gaming environment due to the processing power needed to calculate the boolean operations. However one game developer (Violition) is producing a first person game called "Red Faction" (see figure 4) which uses real time polygonal deformation. This CSG code is called Geo-Mod (Geometric Modification) and was written by John Slagel.


Figure 4: Red Faction by Violition uses real time CSG/Boolean operations allowing the player to shoot through walls. Note the hole in the pillar in this picture.

Due to the computer game companies not releasing the specifics of their code, it is impossible to say exactly how Geo-Mod works, however it problably uses a method similar to that presented in [3] . This is as follows.
Given two objects, object1 and object2, each face of object1 must be compared with all the faces of object2 to determine what portion of this face lies inside object2. This is repeated but with each face of object2 compared against all faces of object1. Then the required parts of these faces are kept depending on what sort of boolean operation is being performed, thus creating the new modified object.
A face_to_face_intersection algorithm determines where new vertices are to be created. These are topologically sorted. To determine how two intersecting faces are to be divided for the face_to_face_intersection algorithm an edge_to_face algorithm is required. Using the plane equation (a.x + b.y + c.z + d = 0) to represent the polygon/face we can determine where the point of intersection lies along the tested edge. We must also check that this intersection point lies inside the polygon by projecting the edge onto the polygon.

An implicit surface is a surface defined by a density function. A polygonal sphere requires a list of vertices to define its surface but this only gives the surface to a fixed resolution. Using an implicit surface, we would only need the sphere's centre and radius to calculate if a given point is inside or outside the sphere.
The implicit surface function of a sphere with radius r and centre C is:
(P_x - C_x)² + (P_y - C_y)² + (P_x - C_z)² - r² = 0
where P is the point to be tested. The function returns a density for the point P, where negative values are inside the surface and positive values are outside the surface.
An implicit function can be used to describe any surface. This can be as simple as a sphere or as complexed as a human figure (see figure 5). However implicit surfaces are suited to describing curved surfaces and not to geometric objects like buildings.


Figure 5: This torso was built entirely from implicit functions (see [4]) which are blended together to produce the smooth surface. This process of blending implict functions is sometimes called blobby objects or metaballs.

A game world could be built from implicit surfaces. At present the calculation of implicit surfaces is slow. However an implicit world would be entirely dynamic and deformable. Walls could be allowed to flow and bend. Holes could be removed from any object within the world and liquids could flow across undulating surfaces. Considerable work has been done by Marie-Paule Cani [4]&[5] on the subject of modelling and deformation of implicit surfaces in real-time applications.
But how could implicit surfaces be rendered? One method would be raytracing. If the ray passes from inside to outside of the implicit surface at a given point then the surface must be drawn at that point. This method would produce a very accurate and smooth surface but at present is too slow for use within a game engine. Another method of rendering the implicit surface is polygonization.
The best method for the polygonization of an implicit surface was presented by Jules Bloomenthal in [6]. First the space around the implicit surface must be broken down into cubes. This can be done in two methods; continuation and exhaustive search. Continuation means that a starting point is picked on the surface. Then cubes are created away from the starting point along the surface. Exhaustive search methods break down space fully into cubes (for example the marching cubes algorithm). [6] uses the continuation method as it requires O(n²) function evaluations whereas exhaustive search requires O(n³) function evaluations (where n is a meausure of the size of the surface). Exhaustive search requires the evaluation of a volume (n cubed). Continuous search requires the evaluation of a surface area only (n squared). However exhaustive search may produce a more accurate polygonization if the surface isn't continuous. For example if parts of the implict surface have become disconnected, the continuation method would not find these. The exhaustive search method would find the disconnected pieces as it breaks down all of the space occupied by the surface into cubes, including the gaps. (see figure 6)


Figure 6: This implicit surface produced in [5] uses the marching cube algorithm to break down the implicit surface into cubes for polygonization. However it only breaks down areas that have been modified, thus speeding up the process of decomposition.

Then these cubes can be broken down into tetrahedra if a more accurate surface is required. However the tetrahedra method is slower as it requires more function evaluations.
All the edges of the cubes/tetrahedra are tested against the surface to determine the point of intersection with that edge. This is done using binary subdivision with a fixed number of iterations. Binary subdivision finds the intersection point by taking two points known to lie either side of the surface (the two ends of the tested edge). Then these points are subdivided and the halfway point tested to determine if it is inside or outside the surface. This new point is then taken with the opposite end and the edge split again. This is repeated until the edge has been split enough times to give a fairly accurate approximation of the intersection point. This intersection point determines where a vertex should exist for that particular edge. All the vertecies determined for a cube/tetrahedron are joined up to form a face and stored in memory. This list of vertecies can be drawn by a seperate function.

Given the four methods of deformation outlined above, which would be the best for producing a deformable world in planets3D.
If a height map was to be used then the height information in each array element would represent the distance of that point from the centre of the sphere/planet. If a point is hit by a missile, the height of that point is lowered. This method would allow for some very interesting planet texturing. A point's position, relative to the planets surface is contained in the height field. This could be easily translated into texture co-ordinates. The planets could have different coloured internal layers.
The main disadvantage of using a height map in planets3D would be that as a point's height gets lower it will eventually be pushed out through the other side of the planet (see figure 7).


Figure 7: If a surface point is displaced too far it passes out of the far side of the sphere.

To produce holes that pass all the way through a planet using height maps would require a cutting function. This would edit the planet vertex list to delete vertices that had been displaced all the way through the planet. Then new vertices are added where required on the opposite side of the planet thus forming a 'tunnel'.
The CSG method of deformation would be implemented with simple spheres. The boolean operation would be performed on the planet object and a hole object. This hole object would probably be a sphere but could be any shape. The speed of the CSG operation is determined by the complexity of the objects used to perform the boolean operation.
The benifit of using polygonal deformation with the method outlined above is that the game world can be built using a traditional 3D modeller (for example Maya). However as planets3D is built from spheres, polygon deformation may be overly complicated. There is a more appropriate alternative.
In planets3D each planet could be defined as an implicit sphere. If a hole is added to the planet then a negative implicit sphere is added to the total implicit function of that planet. The user can go on adding holes and consequently implicit spheres as required.
planets3D uses implicit surfaces to define the deformable planet objects. The player can shoot holes into and through the planets. They are then re-polygonized when hit. Implicit surfaces would not be the best method of producing a fully deformable game. They are suited for blobby, clay-like objects and not rigid, simple objects like walls. However the polygonization code has already been proven to work and is robust. It is therefore perfectly suited to puting holes in spheres for planets3D without much extra work (although special thanks to James Fletcher [7] who updated Bloomenthals code [6] to use the object based features of C++).