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[0] = pt0;
  32     coincidence.fPts[1] = pt1;
  33     return true;
  34 }
  35
  36 SkOpSegment* SkOpContour::nonVerticalSegment(int* start, int* end) {
  37     int segmentCount = fSortedSegments.count();
  38     SkASSERT(segmentCount > 0);
  39     for (int sortedIndex = fFirstSorted; sortedIndex < segmentCount; ++sortedIndex) {
  40         SkOpSegment* testSegment = fSortedSegments[sortedIndex];
  41         if (testSegment->done()) {
  42             continue;
  43         }
  44         *start = *end = 0;
  45         while (testSegment->nextCandidate(start, end)) {
  46             if (!testSegment->isVertical(*start, *end)) {
  47                 return testSegment;
  48             }
  49         }
  50     }
  51     return NULL;
  52 }
  53
  54 // first pass, add missing T values
  55 // second pass, determine winding values of overlaps
  56 void SkOpContour::addCoincidentPoints() {
  57     int count = fCoincidences.count();
  58     for (int index = 0; index < count; ++index) {
  59         SkCoincidence& coincidence = fCoincidences[index];
  60         int thisIndex = coincidence.fSegments[0];
  61         SkOpSegment& thisOne = fSegments[thisIndex];
  62         SkOpContour* otherContour = coincidence.fOther;
  63         int otherIndex = coincidence.fSegments[1];
  64         SkOpSegment& other = otherContour->fSegments[otherIndex];
  65         if ((thisOne.done() || other.done()) && thisOne.complete() && other.complete()) {
  66             // OPTIMIZATION: remove from array
  67             continue;
  68         }
  69     #if DEBUG_CONCIDENT
  70         thisOne.debugShowTs("-");
  71         other.debugShowTs("o");
  72     #endif
  73         double startT = coincidence.fTs[0][0];
  74         double endT = coincidence.fTs[0][1];
  75         bool startSwapped, oStartSwapped, cancelers;
  76         if ((cancelers = startSwapped = startT > endT)) {
  77             SkTSwap(startT, endT);
  78         }
  79         if (startT == endT) { // if one is very large the smaller may have collapsed to nothing
  80             if (endT <= 1 - FLT_EPSILON) {
  81                 endT += FLT_EPSILON;
  82                 SkASSERT(endT <= 1);
  83             } else {
  84                 startT -= FLT_EPSILON;
  85                 SkASSERT(startT >= 0);
  86             }
  87         }
  88         SkASSERT(!approximately_negative(endT - startT));
  89         double oStartT = coincidence.fTs[1][0];
  90         double oEndT = coincidence.fTs[1][1];
  91         if ((oStartSwapped = oStartT > oEndT)) {
  92             SkTSwap(oStartT, oEndT);
  93             cancelers ^= true;
  94         }
  95         SkASSERT(!approximately_negative(oEndT - oStartT));
  96         if (cancelers) {
  97             // make sure startT and endT have t entries
  98             const SkPoint& startPt = coincidence.fPts[startSwapped];
  99             if (startT > 0 || oEndT < 1
 100                     || thisOne.isMissing(startT, startPt) || other.isMissing(oEndT, startPt)) {
 101                 thisOne.addTPair(startT, &other, oEndT, true, startPt);
 102             }
 103             const SkPoint& oStartPt = coincidence.fPts[oStartSwapped];
 104             if (oStartT > 0 || endT < 1
 105                     || thisOne.isMissing(endT, oStartPt) || other.isMissing(oStartT, oStartPt)) {
 106                 other.addTPair(oStartT, &thisOne, endT, true, oStartPt);
 107             }
 108         } else {
 109             const SkPoint& startPt = coincidence.fPts[startSwapped];
 110             if (startT > 0 || oStartT > 0
 111                     || thisOne.isMissing(startT, startPt) || other.isMissing(oStartT, startPt)) {
 112                 thisOne.addTPair(startT, &other, oStartT, true, startPt);
 113             }
 114             const SkPoint& oEndPt = coincidence.fPts[!oStartSwapped];
 115             if (endT < 1 || oEndT < 1
 116                     || thisOne.isMissing(endT, oEndPt) || other.isMissing(oEndT, oEndPt)) {
 117                 other.addTPair(oEndT, &thisOne, endT, true, oEndPt);
 118             }
 119         }
 120     #if DEBUG_CONCIDENT
 121         thisOne.debugShowTs("+");
 122         other.debugShowTs("o");
 123     #endif
 124     }
 125 }
 126
 127 bool SkOpContour::addPartialCoincident(int index, SkOpContour* other, int otherIndex,
 128         const SkIntersections& ts, int ptIndex, bool swap) {
 129     SkPoint pt0 = ts.pt(ptIndex).asSkPoint();
 130     SkPoint pt1 = ts.pt(ptIndex + 1).asSkPoint();
 131     if (SkDPoint::ApproximatelyEqual(pt0, pt1)) {
 132         // FIXME: one could imagine a case where it would be incorrect to ignore this
 133         // suppose two self-intersecting cubics overlap to form a partial coincidence --
 134         // although it isn't clear why the regular coincidence could wouldn't pick this up
 135         // this is exceptional enough to ignore for now
 136         return false;
 137     }
 138     SkCoincidence& coincidence = fPartialCoincidences.push_back();
 139     coincidence.fOther = other;
 140     coincidence.fSegments[0] = index;
 141     coincidence.fSegments[1] = otherIndex;
 142     coincidence.fTs[swap][0] = ts[0][ptIndex];
 143     coincidence.fTs[swap][1] = ts[0][ptIndex + 1];
 144     coincidence.fTs[!swap][0] = ts[1][ptIndex];
 145     coincidence.fTs[!swap][1] = ts[1][ptIndex + 1];
 146     coincidence.fPts[0] = pt0;
 147     coincidence.fPts[1] = pt1;
 148     return true;
 149 }
 150
 151 void SkOpContour::calcCoincidentWinding() {
 152     int count = fCoincidences.count();
 153 #if DEBUG_CONCIDENT
 154     if (count > 0) {
 155         SkDebugf("%s count=%d\n", __FUNCTION__, count);
 156     }
 157 #endif
 158     for (int index = 0; index < count; ++index) {
 159         SkCoincidence& coincidence = fCoincidences[index];
 160          calcCommonCoincidentWinding(coincidence);
 161     }
 162 }
 163
 164 void SkOpContour::calcPartialCoincidentWinding() {
 165     int count = fPartialCoincidences.count();
 166 #if DEBUG_CONCIDENT
 167     if (count > 0) {
 168         SkDebugf("%s count=%d\n", __FUNCTION__, count);
 169     }
 170 #endif
 171     for (int index = 0; index < count; ++index) {
 172         SkCoincidence& coincidence = fPartialCoincidences[index];
 173          calcCommonCoincidentWinding(coincidence);
 174     }
 175 }
 176
 177 void SkOpContour::joinCoincidence(const SkTArray<SkCoincidence, true>& coincidences, bool partial) {
 178     int count = coincidences.count();
 179 #if DEBUG_CONCIDENT
 180     if (count > 0) {
 181         SkDebugf("%s count=%d\n", __FUNCTION__, count);
 182     }
 183 #endif
 184     // look for a lineup where the partial implies another adjoining coincidence
 185     for (int index = 0; index < count; ++index) {
 186         const SkCoincidence& coincidence = coincidences[index];
 187         int thisIndex = coincidence.fSegments[0];
 188         SkOpSegment& thisOne = fSegments[thisIndex];
 189         SkOpContour* otherContour = coincidence.fOther;
 190         int otherIndex = coincidence.fSegments[1];
 191         SkOpSegment& other = otherContour->fSegments[otherIndex];
 192         double startT = coincidence.fTs[0][0];
 193         double endT = coincidence.fTs[0][1];
 194         if (startT == endT) {  // this can happen in very large compares
 195             continue;
 196         }
 197         double oStartT = coincidence.fTs[1][0];
 198         double oEndT = coincidence.fTs[1][1];
 199         if (oStartT == oEndT) {
 200             continue;
 201         }
 202         bool swapStart = startT > endT;
 203         bool swapOther = oStartT > oEndT;
 204         if (swapStart) {
 205             SkTSwap<double>(startT, endT);
 206             SkTSwap<double>(oStartT, oEndT);
 207         }
 208         bool cancel = swapOther != swapStart;
 209         int step = swapStart ? -1 : 1;
 210         int oStep = swapOther ? -1 : 1;
 211         double oMatchStart = cancel ? oEndT : oStartT;
 212         if (partial ? startT != 0 || oMatchStart != 0 : (startT == 0) != (oMatchStart == 0)) {
 213             bool added = false;
 214             if (oMatchStart != 0) {
 215                 added = thisOne.joinCoincidence(&other, oMatchStart, oStep, cancel);
 216             }
 217             if (!cancel && startT != 0 && !added) {
 218                 (void) other.joinCoincidence(&thisOne, startT, step, cancel);
 219             }
 220         }
 221         double oMatchEnd = cancel ? oStartT : oEndT;
 222         if (partial ? endT != 1 || oMatchEnd != 1 : (endT == 1) != (oMatchEnd == 1)) {
 223             bool added = false;
 224             if (cancel && endT != 1 && !added) {
 225                 (void) other.joinCoincidence(&thisOne, endT, -step, cancel);
 226             }
 227         }
 228     }
 229 }
 230
 231 void SkOpContour::calcCommonCoincidentWinding(const SkCoincidence& coincidence) {
 232     int thisIndex = coincidence.fSegments[0];
 233     SkOpSegment& thisOne = fSegments[thisIndex];
 234     if (thisOne.done()) {
 235         return;
 236     }
 237     SkOpContour* otherContour = coincidence.fOther;
 238     int otherIndex = coincidence.fSegments[1];
 239     SkOpSegment& other = otherContour->fSegments[otherIndex];
 240     if (other.done()) {
 241         return;
 242     }
 243     double startT = coincidence.fTs[0][0];
 244     double endT = coincidence.fTs[0][1];
 245     const SkPoint* startPt = &coincidence.fPts[0];
 246     const SkPoint* endPt = &coincidence.fPts[1];
 247     bool cancelers;
 248     if ((cancelers = startT > endT)) {
 249         SkTSwap<double>(startT, endT);
 250         SkTSwap<const SkPoint*>(startPt, endPt);
 251     }
 252     if (startT == endT) { // if span is very large, the smaller may have collapsed to nothing
 253         if (endT <= 1 - FLT_EPSILON) {
 254             endT += FLT_EPSILON;
 255             SkASSERT(endT <= 1);
 256         } else {
 257             startT -= FLT_EPSILON;
 258             SkASSERT(startT >= 0);
 259         }
 260     }
 261     SkASSERT(!approximately_negative(endT - startT));
 262     double oStartT = coincidence.fTs[1][0];
 263     double oEndT = coincidence.fTs[1][1];
 264     if (oStartT > oEndT) {
 265         SkTSwap<double>(oStartT, oEndT);
 266         cancelers ^= true;
 267     }
 268     SkASSERT(!approximately_negative(oEndT - oStartT));
 269     if (cancelers) {
 270         thisOne.addTCancel(*startPt, *endPt, &other);
 271     } else {
 272         thisOne.addTCoincident(*startPt, *endPt, endT, &other);
 273     }
 274 #if DEBUG_CONCIDENT
 275     thisOne.debugShowTs("p");
 276     other.debugShowTs("o");
 277 #endif
 278 }
 279
 280 void SkOpContour::sortSegments() {
 281     int segmentCount = fSegments.count();
 282     fSortedSegments.push_back_n(segmentCount);
 283     for (int test = 0; test < segmentCount; ++test) {
 284         fSortedSegments[test] = &fSegments[test];
 285     }
 286     SkTQSort<SkOpSegment>(fSortedSegments.begin(), fSortedSegments.end() - 1);
 287     fFirstSorted = 0;
 288 }
 289
 290 void SkOpContour::toPath(SkPathWriter* path) const {
 291     int segmentCount = fSegments.count();
 292     const SkPoint& pt = fSegments.front().pts()[0];
 293     path->deferredMove(pt);
 294     for (int test = 0; test < segmentCount; ++test) {
 295         fSegments[test].addCurveTo(0, 1, path, true);
 296     }
 297     path->close();
 298 }
 299
 300 void SkOpContour::topSortableSegment(const SkPoint& topLeft, SkPoint* bestXY,
 301         SkOpSegment** topStart) {
 302     int segmentCount = fSortedSegments.count();
 303     SkASSERT(segmentCount > 0);
 304     int sortedIndex = fFirstSorted;
 305     fDone = true;  // may be cleared below
 306     for ( ; sortedIndex < segmentCount; ++sortedIndex) {
 307         SkOpSegment* testSegment = fSortedSegments[sortedIndex];
 308         if (testSegment->done()) {
 309             if (sortedIndex == fFirstSorted) {
 310                 ++fFirstSorted;
 311             }
 312             continue;
 313         }
 314         fDone = false;
 315         SkPoint testXY = testSegment->activeLeftTop(true, NULL);
 316         if (*topStart) {
 317             if (testXY.fY < topLeft.fY) {
 318                 continue;
 319             }
 320             if (testXY.fY == topLeft.fY && testXY.fX < topLeft.fX) {
 321                 continue;
 322             }
 323             if (bestXY->fY < testXY.fY) {
 324                 continue;
 325             }
 326             if (bestXY->fY == testXY.fY && bestXY->fX < testXY.fX) {
 327                 continue;
 328             }
 329         }
 330         *topStart = testSegment;
 331         *bestXY = testXY;
 332     }
 333 }
 334
 335 SkOpSegment* SkOpContour::undoneSegment(int* start, int* end) {
 336     int segmentCount = fSegments.count();
 337     for (int test = 0; test < segmentCount; ++test) {
 338         SkOpSegment* testSegment = &fSegments[test];
 339         if (testSegment->done()) {
 340             continue;
 341         }
 342         testSegment->undoneSpan(start, end);
 343         return testSegment;
 344     }
 345     return NULL;
 346 }
 347
 348 #if DEBUG_SHOW_WINDING
 349 int SkOpContour::debugShowWindingValues(int totalSegments, int ofInterest) {
 350     int count = fSegments.count();
 351     int sum = 0;
 352     for (int index = 0; index < count; ++index) {
 353         sum += fSegments[index].debugShowWindingValues(totalSegments, ofInterest);
 354     }
 355 //      SkDebugf("%s sum=%d\n", __FUNCTION__, sum);
 356     return sum;
 357 }
 358
 359 void SkOpContour::debugShowWindingValues(const SkTArray<SkOpContour*, true>& contourList) {
 360 //     int ofInterest = 1 << 1 | 1 << 5 | 1 << 9 | 1 << 13;
 361 //    int ofInterest = 1 << 4 | 1 << 8 | 1 << 12 | 1 << 16;
 362     int ofInterest = 1 << 5 | 1 << 8;
 363     int total = 0;
 364     int index;
 365     for (index = 0; index < contourList.count(); ++index) {
 366         total += contourList[index]->segments().count();
 367     }
 368     int sum = 0;
 369     for (index = 0; index < contourList.count(); ++index) {
 370         sum += contourList[index]->debugShowWindingValues(total, ofInterest);
 371     }
 372 //       SkDebugf("%s total=%d\n", __FUNCTION__, sum);
 373 }
 374 #endif
 375
 376 void SkOpContour::setBounds() {
 377     int count = fSegments.count();
 378     if (count == 0) {
 379         SkDebugf("%s empty contour\n", __FUNCTION__);
 380         SkASSERT(0);
 381         // FIXME: delete empty contour?
 382         return;
 383     }
 384     fBounds = fSegments.front().bounds();
 385     for (int index = 1; index < count; ++index) {
 386         fBounds.add(fSegments[index].bounds());
 387     }
 388 }