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

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

Issue 2299683002: Revert of Screenspace AA tessellated path rendering. (Closed) Base URL: https://skia.googlesource.com/skia.git@master
Patch Set: Created 4 years, 3 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
« no previous file with comments | « src/gpu/GrTessellator.h ('k') | src/gpu/batches/GrTessellatingPathRenderer.cpp » ('j') | no next file with comments »
Toggle Intra-line Diffs ('i') | Expand Comments ('e') | Collapse Comments ('c') | Show Comments Hide Comments ('s')
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 "GrTessellator.h" 8 #include "GrTessellator.h"
9 9
10 #include "GrDefaultGeoProcFactory.h"
11 #include "GrPathUtils.h" 10 #include "GrPathUtils.h"
12 11
13 #include "SkChunkAlloc.h" 12 #include "SkChunkAlloc.h"
14 #include "SkGeometry.h" 13 #include "SkGeometry.h"
15 #include "SkPath.h" 14 #include "SkPath.h"
16 15
17 #include <stdio.h> 16 #include <stdio.h>
18 17
19 /* 18 /*
20 * There are six stages to the basic algorithm: 19 * There are six stages to the algorithm:
21 * 20 *
22 * 1) Linearize the path contours into piecewise linear segments (path_to_contou rs()). 21 * 1) Linearize the path contours into piecewise linear segments (path_to_contou rs()).
23 * 2) Build a mesh of edges connecting the vertices (build_edges()). 22 * 2) Build a mesh of edges connecting the vertices (build_edges()).
24 * 3) Sort the vertices in Y (and secondarily in X) (merge_sort()). 23 * 3) Sort the vertices in Y (and secondarily in X) (merge_sort()).
25 * 4) Simplify the mesh by inserting new vertices at intersecting edges (simplif y()). 24 * 4) Simplify the mesh by inserting new vertices at intersecting edges (simplif y()).
26 * 5) Tessellate the simplified mesh into monotone polygons (tessellate()). 25 * 5) Tessellate the simplified mesh into monotone polygons (tessellate()).
27 * 6) Triangulate the monotone polygons directly into a vertex buffer (polys_to_ triangles()). 26 * 6) Triangulate the monotone polygons directly into a vertex buffer (polys_to_ triangles()).
28 * 27 *
29 * For screenspace antialiasing, the algorithm is modified as follows:
30 *
31 * Run steps 1-5 above to produce polygons.
32 * 5b) Apply fill rules to extract boundary contours from the polygons (extract_ boundaries()).
33 * 5c) Simplify boundaries to remove "pointy" vertices which cause inversions (s implify_boundary()).
34 * 5d) Displace edges by half a pixel inward and outward along their normals. In tersect to find
35 * new vertices, and set zero alpha on the exterior and one alpha on the int erior. Build a new
36 * antialiased mesh from those vertices (boundary_to_aa_mesh()).
37 * Run steps 3-6 above on the new mesh, and produce antialiased triangles.
38 *
39 * The vertex sorting in step (3) is a merge sort, since it plays well with the linked list 28 * The vertex sorting in step (3) is a merge sort, since it plays well with the linked list
40 * of vertices (and the necessity of inserting new vertices on intersection). 29 * of vertices (and the necessity of inserting new vertices on intersection).
41 * 30 *
42 * Stages (4) and (5) use an active edge list, which a list of all edges for whi ch the 31 * Stages (4) and (5) use an active edge list, which a list of all edges for whi ch the
43 * sweep line has crossed the top vertex, but not the bottom vertex. It's sorte d 32 * sweep line has crossed the top vertex, but not the bottom vertex. It's sorte d
44 * left-to-right based on the point where both edges are active (when both top v ertices 33 * left-to-right based on the point where both edges are active (when both top v ertices
45 * have been seen, so the "lower" top vertex of the two). If the top vertices ar e equal 34 * have been seen, so the "lower" top vertex of the two). If the top vertices ar e equal
46 * (shared), it's sorted based on the last point where both edges are active, so the 35 * (shared), it's sorted based on the last point where both edges are active, so the
47 * "upper" bottom vertex. 36 * "upper" bottom vertex.
48 * 37 *
(...skipping 85 matching lines...) Expand 10 before | Expand all | Expand 10 after
134 * circularly-linked list of Vertices for each contour. After edge construction, the same Vertices 123 * circularly-linked list of Vertices for each contour. After edge construction, the same Vertices
135 * are re-ordered by the merge sort according to the sweep_lt comparator (usuall y, increasing 124 * are re-ordered by the merge sort according to the sweep_lt comparator (usuall y, increasing
136 * in Y) using the same fPrev/fNext pointers that were used for the contours, to avoid 125 * in Y) using the same fPrev/fNext pointers that were used for the contours, to avoid
137 * reallocation. Finally, MonotonePolys are built containing a circularly-linked list of 126 * reallocation. Finally, MonotonePolys are built containing a circularly-linked list of
138 * Vertices. (Currently, those Vertices are newly-allocated for the MonotonePoly s, since 127 * Vertices. (Currently, those Vertices are newly-allocated for the MonotonePoly s, since
139 * an individual Vertex from the path mesh may belong to multiple 128 * an individual Vertex from the path mesh may belong to multiple
140 * MonotonePolys, so the original Vertices cannot be re-used. 129 * MonotonePolys, so the original Vertices cannot be re-used.
141 */ 130 */
142 131
143 struct Vertex { 132 struct Vertex {
144 Vertex(const SkPoint& point, uint8_t alpha) 133 Vertex(const SkPoint& point)
145 : fPoint(point), fPrev(nullptr), fNext(nullptr) 134 : fPoint(point), fPrev(nullptr), fNext(nullptr)
146 , fFirstEdgeAbove(nullptr), fLastEdgeAbove(nullptr) 135 , fFirstEdgeAbove(nullptr), fLastEdgeAbove(nullptr)
147 , fFirstEdgeBelow(nullptr), fLastEdgeBelow(nullptr) 136 , fFirstEdgeBelow(nullptr), fLastEdgeBelow(nullptr)
148 , fProcessed(false) 137 , fProcessed(false)
149 , fAlpha(alpha)
150 #if LOGGING_ENABLED 138 #if LOGGING_ENABLED
151 , fID (-1.0f) 139 , fID (-1.0f)
152 #endif 140 #endif
153 {} 141 {}
154 SkPoint fPoint; // Vertex position 142 SkPoint fPoint; // Vertex position
155 Vertex* fPrev; // Linked list of contours, then Y-sorted vertices . 143 Vertex* fPrev; // Linked list of contours, then Y-sorted vertices .
156 Vertex* fNext; // " 144 Vertex* fNext; // "
157 Edge* fFirstEdgeAbove; // Linked list of edges above this vertex. 145 Edge* fFirstEdgeAbove; // Linked list of edges above this vertex.
158 Edge* fLastEdgeAbove; // " 146 Edge* fLastEdgeAbove; // "
159 Edge* fFirstEdgeBelow; // Linked list of edges below this vertex. 147 Edge* fFirstEdgeBelow; // Linked list of edges below this vertex.
160 Edge* fLastEdgeBelow; // " 148 Edge* fLastEdgeBelow; // "
161 bool fProcessed; // Has this vertex been seen in simplify()? 149 bool fProcessed; // Has this vertex been seen in simplify()?
162 uint8_t fAlpha;
163 #if LOGGING_ENABLED 150 #if LOGGING_ENABLED
164 float fID; // Identifier used for logging. 151 float fID; // Identifier used for logging.
165 #endif 152 #endif
166 }; 153 };
167 154
168 /******************************************************************************* ********/ 155 /******************************************************************************* ********/
169 156
170 struct AAParams {
171 bool fTweakAlpha;
172 GrColor fColor;
173 };
174
175 typedef bool (*CompareFunc)(const SkPoint& a, const SkPoint& b); 157 typedef bool (*CompareFunc)(const SkPoint& a, const SkPoint& b);
176 158
177 struct Comparator { 159 struct Comparator {
178 CompareFunc sweep_lt; 160 CompareFunc sweep_lt;
179 CompareFunc sweep_gt; 161 CompareFunc sweep_gt;
180 }; 162 };
181 163
182 bool sweep_lt_horiz(const SkPoint& a, const SkPoint& b) { 164 bool sweep_lt_horiz(const SkPoint& a, const SkPoint& b) {
183 return a.fX == b.fX ? a.fY > b.fY : a.fX < b.fX; 165 return a.fX == b.fX ? a.fY > b.fY : a.fX < b.fX;
184 } 166 }
185 167
186 bool sweep_lt_vert(const SkPoint& a, const SkPoint& b) { 168 bool sweep_lt_vert(const SkPoint& a, const SkPoint& b) {
187 return a.fY == b.fY ? a.fX < b.fX : a.fY < b.fY; 169 return a.fY == b.fY ? a.fX < b.fX : a.fY < b.fY;
188 } 170 }
189 171
190 bool sweep_gt_horiz(const SkPoint& a, const SkPoint& b) { 172 bool sweep_gt_horiz(const SkPoint& a, const SkPoint& b) {
191 return a.fX == b.fX ? a.fY < b.fY : a.fX > b.fX; 173 return a.fX == b.fX ? a.fY < b.fY : a.fX > b.fX;
192 } 174 }
193 175
194 bool sweep_gt_vert(const SkPoint& a, const SkPoint& b) { 176 bool sweep_gt_vert(const SkPoint& a, const SkPoint& b) {
195 return a.fY == b.fY ? a.fX > b.fX : a.fY > b.fY; 177 return a.fY == b.fY ? a.fX > b.fX : a.fY > b.fY;
196 } 178 }
197 179
198 inline void* emit_vertex(Vertex* v, const AAParams* aaParams, void* data) { 180 inline SkPoint* emit_vertex(Vertex* v, SkPoint* data) {
199 if (!aaParams) { 181 *data++ = v->fPoint;
200 SkPoint* d = static_cast<SkPoint*>(data); 182 return data;
201 *d++ = v->fPoint;
202 return d;
203 }
204 if (aaParams->fTweakAlpha) {
205 auto d = static_cast<GrDefaultGeoProcFactory::PositionColorAttr*>(data);
206 d->fPosition = v->fPoint;
207 d->fColor = SkAlphaMulQ(aaParams->fColor, v->fAlpha);
208 d++;
209 return d;
210 }
211 auto d = static_cast<GrDefaultGeoProcFactory::PositionColorCoverageAttr*>(da ta);
212 d->fPosition = v->fPoint;
213 d->fColor = aaParams->fColor;
214 d->fCoverage = GrNormalizeByteToFloat(v->fAlpha);
215 d++;
216 return d;
217 } 183 }
218 184
219 void* emit_triangle(Vertex* v0, Vertex* v1, Vertex* v2, const AAParams* aaParams , void* data) { 185 SkPoint* emit_triangle(Vertex* v0, Vertex* v1, Vertex* v2, SkPoint* data) {
220 #if TESSELLATOR_WIREFRAME 186 #if WIREFRAME
221 data = emit_vertex(v0, aaParams, data); 187 data = emit_vertex(v0, data);
222 data = emit_vertex(v1, aaParams, data); 188 data = emit_vertex(v1, data);
223 data = emit_vertex(v1, aaParams, data); 189 data = emit_vertex(v1, data);
224 data = emit_vertex(v2, aaParams, data); 190 data = emit_vertex(v2, data);
225 data = emit_vertex(v2, aaParams, data); 191 data = emit_vertex(v2, data);
226 data = emit_vertex(v0, aaParams, data); 192 data = emit_vertex(v0, data);
227 #else 193 #else
228 data = emit_vertex(v0, aaParams, data); 194 data = emit_vertex(v0, data);
229 data = emit_vertex(v1, aaParams, data); 195 data = emit_vertex(v1, data);
230 data = emit_vertex(v2, aaParams, data); 196 data = emit_vertex(v2, data);
231 #endif 197 #endif
232 return data; 198 return data;
233 } 199 }
234 200
201 struct EdgeList {
202 EdgeList() : fHead(nullptr), fTail(nullptr) {}
203 Edge* fHead;
204 Edge* fTail;
205 };
206
235 struct VertexList { 207 struct VertexList {
236 VertexList() : fHead(nullptr), fTail(nullptr) {} 208 VertexList() : fHead(nullptr), fTail(nullptr) {}
237 Vertex* fHead; 209 Vertex* fHead;
238 Vertex* fTail; 210 Vertex* fTail;
239 void insert(Vertex* v, Vertex* prev, Vertex* next) { 211 void insert(Vertex* v, Vertex* prev, Vertex* next) {
240 list_insert<Vertex, &Vertex::fPrev, &Vertex::fNext>(v, prev, next, &fHea d, &fTail); 212 list_insert<Vertex, &Vertex::fPrev, &Vertex::fNext>(v, prev, next, &fHea d, &fTail);
241 } 213 }
242 void append(Vertex* v) { 214 void append(Vertex* v) {
243 insert(v, fTail, nullptr); 215 insert(v, fTail, nullptr);
244 } 216 }
245 void prepend(Vertex* v) { 217 void prepend(Vertex* v) {
246 insert(v, nullptr, fHead); 218 insert(v, nullptr, fHead);
247 } 219 }
248 void close() {
249 if (fHead && fTail) {
250 fTail->fNext = fHead;
251 fHead->fPrev = fTail;
252 }
253 }
254 }; 220 };
255 221
256 // Round to nearest quarter-pixel. This is used for screenspace tessellation.
257
258 inline void round(SkPoint* p) {
259 p->fX = SkScalarRoundToScalar(p->fX * SkFloatToScalar(4.0f)) * SkFloatToScal ar(0.25f);
260 p->fY = SkScalarRoundToScalar(p->fY * SkFloatToScalar(4.0f)) * SkFloatToScal ar(0.25f);
261 }
262
263 /** 222 /**
264 * An Edge joins a top Vertex to a bottom Vertex. Edge ordering for the list of "edges above" and 223 * An Edge joins a top Vertex to a bottom Vertex. Edge ordering for the list of "edges above" and
265 * "edge below" a vertex as well as for the active edge list is handled by isLef tOf()/isRightOf(). 224 * "edge below" a vertex as well as for the active edge list is handled by isLef tOf()/isRightOf().
266 * Note that an Edge will give occasionally dist() != 0 for its own endpoints (b ecause floating 225 * Note that an Edge will give occasionally dist() != 0 for its own endpoints (b ecause floating
267 * point). For speed, that case is only tested by the callers which require it ( e.g., 226 * point). For speed, that case is only tested by the callers which require it ( e.g.,
268 * cleanup_active_edges()). Edges also handle checking for intersection with oth er edges. 227 * cleanup_active_edges()). Edges also handle checking for intersection with oth er edges.
269 * Currently, this converts the edges to the parametric form, in order to avoid doing a division 228 * Currently, this converts the edges to the parametric form, in order to avoid doing a division
270 * until an intersection has been confirmed. This is slightly slower in the "fou nd" case, but 229 * until an intersection has been confirmed. This is slightly slower in the "fou nd" case, but
271 * a lot faster in the "not found" case. 230 * a lot faster in the "not found" case.
272 * 231 *
(...skipping 81 matching lines...) Expand 10 before | Expand all | Expand 10 after
354 if (denom > 0.0 ? (sNumer < 0.0 || sNumer > denom || tNumer < 0.0 || tNu mer > denom) 313 if (denom > 0.0 ? (sNumer < 0.0 || sNumer > denom || tNumer < 0.0 || tNu mer > denom)
355 : (sNumer > 0.0 || sNumer < denom || tNumer > 0.0 || tNu mer < denom)) { 314 : (sNumer > 0.0 || sNumer < denom || tNumer > 0.0 || tNu mer < denom)) {
356 return false; 315 return false;
357 } 316 }
358 double s = sNumer / denom; 317 double s = sNumer / denom;
359 SkASSERT(s >= 0.0 && s <= 1.0); 318 SkASSERT(s >= 0.0 && s <= 1.0);
360 p->fX = SkDoubleToScalar(fTop->fPoint.fX + s * fDX); 319 p->fX = SkDoubleToScalar(fTop->fPoint.fX + s * fDX);
361 p->fY = SkDoubleToScalar(fTop->fPoint.fY + s * fDY); 320 p->fY = SkDoubleToScalar(fTop->fPoint.fY + s * fDY);
362 return true; 321 return true;
363 } 322 }
364 }; 323 bool isActive(EdgeList* activeEdges) const {
365 324 return activeEdges && (fLeft || fRight || activeEdges->fHead == this);
366 struct EdgeList {
367 EdgeList() : fHead(nullptr), fTail(nullptr), fNext(nullptr), fCount(0) {}
368 Edge* fHead;
369 Edge* fTail;
370 EdgeList* fNext;
371 int fCount;
372 void insert(Edge* edge, Edge* prev, Edge* next) {
373 list_insert<Edge, &Edge::fLeft, &Edge::fRight>(edge, prev, next, &fHead, &fTail);
374 fCount++;
375 }
376 void append(Edge* e) {
377 insert(e, fTail, nullptr);
378 }
379 void remove(Edge* edge) {
380 list_remove<Edge, &Edge::fLeft, &Edge::fRight>(edge, &fHead, &fTail);
381 fCount--;
382 }
383 void close() {
384 if (fHead && fTail) {
385 fTail->fRight = fHead;
386 fHead->fLeft = fTail;
387 }
388 }
389 bool contains(Edge* edge) const {
390 return edge->fLeft || edge->fRight || fHead == edge;
391 } 325 }
392 }; 326 };
393 327
394 /******************************************************************************* ********/ 328 /******************************************************************************* ********/
395 329
396 struct Poly { 330 struct Poly {
397 Poly(Vertex* v, int winding) 331 Poly(Vertex* v, int winding)
398 : fFirstVertex(v) 332 : fFirstVertex(v)
399 , fWinding(winding) 333 , fWinding(winding)
400 , fHead(nullptr) 334 , fHead(nullptr)
(...skipping 30 matching lines...) Expand all
431 edge, fLastEdge, nullptr, &fFirstEdge, &fLastEdge); 365 edge, fLastEdge, nullptr, &fFirstEdge, &fLastEdge);
432 edge->fUsedInRightPoly = true; 366 edge->fUsedInRightPoly = true;
433 } else { 367 } else {
434 SkASSERT(!edge->fUsedInLeftPoly); 368 SkASSERT(!edge->fUsedInLeftPoly);
435 list_insert<Edge, &Edge::fLeftPolyPrev, &Edge::fLeftPolyNext>( 369 list_insert<Edge, &Edge::fLeftPolyPrev, &Edge::fLeftPolyNext>(
436 edge, fLastEdge, nullptr, &fFirstEdge, &fLastEdge); 370 edge, fLastEdge, nullptr, &fFirstEdge, &fLastEdge);
437 edge->fUsedInLeftPoly = true; 371 edge->fUsedInLeftPoly = true;
438 } 372 }
439 } 373 }
440 374
441 void* emit(const AAParams* aaParams, void* data) { 375 SkPoint* emit(SkPoint* data) {
442 Edge* e = fFirstEdge; 376 Edge* e = fFirstEdge;
443 e->fTop->fPrev = e->fTop->fNext = nullptr; 377 e->fTop->fPrev = e->fTop->fNext = nullptr;
444 VertexList vertices; 378 VertexList vertices;
445 vertices.append(e->fTop); 379 vertices.append(e->fTop);
446 while (e != nullptr) { 380 while (e != nullptr) {
447 e->fBottom->fPrev = e->fBottom->fNext = nullptr; 381 e->fBottom->fPrev = e->fBottom->fNext = nullptr;
448 if (kRight_Side == fSide) { 382 if (kRight_Side == fSide) {
449 vertices.append(e->fBottom); 383 vertices.append(e->fBottom);
450 e = e->fRightPolyNext; 384 e = e->fRightPolyNext;
451 } else { 385 } else {
452 vertices.prepend(e->fBottom); 386 vertices.prepend(e->fBottom);
453 e = e->fLeftPolyNext; 387 e = e->fLeftPolyNext;
454 } 388 }
455 } 389 }
456 Vertex* first = vertices.fHead; 390 Vertex* first = vertices.fHead;
457 Vertex* v = first->fNext; 391 Vertex* v = first->fNext;
458 while (v != vertices.fTail) { 392 while (v != vertices.fTail) {
459 SkASSERT(v && v->fPrev && v->fNext); 393 SkASSERT(v && v->fPrev && v->fNext);
460 Vertex* prev = v->fPrev; 394 Vertex* prev = v->fPrev;
461 Vertex* curr = v; 395 Vertex* curr = v;
462 Vertex* next = v->fNext; 396 Vertex* next = v->fNext;
463 double ax = static_cast<double>(curr->fPoint.fX) - prev->fPoint. fX; 397 double ax = static_cast<double>(curr->fPoint.fX) - prev->fPoint. fX;
464 double ay = static_cast<double>(curr->fPoint.fY) - prev->fPoint. fY; 398 double ay = static_cast<double>(curr->fPoint.fY) - prev->fPoint. fY;
465 double bx = static_cast<double>(next->fPoint.fX) - curr->fPoint. fX; 399 double bx = static_cast<double>(next->fPoint.fX) - curr->fPoint. fX;
466 double by = static_cast<double>(next->fPoint.fY) - curr->fPoint. fY; 400 double by = static_cast<double>(next->fPoint.fY) - curr->fPoint. fY;
467 if (ax * by - ay * bx >= 0.0) { 401 if (ax * by - ay * bx >= 0.0) {
468 data = emit_triangle(prev, curr, next, aaParams, data); 402 data = emit_triangle(prev, curr, next, data);
469 v->fPrev->fNext = v->fNext; 403 v->fPrev->fNext = v->fNext;
470 v->fNext->fPrev = v->fPrev; 404 v->fNext->fPrev = v->fPrev;
471 if (v->fPrev == first) { 405 if (v->fPrev == first) {
472 v = v->fNext; 406 v = v->fNext;
473 } else { 407 } else {
474 v = v->fPrev; 408 v = v->fPrev;
475 } 409 }
476 } else { 410 } else {
477 v = v->fNext; 411 v = v->fNext;
478 } 412 }
(...skipping 35 matching lines...) Expand 10 before | Expand all | Expand 10 after
514 poly = partner; 448 poly = partner;
515 } else { 449 } else {
516 MonotonePoly* m = ALLOC_NEW(MonotonePoly, (e, side), alloc); 450 MonotonePoly* m = ALLOC_NEW(MonotonePoly, (e, side), alloc);
517 m->fPrev = fTail; 451 m->fPrev = fTail;
518 fTail->fNext = m; 452 fTail->fNext = m;
519 fTail = m; 453 fTail = m;
520 } 454 }
521 } 455 }
522 return poly; 456 return poly;
523 } 457 }
524 void* emit(const AAParams* aaParams, void *data) { 458 SkPoint* emit(SkPoint *data) {
525 if (fCount < 3) { 459 if (fCount < 3) {
526 return data; 460 return data;
527 } 461 }
528 LOG("emit() %d, size %d\n", fID, fCount); 462 LOG("emit() %d, size %d\n", fID, fCount);
529 for (MonotonePoly* m = fHead; m != nullptr; m = m->fNext) { 463 for (MonotonePoly* m = fHead; m != nullptr; m = m->fNext) {
530 data = m->emit(aaParams, data); 464 data = m->emit(data);
531 } 465 }
532 return data; 466 return data;
533 } 467 }
534 Vertex* lastVertex() const { return fTail ? fTail->fLastEdge->fBottom : fFir stVertex; } 468 Vertex* lastVertex() const { return fTail ? fTail->fLastEdge->fBottom : fFir stVertex; }
535 Vertex* fFirstVertex; 469 Vertex* fFirstVertex;
536 int fWinding; 470 int fWinding;
537 MonotonePoly* fHead; 471 MonotonePoly* fHead;
538 MonotonePoly* fTail; 472 MonotonePoly* fTail;
539 Poly* fNext; 473 Poly* fNext;
540 Poly* fPartner; 474 Poly* fPartner;
541 int fCount; 475 int fCount;
542 #if LOGGING_ENABLED 476 #if LOGGING_ENABLED
543 int fID; 477 int fID;
544 #endif 478 #endif
545 }; 479 };
546 480
547 /******************************************************************************* ********/ 481 /******************************************************************************* ********/
548 482
549 bool coincident(const SkPoint& a, const SkPoint& b) { 483 bool coincident(const SkPoint& a, const SkPoint& b) {
550 return a == b; 484 return a == b;
551 } 485 }
552 486
553 Poly* new_poly(Poly** head, Vertex* v, int winding, SkChunkAlloc& alloc) { 487 Poly* new_poly(Poly** head, Vertex* v, int winding, SkChunkAlloc& alloc) {
554 Poly* poly = ALLOC_NEW(Poly, (v, winding), alloc); 488 Poly* poly = ALLOC_NEW(Poly, (v, winding), alloc);
555 poly->fNext = *head; 489 poly->fNext = *head;
556 *head = poly; 490 *head = poly;
557 return poly; 491 return poly;
558 } 492 }
559 493
560 EdgeList* new_contour(EdgeList** head, SkChunkAlloc& alloc) {
561 EdgeList* contour = ALLOC_NEW(EdgeList, (), alloc);
562 contour->fNext = *head;
563 *head = contour;
564 return contour;
565 }
566
567 Vertex* append_point_to_contour(const SkPoint& p, Vertex* prev, Vertex** head, 494 Vertex* append_point_to_contour(const SkPoint& p, Vertex* prev, Vertex** head,
568 SkChunkAlloc& alloc) { 495 SkChunkAlloc& alloc) {
569 Vertex* v = ALLOC_NEW(Vertex, (p, 255), alloc); 496 Vertex* v = ALLOC_NEW(Vertex, (p), alloc);
570 #if LOGGING_ENABLED 497 #if LOGGING_ENABLED
571 static float gID = 0.0f; 498 static float gID = 0.0f;
572 v->fID = gID++; 499 v->fID = gID++;
573 #endif 500 #endif
574 if (prev) { 501 if (prev) {
575 prev->fNext = v; 502 prev->fNext = v;
576 v->fPrev = prev; 503 v->fPrev = prev;
577 } else { 504 } else {
578 *head = v; 505 *head = v;
579 } 506 }
(...skipping 64 matching lines...) Expand 10 before | Expand all | Expand 10 after
644 571
645 SkPoint pts[4]; 572 SkPoint pts[4];
646 bool done = false; 573 bool done = false;
647 *isLinear = true; 574 *isLinear = true;
648 SkPath::Iter iter(path, false); 575 SkPath::Iter iter(path, false);
649 Vertex* prev = nullptr; 576 Vertex* prev = nullptr;
650 Vertex* head = nullptr; 577 Vertex* head = nullptr;
651 if (path.isInverseFillType()) { 578 if (path.isInverseFillType()) {
652 SkPoint quad[4]; 579 SkPoint quad[4];
653 clipBounds.toQuad(quad); 580 clipBounds.toQuad(quad);
654 for (int i = 0; i < 4; i++) { 581 for (int i = 3; i >= 0; i--) {
655 prev = append_point_to_contour(quad[i], prev, &head, alloc); 582 prev = append_point_to_contour(quad[i], prev, &head, alloc);
656 } 583 }
657 head->fPrev = prev; 584 head->fPrev = prev;
658 prev->fNext = head; 585 prev->fNext = head;
659 *contours++ = head; 586 *contours++ = head;
660 head = prev = nullptr; 587 head = prev = nullptr;
661 } 588 }
662 SkAutoConicToQuads converter; 589 SkAutoConicToQuads converter;
663 while (!done) { 590 while (!done) {
664 SkPath::Verb verb = iter.next(pts); 591 SkPath::Verb verb = iter.next(pts);
(...skipping 50 matching lines...) Expand 10 before | Expand all | Expand 10 after
715 head->fPrev = prev; 642 head->fPrev = prev;
716 prev->fNext = head; 643 prev->fNext = head;
717 *contours++ = head; 644 *contours++ = head;
718 } 645 }
719 done = true; 646 done = true;
720 break; 647 break;
721 } 648 }
722 } 649 }
723 } 650 }
724 651
725 inline bool apply_fill_type(SkPath::FillType fillType, Poly* poly) { 652 inline bool apply_fill_type(SkPath::FillType fillType, int winding) {
726 if (!poly) {
727 return false;
728 }
729 int winding = poly->fWinding;
730 switch (fillType) { 653 switch (fillType) {
731 case SkPath::kWinding_FillType: 654 case SkPath::kWinding_FillType:
732 return winding != 0; 655 return winding != 0;
733 case SkPath::kEvenOdd_FillType: 656 case SkPath::kEvenOdd_FillType:
734 return (winding & 1) != 0; 657 return (winding & 1) != 0;
735 case SkPath::kInverseWinding_FillType: 658 case SkPath::kInverseWinding_FillType:
736 return winding == -1; 659 return winding == 1;
737 case SkPath::kInverseEvenOdd_FillType: 660 case SkPath::kInverseEvenOdd_FillType:
738 return (winding & 1) == 1; 661 return (winding & 1) == 1;
739 default: 662 default:
740 SkASSERT(false); 663 SkASSERT(false);
741 return false; 664 return false;
742 } 665 }
743 } 666 }
744 667
745 Edge* new_edge(Vertex* prev, Vertex* next, SkChunkAlloc& alloc, Comparator& c, 668 Edge* new_edge(Vertex* prev, Vertex* next, SkChunkAlloc& alloc, Comparator& c) {
746 int winding_scale = 1) { 669 int winding = c.sweep_lt(prev->fPoint, next->fPoint) ? 1 : -1;
747 int winding = c.sweep_lt(prev->fPoint, next->fPoint) ? winding_scale : -wind ing_scale;
748 Vertex* top = winding < 0 ? next : prev; 670 Vertex* top = winding < 0 ? next : prev;
749 Vertex* bottom = winding < 0 ? prev : next; 671 Vertex* bottom = winding < 0 ? prev : next;
750 return ALLOC_NEW(Edge, (top, bottom, winding), alloc); 672 return ALLOC_NEW(Edge, (top, bottom, winding), alloc);
751 } 673 }
752 674
753 void remove_edge(Edge* edge, EdgeList* edges) { 675 void remove_edge(Edge* edge, EdgeList* edges) {
754 LOG("removing edge %g -> %g\n", edge->fTop->fID, edge->fBottom->fID); 676 LOG("removing edge %g -> %g\n", edge->fTop->fID, edge->fBottom->fID);
755 SkASSERT(edges->contains(edge)); 677 SkASSERT(edge->isActive(edges));
756 edges->remove(edge); 678 list_remove<Edge, &Edge::fLeft, &Edge::fRight>(edge, &edges->fHead, &edges-> fTail);
757 } 679 }
758 680
759 void insert_edge(Edge* edge, Edge* prev, EdgeList* edges) { 681 void insert_edge(Edge* edge, Edge* prev, EdgeList* edges) {
760 LOG("inserting edge %g -> %g\n", edge->fTop->fID, edge->fBottom->fID); 682 LOG("inserting edge %g -> %g\n", edge->fTop->fID, edge->fBottom->fID);
761 SkASSERT(!edges->contains(edge)); 683 SkASSERT(!edge->isActive(edges));
762 Edge* next = prev ? prev->fRight : edges->fHead; 684 Edge* next = prev ? prev->fRight : edges->fHead;
763 edges->insert(edge, prev, next); 685 list_insert<Edge, &Edge::fLeft, &Edge::fRight>(edge, prev, next, &edges->fHe ad, &edges->fTail);
764 } 686 }
765 687
766 void find_enclosing_edges(Vertex* v, EdgeList* edges, Edge** left, Edge** right) { 688 void find_enclosing_edges(Vertex* v, EdgeList* edges, Edge** left, Edge** right) {
767 if (v->fFirstEdgeAbove) { 689 if (v->fFirstEdgeAbove) {
768 *left = v->fFirstEdgeAbove->fLeft; 690 *left = v->fFirstEdgeAbove->fLeft;
769 *right = v->fLastEdgeAbove->fRight; 691 *right = v->fLastEdgeAbove->fRight;
770 return; 692 return;
771 } 693 }
772 Edge* next = nullptr; 694 Edge* next = nullptr;
773 Edge* prev; 695 Edge* prev;
(...skipping 19 matching lines...) Expand all
793 edge->isLeftOf(next->fBottom))) { 715 edge->isLeftOf(next->fBottom))) {
794 break; 716 break;
795 } 717 }
796 prev = next; 718 prev = next;
797 } 719 }
798 *left = prev; 720 *left = prev;
799 *right = next; 721 *right = next;
800 } 722 }
801 723
802 void fix_active_state(Edge* edge, EdgeList* activeEdges, Comparator& c) { 724 void fix_active_state(Edge* edge, EdgeList* activeEdges, Comparator& c) {
803 if (activeEdges && activeEdges->contains(edge)) { 725 if (edge->isActive(activeEdges)) {
804 if (edge->fBottom->fProcessed || !edge->fTop->fProcessed) { 726 if (edge->fBottom->fProcessed || !edge->fTop->fProcessed) {
805 remove_edge(edge, activeEdges); 727 remove_edge(edge, activeEdges);
806 } 728 }
807 } else if (edge->fTop->fProcessed && !edge->fBottom->fProcessed) { 729 } else if (edge->fTop->fProcessed && !edge->fBottom->fProcessed) {
808 Edge* left; 730 Edge* left;
809 Edge* right; 731 Edge* right;
810 find_enclosing_edges(edge, activeEdges, c, &left, &right); 732 find_enclosing_edges(edge, activeEdges, c, &left, &right);
811 insert_edge(edge, left, activeEdges); 733 insert_edge(edge, left, activeEdges);
812 } 734 }
813 } 735 }
(...skipping 48 matching lines...) Expand 10 before | Expand all | Expand 10 after
862 edge, &edge->fTop->fFirstEdgeBelow, &edge->fTop->fLastEdgeBelow); 784 edge, &edge->fTop->fFirstEdgeBelow, &edge->fTop->fLastEdgeBelow);
863 } 785 }
864 786
865 void erase_edge_if_zero_winding(Edge* edge, EdgeList* edges) { 787 void erase_edge_if_zero_winding(Edge* edge, EdgeList* edges) {
866 if (edge->fWinding != 0) { 788 if (edge->fWinding != 0) {
867 return; 789 return;
868 } 790 }
869 LOG("erasing edge (%g -> %g)\n", edge->fTop->fID, edge->fBottom->fID); 791 LOG("erasing edge (%g -> %g)\n", edge->fTop->fID, edge->fBottom->fID);
870 remove_edge_above(edge); 792 remove_edge_above(edge);
871 remove_edge_below(edge); 793 remove_edge_below(edge);
872 if (edges && edges->contains(edge)) { 794 if (edge->isActive(edges)) {
873 remove_edge(edge, edges); 795 remove_edge(edge, edges);
874 } 796 }
875 } 797 }
876 798
877 void merge_collinear_edges(Edge* edge, EdgeList* activeEdges, Comparator& c); 799 void merge_collinear_edges(Edge* edge, EdgeList* activeEdges, Comparator& c);
878 800
879 void set_top(Edge* edge, Vertex* v, EdgeList* activeEdges, Comparator& c) { 801 void set_top(Edge* edge, Vertex* v, EdgeList* activeEdges, Comparator& c) {
880 remove_edge_below(edge); 802 remove_edge_below(edge);
881 edge->fTop = v; 803 edge->fTop = v;
882 edge->recompute(); 804 edge->recompute();
(...skipping 116 matching lines...) Expand 10 before | Expand all | Expand 10 after
999 Edge* newEdge = ALLOC_NEW(Edge, (v, edge->fBottom, edge->fWinding), allo c); 921 Edge* newEdge = ALLOC_NEW(Edge, (v, edge->fBottom, edge->fWinding), allo c);
1000 insert_edge_below(newEdge, v, c); 922 insert_edge_below(newEdge, v, c);
1001 insert_edge_above(newEdge, edge->fBottom, c); 923 insert_edge_above(newEdge, edge->fBottom, c);
1002 set_bottom(edge, v, activeEdges, c); 924 set_bottom(edge, v, activeEdges, c);
1003 cleanup_active_edges(edge, activeEdges, c, alloc); 925 cleanup_active_edges(edge, activeEdges, c, alloc);
1004 fix_active_state(newEdge, activeEdges, c); 926 fix_active_state(newEdge, activeEdges, c);
1005 merge_collinear_edges(newEdge, activeEdges, c); 927 merge_collinear_edges(newEdge, activeEdges, c);
1006 } 928 }
1007 } 929 }
1008 930
1009 Edge* connect(Vertex* prev, Vertex* next, SkChunkAlloc& alloc, Comparator c,
1010 int winding_scale = 1) {
1011 Edge* edge = new_edge(prev, next, alloc, c, winding_scale);
1012 if (edge->fWinding > 0) {
1013 insert_edge_below(edge, prev, c);
1014 insert_edge_above(edge, next, c);
1015 } else {
1016 insert_edge_below(edge, next, c);
1017 insert_edge_above(edge, prev, c);
1018 }
1019 merge_collinear_edges(edge, nullptr, c);
1020 return edge;
1021 }
1022
1023 void merge_vertices(Vertex* src, Vertex* dst, Vertex** head, Comparator& c, SkCh unkAlloc& alloc) { 931 void merge_vertices(Vertex* src, Vertex* dst, Vertex** head, Comparator& c, SkCh unkAlloc& alloc) {
1024 LOG("found coincident verts at %g, %g; merging %g into %g\n", src->fPoint.fX , src->fPoint.fY, 932 LOG("found coincident verts at %g, %g; merging %g into %g\n", src->fPoint.fX , src->fPoint.fY,
1025 src->fID, dst->fID); 933 src->fID, dst->fID);
1026 dst->fAlpha = SkTMax(src->fAlpha, dst->fAlpha);
1027 for (Edge* edge = src->fFirstEdgeAbove; edge;) { 934 for (Edge* edge = src->fFirstEdgeAbove; edge;) {
1028 Edge* next = edge->fNextEdgeAbove; 935 Edge* next = edge->fNextEdgeAbove;
1029 set_bottom(edge, dst, nullptr, c); 936 set_bottom(edge, dst, nullptr, c);
1030 edge = next; 937 edge = next;
1031 } 938 }
1032 for (Edge* edge = src->fFirstEdgeBelow; edge;) { 939 for (Edge* edge = src->fFirstEdgeBelow; edge;) {
1033 Edge* next = edge->fNextEdgeBelow; 940 Edge* next = edge->fNextEdgeBelow;
1034 set_top(edge, dst, nullptr, c); 941 set_top(edge, dst, nullptr, c);
1035 edge = next; 942 edge = next;
1036 } 943 }
1037 list_remove<Vertex, &Vertex::fPrev, &Vertex::fNext>(src, head, nullptr); 944 list_remove<Vertex, &Vertex::fPrev, &Vertex::fNext>(src, head, nullptr);
1038 } 945 }
1039 946
1040 uint8_t max_edge_alpha(Edge* a, Edge* b) {
1041 return SkTMax(SkTMax(a->fTop->fAlpha, a->fBottom->fAlpha),
1042 SkTMax(b->fTop->fAlpha, b->fBottom->fAlpha));
1043 }
1044
1045 Vertex* check_for_intersection(Edge* edge, Edge* other, EdgeList* activeEdges, C omparator& c, 947 Vertex* check_for_intersection(Edge* edge, Edge* other, EdgeList* activeEdges, C omparator& c,
1046 SkChunkAlloc& alloc) { 948 SkChunkAlloc& alloc) {
1047 SkPoint p; 949 SkPoint p;
1048 if (!edge || !other) { 950 if (!edge || !other) {
1049 return nullptr; 951 return nullptr;
1050 } 952 }
1051 if (edge->intersect(*other, &p)) { 953 if (edge->intersect(*other, &p)) {
1052 Vertex* v; 954 Vertex* v;
1053 LOG("found intersection, pt is %g, %g\n", p.fX, p.fY); 955 LOG("found intersection, pt is %g, %g\n", p.fX, p.fY);
1054 if (p == edge->fTop->fPoint || c.sweep_lt(p, edge->fTop->fPoint)) { 956 if (p == edge->fTop->fPoint || c.sweep_lt(p, edge->fTop->fPoint)) {
(...skipping 15 matching lines...) Expand all
1070 } 972 }
1071 while (c.sweep_lt(nextV->fPoint, p)) { 973 while (c.sweep_lt(nextV->fPoint, p)) {
1072 nextV = nextV->fNext; 974 nextV = nextV->fNext;
1073 } 975 }
1074 Vertex* prevV = nextV->fPrev; 976 Vertex* prevV = nextV->fPrev;
1075 if (coincident(prevV->fPoint, p)) { 977 if (coincident(prevV->fPoint, p)) {
1076 v = prevV; 978 v = prevV;
1077 } else if (coincident(nextV->fPoint, p)) { 979 } else if (coincident(nextV->fPoint, p)) {
1078 v = nextV; 980 v = nextV;
1079 } else { 981 } else {
1080 uint8_t alpha = max_edge_alpha(edge, other); 982 v = ALLOC_NEW(Vertex, (p), alloc);
1081 v = ALLOC_NEW(Vertex, (p, alpha), alloc);
1082 LOG("inserting between %g (%g, %g) and %g (%g, %g)\n", 983 LOG("inserting between %g (%g, %g) and %g (%g, %g)\n",
1083 prevV->fID, prevV->fPoint.fX, prevV->fPoint.fY, 984 prevV->fID, prevV->fPoint.fX, prevV->fPoint.fY,
1084 nextV->fID, nextV->fPoint.fX, nextV->fPoint.fY); 985 nextV->fID, nextV->fPoint.fX, nextV->fPoint.fY);
1085 #if LOGGING_ENABLED 986 #if LOGGING_ENABLED
1086 v->fID = (nextV->fID + prevV->fID) * 0.5f; 987 v->fID = (nextV->fID + prevV->fID) * 0.5f;
1087 #endif 988 #endif
1088 v->fPrev = prevV; 989 v->fPrev = prevV;
1089 v->fNext = nextV; 990 v->fNext = nextV;
1090 prevV->fNext = v; 991 prevV->fNext = v;
1091 nextV->fPrev = v; 992 nextV->fPrev = v;
1092 } 993 }
1093 split_edge(edge, v, activeEdges, c, alloc); 994 split_edge(edge, v, activeEdges, c, alloc);
1094 split_edge(other, v, activeEdges, c, alloc); 995 split_edge(other, v, activeEdges, c, alloc);
1095 } 996 }
1096 return v; 997 return v;
1097 } 998 }
1098 return nullptr; 999 return nullptr;
1099 } 1000 }
1100 1001
1101 void sanitize_contours(Vertex** contours, int contourCnt, bool approximate) { 1002 void sanitize_contours(Vertex** contours, int contourCnt) {
1102 for (int i = 0; i < contourCnt; ++i) { 1003 for (int i = 0; i < contourCnt; ++i) {
1103 SkASSERT(contours[i]); 1004 SkASSERT(contours[i]);
1104 for (Vertex* v = contours[i];;) { 1005 for (Vertex* v = contours[i];;) {
1105 if (approximate) {
1106 round(&v->fPoint);
1107 }
1108 if (coincident(v->fPrev->fPoint, v->fPoint)) { 1006 if (coincident(v->fPrev->fPoint, v->fPoint)) {
1109 LOG("vertex %g,%g coincident; removing\n", v->fPoint.fX, v->fPoi nt.fY); 1007 LOG("vertex %g,%g coincident; removing\n", v->fPoint.fX, v->fPoi nt.fY);
1110 if (v->fPrev == v) { 1008 if (v->fPrev == v) {
1111 contours[i] = nullptr; 1009 contours[i] = nullptr;
1112 break; 1010 break;
1113 } 1011 }
1114 v->fPrev->fNext = v->fNext; 1012 v->fPrev->fNext = v->fNext;
1115 v->fNext->fPrev = v->fPrev; 1013 v->fNext->fPrev = v->fPrev;
1116 if (contours[i] == v) { 1014 if (contours[i] == v) {
1117 contours[i] = v->fNext; 1015 contours[i] = v->fNext;
(...skipping 19 matching lines...) Expand all
1137 } 1035 }
1138 1036
1139 // Stage 2: convert the contours to a mesh of edges connecting the vertices. 1037 // Stage 2: convert the contours to a mesh of edges connecting the vertices.
1140 1038
1141 Vertex* build_edges(Vertex** contours, int contourCnt, Comparator& c, SkChunkAll oc& alloc) { 1039 Vertex* build_edges(Vertex** contours, int contourCnt, Comparator& c, SkChunkAll oc& alloc) {
1142 Vertex* vertices = nullptr; 1040 Vertex* vertices = nullptr;
1143 Vertex* prev = nullptr; 1041 Vertex* prev = nullptr;
1144 for (int i = 0; i < contourCnt; ++i) { 1042 for (int i = 0; i < contourCnt; ++i) {
1145 for (Vertex* v = contours[i]; v != nullptr;) { 1043 for (Vertex* v = contours[i]; v != nullptr;) {
1146 Vertex* vNext = v->fNext; 1044 Vertex* vNext = v->fNext;
1147 connect(v->fPrev, v, alloc, c); 1045 Edge* edge = new_edge(v->fPrev, v, alloc, c);
1046 if (edge->fWinding > 0) {
1047 insert_edge_below(edge, v->fPrev, c);
1048 insert_edge_above(edge, v, c);
1049 } else {
1050 insert_edge_below(edge, v, c);
1051 insert_edge_above(edge, v->fPrev, c);
1052 }
1053 merge_collinear_edges(edge, nullptr, c);
1148 if (prev) { 1054 if (prev) {
1149 prev->fNext = v; 1055 prev->fNext = v;
1150 v->fPrev = prev; 1056 v->fPrev = prev;
1151 } else { 1057 } else {
1152 vertices = v; 1058 vertices = v;
1153 } 1059 }
1154 prev = v; 1060 prev = v;
1155 v = vNext; 1061 v = vNext;
1156 if (v == contours[i]) break; 1062 if (v == contours[i]) break;
1157 } 1063 }
(...skipping 74 matching lines...) Expand 10 before | Expand all | Expand 10 after
1232 // Stage 4: Simplify the mesh by inserting new vertices at intersecting edges. 1138 // Stage 4: Simplify the mesh by inserting new vertices at intersecting edges.
1233 1139
1234 void simplify(Vertex* vertices, Comparator& c, SkChunkAlloc& alloc) { 1140 void simplify(Vertex* vertices, Comparator& c, SkChunkAlloc& alloc) {
1235 LOG("simplifying complex polygons\n"); 1141 LOG("simplifying complex polygons\n");
1236 EdgeList activeEdges; 1142 EdgeList activeEdges;
1237 for (Vertex* v = vertices; v != nullptr; v = v->fNext) { 1143 for (Vertex* v = vertices; v != nullptr; v = v->fNext) {
1238 if (!v->fFirstEdgeAbove && !v->fFirstEdgeBelow) { 1144 if (!v->fFirstEdgeAbove && !v->fFirstEdgeBelow) {
1239 continue; 1145 continue;
1240 } 1146 }
1241 #if LOGGING_ENABLED 1147 #if LOGGING_ENABLED
1242 LOG("\nvertex %g: (%g,%g), alpha %d\n", v->fID, v->fPoint.fX, v->fPoint. fY, v->fAlpha); 1148 LOG("\nvertex %g: (%g,%g)\n", v->fID, v->fPoint.fX, v->fPoint.fY);
1243 #endif 1149 #endif
1244 Edge* leftEnclosingEdge = nullptr; 1150 Edge* leftEnclosingEdge = nullptr;
1245 Edge* rightEnclosingEdge = nullptr; 1151 Edge* rightEnclosingEdge = nullptr;
1246 bool restartChecks; 1152 bool restartChecks;
1247 do { 1153 do {
1248 restartChecks = false; 1154 restartChecks = false;
1249 find_enclosing_edges(v, &activeEdges, &leftEnclosingEdge, &rightEncl osingEdge); 1155 find_enclosing_edges(v, &activeEdges, &leftEnclosingEdge, &rightEncl osingEdge);
1250 if (v->fFirstEdgeBelow) { 1156 if (v->fFirstEdgeBelow) {
1251 for (Edge* edge = v->fFirstEdgeBelow; edge != nullptr; edge = ed ge->fNextEdgeBelow) { 1157 for (Edge* edge = v->fFirstEdgeBelow; edge != nullptr; edge = ed ge->fNextEdgeBelow) {
1252 if (check_for_intersection(edge, leftEnclosingEdge, &activeE dges, c, alloc)) { 1158 if (check_for_intersection(edge, leftEnclosingEdge, &activeE dges, c, alloc)) {
1253 restartChecks = true; 1159 restartChecks = true;
1254 break; 1160 break;
1255 } 1161 }
1256 if (check_for_intersection(edge, rightEnclosingEdge, &active Edges, c, alloc)) { 1162 if (check_for_intersection(edge, rightEnclosingEdge, &active Edges, c, alloc)) {
1257 restartChecks = true; 1163 restartChecks = true;
1258 break; 1164 break;
1259 } 1165 }
1260 } 1166 }
1261 } else { 1167 } else {
1262 if (Vertex* pv = check_for_intersection(leftEnclosingEdge, right EnclosingEdge, 1168 if (Vertex* pv = check_for_intersection(leftEnclosingEdge, right EnclosingEdge,
1263 &activeEdges, c, alloc)) { 1169 &activeEdges, c, alloc)) {
1264 if (c.sweep_lt(pv->fPoint, v->fPoint)) { 1170 if (c.sweep_lt(pv->fPoint, v->fPoint)) {
1265 v = pv; 1171 v = pv;
1266 } 1172 }
1267 restartChecks = true; 1173 restartChecks = true;
1268 } 1174 }
1269 1175
1270 } 1176 }
1271 } while (restartChecks); 1177 } while (restartChecks);
1272 if (v->fAlpha == 0) {
1273 if ((leftEnclosingEdge && leftEnclosingEdge->fWinding < 0) &&
1274 (rightEnclosingEdge && rightEnclosingEdge->fWinding > 0)) {
1275 v->fAlpha = max_edge_alpha(leftEnclosingEdge, rightEnclosingEdge );
1276 }
1277 }
1278 for (Edge* e = v->fFirstEdgeAbove; e; e = e->fNextEdgeAbove) { 1178 for (Edge* e = v->fFirstEdgeAbove; e; e = e->fNextEdgeAbove) {
1279 remove_edge(e, &activeEdges); 1179 remove_edge(e, &activeEdges);
1280 } 1180 }
1281 Edge* leftEdge = leftEnclosingEdge; 1181 Edge* leftEdge = leftEnclosingEdge;
1282 for (Edge* e = v->fFirstEdgeBelow; e; e = e->fNextEdgeBelow) { 1182 for (Edge* e = v->fFirstEdgeBelow; e; e = e->fNextEdgeBelow) {
1283 insert_edge(e, leftEdge, &activeEdges); 1183 insert_edge(e, leftEdge, &activeEdges);
1284 leftEdge = e; 1184 leftEdge = e;
1285 } 1185 }
1286 v->fProcessed = true; 1186 v->fProcessed = true;
1287 } 1187 }
1288 } 1188 }
1289 1189
1290 // Stage 5: Tessellate the simplified mesh into monotone polygons. 1190 // Stage 5: Tessellate the simplified mesh into monotone polygons.
1291 1191
1292 Poly* tessellate(Vertex* vertices, SkChunkAlloc& alloc) { 1192 Poly* tessellate(Vertex* vertices, SkChunkAlloc& alloc) {
1293 LOG("tessellating simple polygons\n"); 1193 LOG("tessellating simple polygons\n");
1294 EdgeList activeEdges; 1194 EdgeList activeEdges;
1295 Poly* polys = nullptr; 1195 Poly* polys = nullptr;
1296 for (Vertex* v = vertices; v != nullptr; v = v->fNext) { 1196 for (Vertex* v = vertices; v != nullptr; v = v->fNext) {
1297 if (!v->fFirstEdgeAbove && !v->fFirstEdgeBelow) { 1197 if (!v->fFirstEdgeAbove && !v->fFirstEdgeBelow) {
1298 continue; 1198 continue;
1299 } 1199 }
1300 #if LOGGING_ENABLED 1200 #if LOGGING_ENABLED
1301 LOG("\nvertex %g: (%g,%g), alpha %d\n", v->fID, v->fPoint.fX, v->fPoint. fY, v->fAlpha); 1201 LOG("\nvertex %g: (%g,%g)\n", v->fID, v->fPoint.fX, v->fPoint.fY);
1302 #endif 1202 #endif
1303 Edge* leftEnclosingEdge = nullptr; 1203 Edge* leftEnclosingEdge = nullptr;
1304 Edge* rightEnclosingEdge = nullptr; 1204 Edge* rightEnclosingEdge = nullptr;
1305 find_enclosing_edges(v, &activeEdges, &leftEnclosingEdge, &rightEnclosin gEdge); 1205 find_enclosing_edges(v, &activeEdges, &leftEnclosingEdge, &rightEnclosin gEdge);
1306 Poly* leftPoly = nullptr; 1206 Poly* leftPoly = nullptr;
1307 Poly* rightPoly = nullptr; 1207 Poly* rightPoly = nullptr;
1308 if (v->fFirstEdgeAbove) { 1208 if (v->fFirstEdgeAbove) {
1309 leftPoly = v->fFirstEdgeAbove->fLeftPoly; 1209 leftPoly = v->fFirstEdgeAbove->fLeftPoly;
1310 rightPoly = v->fLastEdgeAbove->fRightPoly; 1210 rightPoly = v->fLastEdgeAbove->fRightPoly;
1311 } else { 1211 } else {
(...skipping 79 matching lines...) Expand 10 before | Expand all | Expand 10 after
1391 LOG("\nactive edges:\n"); 1291 LOG("\nactive edges:\n");
1392 for (Edge* e = activeEdges.fHead; e != nullptr; e = e->fRight) { 1292 for (Edge* e = activeEdges.fHead; e != nullptr; e = e->fRight) {
1393 LOG("%g -> %g, lpoly %d, rpoly %d\n", e->fTop->fID, e->fBottom->fID, 1293 LOG("%g -> %g, lpoly %d, rpoly %d\n", e->fTop->fID, e->fBottom->fID,
1394 e->fLeftPoly ? e->fLeftPoly->fID : -1, e->fRightPoly ? e->fRight Poly->fID : -1); 1294 e->fLeftPoly ? e->fLeftPoly->fID : -1, e->fRightPoly ? e->fRight Poly->fID : -1);
1395 } 1295 }
1396 #endif 1296 #endif
1397 } 1297 }
1398 return polys; 1298 return polys;
1399 } 1299 }
1400 1300
1401 bool is_boundary_edge(Edge* edge, SkPath::FillType fillType) {
1402 return apply_fill_type(fillType, edge->fLeftPoly) !=
1403 apply_fill_type(fillType, edge->fRightPoly);
1404 }
1405
1406 bool is_boundary_start(Edge* edge, SkPath::FillType fillType) {
1407 return !apply_fill_type(fillType, edge->fLeftPoly) &&
1408 apply_fill_type(fillType, edge->fRightPoly);
1409 }
1410
1411 Vertex* remove_non_boundary_edges(Vertex* vertices, SkPath::FillType fillType,
1412 SkChunkAlloc& alloc) {
1413 for (Vertex* v = vertices; v != nullptr; v = v->fNext) {
1414 for (Edge* e = v->fFirstEdgeBelow; e != nullptr;) {
1415 Edge* next = e->fNextEdgeBelow;
1416 if (!is_boundary_edge(e, fillType)) {
1417 remove_edge_above(e);
1418 remove_edge_below(e);
1419 }
1420 e = next;
1421 }
1422 }
1423 return vertices;
1424 }
1425
1426 // This is different from Edge::intersect, in that it intersects lines, not line segments.
1427 bool intersect(const Edge& a, const Edge& b, SkPoint* point) {
1428 double denom = a.fDX * b.fDY - a.fDY * b.fDX;
1429 if (denom == 0.0) {
1430 return false;
1431 }
1432 double scale = 1.0f / denom;
1433 point->fX = SkDoubleToScalar((b.fDX * a.fC - a.fDX * b.fC) * scale);
1434 point->fY = SkDoubleToScalar((b.fDY * a.fC - a.fDY * b.fC) * scale);
1435 round(point);
1436 return true;
1437 }
1438
1439 void get_edge_normal(const Edge* e, SkVector* normal) {
1440 normal->setNormalize(SkDoubleToScalar(e->fDX) * e->fWinding,
1441 SkDoubleToScalar(e->fDY) * e->fWinding);
1442 }
1443
1444 // Stage 5c: detect and remove "pointy" vertices whose edge normals point in opp osite directions
1445 // and whose adjacent vertices are less than a quarter pixel from an edge. These are guaranteed to
1446 // invert on stroking.
1447
1448 void simplify_boundary(EdgeList* boundary, Comparator& c, SkChunkAlloc& alloc) {
1449 Edge* prevEdge = boundary->fTail;
1450 SkVector prevNormal;
1451 get_edge_normal(prevEdge, &prevNormal);
1452 for (Edge* e = boundary->fHead; e != nullptr;) {
1453 Vertex* prev = prevEdge->fWinding == 1 ? prevEdge->fTop : prevEdge->fBot tom;
1454 Vertex* next = e->fWinding == 1 ? e->fBottom : e->fTop;
1455 double dist = e->dist(prev->fPoint);
1456 SkVector normal;
1457 get_edge_normal(e, &normal);
1458 float denom = 0.25f * static_cast<float>(e->fDX * e->fDX + e->fDY * e->f DY);
1459 if (prevNormal.dot(normal) < 0.0 && (dist * dist) <= denom) {
1460 Edge* join = new_edge(prev, next, alloc, c);
1461 insert_edge(join, e, boundary);
1462 remove_edge(prevEdge, boundary);
1463 remove_edge(e, boundary);
1464 if (join->fLeft && join->fRight) {
1465 prevEdge = join->fLeft;
1466 e = join;
1467 } else {
1468 prevEdge = boundary->fTail;
1469 e = boundary->fHead; // join->fLeft ? join->fLeft : join;
1470 }
1471 get_edge_normal(prevEdge, &prevNormal);
1472 } else {
1473 prevEdge = e;
1474 prevNormal = normal;
1475 e = e->fRight;
1476 }
1477 }
1478 }
1479
1480 // Stage 5d: Displace edges by half a pixel inward and outward along their norma ls. Intersect to
1481 // find new vertices, and set zero alpha on the exterior and one alpha on the in terior. Build a
1482 // new antialiased mesh from those vertices.
1483
1484 void boundary_to_aa_mesh(EdgeList* boundary, VertexList* mesh, Comparator& c, Sk ChunkAlloc& alloc) {
1485 EdgeList outerContour;
1486 Edge* prevEdge = boundary->fTail;
1487 float radius = 0.5f;
1488 double offset = radius * sqrt(prevEdge->fDX * prevEdge->fDX + prevEdge->fDY * prevEdge->fDY)
1489 * prevEdge->fWinding;
1490 Edge prevInner(prevEdge->fTop, prevEdge->fBottom, prevEdge->fWinding);
1491 prevInner.fC -= offset;
1492 Edge prevOuter(prevEdge->fTop, prevEdge->fBottom, prevEdge->fWinding);
1493 prevOuter.fC += offset;
1494 VertexList innerVertices;
1495 VertexList outerVertices;
1496 SkScalar innerCount = SK_Scalar1, outerCount = SK_Scalar1;
1497 for (Edge* e = boundary->fHead; e != nullptr; e = e->fRight) {
1498 double offset = radius * sqrt(e->fDX * e->fDX + e->fDY * e->fDY) * e->fW inding;
1499 Edge inner(e->fTop, e->fBottom, e->fWinding);
1500 inner.fC -= offset;
1501 Edge outer(e->fTop, e->fBottom, e->fWinding);
1502 outer.fC += offset;
1503 SkPoint innerPoint, outerPoint;
1504 if (intersect(prevInner, inner, &innerPoint) &&
1505 intersect(prevOuter, outer, &outerPoint)) {
1506 Vertex* innerVertex = ALLOC_NEW(Vertex, (innerPoint, 255), alloc);
1507 Vertex* outerVertex = ALLOC_NEW(Vertex, (outerPoint, 0), alloc);
1508 if (innerVertices.fTail && outerVertices.fTail) {
1509 Edge innerEdge(innerVertices.fTail, innerVertex, 1);
1510 Edge outerEdge(outerVertices.fTail, outerVertex, 1);
1511 SkVector innerNormal;
1512 get_edge_normal(&innerEdge, &innerNormal);
1513 SkVector outerNormal;
1514 get_edge_normal(&outerEdge, &outerNormal);
1515 SkVector normal;
1516 get_edge_normal(prevEdge, &normal);
1517 if (normal.dot(innerNormal) < 0) {
1518 innerPoint += innerVertices.fTail->fPoint * innerCount;
1519 innerCount++;
1520 innerPoint *= SkScalarInvert(innerCount);
1521 innerVertices.fTail->fPoint = innerVertex->fPoint = innerPoi nt;
1522 } else {
1523 innerCount = SK_Scalar1;
1524 }
1525 if (normal.dot(outerNormal) < 0) {
1526 outerPoint += outerVertices.fTail->fPoint * outerCount;
1527 outerCount++;
1528 outerPoint *= SkScalarInvert(outerCount);
1529 outerVertices.fTail->fPoint = outerVertex->fPoint = outerPoi nt;
1530 } else {
1531 outerCount = SK_Scalar1;
1532 }
1533 }
1534 innerVertices.append(innerVertex);
1535 outerVertices.append(outerVertex);
1536 prevEdge = e;
1537 }
1538 prevInner = inner;
1539 prevOuter = outer;
1540 }
1541 innerVertices.close();
1542 outerVertices.close();
1543
1544 Vertex* innerVertex = innerVertices.fHead;
1545 Vertex* outerVertex = outerVertices.fHead;
1546 // Alternate clockwise and counterclockwise polys, so the tesselator
1547 // doesn't cancel out the interior edges.
1548 if (!innerVertex || !outerVertex) {
1549 return;
1550 }
1551 do {
1552 connect(outerVertex->fNext, outerVertex, alloc, c);
1553 connect(innerVertex->fNext, innerVertex, alloc, c, 2);
1554 connect(innerVertex, outerVertex->fNext, alloc, c, 2);
1555 connect(outerVertex, innerVertex, alloc, c, 2);
1556 Vertex* innerNext = innerVertex->fNext;
1557 Vertex* outerNext = outerVertex->fNext;
1558 mesh->append(innerVertex);
1559 mesh->append(outerVertex);
1560 innerVertex = innerNext;
1561 outerVertex = outerNext;
1562 } while (innerVertex != innerVertices.fHead && outerVertex != outerVertices. fHead);
1563 }
1564
1565 void extract_boundary(EdgeList* boundary, Edge* e, SkPath::FillType fillType, Sk ChunkAlloc& alloc) {
1566 bool down = is_boundary_start(e, fillType);
1567 while (e) {
1568 e->fWinding = down ? 1 : -1;
1569 Edge* next;
1570 boundary->append(e);
1571 if (down) {
1572 // Find outgoing edge, in clockwise order.
1573 if ((next = e->fNextEdgeAbove)) {
1574 down = false;
1575 } else if ((next = e->fBottom->fLastEdgeBelow)) {
1576 down = true;
1577 } else if ((next = e->fPrevEdgeAbove)) {
1578 down = false;
1579 }
1580 } else {
1581 // Find outgoing edge, in counter-clockwise order.
1582 if ((next = e->fPrevEdgeBelow)) {
1583 down = true;
1584 } else if ((next = e->fTop->fFirstEdgeAbove)) {
1585 down = false;
1586 } else if ((next = e->fNextEdgeBelow)) {
1587 down = true;
1588 }
1589 }
1590 remove_edge_above(e);
1591 remove_edge_below(e);
1592 e = next;
1593 }
1594 }
1595
1596 // Stage 5b: Extract boundary edges.
1597
1598 EdgeList* extract_boundaries(Vertex* vertices, SkPath::FillType fillType, SkChun kAlloc& alloc) {
1599 LOG("extracting boundaries\n");
1600 vertices = remove_non_boundary_edges(vertices, fillType, alloc);
1601 EdgeList* boundaries = nullptr;
1602 for (Vertex* v = vertices; v != nullptr; v = v->fNext) {
1603 while (v->fFirstEdgeBelow) {
1604 EdgeList* boundary = new_contour(&boundaries, alloc);
1605 extract_boundary(boundary, v->fFirstEdgeBelow, fillType, alloc);
1606 }
1607 }
1608 return boundaries;
1609 }
1610
1611 // This is a driver function which calls stages 2-5 in turn. 1301 // This is a driver function which calls stages 2-5 in turn.
1612 1302
1613 Vertex* contours_to_mesh(Vertex** contours, int contourCnt, bool antialias, 1303 Poly* contours_to_polys(Vertex** contours, int contourCnt, const SkRect& pathBou nds,
1614 Comparator& c, SkChunkAlloc& alloc) {
1615 #if LOGGING_ENABLED
1616 for (int i = 0; i < contourCnt; ++i) {
1617 Vertex* v = contours[i];
1618 SkASSERT(v);
1619 LOG("path.moveTo(%20.20g, %20.20g);\n", v->fPoint.fX, v->fPoint.fY);
1620 for (v = v->fNext; v != contours[i]; v = v->fNext) {
1621 LOG("path.lineTo(%20.20g, %20.20g);\n", v->fPoint.fX, v->fPoint.fY);
1622 }
1623 }
1624 #endif
1625 sanitize_contours(contours, contourCnt, antialias);
1626 return build_edges(contours, contourCnt, c, alloc);
1627 }
1628
1629 Poly* mesh_to_polys(Vertex** vertices, SkPath::FillType fillType, Comparator& c,
1630 SkChunkAlloc& alloc) {
1631 if (!vertices || !*vertices) {
1632 return nullptr;
1633 }
1634
1635 // Sort vertices in Y (secondarily in X).
1636 merge_sort(vertices, c);
1637 merge_coincident_vertices(vertices, c, alloc);
1638 #if LOGGING_ENABLED
1639 for (Vertex* v = *vertices; v != nullptr; v = v->fNext) {
1640 static float gID = 0.0f;
1641 v->fID = gID++;
1642 }
1643 #endif
1644 simplify(*vertices, c, alloc);
1645 return tessellate(*vertices, alloc);
1646 }
1647
1648 Poly* contours_to_polys(Vertex** contours, int contourCnt, SkPath::FillType fill Type,
1649 const SkRect& pathBounds, bool antialias,
1650 SkChunkAlloc& alloc) { 1304 SkChunkAlloc& alloc) {
1651 Comparator c; 1305 Comparator c;
1652 if (pathBounds.width() > pathBounds.height()) { 1306 if (pathBounds.width() > pathBounds.height()) {
1653 c.sweep_lt = sweep_lt_horiz; 1307 c.sweep_lt = sweep_lt_horiz;
1654 c.sweep_gt = sweep_gt_horiz; 1308 c.sweep_gt = sweep_gt_horiz;
1655 } else { 1309 } else {
1656 c.sweep_lt = sweep_lt_vert; 1310 c.sweep_lt = sweep_lt_vert;
1657 c.sweep_gt = sweep_gt_vert; 1311 c.sweep_gt = sweep_gt_vert;
1658 } 1312 }
1659 Vertex* mesh = contours_to_mesh(contours, contourCnt, antialias, c, alloc); 1313 #if LOGGING_ENABLED
1660 Poly* polys = mesh_to_polys(&mesh, fillType, c, alloc); 1314 for (int i = 0; i < contourCnt; ++i) {
1661 if (antialias) { 1315 Vertex* v = contours[i];
1662 EdgeList* boundaries = extract_boundaries(mesh, fillType, alloc); 1316 SkASSERT(v);
1663 VertexList aaMesh; 1317 LOG("path.moveTo(%20.20g, %20.20g);\n", v->fPoint.fX, v->fPoint.fY);
1664 for (EdgeList* boundary = boundaries; boundary != nullptr; boundary = bo undary->fNext) { 1318 for (v = v->fNext; v != contours[i]; v = v->fNext) {
1665 simplify_boundary(boundary, c, alloc); 1319 LOG("path.lineTo(%20.20g, %20.20g);\n", v->fPoint.fX, v->fPoint.fY);
1666 if (boundary->fCount > 2) {
1667 boundary_to_aa_mesh(boundary, &aaMesh, c, alloc);
1668 }
1669 }
1670 return mesh_to_polys(&aaMesh.fHead, SkPath::kWinding_FillType, c, alloc) ;
1671 }
1672 return polys;
1673 }
1674
1675 // Stage 6: Triangulate the monotone polygons into a vertex buffer.
1676 void* polys_to_triangles(Poly* polys, SkPath::FillType fillType, const AAParams* aaParams,
1677 void* data) {
1678 for (Poly* poly = polys; poly; poly = poly->fNext) {
1679 if (apply_fill_type(fillType, poly)) {
1680 data = poly->emit(aaParams, data);
1681 } 1320 }
1682 } 1321 }
1683 return data; 1322 #endif
1323 sanitize_contours(contours, contourCnt);
1324 Vertex* vertices = build_edges(contours, contourCnt, c, alloc);
1325 if (!vertices) {
1326 return nullptr;
1327 }
1328
1329 // Sort vertices in Y (secondarily in X).
1330 merge_sort(&vertices, c);
1331 merge_coincident_vertices(&vertices, c, alloc);
1332 #if LOGGING_ENABLED
1333 for (Vertex* v = vertices; v != nullptr; v = v->fNext) {
1334 static float gID = 0.0f;
1335 v->fID = gID++;
1336 }
1337 #endif
1338 simplify(vertices, c, alloc);
1339 return tessellate(vertices, alloc);
1684 } 1340 }
1685 1341
1686 Poly* path_to_polys(const SkPath& path, SkScalar tolerance, const SkRect& clipBo unds, 1342 Poly* path_to_polys(const SkPath& path, SkScalar tolerance, const SkRect& clipBo unds,
1687 int contourCnt, SkChunkAlloc& alloc, bool antialias, bool* i sLinear) { 1343 int contourCnt, SkChunkAlloc& alloc, bool* isLinear) {
1688 SkPath::FillType fillType = path.getFillType(); 1344 SkPath::FillType fillType = path.getFillType();
1689 if (SkPath::IsInverseFillType(fillType)) { 1345 if (SkPath::IsInverseFillType(fillType)) {
1690 contourCnt++; 1346 contourCnt++;
1691 } 1347 }
1692 SkAutoTDeleteArray<Vertex*> contours(new Vertex* [contourCnt]); 1348 SkAutoTDeleteArray<Vertex*> contours(new Vertex* [contourCnt]);
1693 1349
1694 path_to_contours(path, tolerance, clipBounds, contours.get(), alloc, isLinea r); 1350 path_to_contours(path, tolerance, clipBounds, contours.get(), alloc, isLinea r);
1695 return contours_to_polys(contours.get(), contourCnt, path.getFillType(), pat h.getBounds(), 1351 return contours_to_polys(contours.get(), contourCnt, path.getBounds(), alloc );
1696 antialias, alloc);
1697 } 1352 }
1698 1353
1699 void get_contour_count_and_size_estimate(const SkPath& path, SkScalar tolerance, int* contourCnt, 1354 void get_contour_count_and_size_estimate(const SkPath& path, SkScalar tolerance, int* contourCnt,
1700 int* sizeEstimate) { 1355 int* sizeEstimate) {
1701 int maxPts = GrPathUtils::worstCasePointCount(path, contourCnt, tolerance); 1356 int maxPts = GrPathUtils::worstCasePointCount(path, contourCnt, tolerance);
1702 if (maxPts <= 0) { 1357 if (maxPts <= 0) {
1703 *contourCnt = 0; 1358 *contourCnt = 0;
1704 return; 1359 return;
1705 } 1360 }
1706 if (maxPts > ((int)SK_MaxU16 + 1)) { 1361 if (maxPts > ((int)SK_MaxU16 + 1)) {
1707 SkDebugf("Path not rendered, too many verts (%d)\n", maxPts); 1362 SkDebugf("Path not rendered, too many verts (%d)\n", maxPts);
1708 *contourCnt = 0; 1363 *contourCnt = 0;
1709 return; 1364 return;
1710 } 1365 }
1711 // For the initial size of the chunk allocator, estimate based on the point count: 1366 // For the initial size of the chunk allocator, estimate based on the point count:
1712 // one vertex per point for the initial passes, plus two for the vertices in the 1367 // one vertex per point for the initial passes, plus two for the vertices in the
1713 // resulting Polys, since the same point may end up in two Polys. Assume mi nimal 1368 // resulting Polys, since the same point may end up in two Polys. Assume mi nimal
1714 // connectivity of one Edge per Vertex (will grow for intersections). 1369 // connectivity of one Edge per Vertex (will grow for intersections).
1715 *sizeEstimate = maxPts * (3 * sizeof(Vertex) + sizeof(Edge)); 1370 *sizeEstimate = maxPts * (3 * sizeof(Vertex) + sizeof(Edge));
1716 } 1371 }
1717 1372
1718 int count_points(Poly* polys, SkPath::FillType fillType) { 1373 int count_points(Poly* polys, SkPath::FillType fillType) {
1719 int count = 0; 1374 int count = 0;
1720 for (Poly* poly = polys; poly; poly = poly->fNext) { 1375 for (Poly* poly = polys; poly; poly = poly->fNext) {
1721 if (apply_fill_type(fillType, poly) && poly->fCount >= 3) { 1376 if (apply_fill_type(fillType, poly->fWinding) && poly->fCount >= 3) {
1722 count += (poly->fCount - 2) * (TESSELLATOR_WIREFRAME ? 6 : 3); 1377 count += (poly->fCount - 2) * (TESSELLATOR_WIREFRAME ? 6 : 3);
1723 } 1378 }
1724 } 1379 }
1725 return count; 1380 return count;
1726 } 1381 }
1727 1382
1728 } // namespace 1383 } // namespace
1729 1384
1730 namespace GrTessellator { 1385 namespace GrTessellator {
1731 1386
1732 // Stage 6: Triangulate the monotone polygons into a vertex buffer. 1387 // Stage 6: Triangulate the monotone polygons into a vertex buffer.
1733 1388
1734 int PathToTriangles(const SkPath& path, SkScalar tolerance, const SkRect& clipBo unds, 1389 int PathToTriangles(const SkPath& path, SkScalar tolerance, const SkRect& clipBo unds,
1735 VertexAllocator* vertexAllocator, bool antialias, const GrCo lor& color, 1390 VertexAllocator* vertexAllocator, bool* isLinear) {
1736 bool canTweakAlphaForCoverage, bool* isLinear) {
1737 int contourCnt; 1391 int contourCnt;
1738 int sizeEstimate; 1392 int sizeEstimate;
1739 get_contour_count_and_size_estimate(path, tolerance, &contourCnt, &sizeEstim ate); 1393 get_contour_count_and_size_estimate(path, tolerance, &contourCnt, &sizeEstim ate);
1740 if (contourCnt <= 0) { 1394 if (contourCnt <= 0) {
1741 *isLinear = true; 1395 *isLinear = true;
1742 return 0; 1396 return 0;
1743 } 1397 }
1744 SkChunkAlloc alloc(sizeEstimate); 1398 SkChunkAlloc alloc(sizeEstimate);
1745 Poly* polys = path_to_polys(path, tolerance, clipBounds, contourCnt, alloc, antialias, 1399 Poly* polys = path_to_polys(path, tolerance, clipBounds, contourCnt, alloc, isLinear);
1746 isLinear);
1747 SkPath::FillType fillType = path.getFillType(); 1400 SkPath::FillType fillType = path.getFillType();
1748 int count = count_points(polys, fillType); 1401 int count = count_points(polys, fillType);
1749 if (0 == count) { 1402 if (0 == count) {
1750 return 0; 1403 return 0;
1751 } 1404 }
1752 1405
1753 void* verts = vertexAllocator->lock(count); 1406 SkPoint* verts = vertexAllocator->lock(count);
1754 if (!verts) { 1407 if (!verts) {
1755 SkDebugf("Could not allocate vertices\n"); 1408 SkDebugf("Could not allocate vertices\n");
1756 return 0; 1409 return 0;
1757 } 1410 }
1758 1411 SkPoint* end = verts;
1759 LOG("emitting %d verts\n", count); 1412 for (Poly* poly = polys; poly; poly = poly->fNext) {
1760 AAParams aaParams; 1413 if (apply_fill_type(fillType, poly->fWinding)) {
1761 aaParams.fTweakAlpha = canTweakAlphaForCoverage; 1414 end = poly->emit(end);
1762 aaParams.fColor = color; 1415 }
1763 1416 }
1764 void* end = polys_to_triangles(polys, fillType, antialias ? &aaParams : null ptr, verts); 1417 int actualCount = static_cast<int>(end - verts);
1765 int actualCount = static_cast<int>((static_cast<uint8_t*>(end) - static_cast <uint8_t*>(verts)) 1418 LOG("actual count: %d\n", actualCount);
1766 / vertexAllocator->stride());
1767 SkASSERT(actualCount <= count); 1419 SkASSERT(actualCount <= count);
1768 vertexAllocator->unlock(actualCount); 1420 vertexAllocator->unlock(actualCount);
1769 return actualCount; 1421 return actualCount;
1770 } 1422 }
1771 1423
1772 int PathToVertices(const SkPath& path, SkScalar tolerance, const SkRect& clipBou nds, 1424 int PathToVertices(const SkPath& path, SkScalar tolerance, const SkRect& clipBou nds,
1773 GrTessellator::WindingVertex** verts) { 1425 GrTessellator::WindingVertex** verts) {
1774 int contourCnt; 1426 int contourCnt;
1775 int sizeEstimate; 1427 int sizeEstimate;
1776 get_contour_count_and_size_estimate(path, tolerance, &contourCnt, &sizeEstim ate); 1428 get_contour_count_and_size_estimate(path, tolerance, &contourCnt, &sizeEstim ate);
1777 if (contourCnt <= 0) { 1429 if (contourCnt <= 0) {
1778 return 0; 1430 return 0;
1779 } 1431 }
1780 SkChunkAlloc alloc(sizeEstimate); 1432 SkChunkAlloc alloc(sizeEstimate);
1781 bool isLinear; 1433 bool isLinear;
1782 Poly* polys = path_to_polys(path, tolerance, clipBounds, contourCnt, alloc, false, &isLinear); 1434 Poly* polys = path_to_polys(path, tolerance, clipBounds, contourCnt, alloc, &isLinear);
1783 SkPath::FillType fillType = path.getFillType(); 1435 SkPath::FillType fillType = path.getFillType();
1784 int count = count_points(polys, fillType); 1436 int count = count_points(polys, fillType);
1785 if (0 == count) { 1437 if (0 == count) {
1786 *verts = nullptr; 1438 *verts = nullptr;
1787 return 0; 1439 return 0;
1788 } 1440 }
1789 1441
1790 *verts = new GrTessellator::WindingVertex[count]; 1442 *verts = new GrTessellator::WindingVertex[count];
1791 GrTessellator::WindingVertex* vertsEnd = *verts; 1443 GrTessellator::WindingVertex* vertsEnd = *verts;
1792 SkPoint* points = new SkPoint[count]; 1444 SkPoint* points = new SkPoint[count];
1793 SkPoint* pointsEnd = points; 1445 SkPoint* pointsEnd = points;
1794 for (Poly* poly = polys; poly; poly = poly->fNext) { 1446 for (Poly* poly = polys; poly; poly = poly->fNext) {
1795 if (apply_fill_type(fillType, poly)) { 1447 if (apply_fill_type(fillType, poly->fWinding)) {
1796 SkPoint* start = pointsEnd; 1448 SkPoint* start = pointsEnd;
1797 pointsEnd = static_cast<SkPoint*>(poly->emit(nullptr, pointsEnd)); 1449 pointsEnd = poly->emit(pointsEnd);
1798 while (start != pointsEnd) { 1450 while (start != pointsEnd) {
1799 vertsEnd->fPos = *start; 1451 vertsEnd->fPos = *start;
1800 vertsEnd->fWinding = poly->fWinding; 1452 vertsEnd->fWinding = poly->fWinding;
1801 ++start; 1453 ++start;
1802 ++vertsEnd; 1454 ++vertsEnd;
1803 } 1455 }
1804 } 1456 }
1805 } 1457 }
1806 int actualCount = static_cast<int>(vertsEnd - *verts); 1458 int actualCount = static_cast<int>(vertsEnd - *verts);
1807 SkASSERT(actualCount <= count); 1459 SkASSERT(actualCount <= count);
1808 SkASSERT(pointsEnd - points == actualCount); 1460 SkASSERT(pointsEnd - points == actualCount);
1809 delete[] points; 1461 delete[] points;
1810 return actualCount; 1462 return actualCount;
1811 } 1463 }
1812 1464
1813 } // namespace 1465 } // namespace
OLDNEW
« no previous file with comments | « src/gpu/GrTessellator.h ('k') | src/gpu/batches/GrTessellatingPathRenderer.cpp » ('j') | no next file with comments »

Powered by Google App Engine
This is Rietveld 408576698