scene graphs?

[supagu]

okay i have read some articles about scene graphs, but most only deal with transforms, it would be good to see one covering sorting the scene by render states. eg. sorting shaders/textures/transparency etc... as this is one area i am intrested in looking at, but cannot find much info on at all.

[MikeMJH]

Well, in my opinion (largely inspired by Yann L.), scene graphs are used as a hierarchical representation of your scene, and should not be used for sorting render states. That is the job of the render queue (or whatever you'd like to call it).

That said (sorta useless, I know), I too would enjoy reading an article about render sorting.

[anubis]

www.radonlabs.de

the nebula device implements a scene graph as well as render state sorting

[supagu]

okay yeah render sorting, an article on that would be great.

[anubis]

Yann L's opinion (http://www.gamedev.net/community/forums/topic.asp?topic_id=183462)

this is just one of the things my search on google/gamedev turned up...

[supagu]

i'll paste it in for ease:

"Good state sorting generally requires both a preprocessing and a realtime pass. Your objects or instances should be presorted by material (or shader/parameters, if you use a shader based approach). This is only needed, if an object is built from more than a single material, but this is often the case. Let's call those presorted object parts 'subobjects'. Each subobject has a unique material (or shader-parameter pair), several subobjects form an object. You only store the object in the scenegraph. The object contains a pointer to its child subobjects.

In realtime, as soon as an object is considered visible, you process all subobjects. Here, you have several possibilities. You could add the subobjects to material lists, as sBibi suggested. A hashing algorithm could help, if you have a large number of materials. This approach usually works well, if you work with simple materials, but has a huge drawback on complex material or shader based approaches. Imagine having several subobjects of the same shader (material class), but different parameters. For example, you have 6 subobjects with the shader 'diffuse texture'. 3 have texture "bricks", and 3 have the texture "wood". Since all have the same material class, they will all be added to the same list. That is OK so far. But as there is no inherent order in which they will be processed (viewpoint dependent), they could be added to the material list in any order. Imagine this situation:

List(diffuse texture) -> SubObj0(wood) -> SubObj2(bricks) -> SubObj3(wood) -> SubObj4(bricks) -> ...

As you can see, all diffuse texture subobjects are grouped, reducing state changes. But their parameter (the texture) is not, requiring a texture bind at every subobject. Not good.

An alternative is to sort (radix/merge/quicksort) by material and parameter(s) every frame. That will cost more performance, but can be very worthwhile on complex scenes with many different materials. In this case, you only have one single render list (instead of multiple ones as above), where you simply dump all visible subobjects. It doesn't have to be a linked list, a simple array will do. Then, just before rendering, you sort the whole list by shader/paramater:

List before sorting (same order as above):
SubObj0(wood)
SubObj2(bricks)
SubObj3(wood)
SubObj4(bricks)

List after sorting:
SubObj0(wood)
SubObj3(wood)
SubObj2(bricks)
SubObj4(bricks)

The parameters are now also grouped, reducing the number of required state changes even more."

Yann L - http://www.gamedev.net/community/forums/to...topic_id=183462 (http://www.gamedev.net/community/forums/topic.asp?topic_id=183462)

[supagu]

okay, i have complex materials:

i have a material class, which holds a number of textures, and shaders.

when i set my material i set the standard GL material parameters, then bind all my textures, and bind a vertex and pixel shader,

so lets say i have:

Material A:
textures:
-wood
-grass
shaders:
-phong.vert
-phong.frag

Material B:
textures:
-rock
-grass
shaders:
-phong.vert
-phong.frag

Material C:
textures:
-wood
shaders:
-felt.vert
-felt.frag

firstly, the materials should be sorted by shader, then texture (changing shaders is slower i think)

so material A,B,C is ordered when sorted by shader

this would be the optimum order:

B:
-phong.vert, phong.frag
-rock
-grass
//render models using material B

A:
-wood
//render models using material A

C:
-felt.vert, felt.frag
//render models using material C

how do we get a nice list like this though?

[supagu]

http://www.delphi3d.net/articles/viewartic...le=stateman.htm (http://www.delphi3d.net/articles/viewarticle.php?article=stateman.htm)

looks like it solves the problem, this is the idea i was thinking about, some sort of tree, but have to work out how to implement it with shaders....shouldnt be hard.

heres my attempt at what it would look like with a shader tree:

|
--phong.vert, phong.frag
| |
| ----rock
| | |
| | -----grass
| |
| ----wood
| |
| ------grass
|
-- felt.vert, felt.frag
|
---------wood

(i have assumed a texture in channel 0 has a greater priority than in texture unit 1)

with this tree, seems okay, but if it ended up with under phong being wood, then rock, we would have to reset wood when we get to the felt shader :-/

this could be fixed i think, not just by sorting down the tree,
but sort across the tree (across the branches)

[anubis]

i guess you won't abel to always order your materials in a way so that you never have to reset a texture or shader, the question here is which state changes are the most expensive to do. you should find out about this and sort accordingly

[supagu]

yeah, the deeper you go into the tree, the more redundant calls there are :-|

unfortunately, textures would be set redundantly, i think its more expensive to set shaders.

i was thinking of maybe trying to use a graph data type, using the shader as an entry point:



phong felt
| / \
rock wood wood
| /
grass



as you start at the top, work your way to the bottom, somehow to sort this.

so maybe some combination of tree and graph ;p
who knows :-/

[supagu]

okay i implemented a shader tree,

i get 3 times the frame rate with the tree, compared to the scene with no sorting...
im not sure how it compares to my old engine which i just used to sort by material, i do get lower frames, but this is probably because each mesh is only a few polys, while my old engine had a few thousand polys per material (the batching delema ;p )

:blush:

ran vtune over my app, and 90% of the time is spent on in the drivers....

[anubis]

i think its more expensive to set shaders.

definitely...

ran vtune over my app, and 90% of the time is spent on in the drivers....

which is normal depending on what you do

did you use shaders in your old engine ? they eat up quite a big amount of performance. as for the low polycount problem : consider grouping smaller vbo's in one big vbo (~10000 vertices is optimal for nvidia cards according to their docs). this way you reduce buffer switches to a bare minimum