Abitrary Damageable Convex Volumes

Part of this project involved the creation of objects that could be destroyed in an arbitrary manner. Conventional games either allow only animate objects to be destroyed-- holding the background inviolate, or have created pre-programmed destruction sequences. Both of these methods limit the movement of the player to the preset areas. Even with preprogrammable destruction, there will be some areas of the world the player can't destroy. Another unrealistic effect of preprogrammed sequences it that they always will break in the same way. Arbitrary destruction allows the flexibility of allowing the player to destroy anything (eventually) and go anywhere they want assuming they don't die along the way.

The implelementation of arbitrary destroyable volumes maintains one invariant-- that the volumes are always convex. Destruction is done therefore by breaking the existing volume into some number of new volumes, and removing the "damaged" volume. The goals of our arbitrary destruction algorithm were to:

Allow arbitrarily sized damage areas

Allow damage at any physically possible orientation and location

Allow damage to propagate through the volume in any manner

For damageable objects to be entirely destroyed when a certain critical mass or stability had been destroyed.

The implementation thus far, has achieved the first of the goals. Damage at any location is also possible, but damage at any orientation remains untried. The theory and infrastructure is there for the remaining goals, but remains unimplemented at this time due to time constraints.

Implementation

Entrance to the damage code is permitted once per logical time step. Damage that occurrs at both the top and bottom (or any two or more faces) of a volume by a single object will only cause the volume to be damaged once. If multiple objects hit the destroyable volume during the same instant, only one may be processed and the remaining collisions have to be queued until the next time step. A logical time-step in a synchronous system this would correspond to once per frame- however as the SGI Onyx 2RE upon which our application is based runs the display processes in parallel such a correspondence does not actually exist. Thus, it is possible that the damage will only become apparent after several frames have passed. Any lag that is visible should be covered by the explosion that occurrs upon damaging any object.

The interface of the damageable convex volumes is the face. When collided with, the physics module will call the damage function on that face. The face then creates a damage region of a size based upon the magnitude that is passed in by the physics module. In the example below, we see a face that has been damaged exactly once and has been colored so that each of the polygons that make it up are visible.

The volume is first split into 5 volumes, leaving a square hole in the center. The first part of this process is to split the volume by a plane to the right which creates the aqua-marine colored volume. Then a split to the left creates the pink and purple section, leaving the yellow and green mddle section. The division by a horizontal plane above and below creates the first such actual hole and makes the yellow volume and greenish volume separate. This process is repeated at the same point with a damage hole roughly the same size rotated 90 degrees. As can be seen, each remaining volume is split again.

The problem of splitting a volume may seem trivial. But due to the information neede by the algorithms used to create aribitrary damage, the structure,creation and maintenance of the information about the volume is very complex. For instance, each edge knows the two points that make its end points, the two faces that it belongs to, and any edges that it immediately adjoins. Thus when a damage blast lands near the edge of a volume that adjoins another volume (the yellow volume above for instance is sandwidched between the pink and aquamarine volumes), the damage blast can be propagated past the edges of the existing volume into others.

But even drawing a face now is complicated by the need to draw the face in proper counter-clockwise order so that backface culling can be done. Each point must be made in the proper order which can be done by ordering the edges. However, within an edge there are two points, one of which is redundant-- but due to the geometry of the situation it is not apparent which one that is. This information, as well as edge adjacency, as well as which volume owns the edges, etc. must all be properly changed, updated, and created when a volume is split.

It is possible to create damage that removes entire volume elements in an aribtrary fashion for some devastating effects- as can be seen below. The colored images show the actual convex volumes used to represent the remainder. The first set of damage images shows only a third of the damage of the second set.

As can be seen, there is yet some work to be done. There are unconnected elements that are floating in space. These can be removed when the following problem is solved by using a connected component algorithm. There is also not yet a way to propagate damage through space-- the damage on the left side of the view volume ends only a tenth of the way along the volume where the damage hole on the front face furthest to the left first split the volume. This problem can be solved by linking adjoining faces in a manner similar to the damage edges. Thus, damage will be able to spread depthwise as well as breadthwise across the volume.

Work is being done to fix the last of these problems so that a complete solution is available.

Code:

This link is to the C++ code that runs independently of the application and that was used to create the damage volumes. The implementation uses the SbVec3f class from Open Inventor to implement vectors-- though only standard operations are used so this class could easily be replaced. The actual damage code is 5000 lines long, including whitespace and comments, but not including the helper code that makes it possible to view the created volume.

Volume creation is not simple either-- there is alot of information that needs to be created. The program does the complex process of maintaining the data thereafter. The main program that can be used to view the created volume(s) is "DHandlerTest.c++" located in the testing directory. For more information which will undoubtably be necessary, please contact: jmccune@cs.cornell.edu.