dijkstra3d-core 0.1.0

Voxel-grid Dijkstra and rolling-ball invalidation, ported from seung-lab/dijkstra3d and seung-lab/kimimaro
Documentation
//! 6 / 18 / 26 connectivity neighbor offsets, masks, and weights.
//!
//! Direct port of `compute_neighborhood_*` from `dijkstra3d.hpp`. Indices and
//! ordering must match the upstream exactly so that:
//!   - the voxel-connectivity-graph bitfield interprets identically, and
//!   - per-direction edge weights line up with the offsets they describe.

use crate::voxel::Anisotropy;

/// Connectivity choice for path-finding and distance functions.
///
/// 2D values 4 and 8 are mapped onto 3D 6 and 18 internally (sz must be 1).
#[derive(Debug, Clone, Copy, PartialEq, Eq)]
pub enum Connectivity {
    /// Face-only neighbors (3D L1 / 2D 4-connected).
    Six,
    /// Face + edge neighbors (3D / 2D 8-connected when sz=1).
    Eighteen,
    /// Face + edge + corner neighbors (3D Lāˆž).
    TwentySix,
}

impl Connectivity {
    /// Number of neighbors this connectivity considers.
    pub fn count(self) -> usize {
        match self {
            Connectivity::Six => 6,
            Connectivity::Eighteen => 18,
            Connectivity::TwentySix => 26,
        }
    }

    /// Construct from the integer values used in the Python API.
    ///
    /// Accepts 4, 8 (2D), and 6, 18, 26 (3D).
    pub fn from_int(value: u32) -> Option<Self> {
        match value {
            4 | 6 => Some(Connectivity::Six),
            8 | 18 => Some(Connectivity::Eighteen),
            26 => Some(Connectivity::TwentySix),
            _ => None,
        }
    }
}

/// Canonical ordering of the 26 neighbor directions as `(dx, dy, dz)` tuples.
///
/// Order must match `dijkstra3d.hpp::compute_neighborhood_26`. Slots 0..5 are
/// face neighbors, 6..17 edge, 18..25 corner. The voxel-connectivity-graph
/// bit `i` permits direction `DIRECTIONS_26[i]`.
pub const DIRECTIONS_26: [(i32, i32, i32); 26] = [
    // Face neighbors (6-connected): 0..5
    (1, 0, 0),  // 0: +x
    (-1, 0, 0), // 1: -x
    (0, 1, 0),  // 2: +y
    (0, -1, 0), // 3: -y
    (0, 0, 1),  // 4: +z
    (0, 0, -1), // 5: -z
    // Edge neighbors (additional for 18-connected): 6..17
    (1, 1, 0),   // 6:  +x+y
    (1, -1, 0),  // 7:  +x-y
    (-1, 1, 0),  // 8:  -x+y
    (-1, -1, 0), // 9:  -x-y
    (1, 0, 1),   // 10: +x+z
    (1, 0, -1),  // 11: +x-z
    (-1, 0, 1),  // 12: -x+z
    (-1, 0, -1), // 13: -x-z
    (0, 1, 1),   // 14: +y+z
    (0, 1, -1),  // 15: +y-z
    (0, -1, 1),  // 16: -y+z
    (0, -1, -1), // 17: -y-z
    // Corner neighbors (additional for 26-connected): 18..25
    (1, 1, 1),    // 18: +x+y+z
    (1, 1, -1),   // 19: +x+y-z
    (1, -1, 1),   // 20: +x-y+z
    (1, -1, -1),  // 21: +x-y-z
    (-1, 1, 1),   // 22: -x+y+z
    (-1, 1, -1),  // 23: -x+y-z
    (-1, -1, 1),  // 24: -x-y+z
    (-1, -1, -1), // 25: -x-y-z
];

/// Compute the 26 neighbor linear-index offsets for a given `(sx, sxy)` pair.
///
/// In Fortran order (x-fastest-varying), linear index = x + y*sx + z*sxy where
/// sxy = sx * sy. The offset for direction `(dx, dy, dz)` is therefore
/// `dx + dy*sx + dz*sxy`.
pub fn neighborhood_offsets(sx: i64, sxy: i64) -> [i64; 26] {
    let mut out = [0i64; 26];
    let mut i = 0;
    while i < 26 {
        let (dx, dy, dz) = DIRECTIONS_26[i];
        out[i] = dx as i64 + (dy as i64) * sx + (dz as i64) * sxy;
        i += 1;
    }
    out
}

/// Bitmask for each of the 26 directions, used by the voxel connectivity graph.
///
/// `mask[i]` is the bit that, when set in `voxel_graph[loc]`, indicates that
/// stepping from `loc` in direction `DIRECTIONS_26[i]` is permitted.
pub fn neighborhood_masks() -> [u32; 26] {
    let mut out = [0u32; 26];
    let mut i = 0u32;
    while i < 26 {
        out[i as usize] = 1u32 << i;
        i += 1;
    }
    out
}

