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