# Blog 3.0 I make games.

## Procedural Generation For Dummies: Half Edge Geometry

## Procedural City Generation For Dummies Series

- Procedural Generation For Dummies: Half Edge Geometry
- Procedural Generation For Dummies: Galaxy Generation
- Procedural Generation For Dummies: Lot Subdivision
- Procedural Generation For Dummies
- Procedural Generation For Dummies: Road Generation

My game, Heist, is a cooperative stealth game set in a procedurally generated city. This series of blog posts is an introduction to my approach for rapidly generating entire cities. If you’re interested in following the series as it’s released you can follow me on Twitter, Reddit or Subscribe to my RSS feed

A lot of the code for my game is open source - the code applicable to this article can be found here. Unfortunately it has some closed source dependencies which means you won’t be able to compile it (I hope to fix that soon) but at least you can read along (and criticise my code). I should point out that this code is in a bit of a state of flux at the moment - I’ve just recently started an overhaul of some of its core components - so some of it which is only half overhauled may read a little strangely right now!

## Messy Meshes

One thing which I have to deal with all the time in procedural generation is *meshes* - that is things which can be represented as a set of vertices, edges and faces. They appear in road generation (roads, junctions and blocks), floor plan generation (wall join, walls and rooms) and navmesh generation (faces are walkable areas).

Computational geometry is an infamously tricky subject, so it’s important to have a good set of structures for representing the data you’re working with and a good set of tools to manipulate that data.

## Indexed Meshes

Most programmers who have worked with graphics will be familiar with an *indexed mesh*. This is a very simple structure:

- List of vertices
- List of ( List of indices )

We have a flat list of vertices (positions) in a completely arbitrary order. Each face is a list of *indices*, the indices of the vertices which make up this face. Our mesh is then a list of faces - a list of list of indices. If we want to specialise to purely graphical meshes then there is an easy optimisation to make here; since we know every face has three sides simply store the indices as one continuous list (with N, N+1 and N+2 as the three corners). However we want to be a little more general than that so in this system a face is any set with three *or more* vertices.

Here’s an example:

We’ve got two shapes, A and B. Here’s what that would look like in indexed mesh form:

```
Vertices: [ (0, 0), (10, 0), (10, 10), (5, 10), (0, 10), (0, 5), (5, 5) ]
Faces: [[4, 3, 6, 5], [0, 5, 6, 3, 2, 1]]
```

The order of the vertices here is totally arbitrary. The *indices* in each face are stored in clockwise order around the face.

This is simple to build, and simple to enumerate but it doesn’t really offer any good tools to help you build correct geometry. For examples let’s add another face

```
[0, 6, 5, 1]
```

As you can see below this face overlaps the other faces, is incorrectly wound (anticlockwise) *and* is self intersecting! These are all properties which we want to avoid and, if possible, should be *impossible* to construct.

## Half-Edge Meshes

Indexed meshes are a very *topographical* way of representing a mesh - they contain the information about positions and not really much else. Checking for the three critical properties (winding order, overlapping and self-intersection) would require a series of costly vector operations. With a Half-Edge mesh we keep a lot of the *topological* information about the mesh around which means that checking all of these properties becomes just a series of pointer lookups and equality comparisons.

Let’s create the same shape as before, but with a half-edge representation:

I know this looks complex, but that’s because we’re keeping so much more useful information around! Let’s look through the parts one at a time:

#### Vertices

These are represented by the red dots in the diagram. A vertex contains two pieces of information:

- Position
- List of edges
*starting*at this vertex

That’s it! You can extend this model to store more per vertex attributes (normals, texture coordinates etc) but I’ve not yet had a use for this.

#### Half Edges

These are represented by black arrows in the diagram. These are the key part of this structure - every connection between two vertices is a *one way* edge - hence the name *half edge* because each complete edge is represented by two one-way halves. A half edge contains 4 pieces of information:

- Sibling Edge (opposite direction edge)
- End Vertex
- Face which this edge borders (possibly null, if there is no such face). This is represented by the blue arrows in the diagram.
- Next edge around the face this edge borders (possibly null, if there is no such face). This is represented by the green arrows in the diagram.

#### Faces

These are represented by the pale green circles (labelled with the same letters as in the previous diagram). The faces are actually very simple, containing just one single piece of information:

- An arbitrary edge bordering this face

That’s it! With just this information we can answer a lot of useful queries about the mesh and also ensure that those three critical properties (winding order, overlapping and self-intersection) are maintained at all times.

## Critical Properties

It may not be entirely obvious how those critical properties are maintained in this system and in fact they *can* be violated in certain circumstances - but constructing such an invalid mesh is quite difficult and generally as soon as you try to *do* anything with it the system is going to notice something is broken and immediately throw an exception.

#### Winding Order

Here’s the example image from before cut down to just show two edges attached to the two faces. If we tried to reverse A (so it was incorrectly wound) it would be impossible - the edge going up along the right hand side of A is already in use. Since an edge can only ever be assigned to one face if we ever find ourselves trying to attach an edge to another face we know we’re trying to construct invalid geometry.

