meshoptimizer：提升三角形网格渲染效率、降低存储开销的实用库及聚类算法揭秘

目的

GPU 渲染三角形网格时，其管线各阶段处理顶点和索引数据的效率取决于输入数据。`meshoptimizer` 库提供系列算法，可优化网格以提高渲染效率，同时降低网格复杂度和存储开销。该库为所有算法提供 C 和 C++ 接口，可在 C/C++ 中直接使用，也能通过 FFI（如 P/Invoke）在其他语言调用。若要在 Rust 中使用，可采用 `meshopt` crate；部分算法的 JavaScript 接口可通过 `meshoptimizer.js` 获取。此外，还有两个配套项目与该库一同开发和分发：`gltfpack`，一个自动优化 glTF 文件的命令行工具；`clusterlod.h`，一个用于通过聚类简化实现连续细节层次的单头 C/C++ 库。

安装

`meshoptimizer` 托管在 GitHub 上，可使用 `git` 下载最新版本：
```bash
git clone -b v1.2 https://github.com/zeux/meshoptimizer.git
```
也能从 GitHub 直接下载 `.zip` 存档。该库还作为 Linux 包在多个发行版（如 ArchLinux、Debian、FreeBSD、Nix、Ubuntu）中可用，同时提供 Vcpkg 端口和 Conan 包。`gltfpack` 可在 Releases 页面下载预编译二进制文件，也可通过 npm 包获取。建议使用原生二进制文件，因其更高效且支持纹理压缩。

构建

`meshoptimizer` 以 C/C++ 头文件（`src/meshoptimizer.h`）和一组 C++ 源文件（`src/*.cpp`）的形式分发。要将其集成到项目中，有两种选择：
- 使用 CMake 构建库（可作为独立项目或项目的一部分）。
- 将源文件添加到项目的构建系统中。
源文件的组织方式使得无需更改构建系统设置，只需添加所使用算法的源文件即可。这些源文件在所有主流编译器上编译时不会产生警告或需要特殊编译选项。若更喜欢合并构建，也可将源文件合并为一个 `.cpp` 文件进行构建。要使用 `meshoptimizer` 函数，只需包含头文件 `meshoptimizer.h`，该库的源代码是 C++，但头文件与 C 兼容。

核心管线

优化网格以最大化渲染效率，通常需按以下顺序进行一系列优化：

索引化

多数算法假设网格有顶点缓冲区和索引缓冲区。为使算法正常工作并让 GPU 高效渲染，顶点缓冲区不能有冗余顶点。可从无索引的顶点缓冲区生成索引缓冲区，或对现有（可能有冗余）的索引缓冲区重新索引。
注意：`meshoptimizer` 通常使用 32 位（`unsigned int`）索引，但在使用 C++ API 时，可通过提供的模板重载使用任何整数类型作为索引数据。按照惯例，重映射表始终使用 `unsigned int`。
首先，从现有的顶点（可选地，还有索引）数据生成重映射表：
```cpp
size_t index_count = face_count * 3;
size_t unindexed_vertex_count = face_count * 3;
std::vector remap(unindexed_vertex_count); // 临时重映射表
size_t vertex_count = meshopt_generateVertexRemap(&remap[0], NULL, index_count, &unindexed_vertices[0], unindexed_vertex_count, sizeof(Vertex));
```
在上述示例中，只有无索引的顶点缓冲区。若输入网格有索引缓冲区，则需将其传递给 `meshopt_generateVertexRemap` 而非 `NULL`，同时传递正确的源顶点数量。无论哪种情况，重映射表都是基于输入顶点的二进制等价性生成的，因此生成的网格渲染效果与原网格相同。二进制等价性考虑所有输入字节，包括填充字节，若顶点结构有间隙，填充字节应初始化为零。
生成重映射表后，可为目标顶点缓冲区（`vertex_count` 个元素）和索引缓冲区（`index_count` 个元素）分配空间并生成它们：
```cpp
meshopt_remapIndexBuffer(indices, NULL, index_count, &remap[0]);
meshopt_remapVertexBuffer(vertices, &unindexed_vertices[0], unindexed_vertex_count, sizeof(Vertex), &remap[0]);
```
然后，可通过对生成的缓冲区就地调用其他函数来进一步优化它们。
`meshopt_generateVertexRemap` 使用顶点数据的二进制等价性，这通常是合理的默认设置。然而，在某些情况下，某些属性可能存在浮点漂移，导致生成额外的顶点。对于这种情况，可能需要在生成重映射之前对某些属性（最重要的是法线和切线）进行量化，或使用 `meshopt_generateVertexRemapCustom` 算法，该算法允许通过提供自定义比较函数来容忍比较单个属性：
```cpp
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;
});
```

