Der Render-Prozess

Die Rendergeschwindigkeit hängt davon ab, wieviele Entities, Polygone und Pixel aktuell auf dem Bildschirm dargestellt werden. Dies lässt sich vom Anwender sowohl durch ein Verringern der Menge an Entities im Level als auch durch die Anzahl ihrer Polygone beeinflussen. Und auch die Engine hat Einfluss auf die Rendergeschwindigkeit, indem sie so viele Objekte wie möglich entfernt, bevor sie den Rest zeichnet. Diesen Prozess nennt man Scene Management, Visibility Determination, Hidden Surface Removal (Szenen-Management, Sichtbarkeitsbestimmung, Entfernen versteckter Oberflächen) oder kurz Culling (was in etwa so viel bedeutet wie 'Abschneiden nicht sichtbarer Objekte'). Wie man es auch immer nennen mag, das Ziel ist stets dasselbe: möglichst viele Pixel davon abzuhalten, auf dem Bildschirm zu erscheinen.

Ein Szene Manager rendert nur die Teile eines Spiele-Levels, die sichtbar sind. Es gibt verschiedene Methoden. Zu den ältesten Szene Managern gehörte das Octree-System. Ein Octree teilt die Welt in 8 rechteckige Bereiche, wovon jeder wiederum 8 kleinere Regionen enthält. Dieser Prozess wird so oft wiederholt, bis die letzten Regionen so klein sind, dass sie nur noch ein einzelnes Objekt enthalten. Der Renderer berücksichtigt nur den Inhalt der Regionen, die sich im Sichtbereich der Kamera befinden. Wegen ihrer Einfachheit werden Octrees auch heute noch von vielen 3D Engines verwendet. Octrees berücksichtigen allerdings nicht, welche Teile des Levels von Wänden oder anderen Objekten verdeckt sind. Daher wurden bessere Szene Manager entwickelt.

Das BSP-Tree-System teilt den Level in unregelmäßige Regionen, die von der Level-Geometrie bestimmt werden. Es rendert nur die Teile, die tatsächlich sichtbar sind, und ist damit das schnellste und effektivste System, besonders in Innenräumen. Mit einem BSP-Tree-System bleibt die Rendergeschwindigkeit, weitgehend unabhängig von der Levelgröße und erlaubt akzeptable Frameraten auch noch auf alten PCs. Allerdings haben BSP-Tree-Systeme den Nachteil, dass der Editor mit einem integrierten Map Compiler den Tree vorberechnen muss.

Die meisten kommerziellen Engines großer Spielefirmen arbeiten mit einem BSP-Tree-System mit einem PVS-Sichtbarkeitstest. Diese Art von Tree-Algorithmus, kurz: BSP/PVS, ist heutzutage die effektivste Methode zum ermitteln, ob ein Objekt verdeckt ist oder nicht. Weiter unten wird sie detaillierter erklärt. Einfachere Engines benutzen einen Octree oder ein ähnliches geometrie-unabhängiges System. Für Außenlevel, wo ein BSP-Tree nur einen geringen Vorteil bietet, wird oft ein LOD (Levels of Detail - siehe Entities) System benutzt, um die Framerate zu erhöhen. Es schaltet, sobald Objekte weiter von der Kamera entfernt sind, auf einfachere Formen um. Auf diese Weise reduziert sich die Gesamtzahl der pro Frame gezeichneten Polygone.

Der BSP-Tree

Ein Binary Space Partition Tree (binärer Raumaufteilungs-Baum) oder kurz BSP-Tree ist im Grunde eine Methode, die Welt in leicht zu handhabende Regionen aufzuteilen, die dann individuell behandelt werden können. Solche Regionen, die nicht auf dem Bildschirm sichtbar sind, werden früh aus dem Renderprozess entfernt. Folglich ist beim Beschleunigen des Renderns ein BSP-Tree von grundlegender Bedeutung. Darüber hinaus kann er auch Beleuchtungsberechnungen und Kollisionserkennung unterstützen. Außerdem führt er ein Vorsortieren von Objekten aufgrund ihres Abstands zum Bildschirm durch.

