dijkstra3d-core 0.1.0

Voxel-grid Dijkstra and rolling-ball invalidation, ported from seung-lab/dijkstra3d and seung-lab/kimimaro
Documentation
//! Halo-padding utilities for full-volume searches

use crate::dijkstra::Dist;

/// Padded (haloed) dimensions of a volume: each original axis grown by 2 (a
/// one-voxel border on both ends).
#[derive(Debug, Clone, Copy)]
pub(crate) struct PaddedShape {
    /// Padded x extent (`sx + 2`).
    pub psx: u64,
    /// Padded y extent (`sy + 2`).
    pub psy: u64,
    /// Padded z extent (`sz + 2`).
    pub psz: u64,
}

impl PaddedShape {
    /// Build the padded dimensions for an original `(sx, sy, sz)`.
    #[inline]
    pub(crate) fn new(sx: u64, sy: u64, sz: u64) -> Self {
        Self {
            psx: sx + 2,
            psy: sy + 2,
            psz: sz + 2,
        }
    }

    /// Padded xy-plane stride (`psx * psy`).
    #[inline]
    pub(crate) fn psxy(&self) -> u64 {
        self.psx * self.psy
    }

    /// Total padded voxel count (`psx * psy * psz`), saturating on overflow.
    #[inline]
    pub(crate) fn ptotal(&self) -> u64 {
        self.psx.saturating_mul(self.psy).saturating_mul(self.psz)
    }
}

/// Build a one-voxel halo copy of `field` (original dims `sx × sy × sz`, in
/// core canonical order `mem[x + sx*y + sxy*z]`).
///
/// Border cells are never relaxed (their distance is pre-settled by
/// [`set_halo_zero`]), so their value is irrelevant; they are filled with
/// `field[0]` to avoid a `Default`/`Zero` bound. The interior is copied row by
/// row via `copy_from_slice`. This `O(n)` copy is the halo's up-front cost.
///
/// `field` must be non-empty and `field.len() == sx*sy*sz`.
pub(crate) fn pad_field<T: Copy>(
    field: &[T],
    sx: u64,
    sy: u64,
    sz: u64,
    padded: PaddedShape,
) -> Vec<T> {
    let ptotal = padded.ptotal() as usize;
    let mut out = vec![field[0]; ptotal];

    let sx_us = sx as usize;
    let sy_us = sy as usize;
    let sz_us = sz as usize;
    let psx_us = padded.psx as usize;
    let psxy_us = padded.psxy() as usize;

    for z in 0..sz_us {
        for y in 0..sy_us {
            let src_base = (z * sy_us + y) * sx_us;
            let dst_base = (z + 1) * psxy_us + (y + 1) * psx_us + 1;
            out[dst_base..dst_base + sx_us].copy_from_slice(&field[src_base..src_base + sx_us]);
        }
    }
    out
}

/// Map an original `(x, y, z)` to its interior padded linear index.
#[inline]
pub(crate) fn to_padded_index(x: u64, y: u64, z: u64, padded: PaddedShape) -> u64 {
    (z + 1) * padded.psxy() + (y + 1) * padded.psx + (x + 1)
}

/// Decode an interior padded linear index back to the original linear index.
///
/// The padded index must be interior (padded coords in
/// `[1, sx] × [1, sy] × [1, sz]`). Uses one div/mod per call; callers invoke it
/// off the hot loop (during output materialization / path reconstruction only).
#[inline]
pub(crate) fn from_padded_index(p: u64, sx: u64, sxy: u64, psx: u64, psxy: u64) -> u64 {
    let pz = p / psxy;
    let rem = p % psxy;
    let py = rem / psx;
    let px = rem % psx;
    (px - 1) + (py - 1) * sx + (pz - 1) * sxy
}

/// Pre-settle the one-voxel halo of a padded distance buffer to [`Dist::ZERO`],
/// making the border permanently impassable without a per-neighbor bounds check.
///
/// Touches only the `O(surface)` shell, not the `O(volume)` interior.
pub(crate) fn set_halo_zero<D: Dist>(distances: &mut [D], psx: usize, psy: usize, psz: usize) {
    let psxy = psx * psy;
    // z = 0 and z = psz-1 faces (full planes).
    let ztop = (psz - 1) * psxy;
    for p in 0..psxy {
        distances[p] = D::ZERO;
        distances[ztop + p] = D::ZERO;
    }
    // Interior z-planes: y = 0 / y = psy-1 rows, then x = 0 / x = psx-1 columns.
    for z in 1..psz - 1 {
        let zb = z * psxy;
        let yb = zb + (psy - 1) * psx;
        for x in 0..psx {
            distances[zb + x] = D::ZERO; // y = 0 row
            distances[yb + x] = D::ZERO; // y = psy-1 row
        }
        for y in 1..psy - 1 {
            let rb = zb + y * psx;
            distances[rb] = D::ZERO; // x = 0
            distances[rb + psx - 1] = D::ZERO; // x = psx-1
        }
    }
}