顶点缓存优化（可选）

GPU 渲染网格时，会为每个顶点运行顶点着色器。历史上，GPU 使用小型固定大小的后变换缓存（16 - 32 个顶点）和不同的替换策略来存储着色器输出，以避免冗余着色器调用。现代 GPU 仍进行顶点重用，但机制不同：顶点调用根据输入索引批量处理成线程组，有效重用取决于顶点着色器输出和光栅化器吞吐量等因素。
为最大化重用顶点引用的局部性，需重新排序三角形：
```cpp
meshopt_optimizeVertexCache(indices, indices, index_count, vertex_count);
```
不同 GPU 架构的顶点重用细节不同，因此顶点缓存优化使用自适应算法，生成具有良好局部性的三角形序列，适用于不同的 GPU。
也可使用专门针对固定大小 FIFO 缓存进行优化的算法：`meshopt_optimizeVertexCacheFifo`（推荐缓存大小为 16）。虽然它在大多数 GPU 上的性能通常较差，但运行速度快约 2 倍，这可能有利于快速内容迭代。

过绘制优化

顶点变换后，GPU 将三角形发送进行光栅化，生成的像素通常先经过深度测试，通过测试的像素会执行像素着色器以生成最终颜色。随着像素着色器成本的增加，减少过绘制变得越来越重要。
该库提供了一种算法，用于重新排序三角形以最小化各个方向的过绘制，可在顶点缓存优化后运行此算法：
```cpp
meshopt_optimizeOverdraw(indices, indices, index_count, &vertices[0].x, vertex_count, sizeof(Vertex), 1.05f);
```
过绘制优化器需要从顶点读取顶点位置作为 `float3`，上述代码片段假设顶点将位置存储为 `float x, y, z`。进行过绘制优化时，必须指定一个浮点阈值参数。该算法试图在顶点缓存效率和过绘制之间保持平衡，阈值决定了算法在多大程度上可以牺牲顶点缓存命中率，1.05 表示最终的命中率应比优化前最多差 5%。
请注意，根据渲染器结构和目标硬件，此优化可能有益也可能无益。例如，采用平铺延迟渲染的移动 GPU（如 PowerVR、Apple）不会从这种优化中受益。对于顶点密集的场景，建议测量性能影响，以确保减少的过绘制能够弥补顶点缓存效率的降低。

顶点获取优化

确定最终三角形顺序后，仍可优化顶点缓冲区以提高内存效率。在运行顶点着色器之前，GPU 必须从顶点缓冲区获取顶点属性，获取操作通常由内存缓存支持，因此优化数据的内存访问局部性很重要。
可通过运行以下代码来实现：
```cpp
meshopt_optimizeVertexFetch(vertices, indices, index_count, vertices, vertex_count, sizeof(Vertex));
```
这将重新排序顶点缓冲区中的顶点，以提高引用的局部性，并就地重写索引以匹配。如果顶点数据使用多个流存储，应该使用 `meshopt_optimizeVertexFetchRemap` 代替。此优化必须在最终索引缓冲区上执行，因为最佳顶点顺序取决于三角形顺序。
请注意，该算法并不试图精确模拟缓存替换，而是按使用顺序对顶点进行排序，通常能产生接近最优的结果。

顶点量化

