pathops coincident fixes

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 "SkOpCoincidence.h"
 #include "SkOpContour.h"
 #include "SkOpSegment.h"
 #include "SkPathWriter.h"
@@ skipping 141 matching lines @@
 
 bool SkOpSegment::activeWinding(SkOpSpanBase* start, SkOpSpanBase* end, int* sumWinding) {
     int maxWinding;
     setUpWinding(start, end, &maxWinding, sumWinding);
     bool from = maxWinding != 0;
     bool to = *sumWinding  != 0;
     bool result = gUnaryActiveEdge[from][to];
     return result;
 }
 
+void SkOpSegment::addAlignIntersection(SkOpPtT& endPtT, SkPoint& oldPt,
+        SkOpContourHead* contourList, SkChunkAlloc* allocator) {
+    const SkPoint& newPt = endPtT.fPt;
+    if (newPt == oldPt) {
+        return;
+    }
+    SkPoint line[2] = { newPt, oldPt };
+    SkPathOpsBounds lineBounds;
+    lineBounds.setBounds(line, 2);
+    SkDLine aLine;
+    aLine.set(line);
+    SkOpContour* current = contourList;
+    do {
+        if (!SkPathOpsBounds::Intersects(current->bounds(), lineBounds)) {
+            continue;
+        }
+        SkOpSegment* segment = current->first();
+        do {
+            if (!SkPathOpsBounds::Intersects(segment->bounds(), lineBounds)) {
+                continue;
+            }
+            if (newPt == segment->fPts[0]) {
+                continue;
+            }
+            if (newPt == segment->fPts[SkPathOpsVerbToPoints(segment->fVerb)]) {
+                continue;
+            }
+            if (oldPt == segment->fPts[0]) {
+                continue;
+            }
+            if (oldPt == segment->fPts[SkPathOpsVerbToPoints(segment->fVerb)]) {
+                continue;
+            }
+            if (endPtT.contains(segment)) {
+                continue;
+            }
+            SkIntersections i;
+            switch (segment->fVerb) {
+                case SkPath::kLine_Verb: {
+                    SkDLine bLine;
+                    bLine.set(segment->fPts);
+                    i.intersect(bLine, aLine);
+                    } break;
+                case SkPath::kQuad_Verb: {
+                    SkDQuad bQuad;
+                    bQuad.set(segment->fPts);
+                    i.intersect(bQuad, aLine);
+                    } break;
+                case SkPath::kConic_Verb: {
+                    SkDConic bConic;
+                    bConic.set(segment->fPts, segment->fWeight);
+                    i.intersect(bConic, aLine);
+                    } break;
+                case SkPath::kCubic_Verb: {
+                    SkDCubic bCubic;
+                    bCubic.set(segment->fPts);
+                    i.intersect(bCubic, aLine);
+                    } break;
+                default:
+                    SkASSERT(0);
+            }
+            if (i.used()) {
+                SkASSERT(i.used() == 1);
+                SkASSERT(!zero_or_one(i[0][0]));
+                SkOpSpanBase* checkSpan = fHead.next();
+                while (!checkSpan->final()) {
+                    if (checkSpan->contains(segment)) {
+                        goto nextSegment;
+                    }
+                    checkSpan = checkSpan->upCast()->next();
+                }
+                SkOpPtT* ptT = segment->addT(i[0][0], SkOpSegment::kAllowAlias, allocator);
+                ptT->fPt = newPt;
+                endPtT.addOpp(ptT);
+            }
+    nextSegment:
+            ;
+        } while ((segment = segment->next()));
+    } while ((current = current->next()));
+}
+
 void SkOpSegment::addCurveTo(const SkOpSpanBase* start, const SkOpSpanBase* end,
         SkPathWriter* path, bool active) const {
     SkOpCurve edge;
     const SkPoint* ePtr;
     SkScalar eWeight;
     if ((start == &fHead && end == &fTail) || (start == &fTail && end == &fHead)) {
         ePtr = fPts;
         eWeight = fWeight;
     } else {
     // OPTIMIZE? if not active, skip remainder and return xyAtT(end)
@@ skipping 591 matching lines @@
         *nextEnd = step > 0 ? (*nextStart)->upCast()->next() : (*nextStart)->prev();
         return other;
     }
     SkDEBUGCODE(SkOpSpanBase* endNear = step > 0 ? (*nextStart)->upCast()->next() \
             : (*nextStart)->prev());
     SkASSERT(endNear == end);  // is this ever not end?
     SkASSERT(endNear);
     SkASSERT(start != endNear);
     SkASSERT((start->t() < endNear->t()) ^ (step < 0));
     SkOpAngle* angle = this->spanToAngle(end, start);
-    if (angle->unorderable()) {
+    if (!angle || angle->unorderable()) {
         *unsortable = true;
         markDone(start->starter(end));
         return NULL;
     }
 #if DEBUG_SORT
     SkDebugf("%s\n", __FUNCTION__);
     angle->debugLoop();
 #endif
     SkOpAngle* nextAngle = angle->next();
     const SkOpAngle* foundAngle = NULL;
@@ skipping 26 matching lines @@
     return nextSegment;
 }
 
 SkOpGlobalState* SkOpSegment::globalState() const {
     return contour()->globalState(); 
 }
 
 void SkOpSegment::init(SkPoint pts[], SkScalar weight, SkOpContour* contour, SkPath::Verb verb) {
     fContour = contour;
     fNext = NULL;
+    fOriginal[0] = pts[0];
+    fOriginal[1] = pts[SkPathOpsVerbToPoints(verb)];
     fPts = pts;
     fWeight = weight;
     fVerb = verb;
     fCubicType = SkDCubic::kUnsplit_SkDCubicType;
     fCount = 0;
     fDoneCount = 0;
     fTopsFound = false;
     fVisited = false;
     SkOpSpan* zeroSpan = &fHead;
     zeroSpan->init(this, NULL, 0, fPts[0]);
@@ skipping 276 matching lines @@
             opp->resetVisited();
         }
     } while (!span->final() && (span = span->upCast()->next()));
 }
 
 // look for pairs of undetected coincident curves
 // assumes that segments going in have visited flag clear
 // curve/curve intersection should now do a pretty good job of finding coincident runs so 
 // this may be only be necessary for line/curve pairs -- so skip unless this is a line and the
 // the opp is not a line
