Reland of path ops: fix conic weight and partial coincidence

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 "SkPathOpsBounds.h"
 #include "SkPathOpsRect.h"
 #include "SkIntersections.h"
 #include "SkTSort.h"
 
+#ifdef SK_DEBUG
+typedef uint8_t SkOpDebugBool;
+#else
+typedef bool SkOpDebugBool;
+#endif
+
 /* TCurve and OppCurve are one of { SkDQuadratic, SkDConic, SkDCubic } */
 template<typename TCurve, typename OppCurve>
 class SkTCoincident {
 public:
     SkTCoincident() {
         this->init();
     }
 
+    void debugInit() {
+#ifdef SK_DEBUG
+        this->fPerpPt.fX = this->fPerpPt.fY = SK_ScalarNaN;
+        this->fPerpT = SK_ScalarNaN;
+        this->fCoincident = 0xFF;
+#endif
+    }
+
+    char dumpIsCoincidentStr() const;
     void dump() const;
 
     bool isCoincident() const {
-        return fCoincident;
+        SkASSERT(!!fCoincident == fCoincident);
+        return SkToBool(fCoincident);
     }
 
     void init() {
         fPerpT = -1;
         fCoincident = false;
         fPerpPt.fX = fPerpPt.fY = SK_ScalarNaN;
     }
 
     void markCoincident() {
         if (!fCoincident) {
             fPerpT = -1;
         }
         fCoincident = true;
     }
 
     const SkDPoint& perpPt() const {
         return fPerpPt;
     }
 
     double perpT() const {
         return fPerpT;
     }
 
     void setPerp(const TCurve& c1, double t, const SkDPoint& cPt, const OppCurve& );
 
 private:
     SkDPoint fPerpPt;
     double fPerpT;  // perpendicular intersection on opposite curve
-    bool fCoincident;
+    SkOpDebugBool fCoincident;
 };
 
 template<typename TCurve, typename OppCurve> class SkTSect;
 template<typename TCurve, typename OppCurve> class SkTSpan;
 
 template<typename TCurve, typename OppCurve>
 struct SkTSpanBounded {
     SkTSpan<TCurve, OppCurve>* fBounded;
     SkTSpanBounded* fNext;
 };
@@ skipping 113 matching lines @@
     TCurve fPart;
     SkTCoincident<TCurve, OppCurve> fCoinStart;
     SkTCoincident<TCurve, OppCurve> fCoinEnd;
     SkTSpanBounded<OppCurve, TCurve>* fBounded;
     SkTSpan* fPrev;
     SkTSpan* fNext;
     SkDRect fBounds;
     double fStartT;
     double fEndT;
     double fBoundsMax;
