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

Question

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

Devion

5 мая 2014

22 окт. 2017

Триангуляция — Unity — DevTribe: инди-игры, разработка, сообщество

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

UPDATE:

В комментариях приложен доработанный код с более быстрым алгоритмом.

2
3
4 (Текущая страница)

Devion - 16 авг. 2015 0

Господа, таки подстиг я дзен и нашел способ значительно улучшить алгоритм. На замерах кода показывает, что при тестовых условиях новый алгоритм в 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;
    }
}

16 авг. 2015

2
3
4 (Текущая страница)

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

Смотрите также:

Комментарии