michael@0: /*
michael@0: * Copyright 2013 Google Inc.
michael@0: *
michael@0: * Use of this source code is governed by a BSD-style license that can be
michael@0: * found in the LICENSE file.
michael@0: */
michael@0: #include "SkIntersections.h"
michael@0: #include "SkOpContour.h"
michael@0: #include "SkPathWriter.h"
michael@0: #include "SkTSort.h"
michael@0: 
michael@0: bool SkOpContour::addCoincident(int index, SkOpContour* other, int otherIndex,
michael@0:         const SkIntersections& ts, bool swap) {
michael@0:     SkPoint pt0 = ts.pt(0).asSkPoint();
michael@0:     SkPoint pt1 = ts.pt(1).asSkPoint();
michael@0:     if (pt0 == pt1) {
michael@0:         // FIXME: one could imagine a case where it would be incorrect to ignore this
michael@0:         // suppose two self-intersecting cubics overlap to be coincident --
michael@0:         // this needs to check that by some measure the t values are far enough apart
michael@0:         // or needs to check to see if the self-intersection bit was set on the cubic segment
michael@0:         return false;
michael@0:     }
michael@0:     SkCoincidence& coincidence = fCoincidences.push_back();
michael@0:     coincidence.fOther = other;
michael@0:     coincidence.fSegments[0] = index;
michael@0:     coincidence.fSegments[1] = otherIndex;
michael@0:     coincidence.fTs[swap][0] = ts[0][0];
michael@0:     coincidence.fTs[swap][1] = ts[0][1];
michael@0:     coincidence.fTs[!swap][0] = ts[1][0];
michael@0:     coincidence.fTs[!swap][1] = ts[1][1];
michael@0:     coincidence.fPts[0] = pt0;
michael@0:     coincidence.fPts[1] = pt1;
michael@0:     return true;
michael@0: }
michael@0: 
michael@0: SkOpSegment* SkOpContour::nonVerticalSegment(int* start, int* end) {
michael@0:     int segmentCount = fSortedSegments.count();
michael@0:     SkASSERT(segmentCount > 0);
michael@0:     for (int sortedIndex = fFirstSorted; sortedIndex < segmentCount; ++sortedIndex) {
michael@0:         SkOpSegment* testSegment = fSortedSegments[sortedIndex];
michael@0:         if (testSegment->done()) {
michael@0:             continue;
michael@0:         }
michael@0:         *start = *end = 0;
michael@0:         while (testSegment->nextCandidate(start, end)) {
michael@0:             if (!testSegment->isVertical(*start, *end)) {
michael@0:                 return testSegment;
michael@0:             }
michael@0:         }
michael@0:     }
michael@0:     return NULL;
michael@0: }
michael@0: 
michael@0: // first pass, add missing T values
michael@0: // second pass, determine winding values of overlaps
michael@0: void SkOpContour::addCoincidentPoints() {
michael@0:     int count = fCoincidences.count();
michael@0:     for (int index = 0; index < count; ++index) {
michael@0:         SkCoincidence& coincidence = fCoincidences[index];
michael@0:         int thisIndex = coincidence.fSegments[0];
michael@0:         SkOpSegment& thisOne = fSegments[thisIndex];
michael@0:         SkOpContour* otherContour = coincidence.fOther;
michael@0:         int otherIndex = coincidence.fSegments[1];
michael@0:         SkOpSegment& other = otherContour->fSegments[otherIndex];
michael@0:         if ((thisOne.done() || other.done()) && thisOne.complete() && other.complete()) {
michael@0:             // OPTIMIZATION: remove from array
michael@0:             continue;
michael@0:         }
michael@0:     #if DEBUG_CONCIDENT
michael@0:         thisOne.debugShowTs("-");
michael@0:         other.debugShowTs("o");
michael@0:     #endif
michael@0:         double startT = coincidence.fTs[0][0];
michael@0:         double endT = coincidence.fTs[0][1];
michael@0:         bool startSwapped, oStartSwapped, cancelers;
michael@0:         if ((cancelers = startSwapped = startT > endT)) {
michael@0:             SkTSwap(startT, endT);
michael@0:         }
michael@0:         if (startT == endT) { // if one is very large the smaller may have collapsed to nothing
michael@0:             if (endT <= 1 - FLT_EPSILON) {
michael@0:                 endT += FLT_EPSILON;
michael@0:                 SkASSERT(endT <= 1);
michael@0:             } else {
michael@0:                 startT -= FLT_EPSILON;
michael@0:                 SkASSERT(startT >= 0);
michael@0:             }
michael@0:         }
michael@0:         SkASSERT(!approximately_negative(endT - startT));
michael@0:         double oStartT = coincidence.fTs[1][0];
michael@0:         double oEndT = coincidence.fTs[1][1];
michael@0:         if ((oStartSwapped = oStartT > oEndT)) {
michael@0:             SkTSwap(oStartT, oEndT);
michael@0:             cancelers ^= true;
michael@0:         }
michael@0:         SkASSERT(!approximately_negative(oEndT - oStartT));
michael@0:         if (cancelers) {
michael@0:             // make sure startT and endT have t entries
michael@0:             const SkPoint& startPt = coincidence.fPts[startSwapped];
michael@0:             if (startT > 0 || oEndT < 1
michael@0:                     || thisOne.isMissing(startT, startPt) || other.isMissing(oEndT, startPt)) {
michael@0:                 thisOne.addTPair(startT, &other, oEndT, true, startPt);
michael@0:             }
michael@0:             const SkPoint& oStartPt = coincidence.fPts[oStartSwapped];
michael@0:             if (oStartT > 0 || endT < 1
michael@0:                     || thisOne.isMissing(endT, oStartPt) || other.isMissing(oStartT, oStartPt)) {
michael@0:                 other.addTPair(oStartT, &thisOne, endT, true, oStartPt);
michael@0:             }
michael@0:         } else {
michael@0:             const SkPoint& startPt = coincidence.fPts[startSwapped];
michael@0:             if (startT > 0 || oStartT > 0
michael@0:                     || thisOne.isMissing(startT, startPt) || other.isMissing(oStartT, startPt)) {
michael@0:                 thisOne.addTPair(startT, &other, oStartT, true, startPt);
michael@0:             }
michael@0:             const SkPoint& oEndPt = coincidence.fPts[!oStartSwapped];
michael@0:             if (endT < 1 || oEndT < 1
michael@0:                     || thisOne.isMissing(endT, oEndPt) || other.isMissing(oEndT, oEndPt)) {
michael@0:                 other.addTPair(oEndT, &thisOne, endT, true, oEndPt);
michael@0:             }
michael@0:         }
michael@0:     #if DEBUG_CONCIDENT
michael@0:         thisOne.debugShowTs("+");
michael@0:         other.debugShowTs("o");
michael@0:     #endif
michael@0:     }
michael@0: }
michael@0: 
michael@0: bool SkOpContour::addPartialCoincident(int index, SkOpContour* other, int otherIndex,
michael@0:         const SkIntersections& ts, int ptIndex, bool swap) {
michael@0:     SkPoint pt0 = ts.pt(ptIndex).asSkPoint();
michael@0:     SkPoint pt1 = ts.pt(ptIndex + 1).asSkPoint();
michael@0:     if (SkDPoint::ApproximatelyEqual(pt0, pt1)) {
michael@0:         // FIXME: one could imagine a case where it would be incorrect to ignore this
michael@0:         // suppose two self-intersecting cubics overlap to form a partial coincidence --
michael@0:         // although it isn't clear why the regular coincidence could wouldn't pick this up
michael@0:         // this is exceptional enough to ignore for now
michael@0:         return false;
michael@0:     }
michael@0:     SkCoincidence& coincidence = fPartialCoincidences.push_back();
michael@0:     coincidence.fOther = other;
michael@0:     coincidence.fSegments[0] = index;
michael@0:     coincidence.fSegments[1] = otherIndex;
michael@0:     coincidence.fTs[swap][0] = ts[0][ptIndex];
michael@0:     coincidence.fTs[swap][1] = ts[0][ptIndex + 1];
michael@0:     coincidence.fTs[!swap][0] = ts[1][ptIndex];
michael@0:     coincidence.fTs[!swap][1] = ts[1][ptIndex + 1];
michael@0:     coincidence.fPts[0] = pt0;
michael@0:     coincidence.fPts[1] = pt1;
michael@0:     return true;
michael@0: }
michael@0: 
michael@0: void SkOpContour::calcCoincidentWinding() {
michael@0:     int count = fCoincidences.count();
michael@0: #if DEBUG_CONCIDENT
michael@0:     if (count > 0) {
michael@0:         SkDebugf("%s count=%d\n", __FUNCTION__, count);
michael@0:     }
michael@0: #endif
michael@0:     for (int index = 0; index < count; ++index) {
michael@0:         SkCoincidence& coincidence = fCoincidences[index];
michael@0:          calcCommonCoincidentWinding(coincidence);
michael@0:     }
michael@0: }
michael@0: 
michael@0: void SkOpContour::calcPartialCoincidentWinding() {
michael@0:     int count = fPartialCoincidences.count();
michael@0: #if DEBUG_CONCIDENT
michael@0:     if (count > 0) {
michael@0:         SkDebugf("%s count=%d\n", __FUNCTION__, count);
michael@0:     }
michael@0: #endif
michael@0:     for (int index = 0; index < count; ++index) {
michael@0:         SkCoincidence& coincidence = fPartialCoincidences[index];
michael@0:          calcCommonCoincidentWinding(coincidence);
michael@0:     }
michael@0: }
michael@0: 
michael@0: void SkOpContour::joinCoincidence(const SkTArray<SkCoincidence, true>& coincidences, bool partial) {
michael@0:     int count = coincidences.count();
michael@0: #if DEBUG_CONCIDENT
michael@0:     if (count > 0) {
michael@0:         SkDebugf("%s count=%d\n", __FUNCTION__, count);
michael@0:     }
michael@0: #endif
michael@0:     // look for a lineup where the partial implies another adjoining coincidence
michael@0:     for (int index = 0; index < count; ++index) {
michael@0:         const SkCoincidence& coincidence = coincidences[index];
michael@0:         int thisIndex = coincidence.fSegments[0];
michael@0:         SkOpSegment& thisOne = fSegments[thisIndex];
michael@0:         SkOpContour* otherContour = coincidence.fOther;
michael@0:         int otherIndex = coincidence.fSegments[1];
michael@0:         SkOpSegment& other = otherContour->fSegments[otherIndex];
michael@0:         double startT = coincidence.fTs[0][0];
michael@0:         double endT = coincidence.fTs[0][1];
michael@0:         if (startT == endT) {  // this can happen in very large compares
michael@0:             continue;
michael@0:         }
michael@0:         double oStartT = coincidence.fTs[1][0];
michael@0:         double oEndT = coincidence.fTs[1][1];
michael@0:         if (oStartT == oEndT) {
michael@0:             continue;
michael@0:         }
michael@0:         bool swapStart = startT > endT;
michael@0:         bool swapOther = oStartT > oEndT;
michael@0:         if (swapStart) {
michael@0:             SkTSwap<double>(startT, endT);
michael@0:             SkTSwap<double>(oStartT, oEndT);
michael@0:         }
michael@0:         bool cancel = swapOther != swapStart;
michael@0:         int step = swapStart ? -1 : 1;
michael@0:         int oStep = swapOther ? -1 : 1;
michael@0:         double oMatchStart = cancel ? oEndT : oStartT;
michael@0:         if (partial ? startT != 0 || oMatchStart != 0 : (startT == 0) != (oMatchStart == 0)) {
michael@0:             bool added = false;
michael@0:             if (oMatchStart != 0) {
michael@0:                 added = thisOne.joinCoincidence(&other, oMatchStart, oStep, cancel);
michael@0:             }
michael@0:             if (!cancel && startT != 0 && !added) {
michael@0:                 (void) other.joinCoincidence(&thisOne, startT, step, cancel);
michael@0:             }
michael@0:         }
michael@0:         double oMatchEnd = cancel ? oStartT : oEndT;
michael@0:         if (partial ? endT != 1 || oMatchEnd != 1 : (endT == 1) != (oMatchEnd == 1)) {
michael@0:             bool added = false;
michael@0:             if (cancel && endT != 1 && !added) {
michael@0:                 (void) other.joinCoincidence(&thisOne, endT, -step, cancel);
michael@0:             }
michael@0:         }
michael@0:     }
michael@0: }
michael@0: 
michael@0: void SkOpContour::calcCommonCoincidentWinding(const SkCoincidence& coincidence) {
michael@0:     int thisIndex = coincidence.fSegments[0];
michael@0:     SkOpSegment& thisOne = fSegments[thisIndex];
michael@0:     if (thisOne.done()) {
michael@0:         return;
michael@0:     }
michael@0:     SkOpContour* otherContour = coincidence.fOther;
michael@0:     int otherIndex = coincidence.fSegments[1];
michael@0:     SkOpSegment& other = otherContour->fSegments[otherIndex];
michael@0:     if (other.done()) {
michael@0:         return;
michael@0:     }
michael@0:     double startT = coincidence.fTs[0][0];
michael@0:     double endT = coincidence.fTs[0][1];
michael@0:     const SkPoint* startPt = &coincidence.fPts[0];
michael@0:     const SkPoint* endPt = &coincidence.fPts[1];
michael@0:     bool cancelers;
michael@0:     if ((cancelers = startT > endT)) {
michael@0:         SkTSwap<double>(startT, endT);
michael@0:         SkTSwap<const SkPoint*>(startPt, endPt);
michael@0:     }
michael@0:     if (startT == endT) { // if span is very large, the smaller may have collapsed to nothing
michael@0:         if (endT <= 1 - FLT_EPSILON) {
michael@0:             endT += FLT_EPSILON;
michael@0:             SkASSERT(endT <= 1);
michael@0:         } else {
michael@0:             startT -= FLT_EPSILON;
michael@0:             SkASSERT(startT >= 0);
michael@0:         }
michael@0:     }
michael@0:     SkASSERT(!approximately_negative(endT - startT));
michael@0:     double oStartT = coincidence.fTs[1][0];
michael@0:     double oEndT = coincidence.fTs[1][1];
michael@0:     if (oStartT > oEndT) {
michael@0:         SkTSwap<double>(oStartT, oEndT);
michael@0:         cancelers ^= true;
michael@0:     }
michael@0:     SkASSERT(!approximately_negative(oEndT - oStartT));
michael@0:     if (cancelers) {
michael@0:         thisOne.addTCancel(*startPt, *endPt, &other);
michael@0:     } else {
michael@0:         thisOne.addTCoincident(*startPt, *endPt, endT, &other);
michael@0:     }
michael@0: #if DEBUG_CONCIDENT
michael@0:     thisOne.debugShowTs("p");
michael@0:     other.debugShowTs("o");
michael@0: #endif
michael@0: }
michael@0: 
michael@0: void SkOpContour::sortSegments() {
michael@0:     int segmentCount = fSegments.count();
michael@0:     fSortedSegments.push_back_n(segmentCount);
michael@0:     for (int test = 0; test < segmentCount; ++test) {
michael@0:         fSortedSegments[test] = &fSegments[test];
michael@0:     }
michael@0:     SkTQSort<SkOpSegment>(fSortedSegments.begin(), fSortedSegments.end() - 1);
michael@0:     fFirstSorted = 0;
michael@0: }
michael@0: 
michael@0: void SkOpContour::toPath(SkPathWriter* path) const {
michael@0:     int segmentCount = fSegments.count();
michael@0:     const SkPoint& pt = fSegments.front().pts()[0];
michael@0:     path->deferredMove(pt);
michael@0:     for (int test = 0; test < segmentCount; ++test) {
michael@0:         fSegments[test].addCurveTo(0, 1, path, true);
michael@0:     }
michael@0:     path->close();
michael@0: }
michael@0: 
michael@0: void SkOpContour::topSortableSegment(const SkPoint& topLeft, SkPoint* bestXY,
michael@0:         SkOpSegment** topStart) {
michael@0:     int segmentCount = fSortedSegments.count();
michael@0:     SkASSERT(segmentCount > 0);
michael@0:     int sortedIndex = fFirstSorted;
michael@0:     fDone = true;  // may be cleared below
michael@0:     for ( ; sortedIndex < segmentCount; ++sortedIndex) {
michael@0:         SkOpSegment* testSegment = fSortedSegments[sortedIndex];
michael@0:         if (testSegment->done()) {
michael@0:             if (sortedIndex == fFirstSorted) {
michael@0:                 ++fFirstSorted;
michael@0:             }
michael@0:             continue;
michael@0:         }
michael@0:         fDone = false;
michael@0:         SkPoint testXY = testSegment->activeLeftTop(true, NULL);
michael@0:         if (*topStart) {
michael@0:             if (testXY.fY < topLeft.fY) {
michael@0:                 continue;
michael@0:             }
michael@0:             if (testXY.fY == topLeft.fY && testXY.fX < topLeft.fX) {
michael@0:                 continue;
michael@0:             }
michael@0:             if (bestXY->fY < testXY.fY) {
michael@0:                 continue;
michael@0:             }
michael@0:             if (bestXY->fY == testXY.fY && bestXY->fX < testXY.fX) {
michael@0:                 continue;
michael@0:             }
michael@0:         }
michael@0:         *topStart = testSegment;
michael@0:         *bestXY = testXY;
michael@0:     }
michael@0: }
michael@0: 
michael@0: SkOpSegment* SkOpContour::undoneSegment(int* start, int* end) {
michael@0:     int segmentCount = fSegments.count();
michael@0:     for (int test = 0; test < segmentCount; ++test) {
michael@0:         SkOpSegment* testSegment = &fSegments[test];
michael@0:         if (testSegment->done()) {
michael@0:             continue;
michael@0:         }
michael@0:         testSegment->undoneSpan(start, end);
michael@0:         return testSegment;
michael@0:     }
michael@0:     return NULL;
michael@0: }
michael@0: 
michael@0: #if DEBUG_SHOW_WINDING
michael@0: int SkOpContour::debugShowWindingValues(int totalSegments, int ofInterest) {
michael@0:     int count = fSegments.count();
michael@0:     int sum = 0;
michael@0:     for (int index = 0; index < count; ++index) {
michael@0:         sum += fSegments[index].debugShowWindingValues(totalSegments, ofInterest);
michael@0:     }
michael@0: //      SkDebugf("%s sum=%d\n", __FUNCTION__, sum);
michael@0:     return sum;
michael@0: }
michael@0: 
michael@0: void SkOpContour::debugShowWindingValues(const SkTArray<SkOpContour*, true>& contourList) {
michael@0: //     int ofInterest = 1 << 1 | 1 << 5 | 1 << 9 | 1 << 13;
michael@0: //    int ofInterest = 1 << 4 | 1 << 8 | 1 << 12 | 1 << 16;
michael@0:     int ofInterest = 1 << 5 | 1 << 8;
michael@0:     int total = 0;
michael@0:     int index;
michael@0:     for (index = 0; index < contourList.count(); ++index) {
michael@0:         total += contourList[index]->segments().count();
michael@0:     }
michael@0:     int sum = 0;
michael@0:     for (index = 0; index < contourList.count(); ++index) {
michael@0:         sum += contourList[index]->debugShowWindingValues(total, ofInterest);
michael@0:     }
michael@0: //       SkDebugf("%s total=%d\n", __FUNCTION__, sum);
michael@0: }
michael@0: #endif
michael@0: 
michael@0: void SkOpContour::setBounds() {
michael@0:     int count = fSegments.count();
michael@0:     if (count == 0) {
michael@0:         SkDebugf("%s empty contour\n", __FUNCTION__);
michael@0:         SkASSERT(0);
michael@0:         // FIXME: delete empty contour?
michael@0:         return;
michael@0:     }
michael@0:     fBounds = fSegments.front().bounds();
michael@0:     for (int index = 1; index < count; ++index) {
michael@0:         fBounds.add(fSegments[index].bounds());
michael@0:     }
michael@0: }