path: root/src/pathops/SkPathOpsCommon.cpp

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

SkScalar ScaleFactor(const SkPath& path) {
    static const SkScalar twoTo10 = 1024.f;
    SkScalar largest = 0;
    const SkScalar* oneBounds = &path.getBounds().fLeft;
    for (int index = 0; index < 4; ++index) {
        largest = SkTMax(largest, SkScalarAbs(oneBounds[index]));
    }
    SkScalar scale = twoTo10;
    SkScalar next;
    while ((next = scale * twoTo10) < largest) {
        scale = next;
    }
    return scale == twoTo10 ? SK_Scalar1 : scale;
}

void ScalePath(const SkPath& path, SkScalar scale, SkPath* scaled) {
    SkMatrix matrix;
    matrix.setScale(scale, scale);
    *scaled = path;
    scaled->transform(matrix);
}

const SkOpAngle* AngleWinding(SkOpSpanBase* start, SkOpSpanBase* end, int* windingPtr,
        bool* sortablePtr) {
    // find first angle, initialize winding to computed fWindSum
    SkOpSegment* segment = start->segment();
    const SkOpAngle* angle = segment->spanToAngle(start, end);
    if (!angle) {
        *windingPtr = SK_MinS32;
        return nullptr;
    }
    bool computeWinding = false;
    const SkOpAngle* firstAngle = angle;
    bool loop = false;
    bool unorderable = false;
    int winding = SK_MinS32;
    do {
        angle = angle->next();
        if (!angle) {
            return nullptr;
        }
        unorderable |= angle->unorderable();
        if ((computeWinding = unorderable || (angle == firstAngle && loop))) {
            break;    // if we get here, there's no winding, loop is unorderable
        }
        loop |= angle == firstAngle;
        segment = angle->segment();
        winding = segment->windSum(angle);
    } while (winding == SK_MinS32);
    // if the angle loop contains an unorderable span, the angle order may be useless
    // directly compute the winding in this case for each span
    if (computeWinding) {
        firstAngle = angle;
        winding = SK_MinS32;
        do {
            SkOpSpanBase* startSpan = angle->start();
            SkOpSpanBase* endSpan = angle->end();
            SkOpSpan* lesser = startSpan->starter(endSpan);
            int testWinding = lesser->windSum();
            if (testWinding == SK_MinS32) {
                testWinding = lesser->computeWindSum();
            }
            if (testWinding != SK_MinS32) {
                segment = angle->segment();
                winding = testWinding;
            }
            angle = angle->next();
        } while (angle != firstAngle);
    }
    *sortablePtr = !unorderable;
    *windingPtr = winding;
    return angle;
}

SkOpSegment* FindUndone(SkOpContourHead* contourList, SkOpSpanBase** startPtr,
         SkOpSpanBase** endPtr) {
    SkOpSegment* result;
    SkOpContour* contour = contourList;
    do {
        result = contour->undoneSegment(startPtr, endPtr);
        if (result) {
            return result;
        }
    } while ((contour = contour->next()));
    return nullptr;
}

SkOpSegment* FindChase(SkTDArray<SkOpSpanBase*>* chase, SkOpSpanBase** startPtr,
        SkOpSpanBase** endPtr) {
    while (chase->count()) {
        SkOpSpanBase* span;
        chase->pop(&span);
        SkOpSegment* segment = span->segment();
        *startPtr = span->ptT()->next()->span();
        bool done = true;
        *endPtr = nullptr;
        if (SkOpAngle* last = segment->activeAngle(*startPtr, startPtr, endPtr, &done)) {
            *startPtr = last->start();
            *endPtr = last->end();
    #if TRY_ROTATE
            *chase->insert(0) = span;
    #else
            *chase->append() = span;
    #endif
            return last->segment();
        }
        if (done) {
            continue;
        }
        // find first angle, initialize winding to computed wind sum
        int winding;
        bool sortable;
        const SkOpAngle* angle = AngleWinding(*startPtr, *endPtr, &winding, &sortable);
        if (!angle) {
            return nullptr;
        }
        if (winding == SK_MinS32) {
            continue;
        }
        int sumWinding SK_INIT_TO_AVOID_WARNING;
        if (sortable) {
            segment = angle->segment();
            sumWinding = segment->updateWindingReverse(angle);
        }
        SkOpSegment* first = nullptr;
        const SkOpAngle* firstAngle = angle;
        while ((angle = angle->next()) != firstAngle) {
            segment = angle->segment();
            SkOpSpanBase* start = angle->start();
            SkOpSpanBase* end = angle->end();
            int maxWinding SK_INIT_TO_AVOID_WARNING;
            if (sortable) {
                segment->setUpWinding(start, end, &maxWinding, &sumWinding);
            }
            if (!segment->done(angle)) {
                if (!first && (sortable || start->starter(end)->windSum() != SK_MinS32)) {
                    first = segment;
                    *startPtr = start;
                    *endPtr = end;
                }
                // OPTIMIZATION: should this also add to the chase?
                if (sortable) {
                    (void) segment->markAngle(maxWinding, sumWinding, angle);
                }
            }
        }
        if (first) {
       #if TRY_ROTATE
            *chase->insert(0) = span;
       #else
            *chase->append() = span;
       #endif
            return first;
        }
    }
    return nullptr;
}

bool SortContourList(SkOpContourHead** contourList, bool evenOdd, bool oppEvenOdd) {
    SkTDArray<SkOpContour* > list;
    SkOpContour* contour = *contourList;
    do {
        if (contour->count()) {
            contour->setOppXor(contour->operand() ? evenOdd : oppEvenOdd);
            *list.append() = contour;
        }
    } while ((contour = contour->next()));
    int count = list.count();
    if (!count) {
        return false;
    }
    if (count > 1) {
        SkTQSort<SkOpContour>(list.begin(), list.end() - 1);
    }
    contour = list[0];
    SkOpContourHead* contourHead = static_cast<SkOpContourHead*>(contour);
    contour->globalState()->setContourHead(contourHead);
    *contourList = contourHead;
    for (int index = 1; index < count; ++index) {
        SkOpContour* next = list[index];
        contour->setNext(next);
        contour = next;
    }
    contour->setNext(nullptr);
    return true;
}

class DistanceLessThan {
public:
    DistanceLessThan(double* distances) : fDistances(distances) { }
    double* fDistances;
    bool operator()(const int one, const int two) {
        return fDistances[one] < fDistances[two];
    }
};

    /*
        check start and end of each contour
        if not the same, record them
        match them up
        connect closest
        reassemble contour pieces into new path
    */
