1use crate::index::Convert;
14use crate::workspace::{checked_bytes, Work};
15use crate::{Error, Workspace};
16use alloc::collections::BTreeMap;
17use alloc::vec::Vec;
18
19type Point = [f64; 2];
20
21const MAX_COORD: f64 = 16_777_216.0;
23const MAX_PADDING: f32 = 64.0;
25const MAX_BUDGET: u32 = 16;
27const REDUCE_TO: usize = 24;
29const MAX_OUTLINE: usize = 64;
31const MARGIN: f64 = 1.0 / 256.0;
33const MARGIN_SCALE: f64 = 1.0 / 4_194_304.0;
35const MIN_GAIN: f64 = 1e-9;
38
39#[derive(Clone, Copy, Debug, Default, PartialEq, Eq)]
41#[non_exhaustive]
42pub enum AlphaWrap {
43 #[default]
45 Clamp,
46 Repeat,
48}
49
50#[derive(Clone, Copy, Debug)]
57#[non_exhaustive]
58pub struct AlphaMask<'a> {
59 data: &'a [u8],
60 stride: usize,
61 pitch: usize,
62 width: u32,
63 height: u32,
64}
65
66impl<'a> AlphaMask<'a> {
67 #[inline]
73 pub fn new(data: &'a [u8], width: u32, height: u32) -> Result<Self, Error> {
74 let pitch = usize::try_from(width).map_err(|_| Error::SizeOverflow)?;
75 Self::with_layout(data, 1, pitch, width, height)
76 }
77
78 #[inline]
85 pub fn with_layout(
86 data: &'a [u8],
87 stride: usize,
88 pitch: usize,
89 width: u32,
90 height: u32,
91 ) -> Result<Self, Error> {
92 if width == 0 || height == 0 || stride == 0 {
93 return Err(Error::InvalidParameter);
94 }
95 let w = usize::try_from(width - 1).map_err(|_| Error::SizeOverflow)?;
96 let h = usize::try_from(height - 1).map_err(|_| Error::SizeOverflow)?;
97 let last = h
98 .checked_mul(pitch)
99 .and_then(|row| w.checked_mul(stride).and_then(|x| row.checked_add(x)))
100 .ok_or(Error::SizeOverflow)?;
101 if last >= data.len() {
102 return Err(Error::InvalidLayout);
103 }
104 Ok(Self {
105 data,
106 stride,
107 pitch,
108 width,
109 height,
110 })
111 }
112
113 #[inline]
115 pub const fn width(&self) -> u32 {
116 self.width
117 }
118
119 #[inline]
121 pub const fn height(&self) -> u32 {
122 self.height
123 }
124
125 #[inline]
127 pub fn alpha(&self, x: u32, y: u32) -> Option<u8> {
128 if x >= self.width || y >= self.height {
129 return None;
130 }
131 let x = usize::try_from(x).ok()?;
132 let y = usize::try_from(y).ok()?;
133 self.data.get(y * self.pitch + x * self.stride).copied()
134 }
135
136 fn texel(&self, x: i64, y: i64, wrap: AlphaWrap) -> u8 {
137 let (w, h) = (i64::from(self.width), i64::from(self.height));
138 let (x, y) = match wrap {
139 AlphaWrap::Clamp => (x.clamp(0, w - 1), y.clamp(0, h - 1)),
140 AlphaWrap::Repeat => (x.rem_euclid(w), y.rem_euclid(h)),
141 };
142 match (u32::try_from(x), u32::try_from(y)) {
143 (Ok(x), Ok(y)) => self.alpha(x, y).unwrap_or(0),
144 _ => 0,
145 }
146 }
147}
148
149#[derive(Clone, Copy, Debug, PartialEq)]
151#[non_exhaustive]
152pub struct CardTrimOptions {
153 pub threshold: u8,
156 pub max_vertices: u32,
158 pub padding: f32,
163 pub wrap: AlphaWrap,
165 pub vertex_cost: f32,
175}
176
177impl Default for CardTrimOptions {
178 fn default() -> Self {
179 Self {
180 threshold: 128,
181 max_vertices: 8,
182 padding: 0.5,
183 wrap: AlphaWrap::Clamp,
184 vertex_cost: 0.0,
185 }
186 }
187}
188
189#[derive(Clone, Copy, Debug, Default, PartialEq)]
194#[non_exhaustive]
195pub struct CardTrimReport {
196 pub input_triangles: usize,
198 pub output_triangles: usize,
200 pub output_vertices: usize,
202 pub cards: usize,
204 pub trimmed_cards: usize,
206 pub split_cards: usize,
210 pub removed_cards: usize,
212 pub unchanged_cards: usize,
214 pub passthrough_triangles: usize,
216 pub area_before: f64,
218 pub area_after: f64,
220 pub opaque_texels: u64,
223}
224
225#[derive(Clone, Debug, Default, PartialEq)]
227#[non_exhaustive]
228pub struct TrimmedCardsGeneric<I: crate::Index = u32> {
229 pub vertices: Vec<f32>,
231 pub indices: Vec<I>,
233 pub report: CardTrimReport,
235 pub card_vertices: Vec<u32>,
241}
242
243#[derive(Clone, Debug, Default, PartialEq)]
246#[non_exhaustive]
247pub struct TrimmedCards {
248 pub vertices: Vec<f32>,
250 pub indices: Vec<u32>,
252 pub report: CardTrimReport,
254 pub card_vertices: Vec<u32>,
256}
257
258impl From<TrimmedCardsGeneric<u32>> for TrimmedCards {
259 #[inline]
260 fn from(value: TrimmedCardsGeneric<u32>) -> Self {
261 Self {
262 vertices: value.vertices,
263 indices: value.indices,
264 report: value.report,
265 card_vertices: value.card_vertices,
266 }
267 }
268}
269
270impl From<TrimmedCards> for TrimmedCardsGeneric<u32> {
271 #[inline]
272 fn from(value: TrimmedCards) -> Self {
273 Self {
274 vertices: value.vertices,
275 indices: value.indices,
276 report: value.report,
277 card_vertices: value.card_vertices,
278 }
279 }
280}
281
282impl<I: crate::Index> Convert<I> for TrimmedCardsGeneric {
283 type Output = TrimmedCardsGeneric<I>;
284 fn convert(self, ws: &mut Workspace) -> Result<Self::Output, Error> {
285 Ok(TrimmedCardsGeneric {
286 vertices: self.vertices,
287 indices: I::from_vec(self.indices, ws)?,
288 report: self.report,
289 card_vertices: self.card_vertices,
290 })
291 }
292}
293
294#[inline]
365pub fn trim_alpha_cards_generic<I: crate::Index>(
366 indices: &[I],
367 vertices: &[f32],
368 vertex_stride: usize,
369 uv_offset: usize,
370 mask: AlphaMask<'_>,
371 options: CardTrimOptions,
372 workspace: &mut Workspace,
373) -> Result<TrimmedCardsGeneric<I>, Error> {
374 I::with_input(indices, workspace, |indices, workspace| {
375 trim_u32(
376 indices,
377 vertices,
378 vertex_stride,
379 uv_offset,
380 mask,
381 options,
382 workspace,
383 )
384 .and_then(|value| Convert::<I>::convert(value, workspace))
385 })
386}
387
388#[inline]
390pub fn trim_alpha_cards(
391 indices: &[u32],
392 vertices: &[f32],
393 vertex_stride: usize,
394 uv_offset: usize,
395 mask: AlphaMask<'_>,
396 options: CardTrimOptions,
397 workspace: &mut Workspace,
398) -> Result<TrimmedCards, Error> {
399 trim_alpha_cards_generic::<u32>(
400 indices,
401 vertices,
402 vertex_stride,
403 uv_offset,
404 mask,
405 options,
406 workspace,
407 )
408 .map(Into::into)
409}
410
411#[inline(always)]
415fn sub(a: Point, b: Point) -> Point {
416 [a[0] - b[0], a[1] - b[1]]
417}
418
419#[inline(always)]
420fn cross(a: Point, b: Point) -> f64 {
421 a[0] * b[1] - a[1] * b[0]
422}
423
424#[inline(always)]
425fn dot(a: Point, b: Point) -> f64 {
426 a[0] * b[0] + a[1] * b[1]
427}
428
429#[inline(always)]
430fn lerp(a: Point, b: Point, t: f64) -> Point {
431 [a[0] + t * (b[0] - a[0]), a[1] + t * (b[1] - a[1])]
432}
433
434#[inline(always)]
436fn side(lo: Point, hi: Point, p: Point) -> f64 {
437 cross(sub(hi, lo), sub(p, lo))
438}
439
440fn area2(poly: &[Point]) -> f64 {
442 let Some(&origin) = poly.first() else {
443 return 0.0;
444 };
445 let mut sum = 0.0;
446 for pair in poly.windows(2) {
447 sum += cross(sub(pair[0], origin), sub(pair[1], origin));
448 }
449 sum
450}
451
452fn to_i64(x: f64) -> Result<i64, Error> {
453 if x.is_finite() && x.abs() < 9.0e15 {
454 Ok(x as i64)
455 } else {
456 Err(Error::NumericalFailure)
457 }
458}
459
460fn inside(poly: &[Point], p: Point, eps: f64) -> bool {
462 let n = poly.len();
463 (0..n).all(|i| {
464 let a = poly[i];
465 let b = poly[(i + 1) % n];
466 let e = sub(b, a);
467 cross(e, sub(p, a)) >= -eps * (e[0].abs() + e[1].abs())
468 })
469}
470
471fn strip_range(t: &[Point; 3], y0: f64, y1: f64) -> Option<(f64, f64)> {
473 let (mut lo, mut hi) = (f64::INFINITY, f64::NEG_INFINITY);
474 for k in 0..3 {
475 let a = t[k];
476 let b = t[(k + 1) % 3];
477 if a[1] >= y0 && a[1] <= y1 {
478 lo = lo.min(a[0]);
479 hi = hi.max(a[0]);
480 }
481 for y in [y0, y1] {
482 if (a[1] < y && b[1] > y) || (a[1] > y && b[1] < y) {
483 let x = a[0] + (y - a[1]) * (b[0] - a[0]) / (b[1] - a[1]);
484 lo = lo.min(x);
485 hi = hi.max(x);
486 }
487 }
488 }
489 (lo <= hi).then_some((lo, hi))
490}
491
492struct Store<'w> {
496 ws: &'w mut Workspace,
497 bytes: usize,
498}
499
500impl Store<'_> {
501 fn charge(&mut self, bytes: usize) -> Result<(), Error> {
502 let total = self.bytes.checked_add(bytes).ok_or(Error::SizeOverflow)?;
503 self.ws.charge_owned(total)?;
504 self.bytes = total;
505 Ok(())
506 }
507
508 fn grow<T>(&mut self, v: &mut Vec<T>, extra: usize) -> Result<(), Error> {
509 let need = v.len().checked_add(extra).ok_or(Error::SizeOverflow)?;
510 if need <= v.capacity() {
511 return Ok(());
512 }
513 let target = need.max(v.capacity().saturating_mul(2)).max(4);
514 self.charge(checked_bytes(
515 target - v.capacity(),
516 core::mem::size_of::<T>(),
517 )?)?;
518 v.try_reserve_exact(target - v.len())
519 .map_err(|_| Error::AllocationFailed)
520 }
521
522 fn push<T>(&mut self, v: &mut Vec<T>, value: T) -> Result<(), Error> {
523 self.grow(v, 1)?;
524 v.push(value);
525 Ok(())
526 }
527
528 fn fill<T: Clone>(&mut self, v: &mut Vec<T>, n: usize, value: T) -> Result<(), Error> {
529 v.clear();
530 self.grow(v, n)?;
531 v.resize(n, value);
532 Ok(())
533 }
534}
535
536struct Input<'a> {
540 indices: &'a [u32],
541 vertices: &'a [f32],
542 stride: usize,
543 uv: usize,
544 mask: AlphaMask<'a>,
545 threshold: u8,
546 budget: usize,
547 vertex_cost: f64,
548 padding: f64,
549 wrap: AlphaWrap,
550 w: f64,
551 h: f64,
552}
553
554impl Input<'_> {
555 fn attrs(&self, v: u32) -> &[f32] {
556 let base = v as usize * self.stride;
557 &self.vertices[base..base + self.stride]
558 }
559
560 fn texel(&self, v: u32) -> Point {
561 let a = self.attrs(v);
562 [
563 f64::from(a[self.uv]) * self.w,
564 f64::from(a[self.uv + 1]) * self.h,
565 ]
566 }
567}
568
569#[derive(Clone, Copy, Debug)]
570struct Tri {
571 v: [u32; 3],
572 p: [Point; 3],
573 area2: f64,
574 sigma: [f64; 3],
577}
578
579impl Tri {
580 fn new(input: &Input<'_>, t: usize) -> Self {
581 let i = &input.indices[t * 3..t * 3 + 3];
582 let v = [i[0], i[1], i[2]];
583 let p = v.map(|v| input.texel(v));
584 let area2 = cross(sub(p[1], p[0]), sub(p[2], p[0]));
585 let mut tri = Self {
586 v,
587 p,
588 area2,
589 sigma: [0.0; 3],
590 };
591 for k in 0..3 {
592 let (_, _, lo, hi) = tri.edge(k);
593 let s = side(lo, hi, p[(k + 2) % 3]);
594 tri.sigma[k] = if s > 0.0 {
595 1.0
596 } else if s < 0.0 {
597 -1.0
598 } else {
599 0.0
600 };
601 }
602 tri
603 }
604
605 fn valid(&self) -> bool {
606 self.area2 != 0.0 && self.sigma.iter().all(|&s| s != 0.0)
607 }
608
609 fn edge(&self, k: usize) -> (u32, u32, Point, Point) {
611 let (a, b) = (k, (k + 1) % 3);
612 if self.v[a] < self.v[b] {
613 (self.v[a], self.v[b], self.p[a], self.p[b])
614 } else {
615 (self.v[b], self.v[a], self.p[b], self.p[a])
616 }
617 }
618
619 fn point_of(&self, v: u32) -> Option<Point> {
620 (0..3).find(|&k| self.v[k] == v).map(|k| self.p[k])
621 }
622}
623
624#[derive(Clone, Copy, Debug, PartialEq, Eq, PartialOrd, Ord)]
625enum Key {
626 Original(u32),
628 Cross(u32, u32, u32),
630 Corner(u32, u32),
632 OnEdge(u32, u32, u32),
634}
635
636#[derive(Clone, Copy, Debug)]
637enum Line {
638 Fit(u32),
639 Edge(u32, u32),
640}
641
642#[derive(Clone, Copy, Debug)]
643struct WVert {
644 p: Point,
645 key: Key,
646 line: Line,
648}
649
650#[derive(Clone, Copy, Debug)]
651struct Edge {
652 s: Point,
653 d: Point,
654 e: Point,
655}
656
657#[derive(Clone, Copy, Debug)]
658struct Pair {
659 ok: bool,
660 cap: f64,
661 apex: Point,
662}
663
664#[derive(Clone, Copy, Debug)]
665enum FitKind {
666 Empty,
667 Keep,
668 Polygon(usize, usize),
669}
670
671#[derive(Clone, Copy, Debug)]
672struct Fit {
673 kind: FitKind,
674 opaque: u64,
675}
676
677#[derive(Default)]
678struct Scratch {
679 tris: Vec<Tri>,
680 key: Vec<u32>,
681 points: Vec<Point>,
682 hull: Vec<Point>,
683 dom: Vec<Point>,
684 tmp: Vec<Point>,
685 rows: Vec<(i64, i64)>,
686 edges: Vec<Edge>,
687 dirs: Vec<Point>,
688 table: Vec<Pair>,
689 cost: Vec<f64>,
690 parent: Vec<u32>,
691 seq: Vec<u32>,
692 best: Vec<u32>,
693 a: Vec<WVert>,
694 b: Vec<WVert>,
695 pieces: Vec<WVert>,
696 ends: Vec<(usize, usize)>,
697 directed: Vec<(u32, u32)>,
698 boundary: Vec<(u32, u32)>,
699 stats: Vec<[f64; 3]>,
700 values: Vec<f32>,
701 keymap: BTreeMap<Key, u32>,
702}
703
704struct Output {
705 vertices: Vec<f32>,
706 indices: Vec<u32>,
707 remap: Vec<u32>,
708 report: CardTrimReport,
709 card_vertices: Vec<u32>,
710}
711
712fn trim_u32(
716 indices: &[u32],
717 vertices: &[f32],
718 stride: usize,
719 uv: usize,
720 mask: AlphaMask<'_>,
721 options: CardTrimOptions,
722 workspace: &mut Workspace,
723) -> Result<TrimmedCardsGeneric, Error> {
724 if !(3..=MAX_BUDGET).contains(&options.max_vertices)
725 || !options.padding.is_finite()
726 || !(0.0..=MAX_PADDING).contains(&options.padding)
727 || !options.vertex_cost.is_finite()
728 || options.vertex_cost < 0.0
729 {
730 return Err(Error::InvalidParameter);
731 }
732 let fits_uv = uv.checked_add(2).is_some_and(|end| end <= stride);
733 if stride == 0 || !fits_uv || !vertices.len().is_multiple_of(stride) {
734 return Err(Error::InvalidLayout);
735 }
736 let input = Input {
737 indices,
738 vertices,
739 stride,
740 uv,
741 mask,
742 threshold: options.threshold,
743 budget: usize::try_from(options.max_vertices).map_err(|_| Error::SizeOverflow)?,
744 vertex_cost: f64::from(options.vertex_cost),
745 padding: f64::from(options.padding) + MARGIN,
746 wrap: options.wrap,
747 w: f64::from(mask.width),
748 h: f64::from(mask.height),
749 };
750 let mut work = workspace.begin();
751 let result = {
752 let mut store = Store {
753 ws: workspace,
754 bytes: 0,
755 };
756 run(&input, &mut store, &mut work)
757 };
758 workspace.finish(&work);
759 result
760}
761
762fn run(
763 input: &Input<'_>,
764 store: &mut Store<'_>,
765 work: &mut Work,
766) -> Result<TrimmedCardsGeneric, Error> {
767 let vertex_count = input.vertices.len() / input.stride;
768 crate::workspace::topology(input.indices, vertex_count, work)?;
769 work.add(input.indices.len().saturating_mul(input.stride))?;
770 for &v in input.indices {
771 let a = input.attrs(v);
772 if !a.iter().all(|x| x.is_finite()) {
773 return Err(Error::NumericalFailure);
774 }
775 let p = input.texel(v);
776 if p[0].abs() > MAX_COORD || p[1].abs() > MAX_COORD {
777 return Err(Error::InvalidParameter);
778 }
779 }
780 let n = input.indices.len() / 3;
781
782 let mut parent = Vec::new();
784 store.fill(&mut parent, n, u32::MAX)?;
785 let mut edges: Vec<(u32, u32, u32)> = Vec::new();
786 store.grow(&mut edges, n.saturating_mul(3))?;
787 for (t, slot) in parent.iter_mut().enumerate() {
788 let tri = Tri::new(input, t);
789 if !tri.valid() {
790 continue;
791 }
792 let id = parent_id(t)?;
793 *slot = id;
794 for k in 0..3 {
795 let (lo, hi, _, _) = tri.edge(k);
796 edges.push((lo, hi, id));
797 }
798 }
799 work.add(edges.len().saturating_mul(32))?;
800 edges.sort_unstable();
801 for pair in edges.windows(2) {
802 if pair[0].0 == pair[1].0 && pair[0].1 == pair[1].1 {
803 union(&mut parent, pair[0].2, pair[1].2);
804 }
805 }
806 let mut offsets = Vec::new();
808 store.fill(&mut offsets, n + 1, 0usize)?;
809 for t in 0..n {
810 if parent[t] != u32::MAX {
811 let root = find(&mut parent, t);
812 offsets[root + 1] += 1;
813 }
814 }
815 for t in 0..n {
816 offsets[t + 1] += offsets[t];
817 }
818 let mut fill = Vec::new();
819 store.fill(&mut fill, n, 0usize)?;
820 let mut members = Vec::new();
821 store.fill(&mut members, offsets[n], 0u32)?;
822 for t in 0..n {
823 if parent[t] != u32::MAX {
824 let root = find(&mut parent, t);
825 members[offsets[root] + fill[root]] = parent_id(t)?;
826 fill[root] += 1;
827 }
828 }
829 drop(edges);
830
831 let mut out = Output {
832 vertices: Vec::new(),
833 indices: Vec::new(),
834 remap: Vec::new(),
835 card_vertices: Vec::new(),
836 report: CardTrimReport {
837 input_triangles: n,
838 ..CardTrimReport::default()
839 },
840 };
841 store.fill(&mut out.remap, vertex_count, u32::MAX)?;
842 let mut scratch = Scratch::default();
843 let mut memo: BTreeMap<Vec<u32>, Fit> = BTreeMap::new();
844 let mut polygons: Vec<Point> = Vec::new();
845 for t in 0..n {
846 if parent[t] == u32::MAX {
847 out.report.passthrough_triangles += 1;
848 let tri = &input.indices[t * 3..t * 3 + 3];
849 emit_original(input, store, &mut out, [tri[0], tri[1], tri[2]])?;
850 continue;
851 }
852 if find(&mut parent, t) != t {
853 continue;
854 }
855 let card = &members[offsets[t]..offsets[t + 1]];
856 process_card(
857 input,
858 store,
859 work,
860 &mut out,
861 &mut scratch,
862 &mut memo,
863 &mut polygons,
864 card,
865 )?;
866 }
867 out.report.output_triangles = out.indices.len() / 3;
868 out.report.output_vertices = out.vertices.len() / input.stride;
869 Ok(TrimmedCardsGeneric {
870 vertices: out.vertices,
871 indices: out.indices,
872 report: out.report,
873 card_vertices: out.card_vertices,
874 })
875}
876
877fn parent_id(t: usize) -> Result<u32, Error> {
878 u32::try_from(t).map_err(|_| Error::SizeOverflow)
879}
880
881fn find(parent: &mut [u32], t: usize) -> usize {
882 let mut x = t;
883 while parent[x] as usize != x {
884 let up = parent[x] as usize;
885 parent[x] = parent[up];
886 x = parent[x] as usize;
887 }
888 x
889}
890
891fn union(parent: &mut [u32], a: u32, b: u32) {
892 let ra = find(parent, a as usize);
893 let rb = find(parent, b as usize);
894 if ra < rb {
895 parent[rb] = parent[ra];
896 } else if rb < ra {
897 parent[ra] = parent[rb];
898 }
899}
900
901fn copy_vertex(
902 input: &Input<'_>,
903 store: &mut Store<'_>,
904 out: &mut Output,
905 v: u32,
906) -> Result<u32, Error> {
907 let slot = out.remap[v as usize];
908 if slot != u32::MAX {
909 return Ok(slot);
910 }
911 let index = new_index(input, out)?;
912 store.grow(&mut out.vertices, input.stride)?;
913 out.vertices.extend_from_slice(input.attrs(v));
914 out.remap[v as usize] = index;
915 Ok(index)
916}
917
918fn new_index(input: &Input<'_>, out: &Output) -> Result<u32, Error> {
919 u32::try_from(out.vertices.len() / input.stride)
920 .ok()
921 .filter(|&i| i != u32::MAX)
922 .ok_or(Error::SizeOverflow)
923}
924
925fn push_vertex(
926 input: &Input<'_>,
927 store: &mut Store<'_>,
928 out: &mut Output,
929 values: &[f32],
930) -> Result<u32, Error> {
931 let index = new_index(input, out)?;
932 store.grow(&mut out.vertices, input.stride)?;
933 out.vertices.extend_from_slice(values);
934 Ok(index)
935}
936
937fn emit_original(
938 input: &Input<'_>,
939 store: &mut Store<'_>,
940 out: &mut Output,
941 v: [u32; 3],
942) -> Result<(), Error> {
943 let mapped = [
944 copy_vertex(input, store, out, v[0])?,
945 copy_vertex(input, store, out, v[1])?,
946 copy_vertex(input, store, out, v[2])?,
947 ];
948 store.grow(&mut out.indices, 3)?;
949 out.indices.extend_from_slice(&mapped);
950 Ok(())
951}
952
953#[allow(clippy::too_many_arguments)]
957fn process_card(
958 input: &Input<'_>,
959 store: &mut Store<'_>,
960 work: &mut Work,
961 out: &mut Output,
962 s: &mut Scratch,
963 memo: &mut BTreeMap<Vec<u32>, Fit>,
964 polygons: &mut Vec<Point>,
965 card: &[u32],
966) -> Result<(), Error> {
967 s.tris.clear();
968 s.key.clear();
969 let mut before = 0.0;
970 for &t in card {
971 let tri = Tri::new(input, t as usize);
972 before += tri.area2.abs() * 0.5;
973 store.push(&mut s.tris, tri)?;
974 for v in tri.v {
975 let a = input.attrs(v);
976 store.push(&mut s.key, a[input.uv].to_bits())?;
977 store.push(&mut s.key, a[input.uv + 1].to_bits())?;
978 }
979 }
980 work.add(card.len())?;
981 out.report.cards += 1;
982 out.report.area_before += before;
983 let fit = match memo.get(s.key.as_slice()) {
984 Some(&fit) => fit,
985 None => {
986 let fit = fit_card(input, store, work, s, polygons)?;
987 store.charge(checked_bytes(s.key.len(), 4)?.saturating_add(64))?;
988 let mut key = Vec::new();
989 key.try_reserve_exact(s.key.len())
990 .map_err(|_| Error::AllocationFailed)?;
991 key.extend_from_slice(&s.key);
992 memo.insert(key, fit);
993 fit
994 }
995 };
996 out.report.opaque_texels = out.report.opaque_texels.saturating_add(fit.opaque);
997 let (start, len) = match fit.kind {
998 FitKind::Empty => {
999 out.report.removed_cards += 1;
1000 store.push(&mut out.card_vertices, 0)?;
1001 return Ok(());
1002 }
1003 FitKind::Keep => return keep_card(input, store, out, s, before),
1004 FitKind::Polygon(start, len) => (start, len),
1005 };
1006 let q = &polygons[start..start + len];
1007 let scale = s
1010 .tris
1011 .iter()
1012 .flat_map(|t| t.p)
1013 .fold(1.0f64, |m, p| m.max(p[0].abs()).max(p[1].abs()));
1014 let terms = (s.tris.len() * 3 + len) as f64;
1015 let keep_below = before * (1.0 - MIN_GAIN) - 8.0 * f64::EPSILON * terms * scale * scale;
1016 if convex_disk(store, s)? {
1017 if let Some(r) = affine_reference(input, store, s)? {
1018 let after = area2(q) * 0.5;
1019 if after >= keep_below {
1020 return keep_card(input, store, out, s, before);
1021 }
1022 emit_polygon(input, store, out, s, q, r)?;
1023 store.push(&mut out.card_vertices, fitted_count(len)?)?;
1024 out.report.trimmed_cards += 1;
1025 out.report.area_after += after;
1026 return Ok(());
1027 }
1028 }
1029 let after = clip_pieces(store, work, s, q)?;
1030 if after >= keep_below {
1031 return keep_card(input, store, out, s, before);
1032 }
1033 emit_pieces(input, store, out, s)?;
1034 store.push(&mut out.card_vertices, fitted_count(len)?)?;
1035 out.report.trimmed_cards += 1;
1036 out.report.split_cards += 1;
1037 out.report.area_after += after;
1038 Ok(())
1039}
1040
1041fn fitted_count(len: usize) -> Result<u32, Error> {
1042 u32::try_from(len).map_err(|_| Error::SizeOverflow)
1043}
1044
1045fn keep_card(
1046 input: &Input<'_>,
1047 store: &mut Store<'_>,
1048 out: &mut Output,
1049 s: &mut Scratch,
1050 before: f64,
1051) -> Result<(), Error> {
1052 s.seq.clear();
1053 for tri in &s.tris {
1054 emit_original(input, store, out, tri.v)?;
1055 for v in tri.v {
1056 store.push(&mut s.seq, v)?;
1057 }
1058 }
1059 s.seq.sort_unstable();
1060 s.seq.dedup();
1061 store.push(&mut out.card_vertices, fitted_count(s.seq.len())?)?;
1062 out.report.unchanged_cards += 1;
1063 out.report.area_after += before;
1064 Ok(())
1065}
1066
1067fn fit_card(
1069 input: &Input<'_>,
1070 store: &mut Store<'_>,
1071 work: &mut Work,
1072 s: &mut Scratch,
1073 polygons: &mut Vec<Point>,
1074) -> Result<Fit, Error> {
1075 let mut scale: f64 = 1.0;
1076 let (mut ymin, mut ymax) = (f64::INFINITY, f64::NEG_INFINITY);
1077 s.points.clear();
1078 for tri in &s.tris {
1079 for p in tri.p {
1080 scale = scale.max(p[0].abs()).max(p[1].abs());
1081 ymin = ymin.min(p[1]);
1082 ymax = ymax.max(p[1]);
1083 store.push(&mut s.points, p)?;
1084 }
1085 }
1086 let pad = input.padding + scale * MARGIN_SCALE;
1087 let eps = 1e-9 * scale;
1088 convex_hull(store, work, &mut s.points, &mut s.dom)?;
1089 if s.dom.len() < 3 {
1090 return Ok(Fit {
1091 kind: FitKind::Keep,
1092 opaque: 0,
1093 });
1094 }
1095
1096 let j0 = to_i64(libm::ceil(ymin - 1.0 - pad))?;
1099 let j1 = to_i64(libm::floor(ymax + pad))?;
1100 let rows = usize::try_from(j1 - j0 + 1).map_err(|_| Error::SizeOverflow)?;
1101 store.fill(&mut s.rows, rows, (i64::MAX, i64::MIN))?;
1102 let mut opaque = 0u64;
1103 let threshold = input.threshold;
1104 for tri in &s.tris {
1105 let ty0 = tri.p[0][1].min(tri.p[1][1]).min(tri.p[2][1]);
1106 let ty1 = tri.p[0][1].max(tri.p[1][1]).max(tri.p[2][1]);
1107 let r0 = to_i64(libm::ceil(ty0 - 1.0 - pad))?;
1108 let r1 = to_i64(libm::floor(ty1 + pad))?;
1109 for j in r0..=r1 {
1110 let y = j as f64;
1111 let row = usize::try_from(j - j0).map_err(|_| Error::SizeOverflow)?;
1112 if let Some((a, b)) = strip_range(&tri.p, y - pad, y + 1.0 + pad) {
1113 let i0 = to_i64(libm::ceil(a - 1.0 - pad))?;
1114 let i1 = to_i64(libm::floor(b + pad))?;
1115 if i1 >= i0 {
1116 work.add(usize::try_from(i1 - i0 + 1).map_err(|_| Error::SizeOverflow)?)?;
1117 }
1118 let (mut lo, mut hi) = s.rows[row];
1119 for i in i0..=i1 {
1120 if input.mask.texel(i, j, input.wrap) >= threshold {
1121 lo = lo.min(i);
1122 hi = hi.max(i);
1123 }
1124 }
1125 s.rows[row] = (lo, hi);
1126 }
1127 if let Some((c, d)) = strip_range(&tri.p, y + 0.5, y + 0.5) {
1128 let i0 = to_i64(libm::ceil(c - 0.5))?;
1129 let i1 = to_i64(libm::ceil(d - 0.5))? - 1;
1130 for i in i0..=i1 {
1131 if input.mask.texel(i, j, input.wrap) >= threshold {
1132 opaque += 1;
1133 }
1134 }
1135 }
1136 }
1137 }
1138 s.points.clear();
1139 for (row, &(lo, hi)) in s.rows.iter().enumerate() {
1140 if lo > hi {
1141 continue;
1142 }
1143 let y = (j0 + i64::try_from(row).map_err(|_| Error::SizeOverflow)?) as f64;
1144 let (x0, x1) = (lo as f64 - pad, hi as f64 + 1.0 + pad);
1145 let (y0, y1) = (y - pad, y + 1.0 + pad);
1146 for p in [[x0, y0], [x0, y1], [x1, y0], [x1, y1]] {
1147 store.push(&mut s.points, p)?;
1148 }
1149 }
1150 let empty = Fit {
1151 kind: FitKind::Empty,
1152 opaque,
1153 };
1154 if s.points.is_empty() {
1155 return Ok(empty);
1156 }
1157 convex_hull(store, work, &mut s.points, &mut s.hull)?;
1158 clip_convex(store, &mut s.hull, &s.dom, &mut s.tmp)?;
1159 simplify(&mut s.hull);
1160 if s.hull.len() < 3 || area2(&s.hull) <= 0.0 {
1161 return Ok(empty);
1162 }
1163 reduce(work, &mut s.hull, &s.dom, eps)?;
1164 let found = smallest_cycle(input.budget, input.vertex_cost, store, work, s, eps)?;
1165 if !found {
1166 return Ok(Fit {
1167 kind: FitKind::Keep,
1168 opaque,
1169 });
1170 }
1171 let start = polygons.len();
1173 for i in 0..s.best.len() {
1174 let next = s.best[(i + 1) % s.best.len()] as usize;
1175 let n = s.edges.len();
1176 let mut p = s.table[s.best[i] as usize * n + next].apex;
1177 for &d in &s.dom {
1178 if (p[0] - d[0]).abs() <= eps && (p[1] - d[1]).abs() <= eps {
1179 p = d;
1180 }
1181 }
1182 if polygons.len() > start && polygons[polygons.len() - 1] == p {
1183 continue;
1184 }
1185 store.push(polygons, p)?;
1186 }
1187 while polygons.len() > start + 1 && polygons[polygons.len() - 1] == polygons[start] {
1188 polygons.pop();
1189 }
1190 let len = polygons.len() - start;
1191 if len < 3 {
1192 polygons.truncate(start);
1193 return Ok(Fit {
1194 kind: FitKind::Keep,
1195 opaque,
1196 });
1197 }
1198 Ok(Fit {
1199 kind: FitKind::Polygon(start, len),
1200 opaque,
1201 })
1202}
1203
1204fn convex_hull(
1206 store: &mut Store<'_>,
1207 work: &mut Work,
1208 points: &mut [Point],
1209 hull: &mut Vec<Point>,
1210) -> Result<(), Error> {
1211 work.add(points.len().saturating_mul(16))?;
1212 points.sort_unstable_by(|a, b| a[0].total_cmp(&b[0]).then(a[1].total_cmp(&b[1])));
1213 hull.clear();
1214 store.grow(hull, points.len().saturating_mul(2).saturating_add(1))?;
1215 for &p in points.iter() {
1216 while hull.len() >= 2
1217 && cross(
1218 sub(hull[hull.len() - 1], hull[hull.len() - 2]),
1219 sub(p, hull[hull.len() - 2]),
1220 ) <= 0.0
1221 {
1222 hull.pop();
1223 }
1224 hull.push(p);
1225 }
1226 let lower = hull.len() + 1;
1227 for &p in points.iter().rev().skip(1) {
1228 while hull.len() >= lower
1229 && cross(
1230 sub(hull[hull.len() - 1], hull[hull.len() - 2]),
1231 sub(p, hull[hull.len() - 2]),
1232 ) <= 0.0
1233 {
1234 hull.pop();
1235 }
1236 hull.push(p);
1237 }
1238 hull.pop();
1239 Ok(())
1240}
1241
1242fn clip_convex(
1244 store: &mut Store<'_>,
1245 poly: &mut Vec<Point>,
1246 dom: &[Point],
1247 tmp: &mut Vec<Point>,
1248) -> Result<(), Error> {
1249 let m = dom.len();
1250 for i in 0..m {
1251 let (a, b) = (dom[i], dom[(i + 1) % m]);
1252 tmp.clear();
1253 let n = poly.len();
1254 store.grow(tmp, n.saturating_add(1))?;
1255 for k in 0..n {
1256 let (p, q) = (poly[k], poly[(k + 1) % n]);
1257 let (dp, dq) = (side(a, b, p), side(a, b, q));
1258 if dp >= 0.0 {
1259 tmp.push(p);
1260 }
1261 if (dp > 0.0 && dq < 0.0) || (dp < 0.0 && dq > 0.0) {
1262 tmp.push(lerp(p, q, dp / (dp - dq)));
1263 }
1264 }
1265 core::mem::swap(poly, tmp);
1266 if poly.is_empty() {
1267 break;
1268 }
1269 }
1270 Ok(())
1271}
1272
1273fn simplify(poly: &mut Vec<Point>) {
1275 loop {
1276 let n = poly.len();
1277 if n < 3 {
1278 return;
1279 }
1280 let found = (0..n).find(|&i| {
1281 let prev = poly[(i + n - 1) % n];
1282 let next = poly[(i + 1) % n];
1283 poly[i] == prev || cross(sub(poly[i], prev), sub(next, poly[i])) <= 0.0
1284 });
1285 match found {
1286 Some(i) => {
1287 poly.remove(i);
1288 }
1289 None => return,
1290 }
1291 }
1292}
1293
1294fn reduce(work: &mut Work, poly: &mut Vec<Point>, dom: &[Point], eps: f64) -> Result<(), Error> {
1297 while poly.len() > REDUCE_TO {
1298 let n = poly.len();
1299 work.add(n.saturating_mul(dom.len() + 4))?;
1300 let mut best: Option<(f64, usize, Point)> = None;
1301 for i in 0..n {
1302 let prev = poly[(i + n - 1) % n];
1303 let (a, b) = (poly[i], poly[(i + 1) % n]);
1304 let after = poly[(i + 2) % n];
1305 let (dp, dn) = (sub(a, prev), sub(after, b));
1306 let c = cross(dp, dn);
1307 if c <= 0.0 {
1308 continue;
1309 }
1310 let t = cross(sub(b, a), dn) / c;
1311 let apex = [a[0] + t * dp[0], a[1] + t * dp[1]];
1312 if !t.is_finite() || t < 0.0 || !inside(dom, apex, eps) {
1313 continue;
1314 }
1315 let added = cross(sub(b, a), sub(apex, a)).abs();
1316 if best.is_none_or(|(cost, _, _)| added < cost) {
1317 best = Some((added, i, apex));
1318 }
1319 }
1320 let Some((_, i, apex)) = best else {
1321 return Ok(());
1322 };
1323 poly[i] = apex;
1324 poly.remove((i + 1) % n);
1325 }
1326 Ok(())
1327}
1328
1329fn smallest_cycle(
1333 budget: usize,
1334 vertex_cost: f64,
1335 store: &mut Store<'_>,
1336 work: &mut Work,
1337 s: &mut Scratch,
1338 eps: f64,
1339) -> Result<bool, Error> {
1340 let hull = &s.hull;
1341 let m = hull.len();
1342 let md = s.dom.len();
1343 s.edges.clear();
1344 for i in 0..m {
1345 let v = hull[i];
1346 let d_in = sub(v, hull[(i + m - 1) % m]);
1347 let d_out = sub(hull[(i + 1) % m], v);
1348 s.dirs.clear();
1349 let (li, lo) = (libm::sqrt(dot(d_in, d_in)), libm::sqrt(dot(d_out, d_out)));
1351 let bisector = [d_in[0] / li + d_out[0] / lo, d_in[1] / li + d_out[1] / lo];
1352 for k in 0..=md {
1353 let e = if k == md {
1354 bisector
1355 } else {
1356 sub(s.dom[(k + 1) % md], s.dom[k])
1357 };
1358 if cross(d_in, e) > 0.0 && cross(e, d_out) > 0.0 {
1359 let at = s
1360 .dirs
1361 .iter()
1362 .position(|&x| cross(e, x) > 0.0)
1363 .unwrap_or(s.dirs.len());
1364 store.grow(&mut s.dirs, 1)?;
1365 s.dirs.insert(at, e);
1366 }
1367 }
1368 for &d in &s.dirs {
1369 store.push(&mut s.edges, Edge { s: v, d, e: v })?;
1370 }
1371 store.push(
1372 &mut s.edges,
1373 Edge {
1374 s: v,
1375 d: d_out,
1376 e: hull[(i + 1) % m],
1377 },
1378 )?;
1379 }
1380 let n = s.edges.len();
1381 let cells = n.checked_mul(n).ok_or(Error::SizeOverflow)?;
1382 work.add(cells.saturating_mul(n))?;
1383 store.fill(
1384 &mut s.table,
1385 cells,
1386 Pair {
1387 ok: false,
1388 cap: 0.0,
1389 apex: [0.0; 2],
1390 },
1391 )?;
1392 for i in 0..n {
1393 let ei = s.edges[i];
1394 for step in 1..n {
1395 let j = (i + step) % n;
1396 let ej = s.edges[j];
1397 let cell = &mut s.table[i * n + j];
1398 if step == 1 {
1399 *cell = Pair {
1400 ok: true,
1401 cap: 0.0,
1402 apex: ei.e,
1403 };
1404 continue;
1405 }
1406 let c = cross(ei.d, ej.d);
1407 if c <= 0.0 {
1408 continue;
1409 }
1410 let t = cross(sub(ej.s, ei.s), ej.d) / c;
1411 let apex = [ei.s[0] + t * ei.d[0], ei.s[1] + t * ei.d[1]];
1412 if !t.is_finite() || !inside(&s.dom, apex, eps) {
1413 continue;
1414 }
1415 let mut sum = 0.0;
1417 let mut prev = sub(ei.e, apex);
1418 for k in 1..step {
1419 let p = sub(s.edges[(i + k) % n].e, apex);
1420 sum += cross(prev, p);
1421 prev = p;
1422 }
1423 *cell = Pair {
1424 ok: true,
1425 cap: sum.abs() * 0.5,
1426 apex,
1427 };
1428 }
1429 }
1430
1431 let k = budget.min(n);
1432 let layers = k + 1;
1433 let size = layers.checked_mul(n).ok_or(Error::SizeOverflow)?;
1434 work.add(size.saturating_mul(n).saturating_mul(n))?;
1435 store.fill(&mut s.cost, size, f64::INFINITY)?;
1436 store.fill(&mut s.parent, size, u32::MAX)?;
1437 s.best.clear();
1438 let mut best = f64::INFINITY;
1439 for start in 0..n {
1440 s.cost.fill(f64::INFINITY);
1441 s.cost[n + start] = 0.0;
1442 for c in 1..k {
1443 for j in start..n {
1444 let f = s.cost[c * n + j];
1445 if !f.is_finite() {
1446 continue;
1447 }
1448 for j2 in j + 1..n {
1449 let pair = s.table[j * n + j2];
1450 if !pair.ok {
1451 continue;
1452 }
1453 let cand = f + pair.cap;
1454 let slot = (c + 1) * n + j2;
1455 if cand < s.cost[slot] {
1456 s.cost[slot] = cand;
1457 s.parent[slot] = u32::try_from(j).map_err(|_| Error::SizeOverflow)?;
1458 }
1459 }
1460 }
1461 }
1462 for c in 3..=k {
1463 for j in start + 1..n {
1464 let f = s.cost[c * n + j];
1465 let pair = s.table[j * n + start];
1466 if !f.is_finite() || !pair.ok {
1467 continue;
1468 }
1469 let total = f + pair.cap + vertex_cost * c as f64;
1471 if total < best {
1472 best = total;
1473 s.seq.clear();
1474 let mut cur = j;
1475 for level in (2..=c).rev() {
1476 store.push(
1477 &mut s.seq,
1478 u32::try_from(cur).map_err(|_| Error::SizeOverflow)?,
1479 )?;
1480 cur = s.parent[level * n + cur] as usize;
1481 }
1482 store.push(
1483 &mut s.seq,
1484 u32::try_from(cur).map_err(|_| Error::SizeOverflow)?,
1485 )?;
1486 s.seq.reverse();
1487 s.best.clear();
1488 store.grow(&mut s.best, s.seq.len())?;
1489 s.best.extend_from_slice(&s.seq);
1490 }
1491 }
1492 }
1493 }
1494 Ok(!s.best.is_empty())
1495}
1496
1497fn convex_disk(store: &mut Store<'_>, s: &mut Scratch) -> Result<bool, Error> {
1503 let positive = s.tris[0].area2 > 0.0;
1504 if s.tris.iter().any(|t| (t.area2 > 0.0) != positive) {
1505 return Ok(false);
1506 }
1507 s.directed.clear();
1508 for tri in &s.tris {
1509 for k in 0..3 {
1510 store.push(&mut s.directed, (tri.v[k], tri.v[(k + 1) % 3]))?;
1511 }
1512 }
1513 s.directed.sort_unstable();
1514 if s.directed.windows(2).any(|w| w[0] == w[1]) {
1515 return Ok(false);
1516 }
1517 s.boundary.clear();
1518 for &(a, b) in &s.directed {
1519 if s.directed.binary_search(&(b, a)).is_err() {
1520 store.push(&mut s.boundary, (a, b))?;
1521 }
1522 }
1523 let count = s.boundary.len();
1524 if !(3..=MAX_OUTLINE).contains(&count) || s.boundary.windows(2).any(|w| w[0].0 == w[1].0) {
1525 return Ok(false);
1526 }
1527 let first = s.boundary[0].0;
1529 let mut cur = first;
1530 for step in 0..count {
1531 let Ok(at) = s.boundary.binary_search_by(|e| e.0.cmp(&cur)) else {
1532 return Ok(false);
1533 };
1534 cur = s.boundary[at].1;
1535 if cur == first && step + 1 != count {
1536 return Ok(false);
1537 }
1538 }
1539 if cur != first {
1540 return Ok(false);
1541 }
1542 let point = |v: u32| s.tris.iter().find_map(|t| t.point_of(v));
1544 let sign = if positive { 1.0 } else { -1.0 };
1545 for &(a, b) in &s.boundary {
1546 let (Some(pa), Some(pb)) = (point(a), point(b)) else {
1547 return Ok(false);
1548 };
1549 for &(z, _) in &s.boundary {
1550 let Some(pz) = point(z) else {
1551 return Ok(false);
1552 };
1553 if sign * side(pa, pb, pz) < 0.0 {
1554 return Ok(false);
1555 }
1556 }
1557 }
1558 Ok(true)
1559}
1560
1561fn bary(tri: &Tri, p: Point) -> [f64; 3] {
1563 let [a, b, c] = tri.p;
1564 let l1 = cross(sub(p, a), sub(c, a)) / tri.area2;
1565 let l2 = cross(sub(b, a), sub(p, a)) / tri.area2;
1566 [1.0 - l1 - l2, l1, l2]
1567}
1568
1569fn affine_reference(
1571 input: &Input<'_>,
1572 store: &mut Store<'_>,
1573 s: &mut Scratch,
1574) -> Result<Option<usize>, Error> {
1575 let mut r = 0;
1576 for (i, tri) in s.tris.iter().enumerate() {
1577 if tri.area2.abs() > s.tris[r].area2.abs() {
1578 r = i;
1579 }
1580 }
1581 let stride = input.stride;
1582 store.fill(
1583 &mut s.stats,
1584 stride,
1585 [f64::INFINITY, f64::NEG_INFINITY, 0.0],
1586 )?;
1587 for tri in &s.tris {
1588 for v in tri.v {
1589 for (c, &x) in input.attrs(v).iter().enumerate() {
1590 let x = f64::from(x);
1591 let st = &mut s.stats[c];
1592 st[0] = st[0].min(x);
1593 st[1] = st[1].max(x);
1594 st[2] = st[2].max(x.abs());
1595 }
1596 }
1597 }
1598 let reference = s.tris[r];
1599 let rv = reference.v.map(|v| input.attrs(v));
1600 for tri in &s.tris {
1601 for (k, v) in tri.v.into_iter().enumerate() {
1602 let w = bary(&reference, tri.p[k]);
1603 for (c, &x) in input.attrs(v).iter().enumerate() {
1604 if c == input.uv || c == input.uv + 1 {
1605 continue;
1606 }
1607 let predicted = w[0] * f64::from(rv[0][c])
1608 + w[1] * f64::from(rv[1][c])
1609 + w[2] * f64::from(rv[2][c]);
1610 let st = s.stats[c];
1611 let tolerance = 1e-5 * (st[1] - st[0]) + 4.0 * f64::from(f32::EPSILON) * st[2];
1612 if (predicted - f64::from(x)).abs() > tolerance {
1613 return Ok(None);
1614 }
1615 }
1616 }
1617 }
1618 Ok(Some(r))
1619}
1620
1621fn write_uv(input: &Input<'_>, values: &mut [f32], p: Point) {
1622 values[input.uv] = (p[0] / input.w) as f32;
1623 values[input.uv + 1] = (p[1] / input.h) as f32;
1624}
1625
1626fn bary_vertex(
1627 input: &Input<'_>,
1628 store: &mut Store<'_>,
1629 values: &mut Vec<f32>,
1630 tri: &Tri,
1631 p: Point,
1632) -> Result<(), Error> {
1633 let w = bary(tri, p);
1634 let a = tri.v.map(|v| input.attrs(v));
1635 values.clear();
1636 store.grow(values, input.stride)?;
1637 for ((&x, &y), &z) in a[0].iter().zip(a[1]).zip(a[2]) {
1638 values.push((w[0] * f64::from(x) + w[1] * f64::from(y) + w[2] * f64::from(z)) as f32);
1639 }
1640 write_uv(input, values, p);
1641 Ok(())
1642}
1643
1644fn emit_triangle(
1645 store: &mut Store<'_>,
1646 out: &mut Output,
1647 points: [Point; 3],
1648 ids: [u32; 3],
1649 positive: bool,
1650) -> Result<(), Error> {
1651 if cross(sub(points[1], points[0]), sub(points[2], points[0])) == 0.0 {
1652 return Ok(());
1653 }
1654 store.grow(&mut out.indices, 3)?;
1655 if positive {
1656 out.indices.extend_from_slice(&ids);
1657 } else {
1658 out.indices.extend_from_slice(&[ids[0], ids[2], ids[1]]);
1659 }
1660 Ok(())
1661}
1662
1663fn emit_polygon(
1665 input: &Input<'_>,
1666 store: &mut Store<'_>,
1667 out: &mut Output,
1668 s: &mut Scratch,
1669 q: &[Point],
1670 r: usize,
1671) -> Result<(), Error> {
1672 let reference = s.tris[r];
1673 let positive = reference.area2 > 0.0;
1674 s.seq.clear();
1675 for &p in q {
1676 let corner = s
1677 .tris
1678 .iter()
1679 .find_map(|t| (0..3).find(|&k| t.p[k] == p).map(|k| t.v[k]));
1680 let id = match corner {
1681 Some(v) => copy_vertex(input, store, out, v)?,
1682 None => {
1683 bary_vertex(input, store, &mut s.values, &reference, p)?;
1684 push_vertex(input, store, out, &s.values)?
1685 }
1686 };
1687 store.push(&mut s.seq, id)?;
1688 }
1689 for m in 1..q.len() - 1 {
1690 emit_triangle(
1691 store,
1692 out,
1693 [q[0], q[m], q[m + 1]],
1694 [s.seq[0], s.seq[m], s.seq[m + 1]],
1695 positive,
1696 )?;
1697 }
1698 Ok(())
1699}
1700
1701fn clip_pieces(
1703 store: &mut Store<'_>,
1704 work: &mut Work,
1705 s: &mut Scratch,
1706 q: &[Point],
1707) -> Result<f64, Error> {
1708 s.pieces.clear();
1709 s.ends.clear();
1710 let mut total = 0.0;
1711 for ti in 0..s.tris.len() {
1712 let tri = s.tris[ti];
1713 let local = u32::try_from(ti).map_err(|_| Error::SizeOverflow)?;
1714 work.add(q.len().saturating_add(6).saturating_mul(3))?;
1715 s.a.clear();
1716 for (k, &p) in q.iter().enumerate() {
1717 let k = u32::try_from(k).map_err(|_| Error::SizeOverflow)?;
1718 store.push(
1719 &mut s.a,
1720 WVert {
1721 p,
1722 key: Key::Corner(k, local),
1723 line: Line::Fit(k),
1724 },
1725 )?;
1726 }
1727 for e in 0..3 {
1728 let (lo, hi, plo, phi) = tri.edge(e);
1729 let sign = tri.sigma[e];
1730 s.b.clear();
1731 let n = s.a.len();
1732 store.grow(&mut s.b, n.saturating_mul(2))?;
1733 for m in 0..n {
1734 let cur = s.a[m];
1735 let next = s.a[(m + 1) % n];
1736 let dc = sign * side(plo, phi, cur.p);
1737 let dn = sign * side(plo, phi, next.p);
1738 if dc >= 0.0 {
1739 let line = if dc == 0.0 && dn < 0.0 {
1740 Line::Edge(lo, hi)
1741 } else {
1742 cur.line
1743 };
1744 s.b.push(WVert { line, ..cur });
1745 }
1746 if (dc > 0.0 && dn < 0.0) || (dc < 0.0 && dn > 0.0) {
1747 let (p, key) = crossing(q, &tri, cur, next, (lo, hi, plo, phi))?;
1748 let line = if dc > 0.0 {
1749 Line::Edge(lo, hi)
1750 } else {
1751 cur.line
1752 };
1753 s.b.push(WVert { p, key, line });
1754 }
1755 }
1756 core::mem::swap(&mut s.a, &mut s.b);
1757 if s.a.is_empty() {
1758 break;
1759 }
1760 }
1761 for w in &mut s.a {
1765 if let Key::Corner(k, _) = w.key {
1766 if let Some(c) = (0..3).find(|&c| tri.p[c] == w.p) {
1767 w.key = Key::Original(tri.v[c]);
1768 } else if let Some((lo, hi)) = (0..3).find_map(|e| {
1769 let (lo, hi, plo, phi) = tri.edge(e);
1770 (side(plo, phi, w.p) == 0.0).then_some((lo, hi))
1771 }) {
1772 w.key = Key::OnEdge(k, lo, hi);
1773 }
1774 }
1775 }
1776 s.a.dedup_by(|x, y| x.key == y.key);
1777 while s.a.len() > 1 && s.a[0].key == s.a[s.a.len() - 1].key {
1778 s.a.pop();
1779 }
1780 if s.a.len() < 3 {
1781 continue;
1782 }
1783 let mut twice = 0.0;
1784 let origin = s.a[0].p;
1785 for pair in s.a.windows(2) {
1786 twice += cross(sub(pair[0].p, origin), sub(pair[1].p, origin));
1787 }
1788 total += twice * 0.5;
1789 store.grow(&mut s.pieces, s.a.len())?;
1790 s.pieces.extend_from_slice(&s.a);
1791 store.push(&mut s.ends, (s.pieces.len(), ti))?;
1792 }
1793 Ok(total)
1794}
1795
1796fn crossing(
1799 q: &[Point],
1800 tri: &Tri,
1801 cur: WVert,
1802 next: WVert,
1803 edge: (u32, u32, Point, Point),
1804) -> Result<(Point, Key), Error> {
1805 let (lo, hi, plo, phi) = edge;
1806 match cur.line {
1807 Line::Fit(k) => {
1808 let m = q.len();
1809 let a = q[k as usize];
1810 let b = q[(k as usize + 1) % m];
1811 let (da, db) = (side(plo, phi, a), side(plo, phi, b));
1812 let p = if da != db {
1813 lerp(a, b, (da / (da - db)).clamp(0.0, 1.0))
1814 } else {
1815 let (dc, dn) = (side(plo, phi, cur.p), side(plo, phi, next.p));
1816 lerp(cur.p, next.p, dc / (dc - dn))
1817 };
1818 Ok((p, Key::Cross(k, lo, hi)))
1819 }
1820 Line::Edge(a, b) => {
1821 let common = if a == lo || a == hi { a } else { b };
1822 if common != lo && common != hi {
1823 return Err(Error::NumericalFailure);
1824 }
1825 let p = tri.point_of(common).ok_or(Error::NumericalFailure)?;
1826 Ok((p, Key::Original(common)))
1827 }
1828 }
1829}
1830
1831fn emit_pieces(
1832 input: &Input<'_>,
1833 store: &mut Store<'_>,
1834 out: &mut Output,
1835 s: &mut Scratch,
1836) -> Result<(), Error> {
1837 s.keymap.clear();
1838 let mut begin = 0;
1839 for e in 0..s.ends.len() {
1840 let (end, ti) = s.ends[e];
1841 let tri = s.tris[ti];
1842 s.seq.clear();
1843 for w in begin..end {
1844 let vert = s.pieces[w];
1845 let id = match vert.key {
1846 Key::Original(v) => copy_vertex(input, store, out, v)?,
1847 key => match s.keymap.get(&key) {
1848 Some(&id) => id,
1849 None => {
1850 match key {
1851 Key::Cross(_, lo, hi) | Key::OnEdge(_, lo, hi) => {
1852 let (plo, phi) = (input.texel(lo), input.texel(hi));
1853 let d = sub(phi, plo);
1854 let t = dot(sub(vert.p, plo), d) / dot(d, d);
1855 let (alo, ahi) = (input.attrs(lo), input.attrs(hi));
1856 s.values.clear();
1857 store.grow(&mut s.values, input.stride)?;
1858 for c in 0..input.stride {
1859 let (x, y) = (f64::from(alo[c]), f64::from(ahi[c]));
1860 s.values.push((x + t * (y - x)) as f32);
1861 }
1862 write_uv(input, &mut s.values, vert.p);
1863 }
1864 _ => bary_vertex(input, store, &mut s.values, &tri, vert.p)?,
1865 }
1866 let id = push_vertex(input, store, out, &s.values)?;
1867 store.charge(64)?;
1868 s.keymap.insert(key, id);
1869 id
1870 }
1871 },
1872 };
1873 store.push(&mut s.seq, id)?;
1874 }
1875 let positive = tri.area2 > 0.0;
1876 let piece = &s.pieces[begin..end];
1877 for m in 1..piece.len() - 1 {
1878 emit_triangle(
1879 store,
1880 out,
1881 [piece[0].p, piece[m].p, piece[m + 1].p],
1882 [s.seq[0], s.seq[m], s.seq[m + 1]],
1883 positive,
1884 )?;
1885 }
1886 begin = end;
1887 }
1888 Ok(())
1889}