Árbol BSP
Un árbol que divide el espacio de forma recursiva con planos, dando un orden de profundidad garantizado para dibujar — el truco que hizo correr a Doom.
La partición binaria del espacio corta una escena con un plano en un semiespacio delantero y uno trasero, y recurre hasta que cada hoja alberga un fragmento convexo. La introdujeron Fuchs, Kedem y Naylor en 1980. La recompensa: desde cualquier punto de vista el árbol entrega las superficies en orden exacto de atrás hacia delante mediante un recorrido sencillo, alimentando al algoritmo del pintor sin ordenar en cada fotograma.
John Carmack precalculó un árbol BSP para Doom (1993) para que un nivel pudiera dibujarse de forma correcta y rápida en un 386. Las GPU modernas ordenan la profundidad con el búfer Z, así que el BSP sobrevive hoy sobre todo para consultas de colisión y visibilidad precalculada.