Introduction

Binary space partition trees (bsp trees) are very useful for people who work with 2D and 3D computer graphics. This collection of web pages will explain about bsp trees from a game programmers perspective, even though there are other perspectives, such as that of people who work in the field of computational geometry. Game programmers are interested in bsp trees because they can be used to help draw scenes of games very quickly, such as the scene shown in this screenshot of the game Doom.

This is a screen shot from Doom. Doom is a game which was created in 1993 by id Software. It is still popular!

A bsp tree works by dividing up and organizing the parts of a game scene and then sorting the parts of the scene into a useful form from which information about how the parts relate to each other can be quickly accessed. This web site attempts to demystify bsp trees and will also discuss two related graphics algorithms, namely the depth-sort algorithm and the painter's algorithm.

If you have any comments, questions or corrections regarding this site, please email either Gail or Michiko.