# Meshes: vertices, indices, and the invariants that matter A **mesh** is the geometry an object is made of. In practice that means two arrays, plus a set of invariants which, when violated, produce the rendering faults this chapter names. ```{index} single: mesh single: indexed triangle mesh single: vertex; shared ``` ## The indexed triangle mesh A vertex array holds each distinct position once. An index array names three vertices per triangle. A cube of side 2: ```perl # Winding is counter-clockwise seen from OUTSIDE, OpenGL's GL_CCW # default. Every triangle in the mesh must agree on this. my @vert = ( [-1,-1,-1], [ 1,-1,-1], [ 1, 1,-1], [-1, 1,-1], # 0..3 back (z=-1) [-1,-1, 1], [ 1,-1, 1], [ 1, 1, 1], [-1, 1, 1], # 4..7 front (z=+1) ); my @idx = ( 4,5,6, 4,6,7, # front (+z) 1,0,3, 1,3,2, # back (-z) 0,4,7, 0,7,3, # left (-x) 5,1,2, 5,2,6, # right (+x) 3,7,6, 3,6,2, # top (+y) 0,1,5, 0,5,4, # bottom (-y) ); ``` ```text vertices stored: 8 triangles: 12 indices: 36 expanded (no index buffer) would store 36 vertices position data: 60 floats indexed, 108 floats expanded ``` Indexing is not only about size. A shared vertex is shared: move it once and every triangle using it follows, which is what makes editing tractable. It also lets the GPU cache transformed vertices instead of transforming the same corner five times. CCW-from-outside is consistent with the [rasteriser](software-rasteriser): a counter-clockwise triangle in a right-handed space projects to a clockwise triangle on a y-down screen, which is the positive `edge` area that chapter treated as front-facing. ```{index} single: winding order; consistency check single: signed volume ``` ## Invariant 1: consistent winding Every triangle must wind the same way seen from outside. The check is the **signed volume**, which for a closed mesh is the sum over triangles of one sixth of `dot(a, cross(b, c))`: ```perl sub signed_volume { # Requires a CLOSED mesh. On an open surface the result is # meaningless rather than merely wrong. my ($v, $i) = @_; my $vol = 0; for (my $k = 0; $k < @$i; $k += 3) { my ($a, $b, $c) = @{$v}[ @{$i}[$k, $k+1, $k+2] ]; $vol += v_dot($a, v_cross($b, $c)) / 6; } return $vol; } ``` ```text signed volume = 8.0 side 2 cube, so 8 means every face is outward one triangle reversed: 6.6667 ``` A side-2 cube has volume 8, and the test returns exactly that. Reverse one triangle and it returns 6.6667: that triangle now subtracts its contribution instead of adding it. A negative total means the whole mesh is inside out. **Symptom: a model renders with holes in it, and the holes move as the camera orbits.** Cause: inconsistent winding. The holes are triangles being back-face culled that should not have been. ```{index} single: manifold mesh single: mesh; holes single: directed edge ``` ## Invariant 2: the mesh is manifold In a closed mesh, every **undirected** edge is shared by exactly two triangles, and every **directed** edge occurs exactly once. The second half is the winding check again, expressed combinatorially: two adjacent triangles traverse their shared edge in opposite directions, so a directed edge appearing twice means two neighbours disagree. ```text undirected edges: 18, each shared by exactly 2 faces: yes directed edges occurring twice (a winding error): 0 same test on the mesh with one triangle reversed: 3 duplicate directed edges ``` Both faults are worth testing for on any mesh you load or generate: - An undirected edge used **once** means the surface has a hole. - Used **more than twice** means it is non-manifold, and operations like boolean subtraction and subdivision have no defined answer there. - A duplicated **directed** edge means inconsistent winding, exactly the three the reversed triangle produced above. ```{index} single: normal; averaging single: normal; area and angle weighting ``` ## Normals, and the trap in averaging them A face normal is the cross product of two edges. Per-vertex normals come from averaging the normals of the faces meeting at that vertex, which is what makes a faceted surface shade smoothly. The naive average is weighted by **triangle count**, and that is rarely what you want: ```text vertex 6 at [1, 1, 1] -> normal [0.333, 0.667, 0.667] ``` The corner of a cube should point equally along all three axes, at `[0.577, 0.577, 0.577]`. It does not, because the six quads were each split into two triangles and that split is not symmetric about the corner: two triangles of the front face touch vertex 6, two of the top face, but only one of the right face. The average comes out `[1, 2, 2]` normalised. Fixes, in increasing order of correctness: weight each face normal by its **area**, or by the **angle** the face subtends at that vertex. Angle weighting is the one that survives retriangulation, because the angles at a corner do not change when you split a quad differently. **Symptom: a smooth-shaded model has a subtle lighting seam along an edge where nothing else is wrong.** Cause: unweighted normal averaging across a region that was triangulated asymmetrically. ```{index} single: vertex; attributes single: hard edge single: UV seam ``` ## When one position needs several vertices Averaging normals is right for a curved surface and wrong for a cube. A cube should look faceted, which means each corner needs a **different** normal per face it belongs to. A vertex is not a position; it is a position **plus its attributes**, and two triangles can share a position while disagreeing about the normal there. So a smooth-shaded cube has 8 vertices, and a correctly faceted one has 24: each of the 8 corners duplicated once per adjoining face. The same applies to UV coordinates. A **UV seam**, where the texture is cut to be unwrapped flat, forces duplicated positions along the cut, because one position needs two different UVs. **Symptom: an exported model has far more vertices than its corners suggest.** Usually not a bug: hard edges and UV seams both split vertices, and a cube legitimately arrives as 24. ```{index} single: bounding volume single: axis-aligned bounding box single: AABB single: bounding sphere ``` ## Bounding volumes Cheap approximations used to reject work early: a ray that misses the box cannot hit any triangle in it. ```text AABB min [-1, -1, -1] max [ 1, 1, 1] sphere centre [ 0, 0, 0] radius 1.7321 ``` An **axis-aligned bounding box** is two corners, trivially computed, and tests fast. A **bounding sphere** is a centre and a radius, invariant under rotation, so it does not need recomputing when the object turns. The cube's radius is the half-diagonal, `sqrt(3)`. Both are used by the culling and ray tests later in this guide, and they are the leaves of the BVH the scene-graph chapter builds. ```{index} single: welding single: vertex; welding ``` ## Welding Geometry from a file or a generator often repeats positions that should be shared. Welding collapses them by exact or tolerance match: ```perl # Exact match on a rounded key. A tolerance-based weld needs a spatial # hash, not a string key, or it is quadratic. my $key = join ",", map { sprintf "%.6f", $_ } @$v; ``` ```text raw vertices 6 -> welded 4, indices [0,1,2,1,3,2] ``` Two triangles authored as six independent vertices become four vertices and an index list. Weld before running the manifold check: unwelded geometry reports every edge as used once, because no two triangles share a vertex index even where they visually share an edge. ```{index} single: half-edge structure ``` ## Half-edge, for editing The two arrays answer "what are this triangle's vertices" in constant time and "which faces touch this vertex" only by scanning everything. Editing operations need the second question constantly. A **half-edge** structure stores each edge twice, once per direction, with each half knowing its face, its next half-edge, and its opposite. Walking the opposites around a vertex enumerates its neighbours without a scan. It is what a modelling tool holds in memory; a renderer converts back to vertex and index arrays before drawing. The modelling-operations chapter builds on it. ## Next The mesh here was written as Perl literals. Real geometry comes from files, and the [next chapter](model-formats) covers the formats that carry it.