1use crate::math::LANES;
3
4use crate::processing::{cross, dot, finite, point, sub, Context};
5use crate::{Attributes, Error, Positions, Workspace};
6use alloc::vec::Vec;
7
8#[inline(always)]
9fn sqrt8(values: [f32; LANES]) -> [f32; LANES] {
10 #[cfg(feature = "simd")]
11 if let Some(result) = crate::codec::bounds_roots(values) {
12 return result;
13 }
14 crate::math::sqrt8(values)
15}
16
17#[derive(Clone, Copy, Debug)]
26pub struct BoundsPositions<'a> {
27 positions: Positions<'a>,
28 validation: Result<bool, Error>,
29}
30impl<'a> BoundsPositions<'a> {
31 pub fn new(positions: Positions<'a>) -> Self {
35 Self {
36 positions,
37 validation: crate::processing::validate_positions(positions),
38 }
39 }
40 fn apply(self, ctx: &mut Context<'_>) -> Result<bool, Error> {
41 if self.positions.len() > u32::MAX as usize {
42 return Err(Error::SizeOverflow);
43 }
44 ctx.tick(self.positions.len())?;
45 self.validation
46 }
47}
48
49#[derive(Clone, Copy, Debug, Default, PartialEq)]
51pub struct Bounds {
52 pub center: [f32; 3],
54 pub radius: f32,
56 pub cone_apex: [f32; 3],
58 pub cone_axis: [f32; 3],
60 pub cone_cutoff: f32,
62 pub cone_axis_s8: [i8; 3],
64 pub cone_cutoff_s8: i8,
66}
67#[derive(Debug, Default, PartialEq, Eq)]
69pub struct LocalMeshletGeneric<I: crate::Index = u32> {
70 pub vertices: Vec<I>,
72 pub triangles: Vec<u8>,
74}
75
76#[inline(always)]
80fn number<const CHECK: bool>(value: f32) -> Result<f32, Error> {
81 if CHECK {
82 finite(value)
83 } else {
84 Ok(value)
85 }
86}
87trait SphereSource {
88 fn sample(&self, index: usize) -> ([f32; 3], f32);
89}
90trait BoundsSource: Copy {
93 fn point(self, index: u32) -> [f32; 3];
94}
95impl BoundsSource for Positions<'_> {
96 #[inline(always)]
97 fn point(self, index: u32) -> [f32; 3] {
98 point(self, index)
99 }
100}
101impl BoundsSource for &[[f32; 3]] {
102 #[inline(always)]
103 fn point(self, index: u32) -> [f32; 3] {
104 self[index as usize]
105 }
106}
107struct PointSource<'a, P = Positions<'a>> {
108 p: P,
109 indices: Option<&'a [u32]>,
110 radii: Option<Attributes<'a>>,
111}
112impl<P: BoundsSource> SphereSource for PointSource<'_, P> {
113 #[inline(always)]
114 fn sample(&self, index: usize) -> ([f32; 3], f32) {
115 let v = self.indices.map_or(index as u32, |i| i[index]);
116 (
117 self.p.point(v),
118 self.radii
119 .map_or(0., |r| r.get(v as usize, 0).expect("validated radius")),
120 )
121 }
122}
123struct NormalSource<'a>(&'a [[f32; 4]]);
124impl SphereSource for NormalSource<'_> {
125 #[inline(always)]
126 fn sample(&self, index: usize) -> ([f32; 3], f32) {
127 let p = self.0[index];
128 ([p[0], p[1], p[2]], 0.)
129 }
130}
131#[inline(always)]
135fn bounds_roots(values: [f32; LANES], used: usize) -> [f32; LANES] {
136 if used < LANES
137 && values[..used]
138 .iter()
139 .any(|v| v.to_bits().wrapping_sub(0x0080_0000) >= 0x7f00_0000)
140 {
141 let mut result = [1.; LANES];
142 for i in 0..used {
143 result[i] = crate::math::sqrt(values[i]);
144 }
145 result
146 } else {
147 sqrt8(values)
148 }
149}
150#[inline(always)]
151fn sphere<const A: usize, const CHECK: bool>(
152 count: usize,
153 get: impl SphereSource,
154 skip_padding: bool,
155 ctx: &mut Context<'_>,
156) -> Result<([f32; 3], f32), Error> {
157 if count == 0 {
158 return Ok(([0.0; 3], 0.0));
159 }
160 let axes = [
161 [1., 0., 0.],
162 [0., 1., 0.],
163 [0., 0., 1.],
164 [0.57735026; 3],
165 [-0.57735026, 0.57735026, 0.57735026],
166 [0.57735026, -0.57735026, 0.57735026],
167 [0.57735026, 0.57735026, -0.57735026],
168 ];
169 let mut pmin = [0u32; 7];
170 let mut pmax = [0u32; 7];
171 let mut tmin = [f32::MAX; 7];
172 let mut tmax = [-f32::MAX; 7];
173 ctx.tick(count * 2)?;
174 for i in 0..count {
175 let (p, r) = get.sample(i);
176 for k in 0..A {
177 let tp = number::<CHECK>(dot(axes[k], p))?;
178 let lo = number::<CHECK>(tp - r)?;
179 let hi = number::<CHECK>(tp + r)?;
180 let lower = lo < tmin[k];
181 let upper = hi > tmax[k];
182 pmin[k] = if lower { i as u32 } else { pmin[k] };
183 pmax[k] = if upper { i as u32 } else { pmax[k] };
184 tmin[k] = if lower { lo } else { tmin[k] };
185 tmax[k] = if upper { hi } else { tmax[k] };
186 }
187 }
188 let mut squares = [1f32; LANES];
191 for k in 0..A {
192 let (a, _) = get.sample(pmin[k] as usize);
193 let (b, _) = get.sample(pmax[k] as usize);
194 let d = sub(b, a);
195 squares[k] = number::<CHECK>(dot(d, d))?;
196 }
197 let lengths = if skip_padding {
198 bounds_roots(squares, A)
199 } else {
200 sqrt8(squares)
201 };
202 let mut axis = 0;
203 let mut dr = 0.;
204 for k in 0..A {
205 let (_, ar) = get.sample(pmin[k] as usize);
206 let (_, br) = get.sample(pmax[k] as usize);
207 let v = number::<CHECK>(lengths[k] + ar + br)?;
208 if v > dr {
209 dr = v;
210 axis = k;
211 }
212 }
213 let (a, ar) = get.sample(pmin[axis] as usize);
214 let (b, br) = get.sample(pmax[axis] as usize);
215 let delta = sub(b, a);
216 let d = lengths[axis];
218 let k = if d > 0. { (d + br - ar) / (2. * d) } else { 0. };
219 let mut center = [
220 a[0] + delta[0] * k,
221 a[1] + delta[1] * k,
222 a[2] + delta[2] * k,
223 ];
224 let mut radius = dr / 2.;
225 for i in 0..count {
226 let (p, r) = get.sample(i);
227 let dp = sub(p, center);
228 let d2 = number::<CHECK>(dot(dp, dp))?;
229 let limit = radius - r;
233 if limit >= 1.0e-18 {
234 let lower = f32::from_bits(limit.to_bits() - 1);
235 if d2 <= lower * lower {
236 continue;
237 }
238 }
239 let d = ctx.sqrt(d2);
240 if d + r > radius {
241 let k = if d > 0. {
242 (d + r - radius) / (2. * d)
243 } else {
244 0.
245 };
246 for j in 0..3 {
247 center[j] += k * (p[j] - center[j]);
248 }
249 radius = (radius + d + r) / 2.;
250 }
251 }
252 for v in center {
253 number::<CHECK>(v)?;
254 }
255 number::<CHECK>(radius)?;
256 Ok((center, radius))
257}
258fn bounds<const CHECK: bool, const N: usize>(
259 indices: &[u32],
260 corners: &[u32],
261 p: impl BoundsSource,
262 ctx: &mut Context<'_>,
263) -> Result<Bounds, Error> {
264 let mut normals = [[0f32; 4]; N];
265 let mut n = 0;
266 ctx.tick(indices.len() / 3)?;
267 for group in indices.as_chunks::<3>().0.chunks(LANES) {
271 let mut corners = [[0f32; 3]; LANES];
272 let mut normals_raw = [[0f32; 3]; LANES];
273 let mut squares = [1f32; LANES];
274 for (k, t) in group.iter().enumerate() {
275 let a = p.point(t[0]);
276 let normal = cross(sub(p.point(t[1]), a), sub(p.point(t[2]), a));
277 squares[k] = number::<CHECK>(dot(normal, normal))?;
278 corners[k] = a;
279 normals_raw[k] = normal;
280 }
281 let areas = if N == 1 && group.len() == 1 {
282 bounds_roots(squares, 1)
283 } else {
284 sqrt8(squares)
285 };
286 for k in 0..group.len() {
287 let area = areas[k];
288 if area == 0. {
289 continue;
290 }
291 let mut normal = normals_raw[k];
292 for v in &mut normal {
293 *v /= area;
294 }
295 normals[n] = [
296 normal[0],
297 normal[1],
298 normal[2],
299 -number::<CHECK>(dot(normal, corners[k]))?,
300 ];
301 n += 1;
302 }
303 }
304 let mut b = Bounds::default();
305 if n == 0 {
306 return Ok(b);
307 }
308 let (center, radius) = sphere::<7, CHECK>(
309 corners.len(),
310 PointSource {
311 p,
312 indices: Some(corners),
313 radii: None,
314 },
315 N == 1,
316 ctx,
317 )?;
318 b.center = center;
319 b.radius = radius;
320 let (mut axis, _) = sphere::<3, CHECK>(n, NormalSource(&normals[..n]), N == 1, ctx)?;
321 let len = ctx.sqrt(number::<CHECK>(dot(axis, axis))?);
322 let inv = if len == 0. { 0. } else { 1. / len };
323 for a in &mut axis {
324 *a *= inv;
325 }
326 let mut mindp = 1.;
327 ctx.tick(n * 2)?;
328 for normal in &normals[..n] {
329 let dp = dot([normal[0], normal[1], normal[2]], axis);
330 if dp < mindp {
331 mindp = dp;
332 }
333 }
334 if mindp <= 0.1 {
335 b.cone_cutoff = 1.;
336 b.cone_cutoff_s8 = 127;
337 return Ok(b);
338 }
339 let mut maxt = 0.;
340 for normal in &normals[..n] {
341 let nn = [normal[0], normal[1], normal[2]];
342 let dc = dot(center, nn) + normal[3];
343 let dn = dot(axis, nn);
344 let t = number::<CHECK>(dc / dn)?;
345 if t > maxt {
346 maxt = t;
347 }
348 }
349 for j in 0..3 {
350 b.cone_apex[j] = number::<CHECK>(center[j] - axis[j] * maxt)?;
351 b.cone_axis[j] = axis[j];
352 let v = axis[j].clamp(-1., 1.);
353 b.cone_axis_s8[j] = (v * 127. + if v >= 0. { 0.5 } else { -0.5 }) as i8;
354 }
355 b.cone_cutoff = ctx.sqrt(number::<CHECK>(1. - mindp * mindp)?);
356 let e0 = (b.cone_axis_s8[0] as f32 / 127. - axis[0]).abs();
357 let e1 = (b.cone_axis_s8[1] as f32 / 127. - axis[1]).abs();
358 let e2 = (b.cone_axis_s8[2] as f32 / 127. - axis[2]).abs();
359 b.cone_cutoff_s8 = ((127. * (b.cone_cutoff + e0 + e1 + e2) + 1.) as i32).min(127) as i8;
360 Ok(b)
361}
362#[inline]
372pub fn compute_cluster_bounds_generic<I: crate::Index>(
373 indices: &[I],
374 p: Positions<'_>,
375 workspace: &mut Workspace,
376) -> Result<Bounds, Error> {
377 I::with_input(indices, workspace, |indices, workspace| {
378 compute_cluster_bounds_u32(indices, p, workspace)
379 })
380}
381
382fn compute_cluster_bounds_u32(
383 indices: &[u32],
384 p: Positions<'_>,
385 workspace: &mut Workspace,
386) -> Result<Bounds, Error> {
387 let mut ctx = Context::new(workspace)?;
388 if indices.len() > 1536 {
389 return Err(Error::InvalidParameter);
390 }
391 if indices.len() <= 96 {
392 cluster_bounds::<96, 32>(indices, p, &mut ctx, None)
393 } else if indices.len() <= 384 {
394 cluster_bounds::<384, 128>(indices, p, &mut ctx, None)
395 } else {
396 cluster_bounds::<1536, 512>(indices, p, &mut ctx, None)
397 }
398}
399#[inline]
408pub fn compute_cluster_bounds_with_positions_generic<I: crate::Index>(
409 indices: &[I],
410 p: BoundsPositions<'_>,
411 workspace: &mut Workspace,
412) -> Result<Bounds, Error> {
413 I::with_input(indices, workspace, |indices, workspace| {
414 compute_cluster_bounds_with_positions_u32(indices, p, workspace)
415 })
416}
417
418fn compute_cluster_bounds_with_positions_u32(
419 indices: &[u32],
420 p: BoundsPositions<'_>,
421 workspace: &mut Workspace,
422) -> Result<Bounds, Error> {
423 let mut ctx = Context::new(workspace)?;
424 if indices.len() > 1536 {
425 return Err(Error::InvalidParameter);
426 }
427 if indices.len() <= 96 {
428 cluster_bounds_cached::<96, 32>(indices, p, &mut ctx)
429 } else if indices.len() <= 384 {
430 cluster_bounds_cached::<384, 128>(indices, p, &mut ctx)
431 } else {
432 cluster_bounds_cached::<1536, 512>(indices, p, &mut ctx)
433 }
434}
435fn cluster_bounds_cached<const M: usize, const N: usize>(
436 indices: &[u32],
437 p: BoundsPositions<'_>,
438 ctx: &mut Context<'_>,
439) -> Result<Bounds, Error> {
440 ctx.topology(indices, p.positions.len())?;
441 ctx.moderate = p.apply(ctx)?;
442 cluster_bounds_body::<M, N>(indices, p.positions, ctx)
443}
444fn cluster_bounds_body<const M: usize, const N: usize>(
445 indices: &[u32],
446 p: Positions<'_>,
447 ctx: &mut Context<'_>,
448) -> Result<Bounds, Error> {
449 let mut cache = [u32::MAX; 512];
450 let mut corners = [0u32; M];
451 let mut n = 0;
452 ctx.tick(indices.len())?;
453 for &v in indices {
454 let c = &mut cache[v as usize & 511];
455 if *c != v {
456 corners[n] = v;
457 n += 1;
458 }
459 *c = v;
460 }
461 meshlet_bounds_result::<N>(indices, &corners[..n], p, ctx)
462}
463#[cfg(feature = "clusterlod")]
464pub(crate) fn compute_cluster_bounds_validated(
465 indices: &[u32],
466 p: Positions<'_>,
467 moderate: bool,
468 workspace: &mut Workspace,
469) -> Result<Bounds, Error> {
470 let mut ctx = Context::new(workspace)?;
471 if indices.len() > 1536 {
472 return Err(Error::InvalidParameter);
473 }
474 if indices.len() <= 96 {
475 cluster_bounds::<96, 32>(indices, p, &mut ctx, Some(moderate))
476 } else if indices.len() <= 384 {
477 cluster_bounds::<384, 128>(indices, p, &mut ctx, Some(moderate))
478 } else {
479 cluster_bounds::<1536, 512>(indices, p, &mut ctx, Some(moderate))
480 }
481}
482fn cluster_bounds<const M: usize, const N: usize>(
483 indices: &[u32],
484 p: Positions<'_>,
485 ctx: &mut Context<'_>,
486 trusted_moderate: Option<bool>,
487) -> Result<Bounds, Error> {
488 ctx.topology(indices, p.len())?;
489 if let Some(moderate) = trusted_moderate {
490 ctx.moderate = moderate;
491 } else {
492 ctx.positions(p)?;
493 }
494 let mut cache = [u32::MAX; 512];
495 let mut corners = [0u32; M];
496 let mut n = 0;
497 ctx.tick(indices.len())?;
498 for &v in indices {
499 let c = &mut cache[v as usize & 511];
500 if *c != v {
501 corners[n] = v;
502 n += 1;
503 }
504 *c = v;
505 }
506 meshlet_bounds_result::<N>(indices, &corners[..n], p, ctx)
507}
508#[inline]
518pub fn compute_meshlet_bounds_generic<I: crate::Index>(
519 vertices: &[I],
520 triangles: &[u8],
521 p: Positions<'_>,
522 workspace: &mut Workspace,
523) -> Result<Bounds, Error> {
524 I::with_input(vertices, workspace, |vertices, workspace| {
525 compute_meshlet_bounds_u32(vertices, triangles, p, workspace)
526 })
527}
528
529fn compute_meshlet_bounds_u32(
530 vertices: &[u32],
531 triangles: &[u8],
532 p: Positions<'_>,
533 workspace: &mut Workspace,
534) -> Result<Bounds, Error> {
535 let mut ctx = Context::new(workspace)?;
536 validate_local(vertices, triangles)?;
537 if triangles.len() <= 96 {
538 meshlet_bounds::<96, 32>(vertices, triangles, p, &mut ctx)
539 } else if triangles.len() <= 384 {
540 meshlet_bounds::<384, 128>(vertices, triangles, p, &mut ctx)
541 } else {
542 meshlet_bounds::<1536, 512>(vertices, triangles, p, &mut ctx)
543 }
544}
545#[inline]
554pub fn compute_meshlet_bounds_with_positions_generic<I: crate::Index>(
555 vertices: &[I],
556 triangles: &[u8],
557 p: BoundsPositions<'_>,
558 workspace: &mut Workspace,
559) -> Result<Bounds, Error> {
560 I::with_input(vertices, workspace, |vertices, workspace| {
561 compute_meshlet_bounds_with_positions_u32(vertices, triangles, p, workspace)
562 })
563}
564
565fn compute_meshlet_bounds_with_positions_u32(
566 vertices: &[u32],
567 triangles: &[u8],
568 p: BoundsPositions<'_>,
569 workspace: &mut Workspace,
570) -> Result<Bounds, Error> {
571 let mut ctx = Context::new(workspace)?;
572 validate_local(vertices, triangles)?;
573 ctx.moderate = p.apply(&mut ctx)?;
574 if triangles.len() <= 3 {
575 meshlet_bounds_body::<3, 1>(vertices, triangles, p.positions, &mut ctx)
576 } else if triangles.len() <= 96 {
577 meshlet_bounds_body::<96, 32>(vertices, triangles, p.positions, &mut ctx)
578 } else if triangles.len() <= 384 {
579 meshlet_bounds_body::<384, 128>(vertices, triangles, p.positions, &mut ctx)
580 } else {
581 meshlet_bounds_body::<1536, 512>(vertices, triangles, p.positions, &mut ctx)
582 }
583}
584fn meshlet_bounds<const M: usize, const N: usize>(
585 vertices: &[u32],
586 triangles: &[u8],
587 p: Positions<'_>,
588 ctx: &mut Context<'_>,
589) -> Result<Bounds, Error> {
590 ctx.positions(p)?;
591 ctx.tick(vertices.len() + triangles.len())?;
592 if vertices.iter().any(|&v| v as usize >= p.len()) {
593 return Err(Error::IndexOutOfBounds);
594 }
595 let mut indices = [0u32; M];
596 let mut n = 0;
597 for (i, &v) in triangles.iter().enumerate() {
598 indices[i] = vertices[v as usize];
599 n = n.max(v as usize + 1);
600 }
601 meshlet_bounds_result::<N>(&indices[..triangles.len()], &vertices[..n], p, ctx)
602}
603fn meshlet_bounds_body<const M: usize, const N: usize>(
604 vertices: &[u32],
605 triangles: &[u8],
606 p: Positions<'_>,
607 ctx: &mut Context<'_>,
608) -> Result<Bounds, Error> {
609 ctx.tick(vertices.len() + triangles.len())?;
610 if vertices
611 .iter()
612 .copied()
613 .max()
614 .is_some_and(|v| v as usize >= p.len())
615 {
616 return Err(Error::IndexOutOfBounds);
617 }
618 if N == 1 {
619 let Some(triangle) = triangles.first_chunk::<3>() else {
620 return Ok(Bounds::default());
621 };
622 let indices = triangle.map(|v| vertices[v as usize]);
623 let n = triangle.iter().copied().max().unwrap() as usize + 1;
624 return meshlet_bounds_result::<N>(&indices, &vertices[..n], p, ctx);
625 }
626 let mut indices = [0u32; M];
627 let mut n = 0;
628 for (i, &v) in triangles.iter().enumerate() {
629 indices[i] = vertices[v as usize];
630 n = n.max(v as usize + 1);
631 }
632 meshlet_bounds_result::<N>(&indices[..triangles.len()], &vertices[..n], p, ctx)
633}
634#[inline(always)]
635fn meshlet_bounds_result<const N: usize>(
636 indices: &[u32],
637 corners: &[u32],
638 p: Positions<'_>,
639 ctx: &mut Context<'_>,
640) -> Result<Bounds, Error> {
641 if let Some(packed) = p.packed_values() {
642 if ctx.moderate {
643 bounds::<false, N>(indices, corners, packed, ctx)
644 } else {
645 bounds::<true, N>(indices, corners, packed, ctx)
646 }
647 } else if ctx.moderate {
648 bounds::<false, N>(indices, corners, p, ctx)
649 } else {
650 bounds::<true, N>(indices, corners, p, ctx)
651 }
652}
653pub fn compute_sphere_bounds(
660 p: Positions<'_>,
661 radii: Option<Attributes<'_>>,
662 workspace: &mut Workspace,
663) -> Result<Bounds, Error> {
664 let mut ctx = Context::new(workspace)?;
665 ctx.positions(p)?;
666 if let Some(r) = radii {
667 if r.len() != p.len() || r.components() != 1 {
668 return Err(Error::InvalidLayout);
669 }
670 ctx.tick(r.len())?;
671 for i in 0..r.len() {
672 let v = r.get(i, 0).ok_or(Error::InvalidLayout)?;
673 ctx.moderate &= v <= 1.0e8;
674 if !v.is_finite() || v < 0. {
675 return Err(Error::InvalidParameter);
676 }
677 }
678 }
679 let get = PointSource {
680 p,
681 indices: None,
682 radii,
683 };
684 let (center, radius) = if ctx.moderate {
685 sphere::<7, false>(p.len(), get, false, &mut ctx)?
686 } else {
687 sphere::<7, true>(p.len(), get, false, &mut ctx)?
688 };
689 Ok(Bounds {
690 center,
691 radius,
692 ..Bounds::default()
693 })
694}
695fn validate_local(v: &[u32], t: &[u8]) -> Result<(), Error> {
696 if !t.len().is_multiple_of(3) {
697 return Err(Error::InvalidTopology);
698 }
699 if v.len() > 256 || t.len() > 1536 {
700 return Err(Error::InvalidParameter);
701 }
702 if t.iter().any(|&i| i as usize >= v.len()) {
703 return Err(Error::IndexOutOfBounds);
704 }
705 Ok(())
706}
707fn extract<const V: usize, const T: usize>(
708 indices: &[u32],
709 vertices: &mut [u32; V],
710 triangles: &mut [u8; T],
711 ctx: &mut Context<'_>,
712) -> Result<usize, Error> {
713 if !indices.len().is_multiple_of(3) {
714 return Err(Error::InvalidTopology);
715 }
716 if indices.len() > 1536 {
717 return Err(Error::InvalidParameter);
718 }
719 let mut n = 0;
720 let mut cache = [-1i16; 1024];
721 ctx.tick(indices.len())?;
722 for (i, &v) in indices.iter().enumerate() {
723 let key = v as usize & 1023;
724 let c = cache[key];
725 if c >= 0 && vertices[c as u8 as usize] == v {
726 triangles[i] = c as u8;
727 continue;
728 }
729 let pos = if c < 0 {
730 n
731 } else {
732 ctx.tick(n)?;
733 vertices[..n].iter().position(|&x| x == v).unwrap_or(n)
734 };
735 if pos == n {
736 if n == 256 {
737 return Err(Error::InvalidParameter);
738 }
739 vertices[n] = v;
740 n += 1;
741 }
742 cache[key] = pos as i16;
743 triangles[i] = pos as u8;
744 }
745 Ok(n)
746}
747#[inline]
753pub fn extract_meshlet_indices_generic<I: crate::Index>(
754 indices: &[I],
755 workspace: &mut Workspace,
756) -> Result<LocalMeshletGeneric<I>, Error> {
757 I::with_input(indices, workspace, |indices, workspace| {
758 extract_meshlet_indices_u32(indices, workspace)
759 .and_then(|value| crate::index::Convert::<I>::convert(value, workspace))
760 })
761}
762
763fn extract_meshlet_indices_u32(
764 indices: &[u32],
765 workspace: &mut Workspace,
766) -> Result<LocalMeshletGeneric, Error> {
767 let mut ctx = Context::new(workspace)?;
768 extracted(indices, &mut ctx, |v, t, ctx| {
769 Ok(LocalMeshletGeneric {
770 vertices: ctx.copy(v)?,
771 triangles: ctx.copy(t)?,
772 })
773 })
774}
775#[inline(always)]
779fn extracted<R>(
780 indices: &[u32],
781 ctx: &mut Context<'_>,
782 finish: impl FnOnce(&[u32], &[u8], &mut Context<'_>) -> Result<R, Error>,
783) -> Result<R, Error> {
784 if indices.len() <= 96 {
785 let (mut v, mut t) = ([0; 96], [0; 96]);
786 let n = extract(indices, &mut v, &mut t, ctx)?;
787 finish(&v[..n], &t[..indices.len()], ctx)
788 } else if indices.len() <= 384 {
789 let (mut v, mut t) = ([0; 256], [0; 384]);
790 let n = extract(indices, &mut v, &mut t, ctx)?;
791 finish(&v[..n], &t[..indices.len()], ctx)
792 } else {
793 let (mut v, mut t) = ([0; 256], [0; 1536]);
794 let n = extract(indices, &mut v, &mut t, ctx)?;
795 finish(&v[..n], &t[..indices.len()], ctx)
796 }
797}
798#[inline]
803pub fn extract_meshlet_indices_into_generic<I: crate::Index>(
804 vertices: &mut [I],
805 triangles: &mut [u8],
806 indices: &[I],
807 workspace: &mut Workspace,
808) -> Result<usize, Error> {
809 I::with_input(indices, workspace, |indices, workspace| {
810 I::with_mut(vertices, workspace, |vertices, workspace| {
811 extract_meshlet_indices_into_u32(vertices, triangles, indices, workspace)
812 })
813 })
814}
815
816fn extract_meshlet_indices_into_u32(
817 vertices: &mut [u32],
818 triangles: &mut [u8],
819 indices: &[u32],
820 workspace: &mut Workspace,
821) -> Result<usize, Error> {
822 let mut ctx = Context::new(workspace)?;
823 if triangles.len() < indices.len() {
824 return Err(Error::BufferTooSmall);
825 }
826 extracted(indices, &mut ctx, |v, t, _| {
827 if vertices.len() < v.len() {
828 return Err(Error::BufferTooSmall);
829 }
830 vertices[..v.len()].copy_from_slice(v);
831 triangles[..t.len()].copy_from_slice(t);
832 Ok(v.len())
833 })
834}
835fn optimize(v: &mut [u32], t: &mut [u8], level: u8, ctx: &mut Context<'_>) -> Result<(), Error> {
837 if level > 9 {
838 return Err(Error::InvalidParameter);
839 }
840 if level == 0 {
841 optimize_body::<false>(v, t, level, ctx)
842 } else {
843 optimize_body::<true>(v, t, level, ctx)
844 }
845}
846fn optimize_body<const ADVANCED: bool>(
847 v: &mut [u32],
848 t: &mut [u8],
849 level: u8,
850 ctx: &mut Context<'_>,
851) -> Result<(), Error> {
852 let n = t.len() / 3;
853 if n <= 1 {
856 ctx.tick(t.len())?;
857 if n == 1 {
858 ctx.tick(1)?;
859 ctx.tick(1)?;
860 if ADVANCED {
861 ctx.tick(1)?;
862 }
863 }
864 ctx.tick(t.len())?;
865 let mut source = [0u8; 3];
866 let mut order = [0u32; 3];
867 let mut count = 0;
868 for x in t {
869 let local = match source[..count].iter().position(|&i| i == *x) {
870 Some(local) => local,
871 None => {
872 source[count] = *x;
873 order[count] = v[*x as usize];
874 count += 1;
875 count - 1
876 }
877 };
878 *x = local as u8;
879 }
880 v[..count].copy_from_slice(&order[..count]);
881 return Ok(());
882 }
883 let mut cache = [0u8; 256];
884 let mut last = 128u8;
885 let mut valence = [0u8; 256];
886 ctx.tick(t.len())?;
887 for &i in t.iter() {
888 valence[i as usize] = valence[i as usize].wrapping_add(1);
889 }
890 for i in 0..n {
891 let mut next = i;
892 let mut best = -1;
893 let mut edges = 0;
894 ctx.search(
895 t.as_chunks::<3>().0[i..].iter().enumerate(),
896 |(offset, tri)| {
897 let (a, b, c) = (tri[0] as usize, tri[1] as usize, tri[2] as usize);
898 let (ad, bd, cd) = (
899 last.wrapping_sub(cache[a]),
900 last.wrapping_sub(cache[b]),
901 last.wrapping_sub(cache[c]),
902 );
903 let matches = i32::from(ad < 3) + i32::from(bd < 3) + i32::from(cd < 3);
904 let score = if ADVANCED {
905 (matches * 1024 + (1023 - ad as i32 - bd as i32 - cd as i32)) * 256
906 + (255 - valence[a].min(valence[b]).min(valence[c]) as i32)
907 } else {
908 matches
909 };
910 if score > best {
911 best = score;
912 next = i + offset;
913 }
914 if matches >= 2 {
915 edges += 1;
916 if !ADVANCED || edges >= level {
917 return true;
918 }
919 }
920 false
921 },
922 )?;
923 ctx.tick(next - i + 1)?;
924 let tri = [t[next * 3], t[next * 3 + 1], t[next * 3 + 2]];
925 t.copy_within(i * 3..next * 3, (i + 1) * 3);
926 t[i * 3..i * 3 + 3].copy_from_slice(&tri);
927 last = last.wrapping_add(1);
928 for x in tri {
929 cache[x as usize] = last;
930 valence[x as usize] = valence[x as usize].wrapping_sub(1);
931 }
932 }
933 if ADVANCED {
934 cache.fill(0);
935 for i in 0..n {
936 ctx.tick(1)?;
937 let mut tri = [t[i * 3], t[i * 3 + 1], t[i * 3 + 2]];
938 let [a, b, c] = tri;
939 if cache[a as usize] == 0 && cache[b as usize] != 0 && cache[c as usize] == 0 {
940 tri.rotate_left(1);
941 } else if cache[a as usize] == 0 && cache[b as usize] == 0 && cache[c as usize] == 0 {
942 let (mut ab, mut bc, mut ca) = (false, false, false);
943 for j in i + 1..n.min(i + 4) {
944 ctx.tick(1)?;
945 let [oa, ob, oc] = [t[j * 3], t[j * 3 + 1], t[j * 3 + 2]];
946 ab |= (oa == b && ob == a) || (ob == b && oc == a) || (oc == b && oa == a);
947 bc |= (oa == c && ob == b) || (ob == c && oc == b) || (oc == c && oa == b);
948 ca |= (oa == a && ob == c) || (ob == a && oc == c) || (oc == a && oa == c);
949 }
950 if ab && !bc {
951 tri.rotate_left(1);
952 } else if (ab && !ca) || (!ab && bc && !ca) {
953 tri.rotate_right(1);
954 }
955 }
956 t[i * 3..i * 3 + 3].copy_from_slice(&tri);
957 for x in tri {
958 cache[x as usize] = 1;
959 }
960 }
961 }
962 let mut remap = [-1i16; 256];
963 let mut order = [0u32; 256];
964 let mut count = 0;
965 ctx.tick(t.len())?;
966 for x in t {
967 let r = &mut remap[*x as usize];
968 if *r < 0 {
969 *r = count as i16;
970 order[count] = v[*x as usize];
971 count += 1;
972 }
973 *x = *r as u8;
974 }
975 v[..count].copy_from_slice(&order[..count]);
976 Ok(())
977}
978#[inline]
984pub fn optimize_meshlet_level_in_place_generic<I: crate::Index>(
985 vertices: &mut [I],
986 triangles: &mut [u8],
987 level: u8,
988 workspace: &mut Workspace,
989) -> Result<(), Error> {
990 I::with_mut(vertices, workspace, |vertices, workspace| {
991 optimize_meshlet_level_in_place_u32(vertices, triangles, level, workspace)
992 })
993}
994
995fn optimize_meshlet_level_in_place_u32(
996 vertices: &mut [u32],
997 triangles: &mut [u8],
998 level: u8,
999 workspace: &mut Workspace,
1000) -> Result<(), Error> {
1001 let mut ctx = Context::new(workspace)?;
1002 validate_local(vertices, triangles)?;
1003 let mut v = [0; 256];
1004 let mut t = [0; 1536];
1005 v[..vertices.len()].copy_from_slice(vertices);
1006 t[..triangles.len()].copy_from_slice(triangles);
1007 optimize(
1008 &mut v[..vertices.len()],
1009 &mut t[..triangles.len()],
1010 level,
1011 &mut ctx,
1012 )?;
1013 vertices.copy_from_slice(&v[..vertices.len()]);
1014 triangles.copy_from_slice(&t[..triangles.len()]);
1015 Ok(())
1016}
1017#[inline]
1022pub fn optimize_meshlet_in_place_generic<I: crate::Index>(
1023 vertices: &mut [I],
1024 triangles: &mut [u8],
1025 workspace: &mut Workspace,
1026) -> Result<(), Error> {
1027 I::with_mut(vertices, workspace, |vertices, workspace| {
1028 optimize_meshlet_in_place_u32(vertices, triangles, workspace)
1029 })
1030}
1031
1032fn optimize_meshlet_in_place_u32(
1033 vertices: &mut [u32],
1034 triangles: &mut [u8],
1035 workspace: &mut Workspace,
1036) -> Result<(), Error> {
1037 optimize_meshlet_level_in_place_generic(vertices, triangles, 0, workspace)
1038}
1039#[inline]
1044pub fn optimize_meshlet_level_generic<I: crate::Index>(
1045 vertices: &[I],
1046 triangles: &[u8],
1047 level: u8,
1048 workspace: &mut Workspace,
1049) -> Result<LocalMeshletGeneric<I>, Error> {
1050 I::with_input(vertices, workspace, |vertices, workspace| {
1051 optimize_meshlet_level_u32(vertices, triangles, level, workspace)
1052 .and_then(|value| crate::index::Convert::<I>::convert(value, workspace))
1053 })
1054}
1055
1056fn optimize_meshlet_level_u32(
1057 vertices: &[u32],
1058 triangles: &[u8],
1059 level: u8,
1060 workspace: &mut Workspace,
1061) -> Result<LocalMeshletGeneric, Error> {
1062 let mut ctx = Context::new(workspace)?;
1063 validate_local(vertices, triangles)?;
1064 let mut v = ctx.copy(vertices)?;
1065 let mut t = ctx.copy(triangles)?;
1066 optimize(&mut v, &mut t, level, &mut ctx)?;
1067 Ok(LocalMeshletGeneric {
1068 vertices: v,
1069 triangles: t,
1070 })
1071}
1072#[inline]
1077pub fn optimize_meshlet_generic<I: crate::Index>(
1078 vertices: &[I],
1079 triangles: &[u8],
1080 workspace: &mut Workspace,
1081) -> Result<LocalMeshletGeneric<I>, Error> {
1082 I::with_input(vertices, workspace, |vertices, workspace| {
1083 optimize_meshlet_u32(vertices, triangles, workspace)
1084 .and_then(|value| crate::index::Convert::<I>::convert(value, workspace))
1085 })
1086}
1087
1088fn optimize_meshlet_u32(
1089 vertices: &[u32],
1090 triangles: &[u8],
1091 workspace: &mut Workspace,
1092) -> Result<LocalMeshletGeneric, Error> {
1093 optimize_meshlet_level_generic(vertices, triangles, 0, workspace)
1094}
1095
1096#[inline]
1102pub fn optimize_meshlet_level_into_generic<I: crate::Index>(
1103 out_vertices: &mut [I],
1104 out_triangles: &mut [u8],
1105 vertices: &[I],
1106 triangles: &[u8],
1107 level: u8,
1108 workspace: &mut Workspace,
1109) -> Result<(), Error> {
1110 I::with_input(vertices, workspace, |vertices, workspace| {
1111 I::with_mut(out_vertices, workspace, |out_vertices, workspace| {
1112 optimize_meshlet_level_into_u32(
1113 out_vertices,
1114 out_triangles,
1115 vertices,
1116 triangles,
1117 level,
1118 workspace,
1119 )
1120 })
1121 })
1122}
1123
1124fn optimize_meshlet_level_into_u32(
1125 out_vertices: &mut [u32],
1126 out_triangles: &mut [u8],
1127 vertices: &[u32],
1128 triangles: &[u8],
1129 level: u8,
1130 workspace: &mut Workspace,
1131) -> Result<(), Error> {
1132 let mut ctx = Context::new(workspace)?;
1133 if out_vertices.len() < vertices.len() || out_triangles.len() < triangles.len() {
1134 return Err(Error::BufferTooSmall);
1135 }
1136 validate_local(vertices, triangles)?;
1137 let mut v = [0; 256];
1138 let mut t = [0; 1536];
1139 v[..vertices.len()].copy_from_slice(vertices);
1140 t[..triangles.len()].copy_from_slice(triangles);
1141 optimize(
1142 &mut v[..vertices.len()],
1143 &mut t[..triangles.len()],
1144 level,
1145 &mut ctx,
1146 )?;
1147 out_vertices[..vertices.len()].copy_from_slice(&v[..vertices.len()]);
1148 out_triangles[..triangles.len()].copy_from_slice(&t[..triangles.len()]);
1149 Ok(())
1150}
1151#[inline]
1156pub fn optimize_meshlet_into_generic<I: crate::Index>(
1157 out_vertices: &mut [I],
1158 out_triangles: &mut [u8],
1159 vertices: &[I],
1160 triangles: &[u8],
1161 workspace: &mut Workspace,
1162) -> Result<(), Error> {
1163 I::with_input(vertices, workspace, |vertices, workspace| {
1164 I::with_mut(out_vertices, workspace, |out_vertices, workspace| {
1165 optimize_meshlet_into_u32(out_vertices, out_triangles, vertices, triangles, workspace)
1166 })
1167 })
1168}
1169
1170fn optimize_meshlet_into_u32(
1171 out_vertices: &mut [u32],
1172 out_triangles: &mut [u8],
1173 vertices: &[u32],
1174 triangles: &[u8],
1175 workspace: &mut Workspace,
1176) -> Result<(), Error> {
1177 optimize_meshlet_level_into_generic(
1178 out_vertices,
1179 out_triangles,
1180 vertices,
1181 triangles,
1182 0,
1183 workspace,
1184 )
1185}
1186
1187#[inline]
1189pub fn compute_cluster_bounds(
1190 indices: &[u32],
1191 p: Positions<'_>,
1192 workspace: &mut Workspace,
1193) -> Result<Bounds, Error> {
1194 compute_cluster_bounds_generic::<u32>(indices, p, workspace)
1195}
1196
1197#[inline]
1199pub fn compute_cluster_bounds_with_positions(
1200 indices: &[u32],
1201 p: BoundsPositions<'_>,
1202 workspace: &mut Workspace,
1203) -> Result<Bounds, Error> {
1204 compute_cluster_bounds_with_positions_generic::<u32>(indices, p, workspace)
1205}
1206
1207#[inline]
1209pub fn compute_meshlet_bounds(
1210 vertices: &[u32],
1211 triangles: &[u8],
1212 p: Positions<'_>,
1213 workspace: &mut Workspace,
1214) -> Result<Bounds, Error> {
1215 compute_meshlet_bounds_generic::<u32>(vertices, triangles, p, workspace)
1216}
1217
1218#[inline]
1220pub fn compute_meshlet_bounds_with_positions(
1221 vertices: &[u32],
1222 triangles: &[u8],
1223 p: BoundsPositions<'_>,
1224 workspace: &mut Workspace,
1225) -> Result<Bounds, Error> {
1226 compute_meshlet_bounds_with_positions_generic::<u32>(vertices, triangles, p, workspace)
1227}
1228
1229#[inline]
1231pub fn extract_meshlet_indices(
1232 indices: &[u32],
1233 workspace: &mut Workspace,
1234) -> Result<LocalMeshlet, Error> {
1235 extract_meshlet_indices_generic::<u32>(indices, workspace).map(Into::into)
1236}
1237
1238#[inline]
1240pub fn extract_meshlet_indices_into(
1241 vertices: &mut [u32],
1242 triangles: &mut [u8],
1243 indices: &[u32],
1244 workspace: &mut Workspace,
1245) -> Result<usize, Error> {
1246 extract_meshlet_indices_into_generic::<u32>(vertices, triangles, indices, workspace)
1247}
1248
1249#[inline]
1251pub fn optimize_meshlet_level_in_place(
1252 vertices: &mut [u32],
1253 triangles: &mut [u8],
1254 level: u8,
1255 workspace: &mut Workspace,
1256) -> Result<(), Error> {
1257 optimize_meshlet_level_in_place_generic::<u32>(vertices, triangles, level, workspace)
1258}
1259
1260#[inline]
1262pub fn optimize_meshlet_in_place(
1263 vertices: &mut [u32],
1264 triangles: &mut [u8],
1265 workspace: &mut Workspace,
1266) -> Result<(), Error> {
1267 optimize_meshlet_in_place_generic::<u32>(vertices, triangles, workspace)
1268}
1269
1270#[inline]
1272pub fn optimize_meshlet_level(
1273 vertices: &[u32],
1274 triangles: &[u8],
1275 level: u8,
1276 workspace: &mut Workspace,
1277) -> Result<LocalMeshlet, Error> {
1278 optimize_meshlet_level_generic::<u32>(vertices, triangles, level, workspace).map(Into::into)
1279}
1280
1281#[inline]
1283pub fn optimize_meshlet(
1284 vertices: &[u32],
1285 triangles: &[u8],
1286 workspace: &mut Workspace,
1287) -> Result<LocalMeshlet, Error> {
1288 optimize_meshlet_generic::<u32>(vertices, triangles, workspace).map(Into::into)
1289}
1290
1291#[inline]
1293pub fn optimize_meshlet_level_into(
1294 out_vertices: &mut [u32],
1295 out_triangles: &mut [u8],
1296 vertices: &[u32],
1297 triangles: &[u8],
1298 level: u8,
1299 workspace: &mut Workspace,
1300) -> Result<(), Error> {
1301 optimize_meshlet_level_into_generic::<u32>(
1302 out_vertices,
1303 out_triangles,
1304 vertices,
1305 triangles,
1306 level,
1307 workspace,
1308 )
1309}
1310
1311#[inline]
1313pub fn optimize_meshlet_into(
1314 out_vertices: &mut [u32],
1315 out_triangles: &mut [u8],
1316 vertices: &[u32],
1317 triangles: &[u8],
1318 workspace: &mut Workspace,
1319) -> Result<(), Error> {
1320 optimize_meshlet_into_generic::<u32>(
1321 out_vertices,
1322 out_triangles,
1323 vertices,
1324 triangles,
1325 workspace,
1326 )
1327}
1328
1329#[derive(Debug, Default, PartialEq, Eq)]
1332pub struct LocalMeshlet {
1333 pub vertices: Vec<u32>,
1335 pub triangles: Vec<u8>,
1337}
1338impl From<LocalMeshletGeneric<u32>> for LocalMeshlet {
1339 #[inline]
1340 fn from(value: LocalMeshletGeneric<u32>) -> Self {
1341 Self {
1342 vertices: value.vertices,
1343 triangles: value.triangles,
1344 }
1345 }
1346}
1347
1348impl From<LocalMeshlet> for LocalMeshletGeneric<u32> {
1349 #[inline]
1350 fn from(value: LocalMeshlet) -> Self {
1351 Self {
1352 vertices: value.vertices,
1353 triangles: value.triangles,
1354 }
1355 }
1356}
1357
1358#[cfg(test)]
1359mod bounds_root_tests {
1360 use super::{bounds_roots, sqrt8, LANES};
1361
1362 #[test]
1363 fn used_roots_match_full_lanes_bit_for_bit() {
1364 let mut state = 0x1357_2468u32;
1365 let special = [
1366 0,
1367 1,
1368 0x007f_ffff,
1369 0x0080_0000,
1370 0x3f80_0000,
1371 0x7f7f_ffff,
1372 0x8000_0000,
1373 0xbf80_0000,
1374 0x7f80_0000,
1375 0x7fc0_1234,
1376 ];
1377 for sample in 0..512 {
1378 for used in 1..=LANES {
1379 let mut values = [1.; LANES];
1380 for value in &mut values[..used] {
1381 state = state.wrapping_mul(1664525).wrapping_add(1013904223);
1382 let bits = if sample < special.len() {
1383 special[sample]
1384 } else if sample.is_multiple_of(2) {
1385 0x0080_0000 + state % 0x7f00_0000
1386 } else {
1387 state
1388 };
1389 *value = f32::from_bits(bits);
1390 }
1391 assert_eq!(
1392 bounds_roots(values, used).map(f32::to_bits),
1393 sqrt8(values).map(f32::to_bits)
1394 );
1395 }
1396 }
1397 }
1398}