Marching Cubes

• Categoria: Sensing › 3D maps & reconstruction
• Tag: mesh-extraction, 3d-reconstruction, geometry, mapping, isosurface

Un algoritmo che estrae una mesh triangolare di una superficie da una griglia 3D di valori scalari, come un campo di distanza con segno, elaborando la griglia un cubo alla volta.

Definizione

Marching cubes trasforma un campo scalare volumetrico in una mesh poligonale di uno dei suoi insiemi di livello, chiamato isosuperficie. William Lorensen e Harvey Cline lo pubblicarono al SIGGRAPH nel 1987 per costruire superfici a partire da esami medici come la tomografia computerizzata (CT) e la risonanza magnetica (MRI). Oggi è il modo standard per ottenere una mesh da una mappa a campo di distanza con segno troncato (TSDF), da una griglia di occupazione o da un campo neurale.

L'algoritmo visita ogni cubo formato da otto campioni vicini della griglia. Ogni vertice del cubo viene classificato come interno o esterno confrontandone il valore con l'isolivello, che è zero per un campo di distanza con segno. Otto vertici binari danno 256 configurazioni, che la simmetria riduce a un piccolo insieme di casi base (15 nell'articolo originale); una tabella di lookup indica poi quali spigoli del cubo la superficie attraversa e come unire gli attraversamenti in triangoli. La posizione di ogni vertice della mesh lungo uno spigolo attraversato si trova per interpolazione lineare tra i valori dei due vertici del cubo, quindi i vertici sono collocati più finemente del passo della griglia. Le normali alla superficie si ricavano di solito dal gradiente del campo.

Il metodo ha limiti noti. Alcune configurazioni dei vertici sono ambigue, e la tabella dei casi originale può lasciare buchi tra cubi vicini; varianti successive come l'asymptotic decider e Marching Cubes 33, o il metodo affine marching tetrahedra, risolvono il problema. Spigoli e angoli vivi vengono arrotondati, ed è per questo che il dual contouring e metodi simili, che usano l'informazione del gradiente, sono preferiti quando contano i dettagli netti. Dettaglio e dimensione della mesh seguono la risoluzione della griglia: per un campo neurale, la rete va prima valutata su una griglia densa, e la mesh risultante non può essere più dettagliata di quella griglia.

Perché è importante

I sistemi di mappatura e i modelli di scena appresi memorizzano la geometria come campi, mentre strumenti di visualizzazione, motori fisici, verificatori di collisione e software CAD si aspettano mesh. Il marching cubes è il ponte abituale tra i due, quindi la sua risoluzione e i suoi artefatti determinano direttamente le mesh con cui i robot pianificano e simulano.

Applicazioni principali

• Estrazione di mesh da mappe TSDF nella mappatura densa con RGB-D e lidar
• Conversione di campi neurali di distanza con segno o di occupazione in mesh
• Costruzione di mesh di collisione per la simulazione a partire da scansioni 3D
• Valutazione della qualità della ricostruzione rispetto a mesh di riferimento (ground truth)
• Ricostruzione di superfici da scansioni volumetriche mediche e industriali

In pratica

Un team che esegue mappatura densa su un robot mobile fonde i fotogrammi di una telecamera di profondità in una TSDF con una dimensione del voxel di pochi centimetri. Invece di rigenerare la mesh dell'intera mappa dopo ogni fotogramma, esegue il marching cubes solo sui blocchi i cui valori sono cambiati e invia in streaming la mesh risultante a uno strumento di visualizzazione per l'operatore. Alla fine di una sessione la mesh completa viene estratta, semplificata con la decimazione e caricata in un simulatore come mesh di collisione statica. I buchi nella mesh indicano di solito spazio non osservato o troncamento nella TSDF, più che un difetto del marching cubes in sé.

Idee sbagliate comuni

• Il marching cubes ricostruisce una superficie direttamente da punti grezzi — ha bisogno di un campo scalare su una griglia; i punti vanno prima fusi in una TSDF, in una griglia di occupazione o in una funzione implicita
• La mesh non può essere più accurata della dimensione del voxel — i vertici vengono interpolati lungo gli spigoli dei cubi, quindi il posizionamento è più fine della griglia, anche se i dettagli più piccoli di un voxel vanno comunque persi
• Il marching cubes produce sempre mesh chiuse (watertight) — la tabella dei casi originale ha casi ambigui che possono lasciare buchi, e la superficie resta aperta ovunque il campo sia troncato o non osservato
• Gli spigoli vivi escono vivi — il metodo arrotonda gli angoli; il dual contouring e metodi affini si usano quando contano i dettagli netti

Chi dovrebbe saperlo

• Ingegneri della percezione che costruiscono mappe 3D dense da sensori di profondità
• Ingegneri di simulazione che creano mesh di collisione da scansioni
• Ricercatori che lavorano con rappresentazioni implicite neurali della geometria

Tecnologie correlate

• Campo di distanza con segno troncato (Truncated Signed Distance Field, TSDF)
• Dual Contouring
• Marching Tetrahedra
• KinectFusion
• Open3D
• scikit-image

Termini correlati

• Signed Distance Field
• Neural Implicit Representation
• Point Cloud
• SLAM
• Octree
• Neural Radiance Field

Progetti correlati

• 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)

Video

• Coding Adventure: Marching Cubes: Sebastian Lague
• Mesh from Math - The basics of Marching Cubes: Deadlock

Wikipedia

• Marching cubes