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


         

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


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

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

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

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

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

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

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

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

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

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

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

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

Содержание    Вперед