Из Википедии, бесплатной энциклопедии
Перейти к навигации Перейти к поиску
Пример треугольной сетки, представляющей дельфина.

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

Многие графические программыпакеты и аппаратные устройства могут более эффективно работать с треугольниками, сгруппированными в сетки, чем с аналогичным количеством треугольников, которые представлены по отдельности. Обычно это происходит потому, что компьютерная графика выполняет операции с вершинами в углах треугольников. С отдельными треугольниками система должна оперировать тремя вершинами для каждого треугольника. В большой сетке может быть восемь или более треугольников, пересекающихся в одной вершине - обрабатывая эти вершины только один раз, можно выполнить небольшую часть работы и добиться идентичного эффекта. Во многих приложениях компьютерной графики необходимо управлять сеткой треугольников. Компоненты сетки - это вершины, ребра и треугольники. Приложению может потребоваться знание различных связей между компонентами сетки. Эти соединения могут управляться независимо от фактического положения вершин. В этом документе описывается простая структура данных, удобная для управления подключениями. Это не единственная возможная структура данных. Существует множество других типов, которые поддерживают различные запросы о сетках.

Представление [ править ]

Возможны различные способы хранения и работы с сеткой в ​​памяти компьютера. С помощью 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. Объем этой информации, хранящейся в структуре данных, зависит от потребностей приложения. Более того, приложению может потребоваться хранить дополнительную информацию в компонентах. Информация, хранящаяся в вершине, ребре или треугольнике, называется атрибутом вершины, атрибутом ребра или атрибутом треугольника. Их абстрактные представления для простой структуры данных, описанной здесь: или треугольник называется атрибутом вершины, атрибутом края или атрибутом треугольника. Их абстрактные представления для простой структуры данных, описанной здесь: или треугольник называется атрибутом вершины, атрибутом края или атрибутом треугольника. Их абстрактные представления для простой структуры данных, описанной здесь:

Вершина = <целое число>; // vEdge = <целое, целое>; // v0, v1Треугольник <целое, целое, целое>; // v0, v1, v2VData = <данные вершин для конкретного приложения>;EData = <данные края для конкретного приложения>;TData = <данные треугольника для конкретного приложения>;VAttribute = <VData, установить <Edge>, установить <Triangle>>; // данные, eset, tsetEAttribute = <EData, установить <Треугольник>>; // данные, tsetTAttribute = <TData>; // данныеVPair = пара <Вершина, VAttribute>;EPair = pair <Edge, EAttribute>;TPair = пара <Треугольник, TAttribute>;VMap = карта <VPair>;EMap = карта <EPair>;TMap = карта <TPair>;Сетка = <VMap, EMap, TMap>; // vmap, emap, tmap

Карты поддерживают стандартные функции вставки и удаления хеш-таблицы. Вставка происходит только в том случае, если элемент еще не существует. Удаление происходит только в том случае, если предмет действительно существует.

Edge Collapse [ править ]

Эта операция включает в себя идентификацию ребра hvk, vti, где vk называется вершиной поддержки, а vt называется вершиной выброса. Треугольники, которые разделяют этот край, удаляются из сетки. Вершина vt также удаляется из сетки. В любых треугольниках с общим vt эта вершина заменена на vk. На рисунке 1 показана треугольная сетка и последовательность из трех краев, примененных к этой сетке.

Индексный массив [ править ]

С индексными массивами сетка представлена ​​двумя отдельными массивами, один из которых содержит вершины, а другой - наборы из трех индексов в этом массиве, которые определяют треугольник. Графическая система сначала обрабатывает вершины, а затем визуализирует треугольники, используя наборы индексов, работающие с преобразованными данными. В OpenGL это поддерживается примитивом glDrawElements () при использовании Vertex Buffer Object (VBO).

С помощью этого метода любой произвольный набор треугольников с любым произвольным числом вершин может быть сохранен, обработан и передан графическому API без какой-либо промежуточной обработки.

См. Также [ править ]