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