BSP trees(Fuchs et al, 1980)
in the class of "list-priority" visibility algorithms
returns an ordered list of polygons that can be drawn
Building a BSP tree out of polygons
one on top of the next, via scan conversion for example.
each node stores a plane, the polygon on that plane, and two child pointers,
for the positive & negative halfspaces.
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
Producing the ordered list from the tree
Building a tree from non-polygonal objects
classify viewpoint as being in the positive or negative halfspace of our
call that the "near" halfspace, and the associated child node the "near
draw the polygon on the plane
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.
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
overdraw: doesn't draw
preprocessing: this is preprocessing.
clipping: not done
transparent objects: doesn't draw