유니티 - 여러 구멍들이 있는 다각형의 삼각분할 (Polygon Triangulation with Holes)

Unity 전체 링크

 

참고

- CreatePrimitive로 기본 오브젝트 만들기

- 오목 다각형의 삼각분할 (Polygon Triangulation)

- 구멍이 있는 다각형의 삼각분할 (Polygon Triangulation with One Hole)

- 여러 구멍들이 있는 다각형의 삼각분할 (Polygon Triangulation with Holes)

 

구멍이 하나만 있는 다각형의 삼각분할을 여러번 사용하면 구멍이 여러 개 있어도 처리가 가능하다.

다각형에 구멍 하나가 있어도 결국 하나의 다각형이기 때문에 여기에 다시 구멍을 뚫으면 된다.

단, 여기서는 구멍이 완전히 다각형 내부에만 존재하고, 구멍끼리는 겹치지 않는다고 가정하자.

---

Settings

 

이전 글을 참고하여 여기서도 Hole을 2개 더 추가한다.

 

아래의 다각형에 3개의 구멍이 있다.

 

PolygonTriangulationWithHoles.cs는 아래와 같이 변경된다.

---

구현

 

hole이 여러 개이므로 아래와 같이 변수들의 타입이 변경된다.

    public GameObject polygon;
    public GameObject[] holes;

    LineRenderer pLine;
    LineRenderer[] hLines;

    List<Vector3> polygonPos = new List<Vector3>(); /* 시계 방향 */
    List<List<Vector3>> holePoses = new List<List<Vector3>>(); /* 반시계 방향 */

    List<Vector3> mergePolygon = new List<Vector3>();
    List<Vector3> mergePolygons = new List<Vector3>();

 

Start도 여러 개의 구멍을 처리하도록 변경하였다.

    void Start()
    {
        mesh = this.GetComponent<MeshFilter>().mesh;

        pLine = polygon.GetComponent<LineRenderer>();

        hLines = new LineRenderer[holes.Length];
        for(int i = 0; i < holes.Length; i++)
            hLines[i] = holes[i].GetComponent<LineRenderer>();

        initLineRenderer(pLine, Color.blue);
        foreach (Transform tr in polygon.transform)
        {
            Vector3 v = tr.transform.position;
            polygonPos.Add(v);
        }

        setLineRenderer(pLine, polygonPos);

        /* ---------------------- */

        for (int i = 0; i < holes.Length; i++)
            initLineRenderer(hLines[i], Color.cyan);

        int index = 0;
        foreach (GameObject hole in holes)
        {
            List<Vector3> tmp = new List<Vector3>();
            foreach (Transform tr in hole.transform)
            {
                Vector3 v = tr.transform.position;
                tmp.Add(v);
            }

            holePoses.Add(tmp);
            setLineRenderer(hLines[index], holePoses[index]);
            index++;
        }

        mergePolygons = polygonPos;
        for (int i = 0; i < holes.Length; i++)
        {
            Vector3[] shortestDots = getShortestDots(mergePolygons, holePoses[i]);

            mergePolygon = makePolygonWithHole(mergePolygons, holePoses[i], shortestDots);
            mergePolygons = mergePolygon;
        }
    }

 

merge를 hole만큼 순서대로 진행하면 된다.

    mergePolygons = polygonPos;
    for (int i = 0; i < holes.Length; i++)
    {
        Vector3[] shortestDots = getShortestDots(mergePolygons, holePoses[i]);

        mergePolygon = makePolygonWithHole(mergePolygons, holePoses[i], shortestDots);
        mergePolygons = mergePolygon;
    }

 

하지만 게임을 실행해보면 정상적으로 삼각분할이 되지 않고 구멍을 교차한다.

---

원인 분석

 

원인을 분석하기 위해 mergePolygons를 CreatePrimitive를 이용하여 순서대로 출력해보자.

    mergePolygons = polygonPos;
    for (int i = 0; i < holes.Length; i++)
    {
        Vector3[] shortestDots = getShortestDots(mergePolygons, holePoses[i]);

        dupCheck[shortestDots[0]] = true;
        dupCheck[shortestDots[1]] = true;

        mergePolygon = makePolygonWithHole(mergePolygons, holePoses[i], shortestDots);
        mergePolygons = mergePolygon;

        { // 가장 짧은 점 표시하기
            GameObject temp;
            temp = GameObject.CreatePrimitive(PrimitiveType.Sphere);
            temp.transform.position = shortestDots[0];
            temp.transform.localScale = new Vector3(1.1f, 1.1f, 1.1f);

            temp = GameObject.CreatePrimitive(PrimitiveType.Sphere);
            temp.transform.position = shortestDots[1];
            temp.transform.localScale = new Vector3(1.1f, 1.1f, 1.1f);
        }
    }

    foreach (Vector3 m in mergePolygons)
    {
        GameObject go = GameObject.CreatePrimitive(PrimitiveType.Cube);
        go.transform.localScale = new Vector3(1.5f, 1.5f, 1.5f);
        go.transform.position = m;
    }

    LineRenderer mergeLine = this.GetComponent<LineRenderer>();
    initLineRenderer(mergeLine, Color.green, 0.5f);
    setLineRenderer(mergeLine, mergePolygons);

 

