1 /* 2 * Copyright 2006 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 <cmath> 9 #include "SkBuffer.h" 10 #include "SkCubicClipper.h" 11 #include "SkGeometry.h" 12 #include "SkMath.h" 13 #include "SkPathPriv.h" 14 #include "SkPathRef.h" 15 #include "SkRRect.h" 16 17 static float poly_eval(float A, float B, float C, float t) { 18 return (A * t + B) * t + C; 19 } 20 21 static float poly_eval(float A, float B, float C, float D, float t) { 22 return ((A * t + B) * t + C) * t + D; 23 } 24 25 //////////////////////////////////////////////////////////////////////////// 26 27 /** 28 * Path.bounds is defined to be the bounds of all the control points. 29 * If we called bounds.join(r) we would skip r if r was empty, which breaks 30 * our promise. Hence we have a custom joiner that doesn't look at emptiness 31 */ 32 static void joinNoEmptyChecks(SkRect* dst, const SkRect& src) { 33 dst->fLeft = SkMinScalar(dst->fLeft, src.fLeft); 34 dst->fTop = SkMinScalar(dst->fTop, src.fTop); 35 dst->fRight = SkMaxScalar(dst->fRight, src.fRight); 36 dst->fBottom = SkMaxScalar(dst->fBottom, src.fBottom); 37 } 38 39 static bool is_degenerate(const SkPath& path) { 40 SkPath::Iter iter(path, false); 41 SkPoint pts[4]; 42 return SkPath::kDone_Verb == iter.next(pts); 43 } 44 45 class SkAutoDisableDirectionCheck { 46 public: 47 SkAutoDisableDirectionCheck(SkPath* path) : fPath(path) { 48 fSaved = static_cast<SkPathPriv::FirstDirection>(fPath->fFirstDirection.load()); 49 } 50 51 ~SkAutoDisableDirectionCheck() { 52 fPath->fFirstDirection = fSaved; 53 } 54 55 private: 56 SkPath* fPath; 57 SkPathPriv::FirstDirection fSaved; 58 }; 59 #define SkAutoDisableDirectionCheck(...) SK_REQUIRE_LOCAL_VAR(SkAutoDisableDirectionCheck) 60 61 /* This guy's constructor/destructor bracket a path editing operation. It is 62 used when we know the bounds of the amount we are going to add to the path 63 (usually a new contour, but not required). 64 65 It captures some state about the path up front (i.e. if it already has a 66 cached bounds), and then if it can, it updates the cache bounds explicitly, 67 avoiding the need to revisit all of the points in getBounds(). 68 69 It also notes if the path was originally degenerate, and if so, sets 70 isConvex to true. Thus it can only be used if the contour being added is 71 convex. 72 */ 73 class SkAutoPathBoundsUpdate { 74 public: 75 SkAutoPathBoundsUpdate(SkPath* path, const SkRect& r) : fRect(r) { 76 this->init(path); 77 } 78 79 SkAutoPathBoundsUpdate(SkPath* path, SkScalar left, SkScalar top, 80 SkScalar right, SkScalar bottom) { 81 fRect.set(left, top, right, bottom); 82 this->init(path); 83 } 84 85 ~SkAutoPathBoundsUpdate() { 86 fPath->setConvexity(fDegenerate ? SkPath::kConvex_Convexity 87 : SkPath::kUnknown_Convexity); 88 if (fEmpty || fHasValidBounds) { 89 fPath->setBounds(fRect); 90 } 91 } 92 93 private: 94 SkPath* fPath; 95 SkRect fRect; 96 bool fHasValidBounds; 97 bool fDegenerate; 98 bool fEmpty; 99 100 void init(SkPath* path) { 101 // Cannot use fRect for our bounds unless we know it is sorted 102 fRect.sort(); 103 fPath = path; 104 // Mark the path's bounds as dirty if (1) they are, or (2) the path 105 // is non-finite, and therefore its bounds are not meaningful 106 fHasValidBounds = path->hasComputedBounds() && path->isFinite(); 107 fEmpty = path->isEmpty(); 108 if (fHasValidBounds && !fEmpty) { 109 joinNoEmptyChecks(&fRect, fPath->getBounds()); 110 } 111 fDegenerate = is_degenerate(*path); 112 } 113 }; 114 #define SkAutoPathBoundsUpdate(...) SK_REQUIRE_LOCAL_VAR(SkAutoPathBoundsUpdate) 115 116 //////////////////////////////////////////////////////////////////////////// 117 118 /* 119 Stores the verbs and points as they are given to us, with exceptions: 120 - we only record "Close" if it was immediately preceeded by Move | Line | Quad | Cubic 121 - we insert a Move(0,0) if Line | Quad | Cubic is our first command 122 123 The iterator does more cleanup, especially if forceClose == true 124 1. If we encounter degenerate segments, remove them 125 2. if we encounter Close, return a cons'd up Line() first (if the curr-pt != start-pt) 126 3. if we encounter Move without a preceeding Close, and forceClose is true, goto #2 127 4. if we encounter Line | Quad | Cubic after Close, cons up a Move 128 */ 129 130 //////////////////////////////////////////////////////////////////////////// 131 132 // flag to require a moveTo if we begin with something else, like lineTo etc. 133 #define INITIAL_LASTMOVETOINDEX_VALUE ~0 134 135 SkPath::SkPath() 136 : fPathRef(SkPathRef::CreateEmpty()) { 137 this->resetFields(); 138 fIsVolatile = false; 139 } 140 141 void SkPath::resetFields() { 142 //fPathRef is assumed to have been emptied by the caller. 143 fLastMoveToIndex = INITIAL_LASTMOVETOINDEX_VALUE; 144 fFillType = kWinding_FillType; 145 fConvexity = kUnknown_Convexity; 146 fFirstDirection = SkPathPriv::kUnknown_FirstDirection; 147 148 // We don't touch Android's fSourcePath. It's used to track texture garbage collection, so we 149 // don't want to muck with it if it's been set to something non-nullptr. 150 } 151 152 SkPath::SkPath(const SkPath& that) 153 : fPathRef(SkRef(that.fPathRef.get())) { 154 this->copyFields(that); 155 SkDEBUGCODE(that.validate();) 156 } 157 158 SkPath::~SkPath() { 159 SkDEBUGCODE(this->validate();) 160 } 161 162 SkPath& SkPath::operator=(const SkPath& that) { 163 SkDEBUGCODE(that.validate();) 164 165 if (this != &that) { 166 fPathRef.reset(SkRef(that.fPathRef.get())); 167 this->copyFields(that); 168 } 169 SkDEBUGCODE(this->validate();) 170 return *this; 171 } 172 173 void SkPath::copyFields(const SkPath& that) { 174 //fPathRef is assumed to have been set by the caller. 175 fLastMoveToIndex = that.fLastMoveToIndex; 176 fFillType = that.fFillType; 177 fConvexity = that.fConvexity; 178 // Simulate fFirstDirection = that.fFirstDirection; 179 fFirstDirection.store(that.fFirstDirection.load()); 180 fIsVolatile = that.fIsVolatile; 181 } 182 183 bool operator==(const SkPath& a, const SkPath& b) { 184 // note: don't need to look at isConvex or bounds, since just comparing the 185 // raw data is sufficient. 186 return &a == &b || 187 (a.fFillType == b.fFillType && *a.fPathRef.get() == *b.fPathRef.get()); 188 } 189 190 void SkPath::swap(SkPath& that) { 191 if (this != &that) { 192 fPathRef.swap(that.fPathRef); 193 SkTSwap<int>(fLastMoveToIndex, that.fLastMoveToIndex); 194 SkTSwap<uint8_t>(fFillType, that.fFillType); 195 SkTSwap<uint8_t>(fConvexity, that.fConvexity); 196 // Simulate SkTSwap<uint8_t>(fFirstDirection, that.fFirstDirection); 197 uint8_t temp = fFirstDirection; 198 fFirstDirection.store(that.fFirstDirection.load()); 199 that.fFirstDirection.store(temp); 200 SkTSwap<SkBool8>(fIsVolatile, that.fIsVolatile); 201 } 202 } 203 204 bool SkPath::isInterpolatable(const SkPath& compare) const { 205 int count = fPathRef->countVerbs(); 206 if (count != compare.fPathRef->countVerbs()) { 207 return false; 208 } 209 if (!count) { 210 return true; 211 } 212 if (memcmp(fPathRef->verbsMemBegin(), compare.fPathRef->verbsMemBegin(), 213 count)) { 214 return false; 215 } 216 return !fPathRef->countWeights() || 217 !SkToBool(memcmp(fPathRef->conicWeights(), compare.fPathRef->conicWeights(), 218 fPathRef->countWeights() * sizeof(*fPathRef->conicWeights()))); 219 } 220 221 bool SkPath::interpolate(const SkPath& ending, SkScalar weight, SkPath* out) const { 222 int verbCount = fPathRef->countVerbs(); 223 if (verbCount != ending.fPathRef->countVerbs()) { 224 return false; 225 } 226 if (!verbCount) { 227 return true; 228 } 229 out->reset(); 230 out->addPath(*this); 231 fPathRef->interpolate(*ending.fPathRef, weight, out->fPathRef.get()); 232 return true; 233 } 234 235 static inline bool check_edge_against_rect(const SkPoint& p0, 236 const SkPoint& p1, 237 const SkRect& rect, 238 SkPathPriv::FirstDirection dir) { 239 const SkPoint* edgeBegin; 240 SkVector v; 241 if (SkPathPriv::kCW_FirstDirection == dir) { 242 v = p1 - p0; 243 edgeBegin = &p0; 244 } else { 245 v = p0 - p1; 246 edgeBegin = &p1; 247 } 248 if (v.fX || v.fY) { 249 // check the cross product of v with the vec from edgeBegin to each rect corner 250 SkScalar yL = v.fY * (rect.fLeft - edgeBegin->fX); 251 SkScalar xT = v.fX * (rect.fTop - edgeBegin->fY); 252 SkScalar yR = v.fY * (rect.fRight - edgeBegin->fX); 253 SkScalar xB = v.fX * (rect.fBottom - edgeBegin->fY); 254 if ((xT < yL) || (xT < yR) || (xB < yL) || (xB < yR)) { 255 return false; 256 } 257 } 258 return true; 259 } 260 261 bool SkPath::conservativelyContainsRect(const SkRect& rect) const { 262 // This only handles non-degenerate convex paths currently. 263 if (kConvex_Convexity != this->getConvexity()) { 264 return false; 265 } 266 267 SkPathPriv::FirstDirection direction; 268 if (!SkPathPriv::CheapComputeFirstDirection(*this, &direction)) { 269 return false; 270 } 271 272 SkPoint firstPt; 273 SkPoint prevPt; 274 SkPath::Iter iter(*this, true); 275 SkPath::Verb verb; 276 SkPoint pts[4]; 277 SkDEBUGCODE(int moveCnt = 0;) 278 SkDEBUGCODE(int segmentCount = 0;) 279 SkDEBUGCODE(int closeCount = 0;) 280 281 while ((verb = iter.next(pts, true, true)) != kDone_Verb) { 282 int nextPt = -1; 283 switch (verb) { 284 case kMove_Verb: 285 SkASSERT(!segmentCount && !closeCount); 286 SkDEBUGCODE(++moveCnt); 287 firstPt = prevPt = pts[0]; 288 break; 289 case kLine_Verb: 290 nextPt = 1; 291 SkASSERT(moveCnt && !closeCount); 292 SkDEBUGCODE(++segmentCount); 293 break; 294 case kQuad_Verb: 295 case kConic_Verb: 296 SkASSERT(moveCnt && !closeCount); 297 SkDEBUGCODE(++segmentCount); 298 nextPt = 2; 299 break; 300 case kCubic_Verb: 301 SkASSERT(moveCnt && !closeCount); 302 SkDEBUGCODE(++segmentCount); 303 nextPt = 3; 304 break; 305 case kClose_Verb: 306 SkDEBUGCODE(++closeCount;) 307 break; 308 default: 309 SkDEBUGFAIL("unknown verb"); 310 } 311 if (-1 != nextPt) { 312 if (SkPath::kConic_Verb == verb) { 313 SkConic orig; 314 orig.set(pts, iter.conicWeight()); 315 SkPoint quadPts[5]; 316 int count = orig.chopIntoQuadsPOW2(quadPts, 1); 317 SkASSERT_RELEASE(2 == count); 318 319 if (!check_edge_against_rect(quadPts[0], quadPts[2], rect, direction)) { 320 return false; 321 } 322 if (!check_edge_against_rect(quadPts[2], quadPts[4], rect, direction)) { 323 return false; 324 } 325 } else { 326 if (!check_edge_against_rect(prevPt, pts[nextPt], rect, direction)) { 327 return false; 328 } 329 } 330 prevPt = pts[nextPt]; 331 } 332 } 333 334 return check_edge_against_rect(prevPt, firstPt, rect, direction); 335 } 336 337 uint32_t SkPath::getGenerationID() const { 338 uint32_t genID = fPathRef->genID(); 339 #ifdef SK_BUILD_FOR_ANDROID_FRAMEWORK 340 SkASSERT((unsigned)fFillType < (1 << (32 - kPathRefGenIDBitCnt))); 341 genID |= static_cast<uint32_t>(fFillType) << kPathRefGenIDBitCnt; 342 #endif 343 return genID; 344 } 345 346 void SkPath::reset() { 347 SkDEBUGCODE(this->validate();) 348 349 fPathRef.reset(SkPathRef::CreateEmpty()); 350 this->resetFields(); 351 } 352 353 void SkPath::rewind() { 354 SkDEBUGCODE(this->validate();) 355 356 SkPathRef::Rewind(&fPathRef); 357 this->resetFields(); 358 } 359 360 bool SkPath::isLastContourClosed() const { 361 int verbCount = fPathRef->countVerbs(); 362 if (0 == verbCount) { 363 return false; 364 } 365 return kClose_Verb == fPathRef->atVerb(verbCount - 1); 366 } 367 368 bool SkPath::isLine(SkPoint line[2]) const { 369 int verbCount = fPathRef->countVerbs(); 370 371 if (2 == verbCount) { 372 SkASSERT(kMove_Verb == fPathRef->atVerb(0)); 373 if (kLine_Verb == fPathRef->atVerb(1)) { 374 SkASSERT(2 == fPathRef->countPoints()); 375 if (line) { 376 const SkPoint* pts = fPathRef->points(); 377 line[0] = pts[0]; 378 line[1] = pts[1]; 379 } 380 return true; 381 } 382 } 383 return false; 384 } 385 386 /* 387 Determines if path is a rect by keeping track of changes in direction 388 and looking for a loop either clockwise or counterclockwise. 389 390 The direction is computed such that: 391 0: vertical up 392 1: horizontal left 393 2: vertical down 394 3: horizontal right 395 396 A rectangle cycles up/right/down/left or up/left/down/right. 397 398 The test fails if: 399 The path is closed, and followed by a line. 400 A second move creates a new endpoint. 401 A diagonal line is parsed. 402 There's more than four changes of direction. 403 There's a discontinuity on the line (e.g., a move in the middle) 404 The line reverses direction. 405 The path contains a quadratic or cubic. 406 The path contains fewer than four points. 407 *The rectangle doesn't complete a cycle. 408 *The final point isn't equal to the first point. 409 410 *These last two conditions we relax if we have a 3-edge path that would 411 form a rectangle if it were closed (as we do when we fill a path) 412 413 It's OK if the path has: 414 Several colinear line segments composing a rectangle side. 415 Single points on the rectangle side. 416 417 The direction takes advantage of the corners found since opposite sides 418 must travel in opposite directions. 419 420 FIXME: Allow colinear quads and cubics to be treated like lines. 421 FIXME: If the API passes fill-only, return true if the filled stroke 422 is a rectangle, though the caller failed to close the path. 423 424 first,last,next direction state-machine: 425 0x1 is set if the segment is horizontal 426 0x2 is set if the segment is moving to the right or down 427 thus: 428 two directions are opposites iff (dirA ^ dirB) == 0x2 429 two directions are perpendicular iff (dirA ^ dirB) == 0x1 430 431 */ 432 static int rect_make_dir(SkScalar dx, SkScalar dy) { 433 return ((0 != dx) << 0) | ((dx > 0 || dy > 0) << 1); 434 } 435 bool SkPath::isRectContour(bool allowPartial, int* currVerb, const SkPoint** ptsPtr, 436 bool* isClosed, Direction* direction) const { 437 int corners = 0; 438 SkPoint first, last; 439 const SkPoint* pts = *ptsPtr; 440 const SkPoint* savePts = nullptr; 441 first.set(0, 0); 442 last.set(0, 0); 443 int firstDirection = 0; 444 int lastDirection = 0; 445 int nextDirection = 0; 446 bool closedOrMoved = false; 447 bool autoClose = false; 448 bool insertClose = false; 449 int verbCnt = fPathRef->countVerbs(); 450 while (*currVerb < verbCnt && (!allowPartial || !autoClose)) { 451 uint8_t verb = insertClose ? (uint8_t) kClose_Verb : fPathRef->atVerb(*currVerb); 452 switch (verb) { 453 case kClose_Verb: 454 savePts = pts; 455 pts = *ptsPtr; 456 autoClose = true; 457 insertClose = false; 458 case kLine_Verb: { 459 SkScalar left = last.fX; 460 SkScalar top = last.fY; 461 SkScalar right = pts->fX; 462 SkScalar bottom = pts->fY; 463 ++pts; 464 if (left != right && top != bottom) { 465 return false; // diagonal 466 } 467 if (left == right && top == bottom) { 468 break; // single point on side OK 469 } 470 nextDirection = rect_make_dir(right - left, bottom - top); 471 if (0 == corners) { 472 firstDirection = nextDirection; 473 first = last; 474 last = pts[-1]; 475 corners = 1; 476 closedOrMoved = false; 477 break; 478 } 479 if (closedOrMoved) { 480 return false; // closed followed by a line 481 } 482 if (autoClose && nextDirection == firstDirection) { 483 break; // colinear with first 484 } 485 closedOrMoved = autoClose; 486 if (lastDirection != nextDirection) { 487 if (++corners > 4) { 488 return false; // too many direction changes 489 } 490 } 491 last = pts[-1]; 492 if (lastDirection == nextDirection) { 493 break; // colinear segment 494 } 495 // Possible values for corners are 2, 3, and 4. 496 // When corners == 3, nextDirection opposes firstDirection. 497 // Otherwise, nextDirection at corner 2 opposes corner 4. 498 int turn = firstDirection ^ (corners - 1); 499 int directionCycle = 3 == corners ? 0 : nextDirection ^ turn; 500 if ((directionCycle ^ turn) != nextDirection) { 501 return false; // direction didn't follow cycle 502 } 503 break; 504 } 505 case kQuad_Verb: 506 case kConic_Verb: 507 case kCubic_Verb: 508 return false; // quadratic, cubic not allowed 509 case kMove_Verb: 510 if (allowPartial && !autoClose && firstDirection) { 511 insertClose = true; 512 *currVerb -= 1; // try move again afterwards 513 goto addMissingClose; 514 } 515 last = *pts++; 516 closedOrMoved = true; 517 break; 518 default: 519 SkDEBUGFAIL("unexpected verb"); 520 break; 521 } 522 *currVerb += 1; 523 lastDirection = nextDirection; 524 addMissingClose: 525 ; 526 } 527 // Success if 4 corners and first point equals last 528 bool result = 4 == corners && (first == last || autoClose); 529 if (!result) { 530 // check if we are just an incomplete rectangle, in which case we can 531 // return true, but not claim to be closed. 532 // e.g. 533 // 3 sided rectangle 534 // 4 sided but the last edge is not long enough to reach the start 535 // 536 SkScalar closeX = first.x() - last.x(); 537 SkScalar closeY = first.y() - last.y(); 538 if (closeX && closeY) { 539 return false; // we're diagonal, abort (can we ever reach this?) 540 } 541 int closeDirection = rect_make_dir(closeX, closeY); 542 // make sure the close-segment doesn't double-back on itself 543 if (3 == corners || (4 == corners && closeDirection == lastDirection)) { 544 result = true; 545 autoClose = false; // we are not closed 546 } 547 } 548 if (savePts) { 549 *ptsPtr = savePts; 550 } 551 if (result && isClosed) { 552 *isClosed = autoClose; 553 } 554 if (result && direction) { 555 *direction = firstDirection == ((lastDirection + 1) & 3) ? kCCW_Direction : kCW_Direction; 556 } 557 return result; 558 } 559 560 bool SkPath::isRect(SkRect* rect, bool* isClosed, Direction* direction) const { 561 SkDEBUGCODE(this->validate();) 562 int currVerb = 0; 563 const SkPoint* pts = fPathRef->points(); 564 const SkPoint* first = pts; 565 if (!this->isRectContour(false, &currVerb, &pts, isClosed, direction)) { 566 return false; 567 } 568 if (rect) { 569 int32_t num = SkToS32(pts - first); 570 if (num) { 571 rect->set(first, num); 572 } else { 573 // 'pts' isn't updated for open rects 574 *rect = this->getBounds(); 575 } 576 } 577 return true; 578 } 579 580 bool SkPath::isNestedFillRects(SkRect rects[2], Direction dirs[2]) const { 581 SkDEBUGCODE(this->validate();) 582 int currVerb = 0; 583 const SkPoint* pts = fPathRef->points(); 584 const SkPoint* first = pts; 585 Direction testDirs[2]; 586 if (!isRectContour(true, &currVerb, &pts, nullptr, &testDirs[0])) { 587 return false; 588 } 589 const SkPoint* last = pts; 590 SkRect testRects[2]; 591 bool isClosed; 592 if (isRectContour(false, &currVerb, &pts, &isClosed, &testDirs[1])) { 593 testRects[0].set(first, SkToS32(last - first)); 594 if (!isClosed) { 595 pts = fPathRef->points() + fPathRef->countPoints(); 596 } 597 testRects[1].set(last, SkToS32(pts - last)); 598 if (testRects[0].contains(testRects[1])) { 599 if (rects) { 600 rects[0] = testRects[0]; 601 rects[1] = testRects[1]; 602 } 603 if (dirs) { 604 dirs[0] = testDirs[0]; 605 dirs[1] = testDirs[1]; 606 } 607 return true; 608 } 609 if (testRects[1].contains(testRects[0])) { 610 if (rects) { 611 rects[0] = testRects[1]; 612 rects[1] = testRects[0]; 613 } 614 if (dirs) { 615 dirs[0] = testDirs[1]; 616 dirs[1] = testDirs[0]; 617 } 618 return true; 619 } 620 } 621 return false; 622 } 623 624 int SkPath::countPoints() const { 625 return fPathRef->countPoints(); 626 } 627 628 int SkPath::getPoints(SkPoint dst[], int max) const { 629 SkDEBUGCODE(this->validate();) 630 631 SkASSERT(max >= 0); 632 SkASSERT(!max || dst); 633 int count = SkMin32(max, fPathRef->countPoints()); 634 sk_careful_memcpy(dst, fPathRef->points(), count * sizeof(SkPoint)); 635 return fPathRef->countPoints(); 636 } 637 638 SkPoint SkPath::getPoint(int index) const { 639 if ((unsigned)index < (unsigned)fPathRef->countPoints()) { 640 return fPathRef->atPoint(index); 641 } 642 return SkPoint::Make(0, 0); 643 } 644 645 int SkPath::countVerbs() const { 646 return fPathRef->countVerbs(); 647 } 648 649 static inline void copy_verbs_reverse(uint8_t* inorderDst, 650 const uint8_t* reversedSrc, 651 int count) { 652 for (int i = 0; i < count; ++i) { 653 inorderDst[i] = reversedSrc[~i]; 654 } 655 } 656 657 int SkPath::getVerbs(uint8_t dst[], int max) const { 658 SkDEBUGCODE(this->validate();) 659 660 SkASSERT(max >= 0); 661 SkASSERT(!max || dst); 662 int count = SkMin32(max, fPathRef->countVerbs()); 663 copy_verbs_reverse(dst, fPathRef->verbs(), count); 664 return fPathRef->countVerbs(); 665 } 666 667 bool SkPath::getLastPt(SkPoint* lastPt) const { 668 SkDEBUGCODE(this->validate();) 669 670 int count = fPathRef->countPoints(); 671 if (count > 0) { 672 if (lastPt) { 673 *lastPt = fPathRef->atPoint(count - 1); 674 } 675 return true; 676 } 677 if (lastPt) { 678 lastPt->set(0, 0); 679 } 680 return false; 681 } 682 683 void SkPath::setPt(int index, SkScalar x, SkScalar y) { 684 SkDEBUGCODE(this->validate();) 685 686 int count = fPathRef->countPoints(); 687 if (count <= index) { 688 return; 689 } else { 690 SkPathRef::Editor ed(&fPathRef); 691 ed.atPoint(index)->set(x, y); 692 } 693 } 694 695 void SkPath::setLastPt(SkScalar x, SkScalar y) { 696 SkDEBUGCODE(this->validate();) 697 698 int count = fPathRef->countPoints(); 699 if (count == 0) { 700 this->moveTo(x, y); 701 } else { 702 SkPathRef::Editor ed(&fPathRef); 703 ed.atPoint(count-1)->set(x, y); 704 } 705 } 706 707 void SkPath::setConvexity(Convexity c) { 708 if (fConvexity != c) { 709 fConvexity = c; 710 } 711 } 712 713 ////////////////////////////////////////////////////////////////////////////// 714 // Construction methods 715 716 #define DIRTY_AFTER_EDIT \ 717 do { \ 718 fConvexity = kUnknown_Convexity; \ 719 fFirstDirection = SkPathPriv::kUnknown_FirstDirection; \ 720 } while (0) 721 722 void SkPath::incReserve(U16CPU inc) { 723 SkDEBUGCODE(this->validate();) 724 SkPathRef::Editor(&fPathRef, inc, inc); 725 SkDEBUGCODE(this->validate();) 726 } 727 728 void SkPath::moveTo(SkScalar x, SkScalar y) { 729 SkDEBUGCODE(this->validate();) 730 731 SkPathRef::Editor ed(&fPathRef); 732 733 // remember our index 734 fLastMoveToIndex = fPathRef->countPoints(); 735 736 ed.growForVerb(kMove_Verb)->set(x, y); 737 738 DIRTY_AFTER_EDIT; 739 } 740 741 void SkPath::rMoveTo(SkScalar x, SkScalar y) { 742 SkPoint pt; 743 this->getLastPt(&pt); 744 this->moveTo(pt.fX + x, pt.fY + y); 745 } 746 747 void SkPath::injectMoveToIfNeeded() { 748 if (fLastMoveToIndex < 0) { 749 SkScalar x, y; 750 if (fPathRef->countVerbs() == 0) { 751 x = y = 0; 752 } else { 753 const SkPoint& pt = fPathRef->atPoint(~fLastMoveToIndex); 754 x = pt.fX; 755 y = pt.fY; 756 } 757 this->moveTo(x, y); 758 } 759 } 760 761 void SkPath::lineTo(SkScalar x, SkScalar y) { 762 SkDEBUGCODE(this->validate();) 763 764 this->injectMoveToIfNeeded(); 765 766 SkPathRef::Editor ed(&fPathRef); 767 ed.growForVerb(kLine_Verb)->set(x, y); 768 769 DIRTY_AFTER_EDIT; 770 } 771 772 void SkPath::rLineTo(SkScalar x, SkScalar y) { 773 this->injectMoveToIfNeeded(); // This can change the result of this->getLastPt(). 774 SkPoint pt; 775 this->getLastPt(&pt); 776 this->lineTo(pt.fX + x, pt.fY + y); 777 } 778 779 void SkPath::quadTo(SkScalar x1, SkScalar y1, SkScalar x2, SkScalar y2) { 780 SkDEBUGCODE(this->validate();) 781 782 this->injectMoveToIfNeeded(); 783 784 SkPathRef::Editor ed(&fPathRef); 785 SkPoint* pts = ed.growForVerb(kQuad_Verb); 786 pts[0].set(x1, y1); 787 pts[1].set(x2, y2); 788 789 DIRTY_AFTER_EDIT; 790 } 791 792 void SkPath::rQuadTo(SkScalar x1, SkScalar y1, SkScalar x2, SkScalar y2) { 793 this->injectMoveToIfNeeded(); // This can change the result of this->getLastPt(). 794 SkPoint pt; 795 this->getLastPt(&pt); 796 this->quadTo(pt.fX + x1, pt.fY + y1, pt.fX + x2, pt.fY + y2); 797 } 798 799 void SkPath::conicTo(SkScalar x1, SkScalar y1, SkScalar x2, SkScalar y2, 800 SkScalar w) { 801 // check for <= 0 or NaN with this test 802 if (!(w > 0)) { 803 this->lineTo(x2, y2); 804 } else if (!SkScalarIsFinite(w)) { 805 this->lineTo(x1, y1); 806 this->lineTo(x2, y2); 807 } else if (SK_Scalar1 == w) { 808 this->quadTo(x1, y1, x2, y2); 809 } else { 810 SkDEBUGCODE(this->validate();) 811 812 this->injectMoveToIfNeeded(); 813 814 SkPathRef::Editor ed(&fPathRef); 815 SkPoint* pts = ed.growForVerb(kConic_Verb, w); 816 pts[0].set(x1, y1); 817 pts[1].set(x2, y2); 818 819 DIRTY_AFTER_EDIT; 820 } 821 } 822 823 void SkPath::rConicTo(SkScalar dx1, SkScalar dy1, SkScalar dx2, SkScalar dy2, 824 SkScalar w) { 825 this->injectMoveToIfNeeded(); // This can change the result of this->getLastPt(). 826 SkPoint pt; 827 this->getLastPt(&pt); 828 this->conicTo(pt.fX + dx1, pt.fY + dy1, pt.fX + dx2, pt.fY + dy2, w); 829 } 830 831 void SkPath::cubicTo(SkScalar x1, SkScalar y1, SkScalar x2, SkScalar y2, 832 SkScalar x3, SkScalar y3) { 833 SkDEBUGCODE(this->validate();) 834 835 this->injectMoveToIfNeeded(); 836 837 SkPathRef::Editor ed(&fPathRef); 838 SkPoint* pts = ed.growForVerb(kCubic_Verb); 839 pts[0].set(x1, y1); 840 pts[1].set(x2, y2); 841 pts[2].set(x3, y3); 842 843 DIRTY_AFTER_EDIT; 844 } 845 846 void SkPath::rCubicTo(SkScalar x1, SkScalar y1, SkScalar x2, SkScalar y2, 847 SkScalar x3, SkScalar y3) { 848 this->injectMoveToIfNeeded(); // This can change the result of this->getLastPt(). 849 SkPoint pt; 850 this->getLastPt(&pt); 851 this->cubicTo(pt.fX + x1, pt.fY + y1, pt.fX + x2, pt.fY + y2, 852 pt.fX + x3, pt.fY + y3); 853 } 854 855 void SkPath::close() { 856 SkDEBUGCODE(this->validate();) 857 858 int count = fPathRef->countVerbs(); 859 if (count > 0) { 860 switch (fPathRef->atVerb(count - 1)) { 861 case kLine_Verb: 862 case kQuad_Verb: 863 case kConic_Verb: 864 case kCubic_Verb: 865 case kMove_Verb: { 866 SkPathRef::Editor ed(&fPathRef); 867 ed.growForVerb(kClose_Verb); 868 break; 869 } 870 case kClose_Verb: 871 // don't add a close if it's the first verb or a repeat 872 break; 873 default: 874 SkDEBUGFAIL("unexpected verb"); 875 break; 876 } 877 } 878 879 // signal that we need a moveTo to follow us (unless we're done) 880 #if 0 881 if (fLastMoveToIndex >= 0) { 882 fLastMoveToIndex = ~fLastMoveToIndex; 883 } 884 #else 885 fLastMoveToIndex ^= ~fLastMoveToIndex >> (8 * sizeof(fLastMoveToIndex) - 1); 886 #endif 887 } 888 889 /////////////////////////////////////////////////////////////////////////////// 890 891 namespace { 892 893 template <unsigned N> 894 class PointIterator { 895 public: 896 PointIterator(SkPath::Direction dir, unsigned startIndex) 897 : fCurrent(startIndex % N) 898 , fAdvance(dir == SkPath::kCW_Direction ? 1 : N - 1) { } 899 900 const SkPoint& current() const { 901 SkASSERT(fCurrent < N); 902 return fPts[fCurrent]; 903 } 904 905 const SkPoint& next() { 906 fCurrent = (fCurrent + fAdvance) % N; 907 return this->current(); 908 } 909 910 protected: 911 SkPoint fPts[N]; 912 913 private: 914 unsigned fCurrent; 915 unsigned fAdvance; 916 }; 917 918 class RectPointIterator : public PointIterator<4> { 919 public: 920 RectPointIterator(const SkRect& rect, SkPath::Direction dir, unsigned startIndex) 921 : PointIterator(dir, startIndex) { 922 923 fPts[0] = SkPoint::Make(rect.fLeft, rect.fTop); 924 fPts[1] = SkPoint::Make(rect.fRight, rect.fTop); 925 fPts[2] = SkPoint::Make(rect.fRight, rect.fBottom); 926 fPts[3] = SkPoint::Make(rect.fLeft, rect.fBottom); 927 } 928 }; 929 930 class OvalPointIterator : public PointIterator<4> { 931 public: 932 OvalPointIterator(const SkRect& oval, SkPath::Direction dir, unsigned startIndex) 933 : PointIterator(dir, startIndex) { 934 935 const SkScalar cx = oval.centerX(); 936 const SkScalar cy = oval.centerY(); 937 938 fPts[0] = SkPoint::Make(cx, oval.fTop); 939 fPts[1] = SkPoint::Make(oval.fRight, cy); 940 fPts[2] = SkPoint::Make(cx, oval.fBottom); 941 fPts[3] = SkPoint::Make(oval.fLeft, cy); 942 } 943 }; 944 945 class RRectPointIterator : public PointIterator<8> { 946 public: 947 RRectPointIterator(const SkRRect& rrect, SkPath::Direction dir, unsigned startIndex) 948 : PointIterator(dir, startIndex) { 949 950 const SkRect& bounds = rrect.getBounds(); 951 const SkScalar L = bounds.fLeft; 952 const SkScalar T = bounds.fTop; 953 const SkScalar R = bounds.fRight; 954 const SkScalar B = bounds.fBottom; 955 956 fPts[0] = SkPoint::Make(L + rrect.radii(SkRRect::kUpperLeft_Corner).fX, T); 957 fPts[1] = SkPoint::Make(R - rrect.radii(SkRRect::kUpperRight_Corner).fX, T); 958 fPts[2] = SkPoint::Make(R, T + rrect.radii(SkRRect::kUpperRight_Corner).fY); 959 fPts[3] = SkPoint::Make(R, B - rrect.radii(SkRRect::kLowerRight_Corner).fY); 960 fPts[4] = SkPoint::Make(R - rrect.radii(SkRRect::kLowerRight_Corner).fX, B); 961 fPts[5] = SkPoint::Make(L + rrect.radii(SkRRect::kLowerLeft_Corner).fX, B); 962 fPts[6] = SkPoint::Make(L, B - rrect.radii(SkRRect::kLowerLeft_Corner).fY); 963 fPts[7] = SkPoint::Make(L, T + rrect.radii(SkRRect::kUpperLeft_Corner).fY); 964 } 965 }; 966 967 } // anonymous namespace 968 969 static void assert_known_direction(int dir) { 970 SkASSERT(SkPath::kCW_Direction == dir || SkPath::kCCW_Direction == dir); 971 } 972 973 void SkPath::addRect(const SkRect& rect, Direction dir) { 974 this->addRect(rect, dir, 0); 975 } 976 977 void SkPath::addRect(SkScalar left, SkScalar top, SkScalar right, 978 SkScalar bottom, Direction dir) { 979 this->addRect(SkRect::MakeLTRB(left, top, right, bottom), dir, 0); 980 } 981 982 void SkPath::addRect(const SkRect &rect, Direction dir, unsigned startIndex) { 983 assert_known_direction(dir); 984 fFirstDirection = this->hasOnlyMoveTos() ? 985 (SkPathPriv::FirstDirection)dir : SkPathPriv::kUnknown_FirstDirection; 986 SkAutoDisableDirectionCheck addc(this); 987 SkAutoPathBoundsUpdate apbu(this, rect); 988 989 SkDEBUGCODE(int initialVerbCount = this->countVerbs()); 990 991 const int kVerbs = 5; // moveTo + 3x lineTo + close 992 this->incReserve(kVerbs); 993 994 RectPointIterator iter(rect, dir, startIndex); 995 996 this->moveTo(iter.current()); 997 this->lineTo(iter.next()); 998 this->lineTo(iter.next()); 999 this->lineTo(iter.next()); 1000 this->close(); 1001 1002 SkASSERT(this->countVerbs() == initialVerbCount + kVerbs); 1003 } 1004 1005 void SkPath::addPoly(const SkPoint pts[], int count, bool close) { 1006 SkDEBUGCODE(this->validate();) 1007 if (count <= 0) { 1008 return; 1009 } 1010 1011 fLastMoveToIndex = fPathRef->countPoints(); 1012 1013 // +close makes room for the extra kClose_Verb 1014 SkPathRef::Editor ed(&fPathRef, count+close, count); 1015 1016 ed.growForVerb(kMove_Verb)->set(pts[0].fX, pts[0].fY); 1017 if (count > 1) { 1018 SkPoint* p = ed.growForRepeatedVerb(kLine_Verb, count - 1); 1019 memcpy(p, &pts[1], (count-1) * sizeof(SkPoint)); 1020 } 1021 1022 if (close) { 1023 ed.growForVerb(kClose_Verb); 1024 fLastMoveToIndex ^= ~fLastMoveToIndex >> (8 * sizeof(fLastMoveToIndex) - 1); 1025 } 1026 1027 DIRTY_AFTER_EDIT; 1028 SkDEBUGCODE(this->validate();) 1029 } 1030 1031 #include "SkGeometry.h" 1032 1033 static bool arc_is_lone_point(const SkRect& oval, SkScalar startAngle, SkScalar sweepAngle, 1034 SkPoint* pt) { 1035 if (0 == sweepAngle && (0 == startAngle || SkIntToScalar(360) == startAngle)) { 1036 // Chrome uses this path to move into and out of ovals. If not 1037 // treated as a special case the moves can distort the oval's 1038 // bounding box (and break the circle special case). 1039 pt->set(oval.fRight, oval.centerY()); 1040 return true; 1041 } else if (0 == oval.width() && 0 == oval.height()) { 1042 // Chrome will sometimes create 0 radius round rects. Having degenerate 1043 // quad segments in the path prevents the path from being recognized as 1044 // a rect. 1045 // TODO: optimizing the case where only one of width or height is zero 1046 // should also be considered. This case, however, doesn't seem to be 1047 // as common as the single point case. 1048 pt->set(oval.fRight, oval.fTop); 1049 return true; 1050 } 1051 return false; 1052 } 1053 1054 // Return the unit vectors pointing at the start/stop points for the given start/sweep angles 1055 // 1056 static void angles_to_unit_vectors(SkScalar startAngle, SkScalar sweepAngle, 1057 SkVector* startV, SkVector* stopV, SkRotationDirection* dir) { 1058 startV->fY = SkScalarSinCos(SkDegreesToRadians(startAngle), &startV->fX); 1059 stopV->fY = SkScalarSinCos(SkDegreesToRadians(startAngle + sweepAngle), &stopV->fX); 1060 1061 /* If the sweep angle is nearly (but less than) 360, then due to precision 1062 loss in radians-conversion and/or sin/cos, we may end up with coincident 1063 vectors, which will fool SkBuildQuadArc into doing nothing (bad) instead 1064 of drawing a nearly complete circle (good). 1065 e.g. canvas.drawArc(0, 359.99, ...) 1066 -vs- canvas.drawArc(0, 359.9, ...) 1067 We try to detect this edge case, and tweak the stop vector 1068 */ 1069 if (*startV == *stopV) { 1070 SkScalar sw = SkScalarAbs(sweepAngle); 1071 if (sw < SkIntToScalar(360) && sw > SkIntToScalar(359)) { 1072 SkScalar stopRad = SkDegreesToRadians(startAngle + sweepAngle); 1073 // make a guess at a tiny angle (in radians) to tweak by 1074 SkScalar deltaRad = SkScalarCopySign(SK_Scalar1/512, sweepAngle); 1075 // not sure how much will be enough, so we use a loop 1076 do { 1077 stopRad -= deltaRad; 1078 stopV->fY = SkScalarSinCos(stopRad, &stopV->fX); 1079 } while (*startV == *stopV); 1080 } 1081 } 1082 *dir = sweepAngle > 0 ? kCW_SkRotationDirection : kCCW_SkRotationDirection; 1083 } 1084 1085 /** 1086 * If this returns 0, then the caller should just line-to the singlePt, else it should 1087 * ignore singlePt and append the specified number of conics. 1088 */ 1089 static int build_arc_conics(const SkRect& oval, const SkVector& start, const SkVector& stop, 1090 SkRotationDirection dir, SkConic conics[SkConic::kMaxConicsForArc], 1091 SkPoint* singlePt) { 1092 SkMatrix matrix; 1093 1094 matrix.setScale(SkScalarHalf(oval.width()), SkScalarHalf(oval.height())); 1095 matrix.postTranslate(oval.centerX(), oval.centerY()); 1096 1097 int count = SkConic::BuildUnitArc(start, stop, dir, &matrix, conics); 1098 if (0 == count) { 1099 matrix.mapXY(stop.x(), stop.y(), singlePt); 1100 } 1101 return count; 1102 } 1103 1104 void SkPath::addRoundRect(const SkRect& rect, const SkScalar radii[], 1105 Direction dir) { 1106 SkRRect rrect; 1107 rrect.setRectRadii(rect, (const SkVector*) radii); 1108 this->addRRect(rrect, dir); 1109 } 1110 1111 void SkPath::addRRect(const SkRRect& rrect, Direction dir) { 1112 // legacy start indices: 6 (CW) and 7(CCW) 1113 this->addRRect(rrect, dir, dir == kCW_Direction ? 6 : 7); 1114 } 1115 1116 void SkPath::addRRect(const SkRRect &rrect, Direction dir, unsigned startIndex) { 1117 assert_known_direction(dir); 1118 1119 if (rrect.isEmpty()) { 1120 return; 1121 } 1122 1123 bool isRRect = hasOnlyMoveTos(); 1124 const SkRect& bounds = rrect.getBounds(); 1125 1126 if (rrect.isRect()) { 1127 // degenerate(rect) => radii points are collapsing 1128 this->addRect(bounds, dir, (startIndex + 1) / 2); 1129 } else if (rrect.isOval()) { 1130 // degenerate(oval) => line points are collapsing 1131 this->addOval(bounds, dir, startIndex / 2); 1132 } else { 1133 fFirstDirection = this->hasOnlyMoveTos() ? 1134 (SkPathPriv::FirstDirection)dir : SkPathPriv::kUnknown_FirstDirection; 1135 1136 SkAutoPathBoundsUpdate apbu(this, bounds); 1137 SkAutoDisableDirectionCheck addc(this); 1138 1139 // we start with a conic on odd indices when moving CW vs. even indices when moving CCW 1140 const bool startsWithConic = ((startIndex & 1) == (dir == kCW_Direction)); 1141 const SkScalar weight = SK_ScalarRoot2Over2; 1142 1143 SkDEBUGCODE(int initialVerbCount = this->countVerbs()); 1144 const int kVerbs = startsWithConic 1145 ? 9 // moveTo + 4x conicTo + 3x lineTo + close 1146 : 10; // moveTo + 4x lineTo + 4x conicTo + close 1147 this->incReserve(kVerbs); 1148 1149 RRectPointIterator rrectIter(rrect, dir, startIndex); 1150 // Corner iterator indices follow the collapsed radii model, 1151 // adjusted such that the start pt is "behind" the radii start pt. 1152 const unsigned rectStartIndex = startIndex / 2 + (dir == kCW_Direction ? 0 : 1); 1153 RectPointIterator rectIter(bounds, dir, rectStartIndex); 1154 1155 this->moveTo(rrectIter.current()); 1156 if (startsWithConic) { 1157 for (unsigned i = 0; i < 3; ++i) { 1158 this->conicTo(rectIter.next(), rrectIter.next(), weight); 1159 this->lineTo(rrectIter.next()); 1160 } 1161 this->conicTo(rectIter.next(), rrectIter.next(), weight); 1162 // final lineTo handled by close(). 1163 } else { 1164 for (unsigned i = 0; i < 4; ++i) { 1165 this->lineTo(rrectIter.next()); 1166 this->conicTo(rectIter.next(), rrectIter.next(), weight); 1167 } 1168 } 1169 this->close(); 1170 1171 SkPathRef::Editor ed(&fPathRef); 1172 ed.setIsRRect(isRRect, dir, startIndex % 8); 1173 1174 SkASSERT(this->countVerbs() == initialVerbCount + kVerbs); 1175 } 1176 1177 SkDEBUGCODE(fPathRef->validate();) 1178 } 1179 1180 bool SkPath::hasOnlyMoveTos() const { 1181 int count = fPathRef->countVerbs(); 1182 const uint8_t* verbs = const_cast<const SkPathRef*>(fPathRef.get())->verbsMemBegin(); 1183 for (int i = 0; i < count; ++i) { 1184 if (*verbs == kLine_Verb || 1185 *verbs == kQuad_Verb || 1186 *verbs == kConic_Verb || 1187 *verbs == kCubic_Verb) { 1188 return false; 1189 } 1190 ++verbs; 1191 } 1192 return true; 1193 } 1194 1195 bool SkPath::isZeroLengthSincePoint(int startPtIndex) const { 1196 int count = fPathRef->countPoints() - startPtIndex; 1197 if (count < 2) { 1198 return true; 1199 } 1200 const SkPoint* pts = fPathRef.get()->points() + startPtIndex; 1201 const SkPoint& first = *pts; 1202 for (int index = 1; index < count; ++index) { 1203 if (first != pts[index]) { 1204 return false; 1205 } 1206 } 1207 return true; 1208 } 1209 1210 void SkPath::addRoundRect(const SkRect& rect, SkScalar rx, SkScalar ry, 1211 Direction dir) { 1212 assert_known_direction(dir); 1213 1214 if (rx < 0 || ry < 0) { 1215 return; 1216 } 1217 1218 SkRRect rrect; 1219 rrect.setRectXY(rect, rx, ry); 1220 this->addRRect(rrect, dir); 1221 } 1222 1223 void SkPath::addOval(const SkRect& oval, Direction dir) { 1224 // legacy start index: 1 1225 this->addOval(oval, dir, 1); 1226 } 1227 1228 void SkPath::addOval(const SkRect &oval, Direction dir, unsigned startPointIndex) { 1229 assert_known_direction(dir); 1230 1231 /* If addOval() is called after previous moveTo(), 1232 this path is still marked as an oval. This is used to 1233 fit into WebKit's calling sequences. 1234 We can't simply check isEmpty() in this case, as additional 1235 moveTo() would mark the path non empty. 1236 */ 1237 bool isOval = hasOnlyMoveTos(); 1238 if (isOval) { 1239 fFirstDirection = (SkPathPriv::FirstDirection)dir; 1240 } else { 1241 fFirstDirection = SkPathPriv::kUnknown_FirstDirection; 1242 } 1243 1244 SkAutoDisableDirectionCheck addc(this); 1245 SkAutoPathBoundsUpdate apbu(this, oval); 1246 1247 SkDEBUGCODE(int initialVerbCount = this->countVerbs()); 1248 const int kVerbs = 6; // moveTo + 4x conicTo + close 1249 this->incReserve(kVerbs); 1250 1251 OvalPointIterator ovalIter(oval, dir, startPointIndex); 1252 // The corner iterator pts are tracking "behind" the oval/radii pts. 1253 RectPointIterator rectIter(oval, dir, startPointIndex + (dir == kCW_Direction ? 0 : 1)); 1254 const SkScalar weight = SK_ScalarRoot2Over2; 1255 1256 this->moveTo(ovalIter.current()); 1257 for (unsigned i = 0; i < 4; ++i) { 1258 this->conicTo(rectIter.next(), ovalIter.next(), weight); 1259 } 1260 this->close(); 1261 1262 SkASSERT(this->countVerbs() == initialVerbCount + kVerbs); 1263 1264 SkPathRef::Editor ed(&fPathRef); 1265 1266 ed.setIsOval(isOval, kCCW_Direction == dir, startPointIndex % 4); 1267 } 1268 1269 void SkPath::addCircle(SkScalar x, SkScalar y, SkScalar r, Direction dir) { 1270 if (r > 0) { 1271 this->addOval(SkRect::MakeLTRB(x - r, y - r, x + r, y + r), dir); 1272 } 1273 } 1274 1275 void SkPath::arcTo(const SkRect& oval, SkScalar startAngle, SkScalar sweepAngle, 1276 bool forceMoveTo) { 1277 if (oval.width() < 0 || oval.height() < 0) { 1278 return; 1279 } 1280 1281 if (fPathRef->countVerbs() == 0) { 1282 forceMoveTo = true; 1283 } 1284 1285 SkPoint lonePt; 1286 if (arc_is_lone_point(oval, startAngle, sweepAngle, &lonePt)) { 1287 forceMoveTo ? this->moveTo(lonePt) : this->lineTo(lonePt); 1288 return; 1289 } 1290 1291 SkVector startV, stopV; 1292 SkRotationDirection dir; 1293 angles_to_unit_vectors(startAngle, sweepAngle, &startV, &stopV, &dir); 1294 1295 SkPoint singlePt; 1296 1297 // At this point, we know that the arc is not a lone point, but startV == stopV 1298 // indicates that the sweepAngle is too small such that angles_to_unit_vectors 1299 // cannot handle it. 1300 if (startV == stopV) { 1301 SkScalar endAngle = SkDegreesToRadians(startAngle + sweepAngle); 1302 SkScalar radiusX = oval.width() / 2; 1303 SkScalar radiusY = oval.height() / 2; 1304 // We cannot use SkScalarSinCos function in the next line because 1305 // SkScalarSinCos has a threshold *SkScalarNearlyZero*. When sin(startAngle) 1306 // is 0 and sweepAngle is very small and radius is huge, the expected 1307 // behavior here is to draw a line. But calling SkScalarSinCos will 1308 // make sin(endAngle) to be 0 which will then draw a dot. 1309 singlePt.set(oval.centerX() + radiusX * sk_float_cos(endAngle), 1310 oval.centerY() + radiusY * sk_float_sin(endAngle)); 1311 forceMoveTo ? this->moveTo(singlePt) : this->lineTo(singlePt); 1312 return; 1313 } 1314 1315 SkConic conics[SkConic::kMaxConicsForArc]; 1316 int count = build_arc_conics(oval, startV, stopV, dir, conics, &singlePt); 1317 if (count) { 1318 this->incReserve(count * 2 + 1); 1319 const SkPoint& pt = conics[0].fPts[0]; 1320 forceMoveTo ? this->moveTo(pt) : this->lineTo(pt); 1321 for (int i = 0; i < count; ++i) { 1322 this->conicTo(conics[i].fPts[1], conics[i].fPts[2], conics[i].fW); 1323 } 1324 } else { 1325 forceMoveTo ? this->moveTo(singlePt) : this->lineTo(singlePt); 1326 } 1327 } 1328 1329 // This converts the SVG arc to conics. 1330 // Partly adapted from Niko's code in kdelibs/kdecore/svgicons. 1331 // Then transcribed from webkit/chrome's SVGPathNormalizer::decomposeArcToCubic() 1332 // See also SVG implementation notes: 1333 // http://www.w3.org/TR/SVG/implnote.html#ArcConversionEndpointToCenter 1334 // Note that arcSweep bool value is flipped from the original implementation. 1335 void SkPath::arcTo(SkScalar rx, SkScalar ry, SkScalar angle, SkPath::ArcSize arcLarge, 1336 SkPath::Direction arcSweep, SkScalar x, SkScalar y) { 1337 this->injectMoveToIfNeeded(); 1338 SkPoint srcPts[2]; 1339 this->getLastPt(&srcPts[0]); 1340 // If rx = 0 or ry = 0 then this arc is treated as a straight line segment (a "lineto") 1341 // joining the endpoints. 1342 // http://www.w3.org/TR/SVG/implnote.html#ArcOutOfRangeParameters 1343 if (!rx || !ry) { 1344 this->lineTo(x, y); 1345 return; 1346 } 1347 // If the current point and target point for the arc are identical, it should be treated as a 1348 // zero length path. This ensures continuity in animations. 1349 srcPts[1].set(x, y); 1350 if (srcPts[0] == srcPts[1]) { 1351 this->lineTo(x, y); 1352 return; 1353 } 1354 rx = SkScalarAbs(rx); 1355 ry = SkScalarAbs(ry); 1356 SkVector midPointDistance = srcPts[0] - srcPts[1]; 1357 midPointDistance *= 0.5f; 1358 1359 SkMatrix pointTransform; 1360 pointTransform.setRotate(-angle); 1361 1362 SkPoint transformedMidPoint; 1363 pointTransform.mapPoints(&transformedMidPoint, &midPointDistance, 1); 1364 SkScalar squareRx = rx * rx; 1365 SkScalar squareRy = ry * ry; 1366 SkScalar squareX = transformedMidPoint.fX * transformedMidPoint.fX; 1367 SkScalar squareY = transformedMidPoint.fY * transformedMidPoint.fY; 1368 1369 // Check if the radii are big enough to draw the arc, scale radii if not. 1370 // http://www.w3.org/TR/SVG/implnote.html#ArcCorrectionOutOfRangeRadii 1371 SkScalar radiiScale = squareX / squareRx + squareY / squareRy; 1372 if (radiiScale > 1) { 1373 radiiScale = SkScalarSqrt(radiiScale); 1374 rx *= radiiScale; 1375 ry *= radiiScale; 1376 } 1377 1378 pointTransform.setScale(1 / rx, 1 / ry); 1379 pointTransform.preRotate(-angle); 1380 1381 SkPoint unitPts[2]; 1382 pointTransform.mapPoints(unitPts, srcPts, (int) SK_ARRAY_COUNT(unitPts)); 1383 SkVector delta = unitPts[1] - unitPts[0]; 1384 1385 SkScalar d = delta.fX * delta.fX + delta.fY * delta.fY; 1386 SkScalar scaleFactorSquared = SkTMax(1 / d - 0.25f, 0.f); 1387 1388 SkScalar scaleFactor = SkScalarSqrt(scaleFactorSquared); 1389 if (SkToBool(arcSweep) != SkToBool(arcLarge)) { // flipped from the original implementation 1390 scaleFactor = -scaleFactor; 1391 } 1392 delta.scale(scaleFactor); 1393 SkPoint centerPoint = unitPts[0] + unitPts[1]; 1394 centerPoint *= 0.5f; 1395 centerPoint.offset(-delta.fY, delta.fX); 1396 unitPts[0] -= centerPoint; 1397 unitPts[1] -= centerPoint; 1398 SkScalar theta1 = SkScalarATan2(unitPts[0].fY, unitPts[0].fX); 1399 SkScalar theta2 = SkScalarATan2(unitPts[1].fY, unitPts[1].fX); 1400 SkScalar thetaArc = theta2 - theta1; 1401 if (thetaArc < 0 && !arcSweep) { // arcSweep flipped from the original implementation 1402 thetaArc += SK_ScalarPI * 2; 1403 } else if (thetaArc > 0 && arcSweep) { // arcSweep flipped from the original implementation 1404 thetaArc -= SK_ScalarPI * 2; 1405 } 1406 pointTransform.setRotate(angle); 1407 pointTransform.preScale(rx, ry); 1408 1409 int segments = SkScalarCeilToInt(SkScalarAbs(thetaArc / (SK_ScalarPI / 2))); 1410 SkScalar thetaWidth = thetaArc / segments; 1411 SkScalar t = SkScalarTan(0.5f * thetaWidth); 1412 if (!SkScalarIsFinite(t)) { 1413 return; 1414 } 1415 SkScalar startTheta = theta1; 1416 SkScalar w = SkScalarSqrt(SK_ScalarHalf + SkScalarCos(thetaWidth) * SK_ScalarHalf); 1417 for (int i = 0; i < segments; ++i) { 1418 SkScalar endTheta = startTheta + thetaWidth; 1419 SkScalar cosEndTheta, sinEndTheta = SkScalarSinCos(endTheta, &cosEndTheta); 1420 1421 unitPts[1].set(cosEndTheta, sinEndTheta); 1422 unitPts[1] += centerPoint; 1423 unitPts[0] = unitPts[1]; 1424 unitPts[0].offset(t * sinEndTheta, -t * cosEndTheta); 1425 SkPoint mapped[2]; 1426 pointTransform.mapPoints(mapped, unitPts, (int) SK_ARRAY_COUNT(unitPts)); 1427 this->conicTo(mapped[0], mapped[1], w); 1428 startTheta = endTheta; 1429 } 1430 } 1431 1432 void SkPath::rArcTo(SkScalar rx, SkScalar ry, SkScalar xAxisRotate, SkPath::ArcSize largeArc, 1433 SkPath::Direction sweep, SkScalar dx, SkScalar dy) { 1434 SkPoint currentPoint; 1435 this->getLastPt(¤tPoint); 1436 this->arcTo(rx, ry, xAxisRotate, largeArc, sweep, currentPoint.fX + dx, currentPoint.fY + dy); 1437 } 1438 1439 void SkPath::addArc(const SkRect& oval, SkScalar startAngle, SkScalar sweepAngle) { 1440 if (oval.isEmpty() || 0 == sweepAngle) { 1441 return; 1442 } 1443 1444 const SkScalar kFullCircleAngle = SkIntToScalar(360); 1445 1446 if (sweepAngle >= kFullCircleAngle || sweepAngle <= -kFullCircleAngle) { 1447 // We can treat the arc as an oval if it begins at one of our legal starting positions. 1448 // See SkPath::addOval() docs. 1449 SkScalar startOver90 = startAngle / 90.f; 1450 SkScalar startOver90I = SkScalarRoundToScalar(startOver90); 1451 SkScalar error = startOver90 - startOver90I; 1452 if (SkScalarNearlyEqual(error, 0)) { 1453 // Index 1 is at startAngle == 0. 1454 SkScalar startIndex = std::fmod(startOver90I + 1.f, 4.f); 1455 startIndex = startIndex < 0 ? startIndex + 4.f : startIndex; 1456 this->addOval(oval, sweepAngle > 0 ? kCW_Direction : kCCW_Direction, 1457 (unsigned) startIndex); 1458 return; 1459 } 1460 } 1461 this->arcTo(oval, startAngle, sweepAngle, true); 1462 } 1463 1464 /* 1465 Need to handle the case when the angle is sharp, and our computed end-points 1466 for the arc go behind pt1 and/or p2... 1467 */ 1468 void SkPath::arcTo(SkScalar x1, SkScalar y1, SkScalar x2, SkScalar y2, SkScalar radius) { 1469 if (radius == 0) { 1470 this->lineTo(x1, y1); 1471 return; 1472 } 1473 1474 SkVector before, after; 1475 1476 // need to know our prev pt so we can construct tangent vectors 1477 { 1478 SkPoint start; 1479 this->getLastPt(&start); 1480 // Handle degenerate cases by adding a line to the first point and 1481 // bailing out. 1482 before.setNormalize(x1 - start.fX, y1 - start.fY); 1483 after.setNormalize(x2 - x1, y2 - y1); 1484 } 1485 1486 SkScalar cosh = SkPoint::DotProduct(before, after); 1487 SkScalar sinh = SkPoint::CrossProduct(before, after); 1488 1489 if (SkScalarNearlyZero(sinh)) { // angle is too tight 1490 this->lineTo(x1, y1); 1491 return; 1492 } 1493 1494 SkScalar dist = SkScalarAbs(radius * (1 - cosh) / sinh); 1495 1496 SkScalar xx = x1 - dist * before.fX; 1497 SkScalar yy = y1 - dist * before.fY; 1498 after.setLength(dist); 1499 this->lineTo(xx, yy); 1500 SkScalar weight = SkScalarSqrt(SK_ScalarHalf + cosh * SK_ScalarHalf); 1501 this->conicTo(x1, y1, x1 + after.fX, y1 + after.fY, weight); 1502 } 1503 1504 /////////////////////////////////////////////////////////////////////////////// 1505 1506 void SkPath::addPath(const SkPath& path, SkScalar dx, SkScalar dy, AddPathMode mode) { 1507 SkMatrix matrix; 1508 1509 matrix.setTranslate(dx, dy); 1510 this->addPath(path, matrix, mode); 1511 } 1512 1513 void SkPath::addPath(const SkPath& path, const SkMatrix& matrix, AddPathMode mode) { 1514 SkPathRef::Editor(&fPathRef, path.countVerbs(), path.countPoints()); 1515 1516 RawIter iter(path); 1517 SkPoint pts[4]; 1518 Verb verb; 1519 1520 SkMatrix::MapPtsProc proc = matrix.getMapPtsProc(); 1521 bool firstVerb = true; 1522 while ((verb = iter.next(pts)) != kDone_Verb) { 1523 switch (verb) { 1524 case kMove_Verb: 1525 proc(matrix, &pts[0], &pts[0], 1); 1526 if (firstVerb && mode == kExtend_AddPathMode && !isEmpty()) { 1527 injectMoveToIfNeeded(); // In case last contour is closed 1528 this->lineTo(pts[0]); 1529 } else { 1530 this->moveTo(pts[0]); 1531 } 1532 break; 1533 case kLine_Verb: 1534 proc(matrix, &pts[1], &pts[1], 1); 1535 this->lineTo(pts[1]); 1536 break; 1537 case kQuad_Verb: 1538 proc(matrix, &pts[1], &pts[1], 2); 1539 this->quadTo(pts[1], pts[2]); 1540 break; 1541 case kConic_Verb: 1542 proc(matrix, &pts[1], &pts[1], 2); 1543 this->conicTo(pts[1], pts[2], iter.conicWeight()); 1544 break; 1545 case kCubic_Verb: 1546 proc(matrix, &pts[1], &pts[1], 3); 1547 this->cubicTo(pts[1], pts[2], pts[3]); 1548 break; 1549 case kClose_Verb: 1550 this->close(); 1551 break; 1552 default: 1553 SkDEBUGFAIL("unknown verb"); 1554 } 1555 firstVerb = false; 1556 } 1557 } 1558 1559 /////////////////////////////////////////////////////////////////////////////// 1560 1561 static int pts_in_verb(unsigned verb) { 1562 static const uint8_t gPtsInVerb[] = { 1563 1, // kMove 1564 1, // kLine 1565 2, // kQuad 1566 2, // kConic 1567 3, // kCubic 1568 0, // kClose 1569 0 // kDone 1570 }; 1571 1572 SkASSERT(verb < SK_ARRAY_COUNT(gPtsInVerb)); 1573 return gPtsInVerb[verb]; 1574 } 1575 1576 // ignore the last point of the 1st contour 1577 void SkPath::reversePathTo(const SkPath& path) { 1578 const uint8_t* verbs = path.fPathRef->verbsMemBegin(); // points at the last verb 1579 if (!verbs) { // empty path returns nullptr 1580 return; 1581 } 1582 const uint8_t* verbsEnd = path.fPathRef->verbs() - 1; // points just past the first verb 1583 SkASSERT(verbsEnd[0] == kMove_Verb); 1584 const SkPoint* pts = path.fPathRef->pointsEnd() - 1; 1585 const SkScalar* conicWeights = path.fPathRef->conicWeightsEnd(); 1586 1587 while (verbs < verbsEnd) { 1588 uint8_t v = *verbs++; 1589 pts -= pts_in_verb(v); 1590 switch (v) { 1591 case kMove_Verb: 1592 // if the path has multiple contours, stop after reversing the last 1593 return; 1594 case kLine_Verb: 1595 this->lineTo(pts[0]); 1596 break; 1597 case kQuad_Verb: 1598 this->quadTo(pts[1], pts[0]); 1599 break; 1600 case kConic_Verb: 1601 this->conicTo(pts[1], pts[0], *--conicWeights); 1602 break; 1603 case kCubic_Verb: 1604 this->cubicTo(pts[2], pts[1], pts[0]); 1605 break; 1606 case kClose_Verb: 1607 SkASSERT(verbs - path.fPathRef->verbsMemBegin() == 1); 1608 break; 1609 default: 1610 SkDEBUGFAIL("bad verb"); 1611 break; 1612 } 1613 } 1614 } 1615 1616 void SkPath::reverseAddPath(const SkPath& src) { 1617 SkPathRef::Editor ed(&fPathRef, src.fPathRef->countPoints(), src.fPathRef->countVerbs()); 1618 1619 const SkPoint* pts = src.fPathRef->pointsEnd(); 1620 // we will iterator through src's verbs backwards 1621 const uint8_t* verbs = src.fPathRef->verbsMemBegin(); // points at the last verb 1622 const uint8_t* verbsEnd = src.fPathRef->verbs(); // points just past the first verb 1623 const SkScalar* conicWeights = src.fPathRef->conicWeightsEnd(); 1624 1625 bool needMove = true; 1626 bool needClose = false; 1627 while (verbs < verbsEnd) { 1628 uint8_t v = *(verbs++); 1629 int n = pts_in_verb(v); 1630 1631 if (needMove) { 1632 --pts; 1633 this->moveTo(pts->fX, pts->fY); 1634 needMove = false; 1635 } 1636 pts -= n; 1637 switch (v) { 1638 case kMove_Verb: 1639 if (needClose) { 1640 this->close(); 1641 needClose = false; 1642 } 1643 needMove = true; 1644 pts += 1; // so we see the point in "if (needMove)" above 1645 break; 1646 case kLine_Verb: 1647 this->lineTo(pts[0]); 1648 break; 1649 case kQuad_Verb: 1650 this->quadTo(pts[1], pts[0]); 1651 break; 1652 case kConic_Verb: 1653 this->conicTo(pts[1], pts[0], *--conicWeights); 1654 break; 1655 case kCubic_Verb: 1656 this->cubicTo(pts[2], pts[1], pts[0]); 1657 break; 1658 case kClose_Verb: 1659 needClose = true; 1660 break; 1661 default: 1662 SkDEBUGFAIL("unexpected verb"); 1663 } 1664 } 1665 } 1666 1667 /////////////////////////////////////////////////////////////////////////////// 1668 1669 void SkPath::offset(SkScalar dx, SkScalar dy, SkPath* dst) const { 1670 SkMatrix matrix; 1671 1672 matrix.setTranslate(dx, dy); 1673 this->transform(matrix, dst); 1674 } 1675 1676 static void subdivide_cubic_to(SkPath* path, const SkPoint pts[4], 1677 int level = 2) { 1678 if (--level >= 0) { 1679 SkPoint tmp[7]; 1680 1681 SkChopCubicAtHalf(pts, tmp); 1682 subdivide_cubic_to(path, &tmp[0], level); 1683 subdivide_cubic_to(path, &tmp[3], level); 1684 } else { 1685 path->cubicTo(pts[1], pts[2], pts[3]); 1686 } 1687 } 1688 1689 void SkPath::transform(const SkMatrix& matrix, SkPath* dst) const { 1690 SkDEBUGCODE(this->validate();) 1691 if (dst == nullptr) { 1692 dst = (SkPath*)this; 1693 } 1694 1695 if (matrix.hasPerspective()) { 1696 SkPath tmp; 1697 tmp.fFillType = fFillType; 1698 1699 SkPath::Iter iter(*this, false); 1700 SkPoint pts[4]; 1701 SkPath::Verb verb; 1702 1703 while ((verb = iter.next(pts, false)) != kDone_Verb) { 1704 switch (verb) { 1705 case kMove_Verb: 1706 tmp.moveTo(pts[0]); 1707 break; 1708 case kLine_Verb: 1709 tmp.lineTo(pts[1]); 1710 break; 1711 case kQuad_Verb: 1712 // promote the quad to a conic 1713 tmp.conicTo(pts[1], pts[2], 1714 SkConic::TransformW(pts, SK_Scalar1, matrix)); 1715 break; 1716 case kConic_Verb: 1717 tmp.conicTo(pts[1], pts[2], 1718 SkConic::TransformW(pts, iter.conicWeight(), matrix)); 1719 break; 1720 case kCubic_Verb: 1721 subdivide_cubic_to(&tmp, pts); 1722 break; 1723 case kClose_Verb: 1724 tmp.close(); 1725 break; 1726 default: 1727 SkDEBUGFAIL("unknown verb"); 1728 break; 1729 } 1730 } 1731 1732 dst->swap(tmp); 1733 SkPathRef::Editor ed(&dst->fPathRef); 1734 matrix.mapPoints(ed.points(), ed.pathRef()->countPoints()); 1735 dst->fFirstDirection = SkPathPriv::kUnknown_FirstDirection; 1736 } else { 1737 SkPathRef::CreateTransformedCopy(&dst->fPathRef, *fPathRef.get(), matrix); 1738 1739 if (this != dst) { 1740 dst->fFillType = fFillType; 1741 dst->fConvexity = fConvexity; 1742 dst->fIsVolatile = fIsVolatile; 1743 } 1744 1745 if (SkPathPriv::kUnknown_FirstDirection == fFirstDirection) { 1746 dst->fFirstDirection = SkPathPriv::kUnknown_FirstDirection; 1747 } else { 1748 SkScalar det2x2 = 1749 matrix.get(SkMatrix::kMScaleX) * matrix.get(SkMatrix::kMScaleY) - 1750 matrix.get(SkMatrix::kMSkewX) * matrix.get(SkMatrix::kMSkewY); 1751 if (det2x2 < 0) { 1752 dst->fFirstDirection = SkPathPriv::OppositeFirstDirection( 1753 (SkPathPriv::FirstDirection)fFirstDirection.load()); 1754 } else if (det2x2 > 0) { 1755 dst->fFirstDirection = fFirstDirection.load(); 1756 } else { 1757 dst->fConvexity = kUnknown_Convexity; 1758 dst->fFirstDirection = SkPathPriv::kUnknown_FirstDirection; 1759 } 1760 } 1761 1762 SkDEBUGCODE(dst->validate();) 1763 } 1764 } 1765 1766 /////////////////////////////////////////////////////////////////////////////// 1767 /////////////////////////////////////////////////////////////////////////////// 1768 1769 enum SegmentState { 1770 kEmptyContour_SegmentState, // The current contour is empty. We may be 1771 // starting processing or we may have just 1772 // closed a contour. 1773 kAfterMove_SegmentState, // We have seen a move, but nothing else. 1774 kAfterPrimitive_SegmentState // We have seen a primitive but not yet 1775 // closed the path. Also the initial state. 1776 }; 1777 1778 SkPath::Iter::Iter() { 1779 #ifdef SK_DEBUG 1780 fPts = nullptr; 1781 fConicWeights = nullptr; 1782 fMoveTo.fX = fMoveTo.fY = fLastPt.fX = fLastPt.fY = 0; 1783 fForceClose = fCloseLine = false; 1784 fSegmentState = kEmptyContour_SegmentState; 1785 #endif 1786 // need to init enough to make next() harmlessly return kDone_Verb 1787 fVerbs = nullptr; 1788 fVerbStop = nullptr; 1789 fNeedClose = false; 1790 } 1791 1792 SkPath::Iter::Iter(const SkPath& path, bool forceClose) { 1793 this->setPath(path, forceClose); 1794 } 1795 1796 void SkPath::Iter::setPath(const SkPath& path, bool forceClose) { 1797 fPts = path.fPathRef->points(); 1798 fVerbs = path.fPathRef->verbs(); 1799 fVerbStop = path.fPathRef->verbsMemBegin(); 1800 fConicWeights = path.fPathRef->conicWeights(); 1801 if (fConicWeights) { 1802 fConicWeights -= 1; // begin one behind 1803 } 1804 fLastPt.fX = fLastPt.fY = 0; 1805 fMoveTo.fX = fMoveTo.fY = 0; 1806 fForceClose = SkToU8(forceClose); 1807 fNeedClose = false; 1808 fSegmentState = kEmptyContour_SegmentState; 1809 } 1810 1811 bool SkPath::Iter::isClosedContour() const { 1812 if (fVerbs == nullptr || fVerbs == fVerbStop) { 1813 return false; 1814 } 1815 if (fForceClose) { 1816 return true; 1817 } 1818 1819 const uint8_t* verbs = fVerbs; 1820 const uint8_t* stop = fVerbStop; 1821 1822 if (kMove_Verb == *(verbs - 1)) { 1823 verbs -= 1; // skip the initial moveto 1824 } 1825 1826 while (verbs > stop) { 1827 // verbs points one beyond the current verb, decrement first. 1828 unsigned v = *(--verbs); 1829 if (kMove_Verb == v) { 1830 break; 1831 } 1832 if (kClose_Verb == v) { 1833 return true; 1834 } 1835 } 1836 return false; 1837 } 1838 1839 SkPath::Verb SkPath::Iter::autoClose(SkPoint pts[2]) { 1840 SkASSERT(pts); 1841 if (fLastPt != fMoveTo) { 1842 // A special case: if both points are NaN, SkPoint::operation== returns 1843 // false, but the iterator expects that they are treated as the same. 1844 // (consider SkPoint is a 2-dimension float point). 1845 if (SkScalarIsNaN(fLastPt.fX) || SkScalarIsNaN(fLastPt.fY) || 1846 SkScalarIsNaN(fMoveTo.fX) || SkScalarIsNaN(fMoveTo.fY)) { 1847 return kClose_Verb; 1848 } 1849 1850 pts[0] = fLastPt; 1851 pts[1] = fMoveTo; 1852 fLastPt = fMoveTo; 1853 fCloseLine = true; 1854 return kLine_Verb; 1855 } else { 1856 pts[0] = fMoveTo; 1857 return kClose_Verb; 1858 } 1859 } 1860 1861 const SkPoint& SkPath::Iter::cons_moveTo() { 1862 if (fSegmentState == kAfterMove_SegmentState) { 1863 // Set the first return pt to the move pt 1864 fSegmentState = kAfterPrimitive_SegmentState; 1865 return fMoveTo; 1866 } else { 1867 SkASSERT(fSegmentState == kAfterPrimitive_SegmentState); 1868 // Set the first return pt to the last pt of the previous primitive. 1869 return fPts[-1]; 1870 } 1871 } 1872 1873 void SkPath::Iter::consumeDegenerateSegments(bool exact) { 1874 // We need to step over anything that will not move the current draw point 1875 // forward before the next move is seen 1876 const uint8_t* lastMoveVerb = 0; 1877 const SkPoint* lastMovePt = 0; 1878 const SkScalar* lastMoveWeight = nullptr; 1879 SkPoint lastPt = fLastPt; 1880 while (fVerbs != fVerbStop) { 1881 unsigned verb = *(fVerbs - 1); // fVerbs is one beyond the current verb 1882 switch (verb) { 1883 case kMove_Verb: 1884 // Keep a record of this most recent move 1885 lastMoveVerb = fVerbs; 1886 lastMovePt = fPts; 1887 lastMoveWeight = fConicWeights; 1888 lastPt = fPts[0]; 1889 fVerbs--; 1890 fPts++; 1891 break; 1892 1893 case kClose_Verb: 1894 // A close when we are in a segment is always valid except when it 1895 // follows a move which follows a segment. 1896 if (fSegmentState == kAfterPrimitive_SegmentState && !lastMoveVerb) { 1897 return; 1898 } 1899 // A close at any other time must be ignored 1900 fVerbs--; 1901 break; 1902 1903 case kLine_Verb: 1904 if (!IsLineDegenerate(lastPt, fPts[0], exact)) { 1905 if (lastMoveVerb) { 1906 fVerbs = lastMoveVerb; 1907 fPts = lastMovePt; 1908 fConicWeights = lastMoveWeight; 1909 return; 1910 } 1911 return; 1912 } 1913 // Ignore this line and continue 1914 fVerbs--; 1915 fPts++; 1916 break; 1917 1918 case kConic_Verb: 1919 case kQuad_Verb: 1920 if (!IsQuadDegenerate(lastPt, fPts[0], fPts[1], exact)) { 1921 if (lastMoveVerb) { 1922 fVerbs = lastMoveVerb; 1923 fPts = lastMovePt; 1924 fConicWeights = lastMoveWeight; 1925 return; 1926 } 1927 return; 1928 } 1929 // Ignore this line and continue 1930 fVerbs--; 1931 fPts += 2; 1932 fConicWeights += (kConic_Verb == verb); 1933 break; 1934 1935 case kCubic_Verb: 1936 if (!IsCubicDegenerate(lastPt, fPts[0], fPts[1], fPts[2], exact)) { 1937 if (lastMoveVerb) { 1938 fVerbs = lastMoveVerb; 1939 fPts = lastMovePt; 1940 fConicWeights = lastMoveWeight; 1941 return; 1942 } 1943 return; 1944 } 1945 // Ignore this line and continue 1946 fVerbs--; 1947 fPts += 3; 1948 break; 1949 1950 default: 1951 SkDEBUGFAIL("Should never see kDone_Verb"); 1952 } 1953 } 1954 } 1955 1956 SkPath::Verb SkPath::Iter::doNext(SkPoint ptsParam[4]) { 1957 SkASSERT(ptsParam); 1958 1959 if (fVerbs == fVerbStop) { 1960 // Close the curve if requested and if there is some curve to close 1961 if (fNeedClose && fSegmentState == kAfterPrimitive_SegmentState) { 1962 if (kLine_Verb == this->autoClose(ptsParam)) { 1963 return kLine_Verb; 1964 } 1965 fNeedClose = false; 1966 return kClose_Verb; 1967 } 1968 return kDone_Verb; 1969 } 1970 1971 // fVerbs is one beyond the current verb, decrement first 1972 unsigned verb = *(--fVerbs); 1973 const SkPoint* SK_RESTRICT srcPts = fPts; 1974 SkPoint* SK_RESTRICT pts = ptsParam; 1975 1976 switch (verb) { 1977 case kMove_Verb: 1978 if (fNeedClose) { 1979 fVerbs++; // move back one verb 1980 verb = this->autoClose(pts); 1981 if (verb == kClose_Verb) { 1982 fNeedClose = false; 1983 } 1984 return (Verb)verb; 1985 } 1986 if (fVerbs == fVerbStop) { // might be a trailing moveto 1987 return kDone_Verb; 1988 } 1989 fMoveTo = *srcPts; 1990 pts[0] = *srcPts; 1991 srcPts += 1; 1992 fSegmentState = kAfterMove_SegmentState; 1993 fLastPt = fMoveTo; 1994 fNeedClose = fForceClose; 1995 break; 1996 case kLine_Verb: 1997 pts[0] = this->cons_moveTo(); 1998 pts[1] = srcPts[0]; 1999 fLastPt = srcPts[0]; 2000 fCloseLine = false; 2001 srcPts += 1; 2002 break; 2003 case kConic_Verb: 2004 fConicWeights += 1; 2005 // fall-through 2006 case kQuad_Verb: 2007 pts[0] = this->cons_moveTo(); 2008 memcpy(&pts[1], srcPts, 2 * sizeof(SkPoint)); 2009 fLastPt = srcPts[1]; 2010 srcPts += 2; 2011 break; 2012 case kCubic_Verb: 2013 pts[0] = this->cons_moveTo(); 2014 memcpy(&pts[1], srcPts, 3 * sizeof(SkPoint)); 2015 fLastPt = srcPts[2]; 2016 srcPts += 3; 2017 break; 2018 case kClose_Verb: 2019 verb = this->autoClose(pts); 2020 if (verb == kLine_Verb) { 2021 fVerbs++; // move back one verb 2022 } else { 2023 fNeedClose = false; 2024 fSegmentState = kEmptyContour_SegmentState; 2025 } 2026 fLastPt = fMoveTo; 2027 break; 2028 } 2029 fPts = srcPts; 2030 return (Verb)verb; 2031 } 2032 2033 /////////////////////////////////////////////////////////////////////////////// 2034 2035 /* 2036 Format in compressed buffer: [ptCount, verbCount, pts[], verbs[]] 2037 */ 2038 2039 size_t SkPath::writeToMemory(void* storage) const { 2040 SkDEBUGCODE(this->validate();) 2041 2042 if (nullptr == storage) { 2043 const int byteCount = sizeof(int32_t) * 2 + fPathRef->writeSize(); 2044 return SkAlign4(byteCount); 2045 } 2046 2047 SkWBuffer buffer(storage); 2048 2049 int32_t packed = (fConvexity << kConvexity_SerializationShift) | 2050 (fFillType << kFillType_SerializationShift) | 2051 (fFirstDirection << kDirection_SerializationShift) | 2052 (fIsVolatile << kIsVolatile_SerializationShift) | 2053 kCurrent_Version; 2054 2055 buffer.write32(packed); 2056 buffer.write32(fLastMoveToIndex); 2057 2058 fPathRef->writeToBuffer(&buffer); 2059 2060 buffer.padToAlign4(); 2061 return buffer.pos(); 2062 } 2063 2064 size_t SkPath::readFromMemory(const void* storage, size_t length) { 2065 SkRBuffer buffer(storage, length); 2066 2067 int32_t packed; 2068 if (!buffer.readS32(&packed)) { 2069 return 0; 2070 } 2071 2072 unsigned version = packed & 0xFF; 2073 if (version >= kPathPrivLastMoveToIndex_Version && !buffer.readS32(&fLastMoveToIndex)) { 2074 return 0; 2075 } 2076 2077 fConvexity = (packed >> kConvexity_SerializationShift) & 0xFF; 2078 fFillType = (packed >> kFillType_SerializationShift) & 0x3; 2079 uint8_t dir = (packed >> kDirection_SerializationShift) & 0x3; 2080 fIsVolatile = (packed >> kIsVolatile_SerializationShift) & 0x1; 2081 SkPathRef* pathRef = SkPathRef::CreateFromBuffer(&buffer); 2082 if (!pathRef) { 2083 return 0; 2084 } 2085 2086 fPathRef.reset(pathRef); 2087 SkDEBUGCODE(this->validate();) 2088 buffer.skipToAlign4(); 2089 2090 // compatibility check 2091 if (version < kPathPrivFirstDirection_Version) { 2092 switch (dir) { // old values 2093 case 0: 2094 fFirstDirection = SkPathPriv::kUnknown_FirstDirection; 2095 break; 2096 case 1: 2097 fFirstDirection = SkPathPriv::kCW_FirstDirection; 2098 break; 2099 case 2: 2100 fFirstDirection = SkPathPriv::kCCW_FirstDirection; 2101 break; 2102 default: 2103 SkASSERT(false); 2104 } 2105 } else { 2106 fFirstDirection = dir; 2107 } 2108 2109 return buffer.pos(); 2110 } 2111 2112 /////////////////////////////////////////////////////////////////////////////// 2113 2114 #include "SkString.h" 2115 #include "SkStringUtils.h" 2116 #include "SkStream.h" 2117 2118 static void append_params(SkString* str, const char label[], const SkPoint pts[], 2119 int count, SkScalarAsStringType strType, SkScalar conicWeight = -1) { 2120 str->append(label); 2121 str->append("("); 2122 2123 const SkScalar* values = &pts[0].fX; 2124 count *= 2; 2125 2126 for (int i = 0; i < count; ++i) { 2127 SkAppendScalar(str, values[i], strType); 2128 if (i < count - 1) { 2129 str->append(", "); 2130 } 2131 } 2132 if (conicWeight >= 0) { 2133 str->append(", "); 2134 SkAppendScalar(str, conicWeight, strType); 2135 } 2136 str->append(");"); 2137 if (kHex_SkScalarAsStringType == strType) { 2138 str->append(" // "); 2139 for (int i = 0; i < count; ++i) { 2140 SkAppendScalarDec(str, values[i]); 2141 if (i < count - 1) { 2142 str->append(", "); 2143 } 2144 } 2145 if (conicWeight >= 0) { 2146 str->append(", "); 2147 SkAppendScalarDec(str, conicWeight); 2148 } 2149 } 2150 str->append("\n"); 2151 } 2152 2153 void SkPath::dump(SkWStream* wStream, bool forceClose, bool dumpAsHex) const { 2154 SkScalarAsStringType asType = dumpAsHex ? kHex_SkScalarAsStringType : kDec_SkScalarAsStringType; 2155 Iter iter(*this, forceClose); 2156 SkPoint pts[4]; 2157 Verb verb; 2158 2159 SkString builder; 2160 char const * const gFillTypeStrs[] = { 2161 "Winding", 2162 "EvenOdd", 2163 "InverseWinding", 2164 "InverseEvenOdd", 2165 }; 2166 builder.printf("path.setFillType(SkPath::k%s_FillType);\n", 2167 gFillTypeStrs[(int) this->getFillType()]); 2168 while ((verb = iter.next(pts, false)) != kDone_Verb) { 2169 switch (verb) { 2170 case kMove_Verb: 2171 append_params(&builder, "path.moveTo", &pts[0], 1, asType); 2172 break; 2173 case kLine_Verb: 2174 append_params(&builder, "path.lineTo", &pts[1], 1, asType); 2175 break; 2176 case kQuad_Verb: 2177 append_params(&builder, "path.quadTo", &pts[1], 2, asType); 2178 break; 2179 case kConic_Verb: 2180 append_params(&builder, "path.conicTo", &pts[1], 2, asType, iter.conicWeight()); 2181 break; 2182 case kCubic_Verb: 2183 append_params(&builder, "path.cubicTo", &pts[1], 3, asType); 2184 break; 2185 case kClose_Verb: 2186 builder.append("path.close();\n"); 2187 break; 2188 default: 2189 SkDebugf(" path: UNKNOWN VERB %d, aborting dump...\n", verb); 2190 verb = kDone_Verb; // stop the loop 2191 break; 2192 } 2193 if (!wStream && builder.size()) { 2194 SkDebugf("%s", builder.c_str()); 2195 builder.reset(); 2196 } 2197 } 2198 if (wStream) { 2199 wStream->writeText(builder.c_str()); 2200 } 2201 } 2202 2203 void SkPath::dump() const { 2204 this->dump(nullptr, false, false); 2205 } 2206 2207 void SkPath::dumpHex() const { 2208 this->dump(nullptr, false, true); 2209 } 2210 2211 #ifdef SK_DEBUG 2212 void SkPath::validate() const { 2213 SkASSERT((fFillType & ~3) == 0); 2214 2215 #ifdef SK_DEBUG_PATH 2216 if (!fBoundsIsDirty) { 2217 SkRect bounds; 2218 2219 bool isFinite = compute_pt_bounds(&bounds, *fPathRef.get()); 2220 SkASSERT(SkToBool(fIsFinite) == isFinite); 2221 2222 if (fPathRef->countPoints() <= 1) { 2223 // if we're empty, fBounds may be empty but translated, so we can't 2224 // necessarily compare to bounds directly 2225 // try path.addOval(2, 2, 2, 2) which is empty, but the bounds will 2226 // be [2, 2, 2, 2] 2227 SkASSERT(bounds.isEmpty()); 2228 SkASSERT(fBounds.isEmpty()); 2229 } else { 2230 if (bounds.isEmpty()) { 2231 SkASSERT(fBounds.isEmpty()); 2232 } else { 2233 if (!fBounds.isEmpty()) { 2234 SkASSERT(fBounds.contains(bounds)); 2235 } 2236 } 2237 } 2238 } 2239 #endif // SK_DEBUG_PATH 2240 } 2241 #endif // SK_DEBUG 2242 2243 /////////////////////////////////////////////////////////////////////////////// 2244 2245 static int sign(SkScalar x) { return x < 0; } 2246 #define kValueNeverReturnedBySign 2 2247 2248 enum DirChange { 2249 kLeft_DirChange, 2250 kRight_DirChange, 2251 kStraight_DirChange, 2252 kBackwards_DirChange, 2253 2254 kInvalid_DirChange 2255 }; 2256 2257 2258 static bool almost_equal(SkScalar compA, SkScalar compB) { 2259 // The error epsilon was empirically derived; worse case round rects 2260 // with a mid point outset by 2x float epsilon in tests had an error 2261 // of 12. 2262 const int epsilon = 16; 2263 if (!SkScalarIsFinite(compA) || !SkScalarIsFinite(compB)) { 2264 return false; 2265 } 2266 // no need to check for small numbers because SkPath::Iter has removed degenerate values 2267 int aBits = SkFloatAs2sCompliment(compA); 2268 int bBits = SkFloatAs2sCompliment(compB); 2269 return aBits < bBits + epsilon && bBits < aBits + epsilon; 2270 } 2271 2272 static bool approximately_zero_when_compared_to(double x, double y) { 2273 return x == 0 || fabs(x) < fabs(y * FLT_EPSILON); 2274 } 2275 2276 2277 // only valid for a single contour 2278 struct Convexicator { 2279 Convexicator() 2280 : fPtCount(0) 2281 , fConvexity(SkPath::kConvex_Convexity) 2282 , fFirstDirection(SkPathPriv::kUnknown_FirstDirection) 2283 , fIsFinite(true) 2284 , fIsCurve(false) { 2285 fExpectedDir = kInvalid_DirChange; 2286 // warnings 2287 fPriorPt.set(0,0); 2288 fLastPt.set(0, 0); 2289 fCurrPt.set(0, 0); 2290 fLastVec.set(0, 0); 2291 fFirstVec.set(0, 0); 2292 2293 fDx = fDy = 0; 2294 fSx = fSy = kValueNeverReturnedBySign; 2295 } 2296 2297 SkPath::Convexity getConvexity() const { return fConvexity; } 2298 2299 /** The direction returned is only valid if the path is determined convex */ 2300 SkPathPriv::FirstDirection getFirstDirection() const { return fFirstDirection; } 2301 2302 void addPt(const SkPoint& pt) { 2303 if (SkPath::kConcave_Convexity == fConvexity || !fIsFinite) { 2304 return; 2305 } 2306 2307 if (0 == fPtCount) { 2308 fCurrPt = pt; 2309 ++fPtCount; 2310 } else { 2311 SkVector vec = pt - fCurrPt; 2312 SkScalar lengthSqd = vec.lengthSqd(); 2313 if (!SkScalarIsFinite(lengthSqd)) { 2314 fIsFinite = false; 2315 } else if (lengthSqd) { 2316 fPriorPt = fLastPt; 2317 fLastPt = fCurrPt; 2318 fCurrPt = pt; 2319 if (++fPtCount == 2) { 2320 fFirstVec = fLastVec = vec; 2321 } else { 2322 SkASSERT(fPtCount > 2); 2323 this->addVec(vec); 2324 } 2325 2326 int sx = sign(vec.fX); 2327 int sy = sign(vec.fY); 2328 fDx += (sx != fSx); 2329 fDy += (sy != fSy); 2330 fSx = sx; 2331 fSy = sy; 2332 2333 if (fDx > 3 || fDy > 3) { 2334 fConvexity = SkPath::kConcave_Convexity; 2335 } 2336 } 2337 } 2338 } 2339 2340 void close() { 2341 if (fPtCount > 2) { 2342 this->addVec(fFirstVec); 2343 } 2344 } 2345 2346 DirChange directionChange(const SkVector& curVec) { 2347 SkScalar cross = SkPoint::CrossProduct(fLastVec, curVec); 2348 2349 SkScalar smallest = SkTMin(fCurrPt.fX, SkTMin(fCurrPt.fY, SkTMin(fLastPt.fX, fLastPt.fY))); 2350 SkScalar largest = SkTMax(fCurrPt.fX, SkTMax(fCurrPt.fY, SkTMax(fLastPt.fX, fLastPt.fY))); 2351 largest = SkTMax(largest, -smallest); 2352 2353 if (!almost_equal(largest, largest + cross)) { 2354 int sign = SkScalarSignAsInt(cross); 2355 if (sign) { 2356 return (1 == sign) ? kRight_DirChange : kLeft_DirChange; 2357 } 2358 } 2359 2360 if (cross) { 2361 double dLastVecX = SkScalarToDouble(fLastPt.fX) - SkScalarToDouble(fPriorPt.fX); 2362 double dLastVecY = SkScalarToDouble(fLastPt.fY) - SkScalarToDouble(fPriorPt.fY); 2363 double dCurrVecX = SkScalarToDouble(fCurrPt.fX) - SkScalarToDouble(fLastPt.fX); 2364 double dCurrVecY = SkScalarToDouble(fCurrPt.fY) - SkScalarToDouble(fLastPt.fY); 2365 double dCross = dLastVecX * dCurrVecY - dLastVecY * dCurrVecX; 2366 if (!approximately_zero_when_compared_to(dCross, SkScalarToDouble(largest))) { 2367 int sign = SkScalarSignAsInt(SkDoubleToScalar(dCross)); 2368 if (sign) { 2369 return (1 == sign) ? kRight_DirChange : kLeft_DirChange; 2370 } 2371 } 2372 } 2373 2374 if (!SkScalarNearlyZero(fLastVec.lengthSqd(), SK_ScalarNearlyZero*SK_ScalarNearlyZero) && 2375 !SkScalarNearlyZero(curVec.lengthSqd(), SK_ScalarNearlyZero*SK_ScalarNearlyZero) && 2376 fLastVec.dot(curVec) < 0.0f) { 2377 return kBackwards_DirChange; 2378 } 2379 2380 return kStraight_DirChange; 2381 } 2382 2383 2384 bool isFinite() const { 2385 return fIsFinite; 2386 } 2387 2388 void setCurve(bool isCurve) { 2389 fIsCurve = isCurve; 2390 } 2391 2392 private: 2393 void addVec(const SkVector& vec) { 2394 SkASSERT(vec.fX || vec.fY); 2395 DirChange dir = this->directionChange(vec); 2396 switch (dir) { 2397 case kLeft_DirChange: // fall through 2398 case kRight_DirChange: 2399 if (kInvalid_DirChange == fExpectedDir) { 2400 fExpectedDir = dir; 2401 fFirstDirection = (kRight_DirChange == dir) ? SkPathPriv::kCW_FirstDirection 2402 : SkPathPriv::kCCW_FirstDirection; 2403 } else if (dir != fExpectedDir) { 2404 fConvexity = SkPath::kConcave_Convexity; 2405 fFirstDirection = SkPathPriv::kUnknown_FirstDirection; 2406 } 2407 fLastVec = vec; 2408 break; 2409 case kStraight_DirChange: 2410 break; 2411 case kBackwards_DirChange: 2412 if (fIsCurve) { 2413 // If any of the subsequent dir is non-backward, it'll be concave. 2414 // Otherwise, it's still convex. 2415 fExpectedDir = dir; 2416 } 2417 fLastVec = vec; 2418 break; 2419 case kInvalid_DirChange: 2420 SkFAIL("Use of invalid direction change flag"); 2421 break; 2422 } 2423 } 2424 2425 SkPoint fPriorPt; 2426 SkPoint fLastPt; 2427 SkPoint fCurrPt; 2428 // fLastVec does not necessarily start at fLastPt. We only advance it when the cross product 2429 // value with the current vec is deemed to be of a significant value. 2430 SkVector fLastVec, fFirstVec; 2431 int fPtCount; // non-degenerate points 2432 DirChange fExpectedDir; 2433 SkPath::Convexity fConvexity; 2434 SkPathPriv::FirstDirection fFirstDirection; 2435 int fDx, fDy, fSx, fSy; 2436 bool fIsFinite; 2437 bool fIsCurve; 2438 }; 2439 2440 SkPath::Convexity SkPath::internalGetConvexity() const { 2441 SkASSERT(kUnknown_Convexity == fConvexity); 2442 SkPoint pts[4]; 2443 SkPath::Verb verb; 2444 SkPath::Iter iter(*this, true); 2445 2446 int contourCount = 0; 2447 int count; 2448 Convexicator state; 2449 2450 if (!isFinite()) { 2451 return kUnknown_Convexity; 2452 } 2453 while ((verb = iter.next(pts, true, true)) != SkPath::kDone_Verb) { 2454 switch (verb) { 2455 case kMove_Verb: 2456 if (++contourCount > 1) { 2457 fConvexity = kConcave_Convexity; 2458 return kConcave_Convexity; 2459 } 2460 pts[1] = pts[0]; 2461 // fall through 2462 case kLine_Verb: 2463 count = 1; 2464 state.setCurve(false); 2465 break; 2466 case kQuad_Verb: 2467 // fall through 2468 case kConic_Verb: 2469 // fall through 2470 case kCubic_Verb: 2471 count = 2 + (kCubic_Verb == verb); 2472 // As an additional enhancement, this could set curve true only 2473 // if the curve is nonlinear 2474 state.setCurve(true); 2475 break; 2476 case kClose_Verb: 2477 state.setCurve(false); 2478 state.close(); 2479 count = 0; 2480 break; 2481 default: 2482 SkDEBUGFAIL("bad verb"); 2483 fConvexity = kConcave_Convexity; 2484 return kConcave_Convexity; 2485 } 2486 2487 for (int i = 1; i <= count; i++) { 2488 state.addPt(pts[i]); 2489 } 2490 // early exit 2491 if (!state.isFinite()) { 2492 return kUnknown_Convexity; 2493 } 2494 if (kConcave_Convexity == state.getConvexity()) { 2495 fConvexity = kConcave_Convexity; 2496 return kConcave_Convexity; 2497 } 2498 } 2499 fConvexity = state.getConvexity(); 2500 if (kConvex_Convexity == fConvexity && SkPathPriv::kUnknown_FirstDirection == fFirstDirection) { 2501 fFirstDirection = state.getFirstDirection(); 2502 } 2503 return static_cast<Convexity>(fConvexity); 2504 } 2505 2506 /////////////////////////////////////////////////////////////////////////////// 2507 2508 class ContourIter { 2509 public: 2510 ContourIter(const SkPathRef& pathRef); 2511 2512 bool done() const { return fDone; } 2513 // if !done() then these may be called 2514 int count() const { return fCurrPtCount; } 2515 const SkPoint* pts() const { return fCurrPt; } 2516 void next(); 2517 2518 private: 2519 int fCurrPtCount; 2520 const SkPoint* fCurrPt; 2521 const uint8_t* fCurrVerb; 2522 const uint8_t* fStopVerbs; 2523 const SkScalar* fCurrConicWeight; 2524 bool fDone; 2525 SkDEBUGCODE(int fContourCounter;) 2526 }; 2527 2528 ContourIter::ContourIter(const SkPathRef& pathRef) { 2529 fStopVerbs = pathRef.verbsMemBegin(); 2530 fDone = false; 2531 fCurrPt = pathRef.points(); 2532 fCurrVerb = pathRef.verbs(); 2533 fCurrConicWeight = pathRef.conicWeights(); 2534 fCurrPtCount = 0; 2535 SkDEBUGCODE(fContourCounter = 0;) 2536 this->next(); 2537 } 2538 2539 void ContourIter::next() { 2540 if (fCurrVerb <= fStopVerbs) { 2541 fDone = true; 2542 } 2543 if (fDone) { 2544 return; 2545 } 2546 2547 // skip pts of prev contour 2548 fCurrPt += fCurrPtCount; 2549 2550 SkASSERT(SkPath::kMove_Verb == fCurrVerb[~0]); 2551 int ptCount = 1; // moveTo 2552 const uint8_t* verbs = fCurrVerb; 2553 2554 for (--verbs; verbs > fStopVerbs; --verbs) { 2555 switch (verbs[~0]) { 2556 case SkPath::kMove_Verb: 2557 goto CONTOUR_END; 2558 case SkPath::kLine_Verb: 2559 ptCount += 1; 2560 break; 2561 case SkPath::kConic_Verb: 2562 fCurrConicWeight += 1; 2563 // fall-through 2564 case SkPath::kQuad_Verb: 2565 ptCount += 2; 2566 break; 2567 case SkPath::kCubic_Verb: 2568 ptCount += 3; 2569 break; 2570 case SkPath::kClose_Verb: 2571 break; 2572 default: 2573 SkDEBUGFAIL("unexpected verb"); 2574 break; 2575 } 2576 } 2577 CONTOUR_END: 2578 fCurrPtCount = ptCount; 2579 fCurrVerb = verbs; 2580 SkDEBUGCODE(++fContourCounter;) 2581 } 2582 2583 // returns cross product of (p1 - p0) and (p2 - p0) 2584 static SkScalar cross_prod(const SkPoint& p0, const SkPoint& p1, const SkPoint& p2) { 2585 SkScalar cross = SkPoint::CrossProduct(p1 - p0, p2 - p0); 2586 // We may get 0 when the above subtracts underflow. We expect this to be 2587 // very rare and lazily promote to double. 2588 if (0 == cross) { 2589 double p0x = SkScalarToDouble(p0.fX); 2590 double p0y = SkScalarToDouble(p0.fY); 2591 2592 double p1x = SkScalarToDouble(p1.fX); 2593 double p1y = SkScalarToDouble(p1.fY); 2594 2595 double p2x = SkScalarToDouble(p2.fX); 2596 double p2y = SkScalarToDouble(p2.fY); 2597 2598 cross = SkDoubleToScalar((p1x - p0x) * (p2y - p0y) - 2599 (p1y - p0y) * (p2x - p0x)); 2600 2601 } 2602 return cross; 2603 } 2604 2605 // Returns the first pt with the maximum Y coordinate 2606 static int find_max_y(const SkPoint pts[], int count) { 2607 SkASSERT(count > 0); 2608 SkScalar max = pts[0].fY; 2609 int firstIndex = 0; 2610 for (int i = 1; i < count; ++i) { 2611 SkScalar y = pts[i].fY; 2612 if (y > max) { 2613 max = y; 2614 firstIndex = i; 2615 } 2616 } 2617 return firstIndex; 2618 } 2619 2620 static int find_diff_pt(const SkPoint pts[], int index, int n, int inc) { 2621 int i = index; 2622 for (;;) { 2623 i = (i + inc) % n; 2624 if (i == index) { // we wrapped around, so abort 2625 break; 2626 } 2627 if (pts[index] != pts[i]) { // found a different point, success! 2628 break; 2629 } 2630 } 2631 return i; 2632 } 2633 2634 /** 2635 * Starting at index, and moving forward (incrementing), find the xmin and 2636 * xmax of the contiguous points that have the same Y. 2637 */ 2638 static int find_min_max_x_at_y(const SkPoint pts[], int index, int n, 2639 int* maxIndexPtr) { 2640 const SkScalar y = pts[index].fY; 2641 SkScalar min = pts[index].fX; 2642 SkScalar max = min; 2643 int minIndex = index; 2644 int maxIndex = index; 2645 for (int i = index + 1; i < n; ++i) { 2646 if (pts[i].fY != y) { 2647 break; 2648 } 2649 SkScalar x = pts[i].fX; 2650 if (x < min) { 2651 min = x; 2652 minIndex = i; 2653 } else if (x > max) { 2654 max = x; 2655 maxIndex = i; 2656 } 2657 } 2658 *maxIndexPtr = maxIndex; 2659 return minIndex; 2660 } 2661 2662 static void crossToDir(SkScalar cross, SkPathPriv::FirstDirection* dir) { 2663 *dir = cross > 0 ? SkPathPriv::kCW_FirstDirection : SkPathPriv::kCCW_FirstDirection; 2664 } 2665 2666 /* 2667 * We loop through all contours, and keep the computed cross-product of the 2668 * contour that contained the global y-max. If we just look at the first 2669 * contour, we may find one that is wound the opposite way (correctly) since 2670 * it is the interior of a hole (e.g. 'o'). Thus we must find the contour 2671 * that is outer most (or at least has the global y-max) before we can consider 2672 * its cross product. 2673 */ 2674 bool SkPathPriv::CheapComputeFirstDirection(const SkPath& path, FirstDirection* dir) { 2675 if (kUnknown_FirstDirection != path.fFirstDirection.load()) { 2676 *dir = static_cast<FirstDirection>(path.fFirstDirection.load()); 2677 return true; 2678 } 2679 2680 // don't want to pay the cost for computing this if it 2681 // is unknown, so we don't call isConvex() 2682 if (SkPath::kConvex_Convexity == path.getConvexityOrUnknown()) { 2683 SkASSERT(kUnknown_FirstDirection == path.fFirstDirection); 2684 *dir = static_cast<FirstDirection>(path.fFirstDirection.load()); 2685 return false; 2686 } 2687 2688 ContourIter iter(*path.fPathRef.get()); 2689 2690 // initialize with our logical y-min 2691 SkScalar ymax = path.getBounds().fTop; 2692 SkScalar ymaxCross = 0; 2693 2694 for (; !iter.done(); iter.next()) { 2695 int n = iter.count(); 2696 if (n < 3) { 2697 continue; 2698 } 2699 2700 const SkPoint* pts = iter.pts(); 2701 SkScalar cross = 0; 2702 int index = find_max_y(pts, n); 2703 if (pts[index].fY < ymax) { 2704 continue; 2705 } 2706 2707 // If there is more than 1 distinct point at the y-max, we take the 2708 // x-min and x-max of them and just subtract to compute the dir. 2709 if (pts[(index + 1) % n].fY == pts[index].fY) { 2710 int maxIndex; 2711 int minIndex = find_min_max_x_at_y(pts, index, n, &maxIndex); 2712 if (minIndex == maxIndex) { 2713 goto TRY_CROSSPROD; 2714 } 2715 SkASSERT(pts[minIndex].fY == pts[index].fY); 2716 SkASSERT(pts[maxIndex].fY == pts[index].fY); 2717 SkASSERT(pts[minIndex].fX <= pts[maxIndex].fX); 2718 // we just subtract the indices, and let that auto-convert to 2719 // SkScalar, since we just want - or + to signal the direction. 2720 cross = minIndex - maxIndex; 2721 } else { 2722 TRY_CROSSPROD: 2723 // Find a next and prev index to use for the cross-product test, 2724 // but we try to find pts that form non-zero vectors from pts[index] 2725 // 2726 // Its possible that we can't find two non-degenerate vectors, so 2727 // we have to guard our search (e.g. all the pts could be in the 2728 // same place). 2729 2730 // we pass n - 1 instead of -1 so we don't foul up % operator by 2731 // passing it a negative LH argument. 2732 int prev = find_diff_pt(pts, index, n, n - 1); 2733 if (prev == index) { 2734 // completely degenerate, skip to next contour 2735 continue; 2736 } 2737 int next = find_diff_pt(pts, index, n, 1); 2738 SkASSERT(next != index); 2739 cross = cross_prod(pts[prev], pts[index], pts[next]); 2740 // if we get a zero and the points are horizontal, then we look at the spread in 2741 // x-direction. We really should continue to walk away from the degeneracy until 2742 // there is a divergence. 2743 if (0 == cross && pts[prev].fY == pts[index].fY && pts[next].fY == pts[index].fY) { 2744 // construct the subtract so we get the correct Direction below 2745 cross = pts[index].fX - pts[next].fX; 2746 } 2747 } 2748 2749 if (cross) { 2750 // record our best guess so far 2751 ymax = pts[index].fY; 2752 ymaxCross = cross; 2753 } 2754 } 2755 if (ymaxCross) { 2756 crossToDir(ymaxCross, dir); 2757 path.fFirstDirection = *dir; 2758 return true; 2759 } else { 2760 return false; 2761 } 2762 } 2763 2764 /////////////////////////////////////////////////////////////////////////////// 2765 2766 static bool between(SkScalar a, SkScalar b, SkScalar c) { 2767 SkASSERT(((a <= b && b <= c) || (a >= b && b >= c)) == ((a - b) * (c - b) <= 0) 2768 || (SkScalarNearlyZero(a) && SkScalarNearlyZero(b) && SkScalarNearlyZero(c))); 2769 return (a - b) * (c - b) <= 0; 2770 } 2771 2772 static SkScalar eval_cubic_pts(SkScalar c0, SkScalar c1, SkScalar c2, SkScalar c3, 2773 SkScalar t) { 2774 SkScalar A = c3 + 3*(c1 - c2) - c0; 2775 SkScalar B = 3*(c2 - c1 - c1 + c0); 2776 SkScalar C = 3*(c1 - c0); 2777 SkScalar D = c0; 2778 return poly_eval(A, B, C, D, t); 2779 } 2780 2781 template <size_t N> static void find_minmax(const SkPoint pts[], 2782 SkScalar* minPtr, SkScalar* maxPtr) { 2783 SkScalar min, max; 2784 min = max = pts[0].fX; 2785 for (size_t i = 1; i < N; ++i) { 2786 min = SkMinScalar(min, pts[i].fX); 2787 max = SkMaxScalar(max, pts[i].fX); 2788 } 2789 *minPtr = min; 2790 *maxPtr = max; 2791 } 2792 2793 static bool checkOnCurve(SkScalar x, SkScalar y, const SkPoint& start, const SkPoint& end) { 2794 if (start.fY == end.fY) { 2795 return between(start.fX, x, end.fX) && x != end.fX; 2796 } else { 2797 return x == start.fX && y == start.fY; 2798 } 2799 } 2800 2801 static int winding_mono_cubic(const SkPoint pts[], SkScalar x, SkScalar y, int* onCurveCount) { 2802 SkScalar y0 = pts[0].fY; 2803 SkScalar y3 = pts[3].fY; 2804 2805 int dir = 1; 2806 if (y0 > y3) { 2807 SkTSwap(y0, y3); 2808 dir = -1; 2809 } 2810 if (y < y0 || y > y3) { 2811 return 0; 2812 } 2813 if (checkOnCurve(x, y, pts[0], pts[3])) { 2814 *onCurveCount += 1; 2815 return 0; 2816 } 2817 if (y == y3) { 2818 return 0; 2819 } 2820 2821 // quickreject or quickaccept 2822 SkScalar min, max; 2823 find_minmax<4>(pts, &min, &max); 2824 if (x < min) { 2825 return 0; 2826 } 2827 if (x > max) { 2828 return dir; 2829 } 2830 2831 // compute the actual x(t) value 2832 SkScalar t; 2833 if (!SkCubicClipper::ChopMonoAtY(pts, y, &t)) { 2834 return 0; 2835 } 2836 SkScalar xt = eval_cubic_pts(pts[0].fX, pts[1].fX, pts[2].fX, pts[3].fX, t); 2837 if (SkScalarNearlyEqual(xt, x)) { 2838 if (x != pts[3].fX || y != pts[3].fY) { // don't test end points; they're start points 2839 *onCurveCount += 1; 2840 return 0; 2841 } 2842 } 2843 return xt < x ? dir : 0; 2844 } 2845 2846 static int winding_cubic(const SkPoint pts[], SkScalar x, SkScalar y, int* onCurveCount) { 2847 SkPoint dst[10]; 2848 int n = SkChopCubicAtYExtrema(pts, dst); 2849 int w = 0; 2850 for (int i = 0; i <= n; ++i) { 2851 w += winding_mono_cubic(&dst[i * 3], x, y, onCurveCount); 2852 } 2853 return w; 2854 } 2855 2856 static double conic_eval_numerator(const SkScalar src[], SkScalar w, SkScalar t) { 2857 SkASSERT(src); 2858 SkASSERT(t >= 0 && t <= 1); 2859 SkScalar src2w = src[2] * w; 2860 SkScalar C = src[0]; 2861 SkScalar A = src[4] - 2 * src2w + C; 2862 SkScalar B = 2 * (src2w - C); 2863 return poly_eval(A, B, C, t); 2864 } 2865 2866 2867 static double conic_eval_denominator(SkScalar w, SkScalar t) { 2868 SkScalar B = 2 * (w - 1); 2869 SkScalar C = 1; 2870 SkScalar A = -B; 2871 return poly_eval(A, B, C, t); 2872 } 2873 2874 static int winding_mono_conic(const SkConic& conic, SkScalar x, SkScalar y, int* onCurveCount) { 2875 const SkPoint* pts = conic.fPts; 2876 SkScalar y0 = pts[0].fY; 2877 SkScalar y2 = pts[2].fY; 2878 2879 int dir = 1; 2880 if (y0 > y2) { 2881 SkTSwap(y0, y2); 2882 dir = -1; 2883 } 2884 if (y < y0 || y > y2) { 2885 return 0; 2886 } 2887 if (checkOnCurve(x, y, pts[0], pts[2])) { 2888 *onCurveCount += 1; 2889 return 0; 2890 } 2891 if (y == y2) { 2892 return 0; 2893 } 2894 2895 SkScalar roots[2]; 2896 SkScalar A = pts[2].fY; 2897 SkScalar B = pts[1].fY * conic.fW - y * conic.fW + y; 2898 SkScalar C = pts[0].fY; 2899 A += C - 2 * B; // A = a + c - 2*(b*w - yCept*w + yCept) 2900 B -= C; // B = b*w - w * yCept + yCept - a 2901 C -= y; 2902 int n = SkFindUnitQuadRoots(A, 2 * B, C, roots); 2903 SkASSERT(n <= 1); 2904 SkScalar xt; 2905 if (0 == n) { 2906 // zero roots are returned only when y0 == y 2907 // Need [0] if dir == 1 2908 // and [2] if dir == -1 2909 xt = pts[1 - dir].fX; 2910 } else { 2911 SkScalar t = roots[0]; 2912 xt = conic_eval_numerator(&pts[0].fX, conic.fW, t) / conic_eval_denominator(conic.fW, t); 2913 } 2914 if (SkScalarNearlyEqual(xt, x)) { 2915 if (x != pts[2].fX || y != pts[2].fY) { // don't test end points; they're start points 2916 *onCurveCount += 1; 2917 return 0; 2918 } 2919 } 2920 return xt < x ? dir : 0; 2921 } 2922 2923 static bool is_mono_quad(SkScalar y0, SkScalar y1, SkScalar y2) { 2924 // return SkScalarSignAsInt(y0 - y1) + SkScalarSignAsInt(y1 - y2) != 0; 2925 if (y0 == y1) { 2926 return true; 2927 } 2928 if (y0 < y1) { 2929 return y1 <= y2; 2930 } else { 2931 return y1 >= y2; 2932 } 2933 } 2934 2935 static int winding_conic(const SkPoint pts[], SkScalar x, SkScalar y, SkScalar weight, 2936 int* onCurveCount) { 2937 SkConic conic(pts, weight); 2938 SkConic chopped[2]; 2939 // If the data points are very large, the conic may not be monotonic but may also 2940 // fail to chop. Then, the chopper does not split the original conic in two. 2941 bool isMono = is_mono_quad(pts[0].fY, pts[1].fY, pts[2].fY) || !conic.chopAtYExtrema(chopped); 2942 int w = winding_mono_conic(isMono ? conic : chopped[0], x, y, onCurveCount); 2943 if (!isMono) { 2944 w += winding_mono_conic(chopped[1], x, y, onCurveCount); 2945 } 2946 return w; 2947 } 2948 2949 static int winding_mono_quad(const SkPoint pts[], SkScalar x, SkScalar y, int* onCurveCount) { 2950 SkScalar y0 = pts[0].fY; 2951 SkScalar y2 = pts[2].fY; 2952 2953 int dir = 1; 2954 if (y0 > y2) { 2955 SkTSwap(y0, y2); 2956 dir = -1; 2957 } 2958 if (y < y0 || y > y2) { 2959 return 0; 2960 } 2961 if (checkOnCurve(x, y, pts[0], pts[2])) { 2962 *onCurveCount += 1; 2963 return 0; 2964 } 2965 if (y == y2) { 2966 return 0; 2967 } 2968 // bounds check on X (not required. is it faster?) 2969 #if 0 2970 if (pts[0].fX > x && pts[1].fX > x && pts[2].fX > x) { 2971 return 0; 2972 } 2973 #endif 2974 2975 SkScalar roots[2]; 2976 int n = SkFindUnitQuadRoots(pts[0].fY - 2 * pts[1].fY + pts[2].fY, 2977 2 * (pts[1].fY - pts[0].fY), 2978 pts[0].fY - y, 2979 roots); 2980 SkASSERT(n <= 1); 2981 SkScalar xt; 2982 if (0 == n) { 2983 // zero roots are returned only when y0 == y 2984 // Need [0] if dir == 1 2985 // and [2] if dir == -1 2986 xt = pts[1 - dir].fX; 2987 } else { 2988 SkScalar t = roots[0]; 2989 SkScalar C = pts[0].fX; 2990 SkScalar A = pts[2].fX - 2 * pts[1].fX + C; 2991 SkScalar B = 2 * (pts[1].fX - C); 2992 xt = poly_eval(A, B, C, t); 2993 } 2994 if (SkScalarNearlyEqual(xt, x)) { 2995 if (x != pts[2].fX || y != pts[2].fY) { // don't test end points; they're start points 2996 *onCurveCount += 1; 2997 return 0; 2998 } 2999 } 3000 return xt < x ? dir : 0; 3001 } 3002 3003 static int winding_quad(const SkPoint pts[], SkScalar x, SkScalar y, int* onCurveCount) { 3004 SkPoint dst[5]; 3005 int n = 0; 3006 3007 if (!is_mono_quad(pts[0].fY, pts[1].fY, pts[2].fY)) { 3008 n = SkChopQuadAtYExtrema(pts, dst); 3009 pts = dst; 3010 } 3011 int w = winding_mono_quad(pts, x, y, onCurveCount); 3012 if (n > 0) { 3013 w += winding_mono_quad(&pts[2], x, y, onCurveCount); 3014 } 3015 return w; 3016 } 3017 3018 static int winding_line(const SkPoint pts[], SkScalar x, SkScalar y, int* onCurveCount) { 3019 SkScalar x0 = pts[0].fX; 3020 SkScalar y0 = pts[0].fY; 3021 SkScalar x1 = pts[1].fX; 3022 SkScalar y1 = pts[1].fY; 3023 3024 SkScalar dy = y1 - y0; 3025 3026 int dir = 1; 3027 if (y0 > y1) { 3028 SkTSwap(y0, y1); 3029 dir = -1; 3030 } 3031 if (y < y0 || y > y1) { 3032 return 0; 3033 } 3034 if (checkOnCurve(x, y, pts[0], pts[1])) { 3035 *onCurveCount += 1; 3036 return 0; 3037 } 3038 if (y == y1) { 3039 return 0; 3040 } 3041 SkScalar cross = (x1 - x0) * (y - pts[0].fY) - dy * (x - x0); 3042 3043 if (!cross) { 3044 // zero cross means the point is on the line, and since the case where 3045 // y of the query point is at the end point is handled above, we can be 3046 // sure that we're on the line (excluding the end point) here 3047 if (x != x1 || y != pts[1].fY) { 3048 *onCurveCount += 1; 3049 } 3050 dir = 0; 3051 } else if (SkScalarSignAsInt(cross) == dir) { 3052 dir = 0; 3053 } 3054 return dir; 3055 } 3056 3057 static void tangent_cubic(const SkPoint pts[], SkScalar x, SkScalar y, 3058 SkTDArray<SkVector>* tangents) { 3059 if (!between(pts[0].fY, y, pts[1].fY) && !between(pts[1].fY, y, pts[2].fY) 3060 && !between(pts[2].fY, y, pts[3].fY)) { 3061 return; 3062 } 3063 if (!between(pts[0].fX, x, pts[1].fX) && !between(pts[1].fX, x, pts[2].fX) 3064 && !between(pts[2].fX, x, pts[3].fX)) { 3065 return; 3066 } 3067 SkPoint dst[10]; 3068 int n = SkChopCubicAtYExtrema(pts, dst); 3069 for (int i = 0; i <= n; ++i) { 3070 SkPoint* c = &dst[i * 3]; 3071 SkScalar t; 3072 if (!SkCubicClipper::ChopMonoAtY(c, y, &t)) { 3073 continue; 3074 } 3075 SkScalar xt = eval_cubic_pts(c[0].fX, c[1].fX, c[2].fX, c[3].fX, t); 3076 if (!SkScalarNearlyEqual(x, xt)) { 3077 continue; 3078 } 3079 SkVector tangent; 3080 SkEvalCubicAt(c, t, nullptr, &tangent, nullptr); 3081 tangents->push(tangent); 3082 } 3083 } 3084 3085 static void tangent_conic(const SkPoint pts[], SkScalar x, SkScalar y, SkScalar w, 3086 SkTDArray<SkVector>* tangents) { 3087 if (!between(pts[0].fY, y, pts[1].fY) && !between(pts[1].fY, y, pts[2].fY)) { 3088 return; 3089 } 3090 if (!between(pts[0].fX, x, pts[1].fX) && !between(pts[1].fX, x, pts[2].fX)) { 3091 return; 3092 } 3093 SkScalar roots[2]; 3094 SkScalar A = pts[2].fY; 3095 SkScalar B = pts[1].fY * w - y * w + y; 3096 SkScalar C = pts[0].fY; 3097 A += C - 2 * B; // A = a + c - 2*(b*w - yCept*w + yCept) 3098 B -= C; // B = b*w - w * yCept + yCept - a 3099 C -= y; 3100 int n = SkFindUnitQuadRoots(A, 2 * B, C, roots); 3101 for (int index = 0; index < n; ++index) { 3102 SkScalar t = roots[index]; 3103 SkScalar xt = conic_eval_numerator(&pts[0].fX, w, t) / conic_eval_denominator(w, t); 3104 if (!SkScalarNearlyEqual(x, xt)) { 3105 continue; 3106 } 3107 SkConic conic(pts, w); 3108 tangents->push(conic.evalTangentAt(t)); 3109 } 3110 } 3111 3112 static void tangent_quad(const SkPoint pts[], SkScalar x, SkScalar y, 3113 SkTDArray<SkVector>* tangents) { 3114 if (!between(pts[0].fY, y, pts[1].fY) && !between(pts[1].fY, y, pts[2].fY)) { 3115 return; 3116 } 3117 if (!between(pts[0].fX, x, pts[1].fX) && !between(pts[1].fX, x, pts[2].fX)) { 3118 return; 3119 } 3120 SkScalar roots[2]; 3121 int n = SkFindUnitQuadRoots(pts[0].fY - 2 * pts[1].fY + pts[2].fY, 3122 2 * (pts[1].fY - pts[0].fY), 3123 pts[0].fY - y, 3124 roots); 3125 for (int index = 0; index < n; ++index) { 3126 SkScalar t = roots[index]; 3127 SkScalar C = pts[0].fX; 3128 SkScalar A = pts[2].fX - 2 * pts[1].fX + C; 3129 SkScalar B = 2 * (pts[1].fX - C); 3130 SkScalar xt = poly_eval(A, B, C, t); 3131 if (!SkScalarNearlyEqual(x, xt)) { 3132 continue; 3133 } 3134 tangents->push(SkEvalQuadTangentAt(pts, t)); 3135 } 3136 } 3137 3138 static void tangent_line(const SkPoint pts[], SkScalar x, SkScalar y, 3139 SkTDArray<SkVector>* tangents) { 3140 SkScalar y0 = pts[0].fY; 3141 SkScalar y1 = pts[1].fY; 3142 if (!between(y0, y, y1)) { 3143 return; 3144 } 3145 SkScalar x0 = pts[0].fX; 3146 SkScalar x1 = pts[1].fX; 3147 if (!between(x0, x, x1)) { 3148 return; 3149 } 3150 SkScalar dx = x1 - x0; 3151 SkScalar dy = y1 - y0; 3152 if (!SkScalarNearlyEqual((x - x0) * dy, dx * (y - y0))) { 3153 return; 3154 } 3155 SkVector v; 3156 v.set(dx, dy); 3157 tangents->push(v); 3158 } 3159 3160 static bool contains_inclusive(const SkRect& r, SkScalar x, SkScalar y) { 3161 return r.fLeft <= x && x <= r.fRight && r.fTop <= y && y <= r.fBottom; 3162 } 3163 3164 bool SkPath::contains(SkScalar x, SkScalar y) const { 3165 bool isInverse = this->isInverseFillType(); 3166 if (this->isEmpty()) { 3167 return isInverse; 3168 } 3169 3170 if (!contains_inclusive(this->getBounds(), x, y)) { 3171 return isInverse; 3172 } 3173 3174 SkPath::Iter iter(*this, true); 3175 bool done = false; 3176 int w = 0; 3177 int onCurveCount = 0; 3178 do { 3179 SkPoint pts[4]; 3180 switch (iter.next(pts, false)) { 3181 case SkPath::kMove_Verb: 3182 case SkPath::kClose_Verb: 3183 break; 3184 case SkPath::kLine_Verb: 3185 w += winding_line(pts, x, y, &onCurveCount); 3186 break; 3187 case SkPath::kQuad_Verb: 3188 w += winding_quad(pts, x, y, &onCurveCount); 3189 break; 3190 case SkPath::kConic_Verb: 3191 w += winding_conic(pts, x, y, iter.conicWeight(), &onCurveCount); 3192 break; 3193 case SkPath::kCubic_Verb: 3194 w += winding_cubic(pts, x, y, &onCurveCount); 3195 break; 3196 case SkPath::kDone_Verb: 3197 done = true; 3198 break; 3199 } 3200 } while (!done); 3201 bool evenOddFill = SkPath::kEvenOdd_FillType == this->getFillType() 3202 || SkPath::kInverseEvenOdd_FillType == this->getFillType(); 3203 if (evenOddFill) { 3204 w &= 1; 3205 } 3206 if (w) { 3207 return !isInverse; 3208 } 3209 if (onCurveCount <= 1) { 3210 return SkToBool(onCurveCount) ^ isInverse; 3211 } 3212 if ((onCurveCount & 1) || evenOddFill) { 3213 return SkToBool(onCurveCount & 1) ^ isInverse; 3214 } 3215 // If the point touches an even number of curves, and the fill is winding, check for 3216 // coincidence. Count coincidence as places where the on curve points have identical tangents. 3217 iter.setPath(*this, true); 3218 done = false; 3219 SkTDArray<SkVector> tangents; 3220 do { 3221 SkPoint pts[4]; 3222 int oldCount = tangents.count(); 3223 switch (iter.next(pts, false)) { 3224 case SkPath::kMove_Verb: 3225 case SkPath::kClose_Verb: 3226 break; 3227 case SkPath::kLine_Verb: 3228 tangent_line(pts, x, y, &tangents); 3229 break; 3230 case SkPath::kQuad_Verb: 3231 tangent_quad(pts, x, y, &tangents); 3232 break; 3233 case SkPath::kConic_Verb: 3234 tangent_conic(pts, x, y, iter.conicWeight(), &tangents); 3235 break; 3236 case SkPath::kCubic_Verb: 3237 tangent_cubic(pts, x, y, &tangents); 3238 break; 3239 case SkPath::kDone_Verb: 3240 done = true; 3241 break; 3242 } 3243 if (tangents.count() > oldCount) { 3244 int last = tangents.count() - 1; 3245 const SkVector& tangent = tangents[last]; 3246 if (SkScalarNearlyZero(tangent.lengthSqd())) { 3247 tangents.remove(last); 3248 } else { 3249 for (int index = 0; index < last; ++index) { 3250 const SkVector& test = tangents[index]; 3251 if (SkScalarNearlyZero(test.cross(tangent)) 3252 && SkScalarSignAsInt(tangent.fX * test.fX) <= 0 3253 && SkScalarSignAsInt(tangent.fY * test.fY) <= 0) { 3254 tangents.remove(last); 3255 tangents.removeShuffle(index); 3256 break; 3257 } 3258 } 3259 } 3260 } 3261 } while (!done); 3262 return SkToBool(tangents.count()) ^ isInverse; 3263 } 3264 3265 int SkPath::ConvertConicToQuads(const SkPoint& p0, const SkPoint& p1, const SkPoint& p2, 3266 SkScalar w, SkPoint pts[], int pow2) { 3267 const SkConic conic(p0, p1, p2, w); 3268 return conic.chopIntoQuadsPOW2(pts, pow2); 3269 } 3270 3271 bool SkPathPriv::IsSimpleClosedRect(const SkPath& path, SkRect* rect, SkPath::Direction* direction, 3272 unsigned* start) { 3273 if (path.getSegmentMasks() != SkPath::kLine_SegmentMask) { 3274 return false; 3275 } 3276 SkPath::RawIter iter(path); 3277 SkPoint verbPts[4]; 3278 SkPath::Verb v; 3279 SkPoint rectPts[5]; 3280 int rectPtCnt = 0; 3281 while ((v = iter.next(verbPts)) != SkPath::kDone_Verb) { 3282 switch (v) { 3283 case SkPath::kMove_Verb: 3284 if (0 != rectPtCnt) { 3285 return false; 3286 } 3287 rectPts[0] = verbPts[0]; 3288 ++rectPtCnt; 3289 break; 3290 case SkPath::kLine_Verb: 3291 if (5 == rectPtCnt) { 3292 return false; 3293 } 3294 rectPts[rectPtCnt] = verbPts[1]; 3295 ++rectPtCnt; 3296 break; 3297 case SkPath::kClose_Verb: 3298 if (4 == rectPtCnt) { 3299 rectPts[4] = rectPts[0]; 3300 rectPtCnt = 5; 3301 } 3302 break; 3303 default: 3304 return false; 3305 } 3306 } 3307 if (rectPtCnt < 5) { 3308 return false; 3309 } 3310 if (rectPts[0] != rectPts[4]) { 3311 return false; 3312 } 3313 // Check for two cases of rectangles: pts 0 and 3 form a vertical edge or a horizontal edge ( 3314 // and pts 1 and 2 the opposite vertical or horizontal edge). 3315 bool vec03IsVertical; 3316 if (rectPts[0].fX == rectPts[3].fX && rectPts[1].fX == rectPts[2].fX && 3317 rectPts[0].fY == rectPts[1].fY && rectPts[3].fY == rectPts[2].fY) { 3318 // Make sure it has non-zero width and height 3319 if (rectPts[0].fX == rectPts[1].fX || rectPts[0].fY == rectPts[3].fY) { 3320 return false; 3321 } 3322 vec03IsVertical = true; 3323 } else if (rectPts[0].fY == rectPts[3].fY && rectPts[1].fY == rectPts[2].fY && 3324 rectPts[0].fX == rectPts[1].fX && rectPts[3].fX == rectPts[2].fX) { 3325 // Make sure it has non-zero width and height 3326 if (rectPts[0].fY == rectPts[1].fY || rectPts[0].fX == rectPts[3].fX) { 3327 return false; 3328 } 3329 vec03IsVertical = false; 3330 } else { 3331 return false; 3332 } 3333 // Set sortFlags so that it has the low bit set if pt index 0 is on right edge and second bit 3334 // set if it is on the bottom edge. 3335 unsigned sortFlags = 3336 ((rectPts[0].fX < rectPts[2].fX) ? 0b00 : 0b01) | 3337 ((rectPts[0].fY < rectPts[2].fY) ? 0b00 : 0b10); 3338 switch (sortFlags) { 3339 case 0b00: 3340 rect->set(rectPts[0].fX, rectPts[0].fY, rectPts[2].fX, rectPts[2].fY); 3341 *direction = vec03IsVertical ? SkPath::kCW_Direction : SkPath::kCCW_Direction; 3342 *start = 0; 3343 break; 3344 case 0b01: 3345 rect->set(rectPts[2].fX, rectPts[0].fY, rectPts[0].fX, rectPts[2].fY); 3346 *direction = vec03IsVertical ? SkPath::kCCW_Direction : SkPath::kCW_Direction; 3347 *start = 1; 3348 break; 3349 case 0b10: 3350 rect->set(rectPts[0].fX, rectPts[2].fY, rectPts[2].fX, rectPts[0].fY); 3351 *direction = vec03IsVertical ? SkPath::kCCW_Direction : SkPath::kCW_Direction; 3352 *start = 3; 3353 break; 3354 case 0b11: 3355 rect->set(rectPts[2].fX, rectPts[2].fY, rectPts[0].fX, rectPts[0].fY); 3356 *direction = vec03IsVertical ? SkPath::kCW_Direction : SkPath::kCCW_Direction; 3357 *start = 2; 3358 break; 3359 } 3360 return true; 3361 } 3362 3363 void SkPathPriv::CreateDrawArcPath(SkPath* path, const SkRect& oval, SkScalar startAngle, 3364 SkScalar sweepAngle, bool useCenter, bool isFillNoPathEffect) { 3365 SkASSERT(!oval.isEmpty()); 3366 SkASSERT(sweepAngle); 3367 3368 path->reset(); 3369 path->setIsVolatile(true); 3370 path->setFillType(SkPath::kWinding_FillType); 3371 if (isFillNoPathEffect && SkScalarAbs(sweepAngle) >= 360.f) { 3372 path->addOval(oval); 3373 return; 3374 } 3375 if (useCenter) { 3376 path->moveTo(oval.centerX(), oval.centerY()); 3377 } 3378 // Arc to mods at 360 and drawArc is not supposed to. 3379 bool forceMoveTo = !useCenter; 3380 while (sweepAngle <= -360.f) { 3381 path->arcTo(oval, startAngle, -180.f, forceMoveTo); 3382 startAngle -= 180.f; 3383 path->arcTo(oval, startAngle, -180.f, false); 3384 startAngle -= 180.f; 3385 forceMoveTo = false; 3386 sweepAngle += 360.f; 3387 } 3388 while (sweepAngle >= 360.f) { 3389 path->arcTo(oval, startAngle, 180.f, forceMoveTo); 3390 startAngle += 180.f; 3391 path->arcTo(oval, startAngle, 180.f, false); 3392 startAngle += 180.f; 3393 forceMoveTo = false; 3394 sweepAngle -= 360.f; 3395 } 3396 path->arcTo(oval, startAngle, sweepAngle, forceMoveTo); 3397 if (useCenter) { 3398 path->close(); 3399 } 3400 } 3401 3402 /////////////////////////////////////////////////////////////////////////////////////////////////// 3403 #include "SkNx.h" 3404 3405 static int compute_quad_extremas(const SkPoint src[3], SkPoint extremas[3]) { 3406 SkScalar ts[2]; 3407 int n = SkFindQuadExtrema(src[0].fX, src[1].fX, src[2].fX, ts); 3408 n += SkFindQuadExtrema(src[0].fY, src[1].fY, src[2].fY, &ts[n]); 3409 SkASSERT(n >= 0 && n <= 2); 3410 for (int i = 0; i < n; ++i) { 3411 extremas[i] = SkEvalQuadAt(src, ts[i]); 3412 } 3413 extremas[n] = src[2]; 3414 return n + 1; 3415 } 3416 3417 static int compute_conic_extremas(const SkPoint src[3], SkScalar w, SkPoint extremas[3]) { 3418 SkConic conic(src[0], src[1], src[2], w); 3419 SkScalar ts[2]; 3420 int n = conic.findXExtrema(ts); 3421 n += conic.findYExtrema(&ts[n]); 3422 SkASSERT(n >= 0 && n <= 2); 3423 for (int i = 0; i < n; ++i) { 3424 extremas[i] = conic.evalAt(ts[i]); 3425 } 3426 extremas[n] = src[2]; 3427 return n + 1; 3428 } 3429 3430 static int compute_cubic_extremas(const SkPoint src[3], SkPoint extremas[5]) { 3431 SkScalar ts[4]; 3432 int n = SkFindCubicExtrema(src[0].fX, src[1].fX, src[2].fX, src[3].fX, ts); 3433 n += SkFindCubicExtrema(src[0].fY, src[1].fY, src[2].fY, src[3].fY, &ts[n]); 3434 SkASSERT(n >= 0 && n <= 4); 3435 for (int i = 0; i < n; ++i) { 3436 SkEvalCubicAt(src, ts[i], &extremas[i], nullptr, nullptr); 3437 } 3438 extremas[n] = src[3]; 3439 return n + 1; 3440 } 3441 3442 SkRect SkPath::computeTightBounds() const { 3443 if (0 == this->countVerbs()) { 3444 return SkRect::MakeEmpty(); 3445 } 3446 3447 if (this->getSegmentMasks() == SkPath::kLine_SegmentMask) { 3448 return this->getBounds(); 3449 } 3450 3451 SkPoint extremas[5]; // big enough to hold worst-case curve type (cubic) extremas + 1 3452 SkPoint pts[4]; 3453 SkPath::RawIter iter(*this); 3454 3455 // initial with the first MoveTo, so we don't have to check inside the switch 3456 Sk2s min, max; 3457 min = max = from_point(this->getPoint(0)); 3458 for (;;) { 3459 int count = 0; 3460 switch (iter.next(pts)) { 3461 case SkPath::kMove_Verb: 3462 extremas[0] = pts[0]; 3463 count = 1; 3464 break; 3465 case SkPath::kLine_Verb: 3466 extremas[0] = pts[1]; 3467 count = 1; 3468 break; 3469 case SkPath::kQuad_Verb: 3470 count = compute_quad_extremas(pts, extremas); 3471 break; 3472 case SkPath::kConic_Verb: 3473 count = compute_conic_extremas(pts, iter.conicWeight(), extremas); 3474 break; 3475 case SkPath::kCubic_Verb: 3476 count = compute_cubic_extremas(pts, extremas); 3477 break; 3478 case SkPath::kClose_Verb: 3479 break; 3480 case SkPath::kDone_Verb: 3481 goto DONE; 3482 } 3483 for (int i = 0; i < count; ++i) { 3484 Sk2s tmp = from_point(extremas[i]); 3485 min = Sk2s::Min(min, tmp); 3486 max = Sk2s::Max(max, tmp); 3487 } 3488 } 3489 DONE: 3490 SkRect bounds; 3491 min.store((SkPoint*)&bounds.fLeft); 3492 max.store((SkPoint*)&bounds.fRight); 3493 return bounds; 3494 } 3495