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 GrMiddleOutPolygonTriangulator_DEFINED 9 #define GrMiddleOutPolygonTriangulator_DEFINED 10 11 #include "include/core/SkPath.h" 12 #include "include/core/SkPoint.h" 13 #include "include/private/SkTemplates.h" 14 #include "src/core/SkMathPriv.h" 15 #include "src/core/SkPathPriv.h" 16 17 // This class emits a polygon triangulation with a "middle-out" topology. Conceptually, middle-out 18 // emits one large triangle with vertices on both endpoints and a middle point, then recurses on 19 // both sides of the new triangle. i.e.: 20 // 21 // void emit_middle_out_triangulation(int startIdx, int endIdx) { 22 // if (startIdx + 1 == endIdx) { 23 // return; 24 // } 25 // int middleIdx = startIdx + SkNextPow2(endIdx - startIdx) / 2; 26 // 27 // // Recurse on the left half. 28 // emit_middle_out_triangulation(startIdx, middleIdx); 29 // 30 // // Emit a large triangle with vertices on both endpoints and a middle point. 31 // emit_triangle(vertices[startIdx], vertices[middleIdx], vertices[endIdx - 1]); 32 // 33 // // Recurse on the right half. 34 // emit_middle_out_triangulation(middleIdx, endIdx); 35 // } 36 // 37 // Middle-out produces drastically less work for the rasterizer as compared a linear triangle strip 38 // or fan. 39 // 40 // This class is designed to not know or store all the vertices in the polygon at once. The caller 41 // pushes each vertex in linear order (perhaps while parsing a path), then rather than relying on 42 // recursion, we manipulate an O(log N) stack to determine the correct middle-out triangulation. 43 class GrMiddleOutPolygonTriangulator { 44 public: GrMiddleOutPolygonTriangulator(SkPoint * vertexData,int perTriangleVertexAdvance,int maxPushVertexCalls)45 GrMiddleOutPolygonTriangulator(SkPoint* vertexData, int perTriangleVertexAdvance, 46 int maxPushVertexCalls) 47 : fVertexData(vertexData) 48 , fPerTriangleVertexAdvance(perTriangleVertexAdvance) { 49 // Determine the deepest our stack can ever go. 50 int maxStackDepth = SkNextLog2(maxPushVertexCalls) + 1; 51 if (maxStackDepth > kStackPreallocCount) { 52 fVertexStack.reset(maxStackDepth); 53 } 54 SkDEBUGCODE(fStackAllocCount = maxStackDepth;) 55 // The stack will always contain a starting point. This is an implicit moveTo(0, 0) 56 // initially, but will be overridden if moveTo() gets called before adding geometry. 57 fVertexStack[0] = {0, {0, 0}}; 58 fTop = fVertexStack; 59 } 60 pushVertex(const SkPoint & pt)61 void pushVertex(const SkPoint& pt) { 62 if (pt == fVertexStack[0].fPoint) { 63 this->close(); 64 return; 65 } 66 // This new vertex we are about to add is one vertex away from the top of the stack. 67 // i.e., it is guaranteed to be the next vertex in the polygon after the one stored in fTop. 68 int vertexIdxDelta = 1; 69 // Our topology wants triangles that have the same vertexIdxDelta on both sides: 70 // e.g., a run of 9 points should be triangulated as: 71 // 72 // [0, 1, 2], [2, 3, 4], [4, 5, 6], [6, 7, 8] // vertexIdxDelta == 1 73 // [0, 2, 4], [4, 6, 8] // vertexIdxDelta == 2 74 // [0, 4, 8] // vertexIdxDelta == 4 75 // 76 // Emit as many new triangles as we can with equal-delta sides and pop their vertices off 77 // the stack before pushing this new vertex. 78 // 79 // (This is a stack-based implementation of the recursive example method from the class 80 // comment.) 81 while (vertexIdxDelta == fTop->fVertexIdxDelta) { 82 this->popTopTriangle(pt); 83 vertexIdxDelta *= 2; 84 } 85 this->pushVertex(vertexIdxDelta, pt); 86 } 87 close()88 int close() { 89 if (fTop == fVertexStack) { // The stack only contains one point (the starting point). 90 return fTotalClosedTriangleCount; 91 } 92 // We will count vertices by walking the stack backwards. 93 int finalVertexCount = 1; 94 // Add an implicit line back to the starting point, then triangulate the rest of the 95 // polygon. Since we simply have to finish now, we aren't picky anymore about making the 96 // vertexIdxDeltas match. 97 const SkPoint& p0 = fVertexStack[0].fPoint; 98 SkASSERT(fTop->fPoint != p0); // We should have detected and handled this case earlier. 99 while (fTop - 1 > fVertexStack) { 100 finalVertexCount += fTop->fVertexIdxDelta; 101 this->popTopTriangle(p0); 102 } 103 SkASSERT(fTop == fVertexStack + 1); 104 finalVertexCount += fTop->fVertexIdxDelta; 105 SkASSERT(fVertexStack[0].fVertexIdxDelta == 0); 106 fTop = fVertexStack; 107 int numTriangles = finalVertexCount - 2; 108 SkASSERT(numTriangles >= 0); 109 fTotalClosedTriangleCount += numTriangles; 110 return fTotalClosedTriangleCount; 111 } 112 closeAndMove(const SkPoint & startPt)113 void closeAndMove(const SkPoint& startPt) { 114 this->close(); 115 SkASSERT(fTop == fVertexStack); // The stack should only contain a starting point now. 116 fTop->fPoint = startPt; // Modify the starting point. 117 SkASSERT(fTop->fVertexIdxDelta == 0); // Ensure we are in the initial stack state. 118 } 119 WritePathInnerFan(SkPoint * vertexData,int perTriangleVertexAdvance,const SkPath & path)120 static int WritePathInnerFan(SkPoint* vertexData, int perTriangleVertexAdvance, 121 const SkPath& path) { 122 GrMiddleOutPolygonTriangulator middleOut(vertexData, perTriangleVertexAdvance, 123 path.countVerbs()); 124 for (auto [verb, pts, w] : SkPathPriv::Iterate(path)) { 125 switch (verb) { 126 case SkPathVerb::kMove: 127 middleOut.closeAndMove(pts[0]); 128 break; 129 case SkPathVerb::kLine: 130 case SkPathVerb::kQuad: 131 case SkPathVerb::kConic: 132 case SkPathVerb::kCubic: 133 middleOut.pushVertex(pts[SkPathPriv::PtsInIter((unsigned)verb) - 1]); 134 break; 135 case SkPathVerb::kClose: 136 break; 137 } 138 } 139 return middleOut.close(); 140 } 141 142 private: 143 struct StackVertex { 144 // How many polygon vertices away is this vertex from the previous vertex on the stack? 145 // i.e., the ith stack element's vertex index in the original polygon is: 146 // 147 // fVertexStack[i].fVertexIdxDelta + fVertexStack[i - 1].fVertexIdxDelta + ... + 148 // fVertexStack[1].fVertexIdxDelta. 149 // 150 // NOTE: fVertexStack[0].fVertexIdxDelta always == 0. 151 int fVertexIdxDelta; 152 SkPoint fPoint; 153 }; 154 pushVertex(int vertexIdxDelta,const SkPoint & point)155 void pushVertex(int vertexIdxDelta, const SkPoint& point) { 156 ++fTop; 157 // We should never push deeper than fStackAllocCount. 158 SkASSERT(fTop < fVertexStack + fStackAllocCount); 159 fTop->fVertexIdxDelta = vertexIdxDelta; 160 fTop->fPoint = point; 161 } 162 popTopTriangle(const SkPoint & lastPt)163 void popTopTriangle(const SkPoint& lastPt) { 164 SkASSERT(fTop > fVertexStack); // We should never pop the starting point. 165 --fTop; 166 fVertexData[0] = fTop[0].fPoint; 167 fVertexData[1] = fTop[1].fPoint; 168 fVertexData[2] = lastPt; 169 fVertexData += fPerTriangleVertexAdvance; 170 } 171 172 constexpr static int kStackPreallocCount = 32; 173 SkAutoSTMalloc<kStackPreallocCount, StackVertex> fVertexStack; 174 SkDEBUGCODE(int fStackAllocCount;) 175 StackVertex* fTop; 176 SkPoint* fVertexData; 177 int fPerTriangleVertexAdvance; 178 int fTotalClosedTriangleCount = 0; 179 }; 180 181 #endif 182