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