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

Добавлен , опубликован
Триангуляция по простому - разбиение фигуры на треугольники. Подобная операция может понадобиться при создании как нестандартной области выделения, так и при генерации моделей из кода.
Однако, как можно посмотреть в википедии - способов триангуляции существует несколько и один другого круче.
Но не беда прочитать о ней, хочется еще и не изобретать велосипед и взять что-то готовое. Так решил сделать и я, но попытки не увенчались успехом - алгоритм Делоне на 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
27
10 лет назад
Отредактирован Devion
0
alexprey, с текстурными координатами вроде там все просто - эти же точки и есть текстурные координаты. Хотя могу ошибаться, меш еще с этим не текстурил
Проверил - не ошибся
вот код-пример использования с мешем по оси Y
    public void Calculate()
    {
        //Add points
        var points = new List<Vector3>();
        for (int i = 0; i < transform.childCount; i++)
            points.Add(transform.GetChild(i).localPosition);

        //Triangulation
        var result = Triangulation.GetResult(points.Select(v => new Vector2(v.x, v.z)).ToList(), true);

        //Get Verticles
        var verticles = result.Select(v => new Vector3(v.x, 0, v.y)).ToList();
        //Get Triangles - тупо значения от 0 и ++
        var triangles = new int[verticles.Count];
        for (int i = 0; i < verticles.Count; i++)
            triangles[i] = i;

        //Create mesh
        var mesh = new Mesh { vertices = verticles.ToArray(), triangles = triangles.ToArray(), uv = result.ToArray() };
        mesh.RecalculateNormals();

        //Add mesh in MeshFilter
        var f = GetComponent<MeshFilter>();
        if (f.sharedMesh != null)
            DestroyImmediate(f.sharedMesh);
        f.sharedMesh = mesh;
    }
Естественно по нестандартной оси появилось бы еще немного работы с кватернионом
Загруженные файлы
0
28
10 лет назад
0
а что в юнити модели только из трианглов сделаны?
1
27
10 лет назад
1
nvc123, из полигонов, если быть точным. Они могут быть представлены как трианглами, так и квадрами.
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, если бы я делал тесселяцию - я бы не триангуляцией как таковой пользовался бы, а скорее делением треугольника на более мелкие - так как это в разы быстрее (имею ввиду когда заранее известно что стороны три и нужно из них образовать два-три подтриангла это пошустрее чем делоне и ушная). Почему-то есть предчувствие что именно так оно и реализовано.
Показан только небольшой набор комментариев вокруг указанного. Перейти к актуальным.
Чтобы оставить комментарий, пожалуйста, войдите на сайт.