# Creating a Scene Graph Questions

## Recommended Posts

I know there have been a lot of posts about this topic in the past, and I understand the jist of scene graphs, (1) just how do you create them? When loading objects, how should nodes be made, and then connected? (2) Another "problem" I dont understand, is the scene graph is constantly changing, so how would you change parents / children. This is how I am thinking of structuring it ( have not done this before so any tips would be good ;) )
Base
|
Quadtree Terrain ( any lod method )
|-> Terrain Node 1
|-> another quadtree to get finer culling of objects
|- Node
|    |---------------> Some 3d obj
|    			|-----------> obj fx
|- Node
|    |----------------> Torch
|    |		        |----------------> Torch FX
|    |---------------> Player
|- Node
|    |---------------> Gun
|- Node
|-> Terrain Node 2
|-> another quadtree to get finer culling of objects
|- Node
|    |--------------->Car

Say the player picks up the torch, now the parent of the torch is the player. I guess that would be detected and handled when the player picks up the torch, but, what if the player walks into another node? how should it be detected? and for that matter, how would the player move (now with the torch) into terrain node 2 and get into the car?

##### Share on other sites
I honestly didn't get scene graph until I took CS2. Basically each node has a list (or vector/array) of pointer to other nodes. You can "attach" a new node by setting a pointer to it in the parent node. All you functions wil pass through all the nodes recursively by processing the node, then calling the function in all the child nodes.

If you are confused still, you may want to ry googling "n-trees" and polymorphism.

##### Share on other sites
well I know that, I have built and used quadtrees for my terrain, - I know recursiveness and pointers to other objects. My main question is how to move objects through the graph, and how do you load it since it is not like a terrain node that you know will be there and there will only be one.

##### Share on other sites
Hmm... I'm still confused what you want. Do you want to know how to load all the scene graph data from the hard drive? What do you mean by "move objects through the graph"? Sorry for all the questions.

##### Share on other sites
When you load objects into the world, like from a script, how do you put them in the correct order. I can see them filling into the correct terrain parent by checking the location on load, but like if you load a house and then a table. the table would have a parent as the house ( am I correct? ) how would that be done - has to be in script/loading file, correct? (I think I just answered that myself)

By moving through the graph, perhaps I am wrong, but you have them bound to tiles of terrain, perhaps in a quadtree. How would you move one object to another positionsuch as a player moving from node 1 to 2, I would have to hard code it in,
if (object_location > node_bounds ) set parent as the next terrain node, but that would be a lot of looping if there is a bunch of moving objects or pc/npc's

Perhaps I am just trying to add a culling type into the SG.

##### Share on other sites
Personally, I would try to keep your scene graph seperate from your quadtree. The scene graph should be more or less static for a given level. Adding objects as they are needed is ok, but nothing should be changing parents. It justs adds a bunch of extra complexity.

Quote:
 Original post by Valor KnightBy moving through the graph, perhaps I am wrong, but you have them bound to tiles of terrain, perhaps in a quadtree. How would you move one object to another positionsuch as a player moving from node 1 to 2, I would have to hard code it in,if (object_location > node_bounds ) set parent as the next terrain node, but that would be a lot of looping if there is a bunch of moving objects or pc/npc's

The player should be a child of a root terrain node (which all the chunks are also children of). Then you don't have to attach a model to seperate tiles and such. The player would have to switch between nodes in the quadtree still, however. You will probably have to hard code that like you mentioned.

##### Share on other sites
Humm, so the scene graph is primarly for static objects, otherwise they are children of the base node? If this is the case, since they are static objects, perhaps I can still do a quad or octtree in the graph, but also use a more flexable one for moving objects

base|------->Player ( computes location in quadtree every update needed )|------->NPC's and non-static objects(cars, monsters) ( computes location in quadtree every update needed )|------->Pickups ( weapons, item drops ) can be added in at will and uses npc/pc culling system ( computes location in quadtree every update needed )|------->Terrain Quadtree                   |----> terrain node 1                           |-> Quad/octtree for objects                                  |---->Objects                                           |->...

