Skip to main content

meshoptimizer_rs/
cache.rs

1// Translation of meshoptimizer 1.3 src/vcacheoptimizer.cpp; see LICENSE.
2use crate::budget::Budget;
3use crate::workspace::{checked_bytes, output, topology, Work};
4use crate::{Error, Workspace};
5use alloc::vec::Vec;
6
7const CACHE: [f32; 17] = [
8    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,
9    0.568, 0.372, 0.234,
10];
11const LIVE: [f32; 9] = [0., 0.995, 0.713, 0.450, 0.404, 0.059, 0.005, 0.147, 0.006];
12const STRIP_CACHE: [f32; 17] = [
13    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,
14    0.050, 0.131,
15];
16const STRIP_LIVE: [f32; 9] = [0., 0.956, 0.786, 0.577, 0.558, 0.618, 0.549, 0.499, 0.489];
17/// Caller-defined vertex-cache scores; an opt-in extension not in C++ meshoptimizer.
18///
19/// Cache score zero is for a vertex outside the cache; entries 1 through 16
20/// correspond to most to least recently used. Live-valence scores cover 0 through
21/// 8 remaining triangle references; larger valences use entry 8. The cache size
22/// and valence clamp cannot be changed. [`Default`] reproduces the standard table.
23#[derive(Clone, Debug, PartialEq)]
24pub struct VertexScoreTable {
25    cache: [f32; 17],
26    live: [f32; 9],
27}
28
29impl VertexScoreTable {
30    /// Copy and validate exactly 17 cache scores and 9 live-valence scores.
31    /// Construction allocates no heap storage and needs no workspace.
32    ///
33    /// # Errors
34    /// `InvalidParameter` if either length differs or any score is non-finite.
35    pub fn new(cache: &[f32], live: &[f32]) -> Result<Self, Error> {
36        if cache.len() != 17 || live.len() != 9 || !cache.iter().chain(live).all(|s| s.is_finite())
37        {
38            return Err(Error::InvalidParameter);
39        }
40        let mut table = Self::default();
41        table.cache.copy_from_slice(cache);
42        table.live.copy_from_slice(live);
43        Ok(table)
44    }
45
46    /// Cache-position scores, including the outside-cache score at zero.
47    pub fn cache_scores(&self) -> &[f32; 17] {
48        &self.cache
49    }
50
51    /// Live-valence scores; valences above eight use the final entry.
52    pub fn live_scores(&self) -> &[f32; 9] {
53        &self.live
54    }
55}
56
57impl Default for VertexScoreTable {
58    fn default() -> Self {
59        Self {
60            cache: CACHE,
61            live: LIVE,
62        }
63    }
64}
65
66trait Scores {
67    fn score(&self, position: usize, live: u32) -> f32;
68}
69
70struct Preset<const STRIP: bool>;
71
72impl<const STRIP: bool> Scores for Preset<STRIP> {
73    fn score(&self, position: usize, live: u32) -> f32 {
74        if STRIP {
75            STRIP_CACHE[position] + STRIP_LIVE[live.min(8) as usize]
76        } else {
77            CACHE[position] + LIVE[live.min(8) as usize]
78        }
79    }
80}
81
82impl Scores for VertexScoreTable {
83    fn score(&self, position: usize, live: u32) -> f32 {
84        self.cache[position] + self.live[live.min(8) as usize]
85    }
86}
87
88/// Reorder triangles with caller-defined scores; not in C++ meshoptimizer.
89///
90/// Uses the same workspace limits, topology validation and triangle preservation
91/// as [`optimize_vertex_cache`]. The default table gives identical output.
92/// Tuned tables must be validated on the target hardware; no improvement is
93/// guaranteed.
94///
95/// A triangle score is the sum of its three vertex scores. After each emitted
96/// triangle, the vertices of the cache are rescored in cache order, and each
97/// change in a vertex score is added to the score of every unemitted triangle
98/// that uses it. The next triangle is whichever updated triangle first reaches
99/// the largest positive running score during this pass, so a transient maximum
100/// reached before a later vertex lowers the same triangle's score can win.
101/// This is upstream's incremental selection, and tables are applied through the
102/// same procedure as the default table. When no updated triangle scores above
103/// zero, the next unemitted triangle in input order follows. A table whose sums
104/// are never positive therefore keeps the input order. Extreme finite scores can overflow the summed scores, which
105/// degrades the ordering but never drops or duplicates a triangle.
106///
107/// ```
108/// use meshoptimizer_rs::{optimize_vertex_cache_with_table, VertexScoreTable, Workspace};
109/// let defaults = VertexScoreTable::default();
110/// let mut cache = *defaults.cache_scores();
111/// cache[1] = 1.0;
112/// let table = VertexScoreTable::new(&cache, defaults.live_scores())?;
113/// let result = optimize_vertex_cache_with_table(&[0, 1, 2], 3, &table,
114///                                               &mut Workspace::default())?;
115/// assert_eq!(result, [0, 1, 2]);
116/// # Ok::<(), meshoptimizer_rs::Error>(())
117/// ```
118///
119/// # Errors
120/// Same errors as [`optimize_vertex_cache`].
121#[inline]
122pub fn optimize_vertex_cache_with_table_generic<I: crate::Index>(
123    indices: &[I],
124    vertex_count: usize,
125    table: &VertexScoreTable,
126    workspace: &mut Workspace,
127) -> Result<Vec<I>, Error> {
128    I::with_input(indices, workspace, |indices, workspace| {
129        optimize_vertex_cache_with_table_u32(indices, vertex_count, table, workspace)
130            .and_then(|value| crate::index::Convert::<I>::convert(value, workspace))
131    })
132}
133
134fn optimize_vertex_cache_with_table_u32(
135    indices: &[u32],
136    vertex_count: usize,
137    table: &VertexScoreTable,
138    workspace: &mut Workspace,
139) -> Result<Vec<u32>, Error> {
140    let mut work = workspace.begin();
141    let result = (|| {
142        topology(indices, vertex_count, &mut work)?;
143        prepare(
144            indices.len(),
145            vertex_count,
146            checked_bytes(indices.len(), 4)?,
147            workspace,
148        )?;
149        let mut destination = output(indices.len())?;
150        kernel(
151            &mut destination,
152            indices,
153            vertex_count,
154            workspace,
155            &mut work,
156            table,
157        )?;
158        Ok(destination)
159    })();
160    workspace.finish(&work);
161    result
162}
163
164/// Write caller-defined cache ordering; not in C++ meshoptimizer.
165///
166/// The unused destination tail is untouched. Validation and reservation precede
167/// writes; work exhaustion can partially modify the used prefix. Caller-owned
168/// destination storage is excluded from workspace byte limits.
169///
170/// # Errors
171/// Same errors as [`optimize_vertex_cache_with_table`], plus `BufferTooSmall`
172/// if the destination is shorter than the input.
173#[inline]
174pub fn optimize_vertex_cache_with_table_into_generic<I: crate::Index>(
175    destination: &mut [I],
176    indices: &[I],
177    vertex_count: usize,
178    table: &VertexScoreTable,
179    workspace: &mut Workspace,
180) -> Result<(), Error> {
181    I::with_input(indices, workspace, |indices, workspace| {
182        I::with_mut(destination, workspace, |destination, workspace| {
183            optimize_vertex_cache_with_table_into_u32(
184                destination,
185                indices,
186                vertex_count,
187                table,
188                workspace,
189            )
190        })
191    })
192}
193
194fn optimize_vertex_cache_with_table_into_u32(
195    destination: &mut [u32],
196    indices: &[u32],
197    vertex_count: usize,
198    table: &VertexScoreTable,
199    workspace: &mut Workspace,
200) -> Result<(), Error> {
201    let mut work = workspace.begin();
202    let result = (|| {
203        topology(indices, vertex_count, &mut work)?;
204        if destination.len() < indices.len() {
205            return Err(Error::BufferTooSmall);
206        }
207        prepare(indices.len(), vertex_count, 0, workspace)?;
208        kernel(
209            destination,
210            indices,
211            vertex_count,
212            workspace,
213            &mut work,
214            table,
215        )
216    })();
217    workspace.finish(&work);
218    result
219}
220
221/// Reorder triangles using upstream `meshopt_optimizeVertexCache` (standard variant).
222///
223/// Returns exactly as many indices as supplied, preserving triangle corner
224/// order and vertex references. Empty input is valid. No geometry is welded
225/// or compacted. Output and scratch count toward the workspace byte limit.
226///
227/// # Errors
228/// `InvalidTopology` for incomplete triangles or `IndexOutOfBounds` for invalid vertex references.
229/// `SizeOverflow` for size overflow, `LimitExceeded` for exhausted limits, or `AllocationFailed` for failed reservation.
230#[inline]
231pub fn optimize_vertex_cache_generic<I: crate::Index>(
232    indices: &[I],
233    vertex_count: usize,
234    workspace: &mut Workspace,
235) -> Result<Vec<I>, Error> {
236    I::with_input(indices, workspace, |indices, workspace| {
237        optimize_vertex_cache_u32(indices, vertex_count, workspace)
238            .and_then(|value| crate::index::Convert::<I>::convert(value, workspace))
239    })
240}
241
242fn optimize_vertex_cache_u32(
243    indices: &[u32],
244    vertex_count: usize,
245    workspace: &mut Workspace,
246) -> Result<Vec<u32>, Error> {
247    let mut work = workspace.begin();
248    let result = (|| {
249        topology(indices, vertex_count, &mut work)?;
250        prepare(
251            indices.len(),
252            vertex_count,
253            checked_bytes(indices.len(), 4)?,
254            workspace,
255        )?;
256        let mut destination = output(indices.len())?;
257        kernel(
258            &mut destination,
259            indices,
260            vertex_count,
261            workspace,
262            &mut work,
263            &Preset::<false>,
264        )?;
265        Ok(destination)
266    })();
267    workspace.finish(&work);
268    result
269}
270
271/// Write upstream standard cache ordering to the used prefix of `destination`.
272///
273/// The unused tail is untouched. Validation and reservation precede writes.
274/// Counted-work exhaustion during optimization can leave the used prefix
275/// partially modified. Caller-owned destination storage is excluded from limits.
276///
277/// # Errors
278/// Same errors as [`optimize_vertex_cache`]. `BufferTooSmall` if the destination is shorter than the input.
279#[inline]
280pub fn optimize_vertex_cache_into_generic<I: crate::Index>(
281    destination: &mut [I],
282    indices: &[I],
283    vertex_count: usize,
284    workspace: &mut Workspace,
285) -> Result<(), Error> {
286    I::with_input(indices, workspace, |indices, workspace| {
287        I::with_mut(destination, workspace, |destination, workspace| {
288            optimize_vertex_cache_into_u32(destination, indices, vertex_count, workspace)
289        })
290    })
291}
292
293fn optimize_vertex_cache_into_u32(
294    destination: &mut [u32],
295    indices: &[u32],
296    vertex_count: usize,
297    workspace: &mut Workspace,
298) -> Result<(), Error> {
299    let mut work = workspace.begin();
300    let result = (|| {
301        topology(indices, vertex_count, &mut work)?;
302        if destination.len() < indices.len() {
303            return Err(Error::BufferTooSmall);
304        }
305        prepare(indices.len(), vertex_count, 0, workspace)?;
306        kernel(
307            destination,
308            indices,
309            vertex_count,
310            workspace,
311            &mut work,
312            &Preset::<false>,
313        )
314    })();
315    workspace.finish(&work);
316    result
317}
318
319/// Destructively apply upstream standard cache ordering, leaving input unchanged on error.
320/// A fallibly allocated temporary output counts toward the byte limit.
321///
322/// # Errors
323/// Same errors as [`optimize_vertex_cache`].
324#[inline]
325pub fn optimize_vertex_cache_in_place_generic<I: crate::Index>(
326    indices: &mut [I],
327    vertex_count: usize,
328    workspace: &mut Workspace,
329) -> Result<(), Error> {
330    I::with_mut(indices, workspace, |indices, workspace| {
331        optimize_vertex_cache_in_place_u32(indices, vertex_count, workspace)
332    })
333}
334
335fn optimize_vertex_cache_in_place_u32(
336    indices: &mut [u32],
337    vertex_count: usize,
338    workspace: &mut Workspace,
339) -> Result<(), Error> {
340    let result = optimize_vertex_cache_generic(indices, vertex_count, workspace)?;
341    indices.copy_from_slice(&result);
342    Ok(())
343}
344
345fn prepare(n: usize, v: usize, out: usize, ws: &mut Workspace) -> Result<(), Error> {
346    ws.acquire(crate::workspace::ScratchFamily::Cache);
347    if n == 0 {
348        return ws.prepare([0; 4], out);
349    }
350    let faces = n / 3;
351    ws.prepare_cache([n, faces, faces, 0], v, out)
352}
353
354fn kernel<S: Scores>(
355    dest: &mut [u32],
356    indices: &[u32],
357    v: usize,
358    ws: &mut Workspace,
359    work: &mut Work,
360    scores: &S,
361) -> Result<(), Error> {
362    if indices.is_empty() {
363        return Ok(());
364    }
365    let faces = indices.len() / 3;
366    let vertices = &mut ws.vertices[..v];
367    let adjacency = &mut ws.integers[..indices.len()];
368    let triangle_scores = &mut ws.floats[..faces];
369    let emitted = &mut ws.flags[..faces];
370    let triangles = indices.as_chunks::<3>().0;
371    let destination = dest[..indices.len()].as_chunks_mut::<3>().0;
372    assert_eq!(triangles.len(), triangle_scores.len());
373    assert_eq!(triangles.len(), emitted.len());
374    work.add(v)?;
375    for vertex in vertices.iter_mut() {
376        vertex.live = 0;
377    }
378    work.scan(indices.iter().copied(), |index| {
379        vertices[index as usize].live += 1;
380        Ok(())
381    })?;
382    let mut offset = 0;
383    work.scan(vertices.iter_mut(), |vertex| {
384        vertex.offset = offset;
385        offset += vertex.live;
386        Ok(())
387    })?;
388    if work.precharge(indices.len(), 1)? {
389        for (i, triangle) in triangles.iter().enumerate() {
390            for &index in triangle {
391                let vertex = &mut vertices[index as usize];
392                adjacency[vertex.offset as usize] = i as u32;
393                vertex.offset += 1;
394            }
395        }
396    } else {
397        for (i, triangle) in indices.as_chunks::<3>().0.iter().enumerate() {
398            for &index in triangle {
399                work.add(1)?;
400                let j = index as usize;
401                let vertex = &mut vertices[j];
402                adjacency[vertex.offset as usize] = i as u32;
403                vertex.offset += 1;
404            }
405        }
406    }
407    let mut max_live = 0usize;
408    work.scan(vertices.iter_mut(), |vertex| {
409        max_live = max_live.max(vertex.live as usize);
410        vertex.offset -= vertex.live;
411        vertex.score = scores.score(0, vertex.live);
412        Ok(())
413    })?;
414    work.add(faces)?;
415    emitted.fill(0);
416    work.scan(
417        triangle_scores[..faces].iter_mut().zip(triangles),
418        |(s, triangle)| {
419            *s = vertices[triangle[0] as usize].score
420                + vertices[triangle[1] as usize].score
421                + vertices[triangle[2] as usize].score;
422            Ok(())
423        },
424    )?;
425    // Per emission: one face, <=16 old cache entries, three removal searches
426    // of <=max_live entries, <=19 score visits each scanning <=max_live. The
427    // cursor advances <=faces-1 times and stops on <=faces-1 selections.
428    let bound = max_live
429        .checked_mul(22)
430        .and_then(|n| n.checked_add(38))
431        .and_then(|n| faces.checked_mul(n));
432    if let Some(bound) = bound.filter(|&n| work.covers(n) == Ok(true)) {
433        // Prepay the proven whole-kernel bound, then refund the unvisited part
434        // so the charged total equals the limited path's visit-by-visit count.
435        work.add(bound)?;
436        let visits = cache_loop_covered(
437            destination,
438            triangles,
439            vertices,
440            adjacency,
441            triangle_scores,
442            emitted,
443            scores,
444        );
445        debug_assert!(visits <= bound, "cache work bound overrun");
446        work.refund_cache(bound.saturating_sub(visits));
447        Ok(())
448    } else {
449        cache_loop_limited(
450            destination,
451            triangles,
452            vertices,
453            adjacency,
454            triangle_scores,
455            emitted,
456            work,
457            scores,
458        )
459    }
460}
461
462/// Merge the previous cache behind the emitted triangle, as upstream does, and
463/// carry each kept entry's live bit to its new position.
464///
465/// Upstream copies each old entry and advances unless it equals a triangle
466/// vertex. Here the old entries equal to a triangle vertex form a mask from
467/// fixed-width comparisons. Without a match all 16 slots are copied at once;
468/// otherwise the copy advances past matched slots, so every kept entry ends at
469/// the same position as upstream's. Slots past `count` hold stale values that
470/// the mask excludes and no later step reads.
471///
472/// `live` has bit `k` set when old entry `k` still has unemitted triangles.
473/// Returns the merged length and the carried live bits, both below 19.
474#[inline(always)]
475fn merge(
476    next: &mut [u32; 32],
477    old: &[u32; 32],
478    count: usize,
479    mut live: u32,
480    [a, b, c]: [u32; 3],
481) -> (usize, u32) {
482    let mut matched = 0u32;
483    for (k, &index) in old[..16].iter().enumerate() {
484        matched |= u32::from((index == a) | (index == b) | (index == c)) << k;
485    }
486    matched &= (1u32 << count.min(16)) - 1;
487    if matched == 0 {
488        next[3..19].copy_from_slice(&old[..16]);
489    } else {
490        let mut write = 3;
491        for (k, &index) in old[..16].iter().enumerate() {
492            next[write & 31] = index;
493            write += (!matched >> k & 1) as usize;
494        }
495        let mut pending = matched;
496        while pending != 0 {
497            // Highest matched slot first keeps lower bit positions valid.
498            let slot = 31 - pending.leading_zeros();
499            pending &= !(1 << slot);
500            let below = (1u32 << slot) - 1;
501            live = (live & below) | (live >> 1 & !below);
502        }
503    }
504    (3 + count.min(16) - matched.count_ones() as usize, live << 3)
505}
506
507/// Covered path of the cache optimizer: no budget checks, returns the exact
508/// number of visits the limited path charges one by one.
509///
510/// Same traversal, float operations and selection as [`cache_loop_limited`].
511/// A vertex's live count only falls when its triangle is emitted, and the
512/// emitted triangle's vertices always land at cache positions 0..3, so a live
513/// bit per cache position is exact: fresh for those three, carried for the
514/// rest. Rescoring then visits the set bits in position order and skips
515/// exhausted vertices without loading them; upstream loads and skips them.
516#[inline(never)]
517#[allow(clippy::too_many_arguments)]
518fn cache_loop_covered<S: Scores>(
519    destination: &mut [[u32; 3]],
520    triangles: &[[u32; 3]],
521    vertices: &mut [crate::workspace::CacheVertex],
522    adjacency: &mut [u32],
523    triangle_scores: &mut [f32],
524    emitted: &mut [u8],
525    scores: &S,
526) -> usize {
527    let faces = triangles.len();
528    assert_eq!(faces, triangle_scores.len());
529    assert_eq!(faces, emitted.len());
530    let mut cache_storage = [0u32; 32];
531    let mut next_storage = [0u32; 32];
532    // Upstream exchanges pointers, not the contents of its two cache arrays.
533    let mut cache = &mut cache_storage;
534    let mut next = &mut next_storage;
535    let mut cache_count = 0;
536    let mut live = 0u32;
537    let mut current = 0usize;
538    let mut cursor = 1usize;
539    let mut emitted_count = 0;
540    let mut visits = 0usize;
541    while current != usize::MAX {
542        visits += 1;
543        let triangle = triangles[current];
544        destination[emitted_count] = triangle;
545        emitted_count += 1;
546        emitted[current] = 1;
547        triangle_scores[current] = 0.;
548        next[..3].copy_from_slice(&triangle);
549        visits += cache_count;
550        let (write, carried) = merge(next, cache, cache_count, live, triangle);
551        core::mem::swap(&mut cache, &mut next);
552        cache_count = write.min(16);
553        let current_id = current as u32;
554        for index in triangle {
555            let vertex = &mut vertices[index as usize];
556            let start = vertex.offset as usize;
557            let count = vertex.live as usize;
558            let adjacent = &mut adjacency[start..start + count];
559            match adjacent.iter().position(|&tri| tri == current_id) {
560                Some(i) => {
561                    visits += i + 1;
562                    adjacent[i] = adjacent[count - 1];
563                    vertex.live -= 1;
564                }
565                None => visits += count,
566            }
567        }
568        let [a, b, c] = triangle;
569        let fresh = u32::from(vertices[a as usize].live != 0)
570            | u32::from(vertices[b as usize].live != 0) << 1
571            | u32::from(vertices[c as usize].live != 0) << 2;
572        let mut pending = carried | fresh;
573        live = pending & 0xffff;
574        // Every cache entry is a visit, exhausted or not.
575        visits += write;
576        let mut best = usize::MAX;
577        let mut best_score = 0.;
578        while pending != 0 {
579            let i = pending.trailing_zeros() as usize;
580            pending &= pending - 1;
581            let vertex = &mut vertices[cache[i & 31] as usize];
582            let s = scores.score(if i >= 16 { 0 } else { i + 1 }, vertex.live);
583            let diff = s - vertex.score;
584            vertex.score = s;
585            let start = vertex.offset as usize;
586            let count = vertex.live as usize;
587            visits += count;
588            for &tri in &adjacency[start..start + count] {
589                let tri = tri as usize;
590                let s = triangle_scores[tri] + diff;
591                if best_score < s {
592                    best = tri;
593                    best_score = s;
594                }
595                triangle_scores[tri] = s;
596            }
597        }
598        current = best;
599        if current == usize::MAX {
600            while cursor < faces {
601                visits += 1;
602                if emitted[cursor] == 0 {
603                    current = cursor;
604                    break;
605                }
606                cursor += 1;
607            }
608        }
609    }
610    visits
611}
612
613/// Limited path: charges every visit before its observable mutation, so
614/// exhaustion stops at exactly the same point as a visit-by-visit meter.
615#[inline(never)]
616#[allow(clippy::too_many_arguments)]
617fn cache_loop_limited<S: Scores>(
618    destination: &mut [[u32; 3]],
619    triangles: &[[u32; 3]],
620    vertices: &mut [crate::workspace::CacheVertex],
621    adjacency: &mut [u32],
622    triangle_scores: &mut [f32],
623    emitted: &mut [u8],
624    work: &mut Work,
625    scores: &S,
626) -> Result<(), Error> {
627    let faces = triangles.len();
628    assert_eq!(triangles.len(), triangle_scores.len());
629    assert_eq!(triangles.len(), emitted.len());
630    let mut cache_storage = [0u32; 20];
631    let mut next_storage = [0u32; 20];
632    // Upstream exchanges pointers, not the contents of its two cache arrays.
633    let mut cache = &mut cache_storage;
634    let mut next = &mut next_storage;
635    let mut cache_count = 0;
636    let mut current = 0usize;
637    let mut cursor = 1usize;
638    let mut emitted_count = 0;
639    while current != usize::MAX {
640        work.add(1)?;
641        let triangle = &triangles[current];
642        destination[emitted_count].copy_from_slice(triangle);
643        emitted_count += 1;
644        emitted[current] = 1;
645        triangle_scores[current] = 0.;
646        next[..3].copy_from_slice(triangle);
647        let mut write = 3;
648        assert!(cache_count <= 16);
649        work.scan(cache[..cache_count].iter().copied(), |index| {
650            next[write] = index;
651            write += usize::from(!triangle.contains(&index));
652            Ok(())
653        })?;
654        core::mem::swap(&mut cache, &mut next);
655        cache_count = write.min(16);
656        for &index in triangle {
657            let j = index as usize;
658            let vertex = &mut vertices[j];
659            let start = vertex.offset as usize;
660            let count = vertex.live as usize;
661            let adjacent = &mut adjacency[start..start + count];
662            let found = work.search(count, |i| adjacent[i] == current as u32)?;
663            if let Some(i) = found {
664                adjacent[i] = adjacent[count - 1];
665                vertex.live -= 1;
666            }
667        }
668        let mut best = usize::MAX;
669        let mut best_score = 0.;
670        // One checked visit per cache entry, before the entry's mutation.
671        for (i, &index) in cache[..write].iter().enumerate() {
672            work.add(1)?;
673            let j = index as usize;
674            let vertex = &mut vertices[j];
675            if vertex.live == 0 {
676                continue;
677            }
678            let s = scores.score(if i >= 16 { 0 } else { i + 1 }, vertex.live);
679            let diff = s - vertex.score;
680            vertex.score = s;
681            work.scan(
682                adjacency[vertex.offset as usize..vertex.offset as usize + vertex.live as usize]
683                    .iter()
684                    .copied(),
685                |tri| {
686                    let tri = tri as usize;
687                    let s = triangle_scores[tri] + diff;
688                    if best_score < s {
689                        best = tri;
690                        best_score = s;
691                    }
692                    triangle_scores[tri] = s;
693                    Ok(())
694                },
695            )?;
696        }
697        current = best;
698        if current == usize::MAX {
699            while cursor < faces {
700                work.add(1)?;
701                if emitted[cursor] == 0 {
702                    current = cursor;
703                    break;
704                }
705                cursor += 1;
706            }
707        }
708    }
709    Ok(())
710}
711
712/// Optimize cache ordering using upstream's strip-oriented score table.
713///
714/// # Errors
715/// Same errors as [`optimize_vertex_cache`].
716#[inline]
717pub fn optimize_vertex_cache_strip_generic<I: crate::Index>(
718    indices: &[I],
719    vertex_count: usize,
720    workspace: &mut Workspace,
721) -> Result<Vec<I>, Error> {
722    I::with_input(indices, workspace, |indices, workspace| {
723        optimize_vertex_cache_strip_u32(indices, vertex_count, workspace)
724            .and_then(|value| crate::index::Convert::<I>::convert(value, workspace))
725    })
726}
727
728fn optimize_vertex_cache_strip_u32(
729    indices: &[u32],
730    vertex_count: usize,
731    workspace: &mut Workspace,
732) -> Result<Vec<u32>, Error> {
733    let mut work = workspace.begin();
734    let result = (|| {
735        topology(indices, vertex_count, &mut work)?;
736        prepare(
737            indices.len(),
738            vertex_count,
739            checked_bytes(indices.len(), 4)?,
740            workspace,
741        )?;
742        let mut destination = output(indices.len())?;
743        kernel(
744            &mut destination,
745            indices,
746            vertex_count,
747            workspace,
748            &mut work,
749            &Preset::<true>,
750        )?;
751        Ok(destination)
752    })();
753    workspace.finish(&work);
754    result
755}
756/// Write strip-oriented cache ordering; work exhaustion may partially modify
757/// the used prefix. The unused destination tail is untouched.
758///
759/// # Errors
760/// Same errors as [`optimize_vertex_cache_strip`]. `BufferTooSmall` if the destination is shorter than the input.
761#[inline]
762pub fn optimize_vertex_cache_strip_into_generic<I: crate::Index>(
763    destination: &mut [I],
764    indices: &[I],
765    vertex_count: usize,
766    workspace: &mut Workspace,
767) -> Result<(), Error> {
768    I::with_input(indices, workspace, |indices, workspace| {
769        I::with_mut(destination, workspace, |destination, workspace| {
770            optimize_vertex_cache_strip_into_u32(destination, indices, vertex_count, workspace)
771        })
772    })
773}
774
775fn optimize_vertex_cache_strip_into_u32(
776    destination: &mut [u32],
777    indices: &[u32],
778    vertex_count: usize,
779    workspace: &mut Workspace,
780) -> Result<(), Error> {
781    let mut work = workspace.begin();
782    let result = (|| {
783        topology(indices, vertex_count, &mut work)?;
784        if destination.len() < indices.len() {
785            return Err(Error::BufferTooSmall);
786        }
787        prepare(indices.len(), vertex_count, 0, workspace)?;
788        kernel(
789            destination,
790            indices,
791            vertex_count,
792            workspace,
793            &mut work,
794            &Preset::<true>,
795        )
796    })();
797    workspace.finish(&work);
798    result
799}
800/// Destructively apply strip-oriented ordering, preserving indices on error.
801///
802/// # Errors
803/// Same errors as [`optimize_vertex_cache_strip`].
804#[inline]
805pub fn optimize_vertex_cache_strip_in_place_generic<I: crate::Index>(
806    indices: &mut [I],
807    vertex_count: usize,
808    workspace: &mut Workspace,
809) -> Result<(), Error> {
810    I::with_mut(indices, workspace, |indices, workspace| {
811        optimize_vertex_cache_strip_in_place_u32(indices, vertex_count, workspace)
812    })
813}
814
815fn optimize_vertex_cache_strip_in_place_u32(
816    indices: &mut [u32],
817    vertex_count: usize,
818    workspace: &mut Workspace,
819) -> Result<(), Error> {
820    let result = optimize_vertex_cache_strip_generic(indices, vertex_count, workspace)?;
821    indices.copy_from_slice(&result);
822    Ok(())
823}
824/// Optimize using upstream's FIFO cache heuristic. Cache size is at least three.
825///
826/// # Errors
827/// Same errors as [`optimize_vertex_cache`]. `InvalidParameter` if the cache size is below three.
828#[inline]
829pub fn optimize_vertex_cache_fifo_generic<I: crate::Index>(
830    indices: &[I],
831    vertex_count: usize,
832    cache_size: u32,
833    workspace: &mut Workspace,
834) -> Result<Vec<I>, Error> {
835    I::with_input(indices, workspace, |indices, workspace| {
836        optimize_vertex_cache_fifo_u32(indices, vertex_count, cache_size, workspace)
837            .and_then(|value| crate::index::Convert::<I>::convert(value, workspace))
838    })
839}
840
841fn optimize_vertex_cache_fifo_u32(
842    indices: &[u32],
843    vertex_count: usize,
844    cache_size: u32,
845    workspace: &mut Workspace,
846) -> Result<Vec<u32>, Error> {
847    let mut work = workspace.begin();
848    let result = (|| {
849        topology(indices, vertex_count, &mut work)?;
850        if cache_size < 3 {
851            return Err(Error::InvalidParameter);
852        }
853        workspace.acquire(crate::workspace::ScratchFamily::Cache);
854        let mut budget = Budget::new(workspace);
855        let mut out = budget.filled(indices.len(), 0u32)?;
856        fifo(
857            &mut out,
858            indices,
859            vertex_count,
860            cache_size,
861            &mut budget,
862            &mut work,
863        )?;
864        Ok(out)
865    })();
866    workspace.finish(&work);
867    result
868}
869/// Write FIFO cache ordering; work exhaustion may partially modify the prefix.
870///
871/// # Errors
872/// Same errors as [`optimize_vertex_cache_fifo`]. `BufferTooSmall` if the destination is shorter than the input.
873#[inline]
874pub fn optimize_vertex_cache_fifo_into_generic<I: crate::Index>(
875    destination: &mut [I],
876    indices: &[I],
877    vertex_count: usize,
878    cache_size: u32,
879    workspace: &mut Workspace,
880) -> Result<(), Error> {
881    I::with_input(indices, workspace, |indices, workspace| {
882        I::with_mut(destination, workspace, |destination, workspace| {
883            optimize_vertex_cache_fifo_into_u32(
884                destination,
885                indices,
886                vertex_count,
887                cache_size,
888                workspace,
889            )
890        })
891    })
892}
893
894fn optimize_vertex_cache_fifo_into_u32(
895    destination: &mut [u32],
896    indices: &[u32],
897    vertex_count: usize,
898    cache_size: u32,
899    workspace: &mut Workspace,
900) -> Result<(), Error> {
901    let mut work = workspace.begin();
902    let result = (|| {
903        topology(indices, vertex_count, &mut work)?;
904        if cache_size < 3 {
905            return Err(Error::InvalidParameter);
906        }
907        if destination.len() < indices.len() {
908            return Err(Error::BufferTooSmall);
909        }
910        workspace.acquire(crate::workspace::ScratchFamily::Cache);
911        fifo(
912            destination,
913            indices,
914            vertex_count,
915            cache_size,
916            &mut Budget::new(workspace),
917            &mut work,
918        )
919    })();
920    workspace.finish(&work);
921    result
922}
923/// Destructively apply FIFO ordering, preserving indices on error.
924///
925/// # Errors
926/// Same errors as [`optimize_vertex_cache_fifo`].
927#[inline]
928pub fn optimize_vertex_cache_fifo_in_place_generic<I: crate::Index>(
929    indices: &mut [I],
930    vertex_count: usize,
931    cache_size: u32,
932    workspace: &mut Workspace,
933) -> Result<(), Error> {
934    I::with_mut(indices, workspace, |indices, workspace| {
935        optimize_vertex_cache_fifo_in_place_u32(indices, vertex_count, cache_size, workspace)
936    })
937}
938
939fn optimize_vertex_cache_fifo_in_place_u32(
940    indices: &mut [u32],
941    vertex_count: usize,
942    cache_size: u32,
943    workspace: &mut Workspace,
944) -> Result<(), Error> {
945    let result = optimize_vertex_cache_fifo_generic(indices, vertex_count, cache_size, workspace)?;
946    indices.copy_from_slice(&result);
947    Ok(())
948}
949fn fifo(
950    out: &mut [u32],
951    indices: &[u32],
952    v: usize,
953    cache_size: u32,
954    budget: &mut Budget<'_>,
955    work: &mut Work,
956) -> Result<(), Error> {
957    if indices.is_empty() {
958        return Ok(());
959    }
960    let length = v
961        .checked_mul(4)
962        .and_then(|n| indices.len().checked_mul(2).and_then(|m| n.checked_add(m)))
963        .ok_or(Error::SizeOverflow)?;
964    let owned = budget.bytes();
965    let ws = &mut *budget.ws;
966    let old_integer_len = ws.integers.len();
967    let old_flag_len = ws.flags.len();
968    ws.prepare([length, 0, indices.len() / 3, 0], owned)?;
969    // prepare initializes every newly extended element to zero. Only retained
970    // active elements can contain state from an earlier operation.
971    ws.integers[..old_integer_len.min(v)].fill(0);
972    let old_hot = old_integer_len.saturating_sub(v * 2).min(v * 2);
973    ws.integers[v * 2..v * 2 + old_hot].fill(0);
974    ws.flags[..old_flag_len.min(indices.len() / 3)].fill(0);
975    let (counts, rest) = ws.integers[..length].split_at_mut(v);
976    let (offsets, rest) = rest.split_at_mut(v);
977    let (hot, rest) = rest.split_at_mut(v * 2);
978    let hot = hot.as_chunks_mut::<2>().0;
979    let (adjacency, dead) = rest.split_at_mut(indices.len());
980    let emitted = &mut ws.flags[..indices.len() / 3];
981    let charged = work.precharge(indices.len(), 1)?;
982    for &i in indices {
983        if !charged {
984            work.add(1)?;
985        }
986        counts[i as usize] += 1;
987    }
988    let mut offset = 0;
989    let charged = work.precharge(v, 1)?;
990    for (dst, &count) in offsets.iter_mut().zip(counts.iter()) {
991        if !charged {
992            work.add(1)?;
993        }
994        *dst = offset;
995        offset += count;
996    }
997    let triangles = indices.as_chunks::<3>().0;
998    if work.precharge(indices.len(), 1)? {
999        // The triangle id is shared by its three corners. Iterating records
1000        // avoids dividing an index-stream offset for every adjacency entry.
1001        for (i, triangle) in triangles.iter().enumerate() {
1002            for &j in triangle {
1003                adjacency[offsets[j as usize] as usize] = i as u32;
1004                offsets[j as usize] += 1;
1005            }
1006        }
1007    } else {
1008        for (i, &j) in indices.iter().enumerate() {
1009            work.add(1)?;
1010            adjacency[offsets[j as usize] as usize] = (i / 3) as u32;
1011            offsets[j as usize] += 1;
1012        }
1013    }
1014    let charged = work.precharge(v, 1)?;
1015    for ((offset, &count), hot) in offsets.iter_mut().zip(counts.iter()).zip(hot.iter_mut()) {
1016        if !charged {
1017            work.add(1)?;
1018        }
1019        *offset -= count;
1020        hot[0] = count;
1021    }
1022    let mut current = 0u32;
1023    let mut timestamp = cache_size.wrapping_add(1);
1024    let mut cursor = 1usize;
1025    let mut top = 0usize;
1026    let mut write = 0usize;
1027    let destination = out[..indices.len()].as_chunks_mut::<3>().0;
1028    while current != u32::MAX {
1029        work.add(1)?;
1030        let begin = top;
1031        let j = current as usize;
1032        let adjacent = &adjacency[offsets[j] as usize..(offsets[j] + counts[j]) as usize];
1033        let charged = work.precharge(adjacent.len(), 1)?;
1034        for &triangle in adjacent {
1035            if !charged {
1036                work.add(1)?;
1037            }
1038            let t = triangle as usize;
1039            if emitted[t] != 0 {
1040                continue;
1041            }
1042            let tri = &triangles[t];
1043            destination[write].copy_from_slice(tri);
1044            write += 1;
1045            dead[top..top + 3].copy_from_slice(tri);
1046            top += 3;
1047            for &index in tri {
1048                let vertex = &mut hot[index as usize];
1049                vertex[0] -= 1;
1050                if timestamp.wrapping_sub(vertex[1]) > cache_size {
1051                    vertex[1] = timestamp;
1052                    timestamp = timestamp.wrapping_add(1);
1053                }
1054            }
1055            emitted[t] = 1;
1056        }
1057        current = u32::MAX;
1058        let mut best = -1i32;
1059        let candidates = &dead[begin..top];
1060        let charged = work.precharge(candidates.len(), 1)?;
1061        for &candidate in candidates {
1062            if !charged {
1063                work.add(1)?;
1064            }
1065            let vertex = hot[candidate as usize];
1066            if vertex[0] != 0 {
1067                let age = timestamp.wrapping_sub(vertex[1]);
1068                let priority = if vertex[0].wrapping_mul(2).wrapping_add(age) <= cache_size {
1069                    age as i32
1070                } else {
1071                    0
1072                };
1073                if priority > best {
1074                    current = candidate;
1075                    best = priority;
1076                }
1077            }
1078        }
1079        if current == u32::MAX {
1080            work.search(top, |_| {
1081                top -= 1;
1082                let vertex = dead[top];
1083                if hot[vertex as usize][0] > 0 {
1084                    current = vertex;
1085                    true
1086                } else {
1087                    false
1088                }
1089            })?;
1090            if current == u32::MAX {
1091                work.search(v - cursor, |_| {
1092                    if hot[cursor][0] > 0 {
1093                        current = cursor as u32;
1094                        true
1095                    } else {
1096                        cursor += 1;
1097                        false
1098                    }
1099                })?;
1100            }
1101        }
1102    }
1103    Ok(())
1104}
1105
1106/// The source-compatible u32 entry point; see [`optimize_vertex_cache_with_table_generic`] for selectable index widths.
1107#[inline]
1108pub fn optimize_vertex_cache_with_table(
1109    indices: &[u32],
1110    vertex_count: usize,
1111    table: &VertexScoreTable,
1112    workspace: &mut Workspace,
1113) -> Result<Vec<u32>, Error> {
1114    optimize_vertex_cache_with_table_generic::<u32>(indices, vertex_count, table, workspace)
1115}
1116
1117/// The source-compatible u32 entry point; see [`optimize_vertex_cache_with_table_into_generic`] for selectable index widths.
1118#[inline]
1119pub fn optimize_vertex_cache_with_table_into(
1120    destination: &mut [u32],
1121    indices: &[u32],
1122    vertex_count: usize,
1123    table: &VertexScoreTable,
1124    workspace: &mut Workspace,
1125) -> Result<(), Error> {
1126    optimize_vertex_cache_with_table_into_generic::<u32>(
1127        destination,
1128        indices,
1129        vertex_count,
1130        table,
1131        workspace,
1132    )
1133}
1134
1135/// The source-compatible u32 entry point; see [`optimize_vertex_cache_generic`] for selectable index widths.
1136#[inline]
1137pub fn optimize_vertex_cache(
1138    indices: &[u32],
1139    vertex_count: usize,
1140    workspace: &mut Workspace,
1141) -> Result<Vec<u32>, Error> {
1142    optimize_vertex_cache_generic::<u32>(indices, vertex_count, workspace)
1143}
1144
1145/// The source-compatible u32 entry point; see [`optimize_vertex_cache_into_generic`] for selectable index widths.
1146#[inline]
1147pub fn optimize_vertex_cache_into(
1148    destination: &mut [u32],
1149    indices: &[u32],
1150    vertex_count: usize,
1151    workspace: &mut Workspace,
1152) -> Result<(), Error> {
1153    optimize_vertex_cache_into_generic::<u32>(destination, indices, vertex_count, workspace)
1154}
1155
1156/// The source-compatible u32 entry point; see [`optimize_vertex_cache_in_place_generic`] for selectable index widths.
1157#[inline]
1158pub fn optimize_vertex_cache_in_place(
1159    indices: &mut [u32],
1160    vertex_count: usize,
1161    workspace: &mut Workspace,
1162) -> Result<(), Error> {
1163    optimize_vertex_cache_in_place_generic::<u32>(indices, vertex_count, workspace)
1164}
1165
1166/// The source-compatible u32 entry point; see [`optimize_vertex_cache_strip_generic`] for selectable index widths.
1167#[inline]
1168pub fn optimize_vertex_cache_strip(
1169    indices: &[u32],
1170    vertex_count: usize,
1171    workspace: &mut Workspace,
1172) -> Result<Vec<u32>, Error> {
1173    optimize_vertex_cache_strip_generic::<u32>(indices, vertex_count, workspace)
1174}
1175
1176/// The source-compatible u32 entry point; see [`optimize_vertex_cache_strip_into_generic`] for selectable index widths.
1177#[inline]
1178pub fn optimize_vertex_cache_strip_into(
1179    destination: &mut [u32],
1180    indices: &[u32],
1181    vertex_count: usize,
1182    workspace: &mut Workspace,
1183) -> Result<(), Error> {
1184    optimize_vertex_cache_strip_into_generic::<u32>(destination, indices, vertex_count, workspace)
1185}
1186
1187/// The source-compatible u32 entry point; see [`optimize_vertex_cache_strip_in_place_generic`] for selectable index widths.
1188#[inline]
1189pub fn optimize_vertex_cache_strip_in_place(
1190    indices: &mut [u32],
1191    vertex_count: usize,
1192    workspace: &mut Workspace,
1193) -> Result<(), Error> {
1194    optimize_vertex_cache_strip_in_place_generic::<u32>(indices, vertex_count, workspace)
1195}
1196
1197/// The source-compatible u32 entry point; see [`optimize_vertex_cache_fifo_generic`] for selectable index widths.
1198#[inline]
1199pub fn optimize_vertex_cache_fifo(
1200    indices: &[u32],
1201    vertex_count: usize,
1202    cache_size: u32,
1203    workspace: &mut Workspace,
1204) -> Result<Vec<u32>, Error> {
1205    optimize_vertex_cache_fifo_generic::<u32>(indices, vertex_count, cache_size, workspace)
1206}
1207
1208/// The source-compatible u32 entry point; see [`optimize_vertex_cache_fifo_into_generic`] for selectable index widths.
1209#[inline]
1210pub fn optimize_vertex_cache_fifo_into(
1211    destination: &mut [u32],
1212    indices: &[u32],
1213    vertex_count: usize,
1214    cache_size: u32,
1215    workspace: &mut Workspace,
1216) -> Result<(), Error> {
1217    optimize_vertex_cache_fifo_into_generic::<u32>(
1218        destination,
1219        indices,
1220        vertex_count,
1221        cache_size,
1222        workspace,
1223    )
1224}
1225
1226/// The source-compatible u32 entry point; see [`optimize_vertex_cache_fifo_in_place_generic`] for selectable index widths.
1227#[inline]
1228pub fn optimize_vertex_cache_fifo_in_place(
1229    indices: &mut [u32],
1230    vertex_count: usize,
1231    cache_size: u32,
1232    workspace: &mut Workspace,
1233) -> Result<(), Error> {
1234    optimize_vertex_cache_fifo_in_place_generic::<u32>(indices, vertex_count, cache_size, workspace)
1235}