THE OBJECT COMPLEXITY MODEL FOR HIDDEN-SURFACE REMOVAL
Edward F. Grove, T. M. Murali, Jeffrey Scott Vitter · International Journal of Computational Geometry & Applications · 1999
We define a new model of complexity, called object complexity, for measuring the performance of hidden-surface removal algorithms. This model is more appropriate for predicting the performance of these algorithms on current graphics rendering systems than the standard measure of scene complexity used in computational geometry. We also consider the problem of determining the set of visible windows in scenes consisting of n axis-parallel windows in ℝ3. We present an algorithm that runs in optimal Θ(n log n) time. The algorithm solves in the object complexity model the same problem that Bern3 addressed in the scene complexity model.