Skip to main content

meshoptimizer_rs/
remap.rs

1//! Index generation and fetch processing from upstream indexgenerator.cpp and
2//! vfetchoptimizer.cpp. Hash probing and callback traversal match upstream.
3use crate::budget::Budget;
4use crate::workspace::{checked_bytes, topology, Work};
5use crate::{Error, Positions, Workspace};
6use alloc::vec::Vec;
7
8const NONE: u32 = u32::MAX;
9
10/// Initialized byte records used as binary equality keys. Supplied padding is
11/// part of equality; no typed object is reinterpreted as bytes.
12#[derive(Clone, Copy, Debug)]
13pub struct VertexStream<'a> {
14    data: &'a [u8],
15    count: usize,
16    size: usize,
17    stride: usize,
18    offset: usize,
19}
20impl<'a> VertexStream<'a> {
21    /// Validate a stream with a key size of 1 through 256 bytes. Stride may
22    /// exceed 256; only the key bytes participate in equality.
23    ///
24    /// # Errors
25    /// `InvalidLayout` for invalid record size, stride, offset or length; `SizeOverflow` for overflowing view sizes.
26    pub fn new(
27        data: &'a [u8],
28        count: usize,
29        size: usize,
30        stride: usize,
31        offset: usize,
32    ) -> Result<Self, Error> {
33        if size == 0 || size > 256 || stride < size {
34            return Err(Error::InvalidLayout);
35        }
36        let end = if count == 0 {
37            offset
38        } else {
39            (count - 1)
40                .checked_mul(stride)
41                .and_then(|v| v.checked_add(offset))
42                .and_then(|v| v.checked_add(size))
43                .ok_or(Error::SizeOverflow)?
44        };
45        if end > data.len() {
46            return Err(Error::InvalidLayout);
47        }
48        if count > u32::MAX as usize {
49            return Err(Error::SizeOverflow);
50        }
51        Ok(Self {
52            data,
53            count,
54            size,
55            stride,
56            offset,
57        })
58    }
59    /// Validate tightly packed initialized records.
60    ///
61    /// # Errors
62    /// `InvalidLayout` for invalid record size, stride, offset or length; `SizeOverflow` for overflowing view sizes.
63    pub fn packed(data: &'a [u8], size: usize) -> Result<Self, Error> {
64        if size == 0 || !data.len().is_multiple_of(size) {
65            return Err(Error::InvalidLayout);
66        }
67        Self::new(data, data.len() / size, size, size, 0)
68    }
69    /// Number of records.
70    pub const fn len(self) -> usize {
71        self.count
72    }
73    /// Whether there are no records.
74    pub const fn is_empty(self) -> bool {
75        self.count == 0
76    }
77    #[inline(always)]
78    fn key(self, i: u32) -> &'a [u8] {
79        let start = self.offset + i as usize * self.stride;
80        &self.data[start..start + self.size]
81    }
82    #[inline(always)]
83    fn key_array<const SIZE: usize>(self, i: u32) -> &'a [u8; SIZE] {
84        let start = self.offset + i as usize * self.stride;
85        self.data[start..start + SIZE]
86            .try_into()
87            .expect("validated fixed-width key")
88    }
89}
90
91/// A compact vertex numbering; unused vertices retain `u32::MAX`.
92#[derive(Debug)]
93pub struct VertexRemap {
94    /// Original vertex to compact vertex index.
95    pub remap: Vec<u32>,
96    /// Number of unique referenced vertices.
97    pub vertex_count: usize,
98}
99/// Fetch-ordered initialized vertex bytes and rewritten indices.
100#[derive(Debug)]
101pub struct FetchedMesh {
102    /// Rewritten topology.
103    pub indices: Vec<u32>,
104    /// Used tightly packed vertex records.
105    pub vertices: Vec<u8>,
106    /// Number of used vertices.
107    pub vertex_count: usize,
108}
109/// Unique first-corner indices and source vertices for provoking-vertex rendering.
110#[derive(Debug)]
111pub struct ProvokingMesh {
112    /// Rotated and rewritten triangle indices.
113    pub indices: Vec<u32>,
114    /// Output vertex to original vertex mapping, including clones.
115    pub reorder: Vec<u32>,
116}
117
118fn buckets(n: usize) -> Result<usize, Error> {
119    n.checked_add(n / 4)
120        .ok_or(Error::SizeOverflow)?
121        .max(1)
122        .checked_next_power_of_two()
123        .ok_or(Error::SizeOverflow)
124}
125#[inline(always)]
126fn hash_update(mut h: u32, mut key: &[u8]) -> u32 {
127    const M: u32 = 0x5bd1e995;
128    while key.len() >= 4 {
129        let mut k = u32::from_le_bytes(key[..4].try_into().expect("four bytes"));
130        k = k.wrapping_mul(M);
131        k ^= k >> 24;
132        k = k.wrapping_mul(M);
133        h = h.wrapping_mul(M) ^ k;
134        key = &key[4..];
135    }
136    if !key.is_empty() {
137        h ^= u32::from(key[0])
138            | (u32::from(key[key.len() / 2]) << 8)
139            | (u32::from(key[key.len() - 1]) << 16);
140        h = h.wrapping_mul(M);
141        h ^= h >> 24;
142    }
143    h
144}
145#[inline]
146fn spatial_hash(p: [u32; 3]) -> u32 {
147    p[0].wrapping_mul(73856093) ^ p[1].wrapping_mul(19349663) ^ p[2].wrapping_mul(83492791)
148}
149#[inline(always)]
150fn position_hash(p: Positions<'_>, i: u32) -> u32 {
151    position_value_hash(p.get(i as usize).expect("validated position"))
152}
153#[inline(always)]
154fn position_value_hash(p: [f32; 3]) -> u32 {
155    spatial_hash(p.map(|v| {
156        let mut x = v.to_bits();
157        if x == 0x80000000 {
158            x = 0;
159        }
160        x ^ (x >> 17)
161    }))
162}
163#[inline(always)]
164fn validate_indices(indices: Option<&[u32]>, count: usize, work: &mut Work) -> Result<(), Error> {
165    if count > u32::MAX as usize {
166        return Err(Error::SizeOverflow);
167    }
168    if let Some(indices) = indices {
169        work.indices(indices, count)?;
170    }
171    Ok(())
172}
173fn streams_valid(streams: &[VertexStream<'_>]) -> Result<usize, Error> {
174    if streams.is_empty() || streams.len() > 16 {
175        return Err(Error::InvalidLayout);
176    }
177    let count = streams[0].count;
178    if streams.iter().any(|s| s.count != count) {
179        return Err(Error::InvalidLayout);
180    }
181    Ok(count)
182}
183#[inline]
184fn stream_hash(streams: &[VertexStream<'_>], i: u32) -> u32 {
185    streams.iter().fold(0, |h, s| hash_update(h, s.key(i)))
186}
187#[inline]
188fn stream_equal(streams: &[VertexStream<'_>], a: u32, b: u32) -> bool {
189    streams.iter().all(|s| s.key(a) == s.key(b))
190}
191#[inline(always)]
192fn generate_record<const CANONICAL: bool, const LIMITED: bool, const OUTLINE: bool>(
193    index: u32,
194    remap: &mut [u32],
195    table: &mut [u32],
196    hash: &impl Fn(u32) -> u32,
197    equal: &mut impl FnMut(u32, u32) -> bool,
198    next: &mut u32,
199    budget: (&mut Work, &mut usize),
200) -> Result<(), Error> {
201    let (work, visits) = budget;
202    if LIMITED {
203        work.add(1)?;
204    } else {
205        *visits += 1;
206    }
207    if remap[index as usize] != NONE {
208        return Ok(());
209    }
210    if OUTLINE {
211        generate_unique_outlined::<CANONICAL, LIMITED>(
212            index,
213            remap,
214            table,
215            hash,
216            equal,
217            next,
218            (work, visits),
219        )
220    } else {
221        generate_unique::<CANONICAL, LIMITED>(
222            index,
223            remap,
224            table,
225            hash,
226            equal,
227            next,
228            (work, visits),
229        )
230    }
231}
232// Keep the common already-mapped scan small for callback-heavy custom remaps.
233#[inline(never)]
234fn generate_unique_outlined<const CANONICAL: bool, const LIMITED: bool>(
235    index: u32,
236    remap: &mut [u32],
237    table: &mut [u32],
238    hash: &impl Fn(u32) -> u32,
239    equal: &mut impl FnMut(u32, u32) -> bool,
240    next: &mut u32,
241    budget: (&mut Work, &mut usize),
242) -> Result<(), Error> {
243    generate_unique::<CANONICAL, LIMITED>(index, remap, table, hash, equal, next, budget)
244}
245#[inline(always)]
246fn generate_unique<const CANONICAL: bool, const LIMITED: bool>(
247    index: u32,
248    remap: &mut [u32],
249    table: &mut [u32],
250    hash: &impl Fn(u32) -> u32,
251    equal: &mut impl FnMut(u32, u32) -> bool,
252    next: &mut u32,
253    budget: (&mut Work, &mut usize),
254) -> Result<(), Error> {
255    let (work, visits) = budget;
256    let mask = table.len() - 1;
257    let mut bucket = hash(index) as usize & mask;
258    let mut found = false;
259    for probe in 0..table.len() {
260        if LIMITED {
261            work.add(1)?;
262        } else {
263            *visits += 1;
264        }
265        if table[bucket] == NONE || equal(table[bucket], index) {
266            found = true;
267            break;
268        }
269        bucket = (bucket + probe + 1) & mask;
270    }
271    if !found {
272        return Err(Error::NumericalFailure);
273    }
274    if table[bucket] == NONE {
275        table[bucket] = index;
276        if CANONICAL {
277            remap[index as usize] = index;
278        } else {
279            remap[index as usize] = *next;
280            *next += 1;
281        }
282    } else if CANONICAL {
283        remap[index as usize] = table[bucket];
284    } else {
285        remap[index as usize] = remap[table[bucket] as usize];
286    }
287    Ok(())
288}
289fn generate_kernel<const CANONICAL: bool, const PREPARED: bool, const OUTLINE: bool>(
290    remap: &mut [u32],
291    indices: Option<&[u32]>,
292    table: &mut [u32],
293    hash: impl Fn(u32) -> u32,
294    equal: impl FnMut(u32, u32) -> bool,
295    work: &mut Work,
296) -> Result<usize, Error> {
297    // Select indexed/linear traversal once, outside the bounded hash batches.
298    if let Some(indices) = indices {
299        generate_custom_kernel::<CANONICAL, PREPARED, true>(
300            remap, indices, table, hash, equal, work,
301        )
302    } else {
303        generate_custom_kernel::<CANONICAL, PREPARED, false>(remap, &[], table, hash, equal, work)
304    }
305}
306fn generate_custom_kernel<const CANONICAL: bool, const PREPARED: bool, const INDEXED: bool>(
307    remap: &mut [u32],
308    indices: &[u32],
309    table: &mut [u32],
310    hash: impl Fn(u32) -> u32,
311    mut equal: impl FnMut(u32, u32) -> bool,
312    work: &mut Work,
313) -> Result<usize, Error> {
314    work.add(remap.len())?;
315    if !PREPARED {
316        remap.fill(NONE);
317    }
318    work.add(table.len())?;
319    table.fill(NONE);
320    let n = if INDEXED { indices.len() } else { remap.len() };
321    let bound = table.len().checked_add(1).ok_or(Error::SizeOverflow)?;
322    let mut next = 0;
323    let mut begin = 0;
324    while begin < n {
325        let count = work.batch(n - begin, bound)?;
326        let mut visits = 0;
327        if count == 0 {
328            let index = if INDEXED {
329                indices[begin]
330            } else {
331                begin as u32
332            };
333            generate_record::<CANONICAL, true, false>(
334                index,
335                remap,
336                table,
337                &hash,
338                &mut equal,
339                &mut next,
340                (work, &mut visits),
341            )?;
342            begin += 1;
343        } else {
344            let result = (|| {
345                if INDEXED {
346                    for &index in &indices[begin..begin + count] {
347                        generate_record::<CANONICAL, false, false>(
348                            index,
349                            remap,
350                            table,
351                            &hash,
352                            &mut equal,
353                            &mut next,
354                            (work, &mut visits),
355                        )?;
356                    }
357                } else {
358                    for index in begin..begin + count {
359                        generate_record::<CANONICAL, false, false>(
360                            index as u32,
361                            remap,
362                            table,
363                            &hash,
364                            &mut equal,
365                            &mut next,
366                            (work, &mut visits),
367                        )?;
368                    }
369                }
370                Ok(())
371            })();
372            work.add(visits)?;
373            result?;
374            begin += count;
375        }
376    }
377    Ok(next as usize)
378}
379fn generate<const OUTLINE: bool>(
380    remap: &mut [u32],
381    indices: Option<&[u32]>,
382    table: &mut [u32],
383    hash: impl Fn(u32) -> u32,
384    equal: impl FnMut(u32, u32) -> bool,
385    canonical: bool,
386    work: &mut Work,
387) -> Result<usize, Error> {
388    if canonical {
389        generate_kernel::<true, false, OUTLINE>(remap, indices, table, hash, equal, work)
390    } else {
391        generate_kernel::<false, false, OUTLINE>(remap, indices, table, hash, equal, work)
392    }
393}
394fn generate_streams(
395    remap: &mut [u32],
396    indices: Option<&[u32]>,
397    table: &mut [u32],
398    streams: &[VertexStream<'_>],
399    canonical: bool,
400    work: &mut Work,
401) -> Result<usize, Error> {
402    if let [vertices] = streams {
403        let vertices = *vertices;
404        match vertices.size {
405            4 => return generate_single::<4>(remap, indices, table, vertices, canonical, work),
406            8 => return generate_single::<8>(remap, indices, table, vertices, canonical, work),
407            12 => return generate_single::<12>(remap, indices, table, vertices, canonical, work),
408            16 => return generate_single::<16>(remap, indices, table, vertices, canonical, work),
409            _ => {}
410        }
411        generate::<false>(
412            remap,
413            indices,
414            table,
415            |i| hash_update(0, vertices.key(i)),
416            |a, b| vertices.key(a) == vertices.key(b),
417            canonical,
418            work,
419        )
420    } else {
421        generate::<false>(
422            remap,
423            indices,
424            table,
425            |i| stream_hash(streams, i),
426            |a, b| stream_equal(streams, a, b),
427            canonical,
428            work,
429        )
430    }
431}
432
433fn generate_single<const SIZE: usize>(
434    remap: &mut [u32],
435    indices: Option<&[u32]>,
436    table: &mut [u32],
437    vertices: VertexStream<'_>,
438    canonical: bool,
439    work: &mut Work,
440) -> Result<usize, Error> {
441    generate::<false>(
442        remap,
443        indices,
444        table,
445        |i| hash_update(0, vertices.key_array::<SIZE>(i)),
446        |a, b| vertices.key_array::<SIZE>(a) == vertices.key_array::<SIZE>(b),
447        canonical,
448        work,
449    )
450}
451
452fn shadow_kernel(
453    remap: &mut [u32],
454    indices: &[u32],
455    output: &mut [u32],
456    table: &mut [u32],
457    hash: impl Fn(u32) -> u32,
458    mut equal: impl FnMut(u32, u32) -> bool,
459    work: &mut Work,
460) -> Result<(), Error> {
461    // The shadow workspace prepares both ranges with the sentinel. Keep the
462    // original logical initialization charges and their failure order.
463    work.add(remap.len())?;
464    work.add(table.len())?;
465    let bound = table.len().checked_add(2).ok_or(Error::SizeOverflow)?;
466    let mut next = 0;
467    let mut begin = 0;
468    while begin < indices.len() {
469        let count = work.batch(indices.len() - begin, bound)?;
470        let mut visits = 0;
471        if count == 0 {
472            let index = indices[begin];
473            generate_record::<true, true, false>(
474                index,
475                remap,
476                table,
477                &hash,
478                &mut equal,
479                &mut next,
480                (work, &mut visits),
481            )?;
482            work.add(1)?;
483            output[begin] = remap[index as usize];
484            begin += 1;
485        } else {
486            let result = (|| {
487                for i in begin..begin + count {
488                    let index = indices[i];
489                    generate_record::<true, false, false>(
490                        index,
491                        remap,
492                        table,
493                        &hash,
494                        &mut equal,
495                        &mut next,
496                        (work, &mut visits),
497                    )?;
498                    visits += 1;
499                    output[i] = remap[index as usize];
500                }
501                Ok(())
502            })();
503            work.add(visits)?;
504            result?;
505            begin += count;
506        }
507    }
508    Ok(())
509}
510
511fn shadow_streams(
512    remap: &mut [u32],
513    indices: &[u32],
514    output: &mut [u32],
515    table: &mut [u32],
516    streams: &[VertexStream<'_>],
517    work: &mut Work,
518) -> Result<(), Error> {
519    if let [vertices] = streams {
520        let vertices = *vertices;
521        match vertices.size {
522            4 => return shadow_single::<4>(remap, indices, output, table, vertices, work),
523            8 => return shadow_single::<8>(remap, indices, output, table, vertices, work),
524            12 => return shadow_single::<12>(remap, indices, output, table, vertices, work),
525            16 => return shadow_single::<16>(remap, indices, output, table, vertices, work),
526            _ => {}
527        }
528        shadow_kernel(
529            remap,
530            indices,
531            output,
532            table,
533            |i| hash_update(0, vertices.key(i)),
534            |a, b| vertices.key(a) == vertices.key(b),
535            work,
536        )
537    } else {
538        shadow_kernel(
539            remap,
540            indices,
541            output,
542            table,
543            |i| stream_hash(streams, i),
544            |a, b| stream_equal(streams, a, b),
545            work,
546        )
547    }
548}
549
550fn shadow_single<const SIZE: usize>(
551    remap: &mut [u32],
552    indices: &[u32],
553    output: &mut [u32],
554    table: &mut [u32],
555    vertices: VertexStream<'_>,
556    work: &mut Work,
557) -> Result<(), Error> {
558    shadow_kernel(
559        remap,
560        indices,
561        output,
562        table,
563        |i| hash_update(0, vertices.key_array::<SIZE>(i)),
564        |a, b| vertices.key_array::<SIZE>(a) == vertices.key_array::<SIZE>(b),
565        work,
566    )
567}
568
569/// Generate compact numbering from tightly packed binary keys. `None` visits
570/// every vertex in original order; indexed input need not be a triangle list.
571///
572/// # Errors
573/// `IndexOutOfBounds` for invalid references;
574/// `SizeOverflow` for size overflow, `LimitExceeded` for exhausted limits, or `AllocationFailed` for failed reservation.
575pub fn generate_vertex_remap(
576    indices: Option<&[u32]>,
577    vertices: VertexStream<'_>,
578    workspace: &mut Workspace,
579) -> Result<VertexRemap, Error> {
580    generate_vertex_remap_multi(indices, &[vertices], workspace)
581}
582/// Generate compact numbering from one through sixteen initialized key streams.
583///
584/// # Errors
585/// `InvalidLayout` for absent or mismatched streams; `IndexOutOfBounds` for invalid references;
586/// `SizeOverflow` for size overflow, `LimitExceeded` for exhausted limits, or `AllocationFailed` for failed reservation.
587pub fn generate_vertex_remap_multi(
588    indices: Option<&[u32]>,
589    streams: &[VertexStream<'_>],
590    workspace: &mut Workspace,
591) -> Result<VertexRemap, Error> {
592    workspace.begin();
593    let count = streams_valid(streams)?;
594    if let [vertices] = streams {
595        let vertices = *vertices;
596        match vertices.size {
597            4 => return remap_alloc_single::<4>(indices, vertices, workspace),
598            8 => return remap_alloc_single::<8>(indices, vertices, workspace),
599            12 => return remap_alloc_single::<12>(indices, vertices, workspace),
600            16 => return remap_alloc_single::<16>(indices, vertices, workspace),
601            _ => {}
602        }
603        remap_alloc::<false>(
604            indices,
605            count,
606            |i| hash_update(0, vertices.key(i)),
607            |a, b| vertices.key(a) == vertices.key(b),
608            false,
609            workspace,
610        )
611    } else {
612        remap_alloc::<false>(
613            indices,
614            count,
615            |i| stream_hash(streams, i),
616            |a, b| stream_equal(streams, a, b),
617            false,
618            workspace,
619        )
620    }
621}
622fn remap_alloc_single<const SIZE: usize>(
623    indices: Option<&[u32]>,
624    vertices: VertexStream<'_>,
625    workspace: &mut Workspace,
626) -> Result<VertexRemap, Error> {
627    remap_alloc::<false>(
628        indices,
629        vertices.count,
630        |i| hash_update(0, vertices.key_array::<SIZE>(i)),
631        |a, b| vertices.key_array::<SIZE>(a) == vertices.key_array::<SIZE>(b),
632        false,
633        workspace,
634    )
635}
636fn remap_alloc<const OUTLINE: bool>(
637    indices: Option<&[u32]>,
638    count: usize,
639    hash: impl Fn(u32) -> u32,
640    equal: impl FnMut(u32, u32) -> bool,
641    canonical: bool,
642    workspace: &mut Workspace,
643) -> Result<VertexRemap, Error> {
644    let mut work = workspace.begin();
645    let result = (|| {
646        validate_indices(indices, count, &mut work)?;
647        let table_len = buckets(count)?;
648        let output_bytes = checked_bytes(count, 4)?;
649        workspace.prepare([table_len, 0, 0, 0], output_bytes)?;
650        let mut remap = crate::workspace::output_sentinel(count)?;
651        if remap.capacity() != count {
652            workspace.prepare([table_len, 0, 0, 0], checked_bytes(remap.capacity(), 4)?)?;
653        }
654        let vertex_count = if canonical {
655            generate_kernel::<true, true, OUTLINE>(
656                &mut remap,
657                indices,
658                &mut workspace.integers[..table_len],
659                hash,
660                equal,
661                &mut work,
662            )?
663        } else {
664            generate_kernel::<false, true, OUTLINE>(
665                &mut remap,
666                indices,
667                &mut workspace.integers[..table_len],
668                hash,
669                equal,
670                &mut work,
671            )?
672        };
673        Ok(VertexRemap {
674            remap,
675            vertex_count,
676        })
677    })();
678    workspace.finish(&work);
679    result
680}
681// Callback work must remain behind numerical position equality. Keeping the
682// call out of the probe body also avoids spilling its state on unequal keys.
683#[inline(never)]
684fn custom_equal(equal: &mut impl FnMut(u32, u32) -> bool, a: u32, b: u32) -> bool {
685    equal(a, b)
686}
687/// Generate compact numbering with a callback invoked only for numerically
688/// equal positions, in exactly upstream's hash-probe order. Signed zeros weld.
689///
690/// # Errors
691/// `IndexOutOfBounds` for invalid references; `NumericalFailure` if bounded hash probing finds no slot.
692/// `SizeOverflow` for size overflow, `LimitExceeded` for exhausted limits, or `AllocationFailed` for failed reservation.
693///
694/// # Panics
695/// Panics if the supplied callback panics.
696pub fn generate_vertex_remap_custom(
697    indices: Option<&[u32]>,
698    positions: Positions<'_>,
699    mut equal: impl FnMut(u32, u32) -> bool,
700    workspace: &mut Workspace,
701) -> Result<VertexRemap, Error> {
702    if let Some(p) = positions.packed_values() {
703        return remap_alloc::<true>(
704            indices,
705            p.len(),
706            |i| position_value_hash(p[i as usize]),
707            |a, b| p[a as usize] == p[b as usize] && custom_equal(&mut equal, a, b),
708            false,
709            workspace,
710        );
711    }
712    remap_alloc::<true>(
713        indices,
714        positions.len(),
715        |i| position_hash(positions, i),
716        |a, b| {
717            positions.get(a as usize) == positions.get(b as usize) && custom_equal(&mut equal, a, b)
718        },
719        false,
720        workspace,
721    )
722}
723/// Map each position to its first numerically equal vertex. Signed zeros weld;
724/// NaNs do not compare equal. The output refers to original indices.
725///
726/// # Errors
727/// `NumericalFailure` if bounded hash probing finds no slot.
728/// `SizeOverflow` for size overflow, `LimitExceeded` for exhausted limits, or `AllocationFailed` for failed reservation.
729pub fn generate_position_remap(
730    positions: Positions<'_>,
731    workspace: &mut Workspace,
732) -> Result<Vec<u32>, Error> {
733    if let Some(p) = positions.packed_values() {
734        return Ok(remap_alloc::<false>(
735            None,
736            p.len(),
737            |i| position_value_hash(p[i as usize]),
738            |a, b| p[a as usize] == p[b as usize],
739            true,
740            workspace,
741        )?
742        .remap);
743    }
744    Ok(remap_alloc::<false>(
745        None,
746        positions.len(),
747        |i| position_hash(positions, i),
748        |a, b| positions.get(a as usize) == positions.get(b as usize),
749        true,
750        workspace,
751    )?
752    .remap)
753}
754/// Generate compact numbering into caller storage. The tail is untouched;
755/// work exhaustion may leave the used prefix partially modified.
756///
757/// # Errors
758/// Same errors as [`generate_vertex_remap_multi`]. `BufferTooSmall` if an output buffer is too short.
759pub fn generate_vertex_remap_multi_into(
760    destination: &mut [u32],
761    indices: Option<&[u32]>,
762    streams: &[VertexStream<'_>],
763    workspace: &mut Workspace,
764) -> Result<usize, Error> {
765    let mut work = workspace.begin();
766    let result = (|| {
767        let count = streams_valid(streams)?;
768        validate_indices(indices, count, &mut work)?;
769        if destination.len() < count {
770            return Err(Error::BufferTooSmall);
771        }
772        let table_len = buckets(count)?;
773        workspace.prepare([table_len, 0, 0, 0], 0)?;
774        generate_streams(
775            &mut destination[..count],
776            indices,
777            &mut workspace.integers[..table_len],
778            streams,
779            false,
780            &mut work,
781        )
782    })();
783    workspace.finish(&work);
784    result
785}
786/// Single-stream caller-buffer compact numbering.
787///
788/// # Errors
789/// Same errors as [`generate_vertex_remap`]. `BufferTooSmall` if an output buffer is too short.
790pub fn generate_vertex_remap_into(
791    destination: &mut [u32],
792    indices: Option<&[u32]>,
793    vertices: VertexStream<'_>,
794    workspace: &mut Workspace,
795) -> Result<usize, Error> {
796    generate_vertex_remap_multi_into(destination, indices, &[vertices], workspace)
797}
798
799#[inline(always)]
800fn copy_vertex<const SIZE: usize>(
801    destination: &mut [u8],
802    vertices: VertexStream<'_>,
803    source: u32,
804    target: usize,
805) {
806    let size = if SIZE == 0 { vertices.size } else { SIZE };
807    let input = vertices.offset + source as usize * vertices.stride;
808    let output = target * size;
809    destination[output..output + size].copy_from_slice(&vertices.data[input..input + size]);
810}
811fn remap_vertex_copy<const SIZE: usize>(
812    destination: &mut [u8],
813    vertices: VertexStream<'_>,
814    remap: &[u32],
815    work: &mut Work,
816) -> Result<(), Error> {
817    if work.precharge(remap.len(), 1)? {
818        for (i, &r) in remap.iter().enumerate() {
819            if r != NONE {
820                copy_vertex::<SIZE>(destination, vertices, i as u32, r as usize);
821            }
822        }
823    } else {
824        for (i, &r) in remap.iter().enumerate() {
825            work.add(1)?;
826            if r != NONE {
827                copy_vertex::<SIZE>(destination, vertices, i as u32, r as usize);
828            }
829        }
830    }
831    Ok(())
832}
833fn remap_vertex_dispatch(
834    destination: &mut [u8],
835    vertices: VertexStream<'_>,
836    remap: &[u32],
837    work: &mut Work,
838) -> Result<(), Error> {
839    match vertices.size {
840        4 => remap_vertex_copy::<4>(destination, vertices, remap, work),
841        8 => remap_vertex_copy::<8>(destination, vertices, remap, work),
842        12 => remap_vertex_copy::<12>(destination, vertices, remap, work),
843        16 => remap_vertex_copy::<16>(destination, vertices, remap, work),
844        _ => remap_vertex_copy::<0>(destination, vertices, remap, work),
845    }
846}
847
848/// Remap initialized vertex bytes into caller storage. Repeated destinations
849/// use the last source record, matching upstream; unmapped records are untouched.
850/// Validation precedes writes; work exhaustion may leave partial output.
851///
852/// # Errors
853/// Same errors as [`remap_vertex_buffer`]. `BufferTooSmall` if an output buffer is too short.
854pub fn remap_vertex_buffer_into(
855    destination: &mut [u8],
856    vertices: VertexStream<'_>,
857    remap: &[u32],
858    workspace: &mut Workspace,
859) -> Result<(), Error> {
860    let mut work = workspace.begin();
861    let result = (|| {
862        if remap.len() != vertices.count {
863            return Err(Error::InvalidLayout);
864        }
865        let mut required = 0;
866        work.scan(remap.iter().copied(), |i| {
867            if i != NONE {
868                if i as usize >= vertices.count {
869                    return Err(Error::IndexOutOfBounds);
870                }
871                required = required.max(i as usize + 1);
872            }
873            Ok(())
874        })?;
875        if destination.len() < checked_bytes(required, vertices.size)? {
876            return Err(Error::BufferTooSmall);
877        }
878        workspace.charge_retained()?;
879        remap_vertex_dispatch(destination, vertices, remap, &mut work)?;
880        Ok(())
881    })();
882    workspace.finish(&work);
883    result
884}
885/// Allocate remapped tightly packed bytes, zero-initializing unmapped records.
886///
887/// # Errors
888/// `InvalidLayout` for a mismatched remap length; `IndexOutOfBounds` for invalid remap values;
889/// `SizeOverflow` for size overflow, `LimitExceeded` for exhausted limits, or `AllocationFailed` for failed reservation.
890pub fn remap_vertex_buffer(
891    vertices: VertexStream<'_>,
892    remap: &[u32],
893    workspace: &mut Workspace,
894) -> Result<Vec<u8>, Error> {
895    let mut work = workspace.begin();
896    let result = (|| {
897        if remap.len() != vertices.count {
898            return Err(Error::InvalidLayout);
899        }
900        let mut required = 0;
901        work.scan(remap.iter().copied(), |i| {
902            if i != NONE {
903                if i as usize >= vertices.count {
904                    return Err(Error::IndexOutOfBounds);
905                }
906                required = required.max(i as usize + 1);
907            }
908            Ok(())
909        })?;
910        let bytes = checked_bytes(required, vertices.size)?;
911        let mut budget = Budget::new(workspace);
912        let mut out = budget.filled(bytes, 0u8)?;
913        remap_vertex_dispatch(&mut out, vertices, remap, &mut work)?;
914        Ok(out)
915    })();
916    workspace.finish(&work);
917    result
918}
919/// Remap arbitrary index sequences. `None` remaps all vertices in order;
920/// references to the unused sentinel are rejected before writes.
921///
922/// # Errors
923/// Same errors as [`remap_index_buffer`]. `BufferTooSmall` if an output buffer is too short.
924pub fn remap_index_buffer_into(
925    destination: &mut [u32],
926    indices: Option<&[u32]>,
927    remap: &[u32],
928    workspace: &mut Workspace,
929) -> Result<(), Error> {
930    let mut work = workspace.begin();
931    let result = (|| {
932        let count = indices.map_or(remap.len(), <[u32]>::len);
933        if let Some(input) = indices.filter(|_| {
934            count
935                .checked_mul(2)
936                .is_some_and(|n| work.covers(n).unwrap_or(false))
937        }) {
938            if remap.len() > u32::MAX as usize {
939                return Err(Error::SizeOverflow);
940            }
941            let mut missing = None;
942            for (at, &index) in input.iter().enumerate() {
943                let Some(&value) = remap.get(index as usize) else {
944                    work.add(at + 1)?;
945                    return Err(Error::IndexOutOfBounds);
946                };
947                if value == NONE && missing.is_none() {
948                    missing = Some(at);
949                }
950            }
951            work.add(count)?;
952            if destination.len() < count {
953                return Err(Error::BufferTooSmall);
954            }
955            work.add(missing.map_or(count, |at| at + 1))?;
956            if missing.is_some() {
957                return Err(Error::InvalidParameter);
958            }
959        } else {
960            validate_indices(indices, remap.len(), &mut work)?;
961            if destination.len() < count {
962                return Err(Error::BufferTooSmall);
963            }
964            work.scan(0..count, |i| {
965                let index = indices.map_or(i as u32, |v| v[i]);
966                if remap[index as usize] == NONE {
967                    return Err(Error::InvalidParameter);
968                }
969                Ok(())
970            })?;
971        }
972        workspace.charge_retained()?;
973        if work.precharge(count, 1)? {
974            if let Some(input) = indices {
975                for (out, &index) in destination[..count].iter_mut().zip(input) {
976                    *out = remap[index as usize];
977                }
978            } else {
979                destination[..count].copy_from_slice(remap);
980            }
981        } else {
982            for (i, out) in destination[..count].iter_mut().enumerate() {
983                work.add(1)?;
984                *out = remap[indices.map_or(i as u32, |v| v[i]) as usize];
985            }
986        }
987        Ok(())
988    })();
989    workspace.finish(&work);
990    result
991}
992#[inline(always)]
993fn remap_index_copy(
994    output: &mut [u32],
995    input: impl ExactSizeIterator<Item = u32>,
996    remap: &[u32],
997    work: &mut Work,
998) -> Result<(), Error> {
999    let count = output.len();
1000    if work.covers(count)? {
1001        for (at, (out, index)) in output.iter_mut().zip(input).enumerate() {
1002            *out = remap[index as usize];
1003            if *out == NONE {
1004                work.add(at + 1)?;
1005                return Err(Error::InvalidParameter);
1006            }
1007        }
1008        work.add(count)?;
1009    } else {
1010        for (out, index) in output.iter_mut().zip(input) {
1011            work.add(1)?;
1012            *out = remap[index as usize];
1013            if *out == NONE {
1014                return Err(Error::InvalidParameter);
1015            }
1016        }
1017    }
1018    Ok(())
1019}
1020
1021/// Allocate remapped indices.
1022///
1023/// # Errors
1024/// `InvalidParameter` if unindexed remapping exceeds the remap length; `IndexOutOfBounds` for invalid references;
1025/// `SizeOverflow` for size overflow, `LimitExceeded` for exhausted limits, or `AllocationFailed` for failed reservation.
1026pub fn remap_index_buffer(
1027    indices: Option<&[u32]>,
1028    remap: &[u32],
1029    workspace: &mut Workspace,
1030) -> Result<Vec<u32>, Error> {
1031    let mut work = workspace.begin();
1032    let result = (|| {
1033        validate_indices(indices, remap.len(), &mut work)?;
1034        let count = indices.map_or(remap.len(), <[u32]>::len);
1035        let mut budget = Budget::new(workspace);
1036        let mut out = budget.filled(count, 0u32)?;
1037        if let Some(input) = indices {
1038            remap_index_copy(&mut out, input.iter().copied(), remap, &mut work)?;
1039        } else {
1040            remap_index_copy(&mut out, (0..count).map(|i| i as u32), remap, &mut work)?;
1041        }
1042        Ok(out)
1043    })();
1044    workspace.finish(&work);
1045    result
1046}
1047
1048#[inline(always)]
1049fn filter_triangle<const LIMITED: bool>(
1050    source: &[u32; 3],
1051    remap: &[u32],
1052    table: &mut [[u32; 3]],
1053    out: &mut [u32],
1054    write: &mut usize,
1055    budget: (&mut Work, &mut usize),
1056) -> Result<(), Error> {
1057    let (work, visits) = budget;
1058    if LIMITED {
1059        work.add(1)?;
1060    } else {
1061        *visits += 1;
1062    }
1063    let mut key = [
1064        remap[source[0] as usize],
1065        remap[source[1] as usize],
1066        remap[source[2] as usize],
1067    ];
1068    if key[0] == key[1] || key[0] == key[2] || key[1] == key[2] {
1069        return Ok(());
1070    }
1071    if key[1] < key[0] && key[1] < key[2] {
1072        key = [key[1], key[2], key[0]];
1073    } else if key[2] < key[0] && key[2] < key[1] {
1074        key = [key[2], key[0], key[1]];
1075    }
1076    let mask = table.len() - 1;
1077    let mut bucket = spatial_hash(key) as usize & mask;
1078    for probe in 0..table.len() {
1079        if LIMITED {
1080            work.add(1)?;
1081        } else {
1082            *visits += 1;
1083        }
1084        if table[bucket] == key {
1085            return Ok(());
1086        }
1087        if table[bucket] == [NONE; 3] {
1088            table[bucket] = key;
1089            out[*write..*write + 3].copy_from_slice(source);
1090            *write += 3;
1091            return Ok(());
1092        }
1093        bucket = (bucket + probe + 1) & mask;
1094    }
1095    Err(Error::NumericalFailure)
1096}
1097
1098fn filter_triangles(
1099    out: &mut [u32],
1100    indices: &[u32],
1101    remap: &[u32],
1102    table: &mut [[u32; 3]],
1103    work: &mut Work,
1104) -> Result<usize, Error> {
1105    work.add(table.len())?;
1106    table.fill([NONE; 3]);
1107    let source = indices.as_chunks::<3>().0;
1108    let bound = table.len().checked_add(1).ok_or(Error::SizeOverflow)?;
1109    let mut write = 0;
1110    let mut begin = 0;
1111    while begin < source.len() {
1112        let count = work.batch(source.len() - begin, bound)?;
1113        let mut visits = 0;
1114        if count == 0 {
1115            filter_triangle::<true>(
1116                &source[begin],
1117                remap,
1118                table,
1119                out,
1120                &mut write,
1121                (work, &mut visits),
1122            )?;
1123            begin += 1;
1124        } else {
1125            let result = (|| {
1126                for triangle in &source[begin..begin + count] {
1127                    filter_triangle::<false>(
1128                        triangle,
1129                        remap,
1130                        table,
1131                        out,
1132                        &mut write,
1133                        (work, &mut visits),
1134                    )?;
1135                }
1136                Ok(())
1137            })();
1138            work.add(visits)?;
1139            result?;
1140            begin += count;
1141        }
1142    }
1143    Ok(write)
1144}
1145
1146fn shadow_filter<const FILTER: bool>(
1147    indices: &[u32],
1148    streams: &[VertexStream<'_>],
1149    destination: Option<&mut [u32]>,
1150    workspace: &mut Workspace,
1151) -> Result<(Vec<u32>, usize), Error> {
1152    let mut work = workspace.begin();
1153    let result = (|| {
1154        let count = streams_valid(streams)?;
1155        topology(indices, count, &mut work)?;
1156        if destination
1157            .as_ref()
1158            .is_some_and(|out| out.len() < indices.len())
1159        {
1160            return Err(Error::BufferTooSmall);
1161        }
1162        let table_len = buckets(count)?;
1163        let triangle_len = if FILTER {
1164            buckets(indices.len() / 3)?
1165        } else {
1166            0
1167        };
1168        let integer_len = triangle_len
1169            .checked_mul(3)
1170            .and_then(|v| v.checked_add(table_len))
1171            .and_then(|v| v.checked_add(count))
1172            .ok_or(Error::SizeOverflow)?;
1173        let output_bytes = if destination.is_none() {
1174            checked_bytes(indices.len(), 4)?
1175        } else {
1176            0
1177        };
1178        if FILTER {
1179            workspace.prepare([integer_len, 0, 0, 0], output_bytes)?;
1180        } else {
1181            workspace.prepare_remap(integer_len, output_bytes)?;
1182        }
1183        let mut owned = if destination.is_none() {
1184            crate::workspace::output(indices.len())?
1185        } else {
1186            Vec::new()
1187        };
1188        if destination.is_none() && owned.capacity() != indices.len() {
1189            let actual_output = checked_bytes(owned.capacity(), 4)?;
1190            if FILTER {
1191                workspace.prepare([integer_len, 0, 0, 0], actual_output)?;
1192            } else {
1193                workspace.prepare_remap(integer_len, actual_output)?;
1194            }
1195        }
1196        let out = destination.unwrap_or(&mut owned);
1197        let out = &mut out[..indices.len()];
1198        let (remap, rest) = workspace.integers[..integer_len].split_at_mut(count);
1199        let (table, triangles) = rest.split_at_mut(table_len);
1200        let triangles = triangles.as_chunks_mut::<3>().0;
1201        if !FILTER {
1202            shadow_streams(remap, indices, out, table, streams, &mut work)?;
1203            return Ok((owned, indices.len()));
1204        }
1205        generate_streams(remap, Some(indices), table, streams, false, &mut work)?;
1206        let write = filter_triangles(out, indices, remap, triangles, &mut work)?;
1207        owned.truncate(write);
1208        Ok((owned, write))
1209    })();
1210    workspace.finish(&work);
1211    result
1212}
1213/// Replace triangle references with first referenced binary-equal vertices.
1214///
1215/// # Errors
1216/// `InvalidTopology` for incomplete triangles or `IndexOutOfBounds` for invalid vertex references.
1217/// `SizeOverflow` for size overflow, `LimitExceeded` for exhausted limits, or `AllocationFailed` for failed reservation.
1218pub fn generate_shadow_index_buffer(
1219    indices: &[u32],
1220    vertices: VertexStream<'_>,
1221    workspace: &mut Workspace,
1222) -> Result<Vec<u32>, Error> {
1223    generate_shadow_index_buffer_multi(indices, &[vertices], workspace)
1224}
1225/// Multi-stream shadow indices, preserving original vertex numbering.
1226///
1227/// # Errors
1228/// `InvalidTopology` for incomplete triangles or `IndexOutOfBounds` for invalid vertex references.
1229/// `InvalidLayout` for absent or mismatched streams;
1230/// `SizeOverflow` for size overflow, `LimitExceeded` for exhausted limits, or `AllocationFailed` for failed reservation.
1231pub fn generate_shadow_index_buffer_multi(
1232    indices: &[u32],
1233    streams: &[VertexStream<'_>],
1234    workspace: &mut Workspace,
1235) -> Result<Vec<u32>, Error> {
1236    Ok(shadow_filter::<false>(indices, streams, None, workspace)?.0)
1237}
1238/// Remove binary-degenerate and duplicate triangles; preserve surviving source
1239/// corners and winding. Rotated duplicates are removed; reversed winding stays.
1240///
1241/// # Errors
1242/// `InvalidTopology` for incomplete triangles or `IndexOutOfBounds` for invalid vertex references.
1243/// `NumericalFailure` if bounded hash probing finds no slot.
1244/// `SizeOverflow` for size overflow, `LimitExceeded` for exhausted limits, or `AllocationFailed` for failed reservation.
1245pub fn filter_index_buffer(
1246    indices: &[u32],
1247    vertices: VertexStream<'_>,
1248    workspace: &mut Workspace,
1249) -> Result<Vec<u32>, Error> {
1250    filter_index_buffer_multi(indices, &[vertices], workspace)
1251}
1252/// Multi-stream triangle filtering.
1253///
1254/// # Errors
1255/// `InvalidTopology` for incomplete triangles or `IndexOutOfBounds` for invalid vertex references.
1256/// `InvalidLayout` for absent or mismatched streams; `NumericalFailure` if bounded hash probing finds no slot.
1257/// `SizeOverflow` for size overflow, `LimitExceeded` for exhausted limits, or `AllocationFailed` for failed reservation.
1258pub fn filter_index_buffer_multi(
1259    indices: &[u32],
1260    streams: &[VertexStream<'_>],
1261    workspace: &mut Workspace,
1262) -> Result<Vec<u32>, Error> {
1263    Ok(shadow_filter::<true>(indices, streams, None, workspace)?.0)
1264}
1265
1266#[inline(always)]
1267fn edge_hash(edge: u64, remap: &[u32]) -> u32 {
1268    edge_value_hash(remap[(edge >> 32) as usize], remap[edge as u32 as usize])
1269}
1270#[inline(always)]
1271fn edge_value_hash(mut h1: u32, mut h2: u32) -> u32 {
1272    const M: u32 = 0x5bd1e995;
1273    h1 ^= h2 >> 18;
1274    h1 = h1.wrapping_mul(M);
1275    h2 ^= h1 >> 22;
1276    h2 = h2.wrapping_mul(M);
1277    h1 ^= h2 >> 17;
1278    h1 = h1.wrapping_mul(M);
1279    h2 ^= h1 >> 19;
1280    h2.wrapping_mul(M)
1281}
1282fn patches<const TESS: bool>(
1283    indices: &[u32],
1284    positions: Positions<'_>,
1285    destination: Option<&mut [u32]>,
1286    workspace: &mut Workspace,
1287) -> Result<Vec<u32>, Error> {
1288    if let Some(p) = positions.packed_values() {
1289        patches_kernel::<TESS>(indices, p.len(), |i| p[i as usize], destination, workspace)
1290    } else {
1291        patches_kernel::<TESS>(
1292            indices,
1293            positions.len(),
1294            |i| positions.get(i as usize).expect("checked position"),
1295            destination,
1296            workspace,
1297        )
1298    }
1299}
1300fn patches_kernel<const TESS: bool>(
1301    indices: &[u32],
1302    vertex_count: usize,
1303    position: impl Fn(u32) -> [f32; 3],
1304    destination: Option<&mut [u32]>,
1305    workspace: &mut Workspace,
1306) -> Result<Vec<u32>, Error> {
1307    let mut work = workspace.begin();
1308    let result = (|| {
1309        topology(indices, vertex_count, &mut work)?;
1310        let mut budget = Budget::new(workspace);
1311        let mut remap = budget.filled(vertex_count, NONE)?;
1312        let mut table = budget.filled(buckets(vertex_count)?, NONE)?;
1313        // Adjacency uses binary position equality (including signed zeros),
1314        // unlike the public numerical generatePositionRemap operation.
1315        generate::<false>(
1316            &mut remap,
1317            None,
1318            &mut table,
1319            |i| {
1320                let mut h = 0;
1321                for v in position(i) {
1322                    h = hash_update(h, &v.to_bits().to_le_bytes());
1323                }
1324                h
1325            },
1326            |a, b| position(a).map(f32::to_bits) == position(b).map(f32::to_bits),
1327            true,
1328            &mut work,
1329        )?;
1330        budget.release(table);
1331        let mut edges = budget.filled(buckets(indices.len())?, u64::MAX)?;
1332        let mut opposite = budget.filled(if TESS { 0 } else { edges.len() }, NONE)?;
1333        let factor = if TESS { 4 } else { 2 };
1334        let size = indices
1335            .len()
1336            .checked_mul(factor)
1337            .ok_or(Error::SizeOverflow)?;
1338        let mut owned = if destination.is_none() {
1339            budget.filled(size, 0u32)?
1340        } else {
1341            Vec::new()
1342        };
1343        let out = destination.unwrap_or(&mut owned);
1344        if out.len() < size {
1345            return Err(Error::BufferTooSmall);
1346        }
1347        let out = &mut out[..size];
1348        if !TESS {
1349            adjacency_pass::<true>(indices, out, &mut edges, &mut opposite, &remap, &mut work)?;
1350            adjacency_pass::<false>(indices, out, &mut edges, &mut opposite, &remap, &mut work)?;
1351            return Ok(owned);
1352        }
1353        for tri in indices.as_chunks::<3>().0 {
1354            for e in 0..3 {
1355                work.add(1)?;
1356                let edge = (u64::from(tri[e]) << 32) | u64::from(tri[(e + 1) % 3]);
1357                let slot = edge_lookup(&edges, &remap, edge, &mut work)?;
1358                if edges[slot] == u64::MAX {
1359                    edges[slot] = edge;
1360                    if !TESS {
1361                        opposite[slot] = tri[(e + 2) % 3];
1362                    }
1363                }
1364            }
1365        }
1366        for (tri, patch) in indices
1367            .as_chunks::<3>()
1368            .0
1369            .iter()
1370            .zip(out.chunks_exact_mut(factor * 3))
1371        {
1372            for e in 0..3 {
1373                work.add(1)?;
1374                let a = tri[e];
1375                let b = tri[(e + 1) % 3];
1376                let edge = (u64::from(b) << 32) | u64::from(a);
1377                let slot = edge_lookup(&edges, &remap, edge, &mut work)?;
1378                if TESS {
1379                    let opp = if edges[slot] == u64::MAX {
1380                        edge
1381                    } else {
1382                        edges[slot]
1383                    };
1384                    patch[e] = a;
1385                    patch[3 + e * 2] = opp as u32;
1386                    patch[4 + e * 2] = (opp >> 32) as u32;
1387                    patch[9 + e] = remap[a as usize];
1388                } else {
1389                    patch[e * 2] = a;
1390                    patch[e * 2 + 1] = if edges[slot] == u64::MAX {
1391                        a
1392                    } else {
1393                        opposite[slot]
1394                    };
1395                }
1396            }
1397        }
1398        Ok(owned)
1399    })();
1400    workspace.finish(&work);
1401    result
1402}
1403
1404// A triangle visits three edges; each lookup probes at most the entire table.
1405// Charge completed batches once when that conservative bound fits. Near the
1406// limit, replay the original per-edge/per-probe sequence before any writes.
1407fn adjacency_pass<const BUILD: bool>(
1408    indices: &[u32],
1409    out: &mut [u32],
1410    edges: &mut [u64],
1411    opposite: &mut [u32],
1412    remap: &[u32],
1413    work: &mut Work,
1414) -> Result<(), Error> {
1415    let triangles = indices.as_chunks::<3>().0;
1416    let bound = edges.len().checked_add(1).and_then(|n| n.checked_mul(3));
1417    let mut begin = 0;
1418    while begin < triangles.len() {
1419        let count = match bound {
1420            Some(bound) => work.batch(triangles.len() - begin, bound)?,
1421            None => 0,
1422        };
1423        let mut visits = 0;
1424        for (offset, tri) in triangles[begin..begin + count.max(1)].iter().enumerate() {
1425            for e in 0..3 {
1426                let a = tri[e];
1427                let b = tri[(e + 1) % 3];
1428                let edge = if BUILD {
1429                    (u64::from(remap[a as usize]) << 32) | u64::from(remap[b as usize])
1430                } else {
1431                    (u64::from(remap[b as usize]) << 32) | u64::from(remap[a as usize])
1432                };
1433                let slot = if count == 0 {
1434                    work.add(1)?;
1435                    adjacency_lookup(edges, edge, work)?
1436                } else {
1437                    visits += 1;
1438                    let (slot, probes) = edge_probe(edges, edge);
1439                    visits += probes;
1440                    let Some(slot) = slot else {
1441                        work.add(visits)?;
1442                        return Err(Error::NumericalFailure);
1443                    };
1444                    slot
1445                };
1446                if BUILD {
1447                    if edges[slot] == u64::MAX {
1448                        edges[slot] = edge;
1449                        opposite[slot] = tri[(e + 2) % 3];
1450                    }
1451                } else {
1452                    let patch = &mut out[(begin + offset) * 6..][..6];
1453                    patch[e * 2] = a;
1454                    patch[e * 2 + 1] = if edges[slot] == u64::MAX {
1455                        a
1456                    } else {
1457                        opposite[slot]
1458                    };
1459                }
1460            }
1461        }
1462        work.add(visits)?;
1463        begin += count.max(1);
1464    }
1465    Ok(())
1466}
1467
1468#[inline(always)]
1469fn edge_probe(table: &[u64], edge: u64) -> (Option<usize>, usize) {
1470    let mask = table.len() - 1;
1471    let mut bucket = edge_value_hash((edge >> 32) as u32, edge as u32) as usize & mask;
1472    for probe in 0..table.len() {
1473        let old = table[bucket];
1474        if old == u64::MAX || old == edge {
1475            return (Some(bucket), probe + 1);
1476        }
1477        bucket = (bucket + probe + 1) & mask;
1478    }
1479    (None, table.len())
1480}
1481
1482#[inline(always)]
1483fn adjacency_lookup(table: &[u64], edge: u64, work: &mut Work) -> Result<usize, Error> {
1484    if work.covers(table.len())? {
1485        let (slot, probes) = edge_probe(table, edge);
1486        work.add(probes)?;
1487        slot.ok_or(Error::NumericalFailure)
1488    } else {
1489        let mask = table.len() - 1;
1490        let mut bucket = edge_value_hash((edge >> 32) as u32, edge as u32) as usize & mask;
1491        for probe in 0..table.len() {
1492            work.add(1)?;
1493            if table[bucket] == u64::MAX || table[bucket] == edge {
1494                return Ok(bucket);
1495            }
1496            bucket = (bucket + probe + 1) & mask;
1497        }
1498        Err(Error::NumericalFailure)
1499    }
1500}
1501#[inline(always)]
1502fn edge_lookup(table: &[u64], remap: &[u32], edge: u64, work: &mut Work) -> Result<usize, Error> {
1503    if work.covers(table.len())? {
1504        edge_lookup_kernel::<false>(table, remap, edge, work)
1505    } else {
1506        edge_lookup_kernel::<true>(table, remap, edge, work)
1507    }
1508}
1509#[inline(always)]
1510fn edge_lookup_kernel<const LIMITED: bool>(
1511    table: &[u64],
1512    remap: &[u32],
1513    edge: u64,
1514    work: &mut Work,
1515) -> Result<usize, Error> {
1516    let mask = table.len() - 1;
1517    let mut bucket = edge_hash(edge, remap) as usize & mask;
1518    let a = remap[(edge >> 32) as usize];
1519    let b = remap[edge as u32 as usize];
1520    for probe in 0..table.len() {
1521        if LIMITED {
1522            work.add(1)?;
1523        }
1524        let old = table[bucket];
1525        if old == u64::MAX || (remap[(old >> 32) as usize] == a && remap[old as u32 as usize] == b)
1526        {
1527            if !LIMITED {
1528                work.add(probe + 1)?;
1529            }
1530            return Ok(bucket);
1531        }
1532        bucket = (bucket + probe + 1) & mask;
1533    }
1534    if !LIMITED {
1535        work.add(table.len())?;
1536    }
1537    Err(Error::NumericalFailure)
1538}
1539/// Generate six adjacency indices per triangle using binary position welding.
1540///
1541/// # Errors
1542/// `InvalidTopology` for incomplete triangles or `IndexOutOfBounds` for invalid vertex references.
1543/// `NumericalFailure` if bounded hash probing finds no slot.
1544/// `SizeOverflow` for size overflow, `LimitExceeded` for exhausted limits, or `AllocationFailed` for failed reservation.
1545pub fn generate_adjacency_index_buffer(
1546    indices: &[u32],
1547    positions: Positions<'_>,
1548    workspace: &mut Workspace,
1549) -> Result<Vec<u32>, Error> {
1550    patches::<false>(indices, positions, None, workspace)
1551}
1552/// Generate twelve tessellation indices per triangle using binary position welding.
1553///
1554/// # Errors
1555/// `InvalidTopology` for incomplete triangles or `IndexOutOfBounds` for invalid vertex references.
1556/// `NumericalFailure` if bounded hash probing finds no slot.
1557/// `SizeOverflow` for size overflow, `LimitExceeded` for exhausted limits, or `AllocationFailed` for failed reservation.
1558pub fn generate_tessellation_index_buffer(
1559    indices: &[u32],
1560    positions: Positions<'_>,
1561    workspace: &mut Workspace,
1562) -> Result<Vec<u32>, Error> {
1563    patches::<true>(indices, positions, None, workspace)
1564}
1565/// Generate a unique first-corner vertex for each triangle, with the same
1566/// wrapping eight-bit valence heuristic and cyclic rotations as upstream.
1567///
1568/// # Errors
1569/// `InvalidTopology` for incomplete triangles or `IndexOutOfBounds` for invalid vertex references.
1570/// `SizeOverflow` for size overflow, `LimitExceeded` for exhausted limits, or `AllocationFailed` for failed reservation.
1571pub fn generate_provoking_index_buffer(
1572    indices: &[u32],
1573    vertex_count: usize,
1574    workspace: &mut Workspace,
1575) -> Result<ProvokingMesh, Error> {
1576    Ok(provoking(indices, vertex_count, None, workspace)?.0)
1577}
1578#[inline(always)]
1579fn provoking_triangle(
1580    tri: [u32; 3],
1581    destination: &mut [u32; 3],
1582    remap: &mut [u32],
1583    valence: &mut [u8],
1584    reorder: &mut [u32],
1585    write: &mut usize,
1586) {
1587    let mut tri = tri;
1588    let rank = |i: u32| {
1589        if remap[i as usize] == NONE {
1590            u32::from(valence[i as usize])
1591        } else {
1592            NONE
1593        }
1594    };
1595    let v = [rank(tri[0]), rank(tri[1]), rank(tri[2])];
1596    if v[1] != NONE && v[1] <= v[0] && v[1] <= v[2] {
1597        tri = [tri[1], tri[2], tri[0]];
1598    } else if v[2] != NONE && v[2] <= v[0] && v[2] <= v[1] {
1599        tri = [tri[2], tri[0], tri[1]];
1600    }
1601    if remap[tri[0] as usize] == NONE {
1602        remap[tri[0] as usize] = *write as u32;
1603    }
1604    reorder[*write] = tri[0];
1605    *destination = [*write as u32, tri[1], tri[2]];
1606    *write += 1;
1607    for i in tri {
1608        valence[i as usize] = valence[i as usize].wrapping_sub(1);
1609    }
1610}
1611#[inline(always)]
1612fn provoking_corner(index: &mut u32, remap: &mut [u32], reorder: &mut [u32], write: &mut usize) {
1613    let r = &mut remap[*index as usize];
1614    if *r == NONE {
1615        *r = *write as u32;
1616        reorder[*write] = *index;
1617        *write += 1;
1618    }
1619    *index = *r;
1620}
1621fn provoking(
1622    indices: &[u32],
1623    vertex_count: usize,
1624    destination: Option<(&mut [u32], &mut [u32])>,
1625    workspace: &mut Workspace,
1626) -> Result<(ProvokingMesh, usize), Error> {
1627    let mut work = workspace.begin();
1628    let result = (|| {
1629        topology(indices, vertex_count, &mut work)?;
1630        let count = vertex_count
1631            .checked_add(indices.len() / 3)
1632            .ok_or(Error::SizeOverflow)?;
1633        if count > u32::MAX as usize {
1634            return Err(Error::SizeOverflow);
1635        }
1636        workspace.prepare([vertex_count, 0, vertex_count, 0], 0)?;
1637        let mut budget = Budget::new(workspace);
1638        let caller = destination.is_some();
1639        let mut owned = if caller {
1640            Vec::new()
1641        } else {
1642            budget.filled(indices.len(), 0u32)?
1643        };
1644        let mut owned_reorder = if caller {
1645            Vec::new()
1646        } else {
1647            budget.filled(count, 0u32)?
1648        };
1649        let (out, reorder) = destination.unwrap_or((&mut owned, &mut owned_reorder));
1650        if out.len() < indices.len() || reorder.len() < count {
1651            return Err(Error::BufferTooSmall);
1652        }
1653        let out = &mut out[..indices.len()];
1654        let remap = &mut budget.ws.integers[..vertex_count];
1655        let valence = &mut budget.ws.flags[..vertex_count];
1656        remap.fill(NONE);
1657        valence.fill(0);
1658        if work.precharge(indices.len(), 1)? {
1659            for &i in indices {
1660                valence[i as usize] = valence[i as usize].wrapping_add(1);
1661            }
1662        } else {
1663            for &i in indices {
1664                work.add(1)?;
1665                valence[i as usize] = valence[i as usize].wrapping_add(1);
1666            }
1667        }
1668        let mut write = 0;
1669        if work.precharge(indices.len() / 3, 1)? {
1670            for (&tri, dest) in indices
1671                .as_chunks::<3>()
1672                .0
1673                .iter()
1674                .zip(out.as_chunks_mut::<3>().0)
1675            {
1676                provoking_triangle(tri, dest, remap, valence, reorder, &mut write);
1677            }
1678        } else {
1679            for (&tri, dest) in indices
1680                .as_chunks::<3>()
1681                .0
1682                .iter()
1683                .zip(out.as_chunks_mut::<3>().0)
1684            {
1685                work.add(1)?;
1686                provoking_triangle(tri, dest, remap, valence, reorder, &mut write);
1687            }
1688        }
1689        let corners = indices.len() / 3 * 2;
1690        if work.precharge(corners, 1)? {
1691            for tri in out.as_chunks_mut::<3>().0 {
1692                provoking_corner(&mut tri[1], remap, reorder, &mut write);
1693                provoking_corner(&mut tri[2], remap, reorder, &mut write);
1694            }
1695        } else {
1696            for tri in out.as_chunks_mut::<3>().0 {
1697                for i in &mut tri[1..] {
1698                    work.add(1)?;
1699                    provoking_corner(i, remap, reorder, &mut write);
1700                }
1701            }
1702        }
1703        owned_reorder.truncate(write);
1704        Ok((
1705            ProvokingMesh {
1706                indices: owned,
1707                reorder: owned_reorder,
1708            },
1709            write,
1710        ))
1711    })();
1712    workspace.finish(&work);
1713    result
1714}
1715
1716/// Borrowed fetch-remap input with its index-validation result cached once.
1717///
1718/// Construction scans at most `indices.len()` entries, without allocating.
1719/// Invalid input is retained so operations can preserve error precedence,
1720/// logical work usage and caller-buffer writes, including on short budgets.
1721#[derive(Clone, Copy, Debug)]
1722pub struct FetchIndices<'a> {
1723    indices: &'a [u32],
1724    vertex_count: usize,
1725    visits: usize,
1726    error: Option<Error>,
1727}
1728impl<'a> FetchIndices<'a> {
1729    /// Cache validation of an arbitrary index sequence and its vertex count.
1730    ///
1731    /// Errors are deferred to the fetch-remap operation, where the original
1732    /// validation visits are charged to its [`Workspace`] in constant time
1733    /// when they fit. Short budgets replay the original charged prefix.
1734    pub fn new(indices: &'a [u32], vertex_count: usize) -> Self {
1735        let (visits, error) = if vertex_count > u32::MAX as usize {
1736            (0, Some(Error::SizeOverflow))
1737        } else if let Some(at) = indices.iter().position(|&i| i as usize >= vertex_count) {
1738            (at + 1, Some(Error::IndexOutOfBounds))
1739        } else {
1740            (indices.len(), None)
1741        };
1742        Self {
1743            indices,
1744            vertex_count,
1745            visits,
1746            error,
1747        }
1748    }
1749    fn apply(self, work: &mut Work) -> Result<(), Error> {
1750        if work.covers(self.visits)? {
1751            work.add(self.visits)?;
1752        } else {
1753            work.scan(self.indices[..self.visits].iter(), |_| Ok(()))?;
1754        }
1755        self.error.map_or(Ok(()), Err)
1756    }
1757}
1758
1759/// Generate first-use fetch numbering using cached index validation.
1760///
1761/// Output, errors, error precedence and logical workspace usage match
1762/// [`optimize_vertex_fetch_remap`]. Construct [`FetchIndices`] once to avoid
1763/// rescanning the sequence for validity on repeated calls. Numbering and
1764/// output initialization still take O(indices.len() + vertex_count) time.
1765///
1766/// # Errors
1767/// `IndexOutOfBounds` for invalid references;
1768/// `SizeOverflow` for size overflow, `LimitExceeded` for exhausted limits, or `AllocationFailed` for failed reservation.
1769pub fn optimize_vertex_fetch_remap_with_indices(
1770    source: FetchIndices<'_>,
1771    workspace: &mut Workspace,
1772) -> Result<VertexRemap, Error> {
1773    let mut work = workspace.begin();
1774    let result = (|| {
1775        source.apply(&mut work)?;
1776        let mut budget = Budget::new(workspace);
1777        let mut remap = budget.filled(source.vertex_count, NONE)?;
1778        let vertex_count = fetch_remap_kernel(&mut remap, source.indices, &mut work)?;
1779        Ok(VertexRemap {
1780            remap,
1781            vertex_count,
1782        })
1783    })();
1784    workspace.finish(&work);
1785    result
1786}
1787
1788/// Generate fetch numbering into caller storage using cached validation.
1789///
1790/// Matches [`optimize_vertex_fetch_remap_into`], including error precedence,
1791/// unused-vertex sentinels, preserved tails and partially written prefixes on
1792/// work exhaustion. Reuse [`FetchIndices`] to avoid repeated validity scans;
1793/// output initialization and numbering remain O(vertex_count + indices.len()).
1794///
1795/// # Errors
1796/// Same errors as [`optimize_vertex_fetch_remap_with_indices`]. `BufferTooSmall` if an output buffer is too short.
1797pub fn optimize_vertex_fetch_remap_with_indices_into(
1798    destination: &mut [u32],
1799    source: FetchIndices<'_>,
1800    workspace: &mut Workspace,
1801) -> Result<usize, Error> {
1802    let mut work = workspace.begin();
1803    let result = (|| {
1804        source.apply(&mut work)?;
1805        if destination.len() < source.vertex_count {
1806            return Err(Error::BufferTooSmall);
1807        }
1808        workspace.prepare([0; 4], 0)?;
1809        work.add(source.vertex_count)?;
1810        destination[..source.vertex_count].fill(NONE);
1811        fetch_remap_kernel(
1812            &mut destination[..source.vertex_count],
1813            source.indices,
1814            &mut work,
1815        )
1816    })();
1817    workspace.finish(&work);
1818    result
1819}
1820
1821/// Generate first-use fetch numbering for an arbitrary index sequence.
1822///
1823/// Validates the full sequence on every call. Repeated queries can cache this
1824/// O(indices.len()) validation with [`FetchIndices`] and
1825/// [`optimize_vertex_fetch_remap_with_indices`].
1826///
1827/// # Errors
1828/// `IndexOutOfBounds` for invalid references;
1829/// `SizeOverflow` for size overflow, `LimitExceeded` for exhausted limits, or `AllocationFailed` for failed reservation.
1830pub fn optimize_vertex_fetch_remap(
1831    indices: &[u32],
1832    vertex_count: usize,
1833    workspace: &mut Workspace,
1834) -> Result<VertexRemap, Error> {
1835    let mut work = workspace.begin();
1836    let result = (|| {
1837        if vertex_count > u32::MAX as usize {
1838            return Err(Error::SizeOverflow);
1839        }
1840        work.indices(indices, vertex_count)?;
1841        let mut budget = Budget::new(workspace);
1842        let mut remap = budget.filled(vertex_count, NONE)?;
1843        let next = fetch_remap_kernel(&mut remap, indices, &mut work)?;
1844        Ok(VertexRemap {
1845            remap,
1846            vertex_count: next,
1847        })
1848    })();
1849    workspace.finish(&work);
1850    result
1851}
1852/// Fetch numbering into caller storage. Unused vertices are `u32::MAX`;
1853/// work exhaustion may partially modify the used prefix.
1854///
1855/// Validates the full sequence on every call. Repeated queries can cache this
1856/// O(indices.len()) validation with [`FetchIndices`] and
1857/// [`optimize_vertex_fetch_remap_with_indices_into`].
1858///
1859/// # Errors
1860/// Same errors as [`optimize_vertex_fetch_remap`]. `BufferTooSmall` if an output buffer is too short.
1861pub fn optimize_vertex_fetch_remap_into(
1862    destination: &mut [u32],
1863    indices: &[u32],
1864    vertex_count: usize,
1865    workspace: &mut Workspace,
1866) -> Result<usize, Error> {
1867    let mut work = workspace.begin();
1868    let result = (|| {
1869        if vertex_count > u32::MAX as usize {
1870            return Err(Error::SizeOverflow);
1871        }
1872        work.indices(indices, vertex_count)?;
1873        if destination.len() < vertex_count {
1874            return Err(Error::BufferTooSmall);
1875        }
1876        workspace.prepare([0; 4], 0)?;
1877        work.add(vertex_count)?;
1878        destination[..vertex_count].fill(NONE);
1879        fetch_remap_kernel(&mut destination[..vertex_count], indices, &mut work)
1880    })();
1881    workspace.finish(&work);
1882    result
1883}
1884#[inline]
1885fn fetch_remap_kernel(remap: &mut [u32], indices: &[u32], work: &mut Work) -> Result<usize, Error> {
1886    let mut next = 0;
1887    if work.precharge(indices.len(), 1)? {
1888        for &i in indices {
1889            let slot = &mut remap[i as usize];
1890            if *slot == NONE {
1891                *slot = next;
1892                next += 1;
1893            }
1894        }
1895    } else {
1896        for &i in indices {
1897            work.add(1)?;
1898            let slot = &mut remap[i as usize];
1899            if *slot == NONE {
1900                *slot = next;
1901                next += 1;
1902            }
1903        }
1904    }
1905    Ok(next as usize)
1906}
1907#[inline(always)]
1908fn fetch_visit<const SIZE: usize>(
1909    destination: &mut [u8],
1910    vertices: VertexStream<'_>,
1911    remap: &mut [u32],
1912    next: &mut usize,
1913    index: u32,
1914    output: &mut u32,
1915) {
1916    let r = &mut remap[index as usize];
1917    if *r == NONE {
1918        copy_vertex::<SIZE>(destination, vertices, index, *next);
1919        *r = *next as u32;
1920        *next += 1;
1921    }
1922    *output = *r;
1923}
1924fn fetch_kernel<'a, const SIZE: usize>(
1925    destination: &mut [u8],
1926    vertices: VertexStream<'_>,
1927    remap: &mut [u32],
1928    indices: impl ExactSizeIterator<Item = (u32, &'a mut u32)>,
1929    work: &mut Work,
1930) -> Result<usize, Error> {
1931    let mut next = 0;
1932    if work.precharge(indices.len(), 1)? {
1933        for (index, output) in indices {
1934            fetch_visit::<SIZE>(destination, vertices, remap, &mut next, index, output);
1935        }
1936    } else {
1937        for (index, output) in indices {
1938            work.add(1)?;
1939            fetch_visit::<SIZE>(destination, vertices, remap, &mut next, index, output);
1940        }
1941    }
1942    Ok(next)
1943}
1944fn fetch_dispatch<'a>(
1945    destination: &mut [u8],
1946    vertices: VertexStream<'_>,
1947    remap: &mut [u32],
1948    indices: impl ExactSizeIterator<Item = (u32, &'a mut u32)>,
1949    work: &mut Work,
1950) -> Result<usize, Error> {
1951    match vertices.size {
1952        4 => fetch_kernel::<4>(destination, vertices, remap, indices, work),
1953        8 => fetch_kernel::<8>(destination, vertices, remap, indices, work),
1954        12 => fetch_kernel::<12>(destination, vertices, remap, indices, work),
1955        16 => fetch_kernel::<16>(destination, vertices, remap, indices, work),
1956        _ => fetch_kernel::<0>(destination, vertices, remap, indices, work),
1957    }
1958}
1959
1960#[inline(always)]
1961fn fetch_owned_record<const SIZE: usize, const PACKED: bool>(
1962    vertices: VertexStream<'_>,
1963    source: &[[u8; SIZE]],
1964    remap: &mut [u32],
1965    index: &mut u32,
1966    next: &mut usize,
1967) -> Option<[u8; SIZE]> {
1968    let entry = &mut remap[*index as usize];
1969    if *entry == NONE {
1970        let record = if PACKED {
1971            source[*index as usize]
1972        } else {
1973            *vertices.key_array::<SIZE>(*index)
1974        };
1975        *entry = *next as u32;
1976        *next += 1;
1977        *index = *entry;
1978        Some(record)
1979    } else {
1980        *index = *entry;
1981        None
1982    }
1983}
1984
1985fn fetch_owned<const SIZE: usize>(
1986    indices: &[u32],
1987    vertices: VertexStream<'_>,
1988    workspace: &mut Workspace,
1989    work: &mut Work,
1990) -> Result<FetchedMesh, Error> {
1991    let (mut out, mut records, owned) = {
1992        let mut budget = Budget::new(workspace);
1993        let out = budget.copied(indices)?;
1994        let records = budget.reserved::<[u8; SIZE]>(vertices.count)?;
1995        (out, records, budget.bytes())
1996    };
1997    workspace.prepare_remap(vertices.count, owned)?;
1998    let remap = &mut workspace.integers[..vertices.count];
1999    let vertex_count = if vertices.stride == SIZE {
2000        let source = &vertices.data[vertices.offset..].as_chunks::<SIZE>().0[..vertices.count];
2001        fetch_owned_kernel::<SIZE, true>(&mut records, vertices, source, remap, &mut out, work)?
2002    } else {
2003        fetch_owned_kernel::<SIZE, false>(&mut records, vertices, &[], remap, &mut out, work)?
2004    };
2005    debug_assert_eq!(records.len(), vertex_count);
2006    Ok(FetchedMesh {
2007        indices: out,
2008        vertices: records.into_flattened(),
2009        vertex_count,
2010    })
2011}
2012
2013fn fetch_owned_kernel<const SIZE: usize, const PACKED: bool>(
2014    records: &mut Vec<[u8; SIZE]>,
2015    vertices: VertexStream<'_>,
2016    source: &[[u8; SIZE]],
2017    remap: &mut [u32],
2018    out: &mut [u32],
2019    work: &mut Work,
2020) -> Result<usize, Error> {
2021    let mut next = 0;
2022    if work.precharge(out.len(), 1)? {
2023        for index in out {
2024            if let Some(record) =
2025                fetch_owned_record::<SIZE, PACKED>(vertices, source, remap, index, &mut next)
2026            {
2027                records.push(record);
2028            }
2029        }
2030    } else {
2031        for index in out {
2032            work.add(1)?;
2033            if let Some(record) =
2034                fetch_owned_record::<SIZE, PACKED>(vertices, source, remap, index, &mut next)
2035            {
2036                records.push(record);
2037            }
2038        }
2039    }
2040    Ok(next)
2041}
2042
2043/// Allocate first-use vertex bytes and rewritten arbitrary indices.
2044///
2045/// # Errors
2046/// `IndexOutOfBounds` for invalid references;
2047/// `SizeOverflow` for size overflow, `LimitExceeded` for exhausted limits, or `AllocationFailed` for failed reservation.
2048pub fn optimize_vertex_fetch(
2049    indices: &[u32],
2050    vertices: VertexStream<'_>,
2051    workspace: &mut Workspace,
2052) -> Result<FetchedMesh, Error> {
2053    let mut work = workspace.begin();
2054    let result = (|| {
2055        validate_indices(Some(indices), vertices.count, &mut work)?;
2056        work.add(indices.len())?;
2057        if vertices.count >= 1024 && vertices.stride != vertices.size {
2058            match vertices.size {
2059                4 => return fetch_owned::<4>(indices, vertices, workspace, &mut work),
2060                8 => return fetch_owned::<8>(indices, vertices, workspace, &mut work),
2061                12 => return fetch_owned::<12>(indices, vertices, workspace, &mut work),
2062                16 => return fetch_owned::<16>(indices, vertices, workspace, &mut work),
2063                _ => {}
2064            }
2065        }
2066        let (mut out, mut bytes, owned) = {
2067            let mut budget = Budget::new(workspace);
2068            let out = budget.copied(indices)?;
2069            let bytes = budget.filled(checked_bytes(vertices.count, vertices.size)?, 0u8)?;
2070            (out, bytes, budget.bytes())
2071        };
2072        workspace.prepare_remap(vertices.count, owned)?;
2073        let remap = &mut workspace.integers[..vertices.count];
2074        let next = fetch_dispatch(
2075            &mut bytes,
2076            vertices,
2077            remap,
2078            out.iter_mut().map(|i| (*i, i)),
2079            &mut work,
2080        )?;
2081        bytes.truncate(next * vertices.size);
2082        Ok(FetchedMesh {
2083            indices: out,
2084            vertices: bytes,
2085            vertex_count: next,
2086        })
2087    })();
2088    workspace.finish(&work);
2089    result
2090}
2091/// Write fetch-ordered bytes while rewriting indices in place. Validation and
2092/// allocation precede writes; counted-work exhaustion may modify both buffers.
2093///
2094/// # Errors
2095/// Same errors as [`optimize_vertex_fetch`]. `BufferTooSmall` if destination storage is insufficient.
2096pub fn optimize_vertex_fetch_into(
2097    destination: &mut [u8],
2098    indices: &mut [u32],
2099    vertices: VertexStream<'_>,
2100    workspace: &mut Workspace,
2101) -> Result<usize, Error> {
2102    let mut work = workspace.begin();
2103    let result = (|| {
2104        validate_indices(Some(indices), vertices.count, &mut work)?;
2105        if destination.len() < checked_bytes(vertices.count, vertices.size)? {
2106            return Err(Error::BufferTooSmall);
2107        }
2108        workspace.prepare_remap(vertices.count, 0)?;
2109        let remap = &mut workspace.integers[..vertices.count];
2110        let next = fetch_dispatch(
2111            destination,
2112            vertices,
2113            remap,
2114            indices.iter_mut().map(|i| (*i, i)),
2115            &mut work,
2116        )?;
2117        Ok(next)
2118    })();
2119    workspace.finish(&work);
2120    result
2121}
2122
2123/// Caller-buffer filtering. The tail is preserved; work exhaustion can leave partial output.
2124///
2125/// # Errors
2126/// Same errors as [`filter_index_buffer`]. `BufferTooSmall` if an output buffer is too short.
2127pub fn filter_index_buffer_into(
2128    destination: &mut [u32],
2129    indices: &[u32],
2130    vertices: VertexStream<'_>,
2131    workspace: &mut Workspace,
2132) -> Result<usize, Error> {
2133    filter_index_buffer_multi_into(destination, indices, &[vertices], workspace)
2134}
2135/// Caller-buffer multi-stream filtering; late work exhaustion can leave partial output.
2136///
2137/// # Errors
2138/// Same errors as [`filter_index_buffer_multi`]. `BufferTooSmall` if an output buffer is too short.
2139pub fn filter_index_buffer_multi_into(
2140    destination: &mut [u32],
2141    indices: &[u32],
2142    streams: &[VertexStream<'_>],
2143    workspace: &mut Workspace,
2144) -> Result<usize, Error> {
2145    Ok(shadow_filter::<true>(indices, streams, Some(destination), workspace)?.1)
2146}
2147/// Caller-buffer shadow indices; late work exhaustion can leave partial output.
2148///
2149/// # Errors
2150/// Same errors as [`generate_shadow_index_buffer`]. `BufferTooSmall` if an output buffer is too short.
2151pub fn generate_shadow_index_buffer_into(
2152    destination: &mut [u32],
2153    indices: &[u32],
2154    vertices: VertexStream<'_>,
2155    workspace: &mut Workspace,
2156) -> Result<usize, Error> {
2157    generate_shadow_index_buffer_multi_into(destination, indices, &[vertices], workspace)
2158}
2159/// Caller-buffer multi-stream shadow indices; late work exhaustion can leave partial output.
2160///
2161/// # Errors
2162/// Same errors as [`generate_shadow_index_buffer_multi`]. `BufferTooSmall` if an output buffer is too short.
2163pub fn generate_shadow_index_buffer_multi_into(
2164    destination: &mut [u32],
2165    indices: &[u32],
2166    streams: &[VertexStream<'_>],
2167    workspace: &mut Workspace,
2168) -> Result<usize, Error> {
2169    Ok(shadow_filter::<false>(indices, streams, Some(destination), workspace)?.1)
2170}
2171/// Caller-buffer adjacency; requires twice input-length capacity. Late work exhaustion can leave partial output.
2172///
2173/// # Errors
2174/// Same errors as [`generate_adjacency_index_buffer`]. `BufferTooSmall` if an output buffer is too short.
2175pub fn generate_adjacency_index_buffer_into(
2176    destination: &mut [u32],
2177    indices: &[u32],
2178    positions: Positions<'_>,
2179    workspace: &mut Workspace,
2180) -> Result<(), Error> {
2181    patches::<false>(indices, positions, Some(destination), workspace)?;
2182    Ok(())
2183}
2184/// Caller-buffer tessellation; requires four times input-length capacity. Late work exhaustion can leave partial output.
2185///
2186/// # Errors
2187/// Same errors as [`generate_tessellation_index_buffer`]. `BufferTooSmall` if an output buffer is too short.
2188pub fn generate_tessellation_index_buffer_into(
2189    destination: &mut [u32],
2190    indices: &[u32],
2191    positions: Positions<'_>,
2192    workspace: &mut Workspace,
2193) -> Result<(), Error> {
2194    patches::<true>(indices, positions, Some(destination), workspace)?;
2195    Ok(())
2196}
2197fn remap_into<const OUTLINE: bool>(
2198    destination: &mut [u32],
2199    indices: Option<&[u32]>,
2200    count: usize,
2201    hash: impl Fn(u32) -> u32,
2202    equal: impl FnMut(u32, u32) -> bool,
2203    canonical: bool,
2204    workspace: &mut Workspace,
2205) -> Result<usize, Error> {
2206    let mut work = workspace.begin();
2207    let result = (|| {
2208        validate_indices(indices, count, &mut work)?;
2209        if destination.len() < count {
2210            return Err(Error::BufferTooSmall);
2211        }
2212        let table_len = buckets(count)?;
2213        workspace.prepare([table_len, 0, 0, 0], 0)?;
2214        generate::<OUTLINE>(
2215            &mut destination[..count],
2216            indices,
2217            &mut workspace.integers[..table_len],
2218            hash,
2219            equal,
2220            canonical,
2221            &mut work,
2222        )
2223    })();
2224    workspace.finish(&work);
2225    result
2226}
2227/// Caller-buffer numerical position remap. The tail is preserved; work exhaustion can leave partial output.
2228///
2229/// # Errors
2230/// Same errors as [`generate_position_remap`]. `BufferTooSmall` if an output buffer is too short.
2231pub fn generate_position_remap_into(
2232    destination: &mut [u32],
2233    positions: Positions<'_>,
2234    workspace: &mut Workspace,
2235) -> Result<(), Error> {
2236    if let Some(p) = positions.packed_values() {
2237        return remap_into::<false>(
2238            destination,
2239            None,
2240            p.len(),
2241            |i| position_value_hash(p[i as usize]),
2242            |a, b| p[a as usize] == p[b as usize],
2243            true,
2244            workspace,
2245        )
2246        .map(|_| ());
2247    }
2248    remap_into::<false>(
2249        destination,
2250        None,
2251        positions.len(),
2252        |i| position_hash(positions, i),
2253        |a, b| positions.get(a as usize) == positions.get(b as usize),
2254        true,
2255        workspace,
2256    )?;
2257    Ok(())
2258}
2259/// Caller-buffer custom numbering with exact callback traversal. Work exhaustion can leave partial output.
2260///
2261/// # Errors
2262/// Same errors as [`generate_vertex_remap_custom`]. `BufferTooSmall` if an output buffer is too short.
2263///
2264/// # Panics
2265/// Panics if the supplied callback panics.
2266pub fn generate_vertex_remap_custom_into(
2267    destination: &mut [u32],
2268    indices: Option<&[u32]>,
2269    positions: Positions<'_>,
2270    mut equal: impl FnMut(u32, u32) -> bool,
2271    workspace: &mut Workspace,
2272) -> Result<usize, Error> {
2273    if let Some(p) = positions.packed_values() {
2274        return remap_into::<true>(
2275            destination,
2276            indices,
2277            p.len(),
2278            |i| position_value_hash(p[i as usize]),
2279            |a, b| p[a as usize] == p[b as usize] && custom_equal(&mut equal, a, b),
2280            false,
2281            workspace,
2282        );
2283    }
2284    remap_into::<true>(
2285        destination,
2286        indices,
2287        positions.len(),
2288        |i| position_hash(positions, i),
2289        |a, b| {
2290            positions.get(a as usize) == positions.get(b as usize) && custom_equal(&mut equal, a, b)
2291        },
2292        false,
2293        workspace,
2294    )
2295}
2296/// Write provoking topology and used reorder prefix. Requires vertex-count plus triangle-count reorder capacity; work exhaustion can partially modify both outputs.
2297///
2298/// # Errors
2299/// Same errors as [`generate_provoking_index_buffer`]. `BufferTooSmall` if an output buffer is too short.
2300pub fn generate_provoking_index_buffer_into(
2301    destination: &mut [u32],
2302    reorder: &mut [u32],
2303    indices: &[u32],
2304    vertex_count: usize,
2305    workspace: &mut Workspace,
2306) -> Result<usize, Error> {
2307    Ok(provoking(
2308        indices,
2309        vertex_count,
2310        Some((destination, reorder)),
2311        workspace,
2312    )?
2313    .1)
2314}