It's been a long time since my last post. I've started and abandoned new projects, but something also stuck. I've started making video games and been an active member and maintainer of the bevy engine community. I've been always fascinated by colony sims and have one in mind that I've been wanting to make for a while. One thing that's been bothering me with any existing "building/crafting" colony sims is standardization of building primitives. Most of the time they are grid-based with flooring/walls pre-canned to a specific size. It works well, but gets nowhere to the creativity level of something like Minecraft, despite providing higher fidelity objects. So I've set out to build a construction system where players aren't bound by square grids.
Immediately I came upon a challenge - without fixed grid sizes the house walls can be any length, so I need a way to generate wall meshes. Naturally, Blender's Geometry Nodes came to mind. How do they work? I tried opening up Blender's source code to check out what's happening there, but it seems the geometry nodes operations are several layers of abstraction away from actual code that modifies the mesh, which I wasn't able to find after 30 minutes of searching for keywords I could think of with grep. My next target of interest was Houdini. After several long searching sessions I finally came upon what seems to be the industry's go to methodology - Half-Edge Mesh.
Datastructure
Half-Edge Mesh is first and foremost a data structure. It's a way of representing the mesh that makes performing editing operations on it easier. To edit meshes, we want to be able to quickly add/remove vertices in-between existing vertices. The vertices are connected by edges, so that means we are likely to need to find edges that connect two vertices. Catmull-Clark subdivision operation also reasons over adjacent faces, so we need something to be able to find adjacent faces of a point. Enter Half-Edge Mesh.
There are some implementation-specific details here - I'm using Rust's SlotMap crate to store unique "pointers" to my structures, but overall Half-Edge Mesh stores a set of vertices, faces, and halfedges. I also have a custom store of attributes that allows me to store vertex colors, positions, UV coordinates and more. The half-edge here being the culprit of the whole usability.
The ids here come from SlotMap crate again. Think of them as C++ pointers, except nice and safe without any of the garbage collection overhead. Each Half-Edge stores a vertex and a face it belongs to. The face is optional, since meshes can have holes in them. The twin and next pointers though are interesting. Next is a pointer to the next halfedge in a loop around a face (or boundary if there's no face). Twin is a pointer to a halfedge that comes from the same vertex as next, but comes in the opposite direction as current edge. This came off as confusing to me at first, but if you think about how the graphics engine has to maintain face winding in order to decide if it's front-facing or not this twin edge comes out naturally. Imagine two polygons - for example quads - sharing a side. Now draw arrows inside of one of the quads coming from each vertex to the next one in CCW order (you can use CW too, just be consistent for all of the edges). Now do the same for the other quad. Notice how the shared edge has two arrows going in opposite directions. Those are the twins!
 | |
| Edge of two adjacent faces has two "half-edges" in opposite directions |
At first when I started working on this I would draw diagrams of my Half-Edges on paper to verify my logic, however just working on a cube took me ~10 minutes to draw all of the labelled data, at which point I set out to make a debug-view which sped up developing process significantly.
 |
| A cube, extruded twice and one of the edges chamfered. This would probably take an hour to draw on paper. |
In theory this datastructure is nice and easy to work with. And you can find out many papers and college level courses that talk about it for example here and here. However the construction of new edges has several pitfalls because you need to ensure consistency manually - given two vertices, create an edge between them if there isn't one yet. The tricky part is modifying other half-edges to point to this newly created edge. There are essentially 4 possible cases where you are connecting two vertices:
- Vertices are already part of a mesh and have incoming and outgoing half-edges.
- Starting vertex has no edges, but destination vertex does.
- Starting vertex has edges, but destination vertex does not.
- Neither vertices have edges.
Seems pretty straightforward right? Nope, each case has its own edge-cases. For example in (1.) if vertices have half-edges, but all of those half-edges have a face set... Then you are trying to create a non-manifold mesh - essentially an object that's impossible to construct in real world. Or if you're trying to attach two vertices that are already attached in the opposite winding direction, or if you're trying to attach vertices that already share a face... Overall I've split the problem into these sub-problems:
- Find all "flows" of edges to and from a vertex. A flow is defined as incoming and outgoing hafledge where incoming.next = outgoing. Be careful - during new vertex creation both edge and its twin will be boundary edges, but their next pointer will not point to each other because they are twins. However, for the flow detection logic they are part of the same flow.
- Cross-compare all flows in both vertices (O(n^2)) and
- Prefer an already-connected edges (start vertex's outgoing edge == end vertex's incoming edge)
- Edges that we previously connected for this face (last created face edge == start vertex's incoming edge) or (first created face edge == end vertex's outgoing edge).
- If at any point you find that start vertex's outgoing edge == end vertex's incoming edge, then the edge already exists and we just need to add it to the face edge if we're creating a face in a loop. On the other hand you might be tempted to check if end vertex's outgoing edge == start vertex's incoming edge and complain about inconsistent windings - this is not always the case. You will hit this condition if you're trying to fill a hole - e.g. all edges are already there and you just went in a circle.
- Check for the 4 vertex conditions above and use tart/end vertex flow data that was selected in (2.) to create new edge pair. This is where you can now also check for non-manifold mesh generation.
Mesh traversal
As long as your mesh is in a consistent state and all of the edges point to the right ones (as insured by the algorithm above) the traversal becomes rather trivial. I've implemented three iterators:
- Face loop
- All incoming half-edges
- All outgoing half-edges
The face loop is rather easy to guess as that's how we defined a half-edge - you just iterate over current = current.next while current != start_edge. To iterate over all of the outgoing edges of a vertex you iterate over current = current.twin.next while current != start_edge. Similar for the incoming: current = current.twin.previous while current != start_edge.
The .previous one is not optimal - we don't have that information readily available and have to iterate over the face loop to find it. however most of your faces are likely to be quads so it's going to be an iteration of 4. Alternatively we can add previous half-edge pointer to the half-edge structure, however reasoning over it for the edge construction becomes challenging.
Mesh operations
Once the face creation and traversal operations are working, the rest of the operations become decently easy. I was actually put aback a little at how "naive" those operations were. For example to chamfer a vertex you iterate over outgoing edges, split that edge in half, delete current vertex and create a face between vertices that resulted after splitting outgoing edges in half. To chamfer an edge it's a similar process except you chamfer end-vertices first without splitting current edge, then delete current edge and its two vertices and create a face at the end, face at the start, and a face in-between.
I've also added a subdivision modifier which subdivides the whole mesh:
 |
| Catmull-Clark subdivision |
 |
| Input |
Sending mesh to the GPU
If you ever tried creating your own vertex buffers by hand you probably have stumbled on a pitfall - drawing through index buffers allows us to save on duplicating vertices, but if you want to draw something with sharp edges like the input image above - you need to duplicate your vertices because GPU assigns normal information per-vertex. As a result - it's impossible to say what the normal should be at any of the vertices of a cuboid - averaging vertices of the face will just result in very odd looking lighting. Luckily half-edge meshes allow us to easily store such information - instead of binding non-continuous attribute data to a vertex we can bind it to half-edge. This allows us to quickly detect conditions when we need to create a new vertex index or if we can re-use the old one. As a result, the textured image below has duplicated vertices at the "seam" of two textures, but not where the texture is continuous.
 |
| Automatic UV-unwrap result |
Generation of UV coordinates for auto-generated meshes is its own beast and needs a blog post of its own. Hopefully I won't take 2 years to make another blog post, especially since I have UV-unwrap mostly working.
The Project
I've put this work into my bevy_copperfield project - a plugin for bevy engine that lets you perform all of the mentioned operations. Screenshots in this post were also made using bevy.
