# How the zeux/meshoptimizer Vertex Cache Optimization Algorithm Works

> Discover how zeux meshoptimizer uses Tom Forsyth's Linear Speed Vertex Cache Optimization to boost GPU performance. Learn about precomputed scores and greedy reordering for maximum cache hits.

- Repository: [Arseny Kapoulkine/meshoptimizer](https://github.com/zeux/meshoptimizer)
- Tags: internals
- Published: 2026-07-11

---

**The meshoptimizer library implements Tom Forsyth's "Linear Speed Vertex Cache Optimization" using a precomputed score table to greedily reorder triangle indices, maximizing GPU cache hits by selecting triangles with the highest combined vertex scores while simulating a 16-entry FIFO cache.**

The zeux/meshoptimizer project provides production-ready mesh optimization for real-time rendering applications. Its vertex cache optimization algorithm reorders index buffers to maximize post-transform vertex cache utilization, significantly reducing GPU vertex processing overhead without modifying mesh geometry or topology.

## Core Components of the Algorithm

The implementation in [`src/vcacheoptimizer.cpp`](https://github.com/zeux/meshoptimizer/blob/main/src/vcacheoptimizer.cpp) relies on three interconnected mechanisms: precomputed score tables, a cache-aware scoring function, and greedy triangle selection backed by FIFO simulation.

### Vertex Score Tables

The algorithm uses a static lookup structure to avoid expensive runtime calculations. The **`VertexScoreTable`** struct (defined at line 16 of [`src/vcacheoptimizer.cpp`](https://github.com/zeux/meshoptimizer/blob/main/src/vcacheoptimizer.cpp)) encodes the benefit of emitting a vertex based on its position in the cache and its remaining unprocessed triangle count. The library provides two predefined instances: **`kVertexScoreTable`** (line 23) optimized for general indexed triangles, and **`kVertexScoreTableStrip`** (line 29) which biases output toward strip-friendly locality patterns.

### The Scoring Function

The **`vertexScore`** function (line 144) calculates a floating-point value by querying the score table with the vertex's current cache position and live triangle count. This function assigns a **cache position bonus** to vertices currently resident in the simulated FIFO cache and a **valence bonus** to vertices referenced by many unprocessed triangles, encouraging future reuse.

### Greedy Selection and Cache Simulation

The core optimizer routine, **`meshopt_optimizeVertexCacheTable`** (line 169), maintains two critical data structures: an active vertex list containing vertices still referenced by unprocessed triangles, and a candidate triangle list containing faces with at least one cached vertex. At each iteration, the algorithm selects the triangle with the highest sum of its three vertex scores, emits it to the output buffer, and updates the simulated **16-entry FIFO cache** by moving the triangle's vertices to the front. Vertices that fall out of the cache lose their positional bonus, naturally de-prioritizing them until they are referenced again.

## Public API Entry Points

Three public functions expose the optimizer through [`src/meshoptimizer.h`](https://github.com/zeux/meshoptimizer/blob/main/src/meshoptimizer.h) (line 207), each forwarding to the internal `meshopt_optimizeVertexCacheTable` implementation with different score table configurations:

- **`meshopt_optimizeVertexCache`** (line 345 of [`src/vcacheoptimizer.cpp`](https://github.com/zeux/meshoptimizer/blob/main/src/vcacheoptimizer.cpp)): Uses `kVertexScoreTable` for standard 16-entry cache optimization compatible with most modern GPUs.
- **`meshopt_optimizeVertexCacheStrip`** (line 350): Uses `kVertexScoreTableStrip` to generate index orders favoring sequential access patterns suitable for strip-like rendering.
- **`meshopt_optimizeVertexCacheFifo`** (line 355): Accepts a custom `cacheSize` parameter, allowing optimization for hardware with non-standard post-transform cache capacities.

## Practical Usage Examples

### Basic Vertex Cache Optimization

The standard API optimizes for a 16-entry cache suitable for most desktop and mobile GPUs:

```cpp
#include "meshoptimizer.h"
#include <vector>

std::vector<unsigned int> indices = /* original index buffer */;
size_t indexCount = indices.size();
size_t vertexCount = /* unique vertex count */;

std::vector<unsigned int> optimized(indexCount);

meshopt_optimizeVertexCache(
    optimized.data(),
    indices.data(),
    indexCount,
    vertexCount);

```

### Custom Cache Size Configuration

For GPUs with larger post-transform caches, use the FIFO variant:

```cpp
unsigned int cacheSize = 24; // Target a 24-entry cache
meshopt_optimizeVertexCacheFifo(
    optimized.data(),
    indices.data(),
    indexCount,
    vertexCount,
    cacheSize);

```

### Benchmarking with vcachetuner

The `vcachetuner` utility in [`tools/vcachetuner.cpp`](https://github.com/zeux/meshoptimizer/blob/main/tools/vcachetuner.cpp) benchmarks different cache configurations:

```bash
./vcachetuner input.meshopt -c 32

```

## Why This Algorithm Maximizes Cache Efficiency

The optimization works by exploiting temporal locality through two complementary scoring mechanisms. **Cache position scoring** ensures vertices remain in the post-transform cache as long as possible, preventing expensive re-transformations. **Valence scoring** (the live triangle count) prioritizes high-degree vertices, ensuring they stay accessible while the algorithm processes their adjacent triangles. By greedily selecting the highest-scoring available triangle at each step, the algorithm approaches theoretical maximum cache utilization while preserving the original mesh topology and vertex count.

## Summary

- The algorithm implements Tom Forsyth's linear-speed approach using precomputed **`VertexScoreTable`** lookup tables defined in [`src/vcacheoptimizer.cpp`](https://github.com/zeux/meshoptimizer/blob/main/src/vcacheoptimizer.cpp).
- The **`vertexScore`** function (line 144) combines cache position and valence bonuses to guide triangle selection.
- Three public APIs—**`meshopt_optimizeVertexCache`**, **`meshopt_optimizeVertexCacheStrip`**, and **`meshopt_optimizeVertexCacheFifo`**—provide flexibility for standard, strip-friendly, and custom cache size scenarios.
- The greedy selection process simulates a 16-entry FIFO cache, emitting triangles with maximum combined vertex scores at each iteration.

## Frequently Asked Questions

### What is vertex cache optimization?

Vertex cache optimization is the process of reordering triangle indices to maximize hits in the GPU's post-transform vertex cache, thereby reducing redundant vertex shader executions. By keeping recently transformed vertices resident in cache, the GPU avoids re-processing shared vertices between adjacent triangles, significantly improving rendering performance for dense meshes.

### How does the meshoptimizer implementation differ from the original Forsyth algorithm?

The meshoptimizer implementation extends Forsyth's original algorithm with production-hardened score tables and multiple optimization modes. As implemented in [`src/vcacheoptimizer.cpp`](https://github.com/zeux/meshoptimizer/blob/main/src/vcacheoptimizer.cpp), it provides **`kVertexScoreTable`** and **`kVertexScoreTableStrip`** variants (lines 23 and 29) tuned for modern GPU architectures, along with explicit support for custom cache sizes through **`meshopt_optimizeVertexCacheFifo`**.

### What cache size should I use with `meshopt_optimizeVertexCacheFifo`?

Use **`meshopt_optimizeVertexCacheFifo`** when targeting hardware with known non-standard cache sizes. While the default 16-entry cache suits most modern GPUs, larger values (24–32 entries) may benefit high-end desktop cards, while smaller values optimize for mobile GPUs. Benchmark with your specific mesh data using `vcachetuner` to determine the optimal size.

### Can I use this optimization for triangle strips?

Yes. While the output remains an indexed triangle list, call **`meshopt_optimizeVertexCacheStrip`** (line 350 of [`src/vcacheoptimizer.cpp`](https://github.com/zeux/meshoptimizer/blob/main/src/vcacheoptimizer.cpp)) to generate index orders that favor sequential access patterns compatible with triangle strip rendering. This function uses `kVertexScoreTableStrip` to prioritize locality patterns typical of strip-based meshes.