Oberflächenrekonstruktion aus ungeordneten Punktmengen

Hoppe et al. [39] verwenden ungeordnete 3D-Punktmengen für die Gittererzeugung. Damit unterscheiden sie sich wesentlich von Turk und Levoy [81], die gerade die Struktur in den Tiefenbildern ausnutzen. Der Oberflächenrekonstruktionsalgorithmus arbeitet in zwei Schritten. Zuerst definieren Hoppe et al. eine Funktion $f: D \to \mathbbm{R}$, wobei $D \subset \mathbbm{R}^3$ die Daten sind, bzw. eine Region in der Nähe der Daten, so dass $f$ die vorzeichenbehaftete Distanz zur unbekannten Oberfläche $M$ schätzt. Der Schlüssel zur Definition der Distanzfunktion $f$ besteht darin, orientierte Ebenen mit jedem 3D-Punkt zu assoziieren. Diese sind Tangentialflächen und dienen als lokale lineare Approximationen der Oberfläche [39].

Da $Z(f)$, das Urbild von $f$, eine Schätzung für $M$ ist, benutzt der zweite Schritt einen so genannten Contour-Algorithmus (Marching Cubes) für die Approximation von $Z(f)$ durch eine einfache Fläche. Der Marching-Cube-Algorithmus legt ein feines 3D-Raster durch das Objekt und evaluiert die Distanzfunktion $f$ an den Rasterpunkten, um die Dreiecke des Gitters aus den Quadern des Rasters zu erzeugen [39].