I'm just popping in, I'll have to be brief I'm affraid...

Quote:Original post by Jason Z
<snip>
Is this a correct understanding?

Yes it's correct, I only meant that before you were comparing a BVH integrated with a scenegraph with a quadtree not integrated in the scenegraph so it wasn't really a fair comparison.

Quote:The more that I think about this issue, I can understand how having a separate spatial structure would be useful in particular cases. However, I have to mention that culling is more or less a O(n) operation if done by brute force. If the only reason that you build a separate spatial hierarchy is for culling, then you will only get marginal gains in performance if you consider the maintenance time on the datastructure.

I suppose it depends on how you implement the system, if you design cleverly the synchornisation between structures shouldn't be too much trouble. If something changes it's logical relationship then the scenegraph changes, if it changes spatially then the spatial tree changes. If they're both one tree then you need to make sure you don't break the spatial or logical relationship when the other one changes.

Quote:Where the separate spatial hierarchy is more useful is in collision detection, which by a brute force method is a O(n*n) operation. The spatial structure would speed the collision detection by whole orders of magnitude, and could be used for culling more or less for free.

A spatial structure built for visibility culling isn't necessarily good at collision detection - especially true for static geometry when batches are big.

Quote:With this in mind though - if you are using a physics API for collision detection, then I don't think it makes sense to build a separate BVH in addition to the scene graph. It would make more sense to use the physics API with a collision detection pass (i.e. create a temporary physics object in the shape and orientation of the view frustum and use that to determine visibility). This basically uses the physics API BVH, relieving you from having to maintain it. Its more or less duplicate CPU work if you do it on your own, and the physics API is probably going to be more reliable than a home-brewed one anyways. Does anyone have any opinions on this???

I suppose it depends on the physics package you use. If it's a 3rd party library then I'd probably use whatever structure they have in place.

Quote:

Quote:Original post by Avi Bar-Zeev
One idea I'd like to inject is on state sorting, since people seem to focus on BVH, transform hierarchies and other obvious wins for using trees. The win with using a state graphs is: the state graph topology doesn't generally change from frame to frame. No state sorting is required, as the graph itself can represent the optimal draw order (per platform) as if everything were visible.

That is an interesting idea, and I actually hadn't considered it before you said it. Our previous discussions seem to have focused on the need to remove rendering state from the generic scene graph, but we hadn't really talked about how best to organize it outside of that scene graph (i.e. which data structure would work best).

I have always just obtained the list of objects and then performed a sorting procedure based on textures, shaders, and object type. Typically I just insert the objects into a heap and then do a heap-sort removal of the nodes to select the rendering order. It would be interesting to see how other structures/algorithms would help speed things up.

One idea is to use a list/array and insert renderables into there. Then you sort them based on render-target, shader and shader-states (the shader would be the best candidate to sort its own states, perhaps with a callback function).
When it comes to the next frame you add or remove renderables that have entered or exited the frustum. The trick is that the previous frame's renderables are all still kept sorted so now you just use an algorithm that benefits from a nearly sorted data set, like a natural merge sort. If you find that the scene did for some reason drastically change from one frame to the next (start of a cut scene for example) then you can optionally ditch the natual merge sort and dynamically swap to an O(1) sort like a radix sort.
What you have overall is a nearly O(1) sort on all renderables that entered a frame's view, renderables still visible from the previous frame weren't necesarily touched.

Quote:Original post by cyansoft

Quote:Original post by Jason Z
Also, I found the wiki link on scene graphs. It basically draws the same conclusions that we have already, but I'll link it for general interest.

The above link is to an article on octrees, which is a space partitioning tree, not a scene graph. The article on scene graphs is here.

What's the general oppinion on that article by the way?

Quote:I agree that a component based design would a) keep things more simplistic by reducing class bloat, and b) make things more flexible as custom components can be tailored to handle rendering, space partitioning, occlusion, collisions, physics, 3d sound, AI / pathfinding, etc.

As do I.

Quote:Original post by cyansoft

Quote:Original post by dmatter
What's the general oppinion on that article by the way?

I think the article is very vague. It even admits that there really isn't a standard definition of what a scenegraph is other than being a data structure to store a scene in a 3d graphics application or vector based drawing application.

To a certain extent its deliberately written in a vague way, as just an overview of what scenegraphs were/are often like (catering for several different applications however, not just 3D graphics) but with little implementation details or specifics.
I wrote the majority of that article a couple of years back (of-course it's an open wiki so changes have been made and there is some original text retained too); the intention was that with a better (and it was awful originally) basis of an article on wikipedia then other people could add their own specifics in and new ideas would lead to better ideas etc etc.. and we'd come out with the ideological scenegraph design. It hasn't really worked out that way but never mind, GDNet does do a very good job none the less [smile]