SkOpSegment.cpp | Explore in Territory

/*
 * 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 "src/pathops/SkOpSegment.h"

#include "include/private/base/SkTDArray.h"
#include "include/private/base/SkTemplates.h"
#include "src/core/SkPointPriv.h"
#include "src/pathops/SkIntersections.h"
#include "src/pathops/SkOpCoincidence.h"
#include "src/pathops/SkOpContour.h"
#include "src/pathops/SkPathOpsLine.h"
#include "src/pathops/SkPathWriter.h"

#include <algorithm>
#include <cfloat>

/*
After computing raw intersections, post process all segments to:
- find small collections of points that can be collapsed to a single point
- find missing intersections to resolve differences caused by different algorithms

Consider segments containing tiny or small intervals. Consider coincident segments
because coincidence finds intersections through distance measurement that non-coincident
intersection tests cannot.
 */

#define F …
#define T …

static const bool gUnaryActiveEdge[2][2] = …;

static const bool gActiveEdge[kXOR_SkPathOp + 1][2][2][2][2] = …;

#undef F
#undef T

SkOpAngle* SkOpSegment::activeAngle(SkOpSpanBase* start, SkOpSpanBase** startPtr,
        SkOpSpanBase** endPtr, bool* done) { … }

SkOpAngle* SkOpSegment::activeAngleInner(SkOpSpanBase* start, SkOpSpanBase** startPtr,
        SkOpSpanBase** endPtr, bool* done) { … }

SkOpAngle* SkOpSegment::activeAngleOther(SkOpSpanBase* start, SkOpSpanBase** startPtr,
        SkOpSpanBase** endPtr, bool* done) { … }

bool SkOpSegment::activeOp(SkOpSpanBase* start, SkOpSpanBase* end, int xorMiMask, int xorSuMask,
        SkPathOp op) { … }

bool SkOpSegment::activeOp(int xorMiMask, int xorSuMask, SkOpSpanBase* start, SkOpSpanBase* end,
        SkPathOp op, int* sumMiWinding, int* sumSuWinding) { … }

bool SkOpSegment::activeWinding(SkOpSpanBase* start, SkOpSpanBase* end) { … }

bool SkOpSegment::activeWinding(SkOpSpanBase* start, SkOpSpanBase* end, int* sumWinding) { … }

bool SkOpSegment::addCurveTo(const SkOpSpanBase* start, const SkOpSpanBase* end,
        SkPathWriter* path) const { … }

const SkOpPtT* SkOpSegment::existing(double t, const SkOpSegment* opp) const { … }

// break the span so that the coincident part does not change the angle of the remainder
bool SkOpSegment::addExpanded(double newT, const SkOpSpanBase* test, bool* startOver) { … }

// Please keep this in sync with debugAddT()
SkOpPtT* SkOpSegment::addT(double t, const SkPoint& pt) { … }

SkOpPtT* SkOpSegment::addT(double t) { … }

void SkOpSegment::calcAngles() { … }

// Please keep this in sync with debugClearAll()
void SkOpSegment::clearAll() { … }

// Please keep this in sync with debugClearOne()
void SkOpSegment::clearOne(SkOpSpan* span) { … }

SkOpSpanBase::Collapsed SkOpSegment::collapsed(double s, double e) const { … }

bool SkOpSegment::ComputeOneSum(const SkOpAngle* baseAngle, SkOpAngle* nextAngle,
        SkOpAngle::IncludeType includeType) { … }

bool SkOpSegment::ComputeOneSumReverse(SkOpAngle* baseAngle, SkOpAngle* nextAngle,
        SkOpAngle::IncludeType includeType) { … }

// at this point, the span is already ordered, or unorderable
int SkOpSegment::computeSum(SkOpSpanBase* start, SkOpSpanBase* end,
        SkOpAngle::IncludeType includeType) { … }

bool SkOpSegment::contains(double newT) const { … }

void SkOpSegment::release(const SkOpSpan* span) { … }

#if DEBUG_ANGLE
// called only by debugCheckNearCoincidence
double SkOpSegment::distSq(double t, const SkOpAngle* oppAngle) const {
    SkDPoint testPt = this->dPtAtT(t);
    SkDLine testPerp = {{ testPt, testPt }};
    SkDVector slope = this->dSlopeAtT(t);
    testPerp[1].fX += slope.fY;
    testPerp[1].fY -= slope.fX;
    SkIntersections i;
    const SkOpSegment* oppSegment = oppAngle->segment();
    (*CurveIntersectRay[oppSegment->verb()])(oppSegment->pts(), oppSegment->weight(), testPerp, &i);
    double closestDistSq = SK_ScalarInfinity;
    for (int index = 0; index < i.used(); ++index) {
        if (!between(oppAngle->start()->t(), i[0][index], oppAngle->end()->t())) {
            continue;
        }
        double testDistSq = testPt.distanceSquared(i.pt(index));
        if (closestDistSq > testDistSq) {
            closestDistSq = testDistSq;
        }
    }
    return closestDistSq;
}
#endif

/*
 The M and S variable name parts stand for the operators.
   Mi stands for Minuend (see wiki subtraction, analogous to difference)
   Su stands for Subtrahend
 The Opp variable name part designates that the value is for the Opposite operator.
 Opposite values result from combining coincident spans.
 */
SkOpSegment* SkOpSegment::findNextOp(SkTDArray<SkOpSpanBase*>* chase, SkOpSpanBase** nextStart,
        SkOpSpanBase** nextEnd, bool* unsortable, bool* simple,
        SkPathOp op, int xorMiMask, int xorSuMask) { … }

