OLD | NEW |
1 /* | 1 /* |
2 * Copyright 2015 Google Inc. | 2 * Copyright 2015 Google Inc. |
3 * | 3 * |
4 * Use of this source code is governed by a BSD-style license that can be | 4 * Use of this source code is governed by a BSD-style license that can be |
5 * found in the LICENSE file. | 5 * found in the LICENSE file. |
6 */ | 6 */ |
7 | 7 |
8 #include "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 Loading... |
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 Loading... |
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 Loading... |
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 Loading... |
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 Loading... |
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 Loading... |
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 Loading... |
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 Loading... |
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 Loading... |
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 Loading... |
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 Loading... |
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 Loading... |
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 Loading... |
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 |
OLD | NEW |