src/third_party/skia/src/pathops/SkOpSegment.cpp

   1 /*
   2  * Copyright 2012 Google Inc.
   3  *
   4  * Use of this source code is governed by a BSD-style license that can be
   5  * found in the LICENSE file.
   6  */
   7 #include "SkIntersections.h"
   8 #include "SkOpContour.h"
   9 #include "SkOpSegment.h"
  10 #include "SkPathWriter.h"
  11 #include "SkTSort.h"
  12
  13 #define F (false)      // discard the edge
  14 #define T (true)       // keep the edge
  15
  16 static const bool gUnaryActiveEdge[2][2] = {
  17 //  from=0  from=1
  18 //  to=0,1  to=0,1
  19     {F, T}, {T, F},
  20 };
  21
  22 static const bool gActiveEdge[kXOR_PathOp + 1][2][2][2][2] = {
  23 //                 miFrom=0                              miFrom=1
  24 //         miTo=0             miTo=1             miTo=0             miTo=1
  25 //     suFrom=0    1      suFrom=0    1      suFrom=0    1      suFrom=0    1
  26 //   suTo=0,1 suTo=0,1  suTo=0,1 suTo=0,1  suTo=0,1 suTo=0,1  suTo=0,1 suTo=0,1
  27     {{{{F, F}, {F, F}}, {{T, F}, {T, F}}}, {{{T, T}, {F, F}}, {{F, T}, {T, F}}}},  // mi - su
  28     {{{{F, F}, {F, F}}, {{F, T}, {F, T}}}, {{{F, F}, {T, T}}, {{F, T}, {T, F}}}},  // mi & su
  29     {{{{F, T}, {T, F}}, {{T, T}, {F, F}}}, {{{T, F}, {T, F}}, {{F, F}, {F, F}}}},  // mi | su
  30     {{{{F, T}, {T, F}}, {{T, F}, {F, T}}}, {{{T, F}, {F, T}}, {{F, T}, {T, F}}}},  // mi ^ su
  31 };
  32
  33 #undef F
  34 #undef T
  35
  36 enum {
  37     kOutsideTrackedTCount = 16,  // FIXME: determine what this should be
  38     kMissingSpanCount = 4,  // FIXME: determine what this should be
  39 };
  40
  41 const SkOpAngle* SkOpSegment::activeAngle(int index, int* start, int* end, bool* done,
  42         bool* sortable) const {
  43     if (const SkOpAngle* result = activeAngleInner(index, start, end, done, sortable)) {
  44         return result;
  45     }
  46     double referenceT = fTs[index].fT;
  47     int lesser = index;
  48     while (--lesser >= 0
  49             && (precisely_negative(referenceT - fTs[lesser].fT) || fTs[lesser].fTiny)) {
  50         if (const SkOpAngle* result = activeAngleOther(lesser, start, end, done, sortable)) {
  51             return result;
  52         }
  53     }
  54     do {
  55         if (const SkOpAngle* result = activeAngleOther(index, start, end, done, sortable)) {
  56             return result;
  57         }
  58         if (++index == fTs.count()) {
  59             break;
  60         }
  61         if (fTs[index - 1].fTiny) {
  62             referenceT = fTs[index].fT;
  63             continue;
  64         }
  65     } while (precisely_negative(fTs[index].fT - referenceT));
  66     return NULL;
  67 }
  68
  69 const SkOpAngle* SkOpSegment::activeAngleInner(int index, int* start, int* end, bool* done,
  70         bool* sortable) const {
  71     int next = nextExactSpan(index, 1);
  72     if (next > 0) {
  73         const SkOpSpan& upSpan = fTs[index];
  74         if (upSpan.fWindValue || upSpan.fOppValue) {
  75             if (*end < 0) {
  76                 *start = index;
  77                 *end = next;
  78             }
  79             if (!upSpan.fDone) {
  80                 if (upSpan.fWindSum != SK_MinS32) {
  81                     return spanToAngle(index, next);
  82                 }
  83                 *done = false;
  84             }
  85         } else {
  86             SkASSERT(upSpan.fDone);
  87         }
  88     }
  89     int prev = nextExactSpan(index, -1);
  90     // edge leading into junction
  91     if (prev >= 0) {
  92         const SkOpSpan& downSpan = fTs[prev];
  93         if (downSpan.fWindValue || downSpan.fOppValue) {
  94             if (*end < 0) {
  95                 *start = index;
  96                 *end = prev;
  97             }
  98             if (!downSpan.fDone) {
  99                 if (downSpan.fWindSum != SK_MinS32) {
 100                     return spanToAngle(index, prev);
 101                 }
 102                 *done = false;
 103             }
 104         } else {
 105             SkASSERT(downSpan.fDone);
 106         }
 107     }
 108     return NULL;
 109 }
 110
 111 const SkOpAngle* SkOpSegment::activeAngleOther(int index, int* start, int* end, bool* done,
 112         bool* sortable) const {
 113     const SkOpSpan* span = &fTs[index];
 114     SkOpSegment* other = span->fOther;
 115     int oIndex = span->fOtherIndex;
 116     return other->activeAngleInner(oIndex, start, end, done, sortable);
 117 }
 118
 119 SkPoint SkOpSegment::activeLeftTop(int* firstT) const {
 120     SkASSERT(!done());
 121     SkPoint topPt = {SK_ScalarMax, SK_ScalarMax};
 122     int count = fTs.count();
 123     // see if either end is not done since we want smaller Y of the pair
 124     bool lastDone = true;
 125     double lastT = -1;
 126     for (int index = 0; index < count; ++index) {
 127         const SkOpSpan& span = fTs[index];
 128         if (span.fDone && lastDone) {
 129             goto next;
 130         }
 131         if (approximately_negative(span.fT - lastT)) {
 132             goto next;
 133         }
 134         {
 135             const SkPoint& xy = xyAtT(&span);
 136             if (topPt.fY > xy.fY || (topPt.fY == xy.fY && topPt.fX > xy.fX)) {
 137                 topPt = xy;
 138                 if (firstT) {
 139                     *firstT = index;
 140                 }
 141             }
 142             if (fVerb != SkPath::kLine_Verb && !lastDone) {
 143                 SkPoint curveTop = (*CurveTop[SkPathOpsVerbToPoints(fVerb)])(fPts, lastT, span.fT);
 144                 if (topPt.fY > curveTop.fY || (topPt.fY == curveTop.fY
 145                         && topPt.fX > curveTop.fX)) {
 146                     topPt = curveTop;
 147                     if (firstT) {
 148                         *firstT = index;
 149                     }
 150                 }
 151             }
 152             lastT = span.fT;
 153         }
 154 next:
 155         lastDone = span.fDone;
 156     }
 157     return topPt;
 158 }
 159
 160 bool SkOpSegment::activeOp(int index, int endIndex, int xorMiMask, int xorSuMask, SkPathOp op) {
 161     int sumMiWinding = updateWinding(endIndex, index);
 162     int sumSuWinding = updateOppWinding(endIndex, index);
 163     if (fOperand) {
 164         SkTSwap<int>(sumMiWinding, sumSuWinding);
 165     }
 166     return activeOp(xorMiMask, xorSuMask, index, endIndex, op, &sumMiWinding, &sumSuWinding);
 167 }
 168
 169 bool SkOpSegment::activeOp(int xorMiMask, int xorSuMask, int index, int endIndex, SkPathOp op,
 170         int* sumMiWinding, int* sumSuWinding) {
 171     int maxWinding, sumWinding, oppMaxWinding, oppSumWinding;
 172     setUpWindings(index, endIndex, sumMiWinding, sumSuWinding,
 173             &maxWinding, &sumWinding, &oppMaxWinding, &oppSumWinding);
 174     bool miFrom;
 175     bool miTo;
 176     bool suFrom;
 177     bool suTo;
 178     if (operand()) {
 179         miFrom = (oppMaxWinding & xorMiMask) != 0;
 180         miTo = (oppSumWinding & xorMiMask) != 0;
 181         suFrom = (maxWinding & xorSuMask) != 0;
 182         suTo = (sumWinding & xorSuMask) != 0;
 183     } else {
 184         miFrom = (maxWinding & xorMiMask) != 0;
 185         miTo = (sumWinding & xorMiMask) != 0;
 186         suFrom = (oppMaxWinding & xorSuMask) != 0;
 187         suTo = (oppSumWinding & xorSuMask) != 0;
 188     }
 189     bool result = gActiveEdge[op][miFrom][miTo][suFrom][suTo];
 190 #if DEBUG_ACTIVE_OP
 191     SkDebugf("%s id=%d t=%1.9g tEnd=%1.9g op=%s miFrom=%d miTo=%d suFrom=%d suTo=%d result=%d\n",
 192             __FUNCTION__, debugID(), span(index).fT, span(endIndex).fT,
 193             SkPathOpsDebug::kPathOpStr[op], miFrom, miTo, suFrom, suTo, result);
 194 #endif
 195     return result;
 196 }
 197
 198 bool SkOpSegment::activeWinding(int index, int endIndex) {
 199     int sumWinding = updateWinding(endIndex, index);
 200     return activeWinding(index, endIndex, &sumWinding);
 201 }
 202
 203 bool SkOpSegment::activeWinding(int index, int endIndex, int* sumWinding) {
 204     int maxWinding;
 205     setUpWinding(index, endIndex, &maxWinding, sumWinding);
 206     bool from = maxWinding != 0;
 207     bool to = *sumWinding  != 0;
 208     bool result = gUnaryActiveEdge[from][to];
 209     return result;
 210 }
 211
 212 void SkOpSegment::addCancelOutsides(const SkPoint& startPt, const SkPoint& endPt,
 213         SkOpSegment* other) {
 214     int tIndex = -1;
 215     int tCount = fTs.count();
 216     int oIndex = -1;
 217     int oCount = other->fTs.count();
 218     do {
 219         ++tIndex;
 220     } while (startPt != fTs[tIndex].fPt && tIndex < tCount);
 221     int tIndexStart = tIndex;
 222     do {
 223         ++oIndex;
 224     } while (endPt != other->fTs[oIndex].fPt && oIndex < oCount);
 225     int oIndexStart = oIndex;
 226     const SkPoint* nextPt;
 227     do {
 228         nextPt = &fTs[++tIndex].fPt;
 229         SkASSERT(fTs[tIndex].fT < 1 || startPt != *nextPt);
 230     } while (startPt == *nextPt);
 231     double nextT = fTs[tIndex].fT;
 232     const SkPoint* oNextPt;
 233     do {
 234         oNextPt = &other->fTs[++oIndex].fPt;
 235         SkASSERT(other->fTs[oIndex].fT < 1 || endPt != *oNextPt);
 236     } while (endPt == *oNextPt);
 237     double oNextT = other->fTs[oIndex].fT;
 238     // at this point, spans before and after are at:
 239     //  fTs[tIndexStart - 1], fTs[tIndexStart], fTs[tIndex]
 240     // if tIndexStart == 0, no prior span
 241     // if nextT == 1, no following span
 242
 243     // advance the span with zero winding
 244     // if the following span exists (not past the end, non-zero winding)
 245     // connect the two edges
 246     if (!fTs[tIndexStart].fWindValue) {
 247         if (tIndexStart > 0 && fTs[tIndexStart - 1].fWindValue) {
 248 #if DEBUG_CONCIDENT
 249             SkDebugf("%s 1 this=%d other=%d t [%d] %1.9g (%1.9g,%1.9g)\n",
 250                     __FUNCTION__, fID, other->fID, tIndexStart - 1,
 251                     fTs[tIndexStart].fT, xyAtT(tIndexStart).fX,
 252                     xyAtT(tIndexStart).fY);
 253 #endif
 254             addTPair(fTs[tIndexStart].fT, other, other->fTs[oIndex].fT, false,
 255                     fTs[tIndexStart].fPt);
 256         }
 257         if (nextT < 1 && fTs[tIndex].fWindValue) {
 258 #if DEBUG_CONCIDENT
 259             SkDebugf("%s 2 this=%d other=%d t [%d] %1.9g (%1.9g,%1.9g)\n",
 260                     __FUNCTION__, fID, other->fID, tIndex,
 261                     fTs[tIndex].fT, xyAtT(tIndex).fX,
 262                     xyAtT(tIndex).fY);
 263 #endif
 264             addTPair(fTs[tIndex].fT, other, other->fTs[oIndexStart].fT, false, fTs[tIndex].fPt);
 265         }
 266     } else {
 267         SkASSERT(!other->fTs[oIndexStart].fWindValue);
 268         if (oIndexStart > 0 && other->fTs[oIndexStart - 1].fWindValue) {
 269 #if DEBUG_CONCIDENT
 270             SkDebugf("%s 3 this=%d other=%d t [%d] %1.9g (%1.9g,%1.9g)\n",
 271                     __FUNCTION__, fID, other->fID, oIndexStart - 1,
 272                     other->fTs[oIndexStart].fT, other->xyAtT(oIndexStart).fX,
 273                     other->xyAtT(oIndexStart).fY);
 274             other->debugAddTPair(other->fTs[oIndexStart].fT, *this, fTs[tIndex].fT);
 275 #endif
 276         }
 277         if (oNextT < 1 && other->fTs[oIndex].fWindValue) {
 278 #if DEBUG_CONCIDENT
 279             SkDebugf("%s 4 this=%d other=%d t [%d] %1.9g (%1.9g,%1.9g)\n",
 280                     __FUNCTION__, fID, other->fID, oIndex,
 281                     other->fTs[oIndex].fT, other->xyAtT(oIndex).fX,
 282                     other->xyAtT(oIndex).fY);
 283             other->debugAddTPair(other->fTs[oIndex].fT, *this, fTs[tIndexStart].fT);
 284 #endif
 285         }
 286     }
 287 }
 288
 289 void SkOpSegment::addCoinOutsides(const SkPoint& startPt, const SkPoint& endPt,
 290         SkOpSegment* other) {
 291     // walk this to startPt
 292     // walk other to startPt
 293     // if either is > 0, add a pointer to the other, copying adjacent winding
 294     int tIndex = -1;
 295     int oIndex = -1;
 296     do {
 297         ++tIndex;
 298     } while (startPt != fTs[tIndex].fPt);
 299     int ttIndex = tIndex;
 300     bool checkOtherTMatch = false;
 301     do {
 302         const SkOpSpan& span = fTs[ttIndex];
 303         if (startPt != span.fPt) {
 304             break;
 305         }
 306         if (span.fOther == other && span.fPt == startPt) {
 307             checkOtherTMatch = true;
 308             break;
 309         }
 310     } while (++ttIndex < count());
 311     do {
 312         ++oIndex;
 313     } while (startPt != other->fTs[oIndex].fPt);
 314     bool skipAdd = false;
 315     if (checkOtherTMatch) {
 316         int ooIndex = oIndex;
 317         do {
 318             const SkOpSpan& oSpan = other->fTs[ooIndex];
 319             if (startPt != oSpan.fPt) {
 320                 break;
 321             }
 322             if (oSpan.fT == fTs[ttIndex].fOtherT) {
 323                 skipAdd = true;
 324                 break;
 325             }
 326         } while (++ooIndex < other->count());
 327     }
 328     if ((tIndex > 0 || oIndex > 0 || fOperand != other->fOperand) && !skipAdd) {
 329         addTPair(fTs[tIndex].fT, other, other->fTs[oIndex].fT, false, startPt);
 330     }
 331     SkPoint nextPt = startPt;
 332     do {
 333         const SkPoint* workPt;
 334         do {
 335             workPt = &fTs[++tIndex].fPt;
 336         } while (nextPt == *workPt);
 337         const SkPoint* oWorkPt;
 338         do {
 339             oWorkPt = &other->fTs[++oIndex].fPt;
 340         } while (nextPt == *oWorkPt);
 341         nextPt = *workPt;
 342         double tStart = fTs[tIndex].fT;
 343         double oStart = other->fTs[oIndex].fT;
 344         if (tStart == 1 && oStart == 1 && fOperand == other->fOperand) {
 345             break;
 346         }
 347         if (*workPt == *oWorkPt) {
 348             addTPair(tStart, other, oStart, false, nextPt);
 349         }
 350     } while (endPt != nextPt);
 351 }
 352
 353 void SkOpSegment::addCubic(const SkPoint pts[4], bool operand, bool evenOdd) {
 354     init(pts, SkPath::kCubic_Verb, operand, evenOdd);
 355     fBounds.setCubicBounds(pts);
 356 }
 357
 358 void SkOpSegment::addCurveTo(int start, int end, SkPathWriter* path, bool active) const {
 359     SkPoint edge[4];
 360     const SkPoint* ePtr;
 361     int lastT = fTs.count() - 1;
 362     if (lastT < 0 || (start == 0 && end == lastT) || (start == lastT && end == 0)) {
 363         ePtr = fPts;
 364     } else {
 365     // OPTIMIZE? if not active, skip remainder and return xyAtT(end)
 366         subDivide(start, end, edge);
 367         ePtr = edge;
 368     }
 369     if (active) {
 370         bool reverse = ePtr == fPts && start != 0;
 371         if (reverse) {
 372             path->deferredMoveLine(ePtr[SkPathOpsVerbToPoints(fVerb)]);
 373             switch (fVerb) {
 374                 case SkPath::kLine_Verb:
 375                     path->deferredLine(ePtr[0]);
 376                     break;
 377                 case SkPath::kQuad_Verb:
 378                     path->quadTo(ePtr[1], ePtr[0]);
 379                     break;
 380                 case SkPath::kCubic_Verb:
 381                     path->cubicTo(ePtr[2], ePtr[1], ePtr[0]);
 382                     break;
 383                 default:
 384                     SkASSERT(0);
 385             }
 386    //         return ePtr[0];
 387        } else {
 388             path->deferredMoveLine(ePtr[0]);
 389             switch (fVerb) {
 390                 case SkPath::kLine_Verb:
 391                     path->deferredLine(ePtr[1]);
 392                     break;
 393                 case SkPath::kQuad_Verb:
 394                     path->quadTo(ePtr[1], ePtr[2]);
 395                     break;
 396                 case SkPath::kCubic_Verb:
 397                     path->cubicTo(ePtr[1], ePtr[2], ePtr[3]);
 398                     break;
 399                 default:
 400                     SkASSERT(0);
 401             }
 402         }
 403     }
 404   //  return ePtr[SkPathOpsVerbToPoints(fVerb)];
 405 }
 406
 407 void SkOpSegment::addEndSpan(int endIndex) {
 408     SkASSERT(span(endIndex).fT == 1 || (span(endIndex).fTiny
 409             && approximately_greater_than_one(span(endIndex).fT)));
 410     int spanCount = fTs.count();
 411     int startIndex = endIndex - 1;
 412     while (fTs[startIndex].fT == 1 || fTs[startIndex].fTiny) {
 413         --startIndex;
 414         SkASSERT(startIndex > 0);
 415         --endIndex;
 416     }
 417     SkOpAngle& angle = fAngles.push_back();
 418     angle.set(this, spanCount - 1, startIndex);
 419 #if DEBUG_ANGLE
 420     debugCheckPointsEqualish(endIndex, spanCount);
 421 #endif
 422     setFromAngle(endIndex, &angle);
 423 }
 424
 425 void SkOpSegment::setFromAngle(int endIndex, SkOpAngle* angle) {
 426     int spanCount = fTs.count();
 427     do {
 428         fTs[endIndex].fFromAngle = angle;
 429     } while (++endIndex < spanCount);
 430 }
 431
 432 void SkOpSegment::addLine(const SkPoint pts[2], bool operand, bool evenOdd) {
 433     init(pts, SkPath::kLine_Verb, operand, evenOdd);
 434     fBounds.set(pts, 2);
 435 }
 436
 437 // add 2 to edge or out of range values to get T extremes
 438 void SkOpSegment::addOtherT(int index, double otherT, int otherIndex) {
 439     SkOpSpan& span = fTs[index];
 440     if (precisely_zero(otherT)) {
 441         otherT = 0;
 442     } else if (precisely_equal(otherT, 1)) {
 443         otherT = 1;
 444     }
 445     span.fOtherT = otherT;
 446     span.fOtherIndex = otherIndex;
 447 }
 448
 449 void SkOpSegment::addQuad(const SkPoint pts[3], bool operand, bool evenOdd) {
 450     init(pts, SkPath::kQuad_Verb, operand, evenOdd);
 451     fBounds.setQuadBounds(pts);
 452 }
 453
 454 SkOpAngle* SkOpSegment::addSingletonAngleDown(SkOpSegment** otherPtr, SkOpAngle** anglePtr) {
 455     int spanIndex = count() - 1;
 456     int startIndex = nextExactSpan(spanIndex, -1);
 457     SkASSERT(startIndex >= 0);
 458     SkOpAngle& angle = fAngles.push_back();
 459     *anglePtr = &angle;
 460     angle.set(this, spanIndex, startIndex);
 461     setFromAngle(spanIndex, &angle);
 462     SkOpSegment* other;
 463     int oStartIndex, oEndIndex;
 464     do {
 465         const SkOpSpan& span = fTs[spanIndex];
 466         SkASSERT(span.fT > 0);
 467         other = span.fOther;
 468         oStartIndex = span.fOtherIndex;
 469         oEndIndex = other->nextExactSpan(oStartIndex, 1);
 470         if (oEndIndex > 0 && other->span(oStartIndex).fWindValue) {
 471             break;
 472         }
 473         oEndIndex = oStartIndex;
 474         oStartIndex = other->nextExactSpan(oEndIndex, -1);
 475         --spanIndex;
 476     } while (oStartIndex < 0 || !other->span(oStartIndex).fWindSum);
 477     SkOpAngle& oAngle = other->fAngles.push_back();
 478     oAngle.set(other, oStartIndex, oEndIndex);
 479     other->setToAngle(oEndIndex, &oAngle);
 480     *otherPtr = other;
 481     return &oAngle;
 482 }
 483
 484 SkOpAngle* SkOpSegment::addSingletonAngleUp(SkOpSegment** otherPtr, SkOpAngle** anglePtr) {
 485     int endIndex = nextExactSpan(0, 1);
 486     SkASSERT(endIndex > 0);
 487     SkOpAngle& angle = fAngles.push_back();
 488     *anglePtr = &angle;
 489     angle.set(this, 0, endIndex);
 490     setToAngle(endIndex, &angle);
 491     int spanIndex = 0;
 492     SkOpSegment* other;
 493     int oStartIndex, oEndIndex;
 494     do {
 495         const SkOpSpan& span = fTs[spanIndex];
 496         SkASSERT(span.fT < 1);
 497         other = span.fOther;
 498         oEndIndex = span.fOtherIndex;
 499         oStartIndex = other->nextExactSpan(oEndIndex, -1);
 500         if (oStartIndex >= 0 && other->span(oStartIndex).fWindValue) {
 501             break;
 502         }
 503         oStartIndex = oEndIndex;
 504         oEndIndex = other->nextExactSpan(oStartIndex, 1);
 505         ++spanIndex;
 506     } while (oEndIndex < 0 || !other->span(oStartIndex).fWindValue);
 507     SkOpAngle& oAngle = other->fAngles.push_back();
 508     oAngle.set(other, oEndIndex, oStartIndex);
 509     other->setFromAngle(oEndIndex, &oAngle);
 510     *otherPtr = other;
 511     return &oAngle;
 512 }
 513
 514 SkOpAngle* SkOpSegment::addSingletonAngles(int step) {
 515     SkOpSegment* other;
 516     SkOpAngle* angle, * otherAngle;
 517     if (step > 0) {
 518         otherAngle = addSingletonAngleUp(&other, &angle);
 519     } else {
 520         otherAngle = addSingletonAngleDown(&other, &angle);
 521     }
 522     angle->insert(otherAngle);
 523     return angle;
 524 }
 525
 526 void SkOpSegment::addStartSpan(int endIndex) {
 527     int index = 0;
 528     SkOpAngle& angle = fAngles.push_back();
 529     angle.set(this, index, endIndex);
 530 #if DEBUG_ANGLE
 531     debugCheckPointsEqualish(index, endIndex);
 532 #endif
 533     setToAngle(endIndex, &angle);
 534 }
 535
 536 void SkOpSegment::setToAngle(int endIndex, SkOpAngle* angle) {
 537     int index = 0;
 538     do {
 539         fTs[index].fToAngle = angle;
 540     } while (++index < endIndex);
 541 }
 542
 543     // Defer all coincident edge processing until
 544     // after normal intersections have been computed
 545
 546 // no need to be tricky; insert in normal T order
 547 // resolve overlapping ts when considering coincidence later
 548
 549     // add non-coincident intersection. Resulting edges are sorted in T.
 550 int SkOpSegment::addT(SkOpSegment* other, const SkPoint& pt, double newT) {
 551     SkASSERT(this != other || fVerb == SkPath::kCubic_Verb);
 552  #if 0  // this needs an even rougher association to be useful
 553     SkASSERT(SkDPoint::RoughlyEqual(ptAtT(newT), pt));
 554  #endif
 555     const SkPoint& firstPt = fPts[0];
 556     const SkPoint& lastPt = fPts[SkPathOpsVerbToPoints(fVerb)];
 557     SkASSERT(newT == 0 || !precisely_zero(newT));
 558     SkASSERT(newT == 1 || !precisely_equal(newT, 1));
 559     // FIXME: in the pathological case where there is a ton of intercepts,
 560     //  binary search?
 561     int insertedAt = -1;
 562     int tCount = fTs.count();
 563     for (int index = 0; index < tCount; ++index) {
 564         // OPTIMIZATION: if there are three or more identical Ts, then
 565         // the fourth and following could be further insertion-sorted so
 566         // that all the edges are clockwise or counterclockwise.
 567         // This could later limit segment tests to the two adjacent
 568         // neighbors, although it doesn't help with determining which
 569         // circular direction to go in.
 570         const SkOpSpan& span = fTs[index];
 571         if (newT < span.fT) {
 572             insertedAt = index;
 573             break;
 574         }
 575         if (newT == span.fT) {
 576             if (pt == span.fPt) {
 577                 insertedAt = index;
 578                 break;
 579             }
 580             if ((pt == firstPt && newT == 0) || (span.fPt == lastPt && newT == 1)) {
 581                 insertedAt = index;
 582                 break;
 583             }
 584         }
 585     }
 586     SkOpSpan* span;
 587     if (insertedAt >= 0) {
 588         span = fTs.insert(insertedAt);
 589     } else {
 590         insertedAt = tCount;
 591         span = fTs.append();
 592     }
 593     span->fT = newT;
 594     span->fOtherT = -1;
 595     span->fOther = other;
 596     span->fPt = pt;
 597 #if 0
 598     // cubics, for instance, may not be exact enough to satisfy this check (e.g., cubicOp69d)
 599     SkASSERT(approximately_equal(xyAtT(newT).fX, pt.fX)
 600             && approximately_equal(xyAtT(newT).fY, pt.fY));
 601 #endif
 602     span->fFromAngle = NULL;
 603     span->fToAngle = NULL;
 604     span->fWindSum = SK_MinS32;
 605     span->fOppSum = SK_MinS32;
 606     span->fWindValue = 1;
 607     span->fOppValue = 0;
 608     span->fChased = false;
 609     span->fCoincident = false;
 610     span->fLoop = false;
 611     span->fNear = false;
 612     span->fMultiple = false;
 613     span->fSmall = false;
 614     span->fTiny = false;
 615     if ((span->fDone = newT == 1)) {
 616         ++fDoneSpans;
 617     }
 618     int less = -1;
 619 // FIXME: note that this relies on spans being a continguous array
 620 // find range of spans with nearly the same point as this one
 621     while (&span[less + 1] - fTs.begin() > 0 && AlmostEqualUlps(span[less].fPt, pt)) {
 622         if (fVerb == SkPath::kCubic_Verb) {
 623             double tInterval = newT - span[less].fT;
 624             double tMid = newT - tInterval / 2;
 625             SkDPoint midPt = dcubic_xy_at_t(fPts, tMid);
 626             if (!midPt.approximatelyEqual(xyAtT(span))) {
 627                 break;
 628             }
 629         }
 630         --less;
 631     }
 632     int more = 1;
 633     while (fTs.end() - &span[more - 1] > 1 && AlmostEqualUlps(span[more].fPt, pt)) {
 634         if (fVerb == SkPath::kCubic_Verb) {
 635             double tEndInterval = span[more].fT - newT;
 636             double tMid = newT - tEndInterval / 2;
 637             SkDPoint midEndPt = dcubic_xy_at_t(fPts, tMid);
 638             if (!midEndPt.approximatelyEqual(xyAtT(span))) {
 639                 break;
 640             }
 641         }
 642         ++more;
 643     }
 644     ++less;
 645     --more;
 646     while (more - 1 > less && span[more].fPt == span[more - 1].fPt
 647             && span[more].fT == span[more - 1].fT) {
 648         --more;
 649     }
 650     if (less == more) {
 651         return insertedAt;
 652     }
 653     if (precisely_negative(span[more].fT - span[less].fT)) {
 654         return insertedAt;
 655     }
 656 // if the total range of t values is big enough, mark all tiny
 657     bool tiny = span[less].fPt == span[more].fPt;
 658     int index = less;
 659     do {
 660         fSmall = span[index].fSmall = true;
 661         fTiny |= span[index].fTiny = tiny;
 662         if (!span[index].fDone) {
 663             span[index].fDone = true;
 664             ++fDoneSpans;
 665         }
 666     } while (++index < more);
 667     return insertedAt;
 668 }
 669
 670 // set spans from start to end to decrement by one
 671 // note this walks other backwards
 672 // FIXME: there's probably an edge case that can be constructed where
 673 // two span in one segment are separated by float epsilon on one span but
 674 // not the other, if one segment is very small. For this
 675 // case the counts asserted below may or may not be enough to separate the
 676 // spans. Even if the counts work out, what if the spans aren't correctly
 677 // sorted? It feels better in such a case to match the span's other span
 678 // pointer since both coincident segments must contain the same spans.
 679 // FIXME? It seems that decrementing by one will fail for complex paths that
 680 // have three or more coincident edges. Shouldn't this subtract the difference
 681 // between the winding values?
 682 /*                                      |-->                           |-->
 683 this     0>>>>1>>>>2>>>>3>>>4      0>>>>1>>>>2>>>>3>>>4      0>>>>1>>>>2>>>>3>>>4
 684 other         2<<<<1<<<<0               2<<<<1<<<<0               2<<<<1<<<<0
 685               ^         ^                 <--|                           <--|
 686            startPt    endPt        test/oTest first pos      test/oTest final pos
 687 */
 688 void SkOpSegment::addTCancel(const SkPoint& startPt, const SkPoint& endPt, SkOpSegment* other) {
 689     bool binary = fOperand != other->fOperand;
 690     int index = 0;
 691     while (startPt != fTs[index].fPt) {
 692         SkASSERT(index < fTs.count());
 693         ++index;
 694     }
 695     while (index > 0 && precisely_equal(fTs[index].fT, fTs[index - 1].fT)) {
 696         --index;
 697     }
 698     bool oFoundEnd = false;
 699     int oIndex = other->fTs.count();
 700     while (startPt != other->fTs[--oIndex].fPt) {  // look for startPt match
 701         SkASSERT(oIndex > 0);
 702     }
 703     double oStartT = other->fTs[oIndex].fT;
 704     // look for first point beyond match
 705     while (startPt == other->fTs[--oIndex].fPt || precisely_equal(oStartT, other->fTs[oIndex].fT)) {
 706         SkASSERT(oIndex > 0);
 707     }
 708     SkOpSpan* test = &fTs[index];
 709     SkOpSpan* oTest = &other->fTs[oIndex];
 710     SkSTArray<kOutsideTrackedTCount, SkPoint, true> outsidePts;
 711     SkSTArray<kOutsideTrackedTCount, SkPoint, true> oOutsidePts;
 712     bool decrement, track, bigger;
 713     int originalWindValue;
 714     const SkPoint* testPt;
 715     const SkPoint* oTestPt;
 716     do {
 717         SkASSERT(test->fT < 1);
 718         SkASSERT(oTest->fT < 1);
 719         decrement = test->fWindValue && oTest->fWindValue;
 720         track = test->fWindValue || oTest->fWindValue;
 721         bigger = test->fWindValue >= oTest->fWindValue;
 722         testPt = &test->fPt;
 723         double testT = test->fT;
 724         oTestPt = &oTest->fPt;
 725         double oTestT = oTest->fT;
 726         do {
 727             if (decrement) {
 728                 if (binary && bigger) {
 729                     test->fOppValue--;
 730                 } else {
 731                     decrementSpan(test);
 732                 }
 733             } else if (track) {
 734                 TrackOutsidePair(&outsidePts, *testPt, *oTestPt);
 735             }
 736             SkASSERT(index < fTs.count() - 1);
 737             test = &fTs[++index];
 738         } while (*testPt == test->fPt || precisely_equal(testT, test->fT));
 739         originalWindValue = oTest->fWindValue;
 740         do {
 741             SkASSERT(oTest->fT < 1);
 742             SkASSERT(originalWindValue == oTest->fWindValue);
 743             if (decrement) {
 744                 if (binary && !bigger) {
 745                     oTest->fOppValue--;
 746                 } else {
 747                     other->decrementSpan(oTest);
 748                 }
 749             } else if (track) {
 750                 TrackOutsidePair(&oOutsidePts, *oTestPt, *testPt);
 751             }
 752             if (!oIndex) {
 753                 break;
 754             }
 755             oFoundEnd |= endPt == oTest->fPt;
 756             oTest = &other->fTs[--oIndex];
 757         } while (*oTestPt == oTest->fPt || precisely_equal(oTestT, oTest->fT));
 758     } while (endPt != test->fPt && test->fT < 1);
 759     // FIXME: determine if canceled edges need outside ts added
 760     if (!oFoundEnd) {
 761         for (int oIdx2 = oIndex; oIdx2 >= 0; --oIdx2) {
 762             SkOpSpan* oTst2 = &other->fTs[oIdx2];
 763             if (originalWindValue != oTst2->fWindValue) {
 764                 goto skipAdvanceOtherCancel;
 765             }
 766             if (!oTst2->fWindValue) {
 767                 goto skipAdvanceOtherCancel;
 768             }
 769             if (endPt == other->fTs[oIdx2].fPt) {
 770                 break;
 771             }
 772         }
 773         do {
 774             SkASSERT(originalWindValue == oTest->fWindValue);
 775             if (decrement) {
 776                 if (binary && !bigger) {
 777                     oTest->fOppValue--;
 778                 } else {
 779                     other->decrementSpan(oTest);
 780                 }
 781             } else if (track) {
 782                 TrackOutsidePair(&oOutsidePts, *oTestPt, *testPt);
 783             }
 784             if (!oIndex) {
 785                 break;
 786             }
 787             oTest = &other->fTs[--oIndex];
 788             oFoundEnd |= endPt == oTest->fPt;
 789         } while (!oFoundEnd || endPt == oTest->fPt);
 790     }
 791 skipAdvanceOtherCancel:
 792     int outCount = outsidePts.count();
 793     if (!done() && outCount) {
 794         addCancelOutsides(outsidePts[0], outsidePts[1], other);
 795         if (outCount > 2) {
 796             addCancelOutsides(outsidePts[outCount - 2], outsidePts[outCount - 1], other);
 797         }
 798     }
 799     if (!other->done() && oOutsidePts.count()) {
 800         other->addCancelOutsides(oOutsidePts[0], oOutsidePts[1], this);
 801     }
 802     setCoincidentRange(startPt, endPt, other);
 803     other->setCoincidentRange(startPt, endPt, this);
 804 }
 805
 806 int SkOpSegment::addSelfT(const SkPoint& pt, double newT) {
 807     // if the tail nearly intersects itself but not quite, the caller records this separately
 808     int result = addT(this, pt, newT);
 809     SkOpSpan* span = &fTs[result];
 810     fLoop = span->fLoop = true;
 811     return result;
 812 }
 813
 814 // find the starting or ending span with an existing loop of angles
 815 // FIXME? replicate for all identical starting/ending spans?
 816 // OPTIMIZE? remove the spans pointing to windValue==0 here or earlier?
 817 // FIXME? assert that only one other span has a valid windValue or oppValue
 818 void SkOpSegment::addSimpleAngle(int index) {
 819     SkOpSpan* span = &fTs[index];
 820     int idx;
 821     int start, end;
 822     if (span->fT == 0) {
 823         idx = 0;
 824         span = &fTs[0];
 825         do {
 826             if (span->fToAngle) {
 827                 SkASSERT(span->fToAngle->loopCount() == 2);
 828                 SkASSERT(!span->fFromAngle);
 829                 span->fFromAngle = span->fToAngle->next();
 830                 return;
 831             }
 832             span = &fTs[++idx];
 833         } while (span->fT == 0);
 834         SkASSERT(!fTs[0].fTiny && fTs[idx].fT > 0);
 835         addStartSpan(idx);
 836         start = 0;
 837         end = idx;
 838     } else {
 839         idx = count() - 1;
 840         span = &fTs[idx];
 841         do {
 842             if (span->fFromAngle) {
 843                 SkASSERT(span->fFromAngle->loopCount() == 2);
 844                 SkASSERT(!span->fToAngle);
 845                 span->fToAngle = span->fFromAngle->next();
 846                 return;
 847             }
 848             span = &fTs[--idx];
 849         } while (span->fT == 1);
 850         SkASSERT(!fTs[idx].fTiny && fTs[idx].fT < 1);
 851         addEndSpan(++idx);
 852         start = idx;
 853         end = count();
 854     }
 855     SkOpSegment* other;
 856     SkOpSpan* oSpan;
 857     index = start;
 858     do {
 859         span = &fTs[index];
 860         other = span->fOther;
 861         int oFrom = span->fOtherIndex;
 862         oSpan = &other->fTs[oFrom];
 863         if (oSpan->fT < 1 && oSpan->fWindValue) {
 864             break;
 865         }
 866         if (oSpan->fT == 0) {
 867             continue;
 868         }
 869         oFrom = other->nextExactSpan(oFrom, -1);
 870         SkOpSpan* oFromSpan = &other->fTs[oFrom];
 871         SkASSERT(oFromSpan->fT < 1);
 872         if (oFromSpan->fWindValue) {
 873             break;
 874         }
 875     } while (++index < end);
 876     SkOpAngle* angle, * oAngle;
 877     if (span->fT == 0) {
 878         SkASSERT(span->fOtherIndex - 1 >= 0);
 879         SkASSERT(span->fOtherT == 1);
 880         SkDEBUGCODE(int oPriorIndex = other->nextExactSpan(span->fOtherIndex, -1));
 881         SkDEBUGCODE(const SkOpSpan& oPrior = other->span(oPriorIndex));
 882         SkASSERT(!oPrior.fTiny && oPrior.fT < 1);
 883         other->addEndSpan(span->fOtherIndex);
 884         angle = span->fToAngle;
 885         oAngle = oSpan->fFromAngle;
 886     } else {
 887         SkASSERT(span->fOtherIndex + 1 < other->count());
 888         SkASSERT(span->fOtherT == 0);
 889         SkASSERT(!oSpan->fTiny && (other->fTs[span->fOtherIndex + 1].fT > 0
 890                 || (other->fTs[span->fOtherIndex + 1].fFromAngle == NULL
 891                 && other->fTs[span->fOtherIndex + 1].fToAngle == NULL)));
 892         int oIndex = 1;
 893         do {
 894             const SkOpSpan& osSpan = other->span(oIndex);
 895             if (osSpan.fFromAngle || osSpan.fT > 0) {
 896                 break;
 897             }
 898             ++oIndex;
 899             SkASSERT(oIndex < other->count());
 900         } while (true);
 901         other->addStartSpan(oIndex);
 902         angle = span->fFromAngle;
 903         oAngle = oSpan->fToAngle;
 904     }
 905     angle->insert(oAngle);
 906 }
 907
 908 void SkOpSegment::alignMultiples(SkTDArray<AlignedSpan>* alignedArray) {
 909     debugValidate();
 910     int count = this->count();
 911     for (int index = 0; index < count; ++index) {
 912         SkOpSpan& span = fTs[index];
 913         if (!span.fMultiple) {
 914             continue;
 915         }
 916         int end = nextExactSpan(index, 1);
 917         SkASSERT(end > index + 1);
 918         const SkPoint& thisPt = span.fPt;
 919         while (index < end - 1) {
 920             SkOpSegment* other1 = span.fOther;
 921             int oCnt = other1->count();
 922             for (int idx2 = index + 1; idx2 < end; ++idx2) {
 923                 SkOpSpan& span2 = fTs[idx2];
 924                 SkOpSegment* other2 = span2.fOther;
 925                 for (int oIdx = 0; oIdx < oCnt; ++oIdx) {
 926                     SkOpSpan& oSpan = other1->fTs[oIdx];
 927                     if (oSpan.fOther != other2) {
 928                         continue;
 929                     }
 930                     if (oSpan.fPt == thisPt) {
 931                         goto skipExactMatches;
 932                     }
 933                 }
 934                 for (int oIdx = 0; oIdx < oCnt; ++oIdx) {
 935                     SkOpSpan& oSpan = other1->fTs[oIdx];
 936                     if (oSpan.fOther != other2) {
 937                         continue;
 938                     }
 939                     if (SkDPoint::RoughlyEqual(oSpan.fPt, thisPt)) {
 940                         SkOpSpan& oSpan2 = other2->fTs[oSpan.fOtherIndex];
 941                         if (zero_or_one(span.fOtherT) || zero_or_one(oSpan.fT)
 942                                 || zero_or_one(span2.fOtherT) || zero_or_one(oSpan2.fT)) {
 943                             return;
 944                         }
 945                         if (!way_roughly_equal(span.fOtherT, oSpan.fT)
 946                                 || !way_roughly_equal(span2.fOtherT, oSpan2.fT)
 947                                 || !way_roughly_equal(span2.fOtherT, oSpan.fOtherT)
 948                                 || !way_roughly_equal(span.fOtherT, oSpan2.fOtherT)) {
 949                             return;
 950                         }
 951                         alignSpan(thisPt, span.fOtherT, other1, span2.fOtherT,
 952                                 other2, &oSpan, alignedArray);
 953                         alignSpan(thisPt, span2.fOtherT, other2, span.fOtherT,
 954                                 other1, &oSpan2, alignedArray);
 955                         break;
 956                     }
 957                 }
 958         skipExactMatches:
 959                 ;
 960             }
 961             ++index;
 962         }
 963     }
 964     debugValidate();
 965 }
 966
 967 void SkOpSegment::alignSpan(const SkPoint& newPt, double newT, const SkOpSegment* other,
 968         double otherT, const SkOpSegment* other2, SkOpSpan* oSpan,
 969         SkTDArray<AlignedSpan>* alignedArray) {
 970     AlignedSpan* aligned = alignedArray->append();
 971     aligned->fOldPt = oSpan->fPt;
 972     aligned->fPt = newPt;
 973     aligned->fOldT = oSpan->fT;
 974     aligned->fT = newT;
 975     aligned->fSegment = this;  // OPTIMIZE: may be unused, can remove
 976     aligned->fOther1 = other;
 977     aligned->fOther2 = other2;
 978     SkASSERT(SkDPoint::RoughlyEqual(oSpan->fPt, newPt));
 979     oSpan->fPt = newPt;
 980 //    SkASSERT(way_roughly_equal(oSpan->fT, newT));
 981     oSpan->fT = newT;
 982 //    SkASSERT(way_roughly_equal(oSpan->fOtherT, otherT));
 983     oSpan->fOtherT = otherT;
 984 }
 985
 986 bool SkOpSegment::alignSpan(int index, double thisT, const SkPoint& thisPt) {
 987     bool aligned = false;
 988     SkOpSpan* span = &fTs[index];
 989     SkOpSegment* other = span->fOther;
 990     int oIndex = span->fOtherIndex;
 991     SkOpSpan* oSpan = &other->fTs[oIndex];
 992     if (span->fT != thisT) {
 993         span->fT = thisT;
 994         oSpan->fOtherT = thisT;
 995         aligned = true;
 996     }
 997     if (span->fPt != thisPt) {
 998         span->fPt = thisPt;
 999         oSpan->fPt = thisPt;
1000         aligned = true;
1001     }
1002     double oT = oSpan->fT;
1003     if (oT == 0) {
1004         return aligned;
1005     }
1006     int oStart = other->nextSpan(oIndex, -1) + 1;
1007     oSpan = &other->fTs[oStart];
1008     int otherIndex = oStart;
1009     if (oT == 1) {
1010         if (aligned) {
1011             while (oSpan->fPt == thisPt && oSpan->fT != 1) {
1012                 oSpan->fTiny = true;
1013                 ++oSpan;
1014             }
1015         }
1016         return aligned;
1017     }
1018     oT = oSpan->fT;
1019     int oEnd = other->nextSpan(oIndex, 1);
1020     bool oAligned = false;
1021     if (oSpan->fPt != thisPt) {
1022         oAligned |= other->alignSpan(oStart, oT, thisPt);
1023     }
1024     while (++otherIndex < oEnd) {
1025         SkOpSpan* oNextSpan = &other->fTs[otherIndex];
1026         if (oNextSpan->fT != oT || oNextSpan->fPt != thisPt) {
1027             oAligned |= other->alignSpan(otherIndex, oT, thisPt);
1028         }
1029     }
1030     if (oAligned) {
1031         other->alignSpanState(oStart, oEnd);
1032     }
1033     return aligned;
1034 }
1035
1036 void SkOpSegment::alignSpanState(int start, int end) {
1037     SkOpSpan* lastSpan = &fTs[--end];
1038     bool allSmall = lastSpan->fSmall;
1039     bool allTiny = lastSpan->fTiny;
1040     bool allDone = lastSpan->fDone;
1041     SkDEBUGCODE(int winding = lastSpan->fWindValue);
1042     SkDEBUGCODE(int oppWinding = lastSpan->fOppValue);
1043     int index = start;
1044     while (index < end) {
1045         SkOpSpan* span = &fTs[index];
1046         span->fSmall = allSmall;
1047         span->fTiny = allTiny;
1048         if (span->fDone != allDone) {
1049             span->fDone = allDone;
1050             fDoneSpans += allDone ? 1 : -1;
1051         }
1052         SkASSERT(span->fWindValue == winding);
1053         SkASSERT(span->fOppValue == oppWinding);
1054         ++index;
1055     }
1056 }
1057
1058 void SkOpSegment::blindCancel(const SkCoincidence& coincidence, SkOpSegment* other) {
1059     bool binary = fOperand != other->fOperand;
1060     int index = 0;
1061     int last = this->count();
1062     do {
1063         SkOpSpan& span = this->fTs[--last];
1064         if (span.fT != 1 && !span.fSmall) {
1065             break;
1066         }
1067         span.fCoincident = true;
1068     } while (true);
1069     int oIndex = other->count();
1070     do {
1071         SkOpSpan& oSpan = other->fTs[--oIndex];
1072         if (oSpan.fT != 1 && !oSpan.fSmall) {
1073             break;
1074         }
1075         oSpan.fCoincident = true;
1076     } while (true);
1077     do {
1078         SkOpSpan* test = &this->fTs[index];
1079         int baseWind = test->fWindValue;
1080         int baseOpp = test->fOppValue;
1081         int endIndex = index;
1082         while (++endIndex <= last) {
1083             SkOpSpan* endSpan = &this->fTs[endIndex];
1084             SkASSERT(endSpan->fT < 1);
1085             if (endSpan->fWindValue != baseWind || endSpan->fOppValue != baseOpp) {
1086                 break;
1087             }
1088             endSpan->fCoincident = true;
1089         }
1090         SkOpSpan* oTest = &other->fTs[oIndex];
1091         int oBaseWind = oTest->fWindValue;
1092         int oBaseOpp = oTest->fOppValue;
1093         int oStartIndex = oIndex;
1094         while (--oStartIndex >= 0) {
1095             SkOpSpan* oStartSpan = &other->fTs[oStartIndex];
1096             if (oStartSpan->fWindValue != oBaseWind || oStartSpan->fOppValue != oBaseOpp) {
1097                 break;
1098             }
1099             oStartSpan->fCoincident = true;
1100         }
1101         bool decrement = baseWind && oBaseWind;
1102         bool bigger = baseWind >= oBaseWind;
1103         do {
1104             SkASSERT(test->fT < 1);
1105             if (decrement) {
1106                 if (binary && bigger) {
1107                     test->fOppValue--;
1108                 } else {
1109                     decrementSpan(test);
1110                 }
1111             }
1112             test->fCoincident = true;
1113             test = &fTs[++index];
1114         } while (index < endIndex);
1115         do {
1116             SkASSERT(oTest->fT < 1);
1117             if (decrement) {
1118                 if (binary && !bigger) {
1119                     oTest->fOppValue--;
1120                 } else {
1121                     other->decrementSpan(oTest);
1122                 }
1123             }
1124             oTest->fCoincident = true;
1125             oTest = &other->fTs[--oIndex];
1126         } while (oIndex > oStartIndex);
1127     } while (index <= last && oIndex >= 0);
1128     SkASSERT(index > last);
1129     SkASSERT(oIndex < 0);
1130 }
1131
1132 void SkOpSegment::blindCoincident(const SkCoincidence& coincidence, SkOpSegment* other) {
1133     bool binary = fOperand != other->fOperand;
1134     int index = 0;
1135     int last = this->count();
1136     do {
1137         SkOpSpan& span = this->fTs[--last];
1138         if (span.fT != 1 && !span.fSmall) {
1139             break;
1140         }
1141         span.fCoincident = true;
1142     } while (true);
1143     int oIndex = 0;
1144     int oLast = other->count();
1145     do {
1146         SkOpSpan& oSpan = other->fTs[--oLast];
1147         if (oSpan.fT != 1 && !oSpan.fSmall) {
1148             break;
1149         }
1150         oSpan.fCoincident = true;
1151     } while (true);
1152     do {
1153         SkOpSpan* test = &this->fTs[index];
1154         int baseWind = test->fWindValue;
1155         int baseOpp = test->fOppValue;
1156         int endIndex = index;
1157         SkOpSpan* endSpan;
1158         while (++endIndex <= last) {
1159             endSpan = &this->fTs[endIndex];
1160             SkASSERT(endSpan->fT < 1);
1161             if (endSpan->fWindValue != baseWind || endSpan->fOppValue != baseOpp) {
1162                 break;
1163             }
1164             endSpan->fCoincident = true;
1165         }
1166         SkOpSpan* oTest = &other->fTs[oIndex];
1167         int oBaseWind = oTest->fWindValue;
1168         int oBaseOpp = oTest->fOppValue;
1169         int oEndIndex = oIndex;
1170         SkOpSpan* oEndSpan;
1171         while (++oEndIndex <= oLast) {
1172             oEndSpan = &this->fTs[oEndIndex];
1173             SkASSERT(oEndSpan->fT < 1);
1174             if (oEndSpan->fWindValue != oBaseWind || oEndSpan->fOppValue != oBaseOpp) {
1175                 break;
1176             }
1177             oEndSpan->fCoincident = true;
1178         }
1179         // consolidate the winding count even if done
1180         if ((test->fWindValue || test->fOppValue) && (oTest->fWindValue || oTest->fOppValue)) {
1181             if (!binary || test->fWindValue + oTest->fOppValue >= 0) {
1182                 bumpCoincidentBlind(binary, index, endIndex);
1183                 other->bumpCoincidentOBlind(oIndex, oEndIndex);
1184             } else {
1185                 other->bumpCoincidentBlind(binary, oIndex, oEndIndex);
1186                 bumpCoincidentOBlind(index, endIndex);
1187             }
1188         }
1189         index = endIndex;
1190         oIndex = oEndIndex;
1191     } while (index <= last && oIndex <= oLast);
1192     SkASSERT(index > last);
1193     SkASSERT(oIndex > oLast);
1194 }
1195
1196 void SkOpSegment::bumpCoincidentBlind(bool binary, int index, int endIndex) {
1197     const SkOpSpan& oTest = fTs[index];
1198     int oWindValue = oTest.fWindValue;
1199     int oOppValue = oTest.fOppValue;
1200     if (binary) {
1201         SkTSwap<int>(oWindValue, oOppValue);
1202     }
1203     do {
1204         (void) bumpSpan(&fTs[index], oWindValue, oOppValue);
1205     } while (++index < endIndex);
1206 }
1207
1208 void SkOpSegment::bumpCoincidentThis(const SkOpSpan& oTest, bool binary, int* indexPtr,
1209         SkTArray<SkPoint, true>* outsideTs) {
1210     int index = *indexPtr;
1211     int oWindValue = oTest.fWindValue;
1212     int oOppValue = oTest.fOppValue;
1213     if (binary) {
1214         SkTSwap<int>(oWindValue, oOppValue);
1215     }
1216     SkOpSpan* const test = &fTs[index];
1217     SkOpSpan* end = test;
1218     const SkPoint& oStartPt = oTest.fPt;
1219     do {
1220         if (bumpSpan(end, oWindValue, oOppValue)) {
1221             TrackOutside(outsideTs, oStartPt);
1222         }
1223         end = &fTs[++index];
1224     } while ((end->fPt == test->fPt || precisely_equal(end->fT, test->fT)) && end->fT < 1);
1225     *indexPtr = index;
1226 }
1227
1228 void SkOpSegment::bumpCoincidentOBlind(int index, int endIndex) {
1229     do {
1230         zeroSpan(&fTs[index]);
1231     } while (++index < endIndex);
1232 }
1233
1234 // because of the order in which coincidences are resolved, this and other
1235 // may not have the same intermediate points. Compute the corresponding
1236 // intermediate T values (using this as the master, other as the follower)
1237 // and walk other conditionally -- hoping that it catches up in the end
1238 void SkOpSegment::bumpCoincidentOther(const SkOpSpan& test, int* oIndexPtr,
1239         SkTArray<SkPoint, true>* oOutsidePts) {
1240     int oIndex = *oIndexPtr;
1241     SkOpSpan* const oTest = &fTs[oIndex];
1242     SkOpSpan* oEnd = oTest;
1243     const SkPoint& oStartPt = oTest->fPt;
1244     double oStartT = oTest->fT;
1245 #if 0  // FIXME : figure out what disabling this breaks
1246     const SkPoint& startPt = test.fPt;
1247     // this is always true since oEnd == oTest && oStartPt == oTest->fPt -- find proper condition
1248     if (oStartPt == oEnd->fPt || precisely_equal(oStartT, oEnd->fT)) {
1249         TrackOutside(oOutsidePts, startPt);
1250     }
1251 #endif
1252     while (oStartPt == oEnd->fPt || precisely_equal(oStartT, oEnd->fT)) {
1253         zeroSpan(oEnd);
1254         oEnd = &fTs[++oIndex];
1255     }
1256     *oIndexPtr = oIndex;
1257 }
1258
1259 // FIXME: need to test this case:
1260 // contourA has two segments that are coincident
1261 // contourB has two segments that are coincident in the same place
1262 // each ends up with +2/0 pairs for winding count
1263 // since logic below doesn't transfer count (only increments/decrements) can this be
1264 // resolved to +4/0 ?
1265
1266 // set spans from start to end to increment the greater by one and decrement
1267 // the lesser
1268 bool SkOpSegment::addTCoincident(const SkPoint& startPt, const SkPoint& endPt, double endT,
1269         SkOpSegment* other) {
1270     bool binary = fOperand != other->fOperand;
1271     int index = 0;
1272     while (startPt != fTs[index].fPt) {
1273         SkASSERT(index < fTs.count());
1274         ++index;
1275     }
1276     double startT = fTs[index].fT;
1277     while (index > 0 && precisely_equal(fTs[index - 1].fT, startT)) {
1278         --index;
1279     }
1280     int oIndex = 0;
1281     while (startPt != other->fTs[oIndex].fPt) {
1282         SkASSERT(oIndex < other->fTs.count());
1283         ++oIndex;
1284     }
1285     double oStartT = other->fTs[oIndex].fT;
1286     while (oIndex > 0 && precisely_equal(other->fTs[oIndex - 1].fT, oStartT)) {
1287         --oIndex;
1288     }
1289     SkSTArray<kOutsideTrackedTCount, SkPoint, true> outsidePts;
1290     SkSTArray<kOutsideTrackedTCount, SkPoint, true> oOutsidePts;
1291     SkOpSpan* test = &fTs[index];
1292     const SkPoint* testPt = &test->fPt;
1293     double testT = test->fT;
1294     SkOpSpan* oTest = &other->fTs[oIndex];
1295     const SkPoint* oTestPt = &oTest->fPt;
1296     // paths with extreme data will fail this test and eject out of pathops altogether later on
1297     // SkASSERT(AlmostEqualUlps(*testPt, *oTestPt));
1298     do {
1299         SkASSERT(test->fT < 1);
1300         if (oTest->fT == 1) {
1301             // paths with extreme data may be so mismatched that we fail here
1302             return false;
1303         }
1304
1305         // consolidate the winding count even if done
1306         if ((test->fWindValue == 0 && test->fOppValue == 0)
1307                 || (oTest->fWindValue == 0 && oTest->fOppValue == 0)) {
1308             SkDEBUGCODE(int firstWind = test->fWindValue);
1309             SkDEBUGCODE(int firstOpp = test->fOppValue);
1310             do {
1311                 SkASSERT(firstWind == fTs[index].fWindValue);
1312                 SkASSERT(firstOpp == fTs[index].fOppValue);
1313                 ++index;
1314                 SkASSERT(index < fTs.count());
1315             } while (*testPt == fTs[index].fPt);
1316             SkDEBUGCODE(firstWind = oTest->fWindValue);
1317             SkDEBUGCODE(firstOpp = oTest->fOppValue);
1318             do {
1319                 SkASSERT(firstWind == other->fTs[oIndex].fWindValue);
1320                 SkASSERT(firstOpp == other->fTs[oIndex].fOppValue);
1321                 ++oIndex;
1322                 SkASSERT(oIndex < other->fTs.count());
1323             } while (*oTestPt == other->fTs[oIndex].fPt);
1324         } else {
1325             if (!binary || test->fWindValue + oTest->fOppValue >= 0) {
1326                 bumpCoincidentThis(*oTest, binary, &index, &outsidePts);
1327                 other->bumpCoincidentOther(*test, &oIndex, &oOutsidePts);
1328             } else {
1329                 other->bumpCoincidentThis(*test, binary, &oIndex, &oOutsidePts);
1330                 bumpCoincidentOther(*oTest, &index, &outsidePts);
1331             }
1332         }
1333         test = &fTs[index];
1334         testPt = &test->fPt;
1335         testT = test->fT;
1336         oTest = &other->fTs[oIndex];
1337         oTestPt = &oTest->fPt;
1338         if (endPt == *testPt || precisely_equal(endT, testT)) {
1339             break;
1340         }
1341 //        SkASSERT(AlmostEqualUlps(*testPt, *oTestPt));
1342     } while (endPt != *oTestPt);
1343     // in rare cases, one may have ended before the other
1344     if (endPt != *testPt && !precisely_equal(endT, testT)) {
1345         int lastWind = test[-1].fWindValue;
1346         int lastOpp = test[-1].fOppValue;
1347         bool zero = lastWind == 0 && lastOpp == 0;
1348         do {
1349             if (test->fWindValue || test->fOppValue) {
1350                 test->fWindValue = lastWind;
1351                 test->fOppValue = lastOpp;
1352                 if (zero) {
1353                     test->fDone = true;
1354                     ++fDoneSpans;
1355                 }
1356             }
1357             test = &fTs[++index];
1358             testPt = &test->fPt;
1359         } while (endPt != *testPt);
1360     }
1361     if (endPt != *oTestPt) {
1362         // look ahead to see if zeroing more spans will allows us to catch up
1363         int oPeekIndex = oIndex;
1364         bool success = true;
1365         SkOpSpan* oPeek;
1366         int oCount = other->count();
1367         do {
1368             oPeek = &other->fTs[oPeekIndex];
1369             if (++oPeekIndex == oCount) {
1370                 success = false;
1371                 break;
1372             }
1373         } while (endPt != oPeek->fPt);
1374         if (success) {
1375             // make sure the matching point completes the coincidence span
1376             success = false;
1377             do {
1378                 if (oPeek->fOther == this) {
1379                     success = true;
1380                     break;
1381                 }
1382                 if (++oPeekIndex == oCount) {
1383                     break;
1384                 }
1385                 oPeek = &other->fTs[oPeekIndex];
1386             } while (endPt == oPeek->fPt);
1387         }
1388         if (success) {
1389             do {
1390                 if (!binary || test->fWindValue + oTest->fOppValue >= 0) {
1391                     other->bumpCoincidentOther(*test, &oIndex, &oOutsidePts);
1392                 } else {
1393                     other->bumpCoincidentThis(*test, binary, &oIndex, &oOutsidePts);
1394                 }
1395                 oTest = &other->fTs[oIndex];
1396                 oTestPt = &oTest->fPt;
1397             } while (endPt != *oTestPt);
1398         }
1399     }
1400     int outCount = outsidePts.count();
1401     if (!done() && outCount) {
1402         addCoinOutsides(outsidePts[0], endPt, other);
1403     }
1404     if (!other->done() && oOutsidePts.count()) {
1405         other->addCoinOutsides(oOutsidePts[0], endPt, this);
1406     }
1407     setCoincidentRange(startPt, endPt, other);
1408     other->setCoincidentRange(startPt, endPt, this);
1409     return true;
1410 }
1411
1412 // FIXME: this doesn't prevent the same span from being added twice
1413 // fix in caller, SkASSERT here?
1414 const SkOpSpan* SkOpSegment::addTPair(double t, SkOpSegment* other, double otherT, bool borrowWind,
1415         const SkPoint& pt, const SkPoint& pt2) {
1416     int tCount = fTs.count();
1417     for (int tIndex = 0; tIndex < tCount; ++tIndex) {
1418         const SkOpSpan& span = fTs[tIndex];
1419         if (!approximately_negative(span.fT - t)) {
1420             break;
1421         }
1422         if (approximately_negative(span.fT - t) && span.fOther == other
1423                 && approximately_equal(span.fOtherT, otherT)) {
1424 #if DEBUG_ADD_T_PAIR
1425             SkDebugf("%s addTPair duplicate this=%d %1.9g other=%d %1.9g\n",
1426                     __FUNCTION__, fID, t, other->fID, otherT);
1427 #endif
1428             return NULL;
1429         }
1430     }
1431 #if DEBUG_ADD_T_PAIR
1432     SkDebugf("%s addTPair this=%d %1.9g other=%d %1.9g\n",
1433             __FUNCTION__, fID, t, other->fID, otherT);
1434 #endif
1435     int insertedAt = addT(other, pt, t);
1436     int otherInsertedAt = other->addT(this, pt2, otherT);
1437     addOtherT(insertedAt, otherT, otherInsertedAt);
1438     other->addOtherT(otherInsertedAt, t, insertedAt);
1439     matchWindingValue(insertedAt, t, borrowWind);
1440     other->matchWindingValue(otherInsertedAt, otherT, borrowWind);
1441     SkOpSpan& span = this->fTs[insertedAt];
1442     if (pt != pt2) {
1443         span.fNear = true;
1444         SkOpSpan& oSpan = other->fTs[otherInsertedAt];
1445         oSpan.fNear = true;
1446     }
1447     return &span;
1448 }
1449
1450 const SkOpSpan* SkOpSegment::addTPair(double t, SkOpSegment* other, double otherT, bool borrowWind,
1451                            const SkPoint& pt) {
1452     return addTPair(t, other, otherT, borrowWind, pt, pt);
1453 }
1454
1455 bool SkOpSegment::betweenPoints(double midT, const SkPoint& pt1, const SkPoint& pt2) const {
1456     const SkPoint midPt = ptAtT(midT);
1457     SkPathOpsBounds bounds;
1458     bounds.set(pt1.fX, pt1.fY, pt2.fX, pt2.fY);
1459     bounds.sort();
1460     return bounds.almostContains(midPt);
1461 }
1462
1463 bool SkOpSegment::betweenTs(int lesser, double testT, int greater) const {
1464     if (lesser > greater) {
1465         SkTSwap<int>(lesser, greater);
1466     }
1467     return approximately_between(fTs[lesser].fT, testT, fTs[greater].fT);
1468 }
1469
1470 // in extreme cases (like the buffer overflow test) return false to abort
1471 // for now, if one t value represents two different points, then the values are too extreme
1472 // to generate meaningful results
1473 bool SkOpSegment::calcAngles() {
1474     int spanCount = fTs.count();
1475     if (spanCount <= 2) {
1476         return spanCount == 2;
1477     }
1478     int index = 1;
1479     const SkOpSpan* firstSpan = &fTs[index];
1480     int activePrior = checkSetAngle(0);
1481     const SkOpSpan* span = &fTs[0];
1482     if (firstSpan->fT == 0 || span->fTiny || span->fOtherT != 1 || span->fOther->multipleEnds()) {
1483         index = findStartSpan(0);  // curve start intersects
1484         if (fTs[index].fT == 0) {
1485             return false;
1486         }
1487         SkASSERT(index > 0);
1488         if (activePrior >= 0) {
1489             addStartSpan(index);
1490         }
1491     }
1492     bool addEnd;
1493     int endIndex = spanCount - 1;
1494     span = &fTs[endIndex - 1];
1495     if ((addEnd = span->fT == 1 || span->fTiny)) {  // if curve end intersects
1496         endIndex = findEndSpan(endIndex);
1497         SkASSERT(endIndex > 0);
1498     } else {
1499         addEnd = fTs[endIndex].fOtherT != 0 || fTs[endIndex].fOther->multipleStarts();
1500     }
1501     SkASSERT(endIndex >= index);
1502     int prior = 0;
1503     while (index < endIndex) {
1504         const SkOpSpan& fromSpan = fTs[index];  // for each intermediate intersection
1505         const SkOpSpan* lastSpan;
1506         span = &fromSpan;
1507         int start = index;
1508         do {
1509             lastSpan = span;
1510             span = &fTs[++index];
1511             SkASSERT(index < spanCount);
1512             if (!precisely_negative(span->fT - lastSpan->fT) && !lastSpan->fTiny) {
1513                 break;
1514             }
1515             if (!SkDPoint::ApproximatelyEqual(lastSpan->fPt, span->fPt)) {
1516                 return false;
1517             }
1518         } while (true);
1519         SkOpAngle* angle = NULL;
1520         SkOpAngle* priorAngle;
1521         if (activePrior >= 0) {
1522             int pActive = firstActive(prior);
1523             SkASSERT(pActive < start);
1524             priorAngle = &fAngles.push_back();
1525             priorAngle->set(this, start, pActive);
1526         }
1527         int active = checkSetAngle(start);
1528         if (active >= 0) {
1529             SkASSERT(active < index);
1530             angle = &fAngles.push_back();
1531             angle->set(this, active, index);
1532         }
1533     #if DEBUG_ANGLE
1534         debugCheckPointsEqualish(start, index);
1535     #endif
1536         prior = start;
1537         do {
1538             const SkOpSpan* startSpan = &fTs[start - 1];
1539             if (!startSpan->fSmall || isCanceled(start - 1) || startSpan->fFromAngle
1540                     || startSpan->fToAngle) {
1541                 break;
1542             }
1543             --start;
1544         } while (start > 0);
1545         do {
1546             if (activePrior >= 0) {
1547                 SkASSERT(fTs[start].fFromAngle == NULL);
1548                 fTs[start].fFromAngle = priorAngle;
1549             }
1550             if (active >= 0) {
1551                 SkASSERT(fTs[start].fToAngle == NULL);
1552                 fTs[start].fToAngle = angle;
1553             }
1554         } while (++start < index);
1555         activePrior = active;
1556     }
1557     if (addEnd && activePrior >= 0) {
1558         addEndSpan(endIndex);
1559     }
1560     return true;
1561 }
1562
1563 int SkOpSegment::checkSetAngle(int tIndex) const {
1564     const SkOpSpan* span = &fTs[tIndex];
1565     while (span->fTiny /* || span->fSmall */) {
1566         span = &fTs[++tIndex];
1567     }
1568     return isCanceled(tIndex) ? -1 : tIndex;
1569 }
1570
1571 // at this point, the span is already ordered, or unorderable
1572 int SkOpSegment::computeSum(int startIndex, int endIndex, SkOpAngle::IncludeType includeType) {
1573     SkASSERT(includeType != SkOpAngle::kUnaryXor);
1574     SkOpAngle* firstAngle = spanToAngle(endIndex, startIndex);
1575     if (NULL == firstAngle) {
1576         return SK_NaN32;
1577     }
1578     // if all angles have a computed winding,
1579     //  or if no adjacent angles are orderable,
1580     //  or if adjacent orderable angles have no computed winding,
1581     //  there's nothing to do
1582     // if two orderable angles are adjacent, and both are next to orderable angles,
1583     //  and one has winding computed, transfer to the other
1584     SkOpAngle* baseAngle = NULL;
1585     bool tryReverse = false;
1586     // look for counterclockwise transfers
1587     SkOpAngle* angle = firstAngle->previous();
1588     SkOpAngle* next = angle->next();
1589     firstAngle = next;
1590     do {
1591         SkOpAngle* prior = angle;
1592         angle = next;
1593         next = angle->next();
1594         SkASSERT(prior->next() == angle);
1595         SkASSERT(angle->next() == next);
1596         if (prior->unorderable() || angle->unorderable() || next->unorderable()) {
1597             baseAngle = NULL;
1598             continue;
1599         }
1600         int testWinding = angle->segment()->windSum(angle);
1601         if (SK_MinS32 != testWinding) {
1602             baseAngle = angle;
1603             tryReverse = true;
1604             continue;
1605         }
1606         if (baseAngle) {
1607             ComputeOneSum(baseAngle, angle, includeType);
1608             baseAngle = SK_MinS32 != angle->segment()->windSum(angle) ? angle : NULL;
1609         }
1610     } while (next != firstAngle);
1611     if (baseAngle && SK_MinS32 == firstAngle->segment()->windSum(firstAngle)) {
1612         firstAngle = baseAngle;
1613         tryReverse = true;
1614     }
1615     if (tryReverse) {
1616         baseAngle = NULL;
1617         SkOpAngle* prior = firstAngle;
1618         do {
1619             angle = prior;
1620             prior = angle->previous();
1621             SkASSERT(prior->next() == angle);
1622             next = angle->next();
1623             if (prior->unorderable() || angle->unorderable() || next->unorderable()) {
1624                 baseAngle = NULL;
1625                 continue;
1626             }
1627             int testWinding = angle->segment()->windSum(angle);
1628             if (SK_MinS32 != testWinding) {
1629                 baseAngle = angle;
1630                 continue;
1631             }
1632             if (baseAngle) {
1633                 ComputeOneSumReverse(baseAngle, angle, includeType);
1634                 baseAngle = SK_MinS32 != angle->segment()->windSum(angle) ? angle : NULL;
1635             }
1636         } while (prior != firstAngle);
1637     }
1638     int minIndex = SkMin32(startIndex, endIndex);
1639     return windSum(minIndex);
1640 }
1641
1642 void SkOpSegment::ComputeOneSum(const SkOpAngle* baseAngle, SkOpAngle* nextAngle,
1643         SkOpAngle::IncludeType includeType) {
1644     const SkOpSegment* baseSegment = baseAngle->segment();
1645     int sumMiWinding = baseSegment->updateWindingReverse(baseAngle);
1646     int sumSuWinding;
1647     bool binary = includeType >= SkOpAngle::kBinarySingle;
1648     if (binary) {
1649         sumSuWinding = baseSegment->updateOppWindingReverse(baseAngle);
1650         if (baseSegment->operand()) {
1651             SkTSwap<int>(sumMiWinding, sumSuWinding);
1652         }
1653     }
1654     SkOpSegment* nextSegment = nextAngle->segment();
1655     int maxWinding, sumWinding;
1656     SkOpSpan* last;
1657     if (binary) {
1658         int oppMaxWinding, oppSumWinding;
1659         nextSegment->setUpWindings(nextAngle->start(), nextAngle->end(), &sumMiWinding,
1660                 &sumSuWinding, &maxWinding, &sumWinding, &oppMaxWinding, &oppSumWinding);
1661         last = nextSegment->markAngle(maxWinding, sumWinding, oppMaxWinding, oppSumWinding,
1662                 nextAngle);
1663     } else {
1664         nextSegment->setUpWindings(nextAngle->start(), nextAngle->end(), &sumMiWinding,
1665                 &maxWinding, &sumWinding);
1666         last = nextSegment->markAngle(maxWinding, sumWinding, nextAngle);
1667     }
1668     nextAngle->setLastMarked(last);
1669 }
1670
1671 void SkOpSegment::ComputeOneSumReverse(const SkOpAngle* baseAngle, SkOpAngle* nextAngle,
1672         SkOpAngle::IncludeType includeType) {
1673     const SkOpSegment* baseSegment = baseAngle->segment();
1674     int sumMiWinding = baseSegment->updateWinding(baseAngle);
1675     int sumSuWinding;
1676     bool binary = includeType >= SkOpAngle::kBinarySingle;
1677     if (binary) {
1678         sumSuWinding = baseSegment->updateOppWinding(baseAngle);
1679         if (baseSegment->operand()) {
1680             SkTSwap<int>(sumMiWinding, sumSuWinding);
1681         }
1682     }
1683     SkOpSegment* nextSegment = nextAngle->segment();
1684     int maxWinding, sumWinding;
1685     SkOpSpan* last;
1686     if (binary) {
1687         int oppMaxWinding, oppSumWinding;
1688         nextSegment->setUpWindings(nextAngle->end(), nextAngle->start(), &sumMiWinding,
1689                 &sumSuWinding, &maxWinding, &sumWinding, &oppMaxWinding, &oppSumWinding);
1690         last = nextSegment->markAngle(maxWinding, sumWinding, oppMaxWinding, oppSumWinding,
1691                 nextAngle);
1692     } else {
1693         nextSegment->setUpWindings(nextAngle->end(), nextAngle->start(), &sumMiWinding,
1694                 &maxWinding, &sumWinding);
1695         last = nextSegment->markAngle(maxWinding, sumWinding, nextAngle);
1696     }
1697     nextAngle->setLastMarked(last);
1698 }
1699
1700 bool SkOpSegment::containsPt(const SkPoint& pt, int index, int endIndex) const {
1701     int step = index < endIndex ? 1 : -1;
1702     do {
1703         const SkOpSpan& span = this->span(index);
1704         if (span.fPt == pt) {
1705             const SkOpSpan& endSpan = this->span(endIndex);
1706             return span.fT == endSpan.fT && pt != endSpan.fPt;
1707         }
1708         index += step;
1709     } while (index != endIndex);
1710     return false;
1711 }
1712
1713 bool SkOpSegment::containsT(double t, const SkOpSegment* other, double otherT) const {
1714     int count = this->count();
1715     for (int index = 0; index < count; ++index) {
1716         const SkOpSpan& span = fTs[index];
1717         if (t < span.fT) {
1718             return false;
1719         }
1720         if (t == span.fT) {
1721             if (other != span.fOther) {
1722                 continue;
1723             }
1724             if (other->fVerb != SkPath::kCubic_Verb) {
1725                 return true;
1726             }
1727             if (!other->fLoop) {
1728                 return true;
1729             }
1730             double otherMidT = (otherT + span.fOtherT) / 2;
1731             SkPoint otherPt = other->ptAtT(otherMidT);
1732             return SkDPoint::ApproximatelyEqual(span.fPt, otherPt);
1733         }
1734     }
1735     return false;
1736 }
1737
1738 int SkOpSegment::crossedSpanY(const SkPoint& basePt, SkScalar* bestY, double* hitT,
1739                               bool* hitSomething, double mid, bool opp, bool current) const {
1740     SkScalar bottom = fBounds.fBottom;
1741     int bestTIndex = -1;
1742     if (bottom <= *bestY) {
1743         return bestTIndex;
1744     }
1745     SkScalar top = fBounds.fTop;
1746     if (top >= basePt.fY) {
1747         return bestTIndex;
1748     }
1749     if (fBounds.fLeft > basePt.fX) {
1750         return bestTIndex;
1751     }
1752     if (fBounds.fRight < basePt.fX) {
1753         return bestTIndex;
1754     }
1755     if (fBounds.fLeft == fBounds.fRight) {
1756         // if vertical, and directly above test point, wait for another one
1757         return AlmostEqualUlps(basePt.fX, fBounds.fLeft) ? SK_MinS32 : bestTIndex;
1758     }
1759     // intersect ray starting at basePt with edge
1760     SkIntersections intersections;
1761     // OPTIMIZE: use specialty function that intersects ray with curve,
1762     // returning t values only for curve (we don't care about t on ray)
1763     intersections.allowNear(false);
1764     int pts = (intersections.*CurveVertical[SkPathOpsVerbToPoints(fVerb)])
1765             (fPts, top, bottom, basePt.fX, false);
1766     if (pts == 0 || (current && pts == 1)) {
1767         return bestTIndex;
1768     }
1769     if (current) {
1770         SkASSERT(pts > 1);
1771         int closestIdx = 0;
1772         double closest = fabs(intersections[0][0] - mid);
1773         for (int idx = 1; idx < pts; ++idx) {
1774             double test = fabs(intersections[0][idx] - mid);
1775             if (closest > test) {
1776                 closestIdx = idx;
1777                 closest = test;
1778             }
1779         }
1780         intersections.quickRemoveOne(closestIdx, --pts);
1781     }
1782     double bestT = -1;
1783     for (int index = 0; index < pts; ++index) {
1784         double foundT = intersections[0][index];
1785         if (approximately_less_than_zero(foundT)
1786                     || approximately_greater_than_one(foundT)) {
1787             continue;
1788         }
1789         SkScalar testY = (*CurvePointAtT[SkPathOpsVerbToPoints(fVerb)])(fPts, foundT).fY;
1790         if (approximately_negative(testY - *bestY)
1791                 || approximately_negative(basePt.fY - testY)) {
1792             continue;
1793         }
1794         if (pts > 1 && fVerb == SkPath::kLine_Verb) {
1795             return SK_MinS32;  // if the intersection is edge on, wait for another one
1796         }
1797         if (fVerb > SkPath::kLine_Verb) {
1798             SkScalar dx = (*CurveSlopeAtT[SkPathOpsVerbToPoints(fVerb)])(fPts, foundT).fX;
1799             if (approximately_zero(dx)) {
1800                 return SK_MinS32;  // hit vertical, wait for another one
1801             }
1802         }
1803         *bestY = testY;
1804         bestT = foundT;
1805     }
1806     if (bestT < 0) {
1807         return bestTIndex;
1808     }
1809     SkASSERT(bestT >= 0);
1810     SkASSERT(bestT <= 1);
1811     int start;
1812     int end = 0;
1813     do {
1814         start = end;
1815         end = nextSpan(start, 1);
1816     } while (fTs[end].fT < bestT);
1817     // FIXME: see next candidate for a better pattern to find the next start/end pair
1818     while (start + 1 < end && fTs[start].fDone) {
1819         ++start;
1820     }
1821     if (!isCanceled(start)) {
1822         *hitT = bestT;
1823         bestTIndex = start;
1824         *hitSomething = true;
1825     }
1826     return bestTIndex;
1827 }
1828
1829 bool SkOpSegment::decrementSpan(SkOpSpan* span) {
1830     SkASSERT(span->fWindValue > 0);
1831     if (--(span->fWindValue) == 0) {
1832         if (!span->fOppValue && !span->fDone) {
1833             span->fDone = true;
1834             ++fDoneSpans;
1835             return true;
1836         }
1837     }
1838     return false;
1839 }
1840
1841 bool SkOpSegment::bumpSpan(SkOpSpan* span, int windDelta, int oppDelta) {
1842     SkASSERT(!span->fDone || span->fTiny || span->fSmall);
1843     span->fWindValue += windDelta;
1844     SkASSERT(span->fWindValue >= 0);
1845     span->fOppValue += oppDelta;
1846     SkASSERT(span->fOppValue >= 0);
1847     if (fXor) {
1848         span->fWindValue &= 1;
1849     }
1850     if (fOppXor) {
1851         span->fOppValue &= 1;
1852     }
1853     if (!span->fWindValue && !span->fOppValue) {
1854         span->fDone = true;
1855         ++fDoneSpans;
1856         return true;
1857     }
1858     return false;
1859 }
1860
1861 const SkOpSpan& SkOpSegment::firstSpan(const SkOpSpan& thisSpan) const {
1862     const SkOpSpan* firstSpan = &thisSpan; // rewind to the start
1863     const SkOpSpan* beginSpan = fTs.begin();
1864     const SkPoint& testPt = thisSpan.fPt;
1865     while (firstSpan > beginSpan && firstSpan[-1].fPt == testPt) {
1866         --firstSpan;
1867     }
1868     return *firstSpan;
1869 }
1870
1871 const SkOpSpan& SkOpSegment::lastSpan(const SkOpSpan& thisSpan) const {
1872     const SkOpSpan* endSpan = fTs.end() - 1;  // last can't be small
1873     const SkOpSpan* lastSpan = &thisSpan;  // find the end
1874     const SkPoint& testPt = thisSpan.fPt;
1875     while (lastSpan < endSpan && lastSpan[1].fPt == testPt) {
1876         ++lastSpan;
1877     }
1878     return *lastSpan;
1879 }
1880
1881 // with a loop, the comparison is move involved
1882 // scan backwards and forwards to count all matching points
1883 // (verify that there are twp scans marked as loops)
1884 // compare that against 2 matching scans for loop plus other results
1885 bool SkOpSegment::calcLoopSpanCount(const SkOpSpan& thisSpan, int* smallCounts) {
1886     const SkOpSpan& firstSpan = this->firstSpan(thisSpan); // rewind to the start
1887     const SkOpSpan& lastSpan = this->lastSpan(thisSpan);  // find the end
1888     double firstLoopT = -1, lastLoopT = -1;
1889     const SkOpSpan* testSpan = &firstSpan - 1;
1890     while (++testSpan <= &lastSpan) {
1891         if (testSpan->fLoop) {
1892             firstLoopT = testSpan->fT;
1893             break;
1894         }
1895     }
1896     testSpan = &lastSpan + 1;
1897     while (--testSpan >= &firstSpan) {
1898         if (testSpan->fLoop) {
1899             lastLoopT = testSpan->fT;
1900             break;
1901         }
1902     }
1903     SkASSERT((firstLoopT == -1) == (lastLoopT == -1));
1904     if (firstLoopT == -1) {
1905         return false;
1906     }
1907     SkASSERT(firstLoopT < lastLoopT);
1908     testSpan = &firstSpan - 1;
1909     smallCounts[0] = smallCounts[1] = 0;
1910     while (++testSpan <= &lastSpan) {
1911         SkASSERT(approximately_equal(testSpan->fT, firstLoopT) +
1912                 approximately_equal(testSpan->fT, lastLoopT) == 1);
1913         smallCounts[approximately_equal(testSpan->fT, lastLoopT)]++;
1914     }
1915     return true;
1916 }
1917
1918 double SkOpSegment::calcMissingTEnd(const SkOpSegment* ref, double loEnd, double min, double max,
1919         double hiEnd, const SkOpSegment* other, int thisStart) {
1920     if (max >= hiEnd) {
1921         return -1;
1922     }
1923     int end = findOtherT(hiEnd, ref);
1924     if (end < 0) {
1925         return -1;
1926     }
1927     double tHi = span(end).fT;
1928     double tLo, refLo;
1929     if (thisStart >= 0) {
1930         tLo = span(thisStart).fT;
1931         refLo = min;
1932     } else {
1933         int start1 = findOtherT(loEnd, ref);
1934         SkASSERT(start1 >= 0);
1935         tLo = span(start1).fT;
1936         refLo = loEnd;
1937     }
1938     double missingT = (max - refLo) / (hiEnd - refLo);
1939     missingT = tLo + missingT * (tHi - tLo);
1940     return missingT;
1941 }
1942
1943 double SkOpSegment::calcMissingTStart(const SkOpSegment* ref, double loEnd, double min, double max,
1944         double hiEnd, const SkOpSegment* other, int thisEnd) {
1945     if (min <= loEnd) {
1946         return -1;
1947     }
1948     int start = findOtherT(loEnd, ref);
1949     if (start < 0) {
1950         return -1;
1951     }
1952     double tLo = span(start).fT;
1953     double tHi, refHi;
1954     if (thisEnd >= 0) {
1955         tHi = span(thisEnd).fT;
1956         refHi = max;
1957     } else {
1958         int end1 = findOtherT(hiEnd, ref);
1959         if (end1 < 0) {
1960             return -1;
1961         }
1962         tHi = span(end1).fT;
1963         refHi = hiEnd;
1964     }
1965     double missingT = (min - loEnd) / (refHi - loEnd);
1966     missingT = tLo + missingT * (tHi - tLo);
1967     return missingT;
1968 }
1969
1970 // see if spans with two or more intersections have the same number on the other end
1971 void SkOpSegment::checkDuplicates() {
1972     debugValidate();
1973     SkSTArray<kMissingSpanCount, MissingSpan, true> missingSpans;
1974     int index;
1975     int endIndex = 0;
1976     bool endFound;
1977     do {
1978         index = endIndex;
1979         endIndex = nextExactSpan(index, 1);
1980         if ((endFound = endIndex < 0)) {
1981             endIndex = count();
1982         }
1983         int dupCount = endIndex - index;
1984         if (dupCount < 2) {
1985             continue;
1986         }
1987         do {
1988             const SkOpSpan* thisSpan = &fTs[index];
1989             if (thisSpan->fNear) {
1990                 continue;
1991             }
1992             SkOpSegment* other = thisSpan->fOther;
1993             int oIndex = thisSpan->fOtherIndex;
1994             int oStart = other->nextExactSpan(oIndex, -1) + 1;
1995             int oEnd = other->nextExactSpan(oIndex, 1);
1996             if (oEnd < 0) {
1997                 oEnd = other->count();
1998             }
1999             int oCount = oEnd - oStart;
2000             // force the other to match its t and this pt if not on an end point
2001             if (oCount != dupCount) {
2002                 MissingSpan& missing = missingSpans.push_back();
2003                 missing.fOther = NULL;
2004                 SkDEBUGCODE(sk_bzero(&missing, sizeof(missing)));
2005                 missing.fPt = thisSpan->fPt;
2006                 const SkOpSpan& oSpan = other->span(oIndex);
2007                 if (oCount > dupCount) {
2008                     missing.fSegment = this;
2009                     missing.fT = thisSpan->fT;
2010                     other->checkLinks(&oSpan, &missingSpans);
2011                 } else {
2012                     missing.fSegment = other;
2013                     missing.fT = oSpan.fT;
2014                     checkLinks(thisSpan, &missingSpans);
2015                 }
2016                 if (!missingSpans.back().fOther) {
2017                     missingSpans.pop_back();
2018                 }
2019             }
2020         } while (++index < endIndex);
2021     } while (!endFound);
2022     int missingCount = missingSpans.count();
2023     if (missingCount == 0) {
2024         return;
2025     }
2026     SkSTArray<kMissingSpanCount, MissingSpan, true> missingCoincidence;
2027     for (index = 0; index < missingCount; ++index)  {
2028         MissingSpan& missing = missingSpans[index];
2029         SkOpSegment* missingOther = missing.fOther;
2030         if (missing.fSegment == missing.fOther) {
2031             continue;
2032         }
2033 #if 0  // FIXME: this eliminates spurious data from skpwww_argus_presse_fr_41 but breaks
2034        // skpwww_fashionscandal_com_94 -- calcAngles complains, but I don't understand why
2035         if (missing.fSegment->containsT(missing.fT, missing.fOther, missing.fOtherT)) {
2036 #if DEBUG_DUPLICATES
2037             SkDebugf("skip 1 id=%d t=%1.9g other=%d otherT=%1.9g\n", missing.fSegment->fID,
2038                     missing.fT, missing.fOther->fID, missing.fOtherT);
2039 #endif
2040             continue;
2041         }
2042         if (missing.fOther->containsT(missing.fOtherT, missing.fSegment, missing.fT)) {
2043 #if DEBUG_DUPLICATES
2044             SkDebugf("skip 2 id=%d t=%1.9g other=%d otherT=%1.9g\n", missing.fOther->fID,
2045                     missing.fOtherT, missing.fSegment->fID, missing.fT);
2046 #endif
2047             continue;
2048         }
2049 #endif
2050         // skip if adding would insert point into an existing coincindent span
2051         if (missing.fSegment->inCoincidentSpan(missing.fT, missingOther)
2052                 && missingOther->inCoincidentSpan(missing.fOtherT, this)) {
2053             continue;
2054         }
2055         // skip if the created coincident spans are small
2056         if (missing.fSegment->coincidentSmall(missing.fPt, missing.fT, missingOther)
2057                 && missingOther->coincidentSmall(missing.fPt, missing.fOtherT, missing.fSegment)) {
2058             continue;
2059         }
2060         const SkOpSpan* added = missing.fSegment->addTPair(missing.fT, missingOther,
2061                 missing.fOtherT, false, missing.fPt);
2062         if (added && added->fSmall) {
2063             missing.fSegment->checkSmallCoincidence(*added, &missingCoincidence);
2064         }
2065     }
2066     for (index = 0; index < missingCount; ++index)  {
2067         MissingSpan& missing = missingSpans[index];
2068         missing.fSegment->fixOtherTIndex();
2069         missing.fOther->fixOtherTIndex();
2070     }
2071     for (index = 0; index < missingCoincidence.count(); ++index) {
2072         MissingSpan& missing = missingCoincidence[index];
2073         missing.fSegment->fixOtherTIndex();
2074     }
2075     debugValidate();
2076 }
2077
2078 // look to see if the curve end intersects an intermediary that intersects the other
2079 void SkOpSegment::checkEnds() {
2080     debugValidate();
2081     SkSTArray<kMissingSpanCount, MissingSpan, true> missingSpans;
2082     int count = fTs.count();
2083     for (int index = 0; index < count; ++index) {
2084         const SkOpSpan& span = fTs[index];
2085         double otherT = span.fOtherT;
2086         if (otherT != 0 && otherT != 1) { // only check ends
2087             continue;
2088         }
2089         const SkOpSegment* other = span.fOther;
2090         // peek start/last describe the range of spans that match the other t of this span
2091         int peekStart = span.fOtherIndex;
2092         while (--peekStart >= 0 && other->fTs[peekStart].fT == otherT)
2093             ;
2094         int otherCount = other->fTs.count();
2095         int peekLast = span.fOtherIndex;
2096         while (++peekLast < otherCount && other->fTs[peekLast].fT == otherT)
2097             ;
2098         if (++peekStart == --peekLast) { // if there isn't a range, there's nothing to do
2099             continue;
2100         }
2101         // t start/last describe the range of spans that match the t of this span
2102         double t = span.fT;
2103         double tBottom = -1;
2104         int tStart = -1;
2105         int tLast = count;
2106         bool lastSmall = false;
2107         double afterT = t;
2108         for (int inner = 0; inner < count; ++inner) {
2109             double innerT = fTs[inner].fT;
2110             if (innerT <= t && innerT > tBottom) {
2111                 if (innerT < t || !lastSmall) {
2112                     tStart = inner - 1;
2113                 }
2114                 tBottom = innerT;
2115             }
2116             if (innerT > afterT) {
2117                 if (t == afterT && lastSmall) {
2118                     afterT = innerT;
2119                 } else {
2120                     tLast = inner;
2121                     break;
2122                 }
2123             }
2124             lastSmall = innerT <= t ? fTs[inner].fSmall : false;
2125         }
2126         for (int peekIndex = peekStart; peekIndex <= peekLast; ++peekIndex) {
2127             if (peekIndex == span.fOtherIndex) {  // skip the other span pointed to by this span
2128                 continue;
2129             }
2130             const SkOpSpan& peekSpan = other->fTs[peekIndex];
2131             SkOpSegment* match = peekSpan.fOther;
2132             if (match->done()) {
2133                 continue;  // if the edge has already been eaten (likely coincidence), ignore it
2134             }
2135             const double matchT = peekSpan.fOtherT;
2136             // see if any of the spans match the other spans
2137             for (int tIndex = tStart + 1; tIndex < tLast; ++tIndex) {
2138                 const SkOpSpan& tSpan = fTs[tIndex];
2139                 if (tSpan.fOther == match) {
2140                     if (tSpan.fOtherT == matchT) {
2141                         goto nextPeekIndex;
2142                     }
2143                     double midT = (tSpan.fOtherT + matchT) / 2;
2144                     if (match->betweenPoints(midT, tSpan.fPt, peekSpan.fPt)) {
2145                         goto nextPeekIndex;
2146                     }
2147                 }
2148             }
2149             if (missingSpans.count() > 0) {
2150                 const MissingSpan& lastMissing = missingSpans.back();
2151                 if (lastMissing.fT == t
2152                         && lastMissing.fOther == match
2153                         && lastMissing.fOtherT == matchT) {
2154                     SkASSERT(lastMissing.fPt == peekSpan.fPt);
2155                     continue;
2156                 }
2157             }
2158 #if DEBUG_CHECK_ENDS
2159             SkDebugf("%s id=%d missing t=%1.9g other=%d otherT=%1.9g pt=(%1.9g,%1.9g)\n",
2160                     __FUNCTION__, fID, t, match->fID, matchT, peekSpan.fPt.fX, peekSpan.fPt.fY);
2161 #endif
2162             // this segment is missing a entry that the other contains
2163             // remember so we can add the missing one and recompute the indices
2164             {
2165                 MissingSpan& missing = missingSpans.push_back();
2166                 SkDEBUGCODE(sk_bzero(&missing, sizeof(missing)));
2167                 missing.fT = t;
2168                 missing.fOther = match;
2169                 missing.fOtherT = matchT;
2170                 missing.fPt = peekSpan.fPt;
2171             }
2172             break;
2173 nextPeekIndex:
2174             ;
2175         }
2176     }
2177     if (missingSpans.count() == 0) {
2178         debugValidate();
2179         return;
2180     }
2181     debugValidate();
2182     int missingCount = missingSpans.count();
2183     for (int index = 0; index < missingCount; ++index)  {
2184         MissingSpan& missing = missingSpans[index];
2185         if (this != missing.fOther) {
2186             addTPair(missing.fT, missing.fOther, missing.fOtherT, false, missing.fPt);
2187         }
2188     }
2189     fixOtherTIndex();
2190     // OPTIMIZATION: this may fix indices more than once. Build an array of unique segments to
2191     // avoid this
2192     for (int index = 0; index < missingCount; ++index)  {
2193         missingSpans[index].fOther->fixOtherTIndex();
2194     }
2195     debugValidate();
2196 }
2197
2198 void SkOpSegment::checkLinks(const SkOpSpan* base,
2199         SkTArray<MissingSpan, true>* missingSpans) const {
2200     const SkOpSpan* first = fTs.begin();
2201     const SkOpSpan* last = fTs.end() - 1;
2202     SkASSERT(base >= first && last >= base);
2203     const SkOpSegment* other = base->fOther;
2204     const SkOpSpan* oFirst = other->fTs.begin();
2205     const SkOpSpan* oLast = other->fTs.end() - 1;
2206     const SkOpSpan* oSpan = &other->fTs[base->fOtherIndex];
2207     const SkOpSpan* test = base;
2208     const SkOpSpan* missing = NULL;
2209     while (test > first && (--test)->fPt == base->fPt) {
2210         CheckOneLink(test, oSpan, oFirst, oLast, &missing, missingSpans);
2211     }
2212     test = base;
2213     while (test < last && (++test)->fPt == base->fPt) {
2214         CheckOneLink(test, oSpan, oFirst, oLast, &missing, missingSpans);
2215     }
2216 }
2217
2218 // see if spans with two or more intersections all agree on common t and point values
2219 void SkOpSegment::checkMultiples() {
2220     debugValidate();
2221     int index;
2222     int end = 0;
2223     while (fTs[++end].fT == 0)
2224         ;
2225     while (fTs[end].fT < 1) {
2226         int start = index = end;
2227         end = nextExactSpan(index, 1);
2228         if (end <= index) {
2229             return;  // buffer overflow example triggers this
2230         }
2231         if (index + 1 == end) {
2232             continue;
2233         }
2234         // force the duplicates to agree on t and pt if not on the end
2235         SkOpSpan& span = fTs[index];
2236         double thisT = span.fT;
2237         const SkPoint& thisPt = span.fPt;
2238         span.fMultiple = true;
2239         bool aligned = false;
2240         while (++index < end) {
2241             aligned |= alignSpan(index, thisT, thisPt);
2242         }
2243         if (aligned) {
2244             alignSpanState(start, end);
2245         }
2246         fMultiples = true;
2247     }
2248     debugValidate();
2249 }
2250
2251 void SkOpSegment::CheckOneLink(const SkOpSpan* test, const SkOpSpan* oSpan,
2252         const SkOpSpan* oFirst, const SkOpSpan* oLast, const SkOpSpan** missingPtr,
2253         SkTArray<MissingSpan, true>* missingSpans) {
2254     SkASSERT(oSpan->fPt == test->fPt);
2255     const SkOpSpan* oTest = oSpan;
2256     while (oTest > oFirst && (--oTest)->fPt == test->fPt) {
2257         if (oTest->fOther == test->fOther && oTest->fOtherT == test->fOtherT) {
2258             return;
2259         }
2260     }
2261     oTest = oSpan;
2262     while (oTest < oLast && (++oTest)->fPt == test->fPt) {
2263         if (oTest->fOther == test->fOther && oTest->fOtherT == test->fOtherT) {
2264             return;
2265         }
2266     }
2267     if (*missingPtr) {
2268         missingSpans->push_back();
2269     }
2270     MissingSpan& lastMissing = missingSpans->back();
2271     if (*missingPtr) {
2272         lastMissing = missingSpans->end()[-2];
2273     }
2274     *missingPtr = test;
2275     lastMissing.fOther = test->fOther;
2276     lastMissing.fOtherT = test->fOtherT;
2277 }
2278
2279 bool SkOpSegment::checkSmall(int index) const {
2280     if (fTs[index].fSmall) {
2281         return true;
2282     }
2283     double tBase = fTs[index].fT;
2284     while (index > 0 && precisely_negative(tBase - fTs[--index].fT))
2285         ;
2286     return fTs[index].fSmall;
2287 }
2288
2289 // a pair of curves may turn into coincident lines -- small may be a hint that that happened
2290 // if a cubic contains a loop, the counts must be adjusted
2291 void SkOpSegment::checkSmall() {
2292     SkSTArray<kMissingSpanCount, MissingSpan, true> missingSpans;
2293     const SkOpSpan* beginSpan = fTs.begin();
2294     const SkOpSpan* thisSpan = beginSpan - 1;
2295     const SkOpSpan* endSpan = fTs.end() - 1;  // last can't be small
2296     while (++thisSpan < endSpan) {
2297         if (!thisSpan->fSmall) {
2298             continue;
2299         }
2300         if (!thisSpan->fWindValue) {
2301             continue;
2302         }
2303         const SkOpSpan& firstSpan = this->firstSpan(*thisSpan);
2304         const SkOpSpan& lastSpan = this->lastSpan(*thisSpan);
2305         const SkOpSpan* nextSpan = &firstSpan + 1;
2306         ptrdiff_t smallCount = &lastSpan - &firstSpan + 1;
2307         SkASSERT(1 <= smallCount && smallCount < count());
2308         if (smallCount <= 1 && !nextSpan->fSmall) {
2309             SkASSERT(1 == smallCount);
2310             checkSmallCoincidence(firstSpan, NULL);
2311             continue;
2312         }
2313         // at this point, check for missing computed intersections
2314         const SkPoint& testPt = firstSpan.fPt;
2315         thisSpan = &firstSpan - 1;
2316         SkOpSegment* other = NULL;
2317         while (++thisSpan <= &lastSpan) {
2318             other = thisSpan->fOther;
2319             if (other != this) {
2320                 break;
2321             }
2322         }
2323         SkASSERT(other != this);
2324         int oIndex = thisSpan->fOtherIndex;
2325         const SkOpSpan& oSpan = other->span(oIndex);
2326         const SkOpSpan& oFirstSpan = other->firstSpan(oSpan);
2327         const SkOpSpan& oLastSpan = other->lastSpan(oSpan);
2328         ptrdiff_t oCount = &oLastSpan - &oFirstSpan + 1;
2329         if (fLoop) {
2330             int smallCounts[2];
2331             SkASSERT(!other->fLoop);  // FIXME: we need more complicated logic for pair of loops
2332             if (calcLoopSpanCount(*thisSpan, smallCounts)) {
2333                 if (smallCounts[0] && oCount != smallCounts[0]) {
2334                     SkASSERT(0);  // FIXME: need a working test case to properly code & debug
2335                 }
2336                 if (smallCounts[1] && oCount != smallCounts[1]) {
2337                     SkASSERT(0);  // FIXME: need a working test case to properly code & debug
2338                 }
2339                 goto nextSmallCheck;
2340             }
2341         }
2342         if (other->fLoop) {
2343             int otherCounts[2];
2344             if (other->calcLoopSpanCount(other->span(oIndex), otherCounts)) {
2345                 if (otherCounts[0] && otherCounts[0] != smallCount) {
2346                     SkASSERT(0);  // FIXME: need a working test case to properly code & debug
2347                 }
2348                 if (otherCounts[1] && otherCounts[1] != smallCount) {
2349                     SkASSERT(0);  // FIXME: need a working test case to properly code & debug
2350                 }
2351                 goto nextSmallCheck;
2352             }
2353         }
2354         if (oCount != smallCount) {  // check if number of pts in this match other
2355             MissingSpan& missing = missingSpans.push_back();
2356             missing.fOther = NULL;
2357             SkDEBUGCODE(sk_bzero(&missing, sizeof(missing)));
2358             missing.fPt = testPt;
2359             const SkOpSpan& oSpan = other->span(oIndex);
2360             if (oCount > smallCount) {
2361                 missing.fSegment = this;
2362                 missing.fT = thisSpan->fT;
2363                 other->checkLinks(&oSpan, &missingSpans);
2364             } else {
2365                 missing.fSegment = other;
2366                 missing.fT = oSpan.fT;
2367                 checkLinks(thisSpan, &missingSpans);
2368             }
2369             if (!missingSpans.back().fOther || missing.fSegment->done()) {
2370                 missingSpans.pop_back();
2371             }
2372         }
2373 nextSmallCheck:
2374         thisSpan = &lastSpan;
2375     }
2376     int missingCount = missingSpans.count();
2377     for (int index = 0; index < missingCount; ++index)  {
2378         MissingSpan& missing = missingSpans[index];
2379         SkOpSegment* missingOther = missing.fOther;
2380         // note that add t pair may edit span arrays, so prior pointers to spans are no longer valid
2381         if (!missing.fSegment->addTPair(missing.fT, missingOther, missing.fOtherT, false,
2382                 missing.fPt)) {
2383             continue;
2384         }
2385         int otherTIndex = missingOther->findT(missing.fOtherT, missing.fPt, missing.fSegment);
2386         const SkOpSpan& otherSpan = missingOther->span(otherTIndex);
2387         if (otherSpan.fSmall) {
2388             const SkOpSpan* nextSpan = &otherSpan;
2389             do {
2390                 ++nextSpan;
2391             } while (nextSpan->fSmall);
2392             SkAssertResult(missing.fSegment->addTCoincident(missing.fPt, nextSpan->fPt,
2393                     nextSpan->fT, missingOther));
2394         } else if (otherSpan.fT > 0) {
2395             const SkOpSpan* priorSpan = &otherSpan;
2396             do {
2397                 --priorSpan;
2398             } while (priorSpan->fT == otherSpan.fT);
2399             if (priorSpan->fSmall) {
2400                 missing.fSegment->addTCancel(missing.fPt, priorSpan->fPt, missingOther);
2401             }
2402         }
2403     }
2404     // OPTIMIZATION: this may fix indices more than once. Build an array of unique segments to
2405     // avoid this
2406     for (int index = 0; index < missingCount; ++index)  {
2407         MissingSpan& missing = missingSpans[index];
2408         missing.fSegment->fixOtherTIndex();
2409         missing.fOther->fixOtherTIndex();
2410     }
2411     debugValidate();
2412 }
2413
2414 void SkOpSegment::checkSmallCoincidence(const SkOpSpan& span,
2415         SkTArray<MissingSpan, true>* checkMultiple) {
2416     SkASSERT(span.fSmall);
2417     if (0 && !span.fWindValue) {
2418         return;
2419     }
2420     SkASSERT(&span < fTs.end() - 1);
2421     const SkOpSpan* next = &span + 1;
2422     SkASSERT(!next->fSmall || checkMultiple);
2423     if (checkMultiple) {
2424         while (next->fSmall) {
2425             ++next;
2426             SkASSERT(next < fTs.end());
2427         }
2428     }
2429     SkOpSegment* other = span.fOther;
2430     while (other != next->fOther) {
2431         if (!checkMultiple) {
2432             return;
2433         }
2434         const SkOpSpan* test = next + 1;
2435         if (test == fTs.end()) {
2436             return;
2437         }
2438         if (test->fPt != next->fPt || !precisely_equal(test->fT, next->fT)) {
2439             return;
2440         }
2441         next = test;
2442     }
2443     SkASSERT(span.fT < next->fT);
2444     int oStartIndex = other->findExactT(span.fOtherT, this);
2445     int oEndIndex = other->findExactT(next->fOtherT, this);
2446     // FIXME: be overly conservative by limiting this to the caller that allows multiple smalls
2447     if (!checkMultiple || fVerb != SkPath::kLine_Verb || other->fVerb != SkPath::kLine_Verb) {
2448         SkPoint mid = ptAtT((span.fT + next->fT) / 2);
2449         const SkOpSpan& oSpanStart = other->fTs[oStartIndex];
2450         const SkOpSpan& oSpanEnd = other->fTs[oEndIndex];
2451         SkPoint oMid = other->ptAtT((oSpanStart.fT + oSpanEnd.fT) / 2);
2452         if (!SkDPoint::ApproximatelyEqual(mid, oMid)) {
2453             return;
2454         }
2455     }
2456     // FIXME: again, be overly conservative to avoid breaking existing tests
2457     const SkOpSpan& oSpan = oStartIndex < oEndIndex ? other->fTs[oStartIndex]
2458             : other->fTs[oEndIndex];
2459     if (checkMultiple && !oSpan.fSmall) {
2460         return;
2461     }
2462     SkASSERT(oSpan.fSmall);
2463     if (oStartIndex < oEndIndex) {
2464         SkAssertResult(addTCoincident(span.fPt, next->fPt, next->fT, other));
2465     } else {
2466         addTCancel(span.fPt, next->fPt, other);
2467     }
2468     if (!checkMultiple) {
2469         return;
2470     }
2471     // check to see if either segment is coincident with a third segment -- if it is, and if
2472     // the opposite segment is not already coincident with the third, make it so
2473     // OPTIMIZE: to make this check easier, add coincident and cancel could set a coincident bit
2474     if (span.fWindValue != 1 || span.fOppValue != 0) {
2475 //        start here;
2476         // iterate through the spans, looking for the third coincident case
2477         // if we find one, we need to return state to the caller so that the indices can be fixed
2478         // this also suggests that all of this function is fragile since it relies on a valid index
2479     }
2480     // probably should make this a common function rather than copy/paste code
2481     if (oSpan.fWindValue != 1 || oSpan.fOppValue != 0) {
2482         const SkOpSpan* oTest = &oSpan;
2483         while (--oTest >= other->fTs.begin()) {
2484             if (oTest->fPt != oSpan.fPt || !precisely_equal(oTest->fT, oSpan.fT)) {
2485                 break;
2486             }
2487             SkOpSegment* testOther = oTest->fOther;
2488             SkASSERT(testOther != this);
2489             // look in both directions to see if there is a coincident span
2490             const SkOpSpan* tTest = testOther->fTs.begin();
2491             for (int testIndex = 0; testIndex < testOther->count(); ++testIndex) {
2492                 if (tTest->fPt != span.fPt) {
2493                     ++tTest;
2494                     continue;
2495                 }
2496                 if (testOther->verb() != SkPath::kLine_Verb
2497                         || other->verb() != SkPath::kLine_Verb) {
2498                     SkPoint mid = ptAtT((span.fT + next->fT) / 2);
2499                     SkPoint oMid = other->ptAtT((oTest->fOtherT + tTest->fT) / 2);
2500                     if (!SkDPoint::ApproximatelyEqual(mid, oMid)) {
2501                         continue;
2502                     }
2503                 }
2504 #if DEBUG_CONCIDENT
2505                 SkDebugf("%s coincident found=%d %1.9g %1.9g\n", __FUNCTION__, testOther->fID,
2506                         oTest->fOtherT, tTest->fT);
2507 #endif
2508                 if (tTest->fT < oTest->fOtherT) {
2509                     SkAssertResult(addTCoincident(span.fPt, next->fPt, next->fT, testOther));
2510                 } else {
2511                     addTCancel(span.fPt, next->fPt, testOther);
2512                 }
2513                 MissingSpan missing;
2514                 missing.fSegment = testOther;
2515                 checkMultiple->push_back(missing);
2516                 break;
2517             }
2518         }
2519         oTest = &oSpan;
2520         while (++oTest < other->fTs.end()) {
2521             if (oTest->fPt != oSpan.fPt || !precisely_equal(oTest->fT, oSpan.fT)) {
2522                 break;
2523             }
2524
2525         }
2526     }
2527 }
2528
2529 // if pair of spans on either side of tiny have the same end point and mid point, mark
2530 // them as parallel
2531 void SkOpSegment::checkTiny() {
2532     SkSTArray<kMissingSpanCount, MissingSpan, true> missingSpans;
2533     SkOpSpan* thisSpan = fTs.begin() - 1;
2534     const SkOpSpan* endSpan = fTs.end() - 1;  // last can't be tiny
2535     while (++thisSpan < endSpan) {
2536         if (!thisSpan->fTiny) {
2537             continue;
2538         }
2539         SkOpSpan* nextSpan = thisSpan + 1;
2540         double thisT = thisSpan->fT;
2541         double nextT = nextSpan->fT;
2542         if (thisT == nextT) {
2543             continue;
2544         }
2545         SkASSERT(thisT < nextT);
2546         SkASSERT(thisSpan->fPt == nextSpan->fPt);
2547         SkOpSegment* thisOther = thisSpan->fOther;
2548         SkOpSegment* nextOther = nextSpan->fOther;
2549         int oIndex = thisSpan->fOtherIndex;
2550         for (int oStep = -1; oStep <= 1; oStep += 2) {
2551             int oEnd = thisOther->nextExactSpan(oIndex, oStep);
2552             if (oEnd < 0) {
2553                 continue;
2554             }
2555             const SkOpSpan& oSpan = thisOther->span(oEnd);
2556             int nIndex = nextSpan->fOtherIndex;
2557             for (int nStep = -1; nStep <= 1; nStep += 2) {
2558                 int nEnd = nextOther->nextExactSpan(nIndex, nStep);
2559                 if (nEnd < 0) {
2560                     continue;
2561                 }
2562                 const SkOpSpan& nSpan = nextOther->span(nEnd);
2563                 if (oSpan.fPt != nSpan.fPt) {
2564                     continue;
2565                 }
2566                 double oMidT = (thisSpan->fOtherT + oSpan.fT) / 2;
2567                 const SkPoint& oPt = thisOther->ptAtT(oMidT);
2568                 double nMidT = (nextSpan->fOtherT + nSpan.fT) / 2;
2569                 const SkPoint& nPt = nextOther->ptAtT(nMidT);
2570                 if (!AlmostEqualUlps(oPt, nPt)) {
2571                     continue;
2572                 }
2573 #if DEBUG_CHECK_TINY
2574                 SkDebugf("%s [%d] add coincidence [%d] [%d]\n", __FUNCTION__, fID,
2575                     thisOther->fID, nextOther->fID);
2576 #endif
2577                 // this segment is missing a entry that the other contains
2578                 // remember so we can add the missing one and recompute the indices
2579                 MissingSpan& missing = missingSpans.push_back();
2580                 SkDEBUGCODE(sk_bzero(&missing, sizeof(missing)));
2581                 missing.fSegment = thisOther;
2582                 missing.fT = thisSpan->fOtherT;
2583                 missing.fOther = nextOther;
2584                 missing.fOtherT = nextSpan->fOtherT;
2585                 missing.fPt = thisSpan->fPt;
2586             }
2587         }
2588     }
2589     int missingCount = missingSpans.count();
2590     if (!missingCount) {
2591         return;
2592     }
2593     for (int index = 0; index < missingCount; ++index)  {
2594         MissingSpan& missing = missingSpans[index];
2595         if (missing.fSegment != missing.fOther) {
2596             missing.fSegment->addTPair(missing.fT, missing.fOther, missing.fOtherT, false,
2597                     missing.fPt);
2598         }
2599     }
2600     // OPTIMIZE: consolidate to avoid multiple calls to fix index
2601     for (int index = 0; index < missingCount; ++index)  {
2602         MissingSpan& missing = missingSpans[index];
2603         missing.fSegment->fixOtherTIndex();
2604         missing.fOther->fixOtherTIndex();
2605     }
2606 }
2607
2608 bool SkOpSegment::coincidentSmall(const SkPoint& pt, double t, const SkOpSegment* other) const {
2609     int count = this->count();
2610     for (int index = 0; index < count; ++index) {
2611         const SkOpSpan& span = this->span(index);
2612         if (span.fOther != other) {
2613             continue;
2614         }
2615         if (span.fPt == pt) {
2616             continue;
2617         }
2618         if (!AlmostEqualUlps(span.fPt, pt)) {
2619             continue;
2620         }
2621         if (fVerb != SkPath::kCubic_Verb) {
2622             return true;
2623         }
2624         double tInterval = t - span.fT;
2625         double tMid = t - tInterval / 2;
2626         SkDPoint midPt = dcubic_xy_at_t(fPts, tMid);
2627         return midPt.approximatelyEqual(xyAtT(t));
2628     }
2629     return false;
2630 }
2631
2632 bool SkOpSegment::findCoincidentMatch(const SkOpSpan* span, const SkOpSegment* other, int oStart,
2633         int oEnd, int step, SkPoint* startPt, SkPoint* endPt, double* endT) const {
2634     SkASSERT(span->fT == 0 || span->fT == 1);
2635     SkASSERT(span->fOtherT == 0 || span->fOtherT == 1);
2636     const SkOpSpan* otherSpan = &other->span(oEnd);
2637     double refT = otherSpan->fT;
2638     const SkPoint& refPt = otherSpan->fPt;
2639     const SkOpSpan* lastSpan = &other->span(step > 0 ? other->count() - 1 : 0);
2640     do {
2641         const SkOpSegment* match = span->fOther;
2642         if (match == otherSpan->fOther) {
2643             // find start of respective spans and see if both have winding
2644             int startIndex, endIndex;
2645             if (span->fOtherT == 1) {
2646                 endIndex = span->fOtherIndex;
2647                 startIndex = match->nextExactSpan(endIndex, -1);
2648             } else {
2649                 startIndex = span->fOtherIndex;
2650                 endIndex = match->nextExactSpan(startIndex, 1);
2651             }
2652             const SkOpSpan& startSpan = match->span(startIndex);
2653             if (startSpan.fWindValue != 0) {
2654                 // draw ray from endSpan.fPt perpendicular to end tangent and measure distance
2655                 // to other segment.
2656                 const SkOpSpan& endSpan = match->span(endIndex);
2657                 SkDLine ray;
2658                 SkVector dxdy;
2659                 if (span->fOtherT == 1) {
2660                     ray.fPts[0].set(startSpan.fPt);
2661                     dxdy = match->dxdy(startIndex);
2662                 } else {
2663                     ray.fPts[0].set(endSpan.fPt);
2664                     dxdy = match->dxdy(endIndex);
2665                 }
2666                 ray.fPts[1].fX = ray.fPts[0].fX + dxdy.fY;
2667                 ray.fPts[1].fY = ray.fPts[0].fY - dxdy.fX;
2668                 SkIntersections i;
2669                 int roots = (i.*CurveRay[SkPathOpsVerbToPoints(other->verb())])(other->pts(), ray);
2670                 for (int index = 0; index < roots; ++index) {
2671                     if (ray.fPts[0].approximatelyEqual(i.pt(index))) {
2672                         double matchMidT = (match->span(startIndex).fT
2673                                 + match->span(endIndex).fT) / 2;
2674                         SkPoint matchMidPt = match->ptAtT(matchMidT);
2675                         double otherMidT = (i[0][index] + other->span(oStart).fT) / 2;
2676                         SkPoint otherMidPt = other->ptAtT(otherMidT);
2677                         if (SkDPoint::ApproximatelyEqual(matchMidPt, otherMidPt)) {
2678                             *startPt = startSpan.fPt;
2679                             *endPt = endSpan.fPt;
2680                             *endT = endSpan.fT;
2681                             return true;
2682                         }
2683                     }
2684                 }
2685             }
2686             return false;
2687         }
2688         if (otherSpan == lastSpan) {
2689             break;
2690         }
2691         otherSpan += step;
2692     } while (otherSpan->fT == refT || otherSpan->fPt == refPt);
2693     return false;
2694 }
2695
2696 int SkOpSegment::findEndSpan(int endIndex) const {
2697     const SkOpSpan* span = &fTs[--endIndex];
2698     const SkPoint& lastPt = span->fPt;
2699     double endT = span->fT;
2700     do {
2701         span = &fTs[--endIndex];
2702     } while (SkDPoint::ApproximatelyEqual(span->fPt, lastPt) && (span->fT == endT || span->fTiny));
2703     return endIndex + 1;
2704 }
2705
2706 /*
2707  The M and S variable name parts stand for the operators.
2708    Mi stands for Minuend (see wiki subtraction, analogous to difference)
2709    Su stands for Subtrahend
2710  The Opp variable name part designates that the value is for the Opposite operator.
2711  Opposite values result from combining coincident spans.
2712  */
2713 SkOpSegment* SkOpSegment::findNextOp(SkTDArray<SkOpSpan*>* chase, int* nextStart, int* nextEnd,
2714                                      bool* unsortable, SkPathOp op, const int xorMiMask,
2715                                      const int xorSuMask) {
2716     const int startIndex = *nextStart;
2717     const int endIndex = *nextEnd;
2718     SkASSERT(startIndex != endIndex);
2719     SkDEBUGCODE(const int count = fTs.count());
2720     SkASSERT(startIndex < endIndex ? startIndex < count - 1 : startIndex > 0);
2721     int step = SkSign32(endIndex - startIndex);
2722     *nextStart = startIndex;
2723     SkOpSegment* other = isSimple(nextStart, &step);
2724     if (other)
2725     {
2726     // mark the smaller of startIndex, endIndex done, and all adjacent
2727     // spans with the same T value (but not 'other' spans)
2728 #if DEBUG_WINDING
2729         SkDebugf("%s simple\n", __FUNCTION__);
2730 #endif
2731         int min = SkMin32(startIndex, endIndex);
2732         if (fTs[min].fDone) {
2733             return NULL;
2734         }
2735         markDoneBinary(min);
2736         double startT = other->fTs[*nextStart].fT;
2737         *nextEnd = *nextStart;
2738         do {
2739             *nextEnd += step;
2740         } while (precisely_zero(startT - other->fTs[*nextEnd].fT));
2741         SkASSERT(step < 0 ? *nextEnd >= 0 : *nextEnd < other->fTs.count());
2742         if (other->isTiny(SkMin32(*nextStart, *nextEnd))) {
2743             *unsortable = true;
2744             return NULL;
2745         }
2746         return other;
2747     }
2748     const int end = nextExactSpan(startIndex, step);
2749     SkASSERT(end >= 0);
2750     SkASSERT(startIndex - endIndex != 0);
2751     SkASSERT((startIndex - endIndex < 0) ^ (step < 0));
2752     // more than one viable candidate -- measure angles to find best
2753
2754     int calcWinding = computeSum(startIndex, end, SkOpAngle::kBinaryOpp);
2755     bool sortable = calcWinding != SK_NaN32;
2756     if (!sortable) {
2757         *unsortable = true;
2758         markDoneBinary(SkMin32(startIndex, endIndex));
2759         return NULL;
2760     }
2761     SkOpAngle* angle = spanToAngle(end, startIndex);
2762     if (angle->unorderable()) {
2763         *unsortable = true;
2764         markDoneBinary(SkMin32(startIndex, endIndex));
2765         return NULL;
2766     }
2767 #if DEBUG_SORT
2768     SkDebugf("%s\n", __FUNCTION__);
2769     angle->debugLoop();
2770 #endif
2771     int sumMiWinding = updateWinding(endIndex, startIndex);
2772     if (sumMiWinding == SK_MinS32) {
2773         *unsortable = true;
2774         markDoneBinary(SkMin32(startIndex, endIndex));
2775         return NULL;
2776     }
2777     int sumSuWinding = updateOppWinding(endIndex, startIndex);
2778     if (operand()) {
2779         SkTSwap<int>(sumMiWinding, sumSuWinding);
2780     }
2781     SkOpAngle* nextAngle = angle->next();
2782     const SkOpAngle* foundAngle = NULL;
2783     bool foundDone = false;
2784     // iterate through the angle, and compute everyone's winding
2785     SkOpSegment* nextSegment;
2786     int activeCount = 0;
2787     do {
2788         nextSegment = nextAngle->segment();
2789         bool activeAngle = nextSegment->activeOp(xorMiMask, xorSuMask, nextAngle->start(),
2790                 nextAngle->end(), op, &sumMiWinding, &sumSuWinding);
2791         if (activeAngle) {
2792             ++activeCount;
2793             if (!foundAngle || (foundDone && activeCount & 1)) {
2794                 if (nextSegment->isTiny(nextAngle)) {
2795                     *unsortable = true;
2796                     markDoneBinary(SkMin32(startIndex, endIndex));
2797                     return NULL;
2798                 }
2799                 foundAngle = nextAngle;
2800                 foundDone = nextSegment->done(nextAngle);
2801             }
2802         }
2803         if (nextSegment->done()) {
2804             continue;
2805         }
2806         if (nextSegment->isTiny(nextAngle)) {
2807             continue;
2808         }
2809         if (!activeAngle) {
2810             (void) nextSegment->markAndChaseDoneBinary(nextAngle->start(), nextAngle->end());
2811         }
2812         SkOpSpan* last = nextAngle->lastMarked();
2813         if (last) {
2814             SkASSERT(!SkPathOpsDebug::ChaseContains(*chase, last));
2815             *chase->append() = last;
2816 #if DEBUG_WINDING
2817             SkDebugf("%s chase.append id=%d windSum=%d small=%d\n", __FUNCTION__,
2818                     last->fOther->fTs[last->fOtherIndex].fOther->debugID(), last->fWindSum,
2819                     last->fSmall);
2820 #endif
2821         }
2822     } while ((nextAngle = nextAngle->next()) != angle);
2823 #if DEBUG_ANGLE
2824     if (foundAngle) {
2825         foundAngle->debugSameAs(foundAngle);
2826     }
2827 #endif
2828
2829     markDoneBinary(SkMin32(startIndex, endIndex));
2830     if (!foundAngle) {
2831         return NULL;
2832     }
2833     *nextStart = foundAngle->start();
2834     *nextEnd = foundAngle->end();
2835     nextSegment = foundAngle->segment();
2836 #if DEBUG_WINDING
2837     SkDebugf("%s from:[%d] to:[%d] start=%d end=%d\n",
2838             __FUNCTION__, debugID(), nextSegment->debugID(), *nextStart, *nextEnd);
2839  #endif
2840     return nextSegment;
2841 }
2842
2843 SkOpSegment* SkOpSegment::findNextWinding(SkTDArray<SkOpSpan*>* chase, int* nextStart,
2844                                           int* nextEnd, bool* unsortable) {
2845     const int startIndex = *nextStart;
2846     const int endIndex = *nextEnd;
2847     SkASSERT(startIndex != endIndex);
2848     SkDEBUGCODE(const int count = fTs.count());
2849     SkASSERT(startIndex < endIndex ? startIndex < count - 1 : startIndex > 0);
2850     int step = SkSign32(endIndex - startIndex);
2851     *nextStart = startIndex;
2852     SkOpSegment* other = isSimple(nextStart, &step);
2853     if (other)
2854     {
2855     // mark the smaller of startIndex, endIndex done, and all adjacent
2856     // spans with the same T value (but not 'other' spans)
2857 #if DEBUG_WINDING
2858         SkDebugf("%s simple\n", __FUNCTION__);
2859 #endif
2860         int min = SkMin32(startIndex, endIndex);
2861         if (fTs[min].fDone) {
2862             return NULL;
2863         }
2864         markDoneUnary(min);
2865         double startT = other->fTs[*nextStart].fT;
2866         *nextEnd = *nextStart;
2867         do {
2868             *nextEnd += step;
2869         } while (precisely_zero(startT - other->fTs[*nextEnd].fT));
2870         SkASSERT(step < 0 ? *nextEnd >= 0 : *nextEnd < other->fTs.count());
2871         if (other->isTiny(SkMin32(*nextStart, *nextEnd))) {
2872             *unsortable = true;
2873             return NULL;
2874         }
2875         return other;
2876     }
2877     const int end = nextExactSpan(startIndex, step);
2878     SkASSERT(end >= 0);
2879     SkASSERT(startIndex - endIndex != 0);
2880     SkASSERT((startIndex - endIndex < 0) ^ (step < 0));
2881     // more than one viable candidate -- measure angles to find best
2882
2883     int calcWinding = computeSum(startIndex, end, SkOpAngle::kUnaryWinding);
2884     bool sortable = calcWinding != SK_NaN32;
2885     if (!sortable) {
2886         *unsortable = true;
2887         markDoneUnary(SkMin32(startIndex, endIndex));
2888         return NULL;
2889     }
2890     SkOpAngle* angle = spanToAngle(end, startIndex);
2891 #if DEBUG_SORT
2892     SkDebugf("%s\n", __FUNCTION__);
2893     angle->debugLoop();
2894 #endif
2895     int sumWinding = updateWinding(endIndex, startIndex);
2896     SkOpAngle* nextAngle = angle->next();
2897     const SkOpAngle* foundAngle = NULL;
2898     bool foundDone = false;
2899     SkOpSegment* nextSegment;
2900     int activeCount = 0;
2901     do {
2902         nextSegment = nextAngle->segment();
2903         bool activeAngle = nextSegment->activeWinding(nextAngle->start(), nextAngle->end(),
2904                 &sumWinding);
2905         if (activeAngle) {
2906             ++activeCount;
2907             if (!foundAngle || (foundDone && activeCount & 1)) {
2908                 if (nextSegment->isTiny(nextAngle)) {
2909                     *unsortable = true;
2910                     markDoneUnary(SkMin32(startIndex, endIndex));
2911                     return NULL;
2912                 }
2913                 foundAngle = nextAngle;
2914                 foundDone = nextSegment->done(nextAngle);
2915             }
2916         }
2917         if (nextSegment->done()) {
2918             continue;
2919         }
2920         if (nextSegment->isTiny(nextAngle)) {
2921             continue;
2922         }
2923         if (!activeAngle) {
2924             nextSegment->markAndChaseDoneUnary(nextAngle->start(), nextAngle->end());
2925         }
2926         SkOpSpan* last = nextAngle->lastMarked();
2927         if (last) {
2928             SkASSERT(!SkPathOpsDebug::ChaseContains(*chase, last));
2929             *chase->append() = last;
2930 #if DEBUG_WINDING
2931             SkDebugf("%s chase.append id=%d windSum=%d small=%d\n", __FUNCTION__,
2932                     last->fOther->fTs[last->fOtherIndex].fOther->debugID(), last->fWindSum,
2933                     last->fSmall);
2934 #endif
2935         }
2936     } while ((nextAngle = nextAngle->next()) != angle);
2937     markDoneUnary(SkMin32(startIndex, endIndex));
2938     if (!foundAngle) {
2939         return NULL;
2940     }
2941     *nextStart = foundAngle->start();
2942     *nextEnd = foundAngle->end();
2943     nextSegment = foundAngle->segment();
2944 #if DEBUG_WINDING
2945     SkDebugf("%s from:[%d] to:[%d] start=%d end=%d\n",
2946             __FUNCTION__, debugID(), nextSegment->debugID(), *nextStart, *nextEnd);
2947  #endif
2948     return nextSegment;
2949 }
2950
2951 SkOpSegment* SkOpSegment::findNextXor(int* nextStart, int* nextEnd, bool* unsortable) {
2952     const int startIndex = *nextStart;
2953     const int endIndex = *nextEnd;
2954     SkASSERT(startIndex != endIndex);
2955     SkDEBUGCODE(int count = fTs.count());
2956     SkASSERT(startIndex < endIndex ? startIndex < count - 1 : startIndex > 0);
2957     int step = SkSign32(endIndex - startIndex);
2958 // Detect cases where all the ends canceled out (e.g.,
2959 // there is no angle) and therefore there's only one valid connection
2960     *nextStart = startIndex;
2961     SkOpSegment* other = isSimple(nextStart, &step);
2962     if (other)
2963     {
2964 #if DEBUG_WINDING
2965         SkDebugf("%s simple\n", __FUNCTION__);
2966 #endif
2967         int min = SkMin32(startIndex, endIndex);
2968         if (fTs[min].fDone) {
2969             return NULL;
2970         }
2971         markDone(min, 1);
2972         double startT = other->fTs[*nextStart].fT;
2973         // FIXME: I don't know why the logic here is difference from the winding case
2974         SkDEBUGCODE(bool firstLoop = true;)
2975         if ((approximately_less_than_zero(startT) && step < 0)
2976                 || (approximately_greater_than_one(startT) && step > 0)) {
2977             step = -step;
2978             SkDEBUGCODE(firstLoop = false;)
2979         }
2980         do {
2981             *nextEnd = *nextStart;
2982             do {
2983                 *nextEnd += step;
2984             } while (precisely_zero(startT - other->fTs[*nextEnd].fT));
2985             if (other->fTs[SkMin32(*nextStart, *nextEnd)].fWindValue) {
2986                 break;
2987             }
2988             SkASSERT(firstLoop);
2989             SkDEBUGCODE(firstLoop = false;)
2990             step = -step;
2991         } while (true);
2992         SkASSERT(step < 0 ? *nextEnd >= 0 : *nextEnd < other->fTs.count());
2993         return other;
2994     }
2995     SkASSERT(startIndex - endIndex != 0);
2996     SkASSERT((startIndex - endIndex < 0) ^ (step < 0));
2997     // parallel block above with presorted version
2998     int end = nextExactSpan(startIndex, step);
2999     SkASSERT(end >= 0);
3000     SkOpAngle* angle = spanToAngle(end, startIndex);
3001     SkASSERT(angle);
3002 #if DEBUG_SORT
3003     SkDebugf("%s\n", __FUNCTION__);
3004     angle->debugLoop();
3005 #endif
3006     SkOpAngle* nextAngle = angle->next();
3007     const SkOpAngle* foundAngle = NULL;
3008     bool foundDone = false;
3009     SkOpSegment* nextSegment;
3010     int activeCount = 0;
3011     do {
3012         nextSegment = nextAngle->segment();
3013         ++activeCount;
3014         if (!foundAngle || (foundDone && activeCount & 1)) {
3015             if (nextSegment->isTiny(nextAngle)) {
3016                 *unsortable = true;
3017                 return NULL;
3018             }
3019             foundAngle = nextAngle;
3020             if (!(foundDone = nextSegment->done(nextAngle))) {
3021                 break;
3022             }
3023         }
3024         nextAngle = nextAngle->next();
3025     } while (nextAngle != angle);
3026     markDone(SkMin32(startIndex, endIndex), 1);
3027     if (!foundAngle) {
3028         return NULL;
3029     }
3030     *nextStart = foundAngle->start();
3031     *nextEnd = foundAngle->end();
3032     nextSegment = foundAngle->segment();
3033 #if DEBUG_WINDING
3034     SkDebugf("%s from:[%d] to:[%d] start=%d end=%d\n",
3035             __FUNCTION__, debugID(), nextSegment->debugID(), *nextStart, *nextEnd);
3036  #endif
3037     return nextSegment;
3038 }
3039
3040 int SkOpSegment::findStartSpan(int startIndex) const {
3041     int index = startIndex;
3042     const SkOpSpan* span = &fTs[index];
3043     const SkPoint& firstPt = span->fPt;
3044     double firstT = span->fT;
3045     const SkOpSpan* prior;
3046     do {
3047         prior = span;
3048         span = &fTs[++index];
3049     } while (SkDPoint::ApproximatelyEqual(span->fPt, firstPt)
3050             && (span->fT == firstT || prior->fTiny));
3051     return index;
3052 }
3053
3054 int SkOpSegment::findExactT(double t, const SkOpSegment* match) const {
3055     int count = this->count();
3056     for (int index = 0; index < count; ++index) {
3057         const SkOpSpan& span = fTs[index];
3058         if (span.fT == t && span.fOther == match) {
3059             return index;
3060         }
3061     }
3062     SkASSERT(0);
3063     return -1;
3064 }
3065
3066 int SkOpSegment::findOtherT(double t, const SkOpSegment* match) const {
3067     int count = this->count();
3068     for (int index = 0; index < count; ++index) {
3069         const SkOpSpan& span = fTs[index];
3070         if (span.fOtherT == t && span.fOther == match) {
3071             return index;
3072         }
3073     }
3074     return -1;
3075 }
3076
3077 int SkOpSegment::findT(double t, const SkPoint& pt, const SkOpSegment* match) const {
3078     int count = this->count();
3079     // prefer exact matches over approximate matches
3080     for (int index = 0; index < count; ++index) {
3081         const SkOpSpan& span = fTs[index];
3082         if (span.fT == t && span.fOther == match) {
3083             return index;
3084         }
3085     }
3086     for (int index = 0; index < count; ++index) {
3087         const SkOpSpan& span = fTs[index];
3088         if (approximately_equal_orderable(span.fT, t) && span.fOther == match) {
3089             return index;
3090         }
3091     }
3092     // Usually, the pair of ts are an exact match. It's possible that the t values have
3093     // been adjusted to make multiple intersections align. In this rare case, look for a
3094     // matching point / match pair instead.
3095     for (int index = 0; index < count; ++index) {
3096         const SkOpSpan& span = fTs[index];
3097         if (span.fPt == pt && span.fOther == match) {
3098             return index;
3099         }
3100     }
3101     SkASSERT(0);
3102     return -1;
3103 }
3104
3105 SkOpSegment* SkOpSegment::findTop(int* tIndexPtr, int* endIndexPtr, bool* unsortable,
3106         bool firstPass) {
3107     // iterate through T intersections and return topmost
3108     // topmost tangent from y-min to first pt is closer to horizontal
3109     SkASSERT(!done());
3110     int firstT = -1;
3111     /* SkPoint topPt = */ activeLeftTop(&firstT);
3112     if (firstT < 0) {
3113         *unsortable = !firstPass;
3114         firstT = 0;
3115         while (fTs[firstT].fDone) {
3116             SkASSERT(firstT < fTs.count());
3117             ++firstT;
3118         }
3119         *tIndexPtr = firstT;
3120         *endIndexPtr = nextExactSpan(firstT, 1);
3121         return this;
3122     }
3123     // sort the edges to find the leftmost
3124     int step = 1;
3125     int end;
3126     if (span(firstT).fDone || (end = nextSpan(firstT, step)) == -1) {
3127         step = -1;
3128         end = nextSpan(firstT, step);
3129         SkASSERT(end != -1);
3130     }
3131     // if the topmost T is not on end, or is three-way or more, find left
3132     // look for left-ness from tLeft to firstT (matching y of other)
3133     SkASSERT(firstT - end != 0);
3134     SkOpAngle* markAngle = spanToAngle(firstT, end);
3135     if (!markAngle) {
3136         markAngle = addSingletonAngles(step);
3137     }
3138     markAngle->markStops();
3139     const SkOpAngle* baseAngle = markAngle->next() == markAngle && !isVertical() ? markAngle
3140             : markAngle->findFirst();
3141     if (!baseAngle) {
3142         return NULL;  // nothing to do
3143     }
3144     SkScalar top = SK_ScalarMax;
3145     const SkOpAngle* firstAngle = NULL;
3146     const SkOpAngle* angle = baseAngle;
3147     do {
3148         if (!angle->unorderable()) {
3149             SkOpSegment* next = angle->segment();
3150             SkPathOpsBounds bounds;
3151             next->subDivideBounds(angle->end(), angle->start(), &bounds);
3152             if (approximately_greater(top, bounds.fTop)) {
3153                 top = bounds.fTop;
3154                 firstAngle = angle;
3155             }
3156         }
3157         angle = angle->next();
3158     } while (angle != baseAngle);
3159     SkASSERT(firstAngle);
3160 #if DEBUG_SORT
3161     SkDebugf("%s\n", __FUNCTION__);
3162     firstAngle->debugLoop();
3163 #endif
3164     // skip edges that have already been processed
3165     angle = firstAngle;
3166     SkOpSegment* leftSegment = NULL;
3167     bool looped = false;
3168     do {
3169         *unsortable = angle->unorderable();
3170         if (firstPass || !*unsortable) {
3171             leftSegment = angle->segment();
3172             *tIndexPtr = angle->end();
3173             *endIndexPtr = angle->start();
3174             if (!leftSegment->fTs[SkMin32(*tIndexPtr, *endIndexPtr)].fDone) {
3175                 break;
3176             }
3177         }
3178         angle = angle->next();
3179         looped = true;
3180     } while (angle != firstAngle);
3181     if (angle == firstAngle && looped) {
3182         return NULL;
3183     }
3184     if (leftSegment->verb() >= SkPath::kQuad_Verb) {
3185         const int tIndex = *tIndexPtr;
3186         const int endIndex = *endIndexPtr;
3187         bool swap;
3188         if (!leftSegment->clockwise(tIndex, endIndex, &swap)) {
3189     #if DEBUG_SWAP_TOP
3190             SkDebugf("%s swap=%d inflections=%d serpentine=%d controlledbyends=%d monotonic=%d\n",
3191                     __FUNCTION__,
3192                     swap, leftSegment->debugInflections(tIndex, endIndex),
3193                     leftSegment->serpentine(tIndex, endIndex),
3194                     leftSegment->controlsContainedByEnds(tIndex, endIndex),
3195                     leftSegment->monotonicInY(tIndex, endIndex));
3196     #endif
3197             if (swap) {
3198     // FIXME: I doubt it makes sense to (necessarily) swap if the edge was not the first
3199     // sorted but merely the first not already processed (i.e., not done)
3200                 SkTSwap(*tIndexPtr, *endIndexPtr);
3201             }
3202         }
3203     }
3204     SkASSERT(!leftSegment->fTs[SkMin32(*tIndexPtr, *endIndexPtr)].fTiny);
3205     return leftSegment;
3206 }
3207
3208 int SkOpSegment::firstActive(int tIndex) const {
3209     while (fTs[tIndex].fTiny) {
3210         SkASSERT(!isCanceled(tIndex));
3211         ++tIndex;
3212     }
3213     return tIndex;
3214 }
3215
3216 // FIXME: not crazy about this
3217 // when the intersections are performed, the other index is into an
3218 // incomplete array. As the array grows, the indices become incorrect
3219 // while the following fixes the indices up again, it isn't smart about
3220 // skipping segments whose indices are already correct
3221 // assuming we leave the code that wrote the index in the first place
3222 // FIXME: if called after remove, this needs to correct tiny
3223 void SkOpSegment::fixOtherTIndex() {
3224     int iCount = fTs.count();
3225     for (int i = 0; i < iCount; ++i) {
3226         SkOpSpan& iSpan = fTs[i];
3227         double oT = iSpan.fOtherT;
3228         SkOpSegment* other = iSpan.fOther;
3229         int oCount = other->fTs.count();
3230         SkDEBUGCODE(iSpan.fOtherIndex = -1);
3231         for (int o = 0; o < oCount; ++o) {
3232             SkOpSpan& oSpan = other->fTs[o];
3233             if (oT == oSpan.fT && this == oSpan.fOther && oSpan.fOtherT == iSpan.fT) {
3234                 iSpan.fOtherIndex = o;
3235                 oSpan.fOtherIndex = i;
3236                 break;
3237             }
3238         }
3239         SkASSERT(iSpan.fOtherIndex >= 0);
3240     }
3241 }
3242
3243 bool SkOpSegment::inCoincidentSpan(double t, const SkOpSegment* other) const {
3244     int foundEnds = 0;
3245     int count = this->count();
3246     for (int index = 0; index < count; ++index) {
3247         const SkOpSpan& span = this->span(index);
3248         if (span.fCoincident) {
3249             foundEnds |= (span.fOther == other) << ((t > span.fT) + (t >= span.fT));
3250         }
3251     }
3252     SkASSERT(foundEnds != 7);
3253     return foundEnds == 0x3 || foundEnds == 0x5 || foundEnds == 0x6;  // two bits set
3254 }
3255
3256 void SkOpSegment::init(const SkPoint pts[], SkPath::Verb verb, bool operand, bool evenOdd) {
3257     fDoneSpans = 0;
3258     fOperand = operand;
3259     fXor = evenOdd;
3260     fPts = pts;
3261     fVerb = verb;
3262     fLoop = fMultiples = fSmall = fTiny = false;
3263 }
3264
3265 void SkOpSegment::initWinding(int start, int end, SkOpAngle::IncludeType angleIncludeType) {
3266     int local = spanSign(start, end);
3267     if (angleIncludeType == SkOpAngle::kBinarySingle) {
3268         int oppLocal = oppSign(start, end);
3269         (void) markAndChaseWinding(start, end, local, oppLocal);
3270     // OPTIMIZATION: the reverse mark and chase could skip the first marking
3271         (void) markAndChaseWinding(end, start, local, oppLocal);
3272     } else {
3273         (void) markAndChaseWinding(start, end, local);
3274     // OPTIMIZATION: the reverse mark and chase could skip the first marking
3275         (void) markAndChaseWinding(end, start, local);
3276     }
3277 }
3278
3279 /*
3280 when we start with a vertical intersect, we try to use the dx to determine if the edge is to
3281 the left or the right of vertical. This determines if we need to add the span's
3282 sign or not. However, this isn't enough.
3283 If the supplied sign (winding) is zero, then we didn't hit another vertical span, so dx is needed.
3284 If there was a winding, then it may or may not need adjusting. If the span the winding was borrowed
3285 from has the same x direction as this span, the winding should change. If the dx is opposite, then
3286 the same winding is shared by both.
3287 */
3288 void SkOpSegment::initWinding(int start, int end, double tHit, int winding, SkScalar hitDx,
3289                               int oppWind, SkScalar hitOppDx) {
3290     SkASSERT(hitDx || !winding);
3291     SkScalar dx = (*CurveSlopeAtT[SkPathOpsVerbToPoints(fVerb)])(fPts, tHit).fX;
3292     SkASSERT(dx);
3293     int windVal = windValue(SkMin32(start, end));
3294 #if DEBUG_WINDING_AT_T
3295     SkDebugf("%s id=%d oldWinding=%d hitDx=%c dx=%c windVal=%d", __FUNCTION__, debugID(), winding,
3296             hitDx ? hitDx > 0 ? '+' : '-' : '0', dx > 0 ? '+' : '-', windVal);
3297 #endif
3298     int sideWind = winding + (dx < 0 ? windVal : -windVal);
3299     if (abs(winding) < abs(sideWind)) {
3300         winding = sideWind;
3301     }
3302     SkDEBUGCODE(int oppLocal = oppSign(start, end));
3303     SkASSERT(hitOppDx || !oppWind || !oppLocal);
3304     int oppWindVal = oppValue(SkMin32(start, end));
3305     if (!oppWind) {
3306         oppWind = dx < 0 ? oppWindVal : -oppWindVal;
3307     } else if (hitOppDx * dx >= 0) {
3308         int oppSideWind = oppWind + (dx < 0 ? oppWindVal : -oppWindVal);
3309         if (abs(oppWind) < abs(oppSideWind)) {
3310             oppWind = oppSideWind;
3311         }
3312     }
3313 #if DEBUG_WINDING_AT_T
3314     SkDebugf(" winding=%d oppWind=%d\n", winding, oppWind);
3315 #endif
3316     (void) markAndChaseWinding(start, end, winding, oppWind);
3317     // OPTIMIZATION: the reverse mark and chase could skip the first marking
3318     (void) markAndChaseWinding(end, start, winding, oppWind);
3319 }
3320
3321 bool SkOpSegment::inLoop(const SkOpAngle* baseAngle, int spanCount, int* indexPtr) const {
3322     if (!baseAngle->inLoop()) {
3323         return false;
3324     }
3325     int index = *indexPtr;
3326     SkOpAngle* from = fTs[index].fFromAngle;
3327     SkOpAngle* to = fTs[index].fToAngle;
3328     while (++index < spanCount) {
3329         SkOpAngle* nextFrom = fTs[index].fFromAngle;
3330         SkOpAngle* nextTo = fTs[index].fToAngle;
3331         if (from != nextFrom || to != nextTo) {
3332             break;
3333         }
3334     }
3335     *indexPtr = index;
3336     return true;
3337 }
3338
3339 // OPTIMIZE: successive calls could start were the last leaves off
3340 // or calls could specialize to walk forwards or backwards
3341 bool SkOpSegment::isMissing(double startT, const SkPoint& pt) const {
3342     int tCount = fTs.count();
3343     for (int index = 0; index < tCount; ++index) {
3344         const SkOpSpan& span = fTs[index];
3345         if (approximately_zero(startT - span.fT) && pt == span.fPt) {
3346             return false;
3347         }
3348     }
3349     return true;
3350 }
3351
3352
3353 SkOpSegment* SkOpSegment::isSimple(int* end, int* step) {
3354     return nextChase(end, step, NULL, NULL);
3355 }
3356
3357 bool SkOpSegment::isTiny(const SkOpAngle* angle) const {
3358     int start = angle->start();
3359     int end = angle->end();
3360     const SkOpSpan& mSpan = fTs[SkMin32(start, end)];
3361     return mSpan.fTiny;
3362 }
3363
3364 bool SkOpSegment::isTiny(int index) const {
3365     return fTs[index].fTiny;
3366 }
3367
3368 // look pair of active edges going away from coincident edge
3369 // one of them should be the continuation of other
3370 // if both are active, look to see if they both the connect to another coincident pair
3371 // if at least one is a line, then make the pair coincident
3372 // if neither is a line, test for coincidence
3373 bool SkOpSegment::joinCoincidence(SkOpSegment* other, double otherT, const SkPoint& otherPt,
3374         int step, bool cancel) {
3375     int otherTIndex = other->findT(otherT, otherPt, this);
3376     int next = other->nextExactSpan(otherTIndex, step);
3377     int otherMin = SkMin32(otherTIndex, next);
3378     int otherWind = other->span(otherMin).fWindValue;
3379     if (otherWind == 0) {
3380         return false;
3381     }
3382     SkASSERT(next >= 0);
3383     int tIndex = 0;
3384     do {
3385         SkOpSpan* test = &fTs[tIndex];
3386         SkASSERT(test->fT == 0);
3387         if (test->fOther == other || test->fOtherT != 1) {
3388             continue;
3389         }
3390         SkPoint startPt, endPt;
3391         double endT;
3392         if (findCoincidentMatch(test, other, otherTIndex, next, step, &startPt, &endPt, &endT)) {
3393             SkOpSegment* match = test->fOther;
3394             if (cancel) {
3395                 match->addTCancel(startPt, endPt, other);
3396             } else {
3397                 SkAssertResult(match->addTCoincident(startPt, endPt, endT, other));
3398             }
3399             return true;
3400         }
3401     } while (fTs[++tIndex].fT == 0);
3402     return false;
3403 }
3404
3405 // this span is excluded by the winding rule -- chase the ends
3406 // as long as they are unambiguous to mark connections as done
3407 // and give them the same winding value
3408
3409 SkOpSpan* SkOpSegment::markAndChaseDoneBinary(int index, int endIndex) {
3410     int step = SkSign32(endIndex - index);
3411     int min = SkMin32(index, endIndex);
3412     markDoneBinary(min);
3413     SkOpSpan* last = NULL;
3414     SkOpSegment* other = this;
3415     while ((other = other->nextChase(&index, &step, &min, &last))) {
3416         if (other->done()) {
3417             SkASSERT(!last);
3418             break;
3419         }
3420         other->markDoneBinary(min);
3421     }
3422     return last;
3423 }
3424
3425 SkOpSpan* SkOpSegment::markAndChaseDoneUnary(int index, int endIndex) {
3426     int step = SkSign32(endIndex - index);
3427     int min = SkMin32(index, endIndex);
3428     markDoneUnary(min);
3429     SkOpSpan* last = NULL;
3430     SkOpSegment* other = this;
3431     while ((other = other->nextChase(&index, &step, &min, &last))) {
3432         if (other->done()) {
3433             SkASSERT(!last);
3434             break;
3435         }
3436         other->markDoneUnary(min);
3437     }
3438     return last;
3439 }
3440
3441 SkOpSpan* SkOpSegment::markAndChaseWinding(const SkOpAngle* angle, int winding) {
3442     int index = angle->start();
3443     int endIndex = angle->end();
3444     int step = SkSign32(endIndex - index);
3445     int min = SkMin32(index, endIndex);
3446     markWinding(min, winding);
3447     SkOpSpan* last = NULL;
3448     SkOpSegment* other = this;
3449     while ((other = other->nextChase(&index, &step, &min, &last))) {
3450         if (other->fTs[min].fWindSum != SK_MinS32) {
3451 //            SkASSERT(other->fTs[min].fWindSum == winding);
3452             SkASSERT(!last);
3453             break;
3454         }
3455         other->markWinding(min, winding);
3456     }
3457     return last;
3458 }
3459
3460 SkOpSpan* SkOpSegment::markAndChaseWinding(int index, int endIndex, int winding) {
3461     int min = SkMin32(index, endIndex);
3462     int step = SkSign32(endIndex - index);
3463     markWinding(min, winding);
3464     SkOpSpan* last = NULL;
3465     SkOpSegment* other = this;
3466     while ((other = other->nextChase(&index, &step, &min, &last))) {
3467         if (other->fTs[min].fWindSum != SK_MinS32) {
3468             SkASSERT(other->fTs[min].fWindSum == winding || other->fTs[min].fLoop);
3469             SkASSERT(!last);
3470             break;
3471         }
3472         other->markWinding(min, winding);
3473     }
3474     return last;
3475 }
3476
3477 SkOpSpan* SkOpSegment::markAndChaseWinding(int index, int endIndex, int winding, int oppWinding) {
3478     int min = SkMin32(index, endIndex);
3479     int step = SkSign32(endIndex - index);
3480     markWinding(min, winding, oppWinding);
3481     SkOpSpan* last = NULL;
3482     SkOpSegment* other = this;
3483     while ((other = other->nextChase(&index, &step, &min, &last))) {
3484         if (other->fTs[min].fWindSum != SK_MinS32) {
3485 #ifdef SK_DEBUG
3486             if (!other->fTs[min].fLoop) {
3487                 if (fOperand == other->fOperand) {
3488 // FIXME: this is probably a bug -- rects4 asserts here
3489 //                    SkASSERT(other->fTs[min].fWindSum == winding);
3490 // FIXME: this is probably a bug -- rects3 asserts here
3491 //                    SkASSERT(other->fTs[min].fOppSum == oppWinding);
3492                 } else {
3493                     SkASSERT(other->fTs[min].fWindSum == oppWinding);
3494 // FIXME: this is probably a bug -- skpwww_joomla_org_23 asserts here
3495 //                    SkASSERT(other->fTs[min].fOppSum == winding);
3496                 }
3497             }
3498             SkASSERT(!last);
3499 #endif
3500             break;
3501         }
3502         if (fOperand == other->fOperand) {
3503             other->markWinding(min, winding, oppWinding);
3504         } else {
3505             other->markWinding(min, oppWinding, winding);
3506         }
3507     }
3508     return last;
3509 }
3510
3511 SkOpSpan* SkOpSegment::markAndChaseWinding(const SkOpAngle* angle, int winding, int oppWinding) {
3512     int start = angle->start();
3513     int end = angle->end();
3514     return markAndChaseWinding(start, end, winding, oppWinding);
3515 }
3516
3517 SkOpSpan* SkOpSegment::markAngle(int maxWinding, int sumWinding, const SkOpAngle* angle) {
3518     SkASSERT(angle->segment() == this);
3519     if (UseInnerWinding(maxWinding, sumWinding)) {
3520         maxWinding = sumWinding;
3521     }
3522     SkOpSpan* last = markAndChaseWinding(angle, maxWinding);
3523 #if DEBUG_WINDING
3524     if (last) {
3525         SkDebugf("%s last id=%d windSum=", __FUNCTION__,
3526                 last->fOther->fTs[last->fOtherIndex].fOther->debugID());
3527         SkPathOpsDebug::WindingPrintf(last->fWindSum);
3528         SkDebugf(" small=%d\n", last->fSmall);
3529     }
3530 #endif
3531     return last;
3532 }
3533
3534 SkOpSpan* SkOpSegment::markAngle(int maxWinding, int sumWinding, int oppMaxWinding,
3535                                  int oppSumWinding, const SkOpAngle* angle) {
3536     SkASSERT(angle->segment() == this);
3537     if (UseInnerWinding(maxWinding, sumWinding)) {
3538         maxWinding = sumWinding;
3539     }
3540     if (oppMaxWinding != oppSumWinding && UseInnerWinding(oppMaxWinding, oppSumWinding)) {
3541         oppMaxWinding = oppSumWinding;
3542     }
3543     SkOpSpan* last = markAndChaseWinding(angle, maxWinding, oppMaxWinding);
3544 #if DEBUG_WINDING
3545     if (last) {
3546         SkDebugf("%s last id=%d windSum=", __FUNCTION__,
3547                 last->fOther->fTs[last->fOtherIndex].fOther->debugID());
3548         SkPathOpsDebug::WindingPrintf(last->fWindSum);
3549         SkDebugf(" small=%d\n", last->fSmall);
3550     }
3551 #endif
3552     return last;
3553 }
3554
3555 // FIXME: this should also mark spans with equal (x,y)
3556 // This may be called when the segment is already marked done. While this
3557 // wastes time, it shouldn't do any more than spin through the T spans.
3558 // OPTIMIZATION: abort on first done found (assuming that this code is
3559 // always called to mark segments done).
3560 void SkOpSegment::markDone(int index, int winding) {
3561   //  SkASSERT(!done());
3562     SkASSERT(winding);
3563     double referenceT = fTs[index].fT;
3564     int lesser = index;
3565     while (--lesser >= 0 && precisely_negative(referenceT - fTs[lesser].fT)) {
3566         markOneDone(__FUNCTION__, lesser, winding);
3567     }
3568     do {
3569         markOneDone(__FUNCTION__, index, winding);
3570     } while (++index < fTs.count() && precisely_negative(fTs[index].fT - referenceT));
3571     debugValidate();
3572 }
3573
3574 void SkOpSegment::markDoneBinary(int index) {
3575     double referenceT = fTs[index].fT;
3576     int lesser = index;
3577     while (--lesser >= 0 && precisely_negative(referenceT - fTs[lesser].fT)) {
3578         markOneDoneBinary(__FUNCTION__, lesser);
3579     }
3580     do {
3581         markOneDoneBinary(__FUNCTION__, index);
3582     } while (++index < fTs.count() && precisely_negative(fTs[index].fT - referenceT));
3583     debugValidate();
3584 }
3585
3586 void SkOpSegment::markDoneUnary(int index) {
3587     double referenceT = fTs[index].fT;
3588     int lesser = index;
3589     while (--lesser >= 0 && precisely_negative(referenceT - fTs[lesser].fT)) {
3590         markOneDoneUnary(__FUNCTION__, lesser);
3591     }
3592     do {
3593         markOneDoneUnary(__FUNCTION__, index);
3594     } while (++index < fTs.count() && precisely_negative(fTs[index].fT - referenceT));
3595     debugValidate();
3596 }
3597
3598 void SkOpSegment::markOneDone(const char* funName, int tIndex, int winding) {
3599     SkOpSpan* span = markOneWinding(funName, tIndex, winding);
3600     if (!span || span->fDone) {
3601         return;
3602     }
3603     span->fDone = true;
3604     fDoneSpans++;
3605 }
3606
3607 void SkOpSegment::markOneDoneBinary(const char* funName, int tIndex) {
3608     SkOpSpan* span = verifyOneWinding(funName, tIndex);
3609     if (!span) {
3610         return;
3611     }
3612     SkASSERT(!span->fDone);
3613     span->fDone = true;
3614     fDoneSpans++;
3615 }
3616
3617 void SkOpSegment::markOneDoneUnary(const char* funName, int tIndex) {
3618     SkOpSpan* span = verifyOneWindingU(funName, tIndex);
3619     if (!span) {
3620         return;
3621     }
3622     if (span->fWindSum == SK_MinS32) {
3623         SkDebugf("%s uncomputed\n", __FUNCTION__);
3624     }
3625     SkASSERT(!span->fDone);
3626     span->fDone = true;
3627     fDoneSpans++;
3628 }
3629
3630 SkOpSpan* SkOpSegment::markOneWinding(const char* funName, int tIndex, int winding) {
3631     SkOpSpan& span = fTs[tIndex];
3632     if (span.fDone && !span.fSmall) {
3633         return NULL;
3634     }
3635 #if DEBUG_MARK_DONE
3636     debugShowNewWinding(funName, span, winding);
3637 #endif
3638     SkASSERT(span.fWindSum == SK_MinS32 || span.fWindSum == winding);
3639 #if DEBUG_LIMIT_WIND_SUM
3640     SkASSERT(abs(winding) <= DEBUG_LIMIT_WIND_SUM);
3641 #endif
3642     span.fWindSum = winding;
3643     return &span;
3644 }
3645
3646 SkOpSpan* SkOpSegment::markOneWinding(const char* funName, int tIndex, int winding,
3647                                       int oppWinding) {
3648     SkOpSpan& span = fTs[tIndex];
3649     if (span.fDone && !span.fSmall) {
3650         return NULL;
3651     }
3652 #if DEBUG_MARK_DONE
3653     debugShowNewWinding(funName, span, winding, oppWinding);
3654 #endif
3655     SkASSERT(span.fWindSum == SK_MinS32 || span.fWindSum == winding);
3656 #if DEBUG_LIMIT_WIND_SUM
3657     SkASSERT(abs(winding) <= DEBUG_LIMIT_WIND_SUM);
3658 #endif
3659     span.fWindSum = winding;
3660     SkASSERT(span.fOppSum == SK_MinS32 || span.fOppSum == oppWinding);
3661 #if DEBUG_LIMIT_WIND_SUM
3662     SkASSERT(abs(oppWinding) <= DEBUG_LIMIT_WIND_SUM);
3663 #endif
3664     span.fOppSum = oppWinding;
3665     debugValidate();
3666     return &span;
3667 }
3668
3669 // from http://stackoverflow.com/questions/1165647/how-to-determine-if-a-list-of-polygon-points-are-in-clockwise-order
3670 bool SkOpSegment::clockwise(int tStart, int tEnd, bool* swap) const {
3671     SkASSERT(fVerb != SkPath::kLine_Verb);
3672     SkPoint edge[4];
3673     subDivide(tStart, tEnd, edge);
3674     int points = SkPathOpsVerbToPoints(fVerb);
3675     double sum = (edge[0].fX - edge[points].fX) * (edge[0].fY + edge[points].fY);
3676     bool sumSet = false;
3677     if (fVerb == SkPath::kCubic_Verb) {
3678         SkDCubic cubic;
3679         cubic.set(edge);
3680         double inflectionTs[2];
3681         int inflections = cubic.findInflections(inflectionTs);
3682         // FIXME: this fixes cubicOp114 and breaks cubicOp58d
3683         // the trouble is that cubics with inflections confuse whether the curve breaks towards
3684         // or away, which in turn is used to determine if it is on the far right or left.
3685         // Probably a totally different approach is in order. At one time I tried to project a
3686         // horizontal ray to determine winding, but was confused by how to map the vertically
3687         // oriented winding computation over.
3688         if (0 && inflections) {
3689             double tLo = this->span(tStart).fT;
3690             double tHi = this->span(tEnd).fT;
3691             double tLoStart = tLo;
3692             for (int index = 0; index < inflections; ++index) {
3693                 if (between(tLo, inflectionTs[index], tHi)) {
3694                     tLo = inflectionTs[index];
3695                 }
3696             }
3697             if (tLo != tLoStart && tLo != tHi) {
3698                 SkDPoint sub[2];
3699                 sub[0] = cubic.ptAtT(tLo);
3700                 sub[1].set(edge[3]);
3701                 SkDPoint ctrl[2];
3702                 SkDCubic::SubDivide(fPts, sub[0], sub[1], tLo, tHi, ctrl);
3703                 edge[0] = sub[0].asSkPoint();
3704                 edge[1] = ctrl[0].asSkPoint();
3705                 edge[2] = ctrl[1].asSkPoint();
3706                 sum = (edge[0].fX - edge[3].fX) * (edge[0].fY + edge[3].fY);
3707             }
3708         }
3709         SkScalar lesser = SkTMin<SkScalar>(edge[0].fY, edge[3].fY);
3710         if (edge[1].fY < lesser && edge[2].fY < lesser) {
3711             SkDLine tangent1 = {{ {edge[0].fX, edge[0].fY}, {edge[1].fX, edge[1].fY} }};
3712             SkDLine tangent2 = {{ {edge[2].fX, edge[2].fY}, {edge[3].fX, edge[3].fY} }};
3713             if (SkIntersections::Test(tangent1, tangent2)) {
3714                 SkPoint topPt = cubic_top(fPts, fTs[tStart].fT, fTs[tEnd].fT);
3715                 sum += (topPt.fX - edge[0].fX) * (topPt.fY + edge[0].fY);
3716                 sum += (edge[3].fX - topPt.fX) * (edge[3].fY + topPt.fY);
3717                 sumSet = true;
3718             }
3719         }
3720     }
3721     if (!sumSet) {
3722         for (int idx = 0; idx < points; ++idx){
3723             sum += (edge[idx + 1].fX - edge[idx].fX) * (edge[idx + 1].fY + edge[idx].fY);
3724         }
3725     }
3726     if (fVerb == SkPath::kCubic_Verb) {
3727         SkDCubic cubic;
3728         cubic.set(edge);
3729          *swap = sum > 0 && !cubic.monotonicInY() && !cubic.serpentine();
3730     } else {
3731         SkDQuad quad;
3732         quad.set(edge);
3733         *swap = sum > 0 && !quad.monotonicInY();
3734     }
3735     return sum <= 0;
3736 }
3737
3738 bool SkOpSegment::monotonicInY(int tStart, int tEnd) const {
3739     SkASSERT(fVerb != SkPath::kLine_Verb);
3740     if (fVerb == SkPath::kQuad_Verb) {
3741         SkDQuad dst = SkDQuad::SubDivide(fPts, fTs[tStart].fT, fTs[tEnd].fT);
3742         return dst.monotonicInY();
3743     }
3744     SkASSERT(fVerb == SkPath::kCubic_Verb);
3745     SkDCubic dst = SkDCubic::SubDivide(fPts, fTs[tStart].fT, fTs[tEnd].fT);
3746     return dst.monotonicInY();
3747 }
3748
3749 bool SkOpSegment::serpentine(int tStart, int tEnd) const {
3750     if (fVerb != SkPath::kCubic_Verb) {
3751         return false;
3752     }
3753     SkDCubic dst = SkDCubic::SubDivide(fPts, fTs[tStart].fT, fTs[tEnd].fT);
3754     return dst.serpentine();
3755 }
3756
3757 SkOpSpan* SkOpSegment::verifyOneWinding(const char* funName, int tIndex) {
3758     SkOpSpan& span = fTs[tIndex];
3759     if (span.fDone) {
3760         return NULL;
3761     }
3762 #if DEBUG_MARK_DONE
3763     debugShowNewWinding(funName, span, span.fWindSum, span.fOppSum);
3764 #endif
3765 // If the prior angle in the sort is unorderable, the winding sum may not be computable.
3766 // To enable the assert, the 'prior is unorderable' state could be
3767 // piped down to this test, but not sure it's worth it.
3768 // (Once the sort order is stored in the span, this test may be feasible.)
3769 //    SkASSERT(span.fWindSum != SK_MinS32);
3770 //    SkASSERT(span.fOppSum != SK_MinS32);
3771     return &span;
3772 }
3773
3774 SkOpSpan* SkOpSegment::verifyOneWindingU(const char* funName, int tIndex) {
3775     SkOpSpan& span = fTs[tIndex];
3776     if (span.fDone) {
3777         return NULL;
3778     }
3779 #if DEBUG_MARK_DONE
3780     debugShowNewWinding(funName, span, span.fWindSum);
3781 #endif
3782 // If the prior angle in the sort is unorderable, the winding sum may not be computable.
3783 // To enable the assert, the 'prior is unorderable' state could be
3784 // piped down to this test, but not sure it's worth it.
3785 // (Once the sort order is stored in the span, this test may be feasible.)
3786 //    SkASSERT(span.fWindSum != SK_MinS32);
3787     return &span;
3788 }
3789
3790 void SkOpSegment::markWinding(int index, int winding) {
3791 //    SkASSERT(!done());
3792     SkASSERT(winding);
3793     double referenceT = fTs[index].fT;
3794     int lesser = index;
3795     while (--lesser >= 0 && precisely_negative(referenceT - fTs[lesser].fT)) {
3796         markOneWinding(__FUNCTION__, lesser, winding);
3797     }
3798     do {
3799         markOneWinding(__FUNCTION__, index, winding);
3800    } while (++index < fTs.count() && precisely_negative(fTs[index].fT - referenceT));
3801     debugValidate();
3802 }
3803
3804 void SkOpSegment::markWinding(int index, int winding, int oppWinding) {
3805 //    SkASSERT(!done());
3806     SkASSERT(winding || oppWinding);
3807     double referenceT = fTs[index].fT;
3808     int lesser = index;
3809     while (--lesser >= 0 && precisely_negative(referenceT - fTs[lesser].fT)) {
3810         markOneWinding(__FUNCTION__, lesser, winding, oppWinding);
3811     }
3812     do {
3813         markOneWinding(__FUNCTION__, index, winding, oppWinding);
3814    } while (++index < fTs.count() && precisely_negative(fTs[index].fT - referenceT));
3815     debugValidate();
3816 }
3817
3818 void SkOpSegment::matchWindingValue(int tIndex, double t, bool borrowWind) {
3819     int nextDoorWind = SK_MaxS32;
3820     int nextOppWind = SK_MaxS32;
3821     // prefer exact matches
3822     if (tIndex > 0) {
3823         const SkOpSpan& below = fTs[tIndex - 1];
3824         if (below.fT == t) {
3825             nextDoorWind = below.fWindValue;
3826             nextOppWind = below.fOppValue;
3827         }
3828     }
3829     if (nextDoorWind == SK_MaxS32 && tIndex + 1 < fTs.count()) {
3830         const SkOpSpan& above = fTs[tIndex + 1];
3831         if (above.fT == t) {
3832             nextDoorWind = above.fWindValue;
3833             nextOppWind = above.fOppValue;
3834         }
3835     }
3836     if (nextDoorWind == SK_MaxS32 && tIndex > 0) {
3837         const SkOpSpan& below = fTs[tIndex - 1];
3838         if (approximately_negative(t - below.fT)) {
3839             nextDoorWind = below.fWindValue;
3840             nextOppWind = below.fOppValue;
3841         }
3842     }
3843     if (nextDoorWind == SK_MaxS32 && tIndex + 1 < fTs.count()) {
3844         const SkOpSpan& above = fTs[tIndex + 1];
3845         if (approximately_negative(above.fT - t)) {
3846             nextDoorWind = above.fWindValue;
3847             nextOppWind = above.fOppValue;
3848         }
3849     }
3850     if (nextDoorWind == SK_MaxS32 && borrowWind && tIndex > 0 && t < 1) {
3851         const SkOpSpan& below = fTs[tIndex - 1];
3852         nextDoorWind = below.fWindValue;
3853         nextOppWind = below.fOppValue;
3854     }
3855     if (nextDoorWind != SK_MaxS32) {
3856         SkOpSpan& newSpan = fTs[tIndex];
3857         newSpan.fWindValue = nextDoorWind;
3858         newSpan.fOppValue = nextOppWind;
3859         if (!nextDoorWind && !nextOppWind && !newSpan.fDone) {
3860             newSpan.fDone = true;
3861             ++fDoneSpans;
3862         }
3863     }
3864 }
3865
3866 bool SkOpSegment::nextCandidate(int* start, int* end) const {
3867     while (fTs[*end].fDone) {
3868         if (fTs[*end].fT == 1) {
3869             return false;
3870         }
3871         ++(*end);
3872     }
3873     *start = *end;
3874     *end = nextExactSpan(*start, 1);
3875     return true;
3876 }
3877
3878 static SkOpSegment* set_last(SkOpSpan** last, SkOpSpan* endSpan) {
3879     if (last && !endSpan->fSmall) {
3880         *last = endSpan;
3881     }
3882     return NULL;
3883 }
3884
3885 SkOpSegment* SkOpSegment::nextChase(int* indexPtr, int* stepPtr, int* minPtr, SkOpSpan** last) {
3886     int origIndex = *indexPtr;
3887     int step = *stepPtr;
3888     int end = nextExactSpan(origIndex, step);
3889     SkASSERT(end >= 0);
3890     SkOpSpan& endSpan = fTs[end];
3891     SkOpAngle* angle = step > 0 ? endSpan.fFromAngle : endSpan.fToAngle;
3892     int foundIndex;
3893     int otherEnd;
3894     SkOpSegment* other;
3895     if (angle == NULL) {
3896         if (endSpan.fT != 0 && endSpan.fT != 1) {
3897             return NULL;
3898         }
3899         other = endSpan.fOther;
3900         foundIndex = endSpan.fOtherIndex;
3901         otherEnd = other->nextExactSpan(foundIndex, step);
3902     } else {
3903         int loopCount = angle->loopCount();
3904         if (loopCount > 2) {
3905             return set_last(last, &endSpan);
3906         }
3907         const SkOpAngle* next = angle->next();
3908         if (angle->sign() != next->sign()) {
3909 #if DEBUG_WINDING
3910             SkDebugf("%s mismatched signs\n", __FUNCTION__);
3911 #endif
3912         //    return set_last(last, &endSpan);
3913         }
3914         other = next->segment();
3915         foundIndex = end = next->start();
3916         otherEnd = next->end();
3917     }
3918     int foundStep = foundIndex < otherEnd ? 1 : -1;
3919     if (*stepPtr != foundStep) {
3920         return set_last(last, &endSpan);
3921     }
3922     SkASSERT(*indexPtr >= 0);
3923     SkASSERT(otherEnd >= 0);
3924 #if 1
3925     int origMin = origIndex + (step < 0 ? step : 0);
3926     const SkOpSpan& orig = this->span(origMin);
3927 #endif
3928     int foundMin = SkMin32(foundIndex, otherEnd);
3929 #if 1
3930     const SkOpSpan& found = other->span(foundMin);
3931     if (found.fWindValue != orig.fWindValue || found.fOppValue != orig.fOppValue) {
3932           return set_last(last, &endSpan);
3933     }
3934 #endif
3935     *indexPtr = foundIndex;
3936     *stepPtr = foundStep;
3937     if (minPtr) {
3938         *minPtr = foundMin;
3939     }
3940     return other;
3941 }
3942
3943 // This has callers for two different situations: one establishes the end
3944 // of the current span, and one establishes the beginning of the next span
3945 // (thus the name). When this is looking for the end of the current span,
3946 // coincidence is found when the beginning Ts contain -step and the end
3947 // contains step. When it is looking for the beginning of the next, the
3948 // first Ts found can be ignored and the last Ts should contain -step.
3949 // OPTIMIZATION: probably should split into two functions
3950 int SkOpSegment::nextSpan(int from, int step) const {
3951     const SkOpSpan& fromSpan = fTs[from];
3952     int count = fTs.count();
3953     int to = from;
3954     while (step > 0 ? ++to < count : --to >= 0) {
3955         const SkOpSpan& span = fTs[to];
3956         if (approximately_zero(span.fT - fromSpan.fT)) {
3957             continue;
3958         }
3959         return to;
3960     }
3961     return -1;
3962 }
3963
3964 // FIXME
3965 // this returns at any difference in T, vs. a preset minimum. It may be
3966 // that all callers to nextSpan should use this instead.
3967 int SkOpSegment::nextExactSpan(int from, int step) const {
3968     int to = from;
3969     if (step < 0) {
3970         const SkOpSpan& fromSpan = fTs[from];
3971         while (--to >= 0) {
3972             const SkOpSpan& span = fTs[to];
3973             if (precisely_negative(fromSpan.fT - span.fT) || span.fTiny) {
3974                 continue;
3975             }
3976             return to;
3977         }
3978     } else {
3979         while (fTs[from].fTiny) {
3980             from++;
3981         }
3982         const SkOpSpan& fromSpan = fTs[from];
3983         int count = fTs.count();
3984         while (++to < count) {
3985             const SkOpSpan& span = fTs[to];
3986             if (precisely_negative(span.fT - fromSpan.fT)) {
3987                 continue;
3988             }
3989             return to;
3990         }
3991     }
3992     return -1;
3993 }
3994
3995 void SkOpSegment::pinT(const SkPoint& pt, double* t) {
3996     if (pt == fPts[0]) {
3997         *t = 0;
3998     }
3999     int count = SkPathOpsVerbToPoints(fVerb);
4000     if (pt == fPts[count]) {
4001         *t = 1;
4002     }
4003 }
4004
4005 bool SkOpSegment::reversePoints(const SkPoint& p1, const SkPoint& p2) const {
4006     SkASSERT(p1 != p2);
4007     int spanCount = count();
4008     int p1IndexMin = -1;
4009     int p2IndexMax = spanCount;
4010     for (int index = 0; index < spanCount; ++index) {
4011         const SkOpSpan& span = fTs[index];
4012         if (span.fPt == p1) {
4013             if (p1IndexMin < 0) {
4014                 p1IndexMin = index;
4015             }
4016         } else if (span.fPt == p2) {
4017             p2IndexMax = index;
4018         }
4019     }
4020     return p1IndexMin > p2IndexMax;
4021 }
4022
4023 void SkOpSegment::setCoincidentRange(const SkPoint& startPt, const SkPoint& endPt,
4024         SkOpSegment* other) {
4025     int count = this->count();
4026     for (int index = 0; index < count; ++index) {
4027         SkOpSpan &span = fTs[index];
4028         if ((startPt == span.fPt || endPt == span.fPt) && other == span.fOther) {
4029             span.fCoincident = true;
4030         }
4031     }
4032 }
4033
4034 void SkOpSegment::setUpWindings(int index, int endIndex, int* sumMiWinding, int* sumSuWinding,
4035         int* maxWinding, int* sumWinding, int* oppMaxWinding, int* oppSumWinding) {
4036     int deltaSum = spanSign(index, endIndex);
4037     int oppDeltaSum = oppSign(index, endIndex);
4038     if (operand()) {
4039         *maxWinding = *sumSuWinding;
4040         *sumWinding = *sumSuWinding -= deltaSum;
4041         *oppMaxWinding = *sumMiWinding;
4042         *oppSumWinding = *sumMiWinding -= oppDeltaSum;
4043     } else {
4044         *maxWinding = *sumMiWinding;
4045         *sumWinding = *sumMiWinding -= deltaSum;
4046         *oppMaxWinding = *sumSuWinding;
4047         *oppSumWinding = *sumSuWinding -= oppDeltaSum;
4048     }
4049 #if DEBUG_LIMIT_WIND_SUM
4050     SkASSERT(abs(*sumWinding) <= DEBUG_LIMIT_WIND_SUM);
4051     SkASSERT(abs(*oppSumWinding) <= DEBUG_LIMIT_WIND_SUM);
4052 #endif
4053 }
4054
4055 void SkOpSegment::setUpWindings(int index, int endIndex, int* sumMiWinding,
4056         int* maxWinding, int* sumWinding) {
4057     int deltaSum = spanSign(index, endIndex);
4058     *maxWinding = *sumMiWinding;
4059     *sumWinding = *sumMiWinding -= deltaSum;
4060 #if DEBUG_LIMIT_WIND_SUM
4061     SkASSERT(abs(*sumWinding) <= DEBUG_LIMIT_WIND_SUM);
4062 #endif
4063 }
4064
4065 void SkOpSegment::sortAngles() {
4066     int spanCount = fTs.count();
4067     if (spanCount <= 2) {
4068         return;
4069     }
4070     int index = 0;
4071     do {
4072         SkOpAngle* fromAngle = fTs[index].fFromAngle;
4073         SkOpAngle* toAngle = fTs[index].fToAngle;
4074         if (!fromAngle && !toAngle) {
4075             index += 1;
4076             continue;
4077         }
4078         SkOpAngle* baseAngle = NULL;
4079         if (fromAngle) {
4080             baseAngle = fromAngle;
4081             if (inLoop(baseAngle, spanCount, &index)) {
4082                 continue;
4083             }
4084         }
4085 #if DEBUG_ANGLE
4086         bool wroteAfterHeader = false;
4087 #endif
4088         if (toAngle) {
4089             if (!baseAngle) {
4090                 baseAngle = toAngle;
4091                 if (inLoop(baseAngle, spanCount, &index)) {
4092                     continue;
4093                 }
4094             } else {
4095                 SkDEBUGCODE(int newIndex = index);
4096                 SkASSERT(!inLoop(baseAngle, spanCount, &newIndex) && newIndex == index);
4097 #if DEBUG_ANGLE
4098                 SkDebugf("%s [%d] tStart=%1.9g [%d]\n", __FUNCTION__, debugID(), fTs[index].fT,
4099                         index);
4100                 wroteAfterHeader = true;
4101 #endif
4102                 baseAngle->insert(toAngle);
4103             }
4104         }
4105         SkOpAngle* nextFrom, * nextTo;
4106         int firstIndex = index;
4107         do {
4108             SkOpSpan& span = fTs[index];
4109             SkOpSegment* other = span.fOther;
4110             SkOpSpan& oSpan = other->fTs[span.fOtherIndex];
4111             SkOpAngle* oAngle = oSpan.fFromAngle;
4112             if (oAngle) {
4113 #if DEBUG_ANGLE
4114                 if (!wroteAfterHeader) {
4115                     SkDebugf("%s [%d] tStart=%1.9g [%d]\n", __FUNCTION__, debugID(), fTs[index].fT,
4116                             index);
4117                     wroteAfterHeader = true;
4118                 }
4119 #endif
4120                 if (!oAngle->loopContains(*baseAngle)) {
4121                     baseAngle->insert(oAngle);
4122                 }
4123             }
4124             oAngle = oSpan.fToAngle;
4125             if (oAngle) {
4126 #if DEBUG_ANGLE
4127                 if (!wroteAfterHeader) {
4128                     SkDebugf("%s [%d] tStart=%1.9g [%d]\n", __FUNCTION__, debugID(), fTs[index].fT,
4129                             index);
4130                     wroteAfterHeader = true;
4131                 }
4132 #endif
4133                 if (!oAngle->loopContains(*baseAngle)) {
4134                     baseAngle->insert(oAngle);
4135                 }
4136             }
4137             if (++index == spanCount) {
4138                 break;
4139             }
4140             nextFrom = fTs[index].fFromAngle;
4141             nextTo = fTs[index].fToAngle;
4142         } while (fromAngle == nextFrom && toAngle == nextTo);
4143         if (baseAngle && baseAngle->loopCount() == 1) {
4144             index = firstIndex;
4145             do {
4146                 SkOpSpan& span = fTs[index];
4147                 span.fFromAngle = span.fToAngle = NULL;
4148                 if (++index == spanCount) {
4149                     break;
4150                 }
4151                 nextFrom = fTs[index].fFromAngle;
4152                 nextTo = fTs[index].fToAngle;
4153             } while (fromAngle == nextFrom && toAngle == nextTo);
4154             baseAngle = NULL;
4155         }
4156 #if DEBUG_SORT
4157         SkASSERT(!baseAngle || baseAngle->loopCount() > 1);
4158 #endif
4159     } while (index < spanCount);
4160 }
4161
4162 // return true if midpoints were computed
4163 bool SkOpSegment::subDivide(int start, int end, SkPoint edge[4]) const {
4164     SkASSERT(start != end);
4165     edge[0] = fTs[start].fPt;
4166     int points = SkPathOpsVerbToPoints(fVerb);
4167     edge[points] = fTs[end].fPt;
4168     if (fVerb == SkPath::kLine_Verb) {
4169         return false;
4170     }
4171     double startT = fTs[start].fT;
4172     double endT = fTs[end].fT;
4173     if ((startT == 0 || endT == 0) && (startT == 1 || endT == 1)) {
4174         // don't compute midpoints if we already have them
4175         if (fVerb == SkPath::kQuad_Verb) {
4176             edge[1] = fPts[1];
4177             return false;
4178         }
4179         SkASSERT(fVerb == SkPath::kCubic_Verb);
4180         if (start < end) {
4181             edge[1] = fPts[1];
4182             edge[2] = fPts[2];
4183             return false;
4184         }
4185         edge[1] = fPts[2];
4186         edge[2] = fPts[1];
4187         return false;
4188     }
4189     const SkDPoint sub[2] = {{ edge[0].fX, edge[0].fY}, {edge[points].fX, edge[points].fY }};
4190     if (fVerb == SkPath::kQuad_Verb) {
4191         edge[1] = SkDQuad::SubDivide(fPts, sub[0], sub[1], startT, endT).asSkPoint();
4192     } else {
4193         SkASSERT(fVerb == SkPath::kCubic_Verb);
4194         SkDPoint ctrl[2];
4195         SkDCubic::SubDivide(fPts, sub[0], sub[1], startT, endT, ctrl);
4196         edge[1] = ctrl[0].asSkPoint();
4197         edge[2] = ctrl[1].asSkPoint();
4198     }
4199     return true;
4200 }
4201
4202 // return true if midpoints were computed
4203 bool SkOpSegment::subDivide(int start, int end, SkDCubic* result) const {
4204     SkASSERT(start != end);
4205     (*result)[0].set(fTs[start].fPt);
4206     int points = SkPathOpsVerbToPoints(fVerb);
4207     (*result)[points].set(fTs[end].fPt);
4208     if (fVerb == SkPath::kLine_Verb) {
4209         return false;
4210     }
4211     double startT = fTs[start].fT;
4212     double endT = fTs[end].fT;
4213     if ((startT == 0 || endT == 0) && (startT == 1 || endT == 1)) {
4214         // don't compute midpoints if we already have them
4215         if (fVerb == SkPath::kQuad_Verb) {
4216             (*result)[1].set(fPts[1]);
4217             return false;
4218         }
4219         SkASSERT(fVerb == SkPath::kCubic_Verb);
4220         if (start < end) {
4221             (*result)[1].set(fPts[1]);
4222             (*result)[2].set(fPts[2]);
4223             return false;
4224         }
4225         (*result)[1].set(fPts[2]);
4226         (*result)[2].set(fPts[1]);
4227         return false;
4228     }
4229     if (fVerb == SkPath::kQuad_Verb) {
4230         (*result)[1] = SkDQuad::SubDivide(fPts, (*result)[0], (*result)[2], startT, endT);
4231     } else {
4232         SkASSERT(fVerb == SkPath::kCubic_Verb);
4233         SkDCubic::SubDivide(fPts, (*result)[0], (*result)[3], startT, endT, &(*result)[1]);
4234     }
4235     return true;
4236 }
4237
4238 void SkOpSegment::subDivideBounds(int start, int end, SkPathOpsBounds* bounds) const {
4239     SkPoint edge[4];
4240     subDivide(start, end, edge);
4241     (bounds->*SetCurveBounds[SkPathOpsVerbToPoints(fVerb)])(edge);
4242 }
4243
4244 void SkOpSegment::TrackOutsidePair(SkTArray<SkPoint, true>* outsidePts, const SkPoint& endPt,
4245         const SkPoint& startPt) {
4246     int outCount = outsidePts->count();
4247     if (outCount == 0 || endPt != (*outsidePts)[outCount - 2]) {
4248         outsidePts->push_back(endPt);
4249         outsidePts->push_back(startPt);
4250     }
4251 }
4252
4253 void SkOpSegment::TrackOutside(SkTArray<SkPoint, true>* outsidePts, const SkPoint& startPt) {
4254     int outCount = outsidePts->count();
4255     if (outCount == 0 || startPt != (*outsidePts)[outCount - 1]) {
4256         outsidePts->push_back(startPt);
4257     }
4258 }
4259
4260 void SkOpSegment::undoneSpan(int* start, int* end) {
4261     int tCount = fTs.count();
4262     int index;
4263     for (index = 0; index < tCount; ++index) {
4264         if (!fTs[index].fDone) {
4265             break;
4266         }
4267     }
4268     SkASSERT(index < tCount - 1);
4269     *start = index;
4270     double startT = fTs[index].fT;
4271     while (approximately_negative(fTs[++index].fT - startT))
4272         SkASSERT(index < tCount);
4273     SkASSERT(index < tCount);
4274     *end = index;
4275 }
4276
4277 int SkOpSegment::updateOppWinding(int index, int endIndex) const {
4278     int lesser = SkMin32(index, endIndex);
4279     int oppWinding = oppSum(lesser);
4280     int oppSpanWinding = oppSign(index, endIndex);
4281     if (oppSpanWinding && UseInnerWinding(oppWinding - oppSpanWinding, oppWinding)
4282             && oppWinding != SK_MaxS32) {
4283         oppWinding -= oppSpanWinding;
4284     }
4285     return oppWinding;
4286 }
4287
4288 int SkOpSegment::updateOppWinding(const SkOpAngle* angle) const {
4289     int startIndex = angle->start();
4290     int endIndex = angle->end();
4291     return updateOppWinding(endIndex, startIndex);
4292 }
4293
4294 int SkOpSegment::updateOppWindingReverse(const SkOpAngle* angle) const {
4295     int startIndex = angle->start();
4296     int endIndex = angle->end();
4297     return updateOppWinding(startIndex, endIndex);
4298 }
4299
4300 int SkOpSegment::updateWinding(int index, int endIndex) const {
4301     int lesser = SkMin32(index, endIndex);
4302     int winding = windSum(lesser);
4303     if (winding == SK_MinS32) {
4304         return winding;
4305     }
4306     int spanWinding = spanSign(index, endIndex);
4307     if (winding && UseInnerWinding(winding - spanWinding, winding)
4308             && winding != SK_MaxS32) {
4309         winding -= spanWinding;
4310     }
4311     return winding;
4312 }
4313
4314 int SkOpSegment::updateWinding(const SkOpAngle* angle) const {
4315     int startIndex = angle->start();
4316     int endIndex = angle->end();
4317     return updateWinding(endIndex, startIndex);
4318 }
4319
4320 int SkOpSegment::updateWindingReverse(int index, int endIndex) const {
4321     int lesser = SkMin32(index, endIndex);
4322     int winding = windSum(lesser);
4323     int spanWinding = spanSign(endIndex, index);
4324     if (winding && UseInnerWindingReverse(winding - spanWinding, winding)
4325             && winding != SK_MaxS32) {
4326         winding -= spanWinding;
4327     }
4328     return winding;
4329 }
4330
4331 int SkOpSegment::updateWindingReverse(const SkOpAngle* angle) const {
4332     int startIndex = angle->start();
4333     int endIndex = angle->end();
4334     return updateWindingReverse(endIndex, startIndex);
4335 }
4336
4337 // OPTIMIZATION: does the following also work, and is it any faster?
4338 // return outerWinding * innerWinding > 0
4339 //      || ((outerWinding + innerWinding < 0) ^ ((outerWinding - innerWinding) < 0)))
4340 bool SkOpSegment::UseInnerWinding(int outerWinding, int innerWinding) {
4341     SkASSERT(outerWinding != SK_MaxS32);
4342     SkASSERT(innerWinding != SK_MaxS32);
4343     int absOut = abs(outerWinding);
4344     int absIn = abs(innerWinding);
4345     bool result = absOut == absIn ? outerWinding < 0 : absOut < absIn;
4346     return result;
4347 }
4348
4349 bool SkOpSegment::UseInnerWindingReverse(int outerWinding, int innerWinding) {
4350     SkASSERT(outerWinding != SK_MaxS32);
4351     SkASSERT(innerWinding != SK_MaxS32);
4352     int absOut = abs(outerWinding);
4353     int absIn = abs(innerWinding);
4354     bool result = absOut == absIn ? true : absOut < absIn;
4355     return result;
4356 }
4357
4358 int SkOpSegment::windingAtT(double tHit, int tIndex, bool crossOpp, SkScalar* dx) const {
4359     if (approximately_zero(tHit - t(tIndex))) {  // if we hit the end of a span, disregard
4360         return SK_MinS32;
4361     }
4362     int winding = crossOpp ? oppSum(tIndex) : windSum(tIndex);
4363     SkASSERT(winding != SK_MinS32);
4364     int windVal = crossOpp ? oppValue(tIndex) : windValue(tIndex);
4365 #if DEBUG_WINDING_AT_T
4366     SkDebugf("%s id=%d opp=%d tHit=%1.9g t=%1.9g oldWinding=%d windValue=%d", __FUNCTION__,
4367             debugID(), crossOpp, tHit, t(tIndex), winding, windVal);
4368 #endif
4369     // see if a + change in T results in a +/- change in X (compute x'(T))
4370     *dx = (*CurveSlopeAtT[SkPathOpsVerbToPoints(fVerb)])(fPts, tHit).fX;
4371     if (fVerb > SkPath::kLine_Verb && approximately_zero(*dx)) {
4372         *dx = fPts[2].fX - fPts[1].fX - *dx;
4373     }
4374     if (*dx == 0) {
4375 #if DEBUG_WINDING_AT_T
4376         SkDebugf(" dx=0 winding=SK_MinS32\n");
4377 #endif
4378         return SK_MinS32;
4379     }
4380     if (windVal < 0) {  // reverse sign if opp contour traveled in reverse
4381             *dx = -*dx;
4382     }
4383     if (winding * *dx > 0) {  // if same signs, result is negative
4384         winding += *dx > 0 ? -windVal : windVal;
4385     }
4386 #if DEBUG_WINDING_AT_T
4387     SkDebugf(" dx=%c winding=%d\n", *dx > 0 ? '+' : '-', winding);
4388 #endif
4389     return winding;
4390 }
4391
4392 int SkOpSegment::windSum(const SkOpAngle* angle) const {
4393     int start = angle->start();
4394     int end = angle->end();
4395     int index = SkMin32(start, end);
4396     return windSum(index);
4397 }
4398
4399 void SkOpSegment::zeroSpan(SkOpSpan* span) {
4400     SkASSERT(span->fWindValue > 0 || span->fOppValue != 0);
4401     span->fWindValue = 0;
4402     span->fOppValue = 0;
4403     if (span->fTiny || span->fSmall) {
4404         return;
4405     }
4406     SkASSERT(!span->fDone);
4407     span->fDone = true;
4408     ++fDoneSpans;
4409 }