Jump to content
  • Advertisement

Archived

This topic is now archived and is closed to further replies.

neurokaotix

Scenegraph Management: A discussion

This topic is 5843 days old which is more than the 365 day threshold we allow for new replies. Please post a new topic.

If you intended to correct an error in the post then please contact us.

Recommended Posts

Right now I''m trying to wrap my mind around a very large and complicated subject: scenegraph management. I''ve been studying various models and ways to accomplish the task, read a few tutorials here and there, browsed through some source code, etc. Are std::vectors inefficient for constant adding and deleting of nodes, and iterating through the list each frame? I was hoping that someone might have some insight on a what is efficient and what is not. I''ve read the tutorial on gdnet about object-oriented scenegraph management and it gave me a good idea as to how to build mine, but after reading the article''s discussion thread I had my doubts on the use of vectors. Perhaps std::map would be better suited for my needs? Any input would be greatly appeciated James Simmons MindEngine Development http://medev.sourceforge.net

Share this post


Link to post
Share on other sites
Advertisement
Guest Anonymous Poster
std::map is very, very heavyweight.

std::vector sucks if you delete or insert at the beginning or in the middle.

std::list is great if you want to insert/delete at arbitrary places, and walk the list from beginning to end.

However, a good scene graph typically will need a better container, such as an octree or kd-tree or something, for faster determination of "nearby" or "visible" entities. You may even need to consider different containers all referencing the same data sets, for different needs (culling, collision, state optimization, etc).

For starters, I would just stick a pointer to each "thing" to render inside a list. "things" could potentially have lists of child things, if you''re into that "inherit the parent properties" thing (which I never found any use for). Store a bounding box or sphere for each "thing".

When rendering, cull the bounding volume of each thing against the viewing frustum (translated into world space, which is where "things" live). Things that intersect get a callback to render themselves.

Only optimize this once you run a profile and determine that this is actually too slow. Chances are, it won''t be.

Share this post


Link to post
Share on other sites
Either that, or an octree (as AP said).
The list is written for you in the STD, but you''d have to write the octree yourself.
An octree would be better, as stated, as you can determine visibility. If a node contains children, and that node itself isn''t visible, then neither will its children, and thus you already cut your processing time down by not performing visibility checks on objects that you know aren''t visible.

-----------------------
"Without a sense of humour we couldn''t react to a lot of things"

Share this post


Link to post
Share on other sites
the difference in performance between vectors and lists will only become apparent with a large number of objects attatched to each of your nodes, a very bushy tree. vectors are very rapid for iterating over their contents, as the memory is generaly contiguous. Having said that since the vector will most likely contain references to other objects in other memory locations the advantage over lists in this respect is minimalised.

Personally I would go for lists, unless you have some specific structure that would optimise well for vectors.

Share this post


Link to post
Share on other sites
I dont understand why octrees are being compared with vectors and lists. Iterating over the list or vector will only become expensive when you have very many child nodes. If you have that many child nodes then it might seem good to store them in an octree, so you can query them faster. But, if thats the case, then just add another level to your tree! Thats what scenegraphs are for, hierarchically representing a scene.

So, if iterating over child nodes during queries is eating performance then your graph is probably too shallow.

Share this post


Link to post
Share on other sites
Rules of thumb to get an efficient scenegraph:

A) Don''t use an SG for visibility determination. That''s not its job. A good SG is not necessarilly a good spatial tree.
B) Don''t use an SG for collision queries. Same reasoning as above.
C) Don''t use a fixed partitioning scheme (eg. octree) for an SG. Use variable node trees.
D) Don''t build your SG on spatial relationships. Build it on logical relationships.

The most important point being, that an SG is abstract structure to represent relationships between objects (often hierarchical attachements, such as in character animation). It is not a structure to do visibility culling, nor will it do collision queries. An SG is a highly abstract logical access structure to your scene data. It is used to efficiently connect gameplay, physics, animation and AI systems to the graphics engine.

In short, don''t confuse a scenegraph with a spatial culling/localization struture such as an octree/BSP/ABT/KdT/etc. They are two totally different and unrelated concepts.

Share this post


Link to post
Share on other sites

Sorry if this is a bit off topic , but now that you mention it:

"Don''t use an SG for visibility determination."

Right now i hava a geometry Node class that can have a child OcclusionBoundingBox. When i build the tree, a bounding box node is created for each geometry node. I use these for my OcclusionQuery tests. I dont think this is the best design and this would imply that i''m using the scene graph to store visibilty information, which is bad. Would it be better to store an adjacent structure for visiblity determination in this case? This could get complex if the hierachy of transforms is modifed in the scene graph then it would have to be modifed in the occlusionBox tree.


Thanks

Share this post


Link to post
Share on other sites
Master Yann L,

How would one integrate a spatial culling structure as an quadtree with a scene graph in order to render a scene?

Would it be something like:
Cull the quadtree nodes outside the frustum
Inside each quadtree node there would be a scene graph, or maybe some pointers on scene graph nodes?
Would the static mesh inside a quadtree node be part of the scene graph?
What types of scene graph nodes are usually used?

Next question is probably a lot to ask and can be ignored:
Can you develop a little the idea :"It is used to efficiently connect gameplay, physics, animation and AI systems to the graphics engine." Maybe giving an example? Or a link?

Thanks in advance

[edited by - fistandantilus on September 19, 2003 5:28:00 PM]

Share this post


Link to post
Share on other sites
I always thought Scenegraphs were created by state; as Yann said, logically, not spacially.

For example, you''d create a list with objects of each texture; group these into materials, etc. So when renderig you''d change state as little as possible.

Share this post


Link to post
Share on other sites

  • Advertisement
×

Important Information

By using GameDev.net, you agree to our community Guidelines, Terms of Use, and Privacy Policy.

GameDev.net is your game development community. Create an account for your GameDev Portfolio and participate in the largest developer community in the games industry.

Sign me up!