Half-edge
Una struttura dati che cattura la topologia di una mesh dividendo ogni spigolo in due half-edge orientati, uno per ciascuna faccia adiacente.
Ogni half-edge memorizza il vertice di origine, il proprio gemello (lo stesso spigolo percorso nell'altro verso), l'half-edge successivo lungo la faccia e la faccia stessa. Grazie a questi puntatori si percorrono in tempo costante i vicini di un vertice, il bordo di una faccia o i due lati di uno spigolo: cosa impossibile con una semplice lista di triangoli, a meno di riscandire tutto.
Discende dalla DCEL di Muller e Preparata (1978) ed è la spina dorsale degli strumenti di modellazione (BMesh di Blender, CGAL) e di algoritmi come il collasso di spigolo e la suddivisione. Il prezzo è la memoria, e il fatto che rappresenti in modo pulito solo superfici manifold: uno spigolo condiviso da tre facce non ha un unico gemello.