Simplify.cpp revision 59823f7f3ba43c7c6bc1fa8c600b093ecb4236aa
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 1 53#define DEBUG_CONCIDENT 1 54#define DEBUG_CROSS 0 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_SORT) && !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 double dy() const { 487 return fDy; 488 } 489 490 int end() const { 491 return fEnd; 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 657static bool useInnerWinding(int outerWinding, int innerWinding) { 658 SkASSERT(outerWinding != innerWinding); 659 int absOut = abs(outerWinding); 660 int absIn = abs(innerWinding); 661 bool result = absOut == absIn ? outerWinding < 0 : absOut < absIn; 662 if (outerWinding * innerWinding < 0) { 663#if DEBUG_WINDING 664 SkDebugf("%s *** outer=%d inner=%d result=%s\n", __FUNCTION__, 665 outerWinding, innerWinding, result ? "true" : "false"); 666#endif 667 } 668 return result; 669} 670 671struct Span { 672 Segment* fOther; 673 mutable SkPoint fPt; // lazily computed as needed 674 double fT; 675 double fOtherT; // value at fOther[fOtherIndex].fT 676 int fOtherIndex; // can't be used during intersection 677 int fWindSum; // accumulated from contours surrounding this one 678 int fWindValue; // 0 == canceled; 1 == normal; >1 == coincident 679 bool fDone; // if set, this span to next higher T has been processed 680}; 681 682class Segment { 683public: 684 Segment() { 685#if DEBUG_DUMP 686 fID = ++gSegmentID; 687#endif 688 } 689 690 bool activeAngle(int index, int& done, SkTDArray<Angle>& angles) const { 691 if (activeAngleInner(index, done, angles)) { 692 return true; 693 } 694 double referenceT = fTs[index].fT; 695 int lesser = index; 696 while (--lesser >= 0 && referenceT - fTs[lesser].fT < FLT_EPSILON) { 697 if (activeAngleOther(lesser, done, angles)) { 698 return true; 699 } 700 } 701 do { 702 if (activeAngleOther(index, done, angles)) { 703 return true; 704 } 705 } while (++index < fTs.count() && fTs[index].fT - referenceT < FLT_EPSILON); 706 return false; 707 } 708 709 bool activeAngleOther(int index, int& done, SkTDArray<Angle>& angles) const { 710 Span* span = &fTs[index]; 711 Segment* other = span->fOther; 712 int oIndex = span->fOtherIndex; 713 return other->activeAngleInner(oIndex, done, angles); 714 } 715 716 bool activeAngleInner(int index, int& done, SkTDArray<Angle>& angles) const { 717 int next = nextSpan(index, 1); 718 if (next > 0) { 719 const Span& upSpan = fTs[index]; 720 if (upSpan.fWindValue) { 721 addAngle(angles, index, next); 722 if (upSpan.fDone) { 723 done++; 724 } else if (upSpan.fWindSum != SK_MinS32) { 725 return true; 726 } 727 } 728 } 729 int prev = nextSpan(index, -1); 730 // edge leading into junction 731 if (prev >= 0) { 732 const Span& downSpan = fTs[prev]; 733 if (downSpan.fWindValue) { 734 addAngle(angles, index, prev); 735 if (downSpan.fDone) { 736 done++; 737 } else if (downSpan.fWindSum != SK_MinS32) { 738 return true; 739 } 740 } 741 } 742 return false; 743 } 744 745 SkScalar activeTop() const { 746 SkASSERT(!done()); 747 int count = fTs.count(); 748 SkScalar result = SK_ScalarMax; 749 bool lastDone = true; 750 for (int index = 0; index < count; ++index) { 751 bool done = fTs[index].fDone; 752 if (!done || !lastDone) { 753 SkScalar y = yAtT(index); 754 if (result > y) { 755 result = y; 756 } 757 } 758 lastDone = done; 759 } 760 SkASSERT(result < SK_ScalarMax); 761 return result; 762 } 763 764 void addAngle(SkTDArray<Angle>& angles, int start, int end) const { 765 SkASSERT(start != end); 766 SkPoint edge[4]; 767 (*SegmentSubDivide[fVerb])(fPts, fTs[start].fT, fTs[end].fT, edge); 768 Angle* angle = angles.append(); 769 angle->set(edge, fVerb, this, start, end); 770 } 771 772 void addCancelOutsides(double tStart, double oStart, Segment& other, 773 double oEnd) { 774 int tIndex = -1; 775 int tCount = fTs.count(); 776 int oIndex = -1; 777 int oCount = other.fTs.count(); 778 do { 779 ++tIndex; 780 } while (tStart - fTs[tIndex].fT >= FLT_EPSILON && tIndex < tCount); 781 int tIndexStart = tIndex; 782 do { 783 ++oIndex; 784 } while (oStart - other.fTs[oIndex].fT >= FLT_EPSILON && oIndex < oCount); 785 int oIndexStart = oIndex; 786 double nextT; 787 do { 788 nextT = fTs[++tIndex].fT; 789 } while (nextT < 1 && nextT - tStart < FLT_EPSILON); 790 double oNextT; 791 do { 792 oNextT = other.fTs[++oIndex].fT; 793 } while (oNextT < 1 && oNextT - oStart < FLT_EPSILON); 794 // at this point, spans before and after are at: 795 // fTs[tIndexStart - 1], fTs[tIndexStart], fTs[tIndex] 796 // if tIndexStart == 0, no prior span 797 // if nextT == 1, no following span 798 799 // advance the span with zero winding 800 // if the following span exists (not past the end, non-zero winding) 801 // connect the two edges 802 if (!fTs[tIndexStart].fWindValue) { 803 if (tIndexStart > 0 && fTs[tIndexStart - 1].fWindValue) { 804 #if DEBUG_CONCIDENT 805 SkDebugf("%s 1 this=%d other=%d t [%d] %1.9g (%1.9g,%1.9g)\n", 806 __FUNCTION__, fID, other.fID, tIndexStart - 1, 807 fTs[tIndexStart].fT, xyAtT(tIndexStart).fX, 808 xyAtT(tIndexStart).fY); 809 #endif 810 addTPair(fTs[tIndexStart].fT, other, other.fTs[oIndex].fT, false); 811 } 812 if (nextT < 1 && fTs[tIndex].fWindValue) { 813 #if DEBUG_CONCIDENT 814 SkDebugf("%s 2 this=%d other=%d t [%d] %1.9g (%1.9g,%1.9g)\n", 815 __FUNCTION__, fID, other.fID, tIndex, 816 fTs[tIndex].fT, xyAtT(tIndex).fX, 817 xyAtT(tIndex).fY); 818 #endif 819 addTPair(fTs[tIndex].fT, other, other.fTs[oIndexStart].fT, false); 820 } 821 } else { 822 SkASSERT(!other.fTs[oIndexStart].fWindValue); 823 if (oIndexStart > 0 && other.fTs[oIndexStart - 1].fWindValue) { 824 #if DEBUG_CONCIDENT 825 SkDebugf("%s 3 this=%d other=%d t [%d] %1.9g (%1.9g,%1.9g)\n", 826 __FUNCTION__, fID, other.fID, oIndexStart - 1, 827 other.fTs[oIndexStart].fT, other.xyAtT(oIndexStart).fX, 828 other.xyAtT(oIndexStart).fY); 829 other.debugAddTPair(other.fTs[oIndexStart].fT, *this, fTs[tIndex].fT); 830 #endif 831 } 832 if (oNextT < 1 && other.fTs[oIndex].fWindValue) { 833 #if DEBUG_CONCIDENT 834 SkDebugf("%s 4 this=%d other=%d t [%d] %1.9g (%1.9g,%1.9g)\n", 835 __FUNCTION__, fID, other.fID, oIndex, 836 other.fTs[oIndex].fT, other.xyAtT(oIndex).fX, 837 other.xyAtT(oIndex).fY); 838 other.debugAddTPair(other.fTs[oIndex].fT, *this, fTs[tIndexStart].fT); 839 #endif 840 } 841 } 842 } 843 844 void addCoinOutsides(const SkTDArray<double>& outsideTs, Segment& other, 845 double oEnd) { 846 // walk this to outsideTs[0] 847 // walk other to outsideTs[1] 848 // if either is > 0, add a pointer to the other, copying adjacent winding 849 int tIndex = -1; 850 int oIndex = -1; 851 double tStart = outsideTs[0]; 852 double oStart = outsideTs[1]; 853 do { 854 ++tIndex; 855 } while (tStart - fTs[tIndex].fT >= FLT_EPSILON); 856 do { 857 ++oIndex; 858 } while (oStart - other.fTs[oIndex].fT >= FLT_EPSILON); 859 if (tIndex > 0 || oIndex > 0) { 860 addTPair(tStart, other, oStart, false); 861 } 862 tStart = fTs[tIndex].fT; 863 oStart = other.fTs[oIndex].fT; 864 do { 865 double nextT; 866 do { 867 nextT = fTs[++tIndex].fT; 868 } while (nextT - tStart < FLT_EPSILON); 869 tStart = nextT; 870 do { 871 nextT = other.fTs[++oIndex].fT; 872 } while (nextT - oStart < FLT_EPSILON); 873 oStart = nextT; 874 if (tStart == 1 && oStart == 1) { 875 break; 876 } 877 addTPair(tStart, other, oStart, false); 878 } while (tStart < 1 && oStart < 1 && oEnd - oStart >= FLT_EPSILON); 879 } 880 881 void addCubic(const SkPoint pts[4]) { 882 init(pts, SkPath::kCubic_Verb); 883 fBounds.setCubicBounds(pts); 884 } 885 886 // FIXME: this needs to defer add for aligned consecutive line segments 887 SkPoint addCurveTo(int start, int end, SkPath& path, bool active) { 888 SkPoint edge[4]; 889 // OPTIMIZE? if not active, skip remainder and return xy_at_t(end) 890 (*SegmentSubDivide[fVerb])(fPts, fTs[start].fT, fTs[end].fT, edge); 891 if (active) { 892 #if DEBUG_PATH_CONSTRUCTION 893 SkDebugf("%s %s (%1.9g,%1.9g)", __FUNCTION__, 894 kLVerbStr[fVerb], edge[1].fX, edge[1].fY); 895 if (fVerb > 1) { 896 SkDebugf(" (%1.9g,%1.9g)", edge[2].fX, edge[2].fY); 897 } 898 if (fVerb > 2) { 899 SkDebugf(" (%1.9g,%1.9g)", edge[3].fX, edge[3].fY); 900 } 901 SkDebugf("\n"); 902 #endif 903 switch (fVerb) { 904 case SkPath::kLine_Verb: 905 path.lineTo(edge[1].fX, edge[1].fY); 906 break; 907 case SkPath::kQuad_Verb: 908 path.quadTo(edge[1].fX, edge[1].fY, edge[2].fX, edge[2].fY); 909 break; 910 case SkPath::kCubic_Verb: 911 path.cubicTo(edge[1].fX, edge[1].fY, edge[2].fX, edge[2].fY, 912 edge[3].fX, edge[3].fY); 913 break; 914 } 915 } 916 return edge[fVerb]; 917 } 918 919 void addLine(const SkPoint pts[2]) { 920 init(pts, SkPath::kLine_Verb); 921 fBounds.set(pts, 2); 922 } 923 924 const SkPoint& addMoveTo(int tIndex, SkPath& path, bool active) { 925 const SkPoint& pt = xyAtT(tIndex); 926 if (active) { 927 #if DEBUG_PATH_CONSTRUCTION 928 SkDebugf("%s (%1.9g,%1.9g)\n", __FUNCTION__, pt.fX, pt.fY); 929 #endif 930 path.moveTo(pt.fX, pt.fY); 931 } 932 return pt; 933 } 934 935 // add 2 to edge or out of range values to get T extremes 936 void addOtherT(int index, double otherT, int otherIndex) { 937 Span& span = fTs[index]; 938 span.fOtherT = otherT; 939 span.fOtherIndex = otherIndex; 940 } 941 942 void addQuad(const SkPoint pts[3]) { 943 init(pts, SkPath::kQuad_Verb); 944 fBounds.setQuadBounds(pts); 945 } 946 947 // Defer all coincident edge processing until 948 // after normal intersections have been computed 949 950// no need to be tricky; insert in normal T order 951// resolve overlapping ts when considering coincidence later 952 953 // add non-coincident intersection. Resulting edges are sorted in T. 954 int addT(double newT, Segment* other) { 955 // FIXME: in the pathological case where there is a ton of intercepts, 956 // binary search? 957 int insertedAt = -1; 958 size_t tCount = fTs.count(); 959 for (size_t index = 0; index < tCount; ++index) { 960 // OPTIMIZATION: if there are three or more identical Ts, then 961 // the fourth and following could be further insertion-sorted so 962 // that all the edges are clockwise or counterclockwise. 963 // This could later limit segment tests to the two adjacent 964 // neighbors, although it doesn't help with determining which 965 // circular direction to go in. 966 if (newT < fTs[index].fT) { 967 insertedAt = index; 968 break; 969 } 970 } 971 Span* span; 972 if (insertedAt >= 0) { 973 span = fTs.insert(insertedAt); 974 } else { 975 insertedAt = tCount; 976 span = fTs.append(); 977 } 978 span->fT = newT; 979 span->fOther = other; 980 span->fPt.fX = SK_ScalarNaN; 981 span->fWindSum = SK_MinS32; 982 span->fWindValue = 1; 983 if ((span->fDone = newT == 1)) { 984 ++fDoneSpans; 985 } 986 return insertedAt; 987 } 988 989 // set spans from start to end to decrement by one 990 // note this walks other backwards 991 // FIMXE: there's probably an edge case that can be constructed where 992 // two span in one segment are separated by float epsilon on one span but 993 // not the other, if one segment is very small. For this 994 // case the counts asserted below may or may not be enough to separate the 995 // spans. Even if the counts work out, what if the spans aren't correctly 996 // sorted? It feels better in such a case to match the span's other span 997 // pointer since both coincident segments must contain the same spans. 998 void addTCancel(double startT, double endT, Segment& other, 999 double oStartT, double oEndT) { 1000 SkASSERT(endT - startT >= FLT_EPSILON); 1001 SkASSERT(oEndT - oStartT >= FLT_EPSILON); 1002 int index = 0; 1003 while (startT - fTs[index].fT >= FLT_EPSILON) { 1004 ++index; 1005 } 1006 int oIndex = other.fTs.count(); 1007 while (other.fTs[--oIndex].fT - oEndT > -FLT_EPSILON) 1008 ; 1009 double tRatio = (oEndT - oStartT) / (endT - startT); 1010 Span* test = &fTs[index]; 1011 Span* oTest = &other.fTs[oIndex]; 1012 SkTDArray<double> outsideTs; 1013 SkTDArray<double> oOutsideTs; 1014 do { 1015 bool decrement = test->fWindValue && oTest->fWindValue; 1016 bool track = test->fWindValue || oTest->fWindValue; 1017 double testT = test->fT; 1018 double oTestT = oTest->fT; 1019 Span* span = test; 1020 do { 1021 if (decrement) { 1022 decrementSpan(span); 1023 } else if (track && span->fT < 1 && oTestT < 1) { 1024 TrackOutside(outsideTs, span->fT, oTestT); 1025 } 1026 span = &fTs[++index]; 1027 } while (span->fT - testT < FLT_EPSILON); 1028 Span* oSpan = oTest; 1029 double otherTMatchStart = oEndT - (span->fT - startT) * tRatio; 1030 double otherTMatchEnd = oEndT - (test->fT - startT) * tRatio; 1031 SkDEBUGCODE(int originalWindValue = oSpan->fWindValue); 1032 while (oSpan->fT > otherTMatchStart - FLT_EPSILON 1033 && otherTMatchEnd - FLT_EPSILON > oSpan->fT) { 1034 SkASSERT(originalWindValue == oSpan->fWindValue); 1035 if (decrement) { 1036 other.decrementSpan(oSpan); 1037 } else if (track && oSpan->fT < 1 && testT < 1) { 1038 TrackOutside(oOutsideTs, oSpan->fT, testT); 1039 } 1040 if (!oIndex) { 1041 break; 1042 } 1043 oSpan = &other.fTs[--oIndex]; 1044 } 1045 test = span; 1046 oTest = oSpan; 1047 } while (test->fT < endT - FLT_EPSILON); 1048 SkASSERT(!oIndex || oTest->fT < oStartT + FLT_EPSILON); 1049 // FIXME: determine if canceled edges need outside ts added 1050 if (!done() && outsideTs.count()) { 1051 double tStart = outsideTs[0]; 1052 double oStart = outsideTs[1]; 1053 addCancelOutsides(tStart, oStart, other, oEndT); 1054 int count = outsideTs.count(); 1055 if (count > 2) { 1056 double tStart = outsideTs[count - 2]; 1057 double oStart = outsideTs[count - 1]; 1058 addCancelOutsides(tStart, oStart, other, oEndT); 1059 } 1060 } 1061 if (!other.done() && oOutsideTs.count()) { 1062 double tStart = oOutsideTs[0]; 1063 double oStart = oOutsideTs[1]; 1064 other.addCancelOutsides(tStart, oStart, *this, endT); 1065 } 1066 } 1067 1068 // set spans from start to end to increment the greater by one and decrement 1069 // the lesser 1070 void addTCoincident(double startT, double endT, Segment& other, 1071 double oStartT, double oEndT) { 1072 SkASSERT(endT - startT >= FLT_EPSILON); 1073 SkASSERT(oEndT - oStartT >= FLT_EPSILON); 1074 int index = 0; 1075 while (startT - fTs[index].fT >= FLT_EPSILON) { 1076 ++index; 1077 } 1078 int oIndex = 0; 1079 while (oStartT - other.fTs[oIndex].fT >= FLT_EPSILON) { 1080 ++oIndex; 1081 } 1082 double tRatio = (oEndT - oStartT) / (endT - startT); 1083 Span* test = &fTs[index]; 1084 Span* oTest = &other.fTs[oIndex]; 1085 SkTDArray<double> outsideTs; 1086 SkTDArray<double> xOutsideTs; 1087 SkTDArray<double> oOutsideTs; 1088 SkTDArray<double> oxOutsideTs; 1089 do { 1090 bool transfer = test->fWindValue && oTest->fWindValue; 1091 bool decrementOther = test->fWindValue >= oTest->fWindValue; 1092 Span* end = test; 1093 double startT = end->fT; 1094 int startIndex = index; 1095 double oStartT = oTest->fT; 1096 int oStartIndex = oIndex; 1097 do { 1098 if (transfer) { 1099 if (decrementOther) { 1100 SkASSERT(abs(end->fWindValue) < gDebugMaxWindValue); 1101 ++(end->fWindValue); 1102 } else if (decrementSpan(end)) { 1103 TrackOutside(outsideTs, end->fT, oStartT); 1104 } 1105 } else if (oTest->fWindValue) { 1106 SkASSERT(!decrementOther); 1107 if (startIndex > 0 && fTs[startIndex - 1].fWindValue) { 1108 TrackOutside(xOutsideTs, end->fT, oStartT); 1109 } 1110 } 1111 end = &fTs[++index]; 1112 } while (end->fT - test->fT < FLT_EPSILON); 1113 // because of the order in which coincidences are resolved, this and other 1114 // may not have the same intermediate points. Compute the corresponding 1115 // intermediate T values (using this as the master, other as the follower) 1116 // and walk other conditionally -- hoping that it catches up in the end 1117 double otherTMatch = (test->fT - startT) * tRatio + oStartT; 1118 Span* oEnd = oTest; 1119 while (oEnd->fT < oEndT - FLT_EPSILON && oEnd->fT - otherTMatch < FLT_EPSILON) { 1120 if (transfer) { 1121 if (!decrementOther) { 1122 SkASSERT(abs(oEnd->fWindValue) < gDebugMaxWindValue); 1123 ++(oEnd->fWindValue); 1124 } else if (other.decrementSpan(oEnd)) { 1125 TrackOutside(oOutsideTs, oEnd->fT, startT); 1126 } 1127 } else if (test->fWindValue) { 1128 SkASSERT(!decrementOther); 1129 if (oStartIndex > 0 && other.fTs[oStartIndex - 1].fWindValue) { 1130 SkASSERT(0); // track for later? 1131 } 1132 } 1133 oEnd = &other.fTs[++oIndex]; 1134 } 1135 test = end; 1136 oTest = oEnd; 1137 } while (test->fT < endT - FLT_EPSILON); 1138 SkASSERT(oTest->fT < oEndT + FLT_EPSILON); 1139 SkASSERT(oTest->fT > oEndT - FLT_EPSILON); 1140 if (!done()) { 1141 if (outsideTs.count()) { 1142 addCoinOutsides(outsideTs, other, oEndT); 1143 } 1144 if (xOutsideTs.count()) { 1145 addCoinOutsides(xOutsideTs, other, oEndT); 1146 } 1147 } 1148 if (!other.done() && oOutsideTs.count()) { 1149 other.addCoinOutsides(oOutsideTs, *this, endT); 1150 } 1151 } 1152 1153 // FIXME: this doesn't prevent the same span from being added twice 1154 // fix in caller, assert here? 1155 void addTPair(double t, Segment& other, double otherT, bool borrowWind) { 1156 int tCount = fTs.count(); 1157 for (int tIndex = 0; tIndex < tCount; ++tIndex) { 1158 const Span& span = fTs[tIndex]; 1159 if (span.fT - t >= FLT_EPSILON) { 1160 break; 1161 } 1162 if (span.fT - t < FLT_EPSILON && span.fOther == &other && span.fOtherT == otherT) { 1163#if DEBUG_ADD_T_PAIR 1164 SkDebugf("%s addTPair duplicate this=%d %1.9g other=%d %1.9g\n", 1165 __FUNCTION__, fID, t, other.fID, otherT); 1166#endif 1167 return; 1168 } 1169 } 1170#if DEBUG_ADD_T_PAIR 1171 SkDebugf("%s addTPair this=%d %1.9g other=%d %1.9g\n", 1172 __FUNCTION__, fID, t, other.fID, otherT); 1173#endif 1174 int insertedAt = addT(t, &other); 1175 int otherInsertedAt = other.addT(otherT, this); 1176 addOtherT(insertedAt, otherT, otherInsertedAt); 1177 other.addOtherT(otherInsertedAt, t, insertedAt); 1178 matchWindingValue(insertedAt, t, borrowWind); 1179 other.matchWindingValue(otherInsertedAt, otherT, borrowWind); 1180 } 1181 1182 void addTwoAngles(int start, int end, SkTDArray<Angle>& angles) const { 1183 // add edge leading into junction 1184 if (fTs[SkMin32(end, start)].fWindValue > 0) { 1185 addAngle(angles, end, start); 1186 } 1187 // add edge leading away from junction 1188 int step = SkSign32(end - start); 1189 int tIndex = nextSpan(end, step); 1190 if (tIndex >= 0 && fTs[SkMin32(end, tIndex)].fWindValue > 0) { 1191 addAngle(angles, end, tIndex); 1192 } 1193 } 1194 1195 const Bounds& bounds() const { 1196 return fBounds; 1197 } 1198 1199 void buildAngles(int index, SkTDArray<Angle>& angles) const { 1200 double referenceT = fTs[index].fT; 1201 int lesser = index; 1202 while (--lesser >= 0 && referenceT - fTs[lesser].fT < FLT_EPSILON) { 1203 buildAnglesInner(lesser, angles); 1204 } 1205 do { 1206 buildAnglesInner(index, angles); 1207 } while (++index < fTs.count() && fTs[index].fT - referenceT < FLT_EPSILON); 1208 } 1209 1210 void buildAnglesInner(int index, SkTDArray<Angle>& angles) const { 1211 Span* span = &fTs[index]; 1212 Segment* other = span->fOther; 1213 // if there is only one live crossing, and no coincidence, continue 1214 // in the same direction 1215 // if there is coincidence, the only choice may be to reverse direction 1216 // find edge on either side of intersection 1217 int oIndex = span->fOtherIndex; 1218 // if done == -1, prior span has already been processed 1219 int step = 1; 1220 int next = other->nextSpan(oIndex, step); 1221 if (next < 0) { 1222 step = -step; 1223 next = other->nextSpan(oIndex, step); 1224 } 1225 // add candidate into and away from junction 1226 other->addTwoAngles(next, oIndex, angles); 1227 } 1228 1229 bool cancels(const Segment& other) const { 1230 SkASSERT(fVerb == SkPath::kLine_Verb); 1231 SkASSERT(other.fVerb == SkPath::kLine_Verb); 1232 SkPoint dxy = fPts[0] - fPts[1]; 1233 SkPoint odxy = other.fPts[0] - other.fPts[1]; 1234 return dxy.fX * odxy.fX < 0 || dxy.fY * odxy.fY < 0; 1235 } 1236 1237 // figure out if the segment's ascending T goes clockwise or not 1238 // not enough context to write this as shown 1239 // instead, add all segments meeting at the top 1240 // sort them using buildAngleList 1241 // find the first in the sort 1242 // see if ascendingT goes to top 1243 bool clockwise(int /* tIndex */) const { 1244 SkASSERT(0); // incomplete 1245 return false; 1246 } 1247 1248 int computeSum(int startIndex, int endIndex) { 1249 SkTDArray<Angle> angles; 1250 addTwoAngles(startIndex, endIndex, angles); 1251 buildAngles(endIndex, angles); 1252 SkTDArray<Angle*> sorted; 1253 sortAngles(angles, sorted); 1254 int angleCount = angles.count(); 1255 const Angle* angle; 1256 const Segment* base; 1257 int winding; 1258 int firstIndex = 0; 1259 do { 1260 angle = sorted[firstIndex]; 1261 base = angle->segment(); 1262 winding = base->windSum(angle); 1263 if (winding != SK_MinS32) { 1264 break; 1265 } 1266 if (++firstIndex == angleCount) { 1267 return SK_MinS32; 1268 } 1269 } while (true); 1270 // turn winding into contourWinding 1271 int spanWinding = base->spanSign(angle); 1272 bool inner = useInnerWinding(winding + spanWinding, winding); 1273 #if DEBUG_WINDING 1274 SkDebugf("%s --- spanWinding=%d winding=%d sign=%d inner=%d result=%d\n", __FUNCTION__, 1275 spanWinding, winding, angle->sign(), inner, 1276 inner ? winding + spanWinding : winding); 1277 #endif 1278 if (inner) { 1279 winding += spanWinding; 1280 } 1281 #if DEBUG_SORT 1282 base->debugShowSort(sorted, firstIndex, winding); 1283 #endif 1284 int nextIndex = firstIndex + 1; 1285 int lastIndex = firstIndex != 0 ? firstIndex : angleCount; 1286 winding -= base->spanSign(angle); 1287 do { 1288 if (nextIndex == angleCount) { 1289 nextIndex = 0; 1290 } 1291 angle = sorted[nextIndex]; 1292 Segment* segment = angle->segment(); 1293 int maxWinding = winding; 1294 winding -= segment->spanSign(angle); 1295 if (segment->windSum(angle) == SK_MinS32) { 1296 if (useInnerWinding(maxWinding, winding)) { 1297 maxWinding = winding; 1298 } 1299 segment->markAndChaseWinding(angle, maxWinding); 1300 } 1301 } while (++nextIndex != lastIndex); 1302 return windSum(SkMin32(startIndex, endIndex)); 1303 } 1304 1305 int crossedSpan(const SkPoint& basePt, SkScalar& bestY, double& hitT) const { 1306 int bestT = -1; 1307 SkScalar top = bounds().fTop; 1308 SkScalar bottom = bounds().fBottom; 1309 int end = 0; 1310 do { 1311 int start = end; 1312 end = nextSpan(start, 1); 1313 if (fTs[start].fWindValue == 0) { 1314 continue; 1315 } 1316 SkPoint edge[4]; 1317 // OPTIMIZE: wrap this so that if start==0 end==fTCount-1 we can 1318 // work with the original data directly 1319 (*SegmentSubDivide[fVerb])(fPts, fTs[start].fT, fTs[end].fT, edge); 1320 // intersect ray starting at basePt with edge 1321 Intersections intersections; 1322 int pts = (*VSegmentIntersect[fVerb])(edge, top, bottom, basePt.fX, 1323 false, intersections); 1324 if (pts == 0) { 1325 continue; 1326 } 1327 if (pts > 1 && fVerb == SkPath::kLine_Verb) { 1328 // if the intersection is edge on, wait for another one 1329 continue; 1330 } 1331 SkASSERT(pts == 1); // FIXME: more code required to disambiguate 1332 SkPoint pt; 1333 double foundT = intersections.fT[0][0]; 1334 (*SegmentXYAtT[fVerb])(fPts, foundT, &pt); 1335 if (bestY < pt.fY && pt.fY < basePt.fY) { 1336 bestY = pt.fY; 1337 bestT = foundT < 1 ? start : end; 1338 hitT = fTs[start].fT + (fTs[end].fT - fTs[start].fT) * foundT; 1339 } 1340 } while (fTs[end].fT != 1); 1341 return bestT; 1342 } 1343 1344 bool crossedSpanHalves(const SkPoint& basePt, bool leftHalf, bool rightHalf) { 1345 // if a segment is connected to this one, consider it crossing 1346 int tIndex; 1347 if (fPts[0].fX == basePt.fX) { 1348 tIndex = 0; 1349 do { 1350 const Span& sSpan = fTs[tIndex]; 1351 const Segment* sOther = sSpan.fOther; 1352 if (!sOther->fTs[sSpan.fOtherIndex].fWindValue) { 1353 continue; 1354 } 1355 if (leftHalf ? sOther->fBounds.fLeft < basePt.fX 1356 : sOther->fBounds.fRight > basePt.fX) { 1357 return true; 1358 } 1359 } while (fTs[++tIndex].fT == 0); 1360 } 1361 if (fPts[fVerb].fX == basePt.fX) { 1362 tIndex = fTs.count() - 1; 1363 do { 1364 const Span& eSpan = fTs[tIndex]; 1365 const Segment* eOther = eSpan.fOther; 1366 if (!eOther->fTs[eSpan.fOtherIndex].fWindValue) { 1367 continue; 1368 } 1369 if (leftHalf ? eOther->fBounds.fLeft < basePt.fX 1370 : eOther->fBounds.fRight > basePt.fX) { 1371 return true; 1372 } 1373 } while (fTs[--tIndex].fT == 1); 1374 } 1375 return false; 1376 } 1377 1378 bool decrementSpan(Span* span) { 1379 SkASSERT(span->fWindValue > 0); 1380 if (--(span->fWindValue) == 0) { 1381 span->fDone = true; 1382 ++fDoneSpans; 1383 return true; 1384 } 1385 return false; 1386 } 1387 1388 bool done() const { 1389 SkASSERT(fDoneSpans <= fTs.count()); 1390 return fDoneSpans == fTs.count(); 1391 } 1392 1393 bool done(const Angle& angle) const { 1394 int start = angle.start(); 1395 int end = angle.end(); 1396 const Span& mSpan = fTs[SkMin32(start, end)]; 1397 return mSpan.fDone; 1398 } 1399 1400 // so the span needs to contain the pairing info found here 1401 // this should include the winding computed for the edge, and 1402 // what edge it connects to, and whether it is discarded 1403 // (maybe discarded == abs(winding) > 1) ? 1404 // only need derivatives for duration of sorting, add a new struct 1405 // for pairings, remove extra spans that have zero length and 1406 // reference an unused other 1407 // for coincident, the last span on the other may be marked done 1408 // (always?) 1409 1410 // if loop is exhausted, contour may be closed. 1411 // FIXME: pass in close point so we can check for closure 1412 1413 // given a segment, and a sense of where 'inside' is, return the next 1414 // segment. If this segment has an intersection, or ends in multiple 1415 // segments, find the mate that continues the outside. 1416 // note that if there are multiples, but no coincidence, we can limit 1417 // choices to connections in the correct direction 1418 1419 // mark found segments as done 1420 1421 // start is the index of the beginning T of this edge 1422 // it is guaranteed to have an end which describes a non-zero length (?) 1423 // winding -1 means ccw, 1 means cw 1424 // firstFind allows coincident edges to be treated differently 1425 Segment* findNext(SkTDArray<Span*>& chase, bool firstFind, bool active, 1426 const int startIndex, const int endIndex, int& nextStart, 1427 int& nextEnd, int& winding, int& spanWinding) { 1428 int outerWinding = winding; 1429 int innerWinding = winding + spanWinding; 1430 #if DEBUG_WINDING 1431 SkDebugf("%s winding=%d spanWinding=%d outerWinding=%d innerWinding=%d\n", 1432 __FUNCTION__, winding, spanWinding, outerWinding, innerWinding); 1433 #endif 1434 if (useInnerWinding(outerWinding, innerWinding)) { 1435 outerWinding = innerWinding; 1436 } 1437 SkASSERT(startIndex != endIndex); 1438 int count = fTs.count(); 1439 SkASSERT(startIndex < endIndex ? startIndex < count - 1 1440 : startIndex > 0); 1441 int step = SkSign32(endIndex - startIndex); 1442 int end = nextSpan(startIndex, step); 1443 SkASSERT(end >= 0); 1444 Span* endSpan = &fTs[end]; 1445 Segment* other; 1446 if (isSimple(end)) { 1447 // mark the smaller of startIndex, endIndex done, and all adjacent 1448 // spans with the same T value (but not 'other' spans) 1449 #if DEBUG_WINDING 1450 SkDebugf("%s simple\n", __FUNCTION__); 1451 #endif 1452 markDone(SkMin32(startIndex, endIndex), outerWinding); 1453 other = endSpan->fOther; 1454 nextStart = endSpan->fOtherIndex; 1455 double startT = other->fTs[nextStart].fT; 1456 nextEnd = nextStart; 1457 do { 1458 nextEnd += step; 1459 } while (fabs(startT - other->fTs[nextEnd].fT) < FLT_EPSILON); 1460 SkASSERT(step < 0 ? nextEnd >= 0 : nextEnd < other->fTs.count()); 1461 return other; 1462 } 1463 // more than one viable candidate -- measure angles to find best 1464 SkTDArray<Angle> angles; 1465 SkASSERT(startIndex - endIndex != 0); 1466 SkASSERT((startIndex - endIndex < 0) ^ (step < 0)); 1467 addTwoAngles(startIndex, end, angles); 1468 buildAngles(end, angles); 1469 SkTDArray<Angle*> sorted; 1470 sortAngles(angles, sorted); 1471 int angleCount = angles.count(); 1472 int firstIndex = findStartingEdge(sorted, startIndex, end); 1473 SkASSERT(firstIndex >= 0); 1474 #if DEBUG_SORT 1475 debugShowSort(sorted, firstIndex, winding); 1476 #endif 1477 SkASSERT(sorted[firstIndex]->segment() == this); 1478 #if DEBUG_WINDING 1479 SkDebugf("%s sign=%d\n", __FUNCTION__, sorted[firstIndex]->sign()); 1480 #endif 1481 int sumWinding = winding - spanSign(sorted[firstIndex]); 1482 int nextIndex = firstIndex + 1; 1483 int lastIndex = firstIndex != 0 ? firstIndex : angleCount; 1484 const Angle* foundAngle = NULL; 1485 bool foundDone = false; 1486 // iterate through the angle, and compute everyone's winding 1487 int toggleWinding = SK_MinS32; 1488 bool flipFound = false; 1489 int flipped = 1; 1490 Segment* nextSegment; 1491 do { 1492 if (nextIndex == angleCount) { 1493 nextIndex = 0; 1494 } 1495 const Angle* nextAngle = sorted[nextIndex]; 1496 int maxWinding = sumWinding; 1497 nextSegment = nextAngle->segment(); 1498 sumWinding -= nextSegment->spanSign(nextAngle); 1499 SkASSERT(abs(sumWinding) <= gDebugMaxWindSum); 1500 #if DEBUG_WINDING 1501 SkDebugf("%s maxWinding=%d sumWinding=%d sign=%d\n", __FUNCTION__, 1502 maxWinding, sumWinding, nextAngle->sign()); 1503 #endif 1504 if (maxWinding * sumWinding < 0) { 1505 flipFound ^= true; 1506 #if DEBUG_WINDING 1507 SkDebugf("%s flipFound=%d maxWinding=%d sumWinding=%d\n", 1508 __FUNCTION__, flipFound, maxWinding, sumWinding); 1509 #endif 1510 } 1511 if (!sumWinding) { 1512 if (!active) { 1513 markDone(SkMin32(startIndex, endIndex), outerWinding); 1514 // FIXME: seems like a bug that this isn't calling userInnerWinding 1515 nextSegment->markWinding(SkMin32(nextAngle->start(), 1516 nextAngle->end()), maxWinding); 1517 #if DEBUG_WINDING 1518 SkDebugf("%s inactive\n", __FUNCTION__); 1519 #endif 1520 return NULL; 1521 } 1522 if (!foundAngle || foundDone) { 1523 foundAngle = nextAngle; 1524 foundDone = nextSegment->done(*nextAngle); 1525 if (flipFound || (maxWinding * outerWinding < 0)) { 1526 flipped = -flipped; 1527 #if DEBUG_WINDING 1528 SkDebugf("%s flipped=%d flipFound=%d maxWinding=%d" 1529 " outerWinding=%d\n", __FUNCTION__, flipped, 1530 flipFound, maxWinding, outerWinding); 1531 #endif 1532 } 1533 } 1534 continue; 1535 } 1536 if (!maxWinding && !foundAngle) { 1537 #if DEBUG_WINDING 1538 if (flipped > 0) { 1539 SkDebugf("%s sumWinding=%d * outerWinding=%d < 0 (%s)\n", 1540 __FUNCTION__, sumWinding, outerWinding, 1541 sumWinding * outerWinding < 0 ? "true" : "false"); 1542 } 1543 #endif 1544 if (sumWinding * outerWinding < 0 && flipped > 0) { 1545 #if DEBUG_WINDING 1546 SkDebugf("%s toggleWinding=%d\n", __FUNCTION__, sumWinding); 1547 #endif 1548 toggleWinding = sumWinding; 1549 } else if (outerWinding != sumWinding) { 1550 #if DEBUG_WINDING 1551 SkDebugf("%s outerWinding=%d != sumWinding=%d winding=%d\n", 1552 __FUNCTION__, outerWinding, sumWinding, winding); 1553 #endif 1554 winding = sumWinding; 1555 } 1556 foundAngle = nextAngle; 1557 if (flipFound) { 1558 flipped = -flipped; 1559 #if DEBUG_WINDING 1560 SkDebugf("%s flipped flipFound=%d\n", __FUNCTION__, flipFound); 1561 #endif 1562 } 1563 } 1564 if (nextSegment->done()) { 1565 continue; 1566 } 1567 // if the winding is non-zero, nextAngle does not connect to 1568 // current chain. If we haven't done so already, mark the angle 1569 // as done, record the winding value, and mark connected unambiguous 1570 // segments as well. 1571 if (nextSegment->windSum(nextAngle) == SK_MinS32) { 1572 if (useInnerWinding(maxWinding, sumWinding)) { 1573 maxWinding = sumWinding; 1574 } 1575 Span* last; 1576 if (foundAngle) { 1577 last = nextSegment->markAndChaseWinding(nextAngle, maxWinding); 1578 } else { 1579 last = nextSegment->markAndChaseDone(nextAngle, maxWinding); 1580 } 1581 if (last) { 1582 *chase.append() = last; 1583 } 1584 } 1585 } while (++nextIndex != lastIndex); 1586 SkASSERT(sorted[firstIndex]->segment() == this); 1587 markDone(SkMin32(startIndex, endIndex), outerWinding); 1588 if (!foundAngle) { 1589 return NULL; 1590 } 1591 nextStart = foundAngle->start(); 1592 nextEnd = foundAngle->end(); 1593 nextSegment = foundAngle->segment(); 1594 spanWinding = SkSign32(spanWinding) * flipped * nextSegment->windValue( 1595 SkMin32(nextStart, nextEnd)); 1596 if (toggleWinding != SK_MinS32) { 1597 winding = toggleWinding; 1598 spanWinding = -spanWinding; 1599 } 1600 #if DEBUG_WINDING 1601 SkDebugf("%s spanWinding=%d\n", __FUNCTION__, spanWinding); 1602 #endif 1603 return nextSegment; 1604 } 1605 1606 int findStartingEdge(SkTDArray<Angle*>& sorted, int start, int end) { 1607 int angleCount = sorted.count(); 1608 int firstIndex = -1; 1609 for (int angleIndex = 0; angleIndex < angleCount; ++angleIndex) { 1610 const Angle* angle = sorted[angleIndex]; 1611 if (angle->segment() == this && angle->start() == end && 1612 angle->end() == start) { 1613 firstIndex = angleIndex; 1614 break; 1615 } 1616 } 1617 return firstIndex; 1618 } 1619 1620 // FIXME: this is tricky code; needs its own unit test 1621 void findTooCloseToCall(int /* winding */ ) { // FIXME: winding should be considered 1622 int count = fTs.count(); 1623 if (count < 3) { // require t=0, x, 1 at minimum 1624 return; 1625 } 1626 int matchIndex = 0; 1627 int moCount; 1628 Span* match; 1629 Segment* mOther; 1630 do { 1631 match = &fTs[matchIndex]; 1632 mOther = match->fOther; 1633 moCount = mOther->fTs.count(); 1634 if (moCount >= 3) { 1635 break; 1636 } 1637 if (++matchIndex >= count) { 1638 return; 1639 } 1640 } while (true); // require t=0, x, 1 at minimum 1641 // OPTIMIZATION: defer matchPt until qualifying toCount is found? 1642 const SkPoint* matchPt = &xyAtT(match); 1643 // look for a pair of nearby T values that map to the same (x,y) value 1644 // if found, see if the pair of other segments share a common point. If 1645 // so, the span from here to there is coincident. 1646 for (int index = matchIndex + 1; index < count; ++index) { 1647 Span* test = &fTs[index]; 1648 if (test->fDone) { 1649 continue; 1650 } 1651 Segment* tOther = test->fOther; 1652 int toCount = tOther->fTs.count(); 1653 if (toCount < 3) { // require t=0, x, 1 at minimum 1654 continue; 1655 } 1656 const SkPoint* testPt = &xyAtT(test); 1657 if (*matchPt != *testPt) { 1658 matchIndex = index; 1659 moCount = toCount; 1660 match = test; 1661 mOther = tOther; 1662 matchPt = testPt; 1663 continue; 1664 } 1665 int moStart = -1; 1666 int moEnd = -1; 1667 double moStartT, moEndT; 1668 for (int moIndex = 0; moIndex < moCount; ++moIndex) { 1669 Span& moSpan = mOther->fTs[moIndex]; 1670 if (moSpan.fDone) { 1671 continue; 1672 } 1673 if (moSpan.fOther == this) { 1674 if (moSpan.fOtherT == match->fT) { 1675 moStart = moIndex; 1676 moStartT = moSpan.fT; 1677 } 1678 continue; 1679 } 1680 if (moSpan.fOther == tOther) { 1681 SkASSERT(moEnd == -1); 1682 moEnd = moIndex; 1683 moEndT = moSpan.fT; 1684 } 1685 } 1686 if (moStart < 0 || moEnd < 0) { 1687 continue; 1688 } 1689 // FIXME: if moStartT, moEndT are initialized to NaN, can skip this test 1690 if (moStartT == moEndT) { 1691 continue; 1692 } 1693 int toStart = -1; 1694 int toEnd = -1; 1695 double toStartT, toEndT; 1696 for (int toIndex = 0; toIndex < toCount; ++toIndex) { 1697 Span& toSpan = tOther->fTs[toIndex]; 1698 if (toSpan.fOther == this) { 1699 if (toSpan.fOtherT == test->fT) { 1700 toStart = toIndex; 1701 toStartT = toSpan.fT; 1702 } 1703 continue; 1704 } 1705 if (toSpan.fOther == mOther && toSpan.fOtherT == moEndT) { 1706 SkASSERT(toEnd == -1); 1707 toEnd = toIndex; 1708 toEndT = toSpan.fT; 1709 } 1710 } 1711 // FIXME: if toStartT, toEndT are initialized to NaN, can skip this test 1712 if (toStart <= 0 || toEnd <= 0) { 1713 continue; 1714 } 1715 if (toStartT == toEndT) { 1716 continue; 1717 } 1718 // test to see if the segment between there and here is linear 1719 if (!mOther->isLinear(moStart, moEnd) 1720 || !tOther->isLinear(toStart, toEnd)) { 1721 continue; 1722 } 1723 // FIXME: defer implementation until the rest works 1724 // this may share code with regular coincident detection 1725 SkASSERT(0); 1726 #if 0 1727 if (flipped) { 1728 mOther->addTCancel(moStart, moEnd, tOther, tStart, tEnd); 1729 } else { 1730 mOther->addTCoincident(moStart, moEnd, tOther, tStart, tEnd); 1731 } 1732 #endif 1733 } 1734 } 1735 1736 // OPTIMIZATION : for a pair of lines, can we compute points at T (cached) 1737 // and use more concise logic like the old edge walker code? 1738 // FIXME: this needs to deal with coincident edges 1739 Segment* findTop(int& tIndex, int& endIndex) { 1740 // iterate through T intersections and return topmost 1741 // topmost tangent from y-min to first pt is closer to horizontal 1742 SkASSERT(!done()); 1743 int firstT; 1744 int lastT; 1745 SkPoint topPt; 1746 topPt.fY = SK_ScalarMax; 1747 int count = fTs.count(); 1748 // see if either end is not done since we want smaller Y of the pair 1749 bool lastDone = true; 1750 for (int index = 0; index < count; ++index) { 1751 const Span& span = fTs[index]; 1752 if (!span.fDone || !lastDone) { 1753 const SkPoint& intercept = xyAtT(&span); 1754 if (topPt.fY > intercept.fY || (topPt.fY == intercept.fY 1755 && topPt.fX > intercept.fX)) { 1756 topPt = intercept; 1757 firstT = lastT = index; 1758 } else if (topPt == intercept) { 1759 lastT = index; 1760 } 1761 } 1762 lastDone = span.fDone; 1763 } 1764 // sort the edges to find the leftmost 1765 int step = 1; 1766 int end = nextSpan(firstT, step); 1767 if (end == -1) { 1768 step = -1; 1769 end = nextSpan(firstT, step); 1770 SkASSERT(end != -1); 1771 } 1772 // if the topmost T is not on end, or is three-way or more, find left 1773 // look for left-ness from tLeft to firstT (matching y of other) 1774 SkTDArray<Angle> angles; 1775 SkASSERT(firstT - end != 0); 1776 addTwoAngles(end, firstT, angles); 1777 buildAngles(firstT, angles); 1778 SkTDArray<Angle*> sorted; 1779 sortAngles(angles, sorted); 1780 // skip edges that have already been processed 1781 firstT = -1; 1782 Segment* leftSegment; 1783 do { 1784 const Angle* angle = sorted[++firstT]; 1785 leftSegment = angle->segment(); 1786 tIndex = angle->end(); 1787 endIndex = angle->start(); 1788 } while (leftSegment->fTs[SkMin32(tIndex, endIndex)].fDone); 1789 return leftSegment; 1790 } 1791 1792 // FIXME: not crazy about this 1793 // when the intersections are performed, the other index is into an 1794 // incomplete array. as the array grows, the indices become incorrect 1795 // while the following fixes the indices up again, it isn't smart about 1796 // skipping segments whose indices are already correct 1797 // assuming we leave the code that wrote the index in the first place 1798 void fixOtherTIndex() { 1799 int iCount = fTs.count(); 1800 for (int i = 0; i < iCount; ++i) { 1801 Span& iSpan = fTs[i]; 1802 double oT = iSpan.fOtherT; 1803 Segment* other = iSpan.fOther; 1804 int oCount = other->fTs.count(); 1805 for (int o = 0; o < oCount; ++o) { 1806 Span& oSpan = other->fTs[o]; 1807 if (oT == oSpan.fT && this == oSpan.fOther) { 1808 iSpan.fOtherIndex = o; 1809 break; 1810 } 1811 } 1812 } 1813 } 1814 1815 // OPTIMIZATION: uses tail recursion. Unwise? 1816 Span* innerChaseDone(int index, int step, int winding) { 1817 int end = nextSpan(index, step); 1818 SkASSERT(end >= 0); 1819 if (multipleSpans(end)) { 1820 return &fTs[end]; 1821 } 1822 const Span& endSpan = fTs[end]; 1823 Segment* other = endSpan.fOther; 1824 index = endSpan.fOtherIndex; 1825 int otherEnd = other->nextSpan(index, step); 1826 Span* last = other->innerChaseDone(index, step, winding); 1827 other->markDone(SkMin32(index, otherEnd), winding); 1828 return last; 1829 } 1830 1831 Span* innerChaseWinding(int index, int step, int winding) { 1832 int end = nextSpan(index, step); 1833 SkASSERT(end >= 0); 1834 if (multipleSpans(end)) { 1835 return &fTs[end]; 1836 } 1837 const Span& endSpan = fTs[end]; 1838 Segment* other = endSpan.fOther; 1839 index = endSpan.fOtherIndex; 1840 int otherEnd = other->nextSpan(index, step); 1841 int min = SkMin32(index, otherEnd); 1842 if (other->fTs[min].fWindSum != SK_MinS32) { 1843 SkASSERT(other->fTs[min].fWindSum == winding); 1844 return NULL; 1845 } 1846 Span* last = other->innerChaseWinding(index, step, winding); 1847 other->markWinding(min, winding); 1848 return last; 1849 } 1850 1851 void init(const SkPoint pts[], SkPath::Verb verb) { 1852 fPts = pts; 1853 fVerb = verb; 1854 fDoneSpans = 0; 1855 } 1856 1857 bool intersected() const { 1858 return fTs.count() > 0; 1859 } 1860 1861 bool isConnected(int startIndex, int endIndex) const { 1862 return fTs[startIndex].fWindSum != SK_MinS32 1863 || fTs[endIndex].fWindSum != SK_MinS32; 1864 } 1865 1866 bool isLinear(int start, int end) const { 1867 if (fVerb == SkPath::kLine_Verb) { 1868 return true; 1869 } 1870 if (fVerb == SkPath::kQuad_Verb) { 1871 SkPoint qPart[3]; 1872 QuadSubDivide(fPts, fTs[start].fT, fTs[end].fT, qPart); 1873 return QuadIsLinear(qPart); 1874 } else { 1875 SkASSERT(fVerb == SkPath::kCubic_Verb); 1876 SkPoint cPart[4]; 1877 CubicSubDivide(fPts, fTs[start].fT, fTs[end].fT, cPart); 1878 return CubicIsLinear(cPart); 1879 } 1880 } 1881 1882 // OPTIMIZE: successive calls could start were the last leaves off 1883 // or calls could specialize to walk forwards or backwards 1884 bool isMissing(double startT) const { 1885 size_t tCount = fTs.count(); 1886 for (size_t index = 0; index < tCount; ++index) { 1887 if (fabs(startT - fTs[index].fT) < FLT_EPSILON) { 1888 return false; 1889 } 1890 } 1891 return true; 1892 } 1893 1894 bool isSimple(int end) const { 1895 int count = fTs.count(); 1896 if (count == 2) { 1897 return true; 1898 } 1899 double t = fTs[end].fT; 1900 if (t < FLT_EPSILON) { 1901 return fTs[1].fT >= FLT_EPSILON; 1902 } 1903 if (t > 1 - FLT_EPSILON) { 1904 return fTs[count - 2].fT <= 1 - FLT_EPSILON; 1905 } 1906 return false; 1907 } 1908 1909 bool isHorizontal() const { 1910 return fBounds.fTop == fBounds.fBottom; 1911 } 1912 1913 bool isVertical() const { 1914 return fBounds.fLeft == fBounds.fRight; 1915 } 1916 1917 SkScalar leftMost(int start, int end) const { 1918 return (*SegmentLeftMost[fVerb])(fPts, fTs[start].fT, fTs[end].fT); 1919 } 1920 1921 // this span is excluded by the winding rule -- chase the ends 1922 // as long as they are unambiguous to mark connections as done 1923 // and give them the same winding value 1924 Span* markAndChaseDone(const Angle* angle, int winding) { 1925 int index = angle->start(); 1926 int endIndex = angle->end(); 1927 int step = SkSign32(endIndex - index); 1928 Span* last = innerChaseDone(index, step, winding); 1929 markDone(SkMin32(index, endIndex), winding); 1930 return last; 1931 } 1932 1933 Span* markAndChaseWinding(const Angle* angle, int winding) { 1934 int index = angle->start(); 1935 int endIndex = angle->end(); 1936 int min = SkMin32(index, endIndex); 1937 int step = SkSign32(endIndex - index); 1938 Span* last = innerChaseWinding(index, step, winding); 1939 markWinding(min, winding); 1940 return last; 1941 } 1942 1943 // FIXME: this should also mark spans with equal (x,y) 1944 // This may be called when the segment is already marked done. While this 1945 // wastes time, it shouldn't do any more than spin through the T spans. 1946 // OPTIMIZATION: abort on first done found (assuming that this code is 1947 // always called to mark segments done). 1948 void markDone(int index, int winding) { 1949 // SkASSERT(!done()); 1950 double referenceT = fTs[index].fT; 1951 int lesser = index; 1952 while (--lesser >= 0 && referenceT - fTs[lesser].fT < FLT_EPSILON) { 1953 Span& span = fTs[lesser]; 1954 if (span.fDone) { 1955 continue; 1956 } 1957 #if DEBUG_MARK_DONE 1958 debugShowNewWinding(__FUNCTION__, span, winding); 1959 #endif 1960 span.fDone = true; 1961 SkASSERT(span.fWindSum == SK_MinS32 || span.fWindSum == winding); 1962 SkASSERT(abs(winding) <= gDebugMaxWindSum); 1963 span.fWindSum = winding; 1964 fDoneSpans++; 1965 } 1966 do { 1967 Span& span = fTs[index]; 1968 // SkASSERT(!span.fDone); 1969 if (span.fDone) { 1970 continue; 1971 } 1972 #if DEBUG_MARK_DONE 1973 debugShowNewWinding(__FUNCTION__, span, winding); 1974 #endif 1975 span.fDone = true; 1976 SkASSERT(span.fWindSum == SK_MinS32 || span.fWindSum == winding); 1977 SkASSERT(abs(winding) <= gDebugMaxWindSum); 1978 span.fWindSum = winding; 1979 fDoneSpans++; 1980 } while (++index < fTs.count() && fTs[index].fT - referenceT < FLT_EPSILON); 1981 } 1982 1983 void markWinding(int index, int winding) { 1984 // SkASSERT(!done()); 1985 double referenceT = fTs[index].fT; 1986 int lesser = index; 1987 while (--lesser >= 0 && referenceT - fTs[lesser].fT < FLT_EPSILON) { 1988 Span& span = fTs[lesser]; 1989 if (span.fDone) { 1990 continue; 1991 } 1992 // SkASSERT(span.fWindValue == 1 || winding == 0); 1993 #if DEBUG_MARK_DONE 1994 debugShowNewWinding(__FUNCTION__, span, winding); 1995 #endif 1996 SkASSERT(span.fWindSum == SK_MinS32 || span.fWindSum == winding); 1997 SkASSERT(abs(winding) <= gDebugMaxWindSum); 1998 span.fWindSum = winding; 1999 } 2000 do { 2001 Span& span = fTs[index]; 2002 // SkASSERT(!span.fDone || span.fCoincident); 2003 if (span.fDone) { 2004 continue; 2005 } 2006 // SkASSERT(span.fWindValue == 1 || winding == 0); 2007 SkASSERT(span.fWindSum == SK_MinS32 || span.fWindSum == winding); 2008 #if DEBUG_MARK_DONE 2009 debugShowNewWinding(__FUNCTION__, span, winding); 2010 #endif 2011 SkASSERT(abs(winding) <= gDebugMaxWindSum); 2012 span.fWindSum = winding; 2013 } while (++index < fTs.count() && fTs[index].fT - referenceT < FLT_EPSILON); 2014 } 2015 2016 void matchWindingValue(int tIndex, double t, bool borrowWind) { 2017 int nextDoorWind = SK_MaxS32; 2018 if (tIndex > 0) { 2019 const Span& below = fTs[tIndex - 1]; 2020 if (t - below.fT < FLT_EPSILON) { 2021 nextDoorWind = below.fWindValue; 2022 } 2023 } 2024 if (nextDoorWind == SK_MaxS32 && tIndex + 1 < fTs.count()) { 2025 const Span& above = fTs[tIndex + 1]; 2026 if (above.fT - t < FLT_EPSILON) { 2027 nextDoorWind = above.fWindValue; 2028 } 2029 } 2030 if (nextDoorWind == SK_MaxS32 && borrowWind && tIndex > 0 && t < 1) { 2031 const Span& below = fTs[tIndex - 1]; 2032 nextDoorWind = below.fWindValue; 2033 } 2034 if (nextDoorWind != SK_MaxS32) { 2035 Span& newSpan = fTs[tIndex]; 2036 newSpan.fWindValue = nextDoorWind; 2037 if (!nextDoorWind) { 2038 newSpan.fDone = true; 2039 ++fDoneSpans; 2040 } 2041 } 2042 } 2043 2044 // return span if when chasing, two or more radiating spans are not done 2045 // OPTIMIZATION: ? multiple spans is detected when there is only one valid 2046 // candidate and the remaining spans have windValue == 0 (canceled by 2047 // coincidence). The coincident edges could either be removed altogether, 2048 // or this code could be more complicated in detecting this case. Worth it? 2049 bool multipleSpans(int end) const { 2050 return end > 0 && end < fTs.count() - 1; 2051 } 2052 2053 // This has callers for two different situations: one establishes the end 2054 // of the current span, and one establishes the beginning of the next span 2055 // (thus the name). When this is looking for the end of the current span, 2056 // coincidence is found when the beginning Ts contain -step and the end 2057 // contains step. When it is looking for the beginning of the next, the 2058 // first Ts found can be ignored and the last Ts should contain -step. 2059 // OPTIMIZATION: probably should split into two functions 2060 int nextSpan(int from, int step) const { 2061 const Span& fromSpan = fTs[from]; 2062 int count = fTs.count(); 2063 int to = from; 2064 while (step > 0 ? ++to < count : --to >= 0) { 2065 const Span& span = fTs[to]; 2066 if ((step > 0 ? span.fT - fromSpan.fT : fromSpan.fT - span.fT) < FLT_EPSILON) { 2067 continue; 2068 } 2069 return to; 2070 } 2071 return -1; 2072 } 2073 2074 const SkPoint* pts() const { 2075 return fPts; 2076 } 2077 2078 void reset() { 2079 init(NULL, (SkPath::Verb) -1); 2080 fBounds.set(SK_ScalarMax, SK_ScalarMax, SK_ScalarMax, SK_ScalarMax); 2081 fTs.reset(); 2082 } 2083 2084 // OPTIMIZATION: mark as debugging only if used solely by tests 2085 const Span& span(int tIndex) const { 2086 return fTs[tIndex]; 2087 } 2088 2089 int spanSign(int startIndex, int endIndex) const { 2090 int result = startIndex < endIndex ? -fTs[startIndex].fWindValue : 2091 fTs[endIndex].fWindValue; 2092#if DEBUG_WIND_BUMP 2093 SkDebugf("%s spanSign=%d\n", __FUNCTION__, result); 2094#endif 2095 return result; 2096 } 2097 2098 int spanSign(const Angle* angle) const { 2099 SkASSERT(angle->segment() == this); 2100 return spanSign(angle->start(), angle->end()); 2101 } 2102 2103 // OPTIMIZATION: mark as debugging only if used solely by tests 2104 double t(int tIndex) const { 2105 return fTs[tIndex].fT; 2106 } 2107 2108 static void TrackOutside(SkTDArray<double>& outsideTs, double end, 2109 double start) { 2110 int outCount = outsideTs.count(); 2111 if (outCount == 0 || end - outsideTs[outCount - 2] >= FLT_EPSILON) { 2112 *outsideTs.append() = end; 2113 *outsideTs.append() = start; 2114 } 2115 } 2116 2117 void updatePts(const SkPoint pts[]) { 2118 fPts = pts; 2119 } 2120 2121 SkPath::Verb verb() const { 2122 return fVerb; 2123 } 2124 2125 int windSum(int tIndex) const { 2126 return fTs[tIndex].fWindSum; 2127 } 2128 2129 int windSum(const Angle* angle) const { 2130 int start = angle->start(); 2131 int end = angle->end(); 2132 int index = SkMin32(start, end); 2133 return windSum(index); 2134 } 2135 2136 int windValue(int tIndex) const { 2137 return fTs[tIndex].fWindValue; 2138 } 2139 2140 int windValue(const Angle* angle) const { 2141 int start = angle->start(); 2142 int end = angle->end(); 2143 int index = SkMin32(start, end); 2144 return windValue(index); 2145 } 2146 2147 SkScalar xAtT(const Span* span) const { 2148 return xyAtT(span).fX; 2149 } 2150 2151 const SkPoint& xyAtT(int index) const { 2152 return xyAtT(&fTs[index]); 2153 } 2154 2155 const SkPoint& xyAtT(const Span* span) const { 2156 if (SkScalarIsNaN(span->fPt.fX)) { 2157 if (span->fT == 0) { 2158 span->fPt = fPts[0]; 2159 } else if (span->fT == 1) { 2160 span->fPt = fPts[fVerb]; 2161 } else { 2162 (*SegmentXYAtT[fVerb])(fPts, span->fT, &span->fPt); 2163 } 2164 } 2165 return span->fPt; 2166 } 2167 2168 SkScalar yAtT(int index) const { 2169 return yAtT(&fTs[index]); 2170 } 2171 2172 SkScalar yAtT(const Span* span) const { 2173 return xyAtT(span).fY; 2174 } 2175 2176#if DEBUG_DUMP 2177 void dump() const { 2178 const char className[] = "Segment"; 2179 const int tab = 4; 2180 for (int i = 0; i < fTs.count(); ++i) { 2181 SkPoint out; 2182 (*SegmentXYAtT[fVerb])(fPts, t(i), &out); 2183 SkDebugf("%*s [%d] %s.fTs[%d]=%1.9g (%1.9g,%1.9g) other=%d" 2184 " otherT=%1.9g windSum=%d\n", 2185 tab + sizeof(className), className, fID, 2186 kLVerbStr[fVerb], i, fTs[i].fT, out.fX, out.fY, 2187 fTs[i].fOther->fID, fTs[i].fOtherT, fTs[i].fWindSum); 2188 } 2189 SkDebugf("%*s [%d] fBounds=(l:%1.9g, t:%1.9g r:%1.9g, b:%1.9g)", 2190 tab + sizeof(className), className, fID, 2191 fBounds.fLeft, fBounds.fTop, fBounds.fRight, fBounds.fBottom); 2192 } 2193#endif 2194 2195#if DEBUG_CONCIDENT 2196 // assert if pair has not already been added 2197 void debugAddTPair(double t, const Segment& other, double otherT) const { 2198 for (int i = 0; i < fTs.count(); ++i) { 2199 if (fTs[i].fT == t && fTs[i].fOther == &other && fTs[i].fOtherT == otherT) { 2200 return; 2201 } 2202 } 2203 SkASSERT(0); 2204 } 2205#endif 2206 2207#if DEBUG_DUMP 2208 int debugID() const { 2209 return fID; 2210 } 2211#endif 2212 2213#if DEBUG_CONCIDENT 2214 void debugShowTs() const { 2215 SkDebugf("%s %d", __FUNCTION__, fID); 2216 for (int i = 0; i < fTs.count(); ++i) { 2217 SkDebugf(" [o=%d t=%1.3g %1.9g,%1.9g w=%d]", fTs[i].fOther->fID, 2218 fTs[i].fT, xAtT(&fTs[i]), yAtT(&fTs[i]), fTs[i].fWindValue); 2219 } 2220 SkDebugf("\n"); 2221 } 2222#endif 2223 2224#if DEBUG_ACTIVE_SPANS 2225 void debugShowActiveSpans() const { 2226 if (done()) { 2227 return; 2228 } 2229 for (int i = 0; i < fTs.count(); ++i) { 2230 if (fTs[i].fDone) { 2231 continue; 2232 } 2233 SkDebugf("%s id=%d", __FUNCTION__, fID); 2234 SkDebugf(" (%1.9g,%1.9g", fPts[0].fX, fPts[0].fY); 2235 for (int vIndex = 1; vIndex <= fVerb; ++vIndex) { 2236 SkDebugf(" %1.9g,%1.9g", fPts[vIndex].fX, fPts[vIndex].fY); 2237 } 2238 const Span* span = &fTs[i]; 2239 SkDebugf(") t=%1.9g (%1.9g,%1.9g)", fTs[i].fT, 2240 xAtT(span), yAtT(span)); 2241 const Segment* other = fTs[i].fOther; 2242 SkDebugf(" other=%d otherT=%1.9g otherIndex=%d windSum=", 2243 other->fID, fTs[i].fOtherT, fTs[i].fOtherIndex); 2244 if (fTs[i].fWindSum == SK_MinS32) { 2245 SkDebugf("?"); 2246 } else { 2247 SkDebugf("%d", fTs[i].fWindSum); 2248 } 2249 SkDebugf(" windValue=%d\n", fTs[i].fWindValue); 2250 } 2251 } 2252#endif 2253 2254#if DEBUG_MARK_DONE 2255 void debugShowNewWinding(const char* fun, const Span& span, int winding) { 2256 const SkPoint& pt = xyAtT(&span); 2257 SkDebugf("%s id=%d", fun, fID); 2258 SkDebugf(" (%1.9g,%1.9g", fPts[0].fX, fPts[0].fY); 2259 for (int vIndex = 1; vIndex <= fVerb; ++vIndex) { 2260 SkDebugf(" %1.9g,%1.9g", fPts[vIndex].fX, fPts[vIndex].fY); 2261 } 2262 SkDebugf(") t=%1.9g (%1.9g,%1.9g) newWindSum=%d windSum=", 2263 span.fT, pt.fX, pt.fY, winding); 2264 if (span.fWindSum == SK_MinS32) { 2265 SkDebugf("?"); 2266 } else { 2267 SkDebugf("%d", span.fWindSum); 2268 } 2269 SkDebugf(" windValue=%d\n", span.fWindValue); 2270 } 2271#endif 2272 2273#if DEBUG_SORT 2274 void debugShowSort(const SkTDArray<Angle*>& angles, int first, 2275 const int contourWinding) const { 2276 SkASSERT(angles[first]->segment() == this); 2277 SkASSERT(angles.count() > 1); 2278 int lastSum = contourWinding; 2279 int windSum = lastSum - spanSign(angles[first]); 2280 SkDebugf("%s contourWinding=%d bump=%d\n", __FUNCTION__, 2281 contourWinding, spanSign(angles[first])); 2282 int index = first; 2283 bool firstTime = true; 2284 do { 2285 const Angle& angle = *angles[index]; 2286 const Segment& segment = *angle.segment(); 2287 int start = angle.start(); 2288 int end = angle.end(); 2289 const Span& sSpan = segment.fTs[start]; 2290 const Span& eSpan = segment.fTs[end]; 2291 const Span& mSpan = segment.fTs[SkMin32(start, end)]; 2292 if (!firstTime) { 2293 lastSum = windSum; 2294 windSum -= segment.spanSign(&angle); 2295 } 2296 SkDebugf("%s [%d] id=%d start=%d (%1.9g,%,1.9g) end=%d (%1.9g,%,1.9g)" 2297 " sign=%d windValue=%d winding: %d->%d (max=%d) done=%d\n", 2298 __FUNCTION__, index, segment.fID, start, segment.xAtT(&sSpan), 2299 segment.yAtT(&sSpan), end, segment.xAtT(&eSpan), 2300 segment.yAtT(&eSpan), angle.sign(), mSpan.fWindValue, 2301 lastSum, windSum, useInnerWinding(lastSum, windSum) 2302 ? windSum : lastSum, mSpan.fDone); 2303 ++index; 2304 if (index == angles.count()) { 2305 index = 0; 2306 } 2307 if (firstTime) { 2308 firstTime = false; 2309 } 2310 } while (index != first); 2311 } 2312#endif 2313 2314#if DEBUG_WINDING 2315 bool debugVerifyWinding(int start, int end, int winding) const { 2316 const Span& span = fTs[SkMin32(start, end)]; 2317 int spanWinding = span.fWindSum; 2318 if (spanWinding == SK_MinS32) { 2319 return true; 2320 } 2321 int spanSign = SkSign32(start - end); 2322 int signedVal = spanSign * span.fWindValue; 2323 if (signedVal < 0) { 2324 spanWinding -= signedVal; 2325 } 2326 return span.fWindSum == winding; 2327 } 2328#endif 2329 2330private: 2331 const SkPoint* fPts; 2332 SkPath::Verb fVerb; 2333 Bounds fBounds; 2334 SkTDArray<Span> fTs; // two or more (always includes t=0 t=1) 2335 int fDoneSpans; // used for quick check that segment is finished 2336#if DEBUG_DUMP 2337 int fID; 2338#endif 2339}; 2340 2341class Contour; 2342 2343struct Coincidence { 2344 Contour* fContours[2]; 2345 int fSegments[2]; 2346 double fTs[2][2]; 2347}; 2348 2349class Contour { 2350public: 2351 Contour() { 2352 reset(); 2353#if DEBUG_DUMP 2354 fID = ++gContourID; 2355#endif 2356 } 2357 2358 bool operator<(const Contour& rh) const { 2359 return fBounds.fTop == rh.fBounds.fTop 2360 ? fBounds.fLeft < rh.fBounds.fLeft 2361 : fBounds.fTop < rh.fBounds.fTop; 2362 } 2363 2364 void addCoincident(int index, Contour* other, int otherIndex, 2365 const Intersections& ts, bool swap) { 2366 Coincidence& coincidence = *fCoincidences.append(); 2367 coincidence.fContours[0] = this; 2368 coincidence.fContours[1] = other; 2369 coincidence.fSegments[0] = index; 2370 coincidence.fSegments[1] = otherIndex; 2371 coincidence.fTs[swap][0] = ts.fT[0][0]; 2372 coincidence.fTs[swap][1] = ts.fT[0][1]; 2373 coincidence.fTs[!swap][0] = ts.fT[1][0]; 2374 coincidence.fTs[!swap][1] = ts.fT[1][1]; 2375 } 2376 2377 void addCross(const Contour* crosser) { 2378#ifdef DEBUG_CROSS 2379 for (int index = 0; index < fCrosses.count(); ++index) { 2380 SkASSERT(fCrosses[index] != crosser); 2381 } 2382#endif 2383 *fCrosses.append() = crosser; 2384 } 2385 2386 void addCubic(const SkPoint pts[4]) { 2387 fSegments.push_back().addCubic(pts); 2388 fContainsCurves = true; 2389 } 2390 2391 int addLine(const SkPoint pts[2]) { 2392 fSegments.push_back().addLine(pts); 2393 return fSegments.count(); 2394 } 2395 2396 void addOtherT(int segIndex, int tIndex, double otherT, int otherIndex) { 2397 fSegments[segIndex].addOtherT(tIndex, otherT, otherIndex); 2398 } 2399 2400 int addQuad(const SkPoint pts[3]) { 2401 fSegments.push_back().addQuad(pts); 2402 fContainsCurves = true; 2403 return fSegments.count(); 2404 } 2405 2406 int addT(int segIndex, double newT, Contour* other, int otherIndex) { 2407 containsIntercepts(); 2408 return fSegments[segIndex].addT(newT, &other->fSegments[otherIndex]); 2409 } 2410 2411 const Bounds& bounds() const { 2412 return fBounds; 2413 } 2414 2415 void complete() { 2416 setBounds(); 2417 fContainsIntercepts = false; 2418 } 2419 2420 void containsIntercepts() { 2421 fContainsIntercepts = true; 2422 } 2423 2424 const Segment* crossedSegment(const SkPoint& basePt, SkScalar& bestY, 2425 int &tIndex, double& hitT) { 2426 int segmentCount = fSegments.count(); 2427 const Segment* bestSegment = NULL; 2428 for (int test = 0; test < segmentCount; ++test) { 2429 Segment* testSegment = &fSegments[test]; 2430 const SkRect& bounds = testSegment->bounds(); 2431 if (bounds.fBottom <= bestY) { 2432 continue; 2433 } 2434 if (bounds.fTop >= basePt.fY) { 2435 continue; 2436 } 2437 if (bounds.fLeft > basePt.fX) { 2438 continue; 2439 } 2440 if (bounds.fRight < basePt.fX) { 2441 continue; 2442 } 2443 if (bounds.fLeft == bounds.fRight) { 2444 continue; 2445 } 2446 #if 0 2447 bool leftHalf = bounds.fLeft == basePt.fX; 2448 bool rightHalf = bounds.fRight == basePt.fX; 2449 if ((leftHalf || rightHalf) && !testSegment->crossedSpanHalves( 2450 basePt, leftHalf, rightHalf)) { 2451 continue; 2452 } 2453 #endif 2454 double testHitT; 2455 int testT = testSegment->crossedSpan(basePt, bestY, testHitT); 2456 if (testT >= 0) { 2457 bestSegment = testSegment; 2458 tIndex = testT; 2459 hitT = testHitT; 2460 } 2461 } 2462 return bestSegment; 2463 } 2464 2465 bool crosses(const Contour* crosser) const { 2466 for (int index = 0; index < fCrosses.count(); ++index) { 2467 if (fCrosses[index] == crosser) { 2468 return true; 2469 } 2470 } 2471 return false; 2472 } 2473 2474 void findTooCloseToCall(int winding) { 2475 int segmentCount = fSegments.count(); 2476 for (int sIndex = 0; sIndex < segmentCount; ++sIndex) { 2477 fSegments[sIndex].findTooCloseToCall(winding); 2478 } 2479 } 2480 2481 void fixOtherTIndex() { 2482 int segmentCount = fSegments.count(); 2483 for (int sIndex = 0; sIndex < segmentCount; ++sIndex) { 2484 fSegments[sIndex].fixOtherTIndex(); 2485 } 2486 } 2487 2488 void reset() { 2489 fSegments.reset(); 2490 fBounds.set(SK_ScalarMax, SK_ScalarMax, SK_ScalarMax, SK_ScalarMax); 2491 fContainsCurves = fContainsIntercepts = false; 2492 } 2493 2494 void resolveCoincidence(int winding) { 2495 int count = fCoincidences.count(); 2496 for (int index = 0; index < count; ++index) { 2497 Coincidence& coincidence = fCoincidences[index]; 2498 Contour* thisContour = coincidence.fContours[0]; 2499 Contour* otherContour = coincidence.fContours[1]; 2500 int thisIndex = coincidence.fSegments[0]; 2501 int otherIndex = coincidence.fSegments[1]; 2502 Segment& thisOne = thisContour->fSegments[thisIndex]; 2503 Segment& other = otherContour->fSegments[otherIndex]; 2504 #if DEBUG_CONCIDENT 2505 thisOne.debugShowTs(); 2506 other.debugShowTs(); 2507 #endif 2508 double startT = coincidence.fTs[0][0]; 2509 double endT = coincidence.fTs[0][1]; 2510 if (startT > endT) { 2511 SkTSwap<double>(startT, endT); 2512 } 2513 SkASSERT(endT - startT >= FLT_EPSILON); 2514 double oStartT = coincidence.fTs[1][0]; 2515 double oEndT = coincidence.fTs[1][1]; 2516 if (oStartT > oEndT) { 2517 SkTSwap<double>(oStartT, oEndT); 2518 } 2519 SkASSERT(oEndT - oStartT >= FLT_EPSILON); 2520 if (winding > 0 || thisOne.cancels(other)) { 2521 // make sure startT and endT have t entries 2522 if (startT > 0 || oEndT < 1 2523 || thisOne.isMissing(startT) || other.isMissing(oEndT)) { 2524 thisOne.addTPair(startT, other, oEndT, true); 2525 } 2526 if (oStartT > 0 || endT < 1 2527 || thisOne.isMissing(endT) || other.isMissing(oStartT)) { 2528 other.addTPair(oStartT, thisOne, endT, true); 2529 } 2530 thisOne.addTCancel(startT, endT, other, oStartT, oEndT); 2531 } else { 2532 if (startT > 0 || oStartT > 0 2533 || thisOne.isMissing(startT) || other.isMissing(oStartT)) { 2534 thisOne.addTPair(startT, other, oStartT, true); 2535 } 2536 if (endT < 1 || oEndT < 1 2537 || thisOne.isMissing(endT) || other.isMissing(oEndT)) { 2538 other.addTPair(oEndT, thisOne, endT, true); 2539 } 2540 thisOne.addTCoincident(startT, endT, other, oStartT, oEndT); 2541 } 2542 #if DEBUG_CONCIDENT 2543 thisOne.debugShowTs(); 2544 other.debugShowTs(); 2545 #endif 2546 } 2547 } 2548 2549 const SkTArray<Segment>& segments() { 2550 return fSegments; 2551 } 2552 2553 // OPTIMIZATION: feel pretty uneasy about this. It seems like once again 2554 // we need to sort and walk edges in y, but that on the surface opens the 2555 // same can of worms as before. But then, this is a rough sort based on 2556 // segments' top, and not a true sort, so it could be ameniable to regular 2557 // sorting instead of linear searching. Still feel like I'm missing something 2558 Segment* topSegment(SkScalar& bestY) { 2559 int segmentCount = fSegments.count(); 2560 SkASSERT(segmentCount > 0); 2561 int best = -1; 2562 Segment* bestSegment = NULL; 2563 while (++best < segmentCount) { 2564 Segment* testSegment = &fSegments[best]; 2565 if (testSegment->done()) { 2566 continue; 2567 } 2568 bestSegment = testSegment; 2569 break; 2570 } 2571 if (!bestSegment) { 2572 return NULL; 2573 } 2574 SkScalar bestTop = bestSegment->activeTop(); 2575 for (int test = best + 1; test < segmentCount; ++test) { 2576 Segment* testSegment = &fSegments[test]; 2577 if (testSegment->done()) { 2578 continue; 2579 } 2580 if (testSegment->bounds().fTop > bestTop) { 2581 continue; 2582 } 2583 SkScalar testTop = testSegment->activeTop(); 2584 if (bestTop > testTop) { 2585 bestTop = testTop; 2586 bestSegment = testSegment; 2587 } 2588 } 2589 bestY = bestTop; 2590 return bestSegment; 2591 } 2592 2593 int updateSegment(int index, const SkPoint* pts) { 2594 Segment& segment = fSegments[index]; 2595 segment.updatePts(pts); 2596 return segment.verb() + 1; 2597 } 2598 2599#if DEBUG_TEST 2600 SkTArray<Segment>& debugSegments() { 2601 return fSegments; 2602 } 2603#endif 2604 2605#if DEBUG_DUMP 2606 void dump() { 2607 int i; 2608 const char className[] = "Contour"; 2609 const int tab = 4; 2610 SkDebugf("%s %p (contour=%d)\n", className, this, fID); 2611 for (i = 0; i < fSegments.count(); ++i) { 2612 SkDebugf("%*s.fSegments[%d]:\n", tab + sizeof(className), 2613 className, i); 2614 fSegments[i].dump(); 2615 } 2616 SkDebugf("%*s.fBounds=(l:%1.9g, t:%1.9g r:%1.9g, b:%1.9g)\n", 2617 tab + sizeof(className), className, 2618 fBounds.fLeft, fBounds.fTop, 2619 fBounds.fRight, fBounds.fBottom); 2620 SkDebugf("%*s.fContainsIntercepts=%d\n", tab + sizeof(className), 2621 className, fContainsIntercepts); 2622 SkDebugf("%*s.fContainsCurves=%d\n", tab + sizeof(className), 2623 className, fContainsCurves); 2624 } 2625#endif 2626 2627#if DEBUG_ACTIVE_SPANS 2628 void debugShowActiveSpans() { 2629 for (int index = 0; index < fSegments.count(); ++index) { 2630 fSegments[index].debugShowActiveSpans(); 2631 } 2632 } 2633#endif 2634 2635protected: 2636 void setBounds() { 2637 int count = fSegments.count(); 2638 if (count == 0) { 2639 SkDebugf("%s empty contour\n", __FUNCTION__); 2640 SkASSERT(0); 2641 // FIXME: delete empty contour? 2642 return; 2643 } 2644 fBounds = fSegments.front().bounds(); 2645 for (int index = 1; index < count; ++index) { 2646 fBounds.add(fSegments[index].bounds()); 2647 } 2648 } 2649 2650private: 2651 SkTArray<Segment> fSegments; 2652 SkTDArray<Coincidence> fCoincidences; 2653 SkTDArray<const Contour*> fCrosses; 2654 Bounds fBounds; 2655 bool fContainsIntercepts; 2656 bool fContainsCurves; 2657#if DEBUG_DUMP 2658 int fID; 2659#endif 2660}; 2661 2662class EdgeBuilder { 2663public: 2664 2665EdgeBuilder(const SkPath& path, SkTArray<Contour>& contours) 2666 : fPath(path) 2667 , fCurrentContour(NULL) 2668 , fContours(contours) 2669{ 2670#if DEBUG_DUMP 2671 gContourID = 0; 2672 gSegmentID = 0; 2673#endif 2674 walk(); 2675} 2676 2677protected: 2678 2679void complete() { 2680 if (fCurrentContour && fCurrentContour->segments().count()) { 2681 fCurrentContour->complete(); 2682 fCurrentContour = NULL; 2683 } 2684} 2685 2686void walk() { 2687 // FIXME:remove once we can access path pts directly 2688 SkPath::RawIter iter(fPath); // FIXME: access path directly when allowed 2689 SkPoint pts[4]; 2690 SkPath::Verb verb; 2691 do { 2692 verb = iter.next(pts); 2693 *fPathVerbs.append() = verb; 2694 if (verb == SkPath::kMove_Verb) { 2695 *fPathPts.append() = pts[0]; 2696 } else if (verb >= SkPath::kLine_Verb && verb <= SkPath::kCubic_Verb) { 2697 fPathPts.append(verb, &pts[1]); 2698 } 2699 } while (verb != SkPath::kDone_Verb); 2700 // FIXME: end of section to remove once path pts are accessed directly 2701 2702 SkPath::Verb reducedVerb; 2703 uint8_t* verbPtr = fPathVerbs.begin(); 2704 const SkPoint* pointsPtr = fPathPts.begin(); 2705 const SkPoint* finalCurveStart = NULL; 2706 const SkPoint* finalCurveEnd = NULL; 2707 while ((verb = (SkPath::Verb) *verbPtr++) != SkPath::kDone_Verb) { 2708 switch (verb) { 2709 case SkPath::kMove_Verb: 2710 complete(); 2711 if (!fCurrentContour) { 2712 fCurrentContour = fContours.push_back_n(1); 2713 *fExtra.append() = -1; // start new contour 2714 } 2715 finalCurveEnd = pointsPtr++; 2716 continue; 2717 case SkPath::kLine_Verb: 2718 // skip degenerate points 2719 if (pointsPtr[-1].fX != pointsPtr[0].fX 2720 || pointsPtr[-1].fY != pointsPtr[0].fY) { 2721 fCurrentContour->addLine(&pointsPtr[-1]); 2722 } 2723 break; 2724 case SkPath::kQuad_Verb: 2725 2726 reducedVerb = QuadReduceOrder(&pointsPtr[-1], fReducePts); 2727 if (reducedVerb == 0) { 2728 break; // skip degenerate points 2729 } 2730 if (reducedVerb == 1) { 2731 *fExtra.append() = 2732 fCurrentContour->addLine(fReducePts.end() - 2); 2733 break; 2734 } 2735 fCurrentContour->addQuad(&pointsPtr[-1]); 2736 break; 2737 case SkPath::kCubic_Verb: 2738 reducedVerb = CubicReduceOrder(&pointsPtr[-1], fReducePts); 2739 if (reducedVerb == 0) { 2740 break; // skip degenerate points 2741 } 2742 if (reducedVerb == 1) { 2743 *fExtra.append() = 2744 fCurrentContour->addLine(fReducePts.end() - 2); 2745 break; 2746 } 2747 if (reducedVerb == 2) { 2748 *fExtra.append() = 2749 fCurrentContour->addQuad(fReducePts.end() - 3); 2750 break; 2751 } 2752 fCurrentContour->addCubic(&pointsPtr[-1]); 2753 break; 2754 case SkPath::kClose_Verb: 2755 SkASSERT(fCurrentContour); 2756 if (finalCurveStart && finalCurveEnd 2757 && *finalCurveStart != *finalCurveEnd) { 2758 *fReducePts.append() = *finalCurveStart; 2759 *fReducePts.append() = *finalCurveEnd; 2760 *fExtra.append() = 2761 fCurrentContour->addLine(fReducePts.end() - 2); 2762 } 2763 complete(); 2764 continue; 2765 default: 2766 SkDEBUGFAIL("bad verb"); 2767 return; 2768 } 2769 finalCurveStart = &pointsPtr[verb - 1]; 2770 pointsPtr += verb; 2771 SkASSERT(fCurrentContour); 2772 } 2773 complete(); 2774 if (fCurrentContour && !fCurrentContour->segments().count()) { 2775 fContours.pop_back(); 2776 } 2777 // correct pointers in contours since fReducePts may have moved as it grew 2778 int cIndex = 0; 2779 int extraCount = fExtra.count(); 2780 SkASSERT(extraCount == 0 || fExtra[0] == -1); 2781 int eIndex = 0; 2782 int rIndex = 0; 2783 while (++eIndex < extraCount) { 2784 int offset = fExtra[eIndex]; 2785 if (offset < 0) { 2786 ++cIndex; 2787 continue; 2788 } 2789 fCurrentContour = &fContours[cIndex]; 2790 rIndex += fCurrentContour->updateSegment(offset - 1, 2791 &fReducePts[rIndex]); 2792 } 2793 fExtra.reset(); // we're done with this 2794} 2795 2796private: 2797 const SkPath& fPath; 2798 SkTDArray<SkPoint> fPathPts; // FIXME: point directly to path pts instead 2799 SkTDArray<uint8_t> fPathVerbs; // FIXME: remove 2800 Contour* fCurrentContour; 2801 SkTArray<Contour>& fContours; 2802 SkTDArray<SkPoint> fReducePts; // segments created on the fly 2803 SkTDArray<int> fExtra; // -1 marks new contour, > 0 offsets into contour 2804}; 2805 2806class Work { 2807public: 2808 enum SegmentType { 2809 kHorizontalLine_Segment = -1, 2810 kVerticalLine_Segment = 0, 2811 kLine_Segment = SkPath::kLine_Verb, 2812 kQuad_Segment = SkPath::kQuad_Verb, 2813 kCubic_Segment = SkPath::kCubic_Verb, 2814 }; 2815 2816 void addCoincident(Work& other, const Intersections& ts, bool swap) { 2817 fContour->addCoincident(fIndex, other.fContour, other.fIndex, ts, swap); 2818 } 2819 2820 // FIXME: does it make sense to write otherIndex now if we're going to 2821 // fix it up later? 2822 void addOtherT(int index, double otherT, int otherIndex) { 2823 fContour->addOtherT(fIndex, index, otherT, otherIndex); 2824 } 2825 2826 // Avoid collapsing t values that are close to the same since 2827 // we walk ts to describe consecutive intersections. Since a pair of ts can 2828 // be nearly equal, any problems caused by this should be taken care 2829 // of later. 2830 // On the edge or out of range values are negative; add 2 to get end 2831 int addT(double newT, const Work& other) { 2832 return fContour->addT(fIndex, newT, other.fContour, other.fIndex); 2833 } 2834 2835 bool advance() { 2836 return ++fIndex < fLast; 2837 } 2838 2839 SkScalar bottom() const { 2840 return bounds().fBottom; 2841 } 2842 2843 const Bounds& bounds() const { 2844 return fContour->segments()[fIndex].bounds(); 2845 } 2846 2847 const SkPoint* cubic() const { 2848 return fCubic; 2849 } 2850 2851 void init(Contour* contour) { 2852 fContour = contour; 2853 fIndex = 0; 2854 fLast = contour->segments().count(); 2855 } 2856 2857 bool isAdjacent(const Work& next) { 2858 return fContour == next.fContour && fIndex + 1 == next.fIndex; 2859 } 2860 2861 bool isFirstLast(const Work& next) { 2862 return fContour == next.fContour && fIndex == 0 2863 && next.fIndex == fLast - 1; 2864 } 2865 2866 SkScalar left() const { 2867 return bounds().fLeft; 2868 } 2869 2870 void promoteToCubic() { 2871 fCubic[0] = pts()[0]; 2872 fCubic[2] = pts()[1]; 2873 fCubic[3] = pts()[2]; 2874 fCubic[1].fX = (fCubic[0].fX + fCubic[2].fX * 2) / 3; 2875 fCubic[1].fY = (fCubic[0].fY + fCubic[2].fY * 2) / 3; 2876 fCubic[2].fX = (fCubic[3].fX + fCubic[2].fX * 2) / 3; 2877 fCubic[2].fY = (fCubic[3].fY + fCubic[2].fY * 2) / 3; 2878 } 2879 2880 const SkPoint* pts() const { 2881 return fContour->segments()[fIndex].pts(); 2882 } 2883 2884 SkScalar right() const { 2885 return bounds().fRight; 2886 } 2887 2888 ptrdiff_t segmentIndex() const { 2889 return fIndex; 2890 } 2891 2892 SegmentType segmentType() const { 2893 const Segment& segment = fContour->segments()[fIndex]; 2894 SegmentType type = (SegmentType) segment.verb(); 2895 if (type != kLine_Segment) { 2896 return type; 2897 } 2898 if (segment.isHorizontal()) { 2899 return kHorizontalLine_Segment; 2900 } 2901 if (segment.isVertical()) { 2902 return kVerticalLine_Segment; 2903 } 2904 return kLine_Segment; 2905 } 2906 2907 bool startAfter(const Work& after) { 2908 fIndex = after.fIndex; 2909 return advance(); 2910 } 2911 2912 SkScalar top() const { 2913 return bounds().fTop; 2914 } 2915 2916 SkPath::Verb verb() const { 2917 return fContour->segments()[fIndex].verb(); 2918 } 2919 2920 SkScalar x() const { 2921 return bounds().fLeft; 2922 } 2923 2924 bool xFlipped() const { 2925 return x() != pts()[0].fX; 2926 } 2927 2928 SkScalar y() const { 2929 return bounds().fTop; 2930 } 2931 2932 bool yFlipped() const { 2933 return y() != pts()[0].fY; 2934 } 2935 2936protected: 2937 Contour* fContour; 2938 SkPoint fCubic[4]; 2939 int fIndex; 2940 int fLast; 2941}; 2942 2943#if DEBUG_ADD_INTERSECTING_TS 2944static void debugShowLineIntersection(int pts, const Work& wt, 2945 const Work& wn, const double wtTs[2], const double wnTs[2]) { 2946 if (!pts) { 2947 SkDebugf("%s no intersect (%1.9g,%1.9g %1.9g,%1.9g) (%1.9g,%1.9g %1.9g,%1.9g)\n", 2948 __FUNCTION__, wt.pts()[0].fX, wt.pts()[0].fY, 2949 wt.pts()[1].fX, wt.pts()[1].fY, wn.pts()[0].fX, wn.pts()[0].fY, 2950 wn.pts()[1].fX, wn.pts()[1].fY); 2951 return; 2952 } 2953 SkPoint wtOutPt, wnOutPt; 2954 LineXYAtT(wt.pts(), wtTs[0], &wtOutPt); 2955 LineXYAtT(wn.pts(), wnTs[0], &wnOutPt); 2956 SkDebugf("%s wtTs[0]=%g (%g,%g, %g,%g) (%g,%g)", 2957 __FUNCTION__, 2958 wtTs[0], wt.pts()[0].fX, wt.pts()[0].fY, 2959 wt.pts()[1].fX, wt.pts()[1].fY, wtOutPt.fX, wtOutPt.fY); 2960 if (pts == 2) { 2961 SkDebugf(" wtTs[1]=%g", wtTs[1]); 2962 } 2963 SkDebugf(" wnTs[0]=%g (%g,%g, %g,%g) (%g,%g)", 2964 wnTs[0], wn.pts()[0].fX, wn.pts()[0].fY, 2965 wn.pts()[1].fX, wn.pts()[1].fY, wnOutPt.fX, wnOutPt.fY); 2966 if (pts == 2) { 2967 SkDebugf(" wnTs[1]=%g", wnTs[1]); 2968 } 2969 SkDebugf("\n"); 2970} 2971#else 2972static void debugShowLineIntersection(int , const Work& , 2973 const Work& , const double [2], const double [2]) { 2974} 2975#endif 2976 2977static bool addIntersectTs(Contour* test, Contour* next) { 2978 2979 if (test != next) { 2980 if (test->bounds().fBottom < next->bounds().fTop) { 2981 return false; 2982 } 2983 if (!Bounds::Intersects(test->bounds(), next->bounds())) { 2984 return true; 2985 } 2986 } 2987 Work wt; 2988 wt.init(test); 2989 bool foundCommonContour = test == next; 2990 do { 2991 Work wn; 2992 wn.init(next); 2993 if (test == next && !wn.startAfter(wt)) { 2994 continue; 2995 } 2996 do { 2997 if (!Bounds::Intersects(wt.bounds(), wn.bounds())) { 2998 continue; 2999 } 3000 int pts; 3001 Intersections ts; 3002 bool swap = false; 3003 switch (wt.segmentType()) { 3004 case Work::kHorizontalLine_Segment: 3005 swap = true; 3006 switch (wn.segmentType()) { 3007 case Work::kHorizontalLine_Segment: 3008 case Work::kVerticalLine_Segment: 3009 case Work::kLine_Segment: { 3010 pts = HLineIntersect(wn.pts(), wt.left(), 3011 wt.right(), wt.y(), wt.xFlipped(), ts); 3012 debugShowLineIntersection(pts, wt, wn, 3013 ts.fT[1], ts.fT[0]); 3014 break; 3015 } 3016 case Work::kQuad_Segment: { 3017 pts = HQuadIntersect(wn.pts(), wt.left(), 3018 wt.right(), wt.y(), wt.xFlipped(), ts); 3019 break; 3020 } 3021 case Work::kCubic_Segment: { 3022 pts = HCubicIntersect(wn.pts(), wt.left(), 3023 wt.right(), wt.y(), wt.xFlipped(), ts); 3024 break; 3025 } 3026 default: 3027 SkASSERT(0); 3028 } 3029 break; 3030 case Work::kVerticalLine_Segment: 3031 swap = true; 3032 switch (wn.segmentType()) { 3033 case Work::kHorizontalLine_Segment: 3034 case Work::kVerticalLine_Segment: 3035 case Work::kLine_Segment: { 3036 pts = VLineIntersect(wn.pts(), wt.top(), 3037 wt.bottom(), wt.x(), wt.yFlipped(), ts); 3038 debugShowLineIntersection(pts, wt, wn, 3039 ts.fT[1], ts.fT[0]); 3040 break; 3041 } 3042 case Work::kQuad_Segment: { 3043 pts = VQuadIntersect(wn.pts(), wt.top(), 3044 wt.bottom(), wt.x(), wt.yFlipped(), ts); 3045 break; 3046 } 3047 case Work::kCubic_Segment: { 3048 pts = VCubicIntersect(wn.pts(), wt.top(), 3049 wt.bottom(), wt.x(), wt.yFlipped(), ts); 3050 break; 3051 } 3052 default: 3053 SkASSERT(0); 3054 } 3055 break; 3056 case Work::kLine_Segment: 3057 switch (wn.segmentType()) { 3058 case Work::kHorizontalLine_Segment: 3059 pts = HLineIntersect(wt.pts(), wn.left(), 3060 wn.right(), wn.y(), wn.xFlipped(), ts); 3061 debugShowLineIntersection(pts, wt, wn, 3062 ts.fT[1], ts.fT[0]); 3063 break; 3064 case Work::kVerticalLine_Segment: 3065 pts = VLineIntersect(wt.pts(), wn.top(), 3066 wn.bottom(), wn.x(), wn.yFlipped(), ts); 3067 debugShowLineIntersection(pts, wt, wn, 3068 ts.fT[1], ts.fT[0]); 3069 break; 3070 case Work::kLine_Segment: { 3071 pts = LineIntersect(wt.pts(), wn.pts(), ts); 3072 debugShowLineIntersection(pts, wt, wn, 3073 ts.fT[1], ts.fT[0]); 3074 break; 3075 } 3076 case Work::kQuad_Segment: { 3077 swap = true; 3078 pts = QuadLineIntersect(wn.pts(), wt.pts(), ts); 3079 break; 3080 } 3081 case Work::kCubic_Segment: { 3082 swap = true; 3083 pts = CubicLineIntersect(wn.pts(), wt.pts(), ts); 3084 break; 3085 } 3086 default: 3087 SkASSERT(0); 3088 } 3089 break; 3090 case Work::kQuad_Segment: 3091 switch (wn.segmentType()) { 3092 case Work::kHorizontalLine_Segment: 3093 pts = HQuadIntersect(wt.pts(), wn.left(), 3094 wn.right(), wn.y(), wn.xFlipped(), ts); 3095 break; 3096 case Work::kVerticalLine_Segment: 3097 pts = VQuadIntersect(wt.pts(), wn.top(), 3098 wn.bottom(), wn.x(), wn.yFlipped(), ts); 3099 break; 3100 case Work::kLine_Segment: { 3101 pts = QuadLineIntersect(wt.pts(), wn.pts(), ts); 3102 break; 3103 } 3104 case Work::kQuad_Segment: { 3105 pts = QuadIntersect(wt.pts(), wn.pts(), ts); 3106 break; 3107 } 3108 case Work::kCubic_Segment: { 3109 wt.promoteToCubic(); 3110 pts = CubicIntersect(wt.cubic(), wn.pts(), ts); 3111 break; 3112 } 3113 default: 3114 SkASSERT(0); 3115 } 3116 break; 3117 case Work::kCubic_Segment: 3118 switch (wn.segmentType()) { 3119 case Work::kHorizontalLine_Segment: 3120 pts = HCubicIntersect(wt.pts(), wn.left(), 3121 wn.right(), wn.y(), wn.xFlipped(), ts); 3122 break; 3123 case Work::kVerticalLine_Segment: 3124 pts = VCubicIntersect(wt.pts(), wn.top(), 3125 wn.bottom(), wn.x(), wn.yFlipped(), ts); 3126 break; 3127 case Work::kLine_Segment: { 3128 pts = CubicLineIntersect(wt.pts(), wn.pts(), ts); 3129 break; 3130 } 3131 case Work::kQuad_Segment: { 3132 wn.promoteToCubic(); 3133 pts = CubicIntersect(wt.pts(), wn.cubic(), ts); 3134 break; 3135 } 3136 case Work::kCubic_Segment: { 3137 pts = CubicIntersect(wt.pts(), wn.pts(), ts); 3138 break; 3139 } 3140 default: 3141 SkASSERT(0); 3142 } 3143 break; 3144 default: 3145 SkASSERT(0); 3146 } 3147 if (!foundCommonContour && pts > 0) { 3148 test->addCross(next); 3149 next->addCross(test); 3150 foundCommonContour = true; 3151 } 3152 // in addition to recording T values, record matching segment 3153 if (pts == 2 && wn.segmentType() <= Work::kLine_Segment 3154 && wt.segmentType() <= Work::kLine_Segment) { 3155 wt.addCoincident(wn, ts, swap); 3156 continue; 3157 } 3158 for (int pt = 0; pt < pts; ++pt) { 3159 SkASSERT(ts.fT[0][pt] >= 0 && ts.fT[0][pt] <= 1); 3160 SkASSERT(ts.fT[1][pt] >= 0 && ts.fT[1][pt] <= 1); 3161 int testTAt = wt.addT(ts.fT[swap][pt], wn); 3162 int nextTAt = wn.addT(ts.fT[!swap][pt], wt); 3163 wt.addOtherT(testTAt, ts.fT[!swap][pt], nextTAt); 3164 wn.addOtherT(nextTAt, ts.fT[swap][pt], testTAt); 3165 } 3166 } while (wn.advance()); 3167 } while (wt.advance()); 3168 return true; 3169} 3170 3171// resolve any coincident pairs found while intersecting, and 3172// see if coincidence is formed by clipping non-concident segments 3173static void coincidenceCheck(SkTDArray<Contour*>& contourList, int winding) { 3174 int contourCount = contourList.count(); 3175 for (int cIndex = 0; cIndex < contourCount; ++cIndex) { 3176 Contour* contour = contourList[cIndex]; 3177 contour->findTooCloseToCall(winding); 3178 } 3179 for (int cIndex = 0; cIndex < contourCount; ++cIndex) { 3180 Contour* contour = contourList[cIndex]; 3181 contour->resolveCoincidence(winding); 3182 } 3183} 3184 3185// project a ray from the top of the contour up and see if it hits anything 3186// note: when we compute line intersections, we keep track of whether 3187// two contours touch, so we need only look at contours not touching this one. 3188// OPTIMIZATION: sort contourList vertically to avoid linear walk 3189static int innerContourCheck(SkTDArray<Contour*>& contourList, 3190 const Segment* current, int index, int endIndex) { 3191 const SkPoint& basePt = current->xyAtT(endIndex); 3192 int contourCount = contourList.count(); 3193 SkScalar bestY = SK_ScalarMin; 3194 const Segment* test = NULL; 3195 int tIndex; 3196 double tHit; 3197 // bool checkCrosses = true; 3198 for (int cTest = 0; cTest < contourCount; ++cTest) { 3199 Contour* contour = contourList[cTest]; 3200 if (basePt.fY < contour->bounds().fTop) { 3201 continue; 3202 } 3203 if (bestY > contour->bounds().fBottom) { 3204 continue; 3205 } 3206#if 0 3207 // even though the contours crossed, if spans cancel through concidence, 3208 // the contours may be not have any span links to chase, and the current 3209 // segment may be isolated. Detect this by seeing if current has 3210 // uninitialized wind sums. If so, project a ray instead of relying on 3211 // previously found intersections. 3212 if (baseContour == contour) { 3213 continue; 3214 } 3215 if (checkCrosses && baseContour->crosses(contour)) { 3216 if (current->isConnected(index, endIndex)) { 3217 continue; 3218 } 3219 checkCrosses = false; 3220 } 3221#endif 3222 const Segment* next = contour->crossedSegment(basePt, bestY, tIndex, tHit); 3223 if (next) { 3224 test = next; 3225 } 3226 } 3227 if (!test) { 3228 return 0; 3229 } 3230 int winding, windValue; 3231 // If the ray hit the end of a span, we need to construct the wheel of 3232 // angles to find the span closest to the ray -- even if there are just 3233 // two spokes on the wheel. 3234 const Angle* angle = NULL; 3235 if (fabs(tHit - test->t(tIndex)) < FLT_EPSILON) { 3236 SkTDArray<Angle> angles; 3237 int end = test->nextSpan(tIndex, 1); 3238 if (end < 0) { 3239 end = test->nextSpan(tIndex, -1); 3240 } 3241 test->addTwoAngles(end, tIndex, angles); 3242 SkASSERT(angles.count() > 0); 3243 if (angles[0].segment()->yAtT(angles[0].start()) >= basePt.fY) { 3244#if DEBUG_SORT 3245 SkDebugf("%s *** early return\n", __FUNCTION__); 3246#endif 3247 return 0; 3248 } 3249 test->buildAngles(tIndex, angles); 3250 SkTDArray<Angle*> sorted; 3251 // OPTIMIZATION: call a sort that, if base point is the leftmost, 3252 // returns the first counterclockwise hour before 6 o'clock, 3253 // or if the base point is rightmost, returns the first clockwise 3254 // hour after 6 o'clock 3255 sortAngles(angles, sorted); 3256#if DEBUG_SORT 3257 sorted[0]->segment()->debugShowSort(sorted, 0, 0); 3258#endif 3259 // walk the sorted angle fan to find the lowest angle 3260 // above the base point. Currently, the first angle in the sorted array 3261 // is 12 noon or an earlier hour (the next counterclockwise) 3262 int count = sorted.count(); 3263 int left = -1; 3264 int mid = -1; 3265 int right = -1; 3266 bool baseMatches = test->yAtT(tIndex) == basePt.fY; 3267 for (int index = 0; index < count; ++index) { 3268 angle = sorted[index]; 3269 if (baseMatches && angle->isHorizontal()) { 3270 continue; 3271 } 3272 double indexDx = angle->dx(); 3273 if (indexDx < 0) { 3274 left = index; 3275 } else if (indexDx > 0) { 3276 right = index; 3277 int previous = index - 1; 3278 if (previous < 0) { 3279 previous = count - 1; 3280 } 3281 const Angle* prev = sorted[previous]; 3282 if (prev->dy() >= 0 && prev->dx() > 0 && angle->dy() < 0) { 3283#if DEBUG_SORT 3284 SkDebugf("%s use prev\n", __FUNCTION__); 3285#endif 3286 right = previous; 3287 } 3288 break; 3289 } else { 3290 mid = index; 3291 } 3292 } 3293 if (left < 0 && right < 0) { 3294 left = mid; 3295 } 3296 SkASSERT(left >= 0 || right >= 0); 3297 if (left < 0) { 3298 left = right; 3299 } else if (left >= 0 && mid >= 0 && right >= 0 3300 && sorted[mid]->sign() == sorted[right]->sign()) { 3301 left = right; 3302 } 3303 angle = sorted[left]; 3304 test = angle->segment(); 3305 winding = test->windSum(angle); 3306 SkASSERT(winding != SK_MinS32); 3307 windValue = test->windValue(angle); 3308#if DEBUG_WINDING 3309 SkDebugf("%s angle winding=%d windValue=%d sign=%d\n", __FUNCTION__, winding, 3310 windValue, angle->sign()); 3311#endif 3312 } else { 3313 winding = test->windSum(tIndex); 3314 SkASSERT(winding != SK_MinS32); 3315 windValue = test->windValue(tIndex); 3316#if DEBUG_WINDING 3317 SkDebugf("%s single winding=%d windValue=%d\n", __FUNCTION__, winding, 3318 windValue); 3319#endif 3320 } 3321 // see if a + change in T results in a +/- change in X (compute x'(T)) 3322 SkScalar dx = (*SegmentDXAtT[test->verb()])(test->pts(), tHit); 3323#if DEBUG_WINDING 3324 SkDebugf("%s dx=%1.9g\n", __FUNCTION__, dx); 3325#endif 3326 SkASSERT(dx != 0); 3327 if (winding * dx > 0) { // if same signs, result is negative 3328 winding += dx > 0 ? -windValue : windValue; 3329#if DEBUG_WINDING 3330 SkDebugf("%s final winding=%d\n", __FUNCTION__, winding); 3331#endif 3332 } 3333 // start here; 3334 // we're broken because we find a vertical span 3335 return winding; 3336} 3337 3338// OPTIMIZATION: not crazy about linear search here to find top active y. 3339// seems like we should break down and do the sort, or maybe sort each 3340// contours' segments? 3341// Once the segment array is built, there's no reason I can think of not to 3342// sort it in Y. hmmm 3343// FIXME: return the contour found to pass to inner contour check 3344static Segment* findTopContour(SkTDArray<Contour*>& contourList) { 3345 int contourCount = contourList.count(); 3346 int cIndex = 0; 3347 Segment* topStart; 3348 SkScalar bestY = SK_ScalarMax; 3349 Contour* contour; 3350 do { 3351 contour = contourList[cIndex]; 3352 topStart = contour->topSegment(bestY); 3353 } while (!topStart && ++cIndex < contourCount); 3354 if (!topStart) { 3355 return NULL; 3356 } 3357 while (++cIndex < contourCount) { 3358 contour = contourList[cIndex]; 3359 if (bestY < contour->bounds().fTop) { 3360 continue; 3361 } 3362 SkScalar testY = SK_ScalarMax; 3363 Segment* test = contour->topSegment(testY); 3364 if (!test || bestY <= testY) { 3365 continue; 3366 } 3367 topStart = test; 3368 bestY = testY; 3369 } 3370 return topStart; 3371} 3372 3373static Segment* findChase(SkTDArray<Span*>& chase, int& tIndex, int& endIndex, 3374 int contourWinding) { 3375 while (chase.count()) { 3376 Span* span = chase[chase.count() - 1]; 3377 const Span& backPtr = span->fOther->span(span->fOtherIndex); 3378 Segment* segment = backPtr.fOther; 3379 tIndex = backPtr.fOtherIndex; 3380 SkTDArray<Angle> angles; 3381 int done = 0; 3382 if (segment->activeAngle(tIndex, done, angles)) { 3383 Angle* last = angles.end() - 1; 3384 tIndex = last->start(); 3385 endIndex = last->end(); 3386 return last->segment(); 3387 } 3388 if (done == angles.count()) { 3389 chase.pop(&span); 3390 continue; 3391 } 3392 SkTDArray<Angle*> sorted; 3393 sortAngles(angles, sorted); 3394 // find first angle, initialize winding to computed fWindSum 3395 int firstIndex = -1; 3396 const Angle* angle; 3397 int winding; 3398 do { 3399 angle = sorted[++firstIndex]; 3400 segment = angle->segment(); 3401 winding = segment->windSum(angle); 3402 } while (winding == SK_MinS32); 3403 int spanWinding = segment->spanSign(angle->start(), angle->end()); 3404 #if DEBUG_WINDING 3405 SkDebugf("%s winding=%d spanWinding=%d contourWinding=%d\n", 3406 __FUNCTION__, winding, spanWinding, contourWinding); 3407 #endif 3408 // turn swinding into contourWinding 3409 if (spanWinding * winding < 0) { 3410 winding += spanWinding; 3411 } 3412 #if DEBUG_SORT 3413 segment->debugShowSort(sorted, firstIndex, winding); 3414 #endif 3415 // we care about first sign and whether wind sum indicates this 3416 // edge is inside or outside. Maybe need to pass span winding 3417 // or first winding or something into this function? 3418 // advance to first undone angle, then return it and winding 3419 // (to set whether edges are active or not) 3420 int nextIndex = firstIndex + 1; 3421 int angleCount = sorted.count(); 3422 int lastIndex = firstIndex != 0 ? firstIndex : angleCount; 3423 angle = sorted[firstIndex]; 3424 winding -= angle->segment()->spanSign(angle); 3425 do { 3426 SkASSERT(nextIndex != firstIndex); 3427 if (nextIndex == angleCount) { 3428 nextIndex = 0; 3429 } 3430 angle = sorted[nextIndex]; 3431 segment = angle->segment(); 3432 int maxWinding = winding; 3433 winding -= segment->spanSign(angle); 3434 #if DEBUG_SORT 3435 SkDebugf("%s id=%d maxWinding=%d winding=%d sign=%d\n", __FUNCTION__, 3436 segment->debugID(), maxWinding, winding, angle->sign()); 3437 #endif 3438 tIndex = angle->start(); 3439 endIndex = angle->end(); 3440 int lesser = SkMin32(tIndex, endIndex); 3441 const Span& nextSpan = segment->span(lesser); 3442 if (!nextSpan.fDone) { 3443#if 1 3444 // FIXME: this be wrong. assign startWinding if edge is in 3445 // same direction. If the direction is opposite, winding to 3446 // assign is flipped sign or +/- 1? 3447 if (useInnerWinding(maxWinding, winding)) { 3448 maxWinding = winding; 3449 } 3450 segment->markWinding(lesser, maxWinding); 3451#endif 3452 break; 3453 } 3454 } while (++nextIndex != lastIndex); 3455 return segment; 3456 } 3457 return NULL; 3458} 3459 3460#if DEBUG_ACTIVE_SPANS 3461static void debugShowActiveSpans(SkTDArray<Contour*>& contourList) { 3462 for (int index = 0; index < contourList.count(); ++ index) { 3463 contourList[index]->debugShowActiveSpans(); 3464 } 3465} 3466#endif 3467 3468static bool windingIsActive(int winding, int spanWinding) { 3469 return winding * spanWinding <= 0 && abs(winding) <= abs(spanWinding) 3470 && (!winding || !spanWinding || winding == -spanWinding); 3471} 3472 3473// Each segment may have an inside or an outside. Segments contained within 3474// winding may have insides on either side, and form a contour that should be 3475// ignored. Segments that are coincident with opposing direction segments may 3476// have outsides on either side, and should also disappear. 3477// 'Normal' segments will have one inside and one outside. Subsequent connections 3478// when winding should follow the intersection direction. If more than one edge 3479// is an option, choose first edge that continues the inside. 3480 // since we start with leftmost top edge, we'll traverse through a 3481 // smaller angle counterclockwise to get to the next edge. 3482static void bridge(SkTDArray<Contour*>& contourList, SkPath& simple) { 3483 bool firstContour = true; 3484 do { 3485 Segment* topStart = findTopContour(contourList); 3486 if (!topStart) { 3487 break; 3488 } 3489 // Start at the top. Above the top is outside, below is inside. 3490 // follow edges to intersection by changing the index by direction. 3491 int index, endIndex; 3492 Segment* current = topStart->findTop(index, endIndex); 3493 int contourWinding; 3494 if (firstContour) { 3495 contourWinding = 0; 3496 firstContour = false; 3497 } else { 3498 int sumWinding = current->windSum(SkMin32(index, endIndex)); 3499 // FIXME: don't I have to adjust windSum to get contourWinding? 3500 if (sumWinding == SK_MinS32) { 3501 sumWinding = current->computeSum(index, endIndex); 3502 } 3503 if (sumWinding == SK_MinS32) { 3504 contourWinding = innerContourCheck(contourList, current, 3505 index, endIndex); 3506 } else { 3507 contourWinding = sumWinding; 3508 int spanWinding = current->spanSign(index, endIndex); 3509 bool inner = useInnerWinding(sumWinding - spanWinding, sumWinding); 3510 if (inner) { 3511 contourWinding -= spanWinding; 3512 } 3513#if DEBUG_WINDING 3514 SkDebugf("%s --- sumWinding=%d spanWinding=%d sign=%d inner=%d result=%d\n", __FUNCTION__, 3515 sumWinding, spanWinding, SkSign32(index - endIndex), 3516 inner, contourWinding); 3517#endif 3518 } 3519#if DEBUG_WINDING 3520 // SkASSERT(current->debugVerifyWinding(index, endIndex, contourWinding)); 3521 SkDebugf("%s contourWinding=%d\n", __FUNCTION__, contourWinding); 3522#endif 3523 } 3524 SkPoint lastPt; 3525 bool firstTime = true; 3526 int winding = contourWinding; 3527 int spanWinding = current->spanSign(index, endIndex); 3528 // FIXME: needs work. While it works in limited situations, it does 3529 // not always compute winding correctly. Active should be removed and instead 3530 // the initial winding should be correctly passed in so that if the 3531 // inner contour is wound the same way, it never finds an accumulated 3532 // winding of zero. Inside 'find next', we need to look for transitions 3533 // other than zero when resolving sorted angles. 3534 bool active = windingIsActive(winding, spanWinding); 3535 SkTDArray<Span*> chaseArray; 3536 do { 3537 #if DEBUG_WINDING 3538 SkDebugf("%s active=%s winding=%d spanWinding=%d\n", 3539 __FUNCTION__, active ? "true" : "false", 3540 winding, spanWinding); 3541 #endif 3542 const SkPoint* firstPt = NULL; 3543 do { 3544 SkASSERT(!current->done()); 3545 int nextStart, nextEnd; 3546 Segment* next = current->findNext(chaseArray, 3547 firstTime, active, index, endIndex, 3548 nextStart, nextEnd, winding, spanWinding); 3549 if (!next) { 3550 break; 3551 } 3552 if (!firstPt) { 3553 firstPt = ¤t->addMoveTo(index, simple, active); 3554 } 3555 lastPt = current->addCurveTo(index, endIndex, simple, active); 3556 current = next; 3557 index = nextStart; 3558 endIndex = nextEnd; 3559 firstTime = false; 3560 } while (*firstPt != lastPt && (active || !current->done())); 3561 if (firstPt && active) { 3562 #if DEBUG_PATH_CONSTRUCTION 3563 SkDebugf("%s close\n", __FUNCTION__); 3564 #endif 3565 simple.close(); 3566 } 3567 current = findChase(chaseArray, index, endIndex, contourWinding); 3568 #if DEBUG_ACTIVE_SPANS 3569 debugShowActiveSpans(contourList); 3570 #endif 3571 if (!current) { 3572 break; 3573 } 3574 int lesser = SkMin32(index, endIndex); 3575 spanWinding = current->spanSign(index, endIndex); 3576 winding = current->windSum(lesser); 3577 bool inner = useInnerWinding(winding - spanWinding, winding); 3578 #if DEBUG_WINDING 3579 SkDebugf("%s --- id=%d t=%1.9g spanWinding=%d winding=%d sign=%d" 3580 " inner=%d result=%d\n", 3581 __FUNCTION__, current->debugID(), current->t(lesser), 3582 spanWinding, winding, SkSign32(index - endIndex), 3583 useInnerWinding(winding - spanWinding, winding), 3584 inner ? winding - spanWinding : winding); 3585 #endif 3586 if (inner) { 3587 winding -= spanWinding; 3588 } 3589 active = windingIsActive(winding, spanWinding); 3590 } while (true); 3591 } while (true); 3592} 3593 3594static void fixOtherTIndex(SkTDArray<Contour*>& contourList) { 3595 int contourCount = contourList.count(); 3596 for (int cTest = 0; cTest < contourCount; ++cTest) { 3597 Contour* contour = contourList[cTest]; 3598 contour->fixOtherTIndex(); 3599 } 3600} 3601 3602static void makeContourList(SkTArray<Contour>& contours, 3603 SkTDArray<Contour*>& list) { 3604 int count = contours.count(); 3605 if (count == 0) { 3606 return; 3607 } 3608 for (int index = 0; index < count; ++index) { 3609 *list.append() = &contours[index]; 3610 } 3611 QSort<Contour>(list.begin(), list.end() - 1); 3612} 3613 3614void simplifyx(const SkPath& path, SkPath& simple) { 3615 // returns 1 for evenodd, -1 for winding, regardless of inverse-ness 3616 int winding = (path.getFillType() & 1) ? 1 : -1; 3617 simple.reset(); 3618 simple.setFillType(SkPath::kEvenOdd_FillType); 3619 3620 // turn path into list of segments 3621 SkTArray<Contour> contours; 3622 // FIXME: add self-intersecting cubics' T values to segment 3623 EdgeBuilder builder(path, contours); 3624 SkTDArray<Contour*> contourList; 3625 makeContourList(contours, contourList); 3626 Contour** currentPtr = contourList.begin(); 3627 if (!currentPtr) { 3628 return; 3629 } 3630 Contour** listEnd = contourList.end(); 3631 // find all intersections between segments 3632 do { 3633 Contour** nextPtr = currentPtr; 3634 Contour* current = *currentPtr++; 3635 Contour* next; 3636 do { 3637 next = *nextPtr++; 3638 } while (addIntersectTs(current, next) && nextPtr != listEnd); 3639 } while (currentPtr != listEnd); 3640 // eat through coincident edges 3641 coincidenceCheck(contourList, winding); 3642 fixOtherTIndex(contourList); 3643 // construct closed contours 3644 bridge(contourList, simple); 3645} 3646 3647