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