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