diff options
| -rw-r--r-- | bench/PolyUtilsBench.cpp | 102 | ||||
| -rw-r--r-- | src/core/SkTDPQueue.h | 1 | ||||
| -rw-r--r-- | src/utils/SkPolyUtils.cpp | 473 | ||||
| -rw-r--r-- | tests/InsetConvexPolyTest.cpp | 2 |
4 files changed, 349 insertions, 229 deletions
diff --git a/bench/PolyUtilsBench.cpp b/bench/PolyUtilsBench.cpp index 1b987fa038..e03c51cf8d 100644 --- a/bench/PolyUtilsBench.cpp +++ b/bench/PolyUtilsBench.cpp @@ -9,12 +9,12 @@ #include "SkPolyUtils.h" class PolyUtilsBench : public Benchmark { +public: // Evaluate SkTriangulateSimplePolygon's performance (via derived classes) on: // a non-self-intersecting star, a circle of tiny line segments and a self-intersecting star + enum class Type { kConvexCheck, kSimpleCheck, kInsetConvex, kOffsetSimple, kTessellateSimple }; - SkString fName; -public: - PolyUtilsBench() {} + PolyUtilsBench(Type type) : fType(type) {} virtual void appendName(SkString*) = 0; virtual void makePoly(SkTDArray<SkPoint>* poly) = 0; @@ -24,32 +24,84 @@ protected: const char* onGetName() override { fName = "poly_utils_"; this->appendName(&fName); + switch (fType) { + case Type::kConvexCheck: + fName.append("_c"); + break; + case Type::kSimpleCheck: + fName.append("_s"); + break; + case Type::kInsetConvex: + fName.append("_i"); + break; + case Type::kOffsetSimple: + fName.append("_o"); + break; + case Type::kTessellateSimple: + fName.append("_t"); + break; + } return fName.c_str(); } void onDraw(int loops, SkCanvas* canvas) override { SkTDArray<SkPoint> poly; this->makePoly(&poly); - SkAutoSTMalloc<64, uint16_t> indexMap(poly.count()); - for (int i = 0; i < poly.count(); ++i) { - indexMap[i] = i; - } - SkTDArray<uint16_t> triangleIndices; - for (int i = 0; i < loops; i++) { - if (SkIsSimplePolygon(poly.begin(), poly.count())) { - SkTriangulateSimplePolygon(poly.begin(), indexMap, poly.count(), - &triangleIndices); - } + switch (fType) { + case Type::kConvexCheck: + for (int i = 0; i < loops; i++) { + (void)SkIsConvexPolygon(poly.begin(), poly.count()); + } + break; + case Type::kSimpleCheck: + for (int i = 0; i < loops; i++) { + (void)SkIsSimplePolygon(poly.begin(), poly.count()); + } + break; + case Type::kInsetConvex: + if (SkIsConvexPolygon(poly.begin(), poly.count())) { + SkTDArray<SkPoint> result; + for (int i = 0; i < loops; i++) { + (void)SkInsetConvexPolygon(poly.begin(), poly.count(), 10, &result); + (void)SkInsetConvexPolygon(poly.begin(), poly.count(), 40, &result); + } + } + break; + case Type::kOffsetSimple: + if (SkIsSimplePolygon(poly.begin(), poly.count())) { + SkTDArray<SkPoint> result; + for (int i = 0; i < loops; i++) { + (void)SkOffsetSimplePolygon(poly.begin(), poly.count(), 10, &result); + (void)SkOffsetSimplePolygon(poly.begin(), poly.count(), -10, &result); + } + } + break; + case Type::kTessellateSimple: + if (SkIsSimplePolygon(poly.begin(), poly.count())) { + SkAutoSTMalloc<64, uint16_t> indexMap(poly.count()); + for (int i = 0; i < poly.count(); ++i) { + indexMap[i] = i; + } + SkTDArray<uint16_t> triangleIndices; + for (int i = 0; i < loops; i++) { + SkTriangulateSimplePolygon(poly.begin(), indexMap, poly.count(), + &triangleIndices); + } + } + break; } } private: + SkString fName; + Type fType; + typedef Benchmark INHERITED; }; class StarPolyUtilsBench : public PolyUtilsBench { public: - StarPolyUtilsBench() {} + StarPolyUtilsBench(PolyUtilsBench::Type type) : INHERITED(type) {} void appendName(SkString* name) override { name->append("star"); @@ -77,7 +129,7 @@ private: class CirclePolyUtilsBench : public PolyUtilsBench { public: - CirclePolyUtilsBench() {} + CirclePolyUtilsBench(PolyUtilsBench::Type type) : INHERITED(type) {} void appendName(SkString* name) override { name->append("circle"); @@ -101,7 +153,7 @@ private: class IntersectingPolyUtilsBench : public PolyUtilsBench { public: - IntersectingPolyUtilsBench() {} + IntersectingPolyUtilsBench(PolyUtilsBench::Type type) : INHERITED(type) {} void appendName(SkString* name) override { name->append("intersecting"); @@ -125,6 +177,18 @@ private: typedef PolyUtilsBench INHERITED; }; -DEF_BENCH(return new StarPolyUtilsBench();) -DEF_BENCH(return new CirclePolyUtilsBench();) -DEF_BENCH(return new IntersectingPolyUtilsBench();) +DEF_BENCH(return new StarPolyUtilsBench(PolyUtilsBench::Type::kConvexCheck);) +DEF_BENCH(return new StarPolyUtilsBench(PolyUtilsBench::Type::kSimpleCheck);) +DEF_BENCH(return new StarPolyUtilsBench(PolyUtilsBench::Type::kInsetConvex);) +DEF_BENCH(return new StarPolyUtilsBench(PolyUtilsBench::Type::kOffsetSimple);) +DEF_BENCH(return new StarPolyUtilsBench(PolyUtilsBench::Type::kTessellateSimple);) +DEF_BENCH(return new CirclePolyUtilsBench(PolyUtilsBench::Type::kConvexCheck);) +DEF_BENCH(return new CirclePolyUtilsBench(PolyUtilsBench::Type::kSimpleCheck);) +DEF_BENCH(return new CirclePolyUtilsBench(PolyUtilsBench::Type::kInsetConvex);) +DEF_BENCH(return new CirclePolyUtilsBench(PolyUtilsBench::Type::kOffsetSimple);) +DEF_BENCH(return new CirclePolyUtilsBench(PolyUtilsBench::Type::kTessellateSimple);) +DEF_BENCH(return new IntersectingPolyUtilsBench(PolyUtilsBench::Type::kConvexCheck);) +DEF_BENCH(return new IntersectingPolyUtilsBench(PolyUtilsBench::Type::kSimpleCheck);) +DEF_BENCH(return new IntersectingPolyUtilsBench(PolyUtilsBench::Type::kInsetConvex);) +DEF_BENCH(return new IntersectingPolyUtilsBench(PolyUtilsBench::Type::kOffsetSimple);) +DEF_BENCH(return new IntersectingPolyUtilsBench(PolyUtilsBench::Type::kTessellateSimple);) diff --git a/src/core/SkTDPQueue.h b/src/core/SkTDPQueue.h index 5dca4910ed..6e2a09ca8a 100644 --- a/src/core/SkTDPQueue.h +++ b/src/core/SkTDPQueue.h @@ -30,6 +30,7 @@ template <typename T, class SkTDPQueue { public: SkTDPQueue() {} + SkTDPQueue(int reserve) { fArray.setReserve(reserve); } SkTDPQueue(SkTDPQueue&&) = default; SkTDPQueue& operator =(SkTDPQueue&&) = default; diff --git a/src/utils/SkPolyUtils.cpp b/src/utils/SkPolyUtils.cpp index b76d270d15..0d1b71c76b 100644 --- a/src/utils/SkPolyUtils.cpp +++ b/src/utils/SkPolyUtils.cpp @@ -7,6 +7,7 @@ #include "SkPolyUtils.h" +#include <set> #include "SkPointPriv.h" #include "SkTArray.h" #include "SkTemplates.h" @@ -298,34 +299,32 @@ bool SkIsConvexPolygon(const SkPoint* polygonVerts, int polygonSize) { return true; } -struct EdgeData { +struct OffsetEdge { + OffsetEdge* fPrev; + OffsetEdge* fNext; OffsetSegment fInset; SkPoint fIntersection; SkScalar fTValue; - uint16_t fStart; uint16_t fEnd; uint16_t fIndex; - bool fValid; - void init() { + void init(uint16_t start = 0, uint16_t end = 0) { 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; } }; +static void remove_node(const OffsetEdge* node, OffsetEdge** head) { + // remove from linked list + node->fPrev->fNext = node->fNext; + node->fNext->fPrev = node->fPrev; + if (node == *head) { + *head = (node->fNext == node) ? nullptr : node->fNext; + } +} + ////////////////////////////////////////////////////////////////////////////////// // The objective here is to inset all of the edges by the given distance, and then @@ -354,115 +353,117 @@ bool SkInsetConvexPolygon(const SkPoint* inputPolygonVerts, int inputPolygonSize } // set up - SkAutoSTMalloc<64, EdgeData> edgeData(inputPolygonSize); - for (int i = 0; i < inputPolygonSize; ++i) { - int j = (i + 1) % inputPolygonSize; - int k = (i + 2) % inputPolygonSize; - if (!inputPolygonVerts[i].isFinite()) { + SkAutoSTMalloc<64, OffsetEdge> edgeData(inputPolygonSize); + int prev = inputPolygonSize - 1; + for (int curr = 0; curr < inputPolygonSize; prev = curr, ++curr) { + int next = (curr + 1) % inputPolygonSize; + if (!inputPolygonVerts[curr].isFinite()) { return false; } // check for convexity just to be sure - if (compute_side(inputPolygonVerts[i], inputPolygonVerts[j], - inputPolygonVerts[k])*winding < 0) { + if (compute_side(inputPolygonVerts[prev], inputPolygonVerts[curr], + inputPolygonVerts[next])*winding < 0) { return false; } - if (!SkOffsetSegment(inputPolygonVerts[i], inputPolygonVerts[j], - insetDistanceFunc(inputPolygonVerts[i]), - insetDistanceFunc(inputPolygonVerts[j]), + edgeData[curr].fPrev = &edgeData[prev]; + edgeData[curr].fNext = &edgeData[next]; + if (!SkOffsetSegment(inputPolygonVerts[curr], inputPolygonVerts[next], + insetDistanceFunc(inputPolygonVerts[curr]), + insetDistanceFunc(inputPolygonVerts[next]), winding, - &edgeData[i].fInset.fP0, &edgeData[i].fInset.fP1)) { + &edgeData[curr].fInset.fP0, &edgeData[curr].fInset.fP1)) { return false; } - edgeData[i].init(); + edgeData[curr].init(); } - int prevIndex = inputPolygonSize - 1; - int currIndex = 0; + OffsetEdge* head = &edgeData[0]; + OffsetEdge* currEdge = head; + OffsetEdge* prevEdge = currEdge->fPrev; int insetVertexCount = inputPolygonSize; int iterations = 0; - while (prevIndex != currIndex) { + while (head && prevEdge != currEdge) { ++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, + if (compute_intersection(prevEdge->fInset, currEdge->fInset, &intersection, &s, &t)) { // if new intersection is further back on previous inset from the prior intersection - if (s < edgeData[prevIndex].fTValue) { + if (s < prevEdge->fTValue) { // no point in considering this one again - edgeData[prevIndex].fValid = false; + remove_node(prevEdge, &head); --insetVertexCount; // go back one segment - prevIndex = (prevIndex + inputPolygonSize - 1) % inputPolygonSize; + prevEdge = prevEdge->fPrev; // we've already considered this intersection, we're done - } else if (edgeData[currIndex].fTValue > SK_ScalarMin && + } else if (currEdge->fTValue > SK_ScalarMin && SkPointPriv::EqualsWithinTolerance(intersection, - edgeData[currIndex].fIntersection, + currEdge->fIntersection, 1.0e-6f)) { break; } else { // add intersection - edgeData[currIndex].fIntersection = intersection; - edgeData[currIndex].fTValue = t; + currEdge->fIntersection = intersection; + currEdge->fTValue = t; // go to next segment - prevIndex = currIndex; - currIndex = (currIndex + 1) % inputPolygonSize; + prevEdge = currEdge; + currEdge = currEdge->fNext; } } 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)) { + int side = winding*compute_side(currEdge->fInset.fP0, + currEdge->fInset.fP1, + prevEdge->fInset.fP1); + if (side < 0 && side == winding*compute_side(currEdge->fInset.fP0, + currEdge->fInset.fP1, + prevEdge->fInset.fP0)) { // no point in considering this one again - edgeData[prevIndex].fValid = false; + remove_node(prevEdge, &head); --insetVertexCount; // go back one segment - prevIndex = (prevIndex + inputPolygonSize - 1) % inputPolygonSize; + prevEdge = prevEdge->fPrev; } else { // move to next segment - edgeData[currIndex].fValid = false; + remove_node(currEdge, &head); --insetVertexCount; - currIndex = (currIndex + 1) % inputPolygonSize; + currEdge = currEdge->fNext; } } } // 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++; + if (head) { + static constexpr SkScalar kCleanupTolerance = 0.01f; + if (insetVertexCount >= 0) { + insetPolygon->setReserve(insetVertexCount); + } + int currIndex = 0; + OffsetEdge* currEdge = head; + *insetPolygon->push() = currEdge->fIntersection; + currEdge = currEdge->fNext; + while (currEdge != head) { + if (!SkPointPriv::EqualsWithinTolerance(currEdge->fIntersection, + (*insetPolygon)[currIndex], + kCleanupTolerance)) { + *insetPolygon->push() = currEdge->fIntersection; + currIndex++; + } + currEdge = currEdge->fNext; + } + // make sure the first and last points aren't coincident + if (currIndex >= 1 && + SkPointPriv::EqualsWithinTolerance((*insetPolygon)[0], (*insetPolygon)[currIndex], + kCleanupTolerance)) { + insetPolygon->pop(); } - } - // make sure the first and last points aren't coincident - if (currIndex >= 1 && - SkPointPriv::EqualsWithinTolerance((*insetPolygon)[0], (*insetPolygon)[currIndex], - kCleanupTolerance)) { - insetPolygon->pop(); } return SkIsConvexPolygon(insetPolygon->begin(), insetPolygon->count()); @@ -504,6 +505,7 @@ 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 @@ -517,30 +519,60 @@ enum VertexFlags { kNextLeft_VertexFlag = 0x2, }; -struct Edge { +struct ActiveEdge { + ActiveEdge(const SkPoint& p0, const SkPoint& p1, int32_t index0, int32_t index1) + : fSegment({p0, p1}) + , fIndex0(index0) + , fIndex1(index1) {} + // returns true if "this" is above "that" - bool above(const Edge& that, SkScalar tolerance = SK_ScalarNearlyZero) { - SkASSERT(this->fSegment.fP0.fX < that.fSegment.fP0.fX || - SkScalarNearlyEqual(this->fSegment.fP0.fX, that.fSegment.fP0.fX, tolerance)); + bool above(const ActiveEdge& that) const { + SkASSERT(this->fSegment.fP0.fX <= that.fSegment.fP0.fX); + const SkScalar kTolerance = SK_ScalarNearlyZero * SK_ScalarNearlyZero; + SkVector u = this->fSegment.fP1 - this->fSegment.fP0; // 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) { + if (this->fIndex0 != that.fIndex0) { + SkVector dv = that.fSegment.fP0 - this->fSegment.fP0; + SkScalar cross = dv.cross(u); + if (cross > kTolerance) { + return true; + } else if (cross < -kTolerance) { + return false; + } + } else if (this->fIndex1 == that.fIndex1) { + // they're the same edge return false; } - // If the result is 0 then either the two origins are equal or the origin of "that" + // At this point either the two origins are nearly 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); + SkVector dv = that.fSegment.fP1 - this->fSegment.fP0; + SkScalar cross = dv.cross(u); + if (cross > kTolerance) { + return true; + } else if (cross < -kTolerance) { + return false; + } + // If the previous check fails, the two segments are nearly collinear + // First check y-coord of first endpoints + if (this->fSegment.fP0.fX < that.fSegment.fP0.fX) { + return (this->fSegment.fP0.fY >= that.fSegment.fP0.fY); + } else if (this->fSegment.fP0.fY > that.fSegment.fP0.fY) { + return true; + } else if (this->fSegment.fP0.fY < that.fSegment.fP0.fY) { + return false; + } + // The first endpoints are the same, so check the other endpoint + if (this->fSegment.fP1.fX < that.fSegment.fP1.fX) { + return (this->fSegment.fP1.fY >= that.fSegment.fP1.fY); + } else { + return (this->fSegment.fP1.fY > that.fSegment.fP1.fY); + } } - bool intersect(const Edge& that) const { + bool intersect(const ActiveEdge& that) const { SkPoint intersection; SkScalar s, t; // check first to see if these edges are neighbors in the polygon @@ -551,78 +583,78 @@ struct Edge { return compute_intersection(this->fSegment, that.fSegment, &intersection, &s, &t); } - bool operator==(const Edge& that) const { + bool operator==(const ActiveEdge& that) const { return (this->fIndex0 == that.fIndex0 && this->fIndex1 == that.fIndex1); } - bool operator!=(const Edge& that) const { + bool operator!=(const ActiveEdge& that) const { return !operator==(that); } + bool lessThan(const ActiveEdge& that) const { + if (this->fSegment.fP0.fX > that.fSegment.fP0.fX || + (this->fSegment.fP0.fX == that.fSegment.fP0.fX && + this->fSegment.fP0.fY < that.fSegment.fP0.fY)) { + return !that.above(*this); + } + return this->above(that); + } + + bool operator<(const ActiveEdge& that) const { + SkASSERT(!this->lessThan(*this)); + SkASSERT(!that.lessThan(that)); + SkASSERT(!(this->lessThan(that) && that.lessThan(*this))); + return this->lessThan(that); + } + OffsetSegment fSegment; int32_t fIndex0; // indices for previous and next vertex int32_t fIndex1; }; -class EdgeList { +class ActiveEdgeList { public: - void reserve(int count) { fEdges.reserve(count); } + void reserve(int 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])) { + bool insert(const SkPoint& p0, const SkPoint& p1, int32_t index0, int32_t index1) { + std::pair<Iterator, bool> result = fEdgeTree.emplace(p0, p1, index0, index1); + if (!result.second) { return false; } - if (insertIndex < fEdges.count() && newEdge.intersect(fEdges[insertIndex])) { + + Iterator& curr = result.first; + if (curr != fEdgeTree.begin() && curr->intersect(*std::prev(curr))) { return false; } - - fEdges.push_back(); - for (int i = fEdges.count() - 1; i > insertIndex; --i) { - fEdges[i] = fEdges[i - 1]; + Iterator next = std::next(curr); + if (next != fEdgeTree.end() && curr->intersect(*next)) { + return false; } - 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; + bool remove(const ActiveEdge& edge) { + auto element = fEdgeTree.find(edge); + // this better not happen + if (element == fEdgeTree.end()) { + return false; } - // 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])) { + if (element != fEdgeTree.begin() && element->intersect(*std::prev(element))) { 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)); + Iterator next = std::next(element); + if (next != fEdgeTree.end() && element->intersect(*next)) { + return false; } - fEdges.pop_back(); + fEdgeTree.erase(element); return true; } private: - SkSTArray<1, Edge> fEdges; + std::set<ActiveEdge> fEdgeTree; + typedef std::set<ActiveEdge>::iterator Iterator; }; // Here we implement a sweep line algorithm to determine whether the provided points @@ -636,10 +668,7 @@ bool SkIsSimplePolygon(const SkPoint* polygon, int polygonSize) { return false; } - SkTDPQueue <Vertex, Vertex::Left> vertexQueue; - EdgeList sweepLine; - - sweepLine.reserve(polygonSize); + SkTDPQueue <Vertex, Vertex::Left> vertexQueue(polygonSize); for (int i = 0; i < polygonSize; ++i) { Vertex newVertex; if (!polygon[i].isFinite()) { @@ -661,31 +690,31 @@ bool SkIsSimplePolygon(const SkPoint* polygon, int polygonSize) { // pop each vertex from the queue and generate events depending on // where it lies relative to its neighboring edges + ActiveEdgeList sweepLine; + sweepLine.reserve(polygonSize); 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 }; + ActiveEdge 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)) { + if (!sweepLine.insert(v.fPosition, polygon[v.fPrevIndex], v.fIndex, v.fPrevIndex)) { break; } } // check edge to next vertex if (v.fFlags & kNextLeft_VertexFlag) { - Edge edge{ { polygon[v.fNextIndex], v.fPosition }, v.fNextIndex, v.fIndex }; + ActiveEdge 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)) { + if (!sweepLine.insert(v.fPosition, polygon[v.fNextIndex], v.fIndex, v.fNextIndex)) { break; } } @@ -698,6 +727,15 @@ bool SkIsSimplePolygon(const SkPoint* polygon, int polygonSize) { /////////////////////////////////////////////////////////////////////////////////////////// +// helper function for SkOffsetSimplePolygon +static void setup_offset_edge(OffsetEdge* currEdge, + const SkPoint& endpoint0, const SkPoint& endpoint1, + int startIndex, int endIndex) { + currEdge->fInset.fP0 = endpoint0; + currEdge->fInset.fP1 = endpoint1; + currEdge->init(startIndex, endIndex); +} + bool SkOffsetSimplePolygon(const SkPoint* inputPolygonVerts, int inputPolygonSize, std::function<SkScalar(const SkPoint&)> offsetDistanceFunc, SkTDArray<SkPoint>* offsetPolygon, SkTDArray<int>* polygonIndices) { @@ -736,7 +774,7 @@ bool SkOffsetSimplePolygon(const SkPoint* inputPolygonVerts, int inputPolygonSiz } // build initial offset edge list - SkSTArray<64, EdgeData> edgeData(inputPolygonSize); + SkSTArray<64, OffsetEdge> edgeData(inputPolygonSize); int prevIndex = inputPolygonSize - 1; int currIndex = 0; int nextIndex = 1; @@ -754,126 +792,143 @@ bool SkOffsetSimplePolygon(const SkPoint* inputPolygonVerts, int inputPolygonSiz &rotSin, &rotCos, &numSteps)) { return false; } + auto currEdge = edgeData.push_back_n(SkTMax(numSteps, 1)); 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); + setup_offset_edge(currEdge, + inputPolygonVerts[currIndex] + prevNormal, + inputPolygonVerts[currIndex] + currNormal, + currIndex, currIndex); prevNormal = currNormal; + ++currEdge; } - EdgeData& edge = edgeData.push_back(); - edge.fInset.fP0 = inputPolygonVerts[currIndex] + prevNormal; - edge.fInset.fP1 = inputPolygonVerts[currIndex] + normal0[currIndex]; - edge.init(currIndex, currIndex); + setup_offset_edge(currEdge, + inputPolygonVerts[currIndex] + prevNormal, + inputPolygonVerts[currIndex] + normal0[currIndex], + currIndex, currIndex); + ++currEdge; + } // 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); + auto edge = edgeData.push_back_n(1); + setup_offset_edge(edge, + inputPolygonVerts[currIndex] + normal0[currIndex], + inputPolygonVerts[nextIndex] + normal1[nextIndex], + currIndex, nextIndex); prevIndex = currIndex; currIndex++; nextIndex = (nextIndex + 1) % inputPolygonSize; } + // build linked list + // we have to do this as a post-process step because we might have reallocated + // the array when adding fans for reflex verts + prevIndex = edgeData.count()-1; + for (int currIndex = 0; currIndex < edgeData.count(); prevIndex = currIndex, ++currIndex) { + int nextIndex = (currIndex + 1) % edgeData.count(); + edgeData[currIndex].fPrev = &edgeData[prevIndex]; + edgeData[currIndex].fNext = &edgeData[nextIndex]; + } + + // now clip edges int edgeDataSize = edgeData.count(); - prevIndex = edgeDataSize - 1; - currIndex = 0; - int insetVertexCount = edgeDataSize; + auto head = &edgeData[0]; + auto currEdge = head; + auto prevEdge = currEdge->fPrev; + int offsetVertexCount = edgeDataSize; int iterations = 0; - while (prevIndex != currIndex) { + while (head && prevEdge != currEdge) { ++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, + if (compute_intersection(prevEdge->fInset, currEdge->fInset, &intersection, &s, &t)) { // if new intersection is further back on previous inset from the prior intersection - if (s < edgeData[prevIndex].fTValue) { + if (s < prevEdge->fTValue) { // no point in considering this one again - edgeData[prevIndex].fValid = false; - --insetVertexCount; + remove_node(prevEdge, &head); + --offsetVertexCount; // go back one segment - prevIndex = (prevIndex + edgeDataSize - 1) % edgeDataSize; + prevEdge = prevEdge->fPrev; // we've already considered this intersection, we're done - } else if (edgeData[currIndex].fTValue > SK_ScalarMin && + } else if (currEdge->fTValue > SK_ScalarMin && SkPointPriv::EqualsWithinTolerance(intersection, - edgeData[currIndex].fIntersection, + currEdge->fIntersection, 1.0e-6f)) { break; } else { // add intersection - edgeData[currIndex].fIntersection = intersection; - edgeData[currIndex].fTValue = t; - edgeData[currIndex].fIndex = edgeData[prevIndex].fEnd; + currEdge->fIntersection = intersection; + currEdge->fTValue = t; + currEdge->fIndex = prevEdge->fEnd; // go to next segment - prevIndex = currIndex; - currIndex = (currIndex + 1) % edgeDataSize; + prevEdge = currEdge; + currEdge = currEdge->fNext; } } 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); + OffsetEdge* prevPrevEdge = prevEdge->fPrev; + OffsetEdge* currNextEdge = currEdge->fNext; + SkScalar dist0 = compute_crossing_distance(currEdge->fInset, + prevPrevEdge->fInset); + SkScalar dist1 = compute_crossing_distance(prevEdge->fInset, + currNextEdge->fInset); if (dist0 < dist1) { - edgeData[prevIndex].fValid = false; - prevIndex = prevPrevIndex; + remove_node(prevEdge, &head); + prevEdge = prevPrevEdge; } else { - edgeData[currIndex].fValid = false; - currIndex = currNextIndex; + remove_node(currEdge, &head); + currEdge = currNextEdge; } - --insetVertexCount; + --offsetVertexCount; } } // 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++; + if (head) { + static constexpr SkScalar kCleanupTolerance = 0.01f; + if (offsetVertexCount >= 0) { + offsetPolygon->setReserve(offsetVertexCount); } - } - // make sure the first and last points aren't coincident - if (currIndex >= 1 && - SkPointPriv::EqualsWithinTolerance((*offsetPolygon)[0], (*offsetPolygon)[currIndex], - kCleanupTolerance)) { - offsetPolygon->pop(); + int currIndex = 0; + OffsetEdge* currEdge = head; + *offsetPolygon->push() = currEdge->fIntersection; if (polygonIndices) { - polygonIndices->pop(); + *polygonIndices->push() = currEdge->fIndex; + } + currEdge = currEdge->fNext; + while (currEdge != head) { + if (!SkPointPriv::EqualsWithinTolerance(currEdge->fIntersection, + (*offsetPolygon)[currIndex], + kCleanupTolerance)) { + *offsetPolygon->push() = currEdge->fIntersection; + if (polygonIndices) { + *polygonIndices->push() = currEdge->fIndex; + } + currIndex++; + } + currEdge = currEdge->fNext; + } + // 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(); + } } } diff --git a/tests/InsetConvexPolyTest.cpp b/tests/InsetConvexPolyTest.cpp index facabb76fa..aaaf591620 100644 --- a/tests/InsetConvexPolyTest.cpp +++ b/tests/InsetConvexPolyTest.cpp @@ -65,7 +65,7 @@ DEF_TEST(InsetConvexPoly, reporter) { // past full inset result = SkInsetConvexPolygon(rrectPoly.begin(), rrectPoly.count(), 75, &insetPoly); REPORTER_ASSERT(reporter, !result); - REPORTER_ASSERT(reporter, insetPoly.count() == 0); + REPORTER_ASSERT(reporter, insetPoly.count() == 1); // troublesome case SkTDArray<SkPoint> clippedRRectPoly; |