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}