Sign in to follow this  
acid2

Scene graph design problems (rendering + frustum culling)

Recommended Posts

Hey, I've got my scene graph working quite nicely at the moment, with support for the visitor pattern and stuff making it quite extendable. I now want to make it more extendable and object orientated. My idea is to have "pipelines" that manipulate the scene graph somehow. For example... Frustum cull -> depth sort -> reflection render -> refraction render -> render to display. Things such as the reflection render and the refraction render are easy to create, because they don't manipulate the scene graph at all, they just perform an operation on it (in this case, rendering). But how does the frustum cull pipeline state tell the depth sort renderer, what to depth sort?! For example, a node is not visible - so do I flag the node as node visible (ie thisNode->visible = false), or do I create a scene graph at runtime and graduly remove needs from this scene graph. The latter sounds much better, because creating new pipeline stages does not require me to touch any existing node types - but it does double the memory of the entire scene graph. What are your thoughts?

Share this post


Link to post
Share on other sites
It seems to me that the results of the frustum cull should be an intrinsic property of the resulting scene graph structure, not something individual nodes in the graph should have to worry about. As I was doing the frustum culling, I would make a copy of the parts of the scene graph that aren't culled. That way you aren't making a full copy of the tree and just pruning the culled parts, and you don't have to add a special variable just for visibility.

Also, take the case where the scene is rendered from multiple views. It wouldn't seem practical to have a visibility variable for every possible view.

[Edited by - Zipster on November 3, 2005 3:10:01 PM]

Share this post


Link to post
Share on other sites
So you mean, for each render - I should create a new scene graph? So, the frustum culler would create the scene graph, and pass it on to something like a depth sorter?

Share this post


Link to post
Share on other sites
The idea that I'm tossing around at the moment for my scene graph system is this:

I have a single iterator traversing the graph, mutliple visitors on the iterator, each visitor can maintain whatever kind of information it needs (stack, state objects, whatever). I'm also doing "weird" things like including user interface information and sound effect information in the scene graph, so when I hit a bounding box node with the GraphicsVisitor, I disable the graphics visitor, but push the bounding box node onto a stack so that I can enable the visitor on the "leaving" visit. I must continue to traverse the graph in case a sound effect was placed within the bounding box which might end up behind the viewpoint but still audible (a strange case which I might determine to be impossible, and decide later to skip child traversal).

