use super::bounds_math::{abs_sum3_up, add_up, enclosing_sphere, f32_up, sqrt_up};
use super::{FlatDagCluster, FlatDagGroup, LodBounds};
use alloc::vec::Vec;
#[derive(Clone, Copy, Debug, PartialEq, Eq)]
#[non_exhaustive]
pub enum CutError {
InvalidTable,
InvalidParameter,
BufferTooSmall,
Incomplete {
group: u32,
},
Allocation,
}
impl core::fmt::Display for CutError {
fn fmt(&self, f: &mut core::fmt::Formatter<'_>) -> core::fmt::Result {
write!(f, "cut: {self:?}")
}
}
#[cfg(feature = "std")]
impl std::error::Error for CutError {}
#[derive(Clone, Copy, Debug, PartialEq, Eq)]
#[non_exhaustive]
pub enum Violation {
InvalidTable,
NonFinite {
group: u32,
},
ErrorDecreases {
child: u32,
parent: u32,
},
NotContained {
child: u32,
parent: u32,
},
}
#[derive(Clone, Copy, Debug, Default, PartialEq, Eq)]
pub struct MonotonicReport {
pub groups_changed: usize,
pub errors_raised: usize,
pub radii_grown: usize,
}
#[derive(Clone, Copy, Debug, PartialEq)]
pub enum Projection {
Perspective {
proj_y: f32,
znear: f32,
},
Orthographic {
pixels_per_unit: f32,
},
}
#[derive(Clone, Copy, Debug, PartialEq)]
pub struct CutView {
pub position: [f32; 3],
pub projection: Projection,
pub viewport_height: f32,
pub scale: f32,
}
#[derive(Clone, Copy, Debug, PartialEq)]
pub enum Threshold {
Pixels(f32),
Finest,
}
impl CutView {
fn validate(&self) -> Result<(), CutError> {
let positive = |v: f32| v.is_finite() && v > 0.0;
let ok = self.position.iter().all(|v| v.is_finite())
&& positive(self.scale)
&& self.viewport_height.is_finite()
&& self.viewport_height >= 0.0
&& match self.projection {
Projection::Perspective { proj_y, znear } => positive(proj_y) && positive(znear),
Projection::Orthographic { pixels_per_unit } => positive(pixels_per_unit),
};
if ok {
Ok(())
} else {
Err(CutError::InvalidParameter)
}
}
}
pub fn projected_error(bounds: LodBounds, view: &CutView) -> f32 {
let s = f64::from(view.scale);
let error = f64::from(bounds.error) * s;
let pixels = match view.projection {
Projection::Perspective { proj_y, znear } => {
let d = |i: usize| f64::from(bounds.center[i]) - f64::from(view.position[i]);
let distance = libm::sqrt(d(0) * d(0) + d(1) * d(1) + d(2) * d(2));
let denominator = (distance - f64::from(bounds.radius) * s).max(f64::from(znear));
error / denominator * (f64::from(proj_y) * 0.5) * f64::from(view.viewport_height)
}
Projection::Orthographic { pixels_per_unit } => error * f64::from(pixels_per_unit),
};
pixels as f32
}
fn group_bounds(g: &FlatDagGroup) -> LodBounds {
LodBounds {
center: g.center,
radius: g.radius,
error: g.error,
}
}
fn vec_filled<T: Clone>(n: usize, value: T) -> Result<Vec<T>, CutError> {
let mut v = Vec::new();
v.try_reserve_exact(n).map_err(|_| CutError::Allocation)?;
v.resize(n, value);
Ok(v)
}
fn span(g: &FlatDagGroup) -> core::ops::Range<usize> {
let first = g.first_cluster as usize;
first..first + g.cluster_count as usize
}
fn validate(groups: &[FlatDagGroup], clusters: &[FlatDagCluster]) -> Result<(), CutError> {
if u32::try_from(clusters.len()).is_err() || i32::try_from(groups.len()).is_err() {
return Err(CutError::InvalidTable);
}
let mut next = 0usize;
for (g, group) in groups.iter().enumerate() {
let end = (group.first_cluster as usize)
.checked_add(group.cluster_count as usize)
.ok_or(CutError::InvalidTable)?;
if group.first_cluster as usize != next || end > clusters.len() {
return Err(CutError::InvalidTable);
}
for c in &clusters[next..end] {
let refined_ok = c.refined == -1 || (c.refined >= 0 && (c.refined as usize) < g);
if c.group as usize != g || !refined_ok {
return Err(CutError::InvalidTable);
}
}
next = end;
}
if next == clusters.len() {
Ok(())
} else {
Err(CutError::InvalidTable)
}
}
struct Children {
start: Vec<u32>,
list: Vec<u32>,
}
impl Children {
fn build(group_count: usize, clusters: &[FlatDagCluster]) -> Result<Self, CutError> {
let mut start = vec_filled(group_count + 1, 0u32)?;
for c in clusters.iter().filter(|c| c.refined >= 0) {
start[c.refined as usize + 1] += 1;
}
for i in 0..group_count {
start[i + 1] += start[i];
}
let mut list = vec_filled(start[group_count] as usize, 0u32)?;
let mut fill = vec_filled(group_count, 0u32)?;
for (i, c) in clusters.iter().enumerate() {
if c.refined >= 0 {
let q = c.refined as usize;
list[(start[q] + fill[q]) as usize] = i as u32;
fill[q] += 1;
}
}
Ok(Self { start, list })
}
fn of(&self, q: usize) -> &[u32] {
&self.list[self.start[q] as usize..self.start[q + 1] as usize]
}
}
fn check_resident(resident: Option<&[bool]>, groups: usize) -> Result<(), CutError> {
match resident {
Some(r) if r.len() != groups => Err(CutError::InvalidParameter),
_ => Ok(()),
}
}
fn needs_refinement<'a>(
groups: &'a [FlatDagGroup],
view: &'a CutView,
threshold: Threshold,
) -> Result<impl Fn(usize) -> bool + 'a, CutError> {
view.validate()?;
let pixels = match threshold {
Threshold::Finest => None,
Threshold::Pixels(t) if t.is_finite() && t >= 0.0 => Some(t),
Threshold::Pixels(_) => return Err(CutError::InvalidParameter),
};
Ok(move |g: usize| match pixels {
None => true,
Some(t) => projected_error(group_bounds(&groups[g]), view) > t,
})
}
fn clamp_refinement(
groups: &[FlatDagGroup],
clusters: &[FlatDagCluster],
children: &Children,
predicate: impl Fn(usize) -> bool,
) -> Result<Vec<bool>, CutError> {
let mut refine = vec_filled(groups.len(), false)?;
for q in (0..groups.len()).rev() {
let parents = children.of(q);
refine[q] = predicate(q)
&& parents
.iter()
.all(|&c| refine[clusters[c as usize].group as usize]);
}
Ok(refine)
}
fn select(
groups: &[FlatDagGroup],
clusters: &[FlatDagCluster],
resident: Option<&[bool]>,
refine: impl Fn(usize) -> bool,
out: &mut [u32],
) -> Result<usize, CutError> {
validate(groups, clusters)?;
check_resident(resident, groups.len())?;
let children = Children::build(groups.len(), clusters)?;
let refine = clamp_refinement(groups, clusters, &children, refine)?;
let is_resident = |g: usize| resident.is_none_or(|r| r[g]);
let mut n = 0;
for (g, group) in groups.iter().enumerate() {
if !is_resident(g) || !(children.of(g).is_empty() || refine[g]) {
continue;
}
for c in span(group) {
let r = clusters[c].refined;
let draw = r < 0 || !refine[r as usize] || !is_resident(r as usize);
if draw {
*out.get_mut(n).ok_or(CutError::BufferTooSmall)? = c as u32;
n += 1;
}
}
}
Ok(n)
}
pub fn select_cut(
groups: &[FlatDagGroup],
clusters: &[FlatDagCluster],
view: &CutView,
threshold: Threshold,
resident: Option<&[bool]>,
out: &mut [u32],
) -> Result<usize, CutError> {
let refine = needs_refinement(groups, view, threshold)?;
select(groups, clusters, resident, refine, out)
}
pub fn select_error_cut(
groups: &[FlatDagGroup],
clusters: &[FlatDagCluster],
error: f32,
out: &mut [u32],
) -> Result<usize, CutError> {
if !(error.is_finite() && error >= 0.0) {
return Err(CutError::InvalidParameter);
}
select(groups, clusters, None, |g| groups[g].error > error, out)
}
pub fn refine_sequential(
groups: &[FlatDagGroup],
clusters: &[FlatDagCluster],
view: &CutView,
threshold: Threshold,
resident: Option<&[bool]>,
out: &mut [u32],
) -> Result<usize, CutError> {
let refine = needs_refinement(groups, view, threshold)?;
validate(groups, clusters)?;
check_resident(resident, groups.len())?;
let children = Children::build(groups.len(), clusters)?;
let refine = clamp_refinement(groups, clusters, &children, refine)?;
let is_resident = |g: usize| resident.is_none_or(|r| r[g]);
let mut drawn = vec_filled(clusters.len(), false)?;
for (g, group) in groups.iter().enumerate() {
if children.of(g).is_empty() && is_resident(g) {
drawn[span(group)].fill(true);
}
}
for q in (0..groups.len()).rev() {
if !is_resident(q) || !refine[q] {
continue;
}
for &c in children.of(q) {
if !drawn[c as usize] {
return Err(CutError::Incomplete { group: q as u32 });
}
drawn[c as usize] = false;
}
drawn[span(&groups[q])].fill(true);
}
let mut n = 0;
for (c, _) in drawn.iter().enumerate().filter(|(_, d)| **d) {
*out.get_mut(n).ok_or(CutError::BufferTooSmall)? = c as u32;
n += 1;
}
Ok(n)
}
pub fn group_parents(
groups: &[FlatDagGroup],
clusters: &[FlatDagCluster],
offsets: &mut [u32],
parents: &mut [u32],
) -> Result<usize, CutError> {
validate(groups, clusters)?;
if offsets.len() <= groups.len() {
return Err(CutError::BufferTooSmall);
}
let children = Children::build(groups.len(), clusters)?;
let mut n = 0usize;
for (q, offset) in offsets.iter_mut().take(groups.len()).enumerate() {
*offset = n as u32;
let mut last = None;
for &c in children.of(q) {
let p = clusters[c as usize].group;
if last != Some(p) {
*parents.get_mut(n).ok_or(CutError::BufferTooSmall)? = p;
n += 1;
last = Some(p);
}
}
}
offsets[groups.len()] = n as u32;
Ok(n)
}
fn containing_radius(p: &FlatDagGroup, q: &FlatDagGroup) -> f64 {
super::bounds_math::containing_radius(p.center, q.center, q.radius)
}
fn group_is_finite(g: &FlatDagGroup) -> bool {
g.center.iter().all(|v| v.is_finite())
&& g.radius.is_finite()
&& g.radius >= 0.0
&& g.error.is_finite()
&& g.error >= 0.0
}
pub fn check_monotonic(
groups: &[FlatDagGroup],
clusters: &[FlatDagCluster],
) -> Result<(), Violation> {
validate(groups, clusters).map_err(|_| Violation::InvalidTable)?;
if let Some(g) = groups.iter().position(|g| !group_is_finite(g)) {
return Err(Violation::NonFinite { group: g as u32 });
}
for (p, parent) in groups.iter().enumerate() {
for c in &clusters[span(parent)] {
if c.refined < 0 {
continue;
}
let child = &groups[c.refined as usize];
let ids = (c.refined as u32, p as u32);
if parent.error < child.error {
return Err(Violation::ErrorDecreases {
child: ids.0,
parent: ids.1,
});
}
if containing_radius(parent, child) > f64::from(parent.radius) {
return Err(Violation::NotContained {
child: ids.0,
parent: ids.1,
});
}
}
}
Ok(())
}
pub fn enforce_monotonic(
groups: &mut [FlatDagGroup],
clusters: &[FlatDagCluster],
) -> Result<MonotonicReport, CutError> {
validate(groups, clusters)?;
if !groups.iter().all(group_is_finite) {
return Err(CutError::InvalidTable);
}
let mut report = MonotonicReport::default();
for p in 0..groups.len() {
let (mut raised, mut grown) = (false, false);
for c in span(&groups[p]) {
if clusters[c].refined < 0 {
continue;
}
let child = groups[clusters[c].refined as usize];
let parent = &mut groups[p];
if parent.error < child.error {
parent.error = child.error;
raised = true;
}
let needed = containing_radius(parent, &child);
if needed > f64::from(parent.radius) {
let radius = f32_up(needed);
if !radius.is_finite() {
return Err(CutError::InvalidTable);
}
parent.radius = radius;
grown = true;
}
}
report.errors_raised += usize::from(raised);
report.radii_grown += usize::from(grown);
report.groups_changed += usize::from(raised || grown);
}
Ok(report)
}
fn root_producers<'t>(
groups: &'t [FlatDagGroup],
clusters: &'t [FlatDagCluster],
children: &'t Children,
) -> impl Iterator<Item = &'t FlatDagGroup> + Clone + 't {
groups
.iter()
.enumerate()
.filter(|(g, _)| children.of(*g).is_empty())
.flat_map(move |(_, group)| clusters[span(group)].iter())
.filter_map(move |c| usize::try_from(c.refined).ok().map(|q| &groups[q]))
}
pub fn root_bounds(
groups: &[FlatDagGroup],
clusters: &[FlatDagCluster],
) -> Result<LodBounds, CutError> {
validate(groups, clusters)?;
let children = Children::build(groups.len(), clusters)?;
let producers = root_producers(groups, clusters, &children);
let mut error = 0.0f32;
for q in producers.clone() {
if !group_is_finite(q) {
return Err(CutError::InvalidTable);
}
error = error.max(q.error);
}
let none = producers.clone().next().is_none();
let (center, radius) = match enclosing_sphere(producers.map(|q| (q.center, q.radius))) {
Some(s) => s,
None if none => ([0.0; 3], 0.0),
None => return Err(CutError::InvalidTable),
};
Ok(LodBounds {
center,
radius,
error,
})
}
pub fn root_error(groups: &[FlatDagGroup], clusters: &[FlatDagCluster]) -> Result<f32, CutError> {
root_bounds(groups, clusters).map(|b| b.error)
}
pub fn root_clusters(
groups: &[FlatDagGroup],
clusters: &[FlatDagCluster],
out: &mut [u32],
) -> Result<usize, CutError> {
validate(groups, clusters)?;
let children = Children::build(groups.len(), clusters)?;
let mut n = 0;
for (g, group) in groups.iter().enumerate() {
if !children.of(g).is_empty() {
continue;
}
for c in span(group) {
*out.get_mut(n).ok_or(CutError::BufferTooSmall)? = c as u32;
n += 1;
}
}
Ok(n)
}
const ROOT_MARGIN: f64 = 1.0 / (1u64 << 44) as f64;
pub fn is_root_cut(sphere: [f32; 4], root_error: f32, view: &CutView, t: Threshold) -> bool {
let Threshold::Pixels(t) = t else {
return false;
};
let bound_ok = sphere.iter().all(|v| v.is_finite())
&& sphere[3] >= 0.0
&& root_error.is_finite()
&& root_error >= 0.0;
if !(bound_ok && t.is_finite() && t >= 0.0) || view.validate().is_err() {
return false;
}
let s = f64::from(view.scale);
let error = f64::from(root_error) * s;
let pixels = match view.projection {
Projection::Perspective { proj_y, znear } => {
let d = |i: usize| f64::from(sphere[i]) - f64::from(view.position[i]);
let distance = libm::sqrt(d(0) * d(0) + d(1) * d(1) + d(2) * d(2));
let reach = f64::from(sphere[3]) * s;
let denominator =
(distance - reach - ROOT_MARGIN * (distance + 2.0 * reach)).max(f64::from(znear));
error / denominator * (f64::from(proj_y) * 0.5) * f64::from(view.viewport_height)
}
Projection::Orthographic { pixels_per_unit } => error * f64::from(pixels_per_unit),
};
pixels <= f64::from(t)
}
pub fn gather_error_cut(
groups: &[FlatDagGroup],
clusters: &[FlatDagCluster],
indices: &[u32],
error: f32,
out: &mut [u32],
mut triangle_clusters: Option<&mut [u32]>,
) -> Result<usize, CutError> {
let mut cut = vec_filled(clusters.len(), 0u32)?;
let k = select_error_cut(groups, clusters, error, &mut cut)?;
let (mut n, mut triangles) = (0usize, 0usize);
for &c in &cut[..k] {
let cluster = &clusters[c as usize];
let first = cluster.first_index as usize;
let count = cluster.index_count as usize;
let span = first
.checked_add(count)
.and_then(|end| indices.get(first..end))
.filter(|s| s.len() % 3 == 0)
.ok_or(CutError::InvalidTable)?;
out.get_mut(n..n + count)
.ok_or(CutError::BufferTooSmall)?
.copy_from_slice(span);
n += count;
if let Some(tc) = triangle_clusters.as_deref_mut() {
let end = triangles + count / 3;
tc.get_mut(triangles..end)
.ok_or(CutError::BufferTooSmall)?
.fill(c);
triangles = end;
}
}
Ok(n)
}
pub fn max_scale(linear: [[f32; 3]; 3]) -> f32 {
if linear.iter().flatten().any(|v| !v.is_finite()) {
return f32::INFINITY;
}
let m = |r: usize, c: usize| f64::from(linear[r][c]);
let mut bound = 0.0f64;
for i in 0..3 {
let mut row = 0.0;
for j in 0..3 {
let g = abs_sum3_up([0, 1, 2].map(|k| m(k, i) * m(k, j)));
row = add_up(row, g);
}
bound = bound.max(row);
}
f32_up(sqrt_up(bound))
}