In dieser Praktikumsaufgabe geht es darum, ein 3D Dreiecksnetz aus Punktwolken zu rekonstruieren. Dabei verfolgen wir den Ansatz, den wir in der Vorlesung Modellierung 1 (Sommersemester 2020) kennengelernt haben.
Schauen Sie sich das Video “22 - Fortgeschrittene Variationsrechnung” aus der Vorlesung Modellierung 1 nochmal an. Die Erklärung der Rekonstruktionsmethode(n) finden Sie in dem Abschnitt 1h:20min - 1h:32min.
Wie in den Übungen zur Modellierung 1 behandelt, schreiben Sie Code, der Dreiecksnetze in Ihr Program einlädt und darstellt. Stellen Sie damit den Stanford Bunny aus dem Stanford 3D-Scanning-Repository dar. Achten Sie darauf, die Dreiecksnormalen richtig einzulesen und für die Schattierung der Flächen zu benutzen.
Tasten Sie nun den Bunny mit zufälligen Punkten ab, die gleichverteilt von der Oberfläche gezogen werden. Dabei soll jedem Punkt die 3D Koordinate sowie die Normale des zugehörigen Dreiecks zugeordnet werden (ein Punkt besteht also aus zwei 3D Vektoren, bzw. aus 6 Zahlen). Die Normalen können dabei auch durch Interpolation benachbarter Dreiecke verfeinert werden. Stellen Sie auch dies in 3D mit Ihrem Viewer dar.
Implementieren Sie das in dem Vorlesungsvideo beschriebene Implicit Moving-Least-Squares (IMLS) Verfahren, um aus der 3D Punktwolke, eine Signed Distance Function (SDF) zu berechnen, die in der Nähe der Stichprobenpunkte definiert ist. Visualisieren Sie Ihre Rekonstruktion in geeigneter Weise (z.B. mit 2D Schnitten durch das 3D Volumen).
Benutzen Sie danach das Marching Cubes Verfahren (Code unbedingt aus dem Netz besorgen und nicht selbst implementieren; es ist eine gruselige Detailarbeit, das richtig ans Laufen zu bringen), um ein 3D Dreiecksnetz zu rekonstruieren. Zeigen Sie dieses an und vergleichen Sie die Qualität mit dem Original bei verschieden hoch aufgelöster Abtastung (Sampling von 3D Punkten).
Das IMLS-Verfahren glättet scharfe Kante stark. Testen Sie dies am besten mit einem Würfel, den Sie mit Punkten abtasten. Sie können die Ergebnisse verbessern, indem Sie bei der Gewichtung der Punkte nicht nur einen Tiefpassfilter \(w(\mathbf{x}-\mathbf{x}_i)\) verwenden, sondern zusätzlich auch noch die Normalenrichtung in das Gewicht einfließen lassen, z.B. via \(w(\mathbf{x}-\mathbf{x}_i) \cdot w(\lambda \cdot (\mathbf{n}-\mathbf{n}_i))\). Damit erhält man eine Art bilateralen Filter für 3D Geometrie. Alternativ kann man auch jeden Datenpunkt mit dem reziproken des Abstandes zur gemittelten Ebene gewichten, und dann iterativ fitten. Diese \(\ell_1\)-Variante des Verfahrens ist auch als robustes IMLS bekannt.
Hinweis: Wenn man die Normalen erst selbst aus der Punktwolke (z.B. via PCA, wie im Video beschrieben) extrahieren muss, muss man natürlich darauf achten, dass diese auch entsprechend scharf sind, sonst bringt das ganze natürlich wenig. Hierzu kann man die Beiträge zur PCA ebenfalls mit einem bilateralen Filter, wie oben, gewichten, oder ein iteratively-reweighted-least-squares Ansatz nutzen, bei dem man in jedem Schritt mit dem Reziproken des Abstandes des Datenpunktes zur Ausgleichsebene gewichtet (sowohl bei der PCA wie auch bei der Interpolation).
Für unsere Aufgabe spielt die Berechnung der Normalen aus den Daten keine Rolle, da wir annehmen, dass die Normalen bereits vorliegen (wer es ausprobieren möchte, kann natürlich gerne die im Video beschriebene Normalenschätzung ergänzen).
Optional können Sie auch den Variationsansatz implementieren, der im Video am Schluss (des angegebenen Zeitintervalls) beschrieben wird (Punkt und Normalenconstraints gekoppelt mit einem Regularisierer, der zweite Ableitungen dämpft, z.B. \(\int_{\Omega}||H_f(\mathbf{x})||_F^2d\mathbf{x}\), diskretisiert auf einem 3D Gitter, mit einem schwachen Funktionsnorm-Regularisierer \(\int_{\Omega}||f(\mathbf{x})||^2d\mathbf{x}\) , damit die Randbedingungen keine invarianten Unterräume bilden). Dieser Ansatz ist deutlich aufwendiger zu realisieren, und teurer zu berechnen, ist aber auch wesentlich flexibler. Auch hier kann man robust Varianten finden; die Diskretisierung wird dann aber noch komplizierter (da ein einfaches 3D Gitter die Auflösung an sich schon zu stark einschränkt). Es ist empfehlenswert, die einfache IMLS-Version immer als erstes zu implementieren, damit man am Ende auf jeden Fall ein Ergebnis hat, und danach erst die Varitionsmethode zu probieren.
Sie sollten mindestens Aufgabenstellung 2a erfolgreich bearbeiten (2b ist eine Erweiterung von 2a, 2c ist als Alternative ausreichend, es wird aber auch hier empfohlen, zuerst 2a zu lösen). Zeigen Sie die Ergebnisse in Ihrer Abschlusspräsentation (Stanford Bunny, verschiedene Abtastungen, vielleicht auch andere Modelle). Was funktioniert gut, wo bestehen noch schwächen?