Триангуляция по простому - разбиение фигуры на треугольники. Подобная операция может понадобиться при создании как нестандартной области выделения, так и при генерации моделей из кода.
Однако, как можно посмотреть в википедии - способов триангуляции существует несколько и один другого круче.
Но не беда прочитать о ней, хочется еще и не изобретать велосипед и взять что-то готовое. Так решил сделать и я, но попытки не увенчались успехом - алгоритм Делоне на 1000 строк кода часть треугольников зачем-то переворачивал, а ушная триангуляция прикрепленная к самой вики статье - на 7000 строк ужасно кривого кода, в котором просто невозможно разобраться. Это принудило меня к написанию алгоритма с нуля - встречайте, ушная триангуляция для Unity всего на 100 строк.
Как работает:
- Закиньте скрипт в папку с проектом
- В коде используйте Triangulation.GetResult для получения результата триангуляции. У метода есть две перегрузки
На вход в методе имеется два параметра:
- List<Vector2> points - точки многоугольника
Триангуляция - это работа в плоскости, потому вектора двумерные. Если внимательно посмотреть, то вариантов разбиения многоугольника на треугольники всегда несколько и в пространстве это бы возвращало разные фигуры. Потому даже не пытайтесь приводить это к трехмерному вектору, не повторяйте моих глупых ошибок :)
- bool clockwise - если true, то полученные точки обрабатываются по часовой, если false - против часовой.
На выходе возвращается:
- List<Vector2> - точки треугольников
Список по количеству всегда кратен 3, то есть через каждые три индекса описывается новый треугольник
Пример использования:
var result = Triangulation.GetResult(points, true);
В методе имеется 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);
В комментариях приложен доработанный код с более быстрым алгоритмом.
Смотрите также:
Комментарии
Господа, таки подстиг я дзен и нашел способ значительно улучшить алгоритм. На замерах кода показывает, что при тестовых условиях новый алгоритм в 20 раз быстрее, но я предполагаю, что это был субъективный замер. Однако могу заверить, что на выпуклых многоугольниках новый алгоритм - полиноминален. Кроме того, измененный код занимает всего 57 строк. Его можно было бы ужать еще больше, но там уже страдает оптимизация.
using System.Collections.Generic; using UnityEngine; public static class Triangulation { public static List<Vector2> GetVertices(List<Vector2> points) { var results = new List<Vector2>(); var checkPoints = new List<Vector2>(); for (int j = points.Count - 1; j >= 0; j--) { var a = points[(j + points.Count - 1) % points.Count]; var b = points[j]; var c = points[(j + 1) % points.Count]; if (GetClockwiseCoef(a - b, c - b) < 0f) checkPoints.Add(b); } for (int j = points.Count - 1; j >= 0; j--) { var a = points[(j + points.Count - 1) % points.Count]; var b = points[j]; var c = points[(j + 1) % points.Count]; if (GetClockwiseCoef(a - b, c - b) > 0f && !TriangleStrictlyAnyContains(a, b, c, checkPoints)) { results.AddRange(new[] { a, b, c }); points.RemoveAt(j); j = points.Count - 1; } } return results; } private static float GetClockwiseCoef(Vector2 v1, Vector2 v2) { return Mathf.Sign(v1.x * v2.y - v1.y * v2.x); } private static bool TriangleStrictlyAnyContains(Vector2 a, Vector2 b, Vector2 c, List<Vector2> points) { if (points.Count == 0) return false; var ky1 = (b.y - a.y); var ky2 = (c.y - b.y); var ky3 = (a.y - c.y); var kx1 = (b.x - a.x); var kx2 = (c.x - b.x); var kx3 = (a.x - c.x); for (int i = 0; i < points.Count; i++) { var point = points[i]; var a1 = (a.x - point.x) * ky1 - kx1 * (a.y - point.y); var b1 = (b.x - point.x) * ky2 - kx2 * (b.y - point.y); var c1 = (c.x - point.x) * ky3 - kx3 * (c.y - point.y); if ((a1 < 0 && b1 < 0 && c1 < 0) || (a1 > 0 && b1 > 0 && c1 > 0)) return true; } return false; } }
Ради спортивного интереса попробовал его ужать еще сильнее, его можно описать в 39 строк, но с небольшим ущербом для производительности :)
using System.Collections.Generic; using System.Linq; using UnityEngine; public static class Triangulation { public static List<Vector2> GetVertices(List<Vector2> points) { var results = new List<Vector2>(); var checkPoints = new List<Vector2>(); for (int j = points.Count - 1; j >= 0; j--) { var a = points[(j + points.Count - 1) % points.Count]; var b = points[j]; var c = points[(j + 1) % points.Count]; if (GetClockwiseCoef(a - b, c - b) < 0f) checkPoints.Add(b); } for (int j = points.Count - 1; j >= 0; j--) { var a = points[(j + points.Count - 1) % points.Count]; var b = points[j]; var c = points[(j + 1) % points.Count]; if (!(GetClockwiseCoef(a - b, c - b) > 0f) || TriangleStrictlyAnyContains(a, b, c, checkPoints)) continue; results.AddRange(new[] { a, b, c }); points.RemoveAt(j); j = points.Count - 1; } return results; } private static float GetClockwiseCoef(Vector2 v1, Vector2 v2) { return Mathf.Sign(v1.x * v2.y - v1.y * v2.x); } private static bool TriangleStrictlyAnyContains(Vector2 a, Vector2 b, Vector2 c, List<Vector2> points) { return (from point in points let a1 = (a.x - point.x)*(b.y - a.y) - (b.x - a.x)*(a.y - point.y) let b1 = (b.x - point.x)*(c.y - b.y) - (c.x - b.x)*(b.y - point.y) let c1 = (c.x - point.x)*(a.y - c.y) - (a.x - c.x)*(c.y - point.y) where (a1 < 0 && b1 < 0 && c1 < 0) || (a1 > 0 && b1 > 0 && c1 > 0) select a1).Any(); } }
Я еще немного поработаю над ним, он выйдет, конечно, чуть-чуть поширше, но зато будет более удобным к использованию. Например хочется добавить автоматическое переворачивание точек многоугольника в нужный формат или возможность подать самопересекаемую фигуру.
Вообще есть мысль написать полноценную статью по многоугольникам, так как последнее время пришлось много с ними работать - кое-что напридумывал, один алгоритм даже абсолютно уникальный, из головы :) Что думаете?
using System.Collections.Generic; using UnityEngine; public static class Triangulation { public static List<Vector2> GetVertices(List<Vector2> points) { var results = new List<Vector2>(); var allPoints = new List<P>(points.Count); var checkPoints = new List<P>(); for (int j = points.Count - 1; j >= 0; j--) { var a = points[(j + points.Count - 1) % points.Count]; var b = points[j]; var c = points[(j + 1) % points.Count]; var p = new P { x = b.x, y = b.y }; allPoints.Insert(0, p); if (GetClockwiseCoef(a.x - b.x, a.y - b.y, c.x - b.x, c.y - b.y) < 0f) checkPoints.Add(p); } for (int j = allPoints.Count - 1; j >= 0; j--) { var a = allPoints[(j + allPoints.Count - 1) % allPoints.Count]; var b = allPoints[j]; var c = allPoints[(j + 1) % allPoints.Count]; if (GetClockwiseCoef(a.x - b.x, a.y - b.y, c.x - b.x, c.y - b.y) > 0f && !TriangleStrictlyAnyContains(a, b, c, checkPoints)) { results.AddRange(new[] { new Vector2(a.x, a.y), new Vector2(b.x, b.y), new Vector2(c.x, c.y) }); Remove(allPoints, j); j = allPoints.Count - 1; } } return results; } private static void Remove(List<P> p, int index) { p[index].needRemove = true; p.RemoveAt(index); } private class P { public float x; public float y; public bool needRemove; } private static float GetClockwiseCoef(float x1, float y1, float x2, float y2) { return Mathf.Sign(x1 * y2 - y1 * x2); } private static bool TriangleStrictlyAnyContains(P a, P b, P c, List<P> points) { if (points.Count == 0) return false; var ky1 = (b.y - a.y); var ky2 = (c.y - b.y); var ky3 = (a.y - c.y); var kx1 = (b.x - a.x); var kx2 = (c.x - b.x); var kx3 = (a.x - c.x); for (int i = 0; i < points.Count; i++) { var point = points[i]; if (point.needRemove) { points.RemoveAt(i--); continue; } var a1 = (a.x - point.x) * ky1 - kx1 * (a.y - point.y); var b1 = (b.x - point.x) * ky2 - kx2 * (b.y - point.y); var c1 = (c.x - point.x) * ky3 - kx3 * (c.y - point.y); if ((a1 < 0 && b1 < 0 && c1 < 0) || (a1 > 0 && b1 > 0 && c1 > 0)) return true; } return false; } }
CollectableItemData.cs
[CreateMenuItem(fileName = "newItem", menuName = "Data/Items/Collectable", order = 51]