Volumetric cell‐and‐portal generation

We present an algorithm to generate a cell‐and‐portal decomposition of general indoor scenes. The method is an adaptation of the 3D watershed transform, computed on a distance‐to‐geometry sampled field. The watershed is processed using a flooding analogy in the distance field space. Flooding originates from local minima, each minimum producing a region. Portals are built as needed to avoid the merging of regions during their growth. As a result, the cell‐and‐portal decomposition is closely linked to the structure of the models. In a building, the algorithm finds all the rooms, doors and windows. To restrict the memory load, a hierarchical implementation of the algorithm is presented. We also explain how to handle possible model degeneracies ‐such as cracks, holes and interpenetrating geometries‐ using a pre‐voxelisation step. The hierarchical algorithm, preceded when necessary by the pre‐voxelisation, was tested on a large range of models. We show that it is able to deal with classical architectural models, as well as cave‐like environments and large mixed indoor/outdoor scenes. Thanks to the intermediate distance field representation, the algorithm can be used regardless of the way the model is represented: it deals with parametric curves, implicit surfaces, volumetric data and polygon soups in a unified way.