Mit dem Zentrum des Levels beginnend, wird die Map zunächst in zwei Regionen längs einer Wand aufgeteilt. Eine Seite nennt man die Front-Region, die andere ist die Back-Region. Dann wird dieser Prozess erneut sowohl mit der Front- und der Back-Region durchgeführt, also jede Region wie eine eigene Map behandelt. Dies wird so lange fortgeführt, bis die Welt genügend aufgeteilt ist (wird vom Compiler festgelegt). Wir haben nun zum Schluss eine hierarchische Liste von Regionen - das ist unser BSP-Tree. Die Engine verfolgt und merkt sich, was wovon abgeteilt wurde. Auf diese Weise weiß jede Region im Tree, von welchen Regionen sie umgeben ist. Da zum Aufsplitten lediglilch Level-Blocks verwendet werden, haben in der Map plazierte Entities keinen Einfluß auf den BSP-Tree.

Die Verbindung zwischen zwei Regionen nennt man ein Portal. Das sind die mysteriösen Portale, die vom Map-Compilingprozess angegeben werden. Aber wir sind noch nicht fertig. Nachdem wir die Welt in Regionen aufgeteilt haben, besucht der Map-Compiler alle Regionen des Trees und stellt fest, welche Regionen von dieser Region aus sichtbar sind. Für jede Region erstellt er eine Liste sämtlicher anderer potentiell sichtbarer Regionen der Welt. Diese Liste nennt man die Potentielle Sichtbarkeitsliste (Potentially Visible Set), oder kurz PVS. Wie Sie unschwer erkennen können, ist dies ein komplexer Prozess, und daher braucht der Map-Compiler ziemlich lange zum Kalkulieren des PVS von komplizierten Maps.

A8 Die A8-Engine unterstützt spezielle Portale, die vom Skript gesteuert werden. Dazu können rechteckige Portalgegionen in WED platziert werden. Eine solche Region wählt, wenn sie mit einem Skriptbefehl aktiviert ist, all seine Objekte aus dem PVS. Dies läßt sich zum Abschalten des Renderns von Objekten innerhalb eines Raumes verwenden solange sich die Kamera ausserhalb befindet oder die Türen geschlossen sind.

Beim Rendern eines Frames durchkämmt die Engine die BSP-Regionen um herauszufinden, in welcher sich die Kamera gegenwärtig befindet. Sobald diese gefunden ist, ermittelt sie anhand des PVS, welche Regionen von dort aus gesehen werden könnten und verwirft die Regionen, die unter keinen Umständen gesehen werden können - einschließlich sämtlicher Objekte innerhalb dieser Regionen. Dies ist eine sehr effektive Form von Sichtbarkeitsbestimmung, denn so lassen sich, je nach Level-Architektur, bis zu 90% aller Objekte entfernen.

Der adaptive Binär-Tree

A7 Ein anpassungsfähiger oder adaptiver Binär-Tree, oder kurz: ABT stellt die effektivste Möglichkeit für ein Szenen-Management ohne vorberechneten Tree dar. Er funktioniert ähnlich wie ein Octree, benutzt aber verschiedene Regionsgrössen, je nach Level-Geometrie und Entity-Verteilung im Level. Ein ABT wird in Echtzeit berechnet und so ist das Kompilieren des Levels aufgrund des Weglassens des BSP/PVS-Prozesses um einiges schneller. Obwohl weniger effektiv als ein BSP-Tree, kann ABT in Außenleveln mit fast derselbem Leistung aufwarten. Die Engine verwendet für Level, die keinen vorausberechneten BSP-Tree beinhalten automatisch einen ABT. Engine Versionen unter P , die BSP nicht unterstützen, verwenden immter einen ABT, auch dann, wenn das Level im BSP-Modus kompilliert wurde

Hindernisse in der Bahn eines Pixels

Nachdem die Objekte der Szenerie sortiert und die verdeckten Objekte durch den BSP/PVS-Alorithmus entfernt sind, stellt die Engine als nächstes fest, welche der potentiell sichtbaren Objekte sich innerhalb des View-Frustums befinden. Das View-Frustum ist der einsehbare Bereich vor der Kamera. Alles, was sich komplett außerhalb dieses Bereichs befindet, kann vom Spieler nicht gesehen werden. Das View-Frustum sieht aus wie eine Pyramide mit abgeschlagener Spitze.

