Системы синтеза реалистических изображений должны обеспечивать передачу всех свойств моделируемого объекта: объемность, расположение, передачу полутонов, тени, освещение, текстуры поверхности. Чем выше степень реалистичности изображения, тем больше требуется вычислений для его формирования.
Генерация объемных изображений представляет сложную вычислительную задачу, в связи этим на практике выполняют ее декомпозицию. Сложные изображения формируют из фрагментов объектов, для чего их разбивают на составные части. Процесс разбиения поверхности объектов на полигоны получил название тесселяции.
В настоящее время появилось большое разнообразие графических акселераторов, которые имеют различные аппаратные графические функции для закраски трехмерных объектов, удаления невидимых частей, наложения текстур и т.п. Для использования преимуществ 3D-ускорителей необходимо сначала программно произвести тесселяцию исходных объектов, а затем передать полученные полигональные области для дальнейшей обработки акселератору.
На практике наиболее часто производится разбиение изображений на треугольники.
Это объясняется следующими причинами:
• треугольник является простейшим полигоном, вершины которого однозначно задают грань;
• любую область можно гарантировано разбить на треугольники;
• вычислительная сложность алгоритмов разбиения на треугольники существенно меньше, чем при использовании других полигонов;
• реализация процедур рендеринга наиболее проста для области, ограниченной треугольником;
• для треугольника легко определить три его ближайших соседа, имеющих с ним общие грани.
Процесс разбиения полигональной области со сложной конфигурацией в набор треугольников называется триангуляцией. При анализе или синтезе сложных поверхностей их аппроксимируют сеткой треугольников, и впоследствии оперируют с простейшими полигональными областями, т.е. с каждым из треугольников.
Алгоритмы триангуляции многоугольников
Алгоритм триангуляции простого невыпуклого многоугольника без отверстий:
Алгоритм основан на принципе отрезания ушей, где вершина является ухом, если диагональ из смежных вершин полностью лежит внутри многоугольника.
Рис.1 Понятие вершины-уха
На рисунке 1
• вершина A2 является вершиной ухом;
• вершина A3 не удовлетворяет условию;
• вершина A4 не удовлетворяет условию.
Находим на многоугольнике вершину-ухо и отсекаем от многоугольника. Повторяем это действие до тех пор, пока не останется 3 вершины.
Программная реализация на JS алгоритма триангуляции по принципу "отрезания ушей" представлена здесь.
