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