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