SkPath.cpp revision b8de1f46594c3cd9c537f0b128c6d6eb30a9f463
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 937/** 938 * If this returns 0, then the caller should just line-to the singlePt, else it should 939 * ignore singlePt and append the specified number of conics. 940 */ 941static int build_arc_conics(const SkRect& oval, const SkVector& start, const SkVector& stop, 942 SkRotationDirection dir, SkConic conics[SkConic::kMaxConicsForArc], 943 SkPoint* singlePt) { 944 SkMatrix matrix; 945 946 matrix.setScale(SkScalarHalf(oval.width()), SkScalarHalf(oval.height())); 947 matrix.postTranslate(oval.centerX(), oval.centerY()); 948 949 int count = SkConic::BuildUnitArc(start, stop, dir, &matrix, conics); 950 if (0 == count) { 951 matrix.mapXY(start.x(), start.y(), singlePt); 952 } 953 return count; 954} 955#endif 956 957void SkPath::addRoundRect(const SkRect& rect, const SkScalar radii[], 958 Direction dir) { 959 SkRRect rrect; 960 rrect.setRectRadii(rect, (const SkVector*) radii); 961 this->addRRect(rrect, dir); 962} 963 964void SkPath::addRRect(const SkRRect& rrect, Direction dir) { 965 assert_known_direction(dir); 966 967 if (rrect.isEmpty()) { 968 return; 969 } 970 971 const SkRect& bounds = rrect.getBounds(); 972 973 if (rrect.isRect()) { 974 this->addRect(bounds, dir); 975 } else if (rrect.isOval()) { 976 this->addOval(bounds, dir); 977 } else { 978 fDirection = this->hasOnlyMoveTos() ? dir : kUnknown_Direction; 979 980 SkAutoPathBoundsUpdate apbu(this, bounds); 981 SkAutoDisableDirectionCheck addc(this); 982 983 const SkScalar L = bounds.fLeft; 984 const SkScalar T = bounds.fTop; 985 const SkScalar R = bounds.fRight; 986 const SkScalar B = bounds.fBottom; 987 const SkScalar W = SK_ScalarRoot2Over2; 988 989 this->incReserve(13); 990 if (kCW_Direction == dir) { 991 this->moveTo(L, B - rrect.fRadii[SkRRect::kLowerLeft_Corner].fY); 992 993 this->lineTo(L, T + rrect.fRadii[SkRRect::kUpperLeft_Corner].fY); 994 this->conicTo(L, T, L + rrect.fRadii[SkRRect::kUpperLeft_Corner].fX, T, W); 995 996 this->lineTo(R - rrect.fRadii[SkRRect::kUpperRight_Corner].fX, T); 997 this->conicTo(R, T, R, T + rrect.fRadii[SkRRect::kUpperRight_Corner].fY, W); 998 999 this->lineTo(R, B - rrect.fRadii[SkRRect::kLowerRight_Corner].fY); 1000 this->conicTo(R, B, R - rrect.fRadii[SkRRect::kLowerRight_Corner].fX, B, W); 1001 1002 this->lineTo(L + rrect.fRadii[SkRRect::kLowerLeft_Corner].fX, B); 1003 this->conicTo(L, B, L, B - rrect.fRadii[SkRRect::kLowerLeft_Corner].fY, W); 1004 } else { 1005 this->moveTo(L, T + rrect.fRadii[SkRRect::kUpperLeft_Corner].fY); 1006 1007 this->lineTo(L, B - rrect.fRadii[SkRRect::kLowerLeft_Corner].fY); 1008 this->conicTo(L, B, L + rrect.fRadii[SkRRect::kLowerLeft_Corner].fX, B, W); 1009 1010 this->lineTo(R - rrect.fRadii[SkRRect::kLowerRight_Corner].fX, B); 1011 this->conicTo(R, B, R, B - rrect.fRadii[SkRRect::kLowerRight_Corner].fY, W); 1012 1013 this->lineTo(R, T + rrect.fRadii[SkRRect::kUpperRight_Corner].fY); 1014 this->conicTo(R, T, R - rrect.fRadii[SkRRect::kUpperRight_Corner].fX, T, W); 1015 1016 this->lineTo(L + rrect.fRadii[SkRRect::kUpperLeft_Corner].fX, T); 1017 this->conicTo(L, T, L, T + rrect.fRadii[SkRRect::kUpperLeft_Corner].fY, W); 1018 } 1019 this->close(); 1020 } 1021 SkDEBUGCODE(fPathRef->validate();) 1022} 1023 1024bool SkPath::hasOnlyMoveTos() const { 1025 int count = fPathRef->countVerbs(); 1026 const uint8_t* verbs = const_cast<const SkPathRef*>(fPathRef.get())->verbsMemBegin(); 1027 for (int i = 0; i < count; ++i) { 1028 if (*verbs == kLine_Verb || 1029 *verbs == kQuad_Verb || 1030 *verbs == kConic_Verb || 1031 *verbs == kCubic_Verb) { 1032 return false; 1033 } 1034 ++verbs; 1035 } 1036 return true; 1037} 1038 1039void SkPath::addRoundRect(const SkRect& rect, SkScalar rx, SkScalar ry, 1040 Direction dir) { 1041 assert_known_direction(dir); 1042 1043 if (rx < 0 || ry < 0) { 1044 SkErrorInternals::SetError( kInvalidArgument_SkError, 1045 "I got %f and %f as radii to SkPath::AddRoundRect, " 1046 "but negative radii are not allowed.", 1047 SkScalarToDouble(rx), SkScalarToDouble(ry) ); 1048 return; 1049 } 1050 1051 SkRRect rrect; 1052 rrect.setRectXY(rect, rx, ry); 1053 this->addRRect(rrect, dir); 1054} 1055 1056void SkPath::addOval(const SkRect& oval, Direction dir) { 1057 assert_known_direction(dir); 1058 1059 /* If addOval() is called after previous moveTo(), 1060 this path is still marked as an oval. This is used to 1061 fit into WebKit's calling sequences. 1062 We can't simply check isEmpty() in this case, as additional 1063 moveTo() would mark the path non empty. 1064 */ 1065 bool isOval = hasOnlyMoveTos(); 1066 if (isOval) { 1067 fDirection = dir; 1068 } else { 1069 fDirection = kUnknown_Direction; 1070 } 1071 1072 SkAutoDisableDirectionCheck addc(this); 1073 1074 SkAutoPathBoundsUpdate apbu(this, oval); 1075 1076#ifdef SK_SUPPORT_LEGACY_ADDOVAL 1077 SkScalar cx = oval.centerX(); 1078 SkScalar cy = oval.centerY(); 1079 SkScalar rx = SkScalarHalf(oval.width()); 1080 SkScalar ry = SkScalarHalf(oval.height()); 1081 1082 SkScalar sx = SkScalarMul(rx, SK_ScalarTanPIOver8); 1083 SkScalar sy = SkScalarMul(ry, SK_ScalarTanPIOver8); 1084 SkScalar mx = SkScalarMul(rx, SK_ScalarRoot2Over2); 1085 SkScalar my = SkScalarMul(ry, SK_ScalarRoot2Over2); 1086 1087 /* 1088 To handle imprecision in computing the center and radii, we revert to 1089 the provided bounds when we can (i.e. use oval.fLeft instead of cx-rx) 1090 to ensure that we don't exceed the oval's bounds *ever*, since we want 1091 to use oval for our fast-bounds, rather than have to recompute it. 1092 */ 1093 const SkScalar L = oval.fLeft; // cx - rx 1094 const SkScalar T = oval.fTop; // cy - ry 1095 const SkScalar R = oval.fRight; // cx + rx 1096 const SkScalar B = oval.fBottom; // cy + ry 1097 1098 this->incReserve(17); // 8 quads + close 1099 this->moveTo(R, cy); 1100 if (dir == kCCW_Direction) { 1101 this->quadTo( R, cy - sy, cx + mx, cy - my); 1102 this->quadTo(cx + sx, T, cx , T); 1103 this->quadTo(cx - sx, T, cx - mx, cy - my); 1104 this->quadTo( L, cy - sy, L, cy ); 1105 this->quadTo( L, cy + sy, cx - mx, cy + my); 1106 this->quadTo(cx - sx, B, cx , B); 1107 this->quadTo(cx + sx, B, cx + mx, cy + my); 1108 this->quadTo( R, cy + sy, R, cy ); 1109 } else { 1110 this->quadTo( R, cy + sy, cx + mx, cy + my); 1111 this->quadTo(cx + sx, B, cx , B); 1112 this->quadTo(cx - sx, B, cx - mx, cy + my); 1113 this->quadTo( L, cy + sy, L, cy ); 1114 this->quadTo( L, cy - sy, cx - mx, cy - my); 1115 this->quadTo(cx - sx, T, cx , T); 1116 this->quadTo(cx + sx, T, cx + mx, cy - my); 1117 this->quadTo( R, cy - sy, R, cy ); 1118 } 1119#else 1120 const SkScalar L = oval.fLeft; 1121 const SkScalar T = oval.fTop; 1122 const SkScalar R = oval.fRight; 1123 const SkScalar B = oval.fBottom; 1124 const SkScalar cx = oval.centerX(); 1125 const SkScalar cy = oval.centerY(); 1126 const SkScalar weight = SK_ScalarRoot2Over2; 1127 1128 this->incReserve(9); // move + 4 conics 1129 this->moveTo(R, cy); 1130 if (dir == kCCW_Direction) { 1131 this->conicTo(R, T, cx, T, weight); 1132 this->conicTo(L, T, L, cy, weight); 1133 this->conicTo(L, B, cx, B, weight); 1134 this->conicTo(R, B, R, cy, weight); 1135 } else { 1136 this->conicTo(R, B, cx, B, weight); 1137 this->conicTo(L, B, L, cy, weight); 1138 this->conicTo(L, T, cx, T, weight); 1139 this->conicTo(R, T, R, cy, weight); 1140 } 1141#endif 1142 this->close(); 1143 1144 SkPathRef::Editor ed(&fPathRef); 1145 1146 ed.setIsOval(isOval); 1147} 1148 1149void SkPath::addCircle(SkScalar x, SkScalar y, SkScalar r, Direction dir) { 1150 if (r > 0) { 1151 SkRect rect; 1152 rect.set(x - r, y - r, x + r, y + r); 1153 this->addOval(rect, dir); 1154 } 1155} 1156 1157void SkPath::arcTo(const SkRect& oval, SkScalar startAngle, SkScalar sweepAngle, 1158 bool forceMoveTo) { 1159 if (oval.width() < 0 || oval.height() < 0) { 1160 return; 1161 } 1162 1163 if (fPathRef->countVerbs() == 0) { 1164 forceMoveTo = true; 1165 } 1166 1167 SkPoint lonePt; 1168 if (arc_is_lone_point(oval, startAngle, sweepAngle, &lonePt)) { 1169 forceMoveTo ? this->moveTo(lonePt) : this->lineTo(lonePt); 1170 return; 1171 } 1172 1173 SkVector startV, stopV; 1174 SkRotationDirection dir; 1175 angles_to_unit_vectors(startAngle, sweepAngle, &startV, &stopV, &dir); 1176 1177#ifdef SK_SUPPORT_LEGACY_ARCTO_QUADS 1178 SkPoint pts[kSkBuildQuadArcStorage]; 1179 int count = build_arc_points(oval, startV, stopV, dir, pts); 1180 SkASSERT((count & 1) == 1); 1181 1182 this->incReserve(count); 1183 forceMoveTo ? this->moveTo(pts[0]) : this->lineTo(pts[0]); 1184 for (int i = 1; i < count; i += 2) { 1185 this->quadTo(pts[i], pts[i+1]); 1186 } 1187#else 1188 SkPoint singlePt; 1189 SkConic conics[SkConic::kMaxConicsForArc]; 1190 int count = build_arc_conics(oval, startV, stopV, dir, conics, &singlePt); 1191 if (count) { 1192 this->incReserve(count * 2 + 1); 1193 const SkPoint& pt = conics[0].fPts[0]; 1194 forceMoveTo ? this->moveTo(pt) : this->lineTo(pt); 1195 for (int i = 0; i < count; ++i) { 1196 this->conicTo(conics[i].fPts[1], conics[i].fPts[2], conics[i].fW); 1197 } 1198 } else { 1199 forceMoveTo ? this->moveTo(singlePt) : this->lineTo(singlePt); 1200 } 1201#endif 1202} 1203 1204void SkPath::addArc(const SkRect& oval, SkScalar startAngle, SkScalar sweepAngle) { 1205 if (oval.isEmpty() || 0 == sweepAngle) { 1206 return; 1207 } 1208 1209 const SkScalar kFullCircleAngle = SkIntToScalar(360); 1210 1211 if (sweepAngle >= kFullCircleAngle || sweepAngle <= -kFullCircleAngle) { 1212 this->addOval(oval, sweepAngle > 0 ? kCW_Direction : kCCW_Direction); 1213 } else { 1214 this->arcTo(oval, startAngle, sweepAngle, true); 1215 } 1216} 1217 1218/* 1219 Need to handle the case when the angle is sharp, and our computed end-points 1220 for the arc go behind pt1 and/or p2... 1221*/ 1222void SkPath::arcTo(SkScalar x1, SkScalar y1, SkScalar x2, SkScalar y2, SkScalar radius) { 1223 if (radius == 0) { 1224 this->lineTo(x1, y1); 1225 return; 1226 } 1227 1228 SkVector before, after; 1229 1230 // need to know our prev pt so we can construct tangent vectors 1231 { 1232 SkPoint start; 1233 this->getLastPt(&start); 1234 // Handle degenerate cases by adding a line to the first point and 1235 // bailing out. 1236 before.setNormalize(x1 - start.fX, y1 - start.fY); 1237 after.setNormalize(x2 - x1, y2 - y1); 1238 } 1239 1240 SkScalar cosh = SkPoint::DotProduct(before, after); 1241 SkScalar sinh = SkPoint::CrossProduct(before, after); 1242 1243 if (SkScalarNearlyZero(sinh)) { // angle is too tight 1244 this->lineTo(x1, y1); 1245 return; 1246 } 1247 1248 SkScalar dist = SkScalarMulDiv(radius, SK_Scalar1 - cosh, sinh); 1249 if (dist < 0) { 1250 dist = -dist; 1251 } 1252 1253 SkScalar xx = x1 - SkScalarMul(dist, before.fX); 1254 SkScalar yy = y1 - SkScalarMul(dist, before.fY); 1255 SkRotationDirection arcDir; 1256 1257 // now turn before/after into normals 1258 if (sinh > 0) { 1259 before.rotateCCW(); 1260 after.rotateCCW(); 1261 arcDir = kCW_SkRotationDirection; 1262 } else { 1263 before.rotateCW(); 1264 after.rotateCW(); 1265 arcDir = kCCW_SkRotationDirection; 1266 } 1267 1268 SkMatrix matrix; 1269 SkPoint pts[kSkBuildQuadArcStorage]; 1270 1271 matrix.setScale(radius, radius); 1272 matrix.postTranslate(xx - SkScalarMul(radius, before.fX), 1273 yy - SkScalarMul(radius, before.fY)); 1274 1275 int count = SkBuildQuadArc(before, after, arcDir, &matrix, pts); 1276 1277 this->incReserve(count); 1278 // [xx,yy] == pts[0] 1279 this->lineTo(xx, yy); 1280 for (int i = 1; i < count; i += 2) { 1281 this->quadTo(pts[i], pts[i+1]); 1282 } 1283} 1284 1285/////////////////////////////////////////////////////////////////////////////// 1286 1287void SkPath::addPath(const SkPath& path, SkScalar dx, SkScalar dy, AddPathMode mode) { 1288 SkMatrix matrix; 1289 1290 matrix.setTranslate(dx, dy); 1291 this->addPath(path, matrix, mode); 1292} 1293 1294void SkPath::addPath(const SkPath& path, const SkMatrix& matrix, AddPathMode mode) { 1295 SkPathRef::Editor(&fPathRef, path.countVerbs(), path.countPoints()); 1296 1297 RawIter iter(path); 1298 SkPoint pts[4]; 1299 Verb verb; 1300 1301 SkMatrix::MapPtsProc proc = matrix.getMapPtsProc(); 1302 bool firstVerb = true; 1303 while ((verb = iter.next(pts)) != kDone_Verb) { 1304 switch (verb) { 1305 case kMove_Verb: 1306 proc(matrix, &pts[0], &pts[0], 1); 1307 if (firstVerb && mode == kExtend_AddPathMode && !isEmpty()) { 1308 injectMoveToIfNeeded(); // In case last contour is closed 1309 this->lineTo(pts[0]); 1310 } else { 1311 this->moveTo(pts[0]); 1312 } 1313 break; 1314 case kLine_Verb: 1315 proc(matrix, &pts[1], &pts[1], 1); 1316 this->lineTo(pts[1]); 1317 break; 1318 case kQuad_Verb: 1319 proc(matrix, &pts[1], &pts[1], 2); 1320 this->quadTo(pts[1], pts[2]); 1321 break; 1322 case kConic_Verb: 1323 proc(matrix, &pts[1], &pts[1], 2); 1324 this->conicTo(pts[1], pts[2], iter.conicWeight()); 1325 break; 1326 case kCubic_Verb: 1327 proc(matrix, &pts[1], &pts[1], 3); 1328 this->cubicTo(pts[1], pts[2], pts[3]); 1329 break; 1330 case kClose_Verb: 1331 this->close(); 1332 break; 1333 default: 1334 SkDEBUGFAIL("unknown verb"); 1335 } 1336 firstVerb = false; 1337 } 1338} 1339 1340/////////////////////////////////////////////////////////////////////////////// 1341 1342static int pts_in_verb(unsigned verb) { 1343 static const uint8_t gPtsInVerb[] = { 1344 1, // kMove 1345 1, // kLine 1346 2, // kQuad 1347 2, // kConic 1348 3, // kCubic 1349 0, // kClose 1350 0 // kDone 1351 }; 1352 1353 SkASSERT(verb < SK_ARRAY_COUNT(gPtsInVerb)); 1354 return gPtsInVerb[verb]; 1355} 1356 1357// ignore the last point of the 1st contour 1358void SkPath::reversePathTo(const SkPath& path) { 1359 int i, vcount = path.fPathRef->countVerbs(); 1360 // exit early if the path is empty, or just has a moveTo. 1361 if (vcount < 2) { 1362 return; 1363 } 1364 1365 SkPathRef::Editor(&fPathRef, vcount, path.countPoints()); 1366 1367 const uint8_t* verbs = path.fPathRef->verbs(); 1368 const SkPoint* pts = path.fPathRef->points(); 1369 const SkScalar* conicWeights = path.fPathRef->conicWeights(); 1370 1371 SkASSERT(verbs[~0] == kMove_Verb); 1372 for (i = 1; i < vcount; ++i) { 1373 unsigned v = verbs[~i]; 1374 int n = pts_in_verb(v); 1375 if (n == 0) { 1376 break; 1377 } 1378 pts += n; 1379 conicWeights += (SkPath::kConic_Verb == v); 1380 } 1381 1382 while (--i > 0) { 1383 switch (verbs[~i]) { 1384 case kLine_Verb: 1385 this->lineTo(pts[-1].fX, pts[-1].fY); 1386 break; 1387 case kQuad_Verb: 1388 this->quadTo(pts[-1].fX, pts[-1].fY, pts[-2].fX, pts[-2].fY); 1389 break; 1390 case kConic_Verb: 1391 this->conicTo(pts[-1], pts[-2], *--conicWeights); 1392 break; 1393 case kCubic_Verb: 1394 this->cubicTo(pts[-1].fX, pts[-1].fY, pts[-2].fX, pts[-2].fY, 1395 pts[-3].fX, pts[-3].fY); 1396 break; 1397 default: 1398 SkDEBUGFAIL("bad verb"); 1399 break; 1400 } 1401 pts -= pts_in_verb(verbs[~i]); 1402 } 1403} 1404 1405void SkPath::reverseAddPath(const SkPath& src) { 1406 SkPathRef::Editor ed(&fPathRef, src.fPathRef->countPoints(), src.fPathRef->countVerbs()); 1407 1408 const SkPoint* pts = src.fPathRef->pointsEnd(); 1409 // we will iterator through src's verbs backwards 1410 const uint8_t* verbs = src.fPathRef->verbsMemBegin(); // points at the last verb 1411 const uint8_t* verbsEnd = src.fPathRef->verbs(); // points just past the first verb 1412 const SkScalar* conicWeights = src.fPathRef->conicWeightsEnd(); 1413 1414 bool needMove = true; 1415 bool needClose = false; 1416 while (verbs < verbsEnd) { 1417 uint8_t v = *(verbs++); 1418 int n = pts_in_verb(v); 1419 1420 if (needMove) { 1421 --pts; 1422 this->moveTo(pts->fX, pts->fY); 1423 needMove = false; 1424 } 1425 pts -= n; 1426 switch (v) { 1427 case kMove_Verb: 1428 if (needClose) { 1429 this->close(); 1430 needClose = false; 1431 } 1432 needMove = true; 1433 pts += 1; // so we see the point in "if (needMove)" above 1434 break; 1435 case kLine_Verb: 1436 this->lineTo(pts[0]); 1437 break; 1438 case kQuad_Verb: 1439 this->quadTo(pts[1], pts[0]); 1440 break; 1441 case kConic_Verb: 1442 this->conicTo(pts[1], pts[0], *--conicWeights); 1443 break; 1444 case kCubic_Verb: 1445 this->cubicTo(pts[2], pts[1], pts[0]); 1446 break; 1447 case kClose_Verb: 1448 needClose = true; 1449 break; 1450 default: 1451 SkDEBUGFAIL("unexpected verb"); 1452 } 1453 } 1454} 1455 1456/////////////////////////////////////////////////////////////////////////////// 1457 1458void SkPath::offset(SkScalar dx, SkScalar dy, SkPath* dst) const { 1459 SkMatrix matrix; 1460 1461 matrix.setTranslate(dx, dy); 1462 this->transform(matrix, dst); 1463} 1464 1465static void subdivide_cubic_to(SkPath* path, const SkPoint pts[4], 1466 int level = 2) { 1467 if (--level >= 0) { 1468 SkPoint tmp[7]; 1469 1470 SkChopCubicAtHalf(pts, tmp); 1471 subdivide_cubic_to(path, &tmp[0], level); 1472 subdivide_cubic_to(path, &tmp[3], level); 1473 } else { 1474 path->cubicTo(pts[1], pts[2], pts[3]); 1475 } 1476} 1477 1478void SkPath::transform(const SkMatrix& matrix, SkPath* dst) const { 1479 SkDEBUGCODE(this->validate();) 1480 if (dst == NULL) { 1481 dst = (SkPath*)this; 1482 } 1483 1484 if (matrix.hasPerspective()) { 1485 SkPath tmp; 1486 tmp.fFillType = fFillType; 1487 1488 SkPath::Iter iter(*this, false); 1489 SkPoint pts[4]; 1490 SkPath::Verb verb; 1491 1492 while ((verb = iter.next(pts, false)) != kDone_Verb) { 1493 switch (verb) { 1494 case kMove_Verb: 1495 tmp.moveTo(pts[0]); 1496 break; 1497 case kLine_Verb: 1498 tmp.lineTo(pts[1]); 1499 break; 1500 case kQuad_Verb: 1501 // promote the quad to a conic 1502 tmp.conicTo(pts[1], pts[2], 1503 SkConic::TransformW(pts, SK_Scalar1, matrix)); 1504 break; 1505 case kConic_Verb: 1506 tmp.conicTo(pts[1], pts[2], 1507 SkConic::TransformW(pts, iter.conicWeight(), matrix)); 1508 break; 1509 case kCubic_Verb: 1510 subdivide_cubic_to(&tmp, pts); 1511 break; 1512 case kClose_Verb: 1513 tmp.close(); 1514 break; 1515 default: 1516 SkDEBUGFAIL("unknown verb"); 1517 break; 1518 } 1519 } 1520 1521 dst->swap(tmp); 1522 SkPathRef::Editor ed(&dst->fPathRef); 1523 matrix.mapPoints(ed.points(), ed.pathRef()->countPoints()); 1524 dst->fDirection = kUnknown_Direction; 1525 } else { 1526 SkPathRef::CreateTransformedCopy(&dst->fPathRef, *fPathRef.get(), matrix); 1527 1528 if (this != dst) { 1529 dst->fFillType = fFillType; 1530 dst->fConvexity = fConvexity; 1531 dst->fIsVolatile = fIsVolatile; 1532 } 1533 1534 if (kUnknown_Direction == fDirection) { 1535 dst->fDirection = kUnknown_Direction; 1536 } else { 1537 SkScalar det2x2 = 1538 SkScalarMul(matrix.get(SkMatrix::kMScaleX), matrix.get(SkMatrix::kMScaleY)) - 1539 SkScalarMul(matrix.get(SkMatrix::kMSkewX), matrix.get(SkMatrix::kMSkewY)); 1540 if (det2x2 < 0) { 1541 dst->fDirection = SkPath::OppositeDirection(static_cast<Direction>(fDirection)); 1542 } else if (det2x2 > 0) { 1543 dst->fDirection = fDirection; 1544 } else { 1545 dst->fConvexity = kUnknown_Convexity; 1546 dst->fDirection = kUnknown_Direction; 1547 } 1548 } 1549 1550 SkDEBUGCODE(dst->validate();) 1551 } 1552} 1553 1554/////////////////////////////////////////////////////////////////////////////// 1555/////////////////////////////////////////////////////////////////////////////// 1556 1557enum SegmentState { 1558 kEmptyContour_SegmentState, // The current contour is empty. We may be 1559 // starting processing or we may have just 1560 // closed a contour. 1561 kAfterMove_SegmentState, // We have seen a move, but nothing else. 1562 kAfterPrimitive_SegmentState // We have seen a primitive but not yet 1563 // closed the path. Also the initial state. 1564}; 1565 1566SkPath::Iter::Iter() { 1567#ifdef SK_DEBUG 1568 fPts = NULL; 1569 fConicWeights = NULL; 1570 fMoveTo.fX = fMoveTo.fY = fLastPt.fX = fLastPt.fY = 0; 1571 fForceClose = fCloseLine = false; 1572 fSegmentState = kEmptyContour_SegmentState; 1573#endif 1574 // need to init enough to make next() harmlessly return kDone_Verb 1575 fVerbs = NULL; 1576 fVerbStop = NULL; 1577 fNeedClose = false; 1578} 1579 1580SkPath::Iter::Iter(const SkPath& path, bool forceClose) { 1581 this->setPath(path, forceClose); 1582} 1583 1584void SkPath::Iter::setPath(const SkPath& path, bool forceClose) { 1585 fPts = path.fPathRef->points(); 1586 fVerbs = path.fPathRef->verbs(); 1587 fVerbStop = path.fPathRef->verbsMemBegin(); 1588 fConicWeights = path.fPathRef->conicWeights() - 1; // begin one behind 1589 fLastPt.fX = fLastPt.fY = 0; 1590 fMoveTo.fX = fMoveTo.fY = 0; 1591 fForceClose = SkToU8(forceClose); 1592 fNeedClose = false; 1593 fSegmentState = kEmptyContour_SegmentState; 1594} 1595 1596bool SkPath::Iter::isClosedContour() const { 1597 if (fVerbs == NULL || fVerbs == fVerbStop) { 1598 return false; 1599 } 1600 if (fForceClose) { 1601 return true; 1602 } 1603 1604 const uint8_t* verbs = fVerbs; 1605 const uint8_t* stop = fVerbStop; 1606 1607 if (kMove_Verb == *(verbs - 1)) { 1608 verbs -= 1; // skip the initial moveto 1609 } 1610 1611 while (verbs > stop) { 1612 // verbs points one beyond the current verb, decrement first. 1613 unsigned v = *(--verbs); 1614 if (kMove_Verb == v) { 1615 break; 1616 } 1617 if (kClose_Verb == v) { 1618 return true; 1619 } 1620 } 1621 return false; 1622} 1623 1624SkPath::Verb SkPath::Iter::autoClose(SkPoint pts[2]) { 1625 SkASSERT(pts); 1626 if (fLastPt != fMoveTo) { 1627 // A special case: if both points are NaN, SkPoint::operation== returns 1628 // false, but the iterator expects that they are treated as the same. 1629 // (consider SkPoint is a 2-dimension float point). 1630 if (SkScalarIsNaN(fLastPt.fX) || SkScalarIsNaN(fLastPt.fY) || 1631 SkScalarIsNaN(fMoveTo.fX) || SkScalarIsNaN(fMoveTo.fY)) { 1632 return kClose_Verb; 1633 } 1634 1635 pts[0] = fLastPt; 1636 pts[1] = fMoveTo; 1637 fLastPt = fMoveTo; 1638 fCloseLine = true; 1639 return kLine_Verb; 1640 } else { 1641 pts[0] = fMoveTo; 1642 return kClose_Verb; 1643 } 1644} 1645 1646const SkPoint& SkPath::Iter::cons_moveTo() { 1647 if (fSegmentState == kAfterMove_SegmentState) { 1648 // Set the first return pt to the move pt 1649 fSegmentState = kAfterPrimitive_SegmentState; 1650 return fMoveTo; 1651 } else { 1652 SkASSERT(fSegmentState == kAfterPrimitive_SegmentState); 1653 // Set the first return pt to the last pt of the previous primitive. 1654 return fPts[-1]; 1655 } 1656} 1657 1658void SkPath::Iter::consumeDegenerateSegments() { 1659 // We need to step over anything that will not move the current draw point 1660 // forward before the next move is seen 1661 const uint8_t* lastMoveVerb = 0; 1662 const SkPoint* lastMovePt = 0; 1663 const SkScalar* lastMoveWeight = NULL; 1664 SkPoint lastPt = fLastPt; 1665 while (fVerbs != fVerbStop) { 1666 unsigned verb = *(fVerbs - 1); // fVerbs is one beyond the current verb 1667 switch (verb) { 1668 case kMove_Verb: 1669 // Keep a record of this most recent move 1670 lastMoveVerb = fVerbs; 1671 lastMovePt = fPts; 1672 lastMoveWeight = fConicWeights; 1673 lastPt = fPts[0]; 1674 fVerbs--; 1675 fPts++; 1676 break; 1677 1678 case kClose_Verb: 1679 // A close when we are in a segment is always valid except when it 1680 // follows a move which follows a segment. 1681 if (fSegmentState == kAfterPrimitive_SegmentState && !lastMoveVerb) { 1682 return; 1683 } 1684 // A close at any other time must be ignored 1685 fVerbs--; 1686 break; 1687 1688 case kLine_Verb: 1689 if (!IsLineDegenerate(lastPt, fPts[0])) { 1690 if (lastMoveVerb) { 1691 fVerbs = lastMoveVerb; 1692 fPts = lastMovePt; 1693 fConicWeights = lastMoveWeight; 1694 return; 1695 } 1696 return; 1697 } 1698 // Ignore this line and continue 1699 fVerbs--; 1700 fPts++; 1701 break; 1702 1703 case kConic_Verb: 1704 case kQuad_Verb: 1705 if (!IsQuadDegenerate(lastPt, fPts[0], fPts[1])) { 1706 if (lastMoveVerb) { 1707 fVerbs = lastMoveVerb; 1708 fPts = lastMovePt; 1709 fConicWeights = lastMoveWeight; 1710 return; 1711 } 1712 return; 1713 } 1714 // Ignore this line and continue 1715 fVerbs--; 1716 fPts += 2; 1717 fConicWeights += (kConic_Verb == verb); 1718 break; 1719 1720 case kCubic_Verb: 1721 if (!IsCubicDegenerate(lastPt, fPts[0], fPts[1], fPts[2])) { 1722 if (lastMoveVerb) { 1723 fVerbs = lastMoveVerb; 1724 fPts = lastMovePt; 1725 fConicWeights = lastMoveWeight; 1726 return; 1727 } 1728 return; 1729 } 1730 // Ignore this line and continue 1731 fVerbs--; 1732 fPts += 3; 1733 break; 1734 1735 default: 1736 SkDEBUGFAIL("Should never see kDone_Verb"); 1737 } 1738 } 1739} 1740 1741SkPath::Verb SkPath::Iter::doNext(SkPoint ptsParam[4]) { 1742 SkASSERT(ptsParam); 1743 1744 if (fVerbs == fVerbStop) { 1745 // Close the curve if requested and if there is some curve to close 1746 if (fNeedClose && fSegmentState == kAfterPrimitive_SegmentState) { 1747 if (kLine_Verb == this->autoClose(ptsParam)) { 1748 return kLine_Verb; 1749 } 1750 fNeedClose = false; 1751 return kClose_Verb; 1752 } 1753 return kDone_Verb; 1754 } 1755 1756 // fVerbs is one beyond the current verb, decrement first 1757 unsigned verb = *(--fVerbs); 1758 const SkPoint* SK_RESTRICT srcPts = fPts; 1759 SkPoint* SK_RESTRICT pts = ptsParam; 1760 1761 switch (verb) { 1762 case kMove_Verb: 1763 if (fNeedClose) { 1764 fVerbs++; // move back one verb 1765 verb = this->autoClose(pts); 1766 if (verb == kClose_Verb) { 1767 fNeedClose = false; 1768 } 1769 return (Verb)verb; 1770 } 1771 if (fVerbs == fVerbStop) { // might be a trailing moveto 1772 return kDone_Verb; 1773 } 1774 fMoveTo = *srcPts; 1775 pts[0] = *srcPts; 1776 srcPts += 1; 1777 fSegmentState = kAfterMove_SegmentState; 1778 fLastPt = fMoveTo; 1779 fNeedClose = fForceClose; 1780 break; 1781 case kLine_Verb: 1782 pts[0] = this->cons_moveTo(); 1783 pts[1] = srcPts[0]; 1784 fLastPt = srcPts[0]; 1785 fCloseLine = false; 1786 srcPts += 1; 1787 break; 1788 case kConic_Verb: 1789 fConicWeights += 1; 1790 // fall-through 1791 case kQuad_Verb: 1792 pts[0] = this->cons_moveTo(); 1793 memcpy(&pts[1], srcPts, 2 * sizeof(SkPoint)); 1794 fLastPt = srcPts[1]; 1795 srcPts += 2; 1796 break; 1797 case kCubic_Verb: 1798 pts[0] = this->cons_moveTo(); 1799 memcpy(&pts[1], srcPts, 3 * sizeof(SkPoint)); 1800 fLastPt = srcPts[2]; 1801 srcPts += 3; 1802 break; 1803 case kClose_Verb: 1804 verb = this->autoClose(pts); 1805 if (verb == kLine_Verb) { 1806 fVerbs++; // move back one verb 1807 } else { 1808 fNeedClose = false; 1809 fSegmentState = kEmptyContour_SegmentState; 1810 } 1811 fLastPt = fMoveTo; 1812 break; 1813 } 1814 fPts = srcPts; 1815 return (Verb)verb; 1816} 1817 1818/////////////////////////////////////////////////////////////////////////////// 1819 1820SkPath::RawIter::RawIter() { 1821#ifdef SK_DEBUG 1822 fPts = NULL; 1823 fConicWeights = NULL; 1824 fMoveTo.fX = fMoveTo.fY = fLastPt.fX = fLastPt.fY = 0; 1825#endif 1826 // need to init enough to make next() harmlessly return kDone_Verb 1827 fVerbs = NULL; 1828 fVerbStop = NULL; 1829} 1830 1831SkPath::RawIter::RawIter(const SkPath& path) { 1832 this->setPath(path); 1833} 1834 1835void SkPath::RawIter::setPath(const SkPath& path) { 1836 fPts = path.fPathRef->points(); 1837 fVerbs = path.fPathRef->verbs(); 1838 fVerbStop = path.fPathRef->verbsMemBegin(); 1839 fConicWeights = path.fPathRef->conicWeights() - 1; // begin one behind 1840 fMoveTo.fX = fMoveTo.fY = 0; 1841 fLastPt.fX = fLastPt.fY = 0; 1842} 1843 1844SkPath::Verb SkPath::RawIter::next(SkPoint pts[4]) { 1845 SkASSERT(pts); 1846 if (fVerbs == fVerbStop) { 1847 return kDone_Verb; 1848 } 1849 1850 // fVerbs points one beyond next verb so decrement first. 1851 unsigned verb = *(--fVerbs); 1852 const SkPoint* srcPts = fPts; 1853 1854 switch (verb) { 1855 case kMove_Verb: 1856 pts[0] = *srcPts; 1857 fMoveTo = srcPts[0]; 1858 fLastPt = fMoveTo; 1859 srcPts += 1; 1860 break; 1861 case kLine_Verb: 1862 pts[0] = fLastPt; 1863 pts[1] = srcPts[0]; 1864 fLastPt = srcPts[0]; 1865 srcPts += 1; 1866 break; 1867 case kConic_Verb: 1868 fConicWeights += 1; 1869 // fall-through 1870 case kQuad_Verb: 1871 pts[0] = fLastPt; 1872 memcpy(&pts[1], srcPts, 2 * sizeof(SkPoint)); 1873 fLastPt = srcPts[1]; 1874 srcPts += 2; 1875 break; 1876 case kCubic_Verb: 1877 pts[0] = fLastPt; 1878 memcpy(&pts[1], srcPts, 3 * sizeof(SkPoint)); 1879 fLastPt = srcPts[2]; 1880 srcPts += 3; 1881 break; 1882 case kClose_Verb: 1883 fLastPt = fMoveTo; 1884 pts[0] = fMoveTo; 1885 break; 1886 } 1887 fPts = srcPts; 1888 return (Verb)verb; 1889} 1890 1891/////////////////////////////////////////////////////////////////////////////// 1892 1893/* 1894 Format in compressed buffer: [ptCount, verbCount, pts[], verbs[]] 1895*/ 1896 1897size_t SkPath::writeToMemory(void* storage) const { 1898 SkDEBUGCODE(this->validate();) 1899 1900 if (NULL == storage) { 1901 const int byteCount = sizeof(int32_t) + fPathRef->writeSize(); 1902 return SkAlign4(byteCount); 1903 } 1904 1905 SkWBuffer buffer(storage); 1906 1907 int32_t packed = (fConvexity << kConvexity_SerializationShift) | 1908 (fFillType << kFillType_SerializationShift) | 1909 (fDirection << kDirection_SerializationShift) | 1910 (fIsVolatile << kIsVolatile_SerializationShift); 1911 1912 buffer.write32(packed); 1913 1914 fPathRef->writeToBuffer(&buffer); 1915 1916 buffer.padToAlign4(); 1917 return buffer.pos(); 1918} 1919 1920size_t SkPath::readFromMemory(const void* storage, size_t length) { 1921 SkRBufferWithSizeCheck buffer(storage, length); 1922 1923 int32_t packed; 1924 if (!buffer.readS32(&packed)) { 1925 return 0; 1926 } 1927 1928 fConvexity = (packed >> kConvexity_SerializationShift) & 0xFF; 1929 fFillType = (packed >> kFillType_SerializationShift) & 0xFF; 1930 fDirection = (packed >> kDirection_SerializationShift) & 0x3; 1931 fIsVolatile = (packed >> kIsVolatile_SerializationShift) & 0x1; 1932 SkPathRef* pathRef = SkPathRef::CreateFromBuffer(&buffer); 1933 1934 size_t sizeRead = 0; 1935 if (buffer.isValid()) { 1936 fPathRef.reset(pathRef); 1937 SkDEBUGCODE(this->validate();) 1938 buffer.skipToAlign4(); 1939 sizeRead = buffer.pos(); 1940 } else if (pathRef) { 1941 // If the buffer is not valid, pathRef should be NULL 1942 sk_throw(); 1943 } 1944 return sizeRead; 1945} 1946 1947/////////////////////////////////////////////////////////////////////////////// 1948 1949#include "SkStringUtils.h" 1950#include "SkStream.h" 1951 1952static void append_params(SkString* str, const char label[], const SkPoint pts[], 1953 int count, SkScalarAsStringType strType, SkScalar conicWeight = -1) { 1954 str->append(label); 1955 str->append("("); 1956 1957 const SkScalar* values = &pts[0].fX; 1958 count *= 2; 1959 1960 for (int i = 0; i < count; ++i) { 1961 SkAppendScalar(str, values[i], strType); 1962 if (i < count - 1) { 1963 str->append(", "); 1964 } 1965 } 1966 if (conicWeight >= 0) { 1967 str->append(", "); 1968 SkAppendScalar(str, conicWeight, strType); 1969 } 1970 str->append(");"); 1971 if (kHex_SkScalarAsStringType == strType) { 1972 str->append(" // "); 1973 for (int i = 0; i < count; ++i) { 1974 SkAppendScalarDec(str, values[i]); 1975 if (i < count - 1) { 1976 str->append(", "); 1977 } 1978 } 1979 if (conicWeight >= 0) { 1980 str->append(", "); 1981 SkAppendScalarDec(str, conicWeight); 1982 } 1983 } 1984 str->append("\n"); 1985} 1986 1987void SkPath::dump(SkWStream* wStream, bool forceClose, bool dumpAsHex) const { 1988 SkScalarAsStringType asType = dumpAsHex ? kHex_SkScalarAsStringType : kDec_SkScalarAsStringType; 1989 Iter iter(*this, forceClose); 1990 SkPoint pts[4]; 1991 Verb verb; 1992 1993 if (!wStream) { 1994 SkDebugf("path: forceClose=%s\n", forceClose ? "true" : "false"); 1995 } 1996 SkString builder; 1997 1998 while ((verb = iter.next(pts, false)) != kDone_Verb) { 1999 switch (verb) { 2000 case kMove_Verb: 2001 append_params(&builder, "path.moveTo", &pts[0], 1, asType); 2002 break; 2003 case kLine_Verb: 2004 append_params(&builder, "path.lineTo", &pts[1], 1, asType); 2005 break; 2006 case kQuad_Verb: 2007 append_params(&builder, "path.quadTo", &pts[1], 2, asType); 2008 break; 2009 case kConic_Verb: 2010 append_params(&builder, "path.conicTo", &pts[1], 2, asType, iter.conicWeight()); 2011 break; 2012 case kCubic_Verb: 2013 append_params(&builder, "path.cubicTo", &pts[1], 3, asType); 2014 break; 2015 case kClose_Verb: 2016 builder.append("path.close();\n"); 2017 break; 2018 default: 2019 SkDebugf(" path: UNKNOWN VERB %d, aborting dump...\n", verb); 2020 verb = kDone_Verb; // stop the loop 2021 break; 2022 } 2023 } 2024 if (wStream) { 2025 wStream->writeText(builder.c_str()); 2026 } else { 2027 SkDebugf("%s", builder.c_str()); 2028 } 2029} 2030 2031void SkPath::dump() const { 2032 this->dump(NULL, false, false); 2033} 2034 2035void SkPath::dumpHex() const { 2036 this->dump(NULL, false, true); 2037} 2038 2039#ifdef SK_DEBUG 2040void SkPath::validate() const { 2041 SkASSERT(this != NULL); 2042 SkASSERT((fFillType & ~3) == 0); 2043 2044#ifdef SK_DEBUG_PATH 2045 if (!fBoundsIsDirty) { 2046 SkRect bounds; 2047 2048 bool isFinite = compute_pt_bounds(&bounds, *fPathRef.get()); 2049 SkASSERT(SkToBool(fIsFinite) == isFinite); 2050 2051 if (fPathRef->countPoints() <= 1) { 2052 // if we're empty, fBounds may be empty but translated, so we can't 2053 // necessarily compare to bounds directly 2054 // try path.addOval(2, 2, 2, 2) which is empty, but the bounds will 2055 // be [2, 2, 2, 2] 2056 SkASSERT(bounds.isEmpty()); 2057 SkASSERT(fBounds.isEmpty()); 2058 } else { 2059 if (bounds.isEmpty()) { 2060 SkASSERT(fBounds.isEmpty()); 2061 } else { 2062 if (!fBounds.isEmpty()) { 2063 SkASSERT(fBounds.contains(bounds)); 2064 } 2065 } 2066 } 2067 } 2068#endif // SK_DEBUG_PATH 2069} 2070#endif // SK_DEBUG 2071 2072/////////////////////////////////////////////////////////////////////////////// 2073 2074static int sign(SkScalar x) { return x < 0; } 2075#define kValueNeverReturnedBySign 2 2076 2077enum DirChange { 2078 kLeft_DirChange, 2079 kRight_DirChange, 2080 kStraight_DirChange, 2081 kBackwards_DirChange, 2082 2083 kInvalid_DirChange 2084}; 2085 2086 2087static bool almost_equal(SkScalar compA, SkScalar compB) { 2088 // The error epsilon was empirically derived; worse case round rects 2089 // with a mid point outset by 2x float epsilon in tests had an error 2090 // of 12. 2091 const int epsilon = 16; 2092 if (!SkScalarIsFinite(compA) || !SkScalarIsFinite(compB)) { 2093 return false; 2094 } 2095 // no need to check for small numbers because SkPath::Iter has removed degenerate values 2096 int aBits = SkFloatAs2sCompliment(compA); 2097 int bBits = SkFloatAs2sCompliment(compB); 2098 return aBits < bBits + epsilon && bBits < aBits + epsilon; 2099} 2100 2101static DirChange direction_change(const SkPoint& lastPt, const SkVector& curPt, 2102 const SkVector& lastVec, const SkVector& curVec) { 2103 SkScalar cross = SkPoint::CrossProduct(lastVec, curVec); 2104 2105 SkScalar smallest = SkTMin(curPt.fX, SkTMin(curPt.fY, SkTMin(lastPt.fX, lastPt.fY))); 2106 SkScalar largest = SkTMax(curPt.fX, SkTMax(curPt.fY, SkTMax(lastPt.fX, lastPt.fY))); 2107 largest = SkTMax(largest, -smallest); 2108 2109 if (!almost_equal(largest, largest + cross)) { 2110 int sign = SkScalarSignAsInt(cross); 2111 if (sign) { 2112 return (1 == sign) ? kRight_DirChange : kLeft_DirChange; 2113 } 2114 } 2115 2116 if (!SkScalarNearlyZero(lastVec.lengthSqd(), SK_ScalarNearlyZero*SK_ScalarNearlyZero) && 2117 !SkScalarNearlyZero(curVec.lengthSqd(), SK_ScalarNearlyZero*SK_ScalarNearlyZero) && 2118 lastVec.dot(curVec) < 0.0f) { 2119 return kBackwards_DirChange; 2120 } 2121 2122 return kStraight_DirChange; 2123} 2124 2125// only valid for a single contour 2126struct Convexicator { 2127 Convexicator() 2128 : fPtCount(0) 2129 , fConvexity(SkPath::kConvex_Convexity) 2130 , fDirection(SkPath::kUnknown_Direction) 2131 , fIsFinite(true) { 2132 fExpectedDir = kInvalid_DirChange; 2133 // warnings 2134 fLastPt.set(0, 0); 2135 fCurrPt.set(0, 0); 2136 fLastVec.set(0, 0); 2137 fFirstVec.set(0, 0); 2138 2139 fDx = fDy = 0; 2140 fSx = fSy = kValueNeverReturnedBySign; 2141 } 2142 2143 SkPath::Convexity getConvexity() const { return fConvexity; } 2144 2145 /** The direction returned is only valid if the path is determined convex */ 2146 SkPath::Direction getDirection() const { return fDirection; } 2147 2148 void addPt(const SkPoint& pt) { 2149 if (SkPath::kConcave_Convexity == fConvexity || !fIsFinite) { 2150 return; 2151 } 2152 2153 if (0 == fPtCount) { 2154 fCurrPt = pt; 2155 ++fPtCount; 2156 } else { 2157 SkVector vec = pt - fCurrPt; 2158 SkScalar lengthSqd = vec.lengthSqd(); 2159 if (!SkScalarIsFinite(lengthSqd)) { 2160 fIsFinite = false; 2161 } else if (!SkScalarNearlyZero(lengthSqd, SK_ScalarNearlyZero*SK_ScalarNearlyZero)) { 2162 fLastPt = fCurrPt; 2163 fCurrPt = pt; 2164 if (++fPtCount == 2) { 2165 fFirstVec = fLastVec = vec; 2166 } else { 2167 SkASSERT(fPtCount > 2); 2168 this->addVec(vec); 2169 } 2170 2171 int sx = sign(vec.fX); 2172 int sy = sign(vec.fY); 2173 fDx += (sx != fSx); 2174 fDy += (sy != fSy); 2175 fSx = sx; 2176 fSy = sy; 2177 2178 if (fDx > 3 || fDy > 3) { 2179 fConvexity = SkPath::kConcave_Convexity; 2180 } 2181 } 2182 } 2183 } 2184 2185 void close() { 2186 if (fPtCount > 2) { 2187 this->addVec(fFirstVec); 2188 } 2189 } 2190 2191 bool isFinite() const { 2192 return fIsFinite; 2193 } 2194 2195private: 2196 void addVec(const SkVector& vec) { 2197 SkASSERT(vec.fX || vec.fY); 2198 DirChange dir = direction_change(fLastPt, fCurrPt, fLastVec, vec); 2199 switch (dir) { 2200 case kLeft_DirChange: // fall through 2201 case kRight_DirChange: 2202 if (kInvalid_DirChange == fExpectedDir) { 2203 fExpectedDir = dir; 2204 fDirection = (kRight_DirChange == dir) ? SkPath::kCW_Direction 2205 : SkPath::kCCW_Direction; 2206 } else if (dir != fExpectedDir) { 2207 fConvexity = SkPath::kConcave_Convexity; 2208 fDirection = SkPath::kUnknown_Direction; 2209 } 2210 fLastVec = vec; 2211 break; 2212 case kStraight_DirChange: 2213 break; 2214 case kBackwards_DirChange: 2215 fLastVec = vec; 2216 break; 2217 case kInvalid_DirChange: 2218 SkFAIL("Use of invalid direction change flag"); 2219 break; 2220 } 2221 } 2222 2223 SkPoint fLastPt; 2224 SkPoint fCurrPt; 2225 // fLastVec does not necessarily start at fLastPt. We only advance it when the cross product 2226 // value with the current vec is deemed to be of a significant value. 2227 SkVector fLastVec, fFirstVec; 2228 int fPtCount; // non-degenerate points 2229 DirChange fExpectedDir; 2230 SkPath::Convexity fConvexity; 2231 SkPath::Direction fDirection; 2232 int fDx, fDy, fSx, fSy; 2233 bool fIsFinite; 2234}; 2235 2236SkPath::Convexity SkPath::internalGetConvexity() const { 2237 SkASSERT(kUnknown_Convexity == fConvexity); 2238 SkPoint pts[4]; 2239 SkPath::Verb verb; 2240 SkPath::Iter iter(*this, true); 2241 2242 int contourCount = 0; 2243 int count; 2244 Convexicator state; 2245 2246 if (!isFinite()) { 2247 return kUnknown_Convexity; 2248 } 2249 while ((verb = iter.next(pts)) != SkPath::kDone_Verb) { 2250 switch (verb) { 2251 case kMove_Verb: 2252 if (++contourCount > 1) { 2253 fConvexity = kConcave_Convexity; 2254 return kConcave_Convexity; 2255 } 2256 pts[1] = pts[0]; 2257 count = 1; 2258 break; 2259 case kLine_Verb: count = 1; break; 2260 case kQuad_Verb: count = 2; break; 2261 case kConic_Verb: count = 2; break; 2262 case kCubic_Verb: count = 3; break; 2263 case kClose_Verb: 2264 state.close(); 2265 count = 0; 2266 break; 2267 default: 2268 SkDEBUGFAIL("bad verb"); 2269 fConvexity = kConcave_Convexity; 2270 return kConcave_Convexity; 2271 } 2272 2273 for (int i = 1; i <= count; i++) { 2274 state.addPt(pts[i]); 2275 } 2276 // early exit 2277 if (!state.isFinite()) { 2278 return kUnknown_Convexity; 2279 } 2280 if (kConcave_Convexity == state.getConvexity()) { 2281 fConvexity = kConcave_Convexity; 2282 return kConcave_Convexity; 2283 } 2284 } 2285 fConvexity = state.getConvexity(); 2286 if (kConvex_Convexity == fConvexity && kUnknown_Direction == fDirection) { 2287 fDirection = state.getDirection(); 2288 } 2289 return static_cast<Convexity>(fConvexity); 2290} 2291 2292/////////////////////////////////////////////////////////////////////////////// 2293 2294class ContourIter { 2295public: 2296 ContourIter(const SkPathRef& pathRef); 2297 2298 bool done() const { return fDone; } 2299 // if !done() then these may be called 2300 int count() const { return fCurrPtCount; } 2301 const SkPoint* pts() const { return fCurrPt; } 2302 void next(); 2303 2304private: 2305 int fCurrPtCount; 2306 const SkPoint* fCurrPt; 2307 const uint8_t* fCurrVerb; 2308 const uint8_t* fStopVerbs; 2309 const SkScalar* fCurrConicWeight; 2310 bool fDone; 2311 SkDEBUGCODE(int fContourCounter;) 2312}; 2313 2314ContourIter::ContourIter(const SkPathRef& pathRef) { 2315 fStopVerbs = pathRef.verbsMemBegin(); 2316 fDone = false; 2317 fCurrPt = pathRef.points(); 2318 fCurrVerb = pathRef.verbs(); 2319 fCurrConicWeight = pathRef.conicWeights(); 2320 fCurrPtCount = 0; 2321 SkDEBUGCODE(fContourCounter = 0;) 2322 this->next(); 2323} 2324 2325void ContourIter::next() { 2326 if (fCurrVerb <= fStopVerbs) { 2327 fDone = true; 2328 } 2329 if (fDone) { 2330 return; 2331 } 2332 2333 // skip pts of prev contour 2334 fCurrPt += fCurrPtCount; 2335 2336 SkASSERT(SkPath::kMove_Verb == fCurrVerb[~0]); 2337 int ptCount = 1; // moveTo 2338 const uint8_t* verbs = fCurrVerb; 2339 2340 for (--verbs; verbs > fStopVerbs; --verbs) { 2341 switch (verbs[~0]) { 2342 case SkPath::kMove_Verb: 2343 goto CONTOUR_END; 2344 case SkPath::kLine_Verb: 2345 ptCount += 1; 2346 break; 2347 case SkPath::kConic_Verb: 2348 fCurrConicWeight += 1; 2349 // fall-through 2350 case SkPath::kQuad_Verb: 2351 ptCount += 2; 2352 break; 2353 case SkPath::kCubic_Verb: 2354 ptCount += 3; 2355 break; 2356 case SkPath::kClose_Verb: 2357 break; 2358 default: 2359 SkDEBUGFAIL("unexpected verb"); 2360 break; 2361 } 2362 } 2363CONTOUR_END: 2364 fCurrPtCount = ptCount; 2365 fCurrVerb = verbs; 2366 SkDEBUGCODE(++fContourCounter;) 2367} 2368 2369// returns cross product of (p1 - p0) and (p2 - p0) 2370static SkScalar cross_prod(const SkPoint& p0, const SkPoint& p1, const SkPoint& p2) { 2371 SkScalar cross = SkPoint::CrossProduct(p1 - p0, p2 - p0); 2372 // We may get 0 when the above subtracts underflow. We expect this to be 2373 // very rare and lazily promote to double. 2374 if (0 == cross) { 2375 double p0x = SkScalarToDouble(p0.fX); 2376 double p0y = SkScalarToDouble(p0.fY); 2377 2378 double p1x = SkScalarToDouble(p1.fX); 2379 double p1y = SkScalarToDouble(p1.fY); 2380 2381 double p2x = SkScalarToDouble(p2.fX); 2382 double p2y = SkScalarToDouble(p2.fY); 2383 2384 cross = SkDoubleToScalar((p1x - p0x) * (p2y - p0y) - 2385 (p1y - p0y) * (p2x - p0x)); 2386 2387 } 2388 return cross; 2389} 2390 2391// Returns the first pt with the maximum Y coordinate 2392static int find_max_y(const SkPoint pts[], int count) { 2393 SkASSERT(count > 0); 2394 SkScalar max = pts[0].fY; 2395 int firstIndex = 0; 2396 for (int i = 1; i < count; ++i) { 2397 SkScalar y = pts[i].fY; 2398 if (y > max) { 2399 max = y; 2400 firstIndex = i; 2401 } 2402 } 2403 return firstIndex; 2404} 2405 2406static int find_diff_pt(const SkPoint pts[], int index, int n, int inc) { 2407 int i = index; 2408 for (;;) { 2409 i = (i + inc) % n; 2410 if (i == index) { // we wrapped around, so abort 2411 break; 2412 } 2413 if (pts[index] != pts[i]) { // found a different point, success! 2414 break; 2415 } 2416 } 2417 return i; 2418} 2419 2420/** 2421 * Starting at index, and moving forward (incrementing), find the xmin and 2422 * xmax of the contiguous points that have the same Y. 2423 */ 2424static int find_min_max_x_at_y(const SkPoint pts[], int index, int n, 2425 int* maxIndexPtr) { 2426 const SkScalar y = pts[index].fY; 2427 SkScalar min = pts[index].fX; 2428 SkScalar max = min; 2429 int minIndex = index; 2430 int maxIndex = index; 2431 for (int i = index + 1; i < n; ++i) { 2432 if (pts[i].fY != y) { 2433 break; 2434 } 2435 SkScalar x = pts[i].fX; 2436 if (x < min) { 2437 min = x; 2438 minIndex = i; 2439 } else if (x > max) { 2440 max = x; 2441 maxIndex = i; 2442 } 2443 } 2444 *maxIndexPtr = maxIndex; 2445 return minIndex; 2446} 2447 2448static void crossToDir(SkScalar cross, SkPath::Direction* dir) { 2449 *dir = cross > 0 ? SkPath::kCW_Direction : SkPath::kCCW_Direction; 2450} 2451 2452/* 2453 * We loop through all contours, and keep the computed cross-product of the 2454 * contour that contained the global y-max. If we just look at the first 2455 * contour, we may find one that is wound the opposite way (correctly) since 2456 * it is the interior of a hole (e.g. 'o'). Thus we must find the contour 2457 * that is outer most (or at least has the global y-max) before we can consider 2458 * its cross product. 2459 */ 2460bool SkPath::cheapComputeDirection(Direction* dir) const { 2461 if (kUnknown_Direction != fDirection) { 2462 *dir = static_cast<Direction>(fDirection); 2463 return true; 2464 } 2465 2466 // don't want to pay the cost for computing this if it 2467 // is unknown, so we don't call isConvex() 2468 if (kConvex_Convexity == this->getConvexityOrUnknown()) { 2469 SkASSERT(kUnknown_Direction == fDirection); 2470 *dir = static_cast<Direction>(fDirection); 2471 return false; 2472 } 2473 2474 ContourIter iter(*fPathRef.get()); 2475 2476 // initialize with our logical y-min 2477 SkScalar ymax = this->getBounds().fTop; 2478 SkScalar ymaxCross = 0; 2479 2480 for (; !iter.done(); iter.next()) { 2481 int n = iter.count(); 2482 if (n < 3) { 2483 continue; 2484 } 2485 2486 const SkPoint* pts = iter.pts(); 2487 SkScalar cross = 0; 2488 int index = find_max_y(pts, n); 2489 if (pts[index].fY < ymax) { 2490 continue; 2491 } 2492 2493 // If there is more than 1 distinct point at the y-max, we take the 2494 // x-min and x-max of them and just subtract to compute the dir. 2495 if (pts[(index + 1) % n].fY == pts[index].fY) { 2496 int maxIndex; 2497 int minIndex = find_min_max_x_at_y(pts, index, n, &maxIndex); 2498 if (minIndex == maxIndex) { 2499 goto TRY_CROSSPROD; 2500 } 2501 SkASSERT(pts[minIndex].fY == pts[index].fY); 2502 SkASSERT(pts[maxIndex].fY == pts[index].fY); 2503 SkASSERT(pts[minIndex].fX <= pts[maxIndex].fX); 2504 // we just subtract the indices, and let that auto-convert to 2505 // SkScalar, since we just want - or + to signal the direction. 2506 cross = minIndex - maxIndex; 2507 } else { 2508 TRY_CROSSPROD: 2509 // Find a next and prev index to use for the cross-product test, 2510 // but we try to find pts that form non-zero vectors from pts[index] 2511 // 2512 // Its possible that we can't find two non-degenerate vectors, so 2513 // we have to guard our search (e.g. all the pts could be in the 2514 // same place). 2515 2516 // we pass n - 1 instead of -1 so we don't foul up % operator by 2517 // passing it a negative LH argument. 2518 int prev = find_diff_pt(pts, index, n, n - 1); 2519 if (prev == index) { 2520 // completely degenerate, skip to next contour 2521 continue; 2522 } 2523 int next = find_diff_pt(pts, index, n, 1); 2524 SkASSERT(next != index); 2525 cross = cross_prod(pts[prev], pts[index], pts[next]); 2526 // if we get a zero and the points are horizontal, then we look at the spread in 2527 // x-direction. We really should continue to walk away from the degeneracy until 2528 // there is a divergence. 2529 if (0 == cross && pts[prev].fY == pts[index].fY && pts[next].fY == pts[index].fY) { 2530 // construct the subtract so we get the correct Direction below 2531 cross = pts[index].fX - pts[next].fX; 2532 } 2533 } 2534 2535 if (cross) { 2536 // record our best guess so far 2537 ymax = pts[index].fY; 2538 ymaxCross = cross; 2539 } 2540 } 2541 if (ymaxCross) { 2542 crossToDir(ymaxCross, dir); 2543 fDirection = *dir; 2544 return true; 2545 } else { 2546 return false; 2547 } 2548} 2549 2550/////////////////////////////////////////////////////////////////////////////// 2551 2552static SkScalar eval_cubic_coeff(SkScalar A, SkScalar B, SkScalar C, 2553 SkScalar D, SkScalar t) { 2554 return SkScalarMulAdd(SkScalarMulAdd(SkScalarMulAdd(A, t, B), t, C), t, D); 2555} 2556 2557static SkScalar eval_cubic_pts(SkScalar c0, SkScalar c1, SkScalar c2, SkScalar c3, 2558 SkScalar t) { 2559 SkScalar A = c3 + 3*(c1 - c2) - c0; 2560 SkScalar B = 3*(c2 - c1 - c1 + c0); 2561 SkScalar C = 3*(c1 - c0); 2562 SkScalar D = c0; 2563 return eval_cubic_coeff(A, B, C, D, t); 2564} 2565 2566/* Given 4 cubic points (either Xs or Ys), and a target X or Y, compute the 2567 t value such that cubic(t) = target 2568 */ 2569static void chopMonoCubicAt(SkScalar c0, SkScalar c1, SkScalar c2, SkScalar c3, 2570 SkScalar target, SkScalar* t) { 2571 // SkASSERT(c0 <= c1 && c1 <= c2 && c2 <= c3); 2572 SkASSERT(c0 < target && target < c3); 2573 2574 SkScalar D = c0 - target; 2575 SkScalar A = c3 + 3*(c1 - c2) - c0; 2576 SkScalar B = 3*(c2 - c1 - c1 + c0); 2577 SkScalar C = 3*(c1 - c0); 2578 2579 const SkScalar TOLERANCE = SK_Scalar1 / 4096; 2580 SkScalar minT = 0; 2581 SkScalar maxT = SK_Scalar1; 2582 SkScalar mid; 2583 int i; 2584 for (i = 0; i < 16; i++) { 2585 mid = SkScalarAve(minT, maxT); 2586 SkScalar delta = eval_cubic_coeff(A, B, C, D, mid); 2587 if (delta < 0) { 2588 minT = mid; 2589 delta = -delta; 2590 } else { 2591 maxT = mid; 2592 } 2593 if (delta < TOLERANCE) { 2594 break; 2595 } 2596 } 2597 *t = mid; 2598} 2599 2600template <size_t N> static void find_minmax(const SkPoint pts[], 2601 SkScalar* minPtr, SkScalar* maxPtr) { 2602 SkScalar min, max; 2603 min = max = pts[0].fX; 2604 for (size_t i = 1; i < N; ++i) { 2605 min = SkMinScalar(min, pts[i].fX); 2606 max = SkMaxScalar(max, pts[i].fX); 2607 } 2608 *minPtr = min; 2609 *maxPtr = max; 2610} 2611 2612static int winding_mono_cubic(const SkPoint pts[], SkScalar x, SkScalar y) { 2613 SkPoint storage[4]; 2614 2615 int dir = 1; 2616 if (pts[0].fY > pts[3].fY) { 2617 storage[0] = pts[3]; 2618 storage[1] = pts[2]; 2619 storage[2] = pts[1]; 2620 storage[3] = pts[0]; 2621 pts = storage; 2622 dir = -1; 2623 } 2624 if (y < pts[0].fY || y >= pts[3].fY) { 2625 return 0; 2626 } 2627 2628 // quickreject or quickaccept 2629 SkScalar min, max; 2630 find_minmax<4>(pts, &min, &max); 2631 if (x < min) { 2632 return 0; 2633 } 2634 if (x > max) { 2635 return dir; 2636 } 2637 2638 // compute the actual x(t) value 2639 SkScalar t; 2640 chopMonoCubicAt(pts[0].fY, pts[1].fY, pts[2].fY, pts[3].fY, y, &t); 2641 SkScalar xt = eval_cubic_pts(pts[0].fX, pts[1].fX, pts[2].fX, pts[3].fX, t); 2642 return xt < x ? dir : 0; 2643} 2644 2645static int winding_cubic(const SkPoint pts[], SkScalar x, SkScalar y) { 2646 SkPoint dst[10]; 2647 int n = SkChopCubicAtYExtrema(pts, dst); 2648 int w = 0; 2649 for (int i = 0; i <= n; ++i) { 2650 w += winding_mono_cubic(&dst[i * 3], x, y); 2651 } 2652 return w; 2653} 2654 2655static int winding_mono_quad(const SkPoint pts[], SkScalar x, SkScalar y) { 2656 SkScalar y0 = pts[0].fY; 2657 SkScalar y2 = pts[2].fY; 2658 2659 int dir = 1; 2660 if (y0 > y2) { 2661 SkTSwap(y0, y2); 2662 dir = -1; 2663 } 2664 if (y < y0 || y >= y2) { 2665 return 0; 2666 } 2667 2668 // bounds check on X (not required. is it faster?) 2669#if 0 2670 if (pts[0].fX > x && pts[1].fX > x && pts[2].fX > x) { 2671 return 0; 2672 } 2673#endif 2674 2675 SkScalar roots[2]; 2676 int n = SkFindUnitQuadRoots(pts[0].fY - 2 * pts[1].fY + pts[2].fY, 2677 2 * (pts[1].fY - pts[0].fY), 2678 pts[0].fY - y, 2679 roots); 2680 SkASSERT(n <= 1); 2681 SkScalar xt; 2682 if (0 == n) { 2683 SkScalar mid = SkScalarAve(y0, y2); 2684 // Need [0] and [2] if dir == 1 2685 // and [2] and [0] if dir == -1 2686 xt = y < mid ? pts[1 - dir].fX : pts[dir - 1].fX; 2687 } else { 2688 SkScalar t = roots[0]; 2689 SkScalar C = pts[0].fX; 2690 SkScalar A = pts[2].fX - 2 * pts[1].fX + C; 2691 SkScalar B = 2 * (pts[1].fX - C); 2692 xt = SkScalarMulAdd(SkScalarMulAdd(A, t, B), t, C); 2693 } 2694 return xt < x ? dir : 0; 2695} 2696 2697static bool is_mono_quad(SkScalar y0, SkScalar y1, SkScalar y2) { 2698 // return SkScalarSignAsInt(y0 - y1) + SkScalarSignAsInt(y1 - y2) != 0; 2699 if (y0 == y1) { 2700 return true; 2701 } 2702 if (y0 < y1) { 2703 return y1 <= y2; 2704 } else { 2705 return y1 >= y2; 2706 } 2707} 2708 2709static int winding_quad(const SkPoint pts[], SkScalar x, SkScalar y) { 2710 SkPoint dst[5]; 2711 int n = 0; 2712 2713 if (!is_mono_quad(pts[0].fY, pts[1].fY, pts[2].fY)) { 2714 n = SkChopQuadAtYExtrema(pts, dst); 2715 pts = dst; 2716 } 2717 int w = winding_mono_quad(pts, x, y); 2718 if (n > 0) { 2719 w += winding_mono_quad(&pts[2], x, y); 2720 } 2721 return w; 2722} 2723 2724static int winding_line(const SkPoint pts[], SkScalar x, SkScalar y) { 2725 SkScalar x0 = pts[0].fX; 2726 SkScalar y0 = pts[0].fY; 2727 SkScalar x1 = pts[1].fX; 2728 SkScalar y1 = pts[1].fY; 2729 2730 SkScalar dy = y1 - y0; 2731 2732 int dir = 1; 2733 if (y0 > y1) { 2734 SkTSwap(y0, y1); 2735 dir = -1; 2736 } 2737 if (y < y0 || y >= y1) { 2738 return 0; 2739 } 2740 2741 SkScalar cross = SkScalarMul(x1 - x0, y - pts[0].fY) - 2742 SkScalarMul(dy, x - pts[0].fX); 2743 2744 if (SkScalarSignAsInt(cross) == dir) { 2745 dir = 0; 2746 } 2747 return dir; 2748} 2749 2750static bool contains_inclusive(const SkRect& r, SkScalar x, SkScalar y) { 2751 return r.fLeft <= x && x <= r.fRight && r.fTop <= y && y <= r.fBottom; 2752} 2753 2754bool SkPath::contains(SkScalar x, SkScalar y) const { 2755 bool isInverse = this->isInverseFillType(); 2756 if (this->isEmpty()) { 2757 return isInverse; 2758 } 2759 2760 if (!contains_inclusive(this->getBounds(), x, y)) { 2761 return isInverse; 2762 } 2763 2764 SkPath::Iter iter(*this, true); 2765 bool done = false; 2766 int w = 0; 2767 do { 2768 SkPoint pts[4]; 2769 switch (iter.next(pts, false)) { 2770 case SkPath::kMove_Verb: 2771 case SkPath::kClose_Verb: 2772 break; 2773 case SkPath::kLine_Verb: 2774 w += winding_line(pts, x, y); 2775 break; 2776 case SkPath::kQuad_Verb: 2777 w += winding_quad(pts, x, y); 2778 break; 2779 case SkPath::kConic_Verb: 2780 SkASSERT(0); 2781 break; 2782 case SkPath::kCubic_Verb: 2783 w += winding_cubic(pts, x, y); 2784 break; 2785 case SkPath::kDone_Verb: 2786 done = true; 2787 break; 2788 } 2789 } while (!done); 2790 2791 switch (this->getFillType()) { 2792 case SkPath::kEvenOdd_FillType: 2793 case SkPath::kInverseEvenOdd_FillType: 2794 w &= 1; 2795 break; 2796 default: 2797 break; 2798 } 2799 return SkToBool(w); 2800} 2801