为进一步优化顶点数据获取时的内存带宽，并减少存储网格所需的内存，通常将顶点属性量化为更小的类型是有益的。虽然此优化技术上可以在管线的任何部分运行（有时将量化作为第一步可以通过合并几乎相同的顶点来改善索引化），但通常在所有其他优化之后运行会更容易，因为其中一些优化需要访问 `float3` 位置。
量化通常是特定于领域的。常见的做法是使用 3 个 8 位整数来量化法线，但也可使用更高精度的量化（例如，在 10_10_10_2 格式中每个分量使用 10 位），或者使用不同的编码仅使用 2 个分量。对于位置和纹理坐标数据，两种最常见的存储格式是半精度浮点数和 16 位归一化整数，它们相对于网格的 AABB 或 UV 边界矩形对位置进行编码。
这里可能的组合数量非常大，但该库提供了基本构建块，特别是将浮点值量化为归一化整数以及半精度浮点数的函数。例如，可以使用 10 - 10 - 10 SNORM 编码来量化法线：
```cpp
unsigned int normal = ((meshopt_quantizeSnorm(v.nx, 10) & 1023) << 20) | ((meshopt_quantizeSnorm(v.ny, 10) & 1023) << 10) | (meshopt_quantizeSnorm(v.nz, 10) & 1023);
```
使用半精度浮点数量化位置：
```cpp
unsigned short px = meshopt_quantizeHalf(v.x);
unsigned short py = meshopt_quantizeHalf(v.y);
unsigned short pz = meshopt_quantizeHalf(v.z);
```
由于量化后的顶点属性通常需要以紧凑表示形式进行高效传输和存储，因此它们通常在顶点处理期间通过正确配置 GPU 顶点输入以期望归一化整数或半精度浮点数来进行反量化，这通常不需要或只需对着色器代码进行最小更改。
如果需要 CPU 反量化，可以使用 `meshopt_dequantizeHalf` 将半精度值转换回单精度；对于归一化整数格式，反量化只需将 unorm 变体除以 `2^N - 1`，将 snorm 变体除以 `2^(N - 1) - 1`。例如，手动反转 `meshopt_quantizeUnorm(v, 10)` 可以通过除以 1023 来完成。

索引过滤（可选）

某些网格可能包含在渲染过程中被处理但对渲染结果没有贡献的三角形。如果三角形的任意两个顶点在顶点着色器处理后得到相同的位置，则该三角形是退化的，将被光栅化器跳过。有些三角形可能是先前三角形的重复，具有相同的变换后位置和绕序，在这种情况下，根据深度测试设置（假设禁用混合），只有一个三角形会可见。
在这两种情况下，这些三角形都需要额外的处理，移除它们可能会提高光栅化或光线追踪性能。该库提供了一种算法，用于从索引缓冲区中移除这些三角形：
```cpp
indices.resize(meshopt_filterIndexBuffer(&indices[0], &indices[0], indices.size(), &vertices[0].x, vertices.size(), sizeof(float) * 3, sizeof(Vertex)));
```
上述示例假设只有位置对于变换顶点是相关的，但对于可变形网格，蒙皮数据可能需要添加到用作键的顶点部分中。如果相关数据不连续，`meshopt_filterIndexBufferMulti` 可能会很有用。
量化后进行过滤很方便，因为如果三角形在量化前具有相似但不相同的顶点位置，量化可能会增加冗余三角形的数量。然而，只要索引缓冲区可用，过滤可以在管线的任何点进行。也可在过滤后运行顶点获取优化，因为它自然会过滤掉在移除冗余三角形后可能变得未使用的任何顶点，从而可能节省额外的内存。

阴影索引化

许多渲染管线除了颜色/G 缓冲区目标外，还需要将网格渲染到仅深度目标（如阴影映射或深度预传递）。虽然可以对两种情况使用相同的几何数据，但减少仅深度渲染时的唯一顶点数量可能是有益的，特别是当源几何图形由于面状着色或光照贴图纹理接缝而有许多属性接缝时。
为实现这一点，该库提供了 `meshopt_generateShadowIndexBuffer` 算法，用于生成第二个（阴影）索引缓冲区，可与原始顶点数据一起使用：
```cpp
std::vector shadow_indices(index_count);
// 注意：此示例假设 Vertex 以 float3 位置开头，对于量化位置应相应调整
meshopt_generateShadowIndexBuffer(&shadow_indices[0], indices, index_count, &vertices[0].x, vertex_count, sizeof(float) * 3, sizeof(Vertex));
```
由于顶点数据是共享的，阴影索引化应该在对顶点/索引数据进行其他优化之后进行。然而，可以（并且建议）对生成的阴影索引缓冲区进行顶点缓存优化：
```cpp
meshopt_optimizeVertexCache(&shadow_indices[0], &shadow_indices[0], index_count, vertex_count);
```
在某些情况下，将顶点位置拆分为单独的缓冲区以最大化仅深度渲染的效率可能是有益的。
请注意，上述示例假设只有位置对于阴影渲染是相关的，但更复杂的材质可能需要将纹理坐标（用于 alpha 测试）或蒙皮数据添加到用作键的顶点部分中。如果相关数据不连续，`meshopt_generateShadowIndexBufferMulti` 可能会很有用。
对于具有最佳索引化和较少属性接缝的网格，阴影索引缓冲区将与原始索引缓冲区非常相似，因此即使渲染管线依赖于仅深度传递，也不一定值得生成单独的阴影索引缓冲区。

