Difference between scenegraph and spatial structure- example?

Quote:

Original post by okonomiyaki First of all, is a scenegraph really a graph or a tree?

A tree is a unidirectional graph (e.g. a tree is a graph but not the other way around). So yeah, it's usually a tree but people call it a graph because graphs are good for these types of problems. You can call it a scenetree if you want and you wouldn't be incorrect. It's just that graphs are usually used to represent networks so people call it a graph (that happens to be a tree).

Quote:

Original post by okonomiyaki The logical hierarchy would be person -> backpack -> flashlight, just as the spatial hierarchy.

But a spacial hierarchy doesn't track relationships between objects. It doesn't care that a backpack is on a person that's inside a room which is inside a building. It cares about *spacial* relationship, triangles (not objects) that are closed to each other. Consider two characters that are next to each other. They don't have a scenegraph relationship but they do have a spacial relationship. Just imagine a 3D grid over your scene. First a box, then 8 smaller boxes, then 8 more smaller boxes in each box. That's a spacial hierarchy (triangles within the boxes that are close to each have a common parent, not objects that relate to each other).

Quote:

Original post by okonomiyaki But I'm finding that a logic-based tree is very close if not exactly like the spatial hierachy.

If one object is logically related to an another, there is a good chance that they will be physically close to each other. There will certainly *seem* to be similarities, but it's in the way they work that makes the difference.

Let'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.

Spatial partitions on the other hand guarenttee that if any node isn't visible then none of its child nodes are either, so the instant you find a non-visible node you can instantly disregard all of it's child nodes.

Quote:

Original post by CoffeeMug Consider two characters that are next to each other. They don't have a scenegraph relationship but they do have a spacial relationship. Just imagine a 3D grid over your scene. First a box, then 8 smaller boxes, then 8 more smaller boxes in each box. That's a spacial hierarchy (triangles within the boxes that are close to each have a common parent, not objects that relate to each other).

Quote:

Let'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.

Two very good examples. Thank you very much, I can see the difference now.
So, you build the spatial tree from bounding boxes I assume and scenegraph from logical (person -> sword -> blade)?
You still calculate the model matrix from the scenegraph I assume, hence the ability to stack transformations. So the scenegraph is still used for rendering also.
And the spatial tree is used for culling/object collision.

Thanks!

Quote:

Original post by CoffeeMug Quote: Original post by okonomiyaki First of all, is a scenegraph really a graph or a tree? A tree is a unidirectional graph (e.g. a tree is a graph but not the other way around). So yeah, it's usually a tree but people call it a graph because graphs are good for these types of problems. You can call it a scenetree if you want and you wouldn't be incorrect. It's just that graphs are usually used to represent networks so people call it a graph (that happens to be a tree).

Actually alot of commerical scene graphs are directed acyclic graphs (DAGs) the reason for this it permits instancing efficently by sharing nodes, how-ever if your clever you can still do instancing efficently and/or share resources with Trees the idea is basically externalizing state of a node type for example instead of making geometry type a sub-type of a scene graph node you introduce a new node type call it *geo node* that refers to an instance of geometry via a (smart) pointer, then you can have any number of *geo node* instances use the same geometry over & over, reuse of resource.

The difference between a DAG and a tree is DAG nodes can have 0..* parents while Tree nodes have 0..1 parents only.

Quote:

Original post by okonomiyaki You still calculate the model matrix from the scenegraph I assume, hence the ability to stack transformations.

Yes internal nodes of a scene graph optionally maintain (but not always) a local transformation which is then accumulated via a depth-first traverse, concatention of transforms are performed.

Quote:

Original post by okonomiyaki So the scenegraph is still used for rendering also. And the spatial tree is used for culling/object collision.

if the scene graph's base node type maintains a bounding volume type this creates a structure with nested-bounding volumes where you can do hierarchical frustum culling on the scene graph, this is simillar to bounding volume hierarchies, then you can allow leaf node types to be encoded in any spatial data structure you desire where you override a nodes classification/interesection method to take advantage of the spatial data structure, so you can do efficent culling when the view frustum is tested in that node.

Quote:

Original post by snk_kid Actually alot of commerical scene graphs are directed acyclic graphs (DAGs) the reason for this it permits instancing efficently by sharing nodes, how-ever if your clever you can still do instancing efficently and/or share resources with Trees the idea is basically externalizing state of a node type for example instead of making geometry type a sub-type of a scene graph node you introduce a new node type call it *geo node* that refers to an instance of geometry via a (smart) pointer, then you can have any number of *geo node* instances use the same geometry over & over, reuse of resource. The difference between a DAG and a tree is DAG nodes can have 0..* parents while Tree nodes have 0..1 parents only.

Yeah, that was my main question (should have been clearer)- if a scenegraph is usually a DAG or a tree.

I've already separated actual geometry information and created geometry nodes that contain a reference to the real geometry. I like this because I can have a central storage for all the geometry, and obviously because it reduces redundancy. But your right, I guess there's no need for a DAG if you do this kind of thing. I would much rather do this and use a tree than have a messy DAG.

Quote:

Quote: Original post by okonomiyaki You still calculate the model matrix from the scenegraph I assume, hence the ability to stack transformations. Yes internal nodes of a scene graph optionally maintain (but not always) a local transformation which is then accumulated via a depth-first traverse, concatention of transforms are performed.

