rive_rs/math/
bezier.rs

1// Copyright 2021 The Fuchsia Authors. All rights reserved.
2// Use of this source code is governed by a BSD-style license that can be
3// found in the LICENSE file.
4
5use std::mem;
6
7use smallvec::SmallVec;
8
9use crate::math;
10
11const TOLERANCE: f32 = 0.005;
12
13fn angle(origin: math::Vec, p0: math::Vec, p1: math::Vec) -> f32 {
14    let d0 = p0 - origin;
15    let d1 = p1 - origin;
16
17    let cross = d0.x * d1.y - d0.y * d1.x;
18    let dot = d0.x * d1.x + d0.y * d1.y;
19
20    cross.atan2(dot)
21}
22
23fn line_segment_intersection(
24    segment0: [math::Vec; 2],
25    segment1: [math::Vec; 2],
26) -> Option<math::Vec> {
27    let d10 = segment0[1] - segment0[0];
28    let d32 = segment1[1] - segment1[0];
29
30    let denom = d10.x * d32.y - d32.x * d10.y;
31    if denom == 0.0 {
32        return None;
33    }
34
35    let denom_is_pos = denom > 0.0;
36
37    let d02 = segment0[0] - segment1[0];
38    let s_numer = d10.x * d02.y - d10.y * d02.x;
39    if (s_numer < 0.0) == denom_is_pos {
40        return None;
41    }
42
43    let t_numer = d32.x * d02.y - d32.y * d02.x;
44    if (t_numer < 0.0) == denom_is_pos {
45        return None;
46    }
47
48    if (s_numer > denom) == denom_is_pos || (t_numer > denom) == denom_is_pos {
49        return None;
50    }
51
52    let t = t_numer / denom;
53    Some(segment0[0] + d10 * t)
54}
55
56fn align(point: math::Vec, line: [math::Vec; 2]) -> math::Vec {
57    let angle = -(line[1].y - line[0].y).atan2(line[1].x - line[0].x);
58
59    math::Vec::new(
60        (point.x - line[0].x) * angle.cos() - (point.y - line[0].y) * angle.sin(),
61        (point.x - line[0].x) * angle.sin() + (point.y - line[0].y) * angle.cos(),
62    )
63}
64
65fn approx_eq(p0: math::Vec, p1: math::Vec) -> bool {
66    (p0.x - p1.x).abs() <= TOLERANCE && (p0.y - p1.y).abs() <= TOLERANCE
67}
68
69fn left_different(points: &[math::Vec]) -> [math::Vec; 2] {
70    points
71        .array_windows()
72        .find_map(|&[p0, p1]| (!approx_eq(p0, p1)).then_some([p0, p1]))
73        .expect("Bezier cannot be a point")
74}
75
76pub fn right_different(points: &[math::Vec]) -> [math::Vec; 2] {
77    points
78        .array_windows()
79        .rev()
80        .find_map(|&[p0, p1]| (!approx_eq(p0, p1)).then_some([p0, p1]))
81        .expect("Bezier cannot be a point")
82}
83
84fn normal(p0: math::Vec, p1: math::Vec, c: f32) -> Option<math::Vec> {
85    let d = (p1 - p0) * c;
86    if d.x.abs() == 0.0 && d.y.abs() == 0.0 {
87        return None;
88    }
89
90    let q = (d.x * d.x + d.y * d.y).sqrt();
91
92    Some(math::Vec::new(-d.y / q, d.x / q))
93}
94
95fn normal_left(points: &[math::Vec]) -> math::Vec {
96    let c = points.len() as f32 - 1.0;
97    let [p0, p1] = left_different(points);
98
99    normal(p0, p1, c).expect("Bezier cannot be a point")
100}
101
102fn normal_right(points: &[math::Vec]) -> math::Vec {
103    let c = points.len() as f32 - 1.0;
104    let [p0, p1] = right_different(points);
105
106    normal(p0, p1, c).expect("Bezier cannot be a point")
107}
108
109fn derive(points: &[math::Vec]) -> SmallVec<[math::Vec; 3]> {
110    let mut derived = SmallVec::new();
111
112    for &[p0, p1] in points.array_windows() {
113        derived.push((p1 - p0) * (points.len() - 1) as f32);
114    }
115
116    derived
117}
118
119fn derive_left(points: &[math::Vec]) -> math::Vec {
120    let [p0, p1] = left_different(points);
121    (p1 - p0) * (points.len() - 1) as f32
122}
123
124fn derive_right(points: &[math::Vec]) -> math::Vec {
125    let [p0, p1] = right_different(points);
126    (p1 - p0) * (points.len() - 1) as f32
127}
128
129fn droots(vals: &[f32]) -> SmallVec<[f32; 2]> {
130    let mut droots = SmallVec::new();
131
132    match *vals {
133        [a, b] => {
134            if a != b {
135                droots.push(a / (a - b));
136            }
137        }
138        [a, b, c] => {
139            let d = a - 2.0 * b + c;
140            if d != 0.0 {
141                let m1 = -(b * b - a * c).sqrt();
142                let m2 = -a + b;
143
144                droots.push(-(m1 + m2) / d);
145                droots.push(-(-m1 + m2) / d);
146            } else if b != c && d == 0.0 {
147                droots.push((2.0 * b - c) / (2.0 * (b - c)));
148            }
149        }
150        _ => (),
151    }
152
153    droots
154}
155
156fn hull(points: &[math::Vec; 4], t: f32) -> SmallVec<[math::Vec; 10]> {
157    let mut hull = SmallVec::new();
158    let mut points = SmallVec::from(*points);
159    let mut next_points = SmallVec::new();
160
161    hull.extend(points.iter().copied());
162
163    while points.len() > 1 {
164        next_points.clear();
165
166        for &[p0, p1] in points.array_windows() {
167            let point = p0.lerp(p1, t);
168            hull.push(point);
169            next_points.push(point);
170        }
171
172        mem::swap(&mut points, &mut next_points);
173    }
174
175    hull
176}
177
178fn split(points: &[math::Vec; 4], t0: f32, t1: f32) -> [math::Vec; 4] {
179    let hull0 = hull(points, t0);
180    let right = [hull0[9], hull0[8], hull0[6], hull0[3]];
181
182    let t1 = (t1 - t0) / (1.0 - t0);
183    let hull1 = hull(&right, t1);
184
185    [hull1[0], hull1[4], hull1[7], hull1[9]]
186}
187
188fn line_intersection(
189    p0: math::Vec,
190    p1: math::Vec,
191    p2: math::Vec,
192    p3: math::Vec,
193) -> Option<math::Vec> {
194    let nx =
195        (p0.x * p1.y - p0.y * p1.x) * (p2.x - p3.x) - (p0.x - p1.x) * (p2.x * p3.y - p2.y * p3.x);
196    let ny =
197        (p0.x * p1.y - p0.y * p1.x) * (p2.y - p3.y) - (p0.y - p1.y) * (p2.x * p3.y - p2.y * p3.x);
198    let d = (p0.x - p1.x) * (p2.y - p3.y) - (p0.y - p1.y) * (p2.x - p3.x);
199
200    if d == 0.0 {
201        return None;
202    }
203
204    Some(math::Vec::new(nx / d, ny / d))
205}
206
207fn scale(points: &[math::Vec; 4], dist: f32) -> Option<[math::Vec; 4]> {
208    if dist == 0.0 {
209        return Some(*points);
210    }
211
212    let normals = [normal_left(points), normal_right(points)];
213    let offset = [points[0] + normals[0] * 10.0, points[3] + normals[1] * 10.0];
214    let origin = line_intersection(offset[0], points[0], offset[1], points[3])?;
215
216    let mut new_points = [math::Vec::default(); 4];
217
218    new_points[0] = points[0] + normals[0] * dist;
219    new_points[3] = points[3] + normals[1] * dist;
220
221    new_points[1] =
222        line_intersection(new_points[0], new_points[0] + derive_left(points), origin, points[1])?;
223    new_points[2] =
224        line_intersection(new_points[3], new_points[3] + derive_right(points), origin, points[2])?;
225
226    Some(new_points)
227}
228
229#[derive(Clone, Debug)]
230pub enum Bezier {
231    Line([math::Vec; 2]),
232    Cubic([math::Vec; 4]),
233}
234
235impl Bezier {
236    fn is_linear(&self) -> bool {
237        match self {
238            Self::Line(_) => true,
239            Self::Cubic(points) => points
240                .iter()
241                .copied()
242                .all(|point| align(point, [points[0], points[3]]).y.abs() < TOLERANCE),
243        }
244    }
245
246    fn is_simple(&self) -> bool {
247        match self {
248            Self::Line(_) => true,
249            Self::Cubic(points) => {
250                let a0 = angle(points[0], points[3], points[1]);
251                let a1 = angle(points[0], points[3], points[2]);
252
253                if (a0 > 0.0 && a1 < 0.0 || a0 < 0.0 && a1 > 0.0) && (a1 - a0).abs() >= TOLERANCE {
254                    return false;
255                }
256
257                let n0 = normal(points[0], points[1], 3.0);
258                let n1 = normal(points[2], points[3], 3.0);
259
260                if let (Some(n0), Some(n1)) = (n0, n1) {
261                    let s = n0.x * n1.x + n0.y * n1.y;
262
263                    s.clamp(-1.0, 1.0).acos().abs() < std::f32::consts::PI / 3.0
264                } else {
265                    false
266                }
267            }
268        }
269    }
270
271    pub fn points(&self) -> &[math::Vec] {
272        match self {
273            Self::Line(points) => points,
274            Self::Cubic(points) => points,
275        }
276    }
277
278    fn points_mut(&mut self) -> &mut [math::Vec] {
279        match self {
280            Self::Line(points) => points,
281            Self::Cubic(points) => points,
282        }
283    }
284
285    pub fn left_different(&self) -> [math::Vec; 2] {
286        left_different(self.points())
287    }
288
289    pub fn right_different(&self) -> [math::Vec; 2] {
290        right_different(self.points())
291    }
292
293    pub fn normalize(&self) -> Option<Self> {
294        match *self {
295            Self::Line([p0, p1]) => {
296                if !approx_eq(p0, p1) {
297                    Some(self.clone())
298                } else {
299                    None
300                }
301            }
302            Self::Cubic([p0, p1, p2, p3]) => {
303                if approx_eq(p0, p1) && approx_eq(p2, p3) {
304                    Self::Line([p0, p3]).normalize()
305                } else {
306                    Some(self.clone())
307                }
308            }
309        }
310    }
311
312    fn as_segment(&self) -> [math::Vec; 2] {
313        match self {
314            Self::Line(points) => *points,
315            Self::Cubic([p0, _, _, p3]) => [*p0, *p3],
316        }
317    }
318
319    pub fn intersect(&self, other: &Self) -> bool {
320        line_segment_intersection(self.as_segment(), other.as_segment()).is_some()
321    }
322
323    fn map(&self, mut f: impl FnMut(math::Vec) -> math::Vec) -> Self {
324        let mut clone = self.clone();
325
326        for point in clone.points_mut() {
327            *point = f(*point);
328        }
329
330        clone
331    }
332
333    pub fn rev(&self) -> Self {
334        match self {
335            Self::Line([p0, p1]) => Self::Line([*p1, *p0]),
336            Self::Cubic([p0, p1, p2, p3]) => Self::Cubic([*p3, *p2, *p1, *p0]),
337        }
338    }
339
340    fn extrema(&self) -> SmallVec<[f32; 8]> {
341        let mut extrema: SmallVec<[f32; 8]> = SmallVec::new();
342
343        let is_unit = |t: f32| (t.is_finite() && (0.0..=1.0).contains(&t)).then(|| t.abs());
344
345        if let Self::Cubic(points) = self {
346            let d1 = derive(points);
347            let d2 = derive(&d1);
348
349            let d1x: SmallVec<[_; 3]> = d1.iter().map(|p| p.x).collect();
350            let d2x: SmallVec<[_; 2]> = d2.iter().map(|p| p.x).collect();
351            let d1y: SmallVec<[_; 3]> = d1.iter().map(|p| p.y).collect();
352            let d2y: SmallVec<[_; 2]> = d2.iter().map(|p| p.y).collect();
353
354            extrema.extend(droots(&d1x).into_iter().filter_map(is_unit));
355            extrema.extend(droots(&d2x).into_iter().filter_map(is_unit));
356            extrema.extend(droots(&d1y).into_iter().filter_map(is_unit));
357            extrema.extend(droots(&d2y).into_iter().filter_map(is_unit));
358        }
359
360        extrema.sort_by(|&a, b| a.partial_cmp(b).unwrap());
361        extrema.dedup();
362
363        extrema
364    }
365
366    fn reduce(&self) -> SmallVec<[Self; 16]> {
367        const STEP: f32 = 0.01;
368
369        let mut extrema = self.extrema();
370
371        if extrema.first().map(|&e| e <= STEP) != Some(true) {
372            extrema.insert(0, 0.0);
373        }
374
375        if extrema.last().map(|&e| (e - 1.0).abs() <= STEP) != Some(true) {
376            extrema.push(1.0);
377        }
378
379        let mut pass0: SmallVec<[_; 8]> = SmallVec::new();
380        let mut pass1 = SmallVec::new();
381
382        if let Self::Cubic(points) = self {
383            for &[t0, t1] in extrema.array_windows() {
384                pass0.push(split(points, t0, t1));
385            }
386
387            'outer: for segment_pass0 in pass0 {
388                let mut t0 = 0.0;
389                let mut t1 = 0.0;
390
391                while t1 <= 1.0 - TOLERANCE {
392                    t1 = t0 + STEP;
393                    while t1 <= 1.0 + STEP - TOLERANCE {
394                        let segment = split(&segment_pass0, t0, t1);
395                        let bezier = Self::Cubic(segment);
396
397                        if !bezier.is_simple() {
398                            t1 -= STEP;
399
400                            if (t1 - t0).abs() < STEP {
401                                if let Some(normalized) = Self::Cubic(segment_pass0).normalize() {
402                                    if t0 == 0.0 {
403                                        pass1.push(normalized);
404                                    }
405                                }
406                                continue 'outer;
407                            }
408
409                            pass1.push(Self::Cubic(split(&segment_pass0, t0, t1)));
410
411                            t0 = t1;
412                            break;
413                        }
414
415                        t1 += STEP;
416                    }
417                }
418
419                if t0 < 1.0 {
420                    pass1.push(Self::Cubic(split(&segment_pass0, t0, 1.0)));
421                }
422            }
423        }
424
425        if pass1.is_empty() {
426            pass1.push(self.clone());
427        }
428
429        pass1
430    }
431
432    pub fn offset(&self, dist: f32) -> SmallVec<[Self; 16]> {
433        if dist.is_sign_negative() {
434            return self.rev().offset(-dist);
435        }
436
437        let mut curves = SmallVec::new();
438
439        if self.is_linear() {
440            let normal = normal_left(self.points());
441
442            curves.push(
443                self.map(|point| {
444                    math::Vec::new(point.x + dist * normal.x, point.y + dist * normal.y)
445                }),
446            );
447
448            return curves;
449        }
450        self.reduce()
451            .iter()
452            .filter_map(|bezier| {
453                bezier
454                    .normalize()
455                    .map(|bezier| {
456                        if bezier.is_linear() {
457                            bezier.offset(dist)[0].clone()
458                        } else if let Self::Cubic(points) = bezier {
459                            if let Some(scaled) = scale(&points, dist) {
460                                Self::Cubic(scaled)
461                            } else {
462                                Self::Line([points[0], points[3]]).offset(dist)[0].clone()
463                            }
464                        } else {
465                            unreachable!()
466                        }
467                    })
468                    .as_ref()
469                    .and_then(Bezier::normalize)
470            })
471            .collect()
472    }
473}
474
475#[cfg(test)]
476mod tests {
477    use super::*;
478
479    macro_rules! assert_approx_eq {
480        ($a:expr, $b:expr) => {{
481            assert!(
482                ($a - $b).abs() < TOLERANCE,
483                "assertion failed: `(left !== right)` \
484                 (left: `{:?}`, right: `{:?}`)",
485                $a,
486                $b,
487            );
488        }};
489    }
490
491    #[test]
492    fn offset_line() {
493        let line = Bezier::Line([math::Vec::new(-0.5, -0.5), math::Vec::new(0.5, 0.5)]);
494
495        let pos_offset = line.offset(2.0f32.sqrt() / 2.0);
496        assert_eq!(pos_offset.len(), 1);
497        assert_eq!(pos_offset[0].points().len(), 2);
498        assert_approx_eq!(pos_offset[0].points()[0].x, -1.0);
499        assert_approx_eq!(pos_offset[0].points()[0].y, 0.0);
500        assert_approx_eq!(pos_offset[0].points()[1].x, 0.0);
501        assert_approx_eq!(pos_offset[0].points()[1].y, 1.0);
502
503        let neg_offset = line.offset(-(2.0f32.sqrt()) / 2.0);
504        assert_eq!(neg_offset.len(), 1);
505        assert_eq!(neg_offset[0].points().len(), 2);
506        assert_approx_eq!(neg_offset[0].points()[1].x, 0.0);
507        assert_approx_eq!(neg_offset[0].points()[1].y, -1.0);
508        assert_approx_eq!(neg_offset[0].points()[0].x, 1.0);
509        assert_approx_eq!(neg_offset[0].points()[0].y, 0.0);
510    }
511}
rive_rs/math/bezier.rs

rive_rs/math/
bezier.rs
