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