compute initial winding from projected rays

src/pathops/SkOpAngle.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 "SkOpAngle.h"
 #include "SkOpSegment.h"
 #include "SkPathOpsCurve.h"
 #include "SkTSort.h"
@@ skipping 342 matching lines @@
                 ? checkEnd->upCast()->next() : NULL
                 : checkEnd->prev();
     } while (checkEnd);
 recomputeSector:
     SkOpSpanBase* computedEnd = stepUp ? checkEnd ? checkEnd->prev() : fEnd->segment()->head() 
             : checkEnd ? checkEnd->upCast()->next() : fEnd->segment()->tail();
     if (checkEnd == fEnd || computedEnd == fEnd || computedEnd == fStart) {
         fUnorderable = true;
         return false;
     }
+    if (stepUp != (fStart->t() < computedEnd->t())) {
+        fUnorderable = true;
+        return false;
+    }
     SkOpSpanBase* saveEnd = fEnd;
     fComputedEnd = fEnd = computedEnd;
     setSpans();
     setSector();
     fEnd = saveEnd;
     return !fUnorderable;
 }
 
 int SkOpAngle::convexHullOverlaps(const SkOpAngle* rh) const {
     const SkDVector* sweep = this->fSweep;
@@ skipping 217 matching lines @@
     SkDVector vLeft = *endPt - start;
     SkDVector vRight = oppPt - start;
     double dir = vLeft.crossCheck(vRight);
     if (!dir) {
         return false;
     }
     *inside = dir < 0;
     return true;
 }
 
