new files for pathops geometric intersection

src/pathops/SkPathOpsTSect.h

+/*
+ * 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 "SkPathOpsRect.h"
+#include "SkPathOpsQuad.h"
+#include "SkIntersections.h"
+#include "SkTArray.h"
+
+/* TCurve is either SkDQuadratic or SkDCubic */
+template<typename TCurve>
+class SkTCoincident {
+public:
+    bool isCoincident() const {
+        return fCoincident;
+    }
+
+    void init() {
+        fCoincident = false;
+        SkDEBUGCODE(fPerpPt.fX = fPerpPt.fY = SK_ScalarNaN);
+        SkDEBUGCODE(fPerpT = 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 TCurve& );
+
+private:
+    SkDPoint fPerpPt;
+    double fPerpT;  // perpendicular intersection on opposite curve
+    bool fCoincident;
+};
+
+template<typename TCurve> class SkTSect;
+
+/* Curve is either TCurve or SkDCubic */
+template<typename TCurve>
+class SkTSpan {
+public:
+    void init(const TCurve& );
+    void initBounds(const TCurve& );
+
+    double closestBoundedT(const SkDPoint& pt) const;
+
+    bool contains(double t) const {
+        return !! const_cast<SkTSpan*>(this)->innerFind(t);
+    }
+
+    bool contains(const SkTSpan* span) const;
+
+    double endT() const {
+        return fEndT;
+    }
+
+    SkTSpan* find(double t) {
+        SkTSpan* result = innerFind(t);
+        SkASSERT(result);
+        return result;
+    }
+
+    bool intersects(const SkTSpan* span, bool* check);
+
+    const SkTSpan* next() const {
+        return fNext;
+    }
+
+    const TCurve& part() const {
+        return fPart;
+    }
+
+    void reset() {
+        fBounded.reset();
+    }
+
+    bool split(SkTSpan* work) {
+        return splitAt(work, (work->fStartT + work->fEndT) * 0.5);
+    }
+
+    bool splitAt(SkTSpan* work, double t);
+
+    double startT() const {
+        return fStartT;
+    }
+
+    bool tightBoundsIntersects(const SkTSpan* span) const;
+
+    // implementation is for testing only
+    void dump() const {
+        dump(NULL);
+    }
+
+private:
+    SkTSpan* innerFind(double t);
+    bool linearIntersects(const TCurve& ) const;
+
+    // implementation is for testing only
+#if DEBUG_T_SECT
+    int debugID(const SkTSect<TCurve>* ) const { return fDebugID; }
+#else
+    int debugID(const SkTSect<TCurve>* ) const;
+#endif
+    void dump(const SkTSect<TCurve>* ) const;
+    void dumpID(const SkTSect<TCurve>* ) const;
+
+#if DEBUG_T_SECT
+    void validate() const;
+#endif
+
+    TCurve fPart;
+    SkTCoincident<TCurve> fCoinStart;
+    SkTCoincident<TCurve> fCoinEnd;
+    SkSTArray<4, SkTSpan*, true> fBounded;
+    SkTSpan* fPrev;
+    SkTSpan* fNext;
+    SkDRect fBounds;
+    double fStartT;
+    double fEndT;
+    double fBoundsMax;
+    bool fCollapsed;
+    bool fHasPerp;
+    bool fIsLinear;
+#if DEBUG_T_SECT
+    int fDebugID;
+    bool fDebugDeleted;
+#endif
+    friend class SkTSect<TCurve>;
+};
+
+template<typename TCurve>
+class SkTSect {
+public:
+    SkTSect(const TCurve& c  PATH_OPS_DEBUG_PARAMS(int id));
+    static void BinarySearch(SkTSect* sect1, SkTSect* sect2, SkIntersections* intersections);
+
+    // for testing only
+    void dump() const;
+    void dumpBoth(const SkTSect& opp) const;
+    void dumpBoth(const SkTSect* opp) const;
+    void dumpCurves() const;
+
+private:
+    enum {
+        kZeroS1Set = 1,
+        kOneS1Set = 2,
+        kZeroS2Set = 4,
+        kOneS2Set = 8
+    };
+
+    SkTSpan<TCurve>* addOne();
+    bool binarySearchCoin(const SkTSect& , double tStart, double tStep, double* t, double* oppT);
+    SkTSpan<TCurve>* boundsMax() const;
+    void coincidentCheck(SkTSect* sect2);
+    static int EndsEqual(const SkTSect* sect1, const SkTSect* sect2, SkIntersections* );
+    bool intersects(SkTSpan<TCurve>* span, const SkTSect* opp,
+            const SkTSpan<TCurve>* oppSpan) const;
+    void onCurveCheck(SkTSect* sect2, SkTSpan<TCurve>* first, SkTSpan<TCurve>* last);
+    void recoverCollapsed();
+    void removeSpan(SkTSpan<TCurve>* span);
+    void removeOne(const SkTSpan<TCurve>* test, SkTSpan<TCurve>* span);
+    void removeSpans(SkTSpan<TCurve>* span, SkTSect* opp);
+    void setPerp(const TCurve& opp, SkTSpan<TCurve>* first, SkTSpan<TCurve>* last);
+    const SkTSpan<TCurve>* tail() const;
+    void trim(SkTSpan<TCurve>* span, SkTSect* opp);
+
+#if DEBUG_T_SECT
+    int debugID() const { return fDebugID; }
+    void validate() const;
+#else
+    int debugID() const { return 0; }
+#endif
+    const TCurve& fCurve;
+    SkChunkAlloc fHeap;
+    SkTSpan<TCurve>* fHead;
+    SkTSpan<TCurve>* fDeleted;
+    int fActiveCount;
+#if DEBUG_T_SECT
+    int fDebugID;
+    int fDebugCount;
+    int fDebugAllocatedCount;
+#endif
+    friend class SkTSpan<TCurve>;  // only used by debug id
+};
+
+#define COINCIDENT_SPAN_COUNT 9
+
+template<typename TCurve>
+void SkTCoincident<TCurve>::setPerp(const TCurve& c1, double t,
+        const SkDPoint& cPt, const TCurve& 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) {
+        fPerpT = -1;
+        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);
+        }
+    }
+    fCoincident = cPt.approximatelyEqual(fPerpPt);
+#if DEBUG_T_SECT
+    if (fCoincident) {
+        SkDebugf("");  // allow setting breakpoint
+    }
+#endif
+}
+
+template<typename TCurve>
+void SkTSpan<TCurve>::init(const TCurve& c) {
+    fPrev = fNext = NULL;
+    fIsLinear = false;
+    fStartT = 0;
+    fEndT = 1;
+    initBounds(c);
+}
+
+template<typename TCurve>
+void SkTSpan<TCurve>::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;
+#if DEBUG_T_SECT
+    fDebugDeleted = false;
+    if (fCollapsed) {
+        SkDebugf("");  // for convenient breakpoints
+    }
+#endif
+}
+
+template<typename TCurve>
+double SkTSpan<TCurve>::closestBoundedT(const SkDPoint& pt) const {
+    int count = fBounded.count();
+    double result = -1;
+    double closest = FLT_MAX;
+    for (int index = 0; index < count; ++index) {
+        const SkTSpan* test = fBounded[index];
+        double startDist = test->fPart[0].distanceSquared(pt);
+        if (closest > startDist) {
+            closest = startDist;
+            result = test->fStartT;
+        }
+        double endDist = test->fPart[TCurve::kPointLast].distanceSquared(pt);
+        if (closest > endDist) {
+            closest = endDist;
+            result = test->fEndT;
+        }
+    }
+    SkASSERT(between(0, result, 1));
+    return result;
+}
+
+template<typename TCurve>
+bool SkTSpan<TCurve>::contains(const SkTSpan* span) const {
+    int count = fBounded.count();
+    for (int index = 0; index < count; ++index) {
+        const SkTSpan* test = fBounded[index];
+        if (span == test) {
+            return true;
+        }
+    }
+    return false;
+}
+
+template<typename TCurve>
+SkTSpan<TCurve>* SkTSpan<TCurve>::innerFind(double t) {
+    SkTSpan* work = this;
+    do {
+        if (between(work->fStartT, t, work->fEndT)) {
+            return work;
+        }
+    } while ((work = work->fNext));
+    return NULL;
+}
+
+// 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>
+bool SkTSpan<TCurve>::intersects(const SkTSpan* span, bool* check) {
+    if (!fBounds.intersects(span->fBounds)) {
+        *check = false;  // no need to check to see if the bounds have end points in common
+        return false;
+    }
+    if (!fIsLinear && fPart.hullIntersects(span->fPart, check)) {
+        if (!*check) {
+            return true;
+        }
+        fIsLinear = true;
+    }
+    if (fIsLinear) {
+        *check = false;
+        return linearIntersects(span->fPart);
+    }
+    return *check; 
+}
+
+template<typename TCurve>
+bool SkTSpan<TCurve>::linearIntersects(const TCurve& q2) const {
+    // looks like q1 is near-linear
+    int start = 0, end = TCurve::kPointCount - 1;  // 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 sign;
+    for (int n = 0; n < TCurve::kPointCount; ++n) {
+        double test = (q2[n].fY - origY) * adj - (q2[n].fX - origX) * opp;
+        if (precisely_zero(test)) {
+            return true;
+        }
+        if (n == 0) {
+            sign = test;
+            continue;
+        }
+        if (test * sign < 0) {
+            return true;
+        }
+    }
+    return false;
+}
+
+template<typename TCurve>
+bool SkTSpan<TCurve>::splitAt(SkTSpan* work, double t) {
+    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;
+    work->fNext = this;
+    if (fNext) {
+        fNext->fPrev = this;
+    }
+    fBounded = work->fBounded;
+    int count = fBounded.count();
+    for (int index = 0; index < count; ++index) {
+        fBounded[index]->fBounded.push_back() = this;
+    }
+    return true;
+}
+
+template<typename TCurve>
+bool SkTSpan<TCurve>::tightBoundsIntersects(const SkTSpan* span) const {
+    // skew all to an axis
+    SkDVector v2_0 = fPart[TCurve::kPointLast] - fPart[0];
+    bool skewToXAxis = fabs(v2_0.fX) > fabs(v2_0.fY);
+    double ratio = skewToXAxis ? v2_0.fY / v2_0.fX : v2_0.fX / v2_0.fY;
+    TCurve r1 = fPart;
+    if (skewToXAxis) {
+        r1[1].fY -= (fPart[1].fX - r1[0].fX) * ratio;
+        if (TCurve::IsCubic()) {
+            r1[2].fY -= (fPart[2].fX - r1[0].fX) * ratio;
+            r1[3].fY = r1[0].fY;
+        } else {
+            r1[2].fY = r1[0].fY;
+        }
+    } else {
+        r1[1].fX -= (fPart[1].fY - r1[0].fY) * ratio;
+        if (TCurve::IsCubic()) {
+            r1[2].fX -= (fPart[2].fY - r1[0].fY) * ratio;
+            r1[3].fX = r1[0].fX;
+        } else {
+            r1[2].fX = r1[0].fX;
+        }
+    }
+    // compute the tight skewed bounds
+    SkDRect bounds;
+    bounds.setBounds(r1);
+    // see if opposite ends are within range of tight skewed bounds
+    TCurve r2 = span->fPart;
+    for (int i = 0; i < TCurve::kPointCount; i += 2) {
+        if (skewToXAxis) {
+            r2[i].fY -= (r2[i].fX - r1[0].fX) * ratio;
+            if (between(bounds.fTop, r2[i].fY, bounds.fBottom)) {
+                return true;
+            }
+        } else {
+            r2[i].fX -= (r2[i].fY - r1[0].fY) * ratio;
+            if (between(bounds.fLeft, r2[i].fX, bounds.fRight)) {
+                return true;
+            }
+        }
+    }
+    // see if opposite ends are on either side of tight skewed bounds
+    if ((skewToXAxis ? (r2[0].fY - r1[0].fY) * (r2[TCurve::kPointLast].fY - r1[0].fY)
+                        : (r2[0].fX - r1[0].fX) * (r2[TCurve::kPointLast].fX - r1[0].fX)) < 0) {
+        return true;
+    }
+    // compute opposite tight skewed bounds
+    if (skewToXAxis) {
+        r2[1].fY -= (r2[1].fX - r1[0].fX) * ratio;
+        if (TCurve::IsCubic()) {
+            r2[2].fY -= (r2[2].fX - r1[0].fX) * ratio;
+        }
+    } else {
+        r2[1].fX -= (r2[1].fY - r1[0].fY) * ratio;
+        if (TCurve::IsCubic()) {
+            r2[2].fX -= (r2[2].fY - r1[0].fY) * ratio;
+        }
+    }
+    SkDRect sBounds;
+    sBounds.setBounds(r2);
+    // see if tight bounds overlap
+    if (skewToXAxis) {
+        return bounds.fTop <= sBounds.fBottom && sBounds.fTop <= bounds.fBottom;  
+    } else {
+        return bounds.fLeft <= sBounds.fRight && sBounds.fLeft <= bounds.fRight;  
+    }
+}
+
+#if DEBUG_T_SECT
+template<typename TCurve>
+void SkTSpan<TCurve>::validate() const {
+    SkASSERT(fNext == NULL || fNext != fPrev);
+    SkASSERT(fNext == NULL || this == fNext->fPrev);
+    SkASSERT(fBounds.width() || fBounds.height());
+    SkASSERT(fBoundsMax == SkTMax(fBounds.width(), fBounds.height()));
+    SkASSERT(0 <= fStartT);
+    SkASSERT(fEndT <= 1);
+    SkASSERT(fStartT < fEndT);
+    SkASSERT(fBounded.count() > 0);
+    for (int index = 0; index < fBounded.count(); ++index) {
+        const SkTSpan* overlap = fBounded[index];
+        SkASSERT(((fDebugID ^ overlap->fDebugID) & 1) == 1);
+        SkASSERT(overlap->contains(this));
+    }
+}
+#endif
+
+template<typename TCurve>
+SkTSect<TCurve>::SkTSect(const TCurve& c PATH_OPS_DEBUG_PARAMS(int id))
+    : fCurve(c)
+    , fHeap(sizeof(SkTSpan<TCurve>) * 4)
+    , fDeleted(NULL)
+    , fActiveCount(0)
+    PATH_OPS_DEBUG_PARAMS(fDebugID(id))
+    PATH_OPS_DEBUG_PARAMS(fDebugCount(0))
+    PATH_OPS_DEBUG_PARAMS(fDebugAllocatedCount(0))
+{
+    fHead = addOne();
+    fHead->init(c);
+}
+
+template<typename TCurve>
+SkTSpan<TCurve>* SkTSect<TCurve>::addOne() {
+    SkTSpan<TCurve>* result;
+    if (fDeleted) {
+        result = fDeleted;
+        result->reset();
+        fDeleted = result->fNext;
+    } else {
+        result = SkNEW_PLACEMENT(fHeap.allocThrow(sizeof(SkTSpan<TCurve>)), SkTSpan<TCurve>);
+#if DEBUG_T_SECT
+        ++fDebugAllocatedCount;
+#endif
+    }
+    ++fActiveCount; 
+#if DEBUG_T_SECT
+    result->fDebugID = fDebugCount++ * 2 + fDebugID;
+#endif
+    return result;
+}
+
+template<typename TCurve>
+bool SkTSect<TCurve>::binarySearchCoin(const SkTSect& sect2, double tStart, double tStep,
+        double* resultT, double* oppT) {
+    SkTSpan<TCurve> work;
+    double result = work.fStartT = work.fEndT = tStart;
+    SkDPoint last = fCurve.ptAtT(tStart);
+    SkDPoint oppPt;
+    bool flip = false;
+    SkDEBUGCODE(bool down = tStep < 0);
+    const TCurve& 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()) {
+            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[TCurve::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>
+SkTSpan<TCurve>* SkTSect<TCurve>::boundsMax() const {
+    SkTSpan<TCurve>* test = fHead;
+    SkTSpan<TCurve>* largest = fHead;
+    bool largestCoin = largest->fCoinStart.isCoincident() && largest->fCoinEnd.isCoincident();
+    while ((test = test->fNext)) {
+        bool testCoin = test->fCoinStart.isCoincident() || test->fCoinEnd.isCoincident();
+        if ((largestCoin && !testCoin) || (largestCoin == testCoin
+                && (largest->fBoundsMax < test->fBoundsMax
+                || (largest->fCollapsed && !test->fCollapsed)))) {
+            largest = test;
+            largestCoin = testCoin;
+        }
+    }
+    return largestCoin ? NULL : largest;
+}
+
+template<typename TCurve>
+void SkTSect<TCurve>::coincidentCheck(SkTSect* sect2) {
+    SkTSpan<TCurve>* first = fHead;
+    SkTSpan<TCurve>* next;
+    do {
+        int consecutive = 1;
+        SkTSpan<TCurve>* last = first;
+        do {
+            next = last->fNext;
+            if (!next) {
+                break;
+            }
+            if (next->fStartT > last->fEndT) {
+                break;
+            }
+            ++consecutive;
+            last = next;
+        } while (true);
+        if (consecutive < COINCIDENT_SPAN_COUNT) {
+            continue;
+        }
+        setPerp(sect2->fCurve, first, last);
+        // check to see if a range of points are on the curve
+        onCurveCheck(sect2, first, last);
+        SkTSpan<TCurve>* removalCandidate = NULL;
+        if (!first->fCoinStart.isCoincident()) {
+            SkTSpan<TCurve>* firstCoin = first->fNext;
+            removalCandidate = first;
+            first = firstCoin;
+        }
+        if (!first->fCoinStart.isCoincident()) {
+            continue;
+        }
+        if (removalCandidate) {
+            removeSpans(removalCandidate, sect2);
+        }
+        if (!last->fCoinStart.isCoincident()) {
+            continue;
+        }
+        if (!last->fCoinEnd.isCoincident()) {
+            if (--consecutive < COINCIDENT_SPAN_COUNT) {
+                continue;
+            }
+            last = last->fPrev;
+            SkASSERT(last->fCoinStart.isCoincident());
+            SkASSERT(last->fCoinEnd.isCoincident());
+        }
+        SkASSERT(between(0, first->fCoinStart.perpT(), 1) || first->fCoinStart.perpT() == -1);
+        if (first->fCoinStart.perpT() < 0) {
+            first->fCoinStart.setPerp(fCurve, first->fStartT, first->fPart[0], sect2->fCurve);
+        }
+        SkASSERT(between(0, last->fCoinEnd.perpT(), 1) || last->fCoinEnd.perpT() == -1);
+        if (last->fCoinEnd.perpT() < 0) {
+            last->fCoinEnd.setPerp(fCurve, last->fEndT, last->fPart[TCurve::kPointLast],
+                    sect2->fCurve);
+        }
+        SkTSpan<TCurve>* removeMe = first->fNext;
+        while (removeMe != last) {
+            SkTSpan<TCurve>* removeNext = removeMe->fNext;
+            removeSpans(removeMe, sect2);
+            removeMe = removeNext;
+        }
+    } while ((first = next));
+}
+
+template<typename TCurve>
+bool SkTSect<TCurve>::intersects(SkTSpan<TCurve>* span, const SkTSect* opp,
+        const SkTSpan<TCurve>* oppSpan) const {
+    bool check;  // we ignore whether the end points are in common or not
+    if (!span->intersects(oppSpan, &check)) {
+        return false;
+    }
+    if (fActiveCount < COINCIDENT_SPAN_COUNT || opp->fActiveCount < COINCIDENT_SPAN_COUNT) {
+        return true;
+    }
+    return span->tightBoundsIntersects(oppSpan);
+}
+
+template<typename TCurve>
+void SkTSect<TCurve>::onCurveCheck(SkTSect* sect2, SkTSpan<TCurve>* first, SkTSpan<TCurve>* last) {
+    SkTSpan<TCurve>* work = first;
+    first = NULL;
+    do {
+        if (work->fCoinStart.isCoincident()) {
+            if (!first) {
+                first = work;
+            }
+        } else if (first) {
+            break;
+        }
+        if (work == last) {
+            break;
+        }
+        work = work->fNext;
+        SkASSERT(work);
+    } while (true);
+    if (!first) {
+        return;
+    }
+    // march outwards to find limit of coincidence from here to previous and next spans
+    double startT = first->fStartT;
+    double oppT;
+    SkTSpan<TCurve>* prev = first->fPrev;
+    if (prev) {
+        double coinStart;
+        if (binarySearchCoin(*sect2, startT, prev->fStartT - startT, &coinStart, &oppT)) {
+            if (coinStart < startT) {
+                SkASSERT(prev->fStartT < coinStart && coinStart < prev->fEndT);
+                SkTSpan<TCurve>* oppStart = sect2->fHead->find(oppT);
+                if (oppStart->fStartT < oppT && oppT < oppStart->fEndT) {
+                    // split prev at coinStart if needed
+                    SkTSpan<TCurve>* half2 = addOne();
+                    half2->splitAt(prev, coinStart);
+                    half2->initBounds(fCurve);
+                    prev->initBounds(fCurve);
+                    prev->fCoinEnd.markCoincident();
+                    half2->fCoinStart.markCoincident();
+                    half2->fCoinEnd.markCoincident();
+                    // find span containing opposite t, and split that too
+                    SkTSpan<TCurve>* oppHalf = sect2->addOne();
+                    oppHalf->splitAt(oppStart, oppT);
+                    oppHalf->initBounds(sect2->fCurve);
+                    oppStart->initBounds(sect2->fCurve);
+                } else {
+                    SkASSERT(oppStart->fStartT == oppT || oppT == oppStart->fEndT);
+                    first->fStartT = coinStart;
+                    prev->fEndT = coinStart;
+                    first->initBounds(fCurve);
+                    prev->initBounds(fCurve);
+                    first->fCoinStart.markCoincident();
+                    first->fCoinEnd.markCoincident();
+                }
+            }
+        }
+    }
+    if (!work->fCoinEnd.isCoincident()) {
+        if (work->fEndT == 1) {
+            SkDebugf("!");
+        }
+//        SkASSERT(work->fEndT < 1);
+        startT = work->fStartT;
+        double coinEnd;
+        if (binarySearchCoin(*sect2, startT, work->fEndT - startT, &coinEnd, &oppT)) {
+            if (coinEnd > startT) {
+                SkTSpan<TCurve>* oppStart = sect2->fHead->find(oppT);
+                if (oppStart->fStartT < oppT && oppT < oppStart->fEndT) {
+                    SkASSERT(coinEnd < work->fEndT);
+                    // split prev at coinEnd if needed
+                    SkTSpan<TCurve>* half2 = addOne();
+                    half2->splitAt(work, coinEnd);
+                    half2->initBounds(fCurve);
+                    work->initBounds(fCurve);
+                    work->fCoinStart.markCoincident();
+                    work->fCoinEnd.markCoincident();
+                    half2->fCoinStart.markCoincident();
+                    SkTSpan<TCurve>* oppHalf = sect2->addOne();
+                    oppHalf->splitAt(oppStart, oppT);
+                    oppHalf->initBounds(sect2->fCurve);
+                    oppStart->initBounds(sect2->fCurve);
+                } else {
+                    SkASSERT(oppStart->fStartT == oppT || oppT == oppStart->fEndT);
+                    SkTSpan<TCurve>* next = work->fNext;
+                    bool hasNext = next && work->fEndT == next->fStartT;
+                    work->fEndT = coinEnd;
+                    work->initBounds(fCurve);
+                    work->fCoinStart.markCoincident();
+                    work->fCoinEnd.markCoincident();
+                    if (hasNext) { 
+                        next->fStartT = coinEnd;
+                        next->initBounds(fCurve);
+                    }
+                }
+            }
+        }
+    }
+}
+
+template<typename TCurve>
+void SkTSect<TCurve>::recoverCollapsed() {
+    SkTSpan<TCurve>* deleted = fDeleted;
+    while (deleted) {
+        SkTSpan<TCurve>* delNext = deleted->fNext;
+        if (deleted->fCollapsed) {
+            SkTSpan<TCurve>** spanPtr = &fHead;
+            while (*spanPtr && (*spanPtr)->fEndT <= deleted->fStartT) {
+                spanPtr = &(*spanPtr)->fNext;
+            }
+            deleted->fNext = *spanPtr;
+            *spanPtr = deleted;
+        }
+        deleted = delNext;
+    }
+}
+
+template<typename TCurve>
+void SkTSect<TCurve>::removeSpan(SkTSpan<TCurve>* span) {
+    SkTSpan<TCurve>* prev = span->fPrev;
+    SkTSpan<TCurve>* next = span->fNext;
+    if (prev) {
+        prev->fNext = next;
+        if (next) {
+            next->fPrev = prev;
+        }
+    } else {
+        fHead = next;
+        if (next) {
+            next->fPrev = NULL;
+        }
+    }
+    --fActiveCount;
+    span->fNext = fDeleted;
+    fDeleted = span;
+#if DEBUG_T_SECT
+    SkASSERT(!span->fDebugDeleted);
+    span->fDebugDeleted = true;
+#endif
+}
+
+template<typename TCurve>
+void SkTSect<TCurve>::removeOne(const SkTSpan<TCurve>* test, SkTSpan<TCurve>* span) {
+    int last = span->fBounded.count() - 1;
+    for (int index = 0; index <= last; ++index) {
+        if (span->fBounded[index] == test) {
+            span->fBounded.removeShuffle(index);
+            if (!last) {
+                removeSpan(span);
+            }
+            return;
+        }
+    }
+}
+
+template<typename TCurve>
+void SkTSect<TCurve>::removeSpans(SkTSpan<TCurve>* span, SkTSect<TCurve>* opp) {
+    int count = span->fBounded.count();
+    for (int index = 0; index < count; ++index) {
+        SkTSpan<TCurve>* bounded = span->fBounded[0];
+        removeOne(bounded, span);  // shuffles last into position 0
+        opp->removeOne(span, bounded);
+    }
+}
+
+template<typename TCurve>
+void SkTSect<TCurve>::setPerp(const TCurve& opp, SkTSpan<TCurve>* first, SkTSpan<TCurve>* last) {
+    SkTSpan<TCurve>* work = first;
+    if (!work->fHasPerp) {
+        work->fCoinStart.setPerp(fCurve, work->fStartT, work->fPart[0], opp);
+    }
+    do {
+        if (!work->fHasPerp) {
+            work->fCoinEnd.setPerp(fCurve, work->fEndT, work->fPart[TCurve::kPointLast], opp);
+            work->fHasPerp = true;
+        }
+        if (work == last) {
+            break;
+        }
+        SkTSpan<TCurve>* last = work;
+        work = work->fNext;
+        SkASSERT(work);
+        if (!work->fHasPerp) {
+            work->fCoinStart = last->fCoinEnd;
+        }
+    } while (true);
+}
+
+template<typename TCurve>
+const SkTSpan<TCurve>* SkTSect<TCurve>::tail() const {
+    const SkTSpan<TCurve>* result = fHead;
+    const SkTSpan<TCurve>* 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>
+void SkTSect<TCurve>::trim(SkTSpan<TCurve>* span, SkTSect* opp) {
+    span->initBounds(fCurve);
+    int count = span->fBounded.count();
+    for (int index = 0; index < count; ) {
+        SkTSpan<TCurve>* test = span->fBounded[index];
+        bool sects = intersects(span, opp, test);
+        if (sects) {
+            ++index;
+        } else {
+            removeOne(test, span);
+            opp->removeOne(span, test);
+            --count;
+        }
+    }
+}
+
+#if DEBUG_T_SECT
+template<typename TCurve>
+void SkTSect<TCurve>::validate() const {
+    int count = 0;
+    if (fHead) {
+        const SkTSpan<TCurve>* span = fHead;
+        SkASSERT(!span->fPrev);
+        double last = 0;
+        do {
+            span->validate();
+            SkASSERT(span->fStartT >= last);
+            last = span->fEndT;
+            ++count;
+        } while ((span = span->fNext) != NULL);
+    }
+    SkASSERT(count == fActiveCount);
+    SkASSERT(fActiveCount <= fDebugAllocatedCount);
+    int deletedCount = 0;
+    const SkTSpan<TCurve>* deleted = fDeleted;
+    while (deleted) {
+        ++deletedCount;
+        deleted = deleted->fNext;
+    }
+    SkASSERT(fActiveCount + deletedCount == fDebugAllocatedCount);
+}
+#endif
+
+template<typename TCurve>
+int SkTSect<TCurve>::EndsEqual(const SkTSect* sect1, const SkTSect* sect2,
+        SkIntersections* intersections) {
+    int zeroOneSet = 0;
+    // check for zero
+    if (sect1->fCurve[0].approximatelyEqual(sect2->fCurve[0])) {
+        zeroOneSet |= kZeroS1Set | kZeroS2Set;
+        if (sect1->fCurve[0] != sect2->fCurve[0]) {
+            intersections->insertNear(0, 0, sect1->fCurve[0], sect2->fCurve[0]);
+        } else {
+            intersections->insert(0, 0, sect1->fCurve[0]);
+        }
+    } 
+    if (sect1->fCurve[0].approximatelyEqual(sect2->fCurve[TCurve::kPointLast])) {
+        zeroOneSet |= kZeroS1Set | kOneS2Set;
+        if (sect1->fCurve[0] != sect2->fCurve[TCurve::kPointLast]) {
+            intersections->insertNear(0, 1, sect1->fCurve[0], sect2->fCurve[TCurve::kPointLast]);
+        } else {
+            intersections->insert(0, 1, sect1->fCurve[0]);
+        }
+    } 
+    // check for one
+    if (sect1->fCurve[TCurve::kPointLast].approximatelyEqual(sect2->fCurve[0])) {
+        zeroOneSet |= kOneS1Set | kZeroS2Set;
+        if (sect1->fCurve[TCurve::kPointLast] != sect2->fCurve[0]) {
+            intersections->insertNear(1, 0, sect1->fCurve[TCurve::kPointLast], sect2->fCurve[0]);
+        } else {
+            intersections->insert(1, 0, sect1->fCurve[TCurve::kPointLast]);
+        }
+    } 
+    if (sect1->fCurve[TCurve::kPointLast].approximatelyEqual(sect2->fCurve[TCurve::kPointLast])) {
+        zeroOneSet |= kOneS1Set | kOneS2Set;
+        if (sect1->fCurve[TCurve::kPointLast] != sect2->fCurve[TCurve::kPointLast]) {
+            intersections->insertNear(1, 1, sect1->fCurve[TCurve::kPointLast],
+                    sect2->fCurve[TCurve::kPointLast]);
+        } else {
+            intersections->insert(1, 1, sect1->fCurve[TCurve::kPointLast]);
+        }
+    }
+    return zeroOneSet;
+}
+
+template<typename TCurve>
+struct SkClosestRecord {
+    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>* span1, const SkTSpan<TCurve>* span2,
+            int c1Index, int c2Index) {
+        const TCurve& c1 = span1->part();
+        const TCurve& 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 = 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>* fC1Span;
+    const SkTSpan<TCurve>* fC2Span;
+    double fC1StartT;
+    double fC1EndT;
+    double fC2StartT;
+    double fC2EndT;
+    double fClosest;
+    int fC1Index;
+    int fC2Index;
+};
+
+template<typename TCurve>
+struct SkClosestSect {
+    SkClosestSect()
+        : fUsed(0) {
+        fClosest.push_back().reset();
+    }
+
+    void find(const SkTSpan<TCurve>* span1, const SkTSpan<TCurve>* span2) {
+        SkClosestRecord<TCurve>* record = &fClosest[fUsed];
+        record->findEnd(span1, span2, 0, 0);
+        record->findEnd(span1, span2, 0, TCurve::kPointLast);
+        record->findEnd(span1, span2, TCurve::kPointLast, 0);
+        record->findEnd(span1, span2, TCurve::kPointLast, TCurve::kPointLast);
+        if (record->fClosest == FLT_MAX) {
+            return;
+        }
+        for (int index = 0; index < fUsed; ++index) {
+            SkClosestRecord<TCurve>* test = &fClosest[index];
+            if (test->matesWith(*record)) {
+                if (test->fClosest > record->fClosest) {
+                    test->merge(*record);
+                }
+                test->update(*record);
+                record->reset();
+                return;
+            }
+        }
+        ++fUsed;
+        fClosest.push_back().reset();
+    }
+
+    void finish(SkIntersections* intersections) const {
+        for (int index = 0; index < fUsed; ++index) {
+            const SkClosestRecord<TCurve>& test = fClosest[index];
+            test.addIntersection(intersections);
+        }
+    }
+
+    // this is oversized by one so that an extra record can merge into final one
+    SkSTArray<TCurve::kMaxIntersections + 1, SkClosestRecord<TCurve>, true> fClosest;
+    int fUsed;
+};
+
+// returns true if the rect is too small to consider
+template<typename TCurve>
+void SkTSect<TCurve>::BinarySearch(SkTSect* sect1, SkTSect* sect2, SkIntersections* intersections) {
+    intersections->reset();
+    intersections->setMax(TCurve::kMaxIntersections);
+    SkTSpan<TCurve>* span1 = sect1->fHead;
+    SkTSpan<TCurve>* span2 = sect2->fHead;
+    bool check;
+    if (!span1->intersects(span2, &check)) {
+        return;
+    }
+    if (check) {
+        (void) EndsEqual(sect1, sect2, intersections);
+        return;
+    }
+    span1->fBounded.push_back() = span2;
+    span2->fBounded.push_back() = span1;
+    do {
+        // find the largest bounds
+        SkTSpan<TCurve>* largest1 = sect1->boundsMax();
+        if (!largest1) {
+            break;
+        }
+        SkTSpan<TCurve>* largest2 = sect2->boundsMax();
+        bool split1 = !largest2 || (largest1 && (largest1->fBoundsMax > largest2->fBoundsMax
+            || (!largest1->fCollapsed && largest2->fCollapsed)));
+        // split it
+        SkTSect* splitSect = split1 ? sect1 : sect2;
+        SkTSpan<TCurve>* half1 = split1 ? largest1 : largest2;
+        SkASSERT(half1);
+        if (half1->fCollapsed) {
+            break;
+        }
+        // trim parts that don't intersect the opposite
+        SkTSpan<TCurve>* half2 = splitSect->addOne();
+        SkTSect* unsplitSect = split1 ? sect2 : sect1;
+        if (!half2->split(half1)) {
+            break;
+        }
+        splitSect->trim(half1, unsplitSect);
+        splitSect->trim(half2, unsplitSect);
+        // 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);
+        }
+#if DEBUG_T_SECT
+        sect1->validate();
+        sect2->validate();
+#endif
+#if DEBUG_T_SECT_DUMP > 1
+        sect1->dumpBoth(*sect2);
+#endif
+        if (!sect1->fHead || !sect2->fHead) {
+            return;
+        }
+    } while (true);
+    if (sect1->fActiveCount >= 2 && sect2->fActiveCount >= 2) {
+        // check for coincidence
+        SkTSpan<TCurve>* first = sect1->fHead;
+        do {
+            if (!first->fCoinStart.isCoincident()) {
+                continue;
+            }
+            int spanCount = 1;
+            SkTSpan<TCurve>* last = first;
+            while (last->fCoinEnd.isCoincident()) {
+                SkTSpan<TCurve>* next = last->fNext;
+                if (!next || !next->fCoinEnd.isCoincident()) {
+                    break;
+                }
+                last = next;
+                ++spanCount;
+            }
+            if (spanCount < 2) {
+                first = last;
+                continue;
+            }
+            int index = intersections->insertCoincident(first->fStartT, first->fCoinStart.perpT(),
+                    first->fPart[0]);
+            if (intersections->insertCoincident(last->fEndT, last->fCoinEnd.perpT(),
+                    last->fPart[TCurve::kPointLast]) < 0) {
+                intersections->clearCoincidence(index);
+            }
+        } while ((first = first->fNext));
+    }
+    int zeroOneSet = EndsEqual(sect1, sect2, intersections);
+    sect1->recoverCollapsed();
+    sect2->recoverCollapsed();
+    SkTSpan<TCurve>* result1 = sect1->fHead;
+    // check heads and tails for zero and ones and insert them if we haven't already done so
+    const SkTSpan<TCurve>* head1 = result1;
+    if (!(zeroOneSet & kZeroS1Set) && approximately_less_than_zero(head1->fStartT)) {
+        const SkDPoint& start1 = sect1->fCurve[0];
+        double t = head1->closestBoundedT(start1);
+        if (sect2->fCurve.ptAtT(t).approximatelyEqual(start1)) {
+            intersections->insert(0, t, start1);
+        }
+    }
+    const SkTSpan<TCurve>* head2 = sect2->fHead;
+    if (!(zeroOneSet & kZeroS2Set) && approximately_less_than_zero(head2->fStartT)) {
+        const SkDPoint& start2 = sect2->fCurve[0];
+        double t = head2->closestBoundedT(start2);
+        if (sect1->fCurve.ptAtT(t).approximatelyEqual(start2)) {
+            intersections->insert(t, 0, start2);
+        }
+    }
+    const SkTSpan<TCurve>* tail1 = sect1->tail();
+    if (!(zeroOneSet & kOneS1Set) && approximately_greater_than_one(tail1->fEndT)) {
+        const SkDPoint& end1 = sect1->fCurve[TCurve::kPointLast];
+        double t = tail1->closestBoundedT(end1);
+        if (sect2->fCurve.ptAtT(t).approximatelyEqual(end1)) {
+            intersections->insert(1, t, end1);
+        }
+    }
+    const SkTSpan<TCurve>* tail2 = sect2->tail();
+    if (!(zeroOneSet & kOneS2Set) && approximately_greater_than_one(tail2->fEndT)) {
+        const SkDPoint& end2 = sect2->fCurve[TCurve::kPointLast];
+        double t = tail2->closestBoundedT(end2);
+        if (sect1->fCurve.ptAtT(t).approximatelyEqual(end2)) {
+            intersections->insert(t, 1, end2);
+        }
+    }
+    SkClosestSect<TCurve> closest;
+    do {
+        while (result1 && result1->fCoinStart.isCoincident() && result1->fCoinEnd.isCoincident()) {
+            result1 = result1->fNext;
+        }
+        if (!result1) {
+            break;
+        }
+        SkTSpan<TCurve>* result2 = sect2->fHead;
+        while (result2) {
+            closest.find(result1, result2);
+            result2 = result2->fNext;
+        }
+        
+    } while ((result1 = result1->fNext));
+    closest.finish(intersections);
+}