curvo 0.1.88

NURBS modeling library
Documentation 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133

use std::borrow::Cow;

use itertools::Itertools;
use nalgebra::{
    allocator::Allocator, Const, DefaultAllocator, DimName, DimNameDiff, DimNameSub, U1,
};

use crate::{
    misc::{FloatingPoint, Plane},
    split::{Split, SplitSurfaceOption},
    surface::{NurbsSurface, UVDirection},
};

use super::{BoundingBox, BoundingBoxTree};

/// A struct representing a bounding box tree with surface in D space.
#[derive(Clone)]
pub struct SurfaceBoundingBoxTree<'a, T: FloatingPoint, D: DimName>
where
    DefaultAllocator: Allocator<D>,
{
    surface: Cow<'a, NurbsSurface<T, D>>,
    tolerance: (T, T),
    direction: UVDirection,
}

impl<'a, T: FloatingPoint, D: DimName> SurfaceBoundingBoxTree<'a, T, D>
where
    D: DimNameSub<U1>,
    DefaultAllocator: Allocator<D>,
    DefaultAllocator: Allocator<DimNameDiff<D, U1>>,
{
    /// Create a new bounding box tree from a surface.
    pub fn new(
        surface: &'a NurbsSurface<T, D>,
        direction: UVDirection,
        tolerance: Option<(T, T)>,
    ) -> Self {
        let tol = tolerance.unwrap_or_else(|| {
            let (u, v) = surface.knots_domain_interval();
            let div = T::from_usize(64).unwrap();
            (u / div, v / div)
        });
        Self {
            surface: Cow::Borrowed(surface),
            tolerance: tol,
            direction,
        }
    }

    pub fn surface(&self) -> &NurbsSurface<T, D> {
        self.surface.as_ref()
    }

    pub fn surface_owned(self) -> NurbsSurface<T, D> {
        self.surface.into_owned()
    }
}

impl<T: FloatingPoint, D: DimName> BoundingBoxTree<T, D> for SurfaceBoundingBoxTree<'_, T, D>
where
    D: DimNameSub<U1>,
    DefaultAllocator: Allocator<D>,
    DefaultAllocator: Allocator<DimNameDiff<D, U1>>,
{
    /// Check if the surface is dividable or not.
    fn is_dividable(&self) -> bool {
        let interval = self.surface.knots_domain_interval();
        let (utol, vtol) = self.tolerance;
        interval.0 > utol || interval.1 > vtol
    }

    /// Try to divide the surface into two parts.
    fn try_divide(&self) -> anyhow::Result<(Self, Self)> {
        let div = T::from_f64(0.5).unwrap();
        let t = self.surface().knots_domain_at(self.direction);
        let mid = (t.0 + t.1) * div;
        let (l, r) = self
            .surface()
            .try_split(SplitSurfaceOption::new(mid, self.direction))?;
        let next = self.direction.opposite();
        Ok((
            Self {
                surface: Cow::Owned(l),
                tolerance: self.tolerance,
                direction: next,
            },
            Self {
                surface: Cow::Owned(r),
                tolerance: self.tolerance,
                direction: next,
            },
        ))
    }

    /// Get the bounding box of the surface.
    fn bounding_box(&self) -> BoundingBox<T, DimNameDiff<D, U1>> {
        self.surface.as_ref().into()
    }
}

impl<'a, T: FloatingPoint> SurfaceBoundingBoxTree<'a, T, Const<4>> {
    /// Recursively traverse all leaf nodes from a bounding box tree that intersect the plane
    pub fn traverse_leaf_nodes_with_plane(&self, plane: &Plane<T>) -> Vec<Self> {
        let bbox = self.bounding_box();
        let corners = bbox.corners();

        // Check if bbox straddles the plane
        let distances = corners
            .iter()
            .map(|p| plane.signed_distance(p))
            .collect_vec();
        let has_positive = distances.iter().any(|&d| d > T::zero());
        let has_negative = distances.iter().any(|&d| d < T::zero());

        if !has_positive || !has_negative {
            // Bbox is entirely on one side of the plane
            return vec![];
        }

        if self.is_dividable() {
            if let Ok((left, right)) = self.try_divide() {
                let mut nodes = left.traverse_leaf_nodes_with_plane(plane);
                nodes.extend(right.traverse_leaf_nodes_with_plane(plane));
                nodes
            } else {
                vec![self.clone()]
            }
        } else {
            vec![self.clone()]
        }
    }
}