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