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