brep_cam/index/
mod.rs

1//! Broad-phase triangle queries.
2//!
3//! Drop-cutter and push-cutter ask the same question many times: which
4//! triangles can a cutter at this XY (or this fiber) touch? A
5//! [`TriangleIndex`] answers with a candidate list that never misses a true
6//! overlap (false positives are allowed; the exact cutter/triangle test is the
7//! caller's). Results are ascending triangle ids, so every implementation
8//! returns the same list for the same query and output is deterministic.
9
10use crate::mesh::{MeshSnapshot, TriangleSource};
11use crate::model::Bounds3;
12use serde::{Deserialize, Serialize};
13
14mod tree;
15
16pub use tree::{AnyIndex, TreeIndex, TreeOptions};
17
18/// Which axes a query compares. A projected mode ignores the dropped axis.
19#[derive(Clone, Copy, Debug, Default, PartialEq, Eq, Hash, Serialize, Deserialize)]
20#[serde(rename_all = "lowercase")]
21pub enum ProjectionMode {
22    /// Compare X and Y only (the drop-cutter's view down the tool axis).
23    #[default]
24    Xy,
25    /// Compare X and Z only (push-cutter fibers along Y).
26    Xz,
27    /// Compare Y and Z only (push-cutter fibers along X).
28    Yz,
29    /// Compare all three axes.
30    Xyz,
31}
32
33impl ProjectionMode {
34    /// Closed-interval overlap of two boxes on the compared axes.
35    pub fn overlaps(self, a: &Bounds3, b: &Bounds3) -> bool {
36        let x = a.min.x <= b.max.x && b.min.x <= a.max.x;
37        let y = a.min.y <= b.max.y && b.min.y <= a.max.y;
38        let z = a.min.z <= b.max.z && b.min.z <= a.max.z;
39        match self {
40            ProjectionMode::Xy => x && y,
41            ProjectionMode::Xz => x && z,
42            ProjectionMode::Yz => y && z,
43            ProjectionMode::Xyz => x && y && z,
44        }
45    }
46}
47
48/// Size and shape of an index, for reports and tests.
49#[derive(Clone, Debug, Default, PartialEq, Eq, Serialize, Deserialize)]
50#[serde(rename_all = "camelCase")]
51pub struct IndexStats {
52    pub triangle_count: usize,
53    #[serde(default, skip_serializing_if = "Option::is_none")]
54    pub node_count: Option<usize>,
55    #[serde(default, skip_serializing_if = "Option::is_none")]
56    pub leaf_count: Option<usize>,
57    #[serde(default, skip_serializing_if = "Option::is_none")]
58    pub max_depth: Option<usize>,
59    /// Implementation name: `brute-force`, `median-split-tree`, ...
60    pub implementation: String,
61}
62
63/// Broad-phase candidate queries over one mesh snapshot.
64/// `Sync`: an index is shared read-only by parallel fiber and span workers
65/// (feature `parallel`); every implementor is plain data.
66pub trait TriangleIndex: Sync {
67    /// Append every triangle id whose bounds overlap `query` on the axes `mode`
68    /// compares. Touching counts. Ids are appended in ascending order and
69    /// `out` is NOT cleared first.
70    fn query_aabb(&self, query: &Bounds3, mode: ProjectionMode, out: &mut Vec<u32>);
71
72    fn stats(&self) -> IndexStats;
73
74    /// Convenience: a fresh ascending candidate list.
75    fn query(&self, query: &Bounds3, mode: ProjectionMode) -> Vec<u32> {
76        let mut out = Vec::new();
77        self.query_aabb(query, mode, &mut out);
78        out
79    }
80
81    /// Candidates for a cutter of `radius` at `(x, y)`: the XY disc's box,
82    /// unbounded in Z (the drop-cutter's query).
83    fn query_cutter_xy(&self, x: f64, y: f64, radius: f64, out: &mut Vec<u32>) {
84        let query = Bounds3::new(
85            crate::model::Point3::new(x - radius, y - radius, f64::NEG_INFINITY),
86            crate::model::Point3::new(x + radius, y + radius, f64::INFINITY),
87        );
88        self.query_aabb(&query, ProjectionMode::Xy, out);
89    }
90}
91
92/// Scans every triangle. The reference every other index is checked against,
93/// and the right choice for small meshes.
94#[derive(Clone, Debug, Default, PartialEq)]
95pub struct BruteForceIndex {
96    bounds: Vec<Bounds3>,
97}
98
99impl BruteForceIndex {
100    pub fn build(mesh: &dyn TriangleSource) -> Self {
101        let bounds = (0..mesh.triangle_count()).map(|i| mesh.triangle(i as u32).bounds).collect();
102        Self { bounds }
103    }
104
105    pub fn from_snapshot(mesh: &MeshSnapshot) -> Self {
106        Self::build(mesh)
107    }
108}
109
110impl TriangleIndex for BruteForceIndex {
111    fn query_aabb(&self, query: &Bounds3, mode: ProjectionMode, out: &mut Vec<u32>) {
112        for (i, b) in self.bounds.iter().enumerate() {
113            if mode.overlaps(b, query) {
114                out.push(i as u32);
115            }
116        }
117    }
118
119    fn stats(&self) -> IndexStats {
120        IndexStats {
121            triangle_count: self.bounds.len(),
122            node_count: None,
123            leaf_count: None,
124            max_depth: None,
125            implementation: "brute-force".to_string(),
126        }
127    }
128}
129
brep_cam/index/mod.rs

brep_cam/index/
mod.rs
