compute initial winding from projected rays

src/pathops/SkPathOpsWinding.cpp

+/*
+ * Copyright 2015 Google Inc.
+ *
+ * Use of this source code is governed by a BSD-style license that can be
+ * found in the LICENSE file.
+ */
+
+// given a prospective edge, compute its initial winding by projecting a ray
+// if the ray hits another edge
+    // if the edge doesn't have a winding yet, hop up to that edge and start over
+        // concern : check for hops forming a loop
+    // if the edge is unsortable, or
+    // the intersection is nearly at the ends, or
+    // the tangent at the intersection is nearly coincident to the ray,
+        // choose a different ray and try again
+            // concern : if it is unable to succeed after N tries, try another edge? direction?
+// if no edge is hit, compute the winding directly
+
+// given the top span, project the most perpendicular ray and look for intersections
+    // let's try up and then down. What the hey
+
+// bestXY is initialized by caller with basePt
+
+#include "SkOpContour.h"
+#include "SkOpSegment.h"
+#include "SkPathOpsCurve.h"
+
+enum class SkOpRayDir {
+    kLeft,
+    kTop,
+    kRight,
+    kBottom,
+};
+
+#if DEBUG_WINDING
+const char* gDebugRayDirName[] = {
+    "kLeft",
+    "kTop",
+    "kRight",
+    "kBottom"
+};
+#endif
+
+static int xy_index(SkOpRayDir dir) {
+    return static_cast<int>(dir) & 1;
+}
+
+static SkScalar pt_xy(const SkPoint& pt, SkOpRayDir dir) {
+    return (&pt.fX)[xy_index(dir)];
+}
+
+static SkScalar pt_yx(const SkPoint& pt, SkOpRayDir dir) {
+    return (&pt.fX)[!xy_index(dir)];
+}
+
+static double pt_dxdy(const SkDVector& v, SkOpRayDir dir) {
+    return (&v.fX)[xy_index(dir)];
+}
+
+static double pt_dydx(const SkDVector& v, SkOpRayDir dir) {
+    return (&v.fX)[!xy_index(dir)];
+}
+
+static SkScalar rect_side(const SkRect& r, SkOpRayDir dir) {
+    return (&r.fLeft)[static_cast<int>(dir)];
+}
+
+static bool sideways_overlap(const SkRect& rect, const SkPoint& pt, SkOpRayDir dir) {
+    int i = !xy_index(dir);
+    return approximately_between((&rect.fLeft)[i], (&pt.fX)[i], (&rect.fRight)[i]);
+}
+
+static bool less_than(SkOpRayDir dir) {
+    return static_cast<bool>((static_cast<int>(dir) & 2) == 0);
+}
+
+static bool ccw_dxdy(const SkDVector& v, SkOpRayDir dir) {
+    bool vPartPos = pt_dydx(v, dir) > 0;
+    bool leftBottom = ((static_cast<int>(dir) + 1) & 2) != 0;
+    return vPartPos == leftBottom;
+}
+
+struct SkOpRayHit {
+    SkOpRayDir makeTestBase(SkOpSpan* span, double t) {
+        fNext = NULL;
+        fSpan = span;
+        fT = span->t() * (1 - t) + span->next()->t() * t;
+        SkOpSegment* segment = span->segment();
+        fSlope = segment->dSlopeAtT(fT);
+        fPt = segment->ptAtT(fT);
+        fValid = true;
+        return fabs(fSlope.fX) < fabs(fSlope.fY) ? SkOpRayDir::kLeft : SkOpRayDir::kTop;
+    }
+
+    SkOpRayHit* fNext;
+    SkOpSpan* fSpan;
+    SkPoint fPt;
+    double fT;
+    SkDVector fSlope;
+    bool fValid;
+};
+
+void SkOpContour::rayCheck(const SkOpRayHit& base, SkOpRayDir dir, SkOpRayHit** hits,
+        SkChunkAlloc* allocator) {
+    // if the bounds extreme is outside the best, we're done
+    SkScalar baseXY = pt_xy(base.fPt, dir);
+    SkScalar boundsXY = rect_side(fBounds, dir);
+    bool checkLessThan = less_than(dir);
+    if (!approximately_equal(baseXY, boundsXY) && (baseXY < boundsXY) == checkLessThan) {
+        return;
+    }
+    SkOpSegment* testSegment = &fHead;
+    do {
+        testSegment->rayCheck(base, dir, hits, allocator);
+    } while ((testSegment = testSegment->next()));
+}
+
+void SkOpSegment::rayCheck(const SkOpRayHit& base, SkOpRayDir dir, SkOpRayHit** hits,
+        SkChunkAlloc* allocator) {
+    if (!sideways_overlap(fBounds, base.fPt, dir)) {
+        return;
+    }
+    SkScalar baseXY = pt_xy(base.fPt, dir);
+    SkScalar boundsXY = rect_side(fBounds, dir);
+    bool checkLessThan = less_than(dir);
+    if (!approximately_equal(baseXY, boundsXY) && (baseXY < boundsXY) == checkLessThan) {
+        return;
+    }
+    double tVals[3];
+    SkScalar baseYX = pt_yx(base.fPt, dir);
+    int roots = (*CurveIntercept[fVerb * 2 + xy_index(dir)])(fPts, fWeight, baseYX, tVals);
+    for (int index = 0; index < roots; ++index) {
+        double t = tVals[index];
+        if (base.fSpan->segment() == this && approximately_equal(base.fT, t)) {
+            continue;
+        }
+        SkDVector slope;
+        SkPoint pt;
+        SkDEBUGCODE(sk_bzero(&slope, sizeof(slope)));
+        bool valid = false;
+        if (approximately_zero(t)) {
+            pt = fPts[0];
+        } else if (approximately_equal(t, 1)) {
+            pt = fPts[SkPathOpsVerbToPoints(fVerb)];
+        } else {
+            SkASSERT(between(0, t, 1));
+            pt = this->ptAtT(t);
+            if (SkDPoint::ApproximatelyEqual(pt, base.fPt)) {
+                if (base.fSpan->segment() == this) {
+                    continue;
+                }
+            } else {
+                SkScalar ptXY = pt_xy(pt, dir);
+                if (!approximately_equal(baseXY, ptXY) && (baseXY < ptXY) == checkLessThan) {
+                    continue;
+                }
+                slope = this->dSlopeAtT(t);
+                if (fVerb == SkPath::kCubic_Verb && base.fSpan->segment() == this
+                        && roughly_equal(base.fT, t)
+                        && SkDPoint::RoughlyEqual(pt, base.fPt)) {
+    #if DEBUG_WINDING
+                    SkDebugf("%s (rarely expect this)\n", __FUNCTION__);
+    #endif
+                    continue;
+                }
+                if (fabs(pt_dydx(slope, dir) * 10000) > fabs(pt_dxdy(slope, dir))) {
+                    valid = true;
+                }
+            }
+        }
+        SkOpSpan* span = this->windingSpanAtT(t);
+        if (!span) {
+            valid = false;
+        } else if (!span->windValue() && !span->oppValue()) {
+            continue;
+        }
+        SkOpRayHit* newHit = SkOpTAllocator<SkOpRayHit>::Allocate(allocator);
+        newHit->fNext = *hits;
+        newHit->fPt = pt;
+        newHit->fSlope = slope;
+        newHit->fSpan = span;
+        newHit->fT = t;
+        newHit->fValid = valid;
+        *hits = newHit;
+    }
+}
+
+SkOpSpan* SkOpSegment::windingSpanAtT(double tHit) {
+    SkOpSpan* span = &fHead;
+    SkOpSpanBase* next;
+    do {
+        next = span->next();
+        if (approximately_equal(tHit, next->t())) {
+            return NULL;
+        } 
+        if (tHit < next->t()) {
+            return span;
+        }
+    } while (!next->final() && (span = next->upCast()));
+    return NULL;
+}
+
+static bool hit_compare_x(const SkOpRayHit* a, const SkOpRayHit* b) {
+    return a->fPt.fX < b->fPt.fX;
+}
+
+static bool reverse_hit_compare_x(const SkOpRayHit* a, const SkOpRayHit* b) {
+    return b->fPt.fX  < a->fPt.fX;
+}
+
+static bool hit_compare_y(const SkOpRayHit* a, const SkOpRayHit* b) {
+    return a->fPt.fY < b->fPt.fY;
+}
+
+static bool reverse_hit_compare_y(const SkOpRayHit* a, const SkOpRayHit* b) {
+    return b->fPt.fY  < a->fPt.fY;
+}
+
+static double get_t_guess(int tTry, int* dirOffset) {
+    double t = 0.5;
+    *dirOffset = tTry & 1;
+    int tBase = tTry >> 1;
+    int tBits = 0;
+    while (tTry >>= 1) {
+        t /= 2;
+        ++tBits;
+    }
+    if (tBits) {
+        int tIndex = (tBase - 1) & ((1 << tBits) - 1);
+        t += t * 2 * tIndex;
+    }
+    return t;
+}
+
+bool SkOpSpan::sortableTop(SkOpContour* contourHead) {
+    SkChunkAlloc allocator(1024);
+    int dirOffset;
+    double t = get_t_guess(fTopTTry++, &dirOffset);
+    SkOpRayHit hitBase;
+    SkOpRayDir dir = hitBase.makeTestBase(this, t);
+    if (hitBase.fSlope.fX == 0 && hitBase.fSlope.fY == 0) {
+        return false;
+    }
+    SkOpRayHit* hitHead = &hitBase;
+    dir = static_cast<SkOpRayDir>(static_cast<int>(dir) + dirOffset);
+    SkOpContour* contour = contourHead;
+    do {
+        contour->rayCheck(hitBase, dir, &hitHead, &allocator);
+    } while ((contour = contour->next()));
+    // sort hits
+    SkSTArray<1, SkOpRayHit*> sorted;
+    SkOpRayHit* hit = hitHead;
+    while (hit) {
+        sorted.push_back(hit);
+        hit = hit->fNext;
+    }
+    int count = sorted.count();
+    SkTQSort(sorted.begin(), sorted.end() - 1, xy_index(dir)
+            ? less_than(dir) ? hit_compare_y : reverse_hit_compare_y 
+            : less_than(dir) ? hit_compare_x : reverse_hit_compare_x);
+    // verify windings
+#if DEBUG_WINDING
+    SkDebugf("%s dir=%s seg=%d t=%1.9g pt=(%1.9g,%1.9g)\n", __FUNCTION__, 
+            gDebugRayDirName[static_cast<int>(dir)], hitBase.fSpan->segment()->debugID(),
+            hitBase.fT, hitBase.fPt.fX, hitBase.fPt.fY);
+    for (int index = 0; index < count; ++index) {
+        hit = sorted[index];
+        SkOpSpan* span = hit->fSpan;
+        SkOpSegment* hitSegment = span ? span->segment() : NULL;
+        bool operand = span ? hitSegment->operand() : false;
+        bool ccw = ccw_dxdy(hit->fSlope, dir);
+        SkDebugf("%s [%d] valid=%d operand=%d span=%d ccw=%d ", __FUNCTION__, index,
+                hit->fValid, operand, span ? span->debugID() : -1, ccw);
+        if (span) {
+            hitSegment->dumpPtsInner();
+        }
+        SkDebugf(" t=%1.9g pt=(%1.9g,%1.9g) slope=(%1.9g,%1.9g)\n", hit->fT,
+                hit->fPt.fX, hit->fPt.fY, hit->fSlope.fX, hit->fSlope.fY);
+    }
+#endif
+    const SkPoint* last = NULL;
+    int wind = 0;
+    int oppWind = 0;
+    for (int index = 0; index < count; ++index) {
+        hit = sorted[index];
+        if (!hit->fValid) {
+            return false;
+        }
+        bool ccw = ccw_dxdy(hit->fSlope, dir);
+        SkASSERT(!approximately_zero(hit->fT) || !hit->fValid);
+        SkOpSpan* span = hit->fSpan;
+        SkOpSegment* hitSegment = span->segment();
+        if (!span) {
+            return false;
+        }
+        if (span->windValue() == 0 && span->oppValue() == 0) {
+            continue;
+        }
+        if (last && SkDPoint::ApproximatelyEqual(*last, hit->fPt)) {
+            return false;
+        }
+        if (index < count - 1) {
+            const SkPoint& next = sorted[index + 1]->fPt;
+            if (SkDPoint::ApproximatelyEqual(next, hit->fPt)) {
+                return false;
+            }
+        }
+        bool operand = hitSegment->operand();
+        if (operand) {
+            SkTSwap(wind, oppWind);
+        }
+        int lastWind = wind;
+        int lastOpp = oppWind;
+        int windValue = ccw ? -span->windValue() : span->windValue();
+        int oppValue = ccw ? -span->oppValue() : span->oppValue();
+        wind += windValue;
+        oppWind += oppValue;
+        bool sumSet = false;
+        int spanSum = span->windSum();
+        int windSum = SkOpSegment::UseInnerWinding(lastWind, wind) ? wind : lastWind;
+        if (spanSum == SK_MinS32) {
+            span->setWindSum(windSum);
+            sumSet = true;
+        } else {
+            // the need for this condition suggests that UseInnerWinding is flawed
+            // happened when last = 1 wind = -1
+#if 0
+            SkASSERT((hitSegment->isXor() ? (windSum & 1) == (spanSum & 1) : windSum == spanSum)
+                    || (abs(wind) == abs(lastWind)
+                    && (windSum ^ wind ^ lastWind) == spanSum));
+#endif
+        }
+        int oSpanSum = span->oppSum();
+        int oppSum = SkOpSegment::UseInnerWinding(lastOpp, oppWind) ? oppWind : lastOpp;
+        if (oSpanSum == SK_MinS32) {
+            span->setOppSum(oppSum);
+        } else {
+#if 0
+            SkASSERT(hitSegment->oppXor() ? (oppSum & 1) == (oSpanSum & 1) : oppSum == oSpanSum
+                    || (abs(oppWind) == abs(lastOpp)
+                    && (oppSum ^ oppWind ^ lastOpp) == oSpanSum));
+#endif
+        }
+        if (sumSet) {
+            (void) hitSegment->markAndChaseWinding(span, span->next(), windSum, oppSum, NULL);
+            (void) hitSegment->markAndChaseWinding(span->next(), span, windSum, oppSum, NULL);
+        }
+        if (operand) {
+            SkTSwap(wind, oppWind);
+        }
+        last = &hit->fPt;
+    }
+    return true;
+}
+
+SkOpSpan* SkOpSegment::findSortableTop(SkOpContour* contourHead) {
+    SkOpSpan* span = &fHead;
+    SkOpSpanBase* next;
+    do {
+        next = span->next();
+        if (span->done()) {
+            continue;
+        }
+        if (span->windSum() != SK_MinS32) {
+            return span;
+        }
+        if (span->sortableTop(contourHead)) {
+            return span;
+        }
+    } while (!next->final() && (span = next->upCast()));
+    return NULL;
+}
+
+SkOpSpan* SkOpContour::findSortableTop(SkOpContour* contourHead) {
+    SkOpSegment* testSegment = &fHead;
+    do {
+        if (testSegment->done()) {
+            continue;
+        }
+        SkOpSpan* result = testSegment->findSortableTop(contourHead);
+        if (result) {
+            return result;
+        }
+    } while ((testSegment = testSegment->next()));
+    return NULL;
+}
+
+SkOpSpan* FindSortableTop(SkOpContourHead* contourHead) {
+    for (int index = 0; index < SkOpGlobalState::kMaxWindingTries; ++index) {
+        SkOpContour* contour = contourHead;
+        do {
+            if (contour->done()) {
+                continue;
+            }
+            SkOpSpan* result = contour->findSortableTop(contourHead);
+            if (result) {
+                return result;
+            }
+        } while ((contour = contour->next()));
+    }
+    return NULL;
+}