際際滷

際際滷Share a Scribd company logo

TopMesh A Tool for Extracting Topological Information From Non-Manifold Objects

University PARIS-SUD
University PARIS-SUD

Full paper presentation at the GRAPP2010 international conference. We present TopMesh, a tool for extracting topological information from non-manifold three-dimensional objects with parts of non-uniform dimensions. The boundary of such objects is discretized as a mesh of triangles and of dangling edges, representing one-dimensional parts of the object. The geometrical and topological information extracted include the number of elements in the mesh, the number of non-manifold singularities and the Betti numbers, which characterize the topology of an object independently of the discretization of its boundary. TopMesh also computes a decomposition of the mesh into connected parts of uniform dimension, into edge-connected components formed by triangles, and into oriented edge-connected sub-meshes. We describe the functionalities of TopMesh and the algorithms implementing them.

1 of 27
TopMesh A Tool for Extracting Topological Information From Non-Manifold Objects Leila De Floriani*, Laura Papaleo*^ * University of Genova (ITALY) ^ICT Department, Province of Genova (ITALY) Annie Hui University of Maryland (USA) 20/05/10 GRAPP2010 - Geometric Modeling
Overview Motivations Background Non-manifold singularities TS library TopMesh Extracting topological information Computing the 2-cycles Results Conclusions GRAPP2010 - Geometric Modeling 20/05/10
Non-manifold shapes: what? Manifold shapes shapes in which every point has a neighborhood homeomorphic to either an open ball (internal point), or to an open half-ball (boundary point) Non-manifold singularities : set of points in a non-manifold shape which do not satisfy the manifold condition Non-manifold shapes : shapes with a complex geometric and topological structure non-manifold singularities parts of different dimensions (2D, 1D, ) GRAPP2010 - Geometric Modeling 20/05/10
Non-manifold shapes: when? Result of a process of abstraction (idealization) applied to manifold shapes to produce iconic (idealized) models Applications: Finite element analysis and simulation Animation Non-manifold shapes often described through simplicial meshes GRAPP2010 - Geometric Modeling Original Idealized 20/05/10
Objective of the work To address the problem of extracting topological characteristics from non-manifold 3D shapes containing parts of different dimensions, discretized as simplicial complexes To design and develop a tool to compute the topological information from non-manifold shapes Useful for: Build a structural model based on topology Be the basis for semantic annotation and understanding of complex shapes GRAPP2010 - Geometric Modeling Semantic model 20/05/10 Geometric model Structural model Motor Blade Blade Blade Blade
Related work Segmentation techniques for manifold simplicial shapes [Shamir, 2006, Eurographics STAR] Techniques for form feature (protrusions, handles) extraction and identification from manifold CAD objects [Shah et al., 2001, survey] Representations of uniformly dimensional non-manifold shapes as collections of manifolds for CAD modeling and compression [Falcidieno et al., 1992; Gueziec et al., 1998] On Homology groups and simplicial complexes: combinatorial stratification for 2D cellular models [Pesco et al., 2004] incremental algorithm for Betti numbers in simplicial 3-complexes [Delfinado Edelsbrunner, 1998] approach to compute generators of the homology groups for compacted triangulated 3-manifolds [Dey Guha 1998] GRAPP2010 - Geometric Modeling 20/05/10
Background: triangle-segment mesh Definition : it is a 2D mesh discretizing the boundary of a non-manifold, non-regular three-dimensional object. It is a 2D simplicial complex embedded in the 3D Euclidean space [Agoston, 2005]. Entities: triangles, wire-edges (edges that do not bound any triangles), vertices. The collection of all the vertices and edges form the 1- skeleton of the mesh . No wire-edges simple triangle mesh. At least one edge bounding only one triangle triangle mesh with boundary . 20/05/10 GRAPP2010 - Geometric Modeling yes no no
Background: Vertex: manifold & non-manifold Be T a triangle-segment mesh, v a vertex v is a manifold vertex if it belongs only to one or two wire-edges or the Link(v) consists of a closed or open chains of edges v is non-manifold otherwise Recall: Star(v): set of triangles & edges incident at v . Link(v): set of edges & vertices in the Star( v ) not incident in v 20/05/10 GRAPP2010 - Geometric Modeling A manifold vertex v A non-manifold vertex v
Background: Edge: manifold & non-manifold Be T a triangle-segment mesh, e an edge e is a manifold edge if its Link consists of one or two vertices otherwise e is non-manifold Recall: Star(e): set of triangles sharing e . Link(e): set of vertices of the triangles in Star( e ) not included in e 20/05/10 GRAPP2010 - Geometric Modeling e A manifold edge e A non-manifold edge
Background: The Betti numbers Fundamental characterization of a 3D object 硫0: number of connected components, 硫1: number of 1-cycles (independent tunnels, through holes) 硫2 : number of 2-cycles (parts of the object which enclose empty space -voids). Betti numbers together in the Euler Poincares formula v e + f = 硫0 硫1 + 硫2 20/05/10 GRAPP2010 - Geometric Modeling one 1-cycle and one 2-cycles two 2-cycles
The TS data structure: Encoding a Non-Manifold Model Generalizes the Indexed structure with Adjacencies to the non-manifold case Encodes all vertices and top simplexes (triangles & wire edges) Relations: wire-edge-vertex (for each e its vertices) triangle-vertex (for each t its vertices) triangle-triangle-at-edge [partial] ( for a triangle t and for each e those triangle(s) immediately preceding and succeeding t around e ) vertex-triangle (for each v one triangle for each 1-connected component incident at v ) vertex-wire-edge (for each v all the wire edges incident v ) 20/05/10 GRAPP2010 - Geometric Modeling *De Floriani et al. CAD Journal (2004)
TopMesh: basic functionalities 1) non-manifold singularities non-manifold vertices, non-manifold edges and wire-edges 2) components with various degrees of connectivity connected components wire-webs (maximal connected components formed by the wire-edges) edge-connected components ( parts which do not contain non-manifold vertices) 3) Number of 2-cycles deducing the Betti numbers 20/05/10 GRAPP2010 - Geometric Modeling
Extracting Non-manifold Singularities & Wire-Edges We provide algorithms for counting and extracting non-manifold vertices, non-manifold edges wire edges 20/05/10 GRAPP2010 - Geometric Modeling Wire-edges explicitly encoded in the TS retrieval and counting is trivial Non-Manifold Vertices for each vertex v take Vertex-triangle and vertex-wire-edge v is manifold if only one of the two relations is not empty if the vertex-triangle relation is not empty, it consists only one triangle if the vertex-wire-edge relation is not empty, it consists of either one or two wire-edges non-manifold otherwise Non-manifold edges For each e consider a triangle t incident at e e is non-manifold if the predecessor and successor in the triangle-triangle-at-edge of t at e, are different
Computing: Connected compontens, 1-Connected Components & Wire-webs To detect parts with certain connectivity, a traversal of the entire model is necessary 20/05/10 GRAPP2010 - Geometric Modeling Connected Components Apply a labeling approach to the 1-skeleton. BF traversal in the TS with a queue. Visit all the triangles t in the vertex-triangle and all the wire-edges e in the vertex-wire-edge . Betti number b0 , is the total number of connected components. Wire-webs connected components formed only of wire-edges. Apply a BF traversal considering for each vertex v , only the incident wire-edges and the corresponding vertices 1-connected components Consider the sub-mesh cutting all the wire-webs . The 1-connected components correspond to connected components of its dual graph G (where nodes are triangles and arcs exists for edges shared by two or more triangles) Used for the computation of the 2-cycles
Computing the 2-Cycles: General idea They are maximal 1-connected sub-meshes enclosing voids and not containing triangles dangling at non-manifold edges We use the 1-connected components and we cut the maximal 1-connected sub-meshes of triangles not bounding void s 2 number of 2-cycles in the model 2 computed 1 can be derived by the Eulers formula ( v -e+f= 0- 1+ 2 ) 20/05/10 GRAPP2010 - Geometric Modeling
Computing the 2-cycles: Triangle sides / adiacency triangle sides A triangle t has two triangle sides (with opposite normals) defined by the two possible orderings of its vertices Two triangle sides are adjacent at their common edge e if one is reachable from the other by crossing e 20/05/10 GRAPP2010 - Geometric Modeling Two triangle sides of two different triangles which are adjacent
Computing the 2-cycles: Oriented surfaces Definition a maximal edge-connected set of triangles sides, such that, for each pair of triangle sides s, s霞 in the set sharing an edge e s is the successor of s霞 according to one orientation of e, and s霞 is the successor of s according to the opposite orientation of e. An oriented surface may enclose a void. 20/05/10 GRAPP2010 - Geometric Modeling An oriented surface is basically the surface formed by all the triangle sides that are reachable (via adjacency) by a walking ant.
Def : An oriented surface S with boundary such that for each t-side s in S the other t-side s of the same triangle is in S ( cannot include any void ). Property there is exactly one oriented surface for each 1-connected component which does not define a 2-cycle #2-cycles = #OrientedSurface #1ConnectedComponents Computing the 2-cycles: Folded Surfaces 20/05/10 GRAPP2010 - Geometric Modeling C defines a cycle of triangles which can be expressed as the linear combination of the A and B . Thus, unlike A and B , C does not define a 2-cycle, since it contains the remaining oriented surfaces C A B C A B
Computing the 2-Cycles Oriented adjacency di-graph Algorithm: For each 1-connected component A Extract connected collections of triangle sides Extract oriented surfaces traversing the model taking the triangle sides and simulating the walk of an ant on a surface Oriented adjacency di-graph G of A nodes are triangle sides, there is a directed arc a from a node s to a node s霞 iff the two sides s and s霞 share an edge e , and side s霞 is the successor of s at e . 20/05/10 GRAPP2010 - Geometric Modeling
Computing the 2-Cycles Oriented adjacency di-graph Each strongly connected sub-graph of the oriented adjacency di-graph G defines an oriented surface NOTE: We do not build the oriented adjacency di-graph we simulate the di-graph G on the TS data structure, using an incremental labeling approach. 20/05/10 GRAPP2010 - Geometric Modeling
TopMesh TopMesh is a command line tool written in C++. Webservice for the AIM@SHAPE Digital shapes repository http://www.aimatshape.net Tested on several data sets Web pages http:// ggg.disi.unige.it / topmesh / the sw and the results http://indy.disi.unige.it/nmcollection/ a repository of non-manifold models 20/05/10 GRAPP2010 - Geometric Modeling
Complexity Extracting singularities & C. time complexity linear in the size of the input triangle-segment mesh Computing the 2-cycles The algorithm performs a visit on the di-graph G the number of nodes in G is proportional to the number of triangles and edges in the input mesh, the algorithm complexity is linear in the size of the mesh.
Results (1/3) 20/05/10 GRAPP2010 - Geometric Modeling
Results (2/3) 20/05/10 GRAPP2010 - Geometric Modeling
Results (3/3) All information extracted can be attached to the initial model using ontology-driven metadata instances of the concept NonManifoldMesh are automatically created 20/05/10 GRAPP2010 - Geometric Modeling COMMON SHAPE ONTOLOGY defined within AIM@SHAPE
Conclusions TopMesh: a tool for the extraction of topological information form a 3D object represented as a triangle-segment mesh encoded in the TS data structure. Webservice for a digital shape repository online integrated as core module in a Semantic Web system for inspecting, structuring annotating 3D shapes and scenes according to ontology-driven metadata We are extending the tool for: performing a semantic-oriented decomposition of a shape. managing large non-manifold meshes using spatial indexing techniques 20/05/10 GRAPP2010 - Geometric Modeling
Thanks for your attention. Questions? Laura Papaleo [email_address] 20/05/10 GRAPP2010 - Geometric Modeling This work has been partially supported by the MIUR-FIRB project SHALOM under contract number RBIN04HWR8, by the National Science Foundation under grant CCF-0541032, and by the MIUR-PRIN project on Multi-resolution modeling of scalar fields and digital shapes.

