A New Partitioning Method for Architectural environments

Main page for other related papers


D. Meneveaux, E. Maisel, K. Bouatouch
Journal of Visualization and Computer Animation.
Wiley Publishers, Nov 98.


Computing global illumination for complex environments in moderate time and walking through them is one of the challenges in computer graphics. To meet this goal, preprocessing is necessary. This preprocessing consists in partitioning the environment into cells and determining visibility between these cells. Most of the existing partitioning methods rely on the Binary Space Partitioning technique (BSP) which can be easily applied to axial environments. But for non axial scenes the BSP has a high complexity of $O(n^3)$ in time to construct a tree of size at worst $O(n^2)$, $n$ beeing the total number of input polygons. Moreover this technique entails a large number of cells that do not necessarily fit with the topology of the environment. We propose in this paper a partitioning method which can be applied to non axial buildings with several floors. It consists of two steps. In the first step, each floor is extracted by applying a BSP technique using the most occlusive horizontal polygons for splitting. In the second step, each floor is in turn partitioned with a model-based method operating in a dual 2D space. The result is a low number of cells fitting at best with the environment topology.