use std::mem;
use std::sync::Mutex;
use rayon::prelude::*;
use crate::classify::{decode, Depth, Label, Status, MAX_DEPTH};
use crate::error::{Error, Result};
use crate::expr::{self, Tri};
use crate::hit::Visibility;
use crate::intern;
use crate::lattice::{Element, Lattice};
use crate::model::Fill;
use crate::surface::Side;
use crate::vec3::{add, dot, norm, scale, Vec3};
use crate::work::Work;
use crate::Model;
#[derive(Clone, Copy, Debug, PartialEq)]
pub struct Line {
pub origin: Vec3,
pub dir: Vec3,
pub t_min: f64,
pub t_max: f64,
}
impl Line {
pub fn new(origin: Vec3, dir: Vec3, t_min: f64, t_max: f64) -> Line {
let n = norm(dir);
Line {
origin,
dir: scale(dir, 1.0 / n),
t_min,
t_max,
}
}
pub fn between(a: Vec3, b: Vec3) -> Line {
let d = crate::vec3::sub(b, a);
Line::new(a, d, 0.0, norm(d))
}
pub fn at(&self, t: f64) -> Vec3 {
add(self.origin, scale(self.dir, t))
}
}
pub const NO_SURFACE: u32 = u32::MAX;
#[derive(Clone, Debug, Default)]
pub struct Tracing {
pub offsets: Vec<usize>,
pub t0: Vec<f64>,
pub t1: Vec<f64>,
pub ids: Vec<u32>,
pub surface_in: Vec<u32>,
pub surface_out: Vec<u32>,
pub labels: Vec<Label>,
}
#[derive(Clone, Debug, PartialEq)]
pub struct Segment {
pub t0: f64,
pub t1: f64,
pub label: Label,
pub surface_in: Option<u32>,
pub surface_out: Option<u32>,
}
impl Tracing {
pub fn line_count(&self) -> usize {
self.offsets.len().saturating_sub(1)
}
pub fn segments(&self, i: usize) -> std::ops::Range<usize> {
self.offsets[i]..self.offsets[i + 1]
}
pub fn segment(&self, k: usize) -> Segment {
let s = |x: u32| (x != NO_SURFACE).then_some(x);
Segment {
t0: self.t0[k],
t1: self.t1[k],
label: self.labels[self.ids[k] as usize].clone(),
surface_in: s(self.surface_in[k]),
surface_out: s(self.surface_out[k]),
}
}
}
const LINE_CHUNK: usize = 64;
pub(crate) fn chunk_len(n: usize) -> usize {
(n / (8 * rayon::current_num_threads())).clamp(1, LINE_CHUNK)
}
const HIT_WINDOW: f64 = 16.0;
const SPAN_PAD: f64 = 1e-3;
const LATTICE_STEP: f64 = 1e-9;
const DEPTH_SHIFT: u32 = 26;
pub(crate) const MAX_SURFACES: usize = 1 << DEPTH_SHIFT;
#[inline]
fn bound(surface: u32, depth: usize) -> u32 {
surface | (depth as u32) << DEPTH_SHIFT
}
#[inline]
pub(crate) fn surface_of(b: u32) -> u32 {
if b == NO_SURFACE {
b
} else {
b & ((1 << DEPTH_SHIFT) - 1)
}
}
#[inline]
fn depth_of(b: u32) -> usize {
(b >> DEPTH_SHIFT) as usize
}
pub(crate) const IDENTITY: [Vec3; 3] = [[1.0, 0.0, 0.0], [0.0, 1.0, 0.0], [0.0, 0.0, 1.0]];
fn child_rotation(m: &[Vec3; 3], rot: &[Vec3; 3]) -> [Vec3; 3] {
let mut out = [[0.0; 3]; 3];
for i in 0..3 {
for j in 0..3 {
out[i][j] = (0..3).map(|k| m[i][k] * rot[j][k]).sum();
}
}
out
}
const SLIVER: f64 = 1e-6;
impl Model {
fn segment_agrees(&self, line: &Line, a: &Segment, b: &Segment, slack: [f64; 2]) -> bool {
let tol = 2.0 * self.tolerance;
let close = |x: f64, y: f64, s: f64| (x - y).abs() <= tol + s;
let same = |x: Option<u32>, y: Option<u32>, t: f64, s: f64| match (x, y) {
(Some(x), Some(y)) => {
let frames = self.path_frames(&a.label, line.at(t));
let near = |k: u32| {
frames
.iter()
.any(|&q| self.shapes[k as usize].side(q, 2.0 * tol + s) == Side::On)
};
self.surface_ids[x as usize] == self.surface_ids[y as usize]
|| self.shapes[x as usize] == self.shapes[y as usize]
|| (near(x) && near(y))
}
(x, y) => x == y,
};
a.label == b.label
&& close(a.t0, b.t0, slack[0])
&& close(a.t1, b.t1, slack[1])
&& same(a.surface_in, b.surface_in, a.t0, slack[0])
&& same(a.surface_out, b.surface_out, a.t1, slack[1])
}
pub(crate) fn traces_agree(&self, line: &Line, a: &[Segment], b: &[Segment]) -> bool {
let (a, b) = (without_slivers(a), without_slivers(b));
a.len() == b.len()
&& a.iter().zip(&b).all(|((x, sx), (y, sy))| {
let s = [sx[0].max(sy[0]), sx[1].max(sy[1])];
self.segment_agrees(line, x, y, s)
})
}
}
impl Model {
pub(crate) fn path_maps(&self, label: &Label) -> Vec<crate::transform::Affine> {
use crate::transform::Affine;
let mut g = Affine::IDENTITY;
let mut out = vec![g];
for step in &label.path {
let t = match (&self.cells[step.cell as usize].fill, step.lattice) {
(Some(Fill::Universe(t)), _) => t,
(Some(Fill::Lattice(l)), Some(ix)) => {
let lat = &self.lattices[*l as usize];
match lat.element(ix) {
Element::Fill(t) => {
let mut shift = [0.0; 3];
for i in 0..3 {
for (k, s) in shift.iter_mut().enumerate() {
*s -= lat.basis[i][k] * ix[i] as f64;
}
}
g = Affine::translation(shift).compose(&g);
t
}
_ => break,
}
}
_ => break,
};
if let Some(a) = t.transform() {
g = a.compose(&g);
}
out.push(g);
}
out
}
pub(crate) fn path_frames(&self, label: &Label, p: Vec3) -> Vec<Vec3> {
let mut out = vec![p];
let mut q = p;
for step in &label.path {
let t = match (&self.cells[step.cell as usize].fill, step.lattice) {
(Some(Fill::Universe(t)), _) => t,
(Some(Fill::Lattice(l)), Some(ix)) => {
let lat = &self.lattices[*l as usize];
match lat.element(ix) {
Element::Fill(t) => {
q = lat.to_element(q, ix);
t
}
_ => break,
}
}
_ => break,
};
q = t.apply(q);
out.push(q);
}
out
}
}
fn without_slivers(segs: &[Segment]) -> Vec<(Segment, [f64; 2])> {
let mut out: Vec<(Segment, [f64; 2])> = Vec::new();
let mut pending = 0.0;
for s in segs {
let len = s.t1 - s.t0;
if s.label.status == Status::OnSurface && len <= SLIVER {
pending += len;
if let Some(last) = out.last_mut() {
last.1[1] = last.1[1].max(pending);
}
continue;
}
if pending > 0.0 {
if let Some(last) = out.last_mut() {
if last.0.label == s.label {
last.0.t1 = s.t1;
last.0.surface_out = s.surface_out;
last.1[1] = 0.0;
pending = 0.0;
continue;
}
}
}
out.push((s.clone(), [pending, 0.0]));
pending = 0.0;
}
out
}
impl Model {
pub(crate) fn segments_agree(&self, line: &Line, a: &Segment, b: &Segment) -> bool {
self.segment_agrees(line, a, b, [0.0; 2])
}
pub fn trace(&self, lines: &[Line], depth: Depth) -> Result<Tracing> {
check_lines(lines)?;
Ok(self.trace_unchecked(lines, false, depth.level()))
}
pub fn trace_line(&self, line: &Line) -> Result<Vec<Segment>> {
let t = self.trace(std::slice::from_ref(line), Depth::All)?;
Ok(t.segments(0).map(|k| t.segment(k)).collect())
}
pub(crate) fn trace_unchecked(
&self,
lines: &[Line],
brute: bool,
level: Option<usize>,
) -> Tracing {
debug_assert!(check_lines(lines).is_ok());
debug_assert!(self.shapes.len() < MAX_SURFACES);
let threads = rayon::current_num_threads();
let tables: Vec<Mutex<intern::Chunk>> = (0..threads).map(|_| Mutex::default()).collect();
let parts: Vec<(Span, Part)> = lines
.par_chunks(chunk_len(lines.len()))
.map_init(
|| {
let mut tr = Tracer::new(self, brute);
tr.set_level(level);
tr
},
|tr, chunk| {
let t = rayon::current_thread_index().unwrap_or(0) % threads;
let mut table = tables[t].lock().unwrap_or_else(|e| e.into_inner());
let mut part = Part {
chunk: mem::take(&mut *table),
..Part::default()
};
let start = part.chunk.ids.len();
for l in chunk {
tr.line(l, &mut part);
}
let span = (t, start, part.chunk.ids.len());
*table = mem::take(&mut part.chunk);
(span, part)
},
)
.collect();
let tables: Vec<intern::Chunk> = tables
.into_iter()
.map(|t| t.into_inner().unwrap_or_else(|e| e.into_inner()))
.collect();
let (spans, parts): (Vec<Span>, Vec<Part>) = parts.into_iter().unzip();
let mut out = segments(&parts, lines.len());
drop(parts);
let (canon, keys) = intern::merge(&tables);
let mut base = Vec::with_capacity(tables.len());
let mut at = 0;
for t in &tables {
base.push(at);
at += t.ids.len();
}
let mut number = vec![u32::MAX; keys.len()];
let mut order: Vec<u32> = Vec::with_capacity(keys.len());
out.ids = Vec::with_capacity(canon.len());
for &(t, s, e) in &spans {
for &c in &canon[base[t] + s..base[t] + e] {
let n = &mut number[c as usize];
if *n == u32::MAX {
*n = order.len() as u32;
order.push(c);
}
out.ids.push(*n);
}
}
out.labels = order
.par_iter()
.map(|&c| decode(keys[c as usize]))
.collect();
out
}
pub(crate) fn trace_few(&self, lines: &[Line], level: Option<usize>) -> Tracing {
debug_assert!(check_lines(lines).is_ok());
let mut tr = Tracer::new(self, false);
tr.set_level(level);
let mut part = Part::default();
for l in lines {
tr.line(l, &mut part);
}
assemble(vec![part], lines.len(), false)
}
pub(crate) fn trace_part(&self, lines: &[Line]) -> Part {
debug_assert!(check_lines(lines).is_ok());
let mut tr = Tracer::new(self, false);
let mut part = Part::default();
for l in lines {
tr.line(l, &mut part);
}
part
}
}
fn assemble(parts: Vec<Part>, lines: usize, parallel: bool) -> Tracing {
let mut out = segments(&parts, lines);
let chunks: Vec<intern::Chunk> = parts.into_iter().map(|p| p.chunk).collect();
let (ids, keys) = intern::merge(&chunks);
out.ids = ids;
out.labels = if parallel {
keys.par_iter().map(|k| decode(k)).collect()
} else {
keys.iter().map(|k| decode(k)).collect()
};
out
}
type Span = (usize, usize, usize);
fn segments(parts: &[Part], lines: usize) -> Tracing {
let mut offsets = Vec::with_capacity(lines + 1);
offsets.push(0);
for p in parts {
for &n in &p.counts {
offsets.push(offsets.last().unwrap() + n as usize);
}
}
Tracing {
offsets,
t0: concat(parts, |p| &p.t0),
t1: concat(parts, |p| &p.t1),
surface_in: concat(parts, |p| &p.surface_in),
surface_out: concat(parts, |p| &p.surface_out),
..Tracing::default()
}
}
pub(crate) fn check_lines(lines: &[Line]) -> Result<()> {
let ok = |l: &Line| {
l.t_min.is_finite()
&& l.t_max.is_finite()
&& l.t_min <= l.t_max
&& (norm(l.dir) - 1.0).abs() < 1e-6
};
match lines.iter().position(|l| !ok(l)) {
None => Ok(()),
Some(index) => Err(Error::Line {
index,
line: lines[index],
}),
}
}
fn concat<T: Copy + Default + Send + Sync>(
parts: &[Part],
field: impl Fn(&Part) -> &Vec<T> + Sync,
) -> Vec<T> {
let total = parts.iter().map(|p| field(p).len()).sum();
let mut out = vec![T::default(); total];
let mut slices = Vec::with_capacity(parts.len());
let mut rest: &mut [T] = &mut out;
for p in parts {
let (head, tail) = rest.split_at_mut(field(p).len());
slices.push(head);
rest = tail;
}
slices
.into_par_iter()
.zip(parts)
.for_each(|(dst, p)| dst.copy_from_slice(field(p)));
out
}
#[derive(Default)]
pub(crate) struct Part {
pub(crate) chunk: intern::Chunk,
pub(crate) counts: Vec<u32>,
pub(crate) t0: Vec<f64>,
pub(crate) t1: Vec<f64>,
surface_in: Vec<u32>,
surface_out: Vec<u32>,
}
struct Seg {
t0: f64,
t1: f64,
s0: u32,
s1: u32,
key: (usize, usize),
}
#[derive(Clone, Copy, PartialEq, Eq)]
enum Kind {
True,
Unknown,
Unsupported,
}
#[derive(Clone, Copy)]
struct Run {
t0: f64,
t1: f64,
s0: u32,
s1: u32,
cell: u32,
kind: Kind,
}
#[derive(Clone, Copy)]
struct Cluster {
first: f64,
rep: f64,
surface: u32,
}
#[derive(Clone, Copy)]
struct Piece {
t0: f64,
t1: f64,
s0: u32,
s1: u32,
status: Status,
cells: (usize, usize),
}
#[derive(Default)]
struct Level {
cands: Vec<(u32, f64, f64)>,
tmp_cands: Vec<(u32, f64, f64)>,
items: Vec<(u32, u32)>,
full: Vec<u32>,
cache: Vec<(u32, u32, u32, u32)>,
roots: Vec<f64>,
tmp: Vec<f64>,
cross: Vec<(f64, u32)>,
leaves: Vec<u32>,
runs: Vec<Run>,
ends: Vec<(f64, u32, bool)>,
clusters: Vec<Cluster>,
active: Vec<usize>,
set: Vec<u32>,
pieces: Vec<Piece>,
piece_cells: Vec<u32>,
breaks: Vec<(f64, u32)>,
elements: Vec<(f64, f64, u32, u32, [i32; 3])>,
}
pub(crate) struct Tracer<'m> {
m: &'m Model,
brute: bool,
levels: Vec<Level>,
slot: Vec<u32>,
path: Vec<u32>,
segs: Vec<Seg>,
keys: Vec<u32>,
frames: Vec<(Vec3, Vec3, [Vec3; 3])>,
max_level: usize,
pub(crate) hit: Option<HitSearch<'m>>,
pub(crate) work: Option<Work>,
}
pub(crate) struct HitSearch<'v> {
pub vis: &'v Visibility,
pub skip: Option<&'v crate::skip::Skip>,
pub found: Option<FoundHit>,
pub ghosts: Option<Vec<GhostStretch>>,
pub veils: crate::hit::Veils,
}
#[derive(Clone, Copy, Debug)]
pub(crate) struct GhostStretch {
cell: u32,
t0: f64,
s0: u32,
n0: Vec3,
t1: f64,
s1: u32,
n1: Vec3,
}
pub(crate) struct FoundHit {
pub t: f64,
pub surface: u32,
pub normal: Vec3,
pub key: (usize, usize),
}
#[inline]
fn at(o: Vec3, d: Vec3, t: f64) -> Vec3 {
add(o, scale(d, t))
}
#[inline]
fn mid(a: f64, b: f64) -> f64 {
a + 0.5 * (b - a)
}
thread_local! {
static SLOT: std::cell::RefCell<Vec<u32>> = const { std::cell::RefCell::new(Vec::new()) };
}
impl Drop for Tracer<'_> {
fn drop(&mut self) {
if !self.slot.is_empty() {
let slot = mem::take(&mut self.slot);
let _ = SLOT.try_with(|s| *s.borrow_mut() = slot);
}
}
}
impl<'m> Tracer<'m> {
pub(crate) fn new(m: &'m Model, brute: bool) -> Self {
Tracer {
m,
brute,
levels: Vec::new(),
slot: Vec::new(),
path: Vec::new(),
segs: Vec::new(),
keys: Vec::new(),
frames: Vec::new(),
max_level: MAX_DEPTH,
hit: None,
work: None,
}
}
pub(crate) fn set_level(&mut self, level: Option<usize>) {
self.max_level = level.map_or(MAX_DEPTH, |k| k.min(MAX_DEPTH));
}
#[inline]
fn done(&self) -> bool {
self.hit.as_ref().is_some_and(|h| h.found.is_some())
}
pub(crate) fn first_hit(&mut self, l: &Line) -> Option<FoundHit> {
self.keys.clear();
self.path.clear();
if let Some(h) = self.hit.as_mut() {
h.found = None;
h.veils = Default::default();
if let Some(g) = h.ghosts.as_mut() {
g.clear();
}
}
let spans = match self.hit.as_ref().and_then(|h| h.skip) {
Some(s) => s.spans(self.m, 0, l.origin, l.dir, (l.t_min, l.t_max), SPAN_PAD),
None => vec![(l.t_min, l.t_max)],
};
for (t0, t1) in spans {
let (mut ta, mut w) = (t0, HIT_WINDOW.max(t0 - l.t_min));
loop {
let tb = if t1 - ta <= 2.0 * w { t1 } else { ta + w };
self.unit(
0, l.origin, l.dir, ta, tb, NO_SURFACE, NO_SURFACE, 0, IDENTITY,
);
if self.done() {
return self.hit.as_mut().and_then(|h| h.found.take());
}
self.keys.clear();
self.path.clear();
if tb >= t1 {
break;
}
(ta, w) = (tb, 2.0 * w);
}
}
None
}
pub(crate) fn keys(&self) -> &[u32] {
&self.keys
}
pub(crate) fn ghost(&self, t_hit: f64) -> crate::hit::Ghost {
let mut out = crate::hit::Ghost::default();
let Some(stretches) = self.hit.as_ref().and_then(|h| h.ghosts.as_ref()) else {
return out;
};
let tol = self.m.tolerance;
let mut ends: Vec<(f64, u8, u32, Vec3)> = Vec::new();
for g in stretches {
if g.s0 != NO_SURFACE && g.t0 <= t_hit + tol {
ends.push((g.t0, 0, g.cell, g.n0));
}
if g.s1 != NO_SURFACE && g.t1 <= t_hit + tol {
ends.push((g.t1, 1, g.cell, g.n1));
}
}
ends.sort_by(|a, b| a.0.total_cmp(&b.0).then(a.1.cmp(&b.1)));
let mut last = f64::NEG_INFINITY;
for (t, _, cell, n) in ends {
if t - last > tol {
if out.count == 0 {
(out.t, out.cell, out.normal) = (t, cell, n);
}
out.count += 1;
}
last = t;
}
out
}
fn ghost_stretch(&mut self, c: u32, t0: f64, t1: f64, s0: u32, s1: u32) {
let n0 = self.normal(t0, s0);
let n1 = self.normal(t1, s1);
let Some(g) = self.hit.as_mut().and_then(|h| h.ghosts.as_mut()) else {
return;
};
if let Some(prev) = g.iter_mut().rev().find(|x| x.cell == c && x.t1 == t0) {
(prev.t1, prev.s1, prev.n1) = (t1, s1, n1);
return;
}
g.push(GhostStretch {
cell: c,
t0,
s0,
n0,
t1,
s1,
n1,
});
}
pub(crate) fn veils(&self) -> crate::hit::Veils {
self.hit.as_ref().map(|h| h.veils).unwrap_or_default()
}
#[cfg(feature = "bench")]
pub(crate) fn trace_one(&mut self, l: &Line) {
self.segs.clear();
self.keys.clear();
self.path.clear();
self.unit(
0, l.origin, l.dir, l.t_min, l.t_max, NO_SURFACE, NO_SURFACE, 0, IDENTITY,
);
}
fn line(&mut self, l: &Line, part: &mut Part) {
self.segs.clear();
self.keys.clear();
self.path.clear();
self.unit(
0, l.origin, l.dir, l.t_min, l.t_max, NO_SURFACE, NO_SURFACE, 0, IDENTITY,
);
part.counts.push(self.segs.len() as u32);
for s in &self.segs {
part.chunk.push(&self.keys[s.key.0..s.key.1]);
part.t0.push(s.t0);
part.t1.push(s.t1);
part.surface_in.push(surface_of(s.s0));
part.surface_out.push(surface_of(s.s1));
}
}
fn emit(&mut self, t0: f64, t1: f64, s0: u32, s1: u32, status: Status, cells: &[u32]) {
if let Some(h) = &self.hit {
if h.found.is_some() || !h.vis.shows(status) {
return;
}
let holder = (self.path.len() >= 5).then(|| self.path[self.path.len() - 5]);
if !h.vis.owns(status, holder, cells) {
return;
}
if h.vis.veils(status) {
let Some(h) = &mut self.hit else {
unreachable!()
};
h.veils.gap |= status == Status::Gap;
h.veils.overlap |= status == Status::Overlap;
return;
}
if status == Status::Inside {
let depth = self.path.len() / 5;
if h.vis.level.is_some_and(|k| depth != k + 1)
|| h.vis.is_ghost(self.path[self.path.len() - 5])
{
return;
}
}
}
let start = self.keys.len();
self.keys.push(status as u32);
self.keys.push((self.path.len() / 5) as u32);
self.keys.extend_from_slice(&self.path);
self.keys.extend_from_slice(cells);
if let Some(prev) = self.segs.last_mut() {
if prev.t1 == t0 && self.keys[prev.key.0..prev.key.1] == self.keys[start..] {
prev.t1 = t1;
prev.s1 = s1;
self.keys.truncate(start);
return;
}
}
let key = (start, self.keys.len());
if self.hit.is_some() {
let normal = self.normal(t0, s0);
let Some(h) = &mut self.hit else {
unreachable!()
};
h.found = Some(FoundHit {
t: t0,
surface: surface_of(s0),
normal,
key,
});
return;
}
self.segs.push(Seg {
t0,
t1,
s0,
s1,
key,
});
}
fn normal(&self, t: f64, b: u32) -> Vec3 {
if b == NO_SURFACE {
return [0.0; 3];
}
let (o, d, rot) = self.frames[depth_of(b)];
let g = self.m.shapes[surface_of(b) as usize].gradient(at(o, d, t));
let n = [0, 1, 2].map(|i| dot(rot[i], g));
let len = norm(n);
if len == 0.0 {
return [0.0; 3];
}
let s = if dot(n, self.frames[0].1) > 0.0 {
-1.0
} else {
1.0
} / len;
scale(n, s)
}
#[allow(clippy::too_many_arguments)]
fn unit(
&mut self,
unit: u32,
o: Vec3,
d: Vec3,
ta: f64,
tb: f64,
sa: u32,
sb: u32,
depth: usize,
rot: [Vec3; 3],
) {
if depth >= MAX_DEPTH {
self.emit(ta, tb, sa, sb, Status::TooDeep, &[]);
return;
}
self.frames.truncate(depth);
self.frames.push((o, d, rot));
if self.levels.len() <= depth {
self.levels.resize_with(depth + 1, Level::default);
}
let m = self.m;
let mut lv = mem::take(&mut self.levels[depth]);
if self.slot.is_empty() {
let old = SLOT.with_borrow_mut(mem::take);
self.slot = if old.len() == m.shapes.len() {
old
} else {
vec![0; m.shapes.len()]
};
}
let mut slot = mem::take(&mut self.slot);
let [crossed, midpoints, evals] =
self.pieces(&mut lv, &mut slot, unit, o, d, ta, tb, sa, sb, depth);
self.slot = slot;
if let Some(w) = self.work.as_mut() {
let l = w.level(depth);
l.visits += 1;
l.candidates += lv.cands.len() as u64;
l.surfaces_crossed += crossed;
l.midpoints += midpoints;
l.surface_evals += evals;
}
for i in 0..lv.pieces.len() {
if self.done() {
break;
}
let p = lv.pieces[i];
let cells = &lv.piece_cells[p.cells.0..p.cells.1];
if p.status != Status::Inside {
self.emit(p.t0, p.t1, p.s0, p.s1, p.status, cells);
continue;
}
let c = cells[0];
if let Some(h) = &self.hit {
if !h.vis.cells[c as usize] {
continue;
}
if h.ghosts.is_some() && h.vis.is_ghost(c) {
self.ghost_stretch(c, p.t0, p.t1, p.s0, p.s1);
}
}
self.path.extend_from_slice(&[c, 0, 0, 0, 0]);
let last = depth >= self.max_level;
match &m.cells[c as usize].fill {
None => self.emit(p.t0, p.t1, p.s0, p.s1, Status::Inside, &[]),
Some(Fill::Universe(_)) if last => {
self.emit(p.t0, p.t1, p.s0, p.s1, Status::Inside, &[])
}
Some(Fill::Universe(t)) => {
let (o2, d2, r2) = match &t.transform {
Some(tr) => (tr.apply(o), tr.apply_dir(d), child_rotation(&rot, &tr.rot)),
None => (o, d, rot),
};
self.unit(t.unit, o2, d2, p.t0, p.t1, p.s0, p.s1, depth + 1, r2);
}
Some(Fill::Lattice(l)) => {
let lat = &m.lattices[*l as usize];
let mut els = mem::take(&mut lv.elements);
lattice_pieces(
lat,
o,
d,
p.t0,
p.t1,
p.s0,
p.s1,
depth,
m.tolerance,
&mut lv.breaks,
&mut els,
);
let n = self.path.len();
for &(a, b, sa2, sb2, ix) in &els {
if self.done() {
break;
}
self.path[n - 4..].copy_from_slice(&[
1,
ix[0] as u32,
ix[1] as u32,
ix[2] as u32,
]);
match lat.element(ix) {
Element::Fill(_) if last => {
self.emit(a, b, sa2, sb2, Status::Inside, &[])
}
Element::Fill(t) => {
let q = lat.to_element(o, ix);
let (o2, d2, r2) = match &t.transform {
Some(tr) => (
tr.apply(q),
tr.apply_dir(d),
child_rotation(&rot, &tr.rot),
),
None => (q, d, rot),
};
self.unit(t.unit, o2, d2, a, b, sa2, sb2, depth + 1, r2);
}
Element::Own => self.emit(a, b, sa2, sb2, Status::Inside, &[]),
Element::Missing => self.emit(a, b, sa2, sb2, Status::Gap, &[]),
}
}
lv.elements = els;
}
}
self.path.truncate(self.path.len() - 5);
}
self.levels[depth] = lv;
}
#[allow(clippy::too_many_arguments)]
fn pieces(
&self,
lv: &mut Level,
slot: &mut [u32],
unit: u32,
o: Vec3,
d: Vec3,
ta: f64,
tb: f64,
sa: u32,
sb: u32,
depth: usize,
) -> [u64; 3] {
self.candidates(lv, unit, o, d, ta, tb);
let mut work = [0u64; 3];
lv.cache.clear();
lv.roots.clear();
lv.runs.clear();
for ci in 0..lv.cands.len() {
self.cell_runs(lv, slot, unit, ci, o, d, ta, tb, depth, &mut work);
}
snap(lv, ta, tb, sa, sb, self.m.tolerance);
sweep(lv);
work
}
#[allow(clippy::too_many_arguments)]
fn cell_runs(
&self,
lv: &mut Level,
slot: &mut [u32],
unit: u32,
ci: usize,
o: Vec3,
d: Vec3,
ta: f64,
tb: f64,
depth: usize,
[crossed, midpoints, evals]: &mut [u64; 3],
) {
let m = self.m;
let u = &m.units[unit as usize];
let counting = self.work.is_some();
let (c, lo, hi) = lv.cands[ci];
let cell = &m.cells[c as usize];
if cell.unsupported.is_some() || m.is_lattice(c) {
let kind = if cell.unsupported.is_some() {
Kind::Unsupported
} else {
Kind::True
};
lv.runs.push(Run {
t0: lo,
t1: hi,
s0: NO_SURFACE,
s1: NO_SURFACE,
cell: c,
kind,
});
return;
}
let items = self.cell_items(lv, u.grid.is_some(), c);
self.cell_crossings(lv, slot, unit, ci, items, o, d, ta, tb, depth, crossed);
lv.cross.push((hi, NO_SURFACE));
let (mut prev, mut sprev) = (lo, NO_SURFACE);
let mut open: Option<Run> = None;
for k in 0..lv.cross.len() {
let (t, s) = lv.cross[k];
if t > prev {
let q = at(o, d, mid(prev, t));
let boxes = (!self.brute && u.roi.contains(q)).then(|| m.node_boxes_of(c));
let code = match (items, &u.grid) {
(Some(_), Some(g)) => match g.leaf_span(q) {
Some((first, n)) => {
match g.items[first..first + n].iter().position(|&x| x == c) {
Some(i) => Ok(g.prog(first + i, m.code(c))),
None => Err(Tri::False),
}
}
None => Ok(Some(m.code(c))),
},
_ => Ok(Some(m.code(c))),
};
*midpoints += counting as u64;
let v = match code {
Err(v) => v,
Ok(None) => Tri::True,
Ok(Some(code)) if counting => m.eval_code_counted(code, q, boxes, evals),
Ok(Some(code)) => m.eval_code(code, q, boxes),
};
let kind = match v {
Tri::True => Some(Kind::True),
Tri::Unknown => Some(Kind::Unknown),
Tri::False => None,
};
match (&mut open, kind) {
(Some(r), Some(k)) if r.kind == k => {
r.t1 = t;
r.s1 = s;
}
(_, kind) => {
if let Some(r) = open.take() {
lv.runs.push(r);
}
open = kind.map(|kind| Run {
t0: prev,
t1: t,
s0: sprev,
s1: s,
cell: c,
kind,
});
}
}
}
prev = t;
sprev = s;
}
if let Some(r) = open {
lv.runs.push(r);
}
}
#[allow(clippy::too_many_arguments)]
fn cell_crossings(
&self,
lv: &mut Level,
slot: &mut [u32],
unit: u32,
ci: usize,
items: Option<(usize, usize)>,
o: Vec3,
d: Vec3,
ta: f64,
tb: f64,
depth: usize,
crossed: &mut u64,
) {
let m = self.m;
let u = &m.units[unit as usize];
let (c, lo, hi) = lv.cands[ci];
lv.cross.clear();
let (pa, pb) = (at(o, d, lo), at(o, d, hi));
let prune = !self.brute && u.roi.contains(pa) && u.roi.contains(pb);
let mut leaves = std::mem::take(&mut lv.leaves);
leaves.clear();
let add = |code: &[u32], leaves: &mut Vec<u32>| {
if prune {
expr::leaves_where(
code,
m.node_boxes_of(c),
&mut |b| b.ray_range(o, d, lo, hi).is_some(),
&mut |s| leaves.push(s),
);
} else {
leaves.extend(expr::leaves(code).map(|(s, _)| s));
}
};
match (items, &u.grid) {
(Some((a, b)), Some(g)) => {
for &(_, k) in &lv.items[a..b] {
if let Some(code) = g.prog(k as usize, m.code(c)) {
add(code, &mut leaves);
}
}
}
_ => add(m.code(c), &mut leaves),
}
for &s in &leaves {
let (start, len) = match lv.cache.get_mut(slot[s as usize] as usize) {
Some(e) if e.0 == s && e.3 == ci as u32 => continue,
Some(e) if e.0 == s => {
e.3 = ci as u32;
(e.1, e.2)
}
_ => {
*crossed += 1;
lv.tmp.clear();
m.shapes[s as usize].crossings(o, d, ta, tb, &mut lv.tmp);
lv.tmp.sort_by(f64::total_cmp);
lv.tmp.dedup();
let r = (lv.roots.len() as u32, lv.tmp.len() as u32);
lv.roots.extend_from_slice(&lv.tmp);
slot[s as usize] = lv.cache.len() as u32;
lv.cache.push((s, r.0, r.1, ci as u32));
r
}
};
let roots = &lv.roots[start as usize..(start + len) as usize];
let first = roots.partition_point(|&t| t <= lo);
for &t in &roots[first..] {
if t >= hi {
break;
}
lv.cross.push((t, bound(s, depth)));
}
}
lv.leaves = leaves;
lv.cross.sort_by(|a, b| {
a.0.total_cmp(&b.0)
.then(surface_of(a.1).cmp(&surface_of(b.1)))
});
}
fn candidates(&self, lv: &mut Level, unit: u32, o: Vec3, d: Vec3, ta: f64, tb: f64) {
let m = self.m;
let u = &m.units[unit as usize];
let cands = &mut lv.cands;
cands.clear();
lv.items.clear();
lv.full.clear();
let all = |a: f64, b: f64, cands: &mut Vec<(u32, f64, f64)>| {
cands.extend(u.cells.iter().map(|&c| (c, a, b)));
};
let outside = |a: f64, b: f64, cands: &mut Vec<(u32, f64, f64)>| {
cands.extend(u.outside().iter().map(|&c| (c, a, b)));
};
let Some((ra, rb)) = u.roi.ray_range(o, d, ta, tb) else {
outside(ta, tb, cands);
return;
};
if ra > ta {
outside(ta, ra, cands);
}
if rb < tb {
outside(rb, tb, cands);
}
if self.brute {
all(ra, rb, cands);
hull_per_cell(cands);
return;
}
let bvh = |a: f64, b: f64, cands: &mut Vec<(u32, f64, f64)>| {
u.bvh.query_ray(o, d, a, b, |c, x, y| cands.push((c, x, y)));
};
match u
.grid
.as_ref()
.and_then(|g| g.root.ray_range(o, d, ra, rb).map(|r| (g, r)))
{
Some((g, (ga, gb))) => {
if ga > ra {
bvh(ra, ga, cands);
}
if gb < rb {
bvh(gb, rb, cands);
}
let tmp = &mut lv.tmp_cands;
tmp.clear();
let items = &mut lv.items;
g.walk(o, d, ga, gb, |first, leaf, a, b| {
tmp.extend(leaf.iter().map(|&c| (c, a, b)));
items.extend(
leaf.iter()
.enumerate()
.map(|(i, &c)| (c, (first + i) as u32)),
);
});
hull_per_cell(tmp);
lv.full.extend(cands.iter().map(|e| e.0));
cands.extend(tmp.iter().filter_map(|&(c, a, b)| {
let (x, y) = m.cells[c as usize].bbox.ray_range(o, d, a, b)?;
Some((c, x, y))
}));
lv.items.sort_unstable();
lv.items.dedup();
}
None => bvh(ra, rb, cands),
}
cands.extend(u.always.iter().map(|&c| (c, ra, rb)));
if lv.items.is_empty() {
lv.full.clear();
} else {
lv.full.extend(u.always.iter().copied());
lv.full.sort_unstable();
lv.full.dedup();
}
hull_per_cell(cands);
}
fn cell_items(&self, lv: &Level, grid: bool, c: u32) -> Option<(usize, usize)> {
if self.brute || !grid || lv.full.binary_search(&c).is_ok() {
return None;
}
let a = lv.items.partition_point(|e| e.0 < c);
let b = lv.items.partition_point(|e| e.0 <= c);
(a < b).then_some((a, b))
}
}
fn hull_per_cell(cands: &mut Vec<(u32, f64, f64)>) {
cands.sort_unstable_by(|a, b| a.0.cmp(&b.0).then(a.1.total_cmp(&b.1)));
let mut w = 0;
for r in 0..cands.len() {
let e = cands[r];
if w > 0 && cands[w - 1].0 == e.0 {
cands[w - 1].2 = cands[w - 1].2.max(e.2);
} else {
cands[w] = e;
w += 1;
}
}
cands.truncate(w);
}
fn snap(lv: &mut Level, ta: f64, tb: f64, sa: u32, sb: u32, tol: f64) {
lv.ends.clear();
lv.ends.push((ta, sa, true));
lv.ends.push((tb, sb, true));
for r in &lv.runs {
lv.ends.push((r.t0, r.s0, false));
lv.ends.push((r.t1, r.s1, false));
}
lv.ends
.sort_by(|a, b| a.0.total_cmp(&b.0).then(b.2.cmp(&a.2)));
lv.clusters.clear();
let snapping = tb - ta > tol;
let mut i = 0;
while i < lv.ends.len() {
let first = lv.ends[i].0;
let mut j = i;
let (mut rep, mut surface, mut anchored, mut fixed) = (first, NO_SURFACE, false, false);
while j < lv.ends.len()
&& (lv.ends[j].0 == first || (snapping && lv.ends[j].0 - first <= tol))
{
let (t, s, anchor) = lv.ends[j];
if anchor && !anchored {
(rep, anchored) = (t, true);
if s != NO_SURFACE {
(surface, fixed) = (s, true);
}
} else if !fixed
&& s != NO_SURFACE
&& (surface == NO_SURFACE || surface_of(s) < surface_of(surface))
{
surface = s;
}
j += 1;
}
lv.clusters.push(Cluster {
first,
rep,
surface,
});
i = j;
}
let clusters = &lv.clusters;
let find = |t: f64| clusters[clusters.partition_point(|c| c.first <= t) - 1];
for r in &mut lv.runs {
r.t0 = find(r.t0).rep;
r.t1 = find(r.t1).rep;
}
lv.runs.retain(|r| r.t0 < r.t1);
}
fn sweep(lv: &mut Level) {
lv.pieces.clear();
lv.piece_cells.clear();
lv.runs
.sort_by(|a, b| a.t0.total_cmp(&b.t0).then(a.cell.cmp(&b.cell)));
lv.active.clear();
let mut next = 0;
let reps: Vec<(f64, u32)> = {
let mut v: Vec<(f64, u32)> = lv.clusters.iter().map(|c| (c.rep, c.surface)).collect();
v.dedup_by(|b, a| a.0 == b.0);
v
};
for w in reps.windows(2) {
let ((x, sx), (y, sy)) = (w[0], w[1]);
if !(y > x) {
continue;
}
lv.active.retain(|&r| lv.runs[r].t1 > x);
while next < lv.runs.len() && lv.runs[next].t0 <= x {
if lv.runs[next].t1 > x {
lv.active.push(next);
}
next += 1;
}
let pick = |kind: Kind, set: &mut Vec<u32>| {
set.clear();
set.extend(
lv.active
.iter()
.map(|&r| &lv.runs[r])
.filter(|r| r.kind == kind)
.map(|r| r.cell),
);
set.sort_unstable();
set.dedup();
};
let mut set = mem::take(&mut lv.set);
pick(Kind::True, &mut set);
let status = match set.len() {
1 => Status::Inside,
n if n > 1 => Status::Overlap,
_ => {
pick(Kind::Unsupported, &mut set);
if !set.is_empty() {
Status::Unsupported
} else {
pick(Kind::Unknown, &mut set);
if set.is_empty() {
Status::Gap
} else {
Status::OnSurface
}
}
}
};
if let Some(p) = lv.pieces.last_mut() {
if p.t1 == x && p.status == status && lv.piece_cells[p.cells.0..p.cells.1] == set[..] {
p.t1 = y;
p.s1 = sy;
lv.set = set;
continue;
}
}
let start = lv.piece_cells.len();
lv.piece_cells.extend_from_slice(&set);
lv.pieces.push(Piece {
t0: x,
t1: y,
s0: sx,
s1: sy,
status,
cells: (start, lv.piece_cells.len()),
});
lv.set = set;
}
}
#[allow(clippy::too_many_arguments)]
fn lattice_pieces(
lat: &Lattice,
o: Vec3,
d: Vec3,
s0: f64,
s1: f64,
sa: u32,
sb: u32,
depth: usize,
tol: f64,
breaks: &mut Vec<(f64, u32)>,
out: &mut Vec<(f64, f64, u32, u32, [i32; 3])>,
) {
breaks.clear();
breaks.push((s0, sa));
let mut t = s0;
let mut ix = lat.index(at(o, d, t));
let mut step = LATTICE_STEP;
while t < s1 {
let (lo, hi, exit) = lat.element_range(o, d, ix);
if lo <= t + step && hi > t + step {
if hi >= s1 {
break;
}
let last = breaks.last().unwrap().0;
if hi - last > tol && s1 - hi > tol {
breaks.push((
hi,
exit.map_or(NO_SURFACE, |k| bound(lat.face_surfaces[k], depth)),
));
}
(t, step) = (hi, LATTICE_STEP);
continue;
}
let mut best: Option<(f64, [i32; 3])> = None;
for nb in lat.neighbours(ix) {
let (l, h, _) = lat.element_range(o, d, nb);
if l <= t + step && h > t + step && best.is_none_or(|b| h < b.0) {
best = Some((h, nb));
}
}
match best {
Some((_, nb)) => ix = nb,
None => {
step *= 8.0;
if t + step >= s1 {
break;
}
ix = lat.index(at(o, d, t + step));
}
}
}
breaks.push((s1, sb));
out.clear();
for w in breaks.windows(2) {
let ((a, sin), (b, sout)) = (w[0], w[1]);
let ix = lat.index(at(o, d, mid(a, b)));
match out.last_mut() {
Some(p) if p.4 == ix => {
p.1 = b;
p.3 = sout;
}
_ => out.push((a, b, sin, sout, ix)),
}
}
}