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