Right now, I render objects during traversal (which I realize doesn't work with depth-sensetive stuff), but I am probably going to end up spitting out some kind of per-frame-scratch render command lists which I can depthsort (for the lists that contain depth-sensetive objects) and optimize for render-state-changes.


So you might use a similar approach - use the scene graph for persistent data storage and some throw-away lists of render actions generated from the traversal. I'm not sure what the advantages or disadvantages of having two scene graphs would be...


Remember, just an idea - I haven't implemented more than a rudimentary object oriented scene graph system so far.

Share this post


Link to post
Share on other sites
Hmm I don't really understand what your problem is but here is what I would do (WILL do, when I have the time to work on that project ^^)


// this function recursively walk through the SG. We assume a previous
// pass updated the BBs, and culling information
// The frusum culling takes place here. If a node isn't visible,
// we discard the whole sub-tree. We could also add a boolean to avoid testing
// the visibiliy : if a BB is entirely inside the frustum, all the children are
// inside the frustum, we don't need to test it.
void OnRenderWalk(CNode *node)
{
if (CFrustumCulling::Cull(node) == INSIDE)
{
for (int i = 0; i < node->_nbChildren; i++)
OnRenderWalk(node->_child[i]);

// in this function, the node send its data to a renderer.
// by "data", I mean all the informations that the renderer will need
// to render the node (buffers, shader, textures, render states, etc.)
node->OnRender();
}
}





the important thing is that this pass don't touch the structure of the SG. It does not modify it, does not create redundant information. Each visible node only send pointers to its data to the renderer. And THEN, the renderer only has the visible entities, and can do its job : sorting by depth, shader, textures, or whatever criteria you want.

Share this post


Link to post
Share on other sites
Quote:
Original post by paic
Hmm I don't really understand what your problem is but here is what I would do (WILL do, when I have the time to work on that project ^^)

*** Source Snippet Removed ***


the important thing is that this pass don't touch the structure of the SG. It does not modify it, does not create redundant information. Each visible node only send pointers to its data to the renderer. And THEN, the renderer only has the visible entities, and can do its job : sorting by depth, shader, textures, or whatever criteria you want.


This is how I initially implemented my pipeline as well: passing on pointers to visible data to the next stage in the pipeline. Unfortunately, although elegant this approach has one big problem that also applies to the pipeline acid2 described. It effectively removes all culled data from the pipeline, which means that subsequent stages cannot access those anymore. Unless you have an incredibly fancy culler, the reflection render will not be able to access any parts of reflected scene that are not within the view frustum.

I personally went for the thisNode->visible = false approach (actually I have two flags visible and culled, to separate culling within the pipeline from user defined culling). It's ugly, but very simple to implement. It is true that this approach modifies data within the scene graph, which is undesirable. More advanced solutions that don't modify scene graph data are possible, but they require a separate mechanism for pipeline stages to communicate...

Tom

Share this post


Link to post
Share on other sites
Hi,

Who said you need to only fill your renderer once per frame ? ^^
You can re-fill your renderer many times per frame. For example, take the shadow mapping. You would create a pass where the camera is at the light place, render your scene to a texture. Then, you would have a second pass (the renderer is cleared after the first pass) and you would re-render from the user's point of view.

For each pass, their is a visibility pass which re-fill the renderer. This way, you take advantage of your culling algorithms in any situation.

You could also have the possibility to pass everything to your renderer plus a boolean "bVisible". Then the renderer would consider only the visible entities, but still have all the infos about invisible entities. But I don't recommend that.

Share this post


Link to post
Share on other sites
Quote:
Original post by paic
Hi,

Who said you need to only fill your renderer once per frame ? ^^
You can re-fill your renderer many times per frame. For example, take the shadow mapping. You would create a pass where the camera is at the light place, render your scene to a texture. Then, you would have a second pass (the renderer is cleared after the first pass) and you would re-render from the user's point of view.

For each pass, their is a visibility pass which re-fill the renderer. This way, you take advantage of your culling algorithms in any situation.

You could also have the possibility to pass everything to your renderer plus a boolean "bVisible". Then the renderer would consider only the visible entities, but still have all the infos about invisible entities. But I don't recommend that.


Ok, that makes sense. I guess what you're saying is that in the acid2 pipeline the reflection render is misplaced:
frustum cull -> depth sort -> reflection render -> refraction render -> render to display

And that it should have its own pipeline, making two separate pipelines (to be executed in this order):
reflection frustum cull -> depth sort -> reflection render
camera frustum cull -> depth sort -> refraction render -> render to display

Tom

Share this post


Link to post
Share on other sites
Yes, seemeed like my word of pipeline was a bad choice. But what you suggested dimebolt seems cool. Now all I need to do is work out the most efficient way of duplicating the scene graph in C#

Share this post


Link to post
Share on other sites
Normally past the frustum cull stage you only need a render list, not a scene graph (although there *may* be cases that one could make for the latter). This will help a lot when you start doing state sorting, etc.

Thus your frustum cull traversal simply spits out a list of renderable chunks as they are found and subsequent operations operate on this list.

You could certainly maintain some sort of tree structure, but there's a lot of nodes that no longer have use after travsformation and culling and carrying them around just to maintain the structure of the tree seems somewhat wasteful, unless there's a specific need to have the tree structure later (that can't be address by the aforementioned recursive rendering).

Share this post


Link to post
Share on other sites
I currently think about doing it like this:
I´ll do the visibility testing on my scene-graph and send the visible geometry over to the renderer, including the shader, texture, material (...) and transormation matrix I want to use.
The renderer receives that and puts it into a tree according to the shader and texture. That tree should look something like that:


root
|- Shader A
| |- Texture A
| | |- Geometry A
| | |- Geometry B
| | |- Geometry E
| |
| |- Texture B
| | |- Geometry A
| | |- Geometry D
| | |- Geometry F

...
you get the idea

this way I´m trying to get around sorting the render-list after the visibility testing and I think this could do the trick. But perhaps I´m missing something, so any suggestions welcome ;)

a bit off-topic but I think still related:
I think about leaving the static part of the map out of my scene-graph. Because of it´s structure the static map could be culled quite good by use of a quadtree (perhaps octree, still have to decide about a feature of the game). So I came up with another thought:
Perhaps a system might be useful where every dynamic object notifies a node in that static map quadtree which it is included in. Now, when culling the quadtree, an invisible node could notify the scenegraph that all dynamic objects contained inside it should be declared invisible, too. After culling the quadtree the only thing left to do would be traversing the scene-graph sending every visbile node over to the renderer.
Any draw-backs except that every dynamic object that changed its position would have to check whether it has changed quadtree-nodes and notify the two nodes?

Share this post


Link to post
Share on other sites
Using a state tree for sorting works of course, but it's no faster than actually just sorting the render list. Both are O(nlogn)... the specific constants will vary a bit depending on how you implement each. Actually if you use a list and implement a radix sort, you can get it down to O(n) :)

The only thing you can really do to avoid the sort is to take advantage of some frame->frame coherency by "modifying" the list from last frame instead of totally regenerating it. This works best if you're renderer isn't heavily recursive. That said, this coherency can be harnessed both in the list and the tree sorting implementation.

Anyways I wouldn't be too concerned about the sorting time... I use a simple STL sort on the render list and it's BY FAR never the bottleneck. Maybe it would be worse if you were rendering millions of tiny chunks, but in that case the bottleneck would shift to changing shaders and/or API overhead for the small batches.

Summary: I wouldn't be too worried about the sorting time, as it's unlikely to be a bottleneck, even with thounsands of chunks to sort per frame. I suspect that like the rest of us, sorting will be the least of your performance problems ;)

