Indexed Triangle Meshes and the Vertex Cache

A closed triangle mesh with $v$ vertices and $f$ triangles satisfies $f \approx 2v$: Euler’s formula gives $v - e + f = 2$ for a genus-zero surface, and each triangle contributes three edges shared by two faces, so $e = 3f/2$. Substituting yields $f = 2v - 4$. That single identity is the reason indexed geometry exists. A flat list of triangles stores three vertices per triangle, so the same vertex position is written to memory about six times. An index buffer keeps one copy per vertex and replaces the repetition with a compact stream of integers.

The byte arithmetic of triangle soup

Consider a vertex carrying a three-component float position, a three-component float normal, and two-component float texture coordinates. Eight floats at four bytes each is 32 bytes. Three vertices per triangle makes 96 bytes, and 96 bytes per triangle times roughly two triangles per vertex means about 192 bytes of vertex data per mesh vertex, of which at most 32 bytes is new information. The rest is duplication of numbers the memory system already holds.

Replace the soup with a shared vertex array plus 32-bit indices. The vertex array is 32 bytes per vertex. The index stream is 3 indices per triangle at 4 bytes, or 12 bytes per triangle, which is 24 bytes per vertex at $f \approx 2v$. Total is 56 bytes per vertex, a factor of roughly 3.4 reduction for this attribute set. With 16-bit indices the index stream halves to 6 bytes per triangle, and the total falls to 44 bytes per vertex.

The 16-bit case exposes a hard limit: index values address at most 65,536 distinct vertices, so a mesh larger than that must be split into chunks, each with its own draw call and its own local vertex array. Hardware index formats are 8-, 16-, and 32-bit, and the 8-bit form caps a chunk at 256 vertices, which is only useful for small props. Choosing chunk boundaries is a partitioning problem: split too finely and the per-draw-call overhead dominates; split too coarsely and the index width grows. A common compromise subdivides spatially so that each chunk stays under the 16-bit limit while sharing as many boundary vertices as it can.

The indexed form is also the output of every mesh processing pass that changes vertex count. A decimation step driven by accumulated quadric error merges vertices and rewrites the index stream, which means any cache-friendly ordering established earlier is invalidated and has to be recomputed after the geometry stops changing.

Why the index stream is not just a compression trick

If the vertex array were the only consideration, the index buffer would be a file-format concern. It is not, because vertex processing is not free and its results are cached. A GPU runs a fixed-stage pipeline: the vertex shader executes once per index fetch that misses the post-transform cache, and the primitive assembly stage consumes the resulting clip-space positions. Deduplicating vertices removes redundant shader invocations.

The post-transform cache is small and fully associative in behavior. On widely deployed hardware it historically held on the order of 16 to 32 entries; the exact figure is not part of any specification and varies by vendor and generation. Because it is small, the order of the index stream decides the hit rate. A mesh whose indices are emitted in arbitrary order thrashes it: each triangle’s three vertices are fetched, three old entries are evicted, and the next triangle shares nothing with what remains. A mesh whose indices are emitted so that consecutive triangles reuse recently referenced vertices reaches a hit rate near the theoretical maximum for the cache size.

The ordering problem has a clean statement. Given a triangle mesh and a cache of size $k$, choose a triangle order minimizing cache misses. The general problem is hard, but greedy heuristics work well because the objective is local. The standard approach scores each candidate vertex by how recently it was used: a vertex still inside the cache is nearly free, a vertex used a few triangles ago is cheap, and an unseen vertex costs a full fetch. Triangles are then chosen to maximize the summed score of their three corners.

def order_triangles(tris, cache_size=32):
    """Greedy ordering: prefer triangles whose corners are still cached."""
    remaining = list(range(len(tris)))
    order, cache = [], []
    while remaining:
        best, best_score, best_at = -1, float('-inf'), -1
        for pos, t in enumerate(remaining):
            score = 0.0
            for v in tris[t]:
                if v in cache:
                    # recency: 0.0 for the oldest entry, 0.75 for the newest
                    age = cache.index(v)
                    score += 0.75 - 0.75 * age / cache_size
                else:
                    score -= 1.0
            if score > best_score:
                best, best_score, best_at = t, score, pos
        order.append(best)
        remaining.pop(best_at)
        for v in tris[best]:
            if v in cache:
                cache.remove(v)
            cache.insert(0, v)
            if len(cache) > cache_size:
                cache.pop()
    return order

The scoring constants are arbitrary; the structure of the heuristic is what matters. Any monotone function of recency produces the same qualitative behavior.

Splitting vertices at attribute seams

An index buffer assumes a vertex is a single indivisible record. That assumption fails whenever two triangles meet at the same position but disagree about another attribute. A cube demonstrates it: the eight corners of a cube are shared by three faces each, but each face needs its own normal. Storing one vertex per corner forces a choice between wrong shading and wrong topology. The practical answer is to split: the mesh has eight positions but twenty-four vertices, one per corner-face pair. Texture seams behave the same way, as do hard edges, per-face material assignments, and skinning weights that differ across a joint.

This is why a renderer’s vertex count rarely equals the topological vertex count. A cube with 8 positions, 12 triangles, and 24 vertices has a vertex-to-position ratio of 3, and its index buffer addresses 24 slots while the geometry has 8. Any conversion pipeline that welds vertices by position alone will destroy the seams, and any pipeline that never welds will inflate the count. The correct rule is to weld only vertices whose full attribute tuples agree.

Splitting has a second-order cost. A seam vertex appears in the index stream several times as different indices, so the cache treats the duplicates as distinct entries. At a seam that runs across many triangles, both sides compete for cache space and neither benefits from the other’s fetches.

Restart indices and what they replace

A draw call that submits a triangle list and a draw call that submits a strip differ in how much index data the memory system must deliver. A strip of $n$ triangles needs $n+2$ indices, because each new index extends the previous two into a new triangle. The catch is that a strip encodes exactly one connected path, and a mesh has many. Joining strips into one call therefore needs a marker that says “the previous triangle is finished, start a new one”.

The primitive restart mechanism supplies it: a reserved index value — all ones in the index’s width, so 65535 for 16-bit and 4294967295 for 32-bit — terminates the current primitive and begins a new one on the next index. Using it, a mesh of $t$ triangles can be submitted as a set of strips separated by restart indices, at a cost of $n + 2 + k$ indices for $k$ strips. Compared with the $3n$ of a plain triangle list, that is a saving of nearly a factor of three whenever strips are long, and it disappears when strips are short: a mesh decomposed into strips averaging four triangles each needs $4 + 2 + 1 = 7$ indices per strip against 12 for the list, a saving of less than half.

Stripification is thus a second optimization problem layered on the first, and it conflicts with cache ordering. A greedy cache-order traversal destroys strip structure because strips want long coherent paths while cache reuse wants local revisits. The two objectives can be combined, but the combination is a heuristic, and a mesh that has been optimized for one is no longer optimal for the other. Hardware that consumes the index stream in fixed-size batches constrains both: an index buffer whose triangle count is not a multiple of the batch size leaves the last partial batch underfilled.

Where the model breaks down

Indexed geometry is not always the smaller representation. For a mesh with no shared vertices at all — a set of disconnected triangles, as produced by a particle system or an unstructured point cloud triangulation — the index buffer is pure overhead, adding 12 bytes per triangle and one indirection to every fetch. Some pipelines therefore support non-indexed draws, and a triangle strip or fan encoding can beat both forms when the mesh has a regular grid structure, because a strip of $n$ triangles needs only $n+2$ indices instead of $3n$.

There is also an interaction with how adjacency is queried on the CPU side. The index stream stores triangles as independent triples, which makes neighbour lookup a search rather than a pointer dereference; a structure that stores explicit connectivity, such as the half-edge representation, pays more bytes per element to answer that question in constant time. Choosing between them is a question of which access pattern dominates, and it is the same trade that separates a file format from an editing data structure. The orientation of the triangles in the stream is a separate concern, covered under consistent orientation and signed volume.

The last failure mode is numerical rather than structural. When vertices are welded by comparing positions, the comparison needs a tolerance, and the tolerance interacts with model scale. Two vertices that differ by less than the tolerance collapse, which is correct for a seam that should not exist and wrong for a thin feature. The result is a mesh with zero-area triangles, whose normals are undefined and whose contribution to any signed volume computation is noise.