Polygon Mesh

A polygon mesh stores a surface as a set of points, the vertices, joined into flat polygons, the faces. Graphics hardware, 3D printers and physics engines consume it, and most 3D reconstruction pipelines end with one. Where a point cloud records only samples, a mesh also records which samples are neighbours, and so defines a surface between them. 3D representations compares meshes with the alternatives; this article covers the mesh itself.

Definition

A polygon mesh is a pair $(V, F)$: a list of vertex positions $\mathbf{v}_i \in \mathbb{R}^3$ and a list of faces, each an ordered cycle of vertex indices. Each pair of cyclically consecutive vertices in a face is an edge. Most meshes in vision are triangle meshes; modelling tools also use quadrilaterals, which split into two triangles each. A triangle is always planar, while a quad with four arbitrary vertices need not be, one reason why processing algorithms assume triangles (Garland and Heckbert, 1997, triangulate any polygon beforehand).

Intuition

Think of a mesh as a paper model: the vertices are the corners, the faces are the flat pieces of paper, and the edges are where pieces are glued together. Moving a vertex bends the model without tearing it, because faces refer to vertices by index; cutting or joining pieces changes the face list instead.

Formal Definition

Indexed face sets and adjacency

The simplest storage is an indexed face set: a $|V| \times 3$ array of coordinates and an $|F| \times 3$ array of vertex indices. Shared vertices are stored once. A “triangle soup”, in which each triangle repeats its three coordinates, has no connectivity: whether two triangles touch can only be found by matching coordinates.

An indexed face set does not answer “which faces surround this vertex?” or “which face lies across this edge?” without a search, so algorithms that walk over the surface use an adjacency structure. The half-edge structure, as documented for CGAL (Kettner), splits each edge into two half-edges of opposite direction; each stores its incident face and vertex and links to the next half-edge around its face and to its opposite. Following next circles a face, and alternating opposite and next circles a vertex (reasoning from the two links). CGAL’s variant is restricted to orientable 2-manifolds, which is why the properties below matter.

Orientation and normals

The order of a face’s vertices gives it an orientation. For a triangle $(\mathbf{a}, \mathbf{b}, \mathbf{c})$, the cross product

$$\mathbf{n} = (\mathbf{b} - \mathbf{a}) \times (\mathbf{c} - \mathbf{a})$$

is perpendicular to the face, points to the side from which the vertices appear counterclockwise, and has length twice the triangle’s area. OBJ, STL and glTF all use this convention: in OBJ, counterclockwise vertices make the face and its normal point toward the viewer, and STL lists vertices counterclockwise seen from outside. A mesh is consistently oriented when every pair of adjacent faces traverses its shared edge in opposite directions; then every directed edge occurs at most once, and on a closed surface all normals point outward (or all inward).

The face normal is $\mathbf{n} / \lVert \mathbf{n} \rVert$. A vertex normal, used for smooth shading, approximates the smooth surface’s normal by averaging the incident face normals; summing the unnormalized cross products weights each face by its area at no extra cost. OBJ stores vertex normals, which replace the facet normals when shading; glTF requires a viewer to compute flat normals when a file supplies none.

Manifoldness, boundaries and watertightness

A surface is a 2-manifold when every point’s neighbourhood looks like a disk, or a half-disk on a boundary (Garland & Heckbert, 1997; Botsch et al., 2007). For a mesh this means two checks:

• Edge-manifold: every edge belongs to one or two faces. An edge shared by three or more faces, such as a fin attached to a wall, violates it.
• Vertex-manifold: the faces around each vertex form a single fan, closed for an interior vertex and open for a boundary vertex. Two cones that touch at their tips give a vertex with two fans.

An edge with one face is a boundary edge; boundary edges form loops around holes. A manifold mesh without boundary edges is closed, or watertight: it separates inside from outside, so volume and inside tests are defined.

Topology: the Euler–Poincaré formula

For a connected, closed, orientable manifold mesh, the counts of vertices, edges and faces satisfy the Euler–Poincaré formula (Euler’s formula; equation 2.2 of Botsch et al., 2007)

$$\chi = |V| - |E| + |F| = 2 - 2g,$$

