BSP trees(Fuchs et al, 1980)

in the class of "list-priority" visibility algorithms Building a BSP tree out of polygons
  1. split along the plane of any polygon
  2. classify all polygons into positive & negative halfspaces of the plane

  3. * if a polygon is on the plane, split it in half
  4. recurse down the positive halfspace
  5. 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)

Building a tree from non-polygonal objects
choose arbitrary split planes:
  1. if only one object left, we're done.
  2. split along any plane, preferably one that divides the objects well
  3. classify all polygons into positive & negative halfspaces
  4. if any objects intersect the plane, split them in half (difficult!)
  5. recurse down the two children.

each node stores a plane and two child pointers
    no object on the plane

use: Quake. raycasting. shadow casting.
worst-case space complexity: O(n2)
worst-case time complexity: O(n3)
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