ntree und binäre bäume

[Parapiler]

Hallo.

Also zuerst einmal weiss ich nicht ob die Frage hierrein muss oder in die Spieleentwicklung. Die Anwendung die entsteht die gehört zweifelsohne der Spieleentwicklung an, meine Frage gehört aber meiner Meinung eher hierhin. Falls ich mich irre, verschiebt den Thread bitte....

Also ich habe folgendes Problem:

Es geht darum einen Scenegraphen zu schreiben. Ich wollte dazu einen Datentyp schreiben, der in der Lage ist, Daten aufzunehmen, die so angeordnet sind wie im Explorer. Die Daten werden 3d Objekte sein, aber das ist für die Sache nicht so wichtig. Die Problematik ist die, dass zu einem Objekt eventuell weitere Objekte gehören, die sich genauso verhalten müssen wie der Vater.

Beispiel:

root

raumschiff
antriebspartikel
waffen
schilde
mensch
waffe
kugel

das ganze muss sogemacht werden, weil zum beispiel wenn sich der mensch bewegt, die waffe sich mitbewegen muss, wenn die waffe sich bewegt, die Kugel sich mitbewegen muss usw.

Jetzt meíne Fragen:

a.) Welchen Vorteil bietet ein Octree (über den es hier auch schon was gibt) ?
b.) Welchen Vorteil bietet ein Quartree?
c.) ist ein Octree und ein Quatree nur ein Spezialfall eines ntrees ?
d.) wie implementiere ich einen ntree?

Gruß Para

[godlikebot]

Ein Octree hat nicht viel mit Scene Management zu tun. Es ist ein Space partitioning Algo. Ein Octree ist übrigens das gleiche, wie ein Quadtree (Ich glaube, das meintest du). Ich hab den Link schonmal im Grafik forum gepostet: http://www.gametutorials.com/Tutorials/OpenGL/Octree.htm

Ich kenne aber auch noch ein gutes Tutorial zu Scenegraphs, dass wahrscheinlich, die meisten deiner Probleme lösen wird: http://www.gamedev.net/reference/articles/article1812.asp

[HumeSikkins]

Hallo,
ich denke, dass diese Frage im Spiele-/Grafikforum besser aufgehoben ist.

[C++ Forumbot]

Dieser Thread wurde von Moderator/in HumeSikkins aus dem Forum C++ in das Forum Spiele-/Grafikprogrammierung verschoben.

Im Zweifelsfall bitte auch folgende Hinweise beachten:
C/C++ Forum :: FAQ - Sonstiges :: Wohin mit meiner Frage?

Dieses Posting wurde automatisch erzeugt.

[rapso]

godlikebot schrieb:

Ein Octree hat nicht viel mit Scene Management zu tun.

damit wäre eigentlich deine ganze frage ausgehebelt, aber es ist so, scene graph und cullingtree sind verschiedene dinge.

godlikebot schrieb:

Ein Octree ist übrigens das gleiche, wie ein Quadtree (Ich glaube, das meintest du). Ich hab den Link schonmal im Grafik forum gepostet: http://www.gametutorials.com/Tutorials/OpenGL/Octree.htm

quadtree ist 2D, Octree ist 3D, sagen wir mal "fast das gleiche"

besorg dir ein buch über engine design, z.b. "3D Game Engine Design" von "David H. Elbery"

rapso->greets();

[Parapiler]

hmmm also:

der unterschied zwischen einem Octree und einem Quadtree is doch erstmal die anzahl der zweige oder? hat nen Octree nicht 8 und nen Quadtree 4? was hat das denn jetzt mit 2d oder 3d zu tun? Das verstehe ich noch nicht....

Was das Buch angeht. Ich bin gerne bereit mir ein zu kaufen, allerdings muss es dann seinen Sinn auch erfüllen. Welches der beiden obrigen würdet ihr denn empfehlen? Oder noch ein ganz anderes??

Weitere Frage: wenn ein Quadtree für 2d ist und ein Octree für 3d, wozu ist dann ein ntree?

Gruß Para

[TGGC]

der unterschied zwischen einem Octree und einem Quadtree is doch erstmal die anzahl der zweige oder?

Ja.

hat nen Octree nicht 8 und nen Quadtree 4?

Ja.

was hat das denn jetzt mit 2d oder 3d zu tun?

2^2 = 4 und 2^3 = 8.

