Триангуляция полигонов
Рассмотрим наиболее распространенные алгоритмы триангуляции полигонов. Простейшее решение задачи триангуляции состоит в расщеплении полигона вдоль некоторой хорды на два полигона и в дальнейшем рекурсивном разбиении их до ситуации, когда подлежащий триангуляции полигон является треугольником.
Данный способ применим лишь для триангуляции выпуклых полигонов. Выпуклым считается полигон, если отрезок прямой, соединяющий любые его две точки, полностью лежит во внутренней области.
Триангуляция невыпуклых полигонов не так проста, поэтому предварительная разбивка невыпуклых многоугольников на выпуклые существенно упрощает алгоритмы их последующей обработки. Проще всего это можно сделать последовательным переносом и поворотом многоугольника так, чтобы одна из его вершин совпадала с началом координат, а исходящая из нее сторона — с осью ОХ. При расположении каких-либо сторон ниже оси, происходит их отсечение, и алгоритм рекурсивно повторяют для полученных полигонов, пока они не станут выпуклыми.
Приведем универсальный алгоритм. Триангуляцию любого полигона можно осуществить по следующему универсальному алгоритму.
Выбирается крайняя левая вершина и между двумя ее смежными сторонами проводится диагональ. При этом могут иметь место следующие два случая:
диагональ является хордой;
диагональ — не хорда, так как внутрь треугольникапопадает вершина полигона (в общем случае их может быть несколько).
Из всех вершин внутри треугольника вершина d наиболее удалена от стороны ас. Эту вершину будем называть вторгающейся. В случае, когда вторгающейся вершины нет, то полученный треугольник заносят в сетку треугольников, и алгоритм рекурсивно обрабатывает оставшийся полигон до тех пор, пока он не выродится в треугольник. При обнаружении вторгающейся вершины проводится диагональ из текущей до вторгающейся вершины. Полученные полигоны рекурсивно обрабатываются до получения треугольников.
Один из подходов к триангуляции состоит в нахождении внутренней точки области, ограниченной полигоном, и соединении с ней всех вершин.
Учитывая, что триангуляция является подготовительным этапом рендеринга, к выбору внутренней точки могут предъявляться определенные требования. Так, например, при многопроцессорной обработке целесообразно внутреннюю точку выбрать таким образом, чтобы площадь составляющих треугольников была примерно одинаковой. В этом случае будет обеспечена одинаковая степень вычислительной загрузки аппаратуры.
При триангуляции в качестве исходных данных наиболее часто задаются вершины полигона. Задача состоит в том, чтобы представить этот полигон совокупностью составных непересекающихся треугольников. В одном из самых распространенных программных интерфейсов (API) для разработки приложений в области двумерной и трехмерной графики стандарте OpenGL для формирования триангуляционной сетки используются следующие команды:
GL_TRIANGLES. Треугольники. Команда рисует серию треугольников, используя тройки вершин v0, v1 и v2, затем v3, v4 и v5 и т.д. Если количество вершин не кратно 3, оставшиеся точки игнорируются. Команду удобно использовать при описании поверхности, которая в результате тесселяции представляется кроме треугольников и другими геометрическими фигурами, например, прямоугольниками. В этом случае треугольники могут быть не соприкасаться между собой. Команда может использоваться для описания всех треугольников полигона, независимо от того, связаны они или нет между собой, однако из-за дублирования информации о координатах общих вершин память используется нерационально.
GL_TRIANGLE_STRIP. Полоса треугольников. Команда рисует серию треугольников, используя вершины в следующем порядке: v0, v1, v2, затем v2, v0, v3, затем v2, v3, v4, и т. д. При таком подходе каждая следующая вершина вместе с двумя предыдущими задает треугольник. Порядок вершин должен гарантировать, что треугольники имеют правильную ориентацию. Полоса может использоваться для формирования части поверхности.
GL_TRIANGLE_FAN. Команда похожа на GL_TRIANGLE_STRIP, но при формировании треугольников используют вершины в таком порядке: v0, v1, v2, затем v0, v2, v3, затем v0, v3, v4, и т.д. Все треугольники имеют общую вершину v0. Команда позволяет разбить n-угольник на n-2 треугольника. Для этого нужно выбрать одну из n вершин полигона и соединить ее с каждой из n-3 несоседних вершин
