Destructible 3D Environments

From PagodaWiki

Contents 1 Introduction 2 Status 2.1 General Partitioning and Triangle Splitting 2.2 Problematic Cases 2.3 BSP Ray Intersection 3 Project Proposal 3.1 Abstract 3.2 Introduction 3.3 Problem 3.4 Literature Search 3.5 Proposed Solution 3.6 Proposed Design

Introduction

Think Red Faction. Shoot a wall, it explodes, chunks go flying, and then you can walk through the hole that you have left permanently.

Status

General Partitioning and Triangle Splitting

Testing the capabilities of the BSP routine to choose the best partitioner of a non-convex set, split the polygons needed, and recursively partition until leaf nodes are created.

Problematic Cases

I ran into most of my issues with the polygon splitting routine. Most of them I determined to be issues with floating point precision, which were then obviously solved by thresholding whenever I tested vertex positions relative to one another, planes, and lines. The map below (screen capped from Maya before I brought it into my application) was a simplified case that helped me to figure out why certain polygons weren't getting pushed onto corresponding leaf node sets. The few polygons in the corner of the image show a case where my routine to test for a convex set failed because all polygons resolved to be behind one another rather than in front.

This is one of the maps I'm testing, which is just bumpy terrain with a cave. Although I do have Phong implemented in GLSL, I'm keeping things flat shaded by using the face normal for all of a triangle's vertices. If I were to smooth shade it, things just look terribly soft. Plus it's easier to see what is going on when normals aren't interpolated between vertices. At this stage the map is being drawn from a correct BSP (as far as I have tested at least).

BSP Ray Intersection

I was able to get ray intersection with the BSP to work. It allows me to do many things, such as select a triangle, shoot at a triangle, etc. This was ultimately needed to allow me to set a trajectory for whatever was going to create the blast when it hits a wall. It ended up uncovering an issue with my BSP implementation. Because I hadn't been pushing the dividing triangles down the positive child tree of a node after being used as the partitioning plane, I have to special case everything such as explicitly drawing partitioners and checking them for ray intersection. Ideally, although a reference to the partitioning polygon of a node is made, they should be treated like regular polygons in the end and also be contained within the convex polygon sets of leaf nodes. At the moment if I try to push the partitioner to the positive set and send it on its way, the program crashes.

At any rate, here is the cave map again with some holes knocked in it. Red signifies partitioner polygons (there are a lot because the scene itself is horrible and resulted in a lot of slivers) and the other color is everything else. The holes are a result of me clicking on a polygon. I could have turned them green for the sake of a visual cue, but I decided to remove them, so don't think this is what I call a blast radius. That will come in time.

Here the craters are half-working. I can make a blast hole, but not keep the "bottom" of the crater in tact.

Project Proposal

Abstract

The ability to modify a game environment in realtime can be powerful and rewarding for both players and game designers. It brings many new elements to gameplay that are not available when a level is static. All in all, there have not been very many attempts at integrating this feature into game engines because it is computationally expensive. By using tried and true BSP tree merging algorithms alongside the more recent technological advancement of geometry shaders, it may be possible to significantly increase the speed at which such engines run.

Introduction

One of the driving forces behind the field of computer graphics is interactive video games. Players always wants to be able to do more in a virtual world, and developers desire to push the limits of technology in order to create a more immersive experience. A destructible 3D environment is one in which the player can modify pieces of the world around them; whether this be through the effect of a simulated explosion during gameplay, or a tool provided for the purpose of level editing. The game Red Faction, by Volition, Inc., displays one of the earliest successful implementations of such an engine. The two most used methods that can be employed to get this effect are constructive solid geometry and binary space partition tree merging.

Problem

The main reason that only a select few games have been able to include a destructible 3d environment in their engine, and the reason that these engines always have noticeable limitations is that such operations become large and complicated very quickly. Each time a new section in culled out of a piece of geometry, numerous new vertices and faces are added to the object. For example, a simple plane, after having an explosive detonated its surface of one face might become a crater of twenty faces. The next time a similar explosion occurs here, we have twenty more faces to intersect. Polyhedral set operations done with BSPs are known to be too intense for hardware, although with the advent of geometry shaders, a technique that allows primitive shapes to be generated from the original ones sent to the beginning of the graphics pipeline, it may be possible to hardware accelerate certain aspects of the destructible environment algorithm.

Literature Search

Ranta-Eskola, Samuel. "Binary Space Partioning Trees and Polygon Removal in Real
          Time 3D Rendering." Diss. Uppsala U, 2001. Gamedev.net. 19 Jan. 2001. 11
          Mar. 2009 <http://www.gamedev.net/>. Path: reference/programming/
          features/bsptree/bsp.pdf.

This master's thesis talks about the basic theory and implementation behind BSP trees. It goes into detail about using BSPs for basic visibility priority, hidden surface removal and collision detection. These are all things that go hand in hand when using BSPs for 3D environments. By maintaining the BSP data structure, it can be applied to several parts of the engine and provide speed increases, as opposed to calculating the elements separately.

Naylor, Bruce, John Amanatides, and William Thibault. "Merging BSP trees yields
      polyhedral set operations." ACM SIGGRAPH Computer Graphics 24 (1990):
      115-24. ACP Portal. The ACM Digital Library, New York. March & april 2009
      <http://portal.acm.org/citation.cfm?doid=97880.97892>.

The paper explains how certain routines performed on BSP trees can set them up to be merged and yield a new BSP tree updated to contain the added or subtracted geometry that resulted from a boolean operation.

Geiss, Ryan. "Generating Complex Procedural Terrains Using the GPU." GPU Gems 3.
          Ed. Hubert Nguyen. 3rd ed. Boston: Addison-Wesley Professional, 2008. 7-37.

Although this article deals with procedural terrain generation, it discusses how to use geometry shaders to create additional topology on the GPU. The author talks about how to calculate the generation of polygons within a specified space, which becomes useful when intersecting a blast radius with a plane. It also talks about collisions of foreign objects. This is key since one has to decide how dynamic objects will interact not only with static geometry represented by the BSP, but also how to transform newly added polygonal detail back out of the graphics pipeline and into the engine's environment model.

Proposed Solution

Working to increase a BSP tree merging algorithms would be a hefty task, and quite out of the league of my skill set. My solution, however, seeks to use technologies that were not available on graphics cards when games like Red Faction were first made. If parts of a destructible 3D environment engine can be optimized with geometry shaders, I believe that significant speed increases can result. Furthermore, there has been research done to use hyper-textures and procedural 3D textures to store pre-computed material breakage data, and with this data derive better, more realistic polyhedron boolean operations.

Proposed Design

I will use Objective-C and Cocoa to build an application with an OpenGL graphics context capable of displaying the results of my destructible 3D environment engine on Mac OS X. A user can then load a level created in a 3D application such as Autodesk Maya, wander around and modify the environment with various tools. C++ classes will handle most of the computation, such as BSP tree creation and routines. Although the project is about exploring speed increases using geometry shaders, I cannot realistically compare my engine, which only performs environment destruction, to a full engine such as Red Faction's. Any game engine is not only going to be better implemented by a team of professionals, but it will also support many other features. The only real benchmark I will have is to compare speeds before and after GPU optimizations of my own program.