#![deny(missing_docs)]
#![forbid(unsafe_code)]
use std::ops::{Index, IndexMut};
#[derive(Clone, Debug, PartialEq)]
pub struct VoxelGrid<T> {
dims: [usize; 3],
pub spacing: [f64; 3],
pub origin: [f64; 3],
data: Vec<T>,
}
pub type Mask = VoxelGrid<bool>;
impl<T: Clone> VoxelGrid<T> {
#[must_use]
pub fn filled(dims: [usize; 3], value: T) -> Self {
Self {
dims,
spacing: [1.0; 3],
origin: [0.0; 3],
data: vec![value; dims[0] * dims[1] * dims[2]],
}
}
#[must_use]
pub fn from_vec(dims: [usize; 3], data: Vec<T>) -> Option<Self> {
if data.len() != dims[0] * dims[1] * dims[2] {
return None;
}
Some(Self {
dims,
spacing: [1.0; 3],
origin: [0.0; 3],
data,
})
}
#[must_use]
pub fn with_spacing(mut self, spacing: [f64; 3]) -> Self {
self.spacing = spacing;
self
}
#[must_use]
pub fn with_origin(mut self, origin: [f64; 3]) -> Self {
self.origin = origin;
self
}
}
impl<T> VoxelGrid<T> {
#[must_use]
pub fn dims(&self) -> [usize; 3] {
self.dims
}
#[must_use]
pub fn len(&self) -> usize {
self.data.len()
}
#[must_use]
pub fn is_empty(&self) -> bool {
self.data.is_empty()
}
#[must_use]
pub fn as_slice(&self) -> &[T] {
&self.data
}
#[inline]
fn idx(&self, [x, y, z]: [usize; 3]) -> usize {
debug_assert!(x < self.dims[0] && y < self.dims[1] && z < self.dims[2]);
(z * self.dims[1] + y) * self.dims[0] + x
}
#[must_use]
pub fn get(&self, p: [usize; 3]) -> Option<&T> {
(p[0] < self.dims[0] && p[1] < self.dims[1] && p[2] < self.dims[2])
.then(|| &self.data[self.idx(p)])
}
pub fn iter(&self) -> impl Iterator<Item = ([usize; 3], &T)> {
let [nx, ny, _] = self.dims;
self.data.iter().enumerate().map(move |(i, v)| {
let x = i % nx;
let y = (i / nx) % ny;
let z = i / (nx * ny);
([x, y, z], v)
})
}
}
impl<T> Index<[usize; 3]> for VoxelGrid<T> {
type Output = T;
fn index(&self, p: [usize; 3]) -> &T {
let i = self.idx(p);
&self.data[i]
}
}
impl<T> IndexMut<[usize; 3]> for VoxelGrid<T> {
fn index_mut(&mut self, p: [usize; 3]) -> &mut T {
let i = self.idx(p);
&mut self.data[i]
}
}
impl<T: PartialOrd> VoxelGrid<T> {
#[must_use]
pub fn threshold(&self, level: T) -> Mask {
Mask {
dims: self.dims,
spacing: self.spacing,
origin: self.origin,
data: self.data.iter().map(|v| *v >= level).collect(),
}
}
}
const NEIGHBOURS: [[isize; 3]; 6] = [
[-1, 0, 0],
[1, 0, 0],
[0, -1, 0],
[0, 1, 0],
[0, 0, -1],
[0, 0, 1],
];
impl Mask {
#[must_use]
pub fn count(&self) -> usize {
self.data.iter().filter(|&&v| v).count()
}
#[inline]
fn is_set(&self, x: isize, y: isize, z: isize) -> bool {
if x < 0 || y < 0 || z < 0 {
return false;
}
let p = [x as usize, y as usize, z as usize];
self.get(p).copied().unwrap_or(false)
}
fn morph(&self, dilate: bool) -> Mask {
let mut out = self.clone();
for ([x, y, z], v) in self.iter() {
let (xi, yi, zi) = (x as isize, y as isize, z as isize);
let any_neigh = |target: bool| {
NEIGHBOURS
.iter()
.any(|d| self.is_set(xi + d[0], yi + d[1], zi + d[2]) == target)
};
let i = (z * self.dims[1] + y) * self.dims[0] + x;
out.data[i] = if dilate {
*v || any_neigh(true)
} else {
*v && !any_neigh(false)
};
}
out
}
#[must_use]
pub fn erode(&self) -> Mask {
self.morph(false)
}
#[must_use]
pub fn dilate(&self) -> Mask {
self.morph(true)
}
#[must_use]
pub fn open(&self) -> Mask {
self.erode().dilate()
}
#[must_use]
pub fn close(&self) -> Mask {
self.dilate().erode()
}
#[must_use]
pub fn to_mesh(&self) -> Mesh {
use std::collections::HashMap;
let mut verts: Vec<[f64; 3]> = Vec::new();
let mut lookup: HashMap<[usize; 3], u32> = HashMap::new();
let mut tris: Vec<[u32; 3]> = Vec::new();
let vertex = |lookup: &mut HashMap<[usize; 3], u32>,
verts: &mut Vec<[f64; 3]>,
gp: [usize; 3]| {
*lookup.entry(gp).or_insert_with(|| {
let id = verts.len() as u32;
verts.push([
self.origin[0] + gp[0] as f64 * self.spacing[0],
self.origin[1] + gp[1] as f64 * self.spacing[1],
self.origin[2] + gp[2] as f64 * self.spacing[2],
]);
id
})
};
for ([x, y, z], &v) in self.iter() {
if !v {
continue;
}
let (xi, yi, zi) = (x as isize, y as isize, z as isize);
for d in NEIGHBOURS {
if self.is_set(xi + d[0], yi + d[1], zi + d[2]) {
continue; }
let base = [
x + usize::from(d[0] > 0),
y + usize::from(d[1] > 0),
z + usize::from(d[2] > 0),
];
let axes: Vec<usize> = (0..3).filter(|&a| d[a] == 0).collect();
let (a, b) = (axes[0], axes[1]);
let mut quad = [base; 4];
quad[1][a] += 1;
quad[2][a] += 1;
quad[2][b] += 1;
quad[3][b] += 1;
let ids: Vec<u32> = quad
.iter()
.map(|&gp| vertex(&mut lookup, &mut verts, gp))
.collect();
let outward = d.iter().sum::<isize>() > 0;
let flip = (a == 0 && b == 2) ^ outward;
if flip {
tris.push([ids[0], ids[1], ids[2]]);
tris.push([ids[0], ids[2], ids[3]]);
} else {
tris.push([ids[2], ids[1], ids[0]]);
tris.push([ids[3], ids[2], ids[0]]);
}
}
}
Mesh {
vertices: verts,
triangles: tris,
}
}
}
#[derive(Clone, Debug, Default, PartialEq)]
pub struct Mesh {
pub vertices: Vec<[f64; 3]>,
pub triangles: Vec<[u32; 3]>,
}
impl Mesh {
#[must_use]
pub fn to_obj(&self) -> String {
let mut s = String::new();
for v in &self.vertices {
s.push_str(&format!("v {} {} {}\n", v[0], v[1], v[2]));
}
for t in &self.triangles {
s.push_str(&format!("f {} {} {}\n", t[0] + 1, t[1] + 1, t[2] + 1));
}
s
}
#[must_use]
pub fn surface_area(&self) -> f64 {
self.triangles
.iter()
.map(|t| {
let [a, b, c] = t.map(|i| self.vertices[i as usize]);
let u = [b[0] - a[0], b[1] - a[1], b[2] - a[2]];
let v = [c[0] - a[0], c[1] - a[1], c[2] - a[2]];
let cross = [
u[1] * v[2] - u[2] * v[1],
u[2] * v[0] - u[0] * v[2],
u[0] * v[1] - u[1] * v[0],
];
0.5 * (cross[0] * cross[0] + cross[1] * cross[1] + cross[2] * cross[2]).sqrt()
})
.sum()
}
}
#[cfg(test)]
mod tests {
use super::*;
fn cube_mask(n: usize, lo: usize, hi: usize) -> Mask {
let mut m = Mask::filled([n, n, n], false);
for z in lo..hi {
for y in lo..hi {
for x in lo..hi {
m[[x, y, z]] = true;
}
}
}
m
}
#[test]
fn threshold_counts() {
let mut vol = VoxelGrid::filled([4, 4, 4], 0i32);
vol[[1, 1, 1]] = 10;
vol[[2, 2, 2]] = 5;
let mask = vol.threshold(5);
assert_eq!(mask.count(), 2);
assert!(mask[[1, 1, 1]] && mask[[2, 2, 2]]);
}
#[test]
fn erosion_shrinks_dilation_grows() {
let m = cube_mask(8, 2, 6); assert_eq!(m.count(), 64);
assert_eq!(m.erode().count(), 8); assert_eq!(m.dilate().count(), 64 + 6 * 16); let opened = m.open();
assert!(opened.count() < m.count());
assert!(opened
.iter()
.all(|(p, &v)| !v || m[p]), "open() must be a subset");
assert_eq!(m.close(), m);
}
#[test]
fn erosion_at_grid_boundary_erodes() {
let m = Mask::filled([3, 3, 3], true);
assert_eq!(m.erode().count(), 1);
assert!(m.erode()[[1, 1, 1]]);
}
#[test]
fn single_voxel_mesh_is_closed_cube() {
let mut m = Mask::filled([3, 3, 3], false);
m[[1, 1, 1]] = true;
let mesh = m.to_mesh();
assert_eq!(mesh.vertices.len(), 8);
assert_eq!(mesh.triangles.len(), 12);
assert!((mesh.surface_area() - 6.0).abs() < 1e-9);
}
#[test]
fn mesh_respects_spacing_and_origin() {
let mut m = Mask::filled([2, 2, 2], false)
.with_spacing([2.0, 2.0, 2.0])
.with_origin([10.0, 0.0, 0.0]);
m[[0, 0, 0]] = true;
let mesh = m.to_mesh();
assert!((mesh.surface_area() - 6.0 * 4.0).abs() < 1e-9);
assert!(mesh.vertices.iter().all(|v| v[0] >= 10.0));
}
#[test]
fn interior_faces_are_culled() {
let m = cube_mask(6, 1, 5); let mesh = m.to_mesh();
assert_eq!(mesh.triangles.len(), 192);
assert!((mesh.surface_area() - 6.0 * 16.0).abs() < 1e-9);
}
#[test]
fn obj_export_shape() {
let mut m = Mask::filled([2, 2, 2], false);
m[[0, 0, 0]] = true;
let obj = m.to_mesh().to_obj();
assert_eq!(obj.matches("\nf ").count() + 1, 1 + 12); assert!(!obj.contains("f 0")); }
}