Crate forsyth

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

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

Structs

Config

A struct holding the parameters controlling the algorithm

Enums

Error

An error or invariant violation during an ordering operation

Constants

DEFAULT_VERTEX_CACHE_SIZE

The default vertex cache size as suggested by the original paper

Functions

order_triangles

Creates an ordered triangle index buffer.

order_triangles_inplace

Orders a slice of triangle indices in place.

order_vertices

Orders a vertex buffer to maximize data locality.