언리얼, 유니티 같은 유명한 게임엔진에 이미 navmesh가 구현되어있는 걸 굳이 재발명하는 이유는
Bad North를 만든 인디게임 개발자가 커스텀 nav-mesh 만드는데 재밌었다고 한다
내가 만들 게임에 매우 중요해보였고
또 유니티 엔진의 도움 받기 싫고 믿을수도 없어 나도 배워보기로 결정했다
아래 링크 포스트 참고
habrador
들어가기 앞서, 메쉬부터 알아봐야한다
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
static Mesh Triangle2Mesh(HashSet<Triangle> triangles)
{
if (triangles == null)
{
return null;
}
Vector3[] triVertices = new Vector3[triangles.Count * 3];
int[] triOrder = new int[triangles.Count * 3];
int i = 0;
foreach (var tri in triangles)
{
int triIndex = i * 3;
int i1 = triIndex;
int i2 = triIndex + 1;
int i3 = triIndex + 2;
// Debug.Log($"v1 : {tri.v1} , v2 : {tri.v2} , v3 : {tri.v3}");
triVertices[i1] = tri.v1;
triVertices[i2] = tri.v2;
triVertices[i3] = tri.v3;
triOrder[i1] = i1;
triOrder[i2] = i2;
triOrder[i3] = i3;
i++;
}
Mesh mesh = new Mesh();
mesh.vertices = triVertices;
mesh.normals = triVertices;
mesh.triangles = triOrder;
return mesh;
}
삼각형들을 메쉬로 바꾸는 메소드다
vertices는 삼각형을 구성하는 3점의 위치이고
normal은 어떤 면이 앞인지 뒤인지 결정하고
triangles은 삼각형의 3점의 순서다
해깔릴 부분은 normal일 것 같지만 2D에다 Unity 내 mesh.recalulateNormal() 이 있으니 넘어간다
중요한건mesh를 표현하는 데이터 구조다
mesh를 표현하는 데이터구조 중 quad-edge, half-edge 등등이 있는데 이해하기 쉬운 half-edge부터 배웠다
habrador님의 것을 그대로 배끼다 알고리즘 실행 도중 막히는게 있어 깃헙에 있던 것을 참고했는데
블로그것에 있던 것이 서로 다르다는 걸 알아채는데 며칠 걸렸다
데이터 구조는 본인이 매우 깊게 알아야 한다는 중요한 교훈을 얻었다
처음이라면 아래 링크로부터 halfedge를 직접 체험해보고 자신이 직접 데이터구조를 만들어보자
visualization
데이터 구조 코드
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
public class HalfEdge
{
public HalfEdgeVertex v;
//The face it belongs to
public HalfEdgeFace face;
//The next half-edge inside the face (ordered clockwise)
//The document says counter-clockwise but clockwise is easier because that's how Unity is displaying triangles
public HalfEdge nextEdge;
//The opposite half-edge belonging to the neighbor
public HalfEdge oppositeEdge;
//(optionally) the previous halfedge in the face
//If we assume the face is closed, then we could identify this edge by walking forward
//until we reach it
public HalfEdge prevEdge;
public HalfEdge(HalfEdgeVertex v)
{
this.v = v;
}
}
public class HalfEdgeFace
{
public HalfEdge edge;
public float circumRadius;
public Vector2 circumCenter;
public Vector2 centerPosition;
public HalfEdgeFace(HalfEdge edge)
{
this.edge = edge;
Vector2 a = edge.v.position;
Vector2 b = edge.nextEdge.v.position;
Vector2 c = edge.prevEdge.v.position;
LinearEquation lineAB = new LinearEquation(a, b);
LinearEquation lineBC = new LinearEquation(b, c);
var perpendicularAB = lineAB.PerpendicularLineAt(Vector2.Lerp(a, b, .5f));
var perpendicularBC = lineBC.PerpendicularLineAt(Vector2.Lerp(b, c, .5f));
this.circumCenter = GetCrossingPoint(perpendicularAB, perpendicularBC);
this.circumRadius = Vector2.Distance(circumCenter, a);
}
public void RecalculateCircums()
{
Vector2 a = edge.v.position;
Vector2 b = edge.nextEdge.v.position;
Vector2 c = edge.prevEdge.v.position;
LinearEquation lineAB = new LinearEquation(a, b);
LinearEquation lineBC = new LinearEquation(b, c);
var perpendicularAB = lineAB.PerpendicularLineAt(Vector2.Lerp(a, b, .5f));
var perpendicularBC = lineBC.PerpendicularLineAt(Vector2.Lerp(b, c, .5f));
circumCenter = GetCrossingPoint(perpendicularAB, perpendicularBC);
circumRadius = Vector2.Distance(circumCenter, a);
centerPosition = (a + b + c) / 3;
}
static Vector2 GetCrossingPoint(LinearEquation line1, LinearEquation line2)
{
float A1 = line1._A;
float A2 = line2._A;
float B1 = line1._B;
float B2 = line2._B;
float C1 = line1._C;
float C2 = line2._C;
//Cramer's rule
float Determinant = A1 * B2 - A2 * B1;
float DeterminantX = C1 * B2 - C2 * B1;
float DeterminantY = A1 * C2 - A2 * C1;
float x = DeterminantX / Determinant;
float y = DeterminantY / Determinant;
return new Vector2(x, y);
}
public bool IsInside(Vector3 p)
{
Vector2 p1 = edge.v.position;
Vector2 p2 = edge.nextEdge.v.position;
Vector2 p3 = edge.prevEdge.v.position;
bool isWithinTriangle = false;
//Based on Barycentric coordinates
float denominator = ((p2.y - p3.y) * (p1.x - p3.x) + (p3.x - p2.x) * (p1.y - p3.y));
float a = ((p2.y - p3.y) * (p.x - p3.x) + (p3.x - p2.x) * (p.y - p3.y)) / denominator;
float b = ((p3.y - p1.y) * (p.x - p3.x) + (p1.x - p3.x) * (p.y - p3.y)) / denominator;
float c = 1 - a - b;
//The point is within the triangle or on the border if 0 <= a <= 1 and 0 <= b <= 1 and 0 <= c <= 1
//if (a >= 0f && a <= 1f && b >= 0f && b <= 1f && c >= 0f && c <= 1f)
//{
// isWithinTriangle = true;
//}
//The point is within the triangle
if (a > 0f && a < 1f && b > 0f && b < 1f && c > 0f && c < 1f)
{
isWithinTriangle = true;
}
return isWithinTriangle;
}
}
public class HalfEdgeVertex
{
public Vector2 position;
// 이 edge의 시작점은 이 vertex다.
public HalfEdge edge;
public HalfEdgeVertex(Vector2 position_)
{
position = position_;
}
}
[System.Serializable]
public class LinearEquation // 이 클라스는 아직 신경쓰지말자
{
public float _A;
public float _B;
public float _C;
public LinearEquation() { }
//Ax+By=C
public LinearEquation(Vector2 pointA, Vector2 pointB)
{
float deltaX = pointB.x - pointA.x;
float deltaY = pointB.y - pointA.y;
_A = deltaY; //y2-y1
_B = -deltaX; //x1-x2
_C = _A * pointA.x + _B * pointA.y;
}
public LinearEquation PerpendicularLineAt(Vector3 point)
{
LinearEquation newLine = new LinearEquation();
newLine._A = -_B;
newLine._B = _A;
newLine._C = newLine._A * point.x + newLine._B * point.y;
return newLine;
}
}
내가 만든 데이터구조를 그림으로 표현하면 이렇다
v = vertex
e = halfedge
n = halfedge.next
p = halfedge.prev
t = halfedge.opposite
다 만들었으면 이제 데이터구조들을 저장할 클라스를 하나 만들면 된다