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