Sign in to follow this  

Scene graph and sorting question

Recommended Posts

i've been wondering this for quite a while now, there are many resources on scene graphs as well as sorting before rendering to minimize state changes but what bugs me is how these two work together, if you traverse your scene graph and just render the objects in the leafs/geometry nodes you end up with a pretty much arbitrary rendering order based on how you built your graph on the other hand when you sort objects by material, texture, camera distance etc. you won't be able to make use of your scene graph so how is it done then? do you sort objects to reduce state changes and instead of having a tree structure for your scene graph you have an actual graph where each node not only has children but also a pointer to its parent then when rendering you could travel the graph starting at the object to be rendered (or 'appearance' node) going up parent by parent store all the nodes up until the root in a list then iterate over the list back-to-front and for each node perform its function (transformation, etc.) that is the only possible way to utilize both i can come up with but it seems uh.. laborious you could further optimize that by not traveling up to the root but checking which nodes have been applied, looking for common parent nodes etc. but still is this how it's done then or is there some easy way i am completely overlooking

Share this post

Link to post
Share on other sites
ye but lets say my graph has a root with 3 nodes each one being a transformation node containing a rotation
each of those rotation nodes has a geometry node containing 1 model to be rendered

| | |
rotationA rotationB rotationC
| | |
modelA modelB modelC

for the sake of simplicity each model only uses 1 texture

modelA uses texture X
modelB uses texture Y
modelC uses texture X again

rendering the scene graph in pseudo code would look like this

render method of node {
set all of the nodes attributes (push matrix and rotate or bind texture, whtaever)
for each child {
call render method of child
remove previously set attributes again

while the render method of the model nodes would additionally render the models, so effectively binding the texture and feeding the geometry to the pipeline

now, if i just sort the models by texture and then render i will only bind each texture once instead of binding texture X twice but i still need to get the rotation in somehow so before rendering modelA i would have to perform the rotation of the rotationA node (and to do that i would have to look at the model node's parent node)

what if before the rotation i would also have to do a translation? i would have to do the translation first and then the rotation and then render the model

so that's what i meant by traveling "up" the graph and storing the nodes in a list in order to "set" them in reverse list order..

and i wonder if this is the way that's done done.. you reduce state changes but depending on how "smart" you do that you increase the number of matrix multiplications and have to do a lot of graph traversal done before the actual rendering

Share this post

Link to post
Share on other sites
What I do is store transformations in transformation nodes, which consists of an object space transformation and a ("final") world space matrix. When a node is created, the scenegraph is searched from that node up to the root or until a transformation node is encountered, and a pointer to the world space matrix in the transformation node is stored in the node. When a transformation node is modified, I multiply/update all transformation nodes' world space matrices in its subtree. That way, I only need to compute transformations when the actual transformation occurs and all nodes have a pointer to their final world space transformation. This also lets me share matrices across many objects (if they use the same transformations) because the nodes only have a pointer to a matrix, not an actual matrix (4 bytes vs 64 bytes!).

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