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