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