11 3D-Graphik: Sichtbarkeit
Die Komplexität des Problems der Entfernung
verdeckter Kanten (engl. Hidden-Line Removal) bzw. verdeckter Flächen (engl.
Hidden-Surface
Removal) hat zu einer Vielzahl von unterschiedlichen Lösungen geführt.
Die entwickelten Verfahren lassen sich grob in drei Gruppen einteilen:
- Objektraum-Verfahren
- Bildraum-Verfahren
- Hybride Verfahren
Objektraum-Verfahren
arbeiten im Weltkoordinatensystem der jeweiligen
Problemstellung und vergleichen Objekte bzw. Objektteile untereinander, um die
Sichtbarkeit zu
bestimmen Üblicherweise liefern diese Verfahren Ergebnisse, die in ihrer
Genauigkeit der Rechengenauigkeit entsprechen. Daraus ergibt sich der Vorteil,
dass sich die berechneten sichtbaren Teile beliebig vergrößert darstellen
lassen.
Bildraum-Verfahren
arbeiten im Gerätekoordinatensystem und entscheiden
für jeden einzelnen Bildpunkt, welches Objekt sichtbar ist. Die Genauigkeit der
Berechnung entspricht dabei der Geräteauflösung. Bei Vergrößerung der
berechneten Darstellung lassen sich in der Regel keine akzeptablen Ergebnisse
erzielen (Rastereffekte, Aliasing).
Objektraum-Verfahren :
Backface-Culling
Es werden die Polygone entfernt, die vom Augenpunkt
(virtuelle Kamera) wegzeigen.
Bemerkungen:
Die zu entfernenden Polygone sind über ihren Normalenvektor (Vektor, der
senkrecht auf der Polygonebene steht) identifizierbar, wenn angenommen wird,
dass er bezüglich des Polyeders nach außen zeigt. Dann sind alle Polygone zu
entfernen, deren Normalenvektor mit der Blickrichtung einen Winkel zwischen -90°
u. 90° bilden.
Objektraum-Verfahren :
Brute-Force-Algorithmus
Für ein Polygon SP werden die sichtbaren Teile
berechnet, indem es sukzessive gegen die anderen Polygone geclippt wird. Dazu
wird für jedes Polygon VP eine Pyramide bestimmt, die durch den Augenpunkt und
das Polygon selbst definiert ist. Teile des Polygons SP sind unsichtbar, wenn
sie sich im Inneren der Pyramide befinden und bzgl. des Augenpunktes hinter VP
liegen. Ein Polygon wird an der Pyramide geclippt, indem es an der jeder
Seitenfläche (bzw. der zugehörigen Ebene) der Pyramide geclippt wird.
Bildraum-Verfahren :
Tiefenpuffer-Algorithmus
u Annahme:
u Für jeden Bildpunkt kann ein Tiefenwert (z-Wert) berechnet werden.
u Vorgehensweise:
u Die Polygone der Szene werden nacheinander auf die Bildebene
projiziert und verrastert.
u Für jeden Bildpunkt eine Polygons wird seine Entfernung zum
Augenpunkt (Tiefeninformation) bestimmt und mit dem für den
Bildpunkt bereits gespeicherten Tiefenwert verglichen.
u Ist seine Tiefe geringer, wird diese dem Bildpunkt zugewiesen und
dieses Polygon als an diesem Bildpunkt sichtbar vermerkt.
u Die Sichtbarkeitsinformation und die Tiefeninformation werden jeweils
in einem zweidimensionalen Feld mit der Auflösung des Viewports
abgelegt.
Hybride Verfahren :
Prioritätslistenverfahren
Mischung aus Objektraum- und Bildraum-Verfahren Die Polygone der Szene werden im
Objektraum nach abnehmender Entfernung zur virtuellen Kamera sortiert (Aufbau
der Prioritätsliste) Das Sichtbarkeitsproblem wird im Bildraum durch Darstellung
der Polygone in der Reihenfolge der
Prioritätsliste gelöst. Die Bildpunkte entfernt liegender Polygone werden durch
davor liegende Polygone überschrieben.
Hybride Verfahren : Painter‘s
Algorithmus
Sortieren der Polygone nach dem Abstand zur Kamera Ausgabe der Polygone von
hinten nach vorne
Problem:
Bei zyklischer Verdeckung ist die Darstellung nicht korrekt
Hybride Verfahren : Binary Space
Partition (BSP)
Aufbau einer Raumzerlegung in Form eines binären
Suchbaumes (BSP-Baum) in einem Vorverarbeitungsschritt Der BSP-Baum erlaubt es
dann, für jede Projektion (Position der Kamera) schnell eine Reihenfolge für die
Darstellung der Polygone zu finden, so dass die Verdeckung korrekt ist. Das
Verfahren eignet sich besonders für statische (sich nicht verändernde) Szenen,
die aus verschiedenen Blickrichtungen betrachtet werden.
Normalenvektor Berechnen
Der Normalenvektor n eines Polygons lässt sich aus
drei nicht kollinearen (auf einer gemeinsamen Gerade liegenden) Punkten p, q,
und r mit dem Kreuzprodukt berechnen:
n=(q-p)x(r-p)
OPENGL
OpenGL bietet zwei Verfahren zur Entfernung
verdeckter Flächen
Backface-Culling
Tiefenpuffer-Algorithmus