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