Алгоритмы, структуры данных

       

Алгоритмы триангуляции


Романюк Александр, Сторчак Александр,

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

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

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

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

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

треугольник является простейшим полигоном, вершины которого однозначно задают грань;

любую область можно гарантировано разбить на треугольники;

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

реализация процедур рендеринга наиболее проста для области, ограниченной треугольником;

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

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

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

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

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

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

Последним этапом является применение алгоритмов сглаживания, которые устраняется ребристость поверхности, эффект Маха.


Содержание раздела