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 --- src/utils/SkPolyUtils.cpp | 151 +++++++++++++++++++++++++++----------- src/utils/SkPolyUtils.h | 21 ++++++ src/utils/SkShadowTessellator.cpp | 35 +++++---- 3 files changed, 146 insertions(+), 61 deletions(-) (limited to 'src/utils') 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; } -- cgit v1.2.3