聚类

传统上，网格一直作为渲染的基本单位，但新的渲染和光线追踪方法开始使用更小的工作单位，如集群或网格小块（meshlets）。这为几何处理提供了更多的灵活性，并可以提高性能和更有效地利用 GPU 硬件。以下介绍旨在将网格作为集群集合处理的算法。

网格着色

现代 GPU 开始偏离传统的光栅化模型。从 Turing 开始的 NVIDIA GPU 和从 RDNA2 开始的 AMD GPU 提供了一种新的可编程几何管线，该管线围绕网格着色器（mesh shaders）构建，而不是基于索引缓冲区和顶点着色器。网格着色器是一种新的着色器类型，允许向光栅化器提供一批工作。
在传统网格渲染中使用网格着色器提供了使用各种优化技术的机会，包括更高效的顶点重用、使用各种形式的剔除（如集群视锥体或遮挡剔除）和内存压缩，以最大限度地利用 GPU 硬件。除了传统渲染，网格着色器还提供了更丰富的编程模型，可以比常见的替代方案（如几何着色器）更有效地合成新的几何图形。
可以通过 Vulkan 或 Direct3D 12 API 访问网格着色，更多信息请参考《Introduction to Turing Mesh Shaders》和《Mesh Shaders and Amplification Shaders: Reinventing the Geometry Pipeline》。
为了有效地将网格着色用于常规渲染，需要将几何图形转换为一系列网格小块。每个网格小块代表原始网格的一个小子集，并带有一小部分顶点和一个单独的微索引缓冲区，该缓冲区引用网格小块中的顶点。这些信息可以直接从网格着色器提供给光栅化器。
该库提供了为网格创建网格小块数据的算法，并且在几何图形静态的情况下，可以计算用于执行集群剔除的边界信息，从而剔除屏幕上不可见的网格小块。
为了生成网格小块数据，该库提供了 `meshopt_buildMeshlets` 算法，该算法试图在拓扑效率（通过最大化网格小块内的顶点重用）和剔除效率（通过最小化网格小块半径和三角形方向差异）之间取得平衡，并生成适合 GPU 的数据。作为替代方案（对于加载时处理可能有用），`meshopt_buildMeshletsScan` 可以使用经过顶点缓存优化的索引缓冲区作为起点，通过贪婪地聚合连续三角形，直到它们超过网格小块限制来创建网格小块数据。即使不使用锥体剔除，也建议在离线数据处理中使用 `meshopt_buildMeshlets`。
```cpp
const size_t max_vertices = 64;
const size_t max_triangles = 126;
// 注意：在 v0.25 或更早版本中，max_triangles 需要能被 4 整除
const float cone_weight = 0.0f;
size_t max_meshlets = meshopt_buildMeshletsBound(indices.size(), max_vertices, max_triangles);
std::vector meshlets(max_meshlets);
std::vector meshlet_vertices(indices.size());
std::vector meshlet_triangles(indices.size());
// 注意：在 v0.25 或更早版本中，使用 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);
```
为了生成网格小块数据，`max_vertices` 和 `max_triangles` 需要设置在硬件支持的范围内。对于 NVIDIA，推荐值为 64 和 126。如果不使用集群锥体剔除，`cone_weight` 应设置为 0；如果要在锥体剔除效率和其他形式的剔除（如视锥体或遮挡剔除）之间取得平衡，可以将其设置为 0 到 1 之间的值（0.25 是一个合理的默认值）。
请注意，对于早期的 AMD GPU，最佳配置通常使用相同的 `max_vertices` 和 `max_triangles` 限制，如 64 和 64，或 128 和 128。此外，虽然 NVIDIA 推荐 64/126 作为良好配置，但考虑使用不同的配置，如 `max_vertices` 为 64，`max_triangles` 为 96，以提供在实际网格上可实现的更现实的限制，并减少其他 GPU 上的开销。
每个生成的网格小块引用 `meshlet_vertices` 和 `meshlet_triangles` 数组的一部分。这些数组为最坏情况进行了过度分配，因此建议在将它们保存为资产或上传到 GPU 之前进行修剪：
```cpp
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);
```
根据应用程序的不同，其他存储数据的策略可能也很有用。例如，`meshlet_vertices` 作为原始顶点缓冲区的索引，但为每个网格小块生成一个迷你顶点缓冲区以消除访问顶点数据时的额外间接性可能是值得的，或者由于每个网格小块中的顶点在空间上可能非常连贯，压缩顶点数据可能是理想的。
为了获得最佳性能，建议通过对顶点和索引数据调用 `meshopt_optimizeMeshlet` 来进一步独立优化每个网格小块，以提高三角形和顶点的局部性：
```cpp
meshopt_optimizeMeshlet(&meshlet_vertices[m.vertex_offset], &meshlet_triangles[m.triangle_offset], m.triangle_count, m.vertex_count);
```
不同的应用程序将选择不同的策略来渲染网格小块。在支持网格着色的 GPU 上，可以直接渲染网格小块。例如，用于 `VK_EXT_mesh_shader` 扩展的基本 GLSL 着色器可能如下所示（为简洁起见省略了部分内容）：
```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_LocalInvocationIndex; i < meshlet.vertex_count; i += gl_WorkGroupSize.x) {
uint index = meshlet_vertices[meshlet.vertex_offset + i];
gl_MeshVerticesEXT[i].gl_Position = world_view_projection * vec4(vertex_positions[index], 1);
}
for (uint i = gl_LocalInvocationIndex; i < meshlet.triangle_count; i += gl_WorkGroupSize.x) {
uint offset = meshlet.triangle_offset + i * 3;
gl_PrimitiveTriangleIndicesEXT[i] = uvec3(meshlet_triangles[offset], meshlet_triangles[offset + 1], meshlet_triangles[offset + 2]);
}
}
```
请注意，DirectX 12 网格着色器不能使用任意字节偏移量对原始缓冲区进行索引。可以使用具有 `DXGI_FORMAT_R8_UINT` 格式的类型化 SRV 缓冲区（`Buffer`），将每个三角形重新打包为 32 位以能够使用对齐的 32 位加载与 `ByteAddressBuffer`，或者考虑使用 16 位标量类型通过两次对齐的 16 位加载来加载一个 3 字节的三角形，然后根据 `triangle_offset & 1` 使用按位操作提取索引。
生成网格小块数据后，可以为每个网格小块生成额外的数据，这些数据可以保存并在运行时用于执行集群剔除，如果某个网格小块保证不可见，则可以将其丢弃。为了生成这些数据，可以使用 `meshopt_computeMeshletBounds`：
```cpp
meshopt_Bounds bounds = meshopt_computeMeshletBounds(&meshlet_vertices[m.vertex_offset], &meshlet_triangles[m.triangle_offset], m.triangle_count, &vertices[0].x, vertices.size(), sizeof(Vertex));
```
生成的边界值可以用于使用边界球体执行视锥体或遮挡剔除，或者使用锥体轴/角度执行锥体剔除（如果从相机的角度看所有三角形都保证背向，则剔除整个网格小块）：
```cpp
if (dot(normalize(cone_apex - camera_position), cone_axis) >= cone_cutoff)
reject();
```
理想情况下，集群剔除的运行频率应低于网格着色，可以使用放大/任务着色器，或者使用单独的计算调度。
默认情况下，网格小块构建器试图形成完整的网格小块，即使这需要将网格的不相连区域合并为一个网格小块。在某些情况下，如分层细节层次，或使用高级剔除时，优先考虑网格小块中三角形的空间局部性可能是有益的，即使这会导致部分填充的网格小块。为此，可以使用 `meshopt_buildMeshletsFlex` 函数代替 `meshopt_buildMeshlets`。它提供了两个三角形限制，`min_triangles` 和 `max_triangles`，并使用一个额外的配置参数 `split_factor`（推荐值为 2.0）来决定是否值得增加网格小块半径以容纳更多三角形。使用此函数时，必须使用 `min_triangles` 参数而不是 `max_triangles` 来计算网格小块数量的最坏情况边界。

