1 /* 2 * Copyright 2020 Google Inc. 3 * 4 * Use of this source code is governed by a BSD-style license that can be 5 * found in the LICENSE file. 6 */ 7 8 #ifndef skgpu_tessellate_MiddleOutPolygonTriangulator_DEFINED 9 #define skgpu_tessellate_MiddleOutPolygonTriangulator_DEFINED 10 11 #include "include/core/SkPath.h" 12 #include "include/core/SkPathTypes.h" 13 #include "include/core/SkPoint.h" 14 #include "include/private/base/SkAssert.h" 15 #include "include/private/base/SkDebug.h" 16 #include "include/private/base/SkTemplates.h" 17 #include "src/base/SkMathPriv.h" 18 #include "src/core/SkPathPriv.h" 19 20 #include <algorithm> 21 #include <cstring> 22 #include <tuple> 23 24 namespace skgpu::tess { 25 26 // This class generates a middle-out triangulation of a polygon. Conceptually, middle-out emits one 27 // large triangle with vertices on both endpoints and a middle point, then recurses on both sides of 28 // the new triangle. i.e.: 29 // 30 // void emit_middle_out_triangulation(int startIdx, int endIdx) { 31 // if (startIdx + 1 == endIdx) { 32 // return; 33 // } 34 // int middleIdx = startIdx + SkNextPow2(endIdx - startIdx) / 2; 35 // 36 // // Recurse on the left half. 37 // emit_middle_out_triangulation(startIdx, middleIdx); 38 // 39 // // Emit a large triangle with vertices on both endpoints and a middle point. 40 // emit_triangle(vertices[startIdx], vertices[middleIdx], vertices[endIdx - 1]); 41 // 42 // // Recurse on the right half. 43 // emit_middle_out_triangulation(middleIdx, endIdx); 44 // } 45 // 46 // Middle-out produces drastically less work for the rasterizer as compared a linear triangle strip 47 // or fan. 48 // 49 // This class is designed to not know or store all the vertices in the polygon at once. The caller 50 // pushes each vertex in linear order (perhaps while parsing a path), then rather than relying on 51 // recursion, we manipulate an O(log N) stack to determine the correct middle-out triangulation. 52 class MiddleOutPolygonTriangulator { 53 private: 54 // Internal representation of how we store vertices on our stack. 55 struct StackVertex { 56 SkPoint fPoint; 57 // How many polygon vertices away is this vertex from the previous vertex on the stack? 58 // i.e., the ith stack element's vertex index in the original polygon is: 59 // 60 // fVertexStack[i].fVertexIdxDelta + fVertexStack[i - 1].fVertexIdxDelta + ... + 61 // fVertexStack[1].fVertexIdxDelta. 62 // 63 // NOTE: fVertexStack[0].fVertexIdxDelta always == 0. 64 int fVertexIdxDelta; 65 }; 66 67 public: 68 // RAII. This class is designed to first allow the caller to iterate the triangles that will be 69 // popped off our stack, and then (during the destructor) it actually pops the finished vertices 70 // and pushes a new one. Example usage: 71 // 72 // for (auto [p0, p1, p2] : middleOut.pushVertex(pt)) { 73 // vertexWriter << p0 << p1 << p2; 74 // } 75 // 76 // The above code iterates over the triangles being popped, and then once iteration is finished, 77 // the PoppedTriangleStack is destroyed, triggering the pending stack update. 78 class PoppedTriangleStack { 79 public: PoppedTriangleStack(MiddleOutPolygonTriangulator * middleOut,SkPoint lastPoint,StackVertex * end,StackVertex * newTopVertex,StackVertex newTopValue)80 PoppedTriangleStack(MiddleOutPolygonTriangulator* middleOut, 81 SkPoint lastPoint, 82 StackVertex* end, 83 StackVertex* newTopVertex, 84 StackVertex newTopValue) 85 : fMiddleOut(middleOut) 86 , fLastPoint(lastPoint) 87 , fEnd(end) 88 , fNewTopVertex(newTopVertex) 89 , fNewTopValue(newTopValue) { 90 } 91 PoppedTriangleStack(PoppedTriangleStack && that)92 PoppedTriangleStack(PoppedTriangleStack&& that) { 93 memcpy(this, &that, sizeof(*this)); 94 that.fMiddleOut = nullptr; // Don't do a stack update during our destructor. 95 } 96 ~PoppedTriangleStack()97 ~PoppedTriangleStack() { 98 if (fMiddleOut) { 99 fMiddleOut->fTop = fNewTopVertex; 100 *fNewTopVertex = fNewTopValue; 101 } 102 } 103 104 struct Iter { 105 bool operator!=(const Iter& iter) { return fVertex != iter.fVertex; } 106 void operator++() { --fVertex; } 107 std::tuple<SkPoint, SkPoint, SkPoint> operator*() { 108 return {fVertex[-1].fPoint, fVertex[0].fPoint, fLastPoint}; 109 } 110 StackVertex* fVertex; 111 SkPoint fLastPoint; 112 }; 113 begin()114 Iter begin() const { return {fMiddleOut ? fMiddleOut->fTop : fEnd, fLastPoint}; } end()115 Iter end() const { return {fEnd, fLastPoint}; } 116 117 private: 118 MiddleOutPolygonTriangulator* fMiddleOut; 119 SkPoint fLastPoint; 120 StackVertex* fEnd; 121 StackVertex* fNewTopVertex; 122 StackVertex fNewTopValue; 123 }; 124 125 // maxPushVertexCalls is an upper bound on the number of times the caller will call 126 // pushVertex(). The caller must not call it more times than this. (Beware of int overflow.) 127 MiddleOutPolygonTriangulator(int maxPushVertexCalls, SkPoint startPoint = {0,0}) { 128 SkASSERT(maxPushVertexCalls >= 0); 129 // Determine the deepest our stack can ever go. 130 int maxStackDepth = SkNextLog2(maxPushVertexCalls) + 1; 131 if (maxStackDepth > kStackPreallocCount) { 132 fVertexStack.reset(maxStackDepth); 133 } 134 SkDEBUGCODE(fStackAllocCount = maxStackDepth;) 135 // The stack will always contain a starting point. This is an implicit moveTo(0, 0) 136 // initially, but will be overridden if moveTo() gets called before adding geometry. 137 fVertexStack[0] = {startPoint, 0}; 138 fTop = fVertexStack; 139 } 140 141 // Returns an RAII object that first allows the caller to iterate the triangles we will pop, 142 // pops those triangles, and finally pushes 'pt' onto the vertex stack. pushVertex(SkPoint pt)143 [[nodiscard]] PoppedTriangleStack pushVertex(SkPoint pt) { 144 // Our topology wants triangles that have the same vertexIdxDelta on both sides: 145 // e.g., a run of 9 points should be triangulated as: 146 // 147 // [0, 1, 2], [2, 3, 4], [4, 5, 6], [6, 7, 8] // vertexIdxDelta == 1 148 // [0, 2, 4], [4, 6, 8] // vertexIdxDelta == 2 149 // [0, 4, 8] // vertexIdxDelta == 4 150 // 151 // Find as many new triangles as we can pop off the stack that have equal-delta sides. (This 152 // is a stack-based implementation of the recursive example method from the class comment.) 153 StackVertex* endVertex = fTop; 154 int vertexIdxDelta = 1; 155 while (endVertex->fVertexIdxDelta == vertexIdxDelta) { 156 --endVertex; 157 vertexIdxDelta *= 2; 158 } 159 160 // Once the above triangles are popped, push 'pt' to the top of the stack. 161 StackVertex* newTopVertex = endVertex + 1; 162 StackVertex newTopValue = {pt, vertexIdxDelta}; 163 SkASSERT(newTopVertex < fVertexStack + fStackAllocCount); // Is fStackAllocCount enough? 164 165 return PoppedTriangleStack(this, pt, endVertex, newTopVertex, newTopValue); 166 } 167 168 // Returns an RAII object that first allows the caller to iterate the remaining triangles, then 169 // resets the vertex stack with newStartPoint. closeAndMove(SkPoint newStartPoint)170 [[nodiscard]] PoppedTriangleStack closeAndMove(SkPoint newStartPoint) { 171 // Add an implicit line back to the starting point. 172 SkPoint startPt = fVertexStack[0].fPoint; 173 174 // Triangulate the rest of the polygon. Since we simply have to finish now, we can't be 175 // picky anymore about getting a pure middle-out topology. 176 StackVertex* endVertex = std::min(fTop, fVertexStack + 1); 177 178 // Once every remaining triangle is popped, reset the vertex stack with newStartPoint. 179 StackVertex* newTopVertex = fVertexStack; 180 StackVertex newTopValue = {newStartPoint, 0}; 181 182 return PoppedTriangleStack(this, startPt, endVertex, newTopVertex, newTopValue); 183 } 184 185 // Returns an RAII object that first allows the caller to iterate the remaining triangles, then 186 // resets the vertex stack with the same starting point as it had before. close()187 [[nodiscard]] PoppedTriangleStack close() { 188 return this->closeAndMove(fVertexStack[0].fPoint); 189 } 190 191 private: 192 constexpr static int kStackPreallocCount = 32; 193 skia_private::AutoSTMalloc<kStackPreallocCount, StackVertex> fVertexStack; 194 SkDEBUGCODE(int fStackAllocCount;) 195 StackVertex* fTop; 196 }; 197 198 // This is a helper class that transforms and pushes a path's inner fan vertices onto a 199 // MiddleOutPolygonTriangulator. Example usage: 200 // 201 // for (PathMiddleOutFanIter it(pathMatrix, path); !it.done();) { 202 // for (auto [p0, p1, p2] : it.nextStack()) { 203 // vertexWriter << p0 << p1 << p2; 204 // } 205 // } 206 // 207 class PathMiddleOutFanIter { 208 public: PathMiddleOutFanIter(const SkPath & path)209 PathMiddleOutFanIter(const SkPath& path) : fMiddleOut(path.countVerbs()) { 210 SkPathPriv::Iterate it(path); 211 fPathIter = it.begin(); 212 fPathEnd = it.end(); 213 } 214 done()215 bool done() const { return fDone; } 216 nextStack()217 MiddleOutPolygonTriangulator::PoppedTriangleStack nextStack() { 218 SkASSERT(!fDone); 219 if (fPathIter == fPathEnd) { 220 fDone = true; 221 return fMiddleOut.close(); 222 } 223 switch (auto [verb, pts, w] = *fPathIter++; verb) { 224 SkPoint pt; 225 case SkPathVerb::kMove: 226 return fMiddleOut.closeAndMove(pts[0]); 227 case SkPathVerb::kLine: 228 case SkPathVerb::kQuad: 229 case SkPathVerb::kConic: 230 case SkPathVerb::kCubic: 231 pt = pts[SkPathPriv::PtsInIter((unsigned)verb) - 1]; 232 return fMiddleOut.pushVertex(pt); 233 case SkPathVerb::kClose: 234 return fMiddleOut.close(); 235 } 236 SkUNREACHABLE; 237 } 238 239 private: 240 MiddleOutPolygonTriangulator fMiddleOut; 241 SkPathPriv::RangeIter fPathIter; 242 SkPathPriv::RangeIter fPathEnd; 243 bool fDone = false; 244 }; 245 246 } // namespace skgpu::tess 247 248 #endif // skgpu_tessellate_MiddleOutPolygonTriangulator_DEFINED 249