SkOpSegment* SkOpSegment::findNextWinding(SkTDArray<SkOpSpanBase*>* chase,
        SkOpSpanBase** nextStart, SkOpSpanBase** nextEnd, bool* unsortable) { … }

SkOpSegment* SkOpSegment::findNextXor(SkOpSpanBase** nextStart, SkOpSpanBase** nextEnd,
        bool* unsortable) { … }

SkOpGlobalState* SkOpSegment::globalState() const { … }

void SkOpSegment::init(SkPoint pts[], SkScalar weight, SkOpContour* contour, SkPath::Verb verb) { … }

bool SkOpSegment::isClose(double t, const SkOpSegment* opp) const { … }

bool SkOpSegment::isXor() const { … }

void SkOpSegment::markAllDone() { … }

 bool SkOpSegment::markAndChaseDone(SkOpSpanBase* start, SkOpSpanBase* end, SkOpSpanBase** found) { … }

bool SkOpSegment::markAndChaseWinding(SkOpSpanBase* start, SkOpSpanBase* end, int winding,
        SkOpSpanBase** lastPtr) { … }

bool SkOpSegment::markAndChaseWinding(SkOpSpanBase* start, SkOpSpanBase* end,
        int winding, int oppWinding, SkOpSpanBase** lastPtr) { … }

bool SkOpSegment::markAngle(int maxWinding, int sumWinding, const SkOpAngle* angle,
                            SkOpSpanBase** result) { … }

bool SkOpSegment::markAngle(int maxWinding, int sumWinding, int oppMaxWinding,
                            int oppSumWinding, const SkOpAngle* angle, SkOpSpanBase** result) { … }

void SkOpSegment::markDone(SkOpSpan* span) { … }

bool SkOpSegment::markWinding(SkOpSpan* span, int winding) { … }

bool SkOpSegment::markWinding(SkOpSpan* span, int winding, int oppWinding) { … }

bool SkOpSegment::match(const SkOpPtT* base, const SkOpSegment* testParent, double testT,
        const SkPoint& testPt) const { … }

static SkOpSegment* set_last(SkOpSpanBase** last, SkOpSpanBase* endSpan) { … }

SkOpSegment* SkOpSegment::nextChase(SkOpSpanBase** startPtr, int* stepPtr, SkOpSpan** minPtr,
        SkOpSpanBase** last) const { … }

// Please keep this in sync with DebugClearVisited()
void SkOpSegment::ClearVisited(SkOpSpanBase* span) { … }

// Please keep this in sync with debugMissingCoincidence()
// look for pairs of undetected coincident curves
// assumes that segments going in have visited flag clear
// Even though pairs of curves correct detect coincident runs, a run may be missed
// if the coincidence is a product of multiple intersections. For instance, given
// curves A, B, and C:
// A-B intersect at a point 1; A-C and B-C intersect at point 2, so near
// the end of C that the intersection is replaced with the end of C.
// Even though A-B correctly do not detect an intersection at point 2,
// the resulting run from point 1 to point 2 is coincident on A and B.
bool SkOpSegment::missingCoincidence() { … }

// please keep this in sync with debugMoveMultiples()
// if a span has more than one intersection, merge the other segments' span as needed
bool SkOpSegment::moveMultiples() { … }

// adjacent spans may have points close by
bool SkOpSegment::spansNearby(const SkOpSpanBase* refSpan, const SkOpSpanBase* checkSpan,
        bool* found) const { … }

// Please keep this function in sync with debugMoveNearby()
// Move nearby t values and pts so they all hang off the same span. Alignment happens later.
bool SkOpSegment::moveNearby() { … }

bool SkOpSegment::operand() const { … }

bool SkOpSegment::oppXor() const { … }

bool SkOpSegment::ptsDisjoint(double t1, const SkPoint& pt1, double t2, const SkPoint& pt2) const { … }

void SkOpSegment::setUpWindings(SkOpSpanBase* start, SkOpSpanBase* end, int* sumMiWinding,
        int* maxWinding, int* sumWinding) { … }

void SkOpSegment::setUpWindings(SkOpSpanBase* start, SkOpSpanBase* end, int* sumMiWinding,
        int* sumSuWinding, int* maxWinding, int* sumWinding, int* oppMaxWinding,
        int* oppSumWinding) { … }

bool SkOpSegment::sortAngles() { … }

bool SkOpSegment::subDivide(const SkOpSpanBase* start, const SkOpSpanBase* end,
        SkDCurve* edge) const { … }

bool SkOpSegment::testForCoincidence(const SkOpPtT* priorPtT, const SkOpPtT* ptT,
        const SkOpSpanBase* prior, const SkOpSpanBase* spanBase, const SkOpSegment* opp) const { … }

SkOpSpan* SkOpSegment::undoneSpan() { … }

int SkOpSegment::updateOppWinding(const SkOpSpanBase* start, const SkOpSpanBase* end) const { … }

int SkOpSegment::updateOppWinding(const SkOpAngle* angle) const { … }

int SkOpSegment::updateOppWindingReverse(const SkOpAngle* angle) const { … }

int SkOpSegment::updateWinding(SkOpSpanBase* start, SkOpSpanBase* end) { … }

int SkOpSegment::updateWinding(SkOpAngle* angle) { … }

int SkOpSegment::updateWindingReverse(const SkOpAngle* angle) { … }

// OPTIMIZATION: does the following also work, and is it any faster?
// return outerWinding * innerWinding > 0
//      || ((outerWinding + innerWinding < 0) ^ ((outerWinding - innerWinding) < 0)))
bool SkOpSegment::UseInnerWinding(int outerWinding, int innerWinding) { … }

int SkOpSegment::windSum(const SkOpAngle* angle) const { … }
chromium/third_party/skia/src/pathops/SkOpSegment.cpp
