1// Copyright 2006 The Android Open Source Project
2// Copyright 2020 Yevhenii Reizner
3//
4// Use of this source code is governed by a BSD-style license that can be
5// found in the LICENSE file.
6
7use alloc::vec::Vec;
8
9use crate::path_builder::PathBuilder;
10use crate::transform::Transform;
11use crate::{Point, Rect};
12
13#[cfg(all(not(feature = "std"), feature = "no-std-float"))]
14use crate::NoStdFloat;
15
16/// A path verb.
17#[allow(missing_docs)]
18#[derive(Copy, Clone, Eq, PartialEq, Ord, PartialOrd, Debug)]
19pub enum PathVerb {
20 Move,
21 Line,
22 Quad,
23 Cubic,
24 Close,
25}
26
27/// A Bezier path.
28///
29/// Can be created via [`PathBuilder`].
30/// Where [`PathBuilder`] can be created from the [`Path`] using [`clear`] to reuse the allocation.
31///
32/// Path is immutable and uses compact storage, where segment types and numbers are stored
33/// separately. Use can access path segments via [`Path::verbs`] and [`Path::points`],
34/// or via [`Path::segments`]
35///
36/// # Guarantees
37///
38/// - Has a valid, precomputed bounds.
39/// - All points are finite.
40/// - Has at least two segments.
41/// - Each contour starts with a MoveTo.
42/// - No duplicated Move.
43/// - No duplicated Close.
44/// - Zero-length contours are allowed.
45///
46/// [`PathBuilder`]: struct.PathBuilder.html
47/// [`clear`]: struct.Path.html#method.clear
48#[derive(Clone, PartialEq)]
49pub struct Path {
50 pub(crate) verbs: Vec<PathVerb>,
51 pub(crate) points: Vec<Point>,
52 pub(crate) bounds: Rect,
53}
54
55impl Path {
56 /// Returns the number of segments in the path.
57 pub fn len(&self) -> usize {
58 self.verbs.len()
59 }
60
61 /// Return if the path is empty.
62 pub fn is_empty(&self) -> bool {
63 self.verbs.is_empty()
64 }
65
66 /// Returns the bounds of the path's points.
67 ///
68 /// The value is already calculated.
69 pub fn bounds(&self) -> Rect {
70 self.bounds
71 }
72
73 /// Calculates path's tight bounds.
74 ///
75 /// This operation can be expensive.
76 pub fn compute_tight_bounds(&self) -> Option<Rect> {
77 // big enough to hold worst-case curve type (cubic) extremas + 1
78 let mut extremas = [Point::zero(); 5];
79
80 let mut min = self.points[0];
81 let mut max = self.points[0];
82 let mut iter = self.segments();
83 let mut last_point = Point::zero();
84 while let Some(segment) = iter.next() {
85 let mut count = 0;
86 match segment {
87 PathSegment::MoveTo(p) => {
88 extremas[0] = p;
89 count = 1;
90 }
91 PathSegment::LineTo(p) => {
92 extremas[0] = p;
93 count = 1;
94 }
95 PathSegment::QuadTo(p0, p1) => {
96 count = compute_quad_extremas(last_point, p0, p1, &mut extremas);
97 }
98 PathSegment::CubicTo(p0, p1, p2) => {
99 count = compute_cubic_extremas(last_point, p0, p1, p2, &mut extremas);
100 }
101 PathSegment::Close => {}
102 }
103
104 last_point = iter.last_point;
105 for tmp in &extremas[0..count] {
106 min.x = min.x.min(tmp.x);
107 min.y = min.y.min(tmp.y);
108 max.x = max.x.max(tmp.x);
109 max.y = max.y.max(tmp.y);
110 }
111 }
112
113 Rect::from_ltrb(min.x, min.y, max.x, max.y)
114 }
115
116 /// Returns an internal vector of verbs.
117 pub fn verbs(&self) -> &[PathVerb] {
118 &self.verbs
119 }
120
121 /// Returns an internal vector of points.
122 pub fn points(&self) -> &[Point] {
123 &self.points
124 }
125
126 /// Returns a transformed in-place path.
127 ///
128 /// Some points may become NaN/inf therefore this method can fail.
129 pub fn transform(mut self, ts: Transform) -> Option<Self> {
130 if ts.is_identity() {
131 return Some(self);
132 }
133
134 ts.map_points(&mut self.points);
135
136 // Update bounds.
137 self.bounds = Rect::from_points(&self.points)?;
138
139 Some(self)
140 }
141
142 /// Returns an iterator over path's segments.
143 pub fn segments(&self) -> PathSegmentsIter {
144 PathSegmentsIter {
145 path: self,
146 verb_index: 0,
147 points_index: 0,
148 is_auto_close: false,
149 last_move_to: Point::zero(),
150 last_point: Point::zero(),
151 }
152 }
153
154 /// Clears the path and returns a `PathBuilder` that will reuse an allocated memory.
155 pub fn clear(mut self) -> PathBuilder {
156 self.verbs.clear();
157 self.points.clear();
158
159 PathBuilder {
160 verbs: self.verbs,
161 points: self.points,
162 last_move_to_index: 0,
163 move_to_required: true,
164 }
165 }
166}
167
168impl core::fmt::Debug for Path {
169 fn fmt(&self, f: &mut core::fmt::Formatter<'_>) -> core::fmt::Result {
170 use core::fmt::Write;
171
172 let mut s = alloc::string::String::new();
173 for segment in self.segments() {
174 match segment {
175 PathSegment::MoveTo(p) => s.write_fmt(format_args!("M {} {} ", p.x, p.y))?,
176 PathSegment::LineTo(p) => s.write_fmt(format_args!("L {} {} ", p.x, p.y))?,
177 PathSegment::QuadTo(p0, p1) => {
178 s.write_fmt(format_args!("Q {} {} {} {} ", p0.x, p0.y, p1.x, p1.y))?
179 }
180 PathSegment::CubicTo(p0, p1, p2) => s.write_fmt(format_args!(
181 "C {} {} {} {} {} {} ",
182 p0.x, p0.y, p1.x, p1.y, p2.x, p2.y
183 ))?,
184 PathSegment::Close => s.write_fmt(format_args!("Z "))?,
185 }
186 }
187
188 s.pop(); // ' '
189
190 f.debug_struct("Path")
191 .field("segments", &s)
192 .field("bounds", &self.bounds)
193 .finish()
194 }
195}
196
197fn compute_quad_extremas(p0: Point, p1: Point, p2: Point, extremas: &mut [Point; 5]) -> usize {
198 use crate::path_geometry;
199
200 let src: [Point; 3] = [p0, p1, p2];
201 let mut extrema_idx: usize = 0;
202 if let Some(t: NormalizedF32Exclusive) = path_geometry::find_quad_extrema(a:p0.x, b:p1.x, c:p2.x) {
203 extremas[extrema_idx] = path_geometry::eval_quad_at(&src, t.to_normalized());
204 extrema_idx += 1;
205 }
206 if let Some(t: NormalizedF32Exclusive) = path_geometry::find_quad_extrema(a:p0.y, b:p1.y, c:p2.y) {
207 extremas[extrema_idx] = path_geometry::eval_quad_at(&src, t.to_normalized());
208 extrema_idx += 1;
209 }
210 extremas[extrema_idx] = p2;
211 extrema_idx + 1
212}
213
214fn compute_cubic_extremas(
215 p0: Point,
216 p1: Point,
217 p2: Point,
218 p3: Point,
219 extremas: &mut [Point; 5],
220) -> usize {
221 use crate::path_geometry;
222
223 let mut ts0: [NormalizedF32Exclusive; 3] = path_geometry::new_t_values();
224 let mut ts1: [NormalizedF32Exclusive; 3] = path_geometry::new_t_values();
225 let n0: usize = path_geometry::find_cubic_extrema(a:p0.x, b:p1.x, c:p2.x, d:p3.x, &mut ts0);
226 let n1: usize = path_geometry::find_cubic_extrema(a:p0.y, b:p1.y, c:p2.y, d:p3.y, &mut ts1);
227 let total_len: usize = n0 + n1;
228 debug_assert!(total_len <= 4);
229
230 let src: [Point; 4] = [p0, p1, p2, p3];
231 let mut extrema_idx: usize = 0;
232 for t: &NormalizedF32Exclusive in &ts0[0..n0] {
233 extremas[extrema_idx] = path_geometry::eval_cubic_pos_at(&src, t.to_normalized());
234 extrema_idx += 1;
235 }
236 for t: &NormalizedF32Exclusive in &ts1[0..n1] {
237 extremas[extrema_idx] = path_geometry::eval_cubic_pos_at(&src, t.to_normalized());
238 extrema_idx += 1;
239 }
240 extremas[total_len] = p3;
241 total_len + 1
242}
243
244/// A path segment.
245#[allow(missing_docs)]
246#[derive(Copy, Clone, PartialEq, Debug)]
247pub enum PathSegment {
248 MoveTo(Point),
249 LineTo(Point),
250 QuadTo(Point, Point),
251 CubicTo(Point, Point, Point),
252 Close,
253}
254
255/// A path segments iterator.
256#[allow(missing_debug_implementations)]
257#[derive(Clone)]
258pub struct PathSegmentsIter<'a> {
259 path: &'a Path,
260 verb_index: usize,
261 points_index: usize,
262
263 is_auto_close: bool,
264 last_move_to: Point,
265 last_point: Point,
266}
267
268impl<'a> PathSegmentsIter<'a> {
269 /// Sets the auto closing mode. Off by default.
270 ///
271 /// When enabled, emits an additional `PathSegment::Line` from the current position
272 /// to the previous `PathSegment::Move`. And only then emits `PathSegment::Close`.
273 pub fn set_auto_close(&mut self, flag: bool) {
274 self.is_auto_close = flag;
275 }
276
277 pub(crate) fn auto_close(&mut self) -> PathSegment {
278 if self.is_auto_close && self.last_point != self.last_move_to {
279 self.verb_index -= 1;
280 PathSegment::LineTo(self.last_move_to)
281 } else {
282 PathSegment::Close
283 }
284 }
285
286 pub(crate) fn has_valid_tangent(&self) -> bool {
287 let mut iter = self.clone();
288 while let Some(segment) = iter.next() {
289 match segment {
290 PathSegment::MoveTo(_) => {
291 return false;
292 }
293 PathSegment::LineTo(p) => {
294 if iter.last_point == p {
295 continue;
296 }
297
298 return true;
299 }
300 PathSegment::QuadTo(p1, p2) => {
301 if iter.last_point == p1 && iter.last_point == p2 {
302 continue;
303 }
304
305 return true;
306 }
307 PathSegment::CubicTo(p1, p2, p3) => {
308 if iter.last_point == p1 && iter.last_point == p2 && iter.last_point == p3 {
309 continue;
310 }
311
312 return true;
313 }
314 PathSegment::Close => {
315 return false;
316 }
317 }
318 }
319
320 false
321 }
322
323 /// Returns the current verb.
324 pub fn curr_verb(&self) -> PathVerb {
325 self.path.verbs[self.verb_index - 1]
326 }
327
328 /// Returns the next verb.
329 pub fn next_verb(&self) -> Option<PathVerb> {
330 self.path.verbs.get(self.verb_index).cloned()
331 }
332}
333
334impl<'a> Iterator for PathSegmentsIter<'a> {
335 type Item = PathSegment;
336
337 fn next(&mut self) -> Option<Self::Item> {
338 if self.verb_index < self.path.verbs.len() {
339 let verb = self.path.verbs[self.verb_index];
340 self.verb_index += 1;
341
342 match verb {
343 PathVerb::Move => {
344 self.points_index += 1;
345 self.last_move_to = self.path.points[self.points_index - 1];
346 self.last_point = self.last_move_to;
347 Some(PathSegment::MoveTo(self.last_move_to))
348 }
349 PathVerb::Line => {
350 self.points_index += 1;
351 self.last_point = self.path.points[self.points_index - 1];
352 Some(PathSegment::LineTo(self.last_point))
353 }
354 PathVerb::Quad => {
355 self.points_index += 2;
356 self.last_point = self.path.points[self.points_index - 1];
357 Some(PathSegment::QuadTo(
358 self.path.points[self.points_index - 2],
359 self.last_point,
360 ))
361 }
362 PathVerb::Cubic => {
363 self.points_index += 3;
364 self.last_point = self.path.points[self.points_index - 1];
365 Some(PathSegment::CubicTo(
366 self.path.points[self.points_index - 3],
367 self.path.points[self.points_index - 2],
368 self.last_point,
369 ))
370 }
371 PathVerb::Close => {
372 let seg = self.auto_close();
373 self.last_point = self.last_move_to;
374 Some(seg)
375 }
376 }
377 } else {
378 None
379 }
380 }
381}
382