반응형
참고
- CreatePrimitive로 기본 오브젝트 만들기
- 오목 다각형의 삼각분할 (Polygon Triangulation)
- 구멍이 있는 다각형의 삼각분할 (Polygon Triangulation with One Hole)
- 여러 구멍들이 있는 다각형의 삼각분할 (Polygon Triangulation with Holes)
(오목) 다각형의 삼각분할은 구멍이 없는 경우에 다각형을 삼각형으로 분할하였다.
하지만 오목 다각형 삼각분할 알고리즘을 잘 보완해서 적용하면 구멍이 있더라도 삼각분할이 가능하다.
오목 다각형 삼각분할 알고리즘 with Hole
아래와 같이 점 0, 1, 2, 3으로 주어진 사각형 내부에 점 4, 5, 6으로 주어진 삼각형 구멍이 있다고 하자.
여기서 삼각형을 만드는 점 하나와 사각형의 점 하나 중 가장 가까운 점 두 개를 찾아 연결한다.
만약 3번과 6번 점을 잡으면 원래의 도형을 교차하기 때문에 가까운 점을 잡는다.
그러면 위의 도형은 더 이상 구멍이 있는 다각형이 아니라 점 0, 1, 2, 3, 0, 5, 4, 6, 5로만든 오목 다각형이 된다.
(삼각형의 점의 순서가 반시계 방향으로 변경된다.)
중복되는 점이 생겼지만 오목 다각형 삼각분할 알고리즘은 점의 순서만 잘 지키면 잘 동작한다.
즉, 중복되는 점은 사실 매우 매우 가까이 있는 점이라고 보면 된다.
따라서 알고리즘을 요약하면 다음과 같다.
- 두 도형 중 가장 가까운 점 2개를 이어서 오목 다각형을 만든다.
- 중복된 점을 포함하여 점의 집합을 갱신한다.
ㄴ 이때, 구멍을 만드는 좌표를 시계 방향에서 반시계 방향으로 정렬한다.
ㄴ 이 글의 경우 구멍 좌표는 미리 반시계로 주어진다.
- 오목 다각형의 삼각분할 알고리즘을 적용한다.
참고로 다각형의 모서리가 N개라면 N - 2개의 삼각형이 만들어지는데,
poylgon + hole은 중복된 점 2개가 추가 되므로 N - 2 + 2 = N 개의 삼각형이 만들어진다.
Settings
임의의 다각형을 만들고 내부에 구멍을 추가하자. (모든 Sphere의 y 좌표는 0이다.)
Poylgon이라는 빈 오브젝트를 만들고 자식으로 Sphere를 추가하고, Polygon에는 LineRenderer를 하나 추가한다.
Sphere만 보면 아래와 같으며, 좌표는 시계 방향이다.
Hole도 Polygon과 마찬가지로 빈 오브젝트에 자식으로 Sphere를 추가하고 LineRenderer를 하나 추가한다.
이때 오브젝트의 좌표가 반시계 방향이 되도록 넣는다.
Hole만 보면 아래와 같으며, 반시계 방향으로 배치 되어야 한다는 것에 주의하자.
PolygonTriangulationWithHole.cs를 빈 오브젝트에 추가하고 아래와 같이 설정한다.
(Mesh Render, Default-Materials, Mesh Filter 추가)
또한 빈 오브젝트의 자식으로 LineRenderer를 적절히 추가한다.
오목 다각형 삼각분할에서 사용한 알고리즘은 아래와 같이 #region으로 분리하였다.
(triangles와 vertices는 절차적 메시를 만들 때 사용하며, 따로 지우지 않는다.)
#region Polygon Triangulation
public int numOfTriangle;
List<Vector3> dotList = new List<Vector3>();
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.1f;
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)
{
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 mergePolygon) // 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구현
PolygonTriangulationWithHole.cs를 구현해보자.
polygon과 hole을 받을 오브젝트와 라인렌더러들을 선언한다.
public GameObject polygon, hole;
LineRenderer pLine, hLine;
List<Vector3> polygonPos = new List<Vector3>(); /* 시계 방향 */
List<Vector3> holePos = new List<Vector3>(); /* 반시계 방향 */
List<Vector3> mergePolygon = new List<Vector3>();
Start는 아래와 같이 구현된다.
void initLineRenderer(LineRenderer lr, Color color)
{
lr.startWidth = lr.endWidth = .1f;
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]);
}
void Start()
{
pLine = polygon.GetComponent<LineRenderer>();
hLine = hole.GetComponent<LineRenderer>();
initLineRenderer(pLine, Color.blue);
initLineRenderer(hLine, Color.cyan);
foreach (Transform tr in polygon.transform)
{
Vector3 v = tr.transform.position;
polygonPos.Add(v);
}
foreach (Transform tr in hole.transform)
{
Vector3 v = tr.transform.position;
holePos.Add(v);
}
setLineRenderer(pLine, polygonPos);
setLineRenderer(hLine, holePos);
Vector3[] shortestDots = getShortestDots(polygonPos, holePos);
{ // 가장 짧은 점 표시하기
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);
}
mergePolygon = makePolygonWithHole(polygonPos, holePos, shortestDots);
}
getShortestDots는 두 점의 집합을 비교해서 가장 짧은 길이를 만드는 점 2개를 return한다.
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)
{
float distance = Vector3.Distance(v1, v2);
if(distance < minValue)
{
minValue = distance;
dot1 = v1;
dot2 = v2;
}
}
}
return new Vector3[] { dot1, dot2 };
}
찾은 두 점을 CreatePrimitive로 점을 표시한다.
{ // 가장 짧은 점 표시하기
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);
}
아래와 같이 Polygon의 점과 Hole의 점 중 가장 가까운 점을 표시하였다.
makePolygonWithHole에 이 점을 넘겨주면 새롭게 만들어진 오목 다각형의 좌표를 return한다.
가장 가까운 점 shortestDots은 중복으로 들어간다.
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;
}
sortListbyStartPoint는 시계 방향으로 정리된 점의 좌표 리스트를 shortestDots으로 시작하도록 만든다.
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;
}하얀색으로 표시한 곳(거리가 가장 짧은 두 점)부터 오목 다각형의 좌표를 정렬해두는 것이 쉽기 때문이다.
이제 게임을 실행해서 삼각분할 과정을 보자.
void OnValidate()
{
if (numOfTriangle > 0)
{
triangluation(numOfTriangle);
}
}
삼각분할이 되다가 구멍 주변에서 잘 되지 않는다.
원인은 checkTriangleInPoint에서 삼각형 내에 점이 포함된 경우를 true로 처리하기 때문이다.
따라서 아래와 같이 방어코드를 추가한다.
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 /* 오차 허용 */;
}
이제 정상적으로 구멍이 있는 다각형도 삼각분할이 되는 것을 알 수 있다.
삼각형이 17개(11 + 6 - 2 + 2)로 분할되었다.
전체 코드는 다음과 같다.
using System.Collections;
using System.Collections.Generic;
using UnityEngine;
[RequireComponent(typeof(MeshRenderer), typeof(MeshFilter))]
public class PolygonTriangulationWithHole : MonoBehaviour
{
public GameObject polygon, hole;
LineRenderer pLine, hLine;
List<Vector3> polygonPos = new List<Vector3>(); /* 시계 방향 */
List<Vector3> holePos = new List<Vector3>(); /* 반시계 방향 */
List<Vector3> mergePolygon = new List<Vector3>();
#region Polygon Triangulation
public int numOfTriangle;
List<Vector3> dotList = new List<Vector3>();
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.1f;
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 mergePolygon) // 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)
{
lr.startWidth = lr.endWidth = .1f;
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)
{
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);
}
}
void Start()
{
pLine = polygon.GetComponent<LineRenderer>();
hLine = hole.GetComponent<LineRenderer>();
initLineRenderer(pLine, Color.blue);
initLineRenderer(hLine, Color.cyan);
foreach (Transform tr in polygon.transform)
{
Vector3 v = tr.transform.position;
polygonPos.Add(v);
}
foreach (Transform tr in hole.transform)
{
Vector3 v = tr.transform.position;
holePos.Add(v);
}
setLineRenderer(pLine, polygonPos);
setLineRenderer(hLine, holePos);
Vector3[] shortestDots = getShortestDots(polygonPos, holePos);
{ // 가장 짧은 점 표시하기
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);
}
mergePolygon = makePolygonWithHole(polygonPos, holePos, shortestDots);
}
}
위의 실행결과는 아래의 unitypackage에서 확인 가능하다.
PolygonTriangulationWithHoles.unitypackage
0.03MB
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
반응형
댓글