Wie Sie einen Einstieg in das Occulsion Culling finden.

Beim Rendern von 3D-Weltbildern in einem Spiel werden Ressourcen, die für die Verarbeitung von Elementen aufgewendet werden, die für den Spieler unsichtbar sind, zwangsläufig verschwendet. Diese Ressourcen könnten besser genutzt werden, um die visuelle Komplexität der sichtbaren Elemente zu erhöhen oder die Zeit für die Erstellung eines Rahmens zu verkürzen. Dazu müssen wir die Objekte identifizieren, die für den Spieler nicht sichtbar sind. Das Bestimmen der Menge von Elementen, die aus einer bestimmten Sicht nicht sichtbar sind, weil sie von vor ihnen liegenden Elementen verdeckt werden, wird als Occlusion Culling bezeichnet.

In interaktiven Echtzeitanwendungen wird das Occlusion Culling traditionell als Rendering-Optimierungtechnik eingesetzt. Es ermöglicht die Produktion von Bildern mit einer Geschwindigkeit, die die Wahrnehmung kontinuierlicher Bewegung ermöglicht. Es gibt jedoch eine Vielzahl von Einsatzmöglichen für Sichtbarkeitsinformationen außerhalb des reinen Renderings. Zu wissen, ob ein Objekt gerade sichtbar ist oder nicht, kann vom großen Nutzen sein.

• Einfluss auf das KI-Verhalten.
• Vereinfachung oder Deaktivierung der physikalischen Simulation und Animation.
• Reduzieren Sie die Menge des Netzwerktraffics, welche erforderlich ist, um Spielerpositionen im gesamten Netzwerk zu replizieren.

Bei der Beurteilung, welchen Wert ein Occlusion Culling System besitzt, sind einige wünschenswerte Eigenschaften zu nennen:

Es funktioniert automatisch und universell.

Im Idealfall arbeitet ein Occlusion Culling System automatisch mit jeder Art von 3D-Inhalt, vom einfachen Objektbetrachter bis hin zu riesigen virtuellen Welten und erfordert keine manuelle Arbeit der Künstler, die die Spielwelt aufbauen und modellieren. Darüber hinaus sollte das System die Kreativität des Künstlers nicht einschränken. Schließlich sollte das System nicht von bestimmten Hardwaremerkmalen, Rendering-Konventionen, Autorenmethoden oder Tools abhängig sein.

Es funktioniert korrekt.

Ein System, das manchmal ganz oder teilweise sichtbare Objekte bestimmt, die vollständig eingeschlossen werden sollen, muss Rendering-Artefakte erzeugen, während ein System das manchmal vollständig geschlossene Objekte als sichtbar meldet, in der Regel die richtige visuelle Ausgabe erzeugen kann.

Es schafft Mehrwert.

Für Renderingzwecke muss das Occlusion Culling anhand der Referenzlösung beurteilt werden, bei der einfach alles im „View Frustum“ dargestellt wird. Zum Beispiel ist ein Sportspiel, das in einer Arena spielt, in der nur ein kleiner Teil der gesamten Inhaltsmenge zu einem bestimmten Zeitpunkt eingeschlossen ist, kein guter Kandidat für ein Occlusion-System. Der Aufwand für die Bestimmung der Occlusion wird verschwendet, da kein Nutzen erzielt werden kann. Wenn jedoch visuelle Komplexität und viel Detailreichtum in komplexen 3D-Welten erforderlich sind, beginnen die Vorteile eines Occlusion Systems deutlich zu steigen. In diesem Artikel stellen wir zunächst die Problem-Domain vor und werfen einen Blick auf die gängigen Methoden, die derzeit für Occlusion Culling verwendet werden und verdeutlichen die Herausforderungen, die sie im Rahmen der Spieleentwicklung darstellen. Anschließend beschreiben wir einen neuartigen Ansatz zum Occlusion Culling, der entwickelt wurde, um die Bedürfnisse unserer Partner und Kunden zu erfüllen, die die nächste Generation von Game-Engines entwickeln.

Dieser Ansatz wird als Umbra 3 Occlusion Culling System bezeichnet.

Hintergrund.

