Simplify.cpp revision 88f7d0cb09707355bc9079d4b0569537e8048fa9
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 21// FIXME: remove once debugging is complete 22#if 0 // set to 1 for no debugging whatsoever 23 24//const bool gxRunTestsInOneThread = false; 25 26#define DEBUG_ADD_INTERSECTING_TS 0 27#define DEBUG_BRIDGE 0 28#define DEBUG_DUMP 0 29#define DEBUG_PATH_CONSTRUCTION 0 30#define DEBUG_UNUSED 0 // set to expose unused functions 31 32#else 33 34//const bool gRunTestsInOneThread = true; 35 36#define DEBUG_ADD_INTERSECTING_TS 0 37#define DEBUG_BRIDGE 1 38#define DEBUG_DUMP 1 39#define DEBUG_PATH_CONSTRUCTION 1 40#define DEBUG_UNUSED 0 // set to expose unused functions 41 42#endif 43 44#if DEBUG_DUMP 45static const char* kLVerbStr[] = {"", "line", "quad", "cubic"}; 46// static const char* kUVerbStr[] = {"", "Line", "Quad", "Cubic"}; 47static int gContourID; 48static int gSegmentID; 49#endif 50 51static int LineIntersect(const SkPoint a[2], const SkPoint b[2], 52 Intersections& intersections) { 53 const _Line aLine = {{a[0].fX, a[0].fY}, {a[1].fX, a[1].fY}}; 54 const _Line bLine = {{b[0].fX, b[0].fY}, {b[1].fX, b[1].fY}}; 55 return intersect(aLine, bLine, intersections.fT[0], intersections.fT[1]); 56} 57 58static int QuadLineIntersect(const SkPoint a[3], const SkPoint b[2], 59 Intersections& intersections) { 60 const Quadratic aQuad = {{a[0].fX, a[0].fY}, {a[1].fX, a[1].fY}, {a[2].fX, a[2].fY}}; 61 const _Line bLine = {{b[0].fX, b[0].fY}, {b[1].fX, b[1].fY}}; 62 intersect(aQuad, bLine, intersections); 63 return intersections.fUsed; 64} 65 66static int CubicLineIntersect(const SkPoint a[2], const SkPoint b[3], 67 Intersections& intersections) { 68 const Cubic aCubic = {{a[0].fX, a[0].fY}, {a[1].fX, a[1].fY}, {a[2].fX, a[2].fY}, 69 {a[3].fX, a[3].fY}}; 70 const _Line bLine = {{b[0].fX, b[0].fY}, {b[1].fX, b[1].fY}}; 71 return intersect(aCubic, bLine, intersections.fT[0], intersections.fT[1]); 72} 73 74static int QuadIntersect(const SkPoint a[3], const SkPoint b[3], 75 Intersections& intersections) { 76 const Quadratic aQuad = {{a[0].fX, a[0].fY}, {a[1].fX, a[1].fY}, {a[2].fX, a[2].fY}}; 77 const Quadratic bQuad = {{b[0].fX, b[0].fY}, {b[1].fX, b[1].fY}, {b[2].fX, b[2].fY}}; 78 intersect(aQuad, bQuad, intersections); 79 return intersections.fUsed; 80} 81 82static int CubicIntersect(const SkPoint a[4], const SkPoint b[4], 83 Intersections& intersections) { 84 const Cubic aCubic = {{a[0].fX, a[0].fY}, {a[1].fX, a[1].fY}, {a[2].fX, a[2].fY}, 85 {a[3].fX, a[3].fY}}; 86 const Cubic bCubic = {{b[0].fX, b[0].fY}, {b[1].fX, b[1].fY}, {b[2].fX, b[2].fY}, 87 {b[3].fX, b[3].fY}}; 88 intersect(aCubic, bCubic, intersections); 89 return intersections.fUsed; 90} 91 92static int HLineIntersect(const SkPoint a[2], SkScalar left, SkScalar right, 93 SkScalar y, bool flipped, Intersections& intersections) { 94 const _Line aLine = {{a[0].fX, a[0].fY}, {a[1].fX, a[1].fY}}; 95 return horizontalIntersect(aLine, left, right, y, flipped, intersections); 96} 97 98static int VLineIntersect(const SkPoint a[2], SkScalar left, SkScalar right, 99 SkScalar y, bool flipped, Intersections& intersections) { 100 const _Line aLine = {{a[0].fX, a[0].fY}, {a[1].fX, a[1].fY}}; 101 return verticalIntersect(aLine, left, right, y, flipped, intersections); 102} 103 104static int HQuadIntersect(const SkPoint a[3], SkScalar left, SkScalar right, 105 SkScalar y, bool flipped, Intersections& intersections) { 106 const Quadratic aQuad = {{a[0].fX, a[0].fY}, {a[1].fX, a[1].fY}, {a[2].fX, a[2].fY}}; 107 return horizontalIntersect(aQuad, left, right, y, flipped, intersections); 108} 109 110static int VQuadIntersect(const SkPoint a[3], SkScalar left, SkScalar right, 111 SkScalar y, bool flipped, Intersections& intersections) { 112 const Quadratic aQuad = {{a[0].fX, a[0].fY}, {a[1].fX, a[1].fY}, {a[2].fX, a[2].fY}}; 113 return verticalIntersect(aQuad, left, right, y, flipped, intersections); 114} 115 116static int HCubicIntersect(const SkPoint a[4], SkScalar left, SkScalar right, 117 SkScalar y, bool flipped, Intersections& intersections) { 118 const Cubic aCubic = {{a[0].fX, a[0].fY}, {a[1].fX, a[1].fY}, {a[2].fX, a[2].fY}, 119 {a[3].fX, a[3].fY}}; 120 return horizontalIntersect(aCubic, left, right, y, flipped, intersections); 121} 122 123static int VCubicIntersect(const SkPoint a[4], SkScalar left, SkScalar right, 124 SkScalar y, bool flipped, Intersections& intersections) { 125 const Cubic aCubic = {{a[0].fX, a[0].fY}, {a[1].fX, a[1].fY}, {a[2].fX, a[2].fY}, 126 {a[3].fX, a[3].fY}}; 127 return verticalIntersect(aCubic, left, right, y, flipped, intersections); 128} 129 130static void LineXYAtT(const SkPoint a[2], double t, SkPoint* out) { 131 const _Line line = {{a[0].fX, a[0].fY}, {a[1].fX, a[1].fY}}; 132 double x, y; 133 xy_at_t(line, t, x, y); 134 out->fX = SkDoubleToScalar(x); 135 out->fY = SkDoubleToScalar(y); 136} 137 138static void QuadXYAtT(const SkPoint a[3], double t, SkPoint* out) { 139 const Quadratic quad = {{a[0].fX, a[0].fY}, {a[1].fX, a[1].fY}, {a[2].fX, a[2].fY}}; 140 double x, y; 141 xy_at_t(quad, t, x, y); 142 out->fX = SkDoubleToScalar(x); 143 out->fY = SkDoubleToScalar(y); 144} 145 146static void CubicXYAtT(const SkPoint a[4], double t, SkPoint* out) { 147 const Cubic cubic = {{a[0].fX, a[0].fY}, {a[1].fX, a[1].fY}, {a[2].fX, a[2].fY}, 148 {a[3].fX, a[3].fY}}; 149 double x, y; 150 xy_at_t(cubic, t, x, y); 151 out->fX = SkDoubleToScalar(x); 152 out->fY = SkDoubleToScalar(y); 153} 154 155static void (* const SegmentXYAtT[])(const SkPoint [], double , SkPoint* ) = { 156 NULL, 157 LineXYAtT, 158 QuadXYAtT, 159 CubicXYAtT 160}; 161 162static SkScalar LineXAtT(const SkPoint a[2], double t) { 163 const _Line aLine = {{a[0].fX, a[0].fY}, {a[1].fX, a[1].fY}}; 164 double x; 165 xy_at_t(aLine, t, x, *(double*) 0); 166 return SkDoubleToScalar(x); 167} 168 169static SkScalar QuadXAtT(const SkPoint a[3], double t) { 170 const Quadratic quad = {{a[0].fX, a[0].fY}, {a[1].fX, a[1].fY}, {a[2].fX, a[2].fY}}; 171 double x; 172 xy_at_t(quad, t, x, *(double*) 0); 173 return SkDoubleToScalar(x); 174} 175 176static SkScalar CubicXAtT(const SkPoint a[4], double t) { 177 const Cubic cubic = {{a[0].fX, a[0].fY}, {a[1].fX, a[1].fY}, {a[2].fX, a[2].fY}, 178 {a[3].fX, a[3].fY}}; 179 double x; 180 xy_at_t(cubic, t, x, *(double*) 0); 181 return SkDoubleToScalar(x); 182} 183 184static SkScalar (* const SegmentXAtT[])(const SkPoint [], double ) = { 185 NULL, 186 LineXAtT, 187 QuadXAtT, 188 CubicXAtT 189}; 190 191static SkScalar LineYAtT(const SkPoint a[2], double t) { 192 const _Line aLine = {{a[0].fX, a[0].fY}, {a[1].fX, a[1].fY}}; 193 double y; 194 xy_at_t(aLine, t, *(double*) 0, y); 195 return SkDoubleToScalar(y); 196} 197 198static SkScalar QuadYAtT(const SkPoint a[3], double t) { 199 const Quadratic quad = {{a[0].fX, a[0].fY}, {a[1].fX, a[1].fY}, {a[2].fX, a[2].fY}}; 200 double y; 201 xy_at_t(quad, t, *(double*) 0, y); 202 return SkDoubleToScalar(y); 203} 204 205static SkScalar CubicYAtT(const SkPoint a[4], double t) { 206 const Cubic cubic = {{a[0].fX, a[0].fY}, {a[1].fX, a[1].fY}, {a[2].fX, a[2].fY}, 207 {a[3].fX, a[3].fY}}; 208 double y; 209 xy_at_t(cubic, t, *(double*) 0, y); 210 return SkDoubleToScalar(y); 211} 212 213static SkScalar (* const SegmentYAtT[])(const SkPoint [], double ) = { 214 NULL, 215 LineYAtT, 216 QuadYAtT, 217 CubicYAtT 218}; 219 220static void LineSubDivide(const SkPoint a[2], double startT, double endT, 221 SkPoint sub[2]) { 222 const _Line aLine = {{a[0].fX, a[0].fY}, {a[1].fX, a[1].fY}}; 223 _Line dst; 224 sub_divide(aLine, startT, endT, dst); 225 sub[0].fX = SkDoubleToScalar(dst[0].x); 226 sub[0].fY = SkDoubleToScalar(dst[0].y); 227 sub[1].fX = SkDoubleToScalar(dst[1].x); 228 sub[1].fY = SkDoubleToScalar(dst[1].y); 229} 230 231static void QuadSubDivide(const SkPoint a[3], double startT, double endT, 232 SkPoint sub[3]) { 233 const Quadratic aQuad = {{a[0].fX, a[0].fY}, {a[1].fX, a[1].fY}, 234 {a[2].fX, a[2].fY}}; 235 Quadratic dst; 236 sub_divide(aQuad, startT, endT, dst); 237 sub[0].fX = SkDoubleToScalar(dst[0].x); 238 sub[0].fY = SkDoubleToScalar(dst[0].y); 239 sub[1].fX = SkDoubleToScalar(dst[1].x); 240 sub[1].fY = SkDoubleToScalar(dst[1].y); 241 sub[2].fX = SkDoubleToScalar(dst[2].x); 242 sub[2].fY = SkDoubleToScalar(dst[2].y); 243} 244 245static void CubicSubDivide(const SkPoint a[4], double startT, double endT, 246 SkPoint sub[4]) { 247 const Cubic aCubic = {{a[0].fX, a[0].fY}, {a[1].fX, a[1].fY}, 248 {a[2].fX, a[2].fY}, {a[3].fX, a[3].fY}}; 249 Cubic dst; 250 sub_divide(aCubic, startT, endT, dst); 251 sub[0].fX = SkDoubleToScalar(dst[0].x); 252 sub[0].fY = SkDoubleToScalar(dst[0].y); 253 sub[1].fX = SkDoubleToScalar(dst[1].x); 254 sub[1].fY = SkDoubleToScalar(dst[1].y); 255 sub[2].fX = SkDoubleToScalar(dst[2].x); 256 sub[2].fY = SkDoubleToScalar(dst[2].y); 257 sub[3].fX = SkDoubleToScalar(dst[3].x); 258 sub[3].fY = SkDoubleToScalar(dst[3].y); 259} 260 261static void (* const SegmentSubDivide[])(const SkPoint [], double , double , 262 SkPoint []) = { 263 NULL, 264 LineSubDivide, 265 QuadSubDivide, 266 CubicSubDivide 267}; 268 269#if DEBUG_UNUSED 270static void QuadSubBounds(const SkPoint a[3], double startT, double endT, 271 SkRect& bounds) { 272 SkPoint dst[3]; 273 QuadSubDivide(a, startT, endT, dst); 274 bounds.fLeft = bounds.fRight = dst[0].fX; 275 bounds.fTop = bounds.fBottom = dst[0].fY; 276 for (int index = 1; index < 3; ++index) { 277 bounds.growToInclude(dst[index].fX, dst[index].fY); 278 } 279} 280 281static void CubicSubBounds(const SkPoint a[4], double startT, double endT, 282 SkRect& bounds) { 283 SkPoint dst[4]; 284 CubicSubDivide(a, startT, endT, dst); 285 bounds.fLeft = bounds.fRight = dst[0].fX; 286 bounds.fTop = bounds.fBottom = dst[0].fY; 287 for (int index = 1; index < 4; ++index) { 288 bounds.growToInclude(dst[index].fX, dst[index].fY); 289 } 290} 291#endif 292 293static SkPath::Verb QuadReduceOrder(const SkPoint a[3], 294 SkTDArray<SkPoint>& reducePts) { 295 const Quadratic aQuad = {{a[0].fX, a[0].fY}, {a[1].fX, a[1].fY}, 296 {a[2].fX, a[2].fY}}; 297 Quadratic dst; 298 int order = reduceOrder(aQuad, dst); 299 if (order == 3) { 300 return SkPath::kQuad_Verb; 301 } 302 for (int index = 0; index < order; ++index) { 303 SkPoint* pt = reducePts.append(); 304 pt->fX = SkDoubleToScalar(dst[index].x); 305 pt->fY = SkDoubleToScalar(dst[index].y); 306 } 307 return (SkPath::Verb) (order - 1); 308} 309 310static SkPath::Verb CubicReduceOrder(const SkPoint a[4], 311 SkTDArray<SkPoint>& reducePts) { 312 const Cubic aCubic = {{a[0].fX, a[0].fY}, {a[1].fX, a[1].fY}, 313 {a[2].fX, a[2].fY}, {a[3].fX, a[3].fY}}; 314 Cubic dst; 315 int order = reduceOrder(aCubic, dst, kReduceOrder_QuadraticsAllowed); 316 if (order == 4) { 317 return SkPath::kCubic_Verb; 318 } 319 for (int index = 0; index < order; ++index) { 320 SkPoint* pt = reducePts.append(); 321 pt->fX = SkDoubleToScalar(dst[index].x); 322 pt->fY = SkDoubleToScalar(dst[index].y); 323 } 324 return (SkPath::Verb) (order - 1); 325} 326 327static bool QuadIsLinear(const SkPoint a[3]) { 328 const Quadratic aQuad = {{a[0].fX, a[0].fY}, {a[1].fX, a[1].fY}, 329 {a[2].fX, a[2].fY}}; 330 return isLinear(aQuad, 0, 2); 331} 332 333static bool CubicIsLinear(const SkPoint a[4]) { 334 const Cubic aCubic = {{a[0].fX, a[0].fY}, {a[1].fX, a[1].fY}, 335 {a[2].fX, a[2].fY}, {a[3].fX, a[3].fY}}; 336 return isLinear(aCubic, 0, 3); 337} 338 339static SkScalar LineLeftMost(const SkPoint a[2], double startT, double endT) { 340 const _Line aLine = {{a[0].fX, a[0].fY}, {a[1].fX, a[1].fY}}; 341 double x[2]; 342 xy_at_t(aLine, startT, x[0], *(double*) 0); 343 xy_at_t(aLine, endT, x[1], *(double*) 0); 344 return SkMinScalar((float) x[0], (float) x[1]); 345} 346 347static SkScalar QuadLeftMost(const SkPoint a[3], double startT, double endT) { 348 const Quadratic aQuad = {{a[0].fX, a[0].fY}, {a[1].fX, a[1].fY}, 349 {a[2].fX, a[2].fY}}; 350 return (float) leftMostT(aQuad, startT, endT); 351} 352 353static SkScalar CubicLeftMost(const SkPoint a[4], double startT, double endT) { 354 const Cubic aCubic = {{a[0].fX, a[0].fY}, {a[1].fX, a[1].fY}, 355 {a[2].fX, a[2].fY}, {a[3].fX, a[3].fY}}; 356 return (float) leftMostT(aCubic, startT, endT); 357} 358 359static SkScalar (* const SegmentLeftMost[])(const SkPoint [], double , double) = { 360 NULL, 361 LineLeftMost, 362 QuadLeftMost, 363 CubicLeftMost 364}; 365 366#if DEBUG_UNUSED 367static bool IsCoincident(const SkPoint a[2], const SkPoint& above, 368 const SkPoint& below) { 369 const _Line aLine = {{a[0].fX, a[0].fY}, {a[1].fX, a[1].fY}}; 370 const _Line bLine = {{above.fX, above.fY}, {below.fX, below.fY}}; 371 return implicit_matches_ulps(aLine, bLine, 32); 372} 373#endif 374 375class Segment; 376 377// sorting angles 378// given angles of {dx dy ddx ddy dddx dddy} sort them 379class Angle { 380public: 381 // FIXME: this is bogus for quads and cubics 382 // if the quads and cubics' line from end pt to ctrl pt are coincident, 383 // there's no obvious way to determine the curve ordering from the 384 // derivatives alone. In particular, if one quadratic's coincident tangent 385 // is longer than the other curve, the final control point can place the 386 // longer curve on either side of the shorter one. 387 // Using Bezier curve focus http://cagd.cs.byu.edu/~tom/papers/bezclip.pdf 388 // may provide some help, but nothing has been figured out yet. 389 bool operator<(const Angle& rh) const { 390 if ((fDy < 0) ^ (rh.fDy < 0)) { 391 return fDy < 0; 392 } 393 if (fDy == 0 && rh.fDy == 0 && fDx != rh.fDx) { 394 return fDx < rh.fDx; 395 } 396 SkScalar cmp = fDx * rh.fDy - rh.fDx * fDy; 397 if (cmp) { 398 return cmp < 0; 399 } 400 if ((fDDy < 0) ^ (rh.fDDy < 0)) { 401 return fDDy < 0; 402 } 403 if (fDDy == 0 && rh.fDDy == 0 && fDDx != rh.fDDx) { 404 return fDDx < rh.fDDx; 405 } 406 cmp = fDDx * rh.fDDy - rh.fDDx * fDDy; 407 if (cmp) { 408 return cmp < 0; 409 } 410 if ((fDDDy < 0) ^ (rh.fDDDy < 0)) { 411 return fDDDy < 0; 412 } 413 if (fDDDy == 0 && rh.fDDDy == 0) { 414 return fDDDx < rh.fDDDx; 415 } 416 return fDDDx * rh.fDDDy < rh.fDDDx * fDDDy; 417 } 418 419 int end() const { 420 return fEnd; 421 } 422 423 bool isHorizontal() const { 424 return fDy == 0 && fDDy == 0 && fDDDy == 0; 425 } 426 427 // since all angles share a point, this needs to know which point 428 // is the common origin, i.e., whether the center is at pts[0] or pts[verb] 429 // practically, this should only be called by addAngle 430 void set(const SkPoint* pts, SkPath::Verb verb, Segment* segment, 431 int start, int end) { 432 SkASSERT(start != end); 433 fSegment = segment; 434 fStart = start; 435 fEnd = end; 436 fDx = pts[1].fX - pts[0].fX; // b - a 437 fDy = pts[1].fY - pts[0].fY; 438 if (verb == SkPath::kLine_Verb) { 439 fDDx = fDDy = fDDDx = fDDDy = 0; 440 return; 441 } 442 fDDx = pts[2].fX - pts[1].fX - fDx; // a - 2b + c 443 fDDy = pts[2].fY - pts[1].fY - fDy; 444 if (verb == SkPath::kQuad_Verb) { 445 fDDDx = fDDDy = 0; 446 return; 447 } 448 fDDDx = pts[3].fX + 3 * (pts[1].fX - pts[2].fX) - pts[0].fX; 449 fDDDy = pts[3].fY + 3 * (pts[1].fY - pts[2].fY) - pts[0].fY; 450 } 451 452 // noncoincident quads/cubics may have the same initial angle 453 // as lines, so must sort by derivatives as well 454 // if flatness turns out to be a reasonable way to sort, use the below: 455 void setFlat(const SkPoint* pts, SkPath::Verb verb, Segment* segment, 456 int start, int end) { 457 fSegment = segment; 458 fStart = start; 459 fEnd = end; 460 fDx = pts[1].fX - pts[0].fX; // b - a 461 fDy = pts[1].fY - pts[0].fY; 462 if (verb == SkPath::kLine_Verb) { 463 fDDx = fDDy = fDDDx = fDDDy = 0; 464 return; 465 } 466 if (verb == SkPath::kQuad_Verb) { 467 int uplsX = FloatAsInt(pts[2].fX - pts[1].fY - fDx); 468 int uplsY = FloatAsInt(pts[2].fY - pts[1].fY - fDy); 469 int larger = std::max(abs(uplsX), abs(uplsY)); 470 int shift = 0; 471 double flatT; 472 SkPoint ddPt; // FIXME: get rid of copy (change fDD_ to point) 473 LineParameters implicitLine; 474 _Line tangent = {{pts[0].fX, pts[0].fY}, {pts[1].fX, pts[1].fY}}; 475 implicitLine.lineEndPoints(tangent); 476 implicitLine.normalize(); 477 while (larger > UlpsEpsilon * 1024) { 478 larger >>= 2; 479 ++shift; 480 flatT = 0.5 / (1 << shift); 481 QuadXYAtT(pts, flatT, &ddPt); 482 _Point _pt = {ddPt.fX, ddPt.fY}; 483 double distance = implicitLine.pointDistance(_pt); 484 if (approximately_zero(distance)) { 485 SkDebugf("%s ulps too small %1.9g\n", __FUNCTION__, distance); 486 break; 487 } 488 } 489 flatT = 0.5 / (1 << shift); 490 QuadXYAtT(pts, flatT, &ddPt); 491 fDDx = ddPt.fX - pts[0].fX; 492 fDDy = ddPt.fY - pts[0].fY; 493 SkASSERT(fDDx != 0 || fDDy != 0); 494 fDDDx = fDDDy = 0; 495 return; 496 } 497 SkASSERT(0); // FIXME: add cubic case 498 } 499 500 Segment* segment() const { 501 return fSegment; 502 } 503 504 int sign() const { 505 return SkSign32(fStart - fEnd); 506 } 507 508 bool slopeEquals(const Angle& rh) const { 509 return fDx == rh.fDx && fDy == rh.fDy; 510 511 } 512 513 int start() const { 514 return fStart; 515 } 516 517private: 518 SkScalar fDx; 519 SkScalar fDy; 520 SkScalar fDDx; 521 SkScalar fDDy; 522 SkScalar fDDDx; 523 SkScalar fDDDy; 524 Segment* fSegment; 525 int fStart; 526 int fEnd; 527}; 528 529static void sortAngles(SkTDArray<Angle>& angles, SkTDArray<Angle*>& angleList) { 530 int angleCount = angles.count(); 531 int angleIndex; 532 angleList.setReserve(angleCount); 533 for (angleIndex = 0; angleIndex < angleCount; ++angleIndex) { 534 *angleList.append() = &angles[angleIndex]; 535 } 536 QSort<Angle>(angleList.begin(), angleList.end() - 1); 537} 538 539// Bounds, unlike Rect, does not consider a vertical line to be empty. 540struct Bounds : public SkRect { 541 static bool Intersects(const Bounds& a, const Bounds& b) { 542 return a.fLeft <= b.fRight && b.fLeft <= a.fRight && 543 a.fTop <= b.fBottom && b.fTop <= a.fBottom; 544 } 545 546 bool isEmpty() { 547 return fLeft > fRight || fTop > fBottom 548 || fLeft == fRight && fTop == fBottom 549 || isnan(fLeft) || isnan(fRight) 550 || isnan(fTop) || isnan(fBottom); 551 } 552 553 void setCubicBounds(const SkPoint a[4]) { 554 _Rect dRect; 555 Cubic cubic = {{a[0].fX, a[0].fY}, {a[1].fX, a[1].fY}, 556 {a[2].fX, a[2].fY}, {a[3].fX, a[3].fY}}; 557 dRect.setBounds(cubic); 558 set((float) dRect.left, (float) dRect.top, (float) dRect.right, 559 (float) dRect.bottom); 560 } 561 562 void setQuadBounds(const SkPoint a[3]) { 563 const Quadratic quad = {{a[0].fX, a[0].fY}, {a[1].fX, a[1].fY}, 564 {a[2].fX, a[2].fY}}; 565 _Rect dRect; 566 dRect.setBounds(quad); 567 set((float) dRect.left, (float) dRect.top, (float) dRect.right, 568 (float) dRect.bottom); 569 } 570}; 571 572struct Span { 573 double fT; 574 Segment* fOther; 575 double fOtherT; // value at fOther[fOtherIndex].fT 576 mutable SkPoint const * fPt; // lazily computed as needed 577 int fOtherIndex; // can't be used during intersection 578 int fWinding; // accumulated from contours surrounding this one 579 // OPTIMIZATION: coincident needs only 2 bits (values are -1, 0, 1) 580 int fCoincident; // -1 start of coincidence, 0 no coincidence, 1 end 581 bool fDone; // if set, this span to next higher T has been processed 582}; 583 584class Segment { 585public: 586 Segment() { 587#if DEBUG_DUMP 588 fID = ++gSegmentID; 589#endif 590 } 591 592 void addAngle(SkTDArray<Angle>& angles, int start, int end) { 593 SkASSERT(start != end); 594 SkPoint edge[4]; 595 (*SegmentSubDivide[fVerb])(fPts, fTs[start].fT, fTs[end].fT, edge); 596 Angle* angle = angles.append(); 597 angle->set(edge, fVerb, this, start, end); 598 } 599 600 void addCubic(const SkPoint pts[4]) { 601 init(pts, SkPath::kCubic_Verb); 602 fBounds.setCubicBounds(pts); 603 } 604 605 // FIXME: this needs to defer add for aligned consecutive line segments 606 SkPoint addCurveTo(int start, int end, SkPath& path) { 607 SkPoint edge[4]; 608 (*SegmentSubDivide[fVerb])(fPts, fTs[start].fT, fTs[end].fT, edge); 609 #if DEBUG_PATH_CONSTRUCTION 610 SkDebugf("%s %s (%1.9g,%1.9g)", __FUNCTION__, 611 kLVerbStr[fVerb], edge[1].fX, edge[1].fY); 612 if (fVerb > 1) { 613 SkDebugf(" (%1.9g,%1.9g)", edge[2].fX, edge[2].fY); 614 } 615 if (fVerb > 2) { 616 SkDebugf(" (%1.9g,%1.9g)", edge[3].fX, edge[3].fY); 617 } 618 SkDebugf("\n"); 619 #endif 620 switch (fVerb) { 621 case SkPath::kLine_Verb: 622 path.lineTo(edge[1].fX, edge[1].fY); 623 break; 624 case SkPath::kQuad_Verb: 625 path.quadTo(edge[1].fX, edge[1].fY, edge[2].fX, edge[2].fY); 626 break; 627 case SkPath::kCubic_Verb: 628 path.cubicTo(edge[1].fX, edge[1].fY, edge[2].fX, edge[2].fY, 629 edge[3].fX, edge[3].fY); 630 break; 631 } 632 return edge[fVerb]; 633 } 634 635 void addLine(const SkPoint pts[2]) { 636 init(pts, SkPath::kLine_Verb); 637 fBounds.set(pts, 2); 638 } 639 640 const SkPoint& addMoveTo(int tIndex, SkPath& path) { 641 const SkPoint& pt = xyAtT(&fTs[tIndex]); 642 #if DEBUG_PATH_CONSTRUCTION 643 SkDebugf("%s (%1.9g,%1.9g)\n", __FUNCTION__, pt.fX, pt.fY); 644 #endif 645 path.moveTo(pt.fX, pt.fY); 646 return pt; 647 } 648 649 // add 2 to edge or out of range values to get T extremes 650 void addOtherT(int index, double otherT, int otherIndex) { 651 Span& span = fTs[index]; 652 span.fOtherT = otherT; 653 span.fOtherIndex = otherIndex; 654 } 655 656 void addQuad(const SkPoint pts[3]) { 657 init(pts, SkPath::kQuad_Verb); 658 fBounds.setQuadBounds(pts); 659 } 660 661 // edges are sorted by T, then by coincidence 662 int addT(double newT, Segment& other, int coincident) { 663 // FIXME: in the pathological case where there is a ton of intercepts, 664 // binary search? 665 int insertedAt = -1; 666 Span* span; 667 size_t tCount = fTs.count(); 668 for (size_t idx2 = 0; idx2 < tCount; ++idx2) { 669 // OPTIMIZATION: if there are three or more identical Ts, then 670 // the fourth and following could be further insertion-sorted so 671 // that all the edges are clockwise or counterclockwise. 672 // This could later limit segment tests to the two adjacent 673 // neighbors, although it doesn't help with determining which 674 // circular direction to go in. 675 if (newT < fTs[idx2].fT || (newT == fTs[idx2].fT && 676 coincident <= fTs[idx2].fCoincident)) { 677 insertedAt = idx2; 678 span = fTs.insert(idx2); 679 goto finish; 680 } 681 } 682 insertedAt = tCount; 683 span = fTs.append(); 684finish: 685 span->fT = newT; 686 span->fOther = &other; 687 span->fPt = NULL; 688 span->fWinding = 0; 689 if (span->fDone = newT == 1) { 690 ++fDoneSpans; 691 } 692 span->fCoincident = coincident; 693 fCoincident |= coincident; // OPTIMIZATION: ever used? 694 return insertedAt; 695 } 696 697 void addTwoAngles(int start, int end, SkTDArray<Angle>& angles) { 698 // add edge leading into junction 699 addAngle(angles, end, start); 700 // add edge leading away from junction 701 int step = SkSign32(end - start); 702 int tIndex = nextSpan(end, step); 703 if (tIndex >= 0) { 704 addAngle(angles, end, tIndex); 705 } 706 } 707 708 const Bounds& bounds() const { 709 return fBounds; 710 } 711 712 void buildAngles(int index, SkTDArray<Angle>& angles) const { 713 SkASSERT(!done()); 714 double referenceT = fTs[index].fT; 715 int lesser = index; 716 while (--lesser >= 0 && referenceT == fTs[lesser].fT) { 717 buildAnglesInner(lesser, angles); 718 } 719 do { 720 buildAnglesInner(index, angles); 721 } while (++index < fTs.count() && referenceT == fTs[index].fT); 722 } 723 724 void buildAnglesInner(int index, SkTDArray<Angle>& angles) const { 725 Span* span = &fTs[index]; 726 Segment* other = span->fOther; 727 // if there is only one live crossing, and no coincidence, continue 728 // in the same direction 729 // if there is coincidence, the only choice may be to reverse direction 730 // find edge on either side of intersection 731 int oIndex = span->fOtherIndex; 732 // if done == -1, prior span has already been processed 733 int step = 1; 734 int next = other->nextSpanEnd(oIndex, step); 735 if (next < 0) { 736 step = -step; 737 next = other->nextSpanEnd(oIndex, step); 738 } 739 oIndex = other->coincidentEnd(oIndex, -step); 740 // add candidate into and away from junction 741 other->addTwoAngles(next, oIndex, angles); 742 } 743 744 // figure out if the segment's ascending T goes clockwise or not 745 // not enough context to write this as shown 746 // instead, add all segments meeting at the top 747 // sort them using buildAngleList 748 // find the first in the sort 749 // see if ascendingT goes to top 750 bool clockwise(int /* tIndex */) const { 751 SkASSERT(0); // incomplete 752 return false; 753 } 754 755 static bool Coincident(const Angle* current, const Angle* next) { 756 const Segment* segment = current->segment(); 757 const Span& span = segment->fTs[current->start()]; 758 if (!span.fCoincident) { 759 return false; 760 } 761 const Segment* nextSegment = next->segment(); 762 const Span& nextSpan = nextSegment->fTs[next->start()]; 763 if (!nextSpan.fCoincident) { 764 return false; 765 } 766 // use angle dx/dy instead of other since 3 or more may be coincident 767 return current->slopeEquals(*next); 768 } 769 770 static bool CoincidentCancels(const Angle* current, const Angle* next) { 771 return SkSign32(current->start() - current->end()) 772 != SkSign32(next->start() - next->end()); 773 } 774 775 int coincidentEnd(int from, int step) const { 776 double fromT = fTs[from].fT; 777 int count = fTs.count(); 778 int to = from; 779 while (step > 0 ? ++to < count : --to >= 0) { 780 const Span& span = fTs[to]; 781 if (fromT != span.fT) { 782 // FIXME: we assume that if the T changes, we don't care about 783 // coincident -- but in nextSpan, we require that both the T 784 // and actual loc change to represent a span. This asymettry may 785 // be OK or may be trouble -- if trouble, probably will need to 786 // detect coincidence earlier or sort differently 787 break; 788 } 789 if (span.fCoincident == step) { 790 return to; 791 } 792 } 793 return from; 794 } 795 796 bool done() const { 797 SkASSERT(fDoneSpans <= fTs.count()); 798 return fDoneSpans == fTs.count(); 799 } 800 801 // start is the index of the beginning T of this edge 802 // it is guaranteed to have an end which describes a non-zero length (?) 803 // winding -1 means ccw, 1 means cw 804 // step is in/out -1 or 1 805 // spanIndex is returned 806 Segment* findNext(int winding, const int startIndex, const int endIndex, 807 int& nextStart, int& nextEnd) { 808 SkASSERT(startIndex != endIndex); 809 int count = fTs.count(); 810 SkASSERT(startIndex < endIndex ? startIndex < count - 1 811 : startIndex > 0); 812 813 int step = SkSign32(endIndex - startIndex); 814 int end = nextSpanEnd(startIndex, step); 815 SkASSERT(end >= 0); 816 817 // preflight for coincidence -- if present, it may change winding 818 // considerations and whether reversed edges can be followed 819 820 // Discard opposing direction candidates if no coincidence was found. 821 Span* endSpan = &fTs[end]; 822 Segment* other; 823 if (isSimple(end, step)) { 824 // mark the smaller of startIndex, endIndex done, and all adjacent 825 // spans with the same T value (but not 'other' spans) 826 markDone(SkMin32(startIndex, endIndex), winding); 827 // move in winding direction until edge in correct direction 828 // balance wrong direction edges before finding correct one 829 // this requres that the intersection is angularly sorted 830 // for a single intersection, special case -- choose the opposite 831 // edge that steps the same 832 other = endSpan->fOther; 833 nextStart = endSpan->fOtherIndex; 834 nextEnd = nextStart + step; 835 SkASSERT(step < 0 ? nextEnd >= 0 : nextEnd < other->fTs.count()); 836 return other; 837 } 838 // more than one viable candidate -- measure angles to find best 839 SkTDArray<Angle> angles; 840 SkASSERT(startIndex - endIndex != 0); 841 SkASSERT((startIndex - endIndex < 0) ^ (step < 0)); 842 addTwoAngles(startIndex, end, angles); 843 buildAngles(end, angles); 844 SkTDArray<Angle*> sorted; 845 sortAngles(angles, sorted); 846 // find the starting edge 847 int firstIndex = -1; 848 int angleCount = angles.count(); 849 int angleIndex; 850 const Angle* angle; 851 for (angleIndex = 0; angleIndex < angleCount; ++angleIndex) { 852 angle = sorted[angleIndex]; 853 if (angle->segment() == this && angle->start() == end && 854 angle->end() == startIndex) { 855 firstIndex = angleIndex; 856 break; 857 } 858 } 859 // back up if prior edge is coincident with firstIndex 860 int prior = firstIndex; 861 do { 862 if (--prior < 0) { 863 prior = angleCount - 1; 864 } 865 SkASSERT(prior != angleIndex); 866 if (!Coincident(sorted[prior], sorted[firstIndex])) { 867 break; 868 } 869 firstIndex = prior; 870 angle = sorted[prior]; 871 } while (true); 872 873 // put some thought into handling coincident edges 874 // 1) defer the initial moveTo/curveTo until we know that firstIndex 875 // isn't coincident (although maybe findTop could tell us that) 876 // 2) allow the below to mark and skip coincident pairs 877 // 3) return something (null?) if all segments cancel each other out 878 // 4) if coincident edges don't cancel, figure out which to return (follow) 879 880 SkASSERT(firstIndex >= 0); 881 int startWinding = winding; 882 int nextIndex = firstIndex; 883 const Angle* nextAngle; 884 Segment* nextSegment; 885 do { 886 if (++nextIndex == angleCount) { 887 nextIndex = 0; 888 } 889 SkASSERT(nextIndex != firstIndex); // should never wrap around 890 nextAngle = sorted[nextIndex]; 891 int maxWinding = winding; 892 winding -= nextAngle->sign(); 893 nextSegment = nextAngle->segment(); 894 if (nextSegment->done()) { 895 if (!winding) { 896 break; 897 } 898 continue; 899 } 900 bool pairCoincides = Coincident(angle, nextAngle); 901 bool pairCancels = pairCoincides 902 && CoincidentCancels(angle, nextAngle); 903 if (pairCancels) { 904 angle->segment()->markAndChaseCoincident(angle->start(), 905 angle->end(), nextSegment); 906 return NULL; 907 } 908 if (!winding) { 909 break; 910 } 911 if (pairCoincides) { 912 bool markNext = abs(maxWinding) < abs(winding); 913 if (markNext) { 914 nextSegment->markDone(SkMin32(nextAngle->start(), 915 nextAngle->end()), winding); 916 } else { 917 angle->segment()->markDone(SkMin32(angle->start(), 918 angle->end()), maxWinding); 919 } 920 } 921 // if the winding is non-zero, nextAngle does not connect to 922 // current chain. If we haven't done so already, mark the angle 923 // as done, record the winding value, and mark connected unambiguous 924 // segments as well. 925 else if (nextSegment->winding(nextAngle) == 0) { 926 if (abs(maxWinding) < abs(winding)) { 927 maxWinding = winding; 928 } 929 nextSegment->markAndChaseWinding(nextAngle, maxWinding); 930 } 931 } while ((angle = nextAngle)); // always true 932 markDone(SkMin32(startIndex, endIndex), startWinding); 933 nextStart = nextAngle->start(); 934 nextEnd = nextAngle->end(); 935 return nextSegment; 936 } 937 938 939 // so the span needs to contain the pairing info found here 940 // this should include the winding computed for the edge, and 941 // what edge it connects to, and whether it is discarded 942 // (maybe discarded == abs(winding) > 1) ? 943 // only need derivatives for duration of sorting, add a new struct 944 // for pairings, remove extra spans that have zero length and 945 // reference an unused other 946 // for coincident, the last span on the other may be marked done 947 // (always?) 948 949 // if loop is exhausted, contour may be closed. 950 // FIXME: pass in close point so we can check for closure 951 952 // given a segment, and a sense of where 'inside' is, return the next 953 // segment. If this segment has an intersection, or ends in multiple 954 // segments, find the mate that continues the outside. 955 // note that if there are multiples, but no coincidence, we can limit 956 // choices to connections in the correct direction 957 958 // mark found segments as done 959 960 // FIXME: this is tricky code; needs its own unit test 961 void findTooCloseToCall(int /* winding */ ) { // FIXME: winding should be considered 962 int count = fTs.count(); 963 if (count < 3) { // require t=0, x, 1 at minimum 964 return; 965 } 966 int matchIndex = 0; 967 int moCount; 968 Span* match; 969 Segment* mOther; 970 do { 971 match = &fTs[matchIndex]; 972 mOther = match->fOther; 973 moCount = mOther->fTs.count(); 974 if (moCount >= 3) { 975 break; 976 } 977 if (++matchIndex >= count) { 978 return; 979 } 980 } while (true); // require t=0, x, 1 at minimum 981 // OPTIMIZATION: defer matchPt until qualifying toCount is found? 982 const SkPoint* matchPt = &xyAtT(match); 983 // look for a pair of nearby T values that map to the same (x,y) value 984 // if found, see if the pair of other segments share a common point. If 985 // so, the span from here to there is coincident. 986 for (int index = matchIndex + 1; index < count; ++index) { 987 Span* test = &fTs[index]; 988 if (test->fCoincident) { 989 continue; 990 } 991 Segment* tOther = test->fOther; 992 int toCount = tOther->fTs.count(); 993 if (toCount < 3) { // require t=0, x, 1 at minimum 994 continue; 995 } 996 const SkPoint* testPt = &xyAtT(test); 997 if (*matchPt != *testPt) { 998 matchIndex = index; 999 moCount = toCount; 1000 match = test; 1001 mOther = tOther; 1002 matchPt = testPt; 1003 continue; 1004 } 1005 int moStart = -1; 1006 int moEnd = -1; 1007 double moStartT, moEndT; 1008 for (int moIndex = 0; moIndex < moCount; ++moIndex) { 1009 Span& moSpan = mOther->fTs[moIndex]; 1010 if (moSpan.fCoincident) { 1011 continue; 1012 } 1013 if (moSpan.fOther == this) { 1014 if (moSpan.fOtherT == match->fT) { 1015 moStart = moIndex; 1016 moStartT = moSpan.fT; 1017 } 1018 continue; 1019 } 1020 if (moSpan.fOther == tOther) { 1021 SkASSERT(moEnd == -1); 1022 moEnd = moIndex; 1023 moEndT = moSpan.fT; 1024 } 1025 } 1026 if (moStart < 0 || moEnd < 0) { 1027 continue; 1028 } 1029 // FIXME: if moStartT, moEndT are initialized to NaN, can skip this test 1030 if (moStartT == moEndT) { 1031 continue; 1032 } 1033 int toStart = -1; 1034 int toEnd = -1; 1035 double toStartT, toEndT; 1036 for (int toIndex = 0; toIndex < toCount; ++toIndex) { 1037 Span& toSpan = tOther->fTs[toIndex]; 1038 if (toSpan.fOther == this) { 1039 if (toSpan.fOtherT == test->fT) { 1040 toStart = toIndex; 1041 toStartT = toSpan.fT; 1042 } 1043 continue; 1044 } 1045 if (toSpan.fOther == mOther && toSpan.fOtherT == moEndT) { 1046 SkASSERT(toEnd == -1); 1047 toEnd = toIndex; 1048 toEndT = toSpan.fT; 1049 } 1050 } 1051 // FIXME: if toStartT, toEndT are initialized to NaN, can skip this test 1052 if (toStart <= 0 || toEnd <= 0) { 1053 continue; 1054 } 1055 if (toStartT == toEndT) { 1056 continue; 1057 } 1058 // test to see if the segment between there and here is linear 1059 if (!mOther->isLinear(moStart, moEnd) 1060 || !tOther->isLinear(toStart, toEnd)) { 1061 continue; 1062 } 1063 // FIXME: may need to resort if we depend on coincidence first, last 1064 mOther->fTs[moStart].fCoincident = -1; 1065 tOther->fTs[toStart].fCoincident = -1; 1066 mOther->fTs[moEnd].fCoincident = 1; 1067 tOther->fTs[toEnd].fCoincident = 1; 1068 } 1069 } 1070 1071 // OPTIMIZATION : for a pair of lines, can we compute points at T (cached) 1072 // and use more concise logic like the old edge walker code? 1073 // FIXME: this needs to deal with coincident edges 1074 Segment* findTop(int& tIndex, int& endIndex) { 1075 // iterate through T intersections and return topmost 1076 // topmost tangent from y-min to first pt is closer to horizontal 1077 SkASSERT(!done()); 1078 int firstT; 1079 int lastT; 1080 int firstCoinT; 1081 SkPoint topPt; 1082 topPt.fY = SK_ScalarMax; 1083 int count = fTs.count(); 1084 bool lastDone = true; 1085 for (int index = 0; index < count; ++index) { 1086 const Span& span = fTs[index]; 1087 if (!span.fDone || !lastDone) { 1088 const SkPoint& intercept = xyAtT(&span); 1089 if (topPt.fY > intercept.fY || (topPt.fY == intercept.fY 1090 && topPt.fX > intercept.fX)) { 1091 topPt = intercept; 1092 firstT = lastT = firstCoinT = index; 1093 } else if (topPt == intercept) { 1094 lastT = index; 1095 if (span.fCoincident) { 1096 firstCoinT = index; 1097 } 1098 } 1099 } 1100 lastDone = span.fDone; 1101 } 1102 // if there's only a pair of segments, go with the endpoint chosen above 1103 if (firstT == lastT) { 1104 tIndex = firstT; 1105 endIndex = firstT > 0 ? tIndex - 1 : tIndex + 1; 1106 return this; 1107 } 1108 // sort the edges to find the leftmost 1109 int step = 1; 1110 int end = nextSpan(firstT, step); 1111 if (end == -1) { 1112 step = -1; 1113 end = nextSpan(firstT, step); 1114 SkASSERT(end != -1); 1115 } 1116 // if the topmost T is not on end, or is three-way or more, find left 1117 // look for left-ness from tLeft to firstT (matching y of other) 1118 SkTDArray<Angle> angles; 1119 SkASSERT(firstT - end != 0); 1120 addTwoAngles(end, firstCoinT, angles); 1121 buildAngles(firstT, angles); 1122 SkTDArray<Angle*> sorted; 1123 sortAngles(angles, sorted); 1124 // skip edges that have already been processed 1125 firstT = -1; 1126 Segment* leftSegment; 1127 do { 1128 const Angle* angle = sorted[++firstT]; 1129 leftSegment = angle->segment(); 1130 tIndex = angle->end(); 1131 endIndex = angle->start(); 1132 } while (leftSegment->fTs[SkMin32(tIndex, endIndex)].fDone); 1133 return leftSegment; 1134 } 1135 1136 // FIXME: not crazy about this 1137 // when the intersections are performed, the other index is into an 1138 // incomplete array. as the array grows, the indices become incorrect 1139 // while the following fixes the indices up again, it isn't smart about 1140 // skipping segments whose indices are already correct 1141 // assuming we leave the code that wrote the index in the first place 1142 void fixOtherTIndex() { 1143 int iCount = fTs.count(); 1144 for (int i = 0; i < iCount; ++i) { 1145 Span& iSpan = fTs[i]; 1146 double oT = iSpan.fOtherT; 1147 Segment* other = iSpan.fOther; 1148 int oCount = other->fTs.count(); 1149 for (int o = 0; o < oCount; ++o) { 1150 Span& oSpan = other->fTs[o]; 1151 if (oT == oSpan.fT && this == oSpan.fOther) { 1152 iSpan.fOtherIndex = o; 1153 } 1154 } 1155 } 1156 } 1157 1158 // OPTIMIZATION: uses tail recursion. Unwise? 1159 void innerCoincidentChase(int step, Segment* other) { 1160 // find other at index 1161 SkASSERT(!done()); 1162 const Span* start = NULL; 1163 const Span* end = NULL; 1164 int index, startIndex, endIndex; 1165 int count = fTs.count(); 1166 for (index = 0; index < count; ++index) { 1167 const Span& span = fTs[index]; 1168 if (!span.fCoincident || span.fOther != other) { 1169 continue; 1170 } 1171 if (!start) { 1172 if (span.fDone) { 1173 continue; 1174 } 1175 startIndex = index; 1176 start = &span; 1177 } else { 1178 SkASSERT(!end); 1179 endIndex = index; 1180 end = &span; 1181 } 1182 } 1183 if (!end) { 1184 return; 1185 } 1186 Segment* next; 1187 Segment* nextOther; 1188 if (step < 0) { 1189 next = start->fT == 0 ? NULL : this; 1190 nextOther = other->fTs[start->fOtherIndex].fT == 1 ? NULL : other; 1191 } else { 1192 next = end->fT == 1 ? NULL : this; 1193 nextOther = other->fTs[end->fOtherIndex].fT == 0 ? NULL : other; 1194 } 1195 SkASSERT(!next || !nextOther); 1196 for (index = 0; index < count; ++index) { 1197 const Span& span = fTs[index]; 1198 if (span.fCoincident || span.fOther == other) { 1199 continue; 1200 } 1201 bool checkNext = !next && (step < 0 ? span.fT == 0 1202 && span.fOtherT == 1 : span.fT == 1 && span.fOtherT == 0); 1203 bool checkOther = !nextOther && (step < 0 ? span.fT == start->fT 1204 && span.fOtherT == 0 : span.fT == end->fT && span.fOtherT == 1); 1205 if (!checkNext && !checkOther) { 1206 continue; 1207 } 1208 Segment* oSegment = span.fOther; 1209 if (oSegment->done()) { 1210 continue; 1211 } 1212 int oCount = oSegment->fTs.count(); 1213 for (int oIndex = 0; oIndex < oCount; ++oIndex) { 1214 const Span& oSpan = oSegment->fTs[oIndex]; 1215 if (oSpan.fT > 0 && oSpan.fT < 1) { 1216 continue; 1217 } 1218 if (!oSpan.fCoincident) { 1219 continue; 1220 } 1221 if (checkNext && (oSpan.fT == 0 ^ step < 0)) { 1222 next = oSegment; 1223 checkNext = false; 1224 } 1225 if (checkOther && (oSpan.fT == 1 ^ step < 0)) { 1226 nextOther = oSegment; 1227 checkOther = false; 1228 } 1229 } 1230 } 1231 markDone(SkMin32(startIndex, endIndex), 0); 1232 other->markDone(SkMin32(start->fOtherIndex, end->fOtherIndex), 0); 1233 if (next && nextOther) { 1234 next->innerCoincidentChase(step, nextOther); 1235 } 1236 } 1237 1238 // OPTIMIZATION: uses tail recursion. Unwise? 1239 void innerChase(int index, int step, int winding) { 1240 int end = nextSpan(index, step); 1241 if (multipleSpans(end, step)) { 1242 return; 1243 } 1244 const Span& endSpan = fTs[end]; 1245 Segment* other = endSpan.fOther; 1246 index = endSpan.fOtherIndex; 1247 int otherEnd = other->nextSpan(index, step); 1248 other->innerChase(index, step, winding); 1249 other->markDone(SkMin32(index, otherEnd), winding); 1250 } 1251 1252 void init(const SkPoint pts[], SkPath::Verb verb) { 1253 fPts = pts; 1254 fVerb = verb; 1255 fDoneSpans = 0; 1256 fCoincident = 0; 1257 } 1258 1259 bool intersected() const { 1260 return fTs.count() > 0; 1261 } 1262 1263 bool isLinear(int start, int end) const { 1264 if (fVerb == SkPath::kLine_Verb) { 1265 return true; 1266 } 1267 if (fVerb == SkPath::kQuad_Verb) { 1268 SkPoint qPart[3]; 1269 QuadSubDivide(fPts, fTs[start].fT, fTs[end].fT, qPart); 1270 return QuadIsLinear(qPart); 1271 } else { 1272 SkASSERT(fVerb == SkPath::kCubic_Verb); 1273 SkPoint cPart[4]; 1274 CubicSubDivide(fPts, fTs[start].fT, fTs[end].fT, cPart); 1275 return CubicIsLinear(cPart); 1276 } 1277 } 1278 1279 bool isSimple(int index, int step) const { 1280 int count = fTs.count(); 1281 if (count == 2) { 1282 return true; 1283 } 1284 double spanT = fTs[index].fT; 1285 if (spanT > 0 && spanT < 1) { 1286 return false; 1287 } 1288 if (step < 0) { 1289 const Span& secondSpan = fTs[1]; 1290 if (secondSpan.fT == 0) { 1291 return false; 1292 } 1293 return xyAtT(&fTs[0]) != xyAtT(&secondSpan); 1294 } 1295 const Span& penultimateSpan = fTs[count - 2]; 1296 if (penultimateSpan.fT == 1) { 1297 return false; 1298 } 1299 return xyAtT(&fTs[count - 1]) != xyAtT(&penultimateSpan); 1300 } 1301 1302 bool isHorizontal() const { 1303 return fBounds.fTop == fBounds.fBottom; 1304 } 1305 1306 bool isVertical() const { 1307 return fBounds.fLeft == fBounds.fRight; 1308 } 1309 1310 SkScalar leftMost(int start, int end) const { 1311 return (*SegmentLeftMost[fVerb])(fPts, fTs[start].fT, fTs[end].fT); 1312 } 1313 1314 void markAndChaseCoincident(int index, int endIndex, Segment* other) { 1315 int step = SkSign32(endIndex - index); 1316 innerCoincidentChase(step, other); 1317 } 1318 1319 // this span is excluded by the winding rule -- chase the ends 1320 // as long as they are unambiguous to mark connections as done 1321 // and give them the same winding value 1322 void markAndChaseWinding(const Angle* angle, int winding) { 1323 int index = angle->start(); 1324 int endIndex = angle->end(); 1325 int step = SkSign32(endIndex - index); 1326 innerChase(index, step, winding); 1327 markDone(SkMin32(index, endIndex), winding); 1328 } 1329 1330 // FIXME: this should also mark spans with equal (x,y) 1331 void markDone(int index, int winding) { 1332 SkASSERT(!done()); 1333 double referenceT = fTs[index].fT; 1334 int lesser = index; 1335 while (--lesser >= 0 && referenceT == fTs[lesser].fT) { 1336 Span& span = fTs[lesser]; 1337 // FIXME: this needs to assert that all are not done or one or more are 1338 // coincident 1339 // SkASSERT(!span.fDone || span.fCoincident); 1340 if (span.fDone) { 1341 continue; 1342 } 1343 span.fDone = true; 1344 SkASSERT(!span.fWinding || span.fWinding == winding); 1345 span.fWinding = winding; 1346 fDoneSpans++; 1347 } 1348 do { 1349 Span& span = fTs[index]; 1350 // SkASSERT(!span.fDone || span.fCoincident); 1351 if (span.fDone) { 1352 continue; 1353 } 1354 span.fDone = true; 1355 SkASSERT(!span.fWinding || span.fWinding == winding); 1356 span.fWinding = winding; 1357 fDoneSpans++; 1358 } while (++index < fTs.count() && referenceT == fTs[index].fT); 1359 } 1360 1361 bool multipleSpans(int end, int step) const { 1362 return step > 0 ? ++end < fTs.count() : end > 0; 1363 } 1364 1365 // This has callers for two different situations: one establishes the end 1366 // of the current span, and one establishes the beginning of the next span 1367 // (thus the name). When this is looking for the end of the current span, 1368 // coincidence is found when the beginning Ts contain -step and the end 1369 // contains step. When it is looking for the beginning of the next, the 1370 // first Ts found can be ignored and the last Ts should contain -step. 1371 int nextSpan(int from, int step) const { 1372 const Span& fromSpan = fTs[from]; 1373 int count = fTs.count(); 1374 int to = from; 1375 while (step > 0 ? ++to < count : --to >= 0) { 1376 const Span& span = fTs[to]; 1377 if (fromSpan.fT == span.fT) { 1378 continue; 1379 } 1380 const SkPoint& loc = xyAtT(&span); 1381 const SkPoint& fromLoc = xyAtT(&fromSpan); 1382 if (fromLoc == loc) { 1383 continue; 1384 } 1385 return to; 1386 } 1387 return -1; 1388 } 1389 1390 // once past current span, if step>0, look for coicident==1 1391 // if step<0, look for coincident==-1 1392 int nextSpanEnd(int from, int step) const { 1393 int result = nextSpan(from, step); 1394 if (result < 0) { 1395 return result; 1396 } 1397 return coincidentEnd(result, step); 1398 } 1399 1400 const SkPoint* pts() const { 1401 return fPts; 1402 } 1403 1404 void reset() { 1405 init(NULL, (SkPath::Verb) -1); 1406 fBounds.set(SK_ScalarMax, SK_ScalarMax, SK_ScalarMax, SK_ScalarMax); 1407 fTs.reset(); 1408 } 1409 1410 // OPTIMIZATION: mark as debugging only if used solely by tests 1411 const Span& span(int tIndex) const { 1412 return fTs[tIndex]; 1413 } 1414 1415 // OPTIMIZATION: mark as debugging only if used solely by tests 1416 double t(int tIndex) const { 1417 return fTs[tIndex].fT; 1418 } 1419 1420 void updatePts(const SkPoint pts[]) { 1421 fPts = pts; 1422 } 1423 1424 SkPath::Verb verb() const { 1425 return fVerb; 1426 } 1427 1428 bool winding(const Angle* angle) { 1429 int start = angle->start(); 1430 int end = angle->end(); 1431 int index = SkMin32(start, end); 1432 Span& span = fTs[index]; 1433 return span.fWinding; 1434 } 1435 1436 SkScalar xAtT(double t) const { 1437 SkASSERT(t >= 0 && t <= 1); 1438 return (*SegmentXAtT[fVerb])(fPts, t); 1439 } 1440 1441 const SkPoint& xyAtT(const Span* span) const { 1442 if (!span->fPt) { 1443 if (span->fT == 0) { 1444 span->fPt = &fPts[0]; 1445 } else if (span->fT == 1) { 1446 span->fPt = &fPts[fVerb]; 1447 } else { 1448 SkPoint* pt = fIntersections.append(); 1449 (*SegmentXYAtT[fVerb])(fPts, span->fT, pt); 1450 span->fPt = pt; 1451 } 1452 } 1453 return *span->fPt; 1454 } 1455 1456 SkScalar yAtT(double t) const { 1457 SkASSERT(t >= 0 && t <= 1); 1458 return (*SegmentYAtT[fVerb])(fPts, t); 1459 } 1460 1461#if DEBUG_DUMP 1462 void dump() const { 1463 const char className[] = "Segment"; 1464 const int tab = 4; 1465 for (int i = 0; i < fTs.count(); ++i) { 1466 SkPoint out; 1467 (*SegmentXYAtT[fVerb])(fPts, t(i), &out); 1468 SkDebugf("%*s [%d] %s.fTs[%d]=%1.9g (%1.9g,%1.9g) other=%d" 1469 " otherT=%1.9g winding=%d\n", 1470 tab + sizeof(className), className, fID, 1471 kLVerbStr[fVerb], i, fTs[i].fT, out.fX, out.fY, 1472 fTs[i].fOther->fID, fTs[i].fOtherT, fTs[i].fWinding); 1473 } 1474 SkDebugf("%*s [%d] fBounds=(l:%1.9g, t:%1.9g r:%1.9g, b:%1.9g)", 1475 tab + sizeof(className), className, fID, 1476 fBounds.fLeft, fBounds.fTop, fBounds.fRight, fBounds.fBottom); 1477 } 1478#endif 1479 1480private: 1481 const SkPoint* fPts; 1482 SkPath::Verb fVerb; 1483 Bounds fBounds; 1484 SkTDArray<Span> fTs; // two or more (always includes t=0 t=1) 1485 // OPTIMIZATION:if intersections array is a pointer, the it could only 1486 // be allocated as needed instead of always initialized -- though maybe 1487 // the initialization is lightweight enough that it hardly matters 1488 mutable SkTDArray<SkPoint> fIntersections; 1489 // FIXME: coincident only needs two bits (-1, 0, 1) 1490 int fCoincident; // non-zero if some coincident span inside 1491 int fDoneSpans; // used for quick check that segment is finished 1492#if DEBUG_DUMP 1493 int fID; 1494#endif 1495}; 1496 1497class Contour { 1498public: 1499 Contour() { 1500 reset(); 1501#if DEBUG_DUMP 1502 fID = ++gContourID; 1503#endif 1504 } 1505 1506 bool operator<(const Contour& rh) const { 1507 return fBounds.fTop == rh.fBounds.fTop 1508 ? fBounds.fLeft < rh.fBounds.fLeft 1509 : fBounds.fTop < rh.fBounds.fTop; 1510 } 1511 1512 void addCubic(const SkPoint pts[4]) { 1513 fSegments.push_back().addCubic(pts); 1514 fContainsCurves = true; 1515 } 1516 1517 int addLine(const SkPoint pts[2]) { 1518 fSegments.push_back().addLine(pts); 1519 return fSegments.count(); 1520 } 1521 1522 int addQuad(const SkPoint pts[3]) { 1523 fSegments.push_back().addQuad(pts); 1524 fContainsCurves = true; 1525 return fSegments.count(); 1526 } 1527 1528 const Bounds& bounds() const { 1529 return fBounds; 1530 } 1531 1532 void complete() { 1533 setBounds(); 1534 fContainsIntercepts = false; 1535 } 1536 1537 void containsIntercepts() { 1538 fContainsIntercepts = true; 1539 } 1540 1541 void findTooCloseToCall(int winding) { 1542 int segmentCount = fSegments.count(); 1543 for (int sIndex = 0; sIndex < segmentCount; ++sIndex) { 1544 fSegments[sIndex].findTooCloseToCall(winding); 1545 } 1546 } 1547 1548 void fixOtherTIndex() { 1549 int segmentCount = fSegments.count(); 1550 for (int sIndex = 0; sIndex < segmentCount; ++sIndex) { 1551 fSegments[sIndex].fixOtherTIndex(); 1552 } 1553 } 1554 1555 void reset() { 1556 fSegments.reset(); 1557 fBounds.set(SK_ScalarMax, SK_ScalarMax, SK_ScalarMax, SK_ScalarMax); 1558 fContainsCurves = fContainsIntercepts = false; 1559 } 1560 1561 // OPTIMIZATION: feel pretty uneasy about this. It seems like once again 1562 // we need to sort and walk edges in y, but that on the surface opens the 1563 // same can of worms as before. But then, this is a rough sort based on 1564 // segments' top, and not a true sort, so it could be ameniable to regular 1565 // sorting instead of linear searching. Still feel like I'm missing something 1566 Segment* topSegment() { 1567 int segmentCount = fSegments.count(); 1568 SkASSERT(segmentCount > 0); 1569 int best = -1; 1570 Segment* bestSegment = NULL; 1571 while (++best < segmentCount) { 1572 Segment* testSegment = &fSegments[best]; 1573 if (testSegment->done()) { 1574 continue; 1575 } 1576 bestSegment = testSegment; 1577 break; 1578 } 1579 if (!bestSegment) { 1580 return NULL; 1581 } 1582 SkScalar bestTop = bestSegment->bounds().fTop; 1583 for (int test = best + 1; test < segmentCount; ++test) { 1584 Segment* testSegment = &fSegments[test]; 1585 if (testSegment->done()) { 1586 continue; 1587 } 1588 SkScalar testTop = testSegment->bounds().fTop; 1589 if (bestTop > testTop) { 1590 bestTop = testTop; 1591 bestSegment = testSegment; 1592 } 1593 } 1594 return bestSegment; 1595 } 1596 1597#if DEBUG_DUMP 1598 void dump() { 1599 int i; 1600 const char className[] = "Contour"; 1601 const int tab = 4; 1602 SkDebugf("%s %p (contour=%d)\n", className, this, fID); 1603 for (i = 0; i < fSegments.count(); ++i) { 1604 SkDebugf("%*s.fSegments[%d]:\n", tab + sizeof(className), 1605 className, i); 1606 fSegments[i].dump(); 1607 } 1608 SkDebugf("%*s.fBounds=(l:%1.9g, t:%1.9g r:%1.9g, b:%1.9g)\n", 1609 tab + sizeof(className), className, 1610 fBounds.fLeft, fBounds.fTop, 1611 fBounds.fRight, fBounds.fBottom); 1612 SkDebugf("%*s.fContainsIntercepts=%d\n", tab + sizeof(className), 1613 className, fContainsIntercepts); 1614 SkDebugf("%*s.fContainsCurves=%d\n", tab + sizeof(className), 1615 className, fContainsCurves); 1616 } 1617#endif 1618 1619protected: 1620 void setBounds() { 1621 int count = fSegments.count(); 1622 if (count == 0) { 1623 SkDebugf("%s empty contour\n", __FUNCTION__); 1624 SkASSERT(0); 1625 // FIXME: delete empty contour? 1626 return; 1627 } 1628 fBounds = fSegments.front().bounds(); 1629 for (int index = 1; index < count; ++index) { 1630 fBounds.growToInclude(fSegments[index].bounds()); 1631 } 1632 } 1633 1634public: 1635 SkTArray<Segment> fSegments; // not worth accessor functions? 1636 1637private: 1638 Bounds fBounds; 1639 bool fContainsIntercepts; 1640 bool fContainsCurves; 1641#if DEBUG_DUMP 1642 int fID; 1643#endif 1644}; 1645 1646class EdgeBuilder { 1647public: 1648 1649EdgeBuilder(const SkPath& path, SkTArray<Contour>& contours) 1650 : fPath(path) 1651 , fCurrentContour(NULL) 1652 , fContours(contours) 1653{ 1654#if DEBUG_DUMP 1655 gContourID = 0; 1656 gSegmentID = 0; 1657#endif 1658 walk(); 1659} 1660 1661protected: 1662 1663void complete() { 1664 if (fCurrentContour && fCurrentContour->fSegments.count()) { 1665 fCurrentContour->complete(); 1666 fCurrentContour = NULL; 1667 } 1668} 1669 1670void walk() { 1671 // FIXME:remove once we can access path pts directly 1672 SkPath::RawIter iter(fPath); // FIXME: access path directly when allowed 1673 SkPoint pts[4]; 1674 SkPath::Verb verb; 1675 do { 1676 verb = iter.next(pts); 1677 *fPathVerbs.append() = verb; 1678 if (verb == SkPath::kMove_Verb) { 1679 *fPathPts.append() = pts[0]; 1680 } else if (verb >= SkPath::kLine_Verb && verb <= SkPath::kCubic_Verb) { 1681 fPathPts.append(verb, &pts[1]); 1682 } 1683 } while (verb != SkPath::kDone_Verb); 1684 // FIXME: end of section to remove once path pts are accessed directly 1685 1686 SkPath::Verb reducedVerb; 1687 uint8_t* verbPtr = fPathVerbs.begin(); 1688 const SkPoint* pointsPtr = fPathPts.begin(); 1689 const SkPoint* finalCurveStart = NULL; 1690 const SkPoint* finalCurveEnd = NULL; 1691 while ((verb = (SkPath::Verb) *verbPtr++) != SkPath::kDone_Verb) { 1692 switch (verb) { 1693 case SkPath::kMove_Verb: 1694 complete(); 1695 if (!fCurrentContour) { 1696 fCurrentContour = fContours.push_back_n(1); 1697 finalCurveEnd = pointsPtr++; 1698 *fExtra.append() = -1; // start new contour 1699 } 1700 continue; 1701 case SkPath::kLine_Verb: 1702 // skip degenerate points 1703 if (pointsPtr[-1].fX != pointsPtr[0].fX 1704 || pointsPtr[-1].fY != pointsPtr[0].fY) { 1705 fCurrentContour->addLine(&pointsPtr[-1]); 1706 } 1707 break; 1708 case SkPath::kQuad_Verb: 1709 1710 reducedVerb = QuadReduceOrder(&pointsPtr[-1], fReducePts); 1711 if (reducedVerb == 0) { 1712 break; // skip degenerate points 1713 } 1714 if (reducedVerb == 1) { 1715 *fExtra.append() = 1716 fCurrentContour->addLine(fReducePts.end() - 2); 1717 break; 1718 } 1719 fCurrentContour->addQuad(&pointsPtr[-1]); 1720 break; 1721 case SkPath::kCubic_Verb: 1722 reducedVerb = CubicReduceOrder(&pointsPtr[-1], fReducePts); 1723 if (reducedVerb == 0) { 1724 break; // skip degenerate points 1725 } 1726 if (reducedVerb == 1) { 1727 *fExtra.append() = 1728 fCurrentContour->addLine(fReducePts.end() - 2); 1729 break; 1730 } 1731 if (reducedVerb == 2) { 1732 *fExtra.append() = 1733 fCurrentContour->addQuad(fReducePts.end() - 3); 1734 break; 1735 } 1736 fCurrentContour->addCubic(&pointsPtr[-1]); 1737 break; 1738 case SkPath::kClose_Verb: 1739 SkASSERT(fCurrentContour); 1740 if (finalCurveStart && finalCurveEnd 1741 && *finalCurveStart != *finalCurveEnd) { 1742 *fReducePts.append() = *finalCurveStart; 1743 *fReducePts.append() = *finalCurveEnd; 1744 *fExtra.append() = 1745 fCurrentContour->addLine(fReducePts.end() - 2); 1746 } 1747 complete(); 1748 continue; 1749 default: 1750 SkDEBUGFAIL("bad verb"); 1751 return; 1752 } 1753 finalCurveStart = &pointsPtr[verb - 1]; 1754 pointsPtr += verb; 1755 SkASSERT(fCurrentContour); 1756 } 1757 complete(); 1758 if (fCurrentContour && !fCurrentContour->fSegments.count()) { 1759 fContours.pop_back(); 1760 } 1761 // correct pointers in contours since fReducePts may have moved as it grew 1762 int cIndex = 0; 1763 fCurrentContour = &fContours[0]; 1764 int extraCount = fExtra.count(); 1765 SkASSERT(fExtra[0] == -1); 1766 int eIndex = 0; 1767 int rIndex = 0; 1768 while (++eIndex < extraCount) { 1769 int offset = fExtra[eIndex]; 1770 if (offset < 0) { 1771 fCurrentContour = &fContours[++cIndex]; 1772 continue; 1773 } 1774 Segment& segment = fCurrentContour->fSegments[offset - 1]; 1775 segment.updatePts(&fReducePts[rIndex]); 1776 rIndex += segment.verb() + 1; 1777 } 1778 fExtra.reset(); // we're done with this 1779} 1780 1781private: 1782 const SkPath& fPath; 1783 SkTDArray<SkPoint> fPathPts; // FIXME: point directly to path pts instead 1784 SkTDArray<uint8_t> fPathVerbs; // FIXME: remove 1785 Contour* fCurrentContour; 1786 SkTArray<Contour>& fContours; 1787 SkTDArray<SkPoint> fReducePts; // segments created on the fly 1788 SkTDArray<int> fExtra; // -1 marks new contour, > 0 offsets into contour 1789}; 1790 1791class Work { 1792public: 1793 enum SegmentType { 1794 kHorizontalLine_Segment = -1, 1795 kVerticalLine_Segment = 0, 1796 kLine_Segment = SkPath::kLine_Verb, 1797 kQuad_Segment = SkPath::kQuad_Verb, 1798 kCubic_Segment = SkPath::kCubic_Verb, 1799 }; 1800 1801 // FIXME: does it make sense to write otherIndex now if we're going to 1802 // fix it up later? 1803 void addOtherT(int index, double otherT, int otherIndex) { 1804 fContour->fSegments[fIndex].addOtherT(index, otherT, otherIndex); 1805 } 1806 1807 // Avoid collapsing t values that are close to the same since 1808 // we walk ts to describe consecutive intersections. Since a pair of ts can 1809 // be nearly equal, any problems caused by this should be taken care 1810 // of later. 1811 // On the edge or out of range values are negative; add 2 to get end 1812 int addT(double newT, const Work& other, int coincident) { 1813 fContour->containsIntercepts(); 1814 return fContour->fSegments[fIndex].addT(newT, 1815 other.fContour->fSegments[other.fIndex], coincident); 1816 } 1817 1818 bool advance() { 1819 return ++fIndex < fLast; 1820 } 1821 1822 SkScalar bottom() const { 1823 return bounds().fBottom; 1824 } 1825 1826 const Bounds& bounds() const { 1827 return fContour->fSegments[fIndex].bounds(); 1828 } 1829 1830 const SkPoint* cubic() const { 1831 return fCubic; 1832 } 1833 1834 void init(Contour* contour) { 1835 fContour = contour; 1836 fIndex = 0; 1837 fLast = contour->fSegments.count(); 1838 } 1839 1840 SkScalar left() const { 1841 return bounds().fLeft; 1842 } 1843 1844 void promoteToCubic() { 1845 fCubic[0] = pts()[0]; 1846 fCubic[2] = pts()[1]; 1847 fCubic[3] = pts()[2]; 1848 fCubic[1].fX = (fCubic[0].fX + fCubic[2].fX * 2) / 3; 1849 fCubic[1].fY = (fCubic[0].fY + fCubic[2].fY * 2) / 3; 1850 fCubic[2].fX = (fCubic[3].fX + fCubic[2].fX * 2) / 3; 1851 fCubic[2].fY = (fCubic[3].fY + fCubic[2].fY * 2) / 3; 1852 } 1853 1854 const SkPoint* pts() const { 1855 return fContour->fSegments[fIndex].pts(); 1856 } 1857 1858 SkScalar right() const { 1859 return bounds().fRight; 1860 } 1861 1862 ptrdiff_t segmentIndex() const { 1863 return fIndex; 1864 } 1865 1866 SegmentType segmentType() const { 1867 const Segment& segment = fContour->fSegments[fIndex]; 1868 SegmentType type = (SegmentType) segment.verb(); 1869 if (type != kLine_Segment) { 1870 return type; 1871 } 1872 if (segment.isHorizontal()) { 1873 return kHorizontalLine_Segment; 1874 } 1875 if (segment.isVertical()) { 1876 return kVerticalLine_Segment; 1877 } 1878 return kLine_Segment; 1879 } 1880 1881 bool startAfter(const Work& after) { 1882 fIndex = after.fIndex; 1883 return advance(); 1884 } 1885 1886 SkScalar top() const { 1887 return bounds().fTop; 1888 } 1889 1890 SkPath::Verb verb() const { 1891 return fContour->fSegments[fIndex].verb(); 1892 } 1893 1894 SkScalar x() const { 1895 return bounds().fLeft; 1896 } 1897 1898 bool xFlipped() const { 1899 return x() != pts()[0].fX; 1900 } 1901 1902 SkScalar y() const { 1903 return bounds().fTop; 1904 } 1905 1906 bool yFlipped() const { 1907 return y() != pts()[0].fX; 1908 } 1909 1910protected: 1911 Contour* fContour; 1912 SkPoint fCubic[4]; 1913 int fIndex; 1914 int fLast; 1915}; 1916 1917#if DEBUG_ADD_INTERSECTING_TS 1918static void debugShowLineIntersection(int pts, const Work& wt, 1919 const Work& wn, const double wtTs[2], const double wnTs[2]) { 1920 if (!pts) { 1921 SkDebugf("%s no intersect (%1.9g,%1.9g %1.9g,%1.9g) (%1.9g,%1.9g %1.9g,%1.9g)\n", 1922 __FUNCTION__, wt.pts()[0].fX, wt.pts()[0].fY, 1923 wt.pts()[1].fX, wt.pts()[1].fY, wn.pts()[0].fX, wn.pts()[0].fY, 1924 wn.pts()[1].fX, wn.pts()[1].fY); 1925 return; 1926 } 1927 SkPoint wtOutPt, wnOutPt; 1928 LineXYAtT(wt.pts(), wtTs[0], &wtOutPt); 1929 LineXYAtT(wn.pts(), wnTs[0], &wnOutPt); 1930 SkDebugf("%s wtTs[0]=%g (%g,%g, %g,%g) (%g,%g)", 1931 __FUNCTION__, 1932 wtTs[0], wt.pts()[0].fX, wt.pts()[0].fY, 1933 wt.pts()[1].fX, wt.pts()[1].fY, wtOutPt.fX, wtOutPt.fY); 1934 if (pts == 2) { 1935 SkDebugf(" wtTs[1]=%g", wtTs[1]); 1936 } 1937 SkDebugf(" wnTs[0]=%g (%g,%g, %g,%g) (%g,%g)\n", 1938 wnTs[0], wn.pts()[0].fX, wn.pts()[0].fY, 1939 wn.pts()[1].fX, wn.pts()[1].fY, wnOutPt.fX, wnOutPt.fY); 1940 if (pts == 2) { 1941 SkDebugf(" wnTs[1]=%g", wnTs[1]); 1942 SkDebugf("\n"); 1943 } 1944#else 1945static void debugShowLineIntersection(int , const Work& , 1946 const Work& , const double [2], const double [2]) { 1947} 1948#endif 1949 1950static bool addIntersectTs(Contour* test, Contour* next) { 1951 1952 if (test != next) { 1953 if (test->bounds().fBottom < next->bounds().fTop) { 1954 return false; 1955 } 1956 if (!Bounds::Intersects(test->bounds(), next->bounds())) { 1957 return true; 1958 } 1959 } 1960 Work wt; 1961 wt.init(test); 1962 do { 1963 Work wn; 1964 wn.init(next); 1965 if (test == next && !wn.startAfter(wt)) { 1966 continue; 1967 } 1968 do { 1969 if (!Bounds::Intersects(wt.bounds(), wn.bounds())) { 1970 continue; 1971 } 1972 int pts; 1973 Intersections ts; 1974 bool swap = false; 1975 switch (wt.segmentType()) { 1976 case Work::kHorizontalLine_Segment: 1977 swap = true; 1978 switch (wn.segmentType()) { 1979 case Work::kHorizontalLine_Segment: 1980 case Work::kVerticalLine_Segment: 1981 case Work::kLine_Segment: { 1982 pts = HLineIntersect(wn.pts(), wt.left(), 1983 wt.right(), wt.y(), wt.xFlipped(), ts); 1984 debugShowLineIntersection(pts, wt, wn, 1985 ts.fT[1], ts.fT[0]); 1986 break; 1987 } 1988 case Work::kQuad_Segment: { 1989 pts = HQuadIntersect(wn.pts(), wt.left(), 1990 wt.right(), wt.y(), wt.xFlipped(), ts); 1991 break; 1992 } 1993 case Work::kCubic_Segment: { 1994 pts = HCubicIntersect(wn.pts(), wt.left(), 1995 wt.right(), wt.y(), wt.xFlipped(), ts); 1996 break; 1997 } 1998 default: 1999 SkASSERT(0); 2000 } 2001 break; 2002 case Work::kVerticalLine_Segment: 2003 swap = true; 2004 switch (wn.segmentType()) { 2005 case Work::kHorizontalLine_Segment: 2006 case Work::kVerticalLine_Segment: 2007 case Work::kLine_Segment: { 2008 pts = VLineIntersect(wn.pts(), wt.top(), 2009 wt.bottom(), wt.x(), wt.yFlipped(), ts); 2010 debugShowLineIntersection(pts, wt, wn, 2011 ts.fT[1], ts.fT[0]); 2012 break; 2013 } 2014 case Work::kQuad_Segment: { 2015 pts = VQuadIntersect(wn.pts(), wt.top(), 2016 wt.bottom(), wt.x(), wt.yFlipped(), ts); 2017 break; 2018 } 2019 case Work::kCubic_Segment: { 2020 pts = VCubicIntersect(wn.pts(), wt.top(), 2021 wt.bottom(), wt.x(), wt.yFlipped(), ts); 2022 break; 2023 } 2024 default: 2025 SkASSERT(0); 2026 } 2027 break; 2028 case Work::kLine_Segment: 2029 switch (wn.segmentType()) { 2030 case Work::kHorizontalLine_Segment: 2031 pts = HLineIntersect(wt.pts(), wn.left(), 2032 wn.right(), wn.y(), wn.xFlipped(), ts); 2033 debugShowLineIntersection(pts, wt, wn, 2034 ts.fT[1], ts.fT[0]); 2035 break; 2036 case Work::kVerticalLine_Segment: 2037 pts = VLineIntersect(wt.pts(), wn.top(), 2038 wn.bottom(), wn.x(), wn.yFlipped(), ts); 2039 debugShowLineIntersection(pts, wt, wn, 2040 ts.fT[1], ts.fT[0]); 2041 break; 2042 case Work::kLine_Segment: { 2043 pts = LineIntersect(wt.pts(), wn.pts(), ts); 2044 debugShowLineIntersection(pts, wt, wn, 2045 ts.fT[1], ts.fT[0]); 2046 break; 2047 } 2048 case Work::kQuad_Segment: { 2049 swap = true; 2050 pts = QuadLineIntersect(wn.pts(), wt.pts(), ts); 2051 break; 2052 } 2053 case Work::kCubic_Segment: { 2054 swap = true; 2055 pts = CubicLineIntersect(wn.pts(), wt.pts(), ts); 2056 break; 2057 } 2058 default: 2059 SkASSERT(0); 2060 } 2061 break; 2062 case Work::kQuad_Segment: 2063 switch (wn.segmentType()) { 2064 case Work::kHorizontalLine_Segment: 2065 pts = HQuadIntersect(wt.pts(), wn.left(), 2066 wn.right(), wn.y(), wn.xFlipped(), ts); 2067 break; 2068 case Work::kVerticalLine_Segment: 2069 pts = VQuadIntersect(wt.pts(), wn.top(), 2070 wn.bottom(), wn.x(), wn.yFlipped(), ts); 2071 break; 2072 case Work::kLine_Segment: { 2073 pts = QuadLineIntersect(wt.pts(), wn.pts(), ts); 2074 break; 2075 } 2076 case Work::kQuad_Segment: { 2077 pts = QuadIntersect(wt.pts(), wn.pts(), ts); 2078 break; 2079 } 2080 case Work::kCubic_Segment: { 2081 wt.promoteToCubic(); 2082 pts = CubicIntersect(wt.cubic(), wn.pts(), ts); 2083 break; 2084 } 2085 default: 2086 SkASSERT(0); 2087 } 2088 break; 2089 case Work::kCubic_Segment: 2090 switch (wn.segmentType()) { 2091 case Work::kHorizontalLine_Segment: 2092 pts = HCubicIntersect(wt.pts(), wn.left(), 2093 wn.right(), wn.y(), wn.xFlipped(), ts); 2094 break; 2095 case Work::kVerticalLine_Segment: 2096 pts = VCubicIntersect(wt.pts(), wn.top(), 2097 wn.bottom(), wn.x(), wn.yFlipped(), ts); 2098 break; 2099 case Work::kLine_Segment: { 2100 pts = CubicLineIntersect(wt.pts(), wn.pts(), ts); 2101 break; 2102 } 2103 case Work::kQuad_Segment: { 2104 wn.promoteToCubic(); 2105 pts = CubicIntersect(wt.pts(), wn.cubic(), ts); 2106 break; 2107 } 2108 case Work::kCubic_Segment: { 2109 pts = CubicIntersect(wt.pts(), wn.pts(), ts); 2110 break; 2111 } 2112 default: 2113 SkASSERT(0); 2114 } 2115 break; 2116 default: 2117 SkASSERT(0); 2118 } 2119 // in addition to recording T values, record matching segment 2120 int testCoin; 2121 int nextCoin; 2122 if (pts == 2 && wn.segmentType() <= Work::kLine_Segment 2123 && wt.segmentType() <= Work::kLine_Segment) { 2124 // pass coincident so that smaller T is -1, larger T is 1 2125 testCoin = ts.fT[swap][0] < ts.fT[swap][1] ? -1 : 1; 2126 nextCoin = ts.fT[!swap][0] < ts.fT[!swap][1] ? -1 : 1; 2127 } else { 2128 testCoin = nextCoin = 0; 2129 } 2130 for (int pt = 0; pt < pts; ++pt) { 2131 SkASSERT(ts.fT[0][pt] >= 0 && ts.fT[0][pt] <= 1); 2132 SkASSERT(ts.fT[1][pt] >= 0 && ts.fT[1][pt] <= 1); 2133 int testTAt = wt.addT(ts.fT[swap][pt], wn, testCoin); 2134 int nextTAt = wn.addT(ts.fT[!swap][pt], wt, nextCoin); 2135 wt.addOtherT(testTAt, ts.fT[!swap][pt], nextTAt); 2136 wn.addOtherT(nextTAt, ts.fT[swap][pt], testTAt); 2137 testCoin = -testCoin; 2138 nextCoin = -nextCoin; 2139 } 2140 } while (wn.advance()); 2141 } while (wt.advance()); 2142 return true; 2143} 2144 2145// see if coincidence is formed by clipping non-concident segments 2146static void coincidenceCheck(SkTDArray<Contour*>& contourList, int winding) { 2147 int contourCount = contourList.count(); 2148 for (int cIndex = 0; cIndex < contourCount; ++cIndex) { 2149 Contour* contour = contourList[cIndex]; 2150 contour->findTooCloseToCall(winding); 2151 } 2152} 2153 2154 2155// OPTIMIZATION: not crazy about linear search here to find top active y. 2156// seems like we should break down and do the sort, or maybe sort each 2157// contours' segments? 2158// Once the segment array is built, there's no reason I can think of not to 2159// sort it in Y. hmmm 2160static Segment* findTopContour(SkTDArray<Contour*>& contourList, 2161 int contourCount) { 2162 int cIndex = 0; 2163 Segment* topStart; 2164 do { 2165 Contour* topContour = contourList[cIndex]; 2166 topStart = topContour->topSegment(); 2167 } while (!topStart && ++cIndex < contourCount); 2168 if (!topStart) { 2169 return NULL; 2170 } 2171 SkScalar top = topStart->bounds().fTop; 2172 for (int cTest = cIndex + 1; cTest < contourCount; ++cTest) { 2173 Contour* contour = contourList[cTest]; 2174 if (top < contour->bounds().fTop) { 2175 continue; 2176 } 2177 Segment* test = contour->topSegment(); 2178 if (top > test->bounds().fTop) { 2179 cIndex = cTest; 2180 topStart = test; 2181 top = test->bounds().fTop; 2182 } 2183 } 2184 return topStart; 2185} 2186 2187// Each segment may have an inside or an outside. Segments contained within 2188// winding may have insides on either side, and form a contour that should be 2189// ignored. Segments that are coincident with opposing direction segments may 2190// have outsides on either side, and should also disappear. 2191// 'Normal' segments will have one inside and one outside. Subsequent connections 2192// when winding should follow the intersection direction. If more than one edge 2193// is an option, choose first edge that continues the inside. 2194 // since we start with leftmost top edge, we'll traverse through a 2195 // smaller angle counterclockwise to get to the next edge. 2196static void bridge(SkTDArray<Contour*>& contourList, SkPath& simple) { 2197 int contourCount = contourList.count(); 2198 do { 2199 Segment* topStart = findTopContour(contourList, contourCount); 2200 if (!topStart) { 2201 break; 2202 } 2203 // FIXME: if this contour is inside others, winding will not be zero initially 2204 int winding = 0; // zero says there are no contours outside this one 2205 // Start at the top. Above the top is outside, below is inside. 2206 // follow edges to intersection by changing the index by direction. 2207 int index, endIndex; 2208 Segment* current = topStart->findTop(index, endIndex); 2209 winding += SkSign32(index - endIndex); 2210 const SkPoint* firstPt = NULL; 2211 SkPoint lastPt; 2212 do { 2213 SkASSERT(!current->done()); 2214 int nextStart, nextEnd; 2215 Segment* next = current->findNext(winding, index, endIndex, 2216 nextStart, nextEnd); 2217 if (!next) { 2218 break; 2219 } 2220 if (!firstPt) { 2221 firstPt = ¤t->addMoveTo(index, simple); 2222 } 2223 lastPt = current->addCurveTo(index, endIndex, simple); 2224 current = next; 2225 index = nextStart; 2226 endIndex = nextEnd; 2227 } while (*firstPt != lastPt); 2228 if (firstPt) { 2229 #if DEBUG_PATH_CONSTRUCTION 2230 SkDebugf("%s close\n", __FUNCTION__); 2231 #endif 2232 simple.close(); 2233 } 2234 } while (true); 2235 // FIXME: more work to be done for contained (but not intersecting) 2236 // segments 2237} 2238 2239static void fixOtherTIndex(SkTDArray<Contour*>& contourList) { 2240 int contourCount = contourList.count(); 2241 for (int cTest = 0; cTest < contourCount; ++cTest) { 2242 Contour* contour = contourList[cTest]; 2243 contour->fixOtherTIndex(); 2244 } 2245} 2246 2247static void makeContourList(SkTArray<Contour>& contours, 2248 SkTDArray<Contour*>& list) { 2249 int count = contours.count(); 2250 if (count == 0) { 2251 return; 2252 } 2253 for (int index = 0; index < count; ++index) { 2254 *list.append() = &contours[index]; 2255 } 2256 QSort<Contour>(list.begin(), list.end() - 1); 2257} 2258 2259void simplifyx(const SkPath& path, SkPath& simple) { 2260 // returns 1 for evenodd, -1 for winding, regardless of inverse-ness 2261 int winding = (path.getFillType() & 1) ? 1 : -1; 2262 simple.reset(); 2263 simple.setFillType(SkPath::kEvenOdd_FillType); 2264 2265 // turn path into list of segments 2266 SkTArray<Contour> contours; 2267 // FIXME: add self-intersecting cubics' T values to segment 2268 EdgeBuilder builder(path, contours); 2269 SkTDArray<Contour*> contourList; 2270 makeContourList(contours, contourList); 2271 Contour** currentPtr = contourList.begin(); 2272 if (!currentPtr) { 2273 return; 2274 } 2275 Contour** listEnd = contourList.end(); 2276 // find all intersections between segments 2277 do { 2278 Contour** nextPtr = currentPtr; 2279 Contour* current = *currentPtr++; 2280 Contour* next; 2281 do { 2282 next = *nextPtr++; 2283 } while (addIntersectTs(current, next) && nextPtr != listEnd); 2284 } while (currentPtr != listEnd); 2285 fixOtherTIndex(contourList); 2286 // eat through coincident edges 2287 coincidenceCheck(contourList, winding); 2288 // construct closed contours 2289 bridge(contourList, simple); 2290} 2291 2292