This property can be violated if you construct two *completely independent* faces (sharing no vertices) - one clockwise, and one anticlockwise. As soon as you try to connect these faces up in any way it will be impossible.

My implementation actually has an additional check to catch invalid winding much earlier than this. When you construct a new mesh object you specify which winding you want. Whenever a new face is constructed it’s winding order is checked (geometrically, by looking at the area of the face and checking if it is negative).

#### Self Intersection

The right hand face here is clearly broken and this is another example of how it’s sometimes possible to construct broken geometry - that face does not violate any of the invariants of a half edge structure. However if you have a self intersecting shape at least one of the edges *must* be incorrectly wound (in this case the top right horizontal edge). This means all self intersecting shapes become a subset of the winding problem and are solved in the same way - as soon as you try to connect that incorrect edge to anything else the error will be detected.

#### Overlapping

Here we have another clearly broken situation - the larger face overlaps the smaller face. In this case the solution is quite obvious from the image - the grey edges are already in use for the smaller face so we can’t possibly assign them to the larger face!

## These Vertices Were Made For Walking

Let’s have a look at the most simple query you can perform: finding all the vertices around a face. With an indexed mesh this is obviously rather trivial:

```
for (index in face)
yield vertices[index]
```

This is pretty much exactly what an indexed mesh is designed for! With a half edge mesh this is slightly more complex. The half edges around a face all point to the *next* half edge around the same face, in this way they form a circular singly linked list around the face. Additionally a face points to an arbitrary bordering edge. These two pieces of information are all you need:

```
first = face.edge
edge = first
do
{
yield edge.EndVertex
edge = edge.Next
} while (edge != first)
```

Just keep following those “next” pointers until we get back to where we started!

Many queries can be implemented on a half edge mesh using the same concept - just keep chasing pointers! For example let’s say we want to find all neighbouring faces to a given face. With an indexed mesh this is a nightmare:

```
# assume we have a variable "face" which is the start of the query
for (neighbour in faces)
if (neighbour == face)
continue;
for (var i = 0; i < neighbour.Length; i++)
find = face.IndexOf(index)
if (find != -1 && face[(find + 1) % face.Length)] == neighbour[(i + 1) % neighbour.Length])
yield neighbour;
```

