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_generic, simplify_points_into, simplify_points_into_generic,
10 simplify_prune, simplify_prune_generic, simplify_prune_into, simplify_prune_into_generic,
11 simplify_sloppy, simplify_sloppy_generic, simplify_sloppy_into, simplify_sloppy_into_generic,
12 simplify_with_update, simplify_with_update_generic,
13};
14
15#[inline(always)]
19fn sqrt(value: f32) -> f32 {
20 #[cfg(feature = "std")]
21 if value.to_bits() < 0x7f80_0000 {
22 return value.sqrt();
23 }
24 crate::math::sqrt(value)
25}
26
27#[inline]
31#[allow(clippy::eq_op)] fn packed_finite(values: &[[f32; 3]]) -> bool {
33 let (chunks, tail) = values.as_flattened().as_chunks::<8>();
34 let mut lanes = [0.0f32; 8];
35 for chunk in chunks {
36 for (lane, &x) in lanes.iter_mut().zip(chunk) {
37 *lane += x - x;
38 }
39 }
40 let mut sum = tail.iter().fold(0.0f32, |sum, &x| sum + (x - x));
41 for lane in lanes {
42 sum += lane;
43 }
44 sum == 0.0
45}
46
47#[cfg(not(feature = "std"))]
48type SqrtCache = crate::math::SqrtCache;
49
50#[cfg(feature = "std")]
53struct SqrtCache;
54#[cfg(feature = "std")]
55impl SqrtCache {
56 const fn new() -> Self {
57 Self
58 }
59 #[inline(always)]
60 fn sqrt(&mut self, value: f32) -> f32 {
61 sqrt(value)
62 }
63}
64
65trait Meter {
72 const PREPAID: bool;
74 fn add(&mut self, count: usize) -> Result<(), Error>;
75 fn precharge(&mut self, count: usize, units: usize) -> Result<bool, Error>;
76 fn scan<T>(
77 &mut self,
78 values: impl ExactSizeIterator<Item = T>,
79 visit: impl FnMut(T) -> Result<(), Error>,
80 ) -> Result<(), Error>;
81}
82impl Meter for Work {
83 const PREPAID: bool = false;
84 #[inline(always)]
85 fn add(&mut self, count: usize) -> Result<(), Error> {
86 Work::add(self, count)
87 }
88 #[inline(always)]
89 fn precharge(&mut self, count: usize, units: usize) -> Result<bool, Error> {
90 Work::precharge(self, count, units)
91 }
92 #[inline(always)]
93 fn scan<T>(
94 &mut self,
95 values: impl ExactSizeIterator<Item = T>,
96 visit: impl FnMut(T) -> Result<(), Error>,
97 ) -> Result<(), Error> {
98 Work::scan(self, values, visit)
99 }
100}
101struct Prepaid(usize);
102impl Meter for Prepaid {
103 const PREPAID: bool = true;
104 #[inline(always)]
105 fn add(&mut self, count: usize) -> Result<(), Error> {
106 self.0 += count;
107 Ok(())
108 }
109 #[inline(always)]
110 fn precharge(&mut self, count: usize, units: usize) -> Result<bool, Error> {
111 self.0 += count.checked_mul(units).ok_or(Error::SizeOverflow)?;
112 Ok(true)
113 }
114 #[inline(always)]
115 fn scan<T>(
116 &mut self,
117 values: impl ExactSizeIterator<Item = T>,
118 mut visit: impl FnMut(T) -> Result<(), Error>,
119 ) -> Result<(), Error> {
120 let count = values.len();
121 for (i, value) in values.enumerate() {
122 if let Err(error) = visit(value) {
123 self.0 += i + 1;
124 return Err(error);
125 }
126 }
127 self.0 += count;
128 Ok(())
129 }
130}
131macro_rules! metered {
134 ($work:expr, $bound:expr, |$m:ident| $body:expr) => {{
135 let work: &mut Work = $work;
136 match $bound {
137 Some(bound) if work.covers(bound)? => {
138 let mut tally = Prepaid(0);
139 let result = {
140 let $m = &mut tally;
141 $body
142 };
143 debug_assert!(tally.0 <= bound);
144 work.add(tally.0)?;
145 result
146 }
147 _ => {
148 let $m = work;
149 $body
150 }
151 }
152 }};
153}
154
155#[derive(Clone, Copy, Debug, Default, PartialEq, Eq)]
157pub struct SimplifyOptions(u32);
158impl SimplifyOptions {
159 pub const EMPTY: Self = Self(0);
161 pub const LOCK_BORDER: Self = Self(1);
163 pub const SPARSE: Self = Self(2);
165 pub const ERROR_ABSOLUTE: Self = Self(4);
167 pub const PRUNE: Self = Self(8);
169 pub const REGULARIZE: Self = Self(16);
171 pub const PERMISSIVE: Self = Self(32);
173 pub const REGULARIZE_LIGHT: Self = Self(64);
175 #[cfg(feature = "experimental")]
177 pub const PRESERVE_FOLDS: Self = Self(128);
178 #[cfg(feature = "experimental")]
180 pub const ERROR_CLAMPED: Self = Self(256);
181 pub const fn from_bits(bits: u32) -> Result<Self, Error> {
186 let mask = if cfg!(feature = "experimental") {
187 511
188 } else {
189 127
190 };
191 if bits & !mask != 0 {
192 Err(Error::UnknownFlags)
193 } else {
194 Ok(Self(bits))
195 }
196 }
197 pub const fn bits(self) -> u32 {
199 self.0
200 }
201 pub const fn contains(self, other: Self) -> bool {
203 self.0 & other.0 == other.0
204 }
205}
206impl core::ops::BitOr for SimplifyOptions {
207 type Output = Self;
208 fn bitor(self, rhs: Self) -> Self {
209 Self(self.0 | rhs.0)
210 }
211}
212impl core::ops::BitOrAssign for SimplifyOptions {
213 fn bitor_assign(&mut self, rhs: Self) {
214 self.0 |= rhs.0;
215 }
216}
217#[derive(Clone, Copy, Debug)]
219pub struct SimplifySettings {
220 pub target_index_count: usize,
222 pub target_error: f32,
224 pub options: SimplifyOptions,
226}
227#[derive(Debug)]
229pub struct SimplifiedMeshGeneric<I: crate::Index = u32> {
230 pub indices: Vec<I>,
232 pub error: f32,
234}
235#[derive(Clone, Copy, Debug)]
237pub struct SimplifyResult {
238 pub index_count: usize,
240 pub error: f32,
242}
243pub fn simplify_scale(positions: Positions<'_>) -> Result<f32, Error> {
253 let Some(values) = positions.packed_values() else {
254 return scale_view(positions);
255 };
256 let finite = values
260 .as_flattened()
261 .iter()
262 .fold(true, |finite, v| finite & v.is_finite());
263 if !finite {
264 return Err(Error::InvalidParameter);
265 }
266 let mut lo = [f32::MAX; 3];
267 let mut hi = [-f32::MAX; 3];
268 for v in values {
269 for j in 0..3 {
270 if lo[j] > v[j] {
271 lo[j] = v[j];
272 }
273 if hi[j] < v[j] {
274 hi[j] = v[j];
275 }
276 }
277 }
278 if values.is_empty() {
279 return Ok(0.0);
280 }
281 let mut extent = 0.0;
282 for j in 0..3 {
283 let d = hi[j] - lo[j];
284 if d >= extent {
285 extent = d;
286 }
287 }
288 if !extent.is_finite() {
289 return Err(Error::NumericalFailure);
290 }
291 Ok(extent)
292}
293#[inline(never)]
295fn scale_view(positions: Positions<'_>) -> Result<f32, Error> {
296 if let Some(records) = positions.scale_full_records() {
297 return scale_records(records, positions.is_empty());
298 }
299 if let Some(records) = positions.scale_records() {
300 return scale_records(records, positions.is_empty());
301 }
302 Ok(bounds(positions)?.1)
303}
304fn scale_records(
305 values: impl Iterator<Item = [f32; 3]> + Clone,
306 empty: bool,
307) -> Result<f32, Error> {
308 let finite = values.clone().fold(true, |finite, v| {
311 finite & v[0].is_finite() & v[1].is_finite() & v[2].is_finite()
312 });
313 if !finite {
314 return Err(Error::InvalidParameter);
315 }
316 let mut lo = [f32::MAX; 3];
317 let mut hi = [-f32::MAX; 3];
318 for v in values {
319 for j in 0..3 {
320 if lo[j] > v[j] {
321 lo[j] = v[j];
322 }
323 if hi[j] < v[j] {
324 hi[j] = v[j];
325 }
326 }
327 }
328 if empty {
329 return Ok(0.0);
330 }
331 let mut extent = 0.0;
332 for j in 0..3 {
333 let d = hi[j] - lo[j];
334 if d >= extent {
335 extent = d;
336 }
337 }
338 if !extent.is_finite() {
339 return Err(Error::NumericalFailure);
340 }
341 Ok(extent)
342}
343fn bounds_impl<const VALIDATED: bool>(p: Positions<'_>) -> Result<([f32; 3], f32), Error> {
344 let mut lo = [f32::MAX; 3];
345 let mut hi = [-f32::MAX; 3];
346 p.for_each(|v| {
347 for j in 0..3 {
348 if !VALIDATED && !v[j].is_finite() {
349 return Err(Error::InvalidParameter);
350 }
351 if lo[j] > v[j] {
352 lo[j] = v[j];
353 }
354 if hi[j] < v[j] {
355 hi[j] = v[j];
356 }
357 }
358 Ok(())
359 })?;
360 if p.is_empty() {
361 return Ok((lo, 0.0));
362 }
363 let mut extent = 0.0;
364 for j in 0..3 {
365 let d = hi[j] - lo[j];
366 if d >= extent {
367 extent = d;
368 }
369 }
370 if !extent.is_finite() {
371 return Err(Error::NumericalFailure);
372 }
373 Ok((lo, extent))
374}
375fn bounds(p: Positions<'_>) -> Result<([f32; 3], f32), Error> {
377 bounds_impl::<false>(p)
378}
379#[inline]
387pub fn simplify_generic<I: crate::Index>(
388 indices: &[I],
389 positions: Positions<'_>,
390 settings: SimplifySettings,
391 workspace: &mut Workspace,
392) -> Result<SimplifiedMeshGeneric<I>, Error> {
393 I::with_input(indices, workspace, |indices, workspace| {
394 simplify_u32(indices, positions, settings, workspace)
395 .and_then(|value| crate::index::Convert::<I>::convert(value, workspace))
396 })
397}
398
399fn simplify_u32(
400 indices: &[u32],
401 positions: Positions<'_>,
402 settings: SimplifySettings,
403 workspace: &mut Workspace,
404) -> Result<SimplifiedMeshGeneric, Error> {
405 allocating(indices, positions, None, &[], None, settings, workspace)
406}
407#[inline]
415pub fn simplify_with_attributes_generic<I: crate::Index>(
416 indices: &[I],
417 positions: Positions<'_>,
418 attributes: Attributes<'_>,
419 weights: &[f32],
420 vertex_flags: Option<&[VertexFlags]>,
421 settings: SimplifySettings,
422 workspace: &mut Workspace,
423) -> Result<SimplifiedMeshGeneric<I>, Error> {
424 I::with_input(indices, workspace, |indices, workspace| {
425 simplify_with_attributes_u32(
426 indices,
427 positions,
428 attributes,
429 weights,
430 vertex_flags,
431 settings,
432 workspace,
433 )
434 .and_then(|value| crate::index::Convert::<I>::convert(value, workspace))
435 })
436}
437
438fn simplify_with_attributes_u32(
439 indices: &[u32],
440 positions: Positions<'_>,
441 attributes: Attributes<'_>,
442 weights: &[f32],
443 vertex_flags: Option<&[VertexFlags]>,
444 settings: SimplifySettings,
445 workspace: &mut Workspace,
446) -> Result<SimplifiedMeshGeneric, Error> {
447 allocating(
448 indices,
449 positions,
450 Some(attributes),
451 weights,
452 vertex_flags,
453 settings,
454 workspace,
455 )
456}
457pub(crate) fn simplify_flagged(
459 indices: &[u32],
460 positions: Positions<'_>,
461 flags: &[VertexFlags],
462 settings: SimplifySettings,
463 workspace: &mut Workspace,
464) -> Result<SimplifiedMeshGeneric, Error> {
465 allocating(
466 indices,
467 positions,
468 None,
469 &[],
470 Some(flags),
471 settings,
472 workspace,
473 )
474}
475fn allocating(
476 indices: &[u32],
477 positions: Positions<'_>,
478 attributes: Option<Attributes<'_>>,
479 weights: &[f32],
480 flags: Option<&[VertexFlags]>,
481 settings: SimplifySettings,
482 ws: &mut Workspace,
483) -> Result<SimplifiedMeshGeneric, Error> {
484 ws.lod_error_limited = false;
485 let mut work = ws.begin();
486 let result = (|| {
487 validate(
488 indices, positions, attributes, weights, flags, settings, &mut work,
489 )?;
490 ws.acquire(crate::workspace::ScratchFamily::Simplify);
491 ws.prepare([0; 4], checked_bytes(indices.len(), 4)?)?;
492 let mut out = crate::workspace::output(indices.len())?;
493 let output_bytes = checked_bytes(out.capacity(), 4)?;
494 let r = run(
495 &mut out,
496 indices,
497 positions,
498 attributes,
499 weights,
500 flags,
501 settings,
502 ws,
503 &mut work,
504 output_bytes,
505 )?;
506 out.truncate(r.index_count);
507 Ok(SimplifiedMeshGeneric {
508 indices: out,
509 error: r.error,
510 })
511 })();
512 ws.finish(&work);
513 result
514}
515#[inline]
522pub fn simplify_into_generic<I: crate::Index>(
523 destination: &mut [I],
524 indices: &[I],
525 positions: Positions<'_>,
526 settings: SimplifySettings,
527 workspace: &mut Workspace,
528) -> Result<SimplifyResult, Error> {
529 I::with_input(indices, workspace, |indices, workspace| {
530 I::with_mut(destination, workspace, |destination, workspace| {
531 simplify_into_u32(destination, indices, positions, settings, workspace)
532 })
533 })
534}
535
536fn simplify_into_u32(
537 destination: &mut [u32],
538 indices: &[u32],
539 positions: Positions<'_>,
540 settings: SimplifySettings,
541 workspace: &mut Workspace,
542) -> Result<SimplifyResult, Error> {
543 into(
544 destination,
545 indices,
546 positions,
547 None,
548 &[],
549 None,
550 settings,
551 workspace,
552 )
553}
554#[allow(clippy::too_many_arguments)]
560#[inline]
561pub fn simplify_with_attributes_into_generic<I: crate::Index>(
562 destination: &mut [I],
563 indices: &[I],
564 positions: Positions<'_>,
565 attributes: Attributes<'_>,
566 weights: &[f32],
567 vertex_flags: Option<&[VertexFlags]>,
568 settings: SimplifySettings,
569 workspace: &mut Workspace,
570) -> Result<SimplifyResult, Error> {
571 I::with_input(indices, workspace, |indices, workspace| {
572 I::with_mut(destination, workspace, |destination, workspace| {
573 simplify_with_attributes_into_u32(
574 destination,
575 indices,
576 positions,
577 attributes,
578 weights,
579 vertex_flags,
580 settings,
581 workspace,
582 )
583 })
584 })
585}
586
587#[allow(clippy::too_many_arguments)]
588fn simplify_with_attributes_into_u32(
589 destination: &mut [u32],
590 indices: &[u32],
591 positions: Positions<'_>,
592 attributes: Attributes<'_>,
593 weights: &[f32],
594 vertex_flags: Option<&[VertexFlags]>,
595 settings: SimplifySettings,
596 workspace: &mut Workspace,
597) -> Result<SimplifyResult, Error> {
598 into(
599 destination,
600 indices,
601 positions,
602 Some(attributes),
603 weights,
604 vertex_flags,
605 settings,
606 workspace,
607 )
608}
609#[allow(clippy::too_many_arguments)]
610fn into(
611 out: &mut [u32],
612 indices: &[u32],
613 p: Positions<'_>,
614 a: Option<Attributes<'_>>,
615 weights: &[f32],
616 flags: Option<&[VertexFlags]>,
617 settings: SimplifySettings,
618 ws: &mut Workspace,
619) -> Result<SimplifyResult, Error> {
620 let mut work = ws.begin();
621 let result = (|| {
622 if out.len() < indices.len() {
623 return Err(Error::BufferTooSmall);
624 }
625 validate(indices, p, a, weights, flags, settings, &mut work)?;
626 ws.acquire(crate::workspace::ScratchFamily::Simplify);
627 run(
628 out, indices, p, a, weights, flags, settings, ws, &mut work, 0,
629 )
630 })();
631 ws.finish(&work);
632 result
633}
634#[allow(clippy::too_many_arguments)]
635fn validate(
636 indices: &[u32],
637 p: Positions<'_>,
638 a: Option<Attributes<'_>>,
639 weights: &[f32],
640 flags: Option<&[VertexFlags]>,
641 s: SimplifySettings,
642 work: &mut Work,
643) -> Result<(), Error> {
644 topology(indices, p.len(), work)?;
645 if s.target_index_count > indices.len() || !s.target_error.is_finite() || s.target_error < 0.0 {
646 return Err(Error::InvalidParameter);
647 }
648 validate_vertex_flags(flags, p.len())?;
649 if let Some(a) = a {
650 if a.len() != p.len() || a.components() != weights.len() {
651 return Err(Error::InvalidLayout);
652 }
653 }
654 work.scan(weights.iter().copied(), |w| {
655 if !w.is_finite() || w < 0.0 {
656 return Err(Error::InvalidParameter);
657 }
658 Ok(())
659 })?;
660 if a.is_none() {
661 if let Some(records) = p.scale_full_records() {
662 return work.scan(records, |v| {
663 if v.iter().fold(true, |finite, x| finite & x.is_finite()) {
664 Ok(())
665 } else {
666 Err(Error::InvalidParameter)
667 }
668 });
669 }
670 if let Some(values) = p.packed_values() {
674 if work.covers(values.len())? && packed_finite(values) {
675 return work.add(values.len());
676 }
677 }
678 return p.for_each_counted(work, |v| {
679 if !v.iter().fold(true, |finite, x| finite & x.is_finite()) {
680 Err(Error::InvalidParameter)
681 } else {
682 Ok(())
683 }
684 });
685 }
686 let mut start = 0;
694 if let (Some(values), Some((records, width))) = (
695 p.packed_values(),
696 a.and_then(|a| Some((a.contiguous_floats()?, a.components()))),
697 ) {
698 let visits = width
699 .checked_add(1)
700 .and_then(|v| v.checked_mul(values.len()));
701 if visits.is_some_and(|v| matches!(work.covers(v), Ok(true))) {
702 start = first_nonfinite_vertex(values, records, width);
703 work.add_covered(start * (width + 1));
704 }
705 }
706 for i in start..p.len() {
707 work.add(1)?;
708 if !p
709 .at(i)?
710 .iter()
711 .fold(true, |finite, x| finite & x.is_finite())
712 {
713 return Err(Error::InvalidParameter);
714 }
715 if let Some(a) = a {
716 if let Some(values) = a.float_record(i) {
717 work.scan(values.iter().copied(), |value| {
718 if value.is_finite() {
719 Ok(())
720 } else {
721 Err(Error::InvalidParameter)
722 }
723 })?;
724 } else {
725 work.scan(0..a.components(), |k| {
726 if !a.get(i, k).ok_or(Error::InvalidLayout)?.is_finite() {
727 return Err(Error::InvalidParameter);
728 }
729 Ok(())
730 })?;
731 }
732 }
733 }
734 Ok(())
735}
736#[derive(Clone, Copy, Default, Debug)]
737struct V {
738 x: f32,
739 y: f32,
740 z: f32,
741}
742impl From<[f32; 3]> for V {
743 fn from(v: [f32; 3]) -> Self {
744 Self {
745 x: v[0],
746 y: v[1],
747 z: v[2],
748 }
749 }
750}
751impl V {
752 #[inline(always)]
753 fn sub(self, b: Self) -> Self {
754 Self {
755 x: self.x - b.x,
756 y: self.y - b.y,
757 z: self.z - b.z,
758 }
759 }
760 #[inline(always)]
761 fn dot(self, b: Self) -> f32 {
762 self.x * b.x + self.y * b.y + self.z * b.z
763 }
764 #[inline(always)]
765 fn cross(self, b: Self) -> Self {
766 Self {
767 x: self.y * b.z - self.z * b.y,
768 y: self.z * b.x - self.x * b.z,
769 z: self.x * b.y - self.y * b.x,
770 }
771 }
772 #[inline(always)]
773 fn normalize(&mut self, cache: &mut SqrtCache) -> f32 {
774 let l = cache.sqrt(self.dot(*self));
775 if l > 0.0 {
776 self.x /= l;
777 self.y /= l;
778 self.z /= l;
779 }
780 l
781 }
782}
783#[derive(Clone, Copy, Default)]
784struct Q {
785 a00: f32,
786 a11: f32,
787 a22: f32,
788 a10: f32,
789 a20: f32,
790 a21: f32,
791 b0: f32,
792 b1: f32,
793 b2: f32,
794 c: f32,
795 w: f32,
796 inverse_weight: f32,
798}
799impl Q {
800 #[inline(always)]
801 fn add(&mut self, r: Self) {
802 self.a00 += r.a00;
803 self.a11 += r.a11;
804 self.a22 += r.a22;
805 self.a10 += r.a10;
806 self.a20 += r.a20;
807 self.a21 += r.a21;
808 self.b0 += r.b0;
809 self.b1 += r.b1;
810 self.b2 += r.b2;
811 self.c += r.c;
812 self.w += r.w;
813 }
814 #[inline(always)]
815 fn eval(self, v: V) -> f32 {
816 let mut rx = (self.b0 + self.a10 * v.y) * 2.0;
817 let mut ry = (self.b1 + self.a21 * v.z) * 2.0;
818 let mut rz = (self.b2 + self.a20 * v.x) * 2.0;
819 rx += self.a00 * v.x;
820 ry += self.a11 * v.y;
821 rz += self.a22 * v.z;
822 self.c + rx * v.x + ry * v.y + rz * v.z
823 }
824 #[inline(always)]
825 fn error(self, v: V) -> f32 {
826 self.eval(v).abs() * self.inverse_weight
827 }
828 fn cache_inverse_weight(&mut self) {
829 self.inverse_weight = if self.w == 0.0 { 0.0 } else { 1.0 / self.w };
830 }
831 #[inline(always)]
832 fn plane(n: V, d: f32, w: f32) -> Self {
833 let aw = n.x * w;
834 let bw = n.y * w;
835 let cw = n.z * w;
836 let dw = d * w;
837 Self {
838 a00: n.x * aw,
839 a11: n.y * bw,
840 a22: n.z * cw,
841 a10: n.x * bw,
842 a20: n.x * cw,
843 a21: n.y * cw,
844 b0: n.x * dw,
845 b1: n.y * dw,
846 b2: n.z * dw,
847 c: d * dw,
848 w,
849 inverse_weight: 0.0,
850 }
851 }
852 #[inline(always)]
853 fn point(p: V, w: f32) -> Self {
854 Self {
855 a00: w,
856 a11: w,
857 a22: w,
858 b0: -p.x * w,
859 b1: -p.y * w,
860 b2: -p.z * w,
861 c: p.dot(p) * w,
862 w,
863 ..Self::default()
864 }
865 }
866 #[inline(always)]
867 fn triangle(a: V, b: V, c: V, w: f32, cache: &mut SqrtCache) -> Self {
868 let mut n = b.sub(a).cross(c.sub(a));
869 let area = n.normalize(cache);
870 Self::plane(n, -n.dot(a), cache.sqrt(area) * w)
871 }
872 #[inline(always)]
873 fn edge(a: V, b: V, c: V, w: f32, cache: &mut SqrtCache) -> Self {
874 let p10 = b.sub(a);
875 let ls = p10.dot(p10);
876 let p20 = c.sub(a);
877 let proj = p20.dot(p10);
878 let mut perp = V {
879 x: p20.x * ls - p10.x * proj,
880 y: p20.y * ls - p10.y * proj,
881 z: p20.z * ls - p10.z * proj,
882 };
883 perp.normalize(cache);
884 Self::plane(perp, -perp.dot(a), cache.sqrt(ls) * w)
885 }
886 #[inline(always)]
888 fn fields(self) -> [f32; 11] {
889 [
890 self.a00, self.a11, self.a22, self.a10, self.a20, self.a21, self.b0, self.b1, self.b2,
891 self.c, self.w,
892 ]
893 }
894 #[inline(always)]
895 fn finite(self) -> bool {
896 self.fields()
900 .into_iter()
901 .map(|x| x.to_bits() & 0x7fff_ffff)
902 .max()
903 .unwrap_or(0)
904 < 0x7f80_0000
905 }
906}
907#[derive(Clone, Copy, Default)]
908struct G {
909 x: f32,
910 y: f32,
911 z: f32,
912 w: f32,
913}
914impl G {
915 fn add(&mut self, r: Self) {
916 self.x += r.x;
917 self.y += r.y;
918 self.z += r.z;
919 self.w += r.w;
920 }
921}
922#[derive(Clone, Copy, Default)]
923struct Edge {
924 next: u32,
925 prev: u32,
926}
927#[derive(Clone, Copy, Default)]
928struct Collapse {
929 a: u32,
930 b: u32,
931 error: f32,
932}
933const NONE: usize = u32::MAX as usize;
934const MAN: u8 = 0;
935const BORDER: u8 = 1;
936const SEAM: u8 = 2;
937const COMPLEX: u8 = 3;
938const FRINGE: u8 = 4;
939const LOCKED: u8 = 5;
940const CAN: [[u8; 6]; 6] = [
941 [1, 1, 1, 1, 1, 1],
942 [0, 1, 0, 0, 1, 1],
943 [0, 0, 1, 0, 0, 1],
944 [0, 0, 0, 1, 1, 1],
945 [0, 0, 0, 0, 1, 0],
946 [0; 6],
947];
948const OPP: [[u8; 6]; 6] = [
949 [1; 6],
950 [1, 0, 1, 0, 0, 0],
951 [1, 1, 1, 0, 0, 1],
952 [1, 0, 0, 0, 0, 0],
953 [1, 0, 0, 0, 0, 0],
954 [1, 0, 1, 0, 0, 0],
955];
956const PICK_ANY: u8 = 1;
958const PICK_BOTH: u8 = 2;
959const PICK_FORWARD: u8 = 4;
960const PICK_OPPOSITE: u8 = 8;
961const PICK_CHECK_FORWARD: u8 = 16;
962const PICK_CHECK_BACK: u8 = 32;
963const PICK: [u8; 64] = {
964 let mut table = [0; 64];
965 let mut k0 = 0;
966 while k0 < 6 {
967 let mut k1 = 0;
968 while k1 < 6 {
969 let forward = CAN[k0][k1] != 0;
970 let reverse = CAN[k1][k0] != 0;
971 let mut rule = 0;
972 if forward || reverse {
973 rule |= PICK_ANY;
974 }
975 if forward && reverse {
976 rule |= PICK_BOTH;
977 }
978 if forward {
979 rule |= PICK_FORWARD;
980 }
981 if OPP[k0][k1] != 0 {
982 rule |= PICK_OPPOSITE;
983 }
984 let loop0 = k0 == BORDER as usize || k0 == SEAM as usize;
985 let loop1 = k1 == BORDER as usize || k1 == SEAM as usize;
986 if loop0 && k1 != MAN as usize {
987 rule |= PICK_CHECK_FORWARD;
988 }
989 if loop1 && k0 != MAN as usize {
990 rule |= PICK_CHECK_BACK;
991 }
992 table[k0 * 8 + k1] = rule;
993 k1 += 1;
994 }
995 k0 += 1;
996 }
997 table
998};
999#[inline(always)]
1001fn pair(k0: u8, k1: u8) -> usize {
1002 ((k0 as usize) << 3 | k1 as usize) & 63
1003}
1004struct Indices(Vec<u32>);
1007impl Indices {
1008 #[inline]
1009 fn get(&self, i: usize) -> usize {
1010 self.0[i] as usize
1011 }
1012 #[inline]
1013 fn set(&mut self, i: usize, value: usize) {
1014 self.0[i] = value as u32;
1015 }
1016 fn fill(&mut self, value: usize) {
1017 self.0.fill(value as u32);
1018 }
1019 fn len(&self) -> usize {
1020 self.0.len()
1021 }
1022}
1023struct PositionBounds {
1026 lo: [f32; 3],
1027 hi: [f32; 3],
1028}
1029pub(crate) struct State {
1030 vertex_count: usize,
1031 sqrt_cache: SqrtCache,
1032 offsets: Indices,
1033 edges: Vec<Edge>,
1034 remap: Indices,
1035 wedge: Indices,
1036 kind: Vec<u8>,
1037 forward: Indices,
1038 back: Indices,
1039 p: Vec<V>,
1040 a: Vec<f32>,
1041 q: Vec<Q>,
1042 aq: Vec<Q>,
1043 g: Vec<G>,
1044 vg: Vec<G>,
1045 sparse: Vec<u32>,
1046 original: Vec<u32>,
1047 clamped: bool,
1048 collapses: Vec<Collapse>,
1049 order: Indices,
1050 cr: Indices,
1051 locked: Vec<bool>,
1052 table: Indices,
1053 max_degree: usize,
1055 ac: usize,
1056 bytes: usize,
1057}
1058struct Input<'a> {
1061 indices: &'a [u32],
1062 original: Vec<u32>,
1063 update: bool,
1064}
1065impl<'a> Input<'a> {
1066 fn borrowed(indices: &'a [u32]) -> Self {
1067 Self {
1068 indices,
1069 original: Vec::new(),
1070 update: false,
1071 }
1072 }
1073 fn as_slice(&self) -> &[u32] {
1074 if self.update {
1075 &self.original
1076 } else {
1077 self.indices
1078 }
1079 }
1080}
1081struct Budget<'a> {
1082 ws: &'a mut Workspace,
1083 bytes: usize,
1084 charged: bool,
1085}
1086impl<'a> Budget<'a> {
1087 fn new(ws: &'a mut Workspace, bytes: usize) -> Self {
1088 Self {
1089 ws,
1090 bytes,
1091 charged: false,
1092 }
1093 }
1094 fn reclaim_input(
1095 &mut self,
1096 original: &mut Vec<u32>,
1097 added: Result<usize, Error>,
1098 ) -> Result<(), Error> {
1099 let requested =
1100 added.and_then(|added| self.bytes.checked_add(added).ok_or(Error::SizeOverflow));
1101 if requested.is_ok_and(|bytes| bytes > self.ws.limits().max_bytes) {
1102 let before = checked_bytes(original.capacity(), 4)?;
1103 crate::workspace::shrink(original, true)?;
1104 self.bytes -= before - checked_bytes(original.capacity(), 4)?;
1105 self.charged = false;
1106 }
1107 Ok(())
1108 }
1109 fn charge_current(&mut self) -> Result<(), Error> {
1110 if !self.charged {
1111 self.ws.charge_owned(self.bytes)?;
1112 self.charged = true;
1113 }
1114 Ok(())
1115 }
1116 fn reuse_capacity<T>(&mut self, v: &mut Vec<T>, n: usize) -> Result<(), Error> {
1117 let size = core::mem::size_of::<T>();
1118 let old = checked_bytes(v.capacity(), size)?;
1119 if self.bytes < old {
1120 return Err(Error::SizeOverflow);
1121 }
1122 if n <= v.capacity() {
1123 self.charge_current()?;
1124 return Ok(());
1125 }
1126 let minimum = n;
1127 let base = self.bytes.checked_sub(old).ok_or(Error::SizeOverflow)?;
1128 let requested = checked_bytes(minimum, size)?;
1129 self.ws
1130 .charge_owned(base.checked_add(requested).ok_or(Error::SizeOverflow)?)?;
1131 if n > v.capacity() {
1132 v.try_reserve_exact(n.saturating_sub(v.len()))
1133 .map_err(|_| Error::AllocationFailed)?;
1134 }
1135 self.bytes = base
1136 .checked_add(checked_bytes(v.capacity(), size)?)
1137 .ok_or(Error::SizeOverflow)?;
1138 if v.capacity() != minimum {
1139 self.ws.charge_owned(self.bytes)?;
1140 }
1141 self.charged = true;
1142 Ok(())
1143 }
1144 fn reuse<T: Default + Clone>(&mut self, v: &mut Vec<T>, n: usize) -> Result<(), Error> {
1145 self.reuse_capacity(v, n)?;
1146 v.resize(n, T::default());
1147 Ok(())
1148 }
1149 fn vec<T: Default + Clone>(&mut self, n: usize) -> Result<Vec<T>, Error> {
1150 self.filled(n, T::default())
1151 }
1152 fn filled<T: Clone>(&mut self, n: usize, value: T) -> Result<Vec<T>, Error> {
1153 let mut v = self.reserve(n)?;
1154 v.resize(n, value);
1155 Ok(v)
1156 }
1157 fn release<T>(&mut self, value: Vec<T>) {
1158 self.bytes -= value.capacity() * core::mem::size_of::<T>();
1159 drop(value);
1160 }
1161 fn reserve<T>(&mut self, n: usize) -> Result<Vec<T>, Error> {
1162 let b = checked_bytes(n, core::mem::size_of::<T>())?;
1163 self.ws
1164 .charge_owned(self.bytes.checked_add(b).ok_or(Error::SizeOverflow)?)?;
1165 let mut v = Vec::new();
1166 v.try_reserve_exact(n)
1167 .map_err(|_| Error::AllocationFailed)?;
1168 self.bytes = self
1169 .bytes
1170 .checked_add(checked_bytes(v.capacity(), core::mem::size_of::<T>())?)
1171 .ok_or(Error::SizeOverflow)?;
1172 if v.capacity() != n {
1173 self.ws.charge_owned(self.bytes)?;
1174 }
1175 self.charged = true;
1176 Ok(v)
1177 }
1178}
1179impl core::fmt::Debug for State {
1180 fn fmt(&self, f: &mut core::fmt::Formatter<'_>) -> core::fmt::Result {
1181 f.debug_struct("SimplifyScratch")
1182 .field("vertices", &self.vertex_count)
1183 .field("heap_bytes", &self.capacity_bytes())
1184 .finish()
1185 }
1186}
1187impl State {
1188 pub(crate) fn capacity_bytes(&self) -> Result<usize, Error> {
1189 let fields = [
1190 (self.offsets.0.capacity(), 4),
1191 (self.edges.capacity(), core::mem::size_of::<Edge>()),
1192 (self.remap.0.capacity(), 4),
1193 (self.wedge.0.capacity(), 4),
1194 (self.kind.capacity(), 1),
1195 (self.forward.0.capacity(), 4),
1196 (self.back.0.capacity(), 4),
1197 (self.p.capacity(), core::mem::size_of::<V>()),
1198 (self.a.capacity(), 4),
1199 (self.q.capacity(), core::mem::size_of::<Q>()),
1200 (self.aq.capacity(), core::mem::size_of::<Q>()),
1201 (self.g.capacity(), core::mem::size_of::<G>()),
1202 (self.vg.capacity(), core::mem::size_of::<G>()),
1203 (self.sparse.capacity(), 4),
1204 (self.original.capacity(), 4),
1205 (self.collapses.capacity(), core::mem::size_of::<Collapse>()),
1206 (self.order.0.capacity(), 4),
1207 (self.cr.0.capacity(), 4),
1208 (self.locked.capacity(), 1),
1209 (self.table.0.capacity(), 4),
1210 ];
1211 fields.into_iter().try_fold(0usize, |sum, (n, size)| {
1212 sum.checked_add(checked_bytes(n, size)?)
1213 .ok_or(Error::SizeOverflow)
1214 })
1215 }
1216 fn reclaim_for(
1217 &mut self,
1218 ws: &Workspace,
1219 requested: Result<usize, Error>,
1220 original: &mut Vec<u32>,
1221 ) -> Result<(), Error> {
1222 if !requested.is_ok_and(|bytes| bytes > ws.limits().max_bytes) {
1223 return Ok(());
1224 }
1225 let before = self.capacity_bytes()? + checked_bytes(original.capacity(), 4)?;
1226 self.remap.0.shrink_to(self.vertex_count);
1229 self.wedge.0.shrink_to(self.vertex_count);
1230 self.p.shrink_to(self.vertex_count);
1231 macro_rules! shrink {
1232 ($($v:expr),* $(,)?) => { $(crate::workspace::shrink(&mut $v, true)?;)* };
1233 }
1234 shrink!(
1235 self.offsets.0,
1236 self.edges,
1237 self.kind,
1238 self.forward.0,
1239 self.back.0,
1240 self.a,
1241 self.q,
1242 self.aq,
1243 self.g,
1244 self.vg,
1245 self.sparse,
1246 self.original,
1247 self.collapses,
1248 self.order.0,
1249 self.cr.0,
1250 self.locked,
1251 self.table.0,
1252 *original
1253 );
1254 let after = self.capacity_bytes()? + checked_bytes(original.capacity(), 4)?;
1255 self.bytes -= before - after;
1256 Ok(())
1257 }
1258 fn retain(mut self, ws: &mut Workspace) {
1259 if ws.retention() == crate::Retention::Lean {
1263 self.q = Vec::new();
1264 }
1265 if let Some(mut unused) = ws.simplify.take() {
1266 if self.a.capacity() == 0 {
1267 self.a = core::mem::take(&mut unused.a);
1268 }
1269 if self.aq.capacity() == 0 {
1270 self.aq = core::mem::take(&mut unused.aq);
1271 }
1272 if self.g.capacity() == 0 {
1273 self.g = core::mem::take(&mut unused.g);
1274 }
1275 if self.vg.capacity() == 0 {
1276 self.vg = core::mem::take(&mut unused.vg);
1277 }
1278 if self.sparse.capacity() == 0 {
1279 self.sparse = core::mem::take(&mut unused.sparse);
1280 }
1281 if self.original.capacity() == 0 {
1282 self.original = core::mem::take(&mut unused.original);
1283 }
1284 }
1285 ws.has_retained = true;
1286 ws.simplify = Some(self);
1287 }
1288 fn empty() -> Self {
1289 Self {
1290 vertex_count: 0,
1291 sqrt_cache: SqrtCache::new(),
1292 offsets: Indices(Vec::new()),
1293 edges: Vec::new(),
1294 remap: Indices(Vec::new()),
1295 wedge: Indices(Vec::new()),
1296 kind: Vec::new(),
1297 forward: Indices(Vec::new()),
1298 back: Indices(Vec::new()),
1299 p: Vec::new(),
1300 a: Vec::new(),
1301 q: Vec::new(),
1302 aq: Vec::new(),
1303 g: Vec::new(),
1304 vg: Vec::new(),
1305 sparse: Vec::new(),
1306 original: Vec::new(),
1307 clamped: false,
1308 collapses: Vec::new(),
1309 order: Indices(Vec::new()),
1310 cr: Indices(Vec::new()),
1311 locked: Vec::new(),
1312 table: Indices(Vec::new()),
1313 max_degree: 0,
1314 ac: 0,
1315 bytes: 0,
1316 }
1317 }
1318 fn new(
1319 n: usize,
1320 m: usize,
1321 ac: usize,
1322 ws: &mut Workspace,
1323 mut output: usize,
1324 solve: bool,
1325 original: &mut Vec<u32>,
1326 ) -> Result<Self, Error> {
1327 let na = n.checked_mul(ac).ok_or(Error::SizeOverflow)?;
1328 let buckets = n
1329 .checked_add(n / 4)
1330 .ok_or(Error::SizeOverflow)?
1331 .checked_next_power_of_two()
1332 .ok_or(Error::SizeOverflow)?;
1333 let mut state = ws.simplify.take().unwrap_or_else(Self::empty);
1334 let mut unused = Self::empty();
1337 if na == 0 {
1338 unused.a = core::mem::take(&mut state.a);
1339 unused.g = core::mem::take(&mut state.g);
1340 }
1341 if ac == 0 {
1342 unused.aq = core::mem::take(&mut state.aq);
1343 }
1344 if !solve || ac == 0 {
1345 unused.vg = core::mem::take(&mut state.vg);
1346 }
1347 unused.sparse = core::mem::take(&mut state.sparse);
1348 unused.original = core::mem::take(&mut state.original);
1349 if unused.capacity_bytes()? != 0 {
1350 ws.has_retained = true;
1351 ws.simplify = Some(unused);
1352 }
1353 let projected = (|| {
1359 let mut projected = output
1360 .checked_add(state.capacity_bytes()?)
1361 .ok_or(Error::SizeOverflow)?;
1362 for (capacity, needed, size) in [
1363 (state.offsets.0.capacity(), n + 1, 4),
1364 (state.edges.capacity(), m, core::mem::size_of::<Edge>()),
1365 (state.remap.0.capacity(), n, 4),
1366 (state.wedge.0.capacity(), n, 4),
1367 (state.kind.capacity(), n, 1),
1368 (state.forward.0.capacity(), n, 4),
1369 (state.back.0.capacity(), n, 4),
1370 (state.p.capacity(), n, core::mem::size_of::<V>()),
1371 (state.a.capacity(), na, 4),
1372 (state.q.capacity(), n, core::mem::size_of::<Q>()),
1373 (
1374 state.aq.capacity(),
1375 if ac > 0 { n } else { 0 },
1376 core::mem::size_of::<Q>(),
1377 ),
1378 (state.g.capacity(), na, core::mem::size_of::<G>()),
1379 (state.cr.0.capacity(), n, 4),
1380 (state.locked.capacity(), n, 1),
1381 (state.table.0.capacity(), buckets, 4),
1382 ] {
1383 projected = projected
1384 .checked_add(checked_bytes(needed.saturating_sub(capacity), size)?)
1385 .ok_or(Error::SizeOverflow)?;
1386 }
1387 Ok::<_, Error>(projected)
1388 })();
1389 if projected.is_ok_and(|bytes| bytes > ws.limits().max_bytes) {
1390 let old = checked_bytes(original.capacity(), 4)?;
1391 crate::workspace::shrink(original, true)?;
1392 let released = old - checked_bytes(original.capacity(), 4)?;
1393 output -= released;
1394 if projected.is_ok_and(|bytes| bytes - released > ws.limits().max_bytes) {
1395 state = Self::empty();
1396 }
1397 }
1398 let bytes = output
1399 .checked_add(state.capacity_bytes()?)
1400 .ok_or(Error::SizeOverflow)?;
1401 let lean = ws.retention() == crate::Retention::Lean;
1402 let mut b = Budget::new(ws, bytes);
1403 b.reuse(&mut state.offsets.0, n + 1)?;
1404 b.reuse(&mut state.edges, m)?;
1405 state.remap.0.clear();
1406 b.reuse_capacity(&mut state.remap.0, n)?;
1407 state.wedge.0.clear();
1408 b.reuse_capacity(&mut state.wedge.0, n)?;
1409 b.reuse(&mut state.kind, n)?;
1410 state.kind.fill(MAN);
1411 b.reuse(&mut state.forward.0, n)?;
1412 state.forward.fill(NONE);
1413 b.reuse(&mut state.back.0, n)?;
1414 state.back.fill(NONE);
1415 state.p.clear();
1416 b.reuse_capacity(&mut state.p, n)?;
1417 b.reuse(&mut state.a, na)?;
1418 if lean {
1419 state.q.clear();
1421 b.reuse(&mut state.q, n)?;
1422 } else {
1423 b.reuse(&mut state.q, n)?;
1424 state.q.fill(Q::default());
1425 }
1426 b.reuse(&mut state.aq, if ac > 0 { n } else { 0 })?;
1427 state.aq.fill(Q::default());
1428 b.reuse(&mut state.g, na)?;
1429 state.g.fill(G::default());
1430 state.vg.clear();
1431 state.sparse.clear();
1432 state.original.clear();
1433 state.collapses.clear();
1434 state.order.0.clear();
1435 b.reuse(&mut state.cr.0, n)?;
1436 b.reuse(&mut state.locked, n)?;
1437 state.locked.fill(false);
1438 b.reuse(&mut state.table.0, buckets)?;
1439 state.table.fill(NONE);
1440 state.ac = ac;
1441 state.vertex_count = n;
1442 state.clamped = false;
1443 state.max_degree = 0;
1444 state.bytes = b.bytes;
1445 Ok(state)
1446 }
1447 fn adjacency<const WELD: bool>(
1448 &mut self,
1449 indices: &[u32],
1450 work: &mut impl Meter,
1451 ) -> Result<(), Error> {
1452 work.add(self.vertex_count)?;
1453 self.offsets.fill(0);
1454 let n = self.vertex_count;
1455 let counters = &mut self.offsets.0[1..][..n];
1456 let remap = &self.remap.0[..if WELD { n } else { 0 }];
1457 let edges = &mut self.edges[..indices.len()];
1458 work.scan(indices.iter().copied(), |i| {
1459 let v = if WELD {
1460 remap[i as usize] as usize
1461 } else {
1462 i as usize
1463 };
1464 counters[v] += 1;
1465 Ok(())
1466 })?;
1467 let mut offset = 0;
1468 let mut max_degree = 0;
1469 for v in counters.iter_mut() {
1470 let count = *v;
1471 *v = offset;
1472 offset += count;
1473 max_degree = max_degree.max(count);
1474 }
1475 self.max_degree = max_degree as usize;
1476 let triangles = indices.as_chunks::<3>().0;
1477 let charged = work.precharge(triangles.len(), 3)?;
1478 for t in triangles {
1479 if !charged {
1480 work.add(3)?;
1481 }
1482 let mut v = [t[0] as usize, t[1] as usize, t[2] as usize];
1483 if WELD {
1484 for x in &mut v {
1485 *x = remap[*x] as usize;
1486 }
1487 }
1488 for e in 0..3 {
1489 let a = v[e];
1490 let offset = &mut counters[a];
1491 edges[*offset as usize] = Edge {
1492 next: v[(e + 1) % 3] as u32,
1493 prev: v[(e + 2) % 3] as u32,
1494 };
1495 *offset += 1;
1496 }
1497 }
1498 Ok(())
1499 }
1500 fn has_edge<const WELD: bool, M: Meter>(
1501 &self,
1502 a: usize,
1503 b: usize,
1504 work: &mut M,
1505 ) -> Result<bool, Error> {
1506 let mut v = a;
1507 loop {
1508 for e in &self.edges[self.offsets.get(v)..self.offsets.get(v + 1)] {
1509 work.add(1)?;
1510 if if WELD {
1511 self.remap.get(e.next as usize) == self.remap.get(b)
1512 } else {
1513 e.next as usize == b
1514 } {
1515 return Ok(true);
1516 }
1517 }
1518 if !WELD {
1519 break;
1520 }
1521 v = self.wedge.get(v);
1522 if v == a {
1523 break;
1524 }
1525 }
1526 Ok(false)
1527 }
1528 fn position_remap(
1529 &mut self,
1530 p: Positions<'_>,
1531 work: &mut Work,
1532 ) -> Result<([f32; 3], [f32; 3]), Error> {
1533 if let Some((values, mapping)) = p.packed_source() {
1534 if let Some(mapping) = mapping {
1535 self.position_remap_kernel::<false>(
1536 mapping.len(),
1537 |i| Ok(values[mapping[i] as usize]),
1538 work,
1539 )
1540 } else {
1541 self.position_remap_kernel::<false>(values.len(), |i| Ok(values[i]), work)
1542 }
1543 } else if let Some(mut records) = p.scale_full_records() {
1544 self.position_remap_kernel::<true>(
1545 p.len(),
1546 |_| Ok(records.next().expect("validated position count")),
1547 work,
1548 )
1549 } else {
1550 self.position_remap_kernel::<true>(p.len(), |i| p.at(i), work)
1551 }
1552 }
1553 fn position_remap_kernel<const CACHE_POSITIONS: bool>(
1554 &mut self,
1555 count: usize,
1556 mut read: impl FnMut(usize) -> Result<[f32; 3], Error>,
1557 work: &mut Work,
1558 ) -> Result<([f32; 3], [f32; 3]), Error> {
1559 let mask = self.table.len() - 1;
1560 self.remap.0.resize(count, 0);
1564 self.wedge.0.resize(count, 0);
1565 if CACHE_POSITIONS {
1566 self.p.resize(count, V::default());
1567 }
1568 let remap = &mut self.remap.0[..count];
1569 let wedge = &mut self.wedge.0[..count];
1570 let positions = &mut self.p[..if CACHE_POSITIONS { count } else { 0 }];
1571 let table = &mut self.table.0[..];
1572 let mut lo = [f32::MAX; 3];
1573 let mut hi = [-f32::MAX; 3];
1574 for start in (0..count).step_by(64) {
1577 let end = count.min(start.saturating_add(64));
1578 let bound = (end - start).checked_mul(mask + 2);
1579 metered!(work, bound, |work| (|| {
1580 for i in start..end {
1581 work.add(1)?;
1582 let v = read(i)?;
1583 for j in 0..3 {
1587 if lo[j] > v[j] {
1588 lo[j] = v[j];
1589 }
1590 if hi[j] < v[j] {
1591 hi[j] = v[j];
1592 }
1593 }
1594 if CACHE_POSITIONS {
1600 positions[i] = V::from(v);
1601 }
1602 let mut bits = v.map(|v| match v.to_bits() {
1603 0x8000_0000 => 0,
1604 bits => bits,
1605 });
1606 for x in &mut bits {
1607 *x ^= *x >> 17;
1608 }
1609 let hash = bits[0].wrapping_mul(73856093)
1610 ^ bits[1].wrapping_mul(19349663)
1611 ^ bits[2].wrapping_mul(83492791);
1612 let mut bucket = hash as usize & mask;
1613 for probe in 0..=mask {
1614 work.add(1)?;
1615 let j = table[bucket] as usize;
1616 if j == NONE {
1617 table[bucket] = i as u32;
1618 break;
1619 }
1620 let candidate = if CACHE_POSITIONS {
1621 let p = positions[j];
1622 [p.x, p.y, p.z]
1623 } else {
1624 read(j)?
1625 };
1626 if candidate == v {
1627 break;
1628 }
1629 bucket = (bucket + probe + 1) & mask;
1630 }
1631 remap[i] = table[bucket];
1632 wedge[i] = i as u32;
1633 }
1634 Ok(())
1635 })())?;
1636 }
1637 self.bytes -= self.table.0.capacity() * core::mem::size_of::<u32>();
1638 self.table.0 = Vec::new();
1639 let wedge = &mut self.wedge.0[..count];
1640 work.scan(self.remap.0[..count].iter().enumerate(), |(i, &r)| {
1641 let r = r as usize;
1642 if r != i {
1643 wedge[i] = wedge[r];
1644 wedge[r] = i as u32;
1645 }
1646 Ok(())
1647 })?;
1648 Ok((lo, hi))
1649 }
1650 fn classify_work(&self, edges: usize, options: SimplifyOptions) -> Option<usize> {
1654 if options.contains(SimplifyOptions::PERMISSIVE) {
1655 return None;
1656 }
1657 edges
1658 .checked_mul(self.max_degree.checked_add(1)?)?
1659 .checked_add(self.vertex_count.checked_mul(5)?)
1660 }
1661 fn classify<M: Meter>(
1662 &mut self,
1663 flags: Option<&[VertexFlags]>,
1664 options: SimplifyOptions,
1665 work: &mut M,
1666 ) -> Result<(), Error> {
1667 let n = self.vertex_count;
1668 let offsets = &self.offsets.0[..n + 1];
1671 let edges = &self.edges[..];
1672 let forward = &mut self.forward.0[..n];
1673 let back = &mut self.back.0[..n];
1674 for (i, range) in offsets.windows(2).enumerate() {
1675 work.add(1)?;
1676 for edge in &edges[range[0] as usize..range[1] as usize] {
1677 work.add(1)?;
1678 let t = edge.next as usize;
1679 if t == i {
1680 forward[i] = i as u32;
1681 back[i] = i as u32;
1682 } else {
1683 let mut opposite = false;
1684 for edge in &edges[offsets[t] as usize..offsets[t + 1] as usize] {
1685 work.add(1)?;
1686 if edge.next as usize == i {
1687 opposite = true;
1688 break;
1689 }
1690 }
1691 if !opposite {
1692 back[t] = if back[t] as usize == NONE { i } else { t } as u32;
1693 forward[i] = if forward[i] as usize == NONE { t } else { i } as u32;
1694 }
1695 }
1696 }
1697 }
1698 let remap = &self.remap.0[..n];
1699 let wedge = &self.wedge.0[..n];
1700 let kind = &mut self.kind[..n];
1701 for i in 0..n {
1702 work.add(1)?;
1703 kind[i] = if remap[i] as usize != i {
1704 kind[remap[i] as usize]
1705 } else if wedge[i] as usize == i {
1706 let a = back[i] as usize;
1707 let b = forward[i] as usize;
1708 if a == NONE && b == NONE {
1709 MAN
1710 } else if a != NONE && b != NONE && remap[a] == remap[b] && a != i {
1711 SEAM
1712 } else if a != i && b != i {
1713 BORDER
1714 } else {
1715 LOCKED
1716 }
1717 } else if wedge[wedge[i] as usize] as usize == i {
1718 let w = wedge[i] as usize;
1719 let a = back[i] as usize;
1720 let b = forward[i] as usize;
1721 let c = back[w] as usize;
1722 let d = forward[w] as usize;
1723 if a != NONE
1724 && a != i
1725 && b != NONE
1726 && b != i
1727 && c != NONE
1728 && c != w
1729 && d != NONE
1730 && d != w
1731 && remap[a] == remap[d]
1732 && remap[b] == remap[c]
1733 && remap[a] != remap[b]
1734 {
1735 SEAM
1736 } else {
1737 LOCKED
1738 }
1739 } else {
1740 LOCKED
1741 };
1742 }
1743 if options.contains(SimplifyOptions::PERMISSIVE) {
1744 for i in 0..n {
1745 work.add(1)?;
1746 if self.kind[i] != SEAM && self.kind[i] != LOCKED {
1747 continue;
1748 }
1749 if self.remap.get(i) != i {
1750 self.kind[i] = self.kind[self.remap.get(i)];
1751 continue;
1752 }
1753 let mut protect = false;
1754 let mut border = false;
1755 let mut v = i;
1756 loop {
1757 work.add(1)?;
1758 protect |= flag(flags, v, VertexFlags::PROTECT);
1759 for j in self.offsets.get(v)..self.offsets.get(v + 1) {
1760 work.add(1)?;
1761 border |=
1762 !self.has_edge::<true, M>(self.edges[j].next as usize, v, work)?;
1763 }
1764 v = self.wedge.get(v);
1765 if v == i {
1766 break;
1767 }
1768 }
1769 if !protect {
1770 self.kind[i] = if border { FRINGE } else { COMPLEX };
1771 }
1772 }
1773 }
1774 if let Some(flags) = flags {
1775 for (i, &f) in flags.iter().enumerate() {
1776 work.add(1)?;
1777 if f.contains(VertexFlags::LOCK) {
1778 self.kind[self.remap.get(i)] = LOCKED;
1779 }
1780 }
1781 for i in 0..n {
1782 work.add(1)?;
1783 if self.kind[self.remap.get(i)] == LOCKED {
1784 self.kind[i] = LOCKED;
1785 }
1786 }
1787 }
1788 if options.contains(SimplifyOptions::LOCK_BORDER) {
1789 for k in &mut self.kind {
1790 work.add(1)?;
1791 if *k == BORDER || *k == FRINGE {
1792 *k = LOCKED;
1793 }
1794 }
1795 }
1796 Ok(())
1797 }
1798}
1799fn flag(flags: Option<&[VertexFlags]>, i: usize, f: VertexFlags) -> bool {
1800 flags.is_some_and(|flags| flags[i].contains(f))
1801}
1802#[inline(always)]
1803fn attribute_gradient(q: &mut Q, values: [f32; 3], p0: V, basis: [V; 2], w: f32) -> G {
1804 let [a0, a1, a2] = values;
1805 let gx = basis[0].x * (a1 - a0) + basis[1].x * (a2 - a0);
1806 let gy = basis[0].y * (a1 - a0) + basis[1].y * (a2 - a0);
1807 let gz = basis[0].z * (a1 - a0) + basis[1].z * (a2 - a0);
1808 let gw = a0 - p0.x * gx - p0.y * gy - p0.z * gz;
1809 q.a00 += w * (gx * gx);
1810 q.a11 += w * (gy * gy);
1811 q.a22 += w * (gz * gz);
1812 q.a10 += w * (gy * gx);
1813 q.a20 += w * (gz * gx);
1814 q.a21 += w * (gz * gy);
1815 q.b0 += w * (gx * gw);
1816 q.b1 += w * (gy * gw);
1817 q.b2 += w * (gz * gw);
1818 q.c += w * (gw * gw);
1819 G {
1820 x: w * gx,
1821 y: w * gy,
1822 z: w * gz,
1823 w: w * gw,
1824 }
1825}
1826fn record_triplet<T>(
1827 records: &mut [T],
1828 width: usize,
1829 indices: [usize; 3],
1830) -> Option<[&mut [T]; 3]> {
1831 let [a, b, c] = indices;
1832 if a == b || a == c || b == c {
1833 return None;
1834 }
1835 records
1836 .get_disjoint_mut([
1837 a * width..(a + 1) * width,
1838 b * width..(b + 1) * width,
1839 c * width..(c + 1) * width,
1840 ])
1841 .ok()
1842}
1843impl State {
1844 fn attribute_quadric(&mut self, t: [usize; 3]) -> Q {
1845 let [i0, i1, i2] = t;
1846 let p0 = self.p[i0];
1847 let v0 = self.p[i1].sub(p0);
1848 let v1 = self.p[i2].sub(p0);
1849 let normal = v0.cross(v1);
1850 let w = self.sqrt_cache.sqrt(normal.dot(normal)) * 0.5;
1851 let d00 = v0.dot(v0);
1852 let d01 = v0.dot(v1);
1853 let d11 = v1.dot(v1);
1854 let denom = d00 * d11 - d01 * d01;
1855 let dr = if denom == 0.0 { 0.0 } else { 1.0 / denom };
1856 let gx1 = (d11 * v0.x - d01 * v1.x) * dr;
1857 let gx2 = (d00 * v1.x - d01 * v0.x) * dr;
1858 let gy1 = (d11 * v0.y - d01 * v1.y) * dr;
1859 let gy2 = (d00 * v1.y - d01 * v0.y) * dr;
1860 let gz1 = (d11 * v0.z - d01 * v1.z) * dr;
1861 let gz2 = (d00 * v1.z - d01 * v0.z) * dr;
1862 let mut q = Q { w, ..Q::default() };
1863 let attributes0 = &self.a[i0 * self.ac..][..self.ac];
1864 let attributes1 = &self.a[i1 * self.ac..][..self.ac];
1865 let attributes2 = &self.a[i2 * self.ac..][..self.ac];
1866 let basis = [
1867 V {
1868 x: gx1,
1869 y: gy1,
1870 z: gz1,
1871 },
1872 V {
1873 x: gx2,
1874 y: gy2,
1875 z: gz2,
1876 },
1877 ];
1878 if let Some([g0, g1, g2]) = record_triplet(&mut self.g, self.ac, t) {
1879 for (((&a0, &a1), &a2), ((g0, g1), g2)) in attributes0
1880 .iter()
1881 .zip(attributes1)
1882 .zip(attributes2)
1883 .zip(g0.iter_mut().zip(g1).zip(g2))
1884 {
1885 let g = attribute_gradient(&mut q, [a0, a1, a2], p0, basis, w);
1886 g0.add(g);
1887 g1.add(g);
1888 g2.add(g);
1889 }
1890 } else {
1891 for (k, ((&a0, &a1), &a2)) in attributes0
1892 .iter()
1893 .zip(attributes1)
1894 .zip(attributes2)
1895 .enumerate()
1896 {
1897 let g = attribute_gradient(&mut q, [a0, a1, a2], p0, basis, w);
1898 for i in t {
1899 self.g[i * self.ac + k].add(g);
1900 }
1901 }
1902 }
1903 q
1904 }
1905 fn quadrics<M: Meter>(
1906 &mut self,
1907 indices: &[u32],
1908 flags: Option<&[VertexFlags]>,
1909 options: SimplifyOptions,
1910 work: &mut M,
1911 ) -> Result<(), Error> {
1912 let n = self.p.len();
1913 let p = &self.p[..n];
1914 let remap = &self.remap.0[..n];
1915 let qv = &mut self.q[..n];
1916 let kind = &self.kind[..n];
1917 let forward = &self.forward.0[..n];
1918 let back = &self.back.0[..n];
1919 let triangles = indices.as_chunks::<3>().0;
1920 let charged = work.precharge(triangles.len(), 3)?;
1921 for t in triangles {
1922 if !charged {
1923 work.add(3)?;
1924 }
1925 let [a, b, c] = [t[0] as usize, t[1] as usize, t[2] as usize];
1926 let mut normal = p[b].sub(p[a]).cross(p[c].sub(p[a]));
1927 let area = normal.normalize(&mut self.sqrt_cache);
1928 let q = Q::plane(normal, -normal.dot(p[a]), self.sqrt_cache.sqrt(area) * 1.0);
1929 for i in [a, b, c] {
1930 qv[remap[i] as usize].add(q);
1931 }
1932 if !self.vg.is_empty() {
1933 let area = area * 0.5;
1935 let g = G {
1936 x: normal.x * area,
1937 y: normal.y * area,
1938 z: normal.z * area,
1939 w: (-p[a].x * normal.x - p[a].y * normal.y - p[a].z * normal.z) * area,
1940 };
1941 for i in [a, b, c] {
1942 self.vg[remap[i] as usize].add(g);
1943 }
1944 }
1945 }
1946 let factor = if options.contains(SimplifyOptions::REGULARIZE_LIGHT) {
1947 1e-2
1948 } else if options.contains(SimplifyOptions::REGULARIZE) {
1949 1e-1
1950 } else {
1951 1e-7
1952 };
1953 work.scan(
1954 qv.iter_mut().zip(p).zip(remap).enumerate(),
1955 |(i, ((q, &position), &r))| {
1956 if r as usize == i {
1957 let w = q.w
1958 * if flag(flags, i, VertexFlags::PRIORITY) {
1959 1.0
1960 } else {
1961 factor
1962 };
1963 q.add(Q::point(position, w));
1964 }
1965 Ok(())
1966 },
1967 )?;
1968 let charged_edges = work.precharge(indices.len(), 1)?;
1969 for t in indices.as_chunks::<3>().0 {
1970 for e in 0..3 {
1971 if !charged_edges {
1972 work.add(1)?;
1973 }
1974 let a = t[e] as usize;
1975 let b = t[(e + 1) % 3] as usize;
1976 let c = t[(e + 2) % 3] as usize;
1977 let k0 = kind[a];
1978 let k1 = kind[b];
1979 if k0 == MAN || k1 == MAN {
1980 continue;
1981 }
1982 if !matches!(k0, BORDER | SEAM | FRINGE) && !matches!(k1, BORDER | SEAM | FRINGE) {
1984 continue;
1985 }
1986 if (k0 == BORDER || k0 == SEAM) && forward[a] as usize != b {
1987 continue;
1988 }
1989 if (k1 == BORDER || k1 == SEAM) && back[b] as usize != a {
1990 continue;
1991 }
1992 if (k0 == FRINGE || k1 == FRINGE) && (k0 == COMPLEX || k1 == COMPLEX) {
1993 continue;
1994 }
1995 let w = if k0 == SEAM || k1 == SEAM { 0.5 } else { 10.0 };
1996 let mut q = Q::edge(p[a], p[b], p[c], w, &mut self.sqrt_cache);
1997 let mut qt = Q::triangle(p[a], p[b], p[c], w, &mut self.sqrt_cache);
1998 qt.w = 0.0;
1999 q.add(qt);
2000 qv[remap[a] as usize].add(q);
2001 qv[remap[b] as usize].add(q);
2002 }
2003 }
2004 if self.ac > 0 {
2005 let units = 3 + self.ac * 3;
2006 let charged = work.precharge(triangles.len(), units)?;
2007 for t in triangles {
2008 if !charged {
2009 work.add(units)?;
2010 }
2011 let t = [t[0] as usize, t[1] as usize, t[2] as usize];
2012 let q = self.attribute_quadric(t);
2013 for i in t {
2014 self.aq[i].add(q);
2015 }
2016 }
2017 }
2018 if options.bits() & 128 != 0 {
2019 extra::fold_quadrics(self, work)?;
2020 }
2021 for q in &mut self.q {
2025 q.cache_inverse_weight();
2026 }
2027 let aq = self.aq.iter().fold([0.0f32; 12], |mut m, q| {
2036 let f = q.fields();
2037 let f = [
2038 f[0], f[1], f[2], f[3], f[4], f[5], f[6], f[7], f[8], f[9], f[10], 0.0,
2039 ];
2040 for (m, x) in m.iter_mut().zip(f) {
2041 *m += x * 0.0;
2042 }
2043 m
2044 });
2045 let g = self.g.iter().fold([0.0f32; 4], |mut m, g| {
2046 for (m, x) in m.iter_mut().zip([g.x, g.y, g.z, g.w]) {
2047 *m += x * 0.0;
2048 }
2049 m
2050 });
2051 if aq.into_iter().chain(g).any(|lane| lane.is_nan()) {
2052 return Err(Error::NumericalFailure);
2053 }
2054 Ok(())
2055 }
2056 fn pick<M: Meter>(
2058 &mut self,
2059 indices: &[u32],
2060 capacity: usize,
2061 work: &mut M,
2062 ) -> Result<usize, Error> {
2063 let mut count = 0;
2064 let n = self.vertex_count;
2068 let remap = &self.remap.0[..n];
2069 let kind = &self.kind[..n];
2070 let forward = &self.forward.0[..n];
2071 let back = &self.back.0[..n];
2072 let collapses = &mut self.collapses;
2073 collapses.clear();
2074 let mut entered = 0;
2077 for t in indices.as_chunks::<3>().0 {
2078 if count + 3 > capacity {
2079 break;
2080 }
2081 entered += 1;
2082 for e in 0..3 {
2083 if !M::PREPAID {
2084 work.add(1)?;
2085 }
2086 let a = t[e] as usize;
2087 let b = t[(e + 1) % 3] as usize;
2088 let ra = remap[a];
2089 let rb = remap[b];
2090 if ra == rb {
2091 continue;
2092 }
2093 let rule = PICK[pair(kind[a], kind[b])];
2094 if rule & PICK_ANY == 0 {
2095 continue;
2096 }
2097 if rule & PICK_OPPOSITE != 0 && rb > ra {
2098 continue;
2099 }
2100 if rule & PICK_CHECK_FORWARD != 0 && forward[a] as usize != b {
2101 continue;
2102 }
2103 if rule & PICK_CHECK_BACK != 0 && back[b] as usize != a {
2104 continue;
2105 }
2106 collapses.push(if rule & PICK_BOTH != 0 {
2107 Collapse {
2108 a: a as u32,
2109 b: b as u32,
2110 error: f32::from_bits(1),
2111 }
2112 } else if rule & PICK_FORWARD != 0 {
2113 Collapse {
2114 a: a as u32,
2115 b: b as u32,
2116 ..Collapse::default()
2117 }
2118 } else {
2119 Collapse {
2120 a: b as u32,
2121 b: a as u32,
2122 ..Collapse::default()
2123 }
2124 });
2125 count += 1;
2126 }
2127 }
2128 if M::PREPAID {
2129 work.add(entered * 3)?;
2130 }
2131 Ok(count)
2132 }
2133 fn complex_target(&self, v: usize, t: usize) -> usize {
2134 let r = self.remap.get(t);
2135 if self.forward.get(v) != NONE && self.remap.get(self.forward.get(v)) == r {
2136 self.forward.get(v)
2137 } else if self.back.get(v) != NONE && self.remap.get(self.back.get(v)) == r {
2138 self.back.get(v)
2139 } else {
2140 t
2141 }
2142 }
2143 fn seam_target(&self, a: usize, b: usize) -> (usize, usize) {
2144 let s0 = self.wedge.get(a);
2145 let s1 = if self.forward.get(a) == b {
2146 self.back.get(s0)
2147 } else {
2148 self.forward.get(s0)
2149 };
2150 (s0, if s1 != NONE { s1 } else { self.wedge.get(b) })
2151 }
2152 fn rank(&mut self, count: usize, work: &mut Work) -> Result<(), Error> {
2153 if self.ac == 0 {
2154 let n = self.p.len();
2157 let p = &self.p[..n];
2158 let q = &self.q[..n];
2159 let remap = &self.remap.0[..n];
2160 #[inline(always)]
2161 fn rank_one(c: &mut Collapse, p: &[V], q: &[Q], remap: &[u32]) -> Result<(), Error> {
2162 let a = c.a as usize;
2163 let b = c.b as usize;
2164 let bidirectional = c.error.to_bits() != 0;
2165 let ei = q[remap[a] as usize].error(p[b]);
2166 let ej = if bidirectional {
2167 q[remap[b] as usize].error(p[a])
2168 } else {
2169 f32::MAX
2170 };
2171 if !(ei.is_finite() & ej.is_finite()) {
2172 return Err(Error::NumericalFailure);
2173 }
2174 if bidirectional && ej < ei {
2175 core::mem::swap(&mut c.a, &mut c.b);
2176 }
2177 c.error = if ej < ei { ej } else { ei };
2178 Ok(())
2179 }
2180 let values = &mut self.collapses[..count];
2181 return if work.covers(count)? {
2182 for (i, c) in values.iter_mut().enumerate() {
2183 if let Err(error) = rank_one(c, p, q, remap) {
2184 work.add(i + 1)?;
2185 return Err(error);
2186 }
2187 }
2188 work.add(count)
2189 } else {
2190 for c in values {
2191 work.add(1)?;
2192 rank_one(c, p, q, remap)?;
2193 }
2194 Ok(())
2195 };
2196 }
2197 let per_candidate = self
2200 .vertex_count
2201 .checked_add(1)
2202 .and_then(|n| self.ac.checked_mul(2)?.checked_mul(n))
2203 .and_then(|n| n.checked_add(1));
2204 for start in (0..count).step_by(64) {
2205 let end = count.min(start.saturating_add(64));
2206 let bound = per_candidate.and_then(|n| n.checked_mul(end - start));
2207 metered!(work, bound, |w| self.rank_attributes(start..end, w))?;
2208 }
2209 Ok(())
2210 }
2211 fn rank_attributes<M: Meter>(
2212 &mut self,
2213 range: core::ops::Range<usize>,
2214 work: &mut M,
2215 ) -> Result<(), Error> {
2216 for i in range {
2217 work.add(1)?;
2218 let c = self.collapses[i];
2219 let a = c.a as usize;
2220 let b = c.b as usize;
2221 let mut ei = self.q[self.remap.get(a)].error(self.p[b]);
2222 let mut ej = if c.error.to_bits() != 0 {
2223 self.q[self.remap.get(b)].error(self.p[a])
2224 } else {
2225 f32::MAX
2226 };
2227 if self.ac > 0 {
2228 work.add(self.ac * 2)?;
2229 ei += self.attribute_error(a, b);
2230 ej += if c.error.to_bits() != 0 {
2231 self.attribute_error(b, a)
2232 } else {
2233 0.0
2234 };
2235 if self.kind[a] == SEAM {
2236 work.add(self.ac * 2)?;
2237 let (s0, s1) = self.seam_target(a, b);
2238 ei += self.attribute_error(s0, s1);
2239 ej += if c.error.to_bits() != 0 {
2240 self.attribute_error(s1, s0)
2241 } else {
2242 0.0
2243 };
2244 } else {
2245 if self.kind[a] == COMPLEX || self.kind[a] == FRINGE {
2246 let mut v = self.wedge.get(a);
2247 while v != a {
2248 work.add(self.ac)?;
2249 ei += self.attribute_error(v, self.complex_target(v, b));
2250 v = self.wedge.get(v);
2251 }
2252 }
2253 if (self.kind[b] == COMPLEX || self.kind[b] == FRINGE)
2254 && (c.error.to_bits() != 0)
2255 {
2256 let mut v = self.wedge.get(b);
2257 while v != b {
2258 work.add(self.ac)?;
2259 ej += self.attribute_error(v, self.complex_target(v, a));
2260 v = self.wedge.get(v);
2261 }
2262 }
2263 }
2264 }
2265 if !(ei.is_finite() & ej.is_finite()) {
2266 return Err(Error::NumericalFailure);
2267 }
2268 let rev = (c.error.to_bits() != 0) && ej < ei;
2269 self.collapses[i] = Collapse {
2270 a: (if rev { b } else { a }) as u32,
2271 b: (if rev { a } else { b }) as u32,
2272 error: if ej < ei { ej } else { ei },
2273 };
2274 }
2275 Ok(())
2276 }
2277 #[inline(always)]
2278 fn attribute_error(&self, source: usize, target: usize) -> f32 {
2279 let v = self.p[target];
2280 let q = self.aq[source];
2281 let mut r = q.eval(v);
2282 let attributes = &self.a[target * self.ac..][..self.ac];
2283 let gradients = &self.g[source * self.ac..][..self.ac];
2284 let term = |a: f32, g: G| {
2285 let g = v.x * g.x + v.y * g.y + v.z * g.z + g.w;
2286 a * (a * q.w - 2.0 * g)
2287 };
2288 let (a4, at) = attributes.as_chunks::<4>();
2289 let (g4, gt) = gradients.as_chunks::<4>();
2290 for (a, g) in a4.iter().zip(g4) {
2291 let terms = [
2294 term(a[0], g[0]),
2295 term(a[1], g[1]),
2296 term(a[2], g[2]),
2297 term(a[3], g[3]),
2298 ];
2299 for t in terms {
2300 r += t;
2301 }
2302 }
2303 for (&a, &g) in at.iter().zip(gt) {
2304 r += term(a, g);
2305 }
2306 let e = r.abs();
2307 if self.clamped && e >= q.w {
2308 q.w
2309 } else {
2310 e
2311 }
2312 }
2313 fn sort(&mut self, count: usize, work: &mut Work) -> Result<(), Error> {
2314 let mut h = [0u32; 2560];
2317 let collapses = &self.collapses[..count];
2318 work.scan(collapses.iter(), |c| {
2319 h[sort_key(c.error)] += 1;
2320 Ok(())
2321 })?;
2322 let mut sum = 0;
2323 for v in &mut h {
2324 let n = *v;
2325 *v = sum as u32;
2326 sum += n as usize;
2327 }
2328 let order = &mut self.order.0[..count];
2329 work.scan(collapses.iter().enumerate(), |(i, c)| {
2330 let k = sort_key(c.error);
2331 order[h[k] as usize] = i as u32;
2332 h[k] += 1;
2333 Ok(())
2334 })?;
2335 Ok(())
2336 }
2337 fn flips<M: Meter>(&mut self, a: usize, b: usize, work: &mut M) -> Result<bool, Error> {
2338 for e in &self.edges[self.offsets.get(a)..self.offsets.get(a + 1)] {
2339 work.add(1)?;
2340 let x = self.cr.get(e.next as usize);
2341 let y = self.cr.get(e.prev as usize);
2342 if x == b || y == b || x == y {
2343 continue;
2344 }
2345 let pa = self.p[x];
2346 let eb = self.p[y].sub(pa);
2347 let ec = self.p[a].sub(pa);
2348 let ed = self.p[b].sub(pa);
2349 let nbc = eb.cross(ec);
2350 let nbd = eb.cross(ed);
2351 if nbc.dot(nbd) <= 0.25 * self.sqrt_cache.sqrt(nbc.dot(nbc) * nbd.dot(nbd)) {
2352 return Ok(true);
2353 }
2354 }
2355 Ok(false)
2356 }
2357 fn perform_work(&self, count: usize, options: SimplifyOptions) -> Option<usize> {
2360 if options.contains(SimplifyOptions::PERMISSIVE) {
2361 return None;
2362 }
2363 count
2364 .checked_mul(self.max_degree.checked_add(1)?)?
2365 .checked_add(self.p.len())
2366 }
2367 fn perform<M: Meter>(
2368 &mut self,
2369 count: usize,
2370 goal: usize,
2371 limit: f32,
2372 error: &mut f32,
2373 work: &mut M,
2374 ) -> Result<(usize, bool), Error> {
2375 let n = self.p.len();
2376 let mut error_limited = false;
2377 work.scan(
2378 self.cr.0[..n]
2379 .iter_mut()
2380 .zip(&mut self.locked[..n])
2381 .enumerate(),
2382 |(i, (remap, locked))| {
2383 *remap = i as u32;
2384 *locked = false;
2385 Ok(())
2386 },
2387 )?;
2388 let mut edges = 0;
2389 let mut triangles = 0;
2390 let mut edge_goal = goal / 2;
2391 for i in 0..count {
2392 work.add(1)?;
2393 let c = self.collapses[self.order.get(i)];
2394 if c.error > limit || triangles >= goal {
2395 error_limited = c.error > limit && triangles < goal;
2396 break;
2397 }
2398 let error_goal = if edge_goal < count {
2399 1.5 * self.collapses[self.order.get(edge_goal)].error
2400 } else {
2401 f32::MAX
2402 };
2403 if c.error > error_goal && c.error > *error && triangles > goal / 6 {
2404 break;
2405 }
2406 let a = c.a as usize;
2407 let b = c.b as usize;
2408 let r0 = self.remap.get(a);
2409 let r1 = self.remap.get(b);
2410 let kind = self.kind[a];
2411 if self.locked[r0] || self.locked[r1] {
2412 continue;
2413 }
2414 if self.flips(r0, r1, work)? {
2415 edge_goal += 1;
2416 continue;
2417 }
2418 self.cr.set(a, b);
2419 if kind == COMPLEX || kind == FRINGE {
2420 let mut v = self.wedge.get(a);
2421 while v != a {
2422 work.add(1)?;
2423 self.cr.set(v, self.complex_target(v, b));
2424 v = self.wedge.get(v);
2425 }
2426 } else if kind == SEAM {
2427 let (s0, s1) = self.seam_target(a, b);
2428 self.cr.set(s0, s1);
2429 }
2430 self.locked[r0] = true;
2431 self.locked[r1] = true;
2432 triangles += if kind == BORDER { 1 } else { 2 };
2433 edges += 1;
2434 if *error < c.error {
2435 *error = c.error;
2436 }
2437 }
2438 Ok((edges, error_limited))
2439 }
2440 fn update<M: Meter>(&mut self, vertex_error: &mut f32, work: &mut M) -> Result<(), Error> {
2441 let n = self.p.len();
2442 let cr = &self.cr.0[..n];
2443 let remap = &self.remap.0[..n];
2444 if self.ac == 0 && self.vg.is_empty() {
2445 let quadrics = &mut self.q[..n];
2448 for (i, &target) in cr.iter().enumerate() {
2451 if !M::PREPAID {
2452 work.add(1)?;
2453 }
2454 let t = target as usize;
2455 if t == i {
2456 continue;
2457 }
2458 let r0 = remap[i] as usize;
2459 let r1 = remap[t] as usize;
2460 if i == r0 {
2461 let q = quadrics[r0];
2462 let destination = &mut quadrics[r1];
2463 destination.add(q);
2464 if !destination.finite() {
2465 if M::PREPAID {
2466 work.add(i + 1)?;
2467 }
2468 return Err(Error::NumericalFailure);
2469 }
2470 destination.cache_inverse_weight();
2471 }
2472 }
2473 if M::PREPAID {
2474 work.add(n)?;
2475 }
2476 } else {
2477 for i in 0..self.p.len() {
2478 work.add(1)?;
2479 let t = self.cr.get(i);
2480 if t == i {
2481 continue;
2482 }
2483 let r0 = self.remap.get(i);
2484 let r1 = self.remap.get(t);
2485 if i == r0 {
2486 let q = self.q[r0];
2487 self.q[r1].add(q);
2488 if !self.q[r1].finite() {
2489 return Err(Error::NumericalFailure);
2490 }
2491 self.q[r1].cache_inverse_weight();
2492 if !self.vg.is_empty() {
2493 let g = self.vg[r0];
2494 self.vg[r1].add(g);
2495 }
2496 }
2497 if self.ac > 0 {
2498 if i == r0 {
2499 let e = self.q[r0].error(self.p[r1]);
2500 if *vertex_error < e {
2501 *vertex_error = e;
2502 }
2503 }
2504 work.add(self.ac)?;
2505 let q = self.aq[i];
2506 self.aq[t].add(q);
2507 if !self.aq[t].finite() {
2508 return Err(Error::NumericalFailure);
2509 }
2510 for k in 0..self.ac {
2511 let g = self.g[i * self.ac + k];
2512 self.g[t * self.ac + k].add(g);
2513 }
2514 }
2515 }
2516 }
2517 if M::PREPAID {
2519 work.add(n * 2)?;
2520 }
2521 for loops in [&mut self.forward.0[..n], &mut self.back.0[..n]] {
2522 for i in 0..n {
2523 if !M::PREPAID {
2524 work.add(1)?;
2525 }
2526 let l = loops[i] as usize;
2527 if l != NONE {
2528 let r = cr[l] as usize;
2529 loops[i] = if i == r {
2530 let next = loops[l] as usize;
2531 if next != NONE {
2532 cr[next]
2533 } else {
2534 NONE as u32
2535 }
2536 } else {
2537 r as u32
2538 };
2539 }
2540 }
2541 }
2542 Ok(())
2543 }
2544}
2545fn sort_key(error: f32) -> usize {
2546 ((error.to_bits() << 1) >> 20).min(2559) as usize
2547}
2548#[allow(clippy::too_many_arguments)]
2549fn run(
2550 out: &mut [u32],
2551 indices: &[u32],
2552 positions: Positions<'_>,
2553 attributes: Option<Attributes<'_>>,
2554 weights: &[f32],
2555 flags: Option<&[VertexFlags]>,
2556 settings: SimplifySettings,
2557 ws: &mut Workspace,
2558 work: &mut Work,
2559 output: usize,
2560) -> Result<SimplifyResult, Error> {
2561 let (result, state, _) = run_state(
2562 out,
2563 Input::borrowed(indices),
2564 positions,
2565 attributes,
2566 weights,
2567 flags,
2568 settings,
2569 ws,
2570 work,
2571 output,
2572 false,
2573 )?;
2574 state.retain(ws);
2575 Ok(result)
2576}
2577#[inline(always)]
2580fn nonfinite(x: f32) -> u32 {
2581 u32::from(x.to_bits() & 0x7f80_0000 == 0x7f80_0000)
2582}
2583#[inline(always)]
2585fn any_nonfinite(values: &[f32]) -> bool {
2586 values.iter().fold(0, |a, &x| a | nonfinite(x)) != 0
2587}
2588fn first_nonfinite_vertex(positions: &[[f32; 3]], records: &[f32], width: usize) -> usize {
2592 if !any_nonfinite(positions.as_flattened()) && !any_nonfinite(records) {
2593 return positions.len();
2594 }
2595 (0..positions.len())
2596 .find(|&i| any_nonfinite(&positions[i]) || any_nonfinite(&records[i * width..][..width]))
2597 .unwrap_or(positions.len())
2598}
2599#[inline(always)]
2600fn prepaid<M: Meter>(_: &M) -> bool {
2601 M::PREPAID
2602}
2603#[allow(clippy::too_many_arguments)]
2609fn normalize_prefix(
2610 positions: &mut [V],
2611 attributes: &mut [f32],
2612 source: Option<&[[f32; 3]]>,
2613 records: &[f32],
2614 weights: &[f32],
2615 lo: [f32; 3],
2616 scale: f32,
2617 finite_scale: bool,
2618) -> usize {
2619 macro_rules! fixed {
2621 ($($w:literal)*) => {
2622 match weights.len() {
2623 $($w => {
2624 return normalize_rows::<$w>(
2625 positions, attributes, source, records, weights, lo, scale, finite_scale,
2626 )
2627 })*
2628 _ => {}
2629 }
2630 };
2631 }
2632 fixed!(1 2 3 4 5 6 7 8);
2633 let width = weights.len();
2634 for (i, destination) in positions.iter_mut().enumerate() {
2635 let normalized = normalized_position(source, i, destination, lo, scale);
2636 if !finite_scale && any_nonfinite(&[normalized.x, normalized.y, normalized.z]) {
2637 return i;
2638 }
2639 let values = &records[i * width..][..width];
2640 let bad = values
2641 .iter()
2642 .zip(weights)
2643 .fold(0, |bad, (&value, &weight)| bad | nonfinite(value * weight));
2644 if bad != 0 {
2645 return i;
2646 }
2647 *destination = normalized;
2648 let row = &mut attributes[i * width..][..width];
2649 for ((d, &value), &weight) in row.iter_mut().zip(values).zip(weights) {
2650 *d = value * weight;
2651 }
2652 }
2653 positions.len()
2654}
2655#[inline(always)]
2656fn normalized_position(
2657 source: Option<&[[f32; 3]]>,
2658 i: usize,
2659 cached: &V,
2660 lo: [f32; 3],
2661 scale: f32,
2662) -> V {
2663 let p = match source {
2664 Some(source) => source[i],
2665 None => [cached.x, cached.y, cached.z],
2666 };
2667 V {
2668 x: (p[0] - lo[0]) * scale,
2669 y: (p[1] - lo[1]) * scale,
2670 z: (p[2] - lo[2]) * scale,
2671 }
2672}
2673#[allow(clippy::too_many_arguments)]
2675fn normalize_rows<const W: usize>(
2676 positions: &mut [V],
2677 attributes: &mut [f32],
2678 source: Option<&[[f32; 3]]>,
2679 records: &[f32],
2680 weights: &[f32],
2681 lo: [f32; 3],
2682 scale: f32,
2683 finite_scale: bool,
2684) -> usize {
2685 let (Some(weights), (records, _), (rows, _)) = (
2686 weights.first_chunk::<W>(),
2687 records.as_chunks::<W>(),
2688 attributes.as_chunks_mut::<W>(),
2689 ) else {
2690 return 0;
2691 };
2692 for (i, destination) in positions.iter_mut().enumerate() {
2693 let normalized = normalized_position(source, i, destination, lo, scale);
2694 if !finite_scale && any_nonfinite(&[normalized.x, normalized.y, normalized.z]) {
2695 return i;
2696 }
2697 let values = records[i];
2698 let products: [f32; W] = core::array::from_fn(|k| values[k] * weights[k]);
2699 if any_nonfinite(&products) {
2700 return i;
2701 }
2702 *destination = normalized;
2703 rows[i] = products;
2704 }
2705 positions.len()
2706}
2707#[inline(always)]
2708fn normalize_attribute_row<M: Meter>(
2709 destination: &mut [f32],
2710 source: Attributes<'_>,
2711 vertex: usize,
2712 weights: &[f32],
2713 work: &mut M,
2714) -> Result<(), Error> {
2715 let mut write_generic = 0;
2716 if let Some(values) = source.float_record(vertex) {
2717 work.scan(values.iter().zip(weights), |(&value, &weight)| {
2718 if weight > 0.0 {
2719 let value = value * weight;
2720 if !value.is_finite() {
2721 return Err(Error::NumericalFailure);
2722 }
2723 destination[write_generic] = value;
2724 write_generic += 1;
2725 }
2726 Ok(())
2727 })?;
2728 } else {
2729 for (component, &weight) in weights.iter().enumerate() {
2730 work.add(1)?;
2731 if weight > 0.0 {
2732 let value = source.get(vertex, component).ok_or(Error::InvalidLayout)? * weight;
2733 if !value.is_finite() {
2734 return Err(Error::NumericalFailure);
2735 }
2736 destination[write_generic] = value;
2737 write_generic += 1;
2738 }
2739 }
2740 }
2741 Ok(())
2742}
2743
2744#[allow(clippy::too_many_arguments)]
2745fn run_state(
2746 out: &mut [u32],
2747 mut input: Input<'_>,
2748 positions: Positions<'_>,
2749 attributes: Option<Attributes<'_>>,
2750 weights: &[f32],
2751 flags: Option<&[VertexFlags]>,
2752 settings: SimplifySettings,
2753 ws: &mut Workspace,
2754 work: &mut Work,
2755 output: usize,
2756 solve: bool,
2757) -> Result<(SimplifyResult, State, PositionBounds), Error> {
2758 if settings.options.contains(SimplifyOptions::SPARSE) {
2759 return extra::sparse_run(
2760 out, input, positions, attributes, weights, flags, settings, ws, work, output, solve,
2761 );
2762 }
2763 let n = positions.len();
2764 let m = input.as_slice().len();
2765 let ac = weights.iter().filter(|&&w| w > 0.0).count();
2766 let dense = ac == weights.len();
2767 let mut s = State::new(n, m, ac, ws, output, solve, &mut input.original)?;
2768 s.clamped = settings.options.bits() & 256 != 0;
2769 if solve && ac > 0 {
2770 let requested = checked_bytes(n.saturating_sub(s.vg.capacity()), core::mem::size_of::<G>())
2771 .and_then(|added| s.bytes.checked_add(added).ok_or(Error::SizeOverflow));
2772 s.reclaim_for(ws, requested, &mut input.original)?;
2773 let mut b = Budget::new(ws, s.bytes);
2774 b.reuse(&mut s.vg, n)?;
2775 s.vg.fill(G::default());
2776 s.bytes = b.bytes;
2777 }
2778 metered!(work, m.checked_mul(2).and_then(|v| v.checked_add(n)), |w| s
2780 .adjacency::<false>(input.as_slice(), w))?;
2781 let (lo, hi) = s.position_remap(positions, work)?;
2782 metered!(work, s.classify_work(m, settings.options), |w| s.classify(
2783 flags,
2784 settings.options,
2785 w
2786 ))?;
2787 work.add(n)?;
2788 let mut extent = 0.0;
2791 if n != 0 {
2792 for j in 0..3 {
2793 let d = hi[j] - lo[j];
2794 if d >= extent {
2795 extent = d;
2796 }
2797 }
2798 }
2799 if !extent.is_finite() {
2800 return Err(Error::NumericalFailure);
2801 }
2802 let scale = if extent == 0.0 { 0.0 } else { 1.0 / extent };
2803 let finite_scale = scale.is_finite();
2808 let cached_positions = s.p.len() == n;
2809 if !cached_positions {
2810 s.p.resize(n, V::default());
2811 }
2812 let normalize_work = weights.len().checked_add(1).and_then(|v| n.checked_mul(v));
2814 metered!(work, normalize_work, |work| (|| {
2815 if let (false, true, None, Some(values)) = (
2820 cached_positions,
2821 finite_scale,
2822 attributes,
2823 positions.packed_values(),
2824 ) {
2825 if work.precharge(values.len(), 1)? {
2826 for (destination, p) in s.p.iter_mut().zip(values) {
2827 *destination = V {
2828 x: (p[0] - lo[0]) * scale,
2829 y: (p[1] - lo[1]) * scale,
2830 z: (p[2] - lo[2]) * scale,
2831 };
2832 }
2833 return Ok(());
2834 }
2835 }
2836 let mut start = 0;
2843 if prepaid(work) && dense {
2844 let source = positions.packed_values();
2845 if let Some(records) = attributes.and_then(|a| a.contiguous_floats()) {
2846 if cached_positions || source.is_some() {
2847 start = normalize_prefix(
2848 &mut s.p,
2849 &mut s.a,
2850 if cached_positions { None } else { source },
2851 records,
2852 weights,
2853 lo,
2854 scale,
2855 finite_scale,
2856 );
2857 work.add(start * (weights.len() + 1))?;
2858 }
2859 }
2860 }
2861 for (i, destination) in s.p.iter_mut().enumerate().skip(start) {
2862 work.add(1)?;
2863 let p = if cached_positions {
2864 let p = *destination;
2865 [p.x, p.y, p.z]
2866 } else {
2867 positions.at(i)?
2868 };
2869 let normalized = V {
2870 x: (p[0] - lo[0]) * scale,
2871 y: (p[1] - lo[1]) * scale,
2872 z: (p[2] - lo[2]) * scale,
2873 };
2874 *destination = normalized;
2875 if !finite_scale
2876 && ![destination.x, destination.y, destination.z]
2877 .iter()
2878 .fold(true, |finite, x| finite & x.is_finite())
2879 {
2880 return Err(Error::NumericalFailure);
2881 }
2882 if let Some(a) = attributes {
2883 normalize_attribute_row(&mut s.a[i * ac..(i + 1) * ac], a, i, weights, work)?;
2884 }
2885 }
2886 Ok(())
2887 })())?;
2888 let (components, component_errors) = if settings.options.contains(SimplifyOptions::PRUNE) {
2889 let requested = checked_bytes(n, 4)
2890 .and_then(|added| s.bytes.checked_add(added).ok_or(Error::SizeOverflow));
2891 s.reclaim_for(ws, requested, &mut input.original)?;
2892 let mut b = crate::budget::Budget::with_bytes(ws, s.bytes);
2893 let (c, nc) = extra::component_ids(&s.remap.0, input.as_slice(), &mut b, work)?;
2894 s.bytes = b.bytes();
2895 let requested = checked_bytes(nc, 16)
2896 .and_then(|added| s.bytes.checked_add(added).ok_or(Error::SizeOverflow));
2897 s.reclaim_for(ws, requested, &mut input.original)?;
2898 let mut b = crate::budget::Budget::with_bytes(ws, s.bytes);
2899 let errors = extra::component_errors(&s.p, &c, nc, &mut b, work)?;
2900 s.bytes = b.bytes();
2901 (c, errors)
2902 } else {
2903 (Vec::new(), Vec::new())
2904 };
2905 let quadric_work = if settings.options.bits() & 128 != 0 {
2908 None
2909 } else {
2910 m.checked_mul(2)
2911 .and_then(|v| v.checked_add(n))
2912 .and_then(|v| {
2913 if ac == 0 {
2914 Some(v)
2915 } else {
2916 ac.checked_add(1)
2917 .and_then(|a| m.checked_mul(a))
2918 .and_then(|a| v.checked_add(a))
2919 }
2920 })
2921 };
2922 metered!(work, quadric_work, |w| s.quadrics(
2923 input.as_slice(),
2924 flags,
2925 settings.options,
2926 w
2927 ))?;
2928 let mut dual = 0;
2929 work.scan(s.kind.iter().zip(s.offsets.0.windows(2)), |(&k, o)| {
2930 if k == MAN || k == SEAM {
2931 dual += o[1] as usize - o[0] as usize;
2932 }
2933 Ok(())
2934 })?;
2935 let capacity = m - dual / 2 + 3;
2936 let requested = (|| {
2937 let order_growth = checked_bytes(capacity.saturating_sub(s.order.0.capacity()), 4)?;
2938 let requested = s
2939 .bytes
2940 .checked_add(checked_bytes(
2941 capacity.saturating_sub(s.collapses.capacity()),
2942 core::mem::size_of::<Collapse>(),
2943 )?)
2944 .and_then(|n| n.checked_add(order_growth))
2945 .ok_or(Error::SizeOverflow)?;
2946 Ok::<_, Error>(requested)
2947 })();
2948 s.reclaim_for(ws, requested, &mut input.original)?;
2949 let lean = ws.retention() == crate::Retention::Lean;
2950 let mut budget = Budget::new(ws, s.bytes);
2951 budget.reuse_capacity(&mut s.collapses, capacity)?;
2952 if lean {
2953 budget.reuse_capacity(&mut s.order.0, capacity)?;
2955 } else {
2956 budget.reuse(&mut s.order.0, capacity)?;
2957 }
2958 let mut count = m;
2959 let mut error = 0.0;
2960 let mut vertex_error = 0.0;
2961 let mut component_next = 0.0;
2962 let error_scale = if settings.options.contains(SimplifyOptions::ERROR_ABSOLUTE) {
2963 extent
2964 } else {
2965 1.0
2966 };
2967 let limit = (settings.target_error * settings.target_error) / (error_scale * error_scale);
2968 work.add(m)?;
2969 out[..m].copy_from_slice(input.as_slice());
2970 while count > settings.target_index_count {
2971 metered!(
2972 work,
2973 count.checked_mul(2).and_then(|v| v.checked_add(n)),
2974 |w| s.adjacency::<true>(&out[..count], w)
2975 )?;
2976 let nc = metered!(work, Some(count), |w| s.pick(&out[..count], capacity, w))?;
2981 if nc == 0 {
2982 break;
2983 }
2984 if lean {
2987 s.order.0.resize(nc, 0);
2988 }
2989 s.rank(nc, work)?;
2990 s.sort(nc, work)?;
2991 let goal = (count - settings.target_index_count) / 3;
2992 let (edges, error_limited) = metered!(work, s.perform_work(nc, settings.options), |w| s
2993 .perform(nc, goal, limit, &mut error, w))?;
2994 if edges == 0 {
2995 ws.lod_error_limited = error_limited;
2996 break;
2997 }
2998 if ac == 0 {
2999 vertex_error = error;
3000 }
3001 let update_work = ac.checked_add(3).and_then(|v| n.checked_mul(v));
3003 metered!(work, update_work, |w| s.update(&mut vertex_error, w))?;
3004 let cr = &s.cr.0[..n];
3005 let remap = &s.remap.0[..n];
3006 let write_generic = metered!(work, Some(count), |w| (|| {
3007 let out = &mut out[..count];
3008 let mut write_generic = 0;
3009 let charged = w.precharge(count / 3, 3)?;
3012 for i in 0..count / 3 {
3013 if !charged {
3014 w.add(3)?;
3015 }
3016 let [a, b, c] = out.as_chunks::<3>().0[i];
3019 let a = cr[a as usize] as usize;
3020 let b = cr[b as usize] as usize;
3021 let c = cr[c as usize] as usize;
3022 let r0 = remap[a];
3023 let r1 = remap[b];
3024 let r2 = remap[c];
3025 if r0 != r1 && r0 != r2 && r1 != r2 {
3026 out.as_chunks_mut::<3>().0[write_generic] = [a as u32, b as u32, c as u32];
3027 write_generic += 1;
3028 }
3029 }
3030 Ok(write_generic)
3031 })())?;
3032 count = write_generic * 3;
3033 if settings.options.contains(SimplifyOptions::PRUNE)
3034 && count > settings.target_index_count
3035 && component_next <= vertex_error
3036 {
3037 (count, component_next) = extra::prune(
3038 out,
3039 count,
3040 &components,
3041 &component_errors,
3042 vertex_error,
3043 work,
3044 )?;
3045 }
3046 }
3047 let mut stale = true;
3048 while settings.options.contains(SimplifyOptions::PRUNE)
3049 && count > settings.target_index_count
3050 && component_next <= limit
3051 {
3052 let cutoff = if component_next * 1.5 < limit {
3053 component_next * 1.5
3054 } else {
3055 limit
3056 };
3057 let mut max_error = 0.0;
3058 for &e in &component_errors {
3059 work.add(1)?;
3060 if e > max_error && e <= cutoff {
3061 max_error = e;
3062 }
3063 }
3064 let (new_count, next) =
3065 extra::prune(out, count, &components, &component_errors, cutoff, work)?;
3066 component_next = next;
3067 if new_count == count && !stale {
3068 break;
3069 }
3070 stale = false;
3071 count = new_count;
3072 if error < max_error {
3073 error = max_error;
3074 }
3075 }
3076 if settings.options.contains(SimplifyOptions::PRUNE)
3077 && count > settings.target_index_count
3078 && component_next > limit
3079 {
3080 ws.lod_error_limited = true;
3081 }
3082 if solve {
3083 extra::solve_state(&mut s, &out[..count], work)?;
3084 }
3085 let error = sqrt(error) * error_scale;
3086 if !error.is_finite() {
3087 return Err(Error::NumericalFailure);
3088 }
3089 s.original = input.original;
3090 Ok((
3091 SimplifyResult {
3092 index_count: count,
3093 error,
3094 },
3095 s,
3096 PositionBounds { lo, hi },
3097 ))
3098}
3099
3100#[inline]
3102pub fn simplify(
3103 indices: &[u32],
3104 positions: Positions<'_>,
3105 settings: SimplifySettings,
3106 workspace: &mut Workspace,
3107) -> Result<SimplifiedMesh, Error> {
3108 simplify_generic::<u32>(indices, positions, settings, workspace).map(Into::into)
3109}
3110
3111#[inline]
3113pub fn simplify_with_attributes(
3114 indices: &[u32],
3115 positions: Positions<'_>,
3116 attributes: Attributes<'_>,
3117 weights: &[f32],
3118 vertex_flags: Option<&[VertexFlags]>,
3119 settings: SimplifySettings,
3120 workspace: &mut Workspace,
3121) -> Result<SimplifiedMesh, Error> {
3122 simplify_with_attributes_generic::<u32>(
3123 indices,
3124 positions,
3125 attributes,
3126 weights,
3127 vertex_flags,
3128 settings,
3129 workspace,
3130 )
3131 .map(Into::into)
3132}
3133
3134#[inline]
3136pub fn simplify_into(
3137 destination: &mut [u32],
3138 indices: &[u32],
3139 positions: Positions<'_>,
3140 settings: SimplifySettings,
3141 workspace: &mut Workspace,
3142) -> Result<SimplifyResult, Error> {
3143 simplify_into_generic::<u32>(destination, indices, positions, settings, workspace)
3144}
3145
3146#[inline]
3148#[allow(clippy::too_many_arguments)]
3149pub fn simplify_with_attributes_into(
3150 destination: &mut [u32],
3151 indices: &[u32],
3152 positions: Positions<'_>,
3153 attributes: Attributes<'_>,
3154 weights: &[f32],
3155 vertex_flags: Option<&[VertexFlags]>,
3156 settings: SimplifySettings,
3157 workspace: &mut Workspace,
3158) -> Result<SimplifyResult, Error> {
3159 simplify_with_attributes_into_generic::<u32>(
3160 destination,
3161 indices,
3162 positions,
3163 attributes,
3164 weights,
3165 vertex_flags,
3166 settings,
3167 workspace,
3168 )
3169}
3170
3171#[derive(Debug)]
3174pub struct SimplifiedMesh {
3175 pub indices: Vec<u32>,
3177 pub error: f32,
3179}
3180impl From<SimplifiedMeshGeneric<u32>> for SimplifiedMesh {
3181 #[inline]
3182 fn from(value: SimplifiedMeshGeneric<u32>) -> Self {
3183 Self {
3184 indices: value.indices,
3185 error: value.error,
3186 }
3187 }
3188}
3189
3190impl From<SimplifiedMesh> for SimplifiedMeshGeneric<u32> {
3191 #[inline]
3192 fn from(value: SimplifiedMesh) -> Self {
3193 Self {
3194 indices: value.indices,
3195 error: value.error,
3196 }
3197 }
3198}
3199
3200#[cfg(test)]
3201mod tests {
3202 use super::*;
3203 use crate::Limits;
3204
3205 #[test]
3206 fn update_bounds_preserve_original_sparse_order_and_zero_signs() {
3207 let p = [
3208 [100.0; 3], [0.0, -0.0, 0.0],
3210 [1.0, 0.0, 0.0],
3211 [-0.0, 1.0, 0.0],
3212 [0.0, 0.0, 1.0],
3213 ];
3214 let indices = [3, 2, 1, 1, 2, 4];
3215 for (options, expected_lo, expected_hi) in [
3216 (SimplifyOptions::EMPTY, [0.0f32, -0.0, 0.0], [100.0f32; 3]),
3217 (SimplifyOptions::SPARSE, [-0.0f32, 0.0, 0.0], [1.0f32; 3]),
3218 ] {
3219 let mut out = [0; 6];
3220 let mut ws = Workspace::default();
3221 let mut work = ws.begin();
3222 let (_, _, bounds) = run_state(
3223 &mut out,
3224 Input::borrowed(&indices),
3225 Positions::from_packed(&p),
3226 None,
3227 &[],
3228 None,
3229 SimplifySettings {
3230 target_index_count: indices.len(),
3231 target_error: 1.0,
3232 options,
3233 },
3234 &mut ws,
3235 &mut work,
3236 0,
3237 true,
3238 )
3239 .unwrap();
3240 assert_eq!(bounds.lo.map(f32::to_bits), expected_lo.map(f32::to_bits));
3241 assert_eq!(bounds.hi.map(f32::to_bits), expected_hi.map(f32::to_bits));
3242 }
3243 }
3244
3245 #[test]
3246 fn preflight_preserves_the_first_reservations_limit_error() {
3247 let vertices = isize::MAX as usize / core::mem::size_of::<Q>() + 1;
3251 let mut ws = Workspace::new(Limits {
3252 max_bytes: 0,
3253 ..Limits::default()
3254 });
3255 assert!(matches!(
3256 State::new(vertices, 0, 0, &mut ws, 0, false, &mut Vec::new()),
3257 Err(Error::LimitExceeded)
3258 ));
3259 }
3260
3261 #[test]
3264 #[ignore = "exhaustive 2^32-pattern backend identity gate"]
3265 fn simplify_sqrt_exhaustive_identity() {
3266 for bits in 0..=u32::MAX {
3267 let value = core::hint::black_box(f32::from_bits(bits));
3268 assert_eq!(
3269 sqrt(value).to_bits(),
3270 crate::math::sqrt(value).to_bits(),
3271 "sqrt operand {bits:08x}"
3272 );
3273 }
3274 }
3275
3276 #[test]
3277 fn repeated_simplify_reuses_arrays_but_releases_the_remapping_hash() {
3278 let p = [[0.0, 0.0, 0.0], [1.0, 0.0, 0.0], [0.0, 1.0, 0.0]];
3279 let settings = SimplifySettings {
3280 target_index_count: 0,
3281 target_error: 0.5,
3282 options: SimplifyOptions::EMPTY,
3283 };
3284 let mut ws = Workspace::default();
3285 let expected = simplify(&[0, 1, 2], Positions::from_packed(&p), settings, &mut ws).unwrap();
3286 let state = ws.simplify.as_ref().unwrap();
3287 assert_eq!(state.table.0.capacity(), 0);
3288 let before = (
3289 state.edges.as_ptr(),
3290 state.q.as_ptr(),
3291 state.collapses.as_ptr(),
3292 state.order.0.as_ptr(),
3293 );
3294 let actual = simplify(&[0, 1, 2], Positions::from_packed(&p), settings, &mut ws).unwrap();
3295 assert_eq!(expected.indices, actual.indices);
3296 assert_eq!(expected.error.to_bits(), actual.error.to_bits());
3297 let state = ws.simplify.as_ref().unwrap();
3298 assert_eq!(state.table.0.capacity(), 0);
3299 assert_eq!(
3300 before,
3301 (
3302 state.edges.as_ptr(),
3303 state.q.as_ptr(),
3304 state.collapses.as_ptr(),
3305 state.order.0.as_ptr()
3306 )
3307 );
3308 }
3309
3310 #[test]
3311 fn prepaid_picker_preserves_every_budget_prefix_and_capacity_stop() {
3312 type PickObservation = (Result<usize, Error>, u64, Vec<(u32, u32, u32)>);
3313 fn run(limit: u64, capacity: usize, prepaid: bool, welded: bool) -> PickObservation {
3314 let indices = [0, 1, 2, 2, 1, 0, 0, 2, 3, 3, 2, 0];
3315 let mut ws = Workspace::new(Limits {
3316 max_bytes: 1 << 20,
3317 max_work: limit,
3318 });
3319 let mut state = State::new(4, 12, 0, &mut ws, 0, false, &mut Vec::new()).unwrap();
3320 state
3321 .remap
3322 .0
3323 .extend(if welded { [0; 4] } else { [0, 1, 2, 3] });
3324 state.collapses.reserve_exact(12);
3325 let mut work = ws.begin();
3326 let result = if prepaid {
3327 (|| {
3328 metered!(&mut work, Some(indices.len()), |w| state
3329 .pick(&indices, capacity, w))
3330 })()
3331 } else {
3332 state.pick(&indices, capacity, &mut work)
3333 };
3334 ws.finish(&work);
3335 let collapses = state
3336 .collapses
3337 .iter()
3338 .map(|c| (c.a, c.b, c.error.to_bits()))
3339 .collect();
3340 (result, ws.usage().work, collapses)
3341 }
3342 for limit in 0..=13 {
3343 for capacity in [0, 2, 3, 6, 12] {
3344 for welded in [false, true] {
3345 assert_eq!(
3346 run(limit, capacity, true, welded),
3347 run(limit, capacity, false, welded)
3348 );
3349 }
3350 }
3351 }
3352 }
3353
3354 #[test]
3355 fn prepaid_phases_match_checked_visits() {
3356 fn phase<M: Meter>(
3359 fail_at: usize,
3360 seen: &mut Vec<usize>,
3361 work: &mut M,
3362 ) -> Result<(), Error> {
3363 for i in 0..5 {
3364 work.add(1)?;
3365 seen.push(i);
3366 if i == fail_at {
3367 return Err(Error::NumericalFailure);
3368 }
3369 }
3370 work.scan(5..7, |i| {
3371 seen.push(i);
3372 if i == fail_at {
3373 return Err(Error::NumericalFailure);
3374 }
3375 Ok(())
3376 })
3377 }
3378 fn run_phase(
3379 limit: u64,
3380 fail_at: usize,
3381 bound: Option<usize>,
3382 ) -> (Result<(), Error>, u64, Vec<usize>) {
3383 let mut ws = Workspace::new(Limits {
3384 max_bytes: 0,
3385 max_work: limit,
3386 });
3387 let mut work = ws.begin();
3388 let mut seen = Vec::new();
3389 let result = (|| metered!(&mut work, bound, |w| phase(fail_at, &mut seen, w)))();
3390 ws.finish(&work);
3391 (result, ws.usage().work, seen)
3392 }
3393 for limit in 0..=9 {
3394 for fail_at in 0..=7 {
3395 let checked = run_phase(limit, fail_at, None);
3396 assert_eq!(run_phase(limit, fail_at, Some(7)), checked);
3397 assert_eq!(run_phase(limit, fail_at, Some(9)), checked);
3398 }
3399 }
3400 }
3401
3402 #[test]
3403 fn ranking_preserves_numerical_failure_and_budget_prefix() {
3404 for limit in 0..=6 {
3405 for fail_at in 0..=5 {
3406 let mut ws = Workspace::new(Limits {
3407 max_bytes: 1 << 20,
3408 max_work: limit,
3409 });
3410 let mut state = State::new(2, 0, 0, &mut ws, 0, false, &mut Vec::new()).unwrap();
3411 state.p.extend([V::default(); 2]);
3412 state.remap.0.extend([0, 1]);
3413 state.q[0] = Q {
3414 c: f32::MAX,
3415 w: 0.5,
3416 inverse_weight: 2.0,
3417 ..Q::default()
3418 };
3419 state.q[1] = Q {
3420 w: 1.0,
3421 inverse_weight: 1.0,
3422 ..Q::default()
3423 };
3424 for i in 0..5 {
3425 state.collapses.push(Collapse {
3426 a: if i == fail_at { 0 } else { 1 },
3427 b: 1,
3428 error: f32::from_bits(1),
3429 });
3430 }
3431 let mut work = ws.begin();
3432 let result = state.rank(5, &mut work);
3433 let (expected, visited, changed) = if limit <= fail_at as u64 && limit < 5 {
3434 (Err(Error::LimitExceeded), limit, limit as usize)
3435 } else if fail_at < 5 {
3436 (Err(Error::NumericalFailure), fail_at as u64 + 1, fail_at)
3437 } else {
3438 (Ok(()), 5, 5)
3439 };
3440 assert_eq!(result, expected);
3441 ws.finish(&work);
3442 assert_eq!(ws.usage().work, visited);
3443 for (i, c) in state.collapses.iter().enumerate() {
3444 assert_eq!(c.error.to_bits(), if i < changed { 0 } else { 1 });
3445 }
3446 }
3447 }
3448 }
3449}
3450
3451#[cfg(test)]
3452mod retention_tests {
3453 use alloc::vec::Vec;
3454
3455 use crate::{
3456 optimize_overdraw, optimize_vertex_cache, simplify, Positions, SimplifyOptions,
3457 SimplifySettings,
3458 };
3459 use crate::{Error, Limits, Retention, Workspace};
3460
3461 #[test]
3462 fn cache_update_cache_releases_scratch_and_preserves_results() {
3463 let positions = [
3464 [0.0, 0.0, 0.0],
3465 [1.0, 0.0, 0.0],
3466 [0.0, 1.0, 0.0],
3467 [1.0, 1.0, 0.1],
3468 ];
3469 let indices = [0, 1, 2, 2, 1, 3];
3470 let mut outcomes = Vec::new();
3471 for retention in [Retention::Lean, Retention::Reuse] {
3472 let mut ws = Workspace::default();
3473 ws.set_retention(retention);
3474 let cached = optimize_vertex_cache(&indices, positions.len(), &mut ws).unwrap();
3475 let cache_work = ws.usage().work;
3476 let mut updated_indices = indices;
3477 let mut updated_positions = positions;
3478 let result = crate::simplify_with_update(
3479 &mut updated_indices,
3480 &mut crate::PositionsMut::from_packed(&mut updated_positions),
3481 None,
3482 &[],
3483 None,
3484 SimplifySettings {
3485 target_index_count: indices.len(),
3486 target_error: 0.5,
3487 options: SimplifyOptions::EMPTY,
3488 },
3489 &mut ws,
3490 )
3491 .unwrap();
3492 let update_work = ws.usage().work;
3493 if retention == Retention::Lean {
3494 assert_eq!(ws.integers.capacity(), 0);
3495 assert_eq!(ws.floats.capacity(), 0);
3496 assert_eq!(ws.flags.capacity(), 0);
3497 assert_eq!(ws.keys.capacity(), 0);
3498 assert_eq!(ws.vertices.capacity(), 0);
3499 }
3500 assert!(ws.simplify.is_some());
3501 let cached_again =
3502 optimize_vertex_cache(&updated_indices, positions.len(), &mut ws).unwrap();
3503 if retention == Retention::Lean {
3504 assert!(ws.simplify.is_none());
3505 }
3506 outcomes.push((
3507 cached,
3508 result.index_count,
3509 result.error.to_bits(),
3510 updated_indices,
3511 updated_positions.map(|p| p.map(f32::to_bits)),
3512 cached_again,
3513 [cache_work, update_work, ws.usage().work],
3514 ));
3515 }
3516 assert_eq!(outcomes[0], outcomes[1]);
3517 }
3518
3519 #[test]
3520 fn switching_chain_family_releases_scratch_and_preserves_results() {
3521 let p = [
3522 [0.0, 0.0, 0.0],
3523 [1.0, 0.0, 0.0],
3524 [0.0, 1.0, 0.0],
3525 [1.0, 1.0, 0.1],
3526 ];
3527 let i = [0, 1, 2, 2, 1, 3];
3528 let settings = SimplifySettings {
3529 target_index_count: 3,
3530 target_error: 0.5,
3531 options: SimplifyOptions::EMPTY,
3532 };
3533 let mut ws = Workspace::default();
3534 ws.set_retention(Retention::Lean);
3535 let simplified = simplify(&i, Positions::from_packed(&p), settings, &mut ws).unwrap();
3536 assert!(ws.simplify.as_ref().unwrap().capacity_bytes().unwrap() > 0);
3537 assert_eq!(ws.simplify.as_ref().unwrap().q.capacity(), 0);
3538 let mut reuse = Workspace::default();
3539 assert_eq!(reuse.retention(), Retention::Reuse);
3540 let expected = simplify(&i, Positions::from_packed(&p), settings, &mut reuse).unwrap();
3541 assert_eq!(expected.indices, simplified.indices);
3542 assert_eq!(expected.error.to_bits(), simplified.error.to_bits());
3543 assert!(reuse.simplify.as_ref().unwrap().q.capacity() > 0);
3544 let expected_cache = optimize_vertex_cache(&i, p.len(), &mut reuse).unwrap();
3545 assert!(reuse.simplify.is_some());
3546 let expected_overdraw = optimize_overdraw(
3547 &expected_cache,
3548 Positions::from_packed(&p),
3549 1.05,
3550 &mut reuse,
3551 )
3552 .unwrap();
3553 assert!(reuse.simplify.is_some());
3554 assert!(reuse.vertices.capacity() > 0);
3555 let cached = optimize_vertex_cache(&i, p.len(), &mut ws).unwrap();
3556 assert!(ws.simplify.is_none());
3557 assert!(ws.vertices.capacity() > 0);
3558 assert_eq!(
3559 cached,
3560 optimize_vertex_cache(&i, p.len(), &mut Workspace::default()).unwrap()
3561 );
3562 let vertex_ptr = ws.vertices.as_ptr();
3563 let integer_ptr = ws.integers.as_ptr();
3564 assert_eq!(cached, optimize_vertex_cache(&i, p.len(), &mut ws).unwrap());
3565 assert_eq!(vertex_ptr, ws.vertices.as_ptr());
3566 assert_eq!(integer_ptr, ws.integers.as_ptr());
3567 let overdraw =
3568 optimize_overdraw(&cached, Positions::from_packed(&p), 1.05, &mut ws).unwrap();
3569 assert_eq!(overdraw, expected_overdraw);
3570 assert_eq!(ws.vertices.capacity(), 0);
3571 assert_eq!(ws.flags.capacity(), 0);
3572 assert_eq!(
3573 overdraw,
3574 optimize_overdraw(
3575 &cached,
3576 Positions::from_packed(&p),
3577 1.05,
3578 &mut Workspace::default()
3579 )
3580 .unwrap()
3581 );
3582 let integer_ptr = ws.integers.as_ptr();
3583 let float_ptr = ws.floats.as_ptr();
3584 assert_eq!(
3585 overdraw,
3586 optimize_overdraw(&cached, Positions::from_packed(&p), 1.05, &mut ws).unwrap()
3587 );
3588 assert_eq!(integer_ptr, ws.integers.as_ptr());
3589 assert_eq!(float_ptr, ws.floats.as_ptr());
3590 let again = simplify(&i, Positions::from_packed(&p), settings, &mut ws).unwrap();
3591 assert_eq!(again.indices, simplified.indices);
3592 assert_eq!(again.error.to_bits(), simplified.error.to_bits());
3593 assert_eq!(ws.integers.capacity(), 0);
3594 assert_eq!(ws.floats.capacity(), 0);
3595 assert_eq!(ws.keys.capacity(), 0);
3596 assert_eq!(ws.simplify.as_ref().unwrap().q.capacity(), 0);
3597 let state_bytes = ws.simplify.as_ref().unwrap().capacity_bytes().unwrap();
3598 assert_eq!(ws.retained_bytes().unwrap(), state_bytes);
3599 assert_eq!(ws.limits(), Limits::default());
3600 assert!(ws.usage().bytes >= state_bytes);
3601 assert!(ws.usage().work > 0);
3602 assert_eq!(
3604 optimize_vertex_cache(&[4, 0, 1], p.len(), &mut ws),
3605 Err(Error::IndexOutOfBounds)
3606 );
3607 assert!(ws.simplify.is_some());
3608 assert_eq!(
3609 optimize_vertex_cache(&[4, 0, 1], p.len(), &mut reuse),
3610 Err(Error::IndexOutOfBounds)
3611 );
3612 assert_eq!(ws.retained_bytes().unwrap(), state_bytes);
3613 let fifo = crate::optimize_vertex_cache_fifo(&i, p.len(), 16, &mut ws).unwrap();
3614 assert!(ws.simplify.is_none());
3615 assert_eq!(
3616 fifo,
3617 crate::optimize_vertex_cache_fifo(&i, p.len(), 16, &mut Workspace::default()).unwrap()
3618 );
3619 let usage = ws.usage();
3620 ws.set_retention(Retention::Lean);
3621 assert_eq!(ws.usage(), usage);
3622 ws.clear();
3623 assert_eq!(ws.retention(), Retention::Lean);
3624 ws.set_limits(Limits::default());
3625 assert_eq!(ws.retention(), Retention::Lean);
3626 ws.set_retention(Retention::Reuse);
3627 assert_eq!(ws.retained_bytes().unwrap(), 0);
3628 assert_eq!(ws.usage(), crate::Usage::default());
3629 }
3630}