МЕТОДЫ СОЗДАНИЯ ТРЕХМЕРНЫХ ПОВЕРХНОСТЕЙ

1. Полигональные сетки

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

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

Учение о полигональных сетках — это большой подраздел компьютерной графики и геометрического моделирования. Множество операций, проводимых над сетками, может включать булеву алгебру, сглаживание, упрощение и многие другие. Разные представления полигональных сеток используются для разных целей и приложений. Для передачи полигональных сеток по сети используются сетевые представления, такие как «потоковые» и «прогрессивные» сетки. Объемные сетки отличаются от полигональных тем, что они явно представляют и поверхность и объём структуры, тогда как полигональные сетки явно представляют лишь поверхность, а не объём. Так как полигональные сетки широко используются в компьютерной графике, для них разработаны алгоритмы трассировки лучей, обнаружения столкновений и динамики твердых тел.

Математический эквивалент полигональных сеток — неструктурированные сетки — изучаются методами комбинаторной геометрии.

Для оценки оптимальности представления используют следующие критерии:

· Объем требуемой памяти;

· Простота идентификации ребер, инцидентных вершине;

· Простота идентификации многоугольников, которым принадлежит данное ребро;

· Простота процедуры поиска вершин, образующих ребро;

· Легкость определения всех ребер, образующих многоугольник;

· Простота получения изображения полигональной сетки;

· Простота обнаружения ошибок в представлении (например, отсутствие ребра или вершины или многоугольника).

Рассмотрим подробнее три способа описания полигональных сеток.

4.1.1. Явное задание многоугольников

Каждый многоугольник можно представить в виде списка координат его вершин:

P = ((x1, y1, z1), (x2, y2, z2), … , (xn, yn, zn))

Вершины запоминаются в том порядке, в котором они встречаются при обходе вокруг многоугольника. При этом все последовательные вершины многоугольника (а также первая и последняя) соединяются ребрами. Для каждого отдельного многоугольника данный способ записи является эффективным, однако для полигональной сетки дает потери памяти вследствие дублирования информации о координатах общих вершин.

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

4.1.2. Задание многоугольников с помощью указателей в список вершин

При использовании этого представления каждый узел полигональной сетки запоминается лишь один раз в списке вершин V =((x1, y1, z1), … , (xn, yn, zn)). Многоугольник определяется списком указателей (или индексов) в списке вершин. Многоугольник, составленный из вершин 3, 5, 7 и 10 этого списка, представляется как Р = (3, 5, 7, 10).

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

4.1.3. Явное задание ребер

В этом представлении имеется список вершин V, однако будем рассматривать теперь многоугольник как совокупность указателей на элементы списка ребер, в котором ребра встречаются лишь один раз. Каждое ребро в списке ребер указывает на две вершины в списке вершин, определяющие это ребро, а также на один или два многоугольника, которым это ребро принадлежит. Таким образом, мы описываем многоугольник как P =(E1, ..., E2), а ребро — как Е = (V1, V2, P1, P2). Если ребро принадлежит только одному многоугольнику, то либо P1 либо P2 – пусто.

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

В некоторых приложениях ребра полигональных сеток являются общими для более чем двух многоугольников. Рассмотрим, например, случай в картографии, когда такие подразделения, как округа, штаты и т. д., описываются многоугольниками. Ребро (или последовательность ребер), представляющее часть границы между двумя штатами, является также границей округа в каждом штате, а возможно, и города. Таким образом, ребро может принадлежать одновременно шести многоугольникам. Если принять во внимание деление городов на районы, избирательные округа и школьные участки, то это число соответственно возрастет. Для таких приложений описания ребер могут быть расширены, чтобы включить произвольное число многоугольников: Е = (V1, V2, P1, P2, …, Pn).

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

5 "крылатое" представление)

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

Так как каждое ребро e присутствует точно в двух гранях, ровно два других ребра e1 и e2 появляются после e в этих гранях. Более точно, поскольку направление обхода грани задано, e появляется один раз в положительной ориентации, а другой раз – в отрицательной.
"Крылатое представление" использует это путем ассоциации с каждым ребром двух "следующих" ребер. Они обозначаются как ncw и nccw ("next clockwise" и "next counterclockwise" ). В данном случае ncw обозначает следующее ребро в той грани, где данное ребро появляется в положительном направлении, а nccw – следующее ребро в другой грани.
Таким образом, начиная с ребра, прямо связанного с гранью, мы может получить все другие инцидентные данной вершине ребра, следуя ссылкам ncw и nccw.
В наиболее общем случае в нашу структуру включают также ссылки на предыдущие ребра в соседних гранях. Имеем следующую структуру (см. рис):

struct edge{
pEdge ncw, pcw, pccw, nccw;
pFace fcw, fccw;
pVertex vstart, vend;
};

Здесь ncw, pcw – ссылки соответственно на следующее и предыдущее ребро в грани, в которую данное ребро входит в положительном направлении.
Аналогично nccw, pccw – следующее и предыдущее ребро в грани, соответствующей отрицательному направлению ребра.