use std::sync::Mutex;
use rayon::prelude::*;
use rustc_hash::{FxHashMap, FxHashSet};
use crate::bbox::{Aabb, Bounder};
use crate::bvh::Bvh;
use crate::classify::{Label, Status};
use crate::error::{Error, Result};
use crate::model::Fill;
use crate::progress::Progress;
use crate::trace::Line;
use crate::transform::Affine;
use crate::vec3::{add, dot, scale, Vec3};
use crate::Model;
static PIECES: std::sync::atomic::AtomicU64 = std::sync::atomic::AtomicU64::new(0);
static LENGTH: std::sync::atomic::AtomicU64 = std::sync::atomic::AtomicU64::new(0);
static PIECE_NS: std::sync::atomic::AtomicU64 = std::sync::atomic::AtomicU64::new(0);
static TRACE_NS: std::sync::atomic::AtomicU64 = std::sync::atomic::AtomicU64::new(0);
const CHUNKS: usize = 1024;
mod grid;
mod instances;
mod placed;
mod refine;
mod sums;
#[cfg(test)]
mod tests;
pub use grid::*;
pub use placed::*;
pub use refine::*;
use sums::*;
#[derive(Clone, Debug, PartialEq)]
pub struct Volume {
pub estimate: f64,
pub sigma: f64,
pub by_probe: Vec<f64>,
pub segments: u64,
pub bbox: Aabb,
lengths: Vec<f64>,
}
impl Volume {
fn empty(probes: usize) -> Volume {
Volume {
estimate: 0.0,
sigma: 0.0,
by_probe: Vec::new(),
segments: 0,
bbox: Aabb::EMPTY,
lengths: vec![0.0; probes],
}
}
pub fn probes_hit(&self) -> usize {
self.lengths.iter().filter(|&&l| l > 0.0).count()
}
fn add(&mut self, o: &Volume) {
for (a, b) in self.lengths.iter_mut().zip(&o.lengths) {
*a += b;
}
self.segments += o.segments;
self.bbox = self.bbox.union(&o.bbox);
}
fn append(&mut self, o: &Volume) {
self.lengths.extend_from_slice(&o.lengths);
self.segments += o.segments;
self.bbox = self.bbox.union(&o.bbox);
}
fn finish(&mut self, grid: &VolumeGrid) {
let s = grid.spacing();
self.by_probe = self.lengths.iter().map(|l| l * s * s).collect();
let n = self.by_probe.len() as f64;
let mean = self.by_probe.iter().sum::<f64>() / n;
let ss: f64 = self.by_probe.iter().map(|v| (v - mean) * (v - mean)).sum();
self.estimate = mean;
self.sigma = (ss / (n - 1.0) / n).sqrt();
}
}
#[derive(Clone, Debug)]
pub struct Volumes {
pub grid: VolumeGrid,
pub labels: Vec<Label>,
pub volumes: Vec<Volume>,
}
impl Volumes {
pub fn group_by<K: std::hash::Hash + Eq + Clone>(
&self,
mut key: impl FnMut(&Label) -> Option<K>,
) -> Vec<(K, Volume)> {
let mut index: FxHashMap<K, usize> = FxHashMap::default();
let mut out: Vec<(K, Volume)> = Vec::new();
for (l, v) in self.labels.iter().zip(&self.volumes) {
let Some(k) = key(l) else { continue };
let i = *index.entry(k.clone()).or_insert_with(|| {
out.push((k, Volume::empty(v.lengths.len())));
out.len() - 1
});
out[i].1.add(v);
}
for (_, v) in &mut out {
v.finish(&self.grid);
}
out
}
pub fn grouped(&self, m: &Model, by: GroupBy) -> Vec<Group> {
let key = |l: &Label| -> (bool, Option<i64>, String) {
let inside = l.status == Status::Inside;
let number = match (l.cell(), by) {
(Some(c), GroupBy::Cell) => Some(m.cell(c).id),
(Some(c), GroupBy::Material) => Some(m.cell(c).material),
(Some(c), GroupBy::Universe) => Some(m.units()[m.cell(c).unit as usize].universe),
_ => None,
};
let name = match number {
Some(n) => n.to_string(),
None => m.describe(l),
};
(!inside, number, name)
};
let mut groups: Vec<(_, Volume)> = self.group_by(|l| {
let k = key(l);
let label = k.1.is_none().then(|| l.clone());
Some((k, l.status, label))
});
groups.sort_by(|a, b| a.0 .0.cmp(&b.0 .0));
groups
.into_iter()
.map(|(((_, number, name), status, label), volume)| Group {
number,
name,
status,
label,
volume,
})
.collect()
}
pub fn problems(&self) -> Vec<usize> {
let mut p: Vec<usize> = (0..self.labels.len())
.filter(|&i| !matches!(self.labels[i].status, Status::Inside | Status::OnSurface))
.collect();
p.sort_by(|&a, &b| {
self.volumes[b]
.estimate
.total_cmp(&self.volumes[a].estimate)
.then(a.cmp(&b))
});
p
}
pub fn total(&self) -> f64 {
self.volumes.iter().map(|v| v.estimate).sum()
}
}
#[derive(Clone, Copy, Debug, PartialEq, Eq, Hash)]
pub enum GroupBy {
Cell,
Material,
Universe,
Label,
}
#[derive(Clone, Debug, PartialEq)]
pub struct Group {
pub number: Option<i64>,
pub name: String,
pub status: Status,
pub label: Option<Label>,
pub volume: Volume,
}
#[derive(Clone, Copy, Debug, PartialEq)]
pub struct VolumeTarget {
pub rel_sigma: f64,
pub h_min: f64,
pub abs_sigma: f64,
pub max_probes: usize,
pub by: GroupBy,
}
#[derive(Clone, Debug)]
pub struct Converged {
pub groups: Vec<Group>,
pub h: Vec<f64>,
pub unconverged: Vec<usize>,
pub unseen: Vec<usize>,
pub empty: Vec<usize>,
pub listed_all: bool,
}
pub const MAX_LISTED_INSTANCES: u64 = 1 << 20;
#[derive(Clone, Copy, Debug, PartialEq)]
pub struct BinTarget {
pub region: Aabb,
pub rel_sigma: f64,
pub h_min: f64,
pub h_max: f64,
pub abs_sigma: f64,
pub max_probes: usize,
pub seed: u64,
pub probes: usize,
}
impl BinTarget {
pub fn new(region: Aabb, rel_sigma: f64, h_min: f64) -> BinTarget {
BinTarget {
region,
rel_sigma,
h_min,
h_max: f64::INFINITY,
abs_sigma: 0.0,
max_probes: MAX_PROBES,
seed: 1,
probes: DEFAULT_PROBES,
}
}
}
#[derive(Clone, Debug)]
pub struct BinVolumes {
pub volumes: Vec<Volume>,
pub h: Vec<f64>,
pub instances: Vec<u64>,
pub unconverged: Vec<usize>,
pub unseen: Vec<usize>,
pub empty: Vec<usize>,
}
impl Model {
pub fn volumes(&self, grid: &VolumeGrid, progress: Option<&Progress>) -> Result<Volumes> {
let none = Progress::new();
self.grid_volumes(grid, progress.unwrap_or(&none))
}
pub fn volumes_within(
&self,
grid: &VolumeGrid,
boxes: &[Aabb],
progress: Option<&Progress>,
) -> Result<Volumes> {
let none = Progress::new();
self.check_grid(grid)?;
if boxes
.iter()
.any(|b| b.lo.iter().chain(&b.hi).any(|v| v.is_nan()))
{
return Err(Error::Invalid("a box to check has NaN bounds".into()));
}
let boxes: Vec<Aabb> = boxes
.iter()
.map(|b| b.intersect(&grid.region))
.filter(|b| !b.is_empty())
.collect();
self.volumes_in(grid, 0..grid.probes, &boxes, progress.unwrap_or(&none))
}
fn check_grid(&self, grid: &VolumeGrid) -> Result<()> {
if !(grid.h > 0.0 && grid.h.is_finite()) {
return Err(Error::Invalid(format!(
"grid spacing must be positive, not {}",
grid.h
)));
}
if !grid.region.is_finite() || grid.region.is_empty() {
return Err(Error::Invalid(format!(
"grid region must be finite and not empty: {:?} .. {:?}",
grid.region.lo, grid.region.hi
)));
}
if grid.probes < 2 {
return Err(Error::Invalid(format!(
"a grid needs at least 2 probes, not {}",
grid.probes
)));
}
Ok(())
}
fn grid_volumes(&self, grid: &VolumeGrid, progress: &Progress) -> Result<Volumes> {
self.check_grid(grid)?;
self.volumes_in(grid, 0..grid.probes, &[grid.region], progress)
}
fn volumes_in(
&self,
grid: &VolumeGrid,
range: std::ops::Range<usize>,
boxes: &[Aabb],
progress: &Progress,
) -> Result<Volumes> {
let n_probes = range.len();
let probes: Vec<Lattice> = range.map(|p| grid.lattice(p)).collect();
let rows: Vec<Vec<(i64, i64, usize)>> = probes
.par_iter()
.map(|l| {
boxes
.iter()
.map(|b| {
let o = grid.lattice_over(l, b);
(o.ka.0, o.ka.1, o.count())
})
.collect()
})
.collect();
let total: usize = rows.iter().flatten().map(|r| r.2).sum();
let per_band = (total / CHUNKS).clamp(BAND_MIN, BAND_MAX);
let mut chunks: Vec<Band> = Vec::new();
for (p, rows) in rows.iter().enumerate() {
let live = rows.iter().filter(|r| r.2 > 0);
let (Some(lo), Some(hi)) = (live.clone().map(|r| r.0).min(), live.map(|r| r.1).max())
else {
continue;
};
let tried: usize = rows.iter().map(|r| r.2).sum();
let span = (hi - lo) as usize;
let width = (span * per_band).div_ceil(tried.max(1)).clamp(1, span) as i64;
let mut pairs: Vec<(i64, u32)> = Vec::new();
for (b, &(a0, a1, n)) in rows.iter().enumerate() {
if n > 0 {
for band in (a0 - lo) / width..=(a1 - 1 - lo) / width {
pairs.push((band, b as u32));
}
}
}
pairs.sort_unstable();
for run in pairs.chunk_by(|x, y| x.0 == y.0) {
let r0 = lo + run[0].0 * width;
chunks.push(Band {
probe: p,
rows: (r0, r0 + width),
boxes: run.iter().map(|x| x.1).collect(),
});
}
}
progress.start(chunks.len());
let acc: Vec<Mutex<Shard>> = (0..SHARDS).map(|_| Mutex::default()).collect();
let lock = |s: usize| acc[s].lock().unwrap_or_else(|e| e.into_inner());
chunks.par_iter().enumerate().for_each(|(c, band)| {
if progress.cancelled() {
return;
}
let sums = self.chunk_sums(grid, boxes, &probes[band.probe], band, progress);
for k in 0..SHARDS {
let s = (c + k) % SHARDS;
if !sums.shard(s).is_empty() {
lock(s).add(&sums, s, c as u32, n_probes);
}
}
});
if progress.cancelled() {
return Err(Error::Cancelled);
}
let acc: Vec<Shard> = acc
.into_iter()
.map(|s| s.into_inner().unwrap_or_else(|e| e.into_inner()))
.collect();
let mut order: Vec<(u64, usize, usize)> = acc
.iter()
.enumerate()
.flat_map(|(s, shard)| shard.first.iter().enumerate().map(move |(i, &f)| (f, s, i)))
.collect();
order.par_sort_unstable();
let labels = order
.par_iter()
.map(|&(_, s, i)| crate::classify::decode(&acc[s].keys[i]))
.collect();
let volumes: Vec<Volume> = order
.par_iter()
.map(|&(_, s, i)| {
let mut v = acc[s].volume(i, n_probes);
v.finish(grid);
v
})
.collect();
Ok(Volumes {
grid: grid.clone(),
labels,
volumes,
})
}
fn chunk_sums(
&self,
grid: &VolumeGrid,
boxes: &[Aabb],
probe: &Lattice,
band: &Band,
progress: &Progress,
) -> ChunkSums {
let mut out = ChunkSums {
probe: band.probe,
keys: Default::default(),
sums: Vec::new(),
by_shard: Vec::new(),
shard_ends: Vec::new(),
};
if progress.cancelled() {
return out;
}
let debug = log::log_enabled!(log::Level::Debug);
let t = debug.then(std::time::Instant::now);
let mut lines: Vec<Line> = Vec::new();
union_pieces(grid, probe, boxes, &band.boxes, band.rows, &mut lines);
if let Some(t) = t {
PIECES.fetch_add(lines.len() as u64, std::sync::atomic::Ordering::Relaxed);
let len: f64 = lines.iter().map(|l| l.t_max - l.t_min).sum();
LENGTH.fetch_add(len as u64, std::sync::atomic::Ordering::Relaxed);
let ns = t.elapsed().as_nanos() as u64;
PIECE_NS.fetch_add(ns, std::sync::atomic::Ordering::Relaxed);
}
let t = debug.then(std::time::Instant::now);
let part = self.trace_part(&lines);
if let Some(t) = t {
let ns = t.elapsed().as_nanos() as u64;
TRACE_NS.fetch_add(ns, std::sync::atomic::Ordering::Relaxed);
}
let keys = &part.chunk;
out.sums = vec![(0, 0, Aabb::EMPTY); keys.len()];
let mut k = 0;
for (line, &n) in lines.iter().zip(&part.counts) {
for _ in 0..n {
let (len, n, bbox) = &mut out.sums[keys.ids[k] as usize];
*len += ((part.t1[k] - part.t0[k]) * FIXED).round() as u128;
*n += 1;
bbox.grow_point(line.at(part.t0[k]));
bbox.grow_point(line.at(part.t1[k]));
k += 1;
}
}
let shard = |i: u32| shard_of(keys.hash_of(i as usize));
out.by_shard = (0..keys.len() as u32).collect();
out.by_shard.sort_by_key(|&i| (shard(i), i));
let mut at = 0;
out.shard_ends = (0..SHARDS)
.map(|s| {
at += out.by_shard[at..].partition_point(|&i| shard(i) == s);
at as u32
})
.collect();
out.keys = part.chunk;
out.keys.keys_only();
progress.step();
out
}
}