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