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