# forsyth

[![pipeline status](https://gitlab.com/kento_asashima/forsyth/badges/master/pipeline.svg)](https://gitlab.com/kento_asashima/forsyth/-/commits/master)
[![coverage report](https://gitlab.com/kento_asashima/forsyth/badges/master/coverage.svg)](https://gitlab.com/kento_asashima/forsyth/-/commits/master)
[![crates.io](https://img.shields.io/crates/v/forsyth.svg)](https://crates.io/crates/forsyth/)
[![docs.rs](https://docs.rs/forsyth/badge.svg)](https://docs.rs/forsyth/)
[![Minimum Supported Rust Version](https://img.shields.io/badge/Rust-1.34.0-blue?color=fc8d62&logo=rust)](https://github.com/rust-lang/rust/blob/master/RELEASES.md#version-1340-2019-04-11)

A pure Rust implementation of Tom Forsyth's [Linear-Speed Vertex Cache Optimisation](https://tomforsyth1000.github.io/papers/fast_vert_cache_opt.html).

## 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.

```rust
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.


 [`Linear-speed Vertex Cache Optimisation`]: https://tomforsyth1000.github.io/papers/fast_vert_cache_opt.html
 [`Kerbel et al. 2018`]: https://arbook.icg.tugraz.at/schmalstieg/Schmalstieg_351.pdf
 [`GPU caching may not benefit from such ordering`]: https://www.highperformancegraphics.org/wp-content/uploads/2018/Papers-Session2/HPG2018_RevisitingVertexCache.pdf
 [`not guaranteed to be exactly linear`]: https://kento_asashima.gitlab.io/-/forsyth/-/jobs/1192073834/artifacts/target/criterion/order_triangles/report/index.html
 [`test coverage reporting`]: https://kento_asashima.gitlab.io/-/forsyth/-/jobs/1421605715/artifacts/cov/tarpaulin-report.html#src/lib.rs
 [`gitlab CI`]: https://gitlab.com/kento_asashima/forsyth/-/pipelines/336386578
 [`cargo-tarpaulin`]: https://crates.io/crates/cargo-tarpaulin
 [`1.34 to latest`]: https://gitlab.com/kento_asashima/forsyth/-/jobs/1421605710
 [`fuzzing`]: https://gitlab.com/kento_asashima/forsyth/-/jobs/1421605714
 [`cargo-fuzz`]: https://github.com/rust-fuzz/cargo-fuzz
 [`benchmarking`]: https://kento_asashima.gitlab.io/-/forsyth/-/jobs/1421605712/artifacts/target/criterion/report/index.html
 [`criterion`]: https://crates.io/crates/criterion

[`LICENSE-MIT`]: LICENSE-MIT
[`LICENSE-UNLICENSE`]: LICENSE-UNLICENSE
[`Code of Conduct`]: https://www.rust-lang.org/en-US/conduct.html