where the genus $g$ is the number of handles: $g = 0$ for a sphere or a cube, $g = 1$ for a torus. With $b$ boundary loops the right-hand side becomes $2 - 2g - b$, a standard extension. The Euler characteristic $\chi$ depends only on the topology, not on the triangulation, so counting elements reveals holes and handles; it also implies that a closed triangle mesh has about twice as many faces as vertices.

Attributes

• Per-vertex colour is interpolated across faces; PLY files commonly add red, green and blue vertex properties (Turk, 1994).
• Texture coordinates $(u, v)$ map each vertex into a 2D image, the texture map, so a coarse mesh can show detail far finer than its triangles. Conventions differ: glTF puts $(0, 0)$ at the image’s upper-left corner; OBJ calls $u$ the horizontal and $v$ the vertical direction.

Along a seam, where the surface is cut open to flatten it into the image, one position has two $(u, v)$ values. OBJ indexes each attribute separately (the face corner 1/4/2 names position 1, texture vertex 4 and normal 2); glTF requires all attribute arrays of a primitive to have the same count, so one index addresses them all and seam vertices must be duplicated. The checks above then report boundary edges along the seam until equal positions are merged.

File Formats

Format	Origin	Geometry	Attributes	Notes
OBJ	Wavefront; specification c. 1992	text; polygons with 1-based indices	texture vertices vt, normals vn, separate index per attribute	negative indices count back from the current line; materials in a companion MTL file
PLY	Stanford, Turk (1994)	ASCII or binary; header declares elements and properties	any per-vertex or per-face property, such as colour or normals	faces are vertex-index lists of any length
STL	3D Systems, 1988–1989	one triangle per record, three vertices each, no shared vertices	a facet normal only; no colour in the original format	binary: 80-byte header, 32-bit little-endian triangle count, 50 bytes per triangle
glTF 2.0	Khronos Group	binary buffers described by JSON; .glb packs both in one file	normals, tangents, texture coordinates, colours, skinning, materials	right-handed, $+Y$ up, metres; triangles are the default primitive

Turk names range data and marching-cubes isosurfaces among PLY’s intended sources. As of October 2026, the Library of Congress has not located the original 3D Systems STL specification; its description is used here. Because STL repeats coordinates per triangle, equal vertices must be merged before any of the checks above. glTF reverses the winding order when a node’s global transform has a negative determinant, so a mesh can be mirrored by a negative scale.

Common Processing

Smoothing. Laplacian smoothing moves each vertex toward the average of its neighbours $N(i)$,

$$\mathbf{v}_i \leftarrow \mathbf{v}_i + \lambda \Big( \frac{1}{|N(i)|} \sum_{j \in N(i)} \mathbf{v}_j - \mathbf{v}_i \Big), \qquad 0 < \lambda < 1,$$

the simplest of the weight choices in Taubin (1995). Taubin notes that this filter shrinks the surface, and follows each step with a second one of negative factor $\mu < -\lambda$, which smooths without shrinking.

Simplification. Garland and Heckbert (1997) reduce the face count by repeatedly contracting vertex pairs, usually edges. Each vertex keeps a symmetric $4 \times 4$ matrix $Q$ that sums the squared-distance quadrics of the planes of its incident triangles, so the error of a position $\bar{\mathbf{v}}$ in homogeneous coordinates is $\bar{\mathbf{v}}^\top Q \bar{\mathbf{v}}$. A contraction gets the quadric $Q_1 + Q_2$, the new vertex goes where this error is smallest (a $4 \times 4$ linear solve), and a heap picks the cheapest pair next. The quadric costs 10 floating-point numbers per vertex, and the authors report a 100-face approximation of their 69,451-triangle bunny in 15 seconds (Figure 10); their timings were collected on an SGI Indigo2 with a 195 MHz R10000 processor. Contracting pairs that share no edge can join separate parts, so the method supports non-manifold models and does not preserve topology.

Subdivision. Loop (1987) refines a triangle mesh by inserting a point on every edge, a weighted average of the edge’s two endpoints (weight $3/8$ each) and the two opposite vertices ($1/8$ each), and moving each old vertex toward the average $\mathbf{Q}$ of its neighbours, to $\alpha_N \mathbf{v} + (1 - \alpha_N)\mathbf{Q}$ with $\alpha_6 = 5/8$ for $N = 6$ neighbours. Repeated, the meshes converge to a surface that is curvature continuous except at a fixed number of extraordinary points, the original vertices with other than six neighbours (Loop calls six-neighbour vertices ordinary); there, Loop shows, the tangent plane is still well defined.

