"A Study in Realtime Rendering using BSP-Trees"
Matt Sykes 2005
Abstract
Originally, created for sorting polygons in a virtual world, binary space partitioning (BSP) is now used in a variety of applications in 3D gaming engines. By making a large number of computations in a preprocessing stage, BSP trees provide a mechanism that sorts polygons in no longer than linear time. This project investigates the topic of BSP trees from its inception in the 1980's.
A number of topics and algorithms related to BSP trees are discussed. Hidden surface removal and the use of bounding volumes are discussed in detail. In addition, a program written in C++ using OpenGL and the GLUT API implements a working example of BSP trees.