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