Sichtbarkeitsverfahren für interaktive Bildraten

Heinrich Hey

Inhalt:

Einleitung

 Die Grafikhardware heutiger Workstations kann mittels Z-Buffer-Verfahren mehrere zigtausend gouraudschattierte texturierte Polygone pro Frame bei einer interaktiven Framerate von mindestens 10 Frames pro Sekunde darstellen.

Typische Szenerien aus den Bereichen Architektur, Spiele, Flugsimulatoren und ähnlichen enthalten aber oftmals mehrere hundertausend bis hundert Millionen Polygone, was um Größenordnungen zu viel ist, um direkt ohne zusätzliche Verarbeitung mit herkömmlichen Methoden (Z-Buffer) interaktiv gerendert werden zu können.

Rund 50 % dieses Problems lassen sich durch die Verwendung von Backface-Culling lösen (was üblicherweise auch getan wird), da dadurch schon einmal ca. die Hälfte aller Polygone eliminiert wird. Weiters läßt sich bei vielen Objekten die Anzahl der darzustellenden Polygone auch durch die Verwendung von Levels of Detail verringern. Trotzdem werden in vielen Fällen immer noch zu viele Polygone übrig bleiben, um interaktiv gerendert werden zu können.

Inhalt dieses Vortrags sind Verfahren die das Sichtbarkeitsproblem wesentlich effizienter lösen, indem sie die vom Betrachter aus unsichtbaren Teile der Szenerie in Form von jeweils möglichst großen Bereichen auf einmal ausscheiden, sodaß nur für die restlichen, zumindestens teilweise sichtbaren Polygone die exakte Sichtbarkeit, meistens per herkömmlicher Grafikhardware, ermittelt werden muß.

Klarerweise hängt die Effektivität all dieser Verfahren bezüglich der erreichbaren Interaktivität vom Grad der Verdeckungen in der Szene ab. Bei günstigen Szenerien wie z.B. in einem kleinen Raum in einem großen Haus ist nur ein sehr geringer Teil der gesamten Polygone sichtbar. Ungünstig hingegen sind z.B. große freie Plätze mit vielen kleinen Objekten, von denen nur verhältnismäßig wenige vollständig verdeckt sind.

Ein wesentliches Unterscheidungsmerkmal zwischen den Verfahren ist, ob sie sich für eine Anwendung in Echtzeit eignen bzw. speziell dafür konzipiert sind, oder ob sie als zumeist rechenzeit- und speicherintensiver Vorverarbeitungsschritt gedacht sind, sodaß danach in der interaktiven Betrachtungsphase die Menge der teilweise sichtbaren Polygone (PVS, potentially visible set) abrufbereit zur Verfügung steht. Einige der Verfahren können in beiden Kategorien angewendet werden.

Die Vorverarbeitungs-Verfahren eignen sich aufgrund ihres Zeitaufwands für statische Szenerien wie z.B. für Walkthroughs von Architektur-Modellen, sind aber gänzlich ungeeignet für sich dynamisch ändernde komplexe Objekte, wie z.B. bei der interaktiven Modellierung von Architektur-Modellen.

Bei den echtzeitmäßigen Verfahren ist es auch ein wichtiges Merkmal, wie weit sie hardwaremäßig realisierbar sind, um eine möglichst hohe Geschwindigkeit zu erreichen.

Portals

 Die Familie der Portal-Verfahren zerteilt den Raum in konvexe Zellen. Einige der Verfahren sind speziell auf Architektur-Modelle eingeschränkt und erlauben nur achsparallele rechteckige Zellen (im zwei-dimensionalen Fall) bzw. Quader-Zellen (im dreidimensionalen Fall). Die Verfahren, die sich für beliebige polygonale Szenerien eignen, verwenden im zwei-dimensionalen Fall Dreiecke und im drei-dimensionalen Fall Tetraeder.

