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