Einführung FaceCenterPoints Zyklenberechnung VESTA-Zyklen Triangulierung Abstandsgesetz Ergebnisse Ausblick Anwendung Quellennachweise
Diese Website präsentiert die Ergebnisse eines Fortgeschrittenen-Praktikums, das Tristan Klemm im Sommersemester 2014 am IWR der Ruprecht-Karls-Universität Heidelberg absolviert hat. Betreut wurde das Praktikum von Dr. Susanne Krömker und Andreas Beyer.
Im Rahmen des ILATO-Projekts wurde der von Bernd Schlei entwickelte VESTA-Algorithmus [1] implementiert, der dazu dient, aus einem dreidimensionalen Skalarfeld von (Dichte-)Werten eine zweidimensionale Oberfläche zu erzeugen. Die Implementation wurde mittels der Klasse ilato::surfaceExtraction realisiert, deren Verwendungsweise hier beschrieben wird.
In der 3D-Computergrafik liegen Daten oft in Form eines dreidimensionalen Gitters vor. Um die in einem solchen Gitter enthaltenen Objekte zu visualisieren, kann man sich die Techniken des Volume-Renderings zunutze machen, die simulieren, wie das Licht entlang eines Sehstrahls an den einzelnen Voxeln des 3D-Gitters absorbiert und reflektiert wird. Zwar lassen sich damit die vielfältigen Strukturen im Inneren eines Objektes und ebenso dessen Außenflächen sichtbar machen, aber wenn es darum geht, allein die Oberfläche des Objektes zu visualisieren, diese zu extrahieren, deren Geometrie zu bestimmen und in einer Datenstruktur abzuspeichern, dann ist das Verfahren des Volume-Renderings völlig ungeeignet, denn dieses Verfahren liefert schlicht keine Informationen darüber, wo Oberflächen in einem 3D-Gitter vorliegen.
Ein Algoritmus, der explizit dazu dient, diese Aufgabe - die Extraktion einer Oberfläche aus einem dreidimensionalen Skalarfeld - zu lösen, ist seit längerem unter dem Namen Marching Cubes bekannt. Bei diesem Algorithmus wandert ein Würfel sukzessive durch das Voxelgitter und prüft, ob innerhalb des Raums, den der Würfel gerade abdeckt, Oberflächenelemente eingezogen werden müssen. Der 'Marching Cube' war von 1985 bis 2005 patentiert, darf heute frei verwendet werden und liegt in unterschiedlichen - einfachen und elaborierten - Varianten vor.
Der von Bernd Schlei entwickelte VESTA-Algorithmus leistet im Prinzip dasselbe wie der 'Marching Cube', geht dabei aber anders vor: Statt auf ein festes Set an Templates zurückzugreifen, die definieren, wie in den unterschiedlichsten Fällen die Oberflächen einzuziehen sind, berechnet der VESTA-Algorithmus die Gestalt eines Oberflächenelementes erst dann, wenn er sich an dem Punkt befindet, an dem dieses Oberflächenelement eingefügt wird. Obwohl man vermuten könnte, dass dies dazu führt, dass der VESTA-Algorithmus langsamer als der 'Marching Cube' ist, ist das nicht der Fall, wie Bernd Schlei in seinem im Jahr 2012 publizierten Paper [1] gezeigt hat. Auch die im Rahmen dieses Praktikums entwickelte Implementierung bestätigt, dass Oberflächen sehr schnell berechnet werden und der VESTA-Algorithmus imstande ist, wenigstens einige kommerzielle 'Marching Cube'-Algorithmen hinsichtlich der Geschwindigkeit deutlich zu schlagen.
Ein weiterer Vorteil des VESTA-Algorithmus ist, dass er - anders als bestimmte einfache 'Marching Cube'-Implementierungen - niemals fehlerhafte Oberflächen generiert.
Wie der VESTA-Algorithmus implementiert wurde und zu welchen Ergebnissen diese Implementation geführt hat, wird im folgenden gezeigt, und zwar in diesen Schritten:
Abgeschlossen wird diese Dokumentation mit folgenden Kapiteln:
Einführung FaceCenterPoints Zyklenberechnung Vesta-Zyklen Triangulierung Abstandsgesetz Ergebnisse Ausblick Anwendung Quellennachweise
1.8.6
