Aktuelle Version vom 30. Dezember 2005, 20:22 Uhr

Ein Szenengraph ist ganz allgemein gesagt eine Datenstruktur, welche graphische Elemente einer virtuellen Welt beinhaltet. Die einfachste Form eines Szenengraphen ist eine Liste oder ein Array von Objekten.

Definition und Aufbau

Üblicherweise geht man jedoch etwas weiter ins Detail und definiert Szenengraphen als eine Baumstruktur welche

• Azyklisch: die Struktur enthält keine Kreisverbindungen, jeder eingeschlagene Weg durch die Struktur führt also zu einem Ende.
• und Hierarchisch: Jeder Knoten hat maximal einen übergeordneten Knoten.

ist. Ein Knoten dieser Struktur kann dabei ein geometrisches Objekt beinhalten und/oder Eigenschaften für die Darstellung von Objekten. Typische Knotentypen und Eigenschaften sind:

• geometrisches Objekt oder Modell
• Transformation
• Auswahlknoten: für eine Auswahl der Level of Detail Stufe; Zustände wie Tür geöffnet oder geschlossen; ...
• (Bounding-) Volumeninformationen: für (effizientere) Sichtbarkeits- und Kollisionsabfragen
• Lichtquelle
• Materialeigenschaften für geometrische Objekte: ambient, diffuse, specular, emmision und shininess Komponente, sowie Textur(en)
• Gegebenenfalls auch weitere (grafische oder auch physikalische) Materialeigenschaften, unter anderem Geräuschquelle(n), Glätte, Härte, ...

Die meisten Eigenschaften werden üblicherweise von den übergeordneten an die untergeordneten Knoten vererbt. Das bedeutet beispielsweise, dass ein Licht nur für die Knoten gültig ist, welche sich im Unterbaum des Knotens der die Lichteigenschaft besitzt befinden. Ein Gängiges Beispiel ist hier auch ein Auto, welches als gesamtes eine Position innerhalb der Welt besitzt, dessen Reifen jedoch Unterknoten des Autos mit zusätzlicher Transformation sind. Dadurch werden die Reifen des Autos an die Position des Autos innerhalb der Welt verschoben, und können zusätzlich noch eine beliebige Rotation und gegebenenfalls auch Translation in Relation zur Autoposition besitzen.

Häufig kann der selbe Knoten oder die selbe Eigenschaft auch öfter in den Baum eingefügt werden. So könnte beim vorigen Beispiel nur ein Knoten vorhanden sein, welcher die Geometrie eines Reifen beinhaltet. Dieser Knoten könnte für alle 4 Reifen eines Autos wiederverwendet werden, nur die Transformation wird durch einen zusätzlichen übergeordneten Knoten jeweils anders definiert.

Operationen auf den Szenengraphen

Zeichenvorgang

Die wichtigste Operation auf einen Szenengraphen ist natürlich der Zeichenvorgang. Hier wird üblicherweise der Szenengraph rekursiv durchlaufen, wobei man sich die Eigenschaften der Parent-Knoten merkt. Häufig wird für diesen Vorgang auch die OpenGL-API direkt verwendet, indem die Push/Pop Funktionalität für verschiedenste Eigenschaften verwendet wird (glPushMatrix, glPopMatrix, glPushAttrib und glPopAttrib sind hier die wichtigsten Funktionen). Für Zustände wo OpenGL keine Push/Pop Funktionalität bietet (beispielsweise die verwendete Textur) muss natürlich eine eigene Push/Pop Funktionalität implementiert werden. Um den Zeichenvorgang effizienter und grafisch korrekter zu machen, können auch zuerst alle Objekte gesammelt, nach ihren Render-Eigenschaften sortiert und erst dann an den Renderer geschickt werden.

Sichtbarkeitsabfrage

Um den Zeichenvorgang zu beschleunigen, kann vorher eine Sichtbarkeitsüberprüfung auf die Knoten des Szenengraphen durchgeführt werden. Dazu sollte natürlich ein Bounding Volumen für den gesamten Unterknoten vorhanden sein.

Update des Szenengraphen

