Notes on Winged Edges and 3D Modelers

This page is under heavy construction. It’s missing large portions and is going under constant edits and refactors.

I have a love-hate relationship with topology and topology algorithms. Especially with a category I’ve dubbed mass-topology. These are things that, by design, will have a large number of complex interconnections. On the one hand, I truly appreciate graph data-structures, which is pretty much just the application of topology to represent things. What things? Anything; pretty much everything! On the other hand…

There are certain reasons a bug can exist. Usually an incorrect symbol or variable is used. Sometimes nesting is configured incorrectly. Sometimes you misunderstood the mechanics of how something was actually supposed to work. Or, sometimes you can know how everything is supposed to work, and if there’s a bug, it’s hard to figure out exactly what it is because it involves validating a super-state, an interconnection of many elements, even for the simplest of examples. So here’s winged eges, good luck, godspeed, and may a divine protective force have mercy on us all.

The winged edge data structure, or its more compact half edge data structure, is pretty much the backbone for 3D modeling programs.

Primer and Prerequisites

Let’s first touch up on the basics here. When 3D models are drawn, at its simplest, they comprise of vertices that are connected to form triangles. This is known as polygon soup. Often you’ll want to make sure these points are connected to create a well-formed surface. This means that for any edge of a triangle, it only has 2 triangles attached to it and these triangles start interconnecting to make more complex forms. This is called meshing.

Now if we’re rendering with a graphics API, we need to send the triangles as instructions to the graphics card – the graphics API will then use its rendering library and it’s connection with the graphics card to do this. And that’s pretty much the run-down for representing and drawing the simplest of shapes. There’s countless ways to add more features and complexity to all this – but that’s the start.

So that’s simple rendering, but what about simple editing and authoring? Well, if we were to make authoring really crude, we could have the users constantly author 3 points, and those triplets of points would the triangle. Or we could allow the user to author a set of points and then author a triplet of indices that refer to those points – which helps reuse points and makes meshing a little more convenient. The problem is, that while these are simple ideas to implement, these are all very crude and unintuitive to the user.

Winged Edge

Enter the winged edge, a data structure that represents the mesh as a graph data structure. It inherently meshes, and allows provides a foundation to create intuitive editing operations for the users, at the cost of complexity. The algorithm focuses of maintaining the topology of the meshes it represents. What does that means specifically? It means the faces are able to track what vertices and edges make it; vertices are able to track what edges and faces they contribute to; and edges are able to track what vertices make it, and what faces it contributes to. Basically, every element of the mesh knows has the ability to quickly find what it’s connected to. All this correct state-keeping requires memory and complexity.

I’m going to be referencing my own C# code for Unity3D, which is going to be different than what other examples might show. One of the biggest reasons is to avoid awkwardly using unsafe code. A lot of code examples out there are C/C++ and they make liberal use of pointers and inline arrays.

public class Vert
{
    // Debug identification
    static int dbgidctr = 0;
    int dbgid;

    // 3D position in the shape
    public Vector3 position;
    // The edges that the verts contribute to.
    public List<WEdge> edges = new List<WEdge>();

    // The position of the vert in the shape's linked list
    public LinkedListNode<Vert> selfNode = null;

    public Vert()
    { 
        this.dbgid = dbgidctr;
        ++dbgidctr;
    }
}

// Vertex to edge connection.
public struct VertEdgeCon
{ 
    // One of the 2 vertices  that make up the edge.
    public Vert vert;

    // The edge connected to this edge, from vert.
    public WEdge edge;

    // The face that this edge is connected to.
    // If this edge, and the member this.edge form
    // a face, that will be this variable. if this were
    // the top point of a vertical edge, this would be
    // the left face.
    public Face face;

    public VertEdgeCon(Vert vert, WEdge edge, Face face)
    { 
        this.vert = vert;
        this.edge = edge;
        this.face = face;
    }
}

public class WEdge
{
    // Debug identification
    static int dbgidctr = 0;
    int dbgid;

    // Half edges
    public VertEdgeCon conA;
    public VertEdgeCon conB;

    // The position of teh edge in the shape's linked list.
    public LinkedListNode<WEdge> selfNode = null;

