From 8664a1d7d719153e8e854ff0112519d92916cfe2 Mon Sep 17 00:00:00 2001 From: Jim Van Verth Date: Thu, 28 Jun 2018 16:26:50 -0400 Subject: 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 Reviewed-by: Robert Phillips --- gm/convex_all_line_paths.cpp | 2 +- gm/polygonoffset.cpp | 2 +- gn/utils.gni | 4 +- src/utils/SkOffsetPolygon.cpp | 805 ------------------------------ src/utils/SkOffsetPolygon.h | 103 ---- src/utils/SkPolyUtils.cpp | 996 ++++++++++++++++++++++++++++++++++++++ src/utils/SkPolyUtils.h | 143 ++++++ src/utils/SkShadowTessellator.cpp | 35 +- src/utils/SkShadowUtils.cpp | 8 +- tests/InsetConvexPolyTest.cpp | 2 +- tests/OffsetSimplePolyTest.cpp | 9 +- 11 files changed, 1165 insertions(+), 944 deletions(-) delete mode 100755 src/utils/SkOffsetPolygon.cpp delete mode 100755 src/utils/SkOffsetPolygon.h create mode 100755 src/utils/SkPolyUtils.cpp create mode 100755 src/utils/SkPolyUtils.h diff --git a/gm/convex_all_line_paths.cpp b/gm/convex_all_line_paths.cpp index b1907bccb7..e21711b2bc 100644 --- a/gm/convex_all_line_paths.cpp +++ b/gm/convex_all_line_paths.cpp @@ -6,7 +6,7 @@ */ #include "gm.h" -#include "SkOffsetPolygon.h" +#include "SkPolyUtils.h" #include "SkPathPriv.h" static void create_ngon(int n, SkPoint* pts, SkScalar width, SkScalar height) { diff --git a/gm/polygonoffset.cpp b/gm/polygonoffset.cpp index 48b6d1a4e4..44a313b285 100644 --- a/gm/polygonoffset.cpp +++ b/gm/polygonoffset.cpp @@ -7,7 +7,7 @@ #include "gm.h" #include "sk_tool_utils.h" -#include "SkOffsetPolygon.h" +#include "SkPolyUtils.h" #include "SkPathPriv.h" static void create_ngon(int n, SkPoint* pts, SkScalar w, SkScalar h, SkPath::Direction dir) { diff --git a/gn/utils.gni b/gn/utils.gni index 63b063bf46..95c4e937c7 100644 --- a/gn/utils.gni +++ b/gn/utils.gni @@ -47,8 +47,6 @@ skia_utils_sources = [ "$_src/utils/SkMultiPictureDocument.cpp", "$_src/utils/SkNWayCanvas.cpp", "$_src/utils/SkNullCanvas.cpp", - "$_src/utils/SkOffsetPolygon.cpp", - "$_src/utils/SkOffsetPolygon.h", "$_src/utils/SkOSPath.cpp", "$_src/utils/SkOSPath.h", "$_src/utils/SkPaintFilterCanvas.cpp", @@ -57,6 +55,8 @@ skia_utils_sources = [ "$_src/utils/SkParsePath.cpp", "$_src/utils/SkPatchUtils.cpp", "$_src/utils/SkPatchUtils.h", + "$_src/utils/SkPolyUtils.cpp", + "$_src/utils/SkPolyUtils.h", "$_src/utils/SkShadowTessellator.cpp", "$_src/utils/SkShadowTessellator.h", "$_src/utils/SkShadowUtils.cpp", 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& 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 insetDistanceFunc, - SkTDArray* 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 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 offsetDistanceFunc, - SkTDArray* offsetPolygon, SkTDArray* 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())); -} - diff --git a/src/utils/SkOffsetPolygon.h b/src/utils/SkOffsetPolygon.h deleted file mode 100755 index 4c98ac0706..0000000000 --- a/src/utils/SkOffsetPolygon.h +++ /dev/null @@ -1,103 +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. - */ - -#ifndef SkOffsetPolygon_DEFINED -#define SkOffsetPolygon_DEFINED - -#include - -#include "SkTDArray.h" -#include "SkPoint.h" - -/** - * 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 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 insetDistanceFunc, - SkTDArray* 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* insetPolygon) { - return SkInsetConvexPolygon(inputPolygonVerts, inputPolygonSize, - [inset](const SkPoint&) { return inset; }, - insetPolygon); -} - -/** - * 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 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, - std::function offsetDistanceFunc, - SkTDArray* offsetPolygon, - SkTDArray* 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* offsetPolygon, - SkTDArray* 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 - * - * @param p0 First endpoint. - * @param p1 Second endpoint. - * @param d0 Offset distance from first endpoint. - * @param d1 Offset distance from second endpoint. - * @param side Indicates whether we want to offset to the left (1) or right (-1) side of segment. - * @param offset0 First endpoint of offset segment. - * @param offset1 Second endpoint of offset segment. - * @return true if an offset segment exists, false otherwise. - */ -bool SkOffsetSegment(const SkPoint& p0, const SkPoint& p1, SkScalar d0, SkScalar d1, - int side, SkPoint* offset0, SkPoint* offset1); - -#endif diff --git a/src/utils/SkPolyUtils.cpp b/src/utils/SkPolyUtils.cpp new file mode 100755 index 0000000000..ea9d649a5c --- /dev/null +++ b/src/utils/SkPolyUtils.cpp @@ -0,0 +1,996 @@ +/* + * 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 "SkPolyUtils.h" + +#include "SkPointPriv.h" +#include "SkTArray.h" +#include "SkTemplates.h" +#include "SkTDPQueue.h" +#include "SkTInternalLList.h" + +////////////////////////////////////////////////////////////////////////////////// +// Helper data structures and functions + +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) { + // compute area and use sign to determine winding + SkScalar quadArea = 0; + for (int curr = 0; curr < polygonSize; ++curr) { + int next = (curr + 1) % polygonSize; + quadArea += polygonVerts[curr].cross(polygonVerts[next]); + } + if (SkScalarNearlyZero(quadArea)) { + return 0; + } + // 1 == ccw, -1 == cw + return (quadArea > 0) ? 1 : -1; +} + +// 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& 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 insetDistanceFunc, + SkTDArray* insetPolygon) { + if (inputPolygonSize < 3) { + return false; + } + + // get winding direction + 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 +void SkComputeRadialSteps(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. +bool SkIsSimplePolygon(const SkPoint* polygon, int polygonSize) { + SkTDPQueue 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); +} + +/////////////////////////////////////////////////////////////////////////////////////////// + +bool SkOffsetSimplePolygon(const SkPoint* inputPolygonVerts, int inputPolygonSize, + std::function offsetDistanceFunc, + SkTDArray* offsetPolygon, SkTDArray* polygonIndices) { + if (inputPolygonSize < 3) { + return false; + } + + // get winding direction + int winding = get_winding(inputPolygonVerts, inputPolygonSize); + if (0 == winding) { + return false; + } + + // 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]; + SkComputeRadialSteps(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(); + } + } + + // check winding of offset polygon (it should be same as the original polygon) + SkScalar offsetWinding = get_winding(offsetPolygon->begin(), offsetPolygon->count()); + + return (winding*offsetWinding > 0 && + SkIsSimplePolygon(offsetPolygon->begin(), offsetPolygon->count())); +} + +////////////////////////////////////////////////////////////////////////////////////////// + +struct TriangulationVertex { + SK_DECLARE_INTERNAL_LLIST_INTERFACE(TriangulationVertex); + + enum class VertexType { kConvex, kReflex }; + + SkPoint fPosition; + VertexType fVertexType; + uint16_t fIndex; + uint16_t fPrevIndex; + uint16_t fNextIndex; +}; + +// test to see if point p is in triangle p0p1p2. +// for now assuming strictly inside -- if on the edge it's outside +static bool point_in_triangle(const SkPoint& p0, const SkPoint& p1, const SkPoint& p2, + const SkPoint& p) { + SkVector v0 = p1 - p0; + SkVector v1 = p2 - p1; + SkScalar n = v0.cross(v1); + + SkVector w0 = p - p0; + if (n*v0.cross(w0) < SK_ScalarNearlyZero) { + return false; + } + + SkVector w1 = p - p1; + if (n*v1.cross(w1) < SK_ScalarNearlyZero) { + return false; + } + + SkVector v2 = p0 - p2; + SkVector w2 = p - p2; + if (n*v2.cross(w2) < SK_ScalarNearlyZero) { + return false; + } + + return true; +} + +// Data structure to track reflex vertices and check whether any are inside a given triangle +class ReflexHash { +public: + void add(TriangulationVertex* v) { + fReflexList.addToTail(v); + } + + void remove(TriangulationVertex* v) { + fReflexList.remove(v); + } + + bool checkTriangle(const SkPoint& p0, const SkPoint& p1, const SkPoint& p2) { + for (SkTInternalLList::Iter reflexIter = fReflexList.begin(); + reflexIter != fReflexList.end(); ++reflexIter) { + TriangulationVertex* reflexVertex = *reflexIter; + if (point_in_triangle(p0, p1, p2, reflexVertex->fPosition)) { + return true; + } + } + + return false; + } + +private: + // TODO: switch to an actual spatial hash + SkTInternalLList fReflexList; +}; + +// Check to see if a reflex vertex has become a convex vertex after clipping an ear +static void reclassify_vertex(TriangulationVertex* p, const SkPoint* polygonVerts, + int winding, ReflexHash* reflexHash, + SkTInternalLList* convexList) { + if (TriangulationVertex::VertexType::kReflex == p->fVertexType) { + SkVector v0 = p->fPosition - polygonVerts[p->fPrevIndex]; + SkVector v1 = polygonVerts[p->fNextIndex] - p->fPosition; + if (winding*v0.cross(v1) > SK_ScalarNearlyZero) { + p->fVertexType = TriangulationVertex::VertexType::kConvex; + reflexHash->remove(p); + p->fPrev = p->fNext = nullptr; + convexList->addToTail(p); + } + } +} + +bool SkTriangulateSimplePolygon(const SkPoint* polygonVerts, uint16_t* indexMap, int polygonSize, + SkTDArray* triangleIndices) { + if (polygonSize < 3) { + return false; + } + // need to be able to represent all the vertices in the 16-bit indices + if (polygonSize >= (1 << 16)) { + return false; + } + + // get winding direction + // TODO: we do this for all the polygon routines -- might be better to have the client + // compute it and pass it in + int winding = get_winding(polygonVerts, polygonSize); + if (0 == winding) { + return false; + } + + // Classify initial vertices into a list of convex vertices and a hash of reflex vertices + // TODO: possibly sort the convexList in some way to get better triangles + SkTInternalLList convexList; + ReflexHash reflexHash; + SkAutoSTMalloc<64, TriangulationVertex> triangulationVertices(polygonSize); + int prevIndex = polygonSize - 1; + int currIndex = 0; + int nextIndex = 1; + SkVector v0 = polygonVerts[currIndex] - polygonVerts[prevIndex]; + SkVector v1 = polygonVerts[nextIndex] - polygonVerts[currIndex]; + for (int i = 0; i < polygonSize; ++i) { + SkDEBUGCODE(memset(&triangulationVertices[currIndex], 0, sizeof(TriangulationVertex))); + triangulationVertices[currIndex].fPosition = polygonVerts[currIndex]; + triangulationVertices[currIndex].fIndex = currIndex; + triangulationVertices[currIndex].fPrevIndex = prevIndex; + triangulationVertices[currIndex].fNextIndex = nextIndex; + if (winding*v0.cross(v1) > SK_ScalarNearlyZero) { + triangulationVertices[currIndex].fVertexType = TriangulationVertex::VertexType::kConvex; + convexList.addToTail(&triangulationVertices[currIndex]); + } else { + // We treat near collinear vertices as reflex + triangulationVertices[currIndex].fVertexType = TriangulationVertex::VertexType::kReflex; + reflexHash.add(&triangulationVertices[currIndex]); + } + + prevIndex = currIndex; + currIndex = nextIndex; + nextIndex = (currIndex + 1) % polygonSize; + v0 = v1; + v1 = polygonVerts[nextIndex] - polygonVerts[currIndex]; + } + + // The general concept: We are trying to find three neighboring vertices where + // no other vertex lies inside the triangle (an "ear"). If we find one, we clip + // that ear off, and then repeat on the new polygon. Once we get down to three vertices + // we have triangulated the entire polygon. + // In the worst case this is an n^2 algorithm. We can cut down the search space somewhat by + // noting that only convex vertices can be potential ears, and we only need to check whether + // any reflex vertices lie inside the ear. + triangleIndices->setReserve(triangleIndices->count() + 3 * (polygonSize - 2)); + int vertexCount = polygonSize; + while (vertexCount > 3) { + bool success = false; + TriangulationVertex* earVertex = nullptr; + TriangulationVertex* p0 = nullptr; + TriangulationVertex* p2 = nullptr; + // find a convex vertex to clip + for (SkTInternalLList::Iter convexIter = convexList.begin(); + convexIter != convexList.end(); ++convexIter) { + earVertex = *convexIter; + SkASSERT(TriangulationVertex::VertexType::kReflex != earVertex->fVertexType); + + p0 = &triangulationVertices[earVertex->fPrevIndex]; + p2 = &triangulationVertices[earVertex->fNextIndex]; + + // see if any reflex vertices are inside the ear + bool failed = reflexHash.checkTriangle(p0->fPosition, earVertex->fPosition, + p2->fPosition); + if (failed) { + continue; + } + + // found one we can clip + success = true; + break; + } + // If we can't find any ears to clip, this probably isn't a simple polygon + if (!success) { + return false; + } + + // add indices + auto indices = triangleIndices->append(3); + indices[0] = indexMap[p0->fIndex]; + indices[1] = indexMap[earVertex->fIndex]; + indices[2] = indexMap[p2->fIndex]; + + // clip the ear + convexList.remove(earVertex); + --vertexCount; + + // reclassify reflex verts + p0->fNextIndex = earVertex->fNextIndex; + reclassify_vertex(p0, polygonVerts, winding, &reflexHash, &convexList); + + p2->fPrevIndex = earVertex->fPrevIndex; + reclassify_vertex(p2, polygonVerts, winding, &reflexHash, &convexList); + } + + // output indices + for (SkTInternalLList::Iter vertexIter = convexList.begin(); + vertexIter != convexList.end(); ++vertexIter) { + TriangulationVertex* vertex = *vertexIter; + *triangleIndices->push() = indexMap[vertex->fIndex]; + } + + return true; +} diff --git a/src/utils/SkPolyUtils.h b/src/utils/SkPolyUtils.h new file mode 100755 index 0000000000..ab5ebb8d40 --- /dev/null +++ b/src/utils/SkPolyUtils.h @@ -0,0 +1,143 @@ +/* + * Copyright 2017 Google Inc. + * + * Use of this source code is governed by a BSD-style license that can be + * found in the LICENSE file. + */ + +#ifndef SkOffsetPolygon_DEFINED +#define SkOffsetPolygon_DEFINED + +#include + +#include "SkTDArray.h" +#include "SkPoint.h" + +/** + * 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 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 insetDistanceFunc, + SkTDArray* 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* insetPolygon) { + return SkInsetConvexPolygon(inputPolygonVerts, inputPolygonSize, + [inset](const SkPoint&) { return inset; }, + insetPolygon); +} + +/** + * Generates a simple polygon (if possible) that is offset a variable distance (controlled by + * offsetDistanceFunc) from the boundary of a given simple polygon. + * The input polygon must be simple and have no coincident vertices or collinear edges. + * + * @param inputPolygonVerts Array of points representing the vertices of the original polygon. + * @param inputPolygonSize Number of vertices in the original polygon. + * @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, + std::function offsetDistanceFunc, + SkTDArray* offsetPolygon, + SkTDArray* polygonIndices = nullptr); + +/** + * Generates a simple polygon (if possible) that is offset a constant distance from the boundary + * of a given simple polygon. + * The input polygon must be simple and have no coincident vertices or collinear edges. + * + * @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* offsetPolygon, + SkTDArray* 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 + * + * @param p0 First endpoint. + * @param p1 Second endpoint. + * @param d0 Offset distance from first endpoint. + * @param d1 Offset distance from second endpoint. + * @param side Indicates whether we want to offset to the left (1) or right (-1) side of segment. + * @param offset0 First endpoint of offset segment. + * @param offset1 Second endpoint of offset segment. + * @return true if an offset segment exists, false otherwise. + */ +bool SkOffsetSegment(const SkPoint& p0, const SkPoint& p1, SkScalar d0, SkScalar d1, + int side, SkPoint* offset0, SkPoint* offset1); + +/** + * Compute the number of points needed for a circular join when offsetting a vertex. + * The lengths of offset0 and offset1 don't have to equal r -- only the direction matters. + * The segment lengths will be approximately four pixels. + * + * @param offset0 Starting offset vector direction. + * @param offset1 Ending offset vector direction. + * @param r Length of offset. + * @param rotSin Sine of rotation delta per step. + * @param rotCos Cosine of rotation delta per step. + * @param n Number of steps to fill out the arc. + */ +void SkComputeRadialSteps(const SkVector& offset0, const SkVector& offset1, SkScalar r, + SkScalar* rotSin, SkScalar* rotCos, int* n); + +/** + * Determine whether a polygon is simple (i.e., not self-intersecting) or not. + * + * @param polygonVerts Array of points representing the vertices of the polygon. + * @param polygonSize Number of vertices in the polygon. + * @return true if the polygon is simple, false otherwise. + */ + bool SkIsSimplePolygon(const SkPoint* polygonVerts, int polygonSize); + + /** + * Compute indices to triangulate the given polygon. + * The input polygon must be simple (i.e. it is not self-intersecting) + * and have no coincident vertices or collinear edges. + * + * @param polygonVerts Array of points representing the vertices of the polygon. + * @param indexMap Mapping from index in the given array to the final index in the triangulation. + * @param polygonSize Number of vertices in the polygon. + * @param triangleIndices Indices of the resulting triangulation. + * @return true if successful, false otherwise. + */ + bool SkTriangulateSimplePolygon(const SkPoint* polygonVerts, uint16_t* indexMap, int polygonSize, + SkTDArray* triangleIndices); + +#endif diff --git a/src/utils/SkShadowTessellator.cpp b/src/utils/SkShadowTessellator.cpp index b454e5f103..3d84e8fdad 100755 --- a/src/utils/SkShadowTessellator.cpp +++ b/src/utils/SkShadowTessellator.cpp @@ -9,7 +9,7 @@ #include "SkColorData.h" #include "SkDrawShadowInfo.h" #include "SkGeometry.h" -#include "SkOffsetPolygon.h" +#include "SkPolyUtils.h" #include "SkPath.h" #include "SkPoint3.h" #include "SkPointPriv.h" @@ -127,21 +127,6 @@ static bool compute_normal(const SkPoint& p0, const SkPoint& p1, SkScalar dir, return true; } -static void compute_radial_steps(const SkVector& v1, const SkVector& v2, SkScalar r, - SkScalar* rotSin, SkScalar* rotCos, int* n) { - const SkScalar kRecipPixelsPerArcSegment = 0.125f; - - 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; -} - static bool duplicate_pt(const SkPoint& p0, const SkPoint& p1) { static constexpr SkScalar kClose = (SK_Scalar1 / 16); static constexpr SkScalar kCloseSqd = kClose * kClose; @@ -269,6 +254,9 @@ void SkBaseShadowTessellator::stitchConcaveRings(const SkTDArray& umbra SkTDArray* umbraIndices, const SkTDArray& penumbraPolygon, SkTDArray* penumbraIndices) { + // TODO: only create and fill indexMap when fTransparent is true? + SkAutoSTMalloc<64, uint16_t> indexMap(umbraPolygon.count()); + // find minimum indices int minIndex = 0; int min = (*penumbraIndices)[0]; @@ -311,6 +299,7 @@ void SkBaseShadowTessellator::stitchConcaveRings(const SkTDArray& umbra *fPositions.push() = umbraPolygon[currUmbra]; *fColors.push() = fUmbraColor; fPrevUmbraIndex = 1; + indexMap[currUmbra] = 1; int nextPenumbra = (currPenumbra + 1) % penumbraPolygon.count(); int nextUmbra = (currUmbra + 1) % umbraPolygon.count(); @@ -326,6 +315,7 @@ void SkBaseShadowTessellator::stitchConcaveRings(const SkTDArray& umbra *fPositions.push() = umbraPolygon[nextUmbra]; *fColors.push() = fUmbraColor; int currUmbraIndex = fPositions.count() - 1; + indexMap[nextUmbra] = currUmbraIndex; this->appendQuad(prevPenumbraIndex, currPenumbraIndex, fPrevUmbraIndex, currUmbraIndex); @@ -363,6 +353,7 @@ void SkBaseShadowTessellator::stitchConcaveRings(const SkTDArray& umbra *fPositions.push() = umbraPolygon[nextUmbra]; *fColors.push() = fUmbraColor; int currUmbraIndex = fPositions.count() - 1; + indexMap[nextUmbra] = currUmbraIndex; this->appendTriangle(fPrevUmbraIndex, prevPenumbraIndex, currUmbraIndex); @@ -381,12 +372,14 @@ void SkBaseShadowTessellator::stitchConcaveRings(const SkTDArray& umbra *fPositions.push() = umbraPolygon[nextUmbra]; *fColors.push() = fUmbraColor; int currUmbraIndex = fPositions.count() - 1; + indexMap[nextUmbra] = currUmbraIndex; this->appendQuad(prevPenumbraIndex, currPenumbraIndex, fPrevUmbraIndex, currUmbraIndex); if (fTransparent) { - // TODO: fill penumbra + SkTriangulateSimplePolygon(umbraPolygon.begin(), indexMap, umbraPolygon.count(), + &fIndices); } } @@ -508,7 +501,7 @@ bool SkBaseShadowTessellator::addArc(const SkVector& nextNormal, bool finishArc) // fill in fan from previous quad SkScalar rotSin, rotCos; int numSteps; - compute_radial_steps(fPrevOutset, nextNormal, fRadius, &rotSin, &rotCos, &numSteps); + SkComputeRadialSteps(fPrevOutset, nextNormal, fRadius, &rotSin, &rotCos, &numSteps); SkVector prevNormal = fPrevOutset; for (int i = 0; i < numSteps-1; ++i) { SkVector currNormal; @@ -801,8 +794,7 @@ bool SkAmbientShadowTessellator::computeConvexShadow() { } bool SkAmbientShadowTessellator::computeConcaveShadow() { - // TODO: remove when we support filling the penumbra - if (fTransparent) { + if (!SkIsSimplePolygon(&fPathPolygon[0], fPathPolygon.count())) { return false; } @@ -1418,8 +1410,7 @@ bool SkSpotShadowTessellator::computeConvexShadow(SkScalar radius) { } bool SkSpotShadowTessellator::computeConcaveShadow(SkScalar radius) { - // TODO: remove when we support filling the penumbra - if (fTransparent) { + if (!SkIsSimplePolygon(&fPathPolygon[0], fPathPolygon.count())) { return false; } diff --git a/src/utils/SkShadowUtils.cpp b/src/utils/SkShadowUtils.cpp index b4fba5fcc1..6d5b7e16b4 100644 --- a/src/utils/SkShadowUtils.cpp +++ b/src/utils/SkShadowUtils.cpp @@ -542,9 +542,11 @@ static bool validate_rec(const SkDrawShadowRec& rec) { void SkBaseDevice::drawShadow(const SkPath& path, const SkDrawShadowRec& rec) { auto drawVertsProc = [this](const SkVertices* vertices, SkBlendMode mode, const SkPaint& paint, SkScalar tx, SkScalar ty) { - SkAutoDeviceCTMRestore adr(this, SkMatrix::Concat(this->ctm(), - SkMatrix::MakeTrans(tx, ty))); - this->drawVertices(vertices, mode, paint); + if (vertices->vertexCount()) { + SkAutoDeviceCTMRestore adr(this, SkMatrix::Concat(this->ctm(), + SkMatrix::MakeTrans(tx, ty))); + this->drawVertices(vertices, mode, paint); + } }; if (!validate_rec(rec)) { diff --git a/tests/InsetConvexPolyTest.cpp b/tests/InsetConvexPolyTest.cpp index 433cf239e6..022060c0f4 100644 --- a/tests/InsetConvexPolyTest.cpp +++ b/tests/InsetConvexPolyTest.cpp @@ -5,7 +5,7 @@ * found in the LICENSE file. */ #include "Test.h" -#include "SkOffsetPolygon.h" +#include "SkPolyUtils.h" static bool is_convex(const SkTDArray& poly) { if (poly.count() < 3) { diff --git a/tests/OffsetSimplePolyTest.cpp b/tests/OffsetSimplePolyTest.cpp index de720b5cf2..547dc9e529 100644 --- a/tests/OffsetSimplePolyTest.cpp +++ b/tests/OffsetSimplePolyTest.cpp @@ -5,7 +5,7 @@ * found in the LICENSE file. */ #include "Test.h" -#include "SkOffsetPolygon.h" +#include "SkPolyUtils.h" static bool is_convex(const SkTDArray& poly) { if (poly.count() < 3) { @@ -200,10 +200,7 @@ DEF_TEST(OffsetSimplePoly, reporter) { *intersectingPoly.push() = SkPoint::Make(-43.30f, -25.0f); *intersectingPoly.push() = SkPoint::Make(-14.43f, -25.0f); - result = SkOffsetSimplePolygon(&intersectingPoly[0], intersectingPoly.count(), -100, - &offsetPoly); + // SkOffsetSimplePolygon now assumes that the input is simple, so we'll just check for that + result = SkIsSimplePolygon(&intersectingPoly[0], intersectingPoly.count()); REPORTER_ASSERT(reporter, !result); - - - } -- cgit v1.2.3