Add implementation of path ops

src/pathops/SkOpSegment.h

Index: src/pathops/SkOpSegment.h
===================================================================
--- src/pathops/SkOpSegment.h	(revision 0)
+++ src/pathops/SkOpSegment.h	(revision 0)
@@ -0,0 +1,410 @@
+/*
+ * Copyright 2012 Google Inc.
+ *
+ * Use of this source code is governed by a BSD-style license that can be
+ * found in the LICENSE file.
+ */
+#ifndef SkOpSegment_DEFINE
+#define SkOpSegment_DEFINE
+
+#include "SkOpAngle.h"
+#include "SkPathOpsBounds.h"
+#include "SkPathOpsCurve.h"
+#include "SkTDArray.h"
+
+class SkPathWriter;
+
+class SkOpSegment {
+public:
+    SkOpSegment() {
+#if DEBUG_DUMP
+        fID = ++gSegmentID;
+#endif
+    }
+
+    bool operator<(const SkOpSegment& rh) const {
+        return fBounds.fTop < rh.fBounds.fTop;
+    }
+
+    const SkPathOpsBounds& bounds() const {
+        return fBounds;
+    }
+
+    // OPTIMIZE
+    // when the edges are initially walked, they don't automatically get the prior and next
+    // edges assigned to positions t=0 and t=1. Doing that would remove the need for this check,
+    // and would additionally remove the need for similar checks in condition edges. It would
+    // also allow intersection code to assume end of segment intersections (maybe?)
+    bool complete() const {
+        int count = fTs.count();
+        return count > 1 && fTs[0].fT == 0 && fTs[--count].fT == 1;
+    }
+
+    bool done() const {
+        SkASSERT(fDoneSpans <= fTs.count());
+        return fDoneSpans == fTs.count();
+    }
+
+    bool done(int min) const {
+        return fTs[min].fDone;
+    }
+
+    bool done(const SkOpAngle* angle) const {
+        return done(SkMin32(angle->start(), angle->end()));
+    }
+
+    SkVector dxdy(int index) const {
+        return (*CurveSlopeAtT[fVerb])(fPts, fTs[index].fT);
+    }
+
+    SkScalar dy(int index) const {
+        return dxdy(index).fY;
+    }
+
+    bool intersected() const {
+        return fTs.count() > 0;
+    }
+
+    bool isCanceled(int tIndex) const {
+        return fTs[tIndex].fWindValue == 0 && fTs[tIndex].fOppValue == 0;
+    }
+
+    bool isConnected(int startIndex, int endIndex) const {
+        return fTs[startIndex].fWindSum != SK_MinS32 || fTs[endIndex].fWindSum != SK_MinS32;
+    }
+
+    bool isHorizontal() const {
+        return fBounds.fTop == fBounds.fBottom;
+    }
+
+    bool isVertical() const {
+        return fBounds.fLeft == fBounds.fRight;
+    }
+
+    bool isVertical(int start, int end) const {
+        return (*CurveIsVertical[fVerb])(fPts, start, end);
+    }
+
+    bool operand() const {
+        return fOperand;
+    }
+
+    int oppSign(const SkOpAngle* angle) const {
+        SkASSERT(angle->segment() == this);
+        return oppSign(angle->start(), angle->end());
+    }
+
+    int oppSign(int startIndex, int endIndex) const {
+        int result = startIndex < endIndex ? -fTs[startIndex].fOppValue : fTs[endIndex].fOppValue;
+#if DEBUG_WIND_BUMP
+        SkDebugf("%s oppSign=%d\n", __FUNCTION__, result);
+#endif
+        return result;
+    }
+
+    int oppSum(int tIndex) const {
+        return fTs[tIndex].fOppSum;
+    }
+
+    int oppSum(const SkOpAngle* angle) const {
+        int lesser = SkMin32(angle->start(), angle->end());
+        return fTs[lesser].fOppSum;
+    }
+
+    int oppValue(int tIndex) const {
+        return fTs[tIndex].fOppValue;
+    }
+
+    int oppValue(const SkOpAngle* angle) const {
+        int lesser = SkMin32(angle->start(), angle->end());
+        return fTs[lesser].fOppValue;
+    }
+
+    const SkPoint* pts() const {
+        return fPts;
+    }
+
+    void reset() {
+        init(NULL, (SkPath::Verb) -1, false, false);
+        fBounds.set(SK_ScalarMax, SK_ScalarMax, SK_ScalarMax, SK_ScalarMax);
+        fTs.reset();
+    }
+
+    void setOppXor(bool isOppXor) {
+        fOppXor = isOppXor;
+    }
+
+    void setSpanT(int index, double t) {
+        SkOpSpan& span = fTs[index];
+        span.fT = t;
+        span.fOther->fTs[span.fOtherIndex].fOtherT = t;
+    }
+
+    void setUpWinding(int index, int endIndex, int& maxWinding, int& sumWinding) {
+        int deltaSum = spanSign(index, endIndex);
+        maxWinding = sumWinding;
+        sumWinding = sumWinding -= deltaSum;
+    }
+
+    // OPTIMIZATION: mark as debugging only if used solely by tests
+    const SkOpSpan& span(int tIndex) const {
+        return fTs[tIndex];
+    }
+
+    int spanSign(const SkOpAngle* angle) const {
+        SkASSERT(angle->segment() == this);
+        return spanSign(angle->start(), angle->end());
+    }
+
+    int spanSign(int startIndex, int endIndex) const {
+        int result = startIndex < endIndex ? -fTs[startIndex].fWindValue : fTs[endIndex].fWindValue;
+#if DEBUG_WIND_BUMP
+        SkDebugf("%s spanSign=%d\n", __FUNCTION__, result);
+#endif
+        return result;
+    }
+
+    // OPTIMIZATION: mark as debugging only if used solely by tests
+    double t(int tIndex) const {
+        return fTs[tIndex].fT;
+    }
+
+    double tAtMid(int start, int end, double mid) const {
+        return fTs[start].fT * (1 - mid) + fTs[end].fT * mid;
+    }
+
+    bool unsortable(int index) const {
+        return fTs[index].fUnsortableStart || fTs[index].fUnsortableEnd;
+    }
+
+    void updatePts(const SkPoint pts[]) {
+        fPts = pts;
+    }
+    
+    SkPath::Verb verb() const {
+        return fVerb;
+    }
+
+    int windSum(int tIndex) const {
+        return fTs[tIndex].fWindSum;
+    }
+
+    int windValue(int tIndex) const {
+        return fTs[tIndex].fWindValue;
+    }
+
+    SkScalar xAtT(int index) const {
+        return xAtT(&fTs[index]);
+    }
+
+    SkScalar xAtT(const SkOpSpan* span) const {
+        return xyAtT(span).fX;
+    }
+
+    const SkPoint& xyAtT(const SkOpSpan* span) const {
+        return span->fPt;
+    }
+
+    // used only by right angle winding finding
+    SkPoint xyAtT(double mid) const {
+        return (*CurvePointAtT[fVerb])(fPts, mid);
+    }
+
+    const SkPoint& xyAtT(int index) const {
+        return xyAtT(&fTs[index]);
+    }
+    
+    SkScalar yAtT(int index) const {
+        return yAtT(&fTs[index]);
+    }
+
+    SkScalar yAtT(const SkOpSpan* span) const {
+        return xyAtT(span).fY;
+    }
+
+    bool activeAngle(int index, int& done, SkTDArray<SkOpAngle>& angles);
+    bool activeAngleOther(int index, int& done, SkTDArray<SkOpAngle>& angles);
+    bool activeAngleInner(int index, int& done, SkTDArray<SkOpAngle>& angles);
+    SkPoint activeLeftTop(bool onlySortable, int* firstT) const;
+    bool activeOp(int index, int endIndex, int xorMiMask, int xorSuMask, SkPathOp op);
+    bool activeOp(int xorMiMask, int xorSuMask, int index, int endIndex, SkPathOp op,
+                  int& sumMiWinding, int& sumSuWinding, int& maxWinding, int& sumWinding,
+                  int& oppMaxWinding, int& oppSumWinding);
+    bool activeWinding(int index, int endIndex);
+    bool activeWinding(int index, int endIndex, int& maxWinding, int& sumWinding);
+    void addAngle(SkTDArray<SkOpAngle>& angles, int start, int end) const;
+    void addCancelOutsides(double tStart, double oStart, SkOpSegment& other, double oEnd);
+    void addCoinOutsides(const SkTDArray<double>& outsideTs, SkOpSegment& other, double oEnd);
+    void addCubic(const SkPoint pts[4], bool operand, bool evenOdd);
+    void addCurveTo(int start, int end, SkPathWriter& path, bool active) const;
+    void addLine(const SkPoint pts[2], bool operand, bool evenOdd);
+    void addOtherT(int index, double otherT, int otherIndex);
+    void addQuad(const SkPoint pts[3], bool operand, bool evenOdd);
+    int addSelfT(SkOpSegment* other, const SkPoint& pt, double newT);
+    int addT(SkOpSegment* other, const SkPoint& pt, double newT);
+    void addTCancel(double startT, double endT, SkOpSegment& other, double oStartT, double oEndT);
+    void addTCoincident(double startT, double endT, SkOpSegment& other, double oStartT,
+                        double oEndT);
+    void addTPair(double t, SkOpSegment& other, double otherT, bool borrowWind, const SkPoint& pt);
+    void addTwoAngles(int start, int end, SkTDArray<SkOpAngle>& angles) const;
+
+    int addUnsortableT(SkOpSegment* other, bool start, const SkPoint& pt, double newT);
+    int advanceCoincidentOther(const SkOpSpan* test, double oEndT, int& oIndex);
+    int advanceCoincidentThis(const SkOpSpan* oTest, bool opp, int index);
+    bool betweenTs(int lesser, double testT, int greater);
+    void buildAngles(int index, SkTDArray<SkOpAngle>& angles, bool includeOpp) const;
+    void buildAnglesInner(int index, SkTDArray<SkOpAngle>& angles) const;
+    int bumpCoincidentThis(const SkOpSpan* oTest, bool opp, int index,
+                           SkTDArray<double>& outsideTs);
+    int bumpCoincidentOther(const SkOpSpan* test, double oEndT, int& oIndex,
+                            SkTDArray<double>& oOutsideTs);
+    bool bumpSpan(SkOpSpan* span, int windDelta, int oppDelta);
+    bool clockwise(int tStart, int tEnd) const;
+    int computeSum(int startIndex, int endIndex, bool binary);
+    int crossedSpanY(const SkPoint& basePt, SkScalar& bestY, double& hitT, bool& hitSomething,
+                     double mid, bool opp, bool current) const;
+    void decrementSpan(SkOpSpan* span);
+    bool equalPoints(int greaterTIndex, int lesserTIndex);
+    SkOpSegment* findNextOp(SkTDArray<SkOpSpan*>& chase, int& nextStart, int& nextEnd,
+                            bool& unsortable, SkPathOp op, const int xorMiMask,
+                            const int xorSuMask);
+    int findStartingEdge(SkTDArray<SkOpAngle*>& sorted, int start, int end);
+    SkOpSegment* findNextWinding(SkTDArray<SkOpSpan*>& chase, int& nextStart, int& nextEnd,
+                                 bool& unsortable);
+    SkOpSegment* findNextXor(int& nextStart, int& nextEnd, bool& unsortable);
+    void findTooCloseToCall();
+    SkOpSegment* findTop(int& tIndex, int& endIndex, bool& unsortable, bool onlySortable);
+    void fixOtherTIndex();
+    void init(const SkPoint pts[], SkPath::Verb verb, bool operand, bool evenOdd);
+    void initWinding(int start, int end);
+    void initWinding(int start, int end, int winding, int oppWinding);
+    void initWinding(int start, int end, double tHit, int winding, SkScalar hitDx, int oppWind,
+            SkScalar hitOppDx);
+    bool isLinear(int start, int end) const;
+    bool isMissing(double startT) const;
+    bool isSimple(int end) const;
+    SkOpSpan* markAndChaseDone(const SkOpAngle* angle, int winding);
+    SkOpSpan* markAndChaseDone(int index, int endIndex, int winding);
+    SkOpSpan* markAndChaseDoneBinary(const SkOpAngle* angle, int winding, int oppWinding);
+    SkOpSpan* markAndChaseDoneBinary(int index, int endIndex);
+    SkOpSpan* markAndChaseDoneUnary(int index, int endIndex);
+    SkOpSpan* markAndChaseDoneUnary(const SkOpAngle* angle, int winding);
+    SkOpSpan* markAndChaseWinding(const SkOpAngle* angle, const int winding);
+    SkOpSpan* markAndChaseWinding(int index, int endIndex, int winding, int oppWinding);
+    SkOpSpan* markAndChaseWinding(const SkOpAngle* angle, int winding, int oppWinding);
+    SkOpSpan* markAngle(int maxWinding, int sumWinding, bool activeAngle, const SkOpAngle* angle);
+    SkOpSpan* markAngle(int maxWinding, int sumWinding, int oppMaxWinding, int oppSumWinding,
+                        bool activeAngle, const SkOpAngle* angle);
+    void markDone(int index, int winding);
+    void markDoneBinary(int index, int winding, int oppWinding);
+    void markDoneBinary(int index);
+    void markDoneUnary(int index, int winding);
+    void markDoneUnary(int index);
+    void markOneDone(const char* funName, int tIndex, int winding);
+    void markOneDoneBinary(const char* funName, int tIndex);
+    void markOneDoneBinary(const char* funName, int tIndex, int winding, int oppWinding);
+    void markOneDoneUnary(const char* funName, int tIndex);
+    void markOneDoneUnary(const char* funName, int tIndex, int winding);
+    SkOpSpan* markOneWinding(const char* funName, int tIndex, int winding);
+    SkOpSpan* markOneWinding(const char* funName, int tIndex, int winding, int oppWinding);
+    void markUnsortable(int start, int end);
+    void markWinding(int index, int winding);
+    void markWinding(int index, int winding, int oppWinding);
+    void matchWindingValue(int tIndex, double t, bool borrowWind);
+
+    bool monotonicInY(int tStart, int tEnd) const;
+    bool moreHorizontal(int index, int endIndex, bool& unsortable) const;
+    bool multipleSpans(int end) const;
+    bool nextCandidate(int& start, int& end) const;
+    SkOpSegment* nextChase(int& index, const int step, int& min, SkOpSpan*& last);
+    int nextExactSpan(int from, int step) const;
+    int nextSpan(int from, int step) const;
+    bool serpentine(int tStart, int tEnd) const;
+    void setUpWindings(int index, int endIndex, int& sumMiWinding, int& sumSuWinding,
+            int& maxWinding, int& sumWinding, int& oppMaxWinding, int& oppSumWinding);
+    static bool SortAngles(SkTDArray<SkOpAngle>& angles, SkTDArray<SkOpAngle*>& angleList);
+    void subDivide(int start, int end, SkPoint edge[4]) const;
+    void subDivideBounds(int start, int end, SkPathOpsBounds& bounds) const;
+    bool tiny(const SkOpAngle* angle) const;
+    static void TrackOutside(SkTDArray<double>& outsideTs, double end, double start);
+    void undoneSpan(int& start, int& end);
+    int updateOppWinding(int index, int endIndex) const;
+    int updateOppWinding(const SkOpAngle* angle) const;
+    int updateOppWindingReverse(const SkOpAngle* angle) const;
+    int updateWinding(int index, int endIndex) const;
+    int updateWinding(const SkOpAngle* angle) const;
+    int updateWindingReverse(const SkOpAngle* angle) const;
+    static bool UseInnerWinding(int outerWinding, int innerWinding);
+    SkOpSpan* verifyOneWinding(const char* funName, int tIndex);
+    SkOpSpan* verifyOneWindingU(const char* funName, int tIndex);
+    int windingAtT(double tHit, int tIndex, bool crossOpp, SkScalar& dx) const;
+    int windSum(const SkOpAngle* angle) const;
+    int windValue(const SkOpAngle* angle) const;
+    int windValueAt(double t) const;
+    void zeroCoincidentOpp(SkOpSpan* oTest, int index);
+    void zeroCoincidentOther(SkOpSpan* test, const double tRatio, const double oEndT, int oIndex);
+    void zeroSpan(SkOpSpan* span);
+
+#if DEBUG_WINDING
+    static char as_digit(int value) {
+        return value < 0 ? '?' : value <= 9 ? '0' + value : '+';
+    }
+#endif
+
+#if DEBUG_DUMP
+    int debugID() const {
+        return fID;
+    }
+#endif
+
+#if DEBUG_SWAP_TOP
+    bool controlsContainedByEnds(int tStart, int tEnd) const;
+#endif
+#if DEBUG_CONCIDENT
+     void debugAddTPair(double t, const SkOpSegment& other, double otherT) const;
+#endif
+#if DEBUG_ACTIVE_SPANS
+    void debugShowActiveSpans() const;
+#endif
+#if DEBUG_MARK_DONE || DEBUG_UNSORTABLE
+    void debugShowNewWinding(const char* fun, const SkOpSpan& span, int winding);
+    void debugShowNewWinding(const char* fun, const SkOpSpan& span, int winding, int oppWinding);
+#endif
+#if DEBUG_SORT || DEBUG_SWAP_TOP
+    void debugShowSort(const char* fun, const SkTDArray<SkOpAngle*>& angles, int first,
+            const int contourWinding, const int oppContourWinding) const;
+    void debugShowSort(const char* fun, const SkTDArray<SkOpAngle*>& angles, int first);
+#endif
+#if DEBUG_WINDING
+    void debugShowSums() const;
+#endif
+#if DEBUG_CONCIDENT
+    void debugShowTs() const;
+#endif
+#if DEBUG_SHOW_WINDING
+    int debugShowWindingValues(int slotCount, int ofInterest) const;
+#endif
+#if DEBUG_DUMP
+    void dump() const;
+#endif
+#if DEBUG_ACTIVE_SPANS
+    void validateActiveSpans() const;
+#endif
+
+private:
+    const SkPoint* fPts;
+    SkPathOpsBounds fBounds;
+    SkTDArray<SkOpSpan> fTs; // two or more (always includes t=0 t=1)
+    // OPTIMIZATION: could pack donespans, verb, operand, xor into 1 int-sized value
+    int fDoneSpans; // quick check that segment is finished
+    // OPTIMIZATION: force the following to be byte-sized
+    SkPath::Verb fVerb;
+    bool fOperand;
+    bool fXor; // set if original contour had even-odd fill
+    bool fOppXor; // set if opposite operand had even-odd fill
+#if DEBUG_DUMP
+    int fID;
+#endif
+};
+
+#endif