Spatial Partitioning

Implementing Polygon level collision detection was fun and quite useful. I have implemented the system for static objects, dynamic objects, skinned characters and terrain. So even though collision detection is done it’s not ready for full game scene having 1 million polygons or more. The main reason is the performance if we use this system as it as for big levels without any High level optimizations we can’t get playable frame rates because CPU’s are still not powerful enough to do that and will never be. Because as the CPU or GPU horsepower increases people would demand larger and more realistic  looking worlds that means more polygons means more horsepower required to manage that. So we have to implement high level optimizations and we should try to rule out insignificant calculations as early as possible. Because check your character against all 1 million polygons or so every frame doesn’t make sense.

So next that’s where Spatial Partitioning comes into use. As name describes itself Spatial Partitioning algorithms divides the game level spatially into different areas or chunks depending on particular algorithm being used.  So every frame we can only test our character against objects / polygons in that particular area.

Not only collision detection same spatial partitioning algorithms can be used for speeding up rendering also. We have already divided space into smaller chunks / areas so sometimes we can get away only rendering that particular area. For example a scene consisting of 100 rooms and we are in room 50 then we just have to render that particular room and objects in it ignoring  all other rooms and objects in them. So that saves a lot of GPU power send in rendering other 99 rooms which user can’t even see (ignoring things like windows etc to make example simpler).

So this was an extreme example I gave but in many cases the amount of boost we get rendering and collision detection is comparable to example above.

Also I just gave you once example in the area of rendering deciding visibility or object but this can help in many other areas like LOD, Animation LOD and much more.

Hierarchical Partitioning

So by spatial partitioning we mean diving scene in cells (rows and columns etc) so we can just reject whole area / chunk of level at once from rendering or collision detection instead of going to each game object or polygon and checking if its visible or colliding.

Well this process can still be speeded up further much more by making the spatial partitioning hierarchical. So for example we can sometimes reject the 50% of the scene in single bounding volume check which is a major speed boost.

So here are some popular Hierarchical partitioning algorithms –

  • Quad Tree : A Quad Tree is a tree data structure in which each internal node has exactly four children. Quad Trees are most often used to partition a 2D / 3D space by recursively subdividing it into four quadrants or regions. The regions may be square or rectangular, or may have arbitrary shapes. But for games shapes are mostly square or sometimes rectangle. At each parent node 2 planes are chosen which mostly divides the node into 4 equal children.
  • Oct Tree : An Oct Treeis mostly same as Quad Tree with a difference that  each internal node has 8 children. Oct Trees are used in 3D environments. At each parent node 3 planes are chosen which mostly divides the node into 8 equal children. But there are other techniques also like Loose Oct Trees in which 8 children may/mayn’t be of equal size.
  • Axis Aligned BSP Trees or KD Trees : A k-d tree (short for k-dimensional tree) is a space-partitioning data structure for organizing points in a k-dimensional space. k-d trees are a useful data structure for several applications, such as searches involving a multidimensional search key. Even Quad Tree and Oct Tree can be thought of as k-d tree with 4 &  8 dimensions.  But in-game development k-d tree mostly means a special case of BSP or Binary Space partitioning Tree in which each internal node has only 2 children and plane used to split at any internal node is aligned to one of the Axes (X,Y or Z).
  • Polygon Aligned BSP Solid  Leaf Trees : Binary space partitioning is a generic process of recursively dividing a scene into two until the partitioning satisfies one or more requirements. At any internal node a plane aligned to one of the polygon is chosen to split other polygons at this level into back child and front child. At leaf Nodes polygons will only be present in front node and back nodes are mostly empty to represent what is called Solid Space or space where player can’t enter.  So we can easily render polygons in back to front or vice versa. Also there many occlusion culling techniques made possible by the BSP trees like Portals and PVS. All of this combined together is still the fastest way to render indoor scenes.

Another factor comes into play is whether we should clip objects / polygons or not along the boundaries of a Node. If we actually clip then polygon count will increase but 2 objects created as a result of clip along any plane will be owned by unique Nodes/ Leafs. But if we decide we don’t want to clip we either have to expand boundaries of Nodes (e.g. loose Oct Trees) or we have to include polygons in both children nodes in which case we have to implement something to avoid rendering same object more than once.

So at the time of writing this Quad Tree , Oct Tree and KD Tree were working and some foundation code for BSP is there but I most probably will be dropping it because right now I want to focus mostly on techniques that can be used in real-time and BSP takes a huge amount of pre processing time in construction of BSP Trees etc, also BSP are mostly much more useful for indoor environments or some outdoor environments with different sections that can be realized like indoor environments or areas (e.g. counterstrike or even half life2 itself).

So here are some screenshots and some statistics of what I achieved –

(Notice the number of triangles rendered in the 1st screenshot is only 8, which is made possible by spatial partitioning and hierarchical frustum culling)

Spatial partitioning is not the end but the beginning of algorithms or techniques that are used to manage / optimize the rendering /collision detection of large scenes. For example one next step is Hierarchical Frustum Culling and then occlusion culling etc.

For people who are interested to investigate it further here are some very good books on the subject –

RealTime Rendering

3D Game Engine Design

Realtime Collision Detection


About chetanjags

Game Developer

Posted on September 22, 2012, in Collision Detection, JustAnotherGameEngine and tagged , , , , , , , . Bookmark the permalink. 1 Comment.

  1. Nice article. I like the fact that even though you are not writing a tutorial you take the time to explain the concepts….it gets readers more interested..for example I have now downloaded all three books suggested by you xD

Leave a Reply

Fill in your details below or click an icon to log in: Logo

You are commenting using your account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

%d bloggers like this: