Non-manifold topology
In a traditional 3D modelling environment, solid objects (e.g. polyhedral) are said to have a 2-manifold boundary. If one imagines the boundary to be flattened and made infinite, then each point on this boundary is completely surrounded by other points on that 2-dimensional boundary. Examples of 2-manifolds include the surface of a torus, a sphere, or a prism. More importantly, each point on the boundary of a 2-manifold solid divides the modelling space into two regions, the solid material inside the boundary and the void of the outside world. A non-manifold topology (NMT) is defined as the condition at which a point on the boundary does not divide the modelling space into two regions. Practically, non-manifold geometric models can be defined as combinations of vertices, edges, surfaces and volumes. Contrary to traditional solid geometry boundary representation, NMT allows for and consistently represents any combination of these elements within a single entity. Conversely, traditional boundary representation struggles with representations where a surface divides the interior of a polyhedron, an edge is shared by more than two surfaces or ones that combine an isolated vertex, edge, surface and a solid in one representation.
Non-manifold definition[edit]
Mathematically, NMT is defined as cell-complexes that are subsets of Euclidean space[1]. It may refer to the logic of how elements or spaces are connected in a non-manifold model. Non-manifold is a geometric topology term that means 'to allow any combination of vertices, edges, surfaces and volumes to exist in a single logical body'. Such models allow multiple faces meeting at an edge or multiple edges meeting at a vertex. Coincident edges and vertices are merged. Moreover, non-manifold topology models have a configuration that cannot be unfolded into a continuous flat piece and are thus not physically realisable and non-manufacturable[2].
Non-manifold modeling[edit]
Non-manifold modeling is a modeling form which removes constraints traditionally associated with manifold solid modeling forms by embodying all of the capabilities of wireframe modelling, surface modeling and solid modeling forms in a unified representation and extending the representational domain beyond that of the above modeling forms[3]. Non-manifold modelling in three-dimensional space can be considered as exhaustively decomposing the three-dimensional space into disjoint sets of elements of zero, one, two, and three dimensional point sets, i.e., vertices, edges, faces, and regions respectively)[4].
Topological entities[edit]
Elements within NMT structures are hierarchically inter-connected. The bottom-most element is a vertex (point). Vertices can exist in isolation or they can be the end-points of an edge (line). The similarity with traditional surface boundary representation ends here because isolated and inter-connected vertices and edges can form open and closed wires. Closed wires with ordered edges form the basis of a face (surface). Faces, in turn, can be combined to create shells, but those can also contain isolated vertices, edges, and faces. Then, a cell can be made from a series of closed and connected faces (i.e. a closed shell). A group of inter-connected cells create a CellComplex which can also include lower-dimensional entities through secondary relationships. Finally, any number of entities of different dimensionalities can be grouped together in a Cluster. These expanded data structures and topological relationships allow for a richer representation of loci, centrelines, elements, surfaces, volumes, and hierarchical groupings
Data structures[edit]
Data structures are ways to organise information, which, in conjunction with algorithms, permit the efficient and elegant solution of computational problems[5]. Geometric algorithms involve the manipulation of objects which are not handled at the machine language level. The user must therefore organise these complex objects by means of the simpler data types directly representable by the computer. These organisations are universally referred to as data structures. Some major topological data structures are the radial edge structure [6], the vertex-based boundary representation [7], the coupling entity structure [8] the selective geometric complexes [9], the partial entity structure [10], the loop edge data sructure [11], the incidence simplicial data structure [12], the doubly-connected edge list/Half-edge data structure [13] and the winged-edge data structure [14].
Editing operations[edit]
Euler operations for manifold geometric modelling[edit]
In manifold solid modelling, the numbers of topological elements must satisfy an equation, which is called the Euler–Poincaré formula:
where
- v is the number of vertices
- e is the number of edges
- f is the number of faces
- r is the number of rings that are cavities in faces
- s is the number of shells that are continuous surfaces
- h is the number of holes through the object
Basic operations that generate and delete topological elements according to the Euler–Poincaré formula are called Euler operations.
Euler operations for non-manifold geometric modelling[edit]
In a cell complex, the numbers of n-cells must satisfy the Euler–Poincaré formula. However, in non-manifold geometric modelling the above formula is not satisfied, and instead a new formula is introduced. Therefore, supposing that each topological element has no cavities and holes, the numbers of topological elements satisfy the following formula[15]
where
- v is the number of vertices
- e is the number of edges
- f is the number of faces
- V is the number of volumes
- C is the number of complexes
- r is the number of rings
- Vh is the number of holes through volumes
- Vc is the number of cavities in volumes
- Ch is the number of holes through complexes
- Cc is the number of cavities in complexes
Basic operations that generate and delete topological elements according to the Euler- Poincaré formula are called Euler operations[16]. Based on this relation, the Euler operators are used for editing an object, so that the Euler–Poincaré formula is always satisfied.
Modeling operations[edit]
A constructive solid geometry (CSG) representation defines a recipe for a solid as a selection of 3-D cells from a decomposition of space induced by the CSG primitives. The operations used to control the selection are the regularized Boolean Union, Intersection, and Difference[17]. Generally with regular Boolean operations, external faces of the input bodies that are within the resulting body are removed. In the case of non-regular Boolean operations (e.g. Merge, Impose, Imprint etc.), external faces of the input bodies that are within the resulting body are retained[18]. As a result, regular operations lead to a manifold result, while non-regular operations lead to a non-manifold result.
Applications of non-manifold topology[edit]
Ship building industry: NMT has been used in the ship-building field to represent complex hull structures[19]. In this field, the use of NMT allowed designers to segment a complex overall form into more cellular zones and spaces in a consistent manner.
Medical field: NMT has been used in the medical field to model complex organic structures with multiple internal zones[20][21].
Architectural design: The potential of NMT in the early design stages has been demonstrated with regard to the advantages of NMT's application for energy analysis in the early design stages[22][23]. Non-manifold topology has already been applied together with parametric and associative scripting to model the spatial organization of a building[24].
3D modeling: Non-manifold geometric models can maintain additional data, which may not appear in the resultant shape. This is one of their most useful characteristics, as it allows hybrid representation (hybrid representation is a modeling form that has characteristics of both constructive solid geometry and boundary representation modeling)[25]
References[edit]
This article "Non-manifold topology" is from Wikipedia. The list of its authors can be seen in its historical and/or the page Edithistory:Non-manifold topology. Articles copied from Draft Namespace on Wikipedia could be seen on the Draft Namespace of Wikipedia and not main one.
- ↑ Masuda, H., 1993. Topological operators and Boolean operations for complex-based non-manifold geometric models. Computer-Aided Design, 25(2), pp. 119–129.
- ↑ https://knowledge.autodesk.com/support/maya-lt/learn-explore/caas/CloudHelp/cloudhelp/2016/ENU/MayaLT/files/GUID-8E97CEF7-1CFE-4838-B4B7-59F526E21AB2-htm.html
- ↑ Weiler, K., 1986. Topological structures for geometric modeling. Graduate Faculty of Rensselaer Polytechnic Institute.
- ↑ Gursoz, E.L., Choi, Y. & Prinz, F., 1990. Non-regularlized Boolean set operations on non- manifold b-rep objects, Pittsburgh, PA.
- ↑ Preparata, F.P. & Shamos, M.I., 1988. Computational Geometry: An Introduction, New York: Springer Verlag.
- ↑ Weiler, K., 1986. Topological structures for geometric modeling. Graduate Faculty of Rensselaer Polytechnic Institute.
- ↑ Gursoz, E.L., Choi, Y. & Prinz, F., 1990. Non-regularlized Boolean set operations on non-manifold b-rep objects, Pittsburgh, PA.
- ↑ Yamaguchi, Y. & Kimura, F., 1995. Non-manifold topology based on coupling entities. IEEE Computer Graphics and Applications, 15, pp. 42–50.
- ↑ Rossignac, J. & Connor, M., 1989. SGC: A dimension-independent model for pointsets with internal structures and incomplete boundaries. In M. Wosny, J. Turner, & K. Preiss, eds. IFIP Workshop on CAD/CAM. Rensselaerville, NY: North-Holland, pp. 145–180. Available at: http://www.cc.gatech.edu/~jarek/papers/SGC.pdf [Accessed January 11, 2017].
- ↑ Lee, S.H. & Lee, K., 2001. Partial entity structure: a compact non-manifold boundary representation based on partial topological entities, pp. 159–170.
- ↑ McMains, S.A., 2000. Geometric Algorithms and Data Representation for Solid Freeform Fabrication. University of California, Berkeley. Available at: http://www.me.berkeley.edu/~mcmains/pubs/thesis.pdf [Accessed November 2, 2016].
- ↑ Hui, A. & De Floriani, L., 2007. A Two-Level Topological Decomposition for Non-manifold Simplicial Shapes. In SPM ‘07: Proceedings of the 2007 ACM Symposium on Solid and Physical Modeling. New York, USA, pp. 335–360.
- ↑ Dyedov, V. et al., 2015. AHF: array-based half-facet data structure for mixed-dimensional and non-manifold meshes. Engineering with Computers, 31(3), pp. 389–404. Available at: https://link.springer.com/10.1007/s00366-014-0378-6 [Accessed September 26, 2016].
- ↑ Baumgart, B.G., 1972. Winged Edge Polyhedron Representation. National Technical Information Service, (October). Available at: http://www.dtic.mil/dtic/tr/fulltext/u2/755141.pdf.
- ↑ Masuda, H. et al., 1989. A Mathematical Theory and Applications of Non-Manifold Geometric Modeling. In International Symposium on Advanced Geometric Modelling for Engineering Applications. Berlin, Germany, pp. 89–103.
- ↑ Masuda, H. et al., 1989. A Mathematical Theory and Applications of Non-Manifold Geometric Modeling. In International Symposium on Advanced Geometric Modelling for Engineering Applications. Berlin, Germany, pp. 89–103.
- ↑ Rossignac, J.R., 1996. Specification, representation, and construction of non-manifold geometric structures, New York.
- ↑ Aish, R. & Pratap, A., 2013. Spatial Information Modeling of Buildings using Non-Manifold Topology with ASM and DesignScript. In L. Hesselgren et al., eds. Advances in Architectural Geometry 2012. Vienna: Springer, pp. 25–36.
- ↑ Lee, S.U., Roh, M.I., Cha, J.H. and Lee, K.Y. Ship compartment modeling based on a non-manifold polyhedron modeling kernel, Advances in Engineering Software. 40 (2009) 378–388.
- ↑ Nguyen, Trunc Duc. 2011. “Simplifying The Non-manifold Topology of Multipartitioning Surface Networks.” Washington University, St. Louis, Missouri. http://openscholarship.wustl.edu/etd/510/.
- ↑ Bronson, Jonathan, Joshua A. Levine, and Ross Whitaker. 2014. “Lattice Cleaving: A Multimaterial Tetrahedral Meshing Algorithm with Guarantees.” IEEE Transactions on Visualization and Computer Graphics 20 (20): 223–237. doi:10.1109/TVCG.2013.115.
- ↑ Jabi, Wassim 2015. The potential of non-manifold topology in the early design stages. In: Combs, Lonn and Perry, Chris eds. Computational Ecologies: Design in the Anthropocene. Proceedings of the 35th Annual Conference of the Association for Computer Aided Design in Architecture, University of Cincinnati, pp. 381–393.
- ↑ Jabi, Wassim 2014. Parametric spatial models for energy analysis in the early design stages. Presented at: Symposium for Architecture and Urban Design – SimAUD 2014, Tampa, FL, 13–16 April 2014. Published in: Gerber, D. and Goldstein, R. eds. 2014 Proceedings of the Symposium for Architecture and Urban Design. San Diego, CA: Simulations Councils, Inc., pp. 17–24.
- ↑ Aish, Robert, and Aparajit Pratap. 2013. “Spatial Information Modeling of Buildings using Non-manifold Topology with ASM and DesignScript.” In: Advances in Architectural Geometry 2012, edited by Lars Hesselgren, Shrikant Sharma, Johannes Wallner, Niccolo Baldassini, Philippe Bompas, and Jacques Raynaud, 25–36. Vienna: Springer Vienna. doi:10.1007/978-3-7091-1251-9.
- ↑ Masuda, H. et al., 1989. A Mathematical Theory and Applications of Non-Manifold Geometric Modeling. In International Symposium on Advanced Geometric Modelling for Engineering Applications. Berlin, Germany, pp. 89–103.
