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

 

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

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

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

 

Ch3. 딥다이브 — 인덱싱 → 테이블 → 보간 → 모호성 → 비교 → 성능

이 챕터는 한 큐브 안에서 마칭큐브가 실제로 무슨 일을 하는지를 끝까지 푼다. 8개 안/밖 비트가 어떻게 8비트 정수 하나로 압축되고, 그 정수가 어떻게 엣지 테이블·삼각형 테이블이라는 두 장의 미리 계산된 룩업표를 한 번씩 조회해서 삼각형을 토해내는지, 보간이 어떻게 정확한 위치를 잡는지, 그리고 1987년부터 따라다닌 모호성(ambiguity) 케이스가 왜 위상 결정을 흔드는지까지가 한 묶음이다. 마지막에는 Dual Contouring / Surface Nets 같은 사촌 알고리즘들과의 짧은 비교, 그리고 성능·메모리 실전 고려사항으로 마무리한다.

8비트 인덱스 — 한 칸을 한 정수로 압축

Ch2에서 정한 인덱싱 컨벤션을 그대로 들고 온다. V_i가 안이면 i번 비트가 1이라는 규칙으로, 한 큐브의 안/밖 패턴은 0…255 사이의 정수 하나로 압축된다.

cubeIndex = 0

for i in 0..7:

    if scalar[V_i] < iso:

        cubeIndex |= (1 << i)

여기서 부등호 방향은 컨벤션이다. 이 글에서는 "안 = 값이 등치값보다 작다" 를 일관되게 쓴다(Bourke 코드와 동일, OpenVDB와 동일). 부호 있는 거리 장(SDF)을 쓰면 "안 = 음수"가 되니 같은 의미가 된다. 부호를 통째로 뒤집은 컨벤션을 쓰는 구현체도 있는데(특히 의료 영상의 일부 코드), 그 경우 결과 메시의 노멀이 뒤집힌 채로 나온다. 정점이 같은 자리에 찍히므로 메시 자체는 옳고, 보통 노멀만 부호 뒤집어 처리하면 끝이다.

256개 케이스가 나오지만, 회전(큐브의 회전 대칭군은 24개)과 반사 대칭으로 묶으면 15개 고유 케이스로 줄어든다. 1987년 Lorensen & Cline의 SIGGRAPH 원논문이 처음 분류한 것도 정확히 이 15개다.

[IMAGE 08 — 15 unique cases (Python): 4×4 grid (15 + blank), 각 cell은 isometric 큐브 + 안쪽 정점 검정 동그라미 + 등치 삼각형 빨강. Case 0(전부 밖) ~ Case 14 라벨. Paul Bourke의 polygonising 테이블을 독립 렌더링 (Lorensen Fig 4 트레이스 아님).]

이 15 케이스를 회전·반사로 펼치면 다시 256개 케이스가 모두 나오는데, 실제 구현은 그 256개를 미리 펼쳐서 두 장의 표에 박아 놓는다. 런타임에 회전 행렬을 곱할 필요가 없으니 룩업 한 번이 진짜로 룩업 한 번이다. 그 두 장의 표가 다음 절에서 만날 엣지 테이블과 삼각형 테이블이다.

두 장의 룩업 표 — 엣지 테이블 & 삼각형 테이블

엣지 테이블 — "어느 엣지가 교차되었나"

엣지 테이블은 길이 256의 배열이고, 각 원소는 12비트 마스크다. cubeIndex로 한 번 인덱싱하면 그 큐브에서 등치면이 가로지르는 12개 엣지 중 어느 것이 활성인지가 한 비트씩 켜져 있다.

// 발췌: paulbourke.net/geometry/polygonise

int edgeTable[256] = {

    0x0,   0x109, 0x203, 0x30a, 0x406, 0x50f, 0x605, 0x70c,

    0x80c, 0x905, 0xa0f, 0xb06, 0xc0a, 0xd03, 0xe09, 0xf00,

    // ... (총 256개)

};

 

int edgeMask = edgeTable[cubeIndex];

if (edgeMask == 0) return;  // 전부 안이거나 전부 밖, 삼각형 없음

