forsyth

A pure Rust implementation of Tom Forsyth's Linear-Speed Vertex Cache Optimisation.

Usage

Two algorithms are provided in this crate.

• order_triangles_inplace and order_triangles to order triangle indices to maximize data locality.
• order_vertices to order vertex data in such an way, that vertex data locality is maximized when iterating sequentially through index data.

Both algorithms can be run independently, but ordering indices first and then ordering vertices provides most benefits.

Note that Kerbel et al. 2018 argued that GPU caching may not benefit from such ordering. However, there may be use cases that benefit from improved data locality when sequentially processing index and vertex data, such as when streaming data from persistent storage or when processing geometry with CPUs.

Despite the original paper's title, the algorithm is not guaranteed to be exactly linear. There are pathological cases where runtime can be worse, especially when there are many vertices with many connected edges (i.e. high valence). Meshes mostly containing very fine-grained triangle fans are an example. However, one can still expect a throughput of hundreds of thousand indices per second on contemporary CPUs even for these cases.

In practice, both algorithms are fast enough to opportunistically apply them to geometry to be processed or read multiple times. Apart from data locality, both algorithms may be useful to improve subsequent compression by producing more contiguous data useful for delta compression and other algorithms.

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]);

This crate is made using gitlab CI:

• it is built and tested with rust versions from 1.34 to latest
• test coverage reporting is provided by cargo-tarpaulin
• fuzzing is provided by cargo-fuzz
• benchmarking is provided by criterion

Minimum Supported Rust Version (MSRV)

The minimum supported Rust version for forsyth is 1.34.0.

Benchmarking and Test Models

Models for benchmarking can be found in Morgan McGuire's Computer Graphics Archive https://casual-effects.com/data

License

Licensed under either of

• MIT license (LICENSE-MIT or http://opensource.org/licenses/MIT)
• Unlicense (LICENSE-UNLICENSE or https://opensource.org/licenses/unlicense)

at your option.

Contribution

Contributions in any form (e.g. issues, merge requests) shall adhere to Rust Code of Conduct.

Unless you explicitly state otherwise, any contribution intentionally submitted for inclusion in the work by you, as defined in the MIT license, shall be dual licensed as above, without any additional terms or conditions.