src/pathops/SkOpSegment.h

/*
 * Copyright 2012 Google Inc.
 *
 * Use of this source code is governed by a BSD-style license that can be
 * found in the LICENSE file.
 */
#ifndef SkOpSegment_DEFINE
#define SkOpSegment_DEFINE

#include "SkOpAngle.h"
#include "SkOpSpan.h"
#include "SkOpTAllocator.h"
#include "SkPathOpsBounds.h"
#include "SkPathOpsCubic.h"
#include "SkPathOpsCurve.h"

struct SkDCurve;
class SkOpCoincidence;
class SkOpContour;
enum class SkOpRayDir;
struct SkOpRayHit;
class SkPathWriter;

class SkOpSegment {
public:
    enum AllowAlias {
        kAllowAlias,
        kNoAlias
    };

    bool operator<(const SkOpSegment& rh) const {
        return fBounds.fTop < rh.fBounds.fTop;
    }

    SkOpAngle* activeAngle(SkOpSpanBase* start, SkOpSpanBase** startPtr, SkOpSpanBase** endPtr,
                            bool* done);
    SkOpAngle* activeAngleInner(SkOpSpanBase* start, SkOpSpanBase** startPtr,
                                       SkOpSpanBase** endPtr, bool* done);
    SkOpAngle* activeAngleOther(SkOpSpanBase* start, SkOpSpanBase** startPtr,
                                       SkOpSpanBase** endPtr, bool* done);
    bool activeOp(SkOpSpanBase* start, SkOpSpanBase* end, int xorMiMask, int xorSuMask,
                  SkPathOp op);
    bool activeOp(int xorMiMask, int xorSuMask, SkOpSpanBase* start, SkOpSpanBase* end, SkPathOp op,
                  int* sumMiWinding, int* sumSuWinding);

    bool activeWinding(SkOpSpanBase* start, SkOpSpanBase* end);
    bool activeWinding(SkOpSpanBase* start, SkOpSpanBase* end, int* sumWinding);
    void addAlignIntersection(SkOpPtT& endPtT, SkPoint& oldPt,
        SkOpContourHead* contourList, SkChunkAlloc* allocator);

    void addAlignIntersections(SkOpContourHead* contourList, SkChunkAlloc* allocator) {
        this->addAlignIntersection(*fHead.ptT(), fOriginal[0], contourList, allocator);
        this->addAlignIntersection(*fTail.ptT(), fOriginal[1], contourList, allocator);
    }

    SkOpSegment* addConic(SkPoint pts[3], SkScalar weight, SkOpContour* parent) {
        init(pts, weight, parent, SkPath::kConic_Verb);
        SkDCurve curve;
        curve.fConic.set(pts, weight);
        curve.setConicBounds(pts, weight, 0, 1, &fBounds);
        return this;
    }

    SkOpSegment* addCubic(SkPoint pts[4], SkOpContour* parent) {
        init(pts, 1, parent, SkPath::kCubic_Verb);
        SkDCurve curve;
        curve.fCubic.set(pts);
        curve.setCubicBounds(pts, 1, 0, 1, &fBounds);
        return this;
    }

    bool addCurveTo(const SkOpSpanBase* start, const SkOpSpanBase* end, SkPathWriter* path) const;

    SkOpAngle* addEndSpan(SkChunkAlloc* allocator) {
        SkOpAngle* angle = SkOpTAllocator<SkOpAngle>::Allocate(allocator);
        angle->set(&fTail, fTail.prev());
        fTail.setFromAngle(angle);
        return angle;
    }

    SkOpSegment* addLine(SkPoint pts[2], SkOpContour* parent) {
        init(pts, 1, parent, SkPath::kLine_Verb);
        fBounds.set(pts, 2);
        return this;
    }

    SkOpPtT* addMissing(double t, SkOpSegment* opp, SkChunkAlloc* );

    SkOpAngle* addStartSpan(SkChunkAlloc* allocator) {
        SkOpAngle* angle = SkOpTAllocator<SkOpAngle>::Allocate(allocator);
        angle->set(&fHead, fHead.next());
        fHead.setToAngle(angle);
        return angle;
    }

    SkOpSegment* addQuad(SkPoint pts[3], SkOpContour* parent) {
        init(pts, 1, parent, SkPath::kQuad_Verb);
        SkDCurve curve;
        curve.fQuad.set(pts);
        curve.setQuadBounds(pts, 1, 0, 1, &fBounds);
        return this;
    }

