I wrote this article to introduce myself to BSP (Binary Space Partition) trees. It’s a beginner’s overview, up to the more advanced math concepts. It’s not complete, but it should help you out, should you need to learn about them.

Abstract

While listening to discussions on how Quake and DOOM work, while reading Michael Abrash’s columns in DDJ or even while browsing the released source to Wolfenstein, you’ve probably come across discussions about an algorithm that seems to be able to do amazing things: BSP-trees.

What is a BSP-tree? Well, the acronym “BSP” stands for “Binary Space Partition”. So, you may then ask, “What exactly is a binary space?” and “How the heck do we partition it?” We’ll get to all of that eventually. The concept of a BSP-tree is fairly complex to visualize if you don’t understand it, however, so I urge you not to go on before you’ve finished comprehending the earlier sections.

Download: bsp.txt