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