Scene Graphs, again... Some clarification please.
Author
Hello Everyone,
Yes, I have questions on scene graphs. I'm fairly certain I get the idea of how they work and I even had a small demo working just fine. However, I have some questions about their practicality in larger projects.
I have read a handful of resources on scene graphs, one of the best seemed to be this thread. But I am still skeptical.
Numbered for answering ease.
1) From the Scene Graph tutorial I got the impression that the nodes in your tree structure are not actually your entities, but merely represent your entities. If this is true, how do you link them together? When a character gets off his horse, how do you find his MeshNode and move it from the horses MeshNode to the root?
Rephrased: Should I be keeping an Entity list in a rather generic entity manager where I can handle mob factory stuff, and then my scene node is kept with the renderer and only says how the entities it represents are to be displayed?
In the demo that I made, the nodes in my scene graph are the actual entities. Everything inherits from SceneNode. In the demo the entities mesh skin is actually a child to it. The entity itself has no render option, it only passes on it's transformation matrix. This makes things very cumbersome. I would much prefer to have an Entity list of generic entity types and keep my scene graph separate. But I don't know how to keep the scene graph in sync with the entity list data without lots of tree iteration.
This problem would arise again when I build an octree to do collision would it not?
2) If I cast a "Summon" spell on a player and I wanted to take his mount if he's on one. How would you go about getting the parent and making sure it's a mount not a boat, or a car?
The whole point of a scene graph to me is abstracting the "connections" between entities. Instead of iteration through Entity.Mounted, Entity.Attachments[], Entity.Skins[], Entity.Weapon, and other dependant relationships that would need to be updated everytime player moved, you can manage them all through a parent->child relationship in a scene graph. If your scene graph has to check the type of a parent node to see if it's Mount, that seems to blur the purpose.
Note: A good system to that keeps the an Entity list separate from the Scene Graph from question 1 may inherently solve this issue.
3) It seemed that most people in other threads agreed that the scene graph should not be used for collision (though it could be, it shouldn't). Assuming we don't want to use it for collision, if all we are keeping are relative positions of entities from their parents then every time you want to do collision you would have to iterate up the tree to the root to make sure you have their world position, and that would be costly.
I suppose we could handle it like the skinned mesh frames. After an update, save "CombinedTransformationMatrices" for each entity. That way we can grab the last rendered world position at any time. However, if the player has moved, but the scene hasn't updated, then that matrix will be off slightly.
Note: Once again, a good answer to question 1 may well solve this issue.
4) Why is it called a Scene GRAPH when it's clearly a tree?
5) Any other snags you came across and found solutions too would be nice. Might save me a post in the near future.
Thanks,
I think this article should help you: http://gamearchitect.net/Articles/GameObjects2.html
This too: http://gamearchitect.net/Articles/GameObjects3.html
This too: http://gamearchitect.net/Articles/GameObjects3.html
Quote:Original post by Kahsm
4) Why is it called a Scene GRAPH when it's clearly a tree?
Ah, but a tree is a graph. Perhaps you're in need of a bit of graph theory.
let R be the root
let A and B its childrean (eg. Transformations)
let C be a Node not in the graph (eg. a building)
now suppose you want to place the building C at A and at B.
Tree:
R --- A --- C
.\--- B --- C' (copy of C)
Graph: (Tree is a special case of a graph!)
R --- A --- C
.\--- B ---/
So in a graph you can reuse Nodes!
Since the links posted by Aldacron seem to be dead, I'll try and answer your questions:
Because I see a scene graph strictly as a datastructure that describes graphics, I would indeed separate. I don't see why this would be hard. If you have a horse and a player object in your game, just let them store pointers to their respective representations in the scene graph. If your game tells you that player mounts horse, simple remove the player representation from the graph and add at the horse node, the pointers are all the info you need.
This is a common problem when using polymorphism. There exist many solutions to find the type of a specific object. You could for example build a list of type numbers. Each constructor of an object adds it's own unique type number to the list. To query if an object is of a specific type, search this list for that type's unique number. I'm sure there are much better ways, but this should be straightforward...
In my scene graph collision detection is done after calculating the model matrix for the renderable objects (geometries, lights). This matrix is always up-to-date, since no positions can be changed during this phase. The problem you describe (with the player matrix being off) can occur in your specific design, but it's fairly easy to change the design to solve the problem.
As stated by dragongame, most scene graphs allow multiple parents per node. This introduces cycles which technically makes it not a tree.
That's tricky. I came across a lot of things. One obvious problem with scene graphs, is rendering large numbers of sperate objects. I needed to draw a molecule consisting of 300K atoms. You'll find that scene graphs won't work in such situations. I solved this particular case by creating a single scene graph object that can contain a list of positions, orientations, scales and colors for a single shape (a simple sphere in this case). Such an object has much less overhead than a SG. Anyway, odds are you'll never run into that specific problem. Each application has it's own...
Tom
Quote:Original post by Kahsm
1) From the Scene Graph tutorial I got the impression that the nodes in your tree structure are not actually your entities, but merely represent your entities. If this is true, how do you link them together? When a character gets off his horse, how do you find his MeshNode and move it from the horses MeshNode to the root?
Because I see a scene graph strictly as a datastructure that describes graphics, I would indeed separate. I don't see why this would be hard. If you have a horse and a player object in your game, just let them store pointers to their respective representations in the scene graph. If your game tells you that player mounts horse, simple remove the player representation from the graph and add at the horse node, the pointers are all the info you need.
Quote:Original post by Kahsm
2) If I cast a "Summon" spell on a player and I wanted to take his mount if he's on one. How would you go about getting the parent and making sure it's a mount not a boat, or a car?
This is a common problem when using polymorphism. There exist many solutions to find the type of a specific object. You could for example build a list of type numbers. Each constructor of an object adds it's own unique type number to the list. To query if an object is of a specific type, search this list for that type's unique number. I'm sure there are much better ways, but this should be straightforward...
Quote:Original post by Kahsm
3) It seemed that most people in other threads agreed that the scene graph should not be used for collision (though it could be, it shouldn't). Assuming we don't want to use it for collision, if all we are keeping are relative positions of entities from their parents then every time you want to do collision you would have to iterate up the tree to the root to make sure you have their world position, and that would be costly.
I suppose we could handle it like the skinned mesh frames. After an update, save "CombinedTransformationMatrices" for each entity. That way we can grab the last rendered world position at any time. However, if the player has moved, but the scene hasn't updated, then that matrix will be off slightly.
In my scene graph collision detection is done after calculating the model matrix for the renderable objects (geometries, lights). This matrix is always up-to-date, since no positions can be changed during this phase. The problem you describe (with the player matrix being off) can occur in your specific design, but it's fairly easy to change the design to solve the problem.
Quote:Original post by Kahsm
4) Why is it called a Scene GRAPH when it's clearly a tree?
As stated by dragongame, most scene graphs allow multiple parents per node. This introduces cycles which technically makes it not a tree.
Quote:Original post by Kahsm
5) Any other snags you came across and found solutions too would be nice. Might save me a post in the near future.
That's tricky. I came across a lot of things. One obvious problem with scene graphs, is rendering large numbers of sperate objects. I needed to draw a molecule consisting of 300K atoms. You'll find that scene graphs won't work in such situations. I solved this particular case by creating a single scene graph object that can contain a list of positions, orientations, scales and colors for a single shape (a simple sphere in this case). Such an object has much less overhead than a SG. Anyway, odds are you'll never run into that specific problem. Each application has it's own...
Tom
Quote:Original post by Kahsm
But I don't know how to keep the scene graph in sync with the entity list data without lots of tree iteration.
Just an idea, you could use the observer design pattern.
Quote:Original post by Kahsm
3) It seemed that most people in other threads agreed that the scene graph should not be used for collision (though it could be, it shouldn't). Assuming we don't want to use it for collision, if all we are keeping are relative positions of entities from their parents then every time you want to do collision you would have to iterate up the tree to the root to make sure you have their world position, and that would be costly.
I suppose we could handle it like the skinned mesh frames. After an update, save "CombinedTransformationMatrices" for each entity. That way we can grab the last rendered world position at any time. However, if the player has moved, but the scene hasn't updated, then that matrix will be off slightly.
That is commonly done to have a cached concatenated transform ready, also to save the trouble of traversing the entire SG everytime a common practice is to maintain nested bounding volumes in all node types it should be very cheap & fast to contain, test, and maintain as its not meant to be a complete replacement for visibility determination & collision detection.
Quote:Original post by Kahsm
4) Why is it called a Scene GRAPH when it's clearly a tree?
Not all scene graphs are n-ary trees some are restricted forms of directed acyclic graphs (DAGs) where leafs nodes are allowed to be shared and as already mentioned a tree is a special case a of graph.
Quote:Original post by dimeboltQuote:Original post by Kahsm
2) If I cast a "Summon" spell on a player and I wanted to take his mount if he's on one. How would you go about getting the parent and making sure it's a mount not a boat, or a car?
This is a common problem when using polymorphism. There exist many solutions to find the type of a specific object. You could for example build a list of type numbers. Each constructor of an object adds it's own unique type number to the list. To query if an object is of a specific type, search this list for that type's unique number. I'm sure there are much better ways, but this should be straightforward...
One good way to handle or get round this as scene graphs are typically instances of the composite design pattern is to use the visitor pattern with composite pattern.
Author
Thanks to everyone who replied.
Things are quite a bit clearer for me.
I enjoyed reading the gamearchitect.net articles. However, other than being rather well written, all he seems to do is tell you where you're going to fail and just seems to leave it at that. I suppose it's an example of how engine design is far from perfected.
He mentioned that some people have implemented scene graphs as their only game entity structure, and each node was a renderable object and held it's own transformation data. That's what I have been playing with myself lately.
What he, all of you, and all the developers he spoke with at GDC, are suggesting is an Entity list separate from the Scene Graph where each Entity holds a pointer to it's Scene Graph representation(s) (possibly an object registration system of some sort).
So, that means your Entity would have no first hand knowledge of rendering information or even world position/scale. Such information might be find by Entity->SceneNode->GetPosition(); or GetWorldPosition(), if you have saved the combined from the last graph update.
Assuming all is right so far, I need to get into more source based issues and away from the Scene Graph theory.
Remember that my previous experience is with a game object based scene graph, and not a transformation based scene graph, so I have some new transformation based questions.
Note: After having re-read through my response I apologize for its rambling nature, but I kind of mind dumped then pulled out my questions from where the dump stopped.
* The tree looks simple, but that is assuming my Player1Mesh (which lets say is a SkinnedMesh) manages its own hierarchy separately. That seems like an easy solution, but if you spent the time to breakup your frames and build them into the scene graph, that to me would make "attachment points" on certain bones much easier to manage (in the scene graph) as now the frames aren’t hidden in your player mesh anymore. Of course knowing to remove all those frames when your player dies or gets removed from the scene via teleportation might be confusing. This means that an Entity might have pointers to multiple scene nodes! One for his transformation, one for his scale, ones for his skinned mesh and maybe a whole bunch for his skeletal bones? Now it seems to be getting harder to manage.
I suppose my question here is, if your transformations are separated from the mesh node, then if your Player moves, how does he know which scene node to update? Does he have links to all the scene nodes he owns directly, as I suggested above? Does an entity always have to own a scene node? Do other game objects ever own any nodes (other than the root case)?
** The torch would be attached to a hand bone, or some predefined "attachment" point that is a child to the hand bone. In my current design my ExtendedFrame class has an array of AttachmentPoints which define a transformation and rotation from the parent bone which attachables can use as a rendering point, thusly, attaching them to that bone.
Hrm, I think my question here is off topic. I want to ask about how to manage skinned mesh frames and attachment points on them. I wrote a program earlier which could swap skins on a skeleton, but I think if I want to break my frames up, and break them from their matrices, and handle them separately in my scene graph, then the general LoadHierarchyFromFile() and AnimationController might be adequate anymore. So if you have any suggestions for handing skinned mesh hierarchies, and attachments to frames in a scene graph, that would be helpful.
I think that should cover it for now. Also an idea of what types of nodes you have in your applications might be nice: transform, rotate, scale, mesh, and particle… any others I might not think of?
Thanks again,
Things are quite a bit clearer for me.
I enjoyed reading the gamearchitect.net articles. However, other than being rather well written, all he seems to do is tell you where you're going to fail and just seems to leave it at that. I suppose it's an example of how engine design is far from perfected.
He mentioned that some people have implemented scene graphs as their only game entity structure, and each node was a renderable object and held it's own transformation data. That's what I have been playing with myself lately.
What he, all of you, and all the developers he spoke with at GDC, are suggesting is an Entity list separate from the Scene Graph where each Entity holds a pointer to it's Scene Graph representation(s) (possibly an object registration system of some sort).
So, that means your Entity would have no first hand knowledge of rendering information or even world position/scale. Such information might be find by Entity->SceneNode->GetPosition(); or GetWorldPosition(), if you have saved the combined from the last graph update.
Assuming all is right so far, I need to get into more source based issues and away from the Scene Graph theory.
Remember that my previous experience is with a game object based scene graph, and not a transformation based scene graph, so I have some new transformation based questions.
Root (Might be a transformation node itself if using a world-view matrix) | |--- Player1Position : TransformationNode | | | |-- Player1Rotation : RotationNode | | | |-- Player1Scale : ScaleNode | | | | | |-- Player1Mesh : MeshNode (*see below) | | | |-- TorchOffset : TransformationNode (** see below) | | (Note: Torch not effected by a scaling spell, lets say) | | | |-- TorchMesh : MeshNode | | | |- ... flame, smoke, light, shadows, blah blah blah ... | |--- Player2 ...Note: After having re-read through my response I apologize for its rambling nature, but I kind of mind dumped then pulled out my questions from where the dump stopped.
* The tree looks simple, but that is assuming my Player1Mesh (which lets say is a SkinnedMesh) manages its own hierarchy separately. That seems like an easy solution, but if you spent the time to breakup your frames and build them into the scene graph, that to me would make "attachment points" on certain bones much easier to manage (in the scene graph) as now the frames aren’t hidden in your player mesh anymore. Of course knowing to remove all those frames when your player dies or gets removed from the scene via teleportation might be confusing. This means that an Entity might have pointers to multiple scene nodes! One for his transformation, one for his scale, ones for his skinned mesh and maybe a whole bunch for his skeletal bones? Now it seems to be getting harder to manage.
I suppose my question here is, if your transformations are separated from the mesh node, then if your Player moves, how does he know which scene node to update? Does he have links to all the scene nodes he owns directly, as I suggested above? Does an entity always have to own a scene node? Do other game objects ever own any nodes (other than the root case)?
** The torch would be attached to a hand bone, or some predefined "attachment" point that is a child to the hand bone. In my current design my ExtendedFrame class has an array of AttachmentPoints which define a transformation and rotation from the parent bone which attachables can use as a rendering point, thusly, attaching them to that bone.
Hrm, I think my question here is off topic. I want to ask about how to manage skinned mesh frames and attachment points on them. I wrote a program earlier which could swap skins on a skeleton, but I think if I want to break my frames up, and break them from their matrices, and handle them separately in my scene graph, then the general LoadHierarchyFromFile() and AnimationController might be adequate anymore. So if you have any suggestions for handing skinned mesh hierarchies, and attachments to frames in a scene graph, that would be helpful.
I think that should cover it for now. Also an idea of what types of nodes you have in your applications might be nice: transform, rotate, scale, mesh, and particle… any others I might not think of?
Thanks again,
Quote:Original post by Kahsm
*** lots of text ***
I suppose my question here is, if your transformations are separated from the mesh node, then if your Player moves, how does he know which scene node to update? Does he have links to all the scene nodes he owns directly, as I suggested above? Does an entity always have to own a scene node? Do other game objects ever own any nodes (other than the root case)?
*** lots of text ***
First off: I don't program games. My problems typically require translation from scientific data to scene graph data. In other words, I never encountered this problem myself and this solution is purely theoretical. What I would is give the player entity a pointer to the player sub-graph (in case of your example: Player1Position : TransformationNode). Assuming that the players influences only the objects within this graph, we have a relatively small search scope. Now just use your naming system (assuming you have a system of naming nodes and finding nodes using their name, if not it's normally very easy to implement) to get the other pointers. This may be slowish (esp. if you use string names, like me), but
I very much doubt it turns out to be a bottleneck unless you have thousands of entities active.
Quote:Original post by Kahsm
*** lots of text ***
I think that should cover it for now. Also an idea of what types of nodes you have in your applications might be nice: transform, rotate, scale, mesh, and particle… any others I might not think of?
Again, my lib is not intended for games (although I did write a Quake 3 lvl loader for it :), but it uses a slightly different approach so I'll mention it. I wanted to keep things simple and easy to use, so I got rid of the transform nodes. Transformation functionality is all put into the base node. From this base node (called Graph) I inherit: Camera, Light, Geometry and Group. Geometry contains an Appearance (think OpenGL state with Texture and Shader objects) and a number of Shape objects (meshes) but these objects are not part of the graph (don't inherit from the base node). Group nodes are the only nodes that can have children. The nice thing about this, is that I can transform each node in the graph, without having to insert extra transformation nodes.
For your case, a camera node type might be nice. It's very user friendly, as it will allow you to attach a camera to the "attachment point" of your players head. The transformations for the camera will all be performed automatically. In fact, you could attach cameras to each entity in the world (including enemies) and by means of a simple camera switch, allow the user to look through the eyes of that entity (which may be useful for debugging).
Tom
Having a separate translation, rotation, scale node types seems like abit over the top to me, you only need one transform node type. I've seen two main ways of going about it
The other way is kinda like what dimebolt was saying, where the base node type maintains a transform but that means every node in the the tree has a transform while the above means only internal (nonterminal) nodes can have transforms applied to there children.
(0..*) Abstract Node type <---------- ^ | | (inherits) | | | -------------------- | (aggregates/contains) | | | | | | Leaf Node types Group Node type --- ^ | (inherits)| | (aggregate) Transform Group -------------> Transform (SRT)The other way is kinda like what dimebolt was saying, where the base node type maintains a transform but that means every node in the the tree has a transform while the above means only internal (nonterminal) nodes can have transforms applied to there children.
This topic is closed to new replies.
Advertisement
Popular Topics
Advertisement
