michael@0: /*
michael@0:  * Copyright 2012 Google Inc.
michael@0:  *
michael@0:  * Use of this source code is governed by a BSD-style license that can be
michael@0:  * found in the LICENSE file.
michael@0:  */
michael@0: #ifndef SkOpSegment_DEFINE
michael@0: #define SkOpSegment_DEFINE
michael@0: 
michael@0: #include "SkOpAngle.h"
michael@0: #include "SkOpSpan.h"
michael@0: #include "SkPathOpsBounds.h"
michael@0: #include "SkPathOpsCurve.h"
michael@0: #include "SkTArray.h"
michael@0: #include "SkTDArray.h"
michael@0: 
michael@0: class SkPathWriter;
michael@0: 
michael@0: class SkOpSegment {
michael@0: public:
michael@0:     SkOpSegment() {
michael@0: #ifdef SK_DEBUG
michael@0:         fID = ++SkPathOpsDebug::gSegmentID;
michael@0: #endif
michael@0:     }
michael@0: 
michael@0:     bool operator<(const SkOpSegment& rh) const {
michael@0:         return fBounds.fTop < rh.fBounds.fTop;
michael@0:     }
michael@0: 
michael@0:     const SkPathOpsBounds& bounds() const {
michael@0:         return fBounds;
michael@0:     }
michael@0: 
michael@0:     // OPTIMIZE
michael@0:     // when the edges are initially walked, they don't automatically get the prior and next
michael@0:     // edges assigned to positions t=0 and t=1. Doing that would remove the need for this check,
michael@0:     // and would additionally remove the need for similar checks in condition edges. It would
michael@0:     // also allow intersection code to assume end of segment intersections (maybe?)
michael@0:     bool complete() const {
michael@0:         int count = fTs.count();
michael@0:         return count > 1 && fTs[0].fT == 0 && fTs[--count].fT == 1;
michael@0:     }
michael@0: 
michael@0:     int count() const {
michael@0:         return fTs.count();
michael@0:     }
michael@0: 
michael@0:     bool done() const {
michael@0:         SkASSERT(fDoneSpans <= fTs.count());
michael@0:         return fDoneSpans == fTs.count();
michael@0:     }
michael@0: 
michael@0:     bool done(int min) const {
michael@0:         return fTs[min].fDone;
michael@0:     }
michael@0: 
michael@0:     bool done(const SkOpAngle* angle) const {
michael@0:         return done(SkMin32(angle->start(), angle->end()));
michael@0:     }
michael@0: 
michael@0:     // used only by partial coincidence detection
michael@0:     SkDPoint dPtAtT(double mid) const {
michael@0:         return (*CurveDPointAtT[SkPathOpsVerbToPoints(fVerb)])(fPts, mid);
michael@0:     }
michael@0: 
michael@0:     SkVector dxdy(int index) const {
michael@0:         return (*CurveSlopeAtT[SkPathOpsVerbToPoints(fVerb)])(fPts, fTs[index].fT);
michael@0:     }
michael@0: 
michael@0:     SkScalar dy(int index) const {
michael@0:         return dxdy(index).fY;
michael@0:     }
michael@0: 
michael@0:     bool intersected() const {
michael@0:         return fTs.count() > 0;
michael@0:     }
michael@0: 
michael@0:     bool isCanceled(int tIndex) const {
michael@0:         return fTs[tIndex].fWindValue == 0 && fTs[tIndex].fOppValue == 0;
michael@0:     }
michael@0: 
michael@0:     bool isConnected(int startIndex, int endIndex) const {
michael@0:         return fTs[startIndex].fWindSum != SK_MinS32 || fTs[endIndex].fWindSum != SK_MinS32;
michael@0:     }
michael@0: 
michael@0:     bool isHorizontal() const {
michael@0:         return fBounds.fTop == fBounds.fBottom;
michael@0:     }
michael@0: 
michael@0:     bool isVertical() const {
michael@0:         return fBounds.fLeft == fBounds.fRight;
michael@0:     }
michael@0: 
michael@0:     bool isVertical(int start, int end) const {
michael@0:         return (*CurveIsVertical[SkPathOpsVerbToPoints(fVerb)])(fPts, start, end);
michael@0:     }
michael@0: 
michael@0:     bool operand() const {
michael@0:         return fOperand;
michael@0:     }
michael@0: 
michael@0:     int oppSign(const SkOpAngle* angle) const {
michael@0:         SkASSERT(angle->segment() == this);
michael@0:         return oppSign(angle->start(), angle->end());
michael@0:     }
michael@0: 
michael@0:     int oppSign(int startIndex, int endIndex) const {
michael@0:         int result = startIndex < endIndex ? -fTs[startIndex].fOppValue : fTs[endIndex].fOppValue;
michael@0: #if DEBUG_WIND_BUMP
michael@0:         SkDebugf("%s oppSign=%d\n", __FUNCTION__, result);
michael@0: #endif
michael@0:         return result;
michael@0:     }
michael@0: 
michael@0:     int oppSum(int tIndex) const {
michael@0:         return fTs[tIndex].fOppSum;
michael@0:     }
michael@0: 
michael@0:     int oppSum(const SkOpAngle* angle) const {
michael@0:         int lesser = SkMin32(angle->start(), angle->end());
michael@0:         return fTs[lesser].fOppSum;
michael@0:     }
michael@0: 
michael@0:     int oppValue(int tIndex) const {
michael@0:         return fTs[tIndex].fOppValue;
michael@0:     }
michael@0: 
michael@0:     int oppValue(const SkOpAngle* angle) const {
michael@0:         int lesser = SkMin32(angle->start(), angle->end());
michael@0:         return fTs[lesser].fOppValue;
michael@0:     }
michael@0: 
michael@0:     const SkOpSegment* other(int index) const {
michael@0:         return fTs[index].fOther;
michael@0:     }
michael@0: 
michael@0:     // was used only by right angle winding finding
michael@0:     SkPoint ptAtT(double mid) const {
michael@0:         return (*CurvePointAtT[SkPathOpsVerbToPoints(fVerb)])(fPts, mid);
michael@0:     }
michael@0: 
michael@0:     const SkPoint* pts() const {
michael@0:         return fPts;
michael@0:     }
michael@0: 
michael@0:     void reset() {
michael@0:         init(NULL, (SkPath::Verb) -1, false, false);
michael@0:         fBounds.set(SK_ScalarMax, SK_ScalarMax, SK_ScalarMax, SK_ScalarMax);
michael@0:         fTs.reset();
michael@0:     }
michael@0: 
michael@0:     void setOppXor(bool isOppXor) {
michael@0:         fOppXor = isOppXor;
michael@0:     }
michael@0: 
michael@0:     void setUpWinding(int index, int endIndex, int* maxWinding, int* sumWinding) {
michael@0:         int deltaSum = spanSign(index, endIndex);
michael@0:         *maxWinding = *sumWinding;
michael@0:         *sumWinding -= deltaSum;
michael@0:     }
michael@0: 
michael@0:     // OPTIMIZATION: mark as debugging only if used solely by tests
michael@0:     const SkOpSpan& span(int tIndex) const {
michael@0:         return fTs[tIndex];
michael@0:     }
michael@0: 
michael@0:     // OPTIMIZATION: mark as debugging only if used solely by tests
michael@0:     const SkTDArray<SkOpSpan>& spans() const {
michael@0:         return fTs;
michael@0:     }
michael@0: 
michael@0:     int spanSign(const SkOpAngle* angle) const {
michael@0:         SkASSERT(angle->segment() == this);
michael@0:         return spanSign(angle->start(), angle->end());
michael@0:     }
michael@0: 
michael@0:     int spanSign(int startIndex, int endIndex) const {
michael@0:         int result = startIndex < endIndex ? -fTs[startIndex].fWindValue : fTs[endIndex].fWindValue;
michael@0: #if DEBUG_WIND_BUMP
michael@0:         SkDebugf("%s spanSign=%d\n", __FUNCTION__, result);
michael@0: #endif
michael@0:         return result;
michael@0:     }
michael@0: 
michael@0:     double t(int tIndex) const {
michael@0:         return fTs[tIndex].fT;
michael@0:     }
michael@0: 
michael@0:     double tAtMid(int start, int end, double mid) const {
michael@0:         return fTs[start].fT * (1 - mid) + fTs[end].fT * mid;
michael@0:     }
michael@0: 
michael@0:     bool unsortable(int index) const {
michael@0:         return fTs[index].fUnsortableStart || fTs[index].fUnsortableEnd;
michael@0:     }
michael@0: 
michael@0:     void updatePts(const SkPoint pts[]) {
michael@0:         fPts = pts;
michael@0:     }
michael@0: 
michael@0:     SkPath::Verb verb() const {
michael@0:         return fVerb;
michael@0:     }
michael@0: 
michael@0:     int windSum(int tIndex) const {
michael@0:         return fTs[tIndex].fWindSum;
michael@0:     }
michael@0: 
michael@0:     int windValue(int tIndex) const {
michael@0:         return fTs[tIndex].fWindValue;
michael@0:     }
michael@0: 
michael@0: #if defined(SK_DEBUG) || DEBUG_WINDING
michael@0:     SkScalar xAtT(int index) const {
michael@0:         return xAtT(&fTs[index]);
michael@0:     }
michael@0: #endif
michael@0: 
michael@0:     const SkPoint& xyAtT(const SkOpSpan* span) const {
michael@0:         return span->fPt;
michael@0:     }
michael@0: 
michael@0:     const SkPoint& xyAtT(int index) const {
michael@0:         return xyAtT(&fTs[index]);
michael@0:     }
michael@0: 
michael@0: #if defined(SK_DEBUG) || DEBUG_WINDING
michael@0:     SkScalar yAtT(int index) const {
michael@0:         return yAtT(&fTs[index]);
michael@0:     }
michael@0: #endif
michael@0: 
michael@0:     bool activeAngle(int index, int* done, SkTArray<SkOpAngle, true>* angles);
michael@0:     SkPoint activeLeftTop(bool onlySortable, int* firstT) const;
michael@0:     bool activeOp(int index, int endIndex, int xorMiMask, int xorSuMask, SkPathOp op);
michael@0:     bool activeWinding(int index, int endIndex);
michael@0:     void addCubic(const SkPoint pts[4], bool operand, bool evenOdd);
michael@0:     void addCurveTo(int start, int end, SkPathWriter* path, bool active) const;
michael@0:     void addLine(const SkPoint pts[2], bool operand, bool evenOdd);
michael@0:     void addOtherT(int index, double otherT, int otherIndex);
michael@0:     void addQuad(const SkPoint pts[3], bool operand, bool evenOdd);
michael@0:     int addSelfT(SkOpSegment* other, const SkPoint& pt, double newT);
michael@0:     int addT(SkOpSegment* other, const SkPoint& pt, double newT);
michael@0:     void addTCancel(const SkPoint& startPt, const SkPoint& endPt, SkOpSegment* other);
michael@0:     void addTCoincident(const SkPoint& startPt, const SkPoint& endPt, double endT,
michael@0:             SkOpSegment* other);
michael@0:     void addTPair(double t, SkOpSegment* other, double otherT, bool borrowWind, const SkPoint& pt);
michael@0:     bool betweenTs(int lesser, double testT, int greater) const;
michael@0:     void checkEnds();
michael@0:     bool checkSmall(int index) const;
michael@0:     void checkTiny();
michael@0:     int computeSum(int startIndex, int endIndex, SkOpAngle::IncludeType includeType,
michael@0:                     SkTArray<SkOpAngle, true>* angles, SkTArray<SkOpAngle*, true>* sorted);
michael@0:     int crossedSpanY(const SkPoint& basePt, SkScalar* bestY, double* hitT, bool* hitSomething,
michael@0:                      double mid, bool opp, bool current) const;
michael@0:     bool findCoincidentMatch(const SkOpSpan* span, const SkOpSegment* other, int oStart, int oEnd,
michael@0:                              int step, SkPoint* startPt, SkPoint* endPt, double* endT) const;
michael@0:     SkOpSegment* findNextOp(SkTDArray<SkOpSpan*>* chase, int* nextStart, int* nextEnd,
michael@0:                             bool* unsortable, SkPathOp op, const int xorMiMask,
michael@0:                             const int xorSuMask);
michael@0:     SkOpSegment* findNextWinding(SkTDArray<SkOpSpan*>* chase, int* nextStart, int* nextEnd,
michael@0:                                  bool* unsortable);
michael@0:     SkOpSegment* findNextXor(int* nextStart, int* nextEnd, bool* unsortable);
michael@0:     int findT(double t, const SkOpSegment* ) const;
michael@0:     SkOpSegment* findTop(int* tIndex, int* endIndex, bool* unsortable, bool onlySortable);
michael@0:     void fixOtherTIndex();
michael@0:     void initWinding(int start, int end);
michael@0:     void initWinding(int start, int end, double tHit, int winding, SkScalar hitDx, int oppWind,
michael@0:                      SkScalar hitOppDx);
michael@0:     bool isMissing(double startT, const SkPoint& pt) const;
michael@0:     bool isTiny(const SkOpAngle* angle) const;
michael@0:     bool joinCoincidence(SkOpSegment* other, double otherT, int step, bool cancel);
michael@0:     SkOpSpan* markAndChaseDoneBinary(int index, int endIndex);
michael@0:     SkOpSpan* markAndChaseDoneUnary(int index, int endIndex);
michael@0:     SkOpSpan* markAndChaseWinding(const SkOpAngle* angle, int winding, int oppWinding);
michael@0:     SkOpSpan* markAngle(int maxWinding, int sumWinding, int oppMaxWinding, int oppSumWinding,
michael@0:                         const SkOpAngle* angle);
michael@0:     void markDone(int index, int winding);
michael@0:     void markDoneBinary(int index);
michael@0:     void markDoneUnary(int index);
michael@0:     bool nextCandidate(int* start, int* end) const;
michael@0:     int nextSpan(int from, int step) const;
michael@0:     void setUpWindings(int index, int endIndex, int* sumMiWinding, int* sumSuWinding,
michael@0:             int* maxWinding, int* sumWinding, int* oppMaxWinding, int* oppSumWinding);
michael@0:     enum SortAngleKind {
michael@0:         kMustBeOrdered_SortAngleKind, // required for winding calc
michael@0:         kMayBeUnordered_SortAngleKind // ok for find top
michael@0:     };
michael@0:     static bool SortAngles(const SkTArray<SkOpAngle, true>& angles,  // FIXME: replace with
michael@0:                            SkTArray<SkOpAngle*, true>* angleList,    //  Sort Angles 2
michael@0:                            SortAngleKind );
michael@0:     static bool SortAngles2(const SkTArray<SkOpAngle, true>& angles,
michael@0:                             SkTArray<SkOpAngle*, true>* angleList);
michael@0:     bool subDivide(int start, int end, SkPoint edge[4]) const;
michael@0:     bool subDivide(int start, int end, SkDCubic* result) const;
michael@0:     void undoneSpan(int* start, int* end);
michael@0:     int updateOppWindingReverse(const SkOpAngle* angle) const;
michael@0:     int updateWindingReverse(const SkOpAngle* angle) const;
michael@0:     static bool UseInnerWinding(int outerWinding, int innerWinding);
michael@0:     int windingAtT(double tHit, int tIndex, bool crossOpp, SkScalar* dx) const;
michael@0:     int windSum(const SkOpAngle* angle) const;
michael@0: 
michael@0: #ifdef SK_DEBUG
michael@0:     int debugID() const {
michael@0:         return fID;
michael@0:     }
michael@0: #endif
michael@0: #if DEBUG_ACTIVE_SPANS || DEBUG_ACTIVE_SPANS_FIRST_ONLY
michael@0:     void debugShowActiveSpans() const;
michael@0: #endif
michael@0: #if DEBUG_SORT || DEBUG_SWAP_TOP
michael@0:     void debugShowSort(const char* fun, const SkTArray<SkOpAngle*, true>& angles, int first,
michael@0:             const int contourWinding, const int oppContourWinding, bool sortable) const;
michael@0:     void debugShowSort(const char* fun, const SkTArray<SkOpAngle*, true>& angles, int first,
michael@0:             bool sortable);
michael@0: #endif
michael@0: #if DEBUG_CONCIDENT
michael@0:     void debugShowTs(const char* prefix) const;
michael@0: #endif
michael@0: #if DEBUG_SHOW_WINDING
michael@0:     int debugShowWindingValues(int slotCount, int ofInterest) const;
michael@0: #endif
michael@0: 
michael@0: private:
michael@0:     struct MissingSpan  {
michael@0:         double fT;
michael@0:         double fEndT;
michael@0:         SkOpSegment* fSegment;
michael@0:         SkOpSegment* fOther;
michael@0:         double fOtherT;
michael@0:         SkPoint fPt;
michael@0:     };
michael@0: 
michael@0:     bool activeAngleOther(int index, int* done, SkTArray<SkOpAngle, true>* angles);
michael@0:     bool activeAngleInner(int index, int* done, SkTArray<SkOpAngle, true>* angles);
michael@0:     bool activeOp(int xorMiMask, int xorSuMask, int index, int endIndex, SkPathOp op,
michael@0:                   int* sumMiWinding, int* sumSuWinding, int* maxWinding, int* sumWinding,
michael@0:                   int* oppMaxWinding, int* oppSumWinding);
michael@0:     bool activeWinding(int index, int endIndex, int* maxWinding, int* sumWinding);
michael@0:     void addAngle(SkTArray<SkOpAngle, true>* angles, int start, int end) const;
michael@0:     void addCancelOutsides(const SkPoint& startPt, const SkPoint& endPt, SkOpSegment* other);
michael@0:     void addCoinOutsides(const SkPoint& startPt, const SkPoint& endPt, SkOpSegment* other);
michael@0:     void addTPair(double t, SkOpSegment* other, double otherT, bool borrowWind, const SkPoint& pt,
michael@0:                   const SkPoint& oPt);
michael@0:     void addTwoAngles(int start, int end, SkTArray<SkOpAngle, true>* angles) const;
michael@0:     bool betweenPoints(double midT, const SkPoint& pt1, const SkPoint& pt2) const;
michael@0:     bool buildAngles(int index, SkTArray<SkOpAngle, true>* angles, bool includeOpp) const;
michael@0:     void buildAnglesInner(int index, SkTArray<SkOpAngle, true>* angles) const;
michael@0:     void bumpCoincidentThis(const SkOpSpan& oTest, bool binary, int* index,
michael@0:                            SkTArray<SkPoint, true>* outsideTs);
michael@0:     void bumpCoincidentOther(const SkOpSpan& oTest, int* index,
michael@0:                            SkTArray<SkPoint, true>* outsideTs);
michael@0:     bool bumpSpan(SkOpSpan* span, int windDelta, int oppDelta);
michael@0:     bool clockwise(int tStart, int tEnd) const;
michael@0:     static void ComputeOneSum(const SkOpAngle* baseAngle, SkOpAngle* nextAngle,
michael@0:                               SkOpAngle::IncludeType );
michael@0:     static void ComputeOneSumReverse(const SkOpAngle* baseAngle, SkOpAngle* nextAngle,
michael@0:                                      SkOpAngle::IncludeType );
michael@0:     bool decrementSpan(SkOpSpan* span);
michael@0:     int findStartingEdge(const SkTArray<SkOpAngle*, true>& sorted, int start, int end);
michael@0:     void init(const SkPoint pts[], SkPath::Verb verb, bool operand, bool evenOdd);
michael@0:     bool isSimple(int end) const;
michael@0:     bool isTiny(int index) const;
michael@0:     void matchWindingValue(int tIndex, double t, bool borrowWind);
michael@0:     SkOpSpan* markAndChaseDone(int index, int endIndex, int winding);
michael@0:     SkOpSpan* markAndChaseDoneBinary(const SkOpAngle* angle, int winding, int oppWinding);
michael@0:     SkOpSpan* markAndChaseWinding(const SkOpAngle* angle, const int winding);
michael@0:     SkOpSpan* markAndChaseWinding(int index, int endIndex, int winding, int oppWinding);
michael@0:     SkOpSpan* markAngle(int maxWinding, int sumWinding, const SkOpAngle* angle);
michael@0:     void markDoneBinary(int index, int winding, int oppWinding);
michael@0:     SkOpSpan* markAndChaseDoneUnary(const SkOpAngle* angle, int winding);
michael@0:     void markOneDone(const char* funName, int tIndex, int winding);
michael@0:     void markOneDoneBinary(const char* funName, int tIndex);
michael@0:     void markOneDoneBinary(const char* funName, int tIndex, int winding, int oppWinding);
michael@0:     void markOneDoneUnary(const char* funName, int tIndex);
michael@0:     SkOpSpan* markOneWinding(const char* funName, int tIndex, int winding);
michael@0:     SkOpSpan* markOneWinding(const char* funName, int tIndex, int winding, int oppWinding);
michael@0:     void markWinding(int index, int winding);
michael@0:     void markWinding(int index, int winding, int oppWinding);
michael@0:     void markUnsortable(int start, int end);
michael@0:     bool monotonicInY(int tStart, int tEnd) const;
michael@0:     bool multipleSpans(int end) const;
michael@0:     SkOpSegment* nextChase(int* index, const int step, int* min, SkOpSpan** last);
michael@0:     int nextExactSpan(int from, int step) const;
michael@0:     bool serpentine(int tStart, int tEnd) const;
michael@0:     void setUpWindings(int index, int endIndex, int* sumMiWinding,
michael@0:             int* maxWinding, int* sumWinding);
michael@0:     void subDivideBounds(int start, int end, SkPathOpsBounds* bounds) const;
michael@0:     static void TrackOutsidePair(SkTArray<SkPoint, true>* outsideTs, const SkPoint& endPt,
michael@0:             const SkPoint& startPt);
michael@0:     static void TrackOutside(SkTArray<SkPoint, true>* outsideTs, const SkPoint& startPt);
michael@0:     int updateOppWinding(int index, int endIndex) const;
michael@0:     int updateOppWinding(const SkOpAngle* angle) const;
michael@0:     int updateWinding(int index, int endIndex) const;
michael@0:     int updateWinding(const SkOpAngle* angle) const;
michael@0:     int updateWindingReverse(int index, int endIndex) const;
michael@0:     static bool UseInnerWindingReverse(int outerWinding, int innerWinding);
michael@0:     SkOpSpan* verifyOneWinding(const char* funName, int tIndex);
michael@0:     SkOpSpan* verifyOneWindingU(const char* funName, int tIndex);
michael@0: 
michael@0:     SkScalar xAtT(const SkOpSpan* span) const {
michael@0:         return xyAtT(span).fX;
michael@0:     }
michael@0: 
michael@0:     SkScalar yAtT(const SkOpSpan* span) const {
michael@0:         return xyAtT(span).fY;
michael@0:     }
michael@0: 
michael@0:     void zeroSpan(SkOpSpan* span);
michael@0: 
michael@0: #if DEBUG_SWAP_TOP
michael@0:     bool controlsContainedByEnds(int tStart, int tEnd) const;
michael@0: #endif
michael@0: #if DEBUG_CONCIDENT
michael@0:      void debugAddTPair(double t, const SkOpSegment& other, double otherT) const;
michael@0: #endif
michael@0: #if DEBUG_MARK_DONE || DEBUG_UNSORTABLE
michael@0:     void debugShowNewWinding(const char* fun, const SkOpSpan& span, int winding);
michael@0:     void debugShowNewWinding(const char* fun, const SkOpSpan& span, int winding, int oppWinding);
michael@0: #endif
michael@0: #if DEBUG_WINDING
michael@0:     static char as_digit(int value) {
michael@0:         return value < 0 ? '?' : value <= 9 ? '0' + value : '+';
michael@0:     }
michael@0: #endif
michael@0:     void debugValidate() const;
michael@0: #ifdef SK_DEBUG
michael@0:     void dumpPts() const;
michael@0:     void dumpDPts() const;
michael@0:     void dumpSpans() const;
michael@0: #endif
michael@0: 
michael@0:     const SkPoint* fPts;
michael@0:     SkPathOpsBounds fBounds;
michael@0:     // FIXME: can't convert to SkTArray because it uses insert
michael@0:     SkTDArray<SkOpSpan> fTs;  // two or more (always includes t=0 t=1)
michael@0:     // OPTIMIZATION: could pack donespans, verb, operand, xor into 1 int-sized value
michael@0:     int fDoneSpans;  // quick check that segment is finished
michael@0:     // OPTIMIZATION: force the following to be byte-sized
michael@0:     SkPath::Verb fVerb;
michael@0:     bool fOperand;
michael@0:     bool fXor;  // set if original contour had even-odd fill
michael@0:     bool fOppXor;  // set if opposite operand had even-odd fill
michael@0: #ifdef SK_DEBUG
michael@0:     int fID;
michael@0: #endif
michael@0: };
michael@0: 
michael@0: #endif