In earlier discussions (here and here), I extolled the benefits of the half edge mesh. It is an elegant way of compactly storing 2d mesh information. Moreover, it allows you to easily do adjacency tests (e.g., what are all the edges touching this vertex?). However, upon further reflection, two weaknesses have occurred to me:
- It is lacking for the finite volume method.
- Its not extendable to 3d
I don’t know that these are show stopper considerations, but they do give one pause. Lets look at them in more detail.
Finite Volume
The key tenet of the finite volume method is the balance of fluxes leaving and entering each cell face. This is what makes this approach intrinsically conservative, unlike the finite element method.
At some point in the execution of a finite volume code, we loop over the faces in the domain and calculate the fluxes crossing those faces. Because each pair of cells share one face, we know that the material leaving cell A must flow into cell B. But the half edge data structure doesn’t have faces; it has half faces. There is no single entity that connects both cells. So how do we achieve this conservation? The simplest way is probably to create a full face data structure that each half face points to. We can then calculate the fluxes on this face as normal. While this adds additional complexity to the scheme and reduces its elegance, it should be perfectly doable.
3d
What really makes me doubt the viability of the half edge approach is in generalizing it to 3d. In 2d, the vertices, edges and cells are connected together in a simple fashion. For instance, the edges around a cell are connected, one to the next, in a chain. This makes it easy to create a linked list of edges to go around the cell.
In 3d, each cell is surrounded by six faces. There are many ways to connect these faces together in a linked list. The figure shows one of them. That is workable, but how do you get an adjacency test out of it? For instance, lets say you want to know all the faces that surround a vertex. I can’t figure out any clever way of looping through the half faces to achieve this.
Next Steps
I am working on another mesh generator that uses algebraic relationships between cells, faces and vertices to establish the connections between these entities. It has a certain elegance to it as well. Unfortunately, in implementing it, I hit all kinds of memory and pointer problems that took awhile to work out.
