Messages

1

Coding / Re: Destructible Terrain

« on: February 08, 2010, 03:39:51 pm »

Good news I think, from http://www.opengl.org - the Cafu source is available under GPL. Pretty powerful engine, and seems to allow real time material editing, possibly another solution to the problem of destructible objects? Here's a link - hope it's not broken: http://www.cafu.de/

They also have a world editor and other tools ready to use. Worth checking out imo.

2

Coding / Re: Destructible Terrain

« on: February 06, 2010, 03:14:23 pm »

Computing Dynamic Changes to BSP Trees
Y. Chrysanthou M. Slater
Department of Computer Science, QMW Uniaversity of London, Mile End Road, London El 4NS, UK. e-mail: yiorgos@dcs.qmw.ac.uk, mel@dcs.qmw.ac.uk
KEYWORDS
Binary Space Partition (BSP) trees • SVBSP • dynamic modification • 3D graphics
ABSTRACT
Abstract
This paper investigates a new method for dynamically changing Binary Space Partition (BSP) trees. A BSP tree representation of a 3D polygonal scene provides an ideal data structure for rapidly performing the hidden surface computations involved in changing the viewpoint. However, BSP trees have generally been thought to be unsuitable for applications where the geometry of objects in the scene changes dynamically. The purpose of this paper is to introduce a dynamic BSP tree algorithm which does allow for such changes, and which maintains the simplicity and integrity of the BSP tree representation. The algorithm is extended to include dynamic changes to shadows. We calibrate the algorithms by transforming a range of objects in a scene, and reporting on the observed timing results.

DIGITAL OBJECT IDENTIFIER (DOI)
10.1111/1467-8659.1130321 About DOI

3

Coding / Re: Destructible Objects

« on: February 05, 2010, 06:14:17 pm »

The cube engine looks like an even better option simply because it's well documented and has a large community. What do you guys think? There is also an interesting paper on dynamic BSP trees:

http://www3.interscience.wiley.com/journal/120705748/abstract?CRETRY=1&SRETRY=0


I haven't read it yet, but will (again, this weekend...). It's old (2003) but may contain some useful info.

4

Coding / Re: Destructible Objects

« on: February 05, 2010, 02:30:58 pm »

http://www.thermite3d.org/

