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