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