Jede Seite einer Zelle ist entweder vollständig undurchsichtig oder enthält einen durchsichtigen polygonalen Bereich (Portal) zu einer benachbarten Zelle. Für jede Zelle ergibt sich die Menge der von ihr aus teilweise sichtbaren Zellen und damit der in ihnen enthaltenen Objekte, indem von der Zelle aus geschaut wird, durch welche Sequenzen von Portalen man durchsehen kann.

Grundsätzlich sind alle Portal-Verfahren vor allem für Szenerien geeiget, die eine möglichst abgeschlossene zellenartige Topologie besitzen, sodaß alle Sequenzen von Portalen möglichst kurz sind, also z.B. Räume und Gang- oder Röhren-Systeme.

Fast alle hier im weiteren genannten Verfahren eignen sich zur Verwendung als (speicher- und vor allem zeitintensiver) Vorverarbeitungsschritt, in dem für jede Zelle der Szenerie die Menge der von ihr aus möglicherweise sichtbaren Polygone (PVS, potentially visible set) ermittelt wird, sodaß dann während der interaktiven Walkthroughphase nur mehr geschaut werden muß, in welcher Zelle sich der Augpunkt befindet, und das PVS dieser Zelle dann abrufbereit zu Verfügung steht und somit schnell gerendert werden kann.

Einige der Verfahren sind aber auch für eine echtzeitmäßige Anwendung geeignet, wobei natürlich immer nur das PVS der aktuellen Augpunkt-Zelle bestimmt werden muß.

Ein solches echtzeitfähiges Verfahren ist das 2 1/2 D-Verfahren in [Schmalstieg, Tobler 97]. Hier wird der zwei-dimensionale Grundriß der Szenerie in Dreiecke zerteilt. Jede Kante einer Zelle ist dabei vollständig durchsichtig oder undurchsichtig (Wand). Beginnend mit der Zelle, in der sich der Augpunkt befindet, wird das Blickfeld von den undurchsichtigen Kanten der Zelle bzw. den ihnen entsprechenden Wänden entsprechend (teilweise) verdeckt. In den noch unbedeckten Blickbereichen, die auf die durchsichtigen Kanten der Zelle fallen (wo also keine Wände sind), wird rekursiv mit den an den durchsichtigen Kanten angrenzenden Zellen weitergemacht (siehe Bild 1).



Bild 1: Triangulierung der Szene und Aufteilung des Blickfeldes an den Kanten der rekursiv besuchten Zellen


Anstelle der bloßen Bestimmung des PVS und anschließendem Rendering per Hardware-Z-Buffer kann man dieses Verfahren auch direkt zum rendern ohne Z-Buffer verwenden, indem man den unverdeckten Teil einer Wand ausgibt sobald man auf sie stößt. Die Erweiterung des Verfahren auf echte 3D unter Verwendung von Tetraedern anstelle der Dreiecke erweist sich aufgrund des Clippings an den dann beliebig polygonalen Blickfeldbereichen als problematisch.

Ein weiteres Verfahren, welches die Sichtbarkeiten ausschließlich echtzeitmäßig bestimmt und in beliebigen drei-dimensionalen Szenerien funktioniert ist das in [Luebke, Georges 95]. Hierbei ergiebt jede Sequenz von Portalen eine Cull Box. Solch eine Cull Box ist der Durchschnitt der Bildraum- Bounding Rectangles der Portale. Ist der Durchschnitt leer, so existiert sicher keine Sichtbarkeit durch die Portal-Sequenz.

Um festzustellen ob ein Objekt möglicherweise sichtbar ist, wird sein Bildraum- Bounding Rectangle mit der Cull Box der Portal-Sequenz von der Augpunkt- Zelle zur Zelle, in der sich das Objekt befindet, verglichen. Liegt das Bounding Rectangle des Objekts außerhalb der Cull Box, so ist das Objekt sicher vollständig verdeckt, ansonsten ist es möglicherweise sichtbar und wird gerendert.

