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

Добавлен , опубликован
Триангуляция по простому - разбиение фигуры на треугольники. Подобная операция может понадобиться при создании как нестандартной области выделения, так и при генерации моделей из кода.
Однако, как можно посмотреть в википедии - способов триангуляции существует несколько и один другого круче.
Но не беда прочитать о ней, хочется еще и не изобретать велосипед и взять что-то готовое. Так решил сделать и я, но попытки не увенчались успехом - алгоритм Делоне на 1000 строк кода часть треугольников зачем-то переворачивал, а ушная триангуляция прикрепленная к самой вики статье - на 7000 строк ужасно кривого кода, в котором просто невозможно разобраться. Это принудило меня к написанию алгоритма с нуля - встречайте, ушная триангуляция для Unity всего на 100 строк.
Как работает:
  • Закиньте скрипт в папку с проектом
  • В коде используйте Triangulation.GetResult для получения результата триангуляции. У метода есть две перегрузки
1 перегрузка (стандартная)
На вход в методе имеется два параметра:
  • List<Vector2> points - точки многоугольника
Триангуляция - это работа в плоскости, потому вектора двумерные. Если внимательно посмотреть, то вариантов разбиения многоугольника на треугольники всегда несколько и в пространстве это бы возвращало разные фигуры. Потому даже не пытайтесь приводить это к трехмерному вектору, не повторяйте моих глупых ошибок :)
  • bool clockwise - если true, то полученные точки обрабатываются по часовой, если false - против часовой.
На выходе возвращается:
  • List<Vector2> - точки треугольников
Список по количеству всегда кратен 3, то есть через каждые три индекса описывается новый треугольник
Пример использования:
var result = Triangulation.GetResult(points, true);
2 перегрузка (быстрая конвертация)
В методе имеется 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:
В комментариях приложен доработанный код с более быстрым алгоритмом.

Показан только небольшой набор комментариев вокруг указанного. Перейти к актуальным.
0
28
10 лет назад
0
Extravert, нет
0
27
10 лет назад
0
nvc123, да
Parameters
mode
Specifies what kind of primitives to render. Symbolic constants GL_POINTS, GL_LINE_STRIP, GL_LINE_LOOP, GL_LINES, GL_LINE_STRIP_ADJACENCY, GL_LINES_ADJACENCY, GL_TRIANGLE_STRIP, GL_TRIANGLE_FAN, GL_TRIANGLES, GL_TRIANGLE_STRIP_ADJACENCY and GL_TRIANGLES_ADJACENCY are accepted.
0
28
10 лет назад
0
где тут Quadres?
0
27
10 лет назад
0
nvc123, нет его тут. Я его называю лишь из того что GL класс в юнити его самостоятельно переделывает
Бтв, речь изначально шла о том что GL в дефолте не держит многоугольники. Еще одно подтверждение.
0
1
9 лет назад
Отредактирован Devion
0
что то у меня ничего не получается..
создаю куб, стандартный юнити куб 1х1х1, потом что то такое :
Mesh mesh = gameObject.GetComponent<MeshFilter> ().mesh;
List<Vector3> listPoint = new List<Vector3> ();

