From 061cc21b61e04ecb6120a6e66ea04f89b82200c2 Mon Sep 17 00:00:00 2001 From: Jim Van Verth Date: Wed, 11 Jul 2018 14:09:09 -0400 Subject: 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 Reviewed-by: Kevin Lubick Reviewed-by: Robert Phillips --- BUILD.gn | 1 + bench/PolyUtilsBench.cpp | 130 ++++++++++++++++++++++++++++++++++++++ fuzz/FuzzPolyUtils.cpp | 48 ++++++++++++++ gn/bench.gni | 1 + src/utils/SkPolyUtils.cpp | 62 +++++++++++++----- src/utils/SkPolyUtils.h | 3 +- src/utils/SkShadowTessellator.cpp | 5 +- tests/PolyUtilsTest.cpp | 63 ++++++++++++------ 8 files changed, 275 insertions(+), 38 deletions(-) create mode 100644 bench/PolyUtilsBench.cpp create mode 100644 fuzz/FuzzPolyUtils.cpp diff --git a/BUILD.gn b/BUILD.gn index f10d232fcc..11b1943a47 100644 --- a/BUILD.gn +++ b/BUILD.gn @@ -1749,6 +1749,7 @@ if (skia_enable_tools) { "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 0000000000..1b987fa038 --- /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* 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 poly; + this->makePoly(&poly); + SkAutoSTMalloc<64, uint16_t> indexMap(poly.count()); + for (int i = 0; i < poly.count(); ++i) { + indexMap[i] = i; + } + SkTDArray 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* 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* 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* 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 0000000000..fda5b5f34a --- /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 output; + ignoreResult(SkInsetConvexPolygon(polygon, count, inset, &output)); + std::function 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 outputIndices; + ignoreResult(SkTriangulateSimplePolygon(polygon, indexMap, count, &outputIndices)); +} diff --git a/gn/bench.gni b/gn/bench.gni index ab1870308c..688636db57 100644 --- a/gn/bench.gni +++ b/gn/bench.gni @@ -86,6 +86,7 @@ bench_sources = [ "$_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 e323f21762..b76d270d15 100755 --- a/src/utils/SkPolyUtils.cpp +++ b/src/utils/SkPolyUtils.cpp @@ -263,6 +263,10 @@ bool SkIsConvexPolygon(const SkPoint* polygonVerts, int polygonSize) { 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 @@ bool SkInsetConvexPolygon(const SkPoint* inputPolygonVerts, int inputPolygonSize 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 @@ bool SkInsetConvexPolygon(const SkPoint* inputPolygonVerts, int inputPolygonSize /////////////////////////////////////////////////////////////////////////////////////////// // 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 @@ enum VertexFlags { 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 @@ private: // 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 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 @@ bool SkOffsetSimplePolygon(const SkPoint* inputPolygonVerts, int inputPolygonSiz 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 @@ bool SkOffsetSimplePolygon(const SkPoint* inputPolygonVerts, int inputPolygonSiz 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 @@ public: 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::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 @@ static void reclassify_vertex(TriangulationVertex* p, const SkPoint* polygonVert 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 @@ bool SkTriangulateSimplePolygon(const SkPoint* polygonVerts, uint16_t* indexMap, 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 @@ bool SkTriangulateSimplePolygon(const SkPoint* polygonVerts, uint16_t* indexMap, // 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 9c25a078ff..b753a91141 100755 --- a/src/utils/SkPolyUtils.h +++ b/src/utils/SkPolyUtils.h @@ -113,8 +113,9 @@ bool SkOffsetSegment(const SkPoint& p0, const SkPoint& p1, SkScalar d0, SkScalar * @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 873e6d2687..b485f3f68c 100755 --- a/src/utils/SkShadowTessellator.cpp +++ b/src/utils/SkShadowTessellator.cpp @@ -500,7 +500,10 @@ bool SkBaseShadowTessellator::addArc(const SkVector& nextNormal, bool finishArc) // 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 bc5a1a4858..0f81f2a8e9 100644 --- a/tests/PolyUtilsTest.cpp +++ b/tests/PolyUtilsTest.cpp @@ -11,8 +11,8 @@ DEF_TEST(PolyUtils, reporter) { SkTDArray 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 triangleIndices; @@ -32,7 +32,7 @@ DEF_TEST(PolyUtils, reporter) { 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 @@ DEF_TEST(PolyUtils, reporter) { // 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 @@ DEF_TEST(PolyUtils, reporter) { 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 @@ DEF_TEST(PolyUtils, reporter) { // 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 @@ DEF_TEST(PolyUtils, reporter) { 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 @@ DEF_TEST(PolyUtils, reporter) { 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 @@ DEF_TEST(PolyUtils, reporter) { // 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 @@ DEF_TEST(PolyUtils, reporter) { 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 @@ DEF_TEST(PolyUtils, reporter) { 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 @@ DEF_TEST(PolyUtils, reporter) { 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 @@ DEF_TEST(PolyUtils, reporter) { 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 @@ DEF_TEST(PolyUtils, reporter) { 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)); -- cgit v1.2.3