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