diff options
author | Jim Van Verth <jvanverth@google.com> | 2018-06-14 09:09:18 -0400 |
---|---|---|
committer | Skia Commit-Bot <skia-commit-bot@chromium.org> | 2018-06-14 13:54:57 +0000 |
commit | bdde428d53ebe0bdf25c0a6048e3872427ef08d3 (patch) | |
tree | d8bff89d3e17903001d1555512fa040d6342f9be /src | |
parent | 10a83da287be541c2253bec23a92f1e5e1a79ff3 (diff) |
Add variable offset support
Bug: skia:7970
Change-Id: I9dadf75f21e19ebe26f82643bcc47dd5794d8970
Reviewed-on: https://skia-review.googlesource.com/134421
Commit-Queue: Jim Van Verth <jvanverth@google.com>
Reviewed-by: Robert Phillips <robertphillips@google.com>
Diffstat (limited to 'src')
-rwxr-xr-x | src/utils/SkOffsetPolygon.cpp | 109 | ||||
-rwxr-xr-x | src/utils/SkOffsetPolygon.h | 50 |
2 files changed, 108 insertions, 51 deletions
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 |