Efficient Algorithms for Computing Conservative Portal Visibility Information

The number of polygons in realistic architectural models is many more than can be rendered at interactive frame rates. Typically, however, due to occlusion by opaque surfaces (e.g., walls), only small fractions of such models are visible from most viewpoints. This fact is used in many popular methods for preprocessing visibility information which assume a scene model subdivided into convex cells connected through convex portals. These methods need to establish which cells or parts thereof are visible to a generalized observer located within each cell. The geometry of this information is termed a ʹvisibility volumeʹ and its computation is usually quite complex. Conservative approximations of viewing volumes, however, are simpler and less expensive to compute. In this paper we present techniques and algorithms which permit the computation of conservative viewing volumes incrementally. In particular, we describe an algorithm for computing the viewing volumes for a given cell through a sequence of ʹmʹ portals containing a total of ʹnʹ edges in Omn time.