Sign in to follow this  
mhamlin

Bounding Volumes / Scenegraph

Recommended Posts

After reading some scenegraph threads, I've decided to (re)design my scenegraph system. I'm still deciding how to organize things, et.c., and am still in the design phase (I'm often in this stage). I've decided to try and implement an adaptive tree. A few quick questions. Should bounding volumes be nodes of the graph (i.e. children of the node they describe) or should each node contain the bounding volume in itself? I've been leaning toward having the volumes themselves be nodes of the graph. Also, when a node is translated, it will obviously need to tell its parent to update its bounding volume accordingly. If the node is translated many times per frame, and if child nodes are translated as well, this could be fairly inefficient. Perhaps each node should set a flag if it has been translated, and when updating the tree, somehow get the deepest node that has the flag set, and walk up the tree updating volumes accordingly? This seems inefficient as well. I would greatly appreciate any insights or advice you can provide.

Share this post


Link to post
Share on other sites
should u even insert bounding information into a scenegraph, should it be part of the logical heirarchy of the scene (which is what the scenegraph is).

The few that I have built have never used bounding information in the scenegraph. Each node was also placed in an octree (which in turn was in the scenegraph) and referenced back to the scenegraph node for its child nodes (which were then also rendered). That way I just culled a portion (with the octree) and not everything in the graph (assuming that is what you are going for with the bounding information).

you can check out this tutorial on a basic scenegraph implementation

Hope that helped

Share this post


Link to post
Share on other sites
Thanks for the input. The reasoning for inserting bounding information for each node is to allow for efficient object-based culling. If the parent node's bounding volume incorporates its children's nodes, then the entire subtree can be culled. If the tree is organized (and if the organization is maintained), then performing some HSR within the scenegraph itself could be fairly efficient.

Basically, I would rather find a different solution than inserting an octree (or quadtree, or whatever) into the scenegraph.

Perhaps I'm going about wrongly by trying to use a scenegraph for HSR.

Again, thanks for your time.

Share this post


Link to post
Share on other sites
Scenegraph is really an implementation of the Composite pattern (Design Patterns, Gamma et al). The pattern consists of Component, Composite, and Leaf; in short:

Component:
- declares the general interface
- implements default behaviour
Leaf:
- has no children
- defines behaviour for primitive objects in the composition
Composite:
- defines behaviour for components having children
- stores child components

Composites can cache traversal or search information about their children. In scenegraphs this is often understood as storing a bounding volume that bounds the bounding volumes of every child. Then, you can use the Decorator pattern for effects, transformations, etc. Flyweight pattern goes for leaves using the same resources (four tires in a car, store the tyre mesh once). Etc, etc.

In my current implementation (And yes, I too, seem to be in constant design phase; Let's call that refactoring, shall we.) there is no separate Composite but every node can have as many children as they like. This is something I've been mulling over since I'm still not sure if I should go back to separate Composite.

Every node has a local OBB (if applicable) and a cached group AABB for the BBs of the children. This way I can cull e.g. collision testing early without propagating all the way down to individual leaves. First I check the incoming BB against the group AABB. If I get a hit I check the BB against the node's local OBB (if there is one), and propagate down. If something moves I push the corresponding BB upwards merging it with the group AABBs above.

If the bounding volumes should be separate constructs _above_ the constructs they bound has crossed my mind, but I'm waiting for that extra push from other parts of the refactoring before I commit to that.

Have to love doing this as a hobby. Trying, testing, and refactoring puts forth knowledge not gained through industrial deadlines.

JD

Share this post


Link to post
Share on other sites
Well with that culling you are going to be doing a lot more of it the more objects you have, just feel that an octree (quad, etc) might be better for these operations. I think your trying to combine a spatial tree with a scenegraph which should just be logical.

I found a few threads on this which might be of help

Yann L on terrains and scenegraphs take a look at the third or so post from Yann.

Scenegraphs and Octrees

Scenegraph management

from one of Yanns posts (last link)

Quote:

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.



Hope that helped



btw thanks for the rate up :)

Share this post


Link to post
Share on other sites
JesusDesoles, thanks for your response. You're suggestion of having both a local and group (world, I suppose) bounding volume is a good one.

nts, I'll have to read those threads again. I was probably trying to accomplish too much with a single tree.

Share this post


Link to post
Share on other sites
I've read the threads way back but thank you for the links anyway. I'm aware of the Yann's (valid) views but mine is a search for something new instead of something finished. In the end I'm hoping to find a novel construct that resembles SGs, octrees, or something completely different. Currently I use SG for dynamic stuff only.

It would be great to argue these things in person like I get to do in conferences about other things but maybe I'll get lucky in time.

JD

Share this post


Link to post
Share on other sites
JesusDesoles:
I'm curious as to how your system works. It seems that you're combining a SG with a partitioning scheme. Care to indulge me?

Share this post


Link to post
Share on other sites
My current interest is a system that would easily handle the installation of coupling, forces, collision checking, object breaking, etc. anywhere in the system with the least amount of effort (in the full implementation). Obviously, this got me interested in SG/Composite with high abstraction (as Yann points out in the threads discussed here).

Hence the sustained refactoring.

For partitioning and SG ref to Yann (nts's first link). I haven't thought about large static structures yet, and once I do, I fear my - by that time so shining - construct will get another major refactor. <place your favourite smiley right here>

JD

Share this post


Link to post
Share on other sites
a bit off topic... I noticed in one of the older threads someone was basically saying Yann L doesn't know what he's talking about...LOL!!!!!! sorry, just found that to be funny ;)

Share this post


Link to post
Share on other sites

Create an account or sign in to comment

You need to be a member in order to leave a comment

Create an account

Sign up for a new account in our community. It's easy!

Register a new account

Sign in

Already have an account? Sign in here.

Sign In Now

Sign in to follow this