fix ops for very close rects

Pathops sorts line intersections to determine which edges to keep.
If the intersections are very short, they may get discarded and the
adjacent edge is used instead.

If a pair of edges are 180 degrees apart, and an adjacent edge is
part of the sort, it is ambiguous whether it is inside or outside
the span. Add logic to look for this and evaluate the original data
rather than the adjacent edge.

In a separate CL, I'll add a specialization for rect/rect ops.

R=halcanary@google.com
Bug: skia:8049
Change-Id: I8d88d5520051d41303ea683e7d6b844f2afa9937
Reviewed-on: https://skia-review.googlesource.com/132661
Commit-Queue: Hal Canary <halcanary@google.com>
Reviewed-by: Hal Canary <halcanary@google.com>
Auto-Submit: Cary Clark <caryclark@skia.org>

2 files changed, 69 insertions, 1 deletions

diff --git a/src/pathops/SkOpAngle.cpp b/src/pathops/SkOpAngle.cpp
index c07e8cc73f..194260f658 100644
--- a/src/pathops/SkOpAngle.cpp
+++ b/src/pathops/SkOpAngle.cpp
@@ -135,7 +135,7 @@ bool SkOpAngle::after(SkOpAngle* test) {
     }
     int trOrder;
     if (rh->fSectorMask & fSectorMask) {
-        trOrder = (int) orderable(rh);
+        trOrder = (int) this->orderable(rh);
     } else {
         int trGap = (rh->fSectorStart - fSectorStart + 32) & 0x1f;
         trOrder = trGap > 20 ? 0 : trGap > 11 ? -1 : 1;
@@ -167,6 +167,41 @@ bool SkOpAngle::after(SkOpAngle* test) {
 //        SkASSERT(lrOpposite != trOpposite);
         return COMPARE_RESULT(10, lrOpposite);
     }
+    // if a pair couldn't be ordered, there's not enough information to determine the sort
+    if (fUnorderable || lh->fUnorderable || rh->fUnorderable) {
+        // limit to lines; should work with curves, but wait for a failing test to verify
+        if (!fPart.isCurve() && !lh->fPart.isCurve() && !rh->fPart.isCurve()) {
+            // see if original raw data is orderable
+            // if two share a point, check if third has both points in same half plane
+            int ltShare = lh->fOriginalCurvePart[0] == fOriginalCurvePart[0];
+            int lrShare = lh->fOriginalCurvePart[0] == rh->fOriginalCurvePart[0];
+            int trShare = fOriginalCurvePart[0] == rh->fOriginalCurvePart[0];
+            // if only one pair are the same, the third point touches neither of the pair
+            if (ltShare + lrShare + trShare == 1) {
+                if (ltShare) {
+                    int lrOOrder = lh->allOnOriginalSide(rh);
+                    int trOOrder = rh->allOnOriginalSide(this);
+                    // result must be 0 and 1 or 1 and 0 to be valid
+                    if ((lrOOrder ^ trOOrder) == 1) {
+                        return trOOrder;
+                    }
+                } else if (lrShare) {
+                    int ltOOrder = lh->allOnOriginalSide(this);
+                    int trOOrder = rh->allOnOriginalSide(this);
+                    if ((ltOOrder ^ trOOrder) == 1) {
+                        return ltOOrder;
+                    }
+                } else {
+                    SkASSERT(trShare);
+                    int ltOOrder = this->allOnOriginalSide(lh);
+                    int lrOOrder = rh->allOnOriginalSide(lh);
+                    if ((ltOOrder ^ lrOOrder) == 1) {
+                        return lrOOrder;
+                    }
+                }
+            }
+        }
+    }
     if (lrOrder < 0) {
         if (ltOrder < 0) {
             return COMPARE_RESULT(11, trOrder);
@@ -214,6 +249,38 @@ int SkOpAngle::allOnOneSide(const SkOpAngle* test) {
     return -1;
 }
 
+// experiment works only with lines for now
+int SkOpAngle::allOnOriginalSide(const SkOpAngle* test) {
+    SkASSERT(!fPart.isCurve());
+    SkASSERT(!test->fPart.isCurve());
+    SkDPoint origin = fOriginalCurvePart[0];
+    SkDVector line = fOriginalCurvePart[1] - origin;
+    double dots[2];
+    double crosses[2];
+    const SkDCurve& testCurve = test->fOriginalCurvePart;
+    for (int index = 0; index < 2; ++index) {
+        SkDVector testLine = testCurve[index] - origin;
+        double xy1 = line.fX * testLine.fY;
+        double xy2 = line.fY * testLine.fX;
+        dots[index] = line.fX * testLine.fX + line.fY * testLine.fY;
+        crosses[index] = AlmostBequalUlps(xy1, xy2) ? 0 : xy1 - xy2;
+    }
+    if (crosses[0] * crosses[1] < 0) {
+        return -1;
+    }
+    if (crosses[0]) {
+        return crosses[0] < 0;
+    }
+    if (crosses[1]) {
+        return crosses[1] < 0;
+    }
+    if ((!dots[0] && dots[1] < 0) || (dots[0] < 0 && !dots[1])) {
+        return 2;  // 180 degrees apart
+    }
+    fUnorderable = true;
+    return -1;
+}
+
 // To sort the angles, all curves are translated to have the same starting point.
 // If the curve's control point in its original position is on one side of a compared line,
 // and translated is on the opposite side, reverse the previously computed order.
diff --git a/src/pathops/SkOpAngle.h b/src/pathops/SkOpAngle.h
index d8615c3229..3d7a8950eb 100644
--- a/src/pathops/SkOpAngle.h
+++ b/src/pathops/SkOpAngle.h
@@ -99,6 +99,7 @@ private:
     bool after(SkOpAngle* test);
     void alignmentSameSide(const SkOpAngle* test, int* order) const;
     int allOnOneSide(const SkOpAngle* test);
+    int allOnOriginalSide(const SkOpAngle* test);
     bool checkCrossesZero() const;
     bool checkParallel(SkOpAngle* );
     bool computeSector();