Da ein Objekt durch mehrere Portal-Sequenzen hindurch sichtbar sein kann, wird es beim rendern als gerendert markiert, um nicht möglicherweise noch einmal gerendert zu werden. Alternativ dazu kann das Objekt auch jeweils in die Cull Box hineingeclippt werden.

Weitere Verbesserungen sind der Z-Buffer-Test, ob die Cull Box nicht durch Objekte vollständig verdeckt ist, und die Erweiterung von Portalen auf Spiegel in denen die Sichtbarkeit umgeleitet wird.

Ein als Vorverarbeitungsphase prädestiniertes Verfahren ist das in [Airey, Rohlf, Brooks 90]. Hierbei wird das Problem der Bestimmung des PVS aller Punkte der Zelle auf das Problem der Bestimmung der von den Portals der Zelle aus sichtbaren Objekte vereinfacht, denn wenn ein Objekt von einem Punkt der Zelle aus sichtbar ist, dann muß es auch von zumindestens einem Punkt eines Portals der Zelle sichtbar sein. Dies ist dann das gleiche Problem wie bei der Sichtbarkeitsbestimmung für Radiosity und wird in [Airey, Rohlf, Brooks 90] mit Hilfe von Shadow-Volumes gelöst.

In [Teller 91] werden jeweils ausgehend von der Zelle, zu der das PVS gesucht wird, mit einer rekursiven Tiefensuche die Portal-Sequenzen ermittelt, durch die jeweils zumindestens eine Sichtbarkeitslinie existiert. Im zwei- dimensionalen Fall besteht dabei ein Portal aus seinem linken und rechten Endpunkt. Sind die Menge der linken Endpunkte und die Menge der rechten Endpunkte einer Portal-Sequenz linear trennbar (siehe Bild 2), so existiert eine Sichtbarkeitslinie durch diese Portal-Sequenz, und die durch sie erreichte Zelle ist zumindest teilweise sichtbar.



Bild 2: Sichtbarkeitslinie durch linear trennbare Portal-Eckpunkte-Menge


Existiert durch eine Portal-Sequenz hindurch keine Sichtbarkeitslinie, so wird der Rekursions-Zweig abgebrochen, da natürlich auch alle weiteren auf dieser Portal-Sequenz aufbauenden Sequenzen keine Sichtbarkeitslinie haben.

Dieses Verfahren ist auch auf 3D erweiterbar, wobei die dann polygonalen möglicherweise konkaven nicht achsparallelen Portale durch ihre achsparallelen Boundig Boxen ersetzt werden. Die dadurch auftretende Überschätzung kann durch die Zerlegung eines Portals in mehrere Teil- Bounding Boxen verringert werden.

Quake

 Ein praktisches Beispiel für die effiziente Nutzung von Sichtbarkeitsverfahren ist das 3D-Spiel Quake [Abrash 96]. Der statische Teil der Szenerie besteht dabei aus rund zehntausend großen Polygonen, die als Blätter in einem (modifizierten) BSP-Baum gespeichert sind, viel zu viel also, um von einem PC, noch dazu ohne Grafikhardware, interaktiv gerendert werden zu können. Daher wird in einem äußerst zeitaufwendigen Vorverarbeitungsschritt für jedes BSP- Blatt das PVS berechnet (selbst wieder ein BSP-Baum). Während des Spiels wird dann das PVS der Zelle, in dem sich der Augpunkt befindet, mittels Scannlining gerendert, wobei die BSP-Sichtbarkeitsreihenfolge als Tiefen-Sortierkriterium verwendet wird.

Gleichzeitig wird dabei der Z-Buffer initialisiert, der danach verwendet wird, um die dynamischen Objekte in der Szene mit korrekter Sichtbarkeit dazuzurendern.

Occluders & Occludees

 Dieses Verfahren [Coorg, Teller 96] basiert auf der Annahme, daß meistens wenige konvexe Polygone (Occluders), die nahe beim Betrachter liegen, den größten Teil des Bildes bedecken und somit den Großteil der restlichen Objekte (Occludees) in der Szene verdecken.