edgeMask & (1 << e) [0001 0000 1001]가 켜져 있으면 E_e 엣지에 등치면이 교차한다는 뜻이다. 그 자리에 보간 교점을 찍어둔다(자세한 보간 공식은 다음 절). 

edgeMask & (1 << e) [0001 0000 1001] 의 시각적의미 :
V0(물 속)에서 출발해서 물 밖의 꼭짓점으로 향하는 엣지는 딱 3개뿐입니다. V1으로 가는 E0, V3로 가는 E3, V4로 올라가는 E8입니다.

삼각형 테이블 — "어느 엣지들을 잇는가"

삼각형 테이블도 길이 256이지만, 각 원소는 길이 16의 정수 배열이다. 3개씩 묶이는 엣지 인덱스 트리플의 나열이고, 끝은 −1로 종료된다. 한 큐브에서 최대 5개의 삼각형이 나올 수 있으므로 15개의 엣지 인덱스 + 종료 −1로 16칸이다.

( 엣지 테이블을 통해 교차하는 엣지들을 찾아 그 위에 점(교점)을 찍었다면, 삼각형 테이블은 "그 점들을 어떤 순서로 이어서 삼각형(폴리곤)을 만들 것인가?"를 알려줍니다. )

// 예: cubeIndex == 0xe (V1,V2,V3가 안)

// triTable[0xe] = { 9, 8, 3,   9, 3, 2,  9, 2, 11, -1, ... }

// → 삼각형 3개: (E9, E8, E3), (E9, E3, E2), (E9, E2, E11)

for (int i = 0; triTable[cubeIndex][i] != -1; i += 3) {

    addTriangle(vertOnEdge[triTable[cubeIndex][i + 0]],

                vertOnEdge[triTable[cubeIndex][i + 1]],

                vertOnEdge[triTable[cubeIndex][i + 2]]);

}

여기서 vertOnEdge[e]는 엣지 테이블 단계에서 미리 계산해 둔, E_e 위의 보간 교점이다. 이 두 단계를 합치면 한 큐브에서 0~5개의 삼각형이 나온다.

 

[시각적 예시: 이어서 삼각형 만들기]

• 상황: 위의 예시와 동일하게 cubeIndex가 1인 상황입니다. 교차점이 생긴 엣지는 E0, E3, E8입니다.
• 테이블 조회: triTable[1]을 조회하면 결과 배열은 [0, 8, 3, -1]로 나옵니다. (-1은 배열의 끝을 의미합니다.)
• 시각적 의미: * 첫 번째 교점: E0 엣지 위의 점
  • 두 번째 교점: E8 엣지 위의 점
  • 세 번째 교점: E3 엣지 위의 점
  • 이 세 점을 선으로 쫙 이어붙이면 V0 꼭짓점 하나만 싹둑 잘라내는 형태의 작은 삼각형 1개가 허공에 그려집니다. 이것이 렌더링될 메시의 한 조각입니다.

[IMAGE 09 — 테이블 룩업 흐름 (SVG): cubeIndex(8-bit) → edgeTable → 활성 엣지 마스크(12-bit) → vertOnEdge 보간 → triTable → 삼각형 트리플. 화살표 + 작은 큐브 픽토그램.]

룩업 한 번이 끝나면 그 큐브의 메시 기여분은 결정이다. 격자 전체에 같은 절차를 마칭하면 전역 메시가 완성된다. 데이터 의존성이 한 큐브 안으로 닫혀 있다는 점이 GPU 병렬화의 자유도를 그대로 보장한다.

엣지 보간 — 정확한 교점 찍기

엣지 테이블이 "어느 엣지가 활성"인지만 알려준다면, 그 엣지 위 어디에 정점을 찍을지는 보간이 결정한다. 등치값보다 작은 끝과 큰 끝 사이를 선형 보간한다.

        v0           iso          v1

        ●----------|-------------●

        p0          p             p1

 

        t = (iso - v0) / (v1 - v0)        // ∈ [0, 1]

        p = p0 + t * (p1 - p0)

