Crate forsyth[][src]

Expand description

This is a clean-room implementation of Tom Forsyth’s Linear-speed Vertex Cache Optimisation in Rust.

Two algorithms are provided in this crate.

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 (ie. 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]);


A struct holding the parameters controlling the algorithm


An error or invariant violation during an ordering operation


The default vertex cache size as suggested by the original paper


Creates an ordered triangle index buffer.

Orders a slice of triangle indices in place.

Orders a vertex buffer to maximize data locality.