A pure Rust implementation of Tom Forsyth's Linear-Speed Vertex Cache Optimisation.
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.
```rust use forsyth::{ordervertices,ordertriangles};
let inputvertices = &['a', 'b', 'c', 'd', 'e']; let inputindices = &[0_u32, 1, 2, 0, 1, 3, 0, 3, 4, 2, 1, 4];
// order indices first let orderedindices = ordertriangles(inputindices).unwraporelse(|| inputindices.tovec());
asserteq!(&orderedindices, &[0, 3, 4, 0, 1, 3, 2, 1, 4, 0, 1, 2]);
// then order vertices and remap indices accordingly let (orderedvertices, orderedindices) = ordervertices(inputvertices, orderedindices.asslice()) .unwraporelse(|| (inputvertices.tovec(), orderedindices));
asserteq!(&orderedvertices, &['a', 'd', 'e', 'b', 'c']); asserteq!(&orderedindices, &[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]
The minimum supported Rust version for forsyth is 1.34.0.
Models for benchmarking can be found in Morgan McGuire's Computer Graphics Archive https://casual-effects.com/data
Licensed under either of
LICENSE-MIT]
or http://opensource.org/licenses/MIT)LICENSE-UNLICENSE]
or https://opensource.org/licenses/unlicense)at your option.
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.