Sunday, April 14, 2013

QuadTree Partitioning

QuadTree-O-clock has arrived folks! After noticing performance drops as a result of Level 1 becoming bigger, I implemented QuadTree Partitioning to make sure that only part of the level is rendered and updated at any given time.

I made a dimension-based QuadTree, meaning I stop sub-dividing nodes that reach a minimum size. Other implementations can be capacity-based, meaning they stop sub-dividing when the number of elements in a node is below a certain threshold, but I chose the former because element density is pretty homogeneous across my level and is generally rather low; Also, I thought it would make level design more solid if I knew in advance the typical dimensions of the QuadTree nodes.

In addition, since I'm making a vertical shooter, I made the QuadTree only sub-divide in one dimension. Thus, this should really be called a BinaryTree! But the implementation is really just the same. I'm pretty happy with the result, below is a screenshot showing the partitioning in Level 1, notice the active nodes (in yellow):

BinaryTree Partitioning

Frustum Culling

Once the QuadTree is built, frustum culling is necessary to determine which nodes ought to be rendered and updated. I implemented a simple frustum/sphere intersection test, and is happy with the result.

I uploaded a video to showcase how this fits within my space shooter game. You can see QuadTree nodes lit-up in yellow as soon as their bounding-sphere intersects with the frustum. There are at most 3 active nodes at any given time, making this feature really worth it performance-wise.


  1. Interesting. If flying I'm only one direction you could maybe even do a simple distance check on the nodes relating to the far clipping plane of the frustum. A full frustum culling May not be needed. But I font know if your view is rotatable etc. If so then it's a no go.

    1. I just saw your message, no idea why I don't get notifications for comments. But funny I thought the same as you, until I wanted in-game cut-scenes where the camera might completely change perspective, that is why I went frustum culling.