Efficient cells-and-portals partitioning

Abstract

In this paper we revisit the cells-and-portals visibility methods, originally developed for the special case of architectural interiors. We define an effectiveness measure for a cells-and-portals partition, and introduce a two-pass algorithm that computes a cells-and-portals partition. The algorithm uses a simple heuristic that strives to create small portals as a means for generating an effective partition. The input to the algorithm is a set of half edges in 2D that can be extracted from a complex polygonal model. The first pass of the algorithm creates an initial partition, which is then refined by the second pass. We show that our method creates a partition that is more effective than the common BSP partition, even when the latter is further refined with the application of our second pass. Our cells-and-portals algorithm is designed to deal with arbitrarily oriented walls. The algorithm also supports outdoor scenes, where the vertical walls of the buildings serve as occluders and portals are extended above the buildings. We show that the extended portals allow an output-sensitive rendering of large urban scenes. While most visibility algorithms use graphics hardware in order to cull hidden regions of the model, we examine the usefulness of a hardware-assisted portal test as opposed to the conventional software test. Finally, since our two-pass method is fully automatic and local, it supports incremental changes of the model by locally recomputing and updating the partition. We call our method 'Breaking the Walls' since it breaks out of indoor scenes to outdoor scenes, and allows walls to be broken interactively, with an instant updating of the partition. Copyright © 2006 John Wiley & Sons, Ltd.