Skip to main content

meshoptimizer_rs/
cutout.rs

1//! Alpha-cutout card trimming. An extension, not in C++ meshoptimizer.
2//!
3//! Each card (edge-connected triangles) is replaced by a convex polygon in
4//! texture space that contains every texel footprint whose alpha passes the
5//! threshold, with at most a caller-chosen number of vertices: the problem
6//! solved by Emil Persson's particle trimmer
7//! (<http://www.humus.name/index.php?page=Cool&ID=8>, 2009). This
8//! implementation takes the convex hull of the opaque texels, then chooses a
9//! subset of its supporting lines (hull edges, corner bisectors and lines
10//! parallel to the card outline) whose intersection has the smallest area. A
11//! greedy pass first reduces long hulls and an exact dynamic program then
12//! picks the best cycle of lines.
13use 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
21/// Largest accepted texel coordinate magnitude (`2^24`).
22const MAX_COORD: f64 = 16_777_216.0;
23/// Largest accepted padding in texels.
24const MAX_PADDING: f32 = 64.0;
25/// Largest accepted vertex budget.
26const MAX_BUDGET: u32 = 16;
27/// Hulls with more edges are greedily reduced before the exact search.
28const REDUCE_TO: usize = 24;
29/// Cards with longer outlines skip the single-polygon output.
30const MAX_OUTLINE: usize = 64;
31/// Fixed footprint margin in texels on top of the caller padding.
32const MARGIN: f64 = 1.0 / 256.0;
33/// Scale-relative footprint margin, larger than f32 rounding of output UVs.
34const MARGIN_SCALE: f64 = 1.0 / 4_194_304.0;
35/// A card is trimmed only when its area shrinks by more than this fraction
36/// and by more than the rounding of the two area sums.
37const MIN_GAIN: f64 = 1e-9;
38
39/// Texel lookup outside `0..width` and `0..height`. Not in C++ meshoptimizer.
40#[derive(Clone, Copy, Debug, Default, PartialEq, Eq)]
41#[non_exhaustive]
42pub enum AlphaWrap {
43    /// Use the nearest edge texel (clamp to edge). Default.
44    #[default]
45    Clamp,
46    /// Repeat the mask in both directions.
47    Repeat,
48}
49
50/// Read-only 8-bit alpha plane for [`trim_alpha_cards`]. Not in C++ meshoptimizer.
51///
52/// Texel `(x, y)` is `data[y * pitch + x * stride]` and covers
53/// `[x, x + 1) x [y, y + 1)` in texel space, which is `(u * width, v * height)`:
54/// `v = 0` is the first row and texel centers lie at half-integer
55/// coordinates, as in [`opacity_map_rasterize`](crate::opacity_map_rasterize).
56#[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    /// A tightly packed plane of `width * height` alpha bytes.
68    ///
69    /// # Errors
70    /// `InvalidParameter` for a zero dimension, `InvalidLayout` if `data` is
71    /// too short, or `SizeOverflow`.
72    #[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    /// A strided view, such as the alpha byte of RGBA8 data
79    /// (`&rgba[3..]`, stride 4, pitch `4 * width`).
80    ///
81    /// # Errors
82    /// `InvalidParameter` for a zero dimension or stride, `InvalidLayout` if
83    /// `data` does not contain the last texel, or `SizeOverflow`.
84    #[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    /// Width in texels.
114    #[inline]
115    pub const fn width(&self) -> u32 {
116        self.width
117    }
118
119    /// Height in texels.
120    #[inline]
121    pub const fn height(&self) -> u32 {
122        self.height
123    }
124
125    /// Alpha of texel `(x, y)`, or `None` outside the mask.
126    #[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/// Settings for [`trim_alpha_cards`]. Not in C++ meshoptimizer.
150#[derive(Clone, Copy, Debug, PartialEq)]
151#[non_exhaustive]
152pub struct CardTrimOptions {
153    /// Texels with alpha at or above this value are visible (default 128,
154    /// the byte form of a 0.5 cutoff). Zero keeps every card unchanged.
155    pub threshold: u8,
156    /// Most vertices of the fitted polygon per card, 3..=16 (default 8).
157    pub max_vertices: u32,
158    /// Footprint expansion in texels around each visible texel, finite and
159    /// within 0..=64 (default 0.5). 0.5 covers bilinear sampling of the full
160    /// resolution mask; 0 covers nearest sampling. For box-filtered mip level
161    /// `L` use `1.5 * 2^L - 1`. Alpha rescaled per mip is not covered.
162    pub padding: f32,
163    /// Lookup outside the mask (default [`AlphaWrap::Clamp`]).
164    pub wrap: AlphaWrap,
165    /// Cost of one polygon vertex in square mask texels, finite and at least
166    /// zero (default 0, always use the full budget). A card takes the vertex
167    /// count `c` that minimizes `polygon area + vertex_cost * c`, so a vertex
168    /// is added only while it removes at least this much transparent area.
169    /// Where the area saved per extra vertex never grows with the count (the
170    /// usual case) this is the same as stopping at the first vertex that saves
171    /// less than the cost. Ties go to fewer vertices. The cost is compared
172    /// with the area of the fitted polygon, before the per-triangle clipping
173    /// of split cards.
174    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/// Counts and texture-space areas. Not in C++ meshoptimizer.
190///
191/// Areas are in square texels of the mask. Cards cover `area_before` before
192/// and `area_after` after trimming; passthrough triangles are not counted.
193#[derive(Clone, Copy, Debug, Default, PartialEq)]
194#[non_exhaustive]
195pub struct CardTrimReport {
196    /// Input triangles.
197    pub input_triangles: usize,
198    /// Output triangles.
199    pub output_triangles: usize,
200    /// Output vertices.
201    pub output_vertices: usize,
202    /// Cards: edge-connected triangles with nonzero texture area.
203    pub cards: usize,
204    /// Cards replaced by a smaller polygon.
205    pub trimmed_cards: usize,
206    /// Trimmed cards emitted as one clipped polygon per source triangle,
207    /// because their attributes are not one affine function of UV or the
208    /// card is not a convex disk in texture space.
209    pub split_cards: usize,
210    /// Cards without visible texels, dropped from the output.
211    pub removed_cards: usize,
212    /// Cards copied unchanged: no smaller polygon within the vertex budget.
213    pub unchanged_cards: usize,
214    /// Triangles with zero texture area, copied unchanged.
215    pub passthrough_triangles: usize,
216    /// Texture area of the cards before trimming.
217    pub area_before: f64,
218    /// Texture area of the cards after trimming.
219    pub area_after: f64,
220    /// Visible texels whose centers lie inside a card triangle, counted per
221    /// triangle; an estimate of the visible area within `area_before`.
222    pub opaque_texels: u64,
223}
224
225/// Trimmed vertex and index buffers. Not in C++ meshoptimizer.
226#[derive(Clone, Debug, Default, PartialEq)]
227#[non_exhaustive]
228pub struct TrimmedCardsGeneric<I: crate::Index = u32> {
229    /// Output vertices with the input stride, in first-use order.
230    pub vertices: Vec<f32>,
231    /// Output triangles.
232    pub indices: Vec<I>,
233    /// Counts and areas.
234    pub report: CardTrimReport,
235    /// Vertices per card, one entry per card in the order of each card's
236    /// first triangle in the input (`report.cards` entries): the fitted
237    /// polygon's vertex count for a trimmed card (a split card is clipped
238    /// into more output vertices than this), 0 for a removed card, and the
239    /// number of distinct vertices for an unchanged card.
240    pub card_vertices: Vec<u32>,
241}
242
243/// The source-compatible u32 form of [`TrimmedCardsGeneric`].
244/// Trimmed vertex and index buffers. Not in C++ meshoptimizer.
245#[derive(Clone, Debug, Default, PartialEq)]
246#[non_exhaustive]
247pub struct TrimmedCards {
248    /// Output vertices with the input stride, in first-use order.
249    pub vertices: Vec<f32>,
250    /// Output triangles.
251    pub indices: Vec<u32>,
252    /// Counts and areas.
253    pub report: CardTrimReport,
254    /// Vertices per card; see [`TrimmedCardsGeneric::card_vertices`].
255    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/// Fit alpha-tested cards to their visible texels. Not in C++ meshoptimizer.
295///
296/// `vertices` holds `vertex_stride` floats per vertex with the UV pair at
297/// float offset `uv_offset`; every float is an attribute. A card is a set of
298/// triangles connected through shared edges (equal vertex index pairs) with
299/// nonzero texture area; any triangle soup is accepted. For each card the
300/// visible region is the union of the footprints of texels with
301/// `alpha >= threshold`, each expanded by `padding` texels, intersected with
302/// the card. It is replaced by a convex polygon with at most `max_vertices`
303/// vertices that contains this region and lies inside the convex hull of the
304/// card's UVs, chosen to minimize area among intersections of supporting
305/// lines of the visible texels' convex hull (hull edges, corner bisectors and
306/// lines parallel to the card outline), as in Persson's particle trimmer.
307/// This is not guaranteed to be the global minimum. Cards without visible
308/// texels are removed; cards without a smaller polygon are copied.
309///
310/// A card whose triangles form a convex disk in texture space and whose
311/// attributes are one affine function of UV (a planar card with linear
312/// attributes) becomes one polygon of at most `max_vertices` vertices,
313/// fan-triangulated. Other cards are clipped per source triangle and each
314/// piece is interpolated with that triangle's own barycentrics, so rendering
315/// is unchanged inside the kept area; such cards may exceed the vertex budget.
316/// Shared edge crossings are computed once per edge so pieces stay watertight;
317/// pieces share new vertices only through equal input vertices or edges, so
318/// triangles that merely touch or overlap in UV keep their own attributes.
319/// Output winding matches each source triangle. Attributes are interpolated
320/// linearly in f64; normals are not renormalized.
321///
322/// Coverage: every point of a visible footprint inside a card triangle lies
323/// inside the output, including a margin of `1/256 + |texel coordinate| / 2^22`
324/// texels that absorbs f32 rounding of output UVs. Where the footprint reaches
325/// the card's own outline, the output edge follows the input edge up to f32
326/// rounding of the new vertices. Visibility assumes the GPU alpha test sees
327/// interpolated alpha no larger than the maximum of the texels it filters,
328/// which holds for nearest and bilinear filtering of this mask.
329///
330/// Work is proportional to the padded texel area of each distinct card
331/// (cards with identical UV triangles reuse one fit) plus at most
332/// `O(max_vertices * n^3)` for `n` reduced hull edges. Storage and work are
333/// fallibly charged to the workspace. The result is deterministic.
334///
335/// ```
336/// use meshoptimizer_rs::{trim_alpha_cards, AlphaMask, CardTrimOptions, Workspace};
337/// // An 8x8 mask with a visible 2x2 block in the middle.
338/// let mut alpha = [0u8; 64];
339/// for y in 3..5 {
340///     for x in 3..5 {
341///         alpha[y * 8 + x] = 255;
342///     }
343/// }
344/// let mask = AlphaMask::new(&alpha, 8, 8)?;
345/// // One quad card: x, y, z, u, v per vertex.
346/// let vertices = [
347///     0., 0., 0., 0., 0., 1., 0., 0., 1., 0., 1., 1., 0., 1., 1., 0., 1., 0., 0., 1.,
348/// ];
349/// let trimmed = trim_alpha_cards(&[0, 1, 2, 0, 2, 3], &vertices, 5, 3, mask,
350///     CardTrimOptions::default(), &mut Workspace::default())?;
351/// assert_eq!(trimmed.report.trimmed_cards, 1);
352/// assert!(trimmed.report.area_after < 10.0 && trimmed.report.area_before == 64.0);
353/// # Ok::<(), meshoptimizer_rs::Error>(())
354/// ```
355///
356/// # Errors
357/// `InvalidTopology` for an incomplete triangle, `IndexOutOfBounds` for an
358/// invalid index, `InvalidLayout` when `uv_offset + 2 > vertex_stride` or the
359/// vertex buffer is not a whole number of vertices, `InvalidParameter` for
360/// invalid options or a texel coordinate beyond `2^24`, `NumericalFailure`
361/// for a non-finite referenced float, `IndexOverflow` when the output does
362/// not fit `I`, and the usual `SizeOverflow`, `LimitExceeded` or
363/// `AllocationFailed`. No partial result is returned.
364#[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/// The source-compatible u32 entry point; see [`trim_alpha_cards_generic`] for selectable index widths.
389#[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// ---------------------------------------------------------------------------
412// Geometry helpers.
413
414#[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/// Canonical side of `p` relative to the directed line `lo -> hi`.
435#[inline(always)]
436fn side(lo: Point, hi: Point, p: Point) -> f64 {
437    cross(sub(hi, lo), sub(p, lo))
438}
439
440/// Twice the signed area.
441fn 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
460/// Is `p` inside the convex counter-clockwise polygon, within `eps`?
461fn 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
471/// X range of a triangle within the horizontal strip `y0..=y1`.
472fn 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
492// ---------------------------------------------------------------------------
493// Fallible storage charged to the workspace.
494
495struct 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
536// ---------------------------------------------------------------------------
537// Input and per-card state.
538
539struct 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    /// Interior side of each edge `k` (`v[k] -> v[k + 1]`) relative to the
575    /// canonical direction from the lower to the higher vertex index.
576    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    /// Canonical edge `k`: lower index, higher index and their points.
610    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    /// An input vertex.
627    Original(u32),
628    /// Fitted-polygon edge `k` crossing the canonical input edge.
629    Cross(u32, u32, u32),
630    /// Fitted-polygon vertex inside one card triangle (local index).
631    Corner(u32, u32),
632    /// Fitted-polygon vertex `k` on the canonical input edge.
633    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 of the edge leaving this vertex.
647    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
712// ---------------------------------------------------------------------------
713// Driver.
714
715fn 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    // Group valid triangles into cards through shared edges.
783    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    // Members of each card in triangle order, grouped by root.
807    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// ---------------------------------------------------------------------------
954// One card.
955
956#[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    // Areas summed from different vertex orders differ by rounding of the
1008    // cross products, which dominates for slivers; such a difference is no gain.
1009    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
1067/// Visible-texel hull, then the smallest polygon within the budget.
1068fn 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    // Leftmost and rightmost visible texel per row whose padded footprint
1097    // meets a card triangle; texels with centers inside a triangle counted.
1098    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    // Snap to outline corners and drop repeated points.
1172    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
1204/// Monotone-chain convex hull, counter-clockwise, collinear points removed.
1205fn 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
1242/// Clip a convex polygon to a convex counter-clockwise domain.
1243fn 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
1273/// Drop repeated points and non-convex (collinear) corners.
1274fn 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
1294/// Greedily remove the edge whose removal adds the least area while the hull
1295/// has more than [`REDUCE_TO`] edges and the new corner stays in the domain.
1296fn 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
1329/// Exact search over cycles of supporting lines: hull edges plus zero-length
1330/// edges parallel to the card outline or bisecting a hull corner. Leaves the
1331/// chosen edges in `s.best`.
1332fn 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        // The exterior-angle bisector touches the hull at this vertex only.
1350        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            // Area between the hull chain e_i .. s_j and the apex.
1416            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                // Zero cost adds exactly 0.0, so the score is the plain area.
1470                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
1497// ---------------------------------------------------------------------------
1498// Output for one fitted card.
1499
1500/// Triangles with one orientation whose boundary is one convex loop over
1501/// distinct vertices: they cover the convex hull of their UVs exactly once.
1502fn 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    // One cycle through every boundary edge.
1528    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    // Convex: every boundary vertex on the inner side of every boundary edge.
1543    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
1561/// Barycentric weights of `p` in `tri`.
1562fn 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
1569/// Reference triangle when every card attribute is one affine function of UV.
1570fn 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
1663/// One fan-triangulated polygon interpolated with the reference triangle.
1664fn 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
1701/// Clip the fitted polygon by each card triangle into `s.pieces`; returns the total area.
1702fn 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        // A fitted corner on the triangle outline is shared only with
1762        // triangles that own the same input vertex or edge: triangles that
1763        // merely touch it in UV (folded cards, seams) have other attributes.
1764        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
1796/// Intersection of the working edge `cur -> next` with a canonical triangle
1797/// edge, computed from the original lines so neighbours agree bit for bit.
1798fn 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}