use crate::atomic_dist::{atomic_dist_vec, AtomicDist};
use crate::connectivity_graph::ConnectivityGraph;
use crate::dijkstra::{checked_int_distance_bound, select_dist_width, Dist, DistWidth, IntQueue};
use crate::halo::PaddedShape;
use crate::neighborhood::{neighborhood_masks, neighborhood_offsets, DIRECTIONS_26};
use crate::queue::binary_heap::BinaryHeapQueue;
use crate::queue::bucket::BucketQueue;
use crate::queue::PriorityQueue;
use crate::voxel::{ToU64Fast, VolumeShape, VoxelSource};
use crate::{Connectivity, Dijkstra3dError, Result};
use num_traits::ToPrimitive;
use rayon::prelude::*;
#[derive(Debug, Clone)]
pub struct DistanceFieldOutput {
pub distances: Vec<f32>,
pub max_location: Option<u64>,
}
pub fn distance_field<V>(
field: &V,
sources: &[u64],
connectivity: Connectivity,
graph: Option<ConnectivityGraph<'_>>,
return_max_location: bool,
) -> Result<DistanceFieldOutput>
where
V: VoxelSource,
V::Item: ToPrimitive,
{
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 queue = BinaryHeapQueue::new();
for &src in sources {
distances[src as usize] = 0.0;
queue.push(0.0, src);
}
let offsets = neighborhood_offsets(shape.sx as i64, shape.stride_z() as i64);
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 (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 masks = neighborhood_masks();
if let Some(g) = &graph {
if !g.allows(loc, masks[i]) {
continue;
}
}
let neighbor_val = field.get(neighbor)?;
let neighbor_cost_f32 = neighbor_val.to_f32().ok_or_else(|| {
Dijkstra3dError::InvalidInput("field value not convertible to f32".into())
})?;
let new_dist = current_dist + neighbor_cost_f32;
if new_dist < distances[neighbor as usize] {
distances[neighbor as usize] = new_dist;
queue.push(new_dist, neighbor);
}
}
}
let max_location = if 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(DistanceFieldOutput {
distances,
max_location,
})
}
pub fn distance_field_parallel<V>(
field: &V,
sources: &[u64],
connectivity: Connectivity,
graph: Option<ConnectivityGraph<'_>>,
return_max_location: bool,
) -> Result<DistanceFieldOutput>
where
V: VoxelSource + Sync,
V::Item: ToPrimitive,
{
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 delta = choose_delta(field, total);
let (dist, _stats) = delta_step_distance(field, sources, connectivity, graph, delta, false);
let distances: Vec<f32> = dist.iter().map(|d| d.load()).collect();
let max_location = if return_max_location {
find_max_finite(&distances)
} else {
None
};
Ok(DistanceFieldOutput {
distances,
max_location,
})
}
fn choose_delta<V>(field: &V, total: u64) -> f32
where
V: VoxelSource,
V::Item: ToPrimitive,
{
if total == 0 {
return 1.0;
}
let sample_n = total.min(4096);
let stride = (total / sample_n).max(1);
let mut sum = 0.0f64;
let mut count = 0u64;
let mut idx = 0u64;
while idx < total && count < sample_n {
if let Ok(v) = field.get(idx) {
if let Some(f) = v.to_f32() {
if f.is_finite() && f > 0.0 {
sum += f as f64;
count += 1;
}
}
}
idx += stride;
}
if count == 0 {
return 1.0;
}
((sum / count as f64) as f32).max(1.0)
}
#[doc(hidden)]
pub struct BspStats {
pub round_frontier_sizes: Vec<usize>,
pub total_pushed: u64,
pub delta: f32,
pub buckets: usize,
}
#[doc(hidden)]
pub fn distance_field_parallel_instrumented<V>(
field: &V,
sources: &[u64],
connectivity: Connectivity,
graph: Option<ConnectivityGraph<'_>>,
delta: Option<f32>,
) -> Result<BspStats>
where
V: VoxelSource + Sync,
V::Item: ToPrimitive,
{
let total = field.shape().total();
let delta = delta.unwrap_or_else(|| choose_delta(field, total));
let (_dist, stats) = delta_step_distance(field, sources, connectivity, graph, delta, true);
Ok(stats)
}
const DISTANCE_FUSION_THRESHOLD: usize = 2048;
fn delta_step_distance<V>(
field: &V,
sources: &[u64],
connectivity: Connectivity,
graph: Option<ConnectivityGraph<'_>>,
delta: f32,
collect_stats: bool,
) -> (Vec<AtomicDist>, BspStats)
where
V: VoxelSource + Sync,
V::Item: ToPrimitive,
{
let shape = field.shape();
let total = shape.total();
let dist = atomic_dist_vec(total as usize);
for &src in sources {
dist[src as usize].store_zero();
}
let offsets = neighborhood_offsets(shape.sx as i64, shape.stride_z() as i64);
let masks = neighborhood_masks();
let neighbor_count = connectivity.count();
let sx = shape.sx as i64;
let sy = shape.sy as i64;
let sz = shape.sz as i64;
let graph_ref = graph.as_ref();
let inv_delta = 1.0f32 / delta;
let nthreads = rayon::current_num_threads().max(1);
let fusion_threshold = DISTANCE_FUSION_THRESHOLD.max(nthreads * 256);
let mut buckets: Vec<Vec<u64>> = vec![sources.to_vec()];
let mut round_frontier_sizes: Vec<usize> = Vec::new();
let mut total_pushed = 0u64;
let mut buckets_touched = 0usize;
let mut b = 0usize;
while b < buckets.len() {
if buckets[b].is_empty() {
b += 1;
continue;
}
buckets_touched += 1;
loop {
let work = std::mem::take(&mut buckets[b]);
if work.is_empty() {
break;
}
if collect_stats {
round_frontier_sizes.push(work.len());
}
if work.len() < fusion_threshold {
let mut acc: Vec<(u64, u32)> = Vec::with_capacity(work.len() * neighbor_count);
for &loc in &work {
expand_voxel_distance_into(
field,
loc,
&dist,
&offsets,
&masks,
neighbor_count,
graph_ref,
&shape,
sx,
sy,
sz,
b,
inv_delta,
&mut acc,
);
}
total_pushed += acc.len() as u64;
for &(idx, band) in &acc {
let band = band as usize;
if band >= buckets.len() {
buckets.resize_with(band + 1, Vec::new);
}
buckets[band].push(idx);
}
} else {
let min_len = (work.len() / (nthreads * 4)).max(1);
let mut worker_bufs: Vec<Vec<(u64, u32)>> = work
.par_iter()
.with_min_len(min_len)
.fold(
|| Vec::with_capacity(64),
|mut acc, &loc| {
expand_voxel_distance_into(
field,
loc,
&dist,
&offsets,
&masks,
neighbor_count,
graph_ref,
&shape,
sx,
sy,
sz,
b,
inv_delta,
&mut acc,
);
acc
},
)
.collect();
for buf in &mut worker_bufs {
total_pushed += buf.len() as u64;
for &(idx, band) in buf.iter() {
let band = band as usize;
if band >= buckets.len() {
buckets.resize_with(band + 1, Vec::new);
}
buckets[band].push(idx);
}
}
}
}
b += 1;
}
let stats = BspStats {
round_frontier_sizes,
total_pushed,
delta,
buckets: buckets_touched,
};
(dist, stats)
}
#[inline]
#[allow(clippy::too_many_arguments)]
fn expand_voxel_distance_into<V>(
field: &V,
loc: u64,
dist: &[AtomicDist],
offsets: &[i64; 26],
masks: &[u32; 26],
neighbor_count: usize,
graph: Option<&ConnectivityGraph<'_>>,
shape: &crate::voxel::VolumeShape,
sx: i64,
sy: i64,
sz: i64,
current_bucket: usize,
inv_delta: f32,
out: &mut Vec<(u64, u32)>,
) where
V: VoxelSource,
V::Item: ToPrimitive,
{
let current_dist = dist[loc as usize].load();
if !current_dist.is_finite() {
return;
}
if (current_dist * inv_delta) as usize != current_bucket {
return;
}
let (x, y, z) = shape.coords(loc);
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;
if let Some(g) = graph {
if !g.allows(loc, masks[i]) {
continue;
}
}
let neighbor_cost_f32 = match field.get(neighbor) {
Ok(v) => match v.to_f32() {
Some(f) => f,
None => continue,
},
Err(_) => continue,
};
let new_dist = current_dist + neighbor_cost_f32;
if dist[neighbor as usize].relax(new_dist) {
let band = (new_dist * inv_delta) as u32;
out.push((neighbor, band));
}
}
}
#[inline]
fn find_max_finite(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
}
pub fn distance_field_slice_int<T: ToU64Fast>(
field: &[T],
shape: VolumeShape,
sources: &[u64],
connectivity: Connectivity,
graph: Option<ConnectivityGraph<'_>>,
) -> Result<DistanceFieldOutput> {
let total = shape.total();
if field.len() as u64 != total {
return Err(Dijkstra3dError::InvalidInput(format!(
"distance_field_slice_int: slice length {} != shape.total() {}",
field.len(),
total
)));
}
if total > u32::MAX as u64 {
return Err(Dijkstra3dError::InvalidInput(format!(
"distance_field_slice_int: volume {total} exceeds u32::MAX voxels; \
use the u64 trait path"
)));
}
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 max_weight = field.iter().map(|&v| v.to_u64_fast()).max().unwrap_or(0);
let dist_bound = checked_int_distance_bound(shape, max_weight)?;
let width = select_dist_width(dist_bound);
let use_bucket = max_weight < 65_536;
let padded = PaddedShape::new(shape.sx, shape.sy, shape.sz);
if graph.is_none() && padded.ptotal() <= u32::MAX as u64 {
let distances = match (use_bucket, width) {
(true, DistWidth::U16) => distance_field_slice_int_search_padded::<_, _, u16>(
field,
shape,
padded,
sources,
connectivity,
BucketQueue::with_capacity(max_weight as u32),
),
(true, DistWidth::U32) => distance_field_slice_int_search_padded::<_, _, u32>(
field,
shape,
padded,
sources,
connectivity,
BucketQueue::with_capacity(max_weight as u32),
),
(true, DistWidth::U64) => distance_field_slice_int_search_padded::<_, _, u64>(
field,
shape,
padded,
sources,
connectivity,
BucketQueue::with_capacity(max_weight as u32),
),
(false, DistWidth::U16) => distance_field_slice_int_search_padded::<_, _, u16>(
field,
shape,
padded,
sources,
connectivity,
BinaryHeapQueue::<u64, u32>::new(),
),
(false, DistWidth::U32) => distance_field_slice_int_search_padded::<_, _, u32>(
field,
shape,
padded,
sources,
connectivity,
BinaryHeapQueue::<u64, u32>::new(),
),
(false, DistWidth::U64) => distance_field_slice_int_search_padded::<_, _, u64>(
field,
shape,
padded,
sources,
connectivity,
BinaryHeapQueue::<u64, u32>::new(),
),
};
return Ok(DistanceFieldOutput {
distances,
max_location: None,
});
}
let distances = match (use_bucket, width) {
(true, DistWidth::U16) => distance_field_slice_int_search::<_, _, u16>(
field,
shape,
sources,
connectivity,
graph,
BucketQueue::with_capacity(max_weight as u32),
),
(true, DistWidth::U32) => distance_field_slice_int_search::<_, _, u32>(
field,
shape,
sources,
connectivity,
graph,
BucketQueue::with_capacity(max_weight as u32),
),
(true, DistWidth::U64) => distance_field_slice_int_search::<_, _, u64>(
field,
shape,
sources,
connectivity,
graph,
BucketQueue::with_capacity(max_weight as u32),
),
(false, DistWidth::U16) => distance_field_slice_int_search::<_, _, u16>(
field,
shape,
sources,
connectivity,
graph,
BinaryHeapQueue::<u64, u32>::new(),
),
(false, DistWidth::U32) => distance_field_slice_int_search::<_, _, u32>(
field,
shape,
sources,
connectivity,
graph,
BinaryHeapQueue::<u64, u32>::new(),
),
(false, DistWidth::U64) => distance_field_slice_int_search::<_, _, u64>(
field,
shape,
sources,
connectivity,
graph,
BinaryHeapQueue::<u64, u32>::new(),
),
};
Ok(DistanceFieldOutput {
distances,
max_location: None,
})
}
fn distance_field_slice_int_search<T: ToU64Fast, Q: IntQueue, D: Dist>(
field: &[T],
shape: VolumeShape,
sources: &[u64],
connectivity: Connectivity,
graph: Option<ConnectivityGraph<'_>>,
mut queue: Q,
) -> Vec<f32> {
let total = shape.total() as usize;
let mut distances = vec![D::MAX; total];
for &src in sources {
distances[src as usize] = D::ZERO;
queue.push_i(0, src as u32);
}
let sx_i = shape.sx as i64;
let sxy_i = (shape.sx * shape.sy) as i64;
let offsets = neighborhood_offsets(sx_i, sxy_i);
let masks = neighborhood_masks();
let neighbor_count = connectivity.count();
let sx_u = shape.sx as i64;
let sy_u = shape.sy as i64;
let sz_u = shape.sz as i64;
while let Some((dist, loc)) = queue.pop_i() {
let loc_us = loc as usize;
if dist > distances[loc_us].to_priority() {
continue;
}
let (lx, ly, lz) = shape.coords(loc as u64);
let current_dist = distances[loc_us];
for i in 0..neighbor_count {
let (dx, dy, dz) = DIRECTIONS_26[i];
let nx = lx as i64 + dx as i64;
let ny = ly as i64 + dy as i64;
let nz = lz as i64 + dz as i64;
if nx < 0 || nx >= sx_u || ny < 0 || ny >= sy_u || nz < 0 || nz >= sz_u {
continue;
}
let neighbor = (loc as i64 + offsets[i]) as u64;
if let Some(ref g) = graph {
if !g.allows(loc as u64, masks[i]) {
continue;
}
}
let neighbor_cost = field[neighbor as usize].to_u64_fast();
let new_dist = current_dist.add_cost(neighbor_cost);
if new_dist < distances[neighbor as usize] {
distances[neighbor as usize] = new_dist;
queue.push_i(new_dist.to_priority(), neighbor as u32);
}
}
}
distances
.iter()
.map(|&d| {
if d == D::MAX {
f32::INFINITY
} else {
d.to_priority() as f32
}
})
.collect()
}
#[doc(hidden)]
pub fn distance_field_slice_int_unpadded<T: ToU64Fast>(
field: &[T],
shape: VolumeShape,
sources: &[u64],
connectivity: Connectivity,
) -> Result<DistanceFieldOutput> {
let total = shape.total();
if field.len() as u64 != total || total > u32::MAX as u64 || sources.is_empty() {
return Err(Dijkstra3dError::InvalidInput(
"distance_field_slice_int_unpadded: invalid input".into(),
));
}
for &src in sources {
if src >= total {
return Err(Dijkstra3dError::OutOfBounds {
idx: src,
volume_size: total,
});
}
}
let max_weight = field.iter().map(|&v| v.to_u64_fast()).max().unwrap_or(0);
let dist_bound = checked_int_distance_bound(shape, max_weight)?;
let use_u32 = dist_bound <= u32::MAX as u64;
let use_bucket = max_weight < 65_536;
let distances = match (use_bucket, use_u32) {
(true, true) => distance_field_slice_int_search::<_, _, u32>(
field,
shape,
sources,
connectivity,
None,
BucketQueue::with_capacity(max_weight as u32),
),
(true, false) => distance_field_slice_int_search::<_, _, u64>(
field,
shape,
sources,
connectivity,
None,
BucketQueue::with_capacity(max_weight as u32),
),
(false, true) => distance_field_slice_int_search::<_, _, u32>(
field,
shape,
sources,
connectivity,
None,
BinaryHeapQueue::<u64, u32>::new(),
),
(false, false) => distance_field_slice_int_search::<_, _, u64>(
field,
shape,
sources,
connectivity,
None,
BinaryHeapQueue::<u64, u32>::new(),
),
};
Ok(DistanceFieldOutput {
distances,
max_location: None,
})
}
#[allow(clippy::too_many_arguments)]
fn distance_field_slice_int_search_padded<T: ToU64Fast, Q: IntQueue, D: Dist>(
field: &[T],
shape: VolumeShape,
padded: PaddedShape,
sources: &[u64],
connectivity: Connectivity,
mut queue: Q,
) -> Vec<f32> {
let psx = padded.psx;
let psy = padded.psy;
let psz = padded.psz;
let psxy = padded.psxy();
let ptotal = padded.ptotal() as usize;
let field_pad = crate::halo::pad_field(field, shape.sx, shape.sy, shape.sz, padded);
let mut distances = vec![D::MAX; ptotal];
crate::halo::set_halo_zero::<D>(&mut distances, psx as usize, psy as usize, psz as usize);
for &src in sources {
let (sxc, syc, szc) = shape.coords(src);
let sp = crate::halo::to_padded_index(sxc, syc, szc, padded) as u32;
distances[sp as usize] = D::ZERO;
queue.push_i(0, sp);
}
let offsets = neighborhood_offsets(psx as i64, psxy as i64);
let neighbor_count = connectivity.count();
while let Some((dist, loc)) = queue.pop_i() {
let loc_us = loc as usize;
let current_dist = unsafe { *distances.get_unchecked(loc_us) };
if dist > current_dist.to_priority() {
continue;
}
for &off in &offsets[..neighbor_count] {
let neighbor = (loc as i64 + off) as usize;
let neighbor_cost = unsafe { field_pad.get_unchecked(neighbor).to_u64_fast() };
let new_dist = current_dist.add_cost(neighbor_cost);
let dn = unsafe { distances.get_unchecked_mut(neighbor) };
if new_dist < *dn {
*dn = new_dist;
queue.push_i(new_dist.to_priority(), neighbor as u32);
}
}
}
let sx = shape.sx;
let sy = shape.sy;
let sz = shape.sz;
let sxy = sx * sy;
let mut out = vec![0f32; (sx * sy * sz) as usize];
for z in 0..sz {
for y in 0..sy {
let pad_base = (z + 1) * psxy + (y + 1) * psx + 1;
let orig_base = z * sxy + y * sx;
for x in 0..sx {
let d = distances[(pad_base + x) as usize];
out[(orig_base + x) as usize] = if d == D::MAX {
f32::INFINITY
} else {
d.to_priority() as f32
};
}
}
}
out
}
#[cfg(test)]
mod tests {
use super::*;
use crate::voxel::ArrayView3Source;
use ndarray::Array3;
#[test]
fn distance_parallel_matches_sequential_uniform() {
let arr = Array3::<u32>::from_elem((8, 8, 8), 1);
let source = ArrayView3Source::new(arr.view());
let sources = vec![0u64];
let seq = distance_field(&source, &sources, Connectivity::TwentySix, None, false).unwrap();
let par = distance_field_parallel(&source, &sources, Connectivity::TwentySix, None, false)
.unwrap();
assert_eq!(seq.distances.len(), par.distances.len());
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 distance_parallel_multi_source_collision() {
let arr = Array3::<u32>::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 seq = distance_field(&source, &[s0, s1], Connectivity::TwentySix, None, false).unwrap();
let par = distance_field_parallel(&source, &[s0, s1], Connectivity::TwentySix, None, false)
.unwrap();
for i in 0..seq.distances.len() {
assert!((seq.distances[i] - par.distances[i]).abs() < 1e-5);
}
}
#[test]
fn distance_parallel_matches_sequential_random_weights() {
use rand::rngs::StdRng;
use rand::{Rng, SeedableRng};
for &n in &[9usize, 16, 23] {
let mut rng = StdRng::seed_from_u64(0xD3175A + n as u64);
let arr =
Array3::<u32>::from_shape_simple_fn((n, n, n), || rng.random_range(1..=255u32));
let source = ArrayView3Source::new(arr.view());
let shape = source.shape();
let s0 = shape.linear(0, 0, 0);
let sc = shape.linear((n / 2) as u64, (n / 2) as u64, (n / 2) as u64);
let s_end = shape.linear((n - 1) as u64, (n - 1) as u64, (n - 1) as u64);
let configs: [Vec<u64>; 3] = [vec![s0], vec![s0, s_end], vec![sc]];
for srcs in &configs {
let seq =
distance_field(&source, srcs, Connectivity::TwentySix, None, false).unwrap();
let par =
distance_field_parallel(&source, srcs, Connectivity::TwentySix, None, false)
.unwrap();
assert_eq!(seq.distances.len(), par.distances.len());
for i in 0..seq.distances.len() {
assert!(
(seq.distances[i] - par.distances[i]).abs() < 1e-3,
"n={n} srcs={srcs:?} voxel {i}: seq {} != par {}",
seq.distances[i],
par.distances[i]
);
}
}
}
}
#[test]
fn distance_parallel_correct_across_delta_extremes() {
use rand::rngs::StdRng;
use rand::{Rng, SeedableRng};
let n = 14usize;
let mut rng = StdRng::seed_from_u64(7);
let arr = Array3::<u32>::from_shape_simple_fn((n, n, n), || rng.random_range(1..=255u32));
let source = ArrayView3Source::new(arr.view());
let shape = source.shape();
let srcs = vec![shape.linear(0, 0, 0)];
let seq = distance_field(&source, &srcs, Connectivity::TwentySix, None, false).unwrap();
for &delta in &[1.0f32, 7.0, 100.0, 1.0e9] {
let (dist, _stats) = super::delta_step_distance(
&source,
&srcs,
Connectivity::TwentySix,
None,
delta,
false,
);
for i in 0..seq.distances.len() {
let par = dist[i].load();
assert!(
(seq.distances[i] - par).abs() < 1e-3,
"Δ={delta} voxel {i}: seq {} != par {}",
seq.distances[i],
par
);
}
}
}
#[test]
fn distance_int_slice_matches_trait_sequential() {
use ndarray::ShapeBuilder;
use rand::rngs::StdRng;
use rand::{Rng, SeedableRng};
let conns = [
Connectivity::Six,
Connectivity::Eighteen,
Connectivity::TwentySix,
];
let shapes = [(8u64, 8, 8), (6, 7, 5), (10, 4, 9)];
macro_rules! check_dtype {
($t:ty, $lo:expr, $hi:expr, $seed_base:expr) => {{
for &(sx, sy, sz) in &shapes {
let shape = VolumeShape::new(sx, sy, sz);
let total = shape.total();
for seed in 0..3u64 {
let mut rng = StdRng::seed_from_u64($seed_base + seed);
let slice: Vec<$t> = (0..total)
.map(|_| rng.random_range($lo..=$hi) as $t)
.collect();
let arr = ndarray::Array3::from_shape_vec(
(sx as usize, sy as usize, sz as usize).f(),
slice.clone(),
)
.unwrap();
let trait_src = ArrayView3Source::new(arr.view());
let s0 = shape.linear(0, 0, 0);
let s_end = shape.linear(sx - 1, sy - 1, sz - 1);
let s_mid = shape.linear(sx / 2, sy / 2, sz / 2);
let source_sets: [Vec<u64>; 4] = [
vec![s0],
vec![s0, s_end],
vec![s_mid],
vec![s0, s_mid, s_end],
];
for sources in &source_sets {
for &conn in &conns {
let a =
distance_field(&trait_src, sources, conn, None, false).unwrap();
let b =
distance_field_slice_int(&slice, shape, sources, conn, None)
.unwrap();
assert_eq!(
a.distances,
b.distances,
"dtype={} shape={:?} seed={} sources={:?} conn={:?}",
stringify!($t),
(sx, sy, sz),
seed,
sources,
conn
);
}
}
}
}
}};
}
check_dtype!(u8, 1u32, 255u32, 100);
check_dtype!(u16, 1u32, 4_000u32, 200);
check_dtype!(u32, 1u32, 4_000u32, 300);
}
#[test]
fn distance_int_slice_matches_trait_unreachable() {
let shape = VolumeShape::new(4, 4, 4);
let total = shape.total();
let slice = vec![1u32; total as usize];
let arr = ndarray::Array3::from_elem((4usize, 4, 4), 1u32);
let trait_src = ArrayView3Source::new(arr.view());
let sources = vec![shape.linear(0, 0, 0)];
let a = distance_field(&trait_src, &sources, Connectivity::Six, None, false).unwrap();
let b = distance_field_slice_int(&slice, shape, &sources, Connectivity::Six, None).unwrap();
assert_eq!(a.distances, b.distances);
}
#[test]
fn distance_slice_int_padded_matches_unpadded() {
use crate::connectivity_graph::ConnectivityGraph;
use rand::rngs::StdRng;
use rand::{Rng, SeedableRng};
let conns = [
Connectivity::Six,
Connectivity::Eighteen,
Connectivity::TwentySix,
];
let shapes = [(8u64, 8, 8), (6, 7, 5), (10, 4, 9)];
macro_rules! check_dtype {
($t:ty, $lo:expr, $hi:expr, $seed_base:expr) => {{
for &(sx, sy, sz) in &shapes {
let shape = VolumeShape::new(sx, sy, sz);
let total = shape.total();
let allow_all = vec![u32::MAX; total as usize];
for seed in 0..3u64 {
let mut rng = StdRng::seed_from_u64($seed_base + seed);
let slice: Vec<$t> =
(0..total).map(|_| rng.random_range($lo..=$hi) as $t).collect();
let s0 = shape.linear(0, 0, 0);
let s_end = shape.linear(sx - 1, sy - 1, sz - 1);
let s_mid = shape.linear(sx / 2, sy / 2, sz / 2);
let source_sets: [Vec<u64>; 4] = [
vec![s0],
vec![s0, s_end],
vec![s_mid],
vec![s0, s_mid, s_end],
];
for sources in &source_sets {
for &conn in &conns {
let padded = distance_field_slice_int(
&slice, shape, sources, conn, None,
)
.unwrap();
let g = ConnectivityGraph::new(&allow_all, shape).unwrap();
let unpadded = distance_field_slice_int(
&slice, shape, sources, conn, Some(g),
)
.unwrap();
assert_eq!(
padded.distances, unpadded.distances,
"padded != unpadded dtype={} shape={:?} seed={} sources={:?} conn={:?}",
stringify!($t), (sx, sy, sz), seed, sources, conn
);
}
}
}
}
}};
}
check_dtype!(u8, 1u32, 255u32, 400); check_dtype!(u16, 1u32, 4_000u32, 500); check_dtype!(u32, 1u32, 5_000u32, 600); check_dtype!(u32, 70_000u32, 100_000u32, 700); }
#[test]
fn distance_int_slice_rejects_empty_sources() {
let shape = VolumeShape::new(4, 4, 4);
let slice = vec![1u32; shape.total() as usize];
let result = distance_field_slice_int(&slice, shape, &[], Connectivity::Six, None);
assert!(matches!(result, Err(Dijkstra3dError::InvalidInput(_))));
}
#[test]
fn distance_int_slice_rejects_unrepresentable_distance_bound() {
let shape = VolumeShape::new(2, 2, 2);
let field = vec![u64::MAX; shape.total() as usize];
let error =
distance_field_slice_int(&field, shape, &[0], Connectivity::Six, None).unwrap_err();
assert!(matches!(error, Dijkstra3dError::InvalidInput(_)));
}
#[test]
fn distance_parallel_rejects_empty_sources() {
let arr = Array3::<u32>::from_elem((4, 4, 4), 1);
let source = ArrayView3Source::new(arr.view());
let result = distance_field_parallel(&source, &[], Connectivity::TwentySix, None, false);
assert!(matches!(result, Err(Dijkstra3dError::InvalidInput(_))));
}
#[test]
fn distance_u16_matches_u32_and_u64_field() {
use rand::rngs::StdRng;
use rand::{Rng, SeedableRng};
let n = 14u64;
let shape = VolumeShape::new(n, n, n);
let sources = [shape.linear(0, 0, 0), shape.linear(n - 1, n - 1, n - 1)];
let conns = [
Connectivity::Six,
Connectivity::Eighteen,
Connectivity::TwentySix,
];
for seed in 0..16u64 {
let mut rng = StdRng::seed_from_u64(0xD15C_0000 + seed);
let field: Vec<u32> = (0..shape.total())
.map(|_| rng.random_range(1..=6u32))
.collect();
let max_w = field.iter().copied().max().unwrap() as u64;
let dist_bound = (shape.sx + shape.sy + shape.sz + 1) * max_w;
assert_eq!(select_dist_width(dist_bound), DistWidth::U16);
let cap = max_w as u32;
for &conn in &conns {
let d16 = distance_field_slice_int_search::<_, _, u16>(
&field,
shape,
&sources,
conn,
None,
BucketQueue::with_capacity(cap),
);
let d32 = distance_field_slice_int_search::<_, _, u32>(
&field,
shape,
&sources,
conn,
None,
BucketQueue::with_capacity(cap),
);
let d64 = distance_field_slice_int_search::<_, _, u64>(
&field,
shape,
&sources,
conn,
None,
BucketQueue::with_capacity(cap),
);
assert_eq!(
d16, d32,
"u16 vs u32 field differ seed={seed} conn={conn:?}"
);
assert_eq!(
d16, d64,
"u16 vs u64 field differ seed={seed} conn={conn:?}"
);
let pub_field = distance_field_slice_int(&field, shape, &sources, conn, None)
.unwrap()
.distances;
assert_eq!(
pub_field, d16,
"public field != u16 seed={seed} conn={conn:?}"
);
}
}
}
#[test]
fn distance_parallel_narrow_frontier_matches_sequential() {
use rand::rngs::StdRng;
use rand::{Rng, SeedableRng};
let mut rng = StdRng::seed_from_u64(9001);
let arr = Array3::<u32>::from_shape_simple_fn((2, 2, 256), || rng.random_range(1..=200u32));
let source = ArrayView3Source::new(arr.view());
let shape = source.shape();
let srcs = vec![shape.linear(0, 0, 0)];
let seq = distance_field(&source, &srcs, Connectivity::TwentySix, None, false).unwrap();
let par =
distance_field_parallel(&source, &srcs, Connectivity::TwentySix, None, false).unwrap();
assert_eq!(seq.distances.len(), par.distances.len());
for i in 0..seq.distances.len() {
assert!(
(seq.distances[i] - par.distances[i]).abs() < 1e-3,
"narrow-frontier voxel {i}: seq {} != par {}",
seq.distances[i],
par.distances[i]
);
}
}
#[test]
fn distance_parallel_deterministic_across_threads() {
use rand::rngs::StdRng;
use rand::{Rng, SeedableRng};
use rayon::ThreadPoolBuilder;
let n = 34usize;
let mut rng = StdRng::seed_from_u64(0x0DD1);
let arr = Array3::<u32>::from_shape_simple_fn((n, n, n), || rng.random_range(1..=64u32));
let source = ArrayView3Source::new(arr.view());
let shape = source.shape();
let srcs = vec![
shape.linear(0, 0, 0),
shape.linear((n - 1) as u64, (n - 1) as u64, (n - 1) as u64),
];
let seq = distance_field(&source, &srcs, Connectivity::TwentySix, None, false).unwrap();
let mut reference: Option<Vec<f32>> = None;
for &threads in &[1usize, 2, 4, 8, 12] {
let pool = ThreadPoolBuilder::new()
.num_threads(threads)
.build()
.unwrap();
let par = pool.install(|| {
distance_field_parallel(&source, &srcs, Connectivity::TwentySix, None, false)
.unwrap()
});
assert_eq!(
par.distances, seq.distances,
"threads={threads}: distances differ from sequential"
);
match &reference {
None => reference = Some(par.distances),
Some(r) => assert_eq!(
r, &par.distances,
"threads={threads}: distances differ across thread counts (race)"
),
}
}
}
}