Remeshing replaces the triangles altogether, typically by ones of near-uniform size and shape.

Examples

The code builds a unit icosphere (an icosahedron whose triangles are split into four, three times) with outward winding. It computes normals, the area and, by the divergence theorem, the volume as a sum of signed tetrahedra $\tfrac{1}{6} \sum_f \mathbf{a} \cdot (\mathbf{b} \times \mathbf{c})$, valid for any closed, consistently oriented mesh. It checks the properties above on the sphere, with one face flipped, with a hole, and glued to a second sphere at a vertex. Finally it adds 2% radial noise to a finer icosphere and applies Laplacian steps with $\lambda = 0.5$.

import numpy as np

def icosphere(levels):
    """Unit icosphere: an icosahedron whose triangles are split into four, `levels` times."""
    p = (1 + 5 ** 0.5) / 2
    V = np.array([[-1, p, 0], [1, p, 0], [-1, -p, 0], [1, -p, 0], [0, -1, p], [0, 1, p],
                  [0, -1, -p], [0, 1, -p], [p, 0, -1], [p, 0, 1], [-p, 0, -1], [-p, 0, 1]], float)
    F = np.array([[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]])                      # counterclockwise seen from outside
    V /= np.linalg.norm(V, axis=1, keepdims=True)
    for _ in range(levels):
        E = np.sort(np.concatenate([F[:, [0, 1]], F[:, [1, 2]], F[:, [2, 0]]]), axis=1)
        E, inv = np.unique(E, axis=0, return_inverse=True)  # one midpoint per edge
        m = len(V) + inv.ravel().reshape(3, -1).T              # midpoint index of edges 01, 12, 20
        mid = V[E].mean(axis=1)
        V = np.vstack([V, mid / np.linalg.norm(mid, axis=1, keepdims=True)])
        a, b, c = F.T
        F = np.concatenate([np.c_[a, m[:, 0], m[:, 2]], np.c_[b, m[:, 1], m[:, 0]],
                            np.c_[c, m[:, 2], m[:, 1]], m])
    return V, F

def face_normals(V, F):
    """Unnormalized normals (b - a) x (c - a): direction from the winding, length = 2 * area."""
    a, b, c = V[F[:, 0]], V[F[:, 1]], V[F[:, 2]]
    return np.cross(b - a, c - a)

def vertex_normals(V, F):
    """Area-weighted average of the incident face normals."""
    N = np.zeros_like(V)
    for k in range(3):
        np.add.at(N, F[:, k], face_normals(V, F))
    return N / np.linalg.norm(N, axis=1, keepdims=True)

def area(V, F):
    return 0.5 * np.linalg.norm(face_normals(V, F), axis=1).sum()

def volume(V, F):
    """Divergence theorem: sum of signed tetrahedra (origin, a, b, c)."""
    a, b, c = V[F[:, 0]], V[F[:, 1]], V[F[:, 2]]
    return np.einsum("ij,ij->i", a, np.cross(b, c)).sum() / 6

def topology(V, F):
    """Counts and checks from the face list alone."""
    he = np.concatenate([F[:, [0, 1]], F[:, [1, 2]], F[:, [2, 0]]])   # directed half-edges
    und, cnt = np.unique(np.sort(he, axis=1), axis=0, return_counts=True)
    _, dcnt = np.unique(he, axis=0, return_counts=True)
    # Vertex-manifold: the faces around each vertex form one fan (connected via shared edges).
    fans_ok = True
    for v in np.unique(F):
        ring = [tuple(r[r != v]) for r in F[(F == v).any(axis=1)]]  # edge opposite v in each face
        seen, todo = {ring[0][0]}, [ring[0][0]]
        while todo:
            x = todo.pop()
            for e in ring:
                if x in e:
                    y = e[1] if e[0] == x else e[0]
                    if y not in seen:
                        seen.add(y); todo.append(y)
        fans_ok &= len(seen) == len({u for e in ring for u in e})
    nV, nE, nF = len(np.unique(F)), len(und), len(F)
    return dict(V=nV, E=nE, F=nF, chi=nV - nE + nF,
                boundary_edges=int(np.sum(cnt == 1)), edge_manifold=bool(np.all(cnt <= 2)),
                vertex_manifold=bool(fans_ok), consistent=bool(np.all(dcnt == 1)))

V, F = icosphere(3)
print("icosphere level 3:", topology(V, F))
Nf = face_normals(V, F)
cent = V[F].mean(axis=1)
print(f"faces with outward normals: {np.mean(np.einsum('ij,ij->i', Nf, cent) > 0):.0%}")
ang = np.degrees(np.arccos(np.clip(np.einsum("ij,ij->i", vertex_normals(V, F), V), -1, 1)))
print(f"vertex-normal error vs exact sphere normal: max {ang.max():.2f} deg")
print(f"area   {area(V, F):.4f}  (sphere 4*pi   = {4 * np.pi:.4f})")
print(f"volume {volume(V, F):.4f}  (sphere 4*pi/3 = {4 * np.pi / 3:.4f})")

# Flip one face: its three half-edges now duplicate their neighbours' half-edges.
Fb = F.copy(); Fb[17] = Fb[17, ::-1]
he = np.concatenate([Fb[:, [0, 1]], Fb[:, [1, 2]], Fb[:, [2, 0]]])
_, inv, dcnt = np.unique(he, axis=0, return_inverse=True, return_counts=True)
bad = (dcnt[inv.ravel()] > 1).reshape(3, -1).sum(axis=0)   # duplicated half-edges per face
print("flipped face 17 -> consistent:", topology(V, Fb)["consistent"],
      "| faces with 3 bad edges:", np.flatnonzero(bad == 3),
      f"| volume {volume(V, Fb):.4f}")

# Open the mesh: delete the faces around one vertex (a hole), then glue a second sphere at a vertex.
Fo = F[~(F == 0).any(axis=1)]
print("hole:", topology(V, Fo))
# Copy centred at 2*V[0]: its vertex 3 (antipode of vertex 0) lands on vertex 0 and is merged.
idx = np.arange(len(V)) + len(V); idx[3] = 0
V2, F2 = np.vstack([V, V + 2 * V[0]]), np.vstack([F, idx[F]])
print("two spheres sharing a vertex:", topology(V2, F2))

# One step of uniform Laplacian smoothing on a noisy sphere: x_i += lam * (mean of neighbours - x_i).
V, F = icosphere(4)
E = np.unique(np.sort(np.concatenate([F[:, [0, 1]], F[:, [1, 2]], F[:, [2, 0]]]), axis=1), axis=0)
deg = np.bincount(E.ravel(), minlength=len(V))

def laplacian_step(X, lam):
    nb = np.zeros_like(X)
    np.add.at(nb, E[:, 0], X[E[:, 1]]); np.add.at(nb, E[:, 1], X[E[:, 0]])
    return X + lam * (nb / deg[:, None] - X)

err = lambda X: np.abs(np.linalg.norm(X, axis=1) - 1).mean()   # mean distance to the unit sphere
print(f"\nlevel 4: {len(V)} vertices, {len(F)} faces; clean area {area(V, F):.4f}, error {err(V):.1e}")
print("seed  noisy area  error  -> smoothed area  error   mean radius")
for seed in range(5):
    rng = np.random.default_rng(seed)
    Vn = V * (1 + 0.02 * rng.standard_normal(len(V)))[:, None]   # 2% radial noise
    Vs = laplacian_step(Vn, 0.5)
    print(f"{seed:4d}  {area(Vn, F):10.4f}  {err(Vn):.4f} -> {area(Vs, F):13.4f}  {err(Vs):.4f}"
          f"   {np.linalg.norm(Vs, axis=1).mean():.4f}")
Vn = V * (1 + 0.02 * np.random.default_rng(0).standard_normal(len(V)))[:, None]
for name, X in [("noisy, seed 0", Vn), ("clean", V)]:
    out, errs = [], []
    for k in range(1, 21):
        X = laplacian_step(X, 0.5)
        errs.append(err(X))
        if k in (1, 2, 3, 5, 10, 20):
            out.append(f"{k}: {errs[-1]:.4f}")
    print(f"error after k steps, {name:13s}", "  ".join(out), f"| lowest at step {np.argmin(errs) + 1}")

Output:

icosphere level 3: {'V': 642, 'E': 1920, 'F': 1280, 'chi': 2, 'boundary_edges': 0, 'edge_manifold': True, 'vertex_manifold': True, 'consistent': True}
faces with outward normals: 100%
vertex-normal error vs exact sphere normal: max 0.68 deg
area   12.5065  (sphere 4*pi   = 12.5664)
volume 4.1527  (sphere 4*pi/3 = 4.1888)
flipped face 17 -> consistent: False | faces with 3 bad edges: [17] | volume 4.1467
hole: {'V': 641, 'E': 1915, 'F': 1275, 'chi': 1, 'boundary_edges': 5, 'edge_manifold': True, 'vertex_manifold': True, 'consistent': True}
two spheres sharing a vertex: {'V': 1283, 'E': 3840, 'F': 2560, 'chi': 3, 'boundary_edges': 0, 'edge_manifold': True, 'vertex_manifold': False, 'consistent': True}

level 4: 2562 vertices, 5120 faces; clean area 12.5514, error 2.7e-17
seed  noisy area  error  -> smoothed area  error   mean radius
   0     14.1194  0.0160 ->       12.8386  0.0089   0.9979
   1     14.1639  0.0160 ->       12.8515  0.0087   0.9984
   2     14.1265  0.0160 ->       12.8266  0.0089   0.9978
   3     14.1617  0.0159 ->       12.8636  0.0086   0.9991
   4     14.1539  0.0158 ->       12.8502  0.0085   0.9986
error after k steps, noisy, seed 0 1: 0.0089  2: 0.0067  3: 0.0064  5: 0.0080  10: 0.0148  20: 0.0287 | lowest at step 3
error after k steps, clean         1: 0.0014  2: 0.0029  3: 0.0043  5: 0.0071  10: 0.0141  20: 0.0280 | lowest at step 1

The inscribed polyhedron falls short of the sphere’s area and volume by 0.5% and 0.9%, and its vertex normals deviate from the exact ones by at most 0.68°. The sphere has $\chi = 2$. A flipped face is the only one whose three half-edges are all duplicated, and its volume term changes sign. Deleting the five faces around a vertex leaves one boundary loop and $\chi = 1 = 2 - 0 - 1$. Two spheres glued at a vertex stay edge-manifold, but the shared vertex has two fans, and $\chi = 3$ matches no closed surface.

Noise of 2% raises the area by 12–13%, because a jagged surface is larger than a smooth one. For all five seeds, one Laplacian step brings the mean distance to the sphere from 0.016 to 0.0085–0.0089 and the area from 14.1–14.2 to 12.8–12.9, but the mean radius drops below 1. With seed 0 the error is lowest after three steps (0.0064) and grows after that, to 0.029 after 20; on the noise-free sphere it grows from the first step, and by step 20 the two runs nearly coincide: shrinkage dominates.

Rendering by Rasterization

A rasterizer projects each vertex with the pinhole camera model, fills each triangle with the pixels whose centres it covers, interpolates normals, colours and texture coordinates from the vertices, and keeps per pixel only the nearest triangle in a depth buffer. Back-face culling skips triangles that face away, as their winding reveals; glTF enables it unless a material is double-sided. Each triangle is processed once rather than sampled along every ray, which is why meshes render in real time.

Common Misconceptions

• “A mesh that looks closed is watertight.” Unmerged duplicate vertices, along texture seams or in STL files, leave boundary edges that a rendering does not show.
• “Stored normals define orientation.” Face normals follow from the winding order; stored vertex normals are a separate attribute that can disagree with it.
• “More smoothing is more accurate.” Uniform Laplacian smoothing also shrinks the surface, so the error soon grows again.

Where It Is Used

• Reconstruction from depth: marching cubes extracts a triangle mesh from the zero level set of a sampled signed distance function, such as a fused depth volume.
• Reconstruction from points: Poisson surface reconstruction meshes oriented points (point cloud).
• Photogrammetry: dense points from structure from motion and multi-view stereo are meshed, textured from the photographs and simplified (3D reconstruction).
• Depth maps: connecting neighbouring pixels of a depth map into triangles gives a mesh of the visible surface directly, if triangles across depth discontinuities are dropped (reasoning from the pixel grid).
• Evaluation and synthesis: reference meshes are sampled into points to score reconstructions; rendered meshes give synthetic images with exact depth.