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