Marching Cubes
- Catégorie: Sensing › 3D maps & reconstruction
- Mots-clés: mesh-extraction, 3d-reconstruction, geometry, mapping, isosurface
Algorithme qui extrait un maillage triangulaire d'une surface à partir d'une grille 3D de valeurs scalaires, comme un champ de distance signée, en traitant la grille un cube à la fois.
Définition
Marching cubes : algorithme qui transforme un champ scalaire volumique en un maillage polygonal de l'un de ses ensembles de niveau, appelé isosurface. William Lorensen et Harvey Cline l'ont publié à SIGGRAPH en 1987 pour construire des surfaces à partir d'examens médicaux comme le scanner (CT) et l'IRM. C'est aujourd'hui la manière standard d'obtenir un maillage à partir d'une carte en champ de distance signée tronqué (TSDF), d'une grille d'occupation ou d'un champ neuronal.
L'algorithme visite chaque cube formé par huit échantillons voisins de la grille. Chaque sommet du cube est classé comme intérieur ou extérieur en comparant sa valeur à l'isovaleur, qui vaut zéro pour un champ de distance signée. Huit sommets binaires donnent 256 configurations, que la symétrie réduit à un petit ensemble de cas de base (15 dans l'article original) ; une table de correspondance indique alors quelles arêtes du cube la surface traverse et comment relier les points d'intersection en triangles. La position de chaque sommet du maillage le long d'une arête traversée est obtenue par interpolation linéaire entre les deux valeurs aux coins, de sorte que les sommets sont placés plus finement que le pas de la grille. Les normales à la surface sont généralement tirées du gradient du champ.
La méthode a des limites connues. Certaines configurations de coins sont ambiguës, et la table de cas d'origine peut laisser des trous entre cubes voisins ; des variantes ultérieures comme l'asymptotic decider et Marching Cubes 33, ou la méthode apparentée des marching tetrahedra, résolvent ce problème. Les arêtes et coins vifs sont arrondis, c'est pourquoi on préfère le dual contouring et des méthodes similaires, qui utilisent l'information de gradient, quand les détails vifs comptent. Le niveau de détail et la taille du maillage suivent la résolution de la grille : pour un champ neuronal, le réseau doit d'abord être évalué sur une grille dense, et le maillage obtenu ne peut pas être plus détaillé que cette grille.
Pourquoi c'est important
Les systèmes de cartographie et les modèles de scène appris stockent la géométrie sous forme de champs, alors que les outils de visualisation, les moteurs physiques, les vérificateurs de collision et les logiciels de CAO attendent des maillages. Marching cubes est le pont habituel entre les deux, de sorte que sa résolution et ses artefacts façonnent directement les maillages avec lesquels les robots planifient et simulent.
Applications principales
- Extraction de maillages à partir de cartes TSDF en cartographie dense RGB-D et LiDAR
- Conversion de champs neuronaux de distance signée ou d'occupation en maillages
- Construction de maillages de collision pour la simulation à partir de scans 3D
- Évaluation de la qualité de reconstruction par rapport à des maillages de vérité terrain
- Reconstruction de surfaces à partir de scans volumiques médicaux et industriels
En pratique
Une équipe qui fait de la cartographie dense sur un robot mobile fusionne les images d'une caméra de profondeur dans une TSDF avec une taille de voxel de quelques centimètres. Plutôt que de remailler toute la carte après chaque image, elle exécute marching cubes uniquement sur les blocs dont les valeurs ont changé, et diffuse le maillage obtenu vers un outil de visualisation pour l'opérateur. En fin de session, le maillage complet est extrait, simplifié par décimation et chargé dans un simulateur comme maillage de collision statique. Les trous dans le maillage signalent généralement un espace non observé ou une troncature dans la TSDF plutôt qu'un défaut de marching cubes lui-même.
Idées reçues
- Marching cubes reconstruit une surface directement à partir de points bruts — il faut un champ scalaire sur une grille ; les points doivent d'abord être fusionnés dans une TSDF, une grille d'occupation ou une fonction implicite
- Le maillage ne peut pas être plus précis que la taille des voxels — les sommets sont interpolés le long des arêtes des cubes, donc leur placement est plus fin que la grille, même si les détails plus petits qu'un voxel sont tout de même perdus
- Marching cubes produit toujours des maillages étanches — la table de cas d'origine comporte des cas ambigus qui peuvent laisser des trous, et la surface est ouverte partout où le champ est tronqué ou non observé
- Les arêtes vives ressortent vives — la méthode arrondit les coins ; on utilise le dual contouring et des méthodes apparentées quand les détails vifs comptent
Qui devrait le savoir
- Ingénieurs en perception qui construisent des cartes 3D denses à partir de capteurs de profondeur
- Ingénieurs en simulation qui créent des maillages de collision à partir de scans
- Chercheurs qui travaillent sur les représentations implicites neuronales de la géométrie
Technologies associées
- Champ de distance signée tronqué (Truncated Signed Distance Field, TSDF)
- Dual Contouring
- Marching Tetrahedra
- KinectFusion
- Open3D
- scikit-image
Termes associés
Projets associés
- 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)
Vidéos
- Coding Adventure: Marching Cubes: Sebastian Lague
- Mesh from Math - The basics of Marching Cubes: Deadlock