Partial entity structure
Authors:
- Kunwoo LeeKLKunwoo Lee
Open Access
- 1 May 2001
- conference paper
- Published by Association for Computing Machinery (ACM)
- p. 159-170
Abstract
Non-manifold boundary representations have gained a great deal of popularity in recent years and various representation schemes have been proposed because they allow an even wider range of objects for various applications than conventional manifold representations. However, since these schemes are mainly interested in describing sufficient adjacency relationships of topological entities, the models represented in these schemes occupy too much storage space redundantly although they are very efficient in answering queries on topological adjacency relationships. Storage requirement can arise as a crucial problem in models in which topological data is more dominant than geometric data, such as tessellated or mesh models.To solve this problem, in this paper, we propose a compact non-manifold boundary representation, called the partial entity structure, which allows the reduction of the storage size to half that of the radial edge structure, which is known as a time efficient non-manifold data structure, while allowing full topological adjacency relationships to be derived without loss of efficiency. This representation contains not only the conventional primitive entities like the region, face, edge, and vertex, but also the partial topological entities such as the partial-face, partial-edge, and partial-vertex for describing non-manifold conditions at vertices, edges, and faces. In order to verify the time and storage efficiency of the partial entity structure, the time complexity of basic query procedures and the storage requirement for typical geometric models are derived and compared with those of existing schemes. Furthermore, a set of the generalized Euler operators and typical high-level modeling capabilities such as Boolean operations are also implemented to confirm that our data structure is sound and easy to be manipulated.Keywords
This publication has 20 references indexed in Scilit:
- Offsetting operations on non-manifold boundary representation models with simple geometry1999
- Non-manifold modelling: an approach based on spatial subdivisionComputer-Aided Design, 1997
- gnomes: an object-oriented nonmanifold geometric engineComputer-Aided Design, 1995
- Octree-based automatic mesh generation for non-manifold domainsEngineering with Computers, 1995
- Nonmanifold topology based on coupling entitiesIEEE Computer Graphics and Applications, 1995
- High-quality solid-modelling system with free-form surfacesComputer-Aided Design, 1993
- Topological operators and Boolean operations for complex-based nonmanifold geometric modelsComputer-Aided Design, 1993
- Topological models for boundary representation: a comparison with n- generalized mapsComputer-Aided Design, 1991
- WITHDRAWN: Boolean set operations on non-manifold boundary representation objectsComputer-Aided Design, 1991
- Primitives for the manipulation of general subdivisions and the computation of VoronoiACM Transactions on Graphics, 1985