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 tiny_skia_path::{NormalizedF32, NormalizedF32Exclusive, Point};
8
9#[cfg(all(not(feature = "std"), feature = "no-std-float"))]
10use tiny_skia_path::NoStdFloat;
11
12pub use tiny_skia_path::path_geometry::{
13 chop_cubic_at2, chop_quad_at, find_cubic_max_curvature, find_unit_quad_roots, new_t_values,
14 CubicCoeff, QuadCoeff,
15};
16
17use tiny_skia_path::path_geometry::valid_unit_divide;
18
19// TODO: return custom type
20/// Returns 0 for 1 quad, and 1 for two quads, either way the answer is stored in dst[].
21///
22/// Guarantees that the 1/2 quads will be monotonic.
23pub fn chop_quad_at_x_extrema(src: &[Point; 3], dst: &mut [Point; 5]) -> usize {
24 let a = src[0].x;
25 let mut b = src[1].x;
26 let c = src[2].x;
27
28 if is_not_monotonic(a, b, c) {
29 if let Some(t_value) = valid_unit_divide(a - b, a - b - b + c) {
30 chop_quad_at(src, t_value, dst);
31
32 // flatten double quad extrema
33 dst[1].x = dst[2].x;
34 dst[3].x = dst[2].x;
35
36 return 1;
37 }
38
39 // if we get here, we need to force dst to be monotonic, even though
40 // we couldn't compute a unit_divide value (probably underflow).
41 b = if (a - b).abs() < (b - c).abs() { a } else { c };
42 }
43
44 dst[0] = Point::from_xy(a, src[0].y);
45 dst[1] = Point::from_xy(b, src[1].y);
46 dst[2] = Point::from_xy(c, src[2].y);
47 0
48}
49
50/// Returns 0 for 1 quad, and 1 for two quads, either way the answer is stored in dst[].
51///
52/// Guarantees that the 1/2 quads will be monotonic.
53pub fn chop_quad_at_y_extrema(src: &[Point; 3], dst: &mut [Point; 5]) -> usize {
54 let a = src[0].y;
55 let mut b = src[1].y;
56 let c = src[2].y;
57
58 if is_not_monotonic(a, b, c) {
59 if let Some(t_value) = valid_unit_divide(a - b, a - b - b + c) {
60 chop_quad_at(src, t_value, dst);
61
62 // flatten double quad extrema
63 dst[1].y = dst[2].y;
64 dst[3].y = dst[2].y;
65
66 return 1;
67 }
68
69 // if we get here, we need to force dst to be monotonic, even though
70 // we couldn't compute a unit_divide value (probably underflow).
71 b = if (a - b).abs() < (b - c).abs() { a } else { c };
72 }
73
74 dst[0] = Point::from_xy(src[0].x, a);
75 dst[1] = Point::from_xy(src[1].x, b);
76 dst[2] = Point::from_xy(src[2].x, c);
77 0
78}
79
80fn is_not_monotonic(a: f32, b: f32, c: f32) -> bool {
81 let ab: f32 = a - b;
82 let mut bc: f32 = b - c;
83 if ab < 0.0 {
84 bc = -bc;
85 }
86
87 ab == 0.0 || bc < 0.0
88}
89
90pub fn chop_cubic_at_x_extrema(src: &[Point; 4], dst: &mut [Point; 10]) -> usize {
91 let mut t_values: [NormalizedF32Exclusive; 3] = new_t_values();
92 let t_values: &[NormalizedF32Exclusive] = find_cubic_extrema(a:src[0].x, b:src[1].x, c:src[2].x, d:src[3].x, &mut t_values);
93
94 chop_cubic_at(src, t_values, dst);
95 if !t_values.is_empty() {
96 // we do some cleanup to ensure our X extrema are flat
97 dst[2].x = dst[3].x;
98 dst[4].x = dst[3].x;
99 if t_values.len() == 2 {
100 dst[5].x = dst[6].x;
101 dst[7].x = dst[6].x;
102 }
103 }
104
105 t_values.len()
106}
107
108/// Given 4 points on a cubic bezier, chop it into 1, 2, 3 beziers such that
109/// the resulting beziers are monotonic in Y.
110///
111/// This is called by the scan converter.
112///
113/// Depending on what is returned, dst[] is treated as follows:
114///
115/// - 0: dst[0..3] is the original cubic
116/// - 1: dst[0..3] and dst[3..6] are the two new cubics
117/// - 2: dst[0..3], dst[3..6], dst[6..9] are the three new cubics
118pub fn chop_cubic_at_y_extrema(src: &[Point; 4], dst: &mut [Point; 10]) -> usize {
119 let mut t_values: [NormalizedF32Exclusive; 3] = new_t_values();
120 let t_values: &[NormalizedF32Exclusive] = find_cubic_extrema(a:src[0].y, b:src[1].y, c:src[2].y, d:src[3].y, &mut t_values);
121
122 chop_cubic_at(src, t_values, dst);
123 if !t_values.is_empty() {
124 // we do some cleanup to ensure our Y extrema are flat
125 dst[2].y = dst[3].y;
126 dst[4].y = dst[3].y;
127 if t_values.len() == 2 {
128 dst[5].y = dst[6].y;
129 dst[7].y = dst[6].y;
130 }
131 }
132
133 t_values.len()
134}
135
136// Cubic'(t) = At^2 + Bt + C, where
137// A = 3(-a + 3(b - c) + d)
138// B = 6(a - 2b + c)
139// C = 3(b - a)
140// Solve for t, keeping only those that fit between 0 < t < 1
141fn find_cubic_extrema(
142 a: f32,
143 b: f32,
144 c: f32,
145 d: f32,
146 t_values: &mut [NormalizedF32Exclusive; 3],
147) -> &[NormalizedF32Exclusive] {
148 // we divide A,B,C by 3 to simplify
149 let na: f32 = d - a + 3.0 * (b - c);
150 let nb: f32 = 2.0 * (a - b - b + c);
151 let nc: f32 = b - a;
152
153 let roots: usize = find_unit_quad_roots(a:na, b:nb, c:nc, roots:t_values);
154 &t_values[0..roots]
155}
156
157// http://code.google.com/p/skia/issues/detail?id=32
158//
159// This test code would fail when we didn't check the return result of
160// valid_unit_divide in SkChopCubicAt(... NormalizedF32Exclusives[], int roots). The reason is
161// that after the first chop, the parameters to valid_unit_divide are equal
162// (thanks to finite float precision and rounding in the subtracts). Thus
163// even though the 2nd NormalizedF32Exclusive looks < 1.0, after we renormalize it, we end
164// up with 1.0, hence the need to check and just return the last cubic as
165// a degenerate clump of 4 points in the same place.
166pub fn chop_cubic_at(src: &[Point; 4], t_values: &[NormalizedF32Exclusive], dst: &mut [Point]) {
167 if t_values.is_empty() {
168 // nothing to chop
169 dst[0] = src[0];
170 dst[1] = src[1];
171 dst[2] = src[2];
172 dst[3] = src[3];
173 } else {
174 let mut t = t_values[0];
175 let mut tmp = [Point::zero(); 4];
176
177 // Reduce the `src` lifetime, so we can use `src = &tmp` later.
178 let mut src = src;
179
180 let mut dst_offset = 0;
181 for i in 0..t_values.len() {
182 chop_cubic_at2(src, t, &mut dst[dst_offset..]);
183 if i == t_values.len() - 1 {
184 break;
185 }
186
187 dst_offset += 3;
188 // have src point to the remaining cubic (after the chop)
189 tmp[0] = dst[dst_offset + 0];
190 tmp[1] = dst[dst_offset + 1];
191 tmp[2] = dst[dst_offset + 2];
192 tmp[3] = dst[dst_offset + 3];
193 src = &tmp;
194
195 // watch out in case the renormalized t isn't in range
196 let n = valid_unit_divide(
197 t_values[i + 1].get() - t_values[i].get(),
198 1.0 - t_values[i].get(),
199 );
200
201 match n {
202 Some(n) => t = n,
203 None => {
204 // if we can't, just create a degenerate cubic
205 dst[dst_offset + 4] = src[3];
206 dst[dst_offset + 5] = src[3];
207 dst[dst_offset + 6] = src[3];
208 break;
209 }
210 }
211 }
212 }
213}
214
215pub fn chop_cubic_at_max_curvature(
216 src: &[Point; 4],
217 t_values: &mut [NormalizedF32Exclusive; 3],
218 dst: &mut [Point],
219) -> usize {
220 let mut roots: [NormalizedF32; 3] = [NormalizedF32::ZERO; 3];
221 let roots: &[NormalizedF32] = find_cubic_max_curvature(src, &mut roots);
222
223 // Throw out values not inside 0..1.
224 let mut count: usize = 0;
225 for root: &NormalizedF32 in roots {
226 if 0.0 < root.get() && root.get() < 1.0 {
227 t_values[count] = NormalizedF32Exclusive::new_bounded(root.get());
228 count += 1;
229 }
230 }
231
232 if count == 0 {
233 dst[0..4].copy_from_slice(src);
234 } else {
235 chop_cubic_at(src, &t_values[0..count], dst);
236 }
237
238 count + 1
239}
240
241pub fn chop_mono_cubic_at_x(src: &[Point; 4], x: f32, dst: &mut [Point; 7]) -> bool {
242 cubic_dchop_at_intercept(src, intercept:x, is_vertical:true, dst)
243}
244
245pub fn chop_mono_cubic_at_y(src: &[Point; 4], y: f32, dst: &mut [Point; 7]) -> bool {
246 cubic_dchop_at_intercept(src, intercept:y, is_vertical:false, dst)
247}
248
249fn cubic_dchop_at_intercept(
250 src: &[Point; 4],
251 intercept: f32,
252 is_vertical: bool,
253 dst: &mut [Point; 7],
254) -> bool {
255 use crate::path64::{cubic64::Cubic64, line_cubic_intersections, point64::Point64};
256
257 let src = [
258 Point64::from_point(src[0]),
259 Point64::from_point(src[1]),
260 Point64::from_point(src[2]),
261 Point64::from_point(src[3]),
262 ];
263
264 let cubic = Cubic64::new(src);
265 let mut roots = [0.0; 3];
266 let count = if is_vertical {
267 line_cubic_intersections::vertical_intersect(&cubic, f64::from(intercept), &mut roots)
268 } else {
269 line_cubic_intersections::horizontal_intersect(&cubic, f64::from(intercept), &mut roots)
270 };
271
272 if count > 0 {
273 let pair = cubic.chop_at(roots[0]);
274 for i in 0..7 {
275 dst[i] = pair.points[i].to_point();
276 }
277
278 true
279 } else {
280 false
281 }
282}
283
284#[cfg(test)]
285mod tests {
286 use super::*;
287
288 #[test]
289 fn chop_cubic_at_y_extrema_1() {
290 let src = [
291 Point::from_xy(10.0, 20.0),
292 Point::from_xy(67.0, 437.0),
293 Point::from_xy(298.0, 213.0),
294 Point::from_xy(401.0, 214.0),
295 ];
296
297 let mut dst = [Point::zero(); 10];
298 let n = chop_cubic_at_y_extrema(&src, &mut dst);
299 assert_eq!(n, 2);
300 assert_eq!(dst[0], Point::from_xy(10.0, 20.0));
301 assert_eq!(dst[1], Point::from_xy(37.508274, 221.24475));
302 assert_eq!(dst[2], Point::from_xy(105.541855, 273.19803));
303 assert_eq!(dst[3], Point::from_xy(180.15599, 273.19803));
304 assert_eq!(dst[4], Point::from_xy(259.80502, 273.19803));
305 assert_eq!(dst[5], Point::from_xy(346.9527, 213.99666));
306 assert_eq!(dst[6], Point::from_xy(400.30844, 213.99666));
307 assert_eq!(dst[7], Point::from_xy(400.53958, 213.99666));
308 assert_eq!(dst[8], Point::from_xy(400.7701, 213.99777));
309 assert_eq!(dst[9], Point::from_xy(401.0, 214.0));
310 }
311}
312