src/pathops/SkOpContour.cpp

/*
* Copyright 2013 Google Inc.
*
* Use of this source code is governed by a BSD-style license that can be
* found in the LICENSE file.
*/
#include "SkIntersections.h"
#include "SkOpContour.h"
#include "SkPathWriter.h"
#include "SkTSort.h"

bool SkOpContour::addCoincident(int index, SkOpContour* other, int otherIndex,
        const SkIntersections& ts, bool swap) {
    SkPoint pt0 = ts.pt(0).asSkPoint();
    SkPoint pt1 = ts.pt(1).asSkPoint();
    if (pt0 == pt1) {
        // FIXME: one could imagine a case where it would be incorrect to ignore this
        // suppose two self-intersecting cubics overlap to be coincident --
        // this needs to check that by some measure the t values are far enough apart
        // or needs to check to see if the self-intersection bit was set on the cubic segment
        return false;
    }
    SkCoincidence& coincidence = fCoincidences.push_back();
    coincidence.fOther = other;
    coincidence.fSegments[0] = index;
    coincidence.fSegments[1] = otherIndex;
    coincidence.fTs[swap][0] = ts[0][0];
    coincidence.fTs[swap][1] = ts[0][1];
    coincidence.fTs[!swap][0] = ts[1][0];
    coincidence.fTs[!swap][1] = ts[1][1];
    coincidence.fPts[0] = pt0;
    coincidence.fPts[1] = pt1;
    return true;
}

SkOpSegment* SkOpContour::nonVerticalSegment(int* start, int* end) {
    int segmentCount = fSortedSegments.count();
    SkASSERT(segmentCount > 0);
    for (int sortedIndex = fFirstSorted; sortedIndex < segmentCount; ++sortedIndex) {
        SkOpSegment* testSegment = fSortedSegments[sortedIndex];
        if (testSegment->done()) {
            continue;
        }
        *start = *end = 0;
        while (testSegment->nextCandidate(start, end)) {
            if (!testSegment->isVertical(*start, *end)) {
                return testSegment;
            }
        }
    }
    return NULL;
}

// first pass, add missing T values
// second pass, determine winding values of overlaps
void SkOpContour::addCoincidentPoints() {
    int count = fCoincidences.count();
    for (int index = 0; index < count; ++index) {
        SkCoincidence& coincidence = fCoincidences[index];
        int thisIndex = coincidence.fSegments[0];
        SkOpSegment& thisOne = fSegments[thisIndex];
        SkOpContour* otherContour = coincidence.fOther;
        int otherIndex = coincidence.fSegments[1];
        SkOpSegment& other = otherContour->fSegments[otherIndex];
        if ((thisOne.done() || other.done()) && thisOne.complete() && other.complete()) {
            // OPTIMIZATION: remove from array
            continue;
        }
    #if DEBUG_CONCIDENT
        thisOne.debugShowTs("-");
        other.debugShowTs("o");
    #endif
        double startT = coincidence.fTs[0][0];
        double endT = coincidence.fTs[0][1];
        bool startSwapped, oStartSwapped, cancelers;
        if ((cancelers = startSwapped = startT > endT)) {
            SkTSwap(startT, endT);
        }
        if (startT == endT) { // if one is very large the smaller may have collapsed to nothing
            if (endT <= 1 - FLT_EPSILON) {
                endT += FLT_EPSILON;
                SkASSERT(endT <= 1);
            } else {
                startT -= FLT_EPSILON;
                SkASSERT(startT >= 0);
            }
        }
        SkASSERT(!approximately_negative(endT - startT));
        double oStartT = coincidence.fTs[1][0];
        double oEndT = coincidence.fTs[1][1];
        if ((oStartSwapped = oStartT > oEndT)) {
            SkTSwap(oStartT, oEndT);
            cancelers ^= true;
        }
        SkASSERT(!approximately_negative(oEndT - oStartT));
        if (cancelers) {
            // make sure startT and endT have t entries
            const SkPoint& startPt = coincidence.fPts[startSwapped];
            if (startT > 0 || oEndT < 1
                    || thisOne.isMissing(startT, startPt) || other.isMissing(oEndT, startPt)) {
                thisOne.addTPair(startT, &other, oEndT, true, startPt);
            }
            const SkPoint& oStartPt = coincidence.fPts[oStartSwapped];
            if (oStartT > 0 || endT < 1
                    || thisOne.isMissing(endT, oStartPt) || other.isMissing(oStartT, oStartPt)) {
                other.addTPair(oStartT, &thisOne, endT, true, oStartPt);
            }
        } else {
            const SkPoint& startPt = coincidence.fPts[startSwapped];
            if (startT > 0 || oStartT > 0
                    || thisOne.isMissing(startT, startPt) || other.isMissing(oStartT, startPt)) {
                thisOne.addTPair(startT, &other, oStartT, true, startPt);
            }
            const SkPoint& oEndPt = coincidence.fPts[!oStartSwapped];
            if (endT < 1 || oEndT < 1
                    || thisOne.isMissing(endT, oEndPt) || other.isMissing(oEndT, oEndPt)) {
                other.addTPair(oEndT, &thisOne, endT, true, oEndPt);
            }
        }
    #if DEBUG_CONCIDENT
        thisOne.debugShowTs("+");
        other.debugShowTs("o");
    #endif
    }
}

