Last Update: 

         Rendering eine Scenegraphen
        =============================
 
  Vorraussetzungen
 ------------------
 Im letzten Artikel "What is a Scenegraph" bin ich auf die grundlegenden Datenstrukturen und Ausgaben eine Scenegraphen eingegangen. In diesem Artikel möchte ich einige Strategien zum Rendern (Darstellen) eines Scenegraphen behandeln. Es ist hilfreich, wenn man mit den Grundlagen von OpenGL und 3d-Grafik vertraut ist, um die Ideen hier nachvollziehen zu können.
 
 
  Unterteilung der Aufgaben
 ---------------------------
 Der Scenegraph soll die Scene mit all ihren Abhängigkeiten verwalten. So können zum Beispiel Geometrie-, Physikaktualisierungen und Szenenoptimierungen durchgeführt werden, bevor der aktuelle Frame gezeichnet werden soll. Um die Struktur dabei nicht unnötig kompliziert zu machen, ist eine Trennung zwischen Szenenverwaltung und Renderer sinnvoll. Es gibt allerdings verschiedene Konzepte, wie hier die Architektur aufgebaut sein kann. In diesem Artikel gehe ich davon aus, dass die Renderfunktionen bereits fertiggestellt sind. Es wird im wesentlichen auf die Art und Weise eingegangen, wie eine Scene-Hierarchie gerendert werden könnte.
 
 1.) Rendertraverer:
 Der Renderer sieht den Scenegraphen nur als Info-Struktur und traversiert die jeweiligen Abhängigkeitsbäume selber ab, um die benötigten Transformationsstates zu erhalten. Im wesentlichen würde das bedeuten, dass im Renderer so etwas wie  eine Updatemethode vorhanden ist:
 
 Beispiel:
class Node {
 protected:
	// Liste aller Child-Knoten
	list<Node*> m_lNodes;
	
	// Renderobjekt 
	RenderObject *m_pRenderObj;
	
 public:	
	// Konstruktor / Destruktor
	Node();
	~Node();
	...
	// Aktualisiert sich slebst und alle Childnodes
	void Update() {
		for (std::list<Node*>::iterator it = m_lNodes.begin(); it != m_lNodes.end(); ++it) {
			(*it)->Update();
		}
	}
	
	// Rendert sich selbst und alle Childnodes
	void Render(Renderer *pRenderer) {
		pRenderer->PushMatrix();
		m_pRenderObj->Render(pRenderer);
		for (std::list<Node*>::iterator it = m_lNodes.begin(); it != m_lNodes.end(); ++it) {
			(*it)->Render(pRenderer);
		}
		pRenderer->PopMatrix();
	}
 };
 
Der Renderer muss nun eine Methode bekommen, um die Scene-Hierarchie traversieren zu können. Das könnte das beispielsweise so aussehen:
 
 // Beispiel Renderer
 class Renderer {	
  public:
	// Konstruktor / Destruktor
	Renderer();
	~Renderer();
	
	// Traversiert die Nodes und aktualisiert sie
	UpdateScene(Node *pRoot) {
		// Update transformation states
		pRoot->Update();
	}
	
	// Traversiert alle Nodes und rendert ihre Renderobjekte
	void RenderScene(Node pRoot) {
		this->BeginScene();
		pRoot->Render(this)
		this->EndScene();
	}
	
	// Tools für Matrixstack
	void PushMatrix(); {
		glPushMatrix();
	}
	void PopMatrix(); {
		glPopMatrix();
	}
	
	// Render Vorbereitungen
	void BeginScene() {
		// Dinge wie Clear, Initialisieren benötigter Datenstrukturen für nächsten Frame etc.
	}
	
	// Abschliessende rbeiten für Frame
	void EndScene() {
		// Swapbuffer etc.
	}
};

// Rendercode im Mainloop
Renderer *pRenderer = new Renderer();
pRenderer->UpdateScene(&Root);
pRenderer->RenderScene(&Root);

Solch ein Rendertraverser kann eine komplette oder auch nur Teile von Nodehierarchien per Argument zugewiesen bekommen und diese dann entsprechend updaten und auf den Bildschirm rendern. Die Nodehierarchien können frei verwaltet werden, eine zentrale Fassade wie ein Szenen-Manager wird in diesem Fall gar nicht benötigt.
Viele Engines benutzen diese Form des Scenegraph-Renderns, da es einfach in der Handhabung und schnell zu verstehen ist. Grundlegende Informationen wie Kollisionsabfragen oder physikalische Informationen müssen jedoch separat behandelt werden.