여기서 v0, v1은 엣지 양끝의 스칼라 값, p0, p1은 양끝의 좌표, iso는 등치값, t는 보간 파라미터다. iso == v0이면 t == 0이라 정점은 정확히 p0에 떨어지고, iso == v1이면 t == 1이라 p1에 떨어진다. 수치적으로 v0 == v1인 자리는 0으로 나누기가 되니, t = 0.5로 폴백하거나 작은 엡실론 가드를 두는 게 보통이다(그 자리는 등치값이 끝과 정확히 같다는 의미라 어느 위치를 골라도 거의 동일하다).

[IMAGE 10 — 엣지 보간 (SVG): 한 엣지 수평선, 왼쪽 끝 v0=-0.4, 오른쪽 끝 v1=+0.8, iso=0 표시. 보간 t = 0.4/1.2 = 0.333 → p = p0 + 0.333*(p1-p0) 위치에 빨강 점. 수식 박스 인접 배치.]

선형 보간을 쓰는 것은 한 큐브 내부에서 스칼라 장이 선형으로 변한다고 가정하기 때문이다. 실제 장은 일반적으로 비선형이지만, 한 칸이 충분히 작으면 그 안에서의 선형 근사가 만들어내는 오차는 무시할 만한 수준이고, 등치면 자체의 위상은 정확히 보존된다. 더 정확한 위치가 필요하면 격자 해상도를 올리는 것이 보간 차수를 올리는 것보다 거의 항상 더 효과적이다 — 이 점은 마칭큐브 가족의 거의 모든 후속 논문이 공유하는 결론이다.

모호성 케이스 — 면 모호성, 내부 모호성, dual surface

Lorensen & Cline의 원논문은 15 케이스로 깔끔하게 끝나지만, 그 분류 안에는 위상적으로 잘못된 메시를 만들 수 있는 케이스가 숨어 있다. Dürst가 1988년에 처음 지적했고, 그 이후 30년 동안 수많은 변종 논문이 이 자리를 두드렸다. 핵심 케이스는 네 자리 — 6, 10, 12, 13 — 이다.

Case 6 — 면(face) 모호성

한 큐브의 어떤 한 면(face)에서, 그 면의 4 꼭짓점이 대각선으로 안-밖이 갈리는 패턴이 나타나면 면 모호성이 발생한다. 그 면을 가로지르는 등치선을 두 가지 합법적인 방식으로 그릴 수 있고, 이웃 큐브의 같은 면에서 어느 쪽을 골랐는지와 어긋나면 두 큐브 사이의 메시에 구멍이 뚫린다.

[IMAGE 11a — 면 모호성 (Case 6) (SVG): 같은 8버텍스 패턴(예: V1+V2 안)에서 두 가지 합법 삼각화 A·B를 좌·우 나란히. 면 가운데 점선으로 "두 합법 곡선" 강조.]

Case 6은 마칭 스퀘어의 Case D(saddle)가 3D로 올라온 직접 후예다. 해결법은 그 면의 중앙에 보간된 스칼라 값을 따로 평가해서 위상을 결정하는 asymptotic decider[등가면 테스트](Nielson & Hamann, 1991)다. 같은 결정 함수를 양쪽 큐브가 똑같이 적용하므로 자동으로 일관된 선택이 나온다.

Case 13 — 내부(internal) 모호성과 dual surface

Case 13은 더 까다롭다. 큐브의 8 꼭짓점이 대각선 쌍으로 안-밖이 갈리는 패턴인데, 이 경우 큐브 내부에서 등치면을 두 가지 위상으로 그릴 수 있다. 한쪽은 두 갈래 표면이 큐브를 관통하며 갈라지는 모양이고, 다른 쪽은 두 표면이 큐브 내부에서 좁은 터널로 이어지는 모양이다. 같은 안/밖 비트가 연결된 메시 vs 분리된 메시라는 완전히 다른 위상을 만든다.

[IMAGE 11b — 내부 모호성 (Case 13) (SVG): 동일 8버텍스 패턴(대각 쌍)에서 좌측은 두 표면 분리, 우측은 좁은 터널로 연결. "dual surface" 라벨.]

