OLD | NEW |
---|---|
1 /* | 1 /* |
2 * Copyright 2015 Google Inc. | 2 * Copyright 2015 Google Inc. |
3 * | 3 * |
4 * Use of this source code is governed by a BSD-style license that can be | 4 * Use of this source code is governed by a BSD-style license that can be |
5 * found in the LICENSE file. | 5 * found in the LICENSE file. |
6 */ | 6 */ |
7 | 7 |
8 #include "GrTessellatingPathRenderer.h" | 8 #include "GrTessellator.h" |
9 | 9 |
10 #include "GrBatchFlushState.h" | 10 #include "GrBatchFlushState.h" |
11 #include "GrBatchTest.h" | 11 #include "GrBatchTest.h" |
12 #include "GrDefaultGeoProcFactory.h" | 12 #include "GrDefaultGeoProcFactory.h" |
13 #include "GrPathUtils.h" | 13 #include "GrPathUtils.h" |
14 #include "GrVertices.h" | 14 #include "GrVertices.h" |
15 #include "GrResourceCache.h" | 15 #include "GrResourceCache.h" |
16 #include "GrResourceProvider.h" | 16 #include "GrResourceProvider.h" |
17 #include "SkChunkAlloc.h" | |
18 #include "SkGeometry.h" | 17 #include "SkGeometry.h" |
19 | 18 |
20 #include "batches/GrVertexBatch.h" | 19 #include "batches/GrVertexBatch.h" |
21 | 20 |
22 #include <stdio.h> | 21 #include <stdio.h> |
23 | 22 |
24 /* | 23 /* |
25 * This path renderer tessellates the path into triangles, uploads the triangles to a | |
26 * vertex buffer, and renders them with a single draw call. It does not currentl y do | |
27 * antialiasing, so it must be used in conjunction with multisampling. | |
28 * | |
29 * There are six stages to the algorithm: | 24 * There are six stages to the algorithm: |
30 * | 25 * |
31 * 1) Linearize the path contours into piecewise linear segments (path_to_contou rs()). | 26 * 1) Linearize the path contours into piecewise linear segments (path_to_contou rs()). |
32 * 2) Build a mesh of edges connecting the vertices (build_edges()). | 27 * 2) Build a mesh of edges connecting the vertices (build_edges()). |
33 * 3) Sort the vertices in Y (and secondarily in X) (merge_sort()). | 28 * 3) Sort the vertices in Y (and secondarily in X) (merge_sort()). |
34 * 4) Simplify the mesh by inserting new vertices at intersecting edges (simplif y()). | 29 * 4) Simplify the mesh by inserting new vertices at intersecting edges (simplif y()). |
35 * 5) Tessellate the simplified mesh into monotone polygons (tessellate()). | 30 * 5) Tessellate the simplified mesh into monotone polygons (tessellate()). |
36 * 6) Triangulate the monotone polygons directly into a vertex buffer (polys_to_ triangles()). | 31 * 6) Triangulate the monotone polygons directly into a vertex buffer (polys_to_ triangles()). |
37 * | 32 * |
38 * The vertex sorting in step (3) is a merge sort, since it plays well with the linked list | 33 * The vertex sorting in step (3) is a merge sort, since it plays well with the linked list |
(...skipping 34 matching lines...) Expand 10 before | Expand all | Expand 10 after Loading... | |
73 * frequent. There may be other data structures worth investigating, however. | 68 * frequent. There may be other data structures worth investigating, however. |
74 * | 69 * |
75 * Note that the orientation of the line sweep algorithms is determined by the a spect ratio of the | 70 * Note that the orientation of the line sweep algorithms is determined by the a spect ratio of the |
76 * path bounds. When the path is taller than it is wide, we sort vertices based on increasing Y | 71 * path bounds. When the path is taller than it is wide, we sort vertices based on increasing Y |
77 * coordinate, and secondarily by increasing X coordinate. When the path is wide r than it is tall, | 72 * coordinate, and secondarily by increasing X coordinate. When the path is wide r than it is tall, |
78 * we sort by increasing X coordinate, but secondarily by *decreasing* Y coordin ate. This is so | 73 * we sort by increasing X coordinate, but secondarily by *decreasing* Y coordin ate. This is so |
79 * that the "left" and "right" orientation in the code remains correct (edges to the left are | 74 * that the "left" and "right" orientation in the code remains correct (edges to the left are |
80 * increasing in Y; edges to the right are decreasing in Y). That is, the settin g rotates 90 | 75 * increasing in Y; edges to the right are decreasing in Y). That is, the settin g rotates 90 |
81 * degrees counterclockwise, rather that transposing. | 76 * degrees counterclockwise, rather that transposing. |
82 */ | 77 */ |
83 #define LOGGING_ENABLED 0 | |
Stephen White
2016/01/04 22:51:19
If we do manage to keep Vertex and friends in the
| |
84 #define WIREFRAME 0 | |
85 | 78 |
86 #if LOGGING_ENABLED | 79 #if TESSELLATOR_LOGGING_ENABLED |
87 #define LOG printf | 80 #define LOG printf |
88 #else | 81 #else |
89 #define LOG(...) | 82 #define LOG(...) |
90 #endif | 83 #endif |
91 | 84 |
92 #define ALLOC_NEW(Type, args, alloc) new (alloc.allocThrow(sizeof(Type))) Type a rgs | 85 #define ALLOC_NEW(Type, args, alloc) new (alloc.allocThrow(sizeof(Type))) Type a rgs |
93 | 86 |
94 namespace { | 87 double Edge::dist(const SkPoint& p) const { |
88 return fDY * p.fX - fDX * p.fY + fC; | |
89 } | |
95 | 90 |
96 struct Vertex; | 91 bool Edge::isRightOf(TessellatorVertex* v) const { |
97 struct Edge; | 92 return dist(v->fPoint) < 0.0; |
93 } | |
94 | |
95 bool Edge::isLeftOf(TessellatorVertex* v) const { | |
96 return dist(v->fPoint) > 0.0; | |
97 } | |
98 | |
99 void Edge::recompute() { | |
100 fDX = static_cast<double>(fBottom->fPoint.fX) - fTop->fPoint.fX; | |
101 fDY = static_cast<double>(fBottom->fPoint.fY) - fTop->fPoint.fY; | |
102 fC = static_cast<double>(fTop->fPoint.fY) * fBottom->fPoint.fX - | |
103 static_cast<double>(fTop->fPoint.fX) * fBottom->fPoint.fY; | |
104 } | |
105 | |
106 bool Edge::intersect(const Edge& other, SkPoint* p) { | |
107 #if TESSELLATOR_LOGGING_ENABLED | |
108 LOG("intersecting %g -> %g with %g -> %g\n", | |
109 fTop->fID, fBottom->fID, | |
110 other.fTop->fID, other.fBottom->fID); | |
111 #endif | |
112 if (fTop == other.fTop || fBottom == other.fBottom) { | |
113 return false; | |
114 } | |
115 double denom = fDX * other.fDY - fDY * other.fDX; | |
116 if (denom == 0.0) { | |
117 return false; | |
118 } | |
119 double dx = static_cast<double>(fTop->fPoint.fX) - other.fTop->fPoint.fX; | |
120 double dy = static_cast<double>(fTop->fPoint.fY) - other.fTop->fPoint.fY; | |
121 double sNumer = dy * other.fDX - dx * other.fDY; | |
122 double tNumer = dy * fDX - dx * fDY; | |
123 // If (sNumer / denom) or (tNumer / denom) is not in [0..1], exit early. | |
124 // This saves us doing the divide below unless absolutely necessary. | |
125 if (denom > 0.0 ? (sNumer < 0.0 || sNumer > denom || tNumer < 0.0 || tNumer > denom) | |
126 : (sNumer > 0.0 || sNumer < denom || tNumer > 0.0 || tNumer < denom)) { | |
127 return false; | |
128 } | |
129 double s = sNumer / denom; | |
130 SkASSERT(s >= 0.0 && s <= 1.0); | |
131 p->fX = SkDoubleToScalar(fTop->fPoint.fX + s * fDX); | |
132 p->fY = SkDoubleToScalar(fTop->fPoint.fY + s * fDY); | |
133 return true; | |
134 } | |
135 | |
136 bool Edge::isActive(EdgeList* activeEdges) const { | |
137 return activeEdges && (fLeft || fRight || activeEdges->fHead == this); | |
138 } | |
139 | |
98 struct Poly; | 140 struct Poly; |
99 | 141 |
100 template <class T, T* T::*Prev, T* T::*Next> | 142 template <class T, T* T::*Prev, T* T::*Next> |
101 void insert(T* t, T* prev, T* next, T** head, T** tail) { | 143 void insert(T* t, T* prev, T* next, T** head, T** tail) { |
102 t->*Prev = prev; | 144 t->*Prev = prev; |
103 t->*Next = next; | 145 t->*Next = next; |
104 if (prev) { | 146 if (prev) { |
105 prev->*Next = t; | 147 prev->*Next = t; |
106 } else if (head) { | 148 } else if (head) { |
107 *head = t; | 149 *head = t; |
(...skipping 13 matching lines...) Expand all Loading... | |
121 *head = t->*Next; | 163 *head = t->*Next; |
122 } | 164 } |
123 if (t->*Next) { | 165 if (t->*Next) { |
124 t->*Next->*Prev = t->*Prev; | 166 t->*Next->*Prev = t->*Prev; |
125 } else if (tail) { | 167 } else if (tail) { |
126 *tail = t->*Prev; | 168 *tail = t->*Prev; |
127 } | 169 } |
128 t->*Prev = t->*Next = nullptr; | 170 t->*Prev = t->*Next = nullptr; |
129 } | 171 } |
130 | 172 |
131 /** | |
132 * Vertices are used in three ways: first, the path contours are converted into a | |
133 * circularly-linked list of Vertices for each contour. After edge construction, the same Vertices | |
134 * are re-ordered by the merge sort according to the sweep_lt comparator (usuall y, increasing | |
135 * in Y) using the same fPrev/fNext pointers that were used for the contours, to avoid | |
136 * reallocation. Finally, MonotonePolys are built containing a circularly-linked list of | |
137 * Vertices. (Currently, those Vertices are newly-allocated for the MonotonePoly s, since | |
138 * an individual Vertex from the path mesh may belong to multiple | |
139 * MonotonePolys, so the original Vertices cannot be re-used. | |
140 */ | |
141 | |
142 struct Vertex { | |
143 Vertex(const SkPoint& point) | |
144 : fPoint(point), fPrev(nullptr), fNext(nullptr) | |
145 , fFirstEdgeAbove(nullptr), fLastEdgeAbove(nullptr) | |
146 , fFirstEdgeBelow(nullptr), fLastEdgeBelow(nullptr) | |
147 , fProcessed(false) | |
148 #if LOGGING_ENABLED | |
149 , fID (-1.0f) | |
150 #endif | |
151 {} | |
152 SkPoint fPoint; // Vertex position | |
153 Vertex* fPrev; // Linked list of contours, then Y-sorted vertices . | |
154 Vertex* fNext; // " | |
155 Edge* fFirstEdgeAbove; // Linked list of edges above this vertex. | |
156 Edge* fLastEdgeAbove; // " | |
157 Edge* fFirstEdgeBelow; // Linked list of edges below this vertex. | |
158 Edge* fLastEdgeBelow; // " | |
159 bool fProcessed; // Has this vertex been seen in simplify()? | |
160 #if LOGGING_ENABLED | |
161 float fID; // Identifier used for logging. | |
162 #endif | |
163 }; | |
164 | |
165 /******************************************************************************* ********/ | 173 /******************************************************************************* ********/ |
166 | 174 |
167 typedef bool (*CompareFunc)(const SkPoint& a, const SkPoint& b); | 175 typedef bool (*CompareFunc)(const SkPoint& a, const SkPoint& b); |
168 | 176 |
169 struct Comparator { | 177 struct Comparator { |
170 CompareFunc sweep_lt; | 178 CompareFunc sweep_lt; |
171 CompareFunc sweep_gt; | 179 CompareFunc sweep_gt; |
172 }; | 180 }; |
173 | 181 |
174 bool sweep_lt_horiz(const SkPoint& a, const SkPoint& b) { | 182 bool sweep_lt_horiz(const SkPoint& a, const SkPoint& b) { |
175 return a.fX == b.fX ? a.fY > b.fY : a.fX < b.fX; | 183 return a.fX == b.fX ? a.fY > b.fY : a.fX < b.fX; |
176 } | 184 } |
177 | 185 |
178 bool sweep_lt_vert(const SkPoint& a, const SkPoint& b) { | 186 bool sweep_lt_vert(const SkPoint& a, const SkPoint& b) { |
179 return a.fY == b.fY ? a.fX < b.fX : a.fY < b.fY; | 187 return a.fY == b.fY ? a.fX < b.fX : a.fY < b.fY; |
180 } | 188 } |
181 | 189 |
182 bool sweep_gt_horiz(const SkPoint& a, const SkPoint& b) { | 190 bool sweep_gt_horiz(const SkPoint& a, const SkPoint& b) { |
183 return a.fX == b.fX ? a.fY < b.fY : a.fX > b.fX; | 191 return a.fX == b.fX ? a.fY < b.fY : a.fX > b.fX; |
184 } | 192 } |
185 | 193 |
186 bool sweep_gt_vert(const SkPoint& a, const SkPoint& b) { | 194 bool sweep_gt_vert(const SkPoint& a, const SkPoint& b) { |
187 return a.fY == b.fY ? a.fX > b.fX : a.fY > b.fY; | 195 return a.fY == b.fY ? a.fX > b.fX : a.fY > b.fY; |
188 } | 196 } |
189 | 197 |
190 inline SkPoint* emit_vertex(Vertex* v, SkPoint* data) { | 198 inline SkPoint* emit_vertex(TessellatorVertex* v, SkPoint* data) { |
191 *data++ = v->fPoint; | 199 *data++ = v->fPoint; |
192 return data; | 200 return data; |
193 } | 201 } |
194 | 202 |
195 SkPoint* emit_triangle(Vertex* v0, Vertex* v1, Vertex* v2, SkPoint* data) { | 203 SkPoint* emit_triangle(TessellatorVertex* v0, TessellatorVertex* v1, Tessellator Vertex* v2, |
196 #if WIREFRAME | 204 SkPoint* data) { |
205 #if TESSELLATOR_WIREFRAME | |
197 data = emit_vertex(v0, data); | 206 data = emit_vertex(v0, data); |
198 data = emit_vertex(v1, data); | 207 data = emit_vertex(v1, data); |
199 data = emit_vertex(v1, data); | 208 data = emit_vertex(v1, data); |
200 data = emit_vertex(v2, data); | 209 data = emit_vertex(v2, data); |
201 data = emit_vertex(v2, data); | 210 data = emit_vertex(v2, data); |
202 data = emit_vertex(v0, data); | 211 data = emit_vertex(v0, data); |
203 #else | 212 #else |
204 data = emit_vertex(v0, data); | 213 data = emit_vertex(v0, data); |
205 data = emit_vertex(v1, data); | 214 data = emit_vertex(v1, data); |
206 data = emit_vertex(v2, data); | 215 data = emit_vertex(v2, data); |
207 #endif | 216 #endif |
208 return data; | 217 return data; |
209 } | 218 } |
210 | 219 |
211 struct EdgeList { | |
212 EdgeList() : fHead(nullptr), fTail(nullptr) {} | |
213 Edge* fHead; | |
214 Edge* fTail; | |
215 }; | |
216 | |
217 /** | 220 /** |
218 * An Edge joins a top Vertex to a bottom Vertex. Edge ordering for the list of "edges above" and | 221 * An Edge joins a top Vertex to a bottom Vertex. Edge ordering for the list of "edges above" and |
219 * "edge below" a vertex as well as for the active edge list is handled by isLef tOf()/isRightOf(). | 222 * "edge below" a vertex as well as for the active edge list is handled by isLef tOf()/isRightOf(). |
220 * Note that an Edge will give occasionally dist() != 0 for its own endpoints (b ecause floating | 223 * Note that an Edge will give occasionally dist() != 0 for its own endpoints (b ecause floating |
221 * point). For speed, that case is only tested by the callers which require it ( e.g., | 224 * point). For speed, that case is only tested by the callers which require it ( e.g., |
222 * cleanup_active_edges()). Edges also handle checking for intersection with oth er edges. | 225 * cleanup_active_edges()). Edges also handle checking for intersection with oth er edges. |
223 * Currently, this converts the edges to the parametric form, in order to avoid doing a division | 226 * Currently, this converts the edges to the parametric form, in order to avoid doing a division |
224 * until an intersection has been confirmed. This is slightly slower in the "fou nd" case, but | 227 * until an intersection has been confirmed. This is slightly slower in the "fou nd" case, but |
225 * a lot faster in the "not found" case. | 228 * a lot faster in the "not found" case. |
226 * | 229 * |
227 * The coefficients of the line equation stored in double precision to avoid cat astrphic | 230 * The coefficients of the line equation stored in double precision to avoid cat astrphic |
228 * cancellation in the isLeftOf() and isRightOf() checks. Using doubles ensures that the result is | 231 * cancellation in the isLeftOf() and isRightOf() checks. Using doubles ensures that the result is |
229 * correct in float, since it's a polynomial of degree 2. The intersect() functi on, being | 232 * correct in float, since it's a polynomial of degree 2. The intersect() functi on, being |
230 * degree 5, is still subject to catastrophic cancellation. We deal with that by assuming its | 233 * degree 5, is still subject to catastrophic cancellation. We deal with that by assuming its |
231 * output may be incorrect, and adjusting the mesh topology to match (see commen t at the top of | 234 * output may be incorrect, and adjusting the mesh topology to match (see commen t at the top of |
232 * this file). | 235 * this file). |
233 */ | 236 */ |
234 | 237 |
235 struct Edge { | |
236 Edge(Vertex* top, Vertex* bottom, int winding) | |
237 : fWinding(winding) | |
238 , fTop(top) | |
239 , fBottom(bottom) | |
240 , fLeft(nullptr) | |
241 , fRight(nullptr) | |
242 , fPrevEdgeAbove(nullptr) | |
243 , fNextEdgeAbove(nullptr) | |
244 , fPrevEdgeBelow(nullptr) | |
245 , fNextEdgeBelow(nullptr) | |
246 , fLeftPoly(nullptr) | |
247 , fRightPoly(nullptr) { | |
248 recompute(); | |
249 } | |
250 int fWinding; // 1 == edge goes downward; -1 = edge goes upwar d. | |
251 Vertex* fTop; // The top vertex in vertex-sort-order (sweep_lt ). | |
252 Vertex* fBottom; // The bottom vertex in vertex-sort-order. | |
253 Edge* fLeft; // The linked list of edges in the active edge l ist. | |
254 Edge* fRight; // " | |
255 Edge* fPrevEdgeAbove; // The linked list of edges in the bottom Vertex 's "edges above". | |
256 Edge* fNextEdgeAbove; // " | |
257 Edge* fPrevEdgeBelow; // The linked list of edges in the top Vertex's "edges below". | |
258 Edge* fNextEdgeBelow; // " | |
259 Poly* fLeftPoly; // The Poly to the left of this edge, if any. | |
260 Poly* fRightPoly; // The Poly to the right of this edge, if any. | |
261 double fDX; // The line equation for this edge, in implicit form. | |
262 double fDY; // fDY * x + fDX * y + fC = 0, for point (x, y) on the line. | |
263 double fC; | |
264 double dist(const SkPoint& p) const { | |
265 return fDY * p.fX - fDX * p.fY + fC; | |
266 } | |
267 bool isRightOf(Vertex* v) const { | |
268 return dist(v->fPoint) < 0.0; | |
269 } | |
270 bool isLeftOf(Vertex* v) const { | |
271 return dist(v->fPoint) > 0.0; | |
272 } | |
273 void recompute() { | |
274 fDX = static_cast<double>(fBottom->fPoint.fX) - fTop->fPoint.fX; | |
275 fDY = static_cast<double>(fBottom->fPoint.fY) - fTop->fPoint.fY; | |
276 fC = static_cast<double>(fTop->fPoint.fY) * fBottom->fPoint.fX - | |
277 static_cast<double>(fTop->fPoint.fX) * fBottom->fPoint.fY; | |
278 } | |
279 bool intersect(const Edge& other, SkPoint* p) { | |
280 LOG("intersecting %g -> %g with %g -> %g\n", | |
281 fTop->fID, fBottom->fID, | |
282 other.fTop->fID, other.fBottom->fID); | |
283 if (fTop == other.fTop || fBottom == other.fBottom) { | |
284 return false; | |
285 } | |
286 double denom = fDX * other.fDY - fDY * other.fDX; | |
287 if (denom == 0.0) { | |
288 return false; | |
289 } | |
290 double dx = static_cast<double>(fTop->fPoint.fX) - other.fTop->fPoint.fX ; | |
291 double dy = static_cast<double>(fTop->fPoint.fY) - other.fTop->fPoint.fY ; | |
292 double sNumer = dy * other.fDX - dx * other.fDY; | |
293 double tNumer = dy * fDX - dx * fDY; | |
294 // If (sNumer / denom) or (tNumer / denom) is not in [0..1], exit early. | |
295 // This saves us doing the divide below unless absolutely necessary. | |
296 if (denom > 0.0 ? (sNumer < 0.0 || sNumer > denom || tNumer < 0.0 || tNu mer > denom) | |
297 : (sNumer > 0.0 || sNumer < denom || tNumer > 0.0 || tNu mer < denom)) { | |
298 return false; | |
299 } | |
300 double s = sNumer / denom; | |
301 SkASSERT(s >= 0.0 && s <= 1.0); | |
302 p->fX = SkDoubleToScalar(fTop->fPoint.fX + s * fDX); | |
303 p->fY = SkDoubleToScalar(fTop->fPoint.fY + s * fDY); | |
304 return true; | |
305 } | |
306 bool isActive(EdgeList* activeEdges) const { | |
307 return activeEdges && (fLeft || fRight || activeEdges->fHead == this); | |
308 } | |
309 }; | |
310 | |
311 /******************************************************************************* ********/ | 238 /******************************************************************************* ********/ |
312 | 239 |
313 struct Poly { | 240 struct Poly { |
314 Poly(int winding) | 241 Poly(int winding) |
315 : fWinding(winding) | 242 : fWinding(winding) |
316 , fHead(nullptr) | 243 , fHead(nullptr) |
317 , fTail(nullptr) | 244 , fTail(nullptr) |
318 , fActive(nullptr) | 245 , fActive(nullptr) |
319 , fNext(nullptr) | 246 , fNext(nullptr) |
320 , fPartner(nullptr) | 247 , fPartner(nullptr) |
321 , fCount(0) | 248 , fCount(0) |
322 { | 249 { |
323 #if LOGGING_ENABLED | 250 #if TESSELLATOR_LOGGING_ENABLED |
324 static int gID = 0; | 251 static int gID = 0; |
325 fID = gID++; | 252 fID = gID++; |
326 LOG("*** created Poly %d\n", fID); | 253 LOG("*** created Poly %d\n", fID); |
327 #endif | 254 #endif |
328 } | 255 } |
329 typedef enum { kNeither_Side, kLeft_Side, kRight_Side } Side; | 256 typedef enum { kNeither_Side, kLeft_Side, kRight_Side } Side; |
330 struct MonotonePoly { | 257 struct MonotonePoly { |
331 MonotonePoly() | 258 MonotonePoly() |
332 : fSide(kNeither_Side) | 259 : fSide(kNeither_Side) |
333 , fHead(nullptr) | 260 , fHead(nullptr) |
334 , fTail(nullptr) | 261 , fTail(nullptr) |
335 , fPrev(nullptr) | 262 , fPrev(nullptr) |
336 , fNext(nullptr) {} | 263 , fNext(nullptr) {} |
337 Side fSide; | 264 Side fSide; |
338 Vertex* fHead; | 265 TessellatorVertex* fHead; |
339 Vertex* fTail; | 266 TessellatorVertex* fTail; |
340 MonotonePoly* fPrev; | 267 MonotonePoly* fPrev; |
341 MonotonePoly* fNext; | 268 MonotonePoly* fNext; |
342 bool addVertex(Vertex* v, Side side, SkChunkAlloc& alloc) { | 269 bool addVertex(TessellatorVertex* v, Side side, SkChunkAlloc& alloc) { |
343 Vertex* newV = ALLOC_NEW(Vertex, (v->fPoint), alloc); | 270 TessellatorVertex* newV = ALLOC_NEW(TessellatorVertex, (v->fPoint), alloc); |
344 bool done = false; | 271 bool done = false; |
345 if (fSide == kNeither_Side) { | 272 if (fSide == kNeither_Side) { |
346 fSide = side; | 273 fSide = side; |
347 } else { | 274 } else { |
348 done = side != fSide; | 275 done = side != fSide; |
349 } | 276 } |
350 if (fHead == nullptr) { | 277 if (fHead == nullptr) { |
351 fHead = fTail = newV; | 278 fHead = fTail = newV; |
352 } else if (fSide == kRight_Side) { | 279 } else if (fSide == kRight_Side) { |
353 newV->fPrev = fTail; | 280 newV->fPrev = fTail; |
354 fTail->fNext = newV; | 281 fTail->fNext = newV; |
355 fTail = newV; | 282 fTail = newV; |
356 } else { | 283 } else { |
357 newV->fNext = fHead; | 284 newV->fNext = fHead; |
358 fHead->fPrev = newV; | 285 fHead->fPrev = newV; |
359 fHead = newV; | 286 fHead = newV; |
360 } | 287 } |
361 return done; | 288 return done; |
362 } | 289 } |
363 | 290 |
364 SkPoint* emit(SkPoint* data) { | 291 SkPoint* emit(int winding, SkPoint* data) { |
365 Vertex* first = fHead; | 292 TessellatorVertex* first = fHead; |
366 Vertex* v = first->fNext; | 293 TessellatorVertex* v = first->fNext; |
367 while (v != fTail) { | 294 while (v != fTail) { |
368 SkASSERT(v && v->fPrev && v->fNext); | 295 SkASSERT(v && v->fPrev && v->fNext); |
369 Vertex* prev = v->fPrev; | 296 TessellatorVertex* prev = v->fPrev; |
370 Vertex* curr = v; | 297 TessellatorVertex* curr = v; |
371 Vertex* next = v->fNext; | 298 TessellatorVertex* next = v->fNext; |
372 double ax = static_cast<double>(curr->fPoint.fX) - prev->fPoint. fX; | 299 double ax = static_cast<double>(curr->fPoint.fX) - prev->fPoint. fX; |
373 double ay = static_cast<double>(curr->fPoint.fY) - prev->fPoint. fY; | 300 double ay = static_cast<double>(curr->fPoint.fY) - prev->fPoint. fY; |
374 double bx = static_cast<double>(next->fPoint.fX) - curr->fPoint. fX; | 301 double bx = static_cast<double>(next->fPoint.fX) - curr->fPoint. fX; |
375 double by = static_cast<double>(next->fPoint.fY) - curr->fPoint. fY; | 302 double by = static_cast<double>(next->fPoint.fY) - curr->fPoint. fY; |
376 if (ax * by - ay * bx >= 0.0) { | 303 if (ax * by - ay * bx >= 0.0) { |
377 data = emit_triangle(prev, curr, next, data); | 304 data = emit_triangle(prev, curr, next, data); |
378 v->fPrev->fNext = v->fNext; | 305 v->fPrev->fNext = v->fNext; |
379 v->fNext->fPrev = v->fPrev; | 306 v->fNext->fPrev = v->fPrev; |
380 if (v->fPrev == first) { | 307 if (v->fPrev == first) { |
381 v = v->fNext; | 308 v = v->fNext; |
382 } else { | 309 } else { |
383 v = v->fPrev; | 310 v = v->fPrev; |
384 } | 311 } |
385 } else { | 312 } else { |
386 v = v->fNext; | 313 v = v->fNext; |
387 } | 314 } |
388 } | 315 } |
389 return data; | 316 return data; |
390 } | 317 } |
391 }; | 318 }; |
392 Poly* addVertex(Vertex* v, Side side, SkChunkAlloc& alloc) { | 319 Poly* addVertex(TessellatorVertex* v, Side side, SkChunkAlloc& alloc) { |
393 LOG("addVertex() to %d at %g (%g, %g), %s side\n", fID, v->fID, v->fPoin t.fX, v->fPoint.fY, | 320 LOG("addVertex() to %d at %g (%g, %g), %s side\n", fID, v->fID, v->fPoin t.fX, v->fPoint.fY, |
394 side == kLeft_Side ? "left" : side == kRight_Side ? "right" : "ne ither"); | 321 side == kLeft_Side ? "left" : side == kRight_Side ? "right" : "ne ither"); |
395 Poly* partner = fPartner; | 322 Poly* partner = fPartner; |
396 Poly* poly = this; | 323 Poly* poly = this; |
397 if (partner) { | 324 if (partner) { |
398 fPartner = partner->fPartner = nullptr; | 325 fPartner = partner->fPartner = nullptr; |
399 } | 326 } |
400 if (!fActive) { | 327 if (!fActive) { |
401 fActive = ALLOC_NEW(MonotonePoly, (), alloc); | 328 fActive = ALLOC_NEW(MonotonePoly, (), alloc); |
402 } | 329 } |
403 if (fActive->addVertex(v, side, alloc)) { | 330 if (fActive->addVertex(v, side, alloc)) { |
404 if (fTail) { | 331 if (fTail) { |
405 fActive->fPrev = fTail; | 332 fActive->fPrev = fTail; |
406 fTail->fNext = fActive; | 333 fTail->fNext = fActive; |
407 fTail = fActive; | 334 fTail = fActive; |
408 } else { | 335 } else { |
409 fHead = fTail = fActive; | 336 fHead = fTail = fActive; |
410 } | 337 } |
411 if (partner) { | 338 if (partner) { |
412 partner->addVertex(v, side, alloc); | 339 partner->addVertex(v, side, alloc); |
413 poly = partner; | 340 poly = partner; |
414 } else { | 341 } else { |
415 Vertex* prev = fActive->fSide == Poly::kLeft_Side ? | 342 TessellatorVertex* prev = fActive->fSide == Poly::kLeft_Side ? |
416 fActive->fHead->fNext : fActive->fTail->fPrev; | 343 fActive->fHead->fNext : fActive->fTail->fPrev; |
417 fActive = ALLOC_NEW(MonotonePoly, , alloc); | 344 fActive = ALLOC_NEW(MonotonePoly, , alloc); |
418 fActive->addVertex(prev, Poly::kNeither_Side, alloc); | 345 fActive->addVertex(prev, Poly::kNeither_Side, alloc); |
419 fActive->addVertex(v, side, alloc); | 346 fActive->addVertex(v, side, alloc); |
420 } | 347 } |
421 } | 348 } |
422 fCount++; | 349 fCount++; |
423 return poly; | 350 return poly; |
424 } | 351 } |
425 void end(Vertex* v, SkChunkAlloc& alloc) { | 352 void end(TessellatorVertex* v, SkChunkAlloc& alloc) { |
426 LOG("end() %d at %g, %g\n", fID, v->fPoint.fX, v->fPoint.fY); | 353 LOG("end() %d at %g, %g\n", fID, v->fPoint.fX, v->fPoint.fY); |
427 if (fPartner) { | 354 if (fPartner) { |
428 fPartner = fPartner->fPartner = nullptr; | 355 fPartner = fPartner->fPartner = nullptr; |
429 } | 356 } |
430 addVertex(v, fActive->fSide == kLeft_Side ? kRight_Side : kLeft_Side, al loc); | 357 addVertex(v, fActive->fSide == kLeft_Side ? kRight_Side : kLeft_Side, al loc); |
431 } | 358 } |
432 SkPoint* emit(SkPoint *data) { | 359 SkPoint* emit(SkPoint *data) { |
433 if (fCount < 3) { | 360 if (fCount < 3) { |
434 return data; | 361 return data; |
435 } | 362 } |
436 LOG("emit() %d, size %d\n", fID, fCount); | 363 LOG("emit() %d, size %d\n", fID, fCount); |
437 for (MonotonePoly* m = fHead; m != nullptr; m = m->fNext) { | 364 for (MonotonePoly* m = fHead; m != nullptr; m = m->fNext) { |
438 data = m->emit(data); | 365 data = m->emit(fWinding, data); |
439 } | 366 } |
440 return data; | 367 return data; |
441 } | 368 } |
442 int fWinding; | 369 int fWinding; |
443 MonotonePoly* fHead; | 370 MonotonePoly* fHead; |
444 MonotonePoly* fTail; | 371 MonotonePoly* fTail; |
445 MonotonePoly* fActive; | 372 MonotonePoly* fActive; |
446 Poly* fNext; | 373 Poly* fNext; |
447 Poly* fPartner; | 374 Poly* fPartner; |
448 int fCount; | 375 int fCount; |
449 #if LOGGING_ENABLED | 376 #if TESSELLATOR_LOGGING_ENABLED |
450 int fID; | 377 int fID; |
451 #endif | 378 #endif |
452 }; | 379 }; |
453 | 380 |
454 /******************************************************************************* ********/ | 381 /******************************************************************************* ********/ |
455 | 382 |
456 bool coincident(const SkPoint& a, const SkPoint& b) { | 383 bool coincident(const SkPoint& a, const SkPoint& b) { |
457 return a == b; | 384 return a == b; |
458 } | 385 } |
459 | 386 |
460 Poly* new_poly(Poly** head, Vertex* v, int winding, SkChunkAlloc& alloc) { | 387 Poly* new_poly(Poly** head, TessellatorVertex* v, int winding, SkChunkAlloc& all oc) { |
461 Poly* poly = ALLOC_NEW(Poly, (winding), alloc); | 388 Poly* poly = ALLOC_NEW(Poly, (winding), alloc); |
462 poly->addVertex(v, Poly::kNeither_Side, alloc); | 389 poly->addVertex(v, Poly::kNeither_Side, alloc); |
463 poly->fNext = *head; | 390 poly->fNext = *head; |
464 *head = poly; | 391 *head = poly; |
465 return poly; | 392 return poly; |
466 } | 393 } |
467 | 394 |
468 Vertex* append_point_to_contour(const SkPoint& p, Vertex* prev, Vertex** head, | 395 TessellatorVertex* append_point_to_contour(const SkPoint& p, TessellatorVertex* prev, |
469 SkChunkAlloc& alloc) { | 396 TessellatorVertex** head, SkChunkAllo c& alloc) { |
470 Vertex* v = ALLOC_NEW(Vertex, (p), alloc); | 397 TessellatorVertex* v = ALLOC_NEW(TessellatorVertex, (p), alloc); |
471 #if LOGGING_ENABLED | 398 #if TESSELLATOR_LOGGING_ENABLED |
472 static float gID = 0.0f; | 399 static float gID = 0.0f; |
473 v->fID = gID++; | 400 v->fID = gID++; |
474 #endif | 401 #endif |
475 if (prev) { | 402 if (prev) { |
476 prev->fNext = v; | 403 prev->fNext = v; |
477 v->fPrev = prev; | 404 v->fPrev = prev; |
478 } else { | 405 } else { |
479 *head = v; | 406 *head = v; |
480 } | 407 } |
481 return v; | 408 return v; |
482 } | 409 } |
483 | 410 |
484 Vertex* generate_quadratic_points(const SkPoint& p0, | 411 TessellatorVertex* generate_quadratic_points(const SkPoint& p0, |
485 const SkPoint& p1, | 412 const SkPoint& p1, |
486 const SkPoint& p2, | 413 const SkPoint& p2, |
487 SkScalar tolSqd, | 414 SkScalar tolSqd, |
488 Vertex* prev, | 415 TessellatorVertex* prev, |
489 Vertex** head, | 416 TessellatorVertex** head, |
490 int pointsLeft, | 417 int pointsLeft, |
491 SkChunkAlloc& alloc) { | 418 SkChunkAlloc& alloc) { |
492 SkScalar d = p1.distanceToLineSegmentBetweenSqd(p0, p2); | 419 SkScalar d = p1.distanceToLineSegmentBetweenSqd(p0, p2); |
493 if (pointsLeft < 2 || d < tolSqd || !SkScalarIsFinite(d)) { | 420 if (pointsLeft < 2 || d < tolSqd || !SkScalarIsFinite(d)) { |
494 return append_point_to_contour(p2, prev, head, alloc); | 421 return append_point_to_contour(p2, prev, head, alloc); |
495 } | 422 } |
496 | 423 |
497 const SkPoint q[] = { | 424 const SkPoint q[] = { |
498 { SkScalarAve(p0.fX, p1.fX), SkScalarAve(p0.fY, p1.fY) }, | 425 { SkScalarAve(p0.fX, p1.fX), SkScalarAve(p0.fY, p1.fY) }, |
499 { SkScalarAve(p1.fX, p2.fX), SkScalarAve(p1.fY, p2.fY) }, | 426 { SkScalarAve(p1.fX, p2.fX), SkScalarAve(p1.fY, p2.fY) }, |
500 }; | 427 }; |
501 const SkPoint r = { SkScalarAve(q[0].fX, q[1].fX), SkScalarAve(q[0].fY, q[1] .fY) }; | 428 const SkPoint r = { SkScalarAve(q[0].fX, q[1].fX), SkScalarAve(q[0].fY, q[1] .fY) }; |
502 | 429 |
503 pointsLeft >>= 1; | 430 pointsLeft >>= 1; |
504 prev = generate_quadratic_points(p0, q[0], r, tolSqd, prev, head, pointsLeft , alloc); | 431 prev = generate_quadratic_points(p0, q[0], r, tolSqd, prev, head, pointsLeft , alloc); |
505 prev = generate_quadratic_points(r, q[1], p2, tolSqd, prev, head, pointsLeft , alloc); | 432 prev = generate_quadratic_points(r, q[1], p2, tolSqd, prev, head, pointsLeft , alloc); |
506 return prev; | 433 return prev; |
507 } | 434 } |
508 | 435 |
509 Vertex* generate_cubic_points(const SkPoint& p0, | 436 TessellatorVertex* generate_cubic_points(const SkPoint& p0, |
510 const SkPoint& p1, | 437 const SkPoint& p1, |
511 const SkPoint& p2, | 438 const SkPoint& p2, |
512 const SkPoint& p3, | 439 const SkPoint& p3, |
513 SkScalar tolSqd, | 440 SkScalar tolSqd, |
514 Vertex* prev, | 441 TessellatorVertex* prev, |
515 Vertex** head, | 442 TessellatorVertex** head, |
516 int pointsLeft, | 443 int pointsLeft, |
517 SkChunkAlloc& alloc) { | 444 SkChunkAlloc& alloc) { |
518 SkScalar d1 = p1.distanceToLineSegmentBetweenSqd(p0, p3); | 445 SkScalar d1 = p1.distanceToLineSegmentBetweenSqd(p0, p3); |
519 SkScalar d2 = p2.distanceToLineSegmentBetweenSqd(p0, p3); | 446 SkScalar d2 = p2.distanceToLineSegmentBetweenSqd(p0, p3); |
520 if (pointsLeft < 2 || (d1 < tolSqd && d2 < tolSqd) || | 447 if (pointsLeft < 2 || (d1 < tolSqd && d2 < tolSqd) || |
521 !SkScalarIsFinite(d1) || !SkScalarIsFinite(d2)) { | 448 !SkScalarIsFinite(d1) || !SkScalarIsFinite(d2)) { |
522 return append_point_to_contour(p3, prev, head, alloc); | 449 return append_point_to_contour(p3, prev, head, alloc); |
523 } | 450 } |
524 const SkPoint q[] = { | 451 const SkPoint q[] = { |
525 { SkScalarAve(p0.fX, p1.fX), SkScalarAve(p0.fY, p1.fY) }, | 452 { SkScalarAve(p0.fX, p1.fX), SkScalarAve(p0.fY, p1.fY) }, |
526 { SkScalarAve(p1.fX, p2.fX), SkScalarAve(p1.fY, p2.fY) }, | 453 { SkScalarAve(p1.fX, p2.fX), SkScalarAve(p1.fY, p2.fY) }, |
527 { SkScalarAve(p2.fX, p3.fX), SkScalarAve(p2.fY, p3.fY) } | 454 { SkScalarAve(p2.fX, p3.fX), SkScalarAve(p2.fY, p3.fY) } |
528 }; | 455 }; |
529 const SkPoint r[] = { | 456 const SkPoint r[] = { |
530 { SkScalarAve(q[0].fX, q[1].fX), SkScalarAve(q[0].fY, q[1].fY) }, | 457 { SkScalarAve(q[0].fX, q[1].fX), SkScalarAve(q[0].fY, q[1].fY) }, |
531 { SkScalarAve(q[1].fX, q[2].fX), SkScalarAve(q[1].fY, q[2].fY) } | 458 { SkScalarAve(q[1].fX, q[2].fX), SkScalarAve(q[1].fY, q[2].fY) } |
532 }; | 459 }; |
533 const SkPoint s = { SkScalarAve(r[0].fX, r[1].fX), SkScalarAve(r[0].fY, r[1] .fY) }; | 460 const SkPoint s = { SkScalarAve(r[0].fX, r[1].fX), SkScalarAve(r[0].fY, r[1] .fY) }; |
534 pointsLeft >>= 1; | 461 pointsLeft >>= 1; |
535 prev = generate_cubic_points(p0, q[0], r[0], s, tolSqd, prev, head, pointsLe ft, alloc); | 462 prev = generate_cubic_points(p0, q[0], r[0], s, tolSqd, prev, head, pointsLe ft, alloc); |
536 prev = generate_cubic_points(s, r[1], q[2], p3, tolSqd, prev, head, pointsLe ft, alloc); | 463 prev = generate_cubic_points(s, r[1], q[2], p3, tolSqd, prev, head, pointsLe ft, alloc); |
537 return prev; | 464 return prev; |
538 } | 465 } |
539 | 466 |
540 // Stage 1: convert the input path to a set of linear contours (linked list of V ertices). | 467 // Stage 1: convert the input path to a set of linear contours (linked list of V ertices). |
541 | 468 |
542 void path_to_contours(const SkPath& path, SkScalar tolerance, const SkRect& clip Bounds, | 469 void path_to_contours(const SkPath& path, SkScalar tolerance, const SkRect& clip Bounds, |
543 Vertex** contours, SkChunkAlloc& alloc, bool *isLinear) { | 470 TessellatorVertex** contours, SkChunkAlloc& alloc, bool *i sLinear) { |
544 | |
545 SkScalar toleranceSqd = tolerance * tolerance; | 471 SkScalar toleranceSqd = tolerance * tolerance; |
546 | 472 |
547 SkPoint pts[4]; | 473 SkPoint pts[4]; |
548 bool done = false; | 474 bool done = false; |
549 *isLinear = true; | 475 *isLinear = true; |
550 SkPath::Iter iter(path, false); | 476 SkPath::Iter iter(path, false); |
551 Vertex* prev = nullptr; | 477 TessellatorVertex* prev = nullptr; |
552 Vertex* head = nullptr; | 478 TessellatorVertex* head = nullptr; |
553 if (path.isInverseFillType()) { | 479 if (path.isInverseFillType()) { |
554 SkPoint quad[4]; | 480 SkPoint quad[4]; |
555 clipBounds.toQuad(quad); | 481 clipBounds.toQuad(quad); |
556 for (int i = 3; i >= 0; i--) { | 482 for (int i = 3; i >= 0; i--) { |
557 prev = append_point_to_contour(quad[i], prev, &head, alloc); | 483 prev = append_point_to_contour(quad[i], prev, &head, alloc); |
558 } | 484 } |
559 head->fPrev = prev; | 485 head->fPrev = prev; |
560 prev->fNext = head; | 486 prev->fNext = head; |
561 *contours++ = head; | 487 *contours++ = head; |
562 head = prev = nullptr; | 488 head = prev = nullptr; |
(...skipping 70 matching lines...) Expand 10 before | Expand all | Expand 10 after Loading... | |
633 case SkPath::kInverseWinding_FillType: | 559 case SkPath::kInverseWinding_FillType: |
634 return winding == 1; | 560 return winding == 1; |
635 case SkPath::kInverseEvenOdd_FillType: | 561 case SkPath::kInverseEvenOdd_FillType: |
636 return (winding & 1) == 1; | 562 return (winding & 1) == 1; |
637 default: | 563 default: |
638 SkASSERT(false); | 564 SkASSERT(false); |
639 return false; | 565 return false; |
640 } | 566 } |
641 } | 567 } |
642 | 568 |
643 Edge* new_edge(Vertex* prev, Vertex* next, SkChunkAlloc& alloc, Comparator& c) { | 569 Edge* new_edge(TessellatorVertex* prev, TessellatorVertex* next, SkChunkAlloc& a lloc, |
570 Comparator& c) { | |
644 int winding = c.sweep_lt(prev->fPoint, next->fPoint) ? 1 : -1; | 571 int winding = c.sweep_lt(prev->fPoint, next->fPoint) ? 1 : -1; |
645 Vertex* top = winding < 0 ? next : prev; | 572 TessellatorVertex* top = winding < 0 ? next : prev; |
646 Vertex* bottom = winding < 0 ? prev : next; | 573 TessellatorVertex* bottom = winding < 0 ? prev : next; |
647 return ALLOC_NEW(Edge, (top, bottom, winding), alloc); | 574 return ALLOC_NEW(Edge, (top, bottom, winding), alloc); |
648 } | 575 } |
649 | 576 |
650 void remove_edge(Edge* edge, EdgeList* edges) { | 577 void remove_edge(Edge* edge, EdgeList* edges) { |
651 LOG("removing edge %g -> %g\n", edge->fTop->fID, edge->fBottom->fID); | 578 LOG("removing edge %g -> %g\n", edge->fTop->fID, edge->fBottom->fID); |
652 SkASSERT(edge->isActive(edges)); | 579 SkASSERT(edge->isActive(edges)); |
653 remove<Edge, &Edge::fLeft, &Edge::fRight>(edge, &edges->fHead, &edges->fTail ); | 580 remove<Edge, &Edge::fLeft, &Edge::fRight>(edge, &edges->fHead, &edges->fTail ); |
654 } | 581 } |
655 | 582 |
656 void insert_edge(Edge* edge, Edge* prev, EdgeList* edges) { | 583 void insert_edge(Edge* edge, Edge* prev, EdgeList* edges) { |
657 LOG("inserting edge %g -> %g\n", edge->fTop->fID, edge->fBottom->fID); | 584 LOG("inserting edge %g -> %g\n", edge->fTop->fID, edge->fBottom->fID); |
658 SkASSERT(!edge->isActive(edges)); | 585 SkASSERT(!edge->isActive(edges)); |
659 Edge* next = prev ? prev->fRight : edges->fHead; | 586 Edge* next = prev ? prev->fRight : edges->fHead; |
660 insert<Edge, &Edge::fLeft, &Edge::fRight>(edge, prev, next, &edges->fHead, & edges->fTail); | 587 insert<Edge, &Edge::fLeft, &Edge::fRight>(edge, prev, next, &edges->fHead, & edges->fTail); |
661 } | 588 } |
662 | 589 |
663 void find_enclosing_edges(Vertex* v, EdgeList* edges, Edge** left, Edge** right) { | 590 void find_enclosing_edges(TessellatorVertex* v, EdgeList* edges, Edge** left, Ed ge** right) { |
664 if (v->fFirstEdgeAbove) { | 591 if (v->fFirstEdgeAbove) { |
665 *left = v->fFirstEdgeAbove->fLeft; | 592 *left = v->fFirstEdgeAbove->fLeft; |
666 *right = v->fLastEdgeAbove->fRight; | 593 *right = v->fLastEdgeAbove->fRight; |
667 return; | 594 return; |
668 } | 595 } |
669 Edge* next = nullptr; | 596 Edge* next = nullptr; |
670 Edge* prev; | 597 Edge* prev; |
671 for (prev = edges->fTail; prev != nullptr; prev = prev->fLeft) { | 598 for (prev = edges->fTail; prev != nullptr; prev = prev->fLeft) { |
672 if (prev->isLeftOf(v)) { | 599 if (prev->isLeftOf(v)) { |
673 break; | 600 break; |
(...skipping 30 matching lines...) Expand all Loading... | |
704 remove_edge(edge, activeEdges); | 631 remove_edge(edge, activeEdges); |
705 } | 632 } |
706 } else if (edge->fTop->fProcessed && !edge->fBottom->fProcessed) { | 633 } else if (edge->fTop->fProcessed && !edge->fBottom->fProcessed) { |
707 Edge* left; | 634 Edge* left; |
708 Edge* right; | 635 Edge* right; |
709 find_enclosing_edges(edge, activeEdges, c, &left, &right); | 636 find_enclosing_edges(edge, activeEdges, c, &left, &right); |
710 insert_edge(edge, left, activeEdges); | 637 insert_edge(edge, left, activeEdges); |
711 } | 638 } |
712 } | 639 } |
713 | 640 |
714 void insert_edge_above(Edge* edge, Vertex* v, Comparator& c) { | 641 void insert_edge_above(Edge* edge, TessellatorVertex* v, Comparator& c) { |
715 if (edge->fTop->fPoint == edge->fBottom->fPoint || | 642 if (edge->fTop->fPoint == edge->fBottom->fPoint || |
716 c.sweep_gt(edge->fTop->fPoint, edge->fBottom->fPoint)) { | 643 c.sweep_gt(edge->fTop->fPoint, edge->fBottom->fPoint)) { |
717 return; | 644 return; |
718 } | 645 } |
719 LOG("insert edge (%g -> %g) above vertex %g\n", edge->fTop->fID, edge->fBott om->fID, v->fID); | 646 LOG("insert edge (%g -> %g) above vertex %g\n", edge->fTop->fID, edge->fBott om->fID, v->fID); |
720 Edge* prev = nullptr; | 647 Edge* prev = nullptr; |
721 Edge* next; | 648 Edge* next; |
722 for (next = v->fFirstEdgeAbove; next; next = next->fNextEdgeAbove) { | 649 for (next = v->fFirstEdgeAbove; next; next = next->fNextEdgeAbove) { |
723 if (next->isRightOf(edge->fTop)) { | 650 if (next->isRightOf(edge->fTop)) { |
724 break; | 651 break; |
725 } | 652 } |
726 prev = next; | 653 prev = next; |
727 } | 654 } |
728 insert<Edge, &Edge::fPrevEdgeAbove, &Edge::fNextEdgeAbove>( | 655 insert<Edge, &Edge::fPrevEdgeAbove, &Edge::fNextEdgeAbove>( |
729 edge, prev, next, &v->fFirstEdgeAbove, &v->fLastEdgeAbove); | 656 edge, prev, next, &v->fFirstEdgeAbove, &v->fLastEdgeAbove); |
730 } | 657 } |
731 | 658 |
732 void insert_edge_below(Edge* edge, Vertex* v, Comparator& c) { | 659 void insert_edge_below(Edge* edge, TessellatorVertex* v, Comparator& c) { |
733 if (edge->fTop->fPoint == edge->fBottom->fPoint || | 660 if (edge->fTop->fPoint == edge->fBottom->fPoint || |
734 c.sweep_gt(edge->fTop->fPoint, edge->fBottom->fPoint)) { | 661 c.sweep_gt(edge->fTop->fPoint, edge->fBottom->fPoint)) { |
735 return; | 662 return; |
736 } | 663 } |
737 LOG("insert edge (%g -> %g) below vertex %g\n", edge->fTop->fID, edge->fBott om->fID, v->fID); | 664 LOG("insert edge (%g -> %g) below vertex %g\n", edge->fTop->fID, edge->fBott om->fID, v->fID); |
738 Edge* prev = nullptr; | 665 Edge* prev = nullptr; |
739 Edge* next; | 666 Edge* next; |
740 for (next = v->fFirstEdgeBelow; next; next = next->fNextEdgeBelow) { | 667 for (next = v->fFirstEdgeBelow; next; next = next->fNextEdgeBelow) { |
741 if (next->isRightOf(edge->fBottom)) { | 668 if (next->isRightOf(edge->fBottom)) { |
742 break; | 669 break; |
(...skipping 25 matching lines...) Expand all Loading... | |
768 LOG("erasing edge (%g -> %g)\n", edge->fTop->fID, edge->fBottom->fID); | 695 LOG("erasing edge (%g -> %g)\n", edge->fTop->fID, edge->fBottom->fID); |
769 remove_edge_above(edge); | 696 remove_edge_above(edge); |
770 remove_edge_below(edge); | 697 remove_edge_below(edge); |
771 if (edge->isActive(edges)) { | 698 if (edge->isActive(edges)) { |
772 remove_edge(edge, edges); | 699 remove_edge(edge, edges); |
773 } | 700 } |
774 } | 701 } |
775 | 702 |
776 void merge_collinear_edges(Edge* edge, EdgeList* activeEdges, Comparator& c); | 703 void merge_collinear_edges(Edge* edge, EdgeList* activeEdges, Comparator& c); |
777 | 704 |
778 void set_top(Edge* edge, Vertex* v, EdgeList* activeEdges, Comparator& c) { | 705 void set_top(Edge* edge, TessellatorVertex* v, EdgeList* activeEdges, Comparator & c) { |
779 remove_edge_below(edge); | 706 remove_edge_below(edge); |
780 edge->fTop = v; | 707 edge->fTop = v; |
781 edge->recompute(); | 708 edge->recompute(); |
782 insert_edge_below(edge, v, c); | 709 insert_edge_below(edge, v, c); |
783 fix_active_state(edge, activeEdges, c); | 710 fix_active_state(edge, activeEdges, c); |
784 merge_collinear_edges(edge, activeEdges, c); | 711 merge_collinear_edges(edge, activeEdges, c); |
785 } | 712 } |
786 | 713 |
787 void set_bottom(Edge* edge, Vertex* v, EdgeList* activeEdges, Comparator& c) { | 714 void set_bottom(Edge* edge, TessellatorVertex* v, EdgeList* activeEdges, Compara tor& c) { |
788 remove_edge_above(edge); | 715 remove_edge_above(edge); |
789 edge->fBottom = v; | 716 edge->fBottom = v; |
790 edge->recompute(); | 717 edge->recompute(); |
791 insert_edge_above(edge, v, c); | 718 insert_edge_above(edge, v, c); |
792 fix_active_state(edge, activeEdges, c); | 719 fix_active_state(edge, activeEdges, c); |
793 merge_collinear_edges(edge, activeEdges, c); | 720 merge_collinear_edges(edge, activeEdges, c); |
794 } | 721 } |
795 | 722 |
796 void merge_edges_above(Edge* edge, Edge* other, EdgeList* activeEdges, Comparato r& c) { | 723 void merge_edges_above(Edge* edge, Edge* other, EdgeList* activeEdges, Comparato r& c) { |
797 if (coincident(edge->fTop->fPoint, other->fTop->fPoint)) { | 724 if (coincident(edge->fTop->fPoint, other->fTop->fPoint)) { |
(...skipping 45 matching lines...) Expand 10 before | Expand all | Expand 10 after Loading... | |
843 } | 770 } |
844 if (edge->fPrevEdgeBelow && (edge->fBottom == edge->fPrevEdgeBelow->fBottom || | 771 if (edge->fPrevEdgeBelow && (edge->fBottom == edge->fPrevEdgeBelow->fBottom || |
845 !edge->fPrevEdgeBelow->isLeftOf(edge->fBottom)) ) { | 772 !edge->fPrevEdgeBelow->isLeftOf(edge->fBottom)) ) { |
846 merge_edges_below(edge, edge->fPrevEdgeBelow, activeEdges, c); | 773 merge_edges_below(edge, edge->fPrevEdgeBelow, activeEdges, c); |
847 } else if (edge->fNextEdgeBelow && (edge->fBottom == edge->fNextEdgeBelow->f Bottom || | 774 } else if (edge->fNextEdgeBelow && (edge->fBottom == edge->fNextEdgeBelow->f Bottom || |
848 !edge->isLeftOf(edge->fNextEdgeBelow->fB ottom))) { | 775 !edge->isLeftOf(edge->fNextEdgeBelow->fB ottom))) { |
849 merge_edges_below(edge, edge->fNextEdgeBelow, activeEdges, c); | 776 merge_edges_below(edge, edge->fNextEdgeBelow, activeEdges, c); |
850 } | 777 } |
851 } | 778 } |
852 | 779 |
853 void split_edge(Edge* edge, Vertex* v, EdgeList* activeEdges, Comparator& c, SkC hunkAlloc& alloc); | 780 void split_edge(Edge* edge, TessellatorVertex* v, EdgeList* activeEdges, Compara tor& c, |
781 SkChunkAlloc& alloc); | |
854 | 782 |
855 void cleanup_active_edges(Edge* edge, EdgeList* activeEdges, Comparator& c, SkCh unkAlloc& alloc) { | 783 void cleanup_active_edges(Edge* edge, EdgeList* activeEdges, Comparator& c, SkCh unkAlloc& alloc) { |
856 Vertex* top = edge->fTop; | 784 TessellatorVertex* top = edge->fTop; |
857 Vertex* bottom = edge->fBottom; | 785 TessellatorVertex* bottom = edge->fBottom; |
858 if (edge->fLeft) { | 786 if (edge->fLeft) { |
859 Vertex* leftTop = edge->fLeft->fTop; | 787 TessellatorVertex* leftTop = edge->fLeft->fTop; |
860 Vertex* leftBottom = edge->fLeft->fBottom; | 788 TessellatorVertex* leftBottom = edge->fLeft->fBottom; |
861 if (c.sweep_gt(top->fPoint, leftTop->fPoint) && !edge->fLeft->isLeftOf(t op)) { | 789 if (c.sweep_gt(top->fPoint, leftTop->fPoint) && !edge->fLeft->isLeftOf(t op)) { |
862 split_edge(edge->fLeft, edge->fTop, activeEdges, c, alloc); | 790 split_edge(edge->fLeft, edge->fTop, activeEdges, c, alloc); |
863 } else if (c.sweep_gt(leftTop->fPoint, top->fPoint) && !edge->isRightOf( leftTop)) { | 791 } else if (c.sweep_gt(leftTop->fPoint, top->fPoint) && !edge->isRightOf( leftTop)) { |
864 split_edge(edge, leftTop, activeEdges, c, alloc); | 792 split_edge(edge, leftTop, activeEdges, c, alloc); |
865 } else if (c.sweep_lt(bottom->fPoint, leftBottom->fPoint) && | 793 } else if (c.sweep_lt(bottom->fPoint, leftBottom->fPoint) && |
866 !edge->fLeft->isLeftOf(bottom)) { | 794 !edge->fLeft->isLeftOf(bottom)) { |
867 split_edge(edge->fLeft, bottom, activeEdges, c, alloc); | 795 split_edge(edge->fLeft, bottom, activeEdges, c, alloc); |
868 } else if (c.sweep_lt(leftBottom->fPoint, bottom->fPoint) && !edge->isRi ghtOf(leftBottom)) { | 796 } else if (c.sweep_lt(leftBottom->fPoint, bottom->fPoint) && !edge->isRi ghtOf(leftBottom)) { |
869 split_edge(edge, leftBottom, activeEdges, c, alloc); | 797 split_edge(edge, leftBottom, activeEdges, c, alloc); |
870 } | 798 } |
871 } | 799 } |
872 if (edge->fRight) { | 800 if (edge->fRight) { |
873 Vertex* rightTop = edge->fRight->fTop; | 801 TessellatorVertex* rightTop = edge->fRight->fTop; |
874 Vertex* rightBottom = edge->fRight->fBottom; | 802 TessellatorVertex* rightBottom = edge->fRight->fBottom; |
875 if (c.sweep_gt(top->fPoint, rightTop->fPoint) && !edge->fRight->isRightO f(top)) { | 803 if (c.sweep_gt(top->fPoint, rightTop->fPoint) && !edge->fRight->isRightO f(top)) { |
876 split_edge(edge->fRight, top, activeEdges, c, alloc); | 804 split_edge(edge->fRight, top, activeEdges, c, alloc); |
877 } else if (c.sweep_gt(rightTop->fPoint, top->fPoint) && !edge->isLeftOf( rightTop)) { | 805 } else if (c.sweep_gt(rightTop->fPoint, top->fPoint) && !edge->isLeftOf( rightTop)) { |
878 split_edge(edge, rightTop, activeEdges, c, alloc); | 806 split_edge(edge, rightTop, activeEdges, c, alloc); |
879 } else if (c.sweep_lt(bottom->fPoint, rightBottom->fPoint) && | 807 } else if (c.sweep_lt(bottom->fPoint, rightBottom->fPoint) && |
880 !edge->fRight->isRightOf(bottom)) { | 808 !edge->fRight->isRightOf(bottom)) { |
881 split_edge(edge->fRight, bottom, activeEdges, c, alloc); | 809 split_edge(edge->fRight, bottom, activeEdges, c, alloc); |
882 } else if (c.sweep_lt(rightBottom->fPoint, bottom->fPoint) && | 810 } else if (c.sweep_lt(rightBottom->fPoint, bottom->fPoint) && |
883 !edge->isLeftOf(rightBottom)) { | 811 !edge->isLeftOf(rightBottom)) { |
884 split_edge(edge, rightBottom, activeEdges, c, alloc); | 812 split_edge(edge, rightBottom, activeEdges, c, alloc); |
885 } | 813 } |
886 } | 814 } |
887 } | 815 } |
888 | 816 |
889 void split_edge(Edge* edge, Vertex* v, EdgeList* activeEdges, Comparator& c, SkC hunkAlloc& alloc) { | 817 void split_edge(Edge* edge, TessellatorVertex* v, EdgeList* activeEdges, Compara tor& c, |
818 SkChunkAlloc& alloc) { | |
890 LOG("splitting edge (%g -> %g) at vertex %g (%g, %g)\n", | 819 LOG("splitting edge (%g -> %g) at vertex %g (%g, %g)\n", |
891 edge->fTop->fID, edge->fBottom->fID, | 820 edge->fTop->fID, edge->fBottom->fID, |
892 v->fID, v->fPoint.fX, v->fPoint.fY); | 821 v->fID, v->fPoint.fX, v->fPoint.fY); |
893 if (c.sweep_lt(v->fPoint, edge->fTop->fPoint)) { | 822 if (c.sweep_lt(v->fPoint, edge->fTop->fPoint)) { |
894 set_top(edge, v, activeEdges, c); | 823 set_top(edge, v, activeEdges, c); |
895 } else if (c.sweep_gt(v->fPoint, edge->fBottom->fPoint)) { | 824 } else if (c.sweep_gt(v->fPoint, edge->fBottom->fPoint)) { |
896 set_bottom(edge, v, activeEdges, c); | 825 set_bottom(edge, v, activeEdges, c); |
897 } else { | 826 } else { |
898 Edge* newEdge = ALLOC_NEW(Edge, (v, edge->fBottom, edge->fWinding), allo c); | 827 Edge* newEdge = ALLOC_NEW(Edge, (v, edge->fBottom, edge->fWinding), allo c); |
899 insert_edge_below(newEdge, v, c); | 828 insert_edge_below(newEdge, v, c); |
900 insert_edge_above(newEdge, edge->fBottom, c); | 829 insert_edge_above(newEdge, edge->fBottom, c); |
901 set_bottom(edge, v, activeEdges, c); | 830 set_bottom(edge, v, activeEdges, c); |
902 cleanup_active_edges(edge, activeEdges, c, alloc); | 831 cleanup_active_edges(edge, activeEdges, c, alloc); |
903 fix_active_state(newEdge, activeEdges, c); | 832 fix_active_state(newEdge, activeEdges, c); |
904 merge_collinear_edges(newEdge, activeEdges, c); | 833 merge_collinear_edges(newEdge, activeEdges, c); |
905 } | 834 } |
906 } | 835 } |
907 | 836 |
908 void merge_vertices(Vertex* src, Vertex* dst, Vertex** head, Comparator& c, SkCh unkAlloc& alloc) { | 837 void merge_vertices(TessellatorVertex* src, TessellatorVertex* dst, TessellatorV ertex** head, |
838 Comparator& c, SkChunkAlloc& alloc) { | |
909 LOG("found coincident verts at %g, %g; merging %g into %g\n", src->fPoint.fX , src->fPoint.fY, | 839 LOG("found coincident verts at %g, %g; merging %g into %g\n", src->fPoint.fX , src->fPoint.fY, |
910 src->fID, dst->fID); | 840 src->fID, dst->fID); |
911 for (Edge* edge = src->fFirstEdgeAbove; edge;) { | 841 for (Edge* edge = src->fFirstEdgeAbove; edge;) { |
912 Edge* next = edge->fNextEdgeAbove; | 842 Edge* next = edge->fNextEdgeAbove; |
913 set_bottom(edge, dst, nullptr, c); | 843 set_bottom(edge, dst, nullptr, c); |
914 edge = next; | 844 edge = next; |
915 } | 845 } |
916 for (Edge* edge = src->fFirstEdgeBelow; edge;) { | 846 for (Edge* edge = src->fFirstEdgeBelow; edge;) { |
917 Edge* next = edge->fNextEdgeBelow; | 847 Edge* next = edge->fNextEdgeBelow; |
918 set_top(edge, dst, nullptr, c); | 848 set_top(edge, dst, nullptr, c); |
919 edge = next; | 849 edge = next; |
920 } | 850 } |
921 remove<Vertex, &Vertex::fPrev, &Vertex::fNext>(src, head, nullptr); | 851 remove<TessellatorVertex, &TessellatorVertex::fPrev, &TessellatorVertex::fNe xt>(src, head, |
852 nullptr); | |
922 } | 853 } |
923 | 854 |
924 Vertex* check_for_intersection(Edge* edge, Edge* other, EdgeList* activeEdges, C omparator& c, | 855 TessellatorVertex* check_for_intersection(Edge* edge, Edge* other, EdgeList* act iveEdges, |
925 SkChunkAlloc& alloc) { | 856 Comparator& c, SkChunkAlloc& alloc) { |
926 SkPoint p; | 857 SkPoint p; |
927 if (!edge || !other) { | 858 if (!edge || !other) { |
928 return nullptr; | 859 return nullptr; |
929 } | 860 } |
930 if (edge->intersect(*other, &p)) { | 861 if (edge->intersect(*other, &p)) { |
931 Vertex* v; | 862 TessellatorVertex* v; |
932 LOG("found intersection, pt is %g, %g\n", p.fX, p.fY); | 863 LOG("found intersection, pt is %g, %g\n", p.fX, p.fY); |
933 if (p == edge->fTop->fPoint || c.sweep_lt(p, edge->fTop->fPoint)) { | 864 if (p == edge->fTop->fPoint || c.sweep_lt(p, edge->fTop->fPoint)) { |
934 split_edge(other, edge->fTop, activeEdges, c, alloc); | 865 split_edge(other, edge->fTop, activeEdges, c, alloc); |
935 v = edge->fTop; | 866 v = edge->fTop; |
936 } else if (p == edge->fBottom->fPoint || c.sweep_gt(p, edge->fBottom->fP oint)) { | 867 } else if (p == edge->fBottom->fPoint || c.sweep_gt(p, edge->fBottom->fP oint)) { |
937 split_edge(other, edge->fBottom, activeEdges, c, alloc); | 868 split_edge(other, edge->fBottom, activeEdges, c, alloc); |
938 v = edge->fBottom; | 869 v = edge->fBottom; |
939 } else if (p == other->fTop->fPoint || c.sweep_lt(p, other->fTop->fPoint )) { | 870 } else if (p == other->fTop->fPoint || c.sweep_lt(p, other->fTop->fPoint )) { |
940 split_edge(edge, other->fTop, activeEdges, c, alloc); | 871 split_edge(edge, other->fTop, activeEdges, c, alloc); |
941 v = other->fTop; | 872 v = other->fTop; |
942 } else if (p == other->fBottom->fPoint || c.sweep_gt(p, other->fBottom-> fPoint)) { | 873 } else if (p == other->fBottom->fPoint || c.sweep_gt(p, other->fBottom-> fPoint)) { |
943 split_edge(edge, other->fBottom, activeEdges, c, alloc); | 874 split_edge(edge, other->fBottom, activeEdges, c, alloc); |
944 v = other->fBottom; | 875 v = other->fBottom; |
945 } else { | 876 } else { |
946 Vertex* nextV = edge->fTop; | 877 TessellatorVertex* nextV = edge->fTop; |
947 while (c.sweep_lt(p, nextV->fPoint)) { | 878 while (c.sweep_lt(p, nextV->fPoint)) { |
948 nextV = nextV->fPrev; | 879 nextV = nextV->fPrev; |
949 } | 880 } |
950 while (c.sweep_lt(nextV->fPoint, p)) { | 881 while (c.sweep_lt(nextV->fPoint, p)) { |
951 nextV = nextV->fNext; | 882 nextV = nextV->fNext; |
952 } | 883 } |
953 Vertex* prevV = nextV->fPrev; | 884 TessellatorVertex* prevV = nextV->fPrev; |
954 if (coincident(prevV->fPoint, p)) { | 885 if (coincident(prevV->fPoint, p)) { |
955 v = prevV; | 886 v = prevV; |
956 } else if (coincident(nextV->fPoint, p)) { | 887 } else if (coincident(nextV->fPoint, p)) { |
957 v = nextV; | 888 v = nextV; |
958 } else { | 889 } else { |
959 v = ALLOC_NEW(Vertex, (p), alloc); | 890 v = ALLOC_NEW(TessellatorVertex, (p), alloc); |
960 LOG("inserting between %g (%g, %g) and %g (%g, %g)\n", | 891 LOG("inserting between %g (%g, %g) and %g (%g, %g)\n", |
961 prevV->fID, prevV->fPoint.fX, prevV->fPoint.fY, | 892 prevV->fID, prevV->fPoint.fX, prevV->fPoint.fY, |
962 nextV->fID, nextV->fPoint.fX, nextV->fPoint.fY); | 893 nextV->fID, nextV->fPoint.fX, nextV->fPoint.fY); |
963 #if LOGGING_ENABLED | 894 #if TESSELLATOR_LOGGING_ENABLED |
964 v->fID = (nextV->fID + prevV->fID) * 0.5f; | 895 v->fID = (nextV->fID + prevV->fID) * 0.5f; |
965 #endif | 896 #endif |
966 v->fPrev = prevV; | 897 v->fPrev = prevV; |
967 v->fNext = nextV; | 898 v->fNext = nextV; |
968 prevV->fNext = v; | 899 prevV->fNext = v; |
969 nextV->fPrev = v; | 900 nextV->fPrev = v; |
970 } | 901 } |
971 split_edge(edge, v, activeEdges, c, alloc); | 902 split_edge(edge, v, activeEdges, c, alloc); |
972 split_edge(other, v, activeEdges, c, alloc); | 903 split_edge(other, v, activeEdges, c, alloc); |
973 } | 904 } |
974 return v; | 905 return v; |
975 } | 906 } |
976 return nullptr; | 907 return nullptr; |
977 } | 908 } |
978 | 909 |
979 void sanitize_contours(Vertex** contours, int contourCnt) { | 910 void sanitize_contours(TessellatorVertex** contours, int contourCnt) { |
980 for (int i = 0; i < contourCnt; ++i) { | 911 for (int i = 0; i < contourCnt; ++i) { |
981 SkASSERT(contours[i]); | 912 SkASSERT(contours[i]); |
982 for (Vertex* v = contours[i];;) { | 913 for (TessellatorVertex* v = contours[i];;) { |
983 if (coincident(v->fPrev->fPoint, v->fPoint)) { | 914 if (coincident(v->fPrev->fPoint, v->fPoint)) { |
984 LOG("vertex %g,%g coincident; removing\n", v->fPoint.fX, v->fPoi nt.fY); | 915 LOG("vertex %g,%g coincident; removing\n", v->fPoint.fX, v->fPoi nt.fY); |
985 if (v->fPrev == v) { | 916 if (v->fPrev == v) { |
986 contours[i] = nullptr; | 917 contours[i] = nullptr; |
987 break; | 918 break; |
988 } | 919 } |
989 v->fPrev->fNext = v->fNext; | 920 v->fPrev->fNext = v->fNext; |
990 v->fNext->fPrev = v->fPrev; | 921 v->fNext->fPrev = v->fPrev; |
991 if (contours[i] == v) { | 922 if (contours[i] == v) { |
992 contours[i] = v->fNext; | 923 contours[i] = v->fNext; |
993 } | 924 } |
994 v = v->fPrev; | 925 v = v->fPrev; |
995 } else { | 926 } else { |
996 v = v->fNext; | 927 v = v->fNext; |
997 if (v == contours[i]) break; | 928 if (v == contours[i]) break; |
998 } | 929 } |
999 } | 930 } |
1000 } | 931 } |
1001 } | 932 } |
1002 | 933 |
1003 void merge_coincident_vertices(Vertex** vertices, Comparator& c, SkChunkAlloc& a lloc) { | 934 void merge_coincident_vertices(TessellatorVertex** vertices, Comparator& c, SkCh unkAlloc& alloc) { |
1004 for (Vertex* v = (*vertices)->fNext; v != nullptr; v = v->fNext) { | 935 for (TessellatorVertex* v = (*vertices)->fNext; v != nullptr; v = v->fNext) { |
1005 if (c.sweep_lt(v->fPoint, v->fPrev->fPoint)) { | 936 if (c.sweep_lt(v->fPoint, v->fPrev->fPoint)) { |
1006 v->fPoint = v->fPrev->fPoint; | 937 v->fPoint = v->fPrev->fPoint; |
1007 } | 938 } |
1008 if (coincident(v->fPrev->fPoint, v->fPoint)) { | 939 if (coincident(v->fPrev->fPoint, v->fPoint)) { |
1009 merge_vertices(v->fPrev, v, vertices, c, alloc); | 940 merge_vertices(v->fPrev, v, vertices, c, alloc); |
1010 } | 941 } |
1011 } | 942 } |
1012 } | 943 } |
1013 | 944 |
1014 // Stage 2: convert the contours to a mesh of edges connecting the vertices. | 945 // Stage 2: convert the contours to a mesh of edges connecting the vertices. |
1015 | 946 |
1016 Vertex* build_edges(Vertex** contours, int contourCnt, Comparator& c, SkChunkAll oc& alloc) { | 947 TessellatorVertex* build_edges(TessellatorVertex** contours, int contourCnt, Com parator& c, |
1017 Vertex* vertices = nullptr; | 948 SkChunkAlloc& alloc) { |
1018 Vertex* prev = nullptr; | 949 TessellatorVertex* vertices = nullptr; |
950 TessellatorVertex* prev = nullptr; | |
1019 for (int i = 0; i < contourCnt; ++i) { | 951 for (int i = 0; i < contourCnt; ++i) { |
1020 for (Vertex* v = contours[i]; v != nullptr;) { | 952 for (TessellatorVertex* v = contours[i]; v != nullptr;) { |
1021 Vertex* vNext = v->fNext; | 953 TessellatorVertex* vNext = v->fNext; |
1022 Edge* edge = new_edge(v->fPrev, v, alloc, c); | 954 Edge* edge = new_edge(v->fPrev, v, alloc, c); |
1023 if (edge->fWinding > 0) { | 955 if (edge->fWinding > 0) { |
1024 insert_edge_below(edge, v->fPrev, c); | 956 insert_edge_below(edge, v->fPrev, c); |
1025 insert_edge_above(edge, v, c); | 957 insert_edge_above(edge, v, c); |
1026 } else { | 958 } else { |
1027 insert_edge_below(edge, v, c); | 959 insert_edge_below(edge, v, c); |
1028 insert_edge_above(edge, v->fPrev, c); | 960 insert_edge_above(edge, v->fPrev, c); |
1029 } | 961 } |
1030 merge_collinear_edges(edge, nullptr, c); | 962 merge_collinear_edges(edge, nullptr, c); |
1031 if (prev) { | 963 if (prev) { |
1032 prev->fNext = v; | 964 prev->fNext = v; |
1033 v->fPrev = prev; | 965 v->fPrev = prev; |
1034 } else { | 966 } else { |
1035 vertices = v; | 967 vertices = v; |
1036 } | 968 } |
1037 prev = v; | 969 prev = v; |
1038 v = vNext; | 970 v = vNext; |
1039 if (v == contours[i]) break; | 971 if (v == contours[i]) break; |
1040 } | 972 } |
1041 } | 973 } |
1042 if (prev) { | 974 if (prev) { |
1043 prev->fNext = vertices->fPrev = nullptr; | 975 prev->fNext = vertices->fPrev = nullptr; |
1044 } | 976 } |
1045 return vertices; | 977 return vertices; |
1046 } | 978 } |
1047 | 979 |
1048 // Stage 3: sort the vertices by increasing sweep direction. | 980 // Stage 3: sort the vertices by increasing sweep direction. |
1049 | 981 |
1050 Vertex* sorted_merge(Vertex* a, Vertex* b, Comparator& c); | 982 TessellatorVertex* sorted_merge(TessellatorVertex* a, TessellatorVertex* b, Comp arator& c); |
1051 | 983 |
1052 void front_back_split(Vertex* v, Vertex** pFront, Vertex** pBack) { | 984 void front_back_split(TessellatorVertex* v, TessellatorVertex** pFront, Tessella torVertex** pBack) { |
1053 Vertex* fast; | 985 TessellatorVertex* fast; |
1054 Vertex* slow; | 986 TessellatorVertex* slow; |
1055 if (!v || !v->fNext) { | 987 if (!v || !v->fNext) { |
1056 *pFront = v; | 988 *pFront = v; |
1057 *pBack = nullptr; | 989 *pBack = nullptr; |
1058 } else { | 990 } else { |
1059 slow = v; | 991 slow = v; |
1060 fast = v->fNext; | 992 fast = v->fNext; |
1061 | 993 |
1062 while (fast != nullptr) { | 994 while (fast != nullptr) { |
1063 fast = fast->fNext; | 995 fast = fast->fNext; |
1064 if (fast != nullptr) { | 996 if (fast != nullptr) { |
1065 slow = slow->fNext; | 997 slow = slow->fNext; |
1066 fast = fast->fNext; | 998 fast = fast->fNext; |
1067 } | 999 } |
1068 } | 1000 } |
1069 | 1001 |
1070 *pFront = v; | 1002 *pFront = v; |
1071 *pBack = slow->fNext; | 1003 *pBack = slow->fNext; |
1072 slow->fNext->fPrev = nullptr; | 1004 slow->fNext->fPrev = nullptr; |
1073 slow->fNext = nullptr; | 1005 slow->fNext = nullptr; |
1074 } | 1006 } |
1075 } | 1007 } |
1076 | 1008 |
1077 void merge_sort(Vertex** head, Comparator& c) { | 1009 void merge_sort(TessellatorVertex** head, Comparator& c) { |
1078 if (!*head || !(*head)->fNext) { | 1010 if (!*head || !(*head)->fNext) { |
1079 return; | 1011 return; |
1080 } | 1012 } |
1081 | 1013 |
1082 Vertex* a; | 1014 TessellatorVertex* a; |
1083 Vertex* b; | 1015 TessellatorVertex* b; |
1084 front_back_split(*head, &a, &b); | 1016 front_back_split(*head, &a, &b); |
1085 | 1017 |
1086 merge_sort(&a, c); | 1018 merge_sort(&a, c); |
1087 merge_sort(&b, c); | 1019 merge_sort(&b, c); |
1088 | 1020 |
1089 *head = sorted_merge(a, b, c); | 1021 *head = sorted_merge(a, b, c); |
1090 } | 1022 } |
1091 | 1023 |
1092 inline void append_vertex(Vertex* v, Vertex** head, Vertex** tail) { | 1024 inline void append_vertex(TessellatorVertex* v, TessellatorVertex** head, |
1093 insert<Vertex, &Vertex::fPrev, &Vertex::fNext>(v, *tail, nullptr, head, tail ); | 1025 TessellatorVertex** tail) { |
1026 insert<TessellatorVertex, &TessellatorVertex::fPrev, &TessellatorVertex::fNe xt>(v, *tail, | |
1027 nullptr, head, | |
1028 tail); | |
1094 } | 1029 } |
1095 | 1030 |
1096 inline void append_vertex_list(Vertex* v, Vertex** head, Vertex** tail) { | 1031 inline void append_vertex_list(TessellatorVertex* v, TessellatorVertex** head, |
1097 insert<Vertex, &Vertex::fPrev, &Vertex::fNext>(v, *tail, v->fNext, head, tai l); | 1032 TessellatorVertex** tail) { |
1033 insert<TessellatorVertex, &TessellatorVertex::fPrev, &TessellatorVertex::fNe xt>(v, *tail, | |
1034 v->fNext, head, | |
1035 tail); | |
1098 } | 1036 } |
1099 | 1037 |
1100 Vertex* sorted_merge(Vertex* a, Vertex* b, Comparator& c) { | 1038 TessellatorVertex* sorted_merge(TessellatorVertex* a, TessellatorVertex* b, Comp arator& c) { |
1101 Vertex* head = nullptr; | 1039 TessellatorVertex* head = nullptr; |
1102 Vertex* tail = nullptr; | 1040 TessellatorVertex* tail = nullptr; |
1103 | 1041 |
1104 while (a && b) { | 1042 while (a && b) { |
1105 if (c.sweep_lt(a->fPoint, b->fPoint)) { | 1043 if (c.sweep_lt(a->fPoint, b->fPoint)) { |
1106 Vertex* next = a->fNext; | 1044 TessellatorVertex* next = a->fNext; |
1107 append_vertex(a, &head, &tail); | 1045 append_vertex(a, &head, &tail); |
1108 a = next; | 1046 a = next; |
1109 } else { | 1047 } else { |
1110 Vertex* next = b->fNext; | 1048 TessellatorVertex* next = b->fNext; |
1111 append_vertex(b, &head, &tail); | 1049 append_vertex(b, &head, &tail); |
1112 b = next; | 1050 b = next; |
1113 } | 1051 } |
1114 } | 1052 } |
1115 if (a) { | 1053 if (a) { |
1116 append_vertex_list(a, &head, &tail); | 1054 append_vertex_list(a, &head, &tail); |
1117 } | 1055 } |
1118 if (b) { | 1056 if (b) { |
1119 append_vertex_list(b, &head, &tail); | 1057 append_vertex_list(b, &head, &tail); |
1120 } | 1058 } |
1121 return head; | 1059 return head; |
1122 } | 1060 } |
1123 | 1061 |
1124 // Stage 4: Simplify the mesh by inserting new vertices at intersecting edges. | 1062 // Stage 4: Simplify the mesh by inserting new vertices at intersecting edges. |
1125 | 1063 |
1126 void simplify(Vertex* vertices, Comparator& c, SkChunkAlloc& alloc) { | 1064 void simplify(TessellatorVertex* vertices, Comparator& c, SkChunkAlloc& alloc) { |
1127 LOG("simplifying complex polygons\n"); | 1065 LOG("simplifying complex polygons\n"); |
1128 EdgeList activeEdges; | 1066 EdgeList activeEdges; |
1129 for (Vertex* v = vertices; v != nullptr; v = v->fNext) { | 1067 for (TessellatorVertex* v = vertices; v != nullptr; v = v->fNext) { |
1130 if (!v->fFirstEdgeAbove && !v->fFirstEdgeBelow) { | 1068 if (!v->fFirstEdgeAbove && !v->fFirstEdgeBelow) { |
1131 continue; | 1069 continue; |
1132 } | 1070 } |
1133 #if LOGGING_ENABLED | 1071 #if TESSELLATOR_LOGGING_ENABLED |
1134 LOG("\nvertex %g: (%g,%g)\n", v->fID, v->fPoint.fX, v->fPoint.fY); | 1072 LOG("\nvertex %g: (%g,%g)\n", v->fID, v->fPoint.fX, v->fPoint.fY); |
1135 #endif | 1073 #endif |
1136 Edge* leftEnclosingEdge = nullptr; | 1074 Edge* leftEnclosingEdge = nullptr; |
1137 Edge* rightEnclosingEdge = nullptr; | 1075 Edge* rightEnclosingEdge = nullptr; |
1138 bool restartChecks; | 1076 bool restartChecks; |
1139 do { | 1077 do { |
1140 restartChecks = false; | 1078 restartChecks = false; |
1141 find_enclosing_edges(v, &activeEdges, &leftEnclosingEdge, &rightEncl osingEdge); | 1079 find_enclosing_edges(v, &activeEdges, &leftEnclosingEdge, &rightEncl osingEdge); |
1142 if (v->fFirstEdgeBelow) { | 1080 if (v->fFirstEdgeBelow) { |
1143 for (Edge* edge = v->fFirstEdgeBelow; edge != nullptr; edge = ed ge->fNextEdgeBelow) { | 1081 for (Edge* edge = v->fFirstEdgeBelow; edge != nullptr; edge = ed ge->fNextEdgeBelow) { |
1144 if (check_for_intersection(edge, leftEnclosingEdge, &activeE dges, c, alloc)) { | 1082 if (check_for_intersection(edge, leftEnclosingEdge, &activeE dges, c, alloc)) { |
1145 restartChecks = true; | 1083 restartChecks = true; |
1146 break; | 1084 break; |
1147 } | 1085 } |
1148 if (check_for_intersection(edge, rightEnclosingEdge, &active Edges, c, alloc)) { | 1086 if (check_for_intersection(edge, rightEnclosingEdge, &active Edges, c, alloc)) { |
1149 restartChecks = true; | 1087 restartChecks = true; |
1150 break; | 1088 break; |
1151 } | 1089 } |
1152 } | 1090 } |
1153 } else { | 1091 } else { |
1154 if (Vertex* pv = check_for_intersection(leftEnclosingEdge, right EnclosingEdge, | 1092 if (TessellatorVertex* pv = check_for_intersection(leftEnclosing Edge, |
1155 &activeEdges, c, alloc)) { | 1093 rightEnclosin gEdge, &activeEdges, |
1094 c, alloc)) { | |
1156 if (c.sweep_lt(pv->fPoint, v->fPoint)) { | 1095 if (c.sweep_lt(pv->fPoint, v->fPoint)) { |
1157 v = pv; | 1096 v = pv; |
1158 } | 1097 } |
1159 restartChecks = true; | 1098 restartChecks = true; |
1160 } | 1099 } |
1161 | 1100 |
1162 } | 1101 } |
1163 } while (restartChecks); | 1102 } while (restartChecks); |
1164 for (Edge* e = v->fFirstEdgeAbove; e; e = e->fNextEdgeAbove) { | 1103 for (Edge* e = v->fFirstEdgeAbove; e; e = e->fNextEdgeAbove) { |
1165 remove_edge(e, &activeEdges); | 1104 remove_edge(e, &activeEdges); |
1166 } | 1105 } |
1167 Edge* leftEdge = leftEnclosingEdge; | 1106 Edge* leftEdge = leftEnclosingEdge; |
1168 for (Edge* e = v->fFirstEdgeBelow; e; e = e->fNextEdgeBelow) { | 1107 for (Edge* e = v->fFirstEdgeBelow; e; e = e->fNextEdgeBelow) { |
1169 insert_edge(e, leftEdge, &activeEdges); | 1108 insert_edge(e, leftEdge, &activeEdges); |
1170 leftEdge = e; | 1109 leftEdge = e; |
1171 } | 1110 } |
1172 v->fProcessed = true; | 1111 v->fProcessed = true; |
1173 } | 1112 } |
1174 } | 1113 } |
1175 | 1114 |
1176 // Stage 5: Tessellate the simplified mesh into monotone polygons. | 1115 // Stage 5: Tessellate the simplified mesh into monotone polygons. |
1177 | 1116 |
1178 Poly* tessellate(Vertex* vertices, SkChunkAlloc& alloc) { | 1117 Poly* tessellate(TessellatorVertex* vertices, SkChunkAlloc& alloc) { |
1179 LOG("tessellating simple polygons\n"); | 1118 LOG("tessellating simple polygons\n"); |
1180 EdgeList activeEdges; | 1119 EdgeList activeEdges; |
1181 Poly* polys = nullptr; | 1120 Poly* polys = nullptr; |
1182 for (Vertex* v = vertices; v != nullptr; v = v->fNext) { | 1121 for (TessellatorVertex* v = vertices; v != nullptr; v = v->fNext) { |
1183 if (!v->fFirstEdgeAbove && !v->fFirstEdgeBelow) { | 1122 if (!v->fFirstEdgeAbove && !v->fFirstEdgeBelow) { |
1184 continue; | 1123 continue; |
1185 } | 1124 } |
1186 #if LOGGING_ENABLED | 1125 #if TESSELLATOR_LOGGING_ENABLED |
1187 LOG("\nvertex %g: (%g,%g)\n", v->fID, v->fPoint.fX, v->fPoint.fY); | 1126 LOG("\nvertex %g: (%g,%g)\n", v->fID, v->fPoint.fX, v->fPoint.fY); |
1188 #endif | 1127 #endif |
1189 Edge* leftEnclosingEdge = nullptr; | 1128 Edge* leftEnclosingEdge = nullptr; |
1190 Edge* rightEnclosingEdge = nullptr; | 1129 Edge* rightEnclosingEdge = nullptr; |
1191 find_enclosing_edges(v, &activeEdges, &leftEnclosingEdge, &rightEnclosin gEdge); | 1130 find_enclosing_edges(v, &activeEdges, &leftEnclosingEdge, &rightEnclosin gEdge); |
1192 Poly* leftPoly = nullptr; | 1131 Poly* leftPoly = nullptr; |
1193 Poly* rightPoly = nullptr; | 1132 Poly* rightPoly = nullptr; |
1194 if (v->fFirstEdgeAbove) { | 1133 if (v->fFirstEdgeAbove) { |
1195 leftPoly = v->fFirstEdgeAbove->fLeftPoly; | 1134 leftPoly = v->fFirstEdgeAbove->fLeftPoly; |
1196 rightPoly = v->fLastEdgeAbove->fRightPoly; | 1135 rightPoly = v->fLastEdgeAbove->fRightPoly; |
1197 } else { | 1136 } else { |
1198 leftPoly = leftEnclosingEdge ? leftEnclosingEdge->fRightPoly : nullp tr; | 1137 leftPoly = leftEnclosingEdge ? leftEnclosingEdge->fRightPoly : nullp tr; |
1199 rightPoly = rightEnclosingEdge ? rightEnclosingEdge->fLeftPoly : nul lptr; | 1138 rightPoly = rightEnclosingEdge ? rightEnclosingEdge->fLeftPoly : nul lptr; |
1200 } | 1139 } |
1201 #if LOGGING_ENABLED | 1140 #if TESSELLATOR_LOGGING_ENABLED |
1202 LOG("edges above:\n"); | 1141 LOG("edges above:\n"); |
1203 for (Edge* e = v->fFirstEdgeAbove; e; e = e->fNextEdgeAbove) { | 1142 for (Edge* e = v->fFirstEdgeAbove; e; e = e->fNextEdgeAbove) { |
1204 LOG("%g -> %g, lpoly %d, rpoly %d\n", e->fTop->fID, e->fBottom->fID, | 1143 LOG("%g -> %g, lpoly %d, rpoly %d\n", e->fTop->fID, e->fBottom->fID, |
1205 e->fLeftPoly ? e->fLeftPoly->fID : -1, e->fRightPoly ? e->fRight Poly->fID : -1); | 1144 e->fLeftPoly ? e->fLeftPoly->fID : -1, e->fRightPoly ? e->fRight Poly->fID : -1); |
1206 } | 1145 } |
1207 LOG("edges below:\n"); | 1146 LOG("edges below:\n"); |
1208 for (Edge* e = v->fFirstEdgeBelow; e; e = e->fNextEdgeBelow) { | 1147 for (Edge* e = v->fFirstEdgeBelow; e; e = e->fNextEdgeBelow) { |
1209 LOG("%g -> %g, lpoly %d, rpoly %d\n", e->fTop->fID, e->fBottom->fID, | 1148 LOG("%g -> %g, lpoly %d, rpoly %d\n", e->fTop->fID, e->fBottom->fID, |
1210 e->fLeftPoly ? e->fLeftPoly->fID : -1, e->fRightPoly ? e->fRight Poly->fID : -1); | 1149 e->fLeftPoly ? e->fLeftPoly->fID : -1, e->fRightPoly ? e->fRight Poly->fID : -1); |
1211 } | 1150 } |
(...skipping 61 matching lines...) Expand 10 before | Expand all | Expand 10 after Loading... | |
1273 int winding = leftEdge->fLeftPoly ? leftEdge->fLeftPoly->fWindin g : 0; | 1212 int winding = leftEdge->fLeftPoly ? leftEdge->fLeftPoly->fWindin g : 0; |
1274 winding += leftEdge->fWinding; | 1213 winding += leftEdge->fWinding; |
1275 if (winding != 0) { | 1214 if (winding != 0) { |
1276 Poly* poly = new_poly(&polys, v, winding, alloc); | 1215 Poly* poly = new_poly(&polys, v, winding, alloc); |
1277 leftEdge->fRightPoly = rightEdge->fLeftPoly = poly; | 1216 leftEdge->fRightPoly = rightEdge->fLeftPoly = poly; |
1278 } | 1217 } |
1279 leftEdge = rightEdge; | 1218 leftEdge = rightEdge; |
1280 } | 1219 } |
1281 v->fLastEdgeBelow->fRightPoly = rightPoly; | 1220 v->fLastEdgeBelow->fRightPoly = rightPoly; |
1282 } | 1221 } |
1283 #if LOGGING_ENABLED | 1222 #if TESSELLATOR_LOGGING_ENABLED |
1284 LOG("\nactive edges:\n"); | 1223 LOG("\nactive edges:\n"); |
1285 for (Edge* e = activeEdges.fHead; e != nullptr; e = e->fRight) { | 1224 for (Edge* e = activeEdges.fHead; e != nullptr; e = e->fRight) { |
1286 LOG("%g -> %g, lpoly %d, rpoly %d\n", e->fTop->fID, e->fBottom->fID, | 1225 LOG("%g -> %g, lpoly %d, rpoly %d\n", e->fTop->fID, e->fBottom->fID, |
1287 e->fLeftPoly ? e->fLeftPoly->fID : -1, e->fRightPoly ? e->fRight Poly->fID : -1); | 1226 e->fLeftPoly ? e->fLeftPoly->fID : -1, e->fRightPoly ? e->fRight Poly->fID : -1); |
1288 } | 1227 } |
1289 #endif | 1228 #endif |
1290 } | 1229 } |
1291 return polys; | 1230 return polys; |
1292 } | 1231 } |
1293 | 1232 |
1294 // This is a driver function which calls stages 2-5 in turn. | 1233 // This is a driver function which calls stages 2-5 in turn. |
1295 | 1234 |
1296 Poly* contours_to_polys(Vertex** contours, int contourCnt, Comparator& c, SkChun kAlloc& alloc) { | 1235 Poly* contours_to_polys(TessellatorVertex** contours, int contourCnt, SkRect pat hBounds, |
1297 #if LOGGING_ENABLED | 1236 SkChunkAlloc& alloc) { |
1237 Comparator c; | |
1238 if (pathBounds.width() > pathBounds.height()) { | |
1239 c.sweep_lt = sweep_lt_horiz; | |
1240 c.sweep_gt = sweep_gt_horiz; | |
1241 } else { | |
1242 c.sweep_lt = sweep_lt_vert; | |
1243 c.sweep_gt = sweep_gt_vert; | |
1244 } | |
1245 #if TESSELLATOR_LOGGING_ENABLED | |
1298 for (int i = 0; i < contourCnt; ++i) { | 1246 for (int i = 0; i < contourCnt; ++i) { |
1299 Vertex* v = contours[i]; | 1247 TessellatorVertex* v = contours[i]; |
1300 SkASSERT(v); | 1248 SkASSERT(v); |
1301 LOG("path.moveTo(%20.20g, %20.20g);\n", v->fPoint.fX, v->fPoint.fY); | 1249 LOG("path.moveTo(%20.20g, %20.20g);\n", v->fPoint.fX, v->fPoint.fY); |
1302 for (v = v->fNext; v != contours[i]; v = v->fNext) { | 1250 for (v = v->fNext; v != contours[i]; v = v->fNext) { |
1303 LOG("path.lineTo(%20.20g, %20.20g);\n", v->fPoint.fX, v->fPoint.fY); | 1251 LOG("path.lineTo(%20.20g, %20.20g);\n", v->fPoint.fX, v->fPoint.fY); |
1304 } | 1252 } |
1305 } | 1253 } |
1306 #endif | 1254 #endif |
1307 sanitize_contours(contours, contourCnt); | 1255 sanitize_contours(contours, contourCnt); |
1308 Vertex* vertices = build_edges(contours, contourCnt, c, alloc); | 1256 TessellatorVertex* vertices = build_edges(contours, contourCnt, c, alloc); |
1309 if (!vertices) { | 1257 if (!vertices) { |
1310 return nullptr; | 1258 return nullptr; |
1311 } | 1259 } |
1312 | 1260 |
1313 // Sort vertices in Y (secondarily in X). | 1261 // Sort vertices in Y (secondarily in X). |
1314 merge_sort(&vertices, c); | 1262 merge_sort(&vertices, c); |
1315 merge_coincident_vertices(&vertices, c, alloc); | 1263 merge_coincident_vertices(&vertices, c, alloc); |
1316 #if LOGGING_ENABLED | 1264 #if TESSELLATOR_LOGGING_ENABLED |
1317 for (Vertex* v = vertices; v != nullptr; v = v->fNext) { | 1265 for (TessellatorVertex* v = vertices; v != nullptr; v = v->fNext) { |
1318 static float gID = 0.0f; | 1266 static float gID = 0.0f; |
1319 v->fID = gID++; | 1267 v->fID = gID++; |
1320 } | 1268 } |
1321 #endif | 1269 #endif |
1322 simplify(vertices, c, alloc); | 1270 simplify(vertices, c, alloc); |
1323 return tessellate(vertices, alloc); | 1271 return tessellate(vertices, alloc); |
1324 } | 1272 } |
1325 | 1273 |
1274 Poly* path_to_polys(const SkPath& path, SkScalar tolerance, const SkRect& clipBo unds, | |
1275 bool* isLinear) { | |
1276 int contourCnt; | |
1277 int maxPts = GrPathUtils::worstCasePointCount(path, &contourCnt, tolerance); | |
1278 if (maxPts <= 0) { | |
1279 return nullptr; | |
1280 } | |
1281 if (maxPts > ((int)SK_MaxU16 + 1)) { | |
1282 SkDebugf("Path not rendered, too many verts (%d)\n", maxPts); | |
1283 return nullptr; | |
1284 } | |
1285 SkPath::FillType fillType = path.getFillType(); | |
1286 if (SkPath::IsInverseFillType(fillType)) { | |
1287 contourCnt++; | |
1288 } | |
1289 SkAutoTDeleteArray<TessellatorVertex*> contours(new TessellatorVertex* [cont ourCnt]); | |
1290 | |
1291 // For the initial size of the chunk allocator, estimate based on the point count: | |
1292 // one vertex per point for the initial passes, plus two for the vertices in the | |
1293 // resulting Polys, since the same point may end up in two Polys. Assume mi nimal | |
1294 // connectivity of one Edge per TessellatorVertex (will grow for intersectio ns). | |
1295 SkChunkAlloc alloc(maxPts * (3 * sizeof(TessellatorVertex) + sizeof(Edge))); | |
1296 path_to_contours(path, tolerance, clipBounds, contours.get(), alloc, isLinea r); | |
1297 return contours_to_polys(contours.get(), contourCnt, path.getBounds(), alloc ); | |
1298 } | |
1299 | |
1326 // Stage 6: Triangulate the monotone polygons into a vertex buffer. | 1300 // Stage 6: Triangulate the monotone polygons into a vertex buffer. |
1327 | 1301 |
1328 SkPoint* polys_to_triangles(Poly* polys, SkPath::FillType fillType, SkPoint* dat a) { | 1302 int polys_to_triangles(Poly* polys, SkPath::FillType fillType, bool isLinear, |
1329 SkPoint* d = data; | 1303 GrResourceProvider* resourceProvider, |
1304 SkAutoTUnref<GrVertexBuffer>& vertexBuffer, bool canMapVB ) { | |
1305 int count = 0; | |
1306 for (Poly* poly = polys; poly; poly = poly->fNext) { | |
1307 if (apply_fill_type(fillType, poly->fWinding) && poly->fCount >= 3) { | |
1308 count += (poly->fCount - 2) * (TESSELLATOR_WIREFRAME ? 6 : 3); | |
1309 } | |
1310 } | |
1311 if (0 == count) { | |
1312 return 0; | |
1313 } | |
1314 | |
1315 size_t size = count * sizeof(SkPoint); | |
1316 if (!vertexBuffer.get() || vertexBuffer->gpuMemorySize() < size) { | |
1317 vertexBuffer.reset(resourceProvider->createVertexBuffer( | |
1318 size, GrResourceProvider::kStatic_BufferUsage, 0)); | |
1319 } | |
1320 if (!vertexBuffer.get()) { | |
1321 SkDebugf("Could not allocate vertices\n"); | |
1322 return 0; | |
1323 } | |
1324 SkPoint* verts; | |
1325 if (canMapVB) { | |
1326 verts = static_cast<SkPoint*>(vertexBuffer->map()); | |
1327 } else { | |
1328 verts = new SkPoint[count]; | |
1329 } | |
1330 SkPoint* end = verts; | |
1330 for (Poly* poly = polys; poly; poly = poly->fNext) { | 1331 for (Poly* poly = polys; poly; poly = poly->fNext) { |
1331 if (apply_fill_type(fillType, poly->fWinding)) { | 1332 if (apply_fill_type(fillType, poly->fWinding)) { |
1332 d = poly->emit(d); | 1333 end = poly->emit(end); |
1333 } | 1334 } |
1334 } | 1335 } |
1335 return d; | 1336 int actualCount = static_cast<int>(end - verts); |
1337 LOG("actual count: %d\n", actualCount); | |
1338 SkASSERT(actualCount <= count); | |
1339 if (canMapVB) { | |
1340 vertexBuffer->unmap(); | |
1341 } else { | |
1342 vertexBuffer->updateData(verts, actualCount * sizeof(SkPoint)); | |
1343 delete[] verts; | |
1344 } | |
1345 | |
1346 return actualCount; | |
1336 } | 1347 } |
1337 | 1348 |
1338 struct TessInfo { | 1349 int polys_to_vertices(Poly* polys, SkPath::FillType fillType, bool isLinear, |
1339 SkScalar fTolerance; | 1350 WindingVertex** verts) { |
1340 int fCount; | 1351 int count = 0; |
1341 }; | 1352 for (Poly* poly = polys; poly; poly = poly->fNext) { |
1342 | 1353 if (apply_fill_type(fillType, poly->fWinding) && poly->fCount >= 3) { |
1343 bool cache_match(GrVertexBuffer* vertexBuffer, SkScalar tol, int* actualCount) { | 1354 count += (poly->fCount - 2) * (TESSELLATOR_WIREFRAME ? 6 : 3); |
1344 if (!vertexBuffer) { | 1355 } |
1345 return false; | |
1346 } | 1356 } |
1347 const SkData* data = vertexBuffer->getUniqueKey().getCustomData(); | 1357 if (0 == count) { |
1348 SkASSERT(data); | 1358 *verts = nullptr; |
1349 const TessInfo* info = static_cast<const TessInfo*>(data->data()); | 1359 return 0; |
1350 if (info->fTolerance == 0 || info->fTolerance < 3.0f * tol) { | |
1351 *actualCount = info->fCount; | |
1352 return true; | |
1353 } | |
1354 return false; | |
1355 } | |
1356 | |
1357 }; | |
1358 | |
1359 GrTessellatingPathRenderer::GrTessellatingPathRenderer() { | |
1360 } | |
1361 | |
1362 namespace { | |
1363 | |
1364 // When the SkPathRef genID changes, invalidate a corresponding GrResource descr ibed by key. | |
1365 class PathInvalidator : public SkPathRef::GenIDChangeListener { | |
1366 public: | |
1367 explicit PathInvalidator(const GrUniqueKey& key) : fMsg(key) {} | |
1368 private: | |
1369 GrUniqueKeyInvalidatedMessage fMsg; | |
1370 | |
1371 void onChange() override { | |
1372 SkMessageBus<GrUniqueKeyInvalidatedMessage>::Post(fMsg); | |
1373 } | |
1374 }; | |
1375 | |
1376 } // namespace | |
1377 | |
1378 bool GrTessellatingPathRenderer::onCanDrawPath(const CanDrawPathArgs& args) cons t { | |
1379 // This path renderer can draw all fill styles, all stroke styles except hai rlines, but does | |
1380 // not do antialiasing. It can do convex and concave paths, but we'll leave the convex ones to | |
1381 // simpler algorithms. | |
1382 return !IsStrokeHairlineOrEquivalent(*args.fStroke, *args.fViewMatrix, nullp tr) && | |
1383 !args.fAntiAlias && !args.fPath->isConvex(); | |
1384 } | |
1385 | |
1386 class TessellatingPathBatch : public GrVertexBatch { | |
1387 public: | |
1388 DEFINE_BATCH_CLASS_ID | |
1389 | |
1390 static GrDrawBatch* Create(const GrColor& color, | |
1391 const SkPath& path, | |
1392 const GrStrokeInfo& stroke, | |
1393 const SkMatrix& viewMatrix, | |
1394 SkRect clipBounds) { | |
1395 return new TessellatingPathBatch(color, path, stroke, viewMatrix, clipBo unds); | |
1396 } | 1360 } |
1397 | 1361 |
1398 const char* name() const override { return "TessellatingPathBatch"; } | 1362 *verts = new WindingVertex[count]; |
1399 | 1363 WindingVertex* vertsEnd = *verts; |
1400 void computePipelineOptimizations(GrInitInvariantOutput* color, | 1364 SkPoint* points = new SkPoint[count]; |
1401 GrInitInvariantOutput* coverage, | 1365 SkPoint* pointsEnd = points; |
1402 GrBatchToXPOverrides* overrides) const ove rride { | 1366 for (Poly* poly = polys; poly; poly = poly->fNext) { |
1403 color->setKnownFourComponents(fColor); | 1367 if (apply_fill_type(fillType, poly->fWinding)) { |
1404 coverage->setUnknownSingleComponent(); | 1368 SkPoint* start = pointsEnd; |
1405 overrides->fUsePLSDstRead = false; | 1369 pointsEnd = poly->emit(pointsEnd); |
1406 } | 1370 while (start != pointsEnd) { |
1407 | 1371 vertsEnd->fPos = *start; |
1408 private: | 1372 vertsEnd->fWinding = poly->fWinding; |
1409 void initBatchTracker(const GrXPOverridesForBatch& overrides) override { | 1373 ++start; |
1410 // Handle any color overrides | 1374 ++vertsEnd; |
1411 if (!overrides.readsColor()) { | |
1412 fColor = GrColor_ILLEGAL; | |
1413 } | |
1414 overrides.getOverrideColorIfSet(&fColor); | |
1415 fPipelineInfo = overrides; | |
1416 } | |
1417 | |
1418 int tessellate(GrUniqueKey* key, | |
1419 GrResourceProvider* resourceProvider, | |
1420 SkAutoTUnref<GrVertexBuffer>& vertexBuffer, | |
1421 bool canMapVB) const { | |
1422 SkPath path; | |
1423 GrStrokeInfo stroke(fStroke); | |
1424 if (stroke.isDashed()) { | |
1425 if (!stroke.applyDashToPath(&path, &stroke, fPath)) { | |
1426 return 0; | |
1427 } | |
1428 } else { | |
1429 path = fPath; | |
1430 } | |
1431 if (!stroke.isFillStyle()) { | |
1432 stroke.setResScale(SkScalarAbs(fViewMatrix.getMaxScale())); | |
1433 if (!stroke.applyToPath(&path, path)) { | |
1434 return 0; | |
1435 } | |
1436 stroke.setFillStyle(); | |
1437 } | |
1438 SkRect pathBounds = path.getBounds(); | |
1439 Comparator c; | |
1440 if (pathBounds.width() > pathBounds.height()) { | |
1441 c.sweep_lt = sweep_lt_horiz; | |
1442 c.sweep_gt = sweep_gt_horiz; | |
1443 } else { | |
1444 c.sweep_lt = sweep_lt_vert; | |
1445 c.sweep_gt = sweep_gt_vert; | |
1446 } | |
1447 SkScalar screenSpaceTol = GrPathUtils::kDefaultTolerance; | |
1448 SkScalar tol = GrPathUtils::scaleToleranceToSrc(screenSpaceTol, fViewMat rix, pathBounds); | |
1449 int contourCnt; | |
1450 int maxPts = GrPathUtils::worstCasePointCount(path, &contourCnt, tol); | |
1451 if (maxPts <= 0) { | |
1452 return 0; | |
1453 } | |
1454 if (maxPts > ((int)SK_MaxU16 + 1)) { | |
1455 SkDebugf("Path not rendered, too many verts (%d)\n", maxPts); | |
1456 return 0; | |
1457 } | |
1458 SkPath::FillType fillType = path.getFillType(); | |
1459 if (SkPath::IsInverseFillType(fillType)) { | |
1460 contourCnt++; | |
1461 } | |
1462 | |
1463 LOG("got %d pts, %d contours\n", maxPts, contourCnt); | |
1464 SkAutoTDeleteArray<Vertex*> contours(new Vertex* [contourCnt]); | |
1465 | |
1466 // For the initial size of the chunk allocator, estimate based on the po int count: | |
1467 // one vertex per point for the initial passes, plus two for the vertice s in the | |
1468 // resulting Polys, since the same point may end up in two Polys. Assum e minimal | |
1469 // connectivity of one Edge per Vertex (will grow for intersections). | |
1470 SkChunkAlloc alloc(maxPts * (3 * sizeof(Vertex) + sizeof(Edge))); | |
1471 bool isLinear; | |
1472 path_to_contours(path, tol, fClipBounds, contours.get(), alloc, &isLinea r); | |
1473 Poly* polys; | |
1474 polys = contours_to_polys(contours.get(), contourCnt, c, alloc); | |
1475 int count = 0; | |
1476 for (Poly* poly = polys; poly; poly = poly->fNext) { | |
1477 if (apply_fill_type(fillType, poly->fWinding) && poly->fCount >= 3) { | |
1478 count += (poly->fCount - 2) * (WIREFRAME ? 6 : 3); | |
1479 } | 1375 } |
1480 } | 1376 } |
1481 if (0 == count) { | |
1482 return 0; | |
1483 } | |
1484 | |
1485 size_t size = count * sizeof(SkPoint); | |
1486 if (!vertexBuffer.get() || vertexBuffer->gpuMemorySize() < size) { | |
1487 vertexBuffer.reset(resourceProvider->createVertexBuffer( | |
1488 size, GrResourceProvider::kStatic_BufferUsage, 0)); | |
1489 } | |
1490 if (!vertexBuffer.get()) { | |
1491 SkDebugf("Could not allocate vertices\n"); | |
1492 return 0; | |
1493 } | |
1494 SkPoint* verts; | |
1495 if (canMapVB) { | |
1496 verts = static_cast<SkPoint*>(vertexBuffer->map()); | |
1497 } else { | |
1498 verts = new SkPoint[count]; | |
1499 } | |
1500 SkPoint* end = polys_to_triangles(polys, fillType, verts); | |
1501 int actualCount = static_cast<int>(end - verts); | |
1502 LOG("actual count: %d\n", actualCount); | |
1503 SkASSERT(actualCount <= count); | |
1504 if (canMapVB) { | |
1505 vertexBuffer->unmap(); | |
1506 } else { | |
1507 vertexBuffer->updateData(verts, actualCount * sizeof(SkPoint)); | |
1508 delete[] verts; | |
1509 } | |
1510 | |
1511 | |
1512 if (!fPath.isVolatile()) { | |
1513 TessInfo info; | |
1514 info.fTolerance = isLinear ? 0 : tol; | |
1515 info.fCount = actualCount; | |
1516 SkAutoTUnref<SkData> data(SkData::NewWithCopy(&info, sizeof(info))); | |
1517 key->setCustomData(data.get()); | |
1518 resourceProvider->assignUniqueKeyToResource(*key, vertexBuffer.get() ); | |
1519 SkPathPriv::AddGenIDChangeListener(fPath, new PathInvalidator(*key)) ; | |
1520 } | |
1521 return actualCount; | |
1522 } | 1377 } |
1523 | 1378 int actualCount = static_cast<int>(vertsEnd - *verts); |
1524 void onPrepareDraws(Target* target) const override { | 1379 SkASSERT(actualCount <= count); |
1525 // construct a cache key from the path's genID and the view matrix | 1380 SkASSERT(pointsEnd - points == actualCount); |
1526 static const GrUniqueKey::Domain kDomain = GrUniqueKey::GenerateDomain() ; | 1381 delete[] points; |
1527 GrUniqueKey key; | 1382 return actualCount; |
1528 int clipBoundsSize32 = | |
1529 fPath.isInverseFillType() ? sizeof(fClipBounds) / sizeof(uint32_t) : 0; | |
1530 int strokeDataSize32 = fStroke.computeUniqueKeyFragmentData32Cnt(); | |
1531 GrUniqueKey::Builder builder(&key, kDomain, 2 + clipBoundsSize32 + strok eDataSize32); | |
1532 builder[0] = fPath.getGenerationID(); | |
1533 builder[1] = fPath.getFillType(); | |
1534 // For inverse fills, the tessellation is dependent on clip bounds. | |
1535 if (fPath.isInverseFillType()) { | |
1536 memcpy(&builder[2], &fClipBounds, sizeof(fClipBounds)); | |
1537 } | |
1538 fStroke.asUniqueKeyFragment(&builder[2 + clipBoundsSize32]); | |
1539 builder.finish(); | |
1540 GrResourceProvider* rp = target->resourceProvider(); | |
1541 SkAutoTUnref<GrVertexBuffer> vertexBuffer(rp->findAndRefTByUniqueKey<GrV ertexBuffer>(key)); | |
1542 int actualCount; | |
1543 SkScalar screenSpaceTol = GrPathUtils::kDefaultTolerance; | |
1544 SkScalar tol = GrPathUtils::scaleToleranceToSrc( | |
1545 screenSpaceTol, fViewMatrix, fPath.getBounds()); | |
1546 if (!cache_match(vertexBuffer.get(), tol, &actualCount)) { | |
1547 bool canMapVB = GrCaps::kNone_MapFlags != target->caps().mapBufferFl ags(); | |
1548 actualCount = this->tessellate(&key, rp, vertexBuffer, canMapVB); | |
1549 } | |
1550 | |
1551 if (actualCount == 0) { | |
1552 return; | |
1553 } | |
1554 | |
1555 SkAutoTUnref<const GrGeometryProcessor> gp; | |
1556 { | |
1557 using namespace GrDefaultGeoProcFactory; | |
1558 | |
1559 Color color(fColor); | |
1560 LocalCoords localCoords(fPipelineInfo.readsLocalCoords() ? | |
1561 LocalCoords::kUsePosition_Type : | |
1562 LocalCoords::kUnused_Type); | |
1563 Coverage::Type coverageType; | |
1564 if (fPipelineInfo.readsCoverage()) { | |
1565 coverageType = Coverage::kSolid_Type; | |
1566 } else { | |
1567 coverageType = Coverage::kNone_Type; | |
1568 } | |
1569 Coverage coverage(coverageType); | |
1570 gp.reset(GrDefaultGeoProcFactory::Create(color, coverage, localCoord s, | |
1571 fViewMatrix)); | |
1572 } | |
1573 | |
1574 target->initDraw(gp, this->pipeline()); | |
1575 SkASSERT(gp->getVertexStride() == sizeof(SkPoint)); | |
1576 | |
1577 GrPrimitiveType primitiveType = WIREFRAME ? kLines_GrPrimitiveType | |
1578 : kTriangles_GrPrimitiveType; | |
1579 GrVertices vertices; | |
1580 vertices.init(primitiveType, vertexBuffer.get(), 0, actualCount); | |
1581 target->draw(vertices); | |
1582 } | |
1583 | |
1584 bool onCombineIfPossible(GrBatch*, const GrCaps&) override { return false; } | |
1585 | |
1586 TessellatingPathBatch(const GrColor& color, | |
1587 const SkPath& path, | |
1588 const GrStrokeInfo& stroke, | |
1589 const SkMatrix& viewMatrix, | |
1590 const SkRect& clipBounds) | |
1591 : INHERITED(ClassID()) | |
1592 , fColor(color) | |
1593 , fPath(path) | |
1594 , fStroke(stroke) | |
1595 , fViewMatrix(viewMatrix) { | |
1596 const SkRect& pathBounds = path.getBounds(); | |
1597 fClipBounds = clipBounds; | |
1598 // Because the clip bounds are used to add a contour for inverse fills, they must also | |
1599 // include the path bounds. | |
1600 fClipBounds.join(pathBounds); | |
1601 if (path.isInverseFillType()) { | |
1602 fBounds = fClipBounds; | |
1603 } else { | |
1604 fBounds = path.getBounds(); | |
1605 } | |
1606 if (!stroke.isFillStyle()) { | |
1607 SkScalar radius = SkScalarHalf(stroke.getWidth()); | |
1608 if (stroke.getJoin() == SkPaint::kMiter_Join) { | |
1609 SkScalar scale = stroke.getMiter(); | |
1610 if (scale > SK_Scalar1) { | |
1611 radius = SkScalarMul(radius, scale); | |
1612 } | |
1613 } | |
1614 fBounds.outset(radius, radius); | |
1615 } | |
1616 viewMatrix.mapRect(&fBounds); | |
1617 } | |
1618 | |
1619 GrColor fColor; | |
1620 SkPath fPath; | |
1621 GrStrokeInfo fStroke; | |
1622 SkMatrix fViewMatrix; | |
1623 SkRect fClipBounds; // in source space | |
1624 GrXPOverridesForBatch fPipelineInfo; | |
1625 | |
1626 typedef GrVertexBatch INHERITED; | |
1627 }; | |
1628 | |
1629 bool GrTessellatingPathRenderer::onDrawPath(const DrawPathArgs& args) { | |
1630 SkASSERT(!args.fAntiAlias); | |
1631 const GrRenderTarget* rt = args.fPipelineBuilder->getRenderTarget(); | |
1632 if (nullptr == rt) { | |
1633 return false; | |
1634 } | |
1635 | |
1636 SkIRect clipBoundsI; | |
1637 args.fPipelineBuilder->clip().getConservativeBounds(rt->width(), rt->height( ), &clipBoundsI); | |
1638 SkRect clipBounds = SkRect::Make(clipBoundsI); | |
1639 SkMatrix vmi; | |
1640 if (!args.fViewMatrix->invert(&vmi)) { | |
1641 return false; | |
1642 } | |
1643 vmi.mapRect(&clipBounds); | |
1644 SkAutoTUnref<GrDrawBatch> batch(TessellatingPathBatch::Create(args.fColor, * args.fPath, | |
1645 *args.fStroke, *args.fViewMatrix, | |
1646 clipBounds)); | |
1647 args.fTarget->drawBatch(*args.fPipelineBuilder, batch); | |
1648 | |
1649 return true; | |
1650 } | 1383 } |
1651 | |
1652 //////////////////////////////////////////////////////////////////////////////// /////////////////// | |
1653 | |
1654 #ifdef GR_TEST_UTILS | |
1655 | |
1656 DRAW_BATCH_TEST_DEFINE(TesselatingPathBatch) { | |
1657 GrColor color = GrRandomColor(random); | |
1658 SkMatrix viewMatrix = GrTest::TestMatrixInvertible(random); | |
1659 SkPath path = GrTest::TestPath(random); | |
1660 SkRect clipBounds = GrTest::TestRect(random); | |
1661 SkMatrix vmi; | |
1662 bool result = viewMatrix.invert(&vmi); | |
1663 if (!result) { | |
1664 SkFAIL("Cannot invert matrix\n"); | |
1665 } | |
1666 vmi.mapRect(&clipBounds); | |
1667 GrStrokeInfo strokeInfo = GrTest::TestStrokeInfo(random); | |
1668 return TessellatingPathBatch::Create(color, path, strokeInfo, viewMatrix, cl ipBounds); | |
1669 } | |
1670 | |
1671 #endif | |
OLD | NEW |