    SkOpPtT* addT(double t, AllowAlias , SkChunkAlloc* );

    void align();

    const SkPathOpsBounds& bounds() const {
        return fBounds;
    }

    void bumpCount() {
        ++fCount;
    }

    void calcAngles(SkChunkAlloc*);
    bool collapsed() const;
    static void ComputeOneSum(const SkOpAngle* baseAngle, SkOpAngle* nextAngle,
                              SkOpAngle::IncludeType );
    static void ComputeOneSumReverse(SkOpAngle* baseAngle, SkOpAngle* nextAngle,
                                     SkOpAngle::IncludeType );
    int computeSum(SkOpSpanBase* start, SkOpSpanBase* end, SkOpAngle::IncludeType includeType);

    SkOpContour* contour() const {
        return fContour;
    }

    int count() const {
        return fCount;
    }

    void debugAddAngle(double startT, double endT, SkChunkAlloc*);
    void debugAddAlignIntersection(const char* id, SkPathOpsDebug::GlitchLog* glitches,
                                   const SkOpPtT& endPtT, const SkPoint& oldPt,
                                   const SkOpContourHead* ) const;

    void debugAddAlignIntersections(const char* id, SkPathOpsDebug::GlitchLog* glitches,
                                    SkOpContourHead* contourList) const {
        this->debugAddAlignIntersection(id, glitches, *fHead.ptT(), fOriginal[0], contourList);
        this->debugAddAlignIntersection(id, glitches, *fTail.ptT(), fOriginal[1], contourList);
    }

    bool debugAddMissing(double t, const SkOpSegment* opp) const;
    void debugAlign(const char* id, SkPathOpsDebug::GlitchLog* glitches) const;
    const SkOpAngle* debugAngle(int id) const;
#if DEBUG_ANGLE
    void debugCheckAngleCoin() const;
#endif
    void debugCheckHealth(const char* id, SkPathOpsDebug::GlitchLog* ) const;
    SkOpContour* debugContour(int id);
    void debugFindCollapsed(const char* id, SkPathOpsDebug::GlitchLog* glitches) const;

    int debugID() const {
        return SkDEBUGRELEASE(fID, -1);
    }

    SkOpAngle* debugLastAngle();
    void debugMissingCoincidence(const char* id, SkPathOpsDebug::GlitchLog* glitches,
                                 const SkOpCoincidence* coincidences) const;
    void debugMoveMultiples(const char* id, SkPathOpsDebug::GlitchLog* glitches) const;
    void debugMoveNearby(const char* id, SkPathOpsDebug::GlitchLog* glitches) const;
    const SkOpPtT* debugPtT(int id) const;
    void debugReset();
    const SkOpSegment* debugSegment(int id) const;

#if DEBUG_ACTIVE_SPANS
    void debugShowActiveSpans() const;
#endif
#if DEBUG_MARK_DONE
    void debugShowNewWinding(const char* fun, const SkOpSpan* span, int winding);
    void debugShowNewWinding(const char* fun, const SkOpSpan* span, int winding, int oppWinding);
#endif

    const SkOpSpanBase* debugSpan(int id) const;
    void debugValidate() const;
    void release(const SkOpSpan* );
    double distSq(double t, const SkOpAngle* opp) const;

    bool done() const {
        SkASSERT(fDoneCount <= fCount);
        return fDoneCount == fCount;
    }

    bool done(const SkOpAngle* angle) const {
        return angle->start()->starter(angle->end())->done();
    }

    SkDPoint dPtAtT(double mid) const {
        return (*CurveDPointAtT[fVerb])(fPts, fWeight, mid);
    }

    SkDVector dSlopeAtT(double mid) const {
        return (*CurveDSlopeAtT[fVerb])(fPts, fWeight, mid);
    }

    void dump() const;
    void dumpAll() const;
    void dumpAngles() const;
    void dumpCoin() const;
    void dumpPts(const char* prefix = "seg") const;
    void dumpPtsInner(const char* prefix = "seg") const;

