Report

Mesh Representation, part II based on: Data Structures for Graphics, chapter 12 in Fundamentals of Computer Graphics, 3rd ed. (Shirley & Marschner) Slides by Marc van Kreveld 1 3D objects facets edges vertices 2 3D objects • We typically represent the boundary; the interior is implied to be the bounded subspace • We will assume linear boundaries here, so we have facets, edges, and vertices (and the interior) 3 Triangle meshes • Many freeform shapes consist of (many) triangles 4 Triangle meshes • How are triangles, edges, and vertices allowed to connect? • How do we represent (store) triangle meshes? • How efficient are such schemes? Separate triangle mesh Indexed triangle mesh Triangle neighbor structure Winged-edge structure 5 Winged-edge structure • Stores connectivity at edges instead of vertices • For one edge, say, e1: – Two vertices are important: v4 and v6 – Two triangles are important: T5 and T6 – Four edges are important: e2, e14, e5, and e8 e7 e3 e11 e8 e12 e14 e9 e4 v6 e2 e13 e1 e5 e6 v1 e10 v2 T2 T1 T v5 5 T3 T4 v3 v7 T6 T7 v4 v8 6 Winged-edge structure • Give e1 a direction, then – v4 is the tail and v6 is the head – T5 is to the left and T6 is to the right – e2 is previous on the left side, e14 is next on the left side, e5 is previous on the right side, and e8 is next on the right side e7 e3 e11 e8 e12 e14 e9 e4 v6 e2 e13 e1 e5 e6 v1 e10 v2 T2 T1 T v5 5 T3 T4 v3 v7 T6 T7 v4 v8 7 Winged-edge structure • Give e1 a direction, then – v4 is the tail and v6 is the head – T5 is to the left and T6 is to the right – e2 is previous on the left side, e14 is next on the left side, e5 is previous on the right side, and e8 is next on the right side head v6 rnext e8 e14 lnext T6 right e1 T5 left e5 rprev e2 lprev v4 8 tail Winged-edge structure Edge { Edge lprev, lnext, rprev, rnext; Vertex head, tail; Triangle left, right } Vertex { double x, y, z; Edge e; // any incident } Triangle { Edge e; // any incident } head lnext rnext right left rprev lprev tail 9 Winged-edge structure • Also works for meshes that do not only use triangles – There is still one head and one tail – There is still one left face and one right face – There are still previous and next edges in the left face and in the right face: e13, e7, e6, and e8 e7 e3 e11 e8 e12 e4 e1 e13 e10 e6 Note: The triangle neighbor structure does not generalize 10 Winged-edge structure • It also works for planar subdivisions like country maps 11 Winged-edge structure Edge { Edge lprev, lnext, rprev, rnext; Vertex head, tail; Face left, right } Vertex { double x, y; Edge e; // any incident } Face { Edge e; } e7 e3 e11 e8 e12 e4 e1 e13 e10 e6 // any incident 12 Winged-edge structure, storage • A triangular mesh with nv vertices has 3nv edges and 2nv triangles • A vertex needs 3(4) units of storage (with z coord.) • An edge needs 8 units of storage • A triangle needs 1 unit of storage 3(4) + 38 + 21 = 29(30) nv units of storage 13 Winged-edge structure • However, the arbitrary orientation of edges makes traversal of the boundary of a face awkward e7 e3 e11 e12 With consistent orientations, we could report the vertices of a face iteratively: e8 F5 e4 e13 e5 e1 e10 x e6 e2 while ( e estart ) { e = e.lnext; report e.tail.coordinates; } But consistent orientations 14 usually do not exist Winged-edge structure while ( e estart ) { if (forward) { report e.tail.coordinates; enew = e.lnext; if (enew.head == e.head) forward = false; } else { report e.head.coordinates; enew = e.rprev; if (enew.tail == e.tail) forward = true; } e = enew; } enew face e enew face e 15 Half-edge structure • A.k.a. doubly-connected edge list, DCEL • Allows the purely forward traversal of the boundary of a face • Every edge is represented as two half-edges (split lengthwise!) 16 Half-edge structure • A consistent orientation around every face now works! • Every half-edge is incident only to the face to its left (by convention) then every face has its half-edges oriented counterclockwise 17 Half-edge structure HEdge { HEdge next, pair; Vertex head; Face f; } head next pair f Vertex { double x, y; HEdge h; // any incident half-edge // pointing to this vertex } Face { HEdge h; // any incident half-edge in its boundary } 18 Half-edge structure • A half-edge h can find its tail as h.pair.head • A half-edge h can find the other face incident to the edge it is part of as h.pair.f head next pair f • A half-edge cannot find its prev easily (prev is the opposite of next); it is a design choice to include an extra prev in HEdge or not 19 Half-edge structure, storage • A triangular mesh with nv vertices has 3nv edges and 2nv triangles • A vertex needs 3(4) units of storage (with z coord.) • A half-edge needs 4 units of storage • A triangle needs 1 unit of storage 3(4) + 324 + 21 = 29(30) nv units of storage 20 Half-edge structure, storage • A half-edge needs 5 units of storage when prev is also stored 3(4) + 325 + 21 = 35(36) nv units of storage 21 Half-edge structure, storage • For country maps instead of triangular meshes, a map with nv vertices has nv edges and << nv faces 3 + 25 + 1 = 14 nv units of storage 22 Half-edge structure, storage • For country maps instead of triangular meshes, a map with nv vertices has nv edges and << nv faces • In GIS, the long sequences of degree-2 vertices (chains) defining the shape of a border are stored differently, with the vertices in an array, so no next and prev are needed • We can define half-chains • The whole half-chain has the same left face • Each half-chain has a next half-chain, a prev half-chain, and a pair half-chain 23 Half-edge structure • Planar subdivisions have much fewer faces and halfchains than the total number of vertices and edges 24 Half-edge structure 25 Half-edge structure • Planar subdivisions may have “islands/holes” in faces: faces from which pieces are excluded • In this case the graph of vertices and edges is not a connected graph f 26 Half-edge structure • Faces with holes are common in 3D CAD/CAM models too 27 Half-edge structure for subdivisions with holes HEdge { HEdge next, pair; Vertex head; Face f; } Vertex { double x, y, x; HEdge h; // any incident half-edge // pointing to this vertex } Face { HEdge h; // any incident half-edge in its boundary HEdge inner[k]; // for each hole, any incident half-edge; // allows up to k holes in the face } 28 Half-edge structure for subdivisions with holes f.inner[0] f f.inner[1] f.h 29 Half-edge structure for subdivisions with holes • Every bounded face has exactly one counterclockwise cycle of half-edges bounding it from the outside, and zero or more clockwise cycles of half-edges bounding that face from the inside (holes) • The structure also works for any planar straight-line graph (PSLG), with possibly: – dangling edges or other dangling structures – loose edges 30 Planar versus non-planar • None of the structures allow edge-crossings, as faces would not be well-defined, and points can lie in multiple faces at once 31 3D meshes • So far, we can represent 2D subdivisions and boundaries of 3D solids, but not 3D subdivisions 32 3D tetrahedral meshes • The 3D version of a triangle is a tetrahedron • The 3D version of a triangular mesh is a tetrahedral mesh (and triangulation vs. tetrahedralization) 33 3D tetrahedral meshes • A 3D tetrahedral mesh has the following features: – – – – vertices edges triangles tetrahedra (0-dimensional) (1-dimensional) (2-dimensional) (3-dimensional) 34 3D tetrahedral meshes • In a proper 3D tetrahedral mesh: – – – – – – Every vertex is endpoint of some edge For every edge, both endpoints are vertices of the mesh Every edge is a side of some triangle For every triangle, its three sides are edges of the mesh Every triangle is a facet of some tetrahedron For every tetrahedron, its four facets are triangles of the mesh – If edges, vertices, and tetrahedra are considered to be open, then no two features of the mesh intersect 35 3D tetrahedral meshes • Every polygon can be converted into a triangular mesh without needing extra vertices, but polyhedra exist that cannot be converted into a tetrahedral mesh without extra edges and vertices Schönhardt polyhedron 36 3D tetrahedral meshes • Representation of 3D tetrahedral meshes: – Indexed tetrahedron mesh: classes for vertex and tetrahedron; a tetrahedron can access its four vertices – Tetrahedron neighbor structure: classes for vertex and tetrahedron; a tetrahedron can access its four vertices and its (up to) four neighbor tetrahedra – Simplices structure: classes for vertex, edge, triangle, and tetrahedron 37 Simplices structure • A k-simplex is the convex hull defined by k+1 points that do not lie in any single (k-1)-dim. linear variety • Equivalent: the k+1 points p0, ..., pk are such that the vectors p0p1, p0p2, ..., p0pk are linearly independent – – – – – 0-simplex: point / vertex 1-simplex: line segment / edge 2-simplex: triangle 3-simplex: tetrahedron 4-simplex: convex hull of 5 non-co-hyperplanar points in 4-space 38 Simplices structure • A vertex has access to one incident edge • An edge has access to its vertices and one incident triangle vertex • A triangle has access to both some its three edges and both edge incident tetrahedra some all 3 • A tetrahedron has access triangle to its four triangles both all 4 tetrahedron 39 Simplices structure • Can also be used for 4D and even higher-D • 4D can be space-time for changing objects • Higher-D can be the space of location and orientation of a rigid 3D object (6D) 40 Simplices structure • Always: k-simplices have access to (k-1)-simplices and (k+1)-simplices 0-dim both some 1-dim some all 3 some all d (d-1)-dim both all d+1 d-dim 41 Quadrilateral meshes 42 Quadrilateral meshes 43 Not every subdivision with triangular faces is a triangular mesh 44 Meshes have multi-resolution possibilities 45 Representation of 3D models: summary • Boundary or solid model representation • Triangle mesh, quadrilateral mesh, general faces • Meshes that store incidence/adjacency of features allow traversal on the mesh faster (local) operations • Triangle strips may be useful for transmitting meshes • Higher-dimensional mesh representations exist as well 46 Questions 1. Write code to report all vertices adjacent to a given vertex v in a half-edge structure for a triangular mesh. Is your solution clockwise or counter-clockwise? Now do it the other way around 2. Do the same for general subdivisions, clockwise and counterclockwise 3. Write code to report all vertices in the boundary of a face that may have holes and is given in a half-edge structure 4. How do you access the four 3-simplices adjacent to a given 3-simplex in a simplices structure in 3D? 5. How many units of storage are needed in the different structures for tetrahedrilization? 47