Треугольная сетка
 |
В компьютерной графике треугольная сетка является разновидностью сетки полигональной . Он состоит из набора треугольников (обычно трехмерных ), соединенных общими краями или вершинами .
Многие графические пакеты программного обеспечения и аппаратные устройства могут более эффективно работать с треугольниками, сгруппированными в сетки, чем с аналогичным количеством треугольников, представленных индивидуально. Обычно это происходит потому, что компьютерная графика выполняет операции с вершинами в углах треугольников. В случае отдельных треугольников система должна оперировать тремя вершинами каждого треугольника. В большой сетке в одной вершине может встречаться восемь или более треугольников — обработав эти вершины только один раз, можно выполнить часть работы и добиться идентичного эффекта. [ нужна ссылка ]
Во многих приложениях компьютерной графики необходимо управлять сеткой треугольников. Компонентами сетки являются вершины, ребра и треугольники. Приложению может потребоваться знание различных связей между компонентами сетки. Этими соединениями можно управлять независимо от фактического положения вершин. В этом документе описана простая структура данных, удобная для управления соединениями. Это не единственная возможная структура данных. Существует множество других типов, которые поддерживают различные запросы о сетках. [ нужна ссылка ]
Представительство [ править ]
Возможны различные способы хранения и работы с сеткой в памяти компьютера. С помощью OpenGL и DirectX API-интерфейсов существует два основных способа передачи треугольной сетки графическому оборудованию: полосы треугольников и массивы индексов. [ нужна ссылка ]
Треугольная полоса [ править ]
Одним из способов совместного использования данных вершин между треугольниками является полоса треугольников. В случае полосок треугольников каждый треугольник имеет одну общую сторону с одним соседом, а другую - со следующим. Другой способ — треугольников веер , который представляет собой набор соединенных треугольников, имеющих одну центральную вершину. С помощью этих методов вершины обрабатываются эффективно, в результате чего необходимо обработать только N+2 вершины, чтобы нарисовать N треугольников. [ нужна ссылка ]
Треугольные полосы эффективны, однако недостатком является то, что может быть неочевидно, как или удобно преобразовать произвольную треугольную сетку в полосы. [ нужна ссылка ]
Структура данных [ править ]
Структура данных, представляющая сетку, обеспечивает поддержку двух основных операций: вставки треугольников и удаления треугольников. Он также поддерживает операцию схлопывания ребер, которая полезна в схемах прореживания треугольников. Структура не поддерживает позиции вершин, но предполагает, что каждой вершине присвоен уникальный целочисленный идентификатор, обычно индекс этой вершины в массиве смежных позиций вершин. Вершина сетки определяется одним целым числом и обозначается hvi. Ребро сетки определяется парой целых чисел hv0,v1i, каждое целое число соответствует конечной точке ребра. Для поддержки карт ребер ребра сохраняются так, что v0 = min(v0,v1). Компонент треугольника определяется тройкой целых чисел hv0,v1,v2i, каждое целое число соответствует вершине треугольника. Для поддержки карт треугольников треугольники сохраняются так, что v0 = min(v0,v1,v2). Обратите внимание, что hv0,v1,v2i и hv0,v2,v1i рассматриваются как разные треугольники. Приложение, требующее двусторонних треугольников, должно вставить обе тройки в структуру данных. Чтобы избежать постоянных напоминаний о порядке индексов, в оставшейся части документа информация о парах/тройках не подразумевает, что вершины каким-либо образом упорядочиваются (хотя реализация обрабатывает порядок). [ нужна ссылка ]
Связность между компонентами полностью определяется набором троек, представляющих треугольники. Треугольник t = hv0,v1,v2i имеет вершины v0, v1 и v2. Он имеет ребра e0 = hv0,v1i, e1 = hv1,v2i и e2 = hv2,v0i. Известны и обратные связи. Вершина v0 примыкает к ребрам e0 и e2 и к треугольнику t. Вершина v1 примыкает к ребрам e0 и e1 и к треугольнику t. Вершина v2 примыкает к ребрам e1 и e2 и к треугольнику t. Все три ребра e0, e1 и e2 смежны с t. [ нужна ссылка ]
Сколько этой информации хранит структура данных, зависит от потребностей приложения. Более того, приложению может потребоваться хранить дополнительную информацию в компонентах. Информация, хранящаяся в вершине, ребре или треугольнике, называется атрибутом вершины, атрибутом ребра или атрибутом треугольника. Их абстрактные представления для описанной здесь простой структуры данных: [ нужна ссылка ]
Vertex = <integer>; // v Edge = <integer, integer>; // v0, v1 Triangle <integer,integer,integer>; // v0, v1, v2 VData = <application-specific vertex data>; EData = <application-specific edge data>; TData = <application-specific triangle data>; VAttribute = <VData, set<Edge>,set<Triangle>>; // data, eset, tset EAttribute = <EData, set<Triangle>>; // data, tset TAttribute = <TData>; // data VPair = pair<Vertex,VAttribute>; EPair = pair<Edge,EAttribute>; TPair = pair<Triangle,TAttribute>; VMap = map<VPair>; EMap = map<EPair>; TMap = map<TPair>; Mesh = <VMap,EMap,TMap>; // vmap, emap, tmap
Карты поддерживают стандартные функции вставки и удаления для хеш-таблицы. Вставка происходит только в том случае, если элемент еще не существует. Удаление происходит только в том случае, если элемент существует. [ нужна ссылка ]
Обрушение края [ править ]
Эта операция включает идентификацию ребра hvk, vti, где vk называется вершиной сохранения, а vt называется вершиной выброса. Треугольники, имеющие общий край, удаляются из сетки. Вершина vt также удаляется из сетки. Во всех треугольниках, у которых есть общая вершина vt, эта вершина заменена на vk. Рисунок 1 [ где? ] показывает треугольную сетку и последовательность из трех схлопываний ребер, примененных к сетке. [ нужна ссылка ]
Индексный массив [ править ]
С помощью индексных массивов сетка представлена двумя отдельными массивами: один массив содержит вершины, а другой содержит наборы из трех индексов в этом массиве, которые определяют треугольник. Графическая система сначала обрабатывает вершины, а затем визуализирует треугольники, используя наборы индексов, работающие с преобразованными данными. В OpenGL это поддерживается примитивом glDrawElements() при использовании объекта буфера вершин (VBO). [ нужна ссылка ]
С помощью этого метода любой произвольный набор треугольников, имеющих любое произвольное количество вершин, может быть сохранен, обработан и передан в графический API без какой-либо промежуточной обработки. [ нужна ссылка ]
См. также [ править ]
- Гиперграф
- Алгоритм Мёллера-Трамбора для пересечения луча и треугольника
- Нетупая сетка
- Неравномерный рациональный B-сплайн
- Облако точек
- Полигональная сетка
- Триангуляция (топология)
- Триангуляция (геометрия)
 | Эта компьютерной графике статья, посвященная , незавершена . Вы можете помочь Википедии, расширив ее . |