bool SkOpContour::addPartialCoincident(int index, SkOpContour* other, int otherIndex,
        const SkIntersections& ts, int ptIndex, bool swap) {
    SkPoint pt0 = ts.pt(ptIndex).asSkPoint();
    SkPoint pt1 = ts.pt(ptIndex + 1).asSkPoint();
    if (SkDPoint::ApproximatelyEqual(pt0, pt1)) {
        // FIXME: one could imagine a case where it would be incorrect to ignore this
        // suppose two self-intersecting cubics overlap to form a partial coincidence --
        // although it isn't clear why the regular coincidence could wouldn't pick this up
        // this is exceptional enough to ignore for now
        return false;
    }
    SkCoincidence& coincidence = fPartialCoincidences.push_back();
    coincidence.fOther = other;
    coincidence.fSegments[0] = index;
    coincidence.fSegments[1] = otherIndex;
    coincidence.fTs[swap][0] = ts[0][ptIndex];
    coincidence.fTs[swap][1] = ts[0][ptIndex + 1];
    coincidence.fTs[!swap][0] = ts[1][ptIndex];
    coincidence.fTs[!swap][1] = ts[1][ptIndex + 1];
    coincidence.fPts[0] = pt0;
    coincidence.fPts[1] = pt1;
    return true;
}

void SkOpContour::calcCoincidentWinding() {
    int count = fCoincidences.count();
#if DEBUG_CONCIDENT
    if (count > 0) {
        SkDebugf("%s count=%d\n", __FUNCTION__, count);
    }
#endif
    for (int index = 0; index < count; ++index) {
        SkCoincidence& coincidence = fCoincidences[index];
         calcCommonCoincidentWinding(coincidence);
    }
}

void SkOpContour::calcPartialCoincidentWinding() {
    int count = fPartialCoincidences.count();
#if DEBUG_CONCIDENT
    if (count > 0) {
        SkDebugf("%s count=%d\n", __FUNCTION__, count);
    }
#endif
    for (int index = 0; index < count; ++index) {
        SkCoincidence& coincidence = fPartialCoincidences[index];
         calcCommonCoincidentWinding(coincidence);
    }
}

