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>
diff --git a/src/core/SkMask.cpp b/src/core/SkMask.cpp
index 7336116..c0875b8 100644
--- a/src/core/SkMask.cpp
+++ b/src/core/SkMask.cpp
@@ -62,12 +62,17 @@
// 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 81b692f..c72f7d4 100755
--- a/src/utils/SkOffsetPolygon.cpp
+++ b/src/utils/SkOffsetPolygon.cpp
@@ -311,6 +311,7 @@
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 @@
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 79f8f22..b454e5f 100755
--- a/src/utils/SkShadowTessellator.cpp
+++ b/src/utils/SkShadowTessellator.cpp
@@ -209,12 +209,10 @@
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 @@
#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 @@
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 @@
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 @@
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 @@
// Middle ring: 0
fIndices.setReserve(12 * path.countPoints());
- this->computePathPolygon(path, ctm);
if (fIsConvex) {
fSucceeded = this->computeConvexShadow();
} else {
@@ -683,7 +698,7 @@
}
}
-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 @@
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) {
- 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;
+ 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:
+ 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 @@
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 @@
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 @@
}
}
+ // 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::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 @@
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 @@
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 @@
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 90c1d8f..07ff6df 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) {
+enum ExpectVerts {
+ kDont_ExpectVerts,
+ kDo_ExpectVerts
+};
- auto heightParams = SkPoint3::Make(0, 0, 4);
+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");
+ }
+ 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);
- 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::MakeAmbient(path, ctm, heightParams, 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);
+
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 @@
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) {