Die Wurzeln des Occlusion Culling in 3D-Grafiken liegen in Algorithmen zur Bestimmung von versteckten Linien und versteckten Oberflächen. Diese Algorithmen sind notwendig, um visuell korrekte Bilder von 2D-Projektionen in einem 3D-Raum zu erzeugen.

Das Problem ist einfach zu begreifen – von den Lichtstrahlen, die von Oberflächen in der Welt zu ihrem Auge wandern, tragen nur diejenigen zum endgültigen Bild bei, die auf dem Weg nicht auf Hindernisse stoßen. Dies ist ein Beispiel für das Sichtbarkeitsproblem und die Formulierung schlägt bereitwillig eine mögliche Lösung für die 3D-Wiedergabe vor: Wir könnten einfach die Lichtstrahlen aus dem Auge zurückverfolgen und die erste Oberfläche finden, mit der sich jeder Strahl überschneidet.

Alle modernen Polygon-Raster-Renderer, sowohl Soft- als auch Hardware-Renderer, verfolgen den kleinsten Abstandswert pro Sample und aktualisieren das Sample nur, wenn ein Abstandswert kleiner als das aktuelle Minimum ist. Diese Lösung wird als Z-Buffering oder Depth Buffering bezeichnet, für den zusätzlichen Puffer der gepflegten Z-Werte. Angesichts des bereits geleisteten Arbeitsaufwands für 2D-Projektion und Raster Samplings ist die Berechnung der Z-Komponente relativ günstig und garantiert das richtige visuelle Erlebnis. Die Berechnung kann reduziert werden, indem Primitive in einer Reihenfolge von vorne nach hinten eingeführt werden: das Rendern des nächstgelegenen Primitives für eine bestimmte Probe bedeutet, dass der Beitrag aller anderen Primitive entlang desselben Strahls durch den Depth Test abgelehnt werden kann und somit jede Berechnung zur Bestimmung der endgültigen Ausgabe einer versteckten Probe, wie z.B. das Interpolieren von Nodeattributen oder das Ausführen von Textur-Lookups, übersprungen werden kann.

Z-Buffering mit einer primitiven Rendering-Reihenfolge von vorne nach hinten kommt dem Ideal, nur einen einzigen Wert für jedes Ausgabepixel zu berechnen, ziemlich nahe. Leider findet das Culling sehr spät in der Rendering-Pipeline einer 3D-Spieleanwendung statt. An dem Punkt, an dem der Renderer eine verdeckte Probe ablehnt, hat die Probe mehrere Stufen der Grafikpipeline durchlaufen, von der Zuführung der Eingangsgeometrie und abhängiger Ressourcen zur GPU für die Per-Vertex-Verarbeitung, den Dreiecksaufbau und die Rasterung. Es gibt Methoden für das frühe Z-Culling in der Rendering-Pipeline, aber letztendlich werden die größten Einsparungen bei der Berechnung erzielt, indem die größten renderbaren Einheiten der Engines ausgewählt werden, bevor sie in das Rendering-Subsystem eingespeist werden.

Okkluder Rasterung.

Die meisten Strategien zum Entfernen von Occlusion Culling zur Laufzeit sagen aus, ob ein Objekt sichtbar ist, indem sie das Äquivalent eines probenbasierten Depth Tests für die transfomierten Grenzen potenziell verschlossener Einzelobjekte oder Objekthierarchien durchführen. Die Herausforderung besteht darin, eine Depth Buffer-Schätzung der Ansicht zu erstellen, bevor das eigentliche Rendering stattfindet.

Eine weit verbreitete Lösung ist die Verwendung eines separaten Depth-Rendering-Passes oder der Depth-Ergebnisse eines vorherigen Frames auf dem Grafikprozessor und die Verwendung von Occlusion Abfragen. Eine Occlusion Abfrage gibt die Anzahl der Samples zurück, die den Depth Test möglicherweise bestehen, ohne Pixelwerte tatsächlich zu verarbeiten oder zu schreiben. Die Herausforderung bei diesem Ansatz ist die Synchronisierung zwischen CPU und GPU, die für die Übertragung der Testdaten und die Gewinnung der Occlusion-Informationen erforderlich ist. In der Praxis ist es praktisch unmöglich, diesen Ansatz für etwas anderes als die Rendering-Optimierung zu nutzen.

