How meshopt_optimizeVertexCache Works and Which GPU Cache Sizes It Targets

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 (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, with public API declarations in src/meshoptimizer.h.

Key source locations:

• kVertexScoreTable definition: 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

#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 (line 455).

JavaScript (WebAssembly) API

import { meshopt_optimizeVertexCache } from "meshoptimizer";

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

Source: JavaScript binding in 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.

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.

{
  "mcpServers": {
    "instagit": {
      "command": "npx",
      "args": ["-y", "instagit@latest"]
    }
  }
}