Premium
Volumetric cell‐and‐portal generation
Author(s) -
Haumont D.,
Debeir O.,
Sillion F.
Publication year - 2003
Publication title -
computer graphics forum
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 0.578
H-Index - 120
eISSN - 1467-8659
pISSN - 0167-7055
DOI - 10.1111/1467-8659.00677
Subject(s) - polygon (computer graphics) , computer science , algorithm , parametric statistics , flooding (psychology) , opengl , range (aeronautics) , morphing , computer graphics (images) , mathematics , artificial intelligence , visualization , psychology , telecommunications , statistics , materials science , composite material , frame (networking) , psychotherapist
Abstract 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.