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>

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