X-maps: An Efficient Model for Non-manifold Modeling

Many representation schemes have been proposed to deal with non-manifold and mixed dimensionalities objects. A majority of those models are based on incidence graphs and although they provide efficient ways to query topological adjacencies, they suffer two major drawbacks: redundancy in the storage of topological entities and relationships, and the lack of a uniform representation of those entities that leads to the development of large sets of intricate topological operators. As regards to manifold meshes - and specifically triangular ones - compact and efficient models are known for twenty years. Ordered topological models like combinatorial maps or half edges based data structures are widely studied and used. We propose a new representation scheme - the extended maps or X-maps - that enhances those models to deal with non-manifold objects and mixed dimensionalities. We exhibit properties that allows an adaptive implementation of the cells and thus ensures that X-maps scale well in case of large surface areas or manifold pieces. We show that the storage requirements for X-maps is strongly reduced compared to the radial edge and similar structures and also present optimizations in case of triangular or tetrahedral non-manifold meshes.