richter

binary space partitioning in Quake maps

Quake was the first video game to utitlize 3-D binary space partitioning trees (Doom used 2-D BSPs with heightmaps). This data structure allowed Quake to run at acceptable speeds on the relatively slow CPUs of the time (Intel's fastest desktop processor in 1996 was a 200 MHz Pentium).

theory

Binary space partitioning is a technique used to divide a large, complex space into small, simple spaces such that neighboring objects can be easily located. This simplifies important operations in the engine:

In 3-dimensional space, binary space partitioning is performed by recursively partitioning a space in half by a 2-dimensional plane. This operation is repeated on each produced subspace until all of the spaces have been reduced to the desired size or complexity.

This algorithm generate a BSP tree, a binary tree whose nodes represent the subspace generated by each successive partition. Each node contains the plane used to divide its children, and the leaves contain information about the subspaces they describe.

Traversing the BSP tree is then as simple as comparing a point to a plane and selecting a child based on which side of the plane it appears, recursing until a leaf is reached.