use crate::math::Vector3;
use std::sync::OnceLock;
pub type Segment = [[f32; 3]; 2];
const CUBIC: [Segment; 3] = [
[[0.0, 0.0, 0.0], [1.0, 0.0, 0.0]],
[[0.0, 0.0, 0.0], [0.0, 1.0, 0.0]],
[[0.0, 0.0, 0.0], [0.0, 0.0, 1.0]],
];
const BCC: [Segment; 8] = [
[[0.5, 0.5, 0.5], [0.0, 0.0, 0.0]],
[[0.5, 0.5, 0.5], [1.0, 0.0, 0.0]],
[[0.5, 0.5, 0.5], [0.0, 1.0, 0.0]],
[[0.5, 0.5, 0.5], [1.0, 1.0, 0.0]],
[[0.5, 0.5, 0.5], [0.0, 0.0, 1.0]],
[[0.5, 0.5, 0.5], [1.0, 0.0, 1.0]],
[[0.5, 0.5, 0.5], [0.0, 1.0, 1.0]],
[[0.5, 0.5, 0.5], [1.0, 1.0, 1.0]],
];
const BCC_Z: [Segment; 11] = [
[[0.5, 0.5, 0.5], [0.0, 0.0, 0.0]],
[[0.5, 0.5, 0.5], [1.0, 0.0, 0.0]],
[[0.5, 0.5, 0.5], [0.0, 1.0, 0.0]],
[[0.5, 0.5, 0.5], [1.0, 1.0, 0.0]],
[[0.5, 0.5, 0.5], [0.0, 0.0, 1.0]],
[[0.5, 0.5, 0.5], [1.0, 0.0, 1.0]],
[[0.5, 0.5, 0.5], [0.0, 1.0, 1.0]],
[[0.5, 0.5, 0.5], [1.0, 1.0, 1.0]],
[[0.0, 0.0, 0.0], [1.0, 0.0, 0.0]],
[[0.0, 0.0, 0.0], [0.0, 1.0, 0.0]],
[[0.0, 0.0, 0.0], [0.0, 0.0, 1.0]],
];
const FCC: [Segment; 12] = [
[[0.0, 0.5, 0.5], [0.0, 0.0, 0.0]],
[[0.0, 0.5, 0.5], [0.0, 1.0, 0.0]],
[[0.0, 0.5, 0.5], [0.0, 1.0, 1.0]],
[[0.0, 0.5, 0.5], [0.0, 0.0, 1.0]],
[[0.5, 0.0, 0.5], [0.0, 0.0, 0.0]],
[[0.5, 0.0, 0.5], [1.0, 0.0, 0.0]],
[[0.5, 0.0, 0.5], [1.0, 0.0, 1.0]],
[[0.5, 0.0, 0.5], [0.0, 0.0, 1.0]],
[[0.5, 0.5, 0.0], [0.0, 0.0, 0.0]],
[[0.5, 0.5, 0.0], [1.0, 0.0, 0.0]],
[[0.5, 0.5, 0.0], [1.0, 1.0, 0.0]],
[[0.5, 0.5, 0.0], [0.0, 1.0, 0.0]],
];
const OCTET: [Segment; 24] = [
[[0.0, 0.5, 0.5], [0.0, 0.0, 0.0]],
[[0.0, 0.5, 0.5], [0.0, 1.0, 0.0]],
[[0.0, 0.5, 0.5], [0.0, 1.0, 1.0]],
[[0.0, 0.5, 0.5], [0.0, 0.0, 1.0]],
[[0.5, 0.0, 0.5], [0.0, 0.0, 0.0]],
[[0.5, 0.0, 0.5], [1.0, 0.0, 0.0]],
[[0.5, 0.0, 0.5], [1.0, 0.0, 1.0]],
[[0.5, 0.0, 0.5], [0.0, 0.0, 1.0]],
[[0.5, 0.5, 0.0], [0.0, 0.0, 0.0]],
[[0.5, 0.5, 0.0], [1.0, 0.0, 0.0]],
[[0.5, 0.5, 0.0], [1.0, 1.0, 0.0]],
[[0.5, 0.5, 0.0], [0.0, 1.0, 0.0]],
[[0.5, 0.5, 0.0], [0.5, 0.0, 0.5]],
[[0.5, 0.5, 0.0], [0.5, 1.0, 0.5]],
[[0.5, 0.5, 0.0], [0.0, 0.5, 0.5]],
[[0.5, 0.5, 0.0], [1.0, 0.5, 0.5]],
[[0.5, 0.5, 1.0], [0.5, 0.0, 0.5]],
[[0.5, 0.5, 1.0], [0.5, 1.0, 0.5]],
[[0.5, 0.5, 1.0], [0.0, 0.5, 0.5]],
[[0.5, 0.5, 1.0], [1.0, 0.5, 0.5]],
[[0.5, 0.0, 0.5], [0.0, 0.5, 0.5]],
[[0.5, 0.0, 0.5], [1.0, 0.5, 0.5]],
[[0.5, 1.0, 0.5], [0.0, 0.5, 0.5]],
[[0.5, 1.0, 0.5], [1.0, 0.5, 0.5]],
];
const DIAMOND: [Segment; 16] = [
[[0.25, 0.25, 0.25], [0.0, 0.0, 0.0]],
[[0.25, 0.25, 0.25], [0.5, 0.5, 0.0]],
[[0.25, 0.25, 0.25], [0.5, 0.0, 0.5]],
[[0.25, 0.25, 0.25], [0.0, 0.5, 0.5]],
[[0.75, 0.75, 0.25], [0.5, 0.5, 0.0]],
[[0.75, 0.75, 0.25], [1.0, 1.0, 0.0]],
[[0.75, 0.75, 0.25], [1.0, 0.5, 0.5]],
[[0.75, 0.75, 0.25], [0.5, 1.0, 0.5]],
[[0.75, 0.25, 0.75], [0.5, 0.0, 0.5]],
[[0.75, 0.25, 0.75], [1.0, 0.5, 0.5]],
[[0.75, 0.25, 0.75], [1.0, 0.0, 1.0]],
[[0.75, 0.25, 0.75], [0.5, 0.5, 1.0]],
[[0.25, 0.75, 0.75], [0.0, 0.5, 0.5]],
[[0.25, 0.75, 0.75], [0.5, 1.0, 0.5]],
[[0.25, 0.75, 0.75], [0.5, 0.5, 1.0]],
[[0.25, 0.75, 0.75], [0.0, 1.0, 1.0]],
];
fn kelvin() -> &'static [Segment] {
static EDGES: OnceLock<Vec<Segment>> = OnceLock::new();
EDGES.get_or_init(|| {
let mut verts: Vec<[f32; 3]> = Vec::with_capacity(24);
for (long, short) in [(0, 1), (0, 2), (1, 0), (1, 2), (2, 0), (2, 1)] {
for sign_long in [0.5f32, -0.5] {
for sign_short in [0.25f32, -0.25] {
let mut v = [0.5f32; 3];
v[long] += sign_long;
v[short] += sign_short;
verts.push(v);
}
}
}
let edge_sq = 0.125f32;
let mut edges = Vec::with_capacity(36);
for (i, a) in verts.iter().enumerate() {
for b in &verts[i + 1..] {
let d = [b[0] - a[0], b[1] - a[1], b[2] - a[2]];
let len_sq = d[0] * d[0] + d[1] * d[1] + d[2] * d[2];
if (len_sq - edge_sq).abs() < 1e-4 {
edges.push([*a, *b]);
}
}
}
edges
})
}
const CURVE_SEGMENTS: usize = 24;
fn polyline(f: impl Fn(f32) -> [f32; 3]) -> Vec<Segment> {
(0..CURVE_SEGMENTS)
.map(|i| {
[
f(i as f32 / CURVE_SEGMENTS as f32),
f((i + 1) as f32 / CURVE_SEGMENTS as f32),
]
})
.collect()
}
const WEAVE_RISE: f32 = 0.125;
fn weave() -> &'static [Segment] {
static SEGMENTS: OnceLock<Vec<Segment>> = OnceLock::new();
SEGMENTS.get_or_init(|| {
let wave = |t: f32| WEAVE_RISE * (std::f32::consts::TAU * t).cos();
let mut out = Vec::new();
out.extend(polyline(|t| [t, 0.25, 0.5 + wave(t)]));
out.extend(polyline(|t| [t, 0.75, 0.5 - wave(t)]));
out.extend(polyline(|t| [0.0, t, 0.5 - wave(t - 0.25)]));
out.extend(polyline(|t| [0.5, t, 0.5 + wave(t - 0.25)]));
out
})
}
fn braid() -> &'static [Segment] {
static SEGMENTS: OnceLock<Vec<Segment>> = OnceLock::new();
SEGMENTS.get_or_init(|| {
let mut out = Vec::new();
for k in 0..3 {
let phase = k as f32 * std::f32::consts::TAU / 3.0;
out.extend(polyline(|t| {
let a = std::f32::consts::TAU * t + phase;
[0.5 + 0.32 * a.sin(), 0.5 + 0.16 * (2.0 * a).sin(), t]
}));
}
out
})
}
fn helix_bundle() -> &'static [Segment] {
static SEGMENTS: OnceLock<Vec<Segment>> = OnceLock::new();
SEGMENTS.get_or_init(|| {
let mut out = Vec::new();
for k in 0..6 {
let phase = k as f32 * std::f32::consts::TAU / 6.0;
out.extend(polyline(|t| {
let a = std::f32::consts::TAU * t + phase;
[0.5 + 0.3 * a.cos(), 0.5 + 0.3 * a.sin(), t]
}));
}
out
})
}
#[derive(Clone, Copy, Debug, PartialEq, Eq, Hash)]
pub enum Strut {
Cubic,
Bcc,
BccZ,
Fcc,
Octet,
Diamond,
Kelvin,
Weave,
Braid,
HelixBundle,
}
impl Strut {
pub const ALL: [Strut; 10] = [
Strut::Cubic,
Strut::Bcc,
Strut::BccZ,
Strut::Fcc,
Strut::Octet,
Strut::Diamond,
Strut::Kelvin,
Strut::Weave,
Strut::Braid,
Strut::HelixBundle,
];
pub fn is_textile(self) -> bool {
matches!(self, Strut::Weave | Strut::Braid | Strut::HelixBundle)
}
pub fn segments(self) -> &'static [Segment] {
match self {
Strut::Cubic => &CUBIC,
Strut::Bcc => &BCC,
Strut::BccZ => &BCC_Z,
Strut::Fcc => &FCC,
Strut::Octet => &OCTET,
Strut::Diamond => &DIAMOND,
Strut::Kelvin => kelvin(),
Strut::Weave => weave(),
Strut::Braid => braid(),
Strut::HelixBundle => helix_bundle(),
}
}
pub fn name(self) -> &'static str {
match self {
Strut::Cubic => "simple-cubic",
Strut::Bcc => "bcc",
Strut::BccZ => "bcc-z",
Strut::Fcc => "fcc",
Strut::Octet => "octet",
Strut::Diamond => "diamond-strut",
Strut::Kelvin => "kelvin",
Strut::Weave => "weave",
Strut::Braid => "braid",
Strut::HelixBundle => "helix-bundle",
}
}
pub fn from_name(name: &str) -> Option<Strut> {
Strut::ALL.into_iter().find(|s| s.name() == name)
}
}
pub(crate) fn distance(
p: Vector3,
origin: Vector3,
cell: Vector3,
segments: &[Segment],
cull: f32,
) -> f32 {
let u = [
(p.x - origin.x) / cell.x,
(p.y - origin.y) / cell.y,
(p.z - origin.z) / cell.z,
];
let base = [u[0].floor(), u[1].floor(), u[2].floor()];
let mut best = cull;
for oz in -1..=1 {
for oy in -1..=1 {
for ox in -1..=1 {
let c = [
base[0] + ox as f32,
base[1] + oy as f32,
base[2] + oz as f32,
];
let mut bound = 0.0f32;
for a in 0..3 {
let local = u[a] - c[a];
let out = if local < 0.0 {
-local
} else if local > 1.0 {
local - 1.0
} else {
0.0
};
let world = out * cell_axis(cell, a);
bound += world * world;
}
if bound >= best * best {
continue;
}
let cell_origin = Vector3::new(
origin.x + c[0] * cell.x,
origin.y + c[1] * cell.y,
origin.z + c[2] * cell.z,
);
for seg in segments {
let a = Vector3::new(
cell_origin.x + seg[0][0] * cell.x,
cell_origin.y + seg[0][1] * cell.y,
cell_origin.z + seg[0][2] * cell.z,
);
let b = Vector3::new(
cell_origin.x + seg[1][0] * cell.x,
cell_origin.y + seg[1][1] * cell.y,
cell_origin.z + seg[1][2] * cell.z,
);
let d = segment_distance(p, a, b);
if d < best {
best = d;
}
}
}
}
}
best
}
const BINS: usize = 8;
pub(crate) struct Bins {
cull: f32,
start: Vec<u32>,
entries: Vec<([i8; 3], u16)>,
}
impl Bins {
pub(crate) fn new(segments: &[Segment], cell: Vector3, cull: f32) -> Option<Bins> {
let size = [cell.x, cell.y, cell.z];
#[allow(clippy::neg_cmp_op_on_partial_ord)]
let unusable = !(cull >= 0.0) || size.iter().any(|&c| !(cull < c));
if unusable || segments.len() > u16::MAX as usize {
return None;
}
let reach = cull * 1.001 + 1e-6 * size.iter().fold(0.0f32, |m, &c| m.max(c));
let mut start = Vec::with_capacity(BINS * BINS * BINS + 1);
let mut entries = Vec::new();
start.push(0);
for bz in 0..BINS {
for by in 0..BINS {
for bx in 0..BINS {
let lo = [bx, by, bz].map(|b| b as f32 / BINS as f32);
let hi = [bx, by, bz].map(|b| (b + 1) as f32 / BINS as f32);
for oz in -1i8..=1 {
for oy in -1i8..=1 {
for ox in -1i8..=1 {
let o = [ox, oy, oz];
for (index, seg) in segments.iter().enumerate() {
let mut gap = 0.0f32;
for a in 0..3 {
let s0 = seg[0][a].min(seg[1][a]) + o[a] as f32;
let s1 = seg[0][a].max(seg[1][a]) + o[a] as f32;
let g = (s0 - hi[a]).max(lo[a] - s1).max(0.0) * size[a];
gap += g * g;
}
if gap <= reach * reach {
entries.push((o, index as u16));
}
}
}
}
}
start.push(entries.len() as u32);
}
}
}
Some(Bins {
cull: reach.min(cull),
start,
entries,
})
}
}
pub(crate) fn distance_binned(
p: Vector3,
origin: Vector3,
cell: Vector3,
segments: &[Segment],
bins: &Bins,
cull: f32,
) -> f32 {
#[allow(clippy::neg_cmp_op_on_partial_ord)]
if !(cull <= bins.cull) {
return distance(p, origin, cell, segments, cull);
}
let u = [
(p.x - origin.x) / cell.x,
(p.y - origin.y) / cell.y,
(p.z - origin.z) / cell.z,
];
let base = [u[0].floor(), u[1].floor(), u[2].floor()];
let bin = |a: usize| (((u[a] - base[a]) * BINS as f32) as usize).min(BINS - 1);
let b = (bin(2) * BINS + bin(1)) * BINS + bin(0);
let mut best = cull;
for &(o, index) in &bins.entries[bins.start[b] as usize..bins.start[b + 1] as usize] {
let c = [
base[0] + o[0] as f32,
base[1] + o[1] as f32,
base[2] + o[2] as f32,
];
let cell_origin = Vector3::new(
origin.x + c[0] * cell.x,
origin.y + c[1] * cell.y,
origin.z + c[2] * cell.z,
);
let seg = &segments[index as usize];
let a = Vector3::new(
cell_origin.x + seg[0][0] * cell.x,
cell_origin.y + seg[0][1] * cell.y,
cell_origin.z + seg[0][2] * cell.z,
);
let b = Vector3::new(
cell_origin.x + seg[1][0] * cell.x,
cell_origin.y + seg[1][1] * cell.y,
cell_origin.z + seg[1][2] * cell.z,
);
let d = segment_distance(p, a, b);
if d < best {
best = d;
}
}
best
}
#[inline]
fn cell_axis(cell: Vector3, axis: usize) -> f32 {
match axis {
0 => cell.x,
1 => cell.y,
_ => cell.z,
}
}
#[inline]
pub(crate) fn segment_distance(p: Vector3, a: Vector3, b: Vector3) -> f32 {
let ab = b - a;
let ap = p - a;
let len_sq = ab.length_sq();
let t = if len_sq > f32::EPSILON {
(ap.dot(ab) / len_sq).clamp(0.0, 1.0)
} else {
0.0
};
(ap - ab * t).length()
}
#[cfg(test)]
mod tests {
use super::*;
const CELL: Vector3 = Vector3::ONE;
fn dist(kind: Strut, p: Vector3) -> f32 {
distance(p, Vector3::ZERO, CELL, kind.segments(), 10.0)
}
#[test]
fn binned_distance_is_the_full_search() {
let cell = Vector3::new(1.3, 0.8, 1.1);
let origin = Vector3::new(-0.37, 0.21, 0.05);
let mut kinds: Vec<Vec<Segment>> =
Strut::ALL.iter().map(|k| k.segments().to_vec()).collect();
kinds.extend(super::super::Cuboct::ALL.iter().map(|c| c.segments(1.0)));
for (n, segments) in kinds.iter().enumerate() {
for cull in [0.05f32, 0.2, 0.5] {
let bins = Bins::new(segments, cell, cull).expect("in range");
for i in 0..2000u32 {
let f = |a: u32| {
(i.wrapping_mul(2654435761u32.wrapping_add(a * 40503)) % 100_000) as f32
/ 100_000.0
};
let p = Vector3::new(f(1) * 4.0 - 2.0, f(2) * 3.0 - 1.5, f(3) * 4.0 - 2.0);
for c in [cull, cull * 0.5, cull * 2.0] {
let full = distance(p, origin, cell, segments, c);
let binned = distance_binned(p, origin, cell, segments, &bins, c);
assert_eq!(
full.to_bits(),
binned.to_bits(),
"kind {n} cull {c} at {p:?}"
);
}
}
}
}
}
fn yarn_gap(kind: Strut, yarns: usize) -> f32 {
let segments = kind.segments();
let per = segments.len() / yarns;
let mut gap = f32::INFINITY;
for (i, a) in segments.iter().enumerate() {
for (j, b) in segments.iter().enumerate() {
if i / per == j / per {
continue;
}
for o in [
[0.0f32, 0.0, 0.0],
[1.0, 0.0, 0.0],
[0.0, 1.0, 0.0],
[0.0, 0.0, 1.0],
[-1.0, 0.0, 0.0],
[0.0, -1.0, 0.0],
] {
for s in 0..=16 {
let t = s as f32 / 16.0;
let p = Vector3::new(
a[0][0] + (a[1][0] - a[0][0]) * t,
a[0][1] + (a[1][1] - a[0][1]) * t,
a[0][2] + (a[1][2] - a[0][2]) * t,
);
let q0 = Vector3::new(b[0][0] + o[0], b[0][1] + o[1], b[0][2] + o[2]);
let q1 = Vector3::new(b[1][0] + o[0], b[1][1] + o[1], b[1][2] + o[2]);
gap = gap.min(segment_distance(p, q0, q1));
}
}
}
}
gap
}
#[test]
fn textile_yarns_keep_apart() {
let weave = yarn_gap(Strut::Weave, 4);
assert!((weave - 0.25).abs() < 0.01, "weave gap {weave}");
let braid = yarn_gap(Strut::Braid, 3);
assert!(
(braid - 0.148).abs() < 0.005,
"braid strands come within {braid}"
);
let rope = yarn_gap(Strut::HelixBundle, 6);
assert!((rope - 0.147).abs() < 0.005, "helix gap {rope}");
}
#[test]
fn segments_stay_inside_their_cell() {
for kind in Strut::ALL {
for seg in kind.segments() {
for end in seg {
for a in end {
assert!(
(0.0..=1.0).contains(a),
"{} leaves the unit cell at {a}",
kind.name()
);
}
}
}
}
}
#[test]
fn field_is_periodic() {
for kind in Strut::ALL {
for p in [
Vector3::new(0.31, 0.62, 0.17),
Vector3::new(0.5, 0.5, 0.5),
Vector3::new(0.9, 0.05, 0.44),
] {
let base = dist(kind, p);
for shift in [
Vector3::new(1.0, 0.0, 0.0),
Vector3::new(0.0, 3.0, 0.0),
Vector3::new(-2.0, 1.0, 4.0),
] {
let moved = dist(kind, p + shift);
assert!(
(base - moved).abs() < 1e-4,
"{} is not periodic: {base} vs {moved}",
kind.name()
);
}
}
}
}
#[test]
fn nodes_sit_on_the_lattice() {
for kind in Strut::ALL
.into_iter()
.filter(|k| *k != Strut::Kelvin && !k.is_textile())
{
assert!(dist(kind, Vector3::ZERO) < 1e-5, "{}", kind.name());
assert!(
dist(kind, Vector3::new(1.0, 1.0, 0.0)) < 1e-5,
"{}",
kind.name()
);
}
assert!(dist(Strut::Bcc, Vector3::new(0.5, 0.5, 0.5)) < 1e-5);
assert!(dist(Strut::Fcc, Vector3::new(0.5, 0.5, 0.0)) < 1e-5);
assert!(dist(Strut::Diamond, Vector3::new(0.25, 0.25, 0.25)) < 1e-5);
assert!(dist(Strut::Kelvin, Vector3::new(1.0, 0.75, 0.5)) < 1e-5);
assert!(dist(Strut::Kelvin, Vector3::ZERO) > 0.3, "corner is a void");
}
#[test]
fn names_round_trip() {
for kind in Strut::ALL {
assert_eq!(Strut::from_name(kind.name()), Some(kind));
}
assert_eq!(Strut::from_name("not-a-lattice"), None);
}
#[test]
fn cell_interiors_stay_open() {
for kind in Strut::ALL {
let p = match kind {
Strut::Bcc | Strut::BccZ => Vector3::new(0.5, 0.5, 0.15),
Strut::Weave => Vector3::new(0.25, 0.5, 0.5),
Strut::Braid => Vector3::new(0.05, 0.05, 0.5),
_ => Vector3::new(0.5, 0.5, 0.5),
};
assert!(dist(kind, p) > 0.1, "{} has no void at {p:?}", kind.name());
}
}
#[test]
fn culling_matches_the_full_search() {
for kind in Strut::ALL {
for i in 0..40 {
let t = i as f32 / 40.0;
let p = Vector3::new(t * 1.7 - 0.3, t * t * 2.0, 0.4 - t);
let full = dist(kind, p);
let culled = distance(p, Vector3::ZERO, CELL, kind.segments(), 0.3);
if full < 0.3 {
assert!((full - culled).abs() < 1e-5, "{}", kind.name());
} else {
assert_eq!(culled, 0.3, "{}", kind.name());
}
}
}
}
#[test]
fn the_kelvin_cell_is_a_truncated_octahedron() {
let edges = kelvin();
assert_eq!(edges.len(), 36, "a truncated octahedron has 36 edges");
let key = |v: &[f32; 3]| {
(
(v[0] * 1000.0).round() as i32,
(v[1] * 1000.0).round() as i32,
(v[2] * 1000.0).round() as i32,
)
};
let mut degree: std::collections::HashMap<(i32, i32, i32), usize> =
std::collections::HashMap::new();
for e in edges {
for v in e {
*degree.entry(key(v)).or_insert(0) += 1;
}
}
assert_eq!(degree.len(), 24, "a truncated octahedron has 24 vertices");
assert!(
degree.values().all(|&d| d == 3),
"every node joins exactly three struts"
);
}
#[test]
fn kelvin_corner_cells_are_covered() {
for mid in [
Vector3::new(0.5, 0.125, 0.125),
Vector3::new(0.125, 0.5, 0.125),
Vector3::new(0.125, 0.125, 0.5),
Vector3::new(0.375, 0.375, 0.0),
] {
let d = dist(Strut::Kelvin, mid);
assert!(d < 1e-4, "corner cell edge missed at {mid:?}: {d}");
}
}
#[test]
fn anisotropic_cells_scale_the_struts() {
let cell = Vector3::new(2.0, 1.0, 1.0);
let segs = Strut::Cubic.segments();
let on = distance(Vector3::new(1.0, 0.0, 0.0), Vector3::ZERO, cell, segs, 10.0);
assert!(on < 1e-5);
let off = distance(Vector3::new(1.0, 0.5, 0.0), Vector3::ZERO, cell, segs, 10.0);
assert!((off - 0.5).abs() < 1e-5, "{off}");
}
}