use crate::math::{sqrt8, LANES};
use crate::processing::{cross, dot, finite, point, sub, Context};
use crate::{Attributes, Error, Positions, Workspace};
use alloc::vec::Vec;
#[derive(Clone, Copy, Debug)]
pub struct BoundsPositions<'a> {
positions: Positions<'a>,
validation: Result<bool, Error>,
}
impl<'a> BoundsPositions<'a> {
pub fn new(positions: Positions<'a>) -> Self {
Self {
positions,
validation: crate::processing::validate_positions(positions),
}
}
fn apply(self, ctx: &mut Context<'_>) -> Result<bool, Error> {
if self.positions.len() > u32::MAX as usize {
return Err(Error::SizeOverflow);
}
ctx.tick(self.positions.len())?;
self.validation
}
}
#[derive(Clone, Copy, Debug, Default, PartialEq)]
pub struct Bounds {
pub center: [f32; 3],
pub radius: f32,
pub cone_apex: [f32; 3],
pub cone_axis: [f32; 3],
pub cone_cutoff: f32,
pub cone_axis_s8: [i8; 3],
pub cone_cutoff_s8: i8,
}
#[derive(Debug, Default, PartialEq, Eq)]
pub struct LocalMeshlet {
pub vertices: Vec<u32>,
pub triangles: Vec<u8>,
}
#[inline(always)]
fn number<const CHECK: bool>(value: f32) -> Result<f32, Error> {
if CHECK {
finite(value)
} else {
Ok(value)
}
}
trait SphereSource {
fn sample(&self, index: usize) -> ([f32; 3], f32);
}
trait BoundsSource: Copy {
fn point(self, index: u32) -> [f32; 3];
}
impl BoundsSource for Positions<'_> {
#[inline(always)]
fn point(self, index: u32) -> [f32; 3] {
point(self, index)
}
}
impl BoundsSource for &[[f32; 3]] {
#[inline(always)]
fn point(self, index: u32) -> [f32; 3] {
self[index as usize]
}
}
struct PointSource<'a, P = Positions<'a>> {
p: P,
indices: Option<&'a [u32]>,
radii: Option<Attributes<'a>>,
}
impl<P: BoundsSource> SphereSource for PointSource<'_, P> {
#[inline(always)]
fn sample(&self, index: usize) -> ([f32; 3], f32) {
let v = self.indices.map_or(index as u32, |i| i[index]);
(
self.p.point(v),
self.radii
.map_or(0., |r| r.get(v as usize, 0).expect("validated radius")),
)
}
}
struct NormalSource<'a>(&'a [[f32; 4]]);
impl SphereSource for NormalSource<'_> {
#[inline(always)]
fn sample(&self, index: usize) -> ([f32; 3], f32) {
let p = self.0[index];
([p[0], p[1], p[2]], 0.)
}
}
#[inline(always)]
fn bounds_roots(values: [f32; LANES], used: usize) -> [f32; LANES] {
if used < LANES
&& values[..used]
.iter()
.any(|v| v.to_bits().wrapping_sub(0x0080_0000) >= 0x7f00_0000)
{
let mut result = [1.; LANES];
for i in 0..used {
result[i] = crate::math::sqrt(values[i]);
}
result
} else {
sqrt8(values)
}
}
#[inline(always)]
fn sphere<const A: usize, const CHECK: bool>(
count: usize,
get: impl SphereSource,
skip_padding: bool,
ctx: &mut Context<'_>,
) -> Result<([f32; 3], f32), Error> {
if count == 0 {
return Ok(([0.0; 3], 0.0));
}
let axes = [
[1., 0., 0.],
[0., 1., 0.],
[0., 0., 1.],
[0.57735026; 3],
[-0.57735026, 0.57735026, 0.57735026],
[0.57735026, -0.57735026, 0.57735026],
[0.57735026, 0.57735026, -0.57735026],
];
let mut pmin = [0u32; 7];
let mut pmax = [0u32; 7];
let mut tmin = [f32::MAX; 7];
let mut tmax = [-f32::MAX; 7];
ctx.tick(count * 2)?;
for i in 0..count {
let (p, r) = get.sample(i);
for k in 0..A {
let tp = number::<CHECK>(dot(axes[k], p))?;
let lo = number::<CHECK>(tp - r)?;
let hi = number::<CHECK>(tp + r)?;
let lower = lo < tmin[k];
let upper = hi > tmax[k];
pmin[k] = if lower { i as u32 } else { pmin[k] };
pmax[k] = if upper { i as u32 } else { pmax[k] };
tmin[k] = if lower { lo } else { tmin[k] };
tmax[k] = if upper { hi } else { tmax[k] };
}
}
let mut squares = [1f32; LANES];
for k in 0..A {
let (a, _) = get.sample(pmin[k] as usize);
let (b, _) = get.sample(pmax[k] as usize);
let d = sub(b, a);
squares[k] = number::<CHECK>(dot(d, d))?;
}
let lengths = if skip_padding {
bounds_roots(squares, A)
} else {
sqrt8(squares)
};
let mut axis = 0;
let mut dr = 0.;
for k in 0..A {
let (_, ar) = get.sample(pmin[k] as usize);
let (_, br) = get.sample(pmax[k] as usize);
let v = number::<CHECK>(lengths[k] + ar + br)?;
if v > dr {
dr = v;
axis = k;
}
}
let (a, ar) = get.sample(pmin[axis] as usize);
let (b, br) = get.sample(pmax[axis] as usize);
let delta = sub(b, a);
let d = lengths[axis];
let k = if d > 0. { (d + br - ar) / (2. * d) } else { 0. };
let mut center = [
a[0] + delta[0] * k,
a[1] + delta[1] * k,
a[2] + delta[2] * k,
];
let mut radius = dr / 2.;
for i in 0..count {
let (p, r) = get.sample(i);
let dp = sub(p, center);
let d2 = number::<CHECK>(dot(dp, dp))?;
let limit = radius - r;
if limit >= 1.0e-18 {
let lower = f32::from_bits(limit.to_bits() - 1);
if d2 <= lower * lower {
continue;
}
}
let d = ctx.sqrt(d2);
if d + r > radius {
let k = if d > 0. {
(d + r - radius) / (2. * d)
} else {
0.
};
for j in 0..3 {
center[j] += k * (p[j] - center[j]);
}
radius = (radius + d + r) / 2.;
}
}
for v in center {
number::<CHECK>(v)?;
}
number::<CHECK>(radius)?;
Ok((center, radius))
}
fn bounds<const CHECK: bool, const N: usize>(
indices: &[u32],
corners: &[u32],
p: impl BoundsSource,
ctx: &mut Context<'_>,
) -> Result<Bounds, Error> {
let mut normals = [[0f32; 4]; N];
let mut n = 0;
ctx.tick(indices.len() / 3)?;
for group in indices.as_chunks::<3>().0.chunks(LANES) {
let mut corners = [[0f32; 3]; LANES];
let mut normals_raw = [[0f32; 3]; LANES];
let mut squares = [1f32; LANES];
for (k, t) in group.iter().enumerate() {
let a = p.point(t[0]);
let normal = cross(sub(p.point(t[1]), a), sub(p.point(t[2]), a));
squares[k] = number::<CHECK>(dot(normal, normal))?;
corners[k] = a;
normals_raw[k] = normal;
}
let areas = if N == 1 && group.len() == 1 {
bounds_roots(squares, 1)
} else {
sqrt8(squares)
};
for k in 0..group.len() {
let area = areas[k];
if area == 0. {
continue;
}
let mut normal = normals_raw[k];
for v in &mut normal {
*v /= area;
}
normals[n] = [
normal[0],
normal[1],
normal[2],
-number::<CHECK>(dot(normal, corners[k]))?,
];
n += 1;
}
}
let mut b = Bounds::default();
if n == 0 {
return Ok(b);
}
let (center, radius) = sphere::<7, CHECK>(
corners.len(),
PointSource {
p,
indices: Some(corners),
radii: None,
},
N == 1,
ctx,
)?;
b.center = center;
b.radius = radius;
let (mut axis, _) = sphere::<3, CHECK>(n, NormalSource(&normals[..n]), N == 1, ctx)?;
let len = ctx.sqrt(number::<CHECK>(dot(axis, axis))?);
let inv = if len == 0. { 0. } else { 1. / len };
for a in &mut axis {
*a *= inv;
}
let mut mindp = 1.;
ctx.tick(n * 2)?;
for normal in &normals[..n] {
let dp = dot([normal[0], normal[1], normal[2]], axis);
if dp < mindp {
mindp = dp;
}
}
if mindp <= 0.1 {
b.cone_cutoff = 1.;
b.cone_cutoff_s8 = 127;
return Ok(b);
}
let mut maxt = 0.;
for normal in &normals[..n] {
let nn = [normal[0], normal[1], normal[2]];
let dc = dot(center, nn) + normal[3];
let dn = dot(axis, nn);
let t = number::<CHECK>(dc / dn)?;
if t > maxt {
maxt = t;
}
}
for j in 0..3 {
b.cone_apex[j] = number::<CHECK>(center[j] - axis[j] * maxt)?;
b.cone_axis[j] = axis[j];
let v = axis[j].clamp(-1., 1.);
b.cone_axis_s8[j] = (v * 127. + if v >= 0. { 0.5 } else { -0.5 }) as i8;
}
b.cone_cutoff = ctx.sqrt(number::<CHECK>(1. - mindp * mindp)?);
let e0 = (b.cone_axis_s8[0] as f32 / 127. - axis[0]).abs();
let e1 = (b.cone_axis_s8[1] as f32 / 127. - axis[1]).abs();
let e2 = (b.cone_axis_s8[2] as f32 / 127. - axis[2]).abs();
b.cone_cutoff_s8 = ((127. * (b.cone_cutoff + e0 + e1 + e2) + 1.) as i32).min(127) as i8;
Ok(b)
}
pub fn compute_cluster_bounds(
indices: &[u32],
p: Positions<'_>,
workspace: &mut Workspace,
) -> Result<Bounds, Error> {
let mut ctx = Context::new(workspace)?;
if indices.len() > 1536 {
return Err(Error::InvalidParameter);
}
if indices.len() <= 96 {
cluster_bounds::<96, 32>(indices, p, &mut ctx, None)
} else if indices.len() <= 384 {
cluster_bounds::<384, 128>(indices, p, &mut ctx, None)
} else {
cluster_bounds::<1536, 512>(indices, p, &mut ctx, None)
}
}
pub fn compute_cluster_bounds_with_positions(
indices: &[u32],
p: BoundsPositions<'_>,
workspace: &mut Workspace,
) -> Result<Bounds, Error> {
let mut ctx = Context::new(workspace)?;
if indices.len() > 1536 {
return Err(Error::InvalidParameter);
}
if indices.len() <= 96 {
cluster_bounds_cached::<96, 32>(indices, p, &mut ctx)
} else if indices.len() <= 384 {
cluster_bounds_cached::<384, 128>(indices, p, &mut ctx)
} else {
cluster_bounds_cached::<1536, 512>(indices, p, &mut ctx)
}
}
fn cluster_bounds_cached<const M: usize, const N: usize>(
indices: &[u32],
p: BoundsPositions<'_>,
ctx: &mut Context<'_>,
) -> Result<Bounds, Error> {
ctx.topology(indices, p.positions.len())?;
ctx.moderate = p.apply(ctx)?;
cluster_bounds_body::<M, N>(indices, p.positions, ctx)
}
fn cluster_bounds_body<const M: usize, const N: usize>(
indices: &[u32],
p: Positions<'_>,
ctx: &mut Context<'_>,
) -> Result<Bounds, Error> {
let mut cache = [u32::MAX; 512];
let mut corners = [0u32; M];
let mut n = 0;
ctx.tick(indices.len())?;
for &v in indices {
let c = &mut cache[v as usize & 511];
if *c != v {
corners[n] = v;
n += 1;
}
*c = v;
}
if ctx.moderate {
bounds::<false, N>(indices, &corners[..n], p, ctx)
} else {
bounds::<true, N>(indices, &corners[..n], p, ctx)
}
}
#[cfg(feature = "clusterlod")]
pub(crate) fn compute_cluster_bounds_validated(
indices: &[u32],
p: Positions<'_>,
moderate: bool,
workspace: &mut Workspace,
) -> Result<Bounds, Error> {
let mut ctx = Context::new(workspace)?;
if indices.len() > 1536 {
return Err(Error::InvalidParameter);
}
if indices.len() <= 96 {
cluster_bounds::<96, 32>(indices, p, &mut ctx, Some(moderate))
} else if indices.len() <= 384 {
cluster_bounds::<384, 128>(indices, p, &mut ctx, Some(moderate))
} else {
cluster_bounds::<1536, 512>(indices, p, &mut ctx, Some(moderate))
}
}
fn cluster_bounds<const M: usize, const N: usize>(
indices: &[u32],
p: Positions<'_>,
ctx: &mut Context<'_>,
trusted_moderate: Option<bool>,
) -> Result<Bounds, Error> {
ctx.topology(indices, p.len())?;
if let Some(moderate) = trusted_moderate {
ctx.moderate = moderate;
} else {
ctx.positions(p)?;
}
let mut cache = [u32::MAX; 512];
let mut corners = [0u32; M];
let mut n = 0;
ctx.tick(indices.len())?;
for &v in indices {
let c = &mut cache[v as usize & 511];
if *c != v {
corners[n] = v;
n += 1;
}
*c = v;
}
if ctx.moderate {
bounds::<false, N>(indices, &corners[..n], p, ctx)
} else {
bounds::<true, N>(indices, &corners[..n], p, ctx)
}
}
pub fn compute_meshlet_bounds(
vertices: &[u32],
triangles: &[u8],
p: Positions<'_>,
workspace: &mut Workspace,
) -> Result<Bounds, Error> {
let mut ctx = Context::new(workspace)?;
validate_local(vertices, triangles)?;
if triangles.len() <= 96 {
meshlet_bounds::<96, 32>(vertices, triangles, p, &mut ctx)
} else if triangles.len() <= 384 {
meshlet_bounds::<384, 128>(vertices, triangles, p, &mut ctx)
} else {
meshlet_bounds::<1536, 512>(vertices, triangles, p, &mut ctx)
}
}
pub fn compute_meshlet_bounds_with_positions(
vertices: &[u32],
triangles: &[u8],
p: BoundsPositions<'_>,
workspace: &mut Workspace,
) -> Result<Bounds, Error> {
let mut ctx = Context::new(workspace)?;
validate_local(vertices, triangles)?;
ctx.moderate = p.apply(&mut ctx)?;
if triangles.len() <= 3 {
meshlet_bounds_body::<3, 1>(vertices, triangles, p.positions, &mut ctx)
} else if triangles.len() <= 96 {
meshlet_bounds_body::<96, 32>(vertices, triangles, p.positions, &mut ctx)
} else if triangles.len() <= 384 {
meshlet_bounds_body::<384, 128>(vertices, triangles, p.positions, &mut ctx)
} else {
meshlet_bounds_body::<1536, 512>(vertices, triangles, p.positions, &mut ctx)
}
}
fn meshlet_bounds<const M: usize, const N: usize>(
vertices: &[u32],
triangles: &[u8],
p: Positions<'_>,
ctx: &mut Context<'_>,
) -> Result<Bounds, Error> {
ctx.positions(p)?;
ctx.tick(vertices.len() + triangles.len())?;
if vertices.iter().any(|&v| v as usize >= p.len()) {
return Err(Error::IndexOutOfBounds);
}
let mut indices = [0u32; M];
let mut n = 0;
for (i, &v) in triangles.iter().enumerate() {
indices[i] = vertices[v as usize];
n = n.max(v as usize + 1);
}
if ctx.moderate {
bounds::<false, N>(&indices[..triangles.len()], &vertices[..n], p, ctx)
} else {
bounds::<true, N>(&indices[..triangles.len()], &vertices[..n], p, ctx)
}
}
fn meshlet_bounds_body<const M: usize, const N: usize>(
vertices: &[u32],
triangles: &[u8],
p: Positions<'_>,
ctx: &mut Context<'_>,
) -> Result<Bounds, Error> {
ctx.tick(vertices.len() + triangles.len())?;
if vertices
.iter()
.copied()
.max()
.is_some_and(|v| v as usize >= p.len())
{
return Err(Error::IndexOutOfBounds);
}
if N == 1 {
let Some(triangle) = triangles.first_chunk::<3>() else {
return Ok(Bounds::default());
};
let indices = triangle.map(|v| vertices[v as usize]);
let n = triangle.iter().copied().max().unwrap() as usize + 1;
return meshlet_bounds_result::<N>(&indices, &vertices[..n], p, ctx);
}
let mut indices = [0u32; M];
let mut n = 0;
for (i, &v) in triangles.iter().enumerate() {
indices[i] = vertices[v as usize];
n = n.max(v as usize + 1);
}
meshlet_bounds_result::<N>(&indices[..triangles.len()], &vertices[..n], p, ctx)
}
#[inline(always)]
fn meshlet_bounds_result<const N: usize>(
indices: &[u32],
corners: &[u32],
p: Positions<'_>,
ctx: &mut Context<'_>,
) -> Result<Bounds, Error> {
if let Some(packed) = p.packed_values() {
if ctx.moderate {
bounds::<false, N>(indices, corners, packed, ctx)
} else {
bounds::<true, N>(indices, corners, packed, ctx)
}
} else if ctx.moderate {
bounds::<false, N>(indices, corners, p, ctx)
} else {
bounds::<true, N>(indices, corners, p, ctx)
}
}
pub fn compute_sphere_bounds(
p: Positions<'_>,
radii: Option<Attributes<'_>>,
workspace: &mut Workspace,
) -> Result<Bounds, Error> {
let mut ctx = Context::new(workspace)?;
ctx.positions(p)?;
if let Some(r) = radii {
if r.len() != p.len() || r.components() != 1 {
return Err(Error::InvalidLayout);
}
ctx.tick(r.len())?;
for i in 0..r.len() {
let v = r.get(i, 0).ok_or(Error::InvalidLayout)?;
ctx.moderate &= v <= 1.0e8;
if !v.is_finite() || v < 0. {
return Err(Error::InvalidParameter);
}
}
}
let get = PointSource {
p,
indices: None,
radii,
};
let (center, radius) = if ctx.moderate {
sphere::<7, false>(p.len(), get, false, &mut ctx)?
} else {
sphere::<7, true>(p.len(), get, false, &mut ctx)?
};
Ok(Bounds {
center,
radius,
..Bounds::default()
})
}
fn validate_local(v: &[u32], t: &[u8]) -> Result<(), Error> {
if !t.len().is_multiple_of(3) {
return Err(Error::InvalidTopology);
}
if v.len() > 256 || t.len() > 1536 {
return Err(Error::InvalidParameter);
}
if t.iter().any(|&i| i as usize >= v.len()) {
return Err(Error::IndexOutOfBounds);
}
Ok(())
}
fn extract<const V: usize, const T: usize>(
indices: &[u32],
vertices: &mut [u32; V],
triangles: &mut [u8; T],
ctx: &mut Context<'_>,
) -> Result<usize, Error> {
if !indices.len().is_multiple_of(3) {
return Err(Error::InvalidTopology);
}
if indices.len() > 1536 {
return Err(Error::InvalidParameter);
}
let mut n = 0;
let mut cache = [-1i16; 1024];
ctx.tick(indices.len())?;
for (i, &v) in indices.iter().enumerate() {
let key = v as usize & 1023;
let c = cache[key];
if c >= 0 && vertices[c as u8 as usize] == v {
triangles[i] = c as u8;
continue;
}
let pos = if c < 0 {
n
} else {
ctx.tick(n)?;
vertices[..n].iter().position(|&x| x == v).unwrap_or(n)
};
if pos == n {
if n == 256 {
return Err(Error::InvalidParameter);
}
vertices[n] = v;
n += 1;
}
cache[key] = pos as i16;
triangles[i] = pos as u8;
}
Ok(n)
}
pub fn extract_meshlet_indices(
indices: &[u32],
workspace: &mut Workspace,
) -> Result<LocalMeshlet, Error> {
let mut ctx = Context::new(workspace)?;
extracted(indices, &mut ctx, |v, t, ctx| {
Ok(LocalMeshlet {
vertices: ctx.copy(v)?,
triangles: ctx.copy(t)?,
})
})
}
#[inline(always)]
fn extracted<R>(
indices: &[u32],
ctx: &mut Context<'_>,
finish: impl FnOnce(&[u32], &[u8], &mut Context<'_>) -> Result<R, Error>,
) -> Result<R, Error> {
if indices.len() <= 96 {
let (mut v, mut t) = ([0; 96], [0; 96]);
let n = extract(indices, &mut v, &mut t, ctx)?;
finish(&v[..n], &t[..indices.len()], ctx)
} else if indices.len() <= 384 {
let (mut v, mut t) = ([0; 256], [0; 384]);
let n = extract(indices, &mut v, &mut t, ctx)?;
finish(&v[..n], &t[..indices.len()], ctx)
} else {
let (mut v, mut t) = ([0; 256], [0; 1536]);
let n = extract(indices, &mut v, &mut t, ctx)?;
finish(&v[..n], &t[..indices.len()], ctx)
}
}
pub fn extract_meshlet_indices_into(
vertices: &mut [u32],
triangles: &mut [u8],
indices: &[u32],
workspace: &mut Workspace,
) -> Result<usize, Error> {
let mut ctx = Context::new(workspace)?;
if triangles.len() < indices.len() {
return Err(Error::BufferTooSmall);
}
extracted(indices, &mut ctx, |v, t, _| {
if vertices.len() < v.len() {
return Err(Error::BufferTooSmall);
}
vertices[..v.len()].copy_from_slice(v);
triangles[..t.len()].copy_from_slice(t);
Ok(v.len())
})
}
fn optimize(v: &mut [u32], t: &mut [u8], level: u8, ctx: &mut Context<'_>) -> Result<(), Error> {
if level > 9 {
return Err(Error::InvalidParameter);
}
if level == 0 {
optimize_body::<false>(v, t, level, ctx)
} else {
optimize_body::<true>(v, t, level, ctx)
}
}
fn optimize_body<const ADVANCED: bool>(
v: &mut [u32],
t: &mut [u8],
level: u8,
ctx: &mut Context<'_>,
) -> Result<(), Error> {
let n = t.len() / 3;
if n <= 1 {
ctx.tick(t.len())?;
if n == 1 {
ctx.tick(1)?;
ctx.tick(1)?;
if ADVANCED {
ctx.tick(1)?;
}
}
ctx.tick(t.len())?;
let mut source = [0u8; 3];
let mut order = [0u32; 3];
let mut count = 0;
for x in t {
let local = match source[..count].iter().position(|&i| i == *x) {
Some(local) => local,
None => {
source[count] = *x;
order[count] = v[*x as usize];
count += 1;
count - 1
}
};
*x = local as u8;
}
v[..count].copy_from_slice(&order[..count]);
return Ok(());
}
let mut cache = [0u8; 256];
let mut last = 128u8;
let mut valence = [0u8; 256];
ctx.tick(t.len())?;
for &i in t.iter() {
valence[i as usize] = valence[i as usize].wrapping_add(1);
}
for i in 0..n {
let mut next = i;
let mut best = -1;
let mut edges = 0;
ctx.search(
t.as_chunks::<3>().0[i..].iter().enumerate(),
|(offset, tri)| {
let (a, b, c) = (tri[0] as usize, tri[1] as usize, tri[2] as usize);
let (ad, bd, cd) = (
last.wrapping_sub(cache[a]),
last.wrapping_sub(cache[b]),
last.wrapping_sub(cache[c]),
);
let matches = i32::from(ad < 3) + i32::from(bd < 3) + i32::from(cd < 3);
let score = if ADVANCED {
(matches * 1024 + (1023 - ad as i32 - bd as i32 - cd as i32)) * 256
+ (255 - valence[a].min(valence[b]).min(valence[c]) as i32)
} else {
matches
};
if score > best {
best = score;
next = i + offset;
}
if matches >= 2 {
edges += 1;
if !ADVANCED || edges >= level {
return true;
}
}
false
},
)?;
ctx.tick(next - i + 1)?;
let tri = [t[next * 3], t[next * 3 + 1], t[next * 3 + 2]];
t.copy_within(i * 3..next * 3, (i + 1) * 3);
t[i * 3..i * 3 + 3].copy_from_slice(&tri);
last = last.wrapping_add(1);
for x in tri {
cache[x as usize] = last;
valence[x as usize] = valence[x as usize].wrapping_sub(1);
}
}
if ADVANCED {
cache.fill(0);
for i in 0..n {
ctx.tick(1)?;
let mut tri = [t[i * 3], t[i * 3 + 1], t[i * 3 + 2]];
let [a, b, c] = tri;
if cache[a as usize] == 0 && cache[b as usize] != 0 && cache[c as usize] == 0 {
tri.rotate_left(1);
} else if cache[a as usize] == 0 && cache[b as usize] == 0 && cache[c as usize] == 0 {
let (mut ab, mut bc, mut ca) = (false, false, false);
for j in i + 1..n.min(i + 4) {
ctx.tick(1)?;
let [oa, ob, oc] = [t[j * 3], t[j * 3 + 1], t[j * 3 + 2]];
ab |= (oa == b && ob == a) || (ob == b && oc == a) || (oc == b && oa == a);
bc |= (oa == c && ob == b) || (ob == c && oc == b) || (oc == c && oa == b);
ca |= (oa == a && ob == c) || (ob == a && oc == c) || (oc == a && oa == c);
}
if ab && !bc {
tri.rotate_left(1);
} else if (ab && !ca) || (!ab && bc && !ca) {
tri.rotate_right(1);
}
}
t[i * 3..i * 3 + 3].copy_from_slice(&tri);
for x in tri {
cache[x as usize] = 1;
}
}
}
let mut remap = [-1i16; 256];
let mut order = [0u32; 256];
let mut count = 0;
ctx.tick(t.len())?;
for x in t {
let r = &mut remap[*x as usize];
if *r < 0 {
*r = count as i16;
order[count] = v[*x as usize];
count += 1;
}
*x = *r as u8;
}
v[..count].copy_from_slice(&order[..count]);
Ok(())
}
pub fn optimize_meshlet_level_in_place(
vertices: &mut [u32],
triangles: &mut [u8],
level: u8,
workspace: &mut Workspace,
) -> Result<(), Error> {
let mut ctx = Context::new(workspace)?;
validate_local(vertices, triangles)?;
let mut v = [0; 256];
let mut t = [0; 1536];
v[..vertices.len()].copy_from_slice(vertices);
t[..triangles.len()].copy_from_slice(triangles);
optimize(
&mut v[..vertices.len()],
&mut t[..triangles.len()],
level,
&mut ctx,
)?;
vertices.copy_from_slice(&v[..vertices.len()]);
triangles.copy_from_slice(&t[..triangles.len()]);
Ok(())
}
pub fn optimize_meshlet_in_place(
vertices: &mut [u32],
triangles: &mut [u8],
workspace: &mut Workspace,
) -> Result<(), Error> {
optimize_meshlet_level_in_place(vertices, triangles, 0, workspace)
}
pub fn optimize_meshlet_level(
vertices: &[u32],
triangles: &[u8],
level: u8,
workspace: &mut Workspace,
) -> Result<LocalMeshlet, Error> {
let mut ctx = Context::new(workspace)?;
validate_local(vertices, triangles)?;
let mut v = ctx.copy(vertices)?;
let mut t = ctx.copy(triangles)?;
optimize(&mut v, &mut t, level, &mut ctx)?;
Ok(LocalMeshlet {
vertices: v,
triangles: t,
})
}
pub fn optimize_meshlet(
vertices: &[u32],
triangles: &[u8],
workspace: &mut Workspace,
) -> Result<LocalMeshlet, Error> {
optimize_meshlet_level(vertices, triangles, 0, workspace)
}
pub fn optimize_meshlet_level_into(
out_vertices: &mut [u32],
out_triangles: &mut [u8],
vertices: &[u32],
triangles: &[u8],
level: u8,
workspace: &mut Workspace,
) -> Result<(), Error> {
let mut ctx = Context::new(workspace)?;
if out_vertices.len() < vertices.len() || out_triangles.len() < triangles.len() {
return Err(Error::BufferTooSmall);
}
validate_local(vertices, triangles)?;
let mut v = [0; 256];
let mut t = [0; 1536];
v[..vertices.len()].copy_from_slice(vertices);
t[..triangles.len()].copy_from_slice(triangles);
optimize(
&mut v[..vertices.len()],
&mut t[..triangles.len()],
level,
&mut ctx,
)?;
out_vertices[..vertices.len()].copy_from_slice(&v[..vertices.len()]);
out_triangles[..triangles.len()].copy_from_slice(&t[..triangles.len()]);
Ok(())
}
pub fn optimize_meshlet_into(
out_vertices: &mut [u32],
out_triangles: &mut [u8],
vertices: &[u32],
triangles: &[u8],
workspace: &mut Workspace,
) -> Result<(), Error> {
optimize_meshlet_level_into(
out_vertices,
out_triangles,
vertices,
triangles,
0,
workspace,
)
}
#[cfg(test)]
mod bounds_root_tests {
use super::{bounds_roots, sqrt8, LANES};
#[test]
fn used_roots_match_full_lanes_bit_for_bit() {
let mut state = 0x1357_2468u32;
let special = [
0,
1,
0x007f_ffff,
0x0080_0000,
0x3f80_0000,
0x7f7f_ffff,
0x8000_0000,
0xbf80_0000,
0x7f80_0000,
0x7fc0_1234,
];
for sample in 0..512 {
for used in 1..=LANES {
let mut values = [1.; LANES];
for value in &mut values[..used] {
state = state.wrapping_mul(1664525).wrapping_add(1013904223);
let bits = if sample < special.len() {
special[sample]
} else if sample.is_multiple_of(2) {
0x0080_0000 + state % 0x7f00_0000
} else {
state
};
*value = f32::from_bits(bits);
}
assert_eq!(
bounds_roots(values, used).map(f32::to_bits),
sqrt8(values).map(f32::to_bits)
);
}
}
}
}