SkPathOpsCommon.h File Reference

#include "include/pathops/SkPathOps.h"
#include "src/pathops/SkPathOpsTypes.h"

Go to the source code of this file.

Functions
const SkOpAngle *	AngleWinding (SkOpSpanBase *start, SkOpSpanBase *end, int *windingPtr, bool *sortable)
SkOpSegment *	FindChase (SkTDArray< SkOpSpanBase * > *chase, SkOpSpanBase **startPtr, SkOpSpanBase **endPtr)
SkOpSpan *	FindSortableTop (SkOpContourHead *)
SkOpSpan *	FindUndone (SkOpContourHead *)
bool	FixWinding (SkPath *path)
bool	SortContourList (SkOpContourHead **, bool evenOdd, bool oppEvenOdd)
bool	HandleCoincidence (SkOpContourHead *, SkOpCoincidence *)
bool	OpDebug (const SkPath &one, const SkPath &two, SkPathOp op, SkPath *result SkDEBUGPARAMS(bool skipAssert) SkDEBUGPARAMS(const char *testName))

Function Documentation

AngleWinding()

const SkOpAngle * AngleWinding	(	SkOpSpanBase *	start,
		SkOpSpanBase *	end,
		int *	windingPtr,
		bool *	sortable
	)

Definition at line 21 of file SkPathOpsCommon.cpp.

                           {
    // 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;
}

FindChase()

SkOpSegment * FindChase	(	SkTDArray< SkOpSpanBase * > *	chase,
		SkOpSpanBase **	startPtr,
		SkOpSpanBase **	endPtr
	)

Definition at line 87 of file SkPathOpsCommon.cpp.

                               {
    while (!chase->empty()) {
        SkOpSpanBase* span = chase->back();
        chase->pop_back();
        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) {
                    // TODO: add error handling
                    SkAssertResult(segment->markAngle(maxWinding, sumWinding, angle, nullptr));
                }
            }
        }
        if (first) {
       #if TRY_ROTATE
            *chase->insert(0) = span;
       #else
            *chase->append() = span;
       #endif
            return first;
        }
    }
    return nullptr;
}

FindSortableTop()

SkOpSpan * FindSortableTop

(

SkOpContourHead *

contourHead

)

Definition at line 429 of file SkPathOpsWinding.cpp.

                                                        {
    for (int index = 0; index < SkOpGlobalState::kMaxWindingTries; ++index) {
        SkOpContour* contour = contourHead;
        do {
            if (contour->done()) {
                continue;
            }
            SkOpSpan* result = contour->findSortableTop(contourHead);
            if (result) {
                return result;
            }
        } while ((contour = contour->next()));
    }
    return nullptr;
}

FindUndone()

SkOpSpan * FindUndone

(

SkOpContourHead *

contourHead

)

Definition at line 73 of file SkPathOpsCommon.cpp.

                                                   {
    SkOpContour* contour = contourHead;
    do {
        if (contour->done()) {
            continue;
        }
        SkOpSpan* result = contour->undoneSpan();
        if (result) {
            return result;
        }
    } while ((contour = contour->next()));
    return nullptr;
}

FixWinding()

bool FixWinding

(

SkPath *

path

)

HandleCoincidence()

bool HandleCoincidence	(	SkOpContourHead *	contourList,
		SkOpCoincidence *	coincidence
	)