    void findCollapsed();
    SkOpSegment* findNextOp(SkTDArray<SkOpSpanBase*>* chase, SkOpSpanBase** nextStart,
                             SkOpSpanBase** nextEnd, bool* unsortable, SkPathOp op,
                             int xorMiMask, int xorSuMask);
    SkOpSegment* findNextWinding(SkTDArray<SkOpSpanBase*>* chase, SkOpSpanBase** nextStart,
                                  SkOpSpanBase** nextEnd, bool* unsortable);
    SkOpSegment* findNextXor(SkOpSpanBase** nextStart, SkOpSpanBase** nextEnd, bool* unsortable);
    SkOpSpan* findSortableTop(SkOpContour* );
    SkOpGlobalState* globalState() const;

    const SkOpSpan* head() const {
        return &fHead;
    }

    SkOpSpan* head() {
        return &fHead;
    }

    void init(SkPoint pts[], SkScalar weight, SkOpContour* parent, SkPath::Verb verb);

    SkOpSpan* insert(SkOpSpan* prev, SkChunkAlloc* allocator) {
        SkOpSpan* result = SkOpTAllocator<SkOpSpan>::Allocate(allocator);
        SkOpSpanBase* next = prev->next();
        result->setPrev(prev);
        prev->setNext(result);
        SkDEBUGCODE(result->ptT()->fT = 0);
        result->setNext(next);
        if (next) {
            next->setPrev(result);
        }
        return result;
    }

    bool isClose(double t, const SkOpSegment* opp) const;

    bool isHorizontal() const {
        return fBounds.fTop == fBounds.fBottom;
    }

    SkOpSegment* isSimple(SkOpSpanBase** end, int* step) {
        return nextChase(end, step, nullptr, nullptr);
    }

    bool isVertical() const {
        return fBounds.fLeft == fBounds.fRight;
    }

    bool isVertical(SkOpSpanBase* start, SkOpSpanBase* end) const {
        return (*CurveIsVertical[fVerb])(fPts, fWeight, start->t(), end->t());
    }

    bool isXor() const;

    const SkPoint& lastPt() const {
        return fPts[SkPathOpsVerbToPoints(fVerb)];
    }

    void markAllDone();
    SkOpSpanBase* markAndChaseDone(SkOpSpanBase* start, SkOpSpanBase* end);
    bool markAndChaseWinding(SkOpSpanBase* start, SkOpSpanBase* end, int winding,
            SkOpSpanBase** lastPtr);
    bool markAndChaseWinding(SkOpSpanBase* start, SkOpSpanBase* end, int winding,
            int oppWinding, SkOpSpanBase** lastPtr);
    SkOpSpanBase* markAngle(int maxWinding, int sumWinding, const SkOpAngle* angle);
    SkOpSpanBase* markAngle(int maxWinding, int sumWinding, int oppMaxWinding, int oppSumWinding,
                         const SkOpAngle* angle);
    void markDone(SkOpSpan* );
    bool markWinding(SkOpSpan* , int winding);
    bool markWinding(SkOpSpan* , int winding, int oppWinding);
    bool match(const SkOpPtT* span, const SkOpSegment* parent, double t, const SkPoint& pt) const;
    bool missingCoincidence(SkOpCoincidence* coincidences, SkChunkAlloc* allocator);
    bool moveMultiples();
    void moveNearby();

    SkOpSegment* next() const {
        return fNext;
    }

    SkOpSegment* nextChase(SkOpSpanBase** , int* step, SkOpSpan** , SkOpSpanBase** last) const;
    bool operand() const;

    static int OppSign(const SkOpSpanBase* start, const SkOpSpanBase* end) {
        int result = start->t() < end->t() ? -start->upCast()->oppValue()
                : end->upCast()->oppValue();
        return result;
    }

    bool oppXor() const;

    const SkOpSegment* prev() const {
        return fPrev;
    }

    SkPoint ptAtT(double mid) const {
        return (*CurvePointAtT[fVerb])(fPts, fWeight, mid);
    }

    const SkPoint* pts() const {
        return fPts;
    }

    bool ptsDisjoint(const SkOpPtT& span, const SkOpPtT& test) const {
        return ptsDisjoint(span.fT, span.fPt, test.fT, test.fPt);
    }

    bool ptsDisjoint(const SkOpPtT& span, double t, const SkPoint& pt) const {
        return ptsDisjoint(span.fT, span.fPt, t, pt);
    }

    bool ptsDisjoint(double t1, const SkPoint& pt1, double t2, const SkPoint& pt2) const;

