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