Triangle Soup, or, how do I eat it?

I have a fascination with old 3D stuff. Games, applications, you name it, it's all exciting! I had a thing for level editors in particular. I remember looking over the source code for the old qtools release and marveling - while taking notes - on how they made it all work, when I read a comment, presumably from Abrash or Carmack:

This is done by brute force, and could easily get a lot faster if anyone cares.

And it had me wondering...

In the years since, I have picked up a few new tricks for solving those same old problems, of which I am happy to present two of them here, but let's begin with the problem itself: the triangle soup.

What is Triangle Soup?

These days it's common for entire levels to be made inside 3D packages; with Traum everything from geometry to entities are made and arranged inside Blender. A piece-wise approach is also popular where geometric set-pieces are crafted in the 3D package of choice, then brought into a designer tool, as is often seen in Unity and Unreal. Which ever way is used though, the data has to be processed into a form that the underlying engine may use. In terms of geometric data, it is often given as an unorganised set of polygons - often triangles - hence the name Triangle Soup comes.

Depending on your application, you may only be interested in the faces, in which case you will need only minimal processing, whereas things like physics engines require a lot more work to process the data into something usable. What ever your application may be, the first data structure presented here will help aid in the digestion of the triangle soup!

The Half-Edge Structure

This data structure is also known as the Doubly Connected Edge List, a name which a part from being a mouthful, also hints at its underlying primitive structure. In short, a given polygon is decomposed into a doubly linked list, where each edge is a node in the list. Edges are linked in respect to their winding order. While not required, I find making the list circular simplifies a lot of code in practice.

The 'half' part of the 'Half-Edge' name stems from the fact each edge in this structure is bound only to a single face, rather than being shared between two as in the general sense of an edge. Instead, each half-edge contains a link to its twin in the other face that shares the logical edge, which together the twins represent. For clarity, see the picture below.

            AB
    A-----------------B
    |                /|
    |               / |
    |     F0       /  |
    |             /   |
    |            /    |
    |           /     |
    |          /      |
 CA |      BC /       | BD
    |        /        |
    |       / CB      |
    |      /          |
    |     /           |
    |    /            |
    |   /             |
    |  /       F1     |
    | /               |
    |/                |
    C-----------------D
            DC

^{Edges AB, BC and CA form face F0, and edges BD, DC and CB form face F1. Edges BC and CB are twins. Note that the twins may have different winding orders.}

In addition to the edge links, the remaining fields of a half-edge are a vertex and a reference to the face to which it belongs. Additional fields may be given as well as needed. A basic example is given below.

struct HalfEdge:
    HalfEdge prev
    HalfEdge next
    HalfEdge twin
    Vector3 point
    Face owner
end

Through the twin links may adjacent faces be traveled, thus forming a full fledged graph once the triangle soup has been rendered into this form! This is where the true power of this structure becomes apparent. For example, merging two faces now boils down to a matter of joining linked lists together, like so:

edge.prev.next = twin.next
twin.next.prev = edge.prev
edge.next.prev = twin.prev
twin.prev.next = edge.next

In practice there will be some extra busy work with fixing up face references, but as far as the geometric operation itself goes, it's really as simple as that!

The appeal in this structure is its generality, and the raw power that it gives us to manipulate geometric data in a sensible, structured way. In the Traum tools for example, triangle soup is digested into a half-edge graph, then run through different modules to generate datasets for the graphics and collision systems, and will be soon used to derive pathfinding data as well.

All of this generality comes at a cost though, and it's ultimately the same as its underlying structure: High memory overhead, and poor data locality. Each Half-Edge is 44 bytes, assuming 64 bit pointers, making a single triangle consume 132 bytes, given the example structure.

For situations where this is too great a cost, I would like to present the next structure as a possible alternative.

The Tri-Tree

The Tri-Tree is, as far as I know, a little known data structure that is analogous in every way to its more famous sibling, the Quad-Tree. The difference between them being that the Tri-Tree only has three neighbours instead of four. I first encountered it while reading about Henri Hakl's Diamond Terrain Algorithm, and have never again seen it in any other literature or application, but it is also a fine digestive aid. See the picture below to get an idea of how it's shaped.

 ________________________
 \          /\          /
  \  left  / b\ right  /
   \      /____\      /
    \    /\    /\    /
     \  /d \ a/ c\  /
      \/____\/____\/
       \  bottom  /
        \        /
         \      /
          \    /
           \  /
            \/

^{The Tri-Tree has a reference to its parent tri-tree, three references to its neighbours, one for each edge, as well as four references to inner tri-tree children.}

An example structure may look like this, and again, additional fields for attribute data may be added as needed:

struct TriTree:
    TriTree parent
    TriTree left, right, bottom     #The three neighbours
    TriTree a, b, c, d              #The four children
    Vector3 p0, p1, p2              #The 3 points of the triangle
end

This structure has a strong hierarchical flavour with this interesting property: any triangle may be split into four sub-triangles, or vice versa, any four children may be reduced into a single triangle. Because of this, the Tri-Tree structure lends it self well to deriving graphical data. For example, by exploiting its hierarchical property, generating LODs is made a much more enjoyable task. I also found that it makes for a suitable choice for creating adjacency graphs, which if that's all you need, then the structure could be modified such that there are only the three neighbour links.

Memory usage may be reduced by storing references as 8- 16- or 32- bit values, that index into a preallocated list of Tri-Tree structures, which is more easily done with this structure than the Half-Edge given above. Similarly the vertices may be given as index values as well for further savings. Indeed, of the two this structure is the most flexible with memory usage. A single triangle comes in at 100 bytes in the example form, and may easily be reduced to less than a single half-edge in size!

Outside of graphical applications things look rough for the Tri-Tree. While it has an interesting hierarchical property, and constant time access to adjacency information, it does not provide any explicit access to edge data, in addition to being locked into representing all geometry as triangles. However, if these limitations are acceptable, then it may work well in digesting triangle soup into pathfinding data, given its easy access to adjacency information.

The Final Word

Some readers may be wondering if there are any other alternatives out there, and the answer is Yes: the Winged Edge structure is said to offer a lot of constant time look ups if you're really hurting for speed, but it's a state heavy solution, requiring three different structures, and has the highest memory overhead of them all. Its features are similar to the Half-Edge structure, which it predates by a few years!

And with that we come to the end of the article. I hope these little musings help someone find their way in this crazy world.

Thank you for reading!