Half-edge (полурёбра)
Структура данных, описывающая топологию сетки: каждое ребро делится на два направленных полуребра — по одному для каждой смежной грани.
Каждое полуребро хранит исходную вершину, близнеца (то же ребро в обратном направлении), следующее полуребро вокруг своей грани и саму грань. Эти указатели позволяют за константное время обходить соседей вершины, границу грани или обе стороны ребра — чего простой список треугольников не умеет без повторного просмотра всего.
Структура происходит от DCEL Мюллера и Препараты (1978) и лежит в основе инструментов моделирования (BMesh в Blender, CGAL) и алгоритмов вроде схлопывания рёбер и подразделения. Цена — память и то, что чисто представлены только многообразные поверхности: у ребра, общего для трёх граней, нет единственного близнеца.