User:KaterinaNMT

From Wikipedia, the free encyclopedia

Non-manifold topology[edit]

Mathematically, non-manifold topology (NMT) is defined as cell-complexes that are subsets of the Euclidean Space[1]. It may refer to the logic of how elements or spaces are connected in a non-manifold model.

Non-manifold definition[edit]

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 ℝ3 can be considered as exhaustively decomposing the ℝ3 into disjoint sets of elements of zero, one, two, and three dimensional point sets, i.e., vertices, edges, faces, and regions respectively)[4].

Geometric primitives[edit]

The geometric primitives comprise the vertex, edge, face and region [5][6]. A non-manifold object can be any combination of the above point set elements

  • A vertex is a zero dimensional point element defined by a position vector in ℝ3.
  • An edge is a connected one dimensional element defined by its geometry and end points. In the linear modelling domain, an edge is defined by two end vertices only. An edge does not include its bounding vertices.
  • A face is a connected two dimensional element defined by its geometry and bounding vertices and edges. In linear geometry domain, bounding vertices and edges on the same plane define a face. A face does not include its bounding vertices and edges. A face can be either convex or concave and have multiple loops.
  • A region is a connected three dimensional element defined by bounding vertices, edges, and faces. A region does not include its boundary elements and there is always one, and only one, region whose volume is infinite.

Topological primitives[edit]

The topological primitives comprise the loop, shell, volume and complex.

  • The loop is an ordered set of edges. The edges bounding a face are divided into closed circuits of edges, called loops [7]. Isolated and inter-connected vertices and edges can form open and closed loops.
  • Each closed set of faces in the object forms a shell [8].
  • A volume can be made out of a series of connected shells.
  • The complex is the top-most element. Complexes can be made out of any combination of volumes, faces, edges and vertices [9].

Data structures[edit]

Data structures are ways to organise information, which, in conjunction with algorithms, permit the efficient and elegant solution of computational problems[10]. 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 included below:

Data structure Reference
Radial Edge Structure [11]
Vertex-based Boundary Representation [12]
Coupling Entity Structure [13]
Selective Geometric Complexes [14]
Partial Entity Structure [15]
Loop Edge Data Structure [16]
Incidence Simplicial Data Structure [17]
Doubly-Connected Edge List/Half-Edge data structure [18]
Winged-edge data structure [19]

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:

v – e + (f – r) = 2 (s – h)

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[20]:

v – e + (f – r) – (V – Vh +Vc) = C – Ch + Cc

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 operationsCite error: A <ref> tag is missing the closing </ref> (see the help page).</ref>. Based on this relation, the Euler operators are used for editing an object, so that the Euler-Poincaré formula is always satisfied. There are two groups of such operators: the Make group and the Kill group. Operators start with M and K and are operators of the Make and Kill groups, respectively. Euler operators are written as Mxyz and Kxyz for operations in the Make and Kill groups, respectively, where x, y and z are elements of the model (e.g., a vertex, edge, face, loop, shell and genus). For example, MEV means adding an edge and a vertex while KEV means deleting an edge and a vertex.

Modeling operations[edit]

The modeling operations include additional operations, such as Boolean operations (union, intersection, difference) both ‘regular’ and ‘non-regular’, and other uniquely topological operations such as split, merge, impose, etc. A further classification of these operations might be in terms of the dimensionality of result produced, compared with the dimensionality of principle inputs. For example, operations might be classified as whether the dimensionality of the result is higher, or the same or lower than the principle inputs.

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 (half-spaces or volume primitives). The operations used to control the selection are the regularized Boolean union, intersection, and difference[21]. 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, external faces of the input bodies that are within the resulting body are retained[22]. 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 successfully used in the ship-building field to represent complex hull structures[23]. 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 successfully used in the medical field to model complex organic structures with multiple internal zones[24][25].
Architectural design: Considering the above applications, transferring NMT’s success from the ship-building and the medical fields to architecture in order to enhance the representation of architectural space is not far-fetched[26]. It is possible to compare the scale, spatial organisation, and complexity of a ship to that of a building. It is also possible to compare complex organic structures with multiple internal zones to complex buildings with similar multiple internal zones. The approach afforded by NMT provides topological clarity that has the potential to allow architects to better design, analyse, reason about, and produce their buildings. The potential of NMT in the early design stages is already proven and research has been undertaken with regard to the advantages of NMT's application for energy analysis in the early design stages[27][28]. Non-manifold topology has already been applied together with parametric and associative scripting to model the spatial organization of a building[29]. This information was then used to create different analytical and material models of a building.
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 CSG and Boundary representation modeling)[30].

