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