src/third_party/skia/src/pathops/SkOpContour.cpp

   1 /*
   2 * Copyright 2013 Google Inc.
   3 *
   4 * Use of this source code is governed by a BSD-style license that can be
   5 * found in the LICENSE file.
   6 */
   7 #include "SkIntersections.h"
   8 #include "SkOpContour.h"
   9 #include "SkPathWriter.h"
  10 #include "SkTSort.h"
  11
  12 bool SkOpContour::addCoincident(int index, SkOpContour* other, int otherIndex,
  13         const SkIntersections& ts, bool swap) {
  14     SkPoint pt0 = ts.pt(0).asSkPoint();
  15     SkPoint pt1 = ts.pt(1).asSkPoint();
  16     if (pt0 == pt1) {
  17         // FIXME: one could imagine a case where it would be incorrect to ignore this
  18         // suppose two self-intersecting cubics overlap to be coincident --
  19         // this needs to check that by some measure the t values are far enough apart
  20         // or needs to check to see if the self-intersection bit was set on the cubic segment
  21         return false;
  22     }
  23     SkCoincidence& coincidence = fCoincidences.push_back();
  24     coincidence.fOther = other;
  25     coincidence.fSegments[0] = index;
  26     coincidence.fSegments[1] = otherIndex;
  27     coincidence.fTs[swap][0] = ts[0][0];
  28     coincidence.fTs[swap][1] = ts[0][1];
  29     coincidence.fTs[!swap][0] = ts[1][0];
  30     coincidence.fTs[!swap][1] = ts[1][1];
  31     coincidence.fPts[swap][0] = pt0;
  32     coincidence.fPts[swap][1] = pt1;
  33     bool nearStart = ts.nearlySame(0);
  34     bool nearEnd = ts.nearlySame(1);
  35     coincidence.fPts[!swap][0] = nearStart ? ts.pt2(0).asSkPoint() : pt0;
  36     coincidence.fPts[!swap][1] = nearEnd ? ts.pt2(1).asSkPoint() : pt1;
  37     coincidence.fNearly[0] = nearStart;
  38     coincidence.fNearly[1] = nearEnd;
  39     return true;
  40 }
  41
  42 SkOpSegment* SkOpContour::nonVerticalSegment(int* start, int* end) {
  43     int segmentCount = fSortedSegments.count();
  44     SkASSERT(segmentCount > 0);
  45     for (int sortedIndex = fFirstSorted; sortedIndex < segmentCount; ++sortedIndex) {
  46         SkOpSegment* testSegment = fSortedSegments[sortedIndex];
  47         if (testSegment->done()) {
  48             continue;
  49         }
  50         *start = *end = 0;
  51         while (testSegment->nextCandidate(start, end)) {
  52             if (!testSegment->isVertical(*start, *end)) {
  53                 return testSegment;
  54             }
  55         }
  56     }
  57     return NULL;
  58 }
  59
  60 // first pass, add missing T values
  61 // second pass, determine winding values of overlaps
  62 void SkOpContour::addCoincidentPoints() {
  63     int count = fCoincidences.count();
  64     for (int index = 0; index < count; ++index) {
  65         SkCoincidence& coincidence = fCoincidences[index];
  66         int thisIndex = coincidence.fSegments[0];
  67         SkOpSegment& thisOne = fSegments[thisIndex];
  68         SkOpContour* otherContour = coincidence.fOther;
  69         int otherIndex = coincidence.fSegments[1];
  70         SkOpSegment& other = otherContour->fSegments[otherIndex];
  71         if ((thisOne.done() || other.done()) && thisOne.complete() && other.complete()) {
  72             // OPTIMIZATION: remove from array
  73             continue;
  74         }
  75     #if DEBUG_CONCIDENT
  76         thisOne.debugShowTs("-");
  77         other.debugShowTs("o");
  78     #endif
  79         double startT = coincidence.fTs[0][0];
  80         double endT = coincidence.fTs[0][1];
  81         bool startSwapped, oStartSwapped, cancelers;
  82         if ((cancelers = startSwapped = startT > endT)) {
  83             SkTSwap(startT, endT);
  84         }
  85         if (startT == endT) { // if one is very large the smaller may have collapsed to nothing
  86             if (endT <= 1 - FLT_EPSILON) {
  87                 endT += FLT_EPSILON;
  88                 SkASSERT(endT <= 1);
  89             } else {
  90                 startT -= FLT_EPSILON;
  91                 SkASSERT(startT >= 0);
  92             }
  93         }
  94         SkASSERT(!approximately_negative(endT - startT));
  95         double oStartT = coincidence.fTs[1][0];
  96         double oEndT = coincidence.fTs[1][1];
  97         if ((oStartSwapped = oStartT > oEndT)) {
  98             SkTSwap(oStartT, oEndT);
  99             cancelers ^= true;
 100         }
 101         SkASSERT(!approximately_negative(oEndT - oStartT));
 102         const SkPoint& startPt = coincidence.fPts[0][startSwapped];
 103         if (cancelers) {
 104             // make sure startT and endT have t entries
 105             if (startT > 0 || oEndT < 1
 106                     || thisOne.isMissing(startT, startPt) || other.isMissing(oEndT, startPt)) {
 107                 thisOne.addTPair(startT, &other, oEndT, true, startPt,
 108                         coincidence.fPts[1][startSwapped]);
 109             }
 110             const SkPoint& oStartPt = coincidence.fPts[1][oStartSwapped];
 111             if (oStartT > 0 || endT < 1
 112                     || thisOne.isMissing(endT, oStartPt) || other.isMissing(oStartT, oStartPt)) {
 113                 other.addTPair(oStartT, &thisOne, endT, true, oStartPt,
 114                         coincidence.fPts[0][oStartSwapped]);
 115             }
 116         } else {
 117             if (startT > 0 || oStartT > 0
 118                     || thisOne.isMissing(startT, startPt) || other.isMissing(oStartT, startPt)) {
 119                 thisOne.addTPair(startT, &other, oStartT, true, startPt,
 120                         coincidence.fPts[1][startSwapped]);
 121             }
 122             const SkPoint& oEndPt = coincidence.fPts[1][!oStartSwapped];
 123             if (endT < 1 || oEndT < 1
 124                     || thisOne.isMissing(endT, oEndPt) || other.isMissing(oEndT, oEndPt)) {
 125                 other.addTPair(oEndT, &thisOne, endT, true, oEndPt,
 126                         coincidence.fPts[0][!oStartSwapped]);
 127             }
 128         }
 129     #if DEBUG_CONCIDENT
 130         thisOne.debugShowTs("+");
 131         other.debugShowTs("o");
 132     #endif
 133     }
 134     // if there are multiple pairs of coincidence that share an edge, see if the opposite
 135     // are also coincident
 136     for (int index = 0; index < count - 1; ++index) {
 137         const SkCoincidence& coincidence = fCoincidences[index];
 138         int thisIndex = coincidence.fSegments[0];
 139         SkOpContour* otherContour = coincidence.fOther;
 140         int otherIndex = coincidence.fSegments[1];
 141         for (int idx2 = 1; idx2 < count; ++idx2) {
 142             const SkCoincidence& innerCoin = fCoincidences[idx2];
 143             int innerThisIndex = innerCoin.fSegments[0];
 144             if (thisIndex == innerThisIndex) {
 145                 checkCoincidentPair(coincidence, 1, innerCoin, 1, false);
 146             }
 147             if (this == otherContour && otherIndex == innerThisIndex) {
 148                 checkCoincidentPair(coincidence, 0, innerCoin, 1, false);
 149             }
 150             SkOpContour* innerOtherContour = innerCoin.fOther;
 151             innerThisIndex = innerCoin.fSegments[1];
 152             if (this == innerOtherContour && thisIndex == innerThisIndex) {
 153                 checkCoincidentPair(coincidence, 1, innerCoin, 0, false);
 154             }
 155             if (otherContour == innerOtherContour && otherIndex == innerThisIndex) {
 156                 checkCoincidentPair(coincidence, 0, innerCoin, 0, false);
 157             }
 158         }
 159     }
 160 }
 161
 162 bool SkOpContour::addPartialCoincident(int index, SkOpContour* other, int otherIndex,
 163         const SkIntersections& ts, int ptIndex, bool swap) {
 164     SkPoint pt0 = ts.pt(ptIndex).asSkPoint();
 165     SkPoint pt1 = ts.pt(ptIndex + 1).asSkPoint();
 166     if (SkDPoint::ApproximatelyEqual(pt0, pt1)) {
 167         // FIXME: one could imagine a case where it would be incorrect to ignore this
 168         // suppose two self-intersecting cubics overlap to form a partial coincidence --
 169         // although it isn't clear why the regular coincidence could wouldn't pick this up
 170         // this is exceptional enough to ignore for now
 171         return false;
 172     }
 173     SkCoincidence& coincidence = fPartialCoincidences.push_back();
 174     coincidence.fOther = other;
 175     coincidence.fSegments[0] = index;
 176     coincidence.fSegments[1] = otherIndex;
 177     coincidence.fTs[swap][0] = ts[0][ptIndex];
 178     coincidence.fTs[swap][1] = ts[0][ptIndex + 1];
 179     coincidence.fTs[!swap][0] = ts[1][ptIndex];
 180     coincidence.fTs[!swap][1] = ts[1][ptIndex + 1];
 181     coincidence.fPts[0][0] = coincidence.fPts[1][0] = pt0;
 182     coincidence.fPts[0][1] = coincidence.fPts[1][1] = pt1;
 183     coincidence.fNearly[0] = 0;
 184     coincidence.fNearly[1] = 0;
 185     return true;
 186 }
 187
 188 void SkOpContour::align(const SkOpSegment::AlignedSpan& aligned, bool swap,
 189         SkCoincidence* coincidence) {
 190     for (int idx2 = 0; idx2 < 2; ++idx2) {
 191         if (coincidence->fPts[0][idx2] == aligned.fOldPt
 192                 && coincidence->fTs[swap][idx2] == aligned.fOldT) {
 193             SkASSERT(SkDPoint::RoughlyEqual(coincidence->fPts[0][idx2], aligned.fPt));
 194             coincidence->fPts[0][idx2] = aligned.fPt;
 195             SkASSERT(way_roughly_equal(coincidence->fTs[swap][idx2], aligned.fT));
 196             coincidence->fTs[swap][idx2] = aligned.fT;
 197         }
 198     }
 199 }
 200
 201 void SkOpContour::alignCoincidence(const SkOpSegment::AlignedSpan& aligned,
 202         SkTArray<SkCoincidence, true>* coincidences) {
 203     int count = coincidences->count();
 204     for (int index = 0; index < count; ++index) {
 205         SkCoincidence& coincidence = (*coincidences)[index];
 206         int thisIndex = coincidence.fSegments[0];
 207         const SkOpSegment* thisOne = &fSegments[thisIndex];
 208         const SkOpContour* otherContour = coincidence.fOther;
 209         int otherIndex = coincidence.fSegments[1];
 210         const SkOpSegment* other = &otherContour->fSegments[otherIndex];
 211         if (thisOne == aligned.fOther1 && other == aligned.fOther2) {
 212             align(aligned, false, &coincidence);
 213         } else if (thisOne == aligned.fOther2 && other == aligned.fOther1) {
 214             align(aligned, true, &coincidence);
 215         }
 216     }
 217 }
 218
 219 void SkOpContour::alignTPt(int segmentIndex, const SkOpContour* other, int otherIndex,
 220         bool swap, int tIndex, SkIntersections* ts, SkPoint* point) const {
 221     int zeroPt;
 222     if ((zeroPt = alignT(swap, tIndex, ts)) >= 0) {
 223         alignPt(segmentIndex, point, zeroPt);
 224     }
 225     if ((zeroPt = other->alignT(!swap, tIndex, ts)) >= 0) {
 226         other->alignPt(otherIndex, point, zeroPt);
 227     }
 228 }
 229
 230 void SkOpContour::alignPt(int index, SkPoint* point, int zeroPt) const {
 231     const SkOpSegment& segment = fSegments[index];
 232     if (0 == zeroPt) {
 233         *point = segment.pts()[0];
 234     } else {
 235         *point = segment.pts()[SkPathOpsVerbToPoints(segment.verb())];
 236     }
 237 }
 238
 239 int SkOpContour::alignT(bool swap, int tIndex, SkIntersections* ts) const {
 240     double tVal = (*ts)[swap][tIndex];
 241     if (tVal != 0 && precisely_zero(tVal)) {
 242         ts->set(swap, tIndex, 0);
 243         return 0;
 244     }
 245      if (tVal != 1 && precisely_equal(tVal, 1)) {
 246         ts->set(swap, tIndex, 1);
 247         return 1;
 248     }
 249     return -1;
 250 }
 251
 252 bool SkOpContour::calcAngles() {
 253     int segmentCount = fSegments.count();
 254     for (int test = 0; test < segmentCount; ++test) {
 255         if (!fSegments[test].calcAngles()) {
 256             return false;
 257         }
 258     }
 259     return true;
 260 }
 261
 262 void SkOpContour::calcCoincidentWinding() {
 263     int count = fCoincidences.count();
 264 #if DEBUG_CONCIDENT
 265     if (count > 0) {
 266         SkDebugf("%s count=%d\n", __FUNCTION__, count);
 267     }
 268 #endif
 269     for (int index = 0; index < count; ++index) {
 270         SkCoincidence& coincidence = fCoincidences[index];
 271          calcCommonCoincidentWinding(coincidence);
 272     }
 273 }
 274
 275 void SkOpContour::calcPartialCoincidentWinding() {
 276     int count = fPartialCoincidences.count();
 277 #if DEBUG_CONCIDENT
 278     if (count > 0) {
 279         SkDebugf("%s count=%d\n", __FUNCTION__, count);
 280     }
 281 #endif
 282     for (int index = 0; index < count; ++index) {
 283         SkCoincidence& coincidence = fPartialCoincidences[index];
 284         calcCommonCoincidentWinding(coincidence);
 285     }
 286     // if there are multiple pairs of partial coincidence that share an edge, see if the opposite
 287     // are also coincident
 288     for (int index = 0; index < count - 1; ++index) {
 289         const SkCoincidence& coincidence = fPartialCoincidences[index];
 290         int thisIndex = coincidence.fSegments[0];
 291         SkOpContour* otherContour = coincidence.fOther;
 292         int otherIndex = coincidence.fSegments[1];
 293         for (int idx2 = 1; idx2 < count; ++idx2) {
 294             const SkCoincidence& innerCoin = fPartialCoincidences[idx2];
 295             int innerThisIndex = innerCoin.fSegments[0];
 296             if (thisIndex == innerThisIndex) {
 297                 checkCoincidentPair(coincidence, 1, innerCoin, 1, true);
 298             }
 299             if (this == otherContour && otherIndex == innerThisIndex) {
 300                 checkCoincidentPair(coincidence, 0, innerCoin, 1, true);
 301             }
 302             SkOpContour* innerOtherContour = innerCoin.fOther;
 303             innerThisIndex = innerCoin.fSegments[1];
 304             if (this == innerOtherContour && thisIndex == innerThisIndex) {
 305                 checkCoincidentPair(coincidence, 1, innerCoin, 0, true);
 306             }
 307             if (otherContour == innerOtherContour && otherIndex == innerThisIndex) {
 308                 checkCoincidentPair(coincidence, 0, innerCoin, 0, true);
 309             }
 310         }
 311     }
 312 }
 313
 314 void SkOpContour::checkCoincidentPair(const SkCoincidence& oneCoin, int oneIdx,
 315         const SkCoincidence& twoCoin, int twoIdx, bool partial) {
 316     SkASSERT((oneIdx ? this : oneCoin.fOther) == (twoIdx ? this : twoCoin.fOther));
 317     SkASSERT(oneCoin.fSegments[!oneIdx] == twoCoin.fSegments[!twoIdx]);
 318     // look for common overlap
 319     double min = SK_ScalarMax;
 320     double max = SK_ScalarMin;
 321     double min1 = oneCoin.fTs[!oneIdx][0];
 322     double max1 = oneCoin.fTs[!oneIdx][1];
 323     double min2 = twoCoin.fTs[!twoIdx][0];
 324     double max2 = twoCoin.fTs[!twoIdx][1];
 325     bool cancelers = (min1 < max1) != (min2 < max2);
 326     if (min1 > max1) {
 327         SkTSwap(min1, max1);
 328     }
 329     if (min2 > max2) {
 330         SkTSwap(min2, max2);
 331     }
 332     if (between(min1, min2, max1)) {
 333         min = min2;
 334     }
 335     if (between(min1, max2, max1)) {
 336         max = max2;
 337     }
 338     if (between(min2, min1, max2)) {
 339         min = SkTMin(min, min1);
 340     }
 341     if (between(min2, max1, max2)) {
 342         max = SkTMax(max, max1);
 343     }
 344     if (min >= max) {
 345         return;  // no overlap
 346     }
 347     // look to see if opposite are different segments
 348     int seg1Index = oneCoin.fSegments[oneIdx];
 349     int seg2Index = twoCoin.fSegments[twoIdx];
 350     if (seg1Index == seg2Index) {
 351         return;
 352     }
 353     SkOpContour* contour1 = oneIdx ? oneCoin.fOther : this;
 354     SkOpContour* contour2 = twoIdx ? twoCoin.fOther : this;
 355     SkOpSegment* segment1 = &contour1->fSegments[seg1Index];
 356     SkOpSegment* segment2 = &contour2->fSegments[seg2Index];
 357     // find opposite t value ranges corresponding to reference min/max range
 358     const SkOpContour* refContour = oneIdx ? this : oneCoin.fOther;
 359     const int refSegIndex = oneCoin.fSegments[!oneIdx];
 360     const SkOpSegment* refSegment = &refContour->fSegments[refSegIndex];
 361     int seg1Start = segment1->findOtherT(min, refSegment);
 362     int seg1End = segment1->findOtherT(max, refSegment);
 363     int seg2Start = segment2->findOtherT(min, refSegment);
 364     int seg2End = segment2->findOtherT(max, refSegment);
 365     // if the opposite pairs already contain min/max, we're done
 366     if (seg1Start >= 0 && seg1End >= 0 && seg2Start >= 0 && seg2End >= 0) {
 367         return;
 368     }
 369     double loEnd = SkTMin(min1, min2);
 370     double hiEnd = SkTMax(max1, max2);
 371     // insert the missing coincident point(s)
 372     double missingT1 = -1;
 373     double otherT1 = -1;
 374     if (seg1Start < 0) {
 375         if (seg2Start < 0) {
 376             return;
 377         }
 378         missingT1 = segment1->calcMissingTStart(refSegment, loEnd, min, max, hiEnd,
 379                 segment2, seg1End);
 380         if (missingT1 < 0) {
 381             return;
 382         }
 383         const SkOpSpan* missingSpan = &segment2->span(seg2Start);
 384         otherT1 = missingSpan->fT;
 385     } else if (seg2Start < 0) {
 386         SkASSERT(seg1Start >= 0);
 387         missingT1 = segment2->calcMissingTStart(refSegment, loEnd, min, max, hiEnd,
 388                 segment1, seg2End);
 389         if (missingT1 < 0) {
 390             return;
 391         }
 392         const SkOpSpan* missingSpan = &segment1->span(seg1Start);
 393         otherT1 = missingSpan->fT;
 394     }
 395     SkPoint missingPt1;
 396     SkOpSegment* addTo1 = NULL;
 397     SkOpSegment* addOther1 = seg1Start < 0 ? segment2 : segment1;
 398     int minTIndex = refSegment->findExactT(min, addOther1);
 399     SkASSERT(minTIndex >= 0);
 400     if (missingT1 >= 0) {
 401         missingPt1 = refSegment->span(minTIndex).fPt;
 402         addTo1 = seg1Start < 0 ? segment1 : segment2;
 403     }
 404     double missingT2 = -1;
 405     double otherT2 = -1;
 406     if (seg1End < 0) {
 407         if (seg2End < 0) {
 408             return;
 409         }
 410         missingT2 = segment1->calcMissingTEnd(refSegment, loEnd, min, max, hiEnd,
 411                 segment2, seg1Start);
 412         if (missingT2 < 0) {
 413             return;
 414         }
 415         const SkOpSpan* missingSpan = &segment2->span(seg2End);
 416         otherT2 = missingSpan->fT;
 417     } else if (seg2End < 0) {
 418         SkASSERT(seg1End >= 0);
 419         missingT2 = segment2->calcMissingTEnd(refSegment, loEnd, min, max, hiEnd,
 420                 segment1, seg2Start);
 421         if (missingT2 < 0) {
 422             return;
 423         }
 424         const SkOpSpan* missingSpan = &segment1->span(seg1End);
 425         otherT2 = missingSpan->fT;
 426     }
 427     SkPoint missingPt2;
 428     SkOpSegment* addTo2 = NULL;
 429     SkOpSegment* addOther2 = seg1End < 0 ? segment2 : segment1;
 430     int maxTIndex = refSegment->findExactT(max, addOther2);
 431     SkASSERT(maxTIndex >= 0);
 432     if (missingT2 >= 0) {
 433         missingPt2 = refSegment->span(maxTIndex).fPt;
 434         addTo2 = seg1End < 0 ? segment1 : segment2;
 435     }
 436     if (missingT1 >= 0) {
 437         addTo1->pinT(missingPt1, &missingT1);
 438         addTo1->addTPair(missingT1, addOther1, otherT1, false, missingPt1);
 439     } else {
 440         SkASSERT(minTIndex >= 0);
 441         missingPt1 = refSegment->span(minTIndex).fPt;
 442     }
 443     if (missingT2 >= 0) {
 444         addTo2->pinT(missingPt2, &missingT2);
 445         addTo2->addTPair(missingT2, addOther2, otherT2, false, missingPt2);
 446     } else {
 447         SkASSERT(minTIndex >= 0);
 448         missingPt2 = refSegment->span(maxTIndex).fPt;
 449     }
 450     if (!partial) {
 451         return;
 452     }
 453     if (cancelers) {
 454         if (missingT1 >= 0) {
 455             if (addTo1->reversePoints(missingPt1, missingPt2)) {
 456                 SkTSwap(missingPt1, missingPt2);
 457             }
 458             addTo1->addTCancel(missingPt1, missingPt2, addOther1);
 459         } else {
 460             if (addTo2->reversePoints(missingPt1, missingPt2)) {
 461                 SkTSwap(missingPt1, missingPt2);
 462             }
 463             addTo2->addTCancel(missingPt1, missingPt2, addOther2);
 464         }
 465     } else if (missingT1 >= 0) {
 466         addTo1->addTCoincident(missingPt1, missingPt2, addTo1 == addTo2 ? missingT2 : otherT2,
 467                 addOther1);
 468     } else {
 469         addTo2->addTCoincident(missingPt2, missingPt1, addTo2 == addTo1 ? missingT1 : otherT1,
 470                 addOther2);
 471     }
 472 }
 473
 474 void SkOpContour::joinCoincidence(const SkTArray<SkCoincidence, true>& coincidences, bool partial) {
 475     int count = coincidences.count();
 476 #if DEBUG_CONCIDENT
 477     if (count > 0) {
 478         SkDebugf("%s count=%d\n", __FUNCTION__, count);
 479     }
 480 #endif
 481     // look for a lineup where the partial implies another adjoining coincidence
 482     for (int index = 0; index < count; ++index) {
 483         const SkCoincidence& coincidence = coincidences[index];
 484         int thisIndex = coincidence.fSegments[0];
 485         SkOpSegment& thisOne = fSegments[thisIndex];
 486         if (thisOne.done()) {
 487             continue;
 488         }
 489         SkOpContour* otherContour = coincidence.fOther;
 490         int otherIndex = coincidence.fSegments[1];
 491         SkOpSegment& other = otherContour->fSegments[otherIndex];
 492         if (other.done()) {
 493             continue;
 494         }
 495         double startT = coincidence.fTs[0][0];
 496         double endT = coincidence.fTs[0][1];
 497         if (startT == endT) {  // this can happen in very large compares
 498             continue;
 499         }
 500         double oStartT = coincidence.fTs[1][0];
 501         double oEndT = coincidence.fTs[1][1];
 502         if (oStartT == oEndT) {
 503             continue;
 504         }
 505         bool swapStart = startT > endT;
 506         bool swapOther = oStartT > oEndT;
 507         const SkPoint* startPt = &coincidence.fPts[0][0];
 508         const SkPoint* endPt = &coincidence.fPts[0][1];
 509         if (swapStart) {
 510             SkTSwap(startT, endT);
 511             SkTSwap(oStartT, oEndT);
 512             SkTSwap(startPt, endPt);
 513         }
 514         bool cancel = swapOther != swapStart;
 515         int step = swapStart ? -1 : 1;
 516         int oStep = swapOther ? -1 : 1;
 517         double oMatchStart = cancel ? oEndT : oStartT;
 518         if (partial ? startT != 0 || oMatchStart != 0 : (startT == 0) != (oMatchStart == 0)) {
 519             bool added = false;
 520             if (oMatchStart != 0) {
 521                 const SkPoint& oMatchStartPt = cancel ? *endPt : *startPt;
 522                 added = thisOne.joinCoincidence(&other, oMatchStart, oMatchStartPt, oStep, cancel);
 523             }
 524             if (!cancel && startT != 0 && !added) {
 525                 (void) other.joinCoincidence(&thisOne, startT, *startPt, step, cancel);
 526             }
 527         }
 528         double oMatchEnd = cancel ? oStartT : oEndT;
 529         if (partial ? endT != 1 || oMatchEnd != 1 : (endT == 1) != (oMatchEnd == 1)) {
 530             bool added = false;
 531             if (cancel && endT != 1 && !added) {
 532                 (void) other.joinCoincidence(&thisOne, endT, *endPt, -step, cancel);
 533             }
 534         }
 535     }
 536 }
 537
 538 void SkOpContour::calcCommonCoincidentWinding(const SkCoincidence& coincidence) {
 539     if (coincidence.fNearly[0] && coincidence.fNearly[1]) {
 540         return;
 541     }
 542     int thisIndex = coincidence.fSegments[0];
 543     SkOpSegment& thisOne = fSegments[thisIndex];
 544     if (thisOne.done()) {
 545         return;
 546     }
 547     SkOpContour* otherContour = coincidence.fOther;
 548     int otherIndex = coincidence.fSegments[1];
 549     SkOpSegment& other = otherContour->fSegments[otherIndex];
 550     if (other.done()) {
 551         return;
 552     }
 553     double startT = coincidence.fTs[0][0];
 554     double endT = coincidence.fTs[0][1];
 555     const SkPoint* startPt = &coincidence.fPts[0][0];
 556     const SkPoint* endPt = &coincidence.fPts[0][1];
 557     bool cancelers;
 558     if ((cancelers = startT > endT)) {
 559         SkTSwap<double>(startT, endT);
 560         SkTSwap<const SkPoint*>(startPt, endPt);
 561     }
 562     if (startT == endT) { // if span is very large, the smaller may have collapsed to nothing
 563         if (endT <= 1 - FLT_EPSILON) {
 564             endT += FLT_EPSILON;
 565             SkASSERT(endT <= 1);
 566         } else {
 567             startT -= FLT_EPSILON;
 568             SkASSERT(startT >= 0);
 569         }
 570     }
 571     SkASSERT(!approximately_negative(endT - startT));
 572     double oStartT = coincidence.fTs[1][0];
 573     double oEndT = coincidence.fTs[1][1];
 574     if (oStartT > oEndT) {
 575         SkTSwap<double>(oStartT, oEndT);
 576         cancelers ^= true;
 577     }
 578     SkASSERT(!approximately_negative(oEndT - oStartT));
 579     if (cancelers) {
 580         thisOne.addTCancel(*startPt, *endPt, &other);
 581     } else {
 582         thisOne.addTCoincident(*startPt, *endPt, endT, &other);
 583     }
 584 #if DEBUG_CONCIDENT
 585     thisOne.debugShowTs("p");
 586     other.debugShowTs("o");
 587 #endif
 588 }
 589
 590 void SkOpContour::resolveNearCoincidence() {
 591     int count = fCoincidences.count();
 592     for (int index = 0; index < count; ++index) {
 593         SkCoincidence& coincidence = fCoincidences[index];
 594         if (!coincidence.fNearly[0] || !coincidence.fNearly[1]) {
 595             continue;
 596         }
 597         int thisIndex = coincidence.fSegments[0];
 598         SkOpSegment& thisOne = fSegments[thisIndex];
 599         SkOpContour* otherContour = coincidence.fOther;
 600         int otherIndex = coincidence.fSegments[1];
 601         SkOpSegment& other = otherContour->fSegments[otherIndex];
 602         if ((thisOne.done() || other.done()) && thisOne.complete() && other.complete()) {
 603             // OPTIMIZATION: remove from coincidence array
 604             continue;
 605         }
 606     #if DEBUG_CONCIDENT
 607         thisOne.debugShowTs("-");
 608         other.debugShowTs("o");
 609     #endif
 610         double startT = coincidence.fTs[0][0];
 611         double endT = coincidence.fTs[0][1];
 612         bool cancelers;
 613         if ((cancelers = startT > endT)) {
 614             SkTSwap<double>(startT, endT);
 615         }
 616         if (startT == endT) { // if span is very large, the smaller may have collapsed to nothing
 617             if (endT <= 1 - FLT_EPSILON) {
 618                 endT += FLT_EPSILON;
 619                 SkASSERT(endT <= 1);
 620             } else {
 621                 startT -= FLT_EPSILON;
 622                 SkASSERT(startT >= 0);
 623             }
 624         }
 625         SkASSERT(!approximately_negative(endT - startT));
 626         double oStartT = coincidence.fTs[1][0];
 627         double oEndT = coincidence.fTs[1][1];
 628         if (oStartT > oEndT) {
 629             SkTSwap<double>(oStartT, oEndT);
 630             cancelers ^= true;
 631         }
 632         SkASSERT(!approximately_negative(oEndT - oStartT));
 633         if (cancelers) {
 634             thisOne.blindCancel(coincidence, &other);
 635         } else {
 636             thisOne.blindCoincident(coincidence, &other);
 637         }
 638     }
 639 }
 640
 641 void SkOpContour::sortAngles() {
 642     int segmentCount = fSegments.count();
 643     for (int test = 0; test < segmentCount; ++test) {
 644         fSegments[test].sortAngles();
 645     }
 646 }
 647
 648 void SkOpContour::sortSegments() {
 649     int segmentCount = fSegments.count();
 650     fSortedSegments.push_back_n(segmentCount);
 651     for (int test = 0; test < segmentCount; ++test) {
 652         fSortedSegments[test] = &fSegments[test];
 653     }
 654     SkTQSort<SkOpSegment>(fSortedSegments.begin(), fSortedSegments.end() - 1);
 655     fFirstSorted = 0;
 656 }
 657
 658 void SkOpContour::toPath(SkPathWriter* path) const {
 659     int segmentCount = fSegments.count();
 660     const SkPoint& pt = fSegments.front().pts()[0];
 661     path->deferredMove(pt);
 662     for (int test = 0; test < segmentCount; ++test) {
 663         fSegments[test].addCurveTo(0, 1, path, true);
 664     }
 665     path->close();
 666 }
 667
 668 void SkOpContour::topSortableSegment(const SkPoint& topLeft, SkPoint* bestXY,
 669         SkOpSegment** topStart) {
 670     int segmentCount = fSortedSegments.count();
 671     SkASSERT(segmentCount > 0);
 672     int sortedIndex = fFirstSorted;
 673     fDone = true;  // may be cleared below
 674     for ( ; sortedIndex < segmentCount; ++sortedIndex) {
 675         SkOpSegment* testSegment = fSortedSegments[sortedIndex];
 676         if (testSegment->done()) {
 677             if (sortedIndex == fFirstSorted) {
 678                 ++fFirstSorted;
 679             }
 680             continue;
 681         }
 682         fDone = false;
 683         SkPoint testXY = testSegment->activeLeftTop(NULL);
 684         if (*topStart) {
 685             if (testXY.fY < topLeft.fY) {
 686                 continue;
 687             }
 688             if (testXY.fY == topLeft.fY && testXY.fX < topLeft.fX) {
 689                 continue;
 690             }
 691             if (bestXY->fY < testXY.fY) {
 692                 continue;
 693             }
 694             if (bestXY->fY == testXY.fY && bestXY->fX < testXY.fX) {
 695                 continue;
 696             }
 697         }
 698         *topStart = testSegment;
 699         *bestXY = testXY;
 700     }
 701 }
 702
 703 SkOpSegment* SkOpContour::undoneSegment(int* start, int* end) {
 704     int segmentCount = fSegments.count();
 705     for (int test = 0; test < segmentCount; ++test) {
 706         SkOpSegment* testSegment = &fSegments[test];
 707         if (testSegment->done()) {
 708             continue;
 709         }
 710         testSegment->undoneSpan(start, end);
 711         return testSegment;
 712     }
 713     return NULL;
 714 }
 715
 716 #if DEBUG_SHOW_WINDING
 717 int SkOpContour::debugShowWindingValues(int totalSegments, int ofInterest) {
 718     int count = fSegments.count();
 719     int sum = 0;
 720     for (int index = 0; index < count; ++index) {
 721         sum += fSegments[index].debugShowWindingValues(totalSegments, ofInterest);
 722     }
 723 //      SkDebugf("%s sum=%d\n", __FUNCTION__, sum);
 724     return sum;
 725 }
 726
 727 void SkOpContour::debugShowWindingValues(const SkTArray<SkOpContour*, true>& contourList) {
 728 //     int ofInterest = 1 << 1 | 1 << 5 | 1 << 9 | 1 << 13;
 729 //    int ofInterest = 1 << 4 | 1 << 8 | 1 << 12 | 1 << 16;
 730     int ofInterest = 1 << 5 | 1 << 8;
 731     int total = 0;
 732     int index;
 733     for (index = 0; index < contourList.count(); ++index) {
 734         total += contourList[index]->segments().count();
 735     }
 736     int sum = 0;
 737     for (index = 0; index < contourList.count(); ++index) {
 738         sum += contourList[index]->debugShowWindingValues(total, ofInterest);
 739     }
 740 //       SkDebugf("%s total=%d\n", __FUNCTION__, sum);
 741 }
 742 #endif
 743
 744 void SkOpContour::setBounds() {
 745     int count = fSegments.count();
 746     if (count == 0) {
 747         SkDebugf("%s empty contour\n", __FUNCTION__);
 748         SkASSERT(0);
 749         // FIXME: delete empty contour?
 750         return;
 751     }
 752     fBounds = fSegments.front().bounds();
 753     for (int index = 1; index < count; ++index) {
 754         fBounds.add(fSegments[index].bounds());
 755     }
 756 }