Крылатый край

Графическое представление краевой записи. Обратите внимание, что ссылки на края выглядят как крылья.

В компьютерной графике структура с крылатыми краями данных представляет собой способ представления полигональных сеток в памяти компьютера . Это тип граничного представления , который описывает как геометрию, так и топологию модели. Используются три типа записей: записи вершин, записи ребер и записи граней. Имея ссылку на запись ребра, можно за постоянное время ответить на несколько типов запросов смежности (запросы о соседних ребрах, вершинах и гранях) . Такая информация о смежности полезна для таких алгоритмов, как подразделение поверхности .

Функции

Структура «крылатых ребер» данных явно описывает геометрию и топологию граней, ребер и вершин, когда три или более поверхности сходятся вместе и встречаются на общем ребре. Порядок таков, что поверхности упорядочены против часовой стрелки относительно исходной ориентации края пересечения. Более того, такое представление допускает численно нестабильные ситуации, подобные изображенной ниже.

Структура данных «крылатых ребер» позволяет быстро перемещаться между гранями, ребрами и вершинами благодаря явно связанной структуре сети. Он обслуживает запросы смежности в постоянное время с небольшими затратами на хранение. Эта богатая форма задания неструктурированной сетки отличается от более простых спецификаций полигональных сеток , таких как список узлов и элементов или подразумеваемая связность регулярной сетки . Альтернативой структуре данных «крылатого ребра» является структура данных «полукрая» .

Структура и псевдокод

Записи граней и вершин относительно просты, а записи ребер более сложны.

• Для каждой вершины в ее записи хранится только положение вершины (например, координаты) и ссылка на одно инцидентное ребро. Остальные ребра можно найти, следуя дальнейшим ссылкам на ребре.
• Аналогично, каждая запись лица хранит ссылку только на один из краев, окружающих лицо. Нет необходимости хранить направление края относительно грани (против часовой стрелки или по часовой стрелке), поскольку для получения этой информации грань можно легко сравнить с собственными левой и правой гранями ребра.
• Наконец, структура краевой записи выглядит следующим образом. Предполагается, что ребро направлено. Запись ребра содержит две ссылки на вершины, составляющие конечные точки ребра, две ссылки на грани по обе стороны от ребра и четыре ссылки на предыдущее и следующее ребра, окружающие левую и правую грань.

Короче говоря, запись ребра имеет ссылки на все соседние записи, как при обходе соседней вершины, так и при обходе соседней грани.

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;
}

См. также

• Четырехгранная структура данных
• Комбинаторные карты
• Двусвязный список ребер
• Двойной связанный список лиц
• Структура данных полуребра

Внешние ссылки

• Баумгарт, Брюс Г. (1972). Изображение многогранника с крылатыми ребрами (PDF) (Технический отчет). Стэнфордский университет. CS-TR-72-320.
• Баумгарт, Брюс Г. (1975). «Представление многогранника для компьютерного зрения» (PDF) . AFIPS '75: Материалы национальной компьютерной конференции и выставки 19–22 мая 1975 г. АКМ Пресс. стр. 589–596. дои : 10.1145/1499949.1500071 . ISBN  978-1-4503-7919-9 . S2CID   9040571 .
• Шене, К.-К. (2011). «Крылатая структура данных» . CS3621 Введение в вычисления с примечаниями по геометрии . Мичиганский технологический университет.
• «Крылатый край» . Многогранные структуры данных: CS488/688: Введение в интерактивную компьютерную графику, Университет Ватерлоо . Пизанский университет.