| /* |
| * 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/core/SkScalar.h" |
| #include "include/core/SkTypes.h" |
| #include "include/private/base/SkDebug.h" |
| #include "include/private/base/SkTo.h" |
| #include "src/base/SkArenaAlloc.h" |
| #include "src/pathops/SkPathOpsPoint.h" |
| #include "src/pathops/SkPathOpsRect.h" |
| #include "src/pathops/SkPathOpsTCurve.h" |
| #include "src/pathops/SkPathOpsTypes.h" |
| |
| #include <cstdint> |
| |
| class SkIntersections; |
| class SkTSect; |
| class SkTSpan; |
| struct SkDLine; |
| |
| #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; |
| }; |
| |
| 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* fake = curve.make(heap); |
| fake->debugInit(); |
| init(*fake); |
| initBounds(*fake); |
| 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 |