Previous | Next --- Slide 38 of 41
Back to Lecture Thumbnails

This sequence of slides provides a great motivation for the half-edge structure. We want:

  • Efficient lookup of adjacent vertices/edges/faces from a vertex/face/edge of the mesh
  • Low memory footprint (compared even to the sparse incidence-based representations described on the previous slide)
  • The ability to efficiently insert or remove vertices from the mesh

The half-edge data structure achieves these goals. However, it relies on the manifold nature of the surface to achieve the low-memory-footprint goal while also maintaining the ability to provide adjacency efficiently. So in exchange for achieving these goals, the half-edge data structure sacrifices some generality (as compared to a basic polygon soup representation).