# 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:

**Visibility**: without a BSP tree, there is no easy way to tell which parts of the level
geometry are visible from a given point. For Quake's software renderer, which lacks a depth
buffer, this would result in unacceptable performance hits from drawing every surface in the
level.
**Collision detection**: the BSP tree allows for easy collision detection due to the small
number of surfaces in a leaf node, whereas the entire tree may have up to
65535
faces.
**Hit detection**: Similar to collision detection, both hitscan shots and projectiles like
nails and rockets are much easier to process when the number of candidate hitboxes is
small.

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.