| /* |
| * Copyright 2020 Google Inc. |
| * |
| * Use of this source code is governed by a BSD-style license that can be |
| * found in the LICENSE file. |
| */ |
| |
| #ifndef skgpu_tessellate_MiddleOutPolygonTriangulator_DEFINED |
| #define skgpu_tessellate_MiddleOutPolygonTriangulator_DEFINED |
| |
| #include "include/core/SkPath.h" |
| #include "include/core/SkPathTypes.h" |
| #include "include/core/SkPoint.h" |
| #include "include/private/base/SkAssert.h" |
| #include "include/private/base/SkDebug.h" |
| #include "include/private/base/SkTemplates.h" |
| #include "src/base/SkMathPriv.h" |
| #include "src/core/SkPathPriv.h" |
| |
| #include <algorithm> |
| #include <cstring> |
| #include <tuple> |
| |
| namespace skgpu::tess { |
| |
| // This class generates a middle-out triangulation of a polygon. Conceptually, middle-out emits one |
| // large triangle with vertices on both endpoints and a middle point, then recurses on both sides of |
| // the new triangle. i.e.: |
| // |
| // void emit_middle_out_triangulation(int startIdx, int endIdx) { |
| // if (startIdx + 1 == endIdx) { |
| // return; |
| // } |
| // int middleIdx = startIdx + SkNextPow2(endIdx - startIdx) / 2; |
| // |
| // // Recurse on the left half. |
| // emit_middle_out_triangulation(startIdx, middleIdx); |
| // |
| // // Emit a large triangle with vertices on both endpoints and a middle point. |
| // emit_triangle(vertices[startIdx], vertices[middleIdx], vertices[endIdx - 1]); |
| // |
| // // Recurse on the right half. |
| // emit_middle_out_triangulation(middleIdx, endIdx); |
| // } |
| // |
| // Middle-out produces drastically less work for the rasterizer as compared a linear triangle strip |
| // or fan. |
| // |
| // This class is designed to not know or store all the vertices in the polygon at once. The caller |
| // pushes each vertex in linear order (perhaps while parsing a path), then rather than relying on |
| // recursion, we manipulate an O(log N) stack to determine the correct middle-out triangulation. |
| class MiddleOutPolygonTriangulator { |
| private: |
| // Internal representation of how we store vertices on our stack. |
| struct StackVertex { |
| SkPoint fPoint; |
| // How many polygon vertices away is this vertex from the previous vertex on the stack? |
| // i.e., the ith stack element's vertex index in the original polygon is: |
| // |
| // fVertexStack[i].fVertexIdxDelta + fVertexStack[i - 1].fVertexIdxDelta + ... + |
| // fVertexStack[1].fVertexIdxDelta. |
| // |
| // NOTE: fVertexStack[0].fVertexIdxDelta always == 0. |
| int fVertexIdxDelta; |
| }; |
| |
| public: |
| // RAII. This class is designed to first allow the caller to iterate the triangles that will be |
| // popped off our stack, and then (during the destructor) it actually pops the finished vertices |
| // and pushes a new one. Example usage: |
| // |
| // for (auto [p0, p1, p2] : middleOut.pushVertex(pt)) { |
| // vertexWriter << p0 << p1 << p2; |
| // } |
| // |
| // The above code iterates over the triangles being popped, and then once iteration is finished, |
| // the PoppedTriangleStack is destroyed, triggering the pending stack update. |
| class PoppedTriangleStack { |
| public: |
| PoppedTriangleStack(MiddleOutPolygonTriangulator* middleOut, |
| SkPoint lastPoint, |
| StackVertex* end, |
| StackVertex* newTopVertex, |
| StackVertex newTopValue) |
| : fMiddleOut(middleOut) |
| , fLastPoint(lastPoint) |
| , fEnd(end) |
| , fNewTopVertex(newTopVertex) |
| , fNewTopValue(newTopValue) { |
| } |
| |
| PoppedTriangleStack(PoppedTriangleStack&& that) { |
| memcpy(this, &that, sizeof(*this)); |
| that.fMiddleOut = nullptr; // Don't do a stack update during our destructor. |
| } |
| |
| ~PoppedTriangleStack() { |
| if (fMiddleOut) { |
| fMiddleOut->fTop = fNewTopVertex; |
| *fNewTopVertex = fNewTopValue; |
| } |
| } |
| |
| struct Iter { |
| bool operator!=(const Iter& iter) { return fVertex != iter.fVertex; } |
| void operator++() { --fVertex; } |
| std::tuple<SkPoint, SkPoint, SkPoint> operator*() { |
| return {fVertex[-1].fPoint, fVertex[0].fPoint, fLastPoint}; |
| } |
| StackVertex* fVertex; |
| SkPoint fLastPoint; |
| }; |
| |
| Iter begin() const { return {fMiddleOut ? fMiddleOut->fTop : fEnd, fLastPoint}; } |
| Iter end() const { return {fEnd, fLastPoint}; } |
| |
| private: |
| MiddleOutPolygonTriangulator* fMiddleOut; |
| SkPoint fLastPoint; |
| StackVertex* fEnd; |
| StackVertex* fNewTopVertex; |
| StackVertex fNewTopValue; |
| }; |
| |
| // maxPushVertexCalls is an upper bound on the number of times the caller will call |
| // pushVertex(). The caller must not call it more times than this. (Beware of int overflow.) |
| MiddleOutPolygonTriangulator(int maxPushVertexCalls, SkPoint startPoint = {0,0}) { |
| SkASSERT(maxPushVertexCalls >= 0); |
| // Determine the deepest our stack can ever go. |
| int maxStackDepth = SkNextLog2(maxPushVertexCalls) + 1; |
| if (maxStackDepth > kStackPreallocCount) { |
| fVertexStack.reset(maxStackDepth); |
| } |
| SkDEBUGCODE(fStackAllocCount = maxStackDepth;) |
| // The stack will always contain a starting point. This is an implicit moveTo(0, 0) |
| // initially, but will be overridden if moveTo() gets called before adding geometry. |
| fVertexStack[0] = {startPoint, 0}; |
| fTop = fVertexStack; |
| } |
| |
| // Returns an RAII object that first allows the caller to iterate the triangles we will pop, |
| // pops those triangles, and finally pushes 'pt' onto the vertex stack. |
| [[nodiscard]] PoppedTriangleStack pushVertex(SkPoint pt) { |
| // Our topology wants triangles that have the same vertexIdxDelta on both sides: |
| // e.g., a run of 9 points should be triangulated as: |
| // |
| // [0, 1, 2], [2, 3, 4], [4, 5, 6], [6, 7, 8] // vertexIdxDelta == 1 |
| // [0, 2, 4], [4, 6, 8] // vertexIdxDelta == 2 |
| // [0, 4, 8] // vertexIdxDelta == 4 |
| // |
| // Find as many new triangles as we can pop off the stack that have equal-delta sides. (This |
| // is a stack-based implementation of the recursive example method from the class comment.) |
| StackVertex* endVertex = fTop; |
| int vertexIdxDelta = 1; |
| while (endVertex->fVertexIdxDelta == vertexIdxDelta) { |
| --endVertex; |
| vertexIdxDelta *= 2; |
| } |
| |
| // Once the above triangles are popped, push 'pt' to the top of the stack. |
| StackVertex* newTopVertex = endVertex + 1; |
| StackVertex newTopValue = {pt, vertexIdxDelta}; |
| SkASSERT(newTopVertex < fVertexStack + fStackAllocCount); // Is fStackAllocCount enough? |
| |
| return PoppedTriangleStack(this, pt, endVertex, newTopVertex, newTopValue); |
| } |
| |
| // Returns an RAII object that first allows the caller to iterate the remaining triangles, then |
| // resets the vertex stack with newStartPoint. |
| [[nodiscard]] PoppedTriangleStack closeAndMove(SkPoint newStartPoint) { |
| // Add an implicit line back to the starting point. |
| SkPoint startPt = fVertexStack[0].fPoint; |
| |
| // Triangulate the rest of the polygon. Since we simply have to finish now, we can't be |
| // picky anymore about getting a pure middle-out topology. |
| StackVertex* endVertex = std::min(fTop, fVertexStack + 1); |
| |
| // Once every remaining triangle is popped, reset the vertex stack with newStartPoint. |
| StackVertex* newTopVertex = fVertexStack; |
| StackVertex newTopValue = {newStartPoint, 0}; |
| |
| return PoppedTriangleStack(this, startPt, endVertex, newTopVertex, newTopValue); |
| } |
| |
| // Returns an RAII object that first allows the caller to iterate the remaining triangles, then |
| // resets the vertex stack with the same starting point as it had before. |
| [[nodiscard]] PoppedTriangleStack close() { |
| return this->closeAndMove(fVertexStack[0].fPoint); |
| } |
| |
| private: |
| constexpr static int kStackPreallocCount = 32; |
| skia_private::AutoSTMalloc<kStackPreallocCount, StackVertex> fVertexStack; |
| SkDEBUGCODE(int fStackAllocCount;) |
| StackVertex* fTop; |
| }; |
| |
| // This is a helper class that transforms and pushes a path's inner fan vertices onto a |
| // MiddleOutPolygonTriangulator. Example usage: |
| // |
| // for (PathMiddleOutFanIter it(pathMatrix, path); !it.done();) { |
| // for (auto [p0, p1, p2] : it.nextStack()) { |
| // vertexWriter << p0 << p1 << p2; |
| // } |
| // } |
| // |
| class PathMiddleOutFanIter { |
| public: |
| PathMiddleOutFanIter(const SkPath& path) : fMiddleOut(path.countVerbs()) { |
| SkPathPriv::Iterate it(path); |
| fPathIter = it.begin(); |
| fPathEnd = it.end(); |
| } |
| |
| bool done() const { return fDone; } |
| |
| MiddleOutPolygonTriangulator::PoppedTriangleStack nextStack() { |
| SkASSERT(!fDone); |
| if (fPathIter == fPathEnd) { |
| fDone = true; |
| return fMiddleOut.close(); |
| } |
| switch (auto [verb, pts, w] = *fPathIter++; verb) { |
| SkPoint pt; |
| case SkPathVerb::kMove: |
| return fMiddleOut.closeAndMove(pts[0]); |
| case SkPathVerb::kLine: |
| case SkPathVerb::kQuad: |
| case SkPathVerb::kConic: |
| case SkPathVerb::kCubic: |
| pt = pts[SkPathPriv::PtsInIter((unsigned)verb) - 1]; |
| return fMiddleOut.pushVertex(pt); |
| case SkPathVerb::kClose: |
| return fMiddleOut.close(); |
| } |
| SkUNREACHABLE; |
| } |
| |
| private: |
| MiddleOutPolygonTriangulator fMiddleOut; |
| SkPathPriv::RangeIter fPathIter; |
| SkPathPriv::RangeIter fPathEnd; |
| bool fDone = false; |
| }; |
| |
| } // namespace skgpu::tess |
| |
| #endif // skgpu_tessellate_MiddleOutPolygonTriangulator_DEFINED |