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