Der Vorteil ist, dass keine zusätzliche Arbeit bei der Generierung des Depth Buffers anfällt und es das genaue Endbild für jede Art von Occluder Geometrie darstellt. Um den asynchronen Betrieb der CPU und des Grafikprozessors zu ermöglichen und den Datentraffic zwischen ihnen zu minimieren, verwenden dieses Systeme typischerweise die vorherigen Ergebnisse des Frame Depth Buffers und können daher keine konservative Aussortierung garantieren. Um ein konservatives Culling zu erhalten, darf die Geometrie die Rasterabdeckung das tatsächliche Ergebnis nicht überschreiten. Normalerweise erstellen die Content-Künstler diese Occlusion-Modelle manuell, Seite an Seite mit den realen Modellen.

Potentiell sichtbare Mengen (PVS).

Wenn die Laufzeitkosten für die frühzeitige Depth-Buffer-Generierung und Occlusion-Tests nicht realisierbar sind und die Occluder-Geometrie meist statisch ist, ist es eine sinnvolle Alternative, die Sichtbarkeitsbeziehungen zwischen View-Zellen und renderbaren Objekten in einer Vorverarbeitungsphase zu bestimmen und zu speichern. Der Satz von Entitäten, die aus einer Ansichtszelle sichtbar bestimmt werden, wird als potenziell sichtbarer Satz bezeichnet. Bei der Laufoperation wird einfach die Sichtzelle des aktuellen Kameraplatzes gefunden und das Set aus dem Speicher gesucht. In einfachen Fällen können die Sichtbarkeitsbeziehungen vom Leveldesigner manuell erstellt werden, aber die übliche Methode besteht darin, die Sichtbarkeit aus einer Sichtzelle entweder durch Strahlenabgabe oder Rasterung in alle Richtungen zu erfassen. Es ist schwierig, in beiden Fällen eine konservatives Culling zu gewährleisten. Durch die Erhöhung der Anzahl der Proben pro View-Zeile kann die Fehlerquote auf Kosten der für die Berechnung benötigten Zeit gesteuert werden. Zusätzlich zu den statischen Zielobjekten können im Set auch volumentrische Sichtbarkeitsinformationen in Form von Zielzellen gespeichert werden, um auch nicht-statische Objekte aussortieren zu können.

Die Generierung von potenziell sichtbaren Mengen kann automatisiert werden, aber eine große Datenmenge muss erzeugt werden, um vernünftige Selektionsergebnisse zu erzielen. Die Abtastzeit in der Vorprozessphase verlangsamt den Iterationszyklus der Inhalte und die schiere Datenmenge zur Darstellung der Sichtbarkeitsbeziehungen kann schnell überschaubar werden. Dies gilt umso mehr, als Sichtbarkeitsbeziehungen globaler Natur sind. Eine kleine Änderung der Occluder-Geometrie kann zu Veränderungen in den Sichtbarkeitsbeziehungen weit weg und auf allen Seiten der ursprünglichen Änderung führen und erfordert daher eine Neuberechnung der potenziell sichtbaren Menge eines großen Bereichs.

Portale und Zellen.

Eine dritte Kategorie von Occlusion Culling Systemen basiert auf der Aufteilung der statischen Spielwelt in Zellen und der Erfassung der Sichtbarkeit zwischen benachbarten Zellen mit 2D-Portalen. Die Laufzeitoperation besteht darin, die Zelle zu finden, in der sich die Kamera befindet und das gebildete Zelldiagramm zu durchlaufen, wodurch die Sichtbarkeit auf dem Weg eingeschränkt wird, indem das „View Frustum“ auf die durchquerten Portale geclippt wird. Objekte werden in einer Vorverarbeitungsphase Zellen zugeordnet und ihre Sichtbarkeit wird durch den Besuch der Zelle, in der sie sich befinden, bestimmt. Dieser Ansatz funktioniert am besten, wenn es weltweit offensichtliche Hotspots gibt, an denen der Leveldesigner Portale platzieren kann, wie z.B. Türen oder Fenster, die Räume in Innenräumen verbinden.

Die Portal- und Zellendaten sind ein vereinfachtes Occlusion-Modell der Welt, das Nicht-Okkludierer und deren Konnektivität anstelle von Okkludern speichert. Während genaue und konservative Okklusionsergebnisse bei relativ geringen Laufzeitkosten erzielt werden können, ist die Arbeit der manuellen Platzierung von Zellen und Portalen sehr arbeitsintensiv, fehleranfällig und erhöht die Kosten der Contentänderung drastisch.

