1use crate::workspace::{checked_bytes, topology, Work};
3use crate::{validate_vertex_flags, Attributes, Error, Positions, VertexFlags, Workspace};
4use alloc::vec::Vec;
5#[path = "simplify_extra.rs"]
6mod extra;
7pub(crate) use extra::SloppyScratch;
8pub use extra::{
9 simplify_points, simplify_points_into, simplify_prune, simplify_prune_into, simplify_sloppy,
10 simplify_sloppy_into, simplify_with_update,
11};
12
13#[inline(always)]
17fn sqrt(value: f32) -> f32 {
18 #[cfg(feature = "std")]
19 if value.to_bits() < 0x7f80_0000 {
20 return value.sqrt();
21 }
22 crate::math::sqrt(value)
23}
24
25#[cfg(not(feature = "std"))]
26type SqrtCache = crate::math::SqrtCache;
27
28#[cfg(feature = "std")]
31struct SqrtCache;
32#[cfg(feature = "std")]
33impl SqrtCache {
34 const fn new() -> Self {
35 Self
36 }
37 #[inline(always)]
38 fn sqrt(&mut self, value: f32) -> f32 {
39 sqrt(value)
40 }
41}
42
43trait Meter {
50 fn add(&mut self, count: usize) -> Result<(), Error>;
51 fn precharge(&mut self, count: usize, units: usize) -> Result<bool, Error>;
52 fn scan<T>(
53 &mut self,
54 values: impl ExactSizeIterator<Item = T>,
55 visit: impl FnMut(T) -> Result<(), Error>,
56 ) -> Result<(), Error>;
57}
58impl Meter for Work {
59 #[inline(always)]
60 fn add(&mut self, count: usize) -> Result<(), Error> {
61 Work::add(self, count)
62 }
63 #[inline(always)]
64 fn precharge(&mut self, count: usize, units: usize) -> Result<bool, Error> {
65 Work::precharge(self, count, units)
66 }
67 #[inline(always)]
68 fn scan<T>(
69 &mut self,
70 values: impl ExactSizeIterator<Item = T>,
71 visit: impl FnMut(T) -> Result<(), Error>,
72 ) -> Result<(), Error> {
73 Work::scan(self, values, visit)
74 }
75}
76struct Prepaid(usize);
77impl Meter for Prepaid {
78 #[inline(always)]
79 fn add(&mut self, count: usize) -> Result<(), Error> {
80 self.0 += count;
81 Ok(())
82 }
83 #[inline(always)]
84 fn precharge(&mut self, count: usize, units: usize) -> Result<bool, Error> {
85 self.0 += count.checked_mul(units).ok_or(Error::SizeOverflow)?;
86 Ok(true)
87 }
88 #[inline(always)]
89 fn scan<T>(
90 &mut self,
91 values: impl ExactSizeIterator<Item = T>,
92 mut visit: impl FnMut(T) -> Result<(), Error>,
93 ) -> Result<(), Error> {
94 let count = values.len();
95 for (i, value) in values.enumerate() {
96 if let Err(error) = visit(value) {
97 self.0 += i + 1;
98 return Err(error);
99 }
100 }
101 self.0 += count;
102 Ok(())
103 }
104}
105macro_rules! metered {
108 ($work:expr, $bound:expr, |$m:ident| $body:expr) => {{
109 let work: &mut Work = $work;
110 match $bound {
111 Some(bound) if work.covers(bound)? => {
112 let mut tally = Prepaid(0);
113 let result = {
114 let $m = &mut tally;
115 $body
116 };
117 debug_assert!(tally.0 <= bound);
118 work.add(tally.0)?;
119 result
120 }
121 _ => {
122 let $m = work;
123 $body
124 }
125 }
126 }};
127}
128
129#[derive(Clone, Copy, Debug, Default, PartialEq, Eq)]
131pub struct SimplifyOptions(u32);
132impl SimplifyOptions {
133 pub const EMPTY: Self = Self(0);
135 pub const LOCK_BORDER: Self = Self(1);
137 pub const SPARSE: Self = Self(2);
139 pub const ERROR_ABSOLUTE: Self = Self(4);
141 pub const PRUNE: Self = Self(8);
143 pub const REGULARIZE: Self = Self(16);
145 pub const PERMISSIVE: Self = Self(32);
147 pub const REGULARIZE_LIGHT: Self = Self(64);
149 #[cfg(feature = "experimental")]
151 pub const PRESERVE_FOLDS: Self = Self(128);
152 #[cfg(feature = "experimental")]
154 pub const ERROR_CLAMPED: Self = Self(256);
155 pub const fn from_bits(bits: u32) -> Result<Self, Error> {
160 let mask = if cfg!(feature = "experimental") {
161 511
162 } else {
163 127
164 };
165 if bits & !mask != 0 {
166 Err(Error::UnknownFlags)
167 } else {
168 Ok(Self(bits))
169 }
170 }
171 pub const fn bits(self) -> u32 {
173 self.0
174 }
175 pub const fn contains(self, other: Self) -> bool {
177 self.0 & other.0 == other.0
178 }
179}
180impl core::ops::BitOr for SimplifyOptions {
181 type Output = Self;
182 fn bitor(self, rhs: Self) -> Self {
183 Self(self.0 | rhs.0)
184 }
185}
186impl core::ops::BitOrAssign for SimplifyOptions {
187 fn bitor_assign(&mut self, rhs: Self) {
188 self.0 |= rhs.0;
189 }
190}
191#[derive(Clone, Copy, Debug)]
193pub struct SimplifySettings {
194 pub target_index_count: usize,
196 pub target_error: f32,
198 pub options: SimplifyOptions,
200}
201#[derive(Debug)]
203pub struct SimplifiedMesh {
204 pub indices: Vec<u32>,
206 pub error: f32,
208}
209#[derive(Clone, Copy, Debug)]
211pub struct SimplifyResult {
212 pub index_count: usize,
214 pub error: f32,
216}
217pub fn simplify_scale(positions: Positions<'_>) -> Result<f32, Error> {
227 let Some(values) = positions.packed_values() else {
228 return scale_view(positions);
229 };
230 let finite = values
234 .as_flattened()
235 .iter()
236 .fold(true, |finite, v| finite & v.is_finite());
237 if !finite {
238 return Err(Error::InvalidParameter);
239 }
240 let mut lo = [f32::MAX; 3];
241 let mut hi = [-f32::MAX; 3];
242 for v in values {
243 for j in 0..3 {
244 if lo[j] > v[j] {
245 lo[j] = v[j];
246 }
247 if hi[j] < v[j] {
248 hi[j] = v[j];
249 }
250 }
251 }
252 if values.is_empty() {
253 return Ok(0.0);
254 }
255 let mut extent = 0.0;
256 for j in 0..3 {
257 let d = hi[j] - lo[j];
258 if d >= extent {
259 extent = d;
260 }
261 }
262 if !extent.is_finite() {
263 return Err(Error::NumericalFailure);
264 }
265 Ok(extent)
266}
267#[inline(never)]
269fn scale_view(positions: Positions<'_>) -> Result<f32, Error> {
270 if let Some(records) = positions.scale_full_records() {
271 return scale_records(records, positions.is_empty());
272 }
273 if let Some(records) = positions.scale_records() {
274 return scale_records(records, positions.is_empty());
275 }
276 Ok(bounds(positions)?.1)
277}
278fn scale_records(
279 values: impl Iterator<Item = [f32; 3]> + Clone,
280 empty: bool,
281) -> Result<f32, Error> {
282 let finite = values.clone().fold(true, |finite, v| {
285 finite & v[0].is_finite() & v[1].is_finite() & v[2].is_finite()
286 });
287 if !finite {
288 return Err(Error::InvalidParameter);
289 }
290 let mut lo = [f32::MAX; 3];
291 let mut hi = [-f32::MAX; 3];
292 for v in values {
293 for j in 0..3 {
294 if lo[j] > v[j] {
295 lo[j] = v[j];
296 }
297 if hi[j] < v[j] {
298 hi[j] = v[j];
299 }
300 }
301 }
302 if empty {
303 return Ok(0.0);
304 }
305 let mut extent = 0.0;
306 for j in 0..3 {
307 let d = hi[j] - lo[j];
308 if d >= extent {
309 extent = d;
310 }
311 }
312 if !extent.is_finite() {
313 return Err(Error::NumericalFailure);
314 }
315 Ok(extent)
316}
317fn bounds_impl<const VALIDATED: bool>(p: Positions<'_>) -> Result<([f32; 3], f32), Error> {
318 let mut lo = [f32::MAX; 3];
319 let mut hi = [-f32::MAX; 3];
320 p.for_each(|v| {
321 for j in 0..3 {
322 if !VALIDATED && !v[j].is_finite() {
323 return Err(Error::InvalidParameter);
324 }
325 if lo[j] > v[j] {
326 lo[j] = v[j];
327 }
328 if hi[j] < v[j] {
329 hi[j] = v[j];
330 }
331 }
332 Ok(())
333 })?;
334 if p.is_empty() {
335 return Ok((lo, 0.0));
336 }
337 let mut extent = 0.0;
338 for j in 0..3 {
339 let d = hi[j] - lo[j];
340 if d >= extent {
341 extent = d;
342 }
343 }
344 if !extent.is_finite() {
345 return Err(Error::NumericalFailure);
346 }
347 Ok((lo, extent))
348}
349fn bounds(p: Positions<'_>) -> Result<([f32; 3], f32), Error> {
351 bounds_impl::<false>(p)
352}
353pub fn simplify(
361 indices: &[u32],
362 positions: Positions<'_>,
363 settings: SimplifySettings,
364 workspace: &mut Workspace,
365) -> Result<SimplifiedMesh, Error> {
366 allocating(indices, positions, None, &[], None, settings, workspace)
367}
368pub fn simplify_with_attributes(
376 indices: &[u32],
377 positions: Positions<'_>,
378 attributes: Attributes<'_>,
379 weights: &[f32],
380 vertex_flags: Option<&[VertexFlags]>,
381 settings: SimplifySettings,
382 workspace: &mut Workspace,
383) -> Result<SimplifiedMesh, Error> {
384 allocating(
385 indices,
386 positions,
387 Some(attributes),
388 weights,
389 vertex_flags,
390 settings,
391 workspace,
392 )
393}
394fn allocating(
395 indices: &[u32],
396 positions: Positions<'_>,
397 attributes: Option<Attributes<'_>>,
398 weights: &[f32],
399 flags: Option<&[VertexFlags]>,
400 settings: SimplifySettings,
401 ws: &mut Workspace,
402) -> Result<SimplifiedMesh, Error> {
403 let mut work = ws.begin();
404 let result = (|| {
405 validate(
406 indices, positions, attributes, weights, flags, settings, &mut work,
407 )?;
408 ws.acquire(crate::workspace::ScratchFamily::Simplify);
409 ws.prepare([0; 4], checked_bytes(indices.len(), 4)?)?;
410 let mut out = crate::workspace::output(indices.len())?;
411 let output_bytes = checked_bytes(out.capacity(), 4)?;
412 let r = run(
413 &mut out,
414 indices,
415 positions,
416 attributes,
417 weights,
418 flags,
419 settings,
420 ws,
421 &mut work,
422 output_bytes,
423 )?;
424 out.truncate(r.index_count);
425 Ok(SimplifiedMesh {
426 indices: out,
427 error: r.error,
428 })
429 })();
430 ws.finish(&work);
431 result
432}
433pub fn simplify_into(
440 destination: &mut [u32],
441 indices: &[u32],
442 positions: Positions<'_>,
443 settings: SimplifySettings,
444 workspace: &mut Workspace,
445) -> Result<SimplifyResult, Error> {
446 into(
447 destination,
448 indices,
449 positions,
450 None,
451 &[],
452 None,
453 settings,
454 workspace,
455 )
456}
457#[allow(clippy::too_many_arguments)]
463pub fn simplify_with_attributes_into(
464 destination: &mut [u32],
465 indices: &[u32],
466 positions: Positions<'_>,
467 attributes: Attributes<'_>,
468 weights: &[f32],
469 vertex_flags: Option<&[VertexFlags]>,
470 settings: SimplifySettings,
471 workspace: &mut Workspace,
472) -> Result<SimplifyResult, Error> {
473 into(
474 destination,
475 indices,
476 positions,
477 Some(attributes),
478 weights,
479 vertex_flags,
480 settings,
481 workspace,
482 )
483}
484#[allow(clippy::too_many_arguments)]
485fn into(
486 out: &mut [u32],
487 indices: &[u32],
488 p: Positions<'_>,
489 a: Option<Attributes<'_>>,
490 weights: &[f32],
491 flags: Option<&[VertexFlags]>,
492 settings: SimplifySettings,
493 ws: &mut Workspace,
494) -> Result<SimplifyResult, Error> {
495 let mut work = ws.begin();
496 let result = (|| {
497 if out.len() < indices.len() {
498 return Err(Error::BufferTooSmall);
499 }
500 validate(indices, p, a, weights, flags, settings, &mut work)?;
501 ws.acquire(crate::workspace::ScratchFamily::Simplify);
502 run(
503 out, indices, p, a, weights, flags, settings, ws, &mut work, 0,
504 )
505 })();
506 ws.finish(&work);
507 result
508}
509#[allow(clippy::too_many_arguments)]
510fn validate(
511 indices: &[u32],
512 p: Positions<'_>,
513 a: Option<Attributes<'_>>,
514 weights: &[f32],
515 flags: Option<&[VertexFlags]>,
516 s: SimplifySettings,
517 work: &mut Work,
518) -> Result<(), Error> {
519 topology(indices, p.len(), work)?;
520 if s.target_index_count > indices.len() || !s.target_error.is_finite() || s.target_error < 0.0 {
521 return Err(Error::InvalidParameter);
522 }
523 validate_vertex_flags(flags, p.len())?;
524 if let Some(a) = a {
525 if a.len() != p.len() || a.components() != weights.len() {
526 return Err(Error::InvalidLayout);
527 }
528 }
529 work.scan(weights.iter().copied(), |w| {
530 if !w.is_finite() || w < 0.0 {
531 return Err(Error::InvalidParameter);
532 }
533 Ok(())
534 })?;
535 if a.is_none() {
536 if let Some(records) = p.scale_full_records() {
537 return work.scan(records, |v| {
538 if v.iter().fold(true, |finite, x| finite & x.is_finite()) {
539 Ok(())
540 } else {
541 Err(Error::InvalidParameter)
542 }
543 });
544 }
545 return p.for_each_counted(work, |v| {
546 if !v.iter().fold(true, |finite, x| finite & x.is_finite()) {
547 Err(Error::InvalidParameter)
548 } else {
549 Ok(())
550 }
551 });
552 }
553 for i in 0..p.len() {
554 work.add(1)?;
555 if !p
556 .at(i)?
557 .iter()
558 .fold(true, |finite, x| finite & x.is_finite())
559 {
560 return Err(Error::InvalidParameter);
561 }
562 if let Some(a) = a {
563 if let Some(values) = a.float_record(i) {
564 work.scan(values.iter().copied(), |value| {
565 if value.is_finite() {
566 Ok(())
567 } else {
568 Err(Error::InvalidParameter)
569 }
570 })?;
571 } else {
572 work.scan(0..a.components(), |k| {
573 if !a.get(i, k).ok_or(Error::InvalidLayout)?.is_finite() {
574 return Err(Error::InvalidParameter);
575 }
576 Ok(())
577 })?;
578 }
579 }
580 }
581 Ok(())
582}
583#[derive(Clone, Copy, Default, Debug)]
584struct V {
585 x: f32,
586 y: f32,
587 z: f32,
588}
589impl From<[f32; 3]> for V {
590 fn from(v: [f32; 3]) -> Self {
591 Self {
592 x: v[0],
593 y: v[1],
594 z: v[2],
595 }
596 }
597}
598impl V {
599 #[inline(always)]
600 fn sub(self, b: Self) -> Self {
601 Self {
602 x: self.x - b.x,
603 y: self.y - b.y,
604 z: self.z - b.z,
605 }
606 }
607 #[inline(always)]
608 fn dot(self, b: Self) -> f32 {
609 self.x * b.x + self.y * b.y + self.z * b.z
610 }
611 #[inline(always)]
612 fn cross(self, b: Self) -> Self {
613 Self {
614 x: self.y * b.z - self.z * b.y,
615 y: self.z * b.x - self.x * b.z,
616 z: self.x * b.y - self.y * b.x,
617 }
618 }
619 #[inline(always)]
620 fn normalize(&mut self, cache: &mut SqrtCache) -> f32 {
621 let l = cache.sqrt(self.dot(*self));
622 if l > 0.0 {
623 self.x /= l;
624 self.y /= l;
625 self.z /= l;
626 }
627 l
628 }
629}
630#[derive(Clone, Copy, Default)]
631struct Q {
632 a00: f32,
633 a11: f32,
634 a22: f32,
635 a10: f32,
636 a20: f32,
637 a21: f32,
638 b0: f32,
639 b1: f32,
640 b2: f32,
641 c: f32,
642 w: f32,
643 inverse_weight: f32,
645}
646impl Q {
647 #[inline(always)]
648 fn add(&mut self, r: Self) {
649 self.a00 += r.a00;
650 self.a11 += r.a11;
651 self.a22 += r.a22;
652 self.a10 += r.a10;
653 self.a20 += r.a20;
654 self.a21 += r.a21;
655 self.b0 += r.b0;
656 self.b1 += r.b1;
657 self.b2 += r.b2;
658 self.c += r.c;
659 self.w += r.w;
660 }
661 #[inline(always)]
662 fn eval(self, v: V) -> f32 {
663 let mut rx = (self.b0 + self.a10 * v.y) * 2.0;
664 let mut ry = (self.b1 + self.a21 * v.z) * 2.0;
665 let mut rz = (self.b2 + self.a20 * v.x) * 2.0;
666 rx += self.a00 * v.x;
667 ry += self.a11 * v.y;
668 rz += self.a22 * v.z;
669 self.c + rx * v.x + ry * v.y + rz * v.z
670 }
671 #[inline(always)]
672 fn error(self, v: V) -> f32 {
673 self.eval(v).abs() * self.inverse_weight
674 }
675 fn cache_inverse_weight(&mut self) {
676 self.inverse_weight = if self.w == 0.0 { 0.0 } else { 1.0 / self.w };
677 }
678 #[inline(always)]
679 fn plane(n: V, d: f32, w: f32) -> Self {
680 let aw = n.x * w;
681 let bw = n.y * w;
682 let cw = n.z * w;
683 let dw = d * w;
684 Self {
685 a00: n.x * aw,
686 a11: n.y * bw,
687 a22: n.z * cw,
688 a10: n.x * bw,
689 a20: n.x * cw,
690 a21: n.y * cw,
691 b0: n.x * dw,
692 b1: n.y * dw,
693 b2: n.z * dw,
694 c: d * dw,
695 w,
696 inverse_weight: 0.0,
697 }
698 }
699 #[inline(always)]
700 fn point(p: V, w: f32) -> Self {
701 Self {
702 a00: w,
703 a11: w,
704 a22: w,
705 b0: -p.x * w,
706 b1: -p.y * w,
707 b2: -p.z * w,
708 c: p.dot(p) * w,
709 w,
710 ..Self::default()
711 }
712 }
713 #[inline(always)]
714 fn triangle(a: V, b: V, c: V, w: f32, cache: &mut SqrtCache) -> Self {
715 let mut n = b.sub(a).cross(c.sub(a));
716 let area = n.normalize(cache);
717 Self::plane(n, -n.dot(a), cache.sqrt(area) * w)
718 }
719 #[inline(always)]
720 fn edge(a: V, b: V, c: V, w: f32, cache: &mut SqrtCache) -> Self {
721 let p10 = b.sub(a);
722 let ls = p10.dot(p10);
723 let p20 = c.sub(a);
724 let proj = p20.dot(p10);
725 let mut perp = V {
726 x: p20.x * ls - p10.x * proj,
727 y: p20.y * ls - p10.y * proj,
728 z: p20.z * ls - p10.z * proj,
729 };
730 perp.normalize(cache);
731 Self::plane(perp, -perp.dot(a), cache.sqrt(ls) * w)
732 }
733 #[inline(always)]
734 fn finite(self) -> bool {
735 [
739 self.a00, self.a11, self.a22, self.a10, self.a20, self.a21, self.b0, self.b1, self.b2,
740 self.c, self.w,
741 ]
742 .into_iter()
743 .map(|x| x.to_bits() & 0x7fff_ffff)
744 .max()
745 .unwrap_or(0)
746 < 0x7f80_0000
747 }
748}
749#[derive(Clone, Copy, Default)]
750struct G {
751 x: f32,
752 y: f32,
753 z: f32,
754 w: f32,
755}
756impl G {
757 fn add(&mut self, r: Self) {
758 self.x += r.x;
759 self.y += r.y;
760 self.z += r.z;
761 self.w += r.w;
762 }
763}
764#[derive(Clone, Copy, Default)]
765struct Edge {
766 next: u32,
767 prev: u32,
768}
769#[derive(Clone, Copy, Default)]
770struct Collapse {
771 a: u32,
772 b: u32,
773 error: f32,
774}
775const NONE: usize = u32::MAX as usize;
776const MAN: u8 = 0;
777const BORDER: u8 = 1;
778const SEAM: u8 = 2;
779const COMPLEX: u8 = 3;
780const FRINGE: u8 = 4;
781const LOCKED: u8 = 5;
782const CAN: [[u8; 6]; 6] = [
783 [1, 1, 1, 1, 1, 1],
784 [0, 1, 0, 0, 1, 1],
785 [0, 0, 1, 0, 0, 1],
786 [0, 0, 0, 1, 1, 1],
787 [0, 0, 0, 0, 1, 0],
788 [0; 6],
789];
790const OPP: [[u8; 6]; 6] = [
791 [1; 6],
792 [1, 0, 1, 0, 0, 0],
793 [1, 1, 1, 0, 0, 1],
794 [1, 0, 0, 0, 0, 0],
795 [1, 0, 0, 0, 0, 0],
796 [1, 0, 1, 0, 0, 0],
797];
798const PICK_ANY: u8 = 1;
800const PICK_BOTH: u8 = 2;
801const PICK_FORWARD: u8 = 4;
802const PICK_OPPOSITE: u8 = 8;
803const PICK_CHECK_FORWARD: u8 = 16;
804const PICK_CHECK_BACK: u8 = 32;
805const PICK: [u8; 64] = {
806 let mut table = [0; 64];
807 let mut k0 = 0;
808 while k0 < 6 {
809 let mut k1 = 0;
810 while k1 < 6 {
811 let forward = CAN[k0][k1] != 0;
812 let reverse = CAN[k1][k0] != 0;
813 let mut rule = 0;
814 if forward || reverse {
815 rule |= PICK_ANY;
816 }
817 if forward && reverse {
818 rule |= PICK_BOTH;
819 }
820 if forward {
821 rule |= PICK_FORWARD;
822 }
823 if OPP[k0][k1] != 0 {
824 rule |= PICK_OPPOSITE;
825 }
826 let loop0 = k0 == BORDER as usize || k0 == SEAM as usize;
827 let loop1 = k1 == BORDER as usize || k1 == SEAM as usize;
828 if loop0 && k1 != MAN as usize {
829 rule |= PICK_CHECK_FORWARD;
830 }
831 if loop1 && k0 != MAN as usize {
832 rule |= PICK_CHECK_BACK;
833 }
834 table[k0 * 8 + k1] = rule;
835 k1 += 1;
836 }
837 k0 += 1;
838 }
839 table
840};
841#[inline(always)]
843fn pair(k0: u8, k1: u8) -> usize {
844 ((k0 as usize) << 3 | k1 as usize) & 63
845}
846struct Indices(Vec<u32>);
849impl Indices {
850 #[inline]
851 fn get(&self, i: usize) -> usize {
852 self.0[i] as usize
853 }
854 #[inline]
855 fn set(&mut self, i: usize, value: usize) {
856 self.0[i] = value as u32;
857 }
858 fn fill(&mut self, value: usize) {
859 self.0.fill(value as u32);
860 }
861 fn len(&self) -> usize {
862 self.0.len()
863 }
864}
865pub(crate) struct State {
866 vertex_count: usize,
867 sqrt_cache: SqrtCache,
868 offsets: Indices,
869 edges: Vec<Edge>,
870 remap: Indices,
871 wedge: Indices,
872 kind: Vec<u8>,
873 forward: Indices,
874 back: Indices,
875 p: Vec<V>,
876 a: Vec<f32>,
877 q: Vec<Q>,
878 aq: Vec<Q>,
879 g: Vec<G>,
880 vg: Vec<G>,
881 sparse: Vec<u32>,
882 original: Vec<u32>,
883 clamped: bool,
884 collapses: Vec<Collapse>,
885 order: Indices,
886 cr: Indices,
887 locked: Vec<bool>,
888 table: Indices,
889 max_degree: usize,
891 ac: usize,
892 bytes: usize,
893}
894struct Input<'a> {
897 indices: &'a [u32],
898 original: Vec<u32>,
899 update: bool,
900}
901impl<'a> Input<'a> {
902 fn borrowed(indices: &'a [u32]) -> Self {
903 Self {
904 indices,
905 original: Vec::new(),
906 update: false,
907 }
908 }
909 fn as_slice(&self) -> &[u32] {
910 if self.update {
911 &self.original
912 } else {
913 self.indices
914 }
915 }
916}
917struct Budget<'a> {
918 ws: &'a mut Workspace,
919 bytes: usize,
920 charged: bool,
921}
922impl<'a> Budget<'a> {
923 fn new(ws: &'a mut Workspace, bytes: usize) -> Self {
924 Self {
925 ws,
926 bytes,
927 charged: false,
928 }
929 }
930 fn reclaim_input(
931 &mut self,
932 original: &mut Vec<u32>,
933 added: Result<usize, Error>,
934 ) -> Result<(), Error> {
935 let requested =
936 added.and_then(|added| self.bytes.checked_add(added).ok_or(Error::SizeOverflow));
937 if requested.is_ok_and(|bytes| bytes > self.ws.limits().max_bytes) {
938 let before = checked_bytes(original.capacity(), 4)?;
939 crate::workspace::shrink(original, true)?;
940 self.bytes -= before - checked_bytes(original.capacity(), 4)?;
941 self.charged = false;
942 }
943 Ok(())
944 }
945 fn charge_current(&mut self) -> Result<(), Error> {
946 if !self.charged {
947 self.ws.charge_owned(self.bytes)?;
948 self.charged = true;
949 }
950 Ok(())
951 }
952 fn reuse_capacity<T>(&mut self, v: &mut Vec<T>, n: usize) -> Result<(), Error> {
953 let size = core::mem::size_of::<T>();
954 let old = checked_bytes(v.capacity(), size)?;
955 if self.bytes < old {
956 return Err(Error::SizeOverflow);
957 }
958 if n <= v.capacity() {
959 self.charge_current()?;
960 return Ok(());
961 }
962 let minimum = n;
963 let base = self.bytes.checked_sub(old).ok_or(Error::SizeOverflow)?;
964 let requested = checked_bytes(minimum, size)?;
965 self.ws
966 .charge_owned(base.checked_add(requested).ok_or(Error::SizeOverflow)?)?;
967 if n > v.capacity() {
968 v.try_reserve_exact(n.saturating_sub(v.len()))
969 .map_err(|_| Error::AllocationFailed)?;
970 }
971 self.bytes = base
972 .checked_add(checked_bytes(v.capacity(), size)?)
973 .ok_or(Error::SizeOverflow)?;
974 if v.capacity() != minimum {
975 self.ws.charge_owned(self.bytes)?;
976 }
977 self.charged = true;
978 Ok(())
979 }
980 fn reuse<T: Default + Clone>(&mut self, v: &mut Vec<T>, n: usize) -> Result<(), Error> {
981 self.reuse_capacity(v, n)?;
982 v.resize(n, T::default());
983 Ok(())
984 }
985 fn vec<T: Default + Clone>(&mut self, n: usize) -> Result<Vec<T>, Error> {
986 self.filled(n, T::default())
987 }
988 fn filled<T: Clone>(&mut self, n: usize, value: T) -> Result<Vec<T>, Error> {
989 let mut v = self.reserve(n)?;
990 v.resize(n, value);
991 Ok(v)
992 }
993 fn release<T>(&mut self, value: Vec<T>) {
994 self.bytes -= value.capacity() * core::mem::size_of::<T>();
995 drop(value);
996 }
997 fn reserve<T>(&mut self, n: usize) -> Result<Vec<T>, Error> {
998 let b = checked_bytes(n, core::mem::size_of::<T>())?;
999 self.ws
1000 .charge_owned(self.bytes.checked_add(b).ok_or(Error::SizeOverflow)?)?;
1001 let mut v = Vec::new();
1002 v.try_reserve_exact(n)
1003 .map_err(|_| Error::AllocationFailed)?;
1004 self.bytes = self
1005 .bytes
1006 .checked_add(checked_bytes(v.capacity(), core::mem::size_of::<T>())?)
1007 .ok_or(Error::SizeOverflow)?;
1008 if v.capacity() != n {
1009 self.ws.charge_owned(self.bytes)?;
1010 }
1011 self.charged = true;
1012 Ok(v)
1013 }
1014}
1015impl core::fmt::Debug for State {
1016 fn fmt(&self, f: &mut core::fmt::Formatter<'_>) -> core::fmt::Result {
1017 f.debug_struct("SimplifyScratch")
1018 .field("vertices", &self.vertex_count)
1019 .field("heap_bytes", &self.capacity_bytes())
1020 .finish()
1021 }
1022}
1023impl State {
1024 pub(crate) fn capacity_bytes(&self) -> Result<usize, Error> {
1025 let fields = [
1026 (self.offsets.0.capacity(), 4),
1027 (self.edges.capacity(), core::mem::size_of::<Edge>()),
1028 (self.remap.0.capacity(), 4),
1029 (self.wedge.0.capacity(), 4),
1030 (self.kind.capacity(), 1),
1031 (self.forward.0.capacity(), 4),
1032 (self.back.0.capacity(), 4),
1033 (self.p.capacity(), core::mem::size_of::<V>()),
1034 (self.a.capacity(), 4),
1035 (self.q.capacity(), core::mem::size_of::<Q>()),
1036 (self.aq.capacity(), core::mem::size_of::<Q>()),
1037 (self.g.capacity(), core::mem::size_of::<G>()),
1038 (self.vg.capacity(), core::mem::size_of::<G>()),
1039 (self.sparse.capacity(), 4),
1040 (self.original.capacity(), 4),
1041 (self.collapses.capacity(), core::mem::size_of::<Collapse>()),
1042 (self.order.0.capacity(), 4),
1043 (self.cr.0.capacity(), 4),
1044 (self.locked.capacity(), 1),
1045 (self.table.0.capacity(), 4),
1046 ];
1047 fields.into_iter().try_fold(0usize, |sum, (n, size)| {
1048 sum.checked_add(checked_bytes(n, size)?)
1049 .ok_or(Error::SizeOverflow)
1050 })
1051 }
1052 fn reclaim_for(
1053 &mut self,
1054 ws: &Workspace,
1055 requested: Result<usize, Error>,
1056 original: &mut Vec<u32>,
1057 ) -> Result<(), Error> {
1058 if !requested.is_ok_and(|bytes| bytes > ws.limits().max_bytes) {
1059 return Ok(());
1060 }
1061 let before = self.capacity_bytes()? + checked_bytes(original.capacity(), 4)?;
1062 self.remap.0.shrink_to(self.vertex_count);
1065 self.wedge.0.shrink_to(self.vertex_count);
1066 self.p.shrink_to(self.vertex_count);
1067 macro_rules! shrink {
1068 ($($v:expr),* $(,)?) => { $(crate::workspace::shrink(&mut $v, true)?;)* };
1069 }
1070 shrink!(
1071 self.offsets.0,
1072 self.edges,
1073 self.kind,
1074 self.forward.0,
1075 self.back.0,
1076 self.a,
1077 self.q,
1078 self.aq,
1079 self.g,
1080 self.vg,
1081 self.sparse,
1082 self.original,
1083 self.collapses,
1084 self.order.0,
1085 self.cr.0,
1086 self.locked,
1087 self.table.0,
1088 *original
1089 );
1090 let after = self.capacity_bytes()? + checked_bytes(original.capacity(), 4)?;
1091 self.bytes -= before - after;
1092 Ok(())
1093 }
1094 fn retain(mut self, ws: &mut Workspace) {
1095 if ws.retention() == crate::Retention::Lean {
1099 self.q = Vec::new();
1100 }
1101 if let Some(mut unused) = ws.simplify.take() {
1102 if self.a.capacity() == 0 {
1103 self.a = core::mem::take(&mut unused.a);
1104 }
1105 if self.aq.capacity() == 0 {
1106 self.aq = core::mem::take(&mut unused.aq);
1107 }
1108 if self.g.capacity() == 0 {
1109 self.g = core::mem::take(&mut unused.g);
1110 }
1111 if self.vg.capacity() == 0 {
1112 self.vg = core::mem::take(&mut unused.vg);
1113 }
1114 if self.sparse.capacity() == 0 {
1115 self.sparse = core::mem::take(&mut unused.sparse);
1116 }
1117 if self.original.capacity() == 0 {
1118 self.original = core::mem::take(&mut unused.original);
1119 }
1120 }
1121 ws.has_retained = true;
1122 ws.simplify = Some(self);
1123 }
1124 fn empty() -> Self {
1125 Self {
1126 vertex_count: 0,
1127 sqrt_cache: SqrtCache::new(),
1128 offsets: Indices(Vec::new()),
1129 edges: Vec::new(),
1130 remap: Indices(Vec::new()),
1131 wedge: Indices(Vec::new()),
1132 kind: Vec::new(),
1133 forward: Indices(Vec::new()),
1134 back: Indices(Vec::new()),
1135 p: Vec::new(),
1136 a: Vec::new(),
1137 q: Vec::new(),
1138 aq: Vec::new(),
1139 g: Vec::new(),
1140 vg: Vec::new(),
1141 sparse: Vec::new(),
1142 original: Vec::new(),
1143 clamped: false,
1144 collapses: Vec::new(),
1145 order: Indices(Vec::new()),
1146 cr: Indices(Vec::new()),
1147 locked: Vec::new(),
1148 table: Indices(Vec::new()),
1149 max_degree: 0,
1150 ac: 0,
1151 bytes: 0,
1152 }
1153 }
1154 fn new(
1155 n: usize,
1156 m: usize,
1157 ac: usize,
1158 ws: &mut Workspace,
1159 mut output: usize,
1160 solve: bool,
1161 original: &mut Vec<u32>,
1162 ) -> Result<Self, Error> {
1163 let na = n.checked_mul(ac).ok_or(Error::SizeOverflow)?;
1164 let buckets = n
1165 .checked_add(n / 4)
1166 .ok_or(Error::SizeOverflow)?
1167 .checked_next_power_of_two()
1168 .ok_or(Error::SizeOverflow)?;
1169 let mut state = ws.simplify.take().unwrap_or_else(Self::empty);
1170 let mut unused = Self::empty();
1173 if na == 0 {
1174 unused.a = core::mem::take(&mut state.a);
1175 unused.g = core::mem::take(&mut state.g);
1176 }
1177 if ac == 0 {
1178 unused.aq = core::mem::take(&mut state.aq);
1179 }
1180 if !solve || ac == 0 {
1181 unused.vg = core::mem::take(&mut state.vg);
1182 }
1183 unused.sparse = core::mem::take(&mut state.sparse);
1184 unused.original = core::mem::take(&mut state.original);
1185 if unused.capacity_bytes()? != 0 {
1186 ws.has_retained = true;
1187 ws.simplify = Some(unused);
1188 }
1189 let projected = (|| {
1195 let mut projected = output
1196 .checked_add(state.capacity_bytes()?)
1197 .ok_or(Error::SizeOverflow)?;
1198 for (capacity, needed, size) in [
1199 (state.offsets.0.capacity(), n + 1, 4),
1200 (state.edges.capacity(), m, core::mem::size_of::<Edge>()),
1201 (state.remap.0.capacity(), n, 4),
1202 (state.wedge.0.capacity(), n, 4),
1203 (state.kind.capacity(), n, 1),
1204 (state.forward.0.capacity(), n, 4),
1205 (state.back.0.capacity(), n, 4),
1206 (state.p.capacity(), n, core::mem::size_of::<V>()),
1207 (state.a.capacity(), na, 4),
1208 (state.q.capacity(), n, core::mem::size_of::<Q>()),
1209 (
1210 state.aq.capacity(),
1211 if ac > 0 { n } else { 0 },
1212 core::mem::size_of::<Q>(),
1213 ),
1214 (state.g.capacity(), na, core::mem::size_of::<G>()),
1215 (state.cr.0.capacity(), n, 4),
1216 (state.locked.capacity(), n, 1),
1217 (state.table.0.capacity(), buckets, 4),
1218 ] {
1219 projected = projected
1220 .checked_add(checked_bytes(needed.saturating_sub(capacity), size)?)
1221 .ok_or(Error::SizeOverflow)?;
1222 }
1223 Ok::<_, Error>(projected)
1224 })();
1225 if projected.is_ok_and(|bytes| bytes > ws.limits().max_bytes) {
1226 let old = checked_bytes(original.capacity(), 4)?;
1227 crate::workspace::shrink(original, true)?;
1228 let released = old - checked_bytes(original.capacity(), 4)?;
1229 output -= released;
1230 if projected.is_ok_and(|bytes| bytes - released > ws.limits().max_bytes) {
1231 state = Self::empty();
1232 }
1233 }
1234 let bytes = output
1235 .checked_add(state.capacity_bytes()?)
1236 .ok_or(Error::SizeOverflow)?;
1237 let lean = ws.retention() == crate::Retention::Lean;
1238 let mut b = Budget::new(ws, bytes);
1239 b.reuse(&mut state.offsets.0, n + 1)?;
1240 b.reuse(&mut state.edges, m)?;
1241 state.remap.0.clear();
1242 b.reuse_capacity(&mut state.remap.0, n)?;
1243 state.wedge.0.clear();
1244 b.reuse_capacity(&mut state.wedge.0, n)?;
1245 b.reuse(&mut state.kind, n)?;
1246 state.kind.fill(MAN);
1247 b.reuse(&mut state.forward.0, n)?;
1248 state.forward.fill(NONE);
1249 b.reuse(&mut state.back.0, n)?;
1250 state.back.fill(NONE);
1251 state.p.clear();
1252 b.reuse_capacity(&mut state.p, n)?;
1253 b.reuse(&mut state.a, na)?;
1254 if lean {
1255 state.q.clear();
1257 b.reuse(&mut state.q, n)?;
1258 } else {
1259 b.reuse(&mut state.q, n)?;
1260 state.q.fill(Q::default());
1261 }
1262 b.reuse(&mut state.aq, if ac > 0 { n } else { 0 })?;
1263 state.aq.fill(Q::default());
1264 b.reuse(&mut state.g, na)?;
1265 state.g.fill(G::default());
1266 state.vg.clear();
1267 state.sparse.clear();
1268 state.original.clear();
1269 state.collapses.clear();
1270 state.order.0.clear();
1271 b.reuse(&mut state.cr.0, n)?;
1272 b.reuse(&mut state.locked, n)?;
1273 state.locked.fill(false);
1274 b.reuse(&mut state.table.0, buckets)?;
1275 state.table.fill(NONE);
1276 state.ac = ac;
1277 state.vertex_count = n;
1278 state.clamped = false;
1279 state.max_degree = 0;
1280 state.bytes = b.bytes;
1281 Ok(state)
1282 }
1283 fn adjacency<const WELD: bool>(
1284 &mut self,
1285 indices: &[u32],
1286 work: &mut impl Meter,
1287 ) -> Result<(), Error> {
1288 work.add(self.vertex_count)?;
1289 self.offsets.fill(0);
1290 let n = self.vertex_count;
1291 let counters = &mut self.offsets.0[1..][..n];
1292 let remap = &self.remap.0[..if WELD { n } else { 0 }];
1293 let edges = &mut self.edges[..indices.len()];
1294 work.scan(indices.iter().copied(), |i| {
1295 let v = if WELD {
1296 remap[i as usize] as usize
1297 } else {
1298 i as usize
1299 };
1300 counters[v] += 1;
1301 Ok(())
1302 })?;
1303 let mut offset = 0;
1304 let mut max_degree = 0;
1305 for v in counters.iter_mut() {
1306 let count = *v;
1307 *v = offset;
1308 offset += count;
1309 max_degree = max_degree.max(count);
1310 }
1311 self.max_degree = max_degree as usize;
1312 let triangles = indices.as_chunks::<3>().0;
1313 let charged = work.precharge(triangles.len(), 3)?;
1314 for t in triangles {
1315 if !charged {
1316 work.add(3)?;
1317 }
1318 let mut v = [t[0] as usize, t[1] as usize, t[2] as usize];
1319 if WELD {
1320 for x in &mut v {
1321 *x = remap[*x] as usize;
1322 }
1323 }
1324 for e in 0..3 {
1325 let a = v[e];
1326 let offset = &mut counters[a];
1327 edges[*offset as usize] = Edge {
1328 next: v[(e + 1) % 3] as u32,
1329 prev: v[(e + 2) % 3] as u32,
1330 };
1331 *offset += 1;
1332 }
1333 }
1334 Ok(())
1335 }
1336 fn has_edge<const WELD: bool, M: Meter>(
1337 &self,
1338 a: usize,
1339 b: usize,
1340 work: &mut M,
1341 ) -> Result<bool, Error> {
1342 let mut v = a;
1343 loop {
1344 for e in &self.edges[self.offsets.get(v)..self.offsets.get(v + 1)] {
1345 work.add(1)?;
1346 if if WELD {
1347 self.remap.get(e.next as usize) == self.remap.get(b)
1348 } else {
1349 e.next as usize == b
1350 } {
1351 return Ok(true);
1352 }
1353 }
1354 if !WELD {
1355 break;
1356 }
1357 v = self.wedge.get(v);
1358 if v == a {
1359 break;
1360 }
1361 }
1362 Ok(false)
1363 }
1364 fn position_remap(
1365 &mut self,
1366 p: Positions<'_>,
1367 work: &mut Work,
1368 ) -> Result<([f32; 3], [f32; 3]), Error> {
1369 if let Some((values, mapping)) = p.packed_source() {
1370 if let Some(mapping) = mapping {
1371 self.position_remap_kernel::<false>(
1372 mapping.len(),
1373 |i| Ok(values[mapping[i] as usize]),
1374 work,
1375 )
1376 } else {
1377 self.position_remap_kernel::<false>(values.len(), |i| Ok(values[i]), work)
1378 }
1379 } else if let Some(mut records) = p.scale_full_records() {
1380 self.position_remap_kernel::<true>(
1381 p.len(),
1382 |_| Ok(records.next().expect("validated position count")),
1383 work,
1384 )
1385 } else {
1386 self.position_remap_kernel::<true>(p.len(), |i| p.at(i), work)
1387 }
1388 }
1389 fn position_remap_kernel<const CACHE_POSITIONS: bool>(
1390 &mut self,
1391 count: usize,
1392 mut read: impl FnMut(usize) -> Result<[f32; 3], Error>,
1393 work: &mut Work,
1394 ) -> Result<([f32; 3], [f32; 3]), Error> {
1395 let mask = self.table.len() - 1;
1396 self.remap.0.resize(count, 0);
1400 self.wedge.0.resize(count, 0);
1401 if CACHE_POSITIONS {
1402 self.p.resize(count, V::default());
1403 }
1404 let remap = &mut self.remap.0[..count];
1405 let wedge = &mut self.wedge.0[..count];
1406 let positions = &mut self.p[..if CACHE_POSITIONS { count } else { 0 }];
1407 let table = &mut self.table.0[..];
1408 let mut lo = [f32::MAX; 3];
1409 let mut hi = [-f32::MAX; 3];
1410 for start in (0..count).step_by(64) {
1413 let end = count.min(start.saturating_add(64));
1414 let bound = (end - start).checked_mul(mask + 2);
1415 metered!(work, bound, |work| (|| {
1416 for i in start..end {
1417 work.add(1)?;
1418 let v = read(i)?;
1419 for j in 0..3 {
1423 if lo[j] > v[j] {
1424 lo[j] = v[j];
1425 }
1426 if hi[j] < v[j] {
1427 hi[j] = v[j];
1428 }
1429 }
1430 if CACHE_POSITIONS {
1436 positions[i] = V::from(v);
1437 }
1438 let mut bits = v.map(|v| match v.to_bits() {
1439 0x8000_0000 => 0,
1440 bits => bits,
1441 });
1442 for x in &mut bits {
1443 *x ^= *x >> 17;
1444 }
1445 let hash = bits[0].wrapping_mul(73856093)
1446 ^ bits[1].wrapping_mul(19349663)
1447 ^ bits[2].wrapping_mul(83492791);
1448 let mut bucket = hash as usize & mask;
1449 for probe in 0..=mask {
1450 work.add(1)?;
1451 let j = table[bucket] as usize;
1452 if j == NONE {
1453 table[bucket] = i as u32;
1454 break;
1455 }
1456 let candidate = if CACHE_POSITIONS {
1457 let p = positions[j];
1458 [p.x, p.y, p.z]
1459 } else {
1460 read(j)?
1461 };
1462 if candidate == v {
1463 break;
1464 }
1465 bucket = (bucket + probe + 1) & mask;
1466 }
1467 remap[i] = table[bucket];
1468 wedge[i] = i as u32;
1469 }
1470 Ok(())
1471 })())?;
1472 }
1473 self.bytes -= self.table.0.capacity() * core::mem::size_of::<u32>();
1474 self.table.0 = Vec::new();
1475 let wedge = &mut self.wedge.0[..count];
1476 work.scan(self.remap.0[..count].iter().enumerate(), |(i, &r)| {
1477 let r = r as usize;
1478 if r != i {
1479 wedge[i] = wedge[r];
1480 wedge[r] = i as u32;
1481 }
1482 Ok(())
1483 })?;
1484 Ok((lo, hi))
1485 }
1486 fn classify_work(&self, edges: usize, options: SimplifyOptions) -> Option<usize> {
1490 if options.contains(SimplifyOptions::PERMISSIVE) {
1491 return None;
1492 }
1493 edges
1494 .checked_mul(self.max_degree.checked_add(1)?)?
1495 .checked_add(self.vertex_count.checked_mul(5)?)
1496 }
1497 fn classify<M: Meter>(
1498 &mut self,
1499 flags: Option<&[VertexFlags]>,
1500 options: SimplifyOptions,
1501 work: &mut M,
1502 ) -> Result<(), Error> {
1503 let n = self.vertex_count;
1504 let offsets = &self.offsets.0[..n + 1];
1507 let edges = &self.edges[..];
1508 let forward = &mut self.forward.0[..n];
1509 let back = &mut self.back.0[..n];
1510 for (i, range) in offsets.windows(2).enumerate() {
1511 work.add(1)?;
1512 for edge in &edges[range[0] as usize..range[1] as usize] {
1513 work.add(1)?;
1514 let t = edge.next as usize;
1515 if t == i {
1516 forward[i] = i as u32;
1517 back[i] = i as u32;
1518 } else {
1519 let mut opposite = false;
1520 for edge in &edges[offsets[t] as usize..offsets[t + 1] as usize] {
1521 work.add(1)?;
1522 if edge.next as usize == i {
1523 opposite = true;
1524 break;
1525 }
1526 }
1527 if !opposite {
1528 back[t] = if back[t] as usize == NONE { i } else { t } as u32;
1529 forward[i] = if forward[i] as usize == NONE { t } else { i } as u32;
1530 }
1531 }
1532 }
1533 }
1534 let remap = &self.remap.0[..n];
1535 let wedge = &self.wedge.0[..n];
1536 let kind = &mut self.kind[..n];
1537 for i in 0..n {
1538 work.add(1)?;
1539 kind[i] = if remap[i] as usize != i {
1540 kind[remap[i] as usize]
1541 } else if wedge[i] as usize == i {
1542 let a = back[i] as usize;
1543 let b = forward[i] as usize;
1544 if a == NONE && b == NONE {
1545 MAN
1546 } else if a != NONE && b != NONE && remap[a] == remap[b] && a != i {
1547 SEAM
1548 } else if a != i && b != i {
1549 BORDER
1550 } else {
1551 LOCKED
1552 }
1553 } else if wedge[wedge[i] as usize] as usize == i {
1554 let w = wedge[i] as usize;
1555 let a = back[i] as usize;
1556 let b = forward[i] as usize;
1557 let c = back[w] as usize;
1558 let d = forward[w] as usize;
1559 if a != NONE
1560 && a != i
1561 && b != NONE
1562 && b != i
1563 && c != NONE
1564 && c != w
1565 && d != NONE
1566 && d != w
1567 && remap[a] == remap[d]
1568 && remap[b] == remap[c]
1569 && remap[a] != remap[b]
1570 {
1571 SEAM
1572 } else {
1573 LOCKED
1574 }
1575 } else {
1576 LOCKED
1577 };
1578 }
1579 if options.contains(SimplifyOptions::PERMISSIVE) {
1580 for i in 0..n {
1581 work.add(1)?;
1582 if self.kind[i] != SEAM && self.kind[i] != LOCKED {
1583 continue;
1584 }
1585 if self.remap.get(i) != i {
1586 self.kind[i] = self.kind[self.remap.get(i)];
1587 continue;
1588 }
1589 let mut protect = false;
1590 let mut border = false;
1591 let mut v = i;
1592 loop {
1593 work.add(1)?;
1594 protect |= flag(flags, v, VertexFlags::PROTECT);
1595 for j in self.offsets.get(v)..self.offsets.get(v + 1) {
1596 work.add(1)?;
1597 border |=
1598 !self.has_edge::<true, M>(self.edges[j].next as usize, v, work)?;
1599 }
1600 v = self.wedge.get(v);
1601 if v == i {
1602 break;
1603 }
1604 }
1605 if !protect {
1606 self.kind[i] = if border { FRINGE } else { COMPLEX };
1607 }
1608 }
1609 }
1610 if let Some(flags) = flags {
1611 for (i, &f) in flags.iter().enumerate() {
1612 work.add(1)?;
1613 if f.contains(VertexFlags::LOCK) {
1614 self.kind[self.remap.get(i)] = LOCKED;
1615 }
1616 }
1617 for i in 0..n {
1618 work.add(1)?;
1619 if self.kind[self.remap.get(i)] == LOCKED {
1620 self.kind[i] = LOCKED;
1621 }
1622 }
1623 }
1624 if options.contains(SimplifyOptions::LOCK_BORDER) {
1625 for k in &mut self.kind {
1626 work.add(1)?;
1627 if *k == BORDER || *k == FRINGE {
1628 *k = LOCKED;
1629 }
1630 }
1631 }
1632 Ok(())
1633 }
1634}
1635fn flag(flags: Option<&[VertexFlags]>, i: usize, f: VertexFlags) -> bool {
1636 flags.is_some_and(|flags| flags[i].contains(f))
1637}
1638#[inline(always)]
1639fn attribute_gradient(q: &mut Q, values: [f32; 3], p0: V, basis: [V; 2], w: f32) -> G {
1640 let [a0, a1, a2] = values;
1641 let gx = basis[0].x * (a1 - a0) + basis[1].x * (a2 - a0);
1642 let gy = basis[0].y * (a1 - a0) + basis[1].y * (a2 - a0);
1643 let gz = basis[0].z * (a1 - a0) + basis[1].z * (a2 - a0);
1644 let gw = a0 - p0.x * gx - p0.y * gy - p0.z * gz;
1645 q.a00 += w * (gx * gx);
1646 q.a11 += w * (gy * gy);
1647 q.a22 += w * (gz * gz);
1648 q.a10 += w * (gy * gx);
1649 q.a20 += w * (gz * gx);
1650 q.a21 += w * (gz * gy);
1651 q.b0 += w * (gx * gw);
1652 q.b1 += w * (gy * gw);
1653 q.b2 += w * (gz * gw);
1654 q.c += w * (gw * gw);
1655 G {
1656 x: w * gx,
1657 y: w * gy,
1658 z: w * gz,
1659 w: w * gw,
1660 }
1661}
1662fn record_triplet<T>(
1663 records: &mut [T],
1664 width: usize,
1665 indices: [usize; 3],
1666) -> Option<[&mut [T]; 3]> {
1667 let [a, b, c] = indices;
1668 if a == b || a == c || b == c {
1669 return None;
1670 }
1671 records
1672 .get_disjoint_mut([
1673 a * width..(a + 1) * width,
1674 b * width..(b + 1) * width,
1675 c * width..(c + 1) * width,
1676 ])
1677 .ok()
1678}
1679impl State {
1680 fn attribute_quadric(&mut self, t: [usize; 3]) -> Q {
1681 let [i0, i1, i2] = t;
1682 let p0 = self.p[i0];
1683 let v0 = self.p[i1].sub(p0);
1684 let v1 = self.p[i2].sub(p0);
1685 let normal = v0.cross(v1);
1686 let w = self.sqrt_cache.sqrt(normal.dot(normal)) * 0.5;
1687 let d00 = v0.dot(v0);
1688 let d01 = v0.dot(v1);
1689 let d11 = v1.dot(v1);
1690 let denom = d00 * d11 - d01 * d01;
1691 let dr = if denom == 0.0 { 0.0 } else { 1.0 / denom };
1692 let gx1 = (d11 * v0.x - d01 * v1.x) * dr;
1693 let gx2 = (d00 * v1.x - d01 * v0.x) * dr;
1694 let gy1 = (d11 * v0.y - d01 * v1.y) * dr;
1695 let gy2 = (d00 * v1.y - d01 * v0.y) * dr;
1696 let gz1 = (d11 * v0.z - d01 * v1.z) * dr;
1697 let gz2 = (d00 * v1.z - d01 * v0.z) * dr;
1698 let mut q = Q { w, ..Q::default() };
1699 let attributes0 = &self.a[i0 * self.ac..][..self.ac];
1700 let attributes1 = &self.a[i1 * self.ac..][..self.ac];
1701 let attributes2 = &self.a[i2 * self.ac..][..self.ac];
1702 let basis = [
1703 V {
1704 x: gx1,
1705 y: gy1,
1706 z: gz1,
1707 },
1708 V {
1709 x: gx2,
1710 y: gy2,
1711 z: gz2,
1712 },
1713 ];
1714 if let Some([g0, g1, g2]) = record_triplet(&mut self.g, self.ac, t) {
1715 for (((&a0, &a1), &a2), ((g0, g1), g2)) in attributes0
1716 .iter()
1717 .zip(attributes1)
1718 .zip(attributes2)
1719 .zip(g0.iter_mut().zip(g1).zip(g2))
1720 {
1721 let g = attribute_gradient(&mut q, [a0, a1, a2], p0, basis, w);
1722 g0.add(g);
1723 g1.add(g);
1724 g2.add(g);
1725 }
1726 } else {
1727 for (k, ((&a0, &a1), &a2)) in attributes0
1728 .iter()
1729 .zip(attributes1)
1730 .zip(attributes2)
1731 .enumerate()
1732 {
1733 let g = attribute_gradient(&mut q, [a0, a1, a2], p0, basis, w);
1734 for i in t {
1735 self.g[i * self.ac + k].add(g);
1736 }
1737 }
1738 }
1739 q
1740 }
1741 fn quadrics<M: Meter>(
1742 &mut self,
1743 indices: &[u32],
1744 flags: Option<&[VertexFlags]>,
1745 options: SimplifyOptions,
1746 work: &mut M,
1747 ) -> Result<(), Error> {
1748 let n = self.p.len();
1749 let p = &self.p[..n];
1750 let remap = &self.remap.0[..n];
1751 let qv = &mut self.q[..n];
1752 let kind = &self.kind[..n];
1753 let forward = &self.forward.0[..n];
1754 let back = &self.back.0[..n];
1755 let triangles = indices.as_chunks::<3>().0;
1756 let charged = work.precharge(triangles.len(), 3)?;
1757 for t in triangles {
1758 if !charged {
1759 work.add(3)?;
1760 }
1761 let [a, b, c] = [t[0] as usize, t[1] as usize, t[2] as usize];
1762 let mut normal = p[b].sub(p[a]).cross(p[c].sub(p[a]));
1763 let area = normal.normalize(&mut self.sqrt_cache);
1764 let q = Q::plane(normal, -normal.dot(p[a]), self.sqrt_cache.sqrt(area) * 1.0);
1765 for i in [a, b, c] {
1766 qv[remap[i] as usize].add(q);
1767 }
1768 if !self.vg.is_empty() {
1769 let area = area * 0.5;
1771 let g = G {
1772 x: normal.x * area,
1773 y: normal.y * area,
1774 z: normal.z * area,
1775 w: (-p[a].x * normal.x - p[a].y * normal.y - p[a].z * normal.z) * area,
1776 };
1777 for i in [a, b, c] {
1778 self.vg[remap[i] as usize].add(g);
1779 }
1780 }
1781 }
1782 let factor = if options.contains(SimplifyOptions::REGULARIZE_LIGHT) {
1783 1e-2
1784 } else if options.contains(SimplifyOptions::REGULARIZE) {
1785 1e-1
1786 } else {
1787 1e-7
1788 };
1789 work.scan(
1790 qv.iter_mut().zip(p).zip(remap).enumerate(),
1791 |(i, ((q, &position), &r))| {
1792 if r as usize == i {
1793 let w = q.w
1794 * if flag(flags, i, VertexFlags::PRIORITY) {
1795 1.0
1796 } else {
1797 factor
1798 };
1799 q.add(Q::point(position, w));
1800 }
1801 Ok(())
1802 },
1803 )?;
1804 let charged_edges = work.precharge(indices.len(), 1)?;
1805 for t in indices.as_chunks::<3>().0 {
1806 for e in 0..3 {
1807 if !charged_edges {
1808 work.add(1)?;
1809 }
1810 let a = t[e] as usize;
1811 let b = t[(e + 1) % 3] as usize;
1812 let c = t[(e + 2) % 3] as usize;
1813 let k0 = kind[a];
1814 let k1 = kind[b];
1815 if k0 == MAN || k1 == MAN {
1816 continue;
1817 }
1818 if ![BORDER, SEAM, FRINGE].contains(&k0) && ![BORDER, SEAM, FRINGE].contains(&k1) {
1819 continue;
1820 }
1821 if (k0 == BORDER || k0 == SEAM) && forward[a] as usize != b {
1822 continue;
1823 }
1824 if (k1 == BORDER || k1 == SEAM) && back[b] as usize != a {
1825 continue;
1826 }
1827 if (k0 == FRINGE || k1 == FRINGE) && (k0 == COMPLEX || k1 == COMPLEX) {
1828 continue;
1829 }
1830 let w = if k0 == SEAM || k1 == SEAM { 0.5 } else { 10.0 };
1831 let mut q = Q::edge(p[a], p[b], p[c], w, &mut self.sqrt_cache);
1832 let mut qt = Q::triangle(p[a], p[b], p[c], w, &mut self.sqrt_cache);
1833 qt.w = 0.0;
1834 q.add(qt);
1835 qv[remap[a] as usize].add(q);
1836 qv[remap[b] as usize].add(q);
1837 }
1838 }
1839 if self.ac > 0 {
1840 let units = 3 + self.ac * 3;
1841 let charged = work.precharge(triangles.len(), units)?;
1842 for t in triangles {
1843 if !charged {
1844 work.add(units)?;
1845 }
1846 let t = [t[0] as usize, t[1] as usize, t[2] as usize];
1847 let q = self.attribute_quadric(t);
1848 for i in t {
1849 self.aq[i].add(q);
1850 }
1851 }
1852 }
1853 if options.bits() & 128 != 0 {
1854 extra::fold_quadrics(self, work)?;
1855 }
1856 for q in &mut self.q {
1861 if !q.finite() {
1862 return Err(Error::NumericalFailure);
1863 }
1864 q.cache_inverse_weight();
1865 }
1866 if self.aq.iter().any(|q| !q.finite())
1867 || self.g.iter().any(|g| {
1868 ![g.x, g.y, g.z, g.w]
1869 .iter()
1870 .fold(true, |finite, x| finite & x.is_finite())
1871 })
1872 {
1873 return Err(Error::NumericalFailure);
1874 }
1875 Ok(())
1876 }
1877 fn pick<M: Meter>(
1879 &mut self,
1880 indices: &[u32],
1881 capacity: usize,
1882 work: &mut M,
1883 ) -> Result<usize, Error> {
1884 let mut count = 0;
1885 let n = self.vertex_count;
1889 let remap = &self.remap.0[..n];
1890 let kind = &self.kind[..n];
1891 let forward = &self.forward.0[..n];
1892 let back = &self.back.0[..n];
1893 let collapses = &mut self.collapses;
1894 collapses.clear();
1895 for t in indices.as_chunks::<3>().0 {
1896 if count + 3 > capacity {
1897 break;
1898 }
1899 for e in 0..3 {
1900 work.add(1)?;
1901 let a = t[e] as usize;
1902 let b = t[(e + 1) % 3] as usize;
1903 let ra = remap[a];
1904 let rb = remap[b];
1905 if ra == rb {
1906 continue;
1907 }
1908 let rule = PICK[pair(kind[a], kind[b])];
1909 if rule & PICK_ANY == 0 {
1910 continue;
1911 }
1912 if rule & PICK_OPPOSITE != 0 && rb > ra {
1913 continue;
1914 }
1915 if rule & PICK_CHECK_FORWARD != 0 && forward[a] as usize != b {
1916 continue;
1917 }
1918 if rule & PICK_CHECK_BACK != 0 && back[b] as usize != a {
1919 continue;
1920 }
1921 collapses.push(if rule & PICK_BOTH != 0 {
1922 Collapse {
1923 a: a as u32,
1924 b: b as u32,
1925 error: f32::from_bits(1),
1926 }
1927 } else if rule & PICK_FORWARD != 0 {
1928 Collapse {
1929 a: a as u32,
1930 b: b as u32,
1931 ..Collapse::default()
1932 }
1933 } else {
1934 Collapse {
1935 a: b as u32,
1936 b: a as u32,
1937 ..Collapse::default()
1938 }
1939 });
1940 count += 1;
1941 }
1942 }
1943 Ok(count)
1944 }
1945 fn complex_target(&self, v: usize, t: usize) -> usize {
1946 let r = self.remap.get(t);
1947 if self.forward.get(v) != NONE && self.remap.get(self.forward.get(v)) == r {
1948 self.forward.get(v)
1949 } else if self.back.get(v) != NONE && self.remap.get(self.back.get(v)) == r {
1950 self.back.get(v)
1951 } else {
1952 t
1953 }
1954 }
1955 fn seam_target(&self, a: usize, b: usize) -> (usize, usize) {
1956 let s0 = self.wedge.get(a);
1957 let s1 = if self.forward.get(a) == b {
1958 self.back.get(s0)
1959 } else {
1960 self.forward.get(s0)
1961 };
1962 (s0, if s1 != NONE { s1 } else { self.wedge.get(b) })
1963 }
1964 fn rank(&mut self, count: usize, work: &mut Work) -> Result<(), Error> {
1965 if self.ac == 0 {
1966 let n = self.p.len();
1969 let p = &self.p[..n];
1970 let q = &self.q[..n];
1971 let remap = &self.remap.0[..n];
1972 #[inline(always)]
1973 fn rank_one(c: &mut Collapse, p: &[V], q: &[Q], remap: &[u32]) -> Result<(), Error> {
1974 let a = c.a as usize;
1975 let b = c.b as usize;
1976 let bidirectional = c.error.to_bits() != 0;
1977 let ei = q[remap[a] as usize].error(p[b]);
1978 let ej = if bidirectional {
1979 q[remap[b] as usize].error(p[a])
1980 } else {
1981 f32::MAX
1982 };
1983 if !(ei.is_finite() & ej.is_finite()) {
1984 return Err(Error::NumericalFailure);
1985 }
1986 if bidirectional && ej < ei {
1987 core::mem::swap(&mut c.a, &mut c.b);
1988 }
1989 c.error = if ej < ei { ej } else { ei };
1990 Ok(())
1991 }
1992 let values = &mut self.collapses[..count];
1993 return if work.covers(count)? {
1994 for (i, c) in values.iter_mut().enumerate() {
1995 if let Err(error) = rank_one(c, p, q, remap) {
1996 work.add(i + 1)?;
1997 return Err(error);
1998 }
1999 }
2000 work.add(count)
2001 } else {
2002 for c in values {
2003 work.add(1)?;
2004 rank_one(c, p, q, remap)?;
2005 }
2006 Ok(())
2007 };
2008 }
2009 let per_candidate = self
2012 .vertex_count
2013 .checked_add(1)
2014 .and_then(|n| self.ac.checked_mul(2)?.checked_mul(n))
2015 .and_then(|n| n.checked_add(1));
2016 for start in (0..count).step_by(64) {
2017 let end = count.min(start.saturating_add(64));
2018 let bound = per_candidate.and_then(|n| n.checked_mul(end - start));
2019 metered!(work, bound, |w| self.rank_attributes(start..end, w))?;
2020 }
2021 Ok(())
2022 }
2023 fn rank_attributes<M: Meter>(
2024 &mut self,
2025 range: core::ops::Range<usize>,
2026 work: &mut M,
2027 ) -> Result<(), Error> {
2028 for i in range {
2029 work.add(1)?;
2030 let c = self.collapses[i];
2031 let a = c.a as usize;
2032 let b = c.b as usize;
2033 let mut ei = self.q[self.remap.get(a)].error(self.p[b]);
2034 let mut ej = if c.error.to_bits() != 0 {
2035 self.q[self.remap.get(b)].error(self.p[a])
2036 } else {
2037 f32::MAX
2038 };
2039 if self.ac > 0 {
2040 work.add(self.ac * 2)?;
2041 ei += self.attribute_error(a, b);
2042 ej += if c.error.to_bits() != 0 {
2043 self.attribute_error(b, a)
2044 } else {
2045 0.0
2046 };
2047 if self.kind[a] == SEAM {
2048 work.add(self.ac * 2)?;
2049 let (s0, s1) = self.seam_target(a, b);
2050 ei += self.attribute_error(s0, s1);
2051 ej += if c.error.to_bits() != 0 {
2052 self.attribute_error(s1, s0)
2053 } else {
2054 0.0
2055 };
2056 } else {
2057 if self.kind[a] == COMPLEX || self.kind[a] == FRINGE {
2058 let mut v = self.wedge.get(a);
2059 while v != a {
2060 work.add(self.ac)?;
2061 ei += self.attribute_error(v, self.complex_target(v, b));
2062 v = self.wedge.get(v);
2063 }
2064 }
2065 if (self.kind[b] == COMPLEX || self.kind[b] == FRINGE)
2066 && (c.error.to_bits() != 0)
2067 {
2068 let mut v = self.wedge.get(b);
2069 while v != b {
2070 work.add(self.ac)?;
2071 ej += self.attribute_error(v, self.complex_target(v, a));
2072 v = self.wedge.get(v);
2073 }
2074 }
2075 }
2076 }
2077 if !(ei.is_finite() & ej.is_finite()) {
2078 return Err(Error::NumericalFailure);
2079 }
2080 let rev = (c.error.to_bits() != 0) && ej < ei;
2081 self.collapses[i] = Collapse {
2082 a: (if rev { b } else { a }) as u32,
2083 b: (if rev { a } else { b }) as u32,
2084 error: if ej < ei { ej } else { ei },
2085 };
2086 }
2087 Ok(())
2088 }
2089 #[inline(always)]
2090 fn attribute_error(&self, source: usize, target: usize) -> f32 {
2091 let v = self.p[target];
2092 let q = self.aq[source];
2093 let mut r = q.eval(v);
2094 let attributes = &self.a[target * self.ac..][..self.ac];
2095 let gradients = &self.g[source * self.ac..][..self.ac];
2096 let term = |a: f32, g: G| {
2097 let g = v.x * g.x + v.y * g.y + v.z * g.z + g.w;
2098 a * (a * q.w - 2.0 * g)
2099 };
2100 let (a4, at) = attributes.as_chunks::<4>();
2101 let (g4, gt) = gradients.as_chunks::<4>();
2102 for (a, g) in a4.iter().zip(g4) {
2103 let terms = [
2106 term(a[0], g[0]),
2107 term(a[1], g[1]),
2108 term(a[2], g[2]),
2109 term(a[3], g[3]),
2110 ];
2111 for t in terms {
2112 r += t;
2113 }
2114 }
2115 for (&a, &g) in at.iter().zip(gt) {
2116 r += term(a, g);
2117 }
2118 let e = r.abs();
2119 if self.clamped && e >= q.w {
2120 q.w
2121 } else {
2122 e
2123 }
2124 }
2125 fn sort(&mut self, count: usize, work: &mut Work) -> Result<(), Error> {
2126 let mut h = [0u32; 2560];
2129 let collapses = &self.collapses[..count];
2130 work.scan(collapses.iter(), |c| {
2131 h[sort_key(c.error)] += 1;
2132 Ok(())
2133 })?;
2134 let mut sum = 0;
2135 for v in &mut h {
2136 let n = *v;
2137 *v = sum as u32;
2138 sum += n as usize;
2139 }
2140 let order = &mut self.order.0[..count];
2141 work.scan(collapses.iter().enumerate(), |(i, c)| {
2142 let k = sort_key(c.error);
2143 order[h[k] as usize] = i as u32;
2144 h[k] += 1;
2145 Ok(())
2146 })?;
2147 Ok(())
2148 }
2149 fn flips<M: Meter>(&mut self, a: usize, b: usize, work: &mut M) -> Result<bool, Error> {
2150 for e in &self.edges[self.offsets.get(a)..self.offsets.get(a + 1)] {
2151 work.add(1)?;
2152 let x = self.cr.get(e.next as usize);
2153 let y = self.cr.get(e.prev as usize);
2154 if x == b || y == b || x == y {
2155 continue;
2156 }
2157 let pa = self.p[x];
2158 let eb = self.p[y].sub(pa);
2159 let ec = self.p[a].sub(pa);
2160 let ed = self.p[b].sub(pa);
2161 let nbc = eb.cross(ec);
2162 let nbd = eb.cross(ed);
2163 if nbc.dot(nbd) <= 0.25 * self.sqrt_cache.sqrt(nbc.dot(nbc) * nbd.dot(nbd)) {
2164 return Ok(true);
2165 }
2166 }
2167 Ok(false)
2168 }
2169 fn perform_work(&self, count: usize, options: SimplifyOptions) -> Option<usize> {
2172 if options.contains(SimplifyOptions::PERMISSIVE) {
2173 return None;
2174 }
2175 count
2176 .checked_mul(self.max_degree.checked_add(1)?)?
2177 .checked_add(self.p.len())
2178 }
2179 fn perform<M: Meter>(
2180 &mut self,
2181 count: usize,
2182 goal: usize,
2183 limit: f32,
2184 error: &mut f32,
2185 work: &mut M,
2186 ) -> Result<usize, Error> {
2187 let n = self.p.len();
2188 work.scan(
2189 self.cr.0[..n]
2190 .iter_mut()
2191 .zip(&mut self.locked[..n])
2192 .enumerate(),
2193 |(i, (remap, locked))| {
2194 *remap = i as u32;
2195 *locked = false;
2196 Ok(())
2197 },
2198 )?;
2199 let mut edges = 0;
2200 let mut triangles = 0;
2201 let mut edge_goal = goal / 2;
2202 for i in 0..count {
2203 work.add(1)?;
2204 let c = self.collapses[self.order.get(i)];
2205 if c.error > limit || triangles >= goal {
2206 break;
2207 }
2208 let error_goal = if edge_goal < count {
2209 1.5 * self.collapses[self.order.get(edge_goal)].error
2210 } else {
2211 f32::MAX
2212 };
2213 if c.error > error_goal && c.error > *error && triangles > goal / 6 {
2214 break;
2215 }
2216 let a = c.a as usize;
2217 let b = c.b as usize;
2218 let r0 = self.remap.get(a);
2219 let r1 = self.remap.get(b);
2220 let kind = self.kind[a];
2221 if self.locked[r0] || self.locked[r1] {
2222 continue;
2223 }
2224 if self.flips(r0, r1, work)? {
2225 edge_goal += 1;
2226 continue;
2227 }
2228 self.cr.set(a, b);
2229 if kind == COMPLEX || kind == FRINGE {
2230 let mut v = self.wedge.get(a);
2231 while v != a {
2232 work.add(1)?;
2233 self.cr.set(v, self.complex_target(v, b));
2234 v = self.wedge.get(v);
2235 }
2236 } else if kind == SEAM {
2237 let (s0, s1) = self.seam_target(a, b);
2238 self.cr.set(s0, s1);
2239 }
2240 self.locked[r0] = true;
2241 self.locked[r1] = true;
2242 triangles += if kind == BORDER { 1 } else { 2 };
2243 edges += 1;
2244 if *error < c.error {
2245 *error = c.error;
2246 }
2247 }
2248 Ok(edges)
2249 }
2250 fn update<M: Meter>(&mut self, vertex_error: &mut f32, work: &mut M) -> Result<(), Error> {
2251 let n = self.p.len();
2252 let cr = &self.cr.0[..n];
2253 let remap = &self.remap.0[..n];
2254 if self.ac == 0 && self.vg.is_empty() {
2255 let quadrics = &mut self.q[..n];
2258 for (i, &target) in cr.iter().enumerate() {
2259 work.add(1)?;
2260 let t = target as usize;
2261 if t == i {
2262 continue;
2263 }
2264 let r0 = remap[i] as usize;
2265 let r1 = remap[t] as usize;
2266 if i == r0 {
2267 let q = quadrics[r0];
2268 let destination = &mut quadrics[r1];
2269 destination.add(q);
2270 if !destination.finite() {
2271 return Err(Error::NumericalFailure);
2272 }
2273 destination.cache_inverse_weight();
2274 }
2275 }
2276 } else {
2277 for i in 0..self.p.len() {
2278 work.add(1)?;
2279 let t = self.cr.get(i);
2280 if t == i {
2281 continue;
2282 }
2283 let r0 = self.remap.get(i);
2284 let r1 = self.remap.get(t);
2285 if i == r0 {
2286 let q = self.q[r0];
2287 self.q[r1].add(q);
2288 if !self.q[r1].finite() {
2289 return Err(Error::NumericalFailure);
2290 }
2291 self.q[r1].cache_inverse_weight();
2292 if !self.vg.is_empty() {
2293 let g = self.vg[r0];
2294 self.vg[r1].add(g);
2295 }
2296 }
2297 if self.ac > 0 {
2298 if i == r0 {
2299 let e = self.q[r0].error(self.p[r1]);
2300 if *vertex_error < e {
2301 *vertex_error = e;
2302 }
2303 }
2304 work.add(self.ac)?;
2305 let q = self.aq[i];
2306 self.aq[t].add(q);
2307 if !self.aq[t].finite() {
2308 return Err(Error::NumericalFailure);
2309 }
2310 for k in 0..self.ac {
2311 let g = self.g[i * self.ac + k];
2312 self.g[t * self.ac + k].add(g);
2313 }
2314 }
2315 }
2316 }
2317 for loops in [&mut self.forward.0[..n], &mut self.back.0[..n]] {
2318 for i in 0..n {
2319 work.add(1)?;
2320 let l = loops[i] as usize;
2321 if l != NONE {
2322 let r = cr[l] as usize;
2323 loops[i] = if i == r {
2324 let next = loops[l] as usize;
2325 if next != NONE {
2326 cr[next]
2327 } else {
2328 NONE as u32
2329 }
2330 } else {
2331 r as u32
2332 };
2333 }
2334 }
2335 }
2336 Ok(())
2337 }
2338}
2339fn sort_key(error: f32) -> usize {
2340 ((error.to_bits() << 1) >> 20).min(2559) as usize
2341}
2342#[allow(clippy::too_many_arguments)]
2343fn run(
2344 out: &mut [u32],
2345 indices: &[u32],
2346 positions: Positions<'_>,
2347 attributes: Option<Attributes<'_>>,
2348 weights: &[f32],
2349 flags: Option<&[VertexFlags]>,
2350 settings: SimplifySettings,
2351 ws: &mut Workspace,
2352 work: &mut Work,
2353 output: usize,
2354) -> Result<SimplifyResult, Error> {
2355 let (result, state) = run_state(
2356 out,
2357 Input::borrowed(indices),
2358 positions,
2359 attributes,
2360 weights,
2361 flags,
2362 settings,
2363 ws,
2364 work,
2365 output,
2366 false,
2367 )?;
2368 state.retain(ws);
2369 Ok(result)
2370}
2371#[inline(always)]
2372fn normalize_attribute_row<M: Meter>(
2373 destination: &mut [f32],
2374 source: Attributes<'_>,
2375 vertex: usize,
2376 weights: &[f32],
2377 work: &mut M,
2378) -> Result<(), Error> {
2379 let mut write = 0;
2380 if let Some(values) = source.float_record(vertex) {
2381 work.scan(values.iter().zip(weights), |(&value, &weight)| {
2382 if weight > 0.0 {
2383 let value = value * weight;
2384 if !value.is_finite() {
2385 return Err(Error::NumericalFailure);
2386 }
2387 destination[write] = value;
2388 write += 1;
2389 }
2390 Ok(())
2391 })?;
2392 } else {
2393 for (component, &weight) in weights.iter().enumerate() {
2394 work.add(1)?;
2395 if weight > 0.0 {
2396 let value = source.get(vertex, component).ok_or(Error::InvalidLayout)? * weight;
2397 if !value.is_finite() {
2398 return Err(Error::NumericalFailure);
2399 }
2400 destination[write] = value;
2401 write += 1;
2402 }
2403 }
2404 }
2405 Ok(())
2406}
2407
2408#[allow(clippy::too_many_arguments)]
2409fn run_state(
2410 out: &mut [u32],
2411 mut input: Input<'_>,
2412 positions: Positions<'_>,
2413 attributes: Option<Attributes<'_>>,
2414 weights: &[f32],
2415 flags: Option<&[VertexFlags]>,
2416 settings: SimplifySettings,
2417 ws: &mut Workspace,
2418 work: &mut Work,
2419 output: usize,
2420 solve: bool,
2421) -> Result<(SimplifyResult, State), Error> {
2422 if settings.options.contains(SimplifyOptions::SPARSE) {
2423 return extra::sparse_run(
2424 out, input, positions, attributes, weights, flags, settings, ws, work, output, solve,
2425 );
2426 }
2427 let n = positions.len();
2428 let m = input.as_slice().len();
2429 let ac = weights.iter().filter(|&&w| w > 0.0).count();
2430 let mut s = State::new(n, m, ac, ws, output, solve, &mut input.original)?;
2431 s.clamped = settings.options.bits() & 256 != 0;
2432 if solve && ac > 0 {
2433 let requested = checked_bytes(n.saturating_sub(s.vg.capacity()), core::mem::size_of::<G>())
2434 .and_then(|added| s.bytes.checked_add(added).ok_or(Error::SizeOverflow));
2435 s.reclaim_for(ws, requested, &mut input.original)?;
2436 let mut b = Budget::new(ws, s.bytes);
2437 b.reuse(&mut s.vg, n)?;
2438 s.vg.fill(G::default());
2439 s.bytes = b.bytes;
2440 }
2441 metered!(work, m.checked_mul(2).and_then(|v| v.checked_add(n)), |w| s
2443 .adjacency::<false>(input.as_slice(), w))?;
2444 let (lo, hi) = s.position_remap(positions, work)?;
2445 metered!(work, s.classify_work(m, settings.options), |w| s.classify(
2446 flags,
2447 settings.options,
2448 w
2449 ))?;
2450 work.add(n)?;
2451 let mut extent = 0.0;
2454 if n != 0 {
2455 for j in 0..3 {
2456 let d = hi[j] - lo[j];
2457 if d >= extent {
2458 extent = d;
2459 }
2460 }
2461 }
2462 if !extent.is_finite() {
2463 return Err(Error::NumericalFailure);
2464 }
2465 let scale = if extent == 0.0 { 0.0 } else { 1.0 / extent };
2466 let finite_scale = scale.is_finite();
2471 let cached_positions = s.p.len() == n;
2472 if !cached_positions {
2473 s.p.resize(n, V::default());
2474 }
2475 let normalize_work = weights.len().checked_add(1).and_then(|v| n.checked_mul(v));
2477 metered!(work, normalize_work, |work| (|| {
2478 for (i, destination) in s.p.iter_mut().enumerate() {
2479 work.add(1)?;
2480 let p = if cached_positions {
2481 let p = *destination;
2482 [p.x, p.y, p.z]
2483 } else {
2484 positions.at(i)?
2485 };
2486 let normalized = V {
2487 x: (p[0] - lo[0]) * scale,
2488 y: (p[1] - lo[1]) * scale,
2489 z: (p[2] - lo[2]) * scale,
2490 };
2491 *destination = normalized;
2492 if !finite_scale
2493 && ![destination.x, destination.y, destination.z]
2494 .iter()
2495 .fold(true, |finite, x| finite & x.is_finite())
2496 {
2497 return Err(Error::NumericalFailure);
2498 }
2499 if let Some(a) = attributes {
2500 normalize_attribute_row(&mut s.a[i * ac..(i + 1) * ac], a, i, weights, work)?;
2501 }
2502 }
2503 Ok(())
2504 })())?;
2505 let (components, component_errors) = if settings.options.contains(SimplifyOptions::PRUNE) {
2506 let requested = checked_bytes(n, 4)
2507 .and_then(|added| s.bytes.checked_add(added).ok_or(Error::SizeOverflow));
2508 s.reclaim_for(ws, requested, &mut input.original)?;
2509 let mut b = crate::budget::Budget::with_bytes(ws, s.bytes);
2510 let (c, nc) = extra::component_ids(&s.remap.0, input.as_slice(), &mut b, work)?;
2511 s.bytes = b.bytes();
2512 let requested = checked_bytes(nc, 16)
2513 .and_then(|added| s.bytes.checked_add(added).ok_or(Error::SizeOverflow));
2514 s.reclaim_for(ws, requested, &mut input.original)?;
2515 let mut b = crate::budget::Budget::with_bytes(ws, s.bytes);
2516 let errors = extra::component_errors(&s.p, &c, nc, &mut b, work)?;
2517 s.bytes = b.bytes();
2518 (c, errors)
2519 } else {
2520 (Vec::new(), Vec::new())
2521 };
2522 let quadric_work = if settings.options.bits() & 128 != 0 {
2525 None
2526 } else {
2527 m.checked_mul(2)
2528 .and_then(|v| v.checked_add(n))
2529 .and_then(|v| {
2530 if ac == 0 {
2531 Some(v)
2532 } else {
2533 ac.checked_add(1)
2534 .and_then(|a| m.checked_mul(a))
2535 .and_then(|a| v.checked_add(a))
2536 }
2537 })
2538 };
2539 metered!(work, quadric_work, |w| s.quadrics(
2540 input.as_slice(),
2541 flags,
2542 settings.options,
2543 w
2544 ))?;
2545 let mut dual = 0;
2546 work.scan(s.kind.iter().zip(s.offsets.0.windows(2)), |(&k, o)| {
2547 if k == MAN || k == SEAM {
2548 dual += o[1] as usize - o[0] as usize;
2549 }
2550 Ok(())
2551 })?;
2552 let capacity = m - dual / 2 + 3;
2553 let requested = (|| {
2554 let order_growth = checked_bytes(capacity.saturating_sub(s.order.0.capacity()), 4)?;
2555 let requested = s
2556 .bytes
2557 .checked_add(checked_bytes(
2558 capacity.saturating_sub(s.collapses.capacity()),
2559 core::mem::size_of::<Collapse>(),
2560 )?)
2561 .and_then(|n| n.checked_add(order_growth))
2562 .ok_or(Error::SizeOverflow)?;
2563 Ok::<_, Error>(requested)
2564 })();
2565 s.reclaim_for(ws, requested, &mut input.original)?;
2566 let lean = ws.retention() == crate::Retention::Lean;
2567 let mut budget = Budget::new(ws, s.bytes);
2568 budget.reuse_capacity(&mut s.collapses, capacity)?;
2569 if lean {
2570 budget.reuse_capacity(&mut s.order.0, capacity)?;
2572 } else {
2573 budget.reuse(&mut s.order.0, capacity)?;
2574 }
2575 let mut count = m;
2576 let mut error = 0.0;
2577 let mut vertex_error = 0.0;
2578 let mut component_next = 0.0;
2579 let error_scale = if settings.options.contains(SimplifyOptions::ERROR_ABSOLUTE) {
2580 extent
2581 } else {
2582 1.0
2583 };
2584 let limit = (settings.target_error * settings.target_error) / (error_scale * error_scale);
2585 work.add(m)?;
2586 out[..m].copy_from_slice(input.as_slice());
2587 while count > settings.target_index_count {
2588 metered!(
2589 work,
2590 count.checked_mul(2).and_then(|v| v.checked_add(n)),
2591 |w| s.adjacency::<true>(&out[..count], w)
2592 )?;
2593 let nc = metered!(work, Some(count), |w| s.pick(&out[..count], capacity, w))?;
2598 if nc == 0 {
2599 break;
2600 }
2601 if lean {
2604 s.order.0.resize(nc, 0);
2605 }
2606 s.rank(nc, work)?;
2607 s.sort(nc, work)?;
2608 let goal = (count - settings.target_index_count) / 3;
2609 let edges = metered!(work, s.perform_work(nc, settings.options), |w| s
2610 .perform(nc, goal, limit, &mut error, w))?;
2611 if edges == 0 {
2612 break;
2613 }
2614 if ac == 0 {
2615 vertex_error = error;
2616 }
2617 let update_work = ac.checked_add(3).and_then(|v| n.checked_mul(v));
2619 metered!(work, update_work, |w| s.update(&mut vertex_error, w))?;
2620 let mut write = 0;
2621 let cr = &s.cr.0[..n];
2622 let remap = &s.remap.0[..n];
2623 metered!(work, Some(count), |w| (|| {
2624 let out = &mut out[..count];
2625 for i in 0..count / 3 {
2626 w.add(3)?;
2627 let [a, b, c] = out.as_chunks::<3>().0[i];
2630 let a = cr[a as usize] as usize;
2631 let b = cr[b as usize] as usize;
2632 let c = cr[c as usize] as usize;
2633 let r0 = remap[a];
2634 let r1 = remap[b];
2635 let r2 = remap[c];
2636 if r0 != r1 && r0 != r2 && r1 != r2 {
2637 out.as_chunks_mut::<3>().0[write] = [a as u32, b as u32, c as u32];
2638 write += 1;
2639 }
2640 }
2641 Ok(())
2642 })())?;
2643 count = write * 3;
2644 if settings.options.contains(SimplifyOptions::PRUNE)
2645 && count > settings.target_index_count
2646 && component_next <= vertex_error
2647 {
2648 (count, component_next) = extra::prune(
2649 out,
2650 count,
2651 &components,
2652 &component_errors,
2653 vertex_error,
2654 work,
2655 )?;
2656 }
2657 }
2658 let mut stale = true;
2659 while settings.options.contains(SimplifyOptions::PRUNE)
2660 && count > settings.target_index_count
2661 && component_next <= limit
2662 {
2663 let cutoff = if component_next * 1.5 < limit {
2664 component_next * 1.5
2665 } else {
2666 limit
2667 };
2668 let mut max_error = 0.0;
2669 for &e in &component_errors {
2670 work.add(1)?;
2671 if e > max_error && e <= cutoff {
2672 max_error = e;
2673 }
2674 }
2675 let (new_count, next) =
2676 extra::prune(out, count, &components, &component_errors, cutoff, work)?;
2677 component_next = next;
2678 if new_count == count && !stale {
2679 break;
2680 }
2681 stale = false;
2682 count = new_count;
2683 if error < max_error {
2684 error = max_error;
2685 }
2686 }
2687 if solve {
2688 extra::solve_state(&mut s, &out[..count], work)?;
2689 }
2690 let error = sqrt(error) * error_scale;
2691 if !error.is_finite() {
2692 return Err(Error::NumericalFailure);
2693 }
2694 s.original = input.original;
2695 Ok((
2696 SimplifyResult {
2697 index_count: count,
2698 error,
2699 },
2700 s,
2701 ))
2702}
2703
2704#[cfg(test)]
2705mod tests {
2706 use super::*;
2707 use crate::Limits;
2708
2709 #[test]
2710 fn preflight_preserves_the_first_reservations_limit_error() {
2711 let vertices = isize::MAX as usize / core::mem::size_of::<Q>() + 1;
2715 let mut ws = Workspace::new(Limits {
2716 max_bytes: 0,
2717 ..Limits::default()
2718 });
2719 assert!(matches!(
2720 State::new(vertices, 0, 0, &mut ws, 0, false, &mut Vec::new()),
2721 Err(Error::LimitExceeded)
2722 ));
2723 }
2724
2725 #[test]
2728 #[ignore = "exhaustive 2^32-pattern backend identity gate"]
2729 fn simplify_sqrt_exhaustive_identity() {
2730 for bits in 0..=u32::MAX {
2731 let value = core::hint::black_box(f32::from_bits(bits));
2732 assert_eq!(
2733 sqrt(value).to_bits(),
2734 crate::math::sqrt(value).to_bits(),
2735 "sqrt operand {bits:08x}"
2736 );
2737 }
2738 }
2739
2740 #[test]
2741 fn repeated_simplify_reuses_arrays_but_releases_the_remapping_hash() {
2742 let p = [[0.0, 0.0, 0.0], [1.0, 0.0, 0.0], [0.0, 1.0, 0.0]];
2743 let settings = SimplifySettings {
2744 target_index_count: 0,
2745 target_error: 0.5,
2746 options: SimplifyOptions::EMPTY,
2747 };
2748 let mut ws = Workspace::default();
2749 let expected = simplify(&[0, 1, 2], Positions::from_packed(&p), settings, &mut ws).unwrap();
2750 let state = ws.simplify.as_ref().unwrap();
2751 assert_eq!(state.table.0.capacity(), 0);
2752 let before = (
2753 state.edges.as_ptr(),
2754 state.q.as_ptr(),
2755 state.collapses.as_ptr(),
2756 state.order.0.as_ptr(),
2757 );
2758 let actual = simplify(&[0, 1, 2], Positions::from_packed(&p), settings, &mut ws).unwrap();
2759 assert_eq!(expected.indices, actual.indices);
2760 assert_eq!(expected.error.to_bits(), actual.error.to_bits());
2761 let state = ws.simplify.as_ref().unwrap();
2762 assert_eq!(state.table.0.capacity(), 0);
2763 assert_eq!(
2764 before,
2765 (
2766 state.edges.as_ptr(),
2767 state.q.as_ptr(),
2768 state.collapses.as_ptr(),
2769 state.order.0.as_ptr()
2770 )
2771 );
2772 }
2773
2774 #[test]
2775 fn prepaid_picker_preserves_every_budget_prefix_and_capacity_stop() {
2776 type PickObservation = (Result<usize, Error>, u64, Vec<(u32, u32, u32)>);
2777 fn run(limit: u64, capacity: usize, prepaid: bool, welded: bool) -> PickObservation {
2778 let indices = [0, 1, 2, 2, 1, 0, 0, 2, 3, 3, 2, 0];
2779 let mut ws = Workspace::new(Limits {
2780 max_bytes: 1 << 20,
2781 max_work: limit,
2782 });
2783 let mut state = State::new(4, 12, 0, &mut ws, 0, false, &mut Vec::new()).unwrap();
2784 state
2785 .remap
2786 .0
2787 .extend(if welded { [0; 4] } else { [0, 1, 2, 3] });
2788 state.collapses.reserve_exact(12);
2789 let mut work = ws.begin();
2790 let result = if prepaid {
2791 (|| {
2792 metered!(&mut work, Some(indices.len()), |w| state
2793 .pick(&indices, capacity, w))
2794 })()
2795 } else {
2796 state.pick(&indices, capacity, &mut work)
2797 };
2798 ws.finish(&work);
2799 let collapses = state
2800 .collapses
2801 .iter()
2802 .map(|c| (c.a, c.b, c.error.to_bits()))
2803 .collect();
2804 (result, ws.usage().work, collapses)
2805 }
2806 for limit in 0..=13 {
2807 for capacity in [0, 2, 3, 6, 12] {
2808 for welded in [false, true] {
2809 assert_eq!(
2810 run(limit, capacity, true, welded),
2811 run(limit, capacity, false, welded)
2812 );
2813 }
2814 }
2815 }
2816 }
2817
2818 #[test]
2819 fn prepaid_phases_match_checked_visits() {
2820 fn phase<M: Meter>(
2823 fail_at: usize,
2824 seen: &mut Vec<usize>,
2825 work: &mut M,
2826 ) -> Result<(), Error> {
2827 for i in 0..5 {
2828 work.add(1)?;
2829 seen.push(i);
2830 if i == fail_at {
2831 return Err(Error::NumericalFailure);
2832 }
2833 }
2834 work.scan(5..7, |i| {
2835 seen.push(i);
2836 if i == fail_at {
2837 return Err(Error::NumericalFailure);
2838 }
2839 Ok(())
2840 })
2841 }
2842 fn run_phase(
2843 limit: u64,
2844 fail_at: usize,
2845 bound: Option<usize>,
2846 ) -> (Result<(), Error>, u64, Vec<usize>) {
2847 let mut ws = Workspace::new(Limits {
2848 max_bytes: 0,
2849 max_work: limit,
2850 });
2851 let mut work = ws.begin();
2852 let mut seen = Vec::new();
2853 let result = (|| metered!(&mut work, bound, |w| phase(fail_at, &mut seen, w)))();
2854 ws.finish(&work);
2855 (result, ws.usage().work, seen)
2856 }
2857 for limit in 0..=9 {
2858 for fail_at in 0..=7 {
2859 let checked = run_phase(limit, fail_at, None);
2860 assert_eq!(run_phase(limit, fail_at, Some(7)), checked);
2861 assert_eq!(run_phase(limit, fail_at, Some(9)), checked);
2862 }
2863 }
2864 }
2865
2866 #[test]
2867 fn ranking_preserves_numerical_failure_and_budget_prefix() {
2868 for limit in 0..=6 {
2869 for fail_at in 0..=5 {
2870 let mut ws = Workspace::new(Limits {
2871 max_bytes: 1 << 20,
2872 max_work: limit,
2873 });
2874 let mut state = State::new(2, 0, 0, &mut ws, 0, false, &mut Vec::new()).unwrap();
2875 state.p.extend([V::default(); 2]);
2876 state.remap.0.extend([0, 1]);
2877 state.q[0] = Q {
2878 c: f32::MAX,
2879 w: 0.5,
2880 inverse_weight: 2.0,
2881 ..Q::default()
2882 };
2883 state.q[1] = Q {
2884 w: 1.0,
2885 inverse_weight: 1.0,
2886 ..Q::default()
2887 };
2888 for i in 0..5 {
2889 state.collapses.push(Collapse {
2890 a: if i == fail_at { 0 } else { 1 },
2891 b: 1,
2892 error: f32::from_bits(1),
2893 });
2894 }
2895 let mut work = ws.begin();
2896 let result = state.rank(5, &mut work);
2897 let (expected, visited, changed) = if limit <= fail_at as u64 && limit < 5 {
2898 (Err(Error::LimitExceeded), limit, limit as usize)
2899 } else if fail_at < 5 {
2900 (Err(Error::NumericalFailure), fail_at as u64 + 1, fail_at)
2901 } else {
2902 (Ok(()), 5, 5)
2903 };
2904 assert_eq!(result, expected);
2905 ws.finish(&work);
2906 assert_eq!(ws.usage().work, visited);
2907 for (i, c) in state.collapses.iter().enumerate() {
2908 assert_eq!(c.error.to_bits(), if i < changed { 0 } else { 1 });
2909 }
2910 }
2911 }
2912 }
2913}
2914
2915#[cfg(test)]
2916mod retention_tests {
2917 use alloc::vec::Vec;
2918
2919 use crate::{
2920 optimize_overdraw, optimize_vertex_cache, simplify, Positions, SimplifyOptions,
2921 SimplifySettings,
2922 };
2923 use crate::{Error, Limits, Retention, Workspace};
2924
2925 #[test]
2926 fn cache_update_cache_releases_scratch_and_preserves_results() {
2927 let positions = [
2928 [0.0, 0.0, 0.0],
2929 [1.0, 0.0, 0.0],
2930 [0.0, 1.0, 0.0],
2931 [1.0, 1.0, 0.1],
2932 ];
2933 let indices = [0, 1, 2, 2, 1, 3];
2934 let mut outcomes = Vec::new();
2935 for retention in [Retention::Lean, Retention::Reuse] {
2936 let mut ws = Workspace::default();
2937 ws.set_retention(retention);
2938 let cached = optimize_vertex_cache(&indices, positions.len(), &mut ws).unwrap();
2939 let cache_work = ws.usage().work;
2940 let mut updated_indices = indices;
2941 let mut updated_positions = positions;
2942 let result = crate::simplify_with_update(
2943 &mut updated_indices,
2944 &mut crate::PositionsMut::from_packed(&mut updated_positions),
2945 None,
2946 &[],
2947 None,
2948 SimplifySettings {
2949 target_index_count: indices.len(),
2950 target_error: 0.5,
2951 options: SimplifyOptions::EMPTY,
2952 },
2953 &mut ws,
2954 )
2955 .unwrap();
2956 let update_work = ws.usage().work;
2957 if retention == Retention::Lean {
2958 assert_eq!(ws.integers.capacity(), 0);
2959 assert_eq!(ws.floats.capacity(), 0);
2960 assert_eq!(ws.flags.capacity(), 0);
2961 assert_eq!(ws.keys.capacity(), 0);
2962 assert_eq!(ws.vertices.capacity(), 0);
2963 }
2964 assert!(ws.simplify.is_some());
2965 let cached_again =
2966 optimize_vertex_cache(&updated_indices, positions.len(), &mut ws).unwrap();
2967 if retention == Retention::Lean {
2968 assert!(ws.simplify.is_none());
2969 }
2970 outcomes.push((
2971 cached,
2972 result.index_count,
2973 result.error.to_bits(),
2974 updated_indices,
2975 updated_positions.map(|p| p.map(f32::to_bits)),
2976 cached_again,
2977 [cache_work, update_work, ws.usage().work],
2978 ));
2979 }
2980 assert_eq!(outcomes[0], outcomes[1]);
2981 }
2982
2983 #[test]
2984 fn switching_chain_family_releases_scratch_and_preserves_results() {
2985 let p = [
2986 [0.0, 0.0, 0.0],
2987 [1.0, 0.0, 0.0],
2988 [0.0, 1.0, 0.0],
2989 [1.0, 1.0, 0.1],
2990 ];
2991 let i = [0, 1, 2, 2, 1, 3];
2992 let settings = SimplifySettings {
2993 target_index_count: 3,
2994 target_error: 0.5,
2995 options: SimplifyOptions::EMPTY,
2996 };
2997 let mut ws = Workspace::default();
2998 ws.set_retention(Retention::Lean);
2999 let simplified = simplify(&i, Positions::from_packed(&p), settings, &mut ws).unwrap();
3000 assert!(ws.simplify.as_ref().unwrap().capacity_bytes().unwrap() > 0);
3001 assert_eq!(ws.simplify.as_ref().unwrap().q.capacity(), 0);
3002 let mut reuse = Workspace::default();
3003 assert_eq!(reuse.retention(), Retention::Reuse);
3004 let expected = simplify(&i, Positions::from_packed(&p), settings, &mut reuse).unwrap();
3005 assert_eq!(expected.indices, simplified.indices);
3006 assert_eq!(expected.error.to_bits(), simplified.error.to_bits());
3007 assert!(reuse.simplify.as_ref().unwrap().q.capacity() > 0);
3008 let expected_cache = optimize_vertex_cache(&i, p.len(), &mut reuse).unwrap();
3009 assert!(reuse.simplify.is_some());
3010 let expected_overdraw = optimize_overdraw(
3011 &expected_cache,
3012 Positions::from_packed(&p),
3013 1.05,
3014 &mut reuse,
3015 )
3016 .unwrap();
3017 assert!(reuse.simplify.is_some());
3018 assert!(reuse.vertices.capacity() > 0);
3019 let cached = optimize_vertex_cache(&i, p.len(), &mut ws).unwrap();
3020 assert!(ws.simplify.is_none());
3021 assert!(ws.vertices.capacity() > 0);
3022 assert_eq!(
3023 cached,
3024 optimize_vertex_cache(&i, p.len(), &mut Workspace::default()).unwrap()
3025 );
3026 let vertex_ptr = ws.vertices.as_ptr();
3027 let integer_ptr = ws.integers.as_ptr();
3028 assert_eq!(cached, optimize_vertex_cache(&i, p.len(), &mut ws).unwrap());
3029 assert_eq!(vertex_ptr, ws.vertices.as_ptr());
3030 assert_eq!(integer_ptr, ws.integers.as_ptr());
3031 let overdraw =
3032 optimize_overdraw(&cached, Positions::from_packed(&p), 1.05, &mut ws).unwrap();
3033 assert_eq!(overdraw, expected_overdraw);
3034 assert_eq!(ws.vertices.capacity(), 0);
3035 assert_eq!(ws.flags.capacity(), 0);
3036 assert_eq!(
3037 overdraw,
3038 optimize_overdraw(
3039 &cached,
3040 Positions::from_packed(&p),
3041 1.05,
3042 &mut Workspace::default()
3043 )
3044 .unwrap()
3045 );
3046 let integer_ptr = ws.integers.as_ptr();
3047 let float_ptr = ws.floats.as_ptr();
3048 assert_eq!(
3049 overdraw,
3050 optimize_overdraw(&cached, Positions::from_packed(&p), 1.05, &mut ws).unwrap()
3051 );
3052 assert_eq!(integer_ptr, ws.integers.as_ptr());
3053 assert_eq!(float_ptr, ws.floats.as_ptr());
3054 let again = simplify(&i, Positions::from_packed(&p), settings, &mut ws).unwrap();
3055 assert_eq!(again.indices, simplified.indices);
3056 assert_eq!(again.error.to_bits(), simplified.error.to_bits());
3057 assert_eq!(ws.integers.capacity(), 0);
3058 assert_eq!(ws.floats.capacity(), 0);
3059 assert_eq!(ws.keys.capacity(), 0);
3060 assert_eq!(ws.simplify.as_ref().unwrap().q.capacity(), 0);
3061 let state_bytes = ws.simplify.as_ref().unwrap().capacity_bytes().unwrap();
3062 assert_eq!(ws.retained_bytes().unwrap(), state_bytes);
3063 assert_eq!(ws.limits(), Limits::default());
3064 assert!(ws.usage().bytes >= state_bytes);
3065 assert!(ws.usage().work > 0);
3066 assert_eq!(
3068 optimize_vertex_cache(&[4, 0, 1], p.len(), &mut ws),
3069 Err(Error::IndexOutOfBounds)
3070 );
3071 assert!(ws.simplify.is_some());
3072 assert_eq!(
3073 optimize_vertex_cache(&[4, 0, 1], p.len(), &mut reuse),
3074 Err(Error::IndexOutOfBounds)
3075 );
3076 assert_eq!(ws.retained_bytes().unwrap(), state_bytes);
3077 let fifo = crate::optimize_vertex_cache_fifo(&i, p.len(), 16, &mut ws).unwrap();
3078 assert!(ws.simplify.is_none());
3079 assert_eq!(
3080 fifo,
3081 crate::optimize_vertex_cache_fifo(&i, p.len(), 16, &mut Workspace::default()).unwrap()
3082 );
3083 let usage = ws.usage();
3084 ws.set_retention(Retention::Lean);
3085 assert_eq!(ws.usage(), usage);
3086 ws.clear();
3087 assert_eq!(ws.retention(), Retention::Lean);
3088 ws.set_limits(Limits::default());
3089 assert_eq!(ws.retention(), Retention::Lean);
3090 ws.set_retention(Retention::Reuse);
3091 assert_eq!(ws.retained_bytes().unwrap(), 0);
3092 assert_eq!(ws.usage(), crate::Usage::default());
3093 }
3094}