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