Jump to content
  • Advertisement
Sign in to follow this  
Nairou

Question: going from the scenegraph to the render queue...

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

Okay. I know that a scenegraph holds hierarchical data about every object in the world. It shows the parent/child relationship of all objects, and how to transform them in the world. But I have to take that and feed it (or a part of it) to the renderer. According to Yann's Material/Shader Implementation thread, each geometry chunk of each object is broken down and organized into render lists, sorted by category (and again by shader, depending on implementation). My question is, how is the scenegraph typically processed and fed to the renderer to end up in these render-friendly lists? Since these render lists are renderer-specific, I'm assuming the main game loop wouldn't try to create those lists, it would just process the scenegraph and feed the objects to the renderer in the best way it can (via an intermediate "scene block" of some sort), and then the renderer itself would loop through all of those object pieces and organize the components into lists for rendering. Thats a lot of sorting and processing. Is there a better way to feed the scenegraph to the renderer without either the game loop or the renderer having to know intimate details of the other? Any examples of how this has been done before?

Share this post


Link to post
Share on other sites
Advertisement
The way I do this on my scenegraph implementation is by exposing a public GetDrawList function in my scenegraph class. It takes a list of filters, and returns a map of <filter,list <drawable> > pairs. So, it's up to the renderer to ask for parts of the scene that it wants to batch. You still have to iterate over the entire scene, but at least you only have to do it once (you use the filters to generate a number of lists all in one pass through the scenegraph). The drawable type also has an overloaded operator< to allow me to do a sort() function, which will group them for fastest rendering... although I don't actually do the sort() because on my geforce 7 series hardware with my AMD X2 3800+, it's faster to just throw objects at the video card (even if in a non-optimal order) than waste CPU time sorting. I don't know that this is the best technique to use, but it works for me... I'm curious as to how others solved this problem.

[Edited by - venzon on July 24, 2007 12:15:55 AM]

Share this post


Link to post
Share on other sites
you could do some sorting work in the nodes that hold your drawable objects and upon rendering your traverse the graph, grab the node's map map<material,drawable> and build an additional map-of-lists map<material, map<material,drawable>&> where you hold references to the lists. Thats certainly cheaper than building a huge list of maps.
There s some point where it makes no sense anymore to sort further, so I suggest you to sort by material name, then shader
How likely is it, that you get a constellation of multiple materials with equal textures, does it justify a additional sorting step for textures?

Also take care about your drawable, maybe you should create an interface like this