聚类光线追踪

除了光栅化，网格小块还可用于光线追踪。从 Turing 开始并使用最新驱动程序的 NVIDIA GPU 支持集群加速结构（通过 `VK_NV_cluster_acceleration_structure` 扩展 / NVAPI）。可以为每个网格小块构建一个集群加速结构，并将其组合成一个单一的聚类 BLAS。虽然目前这会导致静态几何图形的光线追踪性能降低（对于静态几何图形，传统的 BLAS 可能更合适），但它允许在不重建或重新拟合整个 BLAS 的情况下更新各个集群，这对于网格变形或分层细节层次可能很有用。
使用网格小块进行光线追踪时，重要的性能特征与使用光栅化渲染网格时不同。对于光线追踪，优先选择具有最佳空间划分的集群，以最小化光线 - 三角形相交测试；而对于光栅化，理想的是在顶点限制内具有最大三角形数量的集群。
为了生成针对光线追踪优化的网格小块，该库提供了 `meshopt_buildMeshletsSpatial` 算法，该算法使用表面积启发式（SAH）构建集群，以产生适合光线追踪的集群分布：
```cpp
const size_t max_vertices = 64;
const size_t min_triangles = 16;
const size_t max_triangles = 64;
const float fill_weight = 0.5f;
size_t max_meshlets = meshopt_buildMeshletsBound(indices.size(), max_vertices, min_triangles);
// 注意：使用 min_triangles 计算最坏情况边界
std::vector meshlets(max_meshlets);
std::vector meshlet_vertices(indices.size());
std::vector meshlet_triangles(indices.size());
// 注意：在 v0.25 或更早版本中，使用 indices.size() + max_meshlets * 3
size_t meshlet_count = meshopt_buildMeshletsSpatial(meshlets.data(), meshlet_vertices.data(), meshlet_triangles.data(), indices.data(), indices.size(), &vertices[0].x, vertices.size(), sizeof(Vertex), max_vertices, min_triangles, max_triangles, fill_weight);
```
该算法使用 SAH 递归地将三角形细分为类似 BVH 的层次结构，以实现最佳的空间划分，同时平衡集群大小。与 `meshopt_buildMeshlets` 生成的集群相比，这会产生在光线追踪方面效率显著更高的集群，但仍然可以用于光栅化（例如，构建可见性缓冲区或 G 缓冲区）。
`min_triangles` 和 `max_triangles` 参数控制每个集群允许的三角形范围。为了获得最佳的光线追踪性能，`min_triangles` 应最多为 `max_triangles / 2`（理想情况下为 `max_triangles / 4`），以便算法有足够的自由度来产生高质量的空间划分。
对于由于法线或 UV 不连续性而接缝较少的网格，当考虑光栅化性能时，建议使用 `max_vertices` 等于 `max_triangles`；对于有许多接缝的网格或主要使用网格小块进行光线追踪的渲染器，应使用更高的 `max_vertices` 值，以确保更多的集群可以充分利用三角形限制。
`fill_weight` 参数（通常在 0 到 1 之间，尽管也可以使用大于 1 的值来更优先考虑集群填充）控制纯 SAH 优化和三角形利用率之间的权衡。值为 0 将纯粹针对 SAH 进行优化，从而获得最佳的光线追踪性能，但可能会产生较小的集群。0.25 到 0.75 之间的值通常可以在 SAH 质量和三角形数量之间取得良好的平衡。
当使用生成的网格小块生成特定于硬件的加速结构时，使用快速跟踪（如 `VK_BUILD_ACCELERATION_STRUCTURE_PREFER_FAST_TRACE_BIT_KHR`）构建可获得最大性能；如果构建性能很重要，使用 `meshopt_optimizeMeshlet` 可以在使用快速构建（如 `VK_BUILD_ACCELERATION_STRUCTURE_PREFER_FAST_BUILD_BIT_KHR`）时帮助提高光线追踪性能，尽管跟踪性能仍会低于快速跟踪构建。

