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