    void rayCheck(const SkOpRayHit& base, SkOpRayDir dir, SkOpRayHit** hits,
                  SkChunkAlloc* allocator);

    void resetVisited() {
        fVisited = false;
    }

    void setContour(SkOpContour* contour) {
        fContour = contour;
    }

    void setNext(SkOpSegment* next) {
        fNext = next;
    }

    void setPrev(SkOpSegment* prev) {
        fPrev = prev;
    }

    void setVisited() {
        fVisited = true;
    }

    void setUpWinding(SkOpSpanBase* start, SkOpSpanBase* end, int* maxWinding, int* sumWinding) {
        int deltaSum = SpanSign(start, end);
        *maxWinding = *sumWinding;
        if (*sumWinding == SK_MinS32) {
          return;
        }
        *sumWinding -= deltaSum;
    }

    void setUpWindings(SkOpSpanBase* start, SkOpSpanBase* end, int* sumMiWinding,
                       int* maxWinding, int* sumWinding);
    void setUpWindings(SkOpSpanBase* start, SkOpSpanBase* end, int* sumMiWinding, int* sumSuWinding,
                       int* maxWinding, int* sumWinding, int* oppMaxWinding, int* oppSumWinding);
    void sortAngles();

    static int SpanSign(const SkOpSpanBase* start, const SkOpSpanBase* end) {
        int result = start->t() < end->t() ? -start->upCast()->windValue()
                : end->upCast()->windValue();
        return result;
    }

    SkOpAngle* spanToAngle(SkOpSpanBase* start, SkOpSpanBase* end) {
        SkASSERT(start != end);
        return start->t() < end->t() ? start->upCast()->toAngle() : start->fromAngle();
    }

    bool subDivide(const SkOpSpanBase* start, const SkOpSpanBase* end, SkDCurve* result) const;
    bool subDivide(const SkOpSpanBase* start, const SkOpSpanBase* end, SkOpCurve* result) const;

    const SkOpSpanBase* tail() const {
        return &fTail;
    }

    SkOpSpanBase* tail() {
        return &fTail;
    }

    bool testForCoincidence(const SkOpPtT* priorPtT, const SkOpPtT* ptT, const SkOpSpanBase* prior,
            const SkOpSpanBase* spanBase, const SkOpSegment* opp, SkScalar flatnessLimit) const;

    void undoneSpan(SkOpSpanBase** start, SkOpSpanBase** end);
    int updateOppWinding(const SkOpSpanBase* start, const SkOpSpanBase* end) const;
    int updateOppWinding(const SkOpAngle* angle) const;
    int updateOppWindingReverse(const SkOpAngle* angle) const;
    int updateWinding(SkOpSpanBase* start, SkOpSpanBase* end);
    int updateWinding(SkOpAngle* angle);
    int updateWindingReverse(const SkOpAngle* angle);

    static bool UseInnerWinding(int outerWinding, int innerWinding);

    SkPath::Verb verb() const {
        return fVerb;
    }

    // look for two different spans that point to the same opposite segment
    bool visited() {
        if (!fVisited) {
            fVisited = true;
            return false;
        }
        return true;
    }

    SkScalar weight() const {
        return fWeight;
    }

    SkOpSpan* windingSpanAtT(double tHit);
    int windSum(const SkOpAngle* angle) const;

    SkPoint* writablePt(bool end) {
        return &fPts[end ? SkPathOpsVerbToPoints(fVerb) : 0];
    }

private:
    SkOpSpan fHead;  // the head span always has its t set to zero
    SkOpSpanBase fTail;  // the tail span always has its t set to one
    SkOpContour* fContour;
    SkOpSegment* fNext;  // forward-only linked list used by contour to walk the segments
    const SkOpSegment* fPrev;
    SkPoint fOriginal[2];  // if aligned, the original unaligned points are here
    SkPoint* fPts;  // pointer into array of points owned by edge builder that may be tweaked
    SkPathOpsBounds fBounds;  // tight bounds
    SkScalar fWeight;
    int fCount;  // number of spans (one for a non-intersecting segment)
    int fDoneCount;  // number of processed spans (zero initially)
    SkPath::Verb fVerb;
    bool fVisited;  // used by missing coincidence check
    SkDEBUGCODE(int fID);
};

#endif