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