# Connectivity of Triangle Meshes Introduction Triangle meshes Jarek Rossignac GVU Center and College of Computing Georgia Tech, Atlanta http://www.gvu.gatech.edu/~jarek Jarek Rossignac, GVU Center, Georgia Tech 1: T-meshes 3D Compression, SM02 1 Popular domain Surfaces decomposed into simple manifolds (with boundary) Pseudo-manifold Faces (flat or curved) Represent each manifold surface as a triangle mesh T-meshes are supported by optimized rendering systems Easily derived from polygons and parametric surfaces Jarek Rossignac, GVU Center, Georgia Tech 1: T-meshes 3D Compression, SM02 2 Focus on explicit representations Samples: Location and attributes (color, mass) Connectivity: Triangle/vertex incidence

Fit: Rule for bending triangles (subdivision surfaces, NURBS) Samples (vertices): vertex 1 x y z c vertex 2 x y z c vertex 3 x y z c V(3B+k) bits Triangle/vertex incidence: v4 Triangle 1 Triangle 2 Triangle 3 Triangle 4 T = 2V Jarek Rossignac, GVU Center, Georgia Tech Triangle 5 V(6log2V) bits Triangle 6 1: T-meshes 1 3 4 7 6 8

2 3 24 5 2 56 5 8 51 t3 v5 v2 3D Compression, SM02 3 Samples, connectivity, & attributes Samples (vertices) Location (x,y,z) Connectivity (triangles) Define how surface interpolates samples Specifies surface as a set of triangles Associates each triangle with 3 samples (called corners) Define how to interpolate corner attributes over triangle Attributes (parameters for color and texture calculations) One per corner of each triangle Could be the same for all 3 corners (flat triangle) Could be the same for two adjacent corners (smooth edge)

Could be the same for all coincident corners (smooth surface) Linear interpolation of shape and attributes over triangle Jarek Rossignac, GVU Center, Georgia Tech 1: T-meshes 3D Compression, SM02 4 Terminology vertex Vertex: corner Location of a sample triangle Triangles: Decompose approximating surface Edge: Bounds one or more triangles Joins two vertices border edge Corner: Abstract association of a triangle with a vertex

May have its own attributes (not shared by corners with same vertex) Used to capture surface discontinuities Border (half-edge, dart): Association of a triangles with a bounding edge. Defines an orientation of the border A triangle has 3 borders and 3 corners Jarek Rossignac, GVU Center, Georgia Tech 1: T-meshes 3D Compression, SM02 5 Representation as independent triangles For each triangle: For each one of its 3 corners, store: Location Attributes (may be the same for neighboring corners) Each vertex location is repeated (6 times on average) geometry = 36 B/T (float coordinates: 9x4 B/T) Plus 3 attribute-sets per triangle (6 per vertex) vertex 1 vertex 2 vertex 3 Triangle 1 Triangle 2 Triangle 3 xyzxyzxyz xyzxyzxyz xyzxyzxyz

Very verbose! Not good for traversal. Jarek Rossignac, GVU Center, Georgia Tech 1: T-meshes 3D Compression, SM02 6 Connectivity = Incidence + adjacency Triangle/vertex incidence (corner) Associates each triangle with 3 vertices Defines Corners Triangle/triangle adjacency Associates triangle with neighboring triangles Neighboring triangles share a common edge Is completely defined by incidence! Convenient to accelerate traversal of triangulated surface Walk from one triangle to an adjacent one (visit them all once) Used to build triangle strips Used to estimate surface normals at vertices Used to compress triangulated surfaces Triangle/edge incidence (border) Associates triangles with their bounding edges Jarek Rossignac, GVU Center, Georgia Tech

1: T-meshes 3D Compression, SM02 7 Triangle orientation Orient the plane supporting a triangle Pick one of 2 possible orientations for the normal List corners in counter clockwise order Cyclic order (equivalence under cyclic permutation) Orientation compatibility for adjacent triangles Common corners follow each other in reverse order Can try to propagate consistent orientation Pick orientation for first triangle Propagate to neighbors (edge-connected), needs not use geometry What if more than two triangles share same edge? Orientable set of triangles Can all triangles be oriented to be consistent with their neighbors? Only if the mesh is orientable Jarek Rossignac, GVU Center, Georgia Tech 1: T-meshes 3D Compression, SM02 8 Incidence table Integer Ids for vertices (0, 1, 2 V-1) & triangles (0, 1, 2T-1) Triangle orientation: cyclic order in which corners are listed

