Graphics Reference
In-Depth Information
Abb. 5.11
QuadTree zur Veranschaulichung der rekursiven Teilung
Die weitere Teilung wird beendet, wenn das nächstkleinere Quadrat die vorgege-
bene Minimalgröße für Quadrate unterschreitet oder wenn die Fläche - als Summe
aller aktiven Quadrate - hinreichend genau ermittelt ist.
Die rekursive Teilung lässt sich als Baumstruktur darstellen und wird - in der
Ebene mit Quadraten - als ‚QuadTree' bezeichnet. Abbildung
5.11
veranschaulicht
dies für die ersten vier Teilungen obiger Kurve.
Für den dreidimensionalen Raum liegt es nahe, anstatt Quadrate Würfel zu ver-
wenden. Die weitere Prozedur ist ganz analog zur Unterteilung einer zweidimensio-
nalen Ebene in Quadrate. Im folgenden Beispiel umschließt zu Beginn ein entspre-
chend großer Würfel das ganze Objekt. Dieser Würfel wird dann in alle drei Rich-
tungen halbiert, sodass sich acht gleichgroße Teilwürfel ergeben, wie in Abb.
5.12
dargestellt.
Alle acht Würfel werden nun wie folgt untersucht:
liegt der Würfel vollständig außerhalb des Objektes, wird er als inaktiv markiert
und nicht weiter betrachtet;
liegt der Würfel vollständig innerhalb des Objektes, wird er als aktiv markiert
und nicht weiter unterteilt;
enthält der Würfel einen Teil der Berandung wird er wieder halbiert und die sich
ergebenden acht Teilwürfel wie oben weiter untersucht.
Diese Unterteilung wird so lange fortgesetzt, bis die immer kleiner werdenden Teil-
würfel eine vorgegebene Minimalgröße unterschritten haben. Genau wie in der
Ebene führt das Verfahren zwangsläufig zu mehr oder weniger langen Teilungs-
ketten, bis die minimale Voxelgröße erreicht ist. Im Dreidimensionalen heißen die
Teilungsketten ‚OctTree' weil jetzt acht Würfel und nicht vier Quadrate entstehen.
Das ganze Objekt ist durch die Menge aller aktiven Voxel repräsentiert.
