Simplify.cpp revision fa4a6e964691ff9a88bc047418abe2d4324dfcae
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 01 45#define DEBUG_UNUSED 0 // set to expose unused functions 46#define DEBUG_MARK_DONE 01 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 bool activeAngles(int index) const { 650 double referenceT = fTs[index].fT; 651 int lesser = index; 652 while (--lesser >= 0 && referenceT - fTs[lesser].fT < FLT_EPSILON) { 653 if (activeAnglesInner(lesser)) { 654 return true; 655 } 656 } 657 do { 658 if (activeAnglesInner(index)) { 659 return true; 660 } 661 } while (++index < fTs.count() && fTs[index].fT - referenceT < FLT_EPSILON); 662 return false; 663 } 664 665 bool activeAnglesInner(int index) const { 666 Span* span = &fTs[index]; 667 Segment* other = span->fOther; 668 int oIndex = span->fOtherIndex; 669 int next = other->nextSpan(oIndex, 1); 670 if (next > 0 && !other->fTs[oIndex].fDone) { 671 return true; 672 } 673 int prev = other->nextSpan(oIndex, -1); 674 // edge leading into junction 675 return prev >= 0 && !other->fTs[prev].fDone; 676 } 677 678 SkScalar activeTop() const { 679 SkASSERT(!done()); 680 int count = fTs.count(); 681 SkScalar result = SK_ScalarMax; 682 bool lastDone = true; 683 for (int index = 0; index < count; ++index) { 684 bool done = fTs[index].fDone; 685 if (!done || !lastDone) { 686 SkScalar y = yAtT(index); 687 if (result > y) { 688 result = y; 689 } 690 } 691 lastDone = done; 692 } 693 SkASSERT(result < SK_ScalarMax); 694 return result; 695 } 696 697 void addAngle(SkTDArray<Angle>& angles, int start, int end) const { 698 SkASSERT(start != end); 699 SkPoint edge[4]; 700 (*SegmentSubDivide[fVerb])(fPts, fTs[start].fT, fTs[end].fT, edge); 701 Angle* angle = angles.append(); 702 angle->set(edge, fVerb, this, start, end); 703 } 704 705 void addCubic(const SkPoint pts[4]) { 706 init(pts, SkPath::kCubic_Verb); 707 fBounds.setCubicBounds(pts); 708 } 709 710 // FIXME: this needs to defer add for aligned consecutive line segments 711 SkPoint addCurveTo(int start, int end, SkPath& path, bool active) { 712 SkPoint edge[4]; 713 // OPTIMIZE? if not active, skip remainder and return xy_at_t(end) 714 (*SegmentSubDivide[fVerb])(fPts, fTs[start].fT, fTs[end].fT, edge); 715 if (active) { 716 #if DEBUG_PATH_CONSTRUCTION 717 SkDebugf("%s %s (%1.9g,%1.9g)", __FUNCTION__, 718 kLVerbStr[fVerb], edge[1].fX, edge[1].fY); 719 if (fVerb > 1) { 720 SkDebugf(" (%1.9g,%1.9g)", edge[2].fX, edge[2].fY); 721 } 722 if (fVerb > 2) { 723 SkDebugf(" (%1.9g,%1.9g)", edge[3].fX, edge[3].fY); 724 } 725 SkDebugf("\n"); 726 #endif 727 switch (fVerb) { 728 case SkPath::kLine_Verb: 729 path.lineTo(edge[1].fX, edge[1].fY); 730 break; 731 case SkPath::kQuad_Verb: 732 path.quadTo(edge[1].fX, edge[1].fY, edge[2].fX, edge[2].fY); 733 break; 734 case SkPath::kCubic_Verb: 735 path.cubicTo(edge[1].fX, edge[1].fY, edge[2].fX, edge[2].fY, 736 edge[3].fX, edge[3].fY); 737 break; 738 } 739 } 740 return edge[fVerb]; 741 } 742 743 void addLine(const SkPoint pts[2]) { 744 init(pts, SkPath::kLine_Verb); 745 fBounds.set(pts, 2); 746 } 747 748 const SkPoint& addMoveTo(int tIndex, SkPath& path, bool active) { 749 const SkPoint& pt = xyAtT(tIndex); 750 if (active) { 751 #if DEBUG_PATH_CONSTRUCTION 752 SkDebugf("%s (%1.9g,%1.9g)\n", __FUNCTION__, pt.fX, pt.fY); 753 #endif 754 path.moveTo(pt.fX, pt.fY); 755 } 756 return pt; 757 } 758 759 // add 2 to edge or out of range values to get T extremes 760 void addOtherT(int index, double otherT, int otherIndex) { 761 Span& span = fTs[index]; 762 span.fOtherT = otherT; 763 span.fOtherIndex = otherIndex; 764 } 765 766 void addQuad(const SkPoint pts[3]) { 767 init(pts, SkPath::kQuad_Verb); 768 fBounds.setQuadBounds(pts); 769 } 770 771 // Defer all coincident edge processing until 772 // after normal intersections have been computed 773 774// no need to be tricky; insert in normal T order 775// resolve overlapping ts when considering coincidence later 776 777 // add non-coincident intersection. Resulting edges are sorted in T. 778 int addT(double newT, Segment* other) { 779 // FIXME: in the pathological case where there is a ton of intercepts, 780 // binary search? 781 int insertedAt = -1; 782 size_t tCount = fTs.count(); 783 for (size_t index = 0; index < tCount; ++index) { 784 // OPTIMIZATION: if there are three or more identical Ts, then 785 // the fourth and following could be further insertion-sorted so 786 // that all the edges are clockwise or counterclockwise. 787 // This could later limit segment tests to the two adjacent 788 // neighbors, although it doesn't help with determining which 789 // circular direction to go in. 790 if (newT < fTs[index].fT) { 791 insertedAt = index; 792 break; 793 } 794 } 795 Span* span; 796 if (insertedAt >= 0) { 797 span = fTs.insert(insertedAt); 798 } else { 799 insertedAt = tCount; 800 span = fTs.append(); 801 } 802 span->fT = newT; 803 span->fOther = other; 804 span->fPt = NULL; 805 span->fWindSum = SK_MinS32; 806 span->fWindValue = 1; 807 if ((span->fDone = newT == 1)) { 808 ++fDoneSpans; 809 } 810 return insertedAt; 811 } 812 813 // set spans from start to end to decrement by one 814 // note this walks other backwards 815 // FIMXE: there's probably an edge case that can be constructed where 816 // two span in one segment are separated by float epsilon on one span but 817 // not the other, if one segment is very small. For this 818 // case the counts asserted below may or may not be enough to separate the 819 // spans. Even if the counts work out, what if the spanw aren't correctly 820 // sorted? It feels better in such a case to match the span's other span 821 // pointer since both coincident segments must contain the same spans. 822 void addTCancel(double startT, double endT, Segment& other, 823 double oStartT, double oEndT) { 824 SkASSERT(endT - startT >= FLT_EPSILON); 825 SkASSERT(oEndT - oStartT >= FLT_EPSILON); 826 int index = 0; 827 while (startT - fTs[index].fT >= FLT_EPSILON) { 828 ++index; 829 } 830 int oIndex = other.fTs.count(); 831 while (other.fTs[--oIndex].fT - oEndT > -FLT_EPSILON) 832 ; 833 Span* test = &fTs[index]; 834 Span* oTest = &other.fTs[oIndex]; 835 do { 836 bool decrement = test->fWindValue && oTest->fWindValue; 837 Span* end = test; 838 do { 839 if (decrement) { 840 SkASSERT(end->fWindValue > 0); 841 if (--(end->fWindValue) == 0) { 842 end->fDone = true; 843 ++fDoneSpans; 844 } 845 } 846 end = &fTs[++index]; 847 } while (end->fT - test->fT < FLT_EPSILON); 848 Span* oTestStart = oTest; 849 do { 850 if (decrement) { 851 SkASSERT(oTestStart->fWindValue > 0); 852 if (--(oTestStart->fWindValue) == 0) { 853 oTestStart->fDone = true; 854 ++other.fDoneSpans; 855 } 856 } 857 if (!oIndex) { 858 break; 859 } 860 oTestStart = &other.fTs[--oIndex]; 861 } while (oTest->fT - oTestStart->fT < FLT_EPSILON); 862 test = end; 863 oTest = oTestStart; 864 } while (test->fT < endT - FLT_EPSILON); 865 SkASSERT(!oIndex || oTest->fT <= oStartT - FLT_EPSILON); 866 } 867 868 // set spans from start to end to increment the greater by one and decrement 869 // the lesser 870 void addTCoincident(double startT, double endT, Segment& other, 871 double oStartT, double oEndT) { 872 SkASSERT(endT - startT >= FLT_EPSILON); 873 SkASSERT(oEndT - oStartT >= FLT_EPSILON); 874 int index = 0; 875 while (startT - fTs[index].fT >= FLT_EPSILON) { 876 ++index; 877 } 878 int oIndex = 0; 879 while (oStartT - other.fTs[oIndex].fT >= FLT_EPSILON) { 880 ++oIndex; 881 } 882 Span* test = &fTs[index]; 883 Span* oTest = &other.fTs[oIndex]; 884 SkTDArray<double> outsideTs; 885 SkTDArray<double> oOutsideTs; 886 do { 887 bool transfer = test->fWindValue && oTest->fWindValue; 888 bool decrementOther = test->fWindValue >= oTest->fWindValue; 889 Span* end = test; 890 double startT = end->fT; 891 double oStartT = oTest->fT; 892 do { 893 if (transfer) { 894 if (decrementOther) { 895 ++(end->fWindValue); 896 } else { 897 SkASSERT(end->fWindValue > 0); 898 if (--(end->fWindValue) == 0) { 899 end->fDone = true; 900 ++fDoneSpans; 901 int outCount = outsideTs.count(); 902 if (outCount == 0 || end->fT - outsideTs[outCount - 2] 903 >= FLT_EPSILON) { 904 *outsideTs.append() = end->fT; 905 *outsideTs.append() = oStartT; 906 } 907 } 908 } 909 } 910 end = &fTs[++index]; 911 } while (end->fT - test->fT < FLT_EPSILON); 912 Span* oEnd = oTest; 913 do { 914 if (transfer) { 915 if (decrementOther) { 916 SkASSERT(oEnd->fWindValue > 0); 917 if (--(oEnd->fWindValue) == 0) { 918 oEnd->fDone = true; 919 ++other.fDoneSpans; 920 int oOutCount = oOutsideTs.count(); 921 if (oOutCount == 0 || oEnd->fT 922 - oOutsideTs[oOutCount - 2] >= FLT_EPSILON) { 923 *oOutsideTs.append() = oEnd->fT; 924 *oOutsideTs.append() = startT; 925 } 926 } 927 } else { 928 ++(oEnd->fWindValue); 929 } 930 } 931 oEnd = &other.fTs[++oIndex]; 932 } while (oEnd->fT - oTest->fT < FLT_EPSILON); 933 test = end; 934 oTest = oEnd; 935 } while (test->fT < endT - FLT_EPSILON); 936 SkASSERT(oTest->fT < oEndT + FLT_EPSILON); 937 SkASSERT(oTest->fT > oEndT - FLT_EPSILON); 938 if (!done() && outsideTs.count()) { 939 addTOutsides(outsideTs, other, oEndT); 940 } 941 if (!other.done() && oOutsideTs.count()) { 942 other.addTOutsides(oOutsideTs, *this, endT); 943 } 944 } 945 946 void addTOutsides(const SkTDArray<double>& outsideTs, Segment& other, 947 double otherEnd) { 948 int count = outsideTs.count(); 949 double endT = 0; 950 int endSpan = 0; 951 for (int index = 0; index < count; index += 2) { 952 double t = outsideTs[index]; 953 double otherT = outsideTs[index + 1]; 954 if (t > 1 - FLT_EPSILON) { 955 return; 956 } 957 if (t - endT > FLT_EPSILON) { 958 endSpan = addTDonePair(t, other, otherT); 959 } 960 do { 961 endT = fTs[++endSpan].fT; 962 } while (endT - t < FLT_EPSILON); 963 } 964 addTPair(endT, other, otherEnd); 965 } 966 967 // match the other.fWindValue to its mates 968 int addTDonePair(double t, Segment& other, double otherT) { 969 int insertedAt = addTPair(t, other, otherT); 970 Span& end = fTs[insertedAt]; 971 SkASSERT(end.fWindValue == 1); 972 end.fWindValue = 0; 973 end.fDone = true; 974 ++fDoneSpans; 975 Span& otherEnd = other.fTs[end.fOtherIndex]; 976 Span* match = NULL; 977 if (end.fOtherIndex > 0) { 978 match = &other.fTs[end.fOtherIndex - 1]; 979 } 980 if (!match || match->fT < otherT) { 981 match = &other.fTs[end.fOtherIndex + 1]; 982 } 983 otherEnd.fWindValue = match->fWindValue; 984 return insertedAt; 985 } 986 987 int addTPair(double t, Segment& other, double otherT) { 988 int insertedAt = addT(t, &other); 989 int otherInsertedAt = other.addT(otherT, this); 990 addOtherT(insertedAt, otherT, otherInsertedAt); 991 other.addOtherT(otherInsertedAt, t, insertedAt); 992 return insertedAt; 993 } 994 995 void addTwoAngles(int start, int end, SkTDArray<Angle>& angles) const { 996 // add edge leading into junction 997 if (fTs[SkMin32(end, start)].fWindValue > 0) { 998 addAngle(angles, end, start); 999 } 1000 // add edge leading away from junction 1001 int step = SkSign32(end - start); 1002 int tIndex = nextSpan(end, step); 1003 if (tIndex >= 0 && fTs[SkMin32(end, tIndex)].fWindValue > 0) { 1004 addAngle(angles, end, tIndex); 1005 } 1006 } 1007 1008 const Bounds& bounds() const { 1009 return fBounds; 1010 } 1011 1012 void buildAngles(int index, SkTDArray<Angle>& angles) const { 1013 double referenceT = fTs[index].fT; 1014 int lesser = index; 1015 while (--lesser >= 0 && referenceT - fTs[lesser].fT < FLT_EPSILON) { 1016 buildAnglesInner(lesser, angles); 1017 } 1018 do { 1019 buildAnglesInner(index, angles); 1020 } while (++index < fTs.count() && fTs[index].fT - referenceT < FLT_EPSILON); 1021 } 1022 1023 void buildAnglesInner(int index, SkTDArray<Angle>& angles) const { 1024 Span* span = &fTs[index]; 1025 Segment* other = span->fOther; 1026 // if there is only one live crossing, and no coincidence, continue 1027 // in the same direction 1028 // if there is coincidence, the only choice may be to reverse direction 1029 // find edge on either side of intersection 1030 int oIndex = span->fOtherIndex; 1031 // if done == -1, prior span has already been processed 1032 int step = 1; 1033 int next = other->nextSpan(oIndex, step); 1034 if (next < 0) { 1035 step = -step; 1036 next = other->nextSpan(oIndex, step); 1037 } 1038 // add candidate into and away from junction 1039 other->addTwoAngles(next, oIndex, angles); 1040 } 1041 1042 bool cancels(const Segment& other) const { 1043 SkASSERT(fVerb == SkPath::kLine_Verb); 1044 SkASSERT(other.fVerb == SkPath::kLine_Verb); 1045 SkPoint dxy = fPts[0] - fPts[1]; 1046 SkPoint odxy = other.fPts[0] - other.fPts[1]; 1047 return dxy.fX * odxy.fX < 0 || dxy.fY * odxy.fY < 0; 1048 } 1049 1050 // figure out if the segment's ascending T goes clockwise or not 1051 // not enough context to write this as shown 1052 // instead, add all segments meeting at the top 1053 // sort them using buildAngleList 1054 // find the first in the sort 1055 // see if ascendingT goes to top 1056 bool clockwise(int /* tIndex */) const { 1057 SkASSERT(0); // incomplete 1058 return false; 1059 } 1060 1061 int crossedSpan(const SkPoint& basePt, SkScalar& bestY, double& hitT) const { 1062 int start = 0; 1063 int bestT = -1; 1064 SkScalar top = bounds().fTop; 1065 SkScalar bottom = bounds().fBottom; 1066 int end; 1067 do { 1068 end = nextSpan(start, 1); 1069 SkPoint edge[4]; 1070 // OPTIMIZE: wrap this so that if start==0 end==fTCount-1 we can 1071 // work with the original data directly 1072 (*SegmentSubDivide[fVerb])(fPts, fTs[start].fT, fTs[end].fT, edge); 1073 // intersect ray starting at basePt with edge 1074 Intersections intersections; 1075 int pts = (*VSegmentIntersect[fVerb])(edge, top, bottom, basePt.fX, 1076 false, intersections); 1077 if (pts == 0) { 1078 continue; 1079 } 1080 if (pts > 1 && fVerb == SkPath::kLine_Verb) { 1081 // if the intersection is edge on, wait for another one 1082 continue; 1083 } 1084 SkASSERT(pts == 1); // FIXME: more code required to disambiguate 1085 SkPoint pt; 1086 double foundT = intersections.fT[0][0]; 1087 (*SegmentXYAtT[fVerb])(fPts, foundT, &pt); 1088 if (bestY < pt.fY) { 1089 bestY = pt.fY; 1090 bestT = foundT < 1 ? start : end; 1091 hitT = foundT; 1092 } 1093 start = end; 1094 } while (fTs[end].fT != 1); 1095 return bestT; 1096 } 1097 1098 bool done() const { 1099 SkASSERT(fDoneSpans <= fTs.count()); 1100 return fDoneSpans == fTs.count(); 1101 } 1102 1103 // so the span needs to contain the pairing info found here 1104 // this should include the winding computed for the edge, and 1105 // what edge it connects to, and whether it is discarded 1106 // (maybe discarded == abs(winding) > 1) ? 1107 // only need derivatives for duration of sorting, add a new struct 1108 // for pairings, remove extra spans that have zero length and 1109 // reference an unused other 1110 // for coincident, the last span on the other may be marked done 1111 // (always?) 1112 1113 // if loop is exhausted, contour may be closed. 1114 // FIXME: pass in close point so we can check for closure 1115 1116 // given a segment, and a sense of where 'inside' is, return the next 1117 // segment. If this segment has an intersection, or ends in multiple 1118 // segments, find the mate that continues the outside. 1119 // note that if there are multiples, but no coincidence, we can limit 1120 // choices to connections in the correct direction 1121 1122 // mark found segments as done 1123 1124 // start is the index of the beginning T of this edge 1125 // it is guaranteed to have an end which describes a non-zero length (?) 1126 // winding -1 means ccw, 1 means cw 1127 // firstFind allows coincident edges to be treated differently 1128 Segment* findNext(SkTDArray<Span*>& chase, int winding, const int startIndex, 1129 const int endIndex, 1130 int& nextStart, int& nextEnd, int& flipped, bool firstFind) { 1131 SkASSERT(startIndex != endIndex); 1132 int count = fTs.count(); 1133 SkASSERT(startIndex < endIndex ? startIndex < count - 1 1134 : startIndex > 0); 1135 int step = SkSign32(endIndex - startIndex); 1136 int end = nextSpan(startIndex, step); 1137 SkASSERT(end >= 0); 1138 Span* endSpan = &fTs[end]; 1139 Segment* other; 1140 if (isSimple(end)) { 1141 // mark the smaller of startIndex, endIndex done, and all adjacent 1142 // spans with the same T value (but not 'other' spans) 1143 markDone(SkMin32(startIndex, endIndex), winding); 1144 other = endSpan->fOther; 1145 nextStart = endSpan->fOtherIndex; 1146 nextEnd = nextStart + step; 1147 SkASSERT(step < 0 ? nextEnd >= 0 : nextEnd < other->fTs.count()); 1148 return other; 1149 } 1150 // more than one viable candidate -- measure angles to find best 1151 SkTDArray<Angle> angles; 1152 SkASSERT(startIndex - endIndex != 0); 1153 SkASSERT((startIndex - endIndex < 0) ^ (step < 0)); 1154 addTwoAngles(startIndex, end, angles); 1155 buildAngles(end, angles); 1156 SkTDArray<Angle*> sorted; 1157 sortAngles(angles, sorted); 1158 int angleCount = angles.count(); 1159 int firstIndex = findStartingEdge(sorted, startIndex, end); 1160 1161 SkASSERT(firstIndex >= 0); 1162 int startWinding = winding; 1163 int nextIndex = firstIndex + 1; 1164 int lastIndex = firstIndex != 0 ? firstIndex : angleCount; 1165 const Angle* foundAngle = NULL; 1166 // iterate through the angle, and compute everyone's winding 1167 bool firstEdge = true; 1168 do { 1169 if (nextIndex == angleCount) { 1170 nextIndex = 0; 1171 } 1172 const Angle* nextAngle = sorted[nextIndex]; 1173 int maxWinding = winding; 1174 Segment* nextSegment = nextAngle->segment(); 1175 int windValue = nextSegment->windValue(nextAngle); 1176 SkASSERT(windValue > 0); 1177 winding -= nextAngle->sign() * windValue; 1178 #if DEBUG_WINDING 1179 SkDebugf("%s maxWinding=%d winding=%d\n", __FUNCTION__, maxWinding, 1180 winding); 1181 #endif 1182 if (maxWinding * winding < 0) { 1183 flipped = -flipped; 1184 SkDebugf("flipped sign %d %d\n", maxWinding, winding); 1185 } 1186 firstEdge = false; 1187 if (!winding) { 1188 if (!foundAngle) { 1189 foundAngle = nextAngle; 1190 } 1191 continue; 1192 } 1193 if (nextSegment->done()) { 1194 continue; 1195 } 1196 // if the winding is non-zero, nextAngle does not connect to 1197 // current chain. If we haven't done so already, mark the angle 1198 // as done, record the winding value, and mark connected unambiguous 1199 // segments as well. 1200 if (nextSegment->windSum(nextAngle) == SK_MinS32) { 1201 if (abs(maxWinding) < abs(winding)) { 1202 maxWinding = winding; 1203 } 1204 Span* last; 1205 if (foundAngle) { 1206 last = nextSegment->markAndChaseWinding(nextAngle, maxWinding); 1207 } else { 1208 last = nextSegment->markAndChaseDone(nextAngle, maxWinding); 1209 } 1210 if (last) { 1211 *chase.append() = last; 1212 } 1213 } 1214 } while (++nextIndex != lastIndex); 1215 sorted[firstIndex]->segment()-> 1216 markDone(SkMin32(startIndex, endIndex), startWinding); 1217 if (!foundAngle) { 1218 return NULL; 1219 } 1220 nextStart = foundAngle->start(); 1221 nextEnd = foundAngle->end(); 1222 return foundAngle->segment(); 1223 } 1224 1225 int findStartingEdge(SkTDArray<Angle*>& sorted, int start, int end) { 1226 int angleCount = sorted.count(); 1227 int firstIndex = -1; 1228 for (int angleIndex = 0; angleIndex < angleCount; ++angleIndex) { 1229 const Angle* angle = sorted[angleIndex]; 1230 if (angle->segment() == this && angle->start() == end && 1231 angle->end() == start) { 1232 firstIndex = angleIndex; 1233 break; 1234 } 1235 } 1236 return firstIndex; 1237 } 1238 1239 // FIXME: this is tricky code; needs its own unit test 1240 void findTooCloseToCall(int /* winding */ ) { // FIXME: winding should be considered 1241 int count = fTs.count(); 1242 if (count < 3) { // require t=0, x, 1 at minimum 1243 return; 1244 } 1245 int matchIndex = 0; 1246 int moCount; 1247 Span* match; 1248 Segment* mOther; 1249 do { 1250 match = &fTs[matchIndex]; 1251 mOther = match->fOther; 1252 moCount = mOther->fTs.count(); 1253 if (moCount >= 3) { 1254 break; 1255 } 1256 if (++matchIndex >= count) { 1257 return; 1258 } 1259 } while (true); // require t=0, x, 1 at minimum 1260 // OPTIMIZATION: defer matchPt until qualifying toCount is found? 1261 const SkPoint* matchPt = &xyAtT(match); 1262 // look for a pair of nearby T values that map to the same (x,y) value 1263 // if found, see if the pair of other segments share a common point. If 1264 // so, the span from here to there is coincident. 1265 for (int index = matchIndex + 1; index < count; ++index) { 1266 Span* test = &fTs[index]; 1267 if (test->fDone) { 1268 continue; 1269 } 1270 Segment* tOther = test->fOther; 1271 int toCount = tOther->fTs.count(); 1272 if (toCount < 3) { // require t=0, x, 1 at minimum 1273 continue; 1274 } 1275 const SkPoint* testPt = &xyAtT(test); 1276 if (*matchPt != *testPt) { 1277 matchIndex = index; 1278 moCount = toCount; 1279 match = test; 1280 mOther = tOther; 1281 matchPt = testPt; 1282 continue; 1283 } 1284 int moStart = -1; 1285 int moEnd = -1; 1286 double moStartT, moEndT; 1287 for (int moIndex = 0; moIndex < moCount; ++moIndex) { 1288 Span& moSpan = mOther->fTs[moIndex]; 1289 if (moSpan.fDone) { 1290 continue; 1291 } 1292 if (moSpan.fOther == this) { 1293 if (moSpan.fOtherT == match->fT) { 1294 moStart = moIndex; 1295 moStartT = moSpan.fT; 1296 } 1297 continue; 1298 } 1299 if (moSpan.fOther == tOther) { 1300 SkASSERT(moEnd == -1); 1301 moEnd = moIndex; 1302 moEndT = moSpan.fT; 1303 } 1304 } 1305 if (moStart < 0 || moEnd < 0) { 1306 continue; 1307 } 1308 // FIXME: if moStartT, moEndT are initialized to NaN, can skip this test 1309 if (moStartT == moEndT) { 1310 continue; 1311 } 1312 int toStart = -1; 1313 int toEnd = -1; 1314 double toStartT, toEndT; 1315 for (int toIndex = 0; toIndex < toCount; ++toIndex) { 1316 Span& toSpan = tOther->fTs[toIndex]; 1317 if (toSpan.fOther == this) { 1318 if (toSpan.fOtherT == test->fT) { 1319 toStart = toIndex; 1320 toStartT = toSpan.fT; 1321 } 1322 continue; 1323 } 1324 if (toSpan.fOther == mOther && toSpan.fOtherT == moEndT) { 1325 SkASSERT(toEnd == -1); 1326 toEnd = toIndex; 1327 toEndT = toSpan.fT; 1328 } 1329 } 1330 // FIXME: if toStartT, toEndT are initialized to NaN, can skip this test 1331 if (toStart <= 0 || toEnd <= 0) { 1332 continue; 1333 } 1334 if (toStartT == toEndT) { 1335 continue; 1336 } 1337 // test to see if the segment between there and here is linear 1338 if (!mOther->isLinear(moStart, moEnd) 1339 || !tOther->isLinear(toStart, toEnd)) { 1340 continue; 1341 } 1342 // FIXME: defer implementation until the rest works 1343 // this may share code with regular coincident detection 1344 SkASSERT(0); 1345 #if 0 1346 if (flipped) { 1347 mOther->addTCancel(moStart, moEnd, tOther, tStart, tEnd); 1348 } else { 1349 mOther->addTCoincident(moStart, moEnd, tOther, tStart, tEnd); 1350 } 1351 #endif 1352 } 1353 } 1354 1355 // OPTIMIZATION : for a pair of lines, can we compute points at T (cached) 1356 // and use more concise logic like the old edge walker code? 1357 // FIXME: this needs to deal with coincident edges 1358 Segment* findTop(int& tIndex, int& endIndex) { 1359 // iterate through T intersections and return topmost 1360 // topmost tangent from y-min to first pt is closer to horizontal 1361 SkASSERT(!done()); 1362 int firstT; 1363 int lastT; 1364 SkPoint topPt; 1365 topPt.fY = SK_ScalarMax; 1366 int count = fTs.count(); 1367 // see if either end is not done since we want smaller Y of the pair 1368 bool lastDone = true; 1369 for (int index = 0; index < count; ++index) { 1370 const Span& span = fTs[index]; 1371 if (!span.fDone || !lastDone) { 1372 const SkPoint& intercept = xyAtT(&span); 1373 if (topPt.fY > intercept.fY || (topPt.fY == intercept.fY 1374 && topPt.fX > intercept.fX)) { 1375 topPt = intercept; 1376 firstT = lastT = index; 1377 } else if (topPt == intercept) { 1378 lastT = index; 1379 } 1380 } 1381 lastDone = span.fDone; 1382 } 1383 // sort the edges to find the leftmost 1384 int step = 1; 1385 int end = nextSpan(firstT, step); 1386 if (end == -1) { 1387 step = -1; 1388 end = nextSpan(firstT, step); 1389 SkASSERT(end != -1); 1390 } 1391 // if the topmost T is not on end, or is three-way or more, find left 1392 // look for left-ness from tLeft to firstT (matching y of other) 1393 SkTDArray<Angle> angles; 1394 SkASSERT(firstT - end != 0); 1395 addTwoAngles(end, firstT, angles); 1396 buildAngles(firstT, angles); 1397 SkTDArray<Angle*> sorted; 1398 sortAngles(angles, sorted); 1399 // skip edges that have already been processed 1400 firstT = -1; 1401 Segment* leftSegment; 1402 do { 1403 const Angle* angle = sorted[++firstT]; 1404 leftSegment = angle->segment(); 1405 tIndex = angle->end(); 1406 endIndex = angle->start(); 1407 } while (leftSegment->fTs[SkMin32(tIndex, endIndex)].fDone); 1408 return leftSegment; 1409 } 1410 1411 // FIXME: not crazy about this 1412 // when the intersections are performed, the other index is into an 1413 // incomplete array. as the array grows, the indices become incorrect 1414 // while the following fixes the indices up again, it isn't smart about 1415 // skipping segments whose indices are already correct 1416 // assuming we leave the code that wrote the index in the first place 1417 void fixOtherTIndex() { 1418 int iCount = fTs.count(); 1419 for (int i = 0; i < iCount; ++i) { 1420 Span& iSpan = fTs[i]; 1421 double oT = iSpan.fOtherT; 1422 Segment* other = iSpan.fOther; 1423 int oCount = other->fTs.count(); 1424 for (int o = 0; o < oCount; ++o) { 1425 Span& oSpan = other->fTs[o]; 1426 if (oT == oSpan.fT && this == oSpan.fOther) { 1427 iSpan.fOtherIndex = o; 1428 break; 1429 } 1430 } 1431 } 1432 } 1433 1434 // OPTIMIZATION: uses tail recursion. Unwise? 1435 Span* innerChaseDone(int index, int step, int winding) { 1436 int end = nextSpan(index, step); 1437 if (multipleSpans(index, end)) { 1438 return index >= 0 ? &fTs[index] : NULL; 1439 } 1440 const Span& endSpan = fTs[end]; 1441 Segment* other = endSpan.fOther; 1442 index = endSpan.fOtherIndex; 1443 int otherEnd = other->nextSpan(index, step); 1444 Span* last = other->innerChaseDone(index, step, winding); 1445 other->markDone(SkMin32(index, otherEnd), winding); 1446 return last; 1447 } 1448 1449 Span* innerChaseWinding(int index, int step, int winding) { 1450 int end = nextSpan(index, step); 1451 if (multipleSpans(index, end)) { 1452 return index >= 0 ? &fTs[index] : NULL; 1453 } 1454 const Span& endSpan = fTs[end]; 1455 Segment* other = endSpan.fOther; 1456 index = endSpan.fOtherIndex; 1457 int otherEnd = other->nextSpan(index, step); 1458 int min = SkMin32(index, otherEnd); 1459 if (other->fTs[min].fWindSum != SK_MinS32) { 1460 SkASSERT(other->fTs[index].fWindSum == winding); 1461 return NULL; 1462 } 1463 Span* last = other->innerChaseWinding(index, step, winding); 1464 other->markWinding(min, winding); 1465 return last; 1466 } 1467 1468 void init(const SkPoint pts[], SkPath::Verb verb) { 1469 fPts = pts; 1470 fVerb = verb; 1471 fDoneSpans = 0; 1472 } 1473 1474 bool intersected() const { 1475 return fTs.count() > 0; 1476 } 1477 1478 bool isLinear(int start, int end) const { 1479 if (fVerb == SkPath::kLine_Verb) { 1480 return true; 1481 } 1482 if (fVerb == SkPath::kQuad_Verb) { 1483 SkPoint qPart[3]; 1484 QuadSubDivide(fPts, fTs[start].fT, fTs[end].fT, qPart); 1485 return QuadIsLinear(qPart); 1486 } else { 1487 SkASSERT(fVerb == SkPath::kCubic_Verb); 1488 SkPoint cPart[4]; 1489 CubicSubDivide(fPts, fTs[start].fT, fTs[end].fT, cPart); 1490 return CubicIsLinear(cPart); 1491 } 1492 } 1493 1494 // OPTIMIZE: successive calls could start were the last leaves off 1495 // or calls could specialize to walk forwards or backwards 1496 bool isMissing(double startT) const { 1497 size_t tCount = fTs.count(); 1498 for (size_t index = 0; index < tCount; ++index) { 1499 if (fabs(startT - fTs[index].fT) < FLT_EPSILON) { 1500 return false; 1501 } 1502 } 1503 return true; 1504 } 1505 1506 bool isSimple(int end) const { 1507 int count = fTs.count(); 1508 if (count == 2) { 1509 return true; 1510 } 1511 double t = fTs[end].fT; 1512 if (t < FLT_EPSILON) { 1513 return fTs[1].fT >= FLT_EPSILON; 1514 } 1515 if (t > 1 - FLT_EPSILON) { 1516 return fTs[count - 2].fT <= 1 - FLT_EPSILON; 1517 } 1518 return false; 1519 } 1520 1521 bool isHorizontal() const { 1522 return fBounds.fTop == fBounds.fBottom; 1523 } 1524 1525 bool isVertical() const { 1526 return fBounds.fLeft == fBounds.fRight; 1527 } 1528 1529 SkScalar leftMost(int start, int end) const { 1530 return (*SegmentLeftMost[fVerb])(fPts, fTs[start].fT, fTs[end].fT); 1531 } 1532 1533 // this span is excluded by the winding rule -- chase the ends 1534 // as long as they are unambiguous to mark connections as done 1535 // and give them the same winding value 1536 Span* markAndChaseDone(const Angle* angle, int winding) { 1537 int index = angle->start(); 1538 int endIndex = angle->end(); 1539 int step = SkSign32(endIndex - index); 1540 Span* last = innerChaseDone(index, step, winding); 1541 markDone(SkMin32(index, endIndex), winding); 1542 return last; 1543 } 1544 1545 Span* markAndChaseWinding(const Angle* angle, int winding) { 1546 int index = angle->start(); 1547 int endIndex = angle->end(); 1548 int min = SkMin32(index, endIndex); 1549 int step = SkSign32(endIndex - index); 1550 Span* last = innerChaseWinding(index, step, winding); 1551 markWinding(min, winding); 1552 return last; 1553 } 1554 1555 // FIXME: this should also mark spans with equal (x,y) 1556 // This may be called when the segment is already marked done. While this 1557 // wastes time, it shouldn't do any more than spin through the T spans. 1558 // OPTIMIZATION: abort on first done found (assuming that this code is 1559 // always called to mark segments done). 1560 void markDone(int index, int winding) { 1561 // SkASSERT(!done()); 1562 double referenceT = fTs[index].fT; 1563 int lesser = index; 1564 while (--lesser >= 0 && referenceT - fTs[lesser].fT < FLT_EPSILON) { 1565 Span& span = fTs[lesser]; 1566 if (span.fDone) { 1567 continue; 1568 } 1569 #if DEBUG_MARK_DONE 1570 const SkPoint& pt = xyAtT(&span); 1571 SkDebugf("%s segment=%d index=%d t=%1.9g pt=(%1.9g,%1.9g) wind=%d\n", 1572 __FUNCTION__, fID, lesser, span.fT, pt.fX, pt.fY, winding); 1573 #endif 1574 span.fDone = true; 1575 SkASSERT(span.fWindSum == SK_MinS32 || span.fWindSum == winding); 1576 span.fWindSum = winding; 1577 fDoneSpans++; 1578 } 1579 do { 1580 Span& span = fTs[index]; 1581 // SkASSERT(!span.fDone); 1582 if (span.fDone) { 1583 continue; 1584 } 1585 #if DEBUG_MARK_DONE 1586 const SkPoint& pt = xyAtT(&span); 1587 SkDebugf("%s segment=%d index=%d t=%1.9g pt=(%1.9g,%1.9g) wind=%d\n", 1588 __FUNCTION__, fID, index, span.fT, pt.fX, pt.fY, winding); 1589 #endif 1590 span.fDone = true; 1591 SkASSERT(span.fWindSum == SK_MinS32 || span.fWindSum == winding); 1592 span.fWindSum = winding; 1593 fDoneSpans++; 1594 } while (++index < fTs.count() && fTs[index].fT - referenceT < FLT_EPSILON); 1595 } 1596 1597 void markWinding(int index, int winding) { 1598 SkASSERT(!done()); 1599 double referenceT = fTs[index].fT; 1600 int lesser = index; 1601 while (--lesser >= 0 && referenceT - fTs[lesser].fT < FLT_EPSILON) { 1602 Span& span = fTs[lesser]; 1603 if (span.fDone) { 1604 continue; 1605 } 1606 SkASSERT(span.fWindValue == 1 || winding == 0); 1607 SkASSERT(span.fWindSum == SK_MinS32 || span.fWindSum == winding); 1608 #if DEBUG_MARK_DONE 1609 const SkPoint& pt = xyAtT(&span); 1610 SkDebugf("%s segment=%d index=%d t=%1.9g pt=(%1.9g,%1.9g) wind=%d\n", 1611 __FUNCTION__, fID, lesser, span.fT, pt.fX, pt.fY, winding); 1612 #endif 1613 span.fWindSum = winding; 1614 } 1615 do { 1616 Span& span = fTs[index]; 1617 // SkASSERT(!span.fDone || span.fCoincident); 1618 if (span.fDone) { 1619 continue; 1620 } 1621 SkASSERT(span.fWindValue == 1 || winding == 0); 1622 SkASSERT(span.fWindSum == SK_MinS32 || span.fWindSum == winding); 1623 #if DEBUG_MARK_DONE 1624 const SkPoint& pt = xyAtT(&span); 1625 SkDebugf("%s segment=%d index=%d t=%1.9g pt=(%1.9g,%1.9g) wind=%d\n", 1626 __FUNCTION__, fID, index, span.fT, pt.fX, pt.fY, winding); 1627 #endif 1628 span.fWindSum = winding; 1629 } while (++index < fTs.count() && fTs[index].fT - referenceT < FLT_EPSILON); 1630 } 1631 1632 bool multipleSpans(int& index, int end) const { 1633 if (end > index ? end + 1 >= fTs.count() : end <= 0) { 1634 return false; 1635 } 1636 // return span if when chasing, two or more radiating spans are not done 1637 int lesser = SkMin32(index, end); 1638 if (!activeAngles(lesser)) { 1639 index = -1; 1640 } 1641 index = lesser; 1642 return true; 1643 } 1644 1645 // This has callers for two different situations: one establishes the end 1646 // of the current span, and one establishes the beginning of the next span 1647 // (thus the name). When this is looking for the end of the current span, 1648 // coincidence is found when the beginning Ts contain -step and the end 1649 // contains step. When it is looking for the beginning of the next, the 1650 // first Ts found can be ignored and the last Ts should contain -step. 1651 // OPTIMIZATION: probably should split into two functions 1652 int nextSpan(int from, int step) const { 1653 const Span& fromSpan = fTs[from]; 1654 int count = fTs.count(); 1655 int to = from; 1656 while (step > 0 ? ++to < count : --to >= 0) { 1657 const Span& span = fTs[to]; 1658 if ((step > 0 ? span.fT - fromSpan.fT : fromSpan.fT - span.fT) < FLT_EPSILON) { 1659 continue; 1660 } 1661 return to; 1662 } 1663 return -1; 1664 } 1665 1666 const SkPoint* pts() const { 1667 return fPts; 1668 } 1669 1670 void reset() { 1671 init(NULL, (SkPath::Verb) -1); 1672 fBounds.set(SK_ScalarMax, SK_ScalarMax, SK_ScalarMax, SK_ScalarMax); 1673 fTs.reset(); 1674 } 1675 1676 // OPTIMIZATION: mark as debugging only if used solely by tests 1677 const Span& span(int tIndex) const { 1678 return fTs[tIndex]; 1679 } 1680 1681 int spanSign(int startIndex, int endIndex) const { 1682 return startIndex < endIndex ? -fTs[startIndex].fWindValue : 1683 fTs[endIndex].fWindValue; 1684 } 1685 1686 // OPTIMIZATION: mark as debugging only if used solely by tests 1687 double t(int tIndex) const { 1688 return fTs[tIndex].fT; 1689 } 1690 1691 void updatePts(const SkPoint pts[]) { 1692 fPts = pts; 1693 } 1694 1695 SkPath::Verb verb() const { 1696 return fVerb; 1697 } 1698 1699 int windSum(int tIndex) const { 1700 return fTs[tIndex].fWindSum; 1701 } 1702 1703 int windSum(const Angle* angle) const { 1704 int start = angle->start(); 1705 int end = angle->end(); 1706 int index = SkMin32(start, end); 1707 return windSum(index); 1708 } 1709 1710 int windValue(int tIndex) const { 1711 return fTs[tIndex].fWindValue; 1712 } 1713 1714 int windValue(const Angle* angle) const { 1715 int start = angle->start(); 1716 int end = angle->end(); 1717 int index = SkMin32(start, end); 1718 return windValue(index); 1719 } 1720 1721 SkScalar xAtT(const Span* span) const { 1722 return xyAtT(span).fX; 1723 } 1724 1725 const SkPoint& xyAtT(int index) const { 1726 return xyAtT(&fTs[index]); 1727 } 1728 1729 const SkPoint& xyAtT(const Span* span) const { 1730 if (!span->fPt) { 1731 if (span->fT == 0) { 1732 span->fPt = &fPts[0]; 1733 } else if (span->fT == 1) { 1734 span->fPt = &fPts[fVerb]; 1735 } else { 1736 SkPoint* pt = fIntersections.append(); 1737 (*SegmentXYAtT[fVerb])(fPts, span->fT, pt); 1738 span->fPt = pt; 1739 } 1740 } 1741 return *span->fPt; 1742 } 1743 1744 SkScalar yAtT(int index) const { 1745 return yAtT(&fTs[index]); 1746 } 1747 1748 SkScalar yAtT(const Span* span) const { 1749 return xyAtT(span).fY; 1750 } 1751 1752#if DEBUG_DUMP 1753 void dump() const { 1754 const char className[] = "Segment"; 1755 const int tab = 4; 1756 for (int i = 0; i < fTs.count(); ++i) { 1757 SkPoint out; 1758 (*SegmentXYAtT[fVerb])(fPts, t(i), &out); 1759 SkDebugf("%*s [%d] %s.fTs[%d]=%1.9g (%1.9g,%1.9g) other=%d" 1760 " otherT=%1.9g windSum=%d\n", 1761 tab + sizeof(className), className, fID, 1762 kLVerbStr[fVerb], i, fTs[i].fT, out.fX, out.fY, 1763 fTs[i].fOther->fID, fTs[i].fOtherT, fTs[i].fWindSum); 1764 } 1765 SkDebugf("%*s [%d] fBounds=(l:%1.9g, t:%1.9g r:%1.9g, b:%1.9g)", 1766 tab + sizeof(className), className, fID, 1767 fBounds.fLeft, fBounds.fTop, fBounds.fRight, fBounds.fBottom); 1768 } 1769#endif 1770 1771private: 1772 const SkPoint* fPts; 1773 SkPath::Verb fVerb; 1774 Bounds fBounds; 1775 SkTDArray<Span> fTs; // two or more (always includes t=0 t=1) 1776 // OPTIMIZATION:if intersections array is a pointer, the it could only 1777 // be allocated as needed instead of always initialized -- though maybe 1778 // the initialization is lightweight enough that it hardly matters 1779 mutable SkTDArray<SkPoint> fIntersections; 1780 int fDoneSpans; // used for quick check that segment is finished 1781#if DEBUG_DUMP 1782 int fID; 1783#endif 1784}; 1785 1786class Contour; 1787 1788struct Coincidence { 1789 Contour* fContours[2]; 1790 int fSegments[2]; 1791 double fTs[2][2]; 1792}; 1793 1794class Contour { 1795public: 1796 Contour() { 1797 reset(); 1798#if DEBUG_DUMP 1799 fID = ++gContourID; 1800#endif 1801 } 1802 1803 bool operator<(const Contour& rh) const { 1804 return fBounds.fTop == rh.fBounds.fTop 1805 ? fBounds.fLeft < rh.fBounds.fLeft 1806 : fBounds.fTop < rh.fBounds.fTop; 1807 } 1808 1809 void addCoincident(int index, Contour* other, int otherIndex, 1810 const Intersections& ts, bool swap) { 1811 Coincidence& coincidence = *fCoincidences.append(); 1812 coincidence.fContours[0] = this; 1813 coincidence.fContours[1] = other; 1814 coincidence.fSegments[0] = index; 1815 coincidence.fSegments[1] = otherIndex; 1816 coincidence.fTs[swap][0] = ts.fT[0][0]; 1817 coincidence.fTs[swap][1] = ts.fT[0][1]; 1818 coincidence.fTs[!swap][0] = ts.fT[1][0]; 1819 coincidence.fTs[!swap][1] = ts.fT[1][1]; 1820 } 1821 1822 void addCross(const Contour* crosser) { 1823#ifdef DEBUG_CROSS 1824 for (int index = 0; index < fCrosses.count(); ++index) { 1825 SkASSERT(fCrosses[index] != crosser); 1826 } 1827#endif 1828 *fCrosses.append() = crosser; 1829 } 1830 1831 void addCubic(const SkPoint pts[4]) { 1832 fSegments.push_back().addCubic(pts); 1833 fContainsCurves = true; 1834 } 1835 1836 int addLine(const SkPoint pts[2]) { 1837 fSegments.push_back().addLine(pts); 1838 return fSegments.count(); 1839 } 1840 1841 void addOtherT(int segIndex, int tIndex, double otherT, int otherIndex) { 1842 fSegments[segIndex].addOtherT(tIndex, otherT, otherIndex); 1843 } 1844 1845 int addQuad(const SkPoint pts[3]) { 1846 fSegments.push_back().addQuad(pts); 1847 fContainsCurves = true; 1848 return fSegments.count(); 1849 } 1850 1851 int addT(int segIndex, double newT, Contour* other, int otherIndex) { 1852 containsIntercepts(); 1853 return fSegments[segIndex].addT(newT, &other->fSegments[otherIndex]); 1854 } 1855 1856 const Bounds& bounds() const { 1857 return fBounds; 1858 } 1859 1860 void complete() { 1861 setBounds(); 1862 fContainsIntercepts = false; 1863 } 1864 1865 void containsIntercepts() { 1866 fContainsIntercepts = true; 1867 } 1868 1869 const Segment* crossedSegment(const SkPoint& basePt, SkScalar& bestY, 1870 int &tIndex, double& hitT) { 1871 int segmentCount = fSegments.count(); 1872 const Segment* bestSegment = NULL; 1873 for (int test = 0; test < segmentCount; ++test) { 1874 Segment* testSegment = &fSegments[test]; 1875 const SkRect& bounds = testSegment->bounds(); 1876 if (bounds.fTop < bestY) { 1877 continue; 1878 } 1879 if (bounds.fTop > basePt.fY) { 1880 continue; 1881 } 1882 if (bounds.fLeft > basePt.fX) { 1883 continue; 1884 } 1885 if (bounds.fRight < basePt.fX) { 1886 continue; 1887 } 1888 double testHitT; 1889 int testT = testSegment->crossedSpan(basePt, bestY, testHitT); 1890 if (testT >= 0) { 1891 bestSegment = testSegment; 1892 tIndex = testT; 1893 hitT = testHitT; 1894 } 1895 } 1896 return bestSegment; 1897 } 1898 1899 bool crosses(const Contour* crosser) const { 1900 if (this == crosser) { 1901 return true; 1902 } 1903 for (int index = 0; index < fCrosses.count(); ++index) { 1904 if (fCrosses[index] == crosser) { 1905 return true; 1906 } 1907 } 1908 return false; 1909 } 1910 1911 void findTooCloseToCall(int winding) { 1912 int segmentCount = fSegments.count(); 1913 for (int sIndex = 0; sIndex < segmentCount; ++sIndex) { 1914 fSegments[sIndex].findTooCloseToCall(winding); 1915 } 1916 } 1917 1918 void fixOtherTIndex() { 1919 int segmentCount = fSegments.count(); 1920 for (int sIndex = 0; sIndex < segmentCount; ++sIndex) { 1921 fSegments[sIndex].fixOtherTIndex(); 1922 } 1923 } 1924 1925 void reset() { 1926 fSegments.reset(); 1927 fBounds.set(SK_ScalarMax, SK_ScalarMax, SK_ScalarMax, SK_ScalarMax); 1928 fContainsCurves = fContainsIntercepts = false; 1929 fWindingSum = SK_MinS32; 1930 } 1931 1932 void resolveCoincidence(int winding) { 1933 int count = fCoincidences.count(); 1934 for (int index = 0; index < count; ++index) { 1935 Coincidence& coincidence = fCoincidences[index]; 1936 Contour* thisContour = coincidence.fContours[0]; 1937 Contour* otherContour = coincidence.fContours[1]; 1938 int thisIndex = coincidence.fSegments[0]; 1939 int otherIndex = coincidence.fSegments[1]; 1940 Segment& thisOne = thisContour->fSegments[thisIndex]; 1941 Segment& other = otherContour->fSegments[otherIndex]; 1942 double startT = coincidence.fTs[0][0]; 1943 double endT = coincidence.fTs[0][1]; 1944 if (startT > endT) { 1945 SkTSwap<double>(startT, endT); 1946 } 1947 SkASSERT(endT - startT >= FLT_EPSILON); 1948 double oStartT = coincidence.fTs[1][0]; 1949 double oEndT = coincidence.fTs[1][1]; 1950 if (oStartT > oEndT) { 1951 SkTSwap<double>(oStartT, oEndT); 1952 } 1953 SkASSERT(oEndT - oStartT >= FLT_EPSILON); 1954 if (winding > 0 || thisOne.cancels(other)) { 1955 // make sure startT and endT have t entries 1956 if (thisOne.isMissing(startT) || other.isMissing(oEndT)) { 1957 thisOne.addTPair(startT, other, oEndT); 1958 } 1959 if (thisOne.isMissing(endT) || other.isMissing(oStartT)) { 1960 other.addTPair(oStartT, thisOne, endT); 1961 } 1962 thisOne.addTCancel(startT, endT, other, oStartT, oEndT); 1963 } else { 1964 if (thisOne.isMissing(startT) || other.isMissing(oStartT)) { 1965 thisOne.addTPair(startT, other, oStartT); 1966 } 1967 if (thisOne.isMissing(endT) || other.isMissing(oEndT)) { 1968 other.addTPair(oEndT, thisOne, endT); 1969 } 1970 thisOne.addTCoincident(startT, endT, other, oStartT, oEndT); 1971 } 1972 } 1973 } 1974 1975 const SkTArray<Segment>& segments() { 1976 return fSegments; 1977 } 1978 1979 void setWinding(int winding) { 1980 SkASSERT(fWindingSum < 0); 1981 fWindingSum = winding; 1982 } 1983 1984 // OPTIMIZATION: feel pretty uneasy about this. It seems like once again 1985 // we need to sort and walk edges in y, but that on the surface opens the 1986 // same can of worms as before. But then, this is a rough sort based on 1987 // segments' top, and not a true sort, so it could be ameniable to regular 1988 // sorting instead of linear searching. Still feel like I'm missing something 1989 Segment* topSegment(SkScalar& bestY) { 1990 int segmentCount = fSegments.count(); 1991 SkASSERT(segmentCount > 0); 1992 int best = -1; 1993 Segment* bestSegment = NULL; 1994 while (++best < segmentCount) { 1995 Segment* testSegment = &fSegments[best]; 1996 if (testSegment->done()) { 1997 continue; 1998 } 1999 bestSegment = testSegment; 2000 break; 2001 } 2002 if (!bestSegment) { 2003 return NULL; 2004 } 2005 SkScalar bestTop = bestSegment->activeTop(); 2006 for (int test = best + 1; test < segmentCount; ++test) { 2007 Segment* testSegment = &fSegments[test]; 2008 if (testSegment->done()) { 2009 continue; 2010 } 2011 if (testSegment->bounds().fTop > bestTop) { 2012 continue; 2013 } 2014 SkScalar testTop = testSegment->activeTop(); 2015 if (bestTop > testTop) { 2016 bestTop = testTop; 2017 bestSegment = testSegment; 2018 } 2019 } 2020 bestY = bestTop; 2021 return bestSegment; 2022 } 2023 2024 int updateSegment(int index, const SkPoint* pts) { 2025 Segment& segment = fSegments[index]; 2026 segment.updatePts(pts); 2027 return segment.verb() + 1; 2028 } 2029 2030 int windSum() { 2031 if (fWindingSum >= 0) { 2032 return fWindingSum; 2033 } 2034 // check peers 2035 int count = fCrosses.count(); 2036 for (int index = 0; index < count; ++index) { 2037 const Contour* crosser = fCrosses[index]; 2038 if (0 <= crosser->fWindingSum) { 2039 fWindingSum = crosser->fWindingSum; 2040 break; 2041 } 2042 } 2043 return fWindingSum; 2044 } 2045 2046#if DEBUG_TEST 2047 SkTArray<Segment>& debugSegments() { 2048 return fSegments; 2049 } 2050#endif 2051 2052#if DEBUG_DUMP 2053 void dump() { 2054 int i; 2055 const char className[] = "Contour"; 2056 const int tab = 4; 2057 SkDebugf("%s %p (contour=%d)\n", className, this, fID); 2058 for (i = 0; i < fSegments.count(); ++i) { 2059 SkDebugf("%*s.fSegments[%d]:\n", tab + sizeof(className), 2060 className, i); 2061 fSegments[i].dump(); 2062 } 2063 SkDebugf("%*s.fBounds=(l:%1.9g, t:%1.9g r:%1.9g, b:%1.9g)\n", 2064 tab + sizeof(className), className, 2065 fBounds.fLeft, fBounds.fTop, 2066 fBounds.fRight, fBounds.fBottom); 2067 SkDebugf("%*s.fContainsIntercepts=%d\n", tab + sizeof(className), 2068 className, fContainsIntercepts); 2069 SkDebugf("%*s.fContainsCurves=%d\n", tab + sizeof(className), 2070 className, fContainsCurves); 2071 } 2072#endif 2073 2074protected: 2075 void setBounds() { 2076 int count = fSegments.count(); 2077 if (count == 0) { 2078 SkDebugf("%s empty contour\n", __FUNCTION__); 2079 SkASSERT(0); 2080 // FIXME: delete empty contour? 2081 return; 2082 } 2083 fBounds = fSegments.front().bounds(); 2084 for (int index = 1; index < count; ++index) { 2085 fBounds.add(fSegments[index].bounds()); 2086 } 2087 } 2088 2089private: 2090 SkTArray<Segment> fSegments; 2091 SkTDArray<Coincidence> fCoincidences; 2092 SkTDArray<const Contour*> fCrosses; 2093 Bounds fBounds; 2094 bool fContainsIntercepts; 2095 bool fContainsCurves; 2096 int fWindingSum; // initial winding number outside 2097#if DEBUG_DUMP 2098 int fID; 2099#endif 2100}; 2101 2102class EdgeBuilder { 2103public: 2104 2105EdgeBuilder(const SkPath& path, SkTArray<Contour>& contours) 2106 : fPath(path) 2107 , fCurrentContour(NULL) 2108 , fContours(contours) 2109{ 2110#if DEBUG_DUMP 2111 gContourID = 0; 2112 gSegmentID = 0; 2113#endif 2114 walk(); 2115} 2116 2117protected: 2118 2119void complete() { 2120 if (fCurrentContour && fCurrentContour->segments().count()) { 2121 fCurrentContour->complete(); 2122 fCurrentContour = NULL; 2123 } 2124} 2125 2126void walk() { 2127 // FIXME:remove once we can access path pts directly 2128 SkPath::RawIter iter(fPath); // FIXME: access path directly when allowed 2129 SkPoint pts[4]; 2130 SkPath::Verb verb; 2131 do { 2132 verb = iter.next(pts); 2133 *fPathVerbs.append() = verb; 2134 if (verb == SkPath::kMove_Verb) { 2135 *fPathPts.append() = pts[0]; 2136 } else if (verb >= SkPath::kLine_Verb && verb <= SkPath::kCubic_Verb) { 2137 fPathPts.append(verb, &pts[1]); 2138 } 2139 } while (verb != SkPath::kDone_Verb); 2140 // FIXME: end of section to remove once path pts are accessed directly 2141 2142 SkPath::Verb reducedVerb; 2143 uint8_t* verbPtr = fPathVerbs.begin(); 2144 const SkPoint* pointsPtr = fPathPts.begin(); 2145 const SkPoint* finalCurveStart = NULL; 2146 const SkPoint* finalCurveEnd = NULL; 2147 while ((verb = (SkPath::Verb) *verbPtr++) != SkPath::kDone_Verb) { 2148 switch (verb) { 2149 case SkPath::kMove_Verb: 2150 complete(); 2151 if (!fCurrentContour) { 2152 fCurrentContour = fContours.push_back_n(1); 2153 finalCurveEnd = pointsPtr++; 2154 *fExtra.append() = -1; // start new contour 2155 } 2156 continue; 2157 case SkPath::kLine_Verb: 2158 // skip degenerate points 2159 if (pointsPtr[-1].fX != pointsPtr[0].fX 2160 || pointsPtr[-1].fY != pointsPtr[0].fY) { 2161 fCurrentContour->addLine(&pointsPtr[-1]); 2162 } 2163 break; 2164 case SkPath::kQuad_Verb: 2165 2166 reducedVerb = QuadReduceOrder(&pointsPtr[-1], fReducePts); 2167 if (reducedVerb == 0) { 2168 break; // skip degenerate points 2169 } 2170 if (reducedVerb == 1) { 2171 *fExtra.append() = 2172 fCurrentContour->addLine(fReducePts.end() - 2); 2173 break; 2174 } 2175 fCurrentContour->addQuad(&pointsPtr[-1]); 2176 break; 2177 case SkPath::kCubic_Verb: 2178 reducedVerb = CubicReduceOrder(&pointsPtr[-1], fReducePts); 2179 if (reducedVerb == 0) { 2180 break; // skip degenerate points 2181 } 2182 if (reducedVerb == 1) { 2183 *fExtra.append() = 2184 fCurrentContour->addLine(fReducePts.end() - 2); 2185 break; 2186 } 2187 if (reducedVerb == 2) { 2188 *fExtra.append() = 2189 fCurrentContour->addQuad(fReducePts.end() - 3); 2190 break; 2191 } 2192 fCurrentContour->addCubic(&pointsPtr[-1]); 2193 break; 2194 case SkPath::kClose_Verb: 2195 SkASSERT(fCurrentContour); 2196 if (finalCurveStart && finalCurveEnd 2197 && *finalCurveStart != *finalCurveEnd) { 2198 *fReducePts.append() = *finalCurveStart; 2199 *fReducePts.append() = *finalCurveEnd; 2200 *fExtra.append() = 2201 fCurrentContour->addLine(fReducePts.end() - 2); 2202 } 2203 complete(); 2204 continue; 2205 default: 2206 SkDEBUGFAIL("bad verb"); 2207 return; 2208 } 2209 finalCurveStart = &pointsPtr[verb - 1]; 2210 pointsPtr += verb; 2211 SkASSERT(fCurrentContour); 2212 } 2213 complete(); 2214 if (fCurrentContour && !fCurrentContour->segments().count()) { 2215 fContours.pop_back(); 2216 } 2217 // correct pointers in contours since fReducePts may have moved as it grew 2218 int cIndex = 0; 2219 int extraCount = fExtra.count(); 2220 SkASSERT(extraCount == 0 || fExtra[0] == -1); 2221 int eIndex = 0; 2222 int rIndex = 0; 2223 while (++eIndex < extraCount) { 2224 int offset = fExtra[eIndex]; 2225 if (offset < 0) { 2226 ++cIndex; 2227 continue; 2228 } 2229 fCurrentContour = &fContours[cIndex]; 2230 rIndex += fCurrentContour->updateSegment(offset - 1, 2231 &fReducePts[rIndex]); 2232 } 2233 fExtra.reset(); // we're done with this 2234} 2235 2236private: 2237 const SkPath& fPath; 2238 SkTDArray<SkPoint> fPathPts; // FIXME: point directly to path pts instead 2239 SkTDArray<uint8_t> fPathVerbs; // FIXME: remove 2240 Contour* fCurrentContour; 2241 SkTArray<Contour>& fContours; 2242 SkTDArray<SkPoint> fReducePts; // segments created on the fly 2243 SkTDArray<int> fExtra; // -1 marks new contour, > 0 offsets into contour 2244}; 2245 2246class Work { 2247public: 2248 enum SegmentType { 2249 kHorizontalLine_Segment = -1, 2250 kVerticalLine_Segment = 0, 2251 kLine_Segment = SkPath::kLine_Verb, 2252 kQuad_Segment = SkPath::kQuad_Verb, 2253 kCubic_Segment = SkPath::kCubic_Verb, 2254 }; 2255 2256 void addCoincident(Work& other, const Intersections& ts, bool swap) { 2257 fContour->addCoincident(fIndex, other.fContour, other.fIndex, ts, swap); 2258 } 2259 2260 // FIXME: does it make sense to write otherIndex now if we're going to 2261 // fix it up later? 2262 void addOtherT(int index, double otherT, int otherIndex) { 2263 fContour->addOtherT(fIndex, index, otherT, otherIndex); 2264 } 2265 2266 // Avoid collapsing t values that are close to the same since 2267 // we walk ts to describe consecutive intersections. Since a pair of ts can 2268 // be nearly equal, any problems caused by this should be taken care 2269 // of later. 2270 // On the edge or out of range values are negative; add 2 to get end 2271 int addT(double newT, const Work& other) { 2272 return fContour->addT(fIndex, newT, other.fContour, other.fIndex); 2273 } 2274 2275 bool advance() { 2276 return ++fIndex < fLast; 2277 } 2278 2279 SkScalar bottom() const { 2280 return bounds().fBottom; 2281 } 2282 2283 const Bounds& bounds() const { 2284 return fContour->segments()[fIndex].bounds(); 2285 } 2286 2287 const SkPoint* cubic() const { 2288 return fCubic; 2289 } 2290 2291 void init(Contour* contour) { 2292 fContour = contour; 2293 fIndex = 0; 2294 fLast = contour->segments().count(); 2295 } 2296 2297 bool isAdjacent(const Work& next) { 2298 return fContour == next.fContour && fIndex + 1 == next.fIndex; 2299 } 2300 2301 bool isFirstLast(const Work& next) { 2302 return fContour == next.fContour && fIndex == 0 2303 && next.fIndex == fLast - 1; 2304 } 2305 2306 SkScalar left() const { 2307 return bounds().fLeft; 2308 } 2309 2310 void promoteToCubic() { 2311 fCubic[0] = pts()[0]; 2312 fCubic[2] = pts()[1]; 2313 fCubic[3] = pts()[2]; 2314 fCubic[1].fX = (fCubic[0].fX + fCubic[2].fX * 2) / 3; 2315 fCubic[1].fY = (fCubic[0].fY + fCubic[2].fY * 2) / 3; 2316 fCubic[2].fX = (fCubic[3].fX + fCubic[2].fX * 2) / 3; 2317 fCubic[2].fY = (fCubic[3].fY + fCubic[2].fY * 2) / 3; 2318 } 2319 2320 const SkPoint* pts() const { 2321 return fContour->segments()[fIndex].pts(); 2322 } 2323 2324 SkScalar right() const { 2325 return bounds().fRight; 2326 } 2327 2328 ptrdiff_t segmentIndex() const { 2329 return fIndex; 2330 } 2331 2332 SegmentType segmentType() const { 2333 const Segment& segment = fContour->segments()[fIndex]; 2334 SegmentType type = (SegmentType) segment.verb(); 2335 if (type != kLine_Segment) { 2336 return type; 2337 } 2338 if (segment.isHorizontal()) { 2339 return kHorizontalLine_Segment; 2340 } 2341 if (segment.isVertical()) { 2342 return kVerticalLine_Segment; 2343 } 2344 return kLine_Segment; 2345 } 2346 2347 bool startAfter(const Work& after) { 2348 fIndex = after.fIndex; 2349 return advance(); 2350 } 2351 2352 SkScalar top() const { 2353 return bounds().fTop; 2354 } 2355 2356 SkPath::Verb verb() const { 2357 return fContour->segments()[fIndex].verb(); 2358 } 2359 2360 SkScalar x() const { 2361 return bounds().fLeft; 2362 } 2363 2364 bool xFlipped() const { 2365 return x() != pts()[0].fX; 2366 } 2367 2368 SkScalar y() const { 2369 return bounds().fTop; 2370 } 2371 2372 bool yFlipped() const { 2373 return y() != pts()[0].fY; 2374 } 2375 2376protected: 2377 Contour* fContour; 2378 SkPoint fCubic[4]; 2379 int fIndex; 2380 int fLast; 2381}; 2382 2383#if DEBUG_ADD_INTERSECTING_TS 2384static void debugShowLineIntersection(int pts, const Work& wt, 2385 const Work& wn, const double wtTs[2], const double wnTs[2]) { 2386 if (!pts) { 2387 SkDebugf("%s no intersect (%1.9g,%1.9g %1.9g,%1.9g) (%1.9g,%1.9g %1.9g,%1.9g)\n", 2388 __FUNCTION__, wt.pts()[0].fX, wt.pts()[0].fY, 2389 wt.pts()[1].fX, wt.pts()[1].fY, wn.pts()[0].fX, wn.pts()[0].fY, 2390 wn.pts()[1].fX, wn.pts()[1].fY); 2391 return; 2392 } 2393 SkPoint wtOutPt, wnOutPt; 2394 LineXYAtT(wt.pts(), wtTs[0], &wtOutPt); 2395 LineXYAtT(wn.pts(), wnTs[0], &wnOutPt); 2396 SkDebugf("%s wtTs[0]=%g (%g,%g, %g,%g) (%g,%g)", 2397 __FUNCTION__, 2398 wtTs[0], wt.pts()[0].fX, wt.pts()[0].fY, 2399 wt.pts()[1].fX, wt.pts()[1].fY, wtOutPt.fX, wtOutPt.fY); 2400 if (pts == 2) { 2401 SkDebugf(" wtTs[1]=%g", wtTs[1]); 2402 } 2403 SkDebugf(" wnTs[0]=%g (%g,%g, %g,%g) (%g,%g)", 2404 wnTs[0], wn.pts()[0].fX, wn.pts()[0].fY, 2405 wn.pts()[1].fX, wn.pts()[1].fY, wnOutPt.fX, wnOutPt.fY); 2406 if (pts == 2) { 2407 SkDebugf(" wnTs[1]=%g", wnTs[1]); 2408 } 2409 SkDebugf("\n"); 2410} 2411#else 2412static void debugShowLineIntersection(int , const Work& , 2413 const Work& , const double [2], const double [2]) { 2414} 2415#endif 2416 2417static bool addIntersectTs(Contour* test, Contour* next) { 2418 2419 if (test != next) { 2420 if (test->bounds().fBottom < next->bounds().fTop) { 2421 return false; 2422 } 2423 if (!Bounds::Intersects(test->bounds(), next->bounds())) { 2424 return true; 2425 } 2426 } 2427 Work wt; 2428 wt.init(test); 2429 bool foundCommonContour = test == next; 2430 do { 2431 Work wn; 2432 wn.init(next); 2433 if (test == next && !wn.startAfter(wt)) { 2434 continue; 2435 } 2436 do { 2437 if (!Bounds::Intersects(wt.bounds(), wn.bounds())) { 2438 continue; 2439 } 2440 int pts; 2441 Intersections ts; 2442 bool swap = false; 2443 switch (wt.segmentType()) { 2444 case Work::kHorizontalLine_Segment: 2445 swap = true; 2446 switch (wn.segmentType()) { 2447 case Work::kHorizontalLine_Segment: 2448 case Work::kVerticalLine_Segment: 2449 case Work::kLine_Segment: { 2450 pts = HLineIntersect(wn.pts(), wt.left(), 2451 wt.right(), wt.y(), wt.xFlipped(), ts); 2452 debugShowLineIntersection(pts, wt, wn, 2453 ts.fT[1], ts.fT[0]); 2454 break; 2455 } 2456 case Work::kQuad_Segment: { 2457 pts = HQuadIntersect(wn.pts(), wt.left(), 2458 wt.right(), wt.y(), wt.xFlipped(), ts); 2459 break; 2460 } 2461 case Work::kCubic_Segment: { 2462 pts = HCubicIntersect(wn.pts(), wt.left(), 2463 wt.right(), wt.y(), wt.xFlipped(), ts); 2464 break; 2465 } 2466 default: 2467 SkASSERT(0); 2468 } 2469 break; 2470 case Work::kVerticalLine_Segment: 2471 swap = true; 2472 switch (wn.segmentType()) { 2473 case Work::kHorizontalLine_Segment: 2474 case Work::kVerticalLine_Segment: 2475 case Work::kLine_Segment: { 2476 pts = VLineIntersect(wn.pts(), wt.top(), 2477 wt.bottom(), wt.x(), wt.yFlipped(), ts); 2478 debugShowLineIntersection(pts, wt, wn, 2479 ts.fT[1], ts.fT[0]); 2480 break; 2481 } 2482 case Work::kQuad_Segment: { 2483 pts = VQuadIntersect(wn.pts(), wt.top(), 2484 wt.bottom(), wt.x(), wt.yFlipped(), ts); 2485 break; 2486 } 2487 case Work::kCubic_Segment: { 2488 pts = VCubicIntersect(wn.pts(), wt.top(), 2489 wt.bottom(), wt.x(), wt.yFlipped(), ts); 2490 break; 2491 } 2492 default: 2493 SkASSERT(0); 2494 } 2495 break; 2496 case Work::kLine_Segment: 2497 switch (wn.segmentType()) { 2498 case Work::kHorizontalLine_Segment: 2499 pts = HLineIntersect(wt.pts(), wn.left(), 2500 wn.right(), wn.y(), wn.xFlipped(), ts); 2501 debugShowLineIntersection(pts, wt, wn, 2502 ts.fT[1], ts.fT[0]); 2503 break; 2504 case Work::kVerticalLine_Segment: 2505 pts = VLineIntersect(wt.pts(), wn.top(), 2506 wn.bottom(), wn.x(), wn.yFlipped(), ts); 2507 debugShowLineIntersection(pts, wt, wn, 2508 ts.fT[1], ts.fT[0]); 2509 break; 2510 case Work::kLine_Segment: { 2511 pts = LineIntersect(wt.pts(), wn.pts(), ts); 2512 debugShowLineIntersection(pts, wt, wn, 2513 ts.fT[1], ts.fT[0]); 2514 break; 2515 } 2516 case Work::kQuad_Segment: { 2517 swap = true; 2518 pts = QuadLineIntersect(wn.pts(), wt.pts(), ts); 2519 break; 2520 } 2521 case Work::kCubic_Segment: { 2522 swap = true; 2523 pts = CubicLineIntersect(wn.pts(), wt.pts(), ts); 2524 break; 2525 } 2526 default: 2527 SkASSERT(0); 2528 } 2529 break; 2530 case Work::kQuad_Segment: 2531 switch (wn.segmentType()) { 2532 case Work::kHorizontalLine_Segment: 2533 pts = HQuadIntersect(wt.pts(), wn.left(), 2534 wn.right(), wn.y(), wn.xFlipped(), ts); 2535 break; 2536 case Work::kVerticalLine_Segment: 2537 pts = VQuadIntersect(wt.pts(), wn.top(), 2538 wn.bottom(), wn.x(), wn.yFlipped(), ts); 2539 break; 2540 case Work::kLine_Segment: { 2541 pts = QuadLineIntersect(wt.pts(), wn.pts(), ts); 2542 break; 2543 } 2544 case Work::kQuad_Segment: { 2545 pts = QuadIntersect(wt.pts(), wn.pts(), ts); 2546 break; 2547 } 2548 case Work::kCubic_Segment: { 2549 wt.promoteToCubic(); 2550 pts = CubicIntersect(wt.cubic(), wn.pts(), ts); 2551 break; 2552 } 2553 default: 2554 SkASSERT(0); 2555 } 2556 break; 2557 case Work::kCubic_Segment: 2558 switch (wn.segmentType()) { 2559 case Work::kHorizontalLine_Segment: 2560 pts = HCubicIntersect(wt.pts(), wn.left(), 2561 wn.right(), wn.y(), wn.xFlipped(), ts); 2562 break; 2563 case Work::kVerticalLine_Segment: 2564 pts = VCubicIntersect(wt.pts(), wn.top(), 2565 wn.bottom(), wn.x(), wn.yFlipped(), ts); 2566 break; 2567 case Work::kLine_Segment: { 2568 pts = CubicLineIntersect(wt.pts(), wn.pts(), ts); 2569 break; 2570 } 2571 case Work::kQuad_Segment: { 2572 wn.promoteToCubic(); 2573 pts = CubicIntersect(wt.pts(), wn.cubic(), ts); 2574 break; 2575 } 2576 case Work::kCubic_Segment: { 2577 pts = CubicIntersect(wt.pts(), wn.pts(), ts); 2578 break; 2579 } 2580 default: 2581 SkASSERT(0); 2582 } 2583 break; 2584 default: 2585 SkASSERT(0); 2586 } 2587 if (!foundCommonContour && pts > 0) { 2588 test->addCross(next); 2589 next->addCross(test); 2590 foundCommonContour = true; 2591 } 2592 // in addition to recording T values, record matching segment 2593 if (pts == 2 && wn.segmentType() <= Work::kLine_Segment 2594 && wt.segmentType() <= Work::kLine_Segment) { 2595 wt.addCoincident(wn, ts, swap); 2596 continue; 2597 } 2598 for (int pt = 0; pt < pts; ++pt) { 2599 SkASSERT(ts.fT[0][pt] >= 0 && ts.fT[0][pt] <= 1); 2600 SkASSERT(ts.fT[1][pt] >= 0 && ts.fT[1][pt] <= 1); 2601 int testTAt = wt.addT(ts.fT[swap][pt], wn); 2602 int nextTAt = wn.addT(ts.fT[!swap][pt], wt); 2603 wt.addOtherT(testTAt, ts.fT[!swap][pt], nextTAt); 2604 wn.addOtherT(nextTAt, ts.fT[swap][pt], testTAt); 2605 } 2606 } while (wn.advance()); 2607 } while (wt.advance()); 2608 return true; 2609} 2610 2611// resolve any coincident pairs found while intersecting, and 2612// see if coincidence is formed by clipping non-concident segments 2613static void coincidenceCheck(SkTDArray<Contour*>& contourList, int winding) { 2614 int contourCount = contourList.count(); 2615 for (int cIndex = 0; cIndex < contourCount; ++cIndex) { 2616 Contour* contour = contourList[cIndex]; 2617 contour->findTooCloseToCall(winding); 2618 } 2619 for (int cIndex = 0; cIndex < contourCount; ++cIndex) { 2620 Contour* contour = contourList[cIndex]; 2621 contour->resolveCoincidence(winding); 2622 } 2623} 2624 2625// project a ray from the top of the contour up and see if it hits anything 2626// note: when we compute line intersections, we keep track of whether 2627// two contours touch, so we need only look at contours not touching this one. 2628// OPTIMIZATION: sort contourList vertically to avoid linear walk 2629static int innerContourCheck(SkTDArray<Contour*>& contourList, 2630 Contour* baseContour, const SkPoint& basePt) { 2631 int contourCount = contourList.count(); 2632 int winding = 0; 2633 SkScalar bestY = SK_ScalarMin; 2634 for (int cTest = 0; cTest < contourCount; ++cTest) { 2635 Contour* contour = contourList[cTest]; 2636 if (basePt.fY < contour->bounds().fTop) { 2637 continue; 2638 } 2639 if (bestY > contour->bounds().fBottom) { 2640 continue; 2641 } 2642 if (baseContour->crosses(contour)) { 2643 continue; 2644 } 2645 int tIndex; 2646 double tHit; 2647 const Segment* test = contour->crossedSegment(basePt, bestY, tIndex, 2648 tHit); 2649 if (!test) { 2650 continue; 2651 } 2652 // If the ray hit the end of a span, we need to construct the wheel of 2653 // angles to find the span closest to the ray -- even if there are just 2654 // two spokes on the wheel. 2655 if (tHit == test->t(tIndex)) { 2656 SkTDArray<Angle> angles; 2657 int end = test->nextSpan(tIndex, 1); 2658 if (end < 0) { 2659 end = test->nextSpan(tIndex, -1); 2660 } 2661 test->addTwoAngles(tIndex, end, angles); 2662 // test->buildAnglesInner(tIndex, angles); 2663 test->buildAngles(tIndex, angles); 2664 SkTDArray<Angle*> sorted; 2665 sortAngles(angles, sorted); 2666 const Angle* angle = sorted[0]; 2667 test = angle->segment(); 2668 SkScalar testDx = (*SegmentDXAtT[test->verb()])(test->pts(), tHit); 2669 if (testDx == 0) { 2670 angle = *(sorted.end() - 1); 2671 test = angle->segment(); 2672 SkASSERT((*SegmentDXAtT[test->verb()])(test->pts(), tHit) != 0); 2673 } 2674 tIndex = angle->start(); // lesser Y 2675 winding = test->windSum(SkMin32(tIndex, angle->end())); 2676 #if DEBUG_WINDING 2677 SkDebugf("%s 1 winding=%d\n", __FUNCTION__, winding); 2678 #endif 2679 } else { 2680 winding = test->windSum(tIndex); 2681 #if DEBUG_WINDING 2682 SkDebugf("%s 2 winding=%d\n", __FUNCTION__, winding); 2683 #endif 2684 } 2685 // see if a + change in T results in a +/- change in X (compute x'(T)) 2686 SkScalar dx = (*SegmentDXAtT[test->verb()])(test->pts(), tHit); 2687 #if DEBUG_WINDING 2688 SkDebugf("%s dx=%1.9g\n", __FUNCTION__, dx); 2689 #endif 2690 SkASSERT(dx != 0); 2691 if (winding * dx > 0) { // if same signs, result is negative 2692 winding += dx > 0 ? -1 : 1; 2693 #if DEBUG_WINDING 2694 SkDebugf("%s 3 winding=%d\n", __FUNCTION__, winding); 2695 #endif 2696 } 2697 } 2698 baseContour->setWinding(winding); 2699 return winding; 2700} 2701 2702// OPTIMIZATION: not crazy about linear search here to find top active y. 2703// seems like we should break down and do the sort, or maybe sort each 2704// contours' segments? 2705// Once the segment array is built, there's no reason I can think of not to 2706// sort it in Y. hmmm 2707// FIXME: return the contour found to pass to inner contour check 2708static Segment* findTopContour(SkTDArray<Contour*>& contourList, 2709 Contour*& topContour) { 2710 int contourCount = contourList.count(); 2711 int cIndex = 0; 2712 Segment* topStart; 2713 SkScalar bestY = SK_ScalarMax; 2714 Contour* contour; 2715 do { 2716 contour = contourList[cIndex]; 2717 topStart = contour->topSegment(bestY); 2718 } while (!topStart && ++cIndex < contourCount); 2719 if (!topStart) { 2720 return NULL; 2721 } 2722 topContour = contour; 2723 while (++cIndex < contourCount) { 2724 contour = contourList[cIndex]; 2725 if (bestY < contour->bounds().fTop) { 2726 continue; 2727 } 2728 SkScalar testY = SK_ScalarMax; 2729 Segment* test = contour->topSegment(testY); 2730 if (!test || bestY <= testY) { 2731 continue; 2732 } 2733 topContour = contour; 2734 topStart = test; 2735 bestY = testY; 2736 } 2737 return topStart; 2738} 2739 2740static Segment* findChase(SkTDArray<Span*>& chase, int& tIndex, int& endIndex) { 2741 while (chase.count()) { 2742 Span* span; 2743 chase.pop(&span); 2744 const Span& backPtr = span->fOther->span(span->fOtherIndex); 2745 Segment* segment = backPtr.fOther; 2746 tIndex = backPtr.fOtherIndex; 2747 if (segment->activeAngles(tIndex)) { 2748 endIndex = segment->nextSpan(tIndex, 1); 2749 if (span->fDone) { 2750 SkTDArray<Angle> angles; 2751 segment->addTwoAngles(endIndex, tIndex, angles); 2752 segment->buildAngles(tIndex, angles); 2753 SkTDArray<Angle*> sorted; 2754 sortAngles(angles, sorted); 2755 // find first angle, initialize winding to computed fWindSum 2756 int winding = span->fWindSum; 2757 int firstIndex = segment->findStartingEdge(sorted, endIndex, tIndex); 2758 int firstSign = sorted[firstIndex]->sign(); 2759 if (firstSign * winding > 0) { 2760 winding -= firstSign; 2761 } 2762 SkDebugf("%s firstSign=%d\n", __FUNCTION__, firstSign); 2763 // we care about first sign and whether wind sum indicates this 2764 // edge is inside or outside. Maybe need to pass span winding 2765 // or first winding or something into this function? 2766 SkASSERT(firstIndex >= 0); 2767 // advance to first undone angle, then return it and winding 2768 // (to set whether edges are active or not) 2769 int nextIndex = firstIndex + 1; 2770 int angleCount = sorted.count(); 2771 int lastIndex = firstIndex != 0 ? firstIndex : angleCount; 2772 do { 2773 SkASSERT(nextIndex != firstIndex); 2774 if (nextIndex == angleCount) { 2775 nextIndex = 0; 2776 } 2777 const Angle* angle = sorted[nextIndex]; 2778 segment = angle->segment(); 2779 int windValue = segment->windValue(angle); 2780 SkASSERT(windValue > 0); 2781 int maxWinding = winding; 2782 winding -= angle->sign() * windValue; 2783 if (maxWinding * winding < 0) { 2784 SkDebugf("%s flipped sign %d %d\n", __FUNCTION__, maxWinding, winding); 2785 } 2786 tIndex = angle->start(); 2787 endIndex = angle->end(); 2788 int lesser = SkMin32(tIndex, endIndex); 2789 const Span& nextSpan = segment->span(lesser); 2790 if (!nextSpan.fDone) { 2791 // FIXME: this be wrong. assign startWinding if edge is in 2792 // same direction. If the direction is opposite, winding to 2793 // assign is flipped sign or +/- 1? 2794 if (abs(maxWinding) < abs(winding)) { 2795 maxWinding = winding; 2796 } 2797 segment->markWinding(lesser, maxWinding); 2798 break; 2799 } 2800 } while (++nextIndex != lastIndex); 2801 } else { 2802 SkASSERT(endIndex > tIndex); 2803 } 2804 return segment; 2805 } 2806 } 2807 return NULL; 2808} 2809 2810// Each segment may have an inside or an outside. Segments contained within 2811// winding may have insides on either side, and form a contour that should be 2812// ignored. Segments that are coincident with opposing direction segments may 2813// have outsides on either side, and should also disappear. 2814// 'Normal' segments will have one inside and one outside. Subsequent connections 2815// when winding should follow the intersection direction. If more than one edge 2816// is an option, choose first edge that continues the inside. 2817 // since we start with leftmost top edge, we'll traverse through a 2818 // smaller angle counterclockwise to get to the next edge. 2819static void bridge(SkTDArray<Contour*>& contourList, SkPath& simple) { 2820 bool firstContour = true; 2821 do { 2822 Contour* topContour; 2823 Segment* topStart = findTopContour(contourList, topContour); 2824 if (!topStart) { 2825 break; 2826 } 2827 // Start at the top. Above the top is outside, below is inside. 2828 // follow edges to intersection by changing the index by direction. 2829 int index, endIndex; 2830 Segment* current = topStart->findTop(index, endIndex); 2831 int contourWinding; 2832 if (firstContour) { 2833 contourWinding = 0; 2834 firstContour = false; 2835 } else { 2836 const SkPoint& topPoint = current->xyAtT(endIndex); 2837 contourWinding = innerContourCheck(contourList, topContour, topPoint); 2838#if DEBUG_WINDING 2839 SkDebugf("%s contourWinding=%d\n", __FUNCTION__, contourWinding); 2840#endif 2841 } 2842 SkPoint lastPt; 2843 bool firstTime = true; 2844 int winding = contourWinding; 2845 int spanWinding = current->spanSign(index, endIndex); 2846 // int firstWinding = contourWinding + spanWinding; 2847 // FIXME: needs work. While it works in limited situations, it does 2848 // not always compute winding correctly. Active should be removed and instead 2849 // the initial winding should be correctly passed in so that if the 2850 // inner contour is wound the same way, it never finds an accumulated 2851 // winding of zero. Inside 'find next', we need to look for transitions 2852 // other than zero when resolving sorted angles. 2853 SkTDArray<Span*> chaseArray; 2854 do { 2855 bool active = winding * spanWinding <= 0; 2856 const SkPoint* firstPt = NULL; 2857 do { 2858 SkASSERT(!current->done()); 2859 int nextStart, nextEnd, flipped = 1; 2860 Segment* next = current->findNext(chaseArray, 2861 winding + spanWinding, index, 2862 endIndex, nextStart, nextEnd, flipped, firstTime); 2863 if (!next) { 2864 break; 2865 } 2866 if (!firstPt) { 2867 firstPt = ¤t->addMoveTo(index, simple, active); 2868 } 2869 lastPt = current->addCurveTo(index, endIndex, simple, active); 2870 current = next; 2871 index = nextStart; 2872 endIndex = nextEnd; 2873 spanWinding = SkSign32(spanWinding) * flipped * next->windValue( 2874 SkMin32(nextStart, nextEnd)); 2875 #if DEBUG_WINDING 2876 SkDebugf("%s spanWinding=%d\n", __FUNCTION__, spanWinding); 2877 #endif 2878 firstTime = false; 2879 } while (*firstPt != lastPt && (active || !current->done())); 2880 if (firstPt && active) { 2881 #if DEBUG_PATH_CONSTRUCTION 2882 SkDebugf("%s close\n", __FUNCTION__); 2883 #endif 2884 simple.close(); 2885 } 2886 current = findChase(chaseArray, index, endIndex); 2887 if (!current) { 2888 break; 2889 } 2890 int lesser = SkMin32(index, endIndex); 2891 spanWinding = current->windSum(lesser); 2892 int spanValue = current->windValue(lesser); 2893 SkASSERT(spanWinding != SK_MinS32); 2894 int spanSign = current->spanSign(index, endIndex); 2895 #if DEBUG_WINDING 2896 SkDebugf("%s spanWinding=%d spanSign=%d winding=%d spanValue=%d\n", 2897 __FUNCTION__, spanWinding, spanSign, winding, spanValue); 2898 #endif 2899 if (spanWinding * spanSign < 0) { 2900 #if DEBUG_WINDING 2901 SkDebugf("%s spanWinding * spanSign < 0\n", __FUNCTION__); 2902 #endif 2903 SkTSwap<int>(index, endIndex); 2904 } 2905 if (abs(spanWinding) > spanValue) { 2906 #if DEBUG_WINDING 2907 SkDebugf("%s abs(spanWinding) > spanValue\n", __FUNCTION__); 2908 #endif 2909 winding = spanWinding; 2910 spanWinding = spanValue * SkSign32(spanWinding); 2911 winding -= spanWinding; 2912 } 2913 } while (true); 2914 } while (true); 2915} 2916 2917static void fixOtherTIndex(SkTDArray<Contour*>& contourList) { 2918 int contourCount = contourList.count(); 2919 for (int cTest = 0; cTest < contourCount; ++cTest) { 2920 Contour* contour = contourList[cTest]; 2921 contour->fixOtherTIndex(); 2922 } 2923} 2924 2925static void makeContourList(SkTArray<Contour>& contours, 2926 SkTDArray<Contour*>& list) { 2927 int count = contours.count(); 2928 if (count == 0) { 2929 return; 2930 } 2931 for (int index = 0; index < count; ++index) { 2932 *list.append() = &contours[index]; 2933 } 2934 QSort<Contour>(list.begin(), list.end() - 1); 2935} 2936 2937void simplifyx(const SkPath& path, SkPath& simple) { 2938 // returns 1 for evenodd, -1 for winding, regardless of inverse-ness 2939 int winding = (path.getFillType() & 1) ? 1 : -1; 2940 simple.reset(); 2941 simple.setFillType(SkPath::kEvenOdd_FillType); 2942 2943 // turn path into list of segments 2944 SkTArray<Contour> contours; 2945 // FIXME: add self-intersecting cubics' T values to segment 2946 EdgeBuilder builder(path, contours); 2947 SkTDArray<Contour*> contourList; 2948 makeContourList(contours, contourList); 2949 Contour** currentPtr = contourList.begin(); 2950 if (!currentPtr) { 2951 return; 2952 } 2953 Contour** listEnd = contourList.end(); 2954 // find all intersections between segments 2955 do { 2956 Contour** nextPtr = currentPtr; 2957 Contour* current = *currentPtr++; 2958 Contour* next; 2959 do { 2960 next = *nextPtr++; 2961 } while (addIntersectTs(current, next) && nextPtr != listEnd); 2962 } while (currentPtr != listEnd); 2963 // eat through coincident edges 2964 coincidenceCheck(contourList, winding); 2965 fixOtherTIndex(contourList); 2966 // construct closed contours 2967 bridge(contourList, simple); 2968} 2969 2970