[Graphics] 복셀 마칭큐브와 Mesh Terrain - 2

[Graphics] 복셀 마칭큐브와 Mesh Terrain - 1

[Graphics] 복셀 마칭큐브와 Mesh Terrain - 3

[Graphics] 복셀 마칭큐브와 Mesh Terrain - 4

 

Ch2. 입문 — 2D 마칭 스퀘어로 직관 잡고 3D로 점프

마칭큐브는 3D 알고리즘인데, 처음 만나면 큐브 8버텍스가 동시에 안/밖이 갈리는 그림이 머릿속에 잘 그려지지 않는다. 한 차원 내려가서 2D부터 보면 같은 아이디어가 손바닥만한 격자에 펼쳐지고, 거기서 3D로 점프하는 게 훨씬 자연스럽다. 이 챕터는 2D의 마칭 스퀘어(marching squares)로 직관을 잡은 다음, 그 직관을 그대로 한 차원 끌어올려 3D 마칭큐브로 넘어가는 게 목표다.

2D 마칭 스퀘어 — 4 꼭짓점, 16 케이스, 4 고유 케이스

스칼라 장 f(x, y)가 평면에 정의돼 있다고 하자. 우리가 원하는 건 그 장의 등치선(isoline), 즉 f = iso가 되는 곡선이다. 격자(grid) 한 칸을 떼어내면 그 칸은 4개의 꼭짓점을 가진 사각형이다. 각 꼭짓점에서 스칼라 값을 한 번씩 샘플링해 두면, 그 값이 iso보다 작으냐 크냐로 안(below) / 밖(above) 두 상태 중 하나가 된다.

꼭짓점 4개 × 상태 2개니까 한 칸이 가질 수 있는 안/밖 패턴은 정확히 2⁴ = 16가지다. 0000(전부 밖)부터 1111(전부 안)까지. 각 패턴마다 등치선이 그 사각형을 어떻게 가로지르는지가 정해진다. 가장 흔한 패턴 한두 개만 그림으로 보면 "아하" 하는 순간이 온다.

[IMAGE 04 — Marching Squares 16 cases (Python/matplotlib): 4×4 grid, 각 셀에 4꼭짓점 채움 패턴 + 그 안을 가로지르는 등치선. 회전/반사로 묶이는 4 고유 케이스는 색상 그룹으로 표시. 좌표 정확.]

회전(90°·180°·270°)과 반사 대칭으로 묶으면 16개 케이스는 결국 4개의 고유 케이스로 줄어든다.

•      Case A — 전부 안 / 전부 밖. 등치선 없음. (0000, 1111)

•      Case B — 한 꼭짓점만 다른 상태. 그 꼭짓점을 둘러싼 두 엣지를 가로지르는 짧은 직선 한 조각. (8개 패턴이 회전·반사로 묶임)

•      Case C — 인접한 두 꼭짓점이 같은 상태. 사각형을 가로지르는 직선 한 조각. (4개 패턴)

•      Case D — 대각선 두 꼭짓점만 같은 상태 (saddle). 두 조각이 나오는데, 두 가지 연결 방식이 모두 합법이다. 이게 2D판 모호성(ambiguity) 케이스다. (2개 패턴)

Case D의 두 가지 합법 연결 중 어느 쪽을 고를지는 보조 정보 — 예를 들어 사각형 중앙의 보간된 스칼라 값 — 로 결정한다. 이게 3D에서 Case 6 / 13 같은 모호성 케이스로 그대로 확대된다. 2D에서 잠깐 머리를 갸웃하게 만드는 정도지만, 3D에서는 "터널(tunnel)이 뚫리느냐 막히느냐"가 갈리는 위상 결정으로 격상된다. Ch3에서 다시 만난다.

"Marching"이라는 이름의 유래

이 알고리즘 가족이 굳이 마칭(marching, 행진)이라는 군대 용어를 달고 다니는 이유는, 격자의 한 칸 한 칸을 마치 검열관이 행진하듯 순회하면서 같은 룩업 규칙을 반복 적용하기 때문이다. 한 칸의 결정이 옆 칸에 영향을 주지 않고, 모든 칸이 똑같은 짧은 절차를 거친다. 컴파일러로 치면 한 줄짜리 함수를 격자 전체에 map() 하는 셈이고, GPU로 옮기면 한 칸당 한 스레드를 띄우면 끝이다. 알고리즘 이름이 곧 그 구조를 광고하는 드문 사례다.

대안 이름인 cuberille(라틴어로 "큐브 격자"), isosurfacing, contouring 같은 표현들도 같은 가족을 가리키지만, 마칭 계열만이 "한 칸씩 도장 찍듯 진행한다"는 구현 패턴까지 이름에 박아 넣었다.