I’m not certain that’s correct (it’s just blog pseudocode, gimmie a break) but essentially what I’m doing here is enumerating *all* vertices of *all* other faces and trying to find pairs which are in the query face, but reversed. I’ve almost certainly got some off-by-one errors here, and looking back on it I think I’ve got one of the indices the wrong way around. The point is this is annoying code to write and, even worse, the algorithmic complexity is horrible - something like O(#Faces * #AvgVerticesInFace).

Here’s how we do the same thing with a half edge mesh:

```
first = face.edge
edge = first
do
{
if (edge.Sibling.Face != null)
yield edge.Sibling.Face
edge = edge.Next
} while (edge != first)
```

I hope you’ll agree that’s much friendlier and far easier to read! All we’re doing here is enumerating the edges around the face (in the exactly same way we did in the previous example) and then jumping across to the sibling edge and getting the attached face. This was really easy to write and is far less algorithmically complex - O(#EdgesInThisFace).

A few more of the queries which can be done easily in a half edge mesh:

- Edges around face
- Vertices around face
- Faces around face
- Edges from vertex
- Faces around vertex
- Pathfinding (and other graph based algorithms)

If you can’t figure out how to implement some of these queries post a comment below and I’ll do another post explaining them in more detail!

## How Does This Help?

Here’s a concrete example of how these kinds of queries can help - we can use them to detect even more invalid geometry (winding order, overlapping and self-intersection). Let’s look at the overlapping case, here’s a nasty piece of overlapping geometry which would not be detected normally:

This overlap doesn’t generate any invalid edges and would likely *never* be detected by the normal checks. However, if we can do intersection checks (just normal 2D collision detection) we can check for this situation quite easily:

```
for (vertex in face)
for (neighbour in vertex.Faces()) # <-- .Faces() is the query
if (face.Intersects(neighbour))
throw new InvalidMeshException("Oh no!");
```

Pretty simple - we just query every vertex in the proposed new face for neighbours and then check if we overlap any of those faces. This won’t catch *all* invalid overlaps but, as with many of these checks, it ratchets up the difficulty of accidentally creating invalid geometry.

## Conclusion

Half Edge meshes are a more powerful way to represent meshes than a traditional indexed mesh. I use them as the basis for many of my procedural generators where they help ensure that the generator can only ever generate valid geometry.

Comments »## archive

- Procedural Generation For Dummies: Half Edge Geometry 30 Mar 2016
- Fixed Permalinks 21 Mar 2016
- Procedural Generation For Dummies: Galaxy Generation 14 Jan 2016
- 2015 Retrospective 04 Jan 2016
- Procedural Generation For Dummies: Lot Subdivision 27 Dec 2015
- Procedural Generation For Dummies 11 Dec 2015
- Procedural Generation For Dummies: Road Generation 11 Dec 2015
- Deferred Transparency 09 Oct 2015
- Xna In 2015 24 Aug 2015
- Node Machine 26 Jun 2015
- Procedural Generation Of Facades And Other Miscellania 29 May 2015
- This Path Was Made For Walking 23 Apr 2015
- Cross Chunk Navmeshes 27 Mar 2015
- Changelog 27 06 Mar 2015
- Drawing Stuff On Other Stuff With Deferred Screenspace Decals 27 Feb 2015
- Random Gibberish 22 Feb 2015
- This Wall Is Sticky 17 Feb 2015
- Changelog 25 08 Feb 2015
- 2014 Retrospective 13 Jan 2015
- Super Sonic Sound 08 Jan 2015
- Sandboxing Is Dead Long Live Sandboxing 22 Dec 2014
- Changelog 22 B 14 Dec 2014
- Changelog 22 07 Dec 2014
- Possible Interruption To Service 06 Dec 2014
- The Game Programmer Awakens (changelog 21b) 30 Nov 2014
- The Return Of The Programmer (changelog 21) 16 Nov 2014
- The Return Of The Vending Machines 26 Oct 2014
- There Are Vending Machines Everywhere 16 Oct 2014
- Changelog 20 12 Oct 2014
- Ragdolls Are Hard 05 Oct 2014
- Changelog 19 28 Sep 2014
- The Return Of The Game Programmer 21 Sep 2014
- The Ball Is Picked Back Up 17 Aug 2014
- It's Good To Be Back 03 Aug 2014
- Serious Injury 21 Jul 2014
- We Marveled At Our Own Magnificence As We Gave Birth To Ai 14 Jul 2014
- Changelog 17 06 Jul 2014
- Changelog 16 29 Jun 2014
- Happy Birthday 22 Jun 2014
- Changelog 14 15 Jun 2014
- Losing My Way 08 Jun 2014
- Wildcard 02 Jun 2014
- Changelog 13 25 May 2014
- Changelog 12 16 May 2014
- WAI NO VIDEO (Again) 11 May 2014
- Changelog 10 04 May 2014
- Changelog 9 27 Apr 2014
- Changelog 8 20 Apr 2014
- Long Overdue Style Upgrade 18 Apr 2014
- WAI NO VIDEO 13 Apr 2014
- Changelog 7 07 Apr 2014
- Changelog 6 30 Mar 2014
- Changelog 5 23 Mar 2014
- Changelog 4 16 Mar 2014
- This Is Madness! 11 Mar 2014
- Changelog 3 09 Mar 2014
- Changelog 2 02 Mar 2014
- Changelog 1 23 Feb 2014
- Changelog 0 15 Feb 2014
- Payday The Heist 2 13 Jan 2014
- 730 Days Later 01 Jan 2014
- I Just Needed A Rest 12 Nov 2013
- Splinter Cell Blacklist 27 Aug 2013
- Gruelling Homework Assignment 26 Aug 2013
- Scripting Is Dead Long Live Scripting 14 Aug 2013
- The Reports Of My Death Are Greatly Exaggerated 05 Aug 2013
- 27 Gigawatts Of Cake 11 Jun 2013
- Trees Are Well Behaved 22 May 2013
- A Brief Project Update 14 May 2013
- Finite State Machines (are Boring) 16 Apr 2013
- Pathfinding 10 Apr 2013
- Artificial Stupidity Series 08 Apr 2013
- Valve Need To Stop Reading My Mind (and Other Miscellanea) 20 Mar 2013
- Elements Of Style 26 Feb 2013
- Moving To Axmingholmesbury 23 Feb 2013
- The Future Is Steamy 08 Feb 2013
- Mathematical Trickery 22 Jan 2013
- Thinking Aloud About Release 09 Jan 2013
- Game Developers Don't Make Timetables 03 Jan 2013
- What Is Heist? 20 Dec 2012
- How Does Procedural Generation Work? 14 Dec 2012
- Why Does Heist Keep Crashing? 07 Dec 2012
- What Isn't Procedural Generation? 23 Nov 2012
- What Is Procedural Generation? 18 Nov 2012
- Procedural Generation Series 15 Nov 2012
- Packet Encoding(3) 12 Nov 2012
- Packet Encoding(2) 08 Nov 2012
- Packet Encoding 07 Nov 2012
- Deployment Hax 28 Oct 2012
- Wibbly Wobbly Pipey Wipey 24 Oct 2012
- New Release(2) 24 Oct 2012
- New Release 20 Oct 2012
- Say What? 17 Oct 2012
- Get Up And Initiate That Session 15 Oct 2012
- Topological My Dear Watson 14 Oct 2012
- Omg Wtf Multiplayer 13 Oct 2012
- Full Steam Ahead 24 Sep 2012
- You Should Check Out Greenlight 01 Sep 2012
- It's Full Of Entities 20 Aug 2012
- Persistence 06 Aug 2012
- I'll Be Back 01 Aug 2012
- Artificial Stupidity 24 Jul 2012
- Overindulgence 16 Jul 2012
- Not My Cup Of Tea 09 Jul 2012
- Artsy Stuff 02 Jul 2012
- This Was A Triumph 25 Jun 2012
- Multiplayer Release 18 Jun 2012
- Fortnightly Fun 10 Jun 2012
- New Blog 31 May 2012