참고
- 오목 다각형의 삼각분할 (Polygon Triangulation)
- 구멍이 있는 다각형의 삼각분할 (Polygon Triangulation with One Hole)
- 여러 구멍들이 있는 다각형의 삼각분할 (Polygon Triangulation with Holes)
출처 - https://alienryderflex.com/polygon_triangulation_with_hole.shtml
위 링크를 바탕으로 유니티에서 구현하였습니다.
다각형의 삼각분할
점이 N개인 다각형이라면 N - 2개의 삼각형으로 나눌 수 있다.
아래 그림의 별처럼 꼭 N - 2개의 삼각형으로 나뉘지 않을 수 있지만,
일반적인 모든 다각형에서 삼각분할을 하면 오른쪽의 그림대로 삼각형을 나눌 수 있다.
볼록 다각형의 경우 삼각분할은 간단하다.
점 하나를 기준으로 잡고 순서대로 삼각형을 만드는 점을 찾아가면 된다.
하지만 오목 다각형의 경우, 점 하나를 기준으로 잡고 순서대로 삼각분할하면 외부에 삼각형이 만들어질 수 있다.
오목 다각형 삼각분할 알고리즘
먼저 점 하나를 선택하고 내부에 삼각형이 만들어지는지 확인한다.
이때 방향은 상관없으므로, 여기서는 시계 방향으로 점을 찾는다.
첫번째 점을 기준으로 다음 2개의 점은 외부에 삼각형을 만들기 때문에 다음 점으로 넘어간다.
외부에 삼각형을 만드는 것은 CCW 알고리즘으로 판단할 수 있다.
다음 점도 교차하는 선분이 생기기 때문에 삼각형을 만들 수 없다.
그 다음 점은 아래와 같이 내부에 삼각형을 만든다.
삼각형이 만들어진다면 3개의 점 중 가운데 점을 빼고 다시 처음부터 시작한다.
여기서 다시 처음이란, "최초로 시작했던 점"을 기준으로 다시 실행한다는 뜻이다.
정리하자면, 아래의 순서대로 실행하면 다각형을 분할할 수 있다.
1) 다각형을 만드는 점을 시계방향 순서대로 탐색한다.
2) 첫번째 점을 기준으로 다음 두 점과 함께 세 점이 삼각형을 만드는지 판단한다.
- 외부인지 내부인지는 CCW 알고리즘으로 판단한다.
- 선택된 점 외에 모든 직선과 선분이 교차하는지 검사한다.
3) 삼각형이 만들어진다면 후보에서 제외하고, 그렇지 않다면 다음 점으로 넘어간다.
구현
먼저 Sphere를 배치해서 다각형을 만들고 라인 렌더러로 다각형을 그려보자.
using System.Collections;
using System.Collections.Generic;
using UnityEngine;
public class PolygonTriangulation : MonoBehaviour
{
public GameObject[] goArray;
List<Vector3> dotList = new List<Vector3>();
LineRenderer lr;
void Start()
{
foreach (GameObject go in goArray)
dotList.Add(go.transform.position);
lr = this.GetComponent<LineRenderer>();
lr.startWidth = lr.endWidth = 1.0f;
lr.material.color = Color.blue;
lr.positionCount = dotList.Count;
for (int i = 0; i < dotList.Count; i++)
lr.SetPosition(i, dotList[i]);
lr.loop = true;
}
}
빈 오브젝트를 만들고 라인 렌더러를 추가한 후, Sphere를 할당하였다.
게임을 실행해서 적절히 오브젝트가 다각형을 잘 만드는지 확인하자.
참고로 모든 Sphere의 y 값은 0이다.
위의 다각형의 각 점의 좌표는 아래와 같이 시계 방향으로 만들었다.
(0, 0, 0) → (-50, 0, -30) → (-100, 0, 10) → (-30, 0, 25) → (-100, 0, 100)
→ (-50, 0, 150) → (10, 0, 170) → (60, 0, 120) → (40, 0, 80) → (-20, 0, 70)
이제 삼각형을 그릴 라인 렌더러를 자식 오브젝트로 추가한다.
10개의 점이므로 최소 8개의 라인 렌더러가 필요하다.
그리고 GetComponentsInChildren로 자식의 모든 라인 렌더러를 가져온다.
참고로 GetComponentsInChildren는 부모의 오브젝트도 가져오기 때문에 triangles[1]부터 삼각형을 그린다.
LineRenderer[] triangles;
void Start()
{
...
triangles = this.GetComponentsInChildren<LineRenderer>();
}
}
위에 설명한 삼각분할 알고리즘을 그대로 구현하면 아래와 같다.
List에 순서대로 점을 담아서 3개씩 검사하고, 삼각형이 만들어지면 RemoveAt으로 제거한다.
int numOfTriangle = dotList.Count - 2;
for (int i = 0; i < numOfTriangle; 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)
{
/* triangle[0]은 부모의 LineRenderer */
makeTriangle(triangles[i + 1], copy[k], copy[k + 1], copy[k + 2]);
copy.RemoveAt(k + 1);
dotList = new List<Vector3>(copy);
break;
}
}
}
CCW는 아래와 같이 구현한다.
float CCWby2D(Vector3 a, Vector3 b, Vector3 c)
{
Vector3 p = b - a;
Vector3 q = c - b;
return Vector3.Cross(p, q).y;
}
점을 시계 방향으로 검사하는 경우에 왼쪽의 세 개의 점은 반시계 방향이므로 외부에 삼각형을 만든다.
오른쪽 그림의 세 개의 점은 시계 방향이므로 삼각형을 만들 수 있다.
CCWby2D는 시계 방향인 경우 양수를 리턴한다.
그리고 선택된 점 3개 중 첫번째와 세번째 점을 잇는 직선이 나머지 모든 직선과 교차하지 않아야 삼각형을 만들 수 있다.
예를 들면 아래의 1번 점과 3번 점이 남은 다른 직선과 교점을 만들기 때문에 삼각형을 생성할 수 없다.
CrossCheck2D는 2차원 평면에서 유한한 선의 교점을 구할 수 있는지 판단하는 것과 같다.
bool CheckDotInLine(Vector3 a, Vector3 b, Vector3 dot)
{
float epsilon = 0.00001f;
float dAB = Vector3.Distance(a, b);
float dADot = Vector3.Distance(a, dot);
float dBDot = Vector3.Distance(b, dot);
return ((dAB + epsilon) >= (dADot + dBDot));
}
bool CrossCheck2D(Vector3 a, Vector3 b, Vector3 c, Vector3 d)
{
// (x, 0, z)
float x1, x2, x3, x4, z1, z2, z3, z4, X, Z;
x1 = a.x; z1 = a.z;
x2 = b.x; z2 = b.z;
x3 = c.x; z3 = c.z;
x4 = d.x; z4 = d.z;
float cross = ((x1 - x2) * (z3 - z4) - (z1 - z2) * (x3 - x4));
if (cross == 0 /* parallel */) return false;
X = ((x1 * z2 - z1 * x2) * (x3 - x4) - (x1 - x2) * (x3 * z4 - z3 * x4)) / cross;
Z = ((x1 * z2 - z1 * x2) * (z3 - z4) - (z1 - z2) * (x3 * z4 - z3 * x4)) / cross;
return
CheckDotInLine(a, b, new Vector3(X, 0, Z))
&& CheckDotInLine(c, d, new Vector3(X, 0, Z));
}
마지막으로 아래의 함수를 이용해 삼각형을 라인 렌더러로 그린다.
void makeTriangle(LineRenderer lr, Vector3 a, Vector3 b, Vector3 c)
{
lr.startWidth = lr.endWidth = 1.0f;
lr.material.color = Color.red;
lr.positionCount = 3;
lr.SetPosition(0, a);
lr.SetPosition(1, b);
lr.SetPosition(2, c);
lr.loop = true;
}알고리즘 수정
게임을 실행하면 삼각 분할이 제대로 실행되지 않는다.
삼각분할을 차례대로 하다가 마지막 점 4개를 분할할 때를 보자. (빨간 공 4개)
현재 이 경우에 알고리즘을 적용하면 1 → 2 → 3번의 점은 시계 방향이다.
그런데 현재 CrossCheckAll은 4번의 점과 연결될 점이 없어 교점이 없다고 판단한다.
따라서 직선이 서로 교차하는지 체크하지말고, 선택된 점 3개가 만든 삼각형 내부에 점이 있냐를 체크하면 된다.
bool checkTriangleInPoint(Vector3 dot1, Vector3 dot2, Vector3 dot3, Vector3 checkPoint)
{
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;
}
이제 게임을 실행하면 정상적으로 삼각분할이 완성된다.
최종 코드는 다음과 같다.
using System.Collections;
using System.Collections.Generic;
using UnityEngine;
public class PolygonTriangulation : MonoBehaviour
{
public GameObject[] goArray;
List<Vector3> dotList = new List<Vector3>();
LineRenderer lr;
LineRenderer[] triangles;
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 = 1.0f;
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 Start()
{
foreach (GameObject go in goArray)
dotList.Add(go.transform.position);
lr = this.GetComponent<LineRenderer>();
lr.startWidth = lr.endWidth = 1.0f;
lr.material.color = Color.blue;
lr.positionCount = dotList.Count;
for (int i = 0; i < dotList.Count; i++)
lr.SetPosition(i, dotList[i]);
lr.loop = true;
triangles = this.GetComponentsInChildren<LineRenderer>();
int numOfTriangle = dotList.Count - 2;
for (int i = 0; i < numOfTriangle; 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)
{
/* triangle[0]은 부모의 LineRenderer */
makeTriangle(triangles[i + 1], copy[k], copy[k + 1], copy[k + 2]);
copy.RemoveAt(k + 1);
dotList = new List<Vector3>(copy);
break;
}
}
}
}
}
위의 실행결과는 아래의 unitypackage에서 확인 가능하다.
삼각분할 순서대로 확인하기
위의 결과는 최종 결과만 볼 수 있으므로, 하나씩 순서대로 삼각형이 만들어지는 과정을 확인해보자.
Start에서 삼각분할 알고리즘을 아래의 함수로 분리한다.
그리고 매번 새로 그리기 위해 dotList를 초기화하고 triangles 라인 렌더러의 positionCount를 초기화한다.
void triangluation(int count)
{
dotList.Clear();
foreach (GameObject go in goArray) // init
dotList.Add(go.transform.position);
triangles = this.GetComponentsInChildren<LineRenderer>();
for (int i = 1; i < triangles.Length; i++) // init
triangles[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)
{
/* triangle[0]은 부모의 LineRenderer */
makeTriangle(triangles[i + 1], copy[k], copy[k + 1], copy[k + 2]);
copy.RemoveAt(k + 1);
dotList = new List<Vector3>(copy);
break;
}
}
}
}
numOfTriangle을 public 변수로 할당한 후,
OnValidate를 이용하여 public 변수를 변경할 때 N번째로 만들어진 결과를 보도록 하자.
public int numOfTriangle;
void triangluation(int count)
{ ... }
void OnValidate()
{
if(numOfTriangle > 0)
{
triangluation(numOfTriangle);
}
}
게임을 실행하고 인스펙터에서 numOfTriangle을 변경해보자.
최종 코드는 아래와 같다.
using System.Collections;
using System.Collections.Generic;
using UnityEngine;
public class PolygonTriangulation : MonoBehaviour
{
public int numOfTriangle;
public GameObject[] goArray;
List<Vector3> dotList = new List<Vector3>();
LineRenderer lr;
LineRenderer[] triangles;
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 = 1.0f;
lr.material.color = Color.red;
lr.positionCount = 3;
lr.SetPosition(0, a);
lr.SetPosition(1, b);
lr.SetPosition(2, c);
lr.loop = true;
}
bool CheckDotInLine(Vector3 a, Vector3 b, Vector3 dot)
{
float epsilon = 0.00001f;
float dAB = Vector3.Distance(a, b);
float dADot = Vector3.Distance(a, dot);
float dBDot = Vector3.Distance(b, dot);
return ((dAB + epsilon) >= (dADot + dBDot));
}
bool CrossCheck2D(Vector3 a, Vector3 b, Vector3 c, Vector3 d)
{
// (x, 0, z)
float x1, x2, x3, x4, z1, z2, z3, z4, X, Z;
x1 = a.x; z1 = a.z;
x2 = b.x; z2 = b.z;
x3 = c.x; z3 = c.z;
x4 = d.x; z4 = d.z;
float cross = ((x1 - x2) * (z3 - z4) - (z1 - z2) * (x3 - x4));
if (cross == 0 /* parallel */) return false;
X = ((x1 * z2 - z1 * x2) * (x3 - x4) - (x1 - x2) * (x3 * z4 - z3 * x4)) / cross;
Z = ((x1 * z2 - z1 * x2) * (z3 - z4) - (z1 - z2) * (x3 * z4 - z3 * x4)) / cross;
return
CheckDotInLine(a, b, new Vector3(X, 0, Z))
&& CheckDotInLine(c, d, new Vector3(X, 0, Z));
}
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)
{
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 + 2];
// 마지막 삼각형은 삼각형 내부의 점으로 판단
if (list.Count == 4 && index == 0)
{
Vector3 c = list[index + 1];
Vector3 d = list[index + 3];
return checkTriangleInPoint(a, b, c, d);
}
for (int i = index + 3; i < list.Count - 1; i++)
{
Vector3 c = list[i];
Vector3 d = list[i + 1];
bool check = CrossCheck2D(a, b, c, d);
if (check == true) return true;
}
return false;
}
void triangluation(int count)
{
dotList.Clear();
foreach (GameObject go in goArray) // init
dotList.Add(go.transform.position);
triangles = this.GetComponentsInChildren<LineRenderer>();
for (int i = 1; i < triangles.Length; i++) // init
triangles[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)
{
/* triangle[0]은 부모의 LineRenderer */
makeTriangle(triangles[i + 1], copy[k], copy[k + 1], copy[k + 2]);
copy.RemoveAt(k + 1);
dotList = new List<Vector3>(copy);
break;
}
}
}
}
void OnValidate()
{
if(numOfTriangle > 0)
{
triangluation(numOfTriangle);
}
}
void Start()
{
foreach (GameObject go in goArray)
dotList.Add(go.transform.position);
lr = this.GetComponent<LineRenderer>();
lr.startWidth = lr.endWidth = 1.0f;
lr.material.color = Color.blue;
lr.positionCount = dotList.Count;
for (int i = 0; i < dotList.Count; i++)
lr.SetPosition(i, dotList[i]);
lr.loop = true;
}
}
위의 실행결과는 아래의 unitypackage에서 확인 가능하다.
Unity Plus:
Easy 2D, 3D, VR, & AR software for cross-platform development of games and mobile apps. - Unity Store
Have a 2D, 3D, VR, or AR project that needs cross-platform functionality? We can help. Take a look at the easy-to-use Unity Plus real-time dev platform!
store.unity.com
Unity Pro:
Unity Pro
The complete solutions for professionals to create and operate.
unity.com
Unity 프리미엄 학습:
Unity Learn
Advance your Unity skills with live sessions and over 750 hours of on-demand learning content designed for creators at every skill level.
unity.com
댓글