Procedural fracturing for kinetic impacts

So, here is the first post that actually has to do with the development of Bad Things. I've got a few ideas for posts - some are overview/roadmappy things, and some are more retrospective, instead, I thought I'd start with what I'm actually working on right now. Before we get started, if you haven't noticed, I've included some pages on the sidebar for About, Images, and Videos.

wtf is procedural fracturing?

The idea here is that when a kinetic weapon (something that is impact or kinetic energy based) collides with the hull of the ship, it should create an entry point that appears to have a broken hole in the center, and shards of bent and peeled metal around the impact site. There are several ways to go about this, you could just create some animated meshes that look like bent metal going through various states of broken-ness or repaired-ness. That's boring. You'll see the same impact model over and over again and repairing it will always be the same task. What we want is some way to create a believable (or at least interesting) destruction shape that can be created procedurally and quickly. After looking into some procedural destruction techniques, I have settled on using Voronoi diagrams to specify the vertices of the model I'll use for destruction.

Sample fracture pattern from early Voronoi diagram compute shader.

Vorons

The regions (which I have deemed "vorons") seen in the image above are created by choosing some points or "sites" on a 2D plane and determining to which point each pixel is closest. A neat property of vorons is that each voron is guaranteed to be convex - which is an important property for procedurally creating 3D models. Choosing sites carefully, we can create a fracture pattern that looks pretty cool. Making these images in a compute shader is stupid easy, but getting useful information out of them is a bit trickier.

So, the ultimate goal here is to get the vertices that make up each voron. The vertices of a voron are the points that are equidistant from exactly three sites. If this is confusing look at the diagram below and think about it for a few seconds until it isn't.

Site is circled in orange, vertices are in light blue.

We can use the vertices of each voron to create a 3D model that will show how the hull might fracture when impacted by a kinetic weapon. The center, fully enclosed region is the part that is actually destroyed, and imagine the shards that surround the center bent back on themselves.

Back to getting the vertices. To do this I first thought that I could just try to bruteforce my way into finding the vertices by sorting the sites by distance - per pixel and see if the distances were really close to each other and then pow! if the distances were close enough, then your pixel is a vertex! But no, pixels are not nice enough for this, they are too imprecise, every time I tried this, even finely adjusting the tolerances, either there were too many pixels for some vertices or not enough for others. Ah, too bad so sad. This image based technique will not work for me, unfortunately. If only there were an analytical way find the vertices...

Circumcircle Centers

I did some research on Voronoi diagrams and I came across this little gem: http://www.cs.tufts.edu/comp/163/notes05/voronoi_handout.pdf

This handout has a bunch of information on Voronoi diagrams and a lot of it is way more than I need, but I did find something that I could use to calculate the vertices of each voron analytically:

To get the vertices for a certain site (lets call it sexySite), we just need to create all unique triplets of three sites that include sexySite, and then find the center of the circumcircle created by that triplet, and lastly, check if there are no other sites within that circumcircle. That last condition is important, without that we would have the intersection of every 3 sites that include sexySite, not just the ones that make up the voron we want to get the vertices for. Run this algorithm for each site, and you can get the vertices that make it up! Sure, it's kind of slow, but that's fine if you're only doing this once in a while. Oh and also this doesn't work for extreme sites. These aren't just extra badass risk taking sites, these are the ones that are on the outside of the diagram and are unbounded on one side... so to fix that problem, just choose your sites so they are surrounded by some extreme sites that you don't care about.

Current State

Right now, I'm working out the bugs getting all the vertices from a set of sites. There is something weird going on where I'm not getting the furthest vertices on the left or right sides... I've narrowed it down to an optimization, but as far as I can tell the optimization really shouldn't affect this. Once I've got that working reliably, I'll start to bring these vertices together into a mesh, and then figure out how to bend them in a way that looks cool!