1#![allow(clippy::too_many_arguments)]
2use crate::math::{root_at_least, RootEstimate, LANES};
4use crate::processing::{cross, dot, finite, point, sub, Context};
5use crate::{Error, Positions, Workspace};
6use alloc::vec::Vec;
7
8struct SqrtCache(crate::math::SqrtCache);
14impl SqrtCache {
15 const fn new() -> Self {
16 Self(crate::math::SqrtCache::new())
17 }
18 #[inline(always)]
19 fn sqrt(&mut self, value: f32) -> f32 {
20 #[cfg(feature = "std")]
21 if value.to_bits() <= f32::MAX.to_bits() {
22 return value.sqrt();
23 }
24 self.0.sqrt(value)
25 }
26}
27#[inline(always)]
30fn sqrt8(values: [f32; LANES]) -> [f32; LANES] {
31 #[cfg(feature = "std")]
32 if values.iter().all(|v| v.to_bits() <= f32::MAX.to_bits()) {
33 return values.map(f32::sqrt);
34 }
35 crate::math::sqrt8(values)
36}
37
38#[derive(Clone, Copy, Debug, Default, PartialEq, Eq)]
40pub struct Meshlet {
41 pub vertex_offset: u32,
43 pub triangle_offset: u32,
45 pub vertex_count: u32,
47 pub triangle_count: u32,
49}
50#[derive(Debug, Default, PartialEq, Eq)]
52pub struct MeshletsGeneric<I: crate::Index = u32> {
53 pub meshlets: Vec<Meshlet>,
55 pub vertices: Vec<I>,
57 pub triangles: Vec<u8>,
59}
60#[derive(Clone, Copy, Debug, PartialEq, Eq)]
62pub struct MeshletSettings {
63 pub max_vertices: usize,
65 pub max_triangles: usize,
67}
68impl Default for MeshletSettings {
69 fn default() -> Self {
70 Self {
71 max_vertices: 64,
72 max_triangles: 124,
73 }
74 }
75}
76#[derive(Clone, Copy, Debug, Default, PartialEq, Eq)]
78pub struct MeshletSizes {
79 pub meshlets: usize,
81 pub vertices: usize,
83 pub triangles: usize,
85}
86#[inline(always)]
92pub fn build_meshlets_bound(
93 index_count: usize,
94 max_vertices: usize,
95 max_triangles: usize,
96) -> Result<usize, Error> {
97 if !index_count.is_multiple_of(3) {
98 return Err(Error::InvalidTopology);
99 }
100 if !(3..=256).contains(&max_vertices) || !(1..=512).contains(&max_triangles) {
101 return Err(Error::InvalidParameter);
102 }
103 let v = max_vertices - 2;
104 let a = small_divide(
105 index_count.checked_add(v - 1).ok_or(Error::SizeOverflow)?,
106 v,
107 );
108 let b = small_divide(
109 (index_count / 3)
110 .checked_add(max_triangles - 1)
111 .ok_or(Error::SizeOverflow)?,
112 max_triangles,
113 );
114 Ok(a.max(b))
115}
116static RECIPROCALS: [u64; 513] = {
118 let mut table = [0u64; 513];
119 let mut d = 1;
120 while d < 513 {
121 table[d] = (1u64 << 32).div_ceil(d as u64);
122 d += 1;
123 }
124 table
125};
126#[inline(always)]
130fn small_divide(x: usize, d: usize) -> usize {
131 match RECIPROCALS.get(d) {
132 Some(&m) if d != 0 && x < 1 << 22 => ((x as u64 * m) >> 32) as usize,
133 _ => x / d,
134 }
135}
136pub(crate) struct Output<'a> {
137 pub(crate) descriptors: &'a mut [Meshlet],
138 pub(crate) vertices: &'a mut [u32],
139 pub(crate) triangles: &'a mut [u8],
140 pub(crate) current: Meshlet,
141 pub(crate) count: usize,
142}
143pub(crate) trait UsedVertices {
144 fn local(&self, vertex: usize) -> i16;
145 fn set_local(&mut self, vertex: usize, local: i16);
146}
147impl UsedVertices for [i16] {
148 #[inline(always)]
149 fn local(&self, vertex: usize) -> i16 {
150 self[vertex]
151 }
152 #[inline(always)]
153 fn set_local(&mut self, vertex: usize, local: i16) {
154 self[vertex] = local;
155 }
156}
157impl<T> UsedVertices for Vec<T>
158where
159 [T]: UsedVertices,
160{
161 #[inline(always)]
162 fn local(&self, vertex: usize) -> i16 {
163 self.as_slice().local(vertex)
164 }
165 #[inline(always)]
166 fn set_local(&mut self, vertex: usize, local: i16) {
167 self.as_mut_slice().set_local(vertex, local);
168 }
169}
170impl Output<'_> {
171 #[inline(always)]
172 pub(crate) fn append<U: UsedVertices + ?Sized>(
173 &mut self,
174 t: &[u32; 3],
175 used: &mut U,
176 s: MeshletSettings,
177 split: bool,
178 ctx: &mut Context<'_>,
179 ) -> Result<bool, Error> {
180 ctx.tick(1)?;
181 let mut m = self.current;
184 let [a, b, c] = t.map(|v| v as usize);
185 let mut local = [used.local(a), used.local(b), used.local(c)];
186 let extra = local.iter().filter(|&&v| v < 0).count();
189 let mut flush = false;
190 if m.vertex_count as usize + extra > s.max_vertices
191 || m.triangle_count as usize >= s.max_triangles
192 || split
193 {
194 self.descriptors[self.count] = m;
195 self.count += 1;
196 ctx.tick(m.vertex_count as usize)?;
197 for &v in &self.vertices[m.vertex_offset as usize..][..m.vertex_count as usize] {
198 used.set_local(v as usize, -1);
199 }
200 m.vertex_offset += m.vertex_count;
201 m.triangle_offset += m.triangle_count * 3;
202 m.vertex_count = 0;
203 m.triangle_count = 0;
204 local = [-1; 3];
205 flush = true;
206 }
207 let off = m.triangle_offset as usize + m.triangle_count as usize * 3;
208 let triangle = &mut self.triangles[off..off + 3];
209 for k in 0..3 {
210 if local[k] < 0 {
211 if k > 0 && t[k] == t[0] {
214 local[k] = local[0];
215 } else if k == 2 && t[k] == t[1] {
216 local[k] = local[1];
217 } else {
218 local[k] = m.vertex_count as i16;
219 used.set_local(t[k] as usize, local[k]);
220 self.vertices[m.vertex_offset as usize + m.vertex_count as usize] = t[k];
221 m.vertex_count += 1;
222 }
223 }
224 triangle[k] = local[k] as u8;
225 }
226 m.triangle_count += 1;
227 self.current = m;
228 Ok(flush)
229 }
230 fn finish(&mut self) -> MeshletSizes {
231 if self.current.triangle_count != 0 {
232 self.descriptors[self.count] = self.current;
233 self.count += 1;
234 }
235 MeshletSizes {
236 meshlets: self.count,
237 vertices: (self.current.vertex_offset + self.current.vertex_count) as usize,
238 triangles: (self.current.triangle_offset + self.current.triangle_count * 3) as usize,
239 }
240 }
241}
242fn validate(s: MeshletSettings, min: usize, weight: f32, split: f32) -> Result<(), Error> {
243 build_meshlets_bound(0, s.max_vertices, s.max_triangles)?;
244 if min == 0
245 || min > s.max_triangles
246 || !weight.is_finite()
247 || !(0.0..=1.0).contains(&weight)
248 || !split.is_finite()
249 || split < 0.
250 {
251 return Err(Error::InvalidParameter);
252 }
253 Ok(())
254}
255#[derive(Clone, Copy, Default)]
256struct Cone {
257 p: [f32; 3],
258 n: [f32; 3],
259}
260#[inline(always)]
262fn cone_position(acc: Cone, count: u32) -> [f32; 3] {
263 let scale = if count == 0 { 0. } else { 1. / count as f32 };
264 acc.p.map(|v| v * scale)
265}
266struct MeshletNormal {
268 low: [f32; 3],
269 high: [f32; 3],
270 exact: Option<[f32; 3]>,
271}
272impl MeshletNormal {
273 fn exact(acc: [f32; 3], roots: &mut SqrtCache) -> Self {
274 let l = dot(acc, acc);
275 let scale = if l == 0. { 0. } else { 1. / roots.sqrt(l) };
276 let n = acc.map(|v| v * scale);
277 Self {
278 low: n,
279 high: n,
280 exact: Some(n),
281 }
282 }
283 #[inline(always)]
287 fn bounds(acc: [f32; 3], roots: &mut SqrtCache) -> Self {
288 let l = dot(acc, acc);
289 let Some(root) = RootEstimate::new(l) else {
290 return Self::exact(acc, roots);
291 };
292 let (scale_low, scale_high) = root.inverse_table();
293 let mut low = [0f32; 3];
294 let mut high = [0f32; 3];
295 for k in 0..3 {
296 let (a, b) = (acc[k] * scale_low, acc[k] * scale_high);
297 (low[k], high[k]) = if acc[k] >= 0. { (a, b) } else { (b, a) };
298 }
299 Self {
300 low,
301 high,
302 exact: None,
303 }
304 }
305}
306#[derive(Clone, Copy)]
309struct VertexState {
310 offset: u32,
311 live: u32,
312 local: i16,
313}
314impl Default for VertexState {
315 fn default() -> Self {
316 Self {
317 offset: 0,
318 live: 0,
319 local: -1,
320 }
321 }
322}
323impl UsedVertices for [VertexState] {
324 #[inline(always)]
325 fn local(&self, vertex: usize) -> i16 {
326 self[vertex].local
327 }
328 #[inline(always)]
329 fn set_local(&mut self, vertex: usize, local: i16) {
330 self[vertex].local = local;
331 }
332}
333struct Adjacency {
334 vertices: Vec<VertexState>,
335 data: Vec<u32>,
336}
337fn adjacency(indices: &[u32], n: usize, ctx: &mut Context<'_>) -> Result<Adjacency, Error> {
338 let mut vertices = ctx.alloc::<VertexState>(n)?;
339 let mut data = ctx.alloc::<u32>(indices.len())?;
340 ctx.tick(n + indices.len() * 2)?;
341 for &v in indices {
342 vertices[v as usize].live += 1;
343 }
344 let mut offset = 0;
345 for vertex in vertices.iter_mut() {
346 vertex.offset = offset;
347 offset += vertex.live;
348 }
349 for (i, t) in indices.as_chunks::<3>().0.iter().enumerate() {
350 for &v in t {
351 let o = &mut vertices[v as usize].offset;
352 data[*o as usize] = i as u32;
353 *o += 1;
354 }
355 }
356 for vertex in vertices.iter_mut() {
357 vertex.offset -= vertex.live;
358 }
359 Ok(Adjacency { vertices, data })
360}
361#[derive(Clone, Copy, Default)]
363struct Node {
364 data: u32,
365 meta: u32,
366}
367impl Node {
368 fn axis(self) -> usize {
369 (self.meta & 3) as usize
370 }
371 fn children(self) -> usize {
372 (self.meta >> 2) as usize
373 }
374 fn set(&mut self, axis: usize, children: usize) -> Result<(), Error> {
375 if children > 0x3fffffff {
376 return Err(Error::SizeOverflow);
377 }
378 self.meta = (children as u32) << 2 | axis as u32;
379 Ok(())
380 }
381}
382
383#[derive(Clone, Copy, Default)]
385struct KdSplit {
386 mean: [f32; 3],
387 axis: usize,
388}
389impl KdSplit {
390 #[inline(always)]
391 fn finish(mean: [f32; 3], vars: [f32; 3]) -> Self {
392 let axis = if vars[0] >= vars[1] && vars[0] >= vars[2] {
393 0
394 } else if vars[1] >= vars[2] {
395 1
396 } else {
397 2
398 };
399 Self { mean, axis }
400 }
401}
402#[inline(always)]
403fn welford(p: [f32; 3], mean: &mut [f32; 3], vars: &mut [f32; 3], runs: f32) {
404 for k in 0..3 {
405 let delta = p[k] - mean[k];
406 mean[k] += delta * runs;
407 vars[k] += delta * (p[k] - mean[k]);
408 }
409}
410fn kd_stats(order: &[u32], cones: &[Cone]) -> KdSplit {
411 let (mut mean, mut vars) = ([0.; 3], [0.; 3]);
412 let (mut runc, mut runs) = (1f32, 1f32);
413 for &v in order {
414 welford(cones[v as usize].p, &mut mean, &mut vars, runs);
415 runc += 1.;
416 runs = 1. / runc;
417 }
418 KdSplit::finish(mean, vars)
419}
420fn kd_stats2(a: &[u32], b: &[u32], cones: &[Cone]) -> (KdSplit, KdSplit) {
423 let (mut am, mut av, mut bm, mut bv) = ([0.; 3], [0.; 3], [0.; 3], [0.; 3]);
424 let (mut runc, mut runs) = (1f32, 1f32);
425 let common = a.len().min(b.len());
426 for (&x, &y) in a[..common].iter().zip(&b[..common]) {
427 welford(cones[x as usize].p, &mut am, &mut av, runs);
428 welford(cones[y as usize].p, &mut bm, &mut bv, runs);
429 runc += 1.;
430 runs = 1. / runc;
431 }
432 let (rest, mean, vars) = if a.len() > common {
433 (&a[common..], &mut am, &mut av)
434 } else {
435 (&b[common..], &mut bm, &mut bv)
436 };
437 for &v in rest {
438 welford(cones[v as usize].p, mean, vars, runs);
439 runc += 1.;
440 runs = 1. / runc;
441 }
442 (KdSplit::finish(am, av), KdSplit::finish(bm, bv))
443}
444fn kd_build(
449 nodes: &mut [Node],
450 offset: usize,
451 order: &mut [u32],
452 cones: &[Cone],
453 depth: usize,
454 split: Option<KdSplit>,
455 ctx: &mut Context<'_>,
456) -> Result<usize, Error> {
457 let n = order.len();
458 let mut middle = 0;
459 let mut stats = KdSplit::default();
460 if n > 8 {
461 ctx.tick(n * 2)?;
462 stats = split.unwrap_or_else(|| kd_stats(order, cones));
463 let (mean, axis) = (stats.mean, stats.axis);
464 finite(mean[axis])?;
465 for i in 0..n {
466 let v = cones[order[i] as usize].p[axis];
467 order.swap(middle, i);
468 middle += usize::from(v < mean[axis]);
469 }
470 }
471 if n <= 8 || middle <= 4 || middle >= n - 4 || depth >= 50 {
472 if n > 0x3fffffff {
473 return Err(Error::SizeOverflow);
474 }
475 ctx.tick(n)?;
476 for (i, &v) in order.iter().enumerate() {
477 nodes[offset + i] = Node {
478 data: v,
479 meta: 3 | ((if i == 0 { n as u32 } else { 0x3fffffff }) << 2),
480 };
481 }
482 return Ok(offset + n);
483 }
484 nodes[offset].data = stats.mean[stats.axis].to_bits();
485 let (left, right) = order.split_at_mut(middle);
486 let (left_split, right_split) = match (left.len() > 8, right.len() > 8) {
487 (true, true) => {
488 let (l, r) = kd_stats2(left, right, cones);
489 (Some(l), Some(r))
490 }
491 (true, false) => (Some(kd_stats(left, cones)), None),
492 (false, true) => (None, Some(kd_stats(right, cones))),
493 (false, false) => (None, None),
494 };
495 let next = kd_build(nodes, offset + 1, left, cones, depth + 1, left_split, ctx)?;
496 nodes[offset].set(stats.axis, next - offset - 1)?;
497 kd_build(nodes, next, right, cones, depth + 1, right_split, ctx)
498}
499fn nearest<const CHECK: bool>(
500 nodes: &mut [Node],
501 root: usize,
502 cones: &[Cone],
503 emitted: &[u8],
504 p: [f32; 3],
505 result: &mut u32,
506 limit: &mut f32,
507 roots: &mut SqrtCache,
508 ctx: &mut Context<'_>,
509) -> Result<(), Error> {
510 let covered = nodes
511 .len()
512 .checked_mul(2)
513 .is_some_and(|bound| ctx.work.covers(bound).unwrap_or(false));
514 if covered && !CHECK {
515 let mut search = Covered {
516 nodes,
517 cones,
518 emitted,
519 p,
520 result: *result,
521 limit: *limit,
522 visits: 0,
523 roots,
524 };
525 let status = search.nearest(root);
526 ctx.work.add_covered(search.visits);
529 *result = search.result;
530 *limit = search.limit;
531 status
532 } else if covered {
533 nearest_inner::<CHECK, true>(nodes, root, cones, emitted, p, result, limit, roots, ctx)
534 } else {
535 nearest_inner::<CHECK, false>(nodes, root, cones, emitted, p, result, limit, roots, ctx)
536 }
537}
538
539struct Covered<'a> {
544 nodes: &'a mut [Node],
545 cones: &'a [Cone],
546 emitted: &'a [u8],
547 p: [f32; 3],
548 result: u32,
549 limit: f32,
550 visits: usize,
551 roots: &'a mut SqrtCache,
552}
553impl Covered<'_> {
554 fn nearest(&mut self, root: usize) -> Result<(), Error> {
555 self.visits += 1;
556 let node = self.nodes[root];
557 if node.children() == 0 {
558 return Ok(());
559 }
560 if node.axis() == 3 {
561 let count = node.children();
562 let n = self.cones.len().min(self.emitted.len());
565 let (cones, emitted) = (&self.cones[..n], &self.emitted[..n]);
566 let mut inactive = true;
567 for item in &self.nodes[root..root + count] {
568 let v = item.data as usize;
569 if emitted[v] == EMITTED {
570 continue;
571 }
572 inactive = false;
573 let d = sub(cones[v].p, self.p);
574 let square = dot(d, d);
575 if PRUNE && (lower_distance(d) >= self.limit || root_at_least(square, self.limit)) {
576 continue;
577 }
578 let distance = moderate_root(square, self.roots);
579 if distance < self.limit {
580 self.result = v as u32;
581 self.limit = distance;
582 }
583 }
584 self.visits += count;
585 if inactive {
586 self.nodes[root].set(3, 0)?;
587 }
588 } else {
589 let delta = self.p[node.axis()] - f32::from_bits(node.data);
590 let first = if delta <= 0. { 0 } else { node.children() };
591 let second = first ^ node.children();
592 if self.nodes[root + 1 + first].children() | self.nodes[root + 1 + second].children()
593 == 0
594 {
595 self.nodes[root].set(node.axis(), 0)?;
596 }
597 self.nearest(root + 1 + first)?;
598 if delta.abs() <= self.limit {
599 self.nearest(root + 1 + second)?;
600 }
601 }
602 Ok(())
603 }
604}
605
606fn nearest_inner<const CHECK: bool, const COVERED: bool>(
607 nodes: &mut [Node],
608 root: usize,
609 cones: &[Cone],
610 emitted: &[u8],
611 p: [f32; 3],
612 result: &mut u32,
613 limit: &mut f32,
614 roots: &mut SqrtCache,
615 ctx: &mut Context<'_>,
616) -> Result<(), Error> {
617 if COVERED {
618 ctx.work.add_covered(1);
619 } else {
620 ctx.tick(1)?;
621 }
622 let node = nodes[root];
623 if node.children() == 0 {
624 return Ok(());
625 }
626 if node.axis() == 3 && !CHECK && (COVERED || ctx.work.covers(node.children())?) {
627 let count = node.children();
629 let mut inactive = true;
630 for item in &nodes[root..root + count] {
631 let v = item.data as usize;
632 if emitted[v] == EMITTED {
633 continue;
634 }
635 inactive = false;
636 let d = sub(cones[v].p, p);
637 let square = dot(d, d);
638 if PRUNE && (lower_distance(d) >= *limit || root_at_least(square, *limit)) {
639 continue;
640 }
641 let distance = moderate_root(square, roots);
642 if distance < *limit {
643 *result = v as u32;
644 *limit = distance;
645 }
646 }
647 if COVERED {
648 ctx.work.add_covered(count);
649 } else {
650 ctx.tick(count)?;
651 }
652 if inactive {
653 nodes[root].set(3, 0)?;
654 }
655 } else if node.axis() == 3 {
656 let mut inactive = true;
657 ctx.scan(0..node.children(), |_ctx, i| {
658 let v = nodes[root + i].data as usize;
659 if emitted[v] == EMITTED {
660 return Ok(());
661 }
662 inactive = false;
663 let d = sub(cones[v].p, p);
664 if !CHECK && PRUNE && (lower_distance(d) >= *limit || root_at_least(dot(d, d), *limit))
665 {
666 return Ok(());
667 }
668 let distance = roots.sqrt(number::<CHECK>(dot(d, d))?);
669 if distance < *limit {
670 *result = v as u32;
671 *limit = distance;
672 }
673 Ok(())
674 })?;
675 if inactive {
676 nodes[root].set(3, 0)?;
677 }
678 } else {
679 let delta = p[node.axis()] - f32::from_bits(node.data);
680 let first = if delta <= 0. { 0 } else { node.children() };
681 let second = first ^ node.children();
682 if nodes[root + 1 + first].children() | nodes[root + 1 + second].children() == 0 {
683 nodes[root].set(node.axis(), 0)?;
684 }
685 nearest_inner::<CHECK, COVERED>(
686 nodes,
687 root + 1 + first,
688 cones,
689 emitted,
690 p,
691 result,
692 limit,
693 roots,
694 ctx,
695 )?;
696 if delta.abs() <= *limit {
697 nearest_inner::<CHECK, COVERED>(
698 nodes,
699 root + 1 + second,
700 cones,
701 emitted,
702 p,
703 result,
704 limit,
705 roots,
706 ctx,
707 )?;
708 }
709 }
710 Ok(())
711}
712const PRUNE: bool = cfg!(not(feature = "std"));
719#[inline(always)]
721fn moderate_root(value: f32, roots: &mut SqrtCache) -> f32 {
722 #[cfg(feature = "std")]
723 {
724 let _ = roots;
725 value.sqrt()
726 }
727 #[cfg(not(feature = "std"))]
728 {
729 roots.sqrt(value)
730 }
731}
732#[inline(always)]
735fn lower_distance(d: [f32; 3]) -> f32 {
736 let (x, y, z) = (d[0].abs(), d[1].abs(), d[2].abs());
738 let m = if x > y { x } else { y };
739 let m = if m > z { m } else { z };
740 if m >= 1.0e-18 {
742 m
743 } else {
744 0.0
745 }
746}
747#[inline(always)]
748fn number<const CHECK: bool>(value: f32) -> Result<f32, Error> {
749 if CHECK {
750 finite(value)
751 } else {
752 Ok(value)
753 }
754}
755#[inline(always)]
756fn distance<const CHECK: bool>(
757 a: [f32; 3],
758 b: [f32; 3],
759 roots: &mut SqrtCache,
760) -> Result<f32, Error> {
761 let d = sub(a, b);
762 Ok(roots.sqrt(number::<CHECK>(dot(d, d))?))
763}
764struct Selection {
768 triangle: u32,
769 priority: i32,
770 lo: f32,
771 hi: f32,
772 known: bool,
773 square: f32,
774}
775impl Selection {
776 fn new() -> Self {
777 Self {
778 triangle: u32::MAX,
779 priority: 5,
780 lo: f32::MAX,
781 hi: f32::MAX,
782 known: true,
783 square: 0.,
784 }
785 }
786}
787struct CandidateInput<'a> {
788 triangles: &'a [[u32; 3]],
789 vertices: &'a [VertexState],
790 cones: &'a [Cone],
791 meshlet: Cone,
792 weight: f32,
793 radius: f32,
794 inverse_low: f32,
797 inverse_high: f32,
798 bounded: bool,
799 accumulated: [f32; 3],
802 normal_low: [f32; 3],
803 normal_high: [f32; 3],
804}
805struct Search<'r> {
809 roots: &'r mut SqrtCache,
810 normal: Option<[f32; 3]>,
811 listed: bool,
814 data: &'r [u32],
815}
816impl CandidateInput<'_> {
817 #[inline(always)]
818 fn one<const CHECK: bool>(
819 &self,
820 tri: u32,
821 local: u16,
822 selected: &mut Selection,
823 search: &mut Search<'_>,
824 ) -> Result<(), Error> {
825 let [a, b, c] = self.triangles[tri as usize].map(|v| v as usize);
826 let (av, bv, cv) = (self.vertices[a], self.vertices[b], self.vertices[c]);
827 if (av.local as u16).min(bv.local as u16).min(cv.local as u16) < local {
832 return Ok(());
833 }
834 self.evaluate::<CHECK>(tri, [av, bv, cv], selected, search)
835 }
836 #[inline(always)]
837 fn evaluate<const CHECK: bool>(
838 &self,
839 tri: u32,
840 [av, bv, cv]: [VertexState; 3],
841 selected: &mut Selection,
842 search: &mut Search<'_>,
843 ) -> Result<(), Error> {
844 let extra = i32::from(av.local < 0) + i32::from(bv.local < 0) + i32::from(cv.local < 0);
845 let (al, bl, cl) = (av.live, bv.live, cv.live);
846 let priority = if extra == 0 {
847 0
848 } else if al == 1 || bl == 1 || cl == 1 {
849 1
850 } else if i32::from(al == 2) + i32::from(bl == 2) + i32::from(cl == 2) >= 2 {
851 1 + extra
852 } else {
853 2 + extra
854 };
855 if priority > selected.priority {
856 return Ok(());
857 }
858 let cone = self.cones[tri as usize];
859 let dp = sub(cone.p, self.meshlet.p);
860 let square = dot(dp, dp);
861 let square = if CHECK { finite(square)? } else { square };
862 if !CHECK && self.bounded {
863 if PRUNE {
864 self.bracketed(tri, priority, cone.n, square, selected, search);
865 } else {
866 self.exact_bounded(tri, priority, cone.n, square, selected, search);
867 }
868 return Ok(());
869 }
870 let clamped = self.clamped(dot(cone.n, self.meshlet.n));
871 let distance = search.roots.sqrt(square);
872 let score = self.score(distance, clamped);
873 if priority < selected.priority || score < selected.hi {
875 *selected = Selection {
876 triangle: tri,
877 priority,
878 lo: score,
879 hi: score,
880 known: true,
881 square,
882 };
883 }
884 Ok(())
885 }
886 #[inline(always)]
887 fn clamped(&self, spread: f32) -> f32 {
888 let cc = 1. - spread * self.weight;
889 if cc < 1e-3 {
890 1e-3
891 } else {
892 cc
893 }
894 }
895 #[inline(always)]
896 fn score(&self, distance: f32, clamped: f32) -> f32 {
897 (1. + distance / self.radius * (1. - self.weight)) * clamped
898 }
899 #[inline(always)]
911 fn score_low(&self, distance: f32, clamped: f32) -> f32 {
912 (1. + distance * self.inverse_low * (1. - self.weight)) * clamped
913 }
914 #[inline(always)]
915 fn score_high(&self, distance: f32, clamped: f32) -> f32 {
916 (1. + distance * self.inverse_high * (1. - self.weight)) * clamped
917 }
918 #[inline(always)]
920 fn clamped_bounds(&self, n: [f32; 3], low: bool) -> f32 {
921 if self.weight == 0. {
924 return 1.;
925 }
926 let (lo, hi) = (self.normal_low, self.normal_high);
929 let term = |k: usize| {
930 let (a, b) = (n[k] * lo[k], n[k] * hi[k]);
931 if (a > b) == low {
932 a
933 } else {
934 b
935 }
936 };
937 self.clamped(term(0) + term(1) + term(2))
939 }
940 #[cold]
942 #[inline(never)]
943 fn exact_normal(&self, search: &mut Search<'_>) -> [f32; 3] {
944 if self.weight == 0. {
945 return [0.; 3];
946 }
947 if let Some(n) = search.normal {
948 return n;
949 }
950 let l = dot(self.accumulated, self.accumulated);
951 let scale = if l == 0. {
952 0.
953 } else {
954 1. / search.roots.sqrt(l)
955 };
956 let n = self.accumulated.map(|v| v * scale);
957 search.normal = Some(n);
958 n
959 }
960 #[inline(always)]
961 fn bracketed(
962 &self,
963 tri: u32,
964 priority: i32,
965 normal: [f32; 3],
966 square: f32,
967 selected: &mut Selection,
968 search: &mut Search<'_>,
969 ) {
970 let clamped_low = self.clamped_bounds(normal, true);
971 let (lo, hi) = match RootEstimate::new(square) {
972 Some(root) => {
973 let low = self.score_low(root.table().0, clamped_low);
976 if priority == selected.priority
977 && (low > selected.hi || (low == selected.hi && !search.listed))
978 {
979 return;
980 }
981 let (dlo, dhi) = root.bounds();
982 (
983 self.score_low(dlo, clamped_low),
984 self.score_high(dhi, self.clamped_bounds(normal, false)),
985 )
986 }
987 None => {
988 let d = search.roots.sqrt(square);
989 (
990 self.score_low(d, clamped_low),
991 self.score_high(d, self.clamped_bounds(normal, false)),
992 )
993 }
994 };
995 if priority == selected.priority {
996 if lo > selected.hi || (lo == selected.hi && !search.listed) {
998 return;
999 }
1000 if hi >= selected.lo {
1001 self.resolve(tri, priority, square, selected, search);
1002 return;
1003 }
1004 }
1005 *selected = Selection {
1006 triangle: tri,
1007 priority,
1008 lo,
1009 hi,
1010 known: false,
1011 square,
1012 };
1013 }
1014 #[inline(always)]
1019 fn exact_bounded(
1020 &self,
1021 tri: u32,
1022 priority: i32,
1023 normal: [f32; 3],
1024 square: f32,
1025 selected: &mut Selection,
1026 search: &mut Search<'_>,
1027 ) {
1028 let n = if self.weight == 0. {
1030 [0.; 3]
1031 } else {
1032 self.exact_normal(search)
1033 };
1034 let distance = moderate_root(square, search.roots);
1035 let score = self.score(distance, self.clamped(dot(normal, n)));
1036 if priority < selected.priority
1037 || score < selected.hi
1038 || (search.listed
1039 && score == selected.hi
1040 && self.visit(tri, search.data) < self.visit(selected.triangle, search.data))
1041 {
1042 *selected = Selection {
1043 triangle: tri,
1044 priority,
1045 lo: score,
1046 hi: score,
1047 known: true,
1048 square,
1049 };
1050 }
1051 }
1052 fn visit(&self, tri: u32, data: &[u32]) -> (u16, usize) {
1055 let mut first = (u16::MAX, 0usize);
1056 for &v in &self.triangles[tri as usize] {
1057 let state = self.vertices[v as usize];
1058 if (state.local as u16) < first.0 {
1059 first = (state.local as u16, v as usize);
1060 }
1061 }
1062 let state = self.vertices[first.1];
1063 let list = &data[state.offset as usize..][..state.live as usize];
1064 (
1065 first.0,
1066 list.iter().position(|&t| t == tri).unwrap_or(list.len()),
1067 )
1068 }
1069 #[cold]
1071 #[inline(never)]
1072 fn resolve(
1073 &self,
1074 tri: u32,
1075 priority: i32,
1076 square: f32,
1077 selected: &mut Selection,
1078 search: &mut Search<'_>,
1079 ) {
1080 let n = self.exact_normal(search);
1081 let mut exact = |tri: u32, square: f32| {
1082 let clamped = self.clamped(dot(self.cones[tri as usize].n, n));
1083 self.score(search.roots.sqrt(square), clamped)
1084 };
1085 if !selected.known {
1086 let score = exact(selected.triangle, selected.square);
1087 selected.lo = score;
1088 selected.hi = score;
1089 selected.known = true;
1090 }
1091 let score = exact(tri, square);
1092 if score < selected.hi
1093 || (search.listed
1094 && score == selected.hi
1095 && self.visit(tri, search.data) < self.visit(selected.triangle, search.data))
1096 {
1097 *selected = Selection {
1098 triangle: tri,
1099 priority,
1100 lo: score,
1101 hi: score,
1102 known: true,
1103 square,
1104 };
1105 }
1106 }
1107 #[inline(always)]
1118 fn neighbors<const CHECK: bool>(
1119 &self,
1120 active: &mut Active,
1121 data: &[u32],
1122 roots: &mut SqrtCache,
1123 normal: Option<[f32; 3]>,
1124 listed: Option<&mut Candidates>,
1125 emitted: &[u8],
1126 ctx: &mut Context<'_>,
1127 ) -> Result<u32, Error> {
1128 if let Some(listed) = listed.filter(|listed| !CHECK && !listed.overflow) {
1129 let mut total = 0usize;
1130 let mut kept = 0;
1131 for k in 0..active.len {
1132 let v = active.list[k];
1133 let live = self.vertices[v as usize].live as usize;
1134 if live != 0 {
1135 active.list[kept] = v;
1136 kept += 1;
1137 total += live;
1138 }
1139 }
1140 active.len = kept;
1141 if ctx.work.covers(total)? {
1142 let mut search = Search {
1143 roots,
1144 normal,
1145 listed: true,
1146 data,
1147 };
1148 let mut selected = Selection::new();
1149 let mut i = 0;
1150 while i < listed.len {
1151 let tri = listed.list[i];
1152 if emitted[tri as usize] == EMITTED {
1153 listed.len -= 1;
1154 listed.list[i] = listed.list[listed.len];
1155 continue;
1156 }
1157 let [a, b, c] = self.triangles[tri as usize].map(|v| v as usize);
1158 let states = [self.vertices[a], self.vertices[b], self.vertices[c]];
1159 self.evaluate::<CHECK>(tri, states, &mut selected, &mut search)?;
1160 i += 1;
1161 }
1162 ctx.tick(total)?;
1163 return Ok(selected.triangle);
1164 }
1165 }
1166 let mut search = Search {
1167 roots,
1168 normal,
1169 listed: false,
1170 data,
1171 };
1172 let mut selected = Selection::new();
1173 let mut visited = 0usize;
1174 let mut kept = 0;
1175 for k in 0..active.len {
1176 let v = active.list[k];
1177 let state = self.vertices[v as usize];
1178 let live = state.live as usize;
1179 if live == 0 {
1182 continue;
1183 }
1184 active.list[kept] = v;
1185 kept += 1;
1186 let local = state.local as u16;
1187 if !ctx.work.covers(visited + live)? {
1188 ctx.tick(visited)?;
1189 for &v in &active.list[k..active.len] {
1190 let state = self.vertices[v as usize];
1191 let off = state.offset as usize;
1192 for &tri in &data[off..off + state.live as usize] {
1193 ctx.tick(1)?;
1194 self.one::<CHECK>(tri, state.local as u16, &mut selected, &mut search)?;
1195 }
1196 }
1197 return Ok(selected.triangle);
1198 }
1199 let off = state.offset as usize;
1200 for &tri in &data[off..off + live] {
1201 visited += 1;
1202 if let Err(error) = self.one::<CHECK>(tri, local, &mut selected, &mut search) {
1203 ctx.tick(visited)?;
1204 return Err(error);
1205 }
1206 }
1207 }
1208 active.len = kept;
1209 ctx.tick(visited)?;
1210 Ok(selected.triangle)
1211 }
1212}
1213const EMITTED: u8 = 1;
1215const LISTED: u8 = 2;
1216struct Candidates {
1219 list: [u32; 1024],
1220 len: usize,
1221 overflow: bool,
1222}
1223impl Candidates {
1224 fn new() -> Self {
1225 Self {
1226 list: [0; 1024],
1227 len: 0,
1228 overflow: false,
1229 }
1230 }
1231 fn clear(&mut self, emitted: &mut [u8]) {
1232 for &t in &self.list[..self.len] {
1233 if emitted[t as usize] == LISTED {
1234 emitted[t as usize] = 0;
1235 }
1236 }
1237 self.len = 0;
1238 self.overflow = false;
1239 }
1240 fn add(&mut self, live: &[u32], emitted: &mut [u8]) {
1241 for &t in live {
1242 if emitted[t as usize] == 0 {
1243 if self.len == self.list.len() {
1244 self.overflow = true;
1245 return;
1246 }
1247 emitted[t as usize] = LISTED;
1248 self.list[self.len] = t;
1249 self.len += 1;
1250 }
1251 }
1252 }
1253}
1254struct Active {
1258 list: [u32; 256],
1259 len: usize,
1260 offset: u32,
1261 synced: usize,
1262}
1263impl Active {
1264 fn new() -> Self {
1265 Self {
1266 list: [0; 256],
1267 len: 0,
1268 offset: 0,
1269 synced: 0,
1270 }
1271 }
1272 #[inline(always)]
1273 fn sync(
1274 &mut self,
1275 out: &Output<'_>,
1276 adj: &Adjacency,
1277 listed: Option<(&mut Candidates, &mut [u8])>,
1278 ) {
1279 let count = out.current.vertex_count as usize;
1280 let reset = out.current.vertex_offset != self.offset || count < self.synced;
1281 if reset {
1282 self.offset = out.current.vertex_offset;
1283 self.len = 0;
1284 self.synced = 0;
1285 }
1286 let added = &out.vertices[self.offset as usize..][self.synced..count];
1287 if let Some((candidates, emitted)) = listed {
1288 if reset {
1289 candidates.clear(emitted);
1290 }
1291 for &v in added {
1292 let state = adj.vertices[v as usize];
1293 if !candidates.overflow {
1294 let off = state.offset as usize;
1295 candidates.add(&adj.data[off..off + state.live as usize], emitted);
1296 }
1297 }
1298 }
1299 for &v in added {
1300 self.list[self.len] = v;
1301 self.len += 1;
1302 }
1303 self.synced = count;
1304 }
1305}
1306fn fill_cones<const CHECK: bool>(
1309 triangles: &[[u32; 3]],
1310 cones: &mut [Cone],
1311 read: impl Fn(u32) -> [f32; 3],
1312) -> Result<f32, Error> {
1313 let mut mesh_area = 0.;
1314 for (group, out_cones) in triangles.chunks(LANES).zip(cones.chunks_mut(LANES)) {
1315 let mut normals = [[0f32; 3]; LANES];
1316 let mut squares = [1f32; LANES];
1317 for (k, (t, cone)) in group.iter().zip(out_cones.iter_mut()).enumerate() {
1318 let a = read(t[0]);
1319 let b = read(t[1]);
1320 let c = read(t[2]);
1321 let normal = cross(sub(b, a), sub(c, a));
1322 squares[k] = number::<CHECK>(dot(normal, normal))?;
1323 normals[k] = normal;
1324 for j in 0..3 {
1325 cone.p[j] = number::<CHECK>((a[j] + b[j] + c[j]) / 3.)?;
1326 }
1327 }
1328 let areas = sqrt8(squares);
1329 for (k, cone) in out_cones.iter_mut().enumerate() {
1330 let area = areas[k];
1331 let inv = if area == 0. { 0. } else { 1. / area };
1332 for (n, &v) in cone.n.iter_mut().zip(&normals[k]) {
1333 *n = number::<CHECK>(v * inv)?;
1334 }
1335 mesh_area = number::<CHECK>(mesh_area + area)?;
1336 }
1337 }
1338 Ok(mesh_area)
1339}
1340fn flex<const CHECK: bool, const ZERO_WEIGHT: bool>(
1341 out: &mut Output<'_>,
1342 indices: &[u32],
1343 p: Positions<'_>,
1344 s: MeshletSettings,
1345 min: usize,
1346 weight: f32,
1347 split_factor: f32,
1348 ctx: &mut Context<'_>,
1349) -> Result<(), Error> {
1350 let weight = if ZERO_WEIGHT { 0. } else { weight };
1354 if indices.is_empty() {
1355 return Ok(());
1356 }
1357 let n = indices.len() / 3;
1358 let node_count = n.checked_mul(2).ok_or(Error::SizeOverflow)?;
1359 let mut roots = SqrtCache::new();
1361 let mut adj = adjacency(indices, p.len(), ctx)?;
1362 let mut emitted = ctx.alloc::<u8>(n)?;
1363 let mut cones = ctx.alloc::<Cone>(n)?;
1364 ctx.tick(n)?;
1365 let triangles = indices.as_chunks::<3>().0;
1366 let mesh_area = if let Some(values) = p.packed_values() {
1367 fill_cones::<CHECK>(triangles, &mut cones, |i| values[i as usize])?
1368 } else {
1369 fill_cones::<CHECK>(triangles, &mut cones, |i| point(p, i))?
1370 };
1371 let radius = roots.sqrt(number::<CHECK>(
1372 mesh_area / n as f32 * 0.5 * s.max_triangles as f32,
1373 )?) * 0.5;
1374 let mut order = ctx.alloc(n)?;
1375 for (i, v) in order.iter_mut().enumerate() {
1376 *v = i as u32;
1377 }
1378 let mut nodes = ctx.alloc(node_count)?;
1379 kd_build(&mut nodes, 0, &mut order, &cones, 0, None, ctx)?;
1380 ctx.tick(n.checked_mul(2).ok_or(Error::SizeOverflow)?)?;
1381 let mut corner = [f32::MAX; 3];
1382 for c in &cones {
1383 for (k, v) in corner.iter_mut().enumerate() {
1384 if *v > c.p[k] {
1385 *v = c.p[k];
1386 }
1387 }
1388 }
1389 let mut initial = u32::MAX;
1390 let mut score = f32::MAX;
1391 for (i, c) in cones.iter().enumerate() {
1392 if !CHECK && PRUNE && initial != u32::MAX && {
1393 let d = sub(c.p, corner);
1394 lower_distance(d) >= score || root_at_least(dot(d, d), score)
1395 } {
1396 continue;
1397 }
1398 let d = distance::<CHECK>(c.p, corner, &mut roots)?;
1399 if initial == u32::MAX || d < score {
1400 initial = i as u32;
1401 score = d;
1402 }
1403 }
1404 let mut seeds = [0u32; 256];
1405 let mut seed_count = 0;
1406 let mut acc = Cone::default();
1407 let mut active = Active::new();
1408 let inverse = 1. / radius;
1411 let inverse_low = inverse * 0.999_999_5;
1412 let inverse_high = inverse * 1.000_000_5;
1413 let bounded = !CHECK
1414 && radius.is_normal()
1415 && radius > 0.
1416 && inverse_low.is_normal()
1417 && inverse_high.is_finite();
1418 let mut candidates = (bounded && n >= 256).then(Candidates::new);
1422 loop {
1423 ctx.tick(1)?;
1424 let mc_position = cone_position(acc, out.current.triangle_count);
1425 let mut best;
1426 if out.count == 0 && out.current.triangle_count == 0 {
1427 best = initial;
1428 } else {
1429 let normal = if bounded && weight == 0. {
1433 MeshletNormal {
1434 exact: Some([0.; 3]),
1435 low: [0.; 3],
1436 high: [0.; 3],
1437 }
1438 } else if bounded {
1439 MeshletNormal::bounds(acc.n, &mut roots)
1440 } else {
1441 MeshletNormal::exact(acc.n, &mut roots)
1442 };
1443 let input = CandidateInput {
1444 triangles: indices.as_chunks::<3>().0,
1445 vertices: &adj.vertices,
1446 cones: &cones,
1447 meshlet: Cone {
1448 p: mc_position,
1449 n: normal.exact.unwrap_or_default(),
1450 },
1451 weight,
1452 radius,
1453 inverse_low,
1454 inverse_high,
1455 bounded,
1456 accumulated: acc.n,
1457 normal_low: normal.low,
1458 normal_high: normal.high,
1459 };
1460 active.sync(
1461 out,
1462 &adj,
1463 candidates
1464 .as_mut()
1465 .map(|candidates| (candidates, emitted.as_mut_slice())),
1466 );
1467 best = input.neighbors::<CHECK>(
1468 &mut active,
1469 &adj.data,
1470 &mut roots,
1471 normal.exact,
1472 candidates.as_mut(),
1473 &emitted,
1474 ctx,
1475 )?;
1476 }
1477 let mut split = false;
1478 if best == u32::MAX {
1479 let mut d = f32::MAX;
1480 nearest::<CHECK>(
1481 &mut nodes,
1482 0,
1483 &cones,
1484 &emitted,
1485 mc_position,
1486 &mut best,
1487 &mut d,
1488 &mut roots,
1489 ctx,
1490 )?;
1491 split = out.current.triangle_count as usize >= min
1492 && split_factor > 0.
1493 && d > radius * split_factor;
1494 }
1495 if best == u32::MAX {
1496 break;
1497 }
1498 let extra = indices[best as usize * 3..][..3]
1499 .iter()
1500 .filter(|&&v| adj.vertices[v as usize].local < 0)
1501 .count();
1502 if split
1503 || out.current.vertex_count as usize + extra > s.max_vertices
1504 || out.current.triangle_count as usize >= s.max_triangles
1505 {
1506 let mut keep = 0;
1507 for i in 0..seed_count {
1508 if emitted[seeds[i] as usize] != EMITTED {
1509 seeds[keep] = seeds[i];
1510 keep += 1;
1511 }
1512 }
1513 seed_count = keep.min(252);
1514 let mut candidates = [u32::MAX; 4];
1515 let mut lives = [u32::MAX; 4];
1516 let mut scores = [f32::MAX; 4];
1517 for &v in &out.vertices[out.current.vertex_offset as usize..]
1518 [..out.current.vertex_count as usize]
1519 {
1520 let off = adj.vertices[v as usize].offset as usize;
1521 let mut neighbor = u32::MAX;
1522 let mut live = u32::MAX;
1523 ctx.scan(
1524 adj.data[off..off + adj.vertices[v as usize].live as usize]
1525 .iter()
1526 .copied(),
1527 |_ctx, tri| {
1528 let t = &indices[tri as usize * 3..][..3];
1529 let l = adj.vertices[t[0] as usize].live
1530 + adj.vertices[t[1] as usize].live
1531 + adj.vertices[t[2] as usize].live;
1532 if l < live {
1533 neighbor = tri;
1534 live = l;
1535 }
1536 Ok(())
1537 },
1538 )?;
1539 if neighbor == u32::MAX {
1540 continue;
1541 }
1542 let d = distance::<CHECK>(cones[neighbor as usize].p, corner, &mut roots)?;
1543 for j in 0..4 {
1544 if live < lives[j] || (live == lives[j] && d <= scores[j]) {
1545 candidates[j] = neighbor;
1546 lives[j] = live;
1547 scores[j] = d;
1548 break;
1549 }
1550 }
1551 }
1552 for tri in candidates {
1553 if tri != u32::MAX {
1554 seeds[seed_count] = tri;
1555 seed_count += 1;
1556 }
1557 }
1558 let mut seed = u32::MAX;
1559 let mut live = u32::MAX;
1560 let mut score = f32::MAX;
1561 ctx.scan(seeds[..seed_count].iter().copied(), |_ctx, tri| {
1562 let t = &indices[tri as usize * 3..][..3];
1563 let l = adj.vertices[t[0] as usize].live
1564 + adj.vertices[t[1] as usize].live
1565 + adj.vertices[t[2] as usize].live;
1566 if !CHECK
1567 && (l > live
1568 || (PRUNE && l == live && {
1569 let d = sub(cones[tri as usize].p, corner);
1570 lower_distance(d) >= score || root_at_least(dot(d, d), score)
1571 }))
1572 {
1573 return Ok(());
1574 }
1575 let d = distance::<CHECK>(cones[tri as usize].p, corner, &mut roots)?;
1576 if l < live || (l == live && d < score) {
1577 seed = tri;
1578 live = l;
1579 score = d;
1580 }
1581 Ok(())
1582 })?;
1583 if seed != u32::MAX {
1584 best = seed;
1585 }
1586 }
1587 let t = &indices.as_chunks::<3>().0[best as usize];
1588 if out.append(t, &mut adj.vertices, s, split, ctx)? {
1589 acc = Cone::default();
1590 }
1591 for &v in t {
1592 let state = &mut adj.vertices[v as usize];
1593 let list = &mut adj.data[state.offset as usize..][..state.live as usize];
1594 let found = if ctx.work.covers(list.len())? {
1597 let found = list.iter().position(|&tri| tri == best);
1598 ctx.tick(found.map_or(list.len(), |i| i + 1))?;
1599 found
1600 } else {
1601 let mut found = None;
1602 for (i, &tri) in list.iter().enumerate() {
1603 ctx.tick(1)?;
1604 if tri == best {
1605 found = Some(i);
1606 break;
1607 }
1608 }
1609 found
1610 };
1611 if let Some(i) = found {
1612 list[i] = list[list.len() - 1];
1613 state.live -= 1;
1614 }
1615 }
1616 for k in 0..3 {
1617 acc.p[k] = number::<CHECK>(acc.p[k] + cones[best as usize].p[k])?;
1618 acc.n[k] = number::<CHECK>(acc.n[k] + cones[best as usize].n[k])?;
1619 }
1620 emitted[best as usize] = EMITTED;
1621 }
1622 Ok(())
1623}
1624fn scan_covered(
1628 out: &mut Output<'_>,
1629 triangles: &[[u32; 3]],
1630 used: &mut [i16],
1631 s: MeshletSettings,
1632) -> usize {
1633 let mut m = out.current;
1634 let mut count = out.count;
1635 let mut visits = triangles.len();
1636 for (t, triangle) in triangles
1637 .iter()
1638 .zip(out.triangles[..triangles.len() * 3].as_chunks_mut::<3>().0)
1639 {
1640 let mut local = t.map(|v| used[v as usize]);
1641 let extra = local.iter().filter(|&&v| v < 0).count();
1642 if m.vertex_count as usize + extra > s.max_vertices
1643 || m.triangle_count as usize >= s.max_triangles
1644 {
1645 out.descriptors[count] = m;
1646 count += 1;
1647 visits += m.vertex_count as usize;
1648 for &v in &out.vertices[m.vertex_offset as usize..][..m.vertex_count as usize] {
1649 used[v as usize] = -1;
1650 }
1651 m.vertex_offset += m.vertex_count;
1652 m.triangle_offset += m.triangle_count * 3;
1653 m.vertex_count = 0;
1654 m.triangle_count = 0;
1655 local = [-1; 3];
1656 }
1657 for k in 0..3 {
1658 if local[k] < 0 {
1659 if k > 0 && t[k] == t[0] {
1660 local[k] = local[0];
1661 } else if k == 2 && t[k] == t[1] {
1662 local[k] = local[1];
1663 } else {
1664 local[k] = m.vertex_count as i16;
1665 used[t[k] as usize] = local[k];
1666 out.vertices[m.vertex_offset as usize + m.vertex_count as usize] = t[k];
1667 m.vertex_count += 1;
1668 }
1669 }
1670 triangle[k] = local[k] as u8;
1671 }
1672 m.triangle_count += 1;
1673 }
1674 out.current = m;
1675 out.count = count;
1676 visits
1677}
1678fn scan(
1679 out: &mut Output<'_>,
1680 indices: &[u32],
1681 n: usize,
1682 s: MeshletSettings,
1683 ctx: &mut Context<'_>,
1684) -> Result<(), Error> {
1685 let mut used = ctx.alloc::<i16>(n)?;
1686 used.fill(-1);
1687 let triangles = indices.as_chunks::<3>().0;
1688 if indices
1692 .len()
1693 .checked_add(triangles.len())
1694 .is_some_and(|bound| ctx.work.covers(bound).unwrap_or(false))
1695 {
1696 let visits = scan_covered(out, triangles, &mut used, s);
1697 ctx.tick(visits)?;
1698 } else {
1699 for t in triangles {
1700 out.append(t, &mut used, s, false, ctx)?;
1701 }
1702 }
1703 Ok(())
1704}
1705#[derive(Clone, Copy)]
1706pub(crate) enum Builder {
1707 Scan,
1708 Flex {
1709 min: usize,
1710 weight: f32,
1711 split: f32,
1712 },
1713 Spatial {
1715 min: usize,
1716 fill: f32,
1717 parallel: bool,
1718 },
1719}
1720fn min_triangles(b: Builder, s: MeshletSettings) -> usize {
1721 match b {
1722 Builder::Scan => s.max_triangles,
1723 Builder::Flex { min, .. } | Builder::Spatial { min, .. } => min,
1724 }
1725}
1726fn execute(
1727 out: &mut Output<'_>,
1728 indices: &[u32],
1729 n: usize,
1730 p: Option<Positions<'_>>,
1731 s: MeshletSettings,
1732 b: Builder,
1733 ctx: &mut Context<'_>,
1734) -> Result<MeshletSizes, Error> {
1735 match b {
1736 Builder::Scan => scan(out, indices, n, s, ctx)?,
1737 Builder::Flex { min, weight, split } => {
1738 let p = p.expect("positions builder");
1739 if ctx.moderate {
1740 if weight == 0. {
1741 flex::<false, true>(out, indices, p, s, min, weight, split, ctx)?;
1742 } else {
1743 flex::<false, false>(out, indices, p, s, min, weight, split, ctx)?;
1744 }
1745 } else {
1746 flex::<true, false>(out, indices, p, s, min, weight, split, ctx)?;
1747 }
1748 }
1749 Builder::Spatial {
1750 min,
1751 fill,
1752 parallel,
1753 } => crate::meshlet_spatial::spatial(
1754 out,
1755 indices,
1756 p.expect("positions builder"),
1757 s,
1758 min,
1759 fill,
1760 parallel,
1761 ctx,
1762 )?,
1763 }
1764 Ok(out.finish())
1765}
1766fn check(s: MeshletSettings, b: Builder) -> Result<(), Error> {
1767 match b {
1768 Builder::Scan => validate(s, s.max_triangles, 0., 0.),
1769 Builder::Flex { min, weight, split } => validate(s, min, weight, split),
1770 Builder::Spatial { min, fill, .. } => {
1771 validate(s, min, 0., 0.)?;
1772 if !fill.is_finite() || fill < 0. {
1773 return Err(Error::InvalidParameter);
1774 }
1775 Ok(())
1776 }
1777 }
1778}
1779fn build(
1780 indices: &[u32],
1781 n: usize,
1782 p: Option<Positions<'_>>,
1783 s: MeshletSettings,
1784 b: Builder,
1785 workspace: &mut Workspace,
1786 trusted_moderate: Option<bool>,
1787) -> Result<MeshletsGeneric, Error> {
1788 let mut ctx = Context::new(workspace)?;
1789 check(s, b)?;
1790 ctx.topology(indices, n)?;
1791 if let Some(p) = p {
1792 if let Some(moderate) = trusted_moderate {
1793 ctx.moderate = moderate;
1794 } else {
1795 ctx.positions(p)?;
1796 }
1797 }
1798 let bound = build_meshlets_bound(indices.len(), s.max_vertices, min_triangles(b, s))?;
1799 let mut result = MeshletsGeneric {
1800 meshlets: ctx.alloc(bound)?,
1801 vertices: ctx.alloc(indices.len())?,
1802 triangles: ctx.alloc(indices.len())?,
1803 };
1804 let sizes = execute(
1805 &mut Output {
1806 descriptors: &mut result.meshlets,
1807 vertices: &mut result.vertices,
1808 triangles: &mut result.triangles,
1809 current: Meshlet::default(),
1810 count: 0,
1811 },
1812 indices,
1813 n,
1814 p,
1815 s,
1816 b,
1817 &mut ctx,
1818 )?;
1819 result.meshlets.truncate(sizes.meshlets);
1820 result.vertices.truncate(sizes.vertices);
1821 result.triangles.truncate(sizes.triangles);
1822 Ok(result)
1823}
1824fn build_into(
1825 descriptors: &mut [Meshlet],
1826 vertices: &mut [u32],
1827 triangles: &mut [u8],
1828 indices: &[u32],
1829 n: usize,
1830 p: Option<Positions<'_>>,
1831 s: MeshletSettings,
1832 b: Builder,
1833 workspace: &mut Workspace,
1834) -> Result<MeshletSizes, Error> {
1835 let mut ctx = Context::new(workspace)?;
1836 check(s, b)?;
1837 let bound = build_meshlets_bound(indices.len(), s.max_vertices, min_triangles(b, s))?;
1838 if descriptors.len() < bound
1839 || vertices.len() < indices.len()
1840 || triangles.len() < indices.len()
1841 {
1842 return Err(Error::BufferTooSmall);
1843 }
1844 ctx.topology(indices, n)?;
1845 if let Some(p) = p {
1846 ctx.positions(p)?;
1847 }
1848 execute(
1849 &mut Output {
1850 descriptors,
1851 vertices,
1852 triangles,
1853 current: Meshlet::default(),
1854 count: 0,
1855 },
1856 indices,
1857 n,
1858 p,
1859 s,
1860 b,
1861 &mut ctx,
1862 )
1863}
1864#[inline]
1870pub fn build_meshlets_scan_generic<I: crate::Index>(
1871 indices: &[I],
1872 vertex_count: usize,
1873 s: MeshletSettings,
1874 workspace: &mut Workspace,
1875) -> Result<MeshletsGeneric<I>, Error> {
1876 I::with_input(indices, workspace, |indices, workspace| {
1877 build_meshlets_scan_u32(indices, vertex_count, s, workspace)
1878 .and_then(|value| crate::index::Convert::<I>::convert(value, workspace))
1879 })
1880}
1881
1882fn build_meshlets_scan_u32(
1883 indices: &[u32],
1884 vertex_count: usize,
1885 s: MeshletSettings,
1886 workspace: &mut Workspace,
1887) -> Result<MeshletsGeneric, Error> {
1888 build(
1889 indices,
1890 vertex_count,
1891 None,
1892 s,
1893 Builder::Scan,
1894 workspace,
1895 None,
1896 )
1897}
1898#[inline]
1905pub fn build_meshlets_generic<I: crate::Index>(
1906 indices: &[I],
1907 p: Positions<'_>,
1908 s: MeshletSettings,
1909 cone_weight: f32,
1910 workspace: &mut Workspace,
1911) -> Result<MeshletsGeneric<I>, Error> {
1912 I::with_input(indices, workspace, |indices, workspace| {
1913 build_meshlets_u32(indices, p, s, cone_weight, workspace)
1914 .and_then(|value| crate::index::Convert::<I>::convert(value, workspace))
1915 })
1916}
1917
1918fn build_meshlets_u32(
1919 indices: &[u32],
1920 p: Positions<'_>,
1921 s: MeshletSettings,
1922 cone_weight: f32,
1923 workspace: &mut Workspace,
1924) -> Result<MeshletsGeneric, Error> {
1925 build_meshlets_flex_generic(indices, p, s, s.max_triangles, cone_weight, 0., workspace)
1926}
1927#[inline]
1934pub fn build_meshlets_flex_generic<I: crate::Index>(
1935 indices: &[I],
1936 p: Positions<'_>,
1937 s: MeshletSettings,
1938 min_triangles: usize,
1939 cone_weight: f32,
1940 split_factor: f32,
1941 workspace: &mut Workspace,
1942) -> Result<MeshletsGeneric<I>, Error> {
1943 I::with_input(indices, workspace, |indices, workspace| {
1944 build_meshlets_flex_u32(
1945 indices,
1946 p,
1947 s,
1948 min_triangles,
1949 cone_weight,
1950 split_factor,
1951 workspace,
1952 )
1953 .and_then(|value| crate::index::Convert::<I>::convert(value, workspace))
1954 })
1955}
1956
1957fn build_meshlets_flex_u32(
1958 indices: &[u32],
1959 p: Positions<'_>,
1960 s: MeshletSettings,
1961 min_triangles: usize,
1962 cone_weight: f32,
1963 split_factor: f32,
1964 workspace: &mut Workspace,
1965) -> Result<MeshletsGeneric, Error> {
1966 build(
1967 indices,
1968 p.len(),
1969 Some(p),
1970 s,
1971 Builder::Flex {
1972 min: min_triangles,
1973 weight: cone_weight,
1974 split: split_factor,
1975 },
1976 workspace,
1977 None,
1978 )
1979}
1980#[cfg(feature = "clusterlod")]
1981pub(crate) fn build_meshlets_flex_validated(
1982 indices: &[u32],
1983 p: Positions<'_>,
1984 s: MeshletSettings,
1985 min_triangles: usize,
1986 cone_weight: f32,
1987 split_factor: f32,
1988 moderate: bool,
1989 workspace: &mut Workspace,
1990) -> Result<MeshletsGeneric, Error> {
1991 build(
1992 indices,
1993 p.len(),
1994 Some(p),
1995 s,
1996 Builder::Flex {
1997 min: min_triangles,
1998 weight: cone_weight,
1999 split: split_factor,
2000 },
2001 workspace,
2002 Some(moderate),
2003 )
2004}
2005#[inline]
2012pub fn build_meshlets_spatial_generic<I: crate::Index>(
2013 indices: &[I],
2014 p: Positions<'_>,
2015 s: MeshletSettings,
2016 min_triangles: usize,
2017 fill_weight: f32,
2018 workspace: &mut Workspace,
2019) -> Result<MeshletsGeneric<I>, Error> {
2020 I::with_input(indices, workspace, |indices, workspace| {
2021 build_meshlets_spatial_u32(indices, p, s, min_triangles, fill_weight, workspace)
2022 .and_then(|value| crate::index::Convert::<I>::convert(value, workspace))
2023 })
2024}
2025
2026fn build_meshlets_spatial_u32(
2027 indices: &[u32],
2028 p: Positions<'_>,
2029 s: MeshletSettings,
2030 min_triangles: usize,
2031 fill_weight: f32,
2032 workspace: &mut Workspace,
2033) -> Result<MeshletsGeneric, Error> {
2034 build(
2035 indices,
2036 p.len(),
2037 Some(p),
2038 s,
2039 Builder::Spatial {
2040 min: min_triangles,
2041 fill: fill_weight,
2042 parallel: false,
2043 },
2044 workspace,
2045 None,
2046 )
2047}
2048#[cfg(feature = "parallel")]
2053pub(crate) fn build_meshlets_spatial_parallel_generic<I: crate::Index>(
2054 indices: &[I],
2055 p: Positions<'_>,
2056 s: MeshletSettings,
2057 min_triangles: usize,
2058 fill_weight: f32,
2059 workspace: &mut Workspace,
2060) -> Result<MeshletsGeneric<I>, Error> {
2061 let limits = workspace.limits();
2062 let parallel = limits.max_bytes == usize::MAX
2063 && limits.max_work == u64::MAX
2064 && rayon::current_num_threads() > 1;
2065 I::with_input(indices, workspace, |indices, workspace| {
2066 build(
2067 indices,
2068 p.len(),
2069 Some(p),
2070 s,
2071 Builder::Spatial {
2072 min: min_triangles,
2073 fill: fill_weight,
2074 parallel,
2075 },
2076 workspace,
2077 None,
2078 )
2079 .and_then(|value| crate::index::Convert::<I>::convert(value, workspace))
2080 })
2081}
2082#[cfg(feature = "clusterlod")]
2083pub(crate) fn build_meshlets_spatial_validated(
2084 indices: &[u32],
2085 p: Positions<'_>,
2086 s: MeshletSettings,
2087 min_triangles: usize,
2088 fill_weight: f32,
2089 moderate: bool,
2090 workspace: &mut Workspace,
2091) -> Result<MeshletsGeneric, Error> {
2092 build(
2093 indices,
2094 p.len(),
2095 Some(p),
2096 s,
2097 Builder::Spatial {
2098 min: min_triangles,
2099 fill: fill_weight,
2100 parallel: false,
2101 },
2102 workspace,
2103 Some(moderate),
2104 )
2105}
2106#[inline]
2111pub fn build_meshlets_scan_into_generic<I: crate::Index>(
2112 descriptors: &mut [Meshlet],
2113 vertices: &mut [I],
2114 triangles: &mut [u8],
2115 indices: &[I],
2116 vertex_count: usize,
2117 s: MeshletSettings,
2118 workspace: &mut Workspace,
2119) -> Result<MeshletSizes, Error> {
2120 I::with_input(indices, workspace, |indices, workspace| {
2121 I::with_mut(vertices, workspace, |vertices, workspace| {
2122 build_meshlets_scan_into_u32(
2123 descriptors,
2124 vertices,
2125 triangles,
2126 indices,
2127 vertex_count,
2128 s,
2129 workspace,
2130 )
2131 })
2132 })
2133}
2134
2135fn build_meshlets_scan_into_u32(
2136 descriptors: &mut [Meshlet],
2137 vertices: &mut [u32],
2138 triangles: &mut [u8],
2139 indices: &[u32],
2140 vertex_count: usize,
2141 s: MeshletSettings,
2142 workspace: &mut Workspace,
2143) -> Result<MeshletSizes, Error> {
2144 build_into(
2145 descriptors,
2146 vertices,
2147 triangles,
2148 indices,
2149 vertex_count,
2150 None,
2151 s,
2152 Builder::Scan,
2153 workspace,
2154 )
2155}
2156#[inline]
2161pub fn build_meshlets_into_generic<I: crate::Index>(
2162 descriptors: &mut [Meshlet],
2163 vertices: &mut [I],
2164 triangles: &mut [u8],
2165 indices: &[I],
2166 p: Positions<'_>,
2167 s: MeshletSettings,
2168 cone_weight: f32,
2169 workspace: &mut Workspace,
2170) -> Result<MeshletSizes, Error> {
2171 I::with_input(indices, workspace, |indices, workspace| {
2172 I::with_mut(vertices, workspace, |vertices, workspace| {
2173 build_meshlets_into_u32(
2174 descriptors,
2175 vertices,
2176 triangles,
2177 indices,
2178 p,
2179 s,
2180 cone_weight,
2181 workspace,
2182 )
2183 })
2184 })
2185}
2186
2187#[allow(clippy::too_many_arguments)]
2188fn build_meshlets_into_u32(
2189 descriptors: &mut [Meshlet],
2190 vertices: &mut [u32],
2191 triangles: &mut [u8],
2192 indices: &[u32],
2193 p: Positions<'_>,
2194 s: MeshletSettings,
2195 cone_weight: f32,
2196 workspace: &mut Workspace,
2197) -> Result<MeshletSizes, Error> {
2198 build_meshlets_flex_into_generic(
2199 descriptors,
2200 vertices,
2201 triangles,
2202 indices,
2203 p,
2204 s,
2205 s.max_triangles,
2206 cone_weight,
2207 0.,
2208 workspace,
2209 )
2210}
2211#[inline]
2216pub fn build_meshlets_flex_into_generic<I: crate::Index>(
2217 descriptors: &mut [Meshlet],
2218 vertices: &mut [I],
2219 triangles: &mut [u8],
2220 indices: &[I],
2221 p: Positions<'_>,
2222 s: MeshletSettings,
2223 min_triangles: usize,
2224 cone_weight: f32,
2225 split_factor: f32,
2226 workspace: &mut Workspace,
2227) -> Result<MeshletSizes, Error> {
2228 I::with_input(indices, workspace, |indices, workspace| {
2229 I::with_mut(vertices, workspace, |vertices, workspace| {
2230 build_meshlets_flex_into_u32(
2231 descriptors,
2232 vertices,
2233 triangles,
2234 indices,
2235 p,
2236 s,
2237 min_triangles,
2238 cone_weight,
2239 split_factor,
2240 workspace,
2241 )
2242 })
2243 })
2244}
2245
2246#[allow(clippy::too_many_arguments)]
2247fn build_meshlets_flex_into_u32(
2248 descriptors: &mut [Meshlet],
2249 vertices: &mut [u32],
2250 triangles: &mut [u8],
2251 indices: &[u32],
2252 p: Positions<'_>,
2253 s: MeshletSettings,
2254 min_triangles: usize,
2255 cone_weight: f32,
2256 split_factor: f32,
2257 workspace: &mut Workspace,
2258) -> Result<MeshletSizes, Error> {
2259 build_into(
2260 descriptors,
2261 vertices,
2262 triangles,
2263 indices,
2264 p.len(),
2265 Some(p),
2266 s,
2267 Builder::Flex {
2268 min: min_triangles,
2269 weight: cone_weight,
2270 split: split_factor,
2271 },
2272 workspace,
2273 )
2274}
2275#[inline]
2280pub fn build_meshlets_spatial_into_generic<I: crate::Index>(
2281 descriptors: &mut [Meshlet],
2282 vertices: &mut [I],
2283 triangles: &mut [u8],
2284 indices: &[I],
2285 p: Positions<'_>,
2286 s: MeshletSettings,
2287 min_triangles: usize,
2288 fill_weight: f32,
2289 workspace: &mut Workspace,
2290) -> Result<MeshletSizes, Error> {
2291 I::with_input(indices, workspace, |indices, workspace| {
2292 I::with_mut(vertices, workspace, |vertices, workspace| {
2293 build_meshlets_spatial_into_u32(
2294 descriptors,
2295 vertices,
2296 triangles,
2297 indices,
2298 p,
2299 s,
2300 min_triangles,
2301 fill_weight,
2302 workspace,
2303 )
2304 })
2305 })
2306}
2307
2308#[allow(clippy::too_many_arguments)]
2309fn build_meshlets_spatial_into_u32(
2310 descriptors: &mut [Meshlet],
2311 vertices: &mut [u32],
2312 triangles: &mut [u8],
2313 indices: &[u32],
2314 p: Positions<'_>,
2315 s: MeshletSettings,
2316 min_triangles: usize,
2317 fill_weight: f32,
2318 workspace: &mut Workspace,
2319) -> Result<MeshletSizes, Error> {
2320 build_into(
2321 descriptors,
2322 vertices,
2323 triangles,
2324 indices,
2325 p.len(),
2326 Some(p),
2327 s,
2328 Builder::Spatial {
2329 min: min_triangles,
2330 fill: fill_weight,
2331 parallel: false,
2332 },
2333 workspace,
2334 )
2335}
2336
2337#[inline]
2339pub fn build_meshlets_scan(
2340 indices: &[u32],
2341 vertex_count: usize,
2342 s: MeshletSettings,
2343 workspace: &mut Workspace,
2344) -> Result<Meshlets, Error> {
2345 build_meshlets_scan_generic::<u32>(indices, vertex_count, s, workspace).map(Into::into)
2346}
2347
2348#[inline]
2350pub fn build_meshlets(
2351 indices: &[u32],
2352 p: Positions<'_>,
2353 s: MeshletSettings,
2354 cone_weight: f32,
2355 workspace: &mut Workspace,
2356) -> Result<Meshlets, Error> {
2357 build_meshlets_generic::<u32>(indices, p, s, cone_weight, workspace).map(Into::into)
2358}
2359
2360#[inline]
2362pub fn build_meshlets_flex(
2363 indices: &[u32],
2364 p: Positions<'_>,
2365 s: MeshletSettings,
2366 min_triangles: usize,
2367 cone_weight: f32,
2368 split_factor: f32,
2369 workspace: &mut Workspace,
2370) -> Result<Meshlets, Error> {
2371 build_meshlets_flex_generic::<u32>(
2372 indices,
2373 p,
2374 s,
2375 min_triangles,
2376 cone_weight,
2377 split_factor,
2378 workspace,
2379 )
2380 .map(Into::into)
2381}
2382
2383#[inline]
2385pub fn build_meshlets_spatial(
2386 indices: &[u32],
2387 p: Positions<'_>,
2388 s: MeshletSettings,
2389 min_triangles: usize,
2390 fill_weight: f32,
2391 workspace: &mut Workspace,
2392) -> Result<Meshlets, Error> {
2393 build_meshlets_spatial_generic::<u32>(indices, p, s, min_triangles, fill_weight, workspace)
2394 .map(Into::into)
2395}
2396
2397#[inline]
2399pub fn build_meshlets_scan_into(
2400 descriptors: &mut [Meshlet],
2401 vertices: &mut [u32],
2402 triangles: &mut [u8],
2403 indices: &[u32],
2404 vertex_count: usize,
2405 s: MeshletSettings,
2406 workspace: &mut Workspace,
2407) -> Result<MeshletSizes, Error> {
2408 build_meshlets_scan_into_generic::<u32>(
2409 descriptors,
2410 vertices,
2411 triangles,
2412 indices,
2413 vertex_count,
2414 s,
2415 workspace,
2416 )
2417}
2418
2419#[inline]
2421pub fn build_meshlets_into(
2422 descriptors: &mut [Meshlet],
2423 vertices: &mut [u32],
2424 triangles: &mut [u8],
2425 indices: &[u32],
2426 p: Positions<'_>,
2427 s: MeshletSettings,
2428 cone_weight: f32,
2429 workspace: &mut Workspace,
2430) -> Result<MeshletSizes, Error> {
2431 build_meshlets_into_generic::<u32>(
2432 descriptors,
2433 vertices,
2434 triangles,
2435 indices,
2436 p,
2437 s,
2438 cone_weight,
2439 workspace,
2440 )
2441}
2442
2443#[inline]
2445pub fn build_meshlets_flex_into(
2446 descriptors: &mut [Meshlet],
2447 vertices: &mut [u32],
2448 triangles: &mut [u8],
2449 indices: &[u32],
2450 p: Positions<'_>,
2451 s: MeshletSettings,
2452 min_triangles: usize,
2453 cone_weight: f32,
2454 split_factor: f32,
2455 workspace: &mut Workspace,
2456) -> Result<MeshletSizes, Error> {
2457 build_meshlets_flex_into_generic::<u32>(
2458 descriptors,
2459 vertices,
2460 triangles,
2461 indices,
2462 p,
2463 s,
2464 min_triangles,
2465 cone_weight,
2466 split_factor,
2467 workspace,
2468 )
2469}
2470
2471#[inline]
2473pub fn build_meshlets_spatial_into(
2474 descriptors: &mut [Meshlet],
2475 vertices: &mut [u32],
2476 triangles: &mut [u8],
2477 indices: &[u32],
2478 p: Positions<'_>,
2479 s: MeshletSettings,
2480 min_triangles: usize,
2481 fill_weight: f32,
2482 workspace: &mut Workspace,
2483) -> Result<MeshletSizes, Error> {
2484 build_meshlets_spatial_into_generic::<u32>(
2485 descriptors,
2486 vertices,
2487 triangles,
2488 indices,
2489 p,
2490 s,
2491 min_triangles,
2492 fill_weight,
2493 workspace,
2494 )
2495}
2496
2497#[derive(Debug, Default, PartialEq, Eq)]
2500pub struct Meshlets {
2501 pub meshlets: Vec<Meshlet>,
2503 pub vertices: Vec<u32>,
2505 pub triangles: Vec<u8>,
2507}
2508impl From<MeshletsGeneric<u32>> for Meshlets {
2509 #[inline]
2510 fn from(value: MeshletsGeneric<u32>) -> Self {
2511 Self {
2512 meshlets: value.meshlets,
2513 vertices: value.vertices,
2514 triangles: value.triangles,
2515 }
2516 }
2517}
2518
2519impl From<Meshlets> for MeshletsGeneric<u32> {
2520 #[inline]
2521 fn from(value: Meshlets) -> Self {
2522 Self {
2523 meshlets: value.meshlets,
2524 vertices: value.vertices,
2525 triangles: value.triangles,
2526 }
2527 }
2528}
2529
2530#[cfg(test)]
2531mod packed_tests {
2532 use super::*;
2533 #[test]
2534 fn packed_children_check_actual_metadata_without_truncation() {
2535 let mut node = Node::default();
2536 node.set(3, 0x3fffffff).unwrap();
2537 assert_eq!(node.meta, u32::MAX);
2538 assert_eq!(node.axis(), 3);
2539 assert_eq!(node.children(), 0x3fffffff);
2540 assert_eq!(node.set(0, 0x40000000), Err(Error::SizeOverflow));
2541 assert_eq!(node.meta, u32::MAX);
2542 }
2543 #[test]
2544 fn small_divide_matches_integer_division() {
2545 let mut x = 0x9e37_79b9u32;
2546 for d in 1..=512usize {
2547 for edge in [
2548 0,
2549 1,
2550 d - 1,
2551 d,
2552 d + 1,
2553 (1 << 22) - 1,
2554 1 << 22,
2555 u32::MAX as usize,
2556 ] {
2557 assert_eq!(small_divide(edge, d), edge / d);
2558 }
2559 for _ in 0..512 {
2560 x = x.wrapping_mul(1_664_525).wrapping_add(1_013_904_223);
2561 assert_eq!(small_divide(x as usize, d), x as usize / d);
2562 let small = (x >> 10) as usize;
2563 assert_eq!(small_divide(small, d), small / d);
2564 }
2565 }
2566 assert_eq!(small_divide(usize::MAX, 7), usize::MAX / 7);
2567 }
2568}