More Related Content

TopMesh A Tool for Extracting Topological Information From Non-Manifold Objects

  • 1. TopMesh A Tool for Extracting Topological Information From Non-Manifold Objects Leila De Floriani*, Laura Papaleo*^ * University of Genova (ITALY) ^ICT Department, Province of Genova (ITALY) Annie Hui University of Maryland (USA) 20/05/10 GRAPP2010 - Geometric Modeling
  • 2. Overview Motivations Background Non-manifold singularities TS library TopMesh Extracting topological information Computing the 2-cycles Results Conclusions GRAPP2010 - Geometric Modeling 20/05/10
  • 3. Non-manifold shapes: what? Manifold shapes shapes in which every point has a neighborhood homeomorphic to either an open ball (internal point), or to an open half-ball (boundary point) Non-manifold singularities : set of points in a non-manifold shape which do not satisfy the manifold condition Non-manifold shapes : shapes with a complex geometric and topological structure non-manifold singularities parts of different dimensions (2D, 1D, ) GRAPP2010 - Geometric Modeling 20/05/10
  • 4. Non-manifold shapes: when? Result of a process of abstraction (idealization) applied to manifold shapes to produce iconic (idealized) models Applications: Finite element analysis and simulation Animation Non-manifold shapes often described through simplicial meshes GRAPP2010 - Geometric Modeling Original Idealized 20/05/10
  • 5. Objective of the work To address the problem of extracting topological characteristics from non-manifold 3D shapes containing parts of different dimensions, discretized as simplicial complexes To design and develop a tool to compute the topological information from non-manifold shapes Useful for: Build a structural model based on topology Be the basis for semantic annotation and understanding of complex shapes GRAPP2010 - Geometric Modeling Semantic model 20/05/10 Geometric model Structural model Motor Blade Blade Blade Blade
  • 6. Related work Segmentation techniques for manifold simplicial shapes [Shamir, 2006, Eurographics STAR] Techniques for form feature (protrusions, handles) extraction and identification from manifold CAD objects [Shah et al., 2001, survey] Representations of uniformly dimensional non-manifold shapes as collections of manifolds for CAD modeling and compression [Falcidieno et al., 1992; Gueziec et al., 1998] On Homology groups and simplicial complexes: combinatorial stratification for 2D cellular models [Pesco et al., 2004] incremental algorithm for Betti numbers in simplicial 3-complexes [Delfinado Edelsbrunner, 1998] approach to compute generators of the homology groups for compacted triangulated 3-manifolds [Dey Guha 1998] GRAPP2010 - Geometric Modeling 20/05/10
  • 7. Background: triangle-segment mesh Definition : it is a 2D mesh discretizing the boundary of a non-manifold, non-regular three-dimensional object. It is a 2D simplicial complex embedded in the 3D Euclidean space [Agoston, 2005]. Entities: triangles, wire-edges (edges that do not bound any triangles), vertices. The collection of all the vertices and edges form the 1- skeleton of the mesh . No wire-edges simple triangle mesh. At least one edge bounding only one triangle triangle mesh with boundary . 20/05/10 GRAPP2010 - Geometric Modeling yes no no
  • 8. Background: Vertex: manifold & non-manifold Be T a triangle-segment mesh, v a vertex v is a manifold vertex if it belongs only to one or two wire-edges or the Link(v) consists of a closed or open chains of edges v is non-manifold otherwise Recall: Star(v): set of triangles & edges incident at v . Link(v): set of edges & vertices in the Star( v ) not incident in v 20/05/10 GRAPP2010 - Geometric Modeling A manifold vertex v A non-manifold vertex v
  • 9. Background: Edge: manifold & non-manifold Be T a triangle-segment mesh, e an edge e is a manifold edge if its Link consists of one or two vertices otherwise e is non-manifold Recall: Star(e): set of triangles sharing e . Link(e): set of vertices of the triangles in Star( e ) not included in e 20/05/10 GRAPP2010 - Geometric Modeling e A manifold edge e A non-manifold edge
  • 10. Background: The Betti numbers Fundamental characterization of a 3D object 硫0: number of connected components, 硫1: number of 1-cycles (independent tunnels, through holes) 硫2 : number of 2-cycles (parts of the object which enclose empty space -voids). Betti numbers together in the Euler Poincares formula v e + f = 硫0 硫1 + 硫2 20/05/10 GRAPP2010 - Geometric Modeling one 1-cycle and one 2-cycles two 2-cycles
  • 11. The TS data structure: Encoding a Non-Manifold Model Generalizes the Indexed structure with Adjacencies to the non-manifold case Encodes all vertices and top simplexes (triangles & wire edges) Relations: wire-edge-vertex (for each e its vertices) triangle-vertex (for each t its vertices) triangle-triangle-at-edge [partial] ( for a triangle t and for each e those triangle(s) immediately preceding and succeeding t around e ) vertex-triangle (for each v one triangle for each 1-connected component incident at v ) vertex-wire-edge (for each v all the wire edges incident v ) 20/05/10 GRAPP2010 - Geometric Modeling *De Floriani et al. CAD Journal (2004)
  • 12. TopMesh: basic functionalities 1) non-manifold singularities non-manifold vertices, non-manifold edges and wire-edges 2) components with various degrees of connectivity connected components wire-webs (maximal connected components formed by the wire-edges) edge-connected components ( parts which do not contain non-manifold vertices) 3) Number of 2-cycles deducing the Betti numbers 20/05/10 GRAPP2010 - Geometric Modeling
  • 13. Extracting Non-manifold Singularities & Wire-Edges We provide algorithms for counting and extracting non-manifold vertices, non-manifold edges wire edges 20/05/10 GRAPP2010 - Geometric Modeling Wire-edges explicitly encoded in the TS retrieval and counting is trivial Non-Manifold Vertices for each vertex v take Vertex-triangle and vertex-wire-edge v is manifold if only one of the two relations is not empty if the vertex-triangle relation is not empty, it consists only one triangle if the vertex-wire-edge relation is not empty, it consists of either one or two wire-edges non-manifold otherwise Non-manifold edges For each e consider a triangle t incident at e e is non-manifold if the predecessor and successor in the triangle-triangle-at-edge of t at e, are different
  • 14. Computing: Connected compontens, 1-Connected Components & Wire-webs To detect parts with certain connectivity, a traversal of the entire model is necessary 20/05/10 GRAPP2010 - Geometric Modeling Connected Components Apply a labeling approach to the 1-skeleton. BF traversal in the TS with a queue. Visit all the triangles t in the vertex-triangle and all the wire-edges e in the vertex-wire-edge . Betti number b0 , is the total number of connected components. Wire-webs connected components formed only of wire-edges. Apply a BF traversal considering for each vertex v , only the incident wire-edges and the corresponding vertices 1-connected components Consider the sub-mesh cutting all the wire-webs . The 1-connected components correspond to connected components of its dual graph G (where nodes are triangles and arcs exists for edges shared by two or more triangles) Used for the computation of the 2-cycles
  • 15. Computing the 2-Cycles: General idea They are maximal 1-connected sub-meshes enclosing voids and not containing triangles dangling at non-manifold edges We use the 1-connected components and we cut the maximal 1-connected sub-meshes of triangles not bounding void s 2 number of 2-cycles in the model 2 computed 1 can be derived by the Eulers formula ( v -e+f= 0- 1+ 2 ) 20/05/10 GRAPP2010 - Geometric Modeling
  • 16. Computing the 2-cycles: Triangle sides / adiacency triangle sides A triangle t has two triangle sides (with opposite normals) defined by the two possible orderings of its vertices Two triangle sides are adjacent at their common edge e if one is reachable from the other by crossing e 20/05/10 GRAPP2010 - Geometric Modeling Two triangle sides of two different triangles which are adjacent
  • 17. Computing the 2-cycles: Oriented surfaces Definition a maximal edge-connected set of triangles sides, such that, for each pair of triangle sides s, s霞 in the set sharing an edge e s is the successor of s霞 according to one orientation of e, and s霞 is the successor of s according to the opposite orientation of e. An oriented surface may enclose a void. 20/05/10 GRAPP2010 - Geometric Modeling An oriented surface is basically the surface formed by all the triangle sides that are reachable (via adjacency) by a walking ant.
  • 18. Def : An oriented surface S with boundary such that for each t-side s in S the other t-side s of the same triangle is in S ( cannot include any void ). Property there is exactly one oriented surface for each 1-connected component which does not define a 2-cycle #2-cycles = #OrientedSurface #1ConnectedComponents Computing the 2-cycles: Folded Surfaces 20/05/10 GRAPP2010 - Geometric Modeling C defines a cycle of triangles which can be expressed as the linear combination of the A and B . Thus, unlike A and B , C does not define a 2-cycle, since it contains the remaining oriented surfaces C A B C A B
  • 19. Computing the 2-Cycles Oriented adjacency di-graph Algorithm: For each 1-connected component A Extract connected collections of triangle sides Extract oriented surfaces traversing the model taking the triangle sides and simulating the walk of an ant on a surface Oriented adjacency di-graph G of A nodes are triangle sides, there is a directed arc a from a node s to a node s霞 iff the two sides s and s霞 share an edge e , and side s霞 is the successor of s at e . 20/05/10 GRAPP2010 - Geometric Modeling
  • 20. Computing the 2-Cycles Oriented adjacency di-graph Each strongly connected sub-graph of the oriented adjacency di-graph G defines an oriented surface NOTE: We do not build the oriented adjacency di-graph we simulate the di-graph G on the TS data structure, using an incremental labeling approach. 20/05/10 GRAPP2010 - Geometric Modeling
  • 21. TopMesh TopMesh is a command line tool written in C++. Webservice for the AIM@SHAPE Digital shapes repository http://www.aimatshape.net Tested on several data sets Web pages http:// ggg.disi.unige.it / topmesh / the sw and the results http://indy.disi.unige.it/nmcollection/ a repository of non-manifold models 20/05/10 GRAPP2010 - Geometric Modeling
  • 22. Complexity Extracting singularities & C. time complexity linear in the size of the input triangle-segment mesh Computing the 2-cycles The algorithm performs a visit on the di-graph G the number of nodes in G is proportional to the number of triangles and edges in the input mesh, the algorithm complexity is linear in the size of the mesh.
  • 23. Results (1/3) 20/05/10 GRAPP2010 - Geometric Modeling
  • 24. Results (2/3) 20/05/10 GRAPP2010 - Geometric Modeling
  • 25. Results (3/3) All information extracted can be attached to the initial model using ontology-driven metadata instances of the concept NonManifoldMesh are automatically created 20/05/10 GRAPP2010 - Geometric Modeling COMMON SHAPE ONTOLOGY defined within AIM@SHAPE
  • 26. Conclusions TopMesh: a tool for the extraction of topological information form a 3D object represented as a triangle-segment mesh encoded in the TS data structure. Webservice for a digital shape repository online integrated as core module in a Semantic Web system for inspecting, structuring annotating 3D shapes and scenes according to ontology-driven metadata We are extending the tool for: performing a semantic-oriented decomposition of a shape. managing large non-manifold meshes using spatial indexing techniques 20/05/10 GRAPP2010 - Geometric Modeling
  • 27. Thanks for your attention. Questions? Laura Papaleo [email_address] 20/05/10 GRAPP2010 - Geometric Modeling This work has been partially supported by the MIUR-FIRB project SHALOM under contract number RBIN04HWR8, by the National Science Foundation under grant CCF-0541032, and by the MIUR-PRIN project on Multi-resolution modeling of scalar fields and digital shapes.

