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