zeux/meshoptimizer

🐇 meshoptimizer

Purpose

When a GPU renders triangle meshes, various stages of the GPU pipeline have to process vertex and index data. The efficiency of these stages depends on the data you feed to them; this library provides algorithms to help optimize meshes for these stages, as well as algorithms to reduce the mesh complexity and storage overhead.

The library provides a C and C++ interface for all algorithms; you can use it from C/C++ or from other languages via FFI (such as P/Invoke). If you want to use this library from Rust, you should use meshopt crate. JavaScript interface for some algorithms is available through meshoptimizer.js.

Two companion projects are developed and distributed alongside the library: gltfpack, a command-line tool that automatically optimizes glTF files, and clusterlod.h, a single-header C/C++ library for continuous level of detail using clustered simplification.

Installing

meshoptimizer is hosted on GitHub; you can download the latest release using git:

git clone -b v1.3 https://github.com/zeux/meshoptimizer.git

Alternatively you can download the .zip archive from GitHub.

The library is also available as a Linux package in several distributions (ArchLinux, Debian, FreeBSD, Nix, Ubuntu), as well as a Vcpkg port (see installation instructions) and a Conan package.

gltfpack is available as a pre-built binary on Releases page or via npm package. Native binaries are recommended since they are more efficient and support texture compression.

Building