Editor's Notes

  • #7: Several techniques for segmenting the boundary of a 3D manifold shape [Shamir, 2006] - survey. Such techniques try to decompose an object into meaningful components Some methods have been developed in CAD/CAM for extracting the so-called form features (protrusions, depressions), which produce a boundary-based decomposition of a 3D object guided by geometric, topological and semantic criteria, see [Shah, 1991 - for a survey]. Much less work has been done on decomposition of non-manifold shapes. A common approach to represent a non-manifold shape consists of decomposing it into manifold components (PUNTO 3) PUNTO 4 (Pesco et al., 2004) decomposition of a 2D cell complex based on a combinatorial stratification of the complex, inspired by Whitney stratification and a set of topological operators for manipulating it. In (Delfinado and Edelsbrunner, 1995) an incremental algorithm is proposed for computing the ranks of the homology groups (Betti numbers) for simplicial 3-complexes embeddable in the 3D Euclidean space. (Dey and Guha, 1998) present an approach to compute the generators of the homology groups for compacted triangulated 3-manifolds in R3. Then, they show that this approach can be applied to arbitrary simplicial complexes in R3, after thickening the complex to produce a 3-manifold homotopic to it.
  • #12: The IA data structure encodes only the vertices and the triangles of the mesh and, for each triangle, the references to its adjacent triangles. the TS encodes all vertices, and top simplexes, i.e., triangles and edges not bounding triangles, that we call wire edges. The wire-edges and triangles are defined by their bounding vertices, namely by the relations wire-edge-vertex and triangle-vertex For each edge e of a triangle t , the TS stores the triangle-triangle-at-edge relation, encoding the triangle(s) immediately preceding and succeeding t around e , when the triangles incident at e are sorted in counter-clockwise order around e . When there is no triangle adjacent to t along e , the predecessor and the successor in the triangle-triangle-at-edge relation are both t . When edge e is an interior manifold edge, the predecessor and the successor are identical and consist of the only other triangle t0 which share e with t Note that, when e is a non-manifold edge , the predecessor and the successor of t around e are two different triangles to simplify the task of navigating around a vertex, the TS encodes, for each vertex v , the vertex-triangle relation which associates with v one triangle for each 1-connected component incident at v (Fig. 5 (d)) and the vertex-wire-edge relation which associates with v all the wire edges incident at v (Fig. 5 (e)) It has been shown that the TS provides a very compact representation of the initial model [18]. A relevant property of the TS is its scalability to the manifold case and, also, it supports topological navigation in optimal time.
  • #14: Explicit information for a non-manifold shape so we extract them.. Also for structuring the shape for successive processing.
  • #19: An oriented surface OS may enclose a void. Folded surface: an OS with boundary, such that for each t-side s that belongs to S the other side s of the same triangle also belongs to S (cannot include any void). NOTE: a 1-connected component with only one oriented surface is a folded surface. If G consists of two triangulated cubes sharing a face, then there are three oriented surfaces associated. In this case, there exists exactly one oriented surface, Sout, such that the normals to the triangle sides forming it point towards the outside space. Sout defines a cycle of triangles which can be expressed as the linear combination of the other oriented surfaces associated with G. Thus, Sout does not define a 2-cycle, since it contains the remaining oriented surfaces.
  • #20: To clarify the definition of oriented surface, consider the example shown in Fig. 6(c) and an ant walking on the upper side of triangle t (that is T 1). It reaches the triangle side U 1 by crossing edge ( a,b ). It reaches the opposite side of t ( T 2) by crossing edge ( a,c ), because ( a,c ) is a boundary edge. An oriented surface is basically the surface formed by all the triangle sides that are reachable by a walking ant. An oriented surface may enclose a void. An oriented surface S with boundary, such that for each triangle side s that belongs to S the other side s of the same triangle also belongs to S , cannot include any void. We call such oriented surfaces folded surfaces . Note that a 1-connected component G may consist of only one oriented surface, and in this case it must be a folded surface. G may consist of two surfaces, as it is always the case if it contains only manifold edges. For instance, if G is a triangulated sphere, G consists of two oriented surfaces, each of which corresponding to an orientation of the surface of the sphere. If G consists of two triangulated cubes sharing a face, then there are three oriented surfaces associated with G, namely the two cubes with normals pointing towards the inside and the oriented surface consisting of the union of the two cubes with the normals pointing towards the external empty space. It can be easily seen that, if we consider G, there exists exactly one oriented surface in the set of oriented surfaces associated with G, that we denote Sout, such that the normals to the triangle sides forming it point towards the outside space. Sout defines a cycle of triangles which can be expressed as the linear combination of the other oriented surfaces associated with G. Thus, unlike the other oriented surfaces in G, Sout does not define a 2-cycle, since it contains the remaining oriented surfaces. Note that, if G consists of one folded surface, this latter does not define a 2-cycle as well. Since there is exactly one oriented surface for each 1-connected component which does not define a 2-cycle, we have that the number of 2-cycles in the model is equal to the total number of oriented surface minus the number of 1-connected components.
  • #21: If we consider all the triangle sides corresponding to the nodes in the strongly-connected component HA, they form a maximal edge-connected set of triangle sides such that any pair of triangle sides s and s霞 are connected through a path on the complex formed by edgeadjacent triangles which are consistently oriented. Thus, they form an oriented surface.