2 Other connectivity info may be derived Borders: defined by 3 pairs of corners for each triangle Edges: Set of borders with same two vertices Adjacency: Triangles incident upon the same edge Incidence graph representation: List of corners (id for vertex & attribute) Corners of each triangle are consecutive Samples defined separately: List of vertex locations (x,y,z) List of attributes (color,normal, texture) Not practical for traversing mesh Jarek Rossignac, GVU Center, Georgia Tech 1: T-meshes va Triangle 0 1 a Triangle 0 2 b Triangle 0 3 c 3 4 1 vertex 1 x y z vertex 2 x y z vertex 3 x y z

vertex 4 x y z Triangle 1 2 c Triangle 1 1 d Triangle 1 4 e Triangle 2 1 a attribute a red attribute b blue 3D Compression, SM02 9 T-meshes: manifold connectivity graph T-mesh = triangle set with a manifold connectivity graph The corners of each triangle refer to different vertices Each edge has exactly two incident triangles Manifold vertices: The star of each vertex is connected Star = union of edges and triangles incident upon the vertex Triangles form a surface that may be globally oriented All triangle orientations are consistent (No Klein bottle) All triangles form a connected set All pairs of triangles are connected Two adjacent triangles are connected Connectivity is a transitive relation Jarek Rossignac, GVU Center, Georgia Tech 1: T-meshes 3D Compression, SM02 10 Connectivity/geometry discrepancy

Connectivity of T-mesh may conflict with actual geometry Vertices with different names may be coincident Edges with different names may be coincident Triangles, edges, and vertices may intersect T-mesh with consistent geometry Triangles, edges, vertices are pairwise disjoint We consider edges and triangles to be open I.e., not containing their boundary Manifold graphs may be used with invalid geometry Coincident edges and vertices: Non-manifold singularities Self-intersecting surfaces Manifold graph Non-manifold shape Jarek Rossignac, GVU Center, Georgia Tech 1: T-meshes 3D Compression, SM02 11 Handles in T-meshes Handles correspond to through-holes A sphere has zero handles, a torus has one The number of handles is well defined in a T-mesh A handle cannot be identified as a particular set of triangles An edge-loop is a cycle of oriented edges

Each starts where the previous one ended, no repetition of vertices A T-mesh has k handles if and only if you can remove at most 2k edge-loops without disconnecting the mesh connected The genus of a T-mesh is the number of handles it has Jarek Rossignac, GVU Center, Georgia Tech 1: T-meshes 3D Compression, SM02 12 Simple T-meshes (STM) and T-patches We first look at simple meshes (no handles) Homeomorphic to a sphere Incidence graph is a planar triangle graph We will also use the notion of a T-patch Connected portion of an STM Bounded by a single edge-loop Jarek Rossignac, GVU Center, Georgia Tech 1: T-meshes 3D Compression, SM02 13 Simple mesh A simple mesh is homeomorphic to a triangulated sphere

Orientable Manifold No boundary (no holes) No handles (no throu-holes) Properties Each edge has exactly 2 incident triangles Each vertex has a single cycle of incident triangles May be drawn as a planar graph Jarek Rossignac, GVU Center, Georgia Tech 1: T-meshes 3D Compression, SM02 14 Dual graphs and spanning trees From Bosen Dual graph: Nodes represent triangles Links represent edges Join centers of adjacent triangles Vertex spanning tree (VST) Edge-set connecting all vertices No cycles Cuts mesh into simply connected polygon with no interior vertices

Triangle-spanning tree (TST) Graph of remaining vertices No loops Connects all triangles Jarek Rossignac, GVU Center, Georgia Tech 1: T-meshes 3D Compression, SM02 15 Euler formula for Simple Meshes Mesh has V vertices, E edges, and T triangles E = (V-1)+(T-1) VST has V nodes and thus V-1 links TST has T nodes and thus T-1 links E = 3T/2 There are 3 borders (edge-uses) per triangle There are twice more edge-uses then edges T=2V-4 Because (V-1)+(T-1) = 3T/2 And hence V-2 = 3T/2-T = T/2 There are twice more triangles than vertices The number C of corners (vertex-uses) is about 6V C=3T=6V-12 On average, a vertex is used 6 times

