6.4.2 Objektraumalgorithmen



next up previous contents
Next: 6.4.3 Die Tiefensortierungsmethode Up: 6.4 Entfernung verdeckter Flächen Previous: 6.4.1 Bildraumalgorithmen

6.4.2 Objektraumalgorithmen

Diese arbeiten im Weltkoordinatensystem und vergleichen Objekte bzw. Objektteile untereinander, ob sie von einem gewissen Sichtvektor aus sichtbar sind. Da meist das Weltkoordinatensystem so definiert ist, daß es senkrecht aus der zweidimensionalen Bildschirmebene herausragt, wird als Sichtvektor fast immer die negative z-Achse herangezogen. Die Auflösung der Algorithmen entspricht der Maschinengenauigkeit. Daher ergeben auch lokale Vergrößerungen und Druckerausgaben bei hohen Auflösungen zufriedenstellende Ergebnissen.

Der einfachste Ojektraumalgorithmus ist Backface Culling. Für einen Sichtvektor in negativer z-Achsenrichtung wird ein orientiertes Polygon nur dann gezeichnet, wenn dessen Normalvektor einen positiven z-Anteil aufweist. Diese Methode kann jedoch nur bei konvexen Objekten angewendet werden.

Die Anwendung eines bestimmten Algorithmus hängt sehr stark von der gegebenen Applikation ab. In diesem Fall sind eine große Anzahl Polygonen (Dreiecke), die sich zum Großteil in z, x oder y-Richtung nicht überlappen, in ihrer Tiefe richtig einzuordnen. Da eine Postscript-Ausgabe und die Anzeige von Ausschnitten erwünscht sind, wurde den Objektraumalgorithmen der Vorzug gegeben.

Für die gegebenen nichtkonvexen Objekte standen zwei Methoden der Klasse der Prioriätsalgorithmen in der engeren Auswahl: Generieren der Anzeigepriorität durch binäre Raumteilungen (Binary Space Partitions) und der Tiefensortierungsalgorithmus.

Die grundlegende Idee der Binary Space Partitions Methoden ist, einen binären Baum aufzubauen, dessen Wurzel ein beliebiges Polygon aus der Polygonliste ist. Dieses orientierte Polygon wird herangezogen, um den Raum in zwei Halbräume zu teilen und allen restlichen Polygonen den linkem oder rechtem Halbraum zuzuordnen (Divide and Conquer). Alle Polygone, welche die Halbraumgrenze schneiden, werden aufgetrennt. Aus jedem Halbraum wird wieder willkürlich je ein Polygon ausgesucht, und die restlichen Polygone werden in die Baumstruktur in Ebene 2, je nach Lage links oder rechts eingehängt. Dann werden alle Polygone linksseitig der Ebene 1 wieder dem linken oder rechten Halbraum zugeordnet, und ebenso alle Polygone der rechtseitigen Baumebene 1 aufgeteilt. Wieder werden alle Polygone, die eine Halbraumgrenze schneiden, geteilt. Die Rekursion wird so lange fortgesetzt, bis alle Polygone im Baum eingetragen sind.

Kommt es zu keinen Zerteilungen von Polygonen, das ist bei einem konvexen Objekt immer gegeben, so liegt der Aufwand bei , wenn die Anzahl der Polygone ist. Bei zufällig verteilten Polygonen ist mit einem Aufwand von bei einer konstanten Anzahl von Polygonkanten zu rechnen [Mul94].

Enthält der Polygonnormalvektor einen positiven z-Anteil, dann wird der Baum von der linken unteren Ecke beginnend traversiert, und die Polygone werden nacheinander in eine Prioritätsliste gestellt oder direkt gezeichnet. Ist der z-Anteil negativ, so ist bei der rechten unteren Ecke beginnend die Prioritätsliste zu füllen.

Die primären Vorteile dieser Methode sind, daß die Prioritätsliste mit dem Aufwand n aus dem Baum generiert werden kann und bei nachträglicher Objektdrehung kein neuerlicher Aufbau der binären Baumstruktur notwendig ist.

Sind komplexe Strukturen anzuzeigen, so können viele Polygonteilungen den Aufwand stark in die Höhe treiben. Aus diesem Grund wurde eine Methode, die auf der Tiefensortierung der Polygone basiert, implementiert. Diese Methode und die Behandlung der Sonderfälle werden im folgenden Abschnitt besprochen.



next up previous contents
Next: 6.4.3 Die Tiefensortierungsmethode Up: 6.4 Entfernung verdeckter Flächen Previous: 6.4.1 Bildraumalgorithmen



Martin Stiftinger
Fri Nov 25 16:50:24 MET 1994