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