Полигональная сетка

Полигональная сетка (полигональная модель, меш, от англ. polygon mesh) — это совокупность вершин, рёбер и граней, определяющих форму многогранного объекта в трёхмерной компьютерной графике и геометрическом моделировании. Полигональная сетка является одним из основных способов представления трёхмерных объектов, наряду с воксельными, NURBS-поверхностями и неявными поверхностями. Основное преимущество полигональных сеток — простота хранения, обработки и визуализации, что делает их стандартом де-факто в индустрии компьютерных игр, кино, виртуальной реальности и САПР.

Основные понятия и структура

Полигональная сетка состоит из трёх базовых элементов:

• Вершина (vertex) — точка в трёхмерном пространстве, заданная координатами (x, y, z). Вершины являются фундаментом сетки; все остальные элементы определяются через них.
• Ребро (edge) — отрезок, соединяющий две вершины. Ребро является границей грани.
• Грань (face) — замкнутая фигура, образованная последовательностью рёбер. Чаще всего грани представляют собой треугольники (триангуляция) или четырёхугольники (квады). В некоторых случаях используются многоугольники с большим количеством сторон (n-угольники), но их применение ограничено из-за сложности обработки.

Типы граней

• Треугольники (трисы) — наиболее универсальный тип. Любой многоугольник может быть разбит на треугольники. Треугольные сетки используются в большинстве графических API (DirectX, OpenGL, Vulkan) и в 3D-печати.
• Четырёхугольники (квады) — предпочтительны для моделирования и анимации, так как лучше поддаются деформации и сглаживанию. Квадратные сетки часто применяются в программах для скульптинга (ZBrush, Blender) и в системах подразделения поверхностей (Subdivision Surface).
• n-угольники — многоугольники с числом сторон более четырёх. Используются редко, обычно в CAD-моделях или при импорте из других форматов. Могут вызывать артефакты при текстурировании и рендеринге.

Атрибуты вершин

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

• Нормали — векторы, определяющие ориентацию поверхности в данной точке. Используются для расчёта освещения.
• Текстурные координаты (UV-координаты) — двумерные координаты, связывающие вершину с точкой на текстурном изображении.
• Цвета вершин — задают цвет непосредственно на вершине, который затем интерполируется по грани.
• Вертексные веса — используются в скелетной анимации для определения влияния костей на вершины.

Способы представления

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

Список вершин и граней (Face-Vertex Mesh)

Самый простой и распространённый формат. Сетка хранится как два массива:

• Массив вершин (список всех координат).
• Массив граней, где каждая грань — это список индексов вершин, образующих её.

Этот способ экономит память по сравнению с хранением каждой грани отдельно, но требует дополнительных затрат на поиск рёбер и соседних граней.

Список рёбер (Edge List)

Хранятся только вершины и рёбра. Грани не хранятся явно, а восстанавливаются по рёбрам. Используется редко, в основном в алгоритмах обработки сеток.

Связанная структура рёбер (Half-Edge Mesh)

Более сложная структура, в которой каждое ребро представлено двумя полуребрами (half-edges), направленными в противоположные стороны. Каждое полуребро хранит ссылки на:

• Вершину, из которой оно исходит.
• Следующее полуребро в той же грани.
• Противоположное полуребро.
• Грань, которой принадлежит.

Такая структура обеспечивает быстрый обход сетки и эффективное выполнение операций (разрезание, сшивание, подразделение), но требует больше памяти.

Свойства и характеристики

Топология

Топология сетки описывает, как её элементы соединены между собой, без учёта геометрических координат. Ключевые топологические понятия:

• Многообразие (manifold) — сетка, в которой каждое ребро принадлежит не более чем двум граням, а окрестность каждой вершины гомеоморфна диску. Немногообразие (non-manifold) — ситуации, когда ребро принадлежит трём и более граням или когда вершина соединяет несвязанные части сетки. Немногообразие часто вызывает проблемы в алгоритмах.
• Род (genus) — топологическая характеристика, равная числу «дырок» (ручек) в сетке. Например, сфера имеет род 0, тор — род 1.
• Связность — количество отдельных компонент сетки.
• Эйлерова характеристика — для замкнутой сетки выполняется формула Эйлера: V — E + F = 2 — 2g, где V — число вершин, E — число рёбер, F — число граней, g — род.

Геометрия

Геометрия сетки — это положение вершин в пространстве. Основные геометрические характеристики:

