Conservative visibility and strong occlusion for viewspace partitioning ofdensely occluded scenes

Computing the visibility of out-door scenes is often much harder than of in -door scenes. A typical urban scene,for example, is densely occluded, and i t is effective to precompute its visibility space, since fr om a given poin t only a small fraction of the scene is visible. The difficulty is that alt hough the majority, of objects are hidden, some parts might be visible at a distance in an arbitrary location, and it is not clear how to detect them quickly. In this paper we present a method to partition the viewspace into cells containing a conservative superset of the visible objects. For a give n cell the method tests the visibility of all the objects in the scene; For each object it searches for a strong occluder which guarantees that the ob ject is not visible from any point within the cell. We show analytically th at in a densely occluded scene, the vast majority of objects are strongly o ccluded, and the overhead of using conservative visibility (rather than vis ibility) is small. These results are further supported by our experimental results. We also analyze the cost of the method and discuss its effectivene ss.