Системы синтеза реалистических изображений должны обеспечивать передачу всех свойств моделируемого объекта: объемность, расположение, передачу полутонов, тени, освещение, текстуры поверхности. Чем выше степень реалистичности изображения, тем больше требуется вычислений для его формирования.

Генерация объемных изображений представляет сложную вычислительную задачу, в связи с этим на практике выполняют ее декомпозицию. Сложные изображения формируют из фрагментов объектов, для чего их разбивают на составные части. Процесс разбиения поверхности объектов на полигоны получил название тесселяции.

Тесселяция Electric Sports Car Black Rigged

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

На практике наиболее часто производится разбиение изображений на треугольники.

Это объясняется следующими причинами:

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

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

Триангуляция деревенского пейзажа

Алгоритмы триангуляции для простого выпуклого многоугольника

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

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

Определение. Триангуляция многоугольника — разбиение многоугольника на множество треугольников, внутренние области которых попарно не пересекаются и объединение которых в совокупности составляет сам многоугольник.

Наиболее просто разбивать на треугольники простые выпуклые многоугольники. Очевидно, что разбиение не единственно и алгоритмов может быть предложено довольно много. Например, проведение диагоналей из любой вершины во все остальные вершины выпуклого многоугольника (см. Рис.1).

Рис.1. Триангуляция выпуклого многоугольника алгоритмом проведения диагоналей из одной вершины.

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

Рис.2. Триангуляция выпуклого многоугольника алгоритмом отсечения вершин.

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

Однако, в зависимости от задачи, возможны различные алгоритмы, позволяющие проводить разбиение на треугольники с использованием дополнительных элементов. Например, алгоритм с добавлением в выпуклый многоугольник точки, лежащей внутри многоугольника: проводим из нее лучи во все вершины многоугольника, тем самым разбиваем его на треугольники (см. Рис.3).

Рис.3. Разбиение выпуклого многоугольника на треугольники с использованием внутренней точки.

Алгоритм триангуляции для простого невыпуклого многоугольника

Один из алгоритмов триангуляции основан на понятии "вершины-уха".

Определение. Вершина v_i называется ухом, если диагональ v_i−1v_i+1 лежит строго во внутренней области многоугольника.

Ниже на рисунке 4 показан пример, на котором в первом случае выделенная вершина является ухом, а в остальных нет.

Рис.4. Демонстрация ситуации, в которой вершина является "ухом".

Алгоритм триангуляцции построен по принципу "отрезания ушей". Общая идея такая: находим вершину, которая является ухом, и отрезаем ее от многоугольника. После этого ту же операцию повторяем к оставшемуся многоугольнику до тех пор, пока не останется один треугольник.

Для реализации алгоритма, необходимо проверять два условия:

1. попадает ли точка внутрь треугольника;
2. лежит ли диагональ во внутренней области многоугольника.

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

Общий вид алгоритма:

Заранее определим порядок обхода вершин в заданном многоугольнике: против часовой (или по часовой) стрелке.

1. Выбираем первую вершину, как текущую (v_i).
2. Если число вершин в рассматриваемом многоугольнике равно 3 - разбиение закончено. Алгоритм завершен.
3. Пытаемся провести из текущей вершины диагональ внутри многоугольника к вершине v_i+2, проверяя следующие условия:

• внутри треугольника v_iv_i+1v_i+2 нет ни одной вершины многоугольника;
• косое произведение векторов v_iv_i+1 Λ v_iv_i+2 положительно, т.е. направление обхода трех вершин v_i v_i+1 v_i+2 совпадает с направлением обхода многоугольника.

Если хоть одно условие не выполнено, то выбираем в качестве текущей следующую вершину v_i = v_i+1 и повторяем пункт 3.
4. Если оба условия выполняются, то "отрезаем" треугольник от многоугольника. Вершин становится на одну меньше за счёт исключения вершины v_i+1 и переходим к пункту 2.

См. программную реализацию алгоритма триангуляции на JavaScript.