new files for pathops geometric intersection

src/pathops/SkPathOpsCubicSect.h

Index: src/pathops/SkPathOpsCubicSect.h
diff --git a/src/pathops/SkPathOpsCubicSect.h b/src/pathops/SkPathOpsCubicSect.h
new file mode 100644
index 0000000000000000000000000000000000000000..d7634449b6ce2031d4bbf66bba083f4c6c253381
--- /dev/null
+++ b/src/pathops/SkPathOpsCubicSect.h
@@ -0,0 +1,175 @@
+/*
+ * Copyright 2014 Google Inc.
+ *
+ * Use of this source code is governed by a BSD-style license that can be
+ * found in the LICENSE file.
+ */
+#ifndef SkCubicSpan_DEFINE
+#define SkCubicSpan_DEFINE
+
+#include "SkChunkAlloc.h"
+#include "SkPathOpsRect.h"
+#include "SkPathOpsCubic.h"
+#include "SkTArray.h"
+
+class SkIntersections;
+
+class SkCubicCoincident {
+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 SkDCubic& cubic1, double t, const SkDPoint& qPt, const SkDCubic& cubic2);
+
+private:
+    SkDPoint fPerpPt;
+    double fPerpT;  // perpendicular intersection on opposite Cubic
+    bool fCoincident;
+};
+
+class SkCubicSect;  // used only by debug id
+
+class SkCubicSpan {
+public:
+    void init(const SkDCubic& Cubic);
+    void initBounds(const SkDCubic& Cubic);
+
+    bool contains(double t) const {
+        return !! const_cast<SkCubicSpan*>(this)->innerFind(t);
+    }
+
+    bool contains(const SkCubicSpan* span) const;
+
+    SkCubicSpan* find(double t) {
+        SkCubicSpan* result = innerFind(t);
+        SkASSERT(result);
+        return result;
+    }
+
+    bool intersects(const SkCubicSpan* span) const;
+
+    const SkCubicSpan* next() const {
+        return fNext;
+    }
+
+    void reset() {
+        fBounded.reset();
+    }
+
+    bool split(SkCubicSpan* work) {
+        return splitAt(work, (work->fStartT + work->fEndT) * 0.5);
+    }
+
+    bool splitAt(SkCubicSpan* work, double t);
+    bool tightBoundsIntersects(const SkCubicSpan* span) const;
+
+    // implementation is for testing only
+    void dump() const;
+
+private:
+    bool hullIntersects(const SkDCubic& ) const;
+    SkCubicSpan* innerFind(double t);
+    bool linearIntersects(const SkDCubic& ) const;
+
+    // implementation is for testing only
+#if DEBUG_BINARY_CUBIC
+    int debugID(const SkCubicSect* ) const { return fDebugID; }
+#else
+    int debugID(const SkCubicSect* ) const;
+#endif
+    void dump(const SkCubicSect* ) const;
+    void dumpID(const SkCubicSect* ) const;
+
+#if DEBUG_BINARY_CUBIC
+    void validate() const;
+#endif
+
+    SkDCubic fPart;
+    SkCubicCoincident fCoinStart;
+    SkCubicCoincident fCoinEnd;
+    SkSTArray<4, SkCubicSpan*, true> fBounded;
+    SkCubicSpan* fPrev;
+    SkCubicSpan* fNext;
+    SkDRect fBounds;
+    double fStartT;
+    double fEndT;
+    double fBoundsMax;
+    bool fCollapsed;
+    bool fHasPerp;
+    mutable bool fIsLinear;
+#if DEBUG_BINARY_CUBIC
+    int fDebugID;
+    bool fDebugDeleted;
+#endif
+    friend class SkCubicSect;
+};
+
+class SkCubicSect {
+public:
+    SkCubicSect(const SkDCubic& Cubic PATH_OPS_DEBUG_PARAMS(int id));
+    static void BinarySearch(SkCubicSect* sect1, SkCubicSect* sect2, SkIntersections* intersections);
+
+    // for testing only
+    void dumpCubics() const;
+private:
+    SkCubicSpan* addOne();
+    bool binarySearchCoin(const SkCubicSect& , double tStart, double tStep, double* t,
+            double* oppT);
+    SkCubicSpan* boundsMax() const;
+    void coincidentCheck(SkCubicSect* sect2);
+    bool intersects(const SkCubicSpan* span, const SkCubicSect* opp, const SkCubicSpan* oppSpan) const;
+    void onCurveCheck(SkCubicSect* sect2, SkCubicSpan* first, SkCubicSpan* last);
+    void recoverCollapsed();
+    void removeSpan(SkCubicSpan* span);
+    void removeOne(const SkCubicSpan* test, SkCubicSpan* span);
+    void removeSpans(SkCubicSpan* span, SkCubicSect* opp);
+    void setPerp(const SkDCubic& opp, SkCubicSpan* first, SkCubicSpan* last);
+    void trim(SkCubicSpan* span, SkCubicSect* opp);
+
+    // for testing only
+    void dump() const;
+    void dumpBoth(const SkCubicSect& opp) const;
+    void dumpBoth(const SkCubicSect* opp) const;
+
+#if DEBUG_BINARY_CUBIC
+    int debugID() const { return fDebugID; }
+    void validate() const;
+#else
+    int debugID() const { return 0; }
+#endif
+    const SkDCubic& fCubic;
+    SkChunkAlloc fHeap;
+    SkCubicSpan* fHead;
+    SkCubicSpan* fDeleted;
+    int fActiveCount;
+#if DEBUG_BINARY_CUBIC
+    int fDebugID;
+    int fDebugCount;
+    int fDebugAllocatedCount;
+#endif
+    friend class SkCubicSpan;  // only used by debug id
+};
+
+#endif