1//! Perform cached measurements and split operations on a path.
2//!
3use crate::geom::{CubicBezierSegment, LineSegment, QuadraticBezierSegment, Segment};
4use crate::math::*;
5use crate::path::{
6 builder::PathBuilder, AttributeStore, Attributes, EndpointId, IdEvent, Path, PathSlice,
7 PositionStore,
8};
9use core::ops::Range;
10
11use alloc::vec::Vec;
12
13/// Whether to measure real or normalized (between 0 and 1) distances.
14#[derive(Copy, Clone, Debug, PartialEq, Eq, Hash)]
15pub enum SampleType {
16 Distance,
17 Normalized,
18}
19
20type EndpointPair = (EndpointId, EndpointId);
21
22enum SegmentWrapper {
23 Empty,
24 Line(LineSegment<f32>, EndpointPair),
25 Quadratic(QuadraticBezierSegment<f32>, EndpointPair),
26 Cubic(CubicBezierSegment<f32>, EndpointPair),
27}
28
29impl SegmentWrapper {
30 fn split(&self, range: Range<f32>) -> Self {
31 match self {
32 Self::Empty => Self::Empty,
33 Self::Line(segment: &LineSegment, pair: &(EndpointId, EndpointId)) => Self::Line(segment.split_range(range), *pair),
34 Self::Quadratic(segment: &QuadraticBezierSegment, pair: &(EndpointId, EndpointId)) => Self::Quadratic(segment.split_range(range), *pair),
35 Self::Cubic(segment: &CubicBezierSegment, pair: &(EndpointId, EndpointId)) => Self::Cubic(segment.split_range(range), *pair),
36 }
37 }
38}
39
40struct Edge {
41 // distance from the beginning of the path
42 distance: f32,
43 // which segment this edge is on
44 index: usize,
45 // t-value of the endpoint on the segment
46 t: f32,
47}
48
49/// The result of sampling a path.
50#[derive(PartialEq, Debug)]
51pub struct PathSample<'l> {
52 position: Point,
53 tangent: Vector,
54 attributes: Attributes<'l>,
55}
56
57impl<'l> PathSample<'l> {
58 #[inline]
59 pub fn position(&self) -> Point {
60 self.position
61 }
62
63 #[inline]
64 pub fn tangent(&self) -> Vector {
65 self.tangent
66 }
67
68 // Takes &mut self to allow interpolating attributes lazily (like the stroke tessellator) without changing
69 // the API.
70 #[inline]
71 pub fn attributes(&mut self) -> Attributes<'l> {
72 self.attributes
73 }
74}
75
76/// An acceleration structure for sampling distances along a specific path.
77///
78/// Building the path measurements can be an expensive operation depending on the complexity of the
79/// measured path, so it is usually a good idea to cache and reuse it whenever possible.
80///
81/// Queries on path measurements are made via a sampler object (see `PathSampler`) which can be configured
82/// to measure real distance or normalized ones (values between 0 and 1 with zero indicating the start
83/// of the path and 1 indicating the end).
84///
85/// ## Differences with the `PathWalker`
86///
87/// The `walker` module provides a similar functionality via the `PathWalker`. The main differences are:
88/// - The path walker does all of its computation on the fly without storing any information for later use.
89/// - `PathMeasurements` stores potentially large amounts of data to speed up sample queries.
90/// - The cost of creating `PathMeasurements` is similar to that of walking the entire path once.
91/// - Once the `PathMeasurements` have been created, random samples on the path are much faster than path walking.
92/// - The PathWalker does not handle normalized distances since the length of the path cannot be known without
93/// traversing the entire path at least once.
94///
95/// Prefer `PathMeasurements` over `PathWalker` if the measurements can be cached and reused for a large number of
96/// queries.
97///
98/// ## Example
99///
100/// ```
101/// use lyon_algorithms::{
102/// math::point,
103/// path::Path,
104/// length::approximate_length,
105/// measure::{PathMeasurements, SampleType},
106/// };
107///
108/// let mut path = Path::builder();
109/// path.begin(point(0.0, 0.0));
110/// path.quadratic_bezier_to(point(1.0, 1.0), point(2.0, 0.0));
111/// path.end(false);
112/// let path = path.build();
113///
114/// // Build the acceleration structure.
115/// let measurements = PathMeasurements::from_path(&path, 1e-3);
116/// let mut sampler = measurements.create_sampler(&path, SampleType::Normalized);
117///
118/// let sample = sampler.sample(0.5);
119/// println!("Mid-point position: {:?}, tangent: {:?}", sample.position(), sample.tangent());
120///
121/// let mut second_half = Path::builder();
122/// sampler.split_range(0.5..1.0, &mut second_half);
123/// let second_half = second_half.build();
124/// assert!((sampler.length() / 2.0 - approximate_length(&second_half, 1e-3)).abs() < 1e-3);
125/// ```
126///
127pub struct PathMeasurements {
128 events: Vec<IdEvent>,
129 edges: Vec<Edge>,
130}
131
132impl PathMeasurements {
133 /// Create empty path measurements.
134 ///
135 /// The measurements cannot be used until it has been initialized.
136 pub fn empty() -> Self {
137 PathMeasurements {
138 events: Vec::new(),
139 edges: Vec::new(),
140 }
141 }
142
143 /// Create path measurements initialized with a `Path`.
144 pub fn from_path(path: &Path, tolerance: f32) -> Self {
145 let mut m = Self::empty();
146 m.initialize(path.id_iter(), path, tolerance);
147
148 m
149 }
150
151 /// Create path measurements initialized with a `PathSlice`.
152 pub fn from_path_slice(path: &PathSlice, tolerance: f32) -> Self {
153 let mut m = Self::empty();
154 m.initialize(path.id_iter(), path, tolerance);
155
156 m
157 }
158
159 /// Create path measurements initialized with a generic iterator and position store.
160 pub fn from_iter<Iter, PS>(path: Iter, positions: &PS, tolerance: f32) -> Self
161 where
162 Iter: IntoIterator<Item = IdEvent>,
163 PS: PositionStore,
164 {
165 let mut m = Self::empty();
166 m.initialize(path, positions, tolerance);
167
168 m
169 }
170
171 /// Initialize the path measurements with a path.
172 pub fn initialize<Iter, PS>(&mut self, path: Iter, position_store: &PS, tolerance: f32)
173 where
174 Iter: IntoIterator<Item = IdEvent>,
175 PS: PositionStore,
176 {
177 let tolerance = tolerance.max(1e-4);
178 let mut events = core::mem::take(&mut self.events);
179 events.clear();
180 events.extend(path.into_iter());
181 let mut edges = core::mem::take(&mut self.edges);
182 edges.clear();
183
184 let mut distance = 0.0;
185 for (index, event) in events.iter().cloned().enumerate() {
186 match event {
187 IdEvent::Begin { .. } => {
188 edges.push(Edge {
189 distance,
190 index,
191 t: 1.0,
192 });
193 }
194 IdEvent::Line { from, to } => {
195 let from = position_store.get_endpoint(from);
196 let to = position_store.get_endpoint(to);
197 distance += (from - to).length();
198 edges.push(Edge {
199 distance,
200 index,
201 t: 1.0,
202 })
203 }
204 IdEvent::Quadratic { from, ctrl, to } => {
205 let from = position_store.get_endpoint(from);
206 let to = position_store.get_endpoint(to);
207 let ctrl = position_store.get_control_point(ctrl);
208 let segment = QuadraticBezierSegment { from, ctrl, to };
209 segment.for_each_flattened_with_t(tolerance, &mut |line, t| {
210 distance += line.length();
211 edges.push(Edge {
212 distance,
213 index,
214 t: t.end,
215 });
216 });
217 }
218 IdEvent::Cubic {
219 from,
220 ctrl1,
221 ctrl2,
222 to,
223 } => {
224 let from = position_store.get_endpoint(from);
225 let to = position_store.get_endpoint(to);
226 let ctrl1 = position_store.get_control_point(ctrl1);
227 let ctrl2 = position_store.get_control_point(ctrl2);
228 let segment = CubicBezierSegment {
229 from,
230 ctrl1,
231 ctrl2,
232 to,
233 };
234 segment.for_each_flattened_with_t(tolerance, &mut |line, t| {
235 distance += line.length();
236 edges.push(Edge {
237 distance,
238 index,
239 t: t.end,
240 });
241 });
242 }
243 IdEvent::End {
244 last,
245 first,
246 close: true,
247 } => {
248 let last = position_store.get_endpoint(last);
249 let first = position_store.get_endpoint(first);
250 distance += (last - first).length();
251 edges.push(Edge {
252 distance,
253 index,
254 t: 1.0,
255 })
256 }
257 _ => {}
258 }
259 }
260
261 if !edges.is_empty() {
262 debug_assert_eq!(edges.first().unwrap().distance, 0.0);
263 }
264
265 self.events = events;
266 self.edges = edges;
267 }
268
269 /// Initialize the path measurements with a path.
270 pub fn initialize_with_path(&mut self, path: &Path, tolerance: f32) {
271 self.initialize_with_path_slice(path.as_slice(), tolerance)
272 }
273
274 /// Initialize the path measurements with a path.
275 pub fn initialize_with_path_slice(&mut self, path: PathSlice, tolerance: f32) {
276 self.initialize(path.id_iter(), &path, tolerance)
277 }
278
279 /// Returns the approximate length of the path.
280 pub fn length(&self) -> f32 {
281 if self.edges.is_empty() {
282 0.0
283 } else {
284 self.edges.last().unwrap().distance
285 }
286 }
287
288 /// Create an object that can perform fast sample queries on a path using the cached measurements.
289 ///
290 /// The returned sampler does not compute interpolated attributes.
291 pub fn create_sampler<'l, PS: PositionStore>(
292 &'l self,
293 positions: &'l PS,
294 ty: SampleType,
295 ) -> PathSampler<'l, PS, ()> {
296 let attr: &'static () = &();
297 PathSampler::new(self, positions, attr, ty)
298 }
299
300 /// Create an object that can perform fast sample queries on a path using the cached measurements.
301 ///
302 /// The returned sampler computes interpolated attributes.
303 pub fn create_sampler_with_attributes<'l, PS, AS>(
304 &'l self,
305 positions: &'l PS,
306 attributes: &'l AS,
307 ty: SampleType,
308 ) -> PathSampler<'l, PS, AS>
309 where
310 PS: PositionStore,
311 AS: AttributeStore,
312 {
313 PathSampler::new(self, positions, attributes, ty)
314 }
315}
316
317/// Performs fast sample queries on a path with cached measurements.
318///
319/// This object contains the mutable state necessary for speeding up the queries, this allows the
320/// path measurements to be immutable and accessible concurrently from multiple threads if needed.
321///
322/// Reusing a sampler over multiple queries saves a memory allocation if there are custom attributes,
323/// And speeds up queries if they are sequentially ordered along the path.
324pub struct PathSampler<'l, PS, AS> {
325 events: &'l [IdEvent],
326 edges: &'l [Edge],
327 positions: &'l PS,
328 attributes: &'l AS,
329 attribute_buffer: Vec<f32>,
330 cursor: usize,
331 sample_type: SampleType,
332}
333
334impl<'l, PS: PositionStore, AS: AttributeStore> PathSampler<'l, PS, AS> {
335 /// Create a sampler.
336 ///
337 /// The provided positions must be the ones used when initializing the path measurements.
338 pub fn new(
339 measurements: &'l PathMeasurements,
340 positions: &'l PS,
341 attributes: &'l AS,
342 sample_type: SampleType,
343 ) -> Self {
344 PathSampler {
345 events: &measurements.events,
346 edges: &measurements.edges,
347 positions,
348 attributes,
349 attribute_buffer: alloc::vec![0.0; attributes.num_attributes()],
350 cursor: 0,
351 sample_type,
352 }
353 }
354
355 /// Sample at a given distance along the path.
356 ///
357 /// If the path is empty, the produced sample will contain NaNs.
358 pub fn sample(&mut self, dist: f32) -> PathSample {
359 self.sample_impl(dist, self.sample_type)
360 }
361
362 /// Construct a path for a specific sub-range of the measured path.
363 ///
364 /// The path measurements must have been initialized with the same path.
365 /// The distance is clamped to the beginning and end of the path.
366 /// Panics if the path is empty.
367 pub fn split_range(&mut self, mut range: Range<f32>, output: &mut dyn PathBuilder) {
368 let length = self.length();
369 if self.sample_type == SampleType::Normalized {
370 range.start *= length;
371 range.end *= length;
372 }
373 range.start = range.start.max(0.0);
374 range.end = range.end.max(range.start);
375 range.start = range.start.min(length);
376 range.end = range.end.min(length);
377
378 if range.is_empty() {
379 return;
380 }
381
382 let result = self.sample_impl(range.start, SampleType::Distance);
383 output.begin(result.position, result.attributes);
384 let (ptr1, seg1) = (self.cursor, self.edges[self.cursor].index);
385 self.move_cursor(range.end);
386 let (ptr2, seg2) = (self.cursor, self.edges[self.cursor].index);
387
388 let mut is_in_subpath = true;
389 if seg1 == seg2 {
390 self.cursor = ptr1;
391 let t_begin = self.t(range.start);
392 self.cursor = ptr2;
393 let t_end = self.t(range.end);
394 self.add_segment(seg1, Some(t_begin..t_end), output, &mut is_in_subpath);
395 } else {
396 self.cursor = ptr1;
397 self.add_segment(
398 seg1,
399 Some(self.t(range.start)..1.0),
400 output,
401 &mut is_in_subpath,
402 );
403 for seg in (seg1 + 1)..seg2 {
404 self.add_segment(seg, None, output, &mut is_in_subpath);
405 }
406 self.cursor = ptr2;
407 self.add_segment(
408 seg2,
409 Some(0.0..self.t(range.end)),
410 output,
411 &mut is_in_subpath,
412 );
413 }
414
415 output.end(false);
416 }
417
418 /// Returns the approximate length of the path.
419 pub fn length(&self) -> f32 {
420 if self.edges.is_empty() {
421 0.0
422 } else {
423 self.edges.last().unwrap().distance
424 }
425 }
426
427 fn to_segment(&self, event: IdEvent) -> SegmentWrapper {
428 match event {
429 IdEvent::Line { from, to } => SegmentWrapper::Line(
430 LineSegment {
431 from: self.positions.get_endpoint(from),
432 to: self.positions.get_endpoint(to),
433 },
434 (from, to),
435 ),
436 IdEvent::Quadratic { from, ctrl, to } => SegmentWrapper::Quadratic(
437 QuadraticBezierSegment {
438 from: self.positions.get_endpoint(from),
439 to: self.positions.get_endpoint(to),
440 ctrl: self.positions.get_control_point(ctrl),
441 },
442 (from, to),
443 ),
444 IdEvent::Cubic {
445 from,
446 ctrl1,
447 ctrl2,
448 to,
449 } => SegmentWrapper::Cubic(
450 CubicBezierSegment {
451 from: self.positions.get_endpoint(from),
452 to: self.positions.get_endpoint(to),
453 ctrl1: self.positions.get_control_point(ctrl1),
454 ctrl2: self.positions.get_control_point(ctrl2),
455 },
456 (from, to),
457 ),
458 IdEvent::End {
459 last,
460 first,
461 close: true,
462 } => SegmentWrapper::Line(
463 LineSegment {
464 from: self.positions.get_endpoint(last),
465 to: self.positions.get_endpoint(first),
466 },
467 (last, first),
468 ),
469 _ => SegmentWrapper::Empty,
470 }
471 }
472
473 fn in_bounds(&self, dist: f32) -> bool {
474 self.cursor != 0
475 && self.edges[self.cursor - 1].distance <= dist
476 && dist <= self.edges[self.cursor].distance
477 }
478
479 /// Move the pointer so the given point is on the current segment.
480 fn move_cursor(&mut self, dist: f32) {
481 if dist == 0.0 {
482 self.cursor = 1;
483 return;
484 }
485 if self.in_bounds(dist) {
486 // No need to move
487 return;
488 }
489
490 // Performs on [first, last)
491 // ...TTFFF...
492 // ^
493 // sample this point
494 fn partition_point(first: usize, last: usize, pred: impl Fn(usize) -> bool) -> usize {
495 let mut l = first;
496 let mut r = last;
497 while l < r {
498 let mid = (l + r) / 2;
499 if pred(mid) {
500 l = mid + 1;
501 } else {
502 r = mid;
503 }
504 }
505 debug_assert_eq!(l, r);
506 debug_assert_ne!(l, last);
507 l
508 }
509
510 fn floor_log2(num: usize) -> u32 {
511 core::mem::size_of::<usize>() as u32 * 8 - num.leading_zeros() - 1
512 }
513
514 // Here we use a heuristic method combining method 1 & 2
515 // Method 1: Move step by step until we found the corresponding segment, works well on short paths and near queries
516 // Time complexity: (expected) (dist - start).abs() / len * num
517 // Method 2. Binary search on lengths, works well on long paths and random calls
518 // Time complexity: (exact) floor(log2(num))
519 // where `len` and `num` are given as follow
520 //
521 // According to the benchmark, this method works well in both cases and has low overhead in relative to Method 1 & 2.
522 // Benchmark code: https://gist.github.com/Mivik/5f67ae5a72eae3884b2f386370554966
523 let start = self.edges[self.cursor].distance;
524 if start < dist {
525 let (len, num) = (self.length() - start, self.edges.len() - self.cursor - 1);
526 debug_assert_ne!(num, 0);
527 if (dist - start) / len * (num as f32) < floor_log2(num) as f32 {
528 loop {
529 self.cursor += 1;
530 if dist <= self.edges[self.cursor].distance {
531 break;
532 }
533 }
534 } else {
535 self.cursor = partition_point(self.cursor + 1, self.edges.len(), |p| {
536 self.edges[p].distance < dist
537 });
538 }
539 } else {
540 let (len, num) = (start, self.cursor + 1);
541 debug_assert_ne!(num, 0);
542 if (start - dist) / len * (num as f32) < floor_log2(num) as f32 {
543 loop {
544 self.cursor -= 1;
545 if self.cursor == 0 || self.edges[self.cursor - 1].distance < dist {
546 break;
547 }
548 }
549 } else {
550 self.cursor = partition_point(0, self.cursor, |p| self.edges[p].distance < dist);
551 }
552 }
553
554 debug_assert!(self.in_bounds(dist));
555 }
556
557 /// Interpolate the custom attributes.
558 fn interpolate_attributes(&mut self, from: EndpointId, to: EndpointId, t: f32) {
559 let from = self.attributes.get(from);
560 let to = self.attributes.get(to);
561 for i in 0..self.attribute_buffer.len() {
562 self.attribute_buffer[i] = from[i] * (1.0 - t) + to[i] * t;
563 }
564 }
565
566 /// Returns the relative position (0 ~ 1) of the given point on the current segment.
567 fn t(&self, dist: f32) -> f32 {
568 debug_assert!(self.in_bounds(dist));
569 let prev = &self.edges[self.cursor - 1];
570 let cur = &self.edges[self.cursor];
571 let t_begin = if prev.index == cur.index { prev.t } else { 0.0 };
572 let t_end = cur.t;
573 t_begin + (t_end - t_begin) * ((dist - prev.distance) / (cur.distance - prev.distance))
574 }
575
576 fn sample_impl(&mut self, mut dist: f32, sample_type: SampleType) -> PathSample {
577 let length = self.length();
578 if length == 0.0 {
579 return self.sample_zero_length();
580 }
581 if sample_type == SampleType::Normalized {
582 dist *= length;
583 }
584 dist = dist.max(0.0);
585 dist = dist.min(length);
586
587 self.move_cursor(dist);
588 let t = self.t(dist);
589 macro_rules! dispatched_call {
590 ([$v:expr] ($seg:ident, $pair:ident) => $code:block) => {
591 #[allow(unused_parens)]
592 match $v {
593 SegmentWrapper::Line($seg, $pair) => $code,
594 SegmentWrapper::Quadratic($seg, $pair) => $code,
595 SegmentWrapper::Cubic($seg, $pair) => $code,
596 _ => {}
597 }
598 };
599 }
600
601 dispatched_call!([self.to_segment(self.events[self.edges[self.cursor].index])] (segment, pair) => {
602 self.interpolate_attributes(pair.0, pair.1, t);
603 return PathSample {
604 position: segment.sample(t),
605 tangent: segment.derivative(t).normalize(),
606 attributes: &self.attribute_buffer,
607 }
608 });
609
610 unreachable!();
611 }
612
613 #[cold]
614 fn sample_zero_length(&mut self) -> PathSample {
615 if let Some(IdEvent::Begin { at }) = self.events.first() {
616 return PathSample {
617 position: self.positions.get_endpoint(*at),
618 tangent: vector(0.0, 0.0),
619 attributes: self.attributes.get(*at),
620 };
621 }
622
623 for value in &mut self.attribute_buffer {
624 *value = f32::NAN;
625 }
626
627 PathSample {
628 position: point(f32::NAN, f32::NAN),
629 tangent: vector(f32::NAN, f32::NAN),
630 attributes: &self.attribute_buffer,
631 }
632 }
633
634 /// Caller needs to hold a parameter to keep track of whether we're in a subpath or not, as this would be determined
635 /// by prior segments. This function will update `is_in_subpath` based on the segment it adds.
636 fn add_segment(
637 &mut self,
638 ptr: usize,
639 range: Option<Range<f32>>,
640 dest: &mut dyn PathBuilder,
641 is_in_subpath: &mut bool,
642 ) {
643 let segment = self.to_segment(self.events[ptr]);
644 let segment = match range.clone() {
645 Some(range) => segment.split(range),
646 None => segment,
647 };
648 macro_rules! obtain_attrs {
649 ($p:ident, $index:tt) => {
650 match range.clone() {
651 Some(range) => {
652 if range.end == 1.0 {
653 self.attributes.get($p.$index)
654 } else {
655 self.interpolate_attributes($p.0, $p.1, range.end);
656 &mut self.attribute_buffer
657 }
658 }
659 None => self.attributes.get($p.$index),
660 }
661 };
662 }
663
664 match segment {
665 SegmentWrapper::Line(LineSegment { from, to }, pair) => {
666 if !*is_in_subpath {
667 dest.end(false);
668 dest.begin(from, obtain_attrs!(pair, 0));
669 }
670 dest.line_to(to, obtain_attrs!(pair, 1));
671 }
672 SegmentWrapper::Quadratic(QuadraticBezierSegment { from, ctrl, to }, pair) => {
673 if !*is_in_subpath {
674 dest.end(false);
675 dest.begin(from, obtain_attrs!(pair, 0));
676 }
677 dest.quadratic_bezier_to(ctrl, to, obtain_attrs!(pair, 1));
678 }
679 SegmentWrapper::Cubic(
680 CubicBezierSegment {
681 from,
682 ctrl1,
683 ctrl2,
684 to,
685 },
686 pair,
687 ) => {
688 if !*is_in_subpath {
689 dest.end(false);
690 dest.begin(from, obtain_attrs!(pair, 0));
691 }
692 dest.cubic_bezier_to(ctrl1, ctrl2, to, obtain_attrs!(pair, 1));
693 }
694 _ => {}
695 }
696
697 *is_in_subpath = !matches!(
698 self.events[ptr],
699 IdEvent::End { .. } | IdEvent::Begin { .. }
700 );
701 }
702}
703
704#[cfg(test)]
705fn slice(a: &[f32]) -> &[f32] {
706 a
707}
708
709#[test]
710fn measure_line() {
711 let mut path = Path::builder();
712 path.begin(point(1.0, 1.0));
713 path.line_to(point(0.0, 0.0));
714 path.end(false);
715 let path = path.build();
716 let measure = PathMeasurements::from_path(&path, 0.01);
717 let mut sampler = measure.create_sampler(&path, SampleType::Normalized);
718 for t in [0.0, 0.2, 0.3, 0.5, 1.0] {
719 let result = sampler.sample(t);
720 assert!((result.position - point(1.0 - t, 1.0 - t)).length() < 1e-5);
721 assert_eq!(result.tangent, vector(-1.0, -1.0).normalize());
722 }
723}
724
725#[test]
726fn measure_square() {
727 let mut path = Path::builder();
728 path.begin(point(0.0, 0.0));
729 path.line_to(point(1.0, 0.0));
730 path.line_to(point(1.0, 1.0));
731 path.line_to(point(0.0, 1.0));
732 path.close();
733 let path = path.build();
734 let measure = PathMeasurements::from_path(&path, 0.01);
735 let mut sampler = measure.create_sampler(&path, SampleType::Normalized);
736 for (t, position, tangent) in [
737 (0.125, point(0.5, 0.0), vector(1.0, 0.0)),
738 (0.375, point(1.0, 0.5), vector(0.0, 1.0)),
739 (0.625, point(0.5, 1.0), vector(-1.0, 0.0)),
740 (0.875, point(0.0, 0.5), vector(0.0, -1.0)),
741 ] {
742 let result = sampler.sample(t);
743 assert!((result.position - position).length() < 1e-5);
744 assert_eq!(result.tangent, tangent);
745 }
746}
747
748#[test]
749fn measure_attributes() {
750 let mut path = Path::builder_with_attributes(2);
751 path.begin(point(0.0, 0.0), &[1.0, 2.0]);
752 path.line_to(point(1.0, 0.0), &[2.0, 3.0]);
753 path.line_to(point(1.0, 1.0), &[0.0, 0.0]);
754 path.end(false);
755 let path = path.build();
756 let measure = PathMeasurements::from_path(&path, 0.01);
757 let mut sampler = measure.create_sampler_with_attributes(&path, &path, SampleType::Normalized);
758
759 for (t, position, attrs) in [
760 (0.25, point(0.5, 0.0), &[1.5, 2.5]),
761 (0.5, point(1.0, 0.0), &[2.0, 3.0]),
762 (0.75, point(1.0, 0.5), &[1.0, 1.5]),
763 ] {
764 let result = sampler.sample(t);
765 assert!((result.position - position).length() < 1e-5);
766 for i in 0..2 {
767 assert!((result.attributes[i] - attrs[i]).abs() < 1e-5);
768 }
769 }
770}
771
772#[test]
773fn measure_bezier_curve() {
774 let mut path = Path::builder();
775 path.begin(point(0.0, 0.0));
776 path.quadratic_bezier_to(point(0.5, 0.7), point(1.0, 0.0));
777 path.quadratic_bezier_to(point(1.5, -0.7), point(2.0, 0.0));
778 path.end(false);
779 let path = path.build();
780
781 let measure = PathMeasurements::from_path(&path, 0.01);
782 let mut sampler = measure.create_sampler(&path, SampleType::Normalized);
783
784 for t in [0.25, 0.75] {
785 let result = sampler.sample(t);
786 assert_eq!(result.tangent, vector(1.0, 0.0));
787 }
788 for (t, position) in [
789 (0.0, point(0.0, 0.0)),
790 (0.5, point(1.0, 0.0)),
791 (1.0, point(2.0, 0.0)),
792 ] {
793 let result = sampler.sample(t);
794 assert_eq!(result.position, position);
795 }
796}
797
798#[test]
799fn split_square() {
800 use crate::path::Event;
801
802 let mut path = Path::builder();
803 path.begin(point(0.0, 0.0));
804 path.line_to(point(1.0, 0.0));
805 path.line_to(point(1.0, 1.0));
806 path.line_to(point(0.0, 1.0));
807 path.close();
808 let path = path.build();
809 let measure = PathMeasurements::from_path(&path, 0.01);
810 let mut sampler = measure.create_sampler(&path, SampleType::Normalized);
811 let mut path2 = Path::builder();
812 sampler.split_range(0.125..0.625, &mut path2);
813 let path2 = path2.build();
814 assert_eq!(
815 path2.iter().collect::<Vec<_>>(),
816 alloc::vec![
817 Event::Begin {
818 at: point(0.5, 0.0)
819 },
820 Event::Line {
821 from: point(0.5, 0.0),
822 to: point(1.0, 0.0)
823 },
824 Event::Line {
825 from: point(1.0, 0.0),
826 to: point(1.0, 1.0)
827 },
828 Event::Line {
829 from: point(1.0, 1.0),
830 to: point(0.5, 1.0)
831 },
832 Event::End {
833 last: point(0.5, 1.0),
834 first: point(0.5, 0.0),
835 close: false
836 },
837 ]
838 );
839}
840
841#[test]
842fn split_bezier_curve() {
843 use crate::path::Event;
844
845 let mut path = Path::builder();
846 path.begin(point(0.0, 0.0));
847 path.quadratic_bezier_to(point(1.0, 1.0), point(2.0, 0.0));
848 path.end(false);
849 let path = path.build();
850 let measure = PathMeasurements::from_path(&path, 0.01);
851 let mut sampler = measure.create_sampler(&path, SampleType::Normalized);
852
853 let mut path2 = Path::builder();
854 sampler.split_range(0.5..1.0, &mut path2);
855 let path2 = path2.build();
856
857 assert_eq!(
858 path2.iter().collect::<Vec<_>>(),
859 alloc::vec![
860 Event::Begin {
861 at: point(1.0, 0.5)
862 },
863 Event::Quadratic {
864 from: point(1.0, 0.5),
865 ctrl: point(1.5, 0.5),
866 to: point(2.0, 0.0),
867 },
868 Event::End {
869 last: point(2.0, 0.0),
870 first: point(1.0, 0.5),
871 close: false
872 }
873 ]
874 );
875}
876
877#[test]
878fn split_attributes() {
879 use crate::path::Event;
880
881 let mut path = Path::builder_with_attributes(2);
882 path.begin(point(0.0, 0.0), &[1.0, 2.0]);
883 path.line_to(point(1.0, 0.0), &[2.0, 3.0]);
884 path.line_to(point(1.0, 1.0), &[0.0, 0.0]);
885 path.end(false);
886 let path = path.build();
887 let measure = PathMeasurements::from_path(&path, 0.01);
888 let mut sampler = measure.create_sampler_with_attributes(&path, &path, SampleType::Normalized);
889
890 let mut path2 = Path::builder_with_attributes(2);
891 sampler.split_range(0.0..1.0, &mut path2);
892 let path2 = path2.build();
893
894 assert_eq!(
895 path2.iter_with_attributes().collect::<Vec<_>>(),
896 path.iter_with_attributes().collect::<Vec<_>>()
897 );
898
899 let mut path3 = Path::builder_with_attributes(2);
900 sampler.split_range(0.25..0.75, &mut path3);
901 let path3 = path3.build();
902
903 assert_eq!(
904 path3.iter_with_attributes().collect::<Vec<_>>(),
905 alloc::vec![
906 Event::Begin {
907 at: (point(0.5, 0.0), slice(&[1.5, 2.5]))
908 },
909 Event::Line {
910 from: (point(0.5, 0.0), slice(&[1.5, 2.5])),
911 to: (point(1.0, 0.0), slice(&[2.0, 3.0])),
912 },
913 Event::Line {
914 from: (point(1.0, 0.0), slice(&[2.0, 3.0])),
915 to: (point(1.0, 0.5), slice(&[1.0, 1.5])),
916 },
917 Event::End {
918 last: (point(1.0, 0.5), slice(&[1.0, 1.5])),
919 first: (point(0.5, 0.0), slice(&[1.5, 2.5])),
920 close: false
921 }
922 ]
923 );
924}
925
926#[test]
927fn zero_length() {
928 fn expect_nans(sample: PathSample, num_attribs: usize) {
929 assert!(sample.position.x.is_nan());
930 assert!(sample.position.y.is_nan());
931 assert!(sample.tangent.x.is_nan());
932 assert!(sample.tangent.y.is_nan());
933 for attr in sample.attributes {
934 assert!(attr.is_nan());
935 }
936 assert_eq!(sample.attributes.len(), num_attribs);
937 }
938
939 let mut path = Path::builder_with_attributes(2);
940 path.begin(point(1.0, 2.0), &[3.0, 4.0]);
941 path.end(false);
942 let path = path.build();
943 let measure = PathMeasurements::from_path(&path, 0.01);
944 let mut sampler = measure.create_sampler_with_attributes(&path, &path, SampleType::Normalized);
945 let expected = PathSample {
946 position: point(1.0, 2.0),
947 tangent: vector(0.0, 0.0),
948 attributes: &[3.0, 4.0],
949 };
950 assert_eq!(sampler.sample(0.0), expected);
951 assert_eq!(sampler.sample(0.5), expected);
952 assert_eq!(sampler.sample(1.0), expected);
953
954 let mut path = Path::builder_with_attributes(2);
955 path.begin(point(1.0, 2.0), &[3.0, 4.0]);
956 path.end(false);
957 let path = path.build();
958 let measure = PathMeasurements::from_path(&path, 0.01);
959 let mut sampler = measure.create_sampler_with_attributes(&path, &path, SampleType::Distance);
960 let expected = PathSample {
961 position: point(1.0, 2.0),
962 tangent: vector(0.0, 0.0),
963 attributes: &[3.0, 4.0],
964 };
965 assert_eq!(sampler.sample(0.0), expected);
966 assert_eq!(sampler.sample(0.5), expected);
967 assert_eq!(sampler.sample(1.0), expected);
968
969 let path = Path::builder_with_attributes(2).build();
970 let measure = PathMeasurements::from_path(&path, 0.01);
971 let mut sampler = measure.create_sampler_with_attributes(&path, &path, SampleType::Normalized);
972 expect_nans(sampler.sample(0.0), 2);
973 expect_nans(sampler.sample(0.5), 2);
974 expect_nans(sampler.sample(1.0), 2);
975
976 let path = Path::builder_with_attributes(2).build();
977 let measure = PathMeasurements::from_path(&path, 0.01);
978 let mut sampler = measure.create_sampler_with_attributes(&path, &path, SampleType::Distance);
979 expect_nans(sampler.sample(0.0), 2);
980 expect_nans(sampler.sample(0.5), 2);
981 expect_nans(sampler.sample(1.0), 2);
982}
983
984
985#[test]
986fn multiple_sub_paths() {
987 let mut path = Path::builder();
988
989 path.begin(point(0.0, 0.0));
990 path.line_to(point(10.0, 0.0));
991 path.end(false);
992
993 path.begin(point(10.0, 10.0));
994 path.line_to(point(20.0, 10.0));
995 path.end(false);
996
997 let path = path.build();
998 let measure = PathMeasurements::from_path(&path, 0.01);
999 let mut sampler = measure.create_sampler(&path, SampleType::Normalized);
1000
1001 let mut dashes = Path::builder();
1002 sampler.split_range(0.0 .. 0.25, &mut dashes);
1003 sampler.split_range(0.25 .. 0.5, &mut dashes);
1004 // Avoid starting subpaths exactly on the join as we may begin with a zero-length subpath
1005 sampler.split_range(0.6 .. 0.75, &mut dashes);
1006 sampler.split_range(0.75 .. 1.0, &mut dashes);
1007 let dashes = dashes.build();
1008
1009 let mut iter = dashes.iter();
1010
1011 use crate::path::geom::euclid::approxeq::ApproxEq;
1012 fn expect_begin(event: Option<path::PathEvent>, pos: Point) {
1013 std::eprintln!("- {:?}", event);
1014 if let Some(path::PathEvent::Begin { at }) = event {
1015 assert!(at.approx_eq(&pos), "Expected Begin {:?}, got {:?}", pos, at);
1016 } else {
1017 panic!("Expected begin, got {:?}", event);
1018 }
1019 }
1020
1021 fn expect_end(event: Option<path::PathEvent>, pos: Point) {
1022 std::eprintln!("- {:?}", event);
1023 if let Some(path::PathEvent::End { last, .. }) = event {
1024 assert!(last.approx_eq(&pos), "Expected End {:?}, got {:?}", pos, last);
1025 } else {
1026 panic!("Expected end, got {:?}", event);
1027 }
1028 }
1029 fn expect_line(event: Option<path::PathEvent>, expect_from: Point, expect_to: Point) {
1030 std::eprintln!("- {:?}", event);
1031 if let Some(path::PathEvent::Line { from, to }) = event {
1032 assert!(from.approx_eq(&expect_from), "Expected line {:?} {:?}, got {:?} {:?}", expect_from, expect_to, from, to);
1033 assert!(to.approx_eq(&expect_to), "Expected line {:?} {:?}, got {:?} {:?}", expect_from, expect_to, from, to);
1034 } else {
1035 panic!("Expected a line {:?} {:?}, got {:?}", expect_from, expect_to, event);
1036 }
1037 }
1038
1039 expect_begin(iter.next(), point(0.0, 0.0));
1040 expect_line(iter.next(), point(0.0, 0.0), point(5.0, 0.0));
1041 expect_end(iter.next(), point(5.0, 0.0));
1042
1043 expect_begin(iter.next(), point(5.0, 0.0));
1044 expect_line(iter.next(), point(5.0, 0.0), point(10.0, 0.0));
1045 expect_end(iter.next(), point(10.0, 0.0));
1046
1047 expect_begin(iter.next(), point(12.0, 10.0));
1048 expect_line(iter.next(), point(12.0, 10.0), point(15.0, 10.0));
1049 expect_end(iter.next(), point(15.0, 10.0));
1050
1051 expect_begin(iter.next(), point(15.0, 10.0));
1052 expect_line(iter.next(), point(15.0, 10.0), point(20.0, 10.0));
1053 expect_end(iter.next(), point(20.0, 10.0));
1054}