pathops work in progress

src/pathops/SkOpSegment.cpp

 /*
  * Copyright 2012 Google Inc.
  *
  * Use of this source code is governed by a BSD-style license that can be
  * found in the LICENSE file.
  */
 #include "SkIntersections.h"
 #include "SkOpSegment.h"
 #include "SkPathWriter.h"
 #include "SkTSort.h"
@@ skipping 1280 matching lines @@
         return bestTIndex;
     }
     if (fBounds.fLeft == fBounds.fRight) {
         // if vertical, and directly above test point, wait for another one
         return AlmostEqualUlps(basePt.fX, fBounds.fLeft) ? SK_MinS32 : bestTIndex;
     }
     // intersect ray starting at basePt with edge
     SkIntersections intersections;
     // OPTIMIZE: use specialty function that intersects ray with curve,
     // returning t values only for curve (we don't care about t on ray)
+    intersections.allowNear(false);
     int pts = (intersections.*CurveVertical[SkPathOpsVerbToPoints(fVerb)])
             (fPts, top, bottom, basePt.fX, false);
     if (pts == 0 || (current && pts == 1)) {
         return bestTIndex;
     }
     if (current) {
         SkASSERT(pts > 1);
         int closestIdx = 0;
         double closest = fabs(intersections[0][0] - mid);
         for (int idx = 1; idx < pts; ++idx) {
@@ skipping 102 matching lines @@
             ;
         int otherCount = other->fTs.count();
         int peekLast = span.fOtherIndex;
         while (++peekLast < otherCount && other->fTs[peekLast].fT == otherT)
             ;
         if (++peekStart == --peekLast) { // if there isn't a range, there's nothing to do
             continue;
         }
         // t start/last describe the range of spans that match the t of this span
         double t = span.fT;
-        int tStart = index;
-        while (--tStart >= 0 && (t == fTs[tStart].fT || fTs[tStart].fTiny))
-            ;
-        int tLast = index;
-        while (fTs[tLast].fTiny) {
-            ++tLast;
+        double tBottom = -1;
+        int tStart = -1;
+        int tLast = count;
+        bool lastSmall = false;
+        double afterT = t;
+        for (int inner = 0; inner < count; ++inner) {
+            double innerT = fTs[inner].fT;
+            if (innerT <= t && innerT > tBottom) {
+                if (innerT < t || !lastSmall) {
+                    tStart = inner - 1;
+                }
+                tBottom = innerT;
+            }
+            if (innerT > afterT) {
+                if (t == afterT && lastSmall) {
+                    afterT = innerT;
+                } else {
+                    tLast = inner;
+                    break;
+                }
+            }
+            lastSmall = innerT <= t ? fTs[inner].fSmall : false;
         }
-        while (++tLast < count && t == fTs[tLast].fT)
-            ;
         for (int peekIndex = peekStart; peekIndex <= peekLast; ++peekIndex) {
             if (peekIndex == span.fOtherIndex) {  // skip the other span pointed to by this span
                 continue;
             }
             const SkOpSpan& peekSpan = other->fTs[peekIndex];
             SkOpSegment* match = peekSpan.fOther;
             if (match->done()) {
                 continue;  // if the edge has already been eaten (likely coincidence), ignore it
             }
             const double matchT = peekSpan.fOtherT;
@@ skipping 247 matching lines @@
         MissingSpan& missing = missingSpans[index];
         missing.fSegment->addTPair(missing.fT, missing.fOther, missing.fOtherT, false, missing.fPt);
     }
     for (int index = 0; index < missingCount; ++index)  {
         MissingSpan& missing = missingSpans[index];
         missing.fSegment->fixOtherTIndex();
         missing.fOther->fixOtherTIndex();
     }
 }
 
+bool SkOpSegment::findCoincidentMatch(const SkOpSpan* span, const SkOpSegment* other, int oStart,
+        int oEnd, int step, SkPoint* startPt, SkPoint* endPt, double* endT) const {
+    SkASSERT(span->fT == 0 || span->fT == 1);
+    SkASSERT(span->fOtherT == 0 || span->fOtherT == 1);
+    const SkOpSpan* otherSpan = &other->span(oEnd);
+    double refT = otherSpan->fT;
+    const SkPoint& refPt = otherSpan->fPt;
+    const SkOpSpan* lastSpan = &other->span(step > 0 ? other->count() - 1 : 0);
+    do {
+        const SkOpSegment* match = span->fOther;
+        if (match == otherSpan->fOther) {
+            // find start of respective spans and see if both have winding
+            int startIndex, endIndex;
+            if (span->fOtherT == 1) {
+                endIndex = span->fOtherIndex;
+                startIndex = match->nextExactSpan(endIndex, -1);
+            } else {
+                startIndex = span->fOtherIndex;
+                endIndex = match->nextExactSpan(startIndex, 1);
+            }
+            const SkOpSpan& startSpan = match->span(startIndex);
+            if (startSpan.fWindValue != 0) {
+                // draw ray from endSpan.fPt perpendicular to end tangent and measure distance
+                // to other segment.
+                const SkOpSpan& endSpan = match->span(endIndex);
+                SkDLine ray;
+                SkVector dxdy;
+                if (span->fOtherT == 1) {
+                    ray.fPts[0].set(startSpan.fPt);
+                    dxdy = match->dxdy(startIndex);
+                } else {
+                    ray.fPts[0].set(endSpan.fPt);
+                    dxdy = match->dxdy(endIndex);
+                }
+                ray.fPts[1].fX = ray.fPts[0].fX + dxdy.fY;
+                ray.fPts[1].fY = ray.fPts[0].fY - dxdy.fX;
+                SkIntersections i;
+                int roots = (i.*CurveRay[SkPathOpsVerbToPoints(other->verb())])(other->pts(), ray);
+                for (int index = 0; index < roots; ++index) {
+                    if (ray.fPts[0].approximatelyEqual(i.pt(index))) {
+                        double matchMidT = (match->span(startIndex).fT
+                                + match->span(endIndex).fT) / 2;
+                        SkPoint matchMidPt = match->ptAtT(matchMidT);
+                        double otherMidT = (i[0][index] + other->span(oStart).fT) / 2;
+                        SkPoint otherMidPt = other->ptAtT(otherMidT);
+                        if (SkDPoint::ApproximatelyEqual(matchMidPt, otherMidPt)) {
+                            *startPt = startSpan.fPt;
+                            *endPt = endSpan.fPt;
+                            *endT = endSpan.fT;
+                            return true;
+                        }
+                    }
+                }
+            }
+            return false;
+        }
+        if (otherSpan == lastSpan) {
+            break;
+        }
+        otherSpan += step;
+    } while (otherSpan->fT == refT || otherSpan->fPt == refPt);
+    return false;
+}
+
 /*
  The M and S variable name parts stand for the operators.
    Mi stands for Minuend (see wiki subtraction, analogous to difference)
    Su stands for Subtrahend
  The Opp variable name part designates that the value is for the Opposite operator.
  Opposite values result from combining coincident spans.
  */
 SkOpSegment* SkOpSegment::findNextOp(SkTDArray<SkOpSpan*>* chase, int* nextStart, int* nextEnd,
                                      bool* unsortable, SkPathOp op, const int xorMiMask,
                                      const int xorSuMask) {
@@ skipping 360 matching lines @@
         const SkOpAngle* angle = sorted[angleIndex];
         if (angle->segment() == this && angle->start() == end &&
                 angle->end() == start) {
             firstIndex = angleIndex;
             break;
         }
     }
     return firstIndex;
 }
 
+int SkOpSegment::findT(double t, const SkOpSegment* match) const {
+    int count = this->count();
+    for (int index = 0; index < count; ++index) {
+        const SkOpSpan& span = fTs[index];
+        if (span.fT == t && span.fOther == match) {
+            return index;
+        }
+    }
+    SkASSERT(0);
+    return -1;
+}
+
 // FIXME: either:
 // a) mark spans with either end unsortable as done, or
 // b) rewrite findTop / findTopSegment / findTopContour to iterate further
 //    when encountering an unsortable span
 
 // OPTIMIZATION : for a pair of lines, can we compute points at T (cached)
 // and use more concise logic like the old edge walker code?
 // FIXME: this needs to deal with coincident edges
 SkOpSegment* SkOpSegment::findTop(int* tIndexPtr, int* endIndexPtr, bool* unsortable,
                                   bool onlySortable) {
@@ skipping 203 matching lines @@
     double t = fTs[end].fT;
     if (approximately_less_than_zero(t)) {
         return !approximately_less_than_zero(fTs[1].fT);
     }
     if (approximately_greater_than_one(t)) {
         return !approximately_greater_than_one(fTs[count - 2].fT);
     }
     return false;
 }
 
+bool SkOpSegment::isTiny(const SkOpAngle* angle) const {
+    int start = angle->start();
+    int end = angle->end();
+    const SkOpSpan& mSpan = fTs[SkMin32(start, end)];
+    return mSpan.fTiny;
+}
+
+bool SkOpSegment::isTiny(int index) const {
+    return fTs[index].fTiny;
+}
+
+// look pair of active edges going away from coincident edge
+// one of them should be the continuation of other
+// if both are active, look to see if they both the connect to another coincident pair
+// if one at least one is a line, then make the pair coincident
+// if neither is a line, test for coincidence
+bool SkOpSegment::joinCoincidence(bool end, SkOpSegment* other, double otherT, int step,
+        bool cancel) {
+    int otherTIndex = other->findT(otherT, this);
+    int next = other->nextExactSpan(otherTIndex, step);
+    int otherMin = SkTMin(otherTIndex, next);
+    int otherWind = other->span(otherMin).fWindValue;
+    if (otherWind == 0) {
+        return false;
+    }
+    SkASSERT(next >= 0);
+    if (end) {
+        int tIndex = count() - 1;
+        do {
+            SkOpSpan* test = &fTs[tIndex];
+            SkASSERT(test->fT == 1);
+            if (test->fOther == other || test->fOtherT != 0) {
+                continue;
+            }
+            SkPoint startPt, endPt;
+            double endT;
+            if (findCoincidentMatch(test, other, otherTIndex, next, step, &startPt, &endPt, &endT)) {
+                SkOpSegment* match = test->fOther;
+                if (cancel) {
+                    match->addTCancel(startPt, endPt, other);
+                } else {
+                    match->addTCoincident(startPt, endPt, endT, other);
+                }
+                return true;
+            }
+        } while (fTs[--tIndex].fT == 1);
+    } else {
+        int tIndex = 0;
+        do {
+            SkOpSpan* test = &fTs[tIndex];
+            SkASSERT(test->fT == 0);
+            if (test->fOther == other || test->fOtherT != 1) {
+                continue;
+            }
+            SkPoint startPt, endPt;
+            double endT;
+            if (findCoincidentMatch(test, other, otherTIndex, next, step, &startPt, &endPt, &endT)) {
+                SkOpSegment* match = test->fOther;
+                if (cancel) {
+                    match->addTCancel(startPt, endPt, other);
+                } else {
+                    match->addTCoincident(startPt, endPt, endT, other);
+                }
+                return true;
+            }
+        } while (fTs[++tIndex].fT == 0);
+    }
+    return false;
+}
+
 // this span is excluded by the winding rule -- chase the ends
 // as long as they are unambiguous to mark connections as done
 // and give them the same winding value
 SkOpSpan* SkOpSegment::markAndChaseDone(int index, int endIndex, int winding) {
     int step = SkSign32(endIndex - index);
     int min = SkMin32(index, endIndex);
     markDone(min, winding);
     SkOpSpan* last;
     SkOpSegment* other = this;
     while ((other = other->nextChase(&index, step, &min, &last))) {
@@ skipping 699 matching lines @@
     }
     return true;
 }
 
 void SkOpSegment::subDivideBounds(int start, int end, SkPathOpsBounds* bounds) const {
     SkPoint edge[4];
     subDivide(start, end, edge);
     (bounds->*SetCurveBounds[SkPathOpsVerbToPoints(fVerb)])(edge);
 }
 
-bool SkOpSegment::isTiny(const SkOpAngle* angle) const {
-    int start = angle->start();
-    int end = angle->end();
-    const SkOpSpan& mSpan = fTs[SkMin32(start, end)];
-    return mSpan.fTiny;
-}
-
-bool SkOpSegment::isTiny(int index) const {
-    return fTs[index].fTiny;
-}
-
 void SkOpSegment::TrackOutsidePair(SkTArray<SkPoint, true>* outsidePts, const SkPoint& endPt,
         const SkPoint& startPt) {
     int outCount = outsidePts->count();
     if (outCount == 0 || endPt != (*outsidePts)[outCount - 2]) {
         outsidePts->push_back(endPt);
         outsidePts->push_back(startPt);
     }
 }
 
 void SkOpSegment::TrackOutside(SkTArray<SkPoint, true>* outsidePts, const SkPoint& startPt) {
@@ skipping 509 matching lines @@
     SkASSERT(done == fDoneSpans);
 #endif
 }
 
 #ifdef SK_DEBUG
 void SkOpSegment::dumpPts() const {
     int last = SkPathOpsVerbToPoints(fVerb);
     SkDebugf("{{");
     int index = 0;
     do {
-        SkDPoint::DumpSkPoint(fPts[index]);
+        SkDPoint::dump(fPts[index]);
         SkDebugf(", ");
     } while (++index < last);
-    SkDPoint::DumpSkPoint(fPts[index]);
+    SkDPoint::dump(fPts[index]);
     SkDebugf("}}\n");
 }
 
 void SkOpSegment::dumpDPts() const {
     int count = SkPathOpsVerbToPoints(fVerb);
     SkDebugf("{{");
     int index = 0;
     do {
         SkDPoint dPt = {fPts[index].fX, fPts[index].fY};
         dPt.dump();
         if (index != count) {
             SkDebugf(", ");
         }
     } while (++index <= count);
     SkDebugf("}}\n");
 }
 
 void SkOpSegment::dumpSpans() const {
     int count = this->count();
     for (int index = 0; index < count; ++index) {
         const SkOpSpan& span = this->span(index);
         SkDebugf("[%d] ", index);
         span.dump();
     }
 }
 #endif