점프 — 4 꼭짓점이 8 꼭짓점이 되는 순간

여기까지 잡았으면 3D 마칭큐브는 같은 알고리즘을 한 차원 끌어올린 것이다. 정확히 세 가지가 바뀐다.

1.    격자 한 칸의 꼭짓점이 4개 → 8개로 늘어난다. 사각형이 큐브가 되니까.

2.    케이스 수가 2⁴ = 16 → 2⁸ = 256으로 폭증한다. 모든 안/밖 조합.

3.    출력이 선분(line segment)이 아니라 삼각형(triangle)이다. 등치선이 등치면이 됐으니까.

[IMAGE 05 — 2D Marching Squares → 3D Marching Cubes (SVG): 좌측에 4꼭짓점 한 케이스, 우측에 8꼭짓점 큐브의 대응되는 케이스. 화살표로 차원 점프. 4→8, 16→256, 선분→삼각형 라벨링.]

256은 큰 숫자처럼 들리지만, 회전(24개)과 반사 대칭을 모두 적용해 묶으면 결국 15개의 고유 케이스로 줄어든다. 이 15 케이스를 한 장에 그려둔 그림이 마칭큐브 글의 트레이드마크 같은 다이어그램이고, Ch3에서 자세히 본다.

여기서 한 가지 안심해도 되는 사실. 256개 케이스 표를 직접 손으로 채울 일은 거의 없다. 1987년 Lorensen & Cline의 원논문이 15 케이스를 그려서 발표한 이후, Paul Bourke의 polygonising 코드(paulbourke.net/geometry/polygonise)가 public-domain으로 256개 표를 모두 펼쳐 풀어 깔아 두었고, 그 표가 사실상 모든 마칭큐브 구현의 출발점이 됐다. OpenVDB, FastNoise, Voxel Tools, Unreal Engine 내부 GeometryProcessing 모듈까지 — 모두 같은 인덱싱 컨벤션과 같은 (또는 동등한) 룩업 테이블을 공유한다. 즉 새 프로젝트에서 마칭큐브를 들고 와야 할 때 진짜로 직접 짤 부분은 스칼라 장을 어떻게 채울지(노이즈 vs SDF vs CT 데이터) 정도이고, 케이스 분류와 룩업은 거의 모두 잘 다듬어진 레퍼런스에서 옮겨오면 된다.

큐브 인덱싱 컨벤션 — 끝까지 들고 갈 약속

3D에서 8개 꼭짓점에 번호를 매기는 방식은 구현체마다 살짝 다르지만, 이 글에서는 Paul Bourke의 polygonising 코드와 대부분의 오픈소스 구현(특히 OpenVDB, FastNoise)이 채택한 표준을 따른다. 이 표는 이 글 끝까지 그대로 쓰니까 한 번에 못 박고 가자.

인덱스	좌표 (x, y, z)	위치 설명
V0	(0, 0, 0)	바닥 — 앞-왼쪽
V1	(1, 0, 0)	바닥 — 앞-오른쪽
V2	(1, 1, 0)	바닥 — 뒤-오른쪽
V3	(0, 1, 0)	바닥 — 뒤-왼쪽
V4	(0, 0, 1)	위 — 앞-왼쪽
V5	(1, 0, 1)	위 — 앞-오른쪽
V6	(1, 1, 1)	위 — 뒤-오른쪽
V7	(0, 1, 1)	위 — 뒤-왼쪽

 

엣지는 그 사이를 잇는다. 12개의 엣지에도 번호가 있다.

인덱스	잇는 꼭짓점	위치
E0	V0 — V1	바닥 앞
E1	V1 — V2	바닥 오른쪽
E2	V2 — V3	바닥 뒤
E3	V3 — V0	바닥 왼쪽
E4	V4 — V5	위 앞
E5	V5 — V6	위 오른쪽
E6	V6 — V7	위 뒤
E7	V7 — V4	위 왼쪽
E8	V0 — V4	세로 — 앞-왼쪽
E9	V1 — V5	세로 — 앞-오른쪽
E10	V2 — V6	세로 — 뒤-오른쪽
E11	V3 — V7	세로 — 뒤-왼쪽

 

[IMAGE 06 — 큐브 8버텍스 / 12엣지 인덱싱 (SVG): isometric 큐브, V0-V7 라벨 + E0-E11 엣지 라벨. 바닥(z=0) 옅은 색, 위(z=1) 진한 색으로 구분. 좌표축 표시.]

이 번호 매김이 정해지면 한 칸의 안/밖 패턴은 8비트 정수 하나로 압축된다. V_i가 안이면 i번 비트가 1이라는 단순한 규칙이다. 즉 안/밖 패턴 → 0…255 사이 정수 = 큐브 인덱스. 그 인덱스가 곧 256 케이스 중 어느 케이스인지를 가리키는 키가 된다. Ch3의 테이블 룩업이 바로 이 인덱스 한 방으로 결정된다.

