Scene graph questions

After a few months of research on the topic, I am fairly convinced that indeed some sort of "multi-view" scene graph is the way to go, partially because of the problems that you describe.

Quote:

Original post by Smit 1) Should anything that needs to be in the scene graph be based on a single class which acts as a base?

That's probably convenient, but you may want a different base for each "view" of the scene graph (one for a spatial view, one for a transform view, etc). You can actually pull some template magic to make this work without duplicating code though.

Quote:

Original post by Smit 2) I get getting confused about using scene graphs and octrees/quadtrees/bsp trees together. I understand what they are individually, but how do I link them? Would I put the root node of an octree for instance into the scene graph and then go through the octree once I reach that node?

You can encapsulate one inside the other, but it's often handy to have a one->many relationship between views in the scene graph. To this end it's handy to do something like have the transform node create and manage a spatial node (or multiple spatial nodes), feeding it transformation information as necessary. The spatial node in turn can handle spatial information such as bounding volume hierarchies, etc.

This design extends easily to things like a scripting view controlling the transform view, etc.

Quote:

Original post by Smit 3) Would every node that has something rendered also have a bounding box? A parent node should have a bounding box that is large enough for all of the children?

The way that I do it is that every node in the transform graph has a local transformation (and also caches the global model->world transform consisting of the composite matrices on the path from this node to the root). Every spatial node contains a bounding volume that is guaranteed to include all children.

The advantage of doing it this way is that no unnecessary information is stored (for example, bounding volumes for transform nodes), and yet there are strong invariants about what each node and its children contain. Furthermore the C++ type system works well with no casting needed to deal with specific node types (which is evil, and defeats much of the purpose of the polymorphism).

Hope that helps somewhat.

Quote:

Original post by Smit 1) Should anything that needs to be in the scene graph be based on a single class which acts as a base?

Yes basically you'll have a SUPER class at the upper level.
It will feature the required functions which will be virtual or abstract to provide services you'll need everywhere.
SceneGraphs are a way to uniformely access the "world". (Every "object"/"entity" of the world)

Quote:

2) I get getting confused about using scene graphs and octrees/quadtrees/bsp trees together. I understand what they are individually, but how do I link them? Would I put the root node of an octree for instance into the scene graph and then go through the octree once I reach that node?

An Octree/Quadtree, whatever structure you want to insert is just going to be a SceneGraph Node, like everything else. (Alternatively you can make the OctreeNode/QuadtreeNode a SceneGraph Node, depends on your implementation details.)[Just like you said, you can do either]

Quote:

3) Would every node that has something rendered also have a bounding box? A parent node should have a bounding box that is large enough for all of the children?

You are describing a Bounding Volume Hierarchy, (parent's BoundingVolume encapsulate children Bounding Volumes) and it's an effective way to cull batch of geometry, it is desirable to do so.

Basically your whole engine will have two tasks, first find the most accurate set of what's visible (not exact set since it's too expensive), second render everything that is visible.

Here's a link to the WildMagic 3 engine (From 3D Game Engine Design/Architecture books)
http://www.geometrictools.com/
Should give you at least some ideas.

What will compose your scenegraph depends on what you will be using it for. A scenegraph can be a simple render tree with state sorting (sort of low level scene graph), a completely abstract definition of the universe targeted at easy application management, a specialized culling system like Quadtree and such,... .

In my engine, the 'scenegraph' is the interface with the client application for manipulating the universe. Therefore it is designed to be very high level. Here are the design choice I have made and with which I'm happy at the moment ;
- Completely separate culling information from scenegraph (i.e. the quadtree, pvs, ... goes in a dedicated structure which is not part of the scenegraph but kept up-to-date with the scenegraph) ; it allows you to have a culling agnostic scenegraph which can be culled with different methods (for example camera culling, spot light culling, directional light culling do not have the same requirement and therefore may lead you to use different culling method).
- Prohibit any low level rendering information inside the scenegraph (for example, you define the way a renderable is rendered as a functionnal material ; the way it will be rendered is left to the renderer) ; this allows to let the scenegraph evolve with the technology.

Regarding your first question, I have choosen to have a base interface (not class) for all nodes and provide a default implementation of this interface. Here it is ;


Note that these choices are the one which fits my needs and are very dependent on your needs (I think, a low-level scenegraph is most suited for a lot of application). And I don't pretend these are the best choice either.

Vincent

Let me offer another view on this. As Niwak said, there's no single best choice, it depends on what you need.

Quote:

Original post by Smit 1) Should anything that needs to be in the scene graph be based on a single class which acts as a base?

Depends. See my rant about inheritance in scene graphs.

Quote:

2) I get getting confused about using scene graphs and octrees/quadtrees/bsp trees together. I understand what they are individually, but how do I link them? Would I put the root node of an octree for instance into the scene graph and then go through the octree once I reach that node?

Like AndyTX already said, the best way to go is to have multiple "views" on the scene. A scene graph is one. But it's not useful for all purposes, like collision detection, some forms of culling, or figuring out which nodes are near some point (you will need this, think of eg. figuring out which objects are affected by explosions). So your nodes would be stored in both a scene graph, linked together, and an octree/quadtree/bsp/whatever. It's also useful to have a plain list of all nodes in the scene.

-Jussi