Friday, June 28, 2013

Procedural fracturing: Mesh generation and physics

This will probably be the last post on procedural fracturing. Why? Because it's mostly done!  In a few hours of heroic brain effort, I went from this:
Lines are drawn between centroids and vertices in this image.
There's also an axis pointing right is there for debug purposes
To this:
A fully procedural mesh!

The little things

After so much brain destruction over this, there were two bugs: one in finding the center of each circumcircle (I was dividing by zero somewhere, getting secret NaNs), and another in the centroid sorting algorithm. I also facepalmed really hard because the first sentence on the wiki page for polygon triangulation is "A convex polygon is trivial to triangulate in linear time, by adding diagonals from one vertex to all other vertices." Oops. I threw out the copy/paste ear clipping algorithm and just wrote my own thing to add diagonals. It's funny how something can seem so simple and obvious in retrospect. The only downside to this technique is that the geometry created isn't really suitable for animation; I'll be avoiding this by joining vorons together instead of animating vorons individually.

Oh, and the extrusion algorithm I hypothesized in the previous post actually worked! ("I can't believe this actually worked!") Here's a video demonstrating mesh generation and some simple rigidbody physics.

Physics.Raycast() or why I love Unity

Now that we have actual GameObjects and meshes, we can do away with all this math and start brute forcing things! The wonder of Physics.Raycast() is one the reasons I started looking into game development in the first place.
Raycast is actually a very descriptive name because it is a magic spell. You pick an origin and a direction and it will tell you what is in that direction. Every time I use this function I feel like a powerful wizard - able to conjure eldritch data from the very aether! Of course, such great power comes with a cost. It is quite an expensive algorithm to run; you can't do a million raycasts each frame and expect your game to perform decently. Which is fine, we only have to do one raycast per voron, and only do it when we fracture stuff.

What is all this for? We're going to use this to figure out how to join each extruded voron together to create a cool looking fragmentation/bending pattern. From the perspective of each voron, do a raycast in the direction opposite from the center of the impact site, if you don't get anything then you're an edge piece, and if you hit another voron, then you create a physics hinge joint between the two. Maybe also have a probability (10% ?) of not creating a hinge so that there can also be some debris on the ground. Then you'll have to set up the hinge position and axis. The hinge position is the half distance between the two voron sites and the hinge axis is the bisector of that distance vector.

This shows the hinges and voronoi sites, though it's a bit buggy here.

There is also this problem of nightmare vorons. These guys have three voronoi sites that are close to colinear, so they produce a vertex that is very very far away. This can be seen in the video, there are some fragment pieces that are much longer than the others and they get stuck in the roof or floor. The solution to this is rather simple, just check if the vertices are too far away from the center during vertex generation. While I was trying to implement this, I did create a pretty cool looking bug:

Nightmare vorons! *shudder*
Here's a few cool looking examples of the nearly final result of all this work:

Wall pieces are a bit thicker in this one.

Of course, it needs a bit of tuning (maybe the fragments look a bit too round?), and well, the wall isn't actually broken behind the 'impact' yet. If it's kind of hard to tell whats going on, just wait till you see it in 3D. It's pretty awesome. I hope you guys like this. This is by far the most intellectually challenging feature I've implemented. As always, feel free to leave comments or questions. Thanks!