В компьютерной 3D-графике и твердотельном моделировании полигональная сетка представляет собой наборвершины ,край sигрань s, определяющая формумногогранногообъекта. Граниобычно состоят изтреугольников(треугольная сетка),четырехугольников(квадраты) или других простыхвыпуклых многоугольников(n-угольников), поскольку это упрощаетрендеринг, но в более общем случае могут также состоять извогнутых многоугольниковили даже многоугольников с отверстиями.
Исследование полигональных сеток — это большая область компьютерной графики (в частности, 3D-компьютерной графики) и геометрического моделирования . Различные представления полигональных сеток используются для разных приложений и целей. Разнообразие операций, выполняемых над сетками, может включать в себя: Булеву логику ( Конструктивная твердотельная геометрия ), сглаживание , упрощение и многие другие. Также существуют алгоритмы трассировки лучей , обнаружения столкновений и динамики твердого тела с полигональными сетками. Если вместо граней визуализируются края сетки, модель становится каркасной .
Объемные сетки отличаются от полигональных сеток тем, что они явно представляют как поверхность, так и объем конструкции, тогда как полигональные сетки явно представляют только поверхность (объем неявно).
Существует несколько методов генерации сетки , включая алгоритм марширующих кубов . [1]
Объекты, созданные с помощью полигональных сеток, должны хранить элементы разных типов. К ним относятся вершины, ребра, грани, многоугольники и поверхности. Во многих приложениях сохраняются только вершины, ребра, а также грани или многоугольники. Средство визуализации может поддерживать только трехсторонние грани, поэтому многоугольники должны состоять из многих из них, как показано выше. Однако многие средства визуализации либо поддерживают четырехугольники и многоугольники с более высокими сторонами, либо могут конвертировать многоугольники в треугольники на лету, что делает ненужным хранить сетку в триангулированной форме.
Полигональные сетки могут быть представлены различными способами, используя разные методы для хранения данных вершин, ребер и граней. К ним относятся:
VV" представляет только вершины, которые указывают на другие вершины. Информация о ребре и грани неявно присутствует в представлении. Однако простота представления не позволяет выполнять многие эффективные операции над сетками.Каждое из приведенных выше представлений имеет определенные преимущества и недостатки, которые далее обсуждаются Смитом (2006). [2] Выбор структуры данных зависит от приложения, требуемой производительности, размера данных и операций, которые необходимо выполнить. Например, с треугольниками легче иметь дело, чем с обычными многоугольниками, особенно в вычислительной геометрии . Для некоторых операций необходим быстрый доступ к топологической информации, такой как ребра или соседние грани; для этого требуются более сложные структуры, такие как представление с крылатым краем. Для аппаратного рендеринга нужны компактные, простые конструкции; таким образом, угловая таблица (треугольный веер) обычно включается в API низкоуровневого рендеринга, такие как DirectX и OpenGL .
.png/1280px-Vertex-Vertex_Meshes_(VV).png)
Сетки вершин-вершин представляют объект как набор вершин, соединенных с другими вершинами. Это самое простое представление, но оно не широко используется, поскольку информация о грани и ребре неявна. Таким образом, необходимо пройти по данным, чтобы сформировать список лиц для рендеринга. Кроме того, операции с ребрами и гранями выполнить непросто.
Однако сетки VV выигрывают от небольшого пространства для хранения и эффективного морфинга формы. На рисунке выше показан четырехсторонний прямоугольник, представленный сеткой VV. Каждая вершина индексирует соседние вершины. Последние две вершины, 8 и 9 в верхней и нижней центральной части «цилиндра-коробки», имеют четыре соединенных вершины, а не пять. Общая система должна иметь возможность обрабатывать произвольное количество вершин, связанных с любой заданной вершиной.
Полное описание сетей VV см. в Smith (2006). [2]
Сетки граней-вершин представляют объект как набор граней и набор вершин. Это наиболее широко используемое представление сетки, которое обычно принимается современным графическим оборудованием.
Сетки вершин граней улучшают сетку VV для моделирования, поскольку они позволяют явно искать вершины грани и грани, окружающие вершину. На рисунке выше показан пример «коробчатого цилиндра» в виде сетки FV. Вершина v5 выделена, чтобы показать окружающие ее грани. Обратите внимание, что в этом примере каждая грань должна иметь ровно 3 вершины. Однако это не означает, что каждая вершина имеет одинаковое количество окружающих граней.
Для рендеринга список граней обычно передается в графический процессор как набор индексов вершин, а вершины передаются как структуры позиция/цвет/нормаль (на рисунке указана только позиция). Преимущество этого заключается в том, что изменения формы, но не геометрии, можно динамически обновлять, просто повторно отправляя данные вершин без обновления связности граней.
Моделирование требует легкого обхода всех структур. С помощью сеток граней-вертексов легко найти вершины грани. Кроме того, список вершин содержит список граней, связанных с каждой вершиной. В отличие от сеток VV, и грани, и вершины являются явными, поэтому поиск соседних граней и вершин занимает постоянное время. Однако края неявны, поэтому поиск всех граней, окружающих данную грань, все равно необходим. Другие динамические операции, такие как разделение или объединение граней, также затруднены с сетками граней-вершин.
Сетки с крылатыми краями , представленные Баумгартом в 1975 году, явно представляют вершины, грани и края сетки. Это представление широко используется в программах моделирования для обеспечения наибольшей гибкости при динамическом изменении геометрии сетки, поскольку операции разделения и слияния можно выполнять быстро. Их основной недостаток — большие требования к объему памяти и повышенная сложность из-за поддержки множества индексов. Хорошее обсуждение вопросов реализации сеток Winged-edge можно найти в книге Graphics Gems II .
Сети с крыльями решают проблему перемещения от края к краю и обеспечивают упорядоченный набор граней вокруг края. Для любого данного ребра количество исходящих ребер может быть произвольным. Чтобы упростить это, сетки с крылатыми краями предоставляют только четыре, ближайшие по часовой стрелке и против часовой стрелки ребра на каждом конце. Остальные края можно перемещать постепенно. Таким образом, информация для каждого ребра напоминает бабочку, отсюда и сетки с «крылатыми краями». На рисунке выше «коробка-цилиндр» показана в виде сетки с крыльями. Общие данные для ребра состоят из 2 вершин (конечных точек), 2 граней (с каждой стороны) и 4 ребер (крылатого ребра).
Рендеринг сеток с крыльями для графического оборудования требует создания списка индексов лиц. Обычно это делается только при изменении геометрии. Сетки с крыльями идеально подходят для динамической геометрии, такой как поверхности разделения и интерактивное моделирование, поскольку изменения в сетке могут происходить локально. Обход сетки, который может потребоваться для обнаружения столкновений, может быть выполнен эффективно.
Более подробную информацию см. в Baumgart (1975). [3]
Сетки с крыльями — не единственное представление, позволяющее динамически изменять геометрию. Новое представление, которое объединяет сетки с крылатыми краями и сетки с гранями-вершинами, — это динамическая сетка рендеринга , которая явно хранит как вершины грани, так и грани вершины (например, сетки FV), а также грани и вершины грани ( как крылатый край).
Для визуализации динамических сеток требуется немного меньше места для хранения, чем для стандартных сеток с крылатыми краями, и они могут быть непосредственно визуализированы с помощью графического оборудования, поскольку список граней содержит индекс вершин. Кроме того, переход от вершины к грани является явным (постоянное время), как и от грани к вершине. Сетки RD не требуют четырех исходящих ребер, поскольку их можно найти, перемещаясь от края к грани, а затем лицом к соседнему ребру.
Сетки RD выигрывают от особенностей сеток с крылатыми краями, позволяя динамически обновлять геометрию.
Более подробную информацию см. в Tobler & Maierhofer (WSCG 2006). [4]
В приведенной выше таблице явно указано, что операцию можно выполнить за постоянное время, поскольку данные сохраняются напрямую; сравнение списков указывает, что для выполнения операции необходимо выполнить сравнение списков между двумя списками; а поиск пары указывает, что поиск необходимо выполнить по двум индексам. Обозначение avg(V,V) означает среднее количество вершин, соединенных с данной вершиной; avg(E,V) означает среднее количество ребер, соединенных с данной вершиной, а avg(F,V) — среднее количество граней, соединенных с данной вершиной.
Обозначение «V → f1, f2, f3, ... → v1, v2, v3, ...» описывает, что для выполнения операции требуется обход нескольких элементов. Например, чтобы получить «все вершины вокруг данной вершины V» с помощью сетки граней-вершин, необходимо сначала найти грани вокруг данной вершины V, используя список вершин. Затем по этим граням используйте список граней, чтобы найти вершины вокруг них. Сетки с крылатыми краями явно хранят почти всю информацию, а другие операции всегда сначала обращаются к краю, чтобы получить дополнительную информацию. Сетки вершин-вершин — единственное представление, которое явно хранит соседние вершины данной вершины.
По мере того как представления сетки становятся более сложными (слева направо в сводке), объем явно хранимой информации увеличивается. Это дает более прямой, постоянный доступ к обходу и топологии различных элементов, но за счет увеличения накладных расходов и пространства для правильного поддержания индексов.
На рис. 7 показана информация о подключении для каждого из четырех методов, описанных в этой статье. Существуют и другие представления, такие как полукраевые и угловые таблицы. Все это варианты того, как вершины, грани и ребра индексируют друг друга.
Как правило, сетки граней-вершин используются всякий раз, когда объект должен быть визуализирован на графическом оборудовании, которое не меняет геометрию (связность), но может деформировать или трансформировать форму (положение вершин), например, рендеринг статических или морфируемых объектов в реальном времени. . Динамические сетки с крыльями или рендерингом используются при изменении геометрии, например, в пакетах интерактивного моделирования или для расчета поверхностей подразделения. Сетки вершин-вершин идеально подходят для эффективных и сложных изменений геометрии или топологии, если не требуется аппаратный рендеринг.
Существует множество различных форматов файлов для хранения данных полигональной сетки. Каждый формат наиболее эффективен, когда используется по назначению его создателя. Популярные форматы включают .fbx , .dae , .obj и .stl . Таблица еще некоторых из этих форматов представлена ниже: