Half Edge Data Structure

TL;DR: Definition of a half-edge data structure in cuda.

Info! Unfinished notes

I am a big fan of simple data structures like the ones used in libIGL (a N by 3 matrix of doubles for vertices and a M by 3 matrix of integers for faces). However, these data structures can not be used for efficient circulation through the faces (e.g., finding the neighbouring faces of a face is hard).

An alternative is to embrace a more complexe data structure that is more complex to define and use more memory for storing but does provide more flexibility to travel through the mesh. Amongst the popular data structures, halfedges structures are memory efficient but also offer powerful ways to travel on a mesh.

links

• Wiki on data structure
• How to: halfedge data structure
• Open Mesh’s explaination on halfedge data structures
• Euler’s formula
• Cuda best practices

Half-Edge data structures definition

From the documentation of OpenMesh.

• Each vertex references one outgoing halfedge, i.e. a halfedge that starts at this vertex (1).
• Each face references one of the halfedges bounding it (2).
• Each halfedge provides a handle to
  • the vertex it points to (3),
  • the face it belongs to (4)
  • the next halfedge inside the face (ordered counter-clockwise) (5),
  • the opposite halfedge (6),
  • (optionally: the previous halfedge in the face (7)).