1 Introduction

Visibility determination is one of the most important tasks in computer graphics. The goal of visibility determination (also known as hidden surface removal) is to determine parts of the model of virtual environment (MVE) which are visible, given a viewpoint and viewing direction.

Many algorithms to solve the hidden surface removal problem were developed, two of them most commonly used. An example of object space algorithm - the Binary Space Partitioning (BSP) preserves the topological information about the model in a binary tree. Knowing the position of the observer rendering order can be determined by appropriate traversal of the BSP-tree. The z-buffer is an image space oriented algorithm, solving the problem of visibility for each pixel of the screen. This is simple to implemented in hardware, thus commonly used in todays rendering systems. However, these algorithms are not output-sensitive, since they may spend significant time processing parts of the model actually invisible to an observer.

It seems to be worthwhile to study restrictions in visibility and to apply some more sophisticated methods of visibility preprocessing, to speedup queries for visible portion of the model given certain viewpoint or a set of viewpoints.

Teller and Séquin introduced a method to determine the conservative visibility, overestimating the visible portions of the model in [TS91, Tel92]. This method achieves very good performance when applied to densely occluded environments, such as models of architectural interiors. The algorithm is based on spatial subdivision and determination of potentially visible sets (PVS) (portions of the model) for each part of the subdivision.

Recently more general algorithms [CT96, GKM93] appeared, using an idea of obscuration culling instead of potentially visible sets. These algorithms are basically less complicated than Teller's approach and they are not so sensitive to the type of the model they are applied to. However, in the case of densely occluded interiors, the results obtained by obscuration culling does not seem to reach the performance of the PVS approach.

In this paper outlines of the visibility determination based on Teller's technique are described together with some results obtained by this method. Finally discussion about the effectiveness of visibility algorithms is presented, with some possible future directions in this field.

Jiri Bittner - bittner@sgi.felk.cvut.cz