class drawable
{
//
void generate_buffers(boolean_array
// bind buffers selection
void bind_buffers(bool vertex, bool normal, bool texcoord0,...,bool tangent, bool ....);
void bind_buffers(boolean_array);
// just pass primitives to the gpu
void render();
// unbind buffers
void unbind_buffers();
}


The reason I suggest this design is, you may want to implement shadowmaps somewhen in the future and it would be a wast of bandwidth to submit normals or tangents right?

I would add a mask or flag to the shader/material to determine which buffers your really need at load time

Share this post


Link to post
Share on other sites

I don't see why there should be any traversal of a scene graph during rendering. The scene graph describes spatial relationships and nothing about shading. The parts of the graph that get drawn can register with the render list for a given material, which happens once instead of every rendering. Render order can be determined beforehand by sorting all materials and their passes into a list, so there isn't a need to sort anything during rendering except for alpha blended overlapping geometry. Each pass for each material is traversed in the presorted order. If there are any pieces that need drawn for that particular material, they are drawn at that time. The scene graph only feeds the model transform to the process, and even this can be cached in whatever node is being rendered.

Share this post


Link to post
Share on other sites
How would presorting work in a situation where you are using hierarchical culling? e.g. in my engine all objects are stored in a bvh which is drawn top down, and all hit nodes are pushed onto the render queue in front to back order. That queue then still has to be further sorted by material, as it is not ordered wrt to the original objects lists.

Share this post


Link to post
Share on other sites
Quote:
Original post by ironpoint
I don't see why there should be any traversal of a scene graph during rendering. The scene graph describes spatial relationships and nothing about shading.


The scene-graph isnt or shouldnt be a spatial structure, it holds the logical relationship between nodes. The scene-graph cares not for where an object is located nor what it looks like (or even if it has a graphical or spatial representation). However as always, its a fuzzy concept and people mix and match to suite their needs.

From my understanding of Yann's engine, he traverses his scenegraph and at each renderable node (leaf nodes usually) the runtime requests a GC (Geometry Chunk), this GC is a structure that references geometry, textures, an effect and some other things.

Each GC is then passed to the render pipeline, this pipeline decomposes each GC into one or more SPGCs (Shader-Pass-Geometry-Chunks), basically a SPGC is like a GC except that rather than referencing an effect it references a specific shader. For example say an effect is composed of 3 shaders, a GC will decompose into 3 SPGCs.

The render-pipe line now pushes these SPGCs onto the render-queue. The render-queue basically consists of several pass-types (like a Pre-Process-Pass, or a Reflection-Pass for example), these pass-types are basically just lists of SPGC, each SPGC is added to the correct list (so a reflection shader is added to the reflection pass stage).

Now each SPGC within each pass-type list can be sorted to reduce state changes (or alternatively you could have sorted all the SPGCs in one big list before adding them to the pass-type lists, I dont see it makes a difference). For the sorting you basically want to sort by A) Render-target B) ShaderID C) Shader-States. However each shader will individually know how best to order its own shader-states, you shouldnt assume a set-in-stone way to sort the states as you cannot know which states will be the most expensive for a given shader, so each shader should have some sort of callback to sort its own states. So now the sorting routine becomes: sort by A) Render-target B) ShaderID C) Shader-callback

Now the renderer takes over, it iterates over each SPGC in each pass-type list one by one, it sets the render-target, sets the correct shader, checks to see whether a SPGC is already cached in the video-ram and returns a pointer either to that memory or it gets a fresh allocation of VRAM if it wasnt cached, allows the shader to set up and bind its own states however it chooses including filling the VRAM with vertices, renders the geometry using the states and vertex-buffer that the shader did bind, then lets the the shader handle the clearing up of anything special it might have done (like push/pop a matrix for example).

I think thats basically it [smile]
Notice how the render-pipline doesnt know a thing about the scene-graph, only about (SP)GCs and the scene-graph only knows about returning GCs.
The scene-graph iterator (or whatever is using the iterator) is responsible for making the GC requests to the scene-graph and feeding them through to the render-pipeline.

Share this post


Link to post
Share on other sites
Quote:
Original post by Nairou
My question is, how is the scenegraph typically processed and fed to the renderer to end up in these render-friendly lists? Since these render lists are renderer-specific, I'm assuming the main game loop wouldn't try to create those lists, it would just process the scenegraph and feed the objects to the renderer in the best way it can (via an intermediate "scene block" of some sort), and then the renderer itself would loop through all of those object pieces and organize the components into lists for rendering. Thats a lot of sorting and processing. Is there a better way to feed the scenegraph to the renderer without either the game loop or the renderer having to know intimate details of the other? Any examples of how this has been done before?


