Триангуляция по простому - разбиение фигуры на треугольники. Подобная операция может понадобиться при создании как нестандартной области выделения, так и при генерации моделей из кода.
Однако, как можно посмотреть в википедии - способов триангуляции существует несколько и один другого круче.
Но не беда прочитать о ней, хочется еще и не изобретать велосипед и взять что-то готовое. Так решил сделать и я, но попытки не увенчались успехом - алгоритм Делоне на 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]