-    bool fCollapsed;
-    bool fHasPerp;
-    bool fIsLinear;
-    bool fIsLine;
-    bool fDeleted;
+    SkOpDebugBool fCollapsed;
+    SkOpDebugBool fHasPerp;
+    SkOpDebugBool fIsLinear;
+    SkOpDebugBool fIsLine;
+    SkOpDebugBool fDeleted;
     SkDEBUGCODE_(SkTSect<TCurve, OppCurve>* fDebugSect);
     PATH_OPS_DEBUG_T_SECT_CODE(int fID);
     friend class SkTSect<TCurve, OppCurve>;
     friend class SkTSect<OppCurve, TCurve>;
     friend class SkTSpan<OppCurve, TCurve>;
 };
 
 template<typename TCurve, typename OppCurve>
 class SkTSect {
 public:
@@ skipping 59 matching lines @@
     void dumpCommonCurves(const SkTSpan<TCurve, OppCurve>* ) const;
     static int EndsEqual(const SkTSect* sect1, const SkTSect<OppCurve, TCurve>* sect2,
                          SkIntersections* );
     SkTSpan<TCurve, OppCurve>* extractCoincident(SkTSect<OppCurve, TCurve>* sect2,
                                                   SkTSpan<TCurve, OppCurve>* first,
                                                   SkTSpan<TCurve, OppCurve>* last);
     SkTSpan<TCurve, OppCurve>* findCoincidentRun(SkTSpan<TCurve, OppCurve>* first,
                                                   SkTSpan<TCurve, OppCurve>** lastPtr);
     int intersects(SkTSpan<TCurve, OppCurve>* span, SkTSect<OppCurve, TCurve>* opp,
                    SkTSpan<OppCurve, TCurve>* oppSpan, int* oppResult);
+    bool isParallel(const SkDLine& thisLine, const SkTSect<OppCurve, TCurve>* opp) const;
     int linesIntersect(SkTSpan<TCurve, OppCurve>* span, SkTSect<OppCurve, TCurve>* opp,
                        SkTSpan<OppCurve, TCurve>* oppSpan, SkIntersections* );
     void markSpanGone(SkTSpan<TCurve, OppCurve>* span);
     bool matchedDirection(double t, const SkTSect<OppCurve, TCurve>* sect2, double t2) const;
     void matchedDirCheck(double t, const SkTSect<OppCurve, TCurve>* sect2, double t2,
                          bool* calcMatched, bool* oppMatched) const;
     void mergeCoincidence(SkTSect<OppCurve, TCurve>* sect2);
     SkTSpan<TCurve, OppCurve>* prev(SkTSpan<TCurve, OppCurve>* ) const;
     void removeByPerpendicular(SkTSect<OppCurve, TCurve>* opp);
     void recoverCollapsed();
@@ skipping 539 matching lines @@
 {
     fHead = addOne();
     fHead->init(c);
 }
 
 template<typename TCurve, typename OppCurve>
 SkTSpan<TCurve, OppCurve>* SkTSect<TCurve, OppCurve>::addOne() {
     SkTSpan<TCurve, OppCurve>* result;
     if (fDeleted) {
         result = fDeleted;
-        result->reset();
         fDeleted = result->fNext;
     } else {
         result = new (fHeap.allocThrow(sizeof(SkTSpan<TCurve, OppCurve>)))(
                 SkTSpan<TCurve, OppCurve>);
-        result->fBounded = nullptr;
 #if DEBUG_T_SECT
         ++fDebugAllocatedCount;
 #endif
     }
+    result->reset();
     result->fHasPerp = false;
     result->fDeleted = false;
     ++fActiveCount; 
     PATH_OPS_DEBUG_T_SECT_CODE(result->fID = fDebugCount++ * 2 + fID);
     SkDEBUGCODE(result->fDebugSect = this);
+#ifdef SK_DEBUG
+    result->fPart.debugInit();
+    result->fCoinStart.debugInit();
+    result->fCoinEnd.debugInit();
+    result->fPrev = result->fNext = nullptr;
+    result->fBounds.debugInit();
+    result->fStartT = result->fEndT = result->fBoundsMax = SK_ScalarNaN;
+    result->fCollapsed = result->fIsLinear = result->fIsLine = 0xFF;
+#endif
     return result;
 }
 
 template<typename TCurve, typename OppCurve>
 bool SkTSect<TCurve, OppCurve>::binarySearchCoin(SkTSect<OppCurve, TCurve>* sect2, double tStart,
         double tStep, double* resultT, double* oppT) {
     SkTSpan<TCurve, OppCurve> work;
     double result = work.fStartT = work.fEndT = tStart;
     SkDEBUGCODE(work.fDebugSect = this);
     SkDPoint last = fCurve.ptAtT(tStart);
@@ skipping 414 matching lines @@
         span->fStartT = span->fEndT = i[0][0];
         oppSpan->fStartT = oppSpan->fEndT = i[1][0];
         return *oppResult = 2;
     }
     if (span->fIsLinear || oppSpan->fIsLinear) {
         return *oppResult = (int) span->linearsIntersect(oppSpan);
     }
     return *oppResult = 1;
 }
 
