/*
* Copyright 2014 Google Inc.
*
* Use of this source code is governed by a BSD-style license that can be
* found in the LICENSE file.
*/
#include "SkChunkAlloc.h"
#include "SkPathOpsBounds.h"
#include "SkPathOpsRect.h"
#include "SkIntersections.h"
#include "SkTSort.h"
/* TCurve and OppCurve are one of { SkDQuadratic, SkDConic, SkDCubic } */
template<typename TCurve, typename OppCurve>
class SkTCoincident {
public:
SkTCoincident() {
this->init();
}
void dump() const;
bool isCoincident() const {
return fCoincident;
}
void init() {
fPerpT = -1;
fCoincident = false;
fPerpPt.fX = fPerpPt.fY = SK_ScalarNaN;
}
void markCoincident() {
if (!fCoincident) {
fPerpT = -1;
}
fCoincident = true;
}
const SkDPoint& perpPt() const {
return fPerpPt;
}
double perpT() const {
return fPerpT;
}
void setPerp(const TCurve& c1, double t, const SkDPoint& cPt, const OppCurve& );
private:
SkDPoint fPerpPt;
double fPerpT; // perpendicular intersection on opposite curve
bool fCoincident;
};
template<typename TCurve, typename OppCurve> class SkTSect;
template<typename TCurve, typename OppCurve> class SkTSpan;
template<typename TCurve, typename OppCurve>
struct SkTSpanBounded {
SkTSpan<TCurve, OppCurve>* fBounded;
SkTSpanBounded* fNext;
};
/* Curve is either TCurve or SkDCubic */
template<typename TCurve, typename OppCurve>
class SkTSpan {
public:
void addBounded(SkTSpan<OppCurve, TCurve>* , SkChunkAlloc* );
double closestBoundedT(const SkDPoint& pt) const;
bool contains(double t) const;
void debugInit() {
TCurve dummy;
dummy.debugInit();
init(dummy);
initBounds(dummy);
fCoinStart.init();
fCoinEnd.init();
}
const SkTSect<OppCurve, TCurve>* debugOpp() const;
const SkTSpan* debugSpan(int ) const;
const SkTSpan* debugT(double t) const;
#ifdef SK_DEBUG
bool debugIsBefore(const SkTSpan* span) const;
#endif
void dump() const;
void dumpBounded(int id) const;
void dumpBounds() const;
void dumpCoin() const;
double endT() const {
return fEndT;
}
SkTSpan<OppCurve, TCurve>* findOppSpan(const SkTSpan<OppCurve, TCurve>* opp) const;
SkTSpan<OppCurve, TCurve>* findOppT(double t) const {
SkTSpan<OppCurve, TCurve>* result = oppT(t);
SkASSERT(result);
return result;
}
bool hasOppT(double t) const {
return SkToBool(oppT(t));
}
int hullsIntersect(SkTSpan<OppCurve, TCurve>* span, bool* start, bool* oppStart);
void init(const TCurve& );
void initBounds(const TCurve& );
bool isBounded() const {
return fBounded != NULL;
}
bool linearsIntersect(SkTSpan<OppCurve, TCurve>* span);
double linearT(const SkDPoint& ) const;
void markCoincident() {
fCoinStart.markCoincident();
fCoinEnd.markCoincident();
}
const SkTSpan* next() const {
return fNext;
}
bool onlyEndPointsInCommon(const SkTSpan<OppCurve, TCurve>* opp, bool* start,
bool* oppStart, bool* ptsInCommon);
const TCurve& part() const {
return fPart;
}
bool removeAllBounded();
bool removeBounded(const SkTSpan<OppCurve, TCurve>* opp);
void reset() {
fBounded = NULL;
}
void resetBounds(const TCurve& curve) {
fIsLinear = fIsLine = false;
initBounds(curve);
}
bool split(SkTSpan* work, SkChunkAlloc* heap) {
return splitAt(work, (work->fStartT + work->fEndT) * 0.5, heap);
}
bool splitAt(SkTSpan* work, double t, SkChunkAlloc* 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<OppCurve, TCurve>* opp, bool* start, bool* oppStart);
int linearIntersects(const OppCurve& ) const;
SkTSpan<OppCurve, TCurve>* oppT(double t) const;
void validate() const;
void validateBounded() const;
void validatePerpT(double oppT) const;
void validatePerpPt(double t, const SkDPoint& ) const;
TCurve fPart;
SkTCoincident<TCurve, OppCurve> fCoinStart;
SkTCoincident<TCurve, OppCurve> fCoinEnd;
SkTSpanBounded<OppCurve, TCurve>* fBounded;
SkTSpan* fPrev;
SkTSpan* fNext;
SkDRect fBounds;
double fStartT;
double fEndT;
double fBoundsMax;
bool fCollapsed;
bool fHasPerp;
bool fIsLinear;
bool fIsLine;
bool fDeleted;
SkDEBUGCODE_(SkTSect<TCurve, OppCurve>* fDebugSect);
PATH_OPS_DEBUG_T_SECT_CODE(int fID);
friend class SkTSect<TCurve, OppCurve>;
friend class SkTSect<OppCurve, TCurve>;
friend class SkTSpan<OppCurve, TCurve>;
};
template<typename TCurve, typename OppCurve>
class SkTSect {
public:
SkTSect(const TCurve& c PATH_OPS_DEBUG_T_SECT_PARAMS(int id));
static void BinarySearch(SkTSect* sect1, SkTSect<OppCurve, TCurve>* sect2,
SkIntersections* intersections);
// for testing only
bool debugHasBounded(const SkTSpan<OppCurve, TCurve>* ) const;
const SkTSect<OppCurve, TCurve>* debugOpp() const {
return SkDEBUGRELEASE(fOppSect, NULL);
}
const SkTSpan<TCurve, OppCurve>* debugSpan(int id) const;
const SkTSpan<TCurve, OppCurve>* debugT(double t) const;
void dump() const;
void dumpBoth(SkTSect<OppCurve, TCurve>* ) 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<TCurve, OppCurve>* addFollowing(SkTSpan<TCurve, OppCurve>* prior);
void addForPerp(SkTSpan<OppCurve, TCurve>* span, double t);
SkTSpan<TCurve, OppCurve>* addOne();
SkTSpan<TCurve, OppCurve>* addSplitAt(SkTSpan<TCurve, OppCurve>* span, double t) {
SkTSpan<TCurve, OppCurve>* result = this->addOne();
result->splitAt(span, t, &fHeap);
result->initBounds(fCurve);
span->initBounds(fCurve);
return result;
}
bool binarySearchCoin(SkTSect<OppCurve, TCurve>* , double tStart, double tStep, double* t,
double* oppT);
SkTSpan<TCurve, OppCurve>* boundsMax() const;
void coincidentCheck(SkTSect<OppCurve, TCurve>* sect2);
bool coincidentHasT(double t);
int collapsed() const;
void computePerpendiculars(SkTSect<OppCurve, TCurve>* sect2, SkTSpan<TCurve, OppCurve>* first,
SkTSpan<TCurve, OppCurve>* last);
int countConsecutiveSpans(SkTSpan<TCurve, OppCurve>* first,
SkTSpan<TCurve, OppCurve>** last) const;
int debugID() const {
return PATH_OPS_DEBUG_T_SECT_RELEASE(fID, -1);
}
void deleteEmptySpans();
void dumpCommon(const SkTSpan<TCurve, OppCurve>* ) const;
void dumpCommonCurves(const SkTSpan<TCurve, OppCurve>* ) const;
static int EndsEqual(const SkTSect* sect1, const SkTSect<OppCurve, TCurve>* sect2,
SkIntersections* );
SkTSpan<TCurve, OppCurve>* extractCoincident(SkTSect<OppCurve, TCurve>* sect2,
SkTSpan<TCurve, OppCurve>* first,
SkTSpan<TCurve, OppCurve>* last);
SkTSpan<TCurve, OppCurve>* findCoincidentRun(SkTSpan<TCurve, OppCurve>* first,
SkTSpan<TCurve, OppCurve>** lastPtr);
int intersects(SkTSpan<TCurve, OppCurve>* span, SkTSect<OppCurve, TCurve>* opp,
SkTSpan<OppCurve, TCurve>* oppSpan, int* oppResult);
int linesIntersect(SkTSpan<TCurve, OppCurve>* span, SkTSect<OppCurve, TCurve>* opp,
SkTSpan<OppCurve, TCurve>* oppSpan, SkIntersections* );
void markSpanGone(SkTSpan<TCurve, OppCurve>* span);
bool matchedDirection(double t, const SkTSect<OppCurve, TCurve>* sect2, double t2) const;
void matchedDirCheck(double t, const SkTSect<OppCurve, TCurve>* sect2, double t2,
bool* calcMatched, bool* oppMatched) const;
void mergeCoincidence(SkTSect<OppCurve, TCurve>* sect2);
SkTSpan<TCurve, OppCurve>* prev(SkTSpan<TCurve, OppCurve>* ) const;
void removeByPerpendicular(SkTSect<OppCurve, TCurve>* opp);
void recoverCollapsed();
void removeCoincident(SkTSpan<TCurve, OppCurve>* span, bool isBetween);
void removeAllBut(const SkTSpan<OppCurve, TCurve>* keep, SkTSpan<TCurve, OppCurve>* span,
SkTSect<OppCurve, TCurve>* opp);
void removeSpan(SkTSpan<TCurve, OppCurve>* span);
void removeSpanRange(SkTSpan<TCurve, OppCurve>* first, SkTSpan<TCurve, OppCurve>* last);
void removeSpans(SkTSpan<TCurve, OppCurve>* span, SkTSect<OppCurve, TCurve>* opp);
SkTSpan<TCurve, OppCurve>* spanAtT(double t, SkTSpan<TCurve, OppCurve>** priorSpan);
SkTSpan<TCurve, OppCurve>* tail();
void trim(SkTSpan<TCurve, OppCurve>* span, SkTSect<OppCurve, TCurve>* opp);
void unlinkSpan(SkTSpan<TCurve, OppCurve>* span);
bool updateBounded(SkTSpan<TCurve, OppCurve>* first, SkTSpan<TCurve, OppCurve>* last,
SkTSpan<OppCurve, TCurve>* oppFirst);
void validate() const;
void validateBounded() const;
const TCurve& fCurve;
SkChunkAlloc fHeap;
SkTSpan<TCurve, OppCurve>* fHead;
SkTSpan<TCurve, OppCurve>* fCoincident;
SkTSpan<TCurve, OppCurve>* fDeleted;
int fActiveCount;
SkDEBUGCODE_(SkTSect<OppCurve, TCurve>* 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<TCurve, OppCurve>;
friend class SkTSpan<OppCurve, TCurve>;
friend class SkTSect<OppCurve, TCurve>;
};
#define COINCIDENT_SPAN_COUNT 9
template<typename TCurve, typename OppCurve>
void SkTCoincident<TCurve, OppCurve>::setPerp(const TCurve& c1, double t,
const SkDPoint& cPt, const OppCurve& c2) {
SkDVector dxdy = c1.dxdyAtT(t);
SkDLine perp = {{ cPt, {cPt.fX + dxdy.fY, cPt.fY - dxdy.fX} }};
SkIntersections i;
int used = i.intersectRay(c2, perp);
// only keep closest
if (used == 0 || used == 3) {
this->init();
return;
}
fPerpT = i[0][0];
fPerpPt = i.pt(0);
SkASSERT(used <= 2);
if (used == 2) {
double distSq = (fPerpPt - cPt).lengthSquared();
double dist2Sq = (i.pt(1) - cPt).lengthSquared();
if (dist2Sq < distSq) {
fPerpT = i[0][1];
fPerpPt = i.pt(1);
}
}
#if DEBUG_T_SECT
SkDebugf("setPerp t=%1.9g cPt=(%1.9g,%1.9g) %s oppT=%1.9g fPerpPt=(%1.9g,%1.9g)\n",
t, cPt.fX, cPt.fY,
cPt.approximatelyEqual(fPerpPt) ? "==" : "!=", fPerpT, fPerpPt.fX, fPerpPt.fY);
#endif
fCoincident = cPt.approximatelyEqual(fPerpPt);
#if DEBUG_T_SECT
if (fCoincident) {
SkDebugf(""); // allow setting breakpoint
}
#endif
}
template<typename TCurve, typename OppCurve>
void SkTSpan<TCurve, OppCurve>::addBounded(SkTSpan<OppCurve, TCurve>* span, SkChunkAlloc* heap) {
SkTSpanBounded<OppCurve, TCurve>* bounded = SkNEW_PLACEMENT(heap->allocThrow(
sizeof(SkTSpanBounded<OppCurve, TCurve>)), (SkTSpanBounded<OppCurve, TCurve>));
bounded->fBounded = span;
bounded->fNext = fBounded;
fBounded = bounded;
}
template<typename TCurve, typename OppCurve>
SkTSpan<TCurve, OppCurve>* SkTSect<TCurve, OppCurve>::addFollowing(
SkTSpan<TCurve, OppCurve>* prior) {
SkTSpan<TCurve, OppCurve>* result = this->addOne();
result->fStartT = prior ? prior->fEndT : 0;
SkTSpan<TCurve, OppCurve>* next = prior ? prior->fNext : fHead;
result->fEndT = next ? next->fStartT : 1;
result->fPrev = prior;
result->fNext = next;
if (prior) {
prior->fNext = result;
} else {
fHead = result;
}
if (next) {
next->fPrev = result;
}
result->resetBounds(fCurve);
return result;
}
template<typename TCurve, typename OppCurve>
void SkTSect<TCurve, OppCurve>::addForPerp(SkTSpan<OppCurve, TCurve>* span, double t) {
if (!span->hasOppT(t)) {
SkTSpan<TCurve, OppCurve>* priorSpan;
SkTSpan<TCurve, OppCurve>* opp = this->spanAtT(t, &priorSpan);
if (!opp) {
opp = this->addFollowing(priorSpan);
#if DEBUG_PERP
SkDebugf("%s priorSpan=%d t=%1.9g opp=%d\n", __FUNCTION__, priorSpan->debugID(), t,
opp->debugID());
#endif
}
#if DEBUG_PERP
opp->dump(); SkDebugf("\n");
SkDebugf("%s addBounded span=%d opp=%d\n", __FUNCTION__, priorSpan->debugID(),
opp->debugID());
#endif
opp->addBounded(span, &fHeap);
span->addBounded(opp, &fHeap);
}
this->validate();
#if DEBUG_T_SECT
span->validatePerpT(t);
#endif
}
template<typename TCurve, typename OppCurve>
double SkTSpan<TCurve, OppCurve>::closestBoundedT(const SkDPoint& pt) const {
double result = -1;
double closest = FLT_MAX;
const SkTSpanBounded<OppCurve, TCurve>* testBounded = fBounded;
while (testBounded) {
const SkTSpan<OppCurve, TCurve>* test = testBounded->fBounded;
double startDist = test->fPart[0].distanceSquared(pt);
if (closest > startDist) {
closest = startDist;
result = test->fStartT;
}
double endDist = test->fPart[OppCurve::kPointLast].distanceSquared(pt);
if (closest > endDist) {
closest = endDist;
result = test->fEndT;
}
testBounded = testBounded->fNext;
}
SkASSERT(between(0, result, 1));
return result;
}
#ifdef SK_DEBUG
template<typename TCurve, typename OppCurve>
bool SkTSpan<TCurve, OppCurve>::debugIsBefore(const SkTSpan* span) const {
const SkTSpan* work = this;
do {
if (span == work) {
return true;
}
} while ((work = work->fNext));
return false;
}
#endif
template<typename TCurve, typename OppCurve>
bool SkTSpan<TCurve, OppCurve>::contains(double t) const {
const SkTSpan* work = this;
do {
if (between(work->fStartT, t, work->fEndT)) {
return true;
}
} while ((work = work->fNext));
return false;
}
template<typename TCurve, typename OppCurve>
const SkTSect<OppCurve, TCurve>* SkTSpan<TCurve, OppCurve>::debugOpp() const {
return SkDEBUGRELEASE(fDebugSect->debugOpp(), NULL);
}
template<typename TCurve, typename OppCurve>
SkTSpan<OppCurve, TCurve>* SkTSpan<TCurve, OppCurve>::findOppSpan(
const SkTSpan<OppCurve, TCurve>* opp) const {
SkTSpanBounded<OppCurve, TCurve>* bounded = fBounded;
while (bounded) {
SkTSpan<OppCurve, TCurve>* test = bounded->fBounded;
if (opp == test) {
return test;
}
bounded = bounded->fNext;
}
return NULL;
}
// returns 0 if no hull intersection
// 1 if hulls intersect
// 2 if hulls only share a common endpoint
// -1 if linear and further checking is required
template<typename TCurve, typename OppCurve>
int SkTSpan<TCurve, OppCurve>::hullCheck(const SkTSpan<OppCurve, TCurve>* opp,
bool* start, bool* oppStart) {
if (fIsLinear) {
return -1;
}
bool ptsInCommon;
if (onlyEndPointsInCommon(opp, start, oppStart, &ptsInCommon)) {
SkASSERT(ptsInCommon);
return 2;
}
bool linear;
if (fPart.hullIntersects(opp->fPart, &linear)) {
if (!linear) { // check set true if linear
return 1;
}
fIsLinear = true;
fIsLine = fPart.controlsInside();
return ptsInCommon ? 2 : -1;
} else { // hull is not linear; check set true if intersected at the end points
return ((int) ptsInCommon) << 1; // 0 or 2
}
return 0;
}
// OPTIMIZE ? If at_most_end_pts_in_common detects that one quad is near linear,
// use line intersection to guess a better split than 0.5
// OPTIMIZE Once at_most_end_pts_in_common detects linear, mark span so all future splits are linear
template<typename TCurve, typename OppCurve>
int SkTSpan<TCurve, OppCurve>::hullsIntersect(SkTSpan<OppCurve, TCurve>* opp,
bool* start, bool* oppStart) {
if (!fBounds.intersects(opp->fBounds)) {
return 0;
}
int hullSect = this->hullCheck(opp, start, oppStart);
if (hullSect >= 0) {
return hullSect;
}
hullSect = opp->hullCheck(this, oppStart, start);
if (hullSect >= 0) {
return hullSect;
}
return -1;
}
template<typename TCurve, typename OppCurve>
void SkTSpan<TCurve, OppCurve>::init(const TCurve& c) {
fPrev = fNext = NULL;
fStartT = 0;
fEndT = 1;
fBounded = NULL;
resetBounds(c);
}
template<typename TCurve, typename OppCurve>
void SkTSpan<TCurve, OppCurve>::initBounds(const TCurve& c) {
fPart = c.subDivide(fStartT, fEndT);
fBounds.setBounds(fPart);
fCoinStart.init();
fCoinEnd.init();
fBoundsMax = SkTMax(fBounds.width(), fBounds.height());
fCollapsed = fPart.collapsed();
fHasPerp = false;
fDeleted = false;
#if DEBUG_T_SECT
if (fCollapsed) {
SkDebugf(""); // for convenient breakpoints
}
#endif
}
template<typename TCurve, typename OppCurve>
bool SkTSpan<TCurve, OppCurve>::linearsIntersect(SkTSpan<OppCurve, TCurve>* span) {
int result = this->linearIntersects(span->fPart);
if (result <= 1) {
return SkToBool(result);
}
SkASSERT(span->fIsLinear);
result = span->linearIntersects(this->fPart);
// SkASSERT(result <= 1);
return SkToBool(result);
}
template<typename TCurve, typename OppCurve>
double SkTSpan<TCurve, OppCurve>::linearT(const SkDPoint& pt) const {
SkDVector len = fPart[TCurve::kPointLast] - fPart[0];
return fabs(len.fX) > fabs(len.fY)
? (pt.fX - fPart[0].fX) / len.fX
: (pt.fY - fPart[0].fY) / len.fY;
}
template<typename TCurve, typename OppCurve>
int SkTSpan<TCurve, OppCurve>::linearIntersects(const OppCurve& q2) const {
// looks like q1 is near-linear
int start = 0, end = TCurve::kPointLast; // the outside points are usually the extremes
if (!fPart.controlsInside()) {
double dist = 0; // if there's any question, compute distance to find best outsiders
for (int outer = 0; outer < TCurve::kPointCount - 1; ++outer) {
for (int inner = outer + 1; inner < TCurve::kPointCount; ++inner) {
double test = (fPart[outer] - fPart[inner]).lengthSquared();
if (dist > test) {
continue;
}
dist = test;
start = outer;
end = inner;
}
}
}
// see if q2 is on one side of the line formed by the extreme points
double origX = fPart[start].fX;
double origY = fPart[start].fY;
double adj = fPart[end].fX - origX;
double opp = fPart[end].fY - origY;
double maxPart = SkTMax(fabs(adj), fabs(opp));
double sign = 0; // initialization to shut up warning in release build
for (int n = 0; n < OppCurve::kPointCount; ++n) {
double dx = q2[n].fY - origY;
double dy = q2[n].fX - origX;
double maxVal = SkTMax(maxPart, SkTMax(fabs(dx), fabs(dy)));
double test = (q2[n].fY - origY) * adj - (q2[n].fX - origX) * opp;
if (precisely_zero_when_compared_to(test, maxVal)) {
return 1;
}
if (approximately_zero_when_compared_to(test, maxVal)) {
return 3;
}
if (n == 0) {
sign = test;
continue;
}
if (test * sign < 0) {
return 1;
}
}
return 0;
}
template<typename TCurve, typename OppCurve>
bool SkTSpan<TCurve, OppCurve>::onlyEndPointsInCommon(const SkTSpan<OppCurve, TCurve>* opp,
bool* start, bool* oppStart, bool* ptsInCommon) {
if (opp->fPart[0] == fPart[0]) {
*start = *oppStart = true;
} else if (opp->fPart[0] == fPart[TCurve::kPointLast]) {
*start = false;
*oppStart = true;
} else if (opp->fPart[OppCurve::kPointLast] == fPart[0]) {
*start = true;
*oppStart = false;
} else if (opp->fPart[OppCurve::kPointLast] == fPart[TCurve::kPointLast]) {
*start = *oppStart = false;
} else {
*ptsInCommon = false;
return false;
}
*ptsInCommon = true;
const SkDPoint* otherPts[TCurve::kPointCount - 1], * oppOtherPts[OppCurve::kPointCount - 1];
int baseIndex = *start ? 0 : TCurve::kPointLast;
fPart.otherPts(baseIndex, otherPts);
opp->fPart.otherPts(*oppStart ? 0 : OppCurve::kPointLast, oppOtherPts);
const SkDPoint& base = fPart[baseIndex];
for (int o1 = 0; o1 < (int) SK_ARRAY_COUNT(otherPts); ++o1) {
SkDVector v1 = *otherPts[o1] - base;
for (int o2 = 0; o2 < (int) SK_ARRAY_COUNT(oppOtherPts); ++o2) {
SkDVector v2 = *oppOtherPts[o2] - base;
if (v2.dot(v1) >= 0) {
return false;
}
}
}
return true;
}
template<typename TCurve, typename OppCurve>
SkTSpan<OppCurve, TCurve>* SkTSpan<TCurve, OppCurve>::oppT(double t) const {
SkTSpanBounded<OppCurve, TCurve>* bounded = fBounded;
while (bounded) {
SkTSpan<OppCurve, TCurve>* test = bounded->fBounded;
if (between(test->fStartT, t, test->fEndT)) {
return test;
}
bounded = bounded->fNext;
}
return NULL;
}
template<typename TCurve, typename OppCurve>
bool SkTSpan<TCurve, OppCurve>::removeAllBounded() {
bool deleteSpan = false;
SkTSpanBounded<OppCurve, TCurve>* bounded = fBounded;
while (bounded) {
SkTSpan<OppCurve, TCurve>* opp = bounded->fBounded;
deleteSpan |= opp->removeBounded(this);
bounded = bounded->fNext;
}
return deleteSpan;
}
template<typename TCurve, typename OppCurve>
bool SkTSpan<TCurve, OppCurve>::removeBounded(const SkTSpan<OppCurve, TCurve>* opp) {
if (fHasPerp) {
bool foundStart = false;
bool foundEnd = false;
SkTSpanBounded<OppCurve, TCurve>* bounded = fBounded;
while (bounded) {
SkTSpan<OppCurve, TCurve>* test = bounded->fBounded;
if (opp != test) {
foundStart |= between(test->fStartT, fCoinStart.perpT(), test->fEndT);
foundEnd |= between(test->fStartT, fCoinEnd.perpT(), test->fEndT);
}
bounded = bounded->fNext;
}
if (!foundStart || !foundEnd) {
fHasPerp = false;
fCoinStart.init();
fCoinEnd.init();
}
}
SkTSpanBounded<OppCurve, TCurve>* bounded = fBounded;
SkTSpanBounded<OppCurve, TCurve>* prev = NULL;
while (bounded) {
SkTSpanBounded<OppCurve, TCurve>* boundedNext = bounded->fNext;
if (opp == bounded->fBounded) {
if (prev) {
prev->fNext = boundedNext;
return false;
} else {
fBounded = boundedNext;
return fBounded == NULL;
}
}
prev = bounded;
bounded = boundedNext;
}
SkASSERT(0);
return false;
}
template<typename TCurve, typename OppCurve>
bool SkTSpan<TCurve, OppCurve>::splitAt(SkTSpan* work, double t, SkChunkAlloc* heap) {
fStartT = t;
fEndT = work->fEndT;
if (fStartT == fEndT) {
fCollapsed = true;
return false;
}
work->fEndT = t;
if (work->fStartT == work->fEndT) {
work->fCollapsed = true;
return false;
}
fPrev = work;
fNext = work->fNext;
fIsLinear = work->fIsLinear;
fIsLine = work->fIsLine;
work->fNext = this;
if (fNext) {
fNext->fPrev = this;
}
SkTSpanBounded<OppCurve, TCurve>* bounded = work->fBounded;
fBounded = NULL;
while (bounded) {
this->addBounded(bounded->fBounded, heap);
bounded = bounded->fNext;
}
bounded = fBounded;
while (bounded) {
bounded->fBounded->addBounded(this, heap);
bounded = bounded->fNext;
}
return true;
}
template<typename TCurve, typename OppCurve>
void SkTSpan<TCurve, OppCurve>::validate() const {
#if DEBUG_T_SECT
SkASSERT(fNext == NULL || fNext != fPrev);
SkASSERT(fNext == NULL || this == fNext->fPrev);
SkASSERT(fPrev == NULL || this == fPrev->fNext);
SkASSERT(fBounds.width() || fBounds.height() || fCollapsed);
SkASSERT(fBoundsMax == SkTMax(fBounds.width(), fBounds.height()));
SkASSERT(0 <= fStartT);
SkASSERT(fEndT <= 1);
SkASSERT(fStartT <= fEndT);
SkASSERT(fBounded);
this->validateBounded();
if (fHasPerp) {
if (fCoinStart.isCoincident()) {
validatePerpT(fCoinStart.perpT());
validatePerpPt(fCoinStart.perpT(), fCoinStart.perpPt());
}
if (fCoinEnd.isCoincident()) {
validatePerpT(fCoinEnd.perpT());
validatePerpPt(fCoinEnd.perpT(), fCoinEnd.perpPt());
}
}
#endif
}
template<typename TCurve, typename OppCurve>
void SkTSpan<TCurve, OppCurve>::validateBounded() const {
#if DEBUG_VALIDATE
const SkTSpanBounded<OppCurve, TCurve>* testBounded = fBounded;
while (testBounded) {
SkDEBUGCODE_(const SkTSpan<OppCurve, TCurve>* overlap = testBounded->fBounded);
SkASSERT(!overlap->fDeleted);
SkASSERT(((this->debugID() ^ overlap->debugID()) & 1) == 1);
SkASSERT(overlap->findOppSpan(this));
testBounded = testBounded->fNext;
}
#endif
}
template<typename TCurve, typename OppCurve>
void SkTSpan<TCurve, OppCurve>::validatePerpT(double oppT) const {
const SkTSpanBounded<OppCurve, TCurve>* testBounded = fBounded;
while (testBounded) {
const SkTSpan<OppCurve, TCurve>* overlap = testBounded->fBounded;
if (between(overlap->fStartT, oppT, overlap->fEndT)) {
return;
}
testBounded = testBounded->fNext;
}
SkASSERT(0);
}
template<typename TCurve, typename OppCurve>
void SkTSpan<TCurve, OppCurve>::validatePerpPt(double t, const SkDPoint& pt) const {
SkASSERT(fDebugSect->fOppSect->fCurve.ptAtT(t) == pt);
}
template<typename TCurve, typename OppCurve>
SkTSect<TCurve, OppCurve>::SkTSect(const TCurve& c PATH_OPS_DEBUG_T_SECT_PARAMS(int id))
: fCurve(c)
, fHeap(sizeof(SkTSpan<TCurve, OppCurve>) * 4)
, fCoincident(NULL)
, fDeleted(NULL)
, fActiveCount(0)
PATH_OPS_DEBUG_T_SECT_PARAMS(fID(id))
PATH_OPS_DEBUG_T_SECT_PARAMS(fDebugCount(0))
PATH_OPS_DEBUG_T_SECT_PARAMS(fDebugAllocatedCount(0))
{
fHead = addOne();
fHead->init(c);
}
template<typename TCurve, typename OppCurve>
SkTSpan<TCurve, OppCurve>* SkTSect<TCurve, OppCurve>::addOne() {
SkTSpan<TCurve, OppCurve>* result;
if (fDeleted) {
result = fDeleted;
result->reset();
fDeleted = result->fNext;
} else {
result = SkNEW_PLACEMENT(fHeap.allocThrow(sizeof(SkTSpan<TCurve, OppCurve>)),
(SkTSpan<TCurve, OppCurve>));
result->fBounded = NULL;
#if DEBUG_T_SECT
++fDebugAllocatedCount;
#endif
}
result->fHasPerp = false;
result->fDeleted = false;
++fActiveCount;
PATH_OPS_DEBUG_T_SECT_CODE(result->fID = fDebugCount++ * 2 + fID);
SkDEBUGCODE(result->fDebugSect = this);
return result;
}
template<typename TCurve, typename OppCurve>
bool SkTSect<TCurve, OppCurve>::binarySearchCoin(SkTSect<OppCurve, TCurve>* sect2, double tStart,
double tStep, double* resultT, double* oppT) {
SkTSpan<TCurve, OppCurve> work;
double result = work.fStartT = work.fEndT = tStart;
SkDEBUGCODE(work.fDebugSect = this);
SkDPoint last = fCurve.ptAtT(tStart);
SkDPoint oppPt;
bool flip = false;
SkDEBUGCODE(bool down = tStep < 0);
const OppCurve& opp = sect2->fCurve;
do {
tStep *= 0.5;
work.fStartT += tStep;
if (flip) {
tStep = -tStep;
flip = false;
}
work.initBounds(fCurve);
if (work.fCollapsed) {
return false;
}
if (last.approximatelyEqual(work.fPart[0])) {
break;
}
last = work.fPart[0];
work.fCoinStart.setPerp(fCurve, work.fStartT, last, opp);
if (work.fCoinStart.isCoincident()) {
#if DEBUG_T_SECT
work.validatePerpPt(work.fCoinStart.perpT(), work.fCoinStart.perpPt());
#endif
double oppTTest = work.fCoinStart.perpT();
if (sect2->fHead->contains(oppTTest)) {
*oppT = oppTTest;
oppPt = work.fCoinStart.perpPt();
SkASSERT(down ? result > work.fStartT : result < work.fStartT);
result = work.fStartT;
continue;
}
}
tStep = -tStep;
flip = true;
} while (true);
if (last.approximatelyEqual(fCurve[0])) {
result = 0;
} else if (last.approximatelyEqual(fCurve[TCurve::kPointLast])) {
result = 1;
}
if (oppPt.approximatelyEqual(opp[0])) {
*oppT = 0;
} else if (oppPt.approximatelyEqual(opp[OppCurve::kPointLast])) {
*oppT = 1;
}
*resultT = result;
return true;
}
// OPTIMIZE ? keep a sorted list of sizes in the form of a doubly-linked list in quad span
// so that each quad sect has a pointer to the largest, and can update it as spans
// are split
template<typename TCurve, typename OppCurve>
SkTSpan<TCurve, OppCurve>* SkTSect<TCurve, OppCurve>::boundsMax() const {
SkTSpan<TCurve, OppCurve>* test = fHead;
SkTSpan<TCurve, OppCurve>* largest = fHead;
bool lCollapsed = largest->fCollapsed;
while ((test = test->fNext)) {
bool tCollapsed = test->fCollapsed;
if ((lCollapsed && !tCollapsed) || (lCollapsed == tCollapsed &&
largest->fBoundsMax < test->fBoundsMax)) {
largest = test;
lCollapsed = test->fCollapsed;
}
}
return largest;
}
template<typename TCurve, typename OppCurve>
void SkTSect<TCurve, OppCurve>::coincidentCheck(SkTSect<OppCurve, TCurve>* sect2) {
SkTSpan<TCurve, OppCurve>* first = fHead;
SkTSpan<TCurve, OppCurve>* last, * next;
do {
int consecutive = this->countConsecutiveSpans(first, &last);
next = last->fNext;
if (consecutive < COINCIDENT_SPAN_COUNT) {
continue;
}
this->validate();
sect2->validate();
this->computePerpendiculars(sect2, first, last);
this->validate();
sect2->validate();
// check to see if a range of points are on the curve
SkTSpan<TCurve, OppCurve>* coinStart = first;
do {
coinStart = this->extractCoincident(sect2, coinStart, last);
} while (coinStart && !last->fDeleted);
} while ((first = next));
}
template<typename TCurve, typename OppCurve>
bool SkTSect<TCurve, OppCurve>::coincidentHasT(double t) {
SkTSpan<TCurve, OppCurve>* test = fCoincident;
while (test) {
if (between(test->fStartT, t, test->fEndT)) {
return true;
}
test = test->fNext;
}
return false;
}
template<typename TCurve, typename OppCurve>
int SkTSect<TCurve, OppCurve>::collapsed() const {
int result = 0;
const SkTSpan<TCurve, OppCurve>* test = fHead;
while (test) {
if (test->fCollapsed) {
++result;
}
test = test->next();
}
return result;
}
template<typename TCurve, typename OppCurve>
void SkTSect<TCurve, OppCurve>::computePerpendiculars(SkTSect<OppCurve, TCurve>* sect2,
SkTSpan<TCurve, OppCurve>* first, SkTSpan<TCurve, OppCurve>* last) {
const OppCurve& opp = sect2->fCurve;
SkTSpan<TCurve, OppCurve>* work = first;
SkTSpan<TCurve, OppCurve>* prior = NULL;
do {
if (!work->fHasPerp && !work->fCollapsed) {
if (prior) {
work->fCoinStart = prior->fCoinEnd;
} else {
work->fCoinStart.setPerp(fCurve, work->fStartT, work->fPart[0], opp);
}
if (work->fCoinStart.isCoincident()) {
double perpT = work->fCoinStart.perpT();
if (sect2->coincidentHasT(perpT)) {
work->fCoinStart.init();
} else {
sect2->addForPerp(work, perpT);
}
}
work->fCoinEnd.setPerp(fCurve, work->fEndT, work->fPart[TCurve::kPointLast], opp);
if (work->fCoinEnd.isCoincident()) {
double perpT = work->fCoinEnd.perpT();
if (sect2->coincidentHasT(perpT)) {
work->fCoinEnd.init();
} else {
sect2->addForPerp(work, perpT);
}
}
work->fHasPerp = true;
}
if (work == last) {
break;
}
prior = work;
work = work->fNext;
SkASSERT(work);
} while (true);
}
template<typename TCurve, typename OppCurve>
int SkTSect<TCurve, OppCurve>::countConsecutiveSpans(SkTSpan<TCurve, OppCurve>* first,
SkTSpan<TCurve, OppCurve>** lastPtr) const {
int consecutive = 1;
SkTSpan<TCurve, OppCurve>* last = first;
do {
SkTSpan<TCurve, OppCurve>* next = last->fNext;
if (!next) {
break;
}
if (next->fStartT > last->fEndT) {
break;
}
++consecutive;
last = next;
} while (true);
*lastPtr = last;
return consecutive;
}
template<typename TCurve, typename OppCurve>
bool SkTSect<TCurve, OppCurve>::debugHasBounded(const SkTSpan<OppCurve, TCurve>* span) const {
const SkTSpan<TCurve, OppCurve>* test = fHead;
if (!test) {
return false;
}
do {
if (test->findOppSpan(span)) {
return true;
}
} while ((test = test->next()));
return false;
}
template<typename TCurve, typename OppCurve>
void SkTSect<TCurve, OppCurve>::deleteEmptySpans() {
SkTSpan<TCurve, OppCurve>* test;
SkTSpan<TCurve, OppCurve>* next = fHead;
while ((test = next)) {
next = test->fNext;
if (!test->fBounded) {
this->removeSpan(test);
}
}
}
template<typename TCurve, typename OppCurve>
SkTSpan<TCurve, OppCurve>* SkTSect<TCurve, OppCurve>::extractCoincident(
SkTSect<OppCurve, TCurve>* sect2,
SkTSpan<TCurve, OppCurve>* first, SkTSpan<TCurve, OppCurve>* last) {
first = findCoincidentRun(first, &last);
if (!first) {
return NULL;
}
// march outwards to find limit of coincidence from here to previous and next spans
double startT = first->fStartT;
double oppStartT SK_INIT_TO_AVOID_WARNING;
double oppEndT SK_INIT_TO_AVOID_WARNING;
SkTSpan<TCurve, OppCurve>* prev = first->fPrev;
SkASSERT(first->fCoinStart.isCoincident());
SkTSpan<OppCurve, TCurve>* oppFirst = first->findOppT(first->fCoinStart.perpT());
SkASSERT(last->fCoinEnd.isCoincident());
bool oppMatched = first->fCoinStart.perpT() < first->fCoinEnd.perpT();
double coinStart;
SkDEBUGCODE(double coinEnd);
SkTSpan<OppCurve, TCurve>* cutFirst;
if (prev && prev->fEndT == startT
&& this->binarySearchCoin(sect2, startT, prev->fStartT - startT, &coinStart,
&oppStartT)
&& prev->fStartT < coinStart && coinStart < startT
&& (cutFirst = prev->oppT(oppStartT))) {
oppFirst = cutFirst;
first = this->addSplitAt(prev, coinStart);
first->markCoincident();
prev->fCoinEnd.markCoincident();
if (oppFirst->fStartT < oppStartT && oppStartT < oppFirst->fEndT) {
SkTSpan<OppCurve, TCurve>* oppHalf = sect2->addSplitAt(oppFirst, oppStartT);
if (oppMatched) {
oppFirst->fCoinEnd.markCoincident();
oppHalf->markCoincident();
oppFirst = oppHalf;
} else {
oppFirst->markCoincident();
oppHalf->fCoinStart.markCoincident();
}
}
} else {
SkDEBUGCODE(coinStart = first->fStartT);
SkDEBUGCODE(oppStartT = oppMatched ? oppFirst->fStartT : oppFirst->fEndT);
}
// FIXME: incomplete : if we're not at the end, find end of coin
SkTSpan<OppCurve, TCurve>* oppLast;
SkASSERT(last->fCoinEnd.isCoincident());
oppLast = last->findOppT(last->fCoinEnd.perpT());
SkDEBUGCODE(coinEnd = last->fEndT);
SkDEBUGCODE(oppEndT = oppMatched ? oppLast->fEndT : oppLast->fStartT);
if (!oppMatched) {
SkTSwap(oppFirst, oppLast);
SkTSwap(oppStartT, oppEndT);
}
SkASSERT(oppStartT < oppEndT);
SkASSERT(coinStart == first->fStartT);
SkASSERT(coinEnd == last->fEndT);
SkASSERT(oppStartT == oppFirst->fStartT);
SkASSERT(oppEndT == oppLast->fEndT);
// reduce coincident runs to single entries
this->validate();
sect2->validate();
bool deleteEmptySpans = this->updateBounded(first, last, oppFirst);
deleteEmptySpans |= sect2->updateBounded(oppFirst, oppLast, first);
this->removeSpanRange(first, last);
sect2->removeSpanRange(oppFirst, oppLast);
first->fEndT = last->fEndT;
first->resetBounds(this->fCurve);
first->fCoinStart.setPerp(fCurve, first->fStartT, first->fPart[0], sect2->fCurve);
first->fCoinEnd.setPerp(fCurve, first->fEndT, first->fPart[TCurve::kPointLast], sect2->fCurve);
oppStartT = first->fCoinStart.perpT();
oppEndT = first->fCoinEnd.perpT();
if (between(0, oppStartT, 1) && between(0, oppEndT, 1)) {
if (!oppMatched) {
SkTSwap(oppStartT, oppEndT);
}
oppFirst->fStartT = oppStartT;
oppFirst->fEndT = oppEndT;
oppFirst->resetBounds(sect2->fCurve);
}
this->validateBounded();
sect2->validateBounded();
last = first->fNext;
this->removeCoincident(first, false);
sect2->removeCoincident(oppFirst, true);
if (deleteEmptySpans) {
this->deleteEmptySpans();
sect2->deleteEmptySpans();
}
this->validate();
sect2->validate();
return last && !last->fDeleted ? last : NULL;
}
template<typename TCurve, typename OppCurve>
SkTSpan<TCurve, OppCurve>* SkTSect<TCurve, OppCurve>::findCoincidentRun(
SkTSpan<TCurve, OppCurve>* first, SkTSpan<TCurve, OppCurve>** lastPtr) {
SkTSpan<TCurve, OppCurve>* work = first;
SkTSpan<TCurve, OppCurve>* lastCandidate = NULL;
first = NULL;
// find the first fully coincident span
do {
if (work->fCoinStart.isCoincident()) {
#if DEBUG_T_SECT
work->validatePerpT(work->fCoinStart.perpT());
work->validatePerpPt(work->fCoinStart.perpT(), work->fCoinStart.perpPt());
#endif
SkASSERT(work->hasOppT(work->fCoinStart.perpT()));
if (!work->fCoinEnd.isCoincident()) {
break;
}
lastCandidate = work;
if (!first) {
first = work;
}
} else if (first && work->fCollapsed) {
*lastPtr = lastCandidate;
return first;
} else {
lastCandidate = NULL;
SkASSERT(!first);
}
if (work == *lastPtr) {
return first;
}
work = work->fNext;
SkASSERT(work);
} while (true);
if (lastCandidate) {
*lastPtr = lastCandidate;
}
return first;
}
template<typename TCurve, typename OppCurve>
int SkTSect<TCurve, OppCurve>::intersects(SkTSpan<TCurve, OppCurve>* span,
SkTSect<OppCurve, TCurve>* opp,
SkTSpan<OppCurve, TCurve>* oppSpan, int* oppResult) {
bool spanStart, oppStart;
int hullResult = span->hullsIntersect(oppSpan, &spanStart, &oppStart);
if (hullResult >= 0) {
if (hullResult == 2) { // hulls have one point in common
if (!span->fBounded || !span->fBounded->fNext) {
SkASSERT(!span->fBounded || span->fBounded->fBounded == oppSpan);
if (spanStart) {
span->fEndT = span->fStartT;
} else {
span->fStartT = span->fEndT;
}
} else {
hullResult = 1;
}
if (!oppSpan->fBounded || !oppSpan->fBounded->fNext) {
SkASSERT(!oppSpan->fBounded || oppSpan->fBounded->fBounded == span);
if (oppStart) {
oppSpan->fEndT = oppSpan->fStartT;
} else {
oppSpan->fStartT = oppSpan->fEndT;
}
*oppResult = 2;
} else {
*oppResult = 1;
}
} else {
*oppResult = 1;
}
return hullResult;
}
if (span->fIsLine && oppSpan->fIsLine) {
SkIntersections i;
int sects = this->linesIntersect(span, opp, oppSpan, &i);
if (!sects) {
return -1;
}
span->fStartT = span->fEndT = i[0][0];
oppSpan->fStartT = oppSpan->fEndT = i[1][0];
return *oppResult = 2;
}
if (span->fIsLinear || oppSpan->fIsLinear) {
return *oppResult = (int) span->linearsIntersect(oppSpan);
}
return *oppResult = 1;
}
// while the intersection points are sufficiently far apart:
// construct the tangent lines from the intersections
// find the point where the tangent line intersects the opposite curve
template<typename TCurve, typename OppCurve>
int SkTSect<TCurve, OppCurve>::linesIntersect(SkTSpan<TCurve, OppCurve>* span,
SkTSect<OppCurve, TCurve>* opp,
SkTSpan<OppCurve, TCurve>* oppSpan, SkIntersections* i) {
SkIntersections thisRayI, oppRayI;
SkDLine thisLine = {{ span->fPart[0], span->fPart[TCurve::kPointLast] }};
SkDLine oppLine = {{ oppSpan->fPart[0], oppSpan->fPart[OppCurve::kPointLast] }};
int loopCount = 0;
double bestDistSq = DBL_MAX;
if (!thisRayI.intersectRay(opp->fCurve, thisLine)) {
return 0;
}
if (!oppRayI.intersectRay(this->fCurve, oppLine)) {
return 0;
}
do {
// pick the closest pair of points
double closest = DBL_MAX;
int closeIndex SK_INIT_TO_AVOID_WARNING;
int oppCloseIndex SK_INIT_TO_AVOID_WARNING;
for (int index = 0; index < oppRayI.used(); ++index) {
if (!roughly_between(span->fStartT, oppRayI[0][index], span->fEndT)) {
continue;
}
for (int oIndex = 0; oIndex < thisRayI.used(); ++oIndex) {
if (!roughly_between(oppSpan->fStartT, thisRayI[0][oIndex], oppSpan->fEndT)) {
continue;
}
double distSq = thisRayI.pt(index).distanceSquared(oppRayI.pt(oIndex));
if (closest > distSq) {
closest = distSq;
closeIndex = index;
oppCloseIndex = oIndex;
}
}
}
if (closest == DBL_MAX) {
break;
}
const SkDPoint& oppIPt = thisRayI.pt(oppCloseIndex);
const SkDPoint& iPt = oppRayI.pt(closeIndex);
if (between(span->fStartT, oppRayI[0][closeIndex], span->fEndT)
&& between(oppSpan->fStartT, thisRayI[0][oppCloseIndex], oppSpan->fEndT)
&& oppIPt.approximatelyEqual(iPt)) {
i->merge(oppRayI, closeIndex, thisRayI, oppCloseIndex);
return i->used();
}
double distSq = oppIPt.distanceSquared(iPt);
if (bestDistSq < distSq || ++loopCount > 5) {
return 0;
}
bestDistSq = distSq;
double oppStart = oppRayI[0][closeIndex];
thisLine[0] = fCurve.ptAtT(oppStart);
thisLine[1] = thisLine[0] + fCurve.dxdyAtT(oppStart);
if (!thisRayI.intersectRay(opp->fCurve, thisLine)) {
break;
}
double start = thisRayI[0][oppCloseIndex];
oppLine[0] = opp->fCurve.ptAtT(start);
oppLine[1] = oppLine[0] + opp->fCurve.dxdyAtT(start);
if (!oppRayI.intersectRay(this->fCurve, oppLine)) {
break;
}
} while (true);
// convergence may fail if the curves are nearly coincident
SkTCoincident<OppCurve, TCurve> oCoinS, oCoinE;
oCoinS.setPerp(opp->fCurve, oppSpan->fStartT, oppSpan->fPart[0], fCurve);
oCoinE.setPerp(opp->fCurve, oppSpan->fEndT, oppSpan->fPart[OppCurve::kPointLast], fCurve);
double tStart = oCoinS.perpT();
double tEnd = oCoinE.perpT();
bool swap = tStart > tEnd;
if (swap) {
SkTSwap(tStart, tEnd);
}
tStart = SkTMax(tStart, span->fStartT);
tEnd = SkTMin(tEnd, span->fEndT);
if (tStart > tEnd) {
return 0;
}
SkDVector perpS, perpE;
if (tStart == span->fStartT) {
SkTCoincident<TCurve, OppCurve> coinS;
coinS.setPerp(fCurve, span->fStartT, span->fPart[0], opp->fCurve);
perpS = span->fPart[0] - coinS.perpPt();
} else if (swap) {
perpS = oCoinE.perpPt() - oppSpan->fPart[OppCurve::kPointLast];
} else {
perpS = oCoinS.perpPt() - oppSpan->fPart[0];
}
if (tEnd == span->fEndT) {
SkTCoincident<TCurve, OppCurve> coinE;
coinE.setPerp(fCurve, span->fEndT, span->fPart[TCurve::kPointLast], opp->fCurve);
perpE = span->fPart[TCurve::kPointLast] - coinE.perpPt();
} else if (swap) {
perpE = oCoinS.perpPt() - oppSpan->fPart[0];
} else {
perpE = oCoinE.perpPt() - oppSpan->fPart[OppCurve::kPointLast];
}
if (perpS.dot(perpE) >= 0) {
return 0;
}
SkTCoincident<TCurve, OppCurve> coinW;
double workT = tStart;
double tStep = tEnd - tStart;
SkDPoint workPt;
do {
tStep *= 0.5;
if (precisely_zero(tStep)) {
return 0;
}
workT += tStep;
workPt = fCurve.ptAtT(workT);
coinW.setPerp(fCurve, workT, workPt, opp->fCurve);
SkDVector perpW = workPt - coinW.perpPt();
if ((perpS.dot(perpW) >= 0) == (tStep < 0)) {
tStep = -tStep;
}
} while (!workPt.approximatelyEqual(coinW.perpPt()));
double oppTTest = coinW.perpT();
if (!opp->fHead->contains(oppTTest)) {
return 0;
}
i->setMax(1);
i->insert(workT, oppTTest, workPt);
return 1;
}
template<typename TCurve, typename OppCurve>
void SkTSect<TCurve, OppCurve>::markSpanGone(SkTSpan<TCurve, OppCurve>* span) {
--fActiveCount;
span->fNext = fDeleted;
fDeleted = span;
SkASSERT(!span->fDeleted);
span->fDeleted = true;
}
template<typename TCurve, typename OppCurve>
bool SkTSect<TCurve, OppCurve>::matchedDirection(double t, const SkTSect<OppCurve, TCurve>* sect2,
double t2) const {
SkDVector dxdy = this->fCurve.dxdyAtT(t);
SkDVector dxdy2 = sect2->fCurve.dxdyAtT(t2);
return dxdy.dot(dxdy2) >= 0;
}
template<typename TCurve, typename OppCurve>
void SkTSect<TCurve, OppCurve>::matchedDirCheck(double t, const SkTSect<OppCurve, TCurve>* sect2,
double t2, bool* calcMatched, bool* oppMatched) const {
if (*calcMatched) {
SkASSERT(*oppMatched == this->matchedDirection(t, sect2, t2));
} else {
*oppMatched = this->matchedDirection(t, sect2, t2);
*calcMatched = true;
}
}
template<typename TCurve, typename OppCurve>
void SkTSect<TCurve, OppCurve>::mergeCoincidence(SkTSect<OppCurve, TCurve>* sect2) {
double smallLimit = 0;
do {
// find the smallest unprocessed span
SkTSpan<TCurve, OppCurve>* smaller = NULL;
SkTSpan<TCurve, OppCurve>* test = fCoincident;
do {
if (test->fStartT < smallLimit) {
continue;
}
if (smaller && smaller->fEndT < test->fStartT) {
continue;
}
smaller = test;
} while ((test = test->fNext));
if (!smaller) {
return;
}
smallLimit = smaller->fEndT;
// find next larger span
SkTSpan<TCurve, OppCurve>* prior = NULL;
SkTSpan<TCurve, OppCurve>* larger = NULL;
SkTSpan<TCurve, OppCurve>* largerPrior = NULL;
test = fCoincident;
do {
if (test->fStartT < smaller->fEndT) {
continue;
}
SkASSERT(test->fStartT != smaller->fEndT);
if (larger && larger->fStartT < test->fStartT) {
continue;
}
largerPrior = prior;
larger = test;
} while ((prior = test), (test = test->fNext));
if (!larger) {
continue;
}
// check middle t value to see if it is coincident as well
double midT = (smaller->fEndT + larger->fStartT) / 2;
SkDPoint midPt = fCurve.ptAtT(midT);
SkTCoincident<TCurve, OppCurve> coin;
coin.setPerp(fCurve, midT, midPt, sect2->fCurve);
if (coin.isCoincident()) {
smaller->fEndT = larger->fEndT;
smaller->fCoinEnd = larger->fCoinEnd;
if (largerPrior) {
largerPrior->fNext = larger->fNext;
} else {
fCoincident = larger->fNext;
}
}
} while (true);
}
template<typename TCurve, typename OppCurve>
SkTSpan<TCurve, OppCurve>* SkTSect<TCurve, OppCurve>::prev(
SkTSpan<TCurve, OppCurve>* span) const {
SkTSpan<TCurve, OppCurve>* result = NULL;
SkTSpan<TCurve, OppCurve>* test = fHead;
while (span != test) {
result = test;
test = test->fNext;
SkASSERT(test);
}
return result;
}
template<typename TCurve, typename OppCurve>
void SkTSect<TCurve, OppCurve>::recoverCollapsed() {
SkTSpan<TCurve, OppCurve>* deleted = fDeleted;
while (deleted) {
SkTSpan<TCurve, OppCurve>* delNext = deleted->fNext;
if (deleted->fCollapsed) {
SkTSpan<TCurve, OppCurve>** spanPtr = &fHead;
while (*spanPtr && (*spanPtr)->fEndT <= deleted->fStartT) {
spanPtr = &(*spanPtr)->fNext;
}
deleted->fNext = *spanPtr;
*spanPtr = deleted;
}
deleted = delNext;
}
}
template<typename TCurve, typename OppCurve>
void SkTSect<TCurve, OppCurve>::removeAllBut(const SkTSpan<OppCurve, TCurve>* keep,
SkTSpan<TCurve, OppCurve>* span, SkTSect<OppCurve, TCurve>* opp) {
const SkTSpanBounded<OppCurve, TCurve>* testBounded = span->fBounded;
while (testBounded) {
SkTSpan<OppCurve, TCurve>* bounded = testBounded->fBounded;
const SkTSpanBounded<OppCurve, TCurve>* next = testBounded->fNext;
// may have been deleted when opp did 'remove all but'
if (bounded != keep && !bounded->fDeleted) {
SkAssertResult(SkDEBUGCODE(!) span->removeBounded(bounded));
if (bounded->removeBounded(span)) {
opp->removeSpan(bounded);
}
}
testBounded = next;
}
SkASSERT(!span->fDeleted);
SkASSERT(span->findOppSpan(keep));
SkASSERT(keep->findOppSpan(span));
}
template<typename TCurve, typename OppCurve>
void SkTSect<TCurve, OppCurve>::removeByPerpendicular(SkTSect<OppCurve, TCurve>* opp) {
SkTSpan<TCurve, OppCurve>* test = fHead;
SkTSpan<TCurve, OppCurve>* next;
do {
next = test->fNext;
if (test->fCoinStart.perpT() < 0 || test->fCoinEnd.perpT() < 0) {
continue;
}
SkDVector startV = test->fCoinStart.perpPt() - test->fPart[0];
SkDVector endV = test->fCoinEnd.perpPt() - test->fPart[TCurve::kPointLast];
#if DEBUG_T_SECT
SkDebugf("%s startV=(%1.9g,%1.9g) endV=(%1.9g,%1.9g) dot=%1.9g\n", __FUNCTION__,
startV.fX, startV.fY, endV.fX, endV.fY, startV.dot(endV));
#endif
if (startV.dot(endV) <= 0) {
continue;
}
this->removeSpans(test, opp);
} while ((test = next));
}
template<typename TCurve, typename OppCurve>
void SkTSect<TCurve, OppCurve>::removeCoincident(SkTSpan<TCurve, OppCurve>* span, bool isBetween) {
this->unlinkSpan(span);
if (isBetween || between(0, span->fCoinStart.perpT(), 1)) {
--fActiveCount;
span->fNext = fCoincident;
fCoincident = span;
} else {
this->markSpanGone(span);
}
}
template<typename TCurve, typename OppCurve>
void SkTSect<TCurve, OppCurve>::removeSpan(SkTSpan<TCurve, OppCurve>* span) {
this->unlinkSpan(span);
this->markSpanGone(span);
}
template<typename TCurve, typename OppCurve>
void SkTSect<TCurve, OppCurve>::removeSpanRange(SkTSpan<TCurve, OppCurve>* first,
SkTSpan<TCurve, OppCurve>* last) {
if (first == last) {
return;
}
SkTSpan<TCurve, OppCurve>* span = first;
SkASSERT(span);
SkTSpan<TCurve, OppCurve>* final = last->fNext;
SkTSpan<TCurve, OppCurve>* next = span->fNext;
while ((span = next) && span != final) {
next = span->fNext;
this->markSpanGone(span);
}
if (final) {
final->fPrev = first;
}
first->fNext = final;
}
template<typename TCurve, typename OppCurve>
void SkTSect<TCurve, OppCurve>::removeSpans(SkTSpan<TCurve, OppCurve>* span,
SkTSect<OppCurve, TCurve>* opp) {
SkTSpanBounded<OppCurve, TCurve>* bounded = span->fBounded;
while (bounded) {
SkTSpan<OppCurve, TCurve>* spanBounded = bounded->fBounded;
SkTSpanBounded<OppCurve, TCurve>* next = bounded->fNext;
if (span->removeBounded(spanBounded)) { // shuffles last into position 0
this->removeSpan(span);
}
if (spanBounded->removeBounded(span)) {
opp->removeSpan(spanBounded);
}
SkASSERT(!span->fDeleted || !opp->debugHasBounded(span));
bounded = next;
}
}
template<typename TCurve, typename OppCurve>
SkTSpan<TCurve, OppCurve>* SkTSect<TCurve, OppCurve>::spanAtT(double t,
SkTSpan<TCurve, OppCurve>** priorSpan) {
SkTSpan<TCurve, OppCurve>* test = fHead;
SkTSpan<TCurve, OppCurve>* prev = NULL;
while (test && test->fEndT < t) {
prev = test;
test = test->fNext;
}
*priorSpan = prev;
return test && test->fStartT <= t ? test : NULL;
}
template<typename TCurve, typename OppCurve>
SkTSpan<TCurve, OppCurve>* SkTSect<TCurve, OppCurve>::tail() {
SkTSpan<TCurve, OppCurve>* result = fHead;
SkTSpan<TCurve, OppCurve>* next = fHead;
while ((next = next->fNext)) {
if (next->fEndT > result->fEndT) {
result = next;
}
}
return result;
}
/* Each span has a range of opposite spans it intersects. After the span is split in two,
adjust the range to its new size */
template<typename TCurve, typename OppCurve>
void SkTSect<TCurve, OppCurve>::trim(SkTSpan<TCurve, OppCurve>* span,
SkTSect<OppCurve, TCurve>* opp) {
span->initBounds(fCurve);
const SkTSpanBounded<OppCurve, TCurve>* testBounded = span->fBounded;
while (testBounded) {
SkTSpan<OppCurve, TCurve>* test = testBounded->fBounded;
const SkTSpanBounded<OppCurve, TCurve>* next = testBounded->fNext;
int oppSects, sects = this->intersects(span, opp, test, &oppSects);
if (sects >= 1) {
if (oppSects == 2) {
test->initBounds(opp->fCurve);
opp->removeAllBut(span, test, this);
}
if (sects == 2) {
span->initBounds(fCurve);
this->removeAllBut(test, span, opp);
return;
}
} else {
if (span->removeBounded(test)) {
this->removeSpan(span);
}
if (test->removeBounded(span)) {
opp->removeSpan(test);
}
}
testBounded = next;
}
}
template<typename TCurve, typename OppCurve>
void SkTSect<TCurve, OppCurve>::unlinkSpan(SkTSpan<TCurve, OppCurve>* span) {
SkTSpan<TCurve, OppCurve>* prev = span->fPrev;
SkTSpan<TCurve, OppCurve>* next = span->fNext;
if (prev) {
prev->fNext = next;
if (next) {
next->fPrev = prev;
}
} else {
fHead = next;
if (next) {
next->fPrev = NULL;
}
}
}
template<typename TCurve, typename OppCurve>
bool SkTSect<TCurve, OppCurve>::updateBounded(SkTSpan<TCurve, OppCurve>* first,
SkTSpan<TCurve, OppCurve>* last, SkTSpan<OppCurve, TCurve>* oppFirst) {
SkTSpan<TCurve, OppCurve>* test = first;
const SkTSpan<TCurve, OppCurve>* final = last->next();
bool deleteSpan = false;
do {
deleteSpan |= test->removeAllBounded();
} while ((test = test->fNext) != final);
first->fBounded = NULL;
first->addBounded(oppFirst, &fHeap);
// cannot call validate until remove span range is called
return deleteSpan;
}
template<typename TCurve, typename OppCurve>
void SkTSect<TCurve, OppCurve>::validate() const {
#if DEBUG_T_SECT
int count = 0;
if (fHead) {
const SkTSpan<TCurve, OppCurve>* span = fHead;
SkASSERT(!span->fPrev);
SkDEBUGCODE(double last = 0);
do {
span->validate();
SkASSERT(span->fStartT >= last);
SkDEBUGCODE(last = span->fEndT);
++count;
} while ((span = span->fNext) != NULL);
}
SkASSERT(count == fActiveCount);
SkASSERT(fActiveCount <= fDebugAllocatedCount);
int deletedCount = 0;
const SkTSpan<TCurve, OppCurve>* deleted = fDeleted;
while (deleted) {
++deletedCount;
deleted = deleted->fNext;
}
const SkTSpan<TCurve, OppCurve>* coincident = fCoincident;
while (coincident) {
++deletedCount;
coincident = coincident->fNext;
}
SkASSERT(fActiveCount + deletedCount == fDebugAllocatedCount);
#endif
}
template<typename TCurve, typename OppCurve>
void SkTSect<TCurve, OppCurve>::validateBounded() const {
#if DEBUG_T_SECT
if (!fHead) {
return;
}
const SkTSpan<TCurve, OppCurve>* span = fHead;
do {
span->validateBounded();
} while ((span = span->fNext) != NULL);
#endif
}
template<typename TCurve, typename OppCurve>
int SkTSect<TCurve, OppCurve>::EndsEqual(const SkTSect<TCurve, OppCurve>* sect1,
const SkTSect<OppCurve, TCurve>* sect2, SkIntersections* intersections) {
int zeroOneSet = 0;
if (sect1->fCurve[0] == sect2->fCurve[0]) {
zeroOneSet |= kZeroS1Set | kZeroS2Set;
intersections->insert(0, 0, sect1->fCurve[0]);
}
if (sect1->fCurve[0] == sect2->fCurve[OppCurve::kPointLast]) {
zeroOneSet |= kZeroS1Set | kOneS2Set;
intersections->insert(0, 1, sect1->fCurve[0]);
}
if (sect1->fCurve[TCurve::kPointLast] == sect2->fCurve[0]) {
zeroOneSet |= kOneS1Set | kZeroS2Set;
intersections->insert(1, 0, sect1->fCurve[TCurve::kPointLast]);
}
if (sect1->fCurve[TCurve::kPointLast] == sect2->fCurve[OppCurve::kPointLast]) {
zeroOneSet |= kOneS1Set | kOneS2Set;
intersections->insert(1, 1, sect1->fCurve[TCurve::kPointLast]);
}
// check for zero
if (!(zeroOneSet & (kZeroS1Set | kZeroS2Set))
&& sect1->fCurve[0].approximatelyEqual(sect2->fCurve[0])) {
zeroOneSet |= kZeroS1Set | kZeroS2Set;
intersections->insertNear(0, 0, sect1->fCurve[0], sect2->fCurve[0]);
}
if (!(zeroOneSet & (kZeroS1Set | kOneS2Set))
&& sect1->fCurve[0].approximatelyEqual(sect2->fCurve[OppCurve::kPointLast])) {
zeroOneSet |= kZeroS1Set | kOneS2Set;
intersections->insertNear(0, 1, sect1->fCurve[0], sect2->fCurve[OppCurve::kPointLast]);
}
// check for one
if (!(zeroOneSet & (kOneS1Set | kZeroS2Set))
&& sect1->fCurve[TCurve::kPointLast].approximatelyEqual(sect2->fCurve[0])) {
zeroOneSet |= kOneS1Set | kZeroS2Set;
intersections->insertNear(1, 0, sect1->fCurve[TCurve::kPointLast], sect2->fCurve[0]);
}
if (!(zeroOneSet & (kOneS1Set | kOneS2Set))
&& sect1->fCurve[TCurve::kPointLast].approximatelyEqual(sect2->fCurve[
OppCurve::kPointLast])) {
zeroOneSet |= kOneS1Set | kOneS2Set;
intersections->insertNear(1, 1, sect1->fCurve[TCurve::kPointLast],
sect2->fCurve[OppCurve::kPointLast]);
}
return zeroOneSet;
}
template<typename TCurve, typename OppCurve>
struct SkClosestRecord {
bool operator<(const SkClosestRecord& rh) const {
return fClosest < rh.fClosest;
}
void addIntersection(SkIntersections* intersections) const {
double r1t = fC1Index ? fC1Span->endT() : fC1Span->startT();
double r2t = fC2Index ? fC2Span->endT() : fC2Span->startT();
intersections->insert(r1t, r2t, fC1Span->part()[fC1Index]);
}
void findEnd(const SkTSpan<TCurve, OppCurve>* span1, const SkTSpan<OppCurve, TCurve>* span2,
int c1Index, int c2Index) {
const TCurve& c1 = span1->part();
const OppCurve& c2 = span2->part();
if (!c1[c1Index].approximatelyEqual(c2[c2Index])) {
return;
}
double dist = c1[c1Index].distanceSquared(c2[c2Index]);
if (fClosest < dist) {
return;
}
fC1Span = span1;
fC2Span = span2;
fC1StartT = span1->startT();
fC1EndT = span1->endT();
fC2StartT = span2->startT();
fC2EndT = span2->endT();
fC1Index = c1Index;
fC2Index = c2Index;
fClosest = dist;
}
bool matesWith(const SkClosestRecord& mate) const {
SkASSERT(fC1Span == mate.fC1Span || fC1Span->endT() <= mate.fC1Span->startT()
|| mate.fC1Span->endT() <= fC1Span->startT());
SkASSERT(fC2Span == mate.fC2Span || fC2Span->endT() <= mate.fC2Span->startT()
|| mate.fC2Span->endT() <= fC2Span->startT());
return fC1Span == mate.fC1Span || fC1Span->endT() == mate.fC1Span->startT()
|| fC1Span->startT() == mate.fC1Span->endT()
|| fC2Span == mate.fC2Span
|| fC2Span->endT() == mate.fC2Span->startT()
|| fC2Span->startT() == mate.fC2Span->endT();
}
void merge(const SkClosestRecord& mate) {
fC1Span = mate.fC1Span;
fC2Span = mate.fC2Span;
fClosest = mate.fClosest;
fC1Index = mate.fC1Index;
fC2Index = mate.fC2Index;
}
void reset() {
fClosest = FLT_MAX;
SkDEBUGCODE(fC1Span = NULL);
SkDEBUGCODE(fC2Span = NULL);
SkDEBUGCODE(fC1Index = fC2Index = -1);
}
void update(const SkClosestRecord& mate) {
fC1StartT = SkTMin(fC1StartT, mate.fC1StartT);
fC1EndT = SkTMax(fC1EndT, mate.fC1EndT);
fC2StartT = SkTMin(fC2StartT, mate.fC2StartT);
fC2EndT = SkTMax(fC2EndT, mate.fC2EndT);
}
const SkTSpan<TCurve, OppCurve>* fC1Span;
const SkTSpan<OppCurve, TCurve>* fC2Span;
double fC1StartT;
double fC1EndT;
double fC2StartT;
double fC2EndT;
double fClosest;
int fC1Index;
int fC2Index;
};
template<typename TCurve, typename OppCurve>
struct SkClosestSect {
SkClosestSect()
: fUsed(0) {
fClosest.push_back().reset();
}
bool find(const SkTSpan<TCurve, OppCurve>* span1, const SkTSpan<OppCurve, TCurve>* span2) {
SkClosestRecord<TCurve, OppCurve>* record = &fClosest[fUsed];
record->findEnd(span1, span2, 0, 0);
record->findEnd(span1, span2, 0, OppCurve::kPointLast);
record->findEnd(span1, span2, TCurve::kPointLast, 0);
record->findEnd(span1, span2, TCurve::kPointLast, OppCurve::kPointLast);
if (record->fClosest == FLT_MAX) {
return false;
}
for (int index = 0; index < fUsed; ++index) {
SkClosestRecord<TCurve, OppCurve>* test = &fClosest[index];
if (test->matesWith(*record)) {
if (test->fClosest > record->fClosest) {
test->merge(*record);
}
test->update(*record);
record->reset();
return false;
}
}
++fUsed;
fClosest.push_back().reset();
return true;
}
void finish(SkIntersections* intersections) const {
SkSTArray<TCurve::kMaxIntersections * 3,
const SkClosestRecord<TCurve, OppCurve>*, true> closestPtrs;
for (int index = 0; index < fUsed; ++index) {
closestPtrs.push_back(&fClosest[index]);
}
SkTQSort<const SkClosestRecord<TCurve, OppCurve> >(closestPtrs.begin(), closestPtrs.end()
- 1);
for (int index = 0; index < fUsed; ++index) {
const SkClosestRecord<TCurve, OppCurve>* test = closestPtrs[index];
test->addIntersection(intersections);
}
}
// this is oversized so that an extra records can merge into final one
SkSTArray<TCurve::kMaxIntersections * 2, SkClosestRecord<TCurve, OppCurve>, true> fClosest;
int fUsed;
};
// returns true if the rect is too small to consider
template<typename TCurve, typename OppCurve>
void SkTSect<TCurve, OppCurve>::BinarySearch(SkTSect<TCurve, OppCurve>* sect1,
SkTSect<OppCurve, TCurve>* sect2, SkIntersections* intersections) {
#if DEBUG_T_SECT_DUMP > 1
gDumpTSectNum = 0;
#endif
SkDEBUGCODE(sect1->fOppSect = sect2);
SkDEBUGCODE(sect2->fOppSect = sect1);
intersections->reset();
intersections->setMax(TCurve::kMaxIntersections * 3); // give extra for slop
SkTSpan<TCurve, OppCurve>* span1 = sect1->fHead;
SkTSpan<OppCurve, TCurve>* span2 = sect2->fHead;
int oppSect, sect = sect1->intersects(span1, sect2, span2, &oppSect);
// SkASSERT(between(0, sect, 2));
if (!sect) {
return;
}
if (sect == 2 && oppSect == 2) {
(void) EndsEqual(sect1, sect2, intersections);
return;
}
span1->addBounded(span2, §1->fHeap);
span2->addBounded(span1, §2->fHeap);
do {
// find the largest bounds
SkTSpan<TCurve, OppCurve>* largest1 = sect1->boundsMax();
if (!largest1) {
break;
}
SkTSpan<OppCurve, TCurve>* largest2 = sect2->boundsMax();
// split it
if (!largest2 || (largest1 && (largest1->fBoundsMax > largest2->fBoundsMax
|| (!largest1->fCollapsed && largest2->fCollapsed)))) {
if (largest1->fCollapsed) {
break;
}
// trim parts that don't intersect the opposite
SkTSpan<TCurve, OppCurve>* half1 = sect1->addOne();
if (!half1->split(largest1, §1->fHeap)) {
break;
}
sect1->trim(largest1, sect2);
sect1->trim(half1, sect2);
} else {
if (largest2->fCollapsed) {
break;
}
// trim parts that don't intersect the opposite
SkTSpan<OppCurve, TCurve>* half2 = sect2->addOne();
if (!half2->split(largest2, §2->fHeap)) {
break;
}
sect2->trim(largest2, sect1);
sect2->trim(half2, sect1);
}
sect1->validate();
sect2->validate();
// if there are 9 or more continuous spans on both sects, suspect coincidence
if (sect1->fActiveCount >= COINCIDENT_SPAN_COUNT
&& sect2->fActiveCount >= COINCIDENT_SPAN_COUNT) {
sect1->coincidentCheck(sect2);
sect1->validate();
sect2->validate();
}
if (sect1->fActiveCount >= COINCIDENT_SPAN_COUNT
&& sect2->fActiveCount >= COINCIDENT_SPAN_COUNT) {
sect1->computePerpendiculars(sect2, sect1->fHead, sect1->tail());
sect2->computePerpendiculars(sect1, sect2->fHead, sect2->tail());
sect1->removeByPerpendicular(sect2);
sect1->validate();
sect2->validate();
if (sect1->collapsed() > TCurve::kMaxIntersections) {
break;
}
}
#if DEBUG_T_SECT_DUMP
sect1->dumpBoth(sect2);
#endif
if (!sect1->fHead || !sect2->fHead) {
break;
}
} while (true);
SkTSpan<TCurve, OppCurve>* coincident = sect1->fCoincident;
if (coincident) {
// if there is more than one coincident span, check loosely to see if they should be joined
if (coincident->fNext) {
sect1->mergeCoincidence(sect2);
coincident = sect1->fCoincident;
}
SkASSERT(sect2->fCoincident); // courtesy check : coincidence only looks at sect 1
do {
SkASSERT(coincident->fCoinStart.isCoincident());
SkASSERT(coincident->fCoinEnd.isCoincident());
int index = intersections->insertCoincident(coincident->fStartT,
coincident->fCoinStart.perpT(), coincident->fPart[0]);
if ((intersections->insertCoincident(coincident->fEndT,
coincident->fCoinEnd.perpT(),
coincident->fPart[TCurve::kPointLast]) < 0) && index >= 0) {
intersections->clearCoincidence(index);
}
} while ((coincident = coincident->fNext));
}
int zeroOneSet = EndsEqual(sect1, sect2, intersections);
if (!sect1->fHead || !sect2->fHead) {
return;
}
sect1->recoverCollapsed();
sect2->recoverCollapsed();
SkTSpan<TCurve, OppCurve>* result1 = sect1->fHead;
// check heads and tails for zero and ones and insert them if we haven't already done so
const SkTSpan<TCurve, OppCurve>* head1 = result1;
if (!(zeroOneSet & kZeroS1Set) && approximately_less_than_zero(head1->fStartT)) {
const SkDPoint& start1 = sect1->fCurve[0];
if (head1->isBounded()) {
double t = head1->closestBoundedT(start1);
if (sect2->fCurve.ptAtT(t).approximatelyEqual(start1)) {
intersections->insert(0, t, start1);
}
}
}
const SkTSpan<OppCurve, TCurve>* head2 = sect2->fHead;
if (!(zeroOneSet & kZeroS2Set) && approximately_less_than_zero(head2->fStartT)) {
const SkDPoint& start2 = sect2->fCurve[0];
if (head2->isBounded()) {
double t = head2->closestBoundedT(start2);
if (sect1->fCurve.ptAtT(t).approximatelyEqual(start2)) {
intersections->insert(t, 0, start2);
}
}
}
const SkTSpan<TCurve, OppCurve>* tail1 = sect1->tail();
if (!(zeroOneSet & kOneS1Set) && approximately_greater_than_one(tail1->fEndT)) {
const SkDPoint& end1 = sect1->fCurve[TCurve::kPointLast];
if (tail1->isBounded()) {
double t = tail1->closestBoundedT(end1);
if (sect2->fCurve.ptAtT(t).approximatelyEqual(end1)) {
intersections->insert(1, t, end1);
}
}
}
const SkTSpan<OppCurve, TCurve>* tail2 = sect2->tail();
if (!(zeroOneSet & kOneS2Set) && approximately_greater_than_one(tail2->fEndT)) {
const SkDPoint& end2 = sect2->fCurve[OppCurve::kPointLast];
if (tail2->isBounded()) {
double t = tail2->closestBoundedT(end2);
if (sect1->fCurve.ptAtT(t).approximatelyEqual(end2)) {
intersections->insert(t, 1, end2);
}
}
}
SkClosestSect<TCurve, OppCurve> closest;
do {
while (result1 && result1->fCoinStart.isCoincident() && result1->fCoinEnd.isCoincident()) {
result1 = result1->fNext;
}
if (!result1) {
break;
}
SkTSpan<OppCurve, TCurve>* result2 = sect2->fHead;
bool found = false;
while (result2) {
found |= closest.find(result1, result2);
result2 = result2->fNext;
}
} while ((result1 = result1->fNext));
closest.finish(intersections);
// if there is more than one intersection and it isn't already coincident, check
int last = intersections->used() - 1;
for (int index = 0; index < last; ) {
if (intersections->isCoincident(index) && intersections->isCoincident(index + 1)) {
++index;
continue;
}
double midT = ((*intersections)[0][index] + (*intersections)[0][index + 1]) / 2;
SkDPoint midPt = sect1->fCurve.ptAtT(midT);
// intersect perpendicular with opposite curve
SkTCoincident<TCurve, OppCurve> perp;
perp.setPerp(sect1->fCurve, midT, midPt, sect2->fCurve);
if (!perp.isCoincident()) {
++index;
continue;
}
if (intersections->isCoincident(index)) {
intersections->removeOne(index);
--last;
} else if (intersections->isCoincident(index + 1)) {
intersections->removeOne(index + 1);
--last;
} else {
intersections->setCoincident(index++);
}
intersections->setCoincident(index);
}
SkASSERT(intersections->used() <= TCurve::kMaxIntersections);
}