src/pathops/SkPathOpsOp.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 "include/core/SkPath.h"
#include "include/core/SkPathTypes.h"
#include "include/core/SkRect.h"
#include "include/core/SkTypes.h"
#include "include/pathops/SkPathOps.h"
#include "include/private/base/SkMath.h"
#include "include/private/base/SkTDArray.h"
#include "src/base/SkArenaAlloc.h"
#include "src/pathops/SkAddIntersections.h"
#include "src/pathops/SkOpAngle.h"
#include "src/pathops/SkOpCoincidence.h"
#include "src/pathops/SkOpContour.h"
#include "src/pathops/SkOpEdgeBuilder.h"
#include "src/pathops/SkOpSegment.h"
#include "src/pathops/SkOpSpan.h"
#include "src/pathops/SkPathOpsCommon.h"
#include "src/pathops/SkPathOpsTypes.h"
#include "src/pathops/SkPathWriter.h"

#include <utility>

static bool findChaseOp(SkTDArray<SkOpSpanBase*>& chase, SkOpSpanBase** startPtr,
        SkOpSpanBase** endPtr, SkOpSegment** result) {
    while (!chase.empty()) {
        SkOpSpanBase* span = chase.back();
        chase.pop_back();
        // OPTIMIZE: prev makes this compatible with old code -- but is it necessary?
        *startPtr = span->ptT()->prev()->span();
        SkOpSegment* segment = (*startPtr)->segment();
        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
            *result = last->segment();
            return true;
        }
        if (done) {
            continue;
        }
        int winding;
        bool sortable;
        const SkOpAngle* angle = AngleWinding(*startPtr, *endPtr, &winding, &sortable);
        if (!angle) {
            *result = nullptr;
            return true;
        }
        if (winding == SK_MinS32) {
            continue;
        }
        int sumMiWinding, sumSuWinding;
        if (sortable) {
            segment = angle->segment();
            sumMiWinding = segment->updateWindingReverse(angle);
            if (sumMiWinding == SK_MinS32) {
                SkASSERT(segment->globalState()->debugSkipAssert());
                *result = nullptr;
                return true;
            }
            sumSuWinding = segment->updateOppWindingReverse(angle);
            if (sumSuWinding == SK_MinS32) {
                SkASSERT(segment->globalState()->debugSkipAssert());
                *result = nullptr;
                return true;
            }
            if (segment->operand()) {
                using std::swap;
                swap(sumMiWinding, sumSuWinding);
            }
        }
        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 = 0, sumWinding = 0, oppMaxWinding = 0, oppSumWinding = 0;
            if (sortable) {
                segment->setUpWindings(start, end, &sumMiWinding, &sumSuWinding,
                        &maxWinding, &sumWinding, &oppMaxWinding, &oppSumWinding);
            }
            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) {
                    if (!segment->markAngle(maxWinding, sumWinding, oppMaxWinding,
                            oppSumWinding, angle, nullptr)) {
                        return false;
                    }
                }
            }
        }
        if (first) {
       #if TRY_ROTATE
            *chase.insert(0) = span;
       #else
            *chase.append() = span;
       #endif
            *result = first;
            return true;
        }
    }
    *result = nullptr;
    return true;
}

