The Algorithms
Image-space algorithms
-
Traditional Scan Conversion and Z-buffering
-
Hierarchical Scan Conversion and Z-buffering
input: any plane-sweepable/plane-boundable objects
preprocessing: none
output: a discrete image of the exact visible set
Classic object-space algorithms
-
Volume testing, The First One
input: convex polygons + infinite eye pt
output: visible portions of wireframe edges
-
BSP Trees
input: plane-testable and splittable objects
output: a back-to-front ordered list of objects
-
Painter's Algorithm
input: a correct back-to-front ordered list of objects
output: usually a discrete image
all of these compute the exact visible set
Conservative Visibility Algorithms
-
Viewport clipping
-
Back-face culling
-
Warnock's screen-space subdivision
-
Selective K-d Tree Traversal
-
*Hierarchical Occlusion Maps (* not actually conservative!)
-
Cells and Portals
input: some types of objects
output: some set of potentially visible objects
these are preprocessors - they remove objects from consideration,
but do not necessarily solve the problem
Raycasting