아래의 점 순서대로 만들어져있는데, 자세히보면 다각형이 꼬여있다.

 

순서대로 보면 다음과 같다.

빨간 화살표와 파란 화살표가 교차하는 것을 알 수 있다.

 

알고리즘이 정상 동작하려면 아래와 같은 순서로 생성되었어야 한다.

 

문제의 원인은 구멍과 다각형의 가까운 점을 찾을 때, 중복되는 점이 생기기 때문이다.

 

아래 코드에서 위의 화살표의 순서를 보장하지 않기 때문에 문제가 발생한다.

    List<Vector3> sortListbyStartPoint(List<Vector3> list, Vector3 startPos)
    {
		...
        for (start = 0; start < list.Count; start++)
            if (list[start] == startPos) break; <<< ERROR!

        for (int i = start; i < start + count; i++) sort.Add(doubleList[i]);

        return sort;
    }

---

보완

 

사용된 좌표는 중복 선택될 수 없도록 관리하면 모든 것이 해결된다.

즉, 다음으로 짧은 거리의 점을 선택하면 된다.

 

중복 체크를 위해 Dictionary를 선언하자.

Dictionary<Vector3, bool> dupCheck = new Dictionary<Vector3, bool>();

 

그리고 가장 길이가 짧은 두 점을 구한 후 dupCheck에 표시한다.

    mergePolygons = polygonPos;
    for (int i = 0; i < holes.Length; i++)
    {
        Vector3[] shortestDots = getShortestDots(mergePolygons, holePoses[i]);

        dupCheck[shortestDots[0]] = true;
        dupCheck[shortestDots[1]] = true;

        mergePolygon = makePolygonWithHole(mergePolygons, holePoses[i], shortestDots);
        mergePolygons = mergePolygon;

 

getShortestDots에서 ContainsKey를 이용해 중복되는 좌표는 최소거리 계산 때 제외하면 된다.

    Vector3[] getShortestDots(List<Vector3> a, List<Vector3> b)
    {
        float minValue = float.MaxValue;
        Vector3 dot1, dot2;

        dot1 = dot2 = Vector3.zero;
        foreach (Vector3 v1 in a)
        {
            foreach (Vector3 v2 in b)
            {
                if (dupCheck.ContainsKey(v1) == true
                    || dupCheck.ContainsKey(v2) == true) continue;

                float distance = Vector3.Distance(v1, v2);
                if (distance < minValue)
                {
                    minValue = distance;
                    dot1 = v1;
                    dot2 = v2;
                }
            }
        }

        return new Vector3[] { dot1, dot2 };
    }

 

다시 디버깅해보면 알맞은 순서대로 mergePolygons가 생성되었다.

 

이제 디버깅 코드를 지우고 삼각분할을 해보자.

 

총 30개의 삼각형(11 + 6 + 2 + 5 + 2 + 4 + 2 - 2)으로 분할되는 것을 확인할 수 있다.

 

전체 코드는 다음과 같다.

using System.Collections;
using System.Collections.Generic;
using UnityEngine;

[RequireComponent(typeof(MeshRenderer), typeof(MeshFilter))]
public class PolygonTriangulationWithHoles : MonoBehaviour
{
    public GameObject polygon;
    public GameObject[] holes;

    LineRenderer pLine;
    LineRenderer[] hLines;

    List<Vector3> polygonPos = new List<Vector3>(); /* 시계 방향 */
    List<List<Vector3>> holePoses = new List<List<Vector3>>(); /* 반시계 방향 */

    List<Vector3> mergePolygon = new List<Vector3>();
    List<Vector3> mergePolygons = new List<Vector3>();

    Dictionary<Vector3, bool> dupCheck = new Dictionary<Vector3, bool>();

    #region Polygon Triangulation
    public int numOfTriangle;
    List<Vector3> dotList = new List<Vector3>();

    Mesh mesh;
    List<Vector3> vertices = new List<Vector3>();
    List<int> triangles = new List<int>();
    Dictionary<Vector3, int> dic = new Dictionary<Vector3, int>();

    LineRenderer[] lineForTriangles;

    float CCWby2D(Vector3 a, Vector3 b, Vector3 c)
    {
        Vector3 p = b - a;
        Vector3 q = c - b;

        return Vector3.Cross(p, q).y;
    }

    void makeTriangle(LineRenderer lr, Vector3 a, Vector3 b, Vector3 c)
    {
        lr.startWidth = lr.endWidth = 0.2f;
        lr.material.color = Color.red;

        lr.positionCount = 3;

        lr.SetPosition(0, a);
        lr.SetPosition(1, b);
        lr.SetPosition(2, c);

        lr.loop = true;
    }

    float getAreaOfTriangle(Vector3 dot1, Vector3 dot2, Vector3 dot3)
    {
        Vector3 a = dot2 - dot1;
        Vector3 b = dot3 - dot1;
        Vector3 cross = Vector3.Cross(a, b);

        return cross.magnitude / 2.0f;
    }

    bool checkTriangleInPoint(Vector3 dot1, Vector3 dot2, Vector3 dot3, Vector3 checkPoint)
    {
        if (dot1 == checkPoint) return false;
        if (dot2 == checkPoint) return false;
        if (dot3 == checkPoint) return false;

        float area = getAreaOfTriangle(dot1, dot2, dot3);
        float dot12 = getAreaOfTriangle(dot1, dot2, checkPoint);
        float dot23 = getAreaOfTriangle(dot2, dot3, checkPoint);
        float dot31 = getAreaOfTriangle(dot3, dot1, checkPoint);

        return (dot12 + dot23 + dot31) <= area + 0.1f /* 오차 허용 */;
    }

    bool CrossCheckAll(List<Vector3> list, int index)
    {
        Vector3 a = list[index];
        Vector3 b = list[index + 1];
        Vector3 c = list[index + 2];

        for (int i = index + 3; i < list.Count; i++)
        {
            if (checkTriangleInPoint(a, b, c, list[i]) == true) return true;
        }

        return false;
    }

    void triangluation(int count)
    {
        vertices.Clear();
        triangles.Clear();
        dic.Clear();

        dotList.Clear();
        foreach (Vector3 v in mergePolygons) // init
            dotList.Add(v);

        lineForTriangles = this.GetComponentsInChildren<LineRenderer>();

        for (int i = 0; i < lineForTriangles.Length; i++) // init
            lineForTriangles[i].positionCount = 0;

        //int numOfTriangle = dotList.Count - 2;
        if (count > dotList.Count - 2) count = dotList.Count - 2;

        for (int i = 0; i < count; i++)
        {
            List<Vector3> copy = new List<Vector3>(dotList);

            for (int k = 0; k < copy.Count - 2; k++)
            {
                bool ccw = (CCWby2D(copy[k], copy[k + 1], copy[k + 2]) > 0);
                bool cross = CrossCheckAll(copy, k);

                if (ccw == true && cross == false)
                {
                    makeTriangle(lineForTriangles[i], copy[k], copy[k + 1], copy[k + 2]);

                    for (int c = 0; c < 3; c++)
                    {
                        if (dic.ContainsKey(copy[k + c])) continue;

                        dic[copy[k + c]] = vertices.Count;
                        vertices.Add(copy[k + c]);
                    }

                    for (int c = 0; c < 3; c++)
                        triangles.Add(dic[copy[k + c]]);

                    copy.RemoveAt(k + 1);
                    dotList = new List<Vector3>(copy);

                    break;
                }
            }
        }
    }
    #endregion
    void initLineRenderer(LineRenderer lr, Color color, float length = 0.1f)
    {
        lr.startWidth = lr.endWidth = length;
        lr.material.color = color;
        lr.loop = true;
    }

    void setLineRenderer(LineRenderer lr, List<Vector3> pos)
    {
        lr.positionCount = pos.Count;

        for (int i = 0; i < pos.Count; i++)
            lr.SetPosition(i, pos[i]);
    }

    Vector3[] getShortestDots(List<Vector3> a, List<Vector3> b)
    {
        float minValue = float.MaxValue;
        Vector3 dot1, dot2;

        dot1 = dot2 = Vector3.zero;
        foreach (Vector3 v1 in a)
        {
            foreach (Vector3 v2 in b)
            {
                if (dupCheck.ContainsKey(v1) == true
                    || dupCheck.ContainsKey(v2) == true) continue;

                float distance = Vector3.Distance(v1, v2);
                if (distance < minValue)
                {
                    minValue = distance;
                    dot1 = v1;
                    dot2 = v2;
                }
            }
        }

        return new Vector3[] { dot1, dot2 };
    }

    List<Vector3> sortListbyStartPoint(List<Vector3> list, Vector3 startPos)
    {
        List<Vector3> sort = new List<Vector3>();
        List<Vector3> doubleList = new List<Vector3>();
        int count = list.Count;

        foreach (Vector3 v in list) doubleList.Add(v);
        foreach (Vector3 v in list) doubleList.Add(v);

        int start;
        for (start = 0; start < list.Count; start++)
            if (list[start] == startPos) break;

        for (int i = start; i < start + count; i++) sort.Add(doubleList[i]);

        return sort;
    }

    List<Vector3> makePolygonWithHole(List<Vector3> polygonPos, List<Vector3> holePos, Vector3[] shortestDots)
    {
        List<Vector3> sortPolygon = sortListbyStartPoint(polygonPos, shortestDots[0]);
        List<Vector3> sortHole = sortListbyStartPoint(holePos, shortestDots[1]);
        List<Vector3> merge = new List<Vector3>();

        foreach (Vector3 v in sortPolygon) merge.Add(v);
        merge.Add(sortPolygon[0]);

        foreach (Vector3 v in sortHole) merge.Add(v);
        merge.Add(sortHole[0]);

        return merge;
    }

    void OnValidate()
    {
        if (numOfTriangle > 0)
        {
            triangluation(numOfTriangle);
            //createProceduralMesh();
        }
    }

    void Start()
    {
        mesh = this.GetComponent<MeshFilter>().mesh;

        pLine = polygon.GetComponent<LineRenderer>();

        hLines = new LineRenderer[holes.Length];
        for(int i = 0; i < holes.Length; i++)
            hLines[i] = holes[i].GetComponent<LineRenderer>();

        initLineRenderer(pLine, Color.blue);
        foreach (Transform tr in polygon.transform)
        {
            Vector3 v = tr.transform.position;
            polygonPos.Add(v);
        }

        setLineRenderer(pLine, polygonPos);

        /* ---------------------- */

        for (int i = 0; i < holes.Length; i++)
            initLineRenderer(hLines[i], Color.cyan);

        int index = 0;
        foreach (GameObject hole in holes)
        {
            List<Vector3> tmp = new List<Vector3>();
            foreach (Transform tr in hole.transform)
            {
                Vector3 v = tr.transform.position;
                tmp.Add(v);
            }

            holePoses.Add(tmp);
            setLineRenderer(hLines[index], holePoses[index]);
            index++;
        }

        mergePolygons = polygonPos;
        for (int i = 0; i < holes.Length; i++)
        {
            Vector3[] shortestDots = getShortestDots(mergePolygons, holePoses[i]);

            dupCheck[shortestDots[0]] = true;
            dupCheck[shortestDots[1]] = true;

            mergePolygon = makePolygonWithHole(mergePolygons, holePoses[i], shortestDots);
            mergePolygons = mergePolygon;

            //{ // 가장 짧은 점 표시하기
            //    GameObject temp;
            //    temp = GameObject.CreatePrimitive(PrimitiveType.Sphere);
            //    temp.transform.position = shortestDots[0];
            //    temp.transform.localScale = new Vector3(1.1f, 1.1f, 1.1f);

            //    temp = GameObject.CreatePrimitive(PrimitiveType.Sphere);
            //    temp.transform.position = shortestDots[1];
            //    temp.transform.localScale = new Vector3(1.1f, 1.1f, 1.1f);
            //}
        }

        //foreach (Vector3 m in mergePolygons)
        //{
        //    GameObject go = GameObject.CreatePrimitive(PrimitiveType.Cube);
        //    go.transform.localScale = new Vector3(1.5f, 1.5f, 1.5f);
        //    go.transform.position = m;
        //}

        //LineRenderer mergeLine = this.GetComponent<LineRenderer>();
        //initLineRenderer(mergeLine, Color.green, 0.5f);
        //setLineRenderer(mergeLine, mergePolygons);
    }
}

 

위의 실행결과는 아래의 unitypackage에서 확인 가능하다.

PolygonTriangulationWithHoles.unitypackage

0.03MB

 

Unity Plus:

Easy 2D, 3D, VR, & AR software for cross-platform development of games and mobile apps. - Unity Store

 

Unity Pro:

Unity Pro

 

Unity 프리미엄 학습:

Unity Learn