• Плотность — количество вершин и граней на единицу площади. Высокая плотность позволяет передавать мелкие детали, но увеличивает вычислительную нагрузку.
• Равномерность — степень однородности распределения вершин. Неравномерные сетки (с разной плотностью в разных областях) часто используются для оптимизации.
• Качество — форма граней. Идеальными считаются равносторонние треугольники и квадраты. Вытянутые, узкие грани (стрипы) ухудшают качество визуализации и численных расчётов.

Создание и редактирование

Полигональные сетки создаются несколькими способами:

• Ручное моделирование — в 3D-редакторах (Blender, 3ds Max, Maya) художник вручную создаёт и редактирует вершины, рёбра и грани.
• Скульптинг — цифровая лепка, при которой художник использует кисти для деформации высокополигональной сетки (ZBrush, Mudbox).
• Процедурная генерация — создание сетки по алгоритму (например, генерация ландшафта, зданий, растительности).
• Фотограмметрия — восстановление трёхмерной модели по набору фотографий.
• 3D-сканирование — получение облака точек с последующей триангуляцией.
• Импорт из CAD-систем — преобразование NURBS-поверхностей в полигональную сетку.

Основные операции редактирования:

• Экструзия — выдавливание грани или ребра для создания новых форм.
• Подразделение (subdivision) — деление граней на более мелкие для увеличения детализации.
• Сглаживание — усреднение положения вершин для уменьшения шероховатостей.
• Ретопология — перестроение сетки с целью улучшения её топологии и распределения вершин.
• Децимация — уменьшение количества полигонов с минимальной потерей качества.

Применение

Компьютерная графика и анимация

Полигональные сетки — основа для рендеринга в реальном времени (игры, VR/AR) и офлайн-рендеринга (кино, реклама). В играх используются низкополигональные модели (LOD — Level of Detail) для оптимизации производительности. В кино — высокополигональные модели с миллионами полигонов.

3D-печать

Для 3D-печати требуется замкнутая водонепроницаемая (watertight) полигональная сетка, не содержащая дырок и многообразий. Формат STL является стандартом для 3D-печати и хранит только треугольные грани без атрибутов.

Научные расчёты (FEM, CFD)

В методе конечных элементов (МКЭ) и вычислительной гидродинамике (CFD) полигональные сетки используются для разбиения расчётной области на элементы. Качество сетки критически влияет на точность и сходимость решения.

Медицина

По данным компьютерной томографии (КТ) и магнитно-резонансной томографии (МРТ) строятся трёхмерные полигональные модели органов и костей для диагностики, планирования операций и протезирования.

Геоинформационные системы (ГИС)

Цифровые модели рельефа (ЦМР) часто представляются в виде полигональных сеток (TIN — Triangulated Irregular Network) для визуализации и анализа ландшафта.

Форматы файлов

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

• OBJ — текстовый формат, поддерживает вершины, грани, текстурные координаты и нормали. Широко используется для обмена данными.
• FBX — бинарный формат, разработанный компанией Autodesk. Поддерживает анимацию, скелеты, материалы. Стандарт в игровой индустрии.
• STL — простой формат, хранящий только треугольные грани. Используется в 3D-печати.
• PLY (Polygon File Format) — поддерживает как текстовое, так и бинарное представление. Может хранить дополнительные атрибуты вершин (цвет, нормали).
• GLTF — современный формат для передачи 3D-контента в веб-приложениях. Оптимизирован для загрузки и рендеринга.
• 3DS — устаревший формат, но всё ещё встречается в старых проектах.
• BLEND — внутренний формат Blender.
• MAX — внутренний формат 3ds Max.

Проблемы и ограничения

• Размер данных — высокополигональные модели могут занимать гигабайты памяти, что затрудняет их передачу и обработку.
• Топологические дефекты — дырки, многообразия, вырожденные грани (нулевой площади) могут приводить к ошибкам в рендеринге и 3D-печати.
• Алиасинг — ступенчатость на краях модели при недостаточном разрешении сетки.
• Сложность анимации — деформация сетки с плохой топологией может приводить к артефактам (складкам, растяжениям).

Литература

• Botsch, M., Kobbelt, L., Pauly, M., Alliez, P., & Levy, B. (2010). Polygon Mesh Processing. CRC Press.
• Foley, J. D., van Dam, A., Feiner, S. K., & Hughes, J. F. (1996). Computer Graphics: Principles and Practice. Addison-Wesley.
• Авербух, В. Л. (2008). Компьютерная графика: учебное пособие. Екатеринбург: УрГУ.