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