Optimizing glTF Indices with the Forsyth Algorithm

This article explores the critical role Tom Forsyth’s algorithm plays in optimizing glTF 3D model assets for real-time rendering. By restructuring a mesh's index buffer, the algorithm maximizes the efficiency of the modern GPU post-transform vertex cache, reducing redundant vertex shader invocations. You will learn how the GPU post-transform cache functions, how Forsyth’s scoring heuristic systematically orders triangle indices, and how this optimization directly improves runtime rendering performance and compression in the glTF ecosystem.

The Post-Transform Vertex Cache Challenge

When a modern GPU renders indexed triangle meshes—the standard representation in glTF assets—it processes vertices via the vertex shader before assembling them into primitives. To prevent redundant computation when multiple triangles share the same vertex, the GPU stores recently processed vertex results in a small hardware buffer known as the post-transform vertex cache (commonly modeled as a First-In, First-Out [FIFO] or Least Recently Used [LRU] cache, typically holding 16 to 64 vertices).

If a glTF file’s triangle indices are arranged randomly or naively, the GPU repeatedly evicts and recalculates identical vertices across neighboring triangles. This inefficiency raises the Average Cache Miss Ratio (ACMR)—the ratio of processed vertices to rendered triangles. An unoptimized mesh can approach an ACMR of 3.0 (meaning every vertex of every triangle is shaded from scratch), severely bottlenecking the GPU’s vertex pipeline.

How the Forsyth Algorithm Works

Published by Tom Forsyth, the algorithm is a fast, linear-time heuristic designed to reorder triangle draw order so that vertices stay resident in the post-transform cache for as long as possible. The algorithm calculates a dynamic score for each vertex using two primary metrics:

  1. Cache Score: Based on the vertex's current position within a simulated LRU cache. Vertices currently residing near the top of the cache receive a high score, encouraging the immediate rendering of adjacent triangles before those vertices are evicted.
  2. Valence Score: Based on the number of unrendered triangles that still share that vertex. Vertices belonging to fewer remaining triangles receive higher scores, prioritizing triangles that consume "dying" vertices and completely remove them from consideration.

For each step, the algorithm computes a composite score for unrendered triangles by summing the scores of their three corner vertices. It outputs the highest-scoring triangle to the new index buffer, updates the simulated cache state and remaining valences, and repeats the process until all indices are reordered.

Role of the Algorithm in glTF Optimization

In the glTF asset pipeline, the Forsyth algorithm operates directly on primitive index accessors (indices). Its implementation serves several vital functions:

  • Minimizing Vertex Shader Load: By reordering the index stream prior to runtime, the algorithm lowers the ACMR toward the theoretical limit (typically between 0.5 and 0.7 for manifold geometry). This yields a 2x to 3x reduction in vertex shader workload with zero loss in visual fidelity.
  • Pre-computation Over Runtime Cost: glTF is designed as a transmission format for runtime efficiency. Applying Forsyth's algorithm during offline asset preparation (via tools such as meshoptimizer or gltf-transform) ensures the client application incurs no CPU overhead for optimization upon loading the model.
  • Enabling Overfetch and Pre-Transform Optimization: Once indices are reordered for post-transform cache locality, the glTF vertex buffer itself can be reordered to match the first-appearance order in the index stream. This optimizes the pre-transform cache (the memory cache reading raw vertex data), minimizing memory bandwidth usage and cache thrashing across GPU memory buses.
  • Enhancing Downstream Compression: Reordering triangles into a localized, continuous spatial flow causes the numerical differences between adjacent indices to become smaller and more predictable. This significantly improves the compression ratios achieved by glTF extensions like KHR_mesh_quantization and EXT_meshopt_compression.