Umbra 3: die nächste Generation des Occlusion Culling.

Das Umbra 3 Occlusion Culling System wurde entwickelt, um die in den vorherigen Kapiteln beschriebenen Herausforderungen zu bewältigen.

Umbra 3 basiert auf der Idee, eine 3D-Welt von der detaillierten, vom Künstler erstellten Polygondarstellung in eine vereinfachte zu verwandeln. Die Transformation konzentriert sich auf die Erfassung der wesentlichen Occlusion-Eigenschaften unter gleichzeitiger Ignorierung von Informationen über Details, die keine oder nur geringe Relevanz im Prozess des Occlusion Cullings haben. Dieser Ansatz ähnelt dem manuell erstellten Portal- und Zellendiagramm. Das von Umbra 3 verwendete Occlusion-Modell ist jedoch ein automatisch generiertes Portal- und Zelldiagramm.

Traditionell wurden die Spielwelten, in denen das Portal Culling erfolgreich eingesetzt wird, so gestaltet, dass eine kleine Anzahl von Portalen grobe Occlusion-Informationen erfassen kann. Leere Räume, die durch enge Durchgänge verbunden sind, wobei die meisten Verbindungen auf oder in der Nähe der Grundplatte stattfinden. Eine allgemeine Lösung kann solche Annahmen über die Welt nicht treffen und muss mit beliebig komplizierten Topologien in allen drei Dimensionen arbeiten. Eine viel größere Anzahl von Zellen und Portalen ist erforderlich, um den Verschluss großer Außenflächen mit individuellen Verschlussmerkmalen zu erfassen.

Umbra 3 besteht aus zwei Komponenten:

Der Optimizer.

Der Optimizer wird in der Pre-Processing-Phase in den Spieleeditor integriert. Es nimmt als Eingabe jede Art von Polygon-Soup und diskretiziert die gesamte Szene in Voxel, um View-Zellen zu erzeugen. Die View-Zellen werden anschließend durch Portale verbunden. Die Diagrammdaten der Portale und Zellen werden in einer optimierten Datenstruktur gespeichert, auf die zur Laufzeit zugegriffen wird.

Die Runtime-Komponente.

Die Runtime-Komponente rastert einen Software Depth Buffer, der zum Testen der Sichtbarkeit verwendet wird. Es ermöglicht eine große Anzahl von dynamischen Objekttests pro Frame bei sehr geringen Rechenkosten. Die Genauigkeit des Algorithmus liegt nahe der von Hardware-Occlusionabfragen, ist aber – als reine Software-Implementierung – frei von allen Synchronisations- und Portabilitätsproblemen, die für hardwarebasiertes Occlusion Culling typisch ist.

Die technischen Herausforderungen für das automatisch generierte Portal- und Zellendiagramm lassen wie folgt zusammenfassen:

• Eine zufällige Polygon-Soup muss in ein repräsentatives Portal- und Zelldiagramm umgewandelt werden, so dass die Größe des Diagramms und die Granularität der Occlusion gesteuert werden können.
• Eine effektive Runtime-Culling-Methode ist erforderlich. Es muss das Portal- und Zellendiagramm verwenden und mit einer relativ großen Anzahl von Portalen umgehen können. Darüber hinaus muss es konservative Culling-Ergebnisse in festem oder begrenzten Speicher liefern und dies schnell genug tun, um in einem minimalen Occlusion-Szenario nicht zu einem Engpass zu werden.

Die folgenden beiden Kapitel beschreiben Lösungen für diese beiden Herausforderungen, wie sie im Umbra 3 Occlusion Culling System umgesetzt sind.

Generierung von Occlusion-Daten.

Auf einer hohen Ebene wird das Diagramm für eine 3D-Szene erzeugt, indem ein rohes, gleichmäßig verteiltes Ausgangsportaldiagramm erstellt wird. Dieses Diagramm wird schrittweise vereinfacht, indem Daten entfernt werden, die wenig zur gesamten Occlusion beitragen. Die eingegebenen Verschluss-Meshes werden nur in der ersten Phase der Zellgenerierung verwendet, um zu bestimmen, ob ein einzelner Voxel oder eine achsenausgerichtete Box als fest oder leer anzusehen ist.

