Zur effizienten Bearbeitung von z.B. Kollisionsanfragen auf großen
CAD-Datenbanken wird ein Filterschritt mit einer konservativen Voxel-Approximation
vorgeschaltet.
Problemstellung
Im Rahmen dieser Projektarbeit sollen Algorithmen entwickelt und implementiert
werden, die eine gegebene Voxel-Oberfläche durch eine Menge von achsenparallelen
überlappungsfreien Quadern approximieren. Der maximale Approximationsfehler
soll über eine Funktion lokal parametrisiert werden können.
Lösungsansatz
Zur Lösung des Problems wird ein Divide-And-Conquer-Algorithmus verwendet.
Grundsätzlich möglich wäre auch ein Plane-Sweep-Verfahren.
Ziel
Ziel ist es, neben dem bereits vorhandenen Grow-Algorithmus einen Algorithmus
bereitzustellen, der Variationen in der Wahl der Splitachse, des Splitwertes
und des Approximationsfehlers ermöglicht.
Im Rahmen der Projektarbeit wurde ein Divide-Algorithmus entwickelt und
implementiert und ein gegebener Grow-Algorithmus implementiert. Für
den Divide-Algorithmus wurde der gesamte Datenraum in Gütezellen,
d.h. überlappungsfreie Würfel mit wählbarer Kantenlänge,
unterteilt. Auf diesen Gütezellen wurde ein Interface für eine
Gütefunktion definiert, die den Grenzwert angibt, wieviele Voxel des
Objektes mindestens in dieser Gütezelle liegen müssen. Dabei
sind z.B. konstante, lineare oder lokal definierte Gütefunktionen
denkbar.
Die Voxel werden in ein Java-Bitset geladen und die Bounding-Box für
das Objekt berechnet. Wenn alle Gütezellen, die die Bounding-Box enthält
oder schneidet ausreichend gefüllt sind, bricht der Algorithmus ab.
Andernfalls werden die Splitachse und der Splitwert gewählt, die Bounding-Box
entsprechend geteilt und der Algorithmus rekursiv für die beiden entstandenen
Boxen aufgerufen.
Der Grow-Algorithmus durchläuft den Datenraum in linearer Folge.
Das erste Voxel des Objekts, das der Algorithmus findet und das noch nicht
verarbeitet wurde, bildet die erste Bounding-Box. Nun versucht der Algorithmus
diese Bounding-Box in die Richtung zu vergrößern, die den größten
Volumenzuwachs bewirkt. Das wird so lange wiederholt, bis der Grenzwert
für die minimale Füllung der Bounding-Box unterschritten wird.
Danach wird der lineare Durchlauf fortgesetzt zum nächsten Voxel des
Objektes, das noch nicht verarbeitet wurde. Der Algorithmus bricht ab, wenn alle Voxel des Objektes verarbeitet wurden.
Der Vergleich beider Algorithmen hat gezeigt, das bei genauer Approximation
der Grow-Algorithmus deutlich bessere Ergebnisse liefert, der Divide-Algorithmus
hingegen mit ungenauer Approximation besser wird und darüber hinaus
die Möglichkeit bietet, durch geeignete Wahl der Splitachse, des Splitwertes,
der Größe der Gütezellen und der Gütefunktion die
Approximation an die individuellen Erfordernisse anzupassen.
Bei der Implementierung wurde kein Wert auf Optimierung gelegt. Hier
liegt noch Potential für Verbesserungen. Darüberhinaus verspricht
der Divide-Algorithmus Verbesserungsmöglichkeiten durch Verwendung
eines Merge-Schrittes, der in geeigneter Weise vorhandene Bounding-Boxen
zu größeren Boxen zusammenschließt. Nach welchen Kriterien
die Splitachse und der Splitwert ausgewählt werden sollen, kann ebenfalls
eine Möglichkeit sein, bessere Ergebnisse zu erhalten. Das Splitten
der jeweils längsten Seite scheint am erfolgreichsten zu sein, während
der 50%-Median als Splitwert gegenüber dem Mittelpunkt der Seite keine
signifikanten Vorteile hatte. Auch hier können weitere Untersuchungen
eventuell den Algorithmus verbessern.
DBS