Der Sichtbarkeitstest der Occludees an den Occludern erfolgt mit Hilfe von Trenn- und Trägerflächen. Eine Trägerfläche wird von einem Punkt des Occludees und einer Kante des Occluders aufgespannt wobei beide Objekte auf der gleichen Seite der Trägerfläche liegen. Im Gegensatz dazu liegen bei einer Trennfläche die beiden Objekte auf verschiedenen Seiten der Trennfläche.

Hat man alle Trenn- und Trägerflächen zu einem Paar (Occluder,Occludee) so teilen diese den Raum in drei Klassen:
(1) Occludee ist nicht von Occluder verdeckt,
(2) Occludee ist teilweise von Occluder verdeckt,
(3) Occludee ist vollständig von Occluder verdeckt,
je nachdem ob der Augpunkt im Bereich zwischen den Trägerflächen (3), im Bereich zwischen den Trennflächen (2) oder außerhalb (1) ist (siehe Bild 3). Befindet sich der Augpunkt vor der Ebene des Occluder, so ist der Occludee grundsätzlich nicht von diesem Occluder verdeckt.



Bild 3: Sichtbarkeitsklassifizierung mit Trenn- und Trägerflächen


Ein Occludee wird aber oft nur durch mehrere aneinandergrenzende Occluder vollständig verdeckt (siehe Bild 4). Deshalb werden Occluder mit einer vollständig gemeinsamen Kante wie ein einzelner Occluder gehandhabt, und die Trenn- und Trägerflächen müssen nur für die Randkanten berechnet werden.



Bild 4: Verdeckung durch aneinandergrenzende Occluder


Die Occluder werden bestimmt, indem die Polygone in der näheren Umgebung des Augpunkts heuristisch auf ihre Größe im Bild geschätzt werden. Von diesen Polygonen werden dann die k besten als Occluder genommen. k wird bei [Coorg, Teller 96] fix auf 32 gesetzt.

Eben dieses fixe k ist aber der große Schwachpunkt dieses Verfahrens. Ist es so klein wie in diesem Fall, so eignet sich das Verfahren nur für Szenen in denen entsprechend wenige Polygone den größten Teil des Blickfeldes bedecken. Ist es wesentlich größer, um auch Szenen mit sehr vielen kleinen sichtbaren Polygonen handhaben zu können, wird es im Normalfall mit nicht ganz so vielen sichtbaren Polygonen ineffizient. Eine Verfahren zur automatischen Bestimmung von k ist demnach notwendig.

Das Verfahren ist zwar nicht für eine Hardware-Implementierung prädestiniert, läßt sich aber parallelisieren, indem die Sichtbarkeitstests der Occludees an die Prozessoren verteilt werden.

Regular Subdivision

 Bei diesem Verfahren [Yagel, Ray 96] wird der Raum in ein Raster von Zellen unterteilt (siehe Bild 5). Jede Zelle ist entweder leer, voll oder beinhaltet eine Oberfläche. In der Vorverarbeitungsphase wird zu jeder Zelle die Liste aller von ihr aus möglicherweise sichtbaren Zellen mit Oberflächen ermittelt. Während der Walkthroughphase müssen dann numehr die Oberflächen, die in den Zellen enthalten sind, die von der Zelle in der sich der Augpunkt befindet aus möglicherweise sichtbar sind, gerendert werden.



Bild 5: Rasterisierung und Klassifikation des Raums


Die Bestimmung der möglichen Sichtbarkeit zwischen zwei Zellen erfolgt, indem getestet wird, ob zwischen den beiden Zellen ein 8-verbundener Pfad existiert, der nur über nicht volle Zellen verläuft, die sich mit dem Korridor der beiden Zellen schneiden. Der Korridor ist die konvexe Hülle, die durch die Eckpunkte der beiden Zellen aufgespannt wird. Die Zellen, die sich mit dem Korridor schneiden, lassen sich leicht bestimmen, denn sie sind eine Teilmenge der drei Zellen breiten Bresenham-Linie zwischen den beiden Zellen (siehe Bild 6).



