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.
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:
# 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)
);
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: 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.
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)):
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;
}
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.
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.
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.
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:
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.
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.
Bounding volumes#
Cheap approximations used to reject work early: a ray that misses the box cannot hit any triangle in it.
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.
Welding#
Geometry from a file or a generator often repeats positions that should be shared. Welding collapses them by exact or tolerance match:
# 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;
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.
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 covers the formats that carry it.