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

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


Просмотров: 9 175

» Лучшие комментарии


alexprey #1 - 3 года назад 1
Круто! Штука весьма полезная, особенно для динамического создания различных эффектов. Жаль только текстурные координаты не генерирует
NCrashed #3 - 3 года назад 1
Схоронил, однажды понадобилась и я забил именно из-за 7к кривых строк, которые еще нужно переписывать. Этот код гораздо легче портировать.
Devion #4 - 3 года назад (отредактировано ) 0
alexprey, с текстурными координатами вроде там все просто - эти же точки и есть текстурные координаты. Хотя могу ошибаться, меш еще с этим не текстурил
Проверил - не ошибся
» вот код-пример использования с мешем по оси Y
    public void Calculate()
    {
        //Add points
        var points = new List<Vector3>();
        for (int i = 0; i < transform.childCount; i++)
            points.Add(transform.GetChild(i).localPosition);

        //Triangulation
        var result = Triangulation.GetResult(points.Select(v => new Vector2(v.x, v.z)).ToList(), true);

        //Get Verticles
        var verticles = result.Select(v => new Vector3(v.x, 0, v.y)).ToList();
        //Get Triangles - тупо значения от 0 и ++
        var triangles = new int[verticles.Count];
        for (int i = 0; i < verticles.Count; i++)
            triangles[i] = i;

        //Create mesh
        var mesh = new Mesh { vertices = verticles.ToArray(), triangles = triangles.ToArray(), uv = result.ToArray() };
        mesh.RecalculateNormals();

        //Add mesh in MeshFilter
        var f = GetComponent<MeshFilter>();
        if (f.sharedMesh != null)
            DestroyImmediate(f.sharedMesh);
        f.sharedMesh = mesh;
    }
