The Object Complexity Model for Hidden-Surface Elimination

E. F. Grove, T. M. Murali, and J. S. Vitter. ``The Object Complexity Model for Hidden-Surface Elimination,'' International Journal of Computational Geometry and Applications, 9, 1999, 207-217. A preliminary version appeared in the Proceedings of the Seventh Canadian Conference on Computational Geometry (CCCG '95), Québec City, Québec, Canada, August 1995.

Full text (Adobe pdf format)

We define a new complexity measure, called object complexity, for hidden-surface elimination algorithms. This model is more appropriate than the standard scene complexity measure used in computational geometry for predicting the performance of these algorithms on current graphics rendering systems.

We also present an algorithm to determine the set of visible windows in 3-D scenes consisting of n isothetic windows. It takes time $O(n \log n)$, which is optimal. The algorithm solves in the object complexity model the same problem that Bern addressed for the standard scene complexity model.