1 /*
2 * Copyright 2006 The Android Open Source Project
3 *
4 * Use of this source code is governed by a BSD-style license that can be
5 * found in the LICENSE file.
6 */
7
8 #ifndef SkGeometry_DEFINED
9 #define SkGeometry_DEFINED
10
11 #include "include/core/SkPoint.h"
12 #include "include/core/SkScalar.h"
13 #include "include/core/SkTypes.h"
14 #include "include/private/base/SkFloatingPoint.h"
15 #include "src/base/SkVx.h"
16
17 #include <cstring>
18
19 class SkMatrix;
20 struct SkRect;
21
from_point(const SkPoint & point)22 static inline skvx::float2 from_point(const SkPoint& point) {
23 return skvx::float2::Load(&point);
24 }
25
to_point(const skvx::float2 & x)26 static inline SkPoint to_point(const skvx::float2& x) {
27 SkPoint point;
28 x.store(&point);
29 return point;
30 }
31
times_2(const skvx::float2 & value)32 static skvx::float2 times_2(const skvx::float2& value) {
33 return value + value;
34 }
35
36 /** Given a quadratic equation Ax^2 + Bx + C = 0, return 0, 1, 2 roots for the
37 equation.
38 */
39 int SkFindUnitQuadRoots(SkScalar A, SkScalar B, SkScalar C, SkScalar roots[2]);
40
41 /** Measures the angle between two vectors, in the range [0, pi].
42 */
43 float SkMeasureAngleBetweenVectors(SkVector, SkVector);
44
45 /** Returns a new, arbitrarily scaled vector that bisects the given vectors. The returned bisector
46 will always point toward the interior of the provided vectors.
47 */
48 SkVector SkFindBisector(SkVector, SkVector);
49
50 ///////////////////////////////////////////////////////////////////////////////
51
52 SkPoint SkEvalQuadAt(const SkPoint src[3], SkScalar t);
53 SkPoint SkEvalQuadTangentAt(const SkPoint src[3], SkScalar t);
54
55 /** Set pt to the point on the src quadratic specified by t. t must be
56 0 <= t <= 1.0
57 */
58 void SkEvalQuadAt(const SkPoint src[3], SkScalar t, SkPoint* pt, SkVector* tangent = nullptr);
59
60 /** Given a src quadratic bezier, chop it at the specified t value,
61 where 0 < t < 1, and return the two new quadratics in dst:
62 dst[0..2] and dst[2..4]
63 */
64 void SkChopQuadAt(const SkPoint src[3], SkPoint dst[5], SkScalar t);
65
66 /** Given a src quadratic bezier, chop it at the specified t == 1/2,
67 The new quads are returned in dst[0..2] and dst[2..4]
68 */
69 void SkChopQuadAtHalf(const SkPoint src[3], SkPoint dst[5]);
70
71 /** Measures the rotation of the given quadratic curve in radians.
72
73 Rotation is perhaps easiest described via a driving analogy: If you drive your car along the
74 curve from p0 to p2, then by the time you arrive at p2, how many radians will your car have
75 rotated? For a quadratic this is the same as the vector inside the tangents at the endpoints.
76
77 Quadratics can have rotations in the range [0, pi].
78 */
SkMeasureQuadRotation(const SkPoint pts[3])79 inline float SkMeasureQuadRotation(const SkPoint pts[3]) {
80 return SkMeasureAngleBetweenVectors(pts[1] - pts[0], pts[2] - pts[1]);
81 }
82
83 /** Given a src quadratic bezier, returns the T value whose tangent angle is halfway between the
84 tangents at p0 and p3.
85 */
86 float SkFindQuadMidTangent(const SkPoint src[3]);
87
88 /** Given a src quadratic bezier, chop it at the tangent whose angle is halfway between the
89 tangents at p0 and p2. The new quads are returned in dst[0..2] and dst[2..4].
90 */
SkChopQuadAtMidTangent(const SkPoint src[3],SkPoint dst[5])91 inline void SkChopQuadAtMidTangent(const SkPoint src[3], SkPoint dst[5]) {
92 SkChopQuadAt(src, dst, SkFindQuadMidTangent(src));
93 }
94
95 /** Given the 3 coefficients for a quadratic bezier (either X or Y values), look
96 for extrema, and return the number of t-values that are found that represent
97 these extrema. If the quadratic has no extrema betwee (0..1) exclusive, the
98 function returns 0.
99 Returned count tValues[]
100 0 ignored
101 1 0 < tValues[0] < 1
102 */
103 int SkFindQuadExtrema(SkScalar a, SkScalar b, SkScalar c, SkScalar tValues[1]);
104
105 /** Given 3 points on a quadratic bezier, chop it into 1, 2 beziers such that
106 the resulting beziers are monotonic in Y. This is called by the scan converter.
107 Depending on what is returned, dst[] is treated as follows
108 0 dst[0..2] is the original quad
109 1 dst[0..2] and dst[2..4] are the two new quads
110 */
111 int SkChopQuadAtYExtrema(const SkPoint src[3], SkPoint dst[5]);
112 int SkChopQuadAtXExtrema(const SkPoint src[3], SkPoint dst[5]);
113
114 /** Given 3 points on a quadratic bezier, if the point of maximum
115 curvature exists on the segment, returns the t value for this
116 point along the curve. Otherwise it will return a value of 0.
117 */
118 SkScalar SkFindQuadMaxCurvature(const SkPoint src[3]);
119
120 /** Given 3 points on a quadratic bezier, divide it into 2 quadratics
121 if the point of maximum curvature exists on the quad segment.
122 Depending on what is returned, dst[] is treated as follows
123 1 dst[0..2] is the original quad
124 2 dst[0..2] and dst[2..4] are the two new quads
125 If dst == null, it is ignored and only the count is returned.
126 */
127 int SkChopQuadAtMaxCurvature(const SkPoint src[3], SkPoint dst[5]);
128
129 /** Given 3 points on a quadratic bezier, use degree elevation to
130 convert it into the cubic fitting the same curve. The new cubic
131 curve is returned in dst[0..3].
132 */
133 void SkConvertQuadToCubic(const SkPoint src[3], SkPoint dst[4]);
134
135 ///////////////////////////////////////////////////////////////////////////////
136
137 /** Set pt to the point on the src cubic specified by t. t must be
138 0 <= t <= 1.0
139 */
140 void SkEvalCubicAt(const SkPoint src[4], SkScalar t, SkPoint* locOrNull,
141 SkVector* tangentOrNull, SkVector* curvatureOrNull);
142
143 /** Given a src cubic bezier, chop it at the specified t value,
144 where 0 <= t <= 1, and return the two new cubics in dst:
145 dst[0..3] and dst[3..6]
146 */
147 void SkChopCubicAt(const SkPoint src[4], SkPoint dst[7], SkScalar t);
148
149 /** Given a src cubic bezier, chop it at the specified t0 and t1 values,
150 where 0 <= t0 <= t1 <= 1, and return the three new cubics in dst:
151 dst[0..3], dst[3..6], and dst[6..9]
152 */
153 void SkChopCubicAt(const SkPoint src[4], SkPoint dst[10], float t0, float t1);
154
155 /** Given a src cubic bezier, chop it at the specified t values,
156 where 0 <= t0 <= t1 <= ... <= 1, and return the new cubics in dst:
157 dst[0..3],dst[3..6],...,dst[3*t_count..3*(t_count+1)]
158 */
159 void SkChopCubicAt(const SkPoint src[4], SkPoint dst[], const SkScalar t[],
160 int t_count);
161
162 /** Given a src cubic bezier, chop it at the specified t == 1/2,
163 The new cubics are returned in dst[0..3] and dst[3..6]
164 */
165 void SkChopCubicAtHalf(const SkPoint src[4], SkPoint dst[7]);
166
167 /** Given a cubic curve with no inflection points, this method measures the rotation in radians.
168
169 Rotation is perhaps easiest described via a driving analogy: If you drive your car along the
170 curve from p0 to p3, then by the time you arrive at p3, how many radians will your car have
171 rotated? This is not quite the same as the vector inside the tangents at the endpoints, even
172 without inflection, because the curve might rotate around the outside of the
173 tangents (>= 180 degrees) or the inside (<= 180 degrees).
174
175 Cubics can have rotations in the range [0, 2*pi].
176
177 NOTE: The caller must either call SkChopCubicAtInflections or otherwise prove that the provided
178 cubic has no inflection points prior to calling this method.
179 */
180 float SkMeasureNonInflectCubicRotation(const SkPoint[4]);
181
182 /** Given a src cubic bezier, returns the T value whose tangent angle is halfway between the
183 tangents at p0 and p3.
184 */
185 float SkFindCubicMidTangent(const SkPoint src[4]);
186
187 /** Given a src cubic bezier, chop it at the tangent whose angle is halfway between the
188 tangents at p0 and p3. The new cubics are returned in dst[0..3] and dst[3..6].
189
190 NOTE: 0- and 360-degree flat lines don't have single points of midtangent.
191 (tangent == midtangent at every point on these curves except the cusp points.)
192 If this is the case then we simply chop at a point which guarantees neither side rotates more
193 than 180 degrees.
194 */
SkChopCubicAtMidTangent(const SkPoint src[4],SkPoint dst[7])195 inline void SkChopCubicAtMidTangent(const SkPoint src[4], SkPoint dst[7]) {
196 SkChopCubicAt(src, dst, SkFindCubicMidTangent(src));
197 }
198
199 /** Given the 4 coefficients for a cubic bezier (either X or Y values), look
200 for extrema, and return the number of t-values that are found that represent
201 these extrema. If the cubic has no extrema betwee (0..1) exclusive, the
202 function returns 0.
203 Returned count tValues[]
204 0 ignored
205 1 0 < tValues[0] < 1
206 2 0 < tValues[0] < tValues[1] < 1
207 */
208 int SkFindCubicExtrema(SkScalar a, SkScalar b, SkScalar c, SkScalar d,
209 SkScalar tValues[2]);
210
211 /** Given 4 points on a cubic bezier, chop it into 1, 2, 3 beziers such that
212 the resulting beziers are monotonic in Y. This is called by the scan converter.
213 Depending on what is returned, dst[] is treated as follows
214 0 dst[0..3] is the original cubic
215 1 dst[0..3] and dst[3..6] are the two new cubics
216 2 dst[0..3], dst[3..6], dst[6..9] are the three new cubics
217 If dst == null, it is ignored and only the count is returned.
218 */
219 int SkChopCubicAtYExtrema(const SkPoint src[4], SkPoint dst[10]);
220 int SkChopCubicAtXExtrema(const SkPoint src[4], SkPoint dst[10]);
221
222 /** Given a cubic bezier, return 0, 1, or 2 t-values that represent the
223 inflection points.
224 */
225 int SkFindCubicInflections(const SkPoint src[4], SkScalar tValues[2]);
226
227 /** Return 1 for no chop, 2 for having chopped the cubic at a single
228 inflection point, 3 for having chopped at 2 inflection points.
229 dst will hold the resulting 1, 2, or 3 cubics.
230 */
231 int SkChopCubicAtInflections(const SkPoint src[4], SkPoint dst[10]);
232
233 int SkFindCubicMaxCurvature(const SkPoint src[4], SkScalar tValues[3]);
234 int SkChopCubicAtMaxCurvature(const SkPoint src[4], SkPoint dst[13],
235 SkScalar tValues[3] = nullptr);
236 /** Returns t value of cusp if cubic has one; returns -1 otherwise.
237 */
238 SkScalar SkFindCubicCusp(const SkPoint src[4]);
239
240 /** Given a monotonically increasing or decreasing cubic bezier src, chop it
241 * where the X value is the specified value. The returned cubics will be in
242 * dst, sharing the middle point. That is, the first cubic is dst[0..3] and
243 * the second dst[3..6].
244 *
245 * If the cubic provided is *not* monotone, it will be chopped at the first
246 * time the curve has the specified X value.
247 *
248 * If the cubic never reaches the specified value, the function returns false.
249 */
250 bool SkChopMonoCubicAtX(const SkPoint src[4], SkScalar x, SkPoint dst[7]);
251
252 /** Given a monotonically increasing or decreasing cubic bezier src, chop it
253 * where the Y value is the specified value. The returned cubics will be in
254 * dst, sharing the middle point. That is, the first cubic is dst[0..3] and
255 * the second dst[3..6].
256 *
257 * If the cubic provided is *not* monotone, it will be chopped at the first
258 * time the curve has the specified Y value.
259 *
260 * If the cubic never reaches the specified value, the function returns false.
261 */
262 bool SkChopMonoCubicAtY(const SkPoint src[4], SkScalar y, SkPoint dst[7]);
263
264 enum class SkCubicType {
265 kSerpentine,
266 kLoop,
267 kLocalCusp, // Cusp at a non-infinite parameter value with an inflection at t=infinity.
268 kCuspAtInfinity, // Cusp with a cusp at t=infinity and a local inflection.
269 kQuadratic,
270 kLineOrPoint
271 };
272
SkCubicIsDegenerate(SkCubicType type)273 static inline bool SkCubicIsDegenerate(SkCubicType type) {
274 switch (type) {
275 case SkCubicType::kSerpentine:
276 case SkCubicType::kLoop:
277 case SkCubicType::kLocalCusp:
278 case SkCubicType::kCuspAtInfinity:
279 return false;
280 case SkCubicType::kQuadratic:
281 case SkCubicType::kLineOrPoint:
282 return true;
283 }
284 SK_ABORT("Invalid SkCubicType");
285 }
286
SkCubicTypeName(SkCubicType type)287 static inline const char* SkCubicTypeName(SkCubicType type) {
288 switch (type) {
289 case SkCubicType::kSerpentine: return "kSerpentine";
290 case SkCubicType::kLoop: return "kLoop";
291 case SkCubicType::kLocalCusp: return "kLocalCusp";
292 case SkCubicType::kCuspAtInfinity: return "kCuspAtInfinity";
293 case SkCubicType::kQuadratic: return "kQuadratic";
294 case SkCubicType::kLineOrPoint: return "kLineOrPoint";
295 }
296 SK_ABORT("Invalid SkCubicType");
297 }
298
299 /** Returns the cubic classification.
300
301 t[],s[] are set to the two homogeneous parameter values at which points the lines L & M
302 intersect with K, sorted from smallest to largest and oriented so positive values of the
303 implicit are on the "left" side. For a serpentine curve they are the inflection points. For a
304 loop they are the double point. For a local cusp, they are both equal and denote the cusp point.
305 For a cusp at an infinite parameter value, one will be the local inflection point and the other
306 +inf (t,s = 1,0). If the curve is degenerate (i.e. quadratic or linear) they are both set to a
307 parameter value of +inf (t,s = 1,0).
308
309 d[] is filled with the cubic inflection function coefficients. See "Resolution Independent
310 Curve Rendering using Programmable Graphics Hardware", 4.2 Curve Categorization:
311
312 If the input points contain infinities or NaN, the return values are undefined.
313
314 https://www.microsoft.com/en-us/research/wp-content/uploads/2005/01/p1000-loop.pdf
315 */
316 SkCubicType SkClassifyCubic(const SkPoint p[4], double t[2] = nullptr, double s[2] = nullptr,
317 double d[4] = nullptr);
318
319 ///////////////////////////////////////////////////////////////////////////////
320
321 enum SkRotationDirection {
322 kCW_SkRotationDirection,
323 kCCW_SkRotationDirection
324 };
325
326 struct SkConic {
SkConicSkConic327 SkConic() {}
SkConicSkConic328 SkConic(const SkPoint& p0, const SkPoint& p1, const SkPoint& p2, SkScalar w) {
329 this->set(p0, p1, p2, w);
330 }
331
SkConicSkConic332 SkConic(const SkPoint pts[3], SkScalar w) {
333 this->set(pts, w);
334 }
335
336 SkPoint fPts[3];
337 SkScalar fW;
338
setSkConic339 void set(const SkPoint pts[3], SkScalar w) {
340 memcpy(fPts, pts, 3 * sizeof(SkPoint));
341 this->setW(w);
342 }
343
setSkConic344 void set(const SkPoint& p0, const SkPoint& p1, const SkPoint& p2, SkScalar w) {
345 fPts[0] = p0;
346 fPts[1] = p1;
347 fPts[2] = p2;
348 this->setW(w);
349 }
350
setWSkConic351 void setW(SkScalar w) {
352 if (SkIsFinite(w)) {
353 SkASSERT(w > 0);
354 }
355
356 // Guard against bad weights by forcing them to 1.
357 fW = w > 0 && SkIsFinite(w) ? w : 1;
358 }
359
360 /**
361 * Given a t-value [0...1] return its position and/or tangent.
362 * If pos is not null, return its position at the t-value.
363 * If tangent is not null, return its tangent at the t-value. NOTE the
364 * tangent value's length is arbitrary, and only its direction should
365 * be used.
366 */
367 void evalAt(SkScalar t, SkPoint* pos, SkVector* tangent = nullptr) const;
368 [[nodiscard]] bool chopAt(SkScalar t, SkConic dst[2]) const;
369 void chopAt(SkScalar t1, SkScalar t2, SkConic* dst) const;
370 void chop(SkConic dst[2]) const;
371
372 SkPoint evalAt(SkScalar t) const;
373 SkVector evalTangentAt(SkScalar t) const;
374
375 void computeAsQuadError(SkVector* err) const;
376 bool asQuadTol(SkScalar tol) const;
377
378 /**
379 * return the power-of-2 number of quads needed to approximate this conic
380 * with a sequence of quads. Will be >= 0.
381 */
382 int SK_SPI computeQuadPOW2(SkScalar tol) const;
383
384 /**
385 * Chop this conic into N quads, stored continguously in pts[], where
386 * N = 1 << pow2. The amount of storage needed is (1 + 2 * N)
387 */
388 [[nodiscard]] int SK_SPI chopIntoQuadsPOW2(SkPoint pts[], int pow2) const;
389
390 float findMidTangent() const;
391 bool findXExtrema(SkScalar* t) const;
392 bool findYExtrema(SkScalar* t) const;
393 bool chopAtXExtrema(SkConic dst[2]) const;
394 bool chopAtYExtrema(SkConic dst[2]) const;
395
396 void computeTightBounds(SkRect* bounds) const;
397 void computeFastBounds(SkRect* bounds) const;
398
399 /** Find the parameter value where the conic takes on its maximum curvature.
400 *
401 * @param t output scalar for max curvature. Will be unchanged if
402 * max curvature outside 0..1 range.
403 *
404 * @return true if max curvature found inside 0..1 range, false otherwise
405 */
406 // bool findMaxCurvature(SkScalar* t) const; // unimplemented
407
408 static SkScalar TransformW(const SkPoint[3], SkScalar w, const SkMatrix&);
409
410 enum {
411 kMaxConicsForArc = 5
412 };
413 static int BuildUnitArc(const SkVector& start, const SkVector& stop, SkRotationDirection,
414 const SkMatrix*, SkConic conics[kMaxConicsForArc]);
415 };
416
417 // inline helpers are contained in a namespace to avoid external leakage to fragile SkVx members
418 namespace { // NOLINT(google-build-namespaces)
419
420 /**
421 * use for : eval(t) == A * t^2 + B * t + C
422 */
423 struct SkQuadCoeff {
SkQuadCoeffSkQuadCoeff424 SkQuadCoeff() {}
425
SkQuadCoeffSkQuadCoeff426 SkQuadCoeff(const skvx::float2& A, const skvx::float2& B, const skvx::float2& C)
427 : fA(A)
428 , fB(B)
429 , fC(C)
430 {
431 }
432
SkQuadCoeffSkQuadCoeff433 SkQuadCoeff(const SkPoint src[3]) {
434 fC = from_point(src[0]);
435 auto P1 = from_point(src[1]);
436 auto P2 = from_point(src[2]);
437 fB = times_2(P1 - fC);
438 fA = P2 - times_2(P1) + fC;
439 }
440
evalSkQuadCoeff441 skvx::float2 eval(const skvx::float2& tt) {
442 return (fA * tt + fB) * tt + fC;
443 }
444
445 skvx::float2 fA;
446 skvx::float2 fB;
447 skvx::float2 fC;
448 };
449
450 struct SkConicCoeff {
SkConicCoeffSkConicCoeff451 SkConicCoeff(const SkConic& conic) {
452 skvx::float2 p0 = from_point(conic.fPts[0]);
453 skvx::float2 p1 = from_point(conic.fPts[1]);
454 skvx::float2 p2 = from_point(conic.fPts[2]);
455 skvx::float2 ww(conic.fW);
456
457 auto p1w = p1 * ww;
458 fNumer.fC = p0;
459 fNumer.fA = p2 - times_2(p1w) + p0;
460 fNumer.fB = times_2(p1w - p0);
461
462 fDenom.fC = 1;
463 fDenom.fB = times_2(ww - fDenom.fC);
464 fDenom.fA = 0 - fDenom.fB;
465 }
466
evalSkConicCoeff467 skvx::float2 eval(SkScalar t) {
468 skvx::float2 tt(t);
469 skvx::float2 numer = fNumer.eval(tt);
470 skvx::float2 denom = fDenom.eval(tt);
471 return numer / denom;
472 }
473
474 SkQuadCoeff fNumer;
475 SkQuadCoeff fDenom;
476 };
477
478 struct SkCubicCoeff {
SkCubicCoeffSkCubicCoeff479 SkCubicCoeff(const SkPoint src[4]) {
480 skvx::float2 P0 = from_point(src[0]);
481 skvx::float2 P1 = from_point(src[1]);
482 skvx::float2 P2 = from_point(src[2]);
483 skvx::float2 P3 = from_point(src[3]);
484 skvx::float2 three(3);
485 fA = P3 + three * (P1 - P2) - P0;
486 fB = three * (P2 - times_2(P1) + P0);
487 fC = three * (P1 - P0);
488 fD = P0;
489 }
490
evalSkCubicCoeff491 skvx::float2 eval(const skvx::float2& t) {
492 return ((fA * t + fB) * t + fC) * t + fD;
493 }
494
495 skvx::float2 fA;
496 skvx::float2 fB;
497 skvx::float2 fC;
498 skvx::float2 fD;
499 };
500
501 } // namespace
502
503 #include "include/private/base/SkTemplates.h"
504
505 /**
506 * Help class to allocate storage for approximating a conic with N quads.
507 */
508 class SkAutoConicToQuads {
509 public:
SkAutoConicToQuads()510 SkAutoConicToQuads() : fQuadCount(0) {}
511
512 /**
513 * Given a conic and a tolerance, return the array of points for the
514 * approximating quad(s). Call countQuads() to know the number of quads
515 * represented in these points.
516 *
517 * The quads are allocated to share end-points. e.g. if there are 4 quads,
518 * there will be 9 points allocated as follows
519 * quad[0] == pts[0..2]
520 * quad[1] == pts[2..4]
521 * quad[2] == pts[4..6]
522 * quad[3] == pts[6..8]
523 */
computeQuads(const SkConic & conic,SkScalar tol)524 const SkPoint* computeQuads(const SkConic& conic, SkScalar tol) {
525 int pow2 = conic.computeQuadPOW2(tol);
526 fQuadCount = 1 << pow2;
527 SkPoint* pts = fStorage.reset(1 + 2 * fQuadCount);
528 fQuadCount = conic.chopIntoQuadsPOW2(pts, pow2);
529 return pts;
530 }
531
computeQuads(const SkPoint pts[3],SkScalar weight,SkScalar tol)532 const SkPoint* computeQuads(const SkPoint pts[3], SkScalar weight,
533 SkScalar tol) {
534 SkConic conic;
535 conic.set(pts, weight);
536 return computeQuads(conic, tol);
537 }
538
countQuads()539 int countQuads() const { return fQuadCount; }
540
541 private:
542 enum {
543 kQuadCount = 8, // should handle most conics
544 kPointCount = 1 + 2 * kQuadCount,
545 };
546 skia_private::AutoSTMalloc<kPointCount, SkPoint> fStorage;
547 int fQuadCount; // #quads for current usage
548 };
549
550 #endif
551