1use std::cmp::Ordering;
2
3use approx::relative_eq;
4
5use derive_more::{Deref, DerefMut};
6use glam::DVec3;
7use itertools::Itertools;
8
9use crate::anchor::Aabb;
10use crate::traits::{
11 Alignable, ApplyTransform, RotateTransform, ScaleTransform, ShiftTransform, ShiftTransformExt,
12};
13use crate::utils::bezier::{get_subpath_closed_flag, trim_quad_bezier};
14use crate::utils::math::interpolate_usize;
15use crate::utils::{avg, resize_preserving_order_with_repeated_indices};
16
17fn bezier_aabb(p1: DVec3, p2: DVec3, p3: DVec3) -> [DVec3; 2] {
18 let mut min = p1.min(p3);
26 let mut max = p1.max(p3);
27
28 let denom = p1 - 2. * p2 + p3;
29 let numer = p1 - p2;
30
31 for i in 0..3 {
32 if denom[i].abs() > f64::EPSILON {
33 let t = numer[i] / denom[i];
34 if (0.0..=1.0).contains(&t) {
35 let val = (1. - t).powi(2) * p1[i] + 2. * t * (1. - t) * p2[i] + t.powi(2) * p3[i];
36 min[i] = min[i].min(val);
37 max[i] = max[i].max(val);
38 }
39 }
40 }
41
42 [min, max]
43}
44
45#[derive(Debug, Clone, PartialEq, Deref, DerefMut, ranim_macros::Interpolatable)]
59pub struct VPointVec(pub Vec<DVec3>);
60
61impl Aabb for VPointVec {
62 fn aabb(&self) -> [DVec3; 2] {
68 self.0
69 .windows(3)
70 .step_by(2)
71 .map(|w| bezier_aabb(w[0], w[1], w[2]))
72 .reduce(|[acc_min, acc_max], [min, max]| [acc_min.min(min), acc_max.max(max)])
73 .unwrap_or([DVec3::ZERO; 2])
74 }
75}
76
77impl AsRef<[DVec3]> for VPointVec {
78 fn as_ref(&self) -> &[DVec3] {
79 self.0.as_ref()
80 }
81}
82
83impl AsMut<[DVec3]> for VPointVec {
84 fn as_mut(&mut self) -> &mut [DVec3] {
85 self.0.as_mut()
86 }
87}
88
89impl<G: Into<glam::DAffine3>> ApplyTransform<G> for VPointVec {
90 fn apply(&mut self, transform: G) -> &mut Self {
91 self.0.apply(transform.into());
92 self
93 }
94}
95
96impl Alignable for VPointVec {
97 fn is_aligned(&self, other: &Self) -> bool {
98 self.len() == other.len()
99 }
100 fn align_with(&mut self, other: &mut Self) {
101 if self.is_empty() {
102 self.0 = vec![DVec3::ZERO; 3];
103 }
104 if self.len() > other.len() {
105 other.align_with(self);
106 return;
107 }
108
109 let into_closed_subpaths = |subpaths: Vec<Vec<DVec3>>| -> Vec<Vec<DVec3>> {
110 subpaths
111 .into_iter()
112 .map(|sp| {
113 if !get_subpath_closed_flag(&sp).map(|f| f.1).unwrap() {
115 let sp_len = sp.len();
116 let sp_iter = sp.into_iter();
117 sp_iter
118 .clone()
119 .take(sp_len - 1)
120 .chain(sp_iter.rev())
121 .collect::<Vec<_>>()
122 } else {
123 sp
124 }
125 })
126 .collect::<Vec<_>>()
127 };
128 let mut sps_self = into_closed_subpaths(self.get_subpaths());
129 let mut sps_other = into_closed_subpaths(other.get_subpaths());
130 let len = sps_self.len().max(sps_other.len());
131 let resize_subpaths = |sps: &mut Vec<Vec<DVec3>>| {
132 if sps.len() != len {
133 let (mut x, idxs) = resize_preserving_order_with_repeated_indices(sps, len);
134 for idx in idxs {
135 let center = avg(&x[idx]);
136 x[idx].fill(center);
137 }
138 *sps = x;
139 }
140 };
141 resize_subpaths(&mut sps_self);
142 resize_subpaths(&mut sps_other);
143
144 let points_to_bez_tuples = |points: &[DVec3]| -> Vec<[DVec3; 3]> {
145 points
146 .windows(3)
147 .step_by(2)
148 .map(|w| [w[0], w[1], w[2]])
149 .collect()
150 };
151 let align_points = |points: &[DVec3], len: usize| -> Vec<DVec3> {
152 let bez_tuples = points_to_bez_tuples(points);
153
154 let diff_len = (len - points.len()) / 2;
155 let mut lens = bez_tuples
157 .iter()
158 .map(|[a, b, c]| {
159 if (a - b).length_squared() < f64::EPSILON {
160 0.0
161 } else {
162 (c - a).length()
163 }
164 })
165 .collect::<Vec<_>>();
166 let mut ipc = vec![0usize; bez_tuples.len()];
167
168 for _ in 0..diff_len {
169 let idx = lens
171 .iter()
172 .position_max_by(|a, b| a.partial_cmp(b).unwrap_or(Ordering::Equal))
173 .unwrap();
174 ipc[idx] += 1;
175 lens[idx] *= ipc[idx] as f64 / (ipc[idx] + 1) as f64;
176 }
177 let new_segs = bez_tuples
180 .into_iter()
181 .zip(ipc)
182 .map(|(bez, ipc)| {
183 let alphas = (0..ipc + 2)
185 .map(|i: usize| i as f64 / (ipc + 1) as f64)
186 .collect::<Vec<_>>();
187 let mut new_points = Vec::with_capacity((ipc + 1) * 2 + 1);
188 new_points.push(bez[0]);
189 alphas.iter().tuple_windows().for_each(|(a1, a2)| {
191 let partial = trim_quad_bezier(&bez, *a1, *a2);
192 new_points.extend(partial[1..].iter())
194 });
195 new_points
197 })
198 .collect::<Vec<_>>();
199 let mut new_points = Vec::with_capacity(other.len());
200 new_points.extend_from_slice(&new_segs[0]);
201 for seg in new_segs.into_iter().skip(1) {
202 new_points.extend(&seg[1..]);
203 }
204 new_points
205 };
206
207 sps_self
208 .iter_mut()
209 .zip(sps_other.iter_mut())
210 .for_each(|(sp_a, sp_b)| {
211 let len = sp_a.len().max(sp_b.len());
213 if sp_a.len() != len {
214 *sp_a = align_points(sp_a, len)
215 }
216 if sp_b.len() != len {
217 *sp_b = align_points(sp_b, len)
218 }
219 });
220
221 let sps_to_points = |sps: Vec<Vec<DVec3>>| -> Vec<DVec3> {
222 let mut points = sps
223 .into_iter()
224 .flat_map(|sp| {
225 let last = *sp.last().unwrap();
226 sp.into_iter().chain(std::iter::once(last))
227 })
228 .collect::<Vec<_>>();
229 points.pop();
230 points
231 };
232
233 self.0 = sps_to_points(sps_self);
234 other.0 = sps_to_points(sps_other);
235 }
236}
237
238impl VPointVec {
243 pub fn get_subpaths(&self) -> Vec<Vec<DVec3>> {
245 let mut subpaths = Vec::new();
246
247 let mut subpath = Vec::new();
248 let mut iter_a = self.iter().step_by(2).peekable();
249 let mut iter_b = self.iter().skip(1).step_by(2).peekable();
250
251 loop {
252 match (iter_a.next(), iter_b.next()) {
253 (Some(a), Some(b)) => {
254 subpath.push(*a);
255 if a != b {
256 subpath.push(*b);
257 } else {
258 while let (Some(c), Some(d)) = (iter_a.peek(), iter_b.peek())
259 && b == *c
260 && c == d
261 {
262 subpath.extend([**c; 2]);
263 iter_a.next();
264 iter_b.next();
265 }
266 assert!(subpath.len() % 2 != 0);
267 subpaths.push(std::mem::take(&mut subpath));
268 }
269 }
270 (Some(a), None) => {
271 subpath.push(*a);
272 assert!(subpath.len() % 2 != 0);
273 subpaths.push(std::mem::take(&mut subpath));
274 break;
275 }
276 _ => unreachable!(),
277 }
278 }
279
280 subpaths
285 }
286 pub fn get_seg(&self, idx: usize) -> Option<&[DVec3; 3]> {
288 self.get(idx * 2..idx * 2 + 3)
289 .and_then(|seg| seg.try_into().ok())
290 }
291 pub fn get_closepath_flags(&self) -> Vec<bool> {
297 let mut flags = vec![false; self.len()];
298
299 let mut start = 0;
300 let mut last_closed = false;
301 for subpath in self.get_subpaths() {
302 let count = subpath.len();
303 let end = (start + count).min(self.len());
304 last_closed = count >= 2 && relative_eq!(subpath[0], subpath[count - 1]);
305 flags[start..end].fill(last_closed);
306 start = end;
307 }
308 if start < self.len() {
311 flags[start..].fill(last_closed);
312 }
313 flags
314 }
315
316 pub fn put_start_and_end_on(&mut self, start: DVec3, end: DVec3) -> &mut Self {
318 let (cur_start, cur_end) = (
319 self.first().cloned().unwrap_or_default(),
320 self.last().cloned().unwrap_or_default(),
321 );
322 let cur_v = cur_end - cur_start;
323 if cur_v.length_squared() <= f64::EPSILON {
324 return self;
325 }
326
327 let v = end - start;
328 self.with_origin(cur_start, |x| {
329 x.scale(DVec3::splat(v.length() / cur_v.length()));
330 });
331 let rotate_angle = cur_v.angle_between(v);
332 let mut rotate_axis = cur_v.cross(v);
333 if rotate_axis.length_squared() <= f64::EPSILON {
334 rotate_axis = DVec3::Z;
335 }
336 rotate_axis = rotate_axis.normalize();
337 self.with_origin(cur_start, |x| {
338 x.rotate_on_axis(rotate_axis, rotate_angle);
339 });
340 self.shift(start - cur_start);
341
342 self
343 }
344
345 pub fn get_partial(&self, range: std::ops::Range<f64>) -> Self {
349 let max_anchor_idx = self.len() / 2;
350
351 let (start_index, start_residue) = interpolate_usize(0, max_anchor_idx, range.start);
352 let (end_index, end_residue) = interpolate_usize(0, max_anchor_idx, range.end);
353
354 if end_index - start_index == 0 {
355 let seg = *self.get_seg(start_index).unwrap();
356 let quad = trim_quad_bezier(&seg, start_residue, end_residue);
357 VPointVec(quad.into())
358 } else {
359 let mut partial = Vec::with_capacity((end_index - start_index + 1 + 2) * 2 + 1);
360
361 let seg = *self.get_seg(start_index).unwrap();
362 let start_part = trim_quad_bezier(&seg, start_residue, 1.0);
363 partial.extend_from_slice(&start_part);
364
365 if end_index - start_index > 1 {
369 let mid = self
370 .get((start_index + 1) * 2 + 1..=end_index * 2)
371 .unwrap()
372 .iter();
373 partial.extend(mid);
374 }
375
376 if end_residue != 0.0 {
377 let seg = *self.get_seg(end_index).unwrap();
378 let end_part = trim_quad_bezier(&seg, 0.0, end_residue);
379 partial.extend_from_slice(&end_part[1..]);
380 }
381
382 VPointVec(partial)
383 }
384 }
385}
386
387#[cfg(test)]
388mod test {
389 use std::f64::consts::PI;
390
391 use assert_float_eq::assert_float_absolute_eq;
392 use glam::{DVec3, dvec3};
393
394 use crate::{
395 components::vpoint::VPointVec,
396 traits::{Aabb, RotateTransform},
397 };
398
399 fn assert_dvec3_eq(a: DVec3, b: DVec3) {
400 assert_float_absolute_eq!(a.distance_squared(b), 0.0, 1e-10);
401 }
402
403 fn assert_points_eq(result: &[DVec3], expected: &[DVec3]) {
404 assert_eq!(result.len(), expected.len(), "length mismatch");
405 for (r, e) in result.iter().zip(expected) {
406 assert_dvec3_eq(*r, *e);
407 }
408 }
409
410 fn partial_fixture() -> VPointVec {
411 VPointVec(vec![
412 dvec3(0.0, 0.0, 0.0),
413 dvec3(1.0, 1.0, 1.0),
414 dvec3(2.0, 2.0, 2.0),
415 dvec3(2.0, 2.0, 2.0),
416 dvec3(3.0, 3.0, 3.0),
417 dvec3(4.0, 4.0, 4.0),
418 dvec3(5.0, 5.0, 5.0),
419 ])
420 }
421
422 #[test]
423 fn get_subpaths_splits_on_degenerate_seam_handles() {
424 let two = VPointVec(vec![
425 DVec3::X,
426 DVec3::Y,
427 DVec3::Z,
428 DVec3::Z,
429 DVec3::NEG_X,
430 DVec3::NEG_Y,
431 DVec3::ZERO,
432 ]);
433 let subpaths = two.get_subpaths();
434 assert_eq!(subpaths.len(), 2);
435 assert_points_eq(&subpaths[0], &[DVec3::X, DVec3::Y, DVec3::Z]);
436 assert_points_eq(&subpaths[1], &[DVec3::NEG_X, DVec3::NEG_Y, DVec3::ZERO]);
437
438 let single = VPointVec(vec![DVec3::X, DVec3::Y, DVec3::Z]);
439 assert_eq!(
440 single.get_subpaths(),
441 vec![vec![DVec3::X, DVec3::Y, DVec3::Z]]
442 );
443
444 let degenerate_tail = VPointVec(vec![DVec3::X, DVec3::Y, DVec3::Z, DVec3::Z, DVec3::Z]);
445 let subpaths = degenerate_tail.get_subpaths();
446 assert_eq!(subpaths.len(), 2);
447 assert_points_eq(&subpaths[1], &[DVec3::Z]);
448 }
449
450 #[test]
451 fn get_partial_covers_range_boundaries() {
452 let points = partial_fixture();
453 assert_eq!(points.get_partial(0.0..1.0), points);
454
455 let half = points.get_partial(0.0..0.5);
457 assert_eq!(half.len(), 5);
458 assert_dvec3_eq(*half.last().unwrap(), dvec3(2.25, 2.25, 2.25));
459
460 let single = points.get_partial(0.0..1.0 / 6.0);
462 assert_eq!(single.len(), 3);
463 assert_dvec3_eq(single[0], dvec3(0.0, 0.0, 0.0));
464 assert_dvec3_eq(single[1], dvec3(0.5, 0.5, 0.5));
465 assert_dvec3_eq(single[2], dvec3(1.0, 1.0, 1.0));
466
467 let exact = points.get_partial(0.0..1.0 / 3.0);
469 assert_eq!(exact.len(), 3);
470 assert_dvec3_eq(exact[2], dvec3(2.0, 2.0, 2.0));
471 }
472
473 #[test]
474 fn point_transforms_rotate_and_fit_segments() {
475 let mut points = VPointVec(vec![
476 dvec3(0.0, 0.0, 0.0),
477 dvec3(1.0, 0.0, 0.0),
478 dvec3(2.0, 2.0, 0.0),
479 ]);
480 points.rotate_on_z(PI);
481 assert_points_eq(
482 &points.0,
483 &[
484 dvec3(0.0, 0.0, 0.0),
485 dvec3(-1.0, 0.0, 0.0),
486 dvec3(-2.0, -2.0, 0.0),
487 ],
488 );
489
490 let mut scaled = VPointVec(vec![
491 dvec3(0.0, 0.0, 0.0),
492 dvec3(1.0, 0.0, 0.0),
493 dvec3(2.0, 2.0, 0.0),
494 ]);
495 scaled.put_start_and_end_on(dvec3(0.0, 0.0, 0.0), dvec3(4.0, 4.0, 0.0));
496 assert_points_eq(
497 &scaled.0,
498 &[
499 dvec3(0.0, 0.0, 0.0),
500 dvec3(2.0, 0.0, 0.0),
501 dvec3(4.0, 4.0, 0.0),
502 ],
503 );
504
505 scaled.put_start_and_end_on(dvec3(0.0, 0.0, 0.0), dvec3(-2.0, -2.0, 0.0));
506 assert_points_eq(
507 &scaled.0,
508 &[
509 dvec3(0.0, 0.0, 0.0),
510 dvec3(-1.0, 0.0, 0.0),
511 dvec3(-2.0, -2.0, 0.0),
512 ],
513 );
514 }
515
516 #[test]
517 fn aabb_covers_curve_extrema_and_degenerates() {
518 let [min, max] = VPointVec(vec![
520 dvec3(-2.0, 1.0, 0.0),
521 dvec3(0.0, -1.0, 0.0),
522 dvec3(2.0, 1.0, 0.0),
523 ])
524 .aabb();
525 assert_dvec3_eq(min, dvec3(-2.0, 0.0, 0.0));
526 assert_dvec3_eq(max, dvec3(2.0, 1.0, 0.0));
527
528 let [min, max] = VPointVec(vec![
530 dvec3(0.0, 0.0, 0.0),
531 dvec3(1.0, 1.0, 0.0),
532 dvec3(2.0, 2.0, 0.0),
533 ])
534 .aabb();
535 assert_dvec3_eq(min, dvec3(0.0, 0.0, 0.0));
536 assert_dvec3_eq(max, dvec3(2.0, 2.0, 0.0));
537
538 let [min, max] = VPointVec(vec![
540 dvec3(0.0, 0.0, 0.0),
541 dvec3(1.0, 2.0, 0.0),
542 dvec3(2.0, 0.0, 0.0),
543 dvec3(3.0, -2.0, 0.0),
544 dvec3(4.0, 0.0, 0.0),
545 ])
546 .aabb();
547 assert_dvec3_eq(min, dvec3(0.0, -1.0, 0.0));
548 assert_dvec3_eq(max, dvec3(4.0, 1.0, 0.0));
549
550 let [min, max] = VPointVec(vec![
552 dvec3(0.0, 0.0, 0.0),
553 dvec3(0.0, 2.0, 0.0),
554 dvec3(2.0, 0.0, 0.0),
555 dvec3(2.0, 0.0, 0.0),
556 dvec3(3.0, 0.0, 0.0),
557 dvec3(3.0, -2.0, 0.0),
558 dvec3(5.0, 0.0, 0.0),
559 ])
560 .aabb();
561 assert_dvec3_eq(min, dvec3(0.0, -1.0, 0.0));
562 assert_dvec3_eq(max, dvec3(5.0, 1.0, 0.0));
563
564 let [min, max] = VPointVec(vec![DVec3::ONE; 3]).aabb();
566 assert_dvec3_eq(min, DVec3::ONE);
567 assert_dvec3_eq(max, DVec3::ONE);
568
569 let [min, max] = VPointVec(vec![]).aabb();
571 assert_dvec3_eq(min, DVec3::ZERO);
572 assert_dvec3_eq(max, DVec3::ZERO);
573 }
574
575 #[test]
578 fn repro_textitem_i_flags() {
579 let points = vec![
580 dvec3(-1.1095102, 0.2, 0.0),
581 dvec3(-1.1095102, 0.24466859, 0.0),
582 dvec3(-1.1095102, 0.2893372, 0.0),
583 dvec3(-0.965936, 0.2893372, 0.0),
584 dvec3(-0.93119603, 0.3029707, 0.0),
585 dvec3(-0.8847263, 0.3212075, 0.0),
586 dvec3(-0.8847263, 0.39596543, 0.0),
587 dvec3(-0.8847263, 0.8008646, 0.0),
588 dvec3(-0.8847263, 1.2057637, 0.0),
589 dvec3(-0.8847263, 1.3013107, 0.0),
590 dvec3(-0.92327094, 1.3273722, 0.0),
591 dvec3(-0.96078646, 1.3527378, 0.0),
592 dvec3(-1.0979828, 1.3527378, 0.0),
593 dvec3(-1.0979828, 1.3974065, 0.0),
594 dvec3(-1.0979828, 1.442075, 0.0),
595 dvec3(-0.89625365, 1.4579251, 0.0),
596 dvec3(-0.6945245, 1.4737753, 0.0),
597 dvec3(-0.6945245, 0.93487036, 0.0),
598 dvec3(-0.6945245, 0.39596543, 0.0),
599 dvec3(-0.6945245, 0.32224214, 0.0),
600 dvec3(-0.65309805, 0.30372962, 0.0),
601 dvec3(-0.6208913, 0.2893372, 0.0),
602 dvec3(-0.49279544, 0.2893372, 0.0),
603 dvec3(-0.49279544, 0.24466859, 0.0),
604 dvec3(-0.49279544, 0.2, 0.0),
605 dvec3(-0.52158666, 0.2, 0.0),
606 dvec3(-0.60612535, 0.20347658, 0.0),
607 dvec3(-0.7318171, 0.20864554, 0.0),
608 dvec3(-0.79538906, 0.20864554, 0.0),
609 dvec3(-0.85056424, 0.20864554, 0.0),
610 dvec3(-0.9803795, 0.20371476, 0.0),
611 dvec3(-1.0781803, 0.2, 0.0),
612 dvec3(-1.1095102, 0.2, 0.0),
613 dvec3(-1.1095102, 0.2, 0.0),
614 dvec3(-1.1095102, 0.2, 0.0),
615 dvec3(-1.1095102, 0.2, 0.0),
616 dvec3(-0.8328531, 1.8224784, 0.0),
617 dvec3(-0.766148, 1.8224784, 0.0),
618 dvec3(-0.72442365, 1.8653458, 0.0),
619 dvec3(-0.68299717, 1.9079074, 0.0),
620 dvec3(-0.68299717, 1.9752162, 0.0),
621 dvec3(-0.68299717, 2.0446506, 0.0),
622 dvec3(-0.73126805, 2.0868876, 0.0),
623 dvec3(-0.7749074, 2.125072, 0.0),
624 dvec3(-0.8357349, 2.125072, 0.0),
625 dvec3(-0.89681745, 2.125072, 0.0),
626 dvec3(-0.9387609, 2.0879683, 0.0),
627 dvec3(-0.9855908, 2.0465417, 0.0),
628 dvec3(-0.9855908, 1.9752162, 0.0),
629 dvec3(-0.9855908, 1.9138817, 0.0),
630 dvec3(-0.95028824, 1.87183, 0.0),
631 dvec3(-0.9088573, 1.8224784, 0.0),
632 dvec3(-0.8328531, 1.8224784, 0.0),
633 ];
634 let vp = VPointVec(points);
635 let flags = vp.get_closepath_flags();
636 assert!(
637 flags.iter().all(|f| *f),
638 "some segments flagged open: {flags:?}"
639 );
640 }
641}