Im Rahmen dieser Studienarbeit wurde der sogenannte "Ball-Pivoting Algorithm" (BPA) von Bernardini et al, der zur Rekonstruktion von Oberflächen aus Punktwolken mittels Dreiecksnetzen dient, implementiert und mit einem weiteren Algorithmus verglichen, dem Algorithmus von Linsen/Preuß. Hierzu wurde das Verhalten des Algorithmus genauer untersucht und Messungen zum Laufzeitverhalten und zur Korrektheit durchgeführt.

Schon in der Implementierungsphase stellte sich heraus, dass der BPA auf Grund seiner Konzeption bei bestimmten Punktkonstellationen Fehler verursacht. Solche Fehler können sowohl bei einem einzelnen Durchlauf als auch bei mehreren Durchläufen des BPA auftreten. Diese Fehler werden in der vorliegenden Implementierung abgefangen, ohne dass dies gravierende Auswirkungen auf die Laufzeit verursacht. Im Vergleich mit dem Algorithmus von Linsen/Preuß lieferte der BPA die qualitativ besseren Triangulationen, insbesondere neigte der BPA mit den vorgenommenen Ausbesserungen nur in Ausnahmefällen zu topologischen Fehlern in einer Triangulation. Bei der Messung der Laufzeit schnitt der BPA meist schlechter ab als der Algorithmus von Linsen/Preuß, war in Ausnahmefällen aber auch schneller.

Die Ergebnisse der durchgeführten Messungen zeigt die unten aufgeführte Tabelle. Als Testsystem wurde ein Rechner mit einem Intel Pentium II 400MHz Prozessor und 384MB Hauptspeicher unter der Linux-Distribution SuSE Linux 7.3 der SuSE Linux AG verwendet.