geop_core_editor/view/
tree.rs

1//! [`FaceTree`]: a bounding volume hierarchy over the triangles of a view's
2//! faces, so that a pick tests the triangles near the ray, not every one —
3//! a few boxes per level, and the triangles of the boxes the ray passes
4//! through, for a part of any size. A component's view is shared by every
5//! part placed from it, and so is its tree: built once, when it is first
6//! picked in.
7//!
8//! A box is passed by only where the ray definitely misses it, its
9//! crossing of each slab enclosed by interval arithmetic: every triangle
10//! the ray could meet is tested, as testing every one would.
11
12use std::cell::Cell;
13
14use geop_core_math::{primitives::Ray, scalars::Scalar, vector::Vector3};
15
16use super::ViewFace;
17
18/// How many triangles a leaf of the tree holds at most.
19const LEAF: usize = 4;
20
21thread_local! {
22    static TRIANGLES_TESTED: Cell<usize> = const { Cell::new(0) };
23}
24
25/// How many triangles this thread has tested a pick's ray against ever:
26/// what a hover must keep few, however many triangles the parts under the
27/// pointer have — so a test bounds it by counting these, not by timing it.
28pub fn triangles_tested() -> usize {
29    TRIANGLES_TESTED.get()
30}
31
32/// A box of the tree, and what is in it: two boxes, or a run of triangles.
33struct Node {
34    lo: [f64; 3],
35    hi: [f64; 3],
36    content: Content,
37}
38
39enum Content {
40    Boxes(usize, usize),
41    /// The triangles `start..end` of [`FaceTree::triangles`].
42    Triangles(usize, usize),
43}
44
45/// The tree of the triangles of some faces: see the [module](self).
46pub(crate) struct FaceTree {
47    nodes: Vec<Node>,
48    /// Each triangle, by its face's index and its own in the face's mesh,
49    /// in the order the leaves hold them.
50    triangles: Vec<(usize, usize)>,
51    /// The meshes it was built of, to tell it from the tree of other faces.
52    meshes: Vec<*const super::FaceMesh>,
53}
54
55impl std::fmt::Debug for FaceTree {
56    fn fmt(&self, f: &mut std::fmt::Formatter<'_>) -> std::fmt::Result {
57        write!(f, "FaceTree({} triangles)", self.triangles.len())
58    }
59}
60
61/// A triangle while the tree is built: where it is, its box, and its
62/// middle.
63struct Entry {
64    at: (usize, usize),
65    lo: [f64; 3],
66    hi: [f64; 3],
67    middle: [f64; 3],
68}
69
70impl FaceTree {
71    /// The tree of the triangles of `faces`.
72    pub(crate) fn of(faces: &[ViewFace]) -> Self {
73        let mut entries = Vec::new();
74        for (f, face) in faces.iter().enumerate() {
75            for (t, corners) in face.mesh.triangles.iter().enumerate() {
76                let mut lo = [f64::INFINITY; 3];
77                let mut hi = [f64::NEG_INFINITY; 3];
78                for p in corners {
79                    widen(&mut lo, &mut hi, p.to_array().map(|x| (x.lo, x.hi)));
80                }
81                let middle = std::array::from_fn(|k| {
82                    let (a, b) = (lo.get(k).copied(), hi.get(k).copied());
83                    0.5 * (a.unwrap_or_default() + b.unwrap_or_default())
84                });
85                entries.push(Entry {
86                    at: (f, t),
87                    lo,
88                    hi,
89                    middle,
90                });
91            }
92        }
93        let mut tree = Self {
94            nodes: Vec::new(),
95            triangles: Vec::with_capacity(entries.len()),
96            meshes: faces.iter().map(|f| std::rc::Rc::as_ptr(&f.mesh)).collect(),
97        };
98        if !entries.is_empty() {
99            tree.build(&mut entries);
100        }
101        tree
102    }
103
104    /// Whether it is the tree of `faces`.
105    pub(crate) fn is_of(&self, faces: &[ViewFace]) -> bool {
106        self.meshes.len() == faces.len()
107            && (self.meshes.iter().zip(faces)).all(|(m, f)| *m == std::rc::Rc::as_ptr(&f.mesh))
108    }
109
110    /// Adds the box of `entries`, and those in it, and gives its index.
111    fn build(&mut self, entries: &mut [Entry]) -> usize {
112        let mut lo = [f64::INFINITY; 3];
113        let mut hi = [f64::NEG_INFINITY; 3];
114        for e in entries.iter() {
115            widen(
116                &mut lo,
117                &mut hi,
118                std::array::from_fn(|k| {
119                    (
120                        e.lo.get(k).copied().unwrap_or_default(),
121                        e.hi.get(k).copied().unwrap_or_default(),
122                    )
123                }),
124            );
125        }
126        let at = self.nodes.len();
127        self.nodes.push(Node {
128            lo,
129            hi,
130            content: Content::Triangles(0, 0),
131        });
132        let content = if entries.len() <= LEAF {
133            let start = self.triangles.len();
134            self.triangles.extend(entries.iter().map(|e| e.at));
135            Content::Triangles(start, self.triangles.len())
136        } else {
137            // Halved at the middle triangle along the axis the middles
138            // spread furthest along.
139            let spread = |k: usize| {
140                let (mut a, mut b) = (f64::INFINITY, f64::NEG_INFINITY);
141                for x in entries.iter().filter_map(|e| e.middle.get(k)) {
142                    a = a.min(*x);
143                    b = b.max(*x);
144                }
145                b - a
146            };
147            let axis = (0..3)
148                .max_by(|&a, &b| spread(a).total_cmp(&spread(b)))
149                .unwrap_or_default();
150            let half = entries.len() / 2;
151            let along = |e: &Entry| e.middle.get(axis).copied().unwrap_or_default();
152            entries.select_nth_unstable_by(half, |a, b| along(a).total_cmp(&along(b)));
153            let (left, right) = entries.split_at_mut(half);
154            Content::Boxes(self.build(left), self.build(right))
155        };
156        if let Some(node) = self.nodes.get_mut(at) {
157            node.content = content;
158        }
159        at
160    }
161
162    /// Calls `test` with each triangle, by its face's index and its own,
163    /// in a box `ray` could pass through — and counts them.
164    pub(crate) fn near(&self, ray: &Ray, mut test: impl FnMut(usize, usize)) {
165        let mut stack = vec![0];
166        while let Some(at) = stack.pop() {
167            let Some(node) = self.nodes.get(at) else {
168                continue;
169            };
170            if !could_pass(ray, &node.lo, &node.hi) {
171                continue;
172            }
173            match node.content {
174                Content::Boxes(a, b) => stack.extend([a, b]),
175                Content::Triangles(start, end) => {
176                    for &(face, triangle) in self.triangles.get(start..end).unwrap_or_default() {
177                        TRIANGLES_TESTED.set(TRIANGLES_TESTED.get() + 1);
178                        test(face, triangle);
179                    }
180                }
181            }
182        }
183    }
184}
185
186/// Whether `ray` could pass through the box from `lo` to `hi`, ahead of
187/// its origin: false only where it definitely does not.
188fn could_pass(ray: &Ray, lo: &[f64; 3], hi: &[f64; 3]) -> bool {
189    let (origin, dir): (&Vector3, &Vector3) = (ray.origin(), ray.dir());
190    // The ray is in the box from the latest it could enter a slab to the
191    // earliest it could leave one, and never behind its origin.
192    let mut enter = 0.0f64;
193    let mut leave = f64::INFINITY;
194    let slabs = (lo.iter().zip(hi)).zip(origin.to_array().into_iter().zip(dir.to_array()));
195    for ((&a, &b), (o, d)) in slabs {
196        let (a, b) = (Scalar::from_f64(a), Scalar::from_f64(b));
197        if d.could_be_equal(Scalar::ZERO) {
198            // Running along the slab: it misses it only from outside.
199            if o.definitely_less(a) || o.definitely_greater(b) {
200                return false;
201            }
202            continue;
203        }
204        let (Ok(ta), Ok(tb)) = (a.sub(o).div(d), b.sub(o).div(d)) else {
205            continue;
206        };
207        enter = enter.max(ta.lo.min(tb.lo));
208        leave = leave.min(ta.hi.max(tb.hi));
209    }
210    enter <= leave
211}
212
213/// Widens the box from `lo` to `hi` to take in `bounds`, an interval each.
214fn widen(lo: &mut [f64; 3], hi: &mut [f64; 3], bounds: [(f64, f64); 3]) {
215    for ((l, h), (a, b)) in lo.iter_mut().zip(hi.iter_mut()).zip(bounds) {
216        *l = l.min(a);
217        *h = h.max(b);
218    }
219}
geop_core_editor/view/tree.rs

geop_core_editor/view/
tree.rs
