of 24

# Polygon Mesh Representation

My lecture notes for the course Geo1004 3D (2015) modelling of the built environment at TU Delft, Faculty of Architecture and the Built Environment
Published on: Mar 4, 2016
Published in: Engineering

#### Transcripts - Polygon Mesh Representation

• 1. 1Challenge the future Boundary Representations 2: Polygon Mesh Models Ir. Pirouz Nourian PhD candidate & Instructor, chair of Design Informatics, since 2010 MSc in Architecture 2009 BSc in Control Engineering 2005 Geo1004, Geomatics Master, Directed by Dr. ir. Sisi Zlatannova
• 2. 2Challenge the future • Example: • Important note: the geometry of faces is not stored; only rendered when needed! What you see on the screen is not necessarily what you store! Mesh Representation A light-weight model composed of points and a set of topological relations among them. Points >Vertices Lines > Edges Polygons > Faces Mesh T1: {0,4,3} T2:{0,1,4} Q1:{1,2,5,4}
• 3. 3Challenge the future • The geometry of a mesh can be represented by its points (known as geometrical vertices in Rhino), i.e. a list of 3D points in ℝ3 • The topology of a mesh can be represented based on its [topological] vertices, referring to a ‘set’ of 3D points in ℝ3 , there are multiple ways to describe how these vertices are spatially related (connected or adjacent) to one another and also to edges and faces of the mesh • Same topology and different geometries: Mesh Mesh Geometry versus Mesh Topology T1: {0,4,3} T2:{0,1,4} Q1:{1,2,5,4} T1 T2 Q1 T1 T2 Q1 0 3 1 4 5 2 0 3 1 4 5 2
• 4. 4Challenge the future • formally an ordered set of Vertices, Edges and Faces or 𝑀 = (𝑉, 𝐸, 𝐹) • The ordered set describes a set of vertices and a set of faces describing how the vertices construct convex polygons by the set of edges connecting them when embedded in ℝ3 . (In a set there is no duplicate element. So, the vertices, edges and faces in the above definition are unique in their sets and have no duplicates.) • Edges and faces should not intersect or self-intersect. • Edges correspond to straight lines, faces are generators of convex and planar polygons. A mesh represents a polyhedron if it has planar faces without self-intersection. • Mesh has a topological structure, in which edges are tuples of vertex indices and faces are composed of (CW/CCW ordered) tuples of integers referring to indices of the vertices or edges • Ensuring flatness of faces is most convenient with triangular faces. This is one of many reasons that triangular meshes are most common and used for rendering engines. • Faces or edges should not be degenerate; e.g. an edge that effectively corresponds to a line of length zero, or a face giving rise to a polygon that has zero surface area. Faces (polygons) should not be self intersecting; edges should not self- intersect either. Proper Mesh A mesh that does not need to be corrected!
• 5. 5Challenge the future Mesh Basics Some preliminary definitions: fan, star, strip A triangle strip=:ABCDEF  ABC, CBD, CDE, and EDF A B C D E F A Closed Triangle Fan or a ‘star’=:ABCDEF A B C D E F  ABC, ACD, ADE, and AEF A Triangle Fan=: ABCDE AB C D E  ABC, ACD, and ADE
• 6. 6Challenge the future Mesh Basics Some preliminary definitions: free* vertices, free* edges If an edge has less than two faces adjacent to it then it is considered free ; if a vertex is part of such an edge it is considered as free too. * In Rhinocommon free vertices/edges are referred to as naked.
• 7. 7Challenge the future Images courtesy of Dr. Ching-Kuang Shene from Michigan Technological University • if a mesh is supposed to be a 2D manifold then it should meet these criteria: 1. each edge is incident to only one or two faces; and 2. the faces incident to a vertex form a closed or an open fan. Non manifold mesh examples: (note why!) Proper Mesh A mesh that does not need to be corrected!? • if a mesh is supposed to be orientable then, it should be possible to find ‘compatible’ orientations for any two adjacent faces; in which, for each pair of adjacent faces, the common edge of the two faces has opposite orders. • Example: Möbius band is a 2D manifold mesh that is not orientable.
• 8. 8Challenge the future Mesh Basics Some preliminary definitions: boundary denoted as 𝜹 • The boundary is the set of edges incident to only one face of a manifold. Therefore: we can conceptualize the boundary as the union of all faces of a manifold. We can conclude that: • If every vertex has a closed fan (or there is no edge of valence less than 2), the given manifold has no boundary. Example: a box! non-manifold boundary manifold boundaryno boundary
• 9. 9Challenge the future Image Source: http://prateekvjoshi.com/2014/11/16/homomorphism-vs homeomorphism/ Mesh Topology: Homeomorphism clay models that are all topologically equal!? Images courtesy of Dr. Ching-Kuang Shene from Michigan Technological University Two 2-manifold meshes A and B are homeomorphic if their surfaces can be transformed to one another by topological transformations (bending, twisting, stretching, scaling, etc.) without cutting and gluing.
• 10. 10Challenge the future Mesh Topology: Homeomorphism Euler-Poincare Characteristic: key to homeomorphism Images courtesy of Dr. Ching-Kuang Shene from Michigan Technological University 𝜒 𝑀 = 𝑉 − 𝐸 + 𝐹 = 2 1 − 𝑔 − 𝛿 • 𝛿 is the number of boundaries • 𝑔 is the number of “genera” (pl. of genus) or holes • Irrespective of tessellation! 𝜒 𝑀 = 𝑉 − 𝐸 + 𝐹 = 2 1 − 2 − 0 = −2
• 11. 11Challenge the future Mesh Topology: Homeomorphism Euler-Poincare Characteristic: key to homeomorphism • N-Manifold/Non-Manifold: Each point of an n-dimensional manifold has a neighborhood that is homeomorphic to the Euclidean space of n-dimension • Riddle: The above definition implies that for mapping some local features 2D maps are fine. What about the whole globe? That is not homoeomorphic to a rectangular surface! How do we do it then?
• 12. 12Challenge the future Quiz: Check Euler-Poincare Characteristic on two spherical meshes • Question: we know that the Euler-Poincare Characteristic is independent of tessellation; check this fact on the two spheres below; explain the discrepancy. Hints: http://4.rhino3d.com/5/rhinocommon/ look at mesh [class] members 𝜒 𝑀 = 2𝜒 𝑀 = 66!?
• 13. 13Challenge the future Mesh Geometry • Polygon vs Face • Triangulate • Quadrangulate
• 14. 14Challenge the future Mesh Geometry • Boolean operation on meshes: 1. 𝐴 ∪ 𝐵: Boolean Union 2. 𝐴 − 𝐵: Boolean Difference 3. 𝐴 ∩ 𝐵: Boolean Intersection • why do they fail sometimes?
• 15. 15Challenge the future Mesh Topological Structure • Mesh Topological Data Models: Face-Vertex: e.g. 𝐹0 = {𝑉0, 𝑉5, 𝑉4} & 𝑉0 ∈ 𝐹0, 𝐹1, 𝐹12, 𝐹15, 𝐹7 Images courtesy of David Dorfman, from Wikipedia Face-Vertex (as implemented in Rhinoceros)
• 16. 16Challenge the future Vertex-Vertex: e.g. 𝑉0~{𝑉1, 𝑉4, 𝑉3} Face-Vertex: e.g. 𝐹0 = 𝑉0, 𝑉5, 𝑉4 , 𝑉0 ∈ 𝐹0, 𝐹1, 𝐹12, 𝐹15, 𝐹7 Winged-Edge: e.g. 𝐹0 = 𝐸4, 𝐸8, 𝐸9 , 𝐸0 = 𝑉0, 𝑉1 , 𝐸0~ 𝐹1, 𝐹12 , 𝐸0~ 𝐸9, 𝐸23, 𝐸10, 𝐸20 Half-Edge: each half edge has a twin edge in opposite direction, a previous and a next Mesh Topological Structures Image courtesy of David Dorfman, from Wikipedia What is explicitly stored as topology of a mesh: E.g. Face-Vertex (as implemented in Rhinoceros) http://doc.cgal.org/latest/HalfedgeDS/index.html
• 17. 17Challenge the future Mesh Topological Structure • Mesh Topological Data Models: Face-Vertex Example: http://4.rhino3d.com/5/rhinocommon/html/AllMembers_T_Rhino_Geometry_Collections_MeshTopologyVertexList.htm Face-Vertex (as implemented in Rhinoceros) Name Description ConnectedFaces Gets all faces that are connected to a given vertex. ConnectedTopologyVertices(Int32) Gets all topological vertices that are connected to a given vertex. ConnectedTopologyVertices(Int32, Boolean) Gets all topological vertices that are connected to a given vertex. The MeshTopologyVertexList type exposes the following members. Half-Edge: Half-Edge Mesh Data Structure, example implementation by Daniel Piker: http://www.grasshopper3d.com/group/plankton
• 18. 18Challenge the future Repairing/Reconstructing Geometry • Example: Coons’ Patch • Code it and get bonus points! Image courtesy of CVG Lab
• 19. 19Challenge the future Mesh Smoothing • For k As Integer=0 To L - 1 Dim SmoothV As New List(Of Point3d) For i As Integer=0 To M.Vertices.Count - 1 Dim Ngh = Neighbors(M, i) Dim NVertex As New Point3d(0, 0, 0) For Each neighbor As point3d In Ngh NVertex = NVertex + neighbor Next NVertex = (1 / Ngh.Count) * NVertex SmoothV.Add(NVertex) Next M.Vertices.Clear M.Vertices.AddVertices(SmoothV) A = M Next
• 20. 20Challenge the future Normal Vectors of a Mesh • Topological Vertices versus Geometrical Points • Joining mesh objects: What is a mesh box? • Welding Meshes: how does it work? • Face Normal versus Vertex Normal Where do they come from and what do they represent?
• 21. 21Challenge the future How to Compute Mesh Normals? • 00, 00 ),( vvuuv p u p vun              1 ( ) ( ) 0 ( )( ) N x i next i i next i i N y y z z      1 ( ) ( ) 0 ( )( ) N z i next i i next i i N x x y y      1 ( ) ( ) 0 ( )( ) N y i next i i next i i N z z x x      Martin Newell at Utah (remember the teapot?) Why?
• 22. 22Challenge the future (2D Curvature Analysis: Mesh) • Discretization Mesh • Measurement At vertices • Attribution To vertices Curvature Estimation on Meshes?
• 23. 23Challenge the future Curvature Estimation on Meshes • What was the definition of curvature? • Change of tangents or change of normals? • How to measure change of normals? • ProVec = vec - (vec * M.Normals(i)) * M.Normals(i) • Projected_Vector=Vector-(Vector.Normal).Normal Why? • Maximum & Minimum change • Estimation of Gaussian & Mean curvature on mesh vertices
• 24. 24Challenge the future Questions? p.nourian@tudelft.nl