# How meshopt_optimizeVertexCache Works and Which GPU Cache Sizes It Targets

> Learn how meshopt_optimizeVertexCache reorders triangle indices using a greedy algorithm for a 16-entry GPU vertex cache to boost post-transform cache hits.

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

---

**`meshopt_optimizeVertexCache` reorders triangle indices using a Forsyth-style greedy algorithm tuned for a 16-entry GPU vertex cache to maximize post-transform cache hits.**

The `meshopt_optimizeVertexCache` function in the **zeux/meshoptimizer** library implements vertex cache optimization that minimizes GPU vertex shading overhead by reordering mesh indices. It targets the post-transform vertex cache found in modern NVIDIA and AMD hardware using a linear-time algorithm that simulates cache behavior during optimization.

## Algorithm Overview

The implementation follows Tom Forsyth’s classic linear-speed cache optimization algorithm, enhanced with scoring heuristics specific to contemporary GPUs.

### Score Tables and Cache Modeling

At the core of the optimizer is a static **`VertexScoreTable`** defined in [`src/vcacheoptimizer.cpp`](https://github.com/zeux/meshoptimizer/blob/main/src/vcacheoptimizer.cpp) (lines 13–26). This table assigns a **cache score** for each possible cache position (0–15) and a **valence score** based on the number of live triangles remaining for a vertex (up to 8). The algorithm uses these pre-computed scores to evaluate how beneficial it is to reference a vertex at any given step.

### Building Triangle Adjacency

Before optimization begins, the function constructs per-vertex adjacency information via **`buildTriangleAdjacency`** (lines 41–88). This data structure maps every vertex to the list of triangles that reference it, enabling efficient updates when triangles are emitted. The adjacency build also initializes the `live_triangles` count for each vertex, which tracks how many triangles still need to be processed.

### Initial Scoring and Greedy Selection

The algorithm computes an initial score for each vertex using **`vertexScore(table, -1, live_triangles[i])`**, where `-1` indicates the vertex is not currently in the cache (lines 106–122). Triangle scores are the sum of their three vertex scores.

The optimizer then enters a greedy emission loop (lines 169–341):

1. **Select** the highest-scoring triangle and append its indices to the output buffer.
2. **Update** the simulated FIFO cache, pushing the triangle’s vertices to the front and aging existing entries.
3. **Decrement** `live_triangles` counts for the emitted vertices and recompute vertex scores based on new cache positions and remaining valence.
4. **Update** triangle scores for all triangles sharing the modified vertices.

If the cache becomes empty (a "dead-end"), the algorithm selects the next vertex from the input order to restart the process.

## Target Cache Sizes and Variants

The library provides three related functions targeting different cache configurations.

### Default 16-Entry Cache Target

`meshopt_optimizeVertexCache` assumes a **maximum cache size of 16 entries** (`kCacheSizeMax = 16` at line 13), which reflects the typical post-transform cache size on modern discrete GPUs. This fixed target provides optimal results for standard indexed triangle lists without requiring configuration.

### Strip-Optimized Variant

**`meshopt_optimizeVertexCacheStrip`** uses an alternative score table (`kVertexScoreTableStrip`, lines 30–33) optimized for minimizing encoded index buffer size rather than raw cache misses. This variant produces layouts that compress more efficiently while maintaining reasonable cache coherence.

### Configurable FIFO Variant

**`meshopt_optimizeVertexCacheFifo`** allows explicit control over cache size via a `cache_size` parameter (minimum 3, recommended 16). This variant uses a simpler FIFO replacement policy that runs faster than the adaptive algorithm but generally produces slightly lower quality results. As noted in the README (line 96), a cache size of 16 is recommended for this variant to match hardware expectations.

## Implementation Details from Source

The optimizer handles in-place operations safely: if the destination pointer equals the source indices, the routine copies the index buffer to a temporary array before processing (lines 81–87). All vertex cache variants are implemented in [`src/vcacheoptimizer.cpp`](https://github.com/zeux/meshoptimizer/blob/main/src/vcacheoptimizer.cpp), with public API declarations in [`src/meshoptimizer.h`](https://github.com/zeux/meshoptimizer/blob/main/src/meshoptimizer.h).

Key source locations:
- **`kVertexScoreTable`** definition: [`src/vcacheoptimizer.cpp`](https://github.com/zeux/meshoptimizer/blob/main/src/vcacheoptimizer.cpp) lines 13–26
- **Adjacency construction**: lines 41–88
- **Greedy optimization loop**: lines 169–341
- **Strip variant**: lines 50–53
- **FIFO variant**: lines 55–66

## Usage Examples

### C++ API

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

void optimizeMesh(std::vector<unsigned int>& indices, size_t vertex_count) {
    // In-place optimization for 16-entry cache
    meshopt_optimizeVertexCache(
        indices.data(),      // destination
        indices.data(),      // source
        indices.size(),
        vertex_count
    );
}

```

*Source: Usage pattern derived from [`demo/main.cpp`](https://github.com/zeux/meshoptimizer/blob/main/demo/main.cpp) (line 455).*

### JavaScript (WebAssembly) API

```javascript
import { meshopt_optimizeVertexCache } from "meshoptimizer";

// indices is a Uint32Array
meshopt_optimizeVertexCache(
    indices, 
    indices, 
    indices.length, 
    vertexCount
);

```

*Source: JavaScript binding in [`js/meshopt_encoder.js`](https://github.com/zeux/meshoptimizer/blob/main/js/meshopt_encoder.js) (line 144).*

## Summary

- **`meshopt_optimizeVertexCache`** implements a Forsyth-based greedy algorithm with a fixed 16-entry cache target.
- The optimizer uses pre-computed **score tables** for cache positions 0–15 and vertex valence up to 8.
- **Adjacency information** is built first to track live triangles per vertex.
- The **strip variant** optimizes for index buffer compression, while the **FIFO variant** allows custom cache sizes (minimum 3).
- All variants safely support **in-place** optimization when source and destination pointers match.

## Frequently Asked Questions

### What GPU cache size does meshopt_optimizeVertexCache target?

The function targets a **16-entry FIFO cache** (`kCacheSizeMax = 16`), which matches the post-transform vertex cache size found in modern NVIDIA and AMD GPUs. This fixed value is hardcoded in the score table definition in [`src/vcacheoptimizer.cpp`](https://github.com/zeux/meshoptimizer/blob/main/src/vcacheoptimizer.cpp).

### How does meshopt_optimizeVertexCache differ from the FIFO variant?

**`meshopt_optimizeVertexCache`** uses an adaptive scoring heuristic that considers both cache position and vertex valence, while **`meshopt_optimizeVertexCacheFifo`** uses a simpler strict FIFO replacement policy. The FIFO variant accepts a custom `cache_size` parameter and runs faster but produces lower quality results.

### Can I use meshopt_optimizeVertexCache for triangle strips?

No, the standard function optimizes for indexed triangle lists. For strip-friendly layouts, use **`meshopt_optimizeVertexCacheStrip`**, which employs a different score table (`kVertexScoreTableStrip`) optimized for minimizing strip encoded size.

### Is the algorithm suitable for real-time mesh processing?

Yes, the algorithm runs in **linear time** relative to the number of triangles, making it suitable for runtime optimization. However, the adaptive scoring variant is slower than the FIFO variant, so use **`meshopt_optimizeVertexCacheFifo`** with an appropriate cache size if speed is critical.