이 dual surface 문제를 가장 정직하게 다루는 길은 큐브 내부 중심의 보간된 스칼라 값까지 동원해서 위상을 결정하는 것이고, Asymptotic Decider의 확장 버전 또는 Nielson의 "MC33"이라 불리는 33케이스 확장 분류가 표준 해법이다(원래 15 케이스 안에 모호성 케이스들을 추가 분기로 풀어 33개로 다시 묶는다). Case 10, 12는 6 / 13의 사촌으로, 같은 가족 안에서 처리된다.

Asymptotic Decider 공식 (스니펫)

면 모호성 케이스 한 자리에서 실제로 어떻게 결정하는지만 한 번 보고 가자. 한 면의 4 꼭짓점 값을 a, b, c, d(좌하·우하·우상·좌상 순)라 하면, 그 면을 가로지르는 두 등치선의 점근(asymptote) 교점에서 평가한 스칼라 값은

f_center = (a * c - b * d) / (a + c - b - d)

이고, f_center의 부호가 iso보다 크냐 작냐로 두 가지 합법 연결 중 하나를 고른다. 이웃 큐브의 같은 면도 같은 4 꼭짓점을 공유하므로 같은 값을 얻고, 결과적으로 두 큐브가 자동으로 같은 연결을 선택한다 — 추가 통신 없이 일관성이 보장되는 점이 이 방법의 우아한 점이다.

Case 13 같은 내부 모호성도 같은 아이디어를 큐브 중심으로 확장한 결정 함수로 풀린다. 디테일은 Nielson & Hamann (1991) 원논문과 MC33 분류표(Chernyaev 1995, Lewiner et al. 2003)가 표준 참고문헌이다.

수치 안정성과 퇴화 케이스

v0 == v1(앞서 언급한 0 나누기), v_i == iso(꼭짓점이 정확히 등치값 위에 있음), 그리고 한 큐브에서 여러 정점이 같은 좌표로 떨어져 퇴화 삼각형(degenerate triangle, 넓이 0)이 생기는 경우 — 이 세 가지는 어떤 마칭큐브 구현체든 한 번씩은 부딪힌다. 표준 처리는 다음과 같다.

•      v0 == v1 → t = 0.5로 폴백(또는 작은 엡실론 가드).

•      v_i == iso → 안/밖 컨벤션에 따라 한쪽으로 일관되게 분류(보통 "안"으로). 모든 큐브가 같은 규칙을 쓰면 인접 큐브 사이의 불일치가 없다.

•      퇴화 삼각형 → 메시 등록 단계에서 넓이 검사로 필터링. 또는 BVH/충돌 메시 구축 시 자동으로 무시되도록 후처리.

이 세 가지는 정확한 결정이 핵심이 아니라 모든 큐브가 같은 규칙을 따른다는 일관성이 핵심이다. 한 큐브에서 안으로 분류한 정점이 옆 큐브에서 밖으로 분류되면 그 자리에 메시 구멍이 뚫린다.

실용적으로는 게임용 절차적 지형처럼 위상이 약간 거짓말을 해도 시각적으로 큰 문제가 안 되는 자리에서는 그냥 15케이스 표를 쓰고 모호성을 무시한다. 의료 영상 / CAD처럼 정확한 위상이 중요하면 MC33 또는 그 후속 분류를 쓴다. UE 5.8 메시 테레인은 게임 쪽이라 단순한 분류면 충분한데, "두 절벽을 합치는" 자리는 사용자가 미리 SDF로 부드럽게 깔아두므로 모호성 자체가 잘 발생하지 않는다.

이웃 알고리즘 — Dual Contouring, Surface Nets

마칭큐브가 30년 넘게 표준 자리를 지킨 만큼, "마칭큐브의 약점을 노린" 사촌 알고리즘들도 여럿이다. 두 가지만 짧게 비교한다.