Die Voxifizierung ermöglicht es, dass der Algorithmus unabhängig von der geometrischen Komplexität ist. Die Tatsache, dass das Ergebnis nur konservativ an die reale Geometrie ausgeglichen werden muss, macht dies möglich.

Initiale Zellgenerierung.

Das anfängliche Diagramm wird definiert, indem zuerst die Szenengeometrie in ein achsenorientiertes Mesh unterteilt wird. Die Größe des anfänglichen Raster-Nodes wird entsprechend der Granularität gewählt, bei der wir die Szenenverschlussfunktionen untersuchen möchten. Als nächstes unterteilen wir die Geometrie weiter in Voxel, die entweder als fest oder leer gekennzeichnet sind, indem wir das Voxel mit der Geometrie schneiden.

Die Voxel werden verwendet, um nicht verbundene Bereiche innerhalb des Würfels zu finden, indem leere Voxel durch Fluten gefüllt werden, d.h. rekursives Gruppieren benachbarter leerer Voxel. Die leeren Voxelsätze sind die ersten Kandidatenzellen für unsere Grafik. Für jede dieser leeren Voxelgruppen finden wir den Schnittpunkt mit den Würfelflächen und speichern die achsparallelen Grenzen des Schnittpunktes als Portalrechteck. Um die Ausgangszellen zu einem Diagramm zu verbinden, wird das Portal an ein Nachbarportal angepasst, das auf der anderen Seite der Würfelfläche erzeugt wird.

Der Vorteil der Verwendung einer diskreten volumetrischen Darstellung der Geometrie sollte offensichtlich sein. Die Verschneidung beliebiger Polygondaten mit achsenausgerichteten Kästen kann numerisch robust erfolgen und nach der Bildung der Voxel ist der Algorithmus unabhängig von der Komplexität der Eingabedaten und muss nur noch mit einem einfachen ganzzahligen Mesh umgehen. Da wir nach einer konservativen Occlusion-Repräsentation sind, müssen wir der Geometrie nicht genau folgen, solange wir uns auf die konservative Seite begeben.

Die einzige Ausnahme von dieser Methode ist die Verbindungsermittlung innerhalb des Grid-Nodes. Ein Loch in den Mesh-Daten, das kleiner als die gewählte Voxelgröße ist, wird nicht durch einen Pfad von leeren Voxeln erfasst und trägt nicht zur Konnektivität bei. Glücklicherweise sind kleine, isolierte, durchsichtige Löcher relativ selten und in Spielen oft unbeabsichtigt.

Wenn wir an dieser Stelle Informationen über statische Zielobjekte haben, können wir damit fortfahren, ihre Geometrie ähnlich zu voxeln und Objekte unseren Ausgangszellen zuzuordnen, indem wir die Zelle finden, zu der die benachbarten leeren Voxel gehören. Wenn die gleiche Geometrie sowohl als Okkluder als auch als statisches Zielobjekt verwendet werden soll, können wir natürlich die Hälfte der Arbeit einsparen.

Graph-Simplifizierung.

Wenn wir das Portal mit dem kleinsten Occlusion-Wert in unserem Portal- und Zellendiagramm finden, können wir das Portal entfernen, indem wir die Zellen kombinieren, die das Portal miteinander verbindet. Diese Methode bildet ein vereinfachtes Diagramm, das den Verlust der gesamten Occlusion-Information minimiert. Wenn wir iterativ bis zu einem Schwellenwert für die Portalverschlusskurve oder zu einem festen Speicherbudget voranschreiten, können wir das Kosten-Nutzen-Verhältnis der endgültigen Grafik kontrollieren.

Eine optimale Vereinfachung der Grafik durch Gruppierung der beiden durch das Portal verbundenen Zellen, die den schlechtesten globalen Occlusionswert haben, würde eine unerschwingliche globale Grafikanalyse erfordern, da die Sichtbarkeit im Wesentlichen ein globales Attribut ist. Allerdings können lokale Heuristiken angewendet werden, um die nutzlosesten Portale schnell aus dem Diagramm zu entfernen. Die Vereinfachung kann hierarchisch erfolgen, indem der Schwellenwert für die Portalverschlüsse verringert wird, während wir in der Hierarchie nach oben zu größeren Bereichen zu sehen. Auf jeder neuen Hierarchieebene verbinden wir die externen Portale der benachbarten Volumina und führen die Vereinfachung für die neu gebildete kombinierte Grafik durch.