Bild 6: Korridor, Bresenham-Linie und Zellen entlang denen ein Sichtbarkeitspfad verlaufen kann


Die Größe der Zellen sollte weder zu groß noch zu klein sein. Ist sie zu groß, so wird die Menge der sichtbaren Zellen stark überschätzt. Ist die Größe zu klein, wird die Anzahl der Zellen und Sichtbarkeitstests und der Speicherbedarf zu groß, und der Unterschied in den Sichtbarkeiten zweier benachbarter Zellen wird sehr gering.

Dieses Problem läßt sich aber beheben, indem die Raumunterteilung nicht mit einer fixen Zellgröße, sondern Quadtree-/Octree-mäßig oder per Region Growing erfolgt, wobei die Sichtbarkeitslisten von Zellen mit einer gewissen Ähnlichkeit zusammengefaßt werden, um Speicherplatz zu sparen und somit eine höhere Auflösung bzw. wesentlich größere Szenerien ermöglicht werden.

Eine weitere Möglichkeit zur Speicherverbrauchsreduzierung besteht darin, nur die Differenzen der Sichtbarkeitslisten benachbarter Zellen zu speichern.

Bis hierher war das Verfahren ja noch äußerst zwei-dimensional. Ein drei- dimensionales Verfahren funktioniert analog dazu mit Voxeln anstelle der Zellen. Dies dürfte sich allerdings als ziemlich speicheraufwendig erweisen.

Die Walkthroughphase läßt sich beschleunigen, indem die Sichtbarkeitslisten jeweils in räumliche Oktanten unterteilt werden. Dies ermöglicht dann das Clippen mit dem Viewing-Frustum und somit das Weglassen der Objekte in den unsichtbaren Oktanten-Listen. Weiters ergibt die vorliegende Raumunterteilung eine einfache front to back-order für Depth Culling und weitere Rendering- Optimierungen.

Laut [Yagel, Ray 96] ist das Sichtbarkeitsverfahren schnell genug, um nicht nur als Vorverarbeitungsphase sondern auch echtzeitmäßig verwendet werden zu können.

Hierarchischer Z-Buffer

 Das hierachische Z-Buffer-Verfahren [Green, Kass, Miller 93] erweitert das herkömmliche Z-Buffer-Verfahren dadurch, daß eine Pyramide von Z-Buffern verwendet wird. Jede Ebene der Pyramide entspricht dabei dem gesamten Bild und hat in beiden Dimensionen die halbe Auflösung der darunter liegenden Ebene. Jeder der Z-Werte einer Ebene entspricht dabei dem entferntesten der vier von ihm bedeckten Z-Werte der darunter liegenden Ebene. Die unterste Ebene der Pyramide hat die Auflösung des Bildes, die oberste Ebene besteht aus einem einzelnen Z-Wert, der somit die größte sichtbare Entfernung im Bild darstellt.

Um nun ein Polygon darzustellen, wird sein vorderster Z-Wert beginnend mit dem Z-Wert der obersten Z-Buffer-Ebene verglichen. Ist der vorderste Z-Wert des Polygons kleiner, so wird das Polygon rekursiv mit den von ihm bedeckten darunter liegenden Quadranten der nächsten Ebene verglichen, wobei entweder für jeden Quadranten der entsprechende vorderste Z-Wert des Polygons berechnet wird, oder einfach immer der vorderste Z-Wert des gesamten Polygons verwendet wird (außer auf der untersten Ebene, um die pixelgenaue Sichtbarkeit feststellen zu können).

