Home GitHub Rss

A simple mesh adjacency data structure


Considering a complex mesh data structure like half edge or bmesh? Here is a trick that may save you some energy. Face indices (which map faces to vertices) can be transformed into a multi-map which goes the reverse direction (mapping vertices to faces). This can be used to perform adjacency traversals efficiently and is sufficient for many mesh processing problems.


The standard way to store a 3D mesh is an indexed triangle mesh which looks something like the following:

vec3_t* vertices;
uint32_t indices;

Each element of indices refers to an element in the vertices array, and is the corner of a face. For a triangle mesh, every 3 elements of indices constitutes a face. The main advantage of this structure is it allows vertex information to be shared between faces, given that faces are often conjoined.

The essential topology of the mesh is all here. But it is not efficient to query. Mesh processing usually involves traversing the mesh in a logical and local manner, including:

To do this efficiently we need to add an adjacency data structure that stores local connections, such as the two examples mentioned previously. As Fabien describes, implementing these is challenging project. There are a lot of invariants to keep track of. It will probably be buggy the first time around. Furthermore it often imposes restrictions on the kinds of meshes you can work with (eg. closed manifolds, manifolds with boundary, etc).

Can we get away with anything simpler and easier?

Inverting the index

Given a face we can already lookup which vertices it contains.

face to vertex

What’s missing is the ability to go the other direction, finding the faces each vertex belongs to.

vertex to face

If we can achieve this, then all other queries become possible. For example, to find neighboring faces of a face:

The challenge is a face has a fixed number of corners, and each corner references exactly one vertex. But a vertex can belong to any number of faces. This suggests the need for a growing storage mechanism, or a linked structure, which come with complexity or performance headaches.

Alternatively, consider the mesh indices as a function g : F -> V, mapping face (corner) indices to vertex indices. We are storing this function in it’s Cartesian product form g \subseq F x V as a list of pairs! Because g is not 1-1, it’s not an invertible. But, we can still just flip it around to form a reverse relation g' : V -> F. For each pair (f, v) just replace it with (v, f).

Implementing a reverse index

This new relation constitutes a multi-map which maps vertex indices to face corner indices. Multi maps can be implemented efficiently as an array of sorted pairs [(vertex, face)], where each vertex and face can be appear as many times as needed.

using ReverseIndex = std::pair<uint32_t, uint32_t>;
ReverseIndex* reverse_indices = ...;

To look up the faces a vertex belongs to, simply binary search the array. For example, to compute degree:

struct reverse_index_less {
    bool operator()(const ReverseIndex& x, const ReverseIndex& y) {
        return x.first < rhs.y;

int degree(uint32_t v0)
     auto lookup = std::make_pair(v0, 0);
     auto range = std::equal_range(reverse_indicies, reverse_indicies + n, lookup, reverse_index_less());
     return (int)(range.second - range.first);

Or to compute vertex normals from face normals:

vec3_t average_normal(uint32_t v0, vec3_t* face_normals)
     auto lookup = std::make_pair(v0, 0);
     auto i = std::lower_bound(reverse_indicies, reverse_indicies + n, lookup);

     vec3_t n;

     while (i != reverse_indices + n && i->first == v0) {
        uint32_t face_index = (i->second) / 3;
        n += face_normals[face_index];

     return n.normalized();

To construct the index you just need to sort.

ReverseIndex* reverse_indices = new ReverseIndex[index_count];

for (int i = 0; i < index_count; ++i) {
    reverse_indices[i] = std::make_pair(indices[i], i);

std::sort(reverse_indices, reverse_indices + index_count);


It’s easy to implement, but what are we missing? Let’s summarize some of it’s limitations:

However, besides it’s simplicity it has a few additional strengths: