Skip to main content

three_rs/extras/
curve_path.rs

1//! Port of `three.js/src/extras/core/CurvePath.js`.
2
3use std::cell::{Cell, RefCell};
4use std::fmt;
5use std::rc::Rc;
6
7use super::curve::{compute_lengths, Curve, CurveVector};
8use super::line_curve::{LineCurve, LineVector};
9
10/// A shared, immutable sub-curve of a [`CurvePath`].
11///
12/// three.js holds its curves by reference too, and `CurvePath.clone()`
13/// deep-copies them; since a curve here is immutable once it is in a path,
14/// sharing it between a path and its clone is the same thing.
15pub type CurveRef<P> = Rc<dyn Curve<Point = P>>;
16
17/// `CurvePath`: a sequence of connected curves, itself a [`Curve`].
18///
19/// # The two caches
20///
21/// `CurvePath.getPoint( t )` is built on `getLength()`, which sums every
22/// sub-curve's length, and the inherited `getPointAt( u )` maps `u` through
23/// `getLengths()`, which calls `getPoint` 201 times. Uncached that is
24/// quadratic, so unlike the leaf curves (see `super::curve`) this keeps
25/// both of three.js' caches, with three.js' own invalidation rules:
26///
27/// * `cacheLengths` (the per-curve running sums, `getCurveLengths()`) is
28///   reused while it has one entry per curve, so adding a curve refreshes it;
29/// * `cacheArcLengths` (`Curve.getLengths()`) is reused while it has
30///   `divisions + 1` entries and `needsUpdate` is unset. Adding a curve does
31///   **not** refresh it — in three.js either — so `get_point_at` after a later
32///   `line_to` maps through the old path's arc lengths until
33///   [`update_arc_lengths`](CurvePath::update_arc_lengths) is called. That is
34///   reproduced on purpose: it is what three.js computes.
35pub struct CurvePath<P: CurveVector> {
36    /// The curves, in order.
37    pub curves: Vec<CurveRef<P>>,
38    /// Whether the path should automatically be closed by a line curve.
39    pub auto_close: bool,
40    /// `Curve.arcLengthDivisions`, default 200.
41    pub arc_length_divisions: usize,
42    /// `this.needsUpdate`.
43    pub needs_update: Cell<bool>,
44    cache_lengths: RefCell<Option<Vec<f64>>>,
45    cache_arc_lengths: RefCell<Option<Vec<f64>>>,
46}
47
48impl<P: CurveVector> Default for CurvePath<P> {
49    fn default() -> Self {
50        Self {
51            curves: Vec::new(),
52            auto_close: false,
53            arc_length_divisions: 200,
54            needs_update: Cell::new(false),
55            cache_lengths: RefCell::new(None),
56            cache_arc_lengths: RefCell::new(None),
57        }
58    }
59}
60
61impl<P: CurveVector> Clone for CurvePath<P> {
62    /// `CurvePath.clone()`: the curves, `autoClose` and `arcLengthDivisions`;
63    /// the caches start empty, as a fresh three.js instance's do.
64    fn clone(&self) -> Self {
65        Self {
66            curves: self.curves.clone(),
67            auto_close: self.auto_close,
68            arc_length_divisions: self.arc_length_divisions,
69            ..Self::default()
70        }
71    }
72}
73
74impl<P: CurveVector> fmt::Debug for CurvePath<P> {
75    fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
76        f.debug_struct("CurvePath")
77            .field(
78                "curves",
79                &self
80                    .curves
81                    .iter()
82                    .map(|c| c.type_name())
83                    .collect::<Vec<_>>(),
84            )
85            .field("auto_close", &self.auto_close)
86            .finish()
87    }
88}
89
90impl<P: CurveVector> CurvePath<P> {
91    /// `new CurvePath()`.
92    pub fn new() -> Self {
93        Self::default()
94    }
95
96    /// `CurvePath.add( curve )`.
97    pub fn add(&mut self, curve: impl Curve<Point = P> + 'static) {
98        self.curves.push(Rc::new(curve));
99    }
100
101    /// `CurvePath.updateArcLengths()`.
102    pub fn update_arc_lengths(&self) {
103        self.needs_update.set(true);
104        *self.cache_lengths.borrow_mut() = None;
105        self.get_curve_lengths();
106    }
107
108    /// `CurvePath.getCurveLengths()`: the running sum of the sub-curves'
109    /// lengths, cached while the curve count is unchanged.
110    pub fn get_curve_lengths(&self) -> Vec<f64> {
111        // Compute lengths and cache them
112        // We cannot overwrite getLengths() because UtoT mapping uses it.
113        // We use cache values if curves and cache array are same length
114
115        if let Some(cache) = self.cache_lengths.borrow().as_ref() {
116            if cache.len() == self.curves.len() {
117                return cache.clone();
118            }
119        }
120
121        // Get length of sub-curve
122        // Push sums into cached array
123
124        let mut lengths = Vec::new();
125        let mut sums = 0.0;
126
127        for curve in &self.curves {
128            sums += curve.get_length();
129            lengths.push(sums);
130        }
131
132        *self.cache_lengths.borrow_mut() = Some(lengths.clone());
133
134        lengths
135    }
136}
137
138impl<P: LineVector> CurvePath<P> {
139    /// `CurvePath.closePath()`: adds a line curve back to the start if the
140    /// path does not already end there.
141    pub fn close_path(&mut self) -> &mut Self {
142        // Add a line curve if start and end of lines are not connected
143        let start_point = self.curves[0].get_point(0.0);
144        let end_point = self.curves[self.curves.len() - 1].get_point(1.0);
145
146        if !start_point.equals(&end_point) {
147            self.curves
148                .push(Rc::new(LineCurve::new(end_point, start_point)));
149        }
150
151        self
152    }
153}
154
155impl<P: CurveVector> Curve for CurvePath<P> {
156    type Point = P;
157
158    fn type_name(&self) -> &'static str {
159        "CurvePath"
160    }
161
162    fn arc_length_divisions(&self) -> usize {
163        self.arc_length_divisions
164    }
165
166    /// `CurvePath.getPoint( t )`.
167    ///
168    /// # Panics
169    ///
170    /// Where three.js returns `null`: when `t * getLength()` lies past the last
171    /// curve (`t > 1`, or an empty path).
172    fn get_point(&self, t: f64) -> P {
173        // To get accurate point with reference to
174        // entire path distance at time t,
175        // following has to be done:
176
177        // 1. Length of each sub path have to be known
178        // 2. Locate and identify type of curve
179        // 3. Get t for the curve
180        // 4. Return curve.getPointAt(t')
181
182        let d = t * self.get_length();
183        let curve_lengths = self.get_curve_lengths();
184
185        // To think about boundaries points.
186
187        for (i, &curve_length) in curve_lengths.iter().enumerate() {
188            if curve_length >= d {
189                let diff = curve_length - d;
190                let curve = &self.curves[i];
191
192                let segment_length = curve.get_length();
193                let u = if segment_length == 0.0 {
194                    0.0
195                } else {
196                    1.0 - diff / segment_length
197                };
198
199                return curve.get_point_at(u);
200            }
201        }
202
203        panic!("three-rs: CurvePath::get_point({t}) lies past the end of the path (three.js returns null)");
204
205        // loop where sum != 0, sum > d , sum+1 <d
206    }
207
208    /// `CurvePath.getLength()`.
209    ///
210    /// We cannot use the default THREE.Curve getPoint() with getLength()
211    /// because in THREE.Curve, getLength() depends on getPoint() but in
212    /// THREE.CurvePath getPoint() depends on getLength
213    fn get_length(&self) -> f64 {
214        let lens = self.get_curve_lengths();
215        // `lens[ lens.length - 1 ]` is `undefined` (NaN downstream) for an
216        // empty path.
217        lens.last().copied().unwrap_or(f64::NAN)
218    }
219
220    /// `Curve.getLengths( divisions )` with its `cacheArcLengths` cache; see
221    /// the type's doc.
222    fn get_lengths(&self, divisions: usize) -> Vec<f64> {
223        if let Some(cache) = self.cache_arc_lengths.borrow().as_ref() {
224            if cache.len() == divisions + 1 && !self.needs_update.get() {
225                return cache.clone();
226            }
227        }
228
229        self.needs_update.set(false);
230
231        let cache = compute_lengths(self, divisions);
232
233        *self.cache_arc_lengths.borrow_mut() = Some(cache.clone());
234
235        cache
236    }
237
238    /// `CurvePath.getSpacedPoints( divisions )`: `getPoint`, not `getPointAt`,
239    /// at even `t`, plus the first point again when `autoClose` is set.
240    fn get_spaced_points(&self, divisions: usize) -> Vec<P> {
241        let mut points = Vec::new();
242
243        for i in 0..=divisions {
244            points.push(self.get_point(i as f64 / divisions as f64));
245        }
246
247        if self.auto_close {
248            points.push(points[0]);
249        }
250
251        points
252    }
253
254    /// `CurvePath.getPoints( divisions )`: each curve sampled at its own
255    /// resolution ([`Curve::curve_path_resolution`]), consecutive duplicates
256    /// dropped.
257    fn get_points(&self, divisions: usize) -> Vec<P> {
258        let mut points: Vec<P> = Vec::new();
259        let mut last: Option<P> = None;
260
261        for curve in &self.curves {
262            let resolution = curve.curve_path_resolution(divisions);
263
264            let pts = curve.get_points(resolution);
265
266            for point in pts {
267                if last.is_some_and(|last| last.equals(&point)) {
268                    continue; // ensures no consecutive points are duplicates
269                }
270
271                points.push(point);
272                last = Some(point);
273            }
274        }
275
276        if self.auto_close && points.len() > 1 && !points[points.len() - 1].equals(&points[0]) {
277            points.push(points[0]);
278        }
279
280        points
281    }
282}
283
284/// Implements [`Curve`] for a type that wraps a [`CurvePath`] (three.js'
285/// `Path` and `Shape` subclasses), forwarding every method `CurvePath`
286/// overrides and changing only `type`.
287macro_rules! delegate_curve_path {
288    ($ty:ty, $field:ident, $point:ty, $name:literal) => {
289        impl $crate::extras::Curve for $ty {
290            type Point = $point;
291
292            fn type_name(&self) -> &'static str {
293                $name
294            }
295
296            fn arc_length_divisions(&self) -> usize {
297                $crate::extras::Curve::arc_length_divisions(&self.$field)
298            }
299
300            fn get_point(&self, t: f64) -> $point {
301                $crate::extras::Curve::get_point(&self.$field, t)
302            }
303
304            fn get_length(&self) -> f64 {
305                $crate::extras::Curve::get_length(&self.$field)
306            }
307
308            fn get_lengths(&self, divisions: usize) -> Vec<f64> {
309                $crate::extras::Curve::get_lengths(&self.$field, divisions)
310            }
311
312            fn get_spaced_points(&self, divisions: usize) -> Vec<$point> {
313                $crate::extras::Curve::get_spaced_points(&self.$field, divisions)
314            }
315
316            fn get_points(&self, divisions: usize) -> Vec<$point> {
317                $crate::extras::Curve::get_points(&self.$field, divisions)
318            }
319        }
320    };
321}
322
323pub(crate) use delegate_curve_path;