2.) Scenegraph use Renderer
Der Scenegraph stellt ein grundlegendes Interface für den User bereit, der Renderer ist ein Subsystem des Scenegraphen, so dass der Anwender den Renderer gar nicht erst benutzen muss. Da gerade bei komplizierteren Szenen mit viele verschiedenen Effekten wie Enviroment-Mapping, Blending etc. das benötigte Interface des Renderers sehr kompliziert sein kann, ist es mit der Kapselung des Renderers durch den Scenegraphen möglich, diese Komplexität so weit wie möglich zu verbergen.

Die Benutzung des Renderer durch den Scenegraphen kann auf verschiedenen Wegen erfolgen.

 - Scenegraph traversiert und aktualisiert alle verwalteten Nodes. Nodes implementieren das rendern selber und rufen den Renderer selbst auf. Dieses Beispiel konnten wir m ersten Teil dieser Artikelserie sehen.
   
 - Scenegraph benutzt Visitoren, um Render-Implementierung zentral vorliegen zu haben. Nodes bilden bei diesem Design nur spezielle Eigenschaften wie Geometrie-Zustände oder physikalische Abhängigkeiten ab. Sie implementieren nicht ihren eigenen Render-Code.

   Um die 2. Möglichkeit vertiefen zu können, ist es sinnvoll, sich zunächst das Visitor-Pattern näher zu betrachten:

Das Visitorpattern bietet eine Möglichkeit an, Objekt und Algorithmus voneinander zu separieren. Aus diese Weise muss in unserem  Fall die Implementierung des Nodes nicht varriiert werden, um auf einen neueren Algorithmus angepasst zu werden. Die genaue Funktionsweise sowie Hinweise zur IMplementierung und Funktion kann man [1] entnehmen.
Um den Node mittels eines Visitors aktualisieren zu können, muss das Node-Interface etwas erweitert werden:

class Node {
 public:
	...
	// Wird vom Visitor gerufen
	void Accept(Visitor *pVisitor) {
		pVisitor->VisitNode(this);
	}
	...
};

Nun können wir den Visitor implementieren, der die Node besuchen soll:

class Visitor {
 public:
	Visitor();
	virtual ~Visitor();
	
	// Hier wird der Node besucht
	virtual void VisitNode(Node *pNode) =0;
};

Will man nun den Algorithmus für alle Nodes varriieren, muss nur die entsprechende VisitNode-Methode des Visitors geändert werden. Im Scenegraph kann man nun mehrere Nodevisitoren vorsehen, die sich um Dinge wie Rendering, Traversierung, Physik oder Culling kömmern sollen:

class SceneGraph {
 private:
	Node *m_pRoot;
	std::list<Node*>	m_NodeList;
	std::list<Visitor*>	m_lVisitorList;
 
 public:
	// 
	SceneGraph();
	~SceneGraph();
	
	// Methode zum Anfügen neuer Visitoren
	void AddVisitor(Visitor *pVisitor) {
		m_lVisitorList.push_back(pVisitor);
	}
	
	// Aktualisiert alle Nodes, indem diese von den registrierten Visitoren
	// besucht werden
	void Update() {
		std::list<Node*>::iterator it_node;
		std::list<Visitor*>::iterator it_visitor;
		for (it_visitor = m_lVisitorList.begin(); it_visitor != m_lVisitorList.end(); ++m_lVisitorList) {
			for (it_node = m_NodeList.begin(); it != m_NodeList.end(); ++m_NodeList) {
				(*it_visitor)->VisitNode(*m_NodeList);
			}
		}
	}
};

Ein Rendernode-Visitor könnte nun die folgende stark vereinfachte Form annehmen:

class RendernodeVisitor : public Visitor {
 private:
	Renderer *m_pRenderer;
	
 public:
	RendernodeVisitor();
	~RendernodeVisitor();
	
	// Einfaches Beispiel
	virtual void VisitNode(Node *pNode) {
		pNode->Render(pNode->GetRenderObject());
	}
};

Will man nun die Art und Weise des Rendern im Rendermodul neu implementieren, muss man nur den RendervodeVisitor neu  implementieren. Die Node-Interfaces bleiben davon weitesgehend unbeeindruckt. Dazu hat man mittles dieses Design-Pattern eine Variante bei der Hand, um weitere Algorithmen ohne grosse Änderungen in das Framework integrieren zu können.

[1]   http://www.informatik.fh-muenchen.de/~schieder/seminar-oo-modellieren-ws97-98/f7alpha1.informatik.fh-muenchen.de/~ifw93027/visitor.html