Tech Report CS-96-15

Hidden-Surfaces: Combining BSP Trees with Graph-Based Algorithms

Timothy Miller

April 1996

Abstract:

BSP trees and a priori potential-occlusion-graph-based techniques may be unified to produce a superior algorithm for visible surface determination involving a hybrid data structure in which BSP nodes are used where the simple graph-based algorithm breaks down. In particular, empirical results show around two to three times fewer split polygons for this method, 20--40% less run-time space needed, and up to 34% faster display refresh rates overall (including significant computation not affected by the algorithm).

(complete text in pdf or gzipped postscript)