Q-Complex: efficient non-manifold boundary representation with inclusion topology
Published in Computer-Aided Design, 2012
Abstract: The interpretation of auxiliary entities as boundary entities in previous non-manifold boundary (NMB) representations may change a model’s intended topology and increase the complexity of the corresponding data structure. In this paper, entities appearing in a modeling process are classified into boundary and non-boundary entities. Non-boundary entities are usually embedded into embedding- space entities. These embedding relationships are described by inclusion topology. To support inclusion topology, a new mathematical framework—quasi-cell-complex, as well as a topological data structure— Q -Complex, are proposed. Quasi-cell-complex is an extension of cell-complex with inclusion topology supported. Q -Complex is an NMB representation, in which a new topological entity—embedder is created for inclusion topology and zone/disk is adopted to capture the complete adjacencies around a vertex. Thus, Q -Complex allows full adjacencies, incidence-ordering, and inclusion relationships to be derived, and the efficiency of most basic queries is several times faster than most state-of-the-art NMB representations, without increasing storage. Additionally, the benefits of inclusion topology for shape modeling and feature modeling are explored.
Recommended citation: Long Zeng, Yong-Jin Liu, Sang-Hun Lee, Ming-Fai Yuen (2012) Q-Complex: efficient non-manifold boundary representation with inclusion topology. Computer-Aided Design, Vol. 44, No. 11, pp. 1115-1126, 2012.