tor-browser

The Tor Browser
git clone https://git.dasho.dev/tor-browser.git
Log | Files | Refs | README | LICENSE

SkPathOpsOp.cpp (14542B)

      1 /*
      2 * Copyright 2012 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 "include/core/SkPath.h"
      8 #include "include/core/SkPathTypes.h"
      9 #include "include/core/SkRect.h"
     10 #include "include/core/SkTypes.h"
     11 #include "include/pathops/SkPathOps.h"
     12 #include "include/private/base/SkMath.h"
     13 #include "include/private/base/SkTDArray.h"
     14 #include "src/base/SkArenaAlloc.h"
     15 #include "src/pathops/SkAddIntersections.h"
     16 #include "src/pathops/SkOpAngle.h"
     17 #include "src/pathops/SkOpCoincidence.h"
     18 #include "src/pathops/SkOpContour.h"
     19 #include "src/pathops/SkOpEdgeBuilder.h"
     20 #include "src/pathops/SkOpSegment.h"
     21 #include "src/pathops/SkOpSpan.h"
     22 #include "src/pathops/SkPathOpsCommon.h"
     23 #include "src/pathops/SkPathOpsTypes.h"
     24 #include "src/pathops/SkPathWriter.h"
     25 
     26 #include <utility>
     27 
     28 static bool findChaseOp(SkTDArray<SkOpSpanBase*>& chase, SkOpSpanBase** startPtr,
     29        SkOpSpanBase** endPtr, SkOpSegment** result) {
     30    while (!chase.empty()) {
     31        SkOpSpanBase* span = chase.back();
     32        chase.pop_back();
     33        // OPTIMIZE: prev makes this compatible with old code -- but is it necessary?
     34        *startPtr = span->ptT()->prev()->span();
     35        SkOpSegment* segment = (*startPtr)->segment();
     36        bool done = true;
     37        *endPtr = nullptr;
     38        if (SkOpAngle* last = segment->activeAngle(*startPtr, startPtr, endPtr, &done)) {
     39            *startPtr = last->start();
     40            *endPtr = last->end();
     41   #if TRY_ROTATE
     42            *chase.insert(0) = span;
     43   #else
     44            *chase.append() = span;
     45   #endif
     46            *result = last->segment();
     47            return true;
     48        }
     49        if (done) {
     50            continue;
     51        }
     52        int winding;
     53        bool sortable;
     54        const SkOpAngle* angle = AngleWinding(*startPtr, *endPtr, &winding, &sortable);
     55        if (!angle) {
     56            *result = nullptr;
     57            return true;
     58        }
     59        if (winding == SK_MinS32) {
     60            continue;
     61        }
     62        int sumMiWinding, sumSuWinding;
     63        if (sortable) {
     64            segment = angle->segment();
     65            sumMiWinding = segment->updateWindingReverse(angle);
     66            if (sumMiWinding == SK_MinS32) {
     67                SkASSERT(segment->globalState()->debugSkipAssert());
     68                *result = nullptr;
     69                return true;
     70            }
     71            sumSuWinding = segment->updateOppWindingReverse(angle);
     72            if (sumSuWinding == SK_MinS32) {
     73                SkASSERT(segment->globalState()->debugSkipAssert());
     74                *result = nullptr;
     75                return true;
     76            }
     77            if (segment->operand()) {
     78                using std::swap;
     79                swap(sumMiWinding, sumSuWinding);
     80            }
     81        }
     82        SkOpSegment* first = nullptr;
     83        const SkOpAngle* firstAngle = angle;
     84        while ((angle = angle->next()) != firstAngle) {
     85            segment = angle->segment();
     86            SkOpSpanBase* start = angle->start();
     87            SkOpSpanBase* end = angle->end();
     88            int maxWinding = 0, sumWinding = 0, oppMaxWinding = 0, oppSumWinding = 0;
     89            if (sortable) {
     90                segment->setUpWindings(start, end, &sumMiWinding, &sumSuWinding,
     91                        &maxWinding, &sumWinding, &oppMaxWinding, &oppSumWinding);
     92            }
     93            if (!segment->done(angle)) {
     94                if (!first && (sortable || start->starter(end)->windSum() != SK_MinS32)) {
     95                    first = segment;
     96                    *startPtr = start;
     97                    *endPtr = end;
     98                }
     99                // OPTIMIZATION: should this also add to the chase?
    100                if (sortable) {
    101                    if (!segment->markAngle(maxWinding, sumWinding, oppMaxWinding,
    102                            oppSumWinding, angle, nullptr)) {
    103                        return false;
    104                    }
    105                }
    106            }
    107        }
    108        if (first) {
    109       #if TRY_ROTATE
    110            *chase.insert(0) = span;
    111       #else
    112            *chase.append() = span;
    113       #endif
    114            *result = first;
    115            return true;
    116        }
    117    }
    118    *result = nullptr;
    119    return true;
    120 }
    121 
    122 static bool bridgeOp(SkOpContourHead* contourList, const SkPathOp op,
    123        const int xorMask, const int xorOpMask, SkPathWriter* writer) {
    124    bool unsortable = false;
    125    bool lastSimple = false;
    126    bool simple = false;
    127    do {
    128        SkOpSpan* span = FindSortableTop(contourList);
    129        if (!span) {
    130            break;
    131        }
    132        SkOpSegment* current = span->segment();
    133        SkOpSpanBase* start = span->next();
    134        SkOpSpanBase* end = span;
    135        SkTDArray<SkOpSpanBase*> chase;
    136        do {
    137            if (current->activeOp(start, end, xorMask, xorOpMask, op)) {
    138                do {
    139                    if (!unsortable && current->done()) {
    140                        break;
    141                    }
    142                    SkASSERT(unsortable || !current->done());
    143                    SkOpSpanBase* nextStart = start;
    144                    SkOpSpanBase* nextEnd = end;
    145                    lastSimple = simple;
    146                    SkOpSegment* next = current->findNextOp(&chase, &nextStart, &nextEnd,
    147                            &unsortable, &simple, op, xorMask, xorOpMask);
    148                    if (!next) {
    149                        if (!unsortable && writer->hasMove()
    150                                && current->verb() != SkPath::kLine_Verb
    151                                && !writer->isClosed()) {
    152                            if (!current->addCurveTo(start, end, writer)) {
    153                                return false;
    154                            }
    155                            if (!writer->isClosed()) {
    156                                SkPathOpsDebug::ShowActiveSpans(contourList);
    157                            }
    158                        } else if (lastSimple) {
    159                            if (!current->addCurveTo(start, end, writer)) {
    160                                return false;
    161                            }
    162                        }
    163                        break;
    164                    }
    165        #if DEBUG_FLOW
    166                    SkDebugf("%s current id=%d from=(%1.9g,%1.9g) to=(%1.9g,%1.9g)\n", __FUNCTION__,
    167                            current->debugID(), start->pt().fX, start->pt().fY,
    168                            end->pt().fX, end->pt().fY);
    169        #endif
    170                    if (!current->addCurveTo(start, end, writer)) {
    171                        return false;
    172                    }
    173                    current = next;
    174                    start = nextStart;
    175                    end = nextEnd;
    176                } while (!writer->isClosed() && (!unsortable || !start->starter(end)->done()));
    177                if (current->activeWinding(start, end) && !writer->isClosed()) {
    178                    SkOpSpan* spanStart = start->starter(end);
    179                    if (!spanStart->done()) {
    180                        if (!current->addCurveTo(start, end, writer)) {
    181                            return false;
    182                        }
    183                        current->markDone(spanStart);
    184                    }
    185                }
    186                writer->finishContour();
    187            } else {
    188                SkOpSpanBase* last;
    189                if (!current->markAndChaseDone(start, end, &last)) {
    190                    return false;
    191                }
    192                if (last && !last->chased()) {
    193                    last->setChased(true);
    194                    SkASSERT(!SkPathOpsDebug::ChaseContains(chase, last));
    195                    *chase.append() = last;
    196 #if DEBUG_WINDING
    197                    SkDebugf("%s chase.append id=%d", __FUNCTION__, last->segment()->debugID());
    198                    if (!last->final()) {
    199                         SkDebugf(" windSum=%d", last->upCast()->windSum());
    200                    }
    201                    SkDebugf("\n");
    202 #endif
    203                }
    204            }
    205            if (!findChaseOp(chase, &start, &end, &current)) {
    206                return false;
    207            }
    208            SkPathOpsDebug::ShowActiveSpans(contourList);
    209            if (!current) {
    210                break;
    211            }
    212        } while (true);
    213    } while (true);
    214    return true;
    215 }
    216 
    217 // diagram of why this simplifcation is possible is here:
    218 // https://skia.org/dev/present/pathops link at bottom of the page
    219 // https://drive.google.com/file/d/0BwoLUwz9PYkHLWpsaXd0UDdaN00/view?usp=sharing
    220 static const SkPathOp gOpInverse[kReverseDifference_SkPathOp + 1][2][2] = {
    221 //                  inside minuend                               outside minuend
    222 //     inside subtrahend     outside subtrahend      inside subtrahend     outside subtrahend
    223 {{ kDifference_SkPathOp,   kIntersect_SkPathOp }, { kUnion_SkPathOp, kReverseDifference_SkPathOp }},
    224 {{ kIntersect_SkPathOp,   kDifference_SkPathOp }, { kReverseDifference_SkPathOp, kUnion_SkPathOp }},
    225 {{ kUnion_SkPathOp, kReverseDifference_SkPathOp }, { kDifference_SkPathOp,   kIntersect_SkPathOp }},
    226 {{ kXOR_SkPathOp,                 kXOR_SkPathOp }, { kXOR_SkPathOp,                kXOR_SkPathOp }},
    227 {{ kReverseDifference_SkPathOp, kUnion_SkPathOp }, { kIntersect_SkPathOp,   kDifference_SkPathOp }},
    228 };
    229 
    230 static const bool gOutInverse[kReverseDifference_SkPathOp + 1][2][2] = {
    231    {{ false, false }, { true, false }},  // diff
    232    {{ false, false }, { false, true }},  // sect
    233    {{ false, true }, { true, true }},    // union
    234    {{ false, true }, { true, false }},   // xor
    235    {{ false, true }, { false, false }},  // rev diff
    236 };
    237 
    238 #if DEBUG_T_SECT_LOOP_COUNT
    239 
    240 #include "include/private/base/SkMutex.h"
    241 
    242 SkOpGlobalState debugWorstState(nullptr, nullptr  SkDEBUGPARAMS(false) SkDEBUGPARAMS(nullptr));
    243 
    244 void ReportPathOpsDebugging() {
    245    debugWorstState.debugLoopReport();
    246 }
    247 
    248 extern void (*gVerboseFinalize)();
    249 
    250 #endif
    251 
    252 std::optional<SkPath> OpDebug(const SkPath& one, const SkPath& two, SkPathOp op
    253        SkDEBUGPARAMS(bool skipAssert) SkDEBUGPARAMS(const char* testName)) {
    254 #if DEBUG_DUMP_VERIFY
    255 #ifndef SK_DEBUG
    256    const char* testName = "release";
    257 #endif
    258    if (SkPathOpsDebug::gDumpOp) {
    259        DumpOp(one, two, op, testName);
    260    }
    261 #endif
    262    op = gOpInverse[op][one.isInverseFillType()][two.isInverseFillType()];
    263    bool inverseFill = gOutInverse[op][one.isInverseFillType()][two.isInverseFillType()];
    264    SkPathFillType fillType = inverseFill ? SkPathFillType::kInverseEvenOdd :
    265            SkPathFillType::kEvenOdd;
    266    SkRect rect1, rect2;
    267    if (kIntersect_SkPathOp == op && one.isRect(&rect1) && two.isRect(&rect2)) {
    268        SkPath result = rect1.intersect(rect2) ? SkPath::Rect(rect1)
    269                                               : SkPath();
    270        return result.makeFillType(fillType);
    271    }
    272    if (one.isEmpty() || two.isEmpty()) {
    273        SkPath work;
    274        switch (op) {
    275            case kIntersect_SkPathOp:
    276                break;
    277            case kUnion_SkPathOp:
    278            case kXOR_SkPathOp:
    279                work = one.isEmpty() ? two : one;
    280                break;
    281            case kDifference_SkPathOp:
    282                if (!one.isEmpty()) {
    283                    work = one;
    284                }
    285                break;
    286            case kReverseDifference_SkPathOp:
    287                if (!two.isEmpty()) {
    288                    work = two;
    289                }
    290                break;
    291            default:
    292                SkASSERT(0);  // unhandled case
    293        }
    294        if (inverseFill != work.isInverseFillType()) {
    295            work.toggleInverseFillType();
    296        }
    297        return Simplify(work);
    298    }
    299    SkSTArenaAlloc<4096> allocator;  // FIXME: add a constant expression here, tune
    300    SkOpContour contour;
    301    SkOpContourHead* contourList = static_cast<SkOpContourHead*>(&contour);
    302    SkOpGlobalState globalState(contourList, &allocator
    303            SkDEBUGPARAMS(skipAssert) SkDEBUGPARAMS(testName));
    304    SkOpCoincidence coincidence(&globalState);
    305    const SkPath* minuend = &one;
    306    const SkPath* subtrahend = &two;
    307    if (op == kReverseDifference_SkPathOp) {
    308        using std::swap;
    309        swap(minuend, subtrahend);
    310        op = kDifference_SkPathOp;
    311    }
    312 #if DEBUG_SORT
    313    SkPathOpsDebug::gSortCount = SkPathOpsDebug::gSortCountDefault;
    314 #endif
    315    // turn path into list of segments
    316    SkOpEdgeBuilder builder(*minuend, contourList, &globalState);
    317    if (builder.unparseable()) {
    318        return {};
    319    }
    320    const int xorMask = builder.xorMask();
    321    builder.addOperand(*subtrahend);
    322    if (!builder.finish()) {
    323        return {};
    324    }
    325 #if DEBUG_DUMP_SEGMENTS
    326    contourList->dumpSegments("seg", op);
    327 #endif
    328 
    329    const int xorOpMask = builder.xorMask();
    330    if (!SortContourList(&contourList, xorMask == kEvenOdd_PathOpsMask,
    331            xorOpMask == kEvenOdd_PathOpsMask)) {
    332        return SkPath().makeFillType(fillType);
    333    }
    334    // find all intersections between segments
    335    SkOpContour* current = contourList;
    336    do {
    337        SkOpContour* next = current;
    338        while (AddIntersectTs(current, next, &coincidence)
    339                && (next = next->next()))
    340            ;
    341    } while ((current = current->next()));
    342 #if DEBUG_VALIDATE
    343    globalState.setPhase(SkOpPhase::kWalking);
    344 #endif
    345    bool success = HandleCoincidence(contourList, &coincidence);
    346 #if DEBUG_COIN
    347    globalState.debugAddToGlobalCoinDicts();
    348 #endif
    349    if (!success) {
    350        return {};
    351    }
    352 #if DEBUG_ALIGNMENT
    353    contourList->dumpSegments("aligned");
    354 #endif
    355    // construct closed contours
    356    SkPathWriter wrapper(fillType);
    357    if (!bridgeOp(contourList, op, xorMask, xorOpMask, &wrapper)) {
    358        return {};
    359    }
    360    wrapper.assemble();  // if some edges could not be resolved, assemble remaining
    361    SkPath result = wrapper.nativePath();
    362 #if DEBUG_T_SECT_LOOP_COUNT
    363    static SkMutex& debugWorstLoop = *(new SkMutex);
    364    {
    365        SkAutoMutexExclusive autoM(debugWorstLoop);
    366        if (!gVerboseFinalize) {
    367            gVerboseFinalize = &ReportPathOpsDebugging;
    368        }
    369        debugWorstState.debugDoYourWorst(&globalState);
    370    }
    371 #endif
    372    return result;
    373 }
    374 
    375 std::optional<SkPath> Op(const SkPath& one, const SkPath& two, SkPathOp op) {
    376 #if DEBUG_DUMP_VERIFY
    377    if (SkPathOpsDebug::gVerifyOp) {
    378        if (auto result = OpDebug(one, two, op  SkDEBUGPARAMS(false) SkDEBUGPARAMS(nullptr))) {
    379            VerifyOp(one, two, op, &result.value());
    380            return *result;
    381        } else {
    382            ReportOpFail(one, two, op);
    383            return {};
    384        }
    385    }
    386 #endif
    387    if (auto result = OpDebug(one, two, op  SkDEBUGPARAMS(true) SkDEBUGPARAMS(nullptr))) {
    388        return *result;
    389    }
    390    return {};
    391 }