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