| /* |
| * 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); |
| } |
