Marching Squares - Part 2 | Implementation
Metaball을 표현해봅시다
목차
- Marching Squares - Part 1 | Algorithm
- Marching Squares - Part 2 | Implementation
- Marching Squares - Part 3 | Optimization
Metaball
Metaball은 Isosurface의 한 형태로, 액체와 같이 Blobby한 모습을 표현하는데 사용할 수 있습니다. 여기서는 2차원의 Metaball을 다루는데 더 일반적인 이야기는 위키(Metaballs)를 참고하시면 좋습니다.
Metaball을 구현하는 방법이 Marching Squares만 있는것은 아닙니다. Shader를 이용한 구현도 있고, 3차원이라면 Ray Marching을 이용할 수도 있습니다. 심지어 속도도 Shader를 이용하면 대체로 더 빠릅니다!
Voxel
public struct Voxel
{
float density;
public float Density
{
get => density;
set => density = Mathf.Clamp(value, -1f, 1f);
}
}
Grid로 표현되는 맵에서 각 교차점에 해당하는 부분입니다. 따라서 Part 1에서 봤던 사각형의 꼭짓점을 표현하는 것이죠. 하지만 여기서 주의해야 할 점은 Mesh가 만들어지는 지점의 위치가 Voxel이 아니라는 것입니다. 아직 무슨말인지 잘 모르겠더라도 괜찮습니다. 아래에서 계속 설명하겠습니다.
Marching Squares
public static void GenerateMarchingSquares(Voxel[,] voxels, Vector2Int chunkSize, Vector2 chunkScale, bool interpolate ref List<Vector3> verticies, ref List<int> triangles)
{
for (int x = 0; x < chunkSize.x; x++)
{
for (int y = 0; y < chunkSize.y; y++)
{
// Density 계산
// 교차하는 변 찾기
// 변에서 교차점 위치 계산
// 최종 삼각형 추가
}
}
}
알고리즘은 다음과 같이 진행됩니다. 차례로 살펴보겠습니다.
Density 계산
/*
* 0 1
* ┌─────────┐
* │ 4 │ 0~3 : 모서리
* │7 5│ 4~7 : 변
* │ 6 │
* └─────────┘
* 3 2
*/
public static Vector2Int[] CornerTable =
{
new Vector2Int(0, 1),
new Vector2Int(1, 1),
new Vector2Int(1, 0),
new Vector2Int(0, 0),
};
float[] densities = new float[4];
// 사각형의 각 꼭짓점을 순회하면서 Density를 받아온다
for (int i = 0; i < 4; i++)
{
densities[i] = voxels[x + CornerTable[i].x, y + CornerTable[i].y].Density;
}
Density를 받아오는 부분입니다. 여기서 CornerTable이 쓰이는데, Table을 보시면 사각형의 꼭짓점에 대한 Offset인 것을 알 수 있습니다.
교차하는 변 찾기
public static int[] EdgeTable =
{
0, //{0, 0, 0, 0}, // 0000
3, //{0, 0, 1, 1}, // 0001
6, //{0, 1, 1, 0}, // 0010
5, //{0, 1, 0, 1}, // 0011
12, //{1, 1, 0, 0}, // 0100
15, //{1, 1, 1, 1}, // 0101
10, //{1, 0, 1, 0}, // 0110
9, //{1, 0, 0, 1}, // 0111
9, //{1, 0, 0, 1}, // 1000
10, //{1, 0, 1, 0}, // 1001
15, //{1, 1, 1, 1}, // 1010
12, //{1, 1, 0, 0}, // 1011
5, //{0, 1, 0, 1}, // 1100
6, //{0, 1, 1, 0}, // 1101
3, //{0, 0, 1, 1}, // 1110
0, //{0, 0, 0, 0}, // 1111
};
// 교차하는 꼭짓점을 찾는다
// IsoLevel은 0이라고 가정
int intersectionBits = 0;
for (int i = 0; i < 4; i++)
{
if (densities[i] > 0)
{
intersectionBits |= 1 << (3 - i);
}
}
// 교차하는 꼭짓점이 없다면 끝낸다.
if(intersectionBits == 0)
continue;
// 교차하는 변 찾기
int edgeBits = EdgeTable[intersectionBits];
교차하는 꼭짓점에 대해서 Bit를 1로 설정합니다. 만약 교차하는 꼭짓점이 없었다면 intersectionBits는 0이며, Loop를 Skip합니다. 그 후 EdgeTable을 이용해 edgeBits를 찾습니다.
변에서 교차점 위치 계산
public static int[,] CornerofEdgeTable =
{
{0, 1},
{1, 2},
{2, 3},
{3, 0}
};
static Vector2 VectorInterp(Vector2 p0, Vector2 p1, float v0, float v1)
{
// IsoLevel은 0이라 가정
if (Mathf.Abs(v0) < 0.00001f)
return p0;
if (Mathf.Abs(v1) < 0.00001f)
return p1;
if (Mathf.Abs(v0 - v1) < 0.00001f)
return p0;
float mu = (0 - v0) / (v1 - v0);
return new Vector2
{
x = p0.x + mu * (p1.x - p0.x),
y = p0.y + mu * (p1.y - p0.y)
};
}
// 교차하는 변의 교차점 보간하여 찾기
Vector2Int gridPosition = new Vector2Int(x, y);
Vector2[] interpolatedPoints = new Vector2[4];
for (int i = 0; i < 4; i++) // 각 변을 순회
{
if ((edgeBits & (1 << (3 - i))) != 0) // 만약 변이 교차되었다면
{
Vector2 edge0 = (gridPosition + CornerTable[CornerofEdgeTable[i, 0]]);
Vector2 edge1 = (gridPosition + CornerTable[CornerofEdgeTable[i, 1]]);
if (interpolate) // 보간을 사용하는가?
{
float v0 = densities[CornerofEdgeTable[i, 0]];
float v1 = densities[CornerofEdgeTable[i, 1]];
interpolatedPoints[i] = VectorInterp(edge0, edge1, v0, v1);
}
else
{
interpolatedPoints[i] = (edge0 + edge1) / 2.0f; // 변의 중심점 사용
}
}
}
CornerofEdgeTable은 변의 두 꼭짓점에 해당하는 정보입니다. 따라서 interpolate가 true인 경우에는 두 꼭짓점의 위치와 Density를 이용해 선형보간을 하여 실제 교차된 지점을 찾을 수 있습니다.
삼각형을 만들기 전에
// 모서리와 변의 교차점을 합친 배열
Vector2[] finalPoints = new Vector2[8];
for (int i = 0; i < 4; i++)
{
finalPoints[i] = gridPosition + CornerTable[i];
}
for (int i = 4; i < 8; i++)
{
finalPoints[i] = interpolatedPoints[i - 4];
}
사각형의 꼭짓점과 변의 보간된 점을 합친 배열을 만듭니다. 이는 바로 나올 삼각형을 만들 때 사용합니다.
삼각형 만들기
public static int[,] TriangleTable =
{
// 0~3 : 사각형의 꼭짓점, 4~7 : 변의 보간된 점 // intersectionBits
{-1, -1, -1, -1, -1, -1, -1, -1, -1}, // 0000
{3, 7, 6, -1, -1, -1, -1, -1, -1}, // 0001
{2, 6, 5, -1, -1, -1, -1, -1, -1}, // 0010
{3, 7, 5, 3, 5, 2, -1, -1, -1}, // 0011
{4, 1, 5, -1, -1, -1, -1, -1, -1}, // 0100
{4, 1, 5, 3, 7, 6, -1, -1, -1}, // 0101
{6, 4, 1, 6, 1, 2, -1, -1, -1}, // 0110
{2, 3, 7, 2, 7, 4, 2, 4, 1}, // 0111
{7, 0, 4, -1, -1, -1, -1, -1, -1}, // 1000
{3, 0, 4, 3, 4, 6, -1, -1, -1}, // 1001
{7, 0, 4, 2, 6, 5, -1, -1, -1}, // 1010
{3, 0, 4, 3, 4, 5, 3, 5, 2}, // 1011
{7, 0, 1, 7, 1, 5, -1, -1, -1}, // 1100
{0, 1, 5, 0, 5, 6, 0, 6, 3}, // 1101
{1, 2, 6, 1, 6, 7, 1, 7, 0}, // 1110
{3, 0, 2, 2, 0, 1, -1, -1, -1} // 1111
};
// 삼각형 만들기
for (int i = 0; i < 9; i += 3)
{
int index0 = TriangleTable[intersectionBits, i];
int index1 = TriangleTable[intersectionBits, i + 1];
int index2 = TriangleTable[intersectionBits, i + 2];
if(index0 == -1 || index1 == -1 || index2 == -1)
break;
Vector3 vertex0 = finalPoints[index0] * chunkScale;
Vector3 vertex1 = finalPoints[index1] * chunkScale;
Vector3 vertex2 = finalPoints[index2] * chunkScale;
verticies.Add(vertex0);
verticies.Add(vertex1);
verticies.Add(vertex2);
int numTriangles = triangles.Count;
triangles.Add(numTriangles++);
triangles.Add(numTriangles++);
triangles.Add(numTriangles);
}
마지막으로 삼각형을 만드는 부분입니다. 크게 어려운 부분은 없고, TriangleTable을 보고 꼭짓점과 보간된점에서 어떤 점 그리고 어디의 점을 사용할지 알 수 있습니다. 사실 Table의 사용은 모두 Optional합니다. 모두 직접 switch등으로 로직을 작성하여도 당연히 괜찮습니다.
끝입니다. 간단한 알고리즘이죠.
마무리
삼각형이 너무 많아요!
여기까지 구현된 알고리즘으로는 아직 문제가 많습니다. Vertex를 Indexing하지 않아 중복된 Vertex들이 있고, 사실 가운데에 꽉 찬 사각형들은 큰 사각형으로 하나로 합칠 수도 있겠죠. 이러한 부분에 대한 최적화를 다음 Part3에서 다루도록 하겠습니다.
모든 코드는 Github/Marching-Squares에서 보실 수 있습니다. Part를 3까지 기획하고 있기 때문에 위의 코드와는 조금 다릅니다. 하지만 조금 살펴보시면 몇몇이 생략된 것 말고는 똑같다는 걸 알 수 있을 겁니다.
감사합니다.