Hi all!

I need your help with understanding of base concepts of destructible environment creation.

A little background. We build a 3D turn-based grid-based game in Unity, in which we want to achieve almost full environment destruction - walls, buildings, interior objects etc. (like old X-Com games but full 3D). This also need to allow partial object damaging (aka object hp). Also, our game would involve free aiming feature, so static fracturing may be a little off visually.

So, we've decided to try dynamic real-time mesh fracturing approach. As I understand from viewing a couple of resources on this topic, common method of dynamic fracturing involves Voronoi diagrams in some form. However, all approaches that i've seen lack some detail or I can simply have no needed background for understand it.

Here is how I understand pipeline right now, step by step:

1. Generate a set of seed points inside mesh, which will be centers of Voronoi Diagram cells. It must be relatively easy, using impact point, force and some kind of predetermined “fracture pattern”, like Perlin Noise etc.
2. Create Voronoi diagram from this set of seed points. Is this diagram need to be 3D or 2D? In most resources I saw 2D diagrams as examples, but then I don't understand, how to apply 2D Voronoi diagram to 3D mesh.
3. Intersect created Voronoi diagram with mesh, create cuts on faces according to this intersection. Currently I don't know how to do it, but think that boolean operations will do the trick.
4. Create new meshes, inherit and interpolate all texture, normal, color data etc.
5. Fill cut mesh parts with new faces, using triangulation. Separater this new back faces in submesh and introduce some sort of “inner material" (or somehow battle with UVs, don't know how)
6. For complex structures, consisting of many mesh chunks, create fixed joints, and collapse all structure when there is no connection to the ground (for example, if building level walls is crushed, all building will land down one level)

Can someone help me validate my understanding of entire pipeline, and provide resources or insight of where I need to start and how can I feel the gaps in my knowledge?

I'd confirm all your points to be correct, though i have not implemented this but some similar things.

1. Create Voronoi diagram from this set of seed points. Is this diagram need to be 3D or 2D? In most resources I saw 2D diagrams as examples, but then I don't understand, how to apply 2D Voronoi diagram to 3D mesh.

2D is quite difficult i guess. It will work if you can divide your buildings walls into sets of 2D planes, but then edges and corners become difficult to handle. I don't think it's easier, but quality would be better eventually. I would start with 3D to keep it simpler and reject voronoi sample too close to the surface, or user other hacks heuristics to deal with quality issues.

BlackDice said:
Intersect created Voronoi diagram with mesh, create cuts on faces according to this intersection. Currently I don't know how to do it, but think that boolean operations will do the trick.

Yeah. Another can of worms. CSG operations are hard to make robust, and you need solid manifold geometry as input, which usually is not the case for game models. Common methods are to make BSP trees over the solid input geometry, or use voxelization / SDF methods to convert surface models into volumes, process it, convert back to surface meshes.

For a resource, the Newton Physics engine (http://www.newtondynamics.com)​ has the feature, but parts of it are still WIP and not sure if there's a demo currently to show it. (More likely in the older 3.x version than in the newer 4.0).

I guess other physics engines have this too, but not sure about PhysX which unity uses. I would have assumed Unity has tools to do such destruction preprocessing? (EDIT: Or you can find some plug in?)

CGAL (https://www.cgal.org/)​ is known to have robust CSG support.

GitHub also shows a lot of CSG projects.

@JoeJ thank you!

After some thinking, we decided that with our current knowledge this task unfortunately would be very hard to accomplish in near future. There is serious lack of knowledge in math algorithms and data structures like BSP trees etc..

But this isn't mean that I want to give up with this idea. For our current project we will use simpler “smokes and mirrors” approach, but I still want to learn this stuff.

As I've said, my knowledge in 3D math is very basic - linear math, vectors, matrices, and previously I've implemented some collision detection algorithms and ocean floor simulation, but that's practically all. Can you advice me, is there method to close this blank spaces systematically? I mean, some math literature that can give me enough fundamentals? I want to understand all of this, but I can't find a safe way to climb avoiding overcomplexity and frustration I get now.

BlackDice said:
we decided that with our current knowledge this task unfortunately would be very hard to accomplish in near future.

I think that's a wise decision. Doing this yourself would mean to spend the very most time on a single feature, and if it's mainly cosmetically that's likely not worth it.

As I've said, my knowledge in 3D math is very basic - linear math, vectors, matrices, and previously I've implemented some collision detection algorithms and ocean floor simulation, but that's practically all.

Sounds you're well equipped. Personally i'm self thought, and after working mainly on geometry processing for the last 5 years i feel it is a very hard field to dive into, especially because lacking education in calculus and linear algebra. And i never found any resources to learn even those basics easily. Overcomplexity and frustration so became good known friends to me, reinventing wheels as well ; )

Very helpful were the works from here: https://www.cs.cmu.edu/~kmcrane/index.html#top​ Very advanced stuff, but i was able to implement some papers and there are also courses / introductions on the field of discrete differential geometry. Helpful for things like automatic UV parameterization and remeshing.

Though, that's not really what's needed to slice a model into pieces, which seems more a matter of programming skills than math. I expect practical problems like many special cases and floating point precision issues. You could look up how BSP map compilers for Quake worked, but i'm not sure if this approach can scale up to current day detailed geometry. There was a related thread here some while back: https://www.gamedev.net/forums/topic/709278-ray-to-octree-intersection-for-boolean-geometry/5436021/?page=1​

The best advice i can give is to lookup open source libraries and related research papers.​

@JoeJ Big thank you for support and your advices!

You are right that this things must not be rushed. 5 years is big chunk of time, and I obviously can't get same results in a few days ?

Thank you.