wenn ein Quadtree für 2d ist und ein Octree für 3d, wozu ist dann ein ntree?

Für Fälle, in denem man n Kinder benötigt.

Bye, TGGC (Hast du's drauf?)

[Parapiler]

ich verstehe deine Rechnung nicht!

wieso machst du alles auf der basis 2?

[rapso]

quadtrees werden benutzt um 2D aufzuteilen, deswegen werden aus einem vierecke, 4 vierecke gebildet. so teilt man 2d gebilde auf, z.b. den blidschirm beim raytracen. beim octree zerteilt man einen 3D raum in würfel, man hat dann 3 coordinaten die man zerteilt.

raum -> würfel -> 3d -> octree
fläce -> vierecke -> 2d -> quadtree
(strahl -> strecken -> 1d -> binärtree )

rapso->greets();

[godlikebot]

Quadtree(2D): http://alff.funbad.de/quadtree.gif
Octree(3D): http://www.flipcode.com/tfiles/octree-node.jpg

EDIT: Die Bilder zeigen immer die simpelste Unterteilungstiefe von 1. Man kann die einzelnen Vierecke bzw. Quadrate ja immer weiter aufteilen.

[TGGC]

Parapiler schrieb:

wieso machst du alles auf der basis 2?

Weil beim teilen 2 Teile rauskommen. (Norden/Süden, Osten/Westen, oben/unten)

Bye, TGGC (Hast du's drauf?)

[Parapiler]

Also ich habe nochmal eine Frage

Oben hat ja jemand ein Tutorial zu Scenegraphen gepostet. Ich habe das mir mal angeguckt und angefangen, nach diesem Tutorial einen Scenegraphen aufzusetzen. Allerdings tue ich mich mit dem verständnis des Tutorials sehr schwer. Besonders schwierig ist für mich der folgende absatz:

Rendering a Node
Since each object does not directly know anything more than the offset from its parent, we define that object to be in object space ? also known as local space. In our example with the monster truck, each wheel doesn't necessarily need to know about anything except its offset from the truck body. But in order to render an object, the renderer needs to know exactly where in world space that object will be. To know what the world space of this object is, the renderer would have to concatenate all transformations from the node it wants to draw to each parent up to the root of the tree. This is not a practical approach, so a simple way to speed this process up could be to force each node to keep a world matrix locally that is only updated if the parent (or any grand-parent of this node) has changed in some way. Then rendering a node is just a simple matter of multiplying the parent's world matrix with the object's model matrix, and drawing that node. Since space is limited, check out my web page for a more detailed explanation.

Recursive Iteration of the Scene Graph
Many beginning programmers cringe when they hear the word recursion, but any time you hear the word tree (as related to programming), you'd better get used to recursion. Recursion itself is a beautiful and painless technique normally used to reduce your problem to its simplest terms if you understand what is actually going on. Recursion for our scene graph is simple and necessary.

There are two ways to traverse any kind of tree: Breath-first, and Depth-first. Breath-first traverses a tree from left to right in any level before going to the next depth, and Depth-first traverses down the tree first and only goes back up when it can't go down anymore. Because of our hierarchy, it makes the most sense to update and render the scene depth-first in a sort of "in-order" fashion (see Figure 1).

To actually update and render the scene, the base object, FFObject, will contain virtual functions for updating and drawing the object. Each object will override this function so that the update and drawing is done correctly for that object. There will be at least two recursive passes each frame, one for updating and one for drawing. All objects will update their transformations based on their parents' transformations, but not all objects will need to draw. Lights and Sounds usually don't do anything in the draw functions, except maybe in debug mode where you might want to draw widgets to show where they are in the world.

To recursively update the scene, the function might look like this:

void FFSystem::UpdateScene(FFObject* pObject,
                           float fElapsedTime)
{
  // Base case for the recursion
  if (pObject == NULL)
    return;

  else
  {
    // Update this object.
    pObject->Update(fElapsedTime);

    // Recursively call all children
    vector<FFObject*>::iterator it =
                   pObject->GetChildList()->begin();

    for (;it != pObject->GetChildList()->end(); ++it)
      UpdateScene(*it, fElapsedTime);
  }
}

//edit by rapso

Rendering the scene looks exactly like the above code with the Update function replaced with the Draw function.

Bis zu dem Code bin ich nicht einmal gekommen, obwohl da noch hinzukommt, dass mir noch nicht klar ist was ein Iterator ist, weil ich mit der stl nie gearbeitet habe. Da werde ich jetzt gleich aber direkt mal nach Tutorials suchen.

Vielleicht kannn mir dort ja einer weiterhelfen, was in dem Abschnitt gemacht wird.

Ein Anderes Problem ist dies hier: Ich habe ja jetzt wie in dem Tutorial ´beschrieben eine Klasse erstellt. Diese Klasse hat ja 2 rein virtuelle Methoden, also ist die Klasse abstrakt. Wie kann ich denn nun Objekte zu dem Scenegraphen hinzufügen? Ich darf ja keine Instanz von der Klasse machen....

Gruß Para

[godlikebot]

Angenommen in deinem Spiel gibt es ein Scenegraph Objekt namens Mensch. Dieser Mensch besteht aus vielen Teilen. Zwei davon sind: "Körper" und "Arm".

Beispiel:
Der Körper befindet sich an der ("absoluten") Position (0, 0, 0) und der Arm an der ("absoluten") Position (12, 0, 0). Wenn der Körper nun an die Position (0, 0, 10) wechselt, bleibt der Arm immer noch auf seiner alten Position (12, 0, 0). Deswegen hat der Autor ein anderes System gewählt.
Der Arm und der Körper haben mit diesem anderen System nicht mehr absolute, sondern relative Koordinaten. Das heisst, wenn der Arm die Koordinaten (12, 0, 0) hat, befindet sich 12 Einheiten rechts vom Körper. Wenn der Körper nun seine Position ändert, befindet sich der Arm immer noch 12 Einheiten rechs vom Körper.

Ich hoffe das war verständlich

Object-Oriented Scene Management schrieb:

In our scene graph, we will need a base class object that will take on the role of a mold for all objects that will be derived from it. [...] Let's call this base class FFObject

[TGGC]

Ein Anderes Problem ist dies hier: Ich habe ja jetzt wie in dem Tutorial ´beschrieben eine Klasse erstellt. Diese Klasse hat ja 2 rein virtuelle Methoden, also ist die Klasse abstrakt. Wie kann ich denn nun Objekte zu dem Scenegraphen hinzufügen? Ich darf ja keine Instanz von der Klasse machen....

Each object will override this function so that the update and drawing is done correctly for that object.

Lesen ist was Feines.

Bye, TGGC (Hast du's drauf?)

[Parapiler]

ja das war jetzt schon verständlich..... aber ich komm damit mit meinem problem immer noch nicht weiter

1.) Der Kern meines Problems ist glaub ich, dass mir nicht klar ist, so wie es im Tutorial steht, dass jedes Child des Scenegraphen eine eigene Transformationsmatrix hat. Eine Transformationsmatrix ist doch die Matrix, die ein Objekt entlang der x- y- oder z-Achse verschiebt oder (bzw. einer kombination dieser)? Wie ist das denn Programmiertechnisch zu realisieren?

2.) Okay es ist logisch, mit relativen Koordinaten zu arbeiten. Aber wie implementiere ich das jetzt?

3.) Wie kriege ich denn jetzt Objekte in meinen Scenegraphen? Der redet da von Licht oder Kameraobjekten und das es egal ist, was der Scenegraph handeln soll. Ich will zuerstmal ein ausgelesenes 3d objekt dort reintun und dem Renderer sagen, dass er dieses Rendern soll. Dabei habe ich folgendes Problem:

