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