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