Marching Cubes

https://dl.acm.org/doi/pdf/10.1145/37402.37422

"Marching cubes: A high resolution 3D surface construction algorithm"

 

3차원 공간에 있는 density 값들로 3D Mesh를 생성하는 알고리즘입니다.

 

먼저 8개의 vertex로 이루어진 cube가 있고, 이런 cube들이 모여서 3D 공간을 생성합니다.

 

Cube

 

큐브의 각 꼭짓점의 값이 임계값(surface value)보다 크면 1, 작으면 0으로 레이블링 합니다.

아래 그림처럼 까만 점으로 표현된 꼭짓점(1)과 아닌 꼭짓점(0) 사이의 모서리는 분리되게 됩니다.

(예를 들어, NeRF와 Marching Cubes가 연결될 때는, NeRF의 출력인 x,y,z 좌표가 cube를 구성하는데 사용되고, density가 각 꼭짓점의 값이 됩니다)

8개의 꼭짓점이 0 또는 1의 값을 가질 수 있기 때문에 총 256 경우의 수가 존재합니다.

대칭인 것들을 제거하면 14개의 패턴으로 표현할 수 있다고 합니다.

 

모서리가 분리될 때, 분리되는 위치(=intersection)는 linear interpolation을 통해 계산됩니다.

 

Mesh로 표현하기 위해 각 vertex의 unit normal을 구해야 합니다.

먼저 아래 수식으로 cube의 8개 vertex에 대해 gradient를 구한 후, 이 normal (=정규화된 gradient)값을 linear interpolation해서 intersection의 normal 값을 계산합니다.

 

계산된 intersection의 위치와 normal 값으로 3d mesh를 생성할 수 있습니다.