Meshes and geometry processing

Most objects in real-time graphics and film are represented as polygon meshes: collections of vertices, edges and faces, almost always triangles at render time, that approximate a surface. A character might have tens of thousands of triangles, a film creature millions, a scanned building billions. This lesson covers how meshes are stored, how normals are computed, the data structures that let algorithms walk across a mesh, and the core geometry-processing operations of subdivision, smoothing, simplification and level of detail. Curves and smooth surfaces come in lesson 10.

Representing surfaces

Surfaces can be represented explicitly, as meshes or parametric patches, or implicitly, as the set of points where a function is zero, such as \(x^2 + y^2 + z^2 - r^2 = 0\) for a sphere. Implicit surfaces make inside-outside tests and blending of shapes easy, and signed distance fields, which store the distance to the nearest surface with a sign, are popular for ray marching, collision detection and font rendering. Point clouds from laser scanners and photogrammetry store only sampled surface points, and volumetric grids store density for clouds, smoke and medical scans. Meshes dominate because GPUs rasterize triangles, because they represent sharp and smooth features flexibly, and because every modeling tool, game engine and file format supports them.

A triangle mesh has geometry, the positions of its vertices, and topology or connectivity, which vertices form each face. A mesh is a manifold if every edge is shared by exactly one or two faces and the faces around each vertex form a single fan; a closed manifold mesh, such as a sphere, has no boundary edges. Many algorithms require manifold input, while scanned and hand-made meshes often contain non-manifold edges, holes, duplicate vertices and self-intersections that need repair. Euler's formula connects counts: for a closed, connected, orientable mesh of genus g (the number of handles), \(V - E + F = 2 - 2g\). A sphere-like mesh has \(V - E + F = 2\); a torus has 0. For a closed triangle mesh each face has three edges and each edge two faces, so \(E = 3F/2\), and therefore \(F \approx 2V\): a triangle mesh has about twice as many triangles as vertices, and each vertex has on average six neighbors.

Storing meshes

The simplest storage is a triangle soup, a list of triangles with three explicit positions each. It is easy to generate but wastes memory, because each vertex is repeated in about six triangles, and it does not record which triangles are neighbors. An indexed face set stores each vertex once in a vertex buffer and each triangle as three integer indices into it. This is the format GPUs consume: an index buffer of 16-bit or 32-bit integers plus a vertex buffer with interleaved attributes. Indexing saves memory and lets the GPU's post-transform cache reuse vertex shader results for shared vertices; mesh optimizers such as meshoptimizer reorder triangles to maximize that reuse. Triangle strips and fans, once important, are mostly superseded by indexed lists with good ordering.

A vertex, in the GPU sense, is a unique combination of all its attributes, not just a position. Where a surface has a sharp crease, such as the edge of a cube, or a seam in its texture coordinates, the same position needs different normals or texture coordinates on each side, so it is duplicated into several vertices. A cube with flat-shaded faces therefore has 24 vertices, not 8. Common file formats include OBJ (simple text, positions, normals and texture coordinates), PLY (popular for scans), STL (triangle soup for 3D printing), FBX (proprietary, common in game pipelines), glTF 2.0 (the Khronos 'JPEG of 3D', designed for efficient transmission with physically based materials) and Pixar's Universal Scene Description (USD), which is becoming the interchange format for whole scenes across film, games and industrial digital twins.

# An indexed triangle mesh: the icosahedron, its Euler characteristic, face and
# vertex normals, and repeated subdivision toward a sphere (an "icosphere").
import numpy as np
t = (1 + 5 ** 0.5) / 2
V = np.array([[-1, t, 0], [1, t, 0], [-1, -t, 0], [1, -t, 0], [0, -1, t], [0, 1, t],
              [0, -1, -t], [0, 1, -t], [t, 0, -1], [t, 0, 1], [-t, 0, -1], [-t, 0, 1]], float)
V /= np.linalg.norm(V, axis=1, keepdims=True)
F = [(0, 11, 5), (0, 5, 1), (0, 1, 7), (0, 7, 10), (0, 10, 11), (1, 5, 9), (5, 11, 4), (11, 10, 2),
     (10, 7, 6), (7, 1, 8), (3, 9, 4), (3, 4, 2), (3, 2, 6), (3, 6, 8), (3, 8, 9), (4, 9, 5),
     (2, 4, 11), (6, 2, 10), (8, 6, 7), (9, 8, 1)]
