Given a large geometric model like a building, it is an important issue in computer graphics to develop an efficient walkthrough algorithm for interactively rendering the model. We can significantly speed up the rendering by accelerating a clipping operation and precomputing invisible polygons.
Kim et al. [1]suggested Visibility layers which provide efficient visibility operations from a given source. The visibility layers maintain the polygons in the geometric model in a sequence of layers according to their visibility relationship with respect to the source. For each layer, they constructed the shadow region from the source cast by the polygons in the layer. Every ray shot from the source intersects the boundary of the shadow region at most once. From this fact, they developed an efficient clipping operation for a viewer in the source.
In order to generate an image from an arbitrary points, we divide the 3D scene space into cells using grids, octrees or binary space partition trees, and then construct visibility layers for each cell. These visibility layers efficiently support the clipping operation from any view point in the 3D scene space. Moreover, in order to increase the performance of the clipping operation, we develop compact visibility layers to reduce the number of layers. We also suggest an algorithm for efficiently eliminating the invisible polygons from each cell. Our experiment shows that this method is well adapted to various environments including densely occluded models and sparsely occluded models.