static bool bridgeOp(SkOpContourHead* contourList, const SkPathOp op,
        const int xorMask, const int xorOpMask, SkPathWriter* writer) {
    bool unsortable = false;
    bool lastSimple = false;
    bool simple = false;
    do {
        SkOpSpan* span = FindSortableTop(contourList);
        if (!span) {
            break;
        }
        SkOpSegment* current = span->segment();
        SkOpSpanBase* start = span->next();
        SkOpSpanBase* end = span;
        SkTDArray<SkOpSpanBase*> chase;
        do {
            if (current->activeOp(start, end, xorMask, xorOpMask, op)) {
                do {
                    if (!unsortable && current->done()) {
                        break;
                    }
                    SkASSERT(unsortable || !current->done());
                    SkOpSpanBase* nextStart = start;
                    SkOpSpanBase* nextEnd = end;
                    lastSimple = simple;
                    SkOpSegment* next = current->findNextOp(&chase, &nextStart, &nextEnd,
                            &unsortable, &simple, op, xorMask, xorOpMask);
                    if (!next) {
                        if (!unsortable && writer->hasMove()
                                && current->verb() != SkPath::kLine_Verb
                                && !writer->isClosed()) {
                            if (!current->addCurveTo(start, end, writer)) {
                                return false;
                            }
                            if (!writer->isClosed()) {
                                SkPathOpsDebug::ShowActiveSpans(contourList);
                            }
                        } else if (lastSimple) {
                            if (!current->addCurveTo(start, end, writer)) {
                                return false;
                            }
                        }
                        break;
                    }
        #if DEBUG_FLOW
                    SkDebugf("%s current id=%d from=(%1.9g,%1.9g) to=(%1.9g,%1.9g)\n", __FUNCTION__,
                            current->debugID(), start->pt().fX, start->pt().fY,
                            end->pt().fX, end->pt().fY);
        #endif
                    if (!current->addCurveTo(start, end, writer)) {
                        return false;
                    }
                    current = next;
                    start = nextStart;
                    end = nextEnd;
                } while (!writer->isClosed() && (!unsortable || !start->starter(end)->done()));
                if (current->activeWinding(start, end) && !writer->isClosed()) {
                    SkOpSpan* spanStart = start->starter(end);
                    if (!spanStart->done()) {
                        if (!current->addCurveTo(start, end, writer)) {
                            return false;
                        }
                        current->markDone(spanStart);
                    }
                }
                writer->finishContour();
            } else {
                SkOpSpanBase* last;
                if (!current->markAndChaseDone(start, end, &last)) {
                    return false;
                }
                if (last && !last->chased()) {
                    last->setChased(true);
                    SkASSERT(!SkPathOpsDebug::ChaseContains(chase, last));
                    *chase.append() = last;
#if DEBUG_WINDING
                    SkDebugf("%s chase.append id=%d", __FUNCTION__, last->segment()->debugID());
                    if (!last->final()) {
                         SkDebugf(" windSum=%d", last->upCast()->windSum());
                    }
                    SkDebugf("\n");
#endif
                }
            }
            if (!findChaseOp(chase, &start, &end, &current)) {
                return false;
            }
            SkPathOpsDebug::ShowActiveSpans(contourList);
            if (!current) {
                break;
            }
        } while (true);
    } while (true);
    return true;
}

// diagram of why this simplifcation is possible is here:
// https://skia.org/dev/present/pathops link at bottom of the page
// https://drive.google.com/file/d/0BwoLUwz9PYkHLWpsaXd0UDdaN00/view?usp=sharing
static const SkPathOp gOpInverse[kReverseDifference_SkPathOp + 1][2][2] = {
//                  inside minuend                               outside minuend
//     inside subtrahend     outside subtrahend      inside subtrahend     outside subtrahend
{{ kDifference_SkPathOp,   kIntersect_SkPathOp }, { kUnion_SkPathOp, kReverseDifference_SkPathOp }},
{{ kIntersect_SkPathOp,   kDifference_SkPathOp }, { kReverseDifference_SkPathOp, kUnion_SkPathOp }},
{{ kUnion_SkPathOp, kReverseDifference_SkPathOp }, { kDifference_SkPathOp,   kIntersect_SkPathOp }},
{{ kXOR_SkPathOp,                 kXOR_SkPathOp }, { kXOR_SkPathOp,                kXOR_SkPathOp }},
{{ kReverseDifference_SkPathOp, kUnion_SkPathOp }, { kIntersect_SkPathOp,   kDifference_SkPathOp }},
};

static const bool gOutInverse[kReverseDifference_SkPathOp + 1][2][2] = {
    {{ false, false }, { true, false }},  // diff
    {{ false, false }, { false, true }},  // sect
    {{ false, true }, { true, true }},    // union
    {{ false, true }, { true, false }},   // xor
    {{ false, true }, { false, false }},  // rev diff
};

#if DEBUG_T_SECT_LOOP_COUNT

#include "include/private/base/SkMutex.h"

SkOpGlobalState debugWorstState(nullptr, nullptr  SkDEBUGPARAMS(false) SkDEBUGPARAMS(nullptr));

void ReportPathOpsDebugging() {
    debugWorstState.debugLoopReport();
}

extern void (*gVerboseFinalize)();

#endif