def edges(F): return {tuple(sorted((f[i], f[(i + 1) % 3]))) for f in F for i in range(3)}
def subdivide(V, F):
    V = list(map(tuple, V)); cache = {}
    def mid(a, b):
        k = tuple(sorted((a, b)))
        if k not in cache:
            m = (np.array(V[a]) + np.array(V[b])) / 2
            V.append(tuple(m / np.linalg.norm(m))); cache[k] = len(V) - 1   # push onto the sphere
        return cache[k]
    G = []
    for a, b, c in F:
        ab, bc, ca = mid(a, b), mid(b, c), mid(c, a)
        G += [(a, ab, ca), (b, bc, ab), (c, ca, bc), (ab, bc, ca)]
    return np.array(V), G
print("level  vertices  edges  faces  V-E+F  max gap to true sphere")
for level in range(4):
    if level: V, F = subdivide(V, F)
    E = len(edges(F))
    cent = np.array([V[list(f)].mean(axis=0) for f in F])
    gap = 1 - np.linalg.norm(cent, axis=1).min()          # flat faces sag inside the sphere
    print(f"{level:5} {len(V):9} {E:6} {len(F):6} {len(V) - E + len(F):6} {gap:12.4f}")
# Face normals by cross product, vertex normals by area-weighted averaging
fn = np.array([np.cross(V[b] - V[a], V[c] - V[a]) for a, b, c in F])   # length = 2 x area
vn = np.zeros_like(V)
for (a, b, c), n in zip(F, fn):
    for i in (a, b, c): vn[i] += n
vn /= np.linalg.norm(vn, axis=1, keepdims=True)
print("max angle between vertex normal and true sphere normal:",
      round(float(np.degrees(np.arccos(np.clip((vn * V).sum(axis=1), -1, 1)).max())), 4), "degrees")
print(f"memory, indexed: {len(V) * 12 + len(F) * 3 * 4} bytes; unindexed: {len(F) * 3 * 12} bytes")

level  vertices  edges  faces  V-E+F  max gap to true sphere
    0        12     30     20      2       0.2053
    1        42    120     80      2       0.0658
    2       162    480    320      2       0.0178
    3       642   1920   1280      2       0.0045
max angle between vertex normal and true sphere normal: 0.6769 degrees
memory, indexed: 23064 bytes; unindexed: 46080 bytes

The icosahedron has 12 vertices, 30 edges and 20 faces, and every level of subdivision keeps \(V - E + F = 2\), as Euler's formula requires for a sphere-like surface. Each level multiplies the faces by four, and the largest gap between the flat faces and the true sphere shrinks by roughly a factor of four, because the sag of a chord shrinks with the square of its length. The final lines show that area-weighted vertex normals approximate the true sphere normals within a fraction of a degree, and that indexed storage uses about half the memory of unindexed triangles even before attributes other than positions are added.

Normals

Lighting depends on surface normals (lesson 8). A face normal comes from the cross product of two edge vectors, \(n = (b - a) \times (c - a)\), whose direction follows the winding order and whose length is twice the triangle's area. Consistent winding, usually counter-clockwise when seen from outside, is what makes normals point outward and back-face culling work. For smooth shading, each vertex needs a normal approximating the underlying smooth surface. The common approach averages the normals of the faces around the vertex, weighted by area (which the unnormalized cross product gives for free) or by the angle each face makes at the vertex, which is more robust when triangle sizes vary. Hard edges are preserved by splitting vertices along creases, often chosen automatically when the angle between adjacent faces exceeds a threshold such as 30 degrees.

Half-edge and other connectivity structures

Many algorithms need to navigate a mesh: find the faces around a vertex, the neighbors of a face, or the boundary loops. An indexed face set can answer these questions only by searching. The half-edge data structure, widely used since the 1980s and implemented in libraries such as OpenMesh and CGAL, splits each edge into two directed half-edges, one for each adjacent face. Each half-edge stores its origin vertex, the face to its left, the next half-edge around that face and its twin, the oppositely directed half-edge on the neighboring face. Each vertex stores one outgoing half-edge and each face one of its half-edges. With these pointers, all adjacency queries take constant time per element: the one-ring of a vertex is found by repeatedly moving to the twin of the previous edge, and boundary edges are those without a twin.

# A half-edge data structure built from a triangle list: each directed edge
# knows its next half-edge, its twin, its origin vertex and its face.
def build(F):
    he = {}                                    # (u, v) -> index
    rec = []                                   # [origin, face, next, twin]
    for fi, f in enumerate(F):
        base = len(rec)
        for k in range(3):
            u, v = f[k], f[(k + 1) % 3]
            he[(u, v)] = base + k
            rec.append([u, fi, base + (k + 1) % 3, None])
    for (u, v), i in he.items():
        rec[i][3] = he.get((v, u))             # None on a boundary
    return rec, he
