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