Convexity checker: Wait for significant x-product when walking edges
This effectively re-applies the logic from
https://codereview.chromium.org/298973004
The change to the unit test for 389050 is interesting.
The last convexity rewrite "fixed" that case by allowing
it to be detected as convex. In the process, it actually
broke the original bug, so that rendering of the HTML
failed. This CL causes us to give up and decide that the
path is concave, but we return to rendering correctly, so
that's a win.
The bug that initiated this (950508) is effectively the
exact same bug as 2235, which is why I haven't added a new
test case. The existing test case is much more concise than
the 100K data file needed for the new one.
Bugs: skia:2235 chromium:389050 chromium:950508
Change-Id: I0de65db8644f37e335c47e9d41c676b8e8b020fc
Reviewed-on: https://skia-review.googlesource.com/c/skia/+/209164
Reviewed-by: Brian Salomon <bsalomon@google.com>
Commit-Queue: Brian Osman <brianosman@google.com>
diff --git a/src/core/SkPath.cpp b/src/core/SkPath.cpp
index 29693a0..6901f19 100644
--- a/src/core/SkPath.cpp
+++ b/src/core/SkPath.cpp
@@ -2592,7 +2592,6 @@
kLeft_DirChange,
kRight_DirChange,
kStraight_DirChange,
- kConcave_DirChange, // if cross on diagonal is too small, assume concave
kBackwards_DirChange, // if double back, allow simple lines to be convex
kInvalid_DirChange
};
@@ -2628,8 +2627,9 @@
}
fCurrPt = pt;
if (fPriorPt == fLastPt) { // should only be true for first non-zero vector
+ fLastVec = fCurrPt - fLastPt;
fFirstPt = pt;
- } else if (!this->addVec()) {
+ } else if (!this->addVec(fCurrPt - fLastPt)) {
return false;
}
fPriorPt = fLastPt;
@@ -2686,10 +2686,8 @@
}
private:
- DirChange directionChange() {
- SkVector lastVec = fLastPt - fPriorPt;
- SkVector curVec = fCurrPt - fLastPt;
- SkScalar cross = SkPoint::CrossProduct(lastVec, curVec);
+ DirChange directionChange(const SkVector& curVec) {
+ SkScalar cross = SkPoint::CrossProduct(fLastVec, curVec);
if (!SkScalarIsFinite(cross)) {
return kUnknown_DirChange;
}
@@ -2698,13 +2696,13 @@
largest = SkTMax(largest, -smallest);
if (almost_equal(largest, largest + cross)) {
- return lastVec.dot(curVec) < 0 ? kBackwards_DirChange : kStraight_DirChange;
+ return fLastVec.dot(curVec) < 0 ? kBackwards_DirChange : kStraight_DirChange;
}
return 1 == SkScalarSignAsInt(cross) ? kRight_DirChange : kLeft_DirChange;
}
- bool addVec() {
- DirChange dir = this->directionChange();
+ bool addVec(const SkVector& curVec) {
+ DirChange dir = this->directionChange(curVec);
switch (dir) {
case kLeft_DirChange: // fall through
case kRight_DirChange:
@@ -2716,17 +2714,16 @@
fFirstDirection = SkPathPriv::kUnknown_FirstDirection;
return false;
}
+ fLastVec = curVec;
break;
case kStraight_DirChange:
break;
- case kConcave_DirChange:
- fFirstDirection = SkPathPriv::kUnknown_FirstDirection;
- return false;
case kBackwards_DirChange:
// allow path to reverse direction twice
// Given path.moveTo(0, 0); path.lineTo(1, 1);
// - 1st reversal: direction change formed by line (0,0 1,1), line (1,1 0,0)
// - 2nd reversal: direction change formed by line (1,1 0,0), line (0,0 1,1)
+ fLastVec = curVec;
return ++fReversals < 3;
case kUnknown_DirChange:
return (fIsFinite = false);
@@ -2741,6 +2738,7 @@
SkPoint fPriorPt {0, 0};
SkPoint fLastPt {0, 0};
SkPoint fCurrPt {0, 0};
+ SkVector fLastVec {0, 0};
DirChange fExpectedDir { kInvalid_DirChange };
SkPathPriv::FirstDirection fFirstDirection { SkPathPriv::kUnknown_FirstDirection };
int fReversals { 0 };
diff --git a/tests/PathTest.cpp b/tests/PathTest.cpp
index e55cb44..a1e170c 100644
--- a/tests/PathTest.cpp
+++ b/tests/PathTest.cpp
@@ -1348,10 +1348,10 @@
tinyConvexPolygon.lineTo(600.134891f, 800.137724f);
tinyConvexPolygon.close();
tinyConvexPolygon.getConvexity();
- check_convexity(reporter, tinyConvexPolygon, SkPath::kConvex_Convexity);
- // lines are close enough to straight that polygon collapses to line that does not
- // enclose area, so has unknown first direction
- check_direction(reporter, tinyConvexPolygon, SkPathPriv::kUnknown_FirstDirection);
+ // This is convex, but so small that it fails many of our checks, and the three "backwards"
+ // bends convince the checker that it's concave. That's okay though, we draw it correctly.
+ check_convexity(reporter, tinyConvexPolygon, SkPath::kConcave_Convexity);
+ check_direction(reporter, tinyConvexPolygon, SkPathPriv::kCW_FirstDirection);
SkPath platTriangle;
platTriangle.moveTo(0, 0);
@@ -1479,7 +1479,7 @@
SkStrokeRec stroke(SkStrokeRec::kFill_InitStyle);
stroke.setStrokeStyle(2 * SK_Scalar1);
stroke.applyToPath(&strokedSin, strokedSin);
- check_convexity(reporter, strokedSin, SkPath::kConvex_Convexity); // !!!
+ check_convexity(reporter, strokedSin, SkPath::kConcave_Convexity);
check_direction(reporter, strokedSin, kDontCheckDir);
// http://crbug.com/412640