void SkOpContour::joinCoincidence(const SkTArray<SkCoincidence, true>& coincidences, bool partial) {
    int count = coincidences.count();
#if DEBUG_CONCIDENT
    if (count > 0) {
        SkDebugf("%s count=%d\n", __FUNCTION__, count);
    }
#endif
    // look for a lineup where the partial implies another adjoining coincidence
    for (int index = 0; index < count; ++index) {
        const SkCoincidence& coincidence = coincidences[index];
        int thisIndex = coincidence.fSegments[0];
        SkOpSegment& thisOne = fSegments[thisIndex];
        SkOpContour* otherContour = coincidence.fOther;
        int otherIndex = coincidence.fSegments[1];
        SkOpSegment& other = otherContour->fSegments[otherIndex];
        double startT = coincidence.fTs[0][0];
        double endT = coincidence.fTs[0][1];
        if (startT == endT) {  // this can happen in very large compares
            continue;
        }
        double oStartT = coincidence.fTs[1][0];
        double oEndT = coincidence.fTs[1][1];
        if (oStartT == oEndT) {
            continue;
        }
        bool swapStart = startT > endT;
        bool swapOther = oStartT > oEndT;
        if (swapStart) {
            SkTSwap<double>(startT, endT);
            SkTSwap<double>(oStartT, oEndT);
        }
        bool cancel = swapOther != swapStart;
        int step = swapStart ? -1 : 1;
        int oStep = swapOther ? -1 : 1;
        double oMatchStart = cancel ? oEndT : oStartT;
        if (partial ? startT != 0 || oMatchStart != 0 : (startT == 0) != (oMatchStart == 0)) {
            bool added = false;
            if (oMatchStart != 0) {
                added = thisOne.joinCoincidence(false, &other, oMatchStart, oStep, cancel);
            }
            if (startT != 0 && !added) {
                (void) other.joinCoincidence(cancel, &thisOne, startT, step, cancel);
            }
        }
        double oMatchEnd = cancel ? oStartT : oEndT;
        if (partial ? endT != 1 || oMatchEnd != 1 : (endT == 1) != (oMatchEnd == 1)) {
            bool added = false;
            if (oMatchEnd != 1) {
                added = thisOne.joinCoincidence(true, &other, oMatchEnd, -oStep, cancel);
            }
            if (endT != 1 && !added) {
                (void) other.joinCoincidence(!cancel, &thisOne, endT, -step, cancel);
            }
        }
    }
}

void SkOpContour::calcCommonCoincidentWinding(const SkCoincidence& coincidence) {
    int thisIndex = coincidence.fSegments[0];
    SkOpSegment& thisOne = fSegments[thisIndex];
    if (thisOne.done()) {
        return;
    }
    SkOpContour* otherContour = coincidence.fOther;
    int otherIndex = coincidence.fSegments[1];
    SkOpSegment& other = otherContour->fSegments[otherIndex];
    if (other.done()) {
        return;
    }
    double startT = coincidence.fTs[0][0];
    double endT = coincidence.fTs[0][1];
    const SkPoint* startPt = &coincidence.fPts[0];
    const SkPoint* endPt = &coincidence.fPts[1];
    bool cancelers;
    if ((cancelers = startT > endT)) {
        SkTSwap<double>(startT, endT);
        SkTSwap<const SkPoint*>(startPt, endPt);
    }
    if (startT == endT) { // if span is very large, the smaller may have collapsed to nothing
        if (endT <= 1 - FLT_EPSILON) {
            endT += FLT_EPSILON;
            SkASSERT(endT <= 1);
        } else {
            startT -= FLT_EPSILON;
            SkASSERT(startT >= 0);
        }
    }
    SkASSERT(!approximately_negative(endT - startT));
    double oStartT = coincidence.fTs[1][0];
    double oEndT = coincidence.fTs[1][1];
    if (oStartT > oEndT) {
        SkTSwap<double>(oStartT, oEndT);
        cancelers ^= true;
    }
    SkASSERT(!approximately_negative(oEndT - oStartT));
    if (cancelers) {
        thisOne.addTCancel(*startPt, *endPt, &other);
    } else {
        thisOne.addTCoincident(*startPt, *endPt, endT, &other);
    }
#if DEBUG_CONCIDENT
    thisOne.debugShowTs("p");
    other.debugShowTs("o");
#endif
}