Then after load, all objects that have parents of the terrain quadtree should not change. All items/nodes that can change parents are children to the base.

Is this a better setup, or what it should look like? I just dont see why you would not include a quadtree inside of the tree, because you can do two things at once. How would/do you do it?

##### Share on other sites
I am just working through this issue myself, and to put it simple, I'll point you to this thread:

##### Share on other sites
Quote:
 Original post by ShaminoI am just working through this issue myself, and to put it simple, I'll point you to this thread:http://cboard.cprogramming.com/showthread.php?t=76448

Didnt really seen anything that pertains to the structure, though it looks as though you were hinting at it, but went to editors. Yea from what I have come up with, you will need to load the objects with refrences to the parents, but from the position, can compute the location on the map, and what terrain node is its parent.

Currently I belive I have the jist ( I hope ) - I just need to find the correct structure and how to handle moving objects

##### Share on other sites
The thread was more dealing with the first question of yours..

The creation and destruction of complex objects, like your torch for example, either needs to be hard coded, or loaded in modularily.. With files, created with an Editor..

You could fill out a structure of object info yourself, instead of creating an editor which uses files, but this is where your engine might begin to come inflexible...

##### Share on other sites
Quote:
 Original post by ShaminoThe thread was more dealing with the first question of yours..The creation and destruction of complex objects, like your torch for example, either needs to be hard coded, or loaded in modularily.. With files, created with an Editor..You could fill out a structure of object info yourself, instead of creating an editor which uses files, but this is where your engine might begin to come inflexible...

Yea, I am going to use files created from an editor (or hand). I figured that bit out, there is no other way to do it. Have you figured out anything with moving objects or re-parentable objects in your S.G.? Do you have your quadtree/octtree seperate or like the one I may do?

##### Share on other sites
Well for geometry transformation I use a DOF node..