void Assemble(const SkPathWriter& path, SkPathWriter* simple) {
    SkChunkAlloc allocator(4096);  // FIXME: constant-ize, tune
    SkOpContourHead contour;
    SkOpGlobalState globalState(&contour, &allocator  SkDEBUGPARAMS(false)
                                SkDEBUGPARAMS(nullptr));
#if DEBUG_SHOW_TEST_NAME
    SkDebugf("</div>\n");
#endif
#if DEBUG_PATH_CONSTRUCTION
    SkDebugf("%s\n", __FUNCTION__);
#endif
    SkOpEdgeBuilder builder(path, &contour, &globalState);
    builder.finish();
    SkTDArray<const SkOpContour* > runs;  // indices of partial contours
    const SkOpContour* eContour = builder.head();
    do {
        if (!eContour->count()) {
            continue;
        }
        const SkPoint& eStart = eContour->start();
        const SkPoint& eEnd = eContour->end();
#if DEBUG_ASSEMBLE
        SkDebugf("%s contour", __FUNCTION__);
        if (!SkDPoint::ApproximatelyEqual(eStart, eEnd)) {
            SkDebugf("[%d]", runs.count());
        } else {
            SkDebugf("   ");
        }
        SkDebugf(" start=(%1.9g,%1.9g) end=(%1.9g,%1.9g)\n",
                eStart.fX, eStart.fY, eEnd.fX, eEnd.fY);
#endif
        if (SkDPoint::ApproximatelyEqual(eStart, eEnd)) {
            eContour->toPath(simple);
            continue;
        }
        *runs.append() = eContour;
    } while ((eContour = eContour->next()));
    int count = runs.count();
    if (count == 0) {
        return;
    }
    SkTDArray<int> sLink, eLink;
    sLink.append(count);
    eLink.append(count);
    int rIndex, iIndex;
    for (rIndex = 0; rIndex < count; ++rIndex) {
        sLink[rIndex] = eLink[rIndex] = SK_MaxS32;
    }
    const int ends = count * 2;  // all starts and ends
    const int entries = (ends - 1) * count;  // folded triangle : n * (n - 1) / 2
    SkTDArray<double> distances;
    distances.append(entries);
    for (rIndex = 0; rIndex < ends - 1; ++rIndex) {
        const SkOpContour* oContour = runs[rIndex >> 1];
        const SkPoint& oPt = rIndex & 1 ? oContour->end() : oContour->start();
        const int row = rIndex < count - 1 ? rIndex * ends : (ends - rIndex - 2)
                * ends - rIndex - 1;
        for (iIndex = rIndex + 1; iIndex < ends; ++iIndex) {
            const SkOpContour* iContour = runs[iIndex >> 1];
            const SkPoint& iPt = iIndex & 1 ? iContour->end() : iContour->start();
            double dx = iPt.fX - oPt.fX;
            double dy = iPt.fY - oPt.fY;
            double dist = dx * dx + dy * dy;
            distances[row + iIndex] = dist;  // oStart distance from iStart
        }
    }
    SkTDArray<int> sortedDist;
    sortedDist.append(entries);
    for (rIndex = 0; rIndex < entries; ++rIndex) {
        sortedDist[rIndex] = rIndex;
    }
    SkTQSort<int>(sortedDist.begin(), sortedDist.end() - 1, DistanceLessThan(distances.begin()));
    int remaining = count;  // number of start/end pairs
    for (rIndex = 0; rIndex < entries; ++rIndex) {
        int pair = sortedDist[rIndex];
        int row = pair / ends;
        int col = pair - row * ends;
        int thingOne = row < col ? row : ends - row - 2;
        int ndxOne = thingOne >> 1;
        bool endOne = thingOne & 1;
        int* linkOne = endOne ? eLink.begin() : sLink.begin();
        if (linkOne[ndxOne] != SK_MaxS32) {
            continue;
        }
        int thingTwo = row < col ? col : ends - row + col - 1;
        int ndxTwo = thingTwo >> 1;
        bool endTwo = thingTwo & 1;
        int* linkTwo = endTwo ? eLink.begin() : sLink.begin();
        if (linkTwo[ndxTwo] != SK_MaxS32) {
            continue;
        }
        SkASSERT(&linkOne[ndxOne] != &linkTwo[ndxTwo]);
        bool flip = endOne == endTwo;
        linkOne[ndxOne] = flip ? ~ndxTwo : ndxTwo;
        linkTwo[ndxTwo] = flip ? ~ndxOne : ndxOne;
        if (!--remaining) {
            break;
        }
    }
    SkASSERT(!remaining);
#if DEBUG_ASSEMBLE
    for (rIndex = 0; rIndex < count; ++rIndex) {
        int s = sLink[rIndex];
        int e = eLink[rIndex];
        SkDebugf("%s %c%d <- s%d - e%d -> %c%d\n", __FUNCTION__, s < 0 ? 's' : 'e',
                s < 0 ? ~s : s, rIndex, rIndex, e < 0 ? 'e' : 's', e < 0 ? ~e : e);
    }
#endif
    rIndex = 0;
    do {
        bool forward = true;
        bool first = true;
        int sIndex = sLink[rIndex];
        SkASSERT(sIndex != SK_MaxS32);
        sLink[rIndex] = SK_MaxS32;
        int eIndex;
        if (sIndex < 0) {
            eIndex = sLink[~sIndex];
            sLink[~sIndex] = SK_MaxS32;
        } else {
            eIndex = eLink[sIndex];
            eLink[sIndex] = SK_MaxS32;
        }
        SkASSERT(eIndex != SK_MaxS32);
#if DEBUG_ASSEMBLE
        SkDebugf("%s sIndex=%c%d eIndex=%c%d\n", __FUNCTION__, sIndex < 0 ? 's' : 'e',
                    sIndex < 0 ? ~sIndex : sIndex, eIndex < 0 ? 's' : 'e',
                    eIndex < 0 ? ~eIndex : eIndex);
#endif
        do {
            const SkOpContour* contour = runs[rIndex];
            if (first) {
                first = false;
                const SkPoint* startPtr = &contour->start();
                simple->deferredMove(startPtr[0]);
            }
            if (forward) {
                contour->toPartialForward(simple);
            } else {
                contour->toPartialBackward(simple);
            }
#if DEBUG_ASSEMBLE
            SkDebugf("%s rIndex=%d eIndex=%s%d close=%d\n", __FUNCTION__, rIndex,
                eIndex < 0 ? "~" : "", eIndex < 0 ? ~eIndex : eIndex,
                sIndex == ((rIndex != eIndex) ^ forward ? eIndex : ~eIndex));
#endif
            if (sIndex == ((rIndex != eIndex) ^ forward ? eIndex : ~eIndex)) {
                simple->close();
                break;
            }
            if (forward) {
                eIndex = eLink[rIndex];
                SkASSERT(eIndex != SK_MaxS32);
                eLink[rIndex] = SK_MaxS32;
                if (eIndex >= 0) {
                    SkASSERT(sLink[eIndex] == rIndex);
                    sLink[eIndex] = SK_MaxS32;
                } else {
                    SkASSERT(eLink[~eIndex] == ~rIndex);
                    eLink[~eIndex] = SK_MaxS32;
                }
            } else {
                eIndex = sLink[rIndex];
                SkASSERT(eIndex != SK_MaxS32);
                sLink[rIndex] = SK_MaxS32;
                if (eIndex >= 0) {
                    SkASSERT(eLink[eIndex] == rIndex);
                    eLink[eIndex] = SK_MaxS32;
                } else {
                    SkASSERT(sLink[~eIndex] == ~rIndex);
                    sLink[~eIndex] = SK_MaxS32;
                }
            }
            rIndex = eIndex;
            if (rIndex < 0) {
                forward ^= 1;
                rIndex = ~rIndex;
            }
        } while (true);
        for (rIndex = 0; rIndex < count; ++rIndex) {
            if (sLink[rIndex] != SK_MaxS32) {
                break;
            }
        }
    } while (rIndex < count);
#if DEBUG_ASSEMBLE
    for (rIndex = 0; rIndex < count; ++rIndex) {
       SkASSERT(sLink[rIndex] == SK_MaxS32);
       SkASSERT(eLink[rIndex] == SK_MaxS32);
    }
#endif
}

