use glam::{BVec3, DVec3, Mat4, Vec3};
const MAX_BOXES: usize = 1024;
pub(crate) fn posed_bounds(bounds: [Vec3; 2], pose: Mat4) -> [Vec3; 2] {
let pose = pose.as_dmat4();
let [low, high] = bounds.map(|corner| corner.as_dvec3());
let mut min = DVec3::splat(f64::INFINITY);
let mut max = DVec3::splat(f64::NEG_INFINITY);
for corner in 0..8 {
let p = pose.transform_point3(DVec3::select(
BVec3::new(corner & 1 != 0, corner & 2 != 0, corner & 4 != 0),
high,
low,
));
min = min.min(p);
max = max.max(p);
}
outward(min, max)
}
pub(crate) fn grown(bounds: [Vec3; 2], by: f32) -> [Vec3; 2] {
if by == 0. {
return bounds;
}
[bounds[0] - Vec3::splat(by), bounds[1] + Vec3::splat(by)]
}
pub(crate) fn posed_grown(posed: [Vec3; 2], pose: Mat4, by: f32) -> [Vec3; 2] {
if by == 0. {
return posed;
}
let linear = glam::Mat3::from_mat4(pose);
let abs = glam::Mat3::from_cols(
linear.x_axis.abs(),
linear.y_axis.abs(),
linear.z_axis.abs(),
);
let growth = abs * Vec3::splat(by);
let slack = posed[0].abs().max(posed[1].abs()) * f32::EPSILON;
[posed[0] - growth - slack, posed[1] + growth + slack]
}
fn outward(min: DVec3, max: DVec3) -> [Vec3; 2] {
let down = |v: f64| {
let rounded = v as f32;
if f64::from(rounded) > v {
rounded.next_down()
} else {
rounded
}
};
let up = |v: f64| {
let rounded = v as f32;
if f64::from(rounded) < v {
rounded.next_up()
} else {
rounded
}
};
[
Vec3::from_array(min.to_array().map(down)),
Vec3::from_array(max.to_array().map(up)),
]
}
fn union(a: [Vec3; 2], b: [Vec3; 2]) -> [Vec3; 2] {
[a[0].min(b[0]), a[1].max(b[1])]
}
fn halve(boxes: &mut Vec<[Vec3; 2]>) -> usize {
let centre = |bounds: &[Vec3; 2]| (bounds[0] + bounds[1]) * 0.5;
let (low, high) = boxes.iter().fold(
(Vec3::INFINITY, Vec3::NEG_INFINITY),
|(low, high), bounds| (low.min(centre(bounds)), high.max(centre(bounds))),
);
let scale = 1023. / (high - low).max(Vec3::splat(f32::MIN_POSITIVE));
let spread = |bits: u32| {
let mut x = bits & 0x3ff;
x = (x | (x << 16)) & 0x0300_00ff;
x = (x | (x << 8)) & 0x0300_f00f;
x = (x | (x << 4)) & 0x030c_30c3;
(x | (x << 2)) & 0x0924_9249
};
let order = |bounds: &[Vec3; 2]| {
let cell = ((centre(bounds) - low) * scale).as_uvec3();
spread(cell.x) | spread(cell.y) << 1 | spread(cell.z) << 2
};
boxes.sort_by_cached_key(order);
let pairs = boxes.len() / 2;
let kept = boxes.len().div_ceil(2);
for at in 0..kept {
let pair = &boxes[2 * at..(2 * at + 2).min(boxes.len())];
boxes[at] = pair
.iter()
.copied()
.reduce(union)
.expect("pairs are never empty");
}
boxes.truncate(kept);
pairs
}
#[derive(Default)]
pub(crate) struct StaticEdits {
pending: Vec<[Vec3; 2]>,
finished: u64,
edits: u64,
}
impl StaticEdits {
pub fn record(&mut self, bounds: [Vec3; 2]) {
self.edits += 1;
if !bounds[0].is_finite() || !bounds[1].is_finite() {
return;
}
let merged = if self.pending.len() == MAX_BOXES {
halve(&mut self.pending)
} else {
0
};
crate::counters::static_edit(merged);
self.pending.push(bounds);
}
pub fn pending(&self) -> &[[Vec3; 2]] {
&self.pending
}
pub fn finished(&self) -> u64 {
self.finished
}
pub fn edits(&self) -> u64 {
self.edits
}
pub fn move_origin(&mut self, by: Vec3) {
let by = by.as_dvec3();
for bounds in &mut self.pending {
*bounds = outward(bounds[0].as_dvec3() - by, bounds[1].as_dvec3() - by);
}
}
pub fn finish(&mut self) {
self.pending.clear();
self.finished += 1;
}
}
#[cfg(test)]
mod tests {
use super::*;
use wasm_bindgen_test::wasm_bindgen_test;
#[wasm_bindgen_test(unsupported = test)]
fn overflowing_edits_stay_within_the_boxes_kept() {
let mut edits = StaticEdits::default();
let recorded: Vec<[Vec3; 2]> = (0..MAX_BOXES * 3 + 7)
.map(|i| {
let t = i as f32;
let low =
Vec3::new((t * 12.9898).sin(), (t * 4.1414).sin(), (t * 78.233).sin()) * 500.;
[low, low + Vec3::new(16., 3. + t % 5., 16.)]
})
.collect();
for &bounds in &recorded {
edits.record(bounds);
}
let pending = edits.pending();
assert!(pending.len() <= MAX_BOXES, "{} boxes kept", pending.len());
for bounds in &recorded {
assert!(
pending
.iter()
.any(|kept| kept[0].cmple(bounds[0]).all() && kept[1].cmpge(bounds[1]).all()),
"{bounds:?} is in no kept box"
);
}
}
}