Wie im Tutorial beschrieben gibt es 2 Methoden im Scenegraphen, die pure virutual sind. Diese sind die Methoden draw und update. Weiterhin steht im Tutorial, dass der Scenegraph benutzt wird, indem man davon ableitet. Am besten gebe ich euch mal meinen klassenheader auch wenn er schon fett ist dann seht ihr das problem. Ich kann ja vom Scenegraphen kein Objekt machen.... nur von einer Abgeleiteten Klasse vom Scenegraphen.... aber das ist bisher mein Renderwindow.....

/*die Klasse aus dem Tutorial (der Scenegraph) ist das hier */
class CFlBase 
{
	public:
		CFlBase (void);
		~CFlBase (void);
		bool flSetParent (CFlBase* ptr_parent);
		bool flAttachChild (CFlBase* ptr_child);
		virtual int flRender (float fl_felpasedTime) = 0;
		virtual int flUpdate (float fl_felpasedTime) = 0;
		std::vector <CFlBase*>* flGetChildList (void);
	private:
		std::vector<CFlBase*> m_ch_list;
		CFlBase* m_ptr_parent;
	protected:
};

/*das hier ist mein Renderfenster, also die Klasse davon. Ich habe sie im Laufe
  des Tutorials vom Scenegraph abgeleitet (ist das richtig ?!). Dies ist  
  wiederum eine abstrakte Klasse, was den sinn hat, dass es weitere Klassen 
  geben muss, damit das ganze auch auf anderen Plattformen läuft (Windows,
  sdl, glut, qt) */ 
