#![deny(clippy::all)]
#![forbid(unsafe_code)]
use std::{
collections::{HashMap, VecDeque},
convert::{TryFrom, TryInto},
fmt::Display,
u32,
};
const MAX_VERTEX_CACHE_SIZE: u16 = std::u16::MAX - 1;
const NOT_IN_CACHE: u16 = std::u16::MAX;
const NULL_TRI: u32 = std::u32::MAX;
pub const DEFAULT_VERTEX_CACHE_SIZE: u16 = 32;
#[derive(Debug, Clone, Copy, PartialEq)]
pub enum Error {
IndicesNotTriples,
IndexToUsizeConversion,
TooManyTrianglesInTotal { limit: usize },
TooManyTrianglesAtVertex { vertex_idx: usize, limit: usize },
MalformedDrawList,
VertexOutOfBounds,
}
impl Display for Error {
fn fmt(&self, f: &mut std::fmt::Formatter<'_>) -> std::fmt::Result {
match self {
Error::IndicesNotTriples => f.write_str("elements are not all triples"),
Error::IndexToUsizeConversion => f.write_str("cannot convert Index to usize"),
Error::TooManyTrianglesInTotal { limit } => f.write_fmt(format_args!(
"too many triangles in total. {} triangles are supported",
limit,
)),
Error::TooManyTrianglesAtVertex { vertex_idx, limit } => f.write_fmt(format_args!(
"too many triangles connected to vertex {}. {} triangles are supported",
vertex_idx, limit,
)),
Error::MalformedDrawList => {
f.write_str("the generated ordered Index draw list is malformed")
}
Error::VertexOutOfBounds => f.write_str("the vertex index is out of bounds"),
}
}
}
#[derive(Debug, Clone, Copy, PartialEq)]
pub struct Config {
pub cache_decay_power: f32,
pub last_tri_score: f32,
pub valence_boost_scale: f32,
pub valence_boost_power: f32,
}
impl Default for Config {
fn default() -> Self {
Self {
cache_decay_power: 1.5,
last_tri_score: 0.75,
valence_boost_scale: 2.0,
valence_boost_power: 0.5,
}
}
}
#[derive(Clone, Debug)]
struct VertexInfo {
score: f32,
tri_list_ofs: u32,
cache_pos: u16,
num_tris_active: u16,
}
impl Default for VertexInfo {
fn default() -> Self {
Self {
cache_pos: NOT_IN_CACHE,
score: 0.0,
num_tris_active: 0,
tri_list_ofs: 0,
}
}
}
#[derive(Debug)]
struct TriangleInfo<Index> {
verts: [Index; 3],
score: f32,
added_to_draw_list: bool,
}
fn calculate_vertex_score(
config: &Config,
num_active_tris: u32,
cache_pos: u16,
vertex_cache_size: u16,
) -> f32 {
if num_active_tris == 0 {
-1.0f32
} else {
let valence_boost = (num_active_tris as f32).powf(-config.valence_boost_power);
let pos_score = if cache_pos < 3 {
config.last_tri_score
} else if cache_pos < vertex_cache_size {
let scaler = 1.0 / ((vertex_cache_size - 3) as f32);
(1.0 - ((cache_pos - 3) as f32) * scaler).powf(config.cache_decay_power)
} else {
0.0f32
};
pos_score + (config.valence_boost_scale * valence_boost)
}
}
pub fn order_triangles_inplace<Index>(
config: Config,
indices: &mut [Index],
vertex_cache_size: u16,
) -> Result<&[Index], Error>
where
Index: TryInto<usize> + std::default::Default + std::cmp::PartialEq + Copy,
{
let vertex_cache_size =
std::cmp::max(4, std::cmp::min(vertex_cache_size, MAX_VERTEX_CACHE_SIZE));
if indices.is_empty() || (indices.len() % 3) != 0 {
return Err(Error::IndexToUsizeConversion);
}
let num_tris = indices.len() / 3;
let (mut tris, mut verts, mut vertex_tri_list) = {
let mut tris: Vec<TriangleInfo<Index>> = Vec::with_capacity(num_tris);
let mut verts: Vec<VertexInfo> = Vec::with_capacity(indices.len());
let mut total_vertex_tris = 0;
for tri_idx in 0..num_tris {
let mut tri_verts = [Index::default(), Index::default(), Index::default()];
for (v, tri_vert) in tri_verts.iter_mut().enumerate() {
let element = (tri_idx * 3) + v;
let vertex_idx = indices[element];
*tri_vert = vertex_idx;
let vertex_idx: usize = if let Ok(vertex_idx) = vertex_idx.try_into() {
vertex_idx
} else {
return Err(Error::IndexToUsizeConversion);
};
if verts.len() < vertex_idx + 1 {
verts.resize(vertex_idx + 1, VertexInfo::default());
}
let vert: &mut VertexInfo = &mut verts[vertex_idx];
if vert.num_tris_active == std::u16::MAX {
return Err(Error::TooManyTrianglesAtVertex {
vertex_idx,
limit: std::u16::MAX as usize,
});
}
vert.num_tris_active += 1;
if total_vertex_tris == std::u32::MAX {
return Err(Error::TooManyTrianglesInTotal {
limit: std::usize::MAX,
});
}
total_vertex_tris += 1;
}
tris.push(TriangleInfo {
verts: tri_verts,
score: 0.0,
added_to_draw_list: false,
});
}
let mut vertex_tri_list = Vec::with_capacity(total_vertex_tris as usize);
for vert in &mut verts {
vert.tri_list_ofs = vertex_tri_list.len() as u32;
vertex_tri_list.resize(vertex_tri_list.len() + vert.num_tris_active as usize, 0u32);
vert.num_tris_active = 0;
}
for tri_idx in 0..num_tris {
for v in 0..3 {
let element = (tri_idx * 3) + v;
let vertex_idx = indices[element]
.try_into()
.map_err(|_| Error::IndexToUsizeConversion)?;
let vert: &mut VertexInfo = &mut verts[vertex_idx];
let tri_list = &mut vertex_tri_list[vert.tri_list_ofs as usize..];
tri_list[vert.num_tris_active as usize] = tri_idx as u32;
vert.num_tris_active += 1;
}
}
(tris, verts, vertex_tri_list)
};
let mut best_score_tri = (NULL_TRI, 0.0_f32);
for vert in &mut verts {
vert.score = calculate_vertex_score(
&config,
vert.num_tris_active as u32,
NOT_IN_CACHE,
vertex_cache_size,
);
for i in 0..vert.num_tris_active {
let tri_idx = vertex_tri_list[vert.tri_list_ofs as usize + i as usize];
let mut tri = &mut tris[tri_idx as usize];
tri.score += vert.score;
if best_score_tri.0 == NULL_TRI || tri.score > best_score_tri.1 {
best_score_tri = (tri_idx, tri.score);
}
}
}
let mut draw_list_cursor = 0;
let mut lru_cache: VecDeque<Index> = VecDeque::with_capacity(vertex_cache_size as usize + 3);
while best_score_tri.0 != NULL_TRI {
let mut best_tri = &mut tris[best_score_tri.0 as usize];
if best_tri.added_to_draw_list {
break;
}
best_tri.added_to_draw_list = true;
for v in &best_tri.verts {
let vertex_idx = *v;
let vertex_idx_usize: usize = vertex_idx
.try_into()
.map_err(|_| Error::IndexToUsizeConversion)?;
let vert = &mut verts[vertex_idx_usize];
let tri_list = &mut vertex_tri_list[vert.tri_list_ofs as usize
..vert.tri_list_ofs as usize + vert.num_tris_active as usize];
for (i, ti) in tri_list.iter().enumerate() {
if *ti == best_score_tri.0 {
vert.num_tris_active -= 1;
for rot in i..vert.num_tris_active as usize {
tri_list[rot] = tri_list[rot + 1];
}
break;
}
}
if let Some(draw_list_idx) = indices.get_mut(draw_list_cursor) {
*draw_list_idx = vertex_idx;
draw_list_cursor += 1;
} else {
return Err(Error::MalformedDrawList);
}
lru_cache.retain(|&i| i != vertex_idx);
lru_cache.push_front(vertex_idx);
}
best_score_tri = (NULL_TRI, 0.0);
for (cache_pos, vertex_idx) in lru_cache.iter().enumerate() {
let cache_pos = std::cmp::min(cache_pos, (MAX_VERTEX_CACHE_SIZE - 1) as usize) as u16;
let (new_score, old_score, tri_list_ofs, num_tris_active) = {
let vertex_idx: usize = (*vertex_idx)
.try_into()
.map_err(|_| Error::IndexToUsizeConversion)?;
let vert: &mut VertexInfo = &mut verts[vertex_idx];
vert.cache_pos = if cache_pos < vertex_cache_size {
cache_pos
} else {
NOT_IN_CACHE
};
let old_score = vert.score;
vert.score = calculate_vertex_score(
&config,
vert.num_tris_active as u32,
cache_pos,
vertex_cache_size,
);
(
vert.score,
old_score,
vert.tri_list_ofs,
vert.num_tris_active,
)
};
for tri_idx in &vertex_tri_list
[tri_list_ofs as usize..tri_list_ofs as usize + num_tris_active as usize]
{
let tri_idx = *tri_idx;
if tri_idx != NULL_TRI {
let tri = &mut tris[tri_idx as usize];
tri.score -= old_score;
tri.score += new_score;
if tri.added_to_draw_list {
continue;
}
if best_score_tri.0 == NULL_TRI || tri.score > best_score_tri.1 {
best_score_tri = (tri_idx, tri.score);
}
}
}
}
while lru_cache.len() > vertex_cache_size as usize {
lru_cache.pop_back();
}
if best_score_tri.0 == NULL_TRI {
if draw_list_cursor >= num_tris * 3 {
break;
}
for (tri_idx, tri) in tris.iter().enumerate() {
if tri.added_to_draw_list {
continue;
}
if best_score_tri.0 == NULL_TRI || tri.score > best_score_tri.1 {
best_score_tri = (tri_idx as u32, tri.score);
}
}
if best_score_tri.0 == NULL_TRI {
break;
}
}
}
if draw_list_cursor != num_tris * 3 {
return Err(Error::MalformedDrawList);
}
Ok(&indices[0..draw_list_cursor])
}
pub fn order_triangles<Index>(indices: &[Index]) -> Result<Vec<Index>, Error>
where
Index: std::convert::TryInto<usize> + std::default::Default + std::cmp::PartialEq + Copy,
{
if indices.is_empty() || (indices.len() % 3) != 0 {
return Err(Error::IndicesNotTriples);
}
let vertex_cache_size = DEFAULT_VERTEX_CACHE_SIZE;
let buffer = {
let mut buffer = Vec::with_capacity(indices.len());
buffer.extend_from_slice(indices);
order_triangles_inplace(Config::default(), buffer.as_mut_slice(), vertex_cache_size)?;
buffer
};
Ok(buffer)
}
pub fn order_vertices<Index, Vertex>(
vertices: &[Vertex],
indices: &[Index],
) -> Result<(Vec<Vertex>, Vec<Index>), Error>
where
Index: Copy + Eq + TryInto<usize> + TryFrom<usize> + std::hash::Hash,
Vertex: Copy,
{
let mut ordered_vertices = Vec::with_capacity(vertices.len());
let mut ordered_indices = Vec::with_capacity(indices.len());
let mut index_map: HashMap<Index, Index> = HashMap::with_capacity(indices.len());
for index in indices {
let mapped_idx = match index_map.entry(*index) {
std::collections::hash_map::Entry::Occupied(mapped) => *mapped.get(),
std::collections::hash_map::Entry::Vacant(vacant) => {
let index = (*index)
.try_into()
.map_err(|_| Error::IndexToUsizeConversion)?;
if let Some(vertex) = vertices.get(index) {
ordered_vertices.push(*vertex);
let mapped = (ordered_vertices.len() - 1)
.try_into()
.map_err(|_| Error::IndexToUsizeConversion)?;
*vacant.insert(mapped)
} else {
return Err(Error::VertexOutOfBounds);
}
}
};
ordered_indices.push(mapped_idx);
}
Ok((ordered_vertices, ordered_indices))
}
#[cfg(test)]
mod tests {
use super::*;
use proptest::collection::vec;
use proptest::prelude::*;
#[test]
fn error_formatting() {
for e in [
Error::IndexToUsizeConversion,
Error::IndicesNotTriples,
Error::TooManyTrianglesAtVertex {
vertex_idx: 123,
limit: 42,
},
Error::TooManyTrianglesInTotal { limit: 42 },
Error::MalformedDrawList,
Error::VertexOutOfBounds,
] {
assert_eq!(
format!("{}", e),
match e {
Error::IndicesNotTriples => "elements are not all triples",
Error::IndexToUsizeConversion => "cannot convert Index to usize",
Error::TooManyTrianglesInTotal { .. } =>
"too many triangles in total. 42 triangles are supported",
Error::TooManyTrianglesAtVertex { .. } =>
"too many triangles connected to vertex 123. 42 triangles are supported",
Error::MalformedDrawList =>
"the generated ordered Index draw list is malformed",
Error::VertexOutOfBounds => "the vertex index is out of bounds",
}
.to_string()
);
}
}
#[test]
fn config() {
assert_eq!(
Config {
cache_decay_power: 1.5,
last_tri_score: 0.75,
valence_boost_scale: 2.0,
valence_boost_power: 0.5,
},
Config::default()
);
}
#[test]
fn combined() {
let input_vertices = &['a', 'b', 'c', 'd', 'e'];
let input_indices = &[0_u32, 1, 2, 0, 1, 3, 0, 3, 4, 2, 1, 4];
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]);
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]);
}
#[test]
fn fuzz_regressions() {
{
assert_eq!(
order_triangles(&[i16::from_be_bytes([130_u8, 246])]),
Err(Error::IndicesNotTriples)
);
}
}
#[test]
fn sanity_checks() {
let mut cache = VecDeque::new();
cache.push_back(0);
cache.push_back(1);
cache.push_back(2);
cache.push_back(3);
cache.retain(|i| *i != 3);
assert_eq!(cache.len(), 3);
cache.push_front(3);
assert_eq!(cache, [3, 0, 1, 2]);
}
#[test]
fn test_vertex_score() {
const MAX_VERTEX_CACHE_SIZE: u16 = 32;
let config = Config::default();
for (cache_pos, ref_score) in [
(-2, config.valence_boost_scale),
(-1, config.valence_boost_scale),
(0, config.last_tri_score + config.valence_boost_scale),
(1, config.last_tri_score + config.valence_boost_scale),
(2, config.last_tri_score + config.valence_boost_scale),
(3, 3.0),
(4, 2.9487243),
(5, 2.8983564),
(6, 2.8489127),
(MAX_VERTEX_CACHE_SIZE as i32 - 1, 2.0064032),
(MAX_VERTEX_CACHE_SIZE as i32, config.valence_boost_scale),
(2 * MAX_VERTEX_CACHE_SIZE as i32, config.valence_boost_scale),
]
.iter()
{
let score = calculate_vertex_score(
&config,
1,
if *cache_pos < 0 {
MAX_VERTEX_CACHE_SIZE + 1
} else {
*cache_pos as u16
},
MAX_VERTEX_CACHE_SIZE,
);
assert!(
(score - ref_score).abs() <= f32::EPSILON,
"Score ({},{}) != ({},{})",
&cache_pos,
score,
&cache_pos,
&ref_score
);
}
}
#[test]
fn basic_triangle_ordering() {
{
let mut indices = [0_u16, 1, 2, 3, 2, 0, 0, 1, 3, 0, 1, 4, 0, 1, 5];
assert_eq!(
order_triangles_inplace(Config::default(), &mut indices, 32).unwrap(),
&[0, 1, 4, 0, 1, 5, 0, 1, 2, 3, 2, 0, 0, 1, 3]
);
}
assert_eq!(
order_triangles_inplace::<u32>(Config::default(), &mut [], 32),
Err(Error::IndexToUsizeConversion)
);
assert_eq!(
order_triangles_inplace(Config::default(), &mut [-1_i32, 0, 2], 32),
Err(Error::IndexToUsizeConversion)
);
assert_eq!(
order_triangles(&[0_u32, 1, 2, 0, 2, 3]).unwrap(),
[0, 1, 2, 0, 2, 3]
);
assert_eq!(
order_triangles(&Vec::<u32>::new()),
Err(Error::IndicesNotTriples)
);
assert_eq!(order_triangles(&[0]), Err(Error::IndicesNotTriples));
assert_eq!(order_triangles(&[0, 1]), Err(Error::IndicesNotTriples));
assert_eq!(order_triangles(&[0, 1, 2]).unwrap(), [0, 1, 2]);
assert_eq!(
order_triangles(&[0, 1, 2, 3]),
Err(Error::IndicesNotTriples)
);
assert_eq!(
order_triangles(&[0_u32, 1, 2, 3, 4, 5]).unwrap(),
[0, 1, 2, 3, 4, 5]
);
assert_eq!(
order_triangles(&[0_u16, 1, 2, 3, 4, 5]).unwrap(),
[0, 1, 2, 3, 4, 5]
);
assert_eq!(
order_triangles(&[0_u8, 1, 2, 3, 4, 5]).unwrap(),
[0, 1, 2, 3, 4, 5]
);
assert_eq!(
order_triangles(&[0_u64, 1, 2, 3, 4, 5]).unwrap(),
[0, 1, 2, 3, 4, 5]
);
assert_eq!(
order_triangles(&[0_i32, 1, 2, 3, 4, 5]).unwrap(),
[0, 1, 2, 3, 4, 5]
);
assert_eq!(
order_triangles(&[0_i16, 1, 2, 3, 4, 5]).unwrap(),
[0, 1, 2, 3, 4, 5]
);
assert_eq!(
order_triangles(&[0_i8, 1, 2, 3, 4, 5]).unwrap(),
[0, 1, 2, 3, 4, 5]
);
assert_eq!(
order_triangles(&[0_i64, 1, 2, 3, 4, 5]).unwrap(),
[0, 1, 2, 3, 4, 5]
);
assert_eq!(
order_triangles(&[0_usize, 1, 2, 3, 4, 5]).unwrap(),
[0, 1, 2, 3, 4, 5]
);
assert_eq!(
order_triangles(&[0_isize, 1, 2, 3, 4, 5]).unwrap(),
[0, 1, 2, 3, 4, 5]
);
assert_eq!(
order_triangles(&[0_u128, 1, 2, 3, 4, 5]).unwrap(),
[0, 1, 2, 3, 4, 5]
);
assert_eq!(
order_triangles(&[0_i128, 1, 2, 3, 4, 5]).unwrap(),
[0, 1, 2, 3, 4, 5]
);
assert_eq!(
order_triangles(&[0_i8, 1, 2, 63, 64, 65]).unwrap(),
[0, 1, 2, 63, 64, 65]
);
assert_eq!(
order_triangles(&[0_i8, -1, -2, 63, 64, 65]),
Err(Error::IndexToUsizeConversion)
);
{
let num_indices = 3 * 256;
let mut indices = Vec::with_capacity(num_indices);
for _ in 0..num_indices {
indices.push(indices.len());
}
for cs in [
0,
1,
2,
3,
4,
8,
16,
32,
64,
128,
256,
257,
std::u16::MAX - 1,
std::u16::MAX,
] {
let mut indices = indices.clone();
let result = order_triangles_inplace(Config::default(), indices.as_mut_slice(), cs);
assert!(result.is_ok(), "result is {:?}", result);
}
}
{
let mut indices = Vec::with_capacity((std::u16::MAX as usize) + 1);
for _ in 0..(std::u16::MAX as usize) + 1 {
indices.push(0);
indices.push(1);
indices.push(2);
}
assert_eq!(
order_triangles(indices.as_slice()),
Err(Error::TooManyTrianglesAtVertex {
vertex_idx: 0,
limit: 65535
})
);
}
}
#[test]
fn basic_vertex_ordering() {
assert_eq!(
order_vertices(&['a', 'b', 'c'], &[0, 1, 2]),
Ok((vec!['a', 'b', 'c'], vec![0, 1, 2]))
);
assert_eq!(
order_vertices(&['x', 'x', 'a', 'b', 'y', 'c'], &[2, 3, 5]),
Ok((vec!['a', 'b', 'c'], vec![0, 1, 2]))
);
assert_eq!(
order_vertices(&['a', 'b', 'c'], &[-1, 0, 2]),
Err(Error::IndexToUsizeConversion)
);
assert_eq!(
order_vertices(&['a', 'b', 'c'], &[0, 1, 3]),
Err(Error::VertexOutOfBounds)
);
}
#[test]
fn readme_test() {
let input_vertices = &['a', 'b', 'c', 'd', 'e'];
let input_indices = &[0_u32, 1, 2, 0, 1, 3, 0, 3, 4, 2, 1, 4];
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]);
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]);
}
proptest! {
#![proptest_config(ProptestConfig::with_cases(20000))]
#[test]
fn fuzz_order_triangles(mut indices in vec(0u8..32,3..32))
{
while indices.len() < 3 || indices.len() % 3 != 0 {
indices.push(0);
}
let mut ordered = order_triangles(&indices).expect("does not panic!");
assert_eq!(indices.len(),ordered.len());
indices.sort_unstable();
ordered.sort_unstable();
assert_eq!(indices,ordered);
}
}
}