복셀 — 마칭이 실제로 행진하는 단위

"복셀"이라는 단어를 여러 의미로 쓰는데, 마칭큐브 맥락에서는 3D 격자의 한 칸, 정확히는 그 칸의 8개 꼭짓점에서 스칼라 값을 샘플링했다는 사실을 가리킨다. 그래서 NxNxN 그리드에는 (N-1)³개의 복셀 칸이 있고, 각 칸마다 위에서 본 8버텍스 인덱싱 → 256 케이스 룩업 → 삼각형 추출이 독립적으로 일어난다.

[IMAGE 07 — Voxel grid 분위기 (nanobanana 일러스트): 반투명한 3D 그리드 위에 등치면이 살짝 떠오르는 컷. 칸마다 마칭이 진행되는 느낌. 정확 좌표보다는 시각적 분위기.]

여기서 "독립적"이라는 단어가 중요하다. 한 큐브의 결과가 옆 큐브에 직접 의존하지 않으므로 알고리즘은 창피할 만큼 병렬화가 잘 된다(embarrassingly parallel). GPU 컴퓨트 셰이더로 옮기기 쉬운 이유, UE 5.8 MeshPartition이 청크 단위로 베이크할 수 있는 이유가 모두 여기에서 온다.

물론 인접 큐브가 같은 엣지를 공유하므로, 그 엣지 위에 찍히는 보간 교점도 두 큐브에서 같은 좌표여야 한다. 보간 공식이 양쪽에서 동일한 두 끝값으로 계산되니 자연히 그렇게 되지만, 정점 중복(같은 엣지 교점을 두 번 등록)을 피하려면 엣지 인덱스 → 정점 인덱스 해시를 들고 다니는 게 보통이다. 구현 디테일은 Ch3의 성능 절(節)에서 다시 만난다.

스칼라 장이 어디서 오는가

8버텍스 샘플링이라는 표현을 가볍게 썼지만, 그 값이 어디서 오는가는 사용 케이스마다 다르다. 의료 영상에서는 CT 보클(voxel)의 헝(Hounsfield) 단위가 그대로 들어오고, 게임의 절차적 지형에서는 3D Perlin / Simplex 노이즈가 위치를 받아 실수 하나를 뱉는다. UE 5.8 메시 테레인에서는 하이트맵을 한 번 임포트한 다음 그 결과를 협대역 SDF로 들고 있다가, 두 메시를 합칠 때 그 SDF 값을 8버텍스에서 평가하는 식이다. 즉 마칭큐브 입력은 함수든 보클 그리드든 SDF 텍스처든 상관없이, "한 점에 실수 하나를 돌려주는 무언가"면 충분하다. 이 추상화가 알고리즘이 30년 넘게 살아남은 이유 중 하나다.

노멀은 어떻게 구하나

삼각형이 나와도 셰이딩에 쓸 노멀이 없으면 메시가 완성되지 않는다. 마칭큐브에서 노멀은 보통 스칼라 장의 그래디언트(∇f)를 정규화해서 쓴다. 정점 좌표가 정해진 다음 그 좌표에서 ∂f/∂x, ∂f/∂y, ∂f/∂z를 중앙 차분(central difference)으로 추정하고, 부호는 등치값 방향에 맞춰 뒤집는다. 별도의 후처리(per-face normal → vertex normal averaging) 없이 샘플링 단계에서 바로 부드러운 노멀이 떨어지는 게 마칭큐브 가족의 깔끔한 점이다.

이 챕터 요약

차원	한 칸의 꼭짓점	케이스 수	회전·반사 후 고유 케이스	출력
2D (Marching Squares)	4	2⁴ = 16	4	선분
3D (Marching Cubes)	8	2⁸ = 256	15	삼각형

 

다음 챕터에서는 그 15 케이스가 어떻게 한 장에 펼쳐지는지, 엣지 테이블과 삼각형 테이블이 어떻게 한 번의 룩업으로 메시를 토해내는지, 그리고 1987년부터 따라다닌 모호성 케이스의 정체를 차례로 푼다. 차원이 늘어났을 뿐 "한 칸을 8비트로 압축해 룩업 한 번에 끝낸다"는 핵심 골격은 2D 마칭 스퀘어 때와 정확히 같다는 점만 머릿속에 들고 넘어가면 된다. 핵심은 비트 패턴 하나가 곧 인덱스고, 인덱스 하나가 곧 케이스고, 케이스 하나가 곧 미리 계산된 삼각형 묶음을 가리킨다는 사실 — 룩업 한 번이 메시 한 조각이다.