Stone Devlog: Cell Fracture
In my last post, I mentioned that in my efforts to overcomplicate the knapping system, I spent way too much time looking into Constructive Solid Geometry (CSG). It seemed like the solution to my problem and I was on the right track, but I was on the wrong train.
My goal was to cut one 3D shape out of another, so while I initially looked into the full suite of boolean operations, I only actually need to be able to find the difference/subtraction, not the union, XOR, or even intersection. Meanwhile, CSG itself is not an implementation, but rather a technique that employs all the boolean operations. As a result, researching CSG ended up being an exercise in frustration.
After my head started to ache from banging it against the wall for so long, I took a step away and played around with the latest version of Blender. I used the cell fracture add-on to create a render of an object being shattered. As I watched the little, jagged bits fly all over the place, I thought to myself "I wish I had something like that..."
The realization hit me like a sack of bricks. I could have something just like that! Some quick Googling later and I was reading all about Voronoi Diagrams and Delaunay Triangulations.
A Voronoi Diagram is a spatial partitioning of an area into "cells" from an given set of points. It has a lot of useful properties, but all we really care about is that the cells look like shards and it is possible to scale it to 3 dimensional space (and beyond).
So how do we create this Voronoi Diagram? And what's a Delaunay Triangulation? Well, a Delaunay Triangulation is how we create a Voronoi Diagram! While it is possible to generate a Voronoi Diagram directly from the set of points, the Internet assured me it was easier to derive the Voronoi Diagram from its dual, a Delaunay Triangulation.
A Delaunay Triangulation is a triangulation of a set of points such that no point lies inside the circumcircle of a triangle. Again, interesting properties, useful applications (including tessellation and navmesh generation), but we really only care about those shards.
So, let's get cracking. Since we want a 3D Voronoi Diagram, we need to also translate the triangulation to 3D, making it a tetrahedralization. Using a couple articles and a research paper online, I was able to make something that spit out a proper tetrahedralization:
Wireframes are never particularly pretty, but it's the quickest way to show what's going on inside. It might not look like much, but that is a proper Delaunay Tetrahedralization. Now, we can derive the Voronoi Diagram. Each point in the tetrahedralization corresponds to a cell in the Voronoi Diagram. A cell is actually a 3D polyhedron, and its vertices are the circumcenters of each tetrahedron that contains the point. Since every cell is a convex shape, once all those circumcenters are gathered up, the shape of the cell can be determined by finding the convex hull. Easy peasy, we have a 3D Voronoi Diagram:
Wireframe again, but take a look at the highlighted cell in the middle of that mess. It's those little fragments that we are going to chip out of our stones to shape them. But we'll have to talk about that later.
PS: Just for laughs, I added an option to my testing script to add rigidbodies to each of the cells so they all would fall and break apart on the ground.
My goal was to cut one 3D shape out of another, so while I initially looked into the full suite of boolean operations, I only actually need to be able to find the difference/subtraction, not the union, XOR, or even intersection. Meanwhile, CSG itself is not an implementation, but rather a technique that employs all the boolean operations. As a result, researching CSG ended up being an exercise in frustration.
After my head started to ache from banging it against the wall for so long, I took a step away and played around with the latest version of Blender. I used the cell fracture add-on to create a render of an object being shattered. As I watched the little, jagged bits fly all over the place, I thought to myself "I wish I had something like that..."
The realization hit me like a sack of bricks. I could have something just like that! Some quick Googling later and I was reading all about Voronoi Diagrams and Delaunay Triangulations.
A Voronoi Diagram is a spatial partitioning of an area into "cells" from an given set of points. It has a lot of useful properties, but all we really care about is that the cells look like shards and it is possible to scale it to 3 dimensional space (and beyond).
So how do we create this Voronoi Diagram? And what's a Delaunay Triangulation? Well, a Delaunay Triangulation is how we create a Voronoi Diagram! While it is possible to generate a Voronoi Diagram directly from the set of points, the Internet assured me it was easier to derive the Voronoi Diagram from its dual, a Delaunay Triangulation.
A Delaunay Triangulation is a triangulation of a set of points such that no point lies inside the circumcircle of a triangle. Again, interesting properties, useful applications (including tessellation and navmesh generation), but we really only care about those shards.
So, let's get cracking. Since we want a 3D Voronoi Diagram, we need to also translate the triangulation to 3D, making it a tetrahedralization. Using a couple articles and a research paper online, I was able to make something that spit out a proper tetrahedralization:
 |
| 3D Delaunay Tetrahedralization of 100 random points |
Wireframes are never particularly pretty, but it's the quickest way to show what's going on inside. It might not look like much, but that is a proper Delaunay Tetrahedralization. Now, we can derive the Voronoi Diagram. Each point in the tetrahedralization corresponds to a cell in the Voronoi Diagram. A cell is actually a 3D polyhedron, and its vertices are the circumcenters of each tetrahedron that contains the point. Since every cell is a convex shape, once all those circumcenters are gathered up, the shape of the cell can be determined by finding the convex hull. Easy peasy, we have a 3D Voronoi Diagram:
 |
| The derived Voronoi Diagram with one cell highlighted |
Wireframe again, but take a look at the highlighted cell in the middle of that mess. It's those little fragments that we are going to chip out of our stones to shape them. But we'll have to talk about that later.
PS: Just for laughs, I added an option to my testing script to add rigidbodies to each of the cells so they all would fall and break apart on the ground.
 |
| To shards you say |