static void calcAngles(SkOpContourHead* contourList) {
    SkOpContour* contour = contourList;
    do {
        contour->calcAngles();
    } while ((contour = contour->next()));
}

static bool missingCoincidence(SkOpContourHead* contourList) {
    SkOpContour* contour = contourList;
    bool result = false;
    do {
        result |= contour->missingCoincidence();
    } while ((contour = contour->next()));
    return result;
}

static bool moveMultiples(SkOpContourHead* contourList) {
    SkOpContour* contour = contourList;
    do {
        if (!contour->moveMultiples()) {
            return false;
        }
    } while ((contour = contour->next()));
    return true;
}

static void moveNearby(SkOpContourHead* contourList) {
    SkOpContour* contour = contourList;
    do {
        contour->moveNearby();
    } while ((contour = contour->next()));
}

static void sortAngles(SkOpContourHead* contourList) {
    SkOpContour* contour = contourList;
    do {
        contour->sortAngles();
    } while ((contour = contour->next()));
}

bool HandleCoincidence(SkOpContourHead* contourList, SkOpCoincidence* coincidence) {
    SkOpGlobalState* globalState = contourList->globalState();
    DEBUG_COINCIDENCE_HEALTH(contourList, "start");
#if DEBUG_VALIDATE
    globalState->setPhase(SkOpGlobalState::kIntersecting);
#endif

    // match up points within the coincident runs
    if (!coincidence->addExpanded()) {
        return false;
    }
    DEBUG_COINCIDENCE_HEALTH(contourList, "addExpanded");
#if DEBUG_VALIDATE
    globalState->setPhase(SkOpGlobalState::kWalking);
#endif
    // combine t values when multiple intersections occur on some segments but not others
    if (!moveMultiples(contourList)) {
        return false;
    }
    DEBUG_COINCIDENCE_HEALTH(contourList, "moveMultiples");
    // move t values and points together to eliminate small/tiny gaps
    (void) moveNearby(contourList);
    DEBUG_COINCIDENCE_HEALTH(contourList, "moveNearby");
#if DEBUG_VALIDATE
    globalState->setPhase(SkOpGlobalState::kIntersecting);
#endif
    // add coincidence formed by pairing on curve points and endpoints
    coincidence->correctEnds();
    if (!coincidence->addEndMovedSpans()) {
        return false;
    }
    DEBUG_COINCIDENCE_HEALTH(contourList, "addEndMovedSpans");

    const int SAFETY_COUNT = 100;  // FIXME: tune
    int safetyHatch = SAFETY_COUNT;
    // look for coincidence present in A-B and A-C but missing in B-C
    while (coincidence->addMissing()) {
        if (!--safetyHatch) {
            SkASSERT(0);  // FIXME: take this out after verifying std tests don't trigger
            return false;
        }
        DEBUG_COINCIDENCE_HEALTH(contourList, "addMissing");
        moveNearby(contourList);
        DEBUG_COINCIDENCE_HEALTH(contourList, "moveNearby");
    }
    DEBUG_COINCIDENCE_HEALTH(contourList, "addMissing2");
    // FIXME: only call this if addMissing modified something when returning false
    moveNearby(contourList);
    DEBUG_COINCIDENCE_HEALTH(contourList, "moveNearby2");
    // check to see if, loosely, coincident ranges may be expanded
    if (coincidence->expand()) {
        DEBUG_COINCIDENCE_HEALTH(contourList, "expand1");
        coincidence->addMissing();
        DEBUG_COINCIDENCE_HEALTH(contourList, "addMissing2");
        if (!coincidence->addExpanded()) {
            return false;
        }
        DEBUG_COINCIDENCE_HEALTH(contourList, "addExpanded2");
        if (!moveMultiples(contourList)) {
            return false;
        }
        DEBUG_COINCIDENCE_HEALTH(contourList, "moveMultiples2");
        moveNearby(contourList);
    }
#if DEBUG_VALIDATE
    globalState->setPhase(SkOpGlobalState::kWalking);
#endif
    DEBUG_COINCIDENCE_HEALTH(contourList, "expand2");
    // the expanded ranges may not align -- add the missing spans
    if (!coincidence->addExpanded()) {
        SkASSERT(globalState->debugSkipAssert());
        return false;
    }
    DEBUG_COINCIDENCE_HEALTH(contourList, "addExpanded3");
    coincidence->correctEnds();
    if (!coincidence->mark()) {  // mark spans of coincident segments as coincident
        return false;
    }
    DEBUG_COINCIDENCE_HEALTH(contourList, "mark1");
    // look for coincidence lines and curves undetected by intersection
    if (missingCoincidence(contourList)) {
#if DEBUG_VALIDATE
        globalState->setPhase(SkOpGlobalState::kIntersecting);
#endif
        DEBUG_COINCIDENCE_HEALTH(contourList, "missingCoincidence1");
        (void) coincidence->expand();
        DEBUG_COINCIDENCE_HEALTH(contourList, "expand3");
        if (!coincidence->addExpanded()) {
            return false;
        }
#if DEBUG_VALIDATE
        globalState->setPhase(SkOpGlobalState::kWalking);
#endif
        DEBUG_COINCIDENCE_HEALTH(contourList, "addExpanded3");
        if (!coincidence->mark()) {
            return false;
        }
    } else {
        DEBUG_COINCIDENCE_HEALTH(contourList, "missingCoincidence2");
        (void) coincidence->expand();
    }
    DEBUG_COINCIDENCE_HEALTH(contourList, "missingCoincidence3");

    (void) coincidence->expand();

#if 0  // under development
    // coincident runs may cross two or more spans, but the opposite spans may be out of order
    if (!coincidence->reorder()) {
      return false;
    }
#endif
    DEBUG_COINCIDENCE_HEALTH(contourList, "coincidence.reorder");
    SkOpCoincidence overlaps(globalState);
    do {
        SkOpCoincidence* pairs = overlaps.isEmpty() ? coincidence : &overlaps;
        if (!pairs->apply()) {  // adjust the winding value to account for coincident edges
            return false;
        }
        DEBUG_COINCIDENCE_HEALTH(contourList, "pairs->apply");
        // For each coincident pair that overlaps another, when the receivers (the 1st of the pair)
        // are different, construct a new pair to resolve their mutual span
        if (!pairs->findOverlaps(&overlaps)) {
            return false;
        }
        DEBUG_COINCIDENCE_HEALTH(contourList, "pairs->findOverlaps");
    } while (!overlaps.isEmpty());
    calcAngles(contourList);
    sortAngles(contourList);
    if (globalState->angleCoincidence()) {
        (void) missingCoincidence(contourList);
        if (!coincidence->apply()) {
            return false;
        }
    }
#if DEBUG_COINCIDENCE_VERBOSE
    coincidence->debugShowCoincidence();
#endif
#if DEBUG_COINCIDENCE
    coincidence->debugValidate();
#endif
    SkPathOpsDebug::ShowActiveSpans(contourList);
    return true;
}