Definition at line 238 of file SkPathOpsCommon.cpp.

                                                                                   {
    SkOpGlobalState* globalState = contourList->globalState();
    // match up points within the coincident runs
    if (!coincidence->addExpanded(DEBUG_PHASE_ONLY_PARAMS(kIntersecting))) {
        return false;
    }
    // combine t values when multiple intersections occur on some segments but not others
    if (!move_multiples(contourList  DEBUG_PHASE_PARAMS(kWalking))) {
        return false;
    }
    // move t values and points together to eliminate small/tiny gaps
    if (!move_nearby(contourList  DEBUG_COIN_PARAMS())) {
        return false;
    }
    // add coincidence formed by pairing on curve points and endpoints
    coincidence->correctEnds(DEBUG_PHASE_ONLY_PARAMS(kIntersecting));
    if (!coincidence->addEndMovedSpans(DEBUG_COIN_ONLY_PARAMS())) {
        return false;
    }
    const int SAFETY_COUNT = 3;
    int safetyHatch = SAFETY_COUNT;
    // look for coincidence present in A-B and A-C but missing in B-C
    do {
        bool added;
        if (!coincidence->addMissing(&added  DEBUG_ITER_PARAMS(SAFETY_COUNT - safetyHatch))) {
            return false;
        }
        if (!added) {
            break;
        }
        if (!--safetyHatch) {
            SkASSERT(globalState->debugSkipAssert());
            return false;
        }
        move_nearby(contourList  DEBUG_ITER_PARAMS(SAFETY_COUNT - safetyHatch - 1));
    } while (true);
    // check to see if, loosely, coincident ranges may be expanded
    if (coincidence->expand(DEBUG_COIN_ONLY_PARAMS())) {
        bool added;
        if (!coincidence->addMissing(&added  DEBUG_COIN_PARAMS())) {
            return false;
        }
        if (!coincidence->addExpanded(DEBUG_COIN_ONLY_PARAMS())) {
            return false;
        }
        if (!move_multiples(contourList  DEBUG_COIN_PARAMS())) {
            return false;
        }
        move_nearby(contourList  DEBUG_COIN_PARAMS());
    }
    // the expanded ranges may not align -- add the missing spans
    if (!coincidence->addExpanded(DEBUG_PHASE_ONLY_PARAMS(kWalking))) {
        return false;
    }
    // mark spans of coincident segments as coincident
    coincidence->mark(DEBUG_COIN_ONLY_PARAMS());
    // look for coincidence lines and curves undetected by intersection
    if (missing_coincidence(contourList  DEBUG_COIN_PARAMS())) {
        (void) coincidence->expand(DEBUG_PHASE_ONLY_PARAMS(kIntersecting));
        if (!coincidence->addExpanded(DEBUG_COIN_ONLY_PARAMS())) {
            return false;
        }
        if (!coincidence->mark(DEBUG_PHASE_ONLY_PARAMS(kWalking))) {
            return false;
        }
    } else {
        (void) coincidence->expand(DEBUG_COIN_ONLY_PARAMS());
    }
    (void) coincidence->expand(DEBUG_COIN_ONLY_PARAMS());
 
    SkOpCoincidence overlaps(globalState);
    safetyHatch = SAFETY_COUNT;
    do {
        SkOpCoincidence* pairs = overlaps.isEmpty() ? coincidence : &overlaps;
        // adjust the winding value to account for coincident edges
        if (!pairs->apply(DEBUG_ITER_ONLY_PARAMS(SAFETY_COUNT - safetyHatch))) {
            return false;
        }
        // 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  DEBUG_ITER_PARAMS(SAFETY_COUNT - safetyHatch))) {
            return false;
        }
        if (!--safetyHatch) {
            SkASSERT(globalState->debugSkipAssert());
            return false;
        }
    } while (!overlaps.isEmpty());
    calc_angles(contourList  DEBUG_COIN_PARAMS());
    if (!sort_angles(contourList)) {
        return false;
    }
#if DEBUG_COINCIDENCE_VERBOSE
    coincidence->debugShowCoincidence();
#endif
#if DEBUG_COINCIDENCE
    coincidence->debugValidate();
#endif
    SkPathOpsDebug::ShowActiveSpans(contourList);
    return true;
}

OpDebug()

bool OpDebug	(	const SkPath &	one,
		const SkPath &	two,
		SkPathOp	op,
		SkPath *result	SkDEBUGPARAMSbool skipAssert) SkDEBUGPARAMS(const char *testName
	)

Definition at line 252 of file SkPathOpsOp.cpp.

                                                                            {
#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)) {
        result->reset();
        result->setFillType(fillType);
        if (rect1.intersect(rect2)) {
            result->addRect(rect1);
        }
        return true;
    }
    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, result);
    }
    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 false;
    }
    const int xorMask = builder.xorMask();
    builder.addOperand(*subtrahend);
    if (!builder.finish()) {
        return false;
    }
#if DEBUG_DUMP_SEGMENTS
    contourList->dumpSegments("seg", op);
#endif
 
    const int xorOpMask = builder.xorMask();
    if (!SortContourList(&contourList, xorMask == kEvenOdd_PathOpsMask,
            xorOpMask == kEvenOdd_PathOpsMask)) {
        result->reset();
        result->setFillType(fillType);
        return true;
    }
    // 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 false;
    }
#if DEBUG_ALIGNMENT
    contourList->dumpSegments("aligned");
#endif
    // construct closed contours
    SkPath original = *result;
    result->reset();
    result->setFillType(fillType);
    SkPathWriter wrapper(*result);
    if (!bridgeOp(contourList, op, xorMask, xorOpMask, &wrapper)) {
        *result = original;
        return false;
    }
    wrapper.assemble();  // if some edges could not be resolved, assemble remaining
#if DEBUG_T_SECT_LOOP_COUNT
    static SkMutex& debugWorstLoop = *(new SkMutex);
    {
        SkAutoMutexExclusive autoM(debugWorstLoop);
        if (!gVerboseFinalize) {
            gVerboseFinalize = &ReportPathOpsDebugging;
        }
        debugWorstState.debugDoYourWorst(&globalState);
    }
#endif
    return true;
}

SortContourList()

bool SortContourList	(	SkOpContourHead **	contourList,
		bool	evenOdd,
		bool	oppEvenOdd
	)

Definition at line 159 of file SkPathOpsCommon.cpp.

                                                                                   {
    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.size();
    if (!count) {
        return false;
    }
    if (count > 1) {
        SkTQSort<SkOpContour>(list.begin(), list.end());
    }
    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;
}