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