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