Recursive techniques for scene graphs

Anyone who know any good papers on recursive scene graphs ?

I am working on a recursive model and wondered if you guys had any thoughts about this.

Some thoughts of mine…

When creating e.g. a tree. Would you need a switch behaviour to switch in different node paths depending of recursion level.

When building a graph, would you need recursive levels of recursive contents. e.g. kind of stack of recursive contents… e.g. to create recursive leaves as a child of a recursive branch…

When rendering 10.000 (just a big number) recursive nodes, would you recurse each node at a time or would you recurse each node in a pass in parallell. I guess you could limit state switches if you did the latter…

Well that went down like a lead balloon, didn’t it tooltech?

Well. Pretty boring topic I guess :wink:

Tooltech, just out of interest, do you use your scenegraph traversals for culling, collision and state changes?
If you do, then you’re not going to get good performance - scenegraphs are only good for representing hiearchical coordinate systems, they’re no good for culling, no good for state management, no good for collision detection - they’re a coordinate hiearchy, not a spacial hiearchy, therefore are not the right tool for the job.
The only recursion down your scenegraph you should be doing is to update absolute transforms.

Well. I get very good performance anyway :wink:

I use it for culling,traversal, rendering, collision detection etc…

What do you mean it is not good for spatial info ? It is very good for that in my oppinion…

How is it good?
How do you build your scenes? Do you build them with a spacial criteria, or a render state criteria? Do you take in a poly soup and spacially sort your scenegraph?

You use it for collision? Tri-to-tri? Ray-to-tri?
You have a geonode (or whatever you call them) containing a huge mesh (500>tris)…you check your tri/ray with every triangle? Even if you select the lowest LOD, it’s still going to give bad performance.
My point is, scenegraphs are good for some things, but really quite slow and awkward for others. A unified approach is needed - get your coordinate system data from your scenegraph (and other inherited properties), get your state changes from your shader state block, get your collision info from a quadtree/octree/bsp depending on the type of scene you’re rendering (bsp for highly occluded scenes etc.).

The big chunk of geometry in your example is in my oppinion one special case of geometry. The scene graph detects the boundary of the geometry and then lets the actual geometry decide what it hits. That procedure is in your specific case a octree, but could be other methods for other geometries like high level surfaces etc. Very clean design. Scene graph is great for that…

State changes is for rendering purpose. The scene graph does traversal and the rendering pipeline optimizes for state changes. Scene graph does optimis like same state for multiple instances of data etc. minmal state changes between hierarchy nodes etc. very good for that purpose. Dont mix with rendering state sorting.

That’s really confusing. Isn’t an octree a scene graph ? If not, what’s your definition of a scene graph ? If it is, i fail to see how it’s bad for culling for example…

Y.

Originally posted by knackered:
Tooltech, just out of interest, do you use your scenegraph traversals for culling, collision and state changes?
If you do, then you’re not going to get good performance - scenegraphs are only good for representing hiearchical coordinate systems, they’re no good for culling, no good for state management, no good for collision detection - they’re a coordinate hiearchy, not a spacial hiearchy, therefore are not the right tool for the job.

I feel you’ve misunderstood what a scene graphs are about.

Scene graph are extremely good at managing spatial composition, they are tree, perfectly designed for culling, be it view frustum of occlusion culling, occlusion culling, cluster culling, small feature culling & LevelOfDetail culling.

Scene graph can also be extremly good at managing state, although this doens’t come from the scene graph structure but the post processing after the cull traversal that decent scene graphs usually employ.

Culling and sorting the fundamentals why scene graphs provide such good peformance. This is why scene graphs are standard tool for large scale visualization projects.

Robert.

Just to jump back to my original topic.

I can now clearly see that using recursive data in a scene graph makes it possible to make very realistic trees.

Any comments on new scenen graph nodes like

Recursive switches - switch in data dependant on recursion level

Seed switch - to make e.g. position dependant seeds for recursive fractals

Recursive lods - lods that control level of recursion.

