SkPath.cpp revision 10296ccb6a63c65b2e60733a929bf15d8bf94309
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/* This guy's constructor/destructor bracket a path editing operation. It is 18 used when we know the bounds of the amount we are going to add to the path 19 (usually a new contour, but not required). 20 21 It captures some state about the path up front (i.e. if it already has a 22 cached bounds), and the if it can, it updates the cache bounds explicitly, 23 avoiding the need to revisit all of the points in getBounds(). 24 25 It also notes if the path was originally empty, and if so, sets isConvex 26 to true. Thus it can only be used if the contour being added is convex. 27 */ 28class SkAutoPathBoundsUpdate { 29public: 30 SkAutoPathBoundsUpdate(SkPath* path, const SkRect& r) : fRect(r) { 31 this->init(path); 32 } 33 34 SkAutoPathBoundsUpdate(SkPath* path, SkScalar left, SkScalar top, 35 SkScalar right, SkScalar bottom) { 36 fRect.set(left, top, right, bottom); 37 this->init(path); 38 } 39 40 ~SkAutoPathBoundsUpdate() { 41 fPath->setIsConvex(fEmpty); 42 if (fEmpty) { 43 fPath->fBounds = fRect; 44 fPath->fBoundsIsDirty = false; 45 } else if (!fDirty) { 46 fPath->fBounds.join(fRect); 47 fPath->fBoundsIsDirty = false; 48 } 49 } 50 51private: 52 SkPath* fPath; 53 SkRect fRect; 54 bool fDirty; 55 bool fEmpty; 56 57 // returns true if we should proceed 58 void init(SkPath* path) { 59 fPath = path; 60 fDirty = SkToBool(path->fBoundsIsDirty); 61 fEmpty = path->isEmpty(); 62 // Cannot use fRect for our bounds unless we know it is sorted 63 fRect.sort(); 64 } 65}; 66 67static void compute_pt_bounds(SkRect* bounds, const SkTDArray<SkPoint>& pts) { 68 if (pts.count() <= 1) { // we ignore just 1 point (moveto) 69 bounds->set(0, 0, 0, 0); 70 } else { 71 bounds->set(pts.begin(), pts.count()); 72// SkDebugf("------- compute bounds %p %d", &pts, pts.count()); 73 } 74} 75 76//////////////////////////////////////////////////////////////////////////// 77 78/* 79 Stores the verbs and points as they are given to us, with exceptions: 80 - we only record "Close" if it was immediately preceeded by Line | Quad | Cubic 81 - we insert a Move(0,0) if Line | Quad | Cubic is our first command 82 83 The iterator does more cleanup, especially if forceClose == true 84 1. if we encounter Close, return a cons'd up Line() first (if the curr-pt != start-pt) 85 2. if we encounter Move without a preceeding Close, and forceClose is true, goto #1 86 3. if we encounter Line | Quad | Cubic after Close, cons up a Move 87*/ 88 89//////////////////////////////////////////////////////////////////////////// 90 91SkPath::SkPath() : fBoundsIsDirty(true), fFillType(kWinding_FillType) { 92 fConvexity = kUnknown_Convexity; 93 fSegmentMask = 0; 94#ifdef ANDROID 95 fGenerationID = 0; 96#endif 97} 98 99SkPath::SkPath(const SkPath& src) { 100 SkDEBUGCODE(src.validate();) 101 *this = src; 102#ifdef ANDROID 103 // the assignment operator above increments the ID so correct for that here 104 fGenerationID--; 105#endif 106} 107 108SkPath::~SkPath() { 109 SkDEBUGCODE(this->validate();) 110} 111 112SkPath& SkPath::operator=(const SkPath& src) { 113 SkDEBUGCODE(src.validate();) 114 115 if (this != &src) { 116 fBounds = src.fBounds; 117 fPts = src.fPts; 118 fVerbs = src.fVerbs; 119 fFillType = src.fFillType; 120 fBoundsIsDirty = src.fBoundsIsDirty; 121 fConvexity = src.fConvexity; 122 fSegmentMask = src.fSegmentMask; 123 GEN_ID_INC; 124 } 125 SkDEBUGCODE(this->validate();) 126 return *this; 127} 128 129bool operator==(const SkPath& a, const SkPath& b) { 130 // note: don't need to look at isConvex or bounds, since just comparing the 131 // raw data is sufficient. 132 133 // We explicitly check fSegmentMask as a quick-reject. We could skip it, 134 // since it is only a cache of info in the fVerbs, but its a fast way to 135 // notice a difference 136 137 return &a == &b || 138 (a.fFillType == b.fFillType && a.fSegmentMask == b.fSegmentMask && 139 a.fVerbs == b.fVerbs && a.fPts == b.fPts); 140} 141 142void SkPath::swap(SkPath& other) { 143 SkASSERT(&other != NULL); 144 145 if (this != &other) { 146 SkTSwap<SkRect>(fBounds, other.fBounds); 147 fPts.swap(other.fPts); 148 fVerbs.swap(other.fVerbs); 149 SkTSwap<uint8_t>(fFillType, other.fFillType); 150 SkTSwap<uint8_t>(fBoundsIsDirty, other.fBoundsIsDirty); 151 SkTSwap<uint8_t>(fConvexity, other.fConvexity); 152 SkTSwap<uint8_t>(fSegmentMask, other.fSegmentMask); 153 GEN_ID_INC; 154 } 155} 156 157#ifdef ANDROID 158uint32_t SkPath::getGenerationID() const { 159 return fGenerationID; 160} 161#endif 162 163void SkPath::reset() { 164 SkDEBUGCODE(this->validate();) 165 166 fPts.reset(); 167 fVerbs.reset(); 168 GEN_ID_INC; 169 fBoundsIsDirty = true; 170 fConvexity = kUnknown_Convexity; 171 fSegmentMask = 0; 172} 173 174void SkPath::rewind() { 175 SkDEBUGCODE(this->validate();) 176 177 fPts.rewind(); 178 fVerbs.rewind(); 179 GEN_ID_INC; 180 fBoundsIsDirty = true; 181 fConvexity = kUnknown_Convexity; 182 fSegmentMask = 0; 183} 184 185bool SkPath::isEmpty() const { 186 SkDEBUGCODE(this->validate();) 187 188 int count = fVerbs.count(); 189 return count == 0 || (count == 1 && fVerbs[0] == kMove_Verb); 190} 191 192/* 193 Determines if path is a rect by keeping track of changes in direction 194 and looking for a loop either clockwise or counterclockwise. 195 196 The direction is computed such that: 197 0: vertical up 198 1: horizontal right 199 2: vertical down 200 3: horizontal left 201 202A rectangle cycles up/right/down/left or up/left/down/right. 203 204The test fails if: 205 The path is closed, and followed by a line. 206 A second move creates a new endpoint. 207 A diagonal line is parsed. 208 There's more than four changes of direction. 209 There's a discontinuity on the line (e.g., a move in the middle) 210 The line reverses direction. 211 The rectangle doesn't complete a cycle. 212 The path contains a quadratic or cubic. 213 The path contains fewer than four points. 214 The final point isn't equal to the first point. 215 216It's OK if the path has: 217 Several colinear line segments composing a rectangle side. 218 Single points on the rectangle side. 219 220The direction takes advantage of the corners found since opposite sides 221must travel in opposite directions. 222 223FIXME: Allow colinear quads and cubics to be treated like lines. 224FIXME: If the API passes fill-only, return true if the filled stroke 225 is a rectangle, though the caller failed to close the path. 226 */ 227bool SkPath::isRect(SkRect* rect) const { 228 SkDEBUGCODE(this->validate();) 229 230 int corners = 0; 231 SkPoint first, last; 232 first.set(0, 0); 233 last.set(0, 0); 234 int firstDirection = 0; 235 int lastDirection = 0; 236 int nextDirection = 0; 237 bool closedOrMoved = false; 238 bool autoClose = false; 239 const uint8_t* verbs = fVerbs.begin(); 240 const uint8_t* verbStop = fVerbs.end(); 241 const SkPoint* pts = fPts.begin(); 242 while (verbs != verbStop) { 243 switch (*verbs++) { 244 case kClose_Verb: 245 pts = fPts.begin(); 246 autoClose = true; 247 case kLine_Verb: { 248 SkScalar left = last.fX; 249 SkScalar top = last.fY; 250 SkScalar right = pts->fX; 251 SkScalar bottom = pts->fY; 252 ++pts; 253 if (left != right && top != bottom) { 254 return false; // diagonal 255 } 256 if (left == right && top == bottom) { 257 break; // single point on side OK 258 } 259 nextDirection = (left != right) << 0 | 260 (left < right || top < bottom) << 1; 261 if (0 == corners) { 262 firstDirection = nextDirection; 263 first = last; 264 last = pts[-1]; 265 corners = 1; 266 closedOrMoved = false; 267 break; 268 } 269 if (closedOrMoved) { 270 return false; // closed followed by a line 271 } 272 closedOrMoved = autoClose; 273 if (lastDirection != nextDirection) { 274 if (++corners > 4) { 275 return false; // too many direction changes 276 } 277 } 278 last = pts[-1]; 279 if (lastDirection == nextDirection) { 280 break; // colinear segment 281 } 282 // Possible values for corners are 2, 3, and 4. 283 // When corners == 3, nextDirection opposes firstDirection. 284 // Otherwise, nextDirection at corner 2 opposes corner 4. 285 int turn = firstDirection ^ (corners - 1); 286 int directionCycle = 3 == corners ? 0 : nextDirection ^ turn; 287 if ((directionCycle ^ turn) != nextDirection) { 288 return false; // direction didn't follow cycle 289 } 290 break; 291 } 292 case kQuad_Verb: 293 case kCubic_Verb: 294 return false; // quadratic, cubic not allowed 295 case kMove_Verb: 296 last = *pts++; 297 closedOrMoved = true; 298 break; 299 } 300 lastDirection = nextDirection; 301 } 302 // Success if 4 corners and first point equals last 303 bool result = 4 == corners && first == last; 304 if (result && rect) { 305 *rect = getBounds(); 306 } 307 return result; 308} 309 310int SkPath::getPoints(SkPoint copy[], int max) const { 311 SkDEBUGCODE(this->validate();) 312 313 SkASSERT(max >= 0); 314 int count = fPts.count(); 315 if (copy && max > 0 && count > 0) { 316 memcpy(copy, fPts.begin(), sizeof(SkPoint) * SkMin32(max, count)); 317 } 318 return count; 319} 320 321SkPoint SkPath::getPoint(int index) const { 322 if ((unsigned)index < (unsigned)fPts.count()) { 323 return fPts[index]; 324 } 325 return SkPoint::Make(0, 0); 326} 327 328void SkPath::getLastPt(SkPoint* lastPt) const { 329 SkDEBUGCODE(this->validate();) 330 331 if (lastPt) { 332 int count = fPts.count(); 333 if (count == 0) { 334 lastPt->set(0, 0); 335 } else { 336 *lastPt = fPts[count - 1]; 337 } 338 } 339} 340 341void SkPath::setLastPt(SkScalar x, SkScalar y) { 342 SkDEBUGCODE(this->validate();) 343 344 int count = fPts.count(); 345 if (count == 0) { 346 this->moveTo(x, y); 347 } else { 348 fPts[count - 1].set(x, y); 349 GEN_ID_INC; 350 } 351} 352 353void SkPath::computeBounds() const { 354 SkDEBUGCODE(this->validate();) 355 SkASSERT(fBoundsIsDirty); 356 357 fBoundsIsDirty = false; 358 compute_pt_bounds(&fBounds, fPts); 359} 360 361void SkPath::setConvexity(Convexity c) { 362 if (fConvexity != c) { 363 fConvexity = c; 364 GEN_ID_INC; 365 } 366} 367 368////////////////////////////////////////////////////////////////////////////// 369// Construction methods 370 371#define DIRTY_AFTER_EDIT \ 372 do { \ 373 fBoundsIsDirty = true; \ 374 fConvexity = kUnknown_Convexity;\ 375 } while (0) 376 377void SkPath::incReserve(U16CPU inc) { 378 SkDEBUGCODE(this->validate();) 379 380 fVerbs.setReserve(fVerbs.count() + inc); 381 fPts.setReserve(fPts.count() + inc); 382 383 SkDEBUGCODE(this->validate();) 384} 385 386void SkPath::moveTo(SkScalar x, SkScalar y) { 387 SkDEBUGCODE(this->validate();) 388 389 int vc = fVerbs.count(); 390 SkPoint* pt; 391 392 if (vc > 0 && fVerbs[vc - 1] == kMove_Verb) { 393 pt = &fPts[fPts.count() - 1]; 394 } else { 395 pt = fPts.append(); 396 *fVerbs.append() = kMove_Verb; 397 } 398 pt->set(x, y); 399 400 GEN_ID_INC; 401 DIRTY_AFTER_EDIT; 402} 403 404void SkPath::rMoveTo(SkScalar x, SkScalar y) { 405 SkPoint pt; 406 this->getLastPt(&pt); 407 this->moveTo(pt.fX + x, pt.fY + y); 408} 409 410void SkPath::lineTo(SkScalar x, SkScalar y) { 411 SkDEBUGCODE(this->validate();) 412 413 if (fVerbs.count() == 0) { 414 fPts.append()->set(0, 0); 415 *fVerbs.append() = kMove_Verb; 416 } 417 fPts.append()->set(x, y); 418 *fVerbs.append() = kLine_Verb; 419 fSegmentMask |= kLine_SegmentMask; 420 421 GEN_ID_INC; 422 DIRTY_AFTER_EDIT; 423} 424 425void SkPath::rLineTo(SkScalar x, SkScalar y) { 426 SkPoint pt; 427 this->getLastPt(&pt); 428 this->lineTo(pt.fX + x, pt.fY + y); 429} 430 431void SkPath::quadTo(SkScalar x1, SkScalar y1, SkScalar x2, SkScalar y2) { 432 SkDEBUGCODE(this->validate();) 433 434 if (fVerbs.count() == 0) { 435 fPts.append()->set(0, 0); 436 *fVerbs.append() = kMove_Verb; 437 } 438 439 SkPoint* pts = fPts.append(2); 440 pts[0].set(x1, y1); 441 pts[1].set(x2, y2); 442 *fVerbs.append() = kQuad_Verb; 443 fSegmentMask |= kQuad_SegmentMask; 444 445 GEN_ID_INC; 446 DIRTY_AFTER_EDIT; 447} 448 449void SkPath::rQuadTo(SkScalar x1, SkScalar y1, SkScalar x2, SkScalar y2) { 450 SkPoint pt; 451 this->getLastPt(&pt); 452 this->quadTo(pt.fX + x1, pt.fY + y1, pt.fX + x2, pt.fY + y2); 453} 454 455void SkPath::cubicTo(SkScalar x1, SkScalar y1, SkScalar x2, SkScalar y2, 456 SkScalar x3, SkScalar y3) { 457 SkDEBUGCODE(this->validate();) 458 459 if (fVerbs.count() == 0) { 460 fPts.append()->set(0, 0); 461 *fVerbs.append() = kMove_Verb; 462 } 463 SkPoint* pts = fPts.append(3); 464 pts[0].set(x1, y1); 465 pts[1].set(x2, y2); 466 pts[2].set(x3, y3); 467 *fVerbs.append() = kCubic_Verb; 468 fSegmentMask |= kCubic_SegmentMask; 469 470 GEN_ID_INC; 471 DIRTY_AFTER_EDIT; 472} 473 474void SkPath::rCubicTo(SkScalar x1, SkScalar y1, SkScalar x2, SkScalar y2, 475 SkScalar x3, SkScalar y3) { 476 SkPoint pt; 477 this->getLastPt(&pt); 478 this->cubicTo(pt.fX + x1, pt.fY + y1, pt.fX + x2, pt.fY + y2, 479 pt.fX + x3, pt.fY + y3); 480} 481 482void SkPath::close() { 483 SkDEBUGCODE(this->validate();) 484 485 int count = fVerbs.count(); 486 if (count > 0) { 487 switch (fVerbs[count - 1]) { 488 case kLine_Verb: 489 case kQuad_Verb: 490 case kCubic_Verb: 491 *fVerbs.append() = kClose_Verb; 492 GEN_ID_INC; 493 break; 494 default: 495 // don't add a close if the prev wasn't a primitive 496 break; 497 } 498 } 499} 500 501/////////////////////////////////////////////////////////////////////////////// 502 503void SkPath::addRect(const SkRect& rect, Direction dir) { 504 this->addRect(rect.fLeft, rect.fTop, rect.fRight, rect.fBottom, dir); 505} 506 507void SkPath::addRect(SkScalar left, SkScalar top, SkScalar right, 508 SkScalar bottom, Direction dir) { 509 SkAutoPathBoundsUpdate apbu(this, left, top, right, bottom); 510 511 this->incReserve(5); 512 513 this->moveTo(left, top); 514 if (dir == kCCW_Direction) { 515 this->lineTo(left, bottom); 516 this->lineTo(right, bottom); 517 this->lineTo(right, top); 518 } else { 519 this->lineTo(right, top); 520 this->lineTo(right, bottom); 521 this->lineTo(left, bottom); 522 } 523 this->close(); 524} 525 526#define CUBIC_ARC_FACTOR ((SK_ScalarSqrt2 - SK_Scalar1) * 4 / 3) 527 528void SkPath::addRoundRect(const SkRect& rect, SkScalar rx, SkScalar ry, 529 Direction dir) { 530 SkScalar w = rect.width(); 531 SkScalar halfW = SkScalarHalf(w); 532 SkScalar h = rect.height(); 533 SkScalar halfH = SkScalarHalf(h); 534 535 if (halfW <= 0 || halfH <= 0) { 536 return; 537 } 538 539 bool skip_hori = rx >= halfW; 540 bool skip_vert = ry >= halfH; 541 542 if (skip_hori && skip_vert) { 543 this->addOval(rect, dir); 544 return; 545 } 546 547 SkAutoPathBoundsUpdate apbu(this, rect); 548 549 if (skip_hori) { 550 rx = halfW; 551 } else if (skip_vert) { 552 ry = halfH; 553 } 554 555 SkScalar sx = SkScalarMul(rx, CUBIC_ARC_FACTOR); 556 SkScalar sy = SkScalarMul(ry, CUBIC_ARC_FACTOR); 557 558 this->incReserve(17); 559 this->moveTo(rect.fRight - rx, rect.fTop); 560 if (dir == kCCW_Direction) { 561 if (!skip_hori) { 562 this->lineTo(rect.fLeft + rx, rect.fTop); // top 563 } 564 this->cubicTo(rect.fLeft + rx - sx, rect.fTop, 565 rect.fLeft, rect.fTop + ry - sy, 566 rect.fLeft, rect.fTop + ry); // top-left 567 if (!skip_vert) { 568 this->lineTo(rect.fLeft, rect.fBottom - ry); // left 569 } 570 this->cubicTo(rect.fLeft, rect.fBottom - ry + sy, 571 rect.fLeft + rx - sx, rect.fBottom, 572 rect.fLeft + rx, rect.fBottom); // bot-left 573 if (!skip_hori) { 574 this->lineTo(rect.fRight - rx, rect.fBottom); // bottom 575 } 576 this->cubicTo(rect.fRight - rx + sx, rect.fBottom, 577 rect.fRight, rect.fBottom - ry + sy, 578 rect.fRight, rect.fBottom - ry); // bot-right 579 if (!skip_vert) { 580 this->lineTo(rect.fRight, rect.fTop + ry); 581 } 582 this->cubicTo(rect.fRight, rect.fTop + ry - sy, 583 rect.fRight - rx + sx, rect.fTop, 584 rect.fRight - rx, rect.fTop); // top-right 585 } else { 586 this->cubicTo(rect.fRight - rx + sx, rect.fTop, 587 rect.fRight, rect.fTop + ry - sy, 588 rect.fRight, rect.fTop + ry); // top-right 589 if (!skip_vert) { 590 this->lineTo(rect.fRight, rect.fBottom - ry); 591 } 592 this->cubicTo(rect.fRight, rect.fBottom - ry + sy, 593 rect.fRight - rx + sx, rect.fBottom, 594 rect.fRight - rx, rect.fBottom); // bot-right 595 if (!skip_hori) { 596 this->lineTo(rect.fLeft + rx, rect.fBottom); // bottom 597 } 598 this->cubicTo(rect.fLeft + rx - sx, rect.fBottom, 599 rect.fLeft, rect.fBottom - ry + sy, 600 rect.fLeft, rect.fBottom - ry); // bot-left 601 if (!skip_vert) { 602 this->lineTo(rect.fLeft, rect.fTop + ry); // left 603 } 604 this->cubicTo(rect.fLeft, rect.fTop + ry - sy, 605 rect.fLeft + rx - sx, rect.fTop, 606 rect.fLeft + rx, rect.fTop); // top-left 607 if (!skip_hori) { 608 this->lineTo(rect.fRight - rx, rect.fTop); // top 609 } 610 } 611 this->close(); 612} 613 614static void add_corner_arc(SkPath* path, const SkRect& rect, 615 SkScalar rx, SkScalar ry, int startAngle, 616 SkPath::Direction dir, bool forceMoveTo) { 617 rx = SkMinScalar(SkScalarHalf(rect.width()), rx); 618 ry = SkMinScalar(SkScalarHalf(rect.height()), ry); 619 620 SkRect r; 621 r.set(-rx, -ry, rx, ry); 622 623 switch (startAngle) { 624 case 0: 625 r.offset(rect.fRight - r.fRight, rect.fBottom - r.fBottom); 626 break; 627 case 90: 628 r.offset(rect.fLeft - r.fLeft, rect.fBottom - r.fBottom); 629 break; 630 case 180: r.offset(rect.fLeft - r.fLeft, rect.fTop - r.fTop); break; 631 case 270: r.offset(rect.fRight - r.fRight, rect.fTop - r.fTop); break; 632 default: SkASSERT(!"unexpected startAngle in add_corner_arc"); 633 } 634 635 SkScalar start = SkIntToScalar(startAngle); 636 SkScalar sweep = SkIntToScalar(90); 637 if (SkPath::kCCW_Direction == dir) { 638 start += sweep; 639 sweep = -sweep; 640 } 641 642 path->arcTo(r, start, sweep, forceMoveTo); 643} 644 645void SkPath::addRoundRect(const SkRect& rect, const SkScalar rad[], 646 Direction dir) { 647 // abort before we invoke SkAutoPathBoundsUpdate() 648 if (rect.isEmpty()) { 649 return; 650 } 651 652 SkAutoPathBoundsUpdate apbu(this, rect); 653 654 if (kCW_Direction == dir) { 655 add_corner_arc(this, rect, rad[0], rad[1], 180, dir, true); 656 add_corner_arc(this, rect, rad[2], rad[3], 270, dir, false); 657 add_corner_arc(this, rect, rad[4], rad[5], 0, dir, false); 658 add_corner_arc(this, rect, rad[6], rad[7], 90, dir, false); 659 } else { 660 add_corner_arc(this, rect, rad[0], rad[1], 180, dir, true); 661 add_corner_arc(this, rect, rad[6], rad[7], 90, dir, false); 662 add_corner_arc(this, rect, rad[4], rad[5], 0, dir, false); 663 add_corner_arc(this, rect, rad[2], rad[3], 270, dir, false); 664 } 665 this->close(); 666} 667 668void SkPath::addOval(const SkRect& oval, Direction dir) { 669 SkAutoPathBoundsUpdate apbu(this, oval); 670 671 SkScalar cx = oval.centerX(); 672 SkScalar cy = oval.centerY(); 673 SkScalar rx = SkScalarHalf(oval.width()); 674 SkScalar ry = SkScalarHalf(oval.height()); 675#if 0 // these seem faster than using quads (1/2 the number of edges) 676 SkScalar sx = SkScalarMul(rx, CUBIC_ARC_FACTOR); 677 SkScalar sy = SkScalarMul(ry, CUBIC_ARC_FACTOR); 678 679 this->incReserve(13); 680 this->moveTo(cx + rx, cy); 681 if (dir == kCCW_Direction) { 682 this->cubicTo(cx + rx, cy - sy, cx + sx, cy - ry, cx, cy - ry); 683 this->cubicTo(cx - sx, cy - ry, cx - rx, cy - sy, cx - rx, cy); 684 this->cubicTo(cx - rx, cy + sy, cx - sx, cy + ry, cx, cy + ry); 685 this->cubicTo(cx + sx, cy + ry, cx + rx, cy + sy, cx + rx, cy); 686 } else { 687 this->cubicTo(cx + rx, cy + sy, cx + sx, cy + ry, cx, cy + ry); 688 this->cubicTo(cx - sx, cy + ry, cx - rx, cy + sy, cx - rx, cy); 689 this->cubicTo(cx - rx, cy - sy, cx - sx, cy - ry, cx, cy - ry); 690 this->cubicTo(cx + sx, cy - ry, cx + rx, cy - sy, cx + rx, cy); 691 } 692#else 693 SkScalar sx = SkScalarMul(rx, SK_ScalarTanPIOver8); 694 SkScalar sy = SkScalarMul(ry, SK_ScalarTanPIOver8); 695 SkScalar mx = SkScalarMul(rx, SK_ScalarRoot2Over2); 696 SkScalar my = SkScalarMul(ry, SK_ScalarRoot2Over2); 697 698 /* 699 To handle imprecision in computing the center and radii, we revert to 700 the provided bounds when we can (i.e. use oval.fLeft instead of cx-rx) 701 to ensure that we don't exceed the oval's bounds *ever*, since we want 702 to use oval for our fast-bounds, rather than have to recompute it. 703 */ 704 const SkScalar L = oval.fLeft; // cx - rx 705 const SkScalar T = oval.fTop; // cy - ry 706 const SkScalar R = oval.fRight; // cx + rx 707 const SkScalar B = oval.fBottom; // cy + ry 708 709 this->incReserve(17); // 8 quads + close 710 this->moveTo(R, cy); 711 if (dir == kCCW_Direction) { 712 this->quadTo( R, cy - sy, cx + mx, cy - my); 713 this->quadTo(cx + sx, T, cx , T); 714 this->quadTo(cx - sx, T, cx - mx, cy - my); 715 this->quadTo( L, cy - sy, L, cy ); 716 this->quadTo( L, cy + sy, cx - mx, cy + my); 717 this->quadTo(cx - sx, B, cx , B); 718 this->quadTo(cx + sx, B, cx + mx, cy + my); 719 this->quadTo( R, cy + sy, R, cy ); 720 } else { 721 this->quadTo( R, cy + sy, cx + mx, cy + my); 722 this->quadTo(cx + sx, B, cx , B); 723 this->quadTo(cx - sx, B, cx - mx, cy + my); 724 this->quadTo( L, cy + sy, L, cy ); 725 this->quadTo( L, cy - sy, cx - mx, cy - my); 726 this->quadTo(cx - sx, T, cx , T); 727 this->quadTo(cx + sx, T, cx + mx, cy - my); 728 this->quadTo( R, cy - sy, R, cy ); 729 } 730#endif 731 this->close(); 732} 733 734void SkPath::addCircle(SkScalar x, SkScalar y, SkScalar r, Direction dir) { 735 if (r > 0) { 736 SkRect rect; 737 rect.set(x - r, y - r, x + r, y + r); 738 this->addOval(rect, dir); 739 } 740} 741 742#include "SkGeometry.h" 743 744static int build_arc_points(const SkRect& oval, SkScalar startAngle, 745 SkScalar sweepAngle, 746 SkPoint pts[kSkBuildQuadArcStorage]) { 747 SkVector start, stop; 748 749 start.fY = SkScalarSinCos(SkDegreesToRadians(startAngle), &start.fX); 750 stop.fY = SkScalarSinCos(SkDegreesToRadians(startAngle + sweepAngle), 751 &stop.fX); 752 753 /* If the sweep angle is nearly (but less than) 360, then due to precision 754 loss in radians-conversion and/or sin/cos, we may end up with coincident 755 vectors, which will fool SkBuildQuadArc into doing nothing (bad) instead 756 of drawing a nearly complete circle (good). 757 e.g. canvas.drawArc(0, 359.99, ...) 758 -vs- canvas.drawArc(0, 359.9, ...) 759 We try to detect this edge case, and tweak the stop vector 760 */ 761 if (start == stop) { 762 SkScalar sw = SkScalarAbs(sweepAngle); 763 if (sw < SkIntToScalar(360) && sw > SkIntToScalar(359)) { 764 SkScalar stopRad = SkDegreesToRadians(startAngle + sweepAngle); 765 // make a guess at a tiny angle (in radians) to tweak by 766 SkScalar deltaRad = SkScalarCopySign(SK_Scalar1/512, sweepAngle); 767 // not sure how much will be enough, so we use a loop 768 do { 769 stopRad -= deltaRad; 770 stop.fY = SkScalarSinCos(stopRad, &stop.fX); 771 } while (start == stop); 772 } 773 } 774 775 SkMatrix matrix; 776 777 matrix.setScale(SkScalarHalf(oval.width()), SkScalarHalf(oval.height())); 778 matrix.postTranslate(oval.centerX(), oval.centerY()); 779 780 return SkBuildQuadArc(start, stop, 781 sweepAngle > 0 ? kCW_SkRotationDirection : kCCW_SkRotationDirection, 782 &matrix, pts); 783} 784 785void SkPath::arcTo(const SkRect& oval, SkScalar startAngle, SkScalar sweepAngle, 786 bool forceMoveTo) { 787 if (oval.width() < 0 || oval.height() < 0) { 788 return; 789 } 790 791 SkPoint pts[kSkBuildQuadArcStorage]; 792 int count = build_arc_points(oval, startAngle, sweepAngle, pts); 793 SkASSERT((count & 1) == 1); 794 795 if (fVerbs.count() == 0) { 796 forceMoveTo = true; 797 } 798 this->incReserve(count); 799 forceMoveTo ? this->moveTo(pts[0]) : this->lineTo(pts[0]); 800 for (int i = 1; i < count; i += 2) { 801 this->quadTo(pts[i], pts[i+1]); 802 } 803} 804 805void SkPath::addArc(const SkRect& oval, SkScalar startAngle, 806 SkScalar sweepAngle) { 807 if (oval.isEmpty() || 0 == sweepAngle) { 808 return; 809 } 810 811 const SkScalar kFullCircleAngle = SkIntToScalar(360); 812 813 if (sweepAngle >= kFullCircleAngle || sweepAngle <= -kFullCircleAngle) { 814 this->addOval(oval, sweepAngle > 0 ? kCW_Direction : kCCW_Direction); 815 return; 816 } 817 818 SkPoint pts[kSkBuildQuadArcStorage]; 819 int count = build_arc_points(oval, startAngle, sweepAngle, pts); 820 821 this->incReserve(count); 822 this->moveTo(pts[0]); 823 for (int i = 1; i < count; i += 2) { 824 this->quadTo(pts[i], pts[i+1]); 825 } 826} 827 828/* 829 Need to handle the case when the angle is sharp, and our computed end-points 830 for the arc go behind pt1 and/or p2... 831*/ 832void SkPath::arcTo(SkScalar x1, SkScalar y1, SkScalar x2, SkScalar y2, 833 SkScalar radius) { 834 SkVector before, after; 835 836 // need to know our prev pt so we can construct tangent vectors 837 { 838 SkPoint start; 839 this->getLastPt(&start); 840 // Handle degenerate cases by adding a line to the first point and 841 // bailing out. 842 if ((x1 == start.fX && y1 == start.fY) || 843 (x1 == x2 && y1 == y2) || 844 radius == 0) { 845 this->lineTo(x1, y1); 846 return; 847 } 848 before.setNormalize(x1 - start.fX, y1 - start.fY); 849 after.setNormalize(x2 - x1, y2 - y1); 850 } 851 852 SkScalar cosh = SkPoint::DotProduct(before, after); 853 SkScalar sinh = SkPoint::CrossProduct(before, after); 854 855 if (SkScalarNearlyZero(sinh)) { // angle is too tight 856 this->lineTo(x1, y1); 857 return; 858 } 859 860 SkScalar dist = SkScalarMulDiv(radius, SK_Scalar1 - cosh, sinh); 861 if (dist < 0) { 862 dist = -dist; 863 } 864 865 SkScalar xx = x1 - SkScalarMul(dist, before.fX); 866 SkScalar yy = y1 - SkScalarMul(dist, before.fY); 867 SkRotationDirection arcDir; 868 869 // now turn before/after into normals 870 if (sinh > 0) { 871 before.rotateCCW(); 872 after.rotateCCW(); 873 arcDir = kCW_SkRotationDirection; 874 } else { 875 before.rotateCW(); 876 after.rotateCW(); 877 arcDir = kCCW_SkRotationDirection; 878 } 879 880 SkMatrix matrix; 881 SkPoint pts[kSkBuildQuadArcStorage]; 882 883 matrix.setScale(radius, radius); 884 matrix.postTranslate(xx - SkScalarMul(radius, before.fX), 885 yy - SkScalarMul(radius, before.fY)); 886 887 int count = SkBuildQuadArc(before, after, arcDir, &matrix, pts); 888 889 this->incReserve(count); 890 // [xx,yy] == pts[0] 891 this->lineTo(xx, yy); 892 for (int i = 1; i < count; i += 2) { 893 this->quadTo(pts[i], pts[i+1]); 894 } 895} 896 897/////////////////////////////////////////////////////////////////////////////// 898 899void SkPath::addPath(const SkPath& path, SkScalar dx, SkScalar dy) { 900 SkMatrix matrix; 901 902 matrix.setTranslate(dx, dy); 903 this->addPath(path, matrix); 904} 905 906void SkPath::addPath(const SkPath& path, const SkMatrix& matrix) { 907 this->incReserve(path.fPts.count()); 908 909 Iter iter(path, false); 910 SkPoint pts[4]; 911 Verb verb; 912 913 SkMatrix::MapPtsProc proc = matrix.getMapPtsProc(); 914 915 while ((verb = iter.next(pts)) != kDone_Verb) { 916 switch (verb) { 917 case kMove_Verb: 918 proc(matrix, &pts[0], &pts[0], 1); 919 this->moveTo(pts[0]); 920 break; 921 case kLine_Verb: 922 proc(matrix, &pts[1], &pts[1], 1); 923 this->lineTo(pts[1]); 924 break; 925 case kQuad_Verb: 926 proc(matrix, &pts[1], &pts[1], 2); 927 this->quadTo(pts[1], pts[2]); 928 break; 929 case kCubic_Verb: 930 proc(matrix, &pts[1], &pts[1], 3); 931 this->cubicTo(pts[1], pts[2], pts[3]); 932 break; 933 case kClose_Verb: 934 this->close(); 935 break; 936 default: 937 SkASSERT(!"unknown verb"); 938 } 939 } 940} 941 942/////////////////////////////////////////////////////////////////////////////// 943 944static const uint8_t gPtsInVerb[] = { 945 1, // kMove 946 1, // kLine 947 2, // kQuad 948 3, // kCubic 949 0, // kClose 950 0 // kDone 951}; 952 953// ignore the initial moveto, and stop when the 1st contour ends 954void SkPath::pathTo(const SkPath& path) { 955 int i, vcount = path.fVerbs.count(); 956 if (vcount == 0) { 957 return; 958 } 959 960 this->incReserve(vcount); 961 962 const uint8_t* verbs = path.fVerbs.begin(); 963 const SkPoint* pts = path.fPts.begin() + 1; // 1 for the initial moveTo 964 965 SkASSERT(verbs[0] == kMove_Verb); 966 for (i = 1; i < vcount; i++) { 967 switch (verbs[i]) { 968 case kLine_Verb: 969 this->lineTo(pts[0].fX, pts[0].fY); 970 break; 971 case kQuad_Verb: 972 this->quadTo(pts[0].fX, pts[0].fY, pts[1].fX, pts[1].fY); 973 break; 974 case kCubic_Verb: 975 this->cubicTo(pts[0].fX, pts[0].fY, pts[1].fX, pts[1].fY, 976 pts[2].fX, pts[2].fY); 977 break; 978 case kClose_Verb: 979 return; 980 } 981 pts += gPtsInVerb[verbs[i]]; 982 } 983} 984 985// ignore the last point of the 1st contour 986void SkPath::reversePathTo(const SkPath& path) { 987 int i, vcount = path.fVerbs.count(); 988 if (vcount == 0) { 989 return; 990 } 991 992 this->incReserve(vcount); 993 994 const uint8_t* verbs = path.fVerbs.begin(); 995 const SkPoint* pts = path.fPts.begin(); 996 997 SkASSERT(verbs[0] == kMove_Verb); 998 for (i = 1; i < vcount; i++) { 999 int n = gPtsInVerb[verbs[i]]; 1000 if (n == 0) { 1001 break; 1002 } 1003 pts += n; 1004 } 1005 1006 while (--i > 0) { 1007 switch (verbs[i]) { 1008 case kLine_Verb: 1009 this->lineTo(pts[-1].fX, pts[-1].fY); 1010 break; 1011 case kQuad_Verb: 1012 this->quadTo(pts[-1].fX, pts[-1].fY, pts[-2].fX, pts[-2].fY); 1013 break; 1014 case kCubic_Verb: 1015 this->cubicTo(pts[-1].fX, pts[-1].fY, pts[-2].fX, pts[-2].fY, 1016 pts[-3].fX, pts[-3].fY); 1017 break; 1018 default: 1019 SkASSERT(!"bad verb"); 1020 break; 1021 } 1022 pts -= gPtsInVerb[verbs[i]]; 1023 } 1024} 1025 1026/////////////////////////////////////////////////////////////////////////////// 1027 1028void SkPath::offset(SkScalar dx, SkScalar dy, SkPath* dst) const { 1029 SkMatrix matrix; 1030 1031 matrix.setTranslate(dx, dy); 1032 this->transform(matrix, dst); 1033} 1034 1035#include "SkGeometry.h" 1036 1037static void subdivide_quad_to(SkPath* path, const SkPoint pts[3], 1038 int level = 2) { 1039 if (--level >= 0) { 1040 SkPoint tmp[5]; 1041 1042 SkChopQuadAtHalf(pts, tmp); 1043 subdivide_quad_to(path, &tmp[0], level); 1044 subdivide_quad_to(path, &tmp[2], level); 1045 } else { 1046 path->quadTo(pts[1], pts[2]); 1047 } 1048} 1049 1050static void subdivide_cubic_to(SkPath* path, const SkPoint pts[4], 1051 int level = 2) { 1052 if (--level >= 0) { 1053 SkPoint tmp[7]; 1054 1055 SkChopCubicAtHalf(pts, tmp); 1056 subdivide_cubic_to(path, &tmp[0], level); 1057 subdivide_cubic_to(path, &tmp[3], level); 1058 } else { 1059 path->cubicTo(pts[1], pts[2], pts[3]); 1060 } 1061} 1062 1063void SkPath::transform(const SkMatrix& matrix, SkPath* dst) const { 1064 SkDEBUGCODE(this->validate();) 1065 if (dst == NULL) { 1066 dst = (SkPath*)this; 1067 } 1068 1069 if (matrix.hasPerspective()) { 1070 SkPath tmp; 1071 tmp.fFillType = fFillType; 1072 1073 SkPath::Iter iter(*this, false); 1074 SkPoint pts[4]; 1075 SkPath::Verb verb; 1076 1077 while ((verb = iter.next(pts)) != kDone_Verb) { 1078 switch (verb) { 1079 case kMove_Verb: 1080 tmp.moveTo(pts[0]); 1081 break; 1082 case kLine_Verb: 1083 tmp.lineTo(pts[1]); 1084 break; 1085 case kQuad_Verb: 1086 subdivide_quad_to(&tmp, pts); 1087 break; 1088 case kCubic_Verb: 1089 subdivide_cubic_to(&tmp, pts); 1090 break; 1091 case kClose_Verb: 1092 tmp.close(); 1093 break; 1094 default: 1095 SkASSERT(!"unknown verb"); 1096 break; 1097 } 1098 } 1099 1100 dst->swap(tmp); 1101 matrix.mapPoints(dst->fPts.begin(), dst->fPts.count()); 1102 } else { 1103 // remember that dst might == this, so be sure to check 1104 // fBoundsIsDirty before we set it 1105 if (!fBoundsIsDirty && matrix.rectStaysRect() && fPts.count() > 1) { 1106 // if we're empty, fastbounds should not be mapped 1107 matrix.mapRect(&dst->fBounds, fBounds); 1108 dst->fBoundsIsDirty = false; 1109 } else { 1110 GEN_ID_PTR_INC(dst); 1111 dst->fBoundsIsDirty = true; 1112 } 1113 1114 if (this != dst) { 1115 dst->fVerbs = fVerbs; 1116 dst->fPts.setCount(fPts.count()); 1117 dst->fFillType = fFillType; 1118 } 1119 matrix.mapPoints(dst->fPts.begin(), fPts.begin(), fPts.count()); 1120 SkDEBUGCODE(dst->validate();) 1121 } 1122} 1123 1124/////////////////////////////////////////////////////////////////////////////// 1125/////////////////////////////////////////////////////////////////////////////// 1126 1127enum NeedMoveToState { 1128 kAfterClose_NeedMoveToState, 1129 kAfterCons_NeedMoveToState, 1130 kAfterPrefix_NeedMoveToState 1131}; 1132 1133SkPath::Iter::Iter() { 1134#ifdef SK_DEBUG 1135 fPts = NULL; 1136 fMoveTo.fX = fMoveTo.fY = fLastPt.fX = fLastPt.fY = 0; 1137 fForceClose = fNeedMoveTo = fCloseLine = false; 1138#endif 1139 // need to init enough to make next() harmlessly return kDone_Verb 1140 fVerbs = NULL; 1141 fVerbStop = NULL; 1142 fNeedClose = false; 1143} 1144 1145SkPath::Iter::Iter(const SkPath& path, bool forceClose) { 1146 this->setPath(path, forceClose); 1147} 1148 1149void SkPath::Iter::setPath(const SkPath& path, bool forceClose) { 1150 fPts = path.fPts.begin(); 1151 fVerbs = path.fVerbs.begin(); 1152 fVerbStop = path.fVerbs.end(); 1153 fForceClose = SkToU8(forceClose); 1154 fNeedClose = false; 1155 fNeedMoveTo = kAfterPrefix_NeedMoveToState; 1156} 1157 1158bool SkPath::Iter::isClosedContour() const { 1159 if (fVerbs == NULL || fVerbs == fVerbStop) { 1160 return false; 1161 } 1162 if (fForceClose) { 1163 return true; 1164 } 1165 1166 const uint8_t* verbs = fVerbs; 1167 const uint8_t* stop = fVerbStop; 1168 1169 if (kMove_Verb == *verbs) { 1170 verbs += 1; // skip the initial moveto 1171 } 1172 1173 while (verbs < stop) { 1174 unsigned v = *verbs++; 1175 if (kMove_Verb == v) { 1176 break; 1177 } 1178 if (kClose_Verb == v) { 1179 return true; 1180 } 1181 } 1182 return false; 1183} 1184 1185SkPath::Verb SkPath::Iter::autoClose(SkPoint pts[2]) { 1186 if (fLastPt != fMoveTo) { 1187 // A special case: if both points are NaN, SkPoint::operation== returns 1188 // false, but the iterator expects that they are treated as the same. 1189 // (consider SkPoint is a 2-dimension float point). 1190 if (SkScalarIsNaN(fLastPt.fX) || SkScalarIsNaN(fLastPt.fY) || 1191 SkScalarIsNaN(fMoveTo.fX) || SkScalarIsNaN(fMoveTo.fY)) { 1192 return kClose_Verb; 1193 } 1194 1195 if (pts) { 1196 pts[0] = fLastPt; 1197 pts[1] = fMoveTo; 1198 } 1199 fLastPt = fMoveTo; 1200 fCloseLine = true; 1201 return kLine_Verb; 1202 } else { 1203 pts[0] = fMoveTo; 1204 return kClose_Verb; 1205 } 1206} 1207 1208bool SkPath::Iter::cons_moveTo(SkPoint pts[1]) { 1209 if (fNeedMoveTo == kAfterClose_NeedMoveToState) { 1210 if (pts) { 1211 *pts = fMoveTo; 1212 } 1213 fNeedClose = fForceClose; 1214 fNeedMoveTo = kAfterCons_NeedMoveToState; 1215 fVerbs -= 1; 1216 return true; 1217 } 1218 1219 if (fNeedMoveTo == kAfterCons_NeedMoveToState) { 1220 if (pts) { 1221 *pts = fMoveTo; 1222 } 1223 fNeedMoveTo = kAfterPrefix_NeedMoveToState; 1224 } else { 1225 SkASSERT(fNeedMoveTo == kAfterPrefix_NeedMoveToState); 1226 if (pts) { 1227 *pts = fPts[-1]; 1228 } 1229 } 1230 return false; 1231} 1232 1233SkPath::Verb SkPath::Iter::next(SkPoint pts[4]) { 1234 if (fVerbs == fVerbStop) { 1235 if (fNeedClose) { 1236 if (kLine_Verb == this->autoClose(pts)) { 1237 return kLine_Verb; 1238 } 1239 fNeedClose = false; 1240 return kClose_Verb; 1241 } 1242 return kDone_Verb; 1243 } 1244 1245 unsigned verb = *fVerbs++; 1246 const SkPoint* srcPts = fPts; 1247 1248 switch (verb) { 1249 case kMove_Verb: 1250 if (fNeedClose) { 1251 fVerbs -= 1; 1252 verb = this->autoClose(pts); 1253 if (verb == kClose_Verb) { 1254 fNeedClose = false; 1255 } 1256 return (Verb)verb; 1257 } 1258 if (fVerbs == fVerbStop) { // might be a trailing moveto 1259 return kDone_Verb; 1260 } 1261 fMoveTo = *srcPts; 1262 if (pts) { 1263 pts[0] = *srcPts; 1264 } 1265 srcPts += 1; 1266 fNeedMoveTo = kAfterCons_NeedMoveToState; 1267 fNeedClose = fForceClose; 1268 break; 1269 case kLine_Verb: 1270 if (this->cons_moveTo(pts)) { 1271 return kMove_Verb; 1272 } 1273 if (pts) { 1274 pts[1] = srcPts[0]; 1275 } 1276 fLastPt = srcPts[0]; 1277 fCloseLine = false; 1278 srcPts += 1; 1279 break; 1280 case kQuad_Verb: 1281 if (this->cons_moveTo(pts)) { 1282 return kMove_Verb; 1283 } 1284 if (pts) { 1285 memcpy(&pts[1], srcPts, 2 * sizeof(SkPoint)); 1286 } 1287 fLastPt = srcPts[1]; 1288 srcPts += 2; 1289 break; 1290 case kCubic_Verb: 1291 if (this->cons_moveTo(pts)) { 1292 return kMove_Verb; 1293 } 1294 if (pts) { 1295 memcpy(&pts[1], srcPts, 3 * sizeof(SkPoint)); 1296 } 1297 fLastPt = srcPts[2]; 1298 srcPts += 3; 1299 break; 1300 case kClose_Verb: 1301 verb = this->autoClose(pts); 1302 if (verb == kLine_Verb) { 1303 fVerbs -= 1; 1304 } else { 1305 fNeedClose = false; 1306 } 1307 fNeedMoveTo = kAfterClose_NeedMoveToState; 1308 break; 1309 } 1310 fPts = srcPts; 1311 return (Verb)verb; 1312} 1313 1314/////////////////////////////////////////////////////////////////////////////// 1315 1316/* 1317 Format in flattened buffer: [ptCount, verbCount, pts[], verbs[]] 1318*/ 1319 1320void SkPath::flatten(SkWriter32& buffer) const { 1321 SkDEBUGCODE(this->validate();) 1322 1323 buffer.write32(fPts.count()); 1324 buffer.write32(fVerbs.count()); 1325 buffer.write32(fFillType); 1326 buffer.writeMul4(fPts.begin(), sizeof(SkPoint) * fPts.count()); 1327 buffer.writePad(fVerbs.begin(), fVerbs.count()); 1328} 1329 1330void SkPath::unflatten(SkReader32& buffer) { 1331 fPts.setCount(buffer.readS32()); 1332 fVerbs.setCount(buffer.readS32()); 1333 fFillType = buffer.readS32(); 1334 buffer.read(fPts.begin(), sizeof(SkPoint) * fPts.count()); 1335 buffer.read(fVerbs.begin(), fVerbs.count()); 1336 1337 GEN_ID_INC; 1338 DIRTY_AFTER_EDIT; 1339 1340 SkDEBUGCODE(this->validate();) 1341} 1342 1343/////////////////////////////////////////////////////////////////////////////// 1344/////////////////////////////////////////////////////////////////////////////// 1345 1346void SkPath::dump(bool forceClose, const char title[]) const { 1347 Iter iter(*this, forceClose); 1348 SkPoint pts[4]; 1349 Verb verb; 1350 1351 SkDebugf("path: forceClose=%s %s\n", forceClose ? "true" : "false", 1352 title ? title : ""); 1353 1354 while ((verb = iter.next(pts)) != kDone_Verb) { 1355 switch (verb) { 1356 case kMove_Verb: 1357#ifdef SK_CAN_USE_FLOAT 1358 SkDebugf(" path: moveTo [%g %g]\n", 1359 SkScalarToFloat(pts[0].fX), SkScalarToFloat(pts[0].fY)); 1360#else 1361 SkDebugf(" path: moveTo [%x %x]\n", pts[0].fX, pts[0].fY); 1362#endif 1363 break; 1364 case kLine_Verb: 1365#ifdef SK_CAN_USE_FLOAT 1366 SkDebugf(" path: lineTo [%g %g]\n", 1367 SkScalarToFloat(pts[1].fX), SkScalarToFloat(pts[1].fY)); 1368#else 1369 SkDebugf(" path: lineTo [%x %x]\n", pts[1].fX, pts[1].fY); 1370#endif 1371 break; 1372 case kQuad_Verb: 1373#ifdef SK_CAN_USE_FLOAT 1374 SkDebugf(" path: quadTo [%g %g] [%g %g]\n", 1375 SkScalarToFloat(pts[1].fX), SkScalarToFloat(pts[1].fY), 1376 SkScalarToFloat(pts[2].fX), SkScalarToFloat(pts[2].fY)); 1377#else 1378 SkDebugf(" path: quadTo [%x %x] [%x %x]\n", 1379 pts[1].fX, pts[1].fY, pts[2].fX, pts[2].fY); 1380#endif 1381 break; 1382 case kCubic_Verb: 1383#ifdef SK_CAN_USE_FLOAT 1384 SkDebugf(" path: cubeTo [%g %g] [%g %g] [%g %g]\n", 1385 SkScalarToFloat(pts[1].fX), SkScalarToFloat(pts[1].fY), 1386 SkScalarToFloat(pts[2].fX), SkScalarToFloat(pts[2].fY), 1387 SkScalarToFloat(pts[3].fX), SkScalarToFloat(pts[3].fY)); 1388#else 1389 SkDebugf(" path: cubeTo [%x %x] [%x %x] [%x %x]\n", 1390 pts[1].fX, pts[1].fY, pts[2].fX, pts[2].fY, 1391 pts[3].fX, pts[3].fY); 1392#endif 1393 break; 1394 case kClose_Verb: 1395 SkDebugf(" path: close\n"); 1396 break; 1397 default: 1398 SkDebugf(" path: UNKNOWN VERB %d, aborting dump...\n", verb); 1399 verb = kDone_Verb; // stop the loop 1400 break; 1401 } 1402 } 1403 SkDebugf("path: done %s\n", title ? title : ""); 1404} 1405 1406void SkPath::dump() const { 1407 this->dump(false); 1408} 1409 1410#ifdef SK_DEBUG 1411void SkPath::validate() const { 1412 SkASSERT(this != NULL); 1413 SkASSERT((fFillType & ~3) == 0); 1414 fPts.validate(); 1415 fVerbs.validate(); 1416 1417 if (!fBoundsIsDirty) { 1418 SkRect bounds; 1419 compute_pt_bounds(&bounds, fPts); 1420 if (fPts.count() <= 1) { 1421 // if we're empty, fBounds may be empty but translated, so we can't 1422 // necessarily compare to bounds directly 1423 // try path.addOval(2, 2, 2, 2) which is empty, but the bounds will 1424 // be [2, 2, 2, 2] 1425 SkASSERT(bounds.isEmpty()); 1426 SkASSERT(fBounds.isEmpty()); 1427 } else { 1428 fBounds.contains(bounds); 1429 } 1430 } 1431 1432 uint32_t mask = 0; 1433 for (int i = 0; i < fVerbs.count(); i++) { 1434 switch (fVerbs[i]) { 1435 case kLine_Verb: 1436 mask |= kLine_SegmentMask; 1437 break; 1438 case kQuad_Verb: 1439 mask |= kQuad_SegmentMask; 1440 break; 1441 case kCubic_Verb: 1442 mask |= kCubic_SegmentMask; 1443 } 1444 } 1445 SkASSERT(mask == fSegmentMask); 1446} 1447#endif 1448 1449/////////////////////////////////////////////////////////////////////////////// 1450 1451static int sign(SkScalar x) { return x < 0; } 1452#define kValueNeverReturnedBySign 2 1453 1454static int CrossProductSign(const SkVector& a, const SkVector& b) { 1455 return SkScalarSignAsInt(SkPoint::CrossProduct(a, b)); 1456} 1457 1458// only valid for a single contour 1459struct Convexicator { 1460 Convexicator() : fPtCount(0), fConvexity(SkPath::kConvex_Convexity) { 1461 fSign = 0; 1462 // warnings 1463 fCurrPt.set(0, 0); 1464 fVec0.set(0, 0); 1465 fVec1.set(0, 0); 1466 fFirstVec.set(0, 0); 1467 1468 fDx = fDy = 0; 1469 fSx = fSy = kValueNeverReturnedBySign; 1470 } 1471 1472 SkPath::Convexity getConvexity() const { return fConvexity; } 1473 1474 void addPt(const SkPoint& pt) { 1475 if (SkPath::kConcave_Convexity == fConvexity) { 1476 return; 1477 } 1478 1479 if (0 == fPtCount) { 1480 fCurrPt = pt; 1481 ++fPtCount; 1482 } else { 1483 SkVector vec = pt - fCurrPt; 1484 if (vec.fX || vec.fY) { 1485 fCurrPt = pt; 1486 if (++fPtCount == 2) { 1487 fFirstVec = fVec1 = vec; 1488 } else { 1489 SkASSERT(fPtCount > 2); 1490 this->addVec(vec); 1491 } 1492 1493 int sx = sign(vec.fX); 1494 int sy = sign(vec.fY); 1495 fDx += (sx != fSx); 1496 fDy += (sy != fSy); 1497 fSx = sx; 1498 fSy = sy; 1499 1500 if (fDx > 3 || fDy > 3) { 1501 fConvexity = SkPath::kConcave_Convexity; 1502 } 1503 } 1504 } 1505 } 1506 1507 void close() { 1508 if (fPtCount > 2) { 1509 this->addVec(fFirstVec); 1510 } 1511 } 1512 1513private: 1514 void addVec(const SkVector& vec) { 1515 SkASSERT(vec.fX || vec.fY); 1516 fVec0 = fVec1; 1517 fVec1 = vec; 1518 int sign = CrossProductSign(fVec0, fVec1); 1519 if (0 == fSign) { 1520 fSign = sign; 1521 } else if (sign) { 1522 if (fSign != sign) { 1523 fConvexity = SkPath::kConcave_Convexity; 1524 } 1525 } 1526 } 1527 1528 SkPoint fCurrPt; 1529 SkVector fVec0, fVec1, fFirstVec; 1530 int fPtCount; // non-degenerate points 1531 int fSign; 1532 SkPath::Convexity fConvexity; 1533 int fDx, fDy, fSx, fSy; 1534}; 1535 1536SkPath::Convexity SkPath::ComputeConvexity(const SkPath& path) { 1537 SkPoint pts[4]; 1538 SkPath::Verb verb; 1539 SkPath::Iter iter(path, true); 1540 1541 int contourCount = 0; 1542 int count; 1543 Convexicator state; 1544 1545 while ((verb = iter.next(pts)) != SkPath::kDone_Verb) { 1546 switch (verb) { 1547 case kMove_Verb: 1548 if (++contourCount > 1) { 1549 return kConcave_Convexity; 1550 } 1551 pts[1] = pts[0]; 1552 count = 1; 1553 break; 1554 case kLine_Verb: count = 1; break; 1555 case kQuad_Verb: count = 2; break; 1556 case kCubic_Verb: count = 3; break; 1557 case kClose_Verb: 1558 state.close(); 1559 count = 0; 1560 break; 1561 default: 1562 SkASSERT(!"bad verb"); 1563 return kConcave_Convexity; 1564 } 1565 1566 for (int i = 1; i <= count; i++) { 1567 state.addPt(pts[i]); 1568 } 1569 // early exit 1570 if (kConcave_Convexity == state.getConvexity()) { 1571 return kConcave_Convexity; 1572 } 1573 } 1574 return state.getConvexity(); 1575} 1576