Something like this
class CDOFNode : public CSceneNode{public:	CDOFNode( Vector4 translation) 	{		Initialize(translation);	}	~CDOFNode() { }	void Update()	{		// add parent final matrix to this 		// local matrix to get this final matrix		CSceneNode::Update();	}	void Initialize( Vector4 translation) // Updates local matrix	{		LocalMatrix.Translation(translation);	}private:	Matrix4 LocalMatrix;};

One of these comes before any piece of geometry, or renderable data, that we have. It takes the transformation of the parent node, the transformation of the local node, and adds them together for a final transformation.

But do you mean like, say, Soldier A under terrain A moves to terrain B suddenly, now we have to move soldier A and all its children to be under terrain B?

This is a strange issue I havn't really dealt with yet..

Being able to do this would quickly make a lot of huge benefits, for instance, ruling out millions of polygons incredibly fast. You know your frustrum isn't looking at terrain 1, so why bother checking frustrum culls for anything on terrain 1?

And for your torch, lying on the ground it is relative to the terrain, when you pick it up its now relative to your hand... I'm thinking transfer ownership functions?

##### Share on other sites
Quote:
 Original post by ShaminoBut do you mean like, say, Soldier A under terrain A moves to terrain B suddenly, now we have to move soldier A and all its children to be under terrain B?This is a strange issue I havn't really dealt with yet..

I was thinking keep the dynamic units out of the graph entirely (make thier parent the base node and do a quadtree cull), and make them have have thier own tree off them.. but then they would not have any data for collision, ect..

Quote:
 Original post by ShaminoAnd for your torch, lying on the ground it is relative to the terrain, when you pick it up its now relative to your hand... I'm thinking transfer ownership functions?

Yes this is what I was thinking, just re-assign the parent pointer the the Soldier, but then we will have a ever changing scene graph, which Sr_Guapo points out should be largly.

Would it be waise to partition them into a quad/octtree and then put them in that order, so when rendering, it can check bounds all the way doun until we finally get to the objects? or how could they be seperate?

##### Share on other sites
A quad/octree are not scene graphs well not in the typical sense and no scene graphs are not primariary used for storing static objects only, there meant to contain scene entities be it visible/renderable or not that means just about anything that is in the scene. I suggest spending sometime through this.

##### Share on other sites
Yeah, the scene graph is for everything, not just static geometry :)..

##### Share on other sites
Quote:
 Original post by snk_kidA quad/octree are not scene graphs well not in the typical sense and no scene graphs are not primariary used for storing static objects only, there meant to contain scene entities be it visible/renderable or not that means just about anything that is in the scene. I suggest spending sometime through this.

Wow! thats a great thread and needs to be stickied or put into a stickied graphics resource thread.

After reading a bunch of those links, I still have a problem with spatial org. If I use a quadtree, it is seperate from the scene graph, but it's leaves contain n pointers to scene graph data(such as objects, and terrain).
Quote:
 Original post by joanusdmentiaLet's consider your example, the person with the backpack. If the person isn't on the screen does that mean they're backpack isn't? No, it doesn't, the person may be just off the edge of the screen with the backpack still visible. In more general terms, just because a node in the scenegraph isn't visible DOESN'T mean that its child nodes aren't visible. This means that you have to traverse THE ENTIRE TREE in order to find out which objects should be rendered.

Ok, do I create the initial quad/octtree by recursivly going into the scene graph and checking the resulting position after every position node and placing it in the correct QT/OT node? Then if something moves ( such as a player with a backpack ), check it's new position and move it, and possibly its children in the quad/octtree? (this was my main question and seems closer to the correct answer then before)

But, seeing the advantages of render sorting would you make a scene graph for render states AND hierarchy and use them both? or, when rendering, would I insert the pointers to the objects that need to be rendered into a list, then iterate through the list looking for the same texture / shader / state(alpha), render and delete them from the list and then get a new type, and do this until the list is empty?

sorry for being the pest, but I think I am finally starting to get it [wink]

[Edited by - Valor Knight on March 4, 2006 6:05:26 PM]

##### Share on other sites
Is this what it should end up looking like (there is a transform node in front of each node)?
Scene|-->terrain (the class instance - no need to worry about nodes - quadtree takes care of that)|        |---->Player|        |       |->backpack|        |       |->Weapon 1|        |       |     |->cool fx for weapon|        |       |->Weapon 2||        |----->Static object|        |         |----->Particle fx||        |------>torch (player pickupable object)|        |         |-->Fire fx|        |         |-->Smoke fx|        |         |-->light source

Quadtree|------>node 1|         |---->node 2|         |       |-->pointer list (pointer to player scene graph data so using render() would recursivly render all children of player as well)|         |       |--> Also in pointer list is static object||         |---->node 3|         |       |-->pointer list that stores pointer to torch node struct/class

Thus, if the player aquires the torch, then the torch gets re-parented to player, and the children of torch go with it.
Scene|-->terrain (the class instance - no need to worry about nodes - quadtree takes care of that)|        |---->Player|        |       |->backpack|        |       |->Weapon 1|        |       |     |->cool fx for weapon|        |       |->Weapon 2|        |       ||        |       |->torch (player pickupable object)|        |             |-->Fire fx|        |             |-->Smoke fx|        |             |-->light source||        |----->Static object|        |         |----->Particle fx

If the player moves around, it is solely on the quadtree to worry about.

Am I presenting this in a correct way now?

How would I sort for render states?

When rendering, would I insert the pointers to the objects that need to be rendered into a list, then iterate through the list looking for the same texture / shader / state(alpha), render and delete them from the list and then get a new type, and do this until the list is empty?

## Create an account

Register a new account

• ### Forum Statistics

• Total Topics
627716
• Total Posts
2978783

• 9
• 21
• 14
• 12
• 42