Polygon Deformation
by Pat Wilson · in Technical Issues · 12/02/2000 (1:12 pm) · 5 replies
I've had about a billion ideas floating around of things I want to impliment, one that I really thought would be great is a fully deformable environment. After thinking, and having a 3dstudio epiphany, I came up with this solution. You know the binary operations you can perform with objects in 3ds max, most notably subtract, what if, say, for a c4 explosion, you did a binary subtraction algorithm using an invisable sphere that would simmulate the explosion radius, and subtract that from all the entities within the it's boundries. After thinking a little more I came up with an idea of how to possibly do it. The algorithm could do a test to see if a face on the explosion sphere was inside of the entity it was effecting, and then add that polygon into the polygon list for that entity. Wow, that was easy, I thought. Now here is the problem. What kind of data structure would work best for storing world data now? BSP tree wouldn't work because of the constant possiblity that the data inside it could be changed. I'm thinking just a linked list possibly? Right now this is just in the conceptualizing phase, so I haven't yet implimented this, I'm sure I'll have more ideas after I do, but I just thought I'd run this up the proverbial flagpole.
About the author
#2
12/03/2000 (8:39 pm)
Hmm, I took a look at a tutorial (term used loosly) on the Marching Cubes Algorithm that was linked to on flipCode. It gave me kind of an idea of what it is, but I'm not sure if that will help. It is quite possible that I don't fully understand what the algorithm does. 
#3
What you can do is build a cube with size N and divide it in (X^3) equal sized cubes.
Then, you set a floating point value for each of the vertexes of the sub cubes, where 1 means the vertex is part of the surface (wall). Then, knowing this, you use the marching cubes algorithm to really build the polygons that make up the world.
To make a hole with an explosion, you just have to decrement all vertex within the explosion radius by an ammount inversely proportional to the distance of the center of the blast... Then you recompute the walls...
This method works fine, as it is possible (by tweaking it a bit) to make certain areas imune to destruction. It's also easy to ensure good texturing and lighting...
And, best of all, it can be made pretty fast (except for the recomputation of the walls, it's pretty straightforward, and still it's faster than true boolean operations)...
I haven't implemented this yet in my engine, but I will as soon as I have time... It sounds like a very promising piece of code... :)
Just my 2 cents...
Diogo de Andrade
dgan@mega.ist.utl.pt
12/05/2000 (9:07 am)
Ok, let me try to be a bit clearer...What you can do is build a cube with size N and divide it in (X^3) equal sized cubes.
Then, you set a floating point value for each of the vertexes of the sub cubes, where 1 means the vertex is part of the surface (wall). Then, knowing this, you use the marching cubes algorithm to really build the polygons that make up the world.
To make a hole with an explosion, you just have to decrement all vertex within the explosion radius by an ammount inversely proportional to the distance of the center of the blast... Then you recompute the walls...
This method works fine, as it is possible (by tweaking it a bit) to make certain areas imune to destruction. It's also easy to ensure good texturing and lighting...
And, best of all, it can be made pretty fast (except for the recomputation of the walls, it's pretty straightforward, and still it's faster than true boolean operations)...
I haven't implemented this yet in my engine, but I will as soon as I have time... It sounds like a very promising piece of code... :)
Just my 2 cents...
Diogo de Andrade
dgan@mega.ist.utl.pt
#4
12/05/2000 (9:54 am)
After re-reading the document I found a few times, and reading your post I think I get a bit more of how this works. Basically what I'd be doing is dividing space up into a whole messload of little cubes. Then I'd test each cube for it's vertex status, if all 8 vertices are used then the cube is entirely in something, and so on. I'll see about implimentation. 
Diogo de Andrade
One thing you might want to check into is to use the marching cubes algorithm, where you go INSIDE the potential fields, instead of being out of them... There's a paper online somewhere (can't remember the location, nor the title) that talks about that... Do a search on "Deformable enviroments"... I'll try to remember to post the correct name of the paper...
Diogo de Andrade
dgan@mega.ist.utl.pt