I'm trying to figure out a way to make my scene graph in an efficient manner but I'm kind of stuck..

Basically the thing is that my engine basically lets users create hex tile maps in an editor where they can select a bunch of them and move them around as they please - the map can potentially contain as many hex tiles as the user wants to add - the pic illustrates

my question is - how the heck should I organize my scene graph so that in the editor I can have collision detection and such - right now they are each in a grid space that uses modulo division from their center point position to determine which grid space to put them in.. each grid space has a list of object references that currently occupy that space -

so basically I have one base grass hex tile object which has a RenderComponent that contains the mesh data and a vector of matrix transforms for each instance that is in the scene, The render manager then calls draw on just the one grass hex tile passing in the instance data...

The hard part is building the instance data - when there are a lot of tiles on the screen, updating this vector of matrices can be expensive if I do it every frame, right now I only rebuild the vector if a tile is added or deleted - if one is moved I modify the transform directly with the reference (each ObjectReference has a reference to its transform contained in the base object's RenderComponent transform vector.. sounds complicated I know) ...

This all seems like some kind of hack or workaround, It seems like there has got to be a better way to organize these hex tiles - collisions, for example, go through each object with a collision component and check to see if the grid spaces immediately surrounding that object contain objects that also have a collision component - if they do collision is checked... This seems clunky to me and unorganized - but I can't think of a better way to do this

If anyone has some idea on how I should organize my scene - please let me know - I am okay with completely trashing the structure I have now and rebuilding it

how the heck should I organize my scene graph

Every time a scene graph is used for more than a hierarchical representation of a game world an angel loses its wings.

Perhaps some of your confusion is caused by believing in the first place that a scene graph is somehow related to this problem.

In a normal rendering pipeline (notice how I will never be mentioning the words “scene graph” again) you run over the non-culled objects, allow them to submit a render request for each submesh that needs to be rendered, those are sorted in a render queue to reduce state changes, and each object is then rendered.

The purpose of the render queue is to reduce state changes and includes information on which shader to use, as well as which textures and optionally the ID’s of the vertex buffer and index buffer.

These things can be used to determine that objects are similar enough for instancing automatically. The instancing setup can be done automatically and the render call issued to the first object in the list.

L. Spiro

Thanks for the reply!

So then do you think something like this would work -

For each node in the scene graph (which has been determined to be non culled) submit the render request for the sub-meshes that need to be drawn to the render manager which adds the necessary info to the render queue - I mean I know you said the scene graph has nothing to do with it but where do you get the list of non-culled objects?

To determine whether to draw a sub-mesh with an instanced draw call - would this work?

When the rendering manager is going through the render queue - if a sub-mesh's data is determined to be the same as another sub-mesh's data (material, vertex/index buffers) in the queue then make it so that sub-mesh is rendered as an instance of the first sub-mesh

Here's another question - That doesn't necessarily have to do with the previous one

Does this seem like a logical structure?

First go through the scene graph and have each visible object in the scene submit the request to be rendered

Then go through the render queue and sort it to reduce state changes - IE do as few shader, texture, and whatever else I may be forgetting switches as possible

Then do the draw calls for each object in the queue

Or should the "Render Manager" be sorting the queue as submission requests are being made?

And should the engine be doing this once every time through the game loop (if the frame rate is 60 fps then do this 60 times per second)? (since the scene graph culling changes as the camera changes)

We need to be clear on exactly what a scene graph is and does.

A scene graph is nothing but a hierarchical representation of the scene such that objects can be children of other objects and inherit their parents’ transforms. A knife in the hand of a character moves with the hand because it is a child of the hand’s joint.

That’s all it is an does. Nothing related to graphics or rendering, etc. It is not something you traverse for rendering. It allows you to determine an object’s world position to create the matrices that will later be used for rendering, but traversing it is inherently slow due to recursion and leaves open the possibility of stack overflow as well, and should be done as infrequently as possible.

where do you get the list of non-culled objects?

The most straight-forward way is to simply run over the master list of objects in your scene, which should be a simple linear array.

Otherwise it depends on what type of acceleration structure you have in place. If it is an octree, for example, you will find objects inside each node of the tree.

To determine whether to draw a sub-mesh with an instanced draw call - would this work?

Yes.

Does this seem like a logical structure?

Except the part where you “go through the scene graph”.

And should the engine be doing this once every time through the game loop

Yes.

L. Spiro

okay I think I was confusing the "scene graph" term with the structure used as the master list of objects in the scene...

last set of questions I promise - and thanks for taking the time to answer all these questions

Do you use the scene graph only when updating the positions of the objects in the scene then? So - like, if an object is moved (lets say when the key "w" is pressed a character object should move towards the z direction) the scene graph would just be used to move the character towards the z direction, then recursively move each of the character's child objects forward in the z direction?

And when I am doing collisions, should I be using that same master list of objects in the scene as I use to send render requests (not the scene graph) ?

Or should I be using a different object list? Because I was thinking about implementing an octree for the master list so I can implement frustum culling easier, so that when i'm traversing the octree i can just skip whole sections that are not within the frustum, but when doing collisions it seems like you cant just skip objects that are not within the frustum... Would it be normal to just use the same octree but do another traversal of it just for collisions (not culling out entire sections)?

thanks again for your responses!

Do you use the scene graph only when updating the positions of the objects in the scene then?

Yes.

When an object moves it sets a dirty flag on all of its children recursively at a fixed point in the pipeline all dirty objects are told to redetermine their new orientations.

And when I am doing collisions, should I be using that same master list of objects in the scene as I use to send render requests (not the scene graph) ?

If that structure is suitable for collision detection, yes, if not, no. An octree would be suitable for both.

L. Spiro