etc. Any comments on this or have you made simillar work ??

Hi, don’t know about the scenegraphs, but here’s how I’d do the trees:

First generate a small branch and make textures out of it so you can roughly approximate the branch by three triangles textured by this texture.

Then you generate a slightly bigger branch so that when the width becomes smaller than the initial width of the previous branch, you replace the rest of the branch with the triangle-approximation of the smaller branch. Make a new texture from this branch. Repeat until your final branch contains the whole tree.

Now, when drawing the tree, depending on the level of detail you replace the ends of branches with a certain width by the appropriate texture approximation.

You should have several different sets of textures for branches going into different directions so you can approximate gravity in the branches.

I hope this makes sense. Perhaps it’s not as good as whatever you’re thinking of, but it’s one way to render fast recursive trees.

-Ilkka

Ok. I see. I think we have the same thoughts. However I am trying to make a scene graph approach… Like my code for a tree node is like this…

gzNode *buildTree()
{
gzGeometry *geom=new gzGeometryTube(40,1,5,5,GZ_TUBE_CONE,xyfunk,10,10);

geom->useDisplayList(TRUE);
geom->setLocalIncludeBoundary(TRUE);

gzTransform *endNode=new gzTransform;
endNode->setScale(0.4,0.7,0.4);
endNode->addNode(geom);

gzRecursive *tree=new gzRecursive;
tree->setLocalIncludeBoundary(TRUE);
tree->setDistanceDepthEquation(1000,1);
tree->setMaxDepthNode(endNode);

gzMaterial *material=new gzMaterial;

gzState *state=new gzState;

state->setMaterial(material);
state->setMode(GZ_STATE_MATERIAL,GZ_STATE_ON);

gzTexture *tex=new gzTexture;

tex->setImage(gzImageManager::loadImage(“bark.bmp”));
tex->setWrapS(GZ_REPEAT);
tex->setWrapT(GZ_REPEAT);

state->setTexture(tex);
state->setMode(GZ_STATE_TEXTURE,GZ_STATE_ON);

geom->setState(state);

gzTransform *trans_1=new gzTransform;
trans_1->setLocalIncludeBoundary(TRUE);
trans_1->setScale(0.5,0.5,0.5);

trans_1->addNode(geom);

tree->addNode(trans_1);

gzGroup *crown=new gzGroup;
crown->setLocalIncludeBoundary(TRUE);

gzTransform *trans_2=new gzTransform;
trans_2->setLocalIncludeBoundary(TRUE);

trans_2->setHPR(0,-20,10);

trans_2->setScale(0.2,0.5,0.2);

trans_2->addNode(tree);

crown->addNode(trans_2);

gzTransform *trans_3=new gzTransform;
trans_3->setLocalIncludeBoundary(TRUE);

trans_3->setScale(0.2,0.5,0.2);

trans_3->setHPR(0,-30,80);

trans_3->addNode(tree);

crown->addNode(trans_3);

gzTransform *trans_4=new gzTransform;
trans_4->setLocalIncludeBoundary(TRUE);

trans_4->setScale(0.2,0.5,0.2);

trans_4->setHPR(0,30,-50);

trans_4->addNode(tree);

crown->addNode(trans_4);

gzTransform *trans_5=new gzTransform;
trans_5->setLocalIncludeBoundary(TRUE);

trans_5->setScale(0.2,0.5,0.2);

trans_5->setHPR(0,-30,-30);

trans_5->addNode(tree);

crown->addNode(trans_5);

gzTransform *trans_6=new gzTransform;
trans_6->setLocalIncludeBoundary(TRUE);

trans_6->setTranslation(0,20,0);

tree->addNode(trans_6);

trans_6->addNode(crown);

gzTransform *trans_7=new gzTransform;
trans_7->setLocalIncludeBoundary(TRUE);

trans_7->setTranslation(0,10,0);

tree->addNode(trans_7);

trans_7->addNode(crown);

tree->setMaxDepth(3);

return tree;
}