Add ear-clipping code to triangulate simple polygons.

Use this to fill concave shadows.

Bug: skia:7971
Change-Id: I63dc1ed845f9fa3fcd86f1ad13b03da23cae0313
Reviewed-on: https://skia-review.googlesource.com/135200
Commit-Queue: Jim Van Verth <jvanverth@google.com>
Reviewed-by: Robert Phillips <robertphillips@google.com>

1 files changed, 0 insertions, 805 deletions

diff --git a/src/utils/SkOffsetPolygon.cpp b/src/utils/SkOffsetPolygon.cpp
deleted file mode 100755
index c72f7d407b..0000000000
--- a/src/utils/SkOffsetPolygon.cpp
+++ /dev/null
@@ -1,805 +0,0 @@
-/*
- * 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 "SkTArray.h"
-#include "SkTemplates.h"
-#include "SkTDPQueue.h"
-
-struct OffsetSegment {
-    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;
-}
-
-// 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);
-    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);
-        *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 (d0abs < d1abs) {
-            side = -side;
-        }
-        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*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);
-    }
-
-    return true;
-}
-
-// 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;
-}
-
-// 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 OffsetSegment& s0, const OffsetSegment& s1,
-                                 SkPoint* p, SkScalar* s, SkScalar* t) {
-    // Common cases for polygon chains -- 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;
-    }
-
-    SkVector v0 = s0.fP1 - s0.fP0;
-    SkVector v1 = s1.fP1 - s1.fP0;
-    // We should have culled coincident points before this
-    SkASSERT(!SkPointPriv::EqualsWithinTolerance(s0.fP0, s0.fP1));
-    SkASSERT(!SkPointPriv::EqualsWithinTolerance(s1.fP0, s1.fP1));
-
-    SkVector d = s1.fP0 - s0.fP0;
-    SkScalar perpDot = v0.cross(v1);
-    SkScalar localS, localT;
-    if (SkScalarNearlyZero(perpDot)) {
-        // segments are parallel, but not collinear
-        if (!SkScalarNearlyZero(d.dot(d), SK_ScalarNearlyZero*SK_ScalarNearlyZero)) {
-            return false;
-        }
-
-        // project segment1's endpoints onto segment0
-        localS = d.fX / v0.fX;
-        localT = 0;
-        if (localS < 0 || localS > SK_Scalar1) {
-            // the first endpoint doesn't lie on segment0, try the other one
-            SkScalar oldLocalS = localS;
-            localS = (s1.fP1.fX - s0.fP0.fX) / v0.fX;
-            localT = SK_Scalar1;
-            if (localS < 0 || localS > SK_Scalar1) {
-                // it's possible that segment1's interval surrounds segment0
-                // this is false if the params have the same signs, and in that case no collision
-                if (localS*oldLocalS > 0) {
-                    return false;
-                }
-                // otherwise project segment0's endpoint onto segment1 instead
-                localS = 0;
-                localT = -d.fX / v1.fX;
-            }
-        }
-    } else {
-        localS = d.cross(v1) / perpDot;
-        if (localS < 0 || localS > SK_Scalar1) {
-            return false;
-        }
-        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;
-}
-
-// computes the line intersection and then the distance to s0's endpoint
-static SkScalar compute_crossing_distance(const OffsetSegment& s0, const OffsetSegment& s1) {
-    SkVector v0 = s0.fP1 - s0.fP0;
-    SkVector v1 = s1.fP1 - s1.fP0;
-
-    SkScalar perpDot = v0.cross(v1);
-    if (SkScalarNearlyZero(perpDot)) {
-        // segments are parallel
-        return SK_ScalarMax;
-    }
-
-    SkVector d = s1.fP0 - s0.fP0;
-    SkScalar localS = d.cross(v1) / perpDot;
-    if (localS < 0) {
-        localS = -localS;
-    } else {
-        localS -= SK_Scalar1;
-    }
-
-    localS *= v0.length();
-
-    return localS;
-}
-
-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;
-}
-
-struct EdgeData {
-    OffsetSegment fInset;
-    SkPoint       fIntersection;
-    SkScalar      fTValue;
-    uint16_t      fStart;
-    uint16_t      fEnd;
-    uint16_t      fIndex;
-    bool          fValid;
-
-    void init() {
-        fIntersection = fInset.fP0;
-        fTValue = SK_ScalarMin;
-        fStart = 0;
-        fEnd = 0;
-        fIndex = 0;
-        fValid = true;
-    }
-
-    void init(uint16_t start, uint16_t end) {
-        fIntersection = fInset.fP0;
-        fTValue = SK_ScalarMin;
-        fStart = start;
-        fEnd = end;
-        fIndex = start;
-        fValid = 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(const SkPoint&)> insetDistanceFunc,
-                          SkTDArray<SkPoint>* insetPolygon) {
-    if (inputPolygonSize < 3) {
-        return false;
-    }
-
-    int winding = get_winding(inputPolygonVerts, inputPolygonSize);
-    if (0 == winding) {
-        return false;
-    }
-
-    // set up
-    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;
-        }
-        if (!SkOffsetSegment(inputPolygonVerts[i], inputPolygonVerts[j],
-                             insetDistanceFunc(inputPolygonVerts[i]),
-                             insetDistanceFunc(inputPolygonVerts[j]),
-                             winding,
-                             &edgeData[i].fInset.fP0, &edgeData[i].fInset.fP1)) {
-            return false;
-        }
-        edgeData[i].init();
-    }
-
-    int prevIndex = inputPolygonSize - 1;
-    int currIndex = 0;
-    int insetVertexCount = inputPolygonSize;
-    int iterations = 0;
-    while (prevIndex != currIndex) {
-        ++iterations;
-        // we should check each edge against each other edge at most once
-        if (iterations > inputPolygonSize*inputPolygonSize) {
-            return false;
-        }
-
-        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();
-    if (insetVertexCount >= 0) {
-        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));
-}
-
-// compute the number of points needed for a circular join when offsetting a  reflex vertex
-static void compute_radial_steps(const SkVector& v1, const SkVector& v2, SkScalar r,
-                                 SkScalar* rotSin, SkScalar* rotCos, int* n) {
-    const SkScalar kRecipPixelsPerArcSegment = 0.25f;
-
-    SkScalar rCos = v1.dot(v2);
-    SkScalar rSin = v1.cross(v2);
-    SkScalar theta = SkScalarATan2(rSin, rCos);
-
-    int steps = SkScalarRoundToInt(SkScalarAbs(r*theta*kRecipPixelsPerArcSegment));
-
-    SkScalar dTheta = theta / steps;
-    *rotSin = SkScalarSinCos(dTheta, rotCos);
-    *n = steps;
-}
-
-// tolerant less-than comparison
-static inline bool nearly_lt(SkScalar a, SkScalar b, SkScalar tolerance = SK_ScalarNearlyZero) {
-    return a < b - tolerance;
-}
-
-// a point is "left" to another if its x coordinate is less, or if equal, its y coordinate
-static bool left(const SkPoint& p0, const SkPoint& p1) {
-    return nearly_lt(p0.fX, p1.fX) ||
-           (SkScalarNearlyEqual(p0.fX, p1.fX) && nearly_lt(p0.fY, p1.fY));
-}
-
-struct Vertex {
-    static bool Left(const Vertex& qv0, const Vertex& qv1) {
-        return left(qv0.fPosition, qv1.fPosition);
-    }
-    // packed to fit into 16 bytes (one cache line)
-    SkPoint  fPosition;
-    uint16_t fIndex;       // index in unsorted polygon
-    uint16_t fPrevIndex;   // indices for previous and next vertex in unsorted polygon
-    uint16_t fNextIndex;
-    uint16_t fFlags;
-};
-
-enum VertexFlags {
-    kPrevLeft_VertexFlag = 0x1,
-    kNextLeft_VertexFlag = 0x2,
-};
-
-struct Edge {
-    // returns true if "this" is above "that"
-    bool above(const Edge& that, SkScalar tolerance = SK_ScalarNearlyZero) {
-        SkASSERT(nearly_lt(this->fSegment.fP0.fX, that.fSegment.fP0.fX, tolerance) ||
-                 SkScalarNearlyEqual(this->fSegment.fP0.fX, that.fSegment.fP0.fX, tolerance));
-        // The idea here is that if the vector between the origins of the two segments (dv)
-        // rotates counterclockwise up to the vector representing the "this" segment (u),
-        // then we know that "this" is above that. If the result is clockwise we say it's below.
-        SkVector dv = that.fSegment.fP0 - this->fSegment.fP0;
-        SkVector u = this->fSegment.fP1 - this->fSegment.fP0;
-        SkScalar cross = dv.cross(u);
-        if (cross > tolerance) {
-            return true;
-        } else if (cross < -tolerance) {
-            return false;
-        }
-        // If the result is 0 then either the two origins are equal or the origin of "that"
-        // lies on dv. So then we try the same for the vector from the tail of "this"
-        // to the head of "that". Again, ccw means "this" is above "that".
-        dv = that.fSegment.fP1 - this->fSegment.fP0;
-        return (dv.cross(u) > tolerance);
-    }
-
-    bool intersect(const Edge& that) const {
-        SkPoint intersection;
-        SkScalar s, t;
-        // check first to see if these edges are neighbors in the polygon
-        if (this->fIndex0 == that.fIndex0 || this->fIndex1 == that.fIndex0 ||
-            this->fIndex0 == that.fIndex1 || this->fIndex1 == that.fIndex1) {
-            return false;
-        }
-        return compute_intersection(this->fSegment, that.fSegment, &intersection, &s, &t);
-    }
-
-    bool operator==(const Edge& that) const {
-        return (this->fIndex0 == that.fIndex0 && this->fIndex1 == that.fIndex1);
-    }
-
-    bool operator!=(const Edge& that) const {
-        return !operator==(that);
-    }
-
-    OffsetSegment fSegment;
-    int32_t fIndex0;   // indices for previous and next vertex
-    int32_t fIndex1;
-};
-
-class EdgeList {
-public:
-    void reserve(int count) { fEdges.reserve(count); }
-
-    bool insert(const Edge& newEdge) {
-        // linear search for now (expected case is very few active edges)
-        int insertIndex = 0;
-        while (insertIndex < fEdges.count() && fEdges[insertIndex].above(newEdge)) {
-            ++insertIndex;
-        }
-        // if we intersect with the existing edge above or below us
-        // then we know this polygon is not simple, so don't insert, just fail
-        if (insertIndex > 0 && newEdge.intersect(fEdges[insertIndex - 1])) {
-            return false;
-        }
-        if (insertIndex < fEdges.count() && newEdge.intersect(fEdges[insertIndex])) {
-            return false;
-        }
-
-        fEdges.push_back();
-        for (int i = fEdges.count() - 1; i > insertIndex; --i) {
-            fEdges[i] = fEdges[i - 1];
-        }
-        fEdges[insertIndex] = newEdge;
-
-        return true;
-    }
-
-    bool remove(const Edge& edge) {
-        SkASSERT(fEdges.count() > 0);
-
-        // linear search for now (expected case is very few active edges)
-        int removeIndex = 0;
-        while (removeIndex < fEdges.count() && fEdges[removeIndex] != edge) {
-            ++removeIndex;
-        }
-        // we'd better find it or something is wrong
-        SkASSERT(removeIndex < fEdges.count());
-
-        // if we intersect with the edge above or below us
-        // then we know this polygon is not simple, so don't remove, just fail
-        if (removeIndex > 0 && fEdges[removeIndex].intersect(fEdges[removeIndex-1])) {
-            return false;
-        }
-        if (removeIndex < fEdges.count()-1) {
-            if (fEdges[removeIndex].intersect(fEdges[removeIndex + 1])) {
-                return false;
-            }
-            // copy over the old entry
-            memmove(&fEdges[removeIndex], &fEdges[removeIndex + 1],
-                    sizeof(Edge)*(fEdges.count() - removeIndex - 1));
-        }
-
-        fEdges.pop_back();
-        return true;
-    }
-
-private:
-    SkSTArray<1, Edge> fEdges;
-};
-
-// Here we implement a sweep line algorithm to determine whether the provided points
-// represent a simple polygon, i.e., the polygon is non-self-intersecting.
-// We first insert the vertices into a priority queue sorting horizontally from left to right.
-// Then as we pop the vertices from the queue we generate events which indicate that an edge
-// should be added or removed from an edge list. If any intersections are detected in the edge
-// list, then we know the polygon is self-intersecting and hence not simple.
-static bool is_simple_polygon(const SkPoint* polygon, int polygonSize) {
-    SkTDPQueue <Vertex, Vertex::Left> vertexQueue;
-    EdgeList sweepLine;
-
-    sweepLine.reserve(polygonSize);
-    for (int i = 0; i < polygonSize; ++i) {
-        Vertex newVertex;
-        newVertex.fPosition = polygon[i];
-        newVertex.fIndex = i;
-        newVertex.fPrevIndex = (i - 1 + polygonSize) % polygonSize;
-        newVertex.fNextIndex = (i + 1) % polygonSize;
-        newVertex.fFlags = 0;
-        if (left(polygon[newVertex.fPrevIndex], polygon[i])) {
-            newVertex.fFlags |= kPrevLeft_VertexFlag;
-        }
-        if (left(polygon[newVertex.fNextIndex], polygon[i])) {
-            newVertex.fFlags |= kNextLeft_VertexFlag;
-        }
-        vertexQueue.insert(newVertex);
-    }
-
-    // pop each vertex from the queue and generate events depending on
-    // where it lies relative to its neighboring edges
-    while (vertexQueue.count() > 0) {
-        const Vertex& v = vertexQueue.peek();
-
-        // check edge to previous vertex
-        if (v.fFlags & kPrevLeft_VertexFlag) {
-            Edge edge{ { polygon[v.fPrevIndex], v.fPosition }, v.fPrevIndex, v.fIndex };
-            if (!sweepLine.remove(edge)) {
-                break;
-            }
-        } else {
-            Edge edge{ { v.fPosition, polygon[v.fPrevIndex] }, v.fIndex, v.fPrevIndex };
-            if (!sweepLine.insert(edge)) {
-                break;
-            }
-        }
-
-        // check edge to next vertex
-        if (v.fFlags & kNextLeft_VertexFlag) {
-            Edge edge{ { polygon[v.fNextIndex], v.fPosition }, v.fNextIndex, v.fIndex };
-            if (!sweepLine.remove(edge)) {
-                break;
-            }
-        } else {
-            Edge edge{ { v.fPosition, polygon[v.fNextIndex] }, v.fIndex, v.fNextIndex };
-            if (!sweepLine.insert(edge)) {
-                break;
-            }
-        }
-
-        vertexQueue.pop();
-    }
-
-    return (vertexQueue.count() == 0);
-}
-
-// TODO: assuming a constant offset here -- do we want to support variable offset?
-bool SkOffsetSimplePolygon(const SkPoint* inputPolygonVerts, int inputPolygonSize,
-                           std::function<SkScalar(const SkPoint&)> offsetDistanceFunc,
-                           SkTDArray<SkPoint>* offsetPolygon, SkTDArray<int>* polygonIndices) {
-    if (inputPolygonSize < 3) {
-        return false;
-    }
-
-    if (!is_simple_polygon(inputPolygonVerts, inputPolygonSize)) {
-        return false;
-    }
-
-    // compute area and use sign to determine winding
-    SkScalar quadArea = 0;
-    for (int curr = 0; curr < inputPolygonSize; ++curr) {
-        int next = (curr + 1) % inputPolygonSize;
-        quadArea += inputPolygonVerts[curr].cross(inputPolygonVerts[next]);
-    }
-    if (SkScalarNearlyZero(quadArea)) {
-        return false;
-    }
-    // 1 == ccw, -1 == cw
-    int winding = (quadArea > 0) ? 1 : -1;
-
-    // build normals
-    SkAutoSTMalloc<64, SkVector> normal0(inputPolygonSize);
-    SkAutoSTMalloc<64, SkVector> normal1(inputPolygonSize);
-    SkScalar currOffset = offsetDistanceFunc(inputPolygonVerts[0]);
-    for (int curr = 0; curr < inputPolygonSize; ++curr) {
-        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
-    SkSTArray<64, EdgeData> edgeData(inputPolygonSize);
-    int prevIndex = inputPolygonSize - 1;
-    int currIndex = 0;
-    int nextIndex = 1;
-    while (currIndex < inputPolygonSize) {
-        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 = 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,
-                                                     prevNormal.fY*rotCos + prevNormal.fX*rotSin);
-                EdgeData& edge = edgeData.push_back();
-                edge.fInset.fP0 = inputPolygonVerts[currIndex] + prevNormal;
-                edge.fInset.fP1 = inputPolygonVerts[currIndex] + currNormal;
-                edge.init(currIndex, currIndex);
-                prevNormal = currNormal;
-            }
-            EdgeData& edge = edgeData.push_back();
-            edge.fInset.fP0 = inputPolygonVerts[currIndex] + prevNormal;
-            edge.fInset.fP1 = inputPolygonVerts[currIndex] + normal0[currIndex];
-            edge.init(currIndex, currIndex);
-        }
-
-        // Add the edge
-        EdgeData& edge = edgeData.push_back();
-        edge.fInset.fP0 = inputPolygonVerts[currIndex] + normal0[currIndex];
-        edge.fInset.fP1 = inputPolygonVerts[nextIndex] + normal1[nextIndex];
-        edge.init(currIndex, nextIndex);
-
-        prevIndex = currIndex;
-        currIndex++;
-        nextIndex = (nextIndex + 1) % inputPolygonSize;
-    }
-
-    int edgeDataSize = edgeData.count();
-    prevIndex = edgeDataSize - 1;
-    currIndex = 0;
-    int insetVertexCount = edgeDataSize;
-    int iterations = 0;
-    while (prevIndex != currIndex) {
-        ++iterations;
-        // we should check each edge against each other edge at most once
-        if (iterations > edgeDataSize*edgeDataSize) {
-            return false;
-        }
-
-        if (!edgeData[prevIndex].fValid) {
-            prevIndex = (prevIndex + edgeDataSize - 1) % edgeDataSize;
-            continue;
-        }
-        if (!edgeData[currIndex].fValid) {
-            currIndex = (currIndex + 1) % edgeDataSize;
-            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 + edgeDataSize - 1) % edgeDataSize;
-                // 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;
-                edgeData[currIndex].fIndex = edgeData[prevIndex].fEnd;
-
-                // go to next segment
-                prevIndex = currIndex;
-                currIndex = (currIndex + 1) % edgeDataSize;
-            }
-        } else {
-            // If there is no intersection, we want to minimize the distance between
-            // the point where the segment lines cross and the segments themselves.
-            SkScalar prevPrevIndex = (prevIndex + edgeDataSize - 1) % edgeDataSize;
-            SkScalar currNextIndex = (currIndex + 1) % edgeDataSize;
-            SkScalar dist0 = compute_crossing_distance(edgeData[currIndex].fInset,
-                                                       edgeData[prevPrevIndex].fInset);
-            SkScalar dist1 = compute_crossing_distance(edgeData[prevIndex].fInset,
-                                                       edgeData[currNextIndex].fInset);
-            if (dist0 < dist1) {
-                edgeData[prevIndex].fValid = false;
-                prevIndex = prevPrevIndex;
-            } else {
-                edgeData[currIndex].fValid = false;
-                currIndex = currNextIndex;
-            }
-            --insetVertexCount;
-        }
-    }
-
-    // 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;
-
-    offsetPolygon->reset();
-    offsetPolygon->setReserve(insetVertexCount);
-    currIndex = -1;
-    for (int i = 0; i < edgeData.count(); ++i) {
-        if (edgeData[i].fValid && (currIndex == -1 ||
-                                   !SkPointPriv::EqualsWithinTolerance(edgeData[i].fIntersection,
-                                                                       (*offsetPolygon)[currIndex],
-                                                                       kCleanupTolerance))) {
-            *offsetPolygon->push() = edgeData[i].fIntersection;
-            if (polygonIndices) {
-                *polygonIndices->push() = edgeData[i].fIndex;
-            }
-            currIndex++;
-        }
-    }
-    // make sure the first and last points aren't coincident
-    if (currIndex >= 1 &&
-        SkPointPriv::EqualsWithinTolerance((*offsetPolygon)[0], (*offsetPolygon)[currIndex],
-                                           kCleanupTolerance)) {
-        offsetPolygon->pop();
-        if (polygonIndices) {
-            polygonIndices->pop();
-        }
-    }
-
-    // compute signed area to check winding (it should be same as the original polygon)
-    quadArea = 0;
-    for (int curr = 0; curr < offsetPolygon->count(); ++curr) {
-        int next = (curr + 1) % offsetPolygon->count();
-        quadArea += (*offsetPolygon)[curr].cross((*offsetPolygon)[next]);
-    }
-
-    return (winding*quadArea > 0 &&
-            is_simple_polygon(offsetPolygon->begin(), offsetPolygon->count()));
-}
-