Полуреберное представление

Полуреберное представление — это способ хранения и обработки трёхмерных полигональных сеток (мешей) в компьютерной графике и геометрическом моделировании, при котором для каждого ребра сетки хранится информация о двух инцидентных ему гранях (полигонах) и двух вершинах, а также о направлении обхода ребра относительно каждой грани. Данная структура данных является разновидностью реберного представления (winged-edge) и обеспечивает эффективный доступ к топологической информации о сетке, необходимый для многих алгоритмов геометрической обработки.

История и происхождение

Полуреберное представление было разработано в 1980-х годах как усовершенствование winged-edge представления, предложенного Брюсом Баумгартом в 1975 году. Основной целью разработки было устранение ограничений winged-edge, связанных с необходимостью хранения информации о порядке обхода вершин и граней для каждого ребра. Полуреберное представление впервые было описано в работах Марти Мянтюля (Martti Mäntylä) и других исследователей в области твердотельного моделирования. Оно стало стандартной структурой данных в таких системах геометрического моделирования, как ACIS и OpenCASCADE, а также широко используется в библиотеках компьютерной графики, например, в OpenMesh и CGAL.

Структура данных

Полуреберное представление основано на концепции полуребра (half-edge) — направленного ребра, которое принадлежит ровно одной грани. Каждое физическое ребро сетки представляется двумя полуребрами противоположной ориентации. Такая организация позволяет однозначно определить топологию сетки и выполнять операции обхода.

Основные элементы

Структура данных полуреберного представления включает четыре основных типа объектов:

• Вершина (Vertex): хранит координаты точки в пространстве и указатель на одно из полуребер, исходящих из этой вершины.
• Грань (Face): хранит указатель на одно из полуребер, принадлежащих этой грани.
• Полуребро (HalfEdge): хранит указатели на:
• следующее полуребро в цикле грани (next);
• предыдущее полуребро в цикле грани (prev);
• противоположное полуребро (twin или opposite);
• вершину, из которой исходит полуребро (vertex);
• грань, которой принадлежит полуребро (face);
• (опционально) ребро, которому принадлежит полуребро (edge).
• Ребро (Edge) — опциональный элемент, который объединяет два противоположных полуребра и может хранить дополнительные атрибуты ребра (например, цвет или толщину).

Схема связей

Топологические связи в полуреберном представлении образуют замкнутую структуру. Для каждой грани полуребра образуют циклический список, обходящий границу грани в одном направлении (обычно против часовой стрелки для внешних граней). Противоположные полуребра (twin) связывают соседние грани, обеспечивая возможность перехода между ними.

Основные операции

Полуреберное представление позволяет эффективно выполнять следующие операции:

• Обход вершин грани: последовательный переход по полуребрам грани через указатели next.
• Обход граней, инцидентных вершине: переход по полуребрам, исходящим из вершины, с использованием указателей twin и next.
• Проверка смежности граней: сравнение полуребер двух граней на наличие общей пары twin.
• Вставка и удаление вершин, рёбер и граней: модификация топологии сетки с перестроением указателей.
• Разделение ребра (edge split): создание новой вершины на ребре с разбиением двух полуребер на четыре.
• Стягивание ребра (edge collapse): удаление ребра и объединение двух вершин в одну.

Преимущества и недостатки

Преимущества

• Эффективность доступа: большинство топологических запросов выполняется за время O(1) благодаря прямым указателям.
• Поддержка неориентированных и ориентированных сеток: полуреберное представление может хранить как триангулированные, так и произвольные полигональные сетки.
• Удобство модификации: операции вставки и удаления элементов реализуются локальными изменениями указателей без полного перестроения структуры.
• Компактность: по сравнению с winged-edge, полуреберное представление требует меньше памяти, так как не хранит отдельные указатели на все четыре инцидентные грани для каждого ребра.

Недостатки

• Сложность реализации: требуется аккуратное управление указателями и поддержание согласованности топологии при модификациях.
• Ограниченная поддержка неориентированных сеток: для сеток с отверстиями или неориентированными гранями требуется дополнительная обработка.
• Потребление памяти: хранение двух полуребер на каждое физическое ребро увеличивает объём данных по сравнению с простым списком треугольников.

Применение

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

• Компьютерная графика: в системах моделирования и анимации (например, Blender, Maya, 3ds Max) для операций сглаживания, подразделения (subdivision), выдавливания (extrude) и булевых операций.
• Геометрическое моделирование: в CAD-системах (SolidWorks, CATIA, NX) для построения и редактирования твёрдых тел.
• Обработка трёхмерных сканов: в алгоритмах реконструкции поверхностей, упрощения сеток (decimation) и ремешинга (remeshing).
• Научные вычисления: в методах конечных элементов и вычислительной гидродинамике для работы с сетками сложной топологии.

Реализации

Известные программные библиотеки и фреймворки, реализующие полуреберное представление:

• OpenMesh (C++) — библиотека с открытым исходным кодом, предоставляющая гибкую реализацию полуреберного представления с поддержкой динамических атрибутов.
• CGAL (C++) — библиотека алгоритмов вычислительной геометрии, включающая модуль Polyhedron с полуреберным представлением.
• Halfedge (Python) — легковесная реализация для прототипирования и образовательных целей.
• Blender — использует собственную реализацию полуреберного представления (BMesh) для работы с полигональными сетками.

Сравнение с другими структурами данных

Интересные факты

• Полуреберное представление лежит в основе алгоритма подразделения Катмулла — Кларка (Catmull-Clark subdivision), используемого для создания гладких поверхностей из полигональных сеток.
• В библиотеке OpenMesh полуреберное представление реализовано таким образом, что пользователь может динамически добавлять и удалять атрибуты (цвет, нормали, текстурные координаты) без изменения основной структуры.
• Полуреберное представление является одним из ключевых элементов в системах автоматизированного проектирования (САПР), где требуется точное моделирование твёрдых тел с отверстиями и полостями.

Источники

• Mäntylä, M. (1988). An Introduction to Solid Modeling. Computer Science Press.
• Botsch, M., Kobbelt, L., Pauly, M., Alliez, P., & Levy, B. (2010). Polygon Mesh Processing. AK Peters.
• OpenMesh Documentation. Halfedge Data Structure. Дата обращения: 2025.
• CGAL Manual. Polyhedron and Halfedge Data Structures. Дата обращения: 2025.