Fix some shadow issues.

* Clamp path polygon points to nearest 1/16th of a pixel to help
  with floating point issues.
* Added check for multiple contour paths.
* Return empty SkVertices for certain degenerate cases to avoid
  unnecessary blurs.
* Check iteration count in SkOffsetPolygon to avoid infinite loops.
* Add new tests to verify these.

Bug: skia:
Change-Id: Ie6ad48d2504e065dcc822609d369f90c56ef3ad3
Reviewed-on: https://skia-review.googlesource.com/136701
Reviewed-by: Brian Salomon <bsalomon@google.com>
Commit-Queue: Jim Van Verth <jvanverth@google.com>

4 files changed, 177 insertions, 69 deletions

diff --git a/src/core/SkMask.cpp b/src/core/SkMask.cpp
index 7336116f93..c0875b84e8 100644
--- a/src/core/SkMask.cpp
+++ b/src/core/SkMask.cpp
@@ -62,12 +62,17 @@ SkMask SkMask::PrepareDestination(int radiusX, int radiusY, const SkMask& src) {
     // dstH = srcH + 2 * radiusY;
     size_t dstH = safe.add(src.fBounds.height(), safe.add(radiusY, radiusY));
 
-    dst.fBounds.set(0, 0, SkTo<int>(dstW), SkTo<int>(dstH));
-    dst.fBounds.offset(src.fBounds.x(), src.fBounds.y());
-    dst.fBounds.offset(-radiusX, -radiusY);
+    if (!SkTFitsIn<int>(dstW) || !SkTFitsIn<int>(dstH)) {
+        dst.fBounds.setEmpty();
+        dst.fRowBytes = 0;
+    } else {
+        dst.fBounds.set(0, 0, SkTo<int>(dstW), SkTo<int>(dstH));
+        dst.fBounds.offset(src.fBounds.x(), src.fBounds.y());
+        dst.fBounds.offset(-radiusX, -radiusY);
+        dst.fRowBytes = SkTo<uint32_t>(dstW);
+    }
 
     dst.fImage = nullptr;
-    dst.fRowBytes = SkTo<uint32_t>(dstW);
     dst.fFormat = SkMask::kA8_Format;
 
     size_t toAlloc = safe.mul(dstW, dstH);
diff --git a/src/utils/SkOffsetPolygon.cpp b/src/utils/SkOffsetPolygon.cpp
index 81b692f1bf..c72f7d407b 100755
--- a/src/utils/SkOffsetPolygon.cpp
+++ b/src/utils/SkOffsetPolygon.cpp
@@ -311,6 +311,7 @@ bool SkInsetConvexPolygon(const SkPoint* inputPolygonVerts, int inputPolygonSize
     int iterations = 0;
     while (prevIndex != currIndex) {
         ++iterations;
+        // we should check each edge against each other edge at most once
         if (iterations > inputPolygonSize*inputPolygonSize) {
             return false;
         }
@@ -698,7 +699,14 @@ bool SkOffsetSimplePolygon(const SkPoint* inputPolygonVerts, int inputPolygonSiz
     prevIndex = edgeDataSize - 1;
     currIndex = 0;
     int insetVertexCount = edgeDataSize;
+    int iterations = 0;
     while (prevIndex != currIndex) {
+        ++iterations;
+        // we should check each edge against each other edge at most once
+        if (iterations > edgeDataSize*edgeDataSize) {
+            return false;
+        }
+
         if (!edgeData[prevIndex].fValid) {
             prevIndex = (prevIndex + edgeDataSize - 1) % edgeDataSize;
             continue;
diff --git a/src/utils/SkShadowTessellator.cpp b/src/utils/SkShadowTessellator.cpp
index 79f8f22636..b454e5f103 100755
--- a/src/utils/SkShadowTessellator.cpp
+++ b/src/utils/SkShadowTessellator.cpp
@@ -209,12 +209,10 @@ bool SkBaseShadowTessellator::accumulateCentroid(const SkPoint& curr, const SkPo
     fCentroid.fY += (curr.fY + next.fY) * quadArea;
     fArea += quadArea;
     // convexity check
-    if (!SkScalarNearlyZero(quadArea)) {
-        if (quadArea*fLastArea < 0) {
-            ++fAreaSignFlips;
-        }
-        fLastArea = quadArea;
+    if (quadArea*fLastArea < 0) {
+        ++fAreaSignFlips;
     }
+    fLastArea = quadArea;
 
     return true;
 }
@@ -400,9 +398,18 @@ static const SkScalar kCubicTolerance = 0.2f;
 #endif
 static const SkScalar kConicTolerance = 0.5f;
 
+// clamps the point to the nearest 16th of a pixel
+static void sanitize_point(const SkPoint& in, SkPoint* out) {
+    out->fX = SkScalarRoundToScalar(16.f*in.fX)*0.0625f;
+    out->fY = SkScalarRoundToScalar(16.f*in.fY)*0.0625f;
+}
+
 void SkBaseShadowTessellator::handleLine(const SkPoint& p) {
+    SkPoint pSanitized;
+    sanitize_point(p, &pSanitized);
+
     if (fPathPolygon.count() > 0) {
-        if (!this->accumulateCentroid(fPathPolygon[fPathPolygon.count() - 1], p)) {
+        if (!this->accumulateCentroid(fPathPolygon[fPathPolygon.count() - 1], pSanitized)) {
             // skip coincident point
             return;
         }
@@ -411,13 +418,13 @@ void SkBaseShadowTessellator::handleLine(const SkPoint& p) {
     if (fPathPolygon.count() > 1) {
         if (!checkConvexity(fPathPolygon[fPathPolygon.count() - 2],
                             fPathPolygon[fPathPolygon.count() - 1],
-                            p)) {
+                            pSanitized)) {
             // remove collinear point
             fPathPolygon.pop();
         }
     }
 
-    *fPathPolygon.push() = p;
+    *fPathPolygon.push() = pSanitized;
 }
 
 void SkBaseShadowTessellator::handleLine(const SkMatrix& m, SkPoint* p) {
@@ -618,7 +625,7 @@ public:
                                const SkPoint3& zPlaneParams, bool transparent);
 
 private:
-    void computePathPolygon(const SkPath& path, const SkMatrix& ctm);
+    bool computePathPolygon(const SkPath& path, const SkMatrix& ctm);
     bool computeConvexShadow();
     bool computeConcaveShadow();
 
@@ -667,6 +674,15 @@ SkAmbientShadowTessellator::SkAmbientShadowTessellator(const SkPath& path,
         return;
     }
 
+    if (!this->computePathPolygon(path, ctm)) {
+        return;
+    }
+    if (fPathPolygon.count() < 3 || !SkScalarIsFinite(fArea)) {
+        fSucceeded = true; // We don't want to try to blur these cases, so we will
+                           // return an empty SkVertices instead.
+        return;
+    }
+
     // Outer ring: 3*numPts
     // Middle ring: numPts
     fPositions.setReserve(4 * path.countPoints());
@@ -675,7 +691,6 @@ SkAmbientShadowTessellator::SkAmbientShadowTessellator(const SkPath& path,
     // Middle ring: 0
     fIndices.setReserve(12 * path.countPoints());
 
-    this->computePathPolygon(path, ctm);
     if (fIsConvex) {
         fSucceeded = this->computeConvexShadow();
     } else {
@@ -683,7 +698,7 @@ SkAmbientShadowTessellator::SkAmbientShadowTessellator(const SkPath& path,
     }
 }
 
-void SkAmbientShadowTessellator::computePathPolygon(const SkPath& path, const SkMatrix& ctm) {
+bool SkAmbientShadowTessellator::computePathPolygon(const SkPath& path, const SkMatrix& ctm) {
     fPathPolygon.setReserve(path.countPoints());
 
     // walk around the path, tessellate and generate outer ring
@@ -691,28 +706,40 @@ void SkAmbientShadowTessellator::computePathPolygon(const SkPath& path, const Sk
     SkPath::Iter iter(path, true);
     SkPoint pts[4];
     SkPath::Verb verb;
+    bool verbSeen = false;
+    bool closeSeen = false;
     while ((verb = iter.next(pts)) != SkPath::kDone_Verb) {
+        if (closeSeen) {
+            return false;
+        }
         switch (verb) {
-        case SkPath::kLine_Verb:
-            this->handleLine(ctm, &pts[1]);
-            break;
-        case SkPath::kQuad_Verb:
-            this->handleQuad(ctm, pts);
-            break;
-        case SkPath::kCubic_Verb:
-            this->handleCubic(ctm, pts);
-            break;
-        case SkPath::kConic_Verb:
-            this->handleConic(ctm, pts, iter.conicWeight());
-            break;
-        case SkPath::kMove_Verb:
-        case SkPath::kClose_Verb:
-        case SkPath::kDone_Verb:
-            break;
+            case SkPath::kLine_Verb:
+                this->handleLine(ctm, &pts[1]);
+                break;
+            case SkPath::kQuad_Verb:
+                this->handleQuad(ctm, pts);
+                break;
+            case SkPath::kCubic_Verb:
+                this->handleCubic(ctm, pts);
+                break;
+            case SkPath::kConic_Verb:
+                this->handleConic(ctm, pts, iter.conicWeight());
+                break;
+            case SkPath::kMove_Verb:
+                if (verbSeen) {
+                    return false;
+                }
+                break;
+            case SkPath::kClose_Verb:
+            case SkPath::kDone_Verb:
+                closeSeen = true;
+                break;
         }
+        verbSeen = true;
     }
 
     this->finishPathPolygon();
+    return true;
 }
 
 bool SkAmbientShadowTessellator::computeConvexShadow() {
@@ -945,7 +972,7 @@ public:
                             SkScalar lightRadius, bool transparent);
 
 private:
-    void computeClipAndPathPolygons(const SkPath& path, const SkMatrix& ctm,
+    bool computeClipAndPathPolygons(const SkPath& path, const SkMatrix& ctm,
                                     const SkMatrix& shadowTransform);
     void computeClipVectorsAndTestCentroid();
     bool clipUmbraPoint(const SkPoint& umbraPoint, const SkPoint& centroid, SkPoint* clipPoint);
@@ -1035,20 +1062,13 @@ SkSpotShadowTessellator::SkSpotShadowTessellator(const SkPath& path, const SkMat
         return;
     }
 
-    // TODO: calculate these reserves better
-    // Penumbra ring: 3*numPts
-    // Umbra ring: numPts
-    // Inner ring: numPts
-    fPositions.setReserve(5 * path.countPoints());
-    fColors.setReserve(5 * path.countPoints());
-    // Penumbra ring: 12*numPts
-    // Umbra ring: 3*numPts
-    fIndices.setReserve(15 * path.countPoints());
-    fClipPolygon.setReserve(path.countPoints());
-
     // compute rough clip bounds for umbra, plus offset polygon, plus centroid
-    this->computeClipAndPathPolygons(path, ctm, shadowTransform);
-    if (fClipPolygon.count() < 3 || fPathPolygon.count() < 3) {
+    if (!this->computeClipAndPathPolygons(path, ctm, shadowTransform)) {
+        return;
+    }
+    if (fClipPolygon.count() < 3 || fPathPolygon.count() < 3 || !SkScalarIsFinite(fArea)) {
+        fSucceeded = true; // We don't want to try to blur these cases, so we will
+                           // return an empty SkVertices instead.
         return;
     }
 
@@ -1087,6 +1107,16 @@ SkSpotShadowTessellator::SkSpotShadowTessellator(const SkPath& path, const SkMat
         }
     }
 
+    // TODO: calculate these reserves better
+    // Penumbra ring: 3*numPts
+    // Umbra ring: numPts
+    // Inner ring: numPts
+    fPositions.setReserve(5 * path.countPoints());
+    fColors.setReserve(5 * path.countPoints());
+    // Penumbra ring: 12*numPts
+    // Umbra ring: 3*numPts
+    fIndices.setReserve(15 * path.countPoints());
+
     if (fIsConvex) {
         fSucceeded = this->computeConvexShadow(radius);
     } else {
@@ -1134,10 +1164,11 @@ void SkSpotShadowTessellator::addToClip(const SkPoint& point) {
     }
 }
 
-void SkSpotShadowTessellator::computeClipAndPathPolygons(const SkPath& path, const SkMatrix& ctm,
+bool SkSpotShadowTessellator::computeClipAndPathPolygons(const SkPath& path, const SkMatrix& ctm,
                                                          const SkMatrix& shadowTransform) {
 
     fPathPolygon.setReserve(path.countPoints());
+    fClipPolygon.setReserve(path.countPoints());
 
     // Walk around the path and compute clip polygon and path polygon.
     // Will also accumulate sum of areas for centroid.
@@ -1146,8 +1177,6 @@ void SkSpotShadowTessellator::computeClipAndPathPolygons(const SkPath& path, con
     SkPoint pts[4];
     SkPath::Verb verb;
 
-    fClipPolygon.reset();
-
     // coefficients to compute cubic Bezier at t = 5/16
     static constexpr SkScalar kA = 0.32495117187f;
     static constexpr SkScalar kB = 0.44311523437f;
@@ -1156,7 +1185,12 @@ void SkSpotShadowTessellator::computeClipAndPathPolygons(const SkPath& path, con
 
     SkPoint curvePoint;
     SkScalar w;
+    bool closeSeen = false;
+    bool verbSeen = false;
     while ((verb = iter.next(pts)) != SkPath::kDone_Verb) {
+        if (closeSeen) {
+            return false;
+        }
         switch (verb) {
             case SkPath::kLine_Verb:
                 ctm.mapPoints(&pts[1], 1);
@@ -1197,16 +1231,23 @@ void SkSpotShadowTessellator::computeClipAndPathPolygons(const SkPath& path, con
                 this->handleCubic(shadowTransform, pts);
                 break;
             case SkPath::kMove_Verb:
+                if (verbSeen) {
+                    return false;
+                }
+                break;
             case SkPath::kClose_Verb:
             case SkPath::kDone_Verb:
+                closeSeen = true;
                 break;
             default:
                 SkDEBUGFAIL("unknown verb");
         }
+        verbSeen = true;
     }
 
     this->finishPathPolygon();
     fCurrClipPoint = fClipPolygon.count() - 1;
+    return true;
 }
 
 void SkSpotShadowTessellator::computeClipVectorsAndTestCentroid() {
diff --git a/tests/ShadowTest.cpp b/tests/ShadowTest.cpp
index 90c1d8ffcc..07ff6dfdce 100644
--- a/tests/ShadowTest.cpp
+++ b/tests/ShadowTest.cpp
@@ -13,31 +13,40 @@
 #include "SkVertices.h"
 #include "Test.h"
 
-void tessellate_shadow(skiatest::Reporter* reporter, const SkPath& path, const SkMatrix& ctm,
-                       bool expectSuccess) {
-
-    auto heightParams = SkPoint3::Make(0, 0, 4);
+enum ExpectVerts {
+    kDont_ExpectVerts,
+    kDo_ExpectVerts
+};
 
-    auto verts = SkShadowTessellator::MakeAmbient(path, ctm, heightParams, true);
+void check_result(skiatest::Reporter* reporter, sk_sp<SkVertices> verts,
+                  ExpectVerts expectVerts, bool expectSuccess) {
     if (expectSuccess != SkToBool(verts)) {
         ERRORF(reporter, "Expected shadow tessellation to %s but it did not.",
                expectSuccess ? "succeed" : "fail");
     }
-    verts = SkShadowTessellator::MakeAmbient(path, ctm, heightParams, false);
-    if (expectSuccess != SkToBool(verts)) {
-        ERRORF(reporter, "Expected shadow tessellation to %s but it did not.",
-               expectSuccess ? "succeed" : "fail");
+    if (SkToBool(verts)) {
+        if (kDont_ExpectVerts == expectVerts && verts->vertexCount()) {
+            ERRORF(reporter, "Expected shadow tessellation to generate no vertices but it did.");
+        } else if (kDo_ExpectVerts == expectVerts && !verts->vertexCount()) {
+            ERRORF(reporter, "Expected shadow tessellation to generate vertices but it didn't.");
+        }
     }
+}
+
+void tessellate_shadow(skiatest::Reporter* reporter, const SkPath& path, const SkMatrix& ctm,
+                       const SkPoint3& heightParams, ExpectVerts expectVerts, bool expectSuccess) {
+
+    auto verts = SkShadowTessellator::MakeAmbient(path, ctm, heightParams, true);
+    check_result(reporter, verts, expectVerts, expectSuccess);
+
+    verts = SkShadowTessellator::MakeAmbient(path, ctm, heightParams, false);
+    check_result(reporter, verts, expectVerts, expectSuccess);
+
     verts = SkShadowTessellator::MakeSpot(path, ctm, heightParams, {0, 0, 128}, 128.f, false);
-    if (expectSuccess != SkToBool(verts)) {
-        ERRORF(reporter, "Expected shadow tessellation to %s but it did not.",
-               expectSuccess ? "succeed" : "fail");
-    }
+    check_result(reporter, verts, expectVerts, expectSuccess);
+
     verts = SkShadowTessellator::MakeSpot(path, ctm, heightParams, {0, 0, 128}, 128.f, false);
-    if (expectSuccess != SkToBool(verts)) {
-        ERRORF(reporter, "Expected shadow tessellation to %s but it did not.",
-               expectSuccess ? "succeed" : "fail");
-    }
+    check_result(reporter, verts, expectVerts, expectSuccess);
 }
 
 DEF_TEST(ShadowUtils, reporter) {
@@ -45,19 +54,64 @@ DEF_TEST(ShadowUtils, reporter) {
 
     SkPath path;
     path.cubicTo(100, 50, 20, 100, 0, 0);
-    tessellate_shadow(reporter, path, canvas.getTotalMatrix(), true);
+    tessellate_shadow(reporter, path, canvas.getTotalMatrix(), {0, 0, 4}, kDo_ExpectVerts, true);
+    // super high path
+    tessellate_shadow(reporter, path, canvas.getTotalMatrix(), {0, 0, 4.0e+37f},
+                      kDo_ExpectVerts, true);
 
     // This line segment has no area and no shadow.
     path.reset();
     path.lineTo(10.f, 10.f);
-    tessellate_shadow(reporter, path, canvas.getTotalMatrix(), false);
+    tessellate_shadow(reporter, path, canvas.getTotalMatrix(), {0, 0, 4}, kDont_ExpectVerts, true);
 
-    // A series of colinear line segments
+    // A series of collinear line segments
     path.reset();
     for (int i = 0; i < 10; ++i) {
         path.lineTo((SkScalar)i, (SkScalar)i);
     }
-    tessellate_shadow(reporter, path, canvas.getTotalMatrix(), false);
+    tessellate_shadow(reporter, path, canvas.getTotalMatrix(), {0, 0, 4}, kDont_ExpectVerts, true);
+
+    // ugly degenerate path
+    path.reset();
+    path.moveTo(-134217728, 2.22265153e+21f);
+    path.cubicTo(-2.33326106e+21f, 7.36298265e-41f, 3.72237738e-22f, 5.99502692e-36f,
+                 1.13631943e+22f, 2.0890786e+33f);
+    path.cubicTo(1.03397626e-25f, 5.99502692e-36f, 9.18354962e-41f, 0, 4.6142745e-37f, -213558848);
+    path.lineTo(-134217728, 2.2226515e+21f);
+    tessellate_shadow(reporter, path, canvas.getTotalMatrix(), {0, 0, 9}, kDont_ExpectVerts, true);
+
+    // simple concave path (star of David)
+    path.reset();
+    path.moveTo(0.0f, -50.0f);
+    path.lineTo(14.43f, -25.0f);
+    path.lineTo(43.30f, -25.0f);
+    path.lineTo(28.86f, 0.0f);
+    path.lineTo(43.30f, 25.0f);
+    path.lineTo(14.43f, 25.0f);
+    path.lineTo(0.0f, 50.0f);
+    path.lineTo(-14.43f, 25.0f);
+    path.lineTo(-43.30f, 25.0f);
+    path.lineTo(-28.86f, 0.0f);
+    path.lineTo(-43.30f, -25.0f);
+    path.lineTo(-14.43f, -25.0f);
+// uncomment when transparent concave shadows are working
+//    tessellate_shadow(reporter, path, canvas.getTotalMatrix(), {0, 0, 9}, kDo_ExpectVerts, true);
+
+    // complex concave path (bowtie)
+    path.reset();
+    path.moveTo(-50, -50);
+    path.lineTo(-50, 50);
+    path.lineTo(50, -50);
+    path.lineTo(50, 50);
+    path.lineTo(-50, -50);
+    tessellate_shadow(reporter, path, canvas.getTotalMatrix(), {0, 0, 9}, kDont_ExpectVerts, false);
+
+    // multiple contour path
+    path.close();
+    path.moveTo(0, 0);
+    path.lineTo(1, 0);
+    path.lineTo(0, 1);
+    tessellate_shadow(reporter, path, canvas.getTotalMatrix(), {0, 0, 9}, kDont_ExpectVerts, false);
 }
 
 void check_xformed_bounds(skiatest::Reporter* reporter, const SkPath& path, const SkMatrix& ctm) {