1use 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#[derive(Clone, Debug, PartialEq)]
24pub struct VertexScoreTable {
25 cache: [f32; 17],
26 live: [f32; 9],
27}
28
29impl VertexScoreTable {
30 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 pub fn cache_scores(&self) -> &[f32; 17] {
48 &self.cache
49 }
50
51 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#[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#[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#[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#[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#[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 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 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#[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 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#[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 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 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#[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 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 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#[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#[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#[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#[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#[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#[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 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 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#[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#[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#[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#[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#[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#[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#[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#[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#[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#[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#[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}