Path ops formerly found the topmost unprocessed edge and determined its angle sort order to initialize the winding. This never worked correctly with cubics and was flaky with paths consisting mostly of vertical edges.

This replacement shoots axis-aligned rays through all intersecting edges to find the outermost one either horizontally or vertically. The resulting code is smaller and twice as fast.

To support this, most of the horizontal / vertical intersection code was rewritten and standardized, and old code supporting the top-directed winding was deleted.

Contours were pointed to by an SkTDArray. Instead, put them in a linked list, and designate the list head with its own class to ensure that methods that take lists of contours start at the top. This change removed a large percentage of memory allocations used by path ops.

TBR=reed@google.com
BUG=skia:3588

Review URL: https://codereview.chromium.org/1111333002

1 files changed, 402 insertions, 0 deletions

diff --git a/src/pathops/SkPathOpsWinding.cpp b/src/pathops/SkPathOpsWinding.cpp
new file mode 100644
index 0000000000..53083e484e
--- /dev/null
+++ b/src/pathops/SkPathOpsWinding.cpp
@@ -0,0 +1,402 @@
+/*
+ * 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;
+}