Jarek Rossignac, GVU Center, Georgia Tech 1: T-meshes 3D Compression, SM02 16 Properties of manifold meshes T triangles, E edges, V vertices, H handles, S shells Euler: T-E+V=2S -2H Example: a tetrahedron has T=4, E=6, V=4, S=1, H=04-6+4=2-0 Number of handles: H=S-(T-E+V)/2 Shared edges: E=3T/2 3 borders per triangle, 2 borders per edge Twice more triangles than vertices: T=2V+4(H-S) T-3T/2+V=2S-2H Assume H and S are much smaller than V Add 1 vertex, 2 triangles, and 3 edges vertices triangles edges Three times more edges than vertices: E=3V-6+6H 2E/3-E+V=2-2H Jarek Rossignac, GVU Center, Georgia Tech 1: T-meshes

3D Compression, SM02 17 Corner table:data structure for T-meshes c.v Table of corners, for each corner c store: c.v : integer reference to vertex table c.o : integer reference to opposite corner c.a : index to table of corner attributes c c.n Make the corners of each triangle consecutive c.o List them according to consistent orientation of triangles Can retrieve triangle number: c.t = c DIV 3 Can retrieve next corner around triangle: c.n = 3t + (c+1)MOD 3 voa Triangle 0 corner 2 3 5 c Triangle 1 corner 3 2 9 c Triangle 1 corner 4 1 6 d Triangle 1 corner 5 4 c.t 2

Triangle 0 corner 0 1 7 a Triangle 0 corner 1 2 8 b c.n.n 3 2 1 3 0 4 1 5 4 vertex 1 x y z attribute a red vertex 2 x y z attribute b blue vertex 3 x y z vertex 4 x y z

2 e Jarek Rossignac, GVU Center, Georgia Tech 1: T-meshes 3D Compression, SM02 18 Computing adjacency from incidence c.o can be derived from c.v (needs not be transmitted): Build table of triplets {min(c.n.v, c.n.n.v), max(c.n.v, c.n.n.v), c} voa 230, 131, 122, 143, 244, 125, 3 2 2 Triangle 1 corner 0 1 a 1 3 Triangle 1 corner 1 2 b Triangle 1 corner 2 3 c

Triangle 2 corner 3 2 c Triangle 2 corner 4 1 d Triangle 2 corner 5 4 e 0 Sort: 4 5 4 122, 125 ...131... 143 ...230...244 1 Pair-up consecutive entries 2k and 2k+1 voa (122, 125)...131... 143...230...244 Their corners are opposite

(122,125)...131...143...230...244 3 2 2 1 3 0 4 1 Jarek Rossignac, GVU Center, Georgia Tech 1: T-meshes 5 4 Triangle 1 corner 0 1 a Triangle 1 corner 1 2 b Triangle 1 corner 2 3 5 c Triangle 2 corner 3 2

c Triangle 2 corner 4 1 d Triangle 2 corner 5 4 2 e 3D Compression, SM02 19 Accessing left and right neighbors Can identify opposite corners of right and left neighbors c.r = c.n.o c.l = c.n.n.o c.v c.l = c.n.n.o c c.r = c.n.o c.p=c.n.n c.n c.o Jarek Rossignac, GVU Center, Georgia Tech 1: T-meshes

3D Compression, SM02 20 Using adjacency table for T-mesh traversal Visit T-mesh (triangle-spanning tree) Mark triangles as you visit Start with any corner c and call Visit(c) Visit(c) mark c.t; IF NOT marked(c.r.t) THEN visit(c.r); IF NOT marked(c.l.t) THEN visit(c.l); Label vertices Label vertices with consecutive integers Label(c.n.v); Label(c.n.n.v); Visit(c); Visit(c) IF NOT labeled(c.v) THEN Label(c.v); mark c.t; IF NOT marked(c.r.t) THEN visit(c.r); IF NOT marked(c.l.t) THEN visit(c.l); Jarek Rossignac, GVU Center, Georgia Tech 1: T-meshes 3D Compression, SM02 21

Summary Samples+incidence graph define triangles and corners (c.v) Attributes attached to corners (may be same for neighbors) T-mesh: oriented manifold incidence (consistent geometry?) Adjacency (c.o) supports T-mesh traversal (derived from c.v) Simple meshes, T=2V-4, H=0, S=1 Jarek Rossignac, GVU Center, Georgia Tech 1: T-meshes 3D Compression, SM02 22