Um reale Objekte mit der Hilfe von Computern darstellen zu können, werden sie mit einem 3D Laser Scanner abgetastet. Das Ergebnis eines solchen Vorgangs ist eine „Punktwolke“ – eine Menge von Punkten, die an der Oberfläche des gescannten Objekts liegen. Diese Punkte reichen oftmals für die räumliche Darstellung nicht aus. Man braucht eine „Oberfläche“, um z. B. die Texturen bzw. Schattierungen zu sehen. Dafür sind Dreiecksnetze gut geeignet, da Dreiecke geometrisch gut zu handhaben sind. Solche Dreiecksnetze werden auch von der meisten Grafikkarten hardwareseitig unterstützt, so dass die Darstellung und Manipulation in Echtzeit möglich ist. Es gibt inzwischen viele Algorithmen, die eine solche Triangulierung (Erstellung eines Dreiecksnetzes aus einer Punktmenge) ausführen.

Einer der Triangulierungsalgorithmen – nämlich der so genannte „Ball-Pivoting Algorithm“ von Bernardini et. Al (Siehe http://www.research.ibm.com/vistechnology/pdf/bpa_tvcg.pdf) wurde im Rahmen dieser Arbeit implementiert. Um das Ergebnis (Dreiecksnetz) zu speichern wurde auch eine spezielle Datenstruktur „PolyMesh“ entwickelt. Diese Datenstruktur basiert auf sogenannten „Halbkanten“ und stellt einige Methoden bereit, die die Manipulation des Dreiecksnetzes vereinfachen. Es wurde auch eine Exportmöglichkeit in das weit verbreitete VRML-Format implementiert.

Der Ball-Privoting-Algorithmus (kurz: BPA) funktioniert nach folgendem Prinzip: Man stelle sich eine Kugel vor, die über die Oberfläche der Punktwolke „rollt“. Die Kugel muss dazu groß genug sein, um nicht zwischen den Punkten hindurch ins Innere des Objekts zu fallen. Diese Kugel fällt nun immer in eine kleine Mulde, wenn sie an genau drei Punkten aufsitzt. Rollt man sie weiter, liegt sie während den Rollen immer auf zwei der drei Punkte auf. Anschließend fällt sie über diese zwei Punkte hinweg in eine neue Mulde, wo sie wieder auf drei Punkten aufliegt, nämlich auf den zweien, über die sie hinweggerollt wurde und auf einem neuen Punkt. So wird unsere imaginäre Kugel über die gesamte Punktwolke gerollt. Alle Tripel von Punkten, auf denen die Kugel dabei zu liegen kommt, werden zu einem Dreieck verbunden. Der Fall, dass die Kugel auf mehr als 3 Punkten liegt wird separat behandelt. Auf diese Weise ergibt sich ein Dreiecksnetz, das die Oberfläche des Objekts approximiert.

Zuerst wird ein „passendes“ Dreieck (genannt „Startdreieck“) gesucht. Falls ein solches gefunden wird, wird die Kugel über seine Kanten „gerollt“. Zwei „neue“ Kanten der dazugekommenen neuen Dreiecke werden am nächsten Schritt als „Kantenfront“ genommen. Auf diese Weise breitet sich die Kantenfront bei jedem Schritt weiter über die Punktwolke aus. Es wird so weit iteriert, bis es keine Kanten mehr gibt, worüber die Kugel noch gerollt werden kann. Danach wird ein neues Startdreieck gesucht und von dem ausgehend trianguliert, bis es kein gültiges Startdreieck gibt.

Eine der Ziele der Arbeit war auch eine Aufgabe für das Praktikum am Institut für Betriebs- und Dialogsysteme zu erarbeiten, wobei das einfache Verständnis und Lesbarkeit des Quellcodes eine der wichtigsten Schwerpunkte war.
Das Programm verwendet die Bibliotheken von Java 3D (siehe http://java.sun.com/products/java-media/3D/).