8

I ran into half-edges as part of the result of a Delaunay Triangulation library, but can't find an actual definition of what one is.

I understand vertices, edges and faces, but can't find a concrete definition of a half-edge.

Mark A. Ropper
  • 287
  • 2
  • 6
  • as far as i know a half edge is a directed edge. That is, an edge with a defined begining and end rather than two points where order is irrelevant. I don't know how that would fit into a triangulation algorithm but i hope this helps. – Sebastián Mestre Dec 12 '17 at 00:54
  • Here is a good practical introduction on the topic: https://fgiesen.wordpress.com/2012/02/21/half-edge-based-mesh-representations-theory/ – Julien Guertault Dec 13 '17 at 16:08

1 Answers1

13

A half-edge is an edge split along its length, and having a directional component, that is, a beginning vertex and an end vertex. Where two polygons share an edge, each polygon gets a single half-edge between the same two vertices, which will have opposite directions if the winding order is consistent. These half-edges will have references to one another as two halves of a pair.

The full half edge data structure stores for each half-edge:

  • The polygon it belongs to
  • Previous and next half edges within the polygon
  • Its pair half-edge in a neighbouring polygon
  • Its origin vertex

This structure allows you to extract all sorts of connectivity information from a mesh, such as which edges or polygons lie around a particular vertex, simply by traversing the half-edges. There's a good article explaining it here.

russ
  • 2,392
  • 9
  • 18
  • Thank you for your answer, I think I was partly thrown by the dissimilarity between the "half-edges" that the library provided (simply an array of indices) and the more fully fledged structures which came up when searching for half-edges. – Mark A. Ropper Dec 12 '17 at 23:46