Stone Devlog: The Shattered Saga Part II
Let's get right into it. After a quick Google search, I found this paper and it revealed to me all the ways I was being a dumb-dumb with my splitting algorithm.
The gist of the algorithm outlined in the paper is as follows:
Alright, so there are quite a few differences here, compared to my implementation. First and foremost, this split is only concerned with what lies on the positive side of the splitting plane (the side the normal of the plane points). Its operations are also destructive, as it removes edges from faces, so no pulling a negative side out at the same time. This would be problematic if I wanted to make a 3D Fruit Ninja or something, but in my case it isn't a big deal. While I want to keep what's on the negative side of the planes, to keep the inside of the Voronoi cell, I can simply reverse the normal of each plane before splitting.
The algorithm also elegantly handles all those pesky cases I mentioned last time with vertices that are on the splitting plane. It accomplishes this by not actually having a concept of coincidence. Either an edge is bisected by the plane or it isn't. If one vertex is one the plane, but the other isn't, that edge is on one side of the plane or the other. If both vertices are on the plane, the edge is considered on the negative side and removed, leaving a hole in a face that is later closed by the face processing.
That leads me to the biggest difference between this implementation and my own: the edge processing is the real meat and potatoes of the algorithm. In my implementation, the mesh class stores only vertices and faces, mirroring the structure of Unity's meshes. Faces contain an array of the three vertices that comprise them, while edges are merely a by-product. In fact, if I want edge n of a face, the GetEdge function creates a new edge object containing vertex n and vertex n + 1. Conversely, a face in this new algorithm is comprised of a set of (indices of) edges. The top level mesh class contains the vertices, edges, and faces. While I processed the edges of each face, this algorithm processes the edges of the mesh.
Another key difference here is that faces are not necessarily triangles. As I mentioned, a face is comprised of a set of edges, which can grow and shrink as needed. These edges form a closed string of edges that ends at the same vertex it starts at, also known as a polyline. And because this algorithm primarily focuses on the edges, these polyline faces can continue to be processed. This was a tremendous realization for me. The only time I actually need triangles is when I convert the to Unity meshes for rendering. Triangulation of the polylines can just be a part of that conversion. Not only does this alleviate the thin triangles issue I mentioned in the previous part, this could also massively improve the data structures behind the scenes. Currently, faces of the Voronoi cells are triangulated, meaning there are typically several coplanar triangles making up a face. During the splitting process, each of these triangles gets converted to a plane, and then attempts to split the mesh. Except, after the first, no intersection is found because the mesh has already been split by that exact same plane in a prior pass. Instead, the faces of the cell could be a polyline, resulting in only one plane. Similarly, storing a polyline instead of multiple coplanar triangles in the mesh class will improve incremental splitting by removing the need to process extra edges created by the triangulation.
As a final point of interest, this algorithm creates a copy of the mesh and modifies it in place. This is compared to my implementation that built the two subdivisions of the mesh by injecting vertices and faces into one of two new, empty meshes. By modifying the mesh in place, splitting can be performed incrementally until the desired output is produced (i.e. all faces of a Voronoi cell have been processed). This means at the end of all the splitting, the mesh still has its original vertices, they're just flagged to be ignored. With some tinkering to make the algorithm non-destructive of faces on the negative side of the plane, I may be able to finagle it to produce the remainder of the mesh after removing the shard. I will definitely have to look into that when I move into implementing the proper knapping system.
To wrap things up, I've already gone ahead and implemented this algorithm, completely replacing my original attempt. There are still some kinks to work out, but it's been working spectacularly so far. Next time we'll look at some of the results and talk about what still needs to be done.
The gist of the algorithm outlined in the paper is as follows:
- Process the vertices, flagging any that are on the negative side of the plane, and caching the distance of each vertex to the plane. Notably, if the distance is less than an epsilon value and greater than the negative of that epsilon value, the distance is cached as zero. Nice way to simplify subsequent checks. If all the vertices are flagged or no vertices are flagged, there is no intersection and we can exit early.
- Next, the edges are processed. If the cached distances for both vertices of the edge are less than or equal to zero, there is no intersection and the edge is flagged as being on the negative side of the plane. That edge is also removed from the faces that contain it. If all the edges are removed from a face, that face is flagged as being on the negative side of the plane. Additionally, if both distances are greater than or equal to zero, the edge does not intersect the plane, but is on the positive side, so it is left alone. Finally, if one distance is greater than zero and another is less than zero, an intersection exists. The intersection is calculated, then inserted as a new vertex. The new vertex replaces the original vertex of the edge that was on the negative side of the plane.
- Finally, faces are processed. All faces on the positive side of the plane are tested to verify that they are closed polylines. Each vertex of a closed (convex) polyline should occur twice, once as the end of an edge, then a second time as the start of the next edge. An open polyline will have two vertices that occur only once. In that case, a new edge containing those two vertices is inserted into the face.
- After splitting the mesh, to convert the split mesh back to a usable mesh, the indices of the vertices, edges, and faces that are on the positive side of the plane need to be remapped, as everything flagged on the negative side is discarded.
Alright, so there are quite a few differences here, compared to my implementation. First and foremost, this split is only concerned with what lies on the positive side of the splitting plane (the side the normal of the plane points). Its operations are also destructive, as it removes edges from faces, so no pulling a negative side out at the same time. This would be problematic if I wanted to make a 3D Fruit Ninja or something, but in my case it isn't a big deal. While I want to keep what's on the negative side of the planes, to keep the inside of the Voronoi cell, I can simply reverse the normal of each plane before splitting.
The algorithm also elegantly handles all those pesky cases I mentioned last time with vertices that are on the splitting plane. It accomplishes this by not actually having a concept of coincidence. Either an edge is bisected by the plane or it isn't. If one vertex is one the plane, but the other isn't, that edge is on one side of the plane or the other. If both vertices are on the plane, the edge is considered on the negative side and removed, leaving a hole in a face that is later closed by the face processing.
That leads me to the biggest difference between this implementation and my own: the edge processing is the real meat and potatoes of the algorithm. In my implementation, the mesh class stores only vertices and faces, mirroring the structure of Unity's meshes. Faces contain an array of the three vertices that comprise them, while edges are merely a by-product. In fact, if I want edge n of a face, the GetEdge function creates a new edge object containing vertex n and vertex n + 1. Conversely, a face in this new algorithm is comprised of a set of (indices of) edges. The top level mesh class contains the vertices, edges, and faces. While I processed the edges of each face, this algorithm processes the edges of the mesh.
Another key difference here is that faces are not necessarily triangles. As I mentioned, a face is comprised of a set of edges, which can grow and shrink as needed. These edges form a closed string of edges that ends at the same vertex it starts at, also known as a polyline. And because this algorithm primarily focuses on the edges, these polyline faces can continue to be processed. This was a tremendous realization for me. The only time I actually need triangles is when I convert the to Unity meshes for rendering. Triangulation of the polylines can just be a part of that conversion. Not only does this alleviate the thin triangles issue I mentioned in the previous part, this could also massively improve the data structures behind the scenes. Currently, faces of the Voronoi cells are triangulated, meaning there are typically several coplanar triangles making up a face. During the splitting process, each of these triangles gets converted to a plane, and then attempts to split the mesh. Except, after the first, no intersection is found because the mesh has already been split by that exact same plane in a prior pass. Instead, the faces of the cell could be a polyline, resulting in only one plane. Similarly, storing a polyline instead of multiple coplanar triangles in the mesh class will improve incremental splitting by removing the need to process extra edges created by the triangulation.
As a final point of interest, this algorithm creates a copy of the mesh and modifies it in place. This is compared to my implementation that built the two subdivisions of the mesh by injecting vertices and faces into one of two new, empty meshes. By modifying the mesh in place, splitting can be performed incrementally until the desired output is produced (i.e. all faces of a Voronoi cell have been processed). This means at the end of all the splitting, the mesh still has its original vertices, they're just flagged to be ignored. With some tinkering to make the algorithm non-destructive of faces on the negative side of the plane, I may be able to finagle it to produce the remainder of the mesh after removing the shard. I will definitely have to look into that when I move into implementing the proper knapping system.
To wrap things up, I've already gone ahead and implemented this algorithm, completely replacing my original attempt. There are still some kinks to work out, but it's been working spectacularly so far. Next time we'll look at some of the results and talk about what still needs to be done.