Структура крылатое ребро — это способ представления полигональной сетки в компьютерной памяти. Это один из типов граничных представлений, описывающий как геометрию, так и топологию модели. Используются три типа записей: записи вершин, записи рёбер и записи граней. Имея ссылку на запись рёбра, можно за постоянное время ответить на различные запросы о соседстве (запросы о соседних рёбрах, вершинах и гранях). Такая информация о соседстве полезна для алгоритмов, например, для .
Детали Структура крылатое ребро явно описывает геометрию и Топология граней, ребер и вершин, когда три или более поверхности сходятся и встречаются на общем ребре. Порядок задаётся так, что поверхности упорядочены против часовой стрелки относительно внутренней ориентации ребра пересечения. Более того, такое представление допускает численно нестабильные ситуации, подобные изображённой ниже.
Структура крылатое ребро обеспечивает быструю навигацию между гранями, рёбрами и вершинами благодаря явно связанной структуре сети. Она позволяет выполнять запросы о соседстве за постоянное время при минимальных накладных расходах на хранение. Такая богатая форма спецификации неструктурированной сетки контрастирует с более простыми способами представления полигональных сеток, такими как список узлов и элементов или неявная связность регулярной решётки. Альтернативой структуре данных «крылатое ребро» является структура данных «полуребро».
Структура и псевдокод Записи вершин и граней относительно просты, в то время как запись ребра более сложна. Запись каждой вершины хранит только её положение (например, координаты) и ссылку на одно инцидентное ребро. Другие рёбра можно найти, следуя по дальнейшим ссылкам в ребре. Аналогично, каждая запись грани хранит только ссылку на одно из рёбер, окружающих грань. Нет необходимости хранить направление ребра относительно грани (против часовой стрелки или по часовой стрелке), поскольку эту информацию можно тривиально получить, сравнив грань с собственными левой и правой гранями ребра. Наконец, структура записи ребра следующая. Предполагается, что ребро направлено. Запись ребра содержит две ссылки на вершины, составляющие конечные точки ребра, две ссылки на грани по обе стороны от ребра и четыре ссылки на предыдущие и следующие рёбра, окружающие левую и правую грань.
class Edge { Vertex *vert_origin, *vert_destination; Face *face_left, *face_right; Edge *edge_left_cw, *edge_left_ccw, *edge_right_cw, *edge_right_ccw;
class Vertex { float x, y, z; Edge *edge;
class Face { Edge *edge;
См. также Quad-edge
Двусвязный список рёбер
полурёберная структура данных
Примечания
Ссылки
Категория:САПР Категория:Структуры данных компьютерной графики