Take the 2-minute tour ×
Game Development Stack Exchange is a question and answer site for professional and independent game developers. It's 100% free, no registration required.

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.

share|improve this question
    
Optimization can not be generalized very well, it all depends on your game requirements. There is no good or bad here, they all have strengths and weaknesses. Every game is different. –  Maik Semder Oct 30 '12 at 11:55
    
this isn't how you go about things, you should learn about what a scene graph is and then decide whether or not you need it or see whether professionals have used it in games similar to yours, right now you're asking somebody to picks shoes for you over a phone, it's counterproductive and ultimately pointless –  dreta Oct 30 '12 at 13:50
    
Space partitioning and scene graphs have different objectives, just look at relevant articles in wikipedia and it should be clear. –  GriffinHeart Oct 30 '12 at 22:22

3 Answers 3

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.).

share|improve this answer
    
Seems like I need to do more reading about graphs. and I also thought BVH was a graph not a partitioning structure. –  tapirath Oct 30 '12 at 12:50
2  
@tapirath BVH and partitioning structures are graphs. But they're not "scene graphs" in the sense that they don't represent the user-defined relationships between objects (neither spatial nor hierarchial), only their volumes in a way that parent volumes include all child volumes. –  snake5 Oct 30 '12 at 13:05

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.

share|improve this answer
1  
a scene graph is supposed to help set things up and manage your model hierarchies, whether you ALSO use it for optimization, that's a different matter –  dreta Oct 30 '12 at 11:48
    
There is no game yet. I'm trying to wrap my head around 3D concepts and graph/tree structures seemed like fun thing to learn. –  tapirath Oct 30 '12 at 12:14
    
@tapirath then asking about strength and weaknesses of each of them seems much more productive –  Maik Semder Oct 30 '12 at 12:19
1  
I thought that was what I did. Maybe I was not so clear.Think about it like a case study: For a game like Counter-Strike which one would you choose and why? –  tapirath Oct 30 '12 at 12:44
    
@tapirath, no this a different question, and not a very useful one, unless you actually find somebody who worked on it, the rest is just guessing –  Maik Semder Oct 30 '12 at 13:26

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.

share|improve this answer
    
"root of never winter nights 2" that's gold :) –  tapirath Nov 1 '12 at 8:01

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.