forsyth

Tom Forsyth 的 线性速度顶点缓存优化 的纯 Rust 实现。

用法

此包提供了两种算法。

• order_triangles_inplace 和 order_triangles 用于排序三角形索引以最大化数据局部性。
• order_vertices 用于以某种方式排序顶点数据，以便在按顺序遍历索引数据时最大化顶点数据局部性。

这两个算法可以独立运行，但首先排序索引然后排序顶点可以获得最大好处。

请注意，Kerbel 等人. 2018 认为 GPU 缓存可能不会从这种排序中受益。然而，在按顺序处理索引和顶点数据时，可能存在一些用例可以从改进的数据局部性中受益，例如从持久存储中流式传输数据或使用 CPU 处理几何形状。

尽管原始论文的标题是，但该算法 不保证是严格的线性。存在一些病态情况，其运行时间可能更差，尤其是在有许多连接边（即高价态）的顶点很多的情况下。主要由非常细粒度的三角形扇形组成的网格是一个例子。然而，即使在这些情况下，也可以期望在当代 CPU 上每秒处理数十万个索引。

实际上，这两个算法足够快，可以将其应用于要多次处理或读取的几何形状。除了数据局部性之外，这两个算法可能有助于通过生成更多连续数据来提高后续压缩，这些数据对增量压缩和其他算法很有用。

use forsyth::{order_vertices,order_triangles};

let input_vertices = &['a', 'b', 'c', 'd', 'e'];
let input_indices = &[0_u32, 1, 2, 0, 1, 3, 0, 3, 4, 2, 1, 4];

// order indices first
let ordered_indices =
    order_triangles(input_indices).unwrap_or_else(|_| input_indices.to_vec());

assert_eq!(&ordered_indices, &[0, 3, 4, 0, 1, 3, 2, 1, 4, 0, 1, 2]);

// then order vertices and remap indices accordingly
let (ordered_vertices, ordered_indices) =
    order_vertices(input_vertices, ordered_indices.as_slice())
        .unwrap_or_else(|_| (input_vertices.to_vec(), ordered_indices));

assert_eq!(&ordered_vertices, &['a', 'd', 'e', 'b', 'c']);
assert_eq!(&ordered_indices, &[0, 1, 2, 0, 3, 1, 4, 3, 2, 0, 3, 4]);

本软件包是用 gitlab CI 制作的

• 它使用从 1.34 到最新版本 的 rust 版本进行构建和测试
• 测试覆盖率报告 由 cargo-tarpaulin 提供
• 模糊测试 由 cargo-fuzz 提供
• 基准测试 由 criterion 提供

最低支持的 Rust 版本 (MSRV)

forsyth 最低支持的 Rust 版本是 1.34.0

基准测试和测试模型

基准测试模型可以在 Morgan McGuire 的计算机图形存档中找到 https://casual-effects.com/data

许可证

许可证可以是以下之一

• MIT 许可证 (LICENSE-MIT 或 http://opensource.org/licenses/MIT)
• 无许可证 (LICENSE-UNLICENSE 或 https://opensource.org/licenses/unlicense)

任选其一。

贡献

任何形式的贡献（例如，问题、合并请求）应遵守 Rust 行为准则。

除非您明确表示，否则根据 MIT 许可证定义的，您有意提交以包含在您的工作中的任何贡献，将如上双许可，不附加任何额外的条款或条件。