Главная » Игры » Математика в Gamedev по-простому. Триангуляции и Triangle.Net в Unity

Математика в Gamedev по-простому. Триангуляции и Triangle.Net в Unity

Всем привет! Меня зовут Гриша, и я основатель CGDevs. Математика – очень крутой инструмент при разработке игр. Но если скажем без понимания векторов и матриц обойтись в принципе сложно, то алгоритмы триангуляций не столь обязательная вещь, но с помощью них решается достаточно большое количество интересных задач. Сегодня хотелось бы поговорить про достаточно важный инструмент в вычислительной геометрии, такой как триангуляции и их применение в игровой индустрии. Кроме того, я написал порт и немного обёрток великолепной библиотеки Triangle.Net для Unity. Если интересно – добро пожаловать под кат. Ссылка на гитхаб прилагается.

Что такое триангуляция?

В общем случае триангуляция – это разбиение геометрического объекта на треугольники. Это понятие само по себе довольно простое. Базовый пример триангуляции в случае игровых движков – это меш. Строго говоря меш может состоять не только из треугольников, но в игровых движках по целому ряду причин берутся именно меши, состоящие из треугольников.

Триангуляции бывают разными, но один из самых популярных видов триангуляций является триангуляция Делоне. Этот вид триангуляции отличается тем свойством, что в окружности, описанной вокруг каждого треугольника, лежат только вершины этого треугольника.

Зачем они нужны?

В целом за пределами игровой индустрии с помощью триангуляций решается большое количество задач. В геймдеве же первая задача, которая приходит на ум – это navigation mesh. Навмеш – это структура данных, которая определяет, по какому пространству игрок может ходить. Он позволяет избежать таких сложных вычислительных задач, как определение столкновений с частью окружения.

Основным плюсом триангуляции Делоне в данном случае является то, что исходя из её свойств она позволяет избежать очень острых треугольников, которые будут мешать и создавать артефакты на тиррейне. Вторая интересная задача, решаемая с помощью триангуляции Делоне в геймдеве – это генерация террейнов и объектов представленных в виде множества точек.

Помимо этого, с помощью триангуляции Делоне с ограничениями и таким алгоритмам как Chew's second algorithm и Ruppert's algorithm можно генерировать сетки ещё лучше для тиррейнов и генерировать хорошие сетки для другого применения – метода конечных элементов.

В геймдеве он позволяет решать многие задачи, связанные с симуляцией деформаций, жидкостных симуляций и другого используемого для спец. Сам по себе метод конечных элементов, это один из методов с помощью которого решаются задачи прикладной физике. Обычно для записи эффектов в анимации, так как для реалтайма метод обладает слишком высокой вычислительной сложностью. эффектов. При наличии в сетке очень острых углов метод даёт огромную ошибку, по этой причине нужны алгоритмы, перечисленные выше. Важной деталью при использовании метода является то, что ошибка метода зависит от углов треугольников в сетке.

Как пример в гитхаб проекте приведена сцена с возможностью рисовать меши. Ну и конечно же в целом процедурная генерация мешей. Но кроме того алгоритмы триангуляции позволяют с помощью процедурной генерации решать такие задачи, как процедурная разрушаемость и прочее. Некоторые физические головоломки используют это применение, как основную механику.

Помимо геймдева триангуляции используются в сетях, компьютерном зрении, различных аналитических алгоритмах, а так же в каких задачах вычислительной геометрии, как объединение и исключение многоугольников друг из друга (что бывает полезно часто и в задачах возникающих при разработке игр)

Ear Clipping with Holes

Даёт не лучшую сетку и обладает большой вычислительной сложностью О(n^2) в худшем случае. Пожалуй, один из самых простых алгоритмов триангуляции.

Подробнее про него можно прочитать в этой статье

Bowyer–Watson algorithm

В целом, как и у большинства алгоритмов Делоне при правильной реализации алгоритмическая сложность O( n log n), где n – количество вершин. Алгоритм, генерирующий триангуляцию Делоне по набору точек. Но в некоторых случаях может занимать O(n^2).

Минусами относительно Ear Clipping является то, что данный алгоритм строит выпуклую триангуляцию и в базовой реализации не предполагает дыр в получившейся сетке.

Обработка триангуляции Делоне (Delaunay refinement)

Важной деталью алгоритмов является то, что они могут уйти в бесконечный цикл и гарантировано дают результат при углах между примерно 20. Chew's second algorithm и Ruppert's algorithm – это алгоритмы, которые позволяют вводить ограничения в триангуляцию Делоне и задать минимальный угол треугольника в сетке. Возможность задать минимальный угол важна при решении задач, описанных выше. 7 градусов и 29 градусов.

Net archive.codeplex.com/?p=triangle Chew’s second algorithm реализован в бесплатном пакете www.cs.cmu.edu/~quake/triangle.html и его порте на .

Triangle.Net для Unity

Ну и раз уж с помощью триангуляций можно решать так много крутых задач, то на праздниках захотелось реализовать свою обёртку для Unity, чтобы всегда иметь под рукой удобный инструмент. В данной реализации алгоритм триангуляции в среднем работает за O(n), а в худшем за O(n * log n) – где n-количество вершин. К примеру, при тесте на 1кк вершин случайно разбросанных по квадрату юнити в редакторе на Intel Core i7-8700 строило сетку в среднем за 7.56 секунд.

Если считать физические симуляции, то я бы использовал отдельное приложение на плюсовой библиотеке, а результат вычислений уже отдавал Unity чисто для визуализации. Основные отличия от оригинальной библиотеки в наличии методов расширений заточенных под Unity, а так же замена double на float во всей библиотеке (+ пара определённых операторов для каста) Double в юнити не имеет особого смысла. Да, они и так в разных неймспейсах, но тем не менее думаю новичков немного сбивал бы тот факт, что мы с помощью одного Mesh получаем другой. А также переименован тип Mesh на TriangleNetMesh, чтобы не сбивать относительно Mesh из Unity.

Потом на его основе сгенерировать уже меш. Суть библиотеки в том, что вы сначала должны задать так называемый полигон. Для того, чтобы это работало с юнитёвыми структурами данных было введено несколько методов расширений.

Пример использования

public void GenerateMesh()
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 проекте.

Надеюсь, что порт и статья кому-то будут полезны и стало чуть понятнее, зачем нужны триангуляция и знание математики в целом. Спасибо за внимание! В самой вычислительной геометрии ещё очень много интересного, но помимо ещё есть множество других интересных разделов высшей математики. Буду стараться продолжать раскрывать применения и способы решения разных математических задач в геймдеве.


Оставить комментарий

Ваш email нигде не будет показан
Обязательные для заполнения поля помечены *

*

x

Ещё Hi-Tech Интересное!

Не бойтесь пробовать, или Как я стала программистом в возрасте далеко за 18

Когда вы слышите словосочетание «младший разработчик», то наверняка представляете молодого парня на последних курсах вуза или недавнего выпускника — но уж никак не 30-летнюю женщину с маленьким ребёнком, которая до этого несколько лет преподавала в вузе и от разработки была ...

[Перевод] Open source не приносит денег, потому что не создан для этого

Лучший способ что-то сделать — хотя бы попробовать Все знают, что на open source невозможно заработать, верно? Это десятки (сотни?) успешных проектов с открытым исходным кодом. Я сейчас размышляю на эту тему, потому что Mozilla хочет в ближайшие несколько лет ...