use super::*;
pub(super) fn reached(v: &Volume, rel_sigma: f64, abs_sigma: f64, probes: usize) -> bool {
let hit = v.probes_hit();
(v.sigma <= rel_sigma * v.estimate && hit == probes)
|| (abs_sigma > 0.0 && v.sigma <= abs_sigma && hit >= 2)
}
pub const MAX_PROBES: usize = 48;
pub(super) const PROBE_BLOCK: usize = 6;
pub(super) const ALPHA: f64 = 1.5;
pub(super) const ALPHA_MAX: f64 = 3.0;
#[derive(Clone, Copy, Debug, PartialEq)]
pub(super) enum Step {
Done,
Stop,
Trace { level: u32, probes: (usize, usize) },
}
#[derive(Clone, Debug)]
pub(super) struct Track {
pub(super) level: Option<u32>,
pub(super) volume: Volume,
pub(super) before: Option<(u32, f64)>,
pub(super) next: Step,
}
pub(super) type BoxesOf<'a> = dyn FnMut(&[Track], &[usize], &VolumeGrid) -> Vec<Aabb> + 'a;
pub(super) type Assign<'a> = dyn FnMut(&Volumes, &[usize], usize) -> Vec<Volume> + 'a;
pub(super) struct Levels<'a> {
pub(super) grid: &'a dyn Fn(u32) -> VolumeGrid,
pub(super) last: u32,
pub(super) rel_sigma: f64,
pub(super) abs_sigma: f64,
pub(super) base: usize,
pub(super) max_probes: usize,
}
impl Levels<'_> {
pub(super) fn next_step(
&self,
v: &Volume,
level: u32,
before: Option<(u32, f64)>,
reach: f64,
) -> Step {
let n = v.lengths.len();
if reached(v, self.rel_sigma, self.abs_sigma, n) {
return Step::Done;
}
let finer = |j: u32| match level.checked_add(j) {
Some(l) if l <= self.last => Step::Trace {
level: l,
probes: (0, self.base),
},
_ => Step::Stop,
};
if v.segments == 0 {
return if (self.grid)(level).spacing() * UNMET_LINES_ACROSS > reach {
finer(1)
} else {
Step::Stop
};
}
if v.probes_hit() < n {
return finer(1);
}
let want = if self.abs_sigma > 0.0 {
(self.rel_sigma * v.estimate).max(self.abs_sigma)
} else {
self.rel_sigma * v.estimate
};
let spread = v.sigma * (n as f64).sqrt();
let need = (n as f64 * (v.sigma / want).powi(2) * 1.1).ceil();
let more = (need.min(1e9) as usize)
.max(n + 1)
.next_multiple_of(PROBE_BLOCK);
let probes = (more <= self.max_probes).then_some((more - n) as f64);
let alpha = before
.filter(|&(l, s)| l < level && s > spread)
.map_or(ALPHA, |(l, s)| {
((s / spread).log2() / f64::from(level - l)).clamp(1.0, ALPHA_MAX)
});
let levels_for = |alpha: f64| {
(1..=self.last.saturating_sub(level)).find(|&j| {
spread * (-f64::from(j) * alpha).exp2() / (self.base as f64).sqrt() <= 0.9 * want
})
};
let levels = levels_for(alpha).or_else(|| levels_for(ALPHA_MAX));
let cost = |j: u32| self.base as f64 * 4f64.powi(j as i32);
match (probes, levels) {
(Some(a), Some(j)) if a <= cost(j) => Step::Trace {
level,
probes: (n, more),
},
(Some(_), None) => Step::Trace {
level,
probes: (n, more),
},
(_, Some(j)) => finer(j),
(None, None) => Step::Stop,
}
}
}
pub(super) const UNMET_LINES_ACROSS: f64 = 32.0;
pub(super) fn drop_contained(boxes: &mut Vec<Aabb>) {
if boxes.len() < 2 {
return;
}
let prims: Vec<(u32, Aabb)> = boxes
.iter()
.enumerate()
.map(|(i, b)| (i as u32, *b))
.collect();
let bvh = Bvh::build(&prims);
let inside = |a: &Aabb, b: &Aabb| (0..3).all(|k| b.lo[k] <= a.lo[k] && a.hi[k] <= b.hi[k]);
let keep: Vec<bool> = (0..boxes.len())
.into_par_iter()
.map(|i| {
let a = &boxes[i];
let mut covered = false;
bvh.query(a.center(), |j| {
let j = j as usize;
covered |= j != i && inside(a, &boxes[j]);
});
!covered
})
.collect();
let mut k = keep.iter();
boxes.retain(|_| *k.next().unwrap());
}
pub(super) type GroupKey = (Option<i64>, String, Status);
pub(super) fn group_key(g: &Group) -> GroupKey {
(g.number, g.name.clone(), g.status)
}
pub(super) fn expected_groups(m: &Model, by: GroupBy) -> Option<Vec<(Group, Vec<u32>)>> {
let holds = |c: u32| {
let cell = &m.cells[c as usize];
cell.unsupported.is_none()
&& match &cell.fill {
None => true,
Some(Fill::Universe(_)) => false,
Some(Fill::Lattice(_)) => m.fill_targets(c).any(|t| t.unit() == cell.unit),
}
};
let group = |number: Option<i64>, name: String, label: Option<Label>| Group {
number,
name,
status: Status::Inside,
label,
volume: Volume::empty(0),
};
let cells = (0..m.cells.len() as u32).filter(|&c| holds(c));
if by == GroupBy::Label {
let inst = m.instances();
let total: u64 = (0..m.cells.len() as u32)
.filter(|&c| holds(c))
.map(|c| inst.count(c))
.sum();
if total > MAX_LISTED_INSTANCES {
return None;
}
let mut out = Vec::new();
for c in cells {
for id in inst.ids(c) {
let Some(path) = m.instance_path(id) else {
continue;
};
let label = Label {
status: Status::Inside,
path,
involved: Vec::new(),
};
out.push((group(None, m.describe(&label), Some(label)), vec![c]));
}
}
return Some(out);
}
let mut by_number: std::collections::BTreeMap<i64, Vec<u32>> = Default::default();
for c in cells {
let cell = &m.cells[c as usize];
let n = match by {
GroupBy::Cell => cell.id,
GroupBy::Material => cell.material,
GroupBy::Universe => m.units[cell.unit as usize].universe,
GroupBy::Label => unreachable!(),
};
by_number.entry(n).or_default().push(c);
}
Some(
by_number
.into_iter()
.map(|(n, cells)| (group(Some(n), n.to_string(), None), cells))
.collect(),
)
}
impl Model {
#[allow(clippy::too_many_arguments)]
pub(super) fn refine(
&self,
tracks: &mut [Track],
levels: &Levels,
reach: &[f64],
boxes: &mut BoxesOf,
assign: &mut Assign,
progress: &Progress,
report: &mut dyn FnMut(&[Track]),
) -> Result<()> {
let wants = |t: &Track| match t.next {
Step::Trace { level, probes } => Some((level, probes)),
_ => None,
};
while let Some(level) = tracks.iter().filter_map(|t| wants(t).map(|w| w.0)).min() {
report(tracks);
let grid = (levels.grid)(level);
let at: Vec<usize> = (0..tracks.len())
.filter(|&i| wants(&tracks[i]).is_some_and(|w| w.0 == level))
.collect();
let wanted: FxHashMap<usize, (usize, usize)> = at
.iter()
.map(|&i| (i, wants(&tracks[i]).unwrap().1))
.collect();
let range = |i: usize| wanted[&i];
let mut ends: Vec<usize> = at.iter().flat_map(|&i| [range(i).0, range(i).1]).collect();
ends.sort_unstable();
ends.dedup();
let mut jobs: Vec<(std::ops::Range<usize>, Vec<usize>)> = Vec::new();
for w in ends.windows(2) {
let (a, b) = (w[0], w[1]);
let who: Vec<usize> = at
.iter()
.copied()
.filter(|&i| range(i).0 <= a && b <= range(i).1)
.collect();
match jobs.last_mut() {
Some((r, g)) if r.end == a && *g == who => r.end = b,
_ if !who.is_empty() => jobs.push((a..b, who)),
_ => {}
}
}
let mut parts: FxHashMap<usize, Vec<Volume>> = FxHashMap::default();
for (probes, who) in jobs {
let t = std::time::Instant::now();
let mut b = boxes(tracks, &who, &grid);
let boxed = t.elapsed().as_secs_f64();
let bits = |b: &Aabb| [b.lo, b.hi].map(|v| v.map(f64::to_bits));
b.retain(|b| !b.is_empty());
b.sort_by_key(bits);
b.dedup_by_key(|b| bits(b));
drop_contained(&mut b);
let traced = self.volumes_in(&grid, probes.clone(), &b, progress)?;
for (i, v) in who.iter().zip(assign(&traced, &who, probes.len())) {
parts.entry(*i).or_default().push(v);
}
if log::log_enabled!(log::Level::Debug) {
let lines: usize = probes
.clone()
.map(|p| {
b.iter()
.map(|x| grid.lattice_in(p, x).count())
.sum::<usize>()
})
.sum();
let ns = |a: &std::sync::atomic::AtomicU64| {
a.swap(0, std::sync::atomic::Ordering::Relaxed) as f64 * 1e-9
};
log::debug!(
"level {level} (h {}) probes {}..{}: groups {} (unmet {}) boxes {} ({:.3e} cm3) \
lines {lines} pieces {} length {:.3e} in {:.2} s (boxes {:.2} s; thread time: \
pieces {:.1} s, tracing {:.1} s)",
grid.h,
probes.start,
probes.end,
who.len(),
who.iter().filter(|&&i| tracks[i].volume.segments == 0).count(),
b.len(),
b.iter().map(|x| x.volume()).sum::<f64>(),
PIECES.swap(0, std::sync::atomic::Ordering::Relaxed),
LENGTH.swap(0, std::sync::atomic::Ordering::Relaxed) as f64,
t.elapsed().as_secs_f64(),
boxed,
ns(&PIECE_NS),
ns(&TRACE_NS),
);
}
}
for &i in &at {
let fresh = range(i).0 == 0;
let t = &mut tracks[i];
let mut v = if fresh {
if let Some(l) = t.level.filter(|_| t.volume.segments > 0) {
t.before =
Some((l, t.volume.sigma * (t.volume.lengths.len() as f64).sqrt()));
}
Volume::empty(0)
} else {
t.volume.clone()
};
for p in parts.remove(&i).unwrap_or_default() {
v.append(&p);
}
v.finish(&grid);
t.volume = v;
t.level = Some(level);
t.next = levels.next_step(&t.volume, level, t.before, reach[i]);
}
}
Ok(())
}
pub fn volumes_to(
&self,
grid: &VolumeGrid,
target: &VolumeTarget,
wanted: impl Fn(&Group) -> bool,
progress: Option<&Progress>,
mut each: Option<&mut dyn FnMut(&Converged)>,
) -> Result<Converged> {
let none = Progress::new();
let progress = progress.unwrap_or(&none);
if !(target.rel_sigma > 0.0 && target.h_min > 0.0 && target.abs_sigma >= 0.0) {
return Err(Error::Invalid(format!(
"target relative sigma and h_min must be positive, abs_sigma not negative: {target:?}"
)));
}
let by = target.by;
let first = self.grid_volumes(grid, progress)?;
let mut groups = first.grouped(self, by);
let none = |g: &VolumeGrid| {
let mut v = Volume::empty(g.probes);
v.finish(g);
v
};
let expected = expected_groups(self, by);
let listed_all = expected.is_some();
let mut cells_of: FxHashMap<GroupKey, Vec<u32>> = FxHashMap::default();
let mut known: FxHashSet<GroupKey> = groups.iter().map(group_key).collect();
for (mut g, cells) in expected.unwrap_or_default() {
let k = group_key(&g);
if known.insert(k.clone()) {
g.volume = none(grid);
groups.push(g);
}
cells_of.insert(k, cells);
}
let mut from_labels: FxHashMap<GroupKey, Vec<u32>> = FxHashMap::default();
for l in &first.labels {
let Some(c) = l.cell().filter(|_| l.status == Status::Inside) else {
continue;
};
let cell = &self.cells[c as usize];
let number = match by {
GroupBy::Cell => Some(cell.id),
GroupBy::Material => Some(cell.material),
GroupBy::Universe => Some(self.units[cell.unit as usize].universe),
GroupBy::Label => None,
};
let name = number.map_or_else(|| self.describe(l), |n| n.to_string());
let k = (number, name, Status::Inside);
if !cells_of.contains_key(&k) {
from_labels.entry(k).or_default().push(c);
}
}
for (k, mut cells) in from_labels {
cells.sort_unstable();
cells.dedup();
cells_of.insert(k, cells);
}
groups.sort_by(|a, b| {
(a.status != Status::Inside, a.number, &a.name).cmp(&(
b.status != Status::Inside,
b.number,
&b.name,
))
});
let cells: Vec<Option<&Vec<u32>>> =
groups.iter().map(|g| cells_of.get(&group_key(g))).collect();
let t = std::time::Instant::now();
let placed = PlacedBoxes::new(self, grid.region);
if log::log_enabled!(log::Level::Debug) {
log::debug!(
"placed boxes in {:.2} s: {} boxes",
t.elapsed().as_secs_f64(),
placed.boxes.iter().map(Vec::len).sum::<usize>()
);
}
let empty: Vec<usize> = (0..groups.len())
.filter(|&i| {
groups[i].volume.segments == 0
&& cells[i].is_some_and(|cs| cs.iter().all(|&c| placed.boxes(c).is_empty()))
})
.collect();
let want: Vec<bool> = groups
.iter()
.enumerate()
.map(|(i, g)| wanted(g) && empty.binary_search(&i).is_err())
.collect();
let reach: Vec<f64> = cells
.iter()
.map(|cs| {
cs.map_or(f64::INFINITY, |cs| {
cs.iter()
.flat_map(|&c| placed.boxes(c))
.flat_map(|b| (0..3).map(|k| b.hi[k] - b.lo[k]))
.fold(0.0, f64::max)
})
})
.collect();
let grid_at = |l: u32| VolumeGrid {
h: grid.h / f64::from(l).exp2(),
seed: if l == 0 {
grid.seed
} else {
grid.seed ^ u64::from(l).wrapping_mul(0x9e3779b97f4a7c15)
},
..grid.clone()
};
let mut last = 0;
while last < 60 && grid_at(last + 1).h >= target.h_min {
last += 1;
}
let levels = Levels {
grid: &grid_at,
last,
rel_sigma: target.rel_sigma,
abs_sigma: target.abs_sigma,
base: grid.probes,
max_probes: target.max_probes,
};
let mut tracks: Vec<Track> = groups
.iter()
.enumerate()
.map(|(i, g)| Track {
level: Some(0),
volume: g.volume.clone(),
before: None,
next: if want[i] {
levels.next_step(&g.volume, 0, None, reach[i])
} else {
Step::Done
},
})
.collect();
let state = |tracks: &[Track], groups: &[Group]| {
let mut groups = groups.to_vec();
let mut h = vec![grid.h; groups.len()];
for (i, t) in tracks.iter().enumerate() {
groups[i].volume = t.volume.clone();
h[i] = grid_at(t.level.unwrap_or(0)).h;
}
let unconverged: Vec<usize> = (0..groups.len())
.filter(|&i| want[i] && tracks[i].next != Step::Done)
.collect();
let unseen = unconverged
.iter()
.copied()
.filter(|&i| groups[i].volume.segments == 0)
.collect();
Converged {
groups,
h,
unconverged,
unseen,
empty: empty.clone(),
listed_all,
}
};
let mut boxes = |tracks: &[Track], at: &[usize], g: &VolumeGrid| {
let mut todo: Vec<u32> = Vec::new();
let mut boxes: Vec<Aabb> = Vec::new();
for &i in at {
match cells[i] {
Some(cs) => todo.extend_from_slice(cs),
None => {
let pad = grid_at(tracks[i].level.unwrap_or(0)).spacing();
let b = tracks[i].volume.bbox;
boxes.push(
Aabb {
lo: b.lo.map(|x| x - pad),
hi: b.hi.map(|x| x + pad),
}
.intersect(&grid.region),
);
}
}
}
todo.sort_unstable();
todo.dedup();
let side = COVER_SPACINGS * g.spacing();
let covers: Vec<Vec<Aabb>> = todo
.par_iter()
.map(|&c| {
let mut out = Vec::new();
placed.cover(c, side, &mut out);
out
})
.collect();
boxes.extend(covers.into_iter().flatten());
boxes
};
let mut assign = |traced: &Volumes, at: &[usize], n: usize| {
let mut found: FxHashMap<GroupKey, Volume> = traced
.grouped(self, by)
.into_iter()
.map(|g| (group_key(&g), g.volume))
.collect();
at.iter()
.map(|&i| {
found
.remove(&group_key(&groups[i]))
.unwrap_or_else(|| Volume::empty(n))
})
.collect()
};
let mut report = |tracks: &[Track]| {
if let Some(each) = each.as_mut() {
each(&state(tracks, &groups));
}
};
self.refine(
&mut tracks,
&levels,
&reach,
&mut boxes,
&mut assign,
progress,
&mut report,
)?;
Ok(state(&tracks, &groups))
}
}