use crate::atomic_dist::{atomic_dist_parent_vec, atomic_dist_vec, AtomicDist, AtomicDistParent};
use crate::neighborhood::{neighborhood_offsets, neighborhood_weights, DIRECTIONS_26};
use crate::parental::{
is_neighbor_in_bounds, LibstdcxxCompatHeap, UpstreamCompatEntry, UPSTREAM_DIRECTIONS_26,
};
use crate::queue::binary_heap::BinaryHeapQueue;
use crate::queue::PriorityQueue;
use crate::voxel::{Anisotropy, VoxelSource};
use crate::{Connectivity, Dijkstra3dError, Result};
use num_traits::ToPrimitive;
use num_traits::Zero;
use rayon::prelude::*;
#[derive(Debug, Clone)]
pub struct EdfOutput {
pub distances: Vec<f32>,
pub feature_map: Option<Vec<u64>>,
pub max_location: Option<u64>,
}
#[derive(Debug, Clone, Copy)]
pub struct EdfConfig {
pub anisotropy: Anisotropy,
pub free_space_radius: f32,
pub return_feature_map: bool,
pub return_max_location: bool,
}
impl Default for EdfConfig {
fn default() -> Self {
Self {
anisotropy: Anisotropy::default(),
free_space_radius: 0.0,
return_feature_map: false,
return_max_location: false,
}
}
}
pub fn euclidean_distance_field_upstream_compat_slice<T>(
field: &[T],
shape: crate::voxel::VolumeShape,
sources: &[u64],
anisotropy: Anisotropy,
background: T,
) -> Result<EdfOutput>
where
T: Copy + PartialEq,
{
let total = shape.total();
if field.len() as u64 != total {
return Err(Dijkstra3dError::InvalidInput(format!(
"euclidean_distance_field_upstream_compat_slice: slice length {} != shape.total() {total}",
field.len()
)));
}
if total > u32::MAX as u64 {
return Err(Dijkstra3dError::InvalidInput(format!(
"euclidean_distance_field_upstream_compat_slice: volume {total} exceeds u32::MAX voxels"
)));
}
if sources.is_empty() {
return Err(Dijkstra3dError::InvalidInput(
"sources cannot be empty".into(),
));
}
for &source in sources {
if source >= total {
return Err(Dijkstra3dError::OutOfBounds {
idx: source,
volume_size: total,
});
}
}
let mut distances = vec![f32::INFINITY; total as usize];
let mut queue = LibstdcxxCompatHeap::<u32>::default();
for &source in sources {
distances[source as usize] = 0.0;
queue.push(UpstreamCompatEntry {
priority: 0.0,
payload: source as u32,
});
}
let stride_y = shape.sx as i64;
let stride_z = (shape.sx * shape.sy) as i64;
let offsets = UPSTREAM_DIRECTIONS_26
.map(|(dx, dy, dz)| dx as i64 + dy as i64 * stride_y + dz as i64 * stride_z);
let weights = UPSTREAM_DIRECTIONS_26.map(|(dx, dy, dz)| {
let x = dx as f32 * anisotropy.wx;
let y = dy as f32 * anisotropy.wy;
let z = dz as f32 * anisotropy.wz;
(x * x + y * y + z * z).sqrt()
});
let mut max_distance = -1.0f32;
let mut max_location = total + 1;
while let Some(entry) = queue.pop() {
let loc = entry.payload as usize;
let absolute_distance = distances[loc].abs();
if max_distance < absolute_distance {
max_distance = absolute_distance;
max_location = loc as u64;
}
if distances[loc].is_sign_negative() {
continue;
}
let (x, y, z) = shape.coords(loc as u64);
let interior =
x > 0 && x + 1 < shape.sx && y > 0 && y + 1 < shape.sy && z > 0 && z + 1 < shape.sz;
let current_distance = distances[loc];
for ((direction, &offset), &weight) in
UPSTREAM_DIRECTIONS_26.iter().zip(&offsets).zip(&weights)
{
let (dx, dy, dz) = *direction;
if !interior
&& !is_neighbor_in_bounds(
x,
y,
z,
dx,
dy,
dz,
shape.sx as i64,
shape.sy as i64,
shape.sz as i64,
)
{
continue;
}
let neighbor = (loc as i64 + offset) as usize;
if field[neighbor] == background {
continue;
}
let new_distance = current_distance + weight;
if new_distance < distances[neighbor] {
distances[neighbor] = new_distance;
queue.push(UpstreamCompatEntry {
priority: new_distance,
payload: neighbor as u32,
});
}
}
distances[loc] *= -1.0;
}
for distance in &mut distances {
*distance = distance.abs();
}
Ok(EdfOutput {
distances,
feature_map: None,
max_location: (max_location < total).then_some(max_location),
})
}
pub fn euclidean_distance_field<V>(field: &V, sources: &[u64], cfg: EdfConfig) -> Result<EdfOutput>
where
V: VoxelSource,
V::Item: ToPrimitive + num_traits::Zero + PartialEq,
{
let shape = field.shape();
let total = shape.total();
if sources.is_empty() {
return Err(Dijkstra3dError::InvalidInput(
"sources cannot be empty".into(),
));
}
for &src in sources {
if src >= total {
return Err(Dijkstra3dError::OutOfBounds {
idx: src,
volume_size: total,
});
}
}
let mut distances = vec![f32::INFINITY; total as usize];
let mut feature_map = if cfg.return_feature_map {
Some(vec![u64::MAX; total as usize])
} else {
None
};
let mut queue = BinaryHeapQueue::new();
for (src_idx, &src) in sources.iter().enumerate() {
distances[src as usize] = 0.0;
if let Some(ref mut fm) = feature_map {
fm[src as usize] = src_idx as u64;
}
queue.push(0.0, src);
}
let offsets = neighborhood_offsets(shape.sx as i64, shape.stride_z() as i64);
let weights = neighborhood_weights(cfg.anisotropy);
let connectivity = Connectivity::TwentySix; let neighbor_count = connectivity.count();
while let Some((_dist, loc)) = queue.pop() {
let current_dist = distances[loc as usize];
if _dist > current_dist {
continue;
}
let current_feature = feature_map.as_ref().map(|fm| fm[loc as usize]);
let (x, y, z) = shape.coords(loc);
for i in 0..neighbor_count {
let dir = crate::neighborhood::DIRECTIONS_26[i];
let nx = x as i64 + dir.0 as i64;
let ny = y as i64 + dir.1 as i64;
let nz = z as i64 + dir.2 as i64;
if nx < 0
|| nx >= shape.sx as i64
|| ny < 0
|| ny >= shape.sy as i64
|| nz < 0
|| nz >= shape.sz as i64
{
continue;
}
let neighbor = (loc as i64 + offsets[i]) as u64;
let neighbor_val = field.get(neighbor)?;
if neighbor_val == V::Item::zero() {
continue;
}
let step_cost = weights[i];
let new_dist = current_dist + step_cost;
if new_dist < distances[neighbor as usize] {
distances[neighbor as usize] = new_dist;
if let (Some(ref mut fm), Some(feat)) = (&mut feature_map, current_feature) {
fm[neighbor as usize] = feat;
}
queue.push(new_dist, neighbor);
}
}
}
let max_location = if cfg.return_max_location {
let mut max_idx = None;
let mut max_dist = f32::NEG_INFINITY;
for (idx, &dist) in distances.iter().enumerate() {
if dist.is_finite() && dist > max_dist {
max_dist = dist;
max_idx = Some(idx as u64);
}
}
max_idx
} else {
None
};
Ok(EdfOutput {
distances,
feature_map,
max_location,
})
}
pub fn euclidean_distance_field_parallel<V>(
field: &V,
sources: &[u64],
cfg: EdfConfig,
) -> Result<EdfOutput>
where
V: VoxelSource + Sync,
V::Item: ToPrimitive + Zero + PartialEq + Send + Sync,
{
if cfg.free_space_radius > 0.0 {
return euclidean_distance_field(field, sources, cfg);
}
let shape = field.shape();
let total = shape.total();
if sources.is_empty() {
return Err(Dijkstra3dError::InvalidInput(
"sources cannot be empty".into(),
));
}
for &src in sources {
if src >= total {
return Err(Dijkstra3dError::OutOfBounds {
idx: src,
volume_size: total,
});
}
}
if cfg.return_feature_map && sources.len() >= u32::MAX as usize - 1 {
return Err(Dijkstra3dError::InvalidInput(format!(
"euclidean_distance_field_parallel: too many sources ({}) for feature map; \
max {} when return_feature_map=true",
sources.len(),
u32::MAX - 2
)));
}
if cfg.return_feature_map {
edf_parallel_with_feature_map(field, sources, cfg, shape, total)
} else {
edf_parallel_distance_only(field, sources, cfg, shape, total)
}
}
fn edf_parallel_distance_only<V>(
field: &V,
sources: &[u64],
cfg: EdfConfig,
shape: crate::voxel::VolumeShape,
total: u64,
) -> Result<EdfOutput>
where
V: VoxelSource + Sync,
V::Item: ToPrimitive + Zero + PartialEq + Send + Sync,
{
let dist = atomic_dist_vec(total as usize);
for &src in sources {
dist[src as usize].store_zero();
}
let mut frontier: Vec<u64> = sources.to_vec();
let offsets = neighborhood_offsets(shape.sx as i64, shape.stride_z() as i64);
let weights = neighborhood_weights(cfg.anisotropy);
let neighbor_count = Connectivity::TwentySix.count();
let sx = shape.sx as i64;
let sy = shape.sy as i64;
let sz = shape.sz as i64;
while !frontier.is_empty() {
let next_frontier: Vec<u64> = frontier
.par_iter()
.flat_map_iter(|&loc| {
expand_voxel_edf_dist_only(
field,
loc,
&dist,
&offsets,
&weights,
neighbor_count,
&shape,
sx,
sy,
sz,
)
})
.collect();
frontier = next_frontier;
}
let distances: Vec<f32> = dist.iter().map(|d| d.load()).collect();
let max_location = if cfg.return_max_location {
find_max_finite_edf(&distances)
} else {
None
};
Ok(EdfOutput {
distances,
feature_map: None,
max_location,
})
}
fn edf_parallel_with_feature_map<V>(
field: &V,
sources: &[u64],
cfg: EdfConfig,
shape: crate::voxel::VolumeShape,
total: u64,
) -> Result<EdfOutput>
where
V: VoxelSource + Sync,
V::Item: ToPrimitive + Zero + PartialEq + Send + Sync,
{
let dist_feat = atomic_dist_parent_vec(total as usize);
for (src_idx, &src) in sources.iter().enumerate() {
dist_feat[src as usize].relax_with_parent(0.0, src_idx as u32);
}
let mut frontier: Vec<u64> = sources.to_vec();
let offsets = neighborhood_offsets(shape.sx as i64, shape.stride_z() as i64);
let weights = neighborhood_weights(cfg.anisotropy);
let neighbor_count = Connectivity::TwentySix.count();
let sx = shape.sx as i64;
let sy = shape.sy as i64;
let sz = shape.sz as i64;
while !frontier.is_empty() {
let next_frontier: Vec<u64> = frontier
.par_iter()
.flat_map_iter(|&loc| {
expand_voxel_edf_with_feature(
field,
loc,
&dist_feat,
&offsets,
&weights,
neighbor_count,
&shape,
sx,
sy,
sz,
)
})
.collect();
frontier = next_frontier;
}
let mut distances = Vec::with_capacity(total as usize);
let mut feature_map = Vec::with_capacity(total as usize);
for dp in dist_feat.iter() {
let (feat_plus_one, d) = dp.load();
distances.push(d);
feature_map.push(if feat_plus_one == 0 {
u64::MAX
} else {
(feat_plus_one - 1) as u64
});
}
let max_location = if cfg.return_max_location {
find_max_finite_edf(&distances)
} else {
None
};
Ok(EdfOutput {
distances,
feature_map: Some(feature_map),
max_location,
})
}
#[inline]
#[allow(clippy::too_many_arguments)]
fn expand_voxel_edf_dist_only<V>(
field: &V,
loc: u64,
dist: &[AtomicDist],
offsets: &[i64; 26],
weights: &[f32; 26],
neighbor_count: usize,
shape: &crate::voxel::VolumeShape,
sx: i64,
sy: i64,
sz: i64,
) -> Vec<u64>
where
V: VoxelSource,
V::Item: ToPrimitive + Zero + PartialEq,
{
let current_dist = dist[loc as usize].load();
if !current_dist.is_finite() {
return Vec::new();
}
let (x, y, z) = shape.coords(loc);
let mut newly_relaxed: Vec<u64> = Vec::with_capacity(neighbor_count);
for i in 0..neighbor_count {
let dir = DIRECTIONS_26[i];
let nx = x as i64 + dir.0 as i64;
let ny = y as i64 + dir.1 as i64;
let nz = z as i64 + dir.2 as i64;
if nx < 0 || nx >= sx || ny < 0 || ny >= sy || nz < 0 || nz >= sz {
continue;
}
let neighbor = (loc as i64 + offsets[i]) as u64;
let neighbor_val = match field.get(neighbor) {
Ok(v) => v,
Err(_) => continue,
};
if neighbor_val == V::Item::zero() {
continue;
}
let new_dist = current_dist + weights[i];
if dist[neighbor as usize].relax(new_dist) {
newly_relaxed.push(neighbor);
}
}
newly_relaxed
}
#[inline]
#[allow(clippy::too_many_arguments)]
fn expand_voxel_edf_with_feature<V>(
field: &V,
loc: u64,
dist_feat: &[AtomicDistParent],
offsets: &[i64; 26],
weights: &[f32; 26],
neighbor_count: usize,
shape: &crate::voxel::VolumeShape,
sx: i64,
sy: i64,
sz: i64,
) -> Vec<u64>
where
V: VoxelSource,
V::Item: ToPrimitive + Zero + PartialEq,
{
let (current_feat_plus_one, current_dist) = dist_feat[loc as usize].load();
if !current_dist.is_finite() || current_feat_plus_one == 0 {
return Vec::new();
}
let current_feat_idx = current_feat_plus_one - 1;
let (x, y, z) = shape.coords(loc);
let mut newly_relaxed: Vec<u64> = Vec::with_capacity(neighbor_count);
for i in 0..neighbor_count {
let dir = DIRECTIONS_26[i];
let nx = x as i64 + dir.0 as i64;
let ny = y as i64 + dir.1 as i64;
let nz = z as i64 + dir.2 as i64;
if nx < 0 || nx >= sx || ny < 0 || ny >= sy || nz < 0 || nz >= sz {
continue;
}
let neighbor = (loc as i64 + offsets[i]) as u64;
let neighbor_val = match field.get(neighbor) {
Ok(v) => v,
Err(_) => continue,
};
if neighbor_val == V::Item::zero() {
continue;
}
let new_dist = current_dist + weights[i];
if dist_feat[neighbor as usize].relax_with_parent(new_dist, current_feat_idx) {
newly_relaxed.push(neighbor);
}
}
newly_relaxed
}
#[inline]
fn find_max_finite_edf(distances: &[f32]) -> Option<u64> {
let mut max_idx = None;
let mut max_dist = f32::NEG_INFINITY;
for (idx, &d) in distances.iter().enumerate() {
if d.is_finite() && d > max_dist {
max_dist = d;
max_idx = Some(idx as u64);
}
}
max_idx
}
#[derive(Debug, Clone, Copy)]
enum Axis {
X,
Y,
Z,
}
#[derive(Clone, Copy)]
struct SyncMutPtr<T>(*mut T);
unsafe impl<T> Send for SyncMutPtr<T> {}
unsafe impl<T> Sync for SyncMutPtr<T> {}
impl<T> SyncMutPtr<T> {
#[inline]
unsafe fn read_at(self, i: usize) -> T
where
T: Copy,
{
unsafe { *self.0.add(i) }
}
#[inline]
unsafe fn write_at(self, i: usize, val: T) {
unsafe { *self.0.add(i) = val }
}
}
trait FieldStore: Copy + Send + Sync {
const INF: Self;
fn to_f64(self) -> f64;
fn from_f64(x: f64) -> Self;
}
impl FieldStore for f64 {
const INF: Self = f64::INFINITY;
#[inline]
fn to_f64(self) -> f64 {
self
}
#[inline]
fn from_f64(x: f64) -> Self {
x
}
}
impl FieldStore for f32 {
const INF: Self = f32::INFINITY;
#[inline]
fn to_f64(self) -> f64 {
self as f64
}
#[inline]
fn from_f64(x: f64) -> Self {
x as f32
}
}
const F32_EXACT_INT_MAX: f64 = (1u64 << 24) as f64;
#[inline]
fn f32_field_is_exact(shape: crate::voxel::VolumeShape, a_x: f64, a_y: f64, a_z: f64) -> bool {
let integral = a_x.fract() == 0.0 && a_y.fract() == 0.0 && a_z.fract() == 0.0;
if !integral {
return false;
}
let dx = (shape.sx as f64 - 1.0).max(0.0);
let dy = (shape.sy as f64 - 1.0).max(0.0);
let dz = (shape.sz as f64 - 1.0).max(0.0);
let max_sq = a_x * dx * dx + a_y * dy * dy + a_z * dz * dz;
max_sq <= F32_EXACT_INT_MAX
}
struct EdtScratch {
f_line: Vec<f64>,
out_line: Vec<f64>,
v: Vec<usize>,
z: Vec<f64>,
feat_line: Vec<u64>,
feat_out: Vec<u64>,
}
impl EdtScratch {
fn new(n: usize) -> Self {
Self {
f_line: vec![0.0; n],
out_line: vec![0.0; n],
v: vec![0usize; n],
z: vec![0.0; n + 1],
feat_line: vec![u64::MAX; n],
feat_out: vec![u64::MAX; n],
}
}
}
#[inline]
#[allow(clippy::needless_range_loop)]
fn edt_1d(f: &[f64], a: f64, out: &mut [f64], v: &mut [usize], z: &mut [f64]) {
let n = f.len();
let mut k: isize = -1;
for q in 0..n {
let fq = f[q];
if !fq.is_finite() {
continue;
}
if k < 0 {
k = 0;
v[0] = q;
z[0] = f64::NEG_INFINITY;
z[1] = f64::INFINITY;
continue;
}
let aq2 = a * (q as f64) * (q as f64);
loop {
let p = v[k as usize];
let s = ((fq + aq2) - (f[p] + a * (p as f64) * (p as f64)))
/ (2.0 * a * (q as f64 - p as f64));
if s <= z[k as usize] {
k -= 1;
} else {
k += 1;
v[k as usize] = q;
z[k as usize] = s;
z[(k + 1) as usize] = f64::INFINITY;
break;
}
}
}
if k < 0 {
for o in out.iter_mut() {
*o = f64::INFINITY;
}
return;
}
let mut kk: usize = 0;
for q in 0..n {
let qf = q as f64;
while z[kk + 1] < qf {
kk += 1;
}
let p = v[kk];
let d = qf - p as f64;
out[q] = a * d * d + f[p];
}
}
#[inline]
#[allow(clippy::too_many_arguments)]
#[allow(clippy::needless_range_loop)]
fn edt_1d_feat(
f: &[f64],
feat_in: &[u64],
a: f64,
out: &mut [f64],
feat_out: &mut [u64],
v: &mut [usize],
z: &mut [f64],
) {
let n = f.len();
let mut k: isize = -1;
for q in 0..n {
let fq = f[q];
if !fq.is_finite() {
continue;
}
if k < 0 {
k = 0;
v[0] = q;
z[0] = f64::NEG_INFINITY;
z[1] = f64::INFINITY;
continue;
}
let aq2 = a * (q as f64) * (q as f64);
loop {
let p = v[k as usize];
let s = ((fq + aq2) - (f[p] + a * (p as f64) * (p as f64)))
/ (2.0 * a * (q as f64 - p as f64));
if s <= z[k as usize] {
k -= 1;
} else {
k += 1;
v[k as usize] = q;
z[k as usize] = s;
z[(k + 1) as usize] = f64::INFINITY;
break;
}
}
}
if k < 0 {
for o in out.iter_mut() {
*o = f64::INFINITY;
}
for fo in feat_out.iter_mut() {
*fo = u64::MAX;
}
return;
}
let mut kk: usize = 0;
for q in 0..n {
let qf = q as f64;
while z[kk + 1] < qf {
kk += 1;
}
let p = v[kk];
let d = qf - p as f64;
out[q] = a * d * d + f[p];
feat_out[q] = feat_in[p];
}
}
#[inline]
fn axis_geometry(axis: Axis, sx: usize, sy: usize, sz: usize) -> (usize, usize, usize) {
let sxy = sx * sy;
match axis {
Axis::X => (1, sx, sy * sz),
Axis::Y => (sx, sy, sx * sz),
Axis::Z => (sxy, sz, sx * sy),
}
}
#[inline]
fn line_start(axis: Axis, l: usize, sx: usize, sxy: usize) -> usize {
match axis {
Axis::X => l * sx,
Axis::Y => (l % sx) + (l / sx) * sxy,
Axis::Z => l,
}
}
#[inline]
fn run_lines<F>(num_lines: usize, n: usize, parallel: bool, body: F)
where
F: Fn(usize, &mut EdtScratch) + Sync,
{
if parallel {
let threads = rayon::current_num_threads().max(1);
let target_tasks = threads.saturating_mul(8).max(1);
let chunk = num_lines.div_ceil(target_tasks).max(1);
let n_chunks = num_lines.div_ceil(chunk);
(0..n_chunks).into_par_iter().for_each_init(
|| EdtScratch::new(n),
|scratch, c| {
let lo = c * chunk;
let hi = ((c + 1) * chunk).min(num_lines);
for l in lo..hi {
body(l, scratch);
}
},
);
} else {
let mut scratch = EdtScratch::new(n);
for l in 0..num_lines {
body(l, &mut scratch);
}
}
}
fn edt_pass<S: FieldStore>(
f: &mut [S],
a: f64,
axis: Axis,
shape: crate::voxel::VolumeShape,
parallel: bool,
) {
let sx = shape.sx as usize;
let sy = shape.sy as usize;
let sz = shape.sz as usize;
let sxy = sx * sy;
let (stride, n, num_lines) = axis_geometry(axis, sx, sy, sz);
let ptr = SyncMutPtr(f.as_mut_ptr());
let body = move |l: usize, scratch: &mut EdtScratch| {
let start = line_start(axis, l, sx, sxy);
unsafe {
for j in 0..n {
scratch.f_line[j] = ptr.read_at(start + j * stride).to_f64();
}
}
edt_1d(
&scratch.f_line[..n],
a,
&mut scratch.out_line[..n],
&mut scratch.v[..n],
&mut scratch.z[..=n],
);
unsafe {
for j in 0..n {
ptr.write_at(start + j * stride, S::from_f64(scratch.out_line[j]));
}
}
};
run_lines(num_lines, n, parallel, body);
}
fn edt_pass_feat<S: FieldStore>(
f: &mut [S],
feat: &mut [u64],
a: f64,
axis: Axis,
shape: crate::voxel::VolumeShape,
parallel: bool,
) {
let sx = shape.sx as usize;
let sy = shape.sy as usize;
let sz = shape.sz as usize;
let sxy = sx * sy;
let (stride, n, num_lines) = axis_geometry(axis, sx, sy, sz);
let fptr = SyncMutPtr(f.as_mut_ptr());
let featptr = SyncMutPtr(feat.as_mut_ptr());
let body = move |l: usize, scratch: &mut EdtScratch| {
let start = line_start(axis, l, sx, sxy);
unsafe {
for j in 0..n {
let idx = start + j * stride;
scratch.f_line[j] = fptr.read_at(idx).to_f64();
scratch.feat_line[j] = featptr.read_at(idx);
}
}
edt_1d_feat(
&scratch.f_line[..n],
&scratch.feat_line[..n],
a,
&mut scratch.out_line[..n],
&mut scratch.feat_out[..n],
&mut scratch.v[..n],
&mut scratch.z[..=n],
);
unsafe {
for j in 0..n {
let idx = start + j * stride;
fptr.write_at(idx, S::from_f64(scratch.out_line[j]));
featptr.write_at(idx, scratch.feat_out[j]);
}
}
};
run_lines(num_lines, n, parallel, body);
}
fn exact_edf_impl<V>(
field: &V,
sources: &[u64],
cfg: EdfConfig,
parallel: bool,
) -> Result<EdfOutput>
where
V: VoxelSource,
{
let shape = field.shape();
let total = shape.total();
if sources.is_empty() {
return Err(Dijkstra3dError::InvalidInput(
"sources cannot be empty".into(),
));
}
for &src in sources {
if src >= total {
return Err(Dijkstra3dError::OutOfBounds {
idx: src,
volume_size: total,
});
}
}
let a_x = (cfg.anisotropy.wx as f64).powi(2);
let a_y = (cfg.anisotropy.wy as f64).powi(2);
let a_z = (cfg.anisotropy.wz as f64).powi(2);
let out = if f32_field_is_exact(shape, a_x, a_y, a_z) {
exact_edf_run::<f32>(sources, cfg, parallel, shape, total, a_x, a_y, a_z)
} else {
exact_edf_run::<f64>(sources, cfg, parallel, shape, total, a_x, a_y, a_z)
};
Ok(out)
}
#[allow(clippy::too_many_arguments)]
fn exact_edf_run<S: FieldStore>(
sources: &[u64],
cfg: EdfConfig,
parallel: bool,
shape: crate::voxel::VolumeShape,
total: u64,
a_x: f64,
a_y: f64,
a_z: f64,
) -> EdfOutput {
let mut f = vec![S::INF; total as usize];
let want_feat = cfg.return_feature_map;
let mut feat: Vec<u64> = if want_feat {
vec![u64::MAX; total as usize]
} else {
Vec::new()
};
let zero = S::from_f64(0.0);
for (i, &src) in sources.iter().enumerate() {
f[src as usize] = zero;
if want_feat {
feat[src as usize] = i as u64;
}
}
if want_feat {
edt_pass_feat(&mut f, &mut feat, a_x, Axis::X, shape, parallel);
edt_pass_feat(&mut f, &mut feat, a_y, Axis::Y, shape, parallel);
edt_pass_feat(&mut f, &mut feat, a_z, Axis::Z, shape, parallel);
} else {
edt_pass(&mut f, a_x, Axis::X, shape, parallel);
edt_pass(&mut f, a_y, Axis::Y, shape, parallel);
edt_pass(&mut f, a_z, Axis::Z, shape, parallel);
}
let to_dist = |d: &S| -> f32 {
let d = d.to_f64();
if d.is_finite() {
d.sqrt() as f32
} else {
f32::INFINITY
}
};
let distances: Vec<f32> = if parallel {
f.par_iter().map(to_dist).collect()
} else {
f.iter().map(to_dist).collect()
};
let feature_map = if want_feat { Some(feat) } else { None };
let max_location = if cfg.return_max_location {
find_max_finite_edf(&distances)
} else {
None
};
EdfOutput {
distances,
feature_map,
max_location,
}
}
pub fn exact_euclidean_distance_field<V>(
field: &V,
sources: &[u64],
cfg: EdfConfig,
) -> Result<EdfOutput>
where
V: VoxelSource,
{
exact_edf_impl(field, sources, cfg, false)
}
pub fn exact_euclidean_distance_field_parallel<V>(
field: &V,
sources: &[u64],
cfg: EdfConfig,
) -> Result<EdfOutput>
where
V: VoxelSource,
{
exact_edf_impl(field, sources, cfg, true)
}
#[cfg(test)]
mod tests {
use super::*;
use crate::voxel::ArrayView3Source;
use ndarray::Array3;
#[test]
fn edf_parallel_matches_sequential_no_feature_map() {
let arr = Array3::<u8>::from_elem((8, 8, 8), 1);
let source = ArrayView3Source::new(arr.view());
let cfg = EdfConfig::default();
let seq = euclidean_distance_field(&source, &[0], cfg).unwrap();
let par = euclidean_distance_field_parallel(&source, &[0], cfg).unwrap();
for i in 0..seq.distances.len() {
assert!(
(seq.distances[i] - par.distances[i]).abs() < 1e-5,
"voxel {}: seq {} != par {}",
i,
seq.distances[i],
par.distances[i]
);
}
}
#[test]
fn edf_parallel_matches_sequential_with_feature_map() {
let arr = Array3::<u8>::from_elem((6, 6, 6), 1);
let source = ArrayView3Source::new(arr.view());
let shape = source.shape();
let s0 = shape.linear(0, 0, 0);
let s1 = shape.linear(5, 5, 5);
let mut cfg = EdfConfig::default();
cfg.return_feature_map = true;
let seq = euclidean_distance_field(&source, &[s0, s1], cfg).unwrap();
let par = euclidean_distance_field_parallel(&source, &[s0, s1], cfg).unwrap();
for i in 0..seq.distances.len() {
assert!((seq.distances[i] - par.distances[i]).abs() < 1e-5);
}
let seq_fm = seq.feature_map.unwrap();
let par_fm = par.feature_map.unwrap();
for i in 0..seq_fm.len() {
let seq_unclaimed = seq_fm[i] == u64::MAX;
let par_unclaimed = par_fm[i] == u64::MAX;
assert_eq!(
seq_unclaimed, par_unclaimed,
"voxel {} unclaimed mismatch",
i
);
}
}
#[test]
fn edf_parallel_anisotropy() {
let arr = Array3::<u8>::from_elem((8, 8, 8), 1);
let source = ArrayView3Source::new(arr.view());
let mut cfg = EdfConfig::default();
cfg.anisotropy = crate::voxel::Anisotropy::new(4.0, 4.0, 40.0);
let seq = euclidean_distance_field(&source, &[0], cfg).unwrap();
let par = euclidean_distance_field_parallel(&source, &[0], cfg).unwrap();
for i in 0..seq.distances.len() {
assert!(
(seq.distances[i] - par.distances[i]).abs() < 1e-3,
"voxel {}: seq {} != par {}",
i,
seq.distances[i],
par.distances[i]
);
}
}
#[test]
fn edf_parallel_falls_back_for_free_space_radius() {
let arr = Array3::<u8>::from_elem((4, 4, 4), 1);
let source = ArrayView3Source::new(arr.view());
let mut cfg = EdfConfig::default();
cfg.free_space_radius = 2.0;
let result = euclidean_distance_field_parallel(&source, &[0], cfg);
assert!(result.is_ok());
}
fn brute_force_exact(
shape: crate::voxel::VolumeShape,
sources: &[u64],
aniso: crate::voxel::Anisotropy,
) -> Vec<f32> {
let total = shape.total() as usize;
let mut out = vec![f32::INFINITY; total];
let src_coords: Vec<(i64, i64, i64)> = sources
.iter()
.map(|&s| {
let (x, y, z) = shape.coords(s);
(x as i64, y as i64, z as i64)
})
.collect();
for idx in 0..total {
let (x, y, z) = shape.coords(idx as u64);
let (x, y, z) = (x as i64, y as i64, z as i64);
let mut best = f64::INFINITY;
for &(sx, sy, sz) in &src_coords {
let dx = (x - sx) as f64 * aniso.wx as f64;
let dy = (y - sy) as f64 * aniso.wy as f64;
let dz = (z - sz) as f64 * aniso.wz as f64;
let d2 = dx * dx + dy * dy + dz * dz;
if d2 < best {
best = d2;
}
}
out[idx] = best.sqrt() as f32;
}
out
}
fn assert_close(a: &[f32], b: &[f32], tol: f32, ctx: &str) {
assert_eq!(a.len(), b.len(), "{ctx}: length mismatch");
for i in 0..a.len() {
assert!(
(a[i] - b[i]).abs() <= tol,
"{ctx}: voxel {i}: {} vs {} (tol {})",
a[i],
b[i],
tol
);
}
}
#[test]
fn exact_edf_matches_bruteforce_isotropic() {
let arr = Array3::<u8>::from_elem((5, 6, 7), 1);
let source = ArrayView3Source::new(arr.view());
let shape = source.shape();
let sources = vec![
shape.linear(0, 0, 0),
shape.linear(4, 5, 6),
shape.linear(2, 1, 3),
];
let cfg = EdfConfig::default();
let got = exact_euclidean_distance_field(&source, &sources, cfg).unwrap();
let want = brute_force_exact(shape, &sources, cfg.anisotropy);
assert_close(&got.distances, &want, 1e-4, "exact isotropic");
}
#[test]
fn exact_edf_matches_bruteforce_anisotropic() {
let arr = Array3::<u8>::from_elem((7, 5, 4), 1);
let source = ArrayView3Source::new(arr.view());
let shape = source.shape();
let sources = vec![shape.linear(0, 0, 0), shape.linear(6, 4, 3)];
let mut cfg = EdfConfig::default();
cfg.anisotropy = crate::voxel::Anisotropy::new(4.0, 4.0, 40.0);
let got = exact_euclidean_distance_field(&source, &sources, cfg).unwrap();
let want = brute_force_exact(shape, &sources, cfg.anisotropy);
assert_close(&got.distances, &want, 1e-2, "exact anisotropic");
}
#[test]
fn exact_edf_parallel_matches_sequential() {
let arr = Array3::<u8>::from_elem((9, 8, 10), 1);
let source = ArrayView3Source::new(arr.view());
let shape = source.shape();
let sources = vec![
shape.linear(0, 0, 0),
shape.linear(8, 7, 9),
shape.linear(4, 0, 5),
];
let cfg = EdfConfig::default();
let seq = exact_euclidean_distance_field(&source, &sources, cfg).unwrap();
let par = exact_euclidean_distance_field_parallel(&source, &sources, cfg).unwrap();
assert_eq!(seq.distances, par.distances, "seq vs par distances");
}
#[test]
fn exact_edf_deterministic_across_thread_counts() {
let arr = Array3::<u8>::from_elem((12, 11, 10), 1);
let source = ArrayView3Source::new(arr.view());
let shape = source.shape();
let sources = vec![shape.linear(0, 0, 0), shape.linear(11, 10, 9)];
let cfg = EdfConfig::default();
let run = |threads: usize| {
let pool = rayon::ThreadPoolBuilder::new()
.num_threads(threads)
.build()
.unwrap();
pool.install(|| {
exact_euclidean_distance_field_parallel(&source, &sources, cfg)
.unwrap()
.distances
})
};
let d1 = run(1);
let d4 = run(4);
assert_eq!(d1, d4, "exact EDT must be identical at 1 vs 4 threads");
}
#[test]
fn exact_edf_is_more_accurate_than_chamfer_off_diagonal() {
let n = 16usize;
let arr = Array3::<u8>::from_elem((n, n, n), 1);
let source = ArrayView3Source::new(arr.view());
let shape = source.shape();
let corner = shape.linear(0, 0, 0);
let (tx, ty, tz) = (15u64, 7u64, 3u64);
let target = shape.linear(tx, ty, tz);
let cfg = EdfConfig::default();
let exact = exact_euclidean_distance_field(&source, &[corner], cfg).unwrap();
let chamfer = euclidean_distance_field(&source, &[corner], cfg).unwrap();
let true_dist = ((tx * tx + ty * ty + tz * tz) as f32).sqrt();
let exact_d = exact.distances[target as usize];
let chamfer_d = chamfer.distances[target as usize];
assert!(
(exact_d - true_dist).abs() < 1e-3,
"exact {exact_d} != true Euclidean {true_dist}"
);
assert!(
chamfer_d > exact_d + 0.5,
"chamfer {chamfer_d} should exceed exact {exact_d} by the diagonal error"
);
}
#[test]
fn exact_edf_feature_map_is_a_nearest_source() {
let arr = Array3::<u8>::from_elem((8, 8, 8), 1);
let source = ArrayView3Source::new(arr.view());
let shape = source.shape();
let sources = vec![
shape.linear(0, 0, 0),
shape.linear(7, 7, 7),
shape.linear(7, 0, 0),
];
let mut cfg = EdfConfig::default();
cfg.return_feature_map = true;
let got = exact_euclidean_distance_field_parallel(&source, &sources, cfg).unwrap();
let fm = got.feature_map.expect("feature map requested");
for idx in 0..shape.total() as usize {
let feat = fm[idx];
assert!(feat != u64::MAX, "voxel {idx} unclaimed");
let s = sources[feat as usize];
let (sx, sy, sz) = shape.coords(s);
let (x, y, z) = shape.coords(idx as u64);
let dx = x as f64 - sx as f64;
let dy = y as f64 - sy as f64;
let dz = z as f64 - sz as f64;
let feat_dist = (dx * dx + dy * dy + dz * dz).sqrt() as f32;
assert!(
(feat_dist - got.distances[idx]).abs() < 1e-3,
"voxel {idx}: feature source dist {feat_dist} != reported {}",
got.distances[idx]
);
}
}
#[test]
fn exact_edf_source_voxels_are_zero() {
let arr = Array3::<u8>::from_elem((6, 7, 5), 1);
let source = ArrayView3Source::new(arr.view());
let shape = source.shape();
let sources = vec![shape.linear(3, 2, 4), shape.linear(0, 6, 0)];
let cfg = EdfConfig::default();
let got = exact_euclidean_distance_field(&source, &sources, cfg).unwrap();
for &s in &sources {
assert_eq!(got.distances[s as usize], 0.0, "source {s} not zero");
}
}
#[test]
fn exact_edf_rejects_empty_and_oob_sources() {
let arr = Array3::<u8>::from_elem((4, 4, 4), 1);
let source = ArrayView3Source::new(arr.view());
let cfg = EdfConfig::default();
assert!(exact_euclidean_distance_field(&source, &[], cfg).is_err());
assert!(exact_euclidean_distance_field(&source, &[9999], cfg).is_err());
}
#[test]
fn f32_field_is_exact_decision() {
use crate::voxel::VolumeShape;
let iso512 = VolumeShape::new(512, 512, 512);
assert!(f32_field_is_exact(iso512, 1.0, 1.0, 1.0));
let aniso256 = VolumeShape::new(256, 256, 256);
assert!(!f32_field_is_exact(aniso256, 16.0, 16.0, 1600.0));
assert!(!f32_field_is_exact(iso512, 2.25, 1.0, 1.0));
assert!(f32_field_is_exact(
VolumeShape::new(4097, 1, 1),
1.0,
1.0,
1.0
));
assert!(!f32_field_is_exact(
VolumeShape::new(4098, 1, 1),
1.0,
1.0,
1.0
));
}
#[test]
fn exact_edf_f32_storage_exact_near_boundary() {
let n = 4096usize;
let arr = Array3::<u8>::from_elem((n, 1, 1), 1);
let source = ArrayView3Source::new(arr.view());
let shape = source.shape();
let src = shape.linear(0, 0, 0);
let cfg = EdfConfig::default();
assert!(
f32_field_is_exact(shape, 1.0, 1.0, 1.0),
"should pick f32 path"
);
let got = exact_euclidean_distance_field(&source, &[src], cfg).unwrap();
for x in 0..n as u64 {
let idx = shape.linear(x, 0, 0) as usize;
assert_eq!(
got.distances[idx], x as f32,
"voxel x={x}: f32 storage lost the exact distance"
);
}
}
#[test]
fn exact_edf_f64_fallback_non_integer_anisotropy_matches_bruteforce() {
let arr = Array3::<u8>::from_elem((9, 7, 6), 1);
let source = ArrayView3Source::new(arr.view());
let shape = source.shape();
let sources = vec![shape.linear(0, 0, 0), shape.linear(8, 6, 5)];
let mut cfg = EdfConfig::default();
cfg.anisotropy = crate::voxel::Anisotropy::new(1.5, 1.0, 1.0); let a_x = (cfg.anisotropy.wx as f64).powi(2);
assert!(
!f32_field_is_exact(shape, a_x, 1.0, 1.0),
"non-integer anisotropy must take the f64 fallback"
);
let got = exact_euclidean_distance_field(&source, &sources, cfg).unwrap();
let want = brute_force_exact(shape, &sources, cfg.anisotropy);
assert_close(&got.distances, &want, 1e-4, "f64 fallback anisotropic");
}
}