new files for pathops geometric intersection

There's no gyp references to these new files,
so this should only have the effect of reducing
the size of the commit that turns this code on.

TBR=

Review URL: https://codereview.chromium.org/853223002

1 files changed, 1211 insertions, 0 deletions

diff --git a/src/pathops/SkPathOpsTSect.h b/src/pathops/SkPathOpsTSect.h
new file mode 100644
index 0000000000..4e7d3b1795
--- /dev/null
+++ b/src/pathops/SkPathOpsTSect.h
@@ -0,0 +1,1211 @@
+/*
+ * 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);
+}