1#![allow(clippy::too_many_arguments)]
2use crate::math::{root_at_least, sqrt8, RootEstimate, SqrtCache, LANES};
4use crate::processing::{cross, dot, finite, point, sub, Context};
5use crate::{Error, Positions, Workspace};
6use alloc::vec::Vec;
7
8#[derive(Clone, Copy, Debug, Default, PartialEq, Eq)]
10pub struct Meshlet {
11 pub vertex_offset: u32,
13 pub triangle_offset: u32,
15 pub vertex_count: u32,
17 pub triangle_count: u32,
19}
20#[derive(Debug, Default, PartialEq, Eq)]
22pub struct Meshlets {
23 pub meshlets: Vec<Meshlet>,
25 pub vertices: Vec<u32>,
27 pub triangles: Vec<u8>,
29}
30#[derive(Clone, Copy, Debug, PartialEq, Eq)]
32pub struct MeshletSettings {
33 pub max_vertices: usize,
35 pub max_triangles: usize,
37}
38impl Default for MeshletSettings {
39 fn default() -> Self {
40 Self {
41 max_vertices: 64,
42 max_triangles: 124,
43 }
44 }
45}
46#[derive(Clone, Copy, Debug, Default, PartialEq, Eq)]
48pub struct MeshletSizes {
49 pub meshlets: usize,
51 pub vertices: usize,
53 pub triangles: usize,
55}
56#[inline(always)]
62pub fn build_meshlets_bound(
63 index_count: usize,
64 max_vertices: usize,
65 max_triangles: usize,
66) -> Result<usize, Error> {
67 if !index_count.is_multiple_of(3) {
68 return Err(Error::InvalidTopology);
69 }
70 if !(3..=256).contains(&max_vertices) || !(1..=512).contains(&max_triangles) {
71 return Err(Error::InvalidParameter);
72 }
73 let v = max_vertices - 2;
74 let a = small_divide(
75 index_count.checked_add(v - 1).ok_or(Error::SizeOverflow)?,
76 v,
77 );
78 let b = small_divide(
79 (index_count / 3)
80 .checked_add(max_triangles - 1)
81 .ok_or(Error::SizeOverflow)?,
82 max_triangles,
83 );
84 Ok(a.max(b))
85}
86static RECIPROCALS: [u64; 513] = {
88 let mut table = [0u64; 513];
89 let mut d = 1;
90 while d < 513 {
91 table[d] = (1u64 << 32).div_ceil(d as u64);
92 d += 1;
93 }
94 table
95};
96#[inline(always)]
100fn small_divide(x: usize, d: usize) -> usize {
101 match RECIPROCALS.get(d) {
102 Some(&m) if d != 0 && x < 1 << 22 => ((x as u64 * m) >> 32) as usize,
103 _ => x / d,
104 }
105}
106pub(crate) struct Output<'a> {
107 pub(crate) descriptors: &'a mut [Meshlet],
108 pub(crate) vertices: &'a mut [u32],
109 pub(crate) triangles: &'a mut [u8],
110 pub(crate) current: Meshlet,
111 pub(crate) count: usize,
112}
113pub(crate) trait UsedVertices {
114 fn local(&self, vertex: usize) -> i16;
115 fn set_local(&mut self, vertex: usize, local: i16);
116}
117impl UsedVertices for [i16] {
118 #[inline(always)]
119 fn local(&self, vertex: usize) -> i16 {
120 self[vertex]
121 }
122 #[inline(always)]
123 fn set_local(&mut self, vertex: usize, local: i16) {
124 self[vertex] = local;
125 }
126}
127impl<T> UsedVertices for Vec<T>
128where
129 [T]: UsedVertices,
130{
131 #[inline(always)]
132 fn local(&self, vertex: usize) -> i16 {
133 self.as_slice().local(vertex)
134 }
135 #[inline(always)]
136 fn set_local(&mut self, vertex: usize, local: i16) {
137 self.as_mut_slice().set_local(vertex, local);
138 }
139}
140impl Output<'_> {
141 #[inline(always)]
142 pub(crate) fn append<U: UsedVertices + ?Sized>(
143 &mut self,
144 t: &[u32; 3],
145 used: &mut U,
146 s: MeshletSettings,
147 split: bool,
148 ctx: &mut Context<'_>,
149 ) -> Result<bool, Error> {
150 ctx.tick(1)?;
151 let mut m = self.current;
154 let [a, b, c] = t.map(|v| v as usize);
155 let mut local = [used.local(a), used.local(b), used.local(c)];
156 let extra = local.iter().filter(|&&v| v < 0).count();
159 let mut flush = false;
160 if m.vertex_count as usize + extra > s.max_vertices
161 || m.triangle_count as usize >= s.max_triangles
162 || split
163 {
164 self.descriptors[self.count] = m;
165 self.count += 1;
166 ctx.tick(m.vertex_count as usize)?;
167 for &v in &self.vertices[m.vertex_offset as usize..][..m.vertex_count as usize] {
168 used.set_local(v as usize, -1);
169 }
170 m.vertex_offset += m.vertex_count;
171 m.triangle_offset += m.triangle_count * 3;
172 m.vertex_count = 0;
173 m.triangle_count = 0;
174 local = [-1; 3];
175 flush = true;
176 }
177 let off = m.triangle_offset as usize + m.triangle_count as usize * 3;
178 let triangle = &mut self.triangles[off..off + 3];
179 for k in 0..3 {
180 if local[k] < 0 {
181 if k > 0 && t[k] == t[0] {
184 local[k] = local[0];
185 } else if k == 2 && t[k] == t[1] {
186 local[k] = local[1];
187 } else {
188 local[k] = m.vertex_count as i16;
189 used.set_local(t[k] as usize, local[k]);
190 self.vertices[m.vertex_offset as usize + m.vertex_count as usize] = t[k];
191 m.vertex_count += 1;
192 }
193 }
194 triangle[k] = local[k] as u8;
195 }
196 m.triangle_count += 1;
197 self.current = m;
198 Ok(flush)
199 }
200 fn finish(&mut self) -> MeshletSizes {
201 if self.current.triangle_count != 0 {
202 self.descriptors[self.count] = self.current;
203 self.count += 1;
204 }
205 MeshletSizes {
206 meshlets: self.count,
207 vertices: (self.current.vertex_offset + self.current.vertex_count) as usize,
208 triangles: (self.current.triangle_offset + self.current.triangle_count * 3) as usize,
209 }
210 }
211}
212fn validate(s: MeshletSettings, min: usize, weight: f32, split: f32) -> Result<(), Error> {
213 build_meshlets_bound(0, s.max_vertices, s.max_triangles)?;
214 if min == 0
215 || min > s.max_triangles
216 || !weight.is_finite()
217 || !(0.0..=1.0).contains(&weight)
218 || !split.is_finite()
219 || split < 0.
220 {
221 return Err(Error::InvalidParameter);
222 }
223 Ok(())
224}
225#[derive(Clone, Copy, Default)]
226struct Cone {
227 p: [f32; 3],
228 n: [f32; 3],
229}
230#[inline(always)]
232fn cone_position(acc: Cone, count: u32) -> [f32; 3] {
233 let scale = if count == 0 { 0. } else { 1. / count as f32 };
234 acc.p.map(|v| v * scale)
235}
236struct MeshletNormal {
238 low: [f32; 3],
239 high: [f32; 3],
240 exact: Option<[f32; 3]>,
241}
242impl MeshletNormal {
243 fn exact(acc: [f32; 3], roots: &mut SqrtCache) -> Self {
244 let l = dot(acc, acc);
245 let scale = if l == 0. { 0. } else { 1. / roots.sqrt(l) };
246 let n = acc.map(|v| v * scale);
247 Self {
248 low: n,
249 high: n,
250 exact: Some(n),
251 }
252 }
253 #[inline(always)]
257 fn bounds(acc: [f32; 3], roots: &mut SqrtCache) -> Self {
258 let l = dot(acc, acc);
259 let Some(root) = RootEstimate::new(l) else {
260 return Self::exact(acc, roots);
261 };
262 let (scale_low, scale_high) = root.inverse_table();
263 let mut low = [0f32; 3];
264 let mut high = [0f32; 3];
265 for k in 0..3 {
266 let (a, b) = (acc[k] * scale_low, acc[k] * scale_high);
267 (low[k], high[k]) = if acc[k] >= 0. { (a, b) } else { (b, a) };
268 }
269 Self {
270 low,
271 high,
272 exact: None,
273 }
274 }
275}
276#[derive(Clone, Copy)]
279struct VertexState {
280 offset: u32,
281 live: u32,
282 local: i16,
283}
284impl Default for VertexState {
285 fn default() -> Self {
286 Self {
287 offset: 0,
288 live: 0,
289 local: -1,
290 }
291 }
292}
293impl UsedVertices for [VertexState] {
294 #[inline(always)]
295 fn local(&self, vertex: usize) -> i16 {
296 self[vertex].local
297 }
298 #[inline(always)]
299 fn set_local(&mut self, vertex: usize, local: i16) {
300 self[vertex].local = local;
301 }
302}
303struct Adjacency {
304 vertices: Vec<VertexState>,
305 data: Vec<u32>,
306}
307fn adjacency(indices: &[u32], n: usize, ctx: &mut Context<'_>) -> Result<Adjacency, Error> {
308 let mut vertices = ctx.alloc::<VertexState>(n)?;
309 let mut data = ctx.alloc::<u32>(indices.len())?;
310 ctx.tick(n + indices.len() * 2)?;
311 for &v in indices {
312 vertices[v as usize].live += 1;
313 }
314 let mut offset = 0;
315 for vertex in vertices.iter_mut() {
316 vertex.offset = offset;
317 offset += vertex.live;
318 }
319 for (i, t) in indices.as_chunks::<3>().0.iter().enumerate() {
320 for &v in t {
321 let o = &mut vertices[v as usize].offset;
322 data[*o as usize] = i as u32;
323 *o += 1;
324 }
325 }
326 for vertex in vertices.iter_mut() {
327 vertex.offset -= vertex.live;
328 }
329 Ok(Adjacency { vertices, data })
330}
331#[derive(Clone, Copy, Default)]
333struct Node {
334 data: u32,
335 meta: u32,
336}
337impl Node {
338 fn axis(self) -> usize {
339 (self.meta & 3) as usize
340 }
341 fn children(self) -> usize {
342 (self.meta >> 2) as usize
343 }
344 fn set(&mut self, axis: usize, children: usize) -> Result<(), Error> {
345 if children > 0x3fffffff {
346 return Err(Error::SizeOverflow);
347 }
348 self.meta = (children as u32) << 2 | axis as u32;
349 Ok(())
350 }
351}
352#[cfg(test)]
353mod packed_tests {
354 use super::*;
355 #[test]
356 fn packed_children_check_actual_metadata_without_truncation() {
357 let mut node = Node::default();
358 node.set(3, 0x3fffffff).unwrap();
359 assert_eq!(node.meta, u32::MAX);
360 assert_eq!(node.axis(), 3);
361 assert_eq!(node.children(), 0x3fffffff);
362 assert_eq!(node.set(0, 0x40000000), Err(Error::SizeOverflow));
363 assert_eq!(node.meta, u32::MAX);
364 }
365 #[test]
366 fn small_divide_matches_integer_division() {
367 let mut x = 0x9e37_79b9u32;
368 for d in 1..=512usize {
369 for edge in [
370 0,
371 1,
372 d - 1,
373 d,
374 d + 1,
375 (1 << 22) - 1,
376 1 << 22,
377 u32::MAX as usize,
378 ] {
379 assert_eq!(small_divide(edge, d), edge / d);
380 }
381 for _ in 0..512 {
382 x = x.wrapping_mul(1_664_525).wrapping_add(1_013_904_223);
383 assert_eq!(small_divide(x as usize, d), x as usize / d);
384 let small = (x >> 10) as usize;
385 assert_eq!(small_divide(small, d), small / d);
386 }
387 }
388 assert_eq!(small_divide(usize::MAX, 7), usize::MAX / 7);
389 }
390}
391#[derive(Clone, Copy, Default)]
393struct KdSplit {
394 mean: [f32; 3],
395 axis: usize,
396}
397impl KdSplit {
398 #[inline(always)]
399 fn finish(mean: [f32; 3], vars: [f32; 3]) -> Self {
400 let axis = if vars[0] >= vars[1] && vars[0] >= vars[2] {
401 0
402 } else if vars[1] >= vars[2] {
403 1
404 } else {
405 2
406 };
407 Self { mean, axis }
408 }
409}
410#[inline(always)]
411fn welford(p: [f32; 3], mean: &mut [f32; 3], vars: &mut [f32; 3], runs: f32) {
412 for k in 0..3 {
413 let delta = p[k] - mean[k];
414 mean[k] += delta * runs;
415 vars[k] += delta * (p[k] - mean[k]);
416 }
417}
418fn kd_stats(order: &[u32], cones: &[Cone]) -> KdSplit {
419 let (mut mean, mut vars) = ([0.; 3], [0.; 3]);
420 let (mut runc, mut runs) = (1f32, 1f32);
421 for &v in order {
422 welford(cones[v as usize].p, &mut mean, &mut vars, runs);
423 runc += 1.;
424 runs = 1. / runc;
425 }
426 KdSplit::finish(mean, vars)
427}
428fn kd_stats2(a: &[u32], b: &[u32], cones: &[Cone]) -> (KdSplit, KdSplit) {
431 let (mut am, mut av, mut bm, mut bv) = ([0.; 3], [0.; 3], [0.; 3], [0.; 3]);
432 let (mut runc, mut runs) = (1f32, 1f32);
433 let common = a.len().min(b.len());
434 for (&x, &y) in a[..common].iter().zip(&b[..common]) {
435 welford(cones[x as usize].p, &mut am, &mut av, runs);
436 welford(cones[y as usize].p, &mut bm, &mut bv, runs);
437 runc += 1.;
438 runs = 1. / runc;
439 }
440 let (rest, mean, vars) = if a.len() > common {
441 (&a[common..], &mut am, &mut av)
442 } else {
443 (&b[common..], &mut bm, &mut bv)
444 };
445 for &v in rest {
446 welford(cones[v as usize].p, mean, vars, runs);
447 runc += 1.;
448 runs = 1. / runc;
449 }
450 (KdSplit::finish(am, av), KdSplit::finish(bm, bv))
451}
452fn kd_build(
457 nodes: &mut [Node],
458 offset: usize,
459 order: &mut [u32],
460 cones: &[Cone],
461 depth: usize,
462 split: Option<KdSplit>,
463 ctx: &mut Context<'_>,
464) -> Result<usize, Error> {
465 let n = order.len();
466 let mut middle = 0;
467 let mut stats = KdSplit::default();
468 if n > 8 {
469 ctx.tick(n * 2)?;
470 stats = split.unwrap_or_else(|| kd_stats(order, cones));
471 let (mean, axis) = (stats.mean, stats.axis);
472 finite(mean[axis])?;
473 for i in 0..n {
474 let v = cones[order[i] as usize].p[axis];
475 order.swap(middle, i);
476 middle += usize::from(v < mean[axis]);
477 }
478 }
479 if n <= 8 || middle <= 4 || middle >= n - 4 || depth >= 50 {
480 if n > 0x3fffffff {
481 return Err(Error::SizeOverflow);
482 }
483 ctx.tick(n)?;
484 for (i, &v) in order.iter().enumerate() {
485 nodes[offset + i] = Node {
486 data: v,
487 meta: 3 | ((if i == 0 { n as u32 } else { 0x3fffffff }) << 2),
488 };
489 }
490 return Ok(offset + n);
491 }
492 nodes[offset].data = stats.mean[stats.axis].to_bits();
493 let (left, right) = order.split_at_mut(middle);
494 let (left_split, right_split) = match (left.len() > 8, right.len() > 8) {
495 (true, true) => {
496 let (l, r) = kd_stats2(left, right, cones);
497 (Some(l), Some(r))
498 }
499 (true, false) => (Some(kd_stats(left, cones)), None),
500 (false, true) => (None, Some(kd_stats(right, cones))),
501 (false, false) => (None, None),
502 };
503 let next = kd_build(nodes, offset + 1, left, cones, depth + 1, left_split, ctx)?;
504 nodes[offset].set(stats.axis, next - offset - 1)?;
505 kd_build(nodes, next, right, cones, depth + 1, right_split, ctx)
506}
507fn nearest<const CHECK: bool>(
508 nodes: &mut [Node],
509 root: usize,
510 cones: &[Cone],
511 emitted: &[u8],
512 p: [f32; 3],
513 result: &mut u32,
514 limit: &mut f32,
515 roots: &mut SqrtCache,
516 ctx: &mut Context<'_>,
517) -> Result<(), Error> {
518 ctx.tick(1)?;
519 let node = nodes[root];
520 if node.children() == 0 {
521 return Ok(());
522 }
523 if node.axis() == 3 && !CHECK && ctx.work.covers(node.children())? {
524 let count = node.children();
526 let mut inactive = true;
527 for item in &nodes[root..root + count] {
528 let v = item.data as usize;
529 if emitted[v] == EMITTED {
530 continue;
531 }
532 inactive = false;
533 let d = sub(cones[v].p, p);
534 let square = dot(d, d);
535 if lower_distance(d) >= *limit || root_at_least(square, *limit) {
536 continue;
537 }
538 let distance = roots.sqrt(square);
539 if distance < *limit {
540 *result = v as u32;
541 *limit = distance;
542 }
543 }
544 ctx.tick(count)?;
545 if inactive {
546 nodes[root].set(3, 0)?;
547 }
548 } else if node.axis() == 3 {
549 let mut inactive = true;
550 ctx.scan(0..node.children(), |_ctx, i| {
551 let v = nodes[root + i].data as usize;
552 if emitted[v] == EMITTED {
553 return Ok(());
554 }
555 inactive = false;
556 let d = sub(cones[v].p, p);
557 if !CHECK && (lower_distance(d) >= *limit || root_at_least(dot(d, d), *limit)) {
558 return Ok(());
559 }
560 let distance = roots.sqrt(number::<CHECK>(dot(d, d))?);
561 if distance < *limit {
562 *result = v as u32;
563 *limit = distance;
564 }
565 Ok(())
566 })?;
567 if inactive {
568 nodes[root].set(3, 0)?;
569 }
570 } else {
571 let delta = p[node.axis()] - f32::from_bits(node.data);
572 let first = if delta <= 0. { 0 } else { node.children() };
573 let second = first ^ node.children();
574 if nodes[root + 1 + first].children() | nodes[root + 1 + second].children() == 0 {
575 nodes[root].set(node.axis(), 0)?;
576 }
577 nearest::<CHECK>(
578 nodes,
579 root + 1 + first,
580 cones,
581 emitted,
582 p,
583 result,
584 limit,
585 roots,
586 ctx,
587 )?;
588 if delta.abs() <= *limit {
589 nearest::<CHECK>(
590 nodes,
591 root + 1 + second,
592 cones,
593 emitted,
594 p,
595 result,
596 limit,
597 roots,
598 ctx,
599 )?;
600 }
601 }
602 Ok(())
603}
604#[inline(always)]
607fn lower_distance(d: [f32; 3]) -> f32 {
608 let (x, y, z) = (d[0].abs(), d[1].abs(), d[2].abs());
610 let m = if x > y { x } else { y };
611 let m = if m > z { m } else { z };
612 if m >= 1.0e-18 {
614 m
615 } else {
616 0.0
617 }
618}
619#[inline(always)]
620fn number<const CHECK: bool>(value: f32) -> Result<f32, Error> {
621 if CHECK {
622 finite(value)
623 } else {
624 Ok(value)
625 }
626}
627#[inline(always)]
628fn distance<const CHECK: bool>(
629 a: [f32; 3],
630 b: [f32; 3],
631 roots: &mut SqrtCache,
632) -> Result<f32, Error> {
633 let d = sub(a, b);
634 Ok(roots.sqrt(number::<CHECK>(dot(d, d))?))
635}
636struct Selection {
640 triangle: u32,
641 priority: i32,
642 lo: f32,
643 hi: f32,
644 known: bool,
645 square: f32,
646}
647impl Selection {
648 fn new() -> Self {
649 Self {
650 triangle: u32::MAX,
651 priority: 5,
652 lo: f32::MAX,
653 hi: f32::MAX,
654 known: true,
655 square: 0.,
656 }
657 }
658}
659struct CandidateInput<'a> {
660 triangles: &'a [[u32; 3]],
661 vertices: &'a [VertexState],
662 cones: &'a [Cone],
663 meshlet: Cone,
664 weight: f32,
665 radius: f32,
666 inverse_low: f32,
669 inverse_high: f32,
670 bounded: bool,
671 accumulated: [f32; 3],
674 normal_low: [f32; 3],
675 normal_high: [f32; 3],
676}
677struct Search<'r> {
681 roots: &'r mut SqrtCache,
682 normal: Option<[f32; 3]>,
683 listed: bool,
686 data: &'r [u32],
687}
688impl CandidateInput<'_> {
689 #[inline(always)]
690 fn one<const CHECK: bool>(
691 &self,
692 tri: u32,
693 local: u16,
694 selected: &mut Selection,
695 search: &mut Search<'_>,
696 ) -> Result<(), Error> {
697 let [a, b, c] = self.triangles[tri as usize].map(|v| v as usize);
698 let (av, bv, cv) = (self.vertices[a], self.vertices[b], self.vertices[c]);
699 if (av.local as u16).min(bv.local as u16).min(cv.local as u16) < local {
704 return Ok(());
705 }
706 self.evaluate::<CHECK>(tri, [av, bv, cv], selected, search)
707 }
708 #[inline(always)]
709 fn evaluate<const CHECK: bool>(
710 &self,
711 tri: u32,
712 [av, bv, cv]: [VertexState; 3],
713 selected: &mut Selection,
714 search: &mut Search<'_>,
715 ) -> Result<(), Error> {
716 let extra = i32::from(av.local < 0) + i32::from(bv.local < 0) + i32::from(cv.local < 0);
717 let (al, bl, cl) = (av.live, bv.live, cv.live);
718 let priority = if extra == 0 {
719 0
720 } else if al == 1 || bl == 1 || cl == 1 {
721 1
722 } else if i32::from(al == 2) + i32::from(bl == 2) + i32::from(cl == 2) >= 2 {
723 1 + extra
724 } else {
725 2 + extra
726 };
727 if priority > selected.priority {
728 return Ok(());
729 }
730 let cone = self.cones[tri as usize];
731 let dp = sub(cone.p, self.meshlet.p);
732 let square = dot(dp, dp);
733 let square = if CHECK { finite(square)? } else { square };
734 if !CHECK && self.bounded {
735 self.bracketed(tri, priority, cone.n, square, selected, search);
736 return Ok(());
737 }
738 let clamped = self.clamped(dot(cone.n, self.meshlet.n));
739 let distance = search.roots.sqrt(square);
740 let score = self.score(distance, clamped);
741 if priority < selected.priority || score < selected.hi {
743 *selected = Selection {
744 triangle: tri,
745 priority,
746 lo: score,
747 hi: score,
748 known: true,
749 square,
750 };
751 }
752 Ok(())
753 }
754 #[inline(always)]
755 fn clamped(&self, spread: f32) -> f32 {
756 let cc = 1. - spread * self.weight;
757 if cc < 1e-3 {
758 1e-3
759 } else {
760 cc
761 }
762 }
763 #[inline(always)]
764 fn score(&self, distance: f32, clamped: f32) -> f32 {
765 (1. + distance / self.radius * (1. - self.weight)) * clamped
766 }
767 #[inline(always)]
779 fn score_low(&self, distance: f32, clamped: f32) -> f32 {
780 (1. + distance * self.inverse_low * (1. - self.weight)) * clamped
781 }
782 #[inline(always)]
783 fn score_high(&self, distance: f32, clamped: f32) -> f32 {
784 (1. + distance * self.inverse_high * (1. - self.weight)) * clamped
785 }
786 #[inline(always)]
788 fn clamped_bounds(&self, n: [f32; 3], low: bool) -> f32 {
789 if self.weight == 0. {
792 return 1.;
793 }
794 let (lo, hi) = (self.normal_low, self.normal_high);
797 let term = |k: usize| {
798 let (a, b) = (n[k] * lo[k], n[k] * hi[k]);
799 if (a > b) == low {
800 a
801 } else {
802 b
803 }
804 };
805 self.clamped(term(0) + term(1) + term(2))
807 }
808 #[cold]
810 #[inline(never)]
811 fn exact_normal(&self, search: &mut Search<'_>) -> [f32; 3] {
812 if self.weight == 0. {
813 return [0.; 3];
814 }
815 if let Some(n) = search.normal {
816 return n;
817 }
818 let l = dot(self.accumulated, self.accumulated);
819 let scale = if l == 0. {
820 0.
821 } else {
822 1. / search.roots.sqrt(l)
823 };
824 let n = self.accumulated.map(|v| v * scale);
825 search.normal = Some(n);
826 n
827 }
828 #[inline(always)]
829 fn bracketed(
830 &self,
831 tri: u32,
832 priority: i32,
833 normal: [f32; 3],
834 square: f32,
835 selected: &mut Selection,
836 search: &mut Search<'_>,
837 ) {
838 let clamped_low = self.clamped_bounds(normal, true);
839 let (lo, hi) = match RootEstimate::new(square) {
840 Some(root) => {
841 let low = self.score_low(root.table().0, clamped_low);
844 if priority == selected.priority
845 && (low > selected.hi || (low == selected.hi && !search.listed))
846 {
847 return;
848 }
849 let (dlo, dhi) = root.bounds();
850 (
851 self.score_low(dlo, clamped_low),
852 self.score_high(dhi, self.clamped_bounds(normal, false)),
853 )
854 }
855 None => {
856 let d = search.roots.sqrt(square);
857 (
858 self.score_low(d, clamped_low),
859 self.score_high(d, self.clamped_bounds(normal, false)),
860 )
861 }
862 };
863 if priority == selected.priority {
864 if lo > selected.hi || (lo == selected.hi && !search.listed) {
866 return;
867 }
868 if hi >= selected.lo {
869 self.resolve(tri, priority, square, selected, search);
870 return;
871 }
872 }
873 *selected = Selection {
874 triangle: tri,
875 priority,
876 lo,
877 hi,
878 known: false,
879 square,
880 };
881 }
882 fn visit(&self, tri: u32, data: &[u32]) -> (u16, usize) {
885 let mut first = (u16::MAX, 0usize);
886 for &v in &self.triangles[tri as usize] {
887 let state = self.vertices[v as usize];
888 if (state.local as u16) < first.0 {
889 first = (state.local as u16, v as usize);
890 }
891 }
892 let state = self.vertices[first.1];
893 let list = &data[state.offset as usize..][..state.live as usize];
894 (
895 first.0,
896 list.iter().position(|&t| t == tri).unwrap_or(list.len()),
897 )
898 }
899 #[cold]
901 #[inline(never)]
902 fn resolve(
903 &self,
904 tri: u32,
905 priority: i32,
906 square: f32,
907 selected: &mut Selection,
908 search: &mut Search<'_>,
909 ) {
910 let n = self.exact_normal(search);
911 let mut exact = |tri: u32, square: f32| {
912 let clamped = self.clamped(dot(self.cones[tri as usize].n, n));
913 self.score(search.roots.sqrt(square), clamped)
914 };
915 if !selected.known {
916 let score = exact(selected.triangle, selected.square);
917 selected.lo = score;
918 selected.hi = score;
919 selected.known = true;
920 }
921 let score = exact(tri, square);
922 if score < selected.hi
923 || (search.listed
924 && score == selected.hi
925 && self.visit(tri, search.data) < self.visit(selected.triangle, search.data))
926 {
927 *selected = Selection {
928 triangle: tri,
929 priority,
930 lo: score,
931 hi: score,
932 known: true,
933 square,
934 };
935 }
936 }
937 #[inline(always)]
948 fn neighbors<const CHECK: bool>(
949 &self,
950 active: &mut Active,
951 data: &[u32],
952 roots: &mut SqrtCache,
953 normal: Option<[f32; 3]>,
954 listed: Option<&mut Candidates>,
955 emitted: &[u8],
956 ctx: &mut Context<'_>,
957 ) -> Result<u32, Error> {
958 if let Some(listed) = listed.filter(|listed| !CHECK && !listed.overflow) {
959 let mut total = 0usize;
960 let mut kept = 0;
961 for k in 0..active.len {
962 let v = active.list[k];
963 let live = self.vertices[v as usize].live as usize;
964 if live != 0 {
965 active.list[kept] = v;
966 kept += 1;
967 total += live;
968 }
969 }
970 active.len = kept;
971 if ctx.work.covers(total)? {
972 let mut search = Search {
973 roots,
974 normal,
975 listed: true,
976 data,
977 };
978 let mut selected = Selection::new();
979 let mut i = 0;
980 while i < listed.len {
981 let tri = listed.list[i];
982 if emitted[tri as usize] == EMITTED {
983 listed.len -= 1;
984 listed.list[i] = listed.list[listed.len];
985 continue;
986 }
987 let [a, b, c] = self.triangles[tri as usize].map(|v| v as usize);
988 let states = [self.vertices[a], self.vertices[b], self.vertices[c]];
989 self.evaluate::<CHECK>(tri, states, &mut selected, &mut search)?;
990 i += 1;
991 }
992 ctx.tick(total)?;
993 return Ok(selected.triangle);
994 }
995 }
996 let mut search = Search {
997 roots,
998 normal,
999 listed: false,
1000 data,
1001 };
1002 let mut selected = Selection::new();
1003 let mut visited = 0usize;
1004 let mut kept = 0;
1005 for k in 0..active.len {
1006 let v = active.list[k];
1007 let state = self.vertices[v as usize];
1008 let live = state.live as usize;
1009 if live == 0 {
1012 continue;
1013 }
1014 active.list[kept] = v;
1015 kept += 1;
1016 let local = state.local as u16;
1017 if !ctx.work.covers(visited + live)? {
1018 ctx.tick(visited)?;
1019 for &v in &active.list[k..active.len] {
1020 let state = self.vertices[v as usize];
1021 let off = state.offset as usize;
1022 for &tri in &data[off..off + state.live as usize] {
1023 ctx.tick(1)?;
1024 self.one::<CHECK>(tri, state.local as u16, &mut selected, &mut search)?;
1025 }
1026 }
1027 return Ok(selected.triangle);
1028 }
1029 let off = state.offset as usize;
1030 for &tri in &data[off..off + live] {
1031 visited += 1;
1032 if let Err(error) = self.one::<CHECK>(tri, local, &mut selected, &mut search) {
1033 ctx.tick(visited)?;
1034 return Err(error);
1035 }
1036 }
1037 }
1038 active.len = kept;
1039 ctx.tick(visited)?;
1040 Ok(selected.triangle)
1041 }
1042}
1043const EMITTED: u8 = 1;
1045const LISTED: u8 = 2;
1046struct Candidates {
1049 list: [u32; 1024],
1050 len: usize,
1051 overflow: bool,
1052}
1053impl Candidates {
1054 fn new() -> Self {
1055 Self {
1056 list: [0; 1024],
1057 len: 0,
1058 overflow: false,
1059 }
1060 }
1061 fn clear(&mut self, emitted: &mut [u8]) {
1062 for &t in &self.list[..self.len] {
1063 if emitted[t as usize] == LISTED {
1064 emitted[t as usize] = 0;
1065 }
1066 }
1067 self.len = 0;
1068 self.overflow = false;
1069 }
1070 fn add(&mut self, live: &[u32], emitted: &mut [u8]) {
1071 for &t in live {
1072 if emitted[t as usize] == 0 {
1073 if self.len == self.list.len() {
1074 self.overflow = true;
1075 return;
1076 }
1077 emitted[t as usize] = LISTED;
1078 self.list[self.len] = t;
1079 self.len += 1;
1080 }
1081 }
1082 }
1083}
1084struct Active {
1088 list: [u32; 256],
1089 len: usize,
1090 offset: u32,
1091 synced: usize,
1092}
1093impl Active {
1094 fn new() -> Self {
1095 Self {
1096 list: [0; 256],
1097 len: 0,
1098 offset: 0,
1099 synced: 0,
1100 }
1101 }
1102 #[inline(always)]
1103 fn sync(
1104 &mut self,
1105 out: &Output<'_>,
1106 adj: &Adjacency,
1107 listed: Option<(&mut Candidates, &mut [u8])>,
1108 ) {
1109 let count = out.current.vertex_count as usize;
1110 let reset = out.current.vertex_offset != self.offset || count < self.synced;
1111 if reset {
1112 self.offset = out.current.vertex_offset;
1113 self.len = 0;
1114 self.synced = 0;
1115 }
1116 let added = &out.vertices[self.offset as usize..][self.synced..count];
1117 if let Some((candidates, emitted)) = listed {
1118 if reset {
1119 candidates.clear(emitted);
1120 }
1121 for &v in added {
1122 let state = adj.vertices[v as usize];
1123 if !candidates.overflow {
1124 let off = state.offset as usize;
1125 candidates.add(&adj.data[off..off + state.live as usize], emitted);
1126 }
1127 }
1128 }
1129 for &v in added {
1130 self.list[self.len] = v;
1131 self.len += 1;
1132 }
1133 self.synced = count;
1134 }
1135}
1136fn fill_cones<const CHECK: bool>(
1139 triangles: &[[u32; 3]],
1140 cones: &mut [Cone],
1141 read: impl Fn(u32) -> [f32; 3],
1142) -> Result<f32, Error> {
1143 let mut mesh_area = 0.;
1144 for (group, out_cones) in triangles.chunks(LANES).zip(cones.chunks_mut(LANES)) {
1145 let mut normals = [[0f32; 3]; LANES];
1146 let mut squares = [1f32; LANES];
1147 for (k, (t, cone)) in group.iter().zip(out_cones.iter_mut()).enumerate() {
1148 let a = read(t[0]);
1149 let b = read(t[1]);
1150 let c = read(t[2]);
1151 let normal = cross(sub(b, a), sub(c, a));
1152 squares[k] = number::<CHECK>(dot(normal, normal))?;
1153 normals[k] = normal;
1154 for j in 0..3 {
1155 cone.p[j] = number::<CHECK>((a[j] + b[j] + c[j]) / 3.)?;
1156 }
1157 }
1158 let areas = sqrt8(squares);
1159 for (k, cone) in out_cones.iter_mut().enumerate() {
1160 let area = areas[k];
1161 let inv = if area == 0. { 0. } else { 1. / area };
1162 for (n, &v) in cone.n.iter_mut().zip(&normals[k]) {
1163 *n = number::<CHECK>(v * inv)?;
1164 }
1165 mesh_area = number::<CHECK>(mesh_area + area)?;
1166 }
1167 }
1168 Ok(mesh_area)
1169}
1170fn flex<const CHECK: bool, const ZERO_WEIGHT: bool>(
1171 out: &mut Output<'_>,
1172 indices: &[u32],
1173 p: Positions<'_>,
1174 s: MeshletSettings,
1175 min: usize,
1176 weight: f32,
1177 split_factor: f32,
1178 ctx: &mut Context<'_>,
1179) -> Result<(), Error> {
1180 let weight = if ZERO_WEIGHT { 0. } else { weight };
1184 if indices.is_empty() {
1185 return Ok(());
1186 }
1187 let n = indices.len() / 3;
1188 let node_count = n.checked_mul(2).ok_or(Error::SizeOverflow)?;
1189 let mut roots = SqrtCache::new();
1191 let mut adj = adjacency(indices, p.len(), ctx)?;
1192 let mut emitted = ctx.alloc::<u8>(n)?;
1193 let mut cones = ctx.alloc::<Cone>(n)?;
1194 ctx.tick(n)?;
1195 let triangles = indices.as_chunks::<3>().0;
1196 let mesh_area = if let Some(values) = p.packed_values() {
1197 fill_cones::<CHECK>(triangles, &mut cones, |i| values[i as usize])?
1198 } else {
1199 fill_cones::<CHECK>(triangles, &mut cones, |i| point(p, i))?
1200 };
1201 let radius = roots.sqrt(number::<CHECK>(
1202 mesh_area / n as f32 * 0.5 * s.max_triangles as f32,
1203 )?) * 0.5;
1204 let mut order = ctx.alloc(n)?;
1205 for (i, v) in order.iter_mut().enumerate() {
1206 *v = i as u32;
1207 }
1208 let mut nodes = ctx.alloc(node_count)?;
1209 kd_build(&mut nodes, 0, &mut order, &cones, 0, None, ctx)?;
1210 ctx.tick(n.checked_mul(2).ok_or(Error::SizeOverflow)?)?;
1211 let mut corner = [f32::MAX; 3];
1212 for c in &cones {
1213 for (k, v) in corner.iter_mut().enumerate() {
1214 if *v > c.p[k] {
1215 *v = c.p[k];
1216 }
1217 }
1218 }
1219 let mut initial = u32::MAX;
1220 let mut score = f32::MAX;
1221 for (i, c) in cones.iter().enumerate() {
1222 if !CHECK && initial != u32::MAX && {
1223 let d = sub(c.p, corner);
1224 lower_distance(d) >= score || root_at_least(dot(d, d), score)
1225 } {
1226 continue;
1227 }
1228 let d = distance::<CHECK>(c.p, corner, &mut roots)?;
1229 if initial == u32::MAX || d < score {
1230 initial = i as u32;
1231 score = d;
1232 }
1233 }
1234 let mut seeds = [0u32; 256];
1235 let mut seed_count = 0;
1236 let mut acc = Cone::default();
1237 let mut active = Active::new();
1238 let inverse = 1. / radius;
1241 let inverse_low = inverse * 0.999_999_5;
1242 let inverse_high = inverse * 1.000_000_5;
1243 let bounded = !CHECK
1244 && radius.is_normal()
1245 && radius > 0.
1246 && inverse_low.is_normal()
1247 && inverse_high.is_finite();
1248 let mut candidates = (bounded && n >= 256).then(Candidates::new);
1252 loop {
1253 ctx.tick(1)?;
1254 let mc_position = cone_position(acc, out.current.triangle_count);
1255 let mut best;
1256 if out.count == 0 && out.current.triangle_count == 0 {
1257 best = initial;
1258 } else {
1259 let normal = if bounded && weight == 0. {
1263 MeshletNormal {
1264 exact: Some([0.; 3]),
1265 low: [0.; 3],
1266 high: [0.; 3],
1267 }
1268 } else if bounded {
1269 MeshletNormal::bounds(acc.n, &mut roots)
1270 } else {
1271 MeshletNormal::exact(acc.n, &mut roots)
1272 };
1273 let input = CandidateInput {
1274 triangles: indices.as_chunks::<3>().0,
1275 vertices: &adj.vertices,
1276 cones: &cones,
1277 meshlet: Cone {
1278 p: mc_position,
1279 n: normal.exact.unwrap_or_default(),
1280 },
1281 weight,
1282 radius,
1283 inverse_low,
1284 inverse_high,
1285 bounded,
1286 accumulated: acc.n,
1287 normal_low: normal.low,
1288 normal_high: normal.high,
1289 };
1290 active.sync(
1291 out,
1292 &adj,
1293 candidates
1294 .as_mut()
1295 .map(|candidates| (candidates, emitted.as_mut_slice())),
1296 );
1297 best = input.neighbors::<CHECK>(
1298 &mut active,
1299 &adj.data,
1300 &mut roots,
1301 normal.exact,
1302 candidates.as_mut(),
1303 &emitted,
1304 ctx,
1305 )?;
1306 }
1307 let mut split = false;
1308 if best == u32::MAX {
1309 let mut d = f32::MAX;
1310 nearest::<CHECK>(
1311 &mut nodes,
1312 0,
1313 &cones,
1314 &emitted,
1315 mc_position,
1316 &mut best,
1317 &mut d,
1318 &mut roots,
1319 ctx,
1320 )?;
1321 split = out.current.triangle_count as usize >= min
1322 && split_factor > 0.
1323 && d > radius * split_factor;
1324 }
1325 if best == u32::MAX {
1326 break;
1327 }
1328 let extra = indices[best as usize * 3..][..3]
1329 .iter()
1330 .filter(|&&v| adj.vertices[v as usize].local < 0)
1331 .count();
1332 if split
1333 || out.current.vertex_count as usize + extra > s.max_vertices
1334 || out.current.triangle_count as usize >= s.max_triangles
1335 {
1336 let mut keep = 0;
1337 for i in 0..seed_count {
1338 if emitted[seeds[i] as usize] != EMITTED {
1339 seeds[keep] = seeds[i];
1340 keep += 1;
1341 }
1342 }
1343 seed_count = keep.min(252);
1344 let mut candidates = [u32::MAX; 4];
1345 let mut lives = [u32::MAX; 4];
1346 let mut scores = [f32::MAX; 4];
1347 for &v in &out.vertices[out.current.vertex_offset as usize..]
1348 [..out.current.vertex_count as usize]
1349 {
1350 let off = adj.vertices[v as usize].offset as usize;
1351 let mut neighbor = u32::MAX;
1352 let mut live = u32::MAX;
1353 ctx.scan(
1354 adj.data[off..off + adj.vertices[v as usize].live as usize]
1355 .iter()
1356 .copied(),
1357 |_ctx, tri| {
1358 let t = &indices[tri as usize * 3..][..3];
1359 let l = adj.vertices[t[0] as usize].live
1360 + adj.vertices[t[1] as usize].live
1361 + adj.vertices[t[2] as usize].live;
1362 if l < live {
1363 neighbor = tri;
1364 live = l;
1365 }
1366 Ok(())
1367 },
1368 )?;
1369 if neighbor == u32::MAX {
1370 continue;
1371 }
1372 let d = distance::<CHECK>(cones[neighbor as usize].p, corner, &mut roots)?;
1373 for j in 0..4 {
1374 if live < lives[j] || (live == lives[j] && d <= scores[j]) {
1375 candidates[j] = neighbor;
1376 lives[j] = live;
1377 scores[j] = d;
1378 break;
1379 }
1380 }
1381 }
1382 for tri in candidates {
1383 if tri != u32::MAX {
1384 seeds[seed_count] = tri;
1385 seed_count += 1;
1386 }
1387 }
1388 let mut seed = u32::MAX;
1389 let mut live = u32::MAX;
1390 let mut score = f32::MAX;
1391 ctx.scan(seeds[..seed_count].iter().copied(), |_ctx, tri| {
1392 let t = &indices[tri as usize * 3..][..3];
1393 let l = adj.vertices[t[0] as usize].live
1394 + adj.vertices[t[1] as usize].live
1395 + adj.vertices[t[2] as usize].live;
1396 if !CHECK
1397 && (l > live
1398 || (l == live && {
1399 let d = sub(cones[tri as usize].p, corner);
1400 lower_distance(d) >= score || root_at_least(dot(d, d), score)
1401 }))
1402 {
1403 return Ok(());
1404 }
1405 let d = distance::<CHECK>(cones[tri as usize].p, corner, &mut roots)?;
1406 if l < live || (l == live && d < score) {
1407 seed = tri;
1408 live = l;
1409 score = d;
1410 }
1411 Ok(())
1412 })?;
1413 if seed != u32::MAX {
1414 best = seed;
1415 }
1416 }
1417 let t = &indices.as_chunks::<3>().0[best as usize];
1418 if out.append(t, &mut adj.vertices, s, split, ctx)? {
1419 acc = Cone::default();
1420 }
1421 for &v in t {
1422 let state = &mut adj.vertices[v as usize];
1423 let list = &mut adj.data[state.offset as usize..][..state.live as usize];
1424 let found = if ctx.work.covers(list.len())? {
1427 let found = list.iter().position(|&tri| tri == best);
1428 ctx.tick(found.map_or(list.len(), |i| i + 1))?;
1429 found
1430 } else {
1431 let mut found = None;
1432 for (i, &tri) in list.iter().enumerate() {
1433 ctx.tick(1)?;
1434 if tri == best {
1435 found = Some(i);
1436 break;
1437 }
1438 }
1439 found
1440 };
1441 if let Some(i) = found {
1442 list[i] = list[list.len() - 1];
1443 state.live -= 1;
1444 }
1445 }
1446 for k in 0..3 {
1447 acc.p[k] = number::<CHECK>(acc.p[k] + cones[best as usize].p[k])?;
1448 acc.n[k] = number::<CHECK>(acc.n[k] + cones[best as usize].n[k])?;
1449 }
1450 emitted[best as usize] = EMITTED;
1451 }
1452 Ok(())
1453}
1454fn scan_covered(
1458 out: &mut Output<'_>,
1459 triangles: &[[u32; 3]],
1460 used: &mut [i16],
1461 s: MeshletSettings,
1462) -> usize {
1463 let mut m = out.current;
1464 let mut count = out.count;
1465 let mut visits = triangles.len();
1466 for (t, triangle) in triangles
1467 .iter()
1468 .zip(out.triangles[..triangles.len() * 3].as_chunks_mut::<3>().0)
1469 {
1470 let mut local = t.map(|v| used[v as usize]);
1471 let extra = local.iter().filter(|&&v| v < 0).count();
1472 if m.vertex_count as usize + extra > s.max_vertices
1473 || m.triangle_count as usize >= s.max_triangles
1474 {
1475 out.descriptors[count] = m;
1476 count += 1;
1477 visits += m.vertex_count as usize;
1478 for &v in &out.vertices[m.vertex_offset as usize..][..m.vertex_count as usize] {
1479 used[v as usize] = -1;
1480 }
1481 m.vertex_offset += m.vertex_count;
1482 m.triangle_offset += m.triangle_count * 3;
1483 m.vertex_count = 0;
1484 m.triangle_count = 0;
1485 local = [-1; 3];
1486 }
1487 for k in 0..3 {
1488 if local[k] < 0 {
1489 if k > 0 && t[k] == t[0] {
1490 local[k] = local[0];
1491 } else if k == 2 && t[k] == t[1] {
1492 local[k] = local[1];
1493 } else {
1494 local[k] = m.vertex_count as i16;
1495 used[t[k] as usize] = local[k];
1496 out.vertices[m.vertex_offset as usize + m.vertex_count as usize] = t[k];
1497 m.vertex_count += 1;
1498 }
1499 }
1500 triangle[k] = local[k] as u8;
1501 }
1502 m.triangle_count += 1;
1503 }
1504 out.current = m;
1505 out.count = count;
1506 visits
1507}
1508fn scan(
1509 out: &mut Output<'_>,
1510 indices: &[u32],
1511 n: usize,
1512 s: MeshletSettings,
1513 ctx: &mut Context<'_>,
1514) -> Result<(), Error> {
1515 let mut used = ctx.alloc::<i16>(n)?;
1516 used.fill(-1);
1517 let triangles = indices.as_chunks::<3>().0;
1518 if indices
1522 .len()
1523 .checked_add(triangles.len())
1524 .is_some_and(|bound| ctx.work.covers(bound).unwrap_or(false))
1525 {
1526 let visits = scan_covered(out, triangles, &mut used, s);
1527 ctx.tick(visits)?;
1528 } else {
1529 for t in triangles {
1530 out.append(t, &mut used, s, false, ctx)?;
1531 }
1532 }
1533 Ok(())
1534}
1535#[derive(Clone, Copy)]
1536pub(crate) enum Builder {
1537 Scan,
1538 Flex { min: usize, weight: f32, split: f32 },
1539 Spatial { min: usize, fill: f32 },
1540}
1541fn min_triangles(b: Builder, s: MeshletSettings) -> usize {
1542 match b {
1543 Builder::Scan => s.max_triangles,
1544 Builder::Flex { min, .. } | Builder::Spatial { min, .. } => min,
1545 }
1546}
1547fn execute(
1548 out: &mut Output<'_>,
1549 indices: &[u32],
1550 n: usize,
1551 p: Option<Positions<'_>>,
1552 s: MeshletSettings,
1553 b: Builder,
1554 ctx: &mut Context<'_>,
1555) -> Result<MeshletSizes, Error> {
1556 match b {
1557 Builder::Scan => scan(out, indices, n, s, ctx)?,
1558 Builder::Flex { min, weight, split } => {
1559 let p = p.expect("positions builder");
1560 if ctx.moderate {
1561 if weight == 0. {
1562 flex::<false, true>(out, indices, p, s, min, weight, split, ctx)?;
1563 } else {
1564 flex::<false, false>(out, indices, p, s, min, weight, split, ctx)?;
1565 }
1566 } else {
1567 flex::<true, false>(out, indices, p, s, min, weight, split, ctx)?;
1568 }
1569 }
1570 Builder::Spatial { min, fill } => crate::meshlet_spatial::spatial(
1571 out,
1572 indices,
1573 p.expect("positions builder"),
1574 s,
1575 min,
1576 fill,
1577 ctx,
1578 )?,
1579 }
1580 Ok(out.finish())
1581}
1582fn check(s: MeshletSettings, b: Builder) -> Result<(), Error> {
1583 match b {
1584 Builder::Scan => validate(s, s.max_triangles, 0., 0.),
1585 Builder::Flex { min, weight, split } => validate(s, min, weight, split),
1586 Builder::Spatial { min, fill } => {
1587 validate(s, min, 0., 0.)?;
1588 if !fill.is_finite() || fill < 0. {
1589 return Err(Error::InvalidParameter);
1590 }
1591 Ok(())
1592 }
1593 }
1594}
1595fn build(
1596 indices: &[u32],
1597 n: usize,
1598 p: Option<Positions<'_>>,
1599 s: MeshletSettings,
1600 b: Builder,
1601 workspace: &mut Workspace,
1602 trusted_moderate: Option<bool>,
1603) -> Result<Meshlets, Error> {
1604 let mut ctx = Context::new(workspace)?;
1605 check(s, b)?;
1606 ctx.topology(indices, n)?;
1607 if let Some(p) = p {
1608 if let Some(moderate) = trusted_moderate {
1609 ctx.moderate = moderate;
1610 } else {
1611 ctx.positions(p)?;
1612 }
1613 }
1614 let bound = build_meshlets_bound(indices.len(), s.max_vertices, min_triangles(b, s))?;
1615 let mut result = Meshlets {
1616 meshlets: ctx.alloc(bound)?,
1617 vertices: ctx.alloc(indices.len())?,
1618 triangles: ctx.alloc(indices.len())?,
1619 };
1620 let sizes = execute(
1621 &mut Output {
1622 descriptors: &mut result.meshlets,
1623 vertices: &mut result.vertices,
1624 triangles: &mut result.triangles,
1625 current: Meshlet::default(),
1626 count: 0,
1627 },
1628 indices,
1629 n,
1630 p,
1631 s,
1632 b,
1633 &mut ctx,
1634 )?;
1635 result.meshlets.truncate(sizes.meshlets);
1636 result.vertices.truncate(sizes.vertices);
1637 result.triangles.truncate(sizes.triangles);
1638 Ok(result)
1639}
1640fn build_into(
1641 descriptors: &mut [Meshlet],
1642 vertices: &mut [u32],
1643 triangles: &mut [u8],
1644 indices: &[u32],
1645 n: usize,
1646 p: Option<Positions<'_>>,
1647 s: MeshletSettings,
1648 b: Builder,
1649 workspace: &mut Workspace,
1650) -> Result<MeshletSizes, Error> {
1651 let mut ctx = Context::new(workspace)?;
1652 check(s, b)?;
1653 let bound = build_meshlets_bound(indices.len(), s.max_vertices, min_triangles(b, s))?;
1654 if descriptors.len() < bound
1655 || vertices.len() < indices.len()
1656 || triangles.len() < indices.len()
1657 {
1658 return Err(Error::BufferTooSmall);
1659 }
1660 ctx.topology(indices, n)?;
1661 if let Some(p) = p {
1662 ctx.positions(p)?;
1663 }
1664 execute(
1665 &mut Output {
1666 descriptors,
1667 vertices,
1668 triangles,
1669 current: Meshlet::default(),
1670 count: 0,
1671 },
1672 indices,
1673 n,
1674 p,
1675 s,
1676 b,
1677 &mut ctx,
1678 )
1679}
1680pub fn build_meshlets_scan(
1686 indices: &[u32],
1687 vertex_count: usize,
1688 s: MeshletSettings,
1689 workspace: &mut Workspace,
1690) -> Result<Meshlets, Error> {
1691 build(
1692 indices,
1693 vertex_count,
1694 None,
1695 s,
1696 Builder::Scan,
1697 workspace,
1698 None,
1699 )
1700}
1701pub fn build_meshlets(
1708 indices: &[u32],
1709 p: Positions<'_>,
1710 s: MeshletSettings,
1711 cone_weight: f32,
1712 workspace: &mut Workspace,
1713) -> Result<Meshlets, Error> {
1714 build_meshlets_flex(indices, p, s, s.max_triangles, cone_weight, 0., workspace)
1715}
1716pub fn build_meshlets_flex(
1723 indices: &[u32],
1724 p: Positions<'_>,
1725 s: MeshletSettings,
1726 min_triangles: usize,
1727 cone_weight: f32,
1728 split_factor: f32,
1729 workspace: &mut Workspace,
1730) -> Result<Meshlets, Error> {
1731 build(
1732 indices,
1733 p.len(),
1734 Some(p),
1735 s,
1736 Builder::Flex {
1737 min: min_triangles,
1738 weight: cone_weight,
1739 split: split_factor,
1740 },
1741 workspace,
1742 None,
1743 )
1744}
1745#[cfg(feature = "clusterlod")]
1746pub(crate) fn build_meshlets_flex_validated(
1747 indices: &[u32],
1748 p: Positions<'_>,
1749 s: MeshletSettings,
1750 min_triangles: usize,
1751 cone_weight: f32,
1752 split_factor: f32,
1753 moderate: bool,
1754 workspace: &mut Workspace,
1755) -> Result<Meshlets, Error> {
1756 build(
1757 indices,
1758 p.len(),
1759 Some(p),
1760 s,
1761 Builder::Flex {
1762 min: min_triangles,
1763 weight: cone_weight,
1764 split: split_factor,
1765 },
1766 workspace,
1767 Some(moderate),
1768 )
1769}
1770pub fn build_meshlets_spatial(
1777 indices: &[u32],
1778 p: Positions<'_>,
1779 s: MeshletSettings,
1780 min_triangles: usize,
1781 fill_weight: f32,
1782 workspace: &mut Workspace,
1783) -> Result<Meshlets, Error> {
1784 build(
1785 indices,
1786 p.len(),
1787 Some(p),
1788 s,
1789 Builder::Spatial {
1790 min: min_triangles,
1791 fill: fill_weight,
1792 },
1793 workspace,
1794 None,
1795 )
1796}
1797#[cfg(feature = "clusterlod")]
1798pub(crate) fn build_meshlets_spatial_validated(
1799 indices: &[u32],
1800 p: Positions<'_>,
1801 s: MeshletSettings,
1802 min_triangles: usize,
1803 fill_weight: f32,
1804 moderate: bool,
1805 workspace: &mut Workspace,
1806) -> Result<Meshlets, Error> {
1807 build(
1808 indices,
1809 p.len(),
1810 Some(p),
1811 s,
1812 Builder::Spatial {
1813 min: min_triangles,
1814 fill: fill_weight,
1815 },
1816 workspace,
1817 Some(moderate),
1818 )
1819}
1820pub fn build_meshlets_scan_into(
1825 descriptors: &mut [Meshlet],
1826 vertices: &mut [u32],
1827 triangles: &mut [u8],
1828 indices: &[u32],
1829 vertex_count: usize,
1830 s: MeshletSettings,
1831 workspace: &mut Workspace,
1832) -> Result<MeshletSizes, Error> {
1833 build_into(
1834 descriptors,
1835 vertices,
1836 triangles,
1837 indices,
1838 vertex_count,
1839 None,
1840 s,
1841 Builder::Scan,
1842 workspace,
1843 )
1844}
1845pub fn build_meshlets_into(
1850 descriptors: &mut [Meshlet],
1851 vertices: &mut [u32],
1852 triangles: &mut [u8],
1853 indices: &[u32],
1854 p: Positions<'_>,
1855 s: MeshletSettings,
1856 cone_weight: f32,
1857 workspace: &mut Workspace,
1858) -> Result<MeshletSizes, Error> {
1859 build_meshlets_flex_into(
1860 descriptors,
1861 vertices,
1862 triangles,
1863 indices,
1864 p,
1865 s,
1866 s.max_triangles,
1867 cone_weight,
1868 0.,
1869 workspace,
1870 )
1871}
1872pub fn build_meshlets_flex_into(
1877 descriptors: &mut [Meshlet],
1878 vertices: &mut [u32],
1879 triangles: &mut [u8],
1880 indices: &[u32],
1881 p: Positions<'_>,
1882 s: MeshletSettings,
1883 min_triangles: usize,
1884 cone_weight: f32,
1885 split_factor: f32,
1886 workspace: &mut Workspace,
1887) -> Result<MeshletSizes, Error> {
1888 build_into(
1889 descriptors,
1890 vertices,
1891 triangles,
1892 indices,
1893 p.len(),
1894 Some(p),
1895 s,
1896 Builder::Flex {
1897 min: min_triangles,
1898 weight: cone_weight,
1899 split: split_factor,
1900 },
1901 workspace,
1902 )
1903}
1904pub fn build_meshlets_spatial_into(
1909 descriptors: &mut [Meshlet],
1910 vertices: &mut [u32],
1911 triangles: &mut [u8],
1912 indices: &[u32],
1913 p: Positions<'_>,
1914 s: MeshletSettings,
1915 min_triangles: usize,
1916 fill_weight: f32,
1917 workspace: &mut Workspace,
1918) -> Result<MeshletSizes, Error> {
1919 build_into(
1920 descriptors,
1921 vertices,
1922 triangles,
1923 indices,
1924 p.len(),
1925 Some(p),
1926 s,
1927 Builder::Spatial {
1928 min: min_triangles,
1929 fill: fill_weight,
1930 },
1931 workspace,
1932 )
1933}