lyon_algorithms/
walk.rs

1//! Move at a defined speed along a path.
2//!
3//! # Path walking
4//!
5//! ## Overview
6//!
7//! In principle, walking a path is similar to iterating over it,
8//! but instead of going from receiving path segments (of varying
9//! sizes), the path walker makes it possible to advance by a certain
10//! distance along the path.
11//!
12//! ## Example
13//!
14//! ```
15//! use lyon_algorithms::walk::{RegularPattern, walk_along_path, WalkerEvent};
16//! use lyon_algorithms::path::PathSlice;
17//! use lyon_algorithms::path::iterator::*;
18//! use lyon_algorithms::path::math::Point;
19//!
20//! fn dots_along_path(path: PathSlice, dots: &mut Vec<Point>) {
21//!     let mut pattern = RegularPattern {
22//!         callback: &mut |event: WalkerEvent| {
23//!             dots.push(event.position);
24//!             true // Return true to continue walking the path.
25//!         },
26//!         // Invoke the callback above at a regular interval of 3 units.
27//!         interval: 3.0,
28//!     };
29//!
30//!     let tolerance = 0.1; // The path flattening tolerance.
31//!     let start_offset = 0.0; // Start walking at the beginning of the path.
32//!     walk_along_path(
33//!         path.iter(),
34//!         start_offset,
35//!         tolerance,
36//!         &mut pattern
37//!     );
38//! }
39//!
40//! ```
41//!
42
43use crate::geom::{CubicBezierSegment, LineSegment, QuadraticBezierSegment};
44use crate::math::*;
45use crate::path::builder::*;
46use crate::path::{Attributes, EndpointId, PathEvent};
47
48use core::ops::Range;
49
50use alloc::vec::Vec;
51
52/// Walks along the path staring at offset `start` and applies a `Pattern`.
53pub fn walk_along_path<Iter>(path: Iter, start: f32, tolerance: f32, pattern: &mut dyn Pattern)
54where
55    Iter: IntoIterator<Item = PathEvent>,
56{
57    let mut walker = PathWalker::new(start, tolerance, pattern);
58    for evt in path {
59        walker.path_event(evt);
60        if walker.inner().done {
61            return;
62        }
63    }
64}
65
66#[derive(Debug)]
67pub struct WalkerEvent<'l> {
68    pub position: Point,
69    pub tangent: Vector,
70    pub distance: f32,
71    pub attributes: Attributes<'l>,
72}
73
74/// Types implementing the `Pattern` can be used to walk along a path
75/// at constant speed.
76///
77/// At each step, the pattern receives the position, tangent and already
78/// traversed distance along the path and returns the distance until the
79/// next step.
80///
81/// See the `RegularPattern` and `RepeatedPattern` implementations.
82/// This trait is also implemented for all functions/closures with signature
83/// `FnMut(WalkerEvent) -> Option<f32>`.
84pub trait Pattern {
85    /// This method is invoked at each step along the path.
86    ///
87    /// If this method returns None, path walking stops. Otherwise the returned
88    /// value is the distance along the path to the next element in the pattern.
89    fn next(&mut self, event: WalkerEvent) -> Option<f32>;
90
91    /// Invoked at the start each sub-path.
92    ///
93    /// Takes the leftover requested distance from the previous sub-path path,
94    /// if any.
95    ///
96    /// If this method returns None, path walking stops. Otherwise the returned
97    /// value is the distance along the path to the next element in the pattern.
98    fn begin(&mut self, distance: f32) -> Option<f32> {
99        Some(distance)
100    }
101}
102
103/// A helper struct to walk along a flattened path using a builder API.
104pub struct PathWalker<'l> {
105    prev: Point,
106    tolerance: f32,
107    advancement: f32,
108    leftover: f32,
109    next_distance: f32,
110    first: Point,
111    need_moveto: bool,
112    done: bool,
113    prev_attributes: Vec<f32>,
114    attribute_buffer: Vec<f32>,
115    first_attributes: Vec<f32>,
116    num_attributes: usize,
117
118    pattern: &'l mut dyn Pattern,
119}
120
121impl<'l> PathWalker<'l> {
122    pub fn new(start: f32, tolerance: f32, pattern: &'l mut dyn Pattern) -> NoAttributes<Self> {
123        NoAttributes::wrap(Self::with_attributes(0, start, tolerance, pattern))
124    }
125
126    pub fn with_attributes(
127        num_attributes: usize,
128        start: f32,
129        tolerance: f32,
130        pattern: &'l mut dyn Pattern,
131    ) -> Self {
132        let start = f32::max(start, 0.0);
133        PathWalker {
134            prev: point(0.0, 0.0),
135            first: point(0.0, 0.0),
136            tolerance,
137            advancement: 0.0,
138            leftover: 0.0,
139            next_distance: start,
140            need_moveto: true,
141            done: false,
142            pattern,
143            prev_attributes: alloc::vec![0.0; num_attributes],
144            attribute_buffer: alloc::vec![0.0; num_attributes],
145            first_attributes: alloc::vec![0.0; num_attributes],
146            num_attributes,
147        }
148    }
149
150    fn edge(
151        &mut self,
152        to: Point,
153        t: Range<f32>,
154        attributes: Attributes,
155        pos_cb: &dyn Fn(f32) -> (Point, Vector),
156    ) {
157        debug_assert!(!self.need_moveto);
158
159        let v = to - self.prev;
160        let d = v.length();
161
162        if d < 1e-5 {
163            return;
164        }
165
166        let inv_d = 1.0 / d;
167
168        let mut distance = self.leftover + d;
169        let mut x = 0.0;
170        while distance >= self.next_distance {
171            if self.num_attributes > 0 {
172                let t2 = t.end * self.next_distance / distance;
173                for i in 0..self.num_attributes {
174                    self.attribute_buffer[i] =
175                        self.prev_attributes[i] * (1.0 - t2) + attributes[i] * t2;
176                }
177            }
178            x += (self.next_distance - self.leftover) * inv_d;
179            let (position, tangent) = pos_cb(x);
180            self.prev = position;
181            self.leftover = 0.0;
182            self.advancement += self.next_distance;
183            distance -= self.next_distance;
184
185            let event = WalkerEvent {
186                position,
187                tangent,
188                distance: self.advancement,
189                attributes: &self.attribute_buffer[..],
190            };
191            if let Some(distance) = self.pattern.next(event) {
192                self.next_distance = distance;
193            } else {
194                self.done = true;
195                return;
196            }
197        }
198
199        self.prev = to;
200        self.leftover = distance;
201    }
202
203    pub fn num_attributes(&self) -> usize {
204        self.num_attributes
205    }
206
207    pub fn begin(&mut self, to: Point, attributes: Attributes) -> EndpointId {
208        self.need_moveto = false;
209        self.first = to;
210        self.prev = to;
211
212        if let Some(distance) = self.pattern.begin(self.next_distance) {
213            self.next_distance = distance;
214        } else {
215            self.done = true;
216        }
217
218        self.prev_attributes.copy_from_slice(attributes);
219        self.first_attributes.copy_from_slice(attributes);
220
221        EndpointId::INVALID
222    }
223
224    pub fn line_to(&mut self, to: Point, attributes: Attributes) -> EndpointId {
225        debug_assert!(!self.need_moveto);
226
227        let from = self.prev;
228        let tangent = (to - from).normalize();
229        self.edge(to, 0.0..1.0, attributes, &|x| {
230            (LineSegment { from, to }.sample(x), tangent)
231        });
232
233        self.prev_attributes.copy_from_slice(attributes);
234
235        EndpointId::INVALID
236    }
237
238    pub fn end(&mut self, close: bool) {
239        if close {
240            let attributes = core::mem::take(&mut self.first_attributes);
241            let first = self.first;
242            let from = self.prev;
243            let tangent = (first - from).normalize();
244            self.edge(first, 0.0..1.0, &attributes, &|x| {
245                (LineSegment { from, to: first }.sample(x), tangent)
246            });
247            self.first_attributes = attributes;
248            self.need_moveto = true;
249        }
250    }
251
252    pub fn quadratic_bezier_to(
253        &mut self,
254        ctrl: Point,
255        to: Point,
256        attributes: Attributes,
257    ) -> EndpointId {
258        let curve = QuadraticBezierSegment {
259            from: self.prev,
260            ctrl,
261            to,
262        };
263        curve.for_each_flattened_with_t(self.tolerance, &mut |line, t| {
264            if !self.done {
265                self.edge(line.to, t.clone(), attributes, &|x| {
266                    let t2 = t.start + x * (t.end - t.start);
267                    (curve.sample(t2), curve.derivative(t2).normalize())
268                });
269            }
270        });
271
272        self.prev_attributes.copy_from_slice(attributes);
273
274        EndpointId::INVALID
275    }
276
277    pub fn cubic_bezier_to(
278        &mut self,
279        ctrl1: Point,
280        ctrl2: Point,
281        to: Point,
282        attributes: Attributes,
283    ) -> EndpointId {
284        let curve = CubicBezierSegment {
285            from: self.prev,
286            ctrl1,
287            ctrl2,
288            to,
289        };
290
291        curve.for_each_flattened_with_t(self.tolerance, &mut |line, t| {
292            if !self.done {
293                self.edge(line.to, t.clone(), attributes, &|x| {
294                    let t2 = t.start + x * (t.end - t.start);
295                    (curve.sample(t2), curve.derivative(t2).normalize())
296                });
297            }
298        });
299
300        self.prev_attributes.copy_from_slice(attributes);
301
302        EndpointId::INVALID
303    }
304}
305
306impl<'l> PathBuilder for PathWalker<'l> {
307    fn num_attributes(&self) -> usize {
308        self.num_attributes
309    }
310
311    fn begin(&mut self, to: Point, attributes: Attributes) -> EndpointId {
312        self.begin(to, attributes)
313    }
314
315    fn end(&mut self, close: bool) {
316        self.end(close)
317    }
318
319    fn line_to(&mut self, to: Point, attributes: Attributes) -> EndpointId {
320        self.line_to(to, attributes)
321    }
322
323    fn quadratic_bezier_to(
324        &mut self,
325        ctrl: Point,
326        to: Point,
327        attributes: Attributes,
328    ) -> EndpointId {
329        self.quadratic_bezier_to(ctrl, to, attributes)
330    }
331
332    fn cubic_bezier_to(
333        &mut self,
334        ctrl1: Point,
335        ctrl2: Point,
336        to: Point,
337        attributes: Attributes,
338    ) -> EndpointId {
339        self.cubic_bezier_to(ctrl1, ctrl2, to, attributes)
340    }
341}
342
343impl<'l> Build for PathWalker<'l> {
344    type PathType = ();
345
346    fn build(self) {}
347}
348
349/// A simple pattern that invokes a callback at regular intervals.
350///
351/// If the callback returns false, path walking stops.
352pub struct RegularPattern<Cb> {
353    /// The function to call at each step.
354    pub callback: Cb,
355    /// A constant interval between each step.
356    pub interval: f32,
357}
358
359impl<Cb> Pattern for RegularPattern<Cb>
360where
361    Cb: FnMut(WalkerEvent) -> bool,
362{
363    #[inline]
364    fn next(&mut self, event: WalkerEvent) -> Option<f32> {
365        if !(self.callback)(event) {
366            return None;
367        }
368        Some(self.interval)
369    }
370}
371
372/// A pattern that invokes a callback at a repeated sequence of
373/// constant intervals.
374///
375/// If the callback returns false, path walking stops.
376pub struct RepeatedPattern<'l, Cb> {
377    /// The function to call at each step.
378    pub callback: Cb,
379    /// The repeated interval sequence.
380    pub intervals: &'l [f32],
381    /// The index of the next interval in the sequence.
382    pub index: usize,
383}
384
385impl<'l, Cb> Pattern for RepeatedPattern<'l, Cb>
386where
387    Cb: FnMut(WalkerEvent) -> bool,
388{
389    #[inline]
390    fn next(&mut self, event: WalkerEvent) -> Option<f32> {
391        if !(self.callback)(event) {
392            return None;
393        }
394        let idx = self.index % self.intervals.len();
395        self.index += 1;
396        Some(self.intervals[idx])
397    }
398}
399
400impl<Cb> Pattern for Cb
401where
402    Cb: FnMut(WalkerEvent) -> Option<f32>,
403{
404    #[inline]
405    fn next(&mut self, event: WalkerEvent) -> Option<f32> {
406        (self)(event)
407    }
408}
409
410#[test]
411fn walk_square() {
412    let expected = [
413        (point(0.0, 0.0), vector(1.0, 0.0), 0.0),
414        (point(2.0, 0.0), vector(1.0, 0.0), 2.0),
415        (point(4.0, 0.0), vector(1.0, 0.0), 4.0),
416        (point(6.0, 0.0), vector(1.0, 0.0), 6.0),
417        (point(6.0, 2.0), vector(0.0, 1.0), 8.0),
418        (point(6.0, 4.0), vector(0.0, 1.0), 10.0),
419        (point(6.0, 6.0), vector(0.0, 1.0), 12.0),
420        (point(4.0, 6.0), vector(-1.0, 0.0), 14.0),
421        (point(2.0, 6.0), vector(-1.0, 0.0), 16.0),
422        (point(0.0, 6.0), vector(-1.0, 0.0), 18.0),
423        (point(0.0, 4.0), vector(0.0, -1.0), 20.0),
424        (point(0.0, 2.0), vector(0.0, -1.0), 22.0),
425        (point(0.0, 0.0), vector(0.0, -1.0), 24.0),
426    ];
427
428    let mut i = 0;
429    let mut pattern = RegularPattern {
430        interval: 2.0,
431        callback: |event: WalkerEvent| {
432            assert!((event.position - expected[i].0).length() < 0.000001);
433            assert_eq!(event.tangent, expected[i].1);
434            assert_eq!(event.distance, expected[i].2);
435            i += 1;
436            true
437        },
438    };
439
440    let mut walker = PathWalker::new(0.0, 0.1, &mut pattern);
441
442    walker.begin(point(0.0, 0.0));
443    walker.line_to(point(6.0, 0.0));
444    walker.line_to(point(6.0, 6.0));
445    walker.line_to(point(0.0, 6.0));
446    walker.close();
447}
448
449#[test]
450fn walk_with_leftover() {
451    let expected = [
452        (point(1.0, 0.0), vector(1.0, 0.0), 1.0),
453        (point(4.0, 0.0), vector(1.0, 0.0), 4.0),
454        (point(5.0, 2.0), vector(0.0, 1.0), 7.0),
455        (point(5.0, 5.0), vector(0.0, 1.0), 10.0),
456        (point(2.0, 5.0), vector(-1.0, 0.0), 13.0),
457        (point(0.0, 4.0), vector(0.0, -1.0), 16.0),
458        (point(0.0, 1.0), vector(0.0, -1.0), 19.0),
459    ];
460
461    let mut i = 0;
462    let mut pattern = RegularPattern {
463        interval: 3.0,
464        callback: |event: WalkerEvent| {
465            assert!((event.position - expected[i].0).length() < 0.000001);
466            assert_eq!(event.tangent, expected[i].1);
467            assert_eq!(event.distance, expected[i].2);
468            i += 1;
469            true
470        },
471    };
472
473    let mut walker = PathWalker::new(1.0, 0.1, &mut pattern);
474
475    walker.begin(point(0.0, 0.0));
476    walker.line_to(point(5.0, 0.0));
477    walker.line_to(point(5.0, 5.0));
478    walker.line_to(point(0.0, 5.0));
479    walker.close();
480}
481
482#[test]
483fn walk_starting_after() {
484    // With a starting distance that is greater than the path, the
485    // callback should never be called.
486    let cb = &mut |_event: WalkerEvent| -> Option<f32> { panic!() };
487    let mut walker = PathWalker::new(10.0, 0.1, cb);
488
489    walker.begin(point(0.0, 0.0));
490    walker.line_to(point(5.0, 0.0));
491    walker.end(false);
492}
493
494#[test]
495fn walk_abort_early() {
496    let mut callback_counter = 0;
497    let mut pattern = RegularPattern {
498        interval: 3.0,
499        callback: |_event: WalkerEvent| {
500            callback_counter += 1;
501            false
502        },
503    };
504
505    let mut walker = PathWalker::new(1.0, 0.1, &mut pattern);
506
507    walker.begin(point(0.0, 0.0));
508    walker.line_to(point(100.0, 0.0));
509
510    assert_eq!(callback_counter, 1);
511}
lyon_algorithms/walk.rs

lyon_algorithms/
walk.rs
