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