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