1/* 2 * Copyright 2008 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#include "SkStrokerPriv.h" 9#include "SkGeometry.h" 10#include "SkPathPriv.h" 11 12enum { 13 kTangent_RecursiveLimit, 14 kCubic_RecursiveLimit, 15 kConic_RecursiveLimit, 16 kQuad_RecursiveLimit 17}; 18 19// quads with extreme widths (e.g. (0,1) (1,6) (0,3) width=5e7) recurse to point of failure 20// largest seen for normal cubics : 5, 26 21// largest seen for normal quads : 11 22static const int kRecursiveLimits[] = { 5*3, 26*3, 11*3, 11*3 }; // 3x limits seen in practice 23 24static_assert(0 == kTangent_RecursiveLimit, "cubic_stroke_relies_on_tangent_equalling_zero"); 25static_assert(1 == kCubic_RecursiveLimit, "cubic_stroke_relies_on_cubic_equalling_one"); 26static_assert(SK_ARRAY_COUNT(kRecursiveLimits) == kQuad_RecursiveLimit + 1, 27 "recursive_limits_mismatch"); 28 29#ifdef SK_DEBUG 30 int gMaxRecursion[SK_ARRAY_COUNT(kRecursiveLimits)] = { 0 }; 31#endif 32#ifndef DEBUG_QUAD_STROKER 33 #define DEBUG_QUAD_STROKER 0 34#endif 35 36#if DEBUG_QUAD_STROKER 37 /* Enable to show the decisions made in subdividing the curve -- helpful when the resulting 38 stroke has more than the optimal number of quadratics and lines */ 39 #define STROKER_RESULT(resultType, depth, quadPts, format, ...) \ 40 SkDebugf("[%d] %s " format "\n", depth, __FUNCTION__, __VA_ARGS__), \ 41 SkDebugf(" " #resultType " t=(%g,%g)\n", quadPts->fStartT, quadPts->fEndT), \ 42 resultType 43 #define STROKER_DEBUG_PARAMS(...) , __VA_ARGS__ 44#else 45 #define STROKER_RESULT(resultType, depth, quadPts, format, ...) \ 46 resultType 47 #define STROKER_DEBUG_PARAMS(...) 48#endif 49 50static inline bool degenerate_vector(const SkVector& v) { 51 return !SkPoint::CanNormalize(v.fX, v.fY); 52} 53 54static bool set_normal_unitnormal(const SkPoint& before, const SkPoint& after, SkScalar scale, 55 SkScalar radius, 56 SkVector* normal, SkVector* unitNormal) { 57 if (!unitNormal->setNormalize((after.fX - before.fX) * scale, 58 (after.fY - before.fY) * scale)) { 59 return false; 60 } 61 unitNormal->rotateCCW(); 62 unitNormal->scale(radius, normal); 63 return true; 64} 65 66static bool set_normal_unitnormal(const SkVector& vec, 67 SkScalar radius, 68 SkVector* normal, SkVector* unitNormal) { 69 if (!unitNormal->setNormalize(vec.fX, vec.fY)) { 70 return false; 71 } 72 unitNormal->rotateCCW(); 73 unitNormal->scale(radius, normal); 74 return true; 75} 76 77/////////////////////////////////////////////////////////////////////////////// 78 79struct SkQuadConstruct { // The state of the quad stroke under construction. 80 SkPoint fQuad[3]; // the stroked quad parallel to the original curve 81 SkPoint fTangentStart; // a point tangent to fQuad[0] 82 SkPoint fTangentEnd; // a point tangent to fQuad[2] 83 SkScalar fStartT; // a segment of the original curve 84 SkScalar fMidT; // " 85 SkScalar fEndT; // " 86 bool fStartSet; // state to share common points across structs 87 bool fEndSet; // " 88 89 // return false if start and end are too close to have a unique middle 90 bool init(SkScalar start, SkScalar end) { 91 fStartT = start; 92 fMidT = (start + end) * SK_ScalarHalf; 93 fEndT = end; 94 fStartSet = fEndSet = false; 95 return fStartT < fMidT && fMidT < fEndT; 96 } 97 98 bool initWithStart(SkQuadConstruct* parent) { 99 if (!init(parent->fStartT, parent->fMidT)) { 100 return false; 101 } 102 fQuad[0] = parent->fQuad[0]; 103 fTangentStart = parent->fTangentStart; 104 fStartSet = true; 105 return true; 106 } 107 108 bool initWithEnd(SkQuadConstruct* parent) { 109 if (!init(parent->fMidT, parent->fEndT)) { 110 return false; 111 } 112 fQuad[2] = parent->fQuad[2]; 113 fTangentEnd = parent->fTangentEnd; 114 fEndSet = true; 115 return true; 116 } 117}; 118 119class SkPathStroker { 120public: 121 SkPathStroker(const SkPath& src, 122 SkScalar radius, SkScalar miterLimit, SkPaint::Cap, 123 SkPaint::Join, SkScalar resScale); 124 125 bool hasOnlyMoveTo() const { return 0 == fSegmentCount; } 126 SkPoint moveToPt() const { return fFirstPt; } 127 128 void moveTo(const SkPoint&); 129 void lineTo(const SkPoint&, const SkPath::Iter* iter = nullptr); 130 void quadTo(const SkPoint&, const SkPoint&); 131 void conicTo(const SkPoint&, const SkPoint&, SkScalar weight); 132 void cubicTo(const SkPoint&, const SkPoint&, const SkPoint&); 133 void close(bool isLine) { this->finishContour(true, isLine); } 134 135 void done(SkPath* dst, bool isLine) { 136 this->finishContour(false, isLine); 137 fOuter.addPath(fExtra); 138 dst->swap(fOuter); 139 } 140 141 SkScalar getResScale() const { return fResScale; } 142 143 bool isZeroLength() const { 144 return fInner.isZeroLength() && fOuter.isZeroLength(); 145 } 146 147private: 148 SkScalar fRadius; 149 SkScalar fInvMiterLimit; 150 SkScalar fResScale; 151 SkScalar fInvResScale; 152 SkScalar fInvResScaleSquared; 153 154 SkVector fFirstNormal, fPrevNormal, fFirstUnitNormal, fPrevUnitNormal; 155 SkPoint fFirstPt, fPrevPt; // on original path 156 SkPoint fFirstOuterPt; 157 int fSegmentCount; 158 bool fPrevIsLine; 159 160 SkStrokerPriv::CapProc fCapper; 161 SkStrokerPriv::JoinProc fJoiner; 162 163 SkPath fInner, fOuter; // outer is our working answer, inner is temp 164 SkPath fExtra; // added as extra complete contours 165 166 enum StrokeType { 167 kOuter_StrokeType = 1, // use sign-opposite values later to flip perpendicular axis 168 kInner_StrokeType = -1 169 } fStrokeType; 170 171 enum ResultType { 172 kSplit_ResultType, // the caller should split the quad stroke in two 173 kDegenerate_ResultType, // the caller should add a line 174 kQuad_ResultType, // the caller should (continue to try to) add a quad stroke 175 kNormalError_ResultType, // the cubic's normal couldn't be computed -- abort 176 }; 177 178 enum ReductionType { 179 kPoint_ReductionType, // all curve points are practically identical 180 kLine_ReductionType, // the control point is on the line between the ends 181 kQuad_ReductionType, // the control point is outside the line between the ends 182 kDegenerate_ReductionType, // the control point is on the line but outside the ends 183 kDegenerate2_ReductionType, // two control points are on the line but outside ends (cubic) 184 kDegenerate3_ReductionType, // three areas of max curvature found (for cubic) 185 }; 186 187 enum IntersectRayType { 188 kCtrlPt_RayType, 189 kResultType_RayType, 190 }; 191 192 int fRecursionDepth; // track stack depth to abort if numerics run amok 193 bool fFoundTangents; // do less work until tangents meet (cubic) 194 bool fJoinCompleted; // previous join was not degenerate 195 196 void addDegenerateLine(const SkQuadConstruct* ); 197 static ReductionType CheckConicLinear(const SkConic& , SkPoint* reduction); 198 static ReductionType CheckCubicLinear(const SkPoint cubic[4], SkPoint reduction[3], 199 const SkPoint** tanPtPtr); 200 static ReductionType CheckQuadLinear(const SkPoint quad[3], SkPoint* reduction); 201 ResultType compareQuadConic(const SkConic& , SkQuadConstruct* ) const; 202 ResultType compareQuadCubic(const SkPoint cubic[4], SkQuadConstruct* ); 203 ResultType compareQuadQuad(const SkPoint quad[3], SkQuadConstruct* ); 204 void conicPerpRay(const SkConic& , SkScalar t, SkPoint* tPt, SkPoint* onPt, 205 SkPoint* tangent) const; 206 void conicQuadEnds(const SkConic& , SkQuadConstruct* ) const; 207 bool conicStroke(const SkConic& , SkQuadConstruct* ); 208 bool cubicMidOnLine(const SkPoint cubic[4], const SkQuadConstruct* ) const; 209 bool cubicPerpRay(const SkPoint cubic[4], SkScalar t, SkPoint* tPt, SkPoint* onPt, 210 SkPoint* tangent) const; 211 bool cubicQuadEnds(const SkPoint cubic[4], SkQuadConstruct* ); 212 bool cubicQuadMid(const SkPoint cubic[4], const SkQuadConstruct* , SkPoint* mid) const; 213 bool cubicStroke(const SkPoint cubic[4], SkQuadConstruct* ); 214 void init(StrokeType strokeType, SkQuadConstruct* , SkScalar tStart, SkScalar tEnd); 215 ResultType intersectRay(SkQuadConstruct* , IntersectRayType STROKER_DEBUG_PARAMS(int) ) const; 216 bool ptInQuadBounds(const SkPoint quad[3], const SkPoint& pt) const; 217 void quadPerpRay(const SkPoint quad[3], SkScalar t, SkPoint* tPt, SkPoint* onPt, 218 SkPoint* tangent) const; 219 bool quadStroke(const SkPoint quad[3], SkQuadConstruct* ); 220 void setConicEndNormal(const SkConic& , 221 const SkVector& normalAB, const SkVector& unitNormalAB, 222 SkVector* normalBC, SkVector* unitNormalBC); 223 void setCubicEndNormal(const SkPoint cubic[4], 224 const SkVector& normalAB, const SkVector& unitNormalAB, 225 SkVector* normalCD, SkVector* unitNormalCD); 226 void setQuadEndNormal(const SkPoint quad[3], 227 const SkVector& normalAB, const SkVector& unitNormalAB, 228 SkVector* normalBC, SkVector* unitNormalBC); 229 void setRayPts(const SkPoint& tPt, SkVector* dxy, SkPoint* onPt, SkPoint* tangent) const; 230 static bool SlightAngle(SkQuadConstruct* ); 231 ResultType strokeCloseEnough(const SkPoint stroke[3], const SkPoint ray[2], 232 SkQuadConstruct* STROKER_DEBUG_PARAMS(int depth) ) const; 233 ResultType tangentsMeet(const SkPoint cubic[4], SkQuadConstruct* ); 234 235 void finishContour(bool close, bool isLine); 236 bool preJoinTo(const SkPoint&, SkVector* normal, SkVector* unitNormal, 237 bool isLine); 238 void postJoinTo(const SkPoint&, const SkVector& normal, 239 const SkVector& unitNormal); 240 241 void line_to(const SkPoint& currPt, const SkVector& normal); 242}; 243 244/////////////////////////////////////////////////////////////////////////////// 245 246bool SkPathStroker::preJoinTo(const SkPoint& currPt, SkVector* normal, 247 SkVector* unitNormal, bool currIsLine) { 248 SkASSERT(fSegmentCount >= 0); 249 250 SkScalar prevX = fPrevPt.fX; 251 SkScalar prevY = fPrevPt.fY; 252 253 if (!set_normal_unitnormal(fPrevPt, currPt, fResScale, fRadius, normal, unitNormal)) { 254 if (SkStrokerPriv::CapFactory(SkPaint::kButt_Cap) == fCapper) { 255 return false; 256 } 257 /* Square caps and round caps draw even if the segment length is zero. 258 Since the zero length segment has no direction, set the orientation 259 to upright as the default orientation */ 260 normal->set(fRadius, 0); 261 unitNormal->set(1, 0); 262 } 263 264 if (fSegmentCount == 0) { 265 fFirstNormal = *normal; 266 fFirstUnitNormal = *unitNormal; 267 fFirstOuterPt.set(prevX + normal->fX, prevY + normal->fY); 268 269 fOuter.moveTo(fFirstOuterPt.fX, fFirstOuterPt.fY); 270 fInner.moveTo(prevX - normal->fX, prevY - normal->fY); 271 } else { // we have a previous segment 272 fJoiner(&fOuter, &fInner, fPrevUnitNormal, fPrevPt, *unitNormal, 273 fRadius, fInvMiterLimit, fPrevIsLine, currIsLine); 274 } 275 fPrevIsLine = currIsLine; 276 return true; 277} 278 279void SkPathStroker::postJoinTo(const SkPoint& currPt, const SkVector& normal, 280 const SkVector& unitNormal) { 281 fJoinCompleted = true; 282 fPrevPt = currPt; 283 fPrevUnitNormal = unitNormal; 284 fPrevNormal = normal; 285 fSegmentCount += 1; 286} 287 288void SkPathStroker::finishContour(bool close, bool currIsLine) { 289 if (fSegmentCount > 0) { 290 SkPoint pt; 291 292 if (close) { 293 fJoiner(&fOuter, &fInner, fPrevUnitNormal, fPrevPt, 294 fFirstUnitNormal, fRadius, fInvMiterLimit, 295 fPrevIsLine, currIsLine); 296 fOuter.close(); 297 // now add fInner as its own contour 298 fInner.getLastPt(&pt); 299 fOuter.moveTo(pt.fX, pt.fY); 300 fOuter.reversePathTo(fInner); 301 fOuter.close(); 302 } else { // add caps to start and end 303 // cap the end 304 fInner.getLastPt(&pt); 305 fCapper(&fOuter, fPrevPt, fPrevNormal, pt, 306 currIsLine ? &fInner : nullptr); 307 fOuter.reversePathTo(fInner); 308 // cap the start 309 fCapper(&fOuter, fFirstPt, -fFirstNormal, fFirstOuterPt, 310 fPrevIsLine ? &fInner : nullptr); 311 fOuter.close(); 312 } 313 } 314 // since we may re-use fInner, we rewind instead of reset, to save on 315 // reallocating its internal storage. 316 fInner.rewind(); 317 fSegmentCount = -1; 318} 319 320/////////////////////////////////////////////////////////////////////////////// 321 322SkPathStroker::SkPathStroker(const SkPath& src, 323 SkScalar radius, SkScalar miterLimit, 324 SkPaint::Cap cap, SkPaint::Join join, SkScalar resScale) 325 : fRadius(radius) 326 , fResScale(resScale) { 327 328 /* This is only used when join is miter_join, but we initialize it here 329 so that it is always defined, to fis valgrind warnings. 330 */ 331 fInvMiterLimit = 0; 332 333 if (join == SkPaint::kMiter_Join) { 334 if (miterLimit <= SK_Scalar1) { 335 join = SkPaint::kBevel_Join; 336 } else { 337 fInvMiterLimit = SkScalarInvert(miterLimit); 338 } 339 } 340 fCapper = SkStrokerPriv::CapFactory(cap); 341 fJoiner = SkStrokerPriv::JoinFactory(join); 342 fSegmentCount = -1; 343 fPrevIsLine = false; 344 345 // Need some estimate of how large our final result (fOuter) 346 // and our per-contour temp (fInner) will be, so we don't spend 347 // extra time repeatedly growing these arrays. 348 // 349 // 3x for result == inner + outer + join (swag) 350 // 1x for inner == 'wag' (worst contour length would be better guess) 351 fOuter.incReserve(src.countPoints() * 3); 352 fOuter.setIsVolatile(true); 353 fInner.incReserve(src.countPoints()); 354 fInner.setIsVolatile(true); 355 // TODO : write a common error function used by stroking and filling 356 // The '4' below matches the fill scan converter's error term 357 fInvResScale = SkScalarInvert(resScale * 4); 358 fInvResScaleSquared = fInvResScale * fInvResScale; 359 fRecursionDepth = 0; 360} 361 362void SkPathStroker::moveTo(const SkPoint& pt) { 363 if (fSegmentCount > 0) { 364 this->finishContour(false, false); 365 } 366 fSegmentCount = 0; 367 fFirstPt = fPrevPt = pt; 368 fJoinCompleted = false; 369} 370 371void SkPathStroker::line_to(const SkPoint& currPt, const SkVector& normal) { 372 fOuter.lineTo(currPt.fX + normal.fX, currPt.fY + normal.fY); 373 fInner.lineTo(currPt.fX - normal.fX, currPt.fY - normal.fY); 374} 375 376static bool has_valid_tangent(const SkPath::Iter* iter) { 377 SkPath::Iter copy = *iter; 378 SkPath::Verb verb; 379 SkPoint pts[4]; 380 while ((verb = copy.next(pts))) { 381 switch (verb) { 382 case SkPath::kMove_Verb: 383 return false; 384 case SkPath::kLine_Verb: 385 if (pts[0] == pts[1]) { 386 continue; 387 } 388 return true; 389 case SkPath::kQuad_Verb: 390 case SkPath::kConic_Verb: 391 if (pts[0] == pts[1] && pts[0] == pts[2]) { 392 continue; 393 } 394 return true; 395 case SkPath::kCubic_Verb: 396 if (pts[0] == pts[1] && pts[0] == pts[2] && pts[0] == pts[3]) { 397 continue; 398 } 399 return true; 400 case SkPath::kClose_Verb: 401 case SkPath::kDone_Verb: 402 return false; 403 } 404 } 405 return false; 406} 407 408void SkPathStroker::lineTo(const SkPoint& currPt, const SkPath::Iter* iter) { 409 if (SkStrokerPriv::CapFactory(SkPaint::kButt_Cap) == fCapper 410 && fPrevPt.equalsWithinTolerance(currPt, SK_ScalarNearlyZero * fInvResScale)) { 411 return; 412 } 413 if (fPrevPt == currPt && (fJoinCompleted || (iter && has_valid_tangent(iter)))) { 414 return; 415 } 416 SkVector normal, unitNormal; 417 418 if (!this->preJoinTo(currPt, &normal, &unitNormal, true)) { 419 return; 420 } 421 this->line_to(currPt, normal); 422 this->postJoinTo(currPt, normal, unitNormal); 423} 424 425void SkPathStroker::setQuadEndNormal(const SkPoint quad[3], const SkVector& normalAB, 426 const SkVector& unitNormalAB, SkVector* normalBC, SkVector* unitNormalBC) { 427 if (!set_normal_unitnormal(quad[1], quad[2], fResScale, fRadius, normalBC, unitNormalBC)) { 428 *normalBC = normalAB; 429 *unitNormalBC = unitNormalAB; 430 } 431} 432 433void SkPathStroker::setConicEndNormal(const SkConic& conic, const SkVector& normalAB, 434 const SkVector& unitNormalAB, SkVector* normalBC, SkVector* unitNormalBC) { 435 setQuadEndNormal(conic.fPts, normalAB, unitNormalAB, normalBC, unitNormalBC); 436} 437 438void SkPathStroker::setCubicEndNormal(const SkPoint cubic[4], const SkVector& normalAB, 439 const SkVector& unitNormalAB, SkVector* normalCD, SkVector* unitNormalCD) { 440 SkVector ab = cubic[1] - cubic[0]; 441 SkVector cd = cubic[3] - cubic[2]; 442 443 bool degenerateAB = degenerate_vector(ab); 444 bool degenerateCD = degenerate_vector(cd); 445 446 if (degenerateAB && degenerateCD) { 447 goto DEGENERATE_NORMAL; 448 } 449 450 if (degenerateAB) { 451 ab = cubic[2] - cubic[0]; 452 degenerateAB = degenerate_vector(ab); 453 } 454 if (degenerateCD) { 455 cd = cubic[3] - cubic[1]; 456 degenerateCD = degenerate_vector(cd); 457 } 458 if (degenerateAB || degenerateCD) { 459DEGENERATE_NORMAL: 460 *normalCD = normalAB; 461 *unitNormalCD = unitNormalAB; 462 return; 463 } 464 SkAssertResult(set_normal_unitnormal(cd, fRadius, normalCD, unitNormalCD)); 465} 466 467void SkPathStroker::init(StrokeType strokeType, SkQuadConstruct* quadPts, SkScalar tStart, 468 SkScalar tEnd) { 469 fStrokeType = strokeType; 470 fFoundTangents = false; 471 quadPts->init(tStart, tEnd); 472} 473 474// returns the distance squared from the point to the line 475static SkScalar pt_to_line(const SkPoint& pt, const SkPoint& lineStart, const SkPoint& lineEnd) { 476 SkVector dxy = lineEnd - lineStart; 477 if (degenerate_vector(dxy)) { 478 return pt.distanceToSqd(lineStart); 479 } 480 SkVector ab0 = pt - lineStart; 481 SkScalar numer = dxy.dot(ab0); 482 SkScalar denom = dxy.dot(dxy); 483 SkScalar t = numer / denom; 484 SkPoint hit; 485 hit.fX = lineStart.fX * (1 - t) + lineEnd.fX * t; 486 hit.fY = lineStart.fY * (1 - t) + lineEnd.fY * t; 487 return hit.distanceToSqd(pt); 488} 489 490/* Given a cubic, determine if all four points are in a line. 491 Return true if the inner points is close to a line connecting the outermost points. 492 493 Find the outermost point by looking for the largest difference in X or Y. 494 Given the indices of the outermost points, and that outer_1 is greater than outer_2, 495 this table shows the index of the smaller of the remaining points: 496 497 outer_2 498 0 1 2 3 499 outer_1 ---------------- 500 0 | - 2 1 1 501 1 | - - 0 0 502 2 | - - - 0 503 3 | - - - - 504 505 If outer_1 == 0 and outer_2 == 1, the smaller of the remaining indices (2 and 3) is 2. 506 507 This table can be collapsed to: (1 + (2 >> outer_2)) >> outer_1 508 509 Given three indices (outer_1 outer_2 mid_1) from 0..3, the remaining index is: 510 511 mid_2 == (outer_1 ^ outer_2 ^ mid_1) 512 */ 513static bool cubic_in_line(const SkPoint cubic[4]) { 514 SkScalar ptMax = -1; 515 int outer1 SK_INIT_TO_AVOID_WARNING; 516 int outer2 SK_INIT_TO_AVOID_WARNING; 517 for (int index = 0; index < 3; ++index) { 518 for (int inner = index + 1; inner < 4; ++inner) { 519 SkVector testDiff = cubic[inner] - cubic[index]; 520 SkScalar testMax = SkTMax(SkScalarAbs(testDiff.fX), SkScalarAbs(testDiff.fY)); 521 if (ptMax < testMax) { 522 outer1 = index; 523 outer2 = inner; 524 ptMax = testMax; 525 } 526 } 527 } 528 SkASSERT(outer1 >= 0 && outer1 <= 2); 529 SkASSERT(outer2 >= 1 && outer2 <= 3); 530 SkASSERT(outer1 < outer2); 531 int mid1 = (1 + (2 >> outer2)) >> outer1; 532 SkASSERT(mid1 >= 0 && mid1 <= 2); 533 SkASSERT(outer1 != mid1 && outer2 != mid1); 534 int mid2 = outer1 ^ outer2 ^ mid1; 535 SkASSERT(mid2 >= 1 && mid2 <= 3); 536 SkASSERT(mid2 != outer1 && mid2 != outer2 && mid2 != mid1); 537 SkASSERT(((1 << outer1) | (1 << outer2) | (1 << mid1) | (1 << mid2)) == 0x0f); 538 SkScalar lineSlop = ptMax * ptMax * 0.00001f; // this multiplier is pulled out of the air 539 return pt_to_line(cubic[mid1], cubic[outer1], cubic[outer2]) <= lineSlop 540 && pt_to_line(cubic[mid2], cubic[outer1], cubic[outer2]) <= lineSlop; 541} 542 543/* Given quad, see if all there points are in a line. 544 Return true if the inside point is close to a line connecting the outermost points. 545 546 Find the outermost point by looking for the largest difference in X or Y. 547 Since the XOR of the indices is 3 (0 ^ 1 ^ 2) 548 the missing index equals: outer_1 ^ outer_2 ^ 3 549 */ 550static bool quad_in_line(const SkPoint quad[3]) { 551 SkScalar ptMax = -1; 552 int outer1 SK_INIT_TO_AVOID_WARNING; 553 int outer2 SK_INIT_TO_AVOID_WARNING; 554 for (int index = 0; index < 2; ++index) { 555 for (int inner = index + 1; inner < 3; ++inner) { 556 SkVector testDiff = quad[inner] - quad[index]; 557 SkScalar testMax = SkTMax(SkScalarAbs(testDiff.fX), SkScalarAbs(testDiff.fY)); 558 if (ptMax < testMax) { 559 outer1 = index; 560 outer2 = inner; 561 ptMax = testMax; 562 } 563 } 564 } 565 SkASSERT(outer1 >= 0 && outer1 <= 1); 566 SkASSERT(outer2 >= 1 && outer2 <= 2); 567 SkASSERT(outer1 < outer2); 568 int mid = outer1 ^ outer2 ^ 3; 569 SkScalar lineSlop = ptMax * ptMax * 0.00001f; // this multiplier is pulled out of the air 570 return pt_to_line(quad[mid], quad[outer1], quad[outer2]) <= lineSlop; 571} 572 573static bool conic_in_line(const SkConic& conic) { 574 return quad_in_line(conic.fPts); 575} 576 577SkPathStroker::ReductionType SkPathStroker::CheckCubicLinear(const SkPoint cubic[4], 578 SkPoint reduction[3], const SkPoint** tangentPtPtr) { 579 bool degenerateAB = degenerate_vector(cubic[1] - cubic[0]); 580 bool degenerateBC = degenerate_vector(cubic[2] - cubic[1]); 581 bool degenerateCD = degenerate_vector(cubic[3] - cubic[2]); 582 if (degenerateAB & degenerateBC & degenerateCD) { 583 return kPoint_ReductionType; 584 } 585 if (degenerateAB + degenerateBC + degenerateCD == 2) { 586 return kLine_ReductionType; 587 } 588 if (!cubic_in_line(cubic)) { 589 *tangentPtPtr = degenerateAB ? &cubic[2] : &cubic[1]; 590 return kQuad_ReductionType; 591 } 592 SkScalar tValues[3]; 593 int count = SkFindCubicMaxCurvature(cubic, tValues); 594 if (count == 0) { 595 return kLine_ReductionType; 596 } 597 for (int index = 0; index < count; ++index) { 598 SkScalar t = tValues[index]; 599 SkEvalCubicAt(cubic, t, &reduction[index], nullptr, nullptr); 600 } 601 static_assert(kQuad_ReductionType + 1 == kDegenerate_ReductionType, "enum_out_of_whack"); 602 static_assert(kQuad_ReductionType + 2 == kDegenerate2_ReductionType, "enum_out_of_whack"); 603 static_assert(kQuad_ReductionType + 3 == kDegenerate3_ReductionType, "enum_out_of_whack"); 604 605 return (ReductionType) (kQuad_ReductionType + count); 606} 607 608SkPathStroker::ReductionType SkPathStroker::CheckConicLinear(const SkConic& conic, 609 SkPoint* reduction) { 610 bool degenerateAB = degenerate_vector(conic.fPts[1] - conic.fPts[0]); 611 bool degenerateBC = degenerate_vector(conic.fPts[2] - conic.fPts[1]); 612 if (degenerateAB & degenerateBC) { 613 return kPoint_ReductionType; 614 } 615 if (degenerateAB | degenerateBC) { 616 return kLine_ReductionType; 617 } 618 if (!conic_in_line(conic)) { 619 return kQuad_ReductionType; 620 } 621#if 0 // once findMaxCurvature is implemented, this will be a better solution 622 SkScalar t; 623 if (!conic.findMaxCurvature(&t) || 0 == t) { 624 return kLine_ReductionType; 625 } 626#else // but for now, use extrema instead 627 SkScalar xT = 0, yT = 0; 628 (void) conic.findXExtrema(&xT); 629 (void) conic.findYExtrema(&yT); 630 SkScalar t = SkTMax(xT, yT); 631 if (0 == t) { 632 return kLine_ReductionType; 633 } 634#endif 635 conic.evalAt(t, reduction, nullptr); 636 return kDegenerate_ReductionType; 637} 638 639SkPathStroker::ReductionType SkPathStroker::CheckQuadLinear(const SkPoint quad[3], 640 SkPoint* reduction) { 641 bool degenerateAB = degenerate_vector(quad[1] - quad[0]); 642 bool degenerateBC = degenerate_vector(quad[2] - quad[1]); 643 if (degenerateAB & degenerateBC) { 644 return kPoint_ReductionType; 645 } 646 if (degenerateAB | degenerateBC) { 647 return kLine_ReductionType; 648 } 649 if (!quad_in_line(quad)) { 650 return kQuad_ReductionType; 651 } 652 SkScalar t = SkFindQuadMaxCurvature(quad); 653 if (0 == t) { 654 return kLine_ReductionType; 655 } 656 *reduction = SkEvalQuadAt(quad, t); 657 return kDegenerate_ReductionType; 658} 659 660void SkPathStroker::conicTo(const SkPoint& pt1, const SkPoint& pt2, SkScalar weight) { 661 const SkConic conic(fPrevPt, pt1, pt2, weight); 662 SkPoint reduction; 663 ReductionType reductionType = CheckConicLinear(conic, &reduction); 664 if (kPoint_ReductionType == reductionType) { 665 /* If the stroke consists of a moveTo followed by a degenerate curve, treat it 666 as if it were followed by a zero-length line. Lines without length 667 can have square and round end caps. */ 668 this->lineTo(pt2); 669 return; 670 } 671 if (kLine_ReductionType == reductionType) { 672 this->lineTo(pt2); 673 return; 674 } 675 if (kDegenerate_ReductionType == reductionType) { 676 this->lineTo(reduction); 677 SkStrokerPriv::JoinProc saveJoiner = fJoiner; 678 fJoiner = SkStrokerPriv::JoinFactory(SkPaint::kRound_Join); 679 this->lineTo(pt2); 680 fJoiner = saveJoiner; 681 return; 682 } 683 SkASSERT(kQuad_ReductionType == reductionType); 684 SkVector normalAB, unitAB, normalBC, unitBC; 685 if (!this->preJoinTo(pt1, &normalAB, &unitAB, false)) { 686 this->lineTo(pt2); 687 return; 688 } 689 SkQuadConstruct quadPts; 690 this->init(kOuter_StrokeType, &quadPts, 0, 1); 691 (void) this->conicStroke(conic, &quadPts); 692 this->init(kInner_StrokeType, &quadPts, 0, 1); 693 (void) this->conicStroke(conic, &quadPts); 694 this->setConicEndNormal(conic, normalAB, unitAB, &normalBC, &unitBC); 695 this->postJoinTo(pt2, normalBC, unitBC); 696} 697 698void SkPathStroker::quadTo(const SkPoint& pt1, const SkPoint& pt2) { 699 const SkPoint quad[3] = { fPrevPt, pt1, pt2 }; 700 SkPoint reduction; 701 ReductionType reductionType = CheckQuadLinear(quad, &reduction); 702 if (kPoint_ReductionType == reductionType) { 703 /* If the stroke consists of a moveTo followed by a degenerate curve, treat it 704 as if it were followed by a zero-length line. Lines without length 705 can have square and round end caps. */ 706 this->lineTo(pt2); 707 return; 708 } 709 if (kLine_ReductionType == reductionType) { 710 this->lineTo(pt2); 711 return; 712 } 713 if (kDegenerate_ReductionType == reductionType) { 714 this->lineTo(reduction); 715 SkStrokerPriv::JoinProc saveJoiner = fJoiner; 716 fJoiner = SkStrokerPriv::JoinFactory(SkPaint::kRound_Join); 717 this->lineTo(pt2); 718 fJoiner = saveJoiner; 719 return; 720 } 721 SkASSERT(kQuad_ReductionType == reductionType); 722 SkVector normalAB, unitAB, normalBC, unitBC; 723 if (!this->preJoinTo(pt1, &normalAB, &unitAB, false)) { 724 this->lineTo(pt2); 725 return; 726 } 727 SkQuadConstruct quadPts; 728 this->init(kOuter_StrokeType, &quadPts, 0, 1); 729 (void) this->quadStroke(quad, &quadPts); 730 this->init(kInner_StrokeType, &quadPts, 0, 1); 731 (void) this->quadStroke(quad, &quadPts); 732 this->setQuadEndNormal(quad, normalAB, unitAB, &normalBC, &unitBC); 733 734 this->postJoinTo(pt2, normalBC, unitBC); 735} 736 737// Given a point on the curve and its derivative, scale the derivative by the radius, and 738// compute the perpendicular point and its tangent. 739void SkPathStroker::setRayPts(const SkPoint& tPt, SkVector* dxy, SkPoint* onPt, 740 SkPoint* tangent) const { 741 SkPoint oldDxy = *dxy; 742 if (!dxy->setLength(fRadius)) { // consider moving double logic into SkPoint::setLength 743 double xx = oldDxy.fX; 744 double yy = oldDxy.fY; 745 double dscale = fRadius / sqrt(xx * xx + yy * yy); 746 dxy->fX = SkDoubleToScalar(xx * dscale); 747 dxy->fY = SkDoubleToScalar(yy * dscale); 748 } 749 SkScalar axisFlip = SkIntToScalar(fStrokeType); // go opposite ways for outer, inner 750 onPt->fX = tPt.fX + axisFlip * dxy->fY; 751 onPt->fY = tPt.fY - axisFlip * dxy->fX; 752 if (tangent) { 753 tangent->fX = onPt->fX + dxy->fX; 754 tangent->fY = onPt->fY + dxy->fY; 755 } 756} 757 758// Given a conic and t, return the point on curve, its perpendicular, and the perpendicular tangent. 759// Returns false if the perpendicular could not be computed (because the derivative collapsed to 0) 760void SkPathStroker::conicPerpRay(const SkConic& conic, SkScalar t, SkPoint* tPt, SkPoint* onPt, 761 SkPoint* tangent) const { 762 SkVector dxy; 763 conic.evalAt(t, tPt, &dxy); 764 if (dxy.fX == 0 && dxy.fY == 0) { 765 dxy = conic.fPts[2] - conic.fPts[0]; 766 } 767 this->setRayPts(*tPt, &dxy, onPt, tangent); 768} 769 770// Given a conic and a t range, find the start and end if they haven't been found already. 771void SkPathStroker::conicQuadEnds(const SkConic& conic, SkQuadConstruct* quadPts) const { 772 if (!quadPts->fStartSet) { 773 SkPoint conicStartPt; 774 this->conicPerpRay(conic, quadPts->fStartT, &conicStartPt, &quadPts->fQuad[0], 775 &quadPts->fTangentStart); 776 quadPts->fStartSet = true; 777 } 778 if (!quadPts->fEndSet) { 779 SkPoint conicEndPt; 780 this->conicPerpRay(conic, quadPts->fEndT, &conicEndPt, &quadPts->fQuad[2], 781 &quadPts->fTangentEnd); 782 quadPts->fEndSet = true; 783 } 784} 785 786 787// Given a cubic and t, return the point on curve, its perpendicular, and the perpendicular tangent. 788// Returns false if the perpendicular could not be computed (because the derivative collapsed to 0) 789bool SkPathStroker::cubicPerpRay(const SkPoint cubic[4], SkScalar t, SkPoint* tPt, SkPoint* onPt, 790 SkPoint* tangent) const { 791 SkVector dxy; 792 SkEvalCubicAt(cubic, t, tPt, &dxy, nullptr); 793 if (dxy.fX == 0 && dxy.fY == 0) { 794 if (SkScalarNearlyZero(t)) { 795 dxy = cubic[2] - cubic[0]; 796 } else if (SkScalarNearlyZero(1 - t)) { 797 dxy = cubic[3] - cubic[1]; 798 } else { 799 return false; 800 } 801 if (dxy.fX == 0 && dxy.fY == 0) { 802 dxy = cubic[3] - cubic[0]; 803 } 804 } 805 setRayPts(*tPt, &dxy, onPt, tangent); 806 return true; 807} 808 809// Given a cubic and a t range, find the start and end if they haven't been found already. 810bool SkPathStroker::cubicQuadEnds(const SkPoint cubic[4], SkQuadConstruct* quadPts) { 811 if (!quadPts->fStartSet) { 812 SkPoint cubicStartPt; 813 if (!this->cubicPerpRay(cubic, quadPts->fStartT, &cubicStartPt, &quadPts->fQuad[0], 814 &quadPts->fTangentStart)) { 815 return false; 816 } 817 quadPts->fStartSet = true; 818 } 819 if (!quadPts->fEndSet) { 820 SkPoint cubicEndPt; 821 if (!this->cubicPerpRay(cubic, quadPts->fEndT, &cubicEndPt, &quadPts->fQuad[2], 822 &quadPts->fTangentEnd)) { 823 return false; 824 } 825 quadPts->fEndSet = true; 826 } 827 return true; 828} 829 830bool SkPathStroker::cubicQuadMid(const SkPoint cubic[4], const SkQuadConstruct* quadPts, 831 SkPoint* mid) const { 832 SkPoint cubicMidPt; 833 return this->cubicPerpRay(cubic, quadPts->fMidT, &cubicMidPt, mid, nullptr); 834} 835 836// Given a quad and t, return the point on curve, its perpendicular, and the perpendicular tangent. 837void SkPathStroker::quadPerpRay(const SkPoint quad[3], SkScalar t, SkPoint* tPt, SkPoint* onPt, 838 SkPoint* tangent) const { 839 SkVector dxy; 840 SkEvalQuadAt(quad, t, tPt, &dxy); 841 if (dxy.fX == 0 && dxy.fY == 0) { 842 dxy = quad[2] - quad[0]; 843 } 844 setRayPts(*tPt, &dxy, onPt, tangent); 845} 846 847// Find the intersection of the stroke tangents to construct a stroke quad. 848// Return whether the stroke is a degenerate (a line), a quad, or must be split. 849// Optionally compute the quad's control point. 850SkPathStroker::ResultType SkPathStroker::intersectRay(SkQuadConstruct* quadPts, 851 IntersectRayType intersectRayType STROKER_DEBUG_PARAMS(int depth)) const { 852 const SkPoint& start = quadPts->fQuad[0]; 853 const SkPoint& end = quadPts->fQuad[2]; 854 SkVector aLen = quadPts->fTangentStart - start; 855 SkVector bLen = quadPts->fTangentEnd - end; 856 /* Slopes match when denom goes to zero: 857 axLen / ayLen == bxLen / byLen 858 (ayLen * byLen) * axLen / ayLen == (ayLen * byLen) * bxLen / byLen 859 byLen * axLen == ayLen * bxLen 860 byLen * axLen - ayLen * bxLen ( == denom ) 861 */ 862 SkScalar denom = aLen.cross(bLen); 863 if (denom == 0 || !SkScalarIsFinite(denom)) { 864 return STROKER_RESULT(kDegenerate_ResultType, depth, quadPts, "denom == 0"); 865 } 866 SkVector ab0 = start - end; 867 SkScalar numerA = bLen.cross(ab0); 868 SkScalar numerB = aLen.cross(ab0); 869 if ((numerA >= 0) == (numerB >= 0)) { // if the control point is outside the quad ends 870 // if the perpendicular distances from the quad points to the opposite tangent line 871 // are small, a straight line is good enough 872 SkScalar dist1 = pt_to_line(start, end, quadPts->fTangentEnd); 873 SkScalar dist2 = pt_to_line(end, start, quadPts->fTangentStart); 874 if (SkTMax(dist1, dist2) <= fInvResScaleSquared) { 875 return STROKER_RESULT(kDegenerate_ResultType, depth, quadPts, 876 "SkTMax(dist1=%g, dist2=%g) <= fInvResScaleSquared", dist1, dist2); 877 } 878 return STROKER_RESULT(kSplit_ResultType, depth, quadPts, 879 "(numerA=%g >= 0) == (numerB=%g >= 0)", numerA, numerB); 880 } 881 // check to see if the denominator is teeny relative to the numerator 882 // if the offset by one will be lost, the ratio is too large 883 numerA /= denom; 884 bool validDivide = numerA > numerA - 1; 885 if (validDivide) { 886 if (kCtrlPt_RayType == intersectRayType) { 887 SkPoint* ctrlPt = &quadPts->fQuad[1]; 888 // the intersection of the tangents need not be on the tangent segment 889 // so 0 <= numerA <= 1 is not necessarily true 890 ctrlPt->fX = start.fX * (1 - numerA) + quadPts->fTangentStart.fX * numerA; 891 ctrlPt->fY = start.fY * (1 - numerA) + quadPts->fTangentStart.fY * numerA; 892 } 893 return STROKER_RESULT(kQuad_ResultType, depth, quadPts, 894 "(numerA=%g >= 0) != (numerB=%g >= 0)", numerA, numerB); 895 } 896 // if the lines are parallel, straight line is good enough 897 return STROKER_RESULT(kDegenerate_ResultType, depth, quadPts, 898 "SkScalarNearlyZero(denom=%g)", denom); 899} 900 901// Given a cubic and a t-range, determine if the stroke can be described by a quadratic. 902SkPathStroker::ResultType SkPathStroker::tangentsMeet(const SkPoint cubic[4], 903 SkQuadConstruct* quadPts) { 904 if (!this->cubicQuadEnds(cubic, quadPts)) { 905 return kNormalError_ResultType; 906 } 907 return this->intersectRay(quadPts, kResultType_RayType STROKER_DEBUG_PARAMS(fRecursionDepth)); 908} 909 910// Intersect the line with the quad and return the t values on the quad where the line crosses. 911static int intersect_quad_ray(const SkPoint line[2], const SkPoint quad[3], SkScalar roots[2]) { 912 SkVector vec = line[1] - line[0]; 913 SkScalar r[3]; 914 for (int n = 0; n < 3; ++n) { 915 r[n] = (quad[n].fY - line[0].fY) * vec.fX - (quad[n].fX - line[0].fX) * vec.fY; 916 } 917 SkScalar A = r[2]; 918 SkScalar B = r[1]; 919 SkScalar C = r[0]; 920 A += C - 2 * B; // A = a - 2*b + c 921 B -= C; // B = -(b - c) 922 return SkFindUnitQuadRoots(A, 2 * B, C, roots); 923} 924 925// Return true if the point is close to the bounds of the quad. This is used as a quick reject. 926bool SkPathStroker::ptInQuadBounds(const SkPoint quad[3], const SkPoint& pt) const { 927 SkScalar xMin = SkTMin(SkTMin(quad[0].fX, quad[1].fX), quad[2].fX); 928 if (pt.fX + fInvResScale < xMin) { 929 return false; 930 } 931 SkScalar xMax = SkTMax(SkTMax(quad[0].fX, quad[1].fX), quad[2].fX); 932 if (pt.fX - fInvResScale > xMax) { 933 return false; 934 } 935 SkScalar yMin = SkTMin(SkTMin(quad[0].fY, quad[1].fY), quad[2].fY); 936 if (pt.fY + fInvResScale < yMin) { 937 return false; 938 } 939 SkScalar yMax = SkTMax(SkTMax(quad[0].fY, quad[1].fY), quad[2].fY); 940 if (pt.fY - fInvResScale > yMax) { 941 return false; 942 } 943 return true; 944} 945 946static bool points_within_dist(const SkPoint& nearPt, const SkPoint& farPt, SkScalar limit) { 947 return nearPt.distanceToSqd(farPt) <= limit * limit; 948} 949 950static bool sharp_angle(const SkPoint quad[3]) { 951 SkVector smaller = quad[1] - quad[0]; 952 SkVector larger = quad[1] - quad[2]; 953 SkScalar smallerLen = smaller.lengthSqd(); 954 SkScalar largerLen = larger.lengthSqd(); 955 if (smallerLen > largerLen) { 956 SkTSwap(smaller, larger); 957 largerLen = smallerLen; 958 } 959 if (!smaller.setLength(largerLen)) { 960 return false; 961 } 962 SkScalar dot = smaller.dot(larger); 963 return dot > 0; 964} 965 966SkPathStroker::ResultType SkPathStroker::strokeCloseEnough(const SkPoint stroke[3], 967 const SkPoint ray[2], SkQuadConstruct* quadPts STROKER_DEBUG_PARAMS(int depth)) const { 968 SkPoint strokeMid = SkEvalQuadAt(stroke, SK_ScalarHalf); 969 // measure the distance from the curve to the quad-stroke midpoint, compare to radius 970 if (points_within_dist(ray[0], strokeMid, fInvResScale)) { // if the difference is small 971 if (sharp_angle(quadPts->fQuad)) { 972 return STROKER_RESULT(kSplit_ResultType, depth, quadPts, 973 "sharp_angle (1) =%g,%g, %g,%g, %g,%g", 974 quadPts->fQuad[0].fX, quadPts->fQuad[0].fY, 975 quadPts->fQuad[1].fX, quadPts->fQuad[1].fY, 976 quadPts->fQuad[2].fX, quadPts->fQuad[2].fY); 977 } 978 return STROKER_RESULT(kQuad_ResultType, depth, quadPts, 979 "points_within_dist(ray[0]=%g,%g, strokeMid=%g,%g, fInvResScale=%g)", 980 ray[0].fX, ray[0].fY, strokeMid.fX, strokeMid.fY, fInvResScale); 981 } 982 // measure the distance to quad's bounds (quick reject) 983 // an alternative : look for point in triangle 984 if (!ptInQuadBounds(stroke, ray[0])) { // if far, subdivide 985 return STROKER_RESULT(kSplit_ResultType, depth, quadPts, 986 "!pt_in_quad_bounds(stroke=(%g,%g %g,%g %g,%g), ray[0]=%g,%g)", 987 stroke[0].fX, stroke[0].fY, stroke[1].fX, stroke[1].fY, stroke[2].fX, stroke[2].fY, 988 ray[0].fX, ray[0].fY); 989 } 990 // measure the curve ray distance to the quad-stroke 991 SkScalar roots[2]; 992 int rootCount = intersect_quad_ray(ray, stroke, roots); 993 if (rootCount != 1) { 994 return STROKER_RESULT(kSplit_ResultType, depth, quadPts, 995 "rootCount=%d != 1", rootCount); 996 } 997 SkPoint quadPt = SkEvalQuadAt(stroke, roots[0]); 998 SkScalar error = fInvResScale * (SK_Scalar1 - SkScalarAbs(roots[0] - 0.5f) * 2); 999 if (points_within_dist(ray[0], quadPt, error)) { // if the difference is small, we're done 1000 if (sharp_angle(quadPts->fQuad)) { 1001 return STROKER_RESULT(kSplit_ResultType, depth, quadPts, 1002 "sharp_angle (2) =%g,%g, %g,%g, %g,%g", 1003 quadPts->fQuad[0].fX, quadPts->fQuad[0].fY, 1004 quadPts->fQuad[1].fX, quadPts->fQuad[1].fY, 1005 quadPts->fQuad[2].fX, quadPts->fQuad[2].fY); 1006 } 1007 return STROKER_RESULT(kQuad_ResultType, depth, quadPts, 1008 "points_within_dist(ray[0]=%g,%g, quadPt=%g,%g, error=%g)", 1009 ray[0].fX, ray[0].fY, quadPt.fX, quadPt.fY, error); 1010 } 1011 // otherwise, subdivide 1012 return STROKER_RESULT(kSplit_ResultType, depth, quadPts, "%s", "fall through"); 1013} 1014 1015SkPathStroker::ResultType SkPathStroker::compareQuadCubic(const SkPoint cubic[4], 1016 SkQuadConstruct* quadPts) { 1017 // get the quadratic approximation of the stroke 1018 if (!this->cubicQuadEnds(cubic, quadPts)) { 1019 return kNormalError_ResultType; 1020 } 1021 ResultType resultType = this->intersectRay(quadPts, kCtrlPt_RayType 1022 STROKER_DEBUG_PARAMS(fRecursionDepth) ); 1023 if (resultType != kQuad_ResultType) { 1024 return resultType; 1025 } 1026 // project a ray from the curve to the stroke 1027 SkPoint ray[2]; // points near midpoint on quad, midpoint on cubic 1028 if (!this->cubicPerpRay(cubic, quadPts->fMidT, &ray[1], &ray[0], nullptr)) { 1029 return kNormalError_ResultType; 1030 } 1031 return this->strokeCloseEnough(quadPts->fQuad, ray, quadPts 1032 STROKER_DEBUG_PARAMS(fRecursionDepth)); 1033} 1034 1035SkPathStroker::ResultType SkPathStroker::compareQuadConic(const SkConic& conic, 1036 SkQuadConstruct* quadPts) const { 1037 // get the quadratic approximation of the stroke 1038 this->conicQuadEnds(conic, quadPts); 1039 ResultType resultType = this->intersectRay(quadPts, kCtrlPt_RayType 1040 STROKER_DEBUG_PARAMS(fRecursionDepth) ); 1041 if (resultType != kQuad_ResultType) { 1042 return resultType; 1043 } 1044 // project a ray from the curve to the stroke 1045 SkPoint ray[2]; // points near midpoint on quad, midpoint on conic 1046 this->conicPerpRay(conic, quadPts->fMidT, &ray[1], &ray[0], nullptr); 1047 return this->strokeCloseEnough(quadPts->fQuad, ray, quadPts 1048 STROKER_DEBUG_PARAMS(fRecursionDepth)); 1049} 1050 1051SkPathStroker::ResultType SkPathStroker::compareQuadQuad(const SkPoint quad[3], 1052 SkQuadConstruct* quadPts) { 1053 // get the quadratic approximation of the stroke 1054 if (!quadPts->fStartSet) { 1055 SkPoint quadStartPt; 1056 this->quadPerpRay(quad, quadPts->fStartT, &quadStartPt, &quadPts->fQuad[0], 1057 &quadPts->fTangentStart); 1058 quadPts->fStartSet = true; 1059 } 1060 if (!quadPts->fEndSet) { 1061 SkPoint quadEndPt; 1062 this->quadPerpRay(quad, quadPts->fEndT, &quadEndPt, &quadPts->fQuad[2], 1063 &quadPts->fTangentEnd); 1064 quadPts->fEndSet = true; 1065 } 1066 ResultType resultType = this->intersectRay(quadPts, kCtrlPt_RayType 1067 STROKER_DEBUG_PARAMS(fRecursionDepth)); 1068 if (resultType != kQuad_ResultType) { 1069 return resultType; 1070 } 1071 // project a ray from the curve to the stroke 1072 SkPoint ray[2]; 1073 this->quadPerpRay(quad, quadPts->fMidT, &ray[1], &ray[0], nullptr); 1074 return this->strokeCloseEnough(quadPts->fQuad, ray, quadPts 1075 STROKER_DEBUG_PARAMS(fRecursionDepth)); 1076} 1077 1078void SkPathStroker::addDegenerateLine(const SkQuadConstruct* quadPts) { 1079 const SkPoint* quad = quadPts->fQuad; 1080 SkPath* path = fStrokeType == kOuter_StrokeType ? &fOuter : &fInner; 1081 path->lineTo(quad[2].fX, quad[2].fY); 1082} 1083 1084bool SkPathStroker::cubicMidOnLine(const SkPoint cubic[4], const SkQuadConstruct* quadPts) const { 1085 SkPoint strokeMid; 1086 if (!cubicQuadMid(cubic, quadPts, &strokeMid)) { 1087 return false; 1088 } 1089 SkScalar dist = pt_to_line(strokeMid, quadPts->fQuad[0], quadPts->fQuad[2]); 1090 return dist < fInvResScaleSquared; 1091} 1092 1093bool SkPathStroker::cubicStroke(const SkPoint cubic[4], SkQuadConstruct* quadPts) { 1094 if (!fFoundTangents) { 1095 ResultType resultType = this->tangentsMeet(cubic, quadPts); 1096 if (kQuad_ResultType != resultType) { 1097 if (kNormalError_ResultType == resultType) { 1098 return false; 1099 } 1100 if ((kDegenerate_ResultType == resultType 1101 || points_within_dist(quadPts->fQuad[0], quadPts->fQuad[2], 1102 fInvResScale)) && cubicMidOnLine(cubic, quadPts)) { 1103 addDegenerateLine(quadPts); 1104 return true; 1105 } 1106 } else { 1107 fFoundTangents = true; 1108 } 1109 } 1110 if (fFoundTangents) { 1111 ResultType resultType = this->compareQuadCubic(cubic, quadPts); 1112 if (kQuad_ResultType == resultType) { 1113 SkPath* path = fStrokeType == kOuter_StrokeType ? &fOuter : &fInner; 1114 const SkPoint* stroke = quadPts->fQuad; 1115 path->quadTo(stroke[1].fX, stroke[1].fY, stroke[2].fX, stroke[2].fY); 1116 return true; 1117 } 1118 if (kDegenerate_ResultType == resultType) { 1119 addDegenerateLine(quadPts); 1120 return true; 1121 } 1122 if (kNormalError_ResultType == resultType) { 1123 return false; 1124 } 1125 } 1126 if (!SkScalarIsFinite(quadPts->fQuad[2].fX) || !SkScalarIsFinite(quadPts->fQuad[2].fY)) { 1127 return false; // just abort if projected quad isn't representable 1128 } 1129 SkDEBUGCODE(gMaxRecursion[fFoundTangents] = SkTMax(gMaxRecursion[fFoundTangents], 1130 fRecursionDepth + 1)); 1131 if (++fRecursionDepth > kRecursiveLimits[fFoundTangents]) { 1132 return false; // just abort if projected quad isn't representable 1133 } 1134 SkQuadConstruct half; 1135 if (!half.initWithStart(quadPts)) { 1136 addDegenerateLine(quadPts); 1137 return true; 1138 } 1139 if (!this->cubicStroke(cubic, &half)) { 1140 return false; 1141 } 1142 if (!half.initWithEnd(quadPts)) { 1143 addDegenerateLine(quadPts); 1144 return true; 1145 } 1146 if (!this->cubicStroke(cubic, &half)) { 1147 return false; 1148 } 1149 --fRecursionDepth; 1150 return true; 1151} 1152 1153bool SkPathStroker::conicStroke(const SkConic& conic, SkQuadConstruct* quadPts) { 1154 ResultType resultType = this->compareQuadConic(conic, quadPts); 1155 if (kQuad_ResultType == resultType) { 1156 const SkPoint* stroke = quadPts->fQuad; 1157 SkPath* path = fStrokeType == kOuter_StrokeType ? &fOuter : &fInner; 1158 path->quadTo(stroke[1].fX, stroke[1].fY, stroke[2].fX, stroke[2].fY); 1159 return true; 1160 } 1161 if (kDegenerate_ResultType == resultType) { 1162 addDegenerateLine(quadPts); 1163 return true; 1164 } 1165 SkDEBUGCODE(gMaxRecursion[kConic_RecursiveLimit] = SkTMax(gMaxRecursion[kConic_RecursiveLimit], 1166 fRecursionDepth + 1)); 1167 if (++fRecursionDepth > kRecursiveLimits[kConic_RecursiveLimit]) { 1168 return false; // just abort if projected quad isn't representable 1169 } 1170 SkQuadConstruct half; 1171 (void) half.initWithStart(quadPts); 1172 if (!this->conicStroke(conic, &half)) { 1173 return false; 1174 } 1175 (void) half.initWithEnd(quadPts); 1176 if (!this->conicStroke(conic, &half)) { 1177 return false; 1178 } 1179 --fRecursionDepth; 1180 return true; 1181} 1182 1183bool SkPathStroker::quadStroke(const SkPoint quad[3], SkQuadConstruct* quadPts) { 1184 ResultType resultType = this->compareQuadQuad(quad, quadPts); 1185 if (kQuad_ResultType == resultType) { 1186 const SkPoint* stroke = quadPts->fQuad; 1187 SkPath* path = fStrokeType == kOuter_StrokeType ? &fOuter : &fInner; 1188 path->quadTo(stroke[1].fX, stroke[1].fY, stroke[2].fX, stroke[2].fY); 1189 return true; 1190 } 1191 if (kDegenerate_ResultType == resultType) { 1192 addDegenerateLine(quadPts); 1193 return true; 1194 } 1195 SkDEBUGCODE(gMaxRecursion[kQuad_RecursiveLimit] = SkTMax(gMaxRecursion[kQuad_RecursiveLimit], 1196 fRecursionDepth + 1)); 1197 if (++fRecursionDepth > kRecursiveLimits[kQuad_RecursiveLimit]) { 1198 return false; // just abort if projected quad isn't representable 1199 } 1200 SkQuadConstruct half; 1201 (void) half.initWithStart(quadPts); 1202 if (!this->quadStroke(quad, &half)) { 1203 return false; 1204 } 1205 (void) half.initWithEnd(quadPts); 1206 if (!this->quadStroke(quad, &half)) { 1207 return false; 1208 } 1209 --fRecursionDepth; 1210 return true; 1211} 1212 1213void SkPathStroker::cubicTo(const SkPoint& pt1, const SkPoint& pt2, 1214 const SkPoint& pt3) { 1215 const SkPoint cubic[4] = { fPrevPt, pt1, pt2, pt3 }; 1216 SkPoint reduction[3]; 1217 const SkPoint* tangentPt; 1218 ReductionType reductionType = CheckCubicLinear(cubic, reduction, &tangentPt); 1219 if (kPoint_ReductionType == reductionType) { 1220 /* If the stroke consists of a moveTo followed by a degenerate curve, treat it 1221 as if it were followed by a zero-length line. Lines without length 1222 can have square and round end caps. */ 1223 this->lineTo(pt3); 1224 return; 1225 } 1226 if (kLine_ReductionType == reductionType) { 1227 this->lineTo(pt3); 1228 return; 1229 } 1230 if (kDegenerate_ReductionType <= reductionType && kDegenerate3_ReductionType >= reductionType) { 1231 this->lineTo(reduction[0]); 1232 SkStrokerPriv::JoinProc saveJoiner = fJoiner; 1233 fJoiner = SkStrokerPriv::JoinFactory(SkPaint::kRound_Join); 1234 if (kDegenerate2_ReductionType <= reductionType) { 1235 this->lineTo(reduction[1]); 1236 } 1237 if (kDegenerate3_ReductionType == reductionType) { 1238 this->lineTo(reduction[2]); 1239 } 1240 this->lineTo(pt3); 1241 fJoiner = saveJoiner; 1242 return; 1243 } 1244 SkASSERT(kQuad_ReductionType == reductionType); 1245 SkVector normalAB, unitAB, normalCD, unitCD; 1246 if (!this->preJoinTo(*tangentPt, &normalAB, &unitAB, false)) { 1247 this->lineTo(pt3); 1248 return; 1249 } 1250 SkScalar tValues[2]; 1251 int count = SkFindCubicInflections(cubic, tValues); 1252 SkScalar lastT = 0; 1253 for (int index = 0; index <= count; ++index) { 1254 SkScalar nextT = index < count ? tValues[index] : 1; 1255 SkQuadConstruct quadPts; 1256 this->init(kOuter_StrokeType, &quadPts, lastT, nextT); 1257 (void) this->cubicStroke(cubic, &quadPts); 1258 this->init(kInner_StrokeType, &quadPts, lastT, nextT); 1259 (void) this->cubicStroke(cubic, &quadPts); 1260 lastT = nextT; 1261 } 1262 // emit the join even if one stroke succeeded but the last one failed 1263 // this avoids reversing an inner stroke with a partial path followed by another moveto 1264 this->setCubicEndNormal(cubic, normalAB, unitAB, &normalCD, &unitCD); 1265 1266 this->postJoinTo(pt3, normalCD, unitCD); 1267} 1268 1269/////////////////////////////////////////////////////////////////////////////// 1270/////////////////////////////////////////////////////////////////////////////// 1271 1272#include "SkPaintDefaults.h" 1273 1274SkStroke::SkStroke() { 1275 fWidth = SK_Scalar1; 1276 fMiterLimit = SkPaintDefaults_MiterLimit; 1277 fCap = SkPaint::kDefault_Cap; 1278 fJoin = SkPaint::kDefault_Join; 1279 fDoFill = false; 1280} 1281 1282SkStroke::SkStroke(const SkPaint& p) { 1283 fWidth = p.getStrokeWidth(); 1284 fMiterLimit = p.getStrokeMiter(); 1285 fCap = (uint8_t)p.getStrokeCap(); 1286 fJoin = (uint8_t)p.getStrokeJoin(); 1287 fDoFill = SkToU8(p.getStyle() == SkPaint::kStrokeAndFill_Style); 1288} 1289 1290SkStroke::SkStroke(const SkPaint& p, SkScalar width) { 1291 fWidth = width; 1292 fMiterLimit = p.getStrokeMiter(); 1293 fCap = (uint8_t)p.getStrokeCap(); 1294 fJoin = (uint8_t)p.getStrokeJoin(); 1295 fDoFill = SkToU8(p.getStyle() == SkPaint::kStrokeAndFill_Style); 1296} 1297 1298void SkStroke::setWidth(SkScalar width) { 1299 SkASSERT(width >= 0); 1300 fWidth = width; 1301} 1302 1303void SkStroke::setMiterLimit(SkScalar miterLimit) { 1304 SkASSERT(miterLimit >= 0); 1305 fMiterLimit = miterLimit; 1306} 1307 1308void SkStroke::setCap(SkPaint::Cap cap) { 1309 SkASSERT((unsigned)cap < SkPaint::kCapCount); 1310 fCap = SkToU8(cap); 1311} 1312 1313void SkStroke::setJoin(SkPaint::Join join) { 1314 SkASSERT((unsigned)join < SkPaint::kJoinCount); 1315 fJoin = SkToU8(join); 1316} 1317 1318/////////////////////////////////////////////////////////////////////////////// 1319 1320// If src==dst, then we use a tmp path to record the stroke, and then swap 1321// its contents with src when we're done. 1322class AutoTmpPath { 1323public: 1324 AutoTmpPath(const SkPath& src, SkPath** dst) : fSrc(src) { 1325 if (&src == *dst) { 1326 *dst = &fTmpDst; 1327 fSwapWithSrc = true; 1328 } else { 1329 (*dst)->reset(); 1330 fSwapWithSrc = false; 1331 } 1332 } 1333 1334 ~AutoTmpPath() { 1335 if (fSwapWithSrc) { 1336 fTmpDst.swap(*const_cast<SkPath*>(&fSrc)); 1337 } 1338 } 1339 1340private: 1341 SkPath fTmpDst; 1342 const SkPath& fSrc; 1343 bool fSwapWithSrc; 1344}; 1345 1346void SkStroke::strokePath(const SkPath& src, SkPath* dst) const { 1347 SkASSERT(dst); 1348 1349 SkScalar radius = SkScalarHalf(fWidth); 1350 1351 AutoTmpPath tmp(src, &dst); 1352 1353 if (radius <= 0) { 1354 return; 1355 } 1356 1357 // If src is really a rect, call our specialty strokeRect() method 1358 { 1359 SkRect rect; 1360 bool isClosed; 1361 SkPath::Direction dir; 1362 if (src.isRect(&rect, &isClosed, &dir) && isClosed) { 1363 this->strokeRect(rect, dst, dir); 1364 // our answer should preserve the inverseness of the src 1365 if (src.isInverseFillType()) { 1366 SkASSERT(!dst->isInverseFillType()); 1367 dst->toggleInverseFillType(); 1368 } 1369 return; 1370 } 1371 } 1372 1373 SkPathStroker stroker(src, radius, fMiterLimit, this->getCap(), this->getJoin(), fResScale); 1374 SkPath::Iter iter(src, false); 1375 SkPath::Verb lastSegment = SkPath::kMove_Verb; 1376 1377 for (;;) { 1378 SkPoint pts[4]; 1379 switch (iter.next(pts, false)) { 1380 case SkPath::kMove_Verb: 1381 stroker.moveTo(pts[0]); 1382 break; 1383 case SkPath::kLine_Verb: 1384 stroker.lineTo(pts[1], &iter); 1385 lastSegment = SkPath::kLine_Verb; 1386 break; 1387 case SkPath::kQuad_Verb: 1388 stroker.quadTo(pts[1], pts[2]); 1389 lastSegment = SkPath::kQuad_Verb; 1390 break; 1391 case SkPath::kConic_Verb: { 1392 stroker.conicTo(pts[1], pts[2], iter.conicWeight()); 1393 lastSegment = SkPath::kConic_Verb; 1394 break; 1395 } break; 1396 case SkPath::kCubic_Verb: 1397 stroker.cubicTo(pts[1], pts[2], pts[3]); 1398 lastSegment = SkPath::kCubic_Verb; 1399 break; 1400 case SkPath::kClose_Verb: 1401 if (SkPaint::kButt_Cap != this->getCap()) { 1402 /* If the stroke consists of a moveTo followed by a close, treat it 1403 as if it were followed by a zero-length line. Lines without length 1404 can have square and round end caps. */ 1405 if (stroker.hasOnlyMoveTo()) { 1406 stroker.lineTo(stroker.moveToPt()); 1407 goto ZERO_LENGTH; 1408 } 1409 /* If the stroke consists of a moveTo followed by one or more zero-length 1410 verbs, then followed by a close, treat is as if it were followed by a 1411 zero-length line. Lines without length can have square & round end caps. */ 1412 if (stroker.isZeroLength()) { 1413 ZERO_LENGTH: 1414 lastSegment = SkPath::kLine_Verb; 1415 break; 1416 } 1417 } 1418 stroker.close(lastSegment == SkPath::kLine_Verb); 1419 break; 1420 case SkPath::kDone_Verb: 1421 goto DONE; 1422 } 1423 } 1424DONE: 1425 stroker.done(dst, lastSegment == SkPath::kLine_Verb); 1426 1427 if (fDoFill) { 1428 if (SkPathPriv::CheapIsFirstDirection(src, SkPathPriv::kCCW_FirstDirection)) { 1429 dst->reverseAddPath(src); 1430 } else { 1431 dst->addPath(src); 1432 } 1433 } else { 1434 // Seems like we can assume that a 2-point src would always result in 1435 // a convex stroke, but testing has proved otherwise. 1436 // TODO: fix the stroker to make this assumption true (without making 1437 // it slower that the work that will be done in computeConvexity()) 1438#if 0 1439 // this test results in a non-convex stroke :( 1440 static void test(SkCanvas* canvas) { 1441 SkPoint pts[] = { 146.333328, 192.333328, 300.333344, 293.333344 }; 1442 SkPaint paint; 1443 paint.setStrokeWidth(7); 1444 paint.setStrokeCap(SkPaint::kRound_Cap); 1445 canvas->drawLine(pts[0].fX, pts[0].fY, pts[1].fX, pts[1].fY, paint); 1446 } 1447#endif 1448#if 0 1449 if (2 == src.countPoints()) { 1450 dst->setIsConvex(true); 1451 } 1452#endif 1453 } 1454 1455 // our answer should preserve the inverseness of the src 1456 if (src.isInverseFillType()) { 1457 SkASSERT(!dst->isInverseFillType()); 1458 dst->toggleInverseFillType(); 1459 } 1460} 1461 1462static SkPath::Direction reverse_direction(SkPath::Direction dir) { 1463 static const SkPath::Direction gOpposite[] = { SkPath::kCCW_Direction, SkPath::kCW_Direction }; 1464 return gOpposite[dir]; 1465} 1466 1467static void addBevel(SkPath* path, const SkRect& r, const SkRect& outer, SkPath::Direction dir) { 1468 SkPoint pts[8]; 1469 1470 if (SkPath::kCW_Direction == dir) { 1471 pts[0].set(r.fLeft, outer.fTop); 1472 pts[1].set(r.fRight, outer.fTop); 1473 pts[2].set(outer.fRight, r.fTop); 1474 pts[3].set(outer.fRight, r.fBottom); 1475 pts[4].set(r.fRight, outer.fBottom); 1476 pts[5].set(r.fLeft, outer.fBottom); 1477 pts[6].set(outer.fLeft, r.fBottom); 1478 pts[7].set(outer.fLeft, r.fTop); 1479 } else { 1480 pts[7].set(r.fLeft, outer.fTop); 1481 pts[6].set(r.fRight, outer.fTop); 1482 pts[5].set(outer.fRight, r.fTop); 1483 pts[4].set(outer.fRight, r.fBottom); 1484 pts[3].set(r.fRight, outer.fBottom); 1485 pts[2].set(r.fLeft, outer.fBottom); 1486 pts[1].set(outer.fLeft, r.fBottom); 1487 pts[0].set(outer.fLeft, r.fTop); 1488 } 1489 path->addPoly(pts, 8, true); 1490} 1491 1492void SkStroke::strokeRect(const SkRect& origRect, SkPath* dst, 1493 SkPath::Direction dir) const { 1494 SkASSERT(dst != nullptr); 1495 dst->reset(); 1496 1497 SkScalar radius = SkScalarHalf(fWidth); 1498 if (radius <= 0) { 1499 return; 1500 } 1501 1502 SkScalar rw = origRect.width(); 1503 SkScalar rh = origRect.height(); 1504 if ((rw < 0) ^ (rh < 0)) { 1505 dir = reverse_direction(dir); 1506 } 1507 SkRect rect(origRect); 1508 rect.sort(); 1509 // reassign these, now that we know they'll be >= 0 1510 rw = rect.width(); 1511 rh = rect.height(); 1512 1513 SkRect r(rect); 1514 r.outset(radius, radius); 1515 1516 SkPaint::Join join = (SkPaint::Join)fJoin; 1517 if (SkPaint::kMiter_Join == join && fMiterLimit < SK_ScalarSqrt2) { 1518 join = SkPaint::kBevel_Join; 1519 } 1520 1521 switch (join) { 1522 case SkPaint::kMiter_Join: 1523 dst->addRect(r, dir); 1524 break; 1525 case SkPaint::kBevel_Join: 1526 addBevel(dst, rect, r, dir); 1527 break; 1528 case SkPaint::kRound_Join: 1529 dst->addRoundRect(r, radius, radius, dir); 1530 break; 1531 default: 1532 break; 1533 } 1534 1535 if (fWidth < SkMinScalar(rw, rh) && !fDoFill) { 1536 r = rect; 1537 r.inset(radius, radius); 1538 dst->addRect(r, reverse_direction(dir)); 1539 } 1540} 1541