Simplify.cpp revision 0b7da433fe0eaa2833d1b2900715b013b36d93da
1/* 2 * Copyright 2012 Google Inc. 3 * 4 * Use of this source code is governed by a BSD-style license that can be 5 * found in the LICENSE file. 6 */ 7#include "Simplify.h" 8 9#undef SkASSERT 10#define SkASSERT(cond) while (!(cond)) { sk_throw(); } 11 12// Terminology: 13// A Path contains one of more Contours 14// A Contour is made up of Segment array 15// A Segment is described by a Verb and a Point array with 2, 3, or 4 points 16// A Verb is one of Line, Quad(ratic), or Cubic 17// A Segment contains a Span array 18// A Span is describes a portion of a Segment using starting and ending T 19// T values range from 0 to 1, where 0 is the first Point in the Segment 20// An Edge is a Segment generated from a Span 21 22// FIXME: remove once debugging is complete 23#ifdef SK_DEBUG 24int gDebugMaxWindSum = SK_MaxS32; 25int gDebugMaxWindValue = SK_MaxS32; 26#endif 27 28#define PRECISE_T_SORT 1 29#define SORTABLE_CONTOURS 0 // set to 1 for old code that works most of the time 30#define PIN_ADD_T 0 31#define TRY_ROTATE 1 32 33#define DEBUG_UNUSED 0 // set to expose unused functions 34#define FORCE_RELEASE 0 35 36#if FORCE_RELEASE || defined SK_RELEASE // set force release to 1 for multiple thread -- no debugging 37 38const bool gRunTestsInOneThread = false; 39 40#define DEBUG_ACTIVE_SPANS 0 41#define DEBUG_ADD_INTERSECTING_TS 0 42#define DEBUG_ADD_T_PAIR 0 43#define DEBUG_ANGLE 0 44#define DEBUG_CONCIDENT 0 45#define DEBUG_CROSS 0 46#define DEBUG_MARK_DONE 0 47#define DEBUG_PATH_CONSTRUCTION 0 48#define DEBUG_SORT 0 49#define DEBUG_WIND_BUMP 0 50#define DEBUG_WINDING 0 51 52#else 53 54const bool gRunTestsInOneThread = true; 55 56#define DEBUG_ACTIVE_SPANS 1 57#define DEBUG_ADD_INTERSECTING_TS 1 58#define DEBUG_ADD_T_PAIR 1 59#define DEBUG_ANGLE 1 60#define DEBUG_CONCIDENT 1 61#define DEBUG_CROSS 0 62#define DEBUG_MARK_DONE 1 63#define DEBUG_PATH_CONSTRUCTION 1 64#define DEBUG_SORT 1 65#define DEBUG_WIND_BUMP 0 66#define DEBUG_WINDING 1 67 68#endif 69 70#define DEBUG_DUMP (DEBUG_ACTIVE_SPANS | DEBUG_CONCIDENT | DEBUG_SORT | DEBUG_PATH_CONSTRUCTION) 71 72#if DEBUG_DUMP 73static const char* kLVerbStr[] = {"", "line", "quad", "cubic"}; 74// static const char* kUVerbStr[] = {"", "Line", "Quad", "Cubic"}; 75static int gContourID; 76static int gSegmentID; 77#endif 78 79#ifndef DEBUG_TEST 80#define DEBUG_TEST 0 81#endif 82 83#define MAKE_CONST_LINE(line, pts) \ 84 const _Line line = {{pts[0].fX, pts[0].fY}, {pts[1].fX, pts[1].fY}} 85#define MAKE_CONST_QUAD(quad, pts) \ 86 const Quadratic quad = {{pts[0].fX, pts[0].fY}, {pts[1].fX, pts[1].fY}, \ 87 {pts[2].fX, pts[2].fY}} 88#define MAKE_CONST_CUBIC(cubic, pts) \ 89 const Cubic cubic = {{pts[0].fX, pts[0].fY}, {pts[1].fX, pts[1].fY}, \ 90 {pts[2].fX, pts[2].fY}, {pts[3].fX, pts[3].fY}} 91 92static int LineIntersect(const SkPoint a[2], const SkPoint b[2], 93 Intersections& intersections) { 94 MAKE_CONST_LINE(aLine, a); 95 MAKE_CONST_LINE(bLine, b); 96 return intersect(aLine, bLine, intersections.fT[0], intersections.fT[1]); 97} 98 99static int QuadLineIntersect(const SkPoint a[3], const SkPoint b[2], 100 Intersections& intersections) { 101 MAKE_CONST_QUAD(aQuad, a); 102 MAKE_CONST_LINE(bLine, b); 103 return intersect(aQuad, bLine, intersections); 104} 105 106static int CubicLineIntersect(const SkPoint a[4], const SkPoint b[2], 107 Intersections& intersections) { 108 MAKE_CONST_CUBIC(aCubic, a); 109 MAKE_CONST_LINE(bLine, b); 110 return intersect(aCubic, bLine, intersections.fT[0], intersections.fT[1]); 111} 112 113static int QuadIntersect(const SkPoint a[3], const SkPoint b[3], 114 Intersections& intersections) { 115 MAKE_CONST_QUAD(aQuad, a); 116 MAKE_CONST_QUAD(bQuad, b); 117#define TRY_QUARTIC_SOLUTION 1 118#if TRY_QUARTIC_SOLUTION 119 intersect2(aQuad, bQuad, intersections); 120#else 121 intersect(aQuad, bQuad, intersections); 122#endif 123 return intersections.fUsed ? intersections.fUsed : intersections.fCoincidentUsed; 124} 125 126static int CubicIntersect(const SkPoint a[4], const SkPoint b[4], 127 Intersections& intersections) { 128 MAKE_CONST_CUBIC(aCubic, a); 129 MAKE_CONST_CUBIC(bCubic, b); 130 intersect(aCubic, bCubic, intersections); 131 return intersections.fUsed; 132} 133 134static int HLineIntersect(const SkPoint a[2], SkScalar left, SkScalar right, 135 SkScalar y, bool flipped, Intersections& intersections) { 136 MAKE_CONST_LINE(aLine, a); 137 return horizontalIntersect(aLine, left, right, y, flipped, intersections); 138} 139 140static int HQuadIntersect(const SkPoint a[3], SkScalar left, SkScalar right, 141 SkScalar y, bool flipped, Intersections& intersections) { 142 MAKE_CONST_QUAD(aQuad, a); 143 return horizontalIntersect(aQuad, left, right, y, flipped, intersections); 144} 145 146static int HCubicIntersect(const SkPoint a[4], SkScalar left, SkScalar right, 147 SkScalar y, bool flipped, Intersections& intersections) { 148 MAKE_CONST_CUBIC(aCubic, a); 149 return horizontalIntersect(aCubic, left, right, y, flipped, intersections); 150} 151 152static int VLineIntersect(const SkPoint a[2], SkScalar top, SkScalar bottom, 153 SkScalar x, bool flipped, Intersections& intersections) { 154 MAKE_CONST_LINE(aLine, a); 155 return verticalIntersect(aLine, top, bottom, x, flipped, intersections); 156} 157 158static int VQuadIntersect(const SkPoint a[3], SkScalar top, SkScalar bottom, 159 SkScalar x, bool flipped, Intersections& intersections) { 160 MAKE_CONST_QUAD(aQuad, a); 161 return verticalIntersect(aQuad, top, bottom, x, flipped, intersections); 162} 163 164static int VCubicIntersect(const SkPoint a[4], SkScalar top, SkScalar bottom, 165 SkScalar x, bool flipped, Intersections& intersections) { 166 MAKE_CONST_CUBIC(aCubic, a); 167 return verticalIntersect(aCubic, top, bottom, x, flipped, intersections); 168} 169 170static int (* const VSegmentIntersect[])(const SkPoint [], SkScalar , 171 SkScalar , SkScalar , bool , Intersections& ) = { 172 NULL, 173 VLineIntersect, 174 VQuadIntersect, 175 VCubicIntersect 176}; 177 178static void LineXYAtT(const SkPoint a[2], double t, SkPoint* out) { 179 MAKE_CONST_LINE(line, a); 180 double x, y; 181 xy_at_t(line, t, x, y); 182 out->fX = SkDoubleToScalar(x); 183 out->fY = SkDoubleToScalar(y); 184} 185 186static void QuadXYAtT(const SkPoint a[3], double t, SkPoint* out) { 187 MAKE_CONST_QUAD(quad, a); 188 double x, y; 189 xy_at_t(quad, t, x, y); 190 out->fX = SkDoubleToScalar(x); 191 out->fY = SkDoubleToScalar(y); 192} 193 194static void QuadXYAtT(const SkPoint a[3], double t, _Point* out) { 195 MAKE_CONST_QUAD(quad, a); 196 xy_at_t(quad, t, out->x, out->y); 197} 198 199static void CubicXYAtT(const SkPoint a[4], double t, SkPoint* out) { 200 MAKE_CONST_CUBIC(cubic, a); 201 double x, y; 202 xy_at_t(cubic, t, x, y); 203 out->fX = SkDoubleToScalar(x); 204 out->fY = SkDoubleToScalar(y); 205} 206 207static void (* const SegmentXYAtT[])(const SkPoint [], double , SkPoint* ) = { 208 NULL, 209 LineXYAtT, 210 QuadXYAtT, 211 CubicXYAtT 212}; 213 214static SkScalar LineXAtT(const SkPoint a[2], double t) { 215 MAKE_CONST_LINE(aLine, a); 216 double x; 217 xy_at_t(aLine, t, x, *(double*) 0); 218 return SkDoubleToScalar(x); 219} 220 221static SkScalar QuadXAtT(const SkPoint a[3], double t) { 222 MAKE_CONST_QUAD(quad, a); 223 double x; 224 xy_at_t(quad, t, x, *(double*) 0); 225 return SkDoubleToScalar(x); 226} 227 228static SkScalar CubicXAtT(const SkPoint a[4], double t) { 229 MAKE_CONST_CUBIC(cubic, a); 230 double x; 231 xy_at_t(cubic, t, x, *(double*) 0); 232 return SkDoubleToScalar(x); 233} 234 235static SkScalar (* const SegmentXAtT[])(const SkPoint [], double ) = { 236 NULL, 237 LineXAtT, 238 QuadXAtT, 239 CubicXAtT 240}; 241 242static SkScalar LineYAtT(const SkPoint a[2], double t) { 243 MAKE_CONST_LINE(aLine, a); 244 double y; 245 xy_at_t(aLine, t, *(double*) 0, y); 246 return SkDoubleToScalar(y); 247} 248 249static SkScalar QuadYAtT(const SkPoint a[3], double t) { 250 MAKE_CONST_QUAD(quad, a); 251 double y; 252 xy_at_t(quad, t, *(double*) 0, y); 253 return SkDoubleToScalar(y); 254} 255 256static SkScalar CubicYAtT(const SkPoint a[4], double t) { 257 MAKE_CONST_CUBIC(cubic, a); 258 double y; 259 xy_at_t(cubic, t, *(double*) 0, y); 260 return SkDoubleToScalar(y); 261} 262 263static SkScalar (* const SegmentYAtT[])(const SkPoint [], double ) = { 264 NULL, 265 LineYAtT, 266 QuadYAtT, 267 CubicYAtT 268}; 269 270static SkScalar LineDXAtT(const SkPoint a[2], double ) { 271 return a[1].fX - a[0].fX; 272} 273 274static SkScalar QuadDXAtT(const SkPoint a[3], double t) { 275 MAKE_CONST_QUAD(quad, a); 276 double x; 277 dxdy_at_t(quad, t, x, *(double*) 0); 278 return SkDoubleToScalar(x); 279} 280 281static SkScalar CubicDXAtT(const SkPoint a[4], double t) { 282 MAKE_CONST_CUBIC(cubic, a); 283 double x; 284 dxdy_at_t(cubic, t, x, *(double*) 0); 285 return SkDoubleToScalar(x); 286} 287 288static SkScalar (* const SegmentDXAtT[])(const SkPoint [], double ) = { 289 NULL, 290 LineDXAtT, 291 QuadDXAtT, 292 CubicDXAtT 293}; 294 295static void LineSubDivide(const SkPoint a[2], double startT, double endT, 296 SkPoint sub[2]) { 297 MAKE_CONST_LINE(aLine, a); 298 _Line dst; 299 sub_divide(aLine, startT, endT, dst); 300 sub[0].fX = SkDoubleToScalar(dst[0].x); 301 sub[0].fY = SkDoubleToScalar(dst[0].y); 302 sub[1].fX = SkDoubleToScalar(dst[1].x); 303 sub[1].fY = SkDoubleToScalar(dst[1].y); 304} 305 306static void QuadSubDivide(const SkPoint a[3], double startT, double endT, 307 SkPoint sub[3]) { 308 MAKE_CONST_QUAD(aQuad, a); 309 Quadratic dst; 310 sub_divide(aQuad, startT, endT, dst); 311 sub[0].fX = SkDoubleToScalar(dst[0].x); 312 sub[0].fY = SkDoubleToScalar(dst[0].y); 313 sub[1].fX = SkDoubleToScalar(dst[1].x); 314 sub[1].fY = SkDoubleToScalar(dst[1].y); 315 sub[2].fX = SkDoubleToScalar(dst[2].x); 316 sub[2].fY = SkDoubleToScalar(dst[2].y); 317} 318 319static void CubicSubDivide(const SkPoint a[4], double startT, double endT, 320 SkPoint sub[4]) { 321 MAKE_CONST_CUBIC(aCubic, a); 322 Cubic dst; 323 sub_divide(aCubic, startT, endT, dst); 324 sub[0].fX = SkDoubleToScalar(dst[0].x); 325 sub[0].fY = SkDoubleToScalar(dst[0].y); 326 sub[1].fX = SkDoubleToScalar(dst[1].x); 327 sub[1].fY = SkDoubleToScalar(dst[1].y); 328 sub[2].fX = SkDoubleToScalar(dst[2].x); 329 sub[2].fY = SkDoubleToScalar(dst[2].y); 330 sub[3].fX = SkDoubleToScalar(dst[3].x); 331 sub[3].fY = SkDoubleToScalar(dst[3].y); 332} 333 334static void (* const SegmentSubDivide[])(const SkPoint [], double , double , 335 SkPoint []) = { 336 NULL, 337 LineSubDivide, 338 QuadSubDivide, 339 CubicSubDivide 340}; 341 342static void LineSubDivideHD(const SkPoint a[2], double startT, double endT, 343 _Line sub) { 344 MAKE_CONST_LINE(aLine, a); 345 _Line dst; 346 sub_divide(aLine, startT, endT, dst); 347 sub[0] = dst[0]; 348 sub[1] = dst[1]; 349} 350 351static void QuadSubDivideHD(const SkPoint a[3], double startT, double endT, 352 Quadratic sub) { 353 MAKE_CONST_QUAD(aQuad, a); 354 Quadratic dst; 355 sub_divide(aQuad, startT, endT, dst); 356 sub[0] = dst[0]; 357 sub[1] = dst[1]; 358 sub[2] = dst[2]; 359} 360 361static void CubicSubDivideHD(const SkPoint a[4], double startT, double endT, 362 Cubic sub) { 363 MAKE_CONST_CUBIC(aCubic, a); 364 Cubic dst; 365 sub_divide(aCubic, startT, endT, dst); 366 sub[0] = dst[0]; 367 sub[1] = dst[1]; 368 sub[2] = dst[2]; 369 sub[3] = dst[3]; 370} 371 372#if DEBUG_UNUSED 373static void QuadSubBounds(const SkPoint a[3], double startT, double endT, 374 SkRect& bounds) { 375 SkPoint dst[3]; 376 QuadSubDivide(a, startT, endT, dst); 377 bounds.fLeft = bounds.fRight = dst[0].fX; 378 bounds.fTop = bounds.fBottom = dst[0].fY; 379 for (int index = 1; index < 3; ++index) { 380 bounds.growToInclude(dst[index].fX, dst[index].fY); 381 } 382} 383 384static void CubicSubBounds(const SkPoint a[4], double startT, double endT, 385 SkRect& bounds) { 386 SkPoint dst[4]; 387 CubicSubDivide(a, startT, endT, dst); 388 bounds.fLeft = bounds.fRight = dst[0].fX; 389 bounds.fTop = bounds.fBottom = dst[0].fY; 390 for (int index = 1; index < 4; ++index) { 391 bounds.growToInclude(dst[index].fX, dst[index].fY); 392 } 393} 394#endif 395 396static SkPath::Verb QuadReduceOrder(const SkPoint a[3], 397 SkTDArray<SkPoint>& reducePts) { 398 MAKE_CONST_QUAD(aQuad, a); 399 Quadratic dst; 400 int order = reduceOrder(aQuad, dst); 401 if (order == 2) { // quad became line 402 for (int index = 0; index < order; ++index) { 403 SkPoint* pt = reducePts.append(); 404 pt->fX = SkDoubleToScalar(dst[index].x); 405 pt->fY = SkDoubleToScalar(dst[index].y); 406 } 407 } 408 return (SkPath::Verb) (order - 1); 409} 410 411static SkPath::Verb CubicReduceOrder(const SkPoint a[4], 412 SkTDArray<SkPoint>& reducePts) { 413 MAKE_CONST_CUBIC(aCubic, a); 414 Cubic dst; 415 int order = reduceOrder(aCubic, dst, kReduceOrder_QuadraticsAllowed); 416 if (order == 2 || order == 3) { // cubic became line or quad 417 for (int index = 0; index < order; ++index) { 418 SkPoint* pt = reducePts.append(); 419 pt->fX = SkDoubleToScalar(dst[index].x); 420 pt->fY = SkDoubleToScalar(dst[index].y); 421 } 422 } 423 return (SkPath::Verb) (order - 1); 424} 425 426static bool QuadIsLinear(const SkPoint a[3]) { 427 MAKE_CONST_QUAD(aQuad, a); 428 return isLinear(aQuad, 0, 2); 429} 430 431static bool CubicIsLinear(const SkPoint a[4]) { 432 MAKE_CONST_CUBIC(aCubic, a); 433 return isLinear(aCubic, 0, 3); 434} 435 436static SkScalar LineLeftMost(const SkPoint a[2], double startT, double endT) { 437 MAKE_CONST_LINE(aLine, a); 438 double x[2]; 439 xy_at_t(aLine, startT, x[0], *(double*) 0); 440 xy_at_t(aLine, endT, x[1], *(double*) 0); 441 return SkMinScalar((float) x[0], (float) x[1]); 442} 443 444static SkScalar QuadLeftMost(const SkPoint a[3], double startT, double endT) { 445 MAKE_CONST_QUAD(aQuad, a); 446 return (float) leftMostT(aQuad, startT, endT); 447} 448 449static SkScalar CubicLeftMost(const SkPoint a[4], double startT, double endT) { 450 MAKE_CONST_CUBIC(aCubic, a); 451 return (float) leftMostT(aCubic, startT, endT); 452} 453 454static SkScalar (* const SegmentLeftMost[])(const SkPoint [], double , double) = { 455 NULL, 456 LineLeftMost, 457 QuadLeftMost, 458 CubicLeftMost 459}; 460 461#if 0 // currently unused 462static int QuadRayIntersect(const SkPoint a[3], const SkPoint b[2], 463 Intersections& intersections) { 464 MAKE_CONST_QUAD(aQuad, a); 465 MAKE_CONST_LINE(bLine, b); 466 return intersectRay(aQuad, bLine, intersections); 467} 468#endif 469 470static int QuadRayIntersect(const SkPoint a[3], const _Line& bLine, 471 Intersections& intersections) { 472 MAKE_CONST_QUAD(aQuad, a); 473 return intersectRay(aQuad, bLine, intersections); 474} 475 476class Segment; 477 478struct Span { 479 Segment* fOther; 480 mutable SkPoint fPt; // lazily computed as needed 481 double fT; 482 double fOtherT; // value at fOther[fOtherIndex].fT 483 int fOtherIndex; // can't be used during intersection 484 int fWindSum; // accumulated from contours surrounding this one 485 int fWindValue; // 0 == canceled; 1 == normal; >1 == coincident 486 int fWindValueOpp; // opposite value, if any (for binary ops with coincidence) 487 bool fDone; // if set, this span to next higher T has been processed 488 bool fUnsortableStart; // set when start is part of an unsortable pair 489 bool fUnsortableEnd; // set when end is part of an unsortable pair 490 bool fTiny; // if set, span may still be considered once for edge following 491}; 492 493// sorting angles 494// given angles of {dx dy ddx ddy dddx dddy} sort them 495class Angle { 496public: 497 // FIXME: this is bogus for quads and cubics 498 // if the quads and cubics' line from end pt to ctrl pt are coincident, 499 // there's no obvious way to determine the curve ordering from the 500 // derivatives alone. In particular, if one quadratic's coincident tangent 501 // is longer than the other curve, the final control point can place the 502 // longer curve on either side of the shorter one. 503 // Using Bezier curve focus http://cagd.cs.byu.edu/~tom/papers/bezclip.pdf 504 // may provide some help, but nothing has been figured out yet. 505 506 /*( 507 for quads and cubics, set up a parameterized line (e.g. LineParameters ) 508 for points [0] to [1]. See if point [2] is on that line, or on one side 509 or the other. If it both quads' end points are on the same side, choose 510 the shorter tangent. If the tangents are equal, choose the better second 511 tangent angle 512 513 maybe I could set up LineParameters lazily 514 */ 515 bool operator<(const Angle& rh) const { 516 double y = dy(); 517 double ry = rh.dy(); 518 if ((y < 0) ^ (ry < 0)) { // OPTIMIZATION: better to use y * ry < 0 ? 519 return y < 0; 520 } 521 double x = dx(); 522 double rx = rh.dx(); 523 if (y == 0 && ry == 0 && x * rx < 0) { 524 return x < rx; 525 } 526 double x_ry = x * ry; 527 double rx_y = rx * y; 528 double cmp = x_ry - rx_y; 529 if (!approximately_zero(cmp)) { 530 return cmp < 0; 531 } 532 if (approximately_zero(x_ry) && approximately_zero(rx_y) 533 && !approximately_zero_squared(cmp)) { 534 return cmp < 0; 535 } 536 // at this point, the initial tangent line is coincident 537 if (fSide * rh.fSide <= 0 && (!approximately_zero(fSide) || !approximately_zero(rh.fSide))) { 538 // FIXME: running demo will trigger this assertion 539 // (don't know if commenting out will trigger further assertion or not) 540 // commenting it out allows demo to run in release, though 541 // SkASSERT(fSide != rh.fSide); 542 return fSide < rh.fSide; 543 } 544 // see if either curve can be lengthened and try the tangent compare again 545 if (cmp && (*fSpans)[fEnd].fOther != rh.fSegment // tangents not absolutely identical 546 && (*rh.fSpans)[rh.fEnd].fOther != fSegment) { // and not intersecting 547 Angle longer = *this; 548 Angle rhLonger = rh; 549 if (longer.lengthen() | rhLonger.lengthen()) { 550 return longer < rhLonger; 551 } 552 // what if we extend in the other direction? 553 longer = *this; 554 rhLonger = rh; 555 if (longer.reverseLengthen() | rhLonger.reverseLengthen()) { 556 return longer < rhLonger; 557 } 558 } 559 if ((fVerb == SkPath::kLine_Verb && approximately_zero(x) && approximately_zero(y)) 560 || (rh.fVerb == SkPath::kLine_Verb && approximately_zero(rx) && approximately_zero(ry))) { 561 // See general unsortable comment below. This case can happen when 562 // one line has a non-zero change in t but no change in x and y. 563 fUnsortable = true; 564 rh.fUnsortable = true; 565 return this < &rh; // even with no solution, return a stable sort 566 } 567 SkASSERT(fVerb == SkPath::kQuad_Verb); // worry about cubics later 568 SkASSERT(rh.fVerb == SkPath::kQuad_Verb); 569 // FIXME: until I can think of something better, project a ray from the 570 // end of the shorter tangent to midway between the end points 571 // through both curves and use the resulting angle to sort 572 // FIXME: some of this setup can be moved to set() if it works, or cached if it's expensive 573 double len = fTangent1.normalSquared(); 574 double rlen = rh.fTangent1.normalSquared(); 575 _Line ray; 576 Intersections i, ri; 577 int roots, rroots; 578 bool flip = false; 579 do { 580 const Quadratic& q = (len < rlen) ^ flip ? fQ : rh.fQ; 581 double midX = (q[0].x + q[2].x) / 2; 582 double midY = (q[0].y + q[2].y) / 2; 583 ray[0] = q[1]; 584 ray[1].x = midX; 585 ray[1].y = midY; 586 SkASSERT(ray[0] != ray[1]); 587 roots = QuadRayIntersect(fPts, ray, i); 588 rroots = QuadRayIntersect(rh.fPts, ray, ri); 589 } while ((roots == 0 || rroots == 0) && (flip ^= true)); 590 if (roots == 0 || rroots == 0) { 591 // FIXME: we don't have a solution in this case. The interim solution 592 // is to mark the edges as unsortable, exclude them from this and 593 // future computations, and allow the returned path to be fragmented 594 fUnsortable = true; 595 rh.fUnsortable = true; 596 return this < &rh; // even with no solution, return a stable sort 597 } 598 _Point loc; 599 double best = SK_ScalarInfinity; 600 double dx, dy, dist; 601 int index; 602 for (index = 0; index < roots; ++index) { 603 QuadXYAtT(fPts, i.fT[0][index], &loc); 604 dx = loc.x - ray[0].x; 605 dy = loc.y - ray[0].y; 606 dist = dx * dx + dy * dy; 607 if (best > dist) { 608 best = dist; 609 } 610 } 611 for (index = 0; index < rroots; ++index) { 612 QuadXYAtT(rh.fPts, ri.fT[0][index], &loc); 613 dx = loc.x - ray[0].x; 614 dy = loc.y - ray[0].y; 615 dist = dx * dx + dy * dy; 616 if (best > dist) { 617 return fSide < 0; 618 } 619 } 620 return fSide > 0; 621 } 622 623 double dx() const { 624 return fTangent1.dx(); 625 } 626 627 double dy() const { 628 return fTangent1.dy(); 629 } 630 631 int end() const { 632 return fEnd; 633 } 634 635 bool isHorizontal() const { 636 return dy() == 0 && fVerb == SkPath::kLine_Verb; 637 } 638 639 bool lengthen() { 640 int newEnd = fEnd; 641 if (fStart < fEnd ? ++newEnd < fSpans->count() : --newEnd >= 0) { 642 fEnd = newEnd; 643 setSpans(); 644 return true; 645 } 646 return false; 647 } 648 649 bool reverseLengthen() { 650 if (fReversed) { 651 return false; 652 } 653 int newEnd = fStart; 654 if (fStart > fEnd ? ++newEnd < fSpans->count() : --newEnd >= 0) { 655 fEnd = newEnd; 656 fReversed = true; 657 setSpans(); 658 return true; 659 } 660 return false; 661 } 662 663 void set(const SkPoint* orig, SkPath::Verb verb, const Segment* segment, 664 int start, int end, const SkTDArray<Span>& spans) { 665 fSegment = segment; 666 fStart = start; 667 fEnd = end; 668 fPts = orig; 669 fVerb = verb; 670 fSpans = &spans; 671 fReversed = false; 672 fUnsortable = false; 673 setSpans(); 674 } 675 676 void setSpans() { 677 double startT = (*fSpans)[fStart].fT; 678 double endT = (*fSpans)[fEnd].fT; 679 switch (fVerb) { 680 case SkPath::kLine_Verb: 681 _Line l; 682 LineSubDivideHD(fPts, startT, endT, l); 683 // OPTIMIZATION: for pure line compares, we never need fTangent1.c 684 fTangent1.lineEndPoints(l); 685 fUnsortable = dx() == 0 && dy() == 0; 686 fSide = 0; 687 break; 688 case SkPath::kQuad_Verb: 689 QuadSubDivideHD(fPts, startT, endT, fQ); 690 fTangent1.quadEndPoints(fQ, 0, 1); 691 fSide = -fTangent1.pointDistance(fQ[2]); // not normalized -- compare sign only 692 break; 693 case SkPath::kCubic_Verb: 694 Cubic c; 695 CubicSubDivideHD(fPts, startT, endT, c); 696 fTangent1.cubicEndPoints(c, 0, 1); 697 fSide = -fTangent1.pointDistance(c[2]); // not normalized -- compare sign only 698 break; 699 default: 700 SkASSERT(0); 701 } 702 if (fUnsortable) { 703 return; 704 } 705 SkASSERT(fStart != fEnd); 706 int step = fStart < fEnd ? 1 : -1; // OPTIMIZE: worth fStart - fEnd >> 31 type macro? 707 for (int index = fStart; index != fEnd; index += step) { 708 if ((*fSpans)[index].fUnsortableStart) { 709 fUnsortable = true; 710 return; 711 } 712 if (index != fStart && (*fSpans)[index].fUnsortableEnd) { 713 fUnsortable = true; 714 return; 715 } 716 } 717 } 718 719 Segment* segment() const { 720 return const_cast<Segment*>(fSegment); 721 } 722 723 int sign() const { 724 return SkSign32(fStart - fEnd); 725 } 726 727 const SkTDArray<Span>* spans() const { 728 return fSpans; 729 } 730 731 int start() const { 732 return fStart; 733 } 734 735 bool unsortable() const { 736 return fUnsortable; 737 } 738 739#if DEBUG_ANGLE 740 const SkPoint* pts() const { 741 return fPts; 742 } 743 744 SkPath::Verb verb() const { 745 return fVerb; 746 } 747 748 void debugShow(const SkPoint& a) const { 749 SkDebugf(" d=(%1.9g,%1.9g) side=%1.9g\n", dx(), dy(), fSide); 750 } 751#endif 752 753private: 754 const SkPoint* fPts; 755 Quadratic fQ; 756 SkPath::Verb fVerb; 757 double fSide; 758 LineParameters fTangent1; 759 const SkTDArray<Span>* fSpans; 760 const Segment* fSegment; 761 int fStart; 762 int fEnd; 763 bool fReversed; 764 mutable bool fUnsortable; // this alone is editable by the less than operator 765}; 766 767// Bounds, unlike Rect, does not consider a line to be empty. 768struct Bounds : public SkRect { 769 static bool Intersects(const Bounds& a, const Bounds& b) { 770 return a.fLeft <= b.fRight && b.fLeft <= a.fRight && 771 a.fTop <= b.fBottom && b.fTop <= a.fBottom; 772 } 773 774 void add(SkScalar left, SkScalar top, SkScalar right, SkScalar bottom) { 775 if (left < fLeft) { 776 fLeft = left; 777 } 778 if (top < fTop) { 779 fTop = top; 780 } 781 if (right > fRight) { 782 fRight = right; 783 } 784 if (bottom > fBottom) { 785 fBottom = bottom; 786 } 787 } 788 789 void add(const Bounds& toAdd) { 790 add(toAdd.fLeft, toAdd.fTop, toAdd.fRight, toAdd.fBottom); 791 } 792 793 bool isEmpty() { 794 return fLeft > fRight || fTop > fBottom 795 || (fLeft == fRight && fTop == fBottom) 796 || isnan(fLeft) || isnan(fRight) 797 || isnan(fTop) || isnan(fBottom); 798 } 799 800 void setCubicBounds(const SkPoint a[4]) { 801 _Rect dRect; 802 MAKE_CONST_CUBIC(cubic, a); 803 dRect.setBounds(cubic); 804 set((float) dRect.left, (float) dRect.top, (float) dRect.right, 805 (float) dRect.bottom); 806 } 807 808 void setQuadBounds(const SkPoint a[3]) { 809 MAKE_CONST_QUAD(quad, a); 810 _Rect dRect; 811 dRect.setBounds(quad); 812 set((float) dRect.left, (float) dRect.top, (float) dRect.right, 813 (float) dRect.bottom); 814 } 815}; 816 817static bool useInnerWinding(int outerWinding, int innerWinding) { 818 SkASSERT(outerWinding != innerWinding); 819 int absOut = abs(outerWinding); 820 int absIn = abs(innerWinding); 821 bool result = absOut == absIn ? outerWinding < 0 : absOut < absIn; 822 if (outerWinding * innerWinding < 0) { 823#if DEBUG_WINDING 824 SkDebugf("%s outer=%d inner=%d result=%s\n", __FUNCTION__, 825 outerWinding, innerWinding, result ? "true" : "false"); 826#endif 827 } 828 return result; 829} 830 831static const bool opLookup[][2][2] = { 832 // ==0 !=0 833 // b a b a 834 {{true , false}, {false, true }}, // a - b 835 {{false, false}, {true , true }}, // a & b 836 {{true , true }, {false, false}}, // a | b 837 {{true , true }, {true , true }}, // a ^ b 838}; 839 840static bool activeOp(bool angleIsOp, int otherNonZero, ShapeOp op) { 841 return opLookup[op][otherNonZero][angleIsOp]; 842} 843 844 845// wrap path to keep track of whether the contour is initialized and non-empty 846class PathWrapper { 847public: 848 PathWrapper(SkPath& path) 849 : fPathPtr(&path) 850 { 851 init(); 852 } 853 854 void close() { 855 if (!fHasMove) { 856 return; 857 } 858 bool callClose = isClosed(); 859 lineTo(); 860 if (fEmpty) { 861 return; 862 } 863 if (callClose) { 864 #if DEBUG_PATH_CONSTRUCTION 865 SkDebugf("path.close();\n"); 866 #endif 867 fPathPtr->close(); 868 } 869 init(); 870 } 871 872 void cubicTo(const SkPoint& pt1, const SkPoint& pt2, const SkPoint& pt3) { 873 lineTo(); 874 moveTo(); 875#if DEBUG_PATH_CONSTRUCTION 876 SkDebugf("path.cubicTo(%1.9g,%1.9g, %1.9g,%1.9g, %1.9g,%1.9g);\n", 877 pt1.fX, pt1.fY, pt2.fX, pt2.fY, pt3.fX, pt3.fY); 878#endif 879 fPathPtr->cubicTo(pt1.fX, pt1.fY, pt2.fX, pt2.fY, pt3.fX, pt3.fY); 880 fDefer[0] = fDefer[1] = pt3; 881 fEmpty = false; 882 } 883 884 void deferredLine(const SkPoint& pt) { 885 if (pt == fDefer[1]) { 886 return; 887 } 888 if (changedSlopes(pt)) { 889 lineTo(); 890 fDefer[0] = fDefer[1]; 891 } 892 fDefer[1] = pt; 893 } 894 895 void deferredMove(const SkPoint& pt) { 896 fMoved = true; 897 fHasMove = true; 898 fEmpty = true; 899 fDefer[0] = fDefer[1] = pt; 900 } 901 902 void deferredMoveLine(const SkPoint& pt) { 903 if (!fHasMove) { 904 deferredMove(pt); 905 } 906 deferredLine(pt); 907 } 908 909 bool hasMove() const { 910 return fHasMove; 911 } 912 913 void init() { 914 fEmpty = true; 915 fHasMove = false; 916 fMoved = false; 917 } 918 919 bool isClosed() const { 920 return !fEmpty && fFirstPt == fDefer[1]; 921 } 922 923 void lineTo() { 924 if (fDefer[0] == fDefer[1]) { 925 return; 926 } 927 moveTo(); 928 fEmpty = false; 929#if DEBUG_PATH_CONSTRUCTION 930 SkDebugf("path.lineTo(%1.9g,%1.9g);\n", fDefer[1].fX, fDefer[1].fY); 931#endif 932 fPathPtr->lineTo(fDefer[1].fX, fDefer[1].fY); 933 fDefer[0] = fDefer[1]; 934 } 935 936 const SkPath* nativePath() const { 937 return fPathPtr; 938 } 939 940 void quadTo(const SkPoint& pt1, const SkPoint& pt2) { 941 lineTo(); 942 moveTo(); 943#if DEBUG_PATH_CONSTRUCTION 944 SkDebugf("path.quadTo(%1.9g,%1.9g, %1.9g,%1.9g);\n", 945 pt1.fX, pt1.fY, pt2.fX, pt2.fY); 946#endif 947 fPathPtr->quadTo(pt1.fX, pt1.fY, pt2.fX, pt2.fY); 948 fDefer[0] = fDefer[1] = pt2; 949 fEmpty = false; 950 } 951 952protected: 953 bool changedSlopes(const SkPoint& pt) const { 954 if (fDefer[0] == fDefer[1]) { 955 return false; 956 } 957 SkScalar deferDx = fDefer[1].fX - fDefer[0].fX; 958 SkScalar deferDy = fDefer[1].fY - fDefer[0].fY; 959 SkScalar lineDx = pt.fX - fDefer[1].fX; 960 SkScalar lineDy = pt.fY - fDefer[1].fY; 961 return deferDx * lineDy != deferDy * lineDx; 962 } 963 964 void moveTo() { 965 if (!fMoved) { 966 return; 967 } 968 fFirstPt = fDefer[0]; 969#if DEBUG_PATH_CONSTRUCTION 970 SkDebugf("path.moveTo(%1.9g,%1.9g);\n", fDefer[0].fX, fDefer[0].fY); 971#endif 972 fPathPtr->moveTo(fDefer[0].fX, fDefer[0].fY); 973 fMoved = false; 974 } 975 976private: 977 SkPath* fPathPtr; 978 SkPoint fDefer[2]; 979 SkPoint fFirstPt; 980 bool fEmpty; 981 bool fHasMove; 982 bool fMoved; 983}; 984 985class Segment { 986public: 987 Segment() { 988#if DEBUG_DUMP 989 fID = ++gSegmentID; 990#endif 991 } 992 993 bool operator<(const Segment& rh) const { 994 return fBounds.fTop < rh.fBounds.fTop; 995 } 996 997 bool activeAngle(int index, int& done, SkTDArray<Angle>& angles) const { 998 if (activeAngleInner(index, done, angles)) { 999 return true; 1000 } 1001 double referenceT = fTs[index].fT; 1002 int lesser = index; 1003 while (--lesser >= 0 && approximately_negative(referenceT - fTs[lesser].fT)) { 1004 if (activeAngleOther(lesser, done, angles)) { 1005 return true; 1006 } 1007 } 1008 do { 1009 if (activeAngleOther(index, done, angles)) { 1010 return true; 1011 } 1012 } while (++index < fTs.count() && approximately_negative(fTs[index].fT - referenceT)); 1013 return false; 1014 } 1015 1016 bool activeAngleOther(int index, int& done, SkTDArray<Angle>& angles) const { 1017 Span* span = &fTs[index]; 1018 Segment* other = span->fOther; 1019 int oIndex = span->fOtherIndex; 1020 return other->activeAngleInner(oIndex, done, angles); 1021 } 1022 1023 bool activeAngleInner(int index, int& done, SkTDArray<Angle>& angles) const { 1024 int next = nextExactSpan(index, 1); 1025 if (next > 0) { 1026 const Span& upSpan = fTs[index]; 1027 if (upSpan.fWindValue) { 1028 addAngle(angles, index, next); 1029 if (upSpan.fDone || upSpan.fUnsortableEnd) { 1030 done++; 1031 } else if (upSpan.fWindSum != SK_MinS32) { 1032 return true; 1033 } 1034 } 1035 } 1036 int prev = nextExactSpan(index, -1); 1037 // edge leading into junction 1038 if (prev >= 0) { 1039 const Span& downSpan = fTs[prev]; 1040 if (downSpan.fWindValue) { 1041 addAngle(angles, index, prev); 1042 if (downSpan.fDone) { 1043 done++; 1044 } else if (downSpan.fWindSum != SK_MinS32) { 1045 return true; 1046 } 1047 } 1048 } 1049 return false; 1050 } 1051 1052 void activeLeftTop(SkPoint& result) const { 1053 SkASSERT(!done()); 1054 int count = fTs.count(); 1055 result.fY = SK_ScalarMax; 1056 bool lastDone = true; 1057 bool lastUnsortable = false; 1058 for (int index = 0; index < count; ++index) { 1059 const Span& span = fTs[index]; 1060 if (span.fUnsortableStart | lastUnsortable) { 1061 goto next; 1062 } 1063 if (!span.fDone | !lastDone) { 1064 const SkPoint& xy = xyAtT(index); 1065 if (result.fY < xy.fY) { 1066 goto next; 1067 } 1068 if (result.fY == xy.fY && result.fX < xy.fX) { 1069 goto next; 1070 } 1071 result = xy; 1072 } 1073 next: 1074 lastDone = span.fDone; 1075 lastUnsortable = span.fUnsortableEnd; 1076 } 1077 SkASSERT(result.fY < SK_ScalarMax); 1078 } 1079 1080 void addAngle(SkTDArray<Angle>& angles, int start, int end) const { 1081 SkASSERT(start != end); 1082 Angle* angle = angles.append(); 1083#if DEBUG_ANGLE 1084 if (angles.count() > 1) { 1085 SkPoint angle0Pt, newPt; 1086 (*SegmentXYAtT[angles[0].verb()])(angles[0].pts(), 1087 (*angles[0].spans())[angles[0].start()].fT, &angle0Pt); 1088 (*SegmentXYAtT[fVerb])(fPts, fTs[start].fT, &newPt); 1089 SkASSERT(approximately_equal(angle0Pt.fX, newPt.fX)); 1090 SkASSERT(approximately_equal(angle0Pt.fY, newPt.fY)); 1091 } 1092#endif 1093 angle->set(fPts, fVerb, this, start, end, fTs); 1094 } 1095 1096 void addCancelOutsides(double tStart, double oStart, Segment& other, 1097 double oEnd) { 1098 int tIndex = -1; 1099 int tCount = fTs.count(); 1100 int oIndex = -1; 1101 int oCount = other.fTs.count(); 1102 do { 1103 ++tIndex; 1104 } while (!approximately_negative(tStart - fTs[tIndex].fT) && tIndex < tCount); 1105 int tIndexStart = tIndex; 1106 do { 1107 ++oIndex; 1108 } while (!approximately_negative(oStart - other.fTs[oIndex].fT) && oIndex < oCount); 1109 int oIndexStart = oIndex; 1110 double nextT; 1111 do { 1112 nextT = fTs[++tIndex].fT; 1113 } while (nextT < 1 && approximately_negative(nextT - tStart)); 1114 double oNextT; 1115 do { 1116 oNextT = other.fTs[++oIndex].fT; 1117 } while (oNextT < 1 && approximately_negative(oNextT - oStart)); 1118 // at this point, spans before and after are at: 1119 // fTs[tIndexStart - 1], fTs[tIndexStart], fTs[tIndex] 1120 // if tIndexStart == 0, no prior span 1121 // if nextT == 1, no following span 1122 1123 // advance the span with zero winding 1124 // if the following span exists (not past the end, non-zero winding) 1125 // connect the two edges 1126 if (!fTs[tIndexStart].fWindValue) { 1127 if (tIndexStart > 0 && fTs[tIndexStart - 1].fWindValue) { 1128 #if DEBUG_CONCIDENT 1129 SkDebugf("%s 1 this=%d other=%d t [%d] %1.9g (%1.9g,%1.9g)\n", 1130 __FUNCTION__, fID, other.fID, tIndexStart - 1, 1131 fTs[tIndexStart].fT, xyAtT(tIndexStart).fX, 1132 xyAtT(tIndexStart).fY); 1133 #endif 1134 addTPair(fTs[tIndexStart].fT, other, other.fTs[oIndex].fT, false); 1135 } 1136 if (nextT < 1 && fTs[tIndex].fWindValue) { 1137 #if DEBUG_CONCIDENT 1138 SkDebugf("%s 2 this=%d other=%d t [%d] %1.9g (%1.9g,%1.9g)\n", 1139 __FUNCTION__, fID, other.fID, tIndex, 1140 fTs[tIndex].fT, xyAtT(tIndex).fX, 1141 xyAtT(tIndex).fY); 1142 #endif 1143 addTPair(fTs[tIndex].fT, other, other.fTs[oIndexStart].fT, false); 1144 } 1145 } else { 1146 SkASSERT(!other.fTs[oIndexStart].fWindValue); 1147 if (oIndexStart > 0 && other.fTs[oIndexStart - 1].fWindValue) { 1148 #if DEBUG_CONCIDENT 1149 SkDebugf("%s 3 this=%d other=%d t [%d] %1.9g (%1.9g,%1.9g)\n", 1150 __FUNCTION__, fID, other.fID, oIndexStart - 1, 1151 other.fTs[oIndexStart].fT, other.xyAtT(oIndexStart).fX, 1152 other.xyAtT(oIndexStart).fY); 1153 other.debugAddTPair(other.fTs[oIndexStart].fT, *this, fTs[tIndex].fT); 1154 #endif 1155 } 1156 if (oNextT < 1 && other.fTs[oIndex].fWindValue) { 1157 #if DEBUG_CONCIDENT 1158 SkDebugf("%s 4 this=%d other=%d t [%d] %1.9g (%1.9g,%1.9g)\n", 1159 __FUNCTION__, fID, other.fID, oIndex, 1160 other.fTs[oIndex].fT, other.xyAtT(oIndex).fX, 1161 other.xyAtT(oIndex).fY); 1162 other.debugAddTPair(other.fTs[oIndex].fT, *this, fTs[tIndexStart].fT); 1163 #endif 1164 } 1165 } 1166 } 1167 1168 void addCoinOutsides(const SkTDArray<double>& outsideTs, Segment& other, 1169 double oEnd) { 1170 // walk this to outsideTs[0] 1171 // walk other to outsideTs[1] 1172 // if either is > 0, add a pointer to the other, copying adjacent winding 1173 int tIndex = -1; 1174 int oIndex = -1; 1175 double tStart = outsideTs[0]; 1176 double oStart = outsideTs[1]; 1177 do { 1178 ++tIndex; 1179 } while (!approximately_negative(tStart - fTs[tIndex].fT)); 1180 do { 1181 ++oIndex; 1182 } while (!approximately_negative(oStart - other.fTs[oIndex].fT)); 1183 if (tIndex > 0 || oIndex > 0) { 1184 addTPair(tStart, other, oStart, false); 1185 } 1186 tStart = fTs[tIndex].fT; 1187 oStart = other.fTs[oIndex].fT; 1188 do { 1189 double nextT; 1190 do { 1191 nextT = fTs[++tIndex].fT; 1192 } while (approximately_negative(nextT - tStart)); 1193 tStart = nextT; 1194 do { 1195 nextT = other.fTs[++oIndex].fT; 1196 } while (approximately_negative(nextT - oStart)); 1197 oStart = nextT; 1198 if (tStart == 1 && oStart == 1) { 1199 break; 1200 } 1201 addTPair(tStart, other, oStart, false); 1202 } while (tStart < 1 && oStart < 1 && !approximately_negative(oEnd - oStart)); 1203 } 1204 1205 void addCubic(const SkPoint pts[4], bool operand) { 1206 init(pts, SkPath::kCubic_Verb, operand); 1207 fBounds.setCubicBounds(pts); 1208 } 1209 1210 /* SkPoint */ void addCurveTo(int start, int end, PathWrapper& path, bool active) const { 1211 SkPoint edge[4]; 1212 const SkPoint* ePtr; 1213 int lastT = fTs.count() - 1; 1214 if (lastT < 0 || (start == 0 && end == lastT) || (start == lastT && end == 0)) { 1215 ePtr = fPts; 1216 } else { 1217 // OPTIMIZE? if not active, skip remainder and return xy_at_t(end) 1218 (*SegmentSubDivide[fVerb])(fPts, fTs[start].fT, fTs[end].fT, edge); 1219 ePtr = edge; 1220 } 1221 if (active) { 1222 bool reverse = ePtr == fPts && start != 0; 1223 if (reverse) { 1224 path.deferredMoveLine(ePtr[fVerb]); 1225 switch (fVerb) { 1226 case SkPath::kLine_Verb: 1227 path.deferredLine(ePtr[0]); 1228 break; 1229 case SkPath::kQuad_Verb: 1230 path.quadTo(ePtr[1], ePtr[0]); 1231 break; 1232 case SkPath::kCubic_Verb: 1233 path.cubicTo(ePtr[2], ePtr[1], ePtr[0]); 1234 break; 1235 default: 1236 SkASSERT(0); 1237 } 1238 // return ePtr[0]; 1239 } else { 1240 path.deferredMoveLine(ePtr[0]); 1241 switch (fVerb) { 1242 case SkPath::kLine_Verb: 1243 path.deferredLine(ePtr[1]); 1244 break; 1245 case SkPath::kQuad_Verb: 1246 path.quadTo(ePtr[1], ePtr[2]); 1247 break; 1248 case SkPath::kCubic_Verb: 1249 path.cubicTo(ePtr[1], ePtr[2], ePtr[3]); 1250 break; 1251 default: 1252 SkASSERT(0); 1253 } 1254 } 1255 } 1256 // return ePtr[fVerb]; 1257 } 1258 1259 void addLine(const SkPoint pts[2], bool operand) { 1260 init(pts, SkPath::kLine_Verb, operand); 1261 fBounds.set(pts, 2); 1262 } 1263 1264#if 0 1265 const SkPoint& addMoveTo(int tIndex, PathWrapper& path, bool active) const { 1266 const SkPoint& pt = xyAtT(tIndex); 1267 if (active) { 1268 path.deferredMove(pt); 1269 } 1270 return pt; 1271 } 1272#endif 1273 1274 // add 2 to edge or out of range values to get T extremes 1275 void addOtherT(int index, double otherT, int otherIndex) { 1276 Span& span = fTs[index]; 1277 #if PIN_ADD_T 1278 if (precisely_less_than_zero(otherT)) { 1279 otherT = 0; 1280 } else if (precisely_greater_than_one(otherT)) { 1281 otherT = 1; 1282 } 1283 #endif 1284 span.fOtherT = otherT; 1285 span.fOtherIndex = otherIndex; 1286 } 1287 1288 void addQuad(const SkPoint pts[3], bool operand) { 1289 init(pts, SkPath::kQuad_Verb, operand); 1290 fBounds.setQuadBounds(pts); 1291 } 1292 1293 // Defer all coincident edge processing until 1294 // after normal intersections have been computed 1295 1296// no need to be tricky; insert in normal T order 1297// resolve overlapping ts when considering coincidence later 1298 1299 // add non-coincident intersection. Resulting edges are sorted in T. 1300 int addT(double newT, Segment* other) { 1301 // FIXME: in the pathological case where there is a ton of intercepts, 1302 // binary search? 1303 int insertedAt = -1; 1304 size_t tCount = fTs.count(); 1305 #if PIN_ADD_T 1306 // FIXME: only do this pinning here (e.g. this is done also in quad/line intersect) 1307 if (precisely_less_than_zero(newT)) { 1308 newT = 0; 1309 } else if (precisely_greater_than_one(newT)) { 1310 newT = 1; 1311 } 1312 #endif 1313 for (size_t index = 0; index < tCount; ++index) { 1314 // OPTIMIZATION: if there are three or more identical Ts, then 1315 // the fourth and following could be further insertion-sorted so 1316 // that all the edges are clockwise or counterclockwise. 1317 // This could later limit segment tests to the two adjacent 1318 // neighbors, although it doesn't help with determining which 1319 // circular direction to go in. 1320 if (newT < fTs[index].fT) { 1321 insertedAt = index; 1322 break; 1323 } 1324 } 1325 Span* span; 1326 if (insertedAt >= 0) { 1327 span = fTs.insert(insertedAt); 1328 } else { 1329 insertedAt = tCount; 1330 span = fTs.append(); 1331 } 1332 span->fT = newT; 1333 span->fOther = other; 1334 span->fPt.fX = SK_ScalarNaN; 1335 span->fWindSum = SK_MinS32; 1336 span->fWindValue = 1; 1337 span->fWindValueOpp = 0; 1338 span->fTiny = false; 1339 if ((span->fDone = newT == 1)) { 1340 ++fDoneSpans; 1341 } 1342 span->fUnsortableStart = false; 1343 span->fUnsortableEnd = false; 1344 if (span - fTs.begin() > 0 && !span[-1].fDone 1345 && !precisely_negative(newT - span[-1].fT) 1346 // && approximately_negative(newT - span[-1].fT) 1347 && xyAtT(&span[-1]) == xyAtT(span)) { 1348 span[-1].fTiny = true; 1349 span[-1].fDone = true; 1350 if (approximately_negative(newT - span[-1].fT)) { 1351 if (approximately_greater_than_one(newT)) { 1352 span[-1].fUnsortableStart = true; 1353 span[-2].fUnsortableEnd = true; 1354 } 1355 if (approximately_less_than_zero(span[-1].fT)) { 1356 span->fUnsortableStart = true; 1357 span[-1].fUnsortableEnd = true; 1358 } 1359 } 1360 ++fDoneSpans; 1361 } 1362 if (fTs.end() - span > 1 && !span->fDone 1363 && !precisely_negative(span[1].fT - newT) 1364 // && approximately_negative(span[1].fT - newT) 1365 && xyAtT(&span[1]) == xyAtT(span)) { 1366 span->fTiny = true; 1367 span->fDone = true; 1368 if (approximately_negative(span[1].fT - newT)) { 1369 if (approximately_greater_than_one(span[1].fT)) { 1370 span->fUnsortableStart = true; 1371 span[-1].fUnsortableEnd = true; 1372 } 1373 if (approximately_less_than_zero(newT)) { 1374 span[1].fUnsortableStart = true; 1375 span->fUnsortableEnd = true; 1376 } 1377 } 1378 ++fDoneSpans; 1379 } 1380 return insertedAt; 1381 } 1382 1383 // set spans from start to end to decrement by one 1384 // note this walks other backwards 1385 // FIMXE: there's probably an edge case that can be constructed where 1386 // two span in one segment are separated by float epsilon on one span but 1387 // not the other, if one segment is very small. For this 1388 // case the counts asserted below may or may not be enough to separate the 1389 // spans. Even if the counts work out, what if the spans aren't correctly 1390 // sorted? It feels better in such a case to match the span's other span 1391 // pointer since both coincident segments must contain the same spans. 1392 void addTCancel(double startT, double endT, Segment& other, 1393 double oStartT, double oEndT) { 1394 SkASSERT(!approximately_negative(endT - startT)); 1395 SkASSERT(!approximately_negative(oEndT - oStartT)); 1396 bool binary = fOperand != other.fOperand; 1397 int index = 0; 1398 while (!approximately_negative(startT - fTs[index].fT)) { 1399 ++index; 1400 } 1401 int oIndex = other.fTs.count(); 1402 while (approximately_positive(other.fTs[--oIndex].fT - oEndT)) 1403 ; 1404 double tRatio = (oEndT - oStartT) / (endT - startT); 1405 Span* test = &fTs[index]; 1406 Span* oTest = &other.fTs[oIndex]; 1407 SkTDArray<double> outsideTs; 1408 SkTDArray<double> oOutsideTs; 1409 do { 1410 bool decrement = test->fWindValue && oTest->fWindValue; 1411 bool track = test->fWindValue || oTest->fWindValue; 1412 double testT = test->fT; 1413 double oTestT = oTest->fT; 1414 Span* span = test; 1415 do { 1416 if (decrement) { 1417 if (binary) { 1418 --(span->fWindValueOpp); 1419 } else { 1420 decrementSpan(span); 1421 } 1422 } else if (track && span->fT < 1 && oTestT < 1) { 1423 TrackOutside(outsideTs, span->fT, oTestT); 1424 } 1425 span = &fTs[++index]; 1426 } while (approximately_negative(span->fT - testT)); 1427 Span* oSpan = oTest; 1428 double otherTMatchStart = oEndT - (span->fT - startT) * tRatio; 1429 double otherTMatchEnd = oEndT - (test->fT - startT) * tRatio; 1430 SkDEBUGCODE(int originalWindValue = oSpan->fWindValue); 1431 while (approximately_negative(otherTMatchStart - oSpan->fT) 1432 && !approximately_negative(otherTMatchEnd - oSpan->fT)) { 1433 #ifdef SK_DEBUG 1434 SkASSERT(originalWindValue == oSpan->fWindValue); 1435 #endif 1436 if (decrement) { 1437 other.decrementSpan(oSpan); 1438 } else if (track && oSpan->fT < 1 && testT < 1) { 1439 TrackOutside(oOutsideTs, oSpan->fT, testT); 1440 } 1441 if (!oIndex) { 1442 break; 1443 } 1444 oSpan = &other.fTs[--oIndex]; 1445 } 1446 test = span; 1447 oTest = oSpan; 1448 } while (!approximately_negative(endT - test->fT)); 1449 SkASSERT(!oIndex || approximately_negative(oTest->fT - oStartT)); 1450 // FIXME: determine if canceled edges need outside ts added 1451 if (!done() && outsideTs.count()) { 1452 double tStart = outsideTs[0]; 1453 double oStart = outsideTs[1]; 1454 addCancelOutsides(tStart, oStart, other, oEndT); 1455 int count = outsideTs.count(); 1456 if (count > 2) { 1457 double tStart = outsideTs[count - 2]; 1458 double oStart = outsideTs[count - 1]; 1459 addCancelOutsides(tStart, oStart, other, oEndT); 1460 } 1461 } 1462 if (!other.done() && oOutsideTs.count()) { 1463 double tStart = oOutsideTs[0]; 1464 double oStart = oOutsideTs[1]; 1465 other.addCancelOutsides(tStart, oStart, *this, endT); 1466 } 1467 } 1468 1469 // set spans from start to end to increment the greater by one and decrement 1470 // the lesser 1471 void addTCoincident(const bool isXor, double startT, double endT, 1472 Segment& other, double oStartT, double oEndT) { 1473 SkASSERT(!approximately_negative(endT - startT)); 1474 SkASSERT(!approximately_negative(oEndT - oStartT)); 1475 bool binary = fOperand != other.fOperand; 1476 int index = 0; 1477 while (!approximately_negative(startT - fTs[index].fT)) { 1478 ++index; 1479 } 1480 int oIndex = 0; 1481 while (!approximately_negative(oStartT - other.fTs[oIndex].fT)) { 1482 ++oIndex; 1483 } 1484 double tRatio = (oEndT - oStartT) / (endT - startT); 1485 Span* test = &fTs[index]; 1486 Span* oTest = &other.fTs[oIndex]; 1487 SkTDArray<double> outsideTs; 1488 SkTDArray<double> xOutsideTs; 1489 SkTDArray<double> oOutsideTs; 1490 SkTDArray<double> oxOutsideTs; 1491 do { 1492 bool transfer = test->fWindValue && oTest->fWindValue; 1493 bool decrementThis = (test->fWindValue < oTest->fWindValue) & !isXor; 1494 bool decrementOther = (test->fWindValue >= oTest->fWindValue) & !isXor; 1495 Span* end = test; 1496 double startT = end->fT; 1497 int startIndex = index; 1498 double oStartT = oTest->fT; 1499 int oStartIndex = oIndex; 1500 do { 1501 if (transfer) { 1502 if (decrementOther) { 1503 #ifdef SK_DEBUG 1504 SkASSERT(abs(end->fWindValue) < gDebugMaxWindValue); 1505 #endif 1506 if (binary) { 1507 ++(end->fWindValueOpp); 1508 } else { 1509 ++(end->fWindValue); 1510 } 1511 } else if (decrementSpan(end)) { 1512 TrackOutside(outsideTs, end->fT, oStartT); 1513 } 1514 } else if (oTest->fWindValue) { 1515 SkASSERT(!decrementOther); 1516 if (startIndex > 0 && fTs[startIndex - 1].fWindValue) { 1517 TrackOutside(xOutsideTs, end->fT, oStartT); 1518 } 1519 } 1520 end = &fTs[++index]; 1521 } while (approximately_negative(end->fT - test->fT)); 1522 // because of the order in which coincidences are resolved, this and other 1523 // may not have the same intermediate points. Compute the corresponding 1524 // intermediate T values (using this as the master, other as the follower) 1525 // and walk other conditionally -- hoping that it catches up in the end 1526 double otherTMatch = (test->fT - startT) * tRatio + oStartT; 1527 Span* oEnd = oTest; 1528 while (!approximately_negative(oEndT - oEnd->fT) && approximately_negative(oEnd->fT - otherTMatch)) { 1529 if (transfer) { 1530 if (decrementThis) { 1531 #ifdef SK_DEBUG 1532 SkASSERT(abs(oEnd->fWindValue) < gDebugMaxWindValue); 1533 #endif 1534 if (binary) { 1535 ++(oEnd->fWindValueOpp); 1536 } else { 1537 ++(oEnd->fWindValue); 1538 } 1539 } else if (other.decrementSpan(oEnd)) { 1540 TrackOutside(oOutsideTs, oEnd->fT, startT); 1541 } 1542 } else if (test->fWindValue) { 1543 SkASSERT(!decrementOther); 1544 if (oStartIndex > 0 && other.fTs[oStartIndex - 1].fWindValue) { 1545 SkASSERT(0); // track for later? 1546 } 1547 } 1548 oEnd = &other.fTs[++oIndex]; 1549 } 1550 test = end; 1551 oTest = oEnd; 1552 } while (!approximately_negative(endT - test->fT)); 1553 SkASSERT(approximately_negative(oTest->fT - oEndT)); 1554 SkASSERT(approximately_negative(oEndT - oTest->fT)); 1555 if (!done()) { 1556 if (outsideTs.count()) { 1557 addCoinOutsides(outsideTs, other, oEndT); 1558 } 1559 if (xOutsideTs.count()) { 1560 addCoinOutsides(xOutsideTs, other, oEndT); 1561 } 1562 } 1563 if (!other.done() && oOutsideTs.count()) { 1564 other.addCoinOutsides(oOutsideTs, *this, endT); 1565 } 1566 } 1567 1568 // FIXME: this doesn't prevent the same span from being added twice 1569 // fix in caller, assert here? 1570 void addTPair(double t, Segment& other, double otherT, bool borrowWind) { 1571 int tCount = fTs.count(); 1572 for (int tIndex = 0; tIndex < tCount; ++tIndex) { 1573 const Span& span = fTs[tIndex]; 1574 if (!approximately_negative(span.fT - t)) { 1575 break; 1576 } 1577 if (approximately_negative(span.fT - t) && span.fOther == &other 1578 && approximately_equal(span.fOtherT, otherT)) { 1579#if DEBUG_ADD_T_PAIR 1580 SkDebugf("%s addTPair duplicate this=%d %1.9g other=%d %1.9g\n", 1581 __FUNCTION__, fID, t, other.fID, otherT); 1582#endif 1583 return; 1584 } 1585 } 1586#if DEBUG_ADD_T_PAIR 1587 SkDebugf("%s addTPair this=%d %1.9g other=%d %1.9g\n", 1588 __FUNCTION__, fID, t, other.fID, otherT); 1589#endif 1590 int insertedAt = addT(t, &other); 1591 int otherInsertedAt = other.addT(otherT, this); 1592 addOtherT(insertedAt, otherT, otherInsertedAt); 1593 other.addOtherT(otherInsertedAt, t, insertedAt); 1594 matchWindingValue(insertedAt, t, borrowWind); 1595 other.matchWindingValue(otherInsertedAt, otherT, borrowWind); 1596 } 1597 1598 void addTwoAngles(int start, int end, SkTDArray<Angle>& angles) const { 1599 // add edge leading into junction 1600 if (fTs[SkMin32(end, start)].fWindValue > 0) { 1601 addAngle(angles, end, start); 1602 } 1603 // add edge leading away from junction 1604 int step = SkSign32(end - start); 1605 int tIndex = nextExactSpan(end, step); 1606 if (tIndex >= 0 && fTs[SkMin32(end, tIndex)].fWindValue > 0) { 1607 addAngle(angles, end, tIndex); 1608 } 1609 } 1610 1611 const Bounds& bounds() const { 1612 return fBounds; 1613 } 1614 1615 void buildAngles(int index, SkTDArray<Angle>& angles) const { 1616 double referenceT = fTs[index].fT; 1617 int lesser = index; 1618 #if PRECISE_T_SORT 1619 while (--lesser >= 0 && precisely_negative(referenceT - fTs[lesser].fT)) { 1620 buildAnglesInner(lesser, angles); 1621 } 1622 do { 1623 buildAnglesInner(index, angles); 1624 } while (++index < fTs.count() && precisely_negative(fTs[index].fT - referenceT)); 1625 #else 1626 while (--lesser >= 0 && approximately_negative(referenceT - fTs[lesser].fT)) { 1627 buildAnglesInner(lesser, angles); 1628 } 1629 do { 1630 buildAnglesInner(index, angles); 1631 } while (++index < fTs.count() && approximately_negative(fTs[index].fT - referenceT)); 1632 #endif 1633 } 1634 1635 void buildAnglesInner(int index, SkTDArray<Angle>& angles) const { 1636 Span* span = &fTs[index]; 1637 Segment* other = span->fOther; 1638 // if there is only one live crossing, and no coincidence, continue 1639 // in the same direction 1640 // if there is coincidence, the only choice may be to reverse direction 1641 // find edge on either side of intersection 1642 int oIndex = span->fOtherIndex; 1643 // if done == -1, prior span has already been processed 1644 int step = 1; 1645 #if PRECISE_T_SORT 1646 int next = other->nextExactSpan(oIndex, step); 1647 #else 1648 int next = other->nextSpan(oIndex, step); 1649 #endif 1650 if (next < 0) { 1651 step = -step; 1652 #if PRECISE_T_SORT 1653 next = other->nextExactSpan(oIndex, step); 1654 #else 1655 next = other->nextSpan(oIndex, step); 1656 #endif 1657 } 1658 // add candidate into and away from junction 1659 other->addTwoAngles(next, oIndex, angles); 1660 } 1661 1662 // figure out if the segment's ascending T goes clockwise or not 1663 // not enough context to write this as shown 1664 // instead, add all segments meeting at the top 1665 // sort them using buildAngleList 1666 // find the first in the sort 1667 // see if ascendingT goes to top 1668 bool clockwise(int /* tIndex */) const { 1669 SkASSERT(0); // incomplete 1670 return false; 1671 } 1672 1673 // FIXME may not need this at all 1674 // FIXME once I figure out the logic, merge this and too close to call 1675 // NOTE not sure if tiny triangles can ever form at the edge, so until we 1676 // see one, only worry about triangles that happen away from 0 and 1 1677 void collapseTriangles(bool isXor) { 1678 if (fTs.count() < 3) { // require t=0, x, 1 at minimum 1679 return; 1680 } 1681 int lastIndex = 1; 1682 double lastT; 1683 while (approximately_less_than_zero((lastT = fTs[lastIndex].fT))) { 1684 ++lastIndex; 1685 } 1686 if (approximately_greater_than_one(lastT)) { 1687 return; 1688 } 1689 int matchIndex = lastIndex; 1690 do { 1691 Span& match = fTs[++matchIndex]; 1692 double matchT = match.fT; 1693 if (approximately_greater_than_one(matchT)) { 1694 return; 1695 } 1696 if (matchT == lastT) { 1697 goto nextSpan; 1698 } 1699 if (approximately_negative(matchT - lastT)) { 1700 Span& last = fTs[lastIndex]; 1701 Segment* lOther = last.fOther; 1702 double lT = last.fOtherT; 1703 if (approximately_less_than_zero(lT) || approximately_greater_than_one(lT)) { 1704 goto nextSpan; 1705 } 1706 Segment* mOther = match.fOther; 1707 double mT = match.fOtherT; 1708 if (approximately_less_than_zero(mT) || approximately_greater_than_one(mT)) { 1709 goto nextSpan; 1710 } 1711 // add new point to connect adjacent spurs 1712 int count = lOther->fTs.count(); 1713 for (int index = 0; index < count; ++index) { 1714 Span& span = lOther->fTs[index]; 1715 if (span.fOther == mOther && approximately_zero(span.fOtherT - mT)) { 1716 goto nextSpan; 1717 } 1718 } 1719 mOther->addTPair(mT, *lOther, lT, false); 1720 // FIXME ? this could go on to detect that spans on mOther, lOther are now coincident 1721 } 1722 nextSpan: 1723 lastIndex = matchIndex; 1724 lastT = matchT; 1725 } while (true); 1726 } 1727 1728 int computeSum(int startIndex, int endIndex) { 1729 SkTDArray<Angle> angles; 1730 addTwoAngles(startIndex, endIndex, angles); 1731 buildAngles(endIndex, angles); 1732 // OPTIMIZATION: check all angles to see if any have computed wind sum 1733 // before sorting (early exit if none) 1734 SkTDArray<Angle*> sorted; 1735 bool sortable = SortAngles(angles, sorted); 1736#if DEBUG_SORT 1737 sorted[0]->segment()->debugShowSort(__FUNCTION__, sorted, 0, 0); 1738#endif 1739 if (!sortable) { 1740 return SK_MinS32; 1741 } 1742 int angleCount = angles.count(); 1743 const Angle* angle; 1744 const Segment* base; 1745 int winding; 1746 int firstIndex = 0; 1747 do { 1748 angle = sorted[firstIndex]; 1749 base = angle->segment(); 1750 winding = base->windSum(angle); 1751 if (winding != SK_MinS32) { 1752 break; 1753 } 1754 if (++firstIndex == angleCount) { 1755 return SK_MinS32; 1756 } 1757 } while (true); 1758 // turn winding into contourWinding 1759 int spanWinding = base->spanSign(angle); 1760 bool inner = useInnerWinding(winding + spanWinding, winding); 1761 #if DEBUG_WINDING 1762 SkDebugf("%s spanWinding=%d winding=%d sign=%d inner=%d result=%d\n", __FUNCTION__, 1763 spanWinding, winding, angle->sign(), inner, 1764 inner ? winding + spanWinding : winding); 1765 #endif 1766 if (inner) { 1767 winding += spanWinding; 1768 } 1769 #if DEBUG_SORT 1770 base->debugShowSort(__FUNCTION__, sorted, firstIndex, winding); 1771 #endif 1772 int nextIndex = firstIndex + 1; 1773 int lastIndex = firstIndex != 0 ? firstIndex : angleCount; 1774 winding -= base->spanSign(angle); 1775 do { 1776 if (nextIndex == angleCount) { 1777 nextIndex = 0; 1778 } 1779 angle = sorted[nextIndex]; 1780 Segment* segment = angle->segment(); 1781 int maxWinding = winding; 1782 winding -= segment->spanSign(angle); 1783 if (segment->windSum(angle) == SK_MinS32) { 1784 if (useInnerWinding(maxWinding, winding)) { 1785 maxWinding = winding; 1786 } 1787 segment->markAndChaseWinding(angle, maxWinding); 1788 } 1789 } while (++nextIndex != lastIndex); 1790 return windSum(SkMin32(startIndex, endIndex)); 1791 } 1792 1793 int crossedSpan(const SkPoint& basePt, SkScalar& bestY, double& hitT) const { 1794 int bestT = -1; 1795 SkScalar top = bounds().fTop; 1796 SkScalar bottom = bounds().fBottom; 1797 int end = 0; 1798 do { 1799 int start = end; 1800 end = nextSpan(start, 1); 1801 if (fTs[start].fWindValue == 0) { 1802 continue; 1803 } 1804 SkPoint edge[4]; 1805 double startT = fTs[start].fT; 1806 double endT = fTs[end].fT; 1807 (*SegmentSubDivide[fVerb])(fPts, startT, endT, edge); 1808 // intersect ray starting at basePt with edge 1809 Intersections intersections; 1810 // FIXME: always use original and limit results to T values within 1811 // start t and end t. 1812 // OPTIMIZE: use specialty function that intersects ray with curve, 1813 // returning t values only for curve (we don't care about t on ray) 1814 int pts = (*VSegmentIntersect[fVerb])(edge, top, bottom, basePt.fX, 1815 false, intersections); 1816 if (pts == 0) { 1817 continue; 1818 } 1819 if (pts > 1 && fVerb == SkPath::kLine_Verb) { 1820 // if the intersection is edge on, wait for another one 1821 continue; 1822 } 1823 for (int index = 0; index < pts; ++index) { 1824 SkPoint pt; 1825 double foundT = intersections.fT[0][index]; 1826 double testT = startT + (endT - startT) * foundT; 1827 (*SegmentXYAtT[fVerb])(fPts, testT, &pt); 1828 if (bestY < pt.fY && pt.fY < basePt.fY) { 1829 if (fVerb > SkPath::kLine_Verb 1830 && !approximately_less_than_zero(foundT) 1831 && !approximately_greater_than_one(foundT)) { 1832 SkScalar dx = (*SegmentDXAtT[fVerb])(fPts, testT); 1833 if (approximately_zero(dx)) { 1834 continue; 1835 } 1836 } 1837 bestY = pt.fY; 1838 bestT = foundT < 1 ? start : end; 1839 hitT = testT; 1840 } 1841 } 1842 } while (fTs[end].fT != 1); 1843 return bestT; 1844 } 1845 1846 bool crossedSpanHalves(const SkPoint& basePt, bool leftHalf, bool rightHalf) { 1847 // if a segment is connected to this one, consider it crossing 1848 int tIndex; 1849 if (fPts[0].fX == basePt.fX) { 1850 tIndex = 0; 1851 do { 1852 const Span& sSpan = fTs[tIndex]; 1853 const Segment* sOther = sSpan.fOther; 1854 if (!sOther->fTs[sSpan.fOtherIndex].fWindValue) { 1855 continue; 1856 } 1857 if (leftHalf ? sOther->fBounds.fLeft < basePt.fX 1858 : sOther->fBounds.fRight > basePt.fX) { 1859 return true; 1860 } 1861 } while (fTs[++tIndex].fT == 0); 1862 } 1863 if (fPts[fVerb].fX == basePt.fX) { 1864 tIndex = fTs.count() - 1; 1865 do { 1866 const Span& eSpan = fTs[tIndex]; 1867 const Segment* eOther = eSpan.fOther; 1868 if (!eOther->fTs[eSpan.fOtherIndex].fWindValue) { 1869 continue; 1870 } 1871 if (leftHalf ? eOther->fBounds.fLeft < basePt.fX 1872 : eOther->fBounds.fRight > basePt.fX) { 1873 return true; 1874 } 1875 } while (fTs[--tIndex].fT == 1); 1876 } 1877 return false; 1878 } 1879 1880 bool decrementSpan(Span* span) { 1881 SkASSERT(span->fWindValue > 0); 1882 if (--(span->fWindValue) == 0) { 1883 if (!span->fDone) { 1884 span->fDone = true; 1885 ++fDoneSpans; 1886 } 1887 return true; 1888 } 1889 return false; 1890 } 1891 1892 bool done() const { 1893 SkASSERT(fDoneSpans <= fTs.count()); 1894 return fDoneSpans == fTs.count(); 1895 } 1896 1897 bool done(int min) const { 1898 return fTs[min].fDone; 1899 } 1900 1901 bool done(const Angle& angle) const { 1902 return done(SkMin32(angle.start(), angle.end())); 1903 } 1904 1905 Segment* findNextOp(SkTDArray<Span*>& chase, bool active, 1906 int& nextStart, int& nextEnd, int& winding, int& spanWinding, 1907 bool& unsortable, ShapeOp op, 1908 const int aXorMask, const int bXorMask) { 1909 const int startIndex = nextStart; 1910 const int endIndex = nextEnd; 1911 int outerWinding = winding; 1912 int innerWinding = winding + spanWinding; 1913 #if DEBUG_WINDING 1914 SkDebugf("%s winding=%d spanWinding=%d outerWinding=%d innerWinding=%d\n", 1915 __FUNCTION__, winding, spanWinding, outerWinding, innerWinding); 1916 #endif 1917 if (useInnerWinding(outerWinding, innerWinding)) { 1918 outerWinding = innerWinding; 1919 } 1920 SkASSERT(startIndex != endIndex); 1921 int count = fTs.count(); 1922 SkASSERT(startIndex < endIndex ? startIndex < count - 1 1923 : startIndex > 0); 1924 int step = SkSign32(endIndex - startIndex); 1925 #if PRECISE_T_SORT 1926 int end = nextExactSpan(startIndex, step); 1927 #else 1928 int end = nextSpan(startIndex, step); 1929 #endif 1930 SkASSERT(end >= 0); 1931 Span* endSpan = &fTs[end]; 1932 Segment* other; 1933 if (isSimple(end)) { 1934 // mark the smaller of startIndex, endIndex done, and all adjacent 1935 // spans with the same T value (but not 'other' spans) 1936 #if DEBUG_WINDING 1937 SkDebugf("%s simple\n", __FUNCTION__); 1938 #endif 1939 markDone(SkMin32(startIndex, endIndex), outerWinding); 1940 other = endSpan->fOther; 1941 nextStart = endSpan->fOtherIndex; 1942 double startT = other->fTs[nextStart].fT; 1943 nextEnd = nextStart; 1944 do { 1945 nextEnd += step; 1946 } 1947 #if PRECISE_T_SORT 1948 while (precisely_zero(startT - other->fTs[nextEnd].fT)); 1949 #else 1950 while (approximately_zero(startT - other->fTs[nextEnd].fT)); 1951 #endif 1952 SkASSERT(step < 0 ? nextEnd >= 0 : nextEnd < other->fTs.count()); 1953 return other; 1954 } 1955 // more than one viable candidate -- measure angles to find best 1956 SkTDArray<Angle> angles; 1957 SkASSERT(startIndex - endIndex != 0); 1958 SkASSERT((startIndex - endIndex < 0) ^ (step < 0)); 1959 addTwoAngles(startIndex, end, angles); 1960 buildAngles(end, angles); 1961 SkTDArray<Angle*> sorted; 1962 bool sortable = SortAngles(angles, sorted); 1963 int angleCount = angles.count(); 1964 int firstIndex = findStartingEdge(sorted, startIndex, end); 1965 SkASSERT(firstIndex >= 0); 1966 #if DEBUG_SORT 1967 debugShowSort(__FUNCTION__, sorted, firstIndex, winding); 1968 #endif 1969 if (!sortable) { 1970 unsortable = true; 1971 return NULL; 1972 } 1973 SkASSERT(sorted[firstIndex]->segment() == this); 1974 #if DEBUG_WINDING 1975 SkDebugf("%s [%d] sign=%d\n", __FUNCTION__, firstIndex, sorted[firstIndex]->sign()); 1976 #endif 1977 int aSumWinding = winding; 1978 int bSumWinding = winding; 1979 bool angleIsOp = sorted[firstIndex]->segment()->operand(); 1980 int angleSpan = spanSign(sorted[firstIndex]); 1981 if (angleIsOp) { 1982 bSumWinding -= angleSpan; 1983 } else { 1984 aSumWinding -= angleSpan; 1985 } 1986 int nextIndex = firstIndex + 1; 1987 int lastIndex = firstIndex != 0 ? firstIndex : angleCount; 1988 const Angle* foundAngle = NULL; 1989 // FIXME: found done logic probably fails if there are more than 4 1990 // sorted angles. It should bias towards the first and last undone 1991 // edges -- but not sure that it won't choose a middle (incorrect) 1992 // edge if one is undone 1993 bool foundDone = false; 1994 bool foundDone2 = false; 1995 // iterate through the angle, and compute everyone's winding 1996 bool altFlipped = false; 1997 bool foundFlipped = false; 1998 int foundMax = SK_MinS32; 1999 int foundSum = SK_MinS32; 2000 Segment* nextSegment; 2001 int lastNonZeroSum = winding; 2002 do { 2003 if (nextIndex == angleCount) { 2004 nextIndex = 0; 2005 } 2006 const Angle* nextAngle = sorted[nextIndex]; 2007 nextSegment = nextAngle->segment(); 2008 bool nextDone = nextSegment->done(*nextAngle); 2009 bool nextTiny = nextSegment->tiny(*nextAngle); 2010 angleIsOp = nextSegment->operand(); 2011 int sumWinding = angleIsOp ? bSumWinding : aSumWinding; 2012 int maxWinding = sumWinding; 2013 if (sumWinding) { 2014 lastNonZeroSum = sumWinding; 2015 } 2016 sumWinding -= nextSegment->spanSign(nextAngle); 2017 int xorMask = nextSegment->operand() ? bXorMask : aXorMask; 2018 bool otherNonZero; 2019 if (angleIsOp) { 2020 bSumWinding = sumWinding; 2021 otherNonZero = aSumWinding & aXorMask; 2022 } else { 2023 aSumWinding = sumWinding; 2024 otherNonZero = bSumWinding & bXorMask; 2025 } 2026 altFlipped ^= lastNonZeroSum * sumWinding < 0; // flip if different signs 2027 #if 0 && DEBUG_WINDING 2028 SkASSERT(abs(sumWinding) <= gDebugMaxWindSum); 2029 SkDebugf("%s [%d] maxWinding=%d sumWinding=%d sign=%d altFlipped=%d\n", __FUNCTION__, 2030 nextIndex, maxWinding, sumWinding, nextAngle->sign(), altFlipped); 2031 #endif 2032 2033 if (!(sumWinding & xorMask) && activeOp(angleIsOp, otherNonZero, op)) { 2034 if (!active) { 2035 markDone(SkMin32(startIndex, endIndex), outerWinding); 2036 // FIXME: seems like a bug that this isn't calling userInnerWinding 2037 nextSegment->markWinding(SkMin32(nextAngle->start(), 2038 nextAngle->end()), maxWinding); 2039 #if DEBUG_WINDING 2040 SkDebugf("%s [%d] inactive\n", __FUNCTION__, nextIndex); 2041 #endif 2042 return NULL; 2043 } 2044 if (!foundAngle || foundDone) { 2045 foundAngle = nextAngle; 2046 foundDone = nextDone && !nextTiny; 2047 foundFlipped = altFlipped; 2048 foundMax = maxWinding; 2049 } 2050 continue; 2051 } 2052 if (!(maxWinding & xorMask) && (!foundAngle || foundDone2) 2053 && activeOp(angleIsOp, otherNonZero, op)) { 2054 #if DEBUG_WINDING 2055 if (foundAngle && foundDone2) { 2056 SkDebugf("%s [%d] !foundAngle && foundDone2\n", __FUNCTION__, nextIndex); 2057 } 2058 #endif 2059 foundAngle = nextAngle; 2060 foundDone2 = nextDone && !nextTiny; 2061 foundFlipped = altFlipped; 2062 foundSum = sumWinding; 2063 } 2064 if (nextSegment->done()) { 2065 continue; 2066 } 2067 // if the winding is non-zero, nextAngle does not connect to 2068 // current chain. If we haven't done so already, mark the angle 2069 // as done, record the winding value, and mark connected unambiguous 2070 // segments as well. 2071 if (nextSegment->windSum(nextAngle) == SK_MinS32) { 2072 if (useInnerWinding(maxWinding, sumWinding)) { 2073 maxWinding = sumWinding; 2074 } 2075 Span* last; 2076 if (foundAngle) { 2077 last = nextSegment->markAndChaseWinding(nextAngle, maxWinding); 2078 } else { 2079 last = nextSegment->markAndChaseDone(nextAngle, maxWinding); 2080 } 2081 if (last) { 2082 *chase.append() = last; 2083 } 2084 } 2085 } while (++nextIndex != lastIndex); 2086 markDone(SkMin32(startIndex, endIndex), outerWinding); 2087 if (!foundAngle) { 2088 return NULL; 2089 } 2090 nextStart = foundAngle->start(); 2091 nextEnd = foundAngle->end(); 2092 nextSegment = foundAngle->segment(); 2093 int flipped = foundFlipped ? -1 : 1; 2094 spanWinding = SkSign32(spanWinding) * flipped * nextSegment->windValue( 2095 SkMin32(nextStart, nextEnd)); 2096 if (winding) { 2097 #if DEBUG_WINDING 2098 SkDebugf("%s ---6 winding=%d foundSum=", __FUNCTION__, winding); 2099 if (foundSum == SK_MinS32) { 2100 SkDebugf("?"); 2101 } else { 2102 SkDebugf("%d", foundSum); 2103 } 2104 SkDebugf(" foundMax="); 2105 if (foundMax == SK_MinS32) { 2106 SkDebugf("?"); 2107 } else { 2108 SkDebugf("%d", foundMax); 2109 } 2110 SkDebugf("\n"); 2111 #endif 2112 winding = foundSum; 2113 } 2114 #if DEBUG_WINDING 2115 SkDebugf("%s spanWinding=%d flipped=%d\n", __FUNCTION__, spanWinding, flipped); 2116 #endif 2117 return nextSegment; 2118 } 2119 2120 // so the span needs to contain the pairing info found here 2121 // this should include the winding computed for the edge, and 2122 // what edge it connects to, and whether it is discarded 2123 // (maybe discarded == abs(winding) > 1) ? 2124 // only need derivatives for duration of sorting, add a new struct 2125 // for pairings, remove extra spans that have zero length and 2126 // reference an unused other 2127 // for coincident, the last span on the other may be marked done 2128 // (always?) 2129 2130 // if loop is exhausted, contour may be closed. 2131 // FIXME: pass in close point so we can check for closure 2132 2133 // given a segment, and a sense of where 'inside' is, return the next 2134 // segment. If this segment has an intersection, or ends in multiple 2135 // segments, find the mate that continues the outside. 2136 // note that if there are multiples, but no coincidence, we can limit 2137 // choices to connections in the correct direction 2138 2139 // mark found segments as done 2140 2141 // start is the index of the beginning T of this edge 2142 // it is guaranteed to have an end which describes a non-zero length (?) 2143 // winding -1 means ccw, 1 means cw 2144 Segment* findNextWinding(SkTDArray<Span*>& chase, bool active, 2145 int& nextStart, int& nextEnd, int& winding, int& spanWinding, 2146 bool& unsortable) { 2147 const int startIndex = nextStart; 2148 const int endIndex = nextEnd; 2149 int outerWinding = winding; 2150 int innerWinding = winding + spanWinding; 2151 #if DEBUG_WINDING 2152 SkDebugf("%s winding=%d spanWinding=%d outerWinding=%d innerWinding=%d\n", 2153 __FUNCTION__, winding, spanWinding, outerWinding, innerWinding); 2154 #endif 2155 if (useInnerWinding(outerWinding, innerWinding)) { 2156 outerWinding = innerWinding; 2157 } 2158 SkASSERT(startIndex != endIndex); 2159 int count = fTs.count(); 2160 SkASSERT(startIndex < endIndex ? startIndex < count - 1 2161 : startIndex > 0); 2162 int step = SkSign32(endIndex - startIndex); 2163 #if PRECISE_T_SORT 2164 int end = nextExactSpan(startIndex, step); 2165 #else 2166 int end = nextSpan(startIndex, step); 2167 #endif 2168 SkASSERT(end >= 0); 2169 Span* endSpan = &fTs[end]; 2170 Segment* other; 2171 if (isSimple(end)) { 2172 // mark the smaller of startIndex, endIndex done, and all adjacent 2173 // spans with the same T value (but not 'other' spans) 2174 #if DEBUG_WINDING 2175 SkDebugf("%s simple\n", __FUNCTION__); 2176 #endif 2177 markDone(SkMin32(startIndex, endIndex), outerWinding); 2178 other = endSpan->fOther; 2179 nextStart = endSpan->fOtherIndex; 2180 double startT = other->fTs[nextStart].fT; 2181 nextEnd = nextStart; 2182 do { 2183 nextEnd += step; 2184 } 2185 #if PRECISE_T_SORT 2186 while (precisely_zero(startT - other->fTs[nextEnd].fT)); 2187 #else 2188 while (approximately_zero(startT - other->fTs[nextEnd].fT)); 2189 #endif 2190 SkASSERT(step < 0 ? nextEnd >= 0 : nextEnd < other->fTs.count()); 2191 return other; 2192 } 2193 // more than one viable candidate -- measure angles to find best 2194 SkTDArray<Angle> angles; 2195 SkASSERT(startIndex - endIndex != 0); 2196 SkASSERT((startIndex - endIndex < 0) ^ (step < 0)); 2197 addTwoAngles(startIndex, end, angles); 2198 buildAngles(end, angles); 2199 SkTDArray<Angle*> sorted; 2200 bool sortable = SortAngles(angles, sorted); 2201 int angleCount = angles.count(); 2202 int firstIndex = findStartingEdge(sorted, startIndex, end); 2203 SkASSERT(firstIndex >= 0); 2204 #if DEBUG_SORT 2205 debugShowSort(__FUNCTION__, sorted, firstIndex, winding); 2206 #endif 2207 if (!sortable) { 2208 unsortable = true; 2209 return NULL; 2210 } 2211 SkASSERT(sorted[firstIndex]->segment() == this); 2212 #if DEBUG_WINDING 2213 SkDebugf("%s [%d] sign=%d\n", __FUNCTION__, firstIndex, sorted[firstIndex]->sign()); 2214 #endif 2215 int sumWinding = winding - spanSign(sorted[firstIndex]); 2216 int nextIndex = firstIndex + 1; 2217 int lastIndex = firstIndex != 0 ? firstIndex : angleCount; 2218 const Angle* foundAngle = NULL; 2219 // FIXME: found done logic probably fails if there are more than 4 2220 // sorted angles. It should bias towards the first and last undone 2221 // edges -- but not sure that it won't choose a middle (incorrect) 2222 // edge if one is undone 2223 bool foundDone = false; 2224 bool foundDone2 = false; 2225 // iterate through the angle, and compute everyone's winding 2226 bool altFlipped = false; 2227 bool foundFlipped = false; 2228 int foundMax = SK_MinS32; 2229 int foundSum = SK_MinS32; 2230 Segment* nextSegment; 2231 int lastNonZeroSum = winding; 2232 do { 2233 if (nextIndex == angleCount) { 2234 nextIndex = 0; 2235 } 2236 const Angle* nextAngle = sorted[nextIndex]; 2237 int maxWinding = sumWinding; 2238 if (sumWinding) { 2239 lastNonZeroSum = sumWinding; 2240 } 2241 nextSegment = nextAngle->segment(); 2242 bool nextDone = nextSegment->done(*nextAngle); 2243 bool nextTiny = nextSegment->tiny(*nextAngle); 2244 sumWinding -= nextSegment->spanSign(nextAngle); 2245 altFlipped ^= lastNonZeroSum * sumWinding < 0; // flip if different signs 2246 #if 0 && DEBUG_WINDING 2247 SkASSERT(abs(sumWinding) <= gDebugMaxWindSum); 2248 SkDebugf("%s [%d] maxWinding=%d sumWinding=%d sign=%d altFlipped=%d\n", __FUNCTION__, 2249 nextIndex, maxWinding, sumWinding, nextAngle->sign(), altFlipped); 2250 #endif 2251 if (!sumWinding) { 2252 if (!active) { 2253 markDone(SkMin32(startIndex, endIndex), outerWinding); 2254 // FIXME: seems like a bug that this isn't calling userInnerWinding 2255 nextSegment->markWinding(SkMin32(nextAngle->start(), 2256 nextAngle->end()), maxWinding); 2257 #if DEBUG_WINDING 2258 SkDebugf("%s [%d] inactive\n", __FUNCTION__, nextIndex); 2259 #endif 2260 return NULL; 2261 } 2262 if (!foundAngle || foundDone) { 2263 foundAngle = nextAngle; 2264 foundDone = nextDone && !nextTiny; 2265 foundFlipped = altFlipped; 2266 foundMax = maxWinding; 2267 } 2268 continue; 2269 } 2270 2271 if (!maxWinding && (!foundAngle || foundDone2)) { 2272 #if DEBUG_WINDING 2273 if (foundAngle && foundDone2) { 2274 SkDebugf("%s [%d] !foundAngle && foundDone2\n", __FUNCTION__, nextIndex); 2275 } 2276 #endif 2277 foundAngle = nextAngle; 2278 foundDone2 = nextDone && !nextTiny; 2279 foundFlipped = altFlipped; 2280 foundSum = sumWinding; 2281 } 2282 if (nextSegment->done()) { 2283 continue; 2284 } 2285 // if the winding is non-zero, nextAngle does not connect to 2286 // current chain. If we haven't done so already, mark the angle 2287 // as done, record the winding value, and mark connected unambiguous 2288 // segments as well. 2289 if (nextSegment->windSum(nextAngle) == SK_MinS32) { 2290 if (useInnerWinding(maxWinding, sumWinding)) { 2291 maxWinding = sumWinding; 2292 } 2293 Span* last; 2294 if (foundAngle) { 2295 last = nextSegment->markAndChaseWinding(nextAngle, maxWinding); 2296 } else { 2297 last = nextSegment->markAndChaseDone(nextAngle, maxWinding); 2298 } 2299 if (last) { 2300 *chase.append() = last; 2301 } 2302 } 2303 } while (++nextIndex != lastIndex); 2304 markDone(SkMin32(startIndex, endIndex), outerWinding); 2305 if (!foundAngle) { 2306 return NULL; 2307 } 2308 nextStart = foundAngle->start(); 2309 nextEnd = foundAngle->end(); 2310 nextSegment = foundAngle->segment(); 2311 int flipped = foundFlipped ? -1 : 1; 2312 spanWinding = SkSign32(spanWinding) * flipped * nextSegment->windValue( 2313 SkMin32(nextStart, nextEnd)); 2314 if (winding) { 2315 #if DEBUG_WINDING 2316 SkDebugf("%s ---6 winding=%d foundSum=", __FUNCTION__, winding); 2317 if (foundSum == SK_MinS32) { 2318 SkDebugf("?"); 2319 } else { 2320 SkDebugf("%d", foundSum); 2321 } 2322 SkDebugf(" foundMax="); 2323 if (foundMax == SK_MinS32) { 2324 SkDebugf("?"); 2325 } else { 2326 SkDebugf("%d", foundMax); 2327 } 2328 SkDebugf("\n"); 2329 #endif 2330 winding = foundSum; 2331 } 2332 #if DEBUG_WINDING 2333 SkDebugf("%s spanWinding=%d flipped=%d\n", __FUNCTION__, spanWinding, flipped); 2334 #endif 2335 return nextSegment; 2336 } 2337 2338 Segment* findNextXor(int& nextStart, int& nextEnd, bool& unsortable) { 2339 const int startIndex = nextStart; 2340 const int endIndex = nextEnd; 2341 SkASSERT(startIndex != endIndex); 2342 int count = fTs.count(); 2343 SkASSERT(startIndex < endIndex ? startIndex < count - 1 2344 : startIndex > 0); 2345 int step = SkSign32(endIndex - startIndex); 2346 #if PRECISE_T_SORT 2347 int end = nextExactSpan(startIndex, step); 2348 #else 2349 int end = nextSpan(startIndex, step); 2350 #endif 2351 SkASSERT(end >= 0); 2352 Span* endSpan = &fTs[end]; 2353 Segment* other; 2354 markDone(SkMin32(startIndex, endIndex), 1); 2355 if (isSimple(end)) { 2356 #if DEBUG_WINDING 2357 SkDebugf("%s simple\n", __FUNCTION__); 2358 #endif 2359 other = endSpan->fOther; 2360 nextStart = endSpan->fOtherIndex; 2361 double startT = other->fTs[nextStart].fT; 2362 SkDEBUGCODE(bool firstLoop = true;) 2363 if ((approximately_less_than_zero(startT) && step < 0) 2364 || (approximately_greater_than_one(startT) && step > 0)) { 2365 step = -step; 2366 SkDEBUGCODE(firstLoop = false;) 2367 } 2368 do { 2369 nextEnd = nextStart; 2370 do { 2371 nextEnd += step; 2372 } 2373 #if PRECISE_T_SORT 2374 while (precisely_zero(startT - other->fTs[nextEnd].fT)); 2375 #else 2376 while (approximately_zero(startT - other->fTs[nextEnd].fT)); 2377 #endif 2378 if (other->fTs[SkMin32(nextStart, nextEnd)].fWindValue) { 2379 break; 2380 } 2381 #ifdef SK_DEBUG 2382 SkASSERT(firstLoop); 2383 #endif 2384 SkDEBUGCODE(firstLoop = false;) 2385 step = -step; 2386 } while (true); 2387 SkASSERT(step < 0 ? nextEnd >= 0 : nextEnd < other->fTs.count()); 2388 return other; 2389 } 2390 SkTDArray<Angle> angles; 2391 SkASSERT(startIndex - endIndex != 0); 2392 SkASSERT((startIndex - endIndex < 0) ^ (step < 0)); 2393 addTwoAngles(startIndex, end, angles); 2394 buildAngles(end, angles); 2395 SkTDArray<Angle*> sorted; 2396 bool sortable = SortAngles(angles, sorted); 2397 int angleCount = angles.count(); 2398 int firstIndex = findStartingEdge(sorted, startIndex, end); 2399 SkASSERT(firstIndex >= 0); 2400 #if DEBUG_SORT 2401 debugShowSort(__FUNCTION__, sorted, firstIndex, 0); 2402 #endif 2403 if (!sortable) { 2404 unsortable = true; 2405 return NULL; 2406 } 2407 SkASSERT(sorted[firstIndex]->segment() == this); 2408 int nextIndex = firstIndex + 1; 2409 int lastIndex = firstIndex != 0 ? firstIndex : angleCount; 2410 const Angle* nextAngle; 2411 Segment* nextSegment; 2412 do { 2413 if (nextIndex == angleCount) { 2414 nextIndex = 0; 2415 } 2416 nextAngle = sorted[nextIndex]; 2417 nextSegment = nextAngle->segment(); 2418 if (!nextSegment->done(*nextAngle)) { 2419 break; 2420 } 2421 if (++nextIndex == lastIndex) { 2422 return NULL; 2423 } 2424 } while (true); 2425 nextStart = nextAngle->start(); 2426 nextEnd = nextAngle->end(); 2427 return nextSegment; 2428 } 2429 2430 int findStartingEdge(SkTDArray<Angle*>& sorted, int start, int end) { 2431 int angleCount = sorted.count(); 2432 int firstIndex = -1; 2433 for (int angleIndex = 0; angleIndex < angleCount; ++angleIndex) { 2434 const Angle* angle = sorted[angleIndex]; 2435 if (angle->segment() == this && angle->start() == end && 2436 angle->end() == start) { 2437 firstIndex = angleIndex; 2438 break; 2439 } 2440 } 2441 return firstIndex; 2442 } 2443 2444 // FIXME: this is tricky code; needs its own unit test 2445 void findTooCloseToCall(bool isXor) { 2446 int count = fTs.count(); 2447 if (count < 3) { // require t=0, x, 1 at minimum 2448 return; 2449 } 2450 int matchIndex = 0; 2451 int moCount; 2452 Span* match; 2453 Segment* mOther; 2454 do { 2455 match = &fTs[matchIndex]; 2456 mOther = match->fOther; 2457 // FIXME: allow quads, cubics to be near coincident? 2458 if (mOther->fVerb == SkPath::kLine_Verb) { 2459 moCount = mOther->fTs.count(); 2460 if (moCount >= 3) { 2461 break; 2462 } 2463 } 2464 if (++matchIndex >= count) { 2465 return; 2466 } 2467 } while (true); // require t=0, x, 1 at minimum 2468 // OPTIMIZATION: defer matchPt until qualifying toCount is found? 2469 const SkPoint* matchPt = &xyAtT(match); 2470 // look for a pair of nearby T values that map to the same (x,y) value 2471 // if found, see if the pair of other segments share a common point. If 2472 // so, the span from here to there is coincident. 2473 for (int index = matchIndex + 1; index < count; ++index) { 2474 Span* test = &fTs[index]; 2475 if (test->fDone) { 2476 continue; 2477 } 2478 Segment* tOther = test->fOther; 2479 if (tOther->fVerb != SkPath::kLine_Verb) { 2480 continue; // FIXME: allow quads, cubics to be near coincident? 2481 } 2482 int toCount = tOther->fTs.count(); 2483 if (toCount < 3) { // require t=0, x, 1 at minimum 2484 continue; 2485 } 2486 const SkPoint* testPt = &xyAtT(test); 2487 if (*matchPt != *testPt) { 2488 matchIndex = index; 2489 moCount = toCount; 2490 match = test; 2491 mOther = tOther; 2492 matchPt = testPt; 2493 continue; 2494 } 2495 int moStart = -1; 2496 int moEnd = -1; 2497 double moStartT, moEndT; 2498 for (int moIndex = 0; moIndex < moCount; ++moIndex) { 2499 Span& moSpan = mOther->fTs[moIndex]; 2500 if (moSpan.fDone) { 2501 continue; 2502 } 2503 if (moSpan.fOther == this) { 2504 if (moSpan.fOtherT == match->fT) { 2505 moStart = moIndex; 2506 moStartT = moSpan.fT; 2507 } 2508 continue; 2509 } 2510 if (moSpan.fOther == tOther) { 2511 if (tOther->fTs[moSpan.fOtherIndex].fWindValue == 0) { 2512 moStart = -1; 2513 break; 2514 } 2515 SkASSERT(moEnd == -1); 2516 moEnd = moIndex; 2517 moEndT = moSpan.fT; 2518 } 2519 } 2520 if (moStart < 0 || moEnd < 0) { 2521 continue; 2522 } 2523 // FIXME: if moStartT, moEndT are initialized to NaN, can skip this test 2524 if (approximately_equal(moStartT, moEndT)) { 2525 continue; 2526 } 2527 int toStart = -1; 2528 int toEnd = -1; 2529 double toStartT, toEndT; 2530 for (int toIndex = 0; toIndex < toCount; ++toIndex) { 2531 Span& toSpan = tOther->fTs[toIndex]; 2532 if (toSpan.fDone) { 2533 continue; 2534 } 2535 if (toSpan.fOther == this) { 2536 if (toSpan.fOtherT == test->fT) { 2537 toStart = toIndex; 2538 toStartT = toSpan.fT; 2539 } 2540 continue; 2541 } 2542 if (toSpan.fOther == mOther && toSpan.fOtherT == moEndT) { 2543 if (mOther->fTs[toSpan.fOtherIndex].fWindValue == 0) { 2544 moStart = -1; 2545 break; 2546 } 2547 SkASSERT(toEnd == -1); 2548 toEnd = toIndex; 2549 toEndT = toSpan.fT; 2550 } 2551 } 2552 // FIXME: if toStartT, toEndT are initialized to NaN, can skip this test 2553 if (toStart <= 0 || toEnd <= 0) { 2554 continue; 2555 } 2556 if (approximately_equal(toStartT, toEndT)) { 2557 continue; 2558 } 2559 // test to see if the segment between there and here is linear 2560 if (!mOther->isLinear(moStart, moEnd) 2561 || !tOther->isLinear(toStart, toEnd)) { 2562 continue; 2563 } 2564 bool flipped = (moStart - moEnd) * (toStart - toEnd) < 1; 2565 if (flipped) { 2566 mOther->addTCancel(moStartT, moEndT, *tOther, toEndT, toStartT); 2567 } else { 2568 // FIXME: this is bogus for multiple ops 2569 // the xorMask needs to be accumulated from the union of the two 2570 // edges -- which means that the segment must have its own copy of the mask 2571 mOther->addTCoincident(isXor, moStartT, moEndT, *tOther, toStartT, toEndT); 2572 } 2573 } 2574 } 2575 2576 // start here; 2577 // either: 2578 // a) mark spans with either end unsortable as done, or 2579 // b) rewrite findTop / findTopSegment / findTopContour to iterate further 2580 // when encountering an unsortable span 2581 2582 // OPTIMIZATION : for a pair of lines, can we compute points at T (cached) 2583 // and use more concise logic like the old edge walker code? 2584 // FIXME: this needs to deal with coincident edges 2585 Segment* findTop(int& tIndex, int& endIndex) { 2586 // iterate through T intersections and return topmost 2587 // topmost tangent from y-min to first pt is closer to horizontal 2588 SkASSERT(!done()); 2589 int firstT; 2590 int lastT; 2591 SkPoint topPt; 2592 topPt.fY = SK_ScalarMax; 2593 int count = fTs.count(); 2594 // see if either end is not done since we want smaller Y of the pair 2595 bool lastDone = true; 2596 bool lastUnsortable = false; 2597 for (int index = 0; index < count; ++index) { 2598 const Span& span = fTs[index]; 2599 if (span.fUnsortableStart | lastUnsortable) { 2600 goto next; 2601 } 2602 if (!span.fDone | !lastDone) { 2603 const SkPoint& intercept = xyAtT(&span); 2604 if (topPt.fY > intercept.fY || (topPt.fY == intercept.fY 2605 && topPt.fX > intercept.fX)) { 2606 topPt = intercept; 2607 firstT = lastT = index; 2608 } else if (topPt == intercept) { 2609 lastT = index; 2610 } 2611 } 2612 next: 2613 lastDone = span.fDone; 2614 lastUnsortable = span.fUnsortableEnd; 2615 } 2616 // sort the edges to find the leftmost 2617 int step = 1; 2618 int end = nextSpan(firstT, step); 2619 if (end == -1) { 2620 step = -1; 2621 end = nextSpan(firstT, step); 2622 SkASSERT(end != -1); 2623 } 2624 // if the topmost T is not on end, or is three-way or more, find left 2625 // look for left-ness from tLeft to firstT (matching y of other) 2626 SkTDArray<Angle> angles; 2627 SkASSERT(firstT - end != 0); 2628 addTwoAngles(end, firstT, angles); 2629 buildAngles(firstT, angles); 2630 SkTDArray<Angle*> sorted; 2631 bool sortable = SortAngles(angles, sorted); 2632 #if DEBUG_SORT 2633 sorted[0]->segment()->debugShowSort(__FUNCTION__, sorted, 0, 0); 2634 #endif 2635 if (!sortable) { 2636 return NULL; 2637 } 2638 // skip edges that have already been processed 2639 firstT = -1; 2640 Segment* leftSegment; 2641 do { 2642 const Angle* angle = sorted[++firstT]; 2643 SkASSERT(!angle->unsortable()); 2644 leftSegment = angle->segment(); 2645 tIndex = angle->end(); 2646 endIndex = angle->start(); 2647 } while (leftSegment->fTs[SkMin32(tIndex, endIndex)].fDone); 2648 return leftSegment; 2649 } 2650 2651 // FIXME: not crazy about this 2652 // when the intersections are performed, the other index is into an 2653 // incomplete array. as the array grows, the indices become incorrect 2654 // while the following fixes the indices up again, it isn't smart about 2655 // skipping segments whose indices are already correct 2656 // assuming we leave the code that wrote the index in the first place 2657 void fixOtherTIndex() { 2658 int iCount = fTs.count(); 2659 for (int i = 0; i < iCount; ++i) { 2660 Span& iSpan = fTs[i]; 2661 double oT = iSpan.fOtherT; 2662 Segment* other = iSpan.fOther; 2663 int oCount = other->fTs.count(); 2664 for (int o = 0; o < oCount; ++o) { 2665 Span& oSpan = other->fTs[o]; 2666 if (oT == oSpan.fT && this == oSpan.fOther) { 2667 iSpan.fOtherIndex = o; 2668 break; 2669 } 2670 } 2671 } 2672 } 2673 2674 // OPTIMIZATION: uses tail recursion. Unwise? 2675 Span* innerChaseDone(int index, int step, int winding) { 2676 int end = nextExactSpan(index, step); 2677 SkASSERT(end >= 0); 2678 if (multipleSpans(end)) { 2679 return &fTs[end]; 2680 } 2681 const Span& endSpan = fTs[end]; 2682 Segment* other = endSpan.fOther; 2683 index = endSpan.fOtherIndex; 2684 int otherEnd = other->nextExactSpan(index, step); 2685 Span* last = other->innerChaseDone(index, step, winding); 2686 other->markDone(SkMin32(index, otherEnd), winding); 2687 return last; 2688 } 2689 2690 Span* innerChaseWinding(int index, int step, int winding) { 2691 int end = nextExactSpan(index, step); 2692 SkASSERT(end >= 0); 2693 if (multipleSpans(end)) { 2694 return &fTs[end]; 2695 } 2696 const Span& endSpan = fTs[end]; 2697 Segment* other = endSpan.fOther; 2698 index = endSpan.fOtherIndex; 2699 int otherEnd = other->nextExactSpan(index, step); 2700 int min = SkMin32(index, otherEnd); 2701 if (other->fTs[min].fWindSum != SK_MinS32) { 2702 SkASSERT(other->fTs[min].fWindSum == winding); 2703 return NULL; 2704 } 2705 Span* last = other->innerChaseWinding(index, step, winding); 2706 other->markWinding(min, winding); 2707 return last; 2708 } 2709 2710 void init(const SkPoint pts[], SkPath::Verb verb, bool operand) { 2711 fDoneSpans = 0; 2712 fOperand = operand; 2713 fPts = pts; 2714 fVerb = verb; 2715 } 2716 2717 bool intersected() const { 2718 return fTs.count() > 0; 2719 } 2720 2721 bool isConnected(int startIndex, int endIndex) const { 2722 return fTs[startIndex].fWindSum != SK_MinS32 2723 || fTs[endIndex].fWindSum != SK_MinS32; 2724 } 2725 2726 bool isHorizontal() const { 2727 return fBounds.fTop == fBounds.fBottom; 2728 } 2729 2730 bool isLinear(int start, int end) const { 2731 if (fVerb == SkPath::kLine_Verb) { 2732 return true; 2733 } 2734 if (fVerb == SkPath::kQuad_Verb) { 2735 SkPoint qPart[3]; 2736 QuadSubDivide(fPts, fTs[start].fT, fTs[end].fT, qPart); 2737 return QuadIsLinear(qPart); 2738 } else { 2739 SkASSERT(fVerb == SkPath::kCubic_Verb); 2740 SkPoint cPart[4]; 2741 CubicSubDivide(fPts, fTs[start].fT, fTs[end].fT, cPart); 2742 return CubicIsLinear(cPart); 2743 } 2744 } 2745 2746 // OPTIMIZE: successive calls could start were the last leaves off 2747 // or calls could specialize to walk forwards or backwards 2748 bool isMissing(double startT) const { 2749 size_t tCount = fTs.count(); 2750 for (size_t index = 0; index < tCount; ++index) { 2751 if (approximately_zero(startT - fTs[index].fT)) { 2752 return false; 2753 } 2754 } 2755 return true; 2756 } 2757 2758 bool isSimple(int end) const { 2759 int count = fTs.count(); 2760 if (count == 2) { 2761 return true; 2762 } 2763 double t = fTs[end].fT; 2764 if (approximately_less_than_zero(t)) { 2765 return !approximately_less_than_zero(fTs[1].fT); 2766 } 2767 if (approximately_greater_than_one(t)) { 2768 return !approximately_greater_than_one(fTs[count - 2].fT); 2769 } 2770 return false; 2771 } 2772 2773 bool isVertical() const { 2774 return fBounds.fLeft == fBounds.fRight; 2775 } 2776 2777 SkScalar leftMost(int start, int end) const { 2778 return (*SegmentLeftMost[fVerb])(fPts, fTs[start].fT, fTs[end].fT); 2779 } 2780 2781 // this span is excluded by the winding rule -- chase the ends 2782 // as long as they are unambiguous to mark connections as done 2783 // and give them the same winding value 2784 Span* markAndChaseDone(const Angle* angle, int winding) { 2785 int index = angle->start(); 2786 int endIndex = angle->end(); 2787 int step = SkSign32(endIndex - index); 2788 Span* last = innerChaseDone(index, step, winding); 2789 markDone(SkMin32(index, endIndex), winding); 2790 return last; 2791 } 2792 2793 Span* markAndChaseWinding(const Angle* angle, int winding) { 2794 int index = angle->start(); 2795 int endIndex = angle->end(); 2796 int min = SkMin32(index, endIndex); 2797 int step = SkSign32(endIndex - index); 2798 Span* last = innerChaseWinding(index, step, winding); 2799 markWinding(min, winding); 2800 return last; 2801 } 2802 2803 // FIXME: this should also mark spans with equal (x,y) 2804 // This may be called when the segment is already marked done. While this 2805 // wastes time, it shouldn't do any more than spin through the T spans. 2806 // OPTIMIZATION: abort on first done found (assuming that this code is 2807 // always called to mark segments done). 2808 void markDone(int index, int winding) { 2809 // SkASSERT(!done()); 2810 SkASSERT(winding); 2811 double referenceT = fTs[index].fT; 2812 int lesser = index; 2813 #if PRECISE_T_SORT 2814 while (--lesser >= 0 && precisely_negative(referenceT - fTs[lesser].fT)) { 2815 markOneDone(__FUNCTION__, lesser, winding); 2816 } 2817 do { 2818 markOneDone(__FUNCTION__, index, winding); 2819 } while (++index < fTs.count() && precisely_negative(fTs[index].fT - referenceT)); 2820 #else 2821 while (--lesser >= 0 && approximately_negative(referenceT - fTs[lesser].fT)) { 2822 markOneDone(__FUNCTION__, lesser, winding); 2823 } 2824 do { 2825 markOneDone(__FUNCTION__, index, winding); 2826 } while (++index < fTs.count() && approximately_negative(fTs[index].fT - referenceT)); 2827 #endif 2828 } 2829 2830 void markOneDone(const char* funName, int tIndex, int winding) { 2831 Span* span = markOneWinding(funName, tIndex, winding); 2832 if (!span) { 2833 return; 2834 } 2835 span->fDone = true; 2836 fDoneSpans++; 2837 } 2838 2839 Span* markOneWinding(const char* funName, int tIndex, int winding) { 2840 Span& span = fTs[tIndex]; 2841 if (span.fDone) { 2842 return NULL; 2843 } 2844 #if DEBUG_MARK_DONE 2845 debugShowNewWinding(funName, span, winding); 2846 #endif 2847 SkASSERT(span.fWindSum == SK_MinS32 || span.fWindSum == winding); 2848 #ifdef SK_DEBUG 2849 SkASSERT(abs(winding) <= gDebugMaxWindSum); 2850 #endif 2851 span.fWindSum = winding; 2852 return &span; 2853 } 2854 2855 // note that just because a span has one end that is unsortable, that's 2856 // not enough to mark it done. The other end may be sortable, allowing the 2857 // span to be added. 2858 void markUnsortable(int start, int end) { 2859 Span* span = &fTs[start]; 2860 if (start < end) { 2861 span->fUnsortableStart = true; 2862 } else { 2863 --span; 2864 span->fUnsortableEnd = true; 2865 } 2866 if (!span->fUnsortableStart || !span->fUnsortableEnd || span->fDone) { 2867 return; 2868 } 2869 span->fDone = true; 2870 fDoneSpans++; 2871 } 2872 2873 void markWinding(int index, int winding) { 2874 // SkASSERT(!done()); 2875 SkASSERT(winding); 2876 double referenceT = fTs[index].fT; 2877 int lesser = index; 2878 #if PRECISE_T_SORT 2879 while (--lesser >= 0 && precisely_negative(referenceT - fTs[lesser].fT)) { 2880 markOneWinding(__FUNCTION__, lesser, winding); 2881 } 2882 do { 2883 markOneWinding(__FUNCTION__, index, winding); 2884 } while (++index < fTs.count() && precisely_negative(fTs[index].fT - referenceT)); 2885 #else 2886 while (--lesser >= 0 && approximately_negative(referenceT - fTs[lesser].fT)) { 2887 markOneWinding(__FUNCTION__, lesser, winding); 2888 } 2889 do { 2890 markOneWinding(__FUNCTION__, index, winding); 2891 } while (++index < fTs.count() && approximately_negative(fTs[index].fT - referenceT)); 2892 #endif 2893 } 2894 2895 void matchWindingValue(int tIndex, double t, bool borrowWind) { 2896 int nextDoorWind = SK_MaxS32; 2897 if (tIndex > 0) { 2898 const Span& below = fTs[tIndex - 1]; 2899 if (approximately_negative(t - below.fT)) { 2900 nextDoorWind = below.fWindValue; 2901 } 2902 } 2903 if (nextDoorWind == SK_MaxS32 && tIndex + 1 < fTs.count()) { 2904 const Span& above = fTs[tIndex + 1]; 2905 if (approximately_negative(above.fT - t)) { 2906 nextDoorWind = above.fWindValue; 2907 } 2908 } 2909 if (nextDoorWind == SK_MaxS32 && borrowWind && tIndex > 0 && t < 1) { 2910 const Span& below = fTs[tIndex - 1]; 2911 nextDoorWind = below.fWindValue; 2912 } 2913 if (nextDoorWind != SK_MaxS32) { 2914 Span& newSpan = fTs[tIndex]; 2915 newSpan.fWindValue = nextDoorWind; 2916 if (!nextDoorWind && !newSpan.fDone) { 2917 newSpan.fDone = true; 2918 ++fDoneSpans; 2919 } 2920 } 2921 } 2922 2923 // return span if when chasing, two or more radiating spans are not done 2924 // OPTIMIZATION: ? multiple spans is detected when there is only one valid 2925 // candidate and the remaining spans have windValue == 0 (canceled by 2926 // coincidence). The coincident edges could either be removed altogether, 2927 // or this code could be more complicated in detecting this case. Worth it? 2928 bool multipleSpans(int end) const { 2929 return end > 0 && end < fTs.count() - 1; 2930 } 2931 2932 // This has callers for two different situations: one establishes the end 2933 // of the current span, and one establishes the beginning of the next span 2934 // (thus the name). When this is looking for the end of the current span, 2935 // coincidence is found when the beginning Ts contain -step and the end 2936 // contains step. When it is looking for the beginning of the next, the 2937 // first Ts found can be ignored and the last Ts should contain -step. 2938 // OPTIMIZATION: probably should split into two functions 2939 int nextSpan(int from, int step) const { 2940 const Span& fromSpan = fTs[from]; 2941 int count = fTs.count(); 2942 int to = from; 2943 while (step > 0 ? ++to < count : --to >= 0) { 2944 const Span& span = fTs[to]; 2945 if (approximately_zero(span.fT - fromSpan.fT)) { 2946 continue; 2947 } 2948 return to; 2949 } 2950 return -1; 2951 } 2952 2953#if PRECISE_T_SORT 2954 // FIXME 2955 // this returns at any difference in T, vs. a preset minimum. It may be 2956 // that all callers to nextSpan should use this instead. 2957 // OPTIMIZATION splitting this into separate loops for up/down steps 2958 // would allow using precisely_negative instead of precisely_zero 2959 int nextExactSpan(int from, int step) const { 2960 const Span& fromSpan = fTs[from]; 2961 int count = fTs.count(); 2962 int to = from; 2963 while (step > 0 ? ++to < count : --to >= 0) { 2964 const Span& span = fTs[to]; 2965 if (precisely_zero(span.fT - fromSpan.fT)) { 2966 continue; 2967 } 2968 return to; 2969 } 2970 return -1; 2971 } 2972#endif 2973 2974 bool operand() const { 2975 return fOperand; 2976 } 2977 2978 int oppSign(int startIndex, int endIndex) const { 2979 int result = startIndex < endIndex ? -fTs[startIndex].fWindValueOpp : 2980 fTs[endIndex].fWindValueOpp; 2981#if DEBUG_WIND_BUMP 2982 SkDebugf("%s spanSign=%d\n", __FUNCTION__, result); 2983#endif 2984 return result; 2985 } 2986 2987 const SkPoint* pts() const { 2988 return fPts; 2989 } 2990 2991 void reset() { 2992 init(NULL, (SkPath::Verb) -1, false); 2993 fBounds.set(SK_ScalarMax, SK_ScalarMax, SK_ScalarMax, SK_ScalarMax); 2994 fTs.reset(); 2995 } 2996 2997 // This marks all spans unsortable so that this info is available for early 2998 // exclusion in find top and others. This could be optimized to only mark 2999 // adjacent spans that unsortable. However, this makes it difficult to later 3000 // determine starting points for edge detection in find top and the like. 3001 static bool SortAngles(SkTDArray<Angle>& angles, SkTDArray<Angle*>& angleList) { 3002 bool sortable = true; 3003 int angleCount = angles.count(); 3004 int angleIndex; 3005 angleList.setReserve(angleCount); 3006 for (angleIndex = 0; angleIndex < angleCount; ++angleIndex) { 3007 Angle& angle = angles[angleIndex]; 3008 *angleList.append() = ∠ 3009 sortable &= !angle.unsortable(); 3010 } 3011 if (sortable) { 3012 QSort<Angle>(angleList.begin(), angleList.end() - 1); 3013 for (angleIndex = 0; angleIndex < angleCount; ++angleIndex) { 3014 if (angles[angleIndex].unsortable()) { 3015 sortable = false; 3016 break; 3017 } 3018 } 3019 } 3020 if (!sortable) { 3021 for (angleIndex = 0; angleIndex < angleCount; ++angleIndex) { 3022 Angle& angle = angles[angleIndex]; 3023 angle.segment()->markUnsortable(angle.start(), angle.end()); 3024 } 3025 } 3026 return sortable; 3027 } 3028 3029 // OPTIMIZATION: mark as debugging only if used solely by tests 3030 const Span& span(int tIndex) const { 3031 return fTs[tIndex]; 3032 } 3033 3034 int spanSign(const Angle* angle) const { 3035 SkASSERT(angle->segment() == this); 3036 return spanSign(angle->start(), angle->end()); 3037 } 3038 3039 int spanSign(int startIndex, int endIndex) const { 3040 int result = startIndex < endIndex ? -fTs[startIndex].fWindValue : 3041 fTs[endIndex].fWindValue; 3042#if DEBUG_WIND_BUMP 3043 SkDebugf("%s spanSign=%d\n", __FUNCTION__, result); 3044#endif 3045 return result; 3046 } 3047 3048 // OPTIMIZATION: mark as debugging only if used solely by tests 3049 double t(int tIndex) const { 3050 return fTs[tIndex].fT; 3051 } 3052 3053 bool tiny(const Angle& angle) const { 3054 int start = angle.start(); 3055 int end = angle.end(); 3056 const Span& mSpan = fTs[SkMin32(start, end)]; 3057 return mSpan.fTiny; 3058 } 3059 3060 static void TrackOutside(SkTDArray<double>& outsideTs, double end, 3061 double start) { 3062 int outCount = outsideTs.count(); 3063 if (outCount == 0 || !approximately_negative(end - outsideTs[outCount - 2])) { 3064 *outsideTs.append() = end; 3065 *outsideTs.append() = start; 3066 } 3067 } 3068 3069 void undoneSpan(int& start, int& end) { 3070 size_t tCount = fTs.count(); 3071 size_t index; 3072 for (index = 0; index < tCount; ++index) { 3073 if (!fTs[index].fDone) { 3074 break; 3075 } 3076 } 3077 SkASSERT(index < tCount - 1); 3078 start = index; 3079 double startT = fTs[index].fT; 3080 while (approximately_negative(fTs[++index].fT - startT)) 3081 SkASSERT(index < tCount); 3082 SkASSERT(index < tCount); 3083 end = index; 3084 } 3085 3086 bool unsortable(int index) const { 3087 return fTs[index].fUnsortableStart || fTs[index].fUnsortableEnd; 3088 } 3089 3090 void updatePts(const SkPoint pts[]) { 3091 fPts = pts; 3092 } 3093 3094 SkPath::Verb verb() const { 3095 return fVerb; 3096 } 3097 3098 int windSum(int tIndex) const { 3099 return fTs[tIndex].fWindSum; 3100 } 3101 3102 int windSum(const Angle* angle) const { 3103 int start = angle->start(); 3104 int end = angle->end(); 3105 int index = SkMin32(start, end); 3106 return windSum(index); 3107 } 3108 3109 int windValue(int tIndex) const { 3110 return fTs[tIndex].fWindValue; 3111 } 3112 3113 int windValue(const Angle* angle) const { 3114 int start = angle->start(); 3115 int end = angle->end(); 3116 int index = SkMin32(start, end); 3117 return windValue(index); 3118 } 3119 3120 SkScalar xAtT(const Span* span) const { 3121 return xyAtT(span).fX; 3122 } 3123 3124 const SkPoint& xyAtT(int index) const { 3125 return xyAtT(&fTs[index]); 3126 } 3127 3128 const SkPoint& xyAtT(const Span* span) const { 3129 if (SkScalarIsNaN(span->fPt.fX)) { 3130 if (span->fT == 0) { 3131 span->fPt = fPts[0]; 3132 } else if (span->fT == 1) { 3133 span->fPt = fPts[fVerb]; 3134 } else { 3135 (*SegmentXYAtT[fVerb])(fPts, span->fT, &span->fPt); 3136 } 3137 } 3138 return span->fPt; 3139 } 3140 3141 SkScalar yAtT(int index) const { 3142 return yAtT(&fTs[index]); 3143 } 3144 3145 SkScalar yAtT(const Span* span) const { 3146 return xyAtT(span).fY; 3147 } 3148 3149#if DEBUG_DUMP 3150 void dump() const { 3151 const char className[] = "Segment"; 3152 const int tab = 4; 3153 for (int i = 0; i < fTs.count(); ++i) { 3154 SkPoint out; 3155 (*SegmentXYAtT[fVerb])(fPts, t(i), &out); 3156 SkDebugf("%*s [%d] %s.fTs[%d]=%1.9g (%1.9g,%1.9g) other=%d" 3157 " otherT=%1.9g windSum=%d\n", 3158 tab + sizeof(className), className, fID, 3159 kLVerbStr[fVerb], i, fTs[i].fT, out.fX, out.fY, 3160 fTs[i].fOther->fID, fTs[i].fOtherT, fTs[i].fWindSum); 3161 } 3162 SkDebugf("%*s [%d] fBounds=(l:%1.9g, t:%1.9g r:%1.9g, b:%1.9g)", 3163 tab + sizeof(className), className, fID, 3164 fBounds.fLeft, fBounds.fTop, fBounds.fRight, fBounds.fBottom); 3165 } 3166#endif 3167 3168#if DEBUG_CONCIDENT 3169 // assert if pair has not already been added 3170 void debugAddTPair(double t, const Segment& other, double otherT) const { 3171 for (int i = 0; i < fTs.count(); ++i) { 3172 if (fTs[i].fT == t && fTs[i].fOther == &other && fTs[i].fOtherT == otherT) { 3173 return; 3174 } 3175 } 3176 SkASSERT(0); 3177 } 3178#endif 3179 3180#if DEBUG_DUMP 3181 int debugID() const { 3182 return fID; 3183 } 3184#endif 3185 3186#if DEBUG_WINDING 3187 void debugShowSums() const { 3188 SkDebugf("%s id=%d (%1.9g,%1.9g %1.9g,%1.9g)", __FUNCTION__, fID, 3189 fPts[0].fX, fPts[0].fY, fPts[fVerb].fX, fPts[fVerb].fY); 3190 for (int i = 0; i < fTs.count(); ++i) { 3191 const Span& span = fTs[i]; 3192 SkDebugf(" [t=%1.3g %1.9g,%1.9g w=", span.fT, xAtT(&span), yAtT(&span)); 3193 if (span.fWindSum == SK_MinS32) { 3194 SkDebugf("?"); 3195 } else { 3196 SkDebugf("%d", span.fWindSum); 3197 } 3198 SkDebugf("]"); 3199 } 3200 SkDebugf("\n"); 3201 } 3202#endif 3203 3204#if DEBUG_CONCIDENT 3205 void debugShowTs() const { 3206 SkDebugf("%s id=%d", __FUNCTION__, fID); 3207 for (int i = 0; i < fTs.count(); ++i) { 3208 SkDebugf(" [o=%d t=%1.3g %1.9g,%1.9g w=%d]", fTs[i].fOther->fID, 3209 fTs[i].fT, xAtT(&fTs[i]), yAtT(&fTs[i]), fTs[i].fWindValue); 3210 } 3211 SkDebugf("\n"); 3212 } 3213#endif 3214 3215#if DEBUG_ACTIVE_SPANS 3216 void debugShowActiveSpans() const { 3217 if (done()) { 3218 return; 3219 } 3220 for (int i = 0; i < fTs.count(); ++i) { 3221 if (fTs[i].fDone) { 3222 continue; 3223 } 3224 SkDebugf("%s id=%d", __FUNCTION__, fID); 3225 SkDebugf(" (%1.9g,%1.9g", fPts[0].fX, fPts[0].fY); 3226 for (int vIndex = 1; vIndex <= fVerb; ++vIndex) { 3227 SkDebugf(" %1.9g,%1.9g", fPts[vIndex].fX, fPts[vIndex].fY); 3228 } 3229 const Span* span = &fTs[i]; 3230 SkDebugf(") t=%1.9g (%1.9g,%1.9g)", fTs[i].fT, 3231 xAtT(span), yAtT(span)); 3232 const Segment* other = fTs[i].fOther; 3233 SkDebugf(" other=%d otherT=%1.9g otherIndex=%d windSum=", 3234 other->fID, fTs[i].fOtherT, fTs[i].fOtherIndex); 3235 if (fTs[i].fWindSum == SK_MinS32) { 3236 SkDebugf("?"); 3237 } else { 3238 SkDebugf("%d", fTs[i].fWindSum); 3239 } 3240 SkDebugf(" windValue=%d\n", fTs[i].fWindValue); 3241 } 3242 } 3243 3244 // This isn't useful yet -- but leaving it in for now in case i think of something 3245 // to use it for 3246 void validateActiveSpans() const { 3247 if (done()) { 3248 return; 3249 } 3250 int tCount = fTs.count(); 3251 for (int index = 0; index < tCount; ++index) { 3252 if (fTs[index].fDone) { 3253 continue; 3254 } 3255 // count number of connections which are not done 3256 int first = index; 3257 double baseT = fTs[index].fT; 3258 while (first > 0 && approximately_equal(fTs[first - 1].fT, baseT)) { 3259 --first; 3260 } 3261 int last = index; 3262 while (last < tCount - 1 && approximately_equal(fTs[last + 1].fT, baseT)) { 3263 ++last; 3264 } 3265 int connections = 0; 3266 connections += first > 0 && !fTs[first - 1].fDone; 3267 for (int test = first; test <= last; ++test) { 3268 connections += !fTs[test].fDone; 3269 const Segment* other = fTs[test].fOther; 3270 int oIndex = fTs[test].fOtherIndex; 3271 connections += !other->fTs[oIndex].fDone; 3272 connections += oIndex > 0 && !other->fTs[oIndex - 1].fDone; 3273 } 3274 // SkASSERT(!(connections & 1)); 3275 } 3276 } 3277#endif 3278 3279#if DEBUG_MARK_DONE 3280 void debugShowNewWinding(const char* fun, const Span& span, int winding) { 3281 const SkPoint& pt = xyAtT(&span); 3282 SkDebugf("%s id=%d", fun, fID); 3283 SkDebugf(" (%1.9g,%1.9g", fPts[0].fX, fPts[0].fY); 3284 for (int vIndex = 1; vIndex <= fVerb; ++vIndex) { 3285 SkDebugf(" %1.9g,%1.9g", fPts[vIndex].fX, fPts[vIndex].fY); 3286 } 3287 SkASSERT(&span == &span.fOther->fTs[span.fOtherIndex].fOther-> 3288 fTs[span.fOther->fTs[span.fOtherIndex].fOtherIndex]); 3289 SkDebugf(") t=%1.9g [%d] (%1.9g,%1.9g) newWindSum=%d windSum=", 3290 span.fT, span.fOther->fTs[span.fOtherIndex].fOtherIndex, pt.fX, pt.fY, winding); 3291 if (span.fWindSum == SK_MinS32) { 3292 SkDebugf("?"); 3293 } else { 3294 SkDebugf("%d", span.fWindSum); 3295 } 3296 SkDebugf(" windValue=%d\n", span.fWindValue); 3297 } 3298#endif 3299 3300#if DEBUG_SORT 3301 void debugShowSort(const char* fun, const SkTDArray<Angle*>& angles, int first, 3302 const int contourWinding) const { 3303 SkASSERT(angles[first]->segment() == this); 3304 SkASSERT(angles.count() > 1); 3305 int lastSum = contourWinding; 3306 int windSum = lastSum - spanSign(angles[first]); 3307 SkDebugf("%s %s contourWinding=%d sign=%d\n", fun, __FUNCTION__, 3308 contourWinding, spanSign(angles[first])); 3309 int index = first; 3310 bool firstTime = true; 3311 do { 3312 const Angle& angle = *angles[index]; 3313 const Segment& segment = *angle.segment(); 3314 int start = angle.start(); 3315 int end = angle.end(); 3316 const Span& sSpan = segment.fTs[start]; 3317 const Span& eSpan = segment.fTs[end]; 3318 const Span& mSpan = segment.fTs[SkMin32(start, end)]; 3319 if (!firstTime) { 3320 lastSum = windSum; 3321 windSum -= segment.spanSign(&angle); 3322 } 3323 SkDebugf("%s [%d] %sid=%d %s start=%d (%1.9g,%,1.9g) end=%d (%1.9g,%,1.9g)" 3324 " sign=%d windValue=%d windSum=", 3325 __FUNCTION__, index, angle.unsortable() ? "*** UNSORTABLE *** " : "", 3326 segment.fID, kLVerbStr[segment.fVerb], 3327 start, segment.xAtT(&sSpan), segment.yAtT(&sSpan), end, 3328 segment.xAtT(&eSpan), segment.yAtT(&eSpan), angle.sign(), 3329 mSpan.fWindValue); 3330 if (mSpan.fWindSum == SK_MinS32) { 3331 SkDebugf("?"); 3332 } else { 3333 SkDebugf("%d", mSpan.fWindSum); 3334 } 3335 SkDebugf(" winding: %d->%d (max=%d) done=%d tiny=%d\n", lastSum, windSum, 3336 useInnerWinding(lastSum, windSum) ? windSum : lastSum, 3337 mSpan.fDone, mSpan.fTiny); 3338#if false && DEBUG_ANGLE 3339 angle.debugShow(segment.xyAtT(&sSpan)); 3340#endif 3341 ++index; 3342 if (index == angles.count()) { 3343 index = 0; 3344 } 3345 if (firstTime) { 3346 firstTime = false; 3347 } 3348 } while (index != first); 3349 } 3350#endif 3351 3352#if DEBUG_WINDING 3353 bool debugVerifyWinding(int start, int end, int winding) const { 3354 const Span& span = fTs[SkMin32(start, end)]; 3355 int spanWinding = span.fWindSum; 3356 if (spanWinding == SK_MinS32) { 3357 return true; 3358 } 3359 int spanSign = SkSign32(start - end); 3360 int signedVal = spanSign * span.fWindValue; 3361 if (signedVal < 0) { 3362 spanWinding -= signedVal; 3363 } 3364 return span.fWindSum == winding; 3365 } 3366#endif 3367 3368private: 3369 const SkPoint* fPts; 3370 SkPath::Verb fVerb; 3371 Bounds fBounds; 3372 SkTDArray<Span> fTs; // two or more (always includes t=0 t=1) 3373 int fDoneSpans; // quick check that segment is finished 3374 bool fOperand; 3375#if DEBUG_DUMP 3376 int fID; 3377#endif 3378}; 3379 3380class Contour; 3381 3382struct Coincidence { 3383 Contour* fContours[2]; 3384 int fSegments[2]; 3385 double fTs[2][2]; 3386 bool fXor; 3387}; 3388 3389class Contour { 3390public: 3391 Contour() { 3392 reset(); 3393#if DEBUG_DUMP 3394 fID = ++gContourID; 3395#endif 3396 } 3397 3398 bool operator<(const Contour& rh) const { 3399 return fBounds.fTop == rh.fBounds.fTop 3400 ? fBounds.fLeft < rh.fBounds.fLeft 3401 : fBounds.fTop < rh.fBounds.fTop; 3402 } 3403 3404 void addCoincident(int index, Contour* other, int otherIndex, 3405 const Intersections& ts, bool swap) { 3406 Coincidence& coincidence = *fCoincidences.append(); 3407 coincidence.fContours[0] = this; 3408 coincidence.fContours[1] = other; 3409 coincidence.fSegments[0] = index; 3410 coincidence.fSegments[1] = otherIndex; 3411 if (fSegments[index].verb() == SkPath::kLine_Verb && 3412 other->fSegments[otherIndex].verb() == SkPath::kLine_Verb) { 3413 // FIXME: coincident lines use legacy Ts instead of coincident Ts 3414 coincidence.fTs[swap][0] = ts.fT[0][0]; 3415 coincidence.fTs[swap][1] = ts.fT[0][1]; 3416 coincidence.fTs[!swap][0] = ts.fT[1][0]; 3417 coincidence.fTs[!swap][1] = ts.fT[1][1]; 3418 } else if (fSegments[index].verb() == SkPath::kQuad_Verb && 3419 other->fSegments[otherIndex].verb() == SkPath::kQuad_Verb) { 3420 coincidence.fTs[swap][0] = ts.fCoincidentT[0][0]; 3421 coincidence.fTs[swap][1] = ts.fCoincidentT[0][1]; 3422 coincidence.fTs[!swap][0] = ts.fCoincidentT[1][0]; 3423 coincidence.fTs[!swap][1] = ts.fCoincidentT[1][1]; 3424 } 3425 coincidence.fXor = fOperand == other->fOperand ? fXor : true; 3426 } 3427 3428 void addCross(const Contour* crosser) { 3429#ifdef DEBUG_CROSS 3430 for (int index = 0; index < fCrosses.count(); ++index) { 3431 SkASSERT(fCrosses[index] != crosser); 3432 } 3433#endif 3434 *fCrosses.append() = crosser; 3435 } 3436 3437 void addCubic(const SkPoint pts[4]) { 3438 fSegments.push_back().addCubic(pts, fOperand); 3439 fContainsCurves = true; 3440 } 3441 3442 int addLine(const SkPoint pts[2]) { 3443 fSegments.push_back().addLine(pts, fOperand); 3444 return fSegments.count(); 3445 } 3446 3447 void addOtherT(int segIndex, int tIndex, double otherT, int otherIndex) { 3448 fSegments[segIndex].addOtherT(tIndex, otherT, otherIndex); 3449 } 3450 3451 int addQuad(const SkPoint pts[3]) { 3452 fSegments.push_back().addQuad(pts, fOperand); 3453 fContainsCurves = true; 3454 return fSegments.count(); 3455 } 3456 3457 int addT(int segIndex, double newT, Contour* other, int otherIndex) { 3458 containsIntercepts(); 3459 return fSegments[segIndex].addT(newT, &other->fSegments[otherIndex]); 3460 } 3461 3462 const Bounds& bounds() const { 3463 return fBounds; 3464 } 3465 3466 void collapseTriangles() { 3467 int segmentCount = fSegments.count(); 3468 for (int sIndex = 0; sIndex < segmentCount; ++sIndex) { 3469 fSegments[sIndex].collapseTriangles(fXor); 3470 } 3471 } 3472 3473 void complete() { 3474 setBounds(); 3475 fContainsIntercepts = false; 3476 } 3477 3478 void containsIntercepts() { 3479 fContainsIntercepts = true; 3480 } 3481 3482 const Segment* crossedSegment(const SkPoint& basePt, SkScalar& bestY, 3483 int &tIndex, double& hitT) { 3484 int segmentCount = fSegments.count(); 3485 const Segment* bestSegment = NULL; 3486 for (int test = 0; test < segmentCount; ++test) { 3487 Segment* testSegment = &fSegments[test]; 3488 const SkRect& bounds = testSegment->bounds(); 3489 if (bounds.fBottom <= bestY) { 3490 continue; 3491 } 3492 if (bounds.fTop >= basePt.fY) { 3493 continue; 3494 } 3495 if (bounds.fLeft > basePt.fX) { 3496 continue; 3497 } 3498 if (bounds.fRight < basePt.fX) { 3499 continue; 3500 } 3501 if (bounds.fLeft == bounds.fRight) { 3502 continue; 3503 } 3504 #if 0 3505 bool leftHalf = bounds.fLeft == basePt.fX; 3506 bool rightHalf = bounds.fRight == basePt.fX; 3507 if ((leftHalf || rightHalf) && !testSegment->crossedSpanHalves( 3508 basePt, leftHalf, rightHalf)) { 3509 continue; 3510 } 3511 #endif 3512 double testHitT; 3513 int testT = testSegment->crossedSpan(basePt, bestY, testHitT); 3514 if (testT >= 0) { 3515 bestSegment = testSegment; 3516 tIndex = testT; 3517 hitT = testHitT; 3518 } 3519 } 3520 return bestSegment; 3521 } 3522 3523 bool crosses(const Contour* crosser) const { 3524 for (int index = 0; index < fCrosses.count(); ++index) { 3525 if (fCrosses[index] == crosser) { 3526 return true; 3527 } 3528 } 3529 return false; 3530 } 3531 3532 const SkPoint& end() const { 3533 const Segment& segment = fSegments.back(); 3534 return segment.pts()[segment.verb()]; 3535 } 3536 3537 void findTooCloseToCall() { 3538 int segmentCount = fSegments.count(); 3539 for (int sIndex = 0; sIndex < segmentCount; ++sIndex) { 3540 fSegments[sIndex].findTooCloseToCall(fXor); 3541 } 3542 } 3543 3544 void fixOtherTIndex() { 3545 int segmentCount = fSegments.count(); 3546 for (int sIndex = 0; sIndex < segmentCount; ++sIndex) { 3547 fSegments[sIndex].fixOtherTIndex(); 3548 } 3549 } 3550 3551 void reset() { 3552 fSegments.reset(); 3553 fBounds.set(SK_ScalarMax, SK_ScalarMax, SK_ScalarMax, SK_ScalarMax); 3554 fContainsCurves = fContainsIntercepts = false; 3555 } 3556 3557 // FIXME: for binary ops, need to keep both ops winding contributions separately 3558 // in edge array 3559 void resolveCoincidence() { 3560 int count = fCoincidences.count(); 3561 for (int index = 0; index < count; ++index) { 3562 Coincidence& coincidence = fCoincidences[index]; 3563 Contour* thisContour = coincidence.fContours[0]; 3564 Contour* otherContour = coincidence.fContours[1]; 3565 int thisIndex = coincidence.fSegments[0]; 3566 int otherIndex = coincidence.fSegments[1]; 3567 Segment& thisOne = thisContour->fSegments[thisIndex]; 3568 Segment& other = otherContour->fSegments[otherIndex]; 3569 #if DEBUG_CONCIDENT 3570 thisOne.debugShowTs(); 3571 other.debugShowTs(); 3572 #endif 3573 double startT = coincidence.fTs[0][0]; 3574 double endT = coincidence.fTs[0][1]; 3575 bool opposite = false; 3576 if (startT > endT) { 3577 SkTSwap<double>(startT, endT); 3578 opposite ^= true; 3579 } 3580 SkASSERT(!approximately_negative(endT - startT)); 3581 double oStartT = coincidence.fTs[1][0]; 3582 double oEndT = coincidence.fTs[1][1]; 3583 if (oStartT > oEndT) { 3584 SkTSwap<double>(oStartT, oEndT); 3585 opposite ^= true; 3586 } 3587 SkASSERT(!approximately_negative(oEndT - oStartT)); 3588 if (opposite) { 3589 // make sure startT and endT have t entries 3590 SkASSERT(opposite); 3591 if (startT > 0 || oEndT < 1 3592 || thisOne.isMissing(startT) || other.isMissing(oEndT)) { 3593 thisOne.addTPair(startT, other, oEndT, true); 3594 } 3595 if (oStartT > 0 || endT < 1 3596 || thisOne.isMissing(endT) || other.isMissing(oStartT)) { 3597 other.addTPair(oStartT, thisOne, endT, true); 3598 } 3599 thisOne.addTCancel(startT, endT, other, oStartT, oEndT); 3600 } else { 3601 if (startT > 0 || oStartT > 0 3602 || thisOne.isMissing(startT) || other.isMissing(oStartT)) { 3603 thisOne.addTPair(startT, other, oStartT, true); 3604 } 3605 if (endT < 1 || oEndT < 1 3606 || thisOne.isMissing(endT) || other.isMissing(oEndT)) { 3607 other.addTPair(oEndT, thisOne, endT, true); 3608 } 3609 thisOne.addTCoincident(coincidence.fXor, startT, endT, other, oStartT, oEndT); 3610 } 3611 #if DEBUG_CONCIDENT 3612 thisOne.debugShowTs(); 3613 other.debugShowTs(); 3614 #endif 3615 } 3616 } 3617 3618 const SkTArray<Segment>& segments() { 3619 return fSegments; 3620 } 3621 3622 void setOperand(bool isOp) { 3623 fOperand = isOp; 3624 } 3625 3626 void setXor(bool isXor) { 3627 fXor = isXor; 3628 } 3629 3630#if !SORTABLE_CONTOURS 3631 void sortSegments() { 3632 int segmentCount = fSegments.count(); 3633 fSortedSegments.setReserve(segmentCount); 3634 for (int test = 0; test < segmentCount; ++test) { 3635 *fSortedSegments.append() = &fSegments[test]; 3636 } 3637 QSort<Segment>(fSortedSegments.begin(), fSortedSegments.end() - 1); 3638 fFirstSorted = 0; 3639 } 3640#endif 3641 3642 const SkPoint& start() const { 3643 return fSegments.front().pts()[0]; 3644 } 3645 3646 void toPath(PathWrapper& path) const { 3647 int segmentCount = fSegments.count(); 3648 const SkPoint& pt = fSegments.front().pts()[0]; 3649 path.deferredMove(pt); 3650 for (int test = 0; test < segmentCount; ++test) { 3651 fSegments[test].addCurveTo(0, 1, path, true); 3652 } 3653 path.close(); 3654 } 3655 3656 void toPartialBackward(PathWrapper& path) const { 3657 int segmentCount = fSegments.count(); 3658 for (int test = segmentCount - 1; test >= 0; --test) { 3659 fSegments[test].addCurveTo(1, 0, path, true); 3660 } 3661 } 3662 3663 void toPartialForward(PathWrapper& path) const { 3664 int segmentCount = fSegments.count(); 3665 for (int test = 0; test < segmentCount; ++test) { 3666 fSegments[test].addCurveTo(0, 1, path, true); 3667 } 3668 } 3669 3670#if 0 // FIXME: obsolete, remove 3671 // OPTIMIZATION: feel pretty uneasy about this. It seems like once again 3672 // we need to sort and walk edges in y, but that on the surface opens the 3673 // same can of worms as before. But then, this is a rough sort based on 3674 // segments' top, and not a true sort, so it could be ameniable to regular 3675 // sorting instead of linear searching. Still feel like I'm missing something 3676 Segment* topSegment(SkScalar& bestY) { 3677 int segmentCount = fSegments.count(); 3678 SkASSERT(segmentCount > 0); 3679 int best = -1; 3680 Segment* bestSegment = NULL; 3681 while (++best < segmentCount) { 3682 Segment* testSegment = &fSegments[best]; 3683 if (testSegment->done()) { 3684 continue; 3685 } 3686 bestSegment = testSegment; 3687 break; 3688 } 3689 if (!bestSegment) { 3690 return NULL; 3691 } 3692 SkScalar bestTop = bestSegment->activeTop(); 3693 for (int test = best + 1; test < segmentCount; ++test) { 3694 Segment* testSegment = &fSegments[test]; 3695 if (testSegment->done()) { 3696 continue; 3697 } 3698 if (testSegment->bounds().fTop > bestTop) { 3699 continue; 3700 } 3701 SkScalar testTop = testSegment->activeTop(); 3702 if (bestTop > testTop) { 3703 bestTop = testTop; 3704 bestSegment = testSegment; 3705 } 3706 } 3707 bestY = bestTop; 3708 return bestSegment; 3709 } 3710#endif 3711 3712#if !SORTABLE_CONTOURS 3713 Segment* topSortableSegment(const SkPoint& topLeft, SkPoint& bestXY) { 3714 int segmentCount = fSortedSegments.count(); 3715 SkASSERT(segmentCount > 0); 3716 Segment* bestSegment = NULL; 3717 int sortedIndex = fFirstSorted; 3718 for ( ; sortedIndex < segmentCount; ++sortedIndex) { 3719 Segment* testSegment = fSortedSegments[sortedIndex]; 3720 if (testSegment->done()) { 3721 if (sortedIndex == fFirstSorted) { 3722 ++fFirstSorted; 3723 } 3724 continue; 3725 } 3726 SkPoint testXY; 3727 testSegment->activeLeftTop(testXY); 3728 if (testXY.fY < topLeft.fY) { 3729 continue; 3730 } 3731 if (testXY.fY == topLeft.fY && testXY.fX < topLeft.fX) { 3732 continue; 3733 } 3734 if (bestXY.fY < testXY.fY) { 3735 continue; 3736 } 3737 if (bestXY.fY == testXY.fY && bestXY.fX < testXY.fX) { 3738 continue; 3739 } 3740 bestSegment = testSegment; 3741 bestXY = testXY; 3742 } 3743 return bestSegment; 3744 } 3745#endif 3746 3747 Segment* undoneSegment(int& start, int& end) { 3748 int segmentCount = fSegments.count(); 3749 for (int test = 0; test < segmentCount; ++test) { 3750 Segment* testSegment = &fSegments[test]; 3751 if (testSegment->done()) { 3752 continue; 3753 } 3754 testSegment->undoneSpan(start, end); 3755 return testSegment; 3756 } 3757 return NULL; 3758 } 3759 3760 int updateSegment(int index, const SkPoint* pts) { 3761 Segment& segment = fSegments[index]; 3762 segment.updatePts(pts); 3763 return segment.verb() + 1; 3764 } 3765 3766#if DEBUG_TEST 3767 SkTArray<Segment>& debugSegments() { 3768 return fSegments; 3769 } 3770#endif 3771 3772#if DEBUG_DUMP 3773 void dump() { 3774 int i; 3775 const char className[] = "Contour"; 3776 const int tab = 4; 3777 SkDebugf("%s %p (contour=%d)\n", className, this, fID); 3778 for (i = 0; i < fSegments.count(); ++i) { 3779 SkDebugf("%*s.fSegments[%d]:\n", tab + sizeof(className), 3780 className, i); 3781 fSegments[i].dump(); 3782 } 3783 SkDebugf("%*s.fBounds=(l:%1.9g, t:%1.9g r:%1.9g, b:%1.9g)\n", 3784 tab + sizeof(className), className, 3785 fBounds.fLeft, fBounds.fTop, 3786 fBounds.fRight, fBounds.fBottom); 3787 SkDebugf("%*s.fContainsIntercepts=%d\n", tab + sizeof(className), 3788 className, fContainsIntercepts); 3789 SkDebugf("%*s.fContainsCurves=%d\n", tab + sizeof(className), 3790 className, fContainsCurves); 3791 } 3792#endif 3793 3794#if DEBUG_ACTIVE_SPANS 3795 void debugShowActiveSpans() { 3796 for (int index = 0; index < fSegments.count(); ++index) { 3797 fSegments[index].debugShowActiveSpans(); 3798 } 3799 } 3800 3801 void validateActiveSpans() { 3802 for (int index = 0; index < fSegments.count(); ++index) { 3803 fSegments[index].validateActiveSpans(); 3804 } 3805 } 3806#endif 3807 3808protected: 3809 void setBounds() { 3810 int count = fSegments.count(); 3811 if (count == 0) { 3812 SkDebugf("%s empty contour\n", __FUNCTION__); 3813 SkASSERT(0); 3814 // FIXME: delete empty contour? 3815 return; 3816 } 3817 fBounds = fSegments.front().bounds(); 3818 for (int index = 1; index < count; ++index) { 3819 fBounds.add(fSegments[index].bounds()); 3820 } 3821 } 3822 3823private: 3824 SkTArray<Segment> fSegments; 3825#if !SORTABLE_CONTOURS 3826 SkTDArray<Segment*> fSortedSegments; 3827 int fFirstSorted; 3828#endif 3829 SkTDArray<Coincidence> fCoincidences; 3830 SkTDArray<const Contour*> fCrosses; 3831 Bounds fBounds; 3832 bool fContainsIntercepts; 3833 bool fContainsCurves; 3834 bool fOperand; // true for the second argument to a binary operator 3835 bool fXor; 3836#if DEBUG_DUMP 3837 int fID; 3838#endif 3839}; 3840 3841class EdgeBuilder { 3842public: 3843 3844EdgeBuilder(const PathWrapper& path, SkTArray<Contour>& contours) 3845 : fPath(path.nativePath()) 3846 , fContours(contours) 3847{ 3848 init(); 3849} 3850 3851EdgeBuilder(const SkPath& path, SkTArray<Contour>& contours) 3852 : fPath(&path) 3853 , fContours(contours) 3854{ 3855 init(); 3856} 3857 3858void init() { 3859 fCurrentContour = NULL; 3860 fOperand = false; 3861 fXorMask = (fPath->getFillType() & 1) ? kEvenOdd_Mask : kWinding_Mask; 3862#if DEBUG_DUMP 3863 gContourID = 0; 3864 gSegmentID = 0; 3865#endif 3866 fSecondHalf = preFetch(); 3867} 3868 3869void addOperand(const SkPath& path) { 3870 fPath = &path; 3871 fXorMask = (fPath->getFillType() & 1) ? kEvenOdd_Mask : kWinding_Mask; 3872 preFetch(); 3873} 3874 3875void finish() { 3876 walk(); 3877 complete(); 3878 if (fCurrentContour && !fCurrentContour->segments().count()) { 3879 fContours.pop_back(); 3880 } 3881 // correct pointers in contours since fReducePts may have moved as it grew 3882 int cIndex = 0; 3883 int extraCount = fExtra.count(); 3884 SkASSERT(extraCount == 0 || fExtra[0] == -1); 3885 int eIndex = 0; 3886 int rIndex = 0; 3887 while (++eIndex < extraCount) { 3888 int offset = fExtra[eIndex]; 3889 if (offset < 0) { 3890 ++cIndex; 3891 continue; 3892 } 3893 fCurrentContour = &fContours[cIndex]; 3894 rIndex += fCurrentContour->updateSegment(offset - 1, 3895 &fReducePts[rIndex]); 3896 } 3897 fExtra.reset(); // we're done with this 3898} 3899 3900ShapeOpMask xorMask() const { 3901 return fXorMask; 3902} 3903 3904protected: 3905 3906void complete() { 3907 if (fCurrentContour && fCurrentContour->segments().count()) { 3908 fCurrentContour->complete(); 3909 fCurrentContour = NULL; 3910 } 3911} 3912 3913// FIXME:remove once we can access path pts directly 3914int preFetch() { 3915 SkPath::RawIter iter(*fPath); // FIXME: access path directly when allowed 3916 SkPoint pts[4]; 3917 SkPath::Verb verb; 3918 do { 3919 verb = iter.next(pts); 3920 *fPathVerbs.append() = verb; 3921 if (verb == SkPath::kMove_Verb) { 3922 *fPathPts.append() = pts[0]; 3923 } else if (verb >= SkPath::kLine_Verb && verb <= SkPath::kCubic_Verb) { 3924 fPathPts.append(verb, &pts[1]); 3925 } 3926 } while (verb != SkPath::kDone_Verb); 3927 return fPathVerbs.count(); 3928} 3929 3930void walk() { 3931 SkPath::Verb reducedVerb; 3932 uint8_t* verbPtr = fPathVerbs.begin(); 3933 uint8_t* endOfFirstHalf = &verbPtr[fSecondHalf]; 3934 const SkPoint* pointsPtr = fPathPts.begin(); 3935 const SkPoint* finalCurveStart = NULL; 3936 const SkPoint* finalCurveEnd = NULL; 3937 SkPath::Verb verb; 3938 while ((verb = (SkPath::Verb) *verbPtr++) != SkPath::kDone_Verb) { 3939 switch (verb) { 3940 case SkPath::kMove_Verb: 3941 complete(); 3942 if (!fCurrentContour) { 3943 fCurrentContour = fContours.push_back_n(1); 3944 fCurrentContour->setOperand(fOperand); 3945 fCurrentContour->setXor(fXorMask == kEvenOdd_Mask); 3946 *fExtra.append() = -1; // start new contour 3947 } 3948 finalCurveEnd = pointsPtr++; 3949 continue; 3950 case SkPath::kLine_Verb: 3951 // skip degenerate points 3952 if (pointsPtr[-1].fX != pointsPtr[0].fX 3953 || pointsPtr[-1].fY != pointsPtr[0].fY) { 3954 fCurrentContour->addLine(&pointsPtr[-1]); 3955 } 3956 break; 3957 case SkPath::kQuad_Verb: 3958 3959 reducedVerb = QuadReduceOrder(&pointsPtr[-1], fReducePts); 3960 if (reducedVerb == 0) { 3961 break; // skip degenerate points 3962 } 3963 if (reducedVerb == 1) { 3964 *fExtra.append() = 3965 fCurrentContour->addLine(fReducePts.end() - 2); 3966 break; 3967 } 3968 fCurrentContour->addQuad(&pointsPtr[-1]); 3969 break; 3970 case SkPath::kCubic_Verb: 3971 reducedVerb = CubicReduceOrder(&pointsPtr[-1], fReducePts); 3972 if (reducedVerb == 0) { 3973 break; // skip degenerate points 3974 } 3975 if (reducedVerb == 1) { 3976 *fExtra.append() = 3977 fCurrentContour->addLine(fReducePts.end() - 2); 3978 break; 3979 } 3980 if (reducedVerb == 2) { 3981 *fExtra.append() = 3982 fCurrentContour->addQuad(fReducePts.end() - 3); 3983 break; 3984 } 3985 fCurrentContour->addCubic(&pointsPtr[-1]); 3986 break; 3987 case SkPath::kClose_Verb: 3988 SkASSERT(fCurrentContour); 3989 if (finalCurveStart && finalCurveEnd 3990 && *finalCurveStart != *finalCurveEnd) { 3991 *fReducePts.append() = *finalCurveStart; 3992 *fReducePts.append() = *finalCurveEnd; 3993 *fExtra.append() = 3994 fCurrentContour->addLine(fReducePts.end() - 2); 3995 } 3996 complete(); 3997 continue; 3998 default: 3999 SkDEBUGFAIL("bad verb"); 4000 return; 4001 } 4002 finalCurveStart = &pointsPtr[verb - 1]; 4003 pointsPtr += verb; 4004 SkASSERT(fCurrentContour); 4005 if (verbPtr == endOfFirstHalf) { 4006 fOperand = true; 4007 } 4008 } 4009} 4010 4011private: 4012 const SkPath* fPath; 4013 SkTDArray<SkPoint> fPathPts; // FIXME: point directly to path pts instead 4014 SkTDArray<uint8_t> fPathVerbs; // FIXME: remove 4015 Contour* fCurrentContour; 4016 SkTArray<Contour>& fContours; 4017 SkTDArray<SkPoint> fReducePts; // segments created on the fly 4018 SkTDArray<int> fExtra; // -1 marks new contour, > 0 offsets into contour 4019 ShapeOpMask fXorMask; 4020 int fSecondHalf; 4021 bool fOperand; 4022}; 4023 4024class Work { 4025public: 4026 enum SegmentType { 4027 kHorizontalLine_Segment = -1, 4028 kVerticalLine_Segment = 0, 4029 kLine_Segment = SkPath::kLine_Verb, 4030 kQuad_Segment = SkPath::kQuad_Verb, 4031 kCubic_Segment = SkPath::kCubic_Verb, 4032 }; 4033 4034 void addCoincident(Work& other, const Intersections& ts, bool swap) { 4035 fContour->addCoincident(fIndex, other.fContour, other.fIndex, ts, swap); 4036 } 4037 4038 // FIXME: does it make sense to write otherIndex now if we're going to 4039 // fix it up later? 4040 void addOtherT(int index, double otherT, int otherIndex) { 4041 fContour->addOtherT(fIndex, index, otherT, otherIndex); 4042 } 4043 4044 // Avoid collapsing t values that are close to the same since 4045 // we walk ts to describe consecutive intersections. Since a pair of ts can 4046 // be nearly equal, any problems caused by this should be taken care 4047 // of later. 4048 // On the edge or out of range values are negative; add 2 to get end 4049 int addT(double newT, const Work& other) { 4050 return fContour->addT(fIndex, newT, other.fContour, other.fIndex); 4051 } 4052 4053 bool advance() { 4054 return ++fIndex < fLast; 4055 } 4056 4057 SkScalar bottom() const { 4058 return bounds().fBottom; 4059 } 4060 4061 const Bounds& bounds() const { 4062 return fContour->segments()[fIndex].bounds(); 4063 } 4064 4065 const SkPoint* cubic() const { 4066 return fCubic; 4067 } 4068 4069 void init(Contour* contour) { 4070 fContour = contour; 4071 fIndex = 0; 4072 fLast = contour->segments().count(); 4073 } 4074 4075 bool isAdjacent(const Work& next) { 4076 return fContour == next.fContour && fIndex + 1 == next.fIndex; 4077 } 4078 4079 bool isFirstLast(const Work& next) { 4080 return fContour == next.fContour && fIndex == 0 4081 && next.fIndex == fLast - 1; 4082 } 4083 4084 SkScalar left() const { 4085 return bounds().fLeft; 4086 } 4087 4088 void promoteToCubic() { 4089 fCubic[0] = pts()[0]; 4090 fCubic[2] = pts()[1]; 4091 fCubic[3] = pts()[2]; 4092 fCubic[1].fX = (fCubic[0].fX + fCubic[2].fX * 2) / 3; 4093 fCubic[1].fY = (fCubic[0].fY + fCubic[2].fY * 2) / 3; 4094 fCubic[2].fX = (fCubic[3].fX + fCubic[2].fX * 2) / 3; 4095 fCubic[2].fY = (fCubic[3].fY + fCubic[2].fY * 2) / 3; 4096 } 4097 4098 const SkPoint* pts() const { 4099 return fContour->segments()[fIndex].pts(); 4100 } 4101 4102 SkScalar right() const { 4103 return bounds().fRight; 4104 } 4105 4106 ptrdiff_t segmentIndex() const { 4107 return fIndex; 4108 } 4109 4110 SegmentType segmentType() const { 4111 const Segment& segment = fContour->segments()[fIndex]; 4112 SegmentType type = (SegmentType) segment.verb(); 4113 if (type != kLine_Segment) { 4114 return type; 4115 } 4116 if (segment.isHorizontal()) { 4117 return kHorizontalLine_Segment; 4118 } 4119 if (segment.isVertical()) { 4120 return kVerticalLine_Segment; 4121 } 4122 return kLine_Segment; 4123 } 4124 4125 bool startAfter(const Work& after) { 4126 fIndex = after.fIndex; 4127 return advance(); 4128 } 4129 4130 SkScalar top() const { 4131 return bounds().fTop; 4132 } 4133 4134 SkPath::Verb verb() const { 4135 return fContour->segments()[fIndex].verb(); 4136 } 4137 4138 SkScalar x() const { 4139 return bounds().fLeft; 4140 } 4141 4142 bool xFlipped() const { 4143 return x() != pts()[0].fX; 4144 } 4145 4146 SkScalar y() const { 4147 return bounds().fTop; 4148 } 4149 4150 bool yFlipped() const { 4151 return y() != pts()[0].fY; 4152 } 4153 4154protected: 4155 Contour* fContour; 4156 SkPoint fCubic[4]; 4157 int fIndex; 4158 int fLast; 4159}; 4160 4161#if DEBUG_ADD_INTERSECTING_TS 4162static void debugShowLineIntersection(int pts, const Work& wt, 4163 const Work& wn, const double wtTs[2], const double wnTs[2]) { 4164 return; 4165 if (!pts) { 4166 SkDebugf("%s no intersect (%1.9g,%1.9g %1.9g,%1.9g) (%1.9g,%1.9g %1.9g,%1.9g)\n", 4167 __FUNCTION__, wt.pts()[0].fX, wt.pts()[0].fY, 4168 wt.pts()[1].fX, wt.pts()[1].fY, wn.pts()[0].fX, wn.pts()[0].fY, 4169 wn.pts()[1].fX, wn.pts()[1].fY); 4170 return; 4171 } 4172 SkPoint wtOutPt, wnOutPt; 4173 LineXYAtT(wt.pts(), wtTs[0], &wtOutPt); 4174 LineXYAtT(wn.pts(), wnTs[0], &wnOutPt); 4175 SkDebugf("%s wtTs[0]=%1.9g (%1.9g,%1.9g %1.9g,%1.9g) (%1.9g,%1.9g)", 4176 __FUNCTION__, 4177 wtTs[0], wt.pts()[0].fX, wt.pts()[0].fY, 4178 wt.pts()[1].fX, wt.pts()[1].fY, wtOutPt.fX, wtOutPt.fY); 4179 if (pts == 2) { 4180 SkDebugf(" wtTs[1]=%1.9g", wtTs[1]); 4181 } 4182 SkDebugf(" wnTs[0]=%g (%1.9g,%1.9g %1.9g,%1.9g) (%1.9g,%1.9g)", 4183 wnTs[0], wn.pts()[0].fX, wn.pts()[0].fY, 4184 wn.pts()[1].fX, wn.pts()[1].fY, wnOutPt.fX, wnOutPt.fY); 4185 if (pts == 2) { 4186 SkDebugf(" wnTs[1]=%1.9g", wnTs[1]); 4187 } 4188 SkDebugf("\n"); 4189} 4190 4191static void debugShowQuadLineIntersection(int pts, const Work& wt, 4192 const Work& wn, const double wtTs[2], const double wnTs[2]) { 4193 if (!pts) { 4194 SkDebugf("%s no intersect (%1.9g,%1.9g %1.9g,%1.9g %1.9g,%1.9g)" 4195 " (%1.9g,%1.9g %1.9g,%1.9g)\n", 4196 __FUNCTION__, wt.pts()[0].fX, wt.pts()[0].fY, 4197 wt.pts()[1].fX, wt.pts()[1].fY, wt.pts()[2].fX, wt.pts()[2].fY, 4198 wn.pts()[0].fX, wn.pts()[0].fY, wn.pts()[1].fX, wn.pts()[1].fY); 4199 return; 4200 } 4201 SkPoint wtOutPt, wnOutPt; 4202 QuadXYAtT(wt.pts(), wtTs[0], &wtOutPt); 4203 LineXYAtT(wn.pts(), wnTs[0], &wnOutPt); 4204 SkDebugf("%s wtTs[0]=%1.9g (%1.9g,%1.9g %1.9g,%1.9g %1.9g,%1.9g) (%1.9g,%1.9g)", 4205 __FUNCTION__, 4206 wtTs[0], wt.pts()[0].fX, wt.pts()[0].fY, 4207 wt.pts()[1].fX, wt.pts()[1].fY, wt.pts()[2].fX, wt.pts()[2].fY, 4208 wtOutPt.fX, wtOutPt.fY); 4209 if (pts == 2) { 4210 QuadXYAtT(wt.pts(), wtTs[1], &wtOutPt); 4211 SkDebugf(" wtTs[1]=%1.9g (%1.9g,%1.9g)", wtTs[1], wtOutPt.fX, wtOutPt.fY); 4212 } 4213 SkDebugf(" wnTs[0]=%g (%1.9g,%1.9g %1.9g,%1.9g) (%1.9g,%1.9g)", 4214 wnTs[0], wn.pts()[0].fX, wn.pts()[0].fY, 4215 wn.pts()[1].fX, wn.pts()[1].fY, wnOutPt.fX, wnOutPt.fY); 4216 if (pts == 2) { 4217 LineXYAtT(wn.pts(), wnTs[1], &wnOutPt); 4218 SkDebugf(" wnTs[1]=%1.9g (%1.9g,%1.9g)", wnTs[1], wnOutPt.fX, wnOutPt.fY); 4219 } 4220 SkDebugf("\n"); 4221} 4222 4223static void debugShowQuadIntersection(int pts, const Work& wt, 4224 const Work& wn, const double wtTs[2], const double wnTs[2]) { 4225 if (!pts) { 4226 SkDebugf("%s no intersect (%1.9g,%1.9g %1.9g,%1.9g %1.9g,%1.9g)" 4227 " (%1.9g,%1.9g %1.9g,%1.9g %1.9g,%1.9g)\n", 4228 __FUNCTION__, wt.pts()[0].fX, wt.pts()[0].fY, 4229 wt.pts()[1].fX, wt.pts()[1].fY, wt.pts()[2].fX, wt.pts()[2].fY, 4230 wn.pts()[0].fX, wn.pts()[0].fY, wn.pts()[1].fX, wn.pts()[1].fY, 4231 wn.pts()[2].fX, wn.pts()[2].fY ); 4232 return; 4233 } 4234 SkPoint wtOutPt, wnOutPt; 4235 QuadXYAtT(wt.pts(), wtTs[0], &wtOutPt); 4236 QuadXYAtT(wn.pts(), wnTs[0], &wnOutPt); 4237 SkDebugf("%s wtTs[0]=%1.9g (%1.9g,%1.9g %1.9g,%1.9g %1.9g,%1.9g) (%1.9g,%1.9g)", 4238 __FUNCTION__, 4239 wtTs[0], wt.pts()[0].fX, wt.pts()[0].fY, 4240 wt.pts()[1].fX, wt.pts()[1].fY, wt.pts()[2].fX, wt.pts()[2].fY, 4241 wtOutPt.fX, wtOutPt.fY); 4242 if (pts == 2) { 4243 SkDebugf(" wtTs[1]=%1.9g", wtTs[1]); 4244 } 4245 SkDebugf(" wnTs[0]=%g (%1.9g,%1.9g %1.9g,%1.9g %1.9g,%1.9g) (%1.9g,%1.9g)", 4246 wnTs[0], wn.pts()[0].fX, wn.pts()[0].fY, 4247 wn.pts()[1].fX, wn.pts()[1].fY, wn.pts()[2].fX, wn.pts()[2].fY, 4248 wnOutPt.fX, wnOutPt.fY); 4249 if (pts == 2) { 4250 SkDebugf(" wnTs[1]=%1.9g", wnTs[1]); 4251 } 4252 SkDebugf("\n"); 4253} 4254#else 4255static void debugShowLineIntersection(int , const Work& , 4256 const Work& , const double [2], const double [2]) { 4257} 4258 4259static void debugShowQuadLineIntersection(int , const Work& , 4260 const Work& , const double [2], const double [2]) { 4261} 4262 4263static void debugShowQuadIntersection(int , const Work& , 4264 const Work& , const double [2], const double [2]) { 4265} 4266#endif 4267 4268static bool addIntersectTs(Contour* test, Contour* next) { 4269 4270 if (test != next) { 4271 if (test->bounds().fBottom < next->bounds().fTop) { 4272 return false; 4273 } 4274 if (!Bounds::Intersects(test->bounds(), next->bounds())) { 4275 return true; 4276 } 4277 } 4278 Work wt; 4279 wt.init(test); 4280 bool foundCommonContour = test == next; 4281 do { 4282 Work wn; 4283 wn.init(next); 4284 if (test == next && !wn.startAfter(wt)) { 4285 continue; 4286 } 4287 do { 4288 if (!Bounds::Intersects(wt.bounds(), wn.bounds())) { 4289 continue; 4290 } 4291 int pts; 4292 Intersections ts; 4293 bool swap = false; 4294 switch (wt.segmentType()) { 4295 case Work::kHorizontalLine_Segment: 4296 swap = true; 4297 switch (wn.segmentType()) { 4298 case Work::kHorizontalLine_Segment: 4299 case Work::kVerticalLine_Segment: 4300 case Work::kLine_Segment: { 4301 pts = HLineIntersect(wn.pts(), wt.left(), 4302 wt.right(), wt.y(), wt.xFlipped(), ts); 4303 debugShowLineIntersection(pts, wt, wn, 4304 ts.fT[1], ts.fT[0]); 4305 break; 4306 } 4307 case Work::kQuad_Segment: { 4308 pts = HQuadIntersect(wn.pts(), wt.left(), 4309 wt.right(), wt.y(), wt.xFlipped(), ts); 4310 break; 4311 } 4312 case Work::kCubic_Segment: { 4313 pts = HCubicIntersect(wn.pts(), wt.left(), 4314 wt.right(), wt.y(), wt.xFlipped(), ts); 4315 break; 4316 } 4317 default: 4318 SkASSERT(0); 4319 } 4320 break; 4321 case Work::kVerticalLine_Segment: 4322 swap = true; 4323 switch (wn.segmentType()) { 4324 case Work::kHorizontalLine_Segment: 4325 case Work::kVerticalLine_Segment: 4326 case Work::kLine_Segment: { 4327 pts = VLineIntersect(wn.pts(), wt.top(), 4328 wt.bottom(), wt.x(), wt.yFlipped(), ts); 4329 debugShowLineIntersection(pts, wt, wn, 4330 ts.fT[1], ts.fT[0]); 4331 break; 4332 } 4333 case Work::kQuad_Segment: { 4334 pts = VQuadIntersect(wn.pts(), wt.top(), 4335 wt.bottom(), wt.x(), wt.yFlipped(), ts); 4336 break; 4337 } 4338 case Work::kCubic_Segment: { 4339 pts = VCubicIntersect(wn.pts(), wt.top(), 4340 wt.bottom(), wt.x(), wt.yFlipped(), ts); 4341 break; 4342 } 4343 default: 4344 SkASSERT(0); 4345 } 4346 break; 4347 case Work::kLine_Segment: 4348 switch (wn.segmentType()) { 4349 case Work::kHorizontalLine_Segment: 4350 pts = HLineIntersect(wt.pts(), wn.left(), 4351 wn.right(), wn.y(), wn.xFlipped(), ts); 4352 debugShowLineIntersection(pts, wt, wn, 4353 ts.fT[1], ts.fT[0]); 4354 break; 4355 case Work::kVerticalLine_Segment: 4356 pts = VLineIntersect(wt.pts(), wn.top(), 4357 wn.bottom(), wn.x(), wn.yFlipped(), ts); 4358 debugShowLineIntersection(pts, wt, wn, 4359 ts.fT[1], ts.fT[0]); 4360 break; 4361 case Work::kLine_Segment: { 4362 pts = LineIntersect(wt.pts(), wn.pts(), ts); 4363 debugShowLineIntersection(pts, wt, wn, 4364 ts.fT[1], ts.fT[0]); 4365 break; 4366 } 4367 case Work::kQuad_Segment: { 4368 swap = true; 4369 pts = QuadLineIntersect(wn.pts(), wt.pts(), ts); 4370 debugShowQuadLineIntersection(pts, wn, wt, 4371 ts.fT[0], ts.fT[1]); 4372 break; 4373 } 4374 case Work::kCubic_Segment: { 4375 swap = true; 4376 pts = CubicLineIntersect(wn.pts(), wt.pts(), ts); 4377 break; 4378 } 4379 default: 4380 SkASSERT(0); 4381 } 4382 break; 4383 case Work::kQuad_Segment: 4384 switch (wn.segmentType()) { 4385 case Work::kHorizontalLine_Segment: 4386 pts = HQuadIntersect(wt.pts(), wn.left(), 4387 wn.right(), wn.y(), wn.xFlipped(), ts); 4388 break; 4389 case Work::kVerticalLine_Segment: 4390 pts = VQuadIntersect(wt.pts(), wn.top(), 4391 wn.bottom(), wn.x(), wn.yFlipped(), ts); 4392 break; 4393 case Work::kLine_Segment: { 4394 pts = QuadLineIntersect(wt.pts(), wn.pts(), ts); 4395 debugShowQuadLineIntersection(pts, wt, wn, 4396 ts.fT[0], ts.fT[1]); 4397 break; 4398 } 4399 case Work::kQuad_Segment: { 4400 pts = QuadIntersect(wt.pts(), wn.pts(), ts); 4401 debugShowQuadIntersection(pts, wt, wn, 4402 ts.fT[0], ts.fT[1]); 4403 break; 4404 } 4405 case Work::kCubic_Segment: { 4406 wt.promoteToCubic(); 4407 pts = CubicIntersect(wt.cubic(), wn.pts(), ts); 4408 break; 4409 } 4410 default: 4411 SkASSERT(0); 4412 } 4413 break; 4414 case Work::kCubic_Segment: 4415 switch (wn.segmentType()) { 4416 case Work::kHorizontalLine_Segment: 4417 pts = HCubicIntersect(wt.pts(), wn.left(), 4418 wn.right(), wn.y(), wn.xFlipped(), ts); 4419 break; 4420 case Work::kVerticalLine_Segment: 4421 pts = VCubicIntersect(wt.pts(), wn.top(), 4422 wn.bottom(), wn.x(), wn.yFlipped(), ts); 4423 break; 4424 case Work::kLine_Segment: { 4425 pts = CubicLineIntersect(wt.pts(), wn.pts(), ts); 4426 break; 4427 } 4428 case Work::kQuad_Segment: { 4429 wn.promoteToCubic(); 4430 pts = CubicIntersect(wt.pts(), wn.cubic(), ts); 4431 break; 4432 } 4433 case Work::kCubic_Segment: { 4434 pts = CubicIntersect(wt.pts(), wn.pts(), ts); 4435 break; 4436 } 4437 default: 4438 SkASSERT(0); 4439 } 4440 break; 4441 default: 4442 SkASSERT(0); 4443 } 4444 if (!foundCommonContour && pts > 0) { 4445 test->addCross(next); 4446 next->addCross(test); 4447 foundCommonContour = true; 4448 } 4449 // in addition to recording T values, record matching segment 4450 if (pts == 2) { 4451 if (wn.segmentType() <= Work::kLine_Segment 4452 && wt.segmentType() <= Work::kLine_Segment) { 4453 wt.addCoincident(wn, ts, swap); 4454 continue; 4455 } 4456 if (wn.segmentType() == Work::kQuad_Segment 4457 && wt.segmentType() == Work::kQuad_Segment 4458 && ts.coincidentUsed() == 2) { 4459 wt.addCoincident(wn, ts, swap); 4460 continue; 4461 } 4462 4463 } 4464 for (int pt = 0; pt < pts; ++pt) { 4465 SkASSERT(ts.fT[0][pt] >= 0 && ts.fT[0][pt] <= 1); 4466 SkASSERT(ts.fT[1][pt] >= 0 && ts.fT[1][pt] <= 1); 4467 int testTAt = wt.addT(ts.fT[swap][pt], wn); 4468 int nextTAt = wn.addT(ts.fT[!swap][pt], wt); 4469 wt.addOtherT(testTAt, ts.fT[!swap][pt ^ ts.fFlip], nextTAt); 4470 wn.addOtherT(nextTAt, ts.fT[swap][pt ^ ts.fFlip], testTAt); 4471 } 4472 } while (wn.advance()); 4473 } while (wt.advance()); 4474 return true; 4475} 4476 4477// resolve any coincident pairs found while intersecting, and 4478// see if coincidence is formed by clipping non-concident segments 4479static void coincidenceCheck(SkTDArray<Contour*>& contourList) { 4480 int contourCount = contourList.count(); 4481 for (int cIndex = 0; cIndex < contourCount; ++cIndex) { 4482 Contour* contour = contourList[cIndex]; 4483 contour->resolveCoincidence(); 4484 } 4485 for (int cIndex = 0; cIndex < contourCount; ++cIndex) { 4486 Contour* contour = contourList[cIndex]; 4487 contour->findTooCloseToCall(); 4488 } 4489#if 0 4490 // OPTIMIZATION: this check could be folded in with findTooClose -- maybe 4491 for (int cIndex = 0; cIndex < contourCount; ++cIndex) { 4492 Contour* contour = contourList[cIndex]; 4493 contour->collapseTriangles(); 4494 } 4495#endif 4496} 4497 4498// project a ray from the top of the contour up and see if it hits anything 4499// note: when we compute line intersections, we keep track of whether 4500// two contours touch, so we need only look at contours not touching this one. 4501// OPTIMIZATION: sort contourList vertically to avoid linear walk 4502static int innerContourCheck(SkTDArray<Contour*>& contourList, 4503 const Segment* current, int index, int endIndex) { 4504 const SkPoint& basePt = current->xyAtT(endIndex); 4505 int contourCount = contourList.count(); 4506 SkScalar bestY = SK_ScalarMin; 4507 const Segment* test = NULL; 4508 int tIndex; 4509 double tHit; 4510 // bool checkCrosses = true; 4511 for (int cTest = 0; cTest < contourCount; ++cTest) { 4512 Contour* contour = contourList[cTest]; 4513 if (basePt.fY < contour->bounds().fTop) { 4514 continue; 4515 } 4516 if (bestY > contour->bounds().fBottom) { 4517 continue; 4518 } 4519#if 0 4520 // even though the contours crossed, if spans cancel through concidence, 4521 // the contours may be not have any span links to chase, and the current 4522 // segment may be isolated. Detect this by seeing if current has 4523 // uninitialized wind sums. If so, project a ray instead of relying on 4524 // previously found intersections. 4525 if (baseContour == contour) { 4526 continue; 4527 } 4528 if (checkCrosses && baseContour->crosses(contour)) { 4529 if (current->isConnected(index, endIndex)) { 4530 continue; 4531 } 4532 checkCrosses = false; 4533 } 4534#endif 4535 const Segment* next = contour->crossedSegment(basePt, bestY, tIndex, tHit); 4536 if (next) { 4537 test = next; 4538 } 4539 } 4540 if (!test) { 4541 return 0; 4542 } 4543 int winding, windValue; 4544 // If the ray hit the end of a span, we need to construct the wheel of 4545 // angles to find the span closest to the ray -- even if there are just 4546 // two spokes on the wheel. 4547 const Angle* angle = NULL; 4548 if (approximately_zero(tHit - test->t(tIndex))) { 4549 SkTDArray<Angle> angles; 4550 int end = test->nextSpan(tIndex, 1); 4551 if (end < 0) { 4552 end = test->nextSpan(tIndex, -1); 4553 } 4554 test->addTwoAngles(end, tIndex, angles); 4555 SkASSERT(angles.count() > 0); 4556 if (angles[0].segment()->yAtT(angles[0].start()) >= basePt.fY) { 4557#if DEBUG_SORT 4558 SkDebugf("%s early return\n", __FUNCTION__); 4559#endif 4560 return 0; 4561 } 4562 test->buildAngles(tIndex, angles); 4563 SkTDArray<Angle*> sorted; 4564 // OPTIMIZATION: call a sort that, if base point is the leftmost, 4565 // returns the first counterclockwise hour before 6 o'clock, 4566 // or if the base point is rightmost, returns the first clockwise 4567 // hour after 6 o'clock 4568 (void) Segment::SortAngles(angles, sorted); 4569#if DEBUG_SORT 4570 sorted[0]->segment()->debugShowSort(__FUNCTION__, sorted, 0, 0); 4571#endif 4572 // walk the sorted angle fan to find the lowest angle 4573 // above the base point. Currently, the first angle in the sorted array 4574 // is 12 noon or an earlier hour (the next counterclockwise) 4575 int count = sorted.count(); 4576 int left = -1; 4577 int mid = -1; 4578 int right = -1; 4579 bool baseMatches = test->yAtT(tIndex) == basePt.fY; 4580 for (int index = 0; index < count; ++index) { 4581 angle = sorted[index]; 4582 if (angle->unsortable()) { 4583 continue; 4584 } 4585 if (baseMatches && angle->isHorizontal()) { 4586 continue; 4587 } 4588 double indexDx = angle->dx(); 4589 test = angle->segment(); 4590 if (test->verb() > SkPath::kLine_Verb && approximately_zero(indexDx)) { 4591 const SkPoint* pts = test->pts(); 4592 indexDx = pts[2].fX - pts[1].fX - indexDx; 4593 } 4594 if (indexDx < 0) { 4595 left = index; 4596 } else if (indexDx > 0) { 4597 right = index; 4598 int previous = index - 1; 4599 if (previous < 0) { 4600 previous = count - 1; 4601 } 4602 const Angle* prev = sorted[previous]; 4603 if (prev->dy() >= 0 && prev->dx() > 0 && angle->dy() < 0) { 4604#if DEBUG_SORT 4605 SkDebugf("%s use prev\n", __FUNCTION__); 4606#endif 4607 right = previous; 4608 } 4609 break; 4610 } else { 4611 mid = index; 4612 } 4613 } 4614 if (left < 0 && right < 0) { 4615 left = mid; 4616 } 4617 SkASSERT(left >= 0 || right >= 0); 4618 if (left < 0) { 4619 left = right; 4620 } else if (left >= 0 && mid >= 0 && right >= 0 4621 && sorted[mid]->sign() == sorted[right]->sign()) { 4622 left = right; 4623 } 4624 angle = sorted[left]; 4625 test = angle->segment(); 4626 winding = test->windSum(angle); 4627 SkASSERT(winding != SK_MinS32); 4628 windValue = test->windValue(angle); 4629#if DEBUG_WINDING 4630 SkDebugf("%s angle winding=%d windValue=%d sign=%d\n", __FUNCTION__, winding, 4631 windValue, angle->sign()); 4632#endif 4633 } else { 4634 winding = test->windSum(tIndex); 4635 SkASSERT(winding != SK_MinS32); 4636 windValue = test->windValue(tIndex); 4637#if DEBUG_WINDING 4638 SkDebugf("%s single winding=%d windValue=%d\n", __FUNCTION__, winding, 4639 windValue); 4640#endif 4641 } 4642 // see if a + change in T results in a +/- change in X (compute x'(T)) 4643 SkScalar dx = (*SegmentDXAtT[test->verb()])(test->pts(), tHit); 4644 if (test->verb() > SkPath::kLine_Verb && approximately_zero(dx)) { 4645 const SkPoint* pts = test->pts(); 4646 dx = pts[2].fX - pts[1].fX - dx; 4647 } 4648#if DEBUG_WINDING 4649 SkDebugf("%s dx=%1.9g\n", __FUNCTION__, dx); 4650#endif 4651 SkASSERT(dx != 0); 4652 if (winding * dx > 0) { // if same signs, result is negative 4653 winding += dx > 0 ? -windValue : windValue; 4654#if DEBUG_WINDING 4655 SkDebugf("%s final winding=%d\n", __FUNCTION__, winding); 4656#endif 4657 } 4658 return winding; 4659} 4660 4661#if SORTABLE_CONTOURS 4662// OPTIMIZATION: not crazy about linear search here to find top active y. 4663// seems like we should break down and do the sort, or maybe sort each 4664// contours' segments? 4665// Once the segment array is built, there's no reason I can think of not to 4666// sort it in Y. hmmm 4667// FIXME: return the contour found to pass to inner contour check 4668static Segment* findTopContour(SkTDArray<Contour*>& contourList) { 4669 int contourCount = contourList.count(); 4670 int cIndex = 0; 4671 Segment* topStart; 4672 SkScalar bestY = SK_ScalarMax; 4673 Contour* contour; 4674 do { 4675 contour = contourList[cIndex]; 4676 topStart = contour->topSegment(bestY); 4677 } while (!topStart && ++cIndex < contourCount); 4678 if (!topStart) { 4679 return NULL; 4680 } 4681 while (++cIndex < contourCount) { 4682 contour = contourList[cIndex]; 4683 if (bestY < contour->bounds().fTop) { 4684 continue; 4685 } 4686 SkScalar testY = SK_ScalarMax; 4687 Segment* test = contour->topSegment(testY); 4688 if (!test || bestY <= testY) { 4689 continue; 4690 } 4691 topStart = test; 4692 bestY = testY; 4693 } 4694 return topStart; 4695} 4696#endif 4697 4698static Segment* findUndone(SkTDArray<Contour*>& contourList, int& start, int& end) { 4699 int contourCount = contourList.count(); 4700 Segment* result; 4701 for (int cIndex = 0; cIndex < contourCount; ++cIndex) { 4702 Contour* contour = contourList[cIndex]; 4703 result = contour->undoneSegment(start, end); 4704 if (result) { 4705 return result; 4706 } 4707 } 4708 return NULL; 4709} 4710 4711 4712 4713static Segment* findChase(SkTDArray<Span*>& chase, int& tIndex, int& endIndex, 4714 int contourWinding) { 4715 while (chase.count()) { 4716 Span* span; 4717 chase.pop(&span); 4718 const Span& backPtr = span->fOther->span(span->fOtherIndex); 4719 Segment* segment = backPtr.fOther; 4720 tIndex = backPtr.fOtherIndex; 4721 SkTDArray<Angle> angles; 4722 int done = 0; 4723 if (segment->activeAngle(tIndex, done, angles)) { 4724 Angle* last = angles.end() - 1; 4725 tIndex = last->start(); 4726 endIndex = last->end(); 4727 #if TRY_ROTATE 4728 *chase.insert(0) = span; 4729 #else 4730 *chase.append() = span; 4731 #endif 4732 return last->segment(); 4733 } 4734 if (done == angles.count()) { 4735 continue; 4736 } 4737 SkTDArray<Angle*> sorted; 4738 bool sortable = Segment::SortAngles(angles, sorted); 4739#if DEBUG_SORT 4740 sorted[0]->segment()->debugShowSort(__FUNCTION__, sorted, 0, 0); 4741#endif 4742 if (!sortable) { 4743 continue; 4744 } 4745 // find first angle, initialize winding to computed fWindSum 4746 int firstIndex = -1; 4747 const Angle* angle; 4748 int winding; 4749 do { 4750 angle = sorted[++firstIndex]; 4751 segment = angle->segment(); 4752 winding = segment->windSum(angle); 4753 } while (winding == SK_MinS32); 4754 int spanWinding = segment->spanSign(angle->start(), angle->end()); 4755 #if DEBUG_WINDING 4756 SkDebugf("%s winding=%d spanWinding=%d contourWinding=%d\n", 4757 __FUNCTION__, winding, spanWinding, contourWinding); 4758 #endif 4759 // turn swinding into contourWinding 4760 if (spanWinding * winding < 0) { 4761 winding += spanWinding; 4762 } 4763 #if DEBUG_SORT 4764 segment->debugShowSort(__FUNCTION__, sorted, firstIndex, winding); 4765 #endif 4766 // we care about first sign and whether wind sum indicates this 4767 // edge is inside or outside. Maybe need to pass span winding 4768 // or first winding or something into this function? 4769 // advance to first undone angle, then return it and winding 4770 // (to set whether edges are active or not) 4771 int nextIndex = firstIndex + 1; 4772 int angleCount = sorted.count(); 4773 int lastIndex = firstIndex != 0 ? firstIndex : angleCount; 4774 angle = sorted[firstIndex]; 4775 winding -= angle->segment()->spanSign(angle); 4776 do { 4777 SkASSERT(nextIndex != firstIndex); 4778 if (nextIndex == angleCount) { 4779 nextIndex = 0; 4780 } 4781 angle = sorted[nextIndex]; 4782 segment = angle->segment(); 4783 int maxWinding = winding; 4784 winding -= segment->spanSign(angle); 4785 #if DEBUG_SORT 4786 SkDebugf("%s id=%d maxWinding=%d winding=%d sign=%d\n", __FUNCTION__, 4787 segment->debugID(), maxWinding, winding, angle->sign()); 4788 #endif 4789 tIndex = angle->start(); 4790 endIndex = angle->end(); 4791 int lesser = SkMin32(tIndex, endIndex); 4792 const Span& nextSpan = segment->span(lesser); 4793 if (!nextSpan.fDone) { 4794#if 1 4795 // FIXME: this be wrong. assign startWinding if edge is in 4796 // same direction. If the direction is opposite, winding to 4797 // assign is flipped sign or +/- 1? 4798 if (useInnerWinding(maxWinding, winding)) { 4799 maxWinding = winding; 4800 } 4801 segment->markWinding(lesser, maxWinding); 4802#endif 4803 break; 4804 } 4805 } while (++nextIndex != lastIndex); 4806 #if TRY_ROTATE 4807 *chase.insert(0) = span; 4808 #else 4809 *chase.append() = span; 4810 #endif 4811 return segment; 4812 } 4813 return NULL; 4814} 4815 4816#if DEBUG_ACTIVE_SPANS 4817static void debugShowActiveSpans(SkTDArray<Contour*>& contourList) { 4818 int index; 4819 for (index = 0; index < contourList.count(); ++ index) { 4820 contourList[index]->debugShowActiveSpans(); 4821 } 4822 for (index = 0; index < contourList.count(); ++ index) { 4823 contourList[index]->validateActiveSpans(); 4824 } 4825} 4826#endif 4827 4828static bool windingIsActive(int winding, int spanWinding) { 4829 return winding * spanWinding <= 0 && abs(winding) <= abs(spanWinding) 4830 && (!winding || !spanWinding || winding == -spanWinding); 4831} 4832 4833#if !SORTABLE_CONTOURS 4834static Segment* findSortableTop(SkTDArray<Contour*>& contourList, int& index, 4835 int& endIndex, SkPoint& topLeft) { 4836 Segment* result; 4837 do { 4838 SkPoint bestXY = {SK_ScalarMax, SK_ScalarMax}; 4839 int contourCount = contourList.count(); 4840 Segment* topStart = NULL; 4841 for (int cIndex = 0; cIndex < contourCount; ++cIndex) { 4842 Contour* contour = contourList[cIndex]; 4843 const Bounds& bounds = contour->bounds(); 4844 if (bounds.fBottom < topLeft.fY) { 4845 continue; 4846 } 4847 if (bounds.fBottom == topLeft.fY && bounds.fRight < topLeft.fX) { 4848 continue; 4849 } 4850 Segment* test = contour->topSortableSegment(topLeft, bestXY); 4851 if (test) { 4852 topStart = test; 4853 } 4854 } 4855 if (!topStart) { 4856 return NULL; 4857 } 4858 topLeft = bestXY; 4859 result = topStart->findTop(index, endIndex); 4860 } while (!result); 4861 return result; 4862} 4863#endif 4864 4865// Each segment may have an inside or an outside. Segments contained within 4866// winding may have insides on either side, and form a contour that should be 4867// ignored. Segments that are coincident with opposing direction segments may 4868// have outsides on either side, and should also disappear. 4869// 'Normal' segments will have one inside and one outside. Subsequent connections 4870// when winding should follow the intersection direction. If more than one edge 4871// is an option, choose first edge that continues the inside. 4872 // since we start with leftmost top edge, we'll traverse through a 4873 // smaller angle counterclockwise to get to the next edge. 4874// returns true if all edges were processed 4875static bool bridgeWinding(SkTDArray<Contour*>& contourList, PathWrapper& simple) { 4876 bool firstContour = true; 4877 bool unsortable = false; 4878 bool closable = true; 4879 SkPoint topLeft = {SK_ScalarMin, SK_ScalarMin}; 4880 do { 4881#if SORTABLE_CONTOURS // old way 4882 Segment* topStart = findTopContour(contourList); 4883 if (!topStart) { 4884 break; 4885 } 4886 // Start at the top. Above the top is outside, below is inside. 4887 // follow edges to intersection by changing the index by direction. 4888 int index, endIndex; 4889 Segment* current = topStart->findTop(index, endIndex); 4890#else // new way: iterate while top is unsortable 4891 int index, endIndex; 4892 Segment* current = findSortableTop(contourList, index, endIndex, topLeft); 4893 if (!current) { 4894 break; 4895 } 4896#endif 4897 int contourWinding; 4898 if (firstContour) { 4899 contourWinding = 0; 4900 firstContour = false; 4901 } else { 4902 int sumWinding = current->windSum(SkMin32(index, endIndex)); 4903 // FIXME: don't I have to adjust windSum to get contourWinding? 4904 if (sumWinding == SK_MinS32) { 4905 sumWinding = current->computeSum(index, endIndex); 4906 } 4907 if (sumWinding == SK_MinS32) { 4908 contourWinding = innerContourCheck(contourList, current, 4909 index, endIndex); 4910 } else { 4911 contourWinding = sumWinding; 4912 int spanWinding = current->spanSign(index, endIndex); 4913 bool inner = useInnerWinding(sumWinding - spanWinding, sumWinding); 4914 if (inner) { 4915 contourWinding -= spanWinding; 4916 } 4917#if DEBUG_WINDING 4918 SkDebugf("%s sumWinding=%d spanWinding=%d sign=%d inner=%d result=%d\n", __FUNCTION__, 4919 sumWinding, spanWinding, SkSign32(index - endIndex), 4920 inner, contourWinding); 4921#endif 4922 } 4923#if DEBUG_WINDING 4924 // SkASSERT(current->debugVerifyWinding(index, endIndex, contourWinding)); 4925 SkDebugf("%s contourWinding=%d\n", __FUNCTION__, contourWinding); 4926#endif 4927 } 4928 int winding = contourWinding; 4929 int spanWinding = current->spanSign(index, endIndex); 4930 // FIXME: needs work. While it works in limited situations, it does 4931 // not always compute winding correctly. Active should be removed and instead 4932 // the initial winding should be correctly passed in so that if the 4933 // inner contour is wound the same way, it never finds an accumulated 4934 // winding of zero. Inside 'find next', we need to look for transitions 4935 // other than zero when resolving sorted angles. 4936 bool active = windingIsActive(winding, spanWinding); 4937 SkTDArray<Span*> chaseArray; 4938 do { 4939 #if DEBUG_WINDING 4940 SkDebugf("%s active=%s winding=%d spanWinding=%d\n", 4941 __FUNCTION__, active ? "true" : "false", 4942 winding, spanWinding); 4943 #endif 4944 do { 4945 SkASSERT(unsortable || !current->done()); 4946 int nextStart = index; 4947 int nextEnd = endIndex; 4948 Segment* next = current->findNextWinding(chaseArray, active, 4949 nextStart, nextEnd, winding, spanWinding, unsortable); 4950 if (!next) { 4951 if (active && !unsortable && simple.hasMove() 4952 && current->verb() != SkPath::kLine_Verb 4953 && !simple.isClosed()) { 4954 current->addCurveTo(index, endIndex, simple, true); 4955 SkASSERT(simple.isClosed()); 4956 } 4957 break; 4958 } 4959 current->addCurveTo(index, endIndex, simple, active); 4960 current = next; 4961 index = nextStart; 4962 endIndex = nextEnd; 4963 } while (!simple.isClosed() 4964 && ((active && !unsortable) || !current->done())); 4965 if (active) { 4966 if (!simple.isClosed()) { 4967 SkASSERT(unsortable); 4968 int min = SkMin32(index, endIndex); 4969 if (!current->done(min)) { 4970 current->addCurveTo(index, endIndex, simple, true); 4971 current->markDone(SkMin32(index, endIndex), winding ? winding : spanWinding); 4972 } 4973 closable = false; 4974 } 4975 simple.close(); 4976 } 4977 current = findChase(chaseArray, index, endIndex, contourWinding); 4978 #if DEBUG_ACTIVE_SPANS 4979 debugShowActiveSpans(contourList); 4980 #endif 4981 if (!current) { 4982 break; 4983 } 4984 int lesser = SkMin32(index, endIndex); 4985 spanWinding = current->spanSign(index, endIndex); 4986 winding = current->windSum(lesser); 4987 bool inner = useInnerWinding(winding - spanWinding, winding); 4988 #if DEBUG_WINDING 4989 SkDebugf("%s id=%d t=%1.9g spanWinding=%d winding=%d sign=%d" 4990 " inner=%d result=%d\n", 4991 __FUNCTION__, current->debugID(), current->t(lesser), 4992 spanWinding, winding, SkSign32(index - endIndex), 4993 useInnerWinding(winding - spanWinding, winding), 4994 inner ? winding - spanWinding : winding); 4995 #endif 4996 if (inner) { 4997 winding -= spanWinding; 4998 } 4999 active = windingIsActive(winding, spanWinding); 5000 } while (true); 5001 } while (true); 5002 return closable; 5003} 5004 5005// returns true if all edges were processed 5006static bool bridgeXor(SkTDArray<Contour*>& contourList, PathWrapper& simple) { 5007 Segment* current; 5008 int start, end; 5009 bool unsortable = false; 5010 while ((current = findUndone(contourList, start, end))) { 5011 do { 5012 SkASSERT(unsortable || !current->done()); 5013 int nextStart = start; 5014 int nextEnd = end; 5015 Segment* next = current->findNextXor(nextStart, nextEnd, unsortable); 5016 if (!next) { 5017 if (simple.hasMove() 5018 && current->verb() != SkPath::kLine_Verb 5019 && !simple.isClosed()) { 5020 current->addCurveTo(start, end, simple, true); 5021 SkASSERT(simple.isClosed()); 5022 } 5023 break; 5024 } 5025 current->addCurveTo(start, end, simple, true); 5026 current = next; 5027 start = nextStart; 5028 end = nextEnd; 5029 } while (!simple.isClosed()); 5030 // FIXME: add unsortable test 5031 if (simple.hasMove()) { 5032 simple.close(); 5033 } 5034 #if DEBUG_ACTIVE_SPANS 5035 debugShowActiveSpans(contourList); 5036 #endif 5037 } 5038 return !unsortable; 5039} 5040 5041static void fixOtherTIndex(SkTDArray<Contour*>& contourList) { 5042 int contourCount = contourList.count(); 5043 for (int cTest = 0; cTest < contourCount; ++cTest) { 5044 Contour* contour = contourList[cTest]; 5045 contour->fixOtherTIndex(); 5046 } 5047} 5048 5049#if !SORTABLE_CONTOURS 5050static void sortSegments(SkTDArray<Contour*>& contourList) { 5051 int contourCount = contourList.count(); 5052 for (int cTest = 0; cTest < contourCount; ++cTest) { 5053 Contour* contour = contourList[cTest]; 5054 contour->sortSegments(); 5055 } 5056} 5057#endif 5058 5059static void makeContourList(SkTArray<Contour>& contours, 5060 SkTDArray<Contour*>& list) { 5061 int count = contours.count(); 5062 if (count == 0) { 5063 return; 5064 } 5065 for (int index = 0; index < count; ++index) { 5066 *list.append() = &contours[index]; 5067 } 5068 QSort<Contour>(list.begin(), list.end() - 1); 5069} 5070 5071static bool approximatelyEqual(const SkPoint& a, const SkPoint& b) { 5072 return AlmostEqualUlps(a.fX, b.fX) && AlmostEqualUlps(a.fY, b.fY); 5073} 5074 5075 /* 5076 check start and end of each contour 5077 if not the same, record them 5078 match them up 5079 connect closest 5080 reassemble contour pieces into new path 5081 */ 5082static void assemble(const PathWrapper& path, PathWrapper& simple) { 5083#if DEBUG_PATH_CONSTRUCTION 5084 SkDebugf("%s\n", __FUNCTION__); 5085#endif 5086 SkTArray<Contour> contours; 5087 EdgeBuilder builder(path, contours); 5088 builder.finish(); 5089 int count = contours.count(); 5090 int outer; 5091 SkTDArray<int> runs; // indices of partial contours 5092 for (outer = 0; outer < count; ++outer) { 5093 const Contour& eContour = contours[outer]; 5094 const SkPoint& eStart = eContour.start(); 5095 const SkPoint& eEnd = eContour.end(); 5096 if (approximatelyEqual(eStart, eEnd)) { 5097 eContour.toPath(simple); 5098 continue; 5099 } 5100 *runs.append() = outer; 5101 } 5102 count = runs.count(); 5103 if (count == 0) { 5104 return; 5105 } 5106 SkTDArray<int> sLink, eLink; 5107 sLink.setCount(count); 5108 eLink.setCount(count); 5109 SkTDArray<double> sBest, eBest; 5110 sBest.setCount(count); 5111 eBest.setCount(count); 5112 int rIndex; 5113 for (rIndex = 0; rIndex < count; ++rIndex) { 5114 outer = runs[rIndex]; 5115 const Contour& oContour = contours[outer]; 5116 const SkPoint& oStart = oContour.start(); 5117 const SkPoint& oEnd = oContour.end(); 5118 double dx = oEnd.fX - oStart.fX; 5119 double dy = oEnd.fY - oStart.fY; 5120 double dist = dx * dx + dy * dy; 5121 sBest[rIndex] = eBest[rIndex] = dist; 5122 sLink[rIndex] = eLink[rIndex] = rIndex; 5123 } 5124 for (rIndex = 0; rIndex < count - 1; ++rIndex) { 5125 outer = runs[rIndex]; 5126 const Contour& oContour = contours[outer]; 5127 const SkPoint& oStart = oContour.start(); 5128 const SkPoint& oEnd = oContour.end(); 5129 double bestStartDist = sBest[rIndex]; 5130 double bestEndDist = eBest[rIndex]; 5131 for (int iIndex = rIndex + 1; iIndex < count; ++iIndex) { 5132 int inner = runs[iIndex]; 5133 const Contour& iContour = contours[inner]; 5134 const SkPoint& iStart = iContour.start(); 5135 const SkPoint& iEnd = iContour.end(); 5136 double dx = iStart.fX - oStart.fX; 5137 double dy = iStart.fY - oStart.fY; 5138 double dist = dx * dx + dy * dy; 5139 if (bestStartDist > dist) { 5140 bestStartDist = dist; 5141 sLink[rIndex] = ~iIndex; 5142 sLink[iIndex] = ~rIndex; 5143 } 5144 dx = iEnd.fX - oStart.fX; 5145 dy = iEnd.fY - oStart.fY; 5146 dist = dx * dx + dy * dy; 5147 if (bestStartDist > dist) { 5148 bestStartDist = dist; 5149 sLink[rIndex] = iIndex; 5150 eLink[iIndex] = rIndex; 5151 } 5152 dx = iStart.fX - oEnd.fX; 5153 dy = iStart.fY - oEnd.fY; 5154 dist = dx * dx + dy * dy; 5155 if (bestEndDist > dist) { 5156 bestEndDist = dist; 5157 sLink[iIndex] = rIndex; 5158 eLink[rIndex] = iIndex; 5159 } 5160 dx = iEnd.fX - oEnd.fX; 5161 dy = iEnd.fY - oEnd.fY; 5162 dist = dx * dx + dy * dy; 5163 if (bestEndDist > dist) { 5164 bestEndDist = dist; 5165 eLink[iIndex] = ~rIndex; 5166 eLink[rIndex] = ~iIndex; 5167 } 5168 } 5169 } 5170 rIndex = 0; 5171 bool forward = true; 5172 bool first = true; 5173 const SkPoint* startPtr; 5174 int sIndex = sLink[rIndex]; 5175 SkASSERT(sIndex != INT_MAX); 5176 sLink[rIndex] = INT_MAX; 5177 int eIndex; 5178 if (sIndex < 0) { 5179 eIndex = sLink[~sIndex]; 5180 sLink[~sIndex] = INT_MAX; 5181 } else { 5182 eIndex = eLink[sIndex]; 5183 eLink[sIndex] = INT_MAX; 5184 } 5185 SkASSERT(eIndex != INT_MAX); 5186 do { 5187 do { 5188 outer = runs[rIndex]; 5189 const Contour& contour = contours[outer]; 5190 if (first) { 5191 startPtr = &contour.start(); 5192 first = false; 5193 simple.deferredMove(startPtr[0]); 5194 } 5195 const SkPoint* endPtr; 5196 if (forward) { 5197 contour.toPartialForward(simple); 5198 endPtr = &contour.end(); 5199 } else { 5200 contour.toPartialBackward(simple); 5201 endPtr = &contour.start(); 5202 } 5203 if (sIndex == eIndex) { 5204 simple.close(); 5205 first = forward = true; 5206 break; 5207 } 5208 if (forward) { 5209 eIndex = eLink[rIndex]; 5210 SkASSERT(eIndex != INT_MAX); 5211 eLink[rIndex] = INT_MAX; 5212 if (eIndex >= 0) { 5213 SkASSERT(sLink[eIndex] == rIndex); 5214 sLink[eIndex] = INT_MAX; 5215 } else { 5216 SkASSERT(eLink[~eIndex] == ~rIndex); 5217 eLink[~eIndex] = INT_MAX; 5218 } 5219 } else { 5220 eIndex = sLink[rIndex]; 5221 SkASSERT(eIndex != INT_MAX); 5222 sLink[rIndex] = INT_MAX; 5223 if (eIndex >= 0) { 5224 SkASSERT(eLink[eIndex] == rIndex); 5225 eLink[eIndex] = INT_MAX; 5226 } else { 5227 SkASSERT(sLink[~eIndex] == ~rIndex); 5228 sLink[~eIndex] = INT_MAX; 5229 } 5230 } 5231 rIndex = eIndex; 5232 if (rIndex < 0) { 5233 forward ^= 1; 5234 rIndex = ~rIndex; 5235 } 5236 } while (true); 5237 for (rIndex = 0; rIndex < count; ++rIndex) { 5238 if (sLink[rIndex] != INT_MAX) { 5239 break; 5240 } 5241 } 5242 } while (rIndex < count); 5243 SkASSERT(first); 5244} 5245 5246void simplifyx(const SkPath& path, SkPath& result) { 5247 // returns 1 for evenodd, -1 for winding, regardless of inverse-ness 5248 result.reset(); 5249 result.setFillType(SkPath::kEvenOdd_FillType); 5250 PathWrapper simple(result); 5251 5252 // turn path into list of segments 5253 SkTArray<Contour> contours; 5254 // FIXME: add self-intersecting cubics' T values to segment 5255 EdgeBuilder builder(path, contours); 5256 builder.finish(); 5257 SkTDArray<Contour*> contourList; 5258 makeContourList(contours, contourList); 5259 Contour** currentPtr = contourList.begin(); 5260 if (!currentPtr) { 5261 return; 5262 } 5263 Contour** listEnd = contourList.end(); 5264 // find all intersections between segments 5265 do { 5266 Contour** nextPtr = currentPtr; 5267 Contour* current = *currentPtr++; 5268 Contour* next; 5269 do { 5270 next = *nextPtr++; 5271 } while (addIntersectTs(current, next) && nextPtr != listEnd); 5272 } while (currentPtr != listEnd); 5273 // eat through coincident edges 5274 coincidenceCheck(contourList); 5275 fixOtherTIndex(contourList); 5276#if !SORTABLE_CONTOURS 5277 sortSegments(contourList); 5278#endif 5279#if DEBUG_ACTIVE_SPANS 5280 debugShowActiveSpans(contourList); 5281#endif 5282 // construct closed contours 5283 if (builder.xorMask() == kWinding_Mask 5284 ? !bridgeWinding(contourList, simple) 5285 : !bridgeXor(contourList, simple)) 5286 { // if some edges could not be resolved, assemble remaining fragments 5287 SkPath temp; 5288 temp.setFillType(SkPath::kEvenOdd_FillType); 5289 PathWrapper assembled(temp); 5290 assemble(simple, assembled); 5291 result = *assembled.nativePath(); 5292 } 5293} 5294 5295