mod blocked;
mod blocks;
pub mod grid;
mod iad;
pub(crate) mod metrics;
pub mod quality;
mod refine;
mod traverse;
mod wood;
mod write;
use std::collections::BTreeMap;
use crate::error::{Error, Result};
use crate::qsm::Cylinder;
use crate::transform::{add, scale};
use crate::{Point, Raster, Shots};
pub use blocked::BlockedGrid;
pub use blocks::{voxelize_blocks, BlockOptions, BlockStats, Pulses};
pub use iad::TreeIad;
pub use metrics::{classify_de_wit, compute_g, compute_g_from_histogram, laser_spec, solve_bailey_pad, Lad};
pub use write::WriteOptions;
#[derive(Debug, Clone, Copy, PartialEq, Eq)]
pub enum WeightMethod {
Equal,
Full,
First,
Relative,
Strongest,
}
impl WeightMethod {
pub fn parse(s: &str) -> Result<Self> {
Ok(match s {
"equal" => WeightMethod::Equal,
"full" => WeightMethod::Full,
"first" => WeightMethod::First,
"relative" => WeightMethod::Relative,
"strongest" => WeightMethod::Strongest,
other => return Err(Error::invalid(format!("unknown weighting {other:?} (equal|full|first|relative|strongest)"))),
})
}
}
#[derive(Debug, Clone, Copy, PartialEq, Eq)]
pub enum Attenuation {
Fpl,
Ppl,
Transmittance,
Bailey,
}
impl Attenuation {
pub fn parse(s: &str) -> Result<Self> {
Ok(match s.trim().to_ascii_lowercase().as_str() {
"fpl" => Attenuation::Fpl,
"ppl" => Attenuation::Ppl,
"transmittance" => Attenuation::Transmittance,
"bailey" => Attenuation::Bailey,
other => return Err(Error::invalid(format!("unknown attenuation method {other:?} (fpl|ppl|transmittance|bailey)"))),
})
}
pub fn name(&self) -> &'static str {
match self {
Attenuation::Fpl => "fpl",
Attenuation::Ppl => "ppl",
Attenuation::Transmittance => "transmittance",
Attenuation::Bailey => "bailey",
}
}
}
#[derive(Debug, Clone, Copy, PartialEq)]
pub struct BeamSpec {
pub diameter: f64,
pub divergence: f64,
}
#[derive(Debug, Clone, PartialEq)]
pub struct VoxelParams {
pub voxel_size: f64,
pub bounds: Option<(Point, Point)>,
pub weighting: WeightMethod,
pub occlusion: bool,
pub flat_top: bool,
pub neighbour_prior_min_rays: u32,
pub beam: Option<BeamSpec>,
pub subvoxel_split: usize,
pub subvoxel_min_beams: u8,
pub average_leaf_area: f64,
pub lad: Lad,
pub attenuation: Vec<Attenuation>,
pub inclination: bool,
pub n_iad_bins: usize,
pub knn_normal: usize,
pub triangle_lmax: f64,
pub unbounded_range: f64,
}
impl Default for VoxelParams {
fn default() -> Self {
VoxelParams {
voxel_size: 0.1,
bounds: None,
weighting: WeightMethod::Equal,
occlusion: false,
flat_top: false,
neighbour_prior_min_rays: 0,
beam: None,
subvoxel_split: 0,
subvoxel_min_beams: 10,
average_leaf_area: 0.005,
lad: Lad::Spherical,
attenuation: vec![Attenuation::Fpl],
inclination: false,
n_iad_bins: 18,
knn_normal: 10,
triangle_lmax: 0.05,
unbounded_range: f64::INFINITY,
}
}
}
pub mod foliage {
pub const EXCLUDED: u8 = 0;
pub const PLANT: u8 = 1;
pub const LEAF: u8 = 2;
pub const WOOD: u8 = 3;
}
#[derive(Debug, Clone, Copy)]
pub struct VoxelInputs<'a> {
pub shots: &'a Shots,
pub ground: Option<&'a [bool]>,
pub foliage: Option<&'a [u8]>,
pub intensity: Option<&'a [f64]>,
pub tree_id: Option<&'a [i32]>,
pub dtm: Option<&'a Raster>,
}
impl<'a> VoxelInputs<'a> {
pub fn new(shots: &'a Shots) -> Self {
VoxelInputs { shots, ground: None, foliage: None, intensity: None, tree_id: None, dtm: None }
}
}
#[repr(usize)]
#[derive(Debug, Clone, Copy, PartialEq, Eq)]
pub enum F {
NumBeamsWeighted,
PathLength,
PathLengthSq,
FreePathLength,
FreePathLengthPlant,
FreePathLengthLeaf,
FreePathLengthWood,
EffectiveFreePathLength,
PathLengthOccluded,
SumOfAngles,
SumSinAzimuth,
SumCosAzimuth,
SumOfLaserDistances,
SumHitDelta,
SumMissDelta,
PathLengthUnbound,
BsEntering,
BsIntercepted,
BsPotential,
BsFreePath,
BsEffectiveFreePath,
BsEffFreePathHits,
PplMissWl,
HitsWeighted,
}
impl F {
pub const COUNT: usize = 24;
pub const ALL: [F; F::COUNT] = [
F::NumBeamsWeighted, F::PathLength, F::PathLengthSq, F::FreePathLength, F::FreePathLengthPlant,
F::FreePathLengthLeaf, F::FreePathLengthWood, F::EffectiveFreePathLength, F::PathLengthOccluded,
F::SumOfAngles, F::SumSinAzimuth, F::SumCosAzimuth, F::SumOfLaserDistances, F::SumHitDelta,
F::SumMissDelta, F::PathLengthUnbound, F::BsEntering, F::BsIntercepted, F::BsPotential,
F::BsFreePath, F::BsEffectiveFreePath, F::BsEffFreePathHits, F::PplMissWl, F::HitsWeighted,
];
pub fn name(&self) -> &'static str {
match self {
F::NumBeamsWeighted => "num_beams_weighted",
F::PathLength => "path_length",
F::PathLengthSq => "path_length_sq",
F::FreePathLength => "free_path_length",
F::FreePathLengthPlant => "free_path_length_plant",
F::FreePathLengthLeaf => "free_path_length_leaf",
F::FreePathLengthWood => "free_path_length_wood",
F::EffectiveFreePathLength => "effective_free_path_length",
F::PathLengthOccluded => "path_length_occluded",
F::SumOfAngles => "sum_of_angles",
F::SumSinAzimuth => "sum_sin_azimuth",
F::SumCosAzimuth => "sum_cos_azimuth",
F::SumOfLaserDistances => "sum_of_laser_distances",
F::SumHitDelta => "sum_hit_delta",
F::SumMissDelta => "sum_miss_delta",
F::PathLengthUnbound => "path_length_unbound",
F::BsEntering => "bs_entering",
F::BsIntercepted => "bs_intercepted",
F::BsPotential => "bs_potential",
F::BsFreePath => "bs_free_path",
F::BsEffectiveFreePath => "bs_effective_free_path",
F::BsEffFreePathHits => "bs_eff_free_path_hits",
F::PplMissWl => "ppl_miss_wl",
F::HitsWeighted => "num_hits_weighted",
}
}
fn is_beam(&self) -> bool {
matches!(self, F::BsEntering | F::BsIntercepted | F::BsPotential | F::BsFreePath | F::BsEffectiveFreePath | F::BsEffFreePathHits)
}
}
#[repr(usize)]
#[derive(Debug, Clone, Copy, PartialEq, Eq)]
pub enum I {
NumHits,
NumBeams,
NumRaysOccluded,
NumUnboundRays,
NumMissRays,
NumHitLeaf,
NumHitWood,
NumHitPlant,
}
impl I {
pub const COUNT: usize = 8;
pub const ALL: [I; I::COUNT] = [
I::NumHits, I::NumBeams, I::NumRaysOccluded, I::NumUnboundRays, I::NumMissRays, I::NumHitLeaf,
I::NumHitWood, I::NumHitPlant,
];
pub fn name(&self) -> &'static str {
match self {
I::NumHits => "num_hits",
I::NumBeams => "num_beams",
I::NumRaysOccluded => "num_beams_occluded",
I::NumUnboundRays => "num_unbound_rays",
I::NumMissRays => "num_miss_rays",
I::NumHitLeaf => "num_hit_leaf",
I::NumHitWood => "num_hit_wood",
I::NumHitPlant => "num_hit_plant",
}
}
}
#[repr(u8)]
#[derive(Debug, Clone, Copy, PartialEq, Eq)]
pub enum VoxelState {
Unobserved = 0,
Occluded = 1,
Empty = 2,
Filled = 3,
}
#[derive(Debug, Clone)]
pub struct RayVoxels {
pub origin: Point,
pub voxel_size: f64,
pub shape: [usize; 3],
pub params: VoxelParams,
pub has_leaf: bool,
pub has_wood: bool,
pub f: Vec<Vec<f32>>,
pub i: Vec<Vec<i32>>,
pub ppl_lambda: Option<Vec<f32>>,
pub subvoxel_counts: Option<Vec<u8>>,
pub ground_height: Option<Vec<f64>>,
pub wood_volume: Option<Vec<f32>>,
pub predominant_tree: Option<Vec<i32>>,
pub tree_iad: BTreeMap<i32, TreeIad>,
}
impl RayVoxels {
pub fn n_voxels(&self) -> usize {
self.shape[0] * self.shape[1] * self.shape[2]
}
#[inline]
pub fn get_f(&self, field: F, idx: usize) -> f32 {
self.f[field as usize].get(idx).copied().unwrap_or(0.0)
}
#[inline]
pub fn get_i(&self, field: I, idx: usize) -> i32 {
self.i[field as usize][idx]
}
#[inline]
pub fn unravel(&self, idx: usize) -> [usize; 3] {
let (nx, ny) = (self.shape[0], self.shape[1]);
[idx % nx, (idx / nx) % ny, idx / (nx * ny)]
}
pub fn center(&self, idx: usize) -> Point {
let ijk = self.unravel(idx);
[
self.origin[0] + (ijk[0] as f64 + 0.5) * self.voxel_size,
self.origin[1] + (ijk[1] as f64 + 0.5) * self.voxel_size,
self.origin[2] + (ijk[2] as f64 + 0.5) * self.voxel_size,
]
}
pub fn state(&self, idx: usize) -> VoxelState {
if self.get_i(I::NumHits, idx) > 0 {
VoxelState::Filled
} else if self.get_f(F::NumBeamsWeighted, idx) > 0.0 {
VoxelState::Empty
} else if self.get_i(I::NumRaysOccluded, idx) > 0 {
VoxelState::Occluded
} else {
VoxelState::Unobserved
}
}
pub fn add_wood_volume(&mut self, cylinders: &[Cylinder]) {
let n = self.n_voxels();
let out = self.wood_volume.get_or_insert_with(|| vec![0.0; n]);
wood::rasterise(cylinders, &self.origin, self.voxel_size, &self.shape, out);
}
}
pub fn ground_mask_from_dtm(shots: &Shots, dtm: &Raster, max_above: f64) -> Vec<bool> {
shots.echo_xyz().iter().map(|p| p[2] - dtm.sample(p[0], p[1]) <= max_above).collect()
}
fn check_len<T>(name: &str, v: Option<&[T]>, n: usize) -> Result<()> {
match v {
Some(a) if a.len() != n => Err(Error::invalid(format!("{name} has {} values for {n} echoes", a.len()))),
_ => Ok(()),
}
}
pub(crate) fn check_ranges(shots: &Shots) -> Result<()> {
match shots.echo_range.iter().position(|r| !r.is_finite()) {
Some(e) => Err(Error::invalid(format!(
"echo {e} has a range of {} m; echo ranges must be finite (drop these echoes, or their pulses, before voxelising)",
shots.echo_range[e]
))),
None => Ok(()),
}
}
pub struct Voxelizer {
engine: traverse::Engine,
peaks: Option<Vec<f64>>,
ground_height: Option<Vec<f64>>,
echoes: Option<iad::EchoPoints>,
has_leaf: bool,
has_wood: bool,
}
impl Voxelizer {
pub fn new(params: &VoxelParams, bounds: (Point, Point), dtm: Option<&Raster>) -> Result<Self> {
if !(params.voxel_size > 0.0) {
return Err(Error::invalid("voxel_size must be positive"));
}
if params.subvoxel_split > 4 {
return Err(Error::invalid("subvoxel_split must be at most 4"));
}
if params.attenuation.is_empty() {
return Err(Error::invalid("at least one attenuation method is needed"));
}
let lo = bounds.0;
let shape = grid_shape(params, bounds)?;
let cells = shape.iter().map(|&n| n as u128).product::<u128>();
let per_cell = std::mem::size_of::<traverse::Cell>() as u64
+ (params.subvoxel_split.max(1).pow(3) as u64);
crate::util::limits::check_cells(
cells,
per_cell,
&format!("a {} x {} x {} voxel grid at {} m", shape[0], shape[1], shape[2], params.voxel_size),
"a larger voxel, a smaller area, or splitting the plot into tiles",
)?;
let ground_height = dtm.map(|dtm| column_ground(dtm, lo, params.voxel_size, shape));
let wants_iad = params.inclination || params.attenuation.contains(&Attenuation::Bailey);
Ok(Voxelizer {
engine: traverse::Engine::new(params, traverse::Geom::new(lo, params.voxel_size, shape)),
peaks: None,
ground_height,
echoes: wants_iad.then(iad::EchoPoints::default),
has_leaf: false,
has_wood: false,
})
}
pub fn add_peaks(&mut self, shots: &Shots) {
let n = self.engine.geom.shape[0] * self.engine.geom.shape[1];
let peaks = self.peaks.get_or_insert_with(|| vec![f64::MIN; n]);
refine::update_peaks(peaks, &shots.echo_xyz(), &self.engine.geom);
}
pub fn add(&mut self, inputs: &VoxelInputs) -> Result<()> {
let ne = inputs.shots.n_echoes();
check_len("ground", inputs.ground, ne)?;
check_len("foliage", inputs.foliage, ne)?;
check_len("intensity", inputs.intensity, ne)?;
check_len("tree_id", inputs.tree_id, ne)?;
check_ranges(inputs.shots)?;
if matches!(self.engine.params.weighting, WeightMethod::Relative | WeightMethod::Strongest) && inputs.intensity.is_none() {
return Err(Error::invalid("relative / strongest weighting needs echo intensities"));
}
self.has_leaf |= inputs.foliage.is_some_and(|f| f.contains(&foliage::LEAF));
self.has_wood |= inputs.foliage.is_some_and(|f| f.contains(&foliage::WOOD));
let peaks = if self.engine.params.flat_top { self.peaks.as_deref() } else { None };
self.engine.add(inputs, peaks, self.ground_height.as_deref());
if let Some(e) = &mut self.echoes {
e.collect(inputs, &self.engine.geom);
}
Ok(())
}
pub fn finish(self) -> Result<RayVoxels> {
let bailey = self.engine.params.attenuation.contains(&Attenuation::Bailey);
if bailey && !(self.has_leaf && self.has_wood) {
return Err(Error::invalid("the bailey method needs both leaf and wood echoes"));
}
let prior = self.engine.params.neighbour_prior_min_rays;
let mut vox = self.engine.finish();
vox.has_leaf = self.has_leaf;
vox.has_wood = self.has_wood;
vox.ground_height = self.ground_height;
if prior > 0 {
refine::apply_neighbour_priors(&mut vox, prior as f32);
}
if let Some(e) = self.echoes {
iad::build(&mut vox, e);
}
Ok(vox)
}
}
pub(crate) fn grid_shape(params: &VoxelParams, bounds: (Point, Point)) -> Result<[usize; 3]> {
let (lo, hi) = bounds;
let mut shape = [0usize; 3];
for k in 0..3 {
if !(hi[k] > lo[k]) {
return Err(Error::invalid("grid bounds are empty"));
}
shape[k] = ((hi[k] - lo[k]) / params.voxel_size).ceil().max(1.0) as usize;
}
Ok(shape)
}
pub(crate) fn column_ground(dtm: &Raster, lo: Point, size: f64, shape: [usize; 3]) -> Vec<f64> {
let mut g = Vec::with_capacity(shape[0] * shape[1]);
for j in 0..shape[1] {
for i in 0..shape[0] {
g.push(dtm.sample(lo[0] + (i as f64 + 0.5) * size, lo[1] + (j as f64 + 0.5) * size));
}
}
g
}
pub(crate) fn pad_bounds(b: (Point, Point)) -> (Point, Point) {
let (mut lo, mut hi) = b;
for k in 0..3 {
let eps = 1e-4f64.max(hi[k].abs() * 1e-9);
lo[k] -= eps;
hi[k] += eps;
}
(lo, hi)
}
pub fn voxelize(inputs: &VoxelInputs, params: &VoxelParams) -> Result<RayVoxels> {
let bounds = match params.bounds {
Some(b) => b,
None => {
let xyz = inputs.shots.echo_xyz();
if xyz.is_empty() {
return Err(Error::invalid("no echoes to fit the grid to; pass bounds"));
}
pad_bounds((crate::util::spatial::min_corner(&xyz), crate::util::spatial::max_corner(&xyz)))
}
};
let mut v = Voxelizer::new(params, bounds, inputs.dtm)?;
if params.flat_top {
v.add_peaks(inputs.shots);
}
v.add(inputs)?;
v.finish()
}
#[derive(Debug, Clone, PartialEq)]
pub struct EchoLabels {
pub class_attr: String,
pub ground_class: Option<i64>,
pub ground_distance: f64,
pub leaf_classes: Vec<i64>,
pub wood_classes: Vec<i64>,
pub tree_attr: String,
pub intensity_attr: String,
}
impl Default for EchoLabels {
fn default() -> Self {
EchoLabels { class_attr: "classification".into(), ground_class: None, ground_distance: 0.2, leaf_classes: vec![], wood_classes: vec![], tree_attr: "tree_id".into(), intensity_attr: "intensity".into() }
}
}
#[derive(Debug, Clone, Default)]
pub struct EchoAnnotations {
pub ground: Option<Vec<bool>>,
pub foliage: Option<Vec<u8>>,
pub intensity: Option<Vec<f64>>,
pub tree_id: Option<Vec<i32>>,
}
impl EchoLabels {
pub fn annotate(&self, shots: &Shots, dtm: Option<&Raster>) -> Result<EchoAnnotations> {
let class = shots.echo_attrs.get(&self.class_attr).map(|a| a.to_f64());
let need_class = || class.as_ref().ok_or_else(|| Error::invalid(format!("the shots have no {:?} echo attribute", self.class_attr)));
let ground = match (self.ground_class, dtm) {
(Some(c), _) => Some(need_class()?.iter().map(|&v| v == c as f64).collect()),
(None, Some(d)) if self.ground_distance > 0.0 => Some(ground_mask_from_dtm(shots, d, self.ground_distance)),
_ => None,
};
let foliage = if self.leaf_classes.is_empty() && self.wood_classes.is_empty() {
None
} else {
let code = |v: f64| {
if self.leaf_classes.iter().any(|&c| c as f64 == v) {
foliage::LEAF
} else if self.wood_classes.iter().any(|&c| c as f64 == v) {
foliage::WOOD
} else if v < 3.0 {
foliage::EXCLUDED
} else {
foliage::PLANT
}
};
Some(need_class()?.iter().map(|&v| code(v)).collect())
};
Ok(EchoAnnotations {
ground,
foliage,
intensity: shots.echo_attrs.get(&self.intensity_attr).map(|a| a.to_f64()),
tree_id: shots.echo_attrs.get(&self.tree_attr).map(|a| a.to_f64().iter().map(|&v| v as i32).collect()),
})
}
}
impl EchoAnnotations {
pub fn inputs<'a>(&'a self, shots: &'a Shots, dtm: Option<&'a Raster>) -> VoxelInputs<'a> {
VoxelInputs { shots, ground: self.ground.as_deref(), foliage: self.foliage.as_deref(), intensity: self.intensity.as_deref(), tree_id: self.tree_id.as_deref(), dtm }
}
}
pub fn voxelize_file(file: &crate::io::shots::ShotsFile, params: &VoxelParams, labels: &EchoLabels, dtm: Option<&Raster>) -> Result<RayVoxels> {
let mut v = Voxelizer::new(params, params.bounds.unwrap_or_else(|| pad_bounds(file.bounds)), dtm)?;
if params.flat_top {
for g in 0..file.n_groups() {
v.add_peaks(&file.read_group(g)?);
}
}
for_each_file_batch(file, |shots| {
let notes = labels.annotate(&shots, dtm)?;
v.add(¬es.inputs(&shots, dtm))
})?;
v.finish()
}
pub(crate) fn for_each_file_batch(file: &crate::io::shots::ShotsFile, mut f: impl FnMut(Shots) -> Result<()>) -> Result<()> {
const BATCH: usize = 4;
let n = file.n_groups();
let stride = (1..=n).rev().find(|s| *s <= n.div_ceil(BATCH).max(1) && gcd(*s, n) == 1).unwrap_or(1);
let next = std::sync::atomic::AtomicUsize::new(0);
std::thread::scope(|scope| {
let (tx, rx) = std::sync::mpsc::sync_channel(BATCH);
for _ in 0..n.clamp(1, BATCH) {
let (tx, next, handle) = (tx.clone(), &next, file.reopen()?);
scope.spawn(move || loop {
let g = next.fetch_add(1, std::sync::atomic::Ordering::Relaxed);
if g >= n || tx.send((g, handle.read_group(g * stride % n))).is_err() {
break;
}
});
}
drop(tx);
let mut early = BTreeMap::new();
let mut batch = Shots::default();
let mut due = 0;
for (g, part) in rx {
early.insert(g, part);
while let Some(part) = early.remove(&due) {
crate::io::shots::append(&mut batch, part?)?;
due += 1;
if due % BATCH == 0 || due == n {
f(std::mem::take(&mut batch))?;
}
}
}
Ok::<(), Error>(())
})
}
fn gcd(a: usize, b: usize) -> usize {
if b == 0 { a } else { gcd(b, a % b) }
}
pub(crate) fn unbounded_end(origin: &Point, dir: &Point, geom: &traverse::Geom, range: f64) -> Point {
let r = if range.is_finite() {
range
} else {
let mut to_centre = 0.0;
let mut diag = 0.0;
for k in 0..3 {
let ext = geom.shape[k] as f64 * geom.size;
to_centre += (geom.origin[k] + 0.5 * ext - origin[k]).powi(2);
diag += ext * ext;
}
to_centre.sqrt() + diag.sqrt()
};
add(origin, &scale(dir, r))
}