BSP Trees in Modern Game Engines

I first came across BSP when working with the Unreal Engine. We were working in UnrealEd and a level designer was demonstrating how they were using BSP Brushes to make rooms. I thought they looked like plain boxes. And, that’s really all they were until the compile button was pressed and the magic began. Then, those boxes were sliced, diced, lit, packaged, and ready to run.

Now, as I start planning out my level editor, I find myself thinking about those BSP trees. It has been a few years now, and I begin to wonder if they are the right structure to use in my level editor.

A Binary Space Partitioning (BSP) Tree is a structure that subdivides space into smaller sections or sets. It has been used in First Person Shooter (FPS) games to solve a problem with rendering polygons in the correct order. It would provide a method to traverse the structure and draw the polygons from back to front quickly.

But, the need to manually order triangles became less of an issue with the advent of the hardware accelerated Z-buffer. The polygons get pushed onto the GPU to be quickly sorted and processed for rendering.

That doesn't mean that BSP is obsolete. Spatial partitions, such as BSP, quad-tree, and octrees, are essential tools in modern rendering engines. They are used in visibility testing, network optimization, collision, and lighting. They can also be computed during compile time.

There are many discussions on which spatial partition is best. The truth is that they've all got their strengths and weaknesses. Once you've identified the characteristics of your engine, you'll be ready to identify which structure is best for you. But don't rule out the BSP Tree. They are well documented and still used today in modern engines. Especially for First Person Shooters.

Happy Coding!
Jason

Related Links:
http://www.gamedev.net/reference/programming/features/bsptree/bsp.pdf

http://en.wikipedia.org/wiki/Binary_space_partitioning