Wenn auf einen Knoten eine Änderung durchgeführt wird, so müssen Teilweise auch die Parent-Knoten dieses Knoten upgedatet werden. Nach welchen Änderungen welche Attribute verändert werden müssen, ist sehr stark abhängig von der Implementierung des Szenengraphen. Beispiele sind:

• Bounding Volumen der Parents updaten nach Transformation, Animation, Geometrie-Änderung, Hinzufügen oder Entfernen eines Knoten.
• Transformation aller Childs updaten nach der Transformation eines Knoten, wenn aus Effizienzgründen zusätzlich zur Transformation relativ zum Parent auch noch die globale Transformation für jeden Knoten gespeichert wird.
• Parent Knoten ändern nach einer Transformation, wenn eine künstliche, physikalische Unterteilung der Szene beispielsweise durch einen Octree vorgenommen wird.

Üblicherweise wird jedoch die Transformation (welche wahrscheinlich die meisten Updates erfordert) nicht direkt geändert sondern nur die Geschwindigkeit eines Knotens/Objektes. Die Transformation wird dann durch die Animation entsprechend berechnet.

Animation

Um in einen Szenengraphen Animationen einzubauen, sind üblicherweise die meisten Werte die für die verschiedenen Eigenschaften angegeben werden können über die Zeit parametrisierbar. Unter anderem können hier folgende Parameter abhängig von der Zeit verändert werden:

• Position (durch Geschwindigkeit und ggf. auch durch Beschleunigung)
• Intensität einer Lichtquelle
• Farbe von Objekten
• Aussehen von Objekten (Keyframe-Animation, Bone-Animation, ...)

Kollisionsabfragen

Bei den geometrischen Änderungen einer Szene die durch Animationen entstehen sind häufig auch Kollisionsabfragen mit anderen Objekten erwünscht. Auch hier kann von der Hierarchischen Struktur eines Szenengraphen gebrauch gemacht werden, sofern das Bounding Volumen eines Knoten bekannt ist. Hier muss nur mit denjenigen Teilbäumen eine Kollisionsabfrage durchgeführt werden, wo das Bounding-Volumen des Parent Knoten eventuell das Bounding Volumen des animierten Knoten schneidet.

Vergleich: Grafik-Engine

Szenengraphen sind üblicherweise sehr allgemein gehalten, und überlassen die Einteilung der Szene großteils dem Anwender. Dadurch erhält der Anwender zwar mehr Möglichkeiten zur Optimierung, jedoch auch mehr Verantwortung. Nahezu jede Grafik-Engine besteht aus einem Szenengraphen von dem der Anwender jedoch verhältnismäßig wenig sieht. Durch die großteils automatisierte Erstellung des Szenengraphen können zusätzliche Regeln für den Aufbau des Graphen festgelegt werden, wodurch die verschiedenen Operationen auf den Szenengraphen leichter optimiert werden können. Beispiele für solche Regeln sind:

• Die Objekte werden immer in einen Octree eingeteilt.
• Jedes komplexe Objekt (Level) muss einen BSP-Baum für die Kollisionsabfrage besitzen.
• Jedes komplexe Objekt (Level) sollte Portale für Sichtbarkeitsabfragen besitzen.
• Jedes Objekt muss eine Bounding Sphere besitzen.
• Jedes statische Objekt darf zusätzlich noch Bounding Boxes besitzen.
• Jedes statische Objekt muss die Daten für VIPMs zur Verfügung stellen.
• Lichtquellen dürfen nicht animiert werden.
• Jedes komplexe Objekt (Level) muss Lightmaps besitzen.
• ...

Natürlich sollte auch bei einer Engine jede mögliche Szene darstellbar sein, jedoch werden durch diese Regeln verschiedene Szenen besser, schlechter oder teils sogar gar nicht darstellbar, wodurch Grafik-Engines üblicherweise viel spezialisierter als Szenengraphen sind.

Natürlich kann man auch einen Szenengraphen implementieren, welcher verschiedene Regeln voraussetzt, oder anwendet. Alleine die unterstützten Dateiformate und Datenstrukturen geben schon gewisse Regeln vor. Aus diesem Grund ist die Frage ob eine Engine ein Szenengraph ist, oder ob eine Engine einen Szenengraphen benutzt ein Punkt über den man sich lange streiten könnte.