항목	Marching Cubes	Surface Nets (Gibson 1998)	Dual Contouring (Ju et al. 2002)
정점 위치	엣지 위 보간 교점	큐브 중심 (격자 노드의 듀얼)	큐브 내부, 헤시안 최적화
입력	스칼라 값	스칼라 값	스칼라 값 + 엣지 노멀
모호성 케이스	6/10/12/13 (해결법 별도)	거의 없음 (정점이 큐브당 1개)	거의 없음
날카로운 모서리	표현 불가 (항상 부드러움)	표현 약함	표현 가능 (날카로운 특징 보존)
구현 복잡도	낮음 (테이블 룩업)	중간	높음 (QEF 최적화)
메시 토폴로지	매니폴드 보장 어려움	항상 매니폴드	매니폴드 보장 어려움 (Manifold DC 변종 필요)

 

[IMAGE 12 — MC vs Surface Nets vs Dual Contouring (Python): 같은 sharp-corner SDF 입력에 대해 세 알고리즘의 출력 메시 와이어프레임 3개 나란히. MC는 모서리 둥글, Surface Nets는 약간 더 부드러움, DC는 모서리 보존.]

UE 5.8 메시 테레인이 MC를 쓰는 이유는 명확하다. "두 절벽을 합치기"는 모서리 보존이 핵심이 아니라 위상 변화가 부드럽게 일어나는 게 중요하다. 사용자가 만지작거리는 동안 메시가 매끄럽게 변형되는 게 보장돼야 하는 에디터 인터랙션이므로, MC의 항상-부드러운 출력이 오히려 장점이다. 날카로운 모서리는 따로 모델링하면 되고, 절벽의 자연스러운 곡면은 MC가 그대로 뽑아준다. 구현 복잡도가 낮아서 에디터 전용 베이크 코드로 깔기에도 부담이 적다.

성능 — 메모리, 병렬화, 청크 베이크

마칭큐브의 성능 특성은 한 문장으로 요약된다: 창피할 만큼 병렬화가 잘 되지만, 메모리 대역폭이 보틀넥이다.

•      연산 비용: 한 큐브당 룩업 2번(엣지 테이블 + 삼각형 테이블) + 보간 최대 12번 + 삼각형 등록 최대 5개. 분기는 거의 없고, 데이터 의존성이 한 큐브 안에 닫혀 있다.

•      메모리 비용: N³ 격자라면 스칼라 장 N³개를 들고 있어야 한다. 8버텍스 샘플링은 인접 큐브 7개와 6면을 공유하므로, 캐시 친화적인 z-order 또는 청크 단위 슬라이스 접근이 거의 필수다. 출력 메시도 케이스에 따라 한 큐브당 0~15개의 정점(중복 제거 전)이 나오므로 메모리 예약은 보수적으로 잡는다.

•      GPU 매핑: 한 큐브 = 한 스레드 그룹의 한 스레드. 텍스처 또는 SSBO에 스칼라 장을 깔고, append-buffer로 정점을 모은다. 정점 중복 제거(엣지 인덱스 → 정점 인덱스 해시)는 두 번째 패스로 처리하는 게 보통이다.

•      청크 베이크: UE 5.8 MeshPartition처럼 큰 월드를 청크로 자른 다음 청크 단위로 베이크하면 메모리 부하가 분산되고, 청크 경계에서만 정점 공유를 별도 처리하면 된다. 청크 내부는 완전 독립 처리.

[IMAGE 13 — 성능 컷 (nanobanana 일러스트): 거대한 복셀 그리드 위에 청크 단위로 마칭이 동시에 진행되는 추상 컷. 정량 데이터 아님, 분위기.]

실전 수치는 케이스에 따라 천차만별이지만, 64³ 격자의 메시화는 데스크톱 CPU 1코어에서 수 밀리초 단위, GPU에서는 마이크로초 단위로 떨어진다. 일반적인 게임 엔진에서 에디터 베이크 단계의 비용은 거의 무시할 만하다. 런타임 동적 편집이 부담스러운 이유는 메시 자체보다도 충돌 메시 재구성 + GPU 리소스 업로드 + LOD 재계산같은 후속 비용이 누적되기 때문이다.

정점 중복 제거 — 엣지 인덱스 해시

