ranim_core/components/
vpoint.rs

1use std::cmp::Ordering;
2
3use derive_more::{Deref, DerefMut};
4use glam::DVec3;
5use itertools::Itertools;
6
7use crate::anchor::Aabb;
8use crate::traits::*;
9use crate::utils::bezier::{get_subpath_closed_flag, trim_quad_bezier};
10use crate::utils::math::interpolate_usize;
11use crate::utils::{avg, resize_preserving_order_with_repeated_indices};
12
13fn bezier_aabb(p1: DVec3, p2: DVec3, p3: DVec3) -> [DVec3; 2] {
14    // The parametric equation of a quadratic bezier curve is:
15    // $ P(t) = (1 - t)^2 P_1 + 2 t (1 - t) P_2 + t^2 P_3 $
16    // By taking the derivative of the equation, we get:
17    // $ P'(t) = 2 (1 - t) (P_2 - P_1) + 2 t (P_3 - P_2) $
18    // Extrema of the curve are points at parameter $t in [0, 1]$
19    // where one component ($x$, $y$ or $z$) of $P'(t)$ is zero.
20
21    let mut min = p1.min(p3);
22    let mut max = p1.max(p3);
23
24    let denom = p1 - 2. * p2 + p3;
25    let numer = p1 - p2;
26
27    for i in 0..3 {
28        if denom[i].abs() > f64::EPSILON {
29            let t = numer[i] / denom[i];
30            if (0.0..=1.0).contains(&t) {
31                let val = (1. - t).powi(2) * p1[i] + 2. * t * (1. - t) * p2[i] + t.powi(2) * p3[i];
32                min[i] = min[i].min(val);
33                max[i] = max[i].max(val);
34            }
35        }
36    }
37
38    [min, max]
39}
40
41/// A Vec of VPoint Data. It is used to represent a bunch of quad bezier paths.
42///
43/// Every 3 elements in the inner vector is a quad bezier path.
44///
45/// | 0(Anchor) | 1(Handle) | 2(Anchor) | 3(Handle) | 4(Anchor) |
46/// |-----------|-----------|-----------|-----------|-----------|
47/// | a | b | c | d | e(subpath0) |
48///
49/// If the handle is equal to the previous anchor, it represents a subpath's end.
50///
51/// | 0(Anchor) | 1(Handle) | 2(Anchor) | 3(Handle) | 4(Anchor) | 5(Handle) | 6(Anchor) |
52/// |-----------|-----------|-----------|-----------|-----------|-----------|-----------|
53/// | a | b | c | c(subpath0) | d | e | f (subpath1) |
54#[derive(Debug, Clone, PartialEq, Deref, DerefMut, ranim_macros::Interpolatable)]
55pub struct VPointVec(pub Vec<DVec3>);
56
57impl Aabb for VPointVec {
58    /// Note: This iterates over all consecutive bezier segments without distinguishing
59    /// subpath breaks. A subpath break segment `[c, c, d]` (where handle == previous anchor)
60    /// produces B(t) = (1-t²)·c + t²·d, which is monotonic from c to d with no interior
61    /// extrema. Since both c and d are real anchor points already included in the AABB,
62    /// the break segment contributes nothing extra, making special-casing unnecessary.
63    fn aabb(&self) -> [DVec3; 2] {
64        self.0
65            .windows(3)
66            .step_by(2)
67            .map(|w| bezier_aabb(w[0], w[1], w[2]))
68            .reduce(|[acc_min, acc_max], [min, max]| [acc_min.min(min), acc_max.max(max)])
69            .unwrap_or([DVec3::ZERO; 2])
70    }
71}
72
73impl AsRef<[DVec3]> for VPointVec {
74    fn as_ref(&self) -> &[DVec3] {
75        self.0.as_ref()
76    }
77}
78
79impl AsMut<[DVec3]> for VPointVec {
80    fn as_mut(&mut self) -> &mut [DVec3] {
81        self.0.as_mut()
82    }
83}
84
85impl transform::ShiftTransform for VPointVec {
86    fn shift(&mut self, offset: DVec3) -> &mut Self {
87        self.as_mut().shift(offset);
88        self
89    }
90}
91
92impl transform::RotateTransform for VPointVec {
93    fn rotate_on_axis(&mut self, axis: DVec3, angle: f64) -> &mut Self {
94        self.as_mut().rotate_on_axis(axis, angle);
95        self
96    }
97}
98
99impl transform::ScaleTransform for VPointVec {
100    fn scale(&mut self, scale: DVec3) -> &mut Self {
101        self.as_mut().scale(scale);
102        self
103    }
104}
105
106impl Alignable for VPointVec {
107    fn is_aligned(&self, other: &Self) -> bool {
108        self.len() == other.len()
109    }
110    fn align_with(&mut self, other: &mut Self) {
111        if self.is_empty() {
112            self.0 = vec![DVec3::ZERO; 3];
113        }
114        if self.len() > other.len() {
115            other.align_with(self);
116            return;
117        }
118
119        let into_closed_subpaths = |subpaths: Vec<Vec<DVec3>>| -> Vec<Vec<DVec3>> {
120            subpaths
121                .into_iter()
122                .map(|sp| {
123                    // should have no zero-length subpath
124                    if !get_subpath_closed_flag(&sp).map(|f| f.1).unwrap() {
125                        let sp_len = sp.len();
126                        let sp_iter = sp.into_iter();
127                        sp_iter
128                            .clone()
129                            .take(sp_len - 1)
130                            .chain(sp_iter.rev())
131                            .collect::<Vec<_>>()
132                    } else {
133                        sp
134                    }
135                })
136                .collect::<Vec<_>>()
137        };
138        let mut sps_self = into_closed_subpaths(self.get_subpaths());
139        let mut sps_other = into_closed_subpaths(other.get_subpaths());
140        let len = sps_self.len().max(sps_other.len());
141        let resize_subpaths = |sps: &mut Vec<Vec<DVec3>>| {
142            if sps.len() != len {
143                let (mut x, idxs) = resize_preserving_order_with_repeated_indices(sps, len);
144                for idx in idxs {
145                    let center = avg(&x[idx]);
146                    x[idx].fill(center);
147                }
148                *sps = x;
149            }
150        };
151        resize_subpaths(&mut sps_self);
152        resize_subpaths(&mut sps_other);
153
154        let points_to_bez_tuples = |points: &[DVec3]| -> Vec<[DVec3; 3]> {
155            points
156                .windows(3)
157                .step_by(2)
158                .map(|w| [w[0], w[1], w[2]])
159                .collect()
160        };
161        let align_points = |points: &[DVec3], len: usize| -> Vec<DVec3> {
162            let bez_tuples = points_to_bez_tuples(points);
163
164            let diff_len = (len - points.len()) / 2;
165            // println!("{:?}", bez_tuples);
166            let mut lens = bez_tuples
167                .iter()
168                .map(|[a, b, c]| {
169                    if (a - b).length_squared() < f64::EPSILON {
170                        0.0
171                    } else {
172                        (c - a).length()
173                    }
174                })
175                .collect::<Vec<_>>();
176            let mut ipc = vec![0usize; bez_tuples.len()];
177
178            for _ in 0..diff_len {
179                // println!("{:?}", lens);
180                let idx = lens
181                    .iter()
182                    .position_max_by(|a, b| a.partial_cmp(b).unwrap_or(Ordering::Equal))
183                    .unwrap();
184                ipc[idx] += 1;
185                lens[idx] *= ipc[idx] as f64 / (ipc[idx] + 1) as f64;
186            }
187            // println!("BEZ: {:?}", bez_tuples);
188            // println!("IPC: {:?}", ipc);
189            let new_segs = bez_tuples
190                .into_iter()
191                .zip(ipc)
192                .map(|(bez, ipc)| {
193                    // curve cnt is ipc + 1, anchor cnt is ipc + 2
194                    let alphas = (0..ipc + 2)
195                        .map(|i: usize| i as f64 / (ipc + 1) as f64)
196                        .collect::<Vec<_>>();
197                    let mut new_points = Vec::with_capacity((ipc + 1) * 2 + 1);
198                    new_points.push(bez[0]);
199                    // println!("###bez: {:?}, ipc: {}", bez, ipc);
200                    alphas.iter().tuple_windows().for_each(|(a1, a2)| {
201                        let partial = trim_quad_bezier(&bez, *a1, *a2);
202                        // println!("{} {}: {:?}", a1, a2, partial);
203                        new_points.extend(partial[1..].iter())
204                    });
205                    // println!("{:?}", new_points);
206                    new_points
207                })
208                .collect::<Vec<_>>();
209            let mut new_points = Vec::with_capacity(other.len());
210            new_points.extend_from_slice(&new_segs[0]);
211            for seg in new_segs.into_iter().skip(1) {
212                new_points.extend(&seg[1..]);
213            }
214            new_points
215        };
216
217        sps_self
218            .iter_mut()
219            .zip(sps_other.iter_mut())
220            .for_each(|(sp_a, sp_b)| {
221                // println!("sp align: {} {}", sp_a.len(), sp_b.len());
222                let len = sp_a.len().max(sp_b.len());
223                if sp_a.len() != len {
224                    *sp_a = align_points(sp_a, len)
225                }
226                if sp_b.len() != len {
227                    *sp_b = align_points(sp_b, len)
228                }
229            });
230
231        let sps_to_points = |sps: Vec<Vec<DVec3>>| -> Vec<DVec3> {
232            let mut points = sps
233                .into_iter()
234                .flat_map(|sp| {
235                    let last = *sp.last().unwrap();
236                    sp.into_iter().chain(std::iter::once(last))
237                })
238                .collect::<Vec<_>>();
239            points.pop();
240            points
241        };
242
243        self.0 = sps_to_points(sps_self);
244        other.0 = sps_to_points(sps_other);
245    }
246}
247
248// fn extend_subpath_with_n(mut subpath: Vec<DVec3>, n: usize) -> Vec<DVec3> {
249//     let beziers = subpath.iter().zip(other)
250// }
251
252impl VPointVec {
253    /// Get Subpaths
254    pub fn get_subpaths(&self) -> Vec<Vec<DVec3>> {
255        let mut subpaths = Vec::new();
256
257        let mut subpath = Vec::new();
258        let mut iter_a = self.iter().step_by(2).peekable();
259        let mut iter_b = self.iter().skip(1).step_by(2).peekable();
260
261        loop {
262            match (iter_a.next(), iter_b.next()) {
263                (Some(a), Some(b)) => {
264                    subpath.push(*a);
265                    if a != b {
266                        subpath.push(*b);
267                    } else {
268                        while let (Some(c), Some(d)) = (iter_a.peek(), iter_b.peek())
269                            && b == *c
270                            && c == d
271                        {
272                            subpath.extend([**c; 2]);
273                            iter_a.next();
274                            iter_b.next();
275                        }
276                        assert!(subpath.len() % 2 != 0);
277                        subpaths.push(std::mem::take(&mut subpath));
278                    }
279                }
280                (Some(a), None) => {
281                    subpath.push(*a);
282                    assert!(subpath.len() % 2 != 0);
283                    subpaths.push(std::mem::take(&mut subpath));
284                    break;
285                }
286                _ => unreachable!(),
287            }
288        }
289
290        // for sp in &subpaths {
291        //     println!("{}\n - {:?}", sp.len(), sp);
292        // }
293
294        subpaths
295    }
296    /// Get the segment
297    pub fn get_seg(&self, idx: usize) -> Option<&[DVec3; 3]> {
298        self.get(idx * 2..idx * 2 + 3)
299            .and_then(|seg| seg.try_into().ok())
300    }
301    /// Get closed path flags
302    pub fn get_closepath_flags(&self) -> Vec<bool> {
303        let len = self.len();
304        let mut flags = vec![false; len];
305
306        // println!("{:?}", self.0);
307        let mut i = 0;
308        while let Some((end_idx, is_closed)) = self.get(i..).and_then(get_subpath_closed_flag) {
309            // println!("{i} {end_idx} {len}");
310            let end_idx = i + end_idx + 2;
311            flags[i..=end_idx.clamp(i, len - 1)].fill(is_closed);
312            i = end_idx;
313        }
314        // println!("{:?}", flags);
315
316        flags
317    }
318
319    /// Put the start and end points of the item on the given points.
320    pub fn put_start_and_end_on(&mut self, start: DVec3, end: DVec3) -> &mut Self {
321        let (cur_start, cur_end) = (
322            self.first().cloned().unwrap_or_default(),
323            self.last().cloned().unwrap_or_default(),
324        );
325        let cur_v = cur_end - cur_start;
326        if cur_v.length_squared() <= f64::EPSILON {
327            return self;
328        }
329
330        let v = end - start;
331        self.with_origin(cur_start, |x| {
332            x.scale(DVec3::splat(v.length() / cur_v.length()));
333        });
334        let rotate_angle = cur_v.angle_between(v);
335        let mut rotate_axis = cur_v.cross(v);
336        if rotate_axis.length_squared() <= f64::EPSILON {
337            rotate_axis = DVec3::Z;
338        }
339        rotate_axis = rotate_axis.normalize();
340        self.with_origin(cur_start, |x| {
341            x.rotate_on_axis(rotate_axis, rotate_angle);
342        });
343        self.shift(start - cur_start);
344
345        self
346    }
347
348    /// Get partial of the vpoint.
349    ///
350    /// This will trim the bezier.
351    pub fn get_partial(&self, range: std::ops::Range<f64>) -> Self {
352        let max_anchor_idx = self.len() / 2;
353
354        let (start_index, start_residue) = interpolate_usize(0, max_anchor_idx, range.start);
355        let (end_index, end_residue) = interpolate_usize(0, max_anchor_idx, range.end);
356
357        if end_index - start_index == 0 {
358            let seg = *self.get_seg(start_index).unwrap();
359            let quad = trim_quad_bezier(&seg, start_residue, end_residue);
360            VPointVec(quad.into())
361        } else {
362            let mut partial = Vec::with_capacity((end_index - start_index + 1 + 2) * 2 + 1);
363
364            let seg = *self.get_seg(start_index).unwrap();
365            let start_part = trim_quad_bezier(&seg, start_residue, 1.0);
366            partial.extend_from_slice(&start_part);
367
368            // If start_index < end_index - 1, we need to add the middle segment
369            //  start     mid    end
370            // [o - o] [- o - o] [- o]
371            if end_index - start_index > 1 {
372                let mid = self
373                    .get((start_index + 1) * 2 + 1..=end_index * 2)
374                    .unwrap()
375                    .iter();
376                partial.extend(mid);
377            }
378
379            if end_residue != 0.0 {
380                let seg = *self.get_seg(end_index).unwrap();
381                let end_part = trim_quad_bezier(&seg, 0.0, end_residue);
382                partial.extend_from_slice(&end_part[1..]);
383            }
384
385            VPointVec(partial)
386        }
387    }
388}
389
390#[cfg(test)]
391mod test {
392    use std::f64::consts::PI;
393
394    use assert_float_eq::assert_float_absolute_eq;
395    use glam::{DVec3, dvec3};
396
397    use crate::{
398        components::vpoint::VPointVec,
399        traits::{Aabb, RotateTransform},
400    };
401
402    fn assert_dvec3_eq(a: DVec3, b: DVec3) {
403        assert_float_absolute_eq!(a.distance_squared(b), 0.0, 1e-10);
404    }
405
406    fn assert_points_eq(result: &[DVec3], expected: &[DVec3]) {
407        assert_eq!(result.len(), expected.len(), "length mismatch");
408        for (r, e) in result.iter().zip(expected) {
409            assert_dvec3_eq(*r, *e);
410        }
411    }
412
413    #[test]
414    fn test_get_subpath_two_subpaths() {
415        // handle == previous anchor → subpath break
416        let points = VPointVec(vec![
417            DVec3::X,
418            DVec3::Y,
419            DVec3::Z,
420            DVec3::Z,
421            DVec3::NEG_X,
422            DVec3::NEG_Y,
423            DVec3::ZERO,
424        ]);
425        let sps = points.get_subpaths();
426        assert_eq!(sps.len(), 2);
427        assert_eq!(sps[0], vec![DVec3::X, DVec3::Y, DVec3::Z]);
428        assert_eq!(sps[1], vec![DVec3::NEG_X, DVec3::NEG_Y, DVec3::ZERO]);
429    }
430
431    #[test]
432    fn test_get_subpath_single() {
433        let points = VPointVec(vec![DVec3::X, DVec3::Y, DVec3::Z]);
434        let sps = points.get_subpaths();
435        assert_eq!(sps.len(), 1);
436        assert_eq!(sps[0], vec![DVec3::X, DVec3::Y, DVec3::Z]);
437    }
438
439    #[test]
440    fn test_get_subpath_degenerate_tail() {
441        // Second subpath is a degenerate single point
442        let points = VPointVec(vec![DVec3::X, DVec3::Y, DVec3::Z, DVec3::Z, DVec3::Z]);
443        let sps = points.get_subpaths();
444        assert_eq!(sps.len(), 2);
445        assert_eq!(sps[0], vec![DVec3::X, DVec3::Y, DVec3::Z]);
446        assert_eq!(sps[1], vec![DVec3::Z]);
447    }
448
449    #[test]
450    fn test_get_partial_full_range() {
451        let points = VPointVec(vec![
452            dvec3(0.0, 0.0, 0.0),
453            dvec3(1.0, 1.0, 1.0),
454            dvec3(2.0, 2.0, 2.0),
455            dvec3(2.0, 2.0, 2.0),
456            dvec3(3.0, 3.0, 3.0),
457            dvec3(4.0, 4.0, 4.0),
458            dvec3(5.0, 5.0, 5.0),
459        ]);
460        let partial = points.get_partial(0.0..1.0);
461        assert_eq!(partial, points);
462    }
463
464    #[test]
465    fn test_get_partial_half() {
466        let points = VPointVec(vec![
467            dvec3(0.0, 0.0, 0.0),
468            dvec3(1.0, 1.0, 1.0),
469            dvec3(2.0, 2.0, 2.0),
470            dvec3(2.0, 2.0, 2.0),
471            dvec3(3.0, 3.0, 3.0),
472            dvec3(4.0, 4.0, 4.0),
473            dvec3(5.0, 5.0, 5.0),
474        ]);
475        let partial = points.get_partial(0.0..0.5);
476        assert_eq!(partial.len(), 5);
477        assert_dvec3_eq(partial[0], dvec3(0.0, 0.0, 0.0));
478        assert_dvec3_eq(*partial.last().unwrap(), dvec3(2.25, 2.25, 2.25));
479    }
480
481    #[test]
482    fn test_get_partial_single_segment() {
483        let points = VPointVec(vec![
484            dvec3(0.0, 0.0, 0.0),
485            dvec3(1.0, 1.0, 1.0),
486            dvec3(2.0, 2.0, 2.0),
487            dvec3(2.0, 2.0, 2.0),
488            dvec3(3.0, 3.0, 3.0),
489            dvec3(4.0, 4.0, 4.0),
490            dvec3(5.0, 5.0, 5.0),
491        ]);
492        // Within a single segment: trim first bezier to [0, 0.5]
493        let partial = points.get_partial(0.0..1.0 / 6.0);
494        assert_eq!(partial.len(), 3);
495        assert_dvec3_eq(partial[0], dvec3(0.0, 0.0, 0.0));
496        assert_dvec3_eq(partial[1], dvec3(0.5, 0.5, 0.5));
497        assert_dvec3_eq(partial[2], dvec3(1.0, 1.0, 1.0));
498    }
499
500    #[test]
501    fn test_get_partial_exact_segment_boundary() {
502        let points = VPointVec(vec![
503            dvec3(0.0, 0.0, 0.0),
504            dvec3(1.0, 1.0, 1.0),
505            dvec3(2.0, 2.0, 2.0),
506            dvec3(2.0, 2.0, 2.0),
507            dvec3(3.0, 3.0, 3.0),
508            dvec3(4.0, 4.0, 4.0),
509            dvec3(5.0, 5.0, 5.0),
510        ]);
511        // Exactly the first segment
512        let partial = points.get_partial(0.0..1.0 / 3.0);
513        assert_eq!(partial.len(), 3);
514        assert_dvec3_eq(partial[0], dvec3(0.0, 0.0, 0.0));
515        assert_dvec3_eq(partial[2], dvec3(2.0, 2.0, 2.0));
516    }
517
518    #[test]
519    fn test_rotate() {
520        let mut points = VPointVec(vec![
521            dvec3(0.0, 0.0, 0.0),
522            dvec3(1.0, 0.0, 0.0),
523            dvec3(2.0, 2.0, 0.0),
524        ]);
525        points.rotate_on_z(PI);
526        assert_points_eq(
527            &points.0,
528            &[
529                dvec3(0.0, 0.0, 0.0),
530                dvec3(-1.0, 0.0, 0.0),
531                dvec3(-2.0, -2.0, 0.0),
532            ],
533        );
534    }
535
536    #[test]
537    fn test_put_start_and_end_on() {
538        let mut points = VPointVec(vec![
539            dvec3(0.0, 0.0, 0.0),
540            dvec3(1.0, 0.0, 0.0),
541            dvec3(2.0, 2.0, 0.0),
542        ]);
543
544        points.put_start_and_end_on(dvec3(0.0, 0.0, 0.0), dvec3(4.0, 4.0, 0.0));
545        assert_points_eq(
546            &points.0,
547            &[
548                dvec3(0.0, 0.0, 0.0),
549                dvec3(2.0, 0.0, 0.0),
550                dvec3(4.0, 4.0, 0.0),
551            ],
552        );
553
554        points.put_start_and_end_on(dvec3(0.0, 0.0, 0.0), dvec3(-2.0, -2.0, 0.0));
555        assert_points_eq(
556            &points.0,
557            &[
558                dvec3(0.0, 0.0, 0.0),
559                dvec3(-1.0, 0.0, 0.0),
560                dvec3(-2.0, -2.0, 0.0),
561            ],
562        );
563    }
564
565    #[test]
566    fn test_aabb_single_segment_with_extremum() {
567        // Parabola: control point below endpoints → min.y is at the curve extremum
568        let points = VPointVec(vec![
569            dvec3(-2., 1., 0.),
570            dvec3(0., -1., 0.),
571            dvec3(2., 1., 0.),
572        ]);
573        let [min, max] = points.aabb();
574        assert_dvec3_eq(min, dvec3(-2., 0., 0.));
575        assert_dvec3_eq(max, dvec3(2., 1., 0.));
576    }
577
578    #[test]
579    fn test_aabb_straight_line() {
580        // Handle on the line → no extremum beyond endpoints
581        let points = VPointVec(vec![
582            dvec3(0., 0., 0.),
583            dvec3(1., 1., 0.),
584            dvec3(2., 2., 0.),
585        ]);
586        let [min, max] = points.aabb();
587        assert_dvec3_eq(min, dvec3(0., 0., 0.));
588        assert_dvec3_eq(max, dvec3(2., 2., 0.));
589    }
590
591    #[test]
592    fn test_aabb_multiple_segments() {
593        // Two symmetric segments with handles pulling in opposite y directions
594        let points = VPointVec(vec![
595            dvec3(0., 0., 0.),
596            dvec3(1., 2., 0.),
597            dvec3(2., 0., 0.),
598            dvec3(3., -2., 0.),
599            dvec3(4., 0., 0.),
600        ]);
601        let [min, max] = points.aabb();
602        // Extrema at t=0.5 of each segment: y=1.0 and y=-1.0
603        assert_dvec3_eq(min, dvec3(0., -1., 0.));
604        assert_dvec3_eq(max, dvec3(4., 1., 0.));
605    }
606
607    #[test]
608    fn test_aabb_multiple_subpaths() {
609        // Two subpaths: first curves up (y extremum=1), second curves down (y extremum=-1)
610        let points = VPointVec(vec![
611            dvec3(0., 0., 0.),
612            dvec3(0., 2., 0.),
613            dvec3(2., 0., 0.),
614            dvec3(2., 0., 0.), // handle == prev anchor → subpath break
615            dvec3(3., 0., 0.),
616            dvec3(3., -2., 0.),
617            dvec3(5., 0., 0.),
618        ]);
619        let [min, max] = points.aabb();
620        assert_dvec3_eq(min, dvec3(0., -1., 0.));
621        assert_dvec3_eq(max, dvec3(5., 1., 0.));
622    }
623
624    #[test]
625    fn test_aabb_degenerate_single_point() {
626        let points = VPointVec(vec![DVec3::ONE; 3]);
627        let [min, max] = points.aabb();
628        assert_dvec3_eq(min, DVec3::ONE);
629        assert_dvec3_eq(max, DVec3::ONE);
630    }
631
632    #[test]
633    fn test_aabb_empty() {
634        let points = VPointVec(vec![]);
635        let [min, max] = points.aabb();
636        assert_dvec3_eq(min, DVec3::ZERO);
637        assert_dvec3_eq(max, DVec3::ZERO);
638    }
639}
ranim_core/components/vpoint.rs

ranim_core/components/
vpoint.rs
