Simplify.cpp revision fcd4f3e5bf55d8cd1d97c8f620fabd41eb6a754b
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 oIndex = other->matchSpan(this, endSpan->fT); 611 int oCount = other->fTs.count(); 612 do { 613 Span& otherSpan = other->fTs[oIndex]; 614 // if done == -1, prior span has already been processed 615 int next = other->nextSpan(oIndex, step, endLoc, &otherSpan, 616 NULL, NULL); 617 if (next < 0) { 618 continue; 619 } 620 bool otherIsCoincident; 621 last = other->lastSpan(next, step, &endLoc, &otherSpan, 622 otherIsCoincident); 623 if (last < 0) { 624 continue; 625 } 626 #if 0 627 Span& prior = other->fTs[oIndex - 1]; 628 if (otherSpan.fDone >= 0 && oIndex > 0) { 629 // FIXME: this needs to loop on -- until t && pt are different 630 if (prior.fDone > 0) { 631 continue; 632 } 633 634 } 635 } else { // step == 1 636 if (otherSpan.fDone <= 0 && oIndex < oCount - 1) { 637 // FIXME: this needs to loop on ++ until t && pt are different 638 Span& next = other->fTs[oIndex + 1]; 639 if (next.fDone < 0) { 640 continue; 641 } 642 } 643 } 644 #endif 645 if (!segmentCandidate) { 646 segmentCandidate = other; 647 spanCandidate = oIndex; 648 directionCandidate = step; 649 continue; 650 } 651 // there's two or more matches 652 if (spanCandidate >= 0) { // retrieve first stored candidate 653 // add edge leading into junction 654 addAngle(angles, endSpan->fT, startSpan->fT); 655 // add edge leading away from junction 656 double nextT = nextSpan(end, step, endLoc, endSpan, NULL, 657 NULL); 658 if (nextT >= 0) { 659 addAngle(angles, endSpan->fT, nextT); 660 } 661 // add first stored candidate into junction 662 segmentCandidate->addAngle(angles, 663 segmentCandidate->fTs[spanCandidate - 1].fT, 664 segmentCandidate->fTs[spanCandidate].fT); 665 // add first stored candidate away from junction 666 segmentCandidate->addAngle(angles, 667 segmentCandidate->fTs[spanCandidate].fT, 668 segmentCandidate->fTs[spanCandidate + 1].fT); 669 } 670 // add candidate into and away from junction 671 672 673 // start here; 674 // more than once viable candidate -- need to 675 // measure angles to find best 676 // noncoincident quads/cubics may have the same initial angle 677 // as lines, so must sort by derivatives as well 678 // while we're here, figure out all connections given the 679 // initial winding info 680 // so the span needs to contain the pairing info found here 681 // this should include the winding computed for the edge, and 682 // what edge it connects to, and whether it is discarded 683 // (maybe discarded == abs(winding) > 1) ? 684 // only need derivatives for duration of sorting, add a new struct 685 // for pairings, remove extra spans that have zero length and 686 // reference an unused other 687 // for coincident, the last span on the other may be marked done 688 // (always?) 689 } while (++oIndex < oCount); 690 } while ((end += step) != last); 691 // if loop is exhausted, contour may be closed. 692 // FIXME: pass in close point so we can check for closure 693 694 // given a segment, and a sense of where 'inside' is, return the next 695 // segment. If this segment has an intersection, or ends in multiple 696 // segments, find the mate that continues the outside. 697 // note that if there are multiples, but no coincidence, we can limit 698 // choices to connections in the correct direction 699 700 // mark found segments as done 701 } 702 703 void findTooCloseToCall(int winding) { 704 int count = fTs.count(); 705 if (count < 3) { // require t=0, x, 1 at minimum 706 return; 707 } 708 int matchIndex = 0; 709 int moCount; 710 Span* match; 711 Segment* mOther; 712 do { 713 match = &fTs[matchIndex]; 714 mOther = match->fOther; 715 moCount = mOther->fTs.count(); 716 } while (moCount >= 3 || ++matchIndex < count - 1); // require t=0, x, 1 at minimum 717 SkPoint matchPt; 718 // OPTIMIZATION: defer matchPt until qualifying toCount is found? 719 xyAtT(match->fT, &matchPt); 720 // look for a pair of nearby T values that map to the same (x,y) value 721 // if found, see if the pair of other segments share a common point. If 722 // so, the span from here to there is coincident. 723 for (int index = matchIndex + 1; index < count; ++index) { 724 Span* test = &fTs[index]; 725 Segment* tOther = test->fOther; 726 int toCount = tOther->fTs.count(); 727 if (toCount < 3) { // require t=0, x, 1 at minimum 728 continue; 729 } 730 SkPoint testPt; 731 xyAtT(test->fT, &testPt); 732 if (matchPt != testPt) { 733 matchIndex = index; 734 moCount = toCount; 735 match = test; 736 mOther = tOther; 737 matchPt = testPt; 738 continue; 739 } 740 int moStart = -1; // FIXME: initialization is debugging only 741 for (int moIndex = 0; moIndex < moCount; ++moIndex) { 742 Span& moSpan = mOther->fTs[moIndex]; 743 if (moSpan.fOther == this) { 744 if (moSpan.fOtherT == match->fT) { 745 moStart = moIndex; 746 } 747 continue; 748 } 749 if (moSpan.fOther != tOther) { 750 continue; 751 } 752 int toStart = -1; 753 int toIndex; // FIXME: initialization is debugging only 754 bool found = false; 755 for (toIndex = 0; toIndex < toCount; ++toIndex) { 756 Span& toSpan = tOther->fTs[toIndex]; 757 if (toSpan.fOther == this) { 758 if (toSpan.fOtherT == test->fT) { 759 toStart = toIndex; 760 } 761 continue; 762 } 763 if (toSpan.fOther == mOther && toSpan.fOtherT 764 == moSpan.fT) { 765 found = true; 766 break; 767 } 768 } 769 if (!found) { 770 continue; 771 } 772 SkASSERT(moStart >= 0); 773 SkASSERT(toStart >= 0); 774 // test to see if the segment between there and here is linear 775 if (!mOther->isLinear(moStart, moIndex) 776 || !tOther->isLinear(toStart, toIndex)) { 777 continue; 778 } 779 mOther->fTs[moStart].fCoincident = -1; 780 tOther->fTs[toStart].fCoincident = -1; 781 mOther->fTs[moIndex].fCoincident = 1; 782 tOther->fTs[toIndex].fCoincident = 1; 783 } 784 nextStart: 785 ; 786 } 787 } 788 789 int findByT(double t, const Segment* match) const { 790 // OPTIMIZATION: bsearch if count is honkin huge 791 int count = fTs.count(); 792 for (int index = 0; index < count; ++index) { 793 const Span& span = fTs[index]; 794 if (t == span.fT && match == span.fOther) { 795 return index; 796 } 797 } 798 SkASSERT(0); // should never get here 799 return -1; 800 } 801 802 // find the adjacent T that is leftmost, with a point != base 803 int findLefty(int tIndex, const SkPoint& base) const { 804 int bestTIndex; 805 SkPoint test; 806 SkScalar bestX = DBL_MAX; 807 int testTIndex = tIndex; 808 while (--testTIndex >= 0) { 809 xyAtT(testTIndex, &test); 810 if (test != base) { 811 continue; 812 } 813 bestX = test.fX; 814 bestTIndex = testTIndex; 815 break; 816 } 817 int count = fTs.count(); 818 testTIndex = tIndex; 819 while (++testTIndex < count) { 820 xyAtT(testTIndex, &test); 821 if (test == base) { 822 continue; 823 } 824 return bestX > test.fX ? testTIndex : bestTIndex; 825 } 826 SkASSERT(0); // can't get here (?) 827 return -1; 828 } 829 830 // OPTIMIZATION : for a pair of lines, can we compute points at T (cached) 831 // and use more concise logic like the old edge walker code? 832 // FIXME: this needs to deal with coincident edges 833 const Segment* findTop(int& tIndex) const { 834 // iterate through T intersections and return topmost 835 // topmost tangent from y-min to first pt is closer to horizontal 836 int firstT = 0; 837 int lastT = 0; 838 SkScalar topY = fPts[0].fY; 839 int count = fTs.count(); 840 int index; 841 for (index = 1; index < count; ++index) { 842 const Span& span = fTs[index]; 843 double t = span.fT; 844 SkScalar yIntercept = yAtT(t); 845 if (topY > yIntercept) { 846 topY = yIntercept; 847 firstT = lastT = index; 848 } else if (topY == yIntercept) { 849 lastT = index; 850 } 851 } 852 // if there's only a pair of segments, go with the endpoint chosen above 853 if (firstT == lastT && (firstT == 0 || firstT == count - 1)) { 854 tIndex = firstT; 855 return this; 856 } 857 // if the topmost T is not on end, or is three-way or more, find left 858 SkPoint leftBase; 859 xyAtT(firstT, &leftBase); 860 int tLeft = findLefty(firstT, leftBase); 861 const Segment* leftSegment = this; 862 // look for left-ness from tLeft to firstT (matching y of other) 863 for (index = firstT; index <= lastT; ++index) { 864 const Segment* other = fTs[index].fOther; 865 double otherT = fTs[index].fOtherT; 866 int otherTIndex = other->findByT(otherT, this); 867 // pick companionT closest (but not too close) on either side 868 int otherTLeft = other->findLefty(otherTIndex, leftBase); 869 // within this span, find highest y 870 SkPoint testPt, otherPt; 871 testPt.fY = yAtT(tLeft); 872 otherPt.fY = other->yAtT(otherTLeft); 873 // FIXME: incomplete 874 // find the y intercept with the opposite segment 875 if (testPt.fY < otherPt.fY) { 876 877 } else if (testPt.fY > otherPt.fY) { 878 879 } 880 // FIXME: leftMost no good. Use y intercept instead 881#if 0 882 SkScalar otherMost = other->leftMost(otherTIndex, otherTLeft); 883 if (otherMost < left) { 884 leftSegment = other; 885 } 886#endif 887 } 888 return leftSegment; 889 } 890 891 bool intersected() const { 892 return fTs.count() > 0; 893 } 894 895 bool isLinear(int start, int end) const { 896 if (fVerb == SkPath::kLine_Verb) { 897 return true; 898 } 899 if (fVerb == SkPath::kQuad_Verb) { 900 SkPoint qPart[3]; 901 QuadSubDivide(fPts, fTs[start].fT, fTs[end].fT, qPart); 902 return QuadIsLinear(qPart); 903 } else { 904 SkASSERT(fVerb == SkPath::kCubic_Verb); 905 SkPoint cPart[4]; 906 CubicSubDivide(fPts, fTs[start].fT, fTs[end].fT, cPart); 907 return CubicIsLinear(cPart); 908 } 909 } 910 911 bool isHorizontal() const { 912 return fBounds.fTop == fBounds.fBottom; 913 } 914 915 bool isVertical() const { 916 return fBounds.fLeft == fBounds.fRight; 917 } 918 919 int lastSpan(int end, int step, const SkPoint* startLoc, 920 const Span* startSpan, bool& coincident) { 921 int last = end; 922 int count = fTs.count(); 923 coincident = false; 924 SkPoint lastLoc; 925 do { 926 if (fTs[last].fCoincident == -step) { 927 coincident = true; 928 } 929 if (step > 0 ? ++last < count : --last >= 0) { 930 return -1; 931 } 932 const Span& lastSpan = fTs[last]; 933 if (lastSpan.fDone == -step) { 934 return -1; 935 } 936 if (lastSpan.fT == startSpan->fT) { 937 continue; 938 } 939 xyAtT(lastSpan.fT, &lastLoc); 940 } while (*startLoc == lastLoc); 941 return last; 942 } 943 944 SkScalar leftMost(int start, int end) const { 945 return (*SegmentLeftMost[fVerb])(fPts, fTs[start].fT, fTs[end].fT); 946 } 947 948 int matchSpan(const Segment* match, double matchT) 949 { 950 int count = fTs.count(); 951 for (int index = 0; index < count; ++index) { 952 Span& span = fTs[index]; 953 if (span.fOther != match) { 954 continue; 955 } 956 if (span.fOtherT != matchT) { 957 continue; 958 } 959 return index; 960 } 961 SkASSERT(0); // should never get here 962 return -1; 963 } 964 965 int nextSpan(int from, int step, const SkPoint& fromLoc, 966 const Span* fromSpan, SkPoint* toLoc, Span** toSpan) { 967 int count = fTs.count(); 968 int to = from; 969 while (step > 0 ? ++to < count : --to >= 0) { 970 Span* span = &fTs[to]; 971 if (span->fT == fromSpan->fT) { 972 continue; 973 } 974 SkPoint loc; 975 xyAtT(span->fT, &loc); 976 if (fromLoc == loc) { 977 continue; 978 } 979 if (toLoc) { 980 *toLoc = loc; 981 } 982 if (toSpan) { 983 *toSpan = span; 984 } 985 return to; 986 } 987 return -1; 988 } 989 990 const SkPoint* pts() const { 991 return fPts; 992 } 993 994 void reset() { 995 fPts = NULL; 996 fVerb = (SkPath::Verb) -1; 997 fBounds.set(SK_ScalarMax, SK_ScalarMax, SK_ScalarMax, SK_ScalarMax); 998 fTs.reset(); 999 fDone = false; 1000 fCoincident = 0; 1001 } 1002 1003 // OPTIMIZATION: remove this function if it's never called 1004 double t(int tIndex) const { 1005 return fTs[tIndex].fT; 1006 } 1007 1008 SkPath::Verb verb() const { 1009 return fVerb; 1010 } 1011 1012 SkScalar xAtT(double t) const { 1013 return (*SegmentXAtT[fVerb])(fPts, t); 1014 } 1015 1016 void xyAtT(double t, SkPoint* pt) const { 1017 (*SegmentXYAtT[fVerb])(fPts, t, pt); 1018 } 1019 1020 SkScalar yAtT(double t) const { 1021 return (*SegmentYAtT[fVerb])(fPts, t); 1022 } 1023 1024#if DEBUG_DUMP 1025 void dump() const { 1026 const char className[] = "Segment"; 1027 const int tab = 4; 1028 for (int i = 0; i < fTs.count(); ++i) { 1029 SkPoint out; 1030 (*SegmentXYAtT[fVerb])(fPts, t(i), &out); 1031 SkDebugf("%*s [%d] %s.fTs[%d]=%1.9g (%1.9g,%1.9g) other=%d" 1032 " otherT=%1.9g winding=%d\n", 1033 tab + sizeof(className), className, fID, 1034 kLVerbStr[fVerb], i, fTs[i].fT, out.fX, out.fY, 1035 fTs[i].fOther->fID, fTs[i].fOtherT, fTs[i].fWinding); 1036 } 1037 SkDebugf("%*s [%d] fBounds=(l:%1.9g, t:%1.9g r:%1.9g, b:%1.9g)", 1038 tab + sizeof(className), className, fID, 1039 fBounds.fLeft, fBounds.fTop, fBounds.fRight, fBounds.fBottom); 1040 } 1041#endif 1042 1043private: 1044 const SkPoint* fPts; 1045 SkPath::Verb fVerb; 1046 Bounds fBounds; 1047 SkTDArray<Span> fTs; // two or more (always includes t=0 t=1) 1048 // FIXME: coincident only needs two bits (-1, 0, 1) 1049 int fCoincident; // non-zero if some coincident span inside 1050 bool fDone; 1051#if DEBUG_DUMP 1052 int fID; 1053#endif 1054}; 1055 1056class Contour { 1057public: 1058 Contour() { 1059 reset(); 1060#if DEBUG_DUMP 1061 fID = ++gContourID; 1062#endif 1063 } 1064 1065 bool operator<(const Contour& rh) const { 1066 return fBounds.fTop == rh.fBounds.fTop 1067 ? fBounds.fLeft < rh.fBounds.fLeft 1068 : fBounds.fTop < rh.fBounds.fTop; 1069 } 1070 1071 void addCubic(const SkPoint pts[4]) { 1072 fSegments.push_back().addCubic(pts); 1073 fContainsCurves = true; 1074 } 1075 1076 void addLine(const SkPoint pts[2]) { 1077 fSegments.push_back().addLine(pts); 1078 } 1079 1080 void addQuad(const SkPoint pts[3]) { 1081 fSegments.push_back().addQuad(pts); 1082 fContainsCurves = true; 1083 } 1084 1085 const Bounds& bounds() const { 1086 return fBounds; 1087 } 1088 1089 void complete() { 1090 setBounds(); 1091 fContainsIntercepts = false; 1092 } 1093 1094 void containsIntercepts() { 1095 fContainsIntercepts = true; 1096 } 1097 1098 void findTooCloseToCall(int winding) { 1099 int segmentCount = fSegments.count(); 1100 for (int sIndex = 0; sIndex < segmentCount; ++sIndex) { 1101 fSegments[sIndex].findTooCloseToCall(winding); 1102 } 1103 } 1104 1105 void reset() { 1106 fSegments.reset(); 1107 fBounds.set(SK_ScalarMax, SK_ScalarMax, SK_ScalarMax, SK_ScalarMax); 1108 fContainsCurves = fContainsIntercepts = false; 1109 } 1110 1111 // OPTIMIZATION: feel pretty uneasy about this. It seems like once again 1112 // we need to sort and walk edges in y, but that on the surface opens the 1113 // same can of worms as before. But then, this is a rough sort based on 1114 // segments' top, and not a true sort, so it could be ameniable to regular 1115 // sorting instead of linear searching. Still feel like I'm missing something 1116 Segment* topSegment() { 1117 int segmentCount = fSegments.count(); 1118 SkASSERT(segmentCount > 0); 1119 int best = -1; 1120 Segment* bestSegment = NULL; 1121 while (++best < segmentCount) { 1122 Segment* testSegment = &fSegments[best]; 1123 if (testSegment->done()) { 1124 continue; 1125 } 1126 bestSegment = testSegment; 1127 break; 1128 } 1129 if (!bestSegment) { 1130 return NULL; 1131 } 1132 SkScalar bestTop = bestSegment->bounds().fTop; 1133 for (int test = best + 1; test < segmentCount; ++test) { 1134 Segment* testSegment = &fSegments[test]; 1135 if (testSegment->done()) { 1136 continue; 1137 } 1138 SkScalar testTop = testSegment->bounds().fTop; 1139 if (bestTop > testTop) { 1140 bestTop = testTop; 1141 bestSegment = testSegment; 1142 } 1143 } 1144 return bestSegment; 1145 } 1146 1147#if DEBUG_DUMP 1148 void dump() { 1149 int i; 1150 const char className[] = "Contour"; 1151 const int tab = 4; 1152 SkDebugf("%s %p (contour=%d)\n", className, this, fID); 1153 for (i = 0; i < fSegments.count(); ++i) { 1154 SkDebugf("%*s.fSegments[%d]:\n", tab + sizeof(className), 1155 className, i); 1156 fSegments[i].dump(); 1157 } 1158 SkDebugf("%*s.fBounds=(l:%1.9g, t:%1.9g r:%1.9g, b:%1.9g)\n", 1159 tab + sizeof(className), className, 1160 fBounds.fLeft, fBounds.fTop, 1161 fBounds.fRight, fBounds.fBottom); 1162 SkDebugf("%*s.fContainsIntercepts=%d\n", tab + sizeof(className), 1163 className, fContainsIntercepts); 1164 SkDebugf("%*s.fContainsCurves=%d\n", tab + sizeof(className), 1165 className, fContainsCurves); 1166 } 1167#endif 1168 1169protected: 1170 void setBounds() { 1171 int count = fSegments.count(); 1172 if (count == 0) { 1173 SkDebugf("%s empty contour\n", __FUNCTION__); 1174 SkASSERT(0); 1175 // FIXME: delete empty contour? 1176 return; 1177 } 1178 fBounds = fSegments.front().bounds(); 1179 for (int index = 1; index < count; ++index) { 1180 fBounds.growToInclude(fSegments[index].bounds()); 1181 } 1182 } 1183 1184public: 1185 SkTArray<Segment> fSegments; // not worth accessor functions? 1186 1187private: 1188 Bounds fBounds; 1189 bool fContainsIntercepts; 1190 bool fContainsCurves; 1191#if DEBUG_DUMP 1192 int fID; 1193#endif 1194}; 1195 1196class EdgeBuilder { 1197public: 1198 1199EdgeBuilder(const SkPath& path, SkTArray<Contour>& contours) 1200 : fPath(path) 1201 , fCurrentContour(NULL) 1202 , fContours(contours) 1203{ 1204#if DEBUG_DUMP 1205 gContourID = 0; 1206 gSegmentID = 0; 1207#endif 1208 walk(); 1209} 1210 1211protected: 1212 1213void complete() { 1214 if (fCurrentContour && fCurrentContour->fSegments.count()) { 1215 fCurrentContour->complete(); 1216 fCurrentContour = NULL; 1217 } 1218} 1219 1220void startContour() { 1221 if (!fCurrentContour) { 1222 fCurrentContour = fContours.push_back_n(1); 1223 } 1224} 1225 1226void walk() { 1227 // FIXME:remove once we can access path pts directly 1228 SkPath::RawIter iter(fPath); // FIXME: access path directly when allowed 1229 SkPoint pts[4]; 1230 SkPath::Verb verb; 1231 do { 1232 verb = iter.next(pts); 1233 *fPathVerbs.append() = verb; 1234 if (verb == SkPath::kMove_Verb) { 1235 *fPathPts.append() = pts[0]; 1236 } else if (verb >= SkPath::kLine_Verb && verb <= SkPath::kCubic_Verb) { 1237 fPathPts.append(verb, &pts[1]); 1238 } 1239 } while (verb != SkPath::kDone_Verb); 1240 // FIXME: end of section to remove once path pts are accessed directly 1241 1242 SkPath::Verb reducedVerb; 1243 uint8_t* verbPtr = fPathVerbs.begin(); 1244 const SkPoint* pointsPtr = fPathPts.begin(); 1245 while ((verb = (SkPath::Verb) *verbPtr++) != SkPath::kDone_Verb) { 1246 switch (verb) { 1247 case SkPath::kMove_Verb: 1248 complete(); 1249 startContour(); 1250 pointsPtr += 1; 1251 continue; 1252 case SkPath::kLine_Verb: 1253 // skip degenerate points 1254 if (pointsPtr[-1].fX != pointsPtr[0].fX 1255 || pointsPtr[-1].fY != pointsPtr[0].fY) { 1256 fCurrentContour->addLine(&pointsPtr[-1]); 1257 } 1258 break; 1259 case SkPath::kQuad_Verb: 1260 reducedVerb = QuadReduceOrder(&pointsPtr[-1], fReducePts); 1261 if (reducedVerb == 0) { 1262 break; // skip degenerate points 1263 } 1264 if (reducedVerb == 1) { 1265 fCurrentContour->addLine(fReducePts.end() - 2); 1266 break; 1267 } 1268 fCurrentContour->addQuad(&pointsPtr[-1]); 1269 break; 1270 case SkPath::kCubic_Verb: 1271 reducedVerb = CubicReduceOrder(&pointsPtr[-1], fReducePts); 1272 if (reducedVerb == 0) { 1273 break; // skip degenerate points 1274 } 1275 if (reducedVerb == 1) { 1276 fCurrentContour->addLine(fReducePts.end() - 2); 1277 break; 1278 } 1279 if (reducedVerb == 2) { 1280 fCurrentContour->addQuad(fReducePts.end() - 3); 1281 break; 1282 } 1283 fCurrentContour->addCubic(&pointsPtr[-1]); 1284 break; 1285 case SkPath::kClose_Verb: 1286 SkASSERT(fCurrentContour); 1287 complete(); 1288 continue; 1289 default: 1290 SkDEBUGFAIL("bad verb"); 1291 return; 1292 } 1293 pointsPtr += verb; 1294 SkASSERT(fCurrentContour); 1295 } 1296 complete(); 1297 if (fCurrentContour && !fCurrentContour->fSegments.count()) { 1298 fContours.pop_back(); 1299 } 1300} 1301 1302private: 1303 const SkPath& fPath; 1304 SkTDArray<SkPoint> fPathPts; // FIXME: point directly to path pts instead 1305 SkTDArray<uint8_t> fPathVerbs; // FIXME: remove 1306 Contour* fCurrentContour; 1307 SkTArray<Contour>& fContours; 1308 SkTDArray<SkPoint> fReducePts; // segments created on the fly 1309}; 1310 1311class Work { 1312public: 1313 enum SegmentType { 1314 kHorizontalLine_Segment = -1, 1315 kVerticalLine_Segment = 0, 1316 kLine_Segment = SkPath::kLine_Verb, 1317 kQuad_Segment = SkPath::kQuad_Verb, 1318 kCubic_Segment = SkPath::kCubic_Verb, 1319 }; 1320 1321 void addOtherT(int index, double other) { 1322 fContour->fSegments[fIndex].addOtherT(index, other); 1323 } 1324 1325 // Avoid collapsing t values that are close to the same since 1326 // we walk ts to describe consecutive intersections. Since a pair of ts can 1327 // be nearly equal, any problems caused by this should be taken care 1328 // of later. 1329 // On the edge or out of range values are negative; add 2 to get end 1330 int addT(double newT, const Work& other, int coincident) { 1331 fContour->containsIntercepts(); 1332 return fContour->fSegments[fIndex].addT(newT, 1333 other.fContour->fSegments[other.fIndex], coincident); 1334 } 1335 1336 bool advance() { 1337 return ++fIndex < fLast; 1338 } 1339 1340 SkScalar bottom() const { 1341 return bounds().fBottom; 1342 } 1343 1344 const Bounds& bounds() const { 1345 return fContour->fSegments[fIndex].bounds(); 1346 } 1347 1348 const SkPoint* cubic() const { 1349 return fCubic; 1350 } 1351 1352 void init(Contour* contour) { 1353 fContour = contour; 1354 fIndex = 0; 1355 fLast = contour->fSegments.count(); 1356 } 1357 1358 SkScalar left() const { 1359 return bounds().fLeft; 1360 } 1361 1362 void promoteToCubic() { 1363 fCubic[0] = pts()[0]; 1364 fCubic[2] = pts()[1]; 1365 fCubic[3] = pts()[2]; 1366 fCubic[1].fX = (fCubic[0].fX + fCubic[2].fX * 2) / 3; 1367 fCubic[1].fY = (fCubic[0].fY + fCubic[2].fY * 2) / 3; 1368 fCubic[2].fX = (fCubic[3].fX + fCubic[2].fX * 2) / 3; 1369 fCubic[2].fY = (fCubic[3].fY + fCubic[2].fY * 2) / 3; 1370 } 1371 1372 const SkPoint* pts() const { 1373 return fContour->fSegments[fIndex].pts(); 1374 } 1375 1376 SkScalar right() const { 1377 return bounds().fRight; 1378 } 1379 1380 ptrdiff_t segmentIndex() const { 1381 return fIndex; 1382 } 1383 1384 SegmentType segmentType() const { 1385 const Segment& segment = fContour->fSegments[fIndex]; 1386 SegmentType type = (SegmentType) segment.verb(); 1387 if (type != kLine_Segment) { 1388 return type; 1389 } 1390 if (segment.isHorizontal()) { 1391 return kHorizontalLine_Segment; 1392 } 1393 if (segment.isVertical()) { 1394 return kVerticalLine_Segment; 1395 } 1396 return kLine_Segment; 1397 } 1398 1399 bool startAfter(const Work& after) { 1400 fIndex = after.fIndex; 1401 return advance(); 1402 } 1403 1404 SkScalar top() const { 1405 return bounds().fTop; 1406 } 1407 1408 SkPath::Verb verb() const { 1409 return fContour->fSegments[fIndex].verb(); 1410 } 1411 1412 SkScalar x() const { 1413 return bounds().fLeft; 1414 } 1415 1416 bool xFlipped() const { 1417 return x() != pts()[0].fX; 1418 } 1419 1420 SkScalar y() const { 1421 return bounds().fTop; 1422 } 1423 1424 bool yFlipped() const { 1425 return y() != pts()[0].fX; 1426 } 1427 1428protected: 1429 Contour* fContour; 1430 SkPoint fCubic[4]; 1431 int fIndex; 1432 int fLast; 1433}; 1434 1435static void debugShowLineIntersection(int pts, const Work& wt, 1436 const Work& wn, const double wtTs[2], const double wnTs[2]) { 1437#if DEBUG_ADD_INTERSECTING_TS 1438 if (!pts) { 1439 return; 1440 } 1441 SkPoint wtOutPt, wnOutPt; 1442 LineXYAtT(wt.pts(), wtTs[0], &wtOutPt); 1443 LineXYAtT(wn.pts(), wnTs[0], &wnOutPt); 1444 SkDebugf("%s wtTs[0]=%g (%g,%g, %g,%g) (%g,%g)\n", 1445 __FUNCTION__, 1446 wtTs[0], wt.pts()[0].fX, wt.pts()[0].fY, 1447 wt.pts()[1].fX, wt.pts()[1].fY, wtOutPt.fX, wtOutPt.fY); 1448 if (pts == 2) { 1449 SkDebugf("%s wtTs[1]=%g\n", __FUNCTION__, wtTs[1]); 1450 } 1451 SkDebugf("%s wnTs[0]=%g (%g,%g, %g,%g) (%g,%g)\n", 1452 __FUNCTION__, 1453 wnTs[0], wn.pts()[0].fX, wn.pts()[0].fY, 1454 wn.pts()[1].fX, wn.pts()[1].fY, wnOutPt.fX, wnOutPt.fY); 1455 if (pts == 2) { 1456 SkDebugf("%s wnTs[1]=%g\n", __FUNCTION__, wnTs[1]); 1457 } 1458#endif 1459} 1460 1461static bool addIntersectTs(Contour* test, Contour* next, int winding) { 1462 if (test != next) { 1463 if (test->bounds().fBottom < next->bounds().fTop) { 1464 return false; 1465 } 1466 if (!Bounds::Intersects(test->bounds(), next->bounds())) { 1467 return true; 1468 } 1469 } 1470 Work wt, wn; 1471 wt.init(test); 1472 wn.init(next); 1473 do { 1474 if (test == next && !wn.startAfter(wt)) { 1475 continue; 1476 } 1477 do { 1478 if (!Bounds::Intersects(wt.bounds(), wn.bounds())) { 1479 continue; 1480 } 1481 int pts; 1482 Intersections ts; 1483 bool swap = false; 1484 switch (wt.segmentType()) { 1485 case Work::kHorizontalLine_Segment: 1486 swap = true; 1487 switch (wn.segmentType()) { 1488 case Work::kHorizontalLine_Segment: 1489 case Work::kVerticalLine_Segment: 1490 case Work::kLine_Segment: { 1491 pts = HLineIntersect(wn.pts(), wt.left(), 1492 wt.right(), wt.y(), wt.xFlipped(), ts); 1493 break; 1494 } 1495 case Work::kQuad_Segment: { 1496 pts = HQuadIntersect(wn.pts(), wt.left(), 1497 wt.right(), wt.y(), wt.xFlipped(), ts); 1498 break; 1499 } 1500 case Work::kCubic_Segment: { 1501 pts = HCubicIntersect(wn.pts(), wt.left(), 1502 wt.right(), wt.y(), wt.xFlipped(), ts); 1503 break; 1504 } 1505 default: 1506 SkASSERT(0); 1507 } 1508 break; 1509 case Work::kVerticalLine_Segment: 1510 swap = true; 1511 switch (wn.segmentType()) { 1512 case Work::kHorizontalLine_Segment: 1513 case Work::kVerticalLine_Segment: 1514 case Work::kLine_Segment: { 1515 pts = VLineIntersect(wn.pts(), wt.top(), 1516 wt.bottom(), wt.x(), wt.yFlipped(), ts); 1517 break; 1518 } 1519 case Work::kQuad_Segment: { 1520 pts = VQuadIntersect(wn.pts(), wt.top(), 1521 wt.bottom(), wt.x(), wt.yFlipped(), ts); 1522 break; 1523 } 1524 case Work::kCubic_Segment: { 1525 pts = VCubicIntersect(wn.pts(), wt.top(), 1526 wt.bottom(), wt.x(), wt.yFlipped(), ts); 1527 break; 1528 } 1529 default: 1530 SkASSERT(0); 1531 } 1532 break; 1533 case Work::kLine_Segment: 1534 switch (wn.segmentType()) { 1535 case Work::kHorizontalLine_Segment: 1536 pts = HLineIntersect(wt.pts(), wn.left(), 1537 wn.right(), wn.y(), wn.xFlipped(), ts); 1538 break; 1539 case Work::kVerticalLine_Segment: 1540 pts = VLineIntersect(wt.pts(), wn.top(), 1541 wn.bottom(), wn.x(), wn.yFlipped(), ts); 1542 break; 1543 case Work::kLine_Segment: { 1544 pts = LineIntersect(wt.pts(), wn.pts(), ts); 1545 debugShowLineIntersection(pts, wt, wn, 1546 ts.fT[1], ts.fT[0]); 1547 break; 1548 } 1549 case Work::kQuad_Segment: { 1550 swap = true; 1551 pts = QuadLineIntersect(wn.pts(), wt.pts(), ts); 1552 break; 1553 } 1554 case Work::kCubic_Segment: { 1555 swap = true; 1556 pts = CubicLineIntersect(wn.pts(), wt.pts(), ts); 1557 break; 1558 } 1559 default: 1560 SkASSERT(0); 1561 } 1562 break; 1563 case Work::kQuad_Segment: 1564 switch (wn.segmentType()) { 1565 case Work::kHorizontalLine_Segment: 1566 pts = HQuadIntersect(wt.pts(), wn.left(), 1567 wn.right(), wn.y(), wn.xFlipped(), ts); 1568 break; 1569 case Work::kVerticalLine_Segment: 1570 pts = VQuadIntersect(wt.pts(), wn.top(), 1571 wn.bottom(), wn.x(), wn.yFlipped(), ts); 1572 break; 1573 case Work::kLine_Segment: { 1574 pts = QuadLineIntersect(wt.pts(), wn.pts(), ts); 1575 break; 1576 } 1577 case Work::kQuad_Segment: { 1578 pts = QuadIntersect(wt.pts(), wn.pts(), ts); 1579 break; 1580 } 1581 case Work::kCubic_Segment: { 1582 wt.promoteToCubic(); 1583 pts = CubicIntersect(wt.cubic(), wn.pts(), ts); 1584 break; 1585 } 1586 default: 1587 SkASSERT(0); 1588 } 1589 break; 1590 case Work::kCubic_Segment: 1591 switch (wn.segmentType()) { 1592 case Work::kHorizontalLine_Segment: 1593 pts = HCubicIntersect(wt.pts(), wn.left(), 1594 wn.right(), wn.y(), wn.xFlipped(), ts); 1595 break; 1596 case Work::kVerticalLine_Segment: 1597 pts = VCubicIntersect(wt.pts(), wn.top(), 1598 wn.bottom(), wn.x(), wn.yFlipped(), ts); 1599 break; 1600 case Work::kLine_Segment: { 1601 pts = CubicLineIntersect(wt.pts(), wn.pts(), ts); 1602 break; 1603 } 1604 case Work::kQuad_Segment: { 1605 wn.promoteToCubic(); 1606 pts = CubicIntersect(wt.pts(), wn.cubic(), ts); 1607 break; 1608 } 1609 case Work::kCubic_Segment: { 1610 pts = CubicIntersect(wt.pts(), wn.pts(), ts); 1611 break; 1612 } 1613 default: 1614 SkASSERT(0); 1615 } 1616 break; 1617 default: 1618 SkASSERT(0); 1619 } 1620 // in addition to recording T values, record matching segment 1621 int coincident = pts == 2 && wn.segmentType() <= Work::kLine_Segment 1622 && wt.segmentType() <= Work::kLine_Segment ? -1 :0; 1623 for (int pt = 0; pt < pts; ++pt) { 1624 SkASSERT(ts.fT[0][pt] >= 0 && ts.fT[0][pt] <= 1); 1625 SkASSERT(ts.fT[1][pt] >= 0 && ts.fT[1][pt] <= 1); 1626 int testTAt = wt.addT(ts.fT[swap][pt], wn, coincident); 1627 int nextTAt = wn.addT(ts.fT[!swap][pt], wt, coincident); 1628 wt.addOtherT(testTAt, ts.fT[!swap][pt]); 1629 wn.addOtherT(nextTAt, ts.fT[swap][pt]); 1630 coincident = -coincident; 1631 } 1632 } while (wn.advance()); 1633 } while (wt.advance()); 1634 return true; 1635} 1636 1637// see if coincidence is formed by clipping non-concident segments 1638static void coincidenceCheck(SkTDArray<Contour*>& contourList, int winding) { 1639 int contourCount = contourList.count(); 1640 for (size_t cIndex = 0; cIndex < contourCount; ++cIndex) { 1641 Contour* contour = contourList[cIndex]; 1642 contour->findTooCloseToCall(winding); 1643 } 1644} 1645 1646// Each segment may have an inside or an outside. Segments contained within 1647// winding may have insides on either side, and form a contour that should be 1648// ignored. Segments that are coincident with opposing direction segments may 1649// have outsides on either side, and should also disappear. 1650// 'Normal' segments will have one inside and one outside. Subsequent connections 1651// when winding should follow the intersection direction. If more than one edge 1652// is an option, choose first edge that continues the inside. 1653 1654static void bridge(SkTDArray<Contour*>& contourList) { 1655 int contourCount = contourList.count(); 1656 do { 1657 // OPTIMIZATION: not crazy about linear search here to find top active y. 1658 // seems like we should break down and do the sort, or maybe sort each 1659 // contours' segments? 1660 // Once the segment array is built, there's no reason I can think of not to 1661 // sort it in Y. hmmm 1662 int cIndex = 0; 1663 Segment* topStart; 1664 do { 1665 Contour* topContour = contourList[cIndex]; 1666 topStart = topContour->topSegment(); 1667 } while (!topStart && ++cIndex < contourCount); 1668 if (!topStart) { 1669 break; 1670 } 1671 SkScalar top = topStart->bounds().fTop; 1672 for (int cTest = cIndex + 1; cTest < contourCount; ++cTest) { 1673 Contour* contour = contourList[cTest]; 1674 if (top < contour->bounds().fTop) { 1675 continue; 1676 } 1677 Segment* test = contour->topSegment(); 1678 if (top > test->bounds().fTop) { 1679 cIndex = cTest; 1680 topStart = test; 1681 top = test->bounds().fTop; 1682 } 1683 } 1684 int index; 1685 const Segment* topSegment = topStart->findTop(index); 1686 // Start at the top. Above the top is outside, below is inside. 1687 // follow edges to intersection 1688 // at intersection, stay on outside, but mark remaining edges as inside 1689 // or, only mark first pair as inside? 1690 // how is this going to work for contained (but not intersecting) 1691 // segments? 1692 // start here ; 1693 // find span 1694 // mark neighbors winding coverage 1695 // output span 1696 // mark span as processed 1697 1698 } while (true); 1699 1700 1701} 1702 1703static void makeContourList(SkTArray<Contour>& contours, Contour& sentinel, 1704 SkTDArray<Contour*>& list) { 1705 int count = contours.count(); 1706 if (count == 0) { 1707 return; 1708 } 1709 for (int index = 0; index < count; ++index) { 1710 *list.append() = &contours[index]; 1711 } 1712 *list.append() = &sentinel; 1713 QSort<Contour>(list.begin(), list.end() - 1); 1714} 1715 1716void simplifyx(const SkPath& path, bool asFill, SkPath& simple) { 1717 // returns 1 for evenodd, -1 for winding, regardless of inverse-ness 1718 int winding = (path.getFillType() & 1) ? 1 : -1; 1719 simple.reset(); 1720 simple.setFillType(SkPath::kEvenOdd_FillType); 1721 1722 // turn path into list of segments 1723 SkTArray<Contour> contours; 1724 // FIXME: add self-intersecting cubics' T values to segment 1725 EdgeBuilder builder(path, contours); 1726 SkTDArray<Contour*> contourList; 1727 Contour sentinel; 1728 sentinel.reset(); 1729 makeContourList(contours, sentinel, contourList); 1730 Contour** currentPtr = contourList.begin(); 1731 if (!currentPtr) { 1732 return; 1733 } 1734 // find all intersections between segments 1735 do { 1736 Contour** nextPtr = currentPtr; 1737 Contour* current = *currentPtr++; 1738 Contour* next; 1739 do { 1740 next = *nextPtr++; 1741 } while (next != &sentinel && addIntersectTs(current, next, winding)); 1742 } while (*currentPtr != &sentinel); 1743 // eat through coincident edges 1744 coincidenceCheck(contourList, winding); 1745 // construct closed contours 1746 bridge(contourList); 1747} 1748 1749