geometry - a flexible data structure for geometries

What data structure would you use to represent meshes that are to be altered (e.g. adding or removing new faces, vertices and edges), and that have to be "studied" in different ways (e.g. finding all the triangles intersecting a certain ray, or finding all the triangles "visible" from a given point in the space)? I need to consider multiple aspects of the mesh: their geometry, their topology and spatial information.

The meshes are rather big, say 500k triangles, so I am going to use the GPU when computations are heavy.

I tried using arrays with vertices and arrays with indices, but I do not love adding and removing vertices from them. Also, using arrays totally ignore spatial and topological information, which I may need studying the mesh. So, I thought about using custom double-linked list data structures, but I believe doing so will require me to copy the data to array buffers before going on the GPU. I also thought about using BST, but not sure it fits.

Any help is appreciated. If I have been too fuzzy and you require other information feel free to ask.

Answer

Depending on your needs there are different data structure that you can use for geometry representation, before I answer your question I need to point out that geometric representation are usually chosen based on two basic factors,

1. 
   

   Topological Requirements: this includes the types of meshes you are going to store, triangles only? n-polys ? regular, irregular or semi regular?

   
   


2. 
   

   Algorithmic Requirements: Some algorithms work better on some data structure than other. This strictly depends on the type of the algorithm and you may want to use different data structures for different algorithms. For example you need to ask yourself if the structure/algorithm needs a pre-processing step? the time needed to answer specific query such as the adjacent edges of a vertex, edge ?

   
   

I will try to concisely list the most important mesh representations, while pointing out their pros and cons:

• 
  

  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.

  
  

  Cons: Edges and connectivity info are implicit and not explicitly defined making some geometric queries expensive to compute, Cannot store irregular 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. 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:

  
  

    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.

As a final note, I recommend Half-Edge or Directed Edge (if triangles only) for geometric processing, but depending on your application you may need multiple representations, since for example Half-edge are not particularly great for GPU rendering/streaming and may require extra processing for rendering.