한 큐브 한 큐브가 독립적으로 처리되면, 두 인접 큐브가 공유하는 같은 엣지 위에 같은 보간 교점이 두 번 등록된다. 좌표가 동일하다는 게 보장돼 있으니 좌표 비교로 중복을 제거할 수도 있지만, 부동소수점 비교는 위험하다. 표준적인 트릭은 엣지 한 개를 전역적으로 식별하는 정수 키를 만들어서 그 키 → 정점 인덱스 해시를 들고 다니는 것이다.

// 엣지의 두 끝 격자 인덱스 (a, b) — 항상 a < b로 정렬

edgeKey = pack3(min(a, b)) * SHIFT + pack3(max(a, b))

if edgeKey in cache: reuse cache[edgeKey]

else: cache[edgeKey] = registerVertex(p)

GPU 구현은 보통 두 패스로 푼다 — 첫 패스에서 각 엣지 위에 정점을 후보로 등록(activeEdge 마스크 + prefix sum), 두 번째 패스에서 그 정점 인덱스를 참조해 삼각형 인덱스 버퍼를 만든다. 한 패스 안에서 모든 걸 끝내려면 atomic 연산이 필요한데, atomic이 비싸므로 두 패스 분리가 보통 더 빠르다.

청크 경계 처리 — UE5.8 MeshPartition의 자리

청크 단위 베이크가 가장 까다로워지는 자리는 청크 경계다. 두 청크가 공유하는 엣지 위 정점이 양쪽에서 같은 좌표여야 하고, 그 정점에 연결되는 삼각형들이 두 청크에서 모순 없이 만나야 한다. 표준 해법은 청크 그리드를 한 칸 겹쳐서(overlap = 1) 베이크하고, 두 번째 패스에서 경계 정점을 stitching하는 것이다. UE 5.8 MeshPartition이 청크를 자르는 방식도 결국 이 패턴 위에 서 있다 — 한 청크 안은 완전 독립이고, 청크 사이의 일관성은 별도 패스가 책임진다.

이 분리 덕분에 청크 베이크는 독립적이고 병렬화 가능한 N개의 작은 베이크 + 결정론적인 stitching 한 번으로 분해된다. 큰 월드도 청크 단위로 점진 베이크가 가능하고, 사용자가 한 영역을 편집한 결과가 다른 영역으로 새지 않는다.

이 챕터 요약

단계	무엇	자료구조
1. 분류	8버텍스 안/밖 → 8비트 정수	cubeIndex ∈ [0, 256)
2. 엣지 마스크	어느 엣지가 활성인가	edgeTable[256] → 12-bit mask
3. 보간	활성 엣지 위 교점 위치	t = (iso-v0)/(v1-v0)
4. 삼각형 트리플	활성 엣지 인덱스로 삼각형 구성	triTable[256][16]
5. 모호성 해결	면/내부 dual surface 결정	asymptotic decider, MC33
6. 누적	격자 전체에서 메시 합성	per-cube 독립

 

마칭큐브가 30년 넘게 표준 자리를 지킨 이유가 이 표 안에 모두 들어 있다. 6단계 중 5단계가 룩업과 산술이고, 한 단계(모호성 해결)만 분기를 요구하는데 그마저도 입력을 SDF로 정규화하면 사실상 우회된다. 알고리즘 자체의 단순함이 후속 30년의 모든 변종이 "그래도 결국 돌아오는" 기준점을 만들었다.

이제 마칭큐브가 한 큐브 안에서 무슨 일을 하는지를 끝까지 따라왔다. 8비트 인덱스 한 번 만들고, 두 장의 표를 한 번씩 조회하고, 최대 12개 엣지에서 선형 보간을 한 번씩 돌리면 한 큐브의 메시 기여분이 결정된다. 격자 전체에 이 절차가 독립적으로 일어나니 GPU로 옮기든 청크로 베이크하든 자유다. 다음 챕터에서는 이 알고리즘이 UE 5.8 메시 테레인의 "두 절벽 붙이기" 흐름에서 정확히 어느 자리에 박혀 있는지를 본다 — 추상 절차가 엔진 코드로 응결되는 한 자리를 확인하는 것이다.