Add more tests for PolyUtils
* Add fuzzer
* Add bench tests
* Add additional unit test
* Fix some bugs these exposed.
Bug: skia:
Change-Id: I6c587c92cb6cff32ab8300020b78f9f247d2bf64
Reviewed-on: https://skia-review.googlesource.com/139169
Commit-Queue: Jim Van Verth <jvanverth@google.com>
Reviewed-by: Kevin Lubick <kjlubick@google.com>
Reviewed-by: Robert Phillips <robertphillips@google.com>
diff --git a/BUILD.gn b/BUILD.gn
index f10d232..11b1943 100644
--- a/BUILD.gn
+++ b/BUILD.gn
@@ -1749,6 +1749,7 @@
"fuzz/FuzzParsePath.cpp",
"fuzz/FuzzPathMeasure.cpp",
"fuzz/FuzzPathop.cpp",
+ "fuzz/FuzzPolyUtils.cpp",
"fuzz/FuzzRegionOp.cpp",
"fuzz/fuzz.cpp",
"fuzz/oss_fuzz/FuzzAnimatedImage.cpp",
diff --git a/bench/PolyUtilsBench.cpp b/bench/PolyUtilsBench.cpp
new file mode 100644
index 0000000..1b987fa
--- /dev/null
+++ b/bench/PolyUtilsBench.cpp
@@ -0,0 +1,130 @@
+/*
+ * Copyright 2018 Google Inc.
+ *
+ * Use of this source code is governed by a BSD-style license that can be
+ * found in the LICENSE file.
+ */
+
+#include "Benchmark.h"
+#include "SkPolyUtils.h"
+
+class PolyUtilsBench : public Benchmark {
+ // Evaluate SkTriangulateSimplePolygon's performance (via derived classes) on:
+ // a non-self-intersecting star, a circle of tiny line segments and a self-intersecting star
+
+ SkString fName;
+public:
+ PolyUtilsBench() {}
+
+ virtual void appendName(SkString*) = 0;
+ virtual void makePoly(SkTDArray<SkPoint>* poly) = 0;
+ virtual int complexity() { return 0; }
+
+protected:
+ const char* onGetName() override {
+ fName = "poly_utils_";
+ this->appendName(&fName);
+ return fName.c_str();
+ }
+
+ void onDraw(int loops, SkCanvas* canvas) override {
+ SkTDArray<SkPoint> poly;
+ this->makePoly(&poly);
+ SkAutoSTMalloc<64, uint16_t> indexMap(poly.count());
+ for (int i = 0; i < poly.count(); ++i) {
+ indexMap[i] = i;
+ }
+ SkTDArray<uint16_t> triangleIndices;
+ for (int i = 0; i < loops; i++) {
+ if (SkIsSimplePolygon(poly.begin(), poly.count())) {
+ SkTriangulateSimplePolygon(poly.begin(), indexMap, poly.count(),
+ &triangleIndices);
+ }
+ }
+ }
+
+private:
+ typedef Benchmark INHERITED;
+};
+
+class StarPolyUtilsBench : public PolyUtilsBench {
+public:
+ StarPolyUtilsBench() {}
+
+ void appendName(SkString* name) override {
+ name->append("star");
+ }
+ void makePoly(SkTDArray<SkPoint>* poly) override {
+ // create non-intersecting star
+ const SkScalar c = SkIntToScalar(45);
+ const SkScalar r1 = SkIntToScalar(20);
+ const SkScalar r2 = SkIntToScalar(3);
+ const int n = 500;
+ SkScalar rad = 0;
+ const SkScalar drad = SK_ScalarPI / n;
+ for (int i = 0; i < n; i++) {
+ SkScalar cosV, sinV = SkScalarSinCos(rad, &cosV);
+ *poly->push() = SkPoint::Make(c + cosV * r1, c + sinV * r1);
+ rad += drad;
+ sinV = SkScalarSinCos(rad, &cosV);
+ *poly->push() = SkPoint::Make(c + cosV * r2, c + sinV * r2);
+ rad += drad;
+ }
+ }
+private:
+ typedef PolyUtilsBench INHERITED;
+};
+
+class CirclePolyUtilsBench : public PolyUtilsBench {
+public:
+ CirclePolyUtilsBench() {}
+
+ void appendName(SkString* name) override {
+ name->append("circle");
+ }
+ void makePoly(SkTDArray<SkPoint>* poly) override {
+ // create circle with many vertices
+ const SkScalar c = SkIntToScalar(45);
+ const SkScalar r = SkIntToScalar(20);
+ const int n = 1000;
+ SkScalar rad = 0;
+ const SkScalar drad = 2 * SK_ScalarPI / n;
+ for (int i = 0; i < n; i++) {
+ SkScalar cosV, sinV = SkScalarSinCos(rad, &cosV);
+ *poly->push() = SkPoint::Make(c + cosV * r, c + sinV * r);
+ rad += drad;
+ }
+ }
+private:
+ typedef PolyUtilsBench INHERITED;
+};
+
+class IntersectingPolyUtilsBench : public PolyUtilsBench {
+public:
+ IntersectingPolyUtilsBench() {}
+
+ void appendName(SkString* name) override {
+ name->append("intersecting");
+ }
+ void makePoly(SkTDArray<SkPoint>* poly) override {
+ // create self-intersecting star
+ const SkScalar c = SkIntToScalar(45);
+ const SkScalar r = SkIntToScalar(20);
+ const int n = 1000;
+
+ SkScalar rad = -SK_ScalarPI / 2;
+ const SkScalar drad = (n >> 1) * SK_ScalarPI * 2 / n;
+ *poly->push() = SkPoint::Make(c, c - r);
+ for (int i = 1; i < n; i++) {
+ rad += drad;
+ SkScalar cosV, sinV = SkScalarSinCos(rad, &cosV);
+ *poly->push() = SkPoint::Make(c + cosV * r, c + sinV * r);
+ }
+ }
+private:
+ typedef PolyUtilsBench INHERITED;
+};
+
+DEF_BENCH(return new StarPolyUtilsBench();)
+DEF_BENCH(return new CirclePolyUtilsBench();)
+DEF_BENCH(return new IntersectingPolyUtilsBench();)
diff --git a/fuzz/FuzzPolyUtils.cpp b/fuzz/FuzzPolyUtils.cpp
new file mode 100644
index 0000000..fda5b5f
--- /dev/null
+++ b/fuzz/FuzzPolyUtils.cpp
@@ -0,0 +1,48 @@
+/*
+ * Copyright 2018 Google LLC
+ *
+ * Use of this source code is governed by a BSD-style license that can be
+ * found in the LICENSE file.
+ */
+
+#include "Fuzz.h"
+#include "FuzzCommon.h"
+#include "SkPolyUtils.h"
+
+void inline ignoreResult(bool ) {}
+
+DEF_FUZZ(PolyUtils, fuzz) {
+ int count;
+ fuzz->nextRange(&count, 0, 512);
+ SkAutoSTMalloc<64, SkPoint> polygon(count);
+ for (int index = 0; index < count; ++index) {
+ fuzz->next(&polygon[index].fX, &polygon[index].fY);
+ }
+
+ ignoreResult(SkGetPolygonWinding(polygon, count));
+ ignoreResult(SkIsConvexPolygon(polygon, count));
+ ignoreResult(SkIsSimplePolygon(polygon, count));
+
+ SkScalar inset;
+ fuzz->next(&inset);
+ SkTDArray<SkPoint> output;
+ ignoreResult(SkInsetConvexPolygon(polygon, count, inset, &output));
+ std::function<SkScalar(const SkPoint&)> distanceFunc = [fuzz](const SkPoint& p) {
+ SkScalar retVal;
+ fuzz->next(&retVal);
+ return retVal;
+ };
+ ignoreResult(SkInsetConvexPolygon(polygon, count, distanceFunc, &output));
+
+ SkScalar offset;
+ fuzz->next(&offset);
+ ignoreResult(SkOffsetSimplePolygon(polygon, count, offset, &output));
+ ignoreResult(SkOffsetSimplePolygon(polygon, count, distanceFunc, &output));
+
+ SkAutoSTMalloc<64, uint16_t> indexMap(count);
+ for (int index = 0; index < count; ++index) {
+ fuzz->next(&indexMap[index]);
+ }
+ SkTDArray<uint16_t> outputIndices;
+ ignoreResult(SkTriangulateSimplePolygon(polygon, indexMap, count, &outputIndices));
+}
diff --git a/gn/bench.gni b/gn/bench.gni
index ab18703..688636d 100644
--- a/gn/bench.gni
+++ b/gn/bench.gni
@@ -86,6 +86,7 @@
"$_bench/PictureNestingBench.cpp",
"$_bench/PictureOverheadBench.cpp",
"$_bench/PicturePlaybackBench.cpp",
+ "$_bench/PolyUtilsBench.cpp",
"$_bench/PremulAndUnpremulAlphaOpsBench.cpp",
"$_bench/QuickRejectBench.cpp",
"$_bench/ReadPixBench.cpp",
diff --git a/src/utils/SkPolyUtils.cpp b/src/utils/SkPolyUtils.cpp
index e323f21..b76d270 100755
--- a/src/utils/SkPolyUtils.cpp
+++ b/src/utils/SkPolyUtils.cpp
@@ -263,6 +263,10 @@
SkVector w0 = polygonVerts[currIndex] - origin;
SkVector w1 = polygonVerts[nextIndex] - origin;
for (int i = 0; i < polygonSize; ++i) {
+ if (!polygonVerts[i].isFinite()) {
+ return false;
+ }
+
// Check that winding direction is always the same (otherwise we have a reflex vertex)
SkScalar perpDot = v0.cross(v1);
if (lastPerpDot*perpDot < 0) {
@@ -354,6 +358,9 @@
for (int i = 0; i < inputPolygonSize; ++i) {
int j = (i + 1) % inputPolygonSize;
int k = (i + 2) % inputPolygonSize;
+ if (!inputPolygonVerts[i].isFinite()) {
+ return false;
+ }
// check for convexity just to be sure
if (compute_side(inputPolygonVerts[i], inputPolygonVerts[j],
inputPolygonVerts[k])*winding < 0) {
@@ -464,32 +471,33 @@
///////////////////////////////////////////////////////////////////////////////////////////
// compute the number of points needed for a circular join when offsetting a reflex vertex
-void SkComputeRadialSteps(const SkVector& v1, const SkVector& v2, SkScalar r,
+bool SkComputeRadialSteps(const SkVector& v1, const SkVector& v2, SkScalar r,
SkScalar* rotSin, SkScalar* rotCos, int* n) {
const SkScalar kRecipPixelsPerArcSegment = 0.25f;
SkScalar rCos = v1.dot(v2);
+ if (!SkScalarIsFinite(rCos)) {
+ return false;
+ }
SkScalar rSin = v1.cross(v2);
+ if (!SkScalarIsFinite(rSin)) {
+ return false;
+ }
SkScalar theta = SkScalarATan2(rSin, rCos);
int steps = SkScalarRoundToInt(SkScalarAbs(r*theta*kRecipPixelsPerArcSegment));
- SkScalar dTheta = theta / steps;
+ SkScalar dTheta = steps > 0 ? theta / steps : 0;
*rotSin = SkScalarSinCos(dTheta, rotCos);
*n = steps;
+ return true;
}
///////////////////////////////////////////////////////////////////////////////////////////
-// tolerant less-than comparison
-static inline bool nearly_lt(SkScalar a, SkScalar b, SkScalar tolerance = SK_ScalarNearlyZero) {
- return a < b - tolerance;
-}
-
// a point is "left" to another if its x coordinate is less, or if equal, its y coordinate
static bool left(const SkPoint& p0, const SkPoint& p1) {
- return nearly_lt(p0.fX, p1.fX) ||
- (SkScalarNearlyEqual(p0.fX, p1.fX) && nearly_lt(p0.fY, p1.fY));
+ return p0.fX < p1.fX || (!(p0.fX > p1.fX) && p0.fY < p1.fY);
}
struct Vertex {
@@ -512,7 +520,7 @@
struct Edge {
// returns true if "this" is above "that"
bool above(const Edge& that, SkScalar tolerance = SK_ScalarNearlyZero) {
- SkASSERT(nearly_lt(this->fSegment.fP0.fX, that.fSegment.fP0.fX, tolerance) ||
+ SkASSERT(this->fSegment.fP0.fX < that.fSegment.fP0.fX ||
SkScalarNearlyEqual(this->fSegment.fP0.fX, that.fSegment.fP0.fX, tolerance));
// The idea here is that if the vector between the origins of the two segments (dv)
// rotates counterclockwise up to the vector representing the "this" segment (u),
@@ -624,12 +632,19 @@
// should be added or removed from an edge list. If any intersections are detected in the edge
// list, then we know the polygon is self-intersecting and hence not simple.
bool SkIsSimplePolygon(const SkPoint* polygon, int polygonSize) {
+ if (polygonSize < 3) {
+ return false;
+ }
+
SkTDPQueue <Vertex, Vertex::Left> vertexQueue;
EdgeList sweepLine;
sweepLine.reserve(polygonSize);
for (int i = 0; i < polygonSize; ++i) {
Vertex newVertex;
+ if (!polygon[i].isFinite()) {
+ return false;
+ }
newVertex.fPosition = polygon[i];
newVertex.fIndex = i;
newVertex.fPrevIndex = (i - 1 + polygonSize) % polygonSize;
@@ -700,9 +715,18 @@
SkAutoSTMalloc<64, SkVector> normal0(inputPolygonSize);
SkAutoSTMalloc<64, SkVector> normal1(inputPolygonSize);
SkScalar currOffset = offsetDistanceFunc(inputPolygonVerts[0]);
+ if (!SkScalarIsFinite(currOffset)) {
+ return false;
+ }
for (int curr = 0; curr < inputPolygonSize; ++curr) {
+ if (!inputPolygonVerts[curr].isFinite()) {
+ return false;
+ }
int next = (curr + 1) % inputPolygonSize;
SkScalar nextOffset = offsetDistanceFunc(inputPolygonVerts[next]);
+ if (!SkScalarIsFinite(nextOffset)) {
+ return false;
+ }
if (!compute_offset_vectors(inputPolygonVerts[curr], inputPolygonVerts[next],
currOffset, nextOffset, winding,
&normal0[curr], &normal1[next])) {
@@ -726,8 +750,10 @@
SkScalar rotSin, rotCos;
int numSteps;
SkVector prevNormal = normal1[currIndex];
- SkComputeRadialSteps(prevNormal, normal0[currIndex], SkScalarAbs(offset),
- &rotSin, &rotCos, &numSteps);
+ if (!SkComputeRadialSteps(prevNormal, normal0[currIndex], SkScalarAbs(offset),
+ &rotSin, &rotCos, &numSteps)) {
+ return false;
+ }
for (int i = 0; i < numSteps - 1; ++i) {
SkVector currNormal = SkVector::Make(prevNormal.fX*rotCos - prevNormal.fY*rotSin,
prevNormal.fY*rotCos + prevNormal.fX*rotSin);
@@ -910,11 +936,13 @@
fReflexList.remove(v);
}
- bool checkTriangle(const SkPoint& p0, const SkPoint& p1, const SkPoint& p2) {
+ bool checkTriangle(const SkPoint& p0, const SkPoint& p1, const SkPoint& p2,
+ uint16_t ignoreIndex0, uint16_t ignoreIndex1) {
for (SkTInternalLList<TriangulationVertex>::Iter reflexIter = fReflexList.begin();
reflexIter != fReflexList.end(); ++reflexIter) {
TriangulationVertex* reflexVertex = *reflexIter;
- if (point_in_triangle(p0, p1, p2, reflexVertex->fPosition)) {
+ if (reflexVertex->fIndex != ignoreIndex0 && reflexVertex->fIndex != ignoreIndex1 &&
+ point_in_triangle(p0, p1, p2, reflexVertex->fPosition)) {
return true;
}
}
@@ -934,7 +962,7 @@
if (TriangulationVertex::VertexType::kReflex == p->fVertexType) {
SkVector v0 = p->fPosition - polygonVerts[p->fPrevIndex];
SkVector v1 = polygonVerts[p->fNextIndex] - p->fPosition;
- if (winding*v0.cross(v1) > SK_ScalarNearlyZero) {
+ if (winding*v0.cross(v1) > SK_ScalarNearlyZero*SK_ScalarNearlyZero) {
p->fVertexType = TriangulationVertex::VertexType::kConvex;
reflexHash->remove(p);
p->fPrev = p->fNext = nullptr;
@@ -977,7 +1005,7 @@
triangulationVertices[currIndex].fIndex = currIndex;
triangulationVertices[currIndex].fPrevIndex = prevIndex;
triangulationVertices[currIndex].fNextIndex = nextIndex;
- if (winding*v0.cross(v1) > SK_ScalarNearlyZero) {
+ if (winding*v0.cross(v1) > SK_ScalarNearlyZero*SK_ScalarNearlyZero) {
triangulationVertices[currIndex].fVertexType = TriangulationVertex::VertexType::kConvex;
convexList.addToTail(&triangulationVertices[currIndex]);
} else {
@@ -1018,7 +1046,7 @@
// see if any reflex vertices are inside the ear
bool failed = reflexHash.checkTriangle(p0->fPosition, earVertex->fPosition,
- p2->fPosition);
+ p2->fPosition, p0->fIndex, p2->fIndex);
if (failed) {
continue;
}
diff --git a/src/utils/SkPolyUtils.h b/src/utils/SkPolyUtils.h
index 9c25a07..b753a91 100755
--- a/src/utils/SkPolyUtils.h
+++ b/src/utils/SkPolyUtils.h
@@ -113,8 +113,9 @@
* @param rotSin Sine of rotation delta per step.
* @param rotCos Cosine of rotation delta per step.
* @param n Number of steps to fill out the arc.
+ * @return true for success, false otherwise
*/
-void SkComputeRadialSteps(const SkVector& offset0, const SkVector& offset1, SkScalar r,
+bool SkComputeRadialSteps(const SkVector& offset0, const SkVector& offset1, SkScalar r,
SkScalar* rotSin, SkScalar* rotCos, int* n);
/**
diff --git a/src/utils/SkShadowTessellator.cpp b/src/utils/SkShadowTessellator.cpp
index 873e6d2..b485f3f 100755
--- a/src/utils/SkShadowTessellator.cpp
+++ b/src/utils/SkShadowTessellator.cpp
@@ -500,7 +500,10 @@
// fill in fan from previous quad
SkScalar rotSin, rotCos;
int numSteps;
- SkComputeRadialSteps(fPrevOutset, nextNormal, fRadius, &rotSin, &rotCos, &numSteps);
+ if (!SkComputeRadialSteps(fPrevOutset, nextNormal, fRadius, &rotSin, &rotCos, &numSteps)) {
+ // recover as best we can
+ numSteps = 0;
+ }
SkVector prevNormal = fPrevOutset;
for (int i = 0; i < numSteps-1; ++i) {
SkVector currNormal;
diff --git a/tests/PolyUtilsTest.cpp b/tests/PolyUtilsTest.cpp
index bc5a1a4..0f81f2a 100644
--- a/tests/PolyUtilsTest.cpp
+++ b/tests/PolyUtilsTest.cpp
@@ -11,8 +11,8 @@
SkTDArray<SkPoint> poly;
// init simple index map
- uint16_t indexMap[256];
- for (int i = 0; i < 256; ++i) {
+ uint16_t indexMap[1024];
+ for (int i = 0; i < 1024; ++i) {
indexMap[i] = i;
}
SkTDArray<uint16_t> triangleIndices;
@@ -32,7 +32,7 @@
REPORTER_ASSERT(reporter, SkGetPolygonWinding(poly.begin(), poly.count()) > 0);
REPORTER_ASSERT(reporter, SkIsConvexPolygon(poly.begin(), poly.count()));
REPORTER_ASSERT(reporter, SkIsSimplePolygon(poly.begin(), poly.count()));
- triangleIndices.reset();
+ triangleIndices.rewind();
REPORTER_ASSERT(reporter, SkTriangulateSimplePolygon(poly.begin(), indexMap, poly.count(),
&triangleIndices));
@@ -42,7 +42,7 @@
// TODO: should these fail?
REPORTER_ASSERT(reporter, SkIsConvexPolygon(poly.begin(), poly.count()));
REPORTER_ASSERT(reporter, SkIsSimplePolygon(poly.begin(), poly.count()));
- triangleIndices.reset();
+ triangleIndices.rewind();
REPORTER_ASSERT(reporter, !SkTriangulateSimplePolygon(poly.begin(), indexMap, poly.count(),
&triangleIndices));
@@ -53,7 +53,7 @@
REPORTER_ASSERT(reporter, SkGetPolygonWinding(poly.begin(), poly.count()) < 0);
REPORTER_ASSERT(reporter, SkIsConvexPolygon(poly.begin(), poly.count()));
REPORTER_ASSERT(reporter, SkIsSimplePolygon(poly.begin(), poly.count()));
- triangleIndices.reset();
+ triangleIndices.rewind();
REPORTER_ASSERT(reporter, SkTriangulateSimplePolygon(poly.begin(), indexMap, poly.count(),
&triangleIndices));
@@ -65,7 +65,7 @@
// TODO: should these fail?
REPORTER_ASSERT(reporter, SkIsConvexPolygon(poly.begin(), poly.count()));
REPORTER_ASSERT(reporter, SkIsSimplePolygon(poly.begin(), poly.count()));
- triangleIndices.reset();
+ triangleIndices.rewind();
REPORTER_ASSERT(reporter, !SkTriangulateSimplePolygon(poly.begin(), indexMap, poly.count(),
&triangleIndices));
@@ -76,13 +76,13 @@
REPORTER_ASSERT(reporter, SkGetPolygonWinding(poly.begin(), poly.count()) > 0);
REPORTER_ASSERT(reporter, SkIsConvexPolygon(poly.begin(), poly.count()));
REPORTER_ASSERT(reporter, SkIsSimplePolygon(poly.begin(), poly.count()));
- triangleIndices.reset();
+ triangleIndices.rewind();
REPORTER_ASSERT(reporter, SkTriangulateSimplePolygon(poly.begin(), indexMap, poly.count(),
&triangleIndices));
///////////////////////////////////////////////////////////////////////
// round rect
- poly.reset();
+ poly.rewind();
*poly.push() = SkPoint::Make(-100, 55);
*poly.push() = SkPoint::Make(100, 55);
*poly.push() = SkPoint::Make(100 + 2.5f, 50 + 4.330127f);
@@ -106,7 +106,7 @@
REPORTER_ASSERT(reporter, SkGetPolygonWinding(poly.begin(), poly.count()) < 0);
REPORTER_ASSERT(reporter, SkIsConvexPolygon(poly.begin(), poly.count()));
REPORTER_ASSERT(reporter, SkIsSimplePolygon(poly.begin(), poly.count()));
- triangleIndices.reset();
+ triangleIndices.rewind();
REPORTER_ASSERT(reporter, SkTriangulateSimplePolygon(poly.begin(), indexMap, poly.count(),
&triangleIndices));
@@ -118,7 +118,7 @@
// Due to floating point error it's no longer convex
REPORTER_ASSERT(reporter, !SkIsConvexPolygon(poly.begin(), poly.count()));
REPORTER_ASSERT(reporter, SkIsSimplePolygon(poly.begin(), poly.count()));
- triangleIndices.reset();
+ triangleIndices.rewind();
REPORTER_ASSERT(reporter, SkTriangulateSimplePolygon(poly.begin(), indexMap, poly.count(),
&triangleIndices));
@@ -130,12 +130,12 @@
REPORTER_ASSERT(reporter, SkIsConvexPolygon(poly.begin(), poly.count()));
// These can't handle coincident vertices
REPORTER_ASSERT(reporter, !SkIsSimplePolygon(poly.begin(), poly.count()));
- triangleIndices.reset();
+ triangleIndices.rewind();
REPORTER_ASSERT(reporter, !SkTriangulateSimplePolygon(poly.begin(), indexMap, poly.count(),
&triangleIndices));
// troublesome case -- clipped roundrect
- poly.reset();
+ poly.rewind();
*poly.push() = SkPoint::Make(335.928101f, 428.219055f);
*poly.push() = SkPoint::Make(330.414459f, 423.034912f);
*poly.push() = SkPoint::Make(325.749084f, 417.395508f);
@@ -166,12 +166,12 @@
REPORTER_ASSERT(reporter, SkGetPolygonWinding(poly.begin(), poly.count()) > 0);
REPORTER_ASSERT(reporter, SkIsConvexPolygon(poly.begin(), poly.count()));
REPORTER_ASSERT(reporter, SkIsSimplePolygon(poly.begin(), poly.count()));
- triangleIndices.reset();
+ triangleIndices.rewind();
REPORTER_ASSERT(reporter, SkTriangulateSimplePolygon(poly.begin(), indexMap, poly.count(),
&triangleIndices));
// a star is born
- poly.reset();
+ poly.rewind();
*poly.push() = SkPoint::Make(0.0f, -50.0f);
*poly.push() = SkPoint::Make(14.43f, -25.0f);
*poly.push() = SkPoint::Make(43.30f, -25.0f);
@@ -187,12 +187,37 @@
REPORTER_ASSERT(reporter, SkGetPolygonWinding(poly.begin(), poly.count()) > 0);
REPORTER_ASSERT(reporter, !SkIsConvexPolygon(poly.begin(), poly.count()));
REPORTER_ASSERT(reporter, SkIsSimplePolygon(poly.begin(), poly.count()));
- triangleIndices.reset();
+ triangleIndices.rewind();
REPORTER_ASSERT(reporter, SkTriangulateSimplePolygon(poly.begin(), indexMap, poly.count(),
&triangleIndices));
+ // many spiked star
+ {
+ const SkScalar c = SkIntToScalar(45);
+ const SkScalar r1 = SkIntToScalar(20);
+ const SkScalar r2 = SkIntToScalar(3);
+ const int n = 500;
+ poly.rewind();
+ SkScalar rad = 0;
+ const SkScalar drad = SK_ScalarPI / n;
+ for (int i = 0; i < n; i++) {
+ SkScalar cosV, sinV = SkScalarSinCos(rad, &cosV);
+ *poly.push() = SkPoint::Make(c + cosV * r1, c + sinV * r1);
+ rad += drad;
+ sinV = SkScalarSinCos(rad, &cosV);
+ *poly.push() = SkPoint::Make(c + cosV * r2, c + sinV * r2);
+ rad += drad;
+ }
+ REPORTER_ASSERT(reporter, SkGetPolygonWinding(poly.begin(), poly.count()) > 0);
+ REPORTER_ASSERT(reporter, !SkIsConvexPolygon(poly.begin(), poly.count()));
+ REPORTER_ASSERT(reporter, SkIsSimplePolygon(poly.begin(), poly.count()));
+ triangleIndices.rewind();
+ REPORTER_ASSERT(reporter, SkTriangulateSimplePolygon(poly.begin(), indexMap, poly.count(),
+ &triangleIndices));
+ }
+
// self-intersecting polygon
- poly.reset();
+ poly.rewind();
*poly.push() = SkPoint::Make(0.0f, -50.0f);
*poly.push() = SkPoint::Make(14.43f, -25.0f);
*poly.push() = SkPoint::Make(43.30f, -25.0f);
@@ -208,14 +233,14 @@
REPORTER_ASSERT(reporter, SkGetPolygonWinding(poly.begin(), poly.count()) > 0);
REPORTER_ASSERT(reporter, !SkIsConvexPolygon(poly.begin(), poly.count()));
REPORTER_ASSERT(reporter, !SkIsSimplePolygon(poly.begin(), poly.count()));
- triangleIndices.reset();
+ triangleIndices.rewind();
// running this just to make sure it doesn't crash
// the fact that it succeeds doesn't mean anything since the input is not simple
REPORTER_ASSERT(reporter, SkTriangulateSimplePolygon(poly.begin(), indexMap, poly.count(),
&triangleIndices));
// self-intersecting polygon with coincident point
- poly.reset();
+ poly.rewind();
*poly.push() = SkPoint::Make(0.0f, 0.0f);
*poly.push() = SkPoint::Make(-50, -50);
*poly.push() = SkPoint::Make(50, -50);
@@ -225,7 +250,7 @@
REPORTER_ASSERT(reporter, SkGetPolygonWinding(poly.begin(), poly.count()) == 0);
REPORTER_ASSERT(reporter, !SkIsConvexPolygon(poly.begin(), poly.count()));
REPORTER_ASSERT(reporter, !SkIsSimplePolygon(poly.begin(), poly.count()));
- triangleIndices.reset();
+ triangleIndices.rewind();
// running this just to make sure it doesn't crash
REPORTER_ASSERT(reporter, !SkTriangulateSimplePolygon(poly.begin(), indexMap, poly.count(),
&triangleIndices));