| /* |
| * 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 "SkPathOpsBounds.h" |
| #include "SkPathOpsCurve.h" |
| #include "SkTArray.h" |
| #include "SkTDArray.h" |
| |
| class SkPathWriter; |
| |
| class SkOpSegment { |
| public: |
| SkOpSegment() { |
| #if defined(SK_DEBUG) || !FORCE_RELEASE |
| fID = ++SkPathOpsDebug::gSegmentID; |
| #endif |
| } |
| |
| bool operator<(const SkOpSegment& rh) const { |
| return fBounds.fTop < rh.fBounds.fTop; |
| } |
| |
| // FIXME: add some template or macro to avoid casting |
| SkOpAngle& angle(int index) { |
| const SkOpAngle& cAngle = (const_cast<const SkOpSegment*>(this))->angle(index); |
| return const_cast<SkOpAngle&>(cAngle); |
| } |
| |
| const SkPathOpsBounds& bounds() const { |
| return fBounds; |
| } |
| |
| // OPTIMIZE |
| // when the edges are initially walked, they don't automatically get the prior and next |
| // edges assigned to positions t=0 and t=1. Doing that would remove the need for this check, |
| // and would additionally remove the need for similar checks in condition edges. It would |
| // also allow intersection code to assume end of segment intersections (maybe?) |
| bool complete() const { |
| int count = fTs.count(); |
| return count > 1 && fTs[0].fT == 0 && fTs[--count].fT == 1; |
| } |
| |
| int count() const { |
| return fTs.count(); |
| } |
| |
| bool done() const { |
| SkASSERT(fDoneSpans <= fTs.count()); |
| return fDoneSpans == fTs.count(); |
| } |
| |
| bool done(int min) const { |
| return fTs[min].fDone; |
| } |
| |
| bool done(const SkOpAngle* angle) const { |
| return done(SkMin32(angle->start(), angle->end())); |
| } |
| |
| SkDPoint dPtAtT(double mid) const { |
| return (*CurveDPointAtT[SkPathOpsVerbToPoints(fVerb)])(fPts, mid); |
| } |
| |
| SkVector dxdy(int index) const { |
| return (*CurveSlopeAtT[SkPathOpsVerbToPoints(fVerb)])(fPts, fTs[index].fT); |
| } |
| |
| SkScalar dy(int index) const { |
| return dxdy(index).fY; |
| } |
| |
| bool hasSmall() const { |
| return fSmall; |
| } |
| |
| bool hasTiny() const { |
| return fTiny; |
| } |
| |
| bool intersected() const { |
| return fTs.count() > 0; |
| } |
| |
| bool isCanceled(int tIndex) const { |
| return fTs[tIndex].fWindValue == 0 && fTs[tIndex].fOppValue == 0; |
| } |
| |
| bool isConnected(int startIndex, int endIndex) const { |
| return fTs[startIndex].fWindSum != SK_MinS32 || fTs[endIndex].fWindSum != SK_MinS32; |
| } |
| |
| bool isHorizontal() const { |
| return fBounds.fTop == fBounds.fBottom; |
| } |
| |
| bool isVertical() const { |
| return fBounds.fLeft == fBounds.fRight; |
| } |
| |
| bool isVertical(int start, int end) const { |
| return (*CurveIsVertical[SkPathOpsVerbToPoints(fVerb)])(fPts, start, end); |
| } |
| |
| bool operand() const { |
| return fOperand; |
| } |
| |
| int oppSign(const SkOpAngle* angle) const { |
| SkASSERT(angle->segment() == this); |
| return oppSign(angle->start(), angle->end()); |
| } |
| |
| int oppSign(int startIndex, int endIndex) const { |
| int result = startIndex < endIndex ? -fTs[startIndex].fOppValue : fTs[endIndex].fOppValue; |
| #if DEBUG_WIND_BUMP |
| SkDebugf("%s oppSign=%d\n", __FUNCTION__, result); |
| #endif |
| return result; |
| } |
| |
| int oppSum(int tIndex) const { |
| return fTs[tIndex].fOppSum; |
| } |
| |
| int oppSum(const SkOpAngle* angle) const { |
| int lesser = SkMin32(angle->start(), angle->end()); |
| return fTs[lesser].fOppSum; |
| } |
| |
| int oppValue(int tIndex) const { |
| return fTs[tIndex].fOppValue; |
| } |
| |
| int oppValue(const SkOpAngle* angle) const { |
| int lesser = SkMin32(angle->start(), angle->end()); |
| return fTs[lesser].fOppValue; |
| } |
| |
| #if DEBUG_VALIDATE |
| bool oppXor() const { |
| return fOppXor; |
| } |
| #endif |
| |
| SkPoint ptAtT(double mid) const { |
| return (*CurvePointAtT[SkPathOpsVerbToPoints(fVerb)])(fPts, mid); |
| } |
| |
| const SkPoint* pts() const { |
| return fPts; |
| } |
| |
| void reset() { |
| init(NULL, (SkPath::Verb) -1, false, false); |
| fBounds.set(SK_ScalarMax, SK_ScalarMax, SK_ScalarMax, SK_ScalarMax); |
| fTs.reset(); |
| } |
| |
| void setOppXor(bool isOppXor) { |
| fOppXor = isOppXor; |
| } |
| |
| void setUpWinding(int index, int endIndex, int* maxWinding, int* sumWinding) { |
| int deltaSum = spanSign(index, endIndex); |
| *maxWinding = *sumWinding; |
| *sumWinding -= deltaSum; |
| } |
| |
| const SkOpSpan& span(int tIndex) const { |
| return fTs[tIndex]; |
| } |
| |
| const SkOpAngle* spanToAngle(int tStart, int tEnd) const { |
| SkASSERT(tStart != tEnd); |
| const SkOpSpan& span = fTs[tStart]; |
| int index = tStart < tEnd ? span.fToAngleIndex : span.fFromAngleIndex; |
| return index >= 0 ? &angle(index) : NULL; |
| } |
| |
| // FIXME: create some sort of macro or template that avoids casting |
| SkOpAngle* spanToAngle(int tStart, int tEnd) { |
| const SkOpAngle* cAngle = (const_cast<const SkOpSegment*>(this))->spanToAngle(tStart, tEnd); |
| return const_cast<SkOpAngle*>(cAngle); |
| } |
| |
| int spanSign(const SkOpAngle* angle) const { |
| SkASSERT(angle->segment() == this); |
| return spanSign(angle->start(), angle->end()); |
| } |
| |
| int spanSign(int startIndex, int endIndex) const { |
| int result = startIndex < endIndex ? -fTs[startIndex].fWindValue : fTs[endIndex].fWindValue; |
| #if DEBUG_WIND_BUMP |
| SkDebugf("%s spanSign=%d\n", __FUNCTION__, result); |
| #endif |
| return result; |
| } |
| |
| double t(int tIndex) const { |
| return fTs[tIndex].fT; |
| } |
| |
| double tAtMid(int start, int end, double mid) const { |
| return fTs[start].fT * (1 - mid) + fTs[end].fT * mid; |
| } |
| |
| void updatePts(const SkPoint pts[]) { |
| fPts = pts; |
| } |
| |
| SkPath::Verb verb() const { |
| return fVerb; |
| } |
| |
| int windSum(int tIndex) const { |
| return fTs[tIndex].fWindSum; |
| } |
| |
| int windValue(int tIndex) const { |
| return fTs[tIndex].fWindValue; |
| } |
| |
| #if defined(SK_DEBUG) || DEBUG_WINDING |
| SkScalar xAtT(int index) const { |
| return xAtT(&fTs[index]); |
| } |
| #endif |
| |
| #if DEBUG_VALIDATE |
| bool _xor() const { // FIXME: used only by SkOpAngle::debugValidateLoop() |
| return fXor; |
| } |
| #endif |
| |
| const SkPoint& xyAtT(const SkOpSpan* span) const { |
| return span->fPt; |
| } |
| |
| const SkPoint& xyAtT(int index) const { |
| return xyAtT(&fTs[index]); |
| } |
| |
| #if defined(SK_DEBUG) || DEBUG_WINDING |
| SkScalar yAtT(int index) const { |
| return yAtT(&fTs[index]); |
| } |
| #endif |
| |
| const SkOpAngle* activeAngle(int index, int* start, int* end, bool* done, |
| bool* sortable) const; |
| SkPoint activeLeftTop(int* firstT) const; |
| bool activeOp(int index, int endIndex, int xorMiMask, int xorSuMask, SkPathOp op); |
| bool activeWinding(int index, int endIndex); |
| void addCubic(const SkPoint pts[4], bool operand, bool evenOdd); |
| void addCurveTo(int start, int end, SkPathWriter* path, bool active) const; |
| void addEndSpan(int endIndex); |
| void addLine(const SkPoint pts[2], bool operand, bool evenOdd); |
| void addOtherT(int index, double otherT, int otherIndex); |
| void addQuad(const SkPoint pts[3], bool operand, bool evenOdd); |
| void addSimpleAngle(int endIndex); |
| int addSelfT(const SkPoint& pt, double newT); |
| void addStartSpan(int endIndex); |
| int addT(SkOpSegment* other, const SkPoint& pt, double newT); |
| void addTCancel(const SkPoint& startPt, const SkPoint& endPt, SkOpSegment* other); |
| void addTCoincident(const SkPoint& startPt, const SkPoint& endPt, double endT, |
| SkOpSegment* other); |
| const SkOpSpan* addTPair(double t, SkOpSegment* other, double otherT, bool borrowWind, |
| const SkPoint& pt); |
| bool alignSpan(int index, double thisT, const SkPoint& thisPt); |
| void alignSpanState(int start, int end); |
| const SkOpAngle& angle(int index) const; |
| bool betweenTs(int lesser, double testT, int greater) const; |
| bool calcAngles(); |
| void checkDuplicates(); |
| void checkEnds(); |
| void checkMultiples(); |
| void checkSmall(); |
| bool checkSmall(int index) const; |
| void checkTiny(); |
| int computeSum(int startIndex, int endIndex, SkOpAngle::IncludeType includeType); |
| bool containsPt(const SkPoint& , int index, int endIndex) const; |
| int crossedSpanY(const SkPoint& basePt, SkScalar* bestY, double* hitT, bool* hitSomething, |
| double mid, bool opp, bool current) const; |
| bool findCoincidentMatch(const SkOpSpan* span, const SkOpSegment* other, int oStart, int oEnd, |
| int step, SkPoint* startPt, SkPoint* endPt, double* endT) const; |
| SkOpSegment* findNextOp(SkTDArray<SkOpSpan*>* chase, int* nextStart, int* nextEnd, |
| bool* unsortable, SkPathOp op, int xorMiMask, int xorSuMask); |
| SkOpSegment* findNextWinding(SkTDArray<SkOpSpan*>* chase, int* nextStart, int* nextEnd, |
| bool* unsortable); |
| SkOpSegment* findNextXor(int* nextStart, int* nextEnd, bool* unsortable); |
| int findExactT(double t, const SkOpSegment* ) const; |
| int findT(double t, const SkPoint& , const SkOpSegment* ) const; |
| SkOpSegment* findTop(int* tIndex, int* endIndex, bool* unsortable, bool firstPass); |
| void fixOtherTIndex(); |
| void initWinding(int start, int end, SkOpAngle::IncludeType angleIncludeType); |
| void initWinding(int start, int end, double tHit, int winding, SkScalar hitDx, int oppWind, |
| SkScalar hitOppDx); |
| bool isMissing(double startT, const SkPoint& pt) const; |
| bool isTiny(const SkOpAngle* angle) const; |
| bool joinCoincidence(SkOpSegment* other, double otherT, const SkPoint& otherPt, int step, |
| bool cancel); |
| SkOpSpan* markAndChaseDoneBinary(int index, int endIndex); |
| SkOpSpan* markAndChaseDoneUnary(int index, int endIndex); |
| SkOpSpan* markAndChaseWinding(const SkOpAngle* angle, int winding, int oppWinding); |
| SkOpSpan* markAngle(int maxWinding, int sumWinding, int oppMaxWinding, int oppSumWinding, |
| const SkOpAngle* angle); |
| void markDone(int index, int winding); |
| void markDoneBinary(int index); |
| void markDoneUnary(int index); |
| bool nextCandidate(int* start, int* end) const; |
| int nextSpan(int from, int step) const; |
| void setUpWindings(int index, int endIndex, int* sumMiWinding, int* sumSuWinding, |
| int* maxWinding, int* sumWinding, int* oppMaxWinding, int* oppSumWinding); |
| void sortAngles(); |
| bool subDivide(int start, int end, SkPoint edge[4]) const; |
| bool subDivide(int start, int end, SkDCubic* result) const; |
| void undoneSpan(int* start, int* end); |
| int updateOppWindingReverse(const SkOpAngle* angle) const; |
| int updateWindingReverse(const SkOpAngle* angle) const; |
| static bool UseInnerWinding(int outerWinding, int innerWinding); |
| static bool UseInnerWindingReverse(int outerWinding, int innerWinding); |
| int windingAtT(double tHit, int tIndex, bool crossOpp, SkScalar* dx) const; |
| int windSum(const SkOpAngle* angle) const; |
| // available for testing only |
| #if DEBUG_VALIDATE |
| bool debugContains(const SkOpAngle* ) const; |
| #endif |
| #if defined(SK_DEBUG) || !FORCE_RELEASE |
| int debugID() const { |
| return fID; |
| } |
| #else |
| int debugID() const { |
| return -1; |
| } |
| #endif |
| #if DEBUG_ACTIVE_SPANS || DEBUG_ACTIVE_SPANS_FIRST_ONLY |
| void debugShowActiveSpans() const; |
| #endif |
| #if DEBUG_CONCIDENT |
| void debugShowTs(const char* prefix) const; |
| #endif |
| #if DEBUG_SHOW_WINDING |
| int debugShowWindingValues(int slotCount, int ofInterest) const; |
| #endif |
| const SkTDArray<SkOpSpan>& debugSpans() const; |
| void debugValidate() const; |
| // available to testing only |
| void dumpAngles() const; |
| void dumpContour(int firstID, int lastID) const; |
| void dumpPts() const; |
| void dumpSpans() const; |
| |
| private: |
| struct MissingSpan { |
| double fT; |
| double fEndT; |
| SkOpSegment* fSegment; |
| SkOpSegment* fOther; |
| double fOtherT; |
| SkPoint fPt; |
| }; |
| |
| const SkOpAngle* activeAngleInner(int index, int* start, int* end, bool* done, |
| bool* sortable) const; |
| const SkOpAngle* activeAngleOther(int index, int* start, int* end, bool* done, |
| bool* sortable) const; |
| bool activeOp(int xorMiMask, int xorSuMask, int index, int endIndex, SkPathOp op, |
| int* sumMiWinding, int* sumSuWinding); |
| bool activeWinding(int index, int endIndex, int* sumWinding); |
| void addCancelOutsides(const SkPoint& startPt, const SkPoint& endPt, SkOpSegment* other); |
| void addCoinOutsides(const SkPoint& startPt, const SkPoint& endPt, SkOpSegment* other); |
| int addSingletonAngleDown(int start, SkOpSegment** otherPtr); |
| int addSingletonAngleUp(int start, SkOpSegment** otherPtr); |
| SkOpAngle* addSingletonAngles(int start, int step); |
| void addTPair(double t, SkOpSegment* other, double otherT, bool borrowWind, const SkPoint& pt, |
| const SkPoint& oPt); |
| bool betweenPoints(double midT, const SkPoint& pt1, const SkPoint& pt2) const; |
| void bumpCoincidentThis(const SkOpSpan& oTest, bool binary, int* index, |
| SkTArray<SkPoint, true>* outsideTs); |
| void bumpCoincidentOther(const SkOpSpan& oTest, int* index, |
| SkTArray<SkPoint, true>* outsideTs); |
| bool bumpSpan(SkOpSpan* span, int windDelta, int oppDelta); |
| bool calcLoopSpanCount(const SkOpSpan& thisSpan, int* smallCounts); |
| void checkLinks(const SkOpSpan* , |
| SkTArray<MissingSpan, true>* missingSpans) const; |
| static void CheckOneLink(const SkOpSpan* test, const SkOpSpan* oSpan, |
| const SkOpSpan* oFirst, const SkOpSpan* oLast, |
| const SkOpSpan** missingPtr, |
| SkTArray<MissingSpan, true>* missingSpans); |
| int checkSetAngle(int tIndex) const; |
| void checkSmallCoincidence(const SkOpSpan& span, SkTArray<MissingSpan, true>* ); |
| bool clockwise(int tStart, int tEnd) const; |
| static void ComputeOneSum(const SkOpAngle* baseAngle, SkOpAngle* nextAngle, |
| SkOpAngle::IncludeType ); |
| static void ComputeOneSumReverse(const SkOpAngle* baseAngle, SkOpAngle* nextAngle, |
| SkOpAngle::IncludeType ); |
| bool decrementSpan(SkOpSpan* span); |
| int findEndSpan(int endIndex) const; |
| int findStartSpan(int startIndex) const; |
| int firstActive(int tIndex) const; |
| const SkOpSpan& firstSpan(const SkOpSpan& thisSpan) const; |
| void init(const SkPoint pts[], SkPath::Verb verb, bool operand, bool evenOdd); |
| bool inLoop(const SkOpAngle* baseAngle, int spanCount, int* indexPtr) const; |
| bool isSimple(int end) const; |
| bool isTiny(int index) const; |
| const SkOpSpan& lastSpan(const SkOpSpan& thisSpan) const; |
| void matchWindingValue(int tIndex, double t, bool borrowWind); |
| SkOpSpan* markAndChaseDone(int index, int endIndex, int winding); |
| SkOpSpan* markAndChaseDoneBinary(const SkOpAngle* angle, int winding, int oppWinding); |
| SkOpSpan* markAndChaseWinding(const SkOpAngle* angle, int winding); |
| SkOpSpan* markAndChaseWinding(int index, int endIndex, int winding); |
| SkOpSpan* markAndChaseWinding(int index, int endIndex, int winding, int oppWinding); |
| SkOpSpan* markAngle(int maxWinding, int sumWinding, const SkOpAngle* angle); |
| void markDoneBinary(int index, int winding, int oppWinding); |
| SkOpSpan* markAndChaseDoneUnary(const SkOpAngle* angle, int winding); |
| void markOneDone(const char* funName, int tIndex, int winding); |
| void markOneDoneBinary(const char* funName, int tIndex); |
| void markOneDoneBinary(const char* funName, int tIndex, int winding, int oppWinding); |
| void markOneDoneUnary(const char* funName, int tIndex); |
| SkOpSpan* markOneWinding(const char* funName, int tIndex, int winding); |
| SkOpSpan* markOneWinding(const char* funName, int tIndex, int winding, int oppWinding); |
| void markWinding(int index, int winding); |
| void markWinding(int index, int winding, int oppWinding); |
| bool monotonicInY(int tStart, int tEnd) const; |
| |
| bool multipleEnds() const { |
| return fTs[count() - 2].fT == 1; |
| } |
| |
| bool multipleStarts() const { |
| return fTs[1].fT == 0; |
| } |
| |
| bool multipleSpans(int end) const; |
| SkOpSegment* nextChase(int* index, const int step, int* min, SkOpSpan** last); |
| int nextExactSpan(int from, int step) const; |
| bool serpentine(int tStart, int tEnd) const; |
| void setFromAngleIndex(int endIndex, int angleIndex); |
| void setToAngleIndex(int endIndex, int angleIndex); |
| void setUpWindings(int index, int endIndex, int* sumMiWinding, |
| int* maxWinding, int* sumWinding); |
| void subDivideBounds(int start, int end, SkPathOpsBounds* bounds) const; |
| static void TrackOutsidePair(SkTArray<SkPoint, true>* outsideTs, const SkPoint& endPt, |
| const SkPoint& startPt); |
| static void TrackOutside(SkTArray<SkPoint, true>* outsideTs, const SkPoint& startPt); |
| int updateOppWinding(int index, int endIndex) const; |
| int updateOppWinding(const SkOpAngle* angle) const; |
| int updateWinding(int index, int endIndex) const; |
| int updateWinding(const SkOpAngle* angle) const; |
| int updateWindingReverse(int index, int endIndex) const; |
| SkOpSpan* verifyOneWinding(const char* funName, int tIndex); |
| SkOpSpan* verifyOneWindingU(const char* funName, int tIndex); |
| |
| SkScalar xAtT(const SkOpSpan* span) const { |
| return xyAtT(span).fX; |
| } |
| |
| SkScalar yAtT(const SkOpSpan* span) const { |
| return xyAtT(span).fY; |
| } |
| |
| void zeroSpan(SkOpSpan* span); |
| |
| #if DEBUG_SWAP_TOP |
| bool controlsContainedByEnds(int tStart, int tEnd) const; |
| #endif |
| void debugAddAngle(int start, int end); |
| #if DEBUG_CONCIDENT |
| void debugAddTPair(double t, const SkOpSegment& other, double otherT) const; |
| #endif |
| #if DEBUG_ANGLE |
| void debugCheckPointsEqualish(int tStart, int tEnd) const; |
| #endif |
| #if DEBUG_SWAP_TOP |
| int debugInflections(int index, int endIndex) const; |
| #endif |
| #if DEBUG_MARK_DONE || DEBUG_UNSORTABLE |
| void debugShowNewWinding(const char* fun, const SkOpSpan& span, int winding); |
| void debugShowNewWinding(const char* fun, const SkOpSpan& span, int winding, int oppWinding); |
| #endif |
| #if DEBUG_WINDING |
| static char as_digit(int value) { |
| return value < 0 ? '?' : value <= 9 ? '0' + value : '+'; |
| } |
| #endif |
| // available to testing only |
| void debugConstruct(); |
| void debugConstructCubic(SkPoint shortQuad[4]); |
| void debugConstructLine(SkPoint shortQuad[2]); |
| void debugConstructQuad(SkPoint shortQuad[3]); |
| void debugReset(); |
| void dumpDPts() const; |
| void dumpSpan(int index) const; |
| |
| const SkPoint* fPts; |
| SkPathOpsBounds fBounds; |
| // FIXME: can't convert to SkTArray because it uses insert |
| SkTDArray<SkOpSpan> fTs; // 2+ (always includes t=0 t=1) -- at least (number of spans) + 1 |
| // FIXME: replace both with bucket storage that allows direct immovable pointers to angles |
| SkTArray<SkOpAngle, true> fSingletonAngles; // 0 or 2 -- allocated for singletons |
| SkTArray<SkOpAngle, true> fAngles; // 0 or 2+ -- (number of non-zero spans) * 2 |
| // OPTIMIZATION: could pack donespans, verb, operand, xor into 1 int-sized value |
| int fDoneSpans; // quick check that segment is finished |
| // OPTIMIZATION: force the following to be byte-sized |
| SkPath::Verb fVerb; |
| bool fLoop; // set if cubic intersects itself |
| bool fOperand; |
| bool fXor; // set if original contour had even-odd fill |
| bool fOppXor; // set if opposite operand had even-odd fill |
| bool fSmall; // set if some span is small |
| bool fTiny; // set if some span is tiny |
| #if defined(SK_DEBUG) || !FORCE_RELEASE |
| int fID; |
| #endif |
| |
| friend class PathOpsSegmentTester; |
| }; |
| |
| #endif |