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