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