Die hierarchische Vereinfachung bietet auch die Möglichkeit, Detailversionen der Occlusion-Daten auszugeben. Der Runtime-Algorithmus kann diese Ausgaben verwenden, um die verwendete Occlusionsstufe basierend auf der Entfernung vom Standpunkt aus auszuwählen.

View Tree.

Die Graphen der Portale und Zellen können sehr komplex werden. Die letzten Spielzellen, die durch die Teilung in zusammenhängende Voxelgruppen und die anschließende Zellgruppierung gebildet werden, lassen sich nicht mehr leicht durch einfache geometrische Formen erfassen und das Speichern der kompletten Voxelstruktur selbst einer kleinen Szene ist unpraktisch. Um das Portal- und Zellendiagramm für das Runtime-Culling zu verwenden, ist eine andere Datenstruktur erforderlich, um die Zelle, die der Kameraposition im Diagramm entspricht, genau zu lokalisieren. Diese Datenstruktur wird als View Tree bezeichnet.

Zusammenfassend lässt sich sagen, dass der View Tree wie folgt aufgebaut wird:

• Zwei benachbarte leere Voxel, die zu derselben Zelle gehören, können zusammengelegt werden, da ihre getrennte Speicherung keine Informationen hinzufügt. Große leere Bereiche können im View Tree zu achsparallelen Elementen zusammengeklappt werden.
• In Spieleanwendungen darf die Kamera nicht beliebig nahe an der Geometrie platziert werden. Dadurch wird sichergestellt, dass sich die Near-Clipping-Ebene nicht mit der Geometrie überschneiden kann, da dies zu unerwünschten Renderergebnissen führen würde. Daher können wir benachbarte Voxel und sogar leere Voxel, die zu separaten Zellen gehören, zusammenbrechen, solange die Größe des resultierenden Elements den Kollisionsradius der Kamera nicht überschreitet.
• Schließlich können wir Voxelgruppen identifizieren und vereinfachen, die sich in Volumina befinden, in denen die Kamera nicht vorhanden sein darf. Dazu gehören auch Zellen, die innerhalb von Mauern und unterhalb des Geländes bildet werden.

Kacheln.

Abgesehen von der Anpassung der Parameter für die Voxelisierung erfolgt der Prozess der Portalerzeugung automatisch. Es kann jedoch einige Zeit dauern, bis es fertig ist. Dies ist aus der Sicht der Inhaltsiteration unangenehm und verschwendet wertvolle Künstler- und Designerzeit. Auch der Speicherverbrauch ist ein Problem. Unvereinfachte, hochauflösende Voxelisierung kann Gigabyte an Speicher verbrauchen.

Umbra 3 vermeidet dieses Problem, indem es die Welt in räumliche Recheneinheiten, Kacheln, unterteilt, die unabhängig voneinander berechnet werden können. Die Welt kann dann Kachel für Kachel parallel oder verteilt berechnet werden. Nur der aktuell verarbeitete Kachelsatz benötigt Speicher für die hochauflösende Voxeldarstellung.

Da der Prozess der Portalgenerierung deterministisch ist, können Berechnungsergebnisse für eine Kachel auch durch Hash-Eingabe gespeichert werden. Dieser Ansatz unterstützt inkrementelle Änderungen, bei denen nur der aktualisierte Teil einer Szeene neu berechnet werden muss. Die Ergebnisse können auch über das Netzwerk ausgetauscht werden. Zur Laufzeit können die Sichtbarkeitsdaten kachelweise gestreamt werden.

Run-Time Portal Culling.

Die andere Komponente der Umbra 3-Lösung ist ein Run-Time Portal Culling Algorithmus. Dieser Algorithmus verwendet das vereinfachte Occlusion-Modell, um die Sichtbarkeit aus der Kameraansicht zu bestimmen.

