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