Ok, well since the link I gave was broke (I've tried to repost it above), I'll paste a quick description from the site:

How Thermite Works
Most 3D game engines store their world as a collection of polygons, and in fact this is so common that you could be forgiven for thinking that this was the only way that a virtual world can be represented. For example, a simple room in a game world might be made up of six quadrilaterals, one for the floor and ceiling and one for each of the walls. In this representation we are essentially storing the surfaces which exist in the world because, most of the time, this is all we are interested in. We store the information that tells us what pattern is on the surface (texture), but we do not store any information about what is immediately behind that surface (brick, plasterboard, etc) or about what is in front of it (air).

For many purposes this surface representation is sufficient. It allows for detailed environments and efficient rendering by dedicated graphics hardware. However, its main drawback is that it is inherently rather difficult to modify at runtime. Imagine we wish to have an explosion blow a hole in one of our walls. This means we need to remove the polygon representing that wall and compute a new set of polygons in the shape of a hole. This process is known as Constructive Solid Geometry (CSG) and is a difficult thing to accomplish (though by no means impossible, as shown by the Red Faction 1&2).

Thermite3D does things very differently - instead of using polygons it uses a volumetric representation of the world (via the PolyVox library). This means it breaks the world into a 3D grid and, for each point on the grid, it stores what material exists there (rock, wood, air, etc). Each element on the grid is known as a 'volume element' or voxel. Figure (a) shows the idea:
 



The advantage of this representation is that it is very easy to modify at runtime. If you wish to destroy the world at a given point in space then you can simply change the material of all voxels within a given radius from being 'rock' to being 'air' and you have a hole. Of course, it's just as easy to go the other way and create material out of air, or even to just switch one material for another. There are no complex calculations and it is conceptually very simple. Figure (b) shows our room again, this time with a hole in it.

Of course, given this voxel world we still need some we of rendering it. There are a few options:
 
Use Raycasting: Raycasting is a computer graphics technique which involves tracing virtual 'rays' from the camera position into the scene. For each pixel on the screen, a ray is traced until it hits an object at which point lighting and shading calculations are performed to determine the pixel colour.
Render individual voxels: The voxels representing materials other than air can be rendered using graphics hardware. Each voxel could be displayed as a point sprite, or even as a cube mesh (though this would be costly).
Extract surface: An algorithm (known as Marching Cubes) is used to convert the volumetric representation into a conventional polygon mesh. This can then be rendered in the same way as any other geometry in the scene.

Needless to say, there are many trade offs to be considered when choosing one of these approaches. The underlying PolyVox library uses the surface extraction approach which allows it to integrate easily with existing 3D engines. When the world is first created PolyVox generates an initial mesh. When the world is then modified, the 3D engine simply requests new geometry for the appropriate region.

PolyVox is an Open Source (ZLib) library for storing volume data and for extracting isosurfaces for rendering. It is primarily designed to be integrated into a game engine as a method of providing fully dynamic geometry (this is how it is used in Thermite3D) but also has other applications in scientific and medical visualisation.

Its features include:

Storage:
Support for large volumes.
Memory efficient internal representation.
Fast read/write access to modify volume in memory.
Serialization routines provided.
Templatized on voxel type.
Surface extraction:
Fast implementation of the Marching Cubes algorithm.
Support for Level-Of-Detail meshes.
Allows different material types.
Automatic computation of surface normals.
Architecture:
Written in standard c++.
Cross platform (Windows and Linux).
No dependencies beyond standard library.
Bindings available to other languages.
Graphics API independent.

The PolyVox library's source is available, which should be all we need, unless I'm grossly mistaken. You don't need to replace your engine. That's what I'm trying to compile at the moment. Have been busy with work, but will actually look for a solution this weekend.

5

Coding / Re: Destructible Objects

« on: February 04, 2010, 02:25:29 pm »

Did you take a look at the link I posted above? I've run into a compile problem and waiting for some help from the developers so I can proceed.

6

Coding / Re: Destructible Objects

« on: February 04, 2010, 11:29:46 am »

I know that routing and lighting are pre calculated at the moment, I don't really have anything to say about it at this stage. Art work wise, it seems like you can avoid having to do a lot of it if you settle for functionality over visuals to start with. It doesn't have to all look amazing to begin with. Most if not all of the current artwork will be reusable, and to make things look nice you will probably need a few extra things per material type (if that).

I'm interested in looking into the problem.

Edit: I've done a little bit of looking around and the most interesting thing I found so far is this - http://www.thermite3d.org/joomla/index.php . Seems like a better way to store maps for destructible environments, and they claim good performance and as far as I can tell, require no pre-compilation of maps. Trying to compile and get  a working sample of this.

Based on this idea it would seem that you need little to no extra artwork, unless you want some complex animations for when materials are destroyed.

7

Coding / Re: Destructible Objects

« on: February 03, 2010, 12:24:17 pm »

I'll try to be on there when I can.

8

Coding / Re: Destructible Objects

« on: February 02, 2010, 06:21:34 pm »

Well, I don't want to make big promises, but I would like to take a look at the root of the problem.

9

Coding / Destructible Terrain

« on: February 02, 2010, 02:25:59 pm »

I'm sorry to bring this up again, but I'd like to understand the real cause for your inability to produce destructible environments. I have seen the func_breakable, but that doesn't really seem to be a viable solution for creating an entirely destructible map. As far as I could understand it's more of a way to add some destructible objects.

I know next to nothing about the project, but I have tried the game under linux and I have to say that it's very good. I don't have an immense amount of free time on my hands, but I've done a good bit of c/c++/python/java/opengl coding and wanted to consider developing a solution to this particular problem, that I find most interesting.

As far as I understand the graphics engine being used is a heavily modded version of the Q2 engine (please correct me if I am wrong). I've also read that inability to create destructible environments is buried somewhere in the engine. Clearly it's possible to rewrite the engine code as needed and retain backwards compatibility, at worst through an additional abstraction layer.

Basically - someone point me in the right direction to start looking at possible solutions to this problem. That probably includes engine source that you use (which is probably there, I just don't know where). Thanks.