Sign in to follow this  

Scene Graph, Spatial Hierarchy separation

This topic is 4838 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

Hi, I've been reading up in past threads on scene graphs and it seems that most people agree that it should be built on logical relationships and no culling/collision/etc.. should be performed within. My question is therefore how does the scene graph tie in with efficient acceleration structures for rendering etc.. (octrees/bsp trees/whatever)? Thanks

Share this post


Link to post
Share on other sites
Well, fundamentally a scene graph is not tied to visibility. Consider one of the cliche examples, a solar system.

We have the root node of the solar system, which is the sun. All of the planets are children of the root and rotate around it. If the sun moves, their center of rotation changes accordingly, keeping them in the same relative spot. They also rotate around their own axes. Then, some of these planets have child moons that rotate around them, and move with the planets, which are busily circling the sun.

Now, it's pretty obvious that the visibility of the sun doesn't affect whether or not you can see any of the planets. It's mainly used for keeping coherent transformations, linking objects (for example, the wheels of a car), etc.

Spatial work can be completely independent. A fairly standard solution would be some sort of loose octree, or maybe an AABB tree.

The key here is that these two structures don't tie in together. First you apply the scene graph to update all of your objects, then you apply the spatial tree to determine visibility.


There are probably clever ways of linking the two, but I don't know any offhand.

Share this post


Link to post
Share on other sites
Here's a couple of threads from Yann that were linked on TripleBuffer. They make very interesting reads on this subject and offer some useful tidbits of information.

Need Help With SceneGraph/Octree concept

Terrain and SceneGraphs

They're quite lengthy so be prepared for a hearty read :)

EDIT: It seems from the post after this that you've already read them - ignore [rolleyes]

Share this post


Link to post
Share on other sites
are there any well-know clever techniques for making the two work together? I'm slowly trauling through Yann's threads about spatial hierarchies and scene graphs but so far nothing's jumping out at me :)

[EDIT] Many thanks evolutional, I was unaware of the TripleBuffer list. Much interesting Yann reading :) [/EDIT]

[Edited by - algorhythmic on September 12, 2004 2:11:47 PM]

Share this post


Link to post
Share on other sites
Heya, mind if I think out loud into this thread? :D

I started down this road just days ago myself, and have been doing a bit of reading on the subject (inclusive from those helpful threads).

It came to my attention as I got more of any idea of how a SG relates to the title I am working on at the moment I discovered that, for the most part, there's probably little advantage in implementing one at this point. The game I am working on is an overhead shooter of the form of Smash TV, so most of my entities won't be hierarchical at all. The exception being that I would like to add vehicles to the mix, so this requires an attachment mechanism between objects at the very least, but I can only ever see it going one level deep (two absolutely maximum).

I already have a full frame hierarchy implemented for animations and soon-to-be-implemented attachments - rather than make a vechicle attach to part of the frame hierarchy I'll probably include some attachment mechanism in the base object/node class to facilitate this.

I'm yet to determine if I should just go the whole hog and implement a scene graph however, as I've already implemented a frame hierarchy for animation, and in it's basic sense SG doesn't seem too far removed from this. I just don't want to get trapped by any 'gotchas' at a later date.

As for collision detection, I've implemented your standard quad/octree spatial partitioning scheme and I'll be using that for collisions by determining in what node an object lays and going from there, determining collision with other objects and the terrain itself.

Share this post


Link to post
Share on other sites
Nope, upon further research and reading Yanns article on SGs I've decided to just go ahead an write a simple one for now, I can increase it's functionality further in the future if need be. :)

Share this post


Link to post
Share on other sites
Unfortunately I'm not writting a game but a framework which I shall use to explore object interactions and so on within a virtual environment and so I'd like to have something relatively complete (at least a structure that I won't have to completely overhaul almost immediately).

There seem to be so many different interpretations of the concept that my head spins! One thread I was reading mentionned stressed their use to manage render state to as to optimise rendering by minimising state changes. Others look at scene graphs from a purely hierarchical point of view.

I'm lost. /me sobs!

Share this post


Link to post
Share on other sites
Quote:
Original post by algorhythmic
...*snip* their use to manage render state to as to optimise rendering by minimising state changes. Others look at scene graphs from a purely hierarchical point of view.

I'm lost. /me sobs!


sadly this isn't a helpful post, more of a "there, there, it'll be ok" comforting post.

For some reason Scenegraph is a term that gets banded around to describe a wealth of different but slightly related things. The actual term *probably* means something specific but... meh, people are lazy [smile]

if you're interested in documented architecture you could however take a look at NVidia SG SDK and http://www.openscenegraph.com/ they might help you by seeing an implementation and whats it's actually used for.

Andy

Share this post


Link to post
Share on other sites
scene graph is a structure that represents hierarchical relationship among objects, a typical scene graph is an instance of a composite design pattern and is not used as a spatial data structure its higher level entity than that, spatial data structures only deals with geometry. Leaf nodes of a scene graph could encompass an entire spatial data structure such as an octree.

Quote:
Original post by algorhythmic
One thread I was reading mentionned stressed their use to manage render state to as to optimise rendering by minimising state changes.


render states come from the scene graph, from what i understand when the renderer iterates the scene graph/s it can accumulate render state into a render queue that is sorted to minimse state changes.

The renderer can make more than one pass through the scene graph per frame.

Share this post


Link to post
Share on other sites
Well I think superpig said at one stage that he was considering using multiple specialised graphs for different tasks like rendering, culling, collision, physics. I'm wondering whether this is such a good idea. I can see how one could get carried away and loose the benefits of the scene structures...

Share this post


Link to post
Share on other sites
Quote:
Original post by Freaker13
Why not using your scenegraph for culling,collision detection,...???


Quote:
Originally by Real-Time Rendering Second Edition
a node in the scene graph often has a bounding volume (BV), and is thus quite simillar to a bounding volume hierarchy (BVH)


So you can but i think its only good for trivial rejectection, if not rejected then a more detailed & better information can be obtained from the spatial data structures.

Share this post


Link to post
Share on other sites
Quote:
Original post by algorhythmic
Well I think superpig said at one stage that he was considering using multiple specialised graphs for different tasks like rendering, culling, collision, physics. I'm wondering whether this is such a good idea. I can see how one could get carried away and loose the benefits of the scene structures...


Quote:
Originally by Real-Time Rendering Second Edition
It should also be noted that more than one scene graph can be used for the same scene. This is the idea of spatialization, in which the user's scene graph is augmeneted with a seprate scene graph created for different tasks, e.g. faster culling and picking. The leaf nodes, where most models are located, are shared, so the expense of an additional set of internal nodes is minimal.


I love that book, basically take a composite design pattern apply flyweight pattern to leaf nodes only you'll end up with kind of a directed acyclic graph (DAG) instead of a tree. Then you can have multiple scene graphs that reference the same leaf nodes or leafs with more than one parent.

Share this post


Link to post
Share on other sites
when you talk of flyweights you refer to geometry that's rendered often such as enemy characters etc.. One would therefore need to split up mesh and character state right?

Share this post


Link to post
Share on other sites

This topic is 4838 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.

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