Der Algorithmus für das Runtime-Culling muss schnell sein – der gesamte Vorgang muss in der Größenordnung von wenigen Millisekunden abgeschlossen sein – um die Anforderung der Wertschöpfung in einem Spiel mit 60 Bildern pro Sekunde zu erfüllen.

Da die Menge der verarbeiteten Portalgrafikdaten signifikant sein kann, ist eine Schlüsselbetrachtung im Algorithmen-Design der Datenzugriff und das Caching-Muster. Dies gilt insbesondere für Hardware-Architekturen, die für das Streaming paralleler Daten optimiert sind, wie beispielsweise der Cell-Prozessor in der PlayStation 3.

Graphen-Durchlauf.

Das automatisch generierte Portal- und Zellendiagramm unterscheidet sich nicht grundlegend von einem herkömmlichen handgefertigten Diagramm. Daher könnten wir leicht den traditionellen Algorithmus des Portal-Cullings verwenden, bei dem das Diagramm rekursiv durchlaufen wird, während wir den View Frustum auf die eingegebenen Portale zuschneiden. Diese Art der Traversal muss jedoch jede Zelle einmal für jeden sichtbaren Weg besuchen. Im schlimmsten Fall kann dies zu einer exponentiellen Algorithmuslaufzeit und zu einer katastrophalen schlechten Performance führen.

Um den Wiedereintritt von Zellen zu begrenzen, durchläuft der Umbra 3 Runtime Culling Algorithmus das Diagramm in der Regel in der Breite zuerst. Anstelle eines geometrischen Portallösers wird die Software-Rasterung verwendet,um die Sichtbarkeitsinformationen in einem Bildschirmraum-Verschlusspuffer zu sammeln. Diese Methode eliminiert fast vollständig übermäßige Rekursionen. Da die Zellen jedoch aus dem anfänglichen Gitterwürfeln aufgebaut sind, könnte eine echte Verarbeitungsreihenfolge der ersten Zelle nicht einmal existieren: Es kann Zyklen zwischen den Zellen im Diagramm geben, die keine andere Wahl lassen, als eine Zelle mehr als einmal zu verarbeiten.

Um dies zu beheben, wird die Grafik als kastenförmige Fliesen gespeichert, die jeweils Dutzende bis Hunderte von Zellen enthalten. Die Kacheln werden so erzeugt, dass zwischen ihnen eine einfache Front-to-Background-Reihenfolge festgelegt werden kann. Die Per-Tile-Traverse macht den Zugriff auf die Diagrammdaten auch räumlich kohärent und damit Cache-freundlich.

Der Vorteil der Kachelung besteht darin, dass wir wissen, dass wir, sobald alle Zellen in einer Kachel verarbeitet wurden, die endgültigen Sichtbarkeitsinformationen für alle gesammelt haben und daher alle Ressourcen, die zur Erfassung der Sichtbarkeit pro Zelle gehalten werden, sicher freigeben können.

Portal-Rasterung.

Die hierarchische Tile-Diagrammdurchquerung hilft bei der Verwendung der Anzahl der Zellen, die zu einem bestimmten Zeitpunkt aktiv sind. Eine weitere wichtige Speicheroptimierung ist das Datenlayout des Occlusion-Buffers. Auch hier bietet die Tatsache, dass nur konservativ korrekte Ergebnisse erforderlich sind, eine kostengünstige Lösung. Die Portalrechtecke werden in einen niedrigauflösenden, 1 Bit pro Probe umfassenden Abdeckungpuffer gerastert. Jedes gesetzte Bit im Puffer stellt einen unverschlossenen Pfad zur Zelle dar.

Das Konzept der Rasterung der leeren Raumes (der Portale) anstelle einer Darstellung der okkludierenden Geometrie mag zunächst unorthodox erscheinen. Die Rasterung transformierter Quads ermöglicht jedoch eine einfache und konservative Handhabung von Geometriekanten. Der Rasterizer führt Halbraumtests gegen die Portalkantenfunktionen durch und spart Rechenressourcen in großen Innen- oder Außenbereichen, indem er das Bildschirmrechteck hierarchisch untergliedert und gegen rechteckige Eckpunkte testet. Die konservative Rasterung ermöglicht auch die Skalierung der Auflösung basierend auf der Performance der Laufzeitplattform.

