In [[3D computer graphics]], '''Binarybinary space partitioning''', also referred to as '''BSP''', is the method of preprocessing of a [[scene (computer graphics)|scene]] to enhance the subsequent processing of the scene (its rendering, search, etc.). The method basically consists in a recursive subdivision of the scene into [[convex set]]s by [[hyperplane]]s. This subdivision gives rise to a representation of the scene by means of a [[tree data structure]] known as a '''BSP tree'''. Among the applications are [[computer rendering]] and performing geometrical operations with shapes ([[constructive solid geometry]]).
==Overview==
In [[computer graphics]] it's desirable that the drawing of a scene be both correct and quick. A simple way to draw a scene correctly is the [[painter's algorithm]]: draw it from back to front painting the background over with each closer object. However, that approach is quite limited since time is wasted drawing objects that will be overdrawn later, and not all objects will be drawn correctly.
[[Z-buffering]] can ensure that scenes are drawn correctly and eliminate the ordering step of the painter's algorithm, but it is expensive in terms of memory used. BSP trees will split up objects so that the painter's algorithm will draw them correctly without need of a Z-buffer and eliminate the need to sort the objects as simply walking the tree will yeld them in the correct order. It also serves as base for other algorithms, such as visibility lists, which seek to reduce overdraw.
