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: NoAttributes> = PathWalker::new(start, tolerance, pattern);
58 for evt: Event, …> 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: usize = 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}
512