    public WEdge()
    { 
        this.dbgid = dbgidctr;
        ++dbgidctr;
    }
}

// N-gon
public class Face 
{
    // Debug identification
    static int dbgidctr = 0;
    int dbgid;

    // The edges that make the face. These
    // have a clockwise winding.
    public List<WEdge> edges = new List<WEdge>();

    // The position of the face in the shape's linked list.
    public LinkedListNode<Face> selfNode = null;

    public Face()
    { 
        this.dbgid = dbgidctr;
        ++dbgidctr;
    }
}

// A mesh object
public class Shape
{

    // The various linked list of elements that make up the 3D mesh model.
    public LinkedList<WEdge> edges              = new LinkedList<WEdge>();
    public LinkedList<Vert> vertices            = new LinkedList<Vert>();
    public LinkedList<Face> faces               = new LinkedList<Face>();

    // Extra local transform.
    public Vector3 localPos     = Vector3.zero;
    public Vector3 localEuler   = Vector3.zero;
    public Vector3 localScale   = Vector3.one;
}

Here are some snippets of the various classes. I’ve stripped out a lot of the methods and focused on the variables.

A few significant things to mention. Let’s start with mentioning use of the linked lists instead of the standard (non-linked)list. Often times new elements need to be added, and old elements need to be removed in the shape’s collections. The linked list is used to make sure we get good removal times. Also, note in WEdge the two sides of the edges, conA and conB. Another thing is the id stored for every face, edge and vert assigned from a counter. This is a debug feature so that they can be identified. The various algorithms and are deterministic so the exact same shapes produced from the exact same operations between program sessions should always yield the exact same ids. It especially helps with diagramming the network.

A limitation I wanted to point out: points in a mesh may actually be comprised of several verts that share the same position, because there may be triangles that need different (texture) UVs, normals, tangents, etc – these classes as they are cannot support that. Because of that, I’m not even bothering supporting and storing UV and normals. That won’t be talked about here, it won’t be a feature in the demos.

Topology

Winding Order

Let’s say we have a triangle, and we’re looking straight down it it’s surface. The 3 points of the triangle have unique names, let’s say t0, t1 and t2. We list off the names of all the points that make up that triangle. One of two things are going to happen: the order we list the points is going to form a clockwise rotation, or the list of points will form a counter-clockwise rotation.

The order we decided to list these points by, and the rotation that it forms is important. This is called the winding order. The triangle can be though of a limited section of a plane. A plane? A mathematical flat surface that separates two regions of space, called half-spaces. The triangle defines a plane, and the winding order defines which side of the plane is inside, and which side of the plane is outside. When we have multiple triangles meshed together, they will all share the same winding order so that their inside half spaces consistently fill the inside, or define the outside, or the object that they’re meshing to form.

Object Constructions

In modeling packages, simple starting models called primitives can be made. Some examples are sphere, boxes, toruses. Just simple shapes that have a few parameters. The first thing to do was to make some simple shapes where I could stitch the topology by hand and view every part to make sure everything can correct. The two shapes I used were an untesselated plane, and untesselated cube.

Vertex Modifications

Modifying shapes by modifying vertices is

Topology Modifications

Paul Borke on mesh operations.

Boolean Operations

No idea, not really confident on how I would even start implementing simple yet robust Boolean operations. Next topic!

Subdivision

Final Words

Side note, it’s obvious but here goes: this data structure incurs overhead. Maintaining topology information takes more memory than if you didn’t. I once worked in a graphics house where we had an in-house modelling program that was primarily focused on vertex array and index arrays for triangle stitching. There was more to it than that, but essentially it boiled down to that. We had to process very large STL files that were high fidelity exports of CAD models. There were times where I wished we had winged edge tools (extrude, bevel, loop cuts, etc), but that software could handle huge triangle meshes like nothing else! And by nothing-else, I mean these CAD models were absurdly dense and our software didn’t crash where other 3D modeling and animation programs would. Because it didn’t use winged edge data structures, it had a significantly lighter footprint for representing triangles.

– William Leu. Stay strong, code on.