Die Gesamtmenge des Arbeitsspeichers, die der Portal-Culling-Algorithmus benötigt, einschließlich der Traversendatenstrukturen des Output Depth Buffers und des Abdeckungspuffers für den aktiven Zellensatz, ist auf 85 Kilobyte festgelegt. Dadurch ist es klein genug, um in den lokalen Speicher moderner strömungsorientierter Verarbeitungseinheiten zu passen.

Occlusion Testing.

Occlusion Testing von statischen Objekten, die sich in den Zellen befinden, kann während der Diagrammdurchquerung durchgeführt werden, indem festgestellt wird, ob sichtbare Pixel im Abdeckungspuffer vorhanden sind, die sich mit den Bildschirmraumgrenzen der Objekte überlappen.

Die Zuordnung von statischen Objekten zu Zellen ist in der Vorverarbeitungsphase einfach durchzuführen, wo wir es uns leisten können, in der Voxeldarstellung zu arbeiten. Allerdings erfordern alle dynamischen Entitäten, die wir testen möchten, eine andere Lösung. Zu diesem Zweck baut der Entnahmealgorithmus während des Verfahrvorgangs einen globalen Depth Buffer auf. Der Depth Buffer jeder durchlaufenen Zelle wird basierend auf dem aktuellen Abdeckungspuffer aktualisiert, wobei der Abstand des Zellenbegrenzungsrahmens als Tiefenschreibwert verwendet wird. Auf diese Weise muss nur ein einziger 16-Bit 128×128 Depth Buffer für die Dauer der Verfahrbewegung im Speicher gehalten werden.

Die Möglichkeit, einen einzelnen Depth Buffer aus der Traverse auszugeben, ermöglicht es, die dynamischen Objektverschlusstests jederzeit nach der Diagrammdurchführung durchzuführen. Dies kann besonders wichtig sein, wenn die genaue Position und der Umfang der animierenden Objekte parallel zur Ausführung der Portalauslesetraverse ermittelt werden soll.

Schlußfolgerungen.

Wenn man die Grenze der Gesamtkomplexität, die in einem Spiel dargestellt werden kann, überschreitet, sind genaue Sichtbarkeitsinformationen ein unschätzbarer Vorteil. Das Bestimmen der Elemente, die aus einem bestimmten Blickwinkel nicht sichtbar sind, wird als Occlusion Culling bezeichnet. Viele Ansätze wurden entwickelt und eingesetzt, um das des Occlusion Cullings zu lösen. Jeder traditionelle Ansatz bringt jedoch eine Reihe von Kompromissen mit sich und daher bleibt das Culling ein aktiver Bereich der Forschung.

Das Umbra 3 Occlusion Culling System wurde entwickelt, um die Kompromisse bei den traditionellen Occlusion Culling Lösungen zu überwinden. Umbra 3 verarbeitet automatisch jede Art von polygonaler Eingangsszene in eine kompakte Laufzeitdarstellung. Diese Darstellung kann für eine effiziente und konservativ korrektes Occlusion Culling verwendet werden. Die wichtigsten Methoden sind:

• Die Diskretisierung der Eingangsgeometrie beim Voxelisierungsprozess.
• Die Laufzeit-Software-Rasterung, die schnell die Liste der sichtbaren Objekte zusammen mit einem konservativen Depth Buffer in der gewünschten Auflösung erzeugt.

Die Parameter für die Portalgrafik und die Laufzeitauflösung ermöglichen es dem System, nahtlos von Low- zu High-End-Geräten zu skalieren. Daher ist Umbra 3 auch eine praktikable Lösung z.B. für Smartphone-Spiele.

Zusammenfassend lässt sich sagen, dass Umbra 3 den Aufbau massiver 3D-Spielwelten aus zufälligen Polygon-Soups ohne manuelle Markierung für die Sichtbarkeit ermöglicht und gleichzeitig konservativ korrekte Culling-Ergebnisse garantiert. Umbra 3 macht auch Sichtbarkeits- und räumliche Argumentationsinformationen für eine breitere Kategorie von Subsystemen für Spielmaschinen zugänglich. Aus diesem Grund verwenden Spieleentwickler auf der ganzen Welt, wie Bungie und viele anderem Umbra 3 in verschiedenen Produktionen auf einer Vielzahl von Runtime-Plattformen.