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

Issues Search
    My Issues | Starred     Open | Closed | All

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

Issue 855513004: Tessellating GPU path renderer. (Closed) Base URL: https://skia.googlesource.com/skia.git@master
Patch Set: Created 5 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
« src/gpu/GrTessellatingPathRenderer.h ('K') | « src/gpu/GrTessellatingPathRenderer.h ('k') | tests/ConcavePathTests.cpp » ('j') | tests/ConcavePathTests.cpp » ('J')
Toggle Intra-line Diffs ('i') | Expand Comments ('e') | Collapse Comments ('c') | Show Comments Hide Comments ('s')
OLDNEW
(Empty)
1 /*
2 * Copyright 2014 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 "GrTessellatingPathRenderer.h"
9
10 #include "GrDefaultGeoProcFactory.h"
11 #include "GrPathUtils.h"
12 #include "SkChunkAlloc.h"
13 #include "SkGeometry.h"
14 #include "SkStroke.h"
15
16 #include <stdio.h> // FIXME
17
18 #define LOGGING_ENABLED 0
19
20 #if LOGGING_ENABLED
21 #define LOG printf
22 #else
23 #define LOG(...)
24 #endif
25
26 #define ALLOC_NEW(Type, args, alloc) \
27 SkNEW_PLACEMENT_ARGS(alloc.allocThrow(sizeof(Type)), Type, args)
28
29 bool GrTessellatingPathRenderer::gWireframe = false;
30
31 namespace {
32
33 struct Vertex;
34 struct Edge;
35 struct Poly;
36
37 template <class T, T* T::*Prev, T* T::*Next>
38 void insert(T* t, T* prev, T* next, T** head, T** tail)
39 {
40 t->*Prev = prev;
41 t->*Next = next;
42 if (prev) {
43 prev->*Next = t;
44 } else if (head) {
45 *head = t;
46 }
47 if (next) {
48 next->*Prev = t;
49 } else if (tail) {
50 *tail = t;
51 }
52 }
53
54 template <class T, T* T::*Prev, T* T::*Next>
55 void remove(T* t, T** head, T** tail)
56 {
57 if (t->*Prev) {
58 t->*Prev->*Next = t->*Next;
59 } else if (head) {
60 *head = t->*Next;
61 }
62 if (t->*Next) {
63 t->*Next->*Prev = t->*Prev;
64 } else if (tail) {
65 *tail = t->*Prev;
66 }
67 t->*Prev = t->*Next = NULL;
68 }
69
70 struct Vertex {
71 Vertex(const SkPoint& point)
72 : fPoint(point), fPrev(NULL), fNext(NULL)
73 , fFirstEdgeAbove(NULL), fLastEdgeAbove(NULL)
74 , fFirstEdgeBelow(NULL), fLastEdgeBelow(NULL)
75 , fInterior(false)
76 , fProcessed(false)
77 #if LOGGING_ENABLED
78 , fID (-1.0f)
79 #endif
80 {}
81 SkPoint fPoint;
82 Vertex* fPrev;
83 Vertex* fNext;
84 Edge* fFirstEdgeAbove;
85 Edge* fLastEdgeAbove;
86 Edge* fFirstEdgeBelow;
87 Edge* fLastEdgeBelow;
88 bool fInterior;
89 bool fProcessed;
90 #if LOGGING_ENABLED
91 float fID;
92 #endif
93 };
94
95 bool operator<(const SkPoint& a, const SkPoint& b) {
96 SkScalar valuea = a.fY;
97 SkScalar valueb = b.fY;
98
99 if (valuea == valueb) {
100 valuea = a.fX;
101 valueb = b.fX;
102 }
103
104 return valuea < valueb;
105 }
106
107 bool operator>(const SkPoint& a, const SkPoint& b) {
108 SkScalar valuea = a.fY;
109 SkScalar valueb = b.fY;
110
111 if (valuea == valueb) {
112 valuea = a.fX;
113 valueb = b.fX;
114 }
115
116 return valuea > valueb;
117 }
118
119 inline void* emit_vertex(Vertex* v, GrColor color, bool antiAlias, bool tweakAlp ha, void* data) {
120 if (antiAlias) {
121 uint32_t alpha = v->fInterior ? 0xFF000000 : 0;
122 if (tweakAlpha) {
123 struct Vert {
124 SkPoint fPosition;
125 GrColor fColor;
126 };
127 Vert* d = static_cast<Vert*>(data);
128 d->fPosition = v->fPoint;
129 d->fColor = (color & 0x00FFFFFF) | alpha;
130 d++;
131 return d;
132 } else {
133 struct VertSeparateAlpha {
134 SkPoint fPosition;
135 GrColor fColor;
136 float fAlpha;
137 };
138 VertSeparateAlpha* d = static_cast<VertSeparateAlpha*>(data);
139 d->fPosition = v->fPoint;
140 d->fColor = color;
141 d->fAlpha = (alpha >> 24) / 255.0f;
142 d++;
143 return d;
144 }
145 } else {
146 SkPoint* d = static_cast<SkPoint*>(data);
147 *d++ = v->fPoint;
148 return d;
149 }
150 }
151
152 void* emit_triangle(Vertex* v0, Vertex* v1, Vertex* v2, GrColor color, bool anti Alias, bool tweakAlpha, void* data) {
153 if (GrTessellatingPathRenderer::gWireframe) {
154 data = emit_vertex(v0, color, antiAlias, tweakAlpha, data);
155 data = emit_vertex(v1, color, antiAlias, tweakAlpha, data);
156 data = emit_vertex(v1, color, antiAlias, tweakAlpha, data);
157 data = emit_vertex(v2, color, antiAlias, tweakAlpha, data);
158 data = emit_vertex(v2, color, antiAlias, tweakAlpha, data);
159 data = emit_vertex(v0, color, antiAlias, tweakAlpha, data);
160 } else {
161 data = emit_vertex(v0, color, antiAlias, tweakAlpha, data);
162 data = emit_vertex(v1, color, antiAlias, tweakAlpha, data);
163 data = emit_vertex(v2, color, antiAlias, tweakAlpha, data);
164 }
165 return data;
166 }
167
168 Vertex* new_boundary(const SkPoint& point, SkChunkAlloc& alloc) {
169 LOG("*** created boundary at point %g, %g\n", point.fX, point.fY);
170 return ALLOC_NEW(Vertex, (point), alloc);
171 }
172
173 bool boundary_is_closed(Vertex* head) {
174 for (Vertex* v = head; v; v = v->fNext) {
175 if (v->fNext == head) {
176 return true;
177 }
178 }
179 return false;
180 }
181
182 void reverse_boundary(Vertex* head) {
183 for (Vertex* v = head; v;) {
184 SkTSwap(v->fPrev, v->fNext);
185 v->fInterior = true;
186 v = v->fNext;
187 if (v == head) {
188 break;
189 }
190 }
191 }
192
193 void end_boundary(const SkPoint& point, Vertex* prev, Vertex* next, bool interio r, SkTDArray<Vertex*>* boundaries, SkChunkAlloc& alloc) {
194 LOG("stitching together left & right boundaries, %g, %g -> %g, %g -> %g, %g\ n", prev->fPoint.fX, prev->fPoint.fY, point.fX, point.fY, next->fPoint.fX, next- >fPoint.fY);
195 Vertex* v = ALLOC_NEW(Vertex, (point), alloc);
196 v->fPrev = prev;
197 v->fNext = next;
198 next->fPrev = prev->fNext = v;
199 // FIXME: is there a better way?
200 if (boundary_is_closed(v)) {
201 LOG("ending %s boundary\n", interior ? "interior" : "exterior");
202 if (interior) {
203 reverse_boundary(v);
204 }
205 *(boundaries->append()) = v;
206 }
207 }
208
209 Vertex* add_vertex_to_boundary_left(const SkPoint& point, Vertex* next, SkChunkA lloc& alloc) {
210 Vertex* v = ALLOC_NEW(Vertex, (point), alloc);
211 next->fPrev = v;
212 v->fNext = next;
213 LOG("adding to boundary left, v %g, %g -> next %g, %g\n", v->fPoint.fX, v->f Point.fY, next->fPoint.fX, next->fPoint.fY);
214 return v;
215 }
216
217 Vertex* add_vertex_to_boundary_right(const SkPoint& point, Vertex* prev, SkChunk Alloc& alloc) {
218 Vertex* v = ALLOC_NEW(Vertex, (point), alloc);
219 prev->fNext = v;
220 v->fPrev = prev;
221 LOG("adding to boundary right, prev %g, %g -> v %g, %g\n", prev->fPoint.fX, prev->fPoint.fY, v->fPoint.fX, v->fPoint.fY);
222 return v;
223 }
224
225 struct Edge {
226 Edge(Vertex* top, Vertex* bottom, int winding) :
227 fWinding(winding),
228 fTop(top),
229 fBottom(bottom),
230 fLeft(NULL), fRight(NULL),
231 fPrevEdgeAbove(NULL), fNextEdgeAbove(NULL),
232 fPrevEdgeBelow(NULL), fNextEdgeBelow(NULL),
233 fLeftPoly(NULL), fRightPoly(NULL),
234 fLeftBoundary(NULL), fRightBoundary(NULL),
235 fDX(static_cast<double>(fBottom->fPoint.fX) - fTop->fPoint.fX),
236 fDY(static_cast<double>(fBottom->fPoint.fY) - fTop->fPoint.fY),
237 fC(static_cast<double>(fTop->fPoint.fY) * fBottom->fPoint.fX - static_ca st<double>(fTop->fPoint.fX) * fBottom->fPoint.fY) {}
238 int fWinding;
239 Vertex* fTop;
240 Vertex* fBottom;
241 Edge* fLeft;
242 Edge* fRight;
243 Edge* fPrevEdgeAbove;
244 Edge* fNextEdgeAbove;
245 Edge* fPrevEdgeBelow;
246 Edge* fNextEdgeBelow;
247 Poly* fLeftPoly;
248 Poly* fRightPoly;
249 Vertex* fLeftBoundary;
250 Vertex* fRightBoundary;
251 double fDX;
252 double fDY;
253 double fC;
254 double dist(const SkPoint& p) const {
255 return fDY * p.fX - fDX * p.fY + fC;
256 }
257 bool isRightOf(Vertex* v) const {
258 return v != fTop && v != fBottom && dist(v->fPoint) < 0.0;
259 }
260 bool isLeftOf(Vertex* v) const {
261 return v != fTop && v != fBottom && dist(v->fPoint) > 0.0;
262 }
263 void recompute() {
264 fDX = static_cast<double>(fBottom->fPoint.fX) - fTop->fPoint.fX;
265 fDY = static_cast<double>(fBottom->fPoint.fY) - fTop->fPoint.fY;
266 fC = static_cast<double>(fTop->fPoint.fY) * fBottom->fPoint.fX - static_ cast<double>(fTop->fPoint.fX) * fBottom->fPoint.fY;
267 }
268 bool intersect(const Edge& other, SkPoint* p) {
269 LOG("intersecting %g -> %g with %g -> %g\n",
270 fTop->fID, fBottom->fID,
271 other.fTop->fID, other.fBottom->fID);
272 if (fTop == other.fTop || fBottom == other.fBottom) {
273 return false;
274 }
275 double denom = fDX * other.fDY - fDY * other.fDX;
276 if (denom == 0.0) {
277 return false;
278 }
279 double dx = static_cast<double>(fTop->fPoint.fX) - other.fTop->fPoint.fX ;
280 double dy = static_cast<double>(fTop->fPoint.fY) - other.fTop->fPoint.fY ;
281 double sNumer = dy * other.fDX - dx * other.fDY;
282 double tNumer = dy * fDX - dx * fDY;
283 if (denom > 0.0 ? (sNumer < 0.0 || sNumer > denom || tNumer < 0.0 || tNu mer > denom)
284 : (sNumer > 0.0 || sNumer < denom || tNumer > 0.0 || tNu mer < denom)) {
285 return false;
286 }
287 double s = sNumer / denom;
288 p->fX = fTop->fPoint.fX + s * fDX;
289 p->fY = fTop->fPoint.fY + s * fDY;
290 return true;
291 }
292 bool isActive(Edge** activeEdges) const {
293 return activeEdges && (fLeft || fRight || *activeEdges == this);
294 }
295 };
296
297 struct Poly {
298 Poly(int winding) : fWinding(winding), fHead(NULL), fTail(NULL), fActive(NUL L), fNext(NULL), fPartner(NULL), fCount(0)
299 {
300 #if LOGGING_ENABLED
301 static int gID = 0;
302 fID = gID++;
303 LOG("*** created Poly %d\n", fID);
304 #endif
305 }
306 typedef enum { kNeither_Side, kLeft_Side, kRight_Side } Side;
307 struct MonotonePoly {
308 MonotonePoly() : fSide(kNeither_Side), fHead(NULL), fTail(NULL), fPrev(N ULL), fNext(NULL) {}
309 Side fSide;
310 Vertex* fHead;
311 Vertex* fTail;
312 MonotonePoly* fPrev;
313 MonotonePoly* fNext;
314 bool addVertex(Vertex* v, Side side, SkChunkAlloc& alloc) {
315 Vertex* newV = ALLOC_NEW(Vertex, (v->fPoint), alloc);
316 newV->fInterior = v->fInterior;
317 bool done = false;
318 if (fSide == kNeither_Side) {
319 fSide = side;
320 } else {
321 done = side != fSide;
322 }
323 if (fHead == NULL) {
324 fHead = fTail = newV;
325 } else if (fSide == kRight_Side) {
326 newV->fPrev = fTail;
327 fTail->fNext = newV;
328 fTail = newV;
329 } else {
330 newV->fNext = fHead;
331 fHead->fPrev = newV;
332 fHead = newV;
333 }
334 return done;
335 }
336
337 void* emit(bool antiAlias, bool tweakAlpha, GrColor color, void* data) {
338 Vertex* first = fHead;
339 Vertex* v = first->fNext;
340 while (v != fTail) {
341 SkASSERT(v && v->fPrev && v->fNext);
342 #ifdef SK_DEBUG
343 validate();
344 #endif
345 Vertex* prev = v->fPrev;
346 Vertex* curr = v;
347 Vertex* next = v->fNext;
348 double ax = static_cast<double>(curr->fPoint.fX) - prev->fPoint. fX;
349 double ay = static_cast<double>(curr->fPoint.fY) - prev->fPoint. fY;
350 double bx = static_cast<double>(next->fPoint.fX) - curr->fPoint. fX;
351 double by = static_cast<double>(next->fPoint.fY) - curr->fPoint. fY;
352 if (ax * by - ay * bx >= 0.0) {
353 data = emit_triangle(prev, curr, next, color, antiAlias, twe akAlpha, data);
354 v->fPrev->fNext = v->fNext;
355 v->fNext->fPrev = v->fPrev;
356 if (v->fPrev == first) {
357 v = v->fNext;
358 } else {
359 v = v->fPrev;
360 }
361 } else {
362 v = v->fNext;
363 SkASSERT(v != fTail);
364 }
365 }
366 return data;
367 }
368
369 #ifdef SK_DEBUG
370 void validate() {
371 int winding = fHead->fPoint < fTail->fPoint ? 1 : -1;
372 Vertex* top = winding < 0 ? fTail : fHead;
373 Vertex* bottom = winding < 0 ? fHead : fTail;
374 Edge e(top, bottom, winding);
375 for (Vertex* v = fHead->fNext; v != fTail; v = v->fNext) {
376 if (fSide == kRight_Side) {
377 SkASSERT(!e.isRightOf(v));
378 } else if (fSide == Poly::kLeft_Side) {
379 SkASSERT(!e.isLeftOf(v));
380 }
381 }
382 }
383 #endif
384 };
385 Poly* addVertex(Vertex* v, Side side, SkChunkAlloc& alloc) {
386 LOG("addVertex() to %d at %g (%g, %g), %s side\n", fID, v->fID, v->fPoin t.fX, v->fPoint.fY,
387 side == kLeft_Side ? "left" : side == kRight_Side ? "right" : "ne ither");
388 Poly* partner = fPartner;
389 Poly* poly = this;
390 if (partner) {
391 fPartner = partner->fPartner = NULL;
392 }
393 if (!fActive) {
394 fActive = ALLOC_NEW(MonotonePoly, (), alloc);
395 }
396 if (fActive->addVertex(v, side, alloc)) {
397 #ifdef SK_DEBUG
398 fActive->validate();
399 #endif
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 ? fActive->fHe ad->fNext : fActive->fTail->fPrev;
412 fActive = ALLOC_NEW(MonotonePoly, , alloc);
413 fActive->addVertex(prev, Poly::kNeither_Side, alloc);
414 fActive->addVertex(v, side, alloc);
415 }
416 }
417 fCount++;
418 return poly;
419 }
420 void end(Vertex* v, SkChunkAlloc& alloc) {
421 LOG("end() %d at %g, %g\n", fID, v->fPoint.fX, v->fPoint.fY);
422 if (fPartner) {
423 fPartner = fPartner->fPartner = NULL;
424 }
425 addVertex(v, fActive->fSide == kLeft_Side ? kRight_Side : kLeft_Side, al loc);
426 }
427 void* emit(bool antiAlias, bool tweakAlpha, GrColor color, void *data) {
428 if (fCount < 3) {
429 return data;
430 }
431 LOG("emit() %d, size %d\n", fID, fCount);
432 for (MonotonePoly* m = fHead; m != NULL; m = m->fNext) {
433 data = m->emit(antiAlias, tweakAlpha, color, data);
434 }
435 return data;
436 }
437 int fWinding;
438 MonotonePoly* fHead;
439 MonotonePoly* fTail;
440 MonotonePoly* fActive;
441 Poly* fNext;
442 Poly* fPartner;
443 int fCount;
444 #if LOGGING_ENABLED
445 int fID;
446 #endif
447 };
448
449 bool coincident(const SkPoint& a, const SkPoint& b) {
450 return a == b;
451 }
452
453 Poly* new_poly(Poly** head, Vertex* v, int winding, SkChunkAlloc& alloc) {
454 Poly* poly = ALLOC_NEW(Poly, (winding), alloc);
455 poly->addVertex(v, Poly::kNeither_Side, alloc);
456 poly->fNext = *head;
457 *head = poly;
458 return poly;
459 }
460
461 #ifdef SK_DEBUG
462 void validate_edges(Edge* head) {
463 for (Edge* e = head; e != NULL; e = e->fRight) {
464 SkASSERT(e->fTop != e->fBottom);
465 if (e->fLeft) {
466 SkASSERT(e->fLeft->fRight == e);
467 if (e->fTop->fPoint > e->fLeft->fTop->fPoint) {
468 SkASSERT(e->fLeft->isLeftOf(e->fTop));
469 }
470 if (e->fBottom->fPoint < e->fLeft->fBottom->fPoint) {
471 SkASSERT(e->fLeft->isLeftOf(e->fBottom));
472 }
473 } else {
474 SkASSERT(e == head);
475 }
476 if (e->fRight) {
477 SkASSERT(e->fRight->fLeft == e);
478 if (e->fTop->fPoint > e->fRight->fTop->fPoint) {
479 SkASSERT(e->fRight->isRightOf(e->fTop));
480 }
481 if (e->fBottom->fPoint < e->fRight->fBottom->fPoint) {
482 SkASSERT(e->fRight->isRightOf(e->fBottom));
483 }
484 }
485 }
486 }
487
488 void validate_connectivity(Vertex* v) {
489 for (Edge* e = v->fFirstEdgeAbove; e != NULL; e = e->fNextEdgeAbove) {
490 SkASSERT(e->fBottom == v);
491 if (e->fPrevEdgeAbove) {
492 SkASSERT(e->fPrevEdgeAbove->fNextEdgeAbove == e);
493 SkASSERT(e->fPrevEdgeAbove->isLeftOf(e->fTop));
494 } else {
495 SkASSERT(e == v->fFirstEdgeAbove);
496 }
497 if (e->fNextEdgeAbove) {
498 SkASSERT(e->fNextEdgeAbove->fPrevEdgeAbove == e);
499 SkASSERT(e->fNextEdgeAbove->isRightOf(e->fTop));
500 } else {
501 SkASSERT(e == v->fLastEdgeAbove);
502 }
503 }
504 for (Edge* e = v->fFirstEdgeBelow; e != NULL; e = e->fNextEdgeBelow) {
505 SkASSERT(e->fTop == v);
506 if (e->fPrevEdgeBelow) {
507 SkASSERT(e->fPrevEdgeBelow->fNextEdgeBelow == e);
508 SkASSERT(e->fPrevEdgeBelow->isLeftOf(e->fBottom));
509 } else {
510 SkASSERT(e == v->fFirstEdgeBelow);
511 }
512 if (e->fNextEdgeBelow) {
513 SkASSERT(e->fNextEdgeBelow->fPrevEdgeBelow == e);
514 SkASSERT(e->fNextEdgeBelow->isRightOf(e->fBottom));
515 } else {
516 SkASSERT(e == v->fLastEdgeBelow);
517 }
518 }
519 }
520 #endif
521
522 Vertex* append_point_to_contour(const SkPoint& p, Vertex* prev, Vertex** head, S kChunkAlloc& alloc) {
523 Vertex* v = ALLOC_NEW(Vertex, (p), alloc);
524 #if LOGGING_ENABLED
525 static float gID = 0.0f;
526 v->fID = gID++;
527 #endif
528 if (prev) {
529 prev->fNext = v;
530 v->fPrev = prev;
531 } else {
532 *head = v;
533 }
534 return v;
535 }
536
537 Vertex* generate_quadratic_points(const SkPoint& p0,
538 const SkPoint& p1,
539 const SkPoint& p2,
540 SkScalar tolSqd,
541 Vertex* prev,
542 Vertex** head,
543 SkChunkAlloc& alloc) {
544 if ((p1.distanceToLineSegmentBetweenSqd(p0, p2)) < tolSqd) {
545 return append_point_to_contour(p2, prev, head, alloc);
546 }
547
548 SkPoint q[] = {
549 { SkScalarAve(p0.fX, p1.fX), SkScalarAve(p0.fY, p1.fY) },
550 { SkScalarAve(p1.fX, p2.fX), SkScalarAve(p1.fY, p2.fY) },
551 };
552 SkPoint r = { SkScalarAve(q[0].fX, q[1].fX), SkScalarAve(q[0].fY, q[1].fY) } ;
553
554 prev = generate_quadratic_points(p0, q[0], r, tolSqd, prev, head, alloc);
555 prev = generate_quadratic_points(r, q[1], p2, tolSqd, prev, head, alloc);
556 return prev;
557 }
558
559 Vertex* generate_cubic_points(const SkPoint& p0,
560 const SkPoint& p1,
561 const SkPoint& p2,
562 const SkPoint& p3,
563 SkScalar tolSqd,
564 Vertex* prev,
565 Vertex** head,
566 SkChunkAlloc& alloc) {
567 if ((p1.distanceToLineSegmentBetweenSqd(p0, p3) < tolSqd &&
568 p2.distanceToLineSegmentBetweenSqd(p0, p3) < tolSqd)) {
569 return append_point_to_contour(p3, prev, head, alloc);
570 }
571 SkPoint q[] = {
572 { SkScalarAve(p0.fX, p1.fX), SkScalarAve(p0.fY, p1.fY) },
573 { SkScalarAve(p1.fX, p2.fX), SkScalarAve(p1.fY, p2.fY) },
574 { SkScalarAve(p2.fX, p3.fX), SkScalarAve(p2.fY, p3.fY) }
575 };
576 SkPoint r[] = {
577 { SkScalarAve(q[0].fX, q[1].fX), SkScalarAve(q[0].fY, q[1].fY) },
578 { SkScalarAve(q[1].fX, q[2].fX), SkScalarAve(q[1].fY, q[2].fY) }
579 };
580 SkPoint s = { SkScalarAve(r[0].fX, r[1].fX), SkScalarAve(r[0].fY, r[1].fY) } ;
581 prev = generate_cubic_points(p0, q[0], r[0], s, tolSqd, prev, head, alloc);
582 prev = generate_cubic_points(s, r[1], q[2], p3, tolSqd, prev, head, alloc);
583 return prev;
584 }
585
586 void path_to_contours(const SkPath& path, SkScalar srcSpaceTol, const SkRect& cl ipBounds, Vertex** contours, SkChunkAlloc& alloc) {
587
588 SkScalar srcSpaceTolSqd = srcSpaceTol * srcSpaceTol;
589
590 SkPoint pts[4];
591 bool done = false;
592 SkPath::Iter iter(path, false);
593 Vertex* prev = NULL;
594 Vertex* head = NULL;
595 if (path.isInverseFillType()) {
596 SkPoint quad[4];
597 clipBounds.toQuad(quad);
598 for (int i = 3; i >= 0; i--) {
599 prev = append_point_to_contour(quad[i], prev, &head, alloc);
600 }
601 head->fPrev = prev;
602 prev->fNext = head;
603 *contours++ = head;
604 head = prev = NULL;
605 }
606 while (!done) {
607 SkPath::Verb verb = iter.next(pts);
608 switch (verb) {
609 case SkPath::kConic_Verb: {
610 SkScalar weight = iter.conicWeight();
611 SkAutoConicToQuads converter;
612 const SkPoint* quadPts = converter.computeQuads(pts, weight, src SpaceTolSqd);
613 for (int i = 0; i < converter.countQuads(); ++i) {
614 prev = generate_quadratic_points(quadPts[0], quadPts[1], qua dPts[2], srcSpaceTolSqd, prev, &head, alloc);
615 quadPts += 2;
616 }
617 break;
618 }
619 case SkPath::kMove_Verb:
620 if (head) {
621 head->fPrev = prev;
622 prev->fNext = head;
623 *contours++ = head;
624 }
625 head = prev = NULL;
626 prev = append_point_to_contour(pts[0], prev, &head, alloc);
627 break;
628 case SkPath::kLine_Verb: {
629 prev = append_point_to_contour(pts[1], prev, &head, alloc);
630 break;
631 }
632 case SkPath::kQuad_Verb: {
633 prev = generate_quadratic_points(pts[0], pts[1], pts[2], srcSpac eTolSqd, prev, &head, alloc);
634 break;
635 }
636 case SkPath::kCubic_Verb: {
637 prev = generate_cubic_points(pts[0], pts[1], pts[2], pts[3],
638 srcSpaceTolSqd, prev, &head, alloc);
639 break;
640 }
641 case SkPath::kClose_Verb:
642 if (head) {
643 head->fPrev = prev;
644 prev->fNext = head;
645 *contours++ = head;
646 }
647 head = prev = NULL;
648 break;
649 case SkPath::kDone_Verb:
650 if (head) {
651 head->fPrev = prev;
652 prev->fNext = head;
653 *contours++ = head;
654 }
655 done = true;
656 break;
657 }
658 }
659 }
660
661 void close_all_path_contours(const SkPath& src, SkPath* dst) {
662 SkPath::Iter iter(src, true);
663 SkPoint pts[4];
664 SkPath::Verb verb;
665 while ((verb = iter.next(pts)) != SkPath::kDone_Verb) {
666 switch (verb) {
667 case SkPath::kMove_Verb:
668 dst->moveTo(pts[0]);
669 break;
670 case SkPath::kLine_Verb:
671 dst->lineTo(pts[1]);
672 break;
673 case SkPath::kQuad_Verb:
674 dst->quadTo(pts[1], pts[2]);
675 break;
676 case SkPath::kCubic_Verb:
677 dst->cubicTo(pts[1], pts[2], pts[3]);
678 break;
679 case SkPath::kClose_Verb:
680 dst->close();
681 break;
682 case SkPath::kConic_Verb:
683 case SkPath::kDone_Verb:
684 SkASSERT(false);
685 break;
686 }
687 }
688 }
689
690 inline bool apply_fill_type(SkPath::FillType fillType, int winding) {
691 switch (fillType) {
692 case SkPath::kWinding_FillType:
693 return winding != 0;
694 case SkPath::kEvenOdd_FillType:
695 return (winding & 1) != 0;
696 case SkPath::kInverseWinding_FillType:
697 return winding == 1;
698 case SkPath::kInverseEvenOdd_FillType:
699 return (winding & 1) == 1;
700 default:
701 SkASSERT(false);
702 return false;
703 }
704 }
705
706 Edge* new_edge(Vertex* prev, Vertex* next, SkChunkAlloc& alloc) {
707 int winding = prev->fPoint < next->fPoint ? 1 : -1;
708 Vertex* top = winding < 0 ? next : prev;
709 Vertex* bottom = winding < 0 ? prev : next;
710 return ALLOC_NEW(Edge, (top, bottom, winding), alloc);
711 }
712
713 void remove_edge(Edge* edge, Edge** head) {
714 LOG("removing edge %g -> %g\n", edge->fTop->fID, edge->fBottom->fID);
715 SkASSERT(edge->isActive(head));
716 remove<Edge, &Edge::fLeft, &Edge::fRight>(edge, head, NULL);
717 }
718
719 void insert_edge(Edge* edge, Edge* prev, Edge** head) {
720 LOG("inserting edge %g -> %g\n", edge->fTop->fID, edge->fBottom->fID);
721 SkASSERT(!edge->isActive(head));
722 Edge* next = prev ? prev->fRight : *head;
723 insert<Edge, &Edge::fLeft, &Edge::fRight>(edge, prev, next, head, NULL);
724 }
725
726 void find_enclosing_edges(Vertex* v, Edge* head, Edge** left, Edge** right) {
727 if (v->fFirstEdgeAbove) {
728 *left = v->fFirstEdgeAbove->fLeft;
729 *right = v->fLastEdgeAbove->fRight;
730 return;
731 }
732 Edge* prev = NULL;
733 Edge* next;
734 for (next = head; next != NULL; next = next->fRight) {
735 if (next->isRightOf(v)) {
736 break;
737 }
738 prev = next;
739 }
740 *left = prev;
741 *right = next;
742 return;
743 }
744
745 void find_enclosing_edges(Edge* edge, Edge* head, Edge** left, Edge** right) {
746 Edge* prev = NULL;
747 Edge* next;
748 for (next = head; next != NULL; next = next->fRight) {
749 if ((edge->fTop->fPoint > next->fTop->fPoint && next->isRightOf(edge->fT op)) ||
750 (next->fTop->fPoint > edge->fTop->fPoint && edge->isLeftOf(next->fTo p)) ||
751 (edge->fBottom->fPoint < next->fBottom->fPoint && next->isRightOf(ed ge->fBottom)) ||
752 (next->fBottom->fPoint < edge->fBottom->fPoint && edge->isLeftOf(nex t->fBottom))) {
753 break;
754 }
755 prev = next;
756 }
757 *left = prev;
758 *right = next;
759 return;
760 }
761
762 void fix_active_state(Edge* edge, Edge** activeEdges) {
763 if (edge->isActive(activeEdges)) {
764 if (edge->fBottom->fProcessed || !edge->fTop->fProcessed) {
765 remove_edge(edge, activeEdges);
766 }
767 } else if (edge->fTop->fProcessed && !edge->fBottom->fProcessed) {
768 Edge* left;
769 Edge* right;
770 find_enclosing_edges(edge, *activeEdges, &left, &right);
771 insert_edge(edge, left, activeEdges);
772 }
773 }
774
775 void insert_edge_above(Edge* edge, Vertex* v) {
776 if (edge->fTop->fPoint == edge->fBottom->fPoint || edge->fTop->fPoint > edge ->fBottom->fPoint) {
777 SkASSERT(false);
778 return;
779 }
780 LOG("insert edge (%g -> %g) above vertex %g (%g, %g)\n", edge->fTop->fID, ed ge->fBottom->fID, v->fID, v->fPoint.fX, v->fPoint.fY);
781 Edge* prev = NULL;
782 Edge* next;
783 for (next = v->fFirstEdgeAbove; next; next = next->fNextEdgeAbove) {
784 if (next->isRightOf(edge->fTop)) {
785 break;
786 }
787 prev = next;
788 }
789 insert<Edge, &Edge::fPrevEdgeAbove, &Edge::fNextEdgeAbove>(edge, prev, next, &v->fFirstEdgeAbove, &v->fLastEdgeAbove);
790 }
791
792 void insert_edge_below(Edge* edge, Vertex* v) {
793 if (edge->fTop->fPoint == edge->fBottom->fPoint || edge->fTop->fPoint > edge ->fBottom->fPoint) {
794 SkASSERT(false);
795 return;
796 }
797 LOG("insert edge (%g -> %g) below vertex %g (%g, %g)\n", edge->fTop->fID, ed ge->fBottom->fID, v->fID, v->fPoint.fX, v->fPoint.fY);
798 Edge* prev = NULL;
799 Edge* next;
800 for (next = v->fFirstEdgeBelow; next; next = next->fNextEdgeBelow) {
801 if (next->isRightOf(edge->fBottom)) {
802 break;
803 }
804 prev = next;
805 }
806 insert<Edge, &Edge::fPrevEdgeBelow, &Edge::fNextEdgeBelow>(edge, prev, next, &v->fFirstEdgeBelow, &v->fLastEdgeBelow);
807 }
808
809 void remove_edge_above(Edge* edge) {
810 LOG("removing edge (%g -> %g) above vertex %g\n", edge->fTop->fID, edge->fBo ttom->fID, edge->fBottom->fID);
811 remove<Edge, &Edge::fPrevEdgeAbove, &Edge::fNextEdgeAbove>(edge, &edge->fBot tom->fFirstEdgeAbove, &edge->fBottom->fLastEdgeAbove);
812 }
813
814 void remove_edge_below(Edge* edge) {
815 LOG("removing edge (%g -> %g) below vertex %g\n", edge->fTop->fID, edge->fBo ttom->fID, edge->fTop->fID);
816 remove<Edge, &Edge::fPrevEdgeBelow, &Edge::fNextEdgeBelow>(edge, &edge->fTop ->fFirstEdgeBelow, &edge->fTop->fLastEdgeBelow);
817 }
818
819 void erase_edge_if_zero_winding(Edge* edge, Edge** head) {
820 if (edge->fWinding != 0) {
821 return;
822 }
823 LOG("erasing edge (%g -> %g)\n", edge->fTop->fID, edge->fBottom->fID);
824 remove_edge_above(edge);
825 remove_edge_below(edge);
826 if (edge->isActive(head)) {
827 remove_edge(edge, head);
828 }
829 }
830
831 void merge_collinear_edges(Edge* edge, Edge** activeEdges);
832
833 void set_top(Edge* edge, Vertex* v, Edge** activeEdges) {
834 remove_edge_below(edge);
835 edge->fTop = v;
836 edge->recompute();
837 insert_edge_below(edge, v);
838 fix_active_state(edge, activeEdges);
839 merge_collinear_edges(edge, activeEdges);
840 }
841
842 void set_bottom(Edge* edge, Vertex* v, Edge** activeEdges) {
843 remove_edge_above(edge);
844 edge->fBottom = v;
845 edge->recompute();
846 insert_edge_above(edge, v);
847 fix_active_state(edge, activeEdges);
848 merge_collinear_edges(edge, activeEdges);
849 }
850
851 void merge_edges_above(Edge* edge, Edge* other, Edge** activeEdges) {
852 if (coincident(edge->fTop->fPoint, other->fTop->fPoint)) {
853 LOG("merging coincident above edges (%g, %g) -> (%g, %g)\n",
854 edge->fTop->fPoint.fX, edge->fTop->fPoint.fY,
855 edge->fBottom->fPoint.fX, edge->fBottom->fPoint.fY);
856 other->fWinding += edge->fWinding;
857 erase_edge_if_zero_winding(other, activeEdges);
858 edge->fWinding = 0;
859 erase_edge_if_zero_winding(edge, activeEdges);
860 } else if (edge->fTop->fPoint < other->fTop->fPoint) {
861 other->fWinding += edge->fWinding;
862 erase_edge_if_zero_winding(other, activeEdges);
863 set_bottom(edge, other->fTop, activeEdges);
864 } else {
865 edge->fWinding += other->fWinding;
866 erase_edge_if_zero_winding(edge, activeEdges);
867 set_bottom(other, edge->fTop, activeEdges);
868 }
869 }
870
871 void merge_edges_below(Edge* edge, Edge* other, Edge** activeEdges) {
872 if (coincident(edge->fBottom->fPoint, other->fBottom->fPoint)) {
873 LOG("merging coincident below edges (%g, %g) -> (%g, %g)\n",
874 edge->fTop->fPoint.fX, edge->fTop->fPoint.fY,
875 edge->fBottom->fPoint.fX, edge->fBottom->fPoint.fY);
876 other->fWinding += edge->fWinding;
877 erase_edge_if_zero_winding(other, activeEdges);
878 edge->fWinding = 0;
879 erase_edge_if_zero_winding(edge, activeEdges);
880 } else if (edge->fBottom->fPoint < other->fBottom->fPoint) {
881 edge->fWinding += other->fWinding;
882 erase_edge_if_zero_winding(edge, activeEdges);
883 set_top(other, edge->fBottom, activeEdges);
884 } else {
885 other->fWinding += edge->fWinding;
886 erase_edge_if_zero_winding(other, activeEdges);
887 set_top(edge, other->fBottom, activeEdges);
888 }
889 }
890
891 void merge_collinear_edges(Edge* edge, Edge** activeEdges) {
892 if (edge->fPrevEdgeAbove && !edge->fPrevEdgeAbove->isLeftOf(edge->fTop)) {
893 merge_edges_above(edge, edge->fPrevEdgeAbove, activeEdges);
894 } else if (edge->fNextEdgeAbove && !edge->isLeftOf(edge->fNextEdgeAbove->fTo p)) {
895 merge_edges_above(edge, edge->fNextEdgeAbove, activeEdges);
896 }
897 if (edge->fPrevEdgeBelow && !edge->fPrevEdgeBelow->isLeftOf(edge->fBottom)) {
898 merge_edges_below(edge, edge->fPrevEdgeBelow, activeEdges);
899 } else if (edge->fNextEdgeBelow && !edge->isLeftOf(edge->fNextEdgeBelow->fBo ttom)) {
900 merge_edges_below(edge, edge->fNextEdgeBelow, activeEdges);
901 }
902 }
903
904 void split_edge(Edge* edge, Vertex* v, Edge** activeEdges, SkChunkAlloc& alloc);
905
906 void cleanup_active_edges(Edge* edge, Edge** activeEdges, SkChunkAlloc& alloc) {
907 Vertex* top = edge->fTop;
908 Vertex* bottom = edge->fBottom;
909 if (edge->fLeft) {
910 Vertex* leftTop = edge->fLeft->fTop;
911 Vertex* leftBottom = edge->fLeft->fBottom;
912 if (top->fPoint > leftTop->fPoint && !edge->fLeft->isLeftOf(top)) {
913 split_edge(edge->fLeft, edge->fTop, activeEdges, alloc);
914 } else if (leftTop->fPoint > top->fPoint && !edge->isRightOf(leftTop)) {
915 split_edge(edge, leftTop, activeEdges, alloc);
916 } else if (bottom->fPoint < leftBottom->fPoint && !edge->fLeft->isLeftOf (bottom)) {
917 split_edge(edge->fLeft, bottom, activeEdges, alloc);
918 } else if (leftBottom->fPoint < bottom->fPoint && !edge->isRightOf(leftB ottom)) {
919 split_edge(edge, leftBottom, activeEdges, alloc);
920 }
921 }
922 if (edge->fRight) {
923 Vertex* rightTop = edge->fRight->fTop;
924 Vertex* rightBottom = edge->fRight->fBottom;
925 if (top->fPoint > rightTop->fPoint && !edge->fRight->isRightOf(top)) {
926 split_edge(edge->fRight, top, activeEdges, alloc);
927 } else if (rightTop->fPoint > top->fPoint && !edge->isLeftOf(rightTop)) {
928 split_edge(edge, rightTop, activeEdges, alloc);
929 } else if (bottom->fPoint < rightBottom->fPoint && !edge->fRight->isRigh tOf(bottom)) {
930 split_edge(edge->fRight, bottom, activeEdges, alloc);
931 } else if (rightBottom->fPoint < bottom->fPoint && !edge->isLeftOf(right Bottom)) {
932 split_edge(edge, rightBottom, activeEdges, alloc);
933 }
934 }
935 }
936
937 void split_edge(Edge* edge, Vertex* v, Edge** activeEdges, SkChunkAlloc& alloc) {
938 LOG("splitting edge (%g -> %g) at vertex %g (%g, %g)\n",
939 edge->fTop->fID, edge->fBottom->fID,
940 v->fID, v->fPoint.fX, v->fPoint.fY);
941 Edge* newEdge = ALLOC_NEW(Edge, (v, edge->fBottom, edge->fWinding), alloc);
942 insert_edge_below(newEdge, v);
943 insert_edge_above(newEdge, edge->fBottom);
944 set_bottom(edge, v, activeEdges);
945 cleanup_active_edges(edge, activeEdges, alloc);
946 fix_active_state(newEdge, activeEdges);
947 merge_collinear_edges(newEdge, activeEdges);
948 }
949
950 void merge_vertices(Vertex* src, Vertex* dst, Vertex** head, SkChunkAlloc& alloc ) {
951 LOG("found coincident verts at %g, %g; merging %g into %g\n", src->fPoint.fX , src->fPoint.fY, src->fID, dst->fID);
952 for (Edge* edge = src->fFirstEdgeAbove; edge;) {
953 Edge* next = edge->fNextEdgeAbove;
954 set_bottom(edge, dst, NULL);
955 edge = next;
956 }
957 for (Edge* edge = src->fFirstEdgeBelow; edge;) {
958 Edge* next = edge->fNextEdgeBelow;
959 set_top(edge, dst, NULL);
960 edge = next;
961 }
962 remove<Vertex, &Vertex::fPrev, &Vertex::fNext>(src, head, NULL);
963 }
964
965 Vertex* check_for_intersection(Edge* edge, Edge* other, Edge** activeEdges, SkCh unkAlloc& alloc) {
966 SkPoint p;
967 if (!edge || !other) {
968 return NULL;
969 }
970 if (edge->intersect(*other, &p)) {
971 Vertex* v;
972 LOG("found intersection, pt is %g, %g\n", p.fX, p.fY);
973 if (p == edge->fTop->fPoint || p < edge->fTop->fPoint) {
974 split_edge(other, edge->fTop, activeEdges, alloc);
975 v = edge->fTop;
976 } else if (p == edge->fBottom->fPoint || p > edge->fBottom->fPoint) {
977 split_edge(other, edge->fBottom, activeEdges, alloc);
978 v = edge->fBottom;
979 } else if (p == other->fTop->fPoint || p < other->fTop->fPoint) {
980 split_edge(edge, other->fTop, activeEdges, alloc);
981 v = other->fTop;
982 } else if (p == other->fBottom->fPoint || p > other->fBottom->fPoint) {
983 split_edge(edge, other->fBottom, activeEdges, alloc);
984 v = other->fBottom;
985 } else {
986 Vertex* nextV = edge->fTop;
987 while (p < nextV->fPoint) {
988 nextV = nextV->fPrev;
989 }
990 while (nextV->fPoint < p) {
991 nextV = nextV->fNext;
992 }
993 Vertex* prevV = nextV->fPrev;
994 if (coincident(prevV->fPoint, p)) {
995 v = prevV;
996 } else if (coincident(nextV->fPoint, p)) {
997 v = nextV;
998 } else {
999 v = ALLOC_NEW(Vertex, (p), alloc);
1000 LOG("inserting between %g (%g, %g) and %g (%g, %g)\n", prevV->fI D, prevV->fPoint.fX, prevV->fPoint.fY, nextV->fID, nextV->fPoint.fX, nextV->fPoi nt.fY);
1001 #if LOGGING_ENABLED
1002 v->fID = (nextV->fID + prevV->fID) * 0.5f;
1003 #endif
1004 v->fPrev = prevV;
1005 v->fNext = nextV;
1006 prevV->fNext = v;
1007 nextV->fPrev = v;
1008 }
1009 split_edge(edge, v, activeEdges, alloc);
1010 split_edge(other, v, activeEdges, alloc);
1011 }
1012 #ifdef SK_DEBUG
1013 validate_connectivity(v);
1014 #endif
1015 return v;
1016 }
1017 return NULL;
1018 }
1019
1020 Vertex* sorted_merge(Vertex* a, Vertex* b);
1021
1022 void front_back_split(Vertex* v, Vertex** pFront, Vertex** pBack)
1023 {
1024 Vertex* fast;
1025 Vertex* slow;
1026 if (!v || !v->fNext) {
1027 *pFront = v;
1028 *pBack = NULL;
1029 } else {
1030 slow = v;
1031 fast = v->fNext;
1032
1033 while (fast != NULL) {
1034 fast = fast->fNext;
1035 if (fast != NULL) {
1036 slow = slow->fNext;
1037 fast = fast->fNext;
1038 }
1039 }
1040
1041 *pFront = v;
1042 *pBack = slow->fNext;
1043 slow->fNext->fPrev = NULL;
1044 slow->fNext = NULL;
1045 }
1046 }
1047
1048 void merge_sort(Vertex** head)
1049 {
1050 if (!*head || !(*head)->fNext) {
1051 return;
1052 }
1053
1054 Vertex* a;
1055 Vertex* b;
1056 front_back_split(*head, &a, &b);
1057
1058 merge_sort(&a);
1059 merge_sort(&b);
1060
1061 *head = sorted_merge(a, b);
1062 }
1063
1064 Vertex* sorted_merge(Vertex* a, Vertex* b)
1065 {
1066 if (!a) {
1067 return b;
1068 } else if (!b) {
1069 return a;
1070 }
1071
1072 Vertex* result = NULL;
1073
1074 if (a->fPoint < b->fPoint) {
1075 result = a;
1076 result->fNext = sorted_merge(a->fNext, b);
1077 } else {
1078 result = b;
1079 result->fNext = sorted_merge(a, b->fNext);
1080 }
1081 result->fNext->fPrev = result;
1082 return result;
1083 }
1084
1085 void sanitize_contours(Vertex** contours, int contourCnt) {
1086 for (int i = 0; i < contourCnt; ++i) {
1087 SkASSERT(contours[i]);
1088 for (Vertex* v = contours[i];;) {
1089 if (coincident(v->fPrev->fPoint, v->fPoint)) {
1090 LOG("vertex %g,%g coincident; removing\n", v->fPoint.fX, v->fPoi nt.fY);
1091 if (v->fPrev == v) {
1092 contours[i] = NULL;
1093 break;
1094 }
1095 v->fPrev->fNext = v->fNext;
1096 v->fNext->fPrev = v->fPrev;
1097 if (contours[i] == v) {
1098 contours[i] = v->fNext;
1099 }
1100 v = v->fPrev;
1101 } else {
1102 v = v->fNext;
1103 if (v == contours[i]) break;
1104 }
1105 }
1106 }
1107 }
1108
1109 void merge_coincident_vertices(Vertex** headInY, SkChunkAlloc& alloc) {
1110 for (Vertex* v = (*headInY)->fNext; v != NULL; v = v->fNext) {
1111 if (v->fPoint < v->fPrev->fPoint) {
1112 v->fPoint = v->fPrev->fPoint;
1113 }
1114 if (coincident(v->fPrev->fPoint, v->fPoint)) {
1115 merge_vertices(v->fPrev, v, headInY, alloc);
1116 }
1117 }
1118 }
1119
1120 Vertex* build_edges(Vertex** contours, int contourCnt, SkChunkAlloc& alloc) {
1121 Vertex* headInY = NULL;
1122 Vertex* prevInY = NULL;
1123 for (int i = 0; i < contourCnt; ++i) {
1124 for (Vertex* v = contours[i]; v != NULL;) {
1125 Vertex* vNext = v->fNext;
1126 Edge* edge = new_edge(v->fPrev, v, alloc);
1127 if (edge->fWinding > 0) {
1128 insert_edge_below(edge, v->fPrev);
1129 insert_edge_above(edge, v);
1130 } else {
1131 insert_edge_below(edge, v);
1132 insert_edge_above(edge, v->fPrev);
1133 }
1134 merge_collinear_edges(edge, NULL);
1135 if (prevInY) {
1136 prevInY->fNext = v;
1137 v->fPrev = prevInY;
1138 } else {
1139 headInY = v;
1140 }
1141 prevInY = v;
1142 v = vNext;
1143 if (v == contours[i]) break;
1144 }
1145 }
1146 if (prevInY) {
1147 prevInY->fNext = headInY->fPrev = NULL;
1148 }
1149 return headInY;
1150 }
1151
1152 void simplify(Vertex* headInY, SkChunkAlloc& alloc) {
1153 LOG("simplifying complex polygons\n");
1154 Edge* activeEdges = NULL;
1155 for (Vertex* v = headInY; v != NULL; v = v->fNext) {
1156 if (!v->fFirstEdgeAbove && !v->fFirstEdgeBelow) {
1157 continue;
1158 }
1159 #if LOGGING_ENABLED
1160 LOG("\nvertex %g: (%g,%g)\n", v->fID, v->fPoint.fX, v->fPoint.fY);
1161 #endif
1162 #ifdef SK_DEBUG
1163 validate_connectivity(v);
1164 #endif
1165 Edge* leftEnclosingEdge = NULL;
1166 Edge* rightEnclosingEdge = NULL;
1167 bool restartChecks;
1168 do {
1169 restartChecks = false;
1170 find_enclosing_edges(v, activeEdges, &leftEnclosingEdge, &rightEnclo singEdge);
1171 if (v->fFirstEdgeBelow) {
1172 for (Edge* edge = v->fFirstEdgeBelow; edge != NULL; edge = edge- >fNextEdgeBelow) {
1173 if (check_for_intersection(edge, leftEnclosingEdge, &activeE dges, alloc)) {
1174 restartChecks = true;
1175 break;
1176 }
1177 if (check_for_intersection(edge, rightEnclosingEdge, &active Edges, alloc)) {
1178 restartChecks = true;
1179 break;
1180 }
1181 }
1182 } else {
1183 if (Vertex* pv = check_for_intersection(leftEnclosingEdge, right EnclosingEdge, &activeEdges, alloc)) {
1184 if (pv->fPoint < v->fPoint) {
1185 v = pv;
1186 }
1187 restartChecks = true;
1188 }
1189
1190 }
1191 } while (restartChecks);
1192 SkASSERT(!leftEnclosingEdge || leftEnclosingEdge->isLeftOf(v));
1193 SkASSERT(!rightEnclosingEdge || rightEnclosingEdge->isRightOf(v));
1194 #ifdef SK_DEBUG
1195 validate_edges(activeEdges);
1196 #endif
1197 for (Edge* e = v->fFirstEdgeAbove; e; e = e->fNextEdgeAbove) {
1198 remove_edge(e, &activeEdges);
1199 }
1200 Edge* leftEdge = leftEnclosingEdge;
1201 for (Edge* e = v->fFirstEdgeBelow; e; e = e->fNextEdgeBelow) {
1202 insert_edge(e, leftEdge, &activeEdges);
1203 leftEdge = e;
1204 }
1205 v->fProcessed = true;
1206 }
1207 }
1208
1209 Poly* tessellate(Vertex* headInY, SkChunkAlloc& alloc, SkTDArray<Vertex*>* bound aries) {
1210 LOG("tessellating simple polygons\n");
1211 Edge* activeEdges = NULL;
1212 Poly* polys = NULL;
1213 for (Vertex* v = headInY; v != NULL; v = v->fNext) {
1214 if (!v->fFirstEdgeAbove && !v->fFirstEdgeBelow) {
1215 continue;
1216 }
1217 #if LOGGING_ENABLED
1218 LOG("\nvertex %g: (%g,%g)\n", v->fID, v->fPoint.fX, v->fPoint.fY);
1219 #endif
1220 #ifdef SK_DEBUG
1221 validate_connectivity(v);
1222 #endif
1223 Edge* leftEnclosingEdge = NULL;
1224 Edge* rightEnclosingEdge = NULL;
1225 find_enclosing_edges(v, activeEdges, &leftEnclosingEdge, &rightEnclosing Edge);
1226 SkASSERT(!leftEnclosingEdge || leftEnclosingEdge->isLeftOf(v));
1227 SkASSERT(!rightEnclosingEdge || rightEnclosingEdge->isRightOf(v));
1228 #ifdef SK_DEBUG
1229 validate_edges(activeEdges);
1230 #endif
1231 Poly* leftPoly = NULL;
1232 Poly* rightPoly = NULL;
1233 Vertex* leftBoundary = NULL;
1234 Vertex* rightBoundary = NULL;
1235 if (v->fFirstEdgeAbove) {
1236 leftPoly = v->fFirstEdgeAbove->fLeftPoly;
1237 rightPoly = v->fLastEdgeAbove->fRightPoly;
1238 leftBoundary = v->fFirstEdgeAbove->fLeftBoundary;
1239 rightBoundary = v->fLastEdgeAbove->fRightBoundary;
1240 } else {
1241 leftPoly = leftEnclosingEdge ? leftEnclosingEdge->fRightPoly : NULL;
1242 rightPoly = rightEnclosingEdge ? rightEnclosingEdge->fLeftPoly : NUL L;
1243 }
1244 #if LOGGING_ENABLED
1245 LOG("edges above:\n");
1246 for (Edge* e = v->fFirstEdgeAbove; e; e = e->fNextEdgeAbove) {
1247 LOG("%g -> %g, lpoly %d, rpoly %d\n", e->fTop->fID, e->fBottom->fID, e->fLeftPoly ? e->fLeftPoly->fID : -1, e->fRightPoly ? e->fRightPoly->fID : -1) ;
1248 }
1249 LOG("edges below:\n");
1250 for (Edge* e = v->fFirstEdgeBelow; e; e = e->fNextEdgeBelow) {
1251 LOG("%g -> %g, lpoly %d, rpoly %d\n", e->fTop->fID, e->fBottom->fID, e->fLeftPoly ? e->fLeftPoly->fID : -1, e->fRightPoly ? e->fRightPoly->fID : -1) ;
1252 }
1253 #endif
1254 if (v->fFirstEdgeAbove) {
1255 if (leftPoly) {
1256 leftPoly = leftPoly->addVertex(v, Poly::kRight_Side, alloc);
1257 }
1258 if (rightPoly) {
1259 rightPoly = rightPoly->addVertex(v, Poly::kLeft_Side, alloc);
1260 }
1261 for (Edge* e = v->fFirstEdgeAbove; e != v->fLastEdgeAbove; e = e->fN extEdgeAbove) {
1262 Edge* leftEdge = e;
1263 Edge* rightEdge = e->fNextEdgeAbove;
1264 SkASSERT(rightEdge->isRightOf(leftEdge->fTop));
1265 remove_edge(leftEdge, &activeEdges);
1266 if (leftEdge->fRightPoly) {
1267 leftEdge->fRightPoly->end(v, alloc);
1268 } else if (boundaries) {
1269 SkASSERT(leftEdge->fRightBoundary && rightEdge->fLeftBoundar y);
1270 if (leftEdge->fRightBoundary && rightEdge->fLeftBoundary) {
1271 end_boundary(v->fPoint, leftEdge->fRightBoundary, rightE dge->fLeftBoundary, true, boundaries, alloc);
1272 }
1273 }
1274 if (rightEdge->fLeftPoly && rightEdge->fLeftPoly != leftEdge->fR ightPoly) {
1275 rightEdge->fLeftPoly->end(v, alloc);
1276 }
1277 }
1278 remove_edge(v->fLastEdgeAbove, &activeEdges);
1279 if (!v->fFirstEdgeBelow) {
1280 if (leftPoly && rightPoly && leftPoly != rightPoly) {
1281 SkASSERT(leftPoly->fPartner == NULL && rightPoly->fPartner = = NULL);
1282 rightPoly->fPartner = leftPoly;
1283 leftPoly->fPartner = rightPoly;
1284 }
1285 if (leftBoundary) {
1286 SkASSERT(rightBoundary);
1287 if (rightBoundary) {
1288 end_boundary(v->fPoint, rightBoundary, leftBoundary, fal se, boundaries, alloc);
1289 }
1290 }
1291 }
1292 }
1293 if (v->fFirstEdgeBelow) {
1294 if (!v->fFirstEdgeAbove) {
1295 if (leftPoly && leftPoly == rightPoly) {
1296 // Split the poly.
1297 if (leftPoly->fActive->fSide == Poly::kLeft_Side) {
1298 leftPoly = new_poly(&polys, leftEnclosingEdge->fTop, lef tPoly->fWinding, alloc);
1299 leftPoly->addVertex(v, Poly::kRight_Side, alloc);
1300 rightPoly->addVertex(v, Poly::kLeft_Side, alloc);
1301 leftEnclosingEdge->fRightPoly = leftPoly;
1302 } else {
1303 rightPoly = new_poly(&polys, rightEnclosingEdge->fTop, r ightPoly->fWinding, alloc);
1304 rightPoly->addVertex(v, Poly::kLeft_Side, alloc);
1305 leftPoly->addVertex(v, Poly::kRight_Side, alloc);
1306 rightEnclosingEdge->fLeftPoly = rightPoly;
1307 }
1308 } else {
1309 if (leftPoly) {
1310 leftPoly = leftPoly->addVertex(v, Poly::kRight_Side, all oc);
1311 }
1312 if (rightPoly) {
1313 rightPoly = rightPoly->addVertex(v, Poly::kLeft_Side, al loc);
1314 }
1315 }
1316 if (boundaries && (!leftPoly && !rightPoly)) {
1317 Vertex* c = new_boundary(v->fPoint, alloc);
1318 leftBoundary = rightBoundary = c;
1319 }
1320 } else if (boundaries) {
1321 if (!leftPoly) {
1322 SkASSERT(leftBoundary);
1323 if (leftBoundary) {
1324 leftBoundary = add_vertex_to_boundary_left(v->fPoint, le ftBoundary, alloc);
1325 }
1326 }
1327 if (!rightPoly) {
1328 SkASSERT(rightBoundary);
1329 if (rightBoundary) {
1330 rightBoundary = add_vertex_to_boundary_right(v->fPoint, rightBoundary, alloc);
1331 }
1332 }
1333 }
1334 Edge* leftEdge = v->fFirstEdgeBelow;
1335 leftEdge->fLeftPoly = leftPoly;
1336 leftEdge->fLeftBoundary = leftBoundary;
1337 insert_edge(leftEdge, leftEnclosingEdge, &activeEdges);
1338 for (Edge* rightEdge = leftEdge->fNextEdgeBelow; rightEdge; rightEdg e = rightEdge->fNextEdgeBelow) {
1339 insert_edge(rightEdge, leftEdge, &activeEdges);
1340 int winding = leftEdge->fLeftPoly ? leftEdge->fLeftPoly->fWindin g : 0;
1341 winding += leftEdge->fWinding;
1342 if (winding != 0) {
1343 Poly* poly = new_poly(&polys, v, winding, alloc);
1344 leftEdge->fRightPoly = rightEdge->fLeftPoly = poly;
1345 } else if (boundaries) {
1346 leftEdge->fRightBoundary = rightEdge->fLeftBoundary = new_bo undary(v->fPoint, alloc);
1347 }
1348 leftEdge = rightEdge;
1349 }
1350 v->fLastEdgeBelow->fRightPoly = rightPoly;
1351 v->fLastEdgeBelow->fRightBoundary = rightBoundary;
1352 }
1353 #ifdef SK_DEBUG
1354 validate_edges(activeEdges);
1355 #endif
1356 #if LOGGING_ENABLED
1357 LOG("\nactive edges:\n");
1358 for (Edge* e = activeEdges; e != NULL; e = e->fRight) {
1359 LOG("%g -> %g, lpoly %d, rpoly %d, lbound %p, rbound %p\n", e->fTop- >fID, e->fBottom->fID, e->fLeftPoly ? e->fLeftPoly->fID : -1, e->fRightPoly ? e- >fRightPoly->fID : -1, e->fLeftBoundary, e->fRightBoundary);
1360 }
1361 #endif
1362 }
1363 return polys;
1364 }
1365
1366 Poly* contours_to_polys(Vertex** contours, int contourCnt, SkChunkAlloc& alloc, SkTDArray<Vertex*>* boundaries) {
1367 #if LOGGING_ENABLED
1368 for (int i = 0; i < contourCnt; ++i) {
1369 Vertex* v = contours[i];
1370 SkASSERT(v);
1371 LOG("path.moveTo(%20.20g, %20.20g);\n", v->fPoint.fX, v->fPoint.fY);
1372 for (v = v->fNext; v != contours[i]; v = v->fNext) {
1373 LOG("path.lineTo(%20.20g, %20.20g);\n", v->fPoint.fX, v->fPoint.fY);
1374 }
1375 }
1376 #endif
1377 sanitize_contours(contours, contourCnt);
1378 Vertex* headInY = build_edges(contours, contourCnt, alloc);
1379 if (!headInY) {
1380 return NULL;
1381 }
1382
1383 // Sort vertices in Y (secondarily in X).
1384 merge_sort(&headInY);
1385 merge_coincident_vertices(&headInY, alloc);
1386 #if LOGGING_ENABLED
1387 for (Vertex* v = headInY; v != NULL; v = v->fNext) {
1388 static float gID = 0.0f;
1389 v->fID = gID++;
1390 }
1391 #endif
1392 simplify(headInY, alloc);
1393 return tessellate(headInY, alloc, boundaries);
1394 }
1395
1396 void* polys_to_triangles(Poly* polys, SkPath::FillType fillType, bool antiAlias, bool tweakAlpha, GrColor color, void* data) {
1397 void* d = data;
1398 for (Poly* poly = polys; poly; poly = poly->fNext) {
1399 if (apply_fill_type(fillType, poly->fWinding)) {
1400 d = poly->emit(antiAlias, tweakAlpha, color, d);
1401 }
1402 }
1403 return d;
1404 }
1405
1406 };
1407
1408 GrTessellatingPathRenderer::GrTessellatingPathRenderer() {
1409 }
1410
1411 GrPathRenderer::StencilSupport GrTessellatingPathRenderer::onGetStencilSupport(
1412 const GrDrawTarget*,
1413 const GrDrawState*,
1414 const SkPath&,
1415 const SkStrokeRec&) const {
1416 return GrPathRenderer::kNoSupport_StencilSupport;
1417 }
1418
1419 bool GrTessellatingPathRenderer::canDrawPath(const GrDrawTarget* target,
1420 const GrDrawState* drawState,
1421 const SkMatrix& viewMatrix,
1422 const SkPath& path,
1423 const SkStrokeRec& stroke,
1424 bool antiAlias) const {
1425 return stroke.isFillStyle() && !antiAlias;
1426 }
1427
1428 bool GrTessellatingPathRenderer::onDrawPath(GrDrawTarget* target,
1429 GrDrawState* drawState,
1430 GrColor color,
1431 const SkMatrix& viewM,
1432 const SkPath& path,
1433 const SkStrokeRec& stroke,
1434 bool antiAlias) {
1435 SkASSERT(!antiAlias);
1436 SkPath deviceSpacePath;
1437 path.transform(viewM, &deviceSpacePath);
1438 SkASSERT(target);
1439 const GrRenderTarget* rt = drawState->getRenderTarget();
1440 if (NULL == rt) {
1441 return false;
1442 }
1443
1444 SkScalar tol = SK_Scalar1;
1445
1446 if (antiAlias) {
1447 SkPath closedPath;
1448 close_all_path_contours(deviceSpacePath, &closedPath);
1449 SkStroke stroker;
1450 stroker.setJoin(SkPaint::kMiter_Join);
1451 stroker.setWidth(1.0);
1452 SkPath strokedPath;
1453 stroker.strokePath(closedPath, &strokedPath);
1454 deviceSpacePath = strokedPath;
1455 }
1456
1457 int contourCnt;
1458 int maxPts = GrPathUtils::worstCasePointCount(deviceSpacePath, &contourCnt, SK_Scalar1);
1459 SkPath::FillType fillType = deviceSpacePath.getFillType();
1460 if (SkPath::IsInverseFillType(fillType)) {
1461 contourCnt++;
1462 }
1463
1464 if (maxPts <= 0) {
1465 return false;
1466 }
1467 LOG("got %d pts, %d contours\n", maxPts, contourCnt);
1468
1469 SkAutoTDeleteArray<Vertex*> contours(SkNEW_ARRAY(Vertex *, contourCnt));
1470
1471 SkChunkAlloc alloc(maxPts * (3 * sizeof(Vertex) + sizeof(Edge)));
1472 SkIRect clipBounds;
1473 target->getClip()->getConservativeBounds(rt, &clipBounds);
1474 path_to_contours(deviceSpacePath, tol, SkRect::Make(clipBounds), contours.ge t(), alloc);
1475 Poly* polys;
1476 bool tweakAlpha = drawState->canTweakAlphaForCoverage();
1477 uint32_t flags = GrDefaultGeoProcFactory::kPosition_GPType;
1478 if (antiAlias) {
1479 SkTDArray<Vertex*> boundaries;
1480 contours_to_polys(contours.get(), contourCnt, alloc, &boundaries);
1481 LOG("got %d boundaries\n", boundaries.count());
1482 polys = contours_to_polys(boundaries.begin(), boundaries.count(), alloc, NULL);
1483 flags |= GrDefaultGeoProcFactory::kColor_GPType;
1484 if (!tweakAlpha) {
1485 flags |= GrDefaultGeoProcFactory::kCoverage_GPType;
1486 }
1487 } else {
1488 polys = contours_to_polys(contours.get(), contourCnt, alloc, NULL);
1489 }
1490 SkAutoTUnref<const GrGeometryProcessor> gp(GrDefaultGeoProcFactory::Create(f lags, color, SkMatrix::I(), SkMatrix::I()));
1491 int count = 0;
1492 for (Poly* poly = polys; poly; poly = poly->fNext) {
1493 if (apply_fill_type(fillType, poly->fWinding) && poly->fCount >= 3) {
1494 count += (poly->fCount - 2) * (gWireframe ? 6 : 3);
1495 }
1496 }
1497
1498 int stride = gp->getVertexStride();
1499 GrDrawTarget::AutoReleaseGeometry arg;
1500 if (!arg.set(target, count, stride, 0)) {
1501 return false;
1502 }
1503 LOG("emitting %d verts\n", count);
1504 void* end = polys_to_triangles(polys, fillType, antiAlias, tweakAlpha, color , arg.vertices());
1505 int actualCount = (static_cast<char*>(end) - static_cast<char*>(arg.vertices ())) / stride;
1506 LOG("actual count: %d\n", actualCount);
1507 SkASSERT(actualCount <= count);
1508
1509 GrPrimitiveType primitiveType = gWireframe ? kLines_GrPrimitiveType : kTrian gles_GrPrimitiveType;
1510 target->drawNonIndexed(drawState, gp, primitiveType, 0, actualCount);
1511
1512 return true;
1513 }
OLDNEW
« src/gpu/GrTessellatingPathRenderer.h ('K') | « src/gpu/GrTessellatingPathRenderer.h ('k') | tests/ConcavePathTests.cpp » ('j') | tests/ConcavePathTests.cpp » ('J')

Powered by Google App Engine
This is Rietveld 408576698