use std::collections::{BTreeMap, HashMap};
use std::path::{Path, PathBuf};
use crate::qsm::buttress_detect as bd;
use crate::filters::voxel_downsample_indices;
use crate::util::json::py_float_repr;
use crate::leaves::model::qsm_from_rows;
use crate::qsm::buttress::{self as bm, Buttress};
use crate::qsm::metrics::tree_metrics;
use crate::qsm::wood::{wood_mask, WoodParams};
use crate::qsm::{build_qsm, build_qsm_weighted, QsmParams};
use crate::qsm::ops::{self as ops, Row};
use crate::{Error, Point, Result};
fn median(v: &[f64]) -> f64 {
if v.iter().any(|x| x.is_nan()) {
return f64::NAN;
}
crate::util::numeric::median(v)
}
fn py_max(a: f64, b: f64) -> f64 {
if b > a {
b
} else {
a
}
}
pub fn buttress_ground_z(points: &[Point], heights: &[f64], cx: f64, cy: f64) -> f64 {
let base: Vec<f64> = points.iter().zip(heights).map(|(p, h)| p[2] - h).collect();
let near: Vec<f64> = points.iter().zip(&base).filter(|(p, _)| (p[0] - cx).hypot(p[1] - cy) <= 1.0).map(|(_, &b)| b).collect();
median(if near.is_empty() { &base } else { &near })
}
pub fn buttress_raster_check(p: &bm::ButtressParams) -> Result<()> {
let nx = (2.0 * p.max_radius / py_max(p.resolution, 1e-6)).trunc() as i128 + 1;
let nz = (p.max_height / py_max(p.slice, 1e-6)).trunc() as i128 + 1;
let cells = (nx * nx * nz).max(0) as u128;
crate::util::limits::check_cells(
cells,
2,
&format!("a {nx} x {nx} x {nz} buttress raster at {} m", py_float_repr(p.resolution)),
"a coarser resolution, a smaller max_radius, or a lower max_height",
)
}
pub fn buttress_mesh(points: &[Point], heights: &[f64], cx: f64, cy: f64, ground_z: Option<f64>, p: &bm::ButtressParams) -> Result<Buttress> {
if heights.len() != points.len() {
return Err(Error::invalid("heights must have one value per point"));
}
let ground_z = ground_z.unwrap_or_else(|| buttress_ground_z(points, heights, cx, cy));
buttress_raster_check(p)?;
if p.resolution <= 0.0 || p.slice <= 0.0 || p.max_height <= 0.0 {
return Err(Error::invalid("resolution, slice and max_height must be positive"));
}
Ok(bm::buttress_mesh(points, heights, cx, cy, ground_z, p))
}
pub fn wood_points(points: &[Point]) -> Vec<Point> {
let thin: Vec<Point> = voxel_downsample_indices(points, 0.02).into_iter().map(|i| points[i]).collect();
let mask = wood_mask(&thin, &WoodParams::default());
thin.into_iter().zip(mask).filter(|(_, m)| *m).map(|(p, _)| p).collect()
}
#[derive(Debug, Clone)]
pub struct PlotParams {
pub voxel_size: f64,
pub wood: bool,
pub buttress: bool,
pub min_points: f64,
pub qsm: QsmParams,
}
impl Default for PlotParams {
fn default() -> Self {
PlotParams { voxel_size: 0.01, wood: true, buttress: false, min_points: 2000.0, qsm: QsmParams::default() }
}
}
#[derive(Debug, Clone, Copy)]
pub enum PointWood<'a> {
Labels(&'a [bool]),
Weights(&'a [f64]),
}
#[derive(Debug, Clone, Default)]
pub struct PlotModels {
pub models: Vec<(i64, Vec<Row>)>,
pub buttresses: Vec<(i64, Buttress)>,
pub skipped: Vec<(i64, String)>,
pub points: Vec<(i64, usize)>,
pub heights: Vec<(i64, f64)>,
}
pub fn build_plot(points: &[Point], labels: &[i64], heights: Option<&[f64]>, stems: &[(i64, [f64; 2], f64)], p: &PlotParams) -> Result<PlotModels> {
build_plot_with(points, labels, heights, stems, p, None)
}
pub fn build_plot_with(points: &[Point], labels: &[i64], heights: Option<&[f64]>, stems: &[(i64, [f64; 2], f64)], p: &PlotParams, wood: Option<PointWood>) -> Result<PlotModels> {
match wood {
Some(PointWood::Labels(w)) if w.len() != points.len() => return Err(Error::invalid("wood labels must have one value per point")),
Some(PointWood::Weights(w)) => crate::qsm::weighted::check_weights(w, points.len())?,
_ => {}
}
if labels.len() != points.len() {
return Err(Error::invalid("labels must have one value per point"));
}
if heights.is_some_and(|h| h.len() != points.len()) {
return Err(Error::invalid("heights must have one value per point"));
}
let mut members: BTreeMap<i64, Vec<usize>> = BTreeMap::new();
for (i, &t) in labels.iter().enumerate() {
if t >= 0 {
members.entry(t).or_default().push(i);
}
}
let centres: HashMap<i64, [f64; 2]> = stems.iter().map(|&(t, c, _)| (t, c)).collect();
let dbh: HashMap<i64, f64> = stems.iter().map(|&(t, _, d)| (t, d)).collect();
let mut out = PlotModels::default();
let task = crate::util::progress::start("fitting QSMs", members.len() as u64);
for (&tid, idx) in &members {
task.inc(1);
let n = idx.len();
if (n as f64) < p.min_points {
out.skipped.push((tid, format!("{n} points")));
continue;
}
let tree: Vec<Point> = idx.iter().map(|&i| points[i]).collect();
let tree_h: Option<Vec<f64>> = heights.map(|h| idx.iter().map(|&i| h[i]).collect());
out.points.push((tid, n));
if let Some(h) = &tree_h {
let top = if h.iter().any(|x| x.is_nan()) { f64::NAN } else { h.iter().copied().fold(f64::NEG_INFINITY, f64::max) };
out.heights.push((tid, top));
}
let keep: Vec<usize> = if p.voxel_size > 0.0 { voxel_downsample_indices(&tree, p.voxel_size) } else { (0..n).collect() };
let thin: Vec<Point> = keep.iter().map(|&i| tree[i]).collect();
let base = match centres.get(&tid) {
Some(&c) => c,
None => {
let low: Vec<Point> = match &tree_h {
Some(h) => keep.iter().filter(|&&i| h[i] > 0.5 && h[i] < 1.5).map(|&i| tree[i]).collect(),
None => thin.clone(),
};
let from = if low.len() > 20 { &low } else { &thin };
let xs: Vec<f64> = from.iter().map(|q| q[0]).collect();
let ys: Vec<f64> = from.iter().map(|q| q[1]).collect();
[median(&xs), median(&ys)]
}
};
let mut qp = p.qsm.clone();
if qp.base_radius <= 0.0 {
if let Some(&d) = dbh.get(&tid) {
if d.is_finite() && d > 0.0 {
qp.base_radius = d / 2.0;
}
}
}
let fitted = match wood {
None if p.wood => build_qsm(&wood_points(&thin), Some(base), &qp),
None => build_qsm(&thin, Some(base), &qp),
Some(PointWood::Labels(w)) => {
let wood: Vec<Point> = idx.iter().filter(|&&i| w[i]).map(|&i| points[i]).collect();
let input: Vec<Point> = if p.voxel_size > 0.0 { voxel_downsample_indices(&wood, p.voxel_size).into_iter().map(|i| wood[i]).collect() } else { wood };
build_qsm(&input, Some(base), &qp)
}
Some(PointWood::Weights(w)) => {
let tw: Vec<f64> = keep.iter().map(|&k| w[idx[k]]).collect();
build_qsm_weighted(&thin, Some(base), &qp, &tw)
}
};
match fitted {
Ok(q) => out.models.push((tid, q.to_rows())),
Err(e) => {
out.skipped.push((tid, e.to_string()));
continue;
}
}
if let (true, Some(h)) = (p.buttress, &tree_h) {
let found = bd::detect_buttress(&tree, h, Some(base), &bd::ButtressParams::default())?;
if found.buttressed {
let bp = bm::ButtressParams { top: Some(found.top), ..Default::default() };
let b = buttress_mesh(&tree, h, found.centre[0], found.centre[1], None, &bp)?;
if !b.faces.is_empty() {
out.buttresses.push((tid, b));
}
}
}
}
Ok(out)
}
pub fn median_measured_length<'a>(models: impl IntoIterator<Item = &'a [Row]>) -> Option<f64> {
let shares: Vec<f64> = models.into_iter().map(|rows| tree_metrics(&qsm_from_rows(rows), 1.0, 0.5).measured_length_fraction).collect();
if shares.is_empty() {
None
} else {
Some(median(&shares))
}
}
#[derive(Debug, Clone, Copy)]
pub struct ButtressView<'a> {
pub vertices: &'a [Point],
pub faces: &'a [[u32; 3]],
pub volume: f64,
pub top: f64,
pub top_z: f64,
}
#[derive(Debug, Clone, Copy)]
pub struct PlotEntry<'a> {
pub tree_id: i64,
pub rows: &'a [Row],
pub points: Option<i64>,
pub height: Option<f64>,
pub buttress: Option<ButtressView<'a>>,
}
pub fn tree_volume(e: &PlotEntry) -> f64 {
match &e.buttress {
Some(b) => b.volume + ops::volume_above(e.rows, b.top_z),
None => ops::totals(e.rows).total_volume,
}
}
pub fn total_volume(entries: &[PlotEntry]) -> f64 {
entries.iter().fold(0.0, |s, e| s + tree_volume(e))
}
pub fn py_round(x: f64, digits: usize) -> f64 {
if !x.is_finite() {
return x;
}
format!("{x:.digits$}").parse().unwrap_or(x)
}
#[derive(Debug, Clone, PartialEq)]
pub struct TableRow {
pub tree_id: i64,
pub points: Option<i64>,
pub volume_m3: f64,
pub dbh_m: f64,
pub height_m: f64,
pub n_cylinders: usize,
pub measured_volume: f64,
pub measured_length: f64,
pub buttress_m3: Option<f64>,
pub buttress_top_m: Option<f64>,
}
pub const TABLE_COLUMNS: [&str; 10] = ["tree_id", "points", "volume_m3", "dbh_m", "height_m", "n_cylinders", "measured_volume", "measured_length", "buttress_m3", "buttress_top_m"];
pub fn table(entries: &[PlotEntry]) -> Vec<TableRow> {
let mut sorted: Vec<&PlotEntry> = entries.iter().collect();
sorted.sort_by_key(|e| e.tree_id);
sorted
.into_iter()
.map(|e| {
let q = qsm_from_rows(e.rows);
let fit = tree_metrics(&q, 1.0, 0.5);
TableRow {
tree_id: e.tree_id,
points: e.points,
volume_m3: py_round(tree_volume(e), 5),
dbh_m: py_round(q.dbh(), 4),
height_m: py_round(e.height.unwrap_or(f64::NAN), 2),
n_cylinders: e.rows.len(),
measured_volume: py_round(fit.measured_volume_fraction, 3),
measured_length: py_round(fit.measured_length_fraction, 3),
buttress_m3: e.buttress.map(|b| py_round(b.volume, 5)),
buttress_top_m: e.buttress.map(|b| py_round(b.top, 2)),
}
})
.collect()
}
pub fn table_csv(rows: &[TableRow]) -> String {
if rows.is_empty() {
return "tree_id\r\n".into();
}
let mut s = TABLE_COLUMNS.join(",") + "\r\n";
let opt = |v: Option<f64>| v.map(py_float_repr).unwrap_or_default();
for r in rows {
let cells = [
r.tree_id.to_string(),
r.points.map(|p| p.to_string()).unwrap_or_default(),
py_float_repr(r.volume_m3),
py_float_repr(r.dbh_m),
py_float_repr(r.height_m),
r.n_cylinders.to_string(),
py_float_repr(r.measured_volume),
py_float_repr(r.measured_length),
opt(r.buttress_m3),
opt(r.buttress_top_m),
];
s += &cells.join(",");
s += "\r\n";
}
s
}
pub fn write_table_csv(path: impl AsRef<Path>, entries: &[PlotEntry]) -> Result<()> {
std::fs::write(path, table_csv(&table(entries)))?;
Ok(())
}
pub fn write_meshes(directory: impl AsRef<Path>, entries: &[PlotEntry], fmt: &str, sides: usize, contiguous: bool, prefix: &str) -> Result<Vec<PathBuf>> {
if fmt != "ply" && fmt != "obj" {
return Err(Error::invalid("fmt must be 'ply' or 'obj'"));
}
let d = directory.as_ref();
std::fs::create_dir_all(d)?;
let mut sorted: Vec<&PlotEntry> = entries.iter().collect();
sorted.sort_by_key(|e| e.tree_id);
let task = crate::util::progress::start("writing meshes", sorted.len() as u64);
let mut out = Vec::with_capacity(sorted.len());
for e in sorted {
let path = d.join(format!("{prefix}{}.{fmt}", e.tree_id));
match &e.buttress {
Some(b) => {
let t = ops::fuse(b.vertices, b.faces, b.volume, b.top_z, e.rows, sides, contiguous, 0.1)?;
if fmt == "ply" {
ops::write_tree_mesh_ply(&path, &t.vertices, &t.faces, &t.part, None)?;
} else {
ops::write_tree_mesh_obj(&path, &t.vertices, &t.faces, &t.part)?;
}
}
None if fmt == "ply" => ops::write_model_ply(&path, e.rows, sides, None, contiguous)?,
None => ops::write_model_obj(&path, e.rows, sides, contiguous)?,
}
out.push(path);
task.inc(1);
}
Ok(out)
}
pub fn write_cylinders(directory: impl AsRef<Path>, entries: &[PlotEntry], prefix: &str) -> Result<()> {
let d = directory.as_ref();
std::fs::create_dir_all(d)?;
for e in entries {
qsm_from_rows(e.rows).write_csv(d.join(format!("{prefix}{}.csv", e.tree_id)))?;
}
Ok(())
}
#[cfg(test)]
mod tests {
use super::*;
use crate::util::nprandom::Generator;
fn stem(rng: &mut Generator, cx: f64, r: f64, h: f64, n: usize) -> Vec<Point> {
(0..n)
.map(|_| {
let t = rng.random() * std::f64::consts::TAU;
let z = rng.random() * h;
[cx + r * t.cos(), r * t.sin(), z]
})
.collect()
}
#[test]
fn rounding_is_pythons() {
assert_eq!(py_round(2.675, 2), 2.67);
assert_eq!(py_round(0.125, 2), 0.12);
assert!(py_round(-1e-7, 5).is_sign_negative());
assert!(py_round(f64::NAN, 2).is_nan());
assert_eq!(py_round(3e-5, 5), 3e-5);
}
#[test]
fn a_plot_models_its_trees_and_skips_the_small() {
let mut rng = Generator::new(1);
let mut pts = stem(&mut rng, 0.0, 0.15, 4.0, 8000);
let mut labels = vec![1i64; pts.len()];
pts.extend(stem(&mut rng, 5.0, 0.1, 3.0, 6000));
labels.resize(pts.len(), 3);
pts.extend(stem(&mut rng, 9.0, 0.05, 0.4, 100));
labels.resize(pts.len(), 2);
pts.push([0.0, 9.0, 0.0]);
labels.push(-1);
let h: Vec<f64> = pts.iter().map(|p| p[2]).collect();
let p = PlotParams { wood: false, min_points: 1000.0, ..Default::default() };
let plot = build_plot(&pts, &labels, Some(&h), &[(3, [5.0, 0.0], f64::NAN)], &p).unwrap();
assert_eq!(plot.models.iter().map(|m| m.0).collect::<Vec<_>>(), vec![1, 3]);
assert_eq!(plot.skipped, vec![(2, "100 points".to_string())]);
assert_eq!(plot.points, vec![(1, 8000), (3, 6000)]);
assert!(plot.heights[0].1 <= 4.0 && plot.heights[0].1 > 3.9);
let entries: Vec<PlotEntry> = plot.models.iter().map(|(t, r)| PlotEntry { tree_id: *t, rows: r, points: None, height: None, buttress: None }).collect();
let rows = table(&entries);
assert_eq!(rows.len(), 2);
assert!(rows[0].volume_m3 > rows[1].volume_m3);
let csv = table_csv(&rows);
assert!(csv.starts_with("tree_id,points,volume_m3") && csv.contains("\r\n1,,"));
assert_eq!(table_csv(&[]), "tree_id\r\n");
assert!((total_volume(&entries) - entries.iter().map(tree_volume).sum::<f64>()).abs() < 1e-12);
assert!(median_measured_length(plot.models.iter().map(|m| m.1.as_slice())).unwrap() > 0.5);
assert!(build_plot(&pts, &labels[1..], None, &[], &p).is_err());
let dir = std::env::temp_dir().join(format!("sylva-plot-{}", std::process::id()));
assert!(write_meshes(&dir, &entries, "stl", 8, true, "t").is_err());
let files = write_meshes(&dir, &entries, "obj", 8, true, "t").unwrap();
assert_eq!(files.iter().map(|f| f.file_name().unwrap().to_string_lossy().into_owned()).collect::<Vec<_>>(), vec!["t1.obj", "t3.obj"]);
write_cylinders(&dir, &entries, "c").unwrap();
assert!(dir.join("c3.csv").exists());
let _ = std::fs::remove_dir_all(&dir);
}
#[test]
fn wood_can_be_given_per_point() {
let mut rng = Generator::new(4);
let mut pts = stem(&mut rng, 0.0, 0.15, 4.0, 8000);
let n_wood = pts.len();
pts.extend(stem(&mut rng, 0.0, 0.4, 4.0, 3000));
let labels = vec![1i64; pts.len()];
let p = PlotParams { wood: false, min_points: 1000.0, ..Default::default() };
let bare = build_plot(&pts[..n_wood], &labels[..n_wood], None, &[], &p).unwrap();
let wood: Vec<bool> = (0..pts.len()).map(|i| i < n_wood).collect();
let pw = PlotParams { wood: true, ..p.clone() };
let by_label = build_plot_with(&pts, &labels, None, &[], &pw, Some(PointWood::Labels(&wood))).unwrap();
assert!(!by_label.models.is_empty());
let v = |m: &PlotModels| ops::totals(&m.models[0].1).total_volume;
let truth = std::f64::consts::PI * 0.15 * 0.15 * 4.0;
assert!((v(&by_label) - truth).abs() < 0.2 * truth, "{} {truth}", v(&by_label));
assert!((v(&by_label) - v(&bare)).abs() < 0.1 * truth);
let ones = vec![1.0; pts.len()];
let all = build_plot(&pts, &labels, None, &[], &p).unwrap();
let weighted = build_plot_with(&pts, &labels, None, &[], &pw, Some(PointWood::Weights(&ones))).unwrap();
assert_eq!(weighted.models, all.models);
assert!(build_plot_with(&pts, &labels, None, &[], &p, Some(PointWood::Labels(&wood[1..]))).is_err());
assert!(build_plot_with(&pts, &labels, None, &[], &p, Some(PointWood::Weights(&ones[1..]))).is_err());
let mut bad = ones.clone();
bad[5] = f64::NAN;
assert!(build_plot_with(&pts, &labels, None, &[], &p, Some(PointWood::Weights(&bad))).is_err());
}
}