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