Was ist ein Scenegraph ------------------------ Wenn man sich mit 3D-Grafik beschäftigt, wird man irgendwann mit der Tatsache auseinandersetzen müssen, die zu renderndern Daten zu verwalten und Abhängigkeiten untereinander abbilden zu wollen. Hat man nun die komplette Szene in einem Vertex-Array, wird es schwer bis unmöglich, die jeweiligen Relationen der einzelnen Vertices zu verwalten und entsprechend zu modifizieren. Benutzt man statt dessen verschiedene Vertexbuffer beziehungsweise Renderobjekte (gemäss dem Motto, Teile und herrsche), steht man vor dem Problem, die Abhängigkeiten der verschiedenen Objekte zu verwalten. Aber glücklicherweise gibt es bereits einige fertige Algorithmen und Datentypen. Graphen und Bäume: -------------------- Graphen stellen einen fundamentalen Datentyp in der Informatik dar. Eine spezielle Form des Graphen ist der Baum: Ebene 0 Root / \ Ebene 1 Child Child / | \ Ebene 2 C C C Es gibt dabei einen Rootnode (Wurzel), dieser hat verschiedene Childnodes. Jeder Childnode hat mindestens einen Parentnode und kann selbst verschiedene Childnodes haben. Wenn es jeweils pro Node nur höchstens 2 Nodes gibt, bzeichnet man das Konstrukt als ein binären Baum. Die jeweiligen Childnodes haben in einem normalen Baum nur Beziehungen zum Parent und zu den jeweiligen Childnodes, Graphen können auch in sich geschlossene Gebilde sein: Ebene 0 Root / \ Ebene 1 Child-Child / | \ Ebene 2 C C C In der Ebene 1 gibt es in diesem Beispiel eine Relation zwischen den beiden Childnodes, die den Rootnode als Parent haben. In diesem Text möchte ich diesen Sonderfall aber der Einfachheit halber unberücksichtigt lassen. Möchte man nun alle im Baum verwalteten Childs durchlaufen, nennt man diesen Vorgang traversieren. Mittels einer doppelt verketteten Liste lässt sich dieser Vorgang relativ schnell implementieren. Dafür wird auf die STL-List-Implementierung zurückgegriffen: typedef std::list Nodes class Node { protected: // Liste von Childnodes des Knoten Nodes m_lNodeList; const char *m_pName; public: // Konstruktor / Destruktor Node(const char *pName); ~Node(); // Traversiere Childnode-Liste und aktualisiere Daten virtual void Update(); // Füge neuen Childnode hinzu void Add(Node *pChild); // Finde einen Knoten in der Hierarchie Node *Find(const char *pName); // Lösche Childnode void Delete(const char *pName); // Gebe Speicher des Nodes frei void Release(void) { delete this; } // Gebe Childliste frei void Destroy(); // Gibt den Namen des Nodes zurück const char *GetName() const { return m_pName; } }; // Konstruktor Node::Node(const char *pName) { m_pName = new char[strlen(pName)]; strncpy(m_pName, pName, strlen(pName)); } ... // Durchlaufe Child-Liste void Node::Update() { Nodes::iterator it; for (it = m_NodeList.begin(); it != m_NodeList.end(); it++) { (*it)->Update(); } } // Füge Childs hinzu void Node::Add(Node pChild) { ... m_lNodeList.push_back(pChild); ... } // Finde einen Knoten Node *Node::Find(const char *pName) { assert (NULL != pName); Node *pNode = NULL; Nodes::iterator it; for (it = m_NodeList.begin(); it != m_NodeList.end(); it++) { if (0 == strncmp(m_pName, (*it)->GetName(); strlen(m_pName))) { pNode = *it; break; } (*it)->Find(pName); } return pNode; } // Löscht einen Childnode void DeleteChild(const char *pName) { Nodes::iterator it; for (it = m_NodeList.begin(); it != m_NodeList.end(); it++) { if (strncmp((*it)->GenName(), pName, strlen(pName))==0) { m_NodeList.erase(it); break; } } } // Release Childliste void Node::Destroy() { Nodes::iterator it; for (it = m_NodeList.begin(); it != m_NodeList.end(); it++) { this->Release(); } } Das Interface an sich ist sehr einfach gehalten. Man kann Childnodes an einem bestehenden Node anfügen, Childnodes aus dieser Liste entfernen. Dazu gibt es die Möglichkeit, den Status und die Daten des Nodes aktualisieren zu lassen. Destroy sorgt dafür, dass die Daten des Nodes ordnungsgemäss wieder entfernt werden. Dazu bekommt jeder Node einen Namen, den der Anwender zu diesem Zeitpunkt noch selbst eindeutig vergeben muss. Will man einem Childnode neue Childnodes hinzufügen, so muss man in der verwalteten Hierarchie zunächst diesen Node mittels find finden. Danach kann man einen neuen Node anfügen. Idee des Scenegraphen: Beispiel Geometrie-Hierarchie ------------------------------------------------------ Ein SceneGraph wird benutzt, um die verschiedenen Beziehungen der Objekte untereinander zu verwalten. Diese Abhängigkeiten werden in Form von Bäumen abgebildet. Es kann verschiedene Formen der Abhängigkeiten geben: - Gemoetrische Abhängigkeiten (z.B. eine Lampe, die auf einem Tisch steht) - Physikalische Abhängigkeiten (z.B. Metall, dass von einem Magneten angezogen wird) - Abhängigkeiten zum Rendern (z.B. für Blending) Um das grundlegende Prinzip zu verdeutlichen, wollen wir zunächst die geometrische Abhängigkeit einer Lampe auf einem Tisch etwas genauer betrachten: Der Tisch steht auf einem Fussboden, auf dem Tisch wiederum steht eine Lampe. Verschiebt man nun den Tisch, interessiert das die Bewegung des Fussbodens relativ wenig, die Lampe jedoch wird diese Verschiebung ebenfalls betreffen, da sie auf dem Tisch abgestellt wurde. Dementsprechend kann man aus diesem Zusammenhang einen Baum entwickeln, der diesen geometrischen Sachverhalt beschreibt: Boden / \ Stuhl Tisch | Lampe Verschiebt man den Tisch, kann mann die Lampe gleich mit bewegen: - Verschiebe Tisch \ Verschiebe Lampe Der von uns entwickelte Node soll nun herangezogen werden, um diese kleine Szene abzubilden. Der ursprüngliche Node bietet ufgrund seines Interfaces zwar einige Dinge wie die Traversierung aller Childnodes beim Update bereits an, jedoch fehlt noch eine Spezialisierung auf den konkreten Anwendungsfall. Daher leiten wir vom Node einen GeoNode ab, der Transformations-Informationen eines Knotens abbildet: Code: // Geometrieklasse zum Verwalten und Rendern von Meshes class GeoNode : public Node { private: // Transformationsregeln Vector3f *m_pTrans; Vector3f *m_pRot; Vector3f *m_pScale; // Renderobjekt RenderObject *m_pRenderObject; public: // Methoden zum Setzen von Rotationen und Translationen void SetTranslate(float x, float y, float z); void SetRotate(float ex, float ey, float ez); ... void Update(); ... }; // Aktualisierung eigener Geostate + alle Childnode-Geostates void GeoNode::Update(void) { glPushMatrix() // Transation, Rotation und Skalierung glTranslate(m_pTrans->GetX(), m_pTrans->getY(), m_pTrans->GetZ()); glRotate(m_pRot->GetX(); m_pRot->GetY(), m_pRot->GetZ()); glScale(m_pScale->GetX(), m_pScale->GetY(), m_pScale->GetZ()); // Zeichne zugeordnetes Mesh m_pRenderObject->Render(); // Traversiere Geostates aller Childnodes Node::Update(); glPopMatrix() } Mittels des Updates wird zunächst die aktuelle Transformationsmatrix gesichert, danach wird das dem Node zugeordnete Mesh transformiert und gerendert. Danach können die weiteren Childnodes gerendert werden. Das Push / Pop für die aktuelle Transformationsmatrix wird notwendig, um den aktuellen Transformationszustand des aktuellen Nodes zu sichern. Mehr dazu kann man unter http://www.opengl.org [7] finden. Ein weiteres Beispiel kann man unter [1] finden. Ausdehnung des Konzeptes -------------------------- Das beschriebene Verfahren kann auch auf andere Zusammenhänge angewendet werden. In einer Game-Library will man beispielsweise Dinge wie physikalische Zusammenhänge verwalten. Wenn man sich ein Rad eines Autos ansieht, ist dieses über die Achsen mit dem Rest des Autos verbunden. Die Achsen wiederum werden über Stossdämpfer an die Karosserie angebunden. Die Stossdämpfer übertragen aber nicht die komplette Verschiebungen, sondern dämpfen einen Teil weg. Diese Dämpfung kann man vereinfacht durch eine Federkonstante ausdrücken: F = D x s F ... Kraft D ... Federkonstante s ... Weg Nehmen wir an, die Federkonstante hat den Wert 10 [N/m] inne, und wir betrachten die Kraft als Relativverschiebung abhängig von der letzten Verschiebung (sagen wir 1 Einheit), so kann man die Verschiebung um 1 Einheit in der Wirkungsrichtung zurückrechnen. Bilden wir dieses in Graphenform ab, bekommen wir die folgenden 2 Bäume: Geometrie-Abhängigkeits-Baum: Auto-Karrosserie / \ Achse Achse hinten vorn / \ / \ R1 R2 R3 R4 Physik-Abhängigkeits-Baum: Auto-Karosserie / \ Achse Achse hinten vorn / | | \ Feder1 Feder2 Feder 1 Feder 2 (D = 2) (D = 2) (D = 4) (D = 4) Nach dem Durchlaufen wird die Relativverschiebung in Wirkungsrichtung der Feder 1 von 2 Einheiten bestimmt. Die dämpfende Eigenschaft ermittelt eine Rückstellung von: 2 = 2 x s -> s = 1 ----- Die Achse muss um eine Einheit zurück bewegt werden. Diese Zusammenhänge kann man genau wie die Geo-Liste traversieren, um die physikalischen Relationen abzuarbeiten. Dabei muss aber zunächst der Geometrie-Baum abgearbeitet werden, schliesslich benötigt der hier beschriebene Algorithmus zunächst eine Verschiebung. Da hier nach der Aktualisierung der Geometriezustände eine weitere Modifokation der Geometrie notwendig sein kann, ist es nicht mehr so ohne weiteres möglich, das Rendern des Nodes direkt im GeoNode zu implementieren. Culling --------- Gerade bei vielen Nodes steigt der Aufwand zum Zeichnen der Geometrie stark an. Um die benötigte GPU-Zeit zu minimieren, gibt es verschiedene Möglichkeiten, nicht sichtbare Teile des Meshes auszublenden. Die zugrundeliegende Idee kann unter [8] und [9] nachgelesen werden. Im wesentlichen erhält ein GeoNode noch eine Box, die die verwaltete Geometrie komplett umschliesst. Man kann nun testen, ob diese Box im Viewfrustum (Sichtkegel der Kamera in Form eines Pyramidenstumpfes) des aktuellen Viewport ist. Ist das nicht der Fall, muss der GeoNode nicht gezeichnet werden. Dieser Test bezieht sich auf den Transformationszustand, der gerendert werden soll. Daher müssen alle möglichen Modifikationen der Transformations-Zustände bereits abgeschlossen sein. Details für verschiedene Anwendungen kann man unter [9] finden. Rendering ----------- Werden nach der Aktualisierung der Transformationen der verschiedenen Geo-Nodes noch Optimierungen wie Culling eingeführt, kann das Rendern nicht mehr direkt im Geo-Node erfolgen. Des weiteren können vor und nach dem Rendern noch Pre- und Post- prozessing-Schritte für Vor- und Nachverarbeitung des zu rendernden Frames notwendig sein. Daher braucht man ein Design, welches diese Schritte und Optimierungen möglich macht und dabei nach Möglichkeit leicht ausbaubar sein sollte. Auf dieses werde ich im Artikel render_a_scenegraph.txt eingehen. MfG Kimmi Meine Email: sir_kimmi@gmx.de HP : http://www.sir-kimmi.de [1] http://www.gamedev.net/reference/articles/article2028.asp [2] Entwurfsmuster, Erich Gamma, ... [3] http://www.zfx.info [4] http://www.nist.gov/dads/HTML/directAcycGraph.html [5] http://www.r3vis.com/Downloads/SceneGraphPanelProposal-Siggraph99.pdf [6] http://www4.tomshardware.com/column/20000110/index.html [7] http://www.opengl.org [8] http://www2.ravensoft.com/users/ggribb/plane extraction.pdf [9] http://www.flipcode.com/articles/article_frustumculling.shtml