What's the state of the art in Space Partitioning for games? [closed]

Question

I know about BSP trees, Octrees and Portal that where used for a long time. But modern games still use this systems or they are using new things?

If it's possible with pros and cons, considering rendering and collision detection.

Answer 1

Yes, the Unreal engine 3 for instance still uses a BSP -- mainly because it's used during the CSG process. Doom3/id tech 4 uses portals, and I think I've read something that id Tech 5 is back to BSP trees. There are some games which use octrees, too. In game, my understanding is that UE3 moved to a more dynamic approach with occlusion queries, but I would be surprised if they don't use the BSP to at least determine which static meshes are in sight. Other games might just use view-frustum culling (Civilization for instance.) It really depends on what type of game you look.

The reason that BSPs and stuff is still around is because you can't do much better. If you have static geometry, a BSP is great if you construct it right. It requires you to write a BSP builder though, which is tricky (but it might happen for free if your CSG solution uses one!) Octrees and more dynamic solutions (like relying on occlusion queries for everything) are simpler to implement, have higher runtime cost but don't require (expensive) pre-processing of the levels. That's a trade-off that some games are willing to do (Crytek for instance wants everything to run in real-time, so they don't spend processing time to build a static acceleration structure.) Other runtime approaches are for instance software rasterization on the CPU and performing occlusion queries on the CPU (this is used by the Frostbite engine.)

For a really modern approach, look at Umbra, which is a middleware for visibility queries. If you search the web a bit, you should find some of the master thesis which describe the early beginnings of Umbra.

Bottom line: Whether you want to use a BSP/Octree/no AS will highly depend on the type of game you want to create. If your levels are mostly static, you should take advantage of that and build some static acceleration structure. If everything is dynamic, you need of course another approach.

For collision detection, I would take a look at Bullet and PhysX and their collision detection algorithms. But my feeling is that the physics solutions are less tied to the visibility than they used to be -- a physics solution might want to use a GPU based BVH, in that case, there's not much sense to try to use that for visibility queries.

Answer 2

I honestly don't know what next-gen engines are using these days, but I will tell you what I do know. It's easy to get confused between an optimization and the data structure used to assist in that optimization. All of the things mentioned below are for optimizations though, but I'll point out which ones are data structures specifically.

BSP: Data Structure - For detecting intersection between a dynamic moving objects and static world geometry. Used to be used for both collision detection and rendering of geometry correctly without a zbuffer, but it is no longer used for rendering anymore since we have enough memory for a z buffer now days. They're technically generated slightly differently though but still considered the same tree type. Requires preprocessing.

Octree or Kd-Tree: Data Structure - used for determining what objects are in the same "cell" or area to avoid doing an n^2 check on all dynamic objects.

These aren't the only ones, but are probably the most common. There are also a lot of optimizations that allow the engine to avoid rendering geometry in general. But the following just cull out the geometry, and that's usually all it's used for:

Portals: Not technically a data structure, but requires a special one to do culling. Used for visibility culling of world geometry and dynamic object geometry from view. Requires preprocessing to divide the world into areas I think. But I haven't actually implemented this, so I don't know.

Occlusion culling: Optimization - used for visibility culling for whatever you want, probably dynamic objects.

Regular Viewport culling: Optimization - culls objects that aren't in the camera's view.

More viewport culling: Optimization - Regular viewport culling can be optimized even further by using an octree. You can cull out entire cells of the octree that are behind the camera or not in its view. This includes patches of terrain (if you're outside). Whatever isn't culled by the octree you would perform "regular viewport culling". Then, whatever is left, you would render.

Backface culling: Optimization - culls geometry facing away from the camera to prevent rasterization. Usually done in hardware if the render state is set properly.

Special case data structures:

AABB trees or Sphere trees: These are kind of special case data structures. They turn a concave shape into a convex one. For example a character with bones is technically concave. It breaks it up into smaller convex pieces. Can be used as an optimization for collision detection, visibility culling of dynamic objects (usually), and makes it easier to do intersection tests against since it's convex. These would go inside of say, an octree since they're usually dynamic objects. These could also be used to assist with the occlusion culling optimization.

There is no reason why you have to use a single structure to represent everything (such as a scene graph). In my opinion, you would be better to use different data structures for different tasks instead of attempting to use one general purpose tree of some sort. For example, the engine I'm working on presently, I plan to implement a BSP/Octree/AABB Tree combination with the following optimizations: occlusion culling, viewport, &, of course, backface culling. This means I'll have one bsp tree, one octree, and probably multiple aabb trees within that octree.

The selection of the best data structures and algorithms/optimizations is probably the single largest and most beneficial thing you can do for your engine.