If you're aiming for a renderer-agnostic engine you should have some form of intermediate data structure into which you load art assets, or otherwise you would end up having a multitude of loaders for different renderers. This intermediate structure is what you pass to the render queue. As proficiently described by dmatter, Yann calls them GCs. GCs hold mesh-related info (vertex/index buffers) and effects using which that geometry chunk is to be rendered. These intermediate data structures would then be converted to API-specific structures during the cache updating stage and would be uploaded to VRAM or AGP memory. Of course you don't need to upload these already uploaded structures each single frame (and that's the whole point of having a VRAM resident buffer after all), just those ones that have been newly added to the render queue, such as terrain patches that have recently come into view in a paging system.

Share this post


Link to post
Share on other sites
Quote:
Original post by dmatter
Quote:
Original post by ironpoint
I don't see why there should be any traversal of a scene graph during rendering. The scene graph describes spatial relationships and nothing about shading.

The scene-graph isnt or shouldnt be a spatial structure, it holds the logical relationship between nodes. The scene-graph cares not for where an object is located nor what it looks like (or even if it has a graphical or spatial representation). However as always, its a fuzzy concept and people mix and match to suite their needs.

I guess if we are talking about a specific implementation where 'scene graph' already means something unusual, this is true. What is the purpose or logical relationship of the scene graph you are talking about? ownership, object lifetime, dependency of some value, rendering parameters?

In general, a graph that isn't constructed to maintain spatial information and relationships, in my opinion, shouldn't be called a 'scene' graph. The word scene implies a spatial organization such as in 'the scene of the crime'. The strongest logical relationship between chunks of geometry that requires a graph is spatial. I think that a scene graph shouldn't even imply a parent-child relationship (other than spatial), ownership, or object lifetime.

I see that Nairou's original question is about Yann's implementation. Without knowing the purpose of the scene graph, Its hard to say if there is a better way, just that a traversal over a spatial data structure and sorting aren't necessary at render time. I would consider scene level visibility determination a distinct step from rendering.

Share this post


Link to post
Share on other sites
Quote:
Original post by ironpoint
What is the purpose or logical relationship of the scene graph you are talking about? ownership, object lifetime, dependency of some value, rendering parameters?

Out of those I suppose I'm talking about ownership and object dependancy.

Quote:

In general, a graph that isn't constructed to maintain spatial information and relationships, in my opinion, shouldn't be called a 'scene' graph.

Well a scene-graph should maintain relationships of scene objects, hence its name, its a hierarchy of scene objects [smile]
I still dont see why including spatial relationships are necessary to call it a 'scene' graph though.

Quote:

The strongest logical relationship between chunks of geometry that requires a graph is spatial.

Well why would we want to use such a rigid relationship to build a flexible structure? [grin] Why should a scene-graph care how many pixels/units away object A is from object B? It ought to care more about how object A is related to object B.

Quote:

I think that a scene graph shouldn't even imply a parent-child relationship (other than spatial), ownership, or object lifetime.

A graph implies a hierarchy, so ownership and parent-child relationships can be expected, agreed object lifetimes arent necesarily obvious though a scene-graph could be used to manage this too.

Quote:

I see that Nairou's original question is about Yann's implementation. Without knowing the purpose of the scene graph, Its hard to say if there is a better way, just that a traversal over a spatial data structure and sorting aren't necessary at render time. I would consider scene level visibility determination a distinct step from rendering.

A scene-graph is a logical structure == what is in the scene and how does it relate to this or that?
A spatial structure can be used for visibility tests and culling, for spatial trees think BVHs, Octrees and BSPs.

As for Yanns scene-graph implementation we seem to be barking up the same tree ;-)
To quote Yann on scenegraphs (source):

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

Share this post


Link to post
Share on other sites
I didn't understand why scene graphs should not be built on spatial relationships (or at least contain them) at first, until I hit the big wall on the head. It was then that I started to question my motifs. IMHO, this is more about the practicality of the solution rather than how well those parts fit in theory. One big all-purpose tree is a solution biased so as to become beneficial for all parties. It doesn't necessarily demonstrate the best solution for each single one of those problems it's been designed for in the first place. Two nodes that are logically close together in a scene graph do not necessarily need to be close spatially. And there comes a point when you find yourself doing all kinds of hacks to stretch this ill wised all-purpose solution to cover all kinds of new problems from collision detection to render state management and such.

Although I'm not at that point myself, I remember reading a controversial article of Tom Forsyth "Scene Graphs - just say no!" which even took the reasonings further to completely discourage their use, although he hadn't discussed the alternatives. Any ideas?

Share this post


Link to post
Share on other sites
Sign in to follow this  

  • Advertisement
×

Important Information

By using GameDev.net, you agree to our community Guidelines, Terms of Use, and Privacy Policy.

We are the game development community.

Whether you are an indie, hobbyist, AAA developer, or just trying to learn, GameDev.net is the place for you to learn, share, and connect with the games industry. Learn more About Us or sign up!

Sign me up!