Stone Devlog: High Flow DCEL
Alright, time for another long overdue post. It's one of those "I had something to write about, but then I kept going" situations.
In my last post, I mentioned I was having difficulty using my existing mesh data structure to sort out the more complicated problems I was encountering. I wanted a structure that was easier to traverse, with vertices and faces being aware of their neighbors. That's when I started looking into doubly connected edge lists (DCEL). This is the data structure used by the big boy libraries such as CGAL.
A DCEL is basically a graph, with vertices being the nodes, connected by edges, and faces represented by closed edge loops. Unlike my original data structure, which did not really care about edges, in a DCEL the edges do the lion's share of the work. Each edge is actually comprised of two 'half-edges', pointed in opposite directions. One half-edge originates at the first vertex of the edge and terminates at the second, while the 'twin' half-edge originates at the second vertex and terminates at the first. Each half-edge stores a reference to its origin vertex, its twin, the previous and next edge in the loop, and the face it is incident to. In this way, each half-edge 'belongs' to only one of the two faces on either side of the edge. Meanwhile, each vertex stores a single half-edge that originates from it, and each face only stores one of its incident half-edges. And that's all the data structure needs.
By accessing the properties of the edges, every element in a DCEL is aware of every other element around it. For instance, while a face only stores a reference to one half-edge, all of a face's edges can be found by iterating through the half-edge's 'next edge' property until we return to the stored half-edge. Then each half-edge's origin property can be used to get a face's vertices. Additionally, we can use the face property of the twin of each half-edge in the loop to get all adjacent faces. Similarly, we can find the incident edges of a vertex by iterating through the edge's twin's next edge. A little complicated, but imagine travelling along an edge to its endpoint, turning around, following the edge back to the original vertex, then leaving again along the next edge and repeating until we return to the first edge. Once we have the incident half-edges, we can get adjacent vertices using the incident half-edge's twin's origin (the incident half-edge's endpoint) and incident faces using the face property of the incident half-edge.
This all requires a bit of bookkeeping, but the result is pretty slick:
On the left is a selected vertex, with its incident edges highlighted in blue and the edges closing the incident faces in red. On the right is a selected face in green, with its adjacent faces in light blue. While this visualization is decent for demo purposes, I set it up first and foremost to help myself debug the structure. Because it is absolutely reliant on edges being linked properly, the slightest error can render the entire structure essentially useless. As an example, since iterating through an edge loop for a face or incident edges for a vertex ends when it returns to the starting edge, we can end up in an infinite loop if a connection is incorrect or missing.
That said, as long as the properties of affected elements are properly updated, small operations can be chained together to effectively manipulate the structure.
Pictured above, two new vertices are inserted along two different edges of a face, then a new edge is inserted, splitting the face. The selected elements still find their appropriate neighbors. These two operations, splitting edges by inserting a new vertex and splitting faces by inserting a new edge, are pretty much all I needed to re-implement the plane splitting algorithm.
Looking pretty good. As I mentioned earlier, at the time of writing, I'm well beyond this point. I've actually already re-implemented the iterative plane splitting used to cut the Voronoi cells from the mesh. Now I just need to figure out how to use this fancy data structure to actually solve the issues I was stuck on before. But that's a discussion for another day.