void SkOpContour::sortSegments() {
    int segmentCount = fSegments.count();
    fSortedSegments.push_back_n(segmentCount);
    for (int test = 0; test < segmentCount; ++test) {
        fSortedSegments[test] = &fSegments[test];
    }
    SkTQSort<SkOpSegment>(fSortedSegments.begin(), fSortedSegments.end() - 1);
    fFirstSorted = 0;
}

void SkOpContour::toPath(SkPathWriter* path) const {
    int segmentCount = fSegments.count();
    const SkPoint& pt = fSegments.front().pts()[0];
    path->deferredMove(pt);
    for (int test = 0; test < segmentCount; ++test) {
        fSegments[test].addCurveTo(0, 1, path, true);
    }
    path->close();
}

void SkOpContour::topSortableSegment(const SkPoint& topLeft, SkPoint* bestXY,
        SkOpSegment** topStart) {
    int segmentCount = fSortedSegments.count();
    SkASSERT(segmentCount > 0);
    int sortedIndex = fFirstSorted;
    fDone = true;  // may be cleared below
    for ( ; sortedIndex < segmentCount; ++sortedIndex) {
        SkOpSegment* testSegment = fSortedSegments[sortedIndex];
        if (testSegment->done()) {
            if (sortedIndex == fFirstSorted) {
                ++fFirstSorted;
            }
            continue;
        }
        fDone = false;
        SkPoint testXY = testSegment->activeLeftTop(true, NULL);
        if (*topStart) {
            if (testXY.fY < topLeft.fY) {
                continue;
            }
            if (testXY.fY == topLeft.fY && testXY.fX < topLeft.fX) {
                continue;
            }
            if (bestXY->fY < testXY.fY) {
                continue;
            }
            if (bestXY->fY == testXY.fY && bestXY->fX < testXY.fX) {
                continue;
            }
        }
        *topStart = testSegment;
        *bestXY = testXY;
    }
}

SkOpSegment* SkOpContour::undoneSegment(int* start, int* end) {
    int segmentCount = fSegments.count();
    for (int test = 0; test < segmentCount; ++test) {
        SkOpSegment* testSegment = &fSegments[test];
        if (testSegment->done()) {
            continue;
        }
        testSegment->undoneSpan(start, end);
        return testSegment;
    }
    return NULL;
}

#if DEBUG_SHOW_WINDING
int SkOpContour::debugShowWindingValues(int totalSegments, int ofInterest) {
    int count = fSegments.count();
    int sum = 0;
    for (int index = 0; index < count; ++index) {
        sum += fSegments[index].debugShowWindingValues(totalSegments, ofInterest);
    }
//      SkDebugf("%s sum=%d\n", __FUNCTION__, sum);
    return sum;
}

void SkOpContour::debugShowWindingValues(const SkTArray<SkOpContour*, true>& contourList) {
//     int ofInterest = 1 << 1 | 1 << 5 | 1 << 9 | 1 << 13;
//    int ofInterest = 1 << 4 | 1 << 8 | 1 << 12 | 1 << 16;
    int ofInterest = 1 << 5 | 1 << 8;
    int total = 0;
    int index;
    for (index = 0; index < contourList.count(); ++index) {
        total += contourList[index]->segments().count();
    }
    int sum = 0;
    for (index = 0; index < contourList.count(); ++index) {
        sum += contourList[index]->debugShowWindingValues(total, ofInterest);
    }
//       SkDebugf("%s total=%d\n", __FUNCTION__, sum);
}
#endif

void SkOpContour::setBounds() {
    int count = fSegments.count();
    if (count == 0) {
        SkDebugf("%s empty contour\n", __FUNCTION__);
        SkASSERT(0);
        // FIXME: delete empty contour?
        return;
    }
    fBounds = fSegments.front().bounds();
    for (int index = 1; index < count; ++index) {
        fBounds.add(fSegments[index].bounds());
    }
}