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 /** Returns the cubic classification. 171 172 t[],s[] are set to the two homogeneous parameter values at which points the lines L & M 173 intersect with K, sorted from smallest to largest and oriented so positive values of the 174 implicit are on the "left" side. For a serpentine curve they are the inflection points. For a 175 loop they are the double point. For a local cusp, they are both equal and denote the cusp point. 176 For a cusp at an infinite parameter value, one will be the local inflection point and the other 177 +inf (t,s = 1,0). If the curve is degenerate (i.e. quadratic or linear) they are both set to a 178 parameter value of +inf (t,s = 1,0). 179 180 d[] is filled with the cubic inflection function coefficients. See "Resolution Independent 181 Curve Rendering using Programmable Graphics Hardware", 4.2 Curve Categorization: 182 183 https://www.microsoft.com/en-us/research/wp-content/uploads/2005/01/p1000-loop.pdf 184 */ 185 SkCubicType SkClassifyCubic(const SkPoint p[4], double t[2] = nullptr, double s[2] = nullptr, 186 double d[4] = nullptr); 187 188 /////////////////////////////////////////////////////////////////////////////// 189 190 enum SkRotationDirection { 191 kCW_SkRotationDirection, 192 kCCW_SkRotationDirection 193 }; 194 195 struct SkConic { 196 SkConic() {} 197 SkConic(const SkPoint& p0, const SkPoint& p1, const SkPoint& p2, SkScalar w) { 198 fPts[0] = p0; 199 fPts[1] = p1; 200 fPts[2] = p2; 201 fW = w; 202 } 203 SkConic(const SkPoint pts[3], SkScalar w) { 204 memcpy(fPts, pts, sizeof(fPts)); 205 fW = w; 206 } 207 208 SkPoint fPts[3]; 209 SkScalar fW; 210 211 void set(const SkPoint pts[3], SkScalar w) { 212 memcpy(fPts, pts, 3 * sizeof(SkPoint)); 213 fW = w; 214 } 215 216 void set(const SkPoint& p0, const SkPoint& p1, const SkPoint& p2, SkScalar w) { 217 fPts[0] = p0; 218 fPts[1] = p1; 219 fPts[2] = p2; 220 fW = w; 221 } 222 223 /** 224 * Given a t-value [0...1] return its position and/or tangent. 225 * If pos is not null, return its position at the t-value. 226 * If tangent is not null, return its tangent at the t-value. NOTE the 227 * tangent value's length is arbitrary, and only its direction should 228 * be used. 229 */ 230 void evalAt(SkScalar t, SkPoint* pos, SkVector* tangent = nullptr) const; 231 bool SK_WARN_UNUSED_RESULT chopAt(SkScalar t, SkConic dst[2]) const; 232 void chopAt(SkScalar t1, SkScalar t2, SkConic* dst) const; 233 void chop(SkConic dst[2]) const; 234 235 SkPoint evalAt(SkScalar t) const; 236 SkVector evalTangentAt(SkScalar t) const; 237 238 void computeAsQuadError(SkVector* err) const; 239 bool asQuadTol(SkScalar tol) const; 240 241 /** 242 * return the power-of-2 number of quads needed to approximate this conic 243 * with a sequence of quads. Will be >= 0. 244 */ 245 int computeQuadPOW2(SkScalar tol) const; 246 247 /** 248 * Chop this conic into N quads, stored continguously in pts[], where 249 * N = 1 << pow2. The amount of storage needed is (1 + 2 * N) 250 */ 251 int SK_WARN_UNUSED_RESULT chopIntoQuadsPOW2(SkPoint pts[], int pow2) const; 252 253 bool findXExtrema(SkScalar* t) const; 254 bool findYExtrema(SkScalar* t) const; 255 bool chopAtXExtrema(SkConic dst[2]) const; 256 bool chopAtYExtrema(SkConic dst[2]) const; 257 258 void computeTightBounds(SkRect* bounds) const; 259 void computeFastBounds(SkRect* bounds) const; 260 261 /** Find the parameter value where the conic takes on its maximum curvature. 262 * 263 * @param t output scalar for max curvature. Will be unchanged if 264 * max curvature outside 0..1 range. 265 * 266 * @return true if max curvature found inside 0..1 range, false otherwise 267 */ 268 // bool findMaxCurvature(SkScalar* t) const; // unimplemented 269 270 static SkScalar TransformW(const SkPoint[3], SkScalar w, const SkMatrix&); 271 272 enum { 273 kMaxConicsForArc = 5 274 }; 275 static int BuildUnitArc(const SkVector& start, const SkVector& stop, SkRotationDirection, 276 const SkMatrix*, SkConic conics[kMaxConicsForArc]); 277 }; 278 279 // inline helpers are contained in a namespace to avoid external leakage to fragile SkNx members 280 namespace { 281 282 /** 283 * use for : eval(t) == A * t^2 + B * t + C 284 */ 285 struct SkQuadCoeff { 286 SkQuadCoeff() {} 287 288 SkQuadCoeff(const Sk2s& A, const Sk2s& B, const Sk2s& C) 289 : fA(A) 290 , fB(B) 291 , fC(C) 292 { 293 } 294 295 SkQuadCoeff(const SkPoint src[3]) { 296 fC = from_point(src[0]); 297 Sk2s P1 = from_point(src[1]); 298 Sk2s P2 = from_point(src[2]); 299 fB = times_2(P1 - fC); 300 fA = P2 - times_2(P1) + fC; 301 } 302 303 Sk2s eval(SkScalar t) { 304 Sk2s tt(t); 305 return eval(tt); 306 } 307 308 Sk2s eval(const Sk2s& tt) { 309 return (fA * tt + fB) * tt + fC; 310 } 311 312 Sk2s fA; 313 Sk2s fB; 314 Sk2s fC; 315 }; 316 317 struct SkConicCoeff { 318 SkConicCoeff(const SkConic& conic) { 319 Sk2s p0 = from_point(conic.fPts[0]); 320 Sk2s p1 = from_point(conic.fPts[1]); 321 Sk2s p2 = from_point(conic.fPts[2]); 322 Sk2s ww(conic.fW); 323 324 Sk2s p1w = p1 * ww; 325 fNumer.fC = p0; 326 fNumer.fA = p2 - times_2(p1w) + p0; 327 fNumer.fB = times_2(p1w - p0); 328 329 fDenom.fC = Sk2s(1); 330 fDenom.fB = times_2(ww - fDenom.fC); 331 fDenom.fA = Sk2s(0) - fDenom.fB; 332 } 333 334 Sk2s eval(SkScalar t) { 335 Sk2s tt(t); 336 Sk2s numer = fNumer.eval(tt); 337 Sk2s denom = fDenom.eval(tt); 338 return numer / denom; 339 } 340 341 SkQuadCoeff fNumer; 342 SkQuadCoeff fDenom; 343 }; 344 345 struct SkCubicCoeff { 346 SkCubicCoeff(const SkPoint src[4]) { 347 Sk2s P0 = from_point(src[0]); 348 Sk2s P1 = from_point(src[1]); 349 Sk2s P2 = from_point(src[2]); 350 Sk2s P3 = from_point(src[3]); 351 Sk2s three(3); 352 fA = P3 + three * (P1 - P2) - P0; 353 fB = three * (P2 - times_2(P1) + P0); 354 fC = three * (P1 - P0); 355 fD = P0; 356 } 357 358 Sk2s eval(SkScalar t) { 359 Sk2s tt(t); 360 return eval(tt); 361 } 362 363 Sk2s eval(const Sk2s& t) { 364 return ((fA * t + fB) * t + fC) * t + fD; 365 } 366 367 Sk2s fA; 368 Sk2s fB; 369 Sk2s fC; 370 Sk2s fD; 371 }; 372 373 } 374 375 #include "SkTemplates.h" 376 377 /** 378 * Help class to allocate storage for approximating a conic with N quads. 379 */ 380 class SkAutoConicToQuads { 381 public: 382 SkAutoConicToQuads() : fQuadCount(0) {} 383 384 /** 385 * Given a conic and a tolerance, return the array of points for the 386 * approximating quad(s). Call countQuads() to know the number of quads 387 * represented in these points. 388 * 389 * The quads are allocated to share end-points. e.g. if there are 4 quads, 390 * there will be 9 points allocated as follows 391 * quad[0] == pts[0..2] 392 * quad[1] == pts[2..4] 393 * quad[2] == pts[4..6] 394 * quad[3] == pts[6..8] 395 */ 396 const SkPoint* computeQuads(const SkConic& conic, SkScalar tol) { 397 int pow2 = conic.computeQuadPOW2(tol); 398 fQuadCount = 1 << pow2; 399 SkPoint* pts = fStorage.reset(1 + 2 * fQuadCount); 400 fQuadCount = conic.chopIntoQuadsPOW2(pts, pow2); 401 return pts; 402 } 403 404 const SkPoint* computeQuads(const SkPoint pts[3], SkScalar weight, 405 SkScalar tol) { 406 SkConic conic; 407 conic.set(pts, weight); 408 return computeQuads(conic, tol); 409 } 410 411 int countQuads() const { return fQuadCount; } 412 413 private: 414 enum { 415 kQuadCount = 8, // should handle most conics 416 kPointCount = 1 + 2 * kQuadCount, 417 }; 418 SkAutoSTMalloc<kPointCount, SkPoint> fStorage; 419 int fQuadCount; // #quads for current usage 420 }; 421 422 #endif 423
