/* * Copyright 2014 Google Inc. * * Use of this source code is governed by a BSD-style license that can be * found in the LICENSE file. */ #ifndef SkPathOpsTSect_DEFINED #define SkPathOpsTSect_DEFINED #include "include/private/SkMacros.h" #include "src/core/SkArenaAlloc.h" #include "src/core/SkTSort.h" #include "src/pathops/SkIntersections.h" #include "src/pathops/SkPathOpsBounds.h" #include "src/pathops/SkPathOpsRect.h" #include "src/pathops/SkPathOpsTCurve.h" #include #ifdef SK_DEBUG typedef uint8_t SkOpDebugBool; #else typedef bool SkOpDebugBool; #endif static inline bool SkDoubleIsNaN(double x) { return x != x; } class SkTCoincident { public: SkTCoincident() { this->init(); } void debugInit() { #ifdef SK_DEBUG this->fPerpPt.fX = this->fPerpPt.fY = SK_ScalarNaN; this->fPerpT = SK_ScalarNaN; this->fMatch = 0xFF; #endif } char dumpIsCoincidentStr() const; void dump() const; bool isMatch() const { SkASSERT(!!fMatch == fMatch); return SkToBool(fMatch); } void init() { fPerpT = -1; fMatch = false; fPerpPt.fX = fPerpPt.fY = SK_ScalarNaN; } void markCoincident() { if (!fMatch) { fPerpT = -1; } fMatch = true; } const SkDPoint& perpPt() const { return fPerpPt; } double perpT() const { return fPerpT; } void setPerp(const SkTCurve& c1, double t, const SkDPoint& cPt, const SkTCurve& ); private: SkDPoint fPerpPt; double fPerpT; // perpendicular intersection on opposite curve SkOpDebugBool fMatch; }; class SkTSect; class SkTSpan; struct SkTSpanBounded { SkTSpan* fBounded; SkTSpanBounded* fNext; }; class SkTSpan { public: SkTSpan(const SkTCurve& curve, SkArenaAlloc& heap) { fPart = curve.make(heap); } void addBounded(SkTSpan* , SkArenaAlloc* ); double closestBoundedT(const SkDPoint& pt) const; bool contains(double t) const; void debugInit(const SkTCurve& curve, SkArenaAlloc& heap) { #ifdef SK_DEBUG SkTCurve* dummy = curve.make(heap); dummy->debugInit(); init(*dummy); initBounds(*dummy); fCoinStart.init(); fCoinEnd.init(); #endif } const SkTSect* debugOpp() const; #ifdef SK_DEBUG void debugSetGlobalState(SkOpGlobalState* state) { fDebugGlobalState = state; } const SkTSpan* debugSpan(int ) const; const SkTSpan* debugT(double t) const; bool debugIsBefore(const SkTSpan* span) const; #endif void dump() const; void dumpAll() const; void dumpBounded(int id) const; void dumpBounds() const; void dumpCoin() const; double endT() const { return fEndT; } SkTSpan* findOppSpan(const SkTSpan* opp) const; SkTSpan* findOppT(double t) const { SkTSpan* result = oppT(t); SkOPASSERT(result); return result; } SkDEBUGCODE(SkOpGlobalState* globalState() const { return fDebugGlobalState; }) bool hasOppT(double t) const { return SkToBool(oppT(t)); } int hullsIntersect(SkTSpan* span, bool* start, bool* oppStart); void init(const SkTCurve& ); bool initBounds(const SkTCurve& ); bool isBounded() const { return fBounded != nullptr; } bool linearsIntersect(SkTSpan* span); double linearT(const SkDPoint& ) const; void markCoincident() { fCoinStart.markCoincident(); fCoinEnd.markCoincident(); } const SkTSpan* next() const { return fNext; } bool onlyEndPointsInCommon(const SkTSpan* opp, bool* start, bool* oppStart, bool* ptsInCommon); const SkTCurve& part() const { return *fPart; } int pointCount() const { return fPart->pointCount(); } const SkDPoint& pointFirst() const { return (*fPart)[0]; } const SkDPoint& pointLast() const { return (*fPart)[fPart->pointLast()]; } bool removeAllBounded(); bool removeBounded(const SkTSpan* opp); void reset() { fBounded = nullptr; } void resetBounds(const SkTCurve& curve) { fIsLinear = fIsLine = false; initBounds(curve); } bool split(SkTSpan* work, SkArenaAlloc* heap) { return splitAt(work, (work->fStartT + work->fEndT) * 0.5, heap); } bool splitAt(SkTSpan* work, double t, SkArenaAlloc* heap); double startT() const { return fStartT; } private: // implementation is for testing only int debugID() const { return PATH_OPS_DEBUG_T_SECT_RELEASE(fID, -1); } void dumpID() const; int hullCheck(const SkTSpan* opp, bool* start, bool* oppStart); int linearIntersects(const SkTCurve& ) const; SkTSpan* oppT(double t) const; void validate() const; void validateBounded() const; void validatePerpT(double oppT) const; void validatePerpPt(double t, const SkDPoint& ) const; SkTCurve* fPart; SkTCoincident fCoinStart; SkTCoincident fCoinEnd; SkTSpanBounded* fBounded; SkTSpan* fPrev; SkTSpan* fNext; SkDRect fBounds; double fStartT; double fEndT; double fBoundsMax; SkOpDebugBool fCollapsed; SkOpDebugBool fHasPerp; SkOpDebugBool fIsLinear; SkOpDebugBool fIsLine; SkOpDebugBool fDeleted; SkDEBUGCODE(SkOpGlobalState* fDebugGlobalState); SkDEBUGCODE(SkTSect* fDebugSect); PATH_OPS_DEBUG_T_SECT_CODE(int fID); friend class SkTSect; }; class SkTSect { public: SkTSect(const SkTCurve& c SkDEBUGPARAMS(SkOpGlobalState* ) PATH_OPS_DEBUG_T_SECT_PARAMS(int id)); static void BinarySearch(SkTSect* sect1, SkTSect* sect2, SkIntersections* intersections); SkDEBUGCODE(SkOpGlobalState* globalState() { return fDebugGlobalState; }) bool hasBounded(const SkTSpan* ) const; const SkTSect* debugOpp() const { return SkDEBUGRELEASE(fOppSect, nullptr); } #ifdef SK_DEBUG const SkTSpan* debugSpan(int id) const; const SkTSpan* debugT(double t) const; #endif void dump() const; void dumpBoth(SkTSect* ) const; void dumpBounded(int id) const; void dumpBounds() const; void dumpCoin() const; void dumpCoinCurves() const; void dumpCurves() const; private: enum { kZeroS1Set = 1, kOneS1Set = 2, kZeroS2Set = 4, kOneS2Set = 8 }; SkTSpan* addFollowing(SkTSpan* prior); void addForPerp(SkTSpan* span, double t); SkTSpan* addOne(); SkTSpan* addSplitAt(SkTSpan* span, double t) { SkTSpan* result = this->addOne(); SkDEBUGCODE(result->debugSetGlobalState(this->globalState())); result->splitAt(span, t, &fHeap); result->initBounds(fCurve); span->initBounds(fCurve); return result; } bool binarySearchCoin(SkTSect* , double tStart, double tStep, double* t, double* oppT, SkTSpan** oppFirst); SkTSpan* boundsMax(); bool coincidentCheck(SkTSect* sect2); void coincidentForce(SkTSect* sect2, double start1s, double start1e); bool coincidentHasT(double t); int collapsed() const; void computePerpendiculars(SkTSect* sect2, SkTSpan* first, SkTSpan* last); int countConsecutiveSpans(SkTSpan* first, SkTSpan** last) const; int debugID() const { return PATH_OPS_DEBUG_T_SECT_RELEASE(fID, -1); } bool deleteEmptySpans(); void dumpCommon(const SkTSpan* ) const; void dumpCommonCurves(const SkTSpan* ) const; static int EndsEqual(const SkTSect* sect1, const SkTSect* sect2, SkIntersections* ); bool extractCoincident(SkTSect* sect2, SkTSpan* first, SkTSpan* last, SkTSpan** result); SkTSpan* findCoincidentRun(SkTSpan* first, SkTSpan** lastPtr); int intersects(SkTSpan* span, SkTSect* opp, SkTSpan* oppSpan, int* oppResult); bool isParallel(const SkDLine& thisLine, const SkTSect* opp) const; int linesIntersect(SkTSpan* span, SkTSect* opp, SkTSpan* oppSpan, SkIntersections* ); bool markSpanGone(SkTSpan* span); bool matchedDirection(double t, const SkTSect* sect2, double t2) const; void matchedDirCheck(double t, const SkTSect* sect2, double t2, bool* calcMatched, bool* oppMatched) const; void mergeCoincidence(SkTSect* sect2); const SkDPoint& pointLast() const { return fCurve[fCurve.pointLast()]; } SkTSpan* prev(SkTSpan* ) const; bool removeByPerpendicular(SkTSect* opp); void recoverCollapsed(); bool removeCoincident(SkTSpan* span, bool isBetween); void removeAllBut(const SkTSpan* keep, SkTSpan* span, SkTSect* opp); bool removeSpan(SkTSpan* span); void removeSpanRange(SkTSpan* first, SkTSpan* last); bool removeSpans(SkTSpan* span, SkTSect* opp); void removedEndCheck(SkTSpan* span); void resetRemovedEnds() { fRemovedStartT = fRemovedEndT = false; } SkTSpan* spanAtT(double t, SkTSpan** priorSpan); SkTSpan* tail(); bool trim(SkTSpan* span, SkTSect* opp); bool unlinkSpan(SkTSpan* span); bool updateBounded(SkTSpan* first, SkTSpan* last, SkTSpan* oppFirst); void validate() const; void validateBounded() const; const SkTCurve& fCurve; SkSTArenaAlloc<1024> fHeap; SkTSpan* fHead; SkTSpan* fCoincident; SkTSpan* fDeleted; int fActiveCount; bool fRemovedStartT; bool fRemovedEndT; bool fHung; SkDEBUGCODE(SkOpGlobalState* fDebugGlobalState); SkDEBUGCODE(SkTSect* fOppSect); PATH_OPS_DEBUG_T_SECT_CODE(int fID); PATH_OPS_DEBUG_T_SECT_CODE(int fDebugCount); #if DEBUG_T_SECT int fDebugAllocatedCount; #endif friend class SkTSpan; }; #endif