Stone Devlog: Next Steps
When I finished my last post, I intended to start this one by discussing some of the remaining kinks I had to work out in the new mesh clipping implementation. Since then, however, I've actually worked out most of those kinks. So, rather than talk about issues, we're going to change things up a bit and look at some results. Check this out:
That right there is our favorite testing stone split with 5,000 Voronoi cells. Of course, not every cell actually intersects the stone, so the actual number of shards is quite a bit lower (maybe around 10% of the number of cells). Even still, this is awesome. With my previous plane splitting implementation, I could only hope to achieve these results if I made it ignore all the errors it threw, and even then, the geometry always had issues.
The last piece to this puzzle will be to properly fill the holes left behind by the split. As mentioned last time, faces in this algorithm are polylines, rather than triangles. These polylines will need to be triangulated in order to be used by Unity. My original triangulation implementation was a basic 'pinch' style fill, where I create a new vertex by average all the existing vertices, then create triangles connecting each edge to that midpoint. It serves its purpose, but doesn't play nice with concavity, where the center point may be outside of the shape's bounds. I've started working on an implementation of the ear clipping algorithm, which should be able to handle concave polylines, even if the triangulation isn't particularly optimal.
Once that's out of the way, we'll be all set to start cutting shards from the stone. I got a bit over-excited and started working on building the negative portion of the clipped mesh and I'm actually very close to completion. By caching the source polyhedron in the clipped mesh, I can look up any clipped face by index and get its original geometry. This circumvents the issues presented by the destructive operations of the clipping algorithm. Then, by adding a flag to the faces to mark if it fills a hole, I was able to easily identify the faces of the cutout that I needed to keep. All I had to do was flip the faces' normals and insert those faces into the negative mesh as I built it. Using the same idea, I can identify edges around the hole, as well as the faces that need to be created to join the cutout with the rest of the mesh. Here's a picture of what I've got so far:
The red lines show the edges of the faces that need to be created to connect the two sections of the mesh. They are segments of the original edges that were intersected by the clipping planes. The edges are not flagged as 'clipped', but their end points now lie along the hole edge. However, since the algorithm modifies edges in place, they still share the same spot in the edge array as the original edges. So by looking up the original and the modified edge by index, I can use each of their end points to create the edge I need. With those edges gathered up, all I need to do it triangulate the faces they define.
Keen eyes have may noticed that the faces of the hole cutout in the picture don't look like they are filled by the pinch method I mentioned earlier. That's because they're filled by ear clipping! It's almost there, but still needs a little extra love to handle concave polylines reliably... and not get stuck in an infinite loop. Once that is sorted, we will have shard cutting just about complete and we can start wrapping up our first major milestone.
 |
| 5,000 site shatter |
That right there is our favorite testing stone split with 5,000 Voronoi cells. Of course, not every cell actually intersects the stone, so the actual number of shards is quite a bit lower (maybe around 10% of the number of cells). Even still, this is awesome. With my previous plane splitting implementation, I could only hope to achieve these results if I made it ignore all the errors it threw, and even then, the geometry always had issues.
The last piece to this puzzle will be to properly fill the holes left behind by the split. As mentioned last time, faces in this algorithm are polylines, rather than triangles. These polylines will need to be triangulated in order to be used by Unity. My original triangulation implementation was a basic 'pinch' style fill, where I create a new vertex by average all the existing vertices, then create triangles connecting each edge to that midpoint. It serves its purpose, but doesn't play nice with concavity, where the center point may be outside of the shape's bounds. I've started working on an implementation of the ear clipping algorithm, which should be able to handle concave polylines, even if the triangulation isn't particularly optimal.
Once that's out of the way, we'll be all set to start cutting shards from the stone. I got a bit over-excited and started working on building the negative portion of the clipped mesh and I'm actually very close to completion. By caching the source polyhedron in the clipped mesh, I can look up any clipped face by index and get its original geometry. This circumvents the issues presented by the destructive operations of the clipping algorithm. Then, by adding a flag to the faces to mark if it fills a hole, I was able to easily identify the faces of the cutout that I needed to keep. All I had to do was flip the faces' normals and insert those faces into the negative mesh as I built it. Using the same idea, I can identify edges around the hole, as well as the faces that need to be created to join the cutout with the rest of the mesh. Here's a picture of what I've got so far:
 |
| Shard removal with red lines outlining the needed faces |
The red lines show the edges of the faces that need to be created to connect the two sections of the mesh. They are segments of the original edges that were intersected by the clipping planes. The edges are not flagged as 'clipped', but their end points now lie along the hole edge. However, since the algorithm modifies edges in place, they still share the same spot in the edge array as the original edges. So by looking up the original and the modified edge by index, I can use each of their end points to create the edge I need. With those edges gathered up, all I need to do it triangulate the faces they define.
Keen eyes have may noticed that the faces of the hole cutout in the picture don't look like they are filled by the pinch method I mentioned earlier. That's because they're filled by ear clipping! It's almost there, but still needs a little extra love to handle concave polylines reliably... and not get stuck in an infinite loop. Once that is sorted, we will have shard cutting just about complete and we can start wrapping up our first major milestone.