![](https://habrastorage.org/webt/4b/se/ny/4bsenyx2deo5lmmtgaubiqi5kwy.jpeg)
Что такое триангуляция?
В общем случае триангуляция – это разбиение геометрического объекта на треугольники. Это понятие само по себе довольно простое. Базовый пример триангуляции в случае игровых движков – это меш. Строго говоря меш может состоять не только из треугольников, но в игровых движках по целому ряду причин берутся именно меши, состоящие из треугольников.
![](https://habrastorage.org/webt/vm/zo/-o/vmzo-o4hsa5vx472qkg5nxqvxku.jpeg)
Триангуляции бывают разными, но один из самых популярных видов триангуляций является триангуляция Делоне. Этот вид триангуляции отличается тем свойством, что в окружности, описанной вокруг каждого треугольника, лежат только вершины этого треугольника.
![](https://habrastorage.org/webt/nx/ss/pp/nxssppvieg3beuq6bqiazugvhn8.png)
Зачем они нужны?
В целом за пределами игровой индустрии с помощью триангуляций решается большое количество задач. В геймдеве же первая задача, которая приходит на ум – это navigation mesh. Навмеш – это структура данных, которая определяет, по какому пространству игрок может ходить. Он позволяет избежать таких сложных вычислительных задач, как определение столкновений с частью окружения.
Вторая интересная задача, решаемая с помощью триангуляции Делоне в геймдеве – это генерация террейнов и объектов представленных в виде множества точек. Основным плюсом триангуляции Делоне в данном случае является то, что исходя из её свойств она позволяет избежать очень острых треугольников, которые будут мешать и создавать артефакты на тиррейне.
![](https://habrastorage.org/webt/78/yl/d1/78yld1jdecftxumbistwdmc-gaw.jpeg)
Помимо этого, с помощью триангуляции Делоне с ограничениями и таким алгоритмам как Chew's second algorithm и Ruppert's algorithm можно генерировать сетки ещё лучше для тиррейнов и генерировать хорошие сетки для другого применения – метода конечных элементов.
Сам по себе метод конечных элементов, это один из методов с помощью которого решаются задачи прикладной физике. В геймдеве он позволяет решать многие задачи, связанные с симуляцией деформаций, жидкостных симуляций и другого используемого для спец. эффектов. Обычно для записи эффектов в анимации, так как для реалтайма метод обладает слишком высокой вычислительной сложностью. Важной деталью при использовании метода является то, что ошибка метода зависит от углов треугольников в сетке. При наличии в сетке очень острых углов метод даёт огромную ошибку, по этой причине нужны алгоритмы, перечисленные выше.
![](https://habrastorage.org/webt/jx/ei/x8/jxeix82aopn6q0hjsj3te1beb6u.png)
Ну и конечно же в целом процедурная генерация мешей. Как пример в гитхаб проекте приведена сцена с возможностью рисовать меши. Некоторые физические головоломки используют это применение, как основную механику. Но кроме того алгоритмы триангуляции позволяют с помощью процедурной генерации решать такие задачи, как процедурная разрушаемость и прочее.
Помимо геймдева триангуляции используются в сетях, компьютерном зрении, различных аналитических алгоритмах, а так же в каких задачах вычислительной геометрии, как объединение и исключение многоугольников друг из друга (что бывает полезно часто и в задачах возникающих при разработке игр)
Ear Clipping with Holes
![](https://habrastorage.org/webt/6p/5l/je/6p5ljenmksewgdzp12ini57va-w.png)
Пожалуй, один из самых простых алгоритмов триангуляции. Даёт не лучшую сетку и обладает большой вычислительной сложностью О(n^2) в худшем случае.
Подробнее про него можно прочитать в этой статье
Bowyer–Watson algorithm
![](https://habrastorage.org/webt/pv/hy/hn/pvhyhn8ktwwigdkxfazttur14gi.jpeg)
Алгоритм, генерирующий триангуляцию Делоне по набору точек. В целом, как и у большинства алгоритмов Делоне при правильной реализации алгоритмическая сложность O( n log n), где n – количество вершин. Но в некоторых случаях может занимать O(n^2).
Минусами относительно Ear Clipping является то, что данный алгоритм строит выпуклую триангуляцию и в базовой реализации не предполагает дыр в получившейся сетке.
Обработка триангуляции Делоне (Delaunay refinement)
![](https://habrastorage.org/webt/va/hh/oo/vahhooegdpz-2vhs9b7e3qaesmi.gif)
Chew's second algorithm и Ruppert's algorithm – это алгоритмы, которые позволяют вводить ограничения в триангуляцию Делоне и задать минимальный угол треугольника в сетке. Важной деталью алгоритмов является то, что они могут уйти в бесконечный цикл и гарантировано дают результат при углах между примерно 20.7 градусов и 29 градусов. Возможность задать минимальный угол важна при решении задач, описанных выше.
Chew’s second algorithm реализован в бесплатном пакете www.cs.cmu.edu/~quake/triangle.html и его порте на .Net archive.codeplex.com/?p=triangle
Triangle.Net для Unity
Ну и раз уж с помощью триангуляций можно решать так много крутых задач, то на праздниках захотелось реализовать свою обёртку для Unity, чтобы всегда иметь под рукой удобный инструмент. В данной реализации алгоритм триангуляции в среднем работает за O(n), а в худшем за O(n * log n) – где n-количество вершин. К примеру, при тесте на 1кк вершин случайно разбросанных по квадрату юнити в редакторе на Intel Core i7-8700 строило сетку в среднем за 7.56 секунд.
Основные отличия от оригинальной библиотеки в наличии методов расширений заточенных под Unity, а так же замена double на float во всей библиотеке (+ пара определённых операторов для каста) Double в юнити не имеет особого смысла. Если считать физические симуляции, то я бы использовал отдельное приложение на плюсовой библиотеке, а результат вычислений уже отдавал Unity чисто для визуализации. А также переименован тип Mesh на TriangleNetMesh, чтобы не сбивать относительно Mesh из Unity. Да, они и так в разных неймспейсах, но тем не менее думаю новичков немного сбивал бы тот факт, что мы с помощью одного Mesh получаем другой.
Суть библиотеки в том, что вы сначала должны задать так называемый полигон. Потом на его основе сгенерировать уже меш. Для того, чтобы это работало с юнитёвыми структурами данных было введено несколько методов расширений.
public void GenerateMesh()
{
if(_CurrentState != MeshDrawerState.Nothing) return;
Polygon poly = new Polygon();
poly.Add(_Contour);
foreach (var hole in _Holes)
{
poly.Add(hole, true);
}
var triangleNetMesh = (TriangleNetMesh) poly.Triangulate();
GameObject go = new GameObject("Generated mesh");
var mf = go.AddComponent<MeshFilter>();
var mesh = triangleNetMesh.GenerateUnityMesh();
mesh.uv = GenerateUv(mesh.vertices);
mf.mesh = mesh;
var mr = go.AddComponent<MeshRenderer>();
mr.sharedMaterial = _MeshMaterial;
var collider = go.AddComponent<PolygonCollider2D>();
collider.points = _Contour.ToArray();
var rb = go.AddComponent<Rigidbody2D>();
rb.mass = triangleNetMesh.Triangles.Sum(tris => tris.Area);
Clear();
}
Для демонстрации и примера использования была сделана специальная демо-сцена с возможностью отрисовки мешей. С ней и портом библиотеки можно ознакомится в github проекте.
Спасибо за внимание! Надеюсь, что порт и статья кому-то будут полезны и стало чуть понятнее, зачем нужны триангуляция и знание математики в целом. Буду стараться продолжать раскрывать применения и способы решения разных математических задач в геймдеве. В самой вычислительной геометрии ещё очень много интересного, но помимо ещё есть множество других интересных разделов высшей математики.
Комментарии (6)
KsiOwn1t
08.01.2019 16:04спасибо, хоть понял немного, как новичок в юньке — информация важна, буду отслеживать)
CorvOrk
08.01.2019 16:04Спасибо за статью. Пробовал для триангуляции Triangle.NET и poly2Tri — последняя библиотека понравилась больше,
особенно в союзе с clipper (использовал для реализации динамического 2D навигационного меша).
Избавление от double это правильно (тот же recastnavigation, который использует Unity3D, довольстуется float),
но в некоторых случаях недостаточно — лучше полностью переходить на целые числа (как в AStarProject к примеру,
где многие функции используют перегрузку с Vector2/Vector3 на Int2/Int3),
особенно если код будет работать не только на клиенте.DyadichenkoGA Автор
08.01.2019 16:10Poly2Tri сильно слабее, и он генерит не очень хорошие сетки. Но он прям заточен под Unity, в отличии от Triangle.Net. Я использовал Poly2Tri в этом проекте — для такого норм. В целом зависит от конкретной задачи + лицензии тоже важны. Poly2Tri кажется под MSPL, а Triangle.Net — MIT. И MIT даёт больше возможностей по использованию.
У меня сейчас есть идея поиграться с FEM (метод конечных элементов) в Unity, а для этого лучше иметь Delanay Refinement алгоритмы под рукой.
Между этими двумя либами основная разница, что Poly2Tri сильно проще, но Triangle.Net в разы мощнее и позволяет решать большее число задач, так как судя по сетке Poly2Tri, у него под капотом Ear Clipping with Holes.CorvOrk
08.01.2019 16:37Согласен с Вами. Poly2Tri намного проще, собственно поэтому и использовал — мне было важно полностью понимать каждое действие — читал статьи + смотрел готовые реализации. По сути использовал связку Poly2Tri c Clipper в качестве «прототипа», потом все переписывал — в целом эта связка делала ту часть работы, которая нужна для построения динамического nav mesh, в основном первые этапы.
По поводу построения сетки — там на самом деле много было проблем из-за float, переписывание на интах сильно помогает, особенно когда речь идет не просто о построении, а о последующем применении рейкаста к этой сетки (например движение персонажа, управляемого игроком при помощи джостика — в RTS с этим проще, там во многом достаточно pathfinding применить)
EndUser
По np-задаче выпуклого разбиения 3д-мешей имеет смысл что-то искать? Или "специально обученный человек" ® дешевле всегда?
DyadichenkoGA Автор
Если ты про эту задачу codesuppository.blogspot.com/2011/05/hacd-hierarchical-approximate-convex.html я находил только частные случаи или разные реализации HACD. В целом зависит от требований, но если писать с нуля — «обученный человек» дешевле и лучше сделает, если не продавать само такое решение. Мало кому это надо в промышленных масштабах