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

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

Issue 1570503002: Revert of Broke GrTessellatingPathRenderer's tessellator out into a separate file. (Closed) Base URL: https://skia.googlesource.com/skia.git@master
Patch Set: Created 4 years, 11 months ago
Use n/p to move between diff chunks; N/P to move between comments. Draft comments are only viewable by you.
Jump to:
View unified diff | Download patch
« 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
(Empty)
1 /*
2 * Copyright 2015 Google Inc.
3 *
4 * Use of this source code is governed by a BSD-style license that can be
5 * found in the LICENSE file.
6 */
7
8 #include "GrTessellator.h"
9
10 #include "GrBatchFlushState.h"
11 #include "GrBatchTest.h"
12 #include "GrDefaultGeoProcFactory.h"
13 #include "GrPathUtils.h"
14 #include "GrVertices.h"
15 #include "GrResourceCache.h"
16 #include "GrResourceProvider.h"
17 #include "SkGeometry.h"
18 #include "SkChunkAlloc.h"
19
20 #include "batches/GrVertexBatch.h"
21
22 #include <stdio.h>
23
24 /*
25 * There are six stages to the algorithm:
26 *
27 * 1) Linearize the path contours into piecewise linear segments (path_to_contou rs()).
28 * 2) Build a mesh of edges connecting the vertices (build_edges()).
29 * 3) Sort the vertices in Y (and secondarily in X) (merge_sort()).
30 * 4) Simplify the mesh by inserting new vertices at intersecting edges (simplif y()).
31 * 5) Tessellate the simplified mesh into monotone polygons (tessellate()).
32 * 6) Triangulate the monotone polygons directly into a vertex buffer (polys_to_ triangles()).
33 *
34 * The vertex sorting in step (3) is a merge sort, since it plays well with the linked list
35 * of vertices (and the necessity of inserting new vertices on intersection).
36 *
37 * Stages (4) and (5) use an active edge list, which a list of all edges for whi ch the
38 * sweep line has crossed the top vertex, but not the bottom vertex. It's sorte d
39 * left-to-right based on the point where both edges are active (when both top v ertices
40 * have been seen, so the "lower" top vertex of the two). If the top vertices ar e equal
41 * (shared), it's sorted based on the last point where both edges are active, so the
42 * "upper" bottom vertex.
43 *
44 * The most complex step is the simplification (4). It's based on the Bentley-Ot tman
45 * line-sweep algorithm, but due to floating point inaccuracy, the intersection points are
46 * not exact and may violate the mesh topology or active edge list ordering. We
47 * accommodate this by adjusting the topology of the mesh and AEL to match the i ntersection
48 * points. This occurs in three ways:
49 *
50 * A) Intersections may cause a shortened edge to no longer be ordered with resp ect to its
51 * neighbouring edges at the top or bottom vertex. This is handled by merging the
52 * edges (merge_collinear_edges()).
53 * B) Intersections may cause an edge to violate the left-to-right ordering of t he
54 * active edge list. This is handled by splitting the neighbour edge on the
55 * intersected vertex (cleanup_active_edges()).
56 * C) Shortening an edge may cause an active edge to become inactive or an inact ive edge
57 * to become active. This is handled by removing or inserting the edge in the active
58 * edge list (fix_active_state()).
59 *
60 * The tessellation steps (5) and (6) are based on "Triangulating Simple Polygon s and
61 * Equivalent Problems" (Fournier and Montuno); also a line-sweep algorithm. Not e that it
62 * currently uses a linked list for the active edge list, rather than a 2-3 tree as the
63 * paper describes. The 2-3 tree gives O(lg N) lookups, but insertion and remova l also
64 * become O(lg N). In all the test cases, it was found that the cost of frequent O(lg N)
65 * insertions and removals was greater than the cost of infrequent O(N) lookups with the
66 * linked list implementation. With the latter, all removals are O(1), and most insertions
67 * are O(1), since we know the adjacent edge in the active edge list based on th e topology.
68 * Only type 2 vertices (see paper) require the O(N) lookups, and these are much less
69 * frequent. There may be other data structures worth investigating, however.
70 *
71 * Note that the orientation of the line sweep algorithms is determined by the a spect ratio of the
72 * path bounds. When the path is taller than it is wide, we sort vertices based on increasing Y
73 * coordinate, and secondarily by increasing X coordinate. When the path is wide r than it is tall,
74 * we sort by increasing X coordinate, but secondarily by *decreasing* Y coordin ate. This is so
75 * that the "left" and "right" orientation in the code remains correct (edges to the left are
76 * increasing in Y; edges to the right are decreasing in Y). That is, the settin g rotates 90
77 * degrees counterclockwise, rather that transposing.
78 */
79
80 #define LOGGING_ENABLED 0
81
82 #if LOGGING_ENABLED
83 #define LOG printf
84 #else
85 #define LOG(...)
86 #endif
87
88 #define ALLOC_NEW(Type, args, alloc) new (alloc.allocThrow(sizeof(Type))) Type a rgs
89
90 namespace {
91
92 struct Vertex;
93 struct Edge;
94 struct Poly;
95
96 template <class T, T* T::*Prev, T* T::*Next>
97 void insert(T* t, T* prev, T* next, T** head, T** tail) {
98 t->*Prev = prev;
99 t->*Next = next;
100 if (prev) {
101 prev->*Next = t;
102 } else if (head) {
103 *head = t;
104 }
105 if (next) {
106 next->*Prev = t;
107 } else if (tail) {
108 *tail = t;
109 }
110 }
111
112 template <class T, T* T::*Prev, T* T::*Next>
113 void remove(T* t, T** head, T** tail) {
114 if (t->*Prev) {
115 t->*Prev->*Next = t->*Next;
116 } else if (head) {
117 *head = t->*Next;
118 }
119 if (t->*Next) {
120 t->*Next->*Prev = t->*Prev;
121 } else if (tail) {
122 *tail = t->*Prev;
123 }
124 t->*Prev = t->*Next = nullptr;
125 }
126
127 /**
128 * Vertices are used in three ways: first, the path contours are converted into a
129 * circularly-linked list of Vertices for each contour. After edge construction, the same Vertices
130 * are re-ordered by the merge sort according to the sweep_lt comparator (usuall y, increasing
131 * in Y) using the same fPrev/fNext pointers that were used for the contours, to avoid
132 * reallocation. Finally, MonotonePolys are built containing a circularly-linked list of
133 * Vertices. (Currently, those Vertices are newly-allocated for the MonotonePoly s, since
134 * an individual Vertex from the path mesh may belong to multiple
135 * MonotonePolys, so the original Vertices cannot be re-used.
136 */
137
138 struct Vertex {
139 Vertex(const SkPoint& point)
140 : fPoint(point), fPrev(nullptr), fNext(nullptr)
141 , fFirstEdgeAbove(nullptr), fLastEdgeAbove(nullptr)
142 , fFirstEdgeBelow(nullptr), fLastEdgeBelow(nullptr)
143 , fProcessed(false)
144 #if LOGGING_ENABLED
145 , fID (-1.0f)
146 #endif
147 {}
148 SkPoint fPoint; // Vertex position
149 Vertex* fPrev; // Linked list of contours, then Y-sorted vertices .
150 Vertex* fNext; // "
151 Edge* fFirstEdgeAbove; // Linked list of edges above this vertex.
152 Edge* fLastEdgeAbove; // "
153 Edge* fFirstEdgeBelow; // Linked list of edges below this vertex.
154 Edge* fLastEdgeBelow; // "
155 bool fProcessed; // Has this vertex been seen in simplify()?
156 #if LOGGING_ENABLED
157 float fID; // Identifier used for logging.
158 #endif
159 };
160
161 /******************************************************************************* ********/
162
163 typedef bool (*CompareFunc)(const SkPoint& a, const SkPoint& b);
164
165 struct Comparator {
166 CompareFunc sweep_lt;
167 CompareFunc sweep_gt;
168 };
169
170 bool sweep_lt_horiz(const SkPoint& a, const SkPoint& b) {
171 return a.fX == b.fX ? a.fY > b.fY : a.fX < b.fX;
172 }
173
174 bool sweep_lt_vert(const SkPoint& a, const SkPoint& b) {
175 return a.fY == b.fY ? a.fX < b.fX : a.fY < b.fY;
176 }
177
178 bool sweep_gt_horiz(const SkPoint& a, const SkPoint& b) {
179 return a.fX == b.fX ? a.fY < b.fY : a.fX > b.fX;
180 }
181
182 bool sweep_gt_vert(const SkPoint& a, const SkPoint& b) {
183 return a.fY == b.fY ? a.fX > b.fX : a.fY > b.fY;
184 }
185
186 inline SkPoint* emit_vertex(Vertex* v, SkPoint* data) {
187 *data++ = v->fPoint;
188 return data;
189 }
190
191 SkPoint* emit_triangle(Vertex* v0, Vertex* v1, Vertex* v2, SkPoint* data) {
192 #if WIREFRAME
193 data = emit_vertex(v0, data);
194 data = emit_vertex(v1, data);
195 data = emit_vertex(v1, data);
196 data = emit_vertex(v2, data);
197 data = emit_vertex(v2, data);
198 data = emit_vertex(v0, data);
199 #else
200 data = emit_vertex(v0, data);
201 data = emit_vertex(v1, data);
202 data = emit_vertex(v2, data);
203 #endif
204 return data;
205 }
206
207 struct EdgeList {
208 EdgeList() : fHead(nullptr), fTail(nullptr) {}
209 Edge* fHead;
210 Edge* fTail;
211 };
212
213 /**
214 * An Edge joins a top Vertex to a bottom Vertex. Edge ordering for the list of "edges above" and
215 * "edge below" a vertex as well as for the active edge list is handled by isLef tOf()/isRightOf().
216 * Note that an Edge will give occasionally dist() != 0 for its own endpoints (b ecause floating
217 * point). For speed, that case is only tested by the callers which require it ( e.g.,
218 * cleanup_active_edges()). Edges also handle checking for intersection with oth er edges.
219 * Currently, this converts the edges to the parametric form, in order to avoid doing a division
220 * until an intersection has been confirmed. This is slightly slower in the "fou nd" case, but
221 * a lot faster in the "not found" case.
222 *
223 * The coefficients of the line equation stored in double precision to avoid cat astrphic
224 * cancellation in the isLeftOf() and isRightOf() checks. Using doubles ensures that the result is
225 * correct in float, since it's a polynomial of degree 2. The intersect() functi on, being
226 * degree 5, is still subject to catastrophic cancellation. We deal with that by assuming its
227 * output may be incorrect, and adjusting the mesh topology to match (see commen t at the top of
228 * this file).
229 */
230
231 struct Edge {
232 Edge(Vertex* top, Vertex* bottom, int winding)
233 : fWinding(winding)
234 , fTop(top)
235 , fBottom(bottom)
236 , fLeft(nullptr)
237 , fRight(nullptr)
238 , fPrevEdgeAbove(nullptr)
239 , fNextEdgeAbove(nullptr)
240 , fPrevEdgeBelow(nullptr)
241 , fNextEdgeBelow(nullptr)
242 , fLeftPoly(nullptr)
243 , fRightPoly(nullptr) {
244 recompute();
245 }
246 int fWinding; // 1 == edge goes downward; -1 = edge goes upwar d.
247 Vertex* fTop; // The top vertex in vertex-sort-order (sweep_lt ).
248 Vertex* fBottom; // The bottom vertex in vertex-sort-order.
249 Edge* fLeft; // The linked list of edges in the active edge l ist.
250 Edge* fRight; // "
251 Edge* fPrevEdgeAbove; // The linked list of edges in the bottom Vertex 's "edges above".
252 Edge* fNextEdgeAbove; // "
253 Edge* fPrevEdgeBelow; // The linked list of edges in the top Vertex's "edges below".
254 Edge* fNextEdgeBelow; // "
255 Poly* fLeftPoly; // The Poly to the left of this edge, if any.
256 Poly* fRightPoly; // The Poly to the right of this edge, if any.
257 double fDX; // The line equation for this edge, in implicit form.
258 double fDY; // fDY * x + fDX * y + fC = 0, for point (x, y) on the line.
259 double fC;
260 double dist(const SkPoint& p) const {
261 return fDY * p.fX - fDX * p.fY + fC;
262 }
263 bool isRightOf(Vertex* v) const {
264 return dist(v->fPoint) < 0.0;
265 }
266 bool isLeftOf(Vertex* v) const {
267 return dist(v->fPoint) > 0.0;
268 }
269 void recompute() {
270 fDX = static_cast<double>(fBottom->fPoint.fX) - fTop->fPoint.fX;
271 fDY = static_cast<double>(fBottom->fPoint.fY) - fTop->fPoint.fY;
272 fC = static_cast<double>(fTop->fPoint.fY) * fBottom->fPoint.fX -
273 static_cast<double>(fTop->fPoint.fX) * fBottom->fPoint.fY;
274 }
275 bool intersect(const Edge& other, SkPoint* p) {
276 LOG("intersecting %g -> %g with %g -> %g\n",
277 fTop->fID, fBottom->fID,
278 other.fTop->fID, other.fBottom->fID);
279 if (fTop == other.fTop || fBottom == other.fBottom) {
280 return false;
281 }
282 double denom = fDX * other.fDY - fDY * other.fDX;
283 if (denom == 0.0) {
284 return false;
285 }
286 double dx = static_cast<double>(fTop->fPoint.fX) - other.fTop->fPoint.fX ;
287 double dy = static_cast<double>(fTop->fPoint.fY) - other.fTop->fPoint.fY ;
288 double sNumer = dy * other.fDX - dx * other.fDY;
289 double tNumer = dy * fDX - dx * fDY;
290 // If (sNumer / denom) or (tNumer / denom) is not in [0..1], exit early.
291 // This saves us doing the divide below unless absolutely necessary.
292 if (denom > 0.0 ? (sNumer < 0.0 || sNumer > denom || tNumer < 0.0 || tNu mer > denom)
293 : (sNumer > 0.0 || sNumer < denom || tNumer > 0.0 || tNu mer < denom)) {
294 return false;
295 }
296 double s = sNumer / denom;
297 SkASSERT(s >= 0.0 && s <= 1.0);
298 p->fX = SkDoubleToScalar(fTop->fPoint.fX + s * fDX);
299 p->fY = SkDoubleToScalar(fTop->fPoint.fY + s * fDY);
300 return true;
301 }
302 bool isActive(EdgeList* activeEdges) const {
303 return activeEdges && (fLeft || fRight || activeEdges->fHead == this);
304 }
305 };
306
307 /******************************************************************************* ********/
308
309 struct Poly {
310 Poly(int winding)
311 : fWinding(winding)
312 , fHead(nullptr)
313 , fTail(nullptr)
314 , fActive(nullptr)
315 , fNext(nullptr)
316 , fPartner(nullptr)
317 , fCount(0)
318 {
319 #if LOGGING_ENABLED
320 static int gID = 0;
321 fID = gID++;
322 LOG("*** created Poly %d\n", fID);
323 #endif
324 }
325 typedef enum { kNeither_Side, kLeft_Side, kRight_Side } Side;
326 struct MonotonePoly {
327 MonotonePoly()
328 : fSide(kNeither_Side)
329 , fHead(nullptr)
330 , fTail(nullptr)
331 , fPrev(nullptr)
332 , fNext(nullptr) {}
333 Side fSide;
334 Vertex* fHead;
335 Vertex* fTail;
336 MonotonePoly* fPrev;
337 MonotonePoly* fNext;
338 bool addVertex(Vertex* v, Side side, SkChunkAlloc& alloc) {
339 Vertex* newV = ALLOC_NEW(Vertex, (v->fPoint), alloc);
340 bool done = false;
341 if (fSide == kNeither_Side) {
342 fSide = side;
343 } else {
344 done = side != fSide;
345 }
346 if (fHead == nullptr) {
347 fHead = fTail = newV;
348 } else if (fSide == kRight_Side) {
349 newV->fPrev = fTail;
350 fTail->fNext = newV;
351 fTail = newV;
352 } else {
353 newV->fNext = fHead;
354 fHead->fPrev = newV;
355 fHead = newV;
356 }
357 return done;
358 }
359
360 SkPoint* emit(SkPoint* data) {
361 Vertex* first = fHead;
362 Vertex* v = first->fNext;
363 while (v != fTail) {
364 SkASSERT(v && v->fPrev && v->fNext);
365 Vertex* prev = v->fPrev;
366 Vertex* curr = v;
367 Vertex* next = v->fNext;
368 double ax = static_cast<double>(curr->fPoint.fX) - prev->fPoint. fX;
369 double ay = static_cast<double>(curr->fPoint.fY) - prev->fPoint. fY;
370 double bx = static_cast<double>(next->fPoint.fX) - curr->fPoint. fX;
371 double by = static_cast<double>(next->fPoint.fY) - curr->fPoint. fY;
372 if (ax * by - ay * bx >= 0.0) {
373 data = emit_triangle(prev, curr, next, data);
374 v->fPrev->fNext = v->fNext;
375 v->fNext->fPrev = v->fPrev;
376 if (v->fPrev == first) {
377 v = v->fNext;
378 } else {
379 v = v->fPrev;
380 }
381 } else {
382 v = v->fNext;
383 }
384 }
385 return data;
386 }
387 };
388 Poly* addVertex(Vertex* v, Side side, SkChunkAlloc& alloc) {
389 LOG("addVertex() to %d at %g (%g, %g), %s side\n", fID, v->fID, v->fPoin t.fX, v->fPoint.fY,
390 side == kLeft_Side ? "left" : side == kRight_Side ? "right" : "ne ither");
391 Poly* partner = fPartner;
392 Poly* poly = this;
393 if (partner) {
394 fPartner = partner->fPartner = nullptr;
395 }
396 if (!fActive) {
397 fActive = ALLOC_NEW(MonotonePoly, (), alloc);
398 }
399 if (fActive->addVertex(v, side, alloc)) {
400 if (fTail) {
401 fActive->fPrev = fTail;
402 fTail->fNext = fActive;
403 fTail = fActive;
404 } else {
405 fHead = fTail = fActive;
406 }
407 if (partner) {
408 partner->addVertex(v, side, alloc);
409 poly = partner;
410 } else {
411 Vertex* prev = fActive->fSide == Poly::kLeft_Side ?
412 fActive->fHead->fNext : fActive->fTail->fPrev;
413 fActive = ALLOC_NEW(MonotonePoly, , alloc);
414 fActive->addVertex(prev, Poly::kNeither_Side, alloc);
415 fActive->addVertex(v, side, alloc);
416 }
417 }
418 fCount++;
419 return poly;
420 }
421 void end(Vertex* v, SkChunkAlloc& alloc) {
422 LOG("end() %d at %g, %g\n", fID, v->fPoint.fX, v->fPoint.fY);
423 if (fPartner) {
424 fPartner = fPartner->fPartner = nullptr;
425 }
426 addVertex(v, fActive->fSide == kLeft_Side ? kRight_Side : kLeft_Side, al loc);
427 }
428 SkPoint* emit(SkPoint *data) {
429 if (fCount < 3) {
430 return data;
431 }
432 LOG("emit() %d, size %d\n", fID, fCount);
433 for (MonotonePoly* m = fHead; m != nullptr; m = m->fNext) {
434 data = m->emit(data);
435 }
436 return data;
437 }
438 int fWinding;
439 MonotonePoly* fHead;
440 MonotonePoly* fTail;
441 MonotonePoly* fActive;
442 Poly* fNext;
443 Poly* fPartner;
444 int fCount;
445 #if LOGGING_ENABLED
446 int fID;
447 #endif
448 };
449
450 /******************************************************************************* ********/
451
452 bool coincident(const SkPoint& a, const SkPoint& b) {
453 return a == b;
454 }
455
456 Poly* new_poly(Poly** head, Vertex* v, int winding, SkChunkAlloc& alloc) {
457 Poly* poly = ALLOC_NEW(Poly, (winding), alloc);
458 poly->addVertex(v, Poly::kNeither_Side, alloc);
459 poly->fNext = *head;
460 *head = poly;
461 return poly;
462 }
463
464 Vertex* append_point_to_contour(const SkPoint& p, Vertex* prev, Vertex** head,
465 SkChunkAlloc& alloc) {
466 Vertex* v = ALLOC_NEW(Vertex, (p), alloc);
467 #if LOGGING_ENABLED
468 static float gID = 0.0f;
469 v->fID = gID++;
470 #endif
471 if (prev) {
472 prev->fNext = v;
473 v->fPrev = prev;
474 } else {
475 *head = v;
476 }
477 return v;
478 }
479
480 Vertex* generate_quadratic_points(const SkPoint& p0,
481 const SkPoint& p1,
482 const SkPoint& p2,
483 SkScalar tolSqd,
484 Vertex* prev,
485 Vertex** head,
486 int pointsLeft,
487 SkChunkAlloc& alloc) {
488 SkScalar d = p1.distanceToLineSegmentBetweenSqd(p0, p2);
489 if (pointsLeft < 2 || d < tolSqd || !SkScalarIsFinite(d)) {
490 return append_point_to_contour(p2, prev, head, alloc);
491 }
492
493 const SkPoint q[] = {
494 { SkScalarAve(p0.fX, p1.fX), SkScalarAve(p0.fY, p1.fY) },
495 { SkScalarAve(p1.fX, p2.fX), SkScalarAve(p1.fY, p2.fY) },
496 };
497 const SkPoint r = { SkScalarAve(q[0].fX, q[1].fX), SkScalarAve(q[0].fY, q[1] .fY) };
498
499 pointsLeft >>= 1;
500 prev = generate_quadratic_points(p0, q[0], r, tolSqd, prev, head, pointsLeft , alloc);
501 prev = generate_quadratic_points(r, q[1], p2, tolSqd, prev, head, pointsLeft , alloc);
502 return prev;
503 }
504
505 Vertex* generate_cubic_points(const SkPoint& p0,
506 const SkPoint& p1,
507 const SkPoint& p2,
508 const SkPoint& p3,
509 SkScalar tolSqd,
510 Vertex* prev,
511 Vertex** head,
512 int pointsLeft,
513 SkChunkAlloc& alloc) {
514 SkScalar d1 = p1.distanceToLineSegmentBetweenSqd(p0, p3);
515 SkScalar d2 = p2.distanceToLineSegmentBetweenSqd(p0, p3);
516 if (pointsLeft < 2 || (d1 < tolSqd && d2 < tolSqd) ||
517 !SkScalarIsFinite(d1) || !SkScalarIsFinite(d2)) {
518 return append_point_to_contour(p3, prev, head, alloc);
519 }
520 const SkPoint q[] = {
521 { SkScalarAve(p0.fX, p1.fX), SkScalarAve(p0.fY, p1.fY) },
522 { SkScalarAve(p1.fX, p2.fX), SkScalarAve(p1.fY, p2.fY) },
523 { SkScalarAve(p2.fX, p3.fX), SkScalarAve(p2.fY, p3.fY) }
524 };
525 const SkPoint r[] = {
526 { SkScalarAve(q[0].fX, q[1].fX), SkScalarAve(q[0].fY, q[1].fY) },
527 { SkScalarAve(q[1].fX, q[2].fX), SkScalarAve(q[1].fY, q[2].fY) }
528 };
529 const SkPoint s = { SkScalarAve(r[0].fX, r[1].fX), SkScalarAve(r[0].fY, r[1] .fY) };
530 pointsLeft >>= 1;
531 prev = generate_cubic_points(p0, q[0], r[0], s, tolSqd, prev, head, pointsLe ft, alloc);
532 prev = generate_cubic_points(s, r[1], q[2], p3, tolSqd, prev, head, pointsLe ft, alloc);
533 return prev;
534 }
535
536 // Stage 1: convert the input path to a set of linear contours (linked list of V ertices).
537
538 void path_to_contours(const SkPath& path, SkScalar tolerance, const SkRect& clip Bounds,
539 Vertex** contours, SkChunkAlloc& alloc, bool *isLinear) {
540 SkScalar toleranceSqd = tolerance * tolerance;
541
542 SkPoint pts[4];
543 bool done = false;
544 *isLinear = true;
545 SkPath::Iter iter(path, false);
546 Vertex* prev = nullptr;
547 Vertex* head = nullptr;
548 if (path.isInverseFillType()) {
549 SkPoint quad[4];
550 clipBounds.toQuad(quad);
551 for (int i = 3; i >= 0; i--) {
552 prev = append_point_to_contour(quad[i], prev, &head, alloc);
553 }
554 head->fPrev = prev;
555 prev->fNext = head;
556 *contours++ = head;
557 head = prev = nullptr;
558 }
559 SkAutoConicToQuads converter;
560 while (!done) {
561 SkPath::Verb verb = iter.next(pts);
562 switch (verb) {
563 case SkPath::kConic_Verb: {
564 SkScalar weight = iter.conicWeight();
565 const SkPoint* quadPts = converter.computeQuads(pts, weight, tol eranceSqd);
566 for (int i = 0; i < converter.countQuads(); ++i) {
567 int pointsLeft = GrPathUtils::quadraticPointCount(quadPts, t olerance);
568 prev = generate_quadratic_points(quadPts[0], quadPts[1], qua dPts[2],
569 toleranceSqd, prev, &head, pointsLeft, alloc);
570 quadPts += 2;
571 }
572 *isLinear = false;
573 break;
574 }
575 case SkPath::kMove_Verb:
576 if (head) {
577 head->fPrev = prev;
578 prev->fNext = head;
579 *contours++ = head;
580 }
581 head = prev = nullptr;
582 prev = append_point_to_contour(pts[0], prev, &head, alloc);
583 break;
584 case SkPath::kLine_Verb: {
585 prev = append_point_to_contour(pts[1], prev, &head, alloc);
586 break;
587 }
588 case SkPath::kQuad_Verb: {
589 int pointsLeft = GrPathUtils::quadraticPointCount(pts, tolerance );
590 prev = generate_quadratic_points(pts[0], pts[1], pts[2], toleran ceSqd, prev,
591 &head, pointsLeft, alloc);
592 *isLinear = false;
593 break;
594 }
595 case SkPath::kCubic_Verb: {
596 int pointsLeft = GrPathUtils::cubicPointCount(pts, tolerance);
597 prev = generate_cubic_points(pts[0], pts[1], pts[2], pts[3],
598 toleranceSqd, prev, &head, pointsLeft, alloc);
599 *isLinear = false;
600 break;
601 }
602 case SkPath::kClose_Verb:
603 if (head) {
604 head->fPrev = prev;
605 prev->fNext = head;
606 *contours++ = head;
607 }
608 head = prev = nullptr;
609 break;
610 case SkPath::kDone_Verb:
611 if (head) {
612 head->fPrev = prev;
613 prev->fNext = head;
614 *contours++ = head;
615 }
616 done = true;
617 break;
618 }
619 }
620 }
621
622 inline bool apply_fill_type(SkPath::FillType fillType, int winding) {
623 switch (fillType) {
624 case SkPath::kWinding_FillType:
625 return winding != 0;
626 case SkPath::kEvenOdd_FillType:
627 return (winding & 1) != 0;
628 case SkPath::kInverseWinding_FillType:
629 return winding == 1;
630 case SkPath::kInverseEvenOdd_FillType:
631 return (winding & 1) == 1;
632 default:
633 SkASSERT(false);
634 return false;
635 }
636 }
637
638 Edge* new_edge(Vertex* prev, Vertex* next, SkChunkAlloc& alloc, Comparator& c) {
639 int winding = c.sweep_lt(prev->fPoint, next->fPoint) ? 1 : -1;
640 Vertex* top = winding < 0 ? next : prev;
641 Vertex* bottom = winding < 0 ? prev : next;
642 return ALLOC_NEW(Edge, (top, bottom, winding), alloc);
643 }
644
645 void remove_edge(Edge* edge, EdgeList* edges) {
646 LOG("removing edge %g -> %g\n", edge->fTop->fID, edge->fBottom->fID);
647 SkASSERT(edge->isActive(edges));
648 remove<Edge, &Edge::fLeft, &Edge::fRight>(edge, &edges->fHead, &edges->fTail );
649 }
650
651 void insert_edge(Edge* edge, Edge* prev, EdgeList* edges) {
652 LOG("inserting edge %g -> %g\n", edge->fTop->fID, edge->fBottom->fID);
653 SkASSERT(!edge->isActive(edges));
654 Edge* next = prev ? prev->fRight : edges->fHead;
655 insert<Edge, &Edge::fLeft, &Edge::fRight>(edge, prev, next, &edges->fHead, & edges->fTail);
656 }
657
658 void find_enclosing_edges(Vertex* v, EdgeList* edges, Edge** left, Edge** right) {
659 if (v->fFirstEdgeAbove) {
660 *left = v->fFirstEdgeAbove->fLeft;
661 *right = v->fLastEdgeAbove->fRight;
662 return;
663 }
664 Edge* next = nullptr;
665 Edge* prev;
666 for (prev = edges->fTail; prev != nullptr; prev = prev->fLeft) {
667 if (prev->isLeftOf(v)) {
668 break;
669 }
670 next = prev;
671 }
672 *left = prev;
673 *right = next;
674 return;
675 }
676
677 void find_enclosing_edges(Edge* edge, EdgeList* edges, Comparator& c, Edge** lef t, Edge** right) {
678 Edge* prev = nullptr;
679 Edge* next;
680 for (next = edges->fHead; next != nullptr; next = next->fRight) {
681 if ((c.sweep_gt(edge->fTop->fPoint, next->fTop->fPoint) && next->isRight Of(edge->fTop)) ||
682 (c.sweep_gt(next->fTop->fPoint, edge->fTop->fPoint) && edge->isLeftO f(next->fTop)) ||
683 (c.sweep_lt(edge->fBottom->fPoint, next->fBottom->fPoint) &&
684 next->isRightOf(edge->fBottom)) ||
685 (c.sweep_lt(next->fBottom->fPoint, edge->fBottom->fPoint) &&
686 edge->isLeftOf(next->fBottom))) {
687 break;
688 }
689 prev = next;
690 }
691 *left = prev;
692 *right = next;
693 return;
694 }
695
696 void fix_active_state(Edge* edge, EdgeList* activeEdges, Comparator& c) {
697 if (edge->isActive(activeEdges)) {
698 if (edge->fBottom->fProcessed || !edge->fTop->fProcessed) {
699 remove_edge(edge, activeEdges);
700 }
701 } else if (edge->fTop->fProcessed && !edge->fBottom->fProcessed) {
702 Edge* left;
703 Edge* right;
704 find_enclosing_edges(edge, activeEdges, c, &left, &right);
705 insert_edge(edge, left, activeEdges);
706 }
707 }
708
709 void insert_edge_above(Edge* edge, Vertex* v, Comparator& c) {
710 if (edge->fTop->fPoint == edge->fBottom->fPoint ||
711 c.sweep_gt(edge->fTop->fPoint, edge->fBottom->fPoint)) {
712 return;
713 }
714 LOG("insert edge (%g -> %g) above vertex %g\n", edge->fTop->fID, edge->fBott om->fID, v->fID);
715 Edge* prev = nullptr;
716 Edge* next;
717 for (next = v->fFirstEdgeAbove; next; next = next->fNextEdgeAbove) {
718 if (next->isRightOf(edge->fTop)) {
719 break;
720 }
721 prev = next;
722 }
723 insert<Edge, &Edge::fPrevEdgeAbove, &Edge::fNextEdgeAbove>(
724 edge, prev, next, &v->fFirstEdgeAbove, &v->fLastEdgeAbove);
725 }
726
727 void insert_edge_below(Edge* edge, Vertex* v, Comparator& c) {
728 if (edge->fTop->fPoint == edge->fBottom->fPoint ||
729 c.sweep_gt(edge->fTop->fPoint, edge->fBottom->fPoint)) {
730 return;
731 }
732 LOG("insert edge (%g -> %g) below vertex %g\n", edge->fTop->fID, edge->fBott om->fID, v->fID);
733 Edge* prev = nullptr;
734 Edge* next;
735 for (next = v->fFirstEdgeBelow; next; next = next->fNextEdgeBelow) {
736 if (next->isRightOf(edge->fBottom)) {
737 break;
738 }
739 prev = next;
740 }
741 insert<Edge, &Edge::fPrevEdgeBelow, &Edge::fNextEdgeBelow>(
742 edge, prev, next, &v->fFirstEdgeBelow, &v->fLastEdgeBelow);
743 }
744
745 void remove_edge_above(Edge* edge) {
746 LOG("removing edge (%g -> %g) above vertex %g\n", edge->fTop->fID, edge->fBo ttom->fID,
747 edge->fBottom->fID);
748 remove<Edge, &Edge::fPrevEdgeAbove, &Edge::fNextEdgeAbove>(
749 edge, &edge->fBottom->fFirstEdgeAbove, &edge->fBottom->fLastEdgeAbove);
750 }
751
752 void remove_edge_below(Edge* edge) {
753 LOG("removing edge (%g -> %g) below vertex %g\n", edge->fTop->fID, edge->fBo ttom->fID,
754 edge->fTop->fID);
755 remove<Edge, &Edge::fPrevEdgeBelow, &Edge::fNextEdgeBelow>(
756 edge, &edge->fTop->fFirstEdgeBelow, &edge->fTop->fLastEdgeBelow);
757 }
758
759 void erase_edge_if_zero_winding(Edge* edge, EdgeList* edges) {
760 if (edge->fWinding != 0) {
761 return;
762 }
763 LOG("erasing edge (%g -> %g)\n", edge->fTop->fID, edge->fBottom->fID);
764 remove_edge_above(edge);
765 remove_edge_below(edge);
766 if (edge->isActive(edges)) {
767 remove_edge(edge, edges);
768 }
769 }
770
771 void merge_collinear_edges(Edge* edge, EdgeList* activeEdges, Comparator& c);
772
773 void set_top(Edge* edge, Vertex* v, EdgeList* activeEdges, Comparator& c) {
774 remove_edge_below(edge);
775 edge->fTop = v;
776 edge->recompute();
777 insert_edge_below(edge, v, c);
778 fix_active_state(edge, activeEdges, c);
779 merge_collinear_edges(edge, activeEdges, c);
780 }
781
782 void set_bottom(Edge* edge, Vertex* v, EdgeList* activeEdges, Comparator& c) {
783 remove_edge_above(edge);
784 edge->fBottom = v;
785 edge->recompute();
786 insert_edge_above(edge, v, c);
787 fix_active_state(edge, activeEdges, c);
788 merge_collinear_edges(edge, activeEdges, c);
789 }
790
791 void merge_edges_above(Edge* edge, Edge* other, EdgeList* activeEdges, Comparato r& c) {
792 if (coincident(edge->fTop->fPoint, other->fTop->fPoint)) {
793 LOG("merging coincident above edges (%g, %g) -> (%g, %g)\n",
794 edge->fTop->fPoint.fX, edge->fTop->fPoint.fY,
795 edge->fBottom->fPoint.fX, edge->fBottom->fPoint.fY);
796 other->fWinding += edge->fWinding;
797 erase_edge_if_zero_winding(other, activeEdges);
798 edge->fWinding = 0;
799 erase_edge_if_zero_winding(edge, activeEdges);
800 } else if (c.sweep_lt(edge->fTop->fPoint, other->fTop->fPoint)) {
801 other->fWinding += edge->fWinding;
802 erase_edge_if_zero_winding(other, activeEdges);
803 set_bottom(edge, other->fTop, activeEdges, c);
804 } else {
805 edge->fWinding += other->fWinding;
806 erase_edge_if_zero_winding(edge, activeEdges);
807 set_bottom(other, edge->fTop, activeEdges, c);
808 }
809 }
810
811 void merge_edges_below(Edge* edge, Edge* other, EdgeList* activeEdges, Comparato r& c) {
812 if (coincident(edge->fBottom->fPoint, other->fBottom->fPoint)) {
813 LOG("merging coincident below edges (%g, %g) -> (%g, %g)\n",
814 edge->fTop->fPoint.fX, edge->fTop->fPoint.fY,
815 edge->fBottom->fPoint.fX, edge->fBottom->fPoint.fY);
816 other->fWinding += edge->fWinding;
817 erase_edge_if_zero_winding(other, activeEdges);
818 edge->fWinding = 0;
819 erase_edge_if_zero_winding(edge, activeEdges);
820 } else if (c.sweep_lt(edge->fBottom->fPoint, other->fBottom->fPoint)) {
821 edge->fWinding += other->fWinding;
822 erase_edge_if_zero_winding(edge, activeEdges);
823 set_top(other, edge->fBottom, activeEdges, c);
824 } else {
825 other->fWinding += edge->fWinding;
826 erase_edge_if_zero_winding(other, activeEdges);
827 set_top(edge, other->fBottom, activeEdges, c);
828 }
829 }
830
831 void merge_collinear_edges(Edge* edge, EdgeList* activeEdges, Comparator& c) {
832 if (edge->fPrevEdgeAbove && (edge->fTop == edge->fPrevEdgeAbove->fTop ||
833 !edge->fPrevEdgeAbove->isLeftOf(edge->fTop))) {
834 merge_edges_above(edge, edge->fPrevEdgeAbove, activeEdges, c);
835 } else if (edge->fNextEdgeAbove && (edge->fTop == edge->fNextEdgeAbove->fTop ||
836 !edge->isLeftOf(edge->fNextEdgeAbove->fT op))) {
837 merge_edges_above(edge, edge->fNextEdgeAbove, activeEdges, c);
838 }
839 if (edge->fPrevEdgeBelow && (edge->fBottom == edge->fPrevEdgeBelow->fBottom ||
840 !edge->fPrevEdgeBelow->isLeftOf(edge->fBottom)) ) {
841 merge_edges_below(edge, edge->fPrevEdgeBelow, activeEdges, c);
842 } else if (edge->fNextEdgeBelow && (edge->fBottom == edge->fNextEdgeBelow->f Bottom ||
843 !edge->isLeftOf(edge->fNextEdgeBelow->fB ottom))) {
844 merge_edges_below(edge, edge->fNextEdgeBelow, activeEdges, c);
845 }
846 }
847
848 void split_edge(Edge* edge, Vertex* v, EdgeList* activeEdges, Comparator& c, SkC hunkAlloc& alloc);
849
850 void cleanup_active_edges(Edge* edge, EdgeList* activeEdges, Comparator& c, SkCh unkAlloc& alloc) {
851 Vertex* top = edge->fTop;
852 Vertex* bottom = edge->fBottom;
853 if (edge->fLeft) {
854 Vertex* leftTop = edge->fLeft->fTop;
855 Vertex* leftBottom = edge->fLeft->fBottom;
856 if (c.sweep_gt(top->fPoint, leftTop->fPoint) && !edge->fLeft->isLeftOf(t op)) {
857 split_edge(edge->fLeft, edge->fTop, activeEdges, c, alloc);
858 } else if (c.sweep_gt(leftTop->fPoint, top->fPoint) && !edge->isRightOf( leftTop)) {
859 split_edge(edge, leftTop, activeEdges, c, alloc);
860 } else if (c.sweep_lt(bottom->fPoint, leftBottom->fPoint) &&
861 !edge->fLeft->isLeftOf(bottom)) {
862 split_edge(edge->fLeft, bottom, activeEdges, c, alloc);
863 } else if (c.sweep_lt(leftBottom->fPoint, bottom->fPoint) && !edge->isRi ghtOf(leftBottom)) {
864 split_edge(edge, leftBottom, activeEdges, c, alloc);
865 }
866 }
867 if (edge->fRight) {
868 Vertex* rightTop = edge->fRight->fTop;
869 Vertex* rightBottom = edge->fRight->fBottom;
870 if (c.sweep_gt(top->fPoint, rightTop->fPoint) && !edge->fRight->isRightO f(top)) {
871 split_edge(edge->fRight, top, activeEdges, c, alloc);
872 } else if (c.sweep_gt(rightTop->fPoint, top->fPoint) && !edge->isLeftOf( rightTop)) {
873 split_edge(edge, rightTop, activeEdges, c, alloc);
874 } else if (c.sweep_lt(bottom->fPoint, rightBottom->fPoint) &&
875 !edge->fRight->isRightOf(bottom)) {
876 split_edge(edge->fRight, bottom, activeEdges, c, alloc);
877 } else if (c.sweep_lt(rightBottom->fPoint, bottom->fPoint) &&
878 !edge->isLeftOf(rightBottom)) {
879 split_edge(edge, rightBottom, activeEdges, c, alloc);
880 }
881 }
882 }
883
884 void split_edge(Edge* edge, Vertex* v, EdgeList* activeEdges, Comparator& c, SkC hunkAlloc& alloc) {
885 LOG("splitting edge (%g -> %g) at vertex %g (%g, %g)\n",
886 edge->fTop->fID, edge->fBottom->fID,
887 v->fID, v->fPoint.fX, v->fPoint.fY);
888 if (c.sweep_lt(v->fPoint, edge->fTop->fPoint)) {
889 set_top(edge, v, activeEdges, c);
890 } else if (c.sweep_gt(v->fPoint, edge->fBottom->fPoint)) {
891 set_bottom(edge, v, activeEdges, c);
892 } else {
893 Edge* newEdge = ALLOC_NEW(Edge, (v, edge->fBottom, edge->fWinding), allo c);
894 insert_edge_below(newEdge, v, c);
895 insert_edge_above(newEdge, edge->fBottom, c);
896 set_bottom(edge, v, activeEdges, c);
897 cleanup_active_edges(edge, activeEdges, c, alloc);
898 fix_active_state(newEdge, activeEdges, c);
899 merge_collinear_edges(newEdge, activeEdges, c);
900 }
901 }
902
903 void merge_vertices(Vertex* src, Vertex* dst, Vertex** head, Comparator& c, SkCh unkAlloc& alloc) {
904 LOG("found coincident verts at %g, %g; merging %g into %g\n", src->fPoint.fX , src->fPoint.fY,
905 src->fID, dst->fID);
906 for (Edge* edge = src->fFirstEdgeAbove; edge;) {
907 Edge* next = edge->fNextEdgeAbove;
908 set_bottom(edge, dst, nullptr, c);
909 edge = next;
910 }
911 for (Edge* edge = src->fFirstEdgeBelow; edge;) {
912 Edge* next = edge->fNextEdgeBelow;
913 set_top(edge, dst, nullptr, c);
914 edge = next;
915 }
916 remove<Vertex, &Vertex::fPrev, &Vertex::fNext>(src, head, nullptr);
917 }
918
919 Vertex* check_for_intersection(Edge* edge, Edge* other, EdgeList* activeEdges, C omparator& c,
920 SkChunkAlloc& alloc) {
921 SkPoint p;
922 if (!edge || !other) {
923 return nullptr;
924 }
925 if (edge->intersect(*other, &p)) {
926 Vertex* v;
927 LOG("found intersection, pt is %g, %g\n", p.fX, p.fY);
928 if (p == edge->fTop->fPoint || c.sweep_lt(p, edge->fTop->fPoint)) {
929 split_edge(other, edge->fTop, activeEdges, c, alloc);
930 v = edge->fTop;
931 } else if (p == edge->fBottom->fPoint || c.sweep_gt(p, edge->fBottom->fP oint)) {
932 split_edge(other, edge->fBottom, activeEdges, c, alloc);
933 v = edge->fBottom;
934 } else if (p == other->fTop->fPoint || c.sweep_lt(p, other->fTop->fPoint )) {
935 split_edge(edge, other->fTop, activeEdges, c, alloc);
936 v = other->fTop;
937 } else if (p == other->fBottom->fPoint || c.sweep_gt(p, other->fBottom-> fPoint)) {
938 split_edge(edge, other->fBottom, activeEdges, c, alloc);
939 v = other->fBottom;
940 } else {
941 Vertex* nextV = edge->fTop;
942 while (c.sweep_lt(p, nextV->fPoint)) {
943 nextV = nextV->fPrev;
944 }
945 while (c.sweep_lt(nextV->fPoint, p)) {
946 nextV = nextV->fNext;
947 }
948 Vertex* prevV = nextV->fPrev;
949 if (coincident(prevV->fPoint, p)) {
950 v = prevV;
951 } else if (coincident(nextV->fPoint, p)) {
952 v = nextV;
953 } else {
954 v = ALLOC_NEW(Vertex, (p), alloc);
955 LOG("inserting between %g (%g, %g) and %g (%g, %g)\n",
956 prevV->fID, prevV->fPoint.fX, prevV->fPoint.fY,
957 nextV->fID, nextV->fPoint.fX, nextV->fPoint.fY);
958 #if LOGGING_ENABLED
959 v->fID = (nextV->fID + prevV->fID) * 0.5f;
960 #endif
961 v->fPrev = prevV;
962 v->fNext = nextV;
963 prevV->fNext = v;
964 nextV->fPrev = v;
965 }
966 split_edge(edge, v, activeEdges, c, alloc);
967 split_edge(other, v, activeEdges, c, alloc);
968 }
969 return v;
970 }
971 return nullptr;
972 }
973
974 void sanitize_contours(Vertex** contours, int contourCnt) {
975 for (int i = 0; i < contourCnt; ++i) {
976 SkASSERT(contours[i]);
977 for (Vertex* v = contours[i];;) {
978 if (coincident(v->fPrev->fPoint, v->fPoint)) {
979 LOG("vertex %g,%g coincident; removing\n", v->fPoint.fX, v->fPoi nt.fY);
980 if (v->fPrev == v) {
981 contours[i] = nullptr;
982 break;
983 }
984 v->fPrev->fNext = v->fNext;
985 v->fNext->fPrev = v->fPrev;
986 if (contours[i] == v) {
987 contours[i] = v->fNext;
988 }
989 v = v->fPrev;
990 } else {
991 v = v->fNext;
992 if (v == contours[i]) break;
993 }
994 }
995 }
996 }
997
998 void merge_coincident_vertices(Vertex** vertices, Comparator& c, SkChunkAlloc& a lloc) {
999 for (Vertex* v = (*vertices)->fNext; v != nullptr; v = v->fNext) {
1000 if (c.sweep_lt(v->fPoint, v->fPrev->fPoint)) {
1001 v->fPoint = v->fPrev->fPoint;
1002 }
1003 if (coincident(v->fPrev->fPoint, v->fPoint)) {
1004 merge_vertices(v->fPrev, v, vertices, c, alloc);
1005 }
1006 }
1007 }
1008
1009 // Stage 2: convert the contours to a mesh of edges connecting the vertices.
1010
1011 Vertex* build_edges(Vertex** contours, int contourCnt, Comparator& c, SkChunkAll oc& alloc) {
1012 Vertex* vertices = nullptr;
1013 Vertex* prev = nullptr;
1014 for (int i = 0; i < contourCnt; ++i) {
1015 for (Vertex* v = contours[i]; v != nullptr;) {
1016 Vertex* vNext = v->fNext;
1017 Edge* edge = new_edge(v->fPrev, v, alloc, c);
1018 if (edge->fWinding > 0) {
1019 insert_edge_below(edge, v->fPrev, c);
1020 insert_edge_above(edge, v, c);
1021 } else {
1022 insert_edge_below(edge, v, c);
1023 insert_edge_above(edge, v->fPrev, c);
1024 }
1025 merge_collinear_edges(edge, nullptr, c);
1026 if (prev) {
1027 prev->fNext = v;
1028 v->fPrev = prev;
1029 } else {
1030 vertices = v;
1031 }
1032 prev = v;
1033 v = vNext;
1034 if (v == contours[i]) break;
1035 }
1036 }
1037 if (prev) {
1038 prev->fNext = vertices->fPrev = nullptr;
1039 }
1040 return vertices;
1041 }
1042
1043 // Stage 3: sort the vertices by increasing sweep direction.
1044
1045 Vertex* sorted_merge(Vertex* a, Vertex* b, Comparator& c);
1046
1047 void front_back_split(Vertex* v, Vertex** pFront, Vertex** pBack) {
1048 Vertex* fast;
1049 Vertex* slow;
1050 if (!v || !v->fNext) {
1051 *pFront = v;
1052 *pBack = nullptr;
1053 } else {
1054 slow = v;
1055 fast = v->fNext;
1056
1057 while (fast != nullptr) {
1058 fast = fast->fNext;
1059 if (fast != nullptr) {
1060 slow = slow->fNext;
1061 fast = fast->fNext;
1062 }
1063 }
1064
1065 *pFront = v;
1066 *pBack = slow->fNext;
1067 slow->fNext->fPrev = nullptr;
1068 slow->fNext = nullptr;
1069 }
1070 }
1071
1072 void merge_sort(Vertex** head, Comparator& c) {
1073 if (!*head || !(*head)->fNext) {
1074 return;
1075 }
1076
1077 Vertex* a;
1078 Vertex* b;
1079 front_back_split(*head, &a, &b);
1080
1081 merge_sort(&a, c);
1082 merge_sort(&b, c);
1083
1084 *head = sorted_merge(a, b, c);
1085 }
1086
1087 inline void append_vertex(Vertex* v, Vertex** head, Vertex** tail) {
1088 insert<Vertex, &Vertex::fPrev, &Vertex::fNext>(v, *tail, nullptr, head, tail );
1089 }
1090
1091 inline void append_vertex_list(Vertex* v, Vertex** head, Vertex** tail) {
1092 insert<Vertex, &Vertex::fPrev, &Vertex::fNext>(v, *tail, v->fNext, head, tai l);
1093 }
1094
1095 Vertex* sorted_merge(Vertex* a, Vertex* b, Comparator& c) {
1096 Vertex* head = nullptr;
1097 Vertex* tail = nullptr;
1098
1099 while (a && b) {
1100 if (c.sweep_lt(a->fPoint, b->fPoint)) {
1101 Vertex* next = a->fNext;
1102 append_vertex(a, &head, &tail);
1103 a = next;
1104 } else {
1105 Vertex* next = b->fNext;
1106 append_vertex(b, &head, &tail);
1107 b = next;
1108 }
1109 }
1110 if (a) {
1111 append_vertex_list(a, &head, &tail);
1112 }
1113 if (b) {
1114 append_vertex_list(b, &head, &tail);
1115 }
1116 return head;
1117 }
1118
1119 // Stage 4: Simplify the mesh by inserting new vertices at intersecting edges.
1120
1121 void simplify(Vertex* vertices, Comparator& c, SkChunkAlloc& alloc) {
1122 LOG("simplifying complex polygons\n");
1123 EdgeList activeEdges;
1124 for (Vertex* v = vertices; v != nullptr; v = v->fNext) {
1125 if (!v->fFirstEdgeAbove && !v->fFirstEdgeBelow) {
1126 continue;
1127 }
1128 #if LOGGING_ENABLED
1129 LOG("\nvertex %g: (%g,%g)\n", v->fID, v->fPoint.fX, v->fPoint.fY);
1130 #endif
1131 Edge* leftEnclosingEdge = nullptr;
1132 Edge* rightEnclosingEdge = nullptr;
1133 bool restartChecks;
1134 do {
1135 restartChecks = false;
1136 find_enclosing_edges(v, &activeEdges, &leftEnclosingEdge, &rightEncl osingEdge);
1137 if (v->fFirstEdgeBelow) {
1138 for (Edge* edge = v->fFirstEdgeBelow; edge != nullptr; edge = ed ge->fNextEdgeBelow) {
1139 if (check_for_intersection(edge, leftEnclosingEdge, &activeE dges, c, alloc)) {
1140 restartChecks = true;
1141 break;
1142 }
1143 if (check_for_intersection(edge, rightEnclosingEdge, &active Edges, c, alloc)) {
1144 restartChecks = true;
1145 break;
1146 }
1147 }
1148 } else {
1149 if (Vertex* pv = check_for_intersection(leftEnclosingEdge, right EnclosingEdge,
1150 &activeEdges, c, alloc)) {
1151 if (c.sweep_lt(pv->fPoint, v->fPoint)) {
1152 v = pv;
1153 }
1154 restartChecks = true;
1155 }
1156
1157 }
1158 } while (restartChecks);
1159 for (Edge* e = v->fFirstEdgeAbove; e; e = e->fNextEdgeAbove) {
1160 remove_edge(e, &activeEdges);
1161 }
1162 Edge* leftEdge = leftEnclosingEdge;
1163 for (Edge* e = v->fFirstEdgeBelow; e; e = e->fNextEdgeBelow) {
1164 insert_edge(e, leftEdge, &activeEdges);
1165 leftEdge = e;
1166 }
1167 v->fProcessed = true;
1168 }
1169 }
1170
1171 // Stage 5: Tessellate the simplified mesh into monotone polygons.
1172
1173 Poly* tessellate(Vertex* vertices, SkChunkAlloc& alloc) {
1174 LOG("tessellating simple polygons\n");
1175 EdgeList activeEdges;
1176 Poly* polys = nullptr;
1177 for (Vertex* v = vertices; v != nullptr; v = v->fNext) {
1178 if (!v->fFirstEdgeAbove && !v->fFirstEdgeBelow) {
1179 continue;
1180 }
1181 #if LOGGING_ENABLED
1182 LOG("\nvertex %g: (%g,%g)\n", v->fID, v->fPoint.fX, v->fPoint.fY);
1183 #endif
1184 Edge* leftEnclosingEdge = nullptr;
1185 Edge* rightEnclosingEdge = nullptr;
1186 find_enclosing_edges(v, &activeEdges, &leftEnclosingEdge, &rightEnclosin gEdge);
1187 Poly* leftPoly = nullptr;
1188 Poly* rightPoly = nullptr;
1189 if (v->fFirstEdgeAbove) {
1190 leftPoly = v->fFirstEdgeAbove->fLeftPoly;
1191 rightPoly = v->fLastEdgeAbove->fRightPoly;
1192 } else {
1193 leftPoly = leftEnclosingEdge ? leftEnclosingEdge->fRightPoly : nullp tr;
1194 rightPoly = rightEnclosingEdge ? rightEnclosingEdge->fLeftPoly : nul lptr;
1195 }
1196 #if LOGGING_ENABLED
1197 LOG("edges above:\n");
1198 for (Edge* e = v->fFirstEdgeAbove; e; e = e->fNextEdgeAbove) {
1199 LOG("%g -> %g, lpoly %d, rpoly %d\n", e->fTop->fID, e->fBottom->fID,
1200 e->fLeftPoly ? e->fLeftPoly->fID : -1, e->fRightPoly ? e->fRight Poly->fID : -1);
1201 }
1202 LOG("edges below:\n");
1203 for (Edge* e = v->fFirstEdgeBelow; e; e = e->fNextEdgeBelow) {
1204 LOG("%g -> %g, lpoly %d, rpoly %d\n", e->fTop->fID, e->fBottom->fID,
1205 e->fLeftPoly ? e->fLeftPoly->fID : -1, e->fRightPoly ? e->fRight Poly->fID : -1);
1206 }
1207 #endif
1208 if (v->fFirstEdgeAbove) {
1209 if (leftPoly) {
1210 leftPoly = leftPoly->addVertex(v, Poly::kRight_Side, alloc);
1211 }
1212 if (rightPoly) {
1213 rightPoly = rightPoly->addVertex(v, Poly::kLeft_Side, alloc);
1214 }
1215 for (Edge* e = v->fFirstEdgeAbove; e != v->fLastEdgeAbove; e = e->fN extEdgeAbove) {
1216 Edge* leftEdge = e;
1217 Edge* rightEdge = e->fNextEdgeAbove;
1218 SkASSERT(rightEdge->isRightOf(leftEdge->fTop));
1219 remove_edge(leftEdge, &activeEdges);
1220 if (leftEdge->fRightPoly) {
1221 leftEdge->fRightPoly->end(v, alloc);
1222 }
1223 if (rightEdge->fLeftPoly && rightEdge->fLeftPoly != leftEdge->fR ightPoly) {
1224 rightEdge->fLeftPoly->end(v, alloc);
1225 }
1226 }
1227 remove_edge(v->fLastEdgeAbove, &activeEdges);
1228 if (!v->fFirstEdgeBelow) {
1229 if (leftPoly && rightPoly && leftPoly != rightPoly) {
1230 SkASSERT(leftPoly->fPartner == nullptr && rightPoly->fPartne r == nullptr);
1231 rightPoly->fPartner = leftPoly;
1232 leftPoly->fPartner = rightPoly;
1233 }
1234 }
1235 }
1236 if (v->fFirstEdgeBelow) {
1237 if (!v->fFirstEdgeAbove) {
1238 if (leftPoly && leftPoly == rightPoly) {
1239 // Split the poly.
1240 if (leftPoly->fActive->fSide == Poly::kLeft_Side) {
1241 leftPoly = new_poly(&polys, leftEnclosingEdge->fTop, lef tPoly->fWinding,
1242 alloc);
1243 leftPoly->addVertex(v, Poly::kRight_Side, alloc);
1244 rightPoly->addVertex(v, Poly::kLeft_Side, alloc);
1245 leftEnclosingEdge->fRightPoly = leftPoly;
1246 } else {
1247 rightPoly = new_poly(&polys, rightEnclosingEdge->fTop, r ightPoly->fWinding,
1248 alloc);
1249 rightPoly->addVertex(v, Poly::kLeft_Side, alloc);
1250 leftPoly->addVertex(v, Poly::kRight_Side, alloc);
1251 rightEnclosingEdge->fLeftPoly = rightPoly;
1252 }
1253 } else {
1254 if (leftPoly) {
1255 leftPoly = leftPoly->addVertex(v, Poly::kRight_Side, all oc);
1256 }
1257 if (rightPoly) {
1258 rightPoly = rightPoly->addVertex(v, Poly::kLeft_Side, al loc);
1259 }
1260 }
1261 }
1262 Edge* leftEdge = v->fFirstEdgeBelow;
1263 leftEdge->fLeftPoly = leftPoly;
1264 insert_edge(leftEdge, leftEnclosingEdge, &activeEdges);
1265 for (Edge* rightEdge = leftEdge->fNextEdgeBelow; rightEdge;
1266 rightEdge = rightEdge->fNextEdgeBelow) {
1267 insert_edge(rightEdge, leftEdge, &activeEdges);
1268 int winding = leftEdge->fLeftPoly ? leftEdge->fLeftPoly->fWindin g : 0;
1269 winding += leftEdge->fWinding;
1270 if (winding != 0) {
1271 Poly* poly = new_poly(&polys, v, winding, alloc);
1272 leftEdge->fRightPoly = rightEdge->fLeftPoly = poly;
1273 }
1274 leftEdge = rightEdge;
1275 }
1276 v->fLastEdgeBelow->fRightPoly = rightPoly;
1277 }
1278 #if LOGGING_ENABLED
1279 LOG("\nactive edges:\n");
1280 for (Edge* e = activeEdges.fHead; e != nullptr; e = e->fRight) {
1281 LOG("%g -> %g, lpoly %d, rpoly %d\n", e->fTop->fID, e->fBottom->fID,
1282 e->fLeftPoly ? e->fLeftPoly->fID : -1, e->fRightPoly ? e->fRight Poly->fID : -1);
1283 }
1284 #endif
1285 }
1286 return polys;
1287 }
1288
1289 // This is a driver function which calls stages 2-5 in turn.
1290
1291 Poly* contours_to_polys(Vertex** contours, int contourCnt, const SkRect& pathBou nds,
1292 SkChunkAlloc& alloc) {
1293 Comparator c;
1294 if (pathBounds.width() > pathBounds.height()) {
1295 c.sweep_lt = sweep_lt_horiz;
1296 c.sweep_gt = sweep_gt_horiz;
1297 } else {
1298 c.sweep_lt = sweep_lt_vert;
1299 c.sweep_gt = sweep_gt_vert;
1300 }
1301 #if LOGGING_ENABLED
1302 for (int i = 0; i < contourCnt; ++i) {
1303 Vertex* v = contours[i];
1304 SkASSERT(v);
1305 LOG("path.moveTo(%20.20g, %20.20g);\n", v->fPoint.fX, v->fPoint.fY);
1306 for (v = v->fNext; v != contours[i]; v = v->fNext) {
1307 LOG("path.lineTo(%20.20g, %20.20g);\n", v->fPoint.fX, v->fPoint.fY);
1308 }
1309 }
1310 #endif
1311 sanitize_contours(contours, contourCnt);
1312 Vertex* vertices = build_edges(contours, contourCnt, c, alloc);
1313 if (!vertices) {
1314 return nullptr;
1315 }
1316
1317 // Sort vertices in Y (secondarily in X).
1318 merge_sort(&vertices, c);
1319 merge_coincident_vertices(&vertices, c, alloc);
1320 #if LOGGING_ENABLED
1321 for (Vertex* v = vertices; v != nullptr; v = v->fNext) {
1322 static float gID = 0.0f;
1323 v->fID = gID++;
1324 }
1325 #endif
1326 simplify(vertices, c, alloc);
1327 return tessellate(vertices, alloc);
1328 }
1329
1330 Poly* path_to_polys(const SkPath& path, SkScalar tolerance, const SkRect& clipBo unds,
1331 int contourCnt, SkChunkAlloc& alloc, bool* isLinear) {
1332 SkPath::FillType fillType = path.getFillType();
1333 if (SkPath::IsInverseFillType(fillType)) {
1334 contourCnt++;
1335 }
1336 SkAutoTDeleteArray<Vertex*> contours(new Vertex* [contourCnt]);
1337
1338 path_to_contours(path, tolerance, clipBounds, contours.get(), alloc, isLinea r);
1339 return contours_to_polys(contours.get(), contourCnt, path.getBounds(), alloc );
1340 }
1341
1342 void get_contour_count_and_size_estimate(const SkPath& path, SkScalar tolerance, int* contourCnt,
1343 int* sizeEstimate) {
1344 int maxPts = GrPathUtils::worstCasePointCount(path, contourCnt, tolerance);
1345 if (maxPts <= 0) {
1346 *contourCnt = 0;
1347 return;
1348 }
1349 if (maxPts > ((int)SK_MaxU16 + 1)) {
1350 SkDebugf("Path not rendered, too many verts (%d)\n", maxPts);
1351 *contourCnt = 0;
1352 return;
1353 }
1354 // For the initial size of the chunk allocator, estimate based on the point count:
1355 // one vertex per point for the initial passes, plus two for the vertices in the
1356 // resulting Polys, since the same point may end up in two Polys. Assume mi nimal
1357 // connectivity of one Edge per Vertex (will grow for intersections).
1358 *sizeEstimate = maxPts * (3 * sizeof(Vertex) + sizeof(Edge));
1359 }
1360
1361 int count_points(Poly* polys, SkPath::FillType fillType) {
1362 int count = 0;
1363 for (Poly* poly = polys; poly; poly = poly->fNext) {
1364 if (apply_fill_type(fillType, poly->fWinding) && poly->fCount >= 3) {
1365 count += (poly->fCount - 2) * (TESSELLATOR_WIREFRAME ? 6 : 3);
1366 }
1367 }
1368 return count;
1369 }
1370
1371 } // namespace
1372
1373 namespace GrTessellator {
1374
1375 // Stage 6: Triangulate the monotone polygons into a vertex buffer.
1376
1377 int PathToTriangles(const SkPath& path, SkScalar tolerance, const SkRect& clipBo unds,
1378 GrResourceProvider* resourceProvider,
1379 SkAutoTUnref<GrVertexBuffer>& vertexBuffer, bool canMapVB, b ool* isLinear) {
1380 int contourCnt;
1381 int sizeEstimate;
1382 get_contour_count_and_size_estimate(path, tolerance, &contourCnt, &sizeEstim ate);
1383 if (contourCnt <= 0) {
1384 return 0;
1385 }
1386 SkChunkAlloc alloc(sizeEstimate);
1387 Poly* polys = path_to_polys(path, tolerance, clipBounds, contourCnt, alloc, isLinear);
1388 SkPath::FillType fillType = path.getFillType();
1389 int count = count_points(polys, fillType);
1390 if (0 == count) {
1391 return 0;
1392 }
1393
1394 size_t size = count * sizeof(SkPoint);
1395 if (!vertexBuffer.get() || vertexBuffer->gpuMemorySize() < size) {
1396 vertexBuffer.reset(resourceProvider->createVertexBuffer(
1397 size, GrResourceProvider::kStatic_BufferUsage, 0));
1398 }
1399 if (!vertexBuffer.get()) {
1400 SkDebugf("Could not allocate vertices\n");
1401 return 0;
1402 }
1403 SkPoint* verts;
1404 if (canMapVB) {
1405 verts = static_cast<SkPoint*>(vertexBuffer->map());
1406 } else {
1407 verts = new SkPoint[count];
1408 }
1409 SkPoint* end = verts;
1410 for (Poly* poly = polys; poly; poly = poly->fNext) {
1411 if (apply_fill_type(fillType, poly->fWinding)) {
1412 end = poly->emit(end);
1413 }
1414 }
1415 int actualCount = static_cast<int>(end - verts);
1416 LOG("actual count: %d\n", actualCount);
1417 SkASSERT(actualCount <= count);
1418 if (canMapVB) {
1419 vertexBuffer->unmap();
1420 } else {
1421 vertexBuffer->updateData(verts, actualCount * sizeof(SkPoint));
1422 delete[] verts;
1423 }
1424
1425 return actualCount;
1426 }
1427
1428 int PathToVertices(const SkPath& path, SkScalar tolerance, const SkRect& clipBou nds,
1429 GrTessellator::WindingVertex** verts) {
1430 int contourCnt;
1431 int sizeEstimate;
1432 get_contour_count_and_size_estimate(path, tolerance, &contourCnt, &sizeEstim ate);
1433 if (contourCnt <= 0) {
1434 return 0;
1435 }
1436 SkChunkAlloc alloc(sizeEstimate);
1437 bool isLinear;
1438 Poly* polys = path_to_polys(path, tolerance, clipBounds, contourCnt, alloc, &isLinear);
1439 SkPath::FillType fillType = path.getFillType();
1440 int count = count_points(polys, fillType);
1441 if (0 == count) {
1442 *verts = nullptr;
1443 return 0;
1444 }
1445
1446 *verts = new GrTessellator::WindingVertex[count];
1447 GrTessellator::WindingVertex* vertsEnd = *verts;
1448 SkPoint* points = new SkPoint[count];
1449 SkPoint* pointsEnd = points;
1450 for (Poly* poly = polys; poly; poly = poly->fNext) {
1451 if (apply_fill_type(fillType, poly->fWinding)) {
1452 SkPoint* start = pointsEnd;
1453 pointsEnd = poly->emit(pointsEnd);
1454 while (start != pointsEnd) {
1455 vertsEnd->fPos = *start;
1456 vertsEnd->fWinding = poly->fWinding;
1457 ++start;
1458 ++vertsEnd;
1459 }
1460 }
1461 }
1462 int actualCount = static_cast<int>(vertsEnd - *verts);
1463 SkASSERT(actualCount <= count);
1464 SkASSERT(pointsEnd - points == actualCount);
1465 delete[] points;
1466 return actualCount;
1467 }
1468
1469 } // 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