From 6784ffa78e70e17084e1b30e724a8ded175d6007 Mon Sep 17 00:00:00 2001 From: Jim Van Verth Date: Tue, 3 Jul 2018 16:12:39 -0400 Subject: Add some new PolyUtils tests. Also: * clean up PolyUtils checks to be correct and consistent. * fix some bugs discovered by the unit tests. Bug: skia: Change-Id: I1a8e07d13cb44fecc67344154dc1002f3f910f5d Reviewed-on: https://skia-review.googlesource.com/138592 Reviewed-by: Robert Phillips Reviewed-by: Greg Daniel Commit-Queue: Jim Van Verth --- gn/tests.gni | 1 + src/utils/SkPolyUtils.cpp | 151 ++++++++++++++++++------- src/utils/SkPolyUtils.h | 21 ++++ src/utils/SkShadowTessellator.cpp | 35 +++--- tests/InsetConvexPolyTest.cpp | 47 ++------ tests/OffsetSimplePolyTest.cpp | 75 +++++------- tests/PolyUtilsTest.cpp | 232 ++++++++++++++++++++++++++++++++++++++ 7 files changed, 421 insertions(+), 141 deletions(-) create mode 100644 tests/PolyUtilsTest.cpp diff --git a/gn/tests.gni b/gn/tests.gni index 2068ae527c..7ffbb0b00f 100644 --- a/gn/tests.gni +++ b/gn/tests.gni @@ -173,6 +173,7 @@ tests_sources = [ "$_tests/PixelRefTest.cpp", "$_tests/Point3Test.cpp", "$_tests/PointTest.cpp", + "$_tests/PolyUtilsTest.cpp", "$_tests/PremulAlphaRoundTripTest.cpp", "$_tests/PrimitiveProcessorTest.cpp", "$_tests/ProcessorTest.cpp", diff --git a/src/utils/SkPolyUtils.cpp b/src/utils/SkPolyUtils.cpp index ea9d649a5c..e323f21762 100755 --- a/src/utils/SkPolyUtils.cpp +++ b/src/utils/SkPolyUtils.cpp @@ -35,13 +35,20 @@ static int compute_side(const SkPoint& s0, const SkPoint& s1, const SkPoint& p) return 0; } -// returns 1 for ccw, -1 for cw and 0 if degenerate -static int get_winding(const SkPoint* polygonVerts, int polygonSize) { +// Returns 1 for cw, -1 for ccw and 0 if zero signed area (either degenerate or self-intersecting) +int SkGetPolygonWinding(const SkPoint* polygonVerts, int polygonSize) { + if (polygonSize < 3) { + return 0; + } + // compute area and use sign to determine winding SkScalar quadArea = 0; - for (int curr = 0; curr < polygonSize; ++curr) { + SkVector v0 = polygonVerts[1] - polygonVerts[0]; + for (int curr = 1; curr < polygonSize - 1; ++curr) { int next = (curr + 1) % polygonSize; - quadArea += polygonVerts[curr].cross(polygonVerts[next]); + SkVector v1 = polygonVerts[next] - polygonVerts[0]; + quadArea += v0.cross(v1); + v0 = v1; } if (SkScalarNearlyZero(quadArea)) { return 0; @@ -111,6 +118,15 @@ bool SkOffsetSegment(const SkPoint& p0, const SkPoint& p1, SkScalar d0, SkScalar return true; } +// compute fraction of d along v +static inline SkScalar compute_param(const SkVector& v, const SkVector& d) { + if (SkScalarNearlyZero(v.fX)) { + return d.fY / v.fY; + } else { + return d.fX / v.fX; + } +} + // Compute the intersection 'p' between segments s0 and s1, if any. // 's' is the parametric value for the intersection along 's0' & 't' is the same for 's1'. // Returns false if there is no intersection. @@ -132,36 +148,60 @@ static bool compute_intersection(const OffsetSegment& s0, const OffsetSegment& s SkVector v0 = s0.fP1 - s0.fP0; SkVector v1 = s1.fP1 - s1.fP0; - // We should have culled coincident points before this - SkASSERT(!SkPointPriv::EqualsWithinTolerance(s0.fP0, s0.fP1)); - SkASSERT(!SkPointPriv::EqualsWithinTolerance(s1.fP0, s1.fP1)); - SkVector d = s1.fP0 - s0.fP0; SkScalar perpDot = v0.cross(v1); SkScalar localS, localT; if (SkScalarNearlyZero(perpDot)) { // segments are parallel, but not collinear - if (!SkScalarNearlyZero(d.dot(d), SK_ScalarNearlyZero*SK_ScalarNearlyZero)) { + if (!SkScalarNearlyZero(d.cross(v0)) || !SkScalarNearlyZero(d.cross(v1))) { return false; } - // project segment1's endpoints onto segment0 - localS = d.fX / v0.fX; - localT = 0; - if (localS < 0 || localS > SK_Scalar1) { - // the first endpoint doesn't lie on segment0, try the other one - SkScalar oldLocalS = localS; - localS = (s1.fP1.fX - s0.fP0.fX) / v0.fX; - localT = SK_Scalar1; + // Check for degenerate segments + if (!SkPointPriv::CanNormalize(v0.fX, v0.fY)) { + // Both are degenerate + if (!SkPointPriv::CanNormalize(v1.fX, v1.fY)) { + // Check if they're the same point + if (!SkPointPriv::CanNormalize(d.fX, d.fY)) { + *p = s0.fP0; + *s = 0; + *t = 0; + return true; + } else { + return false; + } + } + // Otherwise project onto segment1 + localT = compute_param(v1, -d); + if (localT < 0 || localT > SK_Scalar1) { + return false; + } + localS = 0; + } else { + // Project segment1's endpoints onto segment0 + localS = compute_param(v0, d); + localT = 0; if (localS < 0 || localS > SK_Scalar1) { - // it's possible that segment1's interval surrounds segment0 - // this is false if the params have the same signs, and in that case no collision - if (localS*oldLocalS > 0) { + // The first endpoint doesn't lie on segment0 + // If segment1 is degenerate, then there's no collision + if (!SkPointPriv::CanNormalize(v1.fX, v1.fY)) { return false; } - // otherwise project segment0's endpoint onto segment1 instead - localS = 0; - localT = -d.fX / v1.fX; + + // Otherwise try the other one + SkScalar oldLocalS = localS; + localS = compute_param(v0, s1.fP1 - s0.fP0); + localT = SK_Scalar1; + if (localS < 0 || localS > SK_Scalar1) { + // it's possible that segment1's interval surrounds segment0 + // this is false if params have the same signs, and in that case no collision + if (localS*oldLocalS > 0) { + return false; + } + // otherwise project segment0's endpoint onto segment1 instead + localS = 0; + localT = compute_param(v1, -d); + } } } } else { @@ -175,8 +215,7 @@ static bool compute_intersection(const OffsetSegment& s0, const OffsetSegment& s } } - v0 *= localS; - *p = s0.fP0 + v0; + *p = s0.fP0 + v0*localS; *s = localS; *t = localT; @@ -207,25 +246,49 @@ static SkScalar compute_crossing_distance(const OffsetSegment& s0, const OffsetS return localS; } -static bool is_convex(const SkTDArray& poly) { - if (poly.count() <= 3) { - return true; +bool SkIsConvexPolygon(const SkPoint* polygonVerts, int polygonSize) { + if (polygonSize < 3) { + return false; } - SkVector v0 = poly[0] - poly[poly.count() - 1]; - SkVector v1 = poly[1] - poly[poly.count() - 1]; - SkScalar winding = v0.cross(v1); - - for (int i = 0; i < poly.count() - 1; ++i) { - int j = i + 1; - int k = (i + 2) % poly.count(); + SkScalar lastArea = 0; + SkScalar lastPerpDot = 0; - SkVector v0 = poly[j] - poly[i]; - SkVector v1 = poly[k] - poly[i]; + int prevIndex = polygonSize - 1; + int currIndex = 0; + int nextIndex = 1; + SkPoint origin = polygonVerts[0]; + SkVector v0 = polygonVerts[currIndex] - polygonVerts[prevIndex]; + SkVector v1 = polygonVerts[nextIndex] - polygonVerts[currIndex]; + SkVector w0 = polygonVerts[currIndex] - origin; + SkVector w1 = polygonVerts[nextIndex] - origin; + for (int i = 0; i < polygonSize; ++i) { + // Check that winding direction is always the same (otherwise we have a reflex vertex) SkScalar perpDot = v0.cross(v1); - if (winding*perpDot < 0) { + if (lastPerpDot*perpDot < 0) { return false; } + if (0 != perpDot) { + lastPerpDot = perpDot; + } + + // If the signed area ever flips it's concave + // TODO: see if we can verify convexity only with signed area + SkScalar quadArea = w0.cross(w1); + if (quadArea*lastArea < 0) { + return false; + } + if (0 != quadArea) { + lastArea = quadArea; + } + + prevIndex = currIndex; + currIndex = nextIndex; + nextIndex = (currIndex + 1) % polygonSize; + v0 = v1; + v1 = polygonVerts[nextIndex] - polygonVerts[currIndex]; + w0 = w1; + w1 = polygonVerts[nextIndex] - origin; } return true; @@ -281,7 +344,7 @@ bool SkInsetConvexPolygon(const SkPoint* inputPolygonVerts, int inputPolygonSize } // get winding direction - int winding = get_winding(inputPolygonVerts, inputPolygonSize); + int winding = SkGetPolygonWinding(inputPolygonVerts, inputPolygonSize); if (0 == winding) { return false; } @@ -395,7 +458,7 @@ bool SkInsetConvexPolygon(const SkPoint* inputPolygonVerts, int inputPolygonSize insetPolygon->pop(); } - return (insetPolygon->count() >= 3 && is_convex(*insetPolygon)); + return SkIsConvexPolygon(insetPolygon->begin(), insetPolygon->count()); } /////////////////////////////////////////////////////////////////////////////////////////// @@ -416,6 +479,8 @@ void SkComputeRadialSteps(const SkVector& v1, const SkVector& v2, SkScalar r, *n = steps; } +/////////////////////////////////////////////////////////////////////////////////////////// + // tolerant less-than comparison static inline bool nearly_lt(SkScalar a, SkScalar b, SkScalar tolerance = SK_ScalarNearlyZero) { return a < b - tolerance; @@ -626,7 +691,7 @@ bool SkOffsetSimplePolygon(const SkPoint* inputPolygonVerts, int inputPolygonSiz } // get winding direction - int winding = get_winding(inputPolygonVerts, inputPolygonSize); + int winding = SkGetPolygonWinding(inputPolygonVerts, inputPolygonSize); if (0 == winding) { return false; } @@ -787,7 +852,7 @@ bool SkOffsetSimplePolygon(const SkPoint* inputPolygonVerts, int inputPolygonSiz } // check winding of offset polygon (it should be same as the original polygon) - SkScalar offsetWinding = get_winding(offsetPolygon->begin(), offsetPolygon->count()); + SkScalar offsetWinding = SkGetPolygonWinding(offsetPolygon->begin(), offsetPolygon->count()); return (winding*offsetWinding > 0 && SkIsSimplePolygon(offsetPolygon->begin(), offsetPolygon->count())); @@ -891,7 +956,7 @@ bool SkTriangulateSimplePolygon(const SkPoint* polygonVerts, uint16_t* indexMap, // get winding direction // TODO: we do this for all the polygon routines -- might be better to have the client // compute it and pass it in - int winding = get_winding(polygonVerts, polygonSize); + int winding = SkGetPolygonWinding(polygonVerts, polygonSize); if (0 == winding) { return false; } diff --git a/src/utils/SkPolyUtils.h b/src/utils/SkPolyUtils.h index ab5ebb8d40..9c25a078ff 100755 --- a/src/utils/SkPolyUtils.h +++ b/src/utils/SkPolyUtils.h @@ -117,8 +117,29 @@ bool SkOffsetSegment(const SkPoint& p0, const SkPoint& p1, SkScalar d0, SkScalar void SkComputeRadialSteps(const SkVector& offset0, const SkVector& offset1, SkScalar r, SkScalar* rotSin, SkScalar* rotCos, int* n); +/** + * Determine winding direction for a polygon. + * The input polygon must be simple or the result will be meaningless. + * + * @param polygonVerts Array of points representing the vertices of the polygon. + * @param polygonSize Number of vertices in the polygon. + * @return 1 for cw, -1 for ccw, and 0 if zero signed area (either degenerate or self-intersecting). + * The y-axis is assumed to be pointing down. + */ +int SkGetPolygonWinding(const SkPoint* polygonVerts, int polygonSize); + +/** + * Determine whether a polygon is convex or not. + * + * @param polygonVerts Array of points representing the vertices of the polygon. + * @param polygonSize Number of vertices in the polygon. + * @return true if the polygon is convex, false otherwise. + */ +bool SkIsConvexPolygon(const SkPoint* polygonVerts, int polygonSize); + /** * Determine whether a polygon is simple (i.e., not self-intersecting) or not. + * The input polygon must have no coincident vertices or the test will fail. * * @param polygonVerts Array of points representing the vertices of the polygon. * @param polygonSize Number of vertices in the polygon. diff --git a/src/utils/SkShadowTessellator.cpp b/src/utils/SkShadowTessellator.cpp index 3d84e8fdad..873e6d2687 100755 --- a/src/utils/SkShadowTessellator.cpp +++ b/src/utils/SkShadowTessellator.cpp @@ -92,7 +92,6 @@ protected: SkPoint fCentroid; SkScalar fArea; SkScalar fLastArea; - int fAreaSignFlips; SkScalar fLastCross; int fFirstVertexIndex; @@ -137,18 +136,16 @@ static bool duplicate_pt(const SkPoint& p0, const SkPoint& p1) { static SkScalar perp_dot(const SkPoint& p0, const SkPoint& p1, const SkPoint& p2) { SkVector v0 = p1 - p0; - SkVector v1 = p2 - p0; + SkVector v1 = p2 - p1; return v0.cross(v1); } - SkBaseShadowTessellator::SkBaseShadowTessellator(const SkPoint3& zPlaneParams, bool transparent) : fZPlaneParams(zPlaneParams) , fZOffset(0) , fCentroid({0, 0}) , fArea(0) , fLastArea(0) - , fAreaSignFlips(0) , fLastCross(0) , fFirstVertexIndex(-1) , fSucceeded(false) @@ -189,15 +186,20 @@ bool SkBaseShadowTessellator::accumulateCentroid(const SkPoint& curr, const SkPo return false; } - SkScalar quadArea = curr.cross(next); - fCentroid.fX += (curr.fX + next.fX) * quadArea; - fCentroid.fY += (curr.fY + next.fY) * quadArea; + SkASSERT(fPathPolygon.count() > 0); + SkVector v0 = curr - fPathPolygon[0]; + SkVector v1 = next - fPathPolygon[0]; + SkScalar quadArea = v0.cross(v1); + fCentroid.fX += (v0.fX + v1.fX) * quadArea; + fCentroid.fY += (v0.fY + v1.fY) * quadArea; fArea += quadArea; // convexity check if (quadArea*fLastArea < 0) { - ++fAreaSignFlips; + fIsConvex = false; + } + if (0 != quadArea) { + fLastArea = quadArea; } - fLastArea = quadArea; return true; } @@ -215,7 +217,9 @@ bool SkBaseShadowTessellator::checkConvexity(const SkPoint& p0, if (fLastCross*cross < 0) { fIsConvex = false; } - fLastCross = cross; + if (0 != cross) { + fLastCross = cross; + } return true; } @@ -229,6 +233,9 @@ void SkBaseShadowTessellator::finishPathPolygon() { } if (fPathPolygon.count() > 2) { + // do this before the final convexity check, so we use the correct fPathPolygon[0] + fCentroid *= sk_ieee_float_divide(1, 3 * fArea); + fCentroid += fPathPolygon[0]; if (!checkConvexity(fPathPolygon[fPathPolygon.count() - 2], fPathPolygon[fPathPolygon.count() - 1], fPathPolygon[0])) { @@ -238,14 +245,6 @@ void SkBaseShadowTessellator::finishPathPolygon() { } } - fCentroid *= sk_ieee_float_divide(1, 3 * fArea); - // It's possible to have a concave path that self-intersects but also passes the - // cross-product check (e.g., a star). In that case, the signed area will change signs more - // than twice, so we check for that here. - if (fAreaSignFlips > 2) { - fIsConvex = false; - } - // if area is positive, winding is ccw fDirection = fArea > 0 ? -1 : 1; } diff --git a/tests/InsetConvexPolyTest.cpp b/tests/InsetConvexPolyTest.cpp index 022060c0f4..facabb76fa 100644 --- a/tests/InsetConvexPolyTest.cpp +++ b/tests/InsetConvexPolyTest.cpp @@ -7,30 +7,6 @@ #include "Test.h" #include "SkPolyUtils.h" -static bool is_convex(const SkTDArray& poly) { - if (poly.count() < 3) { - return false; - } - - SkVector v0 = poly[0] - poly[poly.count() - 1]; - SkVector v1 = poly[1] - poly[poly.count() - 1]; - SkScalar winding = v0.cross(v1); - - for (int i = 0; i < poly.count()-1; ++i) { - int j = i + 1; - int k = (i + 2) % poly.count(); - - SkVector v0 = poly[j] - poly[i]; - SkVector v1 = poly[k] - poly[i]; - SkScalar perpDot = v0.cross(v1); - if (winding*perpDot < 0) { - return false; - } - } - - return true; -} - DEF_TEST(InsetConvexPoly, reporter) { SkTDArray rrectPoly; @@ -55,18 +31,18 @@ DEF_TEST(InsetConvexPoly, reporter) { *rrectPoly.push() = SkPoint::Make(-100 - 4.330127f, 50 + 2.5f); *rrectPoly.push() = SkPoint::Make(-100 - 3.535534f, 50 + 3.535534f); *rrectPoly.push() = SkPoint::Make(-100 - 2.5f, 50 + 4.330127f); - REPORTER_ASSERT(reporter, is_convex(rrectPoly)); + REPORTER_ASSERT(reporter, SkIsConvexPolygon(rrectPoly.begin(), rrectPoly.count())); // inset a little SkTDArray insetPoly; - bool result = SkInsetConvexPolygon(&rrectPoly[0], rrectPoly.count(), 3, &insetPoly); + bool result = SkInsetConvexPolygon(rrectPoly.begin(), rrectPoly.count(), 3, &insetPoly); REPORTER_ASSERT(reporter, result); - REPORTER_ASSERT(reporter, is_convex(insetPoly)); + REPORTER_ASSERT(reporter, SkIsConvexPolygon(insetPoly.begin(), insetPoly.count())); // inset to rect - result = SkInsetConvexPolygon(&rrectPoly[0], rrectPoly.count(), 10, &insetPoly); + result = SkInsetConvexPolygon(rrectPoly.begin(), rrectPoly.count(), 10, &insetPoly); REPORTER_ASSERT(reporter, result); - REPORTER_ASSERT(reporter, is_convex(insetPoly)); + REPORTER_ASSERT(reporter, SkIsConvexPolygon(insetPoly.begin(), insetPoly.count())); REPORTER_ASSERT(reporter, insetPoly.count() == 4); if (insetPoly.count() == 4) { REPORTER_ASSERT(reporter, insetPoly[0].equals(-95, 45)); @@ -77,9 +53,9 @@ DEF_TEST(InsetConvexPoly, reporter) { // just to full inset // fails, but outputs a line segment - result = SkInsetConvexPolygon(&rrectPoly[0], rrectPoly.count(), 55, &insetPoly); + result = SkInsetConvexPolygon(rrectPoly.begin(), rrectPoly.count(), 55, &insetPoly); REPORTER_ASSERT(reporter, !result); - REPORTER_ASSERT(reporter, !is_convex(insetPoly)); + REPORTER_ASSERT(reporter, !SkIsConvexPolygon(insetPoly.begin(), insetPoly.count())); REPORTER_ASSERT(reporter, insetPoly.count() == 2); if (insetPoly.count() == 2) { REPORTER_ASSERT(reporter, insetPoly[0].equals(-50, 0)); @@ -87,7 +63,7 @@ DEF_TEST(InsetConvexPoly, reporter) { } // past full inset - result = SkInsetConvexPolygon(&rrectPoly[0], rrectPoly.count(), 75, &insetPoly); + result = SkInsetConvexPolygon(rrectPoly.begin(), rrectPoly.count(), 75, &insetPoly); REPORTER_ASSERT(reporter, !result); REPORTER_ASSERT(reporter, insetPoly.count() == 0); @@ -120,10 +96,11 @@ DEF_TEST(InsetConvexPoly, reporter) { *clippedRRectPoly.push() = SkPoint::Make(381.195313f, 432.207275f); *clippedRRectPoly.push() = SkPoint::Make(377.312134f, 432.947998f); *clippedRRectPoly.push() = SkPoint::Make(342.289948f, 432.947998f); - REPORTER_ASSERT(reporter, is_convex(clippedRRectPoly)); + REPORTER_ASSERT(reporter, SkIsConvexPolygon(clippedRRectPoly.begin(), + clippedRRectPoly.count())); - result = SkInsetConvexPolygon(&clippedRRectPoly[0], clippedRRectPoly.count(), 32.3699417f, + result = SkInsetConvexPolygon(clippedRRectPoly.begin(), clippedRRectPoly.count(), 32.3699417f, &insetPoly); REPORTER_ASSERT(reporter, result); - REPORTER_ASSERT(reporter, is_convex(insetPoly)); + REPORTER_ASSERT(reporter, SkIsConvexPolygon(insetPoly.begin(), insetPoly.count())); } diff --git a/tests/OffsetSimplePolyTest.cpp b/tests/OffsetSimplePolyTest.cpp index 547dc9e529..0f4f18f2ad 100644 --- a/tests/OffsetSimplePolyTest.cpp +++ b/tests/OffsetSimplePolyTest.cpp @@ -7,30 +7,6 @@ #include "Test.h" #include "SkPolyUtils.h" -static bool is_convex(const SkTDArray& poly) { - if (poly.count() < 3) { - return false; - } - - SkVector v0 = poly[0] - poly[poly.count() - 1]; - SkVector v1 = poly[1] - poly[poly.count() - 1]; - SkScalar winding = v0.cross(v1); - - for (int i = 0; i < poly.count()-1; ++i) { - int j = i + 1; - int k = (i + 2) % poly.count(); - - SkVector v0 = poly[j] - poly[i]; - SkVector v1 = poly[k] - poly[i]; - SkScalar perpDot = v0.cross(v1); - if (winding*perpDot < 0) { - return false; - } - } - - return true; -} - DEF_TEST(OffsetSimplePoly, reporter) { SkTDArray rrectPoly; @@ -58,18 +34,18 @@ DEF_TEST(OffsetSimplePoly, reporter) { *rrectPoly.push() = SkPoint::Make(-100 - 4.330127f, 50 + 2.5f); *rrectPoly.push() = SkPoint::Make(-100 - 3.535534f, 50 + 3.535534f); *rrectPoly.push() = SkPoint::Make(-100 - 2.5f, 50 + 4.330127f); - REPORTER_ASSERT(reporter, is_convex(rrectPoly)); + REPORTER_ASSERT(reporter, SkIsConvexPolygon(rrectPoly.begin(), rrectPoly.count())); // inset a little SkTDArray offsetPoly; - bool result = SkOffsetSimplePolygon(&rrectPoly[0], rrectPoly.count(), 3, &offsetPoly); + bool result = SkOffsetSimplePolygon(rrectPoly.begin(), rrectPoly.count(), 3, &offsetPoly); REPORTER_ASSERT(reporter, result); - REPORTER_ASSERT(reporter, is_convex(offsetPoly)); + REPORTER_ASSERT(reporter, SkIsConvexPolygon(offsetPoly.begin(), offsetPoly.count())); // inset to rect - result = SkOffsetSimplePolygon(&rrectPoly[0], rrectPoly.count(), 10, &offsetPoly); + result = SkOffsetSimplePolygon(rrectPoly.begin(), rrectPoly.count(), 10, &offsetPoly); REPORTER_ASSERT(reporter, result); - REPORTER_ASSERT(reporter, is_convex(offsetPoly)); + REPORTER_ASSERT(reporter, SkIsConvexPolygon(offsetPoly.begin(), offsetPoly.count())); REPORTER_ASSERT(reporter, offsetPoly.count() == 4); if (offsetPoly.count() == 4) { REPORTER_ASSERT(reporter, offsetPoly[0].equals(-95, 45)); @@ -80,9 +56,9 @@ DEF_TEST(OffsetSimplePoly, reporter) { // just to full inset // fails, but outputs a line segment - result = SkOffsetSimplePolygon(&rrectPoly[0], rrectPoly.count(), 55, &offsetPoly); + result = SkOffsetSimplePolygon(rrectPoly.begin(), rrectPoly.count(), 55, &offsetPoly); REPORTER_ASSERT(reporter, !result); - REPORTER_ASSERT(reporter, !is_convex(offsetPoly)); + REPORTER_ASSERT(reporter, !SkIsConvexPolygon(offsetPoly.begin(), offsetPoly.count())); REPORTER_ASSERT(reporter, offsetPoly.count() == 2); if (offsetPoly.count() == 2) { REPORTER_ASSERT(reporter, offsetPoly[0].equals(-50, 0)); @@ -90,7 +66,7 @@ DEF_TEST(OffsetSimplePoly, reporter) { } // past full inset - result = SkOffsetSimplePolygon(&rrectPoly[0], rrectPoly.count(), 75, &offsetPoly); + result = SkOffsetSimplePolygon(rrectPoly.begin(), rrectPoly.count(), 75, &offsetPoly); REPORTER_ASSERT(reporter, !result); // troublesome case @@ -122,12 +98,13 @@ DEF_TEST(OffsetSimplePoly, reporter) { *clippedRRectPoly.push() = SkPoint::Make(381.195313f, 432.207275f); *clippedRRectPoly.push() = SkPoint::Make(377.312134f, 432.947998f); *clippedRRectPoly.push() = SkPoint::Make(342.289948f, 432.947998f); - REPORTER_ASSERT(reporter, is_convex(clippedRRectPoly)); + REPORTER_ASSERT(reporter, SkIsConvexPolygon(clippedRRectPoly.begin(), + clippedRRectPoly.count())); - result = SkOffsetSimplePolygon(&clippedRRectPoly[0], clippedRRectPoly.count(), 32.3699417f, + result = SkOffsetSimplePolygon(clippedRRectPoly.begin(), clippedRRectPoly.count(), 32.3699417f, &offsetPoly); REPORTER_ASSERT(reporter, result); - REPORTER_ASSERT(reporter, is_convex(offsetPoly)); + REPORTER_ASSERT(reporter, SkIsConvexPolygon(offsetPoly.begin(), offsetPoly.count())); //////////////////////////////////////////////////////////////////////////////// // Concave tests @@ -145,46 +122,54 @@ DEF_TEST(OffsetSimplePoly, reporter) { *starPoly.push() = SkPoint::Make(-28.86f, 0.0f); *starPoly.push() = SkPoint::Make(-43.30f, -25.0f); *starPoly.push() = SkPoint::Make(-14.43f, -25.0f); + REPORTER_ASSERT(reporter, SkIsSimplePolygon(starPoly.begin(), starPoly.count())); // try a variety of distances - result = SkOffsetSimplePolygon(&starPoly[0], starPoly.count(), 0.1f, + result = SkOffsetSimplePolygon(starPoly.begin(), starPoly.count(), 0.1f, &offsetPoly); REPORTER_ASSERT(reporter, result); + REPORTER_ASSERT(reporter, SkIsSimplePolygon(offsetPoly.begin(), offsetPoly.count())); - result = SkOffsetSimplePolygon(&starPoly[0], starPoly.count(), 5.665f, + result = SkOffsetSimplePolygon(starPoly.begin(), starPoly.count(), 5.665f, &offsetPoly); REPORTER_ASSERT(reporter, result); + REPORTER_ASSERT(reporter, SkIsSimplePolygon(offsetPoly.begin(), offsetPoly.count())); - result = SkOffsetSimplePolygon(&starPoly[0], starPoly.count(), 28, + result = SkOffsetSimplePolygon(starPoly.begin(), starPoly.count(), 28, &offsetPoly); REPORTER_ASSERT(reporter, result); + REPORTER_ASSERT(reporter, SkIsSimplePolygon(offsetPoly.begin(), offsetPoly.count())); // down to a point - result = SkOffsetSimplePolygon(&starPoly[0], starPoly.count(), 28.866f, + result = SkOffsetSimplePolygon(starPoly.begin(), starPoly.count(), 28.866f, &offsetPoly); REPORTER_ASSERT(reporter, !result); // and past - result = SkOffsetSimplePolygon(&starPoly[0], starPoly.count(), 50.5f, + result = SkOffsetSimplePolygon(starPoly.begin(), starPoly.count(), 50.5f, &offsetPoly); REPORTER_ASSERT(reporter, !result); // and now out - result = SkOffsetSimplePolygon(&starPoly[0], starPoly.count(), -0.1f, + result = SkOffsetSimplePolygon(starPoly.begin(), starPoly.count(), -0.1f, &offsetPoly); REPORTER_ASSERT(reporter, result); + REPORTER_ASSERT(reporter, SkIsSimplePolygon(offsetPoly.begin(), offsetPoly.count())); - result = SkOffsetSimplePolygon(&starPoly[0], starPoly.count(), -5.6665f, + result = SkOffsetSimplePolygon(starPoly.begin(), starPoly.count(), -5.6665f, &offsetPoly); REPORTER_ASSERT(reporter, result); + REPORTER_ASSERT(reporter, SkIsSimplePolygon(offsetPoly.begin(), offsetPoly.count())); - result = SkOffsetSimplePolygon(&starPoly[0], starPoly.count(), -50, + result = SkOffsetSimplePolygon(starPoly.begin(), starPoly.count(), -50, &offsetPoly); REPORTER_ASSERT(reporter, result); + REPORTER_ASSERT(reporter, SkIsSimplePolygon(offsetPoly.begin(), offsetPoly.count())); - result = SkOffsetSimplePolygon(&starPoly[0], starPoly.count(), -100, + result = SkOffsetSimplePolygon(starPoly.begin(), starPoly.count(), -100, &offsetPoly); REPORTER_ASSERT(reporter, result); + REPORTER_ASSERT(reporter, SkIsSimplePolygon(offsetPoly.begin(), offsetPoly.count())); SkTDArray intersectingPoly; *intersectingPoly.push() = SkPoint::Make(0.0f, -50.0f); @@ -201,6 +186,6 @@ DEF_TEST(OffsetSimplePoly, reporter) { *intersectingPoly.push() = SkPoint::Make(-14.43f, -25.0f); // SkOffsetSimplePolygon now assumes that the input is simple, so we'll just check for that - result = SkIsSimplePolygon(&intersectingPoly[0], intersectingPoly.count()); + result = SkIsSimplePolygon(intersectingPoly.begin(), intersectingPoly.count()); REPORTER_ASSERT(reporter, !result); } diff --git a/tests/PolyUtilsTest.cpp b/tests/PolyUtilsTest.cpp new file mode 100644 index 0000000000..bc5a1a4858 --- /dev/null +++ b/tests/PolyUtilsTest.cpp @@ -0,0 +1,232 @@ +/* + * 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 "Test.h" +#include "SkPolyUtils.h" + +DEF_TEST(PolyUtils, reporter) { + + SkTDArray poly; + // init simple index map + uint16_t indexMap[256]; + for (int i = 0; i < 256; ++i) { + indexMap[i] = i; + } + SkTDArray triangleIndices; + + // skinny triangle + *poly.push() = SkPoint::Make(-100, 55); + *poly.push() = SkPoint::Make(100, 55); + *poly.push() = SkPoint::Make(102.5f, 54.330127f); + 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())); + REPORTER_ASSERT(reporter, SkTriangulateSimplePolygon(poly.begin(), indexMap, poly.count(), + &triangleIndices)); + + // switch winding + poly[2].set(102.5f, 55.330127f); + 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(); + REPORTER_ASSERT(reporter, SkTriangulateSimplePolygon(poly.begin(), indexMap, poly.count(), + &triangleIndices)); + + // make degenerate + poly[2].set(100 + 2.5f, 55); + REPORTER_ASSERT(reporter, SkGetPolygonWinding(poly.begin(), poly.count()) == 0); + // TODO: should these fail? + REPORTER_ASSERT(reporter, SkIsConvexPolygon(poly.begin(), poly.count())); + REPORTER_ASSERT(reporter, SkIsSimplePolygon(poly.begin(), poly.count())); + triangleIndices.reset(); + REPORTER_ASSERT(reporter, !SkTriangulateSimplePolygon(poly.begin(), indexMap, poly.count(), + &triangleIndices)); + + // giant triangle + poly[0].set(-1.0e+37f, 1.0e+37f); + poly[1].set(1.0e+37f, 1.0e+37f); + poly[2].set(-1.0e+37f, -1.0e+37f); + 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(); + REPORTER_ASSERT(reporter, SkTriangulateSimplePolygon(poly.begin(), indexMap, poly.count(), + &triangleIndices)); + + // teeny triangle + poly[0].set(-1.0e-38f, 1.0e-38f); + poly[1].set(-1.0e-38f, -1.0e-38f); + poly[2].set(1.0e-38f, 1.0e-38f); + REPORTER_ASSERT(reporter, SkGetPolygonWinding(poly.begin(), poly.count()) == 0); + // TODO: should these fail? + REPORTER_ASSERT(reporter, SkIsConvexPolygon(poly.begin(), poly.count())); + REPORTER_ASSERT(reporter, SkIsSimplePolygon(poly.begin(), poly.count())); + triangleIndices.reset(); + REPORTER_ASSERT(reporter, !SkTriangulateSimplePolygon(poly.begin(), indexMap, poly.count(), + &triangleIndices)); + + // triangle way off in space (relative to size so we don't completely obliterate values) + poly[0].set(-100 + 1.0e+9f, 55 - 1.0e+9f); + poly[1].set(100 + 1.0e+9f, 55 - 1.0e+9f); + poly[2].set(150 + 1.0e+9f, 100 - 1.0e+9f); + 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(); + REPORTER_ASSERT(reporter, SkTriangulateSimplePolygon(poly.begin(), indexMap, poly.count(), + &triangleIndices)); + + /////////////////////////////////////////////////////////////////////// + // round rect + poly.reset(); + *poly.push() = SkPoint::Make(-100, 55); + *poly.push() = SkPoint::Make(100, 55); + *poly.push() = SkPoint::Make(100 + 2.5f, 50 + 4.330127f); + *poly.push() = SkPoint::Make(100 + 3.535534f, 50 + 3.535534f); + *poly.push() = SkPoint::Make(100 + 4.330127f, 50 + 2.5f); + *poly.push() = SkPoint::Make(105, 50); + *poly.push() = SkPoint::Make(105, -50); + *poly.push() = SkPoint::Make(100 + 4.330127f, -50 - 2.5f); + *poly.push() = SkPoint::Make(100 + 3.535534f, -50 - 3.535534f); + *poly.push() = SkPoint::Make(100 + 2.5f, -50 - 4.330127f); + *poly.push() = SkPoint::Make(100, -55); + *poly.push() = SkPoint::Make(-100, -55); + *poly.push() = SkPoint::Make(-100 - 2.5f, -50 - 4.330127f); + *poly.push() = SkPoint::Make(-100 - 3.535534f, -50 - 3.535534f); + *poly.push() = SkPoint::Make(-100 - 4.330127f, -50 - 2.5f); + *poly.push() = SkPoint::Make(-105, -50); + *poly.push() = SkPoint::Make(-105, 50); + *poly.push() = SkPoint::Make(-100 - 4.330127f, 50 + 2.5f); + *poly.push() = SkPoint::Make(-100 - 3.535534f, 50 + 3.535534f); + *poly.push() = SkPoint::Make(-100 - 2.5f, 50 + 4.330127f); + 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(); + REPORTER_ASSERT(reporter, SkTriangulateSimplePolygon(poly.begin(), indexMap, poly.count(), + &triangleIndices)); + + // translate far enough to obliterate some low bits + for (int i = 0; i < poly.count(); ++i) { + poly[i].offset(1.0e+7f, 1.0e+7f); + } + REPORTER_ASSERT(reporter, SkGetPolygonWinding(poly.begin(), poly.count()) < 0); + // 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(); + REPORTER_ASSERT(reporter, SkTriangulateSimplePolygon(poly.begin(), indexMap, poly.count(), + &triangleIndices)); + + // translate a little farther to create some coincident vertices + for (int i = 0; i < poly.count(); ++i) { + poly[i].offset(4.0e+7f, 4.0e+7f); + } + REPORTER_ASSERT(reporter, SkGetPolygonWinding(poly.begin(), poly.count()) < 0); + REPORTER_ASSERT(reporter, SkIsConvexPolygon(poly.begin(), poly.count())); + // These can't handle coincident vertices + REPORTER_ASSERT(reporter, !SkIsSimplePolygon(poly.begin(), poly.count())); + triangleIndices.reset(); + REPORTER_ASSERT(reporter, !SkTriangulateSimplePolygon(poly.begin(), indexMap, poly.count(), + &triangleIndices)); + + // troublesome case -- clipped roundrect + poly.reset(); + *poly.push() = SkPoint::Make(335.928101f, 428.219055f); + *poly.push() = SkPoint::Make(330.414459f, 423.034912f); + *poly.push() = SkPoint::Make(325.749084f, 417.395508f); + *poly.push() = SkPoint::Make(321.931946f, 411.300842f); + *poly.push() = SkPoint::Make(318.963074f, 404.750977f); + *poly.push() = SkPoint::Make(316.842468f, 397.745850f); + *poly.push() = SkPoint::Make(315.570068f, 390.285522f); + *poly.push() = SkPoint::Make(315.145966f, 382.369965f); + *poly.push() = SkPoint::Make(315.570068f, 374.454346f); + *poly.push() = SkPoint::Make(316.842468f, 366.994019f); + *poly.push() = SkPoint::Make(318.963074f, 359.988892f); + *poly.push() = SkPoint::Make(321.931946f, 353.439056f); + *poly.push() = SkPoint::Make(325.749084f, 347.344421f); + *poly.push() = SkPoint::Make(330.414459f, 341.705017f); + *poly.push() = SkPoint::Make(335.928101f, 336.520813f); + *poly.push() = SkPoint::Make(342.289948f, 331.791901f); + *poly.push() = SkPoint::Make(377.312134f, 331.791901f); + *poly.push() = SkPoint::Make(381.195313f, 332.532593f); + *poly.push() = SkPoint::Make(384.464935f, 334.754700f); + *poly.push() = SkPoint::Make(386.687042f, 338.024292f); + *poly.push() = SkPoint::Make(387.427765f, 341.907532f); + *poly.push() = SkPoint::Make(387.427765f, 422.832367f); + *poly.push() = SkPoint::Make(386.687042f, 426.715576f); + *poly.push() = SkPoint::Make(384.464935f, 429.985168f); + *poly.push() = SkPoint::Make(381.195313f, 432.207275f); + *poly.push() = SkPoint::Make(377.312134f, 432.947998f); + *poly.push() = SkPoint::Make(342.289948f, 432.947998f); + 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(); + REPORTER_ASSERT(reporter, SkTriangulateSimplePolygon(poly.begin(), indexMap, poly.count(), + &triangleIndices)); + + // a star is born + poly.reset(); + *poly.push() = SkPoint::Make(0.0f, -50.0f); + *poly.push() = SkPoint::Make(14.43f, -25.0f); + *poly.push() = SkPoint::Make(43.30f, -25.0f); + *poly.push() = SkPoint::Make(28.86f, 0.0f); + *poly.push() = SkPoint::Make(43.30f, 25.0f); + *poly.push() = SkPoint::Make(14.43f, 25.0f); + *poly.push() = SkPoint::Make(0.0f, 50.0f); + *poly.push() = SkPoint::Make(-14.43f, 25.0f); + *poly.push() = SkPoint::Make(-43.30f, 25.0f); + *poly.push() = SkPoint::Make(-28.86f, 0.0f); + *poly.push() = SkPoint::Make(-43.30f, -25.0f); + *poly.push() = SkPoint::Make(-14.43f, -25.0f); + 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(); + REPORTER_ASSERT(reporter, SkTriangulateSimplePolygon(poly.begin(), indexMap, poly.count(), + &triangleIndices)); + + // self-intersecting polygon + poly.reset(); + *poly.push() = SkPoint::Make(0.0f, -50.0f); + *poly.push() = SkPoint::Make(14.43f, -25.0f); + *poly.push() = SkPoint::Make(43.30f, -25.0f); + *poly.push() = SkPoint::Make(-28.86f, 0.0f); + *poly.push() = SkPoint::Make(43.30f, 25.0f); + *poly.push() = SkPoint::Make(14.43f, 25.0f); + *poly.push() = SkPoint::Make(0.0f, 50.0f); + *poly.push() = SkPoint::Make(-14.43f, 25.0f); + *poly.push() = SkPoint::Make(-43.30f, 25.0f); + *poly.push() = SkPoint::Make(28.86f, 0.0f); + *poly.push() = SkPoint::Make(-43.30f, -25.0f); + *poly.push() = SkPoint::Make(-14.43f, -25.0f); + 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(); + // 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.push() = SkPoint::Make(0.0f, 0.0f); + *poly.push() = SkPoint::Make(-50, -50); + *poly.push() = SkPoint::Make(50, -50); + *poly.push() = SkPoint::Make(0.00000001f, -0.00000001f); + *poly.push() = SkPoint::Make(-50, 50); + *poly.push() = SkPoint::Make(50, 50); + 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(); + // running this just to make sure it doesn't crash + REPORTER_ASSERT(reporter, !SkTriangulateSimplePolygon(poly.begin(), indexMap, poly.count(), + &triangleIndices)); +} -- cgit v1.2.3