Skip to main content

three_rs/extras/
curve.rs

1//! Port of `three.js/src/extras/core/Curve.js`.
2//!
3//! All arithmetic is `f64`, matching JavaScript number semantics, and every
4//! expression keeps three.js' own order and grouping so the rounding matches
5//! bit for bit.
6//!
7//! three.js' `Curve` is an abstract base class whose subclasses override
8//! `getPoint`; here it is a trait with `get_point` required and everything
9//! else default-implemented on top of it. three.js' curves return a `Vector2`
10//! or a `Vector3` depending on the subclass, and the base class branches on
11//! `pt1.isVector2` where it has to build one; here that is the associated
12//! [`Curve::Point`] type, bounded by [`CurveVector`].
13//!
14//! **Deliberate divergence: no arc length cache on the leaf curves.**
15//! `Curve.getLengths()` memoises its result into `this.cacheArcLengths` and
16//! invalidates it when `needsUpdate` is set. The methods here take `&self`, so
17//! a leaf curve (a line, a Bézier, an ellipse, a spline) recomputes on every
18//! call instead. The computation is pure, so the numbers are identical — only
19//! the cost differs. [`CurvePath`](super::CurvePath) is the exception: its
20//! `getPoint` is itself built on `getLength`, so recomputing there is
21//! quadratic, and it keeps both of three.js' caches, with three.js'
22//! invalidation rules (see its doc).
23
24use crate::math::math_utils::clamp;
25use crate::math::{Matrix4, Vector2, Vector3};
26
27/// The return value of [`Curve::compute_frenet_frames`], three.js'
28/// `{ tangents, normals, binormals }`.
29#[derive(Clone, Debug, Default, PartialEq)]
30pub struct FrenetFrames {
31    /// The tangent vector at each sampled point.
32    pub tangents: Vec<Vector3>,
33    /// The normal vector at each sampled point.
34    pub normals: Vec<Vector3>,
35    /// The binormal vector at each sampled point.
36    pub binormals: Vec<Vector3>,
37}
38
39/// What a curve's points are: `Vector2` for the 2D curves (`LineCurve`,
40/// `EllipseCurve`, `Path`, `Shape`, ...), `Vector3` for the 3D ones. The
41mod sealed {
42    pub trait Sealed {}
43    impl Sealed for crate::math::Vector2 {}
44    impl Sealed for crate::math::Vector3 {}
45}
46
47/// handful of vector operations the base class uses generically.
48///
49/// Sealed: it is implemented for `Vector2` and `Vector3` only, which is what
50/// three.js' curves take, so a method can be added to it (or to
51/// `BezierVector` / `LineVector`, which require it) without a break.
52pub trait CurveVector:
53    sealed::Sealed + Copy + Default + PartialEq + std::fmt::Debug + 'static
54{
55    /// `v.distanceTo( w )`.
56    fn distance_to(&self, v: &Self) -> f64;
57    /// `v.equals( w )`.
58    fn equals(&self, v: &Self) -> bool;
59    /// `new VectorN().copy( pt2 ).sub( pt1 ).normalize()` — `Curve.getTangent`'s
60    /// body.
61    fn tangent(pt1: &Self, pt2: &Self) -> Self;
62    /// The point as a `Vector3`, `z = 0` for a `Vector2`. Only
63    /// [`Curve::compute_frenet_frames`] uses it; three.js copies a `Vector2`
64    /// tangent into a `Vector3` there, which leaves `z` `undefined` (`NaN`
65    /// downstream), so frames of a 2D curve are meaningless in three.js and
66    /// merely planar here.
67    fn to_vector3(&self) -> Vector3;
68}
69
70impl CurveVector for Vector2 {
71    fn distance_to(&self, v: &Self) -> f64 {
72        Vector2::distance_to(self, v)
73    }
74    fn equals(&self, v: &Self) -> bool {
75        Vector2::equals(self, v)
76    }
77    fn tangent(pt1: &Self, pt2: &Self) -> Self {
78        let mut tangent = Vector2::default();
79        tangent.copy(pt2).sub(pt1).normalize();
80        tangent
81    }
82    fn to_vector3(&self) -> Vector3 {
83        Vector3::new(self.x, self.y, 0.0)
84    }
85}
86
87impl CurveVector for Vector3 {
88    fn distance_to(&self, v: &Self) -> f64 {
89        Vector3::distance_to(self, v)
90    }
91    fn equals(&self, v: &Self) -> bool {
92        Vector3::equals(self, v)
93    }
94    fn tangent(pt1: &Self, pt2: &Self) -> Self {
95        let mut tangent = Vector3::default();
96        tangent.copy(pt2).sub(pt1).normalize();
97        tangent
98    }
99    fn to_vector3(&self) -> Vector3 {
100        *self
101    }
102}
103
104/// `Curve.getLengths( divisions )`'s computation, without the cache, so that
105/// an implementor that does cache ([`CurvePath`](super::CurvePath)) can
106/// override [`Curve::get_lengths`] and still call it.
107pub(crate) fn compute_lengths<C: Curve + ?Sized>(curve: &C, divisions: usize) -> Vec<f64> {
108    let mut cache = Vec::new();
109    let mut last = curve.get_point(0.0);
110    let mut sum = 0.0;
111
112    cache.push(0.0);
113
114    for p in 1..=divisions {
115        let current = curve.get_point(p as f64 / divisions as f64);
116        sum += current.distance_to(&last);
117        cache.push(sum);
118        last = current;
119    }
120
121    cache
122}
123
124/// `Curve`. Implementors provide [`Curve::get_point`]; the rest is three.js'
125/// own generic machinery built on it.
126pub trait Curve {
127    /// `Vector2` or `Vector3`.
128    type Point: CurveVector;
129
130    /// `Curve.getPoint( t, optionalTarget )`. `t` is an interpolation factor in
131    /// `[0,1]`.
132    fn get_point(&self, t: f64) -> Self::Point;
133
134    /// `Curve.type`: `'LineCurve'`, `'EllipseCurve'`, `'Path'`, ...
135    fn type_name(&self) -> &'static str;
136
137    /// How many divisions `CurvePath.getPoints( divisions )` asks this curve
138    /// for. three.js writes it as a chain of brand checks in `CurvePath`:
139    /// `isEllipseCurve` doubles it, `isLineCurve` / `isLineCurve3` use 1 and
140    /// `isSplineCurve` multiplies by its point count; every other curve uses
141    /// `divisions` as given. Here each of those subclasses overrides this.
142    fn curve_path_resolution(&self, divisions: usize) -> usize {
143        divisions
144    }
145
146    /// `extrudePath.isCatmullRomCurve3 ? extrudePath.closed : false` — the one
147    /// place three.js reads a subclass' `closed` generically
148    /// (`ExtrudeGeometry`). Only [`CatmullRomCurve3`](super::CatmullRomCurve3)
149    /// overrides it.
150    fn is_closed_catmull_rom(&self) -> bool {
151        false
152    }
153
154    /// `Curve.arcLengthDivisions`, default 200.
155    fn arc_length_divisions(&self) -> usize {
156        200
157    }
158
159    /// `Curve.getPointAt( u, optionalTarget )`.
160    fn get_point_at(&self, u: f64) -> Self::Point {
161        let t = self.get_u_to_t_mapping(u, None);
162        self.get_point(t)
163    }
164
165    /// `Curve.getPoints( divisions )`; returns `divisions + 1` points.
166    fn get_points(&self, divisions: usize) -> Vec<Self::Point> {
167        let mut points = Vec::new();
168
169        for d in 0..=divisions {
170            points.push(self.get_point(d as f64 / divisions as f64));
171        }
172
173        points
174    }
175
176    /// `Curve.getSpacedPoints( divisions )`; returns `divisions + 1` points.
177    fn get_spaced_points(&self, divisions: usize) -> Vec<Self::Point> {
178        let mut points = Vec::new();
179
180        for d in 0..=divisions {
181            points.push(self.get_point_at(d as f64 / divisions as f64));
182        }
183
184        points
185    }
186
187    /// `Curve.getLength()`.
188    fn get_length(&self) -> f64 {
189        let lengths = self.get_lengths(self.arc_length_divisions());
190        lengths[lengths.len() - 1]
191    }
192
193    /// `Curve.getLengths( divisions )`. See the module doc: no cache.
194    fn get_lengths(&self, divisions: usize) -> Vec<f64> {
195        compute_lengths(self, divisions)
196    }
197
198    /// `Curve.getUtoTmapping( u, distance )`, statement for statement.
199    fn get_u_to_t_mapping(&self, u: f64, distance: Option<f64>) -> f64 {
200        let arc_lengths = self.get_lengths(self.arc_length_divisions());
201
202        let il = arc_lengths.len();
203
204        // The targeted u distance value to get. three.js tests `if ( distance )`,
205        // which is falsy for `0` as well as for `null`, so a distance of exactly
206        // zero falls through to the `u`-scaled branch; the QUnit test
207        // `getUtoTmapping( 0, 0 )` depends on that.
208        let target_arc_length = match distance {
209            Some(distance) if distance != 0.0 => distance,
210            _ => u * arc_lengths[il - 1],
211        };
212
213        // binary search for the index with largest value smaller than target u distance
214
215        // `low`/`high` are signed because `high` reaches -1 when the target is
216        // below `arcLengths[ 0 ]`, exactly as the JS indices do. three.js hoists
217        // `i` out of the loop, but `i = high` below overwrites it before it is
218        // read again, so here it is loop-local.
219        let (mut low, mut high): (isize, isize) = (0, il as isize - 1);
220
221        while low <= high {
222            // less likely to overflow, though probably not issue here, JS doesn't
223            // really have integers, all numbers are floats. `high - low` is >= 0
224            // inside the loop, so truncating division is `Math.floor` here.
225            let i = low + (high - low) / 2;
226
227            let comparison = arc_lengths[i as usize] - target_arc_length;
228
229            if comparison < 0.0 {
230                low = i + 1;
231            } else if comparison > 0.0 {
232                high = i - 1;
233            } else {
234                high = i;
235                break;
236
237                // DONE
238            }
239        }
240
241        let i = high;
242
243        assert!(
244            i >= 0,
245            "three-rs: Curve::get_u_to_t_mapping: target arc length {target_arc_length} lies before the start of the curve"
246        );
247        let i = i as usize;
248
249        if arc_lengths[i] == target_arc_length {
250            return i as f64 / (il - 1) as f64;
251        }
252
253        // we could get finer grain at lengths, or use simple interpolation between two points
254
255        assert!(
256            i + 1 < il,
257            "three-rs: Curve::get_u_to_t_mapping: target arc length {target_arc_length} lies past the end of the curve"
258        );
259
260        let length_before = arc_lengths[i];
261        let length_after = arc_lengths[i + 1];
262
263        let segment_length = length_after - length_before;
264
265        // determine where we are between the 'before' and 'after' points
266
267        let segment_fraction = (target_arc_length - length_before) / segment_length;
268
269        // add that fractional amount to t
270
271        (i as f64 + segment_fraction) / (il - 1) as f64
272    }
273
274    /// `Curve.getTangent( t, optionalTarget )`.
275    fn get_tangent(&self, t: f64) -> Self::Point {
276        let delta = 0.0001;
277        let mut t1 = t - delta;
278        let mut t2 = t + delta;
279
280        // Capping in case of danger
281
282        if t1 < 0.0 {
283            t1 = 0.0;
284        }
285        if t2 > 1.0 {
286            t2 = 1.0;
287        }
288
289        let pt1 = self.get_point(t1);
290        let pt2 = self.get_point(t2);
291
292        Self::Point::tangent(&pt1, &pt2)
293    }
294
295    /// `Curve.getTangentAt( u, optionalTarget )`.
296    fn get_tangent_at(&self, u: f64) -> Self::Point {
297        let t = self.get_u_to_t_mapping(u, None);
298        self.get_tangent(t)
299    }
300
301    /// `Curve.computeFrenetFrames( segments, closed )`.
302    ///
303    /// See <http://www.cs.indiana.edu/pub/techreports/TR425.pdf>.
304    fn compute_frenet_frames(&self, segments: usize, closed: bool) -> FrenetFrames {
305        let mut normal = Vector3::default();
306
307        let mut tangents: Vec<Vector3> = Vec::new();
308        let mut normals: Vec<Vector3> = Vec::new();
309        let mut binormals: Vec<Vector3> = Vec::new();
310
311        let mut vec = Vector3::default();
312        let mut mat = Matrix4::default();
313
314        // compute the tangent vectors for each segment on the curve
315
316        for i in 0..=segments {
317            let u = i as f64 / segments as f64;
318
319            tangents.push(self.get_tangent_at(u).to_vector3());
320        }
321
322        // select an initial normal vector perpendicular to the first tangent vector,
323        // and in the direction of the minimum tangent xyz component
324
325        normals.push(Vector3::default());
326        binormals.push(Vector3::default());
327        let mut min = f64::MAX;
328        let tx = tangents[0].x.abs();
329        let ty = tangents[0].y.abs();
330        let tz = tangents[0].z.abs();
331
332        if tx <= min {
333            min = tx;
334            normal.set(1.0, 0.0, 0.0);
335        }
336
337        if ty <= min {
338            min = ty;
339            normal.set(0.0, 1.0, 0.0);
340        }
341
342        if tz <= min {
343            normal.set(0.0, 0.0, 1.0);
344        }
345
346        vec.cross_vectors(&tangents[0], &normal).normalize();
347
348        let n0 = *Vector3::default().cross_vectors(&tangents[0], &vec);
349        normals[0] = n0;
350        binormals[0] = *Vector3::default().cross_vectors(&tangents[0], &normals[0]);
351
352        // compute the slowly-varying normal and binormal vectors for each segment on the curve
353
354        for i in 1..=segments {
355            normals.push(normals[i - 1]);
356
357            binormals.push(binormals[i - 1]);
358
359            vec.cross_vectors(&tangents[i - 1], &tangents[i]);
360
361            if vec.length() > f64::EPSILON {
362                vec.normalize();
363
364                // clamp for floating pt errors
365                let theta = clamp(tangents[i - 1].dot(&tangents[i]), -1.0, 1.0).acos();
366
367                normals[i].apply_matrix4(mat.make_rotation_axis(&vec, theta));
368            }
369
370            binormals[i] = *Vector3::default().cross_vectors(&tangents[i], &normals[i]);
371        }
372
373        // if the curve is closed, postprocess the vectors so the first and last normal vectors are the same
374
375        if closed {
376            let mut theta = clamp(normals[0].dot(&normals[segments]), -1.0, 1.0).acos();
377            theta /= segments as f64;
378
379            if tangents[0].dot(vec.cross_vectors(&normals[0], &normals[segments])) > 0.0 {
380                theta = -theta;
381            }
382
383            for i in 1..=segments {
384                // twist a little...
385                normals[i].apply_matrix4(mat.make_rotation_axis(&tangents[i], theta * i as f64));
386                binormals[i] = *Vector3::default().cross_vectors(&tangents[i], &normals[i]);
387            }
388        }
389
390        FrenetFrames {
391            tangents,
392            normals,
393            binormals,
394        }
395    }
396}