blob: 79d83b1155fbd8728d3d0e986f78c270e97b74a8 [file] [log] [blame]
/*
* 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() {
#ifdef SK_DEBUG
fID = ++SkPathOpsDebug::gSegmentID;
#endif
}
bool operator<(const SkOpSegment& rh) const {
return fBounds.fTop < rh.fBounds.fTop;
}
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()));
}
// used only by partial coincidence detection
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 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;
}
const SkOpSegment* other(int index) const {
return fTs[index].fOther;
}
// was used only by right angle winding finding
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;
}
// OPTIMIZATION: mark as debugging only if used solely by tests
const SkOpSpan& span(int tIndex) const {
return fTs[tIndex];
}
// OPTIMIZATION: mark as debugging only if used solely by tests
const SkTDArray<SkOpSpan>& spans() const {
return fTs;
}
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;
}
bool unsortable(int index) const {
return fTs[index].fUnsortableStart || fTs[index].fUnsortableEnd;
}
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
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
bool activeAngle(int index, int* done, SkTArray<SkOpAngle, true>* angles);
SkPoint activeLeftTop(bool onlySortable, 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 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);
int addSelfT(SkOpSegment* other, const SkPoint& pt, double newT);
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);
void addTPair(double t, SkOpSegment* other, double otherT, bool borrowWind, const SkPoint& pt);
bool betweenTs(int lesser, double testT, int greater) const;
void checkEnds();
bool checkSmall(int index) const;
void checkTiny();
int computeSum(int startIndex, int endIndex, SkOpAngle::IncludeType includeType,
SkTArray<SkOpAngle, true>* angles, SkTArray<SkOpAngle*, true>* sorted);
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, const int xorMiMask,
const int xorSuMask);
SkOpSegment* findNextWinding(SkTDArray<SkOpSpan*>* chase, int* nextStart, int* nextEnd,
bool* unsortable);
SkOpSegment* findNextXor(int* nextStart, int* nextEnd, bool* unsortable);
int findT(double t, const SkOpSegment* ) const;
SkOpSegment* findTop(int* tIndex, int* endIndex, bool* unsortable, bool onlySortable);
void fixOtherTIndex();
void initWinding(int start, int end);
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, 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);
enum SortAngleKind {
kMustBeOrdered_SortAngleKind, // required for winding calc
kMayBeUnordered_SortAngleKind // ok for find top
};
static bool SortAngles(const SkTArray<SkOpAngle, true>& angles, // FIXME: replace with
SkTArray<SkOpAngle*, true>* angleList, // Sort Angles 2
SortAngleKind );
static bool SortAngles2(const SkTArray<SkOpAngle, true>& angles,
SkTArray<SkOpAngle*, true>* angleList);
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);
int windingAtT(double tHit, int tIndex, bool crossOpp, SkScalar* dx) const;
int windSum(const SkOpAngle* angle) const;
#ifdef SK_DEBUG
int debugID() const {
return fID;
}
#endif
#if DEBUG_ACTIVE_SPANS || DEBUG_ACTIVE_SPANS_FIRST_ONLY
void debugShowActiveSpans() const;
#endif
#if DEBUG_SORT || DEBUG_SWAP_TOP
void debugShowSort(const char* fun, const SkTArray<SkOpAngle*, true>& angles, int first,
const int contourWinding, const int oppContourWinding, bool sortable) const;
void debugShowSort(const char* fun, const SkTArray<SkOpAngle*, true>& angles, int first,
bool sortable);
#endif
#if DEBUG_CONCIDENT
void debugShowTs(const char* prefix) const;
#endif
#if DEBUG_SHOW_WINDING
int debugShowWindingValues(int slotCount, int ofInterest) const;
#endif
private:
struct MissingSpan {
double fT;
double fEndT;
SkOpSegment* fSegment;
SkOpSegment* fOther;
double fOtherT;
SkPoint fPt;
};
bool activeAngleOther(int index, int* done, SkTArray<SkOpAngle, true>* angles);
bool activeAngleInner(int index, int* done, SkTArray<SkOpAngle, true>* angles);
bool activeOp(int xorMiMask, int xorSuMask, int index, int endIndex, SkPathOp op,
int* sumMiWinding, int* sumSuWinding, int* maxWinding, int* sumWinding,
int* oppMaxWinding, int* oppSumWinding);
bool activeWinding(int index, int endIndex, int* maxWinding, int* sumWinding);
void addAngle(SkTArray<SkOpAngle, true>* angles, int start, int end) const;
void addCancelOutsides(const SkPoint& startPt, const SkPoint& endPt, SkOpSegment* other);
void addCoinOutsides(const SkPoint& startPt, const SkPoint& endPt, SkOpSegment* other);
void addTPair(double t, SkOpSegment* other, double otherT, bool borrowWind, const SkPoint& pt,
const SkPoint& oPt);
void addTwoAngles(int start, int end, SkTArray<SkOpAngle, true>* angles) const;
bool betweenPoints(double midT, const SkPoint& pt1, const SkPoint& pt2) const;
bool buildAngles(int index, SkTArray<SkOpAngle, true>* angles, bool includeOpp) const;
void buildAnglesInner(int index, SkTArray<SkOpAngle, true>* angles) 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 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 findStartingEdge(const SkTArray<SkOpAngle*, true>& sorted, int start, int end);
void init(const SkPoint pts[], SkPath::Verb verb, bool operand, bool evenOdd);
bool isSimple(int end) const;
bool isTiny(int index) 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, const 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);
void markUnsortable(int start, int end);
bool monotonicInY(int tStart, int tEnd) const;
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 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;
static bool UseInnerWindingReverse(int outerWinding, int innerWinding);
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
#if DEBUG_CONCIDENT
void debugAddTPair(double t, const SkOpSegment& other, double otherT) 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
void debugValidate() const;
#ifdef SK_DEBUG
void dumpPts() const;
void dumpDPts() const;
void dumpSpans() const;
#endif
const SkPoint* fPts;
SkPathOpsBounds fBounds;
// FIXME: can't convert to SkTArray because it uses insert
SkTDArray<SkOpSpan> fTs; // two or more (always includes t=0 t=1)
// 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 fOperand;
bool fXor; // set if original contour had even-odd fill
bool fOppXor; // set if opposite operand had even-odd fill
#ifdef SK_DEBUG
int fID;
#endif
};
#endif