Drzewo BSP
Drzewo, które rekurencyjnie dzieli przestrzeń płaszczyznami i daje gwarantowaną kolejność głębokości przy rysowaniu — sztuczka, dzięki której działał Doom.
Binarny podział przestrzeni (BSP) tnie scenę płaszczyzną na półprzestrzeń przednią i tylną, a potem powtarza to rekurencyjnie, aż każdy liść zawiera wypukły fragment. Wprowadzili go Fuchs, Kedem i Naylor w 1980 roku. Zysk: z dowolnego punktu widzenia proste przejście po drzewie zwraca powierzchnie dokładnie w kolejności od najdalszej do najbliższej, co zasila algorytm malarza bez sortowania w każdej klatce.
John Carmack wyliczył drzewo BSP z góry dla Dooma (1993), by poziom dało się rysować poprawnie i szybko na procesorze 386. Współczesne GPU sortują głębię za pomocą z-bufora, więc BSP przetrwało głównie w zapytaniach o kolizje i w wyliczonej wcześniej widoczności.