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