Simplify.cpp revision 044679ef8c08e1f01afadf5bc08251fe8597df81
161d9df3e62aaa0e87ad05452fcb95142159a17b6Dmitry Shmidt/* 261d9df3e62aaa0e87ad05452fcb95142159a17b6Dmitry Shmidt * Copyright 2012 Google Inc. 3a54fa5fb807eaeff45464139b5a7759f060cec68Dmitry Shmidt * 461d9df3e62aaa0e87ad05452fcb95142159a17b6Dmitry Shmidt * Use of this source code is governed by a BSD-style license that can be 561d9df3e62aaa0e87ad05452fcb95142159a17b6Dmitry Shmidt * found in the LICENSE file. 661d9df3e62aaa0e87ad05452fcb95142159a17b6Dmitry Shmidt */ 761d9df3e62aaa0e87ad05452fcb95142159a17b6Dmitry Shmidt#include "Simplify.h" 861d9df3e62aaa0e87ad05452fcb95142159a17b6Dmitry Shmidt 961d9df3e62aaa0e87ad05452fcb95142159a17b6Dmitry Shmidt#undef SkASSERT 1061d9df3e62aaa0e87ad05452fcb95142159a17b6Dmitry Shmidt#define SkASSERT(cond) while (!(cond)) { sk_throw(); } 1161d9df3e62aaa0e87ad05452fcb95142159a17b6Dmitry Shmidt 1261d9df3e62aaa0e87ad05452fcb95142159a17b6Dmitry Shmidt// Terminology: 1361d9df3e62aaa0e87ad05452fcb95142159a17b6Dmitry Shmidt// A Path contains one of more Contours 1461d9df3e62aaa0e87ad05452fcb95142159a17b6Dmitry Shmidt// A Contour is made up of Segment array 1561d9df3e62aaa0e87ad05452fcb95142159a17b6Dmitry Shmidt// A Segment is described by a Verb and a Point array with 2, 3, or 4 points 1661d9df3e62aaa0e87ad05452fcb95142159a17b6Dmitry Shmidt// A Verb is one of Line, Quad(ratic), or Cubic 1761d9df3e62aaa0e87ad05452fcb95142159a17b6Dmitry Shmidt// A Segment contains a Span array 1861d9df3e62aaa0e87ad05452fcb95142159a17b6Dmitry Shmidt// A Span is describes a portion of a Segment using starting and ending T 1961d9df3e62aaa0e87ad05452fcb95142159a17b6Dmitry Shmidt// T values range from 0 to 1, where 0 is the first Point in the Segment 2061d9df3e62aaa0e87ad05452fcb95142159a17b6Dmitry Shmidt// An Edge is a Segment generated from a Span 2161d9df3e62aaa0e87ad05452fcb95142159a17b6Dmitry Shmidt 2261d9df3e62aaa0e87ad05452fcb95142159a17b6Dmitry Shmidt// FIXME: remove once debugging is complete 2361d9df3e62aaa0e87ad05452fcb95142159a17b6Dmitry Shmidt#ifdef SK_DEBUG 2461d9df3e62aaa0e87ad05452fcb95142159a17b6Dmitry Shmidtint gDebugMaxWindSum = SK_MaxS32; 2561d9df3e62aaa0e87ad05452fcb95142159a17b6Dmitry Shmidtint gDebugMaxWindValue = SK_MaxS32; 2661d9df3e62aaa0e87ad05452fcb95142159a17b6Dmitry Shmidt#endif 2761d9df3e62aaa0e87ad05452fcb95142159a17b6Dmitry Shmidt 2861d9df3e62aaa0e87ad05452fcb95142159a17b6Dmitry Shmidt#define PIN_ADD_T 0 2961d9df3e62aaa0e87ad05452fcb95142159a17b6Dmitry Shmidt#define TRY_ROTATE 1 3061d9df3e62aaa0e87ad05452fcb95142159a17b6Dmitry Shmidt#define ONE_PASS_COINCIDENCE_CHECK 0 3161d9df3e62aaa0e87ad05452fcb95142159a17b6Dmitry Shmidt#define APPROXIMATE_CUBICS 1 32a54fa5fb807eaeff45464139b5a7759f060cec68Dmitry Shmidt 33a54fa5fb807eaeff45464139b5a7759f060cec68Dmitry Shmidt#define DEBUG_UNUSED 0 // set to expose unused functions 34a54fa5fb807eaeff45464139b5a7759f060cec68Dmitry Shmidt 35a54fa5fb807eaeff45464139b5a7759f060cec68Dmitry Shmidt#define FORCE_RELEASE 1 // set force release to 1 for multiple thread -- no debugging 36a54fa5fb807eaeff45464139b5a7759f060cec68Dmitry Shmidt 37a54fa5fb807eaeff45464139b5a7759f060cec68Dmitry Shmidt#if FORCE_RELEASE || defined SK_RELEASE 38a54fa5fb807eaeff45464139b5a7759f060cec68Dmitry Shmidt 39a54fa5fb807eaeff45464139b5a7759f060cec68Dmitry Shmidtconst bool gRunTestsInOneThread = false; 40a54fa5fb807eaeff45464139b5a7759f060cec68Dmitry Shmidt 41a54fa5fb807eaeff45464139b5a7759f060cec68Dmitry Shmidt#define DEBUG_ACTIVE_OP 0 42a54fa5fb807eaeff45464139b5a7759f060cec68Dmitry Shmidt#define DEBUG_ACTIVE_SPANS 0 43a54fa5fb807eaeff45464139b5a7759f060cec68Dmitry Shmidt#define DEBUG_ACTIVE_SPANS_SHORT_FORM 0 44a54fa5fb807eaeff45464139b5a7759f060cec68Dmitry Shmidt#define DEBUG_ADD_INTERSECTING_TS 0 45a54fa5fb807eaeff45464139b5a7759f060cec68Dmitry Shmidt#define DEBUG_ADD_T_PAIR 0 46a54fa5fb807eaeff45464139b5a7759f060cec68Dmitry Shmidt#define DEBUG_ANGLE 0 47a54fa5fb807eaeff45464139b5a7759f060cec68Dmitry Shmidt#define DEBUG_ASSEMBLE 0 48a54fa5fb807eaeff45464139b5a7759f060cec68Dmitry Shmidt#define DEBUG_CONCIDENT 0 49a54fa5fb807eaeff45464139b5a7759f060cec68Dmitry Shmidt#define DEBUG_CROSS 0 50a54fa5fb807eaeff45464139b5a7759f060cec68Dmitry Shmidt#define DEBUG_FLOW 0 51a54fa5fb807eaeff45464139b5a7759f060cec68Dmitry Shmidt#define DEBUG_MARK_DONE 0 52a54fa5fb807eaeff45464139b5a7759f060cec68Dmitry Shmidt#define DEBUG_PATH_CONSTRUCTION 0 53a54fa5fb807eaeff45464139b5a7759f060cec68Dmitry Shmidt#define DEBUG_SHOW_WINDING 0 54a54fa5fb807eaeff45464139b5a7759f060cec68Dmitry Shmidt#define DEBUG_SORT 0 5561d9df3e62aaa0e87ad05452fcb95142159a17b6Dmitry Shmidt#define DEBUG_UNSORTABLE 0 5661d9df3e62aaa0e87ad05452fcb95142159a17b6Dmitry Shmidt#define DEBUG_WIND_BUMP 0 5761d9df3e62aaa0e87ad05452fcb95142159a17b6Dmitry Shmidt#define DEBUG_WINDING 0 5861d9df3e62aaa0e87ad05452fcb95142159a17b6Dmitry Shmidt#define DEBUG_WINDING_AT_T 0 5961d9df3e62aaa0e87ad05452fcb95142159a17b6Dmitry Shmidt 6061d9df3e62aaa0e87ad05452fcb95142159a17b6Dmitry Shmidt#else 61a54fa5fb807eaeff45464139b5a7759f060cec68Dmitry Shmidt 6261d9df3e62aaa0e87ad05452fcb95142159a17b6Dmitry Shmidtconst bool gRunTestsInOneThread = true; 6361d9df3e62aaa0e87ad05452fcb95142159a17b6Dmitry Shmidt 6461d9df3e62aaa0e87ad05452fcb95142159a17b6Dmitry Shmidt#define DEBUG_ACTIVE_OP 1 6561d9df3e62aaa0e87ad05452fcb95142159a17b6Dmitry Shmidt#define DEBUG_ACTIVE_SPANS 1 6661d9df3e62aaa0e87ad05452fcb95142159a17b6Dmitry Shmidt#define DEBUG_ACTIVE_SPANS_SHORT_FORM 1 6761d9df3e62aaa0e87ad05452fcb95142159a17b6Dmitry Shmidt#define DEBUG_ADD_INTERSECTING_TS 1 6861d9df3e62aaa0e87ad05452fcb95142159a17b6Dmitry Shmidt#define DEBUG_ADD_T_PAIR 1 6961d9df3e62aaa0e87ad05452fcb95142159a17b6Dmitry Shmidt#define DEBUG_ANGLE 1 7061d9df3e62aaa0e87ad05452fcb95142159a17b6Dmitry Shmidt#define DEBUG_ASSEMBLE 1 7161d9df3e62aaa0e87ad05452fcb95142159a17b6Dmitry Shmidt#define DEBUG_CONCIDENT 1 72a54fa5fb807eaeff45464139b5a7759f060cec68Dmitry Shmidt#define DEBUG_CROSS 0 7361d9df3e62aaa0e87ad05452fcb95142159a17b6Dmitry Shmidt#define DEBUG_FLOW 1 7461d9df3e62aaa0e87ad05452fcb95142159a17b6Dmitry Shmidt#define DEBUG_MARK_DONE 1 7561d9df3e62aaa0e87ad05452fcb95142159a17b6Dmitry Shmidt#define DEBUG_PATH_CONSTRUCTION 1 7661d9df3e62aaa0e87ad05452fcb95142159a17b6Dmitry Shmidt#define DEBUG_SHOW_WINDING 0 7761d9df3e62aaa0e87ad05452fcb95142159a17b6Dmitry Shmidt#define DEBUG_SORT 1 7861d9df3e62aaa0e87ad05452fcb95142159a17b6Dmitry Shmidt#define DEBUG_UNSORTABLE 1 7961d9df3e62aaa0e87ad05452fcb95142159a17b6Dmitry Shmidt#define DEBUG_WIND_BUMP 0 8061d9df3e62aaa0e87ad05452fcb95142159a17b6Dmitry Shmidt#define DEBUG_WINDING 1 8161d9df3e62aaa0e87ad05452fcb95142159a17b6Dmitry Shmidt#define DEBUG_WINDING_AT_T 1 8261d9df3e62aaa0e87ad05452fcb95142159a17b6Dmitry Shmidt 8361d9df3e62aaa0e87ad05452fcb95142159a17b6Dmitry Shmidt#endif 84a54fa5fb807eaeff45464139b5a7759f060cec68Dmitry Shmidt 8561d9df3e62aaa0e87ad05452fcb95142159a17b6Dmitry Shmidt#define DEBUG_DUMP (DEBUG_ACTIVE_OP | DEBUG_ACTIVE_SPANS | DEBUG_CONCIDENT | DEBUG_SORT | \ 8661d9df3e62aaa0e87ad05452fcb95142159a17b6Dmitry Shmidt DEBUG_PATH_CONSTRUCTION) 8761d9df3e62aaa0e87ad05452fcb95142159a17b6Dmitry Shmidt 8861d9df3e62aaa0e87ad05452fcb95142159a17b6Dmitry Shmidt#if DEBUG_DUMP 89a54fa5fb807eaeff45464139b5a7759f060cec68Dmitry Shmidtstatic const char* kShapeOpStr[] = {"diff", "sect", "union", "xor"}; 90a54fa5fb807eaeff45464139b5a7759f060cec68Dmitry Shmidtstatic const char* kLVerbStr[] = {"", "line", "quad", "cubic"}; 91a54fa5fb807eaeff45464139b5a7759f060cec68Dmitry Shmidt// static const char* kUVerbStr[] = {"", "Line", "Quad", "Cubic"}; 92a54fa5fb807eaeff45464139b5a7759f060cec68Dmitry Shmidtstatic int gContourID; 93a54fa5fb807eaeff45464139b5a7759f060cec68Dmitry Shmidtstatic int gSegmentID; 94a54fa5fb807eaeff45464139b5a7759f060cec68Dmitry Shmidt#endif 95a54fa5fb807eaeff45464139b5a7759f060cec68Dmitry Shmidt 96a54fa5fb807eaeff45464139b5a7759f060cec68Dmitry Shmidt#ifndef DEBUG_TEST 97a54fa5fb807eaeff45464139b5a7759f060cec68Dmitry Shmidt#define DEBUG_TEST 0 9861d9df3e62aaa0e87ad05452fcb95142159a17b6Dmitry Shmidt#endif 99 100#define MAKE_CONST_LINE(line, pts) \ 101 const _Line line = {{pts[0].fX, pts[0].fY}, {pts[1].fX, pts[1].fY}} 102#define MAKE_CONST_QUAD(quad, pts) \ 103 const Quadratic quad = {{pts[0].fX, pts[0].fY}, {pts[1].fX, pts[1].fY}, \ 104 {pts[2].fX, pts[2].fY}} 105#define MAKE_CONST_CUBIC(cubic, pts) \ 106 const Cubic cubic = {{pts[0].fX, pts[0].fY}, {pts[1].fX, pts[1].fY}, \ 107 {pts[2].fX, pts[2].fY}, {pts[3].fX, pts[3].fY}} 108 109static int LineIntersect(const SkPoint a[2], const SkPoint b[2], 110 Intersections& intersections) { 111 MAKE_CONST_LINE(aLine, a); 112 MAKE_CONST_LINE(bLine, b); 113 return intersect(aLine, bLine, intersections); 114} 115 116static int QuadLineIntersect(const SkPoint a[3], const SkPoint b[2], 117 Intersections& intersections) { 118 MAKE_CONST_QUAD(aQuad, a); 119 MAKE_CONST_LINE(bLine, b); 120 return intersect(aQuad, bLine, intersections); 121} 122 123static int CubicLineIntersect(const SkPoint a[4], const SkPoint b[2], 124 Intersections& intersections) { 125 MAKE_CONST_CUBIC(aCubic, a); 126 MAKE_CONST_LINE(bLine, b); 127 return intersect(aCubic, bLine, intersections); 128} 129 130static int QuadIntersect(const SkPoint a[3], const SkPoint b[3], 131 Intersections& intersections) { 132 MAKE_CONST_QUAD(aQuad, a); 133 MAKE_CONST_QUAD(bQuad, b); 134#define TRY_QUARTIC_SOLUTION 1 135#if TRY_QUARTIC_SOLUTION 136 intersect2(aQuad, bQuad, intersections); 137#else 138 intersect(aQuad, bQuad, intersections); 139#endif 140 return intersections.fUsed; 141} 142 143#if APPROXIMATE_CUBICS 144static int CubicQuadIntersect(const SkPoint a[4], const SkPoint b[3], 145 Intersections& intersections) { 146 MAKE_CONST_CUBIC(aCubic, a); 147 MAKE_CONST_QUAD(bQuad, b); 148 return intersect(aCubic, bQuad, intersections); 149} 150#endif 151 152static int CubicIntersect(const SkPoint a[4], const SkPoint b[4], Intersections& intersections) { 153 MAKE_CONST_CUBIC(aCubic, a); 154 MAKE_CONST_CUBIC(bCubic, b); 155#if APPROXIMATE_CUBICS 156 intersect3(aCubic, bCubic, intersections); 157#else 158 intersect(aCubic, bCubic, intersections); 159#endif 160 return intersections.fUsed; 161} 162 163static int HLineIntersect(const SkPoint a[2], SkScalar left, SkScalar right, 164 SkScalar y, bool flipped, Intersections& intersections) { 165 MAKE_CONST_LINE(aLine, a); 166 return horizontalIntersect(aLine, left, right, y, flipped, intersections); 167} 168 169static int HQuadIntersect(const SkPoint a[3], SkScalar left, SkScalar right, 170 SkScalar y, bool flipped, Intersections& intersections) { 171 MAKE_CONST_QUAD(aQuad, a); 172 return horizontalIntersect(aQuad, left, right, y, flipped, intersections); 173} 174 175static int HCubicIntersect(const SkPoint a[4], SkScalar left, SkScalar right, 176 SkScalar y, bool flipped, Intersections& intersections) { 177 MAKE_CONST_CUBIC(aCubic, a); 178 return horizontalIntersect(aCubic, left, right, y, flipped, intersections); 179} 180 181static int (* const HSegmentIntersect[])(const SkPoint [], SkScalar , 182 SkScalar , SkScalar , bool , Intersections& ) = { 183 NULL, 184 HLineIntersect, 185 HQuadIntersect, 186 HCubicIntersect 187}; 188 189static int VLineIntersect(const SkPoint a[2], SkScalar top, SkScalar bottom, 190 SkScalar x, bool flipped, Intersections& intersections) { 191 MAKE_CONST_LINE(aLine, a); 192 return verticalIntersect(aLine, top, bottom, x, flipped, intersections); 193} 194 195static int VQuadIntersect(const SkPoint a[3], SkScalar top, SkScalar bottom, 196 SkScalar x, bool flipped, Intersections& intersections) { 197 MAKE_CONST_QUAD(aQuad, a); 198 return verticalIntersect(aQuad, top, bottom, x, flipped, intersections); 199} 200 201static int VCubicIntersect(const SkPoint a[4], SkScalar top, SkScalar bottom, 202 SkScalar x, bool flipped, Intersections& intersections) { 203 MAKE_CONST_CUBIC(aCubic, a); 204 return verticalIntersect(aCubic, top, bottom, x, flipped, intersections); 205} 206 207static int (* const VSegmentIntersect[])(const SkPoint [], SkScalar , 208 SkScalar , SkScalar , bool , Intersections& ) = { 209 NULL, 210 VLineIntersect, 211 VQuadIntersect, 212 VCubicIntersect 213}; 214 215static void LineXYAtT(const SkPoint a[2], double t, SkPoint* out) { 216 MAKE_CONST_LINE(line, a); 217 double x, y; 218 xy_at_t(line, t, x, y); 219 out->fX = SkDoubleToScalar(x); 220 out->fY = SkDoubleToScalar(y); 221} 222 223static void LineXYAtT(const SkPoint a[2], double t, _Point* out) { 224 MAKE_CONST_LINE(line, a); 225 xy_at_t(line, t, out->x, out->y); 226} 227 228static void QuadXYAtT(const SkPoint a[3], double t, SkPoint* out) { 229 MAKE_CONST_QUAD(quad, a); 230 double x, y; 231 xy_at_t(quad, t, x, y); 232 out->fX = SkDoubleToScalar(x); 233 out->fY = SkDoubleToScalar(y); 234} 235 236static void QuadXYAtT(const SkPoint a[3], double t, _Point* out) { 237 MAKE_CONST_QUAD(quad, a); 238 xy_at_t(quad, t, out->x, out->y); 239} 240 241static void CubicXYAtT(const SkPoint a[4], double t, SkPoint* out) { 242 MAKE_CONST_CUBIC(cubic, a); 243 double x, y; 244 xy_at_t(cubic, t, x, y); 245 out->fX = SkDoubleToScalar(x); 246 out->fY = SkDoubleToScalar(y); 247} 248 249static void CubicXYAtT(const SkPoint a[4], double t, _Point* out) { 250 MAKE_CONST_CUBIC(cubic, a); 251 xy_at_t(cubic, t, out->x, out->y); 252} 253 254static void (* const SegmentXYAtT[])(const SkPoint [], double , SkPoint* ) = { 255 NULL, 256 LineXYAtT, 257 QuadXYAtT, 258 CubicXYAtT 259}; 260 261static void (* const SegmentXYAtT2[])(const SkPoint [], double , _Point* ) = { 262 NULL, 263 LineXYAtT, 264 QuadXYAtT, 265 CubicXYAtT 266}; 267 268static SkScalar LineXAtT(const SkPoint a[2], double t) { 269 MAKE_CONST_LINE(aLine, a); 270 double x; 271 xy_at_t(aLine, t, x, *(double*) 0); 272 return SkDoubleToScalar(x); 273} 274 275static SkScalar QuadXAtT(const SkPoint a[3], double t) { 276 MAKE_CONST_QUAD(quad, a); 277 double x; 278 xy_at_t(quad, t, x, *(double*) 0); 279 return SkDoubleToScalar(x); 280} 281 282static SkScalar CubicXAtT(const SkPoint a[4], double t) { 283 MAKE_CONST_CUBIC(cubic, a); 284 double x; 285 xy_at_t(cubic, t, x, *(double*) 0); 286 return SkDoubleToScalar(x); 287} 288 289static SkScalar (* const SegmentXAtT[])(const SkPoint [], double ) = { 290 NULL, 291 LineXAtT, 292 QuadXAtT, 293 CubicXAtT 294}; 295 296static SkScalar LineYAtT(const SkPoint a[2], double t) { 297 MAKE_CONST_LINE(aLine, a); 298 double y; 299 xy_at_t(aLine, t, *(double*) 0, y); 300 return SkDoubleToScalar(y); 301} 302 303static SkScalar QuadYAtT(const SkPoint a[3], double t) { 304 MAKE_CONST_QUAD(quad, a); 305 double y; 306 xy_at_t(quad, t, *(double*) 0, y); 307 return SkDoubleToScalar(y); 308} 309 310static SkScalar CubicYAtT(const SkPoint a[4], double t) { 311 MAKE_CONST_CUBIC(cubic, a); 312 double y; 313 xy_at_t(cubic, t, *(double*) 0, y); 314 return SkDoubleToScalar(y); 315} 316 317static SkScalar (* const SegmentYAtT[])(const SkPoint [], double ) = { 318 NULL, 319 LineYAtT, 320 QuadYAtT, 321 CubicYAtT 322}; 323 324static SkScalar LineDXAtT(const SkPoint a[2], double ) { 325 return a[1].fX - a[0].fX; 326} 327 328static SkScalar QuadDXAtT(const SkPoint a[3], double t) { 329 MAKE_CONST_QUAD(quad, a); 330 double x = dx_at_t(quad, t); 331 return SkDoubleToScalar(x); 332} 333 334static SkScalar CubicDXAtT(const SkPoint a[4], double t) { 335 MAKE_CONST_CUBIC(cubic, a); 336 double x = dx_at_t(cubic, t); 337 return SkDoubleToScalar(x); 338} 339 340static SkScalar (* const SegmentDXAtT[])(const SkPoint [], double ) = { 341 NULL, 342 LineDXAtT, 343 QuadDXAtT, 344 CubicDXAtT 345}; 346 347static SkScalar LineDYAtT(const SkPoint a[2], double ) { 348 return a[1].fY - a[0].fY; 349} 350 351static SkScalar QuadDYAtT(const SkPoint a[3], double t) { 352 MAKE_CONST_QUAD(quad, a); 353 double y = dy_at_t(quad, t); 354 return SkDoubleToScalar(y); 355} 356 357static SkScalar CubicDYAtT(const SkPoint a[4], double t) { 358 MAKE_CONST_CUBIC(cubic, a); 359 double y = dy_at_t(cubic, t); 360 return SkDoubleToScalar(y); 361} 362 363static SkScalar (* const SegmentDYAtT[])(const SkPoint [], double ) = { 364 NULL, 365 LineDYAtT, 366 QuadDYAtT, 367 CubicDYAtT 368}; 369 370static SkPoint LineDXDYAtT(const SkPoint a[2], double ) { 371 return a[1] - a[0]; 372} 373 374static SkPoint QuadDXDYAtT(const SkPoint a[3], double t) { 375 MAKE_CONST_QUAD(quad, a); 376 _Point pt; 377 dxdy_at_t(quad, t, pt); 378 return pt.asSkPoint(); 379} 380 381static SkPoint CubicDXDYAtT(const SkPoint a[4], double t) { 382 MAKE_CONST_CUBIC(cubic, a); 383 _Point pt; 384 dxdy_at_t(cubic, t, pt); 385 return pt.asSkPoint(); 386} 387 388static SkPoint (* const SegmentDXDYAtT[])(const SkPoint [], double ) = { 389 NULL, 390 LineDXDYAtT, 391 QuadDXDYAtT, 392 CubicDXDYAtT 393}; 394 395static void LineSubDivide(const SkPoint a[2], double startT, double endT, 396 SkPoint sub[2]) { 397 MAKE_CONST_LINE(aLine, a); 398 _Line dst; 399 sub_divide(aLine, startT, endT, dst); 400 sub[0].fX = SkDoubleToScalar(dst[0].x); 401 sub[0].fY = SkDoubleToScalar(dst[0].y); 402 sub[1].fX = SkDoubleToScalar(dst[1].x); 403 sub[1].fY = SkDoubleToScalar(dst[1].y); 404} 405 406static void QuadSubDivide(const SkPoint a[3], double startT, double endT, 407 SkPoint sub[3]) { 408 MAKE_CONST_QUAD(aQuad, a); 409 Quadratic dst; 410 sub_divide(aQuad, startT, endT, dst); 411 sub[0].fX = SkDoubleToScalar(dst[0].x); 412 sub[0].fY = SkDoubleToScalar(dst[0].y); 413 sub[1].fX = SkDoubleToScalar(dst[1].x); 414 sub[1].fY = SkDoubleToScalar(dst[1].y); 415 sub[2].fX = SkDoubleToScalar(dst[2].x); 416 sub[2].fY = SkDoubleToScalar(dst[2].y); 417} 418 419static void CubicSubDivide(const SkPoint a[4], double startT, double endT, 420 SkPoint sub[4]) { 421 MAKE_CONST_CUBIC(aCubic, a); 422 Cubic dst; 423 sub_divide(aCubic, startT, endT, dst); 424 sub[0].fX = SkDoubleToScalar(dst[0].x); 425 sub[0].fY = SkDoubleToScalar(dst[0].y); 426 sub[1].fX = SkDoubleToScalar(dst[1].x); 427 sub[1].fY = SkDoubleToScalar(dst[1].y); 428 sub[2].fX = SkDoubleToScalar(dst[2].x); 429 sub[2].fY = SkDoubleToScalar(dst[2].y); 430 sub[3].fX = SkDoubleToScalar(dst[3].x); 431 sub[3].fY = SkDoubleToScalar(dst[3].y); 432} 433 434static void (* const SegmentSubDivide[])(const SkPoint [], double , double , 435 SkPoint []) = { 436 NULL, 437 LineSubDivide, 438 QuadSubDivide, 439 CubicSubDivide 440}; 441 442static void LineSubDivideHD(const SkPoint a[2], double startT, double endT, _Line& dst) { 443 MAKE_CONST_LINE(aLine, a); 444 sub_divide(aLine, startT, endT, dst); 445} 446 447static void QuadSubDivideHD(const SkPoint a[3], double startT, double endT, Quadratic& dst) { 448 MAKE_CONST_QUAD(aQuad, a); 449 sub_divide(aQuad, startT, endT, dst); 450} 451 452static void CubicSubDivideHD(const SkPoint a[4], double startT, double endT, Cubic& dst) { 453 MAKE_CONST_CUBIC(aCubic, a); 454 sub_divide(aCubic, startT, endT, dst); 455} 456 457static SkPoint QuadTop(const SkPoint a[3], double startT, double endT) { 458 MAKE_CONST_QUAD(quad, a); 459 _Point topPt = top(quad, startT, endT); 460 return topPt.asSkPoint(); 461} 462 463static SkPoint CubicTop(const SkPoint a[3], double startT, double endT) { 464 MAKE_CONST_CUBIC(cubic, a); 465 _Point topPt = top(cubic, startT, endT); 466 return topPt.asSkPoint(); 467} 468 469static SkPoint (* SegmentTop[])(const SkPoint[], double , double ) = { 470 NULL, 471 NULL, 472 QuadTop, 473 CubicTop 474}; 475 476#if DEBUG_UNUSED 477static void QuadSubBounds(const SkPoint a[3], double startT, double endT, 478 SkRect& bounds) { 479 SkPoint dst[3]; 480 QuadSubDivide(a, startT, endT, dst); 481 bounds.fLeft = bounds.fRight = dst[0].fX; 482 bounds.fTop = bounds.fBottom = dst[0].fY; 483 for (int index = 1; index < 3; ++index) { 484 bounds.growToInclude(dst[index].fX, dst[index].fY); 485 } 486} 487 488static void CubicSubBounds(const SkPoint a[4], double startT, double endT, 489 SkRect& bounds) { 490 SkPoint dst[4]; 491 CubicSubDivide(a, startT, endT, dst); 492 bounds.fLeft = bounds.fRight = dst[0].fX; 493 bounds.fTop = bounds.fBottom = dst[0].fY; 494 for (int index = 1; index < 4; ++index) { 495 bounds.growToInclude(dst[index].fX, dst[index].fY); 496 } 497} 498#endif 499 500static SkPath::Verb QuadReduceOrder(const SkPoint a[3], 501 SkTDArray<SkPoint>& reducePts) { 502 MAKE_CONST_QUAD(aQuad, a); 503 Quadratic dst; 504 int order = reduceOrder(aQuad, dst); 505 if (order == 2) { // quad became line 506 for (int index = 0; index < order; ++index) { 507 SkPoint* pt = reducePts.append(); 508 pt->fX = SkDoubleToScalar(dst[index].x); 509 pt->fY = SkDoubleToScalar(dst[index].y); 510 } 511 } 512 return (SkPath::Verb) (order - 1); 513} 514 515static SkPath::Verb CubicReduceOrder(const SkPoint a[4], 516 SkTDArray<SkPoint>& reducePts) { 517 MAKE_CONST_CUBIC(aCubic, a); 518 Cubic dst; 519 int order = reduceOrder(aCubic, dst, kReduceOrder_QuadraticsAllowed); 520 if (order == 2 || order == 3) { // cubic became line or quad 521 for (int index = 0; index < order; ++index) { 522 SkPoint* pt = reducePts.append(); 523 pt->fX = SkDoubleToScalar(dst[index].x); 524 pt->fY = SkDoubleToScalar(dst[index].y); 525 } 526 } 527 return (SkPath::Verb) (order - 1); 528} 529 530static bool QuadIsLinear(const SkPoint a[3]) { 531 MAKE_CONST_QUAD(aQuad, a); 532 return isLinear(aQuad, 0, 2); 533} 534 535static bool CubicIsLinear(const SkPoint a[4]) { 536 MAKE_CONST_CUBIC(aCubic, a); 537 return isLinear(aCubic, 0, 3); 538} 539 540static SkScalar LineLeftMost(const SkPoint a[2], double startT, double endT) { 541 MAKE_CONST_LINE(aLine, a); 542 double x[2]; 543 xy_at_t(aLine, startT, x[0], *(double*) 0); 544 xy_at_t(aLine, endT, x[1], *(double*) 0); 545 return SkMinScalar((float) x[0], (float) x[1]); 546} 547 548static SkScalar QuadLeftMost(const SkPoint a[3], double startT, double endT) { 549 MAKE_CONST_QUAD(aQuad, a); 550 return (float) leftMostT(aQuad, startT, endT); 551} 552 553static SkScalar CubicLeftMost(const SkPoint a[4], double startT, double endT) { 554 MAKE_CONST_CUBIC(aCubic, a); 555 return (float) leftMostT(aCubic, startT, endT); 556} 557 558static SkScalar (* const SegmentLeftMost[])(const SkPoint [], double , double) = { 559 NULL, 560 LineLeftMost, 561 QuadLeftMost, 562 CubicLeftMost 563}; 564 565#if 0 // currently unused 566static int QuadRayIntersect(const SkPoint a[3], const SkPoint b[2], 567 Intersections& intersections) { 568 MAKE_CONST_QUAD(aQuad, a); 569 MAKE_CONST_LINE(bLine, b); 570 return intersectRay(aQuad, bLine, intersections); 571} 572#endif 573 574static int QuadRayIntersect(const SkPoint a[3], const _Line& bLine, Intersections& intersections) { 575 MAKE_CONST_QUAD(aQuad, a); 576 return intersectRay(aQuad, bLine, intersections); 577} 578 579static int CubicRayIntersect(const SkPoint a[3], const _Line& bLine, Intersections& intersections) { 580 MAKE_CONST_CUBIC(aCubic, a); 581 return intersectRay(aCubic, bLine, intersections); 582} 583 584static int (* const SegmentRayIntersect[])(const SkPoint [], const _Line& , Intersections&) = { 585 NULL, 586 NULL, 587 QuadRayIntersect, 588 CubicRayIntersect 589}; 590 591 592 593static bool LineVertical(const SkPoint a[2], double startT, double endT) { 594 MAKE_CONST_LINE(aLine, a); 595 double x[2]; 596 xy_at_t(aLine, startT, x[0], *(double*) 0); 597 xy_at_t(aLine, endT, x[1], *(double*) 0); 598 return AlmostEqualUlps((float) x[0], (float) x[1]); 599} 600 601static bool QuadVertical(const SkPoint a[3], double startT, double endT) { 602 SkPoint dst[3]; 603 QuadSubDivide(a, startT, endT, dst); 604 return AlmostEqualUlps(dst[0].fX, dst[1].fX) && AlmostEqualUlps(dst[1].fX, dst[2].fX); 605} 606 607static bool CubicVertical(const SkPoint a[4], double startT, double endT) { 608 SkPoint dst[4]; 609 CubicSubDivide(a, startT, endT, dst); 610 return AlmostEqualUlps(dst[0].fX, dst[1].fX) && AlmostEqualUlps(dst[1].fX, dst[2].fX) 611 && AlmostEqualUlps(dst[2].fX, dst[3].fX); 612} 613 614static bool (* const SegmentVertical[])(const SkPoint [], double , double) = { 615 NULL, 616 LineVertical, 617 QuadVertical, 618 CubicVertical 619}; 620 621class Segment; 622 623struct Span { 624 Segment* fOther; 625 mutable SkPoint fPt; // lazily computed as needed 626 double fT; 627 double fOtherT; // value at fOther[fOtherIndex].fT 628 int fOtherIndex; // can't be used during intersection 629 int fWindSum; // accumulated from contours surrounding this one. 630 int fOppSum; // for binary operators: the opposite winding sum 631 int fWindValue; // 0 == canceled; 1 == normal; >1 == coincident 632 int fOppValue; // normally 0 -- when binary coincident edges combine, opp value goes here 633 bool fDone; // if set, this span to next higher T has been processed 634 bool fUnsortableStart; // set when start is part of an unsortable pair 635 bool fUnsortableEnd; // set when end is part of an unsortable pair 636 bool fTiny; // if set, span may still be considered once for edge following 637}; 638 639// sorting angles 640// given angles of {dx dy ddx ddy dddx dddy} sort them 641class Angle { 642public: 643 // FIXME: this is bogus for quads and cubics 644 // if the quads and cubics' line from end pt to ctrl pt are coincident, 645 // there's no obvious way to determine the curve ordering from the 646 // derivatives alone. In particular, if one quadratic's coincident tangent 647 // is longer than the other curve, the final control point can place the 648 // longer curve on either side of the shorter one. 649 // Using Bezier curve focus http://cagd.cs.byu.edu/~tom/papers/bezclip.pdf 650 // may provide some help, but nothing has been figured out yet. 651 652 /*( 653 for quads and cubics, set up a parameterized line (e.g. LineParameters ) 654 for points [0] to [1]. See if point [2] is on that line, or on one side 655 or the other. If it both quads' end points are on the same side, choose 656 the shorter tangent. If the tangents are equal, choose the better second 657 tangent angle 658 659 maybe I could set up LineParameters lazily 660 */ 661 bool operator<(const Angle& rh) const { 662 double y = dy(); 663 double ry = rh.dy(); 664 if ((y < 0) ^ (ry < 0)) { // OPTIMIZATION: better to use y * ry < 0 ? 665 return y < 0; 666 } 667 double x = dx(); 668 double rx = rh.dx(); 669 if (y == 0 && ry == 0 && x * rx < 0) { 670 return x < rx; 671 } 672 double x_ry = x * ry; 673 double rx_y = rx * y; 674 double cmp = x_ry - rx_y; 675 if (!approximately_zero(cmp)) { 676 return cmp < 0; 677 } 678 if (approximately_zero(x_ry) && approximately_zero(rx_y) 679 && !approximately_zero_squared(cmp)) { 680 return cmp < 0; 681 } 682 // at this point, the initial tangent line is coincident 683 // see if edges curl away from each other 684 if (fSide * rh.fSide <= 0 && (!approximately_zero(fSide) 685 || !approximately_zero(rh.fSide))) { 686 // FIXME: running demo will trigger this assertion 687 // (don't know if commenting out will trigger further assertion or not) 688 // commenting it out allows demo to run in release, though 689 // SkASSERT(fSide != rh.fSide); 690 return fSide < rh.fSide; 691 } 692 // see if either curve can be lengthened and try the tangent compare again 693 if (cmp && (*fSpans)[fEnd].fOther != rh.fSegment // tangents not absolutely identical 694 && (*rh.fSpans)[rh.fEnd].fOther != fSegment) { // and not intersecting 695 Angle longer = *this; 696 Angle rhLonger = rh; 697 if (longer.lengthen() | rhLonger.lengthen()) { 698 return longer < rhLonger; 699 } 700 #if 0 701 // what if we extend in the other direction? 702 longer = *this; 703 rhLonger = rh; 704 if (longer.reverseLengthen() | rhLonger.reverseLengthen()) { 705 return longer < rhLonger; 706 } 707 #endif 708 } 709 if ((fVerb == SkPath::kLine_Verb && approximately_zero(x) && approximately_zero(y)) 710 || (rh.fVerb == SkPath::kLine_Verb 711 && approximately_zero(rx) && approximately_zero(ry))) { 712 // See general unsortable comment below. This case can happen when 713 // one line has a non-zero change in t but no change in x and y. 714 fUnsortable = true; 715 rh.fUnsortable = true; 716 return this < &rh; // even with no solution, return a stable sort 717 } 718 if ((*rh.fSpans)[SkMin32(rh.fStart, rh.fEnd)].fTiny 719 || (*fSpans)[SkMin32(fStart, fEnd)].fTiny) { 720 fUnsortable = true; 721 rh.fUnsortable = true; 722 return this < &rh; // even with no solution, return a stable sort 723 } 724 SkASSERT(fVerb >= SkPath::kQuad_Verb); 725 SkASSERT(rh.fVerb >= SkPath::kQuad_Verb); 726 // FIXME: until I can think of something better, project a ray from the 727 // end of the shorter tangent to midway between the end points 728 // through both curves and use the resulting angle to sort 729 // FIXME: some of this setup can be moved to set() if it works, or cached if it's expensive 730 double len = fTangent1.normalSquared(); 731 double rlen = rh.fTangent1.normalSquared(); 732 _Line ray; 733 Intersections i, ri; 734 int roots, rroots; 735 bool flip = false; 736 do { 737 bool useThis = (len < rlen) ^ flip; 738 const Cubic& part = useThis ? fCurvePart : rh.fCurvePart; 739 SkPath::Verb partVerb = useThis ? fVerb : rh.fVerb; 740 ray[0] = partVerb == SkPath::kCubic_Verb && part[0].approximatelyEqual(part[1]) ? 741 part[2] : part[1]; 742 ray[1].x = (part[0].x + part[partVerb].x) / 2; 743 ray[1].y = (part[0].y + part[partVerb].y) / 2; 744 SkASSERT(ray[0] != ray[1]); 745 roots = (*SegmentRayIntersect[fVerb])(fPts, ray, i); 746 rroots = (*SegmentRayIntersect[rh.fVerb])(rh.fPts, ray, ri); 747 } while ((roots == 0 || rroots == 0) && (flip ^= true)); 748 if (roots == 0 || rroots == 0) { 749 // FIXME: we don't have a solution in this case. The interim solution 750 // is to mark the edges as unsortable, exclude them from this and 751 // future computations, and allow the returned path to be fragmented 752 fUnsortable = true; 753 rh.fUnsortable = true; 754 return this < &rh; // even with no solution, return a stable sort 755 } 756 _Point loc; 757 double best = SK_ScalarInfinity; 758 double dx, dy, dist; 759 int index; 760 for (index = 0; index < roots; ++index) { 761 (*SegmentXYAtT2[fVerb])(fPts, i.fT[0][index], &loc); 762 dx = loc.x - ray[0].x; 763 dy = loc.y - ray[0].y; 764 dist = dx * dx + dy * dy; 765 if (best > dist) { 766 best = dist; 767 } 768 } 769 for (index = 0; index < rroots; ++index) { 770 (*SegmentXYAtT2[rh.fVerb])(rh.fPts, ri.fT[0][index], &loc); 771 dx = loc.x - ray[0].x; 772 dy = loc.y - ray[0].y; 773 dist = dx * dx + dy * dy; 774 if (best > dist) { 775 return fSide < 0; 776 } 777 } 778 return fSide > 0; 779 } 780 781 double dx() const { 782 return fTangent1.dx(); 783 } 784 785 double dy() const { 786 return fTangent1.dy(); 787 } 788 789 int end() const { 790 return fEnd; 791 } 792 793 bool isHorizontal() const { 794 return dy() == 0 && fVerb == SkPath::kLine_Verb; 795 } 796 797 bool lengthen() { 798 int newEnd = fEnd; 799 if (fStart < fEnd ? ++newEnd < fSpans->count() : --newEnd >= 0) { 800 fEnd = newEnd; 801 setSpans(); 802 return true; 803 } 804 return false; 805 } 806 807 bool reverseLengthen() { 808 if (fReversed) { 809 return false; 810 } 811 int newEnd = fStart; 812 if (fStart > fEnd ? ++newEnd < fSpans->count() : --newEnd >= 0) { 813 fEnd = newEnd; 814 fReversed = true; 815 setSpans(); 816 return true; 817 } 818 return false; 819 } 820 821 void set(const SkPoint* orig, SkPath::Verb verb, const Segment* segment, 822 int start, int end, const SkTDArray<Span>& spans) { 823 fSegment = segment; 824 fStart = start; 825 fEnd = end; 826 fPts = orig; 827 fVerb = verb; 828 fSpans = &spans; 829 fReversed = false; 830 fUnsortable = false; 831 setSpans(); 832 } 833 834 835 void setSpans() { 836 double startT = (*fSpans)[fStart].fT; 837 double endT = (*fSpans)[fEnd].fT; 838 switch (fVerb) { 839 case SkPath::kLine_Verb: 840 _Line l; 841 LineSubDivideHD(fPts, startT, endT, l); 842 // OPTIMIZATION: for pure line compares, we never need fTangent1.c 843 fTangent1.lineEndPoints(l); 844 fSide = 0; 845 break; 846 case SkPath::kQuad_Verb: { 847 Quadratic& quad = (Quadratic&)fCurvePart; 848 QuadSubDivideHD(fPts, startT, endT, quad); 849 fTangent1.quadEndPoints(quad, 0, 1); 850 #if 1 // FIXME: try enabling this and see if a) it's called and b) does it break anything 851 if (dx() == 0 && dy() == 0) { 852 // SkDebugf("*** %s quad is line\n", __FUNCTION__); 853 fTangent1.quadEndPoints(quad); 854 } 855 #endif 856 fSide = -fTangent1.pointDistance(fCurvePart[2]); // not normalized -- compare sign only 857 } break; 858 case SkPath::kCubic_Verb: { 859 int nextC = 2; 860 CubicSubDivideHD(fPts, startT, endT, fCurvePart); 861 fTangent1.cubicEndPoints(fCurvePart, 0, 1); 862 if (dx() == 0 && dy() == 0) { 863 fTangent1.cubicEndPoints(fCurvePart, 0, 2); 864 nextC = 3; 865 #if 1 // FIXME: try enabling this and see if a) it's called and b) does it break anything 866 if (dx() == 0 && dy() == 0) { 867 SkDebugf("*** %s cubic is line\n", __FUNCTION__); 868 fTangent1.cubicEndPoints(fCurvePart, 0, 3); 869 } 870 #endif 871 } 872 fSide = -fTangent1.pointDistance(fCurvePart[nextC]); // compare sign only 873 if (nextC == 2 && approximately_zero(fSide)) { 874 fSide = -fTangent1.pointDistance(fCurvePart[3]); 875 } 876 } break; 877 default: 878 SkASSERT(0); 879 } 880 fUnsortable = dx() == 0 && dy() == 0; 881 if (fUnsortable) { 882 return; 883 } 884 SkASSERT(fStart != fEnd); 885 int step = fStart < fEnd ? 1 : -1; // OPTIMIZE: worth fStart - fEnd >> 31 type macro? 886 for (int index = fStart; index != fEnd; index += step) { 887#if 1 888 const Span& thisSpan = (*fSpans)[index]; 889 const Span& nextSpan = (*fSpans)[index + step]; 890 if (thisSpan.fTiny || thisSpan.fT == nextSpan.fT) { 891 continue; 892 } 893 fUnsortable = step > 0 ? thisSpan.fUnsortableStart : nextSpan.fUnsortableEnd; 894#if DEBUG_UNSORTABLE 895 if (fUnsortable) { 896 SkPoint iPt, ePt; 897 (*SegmentXYAtT[fVerb])(fPts, thisSpan.fT, &iPt); 898 (*SegmentXYAtT[fVerb])(fPts, nextSpan.fT, &ePt); 899 SkDebugf("%s unsortable [%d] (%1.9g,%1.9g) [%d] (%1.9g,%1.9g)\n", __FUNCTION__, 900 index, iPt.fX, iPt.fY, fEnd, ePt.fX, ePt.fY); 901 } 902#endif 903 return; 904#else 905 if ((*fSpans)[index].fUnsortableStart) { 906 fUnsortable = true; 907 return; 908 } 909#endif 910 } 911#if 1 912#if DEBUG_UNSORTABLE 913 SkPoint iPt, ePt; 914 (*SegmentXYAtT[fVerb])(fPts, startT, &iPt); 915 (*SegmentXYAtT[fVerb])(fPts, endT, &ePt); 916 SkDebugf("%s all tiny unsortable [%d] (%1.9g,%1.9g) [%d] (%1.9g,%1.9g)\n", __FUNCTION__, 917 fStart, iPt.fX, iPt.fY, fEnd, ePt.fX, ePt.fY); 918#endif 919 fUnsortable = true; 920#endif 921 } 922 923 Segment* segment() const { 924 return const_cast<Segment*>(fSegment); 925 } 926 927 int sign() const { 928 return SkSign32(fStart - fEnd); 929 } 930 931 const SkTDArray<Span>* spans() const { 932 return fSpans; 933 } 934 935 int start() const { 936 return fStart; 937 } 938 939 bool unsortable() const { 940 return fUnsortable; 941 } 942 943#if DEBUG_ANGLE 944 const SkPoint* pts() const { 945 return fPts; 946 } 947 948 SkPath::Verb verb() const { 949 return fVerb; 950 } 951 952 void debugShow(const SkPoint& a) const { 953 SkDebugf(" d=(%1.9g,%1.9g) side=%1.9g\n", dx(), dy(), fSide); 954 } 955#endif 956 957private: 958 const SkPoint* fPts; 959 Cubic fCurvePart; 960 SkPath::Verb fVerb; 961 double fSide; 962 LineParameters fTangent1; 963 const SkTDArray<Span>* fSpans; 964 const Segment* fSegment; 965 int fStart; 966 int fEnd; 967 bool fReversed; 968 mutable bool fUnsortable; // this alone is editable by the less than operator 969}; 970 971// Bounds, unlike Rect, does not consider a line to be empty. 972struct Bounds : public SkRect { 973 static bool Intersects(const Bounds& a, const Bounds& b) { 974 return a.fLeft <= b.fRight && b.fLeft <= a.fRight && 975 a.fTop <= b.fBottom && b.fTop <= a.fBottom; 976 } 977 978 void add(SkScalar left, SkScalar top, SkScalar right, SkScalar bottom) { 979 if (left < fLeft) { 980 fLeft = left; 981 } 982 if (top < fTop) { 983 fTop = top; 984 } 985 if (right > fRight) { 986 fRight = right; 987 } 988 if (bottom > fBottom) { 989 fBottom = bottom; 990 } 991 } 992 993 void add(const Bounds& toAdd) { 994 add(toAdd.fLeft, toAdd.fTop, toAdd.fRight, toAdd.fBottom); 995 } 996 997 void add(const SkPoint& pt) { 998 if (pt.fX < fLeft) fLeft = pt.fX; 999 if (pt.fY < fTop) fTop = pt.fY; 1000 if (pt.fX > fRight) fRight = pt.fX; 1001 if (pt.fY > fBottom) fBottom = pt.fY; 1002 } 1003 1004 bool isEmpty() { 1005 return fLeft > fRight || fTop > fBottom 1006 || (fLeft == fRight && fTop == fBottom) 1007 || sk_double_isnan(fLeft) || sk_double_isnan(fRight) 1008 || sk_double_isnan(fTop) || sk_double_isnan(fBottom); 1009 } 1010 1011 void setCubicBounds(const SkPoint a[4]) { 1012 _Rect dRect; 1013 MAKE_CONST_CUBIC(cubic, a); 1014 dRect.setBounds(cubic); 1015 set((float) dRect.left, (float) dRect.top, (float) dRect.right, 1016 (float) dRect.bottom); 1017 } 1018 1019 void setQuadBounds(const SkPoint a[3]) { 1020 MAKE_CONST_QUAD(quad, a); 1021 _Rect dRect; 1022 dRect.setBounds(quad); 1023 set((float) dRect.left, (float) dRect.top, (float) dRect.right, 1024 (float) dRect.bottom); 1025 } 1026 1027 void setPoint(const SkPoint& pt) { 1028 fLeft = fRight = pt.fX; 1029 fTop = fBottom = pt.fY; 1030 } 1031}; 1032 1033// OPTIMIZATION: does the following also work, and is it any faster? 1034// return outerWinding * innerWinding > 0 1035// || ((outerWinding + innerWinding < 0) ^ ((outerWinding - innerWinding) < 0))) 1036static bool useInnerWinding(int outerWinding, int innerWinding) { 1037 // SkASSERT(outerWinding != innerWinding); 1038 int absOut = abs(outerWinding); 1039 int absIn = abs(innerWinding); 1040 bool result = absOut == absIn ? outerWinding < 0 : absOut < absIn; 1041 if (outerWinding * innerWinding < 0) { 1042#if DEBUG_WINDING 1043 SkDebugf("%s outer=%d inner=%d result=%s\n", __FUNCTION__, 1044 outerWinding, innerWinding, result ? "true" : "false"); 1045#endif 1046 } 1047 return result; 1048} 1049 1050#define F (false) // discard the edge 1051#define T (true) // keep the edge 1052 1053static const bool gUnaryActiveEdge[2][2] = { 1054// from=0 from=1 1055// to=0,1 to=0,1 1056 {F, T}, {T, F}, 1057}; 1058 1059static const bool gActiveEdge[kShapeOp_Count][2][2][2][2] = { 1060// miFrom=0 miFrom=1 1061// miTo=0 miTo=1 miTo=0 miTo=1 1062// suFrom=0 1 suFrom=0 1 suFrom=0 1 suFrom=0 1 1063// suTo=0,1 suTo=0,1 suTo=0,1 suTo=0,1 suTo=0,1 suTo=0,1 suTo=0,1 suTo=0,1 1064 {{{{F, F}, {F, F}}, {{T, F}, {T, F}}}, {{{T, T}, {F, F}}, {{F, T}, {T, F}}}}, // mi - su 1065 {{{{F, F}, {F, F}}, {{F, T}, {F, T}}}, {{{F, F}, {T, T}}, {{F, T}, {T, F}}}}, // mi & su 1066 {{{{F, T}, {T, F}}, {{T, T}, {F, F}}}, {{{T, F}, {T, F}}, {{F, F}, {F, F}}}}, // mi | su 1067 {{{{F, T}, {T, F}}, {{T, F}, {F, T}}}, {{{T, F}, {F, T}}, {{F, T}, {T, F}}}}, // mi ^ su 1068}; 1069 1070#undef F 1071#undef T 1072 1073// wrap path to keep track of whether the contour is initialized and non-empty 1074class PathWrapper { 1075public: 1076 PathWrapper(SkPath& path) 1077 : fPathPtr(&path) 1078 , fCloses(0) 1079 , fMoves(0) 1080 { 1081 init(); 1082 } 1083 1084 void close() { 1085 if (!fHasMove) { 1086 return; 1087 } 1088 bool callClose = isClosed(); 1089 lineTo(); 1090 if (fEmpty) { 1091 return; 1092 } 1093 if (callClose) { 1094 #if DEBUG_PATH_CONSTRUCTION 1095 SkDebugf("path.close();\n"); 1096 #endif 1097 fPathPtr->close(); 1098 fCloses++; 1099 } 1100 init(); 1101 } 1102 1103 void cubicTo(const SkPoint& pt1, const SkPoint& pt2, const SkPoint& pt3) { 1104 lineTo(); 1105 moveTo(); 1106 fDefer[1] = pt3; 1107 nudge(); 1108 fDefer[0] = fDefer[1]; 1109#if DEBUG_PATH_CONSTRUCTION 1110 SkDebugf("path.cubicTo(%1.9g,%1.9g, %1.9g,%1.9g, %1.9g,%1.9g);\n", 1111 pt1.fX, pt1.fY, pt2.fX, pt2.fY, fDefer[1].fX, fDefer[1].fY); 1112#endif 1113 fPathPtr->cubicTo(pt1.fX, pt1.fY, pt2.fX, pt2.fY, fDefer[1].fX, fDefer[1].fY); 1114 fEmpty = false; 1115 } 1116 1117 void deferredLine(const SkPoint& pt) { 1118 if (pt == fDefer[1]) { 1119 return; 1120 } 1121 if (changedSlopes(pt)) { 1122 lineTo(); 1123 fDefer[0] = fDefer[1]; 1124 } 1125 fDefer[1] = pt; 1126 } 1127 1128 void deferredMove(const SkPoint& pt) { 1129 fMoved = true; 1130 fHasMove = true; 1131 fEmpty = true; 1132 fDefer[0] = fDefer[1] = pt; 1133 } 1134 1135 void deferredMoveLine(const SkPoint& pt) { 1136 if (!fHasMove) { 1137 deferredMove(pt); 1138 } 1139 deferredLine(pt); 1140 } 1141 1142 bool hasMove() const { 1143 return fHasMove; 1144 } 1145 1146 void init() { 1147 fEmpty = true; 1148 fHasMove = false; 1149 fMoved = false; 1150 } 1151 1152 bool isClosed() const { 1153 return !fEmpty && fFirstPt == fDefer[1]; 1154 } 1155 1156 void lineTo() { 1157 if (fDefer[0] == fDefer[1]) { 1158 return; 1159 } 1160 moveTo(); 1161 nudge(); 1162 fEmpty = false; 1163#if DEBUG_PATH_CONSTRUCTION 1164 SkDebugf("path.lineTo(%1.9g,%1.9g);\n", fDefer[1].fX, fDefer[1].fY); 1165#endif 1166 fPathPtr->lineTo(fDefer[1].fX, fDefer[1].fY); 1167 fDefer[0] = fDefer[1]; 1168 } 1169 1170 const SkPath* nativePath() const { 1171 return fPathPtr; 1172 } 1173 1174 void nudge() { 1175 if (fEmpty || !AlmostEqualUlps(fDefer[1].fX, fFirstPt.fX) 1176 || !AlmostEqualUlps(fDefer[1].fY, fFirstPt.fY)) { 1177 return; 1178 } 1179 fDefer[1] = fFirstPt; 1180 } 1181 1182 void quadTo(const SkPoint& pt1, const SkPoint& pt2) { 1183 lineTo(); 1184 moveTo(); 1185 fDefer[1] = pt2; 1186 nudge(); 1187 fDefer[0] = fDefer[1]; 1188#if DEBUG_PATH_CONSTRUCTION 1189 SkDebugf("path.quadTo(%1.9g,%1.9g, %1.9g,%1.9g);\n", 1190 pt1.fX, pt1.fY, fDefer[1].fX, fDefer[1].fY); 1191#endif 1192 fPathPtr->quadTo(pt1.fX, pt1.fY, fDefer[1].fX, fDefer[1].fY); 1193 fEmpty = false; 1194 } 1195 1196 bool someAssemblyRequired() const { 1197 return fCloses < fMoves; 1198 } 1199 1200protected: 1201 bool changedSlopes(const SkPoint& pt) const { 1202 if (fDefer[0] == fDefer[1]) { 1203 return false; 1204 } 1205 SkScalar deferDx = fDefer[1].fX - fDefer[0].fX; 1206 SkScalar deferDy = fDefer[1].fY - fDefer[0].fY; 1207 SkScalar lineDx = pt.fX - fDefer[1].fX; 1208 SkScalar lineDy = pt.fY - fDefer[1].fY; 1209 return deferDx * lineDy != deferDy * lineDx; 1210 } 1211 1212 void moveTo() { 1213 if (!fMoved) { 1214 return; 1215 } 1216 fFirstPt = fDefer[0]; 1217#if DEBUG_PATH_CONSTRUCTION 1218 SkDebugf("path.moveTo(%1.9g,%1.9g);\n", fDefer[0].fX, fDefer[0].fY); 1219#endif 1220 fPathPtr->moveTo(fDefer[0].fX, fDefer[0].fY); 1221 fMoved = false; 1222 fMoves++; 1223 } 1224 1225private: 1226 SkPath* fPathPtr; 1227 SkPoint fDefer[2]; 1228 SkPoint fFirstPt; 1229 int fCloses; 1230 int fMoves; 1231 bool fEmpty; 1232 bool fHasMove; 1233 bool fMoved; 1234}; 1235 1236class Segment { 1237public: 1238 Segment() { 1239#if DEBUG_DUMP 1240 fID = ++gSegmentID; 1241#endif 1242 } 1243 1244 bool operator<(const Segment& rh) const { 1245 return fBounds.fTop < rh.fBounds.fTop; 1246 } 1247 1248 bool activeAngle(int index, int& done, SkTDArray<Angle>& angles) { 1249 if (activeAngleInner(index, done, angles)) { 1250 return true; 1251 } 1252 int lesser = index; 1253 while (--lesser >= 0 && equalPoints(index, lesser)) { 1254 if (activeAngleOther(lesser, done, angles)) { 1255 return true; 1256 } 1257 } 1258 lesser = index; 1259 do { 1260 if (activeAngleOther(index, done, angles)) { 1261 return true; 1262 } 1263 } while (++index < fTs.count() && equalPoints(index, lesser)); 1264 return false; 1265 } 1266 1267 bool activeAngleOther(int index, int& done, SkTDArray<Angle>& angles) { 1268 Span* span = &fTs[index]; 1269 Segment* other = span->fOther; 1270 int oIndex = span->fOtherIndex; 1271 return other->activeAngleInner(oIndex, done, angles); 1272 } 1273 1274 bool activeAngleInner(int index, int& done, SkTDArray<Angle>& angles) { 1275 int next = nextExactSpan(index, 1); 1276 if (next > 0) { 1277 Span& upSpan = fTs[index]; 1278 if (upSpan.fWindValue || upSpan.fOppValue) { 1279 addAngle(angles, index, next); 1280 if (upSpan.fDone || upSpan.fUnsortableEnd) { 1281 done++; 1282 } else if (upSpan.fWindSum != SK_MinS32) { 1283 return true; 1284 } 1285 } else if (!upSpan.fDone) { 1286 upSpan.fDone = true; 1287 fDoneSpans++; 1288 } 1289 } 1290 int prev = nextExactSpan(index, -1); 1291 // edge leading into junction 1292 if (prev >= 0) { 1293 Span& downSpan = fTs[prev]; 1294 if (downSpan.fWindValue || downSpan.fOppValue) { 1295 addAngle(angles, index, prev); 1296 if (downSpan.fDone) { 1297 done++; 1298 } else if (downSpan.fWindSum != SK_MinS32) { 1299 return true; 1300 } 1301 } else if (!downSpan.fDone) { 1302 downSpan.fDone = true; 1303 fDoneSpans++; 1304 } 1305 } 1306 return false; 1307 } 1308 1309 SkPoint activeLeftTop(bool onlySortable, int* firstT) const { 1310 SkASSERT(!done()); 1311 SkPoint topPt = {SK_ScalarMax, SK_ScalarMax}; 1312 int count = fTs.count(); 1313 // see if either end is not done since we want smaller Y of the pair 1314 bool lastDone = true; 1315 bool lastUnsortable = false; 1316 double lastT = -1; 1317 for (int index = 0; index < count; ++index) { 1318 const Span& span = fTs[index]; 1319 if (onlySortable && (span.fUnsortableStart || lastUnsortable)) { 1320 goto next; 1321 } 1322 if (span.fDone && lastDone) { 1323 goto next; 1324 } 1325 if (approximately_negative(span.fT - lastT)) { 1326 goto next; 1327 } 1328 { 1329 const SkPoint& xy = xyAtT(&span); 1330 if (topPt.fY > xy.fY || (topPt.fY == xy.fY && topPt.fX > xy.fX)) { 1331 topPt = xy; 1332 if (firstT) { 1333 *firstT = index; 1334 } 1335 } 1336 if (fVerb != SkPath::kLine_Verb && !lastDone) { 1337 SkPoint curveTop = (*SegmentTop[fVerb])(fPts, lastT, span.fT); 1338 if (topPt.fY > curveTop.fY || (topPt.fY == curveTop.fY 1339 && topPt.fX > curveTop.fX)) { 1340 topPt = curveTop; 1341 if (firstT) { 1342 *firstT = index; 1343 } 1344 } 1345 } 1346 lastT = span.fT; 1347 } 1348 next: 1349 lastDone = span.fDone; 1350 lastUnsortable = span.fUnsortableEnd; 1351 } 1352 return topPt; 1353 } 1354 1355 bool activeOp(int index, int endIndex, int xorMiMask, int xorSuMask, ShapeOp op) { 1356 int sumMiWinding = updateWinding(endIndex, index); 1357 int sumSuWinding = updateOppWinding(endIndex, index); 1358 if (fOperand) { 1359 SkTSwap<int>(sumMiWinding, sumSuWinding); 1360 } 1361 int maxWinding, sumWinding, oppMaxWinding, oppSumWinding; 1362 return activeOp(xorMiMask, xorSuMask, index, endIndex, op, sumMiWinding, sumSuWinding, 1363 maxWinding, sumWinding, oppMaxWinding, oppSumWinding); 1364 } 1365 1366 bool activeOp(int xorMiMask, int xorSuMask, int index, int endIndex, ShapeOp op, 1367 int& sumMiWinding, int& sumSuWinding, 1368 int& maxWinding, int& sumWinding, int& oppMaxWinding, int& oppSumWinding) { 1369 setUpWindings(index, endIndex, sumMiWinding, sumSuWinding, 1370 maxWinding, sumWinding, oppMaxWinding, oppSumWinding); 1371 bool miFrom; 1372 bool miTo; 1373 bool suFrom; 1374 bool suTo; 1375 if (operand()) { 1376 miFrom = (oppMaxWinding & xorMiMask) != 0; 1377 miTo = (oppSumWinding & xorMiMask) != 0; 1378 suFrom = (maxWinding & xorSuMask) != 0; 1379 suTo = (sumWinding & xorSuMask) != 0; 1380 } else { 1381 miFrom = (maxWinding & xorMiMask) != 0; 1382 miTo = (sumWinding & xorMiMask) != 0; 1383 suFrom = (oppMaxWinding & xorSuMask) != 0; 1384 suTo = (oppSumWinding & xorSuMask) != 0; 1385 } 1386 bool result = gActiveEdge[op][miFrom][miTo][suFrom][suTo]; 1387#if DEBUG_ACTIVE_OP 1388 SkDebugf("%s op=%s miFrom=%d miTo=%d suFrom=%d suTo=%d result=%d\n", __FUNCTION__, 1389 kShapeOpStr[op], miFrom, miTo, suFrom, suTo, result); 1390#endif 1391 SkASSERT(result != -1); 1392 return result; 1393 } 1394 1395 bool activeWinding(int index, int endIndex) { 1396 int sumWinding = updateWinding(endIndex, index); 1397 int maxWinding; 1398 return activeWinding(index, endIndex, maxWinding, sumWinding); 1399 } 1400 1401 bool activeWinding(int index, int endIndex, int& maxWinding, int& sumWinding) { 1402 setUpWinding(index, endIndex, maxWinding, sumWinding); 1403 bool from = maxWinding != 0; 1404 bool to = sumWinding != 0; 1405 bool result = gUnaryActiveEdge[from][to]; 1406 SkASSERT(result != -1); 1407 return result; 1408 } 1409 1410 void addAngle(SkTDArray<Angle>& angles, int start, int end) const { 1411 SkASSERT(start != end); 1412 Angle* angle = angles.append(); 1413#if DEBUG_ANGLE 1414 if (angles.count() > 1 && !fTs[start].fTiny) { 1415 SkPoint angle0Pt, newPt; 1416 (*SegmentXYAtT[angles[0].verb()])(angles[0].pts(), 1417 (*angles[0].spans())[angles[0].start()].fT, &angle0Pt); 1418 (*SegmentXYAtT[fVerb])(fPts, fTs[start].fT, &newPt); 1419 SkASSERT(AlmostEqualUlps(angle0Pt.fX, newPt.fX)); 1420 SkASSERT(AlmostEqualUlps(angle0Pt.fY, newPt.fY)); 1421 } 1422#endif 1423 angle->set(fPts, fVerb, this, start, end, fTs); 1424 } 1425 1426 void addCancelOutsides(double tStart, double oStart, Segment& other, 1427 double oEnd) { 1428 int tIndex = -1; 1429 int tCount = fTs.count(); 1430 int oIndex = -1; 1431 int oCount = other.fTs.count(); 1432 do { 1433 ++tIndex; 1434 } while (!approximately_negative(tStart - fTs[tIndex].fT) && tIndex < tCount); 1435 int tIndexStart = tIndex; 1436 do { 1437 ++oIndex; 1438 } while (!approximately_negative(oStart - other.fTs[oIndex].fT) && oIndex < oCount); 1439 int oIndexStart = oIndex; 1440 double nextT; 1441 do { 1442 nextT = fTs[++tIndex].fT; 1443 } while (nextT < 1 && approximately_negative(nextT - tStart)); 1444 double oNextT; 1445 do { 1446 oNextT = other.fTs[++oIndex].fT; 1447 } while (oNextT < 1 && approximately_negative(oNextT - oStart)); 1448 // at this point, spans before and after are at: 1449 // fTs[tIndexStart - 1], fTs[tIndexStart], fTs[tIndex] 1450 // if tIndexStart == 0, no prior span 1451 // if nextT == 1, no following span 1452 1453 // advance the span with zero winding 1454 // if the following span exists (not past the end, non-zero winding) 1455 // connect the two edges 1456 if (!fTs[tIndexStart].fWindValue) { 1457 if (tIndexStart > 0 && fTs[tIndexStart - 1].fWindValue) { 1458 #if DEBUG_CONCIDENT 1459 SkDebugf("%s 1 this=%d other=%d t [%d] %1.9g (%1.9g,%1.9g)\n", 1460 __FUNCTION__, fID, other.fID, tIndexStart - 1, 1461 fTs[tIndexStart].fT, xyAtT(tIndexStart).fX, 1462 xyAtT(tIndexStart).fY); 1463 #endif 1464 addTPair(fTs[tIndexStart].fT, other, other.fTs[oIndex].fT, false, 1465 fTs[tIndexStart].fPt); 1466 } 1467 if (nextT < 1 && fTs[tIndex].fWindValue) { 1468 #if DEBUG_CONCIDENT 1469 SkDebugf("%s 2 this=%d other=%d t [%d] %1.9g (%1.9g,%1.9g)\n", 1470 __FUNCTION__, fID, other.fID, tIndex, 1471 fTs[tIndex].fT, xyAtT(tIndex).fX, 1472 xyAtT(tIndex).fY); 1473 #endif 1474 addTPair(fTs[tIndex].fT, other, other.fTs[oIndexStart].fT, false, fTs[tIndex].fPt); 1475 } 1476 } else { 1477 SkASSERT(!other.fTs[oIndexStart].fWindValue); 1478 if (oIndexStart > 0 && other.fTs[oIndexStart - 1].fWindValue) { 1479 #if DEBUG_CONCIDENT 1480 SkDebugf("%s 3 this=%d other=%d t [%d] %1.9g (%1.9g,%1.9g)\n", 1481 __FUNCTION__, fID, other.fID, oIndexStart - 1, 1482 other.fTs[oIndexStart].fT, other.xyAtT(oIndexStart).fX, 1483 other.xyAtT(oIndexStart).fY); 1484 other.debugAddTPair(other.fTs[oIndexStart].fT, *this, fTs[tIndex].fT); 1485 #endif 1486 } 1487 if (oNextT < 1 && other.fTs[oIndex].fWindValue) { 1488 #if DEBUG_CONCIDENT 1489 SkDebugf("%s 4 this=%d other=%d t [%d] %1.9g (%1.9g,%1.9g)\n", 1490 __FUNCTION__, fID, other.fID, oIndex, 1491 other.fTs[oIndex].fT, other.xyAtT(oIndex).fX, 1492 other.xyAtT(oIndex).fY); 1493 other.debugAddTPair(other.fTs[oIndex].fT, *this, fTs[tIndexStart].fT); 1494 #endif 1495 } 1496 } 1497 } 1498 1499 void addCoinOutsides(const SkTDArray<double>& outsideTs, Segment& other, 1500 double oEnd) { 1501 // walk this to outsideTs[0] 1502 // walk other to outsideTs[1] 1503 // if either is > 0, add a pointer to the other, copying adjacent winding 1504 int tIndex = -1; 1505 int oIndex = -1; 1506 double tStart = outsideTs[0]; 1507 double oStart = outsideTs[1]; 1508 do { 1509 ++tIndex; 1510 } while (!approximately_negative(tStart - fTs[tIndex].fT)); 1511 SkPoint ptStart = fTs[tIndex].fPt; 1512 do { 1513 ++oIndex; 1514 } while (!approximately_negative(oStart - other.fTs[oIndex].fT)); 1515 if (tIndex > 0 || oIndex > 0 || fOperand != other.fOperand) { 1516 addTPair(tStart, other, oStart, false, ptStart); 1517 } 1518 tStart = fTs[tIndex].fT; 1519 oStart = other.fTs[oIndex].fT; 1520 do { 1521 double nextT; 1522 do { 1523 nextT = fTs[++tIndex].fT; 1524 } while (approximately_negative(nextT - tStart)); 1525 tStart = nextT; 1526 ptStart = fTs[tIndex].fPt; 1527 do { 1528 nextT = other.fTs[++oIndex].fT; 1529 } while (approximately_negative(nextT - oStart)); 1530 oStart = nextT; 1531 if (tStart == 1 && oStart == 1 && fOperand == other.fOperand) { 1532 break; 1533 } 1534 addTPair(tStart, other, oStart, false, ptStart); 1535 } while (tStart < 1 && oStart < 1 && !approximately_negative(oEnd - oStart)); 1536 } 1537 1538 void addCubic(const SkPoint pts[4], bool operand, bool evenOdd) { 1539 init(pts, SkPath::kCubic_Verb, operand, evenOdd); 1540 fBounds.setCubicBounds(pts); 1541 } 1542 1543 /* SkPoint */ void addCurveTo(int start, int end, PathWrapper& path, bool active) const { 1544 SkPoint edge[4]; 1545 const SkPoint* ePtr; 1546 int lastT = fTs.count() - 1; 1547 if (lastT < 0 || (start == 0 && end == lastT) || (start == lastT && end == 0)) { 1548 ePtr = fPts; 1549 } else { 1550 // OPTIMIZE? if not active, skip remainder and return xy_at_t(end) 1551 (*SegmentSubDivide[fVerb])(fPts, fTs[start].fT, fTs[end].fT, edge); 1552 ePtr = edge; 1553 } 1554 if (active) { 1555 bool reverse = ePtr == fPts && start != 0; 1556 if (reverse) { 1557 path.deferredMoveLine(ePtr[fVerb]); 1558 switch (fVerb) { 1559 case SkPath::kLine_Verb: 1560 path.deferredLine(ePtr[0]); 1561 break; 1562 case SkPath::kQuad_Verb: 1563 path.quadTo(ePtr[1], ePtr[0]); 1564 break; 1565 case SkPath::kCubic_Verb: 1566 path.cubicTo(ePtr[2], ePtr[1], ePtr[0]); 1567 break; 1568 default: 1569 SkASSERT(0); 1570 } 1571 // return ePtr[0]; 1572 } else { 1573 path.deferredMoveLine(ePtr[0]); 1574 switch (fVerb) { 1575 case SkPath::kLine_Verb: 1576 path.deferredLine(ePtr[1]); 1577 break; 1578 case SkPath::kQuad_Verb: 1579 path.quadTo(ePtr[1], ePtr[2]); 1580 break; 1581 case SkPath::kCubic_Verb: 1582 path.cubicTo(ePtr[1], ePtr[2], ePtr[3]); 1583 break; 1584 default: 1585 SkASSERT(0); 1586 } 1587 } 1588 } 1589 // return ePtr[fVerb]; 1590 } 1591 1592 void addLine(const SkPoint pts[2], bool operand, bool evenOdd) { 1593 init(pts, SkPath::kLine_Verb, operand, evenOdd); 1594 fBounds.set(pts, 2); 1595 } 1596 1597#if 0 1598 const SkPoint& addMoveTo(int tIndex, PathWrapper& path, bool active) const { 1599 const SkPoint& pt = xyAtT(tIndex); 1600 if (active) { 1601 path.deferredMove(pt); 1602 } 1603 return pt; 1604 } 1605#endif 1606 1607 // add 2 to edge or out of range values to get T extremes 1608 void addOtherT(int index, double otherT, int otherIndex) { 1609 Span& span = fTs[index]; 1610 #if PIN_ADD_T 1611 if (precisely_less_than_zero(otherT)) { 1612 otherT = 0; 1613 } else if (precisely_greater_than_one(otherT)) { 1614 otherT = 1; 1615 } 1616 #endif 1617 span.fOtherT = otherT; 1618 span.fOtherIndex = otherIndex; 1619 } 1620 1621 void addQuad(const SkPoint pts[3], bool operand, bool evenOdd) { 1622 init(pts, SkPath::kQuad_Verb, operand, evenOdd); 1623 fBounds.setQuadBounds(pts); 1624 } 1625 1626 // Defer all coincident edge processing until 1627 // after normal intersections have been computed 1628 1629// no need to be tricky; insert in normal T order 1630// resolve overlapping ts when considering coincidence later 1631 1632 // add non-coincident intersection. Resulting edges are sorted in T. 1633 int addT(double newT, Segment* other, const SkPoint& pt) { 1634 // FIXME: in the pathological case where there is a ton of intercepts, 1635 // binary search? 1636 int insertedAt = -1; 1637 size_t tCount = fTs.count(); 1638 #if PIN_ADD_T 1639 // FIXME: only do this pinning here (e.g. this is done also in quad/line intersect) 1640 if (precisely_less_than_zero(newT)) { 1641 newT = 0; 1642 } else if (precisely_greater_than_one(newT)) { 1643 newT = 1; 1644 } 1645 #endif 1646 for (size_t index = 0; index < tCount; ++index) { 1647 // OPTIMIZATION: if there are three or more identical Ts, then 1648 // the fourth and following could be further insertion-sorted so 1649 // that all the edges are clockwise or counterclockwise. 1650 // This could later limit segment tests to the two adjacent 1651 // neighbors, although it doesn't help with determining which 1652 // circular direction to go in. 1653 if (newT < fTs[index].fT) { 1654 insertedAt = index; 1655 break; 1656 } 1657 } 1658 Span* span; 1659 if (insertedAt >= 0) { 1660 span = fTs.insert(insertedAt); 1661 } else { 1662 insertedAt = tCount; 1663 span = fTs.append(); 1664 } 1665 span->fT = newT; 1666 span->fOther = other; 1667 span->fPt = pt; 1668 span->fWindSum = SK_MinS32; 1669 span->fOppSum = SK_MinS32; 1670 span->fWindValue = 1; 1671 span->fOppValue = 0; 1672 span->fTiny = false; 1673 if ((span->fDone = newT == 1)) { 1674 ++fDoneSpans; 1675 } 1676 span->fUnsortableStart = false; 1677 span->fUnsortableEnd = false; 1678 int less = -1; 1679 while (&span[less + 1] - fTs.begin() > 0 && !span[less].fDone 1680 && !precisely_negative(newT - span[less].fT) 1681 // && approximately_negative(newT - span[less].fT) 1682 && xyAtT(&span[less]) == xyAtT(span)) { 1683 span[less].fTiny = true; 1684 span[less].fDone = true; 1685 if (approximately_negative(newT - span[less].fT)) { 1686 if (approximately_greater_than_one(newT)) { 1687 span[less].fUnsortableStart = true; 1688 span[less - 1].fUnsortableEnd = true; 1689 } 1690 if (approximately_less_than_zero(span[less].fT)) { 1691 span[less + 1].fUnsortableStart = true; 1692 span[less].fUnsortableEnd = true; 1693 } 1694 } 1695 ++fDoneSpans; 1696 --less; 1697 } 1698 int more = 1; 1699 while (fTs.end() - &span[more - 1] > 1 && !span[more - 1].fDone 1700 && !precisely_negative(span[more].fT - newT) 1701 // && approximately_negative(span[more].fT - newT) 1702 && xyAtT(&span[more]) == xyAtT(span)) { 1703 span[more - 1].fTiny = true; 1704 span[more - 1].fDone = true; 1705 if (approximately_negative(span[more].fT - newT)) { 1706 if (approximately_greater_than_one(span[more].fT)) { 1707 span[more + 1].fUnsortableStart = true; 1708 span[more].fUnsortableEnd = true; 1709 } 1710 if (approximately_less_than_zero(newT)) { 1711 span[more].fUnsortableStart = true; 1712 span[more - 1].fUnsortableEnd = true; 1713 } 1714 } 1715 ++fDoneSpans; 1716 ++more; 1717 } 1718 return insertedAt; 1719 } 1720 1721 // set spans from start to end to decrement by one 1722 // note this walks other backwards 1723 // FIMXE: there's probably an edge case that can be constructed where 1724 // two span in one segment are separated by float epsilon on one span but 1725 // not the other, if one segment is very small. For this 1726 // case the counts asserted below may or may not be enough to separate the 1727 // spans. Even if the counts work out, what if the spans aren't correctly 1728 // sorted? It feels better in such a case to match the span's other span 1729 // pointer since both coincident segments must contain the same spans. 1730 void addTCancel(double startT, double endT, Segment& other, 1731 double oStartT, double oEndT) { 1732 SkASSERT(!approximately_negative(endT - startT)); 1733 SkASSERT(!approximately_negative(oEndT - oStartT)); 1734 bool binary = fOperand != other.fOperand; 1735 int index = 0; 1736 while (!approximately_negative(startT - fTs[index].fT)) { 1737 ++index; 1738 } 1739 int oIndex = other.fTs.count(); 1740 while (approximately_positive(other.fTs[--oIndex].fT - oEndT)) 1741 ; 1742 double tRatio = (oEndT - oStartT) / (endT - startT); 1743 Span* test = &fTs[index]; 1744 Span* oTest = &other.fTs[oIndex]; 1745 SkTDArray<double> outsideTs; 1746 SkTDArray<double> oOutsideTs; 1747 do { 1748 bool decrement = test->fWindValue && oTest->fWindValue && !binary; 1749 bool track = test->fWindValue || oTest->fWindValue; 1750 double testT = test->fT; 1751 double oTestT = oTest->fT; 1752 Span* span = test; 1753 do { 1754 if (decrement) { 1755 decrementSpan(span); 1756 } else if (track && span->fT < 1 && oTestT < 1) { 1757 TrackOutside(outsideTs, span->fT, oTestT); 1758 } 1759 span = &fTs[++index]; 1760 } while (approximately_negative(span->fT - testT)); 1761 Span* oSpan = oTest; 1762 double otherTMatchStart = oEndT - (span->fT - startT) * tRatio; 1763 double otherTMatchEnd = oEndT - (test->fT - startT) * tRatio; 1764 SkDEBUGCODE(int originalWindValue = oSpan->fWindValue); 1765 while (approximately_negative(otherTMatchStart - oSpan->fT) 1766 && !approximately_negative(otherTMatchEnd - oSpan->fT)) { 1767 #ifdef SK_DEBUG 1768 SkASSERT(originalWindValue == oSpan->fWindValue); 1769 #endif 1770 if (decrement) { 1771 other.decrementSpan(oSpan); 1772 } else if (track && oSpan->fT < 1 && testT < 1) { 1773 TrackOutside(oOutsideTs, oSpan->fT, testT); 1774 } 1775 if (!oIndex) { 1776 break; 1777 } 1778 oSpan = &other.fTs[--oIndex]; 1779 } 1780 test = span; 1781 oTest = oSpan; 1782 } while (!approximately_negative(endT - test->fT)); 1783 SkASSERT(!oIndex || approximately_negative(oTest->fT - oStartT)); 1784 // FIXME: determine if canceled edges need outside ts added 1785 if (!done() && outsideTs.count()) { 1786 double tStart = outsideTs[0]; 1787 double oStart = outsideTs[1]; 1788 addCancelOutsides(tStart, oStart, other, oEndT); 1789 int count = outsideTs.count(); 1790 if (count > 2) { 1791 double tStart = outsideTs[count - 2]; 1792 double oStart = outsideTs[count - 1]; 1793 addCancelOutsides(tStart, oStart, other, oEndT); 1794 } 1795 } 1796 if (!other.done() && oOutsideTs.count()) { 1797 double tStart = oOutsideTs[0]; 1798 double oStart = oOutsideTs[1]; 1799 other.addCancelOutsides(tStart, oStart, *this, endT); 1800 } 1801 } 1802 1803 int addUnsortableT(double newT, Segment* other, bool start, const SkPoint& pt) { 1804 int result = addT(newT, other, pt); 1805 Span* span = &fTs[result]; 1806 if (start) { 1807 if (result > 0) { 1808 span[result - 1].fUnsortableEnd = true; 1809 } 1810 span[result].fUnsortableStart = true; 1811 } else { 1812 span[result].fUnsortableEnd = true; 1813 if (result + 1 < fTs.count()) { 1814 span[result + 1].fUnsortableStart = true; 1815 } 1816 } 1817 return result; 1818 } 1819 1820 int bumpCoincidentThis(const Span* oTest, bool opp, int index, 1821 SkTDArray<double>& outsideTs) { 1822 int oWindValue = oTest->fWindValue; 1823 int oOppValue = oTest->fOppValue; 1824 if (opp) { 1825 SkTSwap<int>(oWindValue, oOppValue); 1826 } 1827 Span* const test = &fTs[index]; 1828 Span* end = test; 1829 const double oStartT = oTest->fT; 1830 do { 1831 if (bumpSpan(end, oWindValue, oOppValue)) { 1832 TrackOutside(outsideTs, end->fT, oStartT); 1833 } 1834 end = &fTs[++index]; 1835 } while (approximately_negative(end->fT - test->fT)); 1836 return index; 1837 } 1838 1839 // because of the order in which coincidences are resolved, this and other 1840 // may not have the same intermediate points. Compute the corresponding 1841 // intermediate T values (using this as the master, other as the follower) 1842 // and walk other conditionally -- hoping that it catches up in the end 1843 int bumpCoincidentOther(const Span* test, double oEndT, int& oIndex, 1844 SkTDArray<double>& oOutsideTs) { 1845 Span* const oTest = &fTs[oIndex]; 1846 Span* oEnd = oTest; 1847 const double startT = test->fT; 1848 const double oStartT = oTest->fT; 1849 while (!approximately_negative(oEndT - oEnd->fT) 1850 && approximately_negative(oEnd->fT - oStartT)) { 1851 zeroSpan(oEnd); 1852 TrackOutside(oOutsideTs, oEnd->fT, startT); 1853 oEnd = &fTs[++oIndex]; 1854 } 1855 return oIndex; 1856 } 1857 1858 // FIXME: need to test this case: 1859 // contourA has two segments that are coincident 1860 // contourB has two segments that are coincident in the same place 1861 // each ends up with +2/0 pairs for winding count 1862 // since logic below doesn't transfer count (only increments/decrements) can this be 1863 // resolved to +4/0 ? 1864 1865 // set spans from start to end to increment the greater by one and decrement 1866 // the lesser 1867 void addTCoincident(double startT, double endT, Segment& other, double oStartT, double oEndT) { 1868 SkASSERT(!approximately_negative(endT - startT)); 1869 SkASSERT(!approximately_negative(oEndT - oStartT)); 1870 bool opp = fOperand ^ other.fOperand; 1871 int index = 0; 1872 while (!approximately_negative(startT - fTs[index].fT)) { 1873 ++index; 1874 } 1875 int oIndex = 0; 1876 while (!approximately_negative(oStartT - other.fTs[oIndex].fT)) { 1877 ++oIndex; 1878 } 1879 Span* test = &fTs[index]; 1880 Span* oTest = &other.fTs[oIndex]; 1881 SkTDArray<double> outsideTs; 1882 SkTDArray<double> oOutsideTs; 1883 do { 1884 // if either span has an opposite value and the operands don't match, resolve first 1885 // SkASSERT(!test->fDone || !oTest->fDone); 1886 if (test->fDone || oTest->fDone) { 1887 index = advanceCoincidentThis(oTest, opp, index); 1888 oIndex = other.advanceCoincidentOther(test, oEndT, oIndex); 1889 } else { 1890 index = bumpCoincidentThis(oTest, opp, index, outsideTs); 1891 oIndex = other.bumpCoincidentOther(test, oEndT, oIndex, oOutsideTs); 1892 } 1893 test = &fTs[index]; 1894 oTest = &other.fTs[oIndex]; 1895 } while (!approximately_negative(endT - test->fT)); 1896 SkASSERT(approximately_negative(oTest->fT - oEndT)); 1897 SkASSERT(approximately_negative(oEndT - oTest->fT)); 1898 if (!done() && outsideTs.count()) { 1899 addCoinOutsides(outsideTs, other, oEndT); 1900 } 1901 if (!other.done() && oOutsideTs.count()) { 1902 other.addCoinOutsides(oOutsideTs, *this, endT); 1903 } 1904 } 1905 1906 // FIXME: this doesn't prevent the same span from being added twice 1907 // fix in caller, SkASSERT here? 1908 void addTPair(double t, Segment& other, double otherT, bool borrowWind, const SkPoint& pt) { 1909 int tCount = fTs.count(); 1910 for (int tIndex = 0; tIndex < tCount; ++tIndex) { 1911 const Span& span = fTs[tIndex]; 1912 if (!approximately_negative(span.fT - t)) { 1913 break; 1914 } 1915 if (approximately_negative(span.fT - t) && span.fOther == &other 1916 && approximately_equal(span.fOtherT, otherT)) { 1917#if DEBUG_ADD_T_PAIR 1918 SkDebugf("%s addTPair duplicate this=%d %1.9g other=%d %1.9g\n", 1919 __FUNCTION__, fID, t, other.fID, otherT); 1920#endif 1921 return; 1922 } 1923 } 1924#if DEBUG_ADD_T_PAIR 1925 SkDebugf("%s addTPair this=%d %1.9g other=%d %1.9g\n", 1926 __FUNCTION__, fID, t, other.fID, otherT); 1927#endif 1928 int insertedAt = addT(t, &other, pt); 1929 int otherInsertedAt = other.addT(otherT, this, pt); 1930 addOtherT(insertedAt, otherT, otherInsertedAt); 1931 other.addOtherT(otherInsertedAt, t, insertedAt); 1932 matchWindingValue(insertedAt, t, borrowWind); 1933 other.matchWindingValue(otherInsertedAt, otherT, borrowWind); 1934 } 1935 1936 void addTwoAngles(int start, int end, SkTDArray<Angle>& angles) const { 1937 // add edge leading into junction 1938 int min = SkMin32(end, start); 1939 if (fTs[min].fWindValue > 0 || fTs[min].fOppValue > 0) { 1940 addAngle(angles, end, start); 1941 } 1942 // add edge leading away from junction 1943 int step = SkSign32(end - start); 1944 int tIndex = nextExactSpan(end, step); 1945 min = SkMin32(end, tIndex); 1946 if (tIndex >= 0 && (fTs[min].fWindValue > 0 || fTs[min].fOppValue > 0)) { 1947 addAngle(angles, end, tIndex); 1948 } 1949 } 1950 1951 int advanceCoincidentThis(const Span* oTest, bool opp, int index) { 1952 Span* const test = &fTs[index]; 1953 Span* end = test; 1954 do { 1955 end = &fTs[++index]; 1956 } while (approximately_negative(end->fT - test->fT)); 1957 return index; 1958 } 1959 1960 int advanceCoincidentOther(const Span* test, double oEndT, int& oIndex) { 1961 Span* const oTest = &fTs[oIndex]; 1962 Span* oEnd = oTest; 1963 const double oStartT = oTest->fT; 1964 while (!approximately_negative(oEndT - oEnd->fT) 1965 && approximately_negative(oEnd->fT - oStartT)) { 1966 oEnd = &fTs[++oIndex]; 1967 } 1968 return oIndex; 1969 } 1970 1971 bool betweenTs(int lesser, double testT, int greater) { 1972 if (lesser > greater) { 1973 SkTSwap<int>(lesser, greater); 1974 } 1975 return approximately_between(fTs[lesser].fT, testT, fTs[greater].fT); 1976 } 1977 1978 const Bounds& bounds() const { 1979 return fBounds; 1980 } 1981 1982 void buildAngles(int index, SkTDArray<Angle>& angles, bool includeOpp) const { 1983 double referenceT = fTs[index].fT; 1984 int lesser = index; 1985 while (--lesser >= 0 && (includeOpp || fTs[lesser].fOther->fOperand == fOperand) 1986 && precisely_negative(referenceT - fTs[lesser].fT)) { 1987 buildAnglesInner(lesser, angles); 1988 } 1989 do { 1990 buildAnglesInner(index, angles); 1991 } while (++index < fTs.count() && (includeOpp || fTs[index].fOther->fOperand == fOperand) 1992 && precisely_negative(fTs[index].fT - referenceT)); 1993 } 1994 1995 void buildAnglesInner(int index, SkTDArray<Angle>& angles) const { 1996 Span* span = &fTs[index]; 1997 Segment* other = span->fOther; 1998 // if there is only one live crossing, and no coincidence, continue 1999 // in the same direction 2000 // if there is coincidence, the only choice may be to reverse direction 2001 // find edge on either side of intersection 2002 int oIndex = span->fOtherIndex; 2003 // if done == -1, prior span has already been processed 2004 int step = 1; 2005 int next = other->nextExactSpan(oIndex, step); 2006 if (next < 0) { 2007 step = -step; 2008 next = other->nextExactSpan(oIndex, step); 2009 } 2010 // add candidate into and away from junction 2011 other->addTwoAngles(next, oIndex, angles); 2012 } 2013 2014 int computeSum(int startIndex, int endIndex, bool binary) { 2015 SkTDArray<Angle> angles; 2016 addTwoAngles(startIndex, endIndex, angles); 2017 buildAngles(endIndex, angles, false); 2018 // OPTIMIZATION: check all angles to see if any have computed wind sum 2019 // before sorting (early exit if none) 2020 SkTDArray<Angle*> sorted; 2021 bool sortable = SortAngles(angles, sorted); 2022#if DEBUG_SORT 2023 sorted[0]->segment()->debugShowSort(__FUNCTION__, sorted, 0, 0, 0); 2024#endif 2025 if (!sortable) { 2026 return SK_MinS32; 2027 } 2028 int angleCount = angles.count(); 2029 const Angle* angle; 2030 const Segment* base; 2031 int winding; 2032 int oWinding; 2033 int firstIndex = 0; 2034 do { 2035 angle = sorted[firstIndex]; 2036 base = angle->segment(); 2037 winding = base->windSum(angle); 2038 if (winding != SK_MinS32) { 2039 oWinding = base->oppSum(angle); 2040 break; 2041 } 2042 if (++firstIndex == angleCount) { 2043 return SK_MinS32; 2044 } 2045 } while (true); 2046 // turn winding into contourWinding 2047 int spanWinding = base->spanSign(angle); 2048 bool inner = useInnerWinding(winding + spanWinding, winding); 2049 #if DEBUG_WINDING 2050 SkDebugf("%s spanWinding=%d winding=%d sign=%d inner=%d result=%d\n", __FUNCTION__, 2051 spanWinding, winding, angle->sign(), inner, 2052 inner ? winding + spanWinding : winding); 2053 #endif 2054 if (inner) { 2055 winding += spanWinding; 2056 } 2057 #if DEBUG_SORT 2058 base->debugShowSort(__FUNCTION__, sorted, firstIndex, winding, oWinding); 2059 #endif 2060 int nextIndex = firstIndex + 1; 2061 int lastIndex = firstIndex != 0 ? firstIndex : angleCount; 2062 winding -= base->spanSign(angle); 2063 oWinding -= base->oppSign(angle); 2064 do { 2065 if (nextIndex == angleCount) { 2066 nextIndex = 0; 2067 } 2068 angle = sorted[nextIndex]; 2069 Segment* segment = angle->segment(); 2070 bool opp = base->fOperand ^ segment->fOperand; 2071 int maxWinding, oMaxWinding; 2072 int spanSign = segment->spanSign(angle); 2073 int oppoSign = segment->oppSign(angle); 2074 if (opp) { 2075 oMaxWinding = oWinding; 2076 oWinding -= spanSign; 2077 maxWinding = winding; 2078 if (oppoSign) { 2079 winding -= oppoSign; 2080 } 2081 } else { 2082 maxWinding = winding; 2083 winding -= spanSign; 2084 oMaxWinding = oWinding; 2085 if (oppoSign) { 2086 oWinding -= oppoSign; 2087 } 2088 } 2089 if (segment->windSum(angle) == SK_MinS32) { 2090 if (opp) { 2091 if (useInnerWinding(oMaxWinding, oWinding)) { 2092 oMaxWinding = oWinding; 2093 } 2094 if (oppoSign && useInnerWinding(maxWinding, winding)) { 2095 maxWinding = winding; 2096 } 2097 (void) segment->markAndChaseWinding(angle, oMaxWinding, maxWinding); 2098 } else { 2099 if (useInnerWinding(maxWinding, winding)) { 2100 maxWinding = winding; 2101 } 2102 if (oppoSign && useInnerWinding(oMaxWinding, oWinding)) { 2103 oMaxWinding = oWinding; 2104 } 2105 (void) segment->markAndChaseWinding(angle, maxWinding, 2106 binary ? oMaxWinding : 0); 2107 } 2108 } 2109 } while (++nextIndex != lastIndex); 2110 int minIndex = SkMin32(startIndex, endIndex); 2111 return windSum(minIndex); 2112 } 2113 2114 int crossedSpanY(const SkPoint& basePt, SkScalar& bestY, double& hitT, bool& hitSomething, 2115 double mid, bool opp, bool current) const { 2116 SkScalar bottom = fBounds.fBottom; 2117 int bestTIndex = -1; 2118 if (bottom <= bestY) { 2119 return bestTIndex; 2120 } 2121 SkScalar top = fBounds.fTop; 2122 if (top >= basePt.fY) { 2123 return bestTIndex; 2124 } 2125 if (fBounds.fLeft > basePt.fX) { 2126 return bestTIndex; 2127 } 2128 if (fBounds.fRight < basePt.fX) { 2129 return bestTIndex; 2130 } 2131 if (fBounds.fLeft == fBounds.fRight) { 2132 // if vertical, and directly above test point, wait for another one 2133 return AlmostEqualUlps(basePt.fX, fBounds.fLeft) ? SK_MinS32 : bestTIndex; 2134 } 2135 // intersect ray starting at basePt with edge 2136 Intersections intersections; 2137 // OPTIMIZE: use specialty function that intersects ray with curve, 2138 // returning t values only for curve (we don't care about t on ray) 2139 int pts = (*VSegmentIntersect[fVerb])(fPts, top, bottom, basePt.fX, false, intersections); 2140 if (pts == 0 || (current && pts == 1)) { 2141 return bestTIndex; 2142 } 2143 if (current) { 2144 SkASSERT(pts > 1); 2145 int closestIdx = 0; 2146 double closest = fabs(intersections.fT[0][0] - mid); 2147 for (int idx = 1; idx < pts; ++idx) { 2148 double test = fabs(intersections.fT[0][idx] - mid); 2149 if (closest > test) { 2150 closestIdx = idx; 2151 closest = test; 2152 } 2153 } 2154 if (closestIdx < pts - 1) { 2155 intersections.fT[0][closestIdx] = intersections.fT[0][pts - 1]; 2156 } 2157 --pts; 2158 } 2159 double bestT = -1; 2160 for (int index = 0; index < pts; ++index) { 2161 double foundT = intersections.fT[0][index]; 2162 if (approximately_less_than_zero(foundT) 2163 || approximately_greater_than_one(foundT)) { 2164 continue; 2165 } 2166 SkScalar testY = (*SegmentYAtT[fVerb])(fPts, foundT); 2167 if (approximately_negative(testY - bestY) 2168 || approximately_negative(basePt.fY - testY)) { 2169 continue; 2170 } 2171 if (pts > 1 && fVerb == SkPath::kLine_Verb) { 2172 return SK_MinS32; // if the intersection is edge on, wait for another one 2173 } 2174 if (fVerb > SkPath::kLine_Verb) { 2175 SkScalar dx = (*SegmentDXAtT[fVerb])(fPts, foundT); 2176 if (approximately_zero(dx)) { 2177 return SK_MinS32; // hit vertical, wait for another one 2178 } 2179 } 2180 bestY = testY; 2181 bestT = foundT; 2182 } 2183 if (bestT < 0) { 2184 return bestTIndex; 2185 } 2186 SkASSERT(bestT >= 0); 2187 SkASSERT(bestT <= 1); 2188 int start; 2189 int end = 0; 2190 do { 2191 start = end; 2192 end = nextSpan(start, 1); 2193 } while (fTs[end].fT < bestT); 2194 // FIXME: see next candidate for a better pattern to find the next start/end pair 2195 while (start + 1 < end && fTs[start].fDone) { 2196 ++start; 2197 } 2198 if (!isCanceled(start)) { 2199 hitT = bestT; 2200 bestTIndex = start; 2201 hitSomething = true; 2202 } 2203 return bestTIndex; 2204 } 2205 2206 void decrementSpan(Span* span) { 2207 SkASSERT(span->fWindValue > 0); 2208 if (--(span->fWindValue) == 0) { 2209 if (!span->fOppValue && !span->fDone) { 2210 span->fDone = true; 2211 ++fDoneSpans; 2212 } 2213 } 2214 } 2215 2216 bool bumpSpan(Span* span, int windDelta, int oppDelta) { 2217 SkASSERT(!span->fDone); 2218 span->fWindValue += windDelta; 2219 SkASSERT(span->fWindValue >= 0); 2220 span->fOppValue += oppDelta; 2221 SkASSERT(span->fOppValue >= 0); 2222 if (fXor) { 2223 span->fWindValue &= 1; 2224 } 2225 if (fOppXor) { 2226 span->fOppValue &= 1; 2227 } 2228 if (!span->fWindValue && !span->fOppValue) { 2229 span->fDone = true; 2230 ++fDoneSpans; 2231 return true; 2232 } 2233 return false; 2234 } 2235 2236 // OPTIMIZE 2237 // when the edges are initially walked, they don't automatically get the prior and next 2238 // edges assigned to positions t=0 and t=1. Doing that would remove the need for this check, 2239 // and would additionally remove the need for similar checks in condition edges. It would 2240 // also allow intersection code to assume end of segment intersections (maybe?) 2241 bool complete() const { 2242 int count = fTs.count(); 2243 return count > 1 && fTs[0].fT == 0 && fTs[--count].fT == 1; 2244 } 2245 2246 bool done() const { 2247 SkASSERT(fDoneSpans <= fTs.count()); 2248 return fDoneSpans == fTs.count(); 2249 } 2250 2251 bool done(int min) const { 2252 return fTs[min].fDone; 2253 } 2254 2255 bool done(const Angle* angle) const { 2256 return done(SkMin32(angle->start(), angle->end())); 2257 } 2258 2259 SkPoint dxdy(int index) const { 2260 return (*SegmentDXDYAtT[fVerb])(fPts, fTs[index].fT); 2261 } 2262 2263 SkScalar dy(int index) const { 2264 return (*SegmentDYAtT[fVerb])(fPts, fTs[index].fT); 2265 } 2266 2267 bool equalPoints(int greaterTIndex, int lesserTIndex) { 2268 SkASSERT(greaterTIndex >= lesserTIndex); 2269 double greaterT = fTs[greaterTIndex].fT; 2270 double lesserT = fTs[lesserTIndex].fT; 2271 if (greaterT == lesserT) { 2272 return true; 2273 } 2274 if (!approximately_negative(greaterT - lesserT)) { 2275 return false; 2276 } 2277 return xyAtT(greaterTIndex) == xyAtT(lesserTIndex); 2278 } 2279 2280 /* 2281 The M and S variable name parts stand for the operators. 2282 Mi stands for Minuend (see wiki subtraction, analogous to difference) 2283 Su stands for Subtrahend 2284 The Opp variable name part designates that the value is for the Opposite operator. 2285 Opposite values result from combining coincident spans. 2286 */ 2287 2288 Segment* findNextOp(SkTDArray<Span*>& chase, int& nextStart, int& nextEnd, 2289 bool& unsortable, ShapeOp op, const int xorMiMask, const int xorSuMask) { 2290 const int startIndex = nextStart; 2291 const int endIndex = nextEnd; 2292 SkASSERT(startIndex != endIndex); 2293 const int count = fTs.count(); 2294 SkASSERT(startIndex < endIndex ? startIndex < count - 1 : startIndex > 0); 2295 const int step = SkSign32(endIndex - startIndex); 2296 const int end = nextExactSpan(startIndex, step); 2297 SkASSERT(end >= 0); 2298 Span* endSpan = &fTs[end]; 2299 Segment* other; 2300 if (isSimple(end)) { 2301 // mark the smaller of startIndex, endIndex done, and all adjacent 2302 // spans with the same T value (but not 'other' spans) 2303 #if DEBUG_WINDING 2304 SkDebugf("%s simple\n", __FUNCTION__); 2305 #endif 2306 int min = SkMin32(startIndex, endIndex); 2307 if (fTs[min].fDone) { 2308 return NULL; 2309 } 2310 markDoneBinary(min); 2311 other = endSpan->fOther; 2312 nextStart = endSpan->fOtherIndex; 2313 double startT = other->fTs[nextStart].fT; 2314 nextEnd = nextStart; 2315 do { 2316 nextEnd += step; 2317 } 2318 while (precisely_zero(startT - other->fTs[nextEnd].fT)); 2319 SkASSERT(step < 0 ? nextEnd >= 0 : nextEnd < other->fTs.count()); 2320 return other; 2321 } 2322 // more than one viable candidate -- measure angles to find best 2323 SkTDArray<Angle> angles; 2324 SkASSERT(startIndex - endIndex != 0); 2325 SkASSERT((startIndex - endIndex < 0) ^ (step < 0)); 2326 addTwoAngles(startIndex, end, angles); 2327 buildAngles(end, angles, true); 2328 SkTDArray<Angle*> sorted; 2329 bool sortable = SortAngles(angles, sorted); 2330 int angleCount = angles.count(); 2331 int firstIndex = findStartingEdge(sorted, startIndex, end); 2332 SkASSERT(firstIndex >= 0); 2333 #if DEBUG_SORT 2334 debugShowSort(__FUNCTION__, sorted, firstIndex); 2335 #endif 2336 if (!sortable) { 2337 unsortable = true; 2338 return NULL; 2339 } 2340 SkASSERT(sorted[firstIndex]->segment() == this); 2341 #if DEBUG_WINDING 2342 SkDebugf("%s firstIndex=[%d] sign=%d\n", __FUNCTION__, firstIndex, 2343 sorted[firstIndex]->sign()); 2344 #endif 2345 int sumMiWinding = updateWinding(endIndex, startIndex); 2346 int sumSuWinding = updateOppWinding(endIndex, startIndex); 2347 if (operand()) { 2348 SkTSwap<int>(sumMiWinding, sumSuWinding); 2349 } 2350 int nextIndex = firstIndex + 1; 2351 int lastIndex = firstIndex != 0 ? firstIndex : angleCount; 2352 const Angle* foundAngle = NULL; 2353 bool foundDone = false; 2354 // iterate through the angle, and compute everyone's winding 2355 Segment* nextSegment; 2356 do { 2357 SkASSERT(nextIndex != firstIndex); 2358 if (nextIndex == angleCount) { 2359 nextIndex = 0; 2360 } 2361 const Angle* nextAngle = sorted[nextIndex]; 2362 nextSegment = nextAngle->segment(); 2363 int maxWinding, sumWinding, oppMaxWinding, oppSumWinding; 2364 bool activeAngle = nextSegment->activeOp(xorMiMask, xorSuMask, nextAngle->start(), 2365 nextAngle->end(), op, sumMiWinding, sumSuWinding, 2366 maxWinding, sumWinding, oppMaxWinding, oppSumWinding); 2367 if (activeAngle && (!foundAngle || foundDone)) { 2368 foundAngle = nextAngle; 2369 foundDone = nextSegment->done(nextAngle) && !nextSegment->tiny(nextAngle); 2370 } 2371 if (nextSegment->done()) { 2372 continue; 2373 } 2374 if (nextSegment->windSum(nextAngle) != SK_MinS32) { 2375 continue; 2376 } 2377 Span* last = nextSegment->markAngle(maxWinding, sumWinding, oppMaxWinding, 2378 oppSumWinding, activeAngle, nextAngle); 2379 if (last) { 2380 *chase.append() = last; 2381#if DEBUG_WINDING 2382 SkDebugf("%s chase.append id=%d\n", __FUNCTION__, 2383 last->fOther->fTs[last->fOtherIndex].fOther->debugID()); 2384#endif 2385 } 2386 } while (++nextIndex != lastIndex); 2387 markDoneBinary(SkMin32(startIndex, endIndex)); 2388 if (!foundAngle) { 2389 return NULL; 2390 } 2391 nextStart = foundAngle->start(); 2392 nextEnd = foundAngle->end(); 2393 nextSegment = foundAngle->segment(); 2394 2395 #if DEBUG_WINDING 2396 SkDebugf("%s from:[%d] to:[%d] start=%d end=%d\n", 2397 __FUNCTION__, debugID(), nextSegment->debugID(), nextStart, nextEnd); 2398 #endif 2399 return nextSegment; 2400 } 2401 2402 Segment* findNextWinding(SkTDArray<Span*>& chase, int& nextStart, int& nextEnd, 2403 bool& unsortable) { 2404 const int startIndex = nextStart; 2405 const int endIndex = nextEnd; 2406 SkASSERT(startIndex != endIndex); 2407 const int count = fTs.count(); 2408 SkASSERT(startIndex < endIndex ? startIndex < count - 1 : startIndex > 0); 2409 const int step = SkSign32(endIndex - startIndex); 2410 const int end = nextExactSpan(startIndex, step); 2411 SkASSERT(end >= 0); 2412 Span* endSpan = &fTs[end]; 2413 Segment* other; 2414 if (isSimple(end)) { 2415 // mark the smaller of startIndex, endIndex done, and all adjacent 2416 // spans with the same T value (but not 'other' spans) 2417 #if DEBUG_WINDING 2418 SkDebugf("%s simple\n", __FUNCTION__); 2419 #endif 2420 int min = SkMin32(startIndex, endIndex); 2421 if (fTs[min].fDone) { 2422 return NULL; 2423 } 2424 markDoneUnary(min); 2425 other = endSpan->fOther; 2426 nextStart = endSpan->fOtherIndex; 2427 double startT = other->fTs[nextStart].fT; 2428 nextEnd = nextStart; 2429 do { 2430 nextEnd += step; 2431 } 2432 while (precisely_zero(startT - other->fTs[nextEnd].fT)); 2433 SkASSERT(step < 0 ? nextEnd >= 0 : nextEnd < other->fTs.count()); 2434 return other; 2435 } 2436 // more than one viable candidate -- measure angles to find best 2437 SkTDArray<Angle> angles; 2438 SkASSERT(startIndex - endIndex != 0); 2439 SkASSERT((startIndex - endIndex < 0) ^ (step < 0)); 2440 addTwoAngles(startIndex, end, angles); 2441 buildAngles(end, angles, true); 2442 SkTDArray<Angle*> sorted; 2443 bool sortable = SortAngles(angles, sorted); 2444 int angleCount = angles.count(); 2445 int firstIndex = findStartingEdge(sorted, startIndex, end); 2446 SkASSERT(firstIndex >= 0); 2447 #if DEBUG_SORT 2448 debugShowSort(__FUNCTION__, sorted, firstIndex); 2449 #endif 2450 if (!sortable) { 2451 unsortable = true; 2452 return NULL; 2453 } 2454 SkASSERT(sorted[firstIndex]->segment() == this); 2455 #if DEBUG_WINDING 2456 SkDebugf("%s firstIndex=[%d] sign=%d\n", __FUNCTION__, firstIndex, 2457 sorted[firstIndex]->sign()); 2458 #endif 2459 int sumWinding = updateWinding(endIndex, startIndex); 2460 int nextIndex = firstIndex + 1; 2461 int lastIndex = firstIndex != 0 ? firstIndex : angleCount; 2462 const Angle* foundAngle = NULL; 2463 bool foundDone = false; 2464 // iterate through the angle, and compute everyone's winding 2465 Segment* nextSegment; 2466 int activeCount = 0; 2467 do { 2468 SkASSERT(nextIndex != firstIndex); 2469 if (nextIndex == angleCount) { 2470 nextIndex = 0; 2471 } 2472 const Angle* nextAngle = sorted[nextIndex]; 2473 nextSegment = nextAngle->segment(); 2474 int maxWinding; 2475 bool activeAngle = nextSegment->activeWinding(nextAngle->start(), nextAngle->end(), 2476 maxWinding, sumWinding); 2477 if (activeAngle) { 2478 ++activeCount; 2479 if (!foundAngle || (foundDone && activeCount & 1)) { 2480 if (nextSegment->tiny(nextAngle)) { 2481 unsortable = true; 2482 return NULL; 2483 } 2484 foundAngle = nextAngle; 2485 foundDone = nextSegment->done(nextAngle); 2486 } 2487 } 2488 if (nextSegment->done()) { 2489 continue; 2490 } 2491 if (nextSegment->windSum(nextAngle) != SK_MinS32) { 2492 continue; 2493 } 2494 Span* last = nextSegment->markAngle(maxWinding, sumWinding, activeAngle, nextAngle); 2495 if (last) { 2496 *chase.append() = last; 2497#if DEBUG_WINDING 2498 SkDebugf("%s chase.append id=%d\n", __FUNCTION__, 2499 last->fOther->fTs[last->fOtherIndex].fOther->debugID()); 2500#endif 2501 } 2502 } while (++nextIndex != lastIndex); 2503 markDoneUnary(SkMin32(startIndex, endIndex)); 2504 if (!foundAngle) { 2505 return NULL; 2506 } 2507 nextStart = foundAngle->start(); 2508 nextEnd = foundAngle->end(); 2509 nextSegment = foundAngle->segment(); 2510 #if DEBUG_WINDING 2511 SkDebugf("%s from:[%d] to:[%d] start=%d end=%d\n", 2512 __FUNCTION__, debugID(), nextSegment->debugID(), nextStart, nextEnd); 2513 #endif 2514 return nextSegment; 2515 } 2516 2517 Segment* findNextXor(int& nextStart, int& nextEnd, bool& unsortable) { 2518 const int startIndex = nextStart; 2519 const int endIndex = nextEnd; 2520 SkASSERT(startIndex != endIndex); 2521 int count = fTs.count(); 2522 SkASSERT(startIndex < endIndex ? startIndex < count - 1 2523 : startIndex > 0); 2524 int step = SkSign32(endIndex - startIndex); 2525 int end = nextExactSpan(startIndex, step); 2526 SkASSERT(end >= 0); 2527 Span* endSpan = &fTs[end]; 2528 Segment* other; 2529 if (isSimple(end)) { 2530 #if DEBUG_WINDING 2531 SkDebugf("%s simple\n", __FUNCTION__); 2532 #endif 2533 int min = SkMin32(startIndex, endIndex); 2534 if (fTs[min].fDone) { 2535 return NULL; 2536 } 2537 markDone(min, 1); 2538 other = endSpan->fOther; 2539 nextStart = endSpan->fOtherIndex; 2540 double startT = other->fTs[nextStart].fT; 2541 #if 01 // FIXME: I don't know why the logic here is difference from the winding case 2542 SkDEBUGCODE(bool firstLoop = true;) 2543 if ((approximately_less_than_zero(startT) && step < 0) 2544 || (approximately_greater_than_one(startT) && step > 0)) { 2545 step = -step; 2546 SkDEBUGCODE(firstLoop = false;) 2547 } 2548 do { 2549 #endif 2550 nextEnd = nextStart; 2551 do { 2552 nextEnd += step; 2553 } 2554 while (precisely_zero(startT - other->fTs[nextEnd].fT)); 2555 #if 01 2556 if (other->fTs[SkMin32(nextStart, nextEnd)].fWindValue) { 2557 break; 2558 } 2559 #ifdef SK_DEBUG 2560 SkASSERT(firstLoop); 2561 #endif 2562 SkDEBUGCODE(firstLoop = false;) 2563 step = -step; 2564 } while (true); 2565 #endif 2566 SkASSERT(step < 0 ? nextEnd >= 0 : nextEnd < other->fTs.count()); 2567 return other; 2568 } 2569 SkTDArray<Angle> angles; 2570 SkASSERT(startIndex - endIndex != 0); 2571 SkASSERT((startIndex - endIndex < 0) ^ (step < 0)); 2572 addTwoAngles(startIndex, end, angles); 2573 buildAngles(end, angles, false); 2574 SkTDArray<Angle*> sorted; 2575 bool sortable = SortAngles(angles, sorted); 2576 if (!sortable) { 2577 unsortable = true; 2578 #if DEBUG_SORT 2579 debugShowSort(__FUNCTION__, sorted, findStartingEdge(sorted, startIndex, end), 0, 0); 2580 #endif 2581 return NULL; 2582 } 2583 int angleCount = angles.count(); 2584 int firstIndex = findStartingEdge(sorted, startIndex, end); 2585 SkASSERT(firstIndex >= 0); 2586 #if DEBUG_SORT 2587 debugShowSort(__FUNCTION__, sorted, firstIndex, 0, 0); 2588 #endif 2589 SkASSERT(sorted[firstIndex]->segment() == this); 2590 int nextIndex = firstIndex + 1; 2591 int lastIndex = firstIndex != 0 ? firstIndex : angleCount; 2592 const Angle* foundAngle = NULL; 2593 bool foundDone = false; 2594 Segment* nextSegment; 2595 int activeCount = 0; 2596 do { 2597 SkASSERT(nextIndex != firstIndex); 2598 if (nextIndex == angleCount) { 2599 nextIndex = 0; 2600 } 2601 const Angle* nextAngle = sorted[nextIndex]; 2602 nextSegment = nextAngle->segment(); 2603 ++activeCount; 2604 if (!foundAngle || (foundDone && activeCount & 1)) { 2605 if (nextSegment->tiny(nextAngle)) { 2606 unsortable = true; 2607 return NULL; 2608 } 2609 foundAngle = nextAngle; 2610 foundDone = nextSegment->done(nextAngle); 2611 } 2612 if (nextSegment->done()) { 2613 continue; 2614 } 2615 } while (++nextIndex != lastIndex); 2616 markDone(SkMin32(startIndex, endIndex), 1); 2617 if (!foundAngle) { 2618 return NULL; 2619 } 2620 nextStart = foundAngle->start(); 2621 nextEnd = foundAngle->end(); 2622 nextSegment = foundAngle->segment(); 2623 #if DEBUG_WINDING 2624 SkDebugf("%s from:[%d] to:[%d] start=%d end=%d\n", 2625 __FUNCTION__, debugID(), nextSegment->debugID(), nextStart, nextEnd); 2626 #endif 2627 return nextSegment; 2628 } 2629 2630 int findStartingEdge(SkTDArray<Angle*>& sorted, int start, int end) { 2631 int angleCount = sorted.count(); 2632 int firstIndex = -1; 2633 for (int angleIndex = 0; angleIndex < angleCount; ++angleIndex) { 2634 const Angle* angle = sorted[angleIndex]; 2635 if (angle->segment() == this && angle->start() == end && 2636 angle->end() == start) { 2637 firstIndex = angleIndex; 2638 break; 2639 } 2640 } 2641 return firstIndex; 2642 } 2643 2644 // FIXME: this is tricky code; needs its own unit test 2645 // note that fOtherIndex isn't computed yet, so it can't be used here 2646 void findTooCloseToCall() { 2647 int count = fTs.count(); 2648 if (count < 3) { // require t=0, x, 1 at minimum 2649 return; 2650 } 2651 int matchIndex = 0; 2652 int moCount; 2653 Span* match; 2654 Segment* mOther; 2655 do { 2656 match = &fTs[matchIndex]; 2657 mOther = match->fOther; 2658 // FIXME: allow quads, cubics to be near coincident? 2659 if (mOther->fVerb == SkPath::kLine_Verb) { 2660 moCount = mOther->fTs.count(); 2661 if (moCount >= 3) { 2662 break; 2663 } 2664 } 2665 if (++matchIndex >= count) { 2666 return; 2667 } 2668 } while (true); // require t=0, x, 1 at minimum 2669 // OPTIMIZATION: defer matchPt until qualifying toCount is found? 2670 const SkPoint* matchPt = &xyAtT(match); 2671 // look for a pair of nearby T values that map to the same (x,y) value 2672 // if found, see if the pair of other segments share a common point. If 2673 // so, the span from here to there is coincident. 2674 for (int index = matchIndex + 1; index < count; ++index) { 2675 Span* test = &fTs[index]; 2676 if (test->fDone) { 2677 continue; 2678 } 2679 Segment* tOther = test->fOther; 2680 if (tOther->fVerb != SkPath::kLine_Verb) { 2681 continue; // FIXME: allow quads, cubics to be near coincident? 2682 } 2683 int toCount = tOther->fTs.count(); 2684 if (toCount < 3) { // require t=0, x, 1 at minimum 2685 continue; 2686 } 2687 const SkPoint* testPt = &xyAtT(test); 2688 if (*matchPt != *testPt) { 2689 matchIndex = index; 2690 moCount = toCount; 2691 match = test; 2692 mOther = tOther; 2693 matchPt = testPt; 2694 continue; 2695 } 2696 int moStart = -1; 2697 int moEnd = -1; 2698 double moStartT, moEndT; 2699 for (int moIndex = 0; moIndex < moCount; ++moIndex) { 2700 Span& moSpan = mOther->fTs[moIndex]; 2701 if (moSpan.fDone) { 2702 continue; 2703 } 2704 if (moSpan.fOther == this) { 2705 if (moSpan.fOtherT == match->fT) { 2706 moStart = moIndex; 2707 moStartT = moSpan.fT; 2708 } 2709 continue; 2710 } 2711 if (moSpan.fOther == tOther) { 2712 if (tOther->windValueAt(moSpan.fOtherT) == 0) { 2713 moStart = -1; 2714 break; 2715 } 2716 SkASSERT(moEnd == -1); 2717 moEnd = moIndex; 2718 moEndT = moSpan.fT; 2719 } 2720 } 2721 if (moStart < 0 || moEnd < 0) { 2722 continue; 2723 } 2724 // FIXME: if moStartT, moEndT are initialized to NaN, can skip this test 2725 if (approximately_equal(moStartT, moEndT)) { 2726 continue; 2727 } 2728 int toStart = -1; 2729 int toEnd = -1; 2730 double toStartT, toEndT; 2731 for (int toIndex = 0; toIndex < toCount; ++toIndex) { 2732 Span& toSpan = tOther->fTs[toIndex]; 2733 if (toSpan.fDone) { 2734 continue; 2735 } 2736 if (toSpan.fOther == this) { 2737 if (toSpan.fOtherT == test->fT) { 2738 toStart = toIndex; 2739 toStartT = toSpan.fT; 2740 } 2741 continue; 2742 } 2743 if (toSpan.fOther == mOther && toSpan.fOtherT == moEndT) { 2744 if (mOther->windValueAt(toSpan.fOtherT) == 0) { 2745 moStart = -1; 2746 break; 2747 } 2748 SkASSERT(toEnd == -1); 2749 toEnd = toIndex; 2750 toEndT = toSpan.fT; 2751 } 2752 } 2753 // FIXME: if toStartT, toEndT are initialized to NaN, can skip this test 2754 if (toStart <= 0 || toEnd <= 0) { 2755 continue; 2756 } 2757 if (approximately_equal(toStartT, toEndT)) { 2758 continue; 2759 } 2760 // test to see if the segment between there and here is linear 2761 if (!mOther->isLinear(moStart, moEnd) 2762 || !tOther->isLinear(toStart, toEnd)) { 2763 continue; 2764 } 2765 bool flipped = (moStart - moEnd) * (toStart - toEnd) < 1; 2766 if (flipped) { 2767 mOther->addTCancel(moStartT, moEndT, *tOther, toEndT, toStartT); 2768 } else { 2769 mOther->addTCoincident(moStartT, moEndT, *tOther, toStartT, toEndT); 2770 } 2771 } 2772 } 2773 2774 // FIXME: either: 2775 // a) mark spans with either end unsortable as done, or 2776 // b) rewrite findTop / findTopSegment / findTopContour to iterate further 2777 // when encountering an unsortable span 2778 2779 // OPTIMIZATION : for a pair of lines, can we compute points at T (cached) 2780 // and use more concise logic like the old edge walker code? 2781 // FIXME: this needs to deal with coincident edges 2782 Segment* findTop(int& tIndex, int& endIndex, bool& unsortable, bool onlySortable) { 2783 // iterate through T intersections and return topmost 2784 // topmost tangent from y-min to first pt is closer to horizontal 2785 SkASSERT(!done()); 2786 int firstT = -1; 2787 SkPoint topPt = activeLeftTop(onlySortable, &firstT); 2788 SkASSERT(firstT >= 0); 2789 // sort the edges to find the leftmost 2790 int step = 1; 2791 int end = nextSpan(firstT, step); 2792 if (end == -1) { 2793 step = -1; 2794 end = nextSpan(firstT, step); 2795 SkASSERT(end != -1); 2796 } 2797 // if the topmost T is not on end, or is three-way or more, find left 2798 // look for left-ness from tLeft to firstT (matching y of other) 2799 SkTDArray<Angle> angles; 2800 SkASSERT(firstT - end != 0); 2801 addTwoAngles(end, firstT, angles); 2802 buildAngles(firstT, angles, true); 2803 SkTDArray<Angle*> sorted; 2804 bool sortable = SortAngles(angles, sorted); 2805 #if DEBUG_SORT 2806 sorted[0]->segment()->debugShowSort(__FUNCTION__, sorted, 0, 0, 0); 2807 #endif 2808 if (onlySortable && !sortable) { 2809 unsortable = true; 2810 return NULL; 2811 } 2812 // skip edges that have already been processed 2813 firstT = -1; 2814 Segment* leftSegment; 2815 do { 2816 const Angle* angle = sorted[++firstT]; 2817 SkASSERT(!onlySortable || !angle->unsortable()); 2818 leftSegment = angle->segment(); 2819 tIndex = angle->end(); 2820 endIndex = angle->start(); 2821 } while (leftSegment->fTs[SkMin32(tIndex, endIndex)].fDone); 2822 if (leftSegment->verb() >= SkPath::kQuad_Verb) { 2823 SkScalar dyE = leftSegment->dy(endIndex); 2824 SkScalar dyS = leftSegment->dy(tIndex); 2825 if (dyE < 0 && dyS > 0) { 2826 SkTSwap(tIndex, endIndex); 2827 } 2828 } 2829 SkASSERT(!leftSegment->fTs[SkMin32(tIndex, endIndex)].fTiny); 2830 return leftSegment; 2831 } 2832 2833 // FIXME: not crazy about this 2834 // when the intersections are performed, the other index is into an 2835 // incomplete array. as the array grows, the indices become incorrect 2836 // while the following fixes the indices up again, it isn't smart about 2837 // skipping segments whose indices are already correct 2838 // assuming we leave the code that wrote the index in the first place 2839 void fixOtherTIndex() { 2840 int iCount = fTs.count(); 2841 for (int i = 0; i < iCount; ++i) { 2842 Span& iSpan = fTs[i]; 2843 double oT = iSpan.fOtherT; 2844 Segment* other = iSpan.fOther; 2845 int oCount = other->fTs.count(); 2846 for (int o = 0; o < oCount; ++o) { 2847 Span& oSpan = other->fTs[o]; 2848 if (oT == oSpan.fT && this == oSpan.fOther) { 2849 iSpan.fOtherIndex = o; 2850 break; 2851 } 2852 } 2853 } 2854 } 2855 2856 void init(const SkPoint pts[], SkPath::Verb verb, bool operand, bool evenOdd) { 2857 fDoneSpans = 0; 2858 fOperand = operand; 2859 fXor = evenOdd; 2860 fPts = pts; 2861 fVerb = verb; 2862 } 2863 2864 void initWinding(int start, int end) { 2865 int local = spanSign(start, end); 2866 int oppLocal = oppSign(start, end); 2867 (void) markAndChaseWinding(start, end, local, oppLocal); 2868 // OPTIMIZATION: the reverse mark and chase could skip the first marking 2869 (void) markAndChaseWinding(end, start, local, oppLocal); 2870 } 2871 2872 void initWinding(int start, int end, int winding, int oppWinding) { 2873 int local = spanSign(start, end); 2874 if (local * winding >= 0) { 2875 winding += local; 2876 } 2877 int oppLocal = oppSign(start, end); 2878 if (oppLocal * oppWinding >= 0) { 2879 oppWinding += oppLocal; 2880 } 2881 (void) markAndChaseWinding(start, end, winding, oppWinding); 2882 } 2883 2884/* 2885when we start with a vertical intersect, we try to use the dx to determine if the edge is to 2886the left or the right of vertical. This determines if we need to add the span's 2887sign or not. However, this isn't enough. 2888If the supplied sign (winding) is zero, then we didn't hit another vertical span, so dx is needed. 2889If there was a winding, then it may or may not need adjusting. If the span the winding was borrowed 2890from has the same x direction as this span, the winding should change. If the dx is opposite, then 2891the same winding is shared by both. 2892*/ 2893 void initWinding(int start, int end, double tHit, int winding, SkScalar hitDx, int oppWind, 2894 SkScalar hitOppDx) { 2895 SkASSERT(hitDx || !winding); 2896 SkScalar dx = (*SegmentDXAtT[fVerb])(fPts, tHit); 2897 SkASSERT(dx); 2898 int windVal = windValue(SkMin32(start, end)); 2899 #if DEBUG_WINDING_AT_T 2900 SkDebugf("%s oldWinding=%d hitDx=%c dx=%c windVal=%d", __FUNCTION__, winding, 2901 hitDx ? hitDx > 0 ? '+' : '-' : '0', dx > 0 ? '+' : '-', windVal); 2902 #endif 2903 if (!winding) { 2904 winding = dx < 0 ? windVal : -windVal; 2905 } else if (winding * dx < 0) { 2906 int sideWind = winding + (dx < 0 ? windVal : -windVal); 2907 if (abs(winding) < abs(sideWind)) { 2908 winding = sideWind; 2909 } 2910 } 2911 #if DEBUG_WINDING_AT_T 2912 SkDebugf(" winding=%d\n", winding); 2913 #endif 2914 int oppLocal = oppSign(start, end); 2915 SkASSERT(hitOppDx || !oppWind || !oppLocal); 2916 int oppWindVal = oppValue(SkMin32(start, end)); 2917 if (!oppWind) { 2918 oppWind = dx < 0 ? oppWindVal : -oppWindVal; 2919 } else if (hitOppDx * dx >= 0) { 2920 int oppSideWind = oppWind + (dx < 0 ? oppWindVal : -oppWindVal); 2921 if (abs(oppWind) < abs(oppSideWind)) { 2922 oppWind = oppSideWind; 2923 } 2924 } 2925 (void) markAndChaseWinding(start, end, winding, oppWind); 2926 } 2927 2928 bool intersected() const { 2929 return fTs.count() > 0; 2930 } 2931 2932 bool isCanceled(int tIndex) const { 2933 return fTs[tIndex].fWindValue == 0 && fTs[tIndex].fOppValue == 0; 2934 } 2935 2936 bool isConnected(int startIndex, int endIndex) const { 2937 return fTs[startIndex].fWindSum != SK_MinS32 2938 || fTs[endIndex].fWindSum != SK_MinS32; 2939 } 2940 2941 bool isHorizontal() const { 2942 return fBounds.fTop == fBounds.fBottom; 2943 } 2944 2945 bool isLinear(int start, int end) const { 2946 if (fVerb == SkPath::kLine_Verb) { 2947 return true; 2948 } 2949 if (fVerb == SkPath::kQuad_Verb) { 2950 SkPoint qPart[3]; 2951 QuadSubDivide(fPts, fTs[start].fT, fTs[end].fT, qPart); 2952 return QuadIsLinear(qPart); 2953 } else { 2954 SkASSERT(fVerb == SkPath::kCubic_Verb); 2955 SkPoint cPart[4]; 2956 CubicSubDivide(fPts, fTs[start].fT, fTs[end].fT, cPart); 2957 return CubicIsLinear(cPart); 2958 } 2959 } 2960 2961 // OPTIMIZE: successive calls could start were the last leaves off 2962 // or calls could specialize to walk forwards or backwards 2963 bool isMissing(double startT) const { 2964 size_t tCount = fTs.count(); 2965 for (size_t index = 0; index < tCount; ++index) { 2966 if (approximately_zero(startT - fTs[index].fT)) { 2967 return false; 2968 } 2969 } 2970 return true; 2971 } 2972 2973 bool isSimple(int end) const { 2974 int count = fTs.count(); 2975 if (count == 2) { 2976 return true; 2977 } 2978 double t = fTs[end].fT; 2979 if (approximately_less_than_zero(t)) { 2980 return !approximately_less_than_zero(fTs[1].fT); 2981 } 2982 if (approximately_greater_than_one(t)) { 2983 return !approximately_greater_than_one(fTs[count - 2].fT); 2984 } 2985 return false; 2986 } 2987 2988 bool isVertical() const { 2989 return fBounds.fLeft == fBounds.fRight; 2990 } 2991 2992 bool isVertical(int start, int end) const { 2993 return (*SegmentVertical[fVerb])(fPts, start, end); 2994 } 2995 2996 SkScalar leftMost(int start, int end) const { 2997 return (*SegmentLeftMost[fVerb])(fPts, fTs[start].fT, fTs[end].fT); 2998 } 2999 3000 // this span is excluded by the winding rule -- chase the ends 3001 // as long as they are unambiguous to mark connections as done 3002 // and give them the same winding value 3003 Span* markAndChaseDone(const Angle* angle, int winding) { 3004 int index = angle->start(); 3005 int endIndex = angle->end(); 3006 return markAndChaseDone(index, endIndex, winding); 3007 } 3008 3009 Span* markAndChaseDone(int index, int endIndex, int winding) { 3010 int step = SkSign32(endIndex - index); 3011 int min = SkMin32(index, endIndex); 3012 markDone(min, winding); 3013 Span* last; 3014 Segment* other = this; 3015 while ((other = other->nextChase(index, step, min, last))) { 3016 other->markDone(min, winding); 3017 } 3018 return last; 3019 } 3020 3021 Span* markAndChaseDoneBinary(const Angle* angle, int winding, int oppWinding) { 3022 int index = angle->start(); 3023 int endIndex = angle->end(); 3024 int step = SkSign32(endIndex - index); 3025 int min = SkMin32(index, endIndex); 3026 markDoneBinary(min, winding, oppWinding); 3027 Span* last; 3028 Segment* other = this; 3029 while ((other = other->nextChase(index, step, min, last))) { 3030 other->markDoneBinary(min, winding, oppWinding); 3031 } 3032 return last; 3033 } 3034 3035 Span* markAndChaseDoneBinary(int index, int endIndex) { 3036 int step = SkSign32(endIndex - index); 3037 int min = SkMin32(index, endIndex); 3038 markDoneBinary(min); 3039 Span* last; 3040 Segment* other = this; 3041 while ((other = other->nextChase(index, step, min, last))) { 3042 if (other->done()) { 3043 return NULL; 3044 } 3045 other->markDoneBinary(min); 3046 } 3047 return last; 3048 } 3049 3050 Span* markAndChaseDoneUnary(int index, int endIndex) { 3051 int step = SkSign32(endIndex - index); 3052 int min = SkMin32(index, endIndex); 3053 markDoneUnary(min); 3054 Span* last; 3055 Segment* other = this; 3056 while ((other = other->nextChase(index, step, min, last))) { 3057 if (other->done()) { 3058 return NULL; 3059 } 3060 other->markDoneUnary(min); 3061 } 3062 return last; 3063 } 3064 3065 Span* markAndChaseDoneUnary(const Angle* angle, int winding) { 3066 int index = angle->start(); 3067 int endIndex = angle->end(); 3068 return markAndChaseDone(index, endIndex, winding); 3069 } 3070 3071 Span* markAndChaseWinding(const Angle* angle, const int winding) { 3072 int index = angle->start(); 3073 int endIndex = angle->end(); 3074 int step = SkSign32(endIndex - index); 3075 int min = SkMin32(index, endIndex); 3076 markWinding(min, winding); 3077 Span* last; 3078 Segment* other = this; 3079 while ((other = other->nextChase(index, step, min, last))) { 3080 if (other->fTs[min].fWindSum != SK_MinS32) { 3081 SkASSERT(other->fTs[min].fWindSum == winding); 3082 return NULL; 3083 } 3084 other->markWinding(min, winding); 3085 } 3086 return last; 3087 } 3088 3089 Span* markAndChaseWinding(int index, int endIndex, int winding, int oppWinding) { 3090 int min = SkMin32(index, endIndex); 3091 int step = SkSign32(endIndex - index); 3092 markWinding(min, winding, oppWinding); 3093 Span* last; 3094 Segment* other = this; 3095 while ((other = other->nextChase(index, step, min, last))) { 3096 if (other->fTs[min].fWindSum != SK_MinS32) { 3097 SkASSERT(other->fTs[min].fWindSum == winding); 3098 return NULL; 3099 } 3100 other->markWinding(min, winding, oppWinding); 3101 } 3102 return last; 3103 } 3104 3105 Span* markAndChaseWinding(const Angle* angle, int winding, int oppWinding) { 3106 int start = angle->start(); 3107 int end = angle->end(); 3108 return markAndChaseWinding(start, end, winding, oppWinding); 3109 } 3110 3111 Span* markAngle(int maxWinding, int sumWinding, bool activeAngle, const Angle* angle) { 3112 SkASSERT(angle->segment() == this); 3113 if (useInnerWinding(maxWinding, sumWinding)) { 3114 maxWinding = sumWinding; 3115 } 3116 Span* last; 3117 if (activeAngle) { 3118 last = markAndChaseWinding(angle, maxWinding); 3119 } else { 3120 last = markAndChaseDoneUnary(angle, maxWinding); 3121 } 3122 return last; 3123 } 3124 3125 Span* markAngle(int maxWinding, int sumWinding, int oppMaxWinding, int oppSumWinding, 3126 bool activeAngle, const Angle* angle) { 3127 SkASSERT(angle->segment() == this); 3128 if (useInnerWinding(maxWinding, sumWinding)) { 3129 maxWinding = sumWinding; 3130 } 3131 if (oppMaxWinding != oppSumWinding && useInnerWinding(oppMaxWinding, oppSumWinding)) { 3132 oppMaxWinding = oppSumWinding; 3133 } 3134 Span* last; 3135 if (activeAngle) { 3136 last = markAndChaseWinding(angle, maxWinding, oppMaxWinding); 3137 } else { 3138 last = markAndChaseDoneBinary(angle, maxWinding, oppMaxWinding); 3139 } 3140 return last; 3141 } 3142 3143 // FIXME: this should also mark spans with equal (x,y) 3144 // This may be called when the segment is already marked done. While this 3145 // wastes time, it shouldn't do any more than spin through the T spans. 3146 // OPTIMIZATION: abort on first done found (assuming that this code is 3147 // always called to mark segments done). 3148 void markDone(int index, int winding) { 3149 // SkASSERT(!done()); 3150 SkASSERT(winding); 3151 double referenceT = fTs[index].fT; 3152 int lesser = index; 3153 while (--lesser >= 0 && precisely_negative(referenceT - fTs[lesser].fT)) { 3154 markOneDone(__FUNCTION__, lesser, winding); 3155 } 3156 do { 3157 markOneDone(__FUNCTION__, index, winding); 3158 } while (++index < fTs.count() && precisely_negative(fTs[index].fT - referenceT)); 3159 } 3160 3161 void markDoneBinary(int index, int winding, int oppWinding) { 3162 // SkASSERT(!done()); 3163 SkASSERT(winding || oppWinding); 3164 double referenceT = fTs[index].fT; 3165 int lesser = index; 3166 while (--lesser >= 0 && precisely_negative(referenceT - fTs[lesser].fT)) { 3167 markOneDoneBinary(__FUNCTION__, lesser, winding, oppWinding); 3168 } 3169 do { 3170 markOneDoneBinary(__FUNCTION__, index, winding, oppWinding); 3171 } while (++index < fTs.count() && precisely_negative(fTs[index].fT - referenceT)); 3172 } 3173 3174 void markDoneBinary(int index) { 3175 double referenceT = fTs[index].fT; 3176 int lesser = index; 3177 while (--lesser >= 0 && precisely_negative(referenceT - fTs[lesser].fT)) { 3178 markOneDoneBinary(__FUNCTION__, lesser); 3179 } 3180 do { 3181 markOneDoneBinary(__FUNCTION__, index); 3182 } while (++index < fTs.count() && precisely_negative(fTs[index].fT - referenceT)); 3183 } 3184 3185 void markDoneUnary(int index, int winding) { 3186 // SkASSERT(!done()); 3187 SkASSERT(winding); 3188 double referenceT = fTs[index].fT; 3189 int lesser = index; 3190 while (--lesser >= 0 && precisely_negative(referenceT - fTs[lesser].fT)) { 3191 markOneDoneUnary(__FUNCTION__, lesser, winding); 3192 } 3193 do { 3194 markOneDoneUnary(__FUNCTION__, index, winding); 3195 } while (++index < fTs.count() && precisely_negative(fTs[index].fT - referenceT)); 3196 } 3197 3198 void markDoneUnary(int index) { 3199 double referenceT = fTs[index].fT; 3200 int lesser = index; 3201 while (--lesser >= 0 && precisely_negative(referenceT - fTs[lesser].fT)) { 3202 markOneDoneUnary(__FUNCTION__, lesser); 3203 } 3204 do { 3205 markOneDoneUnary(__FUNCTION__, index); 3206 } while (++index < fTs.count() && precisely_negative(fTs[index].fT - referenceT)); 3207 } 3208 3209 void markOneDone(const char* funName, int tIndex, int winding) { 3210 Span* span = markOneWinding(funName, tIndex, winding); 3211 if (!span) { 3212 return; 3213 } 3214 span->fDone = true; 3215 fDoneSpans++; 3216 } 3217 3218 void markOneDoneBinary(const char* funName, int tIndex) { 3219 Span* span = verifyOneWinding(funName, tIndex); 3220 if (!span) { 3221 return; 3222 } 3223 span->fDone = true; 3224 fDoneSpans++; 3225 } 3226 3227 void markOneDoneBinary(const char* funName, int tIndex, int winding, int oppWinding) { 3228 Span* span = markOneWinding(funName, tIndex, winding, oppWinding); 3229 if (!span) { 3230 return; 3231 } 3232 span->fDone = true; 3233 fDoneSpans++; 3234 } 3235 3236 void markOneDoneUnary(const char* funName, int tIndex) { 3237 Span* span = verifyOneWindingU(funName, tIndex); 3238 if (!span) { 3239 return; 3240 } 3241 span->fDone = true; 3242 fDoneSpans++; 3243 } 3244 3245 void markOneDoneUnary(const char* funName, int tIndex, int winding) { 3246 Span* span = markOneWinding(funName, tIndex, winding); 3247 if (!span) { 3248 return; 3249 } 3250 span->fDone = true; 3251 fDoneSpans++; 3252 } 3253 3254 Span* markOneWinding(const char* funName, int tIndex, int winding) { 3255 Span& span = fTs[tIndex]; 3256 if (span.fDone) { 3257 return NULL; 3258 } 3259 #if DEBUG_MARK_DONE 3260 debugShowNewWinding(funName, span, winding); 3261 #endif 3262 SkASSERT(span.fWindSum == SK_MinS32 || span.fWindSum == winding); 3263 #ifdef SK_DEBUG 3264 SkASSERT(abs(winding) <= gDebugMaxWindSum); 3265 #endif 3266 span.fWindSum = winding; 3267 return &span; 3268 } 3269 3270 Span* markOneWinding(const char* funName, int tIndex, int winding, int oppWinding) { 3271 Span& span = fTs[tIndex]; 3272 if (span.fDone) { 3273 return NULL; 3274 } 3275 #if DEBUG_MARK_DONE 3276 debugShowNewWinding(funName, span, winding, oppWinding); 3277 #endif 3278 SkASSERT(span.fWindSum == SK_MinS32 || span.fWindSum == winding); 3279 #ifdef SK_DEBUG 3280 SkASSERT(abs(winding) <= gDebugMaxWindSum); 3281 #endif 3282 span.fWindSum = winding; 3283 SkASSERT(span.fOppSum == SK_MinS32 || span.fOppSum == oppWinding); 3284 #ifdef SK_DEBUG 3285 SkASSERT(abs(oppWinding) <= gDebugMaxWindSum); 3286 #endif 3287 span.fOppSum = oppWinding; 3288 return &span; 3289 } 3290 3291 Span* verifyOneWinding(const char* funName, int tIndex) { 3292 Span& span = fTs[tIndex]; 3293 if (span.fDone) { 3294 return NULL; 3295 } 3296 #if DEBUG_MARK_DONE 3297 debugShowNewWinding(funName, span, span.fWindSum, span.fOppSum); 3298 #endif 3299 SkASSERT(span.fWindSum != SK_MinS32); 3300 SkASSERT(span.fOppSum != SK_MinS32); 3301 return &span; 3302 } 3303 3304 Span* verifyOneWindingU(const char* funName, int tIndex) { 3305 Span& span = fTs[tIndex]; 3306 if (span.fDone) { 3307 return NULL; 3308 } 3309 #if DEBUG_MARK_DONE 3310 debugShowNewWinding(funName, span, span.fWindSum); 3311 #endif 3312 SkASSERT(span.fWindSum != SK_MinS32); 3313 return &span; 3314 } 3315 3316 // note that just because a span has one end that is unsortable, that's 3317 // not enough to mark it done. The other end may be sortable, allowing the 3318 // span to be added. 3319 // FIXME: if abs(start - end) > 1, mark intermediates as unsortable on both ends 3320 void markUnsortable(int start, int end) { 3321 Span* span = &fTs[start]; 3322 if (start < end) { 3323#if DEBUG_UNSORTABLE 3324 SkDebugf("%s start id=%d [%d] (%1.9g,%1.9g)\n", __FUNCTION__, fID, start, 3325 xAtT(start), yAtT(start)); 3326#endif 3327 span->fUnsortableStart = true; 3328 } else { 3329 --span; 3330#if DEBUG_UNSORTABLE 3331 SkDebugf("%s end id=%d [%d] (%1.9g,%1.9g) next:(%1.9g,%1.9g)\n", __FUNCTION__, fID, 3332 start - 1, xAtT(start - 1), yAtT(start - 1), xAtT(start), yAtT(start)); 3333#endif 3334 span->fUnsortableEnd = true; 3335 } 3336 if (!span->fUnsortableStart || !span->fUnsortableEnd || span->fDone) { 3337 return; 3338 } 3339 span->fDone = true; 3340 fDoneSpans++; 3341 } 3342 3343 void markWinding(int index, int winding) { 3344 // SkASSERT(!done()); 3345 SkASSERT(winding); 3346 double referenceT = fTs[index].fT; 3347 int lesser = index; 3348 while (--lesser >= 0 && precisely_negative(referenceT - fTs[lesser].fT)) { 3349 markOneWinding(__FUNCTION__, lesser, winding); 3350 } 3351 do { 3352 markOneWinding(__FUNCTION__, index, winding); 3353 } while (++index < fTs.count() && precisely_negative(fTs[index].fT - referenceT)); 3354 } 3355 3356 void markWinding(int index, int winding, int oppWinding) { 3357 // SkASSERT(!done()); 3358 SkASSERT(winding || oppWinding); 3359 double referenceT = fTs[index].fT; 3360 int lesser = index; 3361 while (--lesser >= 0 && precisely_negative(referenceT - fTs[lesser].fT)) { 3362 markOneWinding(__FUNCTION__, lesser, winding, oppWinding); 3363 } 3364 do { 3365 markOneWinding(__FUNCTION__, index, winding, oppWinding); 3366 } while (++index < fTs.count() && precisely_negative(fTs[index].fT - referenceT)); 3367 } 3368 3369 void matchWindingValue(int tIndex, double t, bool borrowWind) { 3370 int nextDoorWind = SK_MaxS32; 3371 int nextOppWind = SK_MaxS32; 3372 if (tIndex > 0) { 3373 const Span& below = fTs[tIndex - 1]; 3374 if (approximately_negative(t - below.fT)) { 3375 nextDoorWind = below.fWindValue; 3376 nextOppWind = below.fOppValue; 3377 } 3378 } 3379 if (nextDoorWind == SK_MaxS32 && tIndex + 1 < fTs.count()) { 3380 const Span& above = fTs[tIndex + 1]; 3381 if (approximately_negative(above.fT - t)) { 3382 nextDoorWind = above.fWindValue; 3383 nextOppWind = above.fOppValue; 3384 } 3385 } 3386 if (nextDoorWind == SK_MaxS32 && borrowWind && tIndex > 0 && t < 1) { 3387 const Span& below = fTs[tIndex - 1]; 3388 nextDoorWind = below.fWindValue; 3389 nextOppWind = below.fOppValue; 3390 } 3391 if (nextDoorWind != SK_MaxS32) { 3392 Span& newSpan = fTs[tIndex]; 3393 newSpan.fWindValue = nextDoorWind; 3394 newSpan.fOppValue = nextOppWind; 3395 if (!nextDoorWind && !nextOppWind && !newSpan.fDone) { 3396 newSpan.fDone = true; 3397 ++fDoneSpans; 3398 } 3399 } 3400 } 3401 3402 bool moreHorizontal(int index, int endIndex, bool& unsortable) const { 3403 // find bounds 3404 Bounds bounds; 3405 bounds.setPoint(xyAtT(index)); 3406 bounds.add(xyAtT(endIndex)); 3407 SkScalar width = bounds.width(); 3408 SkScalar height = bounds.height(); 3409 if (width > height) { 3410 if (approximately_negative(width)) { 3411 unsortable = true; // edge is too small to resolve meaningfully 3412 } 3413 return false; 3414 } else { 3415 if (approximately_negative(height)) { 3416 unsortable = true; // edge is too small to resolve meaningfully 3417 } 3418 return true; 3419 } 3420 } 3421 3422 // return span if when chasing, two or more radiating spans are not done 3423 // OPTIMIZATION: ? multiple spans is detected when there is only one valid 3424 // candidate and the remaining spans have windValue == 0 (canceled by 3425 // coincidence). The coincident edges could either be removed altogether, 3426 // or this code could be more complicated in detecting this case. Worth it? 3427 bool multipleSpans(int end) const { 3428 return end > 0 && end < fTs.count() - 1; 3429 } 3430 3431 bool nextCandidate(int& start, int& end) const { 3432 while (fTs[end].fDone) { 3433 if (fTs[end].fT == 1) { 3434 return false; 3435 } 3436 ++end; 3437 } 3438 start = end; 3439 end = nextExactSpan(start, 1); 3440 return true; 3441 } 3442 3443 Segment* nextChase(int& index, const int step, int& min, Span*& last) const { 3444 int end = nextExactSpan(index, step); 3445 SkASSERT(end >= 0); 3446 if (multipleSpans(end)) { 3447 last = &fTs[end]; 3448 return NULL; 3449 } 3450 const Span& endSpan = fTs[end]; 3451 Segment* other = endSpan.fOther; 3452 index = endSpan.fOtherIndex; 3453 SkASSERT(index >= 0); 3454 int otherEnd = other->nextExactSpan(index, step); 3455 SkASSERT(otherEnd >= 0); 3456 min = SkMin32(index, otherEnd); 3457 return other; 3458 } 3459 3460 // This has callers for two different situations: one establishes the end 3461 // of the current span, and one establishes the beginning of the next span 3462 // (thus the name). When this is looking for the end of the current span, 3463 // coincidence is found when the beginning Ts contain -step and the end 3464 // contains step. When it is looking for the beginning of the next, the 3465 // first Ts found can be ignored and the last Ts should contain -step. 3466 // OPTIMIZATION: probably should split into two functions 3467 int nextSpan(int from, int step) const { 3468 const Span& fromSpan = fTs[from]; 3469 int count = fTs.count(); 3470 int to = from; 3471 while (step > 0 ? ++to < count : --to >= 0) { 3472 const Span& span = fTs[to]; 3473 if (approximately_zero(span.fT - fromSpan.fT)) { 3474 continue; 3475 } 3476 return to; 3477 } 3478 return -1; 3479 } 3480 3481 // FIXME 3482 // this returns at any difference in T, vs. a preset minimum. It may be 3483 // that all callers to nextSpan should use this instead. 3484 // OPTIMIZATION splitting this into separate loops for up/down steps 3485 // would allow using precisely_negative instead of precisely_zero 3486 int nextExactSpan(int from, int step) const { 3487 const Span& fromSpan = fTs[from]; 3488 int count = fTs.count(); 3489 int to = from; 3490 while (step > 0 ? ++to < count : --to >= 0) { 3491 const Span& span = fTs[to]; 3492 if (precisely_zero(span.fT - fromSpan.fT)) { 3493 continue; 3494 } 3495 return to; 3496 } 3497 return -1; 3498 } 3499 3500 bool operand() const { 3501 return fOperand; 3502 } 3503 3504 int oppSign(const Angle* angle) const { 3505 SkASSERT(angle->segment() == this); 3506 return oppSign(angle->start(), angle->end()); 3507 } 3508 3509 int oppSign(int startIndex, int endIndex) const { 3510 int result = startIndex < endIndex ? -fTs[startIndex].fOppValue 3511 : fTs[endIndex].fOppValue; 3512#if DEBUG_WIND_BUMP 3513 SkDebugf("%s oppSign=%d\n", __FUNCTION__, result); 3514#endif 3515 return result; 3516 } 3517 3518 int oppSum(int tIndex) const { 3519 return fTs[tIndex].fOppSum; 3520 } 3521 3522 int oppSum(const Angle* angle) const { 3523 int lesser = SkMin32(angle->start(), angle->end()); 3524 return fTs[lesser].fOppSum; 3525 } 3526 3527 int oppValue(int tIndex) const { 3528 return fTs[tIndex].fOppValue; 3529 } 3530 3531 int oppValue(const Angle* angle) const { 3532 int lesser = SkMin32(angle->start(), angle->end()); 3533 return fTs[lesser].fOppValue; 3534 } 3535 3536 const SkPoint* pts() const { 3537 return fPts; 3538 } 3539 3540 void reset() { 3541 init(NULL, (SkPath::Verb) -1, false, false); 3542 fBounds.set(SK_ScalarMax, SK_ScalarMax, SK_ScalarMax, SK_ScalarMax); 3543 fTs.reset(); 3544 } 3545 3546 void setOppXor(bool isOppXor) { 3547 fOppXor = isOppXor; 3548 } 3549 3550 void setUpWinding(int index, int endIndex, int& maxWinding, int& sumWinding) { 3551 int deltaSum = spanSign(index, endIndex); 3552 maxWinding = sumWinding; 3553 sumWinding = sumWinding -= deltaSum; 3554 } 3555 3556 void setUpWindings(int index, int endIndex, int& sumMiWinding, int& sumSuWinding, 3557 int& maxWinding, int& sumWinding, int& oppMaxWinding, int& oppSumWinding) { 3558 int deltaSum = spanSign(index, endIndex); 3559 int oppDeltaSum = oppSign(index, endIndex); 3560 if (operand()) { 3561 maxWinding = sumSuWinding; 3562 sumWinding = sumSuWinding -= deltaSum; 3563 oppMaxWinding = sumMiWinding; 3564 oppSumWinding = sumMiWinding -= oppDeltaSum; 3565 } else { 3566 maxWinding = sumMiWinding; 3567 sumWinding = sumMiWinding -= deltaSum; 3568 oppMaxWinding = sumSuWinding; 3569 oppSumWinding = sumSuWinding -= oppDeltaSum; 3570 } 3571 } 3572 3573 // This marks all spans unsortable so that this info is available for early 3574 // exclusion in find top and others. This could be optimized to only mark 3575 // adjacent spans that unsortable. However, this makes it difficult to later 3576 // determine starting points for edge detection in find top and the like. 3577 static bool SortAngles(SkTDArray<Angle>& angles, SkTDArray<Angle*>& angleList) { 3578 bool sortable = true; 3579 int angleCount = angles.count(); 3580 int angleIndex; 3581 angleList.setReserve(angleCount); 3582 for (angleIndex = 0; angleIndex < angleCount; ++angleIndex) { 3583 Angle& angle = angles[angleIndex]; 3584 *angleList.append() = ∠ 3585 sortable &= !angle.unsortable(); 3586 } 3587 if (sortable) { 3588 QSort<Angle>(angleList.begin(), angleList.end() - 1); 3589 for (angleIndex = 0; angleIndex < angleCount; ++angleIndex) { 3590 if (angles[angleIndex].unsortable()) { 3591 sortable = false; 3592 break; 3593 } 3594 } 3595 } 3596 if (!sortable) { 3597 for (angleIndex = 0; angleIndex < angleCount; ++angleIndex) { 3598 Angle& angle = angles[angleIndex]; 3599 angle.segment()->markUnsortable(angle.start(), angle.end()); 3600 } 3601 } 3602 return sortable; 3603 } 3604 3605 // OPTIMIZATION: mark as debugging only if used solely by tests 3606 const Span& span(int tIndex) const { 3607 return fTs[tIndex]; 3608 } 3609 3610 int spanSign(const Angle* angle) const { 3611 SkASSERT(angle->segment() == this); 3612 return spanSign(angle->start(), angle->end()); 3613 } 3614 3615 int spanSign(int startIndex, int endIndex) const { 3616 int result = startIndex < endIndex ? -fTs[startIndex].fWindValue 3617 : fTs[endIndex].fWindValue; 3618#if DEBUG_WIND_BUMP 3619 SkDebugf("%s spanSign=%d\n", __FUNCTION__, result); 3620#endif 3621 return result; 3622 } 3623 3624 // OPTIMIZATION: mark as debugging only if used solely by tests 3625 double t(int tIndex) const { 3626 return fTs[tIndex].fT; 3627 } 3628 3629 double tAtMid(int start, int end, double mid) const { 3630 return fTs[start].fT * (1 - mid) + fTs[end].fT * mid; 3631 } 3632 3633 bool tiny(const Angle* angle) const { 3634 int start = angle->start(); 3635 int end = angle->end(); 3636 const Span& mSpan = fTs[SkMin32(start, end)]; 3637 return mSpan.fTiny; 3638 } 3639 3640 static void TrackOutside(SkTDArray<double>& outsideTs, double end, 3641 double start) { 3642 int outCount = outsideTs.count(); 3643 if (outCount == 0 || !approximately_negative(end - outsideTs[outCount - 2])) { 3644 *outsideTs.append() = end; 3645 *outsideTs.append() = start; 3646 } 3647 } 3648 3649 void undoneSpan(int& start, int& end) { 3650 size_t tCount = fTs.count(); 3651 size_t index; 3652 for (index = 0; index < tCount; ++index) { 3653 if (!fTs[index].fDone) { 3654 break; 3655 } 3656 } 3657 SkASSERT(index < tCount - 1); 3658 start = index; 3659 double startT = fTs[index].fT; 3660 while (approximately_negative(fTs[++index].fT - startT)) 3661 SkASSERT(index < tCount); 3662 SkASSERT(index < tCount); 3663 end = index; 3664 } 3665 3666 bool unsortable(int index) const { 3667 return fTs[index].fUnsortableStart || fTs[index].fUnsortableEnd; 3668 } 3669 3670 void updatePts(const SkPoint pts[]) { 3671 fPts = pts; 3672 } 3673 3674 int updateOppWinding(int index, int endIndex) const { 3675 int lesser = SkMin32(index, endIndex); 3676 int oppWinding = oppSum(lesser); 3677 int oppSpanWinding = oppSign(index, endIndex); 3678 if (oppSpanWinding && useInnerWinding(oppWinding - oppSpanWinding, oppWinding)) { 3679 oppWinding -= oppSpanWinding; 3680 } 3681 return oppWinding; 3682 } 3683 3684 int updateOppWinding(const Angle* angle) const { 3685 int startIndex = angle->start(); 3686 int endIndex = angle->end(); 3687 return updateOppWinding(endIndex, startIndex); 3688 } 3689 3690 int updateOppWindingReverse(const Angle* angle) const { 3691 int startIndex = angle->start(); 3692 int endIndex = angle->end(); 3693 return updateOppWinding(startIndex, endIndex); 3694 } 3695 3696 int updateWinding(int index, int endIndex) const { 3697 int lesser = SkMin32(index, endIndex); 3698 int winding = windSum(lesser); 3699 int spanWinding = spanSign(index, endIndex); 3700 if (winding && useInnerWinding(winding - spanWinding, winding)) { 3701 winding -= spanWinding; 3702 } 3703 return winding; 3704 } 3705 3706 int updateWinding(const Angle* angle) const { 3707 int startIndex = angle->start(); 3708 int endIndex = angle->end(); 3709 return updateWinding(endIndex, startIndex); 3710 } 3711 3712 int updateWindingReverse(const Angle* angle) const { 3713 int startIndex = angle->start(); 3714 int endIndex = angle->end(); 3715 return updateWinding(startIndex, endIndex); 3716 } 3717 3718 SkPath::Verb verb() const { 3719 return fVerb; 3720 } 3721 3722 int windingAtT(double tHit, int tIndex, bool crossOpp, SkScalar& dx) const { 3723 if (approximately_zero(tHit - t(tIndex))) { // if we hit the end of a span, disregard 3724 return SK_MinS32; 3725 } 3726 int winding = crossOpp ? oppSum(tIndex) : windSum(tIndex); 3727 SkASSERT(winding != SK_MinS32); 3728 int windVal = crossOpp ? oppValue(tIndex) : windValue(tIndex); 3729 #if DEBUG_WINDING_AT_T 3730 SkDebugf("%s oldWinding=%d windValue=%d", __FUNCTION__, winding, windVal); 3731 #endif 3732 // see if a + change in T results in a +/- change in X (compute x'(T)) 3733 dx = (*SegmentDXAtT[fVerb])(fPts, tHit); 3734 if (fVerb > SkPath::kLine_Verb && approximately_zero(dx)) { 3735 dx = fPts[2].fX - fPts[1].fX - dx; 3736 } 3737 if (dx == 0) { 3738 #if DEBUG_WINDING_AT_T 3739 SkDebugf(" dx=0 winding=SK_MinS32\n"); 3740 #endif 3741 return SK_MinS32; 3742 } 3743 if (winding * dx > 0) { // if same signs, result is negative 3744 winding += dx > 0 ? -windVal : windVal; 3745 } 3746 #if DEBUG_WINDING_AT_T 3747 SkDebugf(" dx=%c winding=%d\n", dx > 0 ? '+' : '-', winding); 3748 #endif 3749 return winding; 3750 } 3751 3752 int windSum(int tIndex) const { 3753 return fTs[tIndex].fWindSum; 3754 } 3755 3756 int windSum(const Angle* angle) const { 3757 int start = angle->start(); 3758 int end = angle->end(); 3759 int index = SkMin32(start, end); 3760 return windSum(index); 3761 } 3762 3763 int windValue(int tIndex) const { 3764 return fTs[tIndex].fWindValue; 3765 } 3766 3767 int windValue(const Angle* angle) const { 3768 int start = angle->start(); 3769 int end = angle->end(); 3770 int index = SkMin32(start, end); 3771 return windValue(index); 3772 } 3773 3774 int windValueAt(double t) const { 3775 int count = fTs.count(); 3776 for (int index = 0; index < count; ++index) { 3777 if (fTs[index].fT == t) { 3778 return fTs[index].fWindValue; 3779 } 3780 } 3781 SkASSERT(0); 3782 return 0; 3783 } 3784 3785 SkScalar xAtT(int index) const { 3786 return xAtT(&fTs[index]); 3787 } 3788 3789 SkScalar xAtT(const Span* span) const { 3790 return xyAtT(span).fX; 3791 } 3792 3793 const SkPoint& xyAtT(int index) const { 3794 return xyAtT(&fTs[index]); 3795 } 3796 3797 const SkPoint& xyAtT(const Span* span) const { 3798 if (SkScalarIsNaN(span->fPt.fX)) { 3799 if (span->fT == 0) { 3800 span->fPt = fPts[0]; 3801 } else if (span->fT == 1) { 3802 span->fPt = fPts[fVerb]; 3803 } else { 3804 (*SegmentXYAtT[fVerb])(fPts, span->fT, &span->fPt); 3805 } 3806 } 3807 return span->fPt; 3808 } 3809 3810 // used only by right angle winding finding 3811 void xyAtT(double mid, SkPoint& pt) const { 3812 (*SegmentXYAtT[fVerb])(fPts, mid, &pt); 3813 } 3814 3815 SkScalar yAtT(int index) const { 3816 return yAtT(&fTs[index]); 3817 } 3818 3819 SkScalar yAtT(const Span* span) const { 3820 return xyAtT(span).fY; 3821 } 3822 3823 void zeroCoincidentOpp(Span* oTest, int index) { 3824 Span* const test = &fTs[index]; 3825 Span* end = test; 3826 do { 3827 end->fOppValue = 0; 3828 end = &fTs[++index]; 3829 } while (approximately_negative(end->fT - test->fT)); 3830 } 3831 3832 void zeroCoincidentOther(Span* test, const double tRatio, const double oEndT, int oIndex) { 3833 Span* const oTest = &fTs[oIndex]; 3834 Span* oEnd = oTest; 3835 const double startT = test->fT; 3836 const double oStartT = oTest->fT; 3837 double otherTMatch = (test->fT - startT) * tRatio + oStartT; 3838 while (!approximately_negative(oEndT - oEnd->fT) 3839 && approximately_negative(oEnd->fT - otherTMatch)) { 3840 oEnd->fOppValue = 0; 3841 oEnd = &fTs[++oIndex]; 3842 } 3843 } 3844 3845 void zeroSpan(Span* span) { 3846 SkASSERT(span->fWindValue > 0 || span->fOppValue > 0); 3847 span->fWindValue = 0; 3848 span->fOppValue = 0; 3849 SkASSERT(!span->fDone); 3850 span->fDone = true; 3851 ++fDoneSpans; 3852 } 3853 3854#if DEBUG_DUMP 3855 void dump() const { 3856 const char className[] = "Segment"; 3857 const int tab = 4; 3858 for (int i = 0; i < fTs.count(); ++i) { 3859 SkPoint out; 3860 (*SegmentXYAtT[fVerb])(fPts, t(i), &out); 3861 SkDebugf("%*s [%d] %s.fTs[%d]=%1.9g (%1.9g,%1.9g) other=%d" 3862 " otherT=%1.9g windSum=%d\n", 3863 tab + sizeof(className), className, fID, 3864 kLVerbStr[fVerb], i, fTs[i].fT, out.fX, out.fY, 3865 fTs[i].fOther->fID, fTs[i].fOtherT, fTs[i].fWindSum); 3866 } 3867 SkDebugf("%*s [%d] fBounds=(l:%1.9g, t:%1.9g r:%1.9g, b:%1.9g)", 3868 tab + sizeof(className), className, fID, 3869 fBounds.fLeft, fBounds.fTop, fBounds.fRight, fBounds.fBottom); 3870 } 3871#endif 3872 3873#if DEBUG_CONCIDENT 3874 // SkASSERT if pair has not already been added 3875 void debugAddTPair(double t, const Segment& other, double otherT) const { 3876 for (int i = 0; i < fTs.count(); ++i) { 3877 if (fTs[i].fT == t && fTs[i].fOther == &other && fTs[i].fOtherT == otherT) { 3878 return; 3879 } 3880 } 3881 SkASSERT(0); 3882 } 3883#endif 3884 3885#if DEBUG_DUMP 3886 int debugID() const { 3887 return fID; 3888 } 3889#endif 3890 3891#if DEBUG_WINDING 3892 void debugShowSums() const { 3893 SkDebugf("%s id=%d (%1.9g,%1.9g %1.9g,%1.9g)", __FUNCTION__, fID, 3894 fPts[0].fX, fPts[0].fY, fPts[fVerb].fX, fPts[fVerb].fY); 3895 for (int i = 0; i < fTs.count(); ++i) { 3896 const Span& span = fTs[i]; 3897 SkDebugf(" [t=%1.3g %1.9g,%1.9g w=", span.fT, xAtT(&span), yAtT(&span)); 3898 if (span.fWindSum == SK_MinS32) { 3899 SkDebugf("?"); 3900 } else { 3901 SkDebugf("%d", span.fWindSum); 3902 } 3903 SkDebugf("]"); 3904 } 3905 SkDebugf("\n"); 3906 } 3907#endif 3908 3909#if DEBUG_CONCIDENT 3910 void debugShowTs() const { 3911 SkDebugf("%s id=%d", __FUNCTION__, fID); 3912 int lastWind = -1; 3913 int lastOpp = -1; 3914 double lastT = -1; 3915 int i; 3916 for (i = 0; i < fTs.count(); ++i) { 3917 bool change = lastT != fTs[i].fT || lastWind != fTs[i].fWindValue 3918 || lastOpp != fTs[i].fOppValue; 3919 if (change && lastWind >= 0) { 3920 SkDebugf(" t=%1.3g %1.9g,%1.9g w=%d o=%d]", 3921 lastT, xyAtT(i - 1).fX, xyAtT(i - 1).fY, lastWind, lastOpp); 3922 } 3923 if (change) { 3924 SkDebugf(" [o=%d", fTs[i].fOther->fID); 3925 lastWind = fTs[i].fWindValue; 3926 lastOpp = fTs[i].fOppValue; 3927 lastT = fTs[i].fT; 3928 } else { 3929 SkDebugf(",%d", fTs[i].fOther->fID); 3930 } 3931 } 3932 if (i <= 0) { 3933 return; 3934 } 3935 SkDebugf(" t=%1.3g %1.9g,%1.9g w=%d o=%d]", 3936 lastT, xyAtT(i - 1).fX, xyAtT(i - 1).fY, lastWind, lastOpp); 3937 if (fOperand) { 3938 SkDebugf(" operand"); 3939 } 3940 if (done()) { 3941 SkDebugf(" done"); 3942 } 3943 SkDebugf("\n"); 3944 } 3945#endif 3946 3947#if DEBUG_ACTIVE_SPANS 3948 void debugShowActiveSpans() const { 3949 if (done()) { 3950 return; 3951 } 3952#if DEBUG_ACTIVE_SPANS_SHORT_FORM 3953 int lastId = -1; 3954 double lastT = -1; 3955#endif 3956 for (int i = 0; i < fTs.count(); ++i) { 3957 if (fTs[i].fDone) { 3958 continue; 3959 } 3960#if DEBUG_ACTIVE_SPANS_SHORT_FORM 3961 if (lastId == fID && lastT == fTs[i].fT) { 3962 continue; 3963 } 3964 lastId = fID; 3965 lastT = fTs[i].fT; 3966#endif 3967 SkDebugf("%s id=%d", __FUNCTION__, fID); 3968 SkDebugf(" (%1.9g,%1.9g", fPts[0].fX, fPts[0].fY); 3969 for (int vIndex = 1; vIndex <= fVerb; ++vIndex) { 3970 SkDebugf(" %1.9g,%1.9g", fPts[vIndex].fX, fPts[vIndex].fY); 3971 } 3972 const Span* span = &fTs[i]; 3973 SkDebugf(") t=%1.9g (%1.9g,%1.9g)", fTs[i].fT, 3974 xAtT(span), yAtT(span)); 3975 const Segment* other = fTs[i].fOther; 3976 SkDebugf(" other=%d otherT=%1.9g otherIndex=%d windSum=", 3977 other->fID, fTs[i].fOtherT, fTs[i].fOtherIndex); 3978 if (fTs[i].fWindSum == SK_MinS32) { 3979 SkDebugf("?"); 3980 } else { 3981 SkDebugf("%d", fTs[i].fWindSum); 3982 } 3983 SkDebugf(" windValue=%d oppValue=%d\n", fTs[i].fWindValue, fTs[i].fOppValue); 3984 } 3985 } 3986 3987 // This isn't useful yet -- but leaving it in for now in case i think of something 3988 // to use it for 3989 void validateActiveSpans() const { 3990 if (done()) { 3991 return; 3992 } 3993 int tCount = fTs.count(); 3994 for (int index = 0; index < tCount; ++index) { 3995 if (fTs[index].fDone) { 3996 continue; 3997 } 3998 // count number of connections which are not done 3999 int first = index; 4000 double baseT = fTs[index].fT; 4001 while (first > 0 && approximately_equal(fTs[first - 1].fT, baseT)) { 4002 --first; 4003 } 4004 int last = index; 4005 while (last < tCount - 1 && approximately_equal(fTs[last + 1].fT, baseT)) { 4006 ++last; 4007 } 4008 int connections = 0; 4009 connections += first > 0 && !fTs[first - 1].fDone; 4010 for (int test = first; test <= last; ++test) { 4011 connections += !fTs[test].fDone; 4012 const Segment* other = fTs[test].fOther; 4013 int oIndex = fTs[test].fOtherIndex; 4014 connections += !other->fTs[oIndex].fDone; 4015 connections += oIndex > 0 && !other->fTs[oIndex - 1].fDone; 4016 } 4017 // SkASSERT(!(connections & 1)); 4018 } 4019 } 4020#endif 4021 4022#if DEBUG_MARK_DONE 4023 void debugShowNewWinding(const char* fun, const Span& span, int winding) { 4024 const SkPoint& pt = xyAtT(&span); 4025 SkDebugf("%s id=%d", fun, fID); 4026 SkDebugf(" (%1.9g,%1.9g", fPts[0].fX, fPts[0].fY); 4027 for (int vIndex = 1; vIndex <= fVerb; ++vIndex) { 4028 SkDebugf(" %1.9g,%1.9g", fPts[vIndex].fX, fPts[vIndex].fY); 4029 } 4030 SkASSERT(&span == &span.fOther->fTs[span.fOtherIndex].fOther-> 4031 fTs[span.fOther->fTs[span.fOtherIndex].fOtherIndex]); 4032 SkDebugf(") t=%1.9g [%d] (%1.9g,%1.9g) newWindSum=%d windSum=", 4033 span.fT, span.fOther->fTs[span.fOtherIndex].fOtherIndex, pt.fX, pt.fY, winding); 4034 if (span.fWindSum == SK_MinS32) { 4035 SkDebugf("?"); 4036 } else { 4037 SkDebugf("%d", span.fWindSum); 4038 } 4039 SkDebugf(" windValue=%d\n", span.fWindValue); 4040 } 4041 4042 void debugShowNewWinding(const char* fun, const Span& span, int winding, int oppWinding) { 4043 const SkPoint& pt = xyAtT(&span); 4044 SkDebugf("%s id=%d", fun, fID); 4045 SkDebugf(" (%1.9g,%1.9g", fPts[0].fX, fPts[0].fY); 4046 for (int vIndex = 1; vIndex <= fVerb; ++vIndex) { 4047 SkDebugf(" %1.9g,%1.9g", fPts[vIndex].fX, fPts[vIndex].fY); 4048 } 4049 SkASSERT(&span == &span.fOther->fTs[span.fOtherIndex].fOther-> 4050 fTs[span.fOther->fTs[span.fOtherIndex].fOtherIndex]); 4051 SkDebugf(") t=%1.9g [%d] (%1.9g,%1.9g) newWindSum=%d newOppSum=%d oppSum=", 4052 span.fT, span.fOther->fTs[span.fOtherIndex].fOtherIndex, pt.fX, pt.fY, 4053 winding, oppWinding); 4054 if (span.fOppSum == SK_MinS32) { 4055 SkDebugf("?"); 4056 } else { 4057 SkDebugf("%d", span.fOppSum); 4058 } 4059 SkDebugf(" windSum="); 4060 if (span.fWindSum == SK_MinS32) { 4061 SkDebugf("?"); 4062 } else { 4063 SkDebugf("%d", span.fWindSum); 4064 } 4065 SkDebugf(" windValue=%d\n", span.fWindValue); 4066 } 4067#endif 4068 4069#if DEBUG_SORT 4070 void debugShowSort(const char* fun, const SkTDArray<Angle*>& angles, int first, 4071 const int contourWinding, const int oppContourWinding) const { 4072 SkASSERT(angles[first]->segment() == this); 4073 SkASSERT(angles.count() > 1); 4074 int lastSum = contourWinding; 4075 int oppLastSum = oppContourWinding; 4076 const Angle* firstAngle = angles[first]; 4077 int windSum = lastSum - spanSign(firstAngle); 4078 int oppoSign = oppSign(firstAngle); 4079 int oppWindSum = oppLastSum - oppoSign; 4080 SkDebugf("%s %s contourWinding=%d oppContourWinding=%d sign=%d\n", fun, __FUNCTION__, 4081 contourWinding, oppContourWinding, spanSign(angles[first])); 4082 int index = first; 4083 bool firstTime = true; 4084 do { 4085 const Angle& angle = *angles[index]; 4086 const Segment& segment = *angle.segment(); 4087 int start = angle.start(); 4088 int end = angle.end(); 4089 const Span& sSpan = segment.fTs[start]; 4090 const Span& eSpan = segment.fTs[end]; 4091 const Span& mSpan = segment.fTs[SkMin32(start, end)]; 4092 bool opp = segment.fOperand ^ fOperand; 4093 if (!firstTime) { 4094 oppoSign = segment.oppSign(&angle); 4095 if (opp) { 4096 oppLastSum = oppWindSum; 4097 oppWindSum -= segment.spanSign(&angle); 4098 if (oppoSign) { 4099 lastSum = windSum; 4100 windSum -= oppoSign; 4101 } 4102 } else { 4103 lastSum = windSum; 4104 windSum -= segment.spanSign(&angle); 4105 if (oppoSign) { 4106 oppLastSum = oppWindSum; 4107 oppWindSum -= oppoSign; 4108 } 4109 } 4110 } 4111 SkDebugf("%s [%d] %sid=%d %s start=%d (%1.9g,%,1.9g) end=%d (%1.9g,%,1.9g)" 4112 " sign=%d windValue=%d windSum=", 4113 __FUNCTION__, index, angle.unsortable() ? "*** UNSORTABLE *** " : "", 4114 segment.fID, kLVerbStr[segment.fVerb], 4115 start, segment.xAtT(&sSpan), segment.yAtT(&sSpan), end, 4116 segment.xAtT(&eSpan), segment.yAtT(&eSpan), angle.sign(), 4117 mSpan.fWindValue); 4118 if (mSpan.fWindSum == SK_MinS32) { 4119 SkDebugf("?"); 4120 } else { 4121 SkDebugf("%d", mSpan.fWindSum); 4122 } 4123 int last, wind; 4124 if (opp) { 4125 last = oppLastSum; 4126 wind = oppWindSum; 4127 } else { 4128 last = lastSum; 4129 wind = windSum; 4130 } 4131 if (!oppoSign) { 4132 SkDebugf(" %d->%d (max=%d)", last, wind, 4133 useInnerWinding(last, wind) ? wind : last); 4134 } else { 4135 SkDebugf(" %d->%d (%d->%d)", last, wind, opp ? lastSum : oppLastSum, 4136 opp ? windSum : oppWindSum); 4137 } 4138 SkDebugf(" done=%d tiny=%d opp=%d\n", mSpan.fDone, mSpan.fTiny, opp); 4139#if false && DEBUG_ANGLE 4140 angle.debugShow(segment.xyAtT(&sSpan)); 4141#endif 4142 ++index; 4143 if (index == angles.count()) { 4144 index = 0; 4145 } 4146 if (firstTime) { 4147 firstTime = false; 4148 } 4149 } while (index != first); 4150 } 4151 4152 void debugShowSort(const char* fun, const SkTDArray<Angle*>& angles, int first) { 4153 const Angle* firstAngle = angles[first]; 4154 const Segment* segment = firstAngle->segment(); 4155 int winding = segment->updateWinding(firstAngle); 4156 int oppWinding = segment->updateOppWinding(firstAngle); 4157 debugShowSort(fun, angles, first, winding, oppWinding); 4158 } 4159 4160#endif 4161 4162#if DEBUG_WINDING 4163 static char as_digit(int value) { 4164 return value < 0 ? '?' : value <= 9 ? '0' + value : '+'; 4165 } 4166#endif 4167 4168#if DEBUG_SHOW_WINDING 4169 int debugShowWindingValues(int slotCount, int ofInterest) const { 4170 if (!(1 << fID & ofInterest)) { 4171 return 0; 4172 } 4173 int sum = 0; 4174 SkTDArray<char> slots; 4175 slots.setCount(slotCount * 2); 4176 memset(slots.begin(), ' ', slotCount * 2); 4177 for (int i = 0; i < fTs.count(); ++i) { 4178 // if (!(1 << fTs[i].fOther->fID & ofInterest)) { 4179 // continue; 4180 // } 4181 sum += fTs[i].fWindValue; 4182 slots[fTs[i].fOther->fID - 1] = as_digit(fTs[i].fWindValue); 4183 sum += fTs[i].fOppValue; 4184 slots[slotCount + fTs[i].fOther->fID - 1] = as_digit(fTs[i].fOppValue); 4185 } 4186 SkDebugf("%s id=%2d %.*s | %.*s\n", __FUNCTION__, fID, slotCount, slots.begin(), slotCount, 4187 slots.begin() + slotCount); 4188 return sum; 4189 } 4190#endif 4191 4192private: 4193 const SkPoint* fPts; 4194 Bounds fBounds; 4195 SkTDArray<Span> fTs; // two or more (always includes t=0 t=1) 4196 // OPTIMIZATION: could pack donespans, verb, operand, xor into 1 int-sized value 4197 int fDoneSpans; // quick check that segment is finished 4198 // OPTIMIZATION: force the following to be byte-sized 4199 SkPath::Verb fVerb; 4200 bool fOperand; 4201 bool fXor; // set if original contour had even-odd fill 4202 bool fOppXor; // set if opposite operand had even-odd fill 4203#if DEBUG_DUMP 4204 int fID; 4205#endif 4206}; 4207 4208class Contour; 4209 4210struct Coincidence { 4211 Contour* fContours[2]; 4212 int fSegments[2]; 4213 double fTs[2][2]; 4214 SkPoint fPts[2]; 4215}; 4216 4217class Contour { 4218public: 4219 Contour() { 4220 reset(); 4221#if DEBUG_DUMP 4222 fID = ++gContourID; 4223#endif 4224 } 4225 4226 bool operator<(const Contour& rh) const { 4227 return fBounds.fTop == rh.fBounds.fTop 4228 ? fBounds.fLeft < rh.fBounds.fLeft 4229 : fBounds.fTop < rh.fBounds.fTop; 4230 } 4231 4232 void addCoincident(int index, Contour* other, int otherIndex, 4233 const Intersections& ts, bool swap) { 4234 Coincidence& coincidence = *fCoincidences.append(); 4235 coincidence.fContours[0] = this; // FIXME: no need to store 4236 coincidence.fContours[1] = other; 4237 coincidence.fSegments[0] = index; 4238 coincidence.fSegments[1] = otherIndex; 4239 coincidence.fTs[swap][0] = ts.fT[0][0]; 4240 coincidence.fTs[swap][1] = ts.fT[0][1]; 4241 coincidence.fTs[!swap][0] = ts.fT[1][0]; 4242 coincidence.fTs[!swap][1] = ts.fT[1][1]; 4243 coincidence.fPts[0] = ts.fPt[0].asSkPoint(); 4244 coincidence.fPts[1] = ts.fPt[1].asSkPoint(); 4245 } 4246 4247 void addCross(const Contour* crosser) { 4248#ifdef DEBUG_CROSS 4249 for (int index = 0; index < fCrosses.count(); ++index) { 4250 SkASSERT(fCrosses[index] != crosser); 4251 } 4252#endif 4253 *fCrosses.append() = crosser; 4254 } 4255 4256 void addCubic(const SkPoint pts[4]) { 4257 fSegments.push_back().addCubic(pts, fOperand, fXor); 4258 fContainsCurves = true; 4259 } 4260 4261 int addLine(const SkPoint pts[2]) { 4262 fSegments.push_back().addLine(pts, fOperand, fXor); 4263 return fSegments.count(); 4264 } 4265 4266 void addOtherT(int segIndex, int tIndex, double otherT, int otherIndex) { 4267 fSegments[segIndex].addOtherT(tIndex, otherT, otherIndex); 4268 } 4269 4270 int addQuad(const SkPoint pts[3]) { 4271 fSegments.push_back().addQuad(pts, fOperand, fXor); 4272 fContainsCurves = true; 4273 return fSegments.count(); 4274 } 4275 4276 int addT(int segIndex, double newT, Contour* other, int otherIndex, const SkPoint& pt) { 4277 containsIntercepts(); 4278 return fSegments[segIndex].addT(newT, &other->fSegments[otherIndex], pt); 4279 } 4280 4281 int addUnsortableT(int segIndex, double newT, Contour* other, int otherIndex, bool start, 4282 const SkPoint& pt) { 4283 return fSegments[segIndex].addUnsortableT(newT, &other->fSegments[otherIndex], start, pt); 4284 } 4285 4286 const Bounds& bounds() const { 4287 return fBounds; 4288 } 4289 4290 void complete() { 4291 setBounds(); 4292 fContainsIntercepts = false; 4293 } 4294 4295 void containsIntercepts() { 4296 fContainsIntercepts = true; 4297 } 4298 4299 bool crosses(const Contour* crosser) const { 4300 for (int index = 0; index < fCrosses.count(); ++index) { 4301 if (fCrosses[index] == crosser) { 4302 return true; 4303 } 4304 } 4305 return false; 4306 } 4307 4308 bool done() const { 4309 return fDone; 4310 } 4311 4312 const SkPoint& end() const { 4313 const Segment& segment = fSegments.back(); 4314 return segment.pts()[segment.verb()]; 4315 } 4316 4317 void findTooCloseToCall() { 4318 int segmentCount = fSegments.count(); 4319 for (int sIndex = 0; sIndex < segmentCount; ++sIndex) { 4320 fSegments[sIndex].findTooCloseToCall(); 4321 } 4322 } 4323 4324 void fixOtherTIndex() { 4325 int segmentCount = fSegments.count(); 4326 for (int sIndex = 0; sIndex < segmentCount; ++sIndex) { 4327 fSegments[sIndex].fixOtherTIndex(); 4328 } 4329 } 4330 4331 Segment* nonVerticalSegment(int& start, int& end) { 4332 int segmentCount = fSortedSegments.count(); 4333 SkASSERT(segmentCount > 0); 4334 for (int sortedIndex = fFirstSorted; sortedIndex < segmentCount; ++sortedIndex) { 4335 Segment* testSegment = fSortedSegments[sortedIndex]; 4336 if (testSegment->done()) { 4337 continue; 4338 } 4339 start = end = 0; 4340 while (testSegment->nextCandidate(start, end)) { 4341 if (!testSegment->isVertical(start, end)) { 4342 return testSegment; 4343 } 4344 } 4345 } 4346 return NULL; 4347 } 4348 4349 bool operand() const { 4350 return fOperand; 4351 } 4352 4353 void reset() { 4354 fSegments.reset(); 4355 fBounds.set(SK_ScalarMax, SK_ScalarMax, SK_ScalarMax, SK_ScalarMax); 4356 fContainsCurves = fContainsIntercepts = fDone = false; 4357 } 4358 4359 void resolveCoincidence(SkTDArray<Contour*>& contourList) { 4360 int count = fCoincidences.count(); 4361 for (int index = 0; index < count; ++index) { 4362 Coincidence& coincidence = fCoincidences[index]; 4363 SkASSERT(coincidence.fContours[0] == this); 4364 int thisIndex = coincidence.fSegments[0]; 4365 Segment& thisOne = fSegments[thisIndex]; 4366 Contour* otherContour = coincidence.fContours[1]; 4367 int otherIndex = coincidence.fSegments[1]; 4368 Segment& other = otherContour->fSegments[otherIndex]; 4369 if ((thisOne.done() || other.done()) && thisOne.complete() && other.complete()) { 4370 continue; 4371 } 4372 #if DEBUG_CONCIDENT 4373 thisOne.debugShowTs(); 4374 other.debugShowTs(); 4375 #endif 4376 double startT = coincidence.fTs[0][0]; 4377 double endT = coincidence.fTs[0][1]; 4378 bool cancelers = false; 4379 if (startT > endT) { 4380 SkTSwap<double>(startT, endT); 4381 cancelers ^= true; // FIXME: just assign true 4382 } 4383 SkASSERT(!approximately_negative(endT - startT)); 4384 double oStartT = coincidence.fTs[1][0]; 4385 double oEndT = coincidence.fTs[1][1]; 4386 if (oStartT > oEndT) { 4387 SkTSwap<double>(oStartT, oEndT); 4388 cancelers ^= true; 4389 } 4390 SkASSERT(!approximately_negative(oEndT - oStartT)); 4391 bool opp = fOperand ^ otherContour->fOperand; 4392 if (cancelers && !opp) { 4393 // make sure startT and endT have t entries 4394 if (startT > 0 || oEndT < 1 4395 || thisOne.isMissing(startT) || other.isMissing(oEndT)) { 4396 thisOne.addTPair(startT, other, oEndT, true, coincidence.fPts[0]); 4397 } 4398 if (oStartT > 0 || endT < 1 4399 || thisOne.isMissing(endT) || other.isMissing(oStartT)) { 4400 other.addTPair(oStartT, thisOne, endT, true, coincidence.fPts[1]); 4401 } 4402 if (!thisOne.done() && !other.done()) { 4403 thisOne.addTCancel(startT, endT, other, oStartT, oEndT); 4404 } 4405 } else { 4406 if (startT > 0 || oStartT > 0 4407 || thisOne.isMissing(startT) || other.isMissing(oStartT)) { 4408 thisOne.addTPair(startT, other, oStartT, true, coincidence.fPts[0]); 4409 } 4410 if (endT < 1 || oEndT < 1 4411 || thisOne.isMissing(endT) || other.isMissing(oEndT)) { 4412 other.addTPair(oEndT, thisOne, endT, true, coincidence.fPts[1]); 4413 } 4414 if (!thisOne.done() && !other.done()) { 4415 thisOne.addTCoincident(startT, endT, other, oStartT, oEndT); 4416 } 4417 } 4418 #if DEBUG_CONCIDENT 4419 thisOne.debugShowTs(); 4420 other.debugShowTs(); 4421 #endif 4422 #if DEBUG_SHOW_WINDING 4423 debugShowWindingValues(contourList); 4424 #endif 4425 } 4426 } 4427 4428 // first pass, add missing T values 4429 // second pass, determine winding values of overlaps 4430 void addCoincidentPoints() { 4431 int count = fCoincidences.count(); 4432 for (int index = 0; index < count; ++index) { 4433 Coincidence& coincidence = fCoincidences[index]; 4434 SkASSERT(coincidence.fContours[0] == this); 4435 int thisIndex = coincidence.fSegments[0]; 4436 Segment& thisOne = fSegments[thisIndex]; 4437 Contour* otherContour = coincidence.fContours[1]; 4438 int otherIndex = coincidence.fSegments[1]; 4439 Segment& other = otherContour->fSegments[otherIndex]; 4440 if ((thisOne.done() || other.done()) && thisOne.complete() && other.complete()) { 4441 // OPTIMIZATION: remove from array 4442 continue; 4443 } 4444 #if DEBUG_CONCIDENT 4445 thisOne.debugShowTs(); 4446 other.debugShowTs(); 4447 #endif 4448 double startT = coincidence.fTs[0][0]; 4449 double endT = coincidence.fTs[0][1]; 4450 bool cancelers; 4451 if ((cancelers = startT > endT)) { 4452 SkTSwap<double>(startT, endT); 4453 } 4454 SkASSERT(!approximately_negative(endT - startT)); 4455 double oStartT = coincidence.fTs[1][0]; 4456 double oEndT = coincidence.fTs[1][1]; 4457 if (oStartT > oEndT) { 4458 SkTSwap<double>(oStartT, oEndT); 4459 cancelers ^= true; 4460 } 4461 SkASSERT(!approximately_negative(oEndT - oStartT)); 4462 bool opp = fOperand ^ otherContour->fOperand; 4463 if (cancelers && !opp) { 4464 // make sure startT and endT have t entries 4465 if (startT > 0 || oEndT < 1 4466 || thisOne.isMissing(startT) || other.isMissing(oEndT)) { 4467 thisOne.addTPair(startT, other, oEndT, true, coincidence.fPts[0]); 4468 } 4469 if (oStartT > 0 || endT < 1 4470 || thisOne.isMissing(endT) || other.isMissing(oStartT)) { 4471 other.addTPair(oStartT, thisOne, endT, true, coincidence.fPts[1]); 4472 } 4473 } else { 4474 if (startT > 0 || oStartT > 0 4475 || thisOne.isMissing(startT) || other.isMissing(oStartT)) { 4476 thisOne.addTPair(startT, other, oStartT, true, coincidence.fPts[0]); 4477 } 4478 if (endT < 1 || oEndT < 1 4479 || thisOne.isMissing(endT) || other.isMissing(oEndT)) { 4480 other.addTPair(oEndT, thisOne, endT, true, coincidence.fPts[1]); 4481 } 4482 } 4483 #if DEBUG_CONCIDENT 4484 thisOne.debugShowTs(); 4485 other.debugShowTs(); 4486 #endif 4487 } 4488 } 4489 4490 void calcCoincidentWinding() { 4491 int count = fCoincidences.count(); 4492 for (int index = 0; index < count; ++index) { 4493 Coincidence& coincidence = fCoincidences[index]; 4494 SkASSERT(coincidence.fContours[0] == this); 4495 int thisIndex = coincidence.fSegments[0]; 4496 Segment& thisOne = fSegments[thisIndex]; 4497 if (thisOne.done()) { 4498 continue; 4499 } 4500 Contour* otherContour = coincidence.fContours[1]; 4501 int otherIndex = coincidence.fSegments[1]; 4502 Segment& other = otherContour->fSegments[otherIndex]; 4503 if (other.done()) { 4504 continue; 4505 } 4506 double startT = coincidence.fTs[0][0]; 4507 double endT = coincidence.fTs[0][1]; 4508 bool cancelers; 4509 if ((cancelers = startT > endT)) { 4510 SkTSwap<double>(startT, endT); 4511 } 4512 SkASSERT(!approximately_negative(endT - startT)); 4513 double oStartT = coincidence.fTs[1][0]; 4514 double oEndT = coincidence.fTs[1][1]; 4515 if (oStartT > oEndT) { 4516 SkTSwap<double>(oStartT, oEndT); 4517 cancelers ^= true; 4518 } 4519 SkASSERT(!approximately_negative(oEndT - oStartT)); 4520 bool opp = fOperand ^ otherContour->fOperand; 4521 if (cancelers && !opp) { 4522 // make sure startT and endT have t entries 4523 if (!thisOne.done() && !other.done()) { 4524 thisOne.addTCancel(startT, endT, other, oStartT, oEndT); 4525 } 4526 } else { 4527 if (!thisOne.done() && !other.done()) { 4528 thisOne.addTCoincident(startT, endT, other, oStartT, oEndT); 4529 } 4530 } 4531 #if DEBUG_CONCIDENT 4532 thisOne.debugShowTs(); 4533 other.debugShowTs(); 4534 #endif 4535 } 4536 } 4537 4538 SkTArray<Segment>& segments() { 4539 return fSegments; 4540 } 4541 4542 void setOperand(bool isOp) { 4543 fOperand = isOp; 4544 } 4545 4546 void setOppXor(bool isOppXor) { 4547 fOppXor = isOppXor; 4548 int segmentCount = fSegments.count(); 4549 for (int test = 0; test < segmentCount; ++test) { 4550 fSegments[test].setOppXor(isOppXor); 4551 } 4552 } 4553 4554 void setXor(bool isXor) { 4555 fXor = isXor; 4556 } 4557 4558 void sortSegments() { 4559 int segmentCount = fSegments.count(); 4560 fSortedSegments.setReserve(segmentCount); 4561 for (int test = 0; test < segmentCount; ++test) { 4562 *fSortedSegments.append() = &fSegments[test]; 4563 } 4564 QSort<Segment>(fSortedSegments.begin(), fSortedSegments.end() - 1); 4565 fFirstSorted = 0; 4566 } 4567 4568 const SkPoint& start() const { 4569 return fSegments.front().pts()[0]; 4570 } 4571 4572 void toPath(PathWrapper& path) const { 4573 int segmentCount = fSegments.count(); 4574 const SkPoint& pt = fSegments.front().pts()[0]; 4575 path.deferredMove(pt); 4576 for (int test = 0; test < segmentCount; ++test) { 4577 fSegments[test].addCurveTo(0, 1, path, true); 4578 } 4579 path.close(); 4580 } 4581 4582 void toPartialBackward(PathWrapper& path) const { 4583 int segmentCount = fSegments.count(); 4584 for (int test = segmentCount - 1; test >= 0; --test) { 4585 fSegments[test].addCurveTo(1, 0, path, true); 4586 } 4587 } 4588 4589 void toPartialForward(PathWrapper& path) const { 4590 int segmentCount = fSegments.count(); 4591 for (int test = 0; test < segmentCount; ++test) { 4592 fSegments[test].addCurveTo(0, 1, path, true); 4593 } 4594 } 4595 4596 void topSortableSegment(const SkPoint& topLeft, SkPoint& bestXY, Segment*& topStart) { 4597 int segmentCount = fSortedSegments.count(); 4598 SkASSERT(segmentCount > 0); 4599 int sortedIndex = fFirstSorted; 4600 fDone = true; // may be cleared below 4601 for ( ; sortedIndex < segmentCount; ++sortedIndex) { 4602 Segment* testSegment = fSortedSegments[sortedIndex]; 4603 if (testSegment->done()) { 4604 if (sortedIndex == fFirstSorted) { 4605 ++fFirstSorted; 4606 } 4607 continue; 4608 } 4609 fDone = false; 4610 SkPoint testXY = testSegment->activeLeftTop(true, NULL); 4611 if (topStart) { 4612 if (testXY.fY < topLeft.fY) { 4613 continue; 4614 } 4615 if (testXY.fY == topLeft.fY && testXY.fX < topLeft.fX) { 4616 continue; 4617 } 4618 if (bestXY.fY < testXY.fY) { 4619 continue; 4620 } 4621 if (bestXY.fY == testXY.fY && bestXY.fX < testXY.fX) { 4622 continue; 4623 } 4624 } 4625 topStart = testSegment; 4626 bestXY = testXY; 4627 } 4628 } 4629 4630 Segment* undoneSegment(int& start, int& end) { 4631 int segmentCount = fSegments.count(); 4632 for (int test = 0; test < segmentCount; ++test) { 4633 Segment* testSegment = &fSegments[test]; 4634 if (testSegment->done()) { 4635 continue; 4636 } 4637 testSegment->undoneSpan(start, end); 4638 return testSegment; 4639 } 4640 return NULL; 4641 } 4642 4643 int updateSegment(int index, const SkPoint* pts) { 4644 Segment& segment = fSegments[index]; 4645 segment.updatePts(pts); 4646 return segment.verb() + 1; 4647 } 4648 4649#if DEBUG_TEST 4650 SkTArray<Segment>& debugSegments() { 4651 return fSegments; 4652 } 4653#endif 4654 4655#if DEBUG_DUMP 4656 void dump() { 4657 int i; 4658 const char className[] = "Contour"; 4659 const int tab = 4; 4660 SkDebugf("%s %p (contour=%d)\n", className, this, fID); 4661 for (i = 0; i < fSegments.count(); ++i) { 4662 SkDebugf("%*s.fSegments[%d]:\n", tab + sizeof(className), 4663 className, i); 4664 fSegments[i].dump(); 4665 } 4666 SkDebugf("%*s.fBounds=(l:%1.9g, t:%1.9g r:%1.9g, b:%1.9g)\n", 4667 tab + sizeof(className), className, 4668 fBounds.fLeft, fBounds.fTop, 4669 fBounds.fRight, fBounds.fBottom); 4670 SkDebugf("%*s.fContainsIntercepts=%d\n", tab + sizeof(className), 4671 className, fContainsIntercepts); 4672 SkDebugf("%*s.fContainsCurves=%d\n", tab + sizeof(className), 4673 className, fContainsCurves); 4674 } 4675#endif 4676 4677#if DEBUG_ACTIVE_SPANS 4678 void debugShowActiveSpans() { 4679 for (int index = 0; index < fSegments.count(); ++index) { 4680 fSegments[index].debugShowActiveSpans(); 4681 } 4682 } 4683 4684 void validateActiveSpans() { 4685 for (int index = 0; index < fSegments.count(); ++index) { 4686 fSegments[index].validateActiveSpans(); 4687 } 4688 } 4689#endif 4690 4691#if DEBUG_SHOW_WINDING 4692 int debugShowWindingValues(int totalSegments, int ofInterest) { 4693 int count = fSegments.count(); 4694 int sum = 0; 4695 for (int index = 0; index < count; ++index) { 4696 sum += fSegments[index].debugShowWindingValues(totalSegments, ofInterest); 4697 } 4698 // SkDebugf("%s sum=%d\n", __FUNCTION__, sum); 4699 return sum; 4700 } 4701 4702 static void debugShowWindingValues(SkTDArray<Contour*>& contourList) { 4703 // int ofInterest = 1 << 1 | 1 << 5 | 1 << 9 | 1 << 13; 4704 // int ofInterest = 1 << 4 | 1 << 8 | 1 << 12 | 1 << 16; 4705 int ofInterest = 1 << 5 | 1 << 8; 4706 int total = 0; 4707 int index; 4708 for (index = 0; index < contourList.count(); ++index) { 4709 total += contourList[index]->segments().count(); 4710 } 4711 int sum = 0; 4712 for (index = 0; index < contourList.count(); ++index) { 4713 sum += contourList[index]->debugShowWindingValues(total, ofInterest); 4714 } 4715 // SkDebugf("%s total=%d\n", __FUNCTION__, sum); 4716 } 4717#endif 4718 4719protected: 4720 void setBounds() { 4721 int count = fSegments.count(); 4722 if (count == 0) { 4723 SkDebugf("%s empty contour\n", __FUNCTION__); 4724 SkASSERT(0); 4725 // FIXME: delete empty contour? 4726 return; 4727 } 4728 fBounds = fSegments.front().bounds(); 4729 for (int index = 1; index < count; ++index) { 4730 fBounds.add(fSegments[index].bounds()); 4731 } 4732 } 4733 4734private: 4735 SkTArray<Segment> fSegments; 4736 SkTDArray<Segment*> fSortedSegments; 4737 int fFirstSorted; 4738 SkTDArray<Coincidence> fCoincidences; 4739 SkTDArray<const Contour*> fCrosses; 4740 Bounds fBounds; 4741 bool fContainsIntercepts; 4742 bool fContainsCurves; 4743 bool fDone; 4744 bool fOperand; // true for the second argument to a binary operator 4745 bool fXor; 4746 bool fOppXor; 4747#if DEBUG_DUMP 4748 int fID; 4749#endif 4750}; 4751 4752class EdgeBuilder { 4753public: 4754 4755EdgeBuilder(const PathWrapper& path, SkTArray<Contour>& contours) 4756 : fPath(path.nativePath()) 4757 , fContours(contours) 4758{ 4759 init(); 4760} 4761 4762EdgeBuilder(const SkPath& path, SkTArray<Contour>& contours) 4763 : fPath(&path) 4764 , fContours(contours) 4765{ 4766 init(); 4767} 4768 4769void init() { 4770 fCurrentContour = NULL; 4771 fOperand = false; 4772 fXorMask[0] = fXorMask[1] = (fPath->getFillType() & 1) ? kEvenOdd_Mask : kWinding_Mask; 4773#if DEBUG_DUMP 4774 gContourID = 0; 4775 gSegmentID = 0; 4776#endif 4777 fSecondHalf = preFetch(); 4778} 4779 4780void addOperand(const SkPath& path) { 4781 SkASSERT(fPathVerbs.count() > 0 && fPathVerbs.end()[-1] == SkPath::kDone_Verb); 4782 fPathVerbs.pop(); 4783 fPath = &path; 4784 fXorMask[1] = (fPath->getFillType() & 1) ? kEvenOdd_Mask : kWinding_Mask; 4785 preFetch(); 4786} 4787 4788void finish() { 4789 walk(); 4790 complete(); 4791 if (fCurrentContour && !fCurrentContour->segments().count()) { 4792 fContours.pop_back(); 4793 } 4794 // correct pointers in contours since fReducePts may have moved as it grew 4795 int cIndex = 0; 4796 int extraCount = fExtra.count(); 4797 SkASSERT(extraCount == 0 || fExtra[0] == -1); 4798 int eIndex = 0; 4799 int rIndex = 0; 4800 while (++eIndex < extraCount) { 4801 int offset = fExtra[eIndex]; 4802 if (offset < 0) { 4803 ++cIndex; 4804 continue; 4805 } 4806 fCurrentContour = &fContours[cIndex]; 4807 rIndex += fCurrentContour->updateSegment(offset - 1, 4808 &fReducePts[rIndex]); 4809 } 4810 fExtra.reset(); // we're done with this 4811} 4812 4813ShapeOpMask xorMask() const { 4814 return fXorMask[fOperand]; 4815} 4816 4817protected: 4818 4819void complete() { 4820 if (fCurrentContour && fCurrentContour->segments().count()) { 4821 fCurrentContour->complete(); 4822 fCurrentContour = NULL; 4823 } 4824} 4825 4826// FIXME:remove once we can access path pts directly 4827int preFetch() { 4828 SkPath::RawIter iter(*fPath); // FIXME: access path directly when allowed 4829 SkPoint pts[4]; 4830 SkPath::Verb verb; 4831 do { 4832 verb = iter.next(pts); 4833 *fPathVerbs.append() = verb; 4834 if (verb == SkPath::kMove_Verb) { 4835 *fPathPts.append() = pts[0]; 4836 } else if (verb >= SkPath::kLine_Verb && verb <= SkPath::kCubic_Verb) { 4837 fPathPts.append(verb, &pts[1]); 4838 } 4839 } while (verb != SkPath::kDone_Verb); 4840 return fPathVerbs.count() - 1; 4841} 4842 4843void walk() { 4844 SkPath::Verb reducedVerb; 4845 uint8_t* verbPtr = fPathVerbs.begin(); 4846 uint8_t* endOfFirstHalf = &verbPtr[fSecondHalf]; 4847 const SkPoint* pointsPtr = fPathPts.begin(); 4848 const SkPoint* finalCurveStart = NULL; 4849 const SkPoint* finalCurveEnd = NULL; 4850 SkPath::Verb verb; 4851 while ((verb = (SkPath::Verb) *verbPtr++) != SkPath::kDone_Verb) { 4852 switch (verb) { 4853 case SkPath::kMove_Verb: 4854 complete(); 4855 if (!fCurrentContour) { 4856 fCurrentContour = fContours.push_back_n(1); 4857 fCurrentContour->setOperand(fOperand); 4858 fCurrentContour->setXor(fXorMask[fOperand] == kEvenOdd_Mask); 4859 *fExtra.append() = -1; // start new contour 4860 } 4861 finalCurveEnd = pointsPtr++; 4862 goto nextVerb; 4863 case SkPath::kLine_Verb: 4864 // skip degenerate points 4865 if (pointsPtr[-1].fX != pointsPtr[0].fX 4866 || pointsPtr[-1].fY != pointsPtr[0].fY) { 4867 fCurrentContour->addLine(&pointsPtr[-1]); 4868 } 4869 break; 4870 case SkPath::kQuad_Verb: 4871 4872 reducedVerb = QuadReduceOrder(&pointsPtr[-1], fReducePts); 4873 if (reducedVerb == 0) { 4874 break; // skip degenerate points 4875 } 4876 if (reducedVerb == 1) { 4877 *fExtra.append() = 4878 fCurrentContour->addLine(fReducePts.end() - 2); 4879 break; 4880 } 4881 fCurrentContour->addQuad(&pointsPtr[-1]); 4882 break; 4883 case SkPath::kCubic_Verb: 4884 reducedVerb = CubicReduceOrder(&pointsPtr[-1], fReducePts); 4885 if (reducedVerb == 0) { 4886 break; // skip degenerate points 4887 } 4888 if (reducedVerb == 1) { 4889 *fExtra.append() = 4890 fCurrentContour->addLine(fReducePts.end() - 2); 4891 break; 4892 } 4893 if (reducedVerb == 2) { 4894 *fExtra.append() = 4895 fCurrentContour->addQuad(fReducePts.end() - 3); 4896 break; 4897 } 4898 fCurrentContour->addCubic(&pointsPtr[-1]); 4899 break; 4900 case SkPath::kClose_Verb: 4901 SkASSERT(fCurrentContour); 4902 if (finalCurveStart && finalCurveEnd 4903 && *finalCurveStart != *finalCurveEnd) { 4904 *fReducePts.append() = *finalCurveStart; 4905 *fReducePts.append() = *finalCurveEnd; 4906 *fExtra.append() = 4907 fCurrentContour->addLine(fReducePts.end() - 2); 4908 } 4909 complete(); 4910 goto nextVerb; 4911 default: 4912 SkDEBUGFAIL("bad verb"); 4913 return; 4914 } 4915 finalCurveStart = &pointsPtr[verb - 1]; 4916 pointsPtr += verb; 4917 SkASSERT(fCurrentContour); 4918 nextVerb: 4919 if (verbPtr == endOfFirstHalf) { 4920 fOperand = true; 4921 } 4922 } 4923} 4924 4925private: 4926 const SkPath* fPath; 4927 SkTDArray<SkPoint> fPathPts; // FIXME: point directly to path pts instead 4928 SkTDArray<uint8_t> fPathVerbs; // FIXME: remove 4929 Contour* fCurrentContour; 4930 SkTArray<Contour>& fContours; 4931 SkTDArray<SkPoint> fReducePts; // segments created on the fly 4932 SkTDArray<int> fExtra; // -1 marks new contour, > 0 offsets into contour 4933 ShapeOpMask fXorMask[2]; 4934 int fSecondHalf; 4935 bool fOperand; 4936}; 4937 4938class Work { 4939public: 4940 enum SegmentType { 4941 kHorizontalLine_Segment = -1, 4942 kVerticalLine_Segment = 0, 4943 kLine_Segment = SkPath::kLine_Verb, 4944 kQuad_Segment = SkPath::kQuad_Verb, 4945 kCubic_Segment = SkPath::kCubic_Verb, 4946 }; 4947 4948 void addCoincident(Work& other, const Intersections& ts, bool swap) { 4949 fContour->addCoincident(fIndex, other.fContour, other.fIndex, ts, swap); 4950 } 4951 4952 // FIXME: does it make sense to write otherIndex now if we're going to 4953 // fix it up later? 4954 void addOtherT(int index, double otherT, int otherIndex) { 4955 fContour->addOtherT(fIndex, index, otherT, otherIndex); 4956 } 4957 4958 // Avoid collapsing t values that are close to the same since 4959 // we walk ts to describe consecutive intersections. Since a pair of ts can 4960 // be nearly equal, any problems caused by this should be taken care 4961 // of later. 4962 // On the edge or out of range values are negative; add 2 to get end 4963 int addT(double newT, const Work& other, const SkPoint& pt) { 4964 return fContour->addT(fIndex, newT, other.fContour, other.fIndex, pt); 4965 } 4966 4967 int addUnsortableT(double newT, const Work& other, bool start, const SkPoint& pt) { 4968 return fContour->addUnsortableT(fIndex, newT, other.fContour, other.fIndex, start, pt); 4969 } 4970 4971 bool advance() { 4972 return ++fIndex < fLast; 4973 } 4974 4975 SkScalar bottom() const { 4976 return bounds().fBottom; 4977 } 4978 4979 const Bounds& bounds() const { 4980 return fContour->segments()[fIndex].bounds(); 4981 } 4982 4983#if !APPROXIMATE_CUBICS 4984 const SkPoint* cubic() const { 4985 return fCubic; 4986 } 4987#endif 4988 4989 void init(Contour* contour) { 4990 fContour = contour; 4991 fIndex = 0; 4992 fLast = contour->segments().count(); 4993 } 4994 4995 bool isAdjacent(const Work& next) { 4996 return fContour == next.fContour && fIndex + 1 == next.fIndex; 4997 } 4998 4999 bool isFirstLast(const Work& next) { 5000 return fContour == next.fContour && fIndex == 0 5001 && next.fIndex == fLast - 1; 5002 } 5003 5004 SkScalar left() const { 5005 return bounds().fLeft; 5006 } 5007 5008#if !APPROXIMATE_CUBICS 5009 void promoteToCubic() { 5010 fCubic[0] = pts()[0]; 5011 fCubic[2] = pts()[1]; 5012 fCubic[3] = pts()[2]; 5013 fCubic[1].fX = (fCubic[0].fX + fCubic[2].fX * 2) / 3; 5014 fCubic[1].fY = (fCubic[0].fY + fCubic[2].fY * 2) / 3; 5015 fCubic[2].fX = (fCubic[3].fX + fCubic[2].fX * 2) / 3; 5016 fCubic[2].fY = (fCubic[3].fY + fCubic[2].fY * 2) / 3; 5017 } 5018#endif 5019 5020 const SkPoint* pts() const { 5021 return fContour->segments()[fIndex].pts(); 5022 } 5023 5024 SkScalar right() const { 5025 return bounds().fRight; 5026 } 5027 5028 ptrdiff_t segmentIndex() const { 5029 return fIndex; 5030 } 5031 5032 SegmentType segmentType() const { 5033 const Segment& segment = fContour->segments()[fIndex]; 5034 SegmentType type = (SegmentType) segment.verb(); 5035 if (type != kLine_Segment) { 5036 return type; 5037 } 5038 if (segment.isHorizontal()) { 5039 return kHorizontalLine_Segment; 5040 } 5041 if (segment.isVertical()) { 5042 return kVerticalLine_Segment; 5043 } 5044 return kLine_Segment; 5045 } 5046 5047 bool startAfter(const Work& after) { 5048 fIndex = after.fIndex; 5049 return advance(); 5050 } 5051 5052 SkScalar top() const { 5053 return bounds().fTop; 5054 } 5055 5056 SkPath::Verb verb() const { 5057 return fContour->segments()[fIndex].verb(); 5058 } 5059 5060 SkScalar x() const { 5061 return bounds().fLeft; 5062 } 5063 5064 bool xFlipped() const { 5065 return x() != pts()[0].fX; 5066 } 5067 5068 SkScalar y() const { 5069 return bounds().fTop; 5070 } 5071 5072 bool yFlipped() const { 5073 return y() != pts()[0].fY; 5074 } 5075 5076protected: 5077 Contour* fContour; 5078#if !APPROXIMATE_CUBICS 5079 SkPoint fCubic[4]; 5080#endif 5081 int fIndex; 5082 int fLast; 5083}; 5084 5085#if DEBUG_ADD_INTERSECTING_TS 5086static void debugShowLineIntersection(int pts, const Work& wt, const Work& wn, 5087 const Intersections& i) { 5088 SkASSERT(i.used() == pts); 5089 if (!pts) { 5090 SkDebugf("%s no intersect (%1.9g,%1.9g %1.9g,%1.9g) (%1.9g,%1.9g %1.9g,%1.9g)\n", 5091 __FUNCTION__, wt.pts()[0].fX, wt.pts()[0].fY, 5092 wt.pts()[1].fX, wt.pts()[1].fY, wn.pts()[0].fX, wn.pts()[0].fY, 5093 wn.pts()[1].fX, wn.pts()[1].fY); 5094 return; 5095 } 5096 SkDebugf("%s wtTs[0]=%1.9g (%1.9g,%1.9g %1.9g,%1.9g) (%1.9g,%1.9g)", 5097 __FUNCTION__, 5098 i.fT[0][0], wt.pts()[0].fX, wt.pts()[0].fY, 5099 wt.pts()[1].fX, wt.pts()[1].fY, i.fPt[0].x, i.fPt[0].y); 5100 if (pts == 2) { 5101 SkDebugf(" wtTs[1]=%1.9g (%1.9g,%1.9g)", i.fT[0][1], i.fPt[1].x, i.fPt[1].y); 5102 } 5103 SkDebugf(" wnTs[0]=%g (%1.9g,%1.9g %1.9g,%1.9g)", i.fT[1][0], wn.pts()[0].fX, wn.pts()[0].fY, 5104 wn.pts()[1].fX, wn.pts()[1].fY); 5105 if (pts == 2) { 5106 SkDebugf(" wnTs[1]=%1.9g", i.fT[1][1]); 5107 } 5108 SkDebugf("\n"); 5109} 5110 5111static void debugShowQuadLineIntersection(int pts, const Work& wt, 5112 const Work& wn, const Intersections& i) { 5113 SkASSERT(i.used() == pts); 5114 if (!pts) { 5115 SkDebugf("%s no intersect (%1.9g,%1.9g %1.9g,%1.9g %1.9g,%1.9g)" 5116 " (%1.9g,%1.9g %1.9g,%1.9g)\n", 5117 __FUNCTION__, wt.pts()[0].fX, wt.pts()[0].fY, 5118 wt.pts()[1].fX, wt.pts()[1].fY, wt.pts()[2].fX, wt.pts()[2].fY, 5119 wn.pts()[0].fX, wn.pts()[0].fY, wn.pts()[1].fX, wn.pts()[1].fY); 5120 return; 5121 } 5122 SkDebugf("%s wtTs[0]=%1.9g (%1.9g,%1.9g %1.9g,%1.9g %1.9g,%1.9g) (%1.9g,%1.9g)", __FUNCTION__, 5123 i.fT[0][0], wt.pts()[0].fX, wt.pts()[0].fY, 5124 wt.pts()[1].fX, wt.pts()[1].fY, wt.pts()[2].fX, wt.pts()[2].fY, 5125 i.fPt[0].x, i.fPt[0].y); 5126 for (int index = 1; index < pts; ++index) { 5127 SkDebugf(" wtTs[%d]=%1.9g (%1.9g,%1.9g)", index, i.fT[0][index], 5128 i.fPt[index].x, i.fPt[index].y); 5129 } 5130 SkDebugf(" wnTs[0]=%g (%1.9g,%1.9g %1.9g,%1.9g)", i.fT[1][0], wn.pts()[0].fX, wn.pts()[0].fY, 5131 wn.pts()[1].fX, wn.pts()[1].fY); 5132 for (int index = 1; index < pts; ++index) { 5133 SkDebugf(" wnTs[%d]=%1.9g", index, i.fT[1][index]); 5134 } 5135 SkDebugf("\n"); 5136} 5137 5138static void debugShowQuadIntersection(int pts, const Work& wt, 5139 const Work& wn, const Intersections& i) { 5140 SkASSERT(i.used() == pts); 5141 if (!pts) { 5142 SkDebugf("%s no intersect (%1.9g,%1.9g %1.9g,%1.9g %1.9g,%1.9g)" 5143 " (%1.9g,%1.9g %1.9g,%1.9g %1.9g,%1.9g)\n", 5144 __FUNCTION__, wt.pts()[0].fX, wt.pts()[0].fY, 5145 wt.pts()[1].fX, wt.pts()[1].fY, wt.pts()[2].fX, wt.pts()[2].fY, 5146 wn.pts()[0].fX, wn.pts()[0].fY, wn.pts()[1].fX, wn.pts()[1].fY, 5147 wn.pts()[2].fX, wn.pts()[2].fY ); 5148 return; 5149 } 5150 SkDebugf("%s wtTs[0]=%1.9g (%1.9g,%1.9g %1.9g,%1.9g %1.9g,%1.9g) (%1.9g,%1.9g)", __FUNCTION__, 5151 i.fT[0][0], wt.pts()[0].fX, wt.pts()[0].fY, 5152 wt.pts()[1].fX, wt.pts()[1].fY, wt.pts()[2].fX, wt.pts()[2].fY, 5153 i.fPt[0].x, i.fPt[0].y); 5154 for (int index = 1; index < pts; ++index) { 5155 SkDebugf(" wtTs[%d]=%1.9g (%1.9g,%1.9g)", index, i.fT[0][index], i.fPt[index].x, 5156 i.fPt[index].y); 5157 } 5158 SkDebugf(" wnTs[0]=%g (%1.9g,%1.9g %1.9g,%1.9g %1.9g,%1.9g)", 5159 i.fT[1][0], wn.pts()[0].fX, wn.pts()[0].fY, 5160 wn.pts()[1].fX, wn.pts()[1].fY, wn.pts()[2].fX, wn.pts()[2].fY); 5161 for (int index = 1; index < pts; ++index) { 5162 SkDebugf(" wnTs[%d]=%1.9g", index, i.fT[1][index]); 5163 } 5164 SkDebugf("\n"); 5165} 5166 5167static void debugShowCubicLineIntersection(int pts, const Work& wt, 5168 const Work& wn, const Intersections& i) { 5169 SkASSERT(i.used() == pts); 5170 if (!pts) { 5171 SkDebugf("%s no intersect (%1.9g,%1.9g %1.9g,%1.9g %1.9g,%1.9g %1.9g,%1.9g)" 5172 " (%1.9g,%1.9g %1.9g,%1.9g)\n", 5173 __FUNCTION__, wt.pts()[0].fX, wt.pts()[0].fY, wt.pts()[1].fX, wt.pts()[1].fY, 5174 wt.pts()[2].fX, wt.pts()[2].fY, wt.pts()[3].fX, wt.pts()[3].fY, 5175 wn.pts()[0].fX, wn.pts()[0].fY, wn.pts()[1].fX, wn.pts()[1].fY); 5176 return; 5177 } 5178 SkDebugf("%s wtTs[0]=%1.9g (%1.9g,%1.9g %1.9g,%1.9g %1.9g,%1.9g %1.9g,%1.9g) (%1.9g,%1.9g)", 5179 __FUNCTION__, 5180 i.fT[0][0], wt.pts()[0].fX, wt.pts()[0].fY, wt.pts()[1].fX, wt.pts()[1].fY, 5181 wt.pts()[2].fX, wt.pts()[2].fY, wt.pts()[3].fX, wt.pts()[3].fY, 5182 i.fPt[0].x, i.fPt[0].y); 5183 for (int index = 1; index < pts; ++index) { 5184 SkDebugf(" wtTs[%d]=%1.9g (%1.9g,%1.9g)", index, i.fT[0][index], i.fPt[index].x, 5185 i.fPt[index].y); 5186 } 5187 SkDebugf(" wnTs[0]=%g (%1.9g,%1.9g %1.9g,%1.9g)", 5188 i.fT[1][0], wn.pts()[0].fX, wn.pts()[0].fY, wn.pts()[1].fX, wn.pts()[1].fY); 5189 for (int index = 1; index < pts; ++index) { 5190 SkDebugf(" wnTs[%d]=%1.9g", index, i.fT[1][index]); 5191 } 5192 SkDebugf("\n"); 5193} 5194 5195// FIXME: show more than two intersection points 5196static void debugShowCubicQuadIntersection(int pts, const Work& wt, 5197 const Work& wn, const Intersections& i) { 5198 SkASSERT(i.used() == pts); 5199 if (!pts) { 5200 SkDebugf("%s no intersect (%1.9g,%1.9g %1.9g,%1.9g %1.9g,%1.9g %1.9g,%1.9g)" 5201 " (%1.9g,%1.9g %1.9g,%1.9g %1.9g,%1.9g)\n", 5202 __FUNCTION__, wt.pts()[0].fX, wt.pts()[0].fY, wt.pts()[1].fX, wt.pts()[1].fY, 5203 wt.pts()[2].fX, wt.pts()[2].fY, wt.pts()[3].fX, wt.pts()[3].fY, 5204 wn.pts()[0].fX, wn.pts()[0].fY, wn.pts()[1].fX, wn.pts()[1].fY, 5205 wn.pts()[2].fX, wn.pts()[2].fY ); 5206 return; 5207 } 5208 SkDebugf("%s wtTs[0]=%1.9g (%1.9g,%1.9g %1.9g,%1.9g %1.9g,%1.9g %1.9g,%1.9g) (%1.9g,%1.9g)", 5209 __FUNCTION__, 5210 i.fT[0][0], wt.pts()[0].fX, wt.pts()[0].fY, wt.pts()[1].fX, wt.pts()[1].fY, 5211 wt.pts()[2].fX, wt.pts()[2].fY, wt.pts()[3].fX, wt.pts()[3].fY, 5212 i.fPt[0].x, i.fPt[0].y); 5213 for (int index = 1; index < pts; ++index) { 5214 SkDebugf(" wtTs[%d]=%1.9g (%1.9g,%1.9g)", index, i.fT[0][index], i.fPt[index].x, 5215 i.fPt[index].y); 5216 } 5217 SkDebugf(" wnTs[0]=%g (%1.9g,%1.9g %1.9g,%1.9g %1.9g,%1.9g)", 5218 i.fT[1][0], wn.pts()[0].fX, wn.pts()[0].fY, wn.pts()[1].fX, wn.pts()[1].fY, 5219 wn.pts()[2].fX, wn.pts()[2].fY); 5220 for (int index = 1; index < pts; ++index) { 5221 SkDebugf(" wnTs[%d]=%1.9g", index, i.fT[1][index]); 5222 } 5223 SkDebugf("\n"); 5224} 5225 5226// FIXME: show more than two intersection points 5227static void debugShowCubicIntersection(int pts, const Work& wt, 5228 const Work& wn, const Intersections& i) { 5229 SkASSERT(i.used() == pts); 5230 if (!pts) { 5231 SkDebugf("%s no intersect (%1.9g,%1.9g %1.9g,%1.9g %1.9g,%1.9g %1.9g,%1.9g)" 5232 " (%1.9g,%1.9g %1.9g,%1.9g %1.9g,%1.9g %1.9g,%1.9g)\n", 5233 __FUNCTION__, wt.pts()[0].fX, wt.pts()[0].fY, wt.pts()[1].fX, wt.pts()[1].fY, 5234 wt.pts()[2].fX, wt.pts()[2].fY, wt.pts()[3].fX, wt.pts()[3].fY, 5235 wn.pts()[0].fX, wn.pts()[0].fY, wn.pts()[1].fX, wn.pts()[1].fY, 5236 wn.pts()[2].fX, wn.pts()[2].fY, wn.pts()[3].fX, wn.pts()[3].fY ); 5237 return; 5238 } 5239 SkDebugf("%s wtTs[0]=%1.9g (%1.9g,%1.9g %1.9g,%1.9g %1.9g,%1.9g %1.9g,%1.9g) (%1.9g,%1.9g)", 5240 __FUNCTION__, 5241 i.fT[0][0], wt.pts()[0].fX, wt.pts()[0].fY, wt.pts()[1].fX, wt.pts()[1].fY, 5242 wt.pts()[2].fX, wt.pts()[2].fY, wt.pts()[3].fX, wt.pts()[3].fY, 5243 i.fPt[0].x, i.fPt[0].y); 5244 for (int index = 1; index < pts; ++index) { 5245 SkDebugf(" wtTs[%d]=%1.9g (%1.9g,%1.9g)", index, i.fT[0][index], i.fPt[index].x, 5246 i.fPt[index].y); 5247 } 5248 SkDebugf(" wnTs[0]=%g (%1.9g,%1.9g %1.9g,%1.9g %1.9g,%1.9g %1.9g,%1.9g)", 5249 i.fT[1][0], wn.pts()[0].fX, wn.pts()[0].fY, wn.pts()[1].fX, wn.pts()[1].fY, 5250 wn.pts()[2].fX, wn.pts()[2].fY, wn.pts()[3].fX, wn.pts()[3].fY); 5251 for (int index = 1; index < pts; ++index) { 5252 SkDebugf(" wnTs[%d]=%1.9g", index, i.fT[0][index]); 5253 } 5254 SkDebugf("\n"); 5255} 5256 5257#else 5258static void debugShowLineIntersection(int , const Work& , const Work& , const Intersections& ) { 5259} 5260 5261static void debugShowQuadLineIntersection(int , const Work& , const Work& , const Intersections& ) { 5262} 5263 5264static void debugShowQuadIntersection(int , const Work& , const Work& , const Intersections& ) { 5265} 5266 5267static void debugShowCubicLineIntersection(int , const Work& , const Work& , 5268 const Intersections& ) { 5269} 5270 5271static void debugShowCubicQuadIntersection(int , const Work& , const Work& , 5272 const Intersections& ) { 5273} 5274 5275static void debugShowCubicIntersection(int , const Work& , const Work& , const Intersections& ) { 5276} 5277#endif 5278 5279static bool addIntersectTs(Contour* test, Contour* next) { 5280 5281 if (test != next) { 5282 if (test->bounds().fBottom < next->bounds().fTop) { 5283 return false; 5284 } 5285 if (!Bounds::Intersects(test->bounds(), next->bounds())) { 5286 return true; 5287 } 5288 } 5289 Work wt; 5290 wt.init(test); 5291 bool foundCommonContour = test == next; 5292 do { 5293 Work wn; 5294 wn.init(next); 5295 if (test == next && !wn.startAfter(wt)) { 5296 continue; 5297 } 5298 do { 5299 if (!Bounds::Intersects(wt.bounds(), wn.bounds())) { 5300 continue; 5301 } 5302 int pts; 5303 Intersections ts; 5304 bool swap = false; 5305 switch (wt.segmentType()) { 5306 case Work::kHorizontalLine_Segment: 5307 swap = true; 5308 switch (wn.segmentType()) { 5309 case Work::kHorizontalLine_Segment: 5310 case Work::kVerticalLine_Segment: 5311 case Work::kLine_Segment: { 5312 pts = HLineIntersect(wn.pts(), wt.left(), 5313 wt.right(), wt.y(), wt.xFlipped(), ts); 5314 debugShowLineIntersection(pts, wt, wn, ts); 5315 break; 5316 } 5317 case Work::kQuad_Segment: { 5318 pts = HQuadIntersect(wn.pts(), wt.left(), 5319 wt.right(), wt.y(), wt.xFlipped(), ts); 5320 break; 5321 } 5322 case Work::kCubic_Segment: { 5323 pts = HCubicIntersect(wn.pts(), wt.left(), 5324 wt.right(), wt.y(), wt.xFlipped(), ts); 5325 debugShowCubicLineIntersection(pts, wn, wt, ts); 5326 break; 5327 } 5328 default: 5329 SkASSERT(0); 5330 } 5331 break; 5332 case Work::kVerticalLine_Segment: 5333 swap = true; 5334 switch (wn.segmentType()) { 5335 case Work::kHorizontalLine_Segment: 5336 case Work::kVerticalLine_Segment: 5337 case Work::kLine_Segment: { 5338 pts = VLineIntersect(wn.pts(), wt.top(), 5339 wt.bottom(), wt.x(), wt.yFlipped(), ts); 5340 debugShowLineIntersection(pts, wt, wn, ts); 5341 break; 5342 } 5343 case Work::kQuad_Segment: { 5344 pts = VQuadIntersect(wn.pts(), wt.top(), 5345 wt.bottom(), wt.x(), wt.yFlipped(), ts); 5346 break; 5347 } 5348 case Work::kCubic_Segment: { 5349 pts = VCubicIntersect(wn.pts(), wt.top(), 5350 wt.bottom(), wt.x(), wt.yFlipped(), ts); 5351 debugShowCubicLineIntersection(pts, wn, wt, ts); 5352 break; 5353 } 5354 default: 5355 SkASSERT(0); 5356 } 5357 break; 5358 case Work::kLine_Segment: 5359 switch (wn.segmentType()) { 5360 case Work::kHorizontalLine_Segment: 5361 pts = HLineIntersect(wt.pts(), wn.left(), 5362 wn.right(), wn.y(), wn.xFlipped(), ts); 5363 debugShowLineIntersection(pts, wt, wn, ts); 5364 break; 5365 case Work::kVerticalLine_Segment: 5366 pts = VLineIntersect(wt.pts(), wn.top(), 5367 wn.bottom(), wn.x(), wn.yFlipped(), ts); 5368 debugShowLineIntersection(pts, wt, wn, ts); 5369 break; 5370 case Work::kLine_Segment: { 5371 pts = LineIntersect(wt.pts(), wn.pts(), ts); 5372 debugShowLineIntersection(pts, wt, wn, ts); 5373 break; 5374 } 5375 case Work::kQuad_Segment: { 5376 swap = true; 5377 pts = QuadLineIntersect(wn.pts(), wt.pts(), ts); 5378 debugShowQuadLineIntersection(pts, wn, wt, ts); 5379 break; 5380 } 5381 case Work::kCubic_Segment: { 5382 swap = true; 5383 pts = CubicLineIntersect(wn.pts(), wt.pts(), ts); 5384 debugShowCubicLineIntersection(pts, wn, wt, ts); 5385 break; 5386 } 5387 default: 5388 SkASSERT(0); 5389 } 5390 break; 5391 case Work::kQuad_Segment: 5392 switch (wn.segmentType()) { 5393 case Work::kHorizontalLine_Segment: 5394 pts = HQuadIntersect(wt.pts(), wn.left(), 5395 wn.right(), wn.y(), wn.xFlipped(), ts); 5396 break; 5397 case Work::kVerticalLine_Segment: 5398 pts = VQuadIntersect(wt.pts(), wn.top(), 5399 wn.bottom(), wn.x(), wn.yFlipped(), ts); 5400 break; 5401 case Work::kLine_Segment: { 5402 pts = QuadLineIntersect(wt.pts(), wn.pts(), ts); 5403 debugShowQuadLineIntersection(pts, wt, wn, ts); 5404 break; 5405 } 5406 case Work::kQuad_Segment: { 5407 pts = QuadIntersect(wt.pts(), wn.pts(), ts); 5408 debugShowQuadIntersection(pts, wt, wn, ts); 5409 break; 5410 } 5411 case Work::kCubic_Segment: { 5412 #if APPROXIMATE_CUBICS 5413 swap = true; 5414 pts = CubicQuadIntersect(wn.pts(), wt.pts(), ts); 5415 debugShowCubicQuadIntersection(pts, wn, wt, ts); 5416 #else 5417 wt.promoteToCubic(); 5418 pts = CubicIntersect(wt.cubic(), wn.pts(), ts); 5419 debugShowCubicIntersection(pts, wt, wn, ts); 5420 #endif 5421 break; 5422 } 5423 default: 5424 SkASSERT(0); 5425 } 5426 break; 5427 case Work::kCubic_Segment: 5428 switch (wn.segmentType()) { 5429 case Work::kHorizontalLine_Segment: 5430 pts = HCubicIntersect(wt.pts(), wn.left(), 5431 wn.right(), wn.y(), wn.xFlipped(), ts); 5432 debugShowCubicLineIntersection(pts, wt, wn, ts); 5433 break; 5434 case Work::kVerticalLine_Segment: 5435 pts = VCubicIntersect(wt.pts(), wn.top(), 5436 wn.bottom(), wn.x(), wn.yFlipped(), ts); 5437 debugShowCubicLineIntersection(pts, wt, wn, ts); 5438 break; 5439 case Work::kLine_Segment: { 5440 pts = CubicLineIntersect(wt.pts(), wn.pts(), ts); 5441 debugShowCubicLineIntersection(pts, wt, wn, ts); 5442 break; 5443 } 5444 case Work::kQuad_Segment: { 5445 #if APPROXIMATE_CUBICS 5446 pts = CubicQuadIntersect(wt.pts(), wn.pts(), ts); 5447 debugShowCubicQuadIntersection(pts, wt, wn, ts); 5448 #else 5449 wn.promoteToCubic(); 5450 pts = CubicIntersect(wt.pts(), wn.cubic(), ts); 5451 debugShowCubicIntersection(pts, wt, wn, ts); 5452 #endif 5453 break; 5454 } 5455 case Work::kCubic_Segment: { 5456 pts = CubicIntersect(wt.pts(), wn.pts(), ts); 5457 debugShowCubicIntersection(pts, wt, wn, ts); 5458 break; 5459 } 5460 default: 5461 SkASSERT(0); 5462 } 5463 break; 5464 default: 5465 SkASSERT(0); 5466 } 5467 if (!foundCommonContour && pts > 0) { 5468 test->addCross(next); 5469 next->addCross(test); 5470 foundCommonContour = true; 5471 } 5472 // in addition to recording T values, record matching segment 5473 if (ts.unsortable()) { 5474 bool start = true; 5475 for (int pt = 0; pt < ts.used(); ++pt) { 5476 // FIXME: if unsortable, the other points to the original. This logic is 5477 // untested downstream. 5478 SkPoint point = ts.fPt[pt].asSkPoint(); 5479 int testTAt = wt.addUnsortableT(ts.fT[swap][pt], wt, start, point); 5480 wt.addOtherT(testTAt, ts.fT[swap][pt], testTAt); 5481 testTAt = wn.addUnsortableT(ts.fT[!swap][pt], wn, start ^ ts.fFlip, point); 5482 wn.addOtherT(testTAt, ts.fT[!swap][pt], testTAt); 5483 start ^= true; 5484 } 5485 continue; 5486 } 5487 if (pts == 2) { 5488 if (wn.segmentType() <= Work::kLine_Segment 5489 && wt.segmentType() <= Work::kLine_Segment) { 5490 wt.addCoincident(wn, ts, swap); 5491 continue; 5492 } 5493 if (wn.segmentType() >= Work::kQuad_Segment 5494 && wt.segmentType() >= Work::kQuad_Segment 5495 && ts.fIsCoincident[0]) { 5496 SkASSERT(ts.coincidentUsed() == 2); 5497 wt.addCoincident(wn, ts, swap); 5498 continue; 5499 } 5500 5501 } 5502 for (int pt = 0; pt < pts; ++pt) { 5503 SkASSERT(ts.fT[0][pt] >= 0 && ts.fT[0][pt] <= 1); 5504 SkASSERT(ts.fT[1][pt] >= 0 && ts.fT[1][pt] <= 1); 5505 SkPoint point = ts.fPt[pt].asSkPoint(); 5506 int testTAt = wt.addT(ts.fT[swap][pt], wn, point); 5507 int nextTAt = wn.addT(ts.fT[!swap][pt], wt, point); 5508 wt.addOtherT(testTAt, ts.fT[!swap][pt ^ ts.fFlip], nextTAt); 5509 wn.addOtherT(nextTAt, ts.fT[swap][pt ^ ts.fFlip], testTAt); 5510 } 5511 } while (wn.advance()); 5512 } while (wt.advance()); 5513 return true; 5514} 5515 5516// resolve any coincident pairs found while intersecting, and 5517// see if coincidence is formed by clipping non-concident segments 5518static void coincidenceCheck(SkTDArray<Contour*>& contourList, int total) { 5519 int contourCount = contourList.count(); 5520#if ONE_PASS_COINCIDENCE_CHECK 5521 for (int cIndex = 0; cIndex < contourCount; ++cIndex) { 5522 Contour* contour = contourList[cIndex]; 5523 contour->resolveCoincidence(contourList); 5524 } 5525#else 5526 for (int cIndex = 0; cIndex < contourCount; ++cIndex) { 5527 Contour* contour = contourList[cIndex]; 5528 contour->addCoincidentPoints(); 5529 } 5530 for (int cIndex = 0; cIndex < contourCount; ++cIndex) { 5531 Contour* contour = contourList[cIndex]; 5532 contour->calcCoincidentWinding(); 5533 } 5534#endif 5535 for (int cIndex = 0; cIndex < contourCount; ++cIndex) { 5536 Contour* contour = contourList[cIndex]; 5537 contour->findTooCloseToCall(); 5538 } 5539} 5540 5541static int contourRangeCheckY(SkTDArray<Contour*>& contourList, Segment*& current, int& index, 5542 int& endIndex, double& bestHit, SkScalar& bestDx, bool& tryAgain, double& mid, bool opp) { 5543 SkPoint basePt; 5544 double tAtMid = current->tAtMid(index, endIndex, mid); 5545 current->xyAtT(tAtMid, basePt); 5546 int contourCount = contourList.count(); 5547 SkScalar bestY = SK_ScalarMin; 5548 Segment* bestSeg = NULL; 5549 int bestTIndex; 5550 bool bestOpp; 5551 bool hitSomething = false; 5552 for (int cTest = 0; cTest < contourCount; ++cTest) { 5553 Contour* contour = contourList[cTest]; 5554 bool testOpp = contour->operand() ^ current->operand() ^ opp; 5555 if (basePt.fY < contour->bounds().fTop) { 5556 continue; 5557 } 5558 if (bestY > contour->bounds().fBottom) { 5559 continue; 5560 } 5561 int segmentCount = contour->segments().count(); 5562 for (int test = 0; test < segmentCount; ++test) { 5563 Segment* testSeg = &contour->segments()[test]; 5564 SkScalar testY = bestY; 5565 double testHit; 5566 int testTIndex = testSeg->crossedSpanY(basePt, testY, testHit, hitSomething, tAtMid, 5567 testOpp, testSeg == current); 5568 if (testTIndex < 0) { 5569 if (testTIndex == SK_MinS32) { 5570 hitSomething = true; 5571 bestSeg = NULL; 5572 goto abortContours; // vertical encountered, return and try different point 5573 } 5574 continue; 5575 } 5576 if (testSeg == current && current->betweenTs(index, testHit, endIndex)) { 5577 double baseT = current->t(index); 5578 double endT = current->t(endIndex); 5579 double newMid = (testHit - baseT) / (endT - baseT); 5580#if DEBUG_WINDING 5581 SkPoint midXY, newXY; 5582 double midT = current->tAtMid(index, endIndex, mid); 5583 current->xyAtT(midT, midXY); 5584 double newMidT = current->tAtMid(index, endIndex, newMid); 5585 current->xyAtT(newMidT, newXY); 5586 SkDebugf("%s [%d] mid=%1.9g->%1.9g s=%1.9g (%1.9g,%1.9g) m=%1.9g (%1.9g,%1.9g)" 5587 " n=%1.9g (%1.9g,%1.9g) e=%1.9g (%1.9g,%1.9g)\n", __FUNCTION__, 5588 current->debugID(), mid, newMid, 5589 baseT, current->xAtT(index), current->yAtT(index), 5590 baseT + mid * (endT - baseT), midXY.fX, midXY.fY, 5591 baseT + newMid * (endT - baseT), newXY.fX, newXY.fY, 5592 endT, current->xAtT(endIndex), current->yAtT(endIndex)); 5593#endif 5594 mid = newMid * 2; // calling loop with divide by 2 before continuing 5595 return SK_MinS32; 5596 } 5597 bestSeg = testSeg; 5598 bestHit = testHit; 5599 bestOpp = testOpp; 5600 bestTIndex = testTIndex; 5601 bestY = testY; 5602 } 5603 } 5604abortContours: 5605 int result; 5606 if (!bestSeg) { 5607 result = hitSomething ? SK_MinS32 : 0; 5608 } else { 5609 if (bestSeg->windSum(bestTIndex) == SK_MinS32) { 5610 current = bestSeg; 5611 index = bestTIndex; 5612 endIndex = bestSeg->nextSpan(bestTIndex, 1); 5613 SkASSERT(index != endIndex && index >= 0 && endIndex >= 0); 5614 tryAgain = true; 5615 return 0; 5616 } 5617 result = bestSeg->windingAtT(bestHit, bestTIndex, bestOpp, bestDx); 5618 SkASSERT(bestDx); 5619 } 5620 double baseT = current->t(index); 5621 double endT = current->t(endIndex); 5622 bestHit = baseT + mid * (endT - baseT); 5623 return result; 5624} 5625 5626static Segment* findUndone(SkTDArray<Contour*>& contourList, int& start, int& end) { 5627 int contourCount = contourList.count(); 5628 Segment* result; 5629 for (int cIndex = 0; cIndex < contourCount; ++cIndex) { 5630 Contour* contour = contourList[cIndex]; 5631 result = contour->undoneSegment(start, end); 5632 if (result) { 5633 return result; 5634 } 5635 } 5636 return NULL; 5637} 5638 5639#define OLD_FIND_CHASE 1 5640 5641static Segment* findChase(SkTDArray<Span*>& chase, int& tIndex, int& endIndex) { 5642 while (chase.count()) { 5643 Span* span; 5644 chase.pop(&span); 5645 const Span& backPtr = span->fOther->span(span->fOtherIndex); 5646 Segment* segment = backPtr.fOther; 5647 tIndex = backPtr.fOtherIndex; 5648 SkTDArray<Angle> angles; 5649 int done = 0; 5650 if (segment->activeAngle(tIndex, done, angles)) { 5651 Angle* last = angles.end() - 1; 5652 tIndex = last->start(); 5653 endIndex = last->end(); 5654 #if TRY_ROTATE 5655 *chase.insert(0) = span; 5656 #else 5657 *chase.append() = span; 5658 #endif 5659 return last->segment(); 5660 } 5661 if (done == angles.count()) { 5662 continue; 5663 } 5664 SkTDArray<Angle*> sorted; 5665 bool sortable = Segment::SortAngles(angles, sorted); 5666 int angleCount = sorted.count(); 5667#if DEBUG_SORT 5668 sorted[0]->segment()->debugShowSort(__FUNCTION__, sorted, 0, 0, 0); 5669#endif 5670 if (!sortable) { 5671 continue; 5672 } 5673 // find first angle, initialize winding to computed fWindSum 5674 int firstIndex = -1; 5675 const Angle* angle; 5676#if OLD_FIND_CHASE 5677 int winding; 5678 do { 5679 angle = sorted[++firstIndex]; 5680 segment = angle->segment(); 5681 winding = segment->windSum(angle); 5682 } while (winding == SK_MinS32); 5683 int spanWinding = segment->spanSign(angle->start(), angle->end()); 5684 #if DEBUG_WINDING 5685 SkDebugf("%s winding=%d spanWinding=%d\n", 5686 __FUNCTION__, winding, spanWinding); 5687 #endif 5688 // turn span winding into contour winding 5689 if (spanWinding * winding < 0) { 5690 winding += spanWinding; 5691 } 5692 #if DEBUG_SORT 5693 segment->debugShowSort(__FUNCTION__, sorted, firstIndex, winding, 0); 5694 #endif 5695 // we care about first sign and whether wind sum indicates this 5696 // edge is inside or outside. Maybe need to pass span winding 5697 // or first winding or something into this function? 5698 // advance to first undone angle, then return it and winding 5699 // (to set whether edges are active or not) 5700 int nextIndex = firstIndex + 1; 5701 int lastIndex = firstIndex != 0 ? firstIndex : angleCount; 5702 angle = sorted[firstIndex]; 5703 winding -= angle->segment()->spanSign(angle); 5704#else 5705 do { 5706 angle = sorted[++firstIndex]; 5707 segment = angle->segment(); 5708 } while (segment->windSum(angle) == SK_MinS32); 5709 #if DEBUG_SORT 5710 segment->debugShowSort(__FUNCTION__, sorted, firstIndex); 5711 #endif 5712 int sumWinding = segment->updateWindingReverse(angle); 5713 int nextIndex = firstIndex + 1; 5714 int lastIndex = firstIndex != 0 ? firstIndex : angleCount; 5715 Segment* first = NULL; 5716#endif 5717 do { 5718 SkASSERT(nextIndex != firstIndex); 5719 if (nextIndex == angleCount) { 5720 nextIndex = 0; 5721 } 5722 angle = sorted[nextIndex]; 5723 segment = angle->segment(); 5724#if OLD_FIND_CHASE 5725 int maxWinding = winding; 5726 winding -= segment->spanSign(angle); 5727 #if DEBUG_SORT 5728 SkDebugf("%s id=%d maxWinding=%d winding=%d sign=%d\n", __FUNCTION__, 5729 segment->debugID(), maxWinding, winding, angle->sign()); 5730 #endif 5731 tIndex = angle->start(); 5732 endIndex = angle->end(); 5733 int lesser = SkMin32(tIndex, endIndex); 5734 const Span& nextSpan = segment->span(lesser); 5735 if (!nextSpan.fDone) { 5736#if 1 5737 // FIXME: this be wrong? assign startWinding if edge is in 5738 // same direction. If the direction is opposite, winding to 5739 // assign is flipped sign or +/- 1? 5740 if (useInnerWinding(maxWinding, winding)) { 5741 maxWinding = winding; 5742 } 5743 segment->markAndChaseWinding(angle, maxWinding, 0); 5744#endif 5745 break; 5746 } 5747#else 5748 int start = angle->start(); 5749 int end = angle->end(); 5750 int maxWinding; 5751 segment->setUpWinding(start, end, maxWinding, sumWinding); 5752 if (!segment->done(angle)) { 5753 if (!first) { 5754 first = segment; 5755 tIndex = start; 5756 endIndex = end; 5757 } 5758 (void) segment->markAngle(maxWinding, sumWinding, true, angle); 5759 } 5760#endif 5761 } while (++nextIndex != lastIndex); 5762 #if TRY_ROTATE 5763 *chase.insert(0) = span; 5764 #else 5765 *chase.append() = span; 5766 #endif 5767 return segment; 5768 } 5769 return NULL; 5770} 5771 5772#if DEBUG_ACTIVE_SPANS 5773static void debugShowActiveSpans(SkTDArray<Contour*>& contourList) { 5774 int index; 5775 for (index = 0; index < contourList.count(); ++ index) { 5776 contourList[index]->debugShowActiveSpans(); 5777 } 5778 for (index = 0; index < contourList.count(); ++ index) { 5779 contourList[index]->validateActiveSpans(); 5780 } 5781} 5782#endif 5783 5784static Segment* findSortableTop(SkTDArray<Contour*>& contourList, int& index, 5785 int& endIndex, SkPoint& topLeft, bool& unsortable, bool& done, bool onlySortable) { 5786 Segment* result; 5787 do { 5788 SkPoint bestXY = {SK_ScalarMax, SK_ScalarMax}; 5789 int contourCount = contourList.count(); 5790 Segment* topStart = NULL; 5791 done = true; 5792 for (int cIndex = 0; cIndex < contourCount; ++cIndex) { 5793 Contour* contour = contourList[cIndex]; 5794 if (contour->done()) { 5795 continue; 5796 } 5797 const Bounds& bounds = contour->bounds(); 5798 if (bounds.fBottom < topLeft.fY) { 5799 done = false; 5800 continue; 5801 } 5802 if (bounds.fBottom == topLeft.fY && bounds.fRight < topLeft.fX) { 5803 done = false; 5804 continue; 5805 } 5806 contour->topSortableSegment(topLeft, bestXY, topStart); 5807 if (!contour->done()) { 5808 done = false; 5809 } 5810 } 5811 if (!topStart) { 5812 return NULL; 5813 } 5814 topLeft = bestXY; 5815 result = topStart->findTop(index, endIndex, unsortable, onlySortable); 5816 } while (!result); 5817 return result; 5818} 5819 5820static int rightAngleWinding(SkTDArray<Contour*>& contourList, 5821 Segment*& current, int& index, int& endIndex, double& tHit, SkScalar& hitDx, bool& tryAgain, 5822 bool opp) { 5823 double test = 0.9; 5824 int contourWinding; 5825 do { 5826 contourWinding = contourRangeCheckY(contourList, current, index, endIndex, tHit, hitDx, 5827 tryAgain, test, opp); 5828 if (contourWinding != SK_MinS32 || tryAgain) { 5829 return contourWinding; 5830 } 5831 test /= 2; 5832 } while (!approximately_negative(test)); 5833 SkASSERT(0); // should be OK to comment out, but interested when this hits 5834 return contourWinding; 5835} 5836 5837static void skipVertical(SkTDArray<Contour*>& contourList, 5838 Segment*& current, int& index, int& endIndex) { 5839 if (!current->isVertical(index, endIndex)) { 5840 return; 5841 } 5842 int contourCount = contourList.count(); 5843 for (int cIndex = 0; cIndex < contourCount; ++cIndex) { 5844 Contour* contour = contourList[cIndex]; 5845 if (contour->done()) { 5846 continue; 5847 } 5848 current = contour->nonVerticalSegment(index, endIndex); 5849 if (current) { 5850 return; 5851 } 5852 } 5853} 5854 5855static Segment* findSortableTop(SkTDArray<Contour*>& contourList, bool& firstContour, int& index, 5856 int& endIndex, SkPoint& topLeft, bool& unsortable, bool& done, bool binary) { 5857 Segment* current = findSortableTop(contourList, index, endIndex, topLeft, unsortable, done, 5858 true); 5859 if (!current) { 5860 return NULL; 5861 } 5862 if (firstContour) { 5863 current->initWinding(index, endIndex); 5864 firstContour = false; 5865 return current; 5866 } 5867 int minIndex = SkMin32(index, endIndex); 5868 int sumWinding = current->windSum(minIndex); 5869 if (sumWinding != SK_MinS32) { 5870 return current; 5871 } 5872 sumWinding = current->computeSum(index, endIndex, binary); 5873 if (sumWinding != SK_MinS32) { 5874 return current; 5875 } 5876 int contourWinding; 5877 int oppContourWinding = 0; 5878 // the simple upward projection of the unresolved points hit unsortable angles 5879 // shoot rays at right angles to the segment to find its winding, ignoring angle cases 5880 bool tryAgain; 5881 double tHit; 5882 SkScalar hitDx = 0; 5883 SkScalar hitOppDx = 0; 5884 do { 5885 // if current is vertical, find another candidate which is not 5886 // if only remaining candidates are vertical, then they can be marked done 5887 SkASSERT(index != endIndex && index >= 0 && endIndex >= 0); 5888 skipVertical(contourList, current, index, endIndex); 5889 SkASSERT(index != endIndex && index >= 0 && endIndex >= 0); 5890 tryAgain = false; 5891 contourWinding = rightAngleWinding(contourList, current, index, endIndex, tHit, hitDx, 5892 tryAgain, false); 5893 if (tryAgain) { 5894 continue; 5895 } 5896 if (!binary) { 5897 break; 5898 } 5899 oppContourWinding = rightAngleWinding(contourList, current, index, endIndex, tHit, hitOppDx, 5900 tryAgain, true); 5901 } while (tryAgain); 5902 5903 current->initWinding(index, endIndex, tHit, contourWinding, hitDx, oppContourWinding, hitOppDx); 5904 return current; 5905} 5906 5907// rewrite that abandons keeping local track of winding 5908static bool bridgeWinding(SkTDArray<Contour*>& contourList, PathWrapper& simple) { 5909 bool firstContour = true; 5910 bool unsortable = false; 5911 bool topUnsortable = false; 5912 SkPoint topLeft = {SK_ScalarMin, SK_ScalarMin}; 5913 do { 5914 int index, endIndex; 5915 bool topDone; 5916 Segment* current = findSortableTop(contourList, firstContour, index, endIndex, topLeft, 5917 topUnsortable, topDone, false); 5918 if (!current) { 5919 if (topUnsortable || !topDone) { 5920 topUnsortable = false; 5921 SkASSERT(topLeft.fX != SK_ScalarMin && topLeft.fY != SK_ScalarMin); 5922 topLeft.fX = topLeft.fY = SK_ScalarMin; 5923 continue; 5924 } 5925 break; 5926 } 5927 SkTDArray<Span*> chaseArray; 5928 do { 5929 if (current->activeWinding(index, endIndex)) { 5930 do { 5931 #if DEBUG_ACTIVE_SPANS 5932 if (!unsortable && current->done()) { 5933 debugShowActiveSpans(contourList); 5934 } 5935 #endif 5936 SkASSERT(unsortable || !current->done()); 5937 int nextStart = index; 5938 int nextEnd = endIndex; 5939 Segment* next = current->findNextWinding(chaseArray, nextStart, nextEnd, 5940 unsortable); 5941 if (!next) { 5942 if (!unsortable && simple.hasMove() 5943 && current->verb() != SkPath::kLine_Verb 5944 && !simple.isClosed()) { 5945 current->addCurveTo(index, endIndex, simple, true); 5946 SkASSERT(simple.isClosed()); 5947 } 5948 break; 5949 } 5950 #if DEBUG_FLOW 5951 SkDebugf("%s current id=%d from=(%1.9g,%1.9g) to=(%1.9g,%1.9g)\n", __FUNCTION__, 5952 current->debugID(), current->xyAtT(index).fX, current->xyAtT(index).fY, 5953 current->xyAtT(endIndex).fX, current->xyAtT(endIndex).fY); 5954 #endif 5955 current->addCurveTo(index, endIndex, simple, true); 5956 current = next; 5957 index = nextStart; 5958 endIndex = nextEnd; 5959 } while (!simple.isClosed() && (!unsortable 5960 || !current->done(SkMin32(index, endIndex)))); 5961 if (current->activeWinding(index, endIndex) && !simple.isClosed()) { 5962 SkASSERT(unsortable); 5963 int min = SkMin32(index, endIndex); 5964 if (!current->done(min)) { 5965 current->addCurveTo(index, endIndex, simple, true); 5966 current->markDoneUnary(min); 5967 } 5968 } 5969 simple.close(); 5970 } else { 5971 Span* last = current->markAndChaseDoneUnary(index, endIndex); 5972 if (last) { 5973 *chaseArray.append() = last; 5974 } 5975 } 5976 current = findChase(chaseArray, index, endIndex); 5977 #if DEBUG_ACTIVE_SPANS 5978 debugShowActiveSpans(contourList); 5979 #endif 5980 if (!current) { 5981 break; 5982 } 5983 } while (true); 5984 } while (true); 5985 return simple.someAssemblyRequired(); 5986} 5987 5988// returns true if all edges were processed 5989static bool bridgeXor(SkTDArray<Contour*>& contourList, PathWrapper& simple) { 5990 Segment* current; 5991 int start, end; 5992 bool unsortable = false; 5993 bool closable = true; 5994 while ((current = findUndone(contourList, start, end))) { 5995 do { 5996 #if DEBUG_ACTIVE_SPANS 5997 if (!unsortable && current->done()) { 5998 debugShowActiveSpans(contourList); 5999 } 6000 #endif 6001 SkASSERT(unsortable || !current->done()); 6002 int nextStart = start; 6003 int nextEnd = end; 6004 Segment* next = current->findNextXor(nextStart, nextEnd, unsortable); 6005 if (!next) { 6006 if (!unsortable && simple.hasMove() 6007 && current->verb() != SkPath::kLine_Verb 6008 && !simple.isClosed()) { 6009 current->addCurveTo(start, end, simple, true); 6010 SkASSERT(simple.isClosed()); 6011 } 6012 break; 6013 } 6014 #if DEBUG_FLOW 6015 SkDebugf("%s current id=%d from=(%1.9g,%1.9g) to=(%1.9g,%1.9g)\n", __FUNCTION__, 6016 current->debugID(), current->xyAtT(start).fX, current->xyAtT(start).fY, 6017 current->xyAtT(end).fX, current->xyAtT(end).fY); 6018 #endif 6019 current->addCurveTo(start, end, simple, true); 6020 current = next; 6021 start = nextStart; 6022 end = nextEnd; 6023 } while (!simple.isClosed() && (!unsortable || !current->done(SkMin32(start, end)))); 6024 if (!simple.isClosed()) { 6025 SkASSERT(unsortable); 6026 int min = SkMin32(start, end); 6027 if (!current->done(min)) { 6028 current->addCurveTo(start, end, simple, true); 6029 current->markDone(min, 1); 6030 } 6031 closable = false; 6032 } 6033 simple.close(); 6034 #if DEBUG_ACTIVE_SPANS 6035 debugShowActiveSpans(contourList); 6036 #endif 6037 } 6038 return closable; 6039} 6040 6041static void fixOtherTIndex(SkTDArray<Contour*>& contourList) { 6042 int contourCount = contourList.count(); 6043 for (int cTest = 0; cTest < contourCount; ++cTest) { 6044 Contour* contour = contourList[cTest]; 6045 contour->fixOtherTIndex(); 6046 } 6047} 6048 6049static void sortSegments(SkTDArray<Contour*>& contourList) { 6050 int contourCount = contourList.count(); 6051 for (int cTest = 0; cTest < contourCount; ++cTest) { 6052 Contour* contour = contourList[cTest]; 6053 contour->sortSegments(); 6054 } 6055} 6056 6057static void makeContourList(SkTArray<Contour>& contours, SkTDArray<Contour*>& list, 6058 bool evenOdd, bool oppEvenOdd) { 6059 int count = contours.count(); 6060 if (count == 0) { 6061 return; 6062 } 6063 for (int index = 0; index < count; ++index) { 6064 Contour& contour = contours[index]; 6065 contour.setOppXor(contour.operand() ? evenOdd : oppEvenOdd); 6066 *list.append() = &contour; 6067 } 6068 QSort<Contour>(list.begin(), list.end() - 1); 6069} 6070 6071static bool approximatelyEqual(const SkPoint& a, const SkPoint& b) { 6072 return AlmostEqualUlps(a.fX, b.fX) && AlmostEqualUlps(a.fY, b.fY); 6073} 6074 6075static bool lessThan(SkTDArray<double>& distances, const int one, const int two) { 6076 return distances[one] < distances[two]; 6077} 6078 /* 6079 check start and end of each contour 6080 if not the same, record them 6081 match them up 6082 connect closest 6083 reassemble contour pieces into new path 6084 */ 6085static void assemble(const PathWrapper& path, PathWrapper& simple) { 6086#if DEBUG_PATH_CONSTRUCTION 6087 SkDebugf("%s\n", __FUNCTION__); 6088#endif 6089 SkTArray<Contour> contours; 6090 EdgeBuilder builder(path, contours); 6091 builder.finish(); 6092 int count = contours.count(); 6093 int outer; 6094 SkTDArray<int> runs; // indices of partial contours 6095 for (outer = 0; outer < count; ++outer) { 6096 const Contour& eContour = contours[outer]; 6097 const SkPoint& eStart = eContour.start(); 6098 const SkPoint& eEnd = eContour.end(); 6099#if DEBUG_ASSEMBLE 6100 SkDebugf("%s contour", __FUNCTION__); 6101 if (!approximatelyEqual(eStart, eEnd)) { 6102 SkDebugf("[%d]", runs.count()); 6103 } else { 6104 SkDebugf(" "); 6105 } 6106 SkDebugf(" start=(%1.9g,%1.9g) end=(%1.9g,%1.9g)\n", 6107 eStart.fX, eStart.fY, eEnd.fX, eEnd.fY); 6108#endif 6109 if (approximatelyEqual(eStart, eEnd)) { 6110 eContour.toPath(simple); 6111 continue; 6112 } 6113 *runs.append() = outer; 6114 } 6115 count = runs.count(); 6116 if (count == 0) { 6117 return; 6118 } 6119 SkTDArray<int> sLink, eLink; 6120 sLink.setCount(count); 6121 eLink.setCount(count); 6122 int rIndex, iIndex; 6123 for (rIndex = 0; rIndex < count; ++rIndex) { 6124 sLink[rIndex] = eLink[rIndex] = SK_MaxS32; 6125 } 6126 SkTDArray<double> distances; 6127 const int ends = count * 2; // all starts and ends 6128 const int entries = (ends - 1) * count; // folded triangle : n * (n - 1) / 2 6129 distances.setCount(entries); 6130 for (rIndex = 0; rIndex < ends - 1; ++rIndex) { 6131 outer = runs[rIndex >> 1]; 6132 const Contour& oContour = contours[outer]; 6133 const SkPoint& oPt = rIndex & 1 ? oContour.end() : oContour.start(); 6134 const int row = rIndex < count - 1 ? rIndex * ends : (ends - rIndex - 2) 6135 * ends - rIndex - 1; 6136 for (iIndex = rIndex + 1; iIndex < ends; ++iIndex) { 6137 int inner = runs[iIndex >> 1]; 6138 const Contour& iContour = contours[inner]; 6139 const SkPoint& iPt = iIndex & 1 ? iContour.end() : iContour.start(); 6140 double dx = iPt.fX - oPt.fX; 6141 double dy = iPt.fY - oPt.fY; 6142 double dist = dx * dx + dy * dy; 6143 distances[row + iIndex] = dist; // oStart distance from iStart 6144 } 6145 } 6146 SkTDArray<int> sortedDist; 6147 sortedDist.setCount(entries); 6148 for (rIndex = 0; rIndex < entries; ++rIndex) { 6149 sortedDist[rIndex] = rIndex; 6150 } 6151 QSort<SkTDArray<double>, int>(distances, sortedDist.begin(), sortedDist.end() - 1, lessThan); 6152 int remaining = count; // number of start/end pairs 6153 for (rIndex = 0; rIndex < entries; ++rIndex) { 6154 int pair = sortedDist[rIndex]; 6155 int row = pair / ends; 6156 int col = pair - row * ends; 6157 int thingOne = row < col ? row : ends - row - 2; 6158 int ndxOne = thingOne >> 1; 6159 bool endOne = thingOne & 1; 6160 int* linkOne = endOne ? eLink.begin() : sLink.begin(); 6161 if (linkOne[ndxOne] != SK_MaxS32) { 6162 continue; 6163 } 6164 int thingTwo = row < col ? col : ends - row + col - 1; 6165 int ndxTwo = thingTwo >> 1; 6166 bool endTwo = thingTwo & 1; 6167 int* linkTwo = endTwo ? eLink.begin() : sLink.begin(); 6168 if (linkTwo[ndxTwo] != SK_MaxS32) { 6169 continue; 6170 } 6171 SkASSERT(&linkOne[ndxOne] != &linkTwo[ndxTwo]); 6172 bool flip = endOne == endTwo; 6173 linkOne[ndxOne] = flip ? ~ndxTwo : ndxTwo; 6174 linkTwo[ndxTwo] = flip ? ~ndxOne : ndxOne; 6175 if (!--remaining) { 6176 break; 6177 } 6178 } 6179 SkASSERT(!remaining); 6180#if DEBUG_ASSEMBLE 6181 for (rIndex = 0; rIndex < count; ++rIndex) { 6182 int s = sLink[rIndex]; 6183 int e = eLink[rIndex]; 6184 SkDebugf("%s %c%d <- s%d - e%d -> %c%d\n", __FUNCTION__, s < 0 ? 's' : 'e', 6185 s < 0 ? ~s : s, rIndex, rIndex, e < 0 ? 'e' : 's', e < 0 ? ~e : e); 6186 } 6187#endif 6188 rIndex = 0; 6189 do { 6190 bool forward = true; 6191 bool first = true; 6192 int sIndex = sLink[rIndex]; 6193 SkASSERT(sIndex != SK_MaxS32); 6194 sLink[rIndex] = SK_MaxS32; 6195 int eIndex; 6196 if (sIndex < 0) { 6197 eIndex = sLink[~sIndex]; 6198 sLink[~sIndex] = SK_MaxS32; 6199 } else { 6200 eIndex = eLink[sIndex]; 6201 eLink[sIndex] = SK_MaxS32; 6202 } 6203 SkASSERT(eIndex != SK_MaxS32); 6204#if DEBUG_ASSEMBLE 6205 SkDebugf("%s sIndex=%c%d eIndex=%c%d\n", __FUNCTION__, sIndex < 0 ? 's' : 'e', 6206 sIndex < 0 ? ~sIndex : sIndex, eIndex < 0 ? 's' : 'e', 6207 eIndex < 0 ? ~eIndex : eIndex); 6208#endif 6209 do { 6210 outer = runs[rIndex]; 6211 const Contour& contour = contours[outer]; 6212 if (first) { 6213 first = false; 6214 const SkPoint* startPtr = &contour.start(); 6215 simple.deferredMove(startPtr[0]); 6216 } 6217 if (forward) { 6218 contour.toPartialForward(simple); 6219 } else { 6220 contour.toPartialBackward(simple); 6221 } 6222#if DEBUG_ASSEMBLE 6223 SkDebugf("%s rIndex=%d eIndex=%s%d close=%d\n", __FUNCTION__, rIndex, 6224 eIndex < 0 ? "~" : "", eIndex < 0 ? ~eIndex : eIndex, 6225 sIndex == ((rIndex != eIndex) ^ forward ? eIndex : ~eIndex)); 6226#endif 6227 if (sIndex == ((rIndex != eIndex) ^ forward ? eIndex : ~eIndex)) { 6228 simple.close(); 6229 break; 6230 } 6231 if (forward) { 6232 eIndex = eLink[rIndex]; 6233 SkASSERT(eIndex != SK_MaxS32); 6234 eLink[rIndex] = SK_MaxS32; 6235 if (eIndex >= 0) { 6236 SkASSERT(sLink[eIndex] == rIndex); 6237 sLink[eIndex] = SK_MaxS32; 6238 } else { 6239 SkASSERT(eLink[~eIndex] == ~rIndex); 6240 eLink[~eIndex] = SK_MaxS32; 6241 } 6242 } else { 6243 eIndex = sLink[rIndex]; 6244 SkASSERT(eIndex != SK_MaxS32); 6245 sLink[rIndex] = SK_MaxS32; 6246 if (eIndex >= 0) { 6247 SkASSERT(eLink[eIndex] == rIndex); 6248 eLink[eIndex] = SK_MaxS32; 6249 } else { 6250 SkASSERT(sLink[~eIndex] == ~rIndex); 6251 sLink[~eIndex] = SK_MaxS32; 6252 } 6253 } 6254 rIndex = eIndex; 6255 if (rIndex < 0) { 6256 forward ^= 1; 6257 rIndex = ~rIndex; 6258 } 6259 } while (true); 6260 for (rIndex = 0; rIndex < count; ++rIndex) { 6261 if (sLink[rIndex] != SK_MaxS32) { 6262 break; 6263 } 6264 } 6265 } while (rIndex < count); 6266#if DEBUG_ASSEMBLE 6267 for (rIndex = 0; rIndex < count; ++rIndex) { 6268 SkASSERT(sLink[rIndex] == SK_MaxS32); 6269 SkASSERT(eLink[rIndex] == SK_MaxS32); 6270 } 6271#endif 6272} 6273 6274void simplifyx(const SkPath& path, SkPath& result) { 6275 // returns 1 for evenodd, -1 for winding, regardless of inverse-ness 6276 result.reset(); 6277 result.setFillType(SkPath::kEvenOdd_FillType); 6278 PathWrapper simple(result); 6279 6280 // turn path into list of segments 6281 SkTArray<Contour> contours; 6282 // FIXME: add self-intersecting cubics' T values to segment 6283 EdgeBuilder builder(path, contours); 6284 builder.finish(); 6285 SkTDArray<Contour*> contourList; 6286 makeContourList(contours, contourList, false, false); 6287 Contour** currentPtr = contourList.begin(); 6288 if (!currentPtr) { 6289 return; 6290 } 6291 Contour** listEnd = contourList.end(); 6292 // find all intersections between segments 6293 do { 6294 Contour** nextPtr = currentPtr; 6295 Contour* current = *currentPtr++; 6296 Contour* next; 6297 do { 6298 next = *nextPtr++; 6299 } while (addIntersectTs(current, next) && nextPtr != listEnd); 6300 } while (currentPtr != listEnd); 6301 // eat through coincident edges 6302 coincidenceCheck(contourList, 0); 6303 fixOtherTIndex(contourList); 6304 sortSegments(contourList); 6305#if DEBUG_ACTIVE_SPANS 6306 debugShowActiveSpans(contourList); 6307#endif 6308 // construct closed contours 6309 if (builder.xorMask() == kWinding_Mask ? bridgeWinding(contourList, simple) 6310 : !bridgeXor(contourList, simple)) 6311 { // if some edges could not be resolved, assemble remaining fragments 6312 SkPath temp; 6313 temp.setFillType(SkPath::kEvenOdd_FillType); 6314 PathWrapper assembled(temp); 6315 assemble(simple, assembled); 6316 result = *assembled.nativePath(); 6317 } 6318} 6319