Триангуляция

Добавлен , опубликован
Триангуляция по простому - разбиение фигуры на треугольники. Подобная операция может понадобиться при создании как нестандартной области выделения, так и при генерации моделей из кода.
Однако, как можно посмотреть в википедии - способов триангуляции существует несколько и один другого круче.
Но не беда прочитать о ней, хочется еще и не изобретать велосипед и взять что-то готовое. Так решил сделать и я, но попытки не увенчались успехом - алгоритм Делоне на 1000 строк кода часть треугольников зачем-то переворачивал, а ушная триангуляция прикрепленная к самой вики статье - на 7000 строк ужасно кривого кода, в котором просто невозможно разобраться. Это принудило меня к написанию алгоритма с нуля - встречайте, ушная триангуляция для Unity всего на 100 строк.
Как работает:
  • Закиньте скрипт в папку с проектом
  • В коде используйте Triangulation.GetResult для получения результата триангуляции. У метода есть две перегрузки
1 перегрузка (стандартная)
На вход в методе имеется два параметра:
  • List<Vector2> points - точки многоугольника
Триангуляция - это работа в плоскости, потому вектора двумерные. Если внимательно посмотреть, то вариантов разбиения многоугольника на треугольники всегда несколько и в пространстве это бы возвращало разные фигуры. Потому даже не пытайтесь приводить это к трехмерному вектору, не повторяйте моих глупых ошибок :)
  • bool clockwise - если true, то полученные точки обрабатываются по часовой, если false - против часовой.
На выходе возвращается:
  • List<Vector2> - точки треугольников
Список по количеству всегда кратен 3, то есть через каждые три индекса описывается новый треугольник
Пример использования:
var result = Triangulation.GetResult(points, true);
2 перегрузка (быстрая конвертация)
В методе имеется 6 параметров, из которых три на вход:
  • List<Vector3> points - точки многоугольника в пространстве
  • bool clockwise - если true, то полученные точки обрабатываются по часовой, если false - против часовой.
  • Vector3 upAxis - ось, перпендикулярная плоскости
Возвращает три параметра при помощи out. Все эти данные используются для создания меша в аналогичных полях:
  • Vector3[] verticles
  • int[] triangles
  • Vector2[] uvcoords
Третья координата рассчитывается как "среднее значение по точкам на перпендикулярной плоскости".
Пример использования:
        Vector3[] verticles;
        int[] triangles;
        Vector2[] uvcoords;
        Triangulation.GetResult(points, true, Vector3.up, out verticles, out triangles, out uvcoords);
UPDATE:
В комментариях приложен доработанный код с более быстрым алгоритмом.

Показан только небольшой набор комментариев вокруг указанного. Перейти к актуальным.
0
28
10 лет назад
0
Extravert, это понятно что из полигонов
просто некоторые движки позволяют юзать не только трианглы и квадры
0
27
10 лет назад
0
nvc123, например?
0
14
10 лет назад
0
nvc123, может, ты имел ввиду просто трёхмерные редакторы?
Extravert, молодец!
1
27
10 лет назад
1
Обновлено.
Добавлена перегрузка, конвертирующая пространственные координаты по указанной нами оси и возвращающая (координаты точек + порядок рисования + текстурные координаты).
В общем для создания мешей удобней и быть не может.
0
28
10 лет назад
0
Extravert, ну во всяком случае опен гл спрашивает количество точек у полигона
хотя возможно он сам проводит триангуляцию
но даже если и делит на трианглы то делает это на gpu
0
11
10 лет назад
0
nvc123:
Extravert, это понятно что из полигонов
просто некоторые движки позволяют юзать не только трианглы и квадры
Многие автоматически разбивают на трианглы при экспорте модели)
1
29
10 лет назад
1
nvc123, как в OpenGL так и в DirectX при DrawCall передается буфер вершин, а уж что он с ними делает зависит от состояния конвеера рендера. Там можно указывать что он будет их рисовать как квады или как трианглы или еще как-что нибудь. Уже не помню полный список, но это два основных. Триангуляцию на GPU никто не делает автоматически, хотя сейчас есть тессяляция, в которой наверное можно как то посчитать триангуляцию, но не уверен. Хотя на самом деле нет смысла делать постоянно триангуляцию, достаточно сделать лишь 1 раз, а потом рендерить полученный меш, а если уж возникла потребность перемещать точки, то при небольших изменениях ничего не случится с мешем, так что можно пересчитывать где-то на каждые кадров 5, при условии медленного изменения сетки
0
27
10 лет назад
Отредактирован Devion
0
Extravert, ну во всяком случае опен гл спрашивает количество точек у полигона
хотя возможно он сам проводит триангуляцию
но даже если и делит на трианглы то делает это на gpu
Многие автоматически разбивают на трианглы при экспорте модели)
Из нестандартных форм полигонов движок держит только квадры, все остальные как и сказал Senbonzakura переделываются в трианглы. В программах для моделлирования уж точно - там по дефолту рендер производится через ЦПУ, если явно не указано использование графического конвейера, так как ЦПУ и ГПУ производят принципиально разный рендер. *Тут был рассказ о том в чем их отличие но я кажется ухожу от темы*.
ГПУ не делит на трианглы даже по той простой причине, что запекание предварительных данных не его обязанность вовсе. А данный алгоритм в рамках ГПУ и кадровых операций весьма затратный, даже если пользоваться самыми быстрыми методами. Короче, все делится на трианглы предварительно, даже в максе, просто пользователю это знать не обязательно.
alexprey, если бы я делал тесселяцию - я бы не триангуляцией как таковой пользовался бы, а скорее делением треугольника на более мелкие - так как это в разы быстрее (имею ввиду когда заранее известно что стороны три и нужно из них образовать два-три подтриангла это пошустрее чем делоне и ушная). Почему-то есть предчувствие что именно так оно и реализовано.
0
29
10 лет назад
0
Extravert, ну вообще да, тесселяция это именно увеличение\уменьшение детализации для готовой сетки, но возможность такая есть.
Extravert:
Почему-то есть предчувствие что именно так оно и реализовано.
самая простая тесселяция да, для более крутой уже используются карты нормалей, карты высот и прочая дополнительная ересь высокого разрешения
0
28
10 лет назад
0
Extravert, только что писали что open gl и derectx могут принимать много-угольники и без всякой триангуляции
0
29
10 лет назад
0
nvc123, не совсем многоугольники, вот точный список
Показан только небольшой набор комментариев вокруг указанного. Перейти к актуальным.
Чтобы оставить комментарий, пожалуйста, войдите на сайт.