diff options
-rw-r--r-- | gm/polygonoffset.cpp | 44 | ||||
-rwxr-xr-x | src/utils/SkOffsetPolygon.cpp | 109 | ||||
-rwxr-xr-x | src/utils/SkOffsetPolygon.h | 50 |
3 files changed, 144 insertions, 59 deletions
diff --git a/gm/polygonoffset.cpp b/gm/polygonoffset.cpp index cbf0849675..48b6d1a4e4 100644 --- a/gm/polygonoffset.cpp +++ b/gm/polygonoffset.cpp @@ -406,18 +406,30 @@ static_assert(SK_ARRAY_COUNT(gSimpleSizes) == SK_ARRAY_COUNT(gSimplePoints), "ar namespace skiagm { // This GM is intended to exercise the offsetting of polygons +// When fVariableOffset is true it will skew the offset by x, +// to test perspective and other variable offset functions class PolygonOffsetGM : public GM { public: - PolygonOffsetGM(bool convexOnly) : fConvexOnly(convexOnly) { + PolygonOffsetGM(bool convexOnly, bool variableOffset) + : fConvexOnly(convexOnly) + , fVariableOffset(variableOffset) { this->setBGColor(0xFFFFFFFF); } protected: SkString onShortName() override { if (fConvexOnly) { - return SkString("convex-polygon-inset"); + if (fVariableOffset) { + return SkString("convex-polygon-inset-v"); + } else { + return SkString("convex-polygon-inset"); + } } else { - return SkString("simple-polygon-offset"); + if (fVariableOffset) { + return SkString("simple-polygon-offset-v"); + } else { + return SkString("simple-polygon-offset"); + } } } SkISize onISize() override { return SkISize::Make(kGMWidth, kGMHeight); } @@ -495,6 +507,7 @@ protected: void drawPolygon(SkCanvas* canvas, int index, SkPoint* offset) { SkPoint center; + SkRect bounds; { std::unique_ptr<SkPoint[]> data(nullptr); int numPts; @@ -503,7 +516,6 @@ protected: } else { GetSimplePolygon(index, SkPath::kCW_Direction, &data, &numPts); } - SkRect bounds; bounds.set(data.get(), numPts); if (!fConvexOnly) { bounds.outset(kMaxOutset, kMaxOutset); @@ -551,12 +563,25 @@ protected: SkTDArray<SkPoint> offsetPoly; size_t count = fConvexOnly ? SK_ARRAY_COUNT(insets) : SK_ARRAY_COUNT(offsets); + SkScalar localCenterX = bounds.centerX(); for (size_t i = 0; i < count; ++i) { + SkScalar offset = fConvexOnly ? insets[i] : offsets[i]; + std::function<SkScalar(const SkPoint&)> offsetFunc; + if (fVariableOffset) { + offsetFunc = [offset, localCenterX](const SkPoint& p) { + return offset + 0.04f*(p.fX - localCenterX); + }; + } else { + offsetFunc = [offset](const SkPoint& p) { + return offset; + }; + } + bool result; if (fConvexOnly) { - result = SkInsetConvexPolygon(data.get(), numPts, insets[i], &offsetPoly); + result = SkInsetConvexPolygon(data.get(), numPts, offsetFunc, &offsetPoly); } else { - result = SkOffsetSimplePolygon(data.get(), numPts, offsets[i], &offsetPoly); + result = SkOffsetSimplePolygon(data.get(), numPts, offsetFunc, &offsetPoly); } if (result) { SkPath path; @@ -595,12 +620,15 @@ private: static constexpr int kGMHeight = 512; bool fConvexOnly; + bool fVariableOffset; typedef GM INHERITED; }; ////////////////////////////////////////////////////////////////////////////// -DEF_GM(return new PolygonOffsetGM(true);) -DEF_GM(return new PolygonOffsetGM(false);) +DEF_GM(return new PolygonOffsetGM(true, false);) +DEF_GM(return new PolygonOffsetGM(true, true);) +DEF_GM(return new PolygonOffsetGM(false, false);) +DEF_GM(return new PolygonOffsetGM(false, true);) } diff --git a/src/utils/SkOffsetPolygon.cpp b/src/utils/SkOffsetPolygon.cpp index 47b41250e2..b335a25f0a 100755 --- a/src/utils/SkOffsetPolygon.cpp +++ b/src/utils/SkOffsetPolygon.cpp @@ -52,44 +52,63 @@ static int get_winding(const SkPoint* polygonVerts, int polygonSize) { return 0; } -// Offset line segment p0-p1 'd0' and 'd1' units in the direction specified by 'side' -bool SkOffsetSegment(const SkPoint& p0, const SkPoint& p1, SkScalar d0, SkScalar d1, - int side, SkPoint* offset0, SkPoint* offset1) { +// Helper function to compute the individual vector for non-equal offsets +inline void compute_offset(SkScalar d, const SkPoint& polyPoint, int side, + const SkPoint& outerTangentIntersect, SkVector* v) { + SkScalar dsq = d * d; + SkVector dP = outerTangentIntersect - polyPoint; + SkScalar dPlenSq = SkPointPriv::LengthSqd(dP); + if (SkScalarNearlyZero(dPlenSq)) { + v->set(0, 0); + } else { + SkScalar discrim = SkScalarSqrt(dPlenSq - dsq); + v->fX = (dsq*dP.fX - side * d*dP.fY*discrim) / dPlenSq; + v->fY = (dsq*dP.fY + side * d*dP.fX*discrim) / dPlenSq; + } +} + +// Compute difference vector to offset p0-p1 'd0' and 'd1' units in direction specified by 'side' +bool compute_offset_vectors(const SkPoint& p0, const SkPoint& p1, SkScalar d0, SkScalar d1, + int side, SkPoint* vector0, SkPoint* vector1) { SkASSERT(side == -1 || side == 1); - SkVector perp = SkVector::Make(p0.fY - p1.fY, p1.fX - p0.fX); if (SkScalarNearlyEqual(d0, d1)) { // if distances are equal, can just outset by the perpendicular + SkVector perp = SkVector::Make(p0.fY - p1.fY, p1.fX - p0.fX); perp.setLength(d0*side); - *offset0 = p0 + perp; - *offset1 = p1 + perp; + *vector0 = perp; + *vector1 = perp; } else { + SkScalar d0abs = SkTAbs(d0); + SkScalar d1abs = SkTAbs(d1); // Otherwise we need to compute the outer tangent. // See: http://www.ambrsoft.com/TrigoCalc/Circles2/Circles2Tangent_.htm - if (d0 < d1) { + if (d0abs < d1abs) { side = -side; } - SkScalar dD = d0 - d1; + SkScalar dD = d0abs - d1abs; // if one circle is inside another, we can't compute an offset if (dD*dD >= SkPointPriv::DistanceToSqd(p0, p1)) { return false; } - SkPoint outerTangentIntersect = SkPoint::Make((p1.fX*d0 - p0.fX*d1) / dD, - (p1.fY*d0 - p0.fY*d1) / dD); + SkPoint outerTangentIntersect = SkPoint::Make((p1.fX*d0abs - p0.fX*d1abs) / dD, + (p1.fY*d0abs - p0.fY*d1abs) / dD); + + compute_offset(d0, p0, side, outerTangentIntersect, vector0); + compute_offset(d1, p1, side, outerTangentIntersect, vector1); + } - SkScalar d0sq = d0*d0; - SkVector dP = outerTangentIntersect - p0; - SkScalar dPlenSq = SkPointPriv::LengthSqd(dP); - SkScalar discrim = SkScalarSqrt(dPlenSq - d0sq); - offset0->fX = p0.fX + (d0sq*dP.fX - side*d0*dP.fY*discrim) / dPlenSq; - offset0->fY = p0.fY + (d0sq*dP.fY + side*d0*dP.fX*discrim) / dPlenSq; + return true; +} - SkScalar d1sq = d1*d1; - dP = outerTangentIntersect - p1; - dPlenSq = SkPointPriv::LengthSqd(dP); - discrim = SkScalarSqrt(dPlenSq - d1sq); - offset1->fX = p1.fX + (d1sq*dP.fX - side*d1*dP.fY*discrim) / dPlenSq; - offset1->fY = p1.fY + (d1sq*dP.fY + side*d1*dP.fX*discrim) / dPlenSq; +// Offset line segment p0-p1 'd0' and 'd1' units in the direction specified by 'side' +bool SkOffsetSegment(const SkPoint& p0, const SkPoint& p1, SkScalar d0, SkScalar d1, + int side, SkPoint* offset0, SkPoint* offset1) { + SkVector v0, v1; + if (!compute_offset_vectors(p0, p1, d0, d1, side, &v0, &v1)) { + return false; } + *offset0 = p0 + v0; + *offset1 = p1 + v1; return true; } @@ -255,7 +274,7 @@ struct EdgeData { // Note: the assumption is that inputPolygon is convex and has no coincident points. // bool SkInsetConvexPolygon(const SkPoint* inputPolygonVerts, int inputPolygonSize, - std::function<SkScalar(int index)> insetDistanceFunc, + std::function<SkScalar(const SkPoint&)> insetDistanceFunc, SkTDArray<SkPoint>* insetPolygon) { if (inputPolygonSize < 3) { return false; @@ -277,7 +296,8 @@ bool SkInsetConvexPolygon(const SkPoint* inputPolygonVerts, int inputPolygonSize return false; } if (!SkOffsetSegment(inputPolygonVerts[i], inputPolygonVerts[j], - insetDistanceFunc(i), insetDistanceFunc(j), + insetDistanceFunc(inputPolygonVerts[i]), + insetDistanceFunc(inputPolygonVerts[j]), winding, &edgeData[i].fInset.fP0, &edgeData[i].fInset.fP1)) { return false; @@ -588,8 +608,8 @@ static bool is_simple_polygon(const SkPoint* polygon, int polygonSize) { // TODO: assuming a constant offset here -- do we want to support variable offset? bool SkOffsetSimplePolygon(const SkPoint* inputPolygonVerts, int inputPolygonSize, - SkScalar offset, SkTDArray<SkPoint>* offsetPolygon, - SkTDArray<int>* polygonIndices) { + std::function<SkScalar(const SkPoint&)> offsetDistanceFunc, + SkTDArray<SkPoint>* offsetPolygon, SkTDArray<int>* polygonIndices) { if (inputPolygonSize < 3) { return false; } @@ -599,25 +619,30 @@ bool SkOffsetSimplePolygon(const SkPoint* inputPolygonVerts, int inputPolygonSiz } // compute area and use sign to determine winding - // do initial pass to build normals - SkAutoSTMalloc<64, SkVector> normals(inputPolygonSize); SkScalar quadArea = 0; for (int curr = 0; curr < inputPolygonSize; ++curr) { int next = (curr + 1) % inputPolygonSize; - SkVector tangent = inputPolygonVerts[next] - inputPolygonVerts[curr]; - SkVector normal = SkVector::Make(-tangent.fY, tangent.fX); - normals[curr] = normal; quadArea += inputPolygonVerts[curr].cross(inputPolygonVerts[next]); } - // 1 == ccw, -1 == cw - int winding = (quadArea > 0) ? 1 : -1; - if (0 == winding) { + if (SkScalarNearlyZero(quadArea)) { return false; } + // 1 == ccw, -1 == cw + int winding = (quadArea > 0) ? 1 : -1; - // resize normals to match offset + // build normals + SkAutoSTMalloc<64, SkVector> normal0(inputPolygonSize); + SkAutoSTMalloc<64, SkVector> normal1(inputPolygonSize); + SkScalar currOffset = offsetDistanceFunc(inputPolygonVerts[0]); for (int curr = 0; curr < inputPolygonSize; ++curr) { - normals[curr].setLength(winding*offset); + int next = (curr + 1) % inputPolygonSize; + SkScalar nextOffset = offsetDistanceFunc(inputPolygonVerts[next]); + if (!compute_offset_vectors(inputPolygonVerts[curr], inputPolygonVerts[next], + currOffset, nextOffset, winding, + &normal0[curr], &normal1[next])) { + return false; + } + currOffset = nextOffset; } // build initial offset edge list @@ -629,13 +654,13 @@ bool SkOffsetSimplePolygon(const SkPoint* inputPolygonVerts, int inputPolygonSiz int side = compute_side(inputPolygonVerts[prevIndex], inputPolygonVerts[currIndex], inputPolygonVerts[nextIndex]); - + SkScalar offset = offsetDistanceFunc(inputPolygonVerts[currIndex]); // if reflex point, fill in curve if (side*winding*offset < 0) { SkScalar rotSin, rotCos; int numSteps; - SkVector prevNormal = normals[prevIndex]; - compute_radial_steps(prevNormal, normals[currIndex], SkScalarAbs(offset), + SkVector prevNormal = normal1[currIndex]; + compute_radial_steps(prevNormal, normal0[currIndex], SkScalarAbs(offset), &rotSin, &rotCos, &numSteps); for (int i = 0; i < numSteps - 1; ++i) { SkVector currNormal = SkVector::Make(prevNormal.fX*rotCos - prevNormal.fY*rotSin, @@ -648,14 +673,14 @@ bool SkOffsetSimplePolygon(const SkPoint* inputPolygonVerts, int inputPolygonSiz } EdgeData& edge = edgeData.push_back(); edge.fInset.fP0 = inputPolygonVerts[currIndex] + prevNormal; - edge.fInset.fP1 = inputPolygonVerts[currIndex] + normals[currIndex]; + edge.fInset.fP1 = inputPolygonVerts[currIndex] + normal0[currIndex]; edge.init(currIndex, currIndex); } // Add the edge EdgeData& edge = edgeData.push_back(); - edge.fInset.fP0 = inputPolygonVerts[currIndex] + normals[currIndex]; - edge.fInset.fP1 = inputPolygonVerts[nextIndex] + normals[currIndex]; + edge.fInset.fP0 = inputPolygonVerts[currIndex] + normal0[currIndex]; + edge.fInset.fP1 = inputPolygonVerts[nextIndex] + normal1[nextIndex]; edge.init(currIndex, nextIndex); prevIndex = currIndex; diff --git a/src/utils/SkOffsetPolygon.h b/src/utils/SkOffsetPolygon.h index b6c3a222ad..4c98ac0706 100755 --- a/src/utils/SkOffsetPolygon.h +++ b/src/utils/SkOffsetPolygon.h @@ -14,44 +14,76 @@ #include "SkPoint.h" /** - * Generates a polygon that is inset a given distance from the boundary of a given convex polygon. + * Generates a polygon that is inset a variable distance (controlled by offsetDistanceFunc) + * from the boundary of a given convex polygon. * * @param inputPolygonVerts Array of points representing the vertices of the original polygon. * It should be convex and have no coincident points. * @param inputPolygonSize Number of vertices in the original polygon. - * @param insetDistanceFunc How far we wish to inset the polygon for a given index in the array. + * @param insetDistanceFunc How far we wish to inset the polygon for a given position. * This should return a positive value. * @param insetPolygon The resulting inset polygon, if any. * @return true if an inset polygon exists, false otherwise. */ bool SkInsetConvexPolygon(const SkPoint* inputPolygonVerts, int inputPolygonSize, - std::function<SkScalar(int index)> insetDistanceFunc, + std::function<SkScalar(const SkPoint&)> insetDistanceFunc, SkTDArray<SkPoint>* insetPolygon); +/** + * Generates a polygon that is inset a constant from the boundary of a given convex polygon. + * + * @param inputPolygonVerts Array of points representing the vertices of the original polygon. + * It should be convex and have no coincident points. + * @param inputPolygonSize Number of vertices in the original polygon. + * @param inset How far we wish to inset the polygon. This should be a positive value. + * @param insetPolygon The resulting inset polygon, if any. + * @return true if an inset polygon exists, false otherwise. + */ inline bool SkInsetConvexPolygon(const SkPoint* inputPolygonVerts, int inputPolygonSize, SkScalar inset, SkTDArray<SkPoint>* insetPolygon) { return SkInsetConvexPolygon(inputPolygonVerts, inputPolygonSize, - [inset](int) { return inset; }, + [inset](const SkPoint&) { return inset; }, insetPolygon); } /** - * Generates a simple polygon (if possible) that is offset a given distance from the boundary of a - * given simple polygon. + * Generates a simple polygon (if possible) that is offset a variable distance (controlled by + * offsetDistanceFunc) from the boundary of a given simple polygon. * * @param inputPolygonVerts Array of points representing the vertices of the original polygon. * @param inputPolygonSize Number of vertices in the original polygon. - * @param offset How far we wish to offset the polygon. - * Positive value means inset, negative value means outset. + * @param offsetDistanceFunc How far we wish to offset the polygon for a given position. + * Positive values indicate insetting, negative values outsetting. * @param offsetPolgon The resulting offset polygon, if any. * @param polygonIndices The indices of the original polygon that map to the new one. * @return true if an offset simple polygon exists, false otherwise. */ bool SkOffsetSimplePolygon(const SkPoint* inputPolygonVerts, int inputPolygonSize, - SkScalar offset, SkTDArray<SkPoint>* offsetPolygon, + std::function<SkScalar(const SkPoint&)> offsetDistanceFunc, + SkTDArray<SkPoint>* offsetPolygon, SkTDArray<int>* polygonIndices = nullptr); /** + * Generates a simple polygon (if possible) that is offset a constant distance from the boundary + * of a given simple polygon. + * + * @param inputPolygonVerts Array of points representing the vertices of the original polygon. + * @param inputPolygonSize Number of vertices in the original polygon. + * @param offset How far we wish to offset the polygon. + * Positive values indicate insetting, negative values outsetting. + * @param offsetPolgon The resulting offset polygon, if any. + * @param polygonIndices The indices of the original polygon that map to the new one. + * @return true if an offset simple polygon exists, false otherwise. + */ +inline bool SkOffsetSimplePolygon(const SkPoint* inputPolygonVerts, int inputPolygonSize, + SkScalar offset, SkTDArray<SkPoint>* offsetPolygon, + SkTDArray<int>* polygonIndices = nullptr) { + return SkOffsetSimplePolygon(inputPolygonVerts, inputPolygonSize, + [offset](const SkPoint&) { return offset; }, + offsetPolygon, polygonIndices); +} + +/** * Offset a segment by the given distance at each point. * Uses the outer tangents of two circles centered on each endpoint. * See: https://en.wikipedia.org/wiki/Tangent_lines_to_circles |