class CFlRenderWindow : public CFlBase
{

	public:
		virtual int flCreate (RENDERCREATE* ptr_render) = 0;
		virtual int flMain (RENDERCREATE* ptr_render) = 0;
		virtual int flAddGlProperty (void) = 0;
		virtual void flResizeGl (int flWidght, int flHeight) = 0;
		virtual int flInitGl (RENDERCREATE* ptr_render) = 0;
		virtual int flKillWindow (RENDERCREATE* ptr_render) = 0;   
	private:
	protected:

};

/*das renderfenster für windows*/
class CFlGlWindows : public CFlRenderWindow
{
	public:
		CFlGlWindows (void);
		~CFlGlWindows (void);

		/* * * * * * * * * * * 
		 * window creation   *
		 * * * * * * * * * * */
		static LRESULT CALLBACK window_proxy (HWND hWnd, UINT msg, WPARAM wParam, LPARAM lParam);
		LRESULT CALLBACK WndProc (HWND hWnd, UINT msg, WPARAM wParam, LPARAM lParam);
		virtual int flMain (RENDERCREATE* ptr_render);
		virtual int flAddGlProperty (void);
		virtual int flCreate (RENDERCREATE* ptr_render);

		/* * * * * * * * * * * 
		 * OpenGL part       *
		 * * * * * * * * * * */
		virtual void flResizeGl (int flWidght, int flHeight);   
		virtual int flInitGl (RENDERCREATE* ptr_renderd);                           
		virtual int flRender (float fl_felpasedTime);                          
		virtual int flRenderScene (CFlBase* ptr_object, float fl_felpasedTime);
		virtual int flUpdate (float fl_felpasedTime);
		virtual int flUpdateScene (CFlBase* ptr_object, float fl_felpasedTime);
		virtual int flKillWindow (RENDERCREATE* ptr_render);                      
	private:
		HWND hWindow;             /*window handle*/
		HDC hdc;                   /*drawing context*/
		HGLRC hgl;                /*render context*/
		bool b_keys [256];        /*array of key flags*/
		bool b_fullscreen;        /*fullscreen flag*/
		bool b_activate;          /*window activating flag*/
		PIXELFORMATDESCRIPTOR px;
	protected:
};

[TGGC]

[...]dass jedes Child des Scenegraphen eine eigene Transformationsmatrix hat. Eine Transformationsmatrix ist doch die Matrix, die ein Objekt entlang der x- y- oder z-Achse verschiebt oder (bzw. einer kombination dieser)? Wie ist das denn Programmiertechnisch zu realisieren?

Sie beschreiben alle Transformationen und nicht nur Translationen. Realisieren kannst du das einfach, indem jedes Child eine solche Matrize als Attribut bekommt.

Okay es ist logisch, mit relativen Koordinaten zu arbeiten. Aber wie implementiere ich das jetzt?

Die einfach Abspeichern?

Wie kriege ich denn jetzt Objekte in meinen Scenegraphen?

SceneRoot sr;
Modell3D m3dTeil( "dateiname.3d");
sr.addChild( m3dTeil );

Bye, TGGC (Hast du's drauf?)

[godlikebot]

Parapiler schrieb:

das hier ist mein Renderfenster, also die Klasse davon. Ich habe sie im Laufe des Tutorials vom Scenegraph abgeleitet (ist das richtig ?!)

Nein! Google dir einfach mal ein paar Informationen über Scenegraphs zusammen. Auf einen Scenegraph gehören nur Sachen, die eine Szene beschreiben und darin auftauchen. Zum Beispiel ein Haus, ein Teich und ein Vogel. Dein Renderfenster gehört meiner Meinung nach nicht auf einen Scenegraph.