Share this post


Link to post
Share on other sites
Nice thread going out here.
I am also designing my scene graph, and got into the same issue matches81 pointed out (about quadtrees and dynamic objects).
Here is my idea:


Let's say we have a quadtree of of depth 2. Segments of the quad tree are indexed from 1-4 within each level (so in the second level we have 1.1 1.2 1.3 1.4 2.1 2.2 ... 4.4)

Quadtree node (QN) dynamically create helper nodes (HN) between dynamic objects nodes (DON) attached to it.

When you attach a single DON to QN into 1.1 segment, your scene graph looks like:


QN
|
HN (1)
|
HN (1)
|
DON


When you move your DON to 1.2, the scene graph's node HN(1) for the second level is destoryed, and another
node HN(2) is created in it's place. If there would be other DON's attached in 1.1, then the
HN(1) node is not removed, and we would get:


____ QN
_____ |
_____HN(1)
_____|___|
__ HN(1) HN(2)
___ | ___ |
__ DON _ DON (another)

[the "_" chars are there to force spaces in the diagram]

DON's do not have to inform quadtree about their position changes. Instead of this HN's keep track of it's children (only DON ones) bbox'es, and communicate with quadtree. Yann L has written about degenerate factor of the nodes in one of the threads. In this case parent nodes (HN's) do not allow any degeneration - we want dynamic nodes to fit exactly in quadtree segments


Visibility of HN nodes is not tested by camera frustum culling. The only tested thing is the visibility flag set by QN they (the HN's) belong to. This allow's QN to control all the visibility and allow to introduce stuff like PVS or other optimizations, that wouldn't fit into the scene graph themselfs.


That are the benefits?
- You don't have to hold extra visibility flag updated by quad tree
- In case you have more that one dynamic object in the same quadtree segment, there is no need to test every object against the whole quad tree in case of object's or camera's movement (objects are grouped).



Please tell me what you guys think about this.
cheers

Share this post


Link to post
Share on other sites
hmm.... don´t know what the helper nodes are there for? Perhaps I just didn´t get it, but as I understood it, they are only there to build a link between the quadtree nodes and the dynamic objects? If so, why not just put a vector of pointers to dynamic objects directly into the quadtree node?

Share this post


Link to post
Share on other sites
1.
You would still need some sort of grouping system to speed up visibility updates. Imagine you have 100 objects in one quadtree segment. During quadtree node visibility update you find out that this segment becomes invisible. With grouping you don't have to iterate every object.

2.
In your approach every node would need to have an extra visiblity flag just for quadtree or similar "container" nodes (like octrees or other) - in my opinion this extra flag is more like a hack. More on that in point 3.

3.
It would be nice to have some smart connection between dynamic objects and quadtree. What would you do when a dynamic object is destroyed? - with a simple pointers array you have to remove a pointer from quadtree in some way. In my approach you just have to check (during scene graph update) if there are some bbox'ed objects connected to helper nodes, or better - write node add/remove functions so that it would automatically inform its parent node about addin/removing/translation, and allow it to react [helper nodes would simply inform it's parents (in this case another helper nodes or quadtree node), and quadtree node would modify it's underlying helper nodes subtree if neccesary].

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