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