How meshopt_stripify Converts Triangle Lists to Triangle Strips in meshoptimizer

meshopt_stripify transforms indexed triangle lists into optimized triangle strips by greedily extending sequences along shared edges while inserting degenerate triangles or restart indices to maintain connectivity, implementing the classic stripification algorithm from Evans, Skiena & Varshney (1996).

The meshopt_stripify function in the zeux/meshoptimizer library provides an efficient CPU-side solution for converting traditional triangle lists into triangle strips, significantly reducing index buffer size and improving GPU cache locality. Located in src/stripifier.cpp, this implementation uses per-vertex valence heuristics and edge-matching to build continuous strips that minimize vertex buffer access.

The Stripification Algorithm

The algorithm follows the approach described by Evans, Skiena & Varshney (1996), processing input triangles to build strips that share edges between consecutive triangles. The function maintains a small working buffer of candidate triangles and tracks vertex valence (the number of incident triangles per vertex) to select optimal starting points for new strips.

Step-by-Step Implementation in src/stripifier.cpp

Input Validation and Temporary Storage

The function begins by validating that the input index_count is a multiple of three and that the destination buffer is distinct from the input indices. It allocates temporary storage including an 8-triangle buffer (buffer[8][3]) and a per-vertex valence array using meshopt_Allocator.

As seen in src/stripifier.cpp (lines 52-60), the initialization code ensures proper alignment and allocates the valence counters:

assert(destination != indices);
assert(index_count % 3 == 0);

The valence computation (lines 73-84) counts how many triangles reference each vertex, storing these counts in 8-bit integers. This heuristic favors low-valence vertices as strip start candidates because they have fewer neighboring triangles to disconnect.

Building Strips with Edge Matching

The main loop runs until all input triangles are consumed, filling the buffer with up to eight triangles at a time from the input index array. When a pending triangle exists (next >= 0), the algorithm searches for a continuation using findStripNext.

According to the implementation in src/stripifier.cpp (lines 105-124), the function removes the matching triangle from the buffer, decrements its vertices' valence counters, and checks for direct edge continuation. If the direct continuation fails but a swap edge exists, the code emits a degenerate vertex pair to change winding order (lines 126-138).

When appending a valid next vertex, the function updates the strip edge trackers (strip[0] and strip[1]) and flips the parity flag to maintain correct face winding (lines 140-148).

Handling Strip Continuation and Restarts

When no continuation exists (next < 0), the algorithm starts a new strip by calling findStripFirst, which selects the triangle with the smallest valence value in the current buffer (lines 154-156). This heuristic minimizes the probability of creating isolated triangles that would require expensive restart sequences.

The selected triangle is rotated so that one of its edges matches a pending triangle in the buffer, testing each edge via findStripNext and keeping the edge that yields the smallest buffer index as the continuation point (lines 168-200).

For the strip restart, the function checks for a primitive restart index. If provided (non-zero), it writes the restart value before the first vertex of the new strip (lines 202-213). Without restart support, the algorithm inserts two degenerate vertices to connect the previous strip to the new one, preserving a single continuous index buffer (lines 217-240).

Working with Primitive Restart and Degenerate Triangles

The meshopt_stripify function supports two modes for handling strip breaks: primitive restart indices and degenerate triangles. When the restart_index parameter is non-zero, the function emits this special value to signal the GPU to start a new strip. This approach requires hardware support but avoids extra vertex processing.

Without primitive restart, the function generates degenerate triangles (zero-area triangles) by duplicating vertices, effectively creating invisible connector geometry that allows the strip to continue. This method works on all hardware but adds overhead to the vertex shader.

Code Examples

Basic Stripification

To convert a triangle list to a strip without primitive restart, first calculate the buffer size using meshopt_stripifyBound, then call meshopt_stripify:

// Compute an upper bound for the strip buffer
size_t indexCount = mesh.indices.size();          // must be a multiple of 3
size_t vertexCount = mesh.vertices.size();
std::vector<unsigned int> strip(meshopt_stripifyBound(indexCount));

// Convert the triangle list -> strip (no restart index)
size_t stripSize = meshopt_stripify(
    strip.data(),
    mesh.indices.data(),
    indexCount,
    vertexCount,
    0u);                                           // 0 disables primitive restart
strip.resize(stripSize);

Using Primitive Restart

For GPUs that support primitive restart, pass a special index value (such as 0xFFFFFFFF for 32-bit indices):

// Using primitive restart (e.g. 0xFFFFFFFF for 32‑bit indices)
unsigned int restart = 0xFFFFFFFFu;
size_t stripSize = meshopt_stripify(
    strip.data(),
    mesh.indices.data(),
    indexCount,
    vertexCount,
    restart);

Converting Back to Triangle Lists

The inverse operation uses meshopt_unstripify to convert strips back to lists:

// Convert the strip back to a triangle list (inverse operation)
std::vector<unsigned int> list(meshopt_unstripifyBound(stripSize));
size_t listSize = meshopt_unstripify(
    list.data(),
    strip.data(),
    stripSize,
    restart);
list.resize(listSize);

These patterns are demonstrated in the repository's demo code at demo/main.cpp (lines 1147-1156) and documented in the README.md.

Summary

• meshopt_stripify in src/stripifier.cpp implements the Evans, Skiena & Varshney (1996) stripification algorithm to convert triangle lists to strips.
• The algorithm uses vertex valence heuristics to select optimal strip starting points, minimizing the number of required restarts.
• Edge matching via findStripNext extends strips by finding triangles that share edges with the current strip end.
• The function supports both primitive restart indices (when restart_index is non-zero) and degenerate triangles (when restarting is disabled) to handle strip breaks.
• Helper functions meshopt_stripifyBound and meshopt_unstripifyBound provide worst-case buffer size calculations, with stripification requiring up to 5 indices per input triangle.

Frequently Asked Questions

What is the difference between meshopt_stripify and meshopt_unstripify?

meshopt_stripify converts a triangle list (groups of three indices) into a triangle strip (where each new vertex forms a triangle with the previous two), while meshopt_unstripify performs the inverse operation, expanding a strip back into a standard triangle list. Both functions are declared in src/meshoptimizer.h and implemented in src/stripifier.cpp.

How does meshopt_stripifyBound calculate the output buffer size?

meshopt_stripifyBound returns the worst-case buffer size required for stripification, calculated as index_count / 3 * 5 (5 indices per triangle). This accommodates the maximum possible overhead from degenerate triangles inserted during strip restarts, ensuring sufficient allocation even for meshes that cannot be efficiently stripped.

Why does meshopt_stripify use vertex valence as a heuristic?

The algorithm uses per-vertex valence (the count of incident triangles) to prioritize starting new strips at low-valence vertices. Vertices with fewer incident triangles are less likely to be shared between multiple strips, reducing the number of forced restarts and minimizing degenerate triangle overhead. This heuristic is computed in src/stripifier.cpp at lines 73-84.

When should I use primitive restart indices versus degenerate triangles?

Use primitive restart indices (passing a non-zero restart_index such as 0xFFFFFFFF) when targeting modern GPUs with hardware restart support, as this avoids processing degenerate vertices. Use degenerate triangles (passing 0 for restart_index) for maximum compatibility with older hardware or when the GPU driver does not properly support primitive restart, though this adds vertex processing overhead.

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