Естественно по нестандартной оси появилось бы еще немного работы с кватернионом
прикреплены файлы
Devion #6 - 3 года назад 1
nvc123, из полигонов, если быть точным. Они могут быть представлены как трианглами, так и квадрами.
nvc123 #7 - 3 года назад 0
Extravert, это понятно что из полигонов
просто некоторые движки позволяют юзать не только трианглы и квадры
Devion #8 - 3 года назад 0
nvc123, например?
Cinos #9 - 3 года назад 0
nvc123, может, ты имел ввиду просто трёхмерные редакторы?
Extravert, молодец!
Devion #10 - 3 года назад 1
Обновлено.
Добавлена перегрузка, конвертирующая пространственные координаты по указанной нами оси и возвращающая (координаты точек + порядок рисования + текстурные координаты).
В общем для создания мешей удобней и быть не может.
nvc123 #11 - 3 года назад 0
Extravert, ну во всяком случае опен гл спрашивает количество точек у полигона
хотя возможно он сам проводит триангуляцию
но даже если и делит на трианглы то делает это на gpu
Senbonzakura #12 - 3 года назад 0
nvc123:
Extravert, это понятно что из полигонов
просто некоторые движки позволяют юзать не только трианглы и квадры
Многие автоматически разбивают на трианглы при экспорте модели)
alexprey #13 - 3 года назад 1
nvc123, как в OpenGL так и в DirectX при DrawCall передается буфер вершин, а уж что он с ними делает зависит от состояния конвеера рендера. Там можно указывать что он будет их рисовать как квады или как трианглы или еще как-что нибудь. Уже не помню полный список, но это два основных. Триангуляцию на GPU никто не делает автоматически, хотя сейчас есть тессяляция, в которой наверное можно как то посчитать триангуляцию, но не уверен. Хотя на самом деле нет смысла делать постоянно триангуляцию, достаточно сделать лишь 1 раз, а потом рендерить полученный меш, а если уж возникла потребность перемещать точки, то при небольших изменениях ничего не случится с мешем, так что можно пересчитывать где-то на каждые кадров 5, при условии медленного изменения сетки
Devion #14 - 3 года назад (отредактировано ) 0
Extravert, ну во всяком случае опен гл спрашивает количество точек у полигона
хотя возможно он сам проводит триангуляцию
но даже если и делит на трианглы то делает это на gpu
Многие автоматически разбивают на трианглы при экспорте модели)
Из нестандартных форм полигонов движок держит только квадры, все остальные как и сказал Senbonzakura переделываются в трианглы. В программах для моделлирования уж точно - там по дефолту рендер производится через ЦПУ, если явно не указано использование графического конвейера, так как ЦПУ и ГПУ производят принципиально разный рендер. *Тут был рассказ о том в чем их отличие но я кажется ухожу от темы*.
ГПУ не делит на трианглы даже по той простой причине, что запекание предварительных данных не его обязанность вовсе. А данный алгоритм в рамках ГПУ и кадровых операций весьма затратный, даже если пользоваться самыми быстрыми методами. Короче, все делится на трианглы предварительно, даже в максе, просто пользователю это знать не обязательно.
alexprey, если бы я делал тесселяцию - я бы не триангуляцией как таковой пользовался бы, а скорее делением треугольника на более мелкие - так как это в разы быстрее (имею ввиду когда заранее известно что стороны три и нужно из них образовать два-три подтриангла это пошустрее чем делоне и ушная). Почему-то есть предчувствие что именно так оно и реализовано.
alexprey #15 - 3 года назад 0
Extravert, ну вообще да, тесселяция это именно увеличение\уменьшение детализации для готовой сетки, но возможность такая есть.
Extravert:
Почему-то есть предчувствие что именно так оно и реализовано.
самая простая тесселяция да, для более крутой уже используются карты нормалей, карты высот и прочая дополнительная ересь высокого разрешения
nvc123 #16 - 3 года назад 0
Extravert, только что писали что open gl и derectx могут принимать много-угольники и без всякой триангуляции
alexprey #17 - 3 года назад 0
nvc123, не совсем многоугольники, вот точный список
nvc123 #18 - 3 года назад 0
public static void glDrawArrays (int mode, int first, int count)
параметр count передаётся не с помощью констант а обычным числом и означает количество вершин у фигуры
это open gl es 2.0
Devion #19 - 3 года назад 0
nvc123, а первый параметр mode равен константным Triangles, Lines, Quadres :)
alexprey #20 - 3 года назад 0
nvc123, count должно быть кратным числом, иначе он просто часть вершин он не рассмотрит
Devion #22 - 3 года назад 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.
Devion #24 - 3 года назад 0
nvc123, нет его тут. Я его называю лишь из того что GL класс в юнити его самостоятельно переделывает
Бтв, речь изначально шла о том что GL в дефолте не держит многоугольники. Еще одно подтверждение.
taraa #25 - 3 года назад (отредактировано ) 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?
Devion #26 - 3 года назад (отредактировано ) 0
taraa, вы отправляете на триангуляцию трехмерный объект, который соответственно нельзя представить в плоскости. Как минимум одна неверность уже есть.
Триангуляция это операция совершаемая в плоскости. Точки пространства же порождают непредсказуемо разные фигуры. То есть для обработки трехмерного объекта вам надо поделить модель на соответствующие "плоскости", которые и будете обрабатывать алгоритмом.
А второе это то что вы подаете "фигуру в целом". А надо подавать ее контур. То есть вы просто туда сейчас закидываете набор точек, некоторые из которых там по два три раза фигурируют. Если вы посмотрите комментарии выше, то увидите что триангуляция строилась по "контуру многоугольника", который вы и должны подать в функцию. В результате точки пересекают фигуру несколько раз и все они засчитываются как невалидные.
Например вот такая фигура по ясным причинам не является обычным многоугольником:
|\/|
|/\|
Она пересекает саму себя, если отправленных точек 4 и они идут накрест.
Триангуляция так не работает, ибо ни по одному варианту из трех точек этой фигуры в итоге нельзя построить треугольник, ибо он не принадлежит фигуре и/или пересекает ее грани.
Но если бы точек было 6 и они бы шли по/против часовой, то это бы прокатило.
Конкретно ваш случай - триангуляцию придется запускать 9 раз (для каждой стороны куба) и класть туда по 4 точки и указывая ось. Вообще не вижу смысла в таких вопросах применять триангуляцию, как то не по назначению.
taraa #27 - 3 года назад 0
Extravert, оно конечно хорошо, но мне нужно только одну допустим грань разбить на маленькие кусочки полигонов, то есть допустим даже взять один полигон треугольной формы и раздробить на более мельче, допустим сделать 2 или 4 или 8 маленьких треугольников в одной плоскости. я просидел кучу времени и у меня не проходит проверку : !Intersect(lines, a, b) && !Intersect(lines, b, c) && !Intersect(lines, a, c)
насколько я понял - он ничего не делает поскольку полигон и так прямоугольник.. возможно если добавить точку по середине между действующими точками поможет... но пока не получается.. как быть.?? возможно вообще такое?
Devion #28 - 3 года назад (отредактировано ) 0
taraa, треугольники на более мелкие нужно разбивать другим алгоритмом. Как это сделать проще всего?
Взять ваш треугольник, на самом широком ребре найти середину, разбить. И повторять так с каждой более мелкой фигурой, пока не достигнете необходимой вам глубины деления.
Почему может не пройти проверка? Очень просто. Линии, которые кладутся в алгоритм изначально собираются "подряд". То есть первая точка связана со второй, вторая с третьей и так далее. Когда вы построили куб, то там вероятно был стык, когда две точки имеют одинаковую координату. Таким образом эти точки пересекаются и проверка не идет. В прямоугольнике у вас должно быть 4 точки, чтобы он разбился например на два треугольника. А не 6, как вероятнее всего они описаны в меше.
Я вас уверяю в описанном вам случае вам не нужна триангуляция. Достаточно сделать то что я описал в самом начале.
То есть.
Берете ваши вертексы из меша. Берете трианглес оттуда же, чтобы узнать в каком порядке вертексы располагаются. Согласно этому порядку берете первые три индекса из массива трианглс, далее по этим индексам обращаетесь к вертексам и кладете все в свой массив. И запускаете в алгоритм, который узнает между какими из трех точек наибольшее расстояние. Вычитаете вектора, делите полученный вектор пополам, прибавляете обратно. И вы узнали точку, образующую новые треугольники.
taraa #29 - 3 года назад 0
Extravert, спасибо)) Вы подтвердили мою вчерашнею теорию над которой сидел.. только я когда добавил новую точку дополнительно прогонял через функцию GetResult.. и для чого непонятно... только запутался.
alexprey #30 - 3 года назад 2
Extravert, nvc123, по поводу нашего разговора о стандартном функционале триангуляции средствами OpenGL. Я тут пока делал лабу на компьютерную графику по OpenGL разобрался в чем соль данного параметра. Это не тип рендера, а порядок обхода вершин. То есть указав 4 вершины и указав тип Quadres он просто создаст 2 треугольника, 1-2-3 и 3-4-1
Devion #31 - 2 года назад (отредактировано ) 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;
    }
}