Chromium Code Reviews
chromiumcodereview-hr@appspot.gserviceaccount.com (chromiumcodereview-hr) | Please choose your nickname with Settings | Help | Chromium Project | Gerrit Changes | Sign out
(1)

Side by Side Diff: src/gpu/GrTessellator.cpp

Issue 1557083002: Broke GrTessellatingPathRenderer's tessellator out into a separate file. (Closed) Base URL: https://skia.googlesource.com/skia.git@master
Patch Set: Created 4 years, 11 months ago
Use n/p to move between diff chunks; N/P to move between comments. Draft comments are only viewable by you.
Jump to:
View unified diff | Download patch
OLDNEW
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
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
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
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
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
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
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
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
OLDNEW

Powered by Google App Engine
This is Rietveld 408576698