Marching Cubes
- 카테고리: Sensing › 3D maps & reconstruction
- 태그: mesh-extraction, 3d-reconstruction, geometry, mapping, isosurface
부호 거리 필드 같은 스칼라 값의 3D 격자로부터, 격자를 한 번에 정육면체 하나씩 처리하여 표면의 삼각형 메시를 추출하는 알고리즘.
정의
마칭 큐브(marching cubes)는 부피 스칼라장을 그 등위 집합 중 하나, 즉 등가면(isosurface)의 폴리곤 메시로 바꾼다. William Lorensen과 Harvey Cline이 CT나 MRI 같은 의료 스캔으로부터 표면을 만들기 위해 1987년 SIGGRAPH에서 발표했다. 지금은 절단 부호 거리 필드(TSDF) 지도, 점유 격자 또는 신경 필드에서 메시를 얻는 표준 방법이다.
이 알고리즘은 이웃한 격자 샘플 여덟 개로 이루어진 각 정육면체를 방문한다. 각 꼭짓점은 그 값을 등위값과 비교해 안쪽 또는 바깥쪽으로 분류되는데, 부호 거리 필드에서 등위값은 0이다. 이진 꼭짓점 여덟 개는 256가지 구성을 만들고, 대칭성으로 이를 소수의 기본 경우(원 논문에서는 15개)로 줄인다. 그런 다음 조회 테이블이 표면이 정육면체의 어느 모서리를 가로지르는지, 그리고 그 교차점들을 어떻게 삼각형으로 잇는지를 알려 준다. 가로질러진 모서리 위 각 정점의 위치는 두 꼭짓점 값 사이의 선형 보간(linear interpolation)으로 구하므로, 정점은 격자 간격보다 더 세밀하게 배치된다. 표면 법선은 보통 필드의 기울기에서 얻는다.
이 방법에는 알려진 한계가 있다. 일부 꼭짓점 구성은 모호하며, 원래의 경우 테이블은 이웃한 정육면체 사이에 구멍을 남길 수 있다. asymptotic decider와 Marching Cubes 33 같은 이후 변형이나 관련 방법인 marching tetrahedra가 이를 해결한다. 날카로운 모서리와 꼭짓점은 둥글게 깎이는데, 그래서 날카로운 특징이 중요할 때는 기울기 정보를 사용하는 이중 윤곽화(dual contouring) 및 유사한 방법이 선호된다. 메시의 세밀도와 크기는 격자 해상도를 따른다. 신경 필드의 경우 네트워크를 먼저 조밀한 격자에서 평가해야 하며, 결과 메시는 그 격자보다 더 세밀할 수 없다.
중요한 이유
매핑 시스템과 학습된 장면 모델은 기하를 필드로 저장하는 반면, 시각화 도구, 물리 엔진, 충돌 검사기, CAD 소프트웨어는 메시를 기대한다. 마칭 큐브는 둘 사이의 일반적인 다리이므로, 그 해상도와 아티팩트가 로봇이 계획과 시뮬레이션에 쓰는 메시를 직접 결정한다.
주요 응용
- 조밀 RGB-D 및 LiDAR 매핑에서 TSDF 지도로부터 메시 추출
- 신경 부호 거리 필드나 점유 필드를 메시로 변환
- 3D 스캔으로부터 시뮬레이션용 충돌 메시 구축
- 참값 메시와 비교한 재구성 품질 평가
- 의료 및 산업용 볼륨 스캔으로부터의 표면 재구성
실제 사례
이동 로봇에서 조밀 매핑을 돌리는 팀은 깊이 카메라 프레임을 복셀 크기 몇 센티미터의 TSDF로 융합한다. 매 프레임 뒤에 지도 전체를 다시 메시화하는 대신, 값이 바뀐 블록에서만 마칭 큐브를 실행하고 결과 메시를 운영자용 시각화 도구로 스트리밍한다. 세션이 끝나면 전체 메시를 추출하고, 메시 단순화(decimation)로 간소화한 뒤, 시뮬레이터에 정적 충돌 메시로 불러온다. 메시의 구멍은 보통 마칭 큐브 자체의 결함이 아니라 TSDF의 관측되지 않은 공간이나 절단을 가리킨다.
흔한 오해
- 마칭 큐브는 원시 점들로부터 표면을 직접 재구성한다 — 격자 위의 스칼라장이 필요하며, 점들은 먼저 TSDF, 점유 격자 또는 암시적 함수로 융합되어야 한다
- 메시는 복셀 크기보다 더 정확할 수 없다 — 정점이 정육면체 모서리를 따라 보간되므로 배치는 격자보다 세밀하지만, 복셀보다 작은 특징은 여전히 사라진다
- 마칭 큐브는 항상 수밀한 메시를 만든다 — 원래의 경우 테이블에는 구멍을 남길 수 있는 모호한 경우가 있고, 필드가 절단되었거나 관측되지 않은 곳에서는 표면이 열려 있다
- 날카로운 모서리는 날카롭게 나온다 — 이 방법은 모서리를 둥글게 만들며, 날카로운 특징이 중요할 때는 이중 윤곽화와 관련 방법이 쓰인다
알아야 할 사람
- 깊이 센서로 조밀 3D 지도를 구축하는 인식 엔지니어
- 스캔으로부터 충돌 메시를 만드는 시뮬레이션 엔지니어
- 기하의 신경 암시적 표현을 다루는 연구자
관련 기술
- 절단 부호 거리 필드(Truncated Signed Distance Field, TSDF)
- 이중 윤곽화(Dual Contouring)
- Marching Tetrahedra
- KinectFusion
- Open3D
- scikit-image
관련 용어
관련 프로젝트
- LingBot-Map: Streaming 3D reconstruction from one camera: pose and depth for every frame, live
- Cartographer: Google's real-time 2D and 3D SLAM system for multi-platform robotics
- OpenDroneMap: Open-source photogrammetry toolkit that turns drone images into maps and 3D models
- RTAB-Map: Versatile graph-based SLAM supporting RGB-D, stereo, and LiDAR with real-time operation
- pySLAM: Hybrid Python/C++ visual SLAM pipeline with classic and deep-learning front-ends
- LeGO-LOAM: Classic lightweight, ground-optimized lidar odometry and mapping baseline (IROS 2018)
동영상
- Coding Adventure: Marching Cubes: Sebastian Lague
- Mesh from Math - The basics of Marching Cubes: Deadlock