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

Добавлен , опубликован
Триангуляция по простому - разбиение фигуры на треугольники. Подобная операция может понадобиться при создании как нестандартной области выделения, так и при генерации моделей из кода.
Однако, как можно посмотреть в википедии - способов триангуляции существует несколько и один другого круче.
Но не беда прочитать о ней, хочется еще и не изобретать велосипед и взять что-то готовое. Так решил сделать и я, но попытки не увенчались успехом - алгоритм Делоне на 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
29
10 лет назад
0
nvc123, не совсем многоугольники, вот точный список
0
28
10 лет назад
0
public static void glDrawArrays (int mode, int first, int count)
параметр count передаётся не с помощью констант а обычным числом и означает количество вершин у фигуры
это open gl es 2.0
0
27
10 лет назад
0
nvc123, а первый параметр mode равен константным Triangles, Lines, Quadres :)
0
29
10 лет назад
0
nvc123, count должно быть кратным числом, иначе он просто часть вершин он не рассмотрит
0
28
10 лет назад
0
Extravert, нет
0
27
10 лет назад
0
nvc123, да
Parameters
mode
Specifies what kind of primitives to render. Symbolic constants GL_POINTS, GL_LINE_STRIP, GL_LINE_LOOP, GL_LINES, GL_LINE_STRIP_ADJACENCY, GL_LINES_ADJACENCY, GL_TRIANGLE_STRIP, GL_TRIANGLE_FAN, GL_TRIANGLES, GL_TRIANGLE_STRIP_ADJACENCY and GL_TRIANGLES_ADJACENCY are accepted.
0
28
10 лет назад
0
где тут Quadres?
0
27
10 лет назад
0
nvc123, нет его тут. Я его называю лишь из того что GL класс в юнити его самостоятельно переделывает
Бтв, речь изначально шла о том что GL в дефолте не держит многоугольники. Еще одно подтверждение.
0
1
9 лет назад
Отредактирован Devion
0
что то у меня ничего не получается..
создаю куб, стандартный юнити куб 1х1х1, потом что то такое :
Mesh mesh = gameObject.GetComponent<MeshFilter> ().mesh;
List<Vector3> listPoint = new List<Vector3> ();

for (int i = 0; i<mesh.vertices.Length; i++) {
listPoint.Add (mesh.vertices[i]);
}
Vector3[] verticles;
int[] triangles;
Vector2[] uvcoords;
Triangulation.GetResult (listPoint, true, Vector3.up, out verticles, out triangles, out uvcoords);
print (mesh.vertices.Length + "|количесво точек в меше" ); вывод - 24
print (verticles.Length + "|количестно новых точек триангуляции"); } вывод - 0
******************************************************
вопрос.. что не так... почему массив новых точек 0?
0
27
9 лет назад
Отредактирован Devion
0
taraa, вы отправляете на триангуляцию трехмерный объект, который соответственно нельзя представить в плоскости. Как минимум одна неверность уже есть.
Триангуляция это операция совершаемая в плоскости. Точки пространства же порождают непредсказуемо разные фигуры. То есть для обработки трехмерного объекта вам надо поделить модель на соответствующие "плоскости", которые и будете обрабатывать алгоритмом.
А второе это то что вы подаете "фигуру в целом". А надо подавать ее контур. То есть вы просто туда сейчас закидываете набор точек, некоторые из которых там по два три раза фигурируют. Если вы посмотрите комментарии выше, то увидите что триангуляция строилась по "контуру многоугольника", который вы и должны подать в функцию. В результате точки пересекают фигуру несколько раз и все они засчитываются как невалидные.
Например вот такая фигура по ясным причинам не является обычным многоугольником:
|\/|
|/\|
Она пересекает саму себя, если отправленных точек 4 и они идут накрест.
Триангуляция так не работает, ибо ни по одному варианту из трех точек этой фигуры в итоге нельзя построить треугольник, ибо он не принадлежит фигуре и/или пересекает ее грани.
Но если бы точек было 6 и они бы шли по/против часовой, то это бы прокатило.
Конкретно ваш случай - триангуляцию придется запускать 9 раз (для каждой стороны куба) и класть туда по 4 точки и указывая ось. Вообще не вижу смысла в таких вопросах применять триангуляцию, как то не по назначению.
0
1
9 лет назад
0
Extravert, оно конечно хорошо, но мне нужно только одну допустим грань разбить на маленькие кусочки полигонов, то есть допустим даже взять один полигон треугольной формы и раздробить на более мельче, допустим сделать 2 или 4 или 8 маленьких треугольников в одной плоскости. я просидел кучу времени и у меня не проходит проверку : !Intersect(lines, a, b) && !Intersect(lines, b, c) && !Intersect(lines, a, c)
насколько я понял - он ничего не делает поскольку полигон и так прямоугольник.. возможно если добавить точку по середине между действующими точками поможет... но пока не получается.. как быть.?? возможно вообще такое?
Показан только небольшой набор комментариев вокруг указанного. Перейти к актуальным.
Чтобы оставить комментарий, пожалуйста, войдите на сайт.