Szenengraph
Ein Szenengraph ist eine Datenstruktur, die häufig bei der Entwicklung computergrafischer Anwendungen eingesetzt wird. Es handelt sich um eine objektorientierte Datenstruktur, mit der die logische, in vielen Fällen auch die räumliche Anordnung der darzustellenden zwei- oder dreidimensionalen Szene beschrieben wird.
Der Begriff Szenengraph ist nur unscharf definiert. Dies liegt daran, dass konkrete Szenengraphen in der Regel anwendungsgetrieben entwickelt werden. Die Programmierer nutzen also die Grundidee, passen sie aber für die spezifischen Erfordernisse der Anwendung an. Feste Regeln, welche Funktionen ein Szenengraph erfüllen muss, gibt es daher nicht.
Hierarchische Modellierung
Aus graphentheoretischer Sicht ist ein Szenengraph ein zusammenhängender gerichteter Graph ohne gerichtete Kreise, dessen Wurzelknoten die Gesamtszene (das „Universum“) enthält. Dieser Wurzel untergeordnet sind Kindknoten, die die einzelnen Objekte der Szene, oder Eigenschaften wie Transformationen und Farben enthalten. Diese Knoten können wiederum Wurzel eines weiteren Baumes, also einer weiteren Hierarchie von Objekten sein. Da es sich um einen Graphen, nicht um einen Baum, handelt, kann ein Knoten auch mehrere Elternknoten haben.
Dieser Ansatz ermöglicht die hierarchische Modellierung der Objekte in einer Szene. Jeder Knoten des Szenengraphen hat üblicherweise eine Transformationsmatrix. Bei Manipulation dieser Matrix wird das zugehörige Objekt selbst, aber auch die Objekte aller untergeordneten Knoten transformiert. Man unterscheidet in diesem Fall zwischen Objektkoordinaten (Koordinaten eines Objektes bezüglich des übergeordneten Objektes) und Weltkoordinaten (Koordinaten eines Objektes bezüglich des Ursprungs des Universums – der Wurzel des Szenengraphen). Durch diese hierarchische Sicht wird der Aufbau und das Manipulieren einer Szene deutlich vereinfacht. Man muss nicht jedes Einzelteil eines Objektes einzeln transformieren, sondern transformiert einfach die Gesamtheit aller Einzelteile. Enthält eine Szene viele Kopien eines Objekts, so können all diese Kopien durch ein Objekt repräsentiert werden. Es gibt dann mehrere Wege von der Wurzel zu dem Knoten mit diesem Objekt, jeder mit seinen eigenen Transformationen und anderen Eigenschaften. Man spricht von Instancing.
Als Beispiel mag die Modellierung eines Autos mit vier Rädern dienen. Ein Knoten im Szenengraph repräsentiert das Objekt Auto. Dieser Knoten hat vier Kindknoten, die jeweils die Transformationsmatrizen der einzelnen Räder enthalten. Diese vier Kindknoten wiederum haben ein und den gleichen Kindknoten, der ein Objekt vom Typ Rad enthält. Ein Objekt – vier Darstellungen. Wird die Position oder die Lage des Auto-Knotens verändert, so wirkt sich die Veränderung auch auf alle Kindknoten, also in diesem Fall die Räder, aus. Eine manuelle Neuberechnung der Position der Räder ist also nicht erforderlich.
Bounding-Volume-Hierarchien
Oft werden Szenengraphen eingesetzt, um die Szenen einer Anwendung effizienter zu rendern oder um Berechnungen wie Kollisionsabfragen zu beschleunigen. Dazu wird zusammen mit einem Szenengraphen eine Hierarchie aus Bounding Volumes mitgeführt. Jedem Knoten ist also zusätzlich ein Bounding Volume zugeordnet, das die räumliche Ausdehnung des Knotens samt Kindknoten anzeigt. Als Bounding Volumes werden einfache geometrische Körper wie achsenparallele Quader (AABBs), am Objekt ausgerichtete Quader (OBBs) oder Kugeln verwendet.
Mit Hilfe der Bounding Volumes werden dann vor dem Rendervorgang alle unsichtbaren (also nicht im View Frustum liegenden) Elemente bestimmt. Wenn ein Knoten bereits als nicht sichtbar klassifiziert wurde, ist eine Überprüfung seiner Kindknoten nicht mehr notwendig. So kann mit geringem Aufwand die Menge der Geometrie, die potentiell sichtbar ist und darum gerendert wird, verringert werden.