BSP trees(Fuchs et al, 1980)
in the class of "list-priority" 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 non-polygonal 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.
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