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 "SkBuffer.h" 9 #include "SkErrorInternals.h" 10 #include "SkGeometry.h" 11 #include "SkMath.h" 12 #include "SkPath.h" 13 #include "SkPathRef.h" 14 #include "SkRRect.h" 15 #include "SkThread.h" 16 17 //////////////////////////////////////////////////////////////////////////// 18 19 /** 20 * Path.bounds is defined to be the bounds of all the control points. 21 * If we called bounds.join(r) we would skip r if r was empty, which breaks 22 * our promise. Hence we have a custom joiner that doesn't look at emptiness 23 */ 24 static void joinNoEmptyChecks(SkRect* dst, const SkRect& src) { 25 dst->fLeft = SkMinScalar(dst->fLeft, src.fLeft); 26 dst->fTop = SkMinScalar(dst->fTop, src.fTop); 27 dst->fRight = SkMaxScalar(dst->fRight, src.fRight); 28 dst->fBottom = SkMaxScalar(dst->fBottom, src.fBottom); 29 } 30 31 static bool is_degenerate(const SkPath& path) { 32 SkPath::Iter iter(path, false); 33 SkPoint pts[4]; 34 return SkPath::kDone_Verb == iter.next(pts); 35 } 36 37 class SkAutoDisableDirectionCheck { 38 public: 39 SkAutoDisableDirectionCheck(SkPath* path) : fPath(path) { 40 fSaved = static_cast<SkPath::Direction>(fPath->fDirection); 41 } 42 43 ~SkAutoDisableDirectionCheck() { 44 fPath->fDirection = fSaved; 45 } 46 47 private: 48 SkPath* fPath; 49 SkPath::Direction fSaved; 50 }; 51 #define SkAutoDisableDirectionCheck(...) SK_REQUIRE_LOCAL_VAR(SkAutoDisableDirectionCheck) 52 53 /* This guy's constructor/destructor bracket a path editing operation. It is 54 used when we know the bounds of the amount we are going to add to the path 55 (usually a new contour, but not required). 56 57 It captures some state about the path up front (i.e. if it already has a 58 cached bounds), and then if it can, it updates the cache bounds explicitly, 59 avoiding the need to revisit all of the points in getBounds(). 60 61 It also notes if the path was originally degenerate, and if so, sets 62 isConvex to true. Thus it can only be used if the contour being added is 63 convex. 64 */ 65 class SkAutoPathBoundsUpdate { 66 public: 67 SkAutoPathBoundsUpdate(SkPath* path, const SkRect& r) : fRect(r) { 68 this->init(path); 69 } 70 71 SkAutoPathBoundsUpdate(SkPath* path, SkScalar left, SkScalar top, 72 SkScalar right, SkScalar bottom) { 73 fRect.set(left, top, right, bottom); 74 this->init(path); 75 } 76 77 ~SkAutoPathBoundsUpdate() { 78 fPath->setConvexity(fDegenerate ? SkPath::kConvex_Convexity 79 : SkPath::kUnknown_Convexity); 80 if (fEmpty || fHasValidBounds) { 81 fPath->setBounds(fRect); 82 } 83 } 84 85 private: 86 SkPath* fPath; 87 SkRect fRect; 88 bool fHasValidBounds; 89 bool fDegenerate; 90 bool fEmpty; 91 92 void init(SkPath* path) { 93 // Cannot use fRect for our bounds unless we know it is sorted 94 fRect.sort(); 95 fPath = path; 96 // Mark the path's bounds as dirty if (1) they are, or (2) the path 97 // is non-finite, and therefore its bounds are not meaningful 98 fHasValidBounds = path->hasComputedBounds() && path->isFinite(); 99 fEmpty = path->isEmpty(); 100 if (fHasValidBounds && !fEmpty) { 101 joinNoEmptyChecks(&fRect, fPath->getBounds()); 102 } 103 fDegenerate = is_degenerate(*path); 104 } 105 }; 106 #define SkAutoPathBoundsUpdate(...) SK_REQUIRE_LOCAL_VAR(SkAutoPathBoundsUpdate) 107 108 //////////////////////////////////////////////////////////////////////////// 109 110 /* 111 Stores the verbs and points as they are given to us, with exceptions: 112 - we only record "Close" if it was immediately preceeded by Move | Line | Quad | Cubic 113 - we insert a Move(0,0) if Line | Quad | Cubic is our first command 114 115 The iterator does more cleanup, especially if forceClose == true 116 1. If we encounter degenerate segments, remove them 117 2. if we encounter Close, return a cons'd up Line() first (if the curr-pt != start-pt) 118 3. if we encounter Move without a preceeding Close, and forceClose is true, goto #2 119 4. if we encounter Line | Quad | Cubic after Close, cons up a Move 120 */ 121 122 //////////////////////////////////////////////////////////////////////////// 123 124 // flag to require a moveTo if we begin with something else, like lineTo etc. 125 #define INITIAL_LASTMOVETOINDEX_VALUE ~0 126 127 SkPath::SkPath() 128 : fPathRef(SkPathRef::CreateEmpty()) { 129 this->resetFields(); 130 fIsVolatile = false; 131 } 132 133 void SkPath::resetFields() { 134 //fPathRef is assumed to have been emptied by the caller. 135 fLastMoveToIndex = INITIAL_LASTMOVETOINDEX_VALUE; 136 fFillType = kWinding_FillType; 137 fConvexity = kUnknown_Convexity; 138 fDirection = kUnknown_Direction; 139 140 // We don't touch Android's fSourcePath. It's used to track texture garbage collection, so we 141 // don't want to muck with it if it's been set to something non-NULL. 142 } 143 144 SkPath::SkPath(const SkPath& that) 145 : fPathRef(SkRef(that.fPathRef.get())) { 146 this->copyFields(that); 147 SkDEBUGCODE(that.validate();) 148 } 149 150 SkPath::~SkPath() { 151 SkDEBUGCODE(this->validate();) 152 } 153 154 SkPath& SkPath::operator=(const SkPath& that) { 155 SkDEBUGCODE(that.validate();) 156 157 if (this != &that) { 158 fPathRef.reset(SkRef(that.fPathRef.get())); 159 this->copyFields(that); 160 } 161 SkDEBUGCODE(this->validate();) 162 return *this; 163 } 164 165 void SkPath::copyFields(const SkPath& that) { 166 //fPathRef is assumed to have been set by the caller. 167 fLastMoveToIndex = that.fLastMoveToIndex; 168 fFillType = that.fFillType; 169 fConvexity = that.fConvexity; 170 fDirection = that.fDirection; 171 fIsVolatile = that.fIsVolatile; 172 } 173 174 bool operator==(const SkPath& a, const SkPath& b) { 175 // note: don't need to look at isConvex or bounds, since just comparing the 176 // raw data is sufficient. 177 return &a == &b || 178 (a.fFillType == b.fFillType && *a.fPathRef.get() == *b.fPathRef.get()); 179 } 180 181 void SkPath::swap(SkPath& that) { 182 if (this != &that) { 183 fPathRef.swap(&that.fPathRef); 184 SkTSwap<int>(fLastMoveToIndex, that.fLastMoveToIndex); 185 SkTSwap<uint8_t>(fFillType, that.fFillType); 186 SkTSwap<uint8_t>(fConvexity, that.fConvexity); 187 SkTSwap<uint8_t>(fDirection, that.fDirection); 188 SkTSwap<SkBool8>(fIsVolatile, that.fIsVolatile); 189 } 190 } 191 192 static inline bool check_edge_against_rect(const SkPoint& p0, 193 const SkPoint& p1, 194 const SkRect& rect, 195 SkPath::Direction dir) { 196 const SkPoint* edgeBegin; 197 SkVector v; 198 if (SkPath::kCW_Direction == dir) { 199 v = p1 - p0; 200 edgeBegin = &p0; 201 } else { 202 v = p0 - p1; 203 edgeBegin = &p1; 204 } 205 if (v.fX || v.fY) { 206 // check the cross product of v with the vec from edgeBegin to each rect corner 207 SkScalar yL = SkScalarMul(v.fY, rect.fLeft - edgeBegin->fX); 208 SkScalar xT = SkScalarMul(v.fX, rect.fTop - edgeBegin->fY); 209 SkScalar yR = SkScalarMul(v.fY, rect.fRight - edgeBegin->fX); 210 SkScalar xB = SkScalarMul(v.fX, rect.fBottom - edgeBegin->fY); 211 if ((xT < yL) || (xT < yR) || (xB < yL) || (xB < yR)) { 212 return false; 213 } 214 } 215 return true; 216 } 217 218 bool SkPath::conservativelyContainsRect(const SkRect& rect) const { 219 // This only handles non-degenerate convex paths currently. 220 if (kConvex_Convexity != this->getConvexity()) { 221 return false; 222 } 223 224 Direction direction; 225 if (!this->cheapComputeDirection(&direction)) { 226 return false; 227 } 228 229 SkPoint firstPt; 230 SkPoint prevPt; 231 RawIter iter(*this); 232 SkPath::Verb verb; 233 SkPoint pts[4]; 234 SkDEBUGCODE(int moveCnt = 0;) 235 SkDEBUGCODE(int segmentCount = 0;) 236 SkDEBUGCODE(int closeCount = 0;) 237 238 while ((verb = iter.next(pts)) != kDone_Verb) { 239 int nextPt = -1; 240 switch (verb) { 241 case kMove_Verb: 242 SkASSERT(!segmentCount && !closeCount); 243 SkDEBUGCODE(++moveCnt); 244 firstPt = prevPt = pts[0]; 245 break; 246 case kLine_Verb: 247 nextPt = 1; 248 SkASSERT(moveCnt && !closeCount); 249 SkDEBUGCODE(++segmentCount); 250 break; 251 case kQuad_Verb: 252 case kConic_Verb: 253 SkASSERT(moveCnt && !closeCount); 254 SkDEBUGCODE(++segmentCount); 255 nextPt = 2; 256 break; 257 case kCubic_Verb: 258 SkASSERT(moveCnt && !closeCount); 259 SkDEBUGCODE(++segmentCount); 260 nextPt = 3; 261 break; 262 case kClose_Verb: 263 SkDEBUGCODE(++closeCount;) 264 break; 265 default: 266 SkDEBUGFAIL("unknown verb"); 267 } 268 if (-1 != nextPt) { 269 if (SkPath::kConic_Verb == verb) { 270 SkConic orig; 271 orig.set(pts, iter.conicWeight()); 272 SkPoint quadPts[5]; 273 int count = orig.chopIntoQuadsPOW2(quadPts, 1); 274 SK_ALWAYSBREAK(2 == count); 275 276 if (!check_edge_against_rect(quadPts[0], quadPts[2], rect, direction)) { 277 return false; 278 } 279 if (!check_edge_against_rect(quadPts[2], quadPts[4], rect, direction)) { 280 return false; 281 } 282 } else { 283 if (!check_edge_against_rect(prevPt, pts[nextPt], rect, direction)) { 284 return false; 285 } 286 } 287 prevPt = pts[nextPt]; 288 } 289 } 290 291 return check_edge_against_rect(prevPt, firstPt, rect, direction); 292 } 293 294 uint32_t SkPath::getGenerationID() const { 295 uint32_t genID = fPathRef->genID(); 296 #ifdef SK_BUILD_FOR_ANDROID_FRAMEWORK 297 SkASSERT((unsigned)fFillType < (1 << (32 - kPathRefGenIDBitCnt))); 298 genID |= static_cast<uint32_t>(fFillType) << kPathRefGenIDBitCnt; 299 #endif 300 return genID; 301 } 302 303 void SkPath::reset() { 304 SkDEBUGCODE(this->validate();) 305 306 fPathRef.reset(SkPathRef::CreateEmpty()); 307 this->resetFields(); 308 } 309 310 void SkPath::rewind() { 311 SkDEBUGCODE(this->validate();) 312 313 SkPathRef::Rewind(&fPathRef); 314 this->resetFields(); 315 } 316 317 bool SkPath::isLine(SkPoint line[2]) const { 318 int verbCount = fPathRef->countVerbs(); 319 320 if (2 == verbCount) { 321 SkASSERT(kMove_Verb == fPathRef->atVerb(0)); 322 if (kLine_Verb == fPathRef->atVerb(1)) { 323 SkASSERT(2 == fPathRef->countPoints()); 324 if (line) { 325 const SkPoint* pts = fPathRef->points(); 326 line[0] = pts[0]; 327 line[1] = pts[1]; 328 } 329 return true; 330 } 331 } 332 return false; 333 } 334 335 /* 336 Determines if path is a rect by keeping track of changes in direction 337 and looking for a loop either clockwise or counterclockwise. 338 339 The direction is computed such that: 340 0: vertical up 341 1: horizontal left 342 2: vertical down 343 3: horizontal right 344 345 A rectangle cycles up/right/down/left or up/left/down/right. 346 347 The test fails if: 348 The path is closed, and followed by a line. 349 A second move creates a new endpoint. 350 A diagonal line is parsed. 351 There's more than four changes of direction. 352 There's a discontinuity on the line (e.g., a move in the middle) 353 The line reverses direction. 354 The path contains a quadratic or cubic. 355 The path contains fewer than four points. 356 *The rectangle doesn't complete a cycle. 357 *The final point isn't equal to the first point. 358 359 *These last two conditions we relax if we have a 3-edge path that would 360 form a rectangle if it were closed (as we do when we fill a path) 361 362 It's OK if the path has: 363 Several colinear line segments composing a rectangle side. 364 Single points on the rectangle side. 365 366 The direction takes advantage of the corners found since opposite sides 367 must travel in opposite directions. 368 369 FIXME: Allow colinear quads and cubics to be treated like lines. 370 FIXME: If the API passes fill-only, return true if the filled stroke 371 is a rectangle, though the caller failed to close the path. 372 373 first,last,next direction state-machine: 374 0x1 is set if the segment is horizontal 375 0x2 is set if the segment is moving to the right or down 376 thus: 377 two directions are opposites iff (dirA ^ dirB) == 0x2 378 two directions are perpendicular iff (dirA ^ dirB) == 0x1 379 380 */ 381 static int rect_make_dir(SkScalar dx, SkScalar dy) { 382 return ((0 != dx) << 0) | ((dx > 0 || dy > 0) << 1); 383 } 384 bool SkPath::isRectContour(bool allowPartial, int* currVerb, const SkPoint** ptsPtr, 385 bool* isClosed, Direction* direction) const { 386 int corners = 0; 387 SkPoint first, last; 388 const SkPoint* pts = *ptsPtr; 389 const SkPoint* savePts = NULL; 390 first.set(0, 0); 391 last.set(0, 0); 392 int firstDirection = 0; 393 int lastDirection = 0; 394 int nextDirection = 0; 395 bool closedOrMoved = false; 396 bool autoClose = false; 397 bool insertClose = false; 398 int verbCnt = fPathRef->countVerbs(); 399 while (*currVerb < verbCnt && (!allowPartial || !autoClose)) { 400 uint8_t verb = insertClose ? (uint8_t) kClose_Verb : fPathRef->atVerb(*currVerb); 401 switch (verb) { 402 case kClose_Verb: 403 savePts = pts; 404 pts = *ptsPtr; 405 autoClose = true; 406 insertClose = false; 407 case kLine_Verb: { 408 SkScalar left = last.fX; 409 SkScalar top = last.fY; 410 SkScalar right = pts->fX; 411 SkScalar bottom = pts->fY; 412 ++pts; 413 if (left != right && top != bottom) { 414 return false; // diagonal 415 } 416 if (left == right && top == bottom) { 417 break; // single point on side OK 418 } 419 nextDirection = rect_make_dir(right - left, bottom - top); 420 if (0 == corners) { 421 firstDirection = nextDirection; 422 first = last; 423 last = pts[-1]; 424 corners = 1; 425 closedOrMoved = false; 426 break; 427 } 428 if (closedOrMoved) { 429 return false; // closed followed by a line 430 } 431 if (autoClose && nextDirection == firstDirection) { 432 break; // colinear with first 433 } 434 closedOrMoved = autoClose; 435 if (lastDirection != nextDirection) { 436 if (++corners > 4) { 437 return false; // too many direction changes 438 } 439 } 440 last = pts[-1]; 441 if (lastDirection == nextDirection) { 442 break; // colinear segment 443 } 444 // Possible values for corners are 2, 3, and 4. 445 // When corners == 3, nextDirection opposes firstDirection. 446 // Otherwise, nextDirection at corner 2 opposes corner 4. 447 int turn = firstDirection ^ (corners - 1); 448 int directionCycle = 3 == corners ? 0 : nextDirection ^ turn; 449 if ((directionCycle ^ turn) != nextDirection) { 450 return false; // direction didn't follow cycle 451 } 452 break; 453 } 454 case kQuad_Verb: 455 case kConic_Verb: 456 case kCubic_Verb: 457 return false; // quadratic, cubic not allowed 458 case kMove_Verb: 459 if (allowPartial && !autoClose && firstDirection) { 460 insertClose = true; 461 *currVerb -= 1; // try move again afterwards 462 goto addMissingClose; 463 } 464 last = *pts++; 465 closedOrMoved = true; 466 break; 467 default: 468 SkDEBUGFAIL("unexpected verb"); 469 break; 470 } 471 *currVerb += 1; 472 lastDirection = nextDirection; 473 addMissingClose: 474 ; 475 } 476 // Success if 4 corners and first point equals last 477 bool result = 4 == corners && (first == last || autoClose); 478 if (!result) { 479 // check if we are just an incomplete rectangle, in which case we can 480 // return true, but not claim to be closed. 481 // e.g. 482 // 3 sided rectangle 483 // 4 sided but the last edge is not long enough to reach the start 484 // 485 SkScalar closeX = first.x() - last.x(); 486 SkScalar closeY = first.y() - last.y(); 487 if (closeX && closeY) { 488 return false; // we're diagonal, abort (can we ever reach this?) 489 } 490 int closeDirection = rect_make_dir(closeX, closeY); 491 // make sure the close-segment doesn't double-back on itself 492 if (3 == corners || (4 == corners && closeDirection == lastDirection)) { 493 result = true; 494 autoClose = false; // we are not closed 495 } 496 } 497 if (savePts) { 498 *ptsPtr = savePts; 499 } 500 if (result && isClosed) { 501 *isClosed = autoClose; 502 } 503 if (result && direction) { 504 *direction = firstDirection == ((lastDirection + 1) & 3) ? kCCW_Direction : kCW_Direction; 505 } 506 return result; 507 } 508 509 bool SkPath::isRect(SkRect* rect, bool* isClosed, Direction* direction) const { 510 SkDEBUGCODE(this->validate();) 511 int currVerb = 0; 512 const SkPoint* pts = fPathRef->points(); 513 const SkPoint* first = pts; 514 if (!this->isRectContour(false, &currVerb, &pts, isClosed, direction)) { 515 return false; 516 } 517 if (rect) { 518 int32_t num = SkToS32(pts - first); 519 if (num) { 520 rect->set(first, num); 521 } else { 522 // 'pts' isn't updated for open rects 523 *rect = this->getBounds(); 524 } 525 } 526 return true; 527 } 528 529 bool SkPath::isNestedFillRects(SkRect rects[2], Direction dirs[2]) const { 530 SkDEBUGCODE(this->validate();) 531 int currVerb = 0; 532 const SkPoint* pts = fPathRef->points(); 533 const SkPoint* first = pts; 534 Direction testDirs[2]; 535 if (!isRectContour(true, &currVerb, &pts, NULL, &testDirs[0])) { 536 return false; 537 } 538 const SkPoint* last = pts; 539 SkRect testRects[2]; 540 bool isClosed; 541 if (isRectContour(false, &currVerb, &pts, &isClosed, &testDirs[1])) { 542 testRects[0].set(first, SkToS32(last - first)); 543 if (!isClosed) { 544 pts = fPathRef->points() + fPathRef->countPoints(); 545 } 546 testRects[1].set(last, SkToS32(pts - last)); 547 if (testRects[0].contains(testRects[1])) { 548 if (rects) { 549 rects[0] = testRects[0]; 550 rects[1] = testRects[1]; 551 } 552 if (dirs) { 553 dirs[0] = testDirs[0]; 554 dirs[1] = testDirs[1]; 555 } 556 return true; 557 } 558 if (testRects[1].contains(testRects[0])) { 559 if (rects) { 560 rects[0] = testRects[1]; 561 rects[1] = testRects[0]; 562 } 563 if (dirs) { 564 dirs[0] = testDirs[1]; 565 dirs[1] = testDirs[0]; 566 } 567 return true; 568 } 569 } 570 return false; 571 } 572 573 int SkPath::countPoints() const { 574 return fPathRef->countPoints(); 575 } 576 577 int SkPath::getPoints(SkPoint dst[], int max) const { 578 SkDEBUGCODE(this->validate();) 579 580 SkASSERT(max >= 0); 581 SkASSERT(!max || dst); 582 int count = SkMin32(max, fPathRef->countPoints()); 583 memcpy(dst, fPathRef->points(), count * sizeof(SkPoint)); 584 return fPathRef->countPoints(); 585 } 586 587 SkPoint SkPath::getPoint(int index) const { 588 if ((unsigned)index < (unsigned)fPathRef->countPoints()) { 589 return fPathRef->atPoint(index); 590 } 591 return SkPoint::Make(0, 0); 592 } 593 594 int SkPath::countVerbs() const { 595 return fPathRef->countVerbs(); 596 } 597 598 static inline void copy_verbs_reverse(uint8_t* inorderDst, 599 const uint8_t* reversedSrc, 600 int count) { 601 for (int i = 0; i < count; ++i) { 602 inorderDst[i] = reversedSrc[~i]; 603 } 604 } 605 606 int SkPath::getVerbs(uint8_t dst[], int max) const { 607 SkDEBUGCODE(this->validate();) 608 609 SkASSERT(max >= 0); 610 SkASSERT(!max || dst); 611 int count = SkMin32(max, fPathRef->countVerbs()); 612 copy_verbs_reverse(dst, fPathRef->verbs(), count); 613 return fPathRef->countVerbs(); 614 } 615 616 bool SkPath::getLastPt(SkPoint* lastPt) const { 617 SkDEBUGCODE(this->validate();) 618 619 int count = fPathRef->countPoints(); 620 if (count > 0) { 621 if (lastPt) { 622 *lastPt = fPathRef->atPoint(count - 1); 623 } 624 return true; 625 } 626 if (lastPt) { 627 lastPt->set(0, 0); 628 } 629 return false; 630 } 631 632 void SkPath::setPt(int index, SkScalar x, SkScalar y) { 633 SkDEBUGCODE(this->validate();) 634 635 int count = fPathRef->countPoints(); 636 if (count <= index) { 637 return; 638 } else { 639 SkPathRef::Editor ed(&fPathRef); 640 ed.atPoint(index)->set(x, y); 641 } 642 } 643 644 void SkPath::setLastPt(SkScalar x, SkScalar y) { 645 SkDEBUGCODE(this->validate();) 646 647 int count = fPathRef->countPoints(); 648 if (count == 0) { 649 this->moveTo(x, y); 650 } else { 651 SkPathRef::Editor ed(&fPathRef); 652 ed.atPoint(count-1)->set(x, y); 653 } 654 } 655 656 void SkPath::setConvexity(Convexity c) { 657 if (fConvexity != c) { 658 fConvexity = c; 659 } 660 } 661 662 ////////////////////////////////////////////////////////////////////////////// 663 // Construction methods 664 665 #define DIRTY_AFTER_EDIT \ 666 do { \ 667 fConvexity = kUnknown_Convexity; \ 668 fDirection = kUnknown_Direction; \ 669 } while (0) 670 671 void SkPath::incReserve(U16CPU inc) { 672 SkDEBUGCODE(this->validate();) 673 SkPathRef::Editor(&fPathRef, inc, inc); 674 SkDEBUGCODE(this->validate();) 675 } 676 677 void SkPath::moveTo(SkScalar x, SkScalar y) { 678 SkDEBUGCODE(this->validate();) 679 680 SkPathRef::Editor ed(&fPathRef); 681 682 // remember our index 683 fLastMoveToIndex = fPathRef->countPoints(); 684 685 ed.growForVerb(kMove_Verb)->set(x, y); 686 687 DIRTY_AFTER_EDIT; 688 } 689 690 void SkPath::rMoveTo(SkScalar x, SkScalar y) { 691 SkPoint pt; 692 this->getLastPt(&pt); 693 this->moveTo(pt.fX + x, pt.fY + y); 694 } 695 696 void SkPath::injectMoveToIfNeeded() { 697 if (fLastMoveToIndex < 0) { 698 SkScalar x, y; 699 if (fPathRef->countVerbs() == 0) { 700 x = y = 0; 701 } else { 702 const SkPoint& pt = fPathRef->atPoint(~fLastMoveToIndex); 703 x = pt.fX; 704 y = pt.fY; 705 } 706 this->moveTo(x, y); 707 } 708 } 709 710 void SkPath::lineTo(SkScalar x, SkScalar y) { 711 SkDEBUGCODE(this->validate();) 712 713 this->injectMoveToIfNeeded(); 714 715 SkPathRef::Editor ed(&fPathRef); 716 ed.growForVerb(kLine_Verb)->set(x, y); 717 718 DIRTY_AFTER_EDIT; 719 } 720 721 void SkPath::rLineTo(SkScalar x, SkScalar y) { 722 this->injectMoveToIfNeeded(); // This can change the result of this->getLastPt(). 723 SkPoint pt; 724 this->getLastPt(&pt); 725 this->lineTo(pt.fX + x, pt.fY + y); 726 } 727 728 void SkPath::quadTo(SkScalar x1, SkScalar y1, SkScalar x2, SkScalar y2) { 729 SkDEBUGCODE(this->validate();) 730 731 this->injectMoveToIfNeeded(); 732 733 SkPathRef::Editor ed(&fPathRef); 734 SkPoint* pts = ed.growForVerb(kQuad_Verb); 735 pts[0].set(x1, y1); 736 pts[1].set(x2, y2); 737 738 DIRTY_AFTER_EDIT; 739 } 740 741 void SkPath::rQuadTo(SkScalar x1, SkScalar y1, SkScalar x2, SkScalar y2) { 742 this->injectMoveToIfNeeded(); // This can change the result of this->getLastPt(). 743 SkPoint pt; 744 this->getLastPt(&pt); 745 this->quadTo(pt.fX + x1, pt.fY + y1, pt.fX + x2, pt.fY + y2); 746 } 747 748 void SkPath::conicTo(SkScalar x1, SkScalar y1, SkScalar x2, SkScalar y2, 749 SkScalar w) { 750 // check for <= 0 or NaN with this test 751 if (!(w > 0)) { 752 this->lineTo(x2, y2); 753 } else if (!SkScalarIsFinite(w)) { 754 this->lineTo(x1, y1); 755 this->lineTo(x2, y2); 756 } else if (SK_Scalar1 == w) { 757 this->quadTo(x1, y1, x2, y2); 758 } else { 759 SkDEBUGCODE(this->validate();) 760 761 this->injectMoveToIfNeeded(); 762 763 SkPathRef::Editor ed(&fPathRef); 764 SkPoint* pts = ed.growForVerb(kConic_Verb, w); 765 pts[0].set(x1, y1); 766 pts[1].set(x2, y2); 767 768 DIRTY_AFTER_EDIT; 769 } 770 } 771 772 void SkPath::rConicTo(SkScalar dx1, SkScalar dy1, SkScalar dx2, SkScalar dy2, 773 SkScalar w) { 774 this->injectMoveToIfNeeded(); // This can change the result of this->getLastPt(). 775 SkPoint pt; 776 this->getLastPt(&pt); 777 this->conicTo(pt.fX + dx1, pt.fY + dy1, pt.fX + dx2, pt.fY + dy2, w); 778 } 779 780 void SkPath::cubicTo(SkScalar x1, SkScalar y1, SkScalar x2, SkScalar y2, 781 SkScalar x3, SkScalar y3) { 782 SkDEBUGCODE(this->validate();) 783 784 this->injectMoveToIfNeeded(); 785 786 SkPathRef::Editor ed(&fPathRef); 787 SkPoint* pts = ed.growForVerb(kCubic_Verb); 788 pts[0].set(x1, y1); 789 pts[1].set(x2, y2); 790 pts[2].set(x3, y3); 791 792 DIRTY_AFTER_EDIT; 793 } 794 795 void SkPath::rCubicTo(SkScalar x1, SkScalar y1, SkScalar x2, SkScalar y2, 796 SkScalar x3, SkScalar y3) { 797 this->injectMoveToIfNeeded(); // This can change the result of this->getLastPt(). 798 SkPoint pt; 799 this->getLastPt(&pt); 800 this->cubicTo(pt.fX + x1, pt.fY + y1, pt.fX + x2, pt.fY + y2, 801 pt.fX + x3, pt.fY + y3); 802 } 803 804 void SkPath::close() { 805 SkDEBUGCODE(this->validate();) 806 807 int count = fPathRef->countVerbs(); 808 if (count > 0) { 809 switch (fPathRef->atVerb(count - 1)) { 810 case kLine_Verb: 811 case kQuad_Verb: 812 case kConic_Verb: 813 case kCubic_Verb: 814 case kMove_Verb: { 815 SkPathRef::Editor ed(&fPathRef); 816 ed.growForVerb(kClose_Verb); 817 break; 818 } 819 case kClose_Verb: 820 // don't add a close if it's the first verb or a repeat 821 break; 822 default: 823 SkDEBUGFAIL("unexpected verb"); 824 break; 825 } 826 } 827 828 // signal that we need a moveTo to follow us (unless we're done) 829 #if 0 830 if (fLastMoveToIndex >= 0) { 831 fLastMoveToIndex = ~fLastMoveToIndex; 832 } 833 #else 834 fLastMoveToIndex ^= ~fLastMoveToIndex >> (8 * sizeof(fLastMoveToIndex) - 1); 835 #endif 836 } 837 838 /////////////////////////////////////////////////////////////////////////////// 839 840 static void assert_known_direction(int dir) { 841 SkASSERT(SkPath::kCW_Direction == dir || SkPath::kCCW_Direction == dir); 842 } 843 844 void SkPath::addRect(const SkRect& rect, Direction dir) { 845 this->addRect(rect.fLeft, rect.fTop, rect.fRight, rect.fBottom, dir); 846 } 847 848 void SkPath::addRect(SkScalar left, SkScalar top, SkScalar right, 849 SkScalar bottom, Direction dir) { 850 assert_known_direction(dir); 851 fDirection = this->hasOnlyMoveTos() ? dir : kUnknown_Direction; 852 SkAutoDisableDirectionCheck addc(this); 853 854 SkAutoPathBoundsUpdate apbu(this, left, top, right, bottom); 855 856 this->incReserve(5); 857 858 this->moveTo(left, top); 859 if (dir == kCCW_Direction) { 860 this->lineTo(left, bottom); 861 this->lineTo(right, bottom); 862 this->lineTo(right, top); 863 } else { 864 this->lineTo(right, top); 865 this->lineTo(right, bottom); 866 this->lineTo(left, bottom); 867 } 868 this->close(); 869 } 870 871 void SkPath::addPoly(const SkPoint pts[], int count, bool close) { 872 SkDEBUGCODE(this->validate();) 873 if (count <= 0) { 874 return; 875 } 876 877 fLastMoveToIndex = fPathRef->countPoints(); 878 879 // +close makes room for the extra kClose_Verb 880 SkPathRef::Editor ed(&fPathRef, count+close, count); 881 882 ed.growForVerb(kMove_Verb)->set(pts[0].fX, pts[0].fY); 883 if (count > 1) { 884 SkPoint* p = ed.growForRepeatedVerb(kLine_Verb, count - 1); 885 memcpy(p, &pts[1], (count-1) * sizeof(SkPoint)); 886 } 887 888 if (close) { 889 ed.growForVerb(kClose_Verb); 890 fLastMoveToIndex ^= ~fLastMoveToIndex >> (8 * sizeof(fLastMoveToIndex) - 1); 891 } 892 893 DIRTY_AFTER_EDIT; 894 SkDEBUGCODE(this->validate();) 895 } 896 897 #include "SkGeometry.h" 898 899 static bool arc_is_lone_point(const SkRect& oval, SkScalar startAngle, SkScalar sweepAngle, 900 SkPoint* pt) { 901 if (0 == sweepAngle && (0 == startAngle || SkIntToScalar(360) == startAngle)) { 902 // Chrome uses this path to move into and out of ovals. If not 903 // treated as a special case the moves can distort the oval's 904 // bounding box (and break the circle special case). 905 pt->set(oval.fRight, oval.centerY()); 906 return true; 907 } else if (0 == oval.width() && 0 == oval.height()) { 908 // Chrome will sometimes create 0 radius round rects. Having degenerate 909 // quad segments in the path prevents the path from being recognized as 910 // a rect. 911 // TODO: optimizing the case where only one of width or height is zero 912 // should also be considered. This case, however, doesn't seem to be 913 // as common as the single point case. 914 pt->set(oval.fRight, oval.fTop); 915 return true; 916 } 917 return false; 918 } 919 920 // Return the unit vectors pointing at the start/stop points for the given start/sweep angles 921 // 922 static void angles_to_unit_vectors(SkScalar startAngle, SkScalar sweepAngle, 923 SkVector* startV, SkVector* stopV, SkRotationDirection* dir) { 924 startV->fY = SkScalarSinCos(SkDegreesToRadians(startAngle), &startV->fX); 925 stopV->fY = SkScalarSinCos(SkDegreesToRadians(startAngle + sweepAngle), &stopV->fX); 926 927 /* If the sweep angle is nearly (but less than) 360, then due to precision 928 loss in radians-conversion and/or sin/cos, we may end up with coincident 929 vectors, which will fool SkBuildQuadArc into doing nothing (bad) instead 930 of drawing a nearly complete circle (good). 931 e.g. canvas.drawArc(0, 359.99, ...) 932 -vs- canvas.drawArc(0, 359.9, ...) 933 We try to detect this edge case, and tweak the stop vector 934 */ 935 if (*startV == *stopV) { 936 SkScalar sw = SkScalarAbs(sweepAngle); 937 if (sw < SkIntToScalar(360) && sw > SkIntToScalar(359)) { 938 SkScalar stopRad = SkDegreesToRadians(startAngle + sweepAngle); 939 // make a guess at a tiny angle (in radians) to tweak by 940 SkScalar deltaRad = SkScalarCopySign(SK_Scalar1/512, sweepAngle); 941 // not sure how much will be enough, so we use a loop 942 do { 943 stopRad -= deltaRad; 944 stopV->fY = SkScalarSinCos(stopRad, &stopV->fX); 945 } while (*startV == *stopV); 946 } 947 } 948 *dir = sweepAngle > 0 ? kCW_SkRotationDirection : kCCW_SkRotationDirection; 949 } 950 951 /** 952 * If this returns 0, then the caller should just line-to the singlePt, else it should 953 * ignore singlePt and append the specified number of conics. 954 */ 955 static int build_arc_conics(const SkRect& oval, const SkVector& start, const SkVector& stop, 956 SkRotationDirection dir, SkConic conics[SkConic::kMaxConicsForArc], 957 SkPoint* singlePt) { 958 SkMatrix matrix; 959 960 matrix.setScale(SkScalarHalf(oval.width()), SkScalarHalf(oval.height())); 961 matrix.postTranslate(oval.centerX(), oval.centerY()); 962 963 int count = SkConic::BuildUnitArc(start, stop, dir, &matrix, conics); 964 if (0 == count) { 965 matrix.mapXY(start.x(), start.y(), singlePt); 966 } 967 return count; 968 } 969 970 void SkPath::addRoundRect(const SkRect& rect, const SkScalar radii[], 971 Direction dir) { 972 SkRRect rrect; 973 rrect.setRectRadii(rect, (const SkVector*) radii); 974 this->addRRect(rrect, dir); 975 } 976 977 void SkPath::addRRect(const SkRRect& rrect, Direction dir) { 978 assert_known_direction(dir); 979 980 if (rrect.isEmpty()) { 981 return; 982 } 983 984 const SkRect& bounds = rrect.getBounds(); 985 986 if (rrect.isRect()) { 987 this->addRect(bounds, dir); 988 } else if (rrect.isOval()) { 989 this->addOval(bounds, dir); 990 } else { 991 fDirection = this->hasOnlyMoveTos() ? dir : kUnknown_Direction; 992 993 SkAutoPathBoundsUpdate apbu(this, bounds); 994 SkAutoDisableDirectionCheck addc(this); 995 996 const SkScalar L = bounds.fLeft; 997 const SkScalar T = bounds.fTop; 998 const SkScalar R = bounds.fRight; 999 const SkScalar B = bounds.fBottom; 1000 const SkScalar W = SK_ScalarRoot2Over2; 1001 1002 this->incReserve(13); 1003 if (kCW_Direction == dir) { 1004 this->moveTo(L, B - rrect.fRadii[SkRRect::kLowerLeft_Corner].fY); 1005 1006 this->lineTo(L, T + rrect.fRadii[SkRRect::kUpperLeft_Corner].fY); 1007 this->conicTo(L, T, L + rrect.fRadii[SkRRect::kUpperLeft_Corner].fX, T, W); 1008 1009 this->lineTo(R - rrect.fRadii[SkRRect::kUpperRight_Corner].fX, T); 1010 this->conicTo(R, T, R, T + rrect.fRadii[SkRRect::kUpperRight_Corner].fY, W); 1011 1012 this->lineTo(R, B - rrect.fRadii[SkRRect::kLowerRight_Corner].fY); 1013 this->conicTo(R, B, R - rrect.fRadii[SkRRect::kLowerRight_Corner].fX, B, W); 1014 1015 this->lineTo(L + rrect.fRadii[SkRRect::kLowerLeft_Corner].fX, B); 1016 this->conicTo(L, B, L, B - rrect.fRadii[SkRRect::kLowerLeft_Corner].fY, W); 1017 } else { 1018 this->moveTo(L, T + rrect.fRadii[SkRRect::kUpperLeft_Corner].fY); 1019 1020 this->lineTo(L, B - rrect.fRadii[SkRRect::kLowerLeft_Corner].fY); 1021 this->conicTo(L, B, L + rrect.fRadii[SkRRect::kLowerLeft_Corner].fX, B, W); 1022 1023 this->lineTo(R - rrect.fRadii[SkRRect::kLowerRight_Corner].fX, B); 1024 this->conicTo(R, B, R, B - rrect.fRadii[SkRRect::kLowerRight_Corner].fY, W); 1025 1026 this->lineTo(R, T + rrect.fRadii[SkRRect::kUpperRight_Corner].fY); 1027 this->conicTo(R, T, R - rrect.fRadii[SkRRect::kUpperRight_Corner].fX, T, W); 1028 1029 this->lineTo(L + rrect.fRadii[SkRRect::kUpperLeft_Corner].fX, T); 1030 this->conicTo(L, T, L, T + rrect.fRadii[SkRRect::kUpperLeft_Corner].fY, W); 1031 } 1032 this->close(); 1033 } 1034 SkDEBUGCODE(fPathRef->validate();) 1035 } 1036 1037 bool SkPath::hasOnlyMoveTos() const { 1038 int count = fPathRef->countVerbs(); 1039 const uint8_t* verbs = const_cast<const SkPathRef*>(fPathRef.get())->verbsMemBegin(); 1040 for (int i = 0; i < count; ++i) { 1041 if (*verbs == kLine_Verb || 1042 *verbs == kQuad_Verb || 1043 *verbs == kConic_Verb || 1044 *verbs == kCubic_Verb) { 1045 return false; 1046 } 1047 ++verbs; 1048 } 1049 return true; 1050 } 1051 1052 void SkPath::addRoundRect(const SkRect& rect, SkScalar rx, SkScalar ry, 1053 Direction dir) { 1054 assert_known_direction(dir); 1055 1056 if (rx < 0 || ry < 0) { 1057 SkErrorInternals::SetError( kInvalidArgument_SkError, 1058 "I got %f and %f as radii to SkPath::AddRoundRect, " 1059 "but negative radii are not allowed.", 1060 SkScalarToDouble(rx), SkScalarToDouble(ry) ); 1061 return; 1062 } 1063 1064 SkRRect rrect; 1065 rrect.setRectXY(rect, rx, ry); 1066 this->addRRect(rrect, dir); 1067 } 1068 1069 void SkPath::addOval(const SkRect& oval, Direction dir) { 1070 assert_known_direction(dir); 1071 1072 /* If addOval() is called after previous moveTo(), 1073 this path is still marked as an oval. This is used to 1074 fit into WebKit's calling sequences. 1075 We can't simply check isEmpty() in this case, as additional 1076 moveTo() would mark the path non empty. 1077 */ 1078 bool isOval = hasOnlyMoveTos(); 1079 if (isOval) { 1080 fDirection = dir; 1081 } else { 1082 fDirection = kUnknown_Direction; 1083 } 1084 1085 SkAutoDisableDirectionCheck addc(this); 1086 1087 SkAutoPathBoundsUpdate apbu(this, oval); 1088 1089 const SkScalar L = oval.fLeft; 1090 const SkScalar T = oval.fTop; 1091 const SkScalar R = oval.fRight; 1092 const SkScalar B = oval.fBottom; 1093 const SkScalar cx = oval.centerX(); 1094 const SkScalar cy = oval.centerY(); 1095 const SkScalar weight = SK_ScalarRoot2Over2; 1096 1097 this->incReserve(9); // move + 4 conics 1098 this->moveTo(R, cy); 1099 if (dir == kCCW_Direction) { 1100 this->conicTo(R, T, cx, T, weight); 1101 this->conicTo(L, T, L, cy, weight); 1102 this->conicTo(L, B, cx, B, weight); 1103 this->conicTo(R, B, R, cy, weight); 1104 } else { 1105 this->conicTo(R, B, cx, B, weight); 1106 this->conicTo(L, B, L, cy, weight); 1107 this->conicTo(L, T, cx, T, weight); 1108 this->conicTo(R, T, R, cy, weight); 1109 } 1110 this->close(); 1111 1112 SkPathRef::Editor ed(&fPathRef); 1113 1114 ed.setIsOval(isOval); 1115 } 1116 1117 void SkPath::addCircle(SkScalar x, SkScalar y, SkScalar r, Direction dir) { 1118 if (r > 0) { 1119 SkRect rect; 1120 rect.set(x - r, y - r, x + r, y + r); 1121 this->addOval(rect, dir); 1122 } 1123 } 1124 1125 void SkPath::arcTo(const SkRect& oval, SkScalar startAngle, SkScalar sweepAngle, 1126 bool forceMoveTo) { 1127 if (oval.width() < 0 || oval.height() < 0) { 1128 return; 1129 } 1130 1131 if (fPathRef->countVerbs() == 0) { 1132 forceMoveTo = true; 1133 } 1134 1135 SkPoint lonePt; 1136 if (arc_is_lone_point(oval, startAngle, sweepAngle, &lonePt)) { 1137 forceMoveTo ? this->moveTo(lonePt) : this->lineTo(lonePt); 1138 return; 1139 } 1140 1141 SkVector startV, stopV; 1142 SkRotationDirection dir; 1143 angles_to_unit_vectors(startAngle, sweepAngle, &startV, &stopV, &dir); 1144 1145 SkPoint singlePt; 1146 SkConic conics[SkConic::kMaxConicsForArc]; 1147 int count = build_arc_conics(oval, startV, stopV, dir, conics, &singlePt); 1148 if (count) { 1149 this->incReserve(count * 2 + 1); 1150 const SkPoint& pt = conics[0].fPts[0]; 1151 forceMoveTo ? this->moveTo(pt) : this->lineTo(pt); 1152 for (int i = 0; i < count; ++i) { 1153 this->conicTo(conics[i].fPts[1], conics[i].fPts[2], conics[i].fW); 1154 } 1155 } else { 1156 forceMoveTo ? this->moveTo(singlePt) : this->lineTo(singlePt); 1157 } 1158 } 1159 1160 void SkPath::addArc(const SkRect& oval, SkScalar startAngle, SkScalar sweepAngle) { 1161 if (oval.isEmpty() || 0 == sweepAngle) { 1162 return; 1163 } 1164 1165 const SkScalar kFullCircleAngle = SkIntToScalar(360); 1166 1167 if (sweepAngle >= kFullCircleAngle || sweepAngle <= -kFullCircleAngle) { 1168 this->addOval(oval, sweepAngle > 0 ? kCW_Direction : kCCW_Direction); 1169 } else { 1170 this->arcTo(oval, startAngle, sweepAngle, true); 1171 } 1172 } 1173 1174 /* 1175 Need to handle the case when the angle is sharp, and our computed end-points 1176 for the arc go behind pt1 and/or p2... 1177 */ 1178 void SkPath::arcTo(SkScalar x1, SkScalar y1, SkScalar x2, SkScalar y2, SkScalar radius) { 1179 if (radius == 0) { 1180 this->lineTo(x1, y1); 1181 return; 1182 } 1183 1184 SkVector before, after; 1185 1186 // need to know our prev pt so we can construct tangent vectors 1187 { 1188 SkPoint start; 1189 this->getLastPt(&start); 1190 // Handle degenerate cases by adding a line to the first point and 1191 // bailing out. 1192 before.setNormalize(x1 - start.fX, y1 - start.fY); 1193 after.setNormalize(x2 - x1, y2 - y1); 1194 } 1195 1196 SkScalar cosh = SkPoint::DotProduct(before, after); 1197 SkScalar sinh = SkPoint::CrossProduct(before, after); 1198 1199 if (SkScalarNearlyZero(sinh)) { // angle is too tight 1200 this->lineTo(x1, y1); 1201 return; 1202 } 1203 1204 SkScalar dist = SkScalarMulDiv(radius, SK_Scalar1 - cosh, sinh); 1205 if (dist < 0) { 1206 dist = -dist; 1207 } 1208 1209 SkScalar xx = x1 - SkScalarMul(dist, before.fX); 1210 SkScalar yy = y1 - SkScalarMul(dist, before.fY); 1211 SkRotationDirection arcDir; 1212 1213 // now turn before/after into normals 1214 if (sinh > 0) { 1215 before.rotateCCW(); 1216 after.rotateCCW(); 1217 arcDir = kCW_SkRotationDirection; 1218 } else { 1219 before.rotateCW(); 1220 after.rotateCW(); 1221 arcDir = kCCW_SkRotationDirection; 1222 } 1223 1224 SkMatrix matrix; 1225 SkPoint pts[kSkBuildQuadArcStorage]; 1226 1227 matrix.setScale(radius, radius); 1228 matrix.postTranslate(xx - SkScalarMul(radius, before.fX), 1229 yy - SkScalarMul(radius, before.fY)); 1230 1231 int count = SkBuildQuadArc(before, after, arcDir, &matrix, pts); 1232 1233 this->incReserve(count); 1234 // [xx,yy] == pts[0] 1235 this->lineTo(xx, yy); 1236 for (int i = 1; i < count; i += 2) { 1237 this->quadTo(pts[i], pts[i+1]); 1238 } 1239 } 1240 1241 /////////////////////////////////////////////////////////////////////////////// 1242 1243 void SkPath::addPath(const SkPath& path, SkScalar dx, SkScalar dy, AddPathMode mode) { 1244 SkMatrix matrix; 1245 1246 matrix.setTranslate(dx, dy); 1247 this->addPath(path, matrix, mode); 1248 } 1249 1250 void SkPath::addPath(const SkPath& path, const SkMatrix& matrix, AddPathMode mode) { 1251 SkPathRef::Editor(&fPathRef, path.countVerbs(), path.countPoints()); 1252 1253 RawIter iter(path); 1254 SkPoint pts[4]; 1255 Verb verb; 1256 1257 SkMatrix::MapPtsProc proc = matrix.getMapPtsProc(); 1258 bool firstVerb = true; 1259 while ((verb = iter.next(pts)) != kDone_Verb) { 1260 switch (verb) { 1261 case kMove_Verb: 1262 proc(matrix, &pts[0], &pts[0], 1); 1263 if (firstVerb && mode == kExtend_AddPathMode && !isEmpty()) { 1264 injectMoveToIfNeeded(); // In case last contour is closed 1265 this->lineTo(pts[0]); 1266 } else { 1267 this->moveTo(pts[0]); 1268 } 1269 break; 1270 case kLine_Verb: 1271 proc(matrix, &pts[1], &pts[1], 1); 1272 this->lineTo(pts[1]); 1273 break; 1274 case kQuad_Verb: 1275 proc(matrix, &pts[1], &pts[1], 2); 1276 this->quadTo(pts[1], pts[2]); 1277 break; 1278 case kConic_Verb: 1279 proc(matrix, &pts[1], &pts[1], 2); 1280 this->conicTo(pts[1], pts[2], iter.conicWeight()); 1281 break; 1282 case kCubic_Verb: 1283 proc(matrix, &pts[1], &pts[1], 3); 1284 this->cubicTo(pts[1], pts[2], pts[3]); 1285 break; 1286 case kClose_Verb: 1287 this->close(); 1288 break; 1289 default: 1290 SkDEBUGFAIL("unknown verb"); 1291 } 1292 firstVerb = false; 1293 } 1294 } 1295 1296 /////////////////////////////////////////////////////////////////////////////// 1297 1298 static int pts_in_verb(unsigned verb) { 1299 static const uint8_t gPtsInVerb[] = { 1300 1, // kMove 1301 1, // kLine 1302 2, // kQuad 1303 2, // kConic 1304 3, // kCubic 1305 0, // kClose 1306 0 // kDone 1307 }; 1308 1309 SkASSERT(verb < SK_ARRAY_COUNT(gPtsInVerb)); 1310 return gPtsInVerb[verb]; 1311 } 1312 1313 // ignore the last point of the 1st contour 1314 void SkPath::reversePathTo(const SkPath& path) { 1315 int i, vcount = path.fPathRef->countVerbs(); 1316 // exit early if the path is empty, or just has a moveTo. 1317 if (vcount < 2) { 1318 return; 1319 } 1320 1321 SkPathRef::Editor(&fPathRef, vcount, path.countPoints()); 1322 1323 const uint8_t* verbs = path.fPathRef->verbs(); 1324 const SkPoint* pts = path.fPathRef->points(); 1325 const SkScalar* conicWeights = path.fPathRef->conicWeights(); 1326 1327 SkASSERT(verbs[~0] == kMove_Verb); 1328 for (i = 1; i < vcount; ++i) { 1329 unsigned v = verbs[~i]; 1330 int n = pts_in_verb(v); 1331 if (n == 0) { 1332 break; 1333 } 1334 pts += n; 1335 conicWeights += (SkPath::kConic_Verb == v); 1336 } 1337 1338 while (--i > 0) { 1339 switch (verbs[~i]) { 1340 case kLine_Verb: 1341 this->lineTo(pts[-1].fX, pts[-1].fY); 1342 break; 1343 case kQuad_Verb: 1344 this->quadTo(pts[-1].fX, pts[-1].fY, pts[-2].fX, pts[-2].fY); 1345 break; 1346 case kConic_Verb: 1347 this->conicTo(pts[-1], pts[-2], *--conicWeights); 1348 break; 1349 case kCubic_Verb: 1350 this->cubicTo(pts[-1].fX, pts[-1].fY, pts[-2].fX, pts[-2].fY, 1351 pts[-3].fX, pts[-3].fY); 1352 break; 1353 default: 1354 SkDEBUGFAIL("bad verb"); 1355 break; 1356 } 1357 pts -= pts_in_verb(verbs[~i]); 1358 } 1359 } 1360 1361 void SkPath::reverseAddPath(const SkPath& src) { 1362 SkPathRef::Editor ed(&fPathRef, src.fPathRef->countPoints(), src.fPathRef->countVerbs()); 1363 1364 const SkPoint* pts = src.fPathRef->pointsEnd(); 1365 // we will iterator through src's verbs backwards 1366 const uint8_t* verbs = src.fPathRef->verbsMemBegin(); // points at the last verb 1367 const uint8_t* verbsEnd = src.fPathRef->verbs(); // points just past the first verb 1368 const SkScalar* conicWeights = src.fPathRef->conicWeightsEnd(); 1369 1370 bool needMove = true; 1371 bool needClose = false; 1372 while (verbs < verbsEnd) { 1373 uint8_t v = *(verbs++); 1374 int n = pts_in_verb(v); 1375 1376 if (needMove) { 1377 --pts; 1378 this->moveTo(pts->fX, pts->fY); 1379 needMove = false; 1380 } 1381 pts -= n; 1382 switch (v) { 1383 case kMove_Verb: 1384 if (needClose) { 1385 this->close(); 1386 needClose = false; 1387 } 1388 needMove = true; 1389 pts += 1; // so we see the point in "if (needMove)" above 1390 break; 1391 case kLine_Verb: 1392 this->lineTo(pts[0]); 1393 break; 1394 case kQuad_Verb: 1395 this->quadTo(pts[1], pts[0]); 1396 break; 1397 case kConic_Verb: 1398 this->conicTo(pts[1], pts[0], *--conicWeights); 1399 break; 1400 case kCubic_Verb: 1401 this->cubicTo(pts[2], pts[1], pts[0]); 1402 break; 1403 case kClose_Verb: 1404 needClose = true; 1405 break; 1406 default: 1407 SkDEBUGFAIL("unexpected verb"); 1408 } 1409 } 1410 } 1411 1412 /////////////////////////////////////////////////////////////////////////////// 1413 1414 void SkPath::offset(SkScalar dx, SkScalar dy, SkPath* dst) const { 1415 SkMatrix matrix; 1416 1417 matrix.setTranslate(dx, dy); 1418 this->transform(matrix, dst); 1419 } 1420 1421 static void subdivide_cubic_to(SkPath* path, const SkPoint pts[4], 1422 int level = 2) { 1423 if (--level >= 0) { 1424 SkPoint tmp[7]; 1425 1426 SkChopCubicAtHalf(pts, tmp); 1427 subdivide_cubic_to(path, &tmp[0], level); 1428 subdivide_cubic_to(path, &tmp[3], level); 1429 } else { 1430 path->cubicTo(pts[1], pts[2], pts[3]); 1431 } 1432 } 1433 1434 void SkPath::transform(const SkMatrix& matrix, SkPath* dst) const { 1435 SkDEBUGCODE(this->validate();) 1436 if (dst == NULL) { 1437 dst = (SkPath*)this; 1438 } 1439 1440 if (matrix.hasPerspective()) { 1441 SkPath tmp; 1442 tmp.fFillType = fFillType; 1443 1444 SkPath::Iter iter(*this, false); 1445 SkPoint pts[4]; 1446 SkPath::Verb verb; 1447 1448 while ((verb = iter.next(pts, false)) != kDone_Verb) { 1449 switch (verb) { 1450 case kMove_Verb: 1451 tmp.moveTo(pts[0]); 1452 break; 1453 case kLine_Verb: 1454 tmp.lineTo(pts[1]); 1455 break; 1456 case kQuad_Verb: 1457 // promote the quad to a conic 1458 tmp.conicTo(pts[1], pts[2], 1459 SkConic::TransformW(pts, SK_Scalar1, matrix)); 1460 break; 1461 case kConic_Verb: 1462 tmp.conicTo(pts[1], pts[2], 1463 SkConic::TransformW(pts, iter.conicWeight(), matrix)); 1464 break; 1465 case kCubic_Verb: 1466 subdivide_cubic_to(&tmp, pts); 1467 break; 1468 case kClose_Verb: 1469 tmp.close(); 1470 break; 1471 default: 1472 SkDEBUGFAIL("unknown verb"); 1473 break; 1474 } 1475 } 1476 1477 dst->swap(tmp); 1478 SkPathRef::Editor ed(&dst->fPathRef); 1479 matrix.mapPoints(ed.points(), ed.pathRef()->countPoints()); 1480 dst->fDirection = kUnknown_Direction; 1481 } else { 1482 SkPathRef::CreateTransformedCopy(&dst->fPathRef, *fPathRef.get(), matrix); 1483 1484 if (this != dst) { 1485 dst->fFillType = fFillType; 1486 dst->fConvexity = fConvexity; 1487 dst->fIsVolatile = fIsVolatile; 1488 } 1489 1490 if (kUnknown_Direction == fDirection) { 1491 dst->fDirection = kUnknown_Direction; 1492 } else { 1493 SkScalar det2x2 = 1494 SkScalarMul(matrix.get(SkMatrix::kMScaleX), matrix.get(SkMatrix::kMScaleY)) - 1495 SkScalarMul(matrix.get(SkMatrix::kMSkewX), matrix.get(SkMatrix::kMSkewY)); 1496 if (det2x2 < 0) { 1497 dst->fDirection = SkPath::OppositeDirection(static_cast<Direction>(fDirection)); 1498 } else if (det2x2 > 0) { 1499 dst->fDirection = fDirection; 1500 } else { 1501 dst->fConvexity = kUnknown_Convexity; 1502 dst->fDirection = kUnknown_Direction; 1503 } 1504 } 1505 1506 SkDEBUGCODE(dst->validate();) 1507 } 1508 } 1509 1510 /////////////////////////////////////////////////////////////////////////////// 1511 /////////////////////////////////////////////////////////////////////////////// 1512 1513 enum SegmentState { 1514 kEmptyContour_SegmentState, // The current contour is empty. We may be 1515 // starting processing or we may have just 1516 // closed a contour. 1517 kAfterMove_SegmentState, // We have seen a move, but nothing else. 1518 kAfterPrimitive_SegmentState // We have seen a primitive but not yet 1519 // closed the path. Also the initial state. 1520 }; 1521 1522 SkPath::Iter::Iter() { 1523 #ifdef SK_DEBUG 1524 fPts = NULL; 1525 fConicWeights = NULL; 1526 fMoveTo.fX = fMoveTo.fY = fLastPt.fX = fLastPt.fY = 0; 1527 fForceClose = fCloseLine = false; 1528 fSegmentState = kEmptyContour_SegmentState; 1529 #endif 1530 // need to init enough to make next() harmlessly return kDone_Verb 1531 fVerbs = NULL; 1532 fVerbStop = NULL; 1533 fNeedClose = false; 1534 } 1535 1536 SkPath::Iter::Iter(const SkPath& path, bool forceClose) { 1537 this->setPath(path, forceClose); 1538 } 1539 1540 void SkPath::Iter::setPath(const SkPath& path, bool forceClose) { 1541 fPts = path.fPathRef->points(); 1542 fVerbs = path.fPathRef->verbs(); 1543 fVerbStop = path.fPathRef->verbsMemBegin(); 1544 fConicWeights = path.fPathRef->conicWeights() - 1; // begin one behind 1545 fLastPt.fX = fLastPt.fY = 0; 1546 fMoveTo.fX = fMoveTo.fY = 0; 1547 fForceClose = SkToU8(forceClose); 1548 fNeedClose = false; 1549 fSegmentState = kEmptyContour_SegmentState; 1550 } 1551 1552 bool SkPath::Iter::isClosedContour() const { 1553 if (fVerbs == NULL || fVerbs == fVerbStop) { 1554 return false; 1555 } 1556 if (fForceClose) { 1557 return true; 1558 } 1559 1560 const uint8_t* verbs = fVerbs; 1561 const uint8_t* stop = fVerbStop; 1562 1563 if (kMove_Verb == *(verbs - 1)) { 1564 verbs -= 1; // skip the initial moveto 1565 } 1566 1567 while (verbs > stop) { 1568 // verbs points one beyond the current verb, decrement first. 1569 unsigned v = *(--verbs); 1570 if (kMove_Verb == v) { 1571 break; 1572 } 1573 if (kClose_Verb == v) { 1574 return true; 1575 } 1576 } 1577 return false; 1578 } 1579 1580 SkPath::Verb SkPath::Iter::autoClose(SkPoint pts[2]) { 1581 SkASSERT(pts); 1582 if (fLastPt != fMoveTo) { 1583 // A special case: if both points are NaN, SkPoint::operation== returns 1584 // false, but the iterator expects that they are treated as the same. 1585 // (consider SkPoint is a 2-dimension float point). 1586 if (SkScalarIsNaN(fLastPt.fX) || SkScalarIsNaN(fLastPt.fY) || 1587 SkScalarIsNaN(fMoveTo.fX) || SkScalarIsNaN(fMoveTo.fY)) { 1588 return kClose_Verb; 1589 } 1590 1591 pts[0] = fLastPt; 1592 pts[1] = fMoveTo; 1593 fLastPt = fMoveTo; 1594 fCloseLine = true; 1595 return kLine_Verb; 1596 } else { 1597 pts[0] = fMoveTo; 1598 return kClose_Verb; 1599 } 1600 } 1601 1602 const SkPoint& SkPath::Iter::cons_moveTo() { 1603 if (fSegmentState == kAfterMove_SegmentState) { 1604 // Set the first return pt to the move pt 1605 fSegmentState = kAfterPrimitive_SegmentState; 1606 return fMoveTo; 1607 } else { 1608 SkASSERT(fSegmentState == kAfterPrimitive_SegmentState); 1609 // Set the first return pt to the last pt of the previous primitive. 1610 return fPts[-1]; 1611 } 1612 } 1613 1614 void SkPath::Iter::consumeDegenerateSegments() { 1615 // We need to step over anything that will not move the current draw point 1616 // forward before the next move is seen 1617 const uint8_t* lastMoveVerb = 0; 1618 const SkPoint* lastMovePt = 0; 1619 const SkScalar* lastMoveWeight = NULL; 1620 SkPoint lastPt = fLastPt; 1621 while (fVerbs != fVerbStop) { 1622 unsigned verb = *(fVerbs - 1); // fVerbs is one beyond the current verb 1623 switch (verb) { 1624 case kMove_Verb: 1625 // Keep a record of this most recent move 1626 lastMoveVerb = fVerbs; 1627 lastMovePt = fPts; 1628 lastMoveWeight = fConicWeights; 1629 lastPt = fPts[0]; 1630 fVerbs--; 1631 fPts++; 1632 break; 1633 1634 case kClose_Verb: 1635 // A close when we are in a segment is always valid except when it 1636 // follows a move which follows a segment. 1637 if (fSegmentState == kAfterPrimitive_SegmentState && !lastMoveVerb) { 1638 return; 1639 } 1640 // A close at any other time must be ignored 1641 fVerbs--; 1642 break; 1643 1644 case kLine_Verb: 1645 if (!IsLineDegenerate(lastPt, fPts[0])) { 1646 if (lastMoveVerb) { 1647 fVerbs = lastMoveVerb; 1648 fPts = lastMovePt; 1649 fConicWeights = lastMoveWeight; 1650 return; 1651 } 1652 return; 1653 } 1654 // Ignore this line and continue 1655 fVerbs--; 1656 fPts++; 1657 break; 1658 1659 case kConic_Verb: 1660 case kQuad_Verb: 1661 if (!IsQuadDegenerate(lastPt, fPts[0], fPts[1])) { 1662 if (lastMoveVerb) { 1663 fVerbs = lastMoveVerb; 1664 fPts = lastMovePt; 1665 fConicWeights = lastMoveWeight; 1666 return; 1667 } 1668 return; 1669 } 1670 // Ignore this line and continue 1671 fVerbs--; 1672 fPts += 2; 1673 fConicWeights += (kConic_Verb == verb); 1674 break; 1675 1676 case kCubic_Verb: 1677 if (!IsCubicDegenerate(lastPt, fPts[0], fPts[1], fPts[2])) { 1678 if (lastMoveVerb) { 1679 fVerbs = lastMoveVerb; 1680 fPts = lastMovePt; 1681 fConicWeights = lastMoveWeight; 1682 return; 1683 } 1684 return; 1685 } 1686 // Ignore this line and continue 1687 fVerbs--; 1688 fPts += 3; 1689 break; 1690 1691 default: 1692 SkDEBUGFAIL("Should never see kDone_Verb"); 1693 } 1694 } 1695 } 1696 1697 SkPath::Verb SkPath::Iter::doNext(SkPoint ptsParam[4]) { 1698 SkASSERT(ptsParam); 1699 1700 if (fVerbs == fVerbStop) { 1701 // Close the curve if requested and if there is some curve to close 1702 if (fNeedClose && fSegmentState == kAfterPrimitive_SegmentState) { 1703 if (kLine_Verb == this->autoClose(ptsParam)) { 1704 return kLine_Verb; 1705 } 1706 fNeedClose = false; 1707 return kClose_Verb; 1708 } 1709 return kDone_Verb; 1710 } 1711 1712 // fVerbs is one beyond the current verb, decrement first 1713 unsigned verb = *(--fVerbs); 1714 const SkPoint* SK_RESTRICT srcPts = fPts; 1715 SkPoint* SK_RESTRICT pts = ptsParam; 1716 1717 switch (verb) { 1718 case kMove_Verb: 1719 if (fNeedClose) { 1720 fVerbs++; // move back one verb 1721 verb = this->autoClose(pts); 1722 if (verb == kClose_Verb) { 1723 fNeedClose = false; 1724 } 1725 return (Verb)verb; 1726 } 1727 if (fVerbs == fVerbStop) { // might be a trailing moveto 1728 return kDone_Verb; 1729 } 1730 fMoveTo = *srcPts; 1731 pts[0] = *srcPts; 1732 srcPts += 1; 1733 fSegmentState = kAfterMove_SegmentState; 1734 fLastPt = fMoveTo; 1735 fNeedClose = fForceClose; 1736 break; 1737 case kLine_Verb: 1738 pts[0] = this->cons_moveTo(); 1739 pts[1] = srcPts[0]; 1740 fLastPt = srcPts[0]; 1741 fCloseLine = false; 1742 srcPts += 1; 1743 break; 1744 case kConic_Verb: 1745 fConicWeights += 1; 1746 // fall-through 1747 case kQuad_Verb: 1748 pts[0] = this->cons_moveTo(); 1749 memcpy(&pts[1], srcPts, 2 * sizeof(SkPoint)); 1750 fLastPt = srcPts[1]; 1751 srcPts += 2; 1752 break; 1753 case kCubic_Verb: 1754 pts[0] = this->cons_moveTo(); 1755 memcpy(&pts[1], srcPts, 3 * sizeof(SkPoint)); 1756 fLastPt = srcPts[2]; 1757 srcPts += 3; 1758 break; 1759 case kClose_Verb: 1760 verb = this->autoClose(pts); 1761 if (verb == kLine_Verb) { 1762 fVerbs++; // move back one verb 1763 } else { 1764 fNeedClose = false; 1765 fSegmentState = kEmptyContour_SegmentState; 1766 } 1767 fLastPt = fMoveTo; 1768 break; 1769 } 1770 fPts = srcPts; 1771 return (Verb)verb; 1772 } 1773 1774 /////////////////////////////////////////////////////////////////////////////// 1775 1776 SkPath::RawIter::RawIter() { 1777 #ifdef SK_DEBUG 1778 fPts = NULL; 1779 fConicWeights = NULL; 1780 fMoveTo.fX = fMoveTo.fY = 0; 1781 #endif 1782 // need to init enough to make next() harmlessly return kDone_Verb 1783 fVerbs = NULL; 1784 fVerbStop = NULL; 1785 } 1786 1787 SkPath::RawIter::RawIter(const SkPath& path) { 1788 this->setPath(path); 1789 } 1790 1791 void SkPath::RawIter::setPath(const SkPath& path) { 1792 fPts = path.fPathRef->points(); 1793 fVerbs = path.fPathRef->verbs(); 1794 fVerbStop = path.fPathRef->verbsMemBegin(); 1795 fConicWeights = path.fPathRef->conicWeights() - 1; // begin one behind 1796 fMoveTo.fX = fMoveTo.fY = 0; 1797 } 1798 1799 SkPath::Verb SkPath::RawIter::next(SkPoint pts[4]) { 1800 SkASSERT(pts); 1801 if (fVerbs == fVerbStop) { 1802 return kDone_Verb; 1803 } 1804 1805 // fVerbs points one beyond next verb so decrement first. 1806 unsigned verb = *(--fVerbs); 1807 const SkPoint* srcPts = fPts; 1808 1809 switch (verb) { 1810 case kMove_Verb: 1811 fMoveTo = pts[0] = srcPts[0]; 1812 srcPts += 1; 1813 break; 1814 case kLine_Verb: 1815 pts[0] = srcPts[-1]; 1816 pts[1] = srcPts[0]; 1817 srcPts += 1; 1818 break; 1819 case kConic_Verb: 1820 fConicWeights += 1; 1821 // fall-through 1822 case kQuad_Verb: 1823 pts[0] = srcPts[-1]; 1824 pts[1] = srcPts[0]; 1825 pts[2] = srcPts[1]; 1826 srcPts += 2; 1827 break; 1828 case kCubic_Verb: 1829 pts[0] = srcPts[-1]; 1830 pts[1] = srcPts[0]; 1831 pts[2] = srcPts[1]; 1832 pts[3] = srcPts[2]; 1833 srcPts += 3; 1834 break; 1835 case kClose_Verb: 1836 pts[0] = fMoveTo; 1837 break; 1838 } 1839 fPts = srcPts; 1840 return (Verb)verb; 1841 } 1842 1843 /////////////////////////////////////////////////////////////////////////////// 1844 1845 /* 1846 Format in compressed buffer: [ptCount, verbCount, pts[], verbs[]] 1847 */ 1848 1849 size_t SkPath::writeToMemory(void* storage) const { 1850 SkDEBUGCODE(this->validate();) 1851 1852 if (NULL == storage) { 1853 const int byteCount = sizeof(int32_t) + fPathRef->writeSize(); 1854 return SkAlign4(byteCount); 1855 } 1856 1857 SkWBuffer buffer(storage); 1858 1859 int32_t packed = (fConvexity << kConvexity_SerializationShift) | 1860 (fFillType << kFillType_SerializationShift) | 1861 (fDirection << kDirection_SerializationShift) | 1862 (fIsVolatile << kIsVolatile_SerializationShift); 1863 1864 buffer.write32(packed); 1865 1866 fPathRef->writeToBuffer(&buffer); 1867 1868 buffer.padToAlign4(); 1869 return buffer.pos(); 1870 } 1871 1872 size_t SkPath::readFromMemory(const void* storage, size_t length) { 1873 SkRBufferWithSizeCheck buffer(storage, length); 1874 1875 int32_t packed; 1876 if (!buffer.readS32(&packed)) { 1877 return 0; 1878 } 1879 1880 fConvexity = (packed >> kConvexity_SerializationShift) & 0xFF; 1881 fFillType = (packed >> kFillType_SerializationShift) & 0xFF; 1882 fDirection = (packed >> kDirection_SerializationShift) & 0x3; 1883 fIsVolatile = (packed >> kIsVolatile_SerializationShift) & 0x1; 1884 SkPathRef* pathRef = SkPathRef::CreateFromBuffer(&buffer); 1885 1886 size_t sizeRead = 0; 1887 if (buffer.isValid()) { 1888 fPathRef.reset(pathRef); 1889 SkDEBUGCODE(this->validate();) 1890 buffer.skipToAlign4(); 1891 sizeRead = buffer.pos(); 1892 } else if (pathRef) { 1893 // If the buffer is not valid, pathRef should be NULL 1894 sk_throw(); 1895 } 1896 return sizeRead; 1897 } 1898 1899 /////////////////////////////////////////////////////////////////////////////// 1900 1901 #include "SkStringUtils.h" 1902 #include "SkStream.h" 1903 1904 static void append_params(SkString* str, const char label[], const SkPoint pts[], 1905 int count, SkScalarAsStringType strType, SkScalar conicWeight = -1) { 1906 str->append(label); 1907 str->append("("); 1908 1909 const SkScalar* values = &pts[0].fX; 1910 count *= 2; 1911 1912 for (int i = 0; i < count; ++i) { 1913 SkAppendScalar(str, values[i], strType); 1914 if (i < count - 1) { 1915 str->append(", "); 1916 } 1917 } 1918 if (conicWeight >= 0) { 1919 str->append(", "); 1920 SkAppendScalar(str, conicWeight, strType); 1921 } 1922 str->append(");"); 1923 if (kHex_SkScalarAsStringType == strType) { 1924 str->append(" // "); 1925 for (int i = 0; i < count; ++i) { 1926 SkAppendScalarDec(str, values[i]); 1927 if (i < count - 1) { 1928 str->append(", "); 1929 } 1930 } 1931 if (conicWeight >= 0) { 1932 str->append(", "); 1933 SkAppendScalarDec(str, conicWeight); 1934 } 1935 } 1936 str->append("\n"); 1937 } 1938 1939 void SkPath::dump(SkWStream* wStream, bool forceClose, bool dumpAsHex) const { 1940 SkScalarAsStringType asType = dumpAsHex ? kHex_SkScalarAsStringType : kDec_SkScalarAsStringType; 1941 Iter iter(*this, forceClose); 1942 SkPoint pts[4]; 1943 Verb verb; 1944 1945 if (!wStream) { 1946 SkDebugf("path: forceClose=%s\n", forceClose ? "true" : "false"); 1947 } 1948 SkString builder; 1949 1950 while ((verb = iter.next(pts, false)) != kDone_Verb) { 1951 switch (verb) { 1952 case kMove_Verb: 1953 append_params(&builder, "path.moveTo", &pts[0], 1, asType); 1954 break; 1955 case kLine_Verb: 1956 append_params(&builder, "path.lineTo", &pts[1], 1, asType); 1957 break; 1958 case kQuad_Verb: 1959 append_params(&builder, "path.quadTo", &pts[1], 2, asType); 1960 break; 1961 case kConic_Verb: 1962 append_params(&builder, "path.conicTo", &pts[1], 2, asType, iter.conicWeight()); 1963 break; 1964 case kCubic_Verb: 1965 append_params(&builder, "path.cubicTo", &pts[1], 3, asType); 1966 break; 1967 case kClose_Verb: 1968 builder.append("path.close();\n"); 1969 break; 1970 default: 1971 SkDebugf(" path: UNKNOWN VERB %d, aborting dump...\n", verb); 1972 verb = kDone_Verb; // stop the loop 1973 break; 1974 } 1975 if (!wStream && builder.size()) { 1976 SkDebugf("%s", builder.c_str()); 1977 builder.reset(); 1978 } 1979 } 1980 if (wStream) { 1981 wStream->writeText(builder.c_str()); 1982 } 1983 } 1984 1985 void SkPath::dump() const { 1986 this->dump(NULL, false, false); 1987 } 1988 1989 void SkPath::dumpHex() const { 1990 this->dump(NULL, false, true); 1991 } 1992 1993 #ifdef SK_DEBUG 1994 void SkPath::validate() const { 1995 SkASSERT((fFillType & ~3) == 0); 1996 1997 #ifdef SK_DEBUG_PATH 1998 if (!fBoundsIsDirty) { 1999 SkRect bounds; 2000 2001 bool isFinite = compute_pt_bounds(&bounds, *fPathRef.get()); 2002 SkASSERT(SkToBool(fIsFinite) == isFinite); 2003 2004 if (fPathRef->countPoints() <= 1) { 2005 // if we're empty, fBounds may be empty but translated, so we can't 2006 // necessarily compare to bounds directly 2007 // try path.addOval(2, 2, 2, 2) which is empty, but the bounds will 2008 // be [2, 2, 2, 2] 2009 SkASSERT(bounds.isEmpty()); 2010 SkASSERT(fBounds.isEmpty()); 2011 } else { 2012 if (bounds.isEmpty()) { 2013 SkASSERT(fBounds.isEmpty()); 2014 } else { 2015 if (!fBounds.isEmpty()) { 2016 SkASSERT(fBounds.contains(bounds)); 2017 } 2018 } 2019 } 2020 } 2021 #endif // SK_DEBUG_PATH 2022 } 2023 #endif // SK_DEBUG 2024 2025 /////////////////////////////////////////////////////////////////////////////// 2026 2027 static int sign(SkScalar x) { return x < 0; } 2028 #define kValueNeverReturnedBySign 2 2029 2030 enum DirChange { 2031 kLeft_DirChange, 2032 kRight_DirChange, 2033 kStraight_DirChange, 2034 kBackwards_DirChange, 2035 2036 kInvalid_DirChange 2037 }; 2038 2039 2040 static bool almost_equal(SkScalar compA, SkScalar compB) { 2041 // The error epsilon was empirically derived; worse case round rects 2042 // with a mid point outset by 2x float epsilon in tests had an error 2043 // of 12. 2044 const int epsilon = 16; 2045 if (!SkScalarIsFinite(compA) || !SkScalarIsFinite(compB)) { 2046 return false; 2047 } 2048 // no need to check for small numbers because SkPath::Iter has removed degenerate values 2049 int aBits = SkFloatAs2sCompliment(compA); 2050 int bBits = SkFloatAs2sCompliment(compB); 2051 return aBits < bBits + epsilon && bBits < aBits + epsilon; 2052 } 2053 2054 static bool approximately_zero_when_compared_to(double x, double y) { 2055 return x == 0 || fabs(x) < fabs(y * FLT_EPSILON); 2056 } 2057 2058 2059 // only valid for a single contour 2060 struct Convexicator { 2061 Convexicator() 2062 : fPtCount(0) 2063 , fConvexity(SkPath::kConvex_Convexity) 2064 , fDirection(SkPath::kUnknown_Direction) 2065 , fIsFinite(true) 2066 , fIsCurve(false) { 2067 fExpectedDir = kInvalid_DirChange; 2068 // warnings 2069 fLastPt.set(0, 0); 2070 fCurrPt.set(0, 0); 2071 fLastVec.set(0, 0); 2072 fFirstVec.set(0, 0); 2073 2074 fDx = fDy = 0; 2075 fSx = fSy = kValueNeverReturnedBySign; 2076 } 2077 2078 SkPath::Convexity getConvexity() const { return fConvexity; } 2079 2080 /** The direction returned is only valid if the path is determined convex */ 2081 SkPath::Direction getDirection() const { return fDirection; } 2082 2083 void addPt(const SkPoint& pt) { 2084 if (SkPath::kConcave_Convexity == fConvexity || !fIsFinite) { 2085 return; 2086 } 2087 2088 if (0 == fPtCount) { 2089 fCurrPt = pt; 2090 ++fPtCount; 2091 } else { 2092 SkVector vec = pt - fCurrPt; 2093 SkScalar lengthSqd = vec.lengthSqd(); 2094 if (!SkScalarIsFinite(lengthSqd)) { 2095 fIsFinite = false; 2096 } else if (!SkScalarNearlyZero(lengthSqd, SK_ScalarNearlyZero*SK_ScalarNearlyZero)) { 2097 fPriorPt = fLastPt; 2098 fLastPt = fCurrPt; 2099 fCurrPt = pt; 2100 if (++fPtCount == 2) { 2101 fFirstVec = fLastVec = vec; 2102 } else { 2103 SkASSERT(fPtCount > 2); 2104 this->addVec(vec); 2105 } 2106 2107 int sx = sign(vec.fX); 2108 int sy = sign(vec.fY); 2109 fDx += (sx != fSx); 2110 fDy += (sy != fSy); 2111 fSx = sx; 2112 fSy = sy; 2113 2114 if (fDx > 3 || fDy > 3) { 2115 fConvexity = SkPath::kConcave_Convexity; 2116 } 2117 } 2118 } 2119 } 2120 2121 void close() { 2122 if (fPtCount > 2) { 2123 this->addVec(fFirstVec); 2124 } 2125 } 2126 2127 DirChange directionChange(const SkVector& curVec) { 2128 SkScalar cross = SkPoint::CrossProduct(fLastVec, curVec); 2129 2130 SkScalar smallest = SkTMin(fCurrPt.fX, SkTMin(fCurrPt.fY, SkTMin(fLastPt.fX, fLastPt.fY))); 2131 SkScalar largest = SkTMax(fCurrPt.fX, SkTMax(fCurrPt.fY, SkTMax(fLastPt.fX, fLastPt.fY))); 2132 largest = SkTMax(largest, -smallest); 2133 2134 if (!almost_equal(largest, largest + cross)) { 2135 int sign = SkScalarSignAsInt(cross); 2136 if (sign) { 2137 return (1 == sign) ? kRight_DirChange : kLeft_DirChange; 2138 } 2139 } 2140 2141 if (cross) { 2142 double dLastVecX = SkScalarToDouble(fLastPt.fX) - SkScalarToDouble(fPriorPt.fX); 2143 double dLastVecY = SkScalarToDouble(fLastPt.fY) - SkScalarToDouble(fPriorPt.fY); 2144 double dCurrVecX = SkScalarToDouble(fCurrPt.fX) - SkScalarToDouble(fLastPt.fX); 2145 double dCurrVecY = SkScalarToDouble(fCurrPt.fY) - SkScalarToDouble(fLastPt.fY); 2146 double dCross = dLastVecX * dCurrVecY - dLastVecY * dCurrVecX; 2147 if (!approximately_zero_when_compared_to(dCross, SkScalarToDouble(largest))) { 2148 int sign = SkScalarSignAsInt(SkDoubleToScalar(dCross)); 2149 if (sign) { 2150 return (1 == sign) ? kRight_DirChange : kLeft_DirChange; 2151 } 2152 } 2153 } 2154 2155 if (!SkScalarNearlyZero(fLastVec.lengthSqd(), SK_ScalarNearlyZero*SK_ScalarNearlyZero) && 2156 !SkScalarNearlyZero(curVec.lengthSqd(), SK_ScalarNearlyZero*SK_ScalarNearlyZero) && 2157 fLastVec.dot(curVec) < 0.0f) { 2158 return kBackwards_DirChange; 2159 } 2160 2161 return kStraight_DirChange; 2162 } 2163 2164 2165 bool isFinite() const { 2166 return fIsFinite; 2167 } 2168 2169 void setCurve(bool isCurve) { 2170 fIsCurve = isCurve; 2171 } 2172 2173 private: 2174 void addVec(const SkVector& vec) { 2175 SkASSERT(vec.fX || vec.fY); 2176 DirChange dir = this->directionChange(vec); 2177 switch (dir) { 2178 case kLeft_DirChange: // fall through 2179 case kRight_DirChange: 2180 if (kInvalid_DirChange == fExpectedDir) { 2181 fExpectedDir = dir; 2182 fDirection = (kRight_DirChange == dir) ? SkPath::kCW_Direction 2183 : SkPath::kCCW_Direction; 2184 } else if (dir != fExpectedDir) { 2185 fConvexity = SkPath::kConcave_Convexity; 2186 fDirection = SkPath::kUnknown_Direction; 2187 } 2188 fLastVec = vec; 2189 break; 2190 case kStraight_DirChange: 2191 break; 2192 case kBackwards_DirChange: 2193 if (fIsCurve) { 2194 fConvexity = SkPath::kConcave_Convexity; 2195 fDirection = SkPath::kUnknown_Direction; 2196 } 2197 fLastVec = vec; 2198 break; 2199 case kInvalid_DirChange: 2200 SkFAIL("Use of invalid direction change flag"); 2201 break; 2202 } 2203 } 2204 2205 SkPoint fPriorPt; 2206 SkPoint fLastPt; 2207 SkPoint fCurrPt; 2208 // fLastVec does not necessarily start at fLastPt. We only advance it when the cross product 2209 // value with the current vec is deemed to be of a significant value. 2210 SkVector fLastVec, fFirstVec; 2211 int fPtCount; // non-degenerate points 2212 DirChange fExpectedDir; 2213 SkPath::Convexity fConvexity; 2214 SkPath::Direction fDirection; 2215 int fDx, fDy, fSx, fSy; 2216 bool fIsFinite; 2217 bool fIsCurve; 2218 }; 2219 2220 SkPath::Convexity SkPath::internalGetConvexity() const { 2221 SkASSERT(kUnknown_Convexity == fConvexity); 2222 SkPoint pts[4]; 2223 SkPath::Verb verb; 2224 SkPath::Iter iter(*this, true); 2225 2226 int contourCount = 0; 2227 int count; 2228 Convexicator state; 2229 2230 if (!isFinite()) { 2231 return kUnknown_Convexity; 2232 } 2233 while ((verb = iter.next(pts)) != SkPath::kDone_Verb) { 2234 switch (verb) { 2235 case kMove_Verb: 2236 if (++contourCount > 1) { 2237 fConvexity = kConcave_Convexity; 2238 return kConcave_Convexity; 2239 } 2240 pts[1] = pts[0]; 2241 // fall through 2242 case kLine_Verb: 2243 count = 1; 2244 state.setCurve(false); 2245 break; 2246 case kQuad_Verb: 2247 // fall through 2248 case kConic_Verb: 2249 // fall through 2250 case kCubic_Verb: 2251 count = 2 + (kCubic_Verb == verb); 2252 // As an additional enhancement, this could set curve true only 2253 // if the curve is nonlinear 2254 state.setCurve(true); 2255 break; 2256 case kClose_Verb: 2257 state.setCurve(false); 2258 state.close(); 2259 count = 0; 2260 break; 2261 default: 2262 SkDEBUGFAIL("bad verb"); 2263 fConvexity = kConcave_Convexity; 2264 return kConcave_Convexity; 2265 } 2266 2267 for (int i = 1; i <= count; i++) { 2268 state.addPt(pts[i]); 2269 } 2270 // early exit 2271 if (!state.isFinite()) { 2272 return kUnknown_Convexity; 2273 } 2274 if (kConcave_Convexity == state.getConvexity()) { 2275 fConvexity = kConcave_Convexity; 2276 return kConcave_Convexity; 2277 } 2278 } 2279 fConvexity = state.getConvexity(); 2280 if (kConvex_Convexity == fConvexity && kUnknown_Direction == fDirection) { 2281 fDirection = state.getDirection(); 2282 } 2283 return static_cast<Convexity>(fConvexity); 2284 } 2285 2286 /////////////////////////////////////////////////////////////////////////////// 2287 2288 class ContourIter { 2289 public: 2290 ContourIter(const SkPathRef& pathRef); 2291 2292 bool done() const { return fDone; } 2293 // if !done() then these may be called 2294 int count() const { return fCurrPtCount; } 2295 const SkPoint* pts() const { return fCurrPt; } 2296 void next(); 2297 2298 private: 2299 int fCurrPtCount; 2300 const SkPoint* fCurrPt; 2301 const uint8_t* fCurrVerb; 2302 const uint8_t* fStopVerbs; 2303 const SkScalar* fCurrConicWeight; 2304 bool fDone; 2305 SkDEBUGCODE(int fContourCounter;) 2306 }; 2307 2308 ContourIter::ContourIter(const SkPathRef& pathRef) { 2309 fStopVerbs = pathRef.verbsMemBegin(); 2310 fDone = false; 2311 fCurrPt = pathRef.points(); 2312 fCurrVerb = pathRef.verbs(); 2313 fCurrConicWeight = pathRef.conicWeights(); 2314 fCurrPtCount = 0; 2315 SkDEBUGCODE(fContourCounter = 0;) 2316 this->next(); 2317 } 2318 2319 void ContourIter::next() { 2320 if (fCurrVerb <= fStopVerbs) { 2321 fDone = true; 2322 } 2323 if (fDone) { 2324 return; 2325 } 2326 2327 // skip pts of prev contour 2328 fCurrPt += fCurrPtCount; 2329 2330 SkASSERT(SkPath::kMove_Verb == fCurrVerb[~0]); 2331 int ptCount = 1; // moveTo 2332 const uint8_t* verbs = fCurrVerb; 2333 2334 for (--verbs; verbs > fStopVerbs; --verbs) { 2335 switch (verbs[~0]) { 2336 case SkPath::kMove_Verb: 2337 goto CONTOUR_END; 2338 case SkPath::kLine_Verb: 2339 ptCount += 1; 2340 break; 2341 case SkPath::kConic_Verb: 2342 fCurrConicWeight += 1; 2343 // fall-through 2344 case SkPath::kQuad_Verb: 2345 ptCount += 2; 2346 break; 2347 case SkPath::kCubic_Verb: 2348 ptCount += 3; 2349 break; 2350 case SkPath::kClose_Verb: 2351 break; 2352 default: 2353 SkDEBUGFAIL("unexpected verb"); 2354 break; 2355 } 2356 } 2357 CONTOUR_END: 2358 fCurrPtCount = ptCount; 2359 fCurrVerb = verbs; 2360 SkDEBUGCODE(++fContourCounter;) 2361 } 2362 2363 // returns cross product of (p1 - p0) and (p2 - p0) 2364 static SkScalar cross_prod(const SkPoint& p0, const SkPoint& p1, const SkPoint& p2) { 2365 SkScalar cross = SkPoint::CrossProduct(p1 - p0, p2 - p0); 2366 // We may get 0 when the above subtracts underflow. We expect this to be 2367 // very rare and lazily promote to double. 2368 if (0 == cross) { 2369 double p0x = SkScalarToDouble(p0.fX); 2370 double p0y = SkScalarToDouble(p0.fY); 2371 2372 double p1x = SkScalarToDouble(p1.fX); 2373 double p1y = SkScalarToDouble(p1.fY); 2374 2375 double p2x = SkScalarToDouble(p2.fX); 2376 double p2y = SkScalarToDouble(p2.fY); 2377 2378 cross = SkDoubleToScalar((p1x - p0x) * (p2y - p0y) - 2379 (p1y - p0y) * (p2x - p0x)); 2380 2381 } 2382 return cross; 2383 } 2384 2385 // Returns the first pt with the maximum Y coordinate 2386 static int find_max_y(const SkPoint pts[], int count) { 2387 SkASSERT(count > 0); 2388 SkScalar max = pts[0].fY; 2389 int firstIndex = 0; 2390 for (int i = 1; i < count; ++i) { 2391 SkScalar y = pts[i].fY; 2392 if (y > max) { 2393 max = y; 2394 firstIndex = i; 2395 } 2396 } 2397 return firstIndex; 2398 } 2399 2400 static int find_diff_pt(const SkPoint pts[], int index, int n, int inc) { 2401 int i = index; 2402 for (;;) { 2403 i = (i + inc) % n; 2404 if (i == index) { // we wrapped around, so abort 2405 break; 2406 } 2407 if (pts[index] != pts[i]) { // found a different point, success! 2408 break; 2409 } 2410 } 2411 return i; 2412 } 2413 2414 /** 2415 * Starting at index, and moving forward (incrementing), find the xmin and 2416 * xmax of the contiguous points that have the same Y. 2417 */ 2418 static int find_min_max_x_at_y(const SkPoint pts[], int index, int n, 2419 int* maxIndexPtr) { 2420 const SkScalar y = pts[index].fY; 2421 SkScalar min = pts[index].fX; 2422 SkScalar max = min; 2423 int minIndex = index; 2424 int maxIndex = index; 2425 for (int i = index + 1; i < n; ++i) { 2426 if (pts[i].fY != y) { 2427 break; 2428 } 2429 SkScalar x = pts[i].fX; 2430 if (x < min) { 2431 min = x; 2432 minIndex = i; 2433 } else if (x > max) { 2434 max = x; 2435 maxIndex = i; 2436 } 2437 } 2438 *maxIndexPtr = maxIndex; 2439 return minIndex; 2440 } 2441 2442 static void crossToDir(SkScalar cross, SkPath::Direction* dir) { 2443 *dir = cross > 0 ? SkPath::kCW_Direction : SkPath::kCCW_Direction; 2444 } 2445 2446 /* 2447 * We loop through all contours, and keep the computed cross-product of the 2448 * contour that contained the global y-max. If we just look at the first 2449 * contour, we may find one that is wound the opposite way (correctly) since 2450 * it is the interior of a hole (e.g. 'o'). Thus we must find the contour 2451 * that is outer most (or at least has the global y-max) before we can consider 2452 * its cross product. 2453 */ 2454 bool SkPath::cheapComputeDirection(Direction* dir) const { 2455 if (kUnknown_Direction != fDirection) { 2456 *dir = static_cast<Direction>(fDirection); 2457 return true; 2458 } 2459 2460 // don't want to pay the cost for computing this if it 2461 // is unknown, so we don't call isConvex() 2462 if (kConvex_Convexity == this->getConvexityOrUnknown()) { 2463 SkASSERT(kUnknown_Direction == fDirection); 2464 *dir = static_cast<Direction>(fDirection); 2465 return false; 2466 } 2467 2468 ContourIter iter(*fPathRef.get()); 2469 2470 // initialize with our logical y-min 2471 SkScalar ymax = this->getBounds().fTop; 2472 SkScalar ymaxCross = 0; 2473 2474 for (; !iter.done(); iter.next()) { 2475 int n = iter.count(); 2476 if (n < 3) { 2477 continue; 2478 } 2479 2480 const SkPoint* pts = iter.pts(); 2481 SkScalar cross = 0; 2482 int index = find_max_y(pts, n); 2483 if (pts[index].fY < ymax) { 2484 continue; 2485 } 2486 2487 // If there is more than 1 distinct point at the y-max, we take the 2488 // x-min and x-max of them and just subtract to compute the dir. 2489 if (pts[(index + 1) % n].fY == pts[index].fY) { 2490 int maxIndex; 2491 int minIndex = find_min_max_x_at_y(pts, index, n, &maxIndex); 2492 if (minIndex == maxIndex) { 2493 goto TRY_CROSSPROD; 2494 } 2495 SkASSERT(pts[minIndex].fY == pts[index].fY); 2496 SkASSERT(pts[maxIndex].fY == pts[index].fY); 2497 SkASSERT(pts[minIndex].fX <= pts[maxIndex].fX); 2498 // we just subtract the indices, and let that auto-convert to 2499 // SkScalar, since we just want - or + to signal the direction. 2500 cross = minIndex - maxIndex; 2501 } else { 2502 TRY_CROSSPROD: 2503 // Find a next and prev index to use for the cross-product test, 2504 // but we try to find pts that form non-zero vectors from pts[index] 2505 // 2506 // Its possible that we can't find two non-degenerate vectors, so 2507 // we have to guard our search (e.g. all the pts could be in the 2508 // same place). 2509 2510 // we pass n - 1 instead of -1 so we don't foul up % operator by 2511 // passing it a negative LH argument. 2512 int prev = find_diff_pt(pts, index, n, n - 1); 2513 if (prev == index) { 2514 // completely degenerate, skip to next contour 2515 continue; 2516 } 2517 int next = find_diff_pt(pts, index, n, 1); 2518 SkASSERT(next != index); 2519 cross = cross_prod(pts[prev], pts[index], pts[next]); 2520 // if we get a zero and the points are horizontal, then we look at the spread in 2521 // x-direction. We really should continue to walk away from the degeneracy until 2522 // there is a divergence. 2523 if (0 == cross && pts[prev].fY == pts[index].fY && pts[next].fY == pts[index].fY) { 2524 // construct the subtract so we get the correct Direction below 2525 cross = pts[index].fX - pts[next].fX; 2526 } 2527 } 2528 2529 if (cross) { 2530 // record our best guess so far 2531 ymax = pts[index].fY; 2532 ymaxCross = cross; 2533 } 2534 } 2535 if (ymaxCross) { 2536 crossToDir(ymaxCross, dir); 2537 fDirection = *dir; 2538 return true; 2539 } else { 2540 return false; 2541 } 2542 } 2543 2544 /////////////////////////////////////////////////////////////////////////////// 2545 2546 static SkScalar eval_cubic_coeff(SkScalar A, SkScalar B, SkScalar C, 2547 SkScalar D, SkScalar t) { 2548 return SkScalarMulAdd(SkScalarMulAdd(SkScalarMulAdd(A, t, B), t, C), t, D); 2549 } 2550 2551 static SkScalar eval_cubic_pts(SkScalar c0, SkScalar c1, SkScalar c2, SkScalar c3, 2552 SkScalar t) { 2553 SkScalar A = c3 + 3*(c1 - c2) - c0; 2554 SkScalar B = 3*(c2 - c1 - c1 + c0); 2555 SkScalar C = 3*(c1 - c0); 2556 SkScalar D = c0; 2557 return eval_cubic_coeff(A, B, C, D, t); 2558 } 2559 2560 /* Given 4 cubic points (either Xs or Ys), and a target X or Y, compute the 2561 t value such that cubic(t) = target 2562 */ 2563 static void chopMonoCubicAt(SkScalar c0, SkScalar c1, SkScalar c2, SkScalar c3, 2564 SkScalar target, SkScalar* t) { 2565 // SkASSERT(c0 <= c1 && c1 <= c2 && c2 <= c3); 2566 SkASSERT(c0 < target && target < c3); 2567 2568 SkScalar D = c0 - target; 2569 SkScalar A = c3 + 3*(c1 - c2) - c0; 2570 SkScalar B = 3*(c2 - c1 - c1 + c0); 2571 SkScalar C = 3*(c1 - c0); 2572 2573 const SkScalar TOLERANCE = SK_Scalar1 / 4096; 2574 SkScalar minT = 0; 2575 SkScalar maxT = SK_Scalar1; 2576 SkScalar mid; 2577 int i; 2578 for (i = 0; i < 16; i++) { 2579 mid = SkScalarAve(minT, maxT); 2580 SkScalar delta = eval_cubic_coeff(A, B, C, D, mid); 2581 if (delta < 0) { 2582 minT = mid; 2583 delta = -delta; 2584 } else { 2585 maxT = mid; 2586 } 2587 if (delta < TOLERANCE) { 2588 break; 2589 } 2590 } 2591 *t = mid; 2592 } 2593 2594 template <size_t N> static void find_minmax(const SkPoint pts[], 2595 SkScalar* minPtr, SkScalar* maxPtr) { 2596 SkScalar min, max; 2597 min = max = pts[0].fX; 2598 for (size_t i = 1; i < N; ++i) { 2599 min = SkMinScalar(min, pts[i].fX); 2600 max = SkMaxScalar(max, pts[i].fX); 2601 } 2602 *minPtr = min; 2603 *maxPtr = max; 2604 } 2605 2606 static int winding_mono_cubic(const SkPoint pts[], SkScalar x, SkScalar y) { 2607 SkPoint storage[4]; 2608 2609 int dir = 1; 2610 if (pts[0].fY > pts[3].fY) { 2611 storage[0] = pts[3]; 2612 storage[1] = pts[2]; 2613 storage[2] = pts[1]; 2614 storage[3] = pts[0]; 2615 pts = storage; 2616 dir = -1; 2617 } 2618 if (y < pts[0].fY || y >= pts[3].fY) { 2619 return 0; 2620 } 2621 2622 // quickreject or quickaccept 2623 SkScalar min, max; 2624 find_minmax<4>(pts, &min, &max); 2625 if (x < min) { 2626 return 0; 2627 } 2628 if (x > max) { 2629 return dir; 2630 } 2631 2632 // compute the actual x(t) value 2633 SkScalar t; 2634 chopMonoCubicAt(pts[0].fY, pts[1].fY, pts[2].fY, pts[3].fY, y, &t); 2635 SkScalar xt = eval_cubic_pts(pts[0].fX, pts[1].fX, pts[2].fX, pts[3].fX, t); 2636 return xt < x ? dir : 0; 2637 } 2638 2639 static int winding_cubic(const SkPoint pts[], SkScalar x, SkScalar y) { 2640 SkPoint dst[10]; 2641 int n = SkChopCubicAtYExtrema(pts, dst); 2642 int w = 0; 2643 for (int i = 0; i <= n; ++i) { 2644 w += winding_mono_cubic(&dst[i * 3], x, y); 2645 } 2646 return w; 2647 } 2648 2649 static int winding_mono_quad(const SkPoint pts[], SkScalar x, SkScalar y) { 2650 SkScalar y0 = pts[0].fY; 2651 SkScalar y2 = pts[2].fY; 2652 2653 int dir = 1; 2654 if (y0 > y2) { 2655 SkTSwap(y0, y2); 2656 dir = -1; 2657 } 2658 if (y < y0 || y >= y2) { 2659 return 0; 2660 } 2661 2662 // bounds check on X (not required. is it faster?) 2663 #if 0 2664 if (pts[0].fX > x && pts[1].fX > x && pts[2].fX > x) { 2665 return 0; 2666 } 2667 #endif 2668 2669 SkScalar roots[2]; 2670 int n = SkFindUnitQuadRoots(pts[0].fY - 2 * pts[1].fY + pts[2].fY, 2671 2 * (pts[1].fY - pts[0].fY), 2672 pts[0].fY - y, 2673 roots); 2674 SkASSERT(n <= 1); 2675 SkScalar xt; 2676 if (0 == n) { 2677 SkScalar mid = SkScalarAve(y0, y2); 2678 // Need [0] and [2] if dir == 1 2679 // and [2] and [0] if dir == -1 2680 xt = y < mid ? pts[1 - dir].fX : pts[dir - 1].fX; 2681 } else { 2682 SkScalar t = roots[0]; 2683 SkScalar C = pts[0].fX; 2684 SkScalar A = pts[2].fX - 2 * pts[1].fX + C; 2685 SkScalar B = 2 * (pts[1].fX - C); 2686 xt = SkScalarMulAdd(SkScalarMulAdd(A, t, B), t, C); 2687 } 2688 return xt < x ? dir : 0; 2689 } 2690 2691 static bool is_mono_quad(SkScalar y0, SkScalar y1, SkScalar y2) { 2692 // return SkScalarSignAsInt(y0 - y1) + SkScalarSignAsInt(y1 - y2) != 0; 2693 if (y0 == y1) { 2694 return true; 2695 } 2696 if (y0 < y1) { 2697 return y1 <= y2; 2698 } else { 2699 return y1 >= y2; 2700 } 2701 } 2702 2703 static int winding_quad(const SkPoint pts[], SkScalar x, SkScalar y) { 2704 SkPoint dst[5]; 2705 int n = 0; 2706 2707 if (!is_mono_quad(pts[0].fY, pts[1].fY, pts[2].fY)) { 2708 n = SkChopQuadAtYExtrema(pts, dst); 2709 pts = dst; 2710 } 2711 int w = winding_mono_quad(pts, x, y); 2712 if (n > 0) { 2713 w += winding_mono_quad(&pts[2], x, y); 2714 } 2715 return w; 2716 } 2717 2718 static int winding_line(const SkPoint pts[], SkScalar x, SkScalar y) { 2719 SkScalar x0 = pts[0].fX; 2720 SkScalar y0 = pts[0].fY; 2721 SkScalar x1 = pts[1].fX; 2722 SkScalar y1 = pts[1].fY; 2723 2724 SkScalar dy = y1 - y0; 2725 2726 int dir = 1; 2727 if (y0 > y1) { 2728 SkTSwap(y0, y1); 2729 dir = -1; 2730 } 2731 if (y < y0 || y >= y1) { 2732 return 0; 2733 } 2734 2735 SkScalar cross = SkScalarMul(x1 - x0, y - pts[0].fY) - 2736 SkScalarMul(dy, x - pts[0].fX); 2737 2738 if (SkScalarSignAsInt(cross) == dir) { 2739 dir = 0; 2740 } 2741 return dir; 2742 } 2743 2744 static bool contains_inclusive(const SkRect& r, SkScalar x, SkScalar y) { 2745 return r.fLeft <= x && x <= r.fRight && r.fTop <= y && y <= r.fBottom; 2746 } 2747 2748 bool SkPath::contains(SkScalar x, SkScalar y) const { 2749 bool isInverse = this->isInverseFillType(); 2750 if (this->isEmpty()) { 2751 return isInverse; 2752 } 2753 2754 if (!contains_inclusive(this->getBounds(), x, y)) { 2755 return isInverse; 2756 } 2757 2758 SkPath::Iter iter(*this, true); 2759 bool done = false; 2760 int w = 0; 2761 do { 2762 SkPoint pts[4]; 2763 switch (iter.next(pts, false)) { 2764 case SkPath::kMove_Verb: 2765 case SkPath::kClose_Verb: 2766 break; 2767 case SkPath::kLine_Verb: 2768 w += winding_line(pts, x, y); 2769 break; 2770 case SkPath::kQuad_Verb: 2771 w += winding_quad(pts, x, y); 2772 break; 2773 case SkPath::kConic_Verb: 2774 SkASSERT(0); 2775 break; 2776 case SkPath::kCubic_Verb: 2777 w += winding_cubic(pts, x, y); 2778 break; 2779 case SkPath::kDone_Verb: 2780 done = true; 2781 break; 2782 } 2783 } while (!done); 2784 2785 switch (this->getFillType()) { 2786 case SkPath::kEvenOdd_FillType: 2787 case SkPath::kInverseEvenOdd_FillType: 2788 w &= 1; 2789 break; 2790 default: 2791 break; 2792 } 2793 return SkToBool(w); 2794 } 2795