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