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