Sign in to follow this  

SceneGraph and Game Engine

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

3D engine works with SceneGraph that containt 3D models which can be rendered. A walkthrough in this graph determine which object are visible and put them in a rendering queue. But what about the model view matrix ? I think this model view matrix is put in the rendering queue at the same time. So if we have a RotationNode in the scenegraph this one can be written (in pseudo code) like this : Rotate if CurrentModel is visible put it in the rendering queue walkthrough childs Rotate opposite way With Rotate a GPU function (like glRotate for example). In this case the CPU doesn't know the position and orientation of each model. However if we wants to add sound or physics to the game engine, we must know the position of each model. So there is two solution : 1/ Query the GPU to have the modelview matrix and retreive the position and orientation of the models. But this is going to increase the GPU/CPU traffic. 2/ Execute the orientation and position calculation on CPU but in this case, we don't use the T of T&L. I am something wrong in my scenegraph implementation ? What is the best solution to this problem ? Best regards

Share this post


Link to post
Share on other sites
I think generally before rendering you traverse the scenegraph (ususally in a DFS).

Each leaf or model node (if you have geometry in places other than the leaves) should store a local transform, so what you do is:

start at the root node
store the transform at the root
visit the first child
multiply the transform there with the stored transform
save this as the "world" transform of the node
( repeat for all nodes in a recursive manner )

That way all nodes not only contain local transforms, but also global ones that you can easily use for collision detection etc.

Yes this is more CPU intensive than just letting the graphics API do it all with glMultMatrixf() but gives you more power overall.

I hope this is what you were asking and not what you already know,

Rob

Share this post


Link to post
Share on other sites
When I read your post I assume that you want to use a Scenegraph for visibility determination. Scenegraphs shouldn't be used for that job - its "just" a data structure that represents how your scene looks like (how the different objects are hierarchically connected with each other).
There are a few interessting posts about this topic listed on this site where Yann explains scenegraphs.

Share this post


Link to post
Share on other sites
Actually if you propagate bounding volumes up the scene graph (i.e. so each parent has a BV that fully encloses each of its childresn VBs) then you can do very efficient frustum culling, rejecting entire subtrees at once.

Share this post


Link to post
Share on other sites
Here's a quotation from Yann (look also here):

Quote:
Original post by YannL
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.


Of course you can combine a Scenegraph with a spatial data structure (however there are a few things to watch out - see Yann's answers in this thread).

Share this post


Link to post
Share on other sites
Hi, not an answer to your question, sorry, but instead, a question (didn't want to post a second thread on scenegraph just after this one ^^)

How do you handle the special cases in a scenegraph ? From what I did understand, it basically consist on an abstraction layer (for example, a virtual class providing the render functions, etc. from which every drawable will inherit) and on a graph in which you store the different entities of the 3D world.

But my problem is with the virtual classes. Say I want a simple mesh to inherit from this class, it will have all the function to load, update, render, etc. But if I add a class which handle billboards, I'll have to give the user position to this class. So if I use a virtual class, I'll have to add a setter in it, and every entity of my scenegraph will have it ?

If it's done like that, then you have a lot of setters / getters to implement to be able to handle every cases that might occure, right ? Did I misunderstood, or is there another way to do that ?

.:: Paic Citron ::.

PS : forgive me if it's a newbish question, i'm quite new to scenegraphes, resources managers and those kind of higher level stuff in 3D engines ^^

Share this post


Link to post
Share on other sites
ugh now I am at a loss as to the design of my engine.

The book I am reading ("3d game engine architecture" by Dave Eberly) seems to use the "scene graph" (actually more of a BV tree) only for hierarchial transformations and frustum culling, but this is exactly what Yann says not to use it for.

Am I meant to use a scene graph for physics etc, and a BV tree for rendering (i.e. two separate data structures to represent the same set of objects)?

Share this post


Link to post
Share on other sites
Dave's book is good but not for fps games :) The guy has a background in 2D medical field and thus the way his book is written. If you want to know how to do it look at some game engine source code and articles on the web. Don't forget the balance between traversing the structure vs. brute force drawing. I've seen demos where an octree was actually slower than brute force drawing. You might use terrain itself and anti-portals or something similar. Or you can design the terrain in a certain way to favor your vis. algo. There have been games made like this and people who played them thought, "why do I feel like walking thru a valley?" :)

Share this post


Link to post
Share on other sites
Quote:
Original post by mictian
ugh now I am at a loss as to the design of my engine.

The book I am reading ("3d game engine architecture" by Dave Eberly) seems to use the "scene graph" (actually more of a BV tree) only for hierarchial transformations and frustum culling, but this is exactly what Yann says not to use it for.

Am I meant to use a scene graph for physics etc, and a BV tree for rendering (i.e. two separate data structures to represent the same set of objects)?

I think that many people have a different understanding of the term scenegraph (and therefore have other opinions in terms of what it has to contain/can be used for and what not).
The decision if you use the SG only for the logical representation of your scene or if you use it for more depends on you. As Yann wrote in his posts SGs and spatial data structures can be combined into one tree.
You can also have a SG, a spatial partitioning tree for culling and another tree (BSP/Kd) for CD.

Share this post


Link to post
Share on other sites
Quote:
Rotate a GPU function (like glRotate for example).


The "T" in "T&L" on the GPU knows how to take vertex values, and transform them by matrices; it's very efficient at doing this by the thousands. It is not efficient at constructing a single matrix and multiplying it with a single other matrix -- the overhead of batching would far outweigh the offload of the CPU.

Thus, all graphics drivers will perform glRotate() on the CPU to keep the modelview matrix up to date. When time comes to blat the vertices to the screen, it sends the current matrix and the vertices to the card for transformation and lighting.

However, most scene graphs and rendering engines don't actually use glRotate() and friends to specify the modelview; instead, they keep some concept of position and orientation (typically, a vector and a quaternion), and another concept of camera position/orientation, and combine them all into a single matrix that gets loaded with glLoadMatrix().

So, when you traverse your visibility tree (or whatever) and queue a mesh for rendering, you'll typically just queue a pointer to an interface encapsulating the mesh data and its transform state. Then when the queue is executed, you'll call into that interface to extract the matrix, and the geometry to draw.

The more interesting questions to answer in scene graph design are questions such as whether transformations are material state or geometry state. This, in turn, affects how you sort, batch, and present your geometry for the card, as well as how the programmer and artist interacts with the system.

Share this post


Link to post
Share on other sites

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