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 8#include "Simplify.h" 9 10#undef SkASSERT 11#define SkASSERT(cond) while (!(cond)) { sk_throw(); } 12 13// FIXME: remove once debugging is complete 14#if 01 // set to 1 for no debugging whatsoever 15 16//const bool gRunTestsInOneThread = false; 17 18#define DEBUG_ACTIVE_LESS_THAN 0 19#define DEBUG_ADD 0 20#define DEBUG_ADD_BOTTOM_TS 0 21#define DEBUG_ADD_INTERSECTING_TS 0 22#define DEBUG_ADJUST_COINCIDENT 0 23#define DEBUG_ASSEMBLE 0 24#define DEBUG_BOTTOM 0 25#define DEBUG_BRIDGE 0 26#define DEBUG_DUMP 0 27#define DEBUG_SORT_HORIZONTAL 0 28#define DEBUG_OUT 0 29#define DEBUG_OUT_LESS_THAN 0 30#define DEBUG_SPLIT 0 31#define DEBUG_STITCH_EDGE 0 32#define DEBUG_TRIM_LINE 0 33 34#else 35 36//const bool gRunTestsInOneThread = true; 37 38#define DEBUG_ACTIVE_LESS_THAN 0 39#define DEBUG_ADD 01 40#define DEBUG_ADD_BOTTOM_TS 0 41#define DEBUG_ADD_INTERSECTING_TS 0 42#define DEBUG_ADJUST_COINCIDENT 1 43#define DEBUG_ASSEMBLE 1 44#define DEBUG_BOTTOM 0 45#define DEBUG_BRIDGE 1 46#define DEBUG_DUMP 1 47#define DEBUG_SORT_HORIZONTAL 01 48#define DEBUG_OUT 01 49#define DEBUG_OUT_LESS_THAN 0 50#define DEBUG_SPLIT 1 51#define DEBUG_STITCH_EDGE 1 52#define DEBUG_TRIM_LINE 1 53 54#endif 55 56#if DEBUG_ASSEMBLE || DEBUG_BRIDGE 57static const char* kLVerbStr[] = {"", "line", "quad", "cubic"}; 58#endif 59#if DEBUG_STITCH_EDGE 60static const char* kUVerbStr[] = {"", "Line", "Quad", "Cubic"}; 61#endif 62 63static int LineIntersect(const SkPoint a[2], const SkPoint b[2], 64 Intersections& intersections) { 65 const _Line aLine = {{a[0].fX, a[0].fY}, {a[1].fX, a[1].fY}}; 66 const _Line bLine = {{b[0].fX, b[0].fY}, {b[1].fX, b[1].fY}}; 67 return intersect(aLine, bLine, intersections); 68} 69 70static int QuadLineIntersect(const SkPoint a[3], const SkPoint b[2], 71 Intersections& intersections) { 72 const Quadratic aQuad = {{a[0].fX, a[0].fY}, {a[1].fX, a[1].fY}, {a[2].fX, a[2].fY}}; 73 const _Line bLine = {{b[0].fX, b[0].fY}, {b[1].fX, b[1].fY}}; 74 intersect(aQuad, bLine, intersections); 75 return intersections.fUsed; 76} 77 78static int CubicLineIntersect(const SkPoint a[2], const SkPoint b[3], 79 Intersections& intersections) { 80 const Cubic aCubic = {{a[0].fX, a[0].fY}, {a[1].fX, a[1].fY}, {a[2].fX, a[2].fY}, 81 {a[3].fX, a[3].fY}}; 82 const _Line bLine = {{b[0].fX, b[0].fY}, {b[1].fX, b[1].fY}}; 83 return intersect(aCubic, bLine, intersections); 84} 85 86static int QuadIntersect(const SkPoint a[3], const SkPoint b[3], 87 Intersections& intersections) { 88 const Quadratic aQuad = {{a[0].fX, a[0].fY}, {a[1].fX, a[1].fY}, {a[2].fX, a[2].fY}}; 89 const Quadratic bQuad = {{b[0].fX, b[0].fY}, {b[1].fX, b[1].fY}, {b[2].fX, b[2].fY}}; 90 intersect2(aQuad, bQuad, intersections); 91 return intersections.fUsed; 92} 93 94static int CubicIntersect(const SkPoint a[4], const SkPoint b[4], 95 Intersections& intersections) { 96 const Cubic aCubic = {{a[0].fX, a[0].fY}, {a[1].fX, a[1].fY}, {a[2].fX, a[2].fY}, 97 {a[3].fX, a[3].fY}}; 98 const Cubic bCubic = {{b[0].fX, b[0].fY}, {b[1].fX, b[1].fY}, {b[2].fX, b[2].fY}, 99 {b[3].fX, b[3].fY}}; 100 intersect(aCubic, bCubic, intersections); 101 return intersections.fUsed; 102} 103 104static int LineIntersect(const SkPoint a[2], SkScalar left, SkScalar right, 105 SkScalar y, double aRange[2]) { 106 const _Line aLine = {{a[0].fX, a[0].fY}, {a[1].fX, a[1].fY}}; 107 return horizontalLineIntersect(aLine, left, right, y, aRange); 108} 109 110static int QuadIntersect(const SkPoint a[3], SkScalar left, SkScalar right, 111 SkScalar y, double aRange[3]) { 112 const Quadratic aQuad = {{a[0].fX, a[0].fY}, {a[1].fX, a[1].fY}, {a[2].fX, a[2].fY}}; 113 return horizontalIntersect(aQuad, left, right, y, aRange); 114} 115 116static int CubicIntersect(const SkPoint a[4], SkScalar left, SkScalar right, 117 SkScalar y, double aRange[4]) { 118 const Cubic aCubic = {{a[0].fX, a[0].fY}, {a[1].fX, a[1].fY}, {a[2].fX, a[2].fY}, 119 {a[3].fX, a[3].fY}}; 120 return horizontalIntersect(aCubic, left, right, y, aRange); 121} 122 123static void LineXYAtT(const SkPoint a[2], double t, SkPoint* out) { 124 const _Line line = {{a[0].fX, a[0].fY}, {a[1].fX, a[1].fY}}; 125 double x, y; 126 xy_at_t(line, t, x, y); 127 out->fX = SkDoubleToScalar(x); 128 out->fY = SkDoubleToScalar(y); 129} 130 131static void QuadXYAtT(const SkPoint a[3], double t, SkPoint* out) { 132 const Quadratic quad = {{a[0].fX, a[0].fY}, {a[1].fX, a[1].fY}, {a[2].fX, a[2].fY}}; 133 double x, y; 134 xy_at_t(quad, t, x, y); 135 out->fX = SkDoubleToScalar(x); 136 out->fY = SkDoubleToScalar(y); 137} 138 139static void CubicXYAtT(const SkPoint a[4], double t, SkPoint* out) { 140 const Cubic cubic = {{a[0].fX, a[0].fY}, {a[1].fX, a[1].fY}, {a[2].fX, a[2].fY}, 141 {a[3].fX, a[3].fY}}; 142 double x, y; 143 xy_at_t(cubic, t, x, y); 144 out->fX = SkDoubleToScalar(x); 145 out->fY = SkDoubleToScalar(y); 146} 147 148static SkScalar LineYAtT(const SkPoint a[2], double t) { 149 const _Line aLine = {{a[0].fX, a[0].fY}, {a[1].fX, a[1].fY}}; 150 double y; 151 xy_at_t(aLine, t, *(double*) 0, y); 152 return SkDoubleToScalar(y); 153} 154 155static SkScalar QuadYAtT(const SkPoint a[3], double t) { 156 const Quadratic quad = {{a[0].fX, a[0].fY}, {a[1].fX, a[1].fY}, {a[2].fX, a[2].fY}}; 157 double y; 158 xy_at_t(quad, t, *(double*) 0, y); 159 return SkDoubleToScalar(y); 160} 161 162static SkScalar CubicYAtT(const SkPoint a[4], double t) { 163 const Cubic cubic = {{a[0].fX, a[0].fY}, {a[1].fX, a[1].fY}, {a[2].fX, a[2].fY}, 164 {a[3].fX, a[3].fY}}; 165 double y; 166 xy_at_t(cubic, t, *(double*) 0, y); 167 return SkDoubleToScalar(y); 168} 169 170static void LineSubDivide(const SkPoint a[2], double startT, double endT, 171 SkPoint sub[2]) { 172 const _Line aLine = {{a[0].fX, a[0].fY}, {a[1].fX, a[1].fY}}; 173 _Line dst; 174 sub_divide(aLine, startT, endT, dst); 175 sub[0].fX = SkDoubleToScalar(dst[0].x); 176 sub[0].fY = SkDoubleToScalar(dst[0].y); 177 sub[1].fX = SkDoubleToScalar(dst[1].x); 178 sub[1].fY = SkDoubleToScalar(dst[1].y); 179} 180 181static void QuadSubDivide(const SkPoint a[3], double startT, double endT, 182 SkPoint sub[3]) { 183 const Quadratic aQuad = {{a[0].fX, a[0].fY}, {a[1].fX, a[1].fY}, 184 {a[2].fX, a[2].fY}}; 185 Quadratic dst; 186 sub_divide(aQuad, startT, endT, dst); 187 sub[0].fX = SkDoubleToScalar(dst[0].x); 188 sub[0].fY = SkDoubleToScalar(dst[0].y); 189 sub[1].fX = SkDoubleToScalar(dst[1].x); 190 sub[1].fY = SkDoubleToScalar(dst[1].y); 191 sub[2].fX = SkDoubleToScalar(dst[2].x); 192 sub[2].fY = SkDoubleToScalar(dst[2].y); 193} 194 195static void CubicSubDivide(const SkPoint a[4], double startT, double endT, 196 SkPoint sub[4]) { 197 const Cubic aCubic = {{a[0].fX, a[0].fY}, {a[1].fX, a[1].fY}, 198 {a[2].fX, a[2].fY}, {a[3].fX, a[3].fY}}; 199 Cubic dst; 200 sub_divide(aCubic, startT, endT, dst); 201 sub[0].fX = SkDoubleToScalar(dst[0].x); 202 sub[0].fY = SkDoubleToScalar(dst[0].y); 203 sub[1].fX = SkDoubleToScalar(dst[1].x); 204 sub[1].fY = SkDoubleToScalar(dst[1].y); 205 sub[2].fX = SkDoubleToScalar(dst[2].x); 206 sub[2].fY = SkDoubleToScalar(dst[2].y); 207 sub[3].fX = SkDoubleToScalar(dst[3].x); 208 sub[3].fY = SkDoubleToScalar(dst[3].y); 209} 210 211static void QuadSubBounds(const SkPoint a[3], double startT, double endT, 212 SkRect& bounds) { 213 SkPoint dst[3]; 214 QuadSubDivide(a, startT, endT, dst); 215 bounds.fLeft = bounds.fRight = dst[0].fX; 216 bounds.fTop = bounds.fBottom = dst[0].fY; 217 for (int index = 1; index < 3; ++index) { 218 bounds.growToInclude(dst[index].fX, dst[index].fY); 219 } 220} 221 222static void CubicSubBounds(const SkPoint a[4], double startT, double endT, 223 SkRect& bounds) { 224 SkPoint dst[4]; 225 CubicSubDivide(a, startT, endT, dst); 226 bounds.fLeft = bounds.fRight = dst[0].fX; 227 bounds.fTop = bounds.fBottom = dst[0].fY; 228 for (int index = 1; index < 4; ++index) { 229 bounds.growToInclude(dst[index].fX, dst[index].fY); 230 } 231} 232 233static SkPath::Verb QuadReduceOrder(SkPoint a[4]) { 234 const Quadratic aQuad = {{a[0].fX, a[0].fY}, {a[1].fX, a[1].fY}, 235 {a[2].fX, a[2].fY}}; 236 Quadratic dst; 237 int order = reduceOrder(aQuad, dst, kReduceOrder_TreatAsFill); 238 for (int index = 0; index < order; ++index) { 239 a[index].fX = SkDoubleToScalar(dst[index].x); 240 a[index].fY = SkDoubleToScalar(dst[index].y); 241 } 242 if (order == 1) { // FIXME: allow returning points, caller should discard 243 a[1] = a[0]; 244 return (SkPath::Verb) order; 245 } 246 return (SkPath::Verb) (order - 1); 247} 248 249static SkPath::Verb CubicReduceOrder(SkPoint a[4]) { 250 const Cubic aCubic = {{a[0].fX, a[0].fY}, {a[1].fX, a[1].fY}, 251 {a[2].fX, a[2].fY}, {a[3].fX, a[3].fY}}; 252 Cubic dst; 253 int order = reduceOrder(aCubic, dst, kReduceOrder_QuadraticsAllowed, kReduceOrder_TreatAsFill); 254 for (int index = 0; index < order; ++index) { 255 a[index].fX = SkDoubleToScalar(dst[index].x); 256 a[index].fY = SkDoubleToScalar(dst[index].y); 257 } 258 if (order == 1) { // FIXME: allow returning points, caller should discard 259 a[1] = a[0]; 260 return (SkPath::Verb) order; 261 } 262 return (SkPath::Verb) (order - 1); 263} 264 265static bool IsCoincident(const SkPoint a[2], const SkPoint& above, 266 const SkPoint& below) { 267 const _Line aLine = {{a[0].fX, a[0].fY}, {a[1].fX, a[1].fY}}; 268 const _Line bLine = {{above.fX, above.fY}, {below.fX, below.fY}}; 269 return implicit_matches_ulps(aLine, bLine, 32); 270} 271 272/* 273list of edges 274bounds for edge 275sort 276active T 277 278if a contour's bounds is outside of the active area, no need to create edges 279*/ 280 281/* given one or more paths, 282 find the bounds of each contour, select the active contours 283 for each active contour, compute a set of edges 284 each edge corresponds to one or more lines and curves 285 leave edges unbroken as long as possible 286 when breaking edges, compute the t at the break but leave the control points alone 287 288 */ 289 290void contourBounds(const SkPath& path, SkTDArray<SkRect>& boundsArray) { 291 SkPath::Iter iter(path, false); 292 SkPoint pts[4]; 293 SkPath::Verb verb; 294 SkRect bounds; 295 bounds.setEmpty(); 296 int count = 0; 297 while ((verb = iter.next(pts)) != SkPath::kDone_Verb) { 298 switch (verb) { 299 case SkPath::kMove_Verb: 300 if (!bounds.isEmpty()) { 301 *boundsArray.append() = bounds; 302 } 303 bounds.set(pts[0].fX, pts[0].fY, pts[0].fX, pts[0].fY); 304 count = 0; 305 break; 306 case SkPath::kLine_Verb: 307 count = 1; 308 break; 309 case SkPath::kQuad_Verb: 310 count = 2; 311 break; 312 case SkPath::kCubic_Verb: 313 count = 3; 314 break; 315 case SkPath::kClose_Verb: 316 count = 0; 317 break; 318 default: 319 SkDEBUGFAIL("bad verb"); 320 return; 321 } 322 for (int i = 1; i <= count; ++i) { 323 bounds.growToInclude(pts[i].fX, pts[i].fY); 324 } 325 } 326} 327 328static bool extendLine(const SkPoint line[2], const SkPoint& add) { 329 // FIXME: allow this to extend lines that have slopes that are nearly equal 330 SkScalar dx1 = line[1].fX - line[0].fX; 331 SkScalar dy1 = line[1].fY - line[0].fY; 332 SkScalar dx2 = add.fX - line[0].fX; 333 SkScalar dy2 = add.fY - line[0].fY; 334 return dx1 * dy2 == dx2 * dy1; 335} 336 337// OPTIMIZATION: this should point to a list of input data rather than duplicating 338// the line data here. This would reduce the need to assemble the results. 339struct OutEdge { 340 bool operator<(const OutEdge& rh) const { 341 const SkPoint& first = fPts[0]; 342 const SkPoint& rhFirst = rh.fPts[0]; 343 return first.fY == rhFirst.fY 344 ? first.fX < rhFirst.fX 345 : first.fY < rhFirst.fY; 346 } 347 348 SkPoint fPts[4]; 349 int fID; // id of edge generating data 350 uint8_t fVerb; // FIXME: not read from everywhere 351 bool fCloseCall; // edge is trimmable if not originally coincident 352}; 353 354class OutEdgeBuilder { 355public: 356 OutEdgeBuilder(bool fill) 357 : fFill(fill) { 358 } 359 360 void addCurve(const SkPoint line[4], SkPath::Verb verb, int id, 361 bool closeCall) { 362 OutEdge& newEdge = fEdges.push_back(); 363 memcpy(newEdge.fPts, line, (verb + 1) * sizeof(SkPoint)); 364 newEdge.fVerb = verb; 365 newEdge.fID = id; 366 newEdge.fCloseCall = closeCall; 367 } 368 369 bool trimLine(SkScalar y, int id) { 370 size_t count = fEdges.count(); 371 while (count-- != 0) { 372 OutEdge& edge = fEdges[count]; 373 if (edge.fID != id) { 374 continue; 375 } 376 if (edge.fCloseCall) { 377 return false; 378 } 379 SkASSERT(edge.fPts[0].fY <= y); 380 if (edge.fPts[1].fY <= y) { 381 continue; 382 } 383 edge.fPts[1].fX = edge.fPts[0].fX + (y - edge.fPts[0].fY) 384 * (edge.fPts[1].fX - edge.fPts[0].fX) 385 / (edge.fPts[1].fY - edge.fPts[0].fY); 386 edge.fPts[1].fY = y; 387#if DEBUG_TRIM_LINE 388 SkDebugf("%s edge=%d %1.9g,%1.9g\n", __FUNCTION__, id, 389 edge.fPts[1].fX, y); 390#endif 391 return true; 392 } 393 return false; 394 } 395 396 void assemble(SkPath& simple) { 397 size_t listCount = fEdges.count(); 398 if (listCount == 0) { 399 return; 400 } 401 do { 402 size_t listIndex = 0; 403 int advance = 1; 404 while (listIndex < listCount && fTops[listIndex] == 0) { 405 ++listIndex; 406 } 407 if (listIndex >= listCount) { 408 break; 409 } 410 int closeEdgeIndex = -listIndex - 1; 411 // the curve is deferred and not added right away because the 412 // following edge may extend the first curve. 413 SkPoint firstPt, lastCurve[4]; 414 uint8_t lastVerb; 415#if DEBUG_ASSEMBLE 416 int firstIndex, lastIndex; 417 const int tab = 8; 418#endif 419 bool doMove = true; 420 int edgeIndex; 421 do { 422 SkPoint* ptArray = fEdges[listIndex].fPts; 423 uint8_t verb = fEdges[listIndex].fVerb; 424 SkPoint* curve[4]; 425 if (advance < 0) { 426 curve[0] = &ptArray[verb]; 427 if (verb == SkPath::kCubic_Verb) { 428 curve[1] = &ptArray[2]; 429 curve[2] = &ptArray[1]; 430 } 431 curve[verb] = &ptArray[0]; 432 } else { 433 curve[0] = &ptArray[0]; 434 if (verb == SkPath::kCubic_Verb) { 435 curve[1] = &ptArray[1]; 436 curve[2] = &ptArray[2]; 437 } 438 curve[verb] = &ptArray[verb]; 439 } 440 if (verb == SkPath::kQuad_Verb) { 441 curve[1] = &ptArray[1]; 442 } 443 if (doMove) { 444 firstPt = *curve[0]; 445 simple.moveTo(curve[0]->fX, curve[0]->fY); 446#if DEBUG_ASSEMBLE 447 SkDebugf("%s %d moveTo (%g,%g)\n", __FUNCTION__, 448 listIndex + 1, curve[0]->fX, curve[0]->fY); 449 firstIndex = listIndex; 450#endif 451 for (int index = 0; index <= verb; ++index) { 452 lastCurve[index] = *curve[index]; 453 } 454 doMove = false; 455 } else { 456 bool gap = lastCurve[lastVerb] != *curve[0]; 457 if (gap || lastVerb != SkPath::kLine_Verb) { // output the accumulated curve before the gap 458 // FIXME: see comment in bridge -- this probably 459 // conceals errors 460 SkASSERT(fFill && UlpsDiff(lastCurve[lastVerb].fY, 461 curve[0]->fY) <= 10); 462 switch (lastVerb) { 463 case SkPath::kLine_Verb: 464 simple.lineTo(lastCurve[1].fX, lastCurve[1].fY); 465 break; 466 case SkPath::kQuad_Verb: 467 simple.quadTo(lastCurve[1].fX, lastCurve[1].fY, 468 lastCurve[2].fX, lastCurve[2].fY); 469 break; 470 case SkPath::kCubic_Verb: 471 simple.cubicTo(lastCurve[1].fX, lastCurve[1].fY, 472 lastCurve[2].fX, lastCurve[2].fY, 473 lastCurve[3].fX, lastCurve[3].fY); 474 break; 475 } 476#if DEBUG_ASSEMBLE 477 SkDebugf("%*s %d %sTo (%g,%g)\n", tab, "", lastIndex + 1, 478 kLVerbStr[lastVerb], lastCurve[lastVerb].fX, 479 lastCurve[lastVerb].fY); 480#endif 481 } 482 int firstCopy = 1; 483 if (gap || (lastVerb == SkPath::kLine_Verb 484 && (verb != SkPath::kLine_Verb 485 || !extendLine(lastCurve, *curve[verb])))) { 486 // FIXME: see comment in bridge -- this probably 487 // conceals errors 488 SkASSERT(lastCurve[lastVerb] == *curve[0] || 489 (fFill && UlpsDiff(lastCurve[lastVerb].fY, 490 curve[0]->fY) <= 10)); 491 simple.lineTo(curve[0]->fX, curve[0]->fY); 492#if DEBUG_ASSEMBLE 493 SkDebugf("%*s %d gap lineTo (%g,%g)\n", tab, "", 494 lastIndex + 1, curve[0]->fX, curve[0]->fY); 495#endif 496 firstCopy = 0; 497 } else if (lastVerb != SkPath::kLine_Verb) { 498 firstCopy = 0; 499 } 500 for (int index = firstCopy; index <= verb; ++index) { 501 lastCurve[index] = *curve[index]; 502 } 503 } 504 lastVerb = verb; 505#if DEBUG_ASSEMBLE 506 lastIndex = listIndex; 507#endif 508 if (advance < 0) { 509 edgeIndex = fTops[listIndex]; 510 fTops[listIndex] = 0; 511 } else { 512 edgeIndex = fBottoms[listIndex]; 513 fBottoms[listIndex] = 0; 514 } 515 if (edgeIndex) { 516 listIndex = abs(edgeIndex) - 1; 517 if (edgeIndex < 0) { 518 fTops[listIndex] = 0; 519 } else { 520 fBottoms[listIndex] = 0; 521 } 522 } 523 if (edgeIndex == closeEdgeIndex || edgeIndex == 0) { 524 switch (lastVerb) { 525 case SkPath::kLine_Verb: 526 simple.lineTo(lastCurve[1].fX, lastCurve[1].fY); 527 break; 528 case SkPath::kQuad_Verb: 529 simple.quadTo(lastCurve[1].fX, lastCurve[1].fY, 530 lastCurve[2].fX, lastCurve[2].fY); 531 break; 532 case SkPath::kCubic_Verb: 533 simple.cubicTo(lastCurve[1].fX, lastCurve[1].fY, 534 lastCurve[2].fX, lastCurve[2].fY, 535 lastCurve[3].fX, lastCurve[3].fY); 536 break; 537 } 538#if DEBUG_ASSEMBLE 539 SkDebugf("%*s %d %sTo last (%g, %g)\n", tab, "", 540 lastIndex + 1, kLVerbStr[lastVerb], 541 lastCurve[lastVerb].fX, lastCurve[lastVerb].fY); 542#endif 543 if (lastCurve[lastVerb] != firstPt) { 544 simple.lineTo(firstPt.fX, firstPt.fY); 545#if DEBUG_ASSEMBLE 546 SkDebugf("%*s %d final line (%g, %g)\n", tab, "", 547 firstIndex + 1, firstPt.fX, firstPt.fY); 548#endif 549 } 550 simple.close(); 551#if DEBUG_ASSEMBLE 552 SkDebugf("%*s close\n", tab, ""); 553#endif 554 break; 555 } 556 // if this and next edge go different directions 557#if DEBUG_ASSEMBLE 558 SkDebugf("%*s advance=%d edgeIndex=%d flip=%s\n", tab, "", 559 advance, edgeIndex, advance > 0 ^ edgeIndex < 0 ? 560 "true" : "false"); 561#endif 562 if (advance > 0 ^ edgeIndex < 0) { 563 advance = -advance; 564 } 565 } while (edgeIndex); 566 } while (true); 567 } 568 569 // sort points by y, then x 570 // if x/y is identical, sort bottoms before tops 571 // if identical and both tops/bottoms, sort by angle 572 static bool lessThan(SkTArray<OutEdge>& edges, const int one, 573 const int two) { 574 const OutEdge& oneEdge = edges[abs(one) - 1]; 575 int oneIndex = one < 0 ? 0 : oneEdge.fVerb; 576 const SkPoint& startPt1 = oneEdge.fPts[oneIndex]; 577 const OutEdge& twoEdge = edges[abs(two) - 1]; 578 int twoIndex = two < 0 ? 0 : twoEdge.fVerb; 579 const SkPoint& startPt2 = twoEdge.fPts[twoIndex]; 580 if (startPt1.fY != startPt2.fY) { 581 #if DEBUG_OUT_LESS_THAN 582 SkDebugf("%s %d<%d (%g,%g) %s startPt1.fY < startPt2.fY\n", __FUNCTION__, 583 one, two, startPt1.fY, startPt2.fY, 584 startPt1.fY < startPt2.fY ? "true" : "false"); 585 #endif 586 return startPt1.fY < startPt2.fY; 587 } 588 if (startPt1.fX != startPt2.fX) { 589 #if DEBUG_OUT_LESS_THAN 590 SkDebugf("%s %d<%d (%g,%g) %s startPt1.fX < startPt2.fX\n", __FUNCTION__, 591 one, two, startPt1.fX, startPt2.fX, 592 startPt1.fX < startPt2.fX ? "true" : "false"); 593 #endif 594 return startPt1.fX < startPt2.fX; 595 } 596 const SkPoint& endPt1 = oneEdge.fPts[oneIndex ^ oneEdge.fVerb]; 597 const SkPoint& endPt2 = twoEdge.fPts[twoIndex ^ twoEdge.fVerb]; 598 SkScalar dy1 = startPt1.fY - endPt1.fY; 599 SkScalar dy2 = startPt2.fY - endPt2.fY; 600 SkScalar dy1y2 = dy1 * dy2; 601 if (dy1y2 < 0) { // different signs 602 #if DEBUG_OUT_LESS_THAN 603 SkDebugf("%s %d<%d %s dy1 > 0\n", __FUNCTION__, one, two, 604 dy1 > 0 ? "true" : "false"); 605 #endif 606 return dy1 > 0; // one < two if one goes up and two goes down 607 } 608 if (dy1y2 == 0) { 609 #if DEBUG_OUT_LESS_THAN 610 SkDebugf("%s %d<%d %s endPt1.fX < endPt2.fX\n", __FUNCTION__, 611 one, two, endPt1.fX < endPt2.fX ? "true" : "false"); 612 #endif 613 return endPt1.fX < endPt2.fX; 614 } 615 SkScalar dx1y2 = (startPt1.fX - endPt1.fX) * dy2; 616 SkScalar dx2y1 = (startPt2.fX - endPt2.fX) * dy1; 617 #if DEBUG_OUT_LESS_THAN 618 SkDebugf("%s %d<%d %s dy2 < 0 ^ dx1y2 < dx2y1\n", __FUNCTION__, 619 one, two, dy2 < 0 ^ dx1y2 < dx2y1 ? "true" : "false"); 620 #endif 621 return dy2 > 0 ^ dx1y2 < dx2y1; 622 } 623 624 // Sort the indices of paired points and then create more indices so 625 // assemble() can find the next edge and connect the top or bottom 626 void bridge() { 627 size_t index; 628 size_t count = fEdges.count(); 629 if (!count) { 630 return; 631 } 632 SkASSERT(!fFill || count > 1); 633 fTops.setCount(count); 634 sk_bzero(fTops.begin(), sizeof(fTops[0]) * count); 635 fBottoms.setCount(count); 636 sk_bzero(fBottoms.begin(), sizeof(fBottoms[0]) * count); 637 SkTDArray<int> order; 638 for (index = 1; index <= count; ++index) { 639 *order.append() = -index; 640 } 641 for (index = 1; index <= count; ++index) { 642 *order.append() = index; 643 } 644 QSort<SkTArray<OutEdge>, int>(fEdges, order.begin(), order.end() - 1, lessThan); 645 int* lastPtr = order.end() - 1; 646 int* leftPtr = order.begin(); 647 while (leftPtr < lastPtr) { 648 int leftIndex = *leftPtr; 649 int leftOutIndex = abs(leftIndex) - 1; 650 const OutEdge& left = fEdges[leftOutIndex]; 651 int* rightPtr = leftPtr + 1; 652 int rightIndex = *rightPtr; 653 int rightOutIndex = abs(rightIndex) - 1; 654 const OutEdge& right = fEdges[rightOutIndex]; 655 bool pairUp = fFill; 656 if (!pairUp) { 657 const SkPoint& leftMatch = 658 left.fPts[leftIndex < 0 ? 0 : left.fVerb]; 659 const SkPoint& rightMatch = 660 right.fPts[rightIndex < 0 ? 0 : right.fVerb]; 661 pairUp = leftMatch == rightMatch; 662 } else { 663 #if DEBUG_OUT 664 // FIXME : not happy that error in low bit is allowed 665 // this probably conceals error elsewhere 666 if (UlpsDiff(left.fPts[leftIndex < 0 ? 0 : left.fVerb].fY, 667 right.fPts[rightIndex < 0 ? 0 : right.fVerb].fY) > 1) { 668 *fMismatches.append() = leftIndex; 669 if (rightPtr == lastPtr) { 670 *fMismatches.append() = rightIndex; 671 } 672 pairUp = false; 673 } 674 #else 675 SkASSERT(UlpsDiff(left.fPts[leftIndex < 0 ? 0 : left.fVerb].fY, 676 right.fPts[rightIndex < 0 ? 0 : right.fVerb].fY) <= 10); 677 #endif 678 } 679 if (pairUp) { 680 if (leftIndex < 0) { 681 fTops[leftOutIndex] = rightIndex; 682 } else { 683 fBottoms[leftOutIndex] = rightIndex; 684 } 685 if (rightIndex < 0) { 686 fTops[rightOutIndex] = leftIndex; 687 } else { 688 fBottoms[rightOutIndex] = leftIndex; 689 } 690 ++rightPtr; 691 } 692 leftPtr = rightPtr; 693 } 694#if DEBUG_OUT 695 int* mismatch = fMismatches.begin(); 696 while (mismatch != fMismatches.end()) { 697 int leftIndex = *mismatch++; 698 int leftOutIndex = abs(leftIndex) - 1; 699 const OutEdge& left = fEdges[leftOutIndex]; 700 const SkPoint& leftPt = left.fPts[leftIndex < 0 ? 0 : left.fVerb]; 701 SkDebugf("%s left=%d %s (%1.9g,%1.9g)\n", 702 __FUNCTION__, left.fID, leftIndex < 0 ? "top" : "bot", 703 leftPt.fX, leftPt.fY); 704 } 705 SkASSERT(fMismatches.count() == 0); 706#endif 707#if DEBUG_BRIDGE 708 for (index = 0; index < count; ++index) { 709 const OutEdge& edge = fEdges[index]; 710 uint8_t verb = edge.fVerb; 711 SkDebugf("%s %d edge=%d %s (%1.9g,%1.9g) (%1.9g,%1.9g)\n", 712 index == 0 ? __FUNCTION__ : " ", 713 index + 1, edge.fID, kLVerbStr[verb], edge.fPts[0].fX, 714 edge.fPts[0].fY, edge.fPts[verb].fX, edge.fPts[verb].fY); 715 } 716 for (index = 0; index < count; ++index) { 717 SkDebugf(" top of % 2d connects to %s of % 2d\n", index + 1, 718 fTops[index] < 0 ? "top " : "bottom", abs(fTops[index])); 719 SkDebugf(" bottom of % 2d connects to %s of % 2d\n", index + 1, 720 fBottoms[index] < 0 ? "top " : "bottom", abs(fBottoms[index])); 721 } 722#endif 723 } 724 725protected: 726 SkTArray<OutEdge> fEdges; 727 SkTDArray<int> fTops; 728 SkTDArray<int> fBottoms; 729 bool fFill; 730#if DEBUG_OUT 731 SkTDArray<int> fMismatches; 732#endif 733}; 734 735// Bounds, unlike Rect, does not consider a vertical line to be empty. 736struct Bounds : public SkRect { 737 static bool Intersects(const Bounds& a, const Bounds& b) { 738 return a.fLeft <= b.fRight && b.fLeft <= a.fRight && 739 a.fTop <= b.fBottom && b.fTop <= a.fBottom; 740 } 741 742 bool isEmpty() { 743 return fLeft > fRight || fTop > fBottom 744 || (fLeft == fRight && fTop == fBottom) 745 || isnan(fLeft) || isnan(fRight) 746 || isnan(fTop) || isnan(fBottom); 747 } 748}; 749 750class Intercepts { 751public: 752 Intercepts() 753 : fTopIntercepts(0) 754 , fBottomIntercepts(0) 755 , fExplicit(false) { 756 } 757 758 Intercepts& operator=(const Intercepts& src) { 759 fTs = src.fTs; 760 fTopIntercepts = src.fTopIntercepts; 761 fBottomIntercepts = src.fBottomIntercepts; 762 return *this; 763 } 764 765 // OPTIMIZATION: remove this function if it's never called 766 double t(int tIndex) const { 767 if (tIndex == 0) { 768 return 0; 769 } 770 if (tIndex > fTs.count()) { 771 return 1; 772 } 773 return fTs[tIndex - 1]; 774 } 775 776#if DEBUG_DUMP 777 void dump(const SkPoint* pts, SkPath::Verb verb) { 778 const char className[] = "Intercepts"; 779 const int tab = 8; 780 for (int i = 0; i < fTs.count(); ++i) { 781 SkPoint out; 782 switch (verb) { 783 case SkPath::kLine_Verb: 784 LineXYAtT(pts, fTs[i], &out); 785 break; 786 case SkPath::kQuad_Verb: 787 QuadXYAtT(pts, fTs[i], &out); 788 break; 789 case SkPath::kCubic_Verb: 790 CubicXYAtT(pts, fTs[i], &out); 791 break; 792 default: 793 SkASSERT(0); 794 } 795 SkDebugf("%*s.fTs[%d]=%1.9g (%1.9g,%1.9g)\n", tab + sizeof(className), 796 className, i, fTs[i], out.fX, out.fY); 797 } 798 SkDebugf("%*s.fTopIntercepts=%u\n", tab + sizeof(className), 799 className, fTopIntercepts); 800 SkDebugf("%*s.fBottomIntercepts=%u\n", tab + sizeof(className), 801 className, fBottomIntercepts); 802 SkDebugf("%*s.fExplicit=%d\n", tab + sizeof(className), 803 className, fExplicit); 804 } 805#endif 806 807 SkTDArray<double> fTs; 808 unsigned char fTopIntercepts; // 0=init state 1=1 edge >1=multiple edges 809 unsigned char fBottomIntercepts; 810 bool fExplicit; // if set, suppress 0 and 1 811 812}; 813 814struct HorizontalEdge { 815 bool operator<(const HorizontalEdge& rh) const { 816 return fY == rh.fY ? fLeft == rh.fLeft ? fRight < rh.fRight 817 : fLeft < rh.fLeft : fY < rh.fY; 818 } 819 820#if DEBUG_DUMP 821 void dump() { 822 const char className[] = "HorizontalEdge"; 823 const int tab = 4; 824 SkDebugf("%*s.fLeft=%1.9g\n", tab + sizeof(className), className, fLeft); 825 SkDebugf("%*s.fRight=%1.9g\n", tab + sizeof(className), className, fRight); 826 SkDebugf("%*s.fY=%1.9g\n", tab + sizeof(className), className, fY); 827 } 828#endif 829 830 SkScalar fLeft; 831 SkScalar fRight; 832 SkScalar fY; 833}; 834 835struct InEdge { 836 bool operator<(const InEdge& rh) const { 837 return fBounds.fTop == rh.fBounds.fTop 838 ? fBounds.fLeft < rh.fBounds.fLeft 839 : fBounds.fTop < rh.fBounds.fTop; 840 } 841 842 // Avoid collapsing t values that are close to the same since 843 // we walk ts to describe consecutive intersections. Since a pair of ts can 844 // be nearly equal, any problems caused by this should be taken care 845 // of later. 846 int add(double* ts, size_t count, ptrdiff_t verbIndex) { 847 // FIXME: in the pathological case where there is a ton of intercepts, binary search? 848 bool foundIntercept = false; 849 int insertedAt = -1; 850 Intercepts& intercepts = fIntercepts[verbIndex]; 851 for (size_t index = 0; index < count; ++index) { 852 double t = ts[index]; 853 if (t <= 0) { 854 intercepts.fTopIntercepts <<= 1; 855 fContainsIntercepts |= ++intercepts.fTopIntercepts > 1; 856 continue; 857 } 858 if (t >= 1) { 859 intercepts.fBottomIntercepts <<= 1; 860 fContainsIntercepts |= ++intercepts.fBottomIntercepts > 1; 861 continue; 862 } 863 fIntersected = true; 864 foundIntercept = true; 865 size_t tCount = intercepts.fTs.count(); 866 double delta; 867 for (size_t idx2 = 0; idx2 < tCount; ++idx2) { 868 if (t <= intercepts.fTs[idx2]) { 869 // FIXME: ? if (t < intercepts.fTs[idx2]) // failed 870 delta = intercepts.fTs[idx2] - t; 871 if (delta > 0) { 872 insertedAt = idx2; 873 *intercepts.fTs.insert(idx2) = t; 874 } 875 goto nextPt; 876 } 877 } 878 if (tCount == 0 || (delta = t - intercepts.fTs[tCount - 1]) > 0) { 879 insertedAt = tCount; 880 *intercepts.fTs.append() = t; 881 } 882 nextPt: 883 ; 884 } 885 fContainsIntercepts |= foundIntercept; 886 return insertedAt; 887 } 888 889 void addPartial(SkTArray<InEdge>& edges, int ptStart, int ptEnd, 890 int verbStart, int verbEnd) { 891 InEdge* edge = edges.push_back_n(1); 892 int verbCount = verbEnd - verbStart; 893 edge->fIntercepts.push_back_n(verbCount); 894 // uint8_t* verbs = &fVerbs[verbStart]; 895 for (int ceptIdx = 0; ceptIdx < verbCount; ++ceptIdx) { 896 edge->fIntercepts[ceptIdx] = fIntercepts[verbStart + ceptIdx]; 897 } 898 edge->fPts.append(ptEnd - ptStart, &fPts[ptStart]); 899 edge->fVerbs.append(verbCount, &fVerbs[verbStart]); 900 edge->setBounds(); 901 edge->fWinding = fWinding; 902 edge->fContainsIntercepts = fContainsIntercepts; // FIXME: may not be correct -- but do we need to know? 903 } 904 905 void addSplit(SkTArray<InEdge>& edges, SkPoint* pts, uint8_t verb, 906 Intercepts& intercepts, int firstT, int lastT, bool flipped) { 907 InEdge* edge = edges.push_back_n(1); 908 edge->fIntercepts.push_back_n(1); 909 if (firstT == 0) { 910 *edge->fIntercepts[0].fTs.append() = 0; 911 } else { 912 *edge->fIntercepts[0].fTs.append() = intercepts.fTs[firstT - 1]; 913 } 914 bool add1 = lastT == intercepts.fTs.count(); 915 edge->fIntercepts[0].fTs.append(lastT - firstT, &intercepts.fTs[firstT]); 916 if (add1) { 917 *edge->fIntercepts[0].fTs.append() = 1; 918 } 919 edge->fIntercepts[0].fExplicit = true; 920 edge->fPts.append(verb + 1, pts); 921 edge->fVerbs.append(1, &verb); 922 // FIXME: bounds could be better for partial Ts 923 edge->setSubBounds(); 924 edge->fContainsIntercepts = fContainsIntercepts; // FIXME: may not be correct -- but do we need to know? 925 if (flipped) { 926 edge->flipTs(); 927 edge->fWinding = -fWinding; 928 } else { 929 edge->fWinding = fWinding; 930 } 931 } 932 933 bool cached(const InEdge* edge) { 934 // FIXME: in the pathological case where there is a ton of edges, binary search? 935 size_t count = fCached.count(); 936 for (size_t index = 0; index < count; ++index) { 937 if (edge == fCached[index]) { 938 return true; 939 } 940 if (edge < fCached[index]) { 941 *fCached.insert(index) = edge; 942 return false; 943 } 944 } 945 *fCached.append() = edge; 946 return false; 947 } 948 949 void complete(signed char winding) { 950 setBounds(); 951 fIntercepts.push_back_n(fVerbs.count()); 952 if ((fWinding = winding) < 0) { // reverse verbs, pts, if bottom to top 953 flip(); 954 } 955 fContainsIntercepts = fIntersected = false; 956 } 957 958 void flip() { 959 size_t index; 960 size_t last = fPts.count() - 1; 961 for (index = 0; index < last; ++index, --last) { 962 SkTSwap<SkPoint>(fPts[index], fPts[last]); 963 } 964 last = fVerbs.count() - 1; 965 for (index = 0; index < last; ++index, --last) { 966 SkTSwap<uint8_t>(fVerbs[index], fVerbs[last]); 967 } 968 } 969 970 void flipTs() { 971 SkASSERT(fIntercepts.count() == 1); 972 Intercepts& intercepts = fIntercepts[0]; 973 SkASSERT(intercepts.fExplicit); 974 SkTDArray<double>& ts = intercepts.fTs; 975 size_t index; 976 size_t last = ts.count() - 1; 977 for (index = 0; index < last; ++index, --last) { 978 SkTSwap<double>(ts[index], ts[last]); 979 } 980 } 981 982 void reset() { 983 fCached.reset(); 984 fIntercepts.reset(); 985 fPts.reset(); 986 fVerbs.reset(); 987 fBounds.set(SK_ScalarMax, SK_ScalarMax, SK_ScalarMax, SK_ScalarMax); 988 fWinding = 0; 989 fContainsIntercepts = false; 990 fIntersected = false; 991 } 992 993 void setBounds() { 994 SkPoint* ptPtr = fPts.begin(); 995 SkPoint* ptLast = fPts.end(); 996 if (ptPtr == ptLast) { 997 SkDebugf("%s empty edge\n", __FUNCTION__); 998 SkASSERT(0); 999 // FIXME: delete empty edge? 1000 return; 1001 } 1002 fBounds.set(ptPtr->fX, ptPtr->fY, ptPtr->fX, ptPtr->fY); 1003 ++ptPtr; 1004 while (ptPtr != ptLast) { 1005 fBounds.growToInclude(ptPtr->fX, ptPtr->fY); 1006 ++ptPtr; 1007 } 1008 } 1009 1010 // recompute bounds based on subrange of T values 1011 void setSubBounds() { 1012 SkASSERT(fIntercepts.count() == 1); 1013 Intercepts& intercepts = fIntercepts[0]; 1014 SkASSERT(intercepts.fExplicit); 1015 SkASSERT(fVerbs.count() == 1); 1016 SkTDArray<double>& ts = intercepts.fTs; 1017 if (fVerbs[0] == SkPath::kQuad_Verb) { 1018 SkASSERT(fPts.count() == 3); 1019 QuadSubBounds(fPts.begin(), ts[0], ts[ts.count() - 1], fBounds); 1020 } else { 1021 SkASSERT(fVerbs[0] == SkPath::kCubic_Verb); 1022 SkASSERT(fPts.count() == 4); 1023 CubicSubBounds(fPts.begin(), ts[0], ts[ts.count() - 1], fBounds); 1024 } 1025 } 1026 1027 void splitInflectionPts(SkTArray<InEdge>& edges) { 1028 if (!fIntersected) { 1029 return; 1030 } 1031 uint8_t* verbs = fVerbs.begin(); 1032 SkPoint* pts = fPts.begin(); 1033 int lastVerb = 0; 1034 int lastPt = 0; 1035 uint8_t verb; 1036 bool edgeSplit = false; 1037 for (int ceptIdx = 0; ceptIdx < fIntercepts.count(); ++ceptIdx, pts += verb) { 1038 Intercepts& intercepts = fIntercepts[ceptIdx]; 1039 verb = *verbs++; 1040 if (verb <= SkPath::kLine_Verb) { 1041 continue; 1042 } 1043 size_t tCount = intercepts.fTs.count(); 1044 if (!tCount) { 1045 continue; 1046 } 1047 size_t tIndex = (size_t) -1; 1048 SkScalar y = pts[0].fY; 1049 int lastSplit = 0; 1050 int firstSplit = -1; 1051 bool curveSplit = false; 1052 while (++tIndex < tCount) { 1053 double nextT = intercepts.fTs[tIndex]; 1054 SkScalar nextY = verb == SkPath::kQuad_Verb 1055 ? QuadYAtT(pts, nextT) : CubicYAtT(pts, nextT); 1056 if (nextY < y) { 1057 edgeSplit = curveSplit = true; 1058 if (firstSplit < 0) { 1059 firstSplit = tIndex; 1060 int nextPt = pts - fPts.begin(); 1061 int nextVerb = verbs - 1 - fVerbs.begin(); 1062 if (lastVerb < nextVerb) { 1063 addPartial(edges, lastPt, nextPt, lastVerb, nextVerb); 1064 #if DEBUG_SPLIT 1065 SkDebugf("%s addPartial 1\n", __FUNCTION__); 1066 #endif 1067 } 1068 lastPt = nextPt; 1069 lastVerb = nextVerb; 1070 } 1071 } else { 1072 if (firstSplit >= 0) { 1073 if (lastSplit < firstSplit) { 1074 addSplit(edges, pts, verb, intercepts, 1075 lastSplit, firstSplit, false); 1076 #if DEBUG_SPLIT 1077 SkDebugf("%s addSplit 1 tIndex=%d,%d\n", 1078 __FUNCTION__, lastSplit, firstSplit); 1079 #endif 1080 } 1081 addSplit(edges, pts, verb, intercepts, 1082 firstSplit, tIndex, true); 1083 #if DEBUG_SPLIT 1084 SkDebugf("%s addSplit 2 tIndex=%d,%d flip\n", 1085 __FUNCTION__, firstSplit, tIndex); 1086 #endif 1087 lastSplit = tIndex; 1088 firstSplit = -1; 1089 } 1090 } 1091 y = nextY; 1092 } 1093 if (curveSplit) { 1094 if (firstSplit < 0) { 1095 firstSplit = lastSplit; 1096 } else { 1097 addSplit(edges, pts, verb, intercepts, lastSplit, 1098 firstSplit, false); 1099 #if DEBUG_SPLIT 1100 SkDebugf("%s addSplit 3 tIndex=%d,%d\n", __FUNCTION__, 1101 lastSplit, firstSplit); 1102 #endif 1103 } 1104 addSplit(edges, pts, verb, intercepts, firstSplit, 1105 tIndex, pts[verb].fY < y); 1106 #if DEBUG_SPLIT 1107 SkDebugf("%s addSplit 4 tIndex=%d,%d %s\n", __FUNCTION__, 1108 firstSplit, tIndex, pts[verb].fY < y ? "flip" : ""); 1109 #endif 1110 } 1111 } 1112 // collapse remainder -- if there's nothing left, clear it somehow? 1113 if (edgeSplit) { 1114 int nextVerb = verbs - 1 - fVerbs.begin(); 1115 if (lastVerb < nextVerb) { 1116 int nextPt = pts - fPts.begin(); 1117 addPartial(edges, lastPt, nextPt, lastVerb, nextVerb); 1118 #if DEBUG_SPLIT 1119 SkDebugf("%s addPartial 2\n", __FUNCTION__); 1120 #endif 1121 } 1122 // OPTIMIZATION: reuse the edge instead of marking it empty 1123 reset(); 1124 } 1125 } 1126 1127#if DEBUG_DUMP 1128 void dump() { 1129 int i; 1130 const char className[] = "InEdge"; 1131 const int tab = 4; 1132 SkDebugf("InEdge %p (edge=%d)\n", this, fID); 1133 for (i = 0; i < fCached.count(); ++i) { 1134 SkDebugf("%*s.fCached[%d]=0x%08x\n", tab + sizeof(className), 1135 className, i, fCached[i]); 1136 } 1137 uint8_t* verbs = fVerbs.begin(); 1138 SkPoint* pts = fPts.begin(); 1139 for (i = 0; i < fIntercepts.count(); ++i) { 1140 SkDebugf("%*s.fIntercepts[%d]:\n", tab + sizeof(className), 1141 className, i); 1142 fIntercepts[i].dump(pts, (SkPath::Verb) *verbs); 1143 pts += *verbs++; 1144 } 1145 for (i = 0; i < fPts.count(); ++i) { 1146 SkDebugf("%*s.fPts[%d]=(%1.9g,%1.9g)\n", tab + sizeof(className), 1147 className, i, fPts[i].fX, fPts[i].fY); 1148 } 1149 for (i = 0; i < fVerbs.count(); ++i) { 1150 SkDebugf("%*s.fVerbs[%d]=%d\n", tab + sizeof(className), 1151 className, i, fVerbs[i]); 1152 } 1153 SkDebugf("%*s.fBounds=(%1.9g, %1.9g, %1.9g, %1.9g)\n", tab + sizeof(className), 1154 className, fBounds.fLeft, fBounds.fTop, 1155 fBounds.fRight, fBounds.fBottom); 1156 SkDebugf("%*s.fWinding=%d\n", tab + sizeof(className), className, 1157 fWinding); 1158 SkDebugf("%*s.fContainsIntercepts=%d\n", tab + sizeof(className), 1159 className, fContainsIntercepts); 1160 SkDebugf("%*s.fIntersected=%d\n", tab + sizeof(className), 1161 className, fIntersected); 1162 } 1163#endif 1164 1165 // FIXME: temporary data : move this to a separate struct? 1166 SkTDArray<const InEdge*> fCached; // list of edges already intercepted 1167 SkTArray<Intercepts> fIntercepts; // one per verb 1168 1169 // persistent data 1170 SkTDArray<SkPoint> fPts; 1171 SkTDArray<uint8_t> fVerbs; 1172 Bounds fBounds; 1173 int fID; 1174 signed char fWinding; 1175 bool fContainsIntercepts; 1176 bool fIntersected; 1177}; 1178 1179class InEdgeBuilder { 1180public: 1181 1182InEdgeBuilder(const SkPath& path, bool ignoreHorizontal, SkTArray<InEdge>& edges, 1183 SkTDArray<HorizontalEdge>& horizontalEdges) 1184 : fPath(path) 1185 , fCurrentEdge(NULL) 1186 , fEdges(edges) 1187 , fHorizontalEdges(horizontalEdges) 1188 , fIgnoreHorizontal(ignoreHorizontal) 1189 , fContainsCurves(false) 1190{ 1191 walk(); 1192} 1193 1194bool containsCurves() const { 1195 return fContainsCurves; 1196} 1197 1198protected: 1199 1200void addEdge() { 1201 SkASSERT(fCurrentEdge); 1202 fCurrentEdge->fPts.append(fPtCount - fPtOffset, &fPts[fPtOffset]); 1203 fPtOffset = 1; 1204 *fCurrentEdge->fVerbs.append() = fVerb; 1205} 1206 1207bool complete() { 1208 if (fCurrentEdge && fCurrentEdge->fVerbs.count()) { 1209 fCurrentEdge->complete(fWinding); 1210 fCurrentEdge = NULL; 1211 return true; 1212 } 1213 return false; 1214} 1215 1216int direction(SkPath::Verb verb) { 1217 fPtCount = verb + 1; 1218 if (fIgnoreHorizontal && isHorizontal()) { 1219 return 0; 1220 } 1221 return fPts[0].fY == fPts[verb].fY 1222 ? fPts[0].fX == fPts[verb].fX ? 0 : fPts[0].fX < fPts[verb].fX 1223 ? 1 : -1 : fPts[0].fY < fPts[verb].fY ? 1 : -1; 1224} 1225 1226bool isHorizontal() { 1227 SkScalar y = fPts[0].fY; 1228 for (int i = 1; i < fPtCount; ++i) { 1229 if (fPts[i].fY != y) { 1230 return false; 1231 } 1232 } 1233 return true; 1234} 1235 1236void startEdge() { 1237 if (!fCurrentEdge) { 1238 fCurrentEdge = fEdges.push_back_n(1); 1239 } 1240 fWinding = 0; 1241 fPtOffset = 0; 1242} 1243 1244void walk() { 1245 SkPath::Iter iter(fPath, true); 1246 int winding = 0; 1247 while ((fVerb = iter.next(fPts)) != SkPath::kDone_Verb) { 1248 switch (fVerb) { 1249 case SkPath::kMove_Verb: 1250 startEdge(); 1251 continue; 1252 case SkPath::kLine_Verb: 1253 winding = direction(SkPath::kLine_Verb); 1254 break; 1255 case SkPath::kQuad_Verb: 1256 fVerb = QuadReduceOrder(fPts); 1257 winding = direction(fVerb); 1258 fContainsCurves |= fVerb == SkPath::kQuad_Verb; 1259 break; 1260 case SkPath::kCubic_Verb: 1261 fVerb = CubicReduceOrder(fPts); 1262 winding = direction(fVerb); 1263 fContainsCurves |= fVerb >= SkPath::kQuad_Verb; 1264 break; 1265 case SkPath::kClose_Verb: 1266 SkASSERT(fCurrentEdge); 1267 complete(); 1268 continue; 1269 default: 1270 SkDEBUGFAIL("bad verb"); 1271 return; 1272 } 1273 if (winding == 0) { 1274 HorizontalEdge* horizontalEdge = fHorizontalEdges.append(); 1275 // FIXME: for degenerate quads and cubics, compute x extremes 1276 horizontalEdge->fLeft = fPts[0].fX; 1277 horizontalEdge->fRight = fPts[fVerb].fX; 1278 horizontalEdge->fY = fPts[0].fY; 1279 if (horizontalEdge->fLeft > horizontalEdge->fRight) { 1280 SkTSwap<SkScalar>(horizontalEdge->fLeft, horizontalEdge->fRight); 1281 } 1282 if (complete()) { 1283 startEdge(); 1284 } 1285 continue; 1286 } 1287 if (fWinding + winding == 0) { 1288 // FIXME: if prior verb or this verb is a horizontal line, reverse 1289 // it instead of starting a new edge 1290 SkASSERT(fCurrentEdge); 1291 if (complete()) { 1292 startEdge(); 1293 } 1294 } 1295 fWinding = winding; 1296 addEdge(); 1297 } 1298 if (!complete()) { 1299 if (fCurrentEdge) { 1300 fEdges.pop_back(); 1301 } 1302 } 1303} 1304 1305private: 1306 const SkPath& fPath; 1307 InEdge* fCurrentEdge; 1308 SkTArray<InEdge>& fEdges; 1309 SkTDArray<HorizontalEdge>& fHorizontalEdges; 1310 SkPoint fPts[4]; 1311 SkPath::Verb fVerb; 1312 int fPtCount; 1313 int fPtOffset; 1314 int8_t fWinding; 1315 bool fIgnoreHorizontal; 1316 bool fContainsCurves; 1317}; 1318 1319struct WorkEdge { 1320 SkScalar bottom() const { 1321 return fPts[verb()].fY; 1322 } 1323 1324 void init(const InEdge* edge) { 1325 fEdge = edge; 1326 fPts = edge->fPts.begin(); 1327 fVerb = edge->fVerbs.begin(); 1328 } 1329 1330 bool advance() { 1331 SkASSERT(fVerb < fEdge->fVerbs.end()); 1332 fPts += *fVerb++; 1333 return fVerb != fEdge->fVerbs.end(); 1334 } 1335 1336 const SkPoint* lastPoints() const { 1337 SkASSERT(fPts >= fEdge->fPts.begin() + lastVerb()); 1338 return &fPts[-lastVerb()]; 1339 } 1340 1341 SkPath::Verb lastVerb() const { 1342 SkASSERT(fVerb > fEdge->fVerbs.begin()); 1343 return (SkPath::Verb) fVerb[-1]; 1344 } 1345 1346 const SkPoint* points() const { 1347 return fPts; 1348 } 1349 1350 SkPath::Verb verb() const { 1351 return (SkPath::Verb) *fVerb; 1352 } 1353 1354 ptrdiff_t verbIndex() const { 1355 return fVerb - fEdge->fVerbs.begin(); 1356 } 1357 1358 int winding() const { 1359 return fEdge->fWinding; 1360 } 1361 1362 const InEdge* fEdge; 1363 const SkPoint* fPts; 1364 const uint8_t* fVerb; 1365}; 1366 1367// always constructed with SkTDArray because new edges are inserted 1368// this may be a inappropriate optimization, suggesting that a separate array of 1369// ActiveEdge* may be faster to insert and search 1370 1371// OPTIMIZATION: Brian suggests that global sorting should be unnecessary, since 1372// as active edges are introduced, only local sorting should be required 1373class ActiveEdge { 1374public: 1375 // this logic must be kept in sync with tooCloseToCall 1376 // callers expect this to only read fAbove, fTangent 1377 bool operator<(const ActiveEdge& rh) const { 1378 if (fVerb == rh.fVerb) { 1379 // FIXME: don't know what to do if verb is quad, cubic 1380 return abCompare(fAbove, fBelow, rh.fAbove, rh.fBelow); 1381 } 1382 // figure out which is quad, line 1383 // if cached data says line did not intersect quad, use top/bottom 1384 if (fVerb != SkPath::kLine_Verb ? noIntersect(rh) : rh.noIntersect(*this)) { 1385 return abCompare(fAbove, fBelow, rh.fAbove, rh.fBelow); 1386 } 1387 // use whichever of top/tangent tangent/bottom overlaps more 1388 // with line top/bot 1389 // assumes quad/cubic can already be upconverted to cubic/cubic 1390 const SkPoint* line[2]; 1391 const SkPoint* curve[4]; 1392 if (fVerb != SkPath::kLine_Verb) { 1393 line[0] = &rh.fAbove; 1394 line[1] = &rh.fBelow; 1395 curve[0] = &fAbove; 1396 curve[1] = &fTangent; 1397 curve[2] = &fBelow; 1398 } else { 1399 line[0] = &fAbove; 1400 line[1] = &fBelow; 1401 curve[0] = &rh.fAbove; 1402 curve[1] = &rh.fTangent; 1403 curve[2] = &rh.fBelow; 1404 } 1405 // FIXME: code has been abandoned, incomplete.... 1406 return false; 1407 } 1408 1409 bool abCompare(const SkPoint& a1, const SkPoint& a2, const SkPoint& b1, 1410 const SkPoint& b2) const { 1411 double topD = a1.fX - b1.fX; 1412 if (b1.fY < a1.fY) { 1413 topD = (b2.fY - b1.fY) * topD - (a1.fY - b1.fY) * (b2.fX - b1.fX); 1414 } else if (b1.fY > a1.fY) { 1415 topD = (a2.fY - a1.fY) * topD + (b1.fY - a1.fY) * (a2.fX - a1.fX); 1416 } 1417 double botD = a2.fX - b2.fX; 1418 if (b2.fY > a2.fY) { 1419 botD = (b2.fY - b1.fY) * botD - (a2.fY - b2.fY) * (b2.fX - b1.fX); 1420 } else if (b2.fY < a2.fY) { 1421 botD = (a2.fY - a1.fY) * botD + (b2.fY - a2.fY) * (a2.fX - a1.fX); 1422 } 1423 // return sign of greater absolute value 1424 return (fabs(topD) > fabs(botD) ? topD : botD) < 0; 1425 } 1426 1427 // If a pair of edges are nearly coincident for some span, add a T in the 1428 // edge so it can be shortened to match the other edge. Note that another 1429 // approach is to trim the edge after it is added to the OutBuilder list -- 1430 // FIXME: since this has no effect if the edge is already done (i.e., 1431 // fYBottom >= y) maybe this can only be done by calling trimLine later. 1432 void addTatYBelow(SkScalar y) { 1433 if (fBelow.fY <= y || fYBottom >= y) { 1434 return; 1435 } 1436 addTatYInner(y); 1437 fFixBelow = true; 1438 } 1439 1440 void addTatYAbove(SkScalar y) { 1441 if (fBelow.fY <= y) { 1442 return; 1443 } 1444 addTatYInner(y); 1445 } 1446 1447 void addTatYInner(SkScalar y) { 1448 if (fWorkEdge.fPts[0].fY > y) { 1449 backup(y); 1450 } 1451 SkScalar left = fWorkEdge.fPts[0].fX; 1452 SkScalar right = fWorkEdge.fPts[1].fX; 1453 if (left > right) { 1454 SkTSwap(left, right); 1455 } 1456 double ts[2]; 1457 SkASSERT(fWorkEdge.fVerb[0] == SkPath::kLine_Verb); 1458 int pts = LineIntersect(fWorkEdge.fPts, left, right, y, ts); 1459 SkASSERT(pts == 1); 1460 // An ActiveEdge or WorkEdge has no need to modify the T values computed 1461 // in the InEdge, except in the following case. If a pair of edges are 1462 // nearly coincident, this may not be detected when the edges are 1463 // intersected. Later, when sorted, and this near-coincidence is found, 1464 // an additional t value must be added, requiring the cast below. 1465 InEdge* writable = const_cast<InEdge*>(fWorkEdge.fEdge); 1466 int insertedAt = writable->add(ts, pts, fWorkEdge.verbIndex()); 1467 #if DEBUG_ADJUST_COINCIDENT 1468 SkDebugf("%s edge=%d y=%1.9g t=%1.9g\n", __FUNCTION__, ID(), y, ts[0]); 1469 #endif 1470 if (insertedAt >= 0) { 1471 if (insertedAt + 1 < fTIndex) { 1472 SkASSERT(insertedAt + 2 == fTIndex); 1473 --fTIndex; 1474 } 1475 } 1476 } 1477 1478 bool advanceT() { 1479 SkASSERT(fTIndex <= fTs->count() - fExplicitTs); 1480 return ++fTIndex <= fTs->count() - fExplicitTs; 1481 } 1482 1483 bool advance() { 1484 // FIXME: flip sense of next 1485 bool result = fWorkEdge.advance(); 1486 fDone = !result; 1487 initT(); 1488 return result; 1489 } 1490 1491 void backup(SkScalar y) { 1492 do { 1493 SkASSERT(fWorkEdge.fEdge->fVerbs.begin() < fWorkEdge.fVerb); 1494 fWorkEdge.fPts -= *--fWorkEdge.fVerb; 1495 SkASSERT(fWorkEdge.fEdge->fPts.begin() <= fWorkEdge.fPts); 1496 } while (fWorkEdge.fPts[0].fY >= y); 1497 initT(); 1498 SkASSERT(!fExplicitTs); 1499 fTIndex = fTs->count() + 1; 1500 } 1501 1502 void calcAboveBelow(double tAbove, double tBelow) { 1503 fVerb = fWorkEdge.verb(); 1504 switch (fVerb) { 1505 case SkPath::kLine_Verb: 1506 LineXYAtT(fWorkEdge.fPts, tAbove, &fAbove); 1507 LineXYAtT(fWorkEdge.fPts, tBelow, &fTangent); 1508 fBelow = fTangent; 1509 break; 1510 case SkPath::kQuad_Verb: 1511 // FIXME: put array in struct to avoid copy? 1512 SkPoint quad[3]; 1513 QuadSubDivide(fWorkEdge.fPts, tAbove, tBelow, quad); 1514 fAbove = quad[0]; 1515 fTangent = quad[0] != quad[1] ? quad[1] : quad[2]; 1516 fBelow = quad[2]; 1517 break; 1518 case SkPath::kCubic_Verb: 1519 SkPoint cubic[3]; 1520 CubicSubDivide(fWorkEdge.fPts, tAbove, tBelow, cubic); 1521 fAbove = cubic[0]; 1522 // FIXME: can't see how quad logic for how tangent is used 1523 // extends to cubic 1524 fTangent = cubic[0] != cubic[1] ? cubic[1] 1525 : cubic[0] != cubic[2] ? cubic[2] : cubic[3]; 1526 fBelow = cubic[3]; 1527 break; 1528 default: 1529 SkASSERT(0); 1530 } 1531 } 1532 1533 void calcLeft(SkScalar y) { 1534 // OPTIMIZE: put a kDone_Verb at the end of the verb list? 1535 if (fDone || fBelow.fY > y) { 1536 return; // nothing to do; use last 1537 } 1538 calcLeft(); 1539 if (fAbove.fY == fBelow.fY) { 1540 SkDebugf("%s edge=%d fAbove.fY != fBelow.fY %1.9g\n", __FUNCTION__, 1541 ID(), fAbove.fY); 1542 } 1543 } 1544 1545 void calcLeft() { 1546 int add = (fTIndex <= fTs->count() - fExplicitTs) - 1; 1547 double tAbove = t(fTIndex + add); 1548 double tBelow = t(fTIndex - ~add); 1549 // OPTIMIZATION: if fAbove, fBelow have already been computed 1550 // for the fTIndex, don't do it again 1551 calcAboveBelow(tAbove, tBelow); 1552 // For identical x, this lets us know which edge is first. 1553 // If both edges have T values < 1, check x at next T (fBelow). 1554 SkASSERT(tAbove != tBelow); 1555 // FIXME: this can loop forever 1556 // need a break if we hit the end 1557 // FIXME: in unit test, figure out how explicit Ts work as well 1558 while (fAbove.fY == fBelow.fY) { 1559 if (add < 0 || fTIndex == fTs->count()) { 1560 add -= 1; 1561 SkASSERT(fTIndex + add >= 0); 1562 tAbove = t(fTIndex + add); 1563 } else { 1564 add += 1; 1565 SkASSERT(fTIndex - ~add <= fTs->count() + 1); 1566 tBelow = t(fTIndex - ~add); 1567 } 1568 calcAboveBelow(tAbove, tBelow); 1569 } 1570 fTAbove = tAbove; 1571 fTBelow = tBelow; 1572 } 1573 1574 bool done(SkScalar bottom) const { 1575 return fDone || fYBottom >= bottom; 1576 } 1577 1578 void fixBelow() { 1579 if (fFixBelow) { 1580 fTBelow = nextT(); 1581 calcAboveBelow(fTAbove, fTBelow); 1582 fFixBelow = false; 1583 } 1584 } 1585 1586 void init(const InEdge* edge) { 1587 fWorkEdge.init(edge); 1588 fDone = false; 1589 initT(); 1590 fBelow.fY = SK_ScalarMin; 1591 fYBottom = SK_ScalarMin; 1592 } 1593 1594 void initT() { 1595 const Intercepts& intercepts = fWorkEdge.fEdge->fIntercepts.front(); 1596 SkASSERT(fWorkEdge.verbIndex() <= fWorkEdge.fEdge->fIntercepts.count()); 1597 const Intercepts* interceptPtr = &intercepts + fWorkEdge.verbIndex(); 1598 fTs = &interceptPtr->fTs; 1599 fExplicitTs = interceptPtr->fExplicit; 1600 // the above is conceptually the same as 1601 // fTs = &fWorkEdge.fEdge->fIntercepts[fWorkEdge.verbIndex()].fTs; 1602 // but templated arrays don't allow returning a pointer to the end() element 1603 fTIndex = 0; 1604 if (!fDone) { 1605 fVerb = fWorkEdge.verb(); 1606 } 1607 SkASSERT(fVerb > SkPath::kMove_Verb); 1608 } 1609 1610 // OPTIMIZATION: record if two edges are coincident when the are intersected 1611 // It's unclear how to do this -- seems more complicated than recording the 1612 // t values, since the same t values could exist intersecting non-coincident 1613 // edges. 1614 bool isCoincidentWith(const ActiveEdge* edge) const { 1615 if (fAbove != edge->fAbove || fBelow != edge->fBelow) { 1616 return false; 1617 } 1618 if (fVerb != edge->fVerb) { 1619 return false; 1620 } 1621 switch (fVerb) { 1622 case SkPath::kLine_Verb: 1623 return true; 1624 default: 1625 // FIXME: add support for quads, cubics 1626 SkASSERT(0); 1627 return false; 1628 } 1629 return false; 1630 } 1631 1632 bool isUnordered(const ActiveEdge* edge) const { 1633 return fAbove == edge->fAbove && fBelow == edge->fBelow; 1634 } 1635 1636// SkPath::Verb lastVerb() const { 1637// return fDone ? fWorkEdge.lastVerb() : fWorkEdge.verb(); 1638// } 1639 1640 const SkPoint* lastPoints() const { 1641 return fDone ? fWorkEdge.lastPoints() : fWorkEdge.points(); 1642 } 1643 1644 bool noIntersect(const ActiveEdge& ) const { 1645 // incomplete 1646 return false; 1647 } 1648 1649 // The shortest close call edge should be moved into a position where 1650 // it contributes if the winding is transitioning to or from zero. 1651 bool swapClose(const ActiveEdge* next, int prev, int wind, int mask) const { 1652#if DEBUG_ADJUST_COINCIDENT 1653 SkDebugf("%s edge=%d (%g) next=%d (%g) prev=%d wind=%d nextWind=%d\n", 1654 __FUNCTION__, ID(), fBelow.fY, next->ID(), next->fBelow.fY, 1655 prev, wind, wind + next->fWorkEdge.winding()); 1656#endif 1657 if ((prev & mask) == 0 || (wind & mask) == 0) { 1658 return next->fBelow.fY < fBelow.fY; 1659 } 1660 int nextWinding = wind + next->fWorkEdge.winding(); 1661 if ((nextWinding & mask) == 0) { 1662 return fBelow.fY < next->fBelow.fY; 1663 } 1664 return false; 1665 } 1666 1667 bool swapCoincident(const ActiveEdge* edge, SkScalar bottom) const { 1668 if (fBelow.fY >= bottom || fDone || edge->fDone) { 1669 return false; 1670 } 1671 ActiveEdge thisWork = *this; 1672 ActiveEdge edgeWork = *edge; 1673 while ((thisWork.advanceT() || thisWork.advance()) 1674 && (edgeWork.advanceT() || edgeWork.advance())) { 1675 thisWork.calcLeft(); 1676 edgeWork.calcLeft(); 1677 if (thisWork < edgeWork) { 1678 return false; 1679 } 1680 if (edgeWork < thisWork) { 1681 return true; 1682 } 1683 } 1684 return false; 1685 } 1686 1687 bool swapUnordered(const ActiveEdge* edge, SkScalar /* bottom */) const { 1688 SkASSERT(fVerb != SkPath::kLine_Verb 1689 || edge->fVerb != SkPath::kLine_Verb); 1690 if (fDone || edge->fDone) { 1691 return false; 1692 } 1693 ActiveEdge thisWork, edgeWork; 1694 extractAboveBelow(thisWork); 1695 edge->extractAboveBelow(edgeWork); 1696 return edgeWork < thisWork; 1697 } 1698 1699 bool tooCloseToCall(const ActiveEdge* edge) const { 1700 int ulps; 1701 double t1, t2, b1, b2; 1702 // This logic must be kept in sync with operator < 1703 if (edge->fAbove.fY < fAbove.fY) { 1704 t1 = (edge->fTangent.fY - edge->fAbove.fY) * (fAbove.fX - edge->fAbove.fX); 1705 t2 = (fAbove.fY - edge->fAbove.fY) * (edge->fTangent.fX - edge->fAbove.fX); 1706 } else if (edge->fAbove.fY > fAbove.fY) { 1707 t1 = (fTangent.fY - fAbove.fY) * (fAbove.fX - edge->fAbove.fX); 1708 t2 = (fAbove.fY - edge->fAbove.fY) * (fTangent.fX - fAbove.fX); 1709 } else { 1710 t1 = fAbove.fX; 1711 t2 = edge->fAbove.fX; 1712 } 1713 if (edge->fTangent.fY > fTangent.fY) { 1714 b1 = (edge->fTangent.fY - edge->fAbove.fY) * (fTangent.fX - edge->fTangent.fX); 1715 b2 = (fTangent.fY - edge->fTangent.fY) * (edge->fTangent.fX - edge->fAbove.fX); 1716 } else if (edge->fTangent.fY < fTangent.fY) { 1717 b1 = (fTangent.fY - fAbove.fY) * (fTangent.fX - edge->fTangent.fX); 1718 b2 = (fTangent.fY - edge->fTangent.fY) * (fTangent.fX - fAbove.fX); 1719 } else { 1720 b1 = fTangent.fX; 1721 b2 = edge->fTangent.fX; 1722 } 1723 if (fabs(t1 - t2) > fabs(b1 - b2)) { 1724 ulps = UlpsDiff((float) t1, (float) t2); 1725 } else { 1726 ulps = UlpsDiff((float) b1, (float) b2); 1727 } 1728#if DEBUG_ADJUST_COINCIDENT 1729 SkDebugf("%s this=%d edge=%d ulps=%d\n", __FUNCTION__, ID(), edge->ID(), 1730 ulps); 1731#endif 1732 if (ulps < 0 || ulps > 32) { 1733 return false; 1734 } 1735 if (fVerb == SkPath::kLine_Verb && edge->fVerb == SkPath::kLine_Verb) { 1736 return true; 1737 } 1738 if (fVerb != SkPath::kLine_Verb && edge->fVerb != SkPath::kLine_Verb) { 1739 return false; 1740 } 1741 1742 double ts[2]; 1743 bool isLine = true; 1744 bool curveQuad = true; 1745 if (fVerb == SkPath::kCubic_Verb) { 1746 ts[0] = (fTAbove * 2 + fTBelow) / 3; 1747 ts[1] = (fTAbove + fTBelow * 2) / 3; 1748 curveQuad = isLine = false; 1749 } else if (edge->fVerb == SkPath::kCubic_Verb) { 1750 ts[0] = (edge->fTAbove * 2 + edge->fTBelow) / 3; 1751 ts[1] = (edge->fTAbove + edge->fTBelow * 2) / 3; 1752 curveQuad = false; 1753 } else if (fVerb == SkPath::kQuad_Verb) { 1754 ts[0] = fTAbove; 1755 ts[1] = (fTAbove + fTBelow) / 2; 1756 isLine = false; 1757 } else { 1758 SkASSERT(edge->fVerb == SkPath::kQuad_Verb); 1759 ts[0] = edge->fTAbove; 1760 ts[1] = (edge->fTAbove + edge->fTBelow) / 2; 1761 } 1762 const SkPoint* curvePts = isLine ? edge->lastPoints() : lastPoints(); 1763 const ActiveEdge* lineEdge = isLine ? this : edge; 1764 SkPoint curveSample[2]; 1765 for (int index = 0; index < 2; ++index) { 1766 if (curveQuad) { 1767 QuadXYAtT(curvePts, ts[index], &curveSample[index]); 1768 } else { 1769 CubicXYAtT(curvePts, ts[index], &curveSample[index]); 1770 } 1771 } 1772 return IsCoincident(curveSample, lineEdge->fAbove, lineEdge->fBelow); 1773 } 1774 1775 double nextT() const { 1776 SkASSERT(fTIndex <= fTs->count() - fExplicitTs); 1777 return t(fTIndex + 1); 1778 } 1779 1780 double t() const { 1781 return t(fTIndex); 1782 } 1783 1784 double t(int tIndex) const { 1785 if (fExplicitTs) { 1786 SkASSERT(tIndex < fTs->count()); 1787 return (*fTs)[tIndex]; 1788 } 1789 if (tIndex == 0) { 1790 return 0; 1791 } 1792 if (tIndex > fTs->count()) { 1793 return 1; 1794 } 1795 return (*fTs)[tIndex - 1]; 1796 } 1797 1798 // FIXME: debugging only 1799 int ID() const { 1800 return fWorkEdge.fEdge->fID; 1801 } 1802 1803private: 1804 // utility used only by swapUnordered 1805 void extractAboveBelow(ActiveEdge& extracted) const { 1806 SkPoint curve[4]; 1807 switch (fVerb) { 1808 case SkPath::kLine_Verb: 1809 extracted.fAbove = fAbove; 1810 extracted.fTangent = fTangent; 1811 return; 1812 case SkPath::kQuad_Verb: 1813 QuadSubDivide(lastPoints(), fTAbove, fTBelow, curve); 1814 break; 1815 case SkPath::kCubic_Verb: 1816 CubicSubDivide(lastPoints(), fTAbove, fTBelow, curve); 1817 break; 1818 default: 1819 SkASSERT(0); 1820 } 1821 extracted.fAbove = curve[0]; 1822 extracted.fTangent = curve[1]; 1823 } 1824 1825public: 1826 WorkEdge fWorkEdge; 1827 const SkTDArray<double>* fTs; 1828 SkPoint fAbove; 1829 SkPoint fTangent; 1830 SkPoint fBelow; 1831 double fTAbove; // OPTIMIZATION: only required if edge has quads or cubics 1832 double fTBelow; 1833 SkScalar fYBottom; 1834 int fCoincident; 1835 int fTIndex; 1836 SkPath::Verb fVerb; 1837 bool fSkip; // OPTIMIZATION: use bitfields? 1838 bool fCloseCall; 1839 bool fDone; 1840 bool fFixBelow; 1841 bool fExplicitTs; 1842}; 1843 1844static void addToActive(SkTDArray<ActiveEdge>& activeEdges, const InEdge* edge) { 1845 size_t count = activeEdges.count(); 1846 for (size_t index = 0; index < count; ++index) { 1847 if (edge == activeEdges[index].fWorkEdge.fEdge) { 1848 return; 1849 } 1850 } 1851 ActiveEdge* active = activeEdges.append(); 1852 active->init(edge); 1853} 1854 1855// Find any intersections in the range of active edges. A pair of edges, on 1856// either side of another edge, may change the winding contribution for part of 1857// the edge. 1858// Keep horizontal edges just for 1859// the purpose of computing when edges change their winding contribution, since 1860// this is essentially computing the horizontal intersection. 1861static void addBottomT(InEdge** currentPtr, InEdge** lastPtr, 1862 HorizontalEdge** horizontal) { 1863 InEdge** testPtr = currentPtr - 1; 1864 HorizontalEdge* horzEdge = *horizontal; 1865 SkScalar left = horzEdge->fLeft; 1866 SkScalar bottom = horzEdge->fY; 1867 while (++testPtr != lastPtr) { 1868 InEdge* test = *testPtr; 1869 if (test->fBounds.fBottom <= bottom || test->fBounds.fRight <= left) { 1870 continue; 1871 } 1872 WorkEdge wt; 1873 wt.init(test); 1874 do { 1875 HorizontalEdge** sorted = horizontal; 1876 horzEdge = *sorted; 1877 do { 1878 double wtTs[4]; 1879 int pts; 1880 uint8_t verb = wt.verb(); 1881 switch (verb) { 1882 case SkPath::kLine_Verb: 1883 pts = LineIntersect(wt.fPts, horzEdge->fLeft, 1884 horzEdge->fRight, horzEdge->fY, wtTs); 1885 break; 1886 case SkPath::kQuad_Verb: 1887 pts = QuadIntersect(wt.fPts, horzEdge->fLeft, 1888 horzEdge->fRight, horzEdge->fY, wtTs); 1889 break; 1890 case SkPath::kCubic_Verb: 1891 pts = CubicIntersect(wt.fPts, horzEdge->fLeft, 1892 horzEdge->fRight, horzEdge->fY, wtTs); 1893 break; 1894 } 1895 if (pts) { 1896#if DEBUG_ADD_BOTTOM_TS 1897 for (int x = 0; x < pts; ++x) { 1898 SkDebugf("%s y=%g wtTs[0]=%g (%g,%g", __FUNCTION__, 1899 horzEdge->fY, wtTs[x], wt.fPts[0].fX, wt.fPts[0].fY); 1900 for (int y = 0; y < verb; ++y) { 1901 SkDebugf(" %g,%g", wt.fPts[y + 1].fX, wt.fPts[y + 1].fY)); 1902 } 1903 SkDebugf(")\n"); 1904 } 1905 if (pts > verb) { 1906 SkASSERT(0); // FIXME ? should this work? 1907 SkDebugf("%s wtTs[1]=%g\n", __FUNCTION__, wtTs[1]); 1908 } 1909#endif 1910 test->add(wtTs, pts, wt.verbIndex()); 1911 } 1912 horzEdge = *++sorted; 1913 } while (horzEdge->fY == bottom 1914 && horzEdge->fLeft <= test->fBounds.fRight); 1915 } while (wt.advance()); 1916 } 1917} 1918 1919#if DEBUG_ADD_INTERSECTING_TS 1920static void debugShowLineIntersection(int pts, const WorkEdge& wt, 1921 const WorkEdge& wn, const double wtTs[2], const double wnTs[2]) { 1922 if (!pts) { 1923 return; 1924 } 1925 SkPoint wtOutPt, wnOutPt; 1926 LineXYAtT(wt.fPts, wtTs[0], &wtOutPt); 1927 LineXYAtT(wn.fPts, wnTs[0], &wnOutPt); 1928 SkDebugf("%s wtTs[0]=%g (%g,%g, %g,%g) (%g,%g)\n", 1929 __FUNCTION__, 1930 wtTs[0], wt.fPts[0].fX, wt.fPts[0].fY, 1931 wt.fPts[1].fX, wt.fPts[1].fY, wtOutPt.fX, wtOutPt.fY); 1932 if (pts == 2) { 1933 SkDebugf("%s wtTs[1]=%g\n", __FUNCTION__, wtTs[1]); 1934 } 1935 SkDebugf("%s wnTs[0]=%g (%g,%g, %g,%g) (%g,%g)\n", 1936 __FUNCTION__, 1937 wnTs[0], wn.fPts[0].fX, wn.fPts[0].fY, 1938 wn.fPts[1].fX, wn.fPts[1].fY, wnOutPt.fX, wnOutPt.fY); 1939 if (pts == 2) { 1940 SkDebugf("%s wnTs[1]=%g\n", __FUNCTION__, wnTs[1]); 1941 } 1942} 1943#else 1944static void debugShowLineIntersection(int , const WorkEdge& , 1945 const WorkEdge& , const double [2], const double [2]) { 1946} 1947#endif 1948 1949static void addIntersectingTs(InEdge** currentPtr, InEdge** lastPtr) { 1950 InEdge** testPtr = currentPtr - 1; 1951 // FIXME: lastPtr should be past the point of interest, so 1952 // test below should be lastPtr - 2 1953 // that breaks testSimplifyTriangle22, so further investigation is needed 1954 while (++testPtr != lastPtr - 1) { 1955 InEdge* test = *testPtr; 1956 InEdge** nextPtr = testPtr; 1957 do { 1958 InEdge* next = *++nextPtr; 1959 // FIXME: this compares against the sentinel sometimes 1960 // OPTIMIZATION: this may never be needed since this gets called 1961 // in two passes now. Verify that double hits are appropriate. 1962 if (test->cached(next)) { 1963 continue; 1964 } 1965 if (!Bounds::Intersects(test->fBounds, next->fBounds)) { 1966 continue; 1967 } 1968 WorkEdge wt, wn; 1969 wt.init(test); 1970 wn.init(next); 1971 do { 1972 int pts; 1973 Intersections ts; 1974 bool swap = false; 1975 switch (wt.verb()) { 1976 case SkPath::kLine_Verb: 1977 switch (wn.verb()) { 1978 case SkPath::kLine_Verb: { 1979 pts = LineIntersect(wt.fPts, wn.fPts, ts); 1980 debugShowLineIntersection(pts, wt, wn, 1981 ts.fT[0], ts.fT[1]); 1982 break; 1983 } 1984 case SkPath::kQuad_Verb: { 1985 swap = true; 1986 pts = QuadLineIntersect(wn.fPts, wt.fPts, ts); 1987 break; 1988 } 1989 case SkPath::kCubic_Verb: { 1990 swap = true; 1991 pts = CubicLineIntersect(wn.fPts, wt.fPts, ts); 1992 break; 1993 } 1994 default: 1995 SkASSERT(0); 1996 } 1997 break; 1998 case SkPath::kQuad_Verb: 1999 switch (wn.verb()) { 2000 case SkPath::kLine_Verb: { 2001 pts = QuadLineIntersect(wt.fPts, wn.fPts, ts); 2002 break; 2003 } 2004 case SkPath::kQuad_Verb: { 2005 pts = QuadIntersect(wt.fPts, wn.fPts, ts); 2006 break; 2007 } 2008 case SkPath::kCubic_Verb: { 2009 // FIXME: promote quad to cubic 2010 pts = CubicIntersect(wt.fPts, wn.fPts, ts); 2011 break; 2012 } 2013 default: 2014 SkASSERT(0); 2015 } 2016 break; 2017 case SkPath::kCubic_Verb: 2018 switch (wn.verb()) { 2019 case SkPath::kLine_Verb: { 2020 pts = CubicLineIntersect(wt.fPts, wn.fPts, ts); 2021 break; 2022 } 2023 case SkPath::kQuad_Verb: { 2024 // FIXME: promote quad to cubic 2025 pts = CubicIntersect(wt.fPts, wn.fPts, ts); 2026 break; 2027 } 2028 case SkPath::kCubic_Verb: { 2029 pts = CubicIntersect(wt.fPts, wn.fPts, ts); 2030 break; 2031 } 2032 default: 2033 SkASSERT(0); 2034 } 2035 break; 2036 default: 2037 SkASSERT(0); 2038 } 2039 test->add(ts.fT[swap], pts, wt.verbIndex()); 2040 next->add(ts.fT[!swap], pts, wn.verbIndex()); 2041 } while (wt.bottom() <= wn.bottom() ? wt.advance() : wn.advance()); 2042 } while (nextPtr != lastPtr); 2043 } 2044} 2045 2046static InEdge** advanceEdges(SkTDArray<ActiveEdge>* activeEdges, 2047 InEdge** currentPtr, InEdge** lastPtr, SkScalar y) { 2048 InEdge** testPtr = currentPtr - 1; 2049 while (++testPtr != lastPtr) { 2050 if ((*testPtr)->fBounds.fBottom > y) { 2051 continue; 2052 } 2053 if (activeEdges) { 2054 InEdge* test = *testPtr; 2055 ActiveEdge* activePtr = activeEdges->begin() - 1; 2056 ActiveEdge* lastActive = activeEdges->end(); 2057 while (++activePtr != lastActive) { 2058 if (activePtr->fWorkEdge.fEdge == test) { 2059 activeEdges->remove(activePtr - activeEdges->begin()); 2060 break; 2061 } 2062 } 2063 } 2064 if (testPtr == currentPtr) { 2065 ++currentPtr; 2066 } 2067 } 2068 return currentPtr; 2069} 2070 2071// OPTIMIZE: inline? 2072static HorizontalEdge** advanceHorizontal(HorizontalEdge** edge, SkScalar y) { 2073 while ((*edge)->fY < y) { 2074 ++edge; 2075 } 2076 return edge; 2077} 2078 2079// compute bottom taking into account any intersected edges 2080static SkScalar computeInterceptBottom(SkTDArray<ActiveEdge>& activeEdges, 2081 SkScalar y, SkScalar bottom) { 2082 ActiveEdge* activePtr = activeEdges.begin() - 1; 2083 ActiveEdge* lastActive = activeEdges.end(); 2084 while (++activePtr != lastActive) { 2085 const InEdge* test = activePtr->fWorkEdge.fEdge; 2086 if (!test->fContainsIntercepts) { 2087 continue; 2088 } 2089 WorkEdge wt; 2090 wt.init(test); 2091 do { 2092 const Intercepts& intercepts = test->fIntercepts[wt.verbIndex()]; 2093 if (intercepts.fTopIntercepts > 1) { 2094 SkScalar yTop = wt.fPts[0].fY; 2095 if (yTop > y && bottom > yTop) { 2096 bottom = yTop; 2097 } 2098 } 2099 if (intercepts.fBottomIntercepts > 1) { 2100 SkScalar yBottom = wt.fPts[wt.verb()].fY; 2101 if (yBottom > y && bottom > yBottom) { 2102 bottom = yBottom; 2103 } 2104 } 2105 const SkTDArray<double>& fTs = intercepts.fTs; 2106 size_t count = fTs.count(); 2107 for (size_t index = 0; index < count; ++index) { 2108 SkScalar yIntercept; 2109 switch (wt.verb()) { 2110 case SkPath::kLine_Verb: { 2111 yIntercept = LineYAtT(wt.fPts, fTs[index]); 2112 break; 2113 } 2114 case SkPath::kQuad_Verb: { 2115 yIntercept = QuadYAtT(wt.fPts, fTs[index]); 2116 break; 2117 } 2118 case SkPath::kCubic_Verb: { 2119 yIntercept = CubicYAtT(wt.fPts, fTs[index]); 2120 break; 2121 } 2122 default: 2123 SkASSERT(0); // should never get here 2124 } 2125 if (yIntercept > y && bottom > yIntercept) { 2126 bottom = yIntercept; 2127 } 2128 } 2129 } while (wt.advance()); 2130 } 2131#if DEBUG_BOTTOM 2132 SkDebugf("%s bottom=%1.9g\n", __FUNCTION__, bottom); 2133#endif 2134 return bottom; 2135} 2136 2137static SkScalar findBottom(InEdge** currentPtr, 2138 InEdge** edgeListEnd, SkTDArray<ActiveEdge>* activeEdges, SkScalar y, 2139 bool /*asFill*/, InEdge**& testPtr) { 2140 InEdge* current = *currentPtr; 2141 SkScalar bottom = current->fBounds.fBottom; 2142 2143 // find the list of edges that cross y 2144 InEdge* test = *testPtr; 2145 while (testPtr != edgeListEnd) { 2146 SkScalar testTop = test->fBounds.fTop; 2147 if (bottom <= testTop) { 2148 break; 2149 } 2150 SkScalar testBottom = test->fBounds.fBottom; 2151 // OPTIMIZATION: Shortening the bottom is only interesting when filling 2152 // and when the edge is to the left of a longer edge. If it's a framing 2153 // edge, or part of the right, it won't effect the longer edges. 2154 if (testTop > y) { 2155 bottom = testTop; 2156 break; 2157 } 2158 if (y < testBottom) { 2159 if (bottom > testBottom) { 2160 bottom = testBottom; 2161 } 2162 if (activeEdges) { 2163 addToActive(*activeEdges, test); 2164 } 2165 } 2166 test = *++testPtr; 2167 } 2168#if DEBUG_BOTTOM 2169 SkDebugf("%s %d bottom=%1.9g\n", __FUNCTION__, activeEdges ? 2 : 1, bottom); 2170#endif 2171 return bottom; 2172} 2173 2174static void makeEdgeList(SkTArray<InEdge>& edges, InEdge& edgeSentinel, 2175 SkTDArray<InEdge*>& edgeList) { 2176 size_t edgeCount = edges.count(); 2177 if (edgeCount == 0) { 2178 return; 2179 } 2180 int id = 0; 2181 for (size_t index = 0; index < edgeCount; ++index) { 2182 InEdge& edge = edges[index]; 2183 if (!edge.fWinding) { 2184 continue; 2185 } 2186 edge.fID = ++id; 2187 *edgeList.append() = &edge; 2188 } 2189 *edgeList.append() = &edgeSentinel; 2190 QSort<InEdge>(edgeList.begin(), edgeList.end() - 1); 2191} 2192 2193static void makeHorizontalList(SkTDArray<HorizontalEdge>& edges, 2194 HorizontalEdge& edgeSentinel, SkTDArray<HorizontalEdge*>& edgeList) { 2195 size_t edgeCount = edges.count(); 2196 if (edgeCount == 0) { 2197 return; 2198 } 2199 for (size_t index = 0; index < edgeCount; ++index) { 2200 *edgeList.append() = &edges[index]; 2201 } 2202 edgeSentinel.fLeft = edgeSentinel.fRight = edgeSentinel.fY = SK_ScalarMax; 2203 *edgeList.append() = &edgeSentinel; 2204 QSort<HorizontalEdge>(edgeList.begin(), edgeList.end() - 1); 2205} 2206 2207static void skipCoincidence(int lastWinding, int winding, int windingMask, 2208 ActiveEdge* activePtr, ActiveEdge* firstCoincident) { 2209 if (((lastWinding & windingMask) == 0) ^ ((winding & windingMask) != 0)) { 2210 return; 2211 } 2212 // FIXME: ? shouldn't this be if (lastWinding & windingMask) ? 2213 if (lastWinding) { 2214#if DEBUG_ADJUST_COINCIDENT 2215 SkDebugf("%s edge=%d 1 set skip=false\n", __FUNCTION__, activePtr->ID()); 2216#endif 2217 activePtr->fSkip = false; 2218 } else { 2219#if DEBUG_ADJUST_COINCIDENT 2220 SkDebugf("%s edge=%d 2 set skip=false\n", __FUNCTION__, firstCoincident->ID()); 2221#endif 2222 firstCoincident->fSkip = false; 2223 } 2224} 2225 2226static void sortHorizontal(SkTDArray<ActiveEdge>& activeEdges, 2227 SkTDArray<ActiveEdge*>& edgeList, SkScalar y) { 2228 size_t edgeCount = activeEdges.count(); 2229 if (edgeCount == 0) { 2230 return; 2231 } 2232#if DEBUG_SORT_HORIZONTAL 2233 const int tab = 3; // FIXME: debugging only 2234 SkDebugf("%s y=%1.9g\n", __FUNCTION__, y); 2235#endif 2236 size_t index; 2237 for (index = 0; index < edgeCount; ++index) { 2238 ActiveEdge& activeEdge = activeEdges[index]; 2239 do { 2240 activeEdge.calcLeft(y); 2241 // skip segments that don't span y 2242 if (activeEdge.fAbove != activeEdge.fBelow) { 2243 break; 2244 } 2245 if (activeEdge.fDone) { 2246#if DEBUG_SORT_HORIZONTAL 2247 SkDebugf("%*s edge=%d done\n", tab, "", activeEdge.ID()); 2248#endif 2249 goto nextEdge; 2250 } 2251#if DEBUG_SORT_HORIZONTAL 2252 SkDebugf("%*s edge=%d above==below\n", tab, "", activeEdge.ID()); 2253#endif 2254 } while (activeEdge.advanceT() || activeEdge.advance()); 2255#if DEBUG_SORT_HORIZONTAL 2256 SkDebugf("%*s edge=%d above=(%1.9g,%1.9g) (%1.9g) below=(%1.9g,%1.9g)" 2257 " (%1.9g)\n", tab, "", activeEdge.ID(), 2258 activeEdge.fAbove.fX, activeEdge.fAbove.fY, activeEdge.fTAbove, 2259 activeEdge.fBelow.fX, activeEdge.fBelow.fY, activeEdge.fTBelow); 2260#endif 2261 activeEdge.fSkip = activeEdge.fCloseCall = activeEdge.fFixBelow = false; 2262 *edgeList.append() = &activeEdge; 2263nextEdge: 2264 ; 2265 } 2266 QSort<ActiveEdge>(edgeList.begin(), edgeList.end() - 1); 2267} 2268 2269// remove coincident edges 2270// OPTIMIZE: remove edges? This is tricky because the current logic expects 2271// the winding count to be maintained while skipping coincident edges. In 2272// addition to removing the coincident edges, the remaining edges would need 2273// to have a different winding value, possibly different per intercept span. 2274static SkScalar adjustCoincident(SkTDArray<ActiveEdge*>& edgeList, 2275 int windingMask, SkScalar y, SkScalar bottom, OutEdgeBuilder& outBuilder) 2276{ 2277#if DEBUG_ADJUST_COINCIDENT 2278 SkDebugf("%s y=%1.9g bottom=%1.9g\n", __FUNCTION__, y, bottom); 2279#endif 2280 size_t edgeCount = edgeList.count(); 2281 if (edgeCount == 0) { 2282 return bottom; 2283 } 2284 ActiveEdge* activePtr, * nextPtr = edgeList[0]; 2285 size_t index; 2286 bool foundCoincident = false; 2287 size_t firstIndex = 0; 2288 for (index = 1; index < edgeCount; ++index) { 2289 activePtr = nextPtr; 2290 nextPtr = edgeList[index]; 2291 if (firstIndex != index - 1 && activePtr->fVerb > SkPath::kLine_Verb 2292 && nextPtr->fVerb == SkPath::kLine_Verb 2293 && activePtr->isUnordered(nextPtr)) { 2294 // swap the line with the curve 2295 // back up to the previous edge and retest 2296 SkTSwap<ActiveEdge*>(edgeList[index - 1], edgeList[index]); 2297 SkASSERT(index > 1); 2298 index -= 2; 2299 nextPtr = edgeList[index]; 2300 continue; 2301 } 2302 bool closeCall = false; 2303 activePtr->fCoincident = firstIndex; 2304 if (activePtr->isCoincidentWith(nextPtr) 2305 || (closeCall = activePtr->tooCloseToCall(nextPtr))) { 2306 activePtr->fSkip = nextPtr->fSkip = foundCoincident = true; 2307 activePtr->fCloseCall = nextPtr->fCloseCall = closeCall; 2308 } else if (activePtr->isUnordered(nextPtr)) { 2309 foundCoincident = true; 2310 } else { 2311 firstIndex = index; 2312 } 2313 } 2314 nextPtr->fCoincident = firstIndex; 2315 if (!foundCoincident) { 2316 return bottom; 2317 } 2318 int winding = 0; 2319 nextPtr = edgeList[0]; 2320 for (index = 1; index < edgeCount; ++index) { 2321 int priorWinding = winding; 2322 winding += activePtr->fWorkEdge.winding(); 2323 activePtr = nextPtr; 2324 nextPtr = edgeList[index]; 2325 SkASSERT(activePtr == edgeList[index - 1]); 2326 SkASSERT(nextPtr == edgeList[index]); 2327 if (activePtr->fCoincident != nextPtr->fCoincident) { 2328 continue; 2329 } 2330 // the coincident edges may not have been sorted above -- advance 2331 // the edges and resort if needed 2332 // OPTIMIZE: if sorting is done incrementally as new edges are added 2333 // and not all at once as is done here, fold this test into the 2334 // current less than test. 2335 while ((!activePtr->fSkip || !nextPtr->fSkip) 2336 && activePtr->fCoincident == nextPtr->fCoincident) { 2337 if (activePtr->swapUnordered(nextPtr, bottom)) { 2338 winding -= activePtr->fWorkEdge.winding(); 2339 SkASSERT(activePtr == edgeList[index - 1]); 2340 SkASSERT(nextPtr == edgeList[index]); 2341 SkTSwap<ActiveEdge*>(edgeList[index - 1], edgeList[index]); 2342 if (--index == 0) { 2343 winding += activePtr->fWorkEdge.winding(); 2344 break; 2345 } 2346 // back up one 2347 activePtr = edgeList[index - 1]; 2348 continue; 2349 } 2350 SkASSERT(activePtr == edgeList[index - 1]); 2351 SkASSERT(nextPtr == edgeList[index]); 2352 break; 2353 } 2354 if (activePtr->fSkip && nextPtr->fSkip) { 2355 if (activePtr->fCloseCall ? activePtr->swapClose(nextPtr, 2356 priorWinding, winding, windingMask) 2357 : activePtr->swapCoincident(nextPtr, bottom)) { 2358 winding -= activePtr->fWorkEdge.winding(); 2359 SkASSERT(activePtr == edgeList[index - 1]); 2360 SkASSERT(nextPtr == edgeList[index]); 2361 SkTSwap<ActiveEdge*>(edgeList[index - 1], edgeList[index]); 2362 SkTSwap<ActiveEdge*>(activePtr, nextPtr); 2363 winding += activePtr->fWorkEdge.winding(); 2364 SkASSERT(activePtr == edgeList[index - 1]); 2365 SkASSERT(nextPtr == edgeList[index]); 2366 } 2367 } 2368 } 2369 int firstCoincidentWinding = 0; 2370 ActiveEdge* firstCoincident = NULL; 2371 winding = 0; 2372 activePtr = edgeList[0]; 2373 for (index = 1; index < edgeCount; ++index) { 2374 int priorWinding = winding; 2375 winding += activePtr->fWorkEdge.winding(); 2376 nextPtr = edgeList[index]; 2377 if (activePtr->fSkip && nextPtr->fSkip 2378 && activePtr->fCoincident == nextPtr->fCoincident) { 2379 if (!firstCoincident) { 2380 firstCoincident = activePtr; 2381 firstCoincidentWinding = priorWinding; 2382 } 2383 if (activePtr->fCloseCall) { 2384 // If one of the edges has already been added to out as a non 2385 // coincident edge, trim it back to the top of this span 2386 if (outBuilder.trimLine(y, activePtr->ID())) { 2387 activePtr->addTatYAbove(y); 2388 #if DEBUG_ADJUST_COINCIDENT 2389 SkDebugf("%s 1 edge=%d y=%1.9g (was fYBottom=%1.9g)\n", 2390 __FUNCTION__, activePtr->ID(), y, activePtr->fYBottom); 2391 #endif 2392 activePtr->fYBottom = y; 2393 } 2394 if (outBuilder.trimLine(y, nextPtr->ID())) { 2395 nextPtr->addTatYAbove(y); 2396 #if DEBUG_ADJUST_COINCIDENT 2397 SkDebugf("%s 2 edge=%d y=%1.9g (was fYBottom=%1.9g)\n", 2398 __FUNCTION__, nextPtr->ID(), y, nextPtr->fYBottom); 2399 #endif 2400 nextPtr->fYBottom = y; 2401 } 2402 // add missing t values so edges can be the same length 2403 SkScalar testY = activePtr->fBelow.fY; 2404 nextPtr->addTatYBelow(testY); 2405 if (bottom > testY && testY > y) { 2406 #if DEBUG_ADJUST_COINCIDENT 2407 SkDebugf("%s 3 edge=%d bottom=%1.9g (was bottom=%1.9g)\n", 2408 __FUNCTION__, activePtr->ID(), testY, bottom); 2409 #endif 2410 bottom = testY; 2411 } 2412 testY = nextPtr->fBelow.fY; 2413 activePtr->addTatYBelow(testY); 2414 if (bottom > testY && testY > y) { 2415 #if DEBUG_ADJUST_COINCIDENT 2416 SkDebugf("%s 4 edge=%d bottom=%1.9g (was bottom=%1.9g)\n", 2417 __FUNCTION__, nextPtr->ID(), testY, bottom); 2418 #endif 2419 bottom = testY; 2420 } 2421 } 2422 } else if (firstCoincident) { 2423 skipCoincidence(firstCoincidentWinding, winding, windingMask, 2424 activePtr, firstCoincident); 2425 firstCoincident = NULL; 2426 } 2427 activePtr = nextPtr; 2428 } 2429 if (firstCoincident) { 2430 winding += activePtr->fWorkEdge.winding(); 2431 skipCoincidence(firstCoincidentWinding, winding, windingMask, activePtr, 2432 firstCoincident); 2433 } 2434 // fix up the bottom for close call edges. OPTIMIZATION: maybe this could 2435 // be in the loop above, but moved here since loop above reads fBelow and 2436 // it felt unsafe to write it in that loop 2437 for (index = 0; index < edgeCount; ++index) { 2438 (edgeList[index])->fixBelow(); 2439 } 2440 return bottom; 2441} 2442 2443// stitch edge and t range that satisfies operation 2444static void stitchEdge(SkTDArray<ActiveEdge*>& edgeList, SkScalar 2445#if DEBUG_STITCH_EDGE 2446y 2447#endif 2448, 2449 SkScalar bottom, int windingMask, bool fill, OutEdgeBuilder& outBuilder) { 2450 int winding = 0; 2451 ActiveEdge** activeHandle = edgeList.begin() - 1; 2452 ActiveEdge** lastActive = edgeList.end(); 2453#if DEBUG_STITCH_EDGE 2454 const int tab = 7; // FIXME: debugging only 2455 SkDebugf("%s y=%1.9g bottom=%1.9g\n", __FUNCTION__, y, bottom); 2456#endif 2457 while (++activeHandle != lastActive) { 2458 ActiveEdge* activePtr = *activeHandle; 2459 const WorkEdge& wt = activePtr->fWorkEdge; 2460 int lastWinding = winding; 2461 winding += wt.winding(); 2462#if DEBUG_STITCH_EDGE 2463 SkDebugf("%*s edge=%d lastWinding=%d winding=%d skip=%d close=%d" 2464 " above=%1.9g below=%1.9g\n", 2465 tab-4, "", activePtr->ID(), lastWinding, 2466 winding, activePtr->fSkip, activePtr->fCloseCall, 2467 activePtr->fTAbove, activePtr->fTBelow); 2468#endif 2469 if (activePtr->done(bottom)) { 2470#if DEBUG_STITCH_EDGE 2471 SkDebugf("%*s fDone=%d || fYBottom=%1.9g >= bottom\n", tab, "", 2472 activePtr->fDone, activePtr->fYBottom); 2473#endif 2474 continue; 2475 } 2476 int opener = (lastWinding & windingMask) == 0; 2477 bool closer = (winding & windingMask) == 0; 2478 SkASSERT(!opener | !closer); 2479 bool inWinding = opener | closer; 2480 SkPoint clippedPts[4]; 2481 const SkPoint* clipped = NULL; 2482 bool moreToDo, aboveBottom; 2483 do { 2484 double currentT = activePtr->t(); 2485 const SkPoint* points = wt.fPts; 2486 double nextT; 2487 SkPath::Verb verb = activePtr->fVerb; 2488 do { 2489 nextT = activePtr->nextT(); 2490 // FIXME: obtuse: want efficient way to say 2491 // !currentT && currentT != 1 || !nextT && nextT != 1 2492 if (currentT * nextT != 0 || currentT + nextT != 1) { 2493 // OPTIMIZATION: if !inWinding, we only need 2494 // clipped[1].fY 2495 switch (verb) { 2496 case SkPath::kLine_Verb: 2497 LineSubDivide(points, currentT, nextT, clippedPts); 2498 break; 2499 case SkPath::kQuad_Verb: 2500 QuadSubDivide(points, currentT, nextT, clippedPts); 2501 break; 2502 case SkPath::kCubic_Verb: 2503 CubicSubDivide(points, currentT, nextT, clippedPts); 2504 break; 2505 default: 2506 SkASSERT(0); 2507 break; 2508 } 2509 clipped = clippedPts; 2510 } else { 2511 clipped = points; 2512 } 2513 if (inWinding && !activePtr->fSkip && (fill ? clipped[0].fY 2514 != clipped[verb].fY : clipped[0] != clipped[verb])) { 2515#if DEBUG_STITCH_EDGE 2516 SkDebugf("%*s add%s %1.9g,%1.9g %1.9g,%1.9g edge=%d" 2517 " v=%d t=(%1.9g,%1.9g)\n", tab, "", 2518 kUVerbStr[verb], clipped[0].fX, clipped[0].fY, 2519 clipped[verb].fX, clipped[verb].fY, 2520 activePtr->ID(), 2521 activePtr->fWorkEdge.fVerb 2522 - activePtr->fWorkEdge.fEdge->fVerbs.begin(), 2523 currentT, nextT); 2524#endif 2525 outBuilder.addCurve(clipped, (SkPath::Verb) verb, 2526 activePtr->fWorkEdge.fEdge->fID, 2527 activePtr->fCloseCall); 2528 } else { 2529#if DEBUG_STITCH_EDGE 2530 SkDebugf("%*s skip%s %1.9g,%1.9g %1.9g,%1.9g" 2531 " edge=%d v=%d t=(%1.9g,%1.9g)\n", tab, "", 2532 kUVerbStr[verb], clipped[0].fX, clipped[0].fY, 2533 clipped[verb].fX, clipped[verb].fY, 2534 activePtr->ID(), 2535 activePtr->fWorkEdge.fVerb 2536 - activePtr->fWorkEdge.fEdge->fVerbs.begin(), 2537 currentT, nextT); 2538#endif 2539 } 2540 // by advancing fAbove/fBelow, the next call to sortHorizontal 2541 // will use these values if they're still valid instead of 2542 // recomputing 2543 if (clipped[verb].fY > activePtr->fBelow.fY 2544 && bottom >= activePtr->fBelow.fY 2545 && verb == SkPath::kLine_Verb) { 2546 activePtr->fAbove = activePtr->fBelow; 2547 activePtr->fBelow = activePtr->fTangent = clipped[verb]; 2548 activePtr->fTAbove = activePtr->fTBelow < 1 2549 ? activePtr->fTBelow : 0; 2550 activePtr->fTBelow = nextT; 2551 } 2552 currentT = nextT; 2553 moreToDo = activePtr->advanceT(); 2554 activePtr->fYBottom = clipped[verb].fY; // was activePtr->fCloseCall ? bottom : 2555 2556 // clearing the fSkip/fCloseCall bit here means that trailing edges 2557 // fall out of sync, if one edge is long and another is a series of short pieces 2558 // if fSkip/fCloseCall is set, need to recompute coincidence/too-close-to-call 2559 // after advancing 2560 // another approach would be to restrict bottom to smaller part of close call 2561 // maybe this is already happening with coincidence when intersection is computed, 2562 // and needs to be added to the close call computation as well 2563 // this is hard to do because that the bottom is important is not known when 2564 // the lines are intersected; only when the computation for edge sorting is done 2565 // does the need for new bottoms become apparent. 2566 // maybe this is good incentive to scrap the current sort and do an insertion 2567 // sort that can take this into consideration when the x value is computed 2568 2569 // FIXME: initialized in sortHorizontal, cleared here as well so 2570 // that next edge is not skipped -- but should skipped edges ever 2571 // continue? (probably not) 2572 aboveBottom = clipped[verb].fY < bottom; 2573 if (clipped[0].fY != clipped[verb].fY) { 2574 activePtr->fSkip = false; 2575 activePtr->fCloseCall = false; 2576 aboveBottom &= !activePtr->fCloseCall; 2577 } 2578#if DEBUG_STITCH_EDGE 2579 else { 2580 if (activePtr->fSkip || activePtr->fCloseCall) { 2581 SkDebugf("%s skip or close == %1.9g\n", __FUNCTION__, 2582 clippedPts[0].fY); 2583 } 2584 } 2585#endif 2586 } while (moreToDo & aboveBottom); 2587 } while ((moreToDo || activePtr->advance()) & aboveBottom); 2588 } 2589} 2590 2591#if DEBUG_DUMP 2592static void dumpEdgeList(const SkTDArray<InEdge*>& edgeList, 2593 const InEdge& edgeSentinel) { 2594 InEdge** debugPtr = edgeList.begin(); 2595 do { 2596 (*debugPtr++)->dump(); 2597 } while (*debugPtr != &edgeSentinel); 2598} 2599#else 2600static void dumpEdgeList(const SkTDArray<InEdge*>& , 2601 const InEdge& ) { 2602} 2603#endif 2604 2605void simplify(const SkPath& path, bool asFill, SkPath& simple) { 2606 // returns 1 for evenodd, -1 for winding, regardless of inverse-ness 2607 int windingMask = (path.getFillType() & 1) ? 1 : -1; 2608 simple.reset(); 2609 simple.setFillType(SkPath::kEvenOdd_FillType); 2610 // turn path into list of edges increasing in y 2611 // if an edge is a quad or a cubic with a y extrema, note it, but leave it 2612 // unbroken. Once we have a list, sort it, then walk the list (walk edges 2613 // twice that have y extrema's on top) and detect crossings -- look for raw 2614 // bounds that cross over, then tight bounds that cross 2615 SkTArray<InEdge> edges; 2616 SkTDArray<HorizontalEdge> horizontalEdges; 2617 InEdgeBuilder builder(path, asFill, edges, horizontalEdges); 2618 SkTDArray<InEdge*> edgeList; 2619 InEdge edgeSentinel; 2620 edgeSentinel.reset(); 2621 makeEdgeList(edges, edgeSentinel, edgeList); 2622 SkTDArray<HorizontalEdge*> horizontalList; 2623 HorizontalEdge horizontalSentinel; 2624 makeHorizontalList(horizontalEdges, horizontalSentinel, horizontalList); 2625 InEdge** currentPtr = edgeList.begin(); 2626 if (!currentPtr) { 2627 return; 2628 } 2629 // find all intersections between edges 2630// beyond looking for horizontal intercepts, we need to know if any active edges 2631// intersect edges below 'bottom', but above the active edge segment. 2632// maybe it makes more sense to compute all intercepts before doing anything 2633// else, since the intercept list is long-lived, at least in the current design. 2634 SkScalar y = (*currentPtr)->fBounds.fTop; 2635 HorizontalEdge** currentHorizontal = horizontalList.begin(); 2636 do { 2637 InEdge** lastPtr = currentPtr; // find the edge below the bottom of the first set 2638 SkScalar bottom = findBottom(currentPtr, edgeList.end(), 2639 NULL, y, asFill, lastPtr); 2640 if (lastPtr > currentPtr) { 2641 if (currentHorizontal) { 2642 if ((*currentHorizontal)->fY < SK_ScalarMax) { 2643 addBottomT(currentPtr, lastPtr, currentHorizontal); 2644 } 2645 currentHorizontal = advanceHorizontal(currentHorizontal, bottom); 2646 } 2647 addIntersectingTs(currentPtr, lastPtr); 2648 } 2649 y = bottom; 2650 currentPtr = advanceEdges(NULL, currentPtr, lastPtr, y); 2651 } while (*currentPtr != &edgeSentinel); 2652 // if a quadratic or cubic now has an intermediate T value, see if the Ts 2653 // on either side cause the Y values to monotonically increase. If not, split 2654 // the curve at the new T. 2655 2656 // try an alternate approach which does not split curves or stitch edges 2657 // (may still need adjustCoincident, though) 2658 // the idea is to output non-intersecting contours, then figure out their 2659 // respective winding contribution 2660 // each contour will need to know whether it is CW or CCW, and then whether 2661 // a ray from that contour hits any a contour that contains it. The ray can 2662 // move to the left and then arbitrarily move up or down (as long as it never 2663 // moves to the right) to find a reference sibling contour or containing 2664 // contour. If the contour is part of an intersection, the companion contour 2665 // that is part of the intersection can determine the containership. 2666 if (builder.containsCurves()) { 2667 currentPtr = edgeList.begin(); 2668 SkTArray<InEdge> splits; 2669 do { 2670 (*currentPtr)->splitInflectionPts(splits); 2671 } while (*++currentPtr != &edgeSentinel); 2672 if (splits.count()) { 2673 for (int index = 0; index < splits.count(); ++index) { 2674 edges.push_back(splits[index]); 2675 } 2676 edgeList.reset(); 2677 makeEdgeList(edges, edgeSentinel, edgeList); 2678 } 2679 } 2680 dumpEdgeList(edgeList, edgeSentinel); 2681 // walk the sorted edges from top to bottom, computing accumulated winding 2682 SkTDArray<ActiveEdge> activeEdges; 2683 OutEdgeBuilder outBuilder(asFill); 2684 currentPtr = edgeList.begin(); 2685 y = (*currentPtr)->fBounds.fTop; 2686 do { 2687 InEdge** lastPtr = currentPtr; // find the edge below the bottom of the first set 2688 SkScalar bottom = findBottom(currentPtr, edgeList.end(), 2689 &activeEdges, y, asFill, lastPtr); 2690 if (lastPtr > currentPtr) { 2691 bottom = computeInterceptBottom(activeEdges, y, bottom); 2692 SkTDArray<ActiveEdge*> activeEdgeList; 2693 sortHorizontal(activeEdges, activeEdgeList, y); 2694 bottom = adjustCoincident(activeEdgeList, windingMask, y, bottom, 2695 outBuilder); 2696 stitchEdge(activeEdgeList, y, bottom, windingMask, asFill, outBuilder); 2697 } 2698 y = bottom; 2699 // OPTIMIZATION: as edges expire, InEdge allocations could be released 2700 currentPtr = advanceEdges(&activeEdges, currentPtr, lastPtr, y); 2701 } while (*currentPtr != &edgeSentinel); 2702 // assemble output path from string of pts, verbs 2703 outBuilder.bridge(); 2704 outBuilder.assemble(simple); 2705} 2706