Scene graphs and spatial partitioning structures: What do you really need?

Question

I've been fiddling with 2D games for awhile and I'm trying to go into 3D game development. I thought I should get my basics right first.

From what I read scene graphs hold your game objects/entities and their relation to each other like 'a tire' would be the child of 'a vehicle'. It's mainly used for frustum/occlusion culling and minimizing the collision checks between the objects.

Spatial partitioning structures on the other hand are used to divide a big game object (like the map) to smaller parts so that you can gain performance by only drawing the relevant polygons and again minimizing the collision checks to those polygons only. Also a spatial partitioning data structure can be used as a node in a scene graph.

But... I've been reading about both subjects and I've seen a lot of "scene graphs are useless" and "BSP performance gain is irrelevant with modern hardware" kind of articles.

Also some of the game engines I've checked like gameplay3d and jmonkeyengine are only using a scene graph (That also may be because they don't want to limit the developers). Whereas games like Quake and Half-Life only use spatial partitioning.

I'm aware that the usage of these structures very much depend on the type of the game you're developing so for the sake of clarity let's assume the game is a FPS like Counter-Strike with some better outdoor environment capabilities (like a terrain).

The obvious question is which one is needed and why (considering the modern hardware capabilities).

Thank you.

Answer 1

It's mainly used for frustum/occlusion culling and minimizing the collision checks between the objects.

Not true. It's mainly used for programming convenience and hierarchial animation. There is no way culling and collision checks benefit from scene graphs. Quite the opposite, actually, since it's required to calculate and cache the world space data before doing everything else. Bounding volume hierarchies are what you need for culling and collisions, if anything.

I've seen a lot of "scene graphs are useless" and "BSP performance gain is irrelevant with modern hardware"

Both are true for simple games, false otherwise. BSP or any other spatial partitioning / bounding volume hierarchy (both are almost the same) system can significantly reduce the time it takes to process things. As for scene graphs, once you want a character that has all kinds of things attached to it or at least, relative object positions in world (light attached to a moving lamp, for example), you'll see that they become useful. Only as far as rendering is concerned, though - physics always has a somewhat flat "scene graph" (sometimes even cyclic, so the DAG (tree) structure of a scene graph isn't useful).

let's assume the game is a FPS like Counter-Strike with some better outdoor environment capabilities

I'd say you need all of them here, and some more. Bounding volume hierarchy (like BSP or octree), perhaps portal culling too for the static parts of the world, occluder volumes (antiportals in Unreal Engine) for terrains and a scene graph for compound objects (lamps, characters, doors etc.).

Answer 2

Neither is needed.

The choice of scene graphs or spatial partitioning or both is a matter of optimisation. And until you have a functioning game, you have nothing to optimise. So obsessing over this sort of detail now is counter-productive to the creation of your game.

My advice: make the game, then measure which bits of it are slow, and finally fix the slow bits. If you start by trying to guess what's going to be slow and obsessing over doing everything in the "right" or the "best" or the "fastest" way before actually having made the game, then you'll never finish.

Answer 3

I tend to disagree with Trevor Powell's answer as there are clearly two different kinds of optimization here. One is optimization after the fact and to make the slow parts go fast, which is what he has touched on, but the other is designing your data structures and flow control to be at least reasonably efficient and sensible in the first place.

The second is the type solved by any spatial partitioning scheme, and if you try to retrofit that on a design that's not built around it, you'll likely make a huge mess and risk ending up even slower.

Premature optimization may be the root of all evil (but don't forget the crucial 3% that Knuth also mentioned) but not optimizing at all is the root of Neverwinter Nights 2.