Mesh data structures, vol. 2: Vertex one-rings

So let’s suppose you’re a developer working on triangle meshes. You’ve read my first article on vertex-face lists (and, inexplicably, nothing else), and now you’re running into problems with connectivity. Perhaps you want to apply a subdivision operator to your mesh, but you can’t easily figure out which vertices are neighbours, or where the edges are. Fortunately, there’s an easy way to add basic connectivity information to a vertex-face list: keep track of each vertex’s neighbours, its one-ring.

Looking at our little diagram here, the vertex v has a one-ring of {a, b, c, d, e, f}. Generally it’s easiest to work with one-rings in some sort of order — counterclockwise is preferred, because that’s how trig functions work — but you don’t necessarily need that kind of complexity.

Adding one-rings to your vertices is pretty simple. Obviously, you’ll need a container in each vertex to store one-ring indices:

typedef struct {
  float x, y, z;
  size_t n_nbrs;
  size_t* one_ring;
} vertex;

Next, every time you add a face to the mesh, you update the one-rings of its vertices. For example, when you add face vab, you add a and b to v‘s one-ring, v and b to a‘s one-ring, and v and a to b‘s one-ring.

Keeping around a one-ring list for each vertex lets you walk from vertex to vertex (and, implicitly, from edge to edge) on a mesh, which is most of what you need to do for subdivision. However, it doesn’t let you walk from face to face without some extra book-keeping.