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