1use 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#[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 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 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 pub const fn len(self) -> usize {
71 self.count
72 }
73 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#[derive(Debug)]
93pub struct VertexRemap {
94 pub remap: Vec<u32>,
96 pub vertex_count: usize,
98}
99#[derive(Debug)]
101pub struct FetchedMesh {
102 pub indices: Vec<u32>,
104 pub vertices: Vec<u8>,
106 pub vertex_count: usize,
108}
109#[derive(Debug)]
111pub struct ProvokingMesh {
112 pub indices: Vec<u32>,
114 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#[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 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 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
569pub 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}
582pub 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#[inline(never)]
684fn custom_equal(equal: &mut impl FnMut(u32, u32) -> bool, a: u32, b: u32) -> bool {
685 equal(a, b)
686}
687pub 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}
723pub 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}
754pub 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}
786pub 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
848pub 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}
885pub 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}
919pub 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
1021pub 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}
1213pub 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}
1225pub 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}
1238pub 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}
1252pub 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 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
1404fn 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}
1539pub 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}
1552pub 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}
1565pub 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#[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 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
1759pub 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
1788pub 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
1821pub 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}
1852pub 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
2043pub 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}
2091pub 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
2123pub 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}
2135pub 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}
2147pub 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}
2159pub 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}
2171pub 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}
2184pub 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}
2227pub 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}
2259pub 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}
2296pub 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}