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 | |
43 | use crate::geom::{CubicBezierSegment, LineSegment, QuadraticBezierSegment}; |
44 | use crate::math::*; |
45 | use crate::path::builder::*; |
46 | use crate::path::{Attributes, EndpointId, PathEvent}; |
47 | |
48 | use core::ops::Range; |
49 | |
50 | use alloc::vec::Vec; |
51 | |
52 | /// Walks along the path staring at offset `start` and applies a `Pattern`. |
53 | pub fn walk_along_path<Iter>(path: Iter, start: f32, tolerance: f32, pattern: &mut dyn Pattern) |
54 | where |
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)] |
67 | pub 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>`. |
84 | pub 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. |
104 | pub 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 | |
121 | impl<'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 | |
306 | impl<'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 | |
343 | impl<'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. |
352 | pub 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 | |
359 | impl<Cb> Pattern for RegularPattern<Cb> |
360 | where |
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. |
376 | pub 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 | |
385 | impl<'l, Cb> Pattern for RepeatedPattern<'l, Cb> |
386 | where |
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 | |
400 | impl<Cb> Pattern for Cb |
401 | where |
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 ] |
411 | fn 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 ] |
450 | fn 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 ] |
483 | fn 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 impl Fn(WalkerEvent<'_>) -> … = &mut |_event: WalkerEvent| -> Option<f32> { panic!() }; |
487 | let mut walker: NoAttributes> = PathWalker::new(start:10.0, tolerance:0.1, pattern:cb); |
488 | |
489 | walker.begin(at:point(x:0.0, y:0.0)); |
490 | walker.line_to(point(x:5.0, y:0.0)); |
491 | walker.end(close:false); |
492 | } |
493 | |
494 | #[test ] |
495 | fn walk_abort_early() { |
496 | let mut callback_counter: i32 = 0; |
497 | let mut pattern: RegularPattern …> = RegularPattern { |
498 | interval: 3.0, |
499 | callback: |_event: WalkerEvent| { |
500 | callback_counter += 1; |
501 | false |
502 | }, |
503 | }; |
504 | |
505 | let mut walker: NoAttributes> = PathWalker::new(start:1.0, tolerance:0.1, &mut pattern); |
506 | |
507 | walker.begin(at:point(x:0.0, y:0.0)); |
508 | walker.line_to(point(x:100.0, y:0.0)); |
509 | |
510 | assert_eq!(callback_counter, 1); |
511 | } |
512 | |