/// Geometric step length for each of the 26 neighbor directions, under the
/// supplied `anisotropy`.
///
/// `weights[i]` pairs with `neighborhood_offsets()[i]` and `DIRECTIONS_26[i]`.
/// For an isotropic volume `(1, 1, 1)`:
/// - face neighbors → 1
/// - edge neighbors → √2
/// - corner neighbors → √3
///
/// For anisotropic volumes the weight is the Euclidean length of the step
/// vector under per-axis voxel sizes, i.e.
/// `sqrt((dx * wx)^2 + (dy * wy)^2 + (dz * wz)^2)`.
pub fn neighborhood_weights(anisotropy: Anisotropy) -> [f32; 26] {
    let wx = anisotropy.wx;
    let wy = anisotropy.wy;
    let wz = anisotropy.wz;

    let mut out = [0f32; 26];
    let mut i = 0;
    while i < 26 {
        let (dx, dy, dz) = DIRECTIONS_26[i];
        let ex = dx as f32 * wx;
        let ey = dy as f32 * wy;
        let ez = dz as f32 * wz;
        out[i] = (ex * ex + ey * ey + ez * ez).sqrt();
        i += 1;
    }
    out
}

#[cfg(test)]
mod tests {
    use super::*;

    #[test]
    fn directions_offsets_agree() {
        // For sx=3, sxy=9 the offset for (dx,dy,dz) is dx + 3*dy + 9*dz.
        let offsets = neighborhood_offsets(3, 9);
        for i in 0..26 {
            let (dx, dy, dz) = DIRECTIONS_26[i];
            let expected = dx as i64 + (dy as i64) * 3 + (dz as i64) * 9;
            assert_eq!(offsets[i], expected, "offset mismatch at index {i}");
        }
    }

    #[test]
    fn test_neighborhood_offsets_basic() {
        let offsets = neighborhood_offsets(3, 9);
        // Faces
        assert_eq!(offsets[0], 1);
        assert_eq!(offsets[1], -1);
        assert_eq!(offsets[2], 3);
        assert_eq!(offsets[3], -3);
        assert_eq!(offsets[4], 9);
        assert_eq!(offsets[5], -9);
        // Sample edge / corner
        assert_eq!(offsets[6], 4); // +x+y
        assert_eq!(offsets[10], 10); // +x+z
        assert_eq!(offsets[18], 13); // +x+y+z
        assert_eq!(offsets[25], -13);
    }

    #[test]
    fn test_neighborhood_masks_unique_powers_of_two() {
        let masks = neighborhood_masks();
        for i in 0..26 {
            assert_eq!(masks[i], 1u32 << i);
            for j in (i + 1)..26 {
                assert_eq!(masks[i] & masks[j], 0);
            }
        }
    }

    #[test]
    fn test_neighborhood_weights_isotropic() {
        let w = neighborhood_weights(Anisotropy::new(1.0, 1.0, 1.0));

        for i in 0..6 {
            assert!((w[i] - 1.0).abs() < 1e-6, "face {i}: {} != 1.0", w[i]);
        }
        let sqrt2 = 2.0_f32.sqrt();
        for i in 6..18 {
            assert!((w[i] - sqrt2).abs() < 1e-6, "edge {i}: {} != √2", w[i]);
        }
        let sqrt3 = 3.0_f32.sqrt();
        for i in 18..26 {
            assert!((w[i] - sqrt3).abs() < 1e-6, "corner {i}: {} != √3", w[i]);
        }
    }

    #[test]
    fn test_neighborhood_weights_anisotropic_em() {
        // Typical EM volume: 4 nm in xy, 40 nm in z
        let w = neighborhood_weights(Anisotropy::new(4.0, 4.0, 40.0));

        assert!((w[0] - 4.0).abs() < 1e-4); // +x face
        assert!((w[2] - 4.0).abs() < 1e-4); // +y face
        assert!((w[4] - 40.0).abs() < 1e-4); // +z face

        let xy = (16.0_f32 + 16.0).sqrt();
        assert!((w[6] - xy).abs() < 1e-4); // xy edge

        let xz = (16.0_f32 + 1600.0).sqrt();
        assert!((w[10] - xz).abs() < 1e-4); // xz edge

        let yz = (16.0_f32 + 1600.0).sqrt();
        assert!((w[14] - yz).abs() < 1e-4); // yz edge

        let cnr = (16.0_f32 + 16.0 + 1600.0).sqrt();
        assert!((w[18] - cnr).abs() < 1e-4);
    }

    #[test]
    fn test_connectivity_count_and_from_int() {
        assert_eq!(Connectivity::Six.count(), 6);
        assert_eq!(Connectivity::Eighteen.count(), 18);
        assert_eq!(Connectivity::TwentySix.count(), 26);

        assert_eq!(Connectivity::from_int(4), Some(Connectivity::Six));
        assert_eq!(Connectivity::from_int(6), Some(Connectivity::Six));
        assert_eq!(Connectivity::from_int(8), Some(Connectivity::Eighteen));
        assert_eq!(Connectivity::from_int(18), Some(Connectivity::Eighteen));
        assert_eq!(Connectivity::from_int(26), Some(Connectivity::TwentySix));
        assert_eq!(Connectivity::from_int(99), None);
    }
}