1use crate::math::{sqrt8, LANES};
3use crate::processing::{cross, dot, finite, point, sub, Context};
4use crate::{Attributes, Error, Positions, Workspace};
5use alloc::vec::Vec;
6
7#[derive(Clone, Copy, Debug)]
16pub struct BoundsPositions<'a> {
17 positions: Positions<'a>,
18 validation: Result<bool, Error>,
19}
20impl<'a> BoundsPositions<'a> {
21 pub fn new(positions: Positions<'a>) -> Self {
25 Self {
26 positions,
27 validation: crate::processing::validate_positions(positions),
28 }
29 }
30 fn apply(self, ctx: &mut Context<'_>) -> Result<bool, Error> {
31 if self.positions.len() > u32::MAX as usize {
32 return Err(Error::SizeOverflow);
33 }
34 ctx.tick(self.positions.len())?;
35 self.validation
36 }
37}
38
39#[derive(Clone, Copy, Debug, Default, PartialEq)]
41pub struct Bounds {
42 pub center: [f32; 3],
44 pub radius: f32,
46 pub cone_apex: [f32; 3],
48 pub cone_axis: [f32; 3],
50 pub cone_cutoff: f32,
52 pub cone_axis_s8: [i8; 3],
54 pub cone_cutoff_s8: i8,
56}
57#[derive(Debug, Default, PartialEq, Eq)]
59pub struct LocalMeshlet {
60 pub vertices: Vec<u32>,
62 pub triangles: Vec<u8>,
64}
65
66#[inline(always)]
70fn number<const CHECK: bool>(value: f32) -> Result<f32, Error> {
71 if CHECK {
72 finite(value)
73 } else {
74 Ok(value)
75 }
76}
77trait SphereSource {
78 fn sample(&self, index: usize) -> ([f32; 3], f32);
79}
80trait BoundsSource: Copy {
83 fn point(self, index: u32) -> [f32; 3];
84}
85impl BoundsSource for Positions<'_> {
86 #[inline(always)]
87 fn point(self, index: u32) -> [f32; 3] {
88 point(self, index)
89 }
90}
91impl BoundsSource for &[[f32; 3]] {
92 #[inline(always)]
93 fn point(self, index: u32) -> [f32; 3] {
94 self[index as usize]
95 }
96}
97struct PointSource<'a, P = Positions<'a>> {
98 p: P,
99 indices: Option<&'a [u32]>,
100 radii: Option<Attributes<'a>>,
101}
102impl<P: BoundsSource> SphereSource for PointSource<'_, P> {
103 #[inline(always)]
104 fn sample(&self, index: usize) -> ([f32; 3], f32) {
105 let v = self.indices.map_or(index as u32, |i| i[index]);
106 (
107 self.p.point(v),
108 self.radii
109 .map_or(0., |r| r.get(v as usize, 0).expect("validated radius")),
110 )
111 }
112}
113struct NormalSource<'a>(&'a [[f32; 4]]);
114impl SphereSource for NormalSource<'_> {
115 #[inline(always)]
116 fn sample(&self, index: usize) -> ([f32; 3], f32) {
117 let p = self.0[index];
118 ([p[0], p[1], p[2]], 0.)
119 }
120}
121#[inline(always)]
125fn bounds_roots(values: [f32; LANES], used: usize) -> [f32; LANES] {
126 if used < LANES
127 && values[..used]
128 .iter()
129 .any(|v| v.to_bits().wrapping_sub(0x0080_0000) >= 0x7f00_0000)
130 {
131 let mut result = [1.; LANES];
132 for i in 0..used {
133 result[i] = crate::math::sqrt(values[i]);
134 }
135 result
136 } else {
137 sqrt8(values)
138 }
139}
140#[inline(always)]
141fn sphere<const A: usize, const CHECK: bool>(
142 count: usize,
143 get: impl SphereSource,
144 skip_padding: bool,
145 ctx: &mut Context<'_>,
146) -> Result<([f32; 3], f32), Error> {
147 if count == 0 {
148 return Ok(([0.0; 3], 0.0));
149 }
150 let axes = [
151 [1., 0., 0.],
152 [0., 1., 0.],
153 [0., 0., 1.],
154 [0.57735026; 3],
155 [-0.57735026, 0.57735026, 0.57735026],
156 [0.57735026, -0.57735026, 0.57735026],
157 [0.57735026, 0.57735026, -0.57735026],
158 ];
159 let mut pmin = [0u32; 7];
160 let mut pmax = [0u32; 7];
161 let mut tmin = [f32::MAX; 7];
162 let mut tmax = [-f32::MAX; 7];
163 ctx.tick(count * 2)?;
164 for i in 0..count {
165 let (p, r) = get.sample(i);
166 for k in 0..A {
167 let tp = number::<CHECK>(dot(axes[k], p))?;
168 let lo = number::<CHECK>(tp - r)?;
169 let hi = number::<CHECK>(tp + r)?;
170 let lower = lo < tmin[k];
171 let upper = hi > tmax[k];
172 pmin[k] = if lower { i as u32 } else { pmin[k] };
173 pmax[k] = if upper { i as u32 } else { pmax[k] };
174 tmin[k] = if lower { lo } else { tmin[k] };
175 tmax[k] = if upper { hi } else { tmax[k] };
176 }
177 }
178 let mut squares = [1f32; LANES];
181 for k in 0..A {
182 let (a, _) = get.sample(pmin[k] as usize);
183 let (b, _) = get.sample(pmax[k] as usize);
184 let d = sub(b, a);
185 squares[k] = number::<CHECK>(dot(d, d))?;
186 }
187 let lengths = if skip_padding {
188 bounds_roots(squares, A)
189 } else {
190 sqrt8(squares)
191 };
192 let mut axis = 0;
193 let mut dr = 0.;
194 for k in 0..A {
195 let (_, ar) = get.sample(pmin[k] as usize);
196 let (_, br) = get.sample(pmax[k] as usize);
197 let v = number::<CHECK>(lengths[k] + ar + br)?;
198 if v > dr {
199 dr = v;
200 axis = k;
201 }
202 }
203 let (a, ar) = get.sample(pmin[axis] as usize);
204 let (b, br) = get.sample(pmax[axis] as usize);
205 let delta = sub(b, a);
206 let d = lengths[axis];
208 let k = if d > 0. { (d + br - ar) / (2. * d) } else { 0. };
209 let mut center = [
210 a[0] + delta[0] * k,
211 a[1] + delta[1] * k,
212 a[2] + delta[2] * k,
213 ];
214 let mut radius = dr / 2.;
215 for i in 0..count {
216 let (p, r) = get.sample(i);
217 let dp = sub(p, center);
218 let d2 = number::<CHECK>(dot(dp, dp))?;
219 let limit = radius - r;
223 if limit >= 1.0e-18 {
224 let lower = f32::from_bits(limit.to_bits() - 1);
225 if d2 <= lower * lower {
226 continue;
227 }
228 }
229 let d = ctx.sqrt(d2);
230 if d + r > radius {
231 let k = if d > 0. {
232 (d + r - radius) / (2. * d)
233 } else {
234 0.
235 };
236 for j in 0..3 {
237 center[j] += k * (p[j] - center[j]);
238 }
239 radius = (radius + d + r) / 2.;
240 }
241 }
242 for v in center {
243 number::<CHECK>(v)?;
244 }
245 number::<CHECK>(radius)?;
246 Ok((center, radius))
247}
248fn bounds<const CHECK: bool, const N: usize>(
249 indices: &[u32],
250 corners: &[u32],
251 p: impl BoundsSource,
252 ctx: &mut Context<'_>,
253) -> Result<Bounds, Error> {
254 let mut normals = [[0f32; 4]; N];
255 let mut n = 0;
256 ctx.tick(indices.len() / 3)?;
257 for group in indices.as_chunks::<3>().0.chunks(LANES) {
261 let mut corners = [[0f32; 3]; LANES];
262 let mut normals_raw = [[0f32; 3]; LANES];
263 let mut squares = [1f32; LANES];
264 for (k, t) in group.iter().enumerate() {
265 let a = p.point(t[0]);
266 let normal = cross(sub(p.point(t[1]), a), sub(p.point(t[2]), a));
267 squares[k] = number::<CHECK>(dot(normal, normal))?;
268 corners[k] = a;
269 normals_raw[k] = normal;
270 }
271 let areas = if N == 1 && group.len() == 1 {
272 bounds_roots(squares, 1)
273 } else {
274 sqrt8(squares)
275 };
276 for k in 0..group.len() {
277 let area = areas[k];
278 if area == 0. {
279 continue;
280 }
281 let mut normal = normals_raw[k];
282 for v in &mut normal {
283 *v /= area;
284 }
285 normals[n] = [
286 normal[0],
287 normal[1],
288 normal[2],
289 -number::<CHECK>(dot(normal, corners[k]))?,
290 ];
291 n += 1;
292 }
293 }
294 let mut b = Bounds::default();
295 if n == 0 {
296 return Ok(b);
297 }
298 let (center, radius) = sphere::<7, CHECK>(
299 corners.len(),
300 PointSource {
301 p,
302 indices: Some(corners),
303 radii: None,
304 },
305 N == 1,
306 ctx,
307 )?;
308 b.center = center;
309 b.radius = radius;
310 let (mut axis, _) = sphere::<3, CHECK>(n, NormalSource(&normals[..n]), N == 1, ctx)?;
311 let len = ctx.sqrt(number::<CHECK>(dot(axis, axis))?);
312 let inv = if len == 0. { 0. } else { 1. / len };
313 for a in &mut axis {
314 *a *= inv;
315 }
316 let mut mindp = 1.;
317 ctx.tick(n * 2)?;
318 for normal in &normals[..n] {
319 let dp = dot([normal[0], normal[1], normal[2]], axis);
320 if dp < mindp {
321 mindp = dp;
322 }
323 }
324 if mindp <= 0.1 {
325 b.cone_cutoff = 1.;
326 b.cone_cutoff_s8 = 127;
327 return Ok(b);
328 }
329 let mut maxt = 0.;
330 for normal in &normals[..n] {
331 let nn = [normal[0], normal[1], normal[2]];
332 let dc = dot(center, nn) + normal[3];
333 let dn = dot(axis, nn);
334 let t = number::<CHECK>(dc / dn)?;
335 if t > maxt {
336 maxt = t;
337 }
338 }
339 for j in 0..3 {
340 b.cone_apex[j] = number::<CHECK>(center[j] - axis[j] * maxt)?;
341 b.cone_axis[j] = axis[j];
342 let v = axis[j].clamp(-1., 1.);
343 b.cone_axis_s8[j] = (v * 127. + if v >= 0. { 0.5 } else { -0.5 }) as i8;
344 }
345 b.cone_cutoff = ctx.sqrt(number::<CHECK>(1. - mindp * mindp)?);
346 let e0 = (b.cone_axis_s8[0] as f32 / 127. - axis[0]).abs();
347 let e1 = (b.cone_axis_s8[1] as f32 / 127. - axis[1]).abs();
348 let e2 = (b.cone_axis_s8[2] as f32 / 127. - axis[2]).abs();
349 b.cone_cutoff_s8 = ((127. * (b.cone_cutoff + e0 + e1 + e2) + 1.) as i32).min(127) as i8;
350 Ok(b)
351}
352pub fn compute_cluster_bounds(
362 indices: &[u32],
363 p: Positions<'_>,
364 workspace: &mut Workspace,
365) -> Result<Bounds, Error> {
366 let mut ctx = Context::new(workspace)?;
367 if indices.len() > 1536 {
368 return Err(Error::InvalidParameter);
369 }
370 if indices.len() <= 96 {
371 cluster_bounds::<96, 32>(indices, p, &mut ctx, None)
372 } else if indices.len() <= 384 {
373 cluster_bounds::<384, 128>(indices, p, &mut ctx, None)
374 } else {
375 cluster_bounds::<1536, 512>(indices, p, &mut ctx, None)
376 }
377}
378pub fn compute_cluster_bounds_with_positions(
387 indices: &[u32],
388 p: BoundsPositions<'_>,
389 workspace: &mut Workspace,
390) -> Result<Bounds, Error> {
391 let mut ctx = Context::new(workspace)?;
392 if indices.len() > 1536 {
393 return Err(Error::InvalidParameter);
394 }
395 if indices.len() <= 96 {
396 cluster_bounds_cached::<96, 32>(indices, p, &mut ctx)
397 } else if indices.len() <= 384 {
398 cluster_bounds_cached::<384, 128>(indices, p, &mut ctx)
399 } else {
400 cluster_bounds_cached::<1536, 512>(indices, p, &mut ctx)
401 }
402}
403fn cluster_bounds_cached<const M: usize, const N: usize>(
404 indices: &[u32],
405 p: BoundsPositions<'_>,
406 ctx: &mut Context<'_>,
407) -> Result<Bounds, Error> {
408 ctx.topology(indices, p.positions.len())?;
409 ctx.moderate = p.apply(ctx)?;
410 cluster_bounds_body::<M, N>(indices, p.positions, ctx)
411}
412fn cluster_bounds_body<const M: usize, const N: usize>(
413 indices: &[u32],
414 p: Positions<'_>,
415 ctx: &mut Context<'_>,
416) -> Result<Bounds, Error> {
417 let mut cache = [u32::MAX; 512];
418 let mut corners = [0u32; M];
419 let mut n = 0;
420 ctx.tick(indices.len())?;
421 for &v in indices {
422 let c = &mut cache[v as usize & 511];
423 if *c != v {
424 corners[n] = v;
425 n += 1;
426 }
427 *c = v;
428 }
429 if ctx.moderate {
430 bounds::<false, N>(indices, &corners[..n], p, ctx)
431 } else {
432 bounds::<true, N>(indices, &corners[..n], p, ctx)
433 }
434}
435#[cfg(feature = "clusterlod")]
436pub(crate) fn compute_cluster_bounds_validated(
437 indices: &[u32],
438 p: Positions<'_>,
439 moderate: bool,
440 workspace: &mut Workspace,
441) -> Result<Bounds, Error> {
442 let mut ctx = Context::new(workspace)?;
443 if indices.len() > 1536 {
444 return Err(Error::InvalidParameter);
445 }
446 if indices.len() <= 96 {
447 cluster_bounds::<96, 32>(indices, p, &mut ctx, Some(moderate))
448 } else if indices.len() <= 384 {
449 cluster_bounds::<384, 128>(indices, p, &mut ctx, Some(moderate))
450 } else {
451 cluster_bounds::<1536, 512>(indices, p, &mut ctx, Some(moderate))
452 }
453}
454fn cluster_bounds<const M: usize, const N: usize>(
455 indices: &[u32],
456 p: Positions<'_>,
457 ctx: &mut Context<'_>,
458 trusted_moderate: Option<bool>,
459) -> Result<Bounds, Error> {
460 ctx.topology(indices, p.len())?;
461 if let Some(moderate) = trusted_moderate {
462 ctx.moderate = moderate;
463 } else {
464 ctx.positions(p)?;
465 }
466 let mut cache = [u32::MAX; 512];
467 let mut corners = [0u32; M];
468 let mut n = 0;
469 ctx.tick(indices.len())?;
470 for &v in indices {
471 let c = &mut cache[v as usize & 511];
472 if *c != v {
473 corners[n] = v;
474 n += 1;
475 }
476 *c = v;
477 }
478 if ctx.moderate {
479 bounds::<false, N>(indices, &corners[..n], p, ctx)
480 } else {
481 bounds::<true, N>(indices, &corners[..n], p, ctx)
482 }
483}
484pub fn compute_meshlet_bounds(
494 vertices: &[u32],
495 triangles: &[u8],
496 p: Positions<'_>,
497 workspace: &mut Workspace,
498) -> Result<Bounds, Error> {
499 let mut ctx = Context::new(workspace)?;
500 validate_local(vertices, triangles)?;
501 if triangles.len() <= 96 {
502 meshlet_bounds::<96, 32>(vertices, triangles, p, &mut ctx)
503 } else if triangles.len() <= 384 {
504 meshlet_bounds::<384, 128>(vertices, triangles, p, &mut ctx)
505 } else {
506 meshlet_bounds::<1536, 512>(vertices, triangles, p, &mut ctx)
507 }
508}
509pub fn compute_meshlet_bounds_with_positions(
518 vertices: &[u32],
519 triangles: &[u8],
520 p: BoundsPositions<'_>,
521 workspace: &mut Workspace,
522) -> Result<Bounds, Error> {
523 let mut ctx = Context::new(workspace)?;
524 validate_local(vertices, triangles)?;
525 ctx.moderate = p.apply(&mut ctx)?;
526 if triangles.len() <= 3 {
527 meshlet_bounds_body::<3, 1>(vertices, triangles, p.positions, &mut ctx)
528 } else if triangles.len() <= 96 {
529 meshlet_bounds_body::<96, 32>(vertices, triangles, p.positions, &mut ctx)
530 } else if triangles.len() <= 384 {
531 meshlet_bounds_body::<384, 128>(vertices, triangles, p.positions, &mut ctx)
532 } else {
533 meshlet_bounds_body::<1536, 512>(vertices, triangles, p.positions, &mut ctx)
534 }
535}
536fn meshlet_bounds<const M: usize, const N: usize>(
537 vertices: &[u32],
538 triangles: &[u8],
539 p: Positions<'_>,
540 ctx: &mut Context<'_>,
541) -> Result<Bounds, Error> {
542 ctx.positions(p)?;
543 ctx.tick(vertices.len() + triangles.len())?;
544 if vertices.iter().any(|&v| v as usize >= p.len()) {
545 return Err(Error::IndexOutOfBounds);
546 }
547 let mut indices = [0u32; M];
548 let mut n = 0;
549 for (i, &v) in triangles.iter().enumerate() {
550 indices[i] = vertices[v as usize];
551 n = n.max(v as usize + 1);
552 }
553 if ctx.moderate {
554 bounds::<false, N>(&indices[..triangles.len()], &vertices[..n], p, ctx)
555 } else {
556 bounds::<true, N>(&indices[..triangles.len()], &vertices[..n], p, ctx)
557 }
558}
559fn meshlet_bounds_body<const M: usize, const N: usize>(
560 vertices: &[u32],
561 triangles: &[u8],
562 p: Positions<'_>,
563 ctx: &mut Context<'_>,
564) -> Result<Bounds, Error> {
565 ctx.tick(vertices.len() + triangles.len())?;
566 if vertices
567 .iter()
568 .copied()
569 .max()
570 .is_some_and(|v| v as usize >= p.len())
571 {
572 return Err(Error::IndexOutOfBounds);
573 }
574 if N == 1 {
575 let Some(triangle) = triangles.first_chunk::<3>() else {
576 return Ok(Bounds::default());
577 };
578 let indices = triangle.map(|v| vertices[v as usize]);
579 let n = triangle.iter().copied().max().unwrap() as usize + 1;
580 return meshlet_bounds_result::<N>(&indices, &vertices[..n], p, ctx);
581 }
582 let mut indices = [0u32; M];
583 let mut n = 0;
584 for (i, &v) in triangles.iter().enumerate() {
585 indices[i] = vertices[v as usize];
586 n = n.max(v as usize + 1);
587 }
588 meshlet_bounds_result::<N>(&indices[..triangles.len()], &vertices[..n], p, ctx)
589}
590#[inline(always)]
591fn meshlet_bounds_result<const N: usize>(
592 indices: &[u32],
593 corners: &[u32],
594 p: Positions<'_>,
595 ctx: &mut Context<'_>,
596) -> Result<Bounds, Error> {
597 if let Some(packed) = p.packed_values() {
598 if ctx.moderate {
599 bounds::<false, N>(indices, corners, packed, ctx)
600 } else {
601 bounds::<true, N>(indices, corners, packed, ctx)
602 }
603 } else if ctx.moderate {
604 bounds::<false, N>(indices, corners, p, ctx)
605 } else {
606 bounds::<true, N>(indices, corners, p, ctx)
607 }
608}
609pub fn compute_sphere_bounds(
616 p: Positions<'_>,
617 radii: Option<Attributes<'_>>,
618 workspace: &mut Workspace,
619) -> Result<Bounds, Error> {
620 let mut ctx = Context::new(workspace)?;
621 ctx.positions(p)?;
622 if let Some(r) = radii {
623 if r.len() != p.len() || r.components() != 1 {
624 return Err(Error::InvalidLayout);
625 }
626 ctx.tick(r.len())?;
627 for i in 0..r.len() {
628 let v = r.get(i, 0).ok_or(Error::InvalidLayout)?;
629 ctx.moderate &= v <= 1.0e8;
630 if !v.is_finite() || v < 0. {
631 return Err(Error::InvalidParameter);
632 }
633 }
634 }
635 let get = PointSource {
636 p,
637 indices: None,
638 radii,
639 };
640 let (center, radius) = if ctx.moderate {
641 sphere::<7, false>(p.len(), get, false, &mut ctx)?
642 } else {
643 sphere::<7, true>(p.len(), get, false, &mut ctx)?
644 };
645 Ok(Bounds {
646 center,
647 radius,
648 ..Bounds::default()
649 })
650}
651fn validate_local(v: &[u32], t: &[u8]) -> Result<(), Error> {
652 if !t.len().is_multiple_of(3) {
653 return Err(Error::InvalidTopology);
654 }
655 if v.len() > 256 || t.len() > 1536 {
656 return Err(Error::InvalidParameter);
657 }
658 if t.iter().any(|&i| i as usize >= v.len()) {
659 return Err(Error::IndexOutOfBounds);
660 }
661 Ok(())
662}
663fn extract<const V: usize, const T: usize>(
664 indices: &[u32],
665 vertices: &mut [u32; V],
666 triangles: &mut [u8; T],
667 ctx: &mut Context<'_>,
668) -> Result<usize, Error> {
669 if !indices.len().is_multiple_of(3) {
670 return Err(Error::InvalidTopology);
671 }
672 if indices.len() > 1536 {
673 return Err(Error::InvalidParameter);
674 }
675 let mut n = 0;
676 let mut cache = [-1i16; 1024];
677 ctx.tick(indices.len())?;
678 for (i, &v) in indices.iter().enumerate() {
679 let key = v as usize & 1023;
680 let c = cache[key];
681 if c >= 0 && vertices[c as u8 as usize] == v {
682 triangles[i] = c as u8;
683 continue;
684 }
685 let pos = if c < 0 {
686 n
687 } else {
688 ctx.tick(n)?;
689 vertices[..n].iter().position(|&x| x == v).unwrap_or(n)
690 };
691 if pos == n {
692 if n == 256 {
693 return Err(Error::InvalidParameter);
694 }
695 vertices[n] = v;
696 n += 1;
697 }
698 cache[key] = pos as i16;
699 triangles[i] = pos as u8;
700 }
701 Ok(n)
702}
703pub fn extract_meshlet_indices(
709 indices: &[u32],
710 workspace: &mut Workspace,
711) -> Result<LocalMeshlet, Error> {
712 let mut ctx = Context::new(workspace)?;
713 extracted(indices, &mut ctx, |v, t, ctx| {
714 Ok(LocalMeshlet {
715 vertices: ctx.copy(v)?,
716 triangles: ctx.copy(t)?,
717 })
718 })
719}
720#[inline(always)]
724fn extracted<R>(
725 indices: &[u32],
726 ctx: &mut Context<'_>,
727 finish: impl FnOnce(&[u32], &[u8], &mut Context<'_>) -> Result<R, Error>,
728) -> Result<R, Error> {
729 if indices.len() <= 96 {
730 let (mut v, mut t) = ([0; 96], [0; 96]);
731 let n = extract(indices, &mut v, &mut t, ctx)?;
732 finish(&v[..n], &t[..indices.len()], ctx)
733 } else if indices.len() <= 384 {
734 let (mut v, mut t) = ([0; 256], [0; 384]);
735 let n = extract(indices, &mut v, &mut t, ctx)?;
736 finish(&v[..n], &t[..indices.len()], ctx)
737 } else {
738 let (mut v, mut t) = ([0; 256], [0; 1536]);
739 let n = extract(indices, &mut v, &mut t, ctx)?;
740 finish(&v[..n], &t[..indices.len()], ctx)
741 }
742}
743pub fn extract_meshlet_indices_into(
748 vertices: &mut [u32],
749 triangles: &mut [u8],
750 indices: &[u32],
751 workspace: &mut Workspace,
752) -> Result<usize, Error> {
753 let mut ctx = Context::new(workspace)?;
754 if triangles.len() < indices.len() {
755 return Err(Error::BufferTooSmall);
756 }
757 extracted(indices, &mut ctx, |v, t, _| {
758 if vertices.len() < v.len() {
759 return Err(Error::BufferTooSmall);
760 }
761 vertices[..v.len()].copy_from_slice(v);
762 triangles[..t.len()].copy_from_slice(t);
763 Ok(v.len())
764 })
765}
766fn optimize(v: &mut [u32], t: &mut [u8], level: u8, ctx: &mut Context<'_>) -> Result<(), Error> {
768 if level > 9 {
769 return Err(Error::InvalidParameter);
770 }
771 if level == 0 {
772 optimize_body::<false>(v, t, level, ctx)
773 } else {
774 optimize_body::<true>(v, t, level, ctx)
775 }
776}
777fn optimize_body<const ADVANCED: bool>(
778 v: &mut [u32],
779 t: &mut [u8],
780 level: u8,
781 ctx: &mut Context<'_>,
782) -> Result<(), Error> {
783 let n = t.len() / 3;
784 if n <= 1 {
787 ctx.tick(t.len())?;
788 if n == 1 {
789 ctx.tick(1)?;
790 ctx.tick(1)?;
791 if ADVANCED {
792 ctx.tick(1)?;
793 }
794 }
795 ctx.tick(t.len())?;
796 let mut source = [0u8; 3];
797 let mut order = [0u32; 3];
798 let mut count = 0;
799 for x in t {
800 let local = match source[..count].iter().position(|&i| i == *x) {
801 Some(local) => local,
802 None => {
803 source[count] = *x;
804 order[count] = v[*x as usize];
805 count += 1;
806 count - 1
807 }
808 };
809 *x = local as u8;
810 }
811 v[..count].copy_from_slice(&order[..count]);
812 return Ok(());
813 }
814 let mut cache = [0u8; 256];
815 let mut last = 128u8;
816 let mut valence = [0u8; 256];
817 ctx.tick(t.len())?;
818 for &i in t.iter() {
819 valence[i as usize] = valence[i as usize].wrapping_add(1);
820 }
821 for i in 0..n {
822 let mut next = i;
823 let mut best = -1;
824 let mut edges = 0;
825 ctx.search(
826 t.as_chunks::<3>().0[i..].iter().enumerate(),
827 |(offset, tri)| {
828 let (a, b, c) = (tri[0] as usize, tri[1] as usize, tri[2] as usize);
829 let (ad, bd, cd) = (
830 last.wrapping_sub(cache[a]),
831 last.wrapping_sub(cache[b]),
832 last.wrapping_sub(cache[c]),
833 );
834 let matches = i32::from(ad < 3) + i32::from(bd < 3) + i32::from(cd < 3);
835 let score = if ADVANCED {
836 (matches * 1024 + (1023 - ad as i32 - bd as i32 - cd as i32)) * 256
837 + (255 - valence[a].min(valence[b]).min(valence[c]) as i32)
838 } else {
839 matches
840 };
841 if score > best {
842 best = score;
843 next = i + offset;
844 }
845 if matches >= 2 {
846 edges += 1;
847 if !ADVANCED || edges >= level {
848 return true;
849 }
850 }
851 false
852 },
853 )?;
854 ctx.tick(next - i + 1)?;
855 let tri = [t[next * 3], t[next * 3 + 1], t[next * 3 + 2]];
856 t.copy_within(i * 3..next * 3, (i + 1) * 3);
857 t[i * 3..i * 3 + 3].copy_from_slice(&tri);
858 last = last.wrapping_add(1);
859 for x in tri {
860 cache[x as usize] = last;
861 valence[x as usize] = valence[x as usize].wrapping_sub(1);
862 }
863 }
864 if ADVANCED {
865 cache.fill(0);
866 for i in 0..n {
867 ctx.tick(1)?;
868 let mut tri = [t[i * 3], t[i * 3 + 1], t[i * 3 + 2]];
869 let [a, b, c] = tri;
870 if cache[a as usize] == 0 && cache[b as usize] != 0 && cache[c as usize] == 0 {
871 tri.rotate_left(1);
872 } else if cache[a as usize] == 0 && cache[b as usize] == 0 && cache[c as usize] == 0 {
873 let (mut ab, mut bc, mut ca) = (false, false, false);
874 for j in i + 1..n.min(i + 4) {
875 ctx.tick(1)?;
876 let [oa, ob, oc] = [t[j * 3], t[j * 3 + 1], t[j * 3 + 2]];
877 ab |= (oa == b && ob == a) || (ob == b && oc == a) || (oc == b && oa == a);
878 bc |= (oa == c && ob == b) || (ob == c && oc == b) || (oc == c && oa == b);
879 ca |= (oa == a && ob == c) || (ob == a && oc == c) || (oc == a && oa == c);
880 }
881 if ab && !bc {
882 tri.rotate_left(1);
883 } else if (ab && !ca) || (!ab && bc && !ca) {
884 tri.rotate_right(1);
885 }
886 }
887 t[i * 3..i * 3 + 3].copy_from_slice(&tri);
888 for x in tri {
889 cache[x as usize] = 1;
890 }
891 }
892 }
893 let mut remap = [-1i16; 256];
894 let mut order = [0u32; 256];
895 let mut count = 0;
896 ctx.tick(t.len())?;
897 for x in t {
898 let r = &mut remap[*x as usize];
899 if *r < 0 {
900 *r = count as i16;
901 order[count] = v[*x as usize];
902 count += 1;
903 }
904 *x = *r as u8;
905 }
906 v[..count].copy_from_slice(&order[..count]);
907 Ok(())
908}
909pub fn optimize_meshlet_level_in_place(
915 vertices: &mut [u32],
916 triangles: &mut [u8],
917 level: u8,
918 workspace: &mut Workspace,
919) -> Result<(), Error> {
920 let mut ctx = Context::new(workspace)?;
921 validate_local(vertices, triangles)?;
922 let mut v = [0; 256];
923 let mut t = [0; 1536];
924 v[..vertices.len()].copy_from_slice(vertices);
925 t[..triangles.len()].copy_from_slice(triangles);
926 optimize(
927 &mut v[..vertices.len()],
928 &mut t[..triangles.len()],
929 level,
930 &mut ctx,
931 )?;
932 vertices.copy_from_slice(&v[..vertices.len()]);
933 triangles.copy_from_slice(&t[..triangles.len()]);
934 Ok(())
935}
936pub fn optimize_meshlet_in_place(
941 vertices: &mut [u32],
942 triangles: &mut [u8],
943 workspace: &mut Workspace,
944) -> Result<(), Error> {
945 optimize_meshlet_level_in_place(vertices, triangles, 0, workspace)
946}
947pub fn optimize_meshlet_level(
952 vertices: &[u32],
953 triangles: &[u8],
954 level: u8,
955 workspace: &mut Workspace,
956) -> Result<LocalMeshlet, Error> {
957 let mut ctx = Context::new(workspace)?;
958 validate_local(vertices, triangles)?;
959 let mut v = ctx.copy(vertices)?;
960 let mut t = ctx.copy(triangles)?;
961 optimize(&mut v, &mut t, level, &mut ctx)?;
962 Ok(LocalMeshlet {
963 vertices: v,
964 triangles: t,
965 })
966}
967pub fn optimize_meshlet(
972 vertices: &[u32],
973 triangles: &[u8],
974 workspace: &mut Workspace,
975) -> Result<LocalMeshlet, Error> {
976 optimize_meshlet_level(vertices, triangles, 0, workspace)
977}
978
979pub fn optimize_meshlet_level_into(
985 out_vertices: &mut [u32],
986 out_triangles: &mut [u8],
987 vertices: &[u32],
988 triangles: &[u8],
989 level: u8,
990 workspace: &mut Workspace,
991) -> Result<(), Error> {
992 let mut ctx = Context::new(workspace)?;
993 if out_vertices.len() < vertices.len() || out_triangles.len() < triangles.len() {
994 return Err(Error::BufferTooSmall);
995 }
996 validate_local(vertices, triangles)?;
997 let mut v = [0; 256];
998 let mut t = [0; 1536];
999 v[..vertices.len()].copy_from_slice(vertices);
1000 t[..triangles.len()].copy_from_slice(triangles);
1001 optimize(
1002 &mut v[..vertices.len()],
1003 &mut t[..triangles.len()],
1004 level,
1005 &mut ctx,
1006 )?;
1007 out_vertices[..vertices.len()].copy_from_slice(&v[..vertices.len()]);
1008 out_triangles[..triangles.len()].copy_from_slice(&t[..triangles.len()]);
1009 Ok(())
1010}
1011pub fn optimize_meshlet_into(
1016 out_vertices: &mut [u32],
1017 out_triangles: &mut [u8],
1018 vertices: &[u32],
1019 triangles: &[u8],
1020 workspace: &mut Workspace,
1021) -> Result<(), Error> {
1022 optimize_meshlet_level_into(
1023 out_vertices,
1024 out_triangles,
1025 vertices,
1026 triangles,
1027 0,
1028 workspace,
1029 )
1030}
1031
1032#[cfg(test)]
1033mod bounds_root_tests {
1034 use super::{bounds_roots, sqrt8, LANES};
1035
1036 #[test]
1037 fn used_roots_match_full_lanes_bit_for_bit() {
1038 let mut state = 0x1357_2468u32;
1039 let special = [
1040 0,
1041 1,
1042 0x007f_ffff,
1043 0x0080_0000,
1044 0x3f80_0000,
1045 0x7f7f_ffff,
1046 0x8000_0000,
1047 0xbf80_0000,
1048 0x7f80_0000,
1049 0x7fc0_1234,
1050 ];
1051 for sample in 0..512 {
1052 for used in 1..=LANES {
1053 let mut values = [1.; LANES];
1054 for value in &mut values[..used] {
1055 state = state.wrapping_mul(1664525).wrapping_add(1013904223);
1056 let bits = if sample < special.len() {
1057 special[sample]
1058 } else if sample.is_multiple_of(2) {
1059 0x0080_0000 + state % 0x7f00_0000
1060 } else {
1061 state
1062 };
1063 *value = f32::from_bits(bits);
1064 }
1065 assert_eq!(
1066 bounds_roots(values, used).map(f32::to_bits),
1067 sqrt8(values).map(f32::to_bits)
1068 );
1069 }
1070 }
1071 }
1072}