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