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