| 마칭 큐브 Marching Cubes | |
|---|---|
| 분야 | 컴퓨터 그래픽스 × 수치해석 |
| 목적 | 스칼라장에서 등가면(isosurface) 추출 |
| 발표 | 1987년 (Lorensen & Cline) |
| 핵심 자료구조 | 256(→15) 케이스 룩업 테이블 |
| 대표 응용 | 의료영상(CT/MRI), 유체 표면, SPH/레벨셋 렌더링 |
1. 개요[편집]
마칭 큐브(Marching Cubes)는 3차원 스칼라장(scalar field)에서 특정 등가값을 갖는 표면, 즉 등가면(isosurface)을 삼각형 메시로 추출하는 알고리즘이다. 공간을 정육면체 격자로 채운 뒤, 각 정육면체(cube)를 하나씩 “행진하듯이” 훑으며 그 안을 등가면이 어떻게 관통하는지 판정하고 삼각형 조각을 만들어 붙인다. 이름의 “마칭”이 바로 이 순회를 가리킨다.
입력은 격자점마다 정의된 스칼라값 와 등가값(isovalue) 다. 우리가 원하는 건 를 만족하는 표면. CT 데이터라면 는 밀도값이고 는 “뼈로 취급할 경계값” 같은 것이 된다. 연속 함수의 등위면을 이산 격자 위에서 근사 복원한다는 점에서, 마칭 큐브는 사실상 3D판 등고선 그리기1다.
2. 알고리즘 원리[편집]
핵심 아이디어는 놀랄 만큼 단순하다. 정육면체의 8개 꼭짓점 각각은 등가값 보다 크거나(안쪽) 작다(바깥쪽). 즉 꼭짓점마다 0/1 두 상태만 가지므로, 한 정육면체의 상태 조합은 가지다.
각 꼭짓점의 안/밖 상태를 비트로 모으면 0~255 사이의 인덱스가 하나 나온다. 이 인덱스로 미리 계산해 둔 삼각형 룩업 테이블을 조회하면, 그 정육면체 안에 몇 개의 삼각형을 어느 모서리(edge) 위에 만들어야 하는지가 바로 튀어나온다. 표면이 지나가는 모서리는 양 끝 꼭짓점의 부호가 다른 모서리들뿐이다.
교점의 정확한 위치는 위처럼 두 꼭짓점 값 사이를 선형 보간해서 정한다. 단순히 모서리 중점을 찍는 것보다 훨씬 매끈한 표면이 나온다. 각 정점의 법선(normal)은 스칼라장의 기울기를 중앙 차분으로 구해 보간하면 셰이딩까지 공짜로 얻는다.
3. 256에서 15로[편집]
256가지를 전부 손으로 다룰 순 없다. 다행히 대칭성을 활용하면 확 줄어든다. 정육면체의 회전(24가지)과 안/밖 반전 대칭을 적용하면, 본질적으로 서로 다른 구성은 15가지 기본 케이스로 압축된다.2 원 논문의 그 유명한 “15개 케이스 그림”이 바로 이것.
실무 구현은 15개를 직접 쓰기보다, 15개에서 회전·반전으로 파생된 256개짜리 완전한 룩업 테이블(triTable)을 상수 배열로 박아 둔다. 런타임에는 분기 없이 배열 인덱싱만 하면 되니 캐시 친화적이고 빠르다. GPU 지오메트리 셰이더나 컴퓨트 셰이더로 옮기기도 좋아서, 실시간 파티클 시스템 표면화에도 자주 쓰인다.
4. 모호성 문제[편집]
마칭 큐브의 원죄는 **모호성(ambiguity)**이다. 정육면체 한 면(face)에서 대각선으로 마주 보는 두 꼭짓점이 안쪽이고 나머지 둘이 바깥쪽인 경우, 표면을 잇는 방법이 두 가지 존재한다. 어느 쪽을 고르냐에 따라 인접 정육면체와 표면이 어긋나 **구멍(hole)**이 뚫린다. 초기 논문이 이 문제를 간과한 탓에, 90년대 초 마칭 큐브로 뽑은 메시에는 미세한 구멍이 숭숭 뚫려 있는 게 국룰이었다.
해결책으로 여러 후속 기법이 나왔다.
- 점근 결정자(asymptotic decider) — 면 내부 값을 쌍곡선으로 근사해 위상학적으로 올바른 연결을 고르는 방법.3
- Marching Tetrahedra — 정육면체를 애초에 5~6개 사면체로 쪼개면 모호성 자체가 사라진다. 대신 삼각형 수가 늘어난다.
- Dual Contouring / Surface Nets — 정점을 셀 내부에 두어 날카로운 모서리(sharp feature)까지 살린다.
5. 응용[편집]
마칭 큐브가 가장 빛나는 무대는 단연 의료영상이다. CT/MRI 볼륨 데이터에서 뼈·장기·종양의 3차원 표면을 뽑아 수술 계획에 쓰는 것이 대표 사례. 알고리즘이 처음부터 의료영상 재구성을 겨냥해 개발되었다는 사실이 이 궁합을 잘 말해 준다.
시뮬레이션 쪽에서는 SPH나 FLIP-PIC 유체 같은 입자 기반 유체의 자유표면을 렌더링할 때 필수다. 입자 위치에서 밀도장이나 부호거리장(SDF)을 격자로 샘플링한 뒤, 그 위에 마칭 큐브를 돌리면 물방울처럼 매끈한 표면이 나온다. 레벨셋 기반 유체 시뮬레이션의 표면 추출, 지형·복셀 게임(마인크래프트류의 부드러운 지형)의 매시화, 레이 트레이싱 전 단계의 지오메트리 생성에도 폭넓게 쓰인다. 요컨대 “격자에 담긴 스칼라값을 눈에 보이는 껍데기로 바꿔야 할 때” 가장 먼저 꺼내 드는 카드다.