An editable non-manifold polygon mesh data structure

One core data structure in the ShapeReality - 3D Modeling application is a non-manifold polygon mesh data structure. This data structure is a graph of Vertices, Edges and Faces. It takes inspiration from Blender's BMesh data structure, the Radial Edge Structure (see Nvidia SMLib - Topology documentation) and the paper Partial Entity Structure: A Compact Boundary Representation for Non-Manifold Geometric Modeling by Lee et al., but arrives at a simpler design that still has the desired feature set.

The data structure supports:

• non-manifold edges, meaning more than 2 faces can be connected to a given edge
• loose vertices (vertices with no edges connected to them)
• loose edges (edges with no faces connected to them)

The main goal of the data structure is to enable adjacency / topological queries:

• For a given vertex, which edges are connected to it?
• For a given edge, which faces are connected to it?
• For a given face, which vertices / edges make up the face?

Vertex uses

We wish to have fast insertion and deletion of elements, and no memory fragmentation. Therefore, a naive implementation such as:

struct Vertex {
  std::vector<Edge*> connected_edges;
};

would not be a good idea.

Therefore, for a given Vertex, we add a circularly linked list of VertexUses:

// circularly linked list
struct VertexUse {
  Vertex* vertex;
  VertexUse* prev;
  VertexUse* next;
  Edge* connected_edge;
};
struct Vertex {
  VertexUse* uses;
  Point* point;
};

This way, we can iterate over all Edges of a given Vertex, and not have millions of separate instances of std::vector<Edge*>.

Edge uses

This same approach is then also used for Edges, which get an accompanying circularly linked list of EdgeUses to answer the question "for a given edge, which faces are connected to it?":

struct EdgeUse {
  Edge* edge;
  EdgeUse* prev;
  EdgeUse* next;
  Face* connected_face;
};
struct Edge {
  EdgeUse* uses;
  VertexUse* v0;
  VertexUse* v1;
};

Face loop

Then, the final task is to add the FaceLoop, which answers the question "for a given face, which vertices / edges make up the given face?":

Note that we also store the vertex for a given FaceLoop segment, because v0 and v1 of an Edge are unordered.

// circularly linked list
struct FaceLoop {
  Face* face;
  FaceLoop* prev;
  FaceLoop* next;
  EdgeUse* edge;
  VertexUse* vertex;
};
struct Face {
  FaceLoop* loop;
};

Merging face loop and edge uses

Because a given EdgeUse is only attached to a single face, we can merge the FaceLoop linked list into the EdgeUse, thus reducing the need for an additional element type in the graph:

struct EdgeUse {
  Edge* edge;
  Face* attached_face;

  // radial (circularly linked list)
  EdgeUse* radial_prev;
  EdgeUse* radial_next;
  
  // face loop (circularly linked list)
  EdgeUse* loop_prev;
  EdgeUse* loop_next;
  Vertex* loop_vertex;
};

This gives us the final structure:

struct EditableMesh{
  Pool<Vertex> vertices;
  Pool<Edge> edges;
  Pool<Face> faces;
  Pool<VertexUse> vertex_uses;
  Pool<EdgeUse> edge_uses;
};

Conclusion

This post presents a simple, performant non-manifold polygon mesh data structure, that enables topological / adjacency queries.

If you want to try out the final result:

ShapeReality - 3D Modeling

ShapeReality - 3D Modeling brings 3D polygon mesh modeling tools to your iPhone and iPad. Inspect, edit, save and share .obj files.