点云聚类

两个网格小块算法都设计用于处理三角形网格。在某些情况下，将点云分割成固定大小的集群可能很有用。生成的点集群可以通过网格或计算着色器进行渲染，或者生成的细分可以用于并行化点处理，同时保持点的局部性。
为此，该库提供了 `meshopt_spatialClusterPoints` 算法：
```cpp
const size_t cluster_size = 256;
std::vector index(vertices.size());
meshopt_spatialClusterPoints(&index[0], &vertices[0].px, vertices.size(), sizeof(Vertex), cluster_size);
```
生成的索引缓冲区可以用于直接处理点，或者将点数据重新组织为扁平连续的数组。索引缓冲区中每连续的 `cluster_size` 个点块引用一个单一的集群，如果点的总数不是 `cluster_size` 的倍数，则最后一个集群包含的点较少。
请注意，索引缓冲区不是重映射表，因此不能使用 `meshopt_remapVertexBuffer` 来扁平化点数据。

集群分区

处理聚类几何图形时，将集群组织成更大的组（分区）以进行更高效的处理或工作负载分配可能是有益的。该库提供了一种算法，用于将集群划分为大小相似的组，同时优先考虑局部性：
```cpp
const size_t partition_size = 24;
std::vector cluster_partitions(cluster_count);
size_t partition_count = meshopt_partitionClusters(&cluster_partitions[0], &cluster_indices[0], total_index_count, &cluster_index_counts[0], cluster_count, &vertices[0].x, vertex_count, sizeof(Vertex), partition_size);
```
该算法将每个集群分配到一个分区，目标是达到目标分区大小，同时优先考虑拓扑局部性（共享顶点）和空间局部性。生成的分区可用于更高效的集群批量处理，或用于类似于 Nanite 的分层简化方案。
如果两个集群引用相同的索引，则它们被认为是拓扑相邻的。在某些情况下，使用 `meshopt_generateShadowIndexBuffer` 处理索引（或使用 `meshopt_generatePositionRemap` 生成的重映射表手动重映射它们）可能会有所帮助，这样即使边界顶点由于属性不连续性而具有不同的索引，集群也可以被视为相邻。
如果指定了顶点位置（不为 `NULL`），空间局部性将影响合并集群的优先级；否则，算法将仅依赖拓扑连接，不会将不相连的集群合并到同一分区中，这可能会导致某些输入的分区较小。
分区后，目标数组中的每个元素包含相应集群的分区 ID（范围从 0 到返回的分区数量减 1）。请注意，分区可能比目标大小小或大；给定一个目标大小，当前返回的最大分区大小为目标大小加上目标大小的 1/3。

