use crate::bbox::Aabb;
use crate::expr;
use crate::surface::Shape;
use crate::transform::Affine;
use crate::vec3::{add, cross, dot, norm, scale, sub, Vec3};
#[derive(Clone, Debug, serde::Serialize, serde::Deserialize)]
pub struct Target {
pub(crate) unit: u32,
pub(crate) transform: Option<Affine>,
}
impl Target {
pub fn unit(&self) -> u32 {
self.unit
}
pub fn transform(&self) -> Option<&Affine> {
self.transform.as_ref()
}
#[inline]
pub fn apply(&self, p: Vec3) -> Vec3 {
match &self.transform {
Some(t) => t.apply(p),
None => p,
}
}
}
#[derive(Clone, Debug, serde::Serialize, serde::Deserialize)]
pub(crate) enum LatticeFill {
Uniform(Target),
Array {
lo: [i32; 3],
size: [i32; 3],
elements: Vec<Option<Target>>,
},
}
#[derive(Clone, Copy, Debug)]
pub enum Element<'a> {
Fill(&'a Target),
Own,
Missing,
}
#[derive(Clone, Debug, serde::Serialize, serde::Deserialize)]
pub struct Lattice {
pub(crate) hexagonal: bool,
pub(crate) center: Vec3,
pub(crate) basis: [Vec3; 3],
pub(crate) dual: [Vec3; 3],
pub(crate) bounded: [bool; 3],
pub(crate) sides: Vec<(Vec3, f64)>,
pub(crate) faces: Vec<(Vec3, f64)>,
pub(crate) face_surfaces: Vec<u32>,
pub(crate) fill: LatticeFill,
}
impl Lattice {
pub fn hexagonal(&self) -> bool {
self.hexagonal
}
#[inline]
pub fn index(&self, p: Vec3) -> [i32; 3] {
let d = sub(p, self.center);
let mut ix = [0i32; 3];
for i in 0..3 {
if self.bounded[i] {
ix[i] = (dot(self.dual[i], d) + 0.5).floor() as i32;
}
}
if self.hexagonal {
let (i0, j0) = (ix[0], ix[1]);
let mut best = (f64::NEG_INFINITY, i0, j0);
for di in -1..=1 {
for dj in -1..=1 {
let (i, j) = (i0 + di, j0 + dj);
let q = sub(
sub(p, scale(self.basis[0], i as f64)),
scale(self.basis[1], j as f64),
);
let margin = self
.sides
.iter()
.map(|(n, dd)| dd - dot(*n, q))
.fold(f64::INFINITY, f64::min);
if margin > best.0 {
best = (margin, i, j);
}
}
}
ix[0] = best.1;
ix[1] = best.2;
}
ix
}
#[inline]
pub(crate) fn to_element(&self, p: Vec3, ix: [i32; 3]) -> Vec3 {
let mut q = p;
for i in 0..3 {
if ix[i] != 0 {
q = sub(q, scale(self.basis[i], ix[i] as f64));
}
}
q
}
pub(crate) fn element_box(&self, ix: [i32; 3]) -> Aabb {
let mut planes = self.faces.clone();
for i in 0..3 {
if !self.bounded[i] {
let a = self.basis[i];
planes.push((a, dot(a, self.center) + 1.0));
planes.push((scale(a, -1.0), 1.0 - dot(a, self.center)));
}
}
let scale_len = planes
.iter()
.map(|(_, d)| d.abs())
.fold(norm(self.center), f64::max)
.max(1.0);
let tol = 1e-9 * scale_len;
let mut b = Aabb::EMPTY;
let n = planes.len();
for i in 0..n {
for j in i + 1..n {
for k in j + 1..n {
let Ok(p) = meet(planes[i], planes[j], planes[k]) else {
continue;
};
if planes.iter().all(|(m, d)| dot(*m, p) <= d + tol) {
b.grow_point(p);
}
}
}
}
if b.is_empty() {
return Aabb::INFINITE;
}
let pad = 1e-6 * scale_len;
let shift = (0..3).fold([0.0; 3], |s, i| add(s, scale(self.basis[i], ix[i] as f64)));
let mut out = Aabb {
lo: [0, 1, 2].map(|k| b.lo[k] - pad + shift[k]),
hi: [0, 1, 2].map(|k| b.hi[k] + pad + shift[k]),
};
for i in 0..3 {
if !self.bounded[i] {
for k in 0..3 {
if self.basis[i][k].abs() > 1e-12 {
out.lo[k] = f64::NEG_INFINITY;
out.hi[k] = f64::INFINITY;
}
}
}
}
out
}
pub(crate) fn element_range(
&self,
o: Vec3,
d: Vec3,
ix: [i32; 3],
) -> (f64, f64, Option<usize>) {
let q = self.to_element(o, ix);
let (mut lo, mut hi, mut exit) = (f64::NEG_INFINITY, f64::INFINITY, None);
for (k, (n, off)) in self.faces.iter().enumerate() {
let nd = dot(*n, d);
let gap = off - dot(*n, q);
if nd == 0.0 {
if gap < 0.0 {
return (f64::INFINITY, f64::NEG_INFINITY, None);
}
continue;
}
let t = gap / nd;
if nd > 0.0 {
if t < hi {
hi = t;
exit = Some(k);
}
} else if t > lo {
lo = t;
}
}
(lo, hi, exit)
}
pub(crate) fn neighbours(&self, ix: [i32; 3]) -> impl Iterator<Item = [i32; 3]> + '_ {
let k = if self.bounded[2] { 1 } else { 0 };
(-1..=1).flat_map(move |di| {
(-1..=1).flat_map(move |dj| {
(-k..=k)
.filter(move |&dk| (di, dj, dk) != (0, 0, 0))
.map(move |dk| [ix[0] + di, ix[1] + dj, ix[2] + dk])
})
})
}
pub fn fill_array(&self) -> Option<([i32; 3], [i32; 3])> {
match &self.fill {
LatticeFill::Uniform(_) => None,
LatticeFill::Array { lo, size, .. } => Some((*lo, *size)),
}
}
pub fn element(&self, ix: [i32; 3]) -> Element<'_> {
match &self.fill {
LatticeFill::Uniform(t) => Element::Fill(t),
LatticeFill::Array { lo, size, elements } => {
let mut flat = 0usize;
for i in (0..3).rev() {
let k = ix[i] - lo[i];
if k < 0 || k >= size[i] {
return Element::Missing;
}
flat = flat * size[i] as usize + k as usize;
}
match &elements[flat] {
Some(t) => Element::Fill(t),
None => Element::Own,
}
}
}
}
pub fn targets(&self) -> impl Iterator<Item = &Target> + '_ {
let (one, array) = match &self.fill {
LatticeFill::Uniform(t) => (Some(t), None),
LatticeFill::Array { elements, .. } => (None, Some(elements)),
};
one.into_iter().chain(array.into_iter().flatten().flatten())
}
}
fn outward_planes(code: &[u32], shapes: &[Shape]) -> Result<Vec<(Vec3, f64)>, String> {
if code
.first()
.is_some_and(|w| w & expr::NODE != 0 && w & expr::OR != 0)
{
return Err("lattice element must be an intersection of planes".into());
}
expr::leaves(code)
.map(|(s, want_pos)| match shapes[s as usize] {
Shape::Plane { n, d } if want_pos => Ok((scale(n, -1.0), -d)),
Shape::Plane { n, d } => Ok((n, d)),
_ => Err("lattice elements must be bounded by planes".to_string()),
})
.collect()
}
fn meet(a: (Vec3, f64), b: (Vec3, f64), c: (Vec3, f64)) -> Result<Vec3, String> {
let det = dot(a.0, cross(b.0, c.0));
if det.abs() < 1e-12 {
return Err("degenerate lattice element".into());
}
let v = add(
add(scale(cross(b.0, c.0), a.1), scale(cross(c.0, a.0), b.1)),
scale(cross(a.0, b.0), c.1),
);
Ok(scale(v, 1.0 / det))
}
fn dual_of(basis: &[Vec3; 3]) -> Result<[Vec3; 3], String> {
let det = dot(basis[0], cross(basis[1], basis[2]));
if det.abs() < 1e-12 {
return Err("degenerate lattice element".into());
}
Ok([
scale(cross(basis[1], basis[2]), 1.0 / det),
scale(cross(basis[2], basis[0]), 1.0 / det),
scale(cross(basis[0], basis[1]), 1.0 / det),
])
}
fn mid(p: (Vec3, f64), q: (Vec3, f64)) -> Result<(Vec3, f64), String> {
if dot(p.0, q.0) > -1.0 + 1e-9 {
return Err("lattice element sides must come in parallel opposite pairs".into());
}
Ok((p.0, 0.5 * (p.1 - q.1)))
}
pub(crate) fn build(
lat: u8,
code: &[u32],
shapes: &[Shape],
fill: LatticeFill,
) -> Result<Lattice, String> {
let planes = outward_planes(code, shapes)?;
let face_surfaces: Vec<u32> = expr::leaves(code).map(|(s, _)| s).collect();
let (sides, dims) = match (lat, planes.len()) {
(1, 6) => (4, 3),
(1, 4) => (4, 2),
(2, 8) => (6, 3),
(2, 6) => (6, 2),
(_, n) => {
return Err(format!(
"LAT={lat} element with {n} surfaces is not supported"
))
}
};
let m0 = mid(planes[0], planes[1])?;
let m1 = mid(planes[2], planes[3])?;
let axis = {
let e = cross(planes[0].0, planes[2].0);
scale(e, 1.0 / norm(e))
};
let (m2, axial) = if dims == 3 {
let (top, bottom) = (planes[sides], planes[sides + 1]);
(mid(top, bottom)?, Some((top, bottom)))
} else {
((axis, 0.0), None)
};
let center = meet(m0, m1, m2)?;
let step = |p: (Vec3, f64)| scale(p.0, 2.0 * (p.1 - dot(p.0, center)));
let a = step(planes[0]);
let b = step(planes[2]);
let c = match axial {
Some((top, bottom)) => {
let e = if dot(axis, top.0) < 0.0 {
scale(axis, -1.0)
} else {
axis
};
scale(e, (top.1 + bottom.1) / dot(e, top.0))
}
None => axis,
};
let (hexagonal, center, basis, bounded) = if lat == 1 && dims == 3 {
let corner = meet(planes[1], planes[3], planes[5])?;
let next = |k: usize| -> Result<Vec3, String> {
let mut ps = [planes[1], planes[3], planes[5]];
ps[k] = planes[2 * k];
Ok(sub(meet(ps[0], ps[1], ps[2])?, corner))
};
let basis = [next(0)?, next(1)?, next(2)?];
let center = add(corner, scale(add(add(basis[0], basis[1]), basis[2]), 0.5));
(false, center, basis, [true, true, true])
} else if lat == 1 {
let corner = meet(planes[1], planes[3], (axis, 0.0))?;
let ea = sub(meet(planes[0], planes[3], (axis, 0.0))?, corner);
let eb = sub(meet(planes[1], planes[2], (axis, 0.0))?, corner);
let center = add(corner, scale(add(ea, eb), 0.5));
(false, center, [ea, eb, axis], [true, true, false])
} else {
(true, center, [a, b, c], [true, true, dims == 3])
};
let dual = dual_of(&basis)?;
let faces = tiling_faces(hexagonal, center, &basis, &dual, &planes);
Ok(Lattice {
hexagonal,
center,
dual,
basis,
bounded,
sides: faces[..sides].to_vec(),
faces,
face_surfaces,
fill,
})
}
fn tiling_faces(
hexagonal: bool,
center: Vec3,
basis: &[Vec3; 3],
dual: &[Vec3; 3],
planes: &[(Vec3, f64)],
) -> Vec<(Vec3, f64)> {
let halfway = |v: Vec3| {
let n = scale(v, 1.0 / norm(v));
(n, dot(n, center) + 0.5 * norm(v))
};
let across_dual = |k: usize, sign: f64| {
let len = norm(dual[k]);
let n = scale(dual[k], sign / len);
(n, dot(n, center) + 0.5 / len)
};
let neg = |v: Vec3| scale(v, -1.0);
let mut faces = Vec::with_capacity(planes.len());
if hexagonal {
let (a, b) = (basis[0], basis[1]);
let third = sub(b, a);
for v in [a, neg(a), b, neg(b), third, neg(third)] {
faces.push(halfway(v));
}
if planes.len() == 8 {
faces.push(across_dual(2, 1.0));
faces.push(across_dual(2, -1.0));
}
} else {
for k in 0..planes.len() / 2 {
faces.push(across_dual(k, 1.0));
faces.push(across_dual(k, -1.0));
}
}
faces
}