Ok, good. I always got the idea that people use scenegraph for nothing but a logic-based hierarchy and I wanted to make sure that rendering info was still extracted from it.

Quote:

Original post by okonomiyaki So the scenegraph is still used for rendering also. And the spatial tree is used for culling/object collision.

if the scene graph's base node type maintains a bounding volume type this creates a structure with nested-bounding volumes where you can do hierarchical frustum culling on the scene graph, this is simillar to bounding volume hierarchies, then you can allow leaf node types to be encoded in any spatial data structure you desire where you override a nodes classification/interesection method to take advantage of the spatial data structure, so you can do efficent culling when the view frustum is tested in that node.[/quote]

Wouldn't that type of hierarchial culling lead to the problem that joanusdmentia mentioned? It seems to me that I need to handle a group of bounding boxes purely on there location and not at all on the logical hiearchy.

edit: snk_kid, I saw your design in your recent post here: http://www.gamedev.net/community/forums/topic.asp?topic_id=299964
Still trying to digest it (I know little formal UML), but it's good to see someone else's design. Sorry I don't know enough to critique your design, looks like not many others do either :(

edit2: I did a little research earlier, but didn't come up with much. Must have been tired. Just did a search for "spatial trees" on gamedev and found some good threads:

Scene Graphs / Directed-Acyclic Graphs
Understanding and Implementing Scene Graphs

[Edited by - okonomiyaki on February 11, 2005 12:55:41 PM]

Quote:

Original post by okonomiyaki But your right, I guess there's no need for a DAG if you do this kind of thing. I would much rather do this and use a tree than have a messy DAG.

Indeed, DAGs have there advantages aswell its just makes the task of maintaining the scene graph more complicated and if you or some-body else decides (i'm still in debates about it my selfs) on using a DAG its advised to use a restricted form of DAG where only leaf node types are shared not grouping node types and to make the burden of maintaining it you can apply some of form of Observer design pattern where any change of the state in the *Subject* (an instance of a leaf node type) sends a notify signal to all its dependents *Observers* (instances of grouping node types) are notified and updated automatically.
[smile]

Quote:

Original post by okonomiyaki Ok, good. I always got the idea that people use scenegraph for nothing but a logic-based hierarchy and I wanted to make sure that rendering info was still extracted from it.

a scenegraph represents semantic(logical) and spatial relationships, either or both can be in there at the same time, besides the point as soon as you add transforms into the equation that is spatial information yes very minimal information but wouldn't you agree that it still is spatial information?

If scene graphs are only mean't to represent pure semantic relationships then you should have no transforms involved but i ask where are the transforms usefully going to be placed? besides the point as an example my arms are relative to my body when my body moves so does my arms moves relative to my body, that says to me its both a semantic & spatial relationship wouldn't you agree? please tell me if my logic is wrong here i like to be corrected so i don't make future mistakes [smile].

In every scene graph i've looked into i have never seen a scene graph that represents only a semantic relationship they represent both and to it seems only sensible to do so (unless some-one opens my eyes up i'm always open minded).

Quote:

Original post by okonomiyaki Wouldn't that type of hierarchial culling lead to the problem that joanusdmentia mentioned? It seems to me that I need to handle a group of bounding boxes purely on there location and not at all on the logical hiearchy.

As i was saying before a scene graph represents both semantic and/or spatial relationships, to me no nested bounds means traversing the entire scene graph including nodes that are outside the view frustum for things like concatenating transforms a O(n) operation, having nested bounds allows me to traverse only a sub-set of the tree and because its a tree on i can gain O(log n) operations, but having this is not enough i want to allow drawable leaf node types to be able to encoded in any plain spatial data structure, a whole leaf node type could be terrain a simple bounds is not enough so i encode it and all at the same time i get uniformity not seperate structures for seperate cases.

Quote:

Original post by okonomiyaki edit: snk_kid, I saw your design in your recent post here: http://www.gamedev.net/community/forums/topic.asp?topic_id=299964 Still trying to digest it (I know little formal UML), but it's good to see someone else's design. Sorry I don't know enough to critique your design, looks like not many others do either :(

Its such as shame because it would be very useful information not just to me be but every-one interesed or in a simillar place (even if its negative feedback).

I choose UML diagram because i thought it would simplifiy discussions with out any ambiguity but maybe your wright about people having little experience with UML :( (maybe i should move the thread to software engineering section?).

Take the design with a fine grain of salt how-ever its not the real thing its simplified & purposely missing info to focus on the problem i had. The main structure how-ever follows the composite & decorator design patterns what i'm intend on doing is alot of generic/template and OO concepts & techniques:

1. "Separation of Data from Their Operations" paradigm. (your all probably going errh? no its OO & generic but i'm using design patterns alot!).
2. generic visitors (ALA Loki style visitors).
3. pooling of nodes & the actual instances themself if they are small too (probably using both or either boost & loki pooled allocators).
4. Embedded reference counted system.
5. intrusive & non-intrusive reference counted smart pointers (intrusive work with the embedded reference counted objects).
6. generic Factories (ALA Loki style factories).
7. a whole other bunch of other design patterns used (Meta-Template'ized of course where possiable).
8. Other stuff [smile]

NOTE: you maybe interested in reading this sample chapter from David Eberly's recently released book 3D Game Engine Architecture its on Scene Graphs, no my design isn't the same as his [smile] (although simillar traits) but its a useful read.

[Edited by - snk_kid on February 12, 2005 2:17:04 AM]