blob: 8a55b133907357576895e765fc4411e0c929d3e3 [file] [log] [blame]
 /* * Copyright 2017 Google Inc. * * Use of this source code is governed by a BSD-style license that can be * found in the LICENSE file. */ #include "SkInsetConvexPolygon.h" #include "SkPointPriv.h" #include "SkTemplates.h" struct InsetSegment { SkPoint fP0; SkPoint fP1; }; // Computes perpDot for point compared to segment. // A positive value means the point is to the left of the segment, // negative is to the right, 0 is collinear. static int compute_side(const SkPoint& s0, const SkPoint& s1, const SkPoint& p) { SkVector v0 = s1 - s0; SkVector v1 = p - s0; SkScalar perpDot = v0.cross(v1); if (!SkScalarNearlyZero(perpDot)) { return ((perpDot > 0) ? 1 : -1); } return 0; } // returns 1 for ccw, -1 for cw and 0 if degenerate static int get_winding(const SkPoint* polygonVerts, int polygonSize) { SkPoint p0 = polygonVerts[0]; SkPoint p1 = polygonVerts[1]; for (int i = 2; i < polygonSize; ++i) { SkPoint p2 = polygonVerts[i]; // determine if cw or ccw int side = compute_side(p0, p1, p2); if (0 != side) { return ((side > 0) ? 1 : -1); } // if nearly collinear, treat as straight line and continue p1 = p2; } 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) { 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 perp.setLength(d0*side); *offset0 = p0 + perp; *offset1 = p1 + perp; } else { // Otherwise we need to compute the outer tangent. // See: http://www.ambrsoft.com/TrigoCalc/Circles2/Circles2Tangent_.htm if (d0 < d1) { side = -side; } SkScalar dD = d0 - d1; // 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); 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; 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; } return true; } // 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. static bool compute_intersection(const InsetSegment& s0, const InsetSegment& s1, SkPoint* p, SkScalar* s, SkScalar* t) { SkVector v0 = s0.fP1 - s0.fP0; SkVector v1 = s1.fP1 - s1.fP0; SkScalar perpDot = v0.cross(v1); if (SkScalarNearlyZero(perpDot)) { // segments are parallel // check if endpoints are touching if (SkPointPriv::EqualsWithinTolerance(s0.fP1, s1.fP0)) { *p = s0.fP1; *s = SK_Scalar1; *t = 0; return true; } if (SkPointPriv::EqualsWithinTolerance(s1.fP1, s0.fP0)) { *p = s1.fP1; *s = 0; *t = SK_Scalar1; return true; } return false; } SkVector d = s1.fP0 - s0.fP0; SkScalar localS = d.cross(v1) / perpDot; if (localS < 0 || localS > SK_Scalar1) { return false; } SkScalar localT = d.cross(v0) / perpDot; if (localT < 0 || localT > SK_Scalar1) { return false; } v0 *= localS; *p = s0.fP0 + v0; *s = localS; *t = localT; return true; } static bool is_convex(const SkTDArray& poly) { if (poly.count() <= 3) { return true; } 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; } // The objective here is to inset all of the edges by the given distance, and then // remove any invalid inset edges by detecting right-hand turns. In a ccw polygon, // we should only be making left-hand turns (for cw polygons, we use the winding // parameter to reverse this). We detect this by checking whether the second intersection // on an edge is closer to its tail than the first one. // // We might also have the case that there is no intersection between two neighboring inset edges. // In this case, one edge will lie to the right of the other and should be discarded along with // its previous intersection (if any). // // Note: the assumption is that inputPolygon is convex and has no coincident points. // bool SkInsetConvexPolygon(const SkPoint* inputPolygonVerts, int inputPolygonSize, std::function insetDistanceFunc, SkTDArray* insetPolygon) { if (inputPolygonSize < 3) { return false; } int winding = get_winding(inputPolygonVerts, inputPolygonSize); if (0 == winding) { return false; } // set up struct EdgeData { InsetSegment fInset; SkPoint fIntersection; SkScalar fTValue; bool fValid; }; SkAutoSTMalloc<64, EdgeData> edgeData(inputPolygonSize); for (int i = 0; i < inputPolygonSize; ++i) { int j = (i + 1) % inputPolygonSize; int k = (i + 2) % inputPolygonSize; // check for convexity just to be sure if (compute_side(inputPolygonVerts[i], inputPolygonVerts[j], inputPolygonVerts[k])*winding < 0) { return false; } SkOffsetSegment(inputPolygonVerts[i], inputPolygonVerts[j], insetDistanceFunc(i), insetDistanceFunc(j), winding, &edgeData[i].fInset.fP0, &edgeData[i].fInset.fP1); edgeData[i].fIntersection = edgeData[i].fInset.fP0; edgeData[i].fTValue = SK_ScalarMin; edgeData[i].fValid = true; } int prevIndex = inputPolygonSize - 1; int currIndex = 0; int insetVertexCount = inputPolygonSize; while (prevIndex != currIndex) { if (!edgeData[prevIndex].fValid) { prevIndex = (prevIndex + inputPolygonSize - 1) % inputPolygonSize; continue; } SkScalar s, t; SkPoint intersection; if (compute_intersection(edgeData[prevIndex].fInset, edgeData[currIndex].fInset, &intersection, &s, &t)) { // if new intersection is further back on previous inset from the prior intersection if (s < edgeData[prevIndex].fTValue) { // no point in considering this one again edgeData[prevIndex].fValid = false; --insetVertexCount; // go back one segment prevIndex = (prevIndex + inputPolygonSize - 1) % inputPolygonSize; // we've already considered this intersection, we're done } else if (edgeData[currIndex].fTValue > SK_ScalarMin && SkPointPriv::EqualsWithinTolerance(intersection, edgeData[currIndex].fIntersection, 1.0e-6f)) { break; } else { // add intersection edgeData[currIndex].fIntersection = intersection; edgeData[currIndex].fTValue = t; // go to next segment prevIndex = currIndex; currIndex = (currIndex + 1) % inputPolygonSize; } } else { // if prev to right side of curr int side = winding*compute_side(edgeData[currIndex].fInset.fP0, edgeData[currIndex].fInset.fP1, edgeData[prevIndex].fInset.fP1); if (side < 0 && side == winding*compute_side(edgeData[currIndex].fInset.fP0, edgeData[currIndex].fInset.fP1, edgeData[prevIndex].fInset.fP0)) { // no point in considering this one again edgeData[prevIndex].fValid = false; --insetVertexCount; // go back one segment prevIndex = (prevIndex + inputPolygonSize - 1) % inputPolygonSize; } else { // move to next segment edgeData[currIndex].fValid = false; --insetVertexCount; currIndex = (currIndex + 1) % inputPolygonSize; } } } // store all the valid intersections that aren't nearly coincident // TODO: look at the main algorithm and see if we can detect these better static constexpr SkScalar kCleanupTolerance = 0.01f; insetPolygon->reset(); insetPolygon->setReserve(insetVertexCount); currIndex = -1; for (int i = 0; i < inputPolygonSize; ++i) { if (edgeData[i].fValid && (currIndex == -1 || !SkPointPriv::EqualsWithinTolerance(edgeData[i].fIntersection, (*insetPolygon)[currIndex], kCleanupTolerance))) { *insetPolygon->push() = edgeData[i].fIntersection; currIndex++; } } // make sure the first and last points aren't coincident if (currIndex >= 1 && SkPointPriv::EqualsWithinTolerance((*insetPolygon)[0], (*insetPolygon)[currIndex], kCleanupTolerance)) { insetPolygon->pop(); } return (insetPolygon->count() >= 3 && is_convex(*insetPolygon)); }