References[edit]

  1. ^ Masuda, H., 1993. Topological operators and Boolean operations for complex-based non-manifold geometric models. Computer-Aided Design, 25(2), pp.119–129.
  2. ^ https://knowledge.autodesk.com/support/maya-lt/learn-explore/caas/CloudHelp/cloudhelp/2016/ENU/MayaLT/files/GUID-8E97CEF7-1CFE-4838-B4B7-59F526E21AB2-htm.html
  3. ^ Weiler, K., 1986. Topological structures for geometric modeling. Graduate Faculty of Rensselaer Polytechnic Institute.
  4. ^ Gursoz, E.L., Choi, Y. & Prinz, F., 1990. Non-regularlized Boolean set operations on non- manifold b-rep objects, Pittsburgh, PA.
  5. ^ Gursoz, E.L., Choi, Y. & Prinz, F., 1990. Non-regularlized Boolean set operations on non- manifold b-rep objects, Pittsburgh, PA.
  6. ^ Zamanian, M.K., Fenves, S.J. & Gursoz, E.L., 1992. Representing spatial abstractions of constructed facilities. Building and Environment, 27(2), pp.221–230.
  7. ^ Stroud, I., 2006. Boundary representation modelling techniques, London: Springer Verlag.
  8. ^ Stroud, I., 2006. Boundary representation modelling techniques, London: Springer Verlag.
  9. ^ Masuda, H., 1993. Topological operators and Boolean operations for complex-based non-manifold geometric models. Computer-Aided Design, 25(2), pp.119–129.
  10. ^ Preparata, F.P. & Shamos, M.I., 1988. Computational Geometry: An Introduction, New York: Springer Verlag.
  11. ^ Weiler, K., 1986. Topological structures for geometric modeling. Graduate Faculty of Rensselaer Polytechnic Institute.
  12. ^ Gursoz, E.L., Choi, Y. & Prinz, F., 1990. Non-regularlized Boolean set operations on non-manifold b-rep objects, Pittsburgh, PA.
  13. ^ Yamaguchi, Y. & Kimura, F., 1995. Non-manifold topology based on coupling entities. IEEE Computer Graphics and Applications, 15, pp.42–50.
  14. ^ 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].
  15. ^ Lee, S.H. & Lee, K., 2001. Partial entity structure: a compact non-manifold boundary representation based on partial topological entities, pp.159–170.
  16. ^ 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].
  17. ^ 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.
  18. ^ 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: http://link.springer.com/10.1007/s00366-014-0378-6 [Accessed September 26, 2016].
  19. ^ 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.
  20. ^ 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.
  21. ^ Rossignac, J.R., 1996. Specification, representation, and construction of non-manifold geometric structures, New York.
  22. ^ 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.
  23. ^ 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.
  24. ^ Nguyen, Trunc Duc. 2011. “Simplifying The Non-manifold Topology of Multipartitioning Surface Networks.” Washington University, St. Louis, Missouri. http://openscholarship.wustl.edu/etd/510/.
  25. ^ 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.
  26. ^ Wassim Jabi (2016): Linking design and simulation using non-manifold topology, Architectural Science Review, DOI: 10.1080/00038628.2015.1117959.
  27. ^ 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.
  28. ^ 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.
  29. ^ 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.
  30. ^ 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.
Retrieved from "https://en.wikipedia.org/w/index.php?title=User:KaterinaNMT&oldid=763501902"