An den Stellen, wo das Polygon dann bis vor die entsprechenden Z-Werten der untersten Ebene reicht, wird es im Bild ausgegeben. Alternativ kann man den hierarchischen Vergleich auch nur dazu verwenden um festzustellen, ob das gesamte Polygon vollständig verdeckt ist, und falls nicht, wird es auf herkömmliche Art pixelweise gescannt (per Hardware).

Durch diese hierarchische Scan-Konversion werden verdeckte Polygonteile schon mit wenigen Z-Vergleichen großflächig als verdeckt erkannt und müssen nicht erst Pixel für Pixel verglichen werden, das Verfahren nützt somit die Bildraum-Kohärenz.

Um auch die Objektraum-Kohärenz auszunützen, kann man den hierarchischen Sichtbarkeitstest auch auf Bounding Volumes anwenden. Ist das gesamte Bounding Volume vollständig verdeckt, so sind es auch alle in ihm enthaltenen Objekte. Ist das Bounding Volume zumindestens teilweise sichtbar, so werden rekursiv die in ihm enthaltenen Objekte auf Sichtbarkeit getestet. Durch diese Methode können große verdeckte Teile der Szenerie auf einmal eliminiert werden. [Green, Kass, Miller 93] verwenden hierzu eine Octree-Raumteilung der Szene als Bounding Volume-Hierarchie.

Des weiteren läßt sich auch noch die zeitliche Kohärenz zweier aufeinanderfolgender Bilder ausnützen, indem in jedem Bild alle sichtbaren Objekte in einer Liste vermerkt werden und beim darauf folgenden Bild ohne hierarchischen Test zu allererst gescannt werden und dabei die Z-Buffer- Pyramide initialisieren. Dies funktioniert effizient unter der Annahme, daß diese Objekte mit großer Wahrscheinlichkeit noch immer sichtbar sind und den größten Teil des neuen Bildes bedecken und somit den nachfolgenden Rest der Szene verdecken.

Die hierarchische Scan-Konversion ist außerdem auch noch hervorragend geeignet, um in Hardware implementiert zu werden und läßt sich auch gut parallelisieren, indem jeder Prozessor einen Teil des Bildes unabhängig von den anderen Bildteilen und Prozessoren bearbeitet.

Literaturverzeichnis

 [Abrash 96]
M. Abrash
Inside Quake: Visible Surface Determination
(1996)
[Airey, Rohlf, Brooks 90]
J. M. Airey, J. H. Rohlf, F. P. Brooks Jr.
Towards Image Realism with Interactive Update Rates in Complex Virtual Building Environments
ACM SIGGRAPH Computer Graphics, Vol. 24, No. 2, pp. 41-50 (1990)
[Coorg, Teller 96]
S. Coorg, S. Teller
A Spatially and Temporally Coherent Object Space Visibility Algorithm
MIT Tech. Report TM-546 (1996)
[Green, Kass, Miller 93]
N. Greene, M. Kass, G. Miller
Hierarchical Z-Buffer Visibility
ACM SIGGRAPH Computer Graphics Proceedings, pp. 231-238 (1993)
[Luebke, Georges 95]
D. Luebke, C. Georges
Portals and Mirrors: Simple, Fast Evaluation of Potentially Visible Sets
ACM SIGGRAPH Symposium on Interactive 3D Graphics, pp. 105-106 (1995)
[Schmalstieg, Tobler 97]
D. Schmalstieg, R. F. Tobler
Exploiting coherence in 2 1/2 D visibility computation
to appear in: Computers & Graphics (1997)
[Teller 91]
S. J. Teller
Visibility Preprocessing for interactive Walkthroughs
ACM SIGGRAPH Computer Graphics, Vol. 25, No. 4, pp. 61-69 (1991)
[Yagel, Ray 96]
R. Yagel, W. Ray
Visibility Computation for Efficient Walkthrough of Complex Environments
Presence, Vol. 5, No. 1, pp. 45-60 (1996)
Zurück zur Virtual Reality Seminar Page.