+template<typename TCurve>
+static bool is_parallel(const SkDLine& thisLine, const TCurve& opp) {
+    if (!opp.IsConic()) {
+        return false; // FIXME : breaks a lot of stuff now
+    }
+    int finds = 0;
+    SkDLine thisPerp;
+    thisPerp.fPts[0].fX = thisLine.fPts[1].fX + (thisLine.fPts[1].fY - thisLine.fPts[0].fY);
+    thisPerp.fPts[0].fY = thisLine.fPts[1].fY + (thisLine.fPts[0].fX - thisLine.fPts[1].fX);
+    thisPerp.fPts[1] = thisLine.fPts[1];
+    SkIntersections perpRayI;
+    perpRayI.intersectRay(opp, thisPerp);
+    for (int pIndex = 0; pIndex < perpRayI.used(); ++pIndex) {
+        finds += perpRayI.pt(pIndex).approximatelyEqual(thisPerp.fPts[1]);
+    }
+    thisPerp.fPts[1].fX = thisLine.fPts[0].fX + (thisLine.fPts[1].fY - thisLine.fPts[0].fY);
+    thisPerp.fPts[1].fY = thisLine.fPts[0].fY + (thisLine.fPts[0].fX - thisLine.fPts[1].fX);
+    thisPerp.fPts[0] = thisLine.fPts[0];
+    perpRayI.intersectRay(opp, thisPerp);
+    for (int pIndex = 0; pIndex < perpRayI.used(); ++pIndex) {
+        finds += perpRayI.pt(pIndex).approximatelyEqual(thisPerp.fPts[0]);
+    }
+    return finds >= 2;
+}
+
 // while the intersection points are sufficiently far apart:
 // construct the tangent lines from the intersections
 // find the point where the tangent line intersects the opposite curve
 template<typename TCurve, typename OppCurve>
 int SkTSect<TCurve, OppCurve>::linesIntersect(SkTSpan<TCurve, OppCurve>* span,
         SkTSect<OppCurve, TCurve>* opp,
         SkTSpan<OppCurve, TCurve>* oppSpan, SkIntersections* i) {
     SkIntersections thisRayI, oppRayI;
     SkDLine thisLine = {{ span->fPart[0], span->fPart[TCurve::kPointLast] }};
     SkDLine oppLine = {{ oppSpan->fPart[0], oppSpan->fPart[OppCurve::kPointLast] }};
     int loopCount = 0;
     double bestDistSq = DBL_MAX;
     if (!thisRayI.intersectRay(opp->fCurve, thisLine)) {
         return 0;
     }
     if (!oppRayI.intersectRay(this->fCurve, oppLine)) {
         return 0;
     }
     // if the ends of each line intersect the opposite curve, the lines are coincident
     if (thisRayI.used() > 1) {
         int ptMatches = 0;
         for (int tIndex = 0; tIndex < thisRayI.used(); ++tIndex) {
             for (int lIndex = 0; lIndex < (int) SK_ARRAY_COUNT(thisLine.fPts); ++lIndex) {
                 ptMatches += thisRayI.pt(tIndex).approximatelyEqual(thisLine.fPts[lIndex]);
             }
         }
-        if (ptMatches == 2) {
+        if (ptMatches == 2 || is_parallel(thisLine, opp->fCurve)) {
             return 2;
         }
     }
     if (oppRayI.used() > 1) {
         int ptMatches = 0;
         for (int oIndex = 0; oIndex < oppRayI.used(); ++oIndex) {
             for (int lIndex = 0; lIndex < (int) SK_ARRAY_COUNT(thisLine.fPts); ++lIndex) {
                 ptMatches += oppRayI.pt(oIndex).approximatelyEqual(oppLine.fPts[lIndex]);
             }
         }
-        if (ptMatches == 2) {
+        if (ptMatches == 2|| is_parallel(oppLine, this->fCurve)) {
             return 2;
         }
     }
     do {
         // pick the closest pair of points
         double closest = DBL_MAX;
         int closeIndex SK_INIT_TO_AVOID_WARNING;
         int oppCloseIndex SK_INIT_TO_AVOID_WARNING;
         for (int index = 0; index < oppRayI.used(); ++index) {
             if (!roughly_between(span->fStartT, oppRayI[0][index], span->fEndT)) {
@@ skipping 846 matching lines @@
         } else if (intersections->isCoincident(index + 1)) {
             intersections->removeOne(index + 1);
             --last;
         } else {
             intersections->setCoincident(index++);
         }
         intersections->setCoincident(index);
     }
     SkASSERT(intersections->used() <= TCurve::kMaxIntersections);
 }