lox 0.1.1

Fast polygon mesh library with different data structures and traits to abstract over those.
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
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202

//! Bounding volumes and how to calculate them.

use std::fmt;

use lina::Point3;

use crate::util::{PrimitiveFloat, Pos3Like};


/// A bounding sphere defined by a center and a radius.
#[derive(Debug, Clone, Copy)]
pub struct BoundingSphere<P: Pos3Like> {
    pub center: P,
    pub radius: P::Scalar,
}

/// Calculates a bounding sphere with the algorithm by Jack Ritter.
///
/// The returned bounding sphere is usually not minimal. This function iterates
/// over all points three times. The given points must not be empty or else
/// this function panics.
///
/// Reference: Ritter, Jack. "An efficient bounding sphere."
/// Graphics gems 1 (1990): 301-303.
pub fn ritter_sphere<I, ScalarT>(positions: I) -> BoundingSphere<I::Item>
where
    I: Iterator + Clone,
    I::Item: Pos3Like<Scalar = ScalarT>,
    ScalarT: PrimitiveFloat,
{
    assert!(positions.clone().next().is_some(), "point set must not be empty");

    // Finds the point furthest away from `origin`.
    let furthest_away_from = |origin| {
        let mut max = ScalarT::zero();
        let mut out = origin;

        for p in positions.clone().map(|p| p.to_point3()) {
            let dist = p.distance2_from(origin);
            if dist > max {
                max = dist;
                out = p;
            }
        }

        out
    };

    // First, take a random point and find another point with maximum distance
    // to it. Then find a point with maximum distance to *that*.
    let x = positions.clone().next().unwrap().to_point3();
    let y = furthest_away_from(x);
    let z = furthest_away_from(y);

    // The center is the midpoint between y and z.
    let center = Point3::centroid([y, z]).unwrap();
    let mut radius = y.distance_from(center);

    // If any point lies outside the sphere, we grow the sphere to include it.
    // The center stays the same.
    for p in positions {
        let dist = p.to_point3().distance_from(center);
        if dist > radius {
            radius = dist;
        }
    }

    BoundingSphere { center: center.convert(), radius }
}

/// A fast algorithm to obtain a bounding sphere of a set of points.
///
/// The returned bounding sphere is usually not minimal. This algorithm is very
/// simple: first, the axis aligned bounding box is calculated. The center of
/// that bounding box is the center of the resulting bounding sphere. The
/// radius of the sphere is simply the maximum distance from the center to a
/// point. As such, this function iterates over all points twice (e.g. the
/// Richter algorithm iterates over all points three times).
///
/// The given points must not be empty or else this function panics.
pub fn fast_sphere<I, ScalarT>(positions: I) -> BoundingSphere<I::Item>
where
    I: Iterator +  Clone,
    I::Item: Pos3Like<Scalar = ScalarT>,
    ScalarT: PrimitiveFloat,
{
    assert!(positions.clone().next().is_some(), "point set must not be empty");

    // Calculate bounding box, take it's center, find vertex with maximum
    // distance to that center, use its distance as radius.
    let bounding_box = BoundingBox::around(positions.clone());
    let center = bounding_box.center();
    let radius = positions
        .map(|p| p.to_point3().distance_from(center))
        .max_by(|a, b| a.partial_cmp(b).unwrap())
        .unwrap();

    BoundingSphere { center: center.convert(), radius }
}


/// An axis aligned bounding box.
pub struct BoundingBox<F: PrimitiveFloat> {
    x_range: [F; 2],
    y_range: [F; 2],
    z_range: [F; 2],
}

impl<F: PrimitiveFloat> BoundingBox<F> {
    /// Creates an invalid bounding box: all lower bounds are ∞, all upper
    /// bounds are -∞. Once you added a single point, the bounding box will be
    /// valid.
    pub fn new() -> Self {
        Self {
            x_range: [F::infinity(), F::neg_infinity()],
            y_range: [F::infinity(), F::neg_infinity()],
            z_range: [F::infinity(), F::neg_infinity()],
        }
    }

    /// Creates a bounding box around all points of the given iterator. If the
    /// iterator is empty, an invalid bounding box is returned (see
    /// [`BoundingBox::new`]).
    pub fn around<I>(iter: I) -> Self
    where
        I: IntoIterator,
        I::Item: Pos3Like<Scalar = F>
    {
        let mut out = Self::new();
        for pos in iter {
            out.add_point(pos);
        }
        out
    }

    /// Returns the `[lower, upper]` limits for the x coordinate.
    pub fn x(&self) -> [F; 2] {
        self.x_range
    }

    /// Returns the `[lower, upper]` limits for the y coordinate.
    pub fn y(&self) -> [F; 2] {
        self.y_range
    }

    /// Returns the `[lower, upper]` limits for the z coordinate.
    pub fn z(&self) -> [F; 2] {
        self.z_range
    }

    /// Returns the center of this bounding box.
    pub fn center(&self) -> Point3<F> {
        Point3::new(
            (self.x_range[1] + self.x_range[0]) / F::from_f32(2.0),
            (self.y_range[1] + self.y_range[0]) / F::from_f32(2.0),
            (self.z_range[1] + self.z_range[0]) / F::from_f32(2.0),
        )
    }

    /// Adds a point to the bounding box, enlarging it if the point lies
    /// outside of the box.
    pub fn add_point<P: Pos3Like<Scalar = F>>(&mut self, p: P) {
        fn min<F: PartialOrd>(state: &mut F, new: F) {
            if new < *state {
                *state = new;
            }
        }
        fn max<F: PartialOrd>(state: &mut F, new: F) {
            if new > *state {
                *state = new;
            }
        }


        min(&mut self.x_range[0], p.x());
        max(&mut self.x_range[1], p.x());
        min(&mut self.y_range[0], p.y());
        max(&mut self.y_range[1], p.y());
        min(&mut self.z_range[0], p.z());
        max(&mut self.z_range[1], p.z());
    }

    /// Returns `true` if all bounds are finite.
    pub fn is_valid(&self) -> bool {
        self.x_range[0].is_finite()
            && self.x_range[1].is_finite()
            && self.y_range[0].is_finite()
            && self.y_range[1].is_finite()
            && self.z_range[0].is_finite()
            && self.z_range[1].is_finite()
    }
}

impl<F: PrimitiveFloat> fmt::Debug for BoundingBox<F> {
    fn fmt(&self, f: &mut fmt::Formatter) -> fmt::Result {
        f.debug_struct("BoundingBox")
            .field("x", &(self.x_range[0]..self.x_range[1]))
            .field("y", &(self.y_range[0]..self.y_range[1]))
            .field("z", &(self.z_range[0]..self.z_range[1]))
            .finish()
    }
}