[개념 정리] Marching Cube : 3D Point to Mesh생성 알고리즘

Marching Cube는 "3차원 공간 내 각 점에 대한 밀도 값들로 3D mesh를 생성하는 알고리즘"중에 하나입니다.

Wikipedia에 언급된 어려운 말로 다시 표현하자면, "3차원의 discrete한(=continuous하지 않는) scalar field(=스칼라장:유클리드 공간의 각점에 스칼라를 대응시킨 것)로 부터 isosurface(=등가면:3차원의 점들이 모여 만든 연속된 표면)형태의 pologon mesh(=다각형면의 조합으로 만든 3D 물체)를 추출하는 컴퓨터 그래픽스 알고리즘"입니다.

 

다시 간단하게 수식으로 풀어쓰자면, σ = f(x,y,z)함수로 3D Mesh를 생성하는 알고리즘 입니다. (x,y,z는 3차원 좌표이고 σ는 밀도입니다.)

 

Scalar field를 갖는 SDF(Signed Distance Field : 내부는 + 외부는 -로 표현하는 field)분야 또는 NeRF(Neural Radiance Field: Neural Network로 view에 따라 다르게 표현하는 field)분야에서 사용 될 수 있습니다.

 

여기까지 알고리즘의 목적에 대해서 설명하였고, 이제 Marching Cube 알고리즘 자체에 대해서 설명해보겠습니다.

 

 

 

Marching Cube 알고리즘

예시를 통해 설명하겠습니다. 초록색 object를 mesh형태로 만들고자 합니다. 3D 공간은 작은 단위의 투명색 cube로 표현 할 수 있습니다. 아래 예시는 16x16x16의 cube grid로 구성되어 있습니다. (그림 출처 : link)

각 투명 cube는 총 8개의 vertex로 구성되어 있으며, 이 vertex들이 object에 포함되어 있는지 유무에 따라 미리 정의해 둔 polygon으로 변형하여, 전체 3D Mesh를 형성합니다.

좀 더 구체적으로 설명하자면, 투명 cube는 vertex가 object에 포함되는지 유무에 따라 총 2^8개(=256개)의 경우의 수로 나눌 수 있습니다. 그리고 각 cube의 경우의 수 마다 surface polygon을 어떻게 배치 할지 사전에 구성해 둘 수 있습니다.  아래는 좌하단전면 1개 vertex를 기준점으로 15개의 경우의 수를 보여줍니다. 다른 7개의 기준점으로 대칭/반전이동이 되겠습니다. (그림 출처 : link)

각 다격형의 시작점은 edge의 중간을 꼭지점으로 갖기 때문에, 모든 투명cube를 이어붙이면 3D Mesh를 만들 수 있습니다.

 

수도코드(출처 : link)를 통해 설명해보자면,

class Point:
    def __init__(self, x: int, y: int, value: float):
        self.x, self.y, self.value = x, y, value
class Cube:
    def __init__(self, corner_points: List[Point]):
        self.corner_points = corner_points
class Grid3D:
    def __init__(self, cubes: List[Cube]):
        self.cubes = cubes

def integer_representation_for_cube(cube: Cube, threshold: float) -> int:
    integer_value = 0
    for index, point in enumerate(cube.corner_points):
        if point.value > threshold:
            integer_value += 1 << index
    return integer_value

def marching_cubes(grid: Grid3D, threshold: float): # 1)
    for cube in grid.cubes: # 1)
        integer_representation = integer_representation_for_cube(cube, threshold) # 2)
        triangles_to_draw: List[Triangle] = lookup_table[integer_representation] # 3)

        for triangle in triangles_to_draw: # 4)
            draw_triangle(triangle)

1) 3D 공간(Grid3D class)에 8 vertex(Points class)로 구성된 Cube(Cube class)들이 주어질 경우, marching_cubes함수에서 cube들을 전체 탐색합니다.

2) inter_representation_for_cube함수에서는 vertex의 밀도값(value)이 정의해 둔 threshold가 넘으면, 이진법 형태로 1 아니면 0으로 저장합니다. cube가 가질 수 있는 경우의 수는 2^8이므로 각 cube는 integer_value를 8bit로 저장 할 수 있습니다.

3) integer_value으로 미리 정의한 lookup_table 딕셔너리를 조회하여 polygon(Triangle class) list를 획득합니다. 

4) cube 마다 polygon들을 랜더링합니다.

 

 

 

그 외 mesh 생성 알고리즘들..

그 외, Marching Cube의 2D버전인 Marching Square알고리즘(link)이 있고, edge의 중간 점이 아닌 vertex의 밀도 값 크기에 따라, edge의 위치를 linear하게 변형하는 기법, 2D polygon의 조합으로 mesh를 생성하지 않고 3D tetrahedron(4면체)로 mesh를 생성하는 기법들이 있습니다. (그림 출처 : link)

 

 

 

Closing..

Marching Cube는 역사가 깊은 알고리즘입니다. 1987년도에 SIGGRAPH에서 나왔으며 당시 CT, MRI scan 이미지를 3D 모델링하는데 사용되었다고 합니다. 최근에는 Nvidia에서 Point Cloud를 입력으로 Tetrahedra기법과 generative model을 사용해 Mesh를 생성하는 DMTet(NeurlPS 2021) 하는 연구도 있습니다. Get3D(NeurlPS 2022) 에서는 texture까지 생성하고 있습니다. link(extract_mesh로 검색)에서는 NeRF로 만든 모델에 marching cube를 적용하고 color mesh까지 하고 있습니다. 

 

 

 

출처 : link1, link2, link3, link4, link5