Applications of interactive 3D graphics, including virtual reality(VR), must satisfy certain performance constraints. It is especially crucial to maintain a suitable frame rate and to respond to users as quickly as possible, disregarding the complexity of a virtual environment. With the advance in computer technology -especially in graphics hardware -the processing time involved in image generation has been shrinking steadily. As the demand for more complex and realistic environments grows, however, the techniques to reduce computing costs, without degrading the perceptual quality, will undoubtedly become increasingly important. Visibility culling is one such technique that detects objects not visible from the viewer and prevents them from being rendered, thereby reducing the amount of polygons fed to the graphics pipeline.
This thesis presents a new approach to visibility culling. We propose a conservative visibility preprocessing method for complex virtual environments. The proposed method deals with general 3D graphical models and invisible polygons jointly blocked by multiple occluders. The proposed method decomposes volume visibility from the predefined volume into the area visibility from rectangles surrounding predefined volume. Then, to handle the volume visibility, we solve the area visibility problem. The proposed method expresses area visibility information into 3D space and keeps it with a BSP(binary space partitioning) tree. Area visibility information is image plane information for every viewpoints within the view rectangle. To express the area visibility information in 3D space, we present modified ghost polygon and method reducing dependency between axes in view rectangle. The proposed method has been tested on several large-scale urban scenes, and has shown its effectiveness.