for (int i = 0; i<mesh.vertices.Length; i++) {
listPoint.Add (mesh.vertices[i]);
}
Vector3[] verticles;
int[] triangles;
Vector2[] uvcoords;
Triangulation.GetResult (listPoint, true, Vector3.up, out verticles, out triangles, out uvcoords);
print (mesh.vertices.Length + "|количесво точек в меше" ); вывод - 24
print (verticles.Length + "|количестно новых точек триангуляции"); } вывод - 0
******************************************************
вопрос.. что не так... почему массив новых точек 0?
0
27
9 лет назад
Отредактирован Devion
0
taraa, вы отправляете на триангуляцию трехмерный объект, который соответственно нельзя представить в плоскости. Как минимум одна неверность уже есть.
Триангуляция это операция совершаемая в плоскости. Точки пространства же порождают непредсказуемо разные фигуры. То есть для обработки трехмерного объекта вам надо поделить модель на соответствующие "плоскости", которые и будете обрабатывать алгоритмом.
А второе это то что вы подаете "фигуру в целом". А надо подавать ее контур. То есть вы просто туда сейчас закидываете набор точек, некоторые из которых там по два три раза фигурируют. Если вы посмотрите комментарии выше, то увидите что триангуляция строилась по "контуру многоугольника", который вы и должны подать в функцию. В результате точки пересекают фигуру несколько раз и все они засчитываются как невалидные.
Например вот такая фигура по ясным причинам не является обычным многоугольником:
|\/|
|/\|
Она пересекает саму себя, если отправленных точек 4 и они идут накрест.
Триангуляция так не работает, ибо ни по одному варианту из трех точек этой фигуры в итоге нельзя построить треугольник, ибо он не принадлежит фигуре и/или пересекает ее грани.
Но если бы точек было 6 и они бы шли по/против часовой, то это бы прокатило.
Конкретно ваш случай - триангуляцию придется запускать 9 раз (для каждой стороны куба) и класть туда по 4 точки и указывая ось. Вообще не вижу смысла в таких вопросах применять триангуляцию, как то не по назначению.
0
1
9 лет назад
0
Extravert, оно конечно хорошо, но мне нужно только одну допустим грань разбить на маленькие кусочки полигонов, то есть допустим даже взять один полигон треугольной формы и раздробить на более мельче, допустим сделать 2 или 4 или 8 маленьких треугольников в одной плоскости. я просидел кучу времени и у меня не проходит проверку : !Intersect(lines, a, b) && !Intersect(lines, b, c) && !Intersect(lines, a, c)
насколько я понял - он ничего не делает поскольку полигон и так прямоугольник.. возможно если добавить точку по середине между действующими точками поможет... но пока не получается.. как быть.?? возможно вообще такое?
0
27
9 лет назад
Отредактирован Devion
0
taraa, треугольники на более мелкие нужно разбивать другим алгоритмом. Как это сделать проще всего?
Взять ваш треугольник, на самом широком ребре найти середину, разбить. И повторять так с каждой более мелкой фигурой, пока не достигнете необходимой вам глубины деления.
Почему может не пройти проверка? Очень просто. Линии, которые кладутся в алгоритм изначально собираются "подряд". То есть первая точка связана со второй, вторая с третьей и так далее. Когда вы построили куб, то там вероятно был стык, когда две точки имеют одинаковую координату. Таким образом эти точки пересекаются и проверка не идет. В прямоугольнике у вас должно быть 4 точки, чтобы он разбился например на два треугольника. А не 6, как вероятнее всего они описаны в меше.
Я вас уверяю в описанном вам случае вам не нужна триангуляция. Достаточно сделать то что я описал в самом начале.
То есть.
Берете ваши вертексы из меша. Берете трианглес оттуда же, чтобы узнать в каком порядке вертексы располагаются. Согласно этому порядку берете первые три индекса из массива трианглс, далее по этим индексам обращаетесь к вертексам и кладете все в свой массив. И запускаете в алгоритм, который узнает между какими из трех точек наибольшее расстояние. Вычитаете вектора, делите полученный вектор пополам, прибавляете обратно. И вы узнали точку, образующую новые треугольники.
0
1
9 лет назад
0
Extravert, спасибо)) Вы подтвердили мою вчерашнею теорию над которой сидел.. только я когда добавил новую точку дополнительно прогонял через функцию GetResult.. и для чого непонятно... только запутался.
2
29
9 лет назад
2
Extravert, nvc123, по поводу нашего разговора о стандартном функционале триангуляции средствами OpenGL. Я тут пока делал лабу на компьютерную графику по OpenGL разобрался в чем соль данного параметра. Это не тип рендера, а порядок обхода вершин. То есть указав 4 вершины и указав тип Quadres он просто создаст 2 треугольника, 1-2-3 и 3-4-1
1
27
9 лет назад
Отредактирован Devion
1
Господа, таки подстиг я дзен и нашел способ значительно улучшить алгоритм. На замерах кода показывает, что при тестовых условиях новый алгоритм в 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();
    }
}
Я еще немного поработаю над ним, он выйдет, конечно, чуть-чуть поширше, но зато будет более удобным к использованию. Например хочется добавить автоматическое переворачивание точек многоугольника в нужный формат или возможность подать самопересекаемую фигуру.
Вообще есть мысль написать полноценную статью по многоугольникам, так как последнее время пришлось много с ними работать - кое-что напридумывал, один алгоритм даже абсолютно уникальный, из головы :) Что думаете?
Еще один вариант - удаляет избыточные точки. Производительность этого способа выше на большом многоугольнике (от 100 точек). Кстати по тесту код был в 70 раз быстрее старого способа.
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;
    }
}
Показан только небольшой набор комментариев вокруг указанного. Перейти к актуальным.
Чтобы оставить комментарий, пожалуйста, войдите на сайт.