Return to Answer

• Face Based: The simplest form stores a set of faces, it can store faces(indices) and separate vertices or you can simply construct faces using vertex positions, this structure is more suitable to store one type of face/polys (e.g. tri) otherwise the implementation becomes complex with little benefit.

  Pros: Cache friendly(usually). Efficient to store in memory, used in many file formats (e.g. Obj, VRML). Usually used in games.

• Edge Based: This defines a face in terms of the edges making a face, each edge stores a reference for it two end point vertices. It's also common for a vertex to have a reference for it's owner edge this is great for efficiently traversing the data structure. An example implementation is the winged-edge data structure. Edges can also store reference to the next and previous edges, which makes good candidate for traversing the structure.

  Pros: Can represent arbitrary polygon, good for traversing adjacent edges.

  Cons: Not so great for memory consumption, traversing a ring still needs distinctive cases.

  

• Half-Edge Based: Similar to Edge-Based with the very important distinction that it defines each edge as a two distinct directed Half-Edges instead of a bidirectional single Edge.

  

  The importance boils down to that Half-edges are oriented consistently in counter-clock wise around each face modelling a ring-loop explicitly, and hence making traversal easier by avoiding some extra cases like asking at which vertex in the face are we standing. Getting a good implementation for this structure is hard so I recommend using OpenMesh which is a great implementation of the structure and many other algorithms.

  Pros: Great flexibility with traversal that other structures lack, can model arbitrary polygons, can explicitly model empty faces. Some implementations (AFAIK) can model irregular meshes. Great for geometric algorithms, and makes it easy to mix faces of different vertex count in one mesh.

  Cons: Harder to implement, not so memory friendly, and usually requires a lot of Heap allocations.

  A sample implementation for the half-edge data structure would look like this:

• Face Based: The simplest form stores a set of faces, it can store faces(indices) and separate vertices or you can simply construct faces using vertex positions, this structure is more suitable to store one type of face/polys (e.g. tri) otherwise the implementation becomes complex with little benefit.

  Pros: Cache friendly(usually). Efficient to store in memory, used in many file formats (e.g. Obj, VRML). Maps nicely to GPU rendering, usually used in games.

• Edge Based: This defines a face in terms of the edges making a face, each edge stores a reference for it two end point vertices. It's also common for a vertex to have a reference for it's owner edge this is great for efficiently traversing the data structure. An example implementation is the winged-edge data structure. Edges can also store reference to the next and previous edges, which makes good candidate for traversing the structure.

  Pros: Can represent arbitrary polygon, good for traversing adjacent edges.

  Cons: Not so great for memory consumption, traversing a ring still needs distinctive cases. Requires extra processing for GPU rendering.

  

• Half-Edge Based: Similar to Edge-Based with the very important distinction that it defines each edge as a two distinct directed Half-Edges instead of a bidirectional single Edge.

  

  The importance boils down to that Half-edges are oriented consistently in counter-clock wise around each face modelling a ring-loop explicitly, and hence making traversal easier by avoiding some extra cases like asking at which vertex in the face are we standing. Getting a good implementation for this structure is hard so I recommend using OpenMesh which is a great implementation of the structure and many other algorithms.

  Pros: Great flexibility with traversal that other structures lack, can model arbitrary polygons, can explicitly model empty faces. Some implementations (AFAIK) can model irregular meshes. Great for geometric algorithms, and makes it easy to mix faces of different vertex count in one mesh.

  Cons: Harder to implement, not so memory friendly, and usually requires a lot of Heap allocations. Requires extra processing for GPU rendering.

  A sample implementation for the half-edge data structure would look like this:

• Edge Based: This defines a face in terms of the edges making a face, each edge stores a reference for it two end point vertices. It's also common for a vertex to have a reference for it's owner edge this is great for efficiently traversing the data structure. An example implementation is the winged-edge data structure. Edges can also store reference to the next and previous edges, which makes good candidate for traversing the structure.

  Pros: Can represent arbitrary polygon, good for traversing adjacent edges.

  Cons: Not so great for memory consumption, traversing a ring still needs distinctive cases.

  

• Half-Edge Based: Similar to Edge-Based with the very important distinction that it defines each edge as a two distinct directed Half-Edges instead of a bidirectional single Edge.

  

  The importance boils down that Half-edges are oriented consistently in counter-clock wise around each face modelling a ring explicitly, and hence making traversal easier by avoiding some extra cases like asking at which vertex in the face are we standing. Getting a good implementation for this structure is hard so I recommend using [OpenMesh] 2] which is a great implementation of the structure and many other algorithms.

  Pros: Great flexibility with traversal that other structures lack, can model arbitrary polygons, can explicitly model empty faces. Some implementations (AFAIK) can model irregular meshes. Great for geometric algorithms, and makes it easy to mix faces of different vertex count in one mesh.

  Cons: Harder to implement, not so memory friendly, and usually requires a lot of Heap allocations.

  A sample implementation for the half-edge data structure would look like this:

• Edge Based: This defines a face in terms of the edges making a face, each edge stores a reference for it two end point vertices. It's also common for a vertex to have a reference for it's owner edge this is great for efficiently traversing the data structure. An example implementation is the winged-edge data structure. Edges can also store reference to the next and previous edges, which makes good candidate for traversing the structure.

  Pros: Can represent arbitrary polygon, good for traversing adjacent edges.

  Cons: Not so great for memory consumption, traversing a ring still needs distinctive cases.

  

• Half-Edge Based: Similar to Edge-Based with the very important distinction that it defines each edge as a two distinct directed Half-Edges instead of a bidirectional single Edge.

  

  The importance boils down to that Half-edges are oriented consistently in counter-clock wise around each face modelling a ring-loop explicitly, and hence making traversal easier by avoiding some extra cases like asking at which vertex in the face are we standing. Getting a good implementation for this structure is hard so I recommend using OpenMesh which is a great implementation of the structure and many other algorithms.

  Pros: Great flexibility with traversal that other structures lack, can model arbitrary polygons, can explicitly model empty faces. Some implementations (AFAIK) can model irregular meshes. Great for geometric algorithms, and makes it easy to mix faces of different vertex count in one mesh.

  Cons: Harder to implement, not so memory friendly, and usually requires a lot of Heap allocations.

  A sample implementation for the half-edge data structure would look like this:

• Edge Based: This defines a face in terms of the edges making a face, each edge stores a reference for it two end point vertices. It's also common for a vertex to have a reference for it's owner edge this is great for efficiently traversing the data structure. An example implementation is the winged-edge data structure. Edges can also store reference to the next and previous edges, which makes good candidate for traversing the structure.

  Pros: Can represent arbitrary polygon, good for traversing adjacent edges.

  Cons: Not so great for memory consumption, traversing a ring still needs distinctive cases.

  

• Half-Edge Based: Similar to Edge-Based with the very important distinction that it defines each edge as a two distinct directed
    Half-Edges instead of a bidirectional single Edge. The importance
  boils down that Half-edges are oriented consistently in counter-clock wise around each face modelling a ring explicitly, and hence making
  traversal easier by avoiding some extra cases like asking at which
  vertex in the face are we standing. Getting a good implantation for this structure is hard so I recommend using OpenMesh which is a great implementation of
    the structure and many other algorithms.

  Pros: Great flexibility with traversal that other structures lack, can model artibtraty polygons, can explicitly model empty faces. Some implementations (AFAIK) can model irregular mesh. Great for geometric algorithms, and makes easy to mix faces of different vertex count in one mesh.

  Cons: Harder to implement, not so memory friendly, and usualy requires alot of Heap allocations.

There is also Directed Edge Data Structure, which is a memory efficient implementation of the half edge that is designed for triangle meshes.

• Edge Based: This defines a face in terms of the edges making a face, each edge stores a reference for it two end point vertices. It's also common for a vertex to have a reference for it's owner edge this is great for efficiently traversing the data structure. An example implementation is the winged-edge data structure. Edges can also store reference to the next and previous edges, which makes good candidate for traversing the structure.

  Pros: Can represent arbitrary polygon, good for traversing adjacent edges.

  Cons: Not so great for memory consumption, traversing a ring still needs distinctive cases.

  

• Half-Edge Based: Similar to Edge-Based with the very important distinction that it defines each edge as a two distinct directed Half-Edges instead of a bidirectional single Edge.

  

  The importance boils down that Half-edges are oriented consistently in counter-clock wise around each face modelling a ring explicitly, and hence making traversal easier by avoiding some extra cases like asking at which vertex in the face are we standing. Getting a good implementation for this structure is hard so I recommend using [OpenMesh] 2] which is a great implementation of the structure and many other algorithms.

  Pros: Great flexibility with traversal that other structures lack, can model arbitrary polygons, can explicitly model empty faces. Some implementations (AFAIK) can model irregular meshes. Great for geometric algorithms, and makes it easy to mix faces of different vertex count in one mesh.

  Cons: Harder to implement, not so memory friendly, and usually requires a lot of Heap allocations.

  A sample implementation for the half-edge data structure would look like this:

    struct Vertex
    {
       Vector3      Position;
       HalfEdge*    halfedge; // outgoing halfedge
    };
    
    struct HalfEdge
    {
      Vertex*   vertex; 
      Face*     face;
      HalfEdge*   next;
      HalfEdge*   prev;
    };
    
    struct Face
    {
      HalfEdge*   halfEdge; // any halfedge
    };
   

• There is also Directed Edge Data Structure, which is a memory efficient implementation of the half edge that is designed for triangle meshes.