std::optional<SkPath> OpDebug(const SkPath& one, const SkPath& two, SkPathOp op
        SkDEBUGPARAMS(bool skipAssert) SkDEBUGPARAMS(const char* testName)) {
#if DEBUG_DUMP_VERIFY
#ifndef SK_DEBUG
    const char* testName = "release";
#endif
    if (SkPathOpsDebug::gDumpOp) {
        DumpOp(one, two, op, testName);
    }
#endif
    op = gOpInverse[op][one.isInverseFillType()][two.isInverseFillType()];
    bool inverseFill = gOutInverse[op][one.isInverseFillType()][two.isInverseFillType()];
    SkPathFillType fillType = inverseFill ? SkPathFillType::kInverseEvenOdd :
            SkPathFillType::kEvenOdd;
    SkRect rect1, rect2;
    if (kIntersect_SkPathOp == op && one.isRect(&rect1) && two.isRect(&rect2)) {
        SkPath result = rect1.intersect(rect2) ? SkPath::Rect(rect1)
                                               : SkPath();
        return result.makeFillType(fillType);
    }
    if (one.isEmpty() || two.isEmpty()) {
        SkPath work;
        switch (op) {
            case kIntersect_SkPathOp:
                break;
            case kUnion_SkPathOp:
            case kXOR_SkPathOp:
                work = one.isEmpty() ? two : one;
                break;
            case kDifference_SkPathOp:
                if (!one.isEmpty()) {
                    work = one;
                }
                break;
            case kReverseDifference_SkPathOp:
                if (!two.isEmpty()) {
                    work = two;
                }
                break;
            default:
                SkASSERT(0);  // unhandled case
        }
        if (inverseFill != work.isInverseFillType()) {
            work.toggleInverseFillType();
        }
        return Simplify(work);
    }
    SkSTArenaAlloc<4096> allocator;  // FIXME: add a constant expression here, tune
    SkOpContour contour;
    SkOpContourHead* contourList = static_cast<SkOpContourHead*>(&contour);
    SkOpGlobalState globalState(contourList, &allocator
            SkDEBUGPARAMS(skipAssert) SkDEBUGPARAMS(testName));
    SkOpCoincidence coincidence(&globalState);
    const SkPath* minuend = &one;
    const SkPath* subtrahend = &two;
    if (op == kReverseDifference_SkPathOp) {
        using std::swap;
        swap(minuend, subtrahend);
        op = kDifference_SkPathOp;
    }
#if DEBUG_SORT
    SkPathOpsDebug::gSortCount = SkPathOpsDebug::gSortCountDefault;
#endif
    // turn path into list of segments
    SkOpEdgeBuilder builder(*minuend, contourList, &globalState);
    if (builder.unparseable()) {
        return {};
    }
    const int xorMask = builder.xorMask();
    builder.addOperand(*subtrahend);
    if (!builder.finish()) {
        return {};
    }
#if DEBUG_DUMP_SEGMENTS
    contourList->dumpSegments("seg", op);
#endif

    const int xorOpMask = builder.xorMask();
    if (!SortContourList(&contourList, xorMask == kEvenOdd_PathOpsMask,
            xorOpMask == kEvenOdd_PathOpsMask)) {
        return SkPath().makeFillType(fillType);
    }
    // find all intersections between segments
    SkOpContour* current = contourList;
    do {
        SkOpContour* next = current;
        while (AddIntersectTs(current, next, &coincidence)
                && (next = next->next()))
            ;
    } while ((current = current->next()));
#if DEBUG_VALIDATE
    globalState.setPhase(SkOpPhase::kWalking);
#endif
    bool success = HandleCoincidence(contourList, &coincidence);
#if DEBUG_COIN
    globalState.debugAddToGlobalCoinDicts();
#endif
    if (!success) {
        return {};
    }
#if DEBUG_ALIGNMENT
    contourList->dumpSegments("aligned");
#endif
    // construct closed contours
    SkPathWriter wrapper(fillType);
    if (!bridgeOp(contourList, op, xorMask, xorOpMask, &wrapper)) {
        return {};
    }
    wrapper.assemble();  // if some edges could not be resolved, assemble remaining
    SkPath result = wrapper.nativePath();
#if DEBUG_T_SECT_LOOP_COUNT
    static SkMutex& debugWorstLoop = *(new SkMutex);
    {
        SkAutoMutexExclusive autoM(debugWorstLoop);
        if (!gVerboseFinalize) {
            gVerboseFinalize = &ReportPathOpsDebugging;
        }
        debugWorstState.debugDoYourWorst(&globalState);
    }
#endif
    return result;
}

std::optional<SkPath> Op(const SkPath& one, const SkPath& two, SkPathOp op) {
#if DEBUG_DUMP_VERIFY
    if (SkPathOpsDebug::gVerifyOp) {
        if (auto result = OpDebug(one, two, op  SkDEBUGPARAMS(false) SkDEBUGPARAMS(nullptr))) {
            VerifyOp(one, two, op, &result.value());
            return *result;
        } else {
            ReportOpFail(one, two, op);
            return {};
        }
    }
#endif
    if (auto result = OpDebug(one, two, op  SkDEBUGPARAMS(true) SkDEBUGPARAMS(nullptr))) {
        return *result;
    }
    return {};
}