/*
|
* 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 "SkArenaAlloc.h"
|
#include "SkOpAngle.h"
|
#include "SkOpSpan.h"
|
#include "SkPathOpsBounds.h"
|
#include "SkPathOpsCubic.h"
|
#include "SkPathOpsCurve.h"
|
|
struct SkDCurve;
|
class SkOpCoincidence;
|
class SkOpContour;
|
enum class SkOpRayDir;
|
struct SkOpRayHit;
|
class SkPathWriter;
|
|
class SkOpSegment {
|
public:
|
bool operator<(const SkOpSegment& rh) const {
|
return fBounds.fTop < rh.fBounds.fTop;
|
}
|
|
SkOpAngle* activeAngle(SkOpSpanBase* start, SkOpSpanBase** startPtr, SkOpSpanBase** endPtr,
|
bool* done);
|
SkOpAngle* activeAngleInner(SkOpSpanBase* start, SkOpSpanBase** startPtr,
|
SkOpSpanBase** endPtr, bool* done);
|
SkOpAngle* activeAngleOther(SkOpSpanBase* start, SkOpSpanBase** startPtr,
|
SkOpSpanBase** endPtr, bool* done);
|
bool activeOp(SkOpSpanBase* start, SkOpSpanBase* end, int xorMiMask, int xorSuMask,
|
SkPathOp op);
|
bool activeOp(int xorMiMask, int xorSuMask, SkOpSpanBase* start, SkOpSpanBase* end, SkPathOp op,
|
int* sumMiWinding, int* sumSuWinding);
|
|
bool activeWinding(SkOpSpanBase* start, SkOpSpanBase* end);
|
bool activeWinding(SkOpSpanBase* start, SkOpSpanBase* end, int* sumWinding);
|
|
SkOpSegment* addConic(SkPoint pts[3], SkScalar weight, SkOpContour* parent) {
|
init(pts, weight, parent, SkPath::kConic_Verb);
|
SkDCurve curve;
|
curve.fConic.set(pts, weight);
|
curve.setConicBounds(pts, weight, 0, 1, &fBounds);
|
return this;
|
}
|
|
SkOpSegment* addCubic(SkPoint pts[4], SkOpContour* parent) {
|
init(pts, 1, parent, SkPath::kCubic_Verb);
|
SkDCurve curve;
|
curve.fCubic.set(pts);
|
curve.setCubicBounds(pts, 1, 0, 1, &fBounds);
|
return this;
|
}
|
|
bool addCurveTo(const SkOpSpanBase* start, const SkOpSpanBase* end, SkPathWriter* path) const;
|
|
SkOpAngle* addEndSpan() {
|
SkOpAngle* angle = this->globalState()->allocator()->make<SkOpAngle>();
|
angle->set(&fTail, fTail.prev());
|
fTail.setFromAngle(angle);
|
return angle;
|
}
|
|
bool addExpanded(double newT, const SkOpSpanBase* test, bool* startOver);
|
|
SkOpSegment* addLine(SkPoint pts[2], SkOpContour* parent) {
|
SkASSERT(pts[0] != pts[1]);
|
init(pts, 1, parent, SkPath::kLine_Verb);
|
fBounds.set(pts, 2);
|
return this;
|
}
|
|
SkOpPtT* addMissing(double t, SkOpSegment* opp, bool* allExist);
|
|
SkOpAngle* addStartSpan() {
|
SkOpAngle* angle = this->globalState()->allocator()->make<SkOpAngle>();
|
angle->set(&fHead, fHead.next());
|
fHead.setToAngle(angle);
|
return angle;
|
}
|
|
SkOpSegment* addQuad(SkPoint pts[3], SkOpContour* parent) {
|
init(pts, 1, parent, SkPath::kQuad_Verb);
|
SkDCurve curve;
|
curve.fQuad.set(pts);
|
curve.setQuadBounds(pts, 1, 0, 1, &fBounds);
|
return this;
|
}
|
|
SkOpPtT* addT(double t);
|
SkOpPtT* addT(double t, const SkPoint& pt);
|
|
const SkPathOpsBounds& bounds() const {
|
return fBounds;
|
}
|
|
void bumpCount() {
|
++fCount;
|
}
|
|
void calcAngles();
|
SkOpSpanBase::Collapsed collapsed(double startT, double endT) const;
|
static bool ComputeOneSum(const SkOpAngle* baseAngle, SkOpAngle* nextAngle,
|
SkOpAngle::IncludeType );
|
static bool ComputeOneSumReverse(SkOpAngle* baseAngle, SkOpAngle* nextAngle,
|
SkOpAngle::IncludeType );
|
int computeSum(SkOpSpanBase* start, SkOpSpanBase* end, SkOpAngle::IncludeType includeType);
|
|
void clearAll();
|
void clearOne(SkOpSpan* span);
|
static void ClearVisited(SkOpSpanBase* span);
|
bool contains(double t) const;
|
|
SkOpContour* contour() const {
|
return fContour;
|
}
|
|
int count() const {
|
return fCount;
|
}
|
|
void debugAddAngle(double startT, double endT);
|
#if DEBUG_COIN
|
const SkOpPtT* debugAddT(double t, SkPathOpsDebug::GlitchLog* ) const;
|
#endif
|
const SkOpAngle* debugAngle(int id) const;
|
#if DEBUG_ANGLE
|
void debugCheckAngleCoin() const;
|
#endif
|
#if DEBUG_COIN
|
void debugCheckHealth(SkPathOpsDebug::GlitchLog* ) const;
|
void debugClearAll(SkPathOpsDebug::GlitchLog* glitches) const;
|
void debugClearOne(const SkOpSpan* span, SkPathOpsDebug::GlitchLog* glitches) const;
|
#endif
|
const SkOpCoincidence* debugCoincidence() const;
|
SkOpContour* debugContour(int id) const;
|
|
int debugID() const {
|
return SkDEBUGRELEASE(fID, -1);
|
}
|
|
SkOpAngle* debugLastAngle();
|
#if DEBUG_COIN
|
void debugMissingCoincidence(SkPathOpsDebug::GlitchLog* glitches) const;
|
void debugMoveMultiples(SkPathOpsDebug::GlitchLog* glitches) const;
|
void debugMoveNearby(SkPathOpsDebug::GlitchLog* glitches) const;
|
#endif
|
const SkOpPtT* debugPtT(int id) const;
|
void debugReset();
|
const SkOpSegment* debugSegment(int id) const;
|
|
#if DEBUG_ACTIVE_SPANS
|
void debugShowActiveSpans(SkString* str) const;
|
#endif
|
#if DEBUG_MARK_DONE
|
void debugShowNewWinding(const char* fun, const SkOpSpan* span, int winding);
|
void debugShowNewWinding(const char* fun, const SkOpSpan* span, int winding, int oppWinding);
|
#endif
|
|
const SkOpSpanBase* debugSpan(int id) const;
|
void debugValidate() const;
|
|
#if DEBUG_COINCIDENCE_ORDER
|
void debugResetCoinT() const;
|
void debugSetCoinT(int, SkScalar ) const;
|
#endif
|
|
#if DEBUG_COIN
|
static void DebugClearVisited(const SkOpSpanBase* span);
|
|
bool debugVisited() const {
|
if (!fDebugVisited) {
|
fDebugVisited = true;
|
return false;
|
}
|
return true;
|
}
|
#endif
|
|
#if DEBUG_ANGLE
|
double distSq(double t, const SkOpAngle* opp) const;
|
#endif
|
|
bool done() const {
|
SkOPASSERT(fDoneCount <= fCount);
|
return fDoneCount == fCount;
|
}
|
|
bool done(const SkOpAngle* angle) const {
|
return angle->start()->starter(angle->end())->done();
|
}
|
|
SkDPoint dPtAtT(double mid) const {
|
return (*CurveDPointAtT[fVerb])(fPts, fWeight, mid);
|
}
|
|
SkDVector dSlopeAtT(double mid) const {
|
return (*CurveDSlopeAtT[fVerb])(fPts, fWeight, mid);
|
}
|
|
void dump() const;
|
void dumpAll() const;
|
void dumpAngles() const;
|
void dumpCoin() const;
|
void dumpPts(const char* prefix = "seg") const;
|
void dumpPtsInner(const char* prefix = "seg") const;
|
|
const SkOpPtT* existing(double t, const SkOpSegment* opp) const;
|
SkOpSegment* findNextOp(SkTDArray<SkOpSpanBase*>* chase, SkOpSpanBase** nextStart,
|
SkOpSpanBase** nextEnd, bool* unsortable, bool* simple,
|
SkPathOp op, int xorMiMask, int xorSuMask);
|
SkOpSegment* findNextWinding(SkTDArray<SkOpSpanBase*>* chase, SkOpSpanBase** nextStart,
|
SkOpSpanBase** nextEnd, bool* unsortable);
|
SkOpSegment* findNextXor(SkOpSpanBase** nextStart, SkOpSpanBase** nextEnd, bool* unsortable);
|
SkOpSpan* findSortableTop(SkOpContour* );
|
SkOpGlobalState* globalState() const;
|
|
const SkOpSpan* head() const {
|
return &fHead;
|
}
|
|
SkOpSpan* head() {
|
return &fHead;
|
}
|
|
void init(SkPoint pts[], SkScalar weight, SkOpContour* parent, SkPath::Verb verb);
|
|
SkOpSpan* insert(SkOpSpan* prev) {
|
SkOpGlobalState* globalState = this->globalState();
|
globalState->setAllocatedOpSpan();
|
SkOpSpan* result = globalState->allocator()->make<SkOpSpan>();
|
SkOpSpanBase* next = prev->next();
|
result->setPrev(prev);
|
prev->setNext(result);
|
SkDEBUGCODE(result->ptT()->fT = 0);
|
result->setNext(next);
|
if (next) {
|
next->setPrev(result);
|
}
|
return result;
|
}
|
|
bool isClose(double t, const SkOpSegment* opp) const;
|
|
bool isHorizontal() const {
|
return fBounds.fTop == fBounds.fBottom;
|
}
|
|
SkOpSegment* isSimple(SkOpSpanBase** end, int* step) const {
|
return nextChase(end, step, nullptr, nullptr);
|
}
|
|
bool isVertical() const {
|
return fBounds.fLeft == fBounds.fRight;
|
}
|
|
bool isVertical(SkOpSpanBase* start, SkOpSpanBase* end) const {
|
return (*CurveIsVertical[fVerb])(fPts, fWeight, start->t(), end->t());
|
}
|
|
bool isXor() const;
|
|
void joinEnds(SkOpSegment* start) {
|
fTail.ptT()->addOpp(start->fHead.ptT(), start->fHead.ptT());
|
}
|
|
const SkPoint& lastPt() const {
|
return fPts[SkPathOpsVerbToPoints(fVerb)];
|
}
|
|
void markAllDone();
|
bool markAndChaseDone(SkOpSpanBase* start, SkOpSpanBase* end, SkOpSpanBase** found);
|
bool markAndChaseWinding(SkOpSpanBase* start, SkOpSpanBase* end, int winding,
|
SkOpSpanBase** lastPtr);
|
bool markAndChaseWinding(SkOpSpanBase* start, SkOpSpanBase* end, int winding,
|
int oppWinding, SkOpSpanBase** lastPtr);
|
bool markAngle(int maxWinding, int sumWinding, const SkOpAngle* angle, SkOpSpanBase** result);
|
bool markAngle(int maxWinding, int sumWinding, int oppMaxWinding, int oppSumWinding,
|
const SkOpAngle* angle, SkOpSpanBase** result);
|
void markDone(SkOpSpan* );
|
bool markWinding(SkOpSpan* , int winding);
|
bool markWinding(SkOpSpan* , int winding, int oppWinding);
|
bool match(const SkOpPtT* span, const SkOpSegment* parent, double t, const SkPoint& pt) const;
|
bool missingCoincidence();
|
bool moveMultiples();
|
bool moveNearby();
|
|
SkOpSegment* next() const {
|
return fNext;
|
}
|
|
SkOpSegment* nextChase(SkOpSpanBase** , int* step, SkOpSpan** , SkOpSpanBase** last) const;
|
bool operand() const;
|
|
static int OppSign(const SkOpSpanBase* start, const SkOpSpanBase* end) {
|
int result = start->t() < end->t() ? -start->upCast()->oppValue()
|
: end->upCast()->oppValue();
|
return result;
|
}
|
|
bool oppXor() const;
|
|
const SkOpSegment* prev() const {
|
return fPrev;
|
}
|
|
SkPoint ptAtT(double mid) const {
|
return (*CurvePointAtT[fVerb])(fPts, fWeight, mid);
|
}
|
|
const SkPoint* pts() const {
|
return fPts;
|
}
|
|
bool ptsDisjoint(const SkOpPtT& span, const SkOpPtT& test) const {
|
SkASSERT(this == span.segment());
|
SkASSERT(this == test.segment());
|
return ptsDisjoint(span.fT, span.fPt, test.fT, test.fPt);
|
}
|
|
bool ptsDisjoint(const SkOpPtT& span, double t, const SkPoint& pt) const {
|
SkASSERT(this == span.segment());
|
return ptsDisjoint(span.fT, span.fPt, t, pt);
|
}
|
|
bool ptsDisjoint(double t1, const SkPoint& pt1, double t2, const SkPoint& pt2) const;
|
|
void rayCheck(const SkOpRayHit& base, SkOpRayDir dir, SkOpRayHit** hits, SkArenaAlloc*);
|
void release(const SkOpSpan* );
|
|
#if DEBUG_COIN
|
void resetDebugVisited() const {
|
fDebugVisited = false;
|
}
|
#endif
|
|
void resetVisited() {
|
fVisited = false;
|
}
|
|
void setContour(SkOpContour* contour) {
|
fContour = contour;
|
}
|
|
void setNext(SkOpSegment* next) {
|
fNext = next;
|
}
|
|
void setPrev(SkOpSegment* prev) {
|
fPrev = prev;
|
}
|
|
void setUpWinding(SkOpSpanBase* start, SkOpSpanBase* end, int* maxWinding, int* sumWinding) {
|
int deltaSum = SpanSign(start, end);
|
*maxWinding = *sumWinding;
|
if (*sumWinding == SK_MinS32) {
|
return;
|
}
|
*sumWinding -= deltaSum;
|
}
|
|
void setUpWindings(SkOpSpanBase* start, SkOpSpanBase* end, int* sumMiWinding,
|
int* maxWinding, int* sumWinding);
|
void setUpWindings(SkOpSpanBase* start, SkOpSpanBase* end, int* sumMiWinding, int* sumSuWinding,
|
int* maxWinding, int* sumWinding, int* oppMaxWinding, int* oppSumWinding);
|
bool sortAngles();
|
bool spansNearby(const SkOpSpanBase* ref, const SkOpSpanBase* check, bool* found) const;
|
|
static int SpanSign(const SkOpSpanBase* start, const SkOpSpanBase* end) {
|
int result = start->t() < end->t() ? -start->upCast()->windValue()
|
: end->upCast()->windValue();
|
return result;
|
}
|
|
SkOpAngle* spanToAngle(SkOpSpanBase* start, SkOpSpanBase* end) {
|
SkASSERT(start != end);
|
return start->t() < end->t() ? start->upCast()->toAngle() : start->fromAngle();
|
}
|
|
bool subDivide(const SkOpSpanBase* start, const SkOpSpanBase* end, SkDCurve* result) const;
|
|
const SkOpSpanBase* tail() const {
|
return &fTail;
|
}
|
|
SkOpSpanBase* tail() {
|
return &fTail;
|
}
|
|
bool testForCoincidence(const SkOpPtT* priorPtT, const SkOpPtT* ptT, const SkOpSpanBase* prior,
|
const SkOpSpanBase* spanBase, const SkOpSegment* opp) const;
|
|
SkOpSpan* undoneSpan();
|
int updateOppWinding(const SkOpSpanBase* start, const SkOpSpanBase* end) const;
|
int updateOppWinding(const SkOpAngle* angle) const;
|
int updateOppWindingReverse(const SkOpAngle* angle) const;
|
int updateWinding(SkOpSpanBase* start, SkOpSpanBase* end);
|
int updateWinding(SkOpAngle* angle);
|
int updateWindingReverse(const SkOpAngle* angle);
|
|
static bool UseInnerWinding(int outerWinding, int innerWinding);
|
|
SkPath::Verb verb() const {
|
return fVerb;
|
}
|
|
// look for two different spans that point to the same opposite segment
|
bool visited() {
|
if (!fVisited) {
|
fVisited = true;
|
return false;
|
}
|
return true;
|
}
|
|
SkScalar weight() const {
|
return fWeight;
|
}
|
|
SkOpSpan* windingSpanAtT(double tHit);
|
int windSum(const SkOpAngle* angle) const;
|
|
private:
|
SkOpSpan fHead; // the head span always has its t set to zero
|
SkOpSpanBase fTail; // the tail span always has its t set to one
|
SkOpContour* fContour;
|
SkOpSegment* fNext; // forward-only linked list used by contour to walk the segments
|
const SkOpSegment* fPrev;
|
SkPoint* fPts; // pointer into array of points owned by edge builder that may be tweaked
|
SkPathOpsBounds fBounds; // tight bounds
|
SkScalar fWeight;
|
int fCount; // number of spans (one for a non-intersecting segment)
|
int fDoneCount; // number of processed spans (zero initially)
|
SkPath::Verb fVerb;
|
bool fVisited; // used by missing coincidence check
|
#if DEBUG_COIN
|
mutable bool fDebugVisited; // used by debug missing coincidence check
|
#endif
|
#if DEBUG_COINCIDENCE_ORDER
|
mutable int fDebugBaseIndex;
|
mutable SkScalar fDebugBaseMin; // if > 0, the 1st t value in this seg vis-a-vis the ref seg
|
mutable SkScalar fDebugBaseMax;
|
mutable int fDebugLastIndex;
|
mutable SkScalar fDebugLastMin; // if > 0, the last t -- next t val - base has same sign
|
mutable SkScalar fDebugLastMax;
|
#endif
|
SkDEBUGCODE(int fID);
|
};
|
|
#endif
|
