Rename SkInsetConvexPolygon to SkOffsetPolygon.
Prep for adding new offset routines.
Change-Id: I261c22d9998e5ae4567b697c5f20a31f20777ac1
Reviewed-on: https://skia-review.googlesource.com/116800
Reviewed-by: Robert Phillips <robertphillips@google.com>
Commit-Queue: Jim Van Verth <jvanverth@google.com>
diff --git a/src/utils/SkOffsetPolygon.cpp b/src/utils/SkOffsetPolygon.cpp
new file mode 100755
index 0000000..c8ebbeb
--- /dev/null
+++ b/src/utils/SkOffsetPolygon.cpp
@@ -0,0 +1,296 @@
+/*
+ * 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 "SkOffsetPolygon.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<SkPoint>& 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<SkScalar(int index)> insetDistanceFunc,
+ SkTDArray<SkPoint>* 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));
+}