All die Objekte, die im View-Frustum übrigbleiben, werden von der Engine tatsächlich gerendert. Dabei sind auch Polygone von Objekten, die nur teilweise innerhalb des Frustums liegen, eingeschlossen und ebenso Polygone, die von der Kamera weg zeigen (backface culling). Alte Engines, wie A4 und A5, hatten extra Clipping-Phasen zum Entfernen nicht nichtbarer Polygone. Heute wird das Polygon-Clipping von der 3D-Hardware übernommen, denn solche Extraphasen würden das Rendering deutlich (bis zu 40%) verlangsamen. Moderne Engines wie A6 rendern daher Objekte als ganzes Polygon-Gitter und kümmern sich nicht um das Clipping einzelner Polygone.

Hat ein Objekt LOD-Stufen, werden diese nun in Abhängigkeit der Objekt-Distanz ausgewählt. Das Rendern geschieht nun in mehreren Durchgängen. Zuerst werden solide Objekte gezeichnet, dann Schattenvolumina, dann transparente Objekte, dann Stencil-Schatten und zum Schluß der Sky. Vor dem Rendern werden solide Objekte von vorn nach hinten sortiert und transparente Objekte von hinten nach vorn. Das hat den Vorteil, daß Pixel solider Objekte früh den Z-Buffer - s.u. - füllen und so zeitaufwendige Shader-Operationen verdeckter Objekte verhindern.

Die 3D-Hardware kümmert sich um die letzten Culling-Phasen. Die Hardware stellt fest, welche Polygone sich außerhalb des Frustums befinden oder von der Camera weg zeigen (diese werden ignoriert) und welche teilweise oder ganz innerhalb des Frustums liegen (sie werden zurechtgeschnitten und dann gerendert). Zum Schluss wird jeder einzelne Pixel eines jeden Polygons mit dem Abstand des bereits auf dem Bildschirm dargestellten Pixels verglichen. Ist der Abstand größer, wird der Pixel nicht gezeichnet. Diesen Prozess nennt man z-buffer-clipping. Das kann eine Menge an Renderzeit sparen, besonders dann, wenn Pixel-Shaders verwendet werden und so das Darstellen jedes Pixels ein kleines Programm erfordert.

Transparenz ist nicht das was Sie denken

Durchscheinende oder transparente Objekte (siehe Transparency), die von einer 3D-Engine gerendert werden, benehmen sich ein kleines Bisschen anders als im richtigen Leben. Der Hauptgrund hierfür ist der, daß sie nicht per z-Buffer geklippt werden - sonst könnten Sie ja nicht hindurchsehen. Dieser Schritt wird also beim Transparenz-Durchgang weggelassen und verursacht typische Sortierfehler innerhalb von Polygonen von nicht-konvexen, transparenten Objekten und führt somit bei Neulingen, die sich noch nicht mit 3D-Engines auskennen zu ebenso typischen Frustrationen. Ab Version A6.6 werden Entities mit transparenten und nicht-transparenten Skin-Teilen in beiden Durchgängen (also sowohl transparent, als auch intransparent) gerendert. Dies ermöglicht es Ihnen, eine Entity mit transparenten Teilen zu haben, ohne dabei Sortierfehler bei ihren intransparenten Teilen zu bekommen.

	Objekte ABT oder BSP/PVS Frustrum (Engine) LOD

	Solider Durchgang	Transparenter Durchgang

	Vorn-nach-Hinten-Sortierung	Hinten-nach-Vorn-Sortierung

	Frustrum (Hardware)	Frustrum (Hardware)

	Backface	Backface

	Z Buffer

	Screen	Screen

In obigem Diagramm ist alles, was die Engine (Software) tut, in blau und die auf der Hardware ablaufenden Prozesse in rot dargestellt. Die Engine agiert auf Objektebene und die Hardware auf Ebene von Meshes (Polygongittern), einzelnen Polygonen und Pixeln.► Aktuelle Version Online