Jirí Bittner
Department of Computer Science, Czech Technical University,
Karlovo námestí 13, 121 35 Praha 2, Czech Republic
e-mail: bittner@sgi.felk.cvut.cz
Solving the hidden surface removal is an essential problem since the early time of computer graphics. Most of the algorithms designed, like z-buffer or BSP-tree, are not output-sensitive what means, that their time complexity is proportional to the total number of graphic primitives in the model. However, in many complex models most their parts are invisible to an observer while located in certain region. This observation yields a search to design output-sensitive algorithms with the runtime complexity (time of rendering) proportional to the number of visible graphic primitives. We present one such algorithm together withe an empirical evidence of the asset of the visibility determination. The method presented in this paper subdivides the model into smaller parts (cells) continuing with determination of visibility relations between them. To describe potentially visible sets a tree data structure is used, where edges correspond to tight approximations of potentially visible frustrums.
Keywords: visibility, hidden surface removal, obscuration culling,
spatial partitioning, computational geometry, virtual reality.