BSP trees(Fuchs et al, 1980)
in the class of "listpriority" visibility algorithms
returns an ordered list of polygons that can be drawn
one on top of the next, via scan conversion for example.
Building a BSP tree out of polygons

split along the plane of any polygon

classify all polygons into positive & negative halfspaces of the plane
* if a polygon is on the plane, split it in half

recurse down the positive halfspace

recurse down the negative halfspace
each node stores a plane, the polygon on that plane, and two child pointers,
for the positive & negative halfspaces.
Producing the ordered list from the tree
node::draw (viewpoint)

classify viewpoint as being in the positive or negative halfspace of our
plane
call that the "near" halfspace, and the associated child node the "near
child"

farchild>draw (viewpoint)

draw the polygon on the plane

nearchild>draw (viewpoint)
Building a tree from nonpolygonal objects
choose arbitrary split planes:

if only one object left, we're done.

split along any plane, preferably one that divides the objects well

classify all polygons into positive & negative halfspaces

if any objects intersect the plane, split them in half (difficult!)

recurse down the two children.
each node stores a plane and two child pointers
no object on the plane
use: Quake. raycasting. shadow casting.
worstcase space complexity: O(n^{2})
worstcase time complexity: O(n^{3})
query time complexity: O(n)
coherence: object, world
scene footprint: total
memory footprint: an individual BSP node and its associated
object
overdraw: doesn't draw
preprocessing: this is preprocessing.
clipping: not done
transparent objects: doesn't draw