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 dst->swap(tmp); 1212 matrix.mapPoints(dst->fPts.begin(), dst->fPts.count()); 1213 } else { 1214 // remember that dst might == this, so be sure to check 1215 // fBoundsIsDirty before we set it 1216 if (!fBoundsIsDirty && matrix.rectStaysRect() && fPts.count() > 1) { 1217 // if we're empty, fastbounds should not be mapped 1218 matrix.mapRect(&dst->fBounds, fBounds); 1219 dst->fBoundsIsDirty = false; 1220 } else { 1221 GEN_ID_PTR_INC(dst); 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 matrix.mapPoints(dst->fPts.begin(), fPts.begin(), fPts.count()); 1233 SkDEBUGCODE(dst->validate();) 1234 } 1235 } 1236 1237 /////////////////////////////////////////////////////////////////////////////// 1238 /////////////////////////////////////////////////////////////////////////////// 1239 1240 enum SegmentState { 1241 kEmptyContour_SegmentState, // The current contour is empty. We may be 1242 // starting processing or we may have just 1243 // closed a contour. 1244 kAfterMove_SegmentState, // We have seen a move, but nothing else. 1245 kAfterPrimitive_SegmentState // We have seen a primitive but not yet 1246 // closed the path. Also the initial state. 1247 }; 1248 1249 SkPath::Iter::Iter() { 1250 #ifdef SK_DEBUG 1251 fPts = NULL; 1252 fMoveTo.fX = fMoveTo.fY = fLastPt.fX = fLastPt.fY = 0; 1253 fForceClose = fCloseLine = false; 1254 fSegmentState = kEmptyContour_SegmentState; 1255 #endif 1256 // need to init enough to make next() harmlessly return kDone_Verb 1257 fVerbs = NULL; 1258 fVerbStop = NULL; 1259 fNeedClose = false; 1260 } 1261 1262 SkPath::Iter::Iter(const SkPath& path, bool forceClose) { 1263 this->setPath(path, forceClose); 1264 } 1265 1266 void SkPath::Iter::setPath(const SkPath& path, bool forceClose) { 1267 fPts = path.fPts.begin(); 1268 fVerbs = path.fVerbs.begin(); 1269 fVerbStop = path.fVerbs.end(); 1270 fLastPt.fX = fLastPt.fY = 0; 1271 fMoveTo.fX = fMoveTo.fY = 0; 1272 fForceClose = SkToU8(forceClose); 1273 fNeedClose = false; 1274 fSegmentState = kEmptyContour_SegmentState; 1275 } 1276 1277 bool SkPath::Iter::isClosedContour() const { 1278 if (fVerbs == NULL || fVerbs == fVerbStop) { 1279 return false; 1280 } 1281 if (fForceClose) { 1282 return true; 1283 } 1284 1285 const uint8_t* verbs = fVerbs; 1286 const uint8_t* stop = fVerbStop; 1287 1288 if (kMove_Verb == *verbs) { 1289 verbs += 1; // skip the initial moveto 1290 } 1291 1292 while (verbs < stop) { 1293 unsigned v = *verbs++; 1294 if (kMove_Verb == v) { 1295 break; 1296 } 1297 if (kClose_Verb == v) { 1298 return true; 1299 } 1300 } 1301 return false; 1302 } 1303 1304 SkPath::Verb SkPath::Iter::autoClose(SkPoint pts[2]) { 1305 if (fLastPt != fMoveTo) { 1306 // A special case: if both points are NaN, SkPoint::operation== returns 1307 // false, but the iterator expects that they are treated as the same. 1308 // (consider SkPoint is a 2-dimension float point). 1309 if (SkScalarIsNaN(fLastPt.fX) || SkScalarIsNaN(fLastPt.fY) || 1310 SkScalarIsNaN(fMoveTo.fX) || SkScalarIsNaN(fMoveTo.fY)) { 1311 return kClose_Verb; 1312 } 1313 1314 if (pts) { 1315 pts[0] = fLastPt; 1316 pts[1] = fMoveTo; 1317 } 1318 fLastPt = fMoveTo; 1319 fCloseLine = true; 1320 return kLine_Verb; 1321 } else { 1322 pts[0] = fMoveTo; 1323 return kClose_Verb; 1324 } 1325 } 1326 1327 bool SkPath::Iter::cons_moveTo(SkPoint pts[1]) { 1328 if (fSegmentState == kAfterMove_SegmentState) { 1329 // Set the first return pt to the move pt 1330 if (pts) { 1331 *pts = fMoveTo; 1332 } 1333 fSegmentState = kAfterPrimitive_SegmentState; 1334 } else { 1335 SkASSERT(fSegmentState == kAfterPrimitive_SegmentState); 1336 // Set the first return pt to the last pt of the previous primitive. 1337 if (pts) { 1338 *pts = fPts[-1]; 1339 } 1340 } 1341 return false; 1342 } 1343 1344 void SkPath::Iter::consumeDegenerateSegments() { 1345 // We need to step over anything that will not move the current draw point 1346 // forward before the next move is seen 1347 const uint8_t* lastMoveVerb = 0; 1348 const SkPoint* lastMovePt = 0; 1349 SkPoint lastPt = fLastPt; 1350 while (fVerbs != fVerbStop) { 1351 unsigned verb = *fVerbs; 1352 switch (verb) { 1353 case kMove_Verb: 1354 // Keep a record of this most recent move 1355 lastMoveVerb = fVerbs; 1356 lastMovePt = fPts; 1357 lastPt = fPts[0]; 1358 fVerbs++; 1359 fPts++; 1360 break; 1361 1362 case kClose_Verb: 1363 // A close when we are in a segment is always valid 1364 if (fSegmentState == kAfterPrimitive_SegmentState) { 1365 return; 1366 } 1367 // A close at any other time must be ignored 1368 fVerbs++; 1369 break; 1370 1371 case kLine_Verb: 1372 if (!IsLineDegenerate(lastPt, fPts[0])) { 1373 if (lastMoveVerb) { 1374 fVerbs = lastMoveVerb; 1375 fPts = lastMovePt; 1376 return; 1377 } 1378 return; 1379 } 1380 // Ignore this line and continue 1381 fVerbs++; 1382 fPts++; 1383 break; 1384 1385 case kQuad_Verb: 1386 if (!IsQuadDegenerate(lastPt, fPts[0], fPts[1])) { 1387 if (lastMoveVerb) { 1388 fVerbs = lastMoveVerb; 1389 fPts = lastMovePt; 1390 return; 1391 } 1392 return; 1393 } 1394 // Ignore this line and continue 1395 fVerbs++; 1396 fPts += 2; 1397 break; 1398 1399 case kCubic_Verb: 1400 if (!IsCubicDegenerate(lastPt, fPts[0], fPts[1], fPts[2])) { 1401 if (lastMoveVerb) { 1402 fVerbs = lastMoveVerb; 1403 fPts = lastMovePt; 1404 return; 1405 } 1406 return; 1407 } 1408 // Ignore this line and continue 1409 fVerbs++; 1410 fPts += 3; 1411 break; 1412 1413 default: 1414 SkDEBUGFAIL("Should never see kDone_Verb"); 1415 } 1416 } 1417 } 1418 1419 SkPath::Verb SkPath::Iter::next(SkPoint pts[4]) { 1420 this->consumeDegenerateSegments(); 1421 1422 if (fVerbs == fVerbStop) { 1423 // Close the curve if requested and if there is some curve to close 1424 if (fNeedClose && fSegmentState == kAfterPrimitive_SegmentState) { 1425 if (kLine_Verb == this->autoClose(pts)) { 1426 return kLine_Verb; 1427 } 1428 fNeedClose = false; 1429 return kClose_Verb; 1430 } 1431 return kDone_Verb; 1432 } 1433 1434 unsigned verb = *fVerbs++; 1435 const SkPoint* srcPts = fPts; 1436 1437 switch (verb) { 1438 case kMove_Verb: 1439 if (fNeedClose) { 1440 fVerbs -= 1; 1441 verb = this->autoClose(pts); 1442 if (verb == kClose_Verb) { 1443 fNeedClose = false; 1444 } 1445 return (Verb)verb; 1446 } 1447 if (fVerbs == fVerbStop) { // might be a trailing moveto 1448 return kDone_Verb; 1449 } 1450 fMoveTo = *srcPts; 1451 if (pts) { 1452 pts[0] = *srcPts; 1453 } 1454 srcPts += 1; 1455 fSegmentState = kAfterMove_SegmentState; 1456 fLastPt = fMoveTo; 1457 fNeedClose = fForceClose; 1458 break; 1459 case kLine_Verb: 1460 if (this->cons_moveTo(pts)) { 1461 return kMove_Verb; 1462 } 1463 if (pts) { 1464 pts[1] = srcPts[0]; 1465 } 1466 fLastPt = srcPts[0]; 1467 fCloseLine = false; 1468 srcPts += 1; 1469 break; 1470 case kQuad_Verb: 1471 if (this->cons_moveTo(pts)) { 1472 return kMove_Verb; 1473 } 1474 if (pts) { 1475 memcpy(&pts[1], srcPts, 2 * sizeof(SkPoint)); 1476 } 1477 fLastPt = srcPts[1]; 1478 srcPts += 2; 1479 break; 1480 case kCubic_Verb: 1481 if (this->cons_moveTo(pts)) { 1482 return kMove_Verb; 1483 } 1484 if (pts) { 1485 memcpy(&pts[1], srcPts, 3 * sizeof(SkPoint)); 1486 } 1487 fLastPt = srcPts[2]; 1488 srcPts += 3; 1489 break; 1490 case kClose_Verb: 1491 verb = this->autoClose(pts); 1492 if (verb == kLine_Verb) { 1493 fVerbs -= 1; 1494 } else { 1495 fNeedClose = false; 1496 fSegmentState = kEmptyContour_SegmentState; 1497 } 1498 fLastPt = fMoveTo; 1499 break; 1500 } 1501 fPts = srcPts; 1502 return (Verb)verb; 1503 } 1504 1505 /////////////////////////////////////////////////////////////////////////////// 1506 1507 SkPath::RawIter::RawIter() { 1508 #ifdef SK_DEBUG 1509 fPts = NULL; 1510 fMoveTo.fX = fMoveTo.fY = fLastPt.fX = fLastPt.fY = 0; 1511 #endif 1512 // need to init enough to make next() harmlessly return kDone_Verb 1513 fVerbs = NULL; 1514 fVerbStop = NULL; 1515 } 1516 1517 SkPath::RawIter::RawIter(const SkPath& path) { 1518 this->setPath(path); 1519 } 1520 1521 void SkPath::RawIter::setPath(const SkPath& path) { 1522 fPts = path.fPts.begin(); 1523 fVerbs = path.fVerbs.begin(); 1524 fVerbStop = path.fVerbs.end(); 1525 fMoveTo.fX = fMoveTo.fY = 0; 1526 fLastPt.fX = fLastPt.fY = 0; 1527 } 1528 1529 SkPath::Verb SkPath::RawIter::next(SkPoint pts[4]) { 1530 if (fVerbs == fVerbStop) { 1531 return kDone_Verb; 1532 } 1533 1534 unsigned verb = *fVerbs++; 1535 const SkPoint* srcPts = fPts; 1536 1537 switch (verb) { 1538 case kMove_Verb: 1539 if (pts) { 1540 pts[0] = *srcPts; 1541 } 1542 fMoveTo = srcPts[0]; 1543 fLastPt = fMoveTo; 1544 srcPts += 1; 1545 break; 1546 case kLine_Verb: 1547 if (pts) { 1548 pts[0] = fLastPt; 1549 pts[1] = srcPts[0]; 1550 } 1551 fLastPt = srcPts[0]; 1552 srcPts += 1; 1553 break; 1554 case kQuad_Verb: 1555 if (pts) { 1556 pts[0] = fLastPt; 1557 memcpy(&pts[1], srcPts, 2 * sizeof(SkPoint)); 1558 } 1559 fLastPt = srcPts[1]; 1560 srcPts += 2; 1561 break; 1562 case kCubic_Verb: 1563 if (pts) { 1564 pts[0] = fLastPt; 1565 memcpy(&pts[1], srcPts, 3 * sizeof(SkPoint)); 1566 } 1567 fLastPt = srcPts[2]; 1568 srcPts += 3; 1569 break; 1570 case kClose_Verb: 1571 fLastPt = fMoveTo; 1572 if (pts) { 1573 pts[0] = fMoveTo; 1574 } 1575 break; 1576 } 1577 fPts = srcPts; 1578 return (Verb)verb; 1579 } 1580 1581 /////////////////////////////////////////////////////////////////////////////// 1582 1583 /* 1584 Format in flattened buffer: [ptCount, verbCount, pts[], verbs[]] 1585 */ 1586 1587 void SkPath::flatten(SkWriter32& buffer) const { 1588 SkDEBUGCODE(this->validate();) 1589 1590 buffer.write32(fPts.count()); 1591 buffer.write32(fVerbs.count()); 1592 buffer.write32((fFillType << 8) | fSegmentMask); 1593 buffer.writeMul4(fPts.begin(), sizeof(SkPoint) * fPts.count()); 1594 buffer.writePad(fVerbs.begin(), fVerbs.count()); 1595 } 1596 1597 void SkPath::unflatten(SkReader32& buffer) { 1598 fPts.setCount(buffer.readS32()); 1599 fVerbs.setCount(buffer.readS32()); 1600 uint32_t packed = buffer.readS32(); 1601 fFillType = packed >> 8; 1602 fSegmentMask = packed & 0xFF; 1603 buffer.read(fPts.begin(), sizeof(SkPoint) * fPts.count()); 1604 buffer.read(fVerbs.begin(), fVerbs.count()); 1605 1606 GEN_ID_INC; 1607 DIRTY_AFTER_EDIT; 1608 1609 SkDEBUGCODE(this->validate();) 1610 } 1611 1612 /////////////////////////////////////////////////////////////////////////////// 1613 1614 void SkPath::dump(bool forceClose, const char title[]) const { 1615 Iter iter(*this, forceClose); 1616 SkPoint pts[4]; 1617 Verb verb; 1618 1619 SkDebugf("path: forceClose=%s %s\n", forceClose ? "true" : "false", 1620 title ? title : ""); 1621 1622 while ((verb = iter.next(pts)) != kDone_Verb) { 1623 switch (verb) { 1624 case kMove_Verb: 1625 #ifdef SK_CAN_USE_FLOAT 1626 SkDebugf(" path: moveTo [%g %g]\n", 1627 SkScalarToFloat(pts[0].fX), SkScalarToFloat(pts[0].fY)); 1628 #else 1629 SkDebugf(" path: moveTo [%x %x]\n", pts[0].fX, pts[0].fY); 1630 #endif 1631 break; 1632 case kLine_Verb: 1633 #ifdef SK_CAN_USE_FLOAT 1634 SkDebugf(" path: lineTo [%g %g]\n", 1635 SkScalarToFloat(pts[1].fX), SkScalarToFloat(pts[1].fY)); 1636 #else 1637 SkDebugf(" path: lineTo [%x %x]\n", pts[1].fX, pts[1].fY); 1638 #endif 1639 break; 1640 case kQuad_Verb: 1641 #ifdef SK_CAN_USE_FLOAT 1642 SkDebugf(" path: quadTo [%g %g] [%g %g]\n", 1643 SkScalarToFloat(pts[1].fX), SkScalarToFloat(pts[1].fY), 1644 SkScalarToFloat(pts[2].fX), SkScalarToFloat(pts[2].fY)); 1645 #else 1646 SkDebugf(" path: quadTo [%x %x] [%x %x]\n", 1647 pts[1].fX, pts[1].fY, pts[2].fX, pts[2].fY); 1648 #endif 1649 break; 1650 case kCubic_Verb: 1651 #ifdef SK_CAN_USE_FLOAT 1652 SkDebugf(" path: cubeTo [%g %g] [%g %g] [%g %g]\n", 1653 SkScalarToFloat(pts[1].fX), SkScalarToFloat(pts[1].fY), 1654 SkScalarToFloat(pts[2].fX), SkScalarToFloat(pts[2].fY), 1655 SkScalarToFloat(pts[3].fX), SkScalarToFloat(pts[3].fY)); 1656 #else 1657 SkDebugf(" path: cubeTo [%x %x] [%x %x] [%x %x]\n", 1658 pts[1].fX, pts[1].fY, pts[2].fX, pts[2].fY, 1659 pts[3].fX, pts[3].fY); 1660 #endif 1661 break; 1662 case kClose_Verb: 1663 SkDebugf(" path: close\n"); 1664 break; 1665 default: 1666 SkDebugf(" path: UNKNOWN VERB %d, aborting dump...\n", verb); 1667 verb = kDone_Verb; // stop the loop 1668 break; 1669 } 1670 } 1671 SkDebugf("path: done %s\n", title ? title : ""); 1672 } 1673 1674 void SkPath::dump() const { 1675 this->dump(false); 1676 } 1677 1678 #ifdef SK_DEBUG 1679 void SkPath::validate() const { 1680 SkASSERT(this != NULL); 1681 SkASSERT((fFillType & ~3) == 0); 1682 fPts.validate(); 1683 fVerbs.validate(); 1684 1685 if (!fBoundsIsDirty) { 1686 SkRect bounds; 1687 compute_pt_bounds(&bounds, fPts); 1688 if (fPts.count() <= 1) { 1689 // if we're empty, fBounds may be empty but translated, so we can't 1690 // necessarily compare to bounds directly 1691 // try path.addOval(2, 2, 2, 2) which is empty, but the bounds will 1692 // be [2, 2, 2, 2] 1693 SkASSERT(bounds.isEmpty()); 1694 SkASSERT(fBounds.isEmpty()); 1695 } else { 1696 if (bounds.isEmpty()) { 1697 SkASSERT(fBounds.isEmpty()); 1698 } else { 1699 if (!fBounds.isEmpty()) { 1700 SkASSERT(fBounds.contains(bounds)); 1701 } 1702 } 1703 } 1704 } 1705 1706 uint32_t mask = 0; 1707 for (int i = 0; i < fVerbs.count(); i++) { 1708 switch (fVerbs[i]) { 1709 case kLine_Verb: 1710 mask |= kLine_SegmentMask; 1711 break; 1712 case kQuad_Verb: 1713 mask |= kQuad_SegmentMask; 1714 break; 1715 case kCubic_Verb: 1716 mask |= kCubic_SegmentMask; 1717 } 1718 } 1719 SkASSERT(mask == fSegmentMask); 1720 } 1721 #endif 1722 1723 /////////////////////////////////////////////////////////////////////////////// 1724 1725 static int sign(SkScalar x) { return x < 0; } 1726 #define kValueNeverReturnedBySign 2 1727 1728 static int CrossProductSign(const SkVector& a, const SkVector& b) { 1729 return SkScalarSignAsInt(SkPoint::CrossProduct(a, b)); 1730 } 1731 1732 // only valid for a single contour 1733 struct Convexicator { 1734 Convexicator() : fPtCount(0), fConvexity(SkPath::kConvex_Convexity) { 1735 fSign = 0; 1736 // warnings 1737 fCurrPt.set(0, 0); 1738 fVec0.set(0, 0); 1739 fVec1.set(0, 0); 1740 fFirstVec.set(0, 0); 1741 1742 fDx = fDy = 0; 1743 fSx = fSy = kValueNeverReturnedBySign; 1744 } 1745 1746 SkPath::Convexity getConvexity() const { return fConvexity; } 1747 1748 void addPt(const SkPoint& pt) { 1749 if (SkPath::kConcave_Convexity == fConvexity) { 1750 return; 1751 } 1752 1753 if (0 == fPtCount) { 1754 fCurrPt = pt; 1755 ++fPtCount; 1756 } else { 1757 SkVector vec = pt - fCurrPt; 1758 if (vec.fX || vec.fY) { 1759 fCurrPt = pt; 1760 if (++fPtCount == 2) { 1761 fFirstVec = fVec1 = vec; 1762 } else { 1763 SkASSERT(fPtCount > 2); 1764 this->addVec(vec); 1765 } 1766 1767 int sx = sign(vec.fX); 1768 int sy = sign(vec.fY); 1769 fDx += (sx != fSx); 1770 fDy += (sy != fSy); 1771 fSx = sx; 1772 fSy = sy; 1773 1774 if (fDx > 3 || fDy > 3) { 1775 fConvexity = SkPath::kConcave_Convexity; 1776 } 1777 } 1778 } 1779 } 1780 1781 void close() { 1782 if (fPtCount > 2) { 1783 this->addVec(fFirstVec); 1784 } 1785 } 1786 1787 private: 1788 void addVec(const SkVector& vec) { 1789 SkASSERT(vec.fX || vec.fY); 1790 fVec0 = fVec1; 1791 fVec1 = vec; 1792 int sign = CrossProductSign(fVec0, fVec1); 1793 if (0 == fSign) { 1794 fSign = sign; 1795 } else if (sign) { 1796 if (fSign != sign) { 1797 fConvexity = SkPath::kConcave_Convexity; 1798 } 1799 } 1800 } 1801 1802 SkPoint fCurrPt; 1803 SkVector fVec0, fVec1, fFirstVec; 1804 int fPtCount; // non-degenerate points 1805 int fSign; 1806 SkPath::Convexity fConvexity; 1807 int fDx, fDy, fSx, fSy; 1808 }; 1809 1810 SkPath::Convexity SkPath::ComputeConvexity(const SkPath& path) { 1811 SkPoint pts[4]; 1812 SkPath::Verb verb; 1813 SkPath::Iter iter(path, true); 1814 1815 int contourCount = 0; 1816 int count; 1817 Convexicator state; 1818 1819 while ((verb = iter.next(pts)) != SkPath::kDone_Verb) { 1820 switch (verb) { 1821 case kMove_Verb: 1822 if (++contourCount > 1) { 1823 return kConcave_Convexity; 1824 } 1825 pts[1] = pts[0]; 1826 count = 1; 1827 break; 1828 case kLine_Verb: count = 1; break; 1829 case kQuad_Verb: count = 2; break; 1830 case kCubic_Verb: count = 3; break; 1831 case kClose_Verb: 1832 state.close(); 1833 count = 0; 1834 break; 1835 default: 1836 SkDEBUGFAIL("bad verb"); 1837 return kConcave_Convexity; 1838 } 1839 1840 for (int i = 1; i <= count; i++) { 1841 state.addPt(pts[i]); 1842 } 1843 // early exit 1844 if (kConcave_Convexity == state.getConvexity()) { 1845 return kConcave_Convexity; 1846 } 1847 } 1848 return state.getConvexity(); 1849 } 1850 1851 /////////////////////////////////////////////////////////////////////////////// 1852 1853 class ContourIter { 1854 public: 1855 ContourIter(const SkTDArray<uint8_t>& verbs, const SkTDArray<SkPoint>& pts); 1856 1857 bool done() const { return fDone; } 1858 // if !done() then these may be called 1859 int count() const { return fCurrPtCount; } 1860 const SkPoint* pts() const { return fCurrPt; } 1861 void next(); 1862 1863 private: 1864 int fCurrPtCount; 1865 const SkPoint* fCurrPt; 1866 const uint8_t* fCurrVerb; 1867 const uint8_t* fStopVerbs; 1868 bool fDone; 1869 SkDEBUGCODE(int fContourCounter;) 1870 }; 1871 1872 ContourIter::ContourIter(const SkTDArray<uint8_t>& verbs, 1873 const SkTDArray<SkPoint>& pts) { 1874 fStopVerbs = verbs.begin() + verbs.count(); 1875 1876 fDone = false; 1877 fCurrPt = pts.begin(); 1878 fCurrVerb = verbs.begin(); 1879 fCurrPtCount = 0; 1880 SkDEBUGCODE(fContourCounter = 0;) 1881 this->next(); 1882 } 1883 1884 void ContourIter::next() { 1885 if (fCurrVerb >= fStopVerbs) { 1886 fDone = true; 1887 } 1888 if (fDone) { 1889 return; 1890 } 1891 1892 // skip pts of prev contour 1893 fCurrPt += fCurrPtCount; 1894 1895 SkASSERT(SkPath::kMove_Verb == fCurrVerb[0]); 1896 int ptCount = 1; // moveTo 1897 const uint8_t* verbs = fCurrVerb; 1898 1899 for (++verbs; verbs < fStopVerbs; ++verbs) { 1900 switch (*verbs) { 1901 case SkPath::kMove_Verb: 1902 goto CONTOUR_END; 1903 case SkPath::kLine_Verb: 1904 ptCount += 1; 1905 break; 1906 case SkPath::kQuad_Verb: 1907 ptCount += 2; 1908 break; 1909 case SkPath::kCubic_Verb: 1910 ptCount += 3; 1911 break; 1912 default: // kClose_Verb, just keep going 1913 break; 1914 } 1915 } 1916 CONTOUR_END: 1917 fCurrPtCount = ptCount; 1918 fCurrVerb = verbs; 1919 SkDEBUGCODE(++fContourCounter;) 1920 } 1921 1922 // returns cross product of (p1 - p0) and (p2 - p0) 1923 static SkScalar cross_prod(const SkPoint& p0, const SkPoint& p1, const SkPoint& p2) { 1924 SkScalar cross = SkPoint::CrossProduct(p1 - p0, p2 - p0); 1925 // We may get 0 when the above subtracts underflow. We expect this to be 1926 // very rare and lazily promote to double. 1927 if (0 == cross) { 1928 double p0x = SkScalarToDouble(p0.fX); 1929 double p0y = SkScalarToDouble(p0.fY); 1930 1931 double p1x = SkScalarToDouble(p1.fX); 1932 double p1y = SkScalarToDouble(p1.fY); 1933 1934 double p2x = SkScalarToDouble(p2.fX); 1935 double p2y = SkScalarToDouble(p2.fY); 1936 1937 cross = SkDoubleToScalar((p1x - p0x) * (p2y - p0y) - 1938 (p1y - p0y) * (p2x - p0x)); 1939 1940 } 1941 return cross; 1942 } 1943 1944 // Returns the first pt with the maximum Y coordinate 1945 static int find_max_y(const SkPoint pts[], int count) { 1946 SkASSERT(count > 0); 1947 SkScalar max = pts[0].fY; 1948 int firstIndex = 0; 1949 for (int i = 1; i < count; ++i) { 1950 SkScalar y = pts[i].fY; 1951 if (y > max) { 1952 max = y; 1953 firstIndex = i; 1954 } 1955 } 1956 return firstIndex; 1957 } 1958 1959 static int find_diff_pt(const SkPoint pts[], int index, int n, int inc) { 1960 int i = index; 1961 for (;;) { 1962 i = (i + inc) % n; 1963 if (i == index) { // we wrapped around, so abort 1964 break; 1965 } 1966 if (pts[index] != pts[i]) { // found a different point, success! 1967 break; 1968 } 1969 } 1970 return i; 1971 } 1972 1973 /** 1974 * Starting at index, and moving forward (incrementing), find the xmin and 1975 * xmax of the contiguous points that have the same Y. 1976 */ 1977 static int find_min_max_x_at_y(const SkPoint pts[], int index, int n, 1978 int* maxIndexPtr) { 1979 const SkScalar y = pts[index].fY; 1980 SkScalar min = pts[index].fX; 1981 SkScalar max = min; 1982 int minIndex = index; 1983 int maxIndex = index; 1984 for (int i = index + 1; i < n; ++i) { 1985 if (pts[i].fY != y) { 1986 break; 1987 } 1988 SkScalar x = pts[i].fX; 1989 if (x < min) { 1990 min = x; 1991 minIndex = i; 1992 } else if (x > max) { 1993 max = x; 1994 maxIndex = i; 1995 } 1996 } 1997 *maxIndexPtr = maxIndex; 1998 return minIndex; 1999 } 2000 2001 static bool crossToDir(SkScalar cross, SkPath::Direction* dir) { 2002 if (dir) { 2003 *dir = cross > 0 ? SkPath::kCW_Direction : SkPath::kCCW_Direction; 2004 } 2005 return true; 2006 } 2007 2008 #if 0 2009 #include "SkString.h" 2010 #include "../utils/SkParsePath.h" 2011 static void dumpPath(const SkPath& path) { 2012 SkString str; 2013 SkParsePath::ToSVGString(path, &str); 2014 SkDebugf("%s\n", str.c_str()); 2015 } 2016 #endif 2017 2018 /* 2019 * We loop through all contours, and keep the computed cross-product of the 2020 * contour that contained the global y-max. If we just look at the first 2021 * contour, we may find one that is wound the opposite way (correctly) since 2022 * it is the interior of a hole (e.g. 'o'). Thus we must find the contour 2023 * that is outer most (or at least has the global y-max) before we can consider 2024 * its cross product. 2025 */ 2026 bool SkPath::cheapComputeDirection(Direction* dir) const { 2027 // dumpPath(*this); 2028 // don't want to pay the cost for computing this if it 2029 // is unknown, so we don't call isConvex() 2030 const Convexity conv = this->getConvexityOrUnknown(); 2031 2032 ContourIter iter(fVerbs, fPts); 2033 2034 // initialize with our logical y-min 2035 SkScalar ymax = this->getBounds().fTop; 2036 SkScalar ymaxCross = 0; 2037 2038 for (; !iter.done(); iter.next()) { 2039 int n = iter.count(); 2040 if (n < 3) { 2041 continue; 2042 } 2043 2044 const SkPoint* pts = iter.pts(); 2045 SkScalar cross = 0; 2046 if (kConvex_Convexity == conv) { 2047 // we loop, skipping over degenerate or flat segments that will 2048 // return 0 for the cross-product 2049 for (int i = 0; i < n - 2; ++i) { 2050 cross = cross_prod(pts[i], pts[i + 1], pts[i + 2]); 2051 if (cross) { 2052 // early-exit, as kConvex is assumed to have only 1 2053 // non-degenerate contour 2054 return crossToDir(cross, dir); 2055 } 2056 } 2057 } else { 2058 int index = find_max_y(pts, n); 2059 if (pts[index].fY < ymax) { 2060 continue; 2061 } 2062 2063 // If there is more than 1 distinct point at the y-max, we take the 2064 // x-min and x-max of them and just subtract to compute the dir. 2065 if (pts[(index + 1) % n].fY == pts[index].fY) { 2066 int maxIndex; 2067 int minIndex = find_min_max_x_at_y(pts, index, n, &maxIndex); 2068 if (minIndex == maxIndex) { 2069 goto TRY_CROSSPROD; 2070 } 2071 SkASSERT(pts[minIndex].fY == pts[index].fY); 2072 SkASSERT(pts[maxIndex].fY == pts[index].fY); 2073 SkASSERT(pts[minIndex].fX <= pts[maxIndex].fX); 2074 // we just subtract the indices, and let that auto-convert to 2075 // SkScalar, since we just want - or + to signal the direction. 2076 cross = minIndex - maxIndex; 2077 } else { 2078 TRY_CROSSPROD: 2079 // Find a next and prev index to use for the cross-product test, 2080 // but we try to find pts that form non-zero vectors from pts[index] 2081 // 2082 // Its possible that we can't find two non-degenerate vectors, so 2083 // we have to guard our search (e.g. all the pts could be in the 2084 // same place). 2085 2086 // we pass n - 1 instead of -1 so we don't foul up % operator by 2087 // passing it a negative LH argument. 2088 int prev = find_diff_pt(pts, index, n, n - 1); 2089 if (prev == index) { 2090 // completely degenerate, skip to next contour 2091 continue; 2092 } 2093 int next = find_diff_pt(pts, index, n, 1); 2094 SkASSERT(next != index); 2095 cross = cross_prod(pts[prev], pts[index], pts[next]); 2096 // if we get a zero, but the pts aren't on top of each other, then 2097 // we can just look at the direction 2098 if (0 == cross) { 2099 // construct the subtract so we get the correct Direction below 2100 cross = pts[index].fX - pts[next].fX; 2101 } 2102 } 2103 2104 if (cross) { 2105 // record our best guess so far 2106 ymax = pts[index].fY; 2107 ymaxCross = cross; 2108 } 2109 } 2110 } 2111 2112 return ymaxCross ? crossToDir(ymaxCross, dir) : false; 2113 } 2114