use crate::budget::Budget;
use crate::workspace::{checked_bytes, output, topology, Work};
use crate::{Error, Workspace};
use alloc::vec::Vec;
const CACHE: [f32; 17] = [
0., 0.779, 0.791, 0.789, 0.981, 0.843, 0.726, 0.847, 0.882, 0.867, 0.799, 0.642, 0.613, 0.600,
0.568, 0.372, 0.234,
];
const LIVE: [f32; 9] = [0., 0.995, 0.713, 0.450, 0.404, 0.059, 0.005, 0.147, 0.006];
const STRIP_CACHE: [f32; 17] = [
0., 1., 1., 1., 0.453, 0.561, 0.490, 0.459, 0.179, 0.526, 0., 0.227, 0.184, 0.490, 0.112,
0.050, 0.131,
];
const STRIP_LIVE: [f32; 9] = [0., 0.956, 0.786, 0.577, 0.558, 0.618, 0.549, 0.499, 0.489];
#[derive(Clone, Debug, PartialEq)]
pub struct VertexScoreTable {
cache: [f32; 17],
live: [f32; 9],
}
impl VertexScoreTable {
pub fn new(cache: &[f32], live: &[f32]) -> Result<Self, Error> {
if cache.len() != 17 || live.len() != 9 || !cache.iter().chain(live).all(|s| s.is_finite())
{
return Err(Error::InvalidParameter);
}
let mut table = Self::default();
table.cache.copy_from_slice(cache);
table.live.copy_from_slice(live);
Ok(table)
}
pub fn cache_scores(&self) -> &[f32; 17] {
&self.cache
}
pub fn live_scores(&self) -> &[f32; 9] {
&self.live
}
}
impl Default for VertexScoreTable {
fn default() -> Self {
Self {
cache: CACHE,
live: LIVE,
}
}
}
trait Scores {
fn score(&self, position: usize, live: u32) -> f32;
}
struct Preset<const STRIP: bool>;
impl<const STRIP: bool> Scores for Preset<STRIP> {
fn score(&self, position: usize, live: u32) -> f32 {
if STRIP {
STRIP_CACHE[position] + STRIP_LIVE[live.min(8) as usize]
} else {
CACHE[position] + LIVE[live.min(8) as usize]
}
}
}
impl Scores for VertexScoreTable {
fn score(&self, position: usize, live: u32) -> f32 {
self.cache[position] + self.live[live.min(8) as usize]
}
}
#[inline]
pub fn optimize_vertex_cache_with_table_generic<I: crate::Index>(
indices: &[I],
vertex_count: usize,
table: &VertexScoreTable,
workspace: &mut Workspace,
) -> Result<Vec<I>, Error> {
I::with_input(indices, workspace, |indices, workspace| {
optimize_vertex_cache_with_table_u32(indices, vertex_count, table, workspace)
.and_then(|value| crate::index::Convert::<I>::convert(value, workspace))
})
}
fn optimize_vertex_cache_with_table_u32(
indices: &[u32],
vertex_count: usize,
table: &VertexScoreTable,
workspace: &mut Workspace,
) -> Result<Vec<u32>, Error> {
let mut work = workspace.begin();
let result = (|| {
topology(indices, vertex_count, &mut work)?;
prepare(
indices.len(),
vertex_count,
checked_bytes(indices.len(), 4)?,
workspace,
)?;
let mut destination = output(indices.len())?;
kernel(
&mut destination,
indices,
vertex_count,
workspace,
&mut work,
table,
)?;
Ok(destination)
})();
workspace.finish(&work);
result
}
#[inline]
pub fn optimize_vertex_cache_with_table_into_generic<I: crate::Index>(
destination: &mut [I],
indices: &[I],
vertex_count: usize,
table: &VertexScoreTable,
workspace: &mut Workspace,
) -> Result<(), Error> {
I::with_input(indices, workspace, |indices, workspace| {
I::with_mut(destination, workspace, |destination, workspace| {
optimize_vertex_cache_with_table_into_u32(
destination,
indices,
vertex_count,
table,
workspace,
)
})
})
}
fn optimize_vertex_cache_with_table_into_u32(
destination: &mut [u32],
indices: &[u32],
vertex_count: usize,
table: &VertexScoreTable,
workspace: &mut Workspace,
) -> Result<(), Error> {
let mut work = workspace.begin();
let result = (|| {
topology(indices, vertex_count, &mut work)?;
if destination.len() < indices.len() {
return Err(Error::BufferTooSmall);
}
prepare(indices.len(), vertex_count, 0, workspace)?;
kernel(
destination,
indices,
vertex_count,
workspace,
&mut work,
table,
)
})();
workspace.finish(&work);
result
}
#[inline]
pub fn optimize_vertex_cache_generic<I: crate::Index>(
indices: &[I],
vertex_count: usize,
workspace: &mut Workspace,
) -> Result<Vec<I>, Error> {
I::with_input(indices, workspace, |indices, workspace| {
optimize_vertex_cache_u32(indices, vertex_count, workspace)
.and_then(|value| crate::index::Convert::<I>::convert(value, workspace))
})
}
fn optimize_vertex_cache_u32(
indices: &[u32],
vertex_count: usize,
workspace: &mut Workspace,
) -> Result<Vec<u32>, Error> {
let mut work = workspace.begin();
let result = (|| {
topology(indices, vertex_count, &mut work)?;
prepare(
indices.len(),
vertex_count,
checked_bytes(indices.len(), 4)?,
workspace,
)?;
let mut destination = output(indices.len())?;
kernel(
&mut destination,
indices,
vertex_count,
workspace,
&mut work,
&Preset::<false>,
)?;
Ok(destination)
})();
workspace.finish(&work);
result
}
#[inline]
pub fn optimize_vertex_cache_into_generic<I: crate::Index>(
destination: &mut [I],
indices: &[I],
vertex_count: usize,
workspace: &mut Workspace,
) -> Result<(), Error> {
I::with_input(indices, workspace, |indices, workspace| {
I::with_mut(destination, workspace, |destination, workspace| {
optimize_vertex_cache_into_u32(destination, indices, vertex_count, workspace)
})
})
}
fn optimize_vertex_cache_into_u32(
destination: &mut [u32],
indices: &[u32],
vertex_count: usize,
workspace: &mut Workspace,
) -> Result<(), Error> {
let mut work = workspace.begin();
let result = (|| {
topology(indices, vertex_count, &mut work)?;
if destination.len() < indices.len() {
return Err(Error::BufferTooSmall);
}
prepare(indices.len(), vertex_count, 0, workspace)?;
kernel(
destination,
indices,
vertex_count,
workspace,
&mut work,
&Preset::<false>,
)
})();
workspace.finish(&work);
result
}
#[inline]
pub fn optimize_vertex_cache_in_place_generic<I: crate::Index>(
indices: &mut [I],
vertex_count: usize,
workspace: &mut Workspace,
) -> Result<(), Error> {
I::with_mut(indices, workspace, |indices, workspace| {
optimize_vertex_cache_in_place_u32(indices, vertex_count, workspace)
})
}
fn optimize_vertex_cache_in_place_u32(
indices: &mut [u32],
vertex_count: usize,
workspace: &mut Workspace,
) -> Result<(), Error> {
let result = optimize_vertex_cache_generic(indices, vertex_count, workspace)?;
indices.copy_from_slice(&result);
Ok(())
}
fn prepare(n: usize, v: usize, out: usize, ws: &mut Workspace) -> Result<(), Error> {
ws.acquire(crate::workspace::ScratchFamily::Cache);
if n == 0 {
return ws.prepare([0; 4], out);
}
let faces = n / 3;
ws.prepare_cache([n, faces, faces, 0], v, out)
}
fn kernel<S: Scores>(
dest: &mut [u32],
indices: &[u32],
v: usize,
ws: &mut Workspace,
work: &mut Work,
scores: &S,
) -> Result<(), Error> {
if indices.is_empty() {
return Ok(());
}
let faces = indices.len() / 3;
let vertices = &mut ws.vertices[..v];
let adjacency = &mut ws.integers[..indices.len()];
let triangle_scores = &mut ws.floats[..faces];
let emitted = &mut ws.flags[..faces];
let triangles = indices.as_chunks::<3>().0;
let destination = dest[..indices.len()].as_chunks_mut::<3>().0;
assert_eq!(triangles.len(), triangle_scores.len());
assert_eq!(triangles.len(), emitted.len());
work.add(v)?;
for vertex in vertices.iter_mut() {
vertex.live = 0;
}
work.scan(indices.iter().copied(), |index| {
vertices[index as usize].live += 1;
Ok(())
})?;
let mut offset = 0;
work.scan(vertices.iter_mut(), |vertex| {
vertex.offset = offset;
offset += vertex.live;
Ok(())
})?;
if work.precharge(indices.len(), 1)? {
for (i, triangle) in triangles.iter().enumerate() {
for &index in triangle {
let vertex = &mut vertices[index as usize];
adjacency[vertex.offset as usize] = i as u32;
vertex.offset += 1;
}
}
} else {
for (i, triangle) in indices.as_chunks::<3>().0.iter().enumerate() {
for &index in triangle {
work.add(1)?;
let j = index as usize;
let vertex = &mut vertices[j];
adjacency[vertex.offset as usize] = i as u32;
vertex.offset += 1;
}
}
}
let mut max_live = 0usize;
work.scan(vertices.iter_mut(), |vertex| {
max_live = max_live.max(vertex.live as usize);
vertex.offset -= vertex.live;
vertex.score = scores.score(0, vertex.live);
Ok(())
})?;
work.add(faces)?;
emitted.fill(0);
work.scan(
triangle_scores[..faces].iter_mut().zip(triangles),
|(s, triangle)| {
*s = vertices[triangle[0] as usize].score
+ vertices[triangle[1] as usize].score
+ vertices[triangle[2] as usize].score;
Ok(())
},
)?;
let bound = max_live
.checked_mul(22)
.and_then(|n| n.checked_add(38))
.and_then(|n| faces.checked_mul(n));
if let Some(bound) = bound.filter(|&n| work.covers(n) == Ok(true)) {
work.add(bound)?;
let visits = cache_loop_covered(
destination,
triangles,
vertices,
adjacency,
triangle_scores,
emitted,
scores,
);
debug_assert!(visits <= bound, "cache work bound overrun");
work.refund_cache(bound.saturating_sub(visits));
Ok(())
} else {
cache_loop_limited(
destination,
triangles,
vertices,
adjacency,
triangle_scores,
emitted,
work,
scores,
)
}
}
#[inline(always)]
fn merge(
next: &mut [u32; 32],
old: &[u32; 32],
count: usize,
mut live: u32,
[a, b, c]: [u32; 3],
) -> (usize, u32) {
let mut matched = 0u32;
for (k, &index) in old[..16].iter().enumerate() {
matched |= u32::from((index == a) | (index == b) | (index == c)) << k;
}
matched &= (1u32 << count.min(16)) - 1;
if matched == 0 {
next[3..19].copy_from_slice(&old[..16]);
} else {
let mut write = 3;
for (k, &index) in old[..16].iter().enumerate() {
next[write & 31] = index;
write += (!matched >> k & 1) as usize;
}
let mut pending = matched;
while pending != 0 {
let slot = 31 - pending.leading_zeros();
pending &= !(1 << slot);
let below = (1u32 << slot) - 1;
live = (live & below) | (live >> 1 & !below);
}
}
(3 + count.min(16) - matched.count_ones() as usize, live << 3)
}
#[inline(never)]
#[allow(clippy::too_many_arguments)]
fn cache_loop_covered<S: Scores>(
destination: &mut [[u32; 3]],
triangles: &[[u32; 3]],
vertices: &mut [crate::workspace::CacheVertex],
adjacency: &mut [u32],
triangle_scores: &mut [f32],
emitted: &mut [u8],
scores: &S,
) -> usize {
let faces = triangles.len();
assert_eq!(faces, triangle_scores.len());
assert_eq!(faces, emitted.len());
let mut cache_storage = [0u32; 32];
let mut next_storage = [0u32; 32];
let mut cache = &mut cache_storage;
let mut next = &mut next_storage;
let mut cache_count = 0;
let mut live = 0u32;
let mut current = 0usize;
let mut cursor = 1usize;
let mut emitted_count = 0;
let mut visits = 0usize;
while current != usize::MAX {
visits += 1;
let triangle = triangles[current];
destination[emitted_count] = triangle;
emitted_count += 1;
emitted[current] = 1;
triangle_scores[current] = 0.;
next[..3].copy_from_slice(&triangle);
visits += cache_count;
let (write, carried) = merge(next, cache, cache_count, live, triangle);
core::mem::swap(&mut cache, &mut next);
cache_count = write.min(16);
let current_id = current as u32;
for index in triangle {
let vertex = &mut vertices[index as usize];
let start = vertex.offset as usize;
let count = vertex.live as usize;
let adjacent = &mut adjacency[start..start + count];
match adjacent.iter().position(|&tri| tri == current_id) {
Some(i) => {
visits += i + 1;
adjacent[i] = adjacent[count - 1];
vertex.live -= 1;
}
None => visits += count,
}
}
let [a, b, c] = triangle;
let fresh = u32::from(vertices[a as usize].live != 0)
| u32::from(vertices[b as usize].live != 0) << 1
| u32::from(vertices[c as usize].live != 0) << 2;
let mut pending = carried | fresh;
live = pending & 0xffff;
visits += write;
let mut best = usize::MAX;
let mut best_score = 0.;
while pending != 0 {
let i = pending.trailing_zeros() as usize;
pending &= pending - 1;
let vertex = &mut vertices[cache[i & 31] as usize];
let s = scores.score(if i >= 16 { 0 } else { i + 1 }, vertex.live);
let diff = s - vertex.score;
vertex.score = s;
let start = vertex.offset as usize;
let count = vertex.live as usize;
visits += count;
for &tri in &adjacency[start..start + count] {
let tri = tri as usize;
let s = triangle_scores[tri] + diff;
if best_score < s {
best = tri;
best_score = s;
}
triangle_scores[tri] = s;
}
}
current = best;
if current == usize::MAX {
while cursor < faces {
visits += 1;
if emitted[cursor] == 0 {
current = cursor;
break;
}
cursor += 1;
}
}
}
visits
}
#[inline(never)]
#[allow(clippy::too_many_arguments)]
fn cache_loop_limited<S: Scores>(
destination: &mut [[u32; 3]],
triangles: &[[u32; 3]],
vertices: &mut [crate::workspace::CacheVertex],
adjacency: &mut [u32],
triangle_scores: &mut [f32],
emitted: &mut [u8],
work: &mut Work,
scores: &S,
) -> Result<(), Error> {
let faces = triangles.len();
assert_eq!(triangles.len(), triangle_scores.len());
assert_eq!(triangles.len(), emitted.len());
let mut cache_storage = [0u32; 20];
let mut next_storage = [0u32; 20];
let mut cache = &mut cache_storage;
let mut next = &mut next_storage;
let mut cache_count = 0;
let mut current = 0usize;
let mut cursor = 1usize;
let mut emitted_count = 0;
while current != usize::MAX {
work.add(1)?;
let triangle = &triangles[current];
destination[emitted_count].copy_from_slice(triangle);
emitted_count += 1;
emitted[current] = 1;
triangle_scores[current] = 0.;
next[..3].copy_from_slice(triangle);
let mut write = 3;
assert!(cache_count <= 16);
work.scan(cache[..cache_count].iter().copied(), |index| {
next[write] = index;
write += usize::from(!triangle.contains(&index));
Ok(())
})?;
core::mem::swap(&mut cache, &mut next);
cache_count = write.min(16);
for &index in triangle {
let j = index as usize;
let vertex = &mut vertices[j];
let start = vertex.offset as usize;
let count = vertex.live as usize;
let adjacent = &mut adjacency[start..start + count];
let found = work.search(count, |i| adjacent[i] == current as u32)?;
if let Some(i) = found {
adjacent[i] = adjacent[count - 1];
vertex.live -= 1;
}
}
let mut best = usize::MAX;
let mut best_score = 0.;
for (i, &index) in cache[..write].iter().enumerate() {
work.add(1)?;
let j = index as usize;
let vertex = &mut vertices[j];
if vertex.live == 0 {
continue;
}
let s = scores.score(if i >= 16 { 0 } else { i + 1 }, vertex.live);
let diff = s - vertex.score;
vertex.score = s;
work.scan(
adjacency[vertex.offset as usize..vertex.offset as usize + vertex.live as usize]
.iter()
.copied(),
|tri| {
let tri = tri as usize;
let s = triangle_scores[tri] + diff;
if best_score < s {
best = tri;
best_score = s;
}
triangle_scores[tri] = s;
Ok(())
},
)?;
}
current = best;
if current == usize::MAX {
while cursor < faces {
work.add(1)?;
if emitted[cursor] == 0 {
current = cursor;
break;
}
cursor += 1;
}
}
}
Ok(())
}
#[inline]
pub fn optimize_vertex_cache_strip_generic<I: crate::Index>(
indices: &[I],
vertex_count: usize,
workspace: &mut Workspace,
) -> Result<Vec<I>, Error> {
I::with_input(indices, workspace, |indices, workspace| {
optimize_vertex_cache_strip_u32(indices, vertex_count, workspace)
.and_then(|value| crate::index::Convert::<I>::convert(value, workspace))
})
}
fn optimize_vertex_cache_strip_u32(
indices: &[u32],
vertex_count: usize,
workspace: &mut Workspace,
) -> Result<Vec<u32>, Error> {
let mut work = workspace.begin();
let result = (|| {
topology(indices, vertex_count, &mut work)?;
prepare(
indices.len(),
vertex_count,
checked_bytes(indices.len(), 4)?,
workspace,
)?;
let mut destination = output(indices.len())?;
kernel(
&mut destination,
indices,
vertex_count,
workspace,
&mut work,
&Preset::<true>,
)?;
Ok(destination)
})();
workspace.finish(&work);
result
}
#[inline]
pub fn optimize_vertex_cache_strip_into_generic<I: crate::Index>(
destination: &mut [I],
indices: &[I],
vertex_count: usize,
workspace: &mut Workspace,
) -> Result<(), Error> {
I::with_input(indices, workspace, |indices, workspace| {
I::with_mut(destination, workspace, |destination, workspace| {
optimize_vertex_cache_strip_into_u32(destination, indices, vertex_count, workspace)
})
})
}
fn optimize_vertex_cache_strip_into_u32(
destination: &mut [u32],
indices: &[u32],
vertex_count: usize,
workspace: &mut Workspace,
) -> Result<(), Error> {
let mut work = workspace.begin();
let result = (|| {
topology(indices, vertex_count, &mut work)?;
if destination.len() < indices.len() {
return Err(Error::BufferTooSmall);
}
prepare(indices.len(), vertex_count, 0, workspace)?;
kernel(
destination,
indices,
vertex_count,
workspace,
&mut work,
&Preset::<true>,
)
})();
workspace.finish(&work);
result
}
#[inline]
pub fn optimize_vertex_cache_strip_in_place_generic<I: crate::Index>(
indices: &mut [I],
vertex_count: usize,
workspace: &mut Workspace,
) -> Result<(), Error> {
I::with_mut(indices, workspace, |indices, workspace| {
optimize_vertex_cache_strip_in_place_u32(indices, vertex_count, workspace)
})
}
fn optimize_vertex_cache_strip_in_place_u32(
indices: &mut [u32],
vertex_count: usize,
workspace: &mut Workspace,
) -> Result<(), Error> {
let result = optimize_vertex_cache_strip_generic(indices, vertex_count, workspace)?;
indices.copy_from_slice(&result);
Ok(())
}
#[inline]
pub fn optimize_vertex_cache_fifo_generic<I: crate::Index>(
indices: &[I],
vertex_count: usize,
cache_size: u32,
workspace: &mut Workspace,
) -> Result<Vec<I>, Error> {
I::with_input(indices, workspace, |indices, workspace| {
optimize_vertex_cache_fifo_u32(indices, vertex_count, cache_size, workspace)
.and_then(|value| crate::index::Convert::<I>::convert(value, workspace))
})
}
fn optimize_vertex_cache_fifo_u32(
indices: &[u32],
vertex_count: usize,
cache_size: u32,
workspace: &mut Workspace,
) -> Result<Vec<u32>, Error> {
let mut work = workspace.begin();
let result = (|| {
topology(indices, vertex_count, &mut work)?;
if cache_size < 3 {
return Err(Error::InvalidParameter);
}
workspace.acquire(crate::workspace::ScratchFamily::Cache);
let mut budget = Budget::new(workspace);
let mut out = budget.filled(indices.len(), 0u32)?;
fifo(
&mut out,
indices,
vertex_count,
cache_size,
&mut budget,
&mut work,
)?;
Ok(out)
})();
workspace.finish(&work);
result
}
#[inline]
pub fn optimize_vertex_cache_fifo_into_generic<I: crate::Index>(
destination: &mut [I],
indices: &[I],
vertex_count: usize,
cache_size: u32,
workspace: &mut Workspace,
) -> Result<(), Error> {
I::with_input(indices, workspace, |indices, workspace| {
I::with_mut(destination, workspace, |destination, workspace| {
optimize_vertex_cache_fifo_into_u32(
destination,
indices,
vertex_count,
cache_size,
workspace,
)
})
})
}
fn optimize_vertex_cache_fifo_into_u32(
destination: &mut [u32],
indices: &[u32],
vertex_count: usize,
cache_size: u32,
workspace: &mut Workspace,
) -> Result<(), Error> {
let mut work = workspace.begin();
let result = (|| {
topology(indices, vertex_count, &mut work)?;
if cache_size < 3 {
return Err(Error::InvalidParameter);
}
if destination.len() < indices.len() {
return Err(Error::BufferTooSmall);
}
workspace.acquire(crate::workspace::ScratchFamily::Cache);
fifo(
destination,
indices,
vertex_count,
cache_size,
&mut Budget::new(workspace),
&mut work,
)
})();
workspace.finish(&work);
result
}
#[inline]
pub fn optimize_vertex_cache_fifo_in_place_generic<I: crate::Index>(
indices: &mut [I],
vertex_count: usize,
cache_size: u32,
workspace: &mut Workspace,
) -> Result<(), Error> {
I::with_mut(indices, workspace, |indices, workspace| {
optimize_vertex_cache_fifo_in_place_u32(indices, vertex_count, cache_size, workspace)
})
}
fn optimize_vertex_cache_fifo_in_place_u32(
indices: &mut [u32],
vertex_count: usize,
cache_size: u32,
workspace: &mut Workspace,
) -> Result<(), Error> {
let result = optimize_vertex_cache_fifo_generic(indices, vertex_count, cache_size, workspace)?;
indices.copy_from_slice(&result);
Ok(())
}
fn fifo(
out: &mut [u32],
indices: &[u32],
v: usize,
cache_size: u32,
budget: &mut Budget<'_>,
work: &mut Work,
) -> Result<(), Error> {
if indices.is_empty() {
return Ok(());
}
let length = v
.checked_mul(4)
.and_then(|n| indices.len().checked_mul(2).and_then(|m| n.checked_add(m)))
.ok_or(Error::SizeOverflow)?;
let owned = budget.bytes();
let ws = &mut *budget.ws;
let old_integer_len = ws.integers.len();
let old_flag_len = ws.flags.len();
ws.prepare([length, 0, indices.len() / 3, 0], owned)?;
ws.integers[..old_integer_len.min(v)].fill(0);
let old_hot = old_integer_len.saturating_sub(v * 2).min(v * 2);
ws.integers[v * 2..v * 2 + old_hot].fill(0);
ws.flags[..old_flag_len.min(indices.len() / 3)].fill(0);
let (counts, rest) = ws.integers[..length].split_at_mut(v);
let (offsets, rest) = rest.split_at_mut(v);
let (hot, rest) = rest.split_at_mut(v * 2);
let hot = hot.as_chunks_mut::<2>().0;
let (adjacency, dead) = rest.split_at_mut(indices.len());
let emitted = &mut ws.flags[..indices.len() / 3];
let charged = work.precharge(indices.len(), 1)?;
for &i in indices {
if !charged {
work.add(1)?;
}
counts[i as usize] += 1;
}
let mut offset = 0;
let charged = work.precharge(v, 1)?;
for (dst, &count) in offsets.iter_mut().zip(counts.iter()) {
if !charged {
work.add(1)?;
}
*dst = offset;
offset += count;
}
let triangles = indices.as_chunks::<3>().0;
if work.precharge(indices.len(), 1)? {
for (i, triangle) in triangles.iter().enumerate() {
for &j in triangle {
adjacency[offsets[j as usize] as usize] = i as u32;
offsets[j as usize] += 1;
}
}
} else {
for (i, &j) in indices.iter().enumerate() {
work.add(1)?;
adjacency[offsets[j as usize] as usize] = (i / 3) as u32;
offsets[j as usize] += 1;
}
}
let charged = work.precharge(v, 1)?;
for ((offset, &count), hot) in offsets.iter_mut().zip(counts.iter()).zip(hot.iter_mut()) {
if !charged {
work.add(1)?;
}
*offset -= count;
hot[0] = count;
}
let mut current = 0u32;
let mut timestamp = cache_size.wrapping_add(1);
let mut cursor = 1usize;
let mut top = 0usize;
let mut write = 0usize;
let destination = out[..indices.len()].as_chunks_mut::<3>().0;
while current != u32::MAX {
work.add(1)?;
let begin = top;
let j = current as usize;
let adjacent = &adjacency[offsets[j] as usize..(offsets[j] + counts[j]) as usize];
let charged = work.precharge(adjacent.len(), 1)?;
for &triangle in adjacent {
if !charged {
work.add(1)?;
}
let t = triangle as usize;
if emitted[t] != 0 {
continue;
}
let tri = &triangles[t];
destination[write].copy_from_slice(tri);
write += 1;
dead[top..top + 3].copy_from_slice(tri);
top += 3;
for &index in tri {
let vertex = &mut hot[index as usize];
vertex[0] -= 1;
if timestamp.wrapping_sub(vertex[1]) > cache_size {
vertex[1] = timestamp;
timestamp = timestamp.wrapping_add(1);
}
}
emitted[t] = 1;
}
current = u32::MAX;
let mut best = -1i32;
let candidates = &dead[begin..top];
let charged = work.precharge(candidates.len(), 1)?;
for &candidate in candidates {
if !charged {
work.add(1)?;
}
let vertex = hot[candidate as usize];
if vertex[0] != 0 {
let age = timestamp.wrapping_sub(vertex[1]);
let priority = if vertex[0].wrapping_mul(2).wrapping_add(age) <= cache_size {
age as i32
} else {
0
};
if priority > best {
current = candidate;
best = priority;
}
}
}
if current == u32::MAX {
work.search(top, |_| {
top -= 1;
let vertex = dead[top];
if hot[vertex as usize][0] > 0 {
current = vertex;
true
} else {
false
}
})?;
if current == u32::MAX {
work.search(v - cursor, |_| {
if hot[cursor][0] > 0 {
current = cursor as u32;
true
} else {
cursor += 1;
false
}
})?;
}
}
}
Ok(())
}
#[inline]
pub fn optimize_vertex_cache_with_table(
indices: &[u32],
vertex_count: usize,
table: &VertexScoreTable,
workspace: &mut Workspace,
) -> Result<Vec<u32>, Error> {
optimize_vertex_cache_with_table_generic::<u32>(indices, vertex_count, table, workspace)
}
#[inline]
pub fn optimize_vertex_cache_with_table_into(
destination: &mut [u32],
indices: &[u32],
vertex_count: usize,
table: &VertexScoreTable,
workspace: &mut Workspace,
) -> Result<(), Error> {
optimize_vertex_cache_with_table_into_generic::<u32>(
destination,
indices,
vertex_count,
table,
workspace,
)
}
#[inline]
pub fn optimize_vertex_cache(
indices: &[u32],
vertex_count: usize,
workspace: &mut Workspace,
) -> Result<Vec<u32>, Error> {
optimize_vertex_cache_generic::<u32>(indices, vertex_count, workspace)
}
#[inline]
pub fn optimize_vertex_cache_into(
destination: &mut [u32],
indices: &[u32],
vertex_count: usize,
workspace: &mut Workspace,
) -> Result<(), Error> {
optimize_vertex_cache_into_generic::<u32>(destination, indices, vertex_count, workspace)
}
#[inline]
pub fn optimize_vertex_cache_in_place(
indices: &mut [u32],
vertex_count: usize,
workspace: &mut Workspace,
) -> Result<(), Error> {
optimize_vertex_cache_in_place_generic::<u32>(indices, vertex_count, workspace)
}
#[inline]
pub fn optimize_vertex_cache_strip(
indices: &[u32],
vertex_count: usize,
workspace: &mut Workspace,
) -> Result<Vec<u32>, Error> {
optimize_vertex_cache_strip_generic::<u32>(indices, vertex_count, workspace)
}
#[inline]
pub fn optimize_vertex_cache_strip_into(
destination: &mut [u32],
indices: &[u32],
vertex_count: usize,
workspace: &mut Workspace,
) -> Result<(), Error> {
optimize_vertex_cache_strip_into_generic::<u32>(destination, indices, vertex_count, workspace)
}
#[inline]
pub fn optimize_vertex_cache_strip_in_place(
indices: &mut [u32],
vertex_count: usize,
workspace: &mut Workspace,
) -> Result<(), Error> {
optimize_vertex_cache_strip_in_place_generic::<u32>(indices, vertex_count, workspace)
}
#[inline]
pub fn optimize_vertex_cache_fifo(
indices: &[u32],
vertex_count: usize,
cache_size: u32,
workspace: &mut Workspace,
) -> Result<Vec<u32>, Error> {
optimize_vertex_cache_fifo_generic::<u32>(indices, vertex_count, cache_size, workspace)
}
#[inline]
pub fn optimize_vertex_cache_fifo_into(
destination: &mut [u32],
indices: &[u32],
vertex_count: usize,
cache_size: u32,
workspace: &mut Workspace,
) -> Result<(), Error> {
optimize_vertex_cache_fifo_into_generic::<u32>(
destination,
indices,
vertex_count,
cache_size,
workspace,
)
}
#[inline]
pub fn optimize_vertex_cache_fifo_in_place(
indices: &mut [u32],
vertex_count: usize,
cache_size: u32,
workspace: &mut Workspace,
) -> Result<(), Error> {
optimize_vertex_cache_fifo_in_place_generic::<u32>(indices, vertex_count, cache_size, workspace)
}