Communication between two heirarchies

Newbie & Debugging Questions
#1

Hi all,
I have a heirarchy of nodes where a leaf is a geometrical representation (opengl, so thats vertices, normals, indices…etc); each node/leaf has a container that is used for frustum culling…and that works fine. Lets call any node/leaf in this heirarchy a “spatial”. Another heirarchy is my render state heirarchy; each node in this heirarchy represents a state change and each node also contains a list of spatials that are associated with that render state.

The problem is mixing the two. I want to do frustum culling on the first heirarchy, and the ones that are culled to not appear in the second. Then, traverse the render state tree and enable state -> render spatials -> recurse for all child render states -> disable state. This may seem simple, but there are a few restrictions.

a) I cant have a boolean in spatial representing whether the spatial has been culled or not as I can insanatiate alot of small renderers everywhere and they have their own culling mechanism and those renderes are mulithreaded.

b) I can’t keep a reference to the render state that the spatial is attached to because it could be attached to multiple render states for multiple pass rnedering and for the multiple rendering mechanism.

With that in mind, anyone have any ideas on how I can communicate the results of the frustum culling with the second heirarchy ?

DP :slight_smile:

#2

Anybody ?

#3

A hash table or something similar?

#4

Add “named” render state references to the spatial (using a map or fixed array-index lookup) and pass that “name” to the spatial tree traversal

#5

Thanks for your replies…

Unfortunetly, a hashmap is too slow as this algorithm is done per frame…a hashlookup per frame per object is just too much.

cylab, what do you mean by a “named render state reference” ?

#6

I think he means named as in some identifier of choice, for instance an integer. Each renderer could have it’s own private state object in each spatial. So during the culling traversal each renderer stores it’s required data in the spatial and reads it back during the rendering pass.
At least that’s how I interpreted it :slight_smile:

#7

interesting that they claim over here that collections are hardly ever a bottleneck.

a hashmap is too slow as this algorithm is done per frame… get map implementation that doesn’t suffer from this?

#8

An ArrayList/LinkedList are different from maps. Maps have an O(log n) performance time per get. Now imagine a large scene with alot of shapes…the algorithm/design is going to be putting and removing from the this map every frame in the render state heirarchy.

Implementing another Map is going to be just too much hassle for what this is supposed to be. And most probably, i can’t do much better than O(log n)…

Regarding the identifier business; storing any information regarding culling status is really not feasible. The API supports small renderers everywhere, for example, each Light has a renderer for depth rendering for shape maps, storing a reference to each of those breaks encapsulation of data.

What I was thinking was maybe traversing the render state tree, obtaining the children in the current render state. Then recursively find its parent until you get to the base node. From there, do frustum culling, then somehow mask the ones that aren’t to be rendered in the render state heirarchy…

DP

#9

(having actually given some tauth)

I would do the culling differendly in the sence that I would mark that which should be painted not what shouldn’t. since the positive result is a tree and the negative result is an collection of fallen off branches. (this hold true wenn if we marked the parent as culled the childs are implicated to be too.) since it would be a collection of references it shouldn’t be cost and creating one could be parallel.

not sure how your render structure is set up (as in value of the nodes)

#10

If I understand your problem right, you can’t reference the render state from the spatial because there could be more than one render state corresponding to a spatial node (multiple views/renderers/passes), so my suggestion was to just hold multiple references to all render states.

This references have to be “named” to find the right render state to update on culling (or other traversals). There are multiple ways to to this. One is using a map and another would be to use an array. Since there won’t be much renderers, every node can use a fixed size array (e.g. size of 4) to store the render state references. the fastest way to resolve the right reference would be to use an integer as “name” and use this “name” as array-index to find the right render state corresponding to the spatial node.

#11

Mr_Light: The current system culls away the non-visible stuff leaving a flat, list like structure called a RenderBin. In a RenderBin, it contains leaf nodes (Shapes), those shapes can then be sorted in a specific manner, for example, to get correct transperancy, you need to sort back to front. Even if I kept the tree intact; it would be in the manner that the user set it up (for example, octree) and not in the RenderState tree…

