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