# A small fan of triangles around vertex 0, open on one side (a boundary)
F = [(0, 1, 2), (0, 2, 3), (0, 3, 4), (0, 4, 5)]
rec, he = build(F)
print("half-edges:", len(rec), " boundary half-edges:", sum(r[3] is None for r in rec))
def one_ring(v):
    # start from any half-edge leaving v and rotate: twin of the previous edge
    start = next(i for i, r in enumerate(rec) if r[0] == v)
    ring, i = [], start
    while True:
        nxt = rec[i][2]; ring.append(rec[nxt][0])          # the edge's destination
        prev = rec[rec[nxt][2]]                             # half-edge entering v in this face
        if prev[3] is None:                                 # hit the boundary:
            ring.append(prev[0]); break                     # keep this face's last vertex
        i = prev[3]
        if i == start: break
    return ring
print("adjacent vertices of vertex 0, walking one way from its first edge:", one_ring(0))
print("half-edges (0, 2) and (2, 0) are twins:", he[(0, 2)], he[(2, 0)], rec[he[(0, 2)]][3] == he[(2, 0)])
print("faces adjacent to face 1:", sorted({rec[rec[i][3]][1] for i in range(3, 6) if rec[i][3] is not None}))

half-edges: 12  boundary half-edges: 6
adjacent vertices of vertex 0, walking one way from its first edge: [1, 2, 3, 4, 5]
half-edges (0, 2) and (2, 0) are twins: 3 2 True
faces adjacent to face 1: [0, 2]

The fan of four triangles has 12 half-edges, of which the outer ones and the two open sides have no twin and lie on the boundary. Walking around vertex 0 from its outgoing half-edge on one open side collects all five neighbors and stops at the other open side. Around an interior vertex the walk returns to its starting half-edge; for a boundary vertex whose walk starts in the middle of its fan, a full implementation also walks the other way to collect the rest. Alternatives include the winged-edge structure (Bruce Baumgart, 1975), corner tables, which store the opposite corner for each triangle corner in compact arrays and are popular in compression, and simple vertex-to-face adjacency lists built on demand. The right choice depends on whether the mesh changes topology during processing.

Subdivision surfaces

Subdivision surfaces produce smooth surfaces from coarse control meshes by repeatedly refining them: each step splits faces and repositions vertices by weighted averages of their neighbors. In the limit the mesh converges to a smooth surface. Edwin Catmull and Jim Clark (1978) defined the scheme for quadrilateral meshes that bears their name, and Charles Loop (1987) defined one for triangles. Catmull–Clark surfaces are smooth (continuous curvature) everywhere except at extraordinary vertices, those with a number of neighbors different from four, where they remain tangent-continuous. Pixar's 1997 short film Geri's Game was the first production use of subdivision surfaces, with semi-sharp creases for clothing and skin, and Pixar later released its OpenSubdiv library, now used throughout film and in real-time engines. Artists model a low-polygon cage, and the renderer subdivides it adaptively.

Smoothing, simplification and level of detail

Scanned meshes are noisy. Laplacian smoothing moves each vertex toward the average of its neighbors, \(v \gets v + \lambda(\bar{v}_{\text{neighbors}} - v)\), which removes noise but also shrinks the shape and rounds features; Gabriel Taubin's 1995 method alternates positive and negative steps to smooth without shrinking, and cotangent-weighted Laplacians respect triangle shapes better than uniform averages. The same discrete Laplacian operator underlies mesh deformation, parameterization and the computation of curvature.

Simplification reduces triangle count while preserving appearance, for level of detail and for transmitting large models. Vertex clustering snaps vertices to a grid and merges those in the same cell, which is fast but crude. Edge collapse methods remove one edge at a time, merging its two vertices, choosing the collapse with the least error. Michael Garland and Paul Heckbert's 1997 quadric error metric stores, for each vertex, a 4 by 4 matrix summing the squared distances to the planes of its adjacent faces; the cost of a collapse is the quadric evaluated at the new position, which can itself be chosen to minimize the error. Quadric simplification is fast, high quality and still the standard method. Progressive meshes (Hugues Hoppe, 1996) record a sequence of collapses that can be replayed in reverse to stream a model coarse to fine.

Level of detail (LOD) swaps between precomputed simplified versions of a model depending on its projected size, keeping triangles a few pixels across so that the GPU is not wasted on sub-pixel triangles. Discrete LODs can pop visibly when they switch, which engines hide with cross-fades or dithering. Unreal Engine 5's Nanite system, introduced in 2021, takes the idea further: it divides meshes into clusters of about 128 triangles organized in a hierarchy of simplified groups, selects a cut through the hierarchy per frame based on screen-space error, and rasterizes small triangles with a compute-shader software rasterizer, allowing film-quality assets with billions of source triangles in real time.

Worked examples