-// Most of the time, the first one can be found trivially by detecting the smallest sector value.
-// If all angles have the same sector value, actual sorting is required.
-SkOpAngle* SkOpAngle::findFirst() {
-    SkOpAngle* best = this;
-    int bestStart = SkTMin(fSectorStart, fSectorEnd);
-    SkOpAngle* angle = this;
-    while ((angle = angle->fNext) != this) {
-        int angleEnd = SkTMax(angle->fSectorStart, angle->fSectorEnd);
-        if (angleEnd < bestStart) {
-            return angle;    // we wrapped around
-        }
-        int angleStart = SkTMin(angle->fSectorStart, angle->fSectorEnd);
-        if (bestStart > angleStart) {
-            best = angle;
-            bestStart = angleStart;
-        }
-    }
-    // back up to the first possible angle
-    SkOpAngle* firstBest = best;
-    angle = best;
-    int bestEnd = SkTMax(best->fSectorStart, best->fSectorEnd);
-    while ((angle = angle->previous()) != firstBest) {
-        if (angle->fStop) {
-            break;
-        }
-        int angleStart = SkTMin(angle->fSectorStart, angle->fSectorEnd);
-        // angles that are smaller by one aren't necessary better, since the larger may be a line
-        // and the smaller may be a curve that curls to the other side of the line.
-        if (bestEnd + 1 < angleStart) {
-            return best;
-        }
-        best = angle;
-        bestEnd = SkTMax(angle->fSectorStart, angle->fSectorEnd);
-    }
-    // in the case where all angles are nearly in the same sector, check the order to find the best
-    firstBest = best;
-    angle = best;
-    do {
-        angle = angle->fNext;
-        if (angle->fStop) {
-            return firstBest;
-        }
-        bool orderable = best->orderable(angle);  // note: may return an unorderable angle
-        if (orderable == 0) {
-            return angle;
-        }
-        best = angle;
-    } while (angle != firstBest);
-    // if the angles are equally ordered, fall back on the initial tangent
-    bool foundBelow = false;
-    while ((angle = angle->fNext)) {
-        SkDVector scratch[2];
-        const SkDVector* sweep;
-        if (!angle->fUnorderedSweep) {
-            sweep = angle->fSweep;
-        } else {
-            scratch[0] = angle->fCurvePart[1] - angle->fCurvePart[0];
-            sweep = &scratch[0];
-        }
-        bool isAbove = sweep->fY <= 0;
-        if (isAbove && foundBelow) {
-            return angle;
-        }
-        foundBelow |= !isAbove;
-        if (angle == firstBest) {
-            return NULL; // should not loop around
-        }
-    }
-    SkASSERT(0);  // should never get here
-    return NULL;
-}
-
 /*      y<0 y==0 y>0  x<0 x==0 x>0 xy<0 xy==0 xy>0
     0    x                      x               x
     1    x                      x          x
     2    x                      x    x
     3    x                  x        x
     4    x             x             x
     5    x             x                   x
     6    x             x                        x
     7         x        x                        x
     8             x    x                        x
@@ skipping 127 matching lines @@
     int count = 0;
     const SkOpAngle* first = this;
     const SkOpAngle* next = this;
     do {
         next = next->fNext;
         ++count;
     } while (next && next != first);
     return count;
 }
 
-// OPTIMIZATION: can this be done better in after when angles are sorted?
-bool SkOpAngle::markStops() {
-    SkOpAngle* angle = this;
-    int lastEnd = SkTMax(fSectorStart, fSectorEnd);
-    do {
-        angle = angle->fNext;
-        if (!angle) {
-            return false;
-        }
-        int angleStart = SkTMin(angle->fSectorStart, angle->fSectorEnd);
-        // angles that are smaller by one aren't necessary better, since the larger may be a line
-        // and the smaller may be a curve that curls to the other side of the line.
-        if (lastEnd + 1 < angleStart) {
-            angle->fStop = true;
-        }
-        lastEnd = SkTMax(angle->fSectorStart, angle->fSectorEnd);
-    } while (angle != this);
-    return true;
-}
-
 bool SkOpAngle::merge(SkOpAngle* angle) {
     SkASSERT(fNext);
     SkASSERT(angle->fNext);
     SkOpAngle* working = angle;
     do {
         if (this == working) {
             return false;
         }
         working = working->fNext;
     } while (working != angle);
@@ skipping 112 matching lines @@
 SkOpSegment* SkOpAngle::segment() const {
     return fStart->segment();
 }
 
 void SkOpAngle::set(SkOpSpanBase* start, SkOpSpanBase* end) {
     fStart = start;
     fComputedEnd = fEnd = end;
     SkASSERT(start != end);
     fNext = NULL;
     fComputeSector = fComputedSector = fCheckCoincidence = false;
-    fStop = false;
     setSpans();
     setSector();
     SkDEBUGCODE(fID = start ? start->globalState()->nextAngleID() : -1);
 }
 
 void SkOpAngle::setCurveHullSweep() {
     fUnorderedSweep = false;
     fSweep[0] = fCurvePart[1] - fCurvePart[0];
     const SkOpSegment* segment = fStart->segment();
     if (SkPath::kLine_Verb == segment->verb()) {
@@ skipping 168 matching lines @@
     crossesZero = this->checkCrossesZero();
     start = SkTMin(fSectorStart, fSectorEnd);
     int end = SkTMax(fSectorStart, fSectorEnd);
     if (!crossesZero) {
         fSectorMask = (unsigned) -1 >> (31 - end + start) << start;
     } else {
         fSectorMask = (unsigned) -1 >> (31 - start) | (-1 << end);
     }
 }
 
-int SkOpAngle::sign() const {
-    SkASSERT(fStart->t() != fEnd->t());
-    return fStart->t() < fEnd->t() ? -1 : 1;
-}
-
 SkOpSpan* SkOpAngle::starter() {
     return fStart->starter(fEnd);
 }
 
 bool SkOpAngle::tangentsDiverge(const SkOpAngle* rh, double s0xt0) const {
     if (s0xt0 == 0) {
         return false;
     }
     // if the ctrl tangents are not nearly parallel, use them
     // solve for opposite direction displacement scale factor == m
@@ skipping 11 matching lines @@
         return true;
     }
     SkASSERT(s0dt0 != 0);
     double m = s0xt0 / s0dt0;
     double sDist = sweep[0].length() * m;
     double tDist = tweep[0].length() * m;
     bool useS = fabs(sDist) < fabs(tDist);
     double mFactor = fabs(useS ? this->distEndRatio(sDist) : rh->distEndRatio(tDist));
     return mFactor < 2400;  // empirically found limit
 }