cylab: Typically speaking, each renderer would have its own render state tree. The way I have implemented it so far (not fully, as this problem is annoying me) is that you have a singleton stack on which you can push and pop root render state. The top most render state tree gets rendered. What this allows is for a Light to push its own agenda on the render state stack, render, pop back to the original render state that the user created (think shadows and post process effects, even deferred shading). So if there are 100 lights through out the scene, there could be a potential 100 renderers…

But i feel uncomfortable introducing any sort of reference inside spatial as this, in my mind, breaks encapsulation…The Shape shouldn’t know what it looks like in terms of textures, lights, any shaders. What it does know about is a bound, a transform and a potential Geometry encapsulation.

So I guess the question has changed to “How can I combine a a tree that contains a set of spatials with another tree that has a portion of that set ?”

DP

#12

I am afraid you can’t without recreating the render trees every frame. You could do some fancy statistical caching to avoid full recreation (of the tree… not yourself ;)), but that’s it (IMHO).

#13

[quote=“darkprophet,post:11,topic:28503”]
I don’t think that necessarily breaks encapsulation. The spatial nodes don’t need to know anything about the render state itself. It can be completely opaque. In the end you’re still going to need to make some sort of relationship between the render state and the spatial. Maybe an alternative would be to have a dedicated render state tree. This would have same structure as the spatial tree, but now each node would contain a reference to a spatial and collection of associated render states…

#14

After much thought, I dont see how that inbetween tree would help. The idea behind the render state tree is that I can traverse the render state tree and render whats inside each node in that render state tree; thus saving state changes.

The “inbetween tree” wouldn’t allow me to minimise state changes…which is what this was about.

If I could bring myself to break the encapsulation; I’ll add a List to Shape; when traversing, if the Spatial is frustum culled, it would remove itself from the List inside RenderState, thus when rendering the state tree, it wouldn’t be there. But I would have to live with the memory increase in Spatial (as opposed to just Shape, which is a leaf node) if I was to implement a more classic Appearance class that Shape would encapsulate…

Anyways, thanks for all your answers; I was hoping for an elegant solution, but there doesn’t seem to be one.

PD

#15

I think I’m messing up some terminology here :slight_smile:
The idea I had was to make three distinct trees:

  • a tree of render states
  • a tree of spatials
  • a tree connecting the two (call it foobar for clarity ;))

Instead of making references from render states to spatial (as you initially described), you would make references to foobar nodes. The foobar tree nodes would contain any renderer specific information (such as ‘isCulled’). Then you perform a cull pass on the foobar tree, storing any required information in the nodes. After that you render using the render state tree. So basically it adds an extra level of indirection and pulls the render info (isCulled, …) out of the spatial nodes without losing the optimized rendering. The tradeoff is memory usage and the extra indirection.

#16

You will run in trouble anyway, since this approach cannot cull whole subtrees without traversing them to remove all spatials from the render tree. I think you will be better of to generate a render list from a spatial tree and sort them to minimize state changes.

#17

@cylab: Im already state sorting after traversal and doing it in such a way that the sorting is O(1) :stuck_out_tongue:

There were other reasons for introducing the render state tree, primarily so that a few fixed render states can be used to render the entire scene (think post process effects here, or even shadows). A simple tree push, render the entire scene with the pushed render state tree, then pop to get back to the original state that the user has set the scene up is what I was aiming for. And doing it in such a way that is completely transperant to the user. Forcing a renderState through a static class might be a way to do that but isn’t as elegant/original to me as the renderstate tree idea…

@pepijnve; good idea, but creating another tree that has a similar memory requirements as the spatial tree is just too much. Also like cylab mentioned, partial traversal can’t be done using my method and it can’t be done using yours. And frustum checking all those extra spatials is probably more expensive than a few render state changes…