-void SkOpSegment::missingCoincidence(SkOpCoincidence* coincidences, SkChunkAlloc* allocator) {
+bool SkOpSegment::missingCoincidence(SkOpCoincidence* coincidences, SkChunkAlloc* allocator) {
     if (this->verb() != SkPath::kLine_Verb) {
-        return;
+        return false;
     }
     if (this->done()) {
-        return;
+        return false;
     }
     SkOpSpan* prior = NULL;
     SkOpSpanBase* spanBase = &fHead;
     do {
         SkOpPtT* ptT = spanBase->ptT(), * spanStopPtT = ptT;
         SkASSERT(ptT->span() == spanBase);
         while ((ptT = ptT->next()) != spanStopPtT) {
             if (ptT->deleted()) {
                 continue;
             }
@@ skipping 47 matching lines @@
             bool swapped = priorPtT->fT > ptT->fT;
             if (swapped) {
                 SkTSwap(priorPtT, ptT);
                 SkTSwap(oppStart, oppEnd);
             }
             bool flipped = oppStart->fT > oppEnd->fT;
             bool coincident;
             if (coincidences->contains(priorPtT, ptT, oppStart, oppEnd, flipped)) {
                 goto swapBack;
             }
-            {
-                // average t, find mid pt
-                double midT = (prior->t() + spanBase->t()) / 2;
-                SkPoint midPt = this->ptAtT(midT);
-                coincident = true;
-                // if the mid pt is not near either end pt, project perpendicular through opp seg
-                if (!SkDPoint::ApproximatelyEqual(priorPtT->fPt, midPt)
-                        && !SkDPoint::ApproximatelyEqual(ptT->fPt, midPt)) {
-                    coincident = false;
-                    SkIntersections i;
-                    SkVector dxdy = (*CurveSlopeAtT[fVerb])(this->pts(), this->weight(), midT);
-                    SkDLine ray = {{{midPt.fX, midPt.fY},
-                            {midPt.fX + dxdy.fY, midPt.fY - dxdy.fX}}};
-                    (*CurveIntersectRay[opp->verb()])(opp->pts(), opp->weight(), ray, &i);
-                    // measure distance and see if it's small enough to denote coincidence
-                    for (int index = 0; index < i.used(); ++index) {
-                        SkDPoint oppPt = i.pt(index);
-                        if (oppPt.approximatelyEqual(midPt)) {
-                            SkVector oppDxdy = (*CurveSlopeAtT[opp->verb()])(opp->pts(),
-                                    opp->weight(), i[index][0]);
-                            oppDxdy.normalize();
-                            dxdy.normalize();
-                            SkScalar flatness = SkScalarAbs(dxdy.cross(oppDxdy) / FLT_EPSILON);
-                            coincident |= flatness < 5000;  // FIXME: replace with tuned value
-                        }
-                    }
-                }
-            }
+            coincident = testForCoincidence(priorPtT, ptT, prior, spanBase, opp, 5000);
             if (coincident) {
             // mark coincidence
                 if (!coincidences->extend(priorPtT, ptT, oppStart, oppEnd)
                         && !coincidences->extend(oppStart, oppEnd, priorPtT, ptT)) {
                     coincidences->add(priorPtT, ptT, oppStart, oppEnd, allocator);
                 }
                 clear_visited(&fHead);
-                return;
+                return true;
             }
     swapBack:
             if (swapped) {
                 SkTSwap(priorPtT, ptT);
             }
         }
     } while ((spanBase = spanBase->final() ? NULL : spanBase->upCast()->next()));
     clear_visited(&fHead);
+    return false;
 }
 
 // if a span has more than one intersection, merge the other segments' span as needed
 void SkOpSegment::moveMultiples() {
     debugValidate();
     SkOpSpanBase* test = &fHead;
     do {
         int addCount = test->spanAddsCount();
         SkASSERT(addCount >= 1);
         if (addCount == 1) {
@@ skipping 357 matching lines @@
     } else if (fVerb == SkPath::kConic_Verb) {
         edge->fConic[1] = SkDConic::SubDivide(fPts, fWeight, edge->fQuad[0], edge->fQuad[2],
             startT, endT, &edge->fConic.fWeight);
     } else {
         SkASSERT(fVerb == SkPath::kCubic_Verb);
         SkDCubic::SubDivide(fPts, edge->fCubic[0], edge->fCubic[3], startT, endT, &edge->fCubic[1]);
     }
     return true;
 }
 
+bool SkOpSegment::testForCoincidence(const SkOpPtT* priorPtT, const SkOpPtT* ptT,
+        const SkOpSpanBase* prior, const SkOpSpanBase* spanBase, const SkOpSegment* opp,
+        SkScalar flatnessLimit) const {
+    // average t, find mid pt
+    double midT = (prior->t() + spanBase->t()) / 2;
+    SkPoint midPt = this->ptAtT(midT);
+    bool coincident = true;
+    // if the mid pt is not near either end pt, project perpendicular through opp seg
+    if (!SkDPoint::ApproximatelyEqual(priorPtT->fPt, midPt)
+            && !SkDPoint::ApproximatelyEqual(ptT->fPt, midPt)) {
+        coincident = false;
+        SkIntersections i;
+        SkVector dxdy = (*CurveSlopeAtT[fVerb])(this->pts(), this->weight(), midT);
+        SkDLine ray = {{{midPt.fX, midPt.fY}, {midPt.fX + dxdy.fY, midPt.fY - dxdy.fX}}};
+        (*CurveIntersectRay[opp->verb()])(opp->pts(), opp->weight(), ray, &i);
+        // measure distance and see if it's small enough to denote coincidence
+        for (int index = 0; index < i.used(); ++index) {
+            SkDPoint oppPt = i.pt(index);
+            if (oppPt.approximatelyEqual(midPt)) {
+                SkVector oppDxdy = (*CurveSlopeAtT[opp->verb()])(opp->pts(),
+                        opp->weight(), i[index][0]);
+                oppDxdy.normalize();
+                dxdy.normalize();
+                SkScalar flatness = SkScalarAbs(dxdy.cross(oppDxdy) / FLT_EPSILON);
+                coincident |= flatness < flatnessLimit;
+            }
+        }
+    }
+    return coincident;
+}
+
 void SkOpSegment::undoneSpan(SkOpSpanBase** start, SkOpSpanBase** end) {
     SkOpSpan* span = this->head();
     do {
         if (!span->done()) {
             break;
         }
     } while ((span = span->next()->upCastable()));
     SkASSERT(span);
     *start = span;
     *end = span->next();
@@ skipping 60 matching lines @@
     int absOut = abs(outerWinding);
     int absIn = abs(innerWinding);
     bool result = absOut == absIn ? outerWinding < 0 : absOut < absIn;
     return result;
 }
 
 int SkOpSegment::windSum(const SkOpAngle* angle) const {
     const SkOpSpan* minSpan = angle->start()->starter(angle->end());
     return minSpan->windSum();
 }