集群位置量化

处理聚类几何图形时，可以对顶点位置使用基于集群的相对量化。具体来说，一种常见的表示方法是将位置量化到一个整数网格上，集群之间共享一个指数，以避免在不同集群之间对共享顶点进行不同的量化，并将每个位置存储为相对于集群锚点的偏移量。DXR2 支持一种称为 Compressed1 位置编码的这种表示变体。
该库提供了一个辅助函数 `meshopt_computePositionExponent`，可用于计算指数，以及一个示例（见 `demo/main.cpp` 中的 `encodeMeshletsDXR`）展示完整的管线。
首先，计算共享指数，以确保每个集群中的任何顶点都能适应 24 位有符号整数，并且还可以编码为相对于每个集群锚点的 K 位无符号增量（在下面的示例中，K = 16，与 DXR2 限制匹配）：
```cpp
const int min_exp = -13; // 从可接受的精度级别开始；2^-13 ~= 0.1mm（公制单位）
const int max_bits = 16; // 每个轴的最大偏移位数
int exponent = min_exp;
for (size_t i = 0; i < meshlets.size(); ++i) {
AABB meshlet_aabb = ...; // 根据顶点位置计算网格小块的 AABB
int cexp = meshopt_computePositionExponent(meshlet_aabb.min, meshlet_aabb.max, min_exp, max_bits);
exponent = std::max(exponent, cexp);
}
float scale = ldexpf(1.f, exponent);
```
之后，每个集群可以独立编码。编码每个位置时，应将位置转换为整数网格，并确定锚点：
```cpp
int positions[256][3];
int anchor[3] = {INT_MAX, INT_MAX, INT_MAX};
for (size_t j = 0; j < meshlet.vertex_count; ++j) {
unsigned int v = meshlet_vertices[meshlet.vertex_offset + j];
const float* p = &vertices[v].px;
for (int k = 0; k < 3; ++k) {
positions[j][k] = int(roundf(p[k] / scale));
anchor[k] = std::min(anchor[k], positions[j][k]);
}
}
```
指数选择保证了对于每个集群，我们得到 24 位的锚点分量，并且对于每个顶点位置 `[k] - anchor[k]` 可以适应 16 位无符号整数。
然后，可以使用固定宽度的 16 位编码对位置进行编码，每个顶点 6 个字节。然而，由于许多集群需要的位数较少，更有效的方法是确定每个集群每个轴的位数（通过计算足以……