meshoptimizer is distributed as a C/C++ header (src/meshoptimizer.h) and a set of C++ source files (src/*.cpp). To include it in your project, you can use one of two options:

• Use CMake to build the library (either as a standalone project or as part of your project)
• Add source files to your project's build system

The source files are organized in such a way that you don't need to change your build-system settings, and you only need to add the source files for the algorithms you use. They should build without warnings or special compilation options on all major compilers. If you prefer amalgamated builds, you can also concatenate the source files into a single .cpp file and build that instead.

To use meshoptimizer functions, simply #include the header meshoptimizer.h; the library source is C++, but the header is C-compatible.

Core pipeline

When optimizing a mesh, to maximize rendering efficiency you should typically feed it through a set of optimizations (the order is important!):

1. Indexing 2. Vertex cache optimization 3. (optional) Overdraw optimization 4. Vertex fetch optimization 5. Vertex quantization 6. Index filtering 7. (optional) Shadow indexing

Indexing

Most algorithms in this library assume that a mesh has a vertex buffer and an index buffer. For algorithms to work well and also for GPU to render your mesh efficiently, the vertex buffer has to have no redundant vertices; you can generate an index buffer from an unindexed vertex buffer or reindex an existing (potentially redundant) index buffer as follows:

Note: meshoptimizer generally works with 32-bit (unsigned int) indices, however when using C++ APIs you can use any integer type for index data by using the provided template overloads. By convention, remap tables always use unsigned int.

First, generate a remap table from your existing vertex (and, optionally, index) data:

size_t index_count = face_count * 3;
size_t unindexed_vertex_count = face_count * 3;
std::vector remap(unindexed_vertex_count); // temporary remap table
size_t vertex_count = meshopt_generateVertexRemap(&remap[0], NULL, index_count,
    &unindexed_vertices[0], unindexed_vertex_count, sizeof(Vertex));

Note that in this case we only have an unindexed vertex buffer; when input mesh has an index buffer, it will need to be passed to meshopt_generateVertexRemap instead of NULL, along with the correct source vertex count. In either case, the remap table is generated based on binary equivalence of the input vertices, so the resulting mesh will render the same way. Binary equivalence considers all input bytes, including padding which should be zero-initialized if the vertex structure has gaps.

After generating the remap table, you can allocate space for the target vertex buffer (vertex_count elements) and index buffer (index_count elements) and generate them:

meshopt_remapIndexBuffer(indices, NULL, index_count, &remap[0]);
meshopt_remapVertexBuffer(vertices, &unindexed_vertices[0], unindexed_vertex_count, sizeof(Vertex), &remap[0]);

You can then further optimize the resulting buffers by calling the other functions on them in-place.

meshopt_generateVertexRemap uses binary equivalence of vertex data, which is generally a reasonable default; however, in some cases some attributes may have floating point drift causing extra vertices to be generated. For such cases, it may be necessary to quantize some attributes (most importantly, normals and tangents) before generating the remap, or use meshopt_generateVertexRemapCustom algorithm that allows comparing individual attributes with tolerance by providing a custom comparison function:

size_t vertex_count = meshopt_generateVertexRemapCustom(&remap[0], NULL, index_count,
    &unindexed_vertices[0].px, unindexed_vertex_count, sizeof(Vertex),
    [&](unsigned int lhs, unsigned int rhs) -> bool {
        const Vertex& lv = unindexed_vertices[lhs];
        const Vertex& rv = unindexed_vertices[rhs];
return fabsf(lv.tx - rv.tx) < 1e-3f && fabsf(lv.ty - rv.ty) < 1e-3f;
    });

Vertex cache optimization

When the GPU renders the mesh, it runs the vertex shader for each vertex. Historically, GPUs used a small fixed-size post-transform cache (16-32 vertices) with different replacement policies to store the shader output and avoid redundant shader invocations. Modern GPUs still perform vertex reuse, but with substantially different mechanics: vertex invocations are batched into thread groups based on the input indices, and effective reuse depends on factors like vertex shader outputs and rasterizer throughput. To maximize the locality of reused vertex references, you have to reorder your triangles like so:

meshopt_optimizeVertexCache(indices, indices, index_count, vertex_count);

The details of vertex reuse vary between different GPU architectures, so vertex cache optimization uses an adaptive algorithm that produces a triangle sequence with good locality that works well across different GPUs. Alternatively, you can use an algorithm that optimizes specifically for fixed-size FIFO caches: meshopt_optimizeVertexCacheFifo (with a recommended cache size of 16). While it generally produces less performant results on most GPUs, it runs ~2x faster, which may benefit rapid content iteration.

Overdraw optimization

After transforming the vertices, GPU sends the triangles for rasterization which results in generating pixels that are usually first run through the depth test, and pixels that pass it get the pixel shader executed to generate the final color. As pixel shaders get more expensive, it becomes more and more important to reduce overdraw. While in general improving overdraw requires view-dependent operations, this library provides an algorithm to reorder triangles to minimize the overdraw from all directions, which you can run after vertex cache optimization like this:

meshopt_optimizeOverdraw(indices, indices, index_count, &vertices[0].x, vertex_count, sizeof(Vertex), 1.05f);

The overdraw optimizer needs to read vertex positions as a float3 from the vertex; the code snippet above assumes that the vertex stores position as float x, y, z.

When performing the overdraw optimization you have to specify a floating-point threshold parameter. The algorithm tries to maintain a balance between vertex cache efficiency and overdraw; the threshold determines how much the algorithm can compromise the vertex cache hit ratio, with 1.05 meaning that the resulting ratio should be at most 5% worse than before the optimization.

Note that depending on the renderer structure and target hardware, the optimization may or may not be beneficial; for example, mobile GPUs with tiled deferred rendering (PowerVR, Apple) would not benefit from this optimization. For vertex heavy scenes it's recommended to measure the performance impact to ensure that the reduced vertex cache efficiency is outweighed by the reduced overdraw.

Vertex fetch optimization

After the final triangle order has been established, we still can optimize the vertex buffer for memory efficiency. Before running the vertex shader GPU has to fetch the vertex attributes from the vertex buffer; the fetch is usually backed by a memory cache, and as such optimizing the data for the locality of memory access is important. You can do this by running this code:

meshopt_optimizeVertexFetch(vertices, indices, index_count, vertices, vertex_count, sizeof(Vertex));

This will reorder the vertices in the vertex buffer to try to improve the locality of reference, and rewrite the indices in place to match; if the vertex data is stored using multiple streams, you should use meshopt_optimizeVertexFetchRemap instead. This optimization has to be performed on the final index buffer since the optimal vertex order depends on the triangle order.

Note that the algorithm does not try to model cache replacement precisely and instead just orders vertices in the order of use, which generally produces results that are close to optimal.

Vertex quantization

To optimize memory bandwidth when fetching the vertex data even further, and to reduce the amount of memory required to store the mesh, it is often beneficial to quantize the vertex attributes to smaller types. While this optimization can technically run at any part of the pipeline (and sometimes doing quantization as the first step can improve indexing by merging almost identical vertices), it generally is easier to run this after all other optimizations since some of them require access to float3 positions.

Quantization is usually domain specific; it's common to quantize normals using 3 8-bit integers but you can use higher-precision quantization (for example using 10 bits per component in a 10_10_10_2 format), or a different encoding to use just 2 components. For positions and texture coordinate data the two most common storage formats are half precision floats, and 16-bit normalized integers that encode the position relative to the AABB of the mesh or the UV bounding rectangle.

The number of possible combinations here is very large but this library does provide the building blocks, specifically functions to quantize floating point values to normalized integers, as well as half-precision floats. For example, here's how you can quantize a normal using 10-10-10 SNORM encoding:

unsigned int normal =
    ((meshopt_quantizeSnorm(v.nx, 10) & 1023) << 20) |
    ((meshopt_quantizeSnorm(v.ny, 10) & 1023) << 10) |
     (meshopt_quantizeSnorm(v.nz, 10) & 1023);

and here's how you can quantize a position using half precision floats:

unsigned short px = meshopt_quantizeHalf(v.x);
unsigned short py = meshopt_quantizeHalf(v.y);
unsigned short pz = meshopt_quantizeHalf(v.z);

Since quantized vertex attributes often need to remain in their compact representations for efficient transfer and storage, they are usually dequantized during vertex processing by configuring the GPU vertex input correctly to expect normalized integers or half precision floats, which often needs no or minimal changes to the shader code. When CPU dequantization is required instead, meshopt_dequantizeHalf can be used to convert half precision values back to single precision; for normalized integer formats, the dequantization just requires dividing by 2^N-1 for unorm and 2^(N-1)-1 for snorm variants. For example, manually reversing meshopt_quantizeUnorm(v, 10) can be done by dividing by 1023.

Index filtering

Some meshes may contain triangles that are processed during rendering but do not contribute to the rendered result. If any two vertices of a triangle result in the same position after vertex shader, the triangle is degenerate and will be skipped by the rasterizer. Some triangles may also be duplicates of an earlier triangle with the same post-transform positions and winding, in which case only one of the triangles will be visible depending on depth testing settings (assuming blending is disabled). In either case, such triangles require extra processing and removing them may improve rasterization or ray tracing performance; this library provides an algorithm that removes such triangles from the index buffer:

indices.resize(meshopt_filterIndexBuffer(&indices[0], &indices[0], indices.size(), &vertices[0].x, vertices.size(), sizeof(float) * 3, sizeof(Vertex)));

Note that the example above assumes only positions are relevant for transforming the vertices, but for deformable meshes skinning data may need to be added to the vertex portion used as a key; meshopt_filterIndexBufferMulti can be useful for these cases if the relevant data is not contiguous.

Filtering after quantization is convenient because quantization may increase the number of redundant triangles if triangles had similar but not identical vertex positions before quantization. However, filtering can be done at any point in the pipeline as soon as the index buffer becomes available; you could also run vertex fetch optimization after filtering, since it will naturally filter out any vertices that may become unused after redundant triangles are eliminated, potentially saving extra memory.

Shadow indexing

Many rendering pipelines require meshes to be rendered to depth-only targets, such as shadow maps or during a depth pre-pass, in addition to color/G-buffer targets. While using the same geometry data for both cases is possible, reducing the number of unique vertices for depth-only rendering can be beneficial, especially when the source geometry has many attribute seams due to faceted shading or lightmap texture seams.

To achieve this, this library provides the meshopt_generateShadowIndexBuffer algorithm, which generates a second (shadow) index buffer that can be used with the original vertex data:

std::vector shadow_indices(index_count);
// note: this assumes Vertex starts with float3 positions and should be adjusted accordingly for quantized positions
meshopt_generateShadowIndexBuffer(&shadow_indices[0], indices, index_count, &vertices[0].x, vertex_count, sizeof(float) * 3, sizeof(Vertex));

Because the vertex data is shared, shadow indexing should be done after other optimizations of the vertex/index data. However, it's possible (and recommended) to optimize the resulting shadow index buffer for vertex cache:

meshopt_optimizeVertexCache(&shadow_indices[0], &shadow_indices[0], index_count, vertex_count);

In some cases, it may be beneficial to split the vertex positions into a separate buffer to maximize efficiency for depth-only rendering. Note that the example above assumes only positions are relevant for shadow rendering, but more complex materials may require adding texture coordinates (for alpha testing) or skinning data to the vertex portion used as a key. meshopt_generateShadowIndexBufferMulti can be useful for these cases if the relevant data is not contiguous.

Note that for meshes with optimal indexing and few attribute seams, the shadow index buffer will be very similar to the original index buffer, so it may not be always worth generating a separate shadow index buffer even if the rendering pipeline relies on depth-only passes.

Clusterization

While traditionally meshes have served as a unit of rendering, new approaches to rendering and raytracing are starting to use a smaller unit of work, such as clusters or meshlets. This allows more freedom in how the geometry is processed, and can lead to better performance and more efficient use of GPU hardware. This section describes algorithms designed to work with meshes as sets of clusters.

Mesh shading

Modern GPUs can deviate from the traditional rasterization model. NVidia GPUs starting from Turing, AMD GPUs starting from RDNA2, Intel GPUs starting from Arc (Xe-HPG), and Apple GPUs starting from M3/A17 Pro provide a new programmable geometry pipeline that, instead of being built around index buffers and vertex shaders, is built around mesh shaders - a new shader type that allows to provide a batch of work to the rasterizer.

Using mesh shaders in context of traditional mesh rendering provides an opportunity to use a variety of optimization techniques, starting from more efficient vertex reuse, using various forms of culling (e.g. cluster frustum or occlusion culling) and in-memory compression to maximize the utilization of GPU hardware. Beyond traditional rendering mesh shaders provide a richer programming model that can synthesize new geometry more efficiently than common alternatives such as geometry shaders. Mesh shading can be accessed via Vulkan, Direct3D 12 or Metal APIs; please refer to Introduction to Turing Mesh Shaders and Mesh Shaders and Amplification Shaders: Reinventing the Geometry Pipeline for additional information.

To use mesh shaders for conventional rendering efficiently, geometry needs to be converted into a series of meshlets; each meshlet represents a small subset of the original mesh and comes with a small set of vertices and a separate micro-index buffer that references vertices in the meshlet. This information can be directly fed to the rasterizer from the mesh shader. This library provides algorithms to create meshlet data for a mesh, and - assuming geometry is static - can compute bounding information that can be used to perform cluster culling, rejecting meshlets that are invisible on screen.

To generate meshlet data, this library provides meshopt_buildMeshlets algorithm, which tries to balance topological efficiency (by maximizing vertex reuse inside meshlets) with culling efficiency (by minimizing meshlet radius and triangle direction divergence) and produces GPU-friendly data. As an alternative (that can be useful for load-time processing), meshopt_buildMeshletsScan can create the meshlet data using a vertex cache-optimized index buffer as a starting point by greedily aggregating consecutive triangles until they go over the meshlet limits. meshopt_buildMeshlets is recommended for offline data processing even if cone culling is not used.

const size_t max_vertices = 64;
const size_t max_triangles = 126; // note: in v0.25 or prior, max_triangles needs to be divisible by 4
const float cone_weight = 0.0f;
size_t max_meshlets = meshopt_buildMeshletsBound(indices.size(), max_vertices, max_triangles);
std::vector<meshopt_Meshlet> meshlets(max_meshlets);
std::vector meshlet_vertices(indices.size());
std::vector meshlet_triangles(indices.size()); // note: in v0.25 or prior, use indices.size() + max_meshlets * 3
size_t meshlet_count = meshopt_buildMeshlets(meshlets.data(), meshlet_vertices.data(), meshlet_triangles.data(), indices.data(),
    indices.size(), &vertices[0].x, vertices.size(), sizeof(Vertex), max_vertices, max_triangles, cone_weight);

To generate the meshlet data, max_vertices and max_triangles need to be set within limits supported by the hardware; for NVidia the values of 64 and 126 are recommended. cone_weight should be left as 0 if cluster cone culling is not used, and set to a value between 0 and 1 to balance cone culling efficiency with other forms of culling like frustum or occlusion culling (0.25 is a reasonable default).

Note that for earlier AMD GPUs, the best configurations tend to use the same limits for max_vertices and max_triangles, such as 64 and 64, or 128 and 128. Additionally, while NVidia recommends 64/126 as a good configuration, consider using a different configuration like max_vertices 64, max_triangles 96, to provide more realistic limits that are achievable on real-world meshes, and to reduce the overhead on other GPUs.

Each resulting meshlet refers to a portion of meshlet_vertices and meshlet_triangles arrays; the arrays are overallocated for the worst case so it's recommended to trim them before saving them as an asset / uploading them to the GPU:

const meshopt_Meshlet& last = meshlets[meshlet_count - 1];
meshlet_vertices.resize(last.vertex_offset + last.vertex_count);
meshlet_triangles.resize(last.triangle_offset + last.triangle_count * 3);
meshlets.resize(meshlet_count);

Depending on the application, other strategies of storing the data can be useful; for example, meshlet_vertices serves as indices into the original vertex buffer but it might be worthwhile to generate a mini vertex buffer for each meshlet to remove the extra indirection when accessing vertex data, or it might be desirable to compress vertex data as vertices in each meshlet are likely to be very spatially coherent.

Some proprietary platforms have additional restrictions on the index range that can be referenced by a meshlet. Building the library with MESHOPTIMIZER_CLUSTERIZER_INDEXLIMIT defined will ensure that generated meshlets conform to these restrictions, but the resulting meshlets can not be processed further as additional reordering may break the limits.

For optimal performance, it is recommended to further optimize each meshlet in isolation for better triangle and vertex locality by calling meshopt_optimizeMeshlet on vertex and index data like so:

meshopt_optimizeMeshlet(&meshlet_vertices[m.vertex_offset], &meshlet_triangles[m.triangle_offset], m.triangle_count, m.vertex_count);

Different applications will choose different strategies for rendering meshlets; on a GPU capable of mesh shading, meshlets can be rendered directly; for example, a basic GLSL shader for VK_EXT_mesh_shader extension could look like this (parts omitted for brevity):

```glsl layout(binding = 0) readonly buffer Meshlets { Meshlet meshlets[]; }; layout(binding = 1) readonly buffer MeshletVertices { uint meshlet_vertices[]; }; layout(binding = 2) readonly buffer MeshletTriangles { uint8_t meshlet_triangles[]; };

void main() { Meshlet meshlet = meshlets[gl_WorkGroupID.x]; SetMeshOutputsEXT(meshlet.vertex_count, meshlet.triangle_count);

for (uint i = gl_LocalInvocationI