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