Marching Cubes

Kategorie: Sensing › 3D maps & reconstruction
Schlagwörter: mesh-extraction, 3d-reconstruction, geometry, mapping, isosurface

Ein Algorithmus, der aus einem 3D-Gitter von Skalarwerten, etwa einem vorzeichenbehafteten Distanzfeld, ein Dreiecksnetz einer Oberfläche extrahiert, indem er das Gitter Würfel für Würfel abarbeitet.

Definition

Marching Cubes wandelt ein volumetrisches Skalarfeld in ein Polygonnetz einer seiner Niveaumengen um, die Isofläche genannt wird. William Lorensen und Harvey Cline veröffentlichten das Verfahren 1987 auf der SIGGRAPH, um Oberflächen aus medizinischen Scans wie CT und MRT zu erzeugen. Heute ist es der Standardweg, ein Netz aus einer Karte als abgeschnittenes vorzeichenbehaftetes Distanzfeld (TSDF), einem Belegungsgitter oder einem neuronalen Feld zu gewinnen.

Der Algorithmus besucht jeden Würfel, der aus acht benachbarten Gitterabtastwerten gebildet wird. Jede Ecke wird als innen oder außen klassifiziert, indem ihr Wert mit dem Isowert verglichen wird, der bei einem vorzeichenbehafteten Distanzfeld null ist. Acht binäre Ecken ergeben 256 Konfigurationen, die sich durch Symmetrie auf eine kleine Menge von Grundfällen reduzieren lassen (15 in der Originalarbeit); eine Nachschlagetabelle gibt dann an, welche Würfelkanten die Oberfläche schneidet und wie die Schnittpunkte zu Dreiecken verbunden werden. Die Position jedes Eckpunkts entlang einer geschnittenen Kante wird durch lineare Interpolation zwischen den beiden Eckwerten bestimmt, sodass Eckpunkte feiner platziert werden als der Gitterabstand. Oberflächennormalen werden meist aus dem Gradienten des Feldes genommen.

Das Verfahren hat bekannte Einschränkungen. Manche Eckkonfigurationen sind mehrdeutig, und die ursprüngliche Falltabelle kann Löcher zwischen benachbarten Würfeln hinterlassen; spätere Varianten wie der Asymptotic Decider und Marching Cubes 33 oder das verwandte Marching Tetrahedra beheben das. Scharfe Kanten und Ecken werden abgerundet, weshalb Dual Contouring und ähnliche Methoden, die Gradienteninformation nutzen, bevorzugt werden, wenn scharfe Merkmale wichtig sind. Detail und Größe des Netzes folgen der Gitterauflösung: Bei einem neuronalen Feld muss das Netz zuerst auf einem dichten Gitter ausgewertet werden, und das resultierende Polygonnetz kann nicht detaillierter sein als dieses Gitter.

Warum es wichtig ist

Kartierungssysteme und gelernte Szenenmodelle speichern Geometrie als Felder, während Visualisierungswerkzeuge, Physik-Engines, Kollisionsprüfer und CAD-Software Netze erwarten. Marching Cubes ist die übliche Brücke zwischen beiden, daher prägen seine Auflösung und seine Artefakte direkt die Netze, mit denen Roboter planen und simulieren.

Wichtige Anwendungen

Extraktion von Netzen aus TSDF-Karten in dichter RGB-D- und LiDAR-Kartierung
Umwandlung neuronaler vorzeichenbehafteter Distanz- oder Belegungsfelder in Netze
Erstellung von Kollisionsnetzen für die Simulation aus 3D-Scans
Bewertung der Rekonstruktionsqualität gegenüber Ground-Truth-Netzen
Oberflächenrekonstruktion aus medizinischen und industriellen Volumenscans

In der Praxis

Ein Team, das dichte Kartierung auf einem mobilen Roboter betreibt, fusioniert Tiefenkamerabilder in eine TSDF mit einer Voxelgröße von wenigen Zentimetern. Statt nach jedem Bild die ganze Karte neu zu vernetzen, führt es Marching Cubes nur auf Blöcken aus, deren Werte sich geändert haben, und streamt das resultierende Netz an ein Visualisierungswerkzeug für den Bediener. Am Ende einer Sitzung wird das vollständige Netz extrahiert, durch Netzdezimierung vereinfacht und als statisches Kollisionsnetz in einen Simulator geladen. Löcher im Netz deuten meist auf unbeobachteten Raum oder Abschneiden in der TSDF hin und nicht auf einen Fehler in Marching Cubes selbst.

Häufige Missverständnisse

Marching Cubes rekonstruiert eine Oberfläche direkt aus rohen Punkten — es braucht ein Skalarfeld auf einem Gitter; Punkte müssen zuerst in eine TSDF, ein Belegungsgitter oder eine implizite Funktion fusioniert werden
Das Netz kann nicht genauer sein als die Voxelgröße — Eckpunkte werden entlang der Würfelkanten interpoliert, daher ist die Platzierung feiner als das Gitter, obwohl Merkmale, die kleiner als ein Voxel sind, dennoch verloren gehen
Marching Cubes erzeugt immer wasserdichte Netze — die ursprüngliche Falltabelle hat mehrdeutige Fälle, die Löcher hinterlassen können, und die Oberfläche ist überall offen, wo das Feld abgeschnitten oder unbeobachtet ist
Scharfe Kanten kommen scharf heraus — das Verfahren rundet Ecken ab; Dual Contouring und verwandte Methoden werden eingesetzt, wenn scharfe Merkmale wichtig sind

Wer das wissen sollte

Wahrnehmungsingenieure, die dichte 3D-Karten aus Tiefensensoren aufbauen
Simulationsingenieure, die Kollisionsnetze aus Scans erstellen
Forschende, die mit neuronalen impliziten Repräsentationen von Geometrie arbeiten

Videos

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

Wikipedia

Marching Cubes

Open Source Robotics