OLD | NEW |
1 /* | 1 /* |
2 * Copyright 2015 Google Inc. | 2 * Copyright 2015 Google Inc. |
3 * | 3 * |
4 * Use of this source code is governed by a BSD-style license that can be | 4 * Use of this source code is governed by a BSD-style license that can be |
5 * found in the LICENSE file. | 5 * found in the LICENSE file. |
6 */ | 6 */ |
7 | 7 |
8 #include "GrTessellatingPathRenderer.h" | 8 #include "GrTessellatingPathRenderer.h" |
9 | 9 |
10 #include "GrBatchFlushState.h" | 10 #include "GrBatchFlushState.h" |
(...skipping 107 matching lines...) Expand 10 before | Expand all | Expand 10 after Loading... |
118 if (t->*Prev) { | 118 if (t->*Prev) { |
119 t->*Prev->*Next = t->*Next; | 119 t->*Prev->*Next = t->*Next; |
120 } else if (head) { | 120 } else if (head) { |
121 *head = t->*Next; | 121 *head = t->*Next; |
122 } | 122 } |
123 if (t->*Next) { | 123 if (t->*Next) { |
124 t->*Next->*Prev = t->*Prev; | 124 t->*Next->*Prev = t->*Prev; |
125 } else if (tail) { | 125 } else if (tail) { |
126 *tail = t->*Prev; | 126 *tail = t->*Prev; |
127 } | 127 } |
128 t->*Prev = t->*Next = NULL; | 128 t->*Prev = t->*Next = nullptr; |
129 } | 129 } |
130 | 130 |
131 /** | 131 /** |
132 * Vertices are used in three ways: first, the path contours are converted into
a | 132 * Vertices are used in three ways: first, the path contours are converted into
a |
133 * circularly-linked list of Vertices for each contour. After edge construction,
the same Vertices | 133 * circularly-linked list of Vertices for each contour. After edge construction,
the same Vertices |
134 * are re-ordered by the merge sort according to the sweep_lt comparator (usuall
y, increasing | 134 * are re-ordered by the merge sort according to the sweep_lt comparator (usuall
y, increasing |
135 * in Y) using the same fPrev/fNext pointers that were used for the contours, to
avoid | 135 * in Y) using the same fPrev/fNext pointers that were used for the contours, to
avoid |
136 * reallocation. Finally, MonotonePolys are built containing a circularly-linked
list of | 136 * reallocation. Finally, MonotonePolys are built containing a circularly-linked
list of |
137 * Vertices. (Currently, those Vertices are newly-allocated for the MonotonePoly
s, since | 137 * Vertices. (Currently, those Vertices are newly-allocated for the MonotonePoly
s, since |
138 * an individual Vertex from the path mesh may belong to multiple | 138 * an individual Vertex from the path mesh may belong to multiple |
139 * MonotonePolys, so the original Vertices cannot be re-used. | 139 * MonotonePolys, so the original Vertices cannot be re-used. |
140 */ | 140 */ |
141 | 141 |
142 struct Vertex { | 142 struct Vertex { |
143 Vertex(const SkPoint& point) | 143 Vertex(const SkPoint& point) |
144 : fPoint(point), fPrev(NULL), fNext(NULL) | 144 : fPoint(point), fPrev(nullptr), fNext(nullptr) |
145 , fFirstEdgeAbove(NULL), fLastEdgeAbove(NULL) | 145 , fFirstEdgeAbove(nullptr), fLastEdgeAbove(nullptr) |
146 , fFirstEdgeBelow(NULL), fLastEdgeBelow(NULL) | 146 , fFirstEdgeBelow(nullptr), fLastEdgeBelow(nullptr) |
147 , fProcessed(false) | 147 , fProcessed(false) |
148 #if LOGGING_ENABLED | 148 #if LOGGING_ENABLED |
149 , fID (-1.0f) | 149 , fID (-1.0f) |
150 #endif | 150 #endif |
151 {} | 151 {} |
152 SkPoint fPoint; // Vertex position | 152 SkPoint fPoint; // Vertex position |
153 Vertex* fPrev; // Linked list of contours, then Y-sorted vertices
. | 153 Vertex* fPrev; // Linked list of contours, then Y-sorted vertices
. |
154 Vertex* fNext; // " | 154 Vertex* fNext; // " |
155 Edge* fFirstEdgeAbove; // Linked list of edges above this vertex. | 155 Edge* fFirstEdgeAbove; // Linked list of edges above this vertex. |
156 Edge* fLastEdgeAbove; // " | 156 Edge* fLastEdgeAbove; // " |
(...skipping 45 matching lines...) Expand 10 before | Expand all | Expand 10 after Loading... |
202 data = emit_vertex(v0, data); | 202 data = emit_vertex(v0, data); |
203 #else | 203 #else |
204 data = emit_vertex(v0, data); | 204 data = emit_vertex(v0, data); |
205 data = emit_vertex(v1, data); | 205 data = emit_vertex(v1, data); |
206 data = emit_vertex(v2, data); | 206 data = emit_vertex(v2, data); |
207 #endif | 207 #endif |
208 return data; | 208 return data; |
209 } | 209 } |
210 | 210 |
211 struct EdgeList { | 211 struct EdgeList { |
212 EdgeList() : fHead(NULL), fTail(NULL) {} | 212 EdgeList() : fHead(nullptr), fTail(nullptr) {} |
213 Edge* fHead; | 213 Edge* fHead; |
214 Edge* fTail; | 214 Edge* fTail; |
215 }; | 215 }; |
216 | 216 |
217 /** | 217 /** |
218 * An Edge joins a top Vertex to a bottom Vertex. Edge ordering for the list of
"edges above" and | 218 * An Edge joins a top Vertex to a bottom Vertex. Edge ordering for the list of
"edges above" and |
219 * "edge below" a vertex as well as for the active edge list is handled by isLef
tOf()/isRightOf(). | 219 * "edge below" a vertex as well as for the active edge list is handled by isLef
tOf()/isRightOf(). |
220 * Note that an Edge will give occasionally dist() != 0 for its own endpoints (b
ecause floating | 220 * Note that an Edge will give occasionally dist() != 0 for its own endpoints (b
ecause floating |
221 * point). For speed, that case is only tested by the callers which require it (
e.g., | 221 * point). For speed, that case is only tested by the callers which require it (
e.g., |
222 * cleanup_active_edges()). Edges also handle checking for intersection with oth
er edges. | 222 * cleanup_active_edges()). Edges also handle checking for intersection with oth
er edges. |
223 * Currently, this converts the edges to the parametric form, in order to avoid
doing a division | 223 * Currently, this converts the edges to the parametric form, in order to avoid
doing a division |
224 * until an intersection has been confirmed. This is slightly slower in the "fou
nd" case, but | 224 * until an intersection has been confirmed. This is slightly slower in the "fou
nd" case, but |
225 * a lot faster in the "not found" case. | 225 * a lot faster in the "not found" case. |
226 * | 226 * |
227 * The coefficients of the line equation stored in double precision to avoid cat
astrphic | 227 * The coefficients of the line equation stored in double precision to avoid cat
astrphic |
228 * cancellation in the isLeftOf() and isRightOf() checks. Using doubles ensures
that the result is | 228 * cancellation in the isLeftOf() and isRightOf() checks. Using doubles ensures
that the result is |
229 * correct in float, since it's a polynomial of degree 2. The intersect() functi
on, being | 229 * correct in float, since it's a polynomial of degree 2. The intersect() functi
on, being |
230 * degree 5, is still subject to catastrophic cancellation. We deal with that by
assuming its | 230 * degree 5, is still subject to catastrophic cancellation. We deal with that by
assuming its |
231 * output may be incorrect, and adjusting the mesh topology to match (see commen
t at the top of | 231 * output may be incorrect, and adjusting the mesh topology to match (see commen
t at the top of |
232 * this file). | 232 * this file). |
233 */ | 233 */ |
234 | 234 |
235 struct Edge { | 235 struct Edge { |
236 Edge(Vertex* top, Vertex* bottom, int winding) | 236 Edge(Vertex* top, Vertex* bottom, int winding) |
237 : fWinding(winding) | 237 : fWinding(winding) |
238 , fTop(top) | 238 , fTop(top) |
239 , fBottom(bottom) | 239 , fBottom(bottom) |
240 , fLeft(NULL) | 240 , fLeft(nullptr) |
241 , fRight(NULL) | 241 , fRight(nullptr) |
242 , fPrevEdgeAbove(NULL) | 242 , fPrevEdgeAbove(nullptr) |
243 , fNextEdgeAbove(NULL) | 243 , fNextEdgeAbove(nullptr) |
244 , fPrevEdgeBelow(NULL) | 244 , fPrevEdgeBelow(nullptr) |
245 , fNextEdgeBelow(NULL) | 245 , fNextEdgeBelow(nullptr) |
246 , fLeftPoly(NULL) | 246 , fLeftPoly(nullptr) |
247 , fRightPoly(NULL) { | 247 , fRightPoly(nullptr) { |
248 recompute(); | 248 recompute(); |
249 } | 249 } |
250 int fWinding; // 1 == edge goes downward; -1 = edge goes upwar
d. | 250 int fWinding; // 1 == edge goes downward; -1 = edge goes upwar
d. |
251 Vertex* fTop; // The top vertex in vertex-sort-order (sweep_lt
). | 251 Vertex* fTop; // The top vertex in vertex-sort-order (sweep_lt
). |
252 Vertex* fBottom; // The bottom vertex in vertex-sort-order. | 252 Vertex* fBottom; // The bottom vertex in vertex-sort-order. |
253 Edge* fLeft; // The linked list of edges in the active edge l
ist. | 253 Edge* fLeft; // The linked list of edges in the active edge l
ist. |
254 Edge* fRight; // " | 254 Edge* fRight; // " |
255 Edge* fPrevEdgeAbove; // The linked list of edges in the bottom Vertex
's "edges above". | 255 Edge* fPrevEdgeAbove; // The linked list of edges in the bottom Vertex
's "edges above". |
256 Edge* fNextEdgeAbove; // " | 256 Edge* fNextEdgeAbove; // " |
257 Edge* fPrevEdgeBelow; // The linked list of edges in the top Vertex's
"edges below". | 257 Edge* fPrevEdgeBelow; // The linked list of edges in the top Vertex's
"edges below". |
(...skipping 48 matching lines...) Expand 10 before | Expand all | Expand 10 after Loading... |
306 bool isActive(EdgeList* activeEdges) const { | 306 bool isActive(EdgeList* activeEdges) const { |
307 return activeEdges && (fLeft || fRight || activeEdges->fHead == this); | 307 return activeEdges && (fLeft || fRight || activeEdges->fHead == this); |
308 } | 308 } |
309 }; | 309 }; |
310 | 310 |
311 /*******************************************************************************
********/ | 311 /*******************************************************************************
********/ |
312 | 312 |
313 struct Poly { | 313 struct Poly { |
314 Poly(int winding) | 314 Poly(int winding) |
315 : fWinding(winding) | 315 : fWinding(winding) |
316 , fHead(NULL) | 316 , fHead(nullptr) |
317 , fTail(NULL) | 317 , fTail(nullptr) |
318 , fActive(NULL) | 318 , fActive(nullptr) |
319 , fNext(NULL) | 319 , fNext(nullptr) |
320 , fPartner(NULL) | 320 , fPartner(nullptr) |
321 , fCount(0) | 321 , fCount(0) |
322 { | 322 { |
323 #if LOGGING_ENABLED | 323 #if LOGGING_ENABLED |
324 static int gID = 0; | 324 static int gID = 0; |
325 fID = gID++; | 325 fID = gID++; |
326 LOG("*** created Poly %d\n", fID); | 326 LOG("*** created Poly %d\n", fID); |
327 #endif | 327 #endif |
328 } | 328 } |
329 typedef enum { kNeither_Side, kLeft_Side, kRight_Side } Side; | 329 typedef enum { kNeither_Side, kLeft_Side, kRight_Side } Side; |
330 struct MonotonePoly { | 330 struct MonotonePoly { |
331 MonotonePoly() | 331 MonotonePoly() |
332 : fSide(kNeither_Side) | 332 : fSide(kNeither_Side) |
333 , fHead(NULL) | 333 , fHead(nullptr) |
334 , fTail(NULL) | 334 , fTail(nullptr) |
335 , fPrev(NULL) | 335 , fPrev(nullptr) |
336 , fNext(NULL) {} | 336 , fNext(nullptr) {} |
337 Side fSide; | 337 Side fSide; |
338 Vertex* fHead; | 338 Vertex* fHead; |
339 Vertex* fTail; | 339 Vertex* fTail; |
340 MonotonePoly* fPrev; | 340 MonotonePoly* fPrev; |
341 MonotonePoly* fNext; | 341 MonotonePoly* fNext; |
342 bool addVertex(Vertex* v, Side side, SkChunkAlloc& alloc) { | 342 bool addVertex(Vertex* v, Side side, SkChunkAlloc& alloc) { |
343 Vertex* newV = ALLOC_NEW(Vertex, (v->fPoint), alloc); | 343 Vertex* newV = ALLOC_NEW(Vertex, (v->fPoint), alloc); |
344 bool done = false; | 344 bool done = false; |
345 if (fSide == kNeither_Side) { | 345 if (fSide == kNeither_Side) { |
346 fSide = side; | 346 fSide = side; |
347 } else { | 347 } else { |
348 done = side != fSide; | 348 done = side != fSide; |
349 } | 349 } |
350 if (fHead == NULL) { | 350 if (fHead == nullptr) { |
351 fHead = fTail = newV; | 351 fHead = fTail = newV; |
352 } else if (fSide == kRight_Side) { | 352 } else if (fSide == kRight_Side) { |
353 newV->fPrev = fTail; | 353 newV->fPrev = fTail; |
354 fTail->fNext = newV; | 354 fTail->fNext = newV; |
355 fTail = newV; | 355 fTail = newV; |
356 } else { | 356 } else { |
357 newV->fNext = fHead; | 357 newV->fNext = fHead; |
358 fHead->fPrev = newV; | 358 fHead->fPrev = newV; |
359 fHead = newV; | 359 fHead = newV; |
360 } | 360 } |
(...skipping 27 matching lines...) Expand all Loading... |
388 } | 388 } |
389 return data; | 389 return data; |
390 } | 390 } |
391 }; | 391 }; |
392 Poly* addVertex(Vertex* v, Side side, SkChunkAlloc& alloc) { | 392 Poly* addVertex(Vertex* v, Side side, SkChunkAlloc& alloc) { |
393 LOG("addVertex() to %d at %g (%g, %g), %s side\n", fID, v->fID, v->fPoin
t.fX, v->fPoint.fY, | 393 LOG("addVertex() to %d at %g (%g, %g), %s side\n", fID, v->fID, v->fPoin
t.fX, v->fPoint.fY, |
394 side == kLeft_Side ? "left" : side == kRight_Side ? "right" : "ne
ither"); | 394 side == kLeft_Side ? "left" : side == kRight_Side ? "right" : "ne
ither"); |
395 Poly* partner = fPartner; | 395 Poly* partner = fPartner; |
396 Poly* poly = this; | 396 Poly* poly = this; |
397 if (partner) { | 397 if (partner) { |
398 fPartner = partner->fPartner = NULL; | 398 fPartner = partner->fPartner = nullptr; |
399 } | 399 } |
400 if (!fActive) { | 400 if (!fActive) { |
401 fActive = ALLOC_NEW(MonotonePoly, (), alloc); | 401 fActive = ALLOC_NEW(MonotonePoly, (), alloc); |
402 } | 402 } |
403 if (fActive->addVertex(v, side, alloc)) { | 403 if (fActive->addVertex(v, side, alloc)) { |
404 if (fTail) { | 404 if (fTail) { |
405 fActive->fPrev = fTail; | 405 fActive->fPrev = fTail; |
406 fTail->fNext = fActive; | 406 fTail->fNext = fActive; |
407 fTail = fActive; | 407 fTail = fActive; |
408 } else { | 408 } else { |
409 fHead = fTail = fActive; | 409 fHead = fTail = fActive; |
410 } | 410 } |
411 if (partner) { | 411 if (partner) { |
412 partner->addVertex(v, side, alloc); | 412 partner->addVertex(v, side, alloc); |
413 poly = partner; | 413 poly = partner; |
414 } else { | 414 } else { |
415 Vertex* prev = fActive->fSide == Poly::kLeft_Side ? | 415 Vertex* prev = fActive->fSide == Poly::kLeft_Side ? |
416 fActive->fHead->fNext : fActive->fTail->fPrev; | 416 fActive->fHead->fNext : fActive->fTail->fPrev; |
417 fActive = ALLOC_NEW(MonotonePoly, , alloc); | 417 fActive = ALLOC_NEW(MonotonePoly, , alloc); |
418 fActive->addVertex(prev, Poly::kNeither_Side, alloc); | 418 fActive->addVertex(prev, Poly::kNeither_Side, alloc); |
419 fActive->addVertex(v, side, alloc); | 419 fActive->addVertex(v, side, alloc); |
420 } | 420 } |
421 } | 421 } |
422 fCount++; | 422 fCount++; |
423 return poly; | 423 return poly; |
424 } | 424 } |
425 void end(Vertex* v, SkChunkAlloc& alloc) { | 425 void end(Vertex* v, SkChunkAlloc& alloc) { |
426 LOG("end() %d at %g, %g\n", fID, v->fPoint.fX, v->fPoint.fY); | 426 LOG("end() %d at %g, %g\n", fID, v->fPoint.fX, v->fPoint.fY); |
427 if (fPartner) { | 427 if (fPartner) { |
428 fPartner = fPartner->fPartner = NULL; | 428 fPartner = fPartner->fPartner = nullptr; |
429 } | 429 } |
430 addVertex(v, fActive->fSide == kLeft_Side ? kRight_Side : kLeft_Side, al
loc); | 430 addVertex(v, fActive->fSide == kLeft_Side ? kRight_Side : kLeft_Side, al
loc); |
431 } | 431 } |
432 SkPoint* emit(SkPoint *data) { | 432 SkPoint* emit(SkPoint *data) { |
433 if (fCount < 3) { | 433 if (fCount < 3) { |
434 return data; | 434 return data; |
435 } | 435 } |
436 LOG("emit() %d, size %d\n", fID, fCount); | 436 LOG("emit() %d, size %d\n", fID, fCount); |
437 for (MonotonePoly* m = fHead; m != NULL; m = m->fNext) { | 437 for (MonotonePoly* m = fHead; m != nullptr; m = m->fNext) { |
438 data = m->emit(data); | 438 data = m->emit(data); |
439 } | 439 } |
440 return data; | 440 return data; |
441 } | 441 } |
442 int fWinding; | 442 int fWinding; |
443 MonotonePoly* fHead; | 443 MonotonePoly* fHead; |
444 MonotonePoly* fTail; | 444 MonotonePoly* fTail; |
445 MonotonePoly* fActive; | 445 MonotonePoly* fActive; |
446 Poly* fNext; | 446 Poly* fNext; |
447 Poly* fPartner; | 447 Poly* fPartner; |
(...skipping 93 matching lines...) Expand 10 before | Expand all | Expand 10 after Loading... |
541 | 541 |
542 void path_to_contours(const SkPath& path, SkScalar tolerance, const SkRect& clip
Bounds, | 542 void path_to_contours(const SkPath& path, SkScalar tolerance, const SkRect& clip
Bounds, |
543 Vertex** contours, SkChunkAlloc& alloc, bool *isLinear) { | 543 Vertex** contours, SkChunkAlloc& alloc, bool *isLinear) { |
544 | 544 |
545 SkScalar toleranceSqd = tolerance * tolerance; | 545 SkScalar toleranceSqd = tolerance * tolerance; |
546 | 546 |
547 SkPoint pts[4]; | 547 SkPoint pts[4]; |
548 bool done = false; | 548 bool done = false; |
549 *isLinear = true; | 549 *isLinear = true; |
550 SkPath::Iter iter(path, false); | 550 SkPath::Iter iter(path, false); |
551 Vertex* prev = NULL; | 551 Vertex* prev = nullptr; |
552 Vertex* head = NULL; | 552 Vertex* head = nullptr; |
553 if (path.isInverseFillType()) { | 553 if (path.isInverseFillType()) { |
554 SkPoint quad[4]; | 554 SkPoint quad[4]; |
555 clipBounds.toQuad(quad); | 555 clipBounds.toQuad(quad); |
556 for (int i = 3; i >= 0; i--) { | 556 for (int i = 3; i >= 0; i--) { |
557 prev = append_point_to_contour(quad[i], prev, &head, alloc); | 557 prev = append_point_to_contour(quad[i], prev, &head, alloc); |
558 } | 558 } |
559 head->fPrev = prev; | 559 head->fPrev = prev; |
560 prev->fNext = head; | 560 prev->fNext = head; |
561 *contours++ = head; | 561 *contours++ = head; |
562 head = prev = NULL; | 562 head = prev = nullptr; |
563 } | 563 } |
564 SkAutoConicToQuads converter; | 564 SkAutoConicToQuads converter; |
565 while (!done) { | 565 while (!done) { |
566 SkPath::Verb verb = iter.next(pts); | 566 SkPath::Verb verb = iter.next(pts); |
567 switch (verb) { | 567 switch (verb) { |
568 case SkPath::kConic_Verb: { | 568 case SkPath::kConic_Verb: { |
569 SkScalar weight = iter.conicWeight(); | 569 SkScalar weight = iter.conicWeight(); |
570 const SkPoint* quadPts = converter.computeQuads(pts, weight, tol
eranceSqd); | 570 const SkPoint* quadPts = converter.computeQuads(pts, weight, tol
eranceSqd); |
571 for (int i = 0; i < converter.countQuads(); ++i) { | 571 for (int i = 0; i < converter.countQuads(); ++i) { |
572 int pointsLeft = GrPathUtils::quadraticPointCount(quadPts, t
olerance); | 572 int pointsLeft = GrPathUtils::quadraticPointCount(quadPts, t
olerance); |
573 prev = generate_quadratic_points(quadPts[0], quadPts[1], qua
dPts[2], | 573 prev = generate_quadratic_points(quadPts[0], quadPts[1], qua
dPts[2], |
574 toleranceSqd, prev, &head,
pointsLeft, alloc); | 574 toleranceSqd, prev, &head,
pointsLeft, alloc); |
575 quadPts += 2; | 575 quadPts += 2; |
576 } | 576 } |
577 *isLinear = false; | 577 *isLinear = false; |
578 break; | 578 break; |
579 } | 579 } |
580 case SkPath::kMove_Verb: | 580 case SkPath::kMove_Verb: |
581 if (head) { | 581 if (head) { |
582 head->fPrev = prev; | 582 head->fPrev = prev; |
583 prev->fNext = head; | 583 prev->fNext = head; |
584 *contours++ = head; | 584 *contours++ = head; |
585 } | 585 } |
586 head = prev = NULL; | 586 head = prev = nullptr; |
587 prev = append_point_to_contour(pts[0], prev, &head, alloc); | 587 prev = append_point_to_contour(pts[0], prev, &head, alloc); |
588 break; | 588 break; |
589 case SkPath::kLine_Verb: { | 589 case SkPath::kLine_Verb: { |
590 prev = append_point_to_contour(pts[1], prev, &head, alloc); | 590 prev = append_point_to_contour(pts[1], prev, &head, alloc); |
591 break; | 591 break; |
592 } | 592 } |
593 case SkPath::kQuad_Verb: { | 593 case SkPath::kQuad_Verb: { |
594 int pointsLeft = GrPathUtils::quadraticPointCount(pts, tolerance
); | 594 int pointsLeft = GrPathUtils::quadraticPointCount(pts, tolerance
); |
595 prev = generate_quadratic_points(pts[0], pts[1], pts[2], toleran
ceSqd, prev, | 595 prev = generate_quadratic_points(pts[0], pts[1], pts[2], toleran
ceSqd, prev, |
596 &head, pointsLeft, alloc); | 596 &head, pointsLeft, alloc); |
597 *isLinear = false; | 597 *isLinear = false; |
598 break; | 598 break; |
599 } | 599 } |
600 case SkPath::kCubic_Verb: { | 600 case SkPath::kCubic_Verb: { |
601 int pointsLeft = GrPathUtils::cubicPointCount(pts, tolerance); | 601 int pointsLeft = GrPathUtils::cubicPointCount(pts, tolerance); |
602 prev = generate_cubic_points(pts[0], pts[1], pts[2], pts[3], | 602 prev = generate_cubic_points(pts[0], pts[1], pts[2], pts[3], |
603 toleranceSqd, prev, &head, pointsLeft, alloc); | 603 toleranceSqd, prev, &head, pointsLeft, alloc); |
604 *isLinear = false; | 604 *isLinear = false; |
605 break; | 605 break; |
606 } | 606 } |
607 case SkPath::kClose_Verb: | 607 case SkPath::kClose_Verb: |
608 if (head) { | 608 if (head) { |
609 head->fPrev = prev; | 609 head->fPrev = prev; |
610 prev->fNext = head; | 610 prev->fNext = head; |
611 *contours++ = head; | 611 *contours++ = head; |
612 } | 612 } |
613 head = prev = NULL; | 613 head = prev = nullptr; |
614 break; | 614 break; |
615 case SkPath::kDone_Verb: | 615 case SkPath::kDone_Verb: |
616 if (head) { | 616 if (head) { |
617 head->fPrev = prev; | 617 head->fPrev = prev; |
618 prev->fNext = head; | 618 prev->fNext = head; |
619 *contours++ = head; | 619 *contours++ = head; |
620 } | 620 } |
621 done = true; | 621 done = true; |
622 break; | 622 break; |
623 } | 623 } |
(...skipping 35 matching lines...) Expand 10 before | Expand all | Expand 10 after Loading... |
659 Edge* next = prev ? prev->fRight : edges->fHead; | 659 Edge* next = prev ? prev->fRight : edges->fHead; |
660 insert<Edge, &Edge::fLeft, &Edge::fRight>(edge, prev, next, &edges->fHead, &
edges->fTail); | 660 insert<Edge, &Edge::fLeft, &Edge::fRight>(edge, prev, next, &edges->fHead, &
edges->fTail); |
661 } | 661 } |
662 | 662 |
663 void find_enclosing_edges(Vertex* v, EdgeList* edges, Edge** left, Edge** right)
{ | 663 void find_enclosing_edges(Vertex* v, EdgeList* edges, Edge** left, Edge** right)
{ |
664 if (v->fFirstEdgeAbove) { | 664 if (v->fFirstEdgeAbove) { |
665 *left = v->fFirstEdgeAbove->fLeft; | 665 *left = v->fFirstEdgeAbove->fLeft; |
666 *right = v->fLastEdgeAbove->fRight; | 666 *right = v->fLastEdgeAbove->fRight; |
667 return; | 667 return; |
668 } | 668 } |
669 Edge* next = NULL; | 669 Edge* next = nullptr; |
670 Edge* prev; | 670 Edge* prev; |
671 for (prev = edges->fTail; prev != NULL; prev = prev->fLeft) { | 671 for (prev = edges->fTail; prev != nullptr; prev = prev->fLeft) { |
672 if (prev->isLeftOf(v)) { | 672 if (prev->isLeftOf(v)) { |
673 break; | 673 break; |
674 } | 674 } |
675 next = prev; | 675 next = prev; |
676 } | 676 } |
677 *left = prev; | 677 *left = prev; |
678 *right = next; | 678 *right = next; |
679 return; | 679 return; |
680 } | 680 } |
681 | 681 |
682 void find_enclosing_edges(Edge* edge, EdgeList* edges, Comparator& c, Edge** lef
t, Edge** right) { | 682 void find_enclosing_edges(Edge* edge, EdgeList* edges, Comparator& c, Edge** lef
t, Edge** right) { |
683 Edge* prev = NULL; | 683 Edge* prev = nullptr; |
684 Edge* next; | 684 Edge* next; |
685 for (next = edges->fHead; next != NULL; next = next->fRight) { | 685 for (next = edges->fHead; next != nullptr; next = next->fRight) { |
686 if ((c.sweep_gt(edge->fTop->fPoint, next->fTop->fPoint) && next->isRight
Of(edge->fTop)) || | 686 if ((c.sweep_gt(edge->fTop->fPoint, next->fTop->fPoint) && next->isRight
Of(edge->fTop)) || |
687 (c.sweep_gt(next->fTop->fPoint, edge->fTop->fPoint) && edge->isLeftO
f(next->fTop)) || | 687 (c.sweep_gt(next->fTop->fPoint, edge->fTop->fPoint) && edge->isLeftO
f(next->fTop)) || |
688 (c.sweep_lt(edge->fBottom->fPoint, next->fBottom->fPoint) && | 688 (c.sweep_lt(edge->fBottom->fPoint, next->fBottom->fPoint) && |
689 next->isRightOf(edge->fBottom)) || | 689 next->isRightOf(edge->fBottom)) || |
690 (c.sweep_lt(next->fBottom->fPoint, edge->fBottom->fPoint) && | 690 (c.sweep_lt(next->fBottom->fPoint, edge->fBottom->fPoint) && |
691 edge->isLeftOf(next->fBottom))) { | 691 edge->isLeftOf(next->fBottom))) { |
692 break; | 692 break; |
693 } | 693 } |
694 prev = next; | 694 prev = next; |
695 } | 695 } |
(...skipping 14 matching lines...) Expand all Loading... |
710 insert_edge(edge, left, activeEdges); | 710 insert_edge(edge, left, activeEdges); |
711 } | 711 } |
712 } | 712 } |
713 | 713 |
714 void insert_edge_above(Edge* edge, Vertex* v, Comparator& c) { | 714 void insert_edge_above(Edge* edge, Vertex* v, Comparator& c) { |
715 if (edge->fTop->fPoint == edge->fBottom->fPoint || | 715 if (edge->fTop->fPoint == edge->fBottom->fPoint || |
716 c.sweep_gt(edge->fTop->fPoint, edge->fBottom->fPoint)) { | 716 c.sweep_gt(edge->fTop->fPoint, edge->fBottom->fPoint)) { |
717 return; | 717 return; |
718 } | 718 } |
719 LOG("insert edge (%g -> %g) above vertex %g\n", edge->fTop->fID, edge->fBott
om->fID, v->fID); | 719 LOG("insert edge (%g -> %g) above vertex %g\n", edge->fTop->fID, edge->fBott
om->fID, v->fID); |
720 Edge* prev = NULL; | 720 Edge* prev = nullptr; |
721 Edge* next; | 721 Edge* next; |
722 for (next = v->fFirstEdgeAbove; next; next = next->fNextEdgeAbove) { | 722 for (next = v->fFirstEdgeAbove; next; next = next->fNextEdgeAbove) { |
723 if (next->isRightOf(edge->fTop)) { | 723 if (next->isRightOf(edge->fTop)) { |
724 break; | 724 break; |
725 } | 725 } |
726 prev = next; | 726 prev = next; |
727 } | 727 } |
728 insert<Edge, &Edge::fPrevEdgeAbove, &Edge::fNextEdgeAbove>( | 728 insert<Edge, &Edge::fPrevEdgeAbove, &Edge::fNextEdgeAbove>( |
729 edge, prev, next, &v->fFirstEdgeAbove, &v->fLastEdgeAbove); | 729 edge, prev, next, &v->fFirstEdgeAbove, &v->fLastEdgeAbove); |
730 } | 730 } |
731 | 731 |
732 void insert_edge_below(Edge* edge, Vertex* v, Comparator& c) { | 732 void insert_edge_below(Edge* edge, Vertex* v, Comparator& c) { |
733 if (edge->fTop->fPoint == edge->fBottom->fPoint || | 733 if (edge->fTop->fPoint == edge->fBottom->fPoint || |
734 c.sweep_gt(edge->fTop->fPoint, edge->fBottom->fPoint)) { | 734 c.sweep_gt(edge->fTop->fPoint, edge->fBottom->fPoint)) { |
735 return; | 735 return; |
736 } | 736 } |
737 LOG("insert edge (%g -> %g) below vertex %g\n", edge->fTop->fID, edge->fBott
om->fID, v->fID); | 737 LOG("insert edge (%g -> %g) below vertex %g\n", edge->fTop->fID, edge->fBott
om->fID, v->fID); |
738 Edge* prev = NULL; | 738 Edge* prev = nullptr; |
739 Edge* next; | 739 Edge* next; |
740 for (next = v->fFirstEdgeBelow; next; next = next->fNextEdgeBelow) { | 740 for (next = v->fFirstEdgeBelow; next; next = next->fNextEdgeBelow) { |
741 if (next->isRightOf(edge->fBottom)) { | 741 if (next->isRightOf(edge->fBottom)) { |
742 break; | 742 break; |
743 } | 743 } |
744 prev = next; | 744 prev = next; |
745 } | 745 } |
746 insert<Edge, &Edge::fPrevEdgeBelow, &Edge::fNextEdgeBelow>( | 746 insert<Edge, &Edge::fPrevEdgeBelow, &Edge::fNextEdgeBelow>( |
747 edge, prev, next, &v->fFirstEdgeBelow, &v->fLastEdgeBelow); | 747 edge, prev, next, &v->fFirstEdgeBelow, &v->fLastEdgeBelow); |
748 } | 748 } |
(...skipping 154 matching lines...) Expand 10 before | Expand all | Expand 10 after Loading... |
903 fix_active_state(newEdge, activeEdges, c); | 903 fix_active_state(newEdge, activeEdges, c); |
904 merge_collinear_edges(newEdge, activeEdges, c); | 904 merge_collinear_edges(newEdge, activeEdges, c); |
905 } | 905 } |
906 } | 906 } |
907 | 907 |
908 void merge_vertices(Vertex* src, Vertex* dst, Vertex** head, Comparator& c, SkCh
unkAlloc& alloc) { | 908 void merge_vertices(Vertex* src, Vertex* dst, Vertex** head, Comparator& c, SkCh
unkAlloc& alloc) { |
909 LOG("found coincident verts at %g, %g; merging %g into %g\n", src->fPoint.fX
, src->fPoint.fY, | 909 LOG("found coincident verts at %g, %g; merging %g into %g\n", src->fPoint.fX
, src->fPoint.fY, |
910 src->fID, dst->fID); | 910 src->fID, dst->fID); |
911 for (Edge* edge = src->fFirstEdgeAbove; edge;) { | 911 for (Edge* edge = src->fFirstEdgeAbove; edge;) { |
912 Edge* next = edge->fNextEdgeAbove; | 912 Edge* next = edge->fNextEdgeAbove; |
913 set_bottom(edge, dst, NULL, c); | 913 set_bottom(edge, dst, nullptr, c); |
914 edge = next; | 914 edge = next; |
915 } | 915 } |
916 for (Edge* edge = src->fFirstEdgeBelow; edge;) { | 916 for (Edge* edge = src->fFirstEdgeBelow; edge;) { |
917 Edge* next = edge->fNextEdgeBelow; | 917 Edge* next = edge->fNextEdgeBelow; |
918 set_top(edge, dst, NULL, c); | 918 set_top(edge, dst, nullptr, c); |
919 edge = next; | 919 edge = next; |
920 } | 920 } |
921 remove<Vertex, &Vertex::fPrev, &Vertex::fNext>(src, head, NULL); | 921 remove<Vertex, &Vertex::fPrev, &Vertex::fNext>(src, head, nullptr); |
922 } | 922 } |
923 | 923 |
924 Vertex* check_for_intersection(Edge* edge, Edge* other, EdgeList* activeEdges, C
omparator& c, | 924 Vertex* check_for_intersection(Edge* edge, Edge* other, EdgeList* activeEdges, C
omparator& c, |
925 SkChunkAlloc& alloc) { | 925 SkChunkAlloc& alloc) { |
926 SkPoint p; | 926 SkPoint p; |
927 if (!edge || !other) { | 927 if (!edge || !other) { |
928 return NULL; | 928 return nullptr; |
929 } | 929 } |
930 if (edge->intersect(*other, &p)) { | 930 if (edge->intersect(*other, &p)) { |
931 Vertex* v; | 931 Vertex* v; |
932 LOG("found intersection, pt is %g, %g\n", p.fX, p.fY); | 932 LOG("found intersection, pt is %g, %g\n", p.fX, p.fY); |
933 if (p == edge->fTop->fPoint || c.sweep_lt(p, edge->fTop->fPoint)) { | 933 if (p == edge->fTop->fPoint || c.sweep_lt(p, edge->fTop->fPoint)) { |
934 split_edge(other, edge->fTop, activeEdges, c, alloc); | 934 split_edge(other, edge->fTop, activeEdges, c, alloc); |
935 v = edge->fTop; | 935 v = edge->fTop; |
936 } else if (p == edge->fBottom->fPoint || c.sweep_gt(p, edge->fBottom->fP
oint)) { | 936 } else if (p == edge->fBottom->fPoint || c.sweep_gt(p, edge->fBottom->fP
oint)) { |
937 split_edge(other, edge->fBottom, activeEdges, c, alloc); | 937 split_edge(other, edge->fBottom, activeEdges, c, alloc); |
938 v = edge->fBottom; | 938 v = edge->fBottom; |
(...skipping 27 matching lines...) Expand all Loading... |
966 v->fPrev = prevV; | 966 v->fPrev = prevV; |
967 v->fNext = nextV; | 967 v->fNext = nextV; |
968 prevV->fNext = v; | 968 prevV->fNext = v; |
969 nextV->fPrev = v; | 969 nextV->fPrev = v; |
970 } | 970 } |
971 split_edge(edge, v, activeEdges, c, alloc); | 971 split_edge(edge, v, activeEdges, c, alloc); |
972 split_edge(other, v, activeEdges, c, alloc); | 972 split_edge(other, v, activeEdges, c, alloc); |
973 } | 973 } |
974 return v; | 974 return v; |
975 } | 975 } |
976 return NULL; | 976 return nullptr; |
977 } | 977 } |
978 | 978 |
979 void sanitize_contours(Vertex** contours, int contourCnt) { | 979 void sanitize_contours(Vertex** contours, int contourCnt) { |
980 for (int i = 0; i < contourCnt; ++i) { | 980 for (int i = 0; i < contourCnt; ++i) { |
981 SkASSERT(contours[i]); | 981 SkASSERT(contours[i]); |
982 for (Vertex* v = contours[i];;) { | 982 for (Vertex* v = contours[i];;) { |
983 if (coincident(v->fPrev->fPoint, v->fPoint)) { | 983 if (coincident(v->fPrev->fPoint, v->fPoint)) { |
984 LOG("vertex %g,%g coincident; removing\n", v->fPoint.fX, v->fPoi
nt.fY); | 984 LOG("vertex %g,%g coincident; removing\n", v->fPoint.fX, v->fPoi
nt.fY); |
985 if (v->fPrev == v) { | 985 if (v->fPrev == v) { |
986 contours[i] = NULL; | 986 contours[i] = nullptr; |
987 break; | 987 break; |
988 } | 988 } |
989 v->fPrev->fNext = v->fNext; | 989 v->fPrev->fNext = v->fNext; |
990 v->fNext->fPrev = v->fPrev; | 990 v->fNext->fPrev = v->fPrev; |
991 if (contours[i] == v) { | 991 if (contours[i] == v) { |
992 contours[i] = v->fNext; | 992 contours[i] = v->fNext; |
993 } | 993 } |
994 v = v->fPrev; | 994 v = v->fPrev; |
995 } else { | 995 } else { |
996 v = v->fNext; | 996 v = v->fNext; |
997 if (v == contours[i]) break; | 997 if (v == contours[i]) break; |
998 } | 998 } |
999 } | 999 } |
1000 } | 1000 } |
1001 } | 1001 } |
1002 | 1002 |
1003 void merge_coincident_vertices(Vertex** vertices, Comparator& c, SkChunkAlloc& a
lloc) { | 1003 void merge_coincident_vertices(Vertex** vertices, Comparator& c, SkChunkAlloc& a
lloc) { |
1004 for (Vertex* v = (*vertices)->fNext; v != NULL; v = v->fNext) { | 1004 for (Vertex* v = (*vertices)->fNext; v != nullptr; v = v->fNext) { |
1005 if (c.sweep_lt(v->fPoint, v->fPrev->fPoint)) { | 1005 if (c.sweep_lt(v->fPoint, v->fPrev->fPoint)) { |
1006 v->fPoint = v->fPrev->fPoint; | 1006 v->fPoint = v->fPrev->fPoint; |
1007 } | 1007 } |
1008 if (coincident(v->fPrev->fPoint, v->fPoint)) { | 1008 if (coincident(v->fPrev->fPoint, v->fPoint)) { |
1009 merge_vertices(v->fPrev, v, vertices, c, alloc); | 1009 merge_vertices(v->fPrev, v, vertices, c, alloc); |
1010 } | 1010 } |
1011 } | 1011 } |
1012 } | 1012 } |
1013 | 1013 |
1014 // Stage 2: convert the contours to a mesh of edges connecting the vertices. | 1014 // Stage 2: convert the contours to a mesh of edges connecting the vertices. |
1015 | 1015 |
1016 Vertex* build_edges(Vertex** contours, int contourCnt, Comparator& c, SkChunkAll
oc& alloc) { | 1016 Vertex* build_edges(Vertex** contours, int contourCnt, Comparator& c, SkChunkAll
oc& alloc) { |
1017 Vertex* vertices = NULL; | 1017 Vertex* vertices = nullptr; |
1018 Vertex* prev = NULL; | 1018 Vertex* prev = nullptr; |
1019 for (int i = 0; i < contourCnt; ++i) { | 1019 for (int i = 0; i < contourCnt; ++i) { |
1020 for (Vertex* v = contours[i]; v != NULL;) { | 1020 for (Vertex* v = contours[i]; v != nullptr;) { |
1021 Vertex* vNext = v->fNext; | 1021 Vertex* vNext = v->fNext; |
1022 Edge* edge = new_edge(v->fPrev, v, alloc, c); | 1022 Edge* edge = new_edge(v->fPrev, v, alloc, c); |
1023 if (edge->fWinding > 0) { | 1023 if (edge->fWinding > 0) { |
1024 insert_edge_below(edge, v->fPrev, c); | 1024 insert_edge_below(edge, v->fPrev, c); |
1025 insert_edge_above(edge, v, c); | 1025 insert_edge_above(edge, v, c); |
1026 } else { | 1026 } else { |
1027 insert_edge_below(edge, v, c); | 1027 insert_edge_below(edge, v, c); |
1028 insert_edge_above(edge, v->fPrev, c); | 1028 insert_edge_above(edge, v->fPrev, c); |
1029 } | 1029 } |
1030 merge_collinear_edges(edge, NULL, c); | 1030 merge_collinear_edges(edge, nullptr, c); |
1031 if (prev) { | 1031 if (prev) { |
1032 prev->fNext = v; | 1032 prev->fNext = v; |
1033 v->fPrev = prev; | 1033 v->fPrev = prev; |
1034 } else { | 1034 } else { |
1035 vertices = v; | 1035 vertices = v; |
1036 } | 1036 } |
1037 prev = v; | 1037 prev = v; |
1038 v = vNext; | 1038 v = vNext; |
1039 if (v == contours[i]) break; | 1039 if (v == contours[i]) break; |
1040 } | 1040 } |
1041 } | 1041 } |
1042 if (prev) { | 1042 if (prev) { |
1043 prev->fNext = vertices->fPrev = NULL; | 1043 prev->fNext = vertices->fPrev = nullptr; |
1044 } | 1044 } |
1045 return vertices; | 1045 return vertices; |
1046 } | 1046 } |
1047 | 1047 |
1048 // Stage 3: sort the vertices by increasing sweep direction. | 1048 // Stage 3: sort the vertices by increasing sweep direction. |
1049 | 1049 |
1050 Vertex* sorted_merge(Vertex* a, Vertex* b, Comparator& c); | 1050 Vertex* sorted_merge(Vertex* a, Vertex* b, Comparator& c); |
1051 | 1051 |
1052 void front_back_split(Vertex* v, Vertex** pFront, Vertex** pBack) { | 1052 void front_back_split(Vertex* v, Vertex** pFront, Vertex** pBack) { |
1053 Vertex* fast; | 1053 Vertex* fast; |
1054 Vertex* slow; | 1054 Vertex* slow; |
1055 if (!v || !v->fNext) { | 1055 if (!v || !v->fNext) { |
1056 *pFront = v; | 1056 *pFront = v; |
1057 *pBack = NULL; | 1057 *pBack = nullptr; |
1058 } else { | 1058 } else { |
1059 slow = v; | 1059 slow = v; |
1060 fast = v->fNext; | 1060 fast = v->fNext; |
1061 | 1061 |
1062 while (fast != NULL) { | 1062 while (fast != nullptr) { |
1063 fast = fast->fNext; | 1063 fast = fast->fNext; |
1064 if (fast != NULL) { | 1064 if (fast != nullptr) { |
1065 slow = slow->fNext; | 1065 slow = slow->fNext; |
1066 fast = fast->fNext; | 1066 fast = fast->fNext; |
1067 } | 1067 } |
1068 } | 1068 } |
1069 | 1069 |
1070 *pFront = v; | 1070 *pFront = v; |
1071 *pBack = slow->fNext; | 1071 *pBack = slow->fNext; |
1072 slow->fNext->fPrev = NULL; | 1072 slow->fNext->fPrev = nullptr; |
1073 slow->fNext = NULL; | 1073 slow->fNext = nullptr; |
1074 } | 1074 } |
1075 } | 1075 } |
1076 | 1076 |
1077 void merge_sort(Vertex** head, Comparator& c) { | 1077 void merge_sort(Vertex** head, Comparator& c) { |
1078 if (!*head || !(*head)->fNext) { | 1078 if (!*head || !(*head)->fNext) { |
1079 return; | 1079 return; |
1080 } | 1080 } |
1081 | 1081 |
1082 Vertex* a; | 1082 Vertex* a; |
1083 Vertex* b; | 1083 Vertex* b; |
1084 front_back_split(*head, &a, &b); | 1084 front_back_split(*head, &a, &b); |
1085 | 1085 |
1086 merge_sort(&a, c); | 1086 merge_sort(&a, c); |
1087 merge_sort(&b, c); | 1087 merge_sort(&b, c); |
1088 | 1088 |
1089 *head = sorted_merge(a, b, c); | 1089 *head = sorted_merge(a, b, c); |
1090 } | 1090 } |
1091 | 1091 |
1092 inline void append_vertex(Vertex* v, Vertex** head, Vertex** tail) { | 1092 inline void append_vertex(Vertex* v, Vertex** head, Vertex** tail) { |
1093 insert<Vertex, &Vertex::fPrev, &Vertex::fNext>(v, *tail, NULL, head, tail); | 1093 insert<Vertex, &Vertex::fPrev, &Vertex::fNext>(v, *tail, nullptr, head, tail
); |
1094 } | 1094 } |
1095 | 1095 |
1096 inline void append_vertex_list(Vertex* v, Vertex** head, Vertex** tail) { | 1096 inline void append_vertex_list(Vertex* v, Vertex** head, Vertex** tail) { |
1097 insert<Vertex, &Vertex::fPrev, &Vertex::fNext>(v, *tail, v->fNext, head, tai
l); | 1097 insert<Vertex, &Vertex::fPrev, &Vertex::fNext>(v, *tail, v->fNext, head, tai
l); |
1098 } | 1098 } |
1099 | 1099 |
1100 Vertex* sorted_merge(Vertex* a, Vertex* b, Comparator& c) { | 1100 Vertex* sorted_merge(Vertex* a, Vertex* b, Comparator& c) { |
1101 Vertex* head = NULL; | 1101 Vertex* head = nullptr; |
1102 Vertex* tail = NULL; | 1102 Vertex* tail = nullptr; |
1103 | 1103 |
1104 while (a && b) { | 1104 while (a && b) { |
1105 if (c.sweep_lt(a->fPoint, b->fPoint)) { | 1105 if (c.sweep_lt(a->fPoint, b->fPoint)) { |
1106 Vertex* next = a->fNext; | 1106 Vertex* next = a->fNext; |
1107 append_vertex(a, &head, &tail); | 1107 append_vertex(a, &head, &tail); |
1108 a = next; | 1108 a = next; |
1109 } else { | 1109 } else { |
1110 Vertex* next = b->fNext; | 1110 Vertex* next = b->fNext; |
1111 append_vertex(b, &head, &tail); | 1111 append_vertex(b, &head, &tail); |
1112 b = next; | 1112 b = next; |
1113 } | 1113 } |
1114 } | 1114 } |
1115 if (a) { | 1115 if (a) { |
1116 append_vertex_list(a, &head, &tail); | 1116 append_vertex_list(a, &head, &tail); |
1117 } | 1117 } |
1118 if (b) { | 1118 if (b) { |
1119 append_vertex_list(b, &head, &tail); | 1119 append_vertex_list(b, &head, &tail); |
1120 } | 1120 } |
1121 return head; | 1121 return head; |
1122 } | 1122 } |
1123 | 1123 |
1124 // Stage 4: Simplify the mesh by inserting new vertices at intersecting edges. | 1124 // Stage 4: Simplify the mesh by inserting new vertices at intersecting edges. |
1125 | 1125 |
1126 void simplify(Vertex* vertices, Comparator& c, SkChunkAlloc& alloc) { | 1126 void simplify(Vertex* vertices, Comparator& c, SkChunkAlloc& alloc) { |
1127 LOG("simplifying complex polygons\n"); | 1127 LOG("simplifying complex polygons\n"); |
1128 EdgeList activeEdges; | 1128 EdgeList activeEdges; |
1129 for (Vertex* v = vertices; v != NULL; v = v->fNext) { | 1129 for (Vertex* v = vertices; v != nullptr; v = v->fNext) { |
1130 if (!v->fFirstEdgeAbove && !v->fFirstEdgeBelow) { | 1130 if (!v->fFirstEdgeAbove && !v->fFirstEdgeBelow) { |
1131 continue; | 1131 continue; |
1132 } | 1132 } |
1133 #if LOGGING_ENABLED | 1133 #if LOGGING_ENABLED |
1134 LOG("\nvertex %g: (%g,%g)\n", v->fID, v->fPoint.fX, v->fPoint.fY); | 1134 LOG("\nvertex %g: (%g,%g)\n", v->fID, v->fPoint.fX, v->fPoint.fY); |
1135 #endif | 1135 #endif |
1136 Edge* leftEnclosingEdge = NULL; | 1136 Edge* leftEnclosingEdge = nullptr; |
1137 Edge* rightEnclosingEdge = NULL; | 1137 Edge* rightEnclosingEdge = nullptr; |
1138 bool restartChecks; | 1138 bool restartChecks; |
1139 do { | 1139 do { |
1140 restartChecks = false; | 1140 restartChecks = false; |
1141 find_enclosing_edges(v, &activeEdges, &leftEnclosingEdge, &rightEncl
osingEdge); | 1141 find_enclosing_edges(v, &activeEdges, &leftEnclosingEdge, &rightEncl
osingEdge); |
1142 if (v->fFirstEdgeBelow) { | 1142 if (v->fFirstEdgeBelow) { |
1143 for (Edge* edge = v->fFirstEdgeBelow; edge != NULL; edge = edge-
>fNextEdgeBelow) { | 1143 for (Edge* edge = v->fFirstEdgeBelow; edge != nullptr; edge = ed
ge->fNextEdgeBelow) { |
1144 if (check_for_intersection(edge, leftEnclosingEdge, &activeE
dges, c, alloc)) { | 1144 if (check_for_intersection(edge, leftEnclosingEdge, &activeE
dges, c, alloc)) { |
1145 restartChecks = true; | 1145 restartChecks = true; |
1146 break; | 1146 break; |
1147 } | 1147 } |
1148 if (check_for_intersection(edge, rightEnclosingEdge, &active
Edges, c, alloc)) { | 1148 if (check_for_intersection(edge, rightEnclosingEdge, &active
Edges, c, alloc)) { |
1149 restartChecks = true; | 1149 restartChecks = true; |
1150 break; | 1150 break; |
1151 } | 1151 } |
1152 } | 1152 } |
1153 } else { | 1153 } else { |
(...skipping 17 matching lines...) Expand all Loading... |
1171 } | 1171 } |
1172 v->fProcessed = true; | 1172 v->fProcessed = true; |
1173 } | 1173 } |
1174 } | 1174 } |
1175 | 1175 |
1176 // Stage 5: Tessellate the simplified mesh into monotone polygons. | 1176 // Stage 5: Tessellate the simplified mesh into monotone polygons. |
1177 | 1177 |
1178 Poly* tessellate(Vertex* vertices, SkChunkAlloc& alloc) { | 1178 Poly* tessellate(Vertex* vertices, SkChunkAlloc& alloc) { |
1179 LOG("tessellating simple polygons\n"); | 1179 LOG("tessellating simple polygons\n"); |
1180 EdgeList activeEdges; | 1180 EdgeList activeEdges; |
1181 Poly* polys = NULL; | 1181 Poly* polys = nullptr; |
1182 for (Vertex* v = vertices; v != NULL; v = v->fNext) { | 1182 for (Vertex* v = vertices; v != nullptr; v = v->fNext) { |
1183 if (!v->fFirstEdgeAbove && !v->fFirstEdgeBelow) { | 1183 if (!v->fFirstEdgeAbove && !v->fFirstEdgeBelow) { |
1184 continue; | 1184 continue; |
1185 } | 1185 } |
1186 #if LOGGING_ENABLED | 1186 #if LOGGING_ENABLED |
1187 LOG("\nvertex %g: (%g,%g)\n", v->fID, v->fPoint.fX, v->fPoint.fY); | 1187 LOG("\nvertex %g: (%g,%g)\n", v->fID, v->fPoint.fX, v->fPoint.fY); |
1188 #endif | 1188 #endif |
1189 Edge* leftEnclosingEdge = NULL; | 1189 Edge* leftEnclosingEdge = nullptr; |
1190 Edge* rightEnclosingEdge = NULL; | 1190 Edge* rightEnclosingEdge = nullptr; |
1191 find_enclosing_edges(v, &activeEdges, &leftEnclosingEdge, &rightEnclosin
gEdge); | 1191 find_enclosing_edges(v, &activeEdges, &leftEnclosingEdge, &rightEnclosin
gEdge); |
1192 Poly* leftPoly = NULL; | 1192 Poly* leftPoly = nullptr; |
1193 Poly* rightPoly = NULL; | 1193 Poly* rightPoly = nullptr; |
1194 if (v->fFirstEdgeAbove) { | 1194 if (v->fFirstEdgeAbove) { |
1195 leftPoly = v->fFirstEdgeAbove->fLeftPoly; | 1195 leftPoly = v->fFirstEdgeAbove->fLeftPoly; |
1196 rightPoly = v->fLastEdgeAbove->fRightPoly; | 1196 rightPoly = v->fLastEdgeAbove->fRightPoly; |
1197 } else { | 1197 } else { |
1198 leftPoly = leftEnclosingEdge ? leftEnclosingEdge->fRightPoly : NULL; | 1198 leftPoly = leftEnclosingEdge ? leftEnclosingEdge->fRightPoly : nullp
tr; |
1199 rightPoly = rightEnclosingEdge ? rightEnclosingEdge->fLeftPoly : NUL
L; | 1199 rightPoly = rightEnclosingEdge ? rightEnclosingEdge->fLeftPoly : nul
lptr; |
1200 } | 1200 } |
1201 #if LOGGING_ENABLED | 1201 #if LOGGING_ENABLED |
1202 LOG("edges above:\n"); | 1202 LOG("edges above:\n"); |
1203 for (Edge* e = v->fFirstEdgeAbove; e; e = e->fNextEdgeAbove) { | 1203 for (Edge* e = v->fFirstEdgeAbove; e; e = e->fNextEdgeAbove) { |
1204 LOG("%g -> %g, lpoly %d, rpoly %d\n", e->fTop->fID, e->fBottom->fID, | 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); | 1205 e->fLeftPoly ? e->fLeftPoly->fID : -1, e->fRightPoly ? e->fRight
Poly->fID : -1); |
1206 } | 1206 } |
1207 LOG("edges below:\n"); | 1207 LOG("edges below:\n"); |
1208 for (Edge* e = v->fFirstEdgeBelow; e; e = e->fNextEdgeBelow) { | 1208 for (Edge* e = v->fFirstEdgeBelow; e; e = e->fNextEdgeBelow) { |
1209 LOG("%g -> %g, lpoly %d, rpoly %d\n", e->fTop->fID, e->fBottom->fID, | 1209 LOG("%g -> %g, lpoly %d, rpoly %d\n", e->fTop->fID, e->fBottom->fID, |
(...skipping 15 matching lines...) Expand all Loading... |
1225 if (leftEdge->fRightPoly) { | 1225 if (leftEdge->fRightPoly) { |
1226 leftEdge->fRightPoly->end(v, alloc); | 1226 leftEdge->fRightPoly->end(v, alloc); |
1227 } | 1227 } |
1228 if (rightEdge->fLeftPoly && rightEdge->fLeftPoly != leftEdge->fR
ightPoly) { | 1228 if (rightEdge->fLeftPoly && rightEdge->fLeftPoly != leftEdge->fR
ightPoly) { |
1229 rightEdge->fLeftPoly->end(v, alloc); | 1229 rightEdge->fLeftPoly->end(v, alloc); |
1230 } | 1230 } |
1231 } | 1231 } |
1232 remove_edge(v->fLastEdgeAbove, &activeEdges); | 1232 remove_edge(v->fLastEdgeAbove, &activeEdges); |
1233 if (!v->fFirstEdgeBelow) { | 1233 if (!v->fFirstEdgeBelow) { |
1234 if (leftPoly && rightPoly && leftPoly != rightPoly) { | 1234 if (leftPoly && rightPoly && leftPoly != rightPoly) { |
1235 SkASSERT(leftPoly->fPartner == NULL && rightPoly->fPartner =
= NULL); | 1235 SkASSERT(leftPoly->fPartner == nullptr && rightPoly->fPartne
r == nullptr); |
1236 rightPoly->fPartner = leftPoly; | 1236 rightPoly->fPartner = leftPoly; |
1237 leftPoly->fPartner = rightPoly; | 1237 leftPoly->fPartner = rightPoly; |
1238 } | 1238 } |
1239 } | 1239 } |
1240 } | 1240 } |
1241 if (v->fFirstEdgeBelow) { | 1241 if (v->fFirstEdgeBelow) { |
1242 if (!v->fFirstEdgeAbove) { | 1242 if (!v->fFirstEdgeAbove) { |
1243 if (leftPoly && leftPoly == rightPoly) { | 1243 if (leftPoly && leftPoly == rightPoly) { |
1244 // Split the poly. | 1244 // Split the poly. |
1245 if (leftPoly->fActive->fSide == Poly::kLeft_Side) { | 1245 if (leftPoly->fActive->fSide == Poly::kLeft_Side) { |
(...skipping 29 matching lines...) Expand all Loading... |
1275 if (winding != 0) { | 1275 if (winding != 0) { |
1276 Poly* poly = new_poly(&polys, v, winding, alloc); | 1276 Poly* poly = new_poly(&polys, v, winding, alloc); |
1277 leftEdge->fRightPoly = rightEdge->fLeftPoly = poly; | 1277 leftEdge->fRightPoly = rightEdge->fLeftPoly = poly; |
1278 } | 1278 } |
1279 leftEdge = rightEdge; | 1279 leftEdge = rightEdge; |
1280 } | 1280 } |
1281 v->fLastEdgeBelow->fRightPoly = rightPoly; | 1281 v->fLastEdgeBelow->fRightPoly = rightPoly; |
1282 } | 1282 } |
1283 #if LOGGING_ENABLED | 1283 #if LOGGING_ENABLED |
1284 LOG("\nactive edges:\n"); | 1284 LOG("\nactive edges:\n"); |
1285 for (Edge* e = activeEdges.fHead; e != NULL; e = e->fRight) { | 1285 for (Edge* e = activeEdges.fHead; e != nullptr; e = e->fRight) { |
1286 LOG("%g -> %g, lpoly %d, rpoly %d\n", e->fTop->fID, e->fBottom->fID, | 1286 LOG("%g -> %g, lpoly %d, rpoly %d\n", e->fTop->fID, e->fBottom->fID, |
1287 e->fLeftPoly ? e->fLeftPoly->fID : -1, e->fRightPoly ? e->fRight
Poly->fID : -1); | 1287 e->fLeftPoly ? e->fLeftPoly->fID : -1, e->fRightPoly ? e->fRight
Poly->fID : -1); |
1288 } | 1288 } |
1289 #endif | 1289 #endif |
1290 } | 1290 } |
1291 return polys; | 1291 return polys; |
1292 } | 1292 } |
1293 | 1293 |
1294 // This is a driver function which calls stages 2-5 in turn. | 1294 // This is a driver function which calls stages 2-5 in turn. |
1295 | 1295 |
1296 Poly* contours_to_polys(Vertex** contours, int contourCnt, Comparator& c, SkChun
kAlloc& alloc) { | 1296 Poly* contours_to_polys(Vertex** contours, int contourCnt, Comparator& c, SkChun
kAlloc& alloc) { |
1297 #if LOGGING_ENABLED | 1297 #if LOGGING_ENABLED |
1298 for (int i = 0; i < contourCnt; ++i) { | 1298 for (int i = 0; i < contourCnt; ++i) { |
1299 Vertex* v = contours[i]; | 1299 Vertex* v = contours[i]; |
1300 SkASSERT(v); | 1300 SkASSERT(v); |
1301 LOG("path.moveTo(%20.20g, %20.20g);\n", v->fPoint.fX, v->fPoint.fY); | 1301 LOG("path.moveTo(%20.20g, %20.20g);\n", v->fPoint.fX, v->fPoint.fY); |
1302 for (v = v->fNext; v != contours[i]; v = v->fNext) { | 1302 for (v = v->fNext; v != contours[i]; v = v->fNext) { |
1303 LOG("path.lineTo(%20.20g, %20.20g);\n", v->fPoint.fX, v->fPoint.fY); | 1303 LOG("path.lineTo(%20.20g, %20.20g);\n", v->fPoint.fX, v->fPoint.fY); |
1304 } | 1304 } |
1305 } | 1305 } |
1306 #endif | 1306 #endif |
1307 sanitize_contours(contours, contourCnt); | 1307 sanitize_contours(contours, contourCnt); |
1308 Vertex* vertices = build_edges(contours, contourCnt, c, alloc); | 1308 Vertex* vertices = build_edges(contours, contourCnt, c, alloc); |
1309 if (!vertices) { | 1309 if (!vertices) { |
1310 return NULL; | 1310 return nullptr; |
1311 } | 1311 } |
1312 | 1312 |
1313 // Sort vertices in Y (secondarily in X). | 1313 // Sort vertices in Y (secondarily in X). |
1314 merge_sort(&vertices, c); | 1314 merge_sort(&vertices, c); |
1315 merge_coincident_vertices(&vertices, c, alloc); | 1315 merge_coincident_vertices(&vertices, c, alloc); |
1316 #if LOGGING_ENABLED | 1316 #if LOGGING_ENABLED |
1317 for (Vertex* v = vertices; v != NULL; v = v->fNext) { | 1317 for (Vertex* v = vertices; v != nullptr; v = v->fNext) { |
1318 static float gID = 0.0f; | 1318 static float gID = 0.0f; |
1319 v->fID = gID++; | 1319 v->fID = gID++; |
1320 } | 1320 } |
1321 #endif | 1321 #endif |
1322 simplify(vertices, c, alloc); | 1322 simplify(vertices, c, alloc); |
1323 return tessellate(vertices, alloc); | 1323 return tessellate(vertices, alloc); |
1324 } | 1324 } |
1325 | 1325 |
1326 // Stage 6: Triangulate the monotone polygons into a vertex buffer. | 1326 // Stage 6: Triangulate the monotone polygons into a vertex buffer. |
1327 | 1327 |
(...skipping 44 matching lines...) Expand 10 before | Expand all | Expand 10 after Loading... |
1372 SkMessageBus<GrUniqueKeyInvalidatedMessage>::Post(fMsg); | 1372 SkMessageBus<GrUniqueKeyInvalidatedMessage>::Post(fMsg); |
1373 } | 1373 } |
1374 }; | 1374 }; |
1375 | 1375 |
1376 } // namespace | 1376 } // namespace |
1377 | 1377 |
1378 bool GrTessellatingPathRenderer::onCanDrawPath(const CanDrawPathArgs& args) cons
t { | 1378 bool GrTessellatingPathRenderer::onCanDrawPath(const CanDrawPathArgs& args) cons
t { |
1379 // This path renderer can draw all fill styles, all stroke styles except hai
rlines, but does | 1379 // This path renderer can draw all fill styles, all stroke styles except hai
rlines, but does |
1380 // not do antialiasing. It can do convex and concave paths, but we'll leave
the convex ones to | 1380 // not do antialiasing. It can do convex and concave paths, but we'll leave
the convex ones to |
1381 // simpler algorithms. | 1381 // simpler algorithms. |
1382 return !IsStrokeHairlineOrEquivalent(*args.fStroke, *args.fViewMatrix, NULL)
&& | 1382 return !IsStrokeHairlineOrEquivalent(*args.fStroke, *args.fViewMatrix, nullp
tr) && |
1383 !args.fAntiAlias && !args.fPath->isConvex(); | 1383 !args.fAntiAlias && !args.fPath->isConvex(); |
1384 } | 1384 } |
1385 | 1385 |
1386 class TessellatingPathBatch : public GrVertexBatch { | 1386 class TessellatingPathBatch : public GrVertexBatch { |
1387 public: | 1387 public: |
1388 | 1388 |
1389 static GrDrawBatch* Create(const GrColor& color, | 1389 static GrDrawBatch* Create(const GrColor& color, |
1390 const SkPath& path, | 1390 const SkPath& path, |
1391 const GrStrokeInfo& stroke, | 1391 const GrStrokeInfo& stroke, |
1392 const SkMatrix& viewMatrix, | 1392 const SkMatrix& viewMatrix, |
(...skipping 219 matching lines...) Expand 10 before | Expand all | Expand 10 after Loading... |
1612 SkPath fPath; | 1612 SkPath fPath; |
1613 GrStrokeInfo fStroke; | 1613 GrStrokeInfo fStroke; |
1614 SkMatrix fViewMatrix; | 1614 SkMatrix fViewMatrix; |
1615 SkRect fClipBounds; // in source space | 1615 SkRect fClipBounds; // in source space |
1616 GrPipelineOptimizations fPipelineInfo; | 1616 GrPipelineOptimizations fPipelineInfo; |
1617 }; | 1617 }; |
1618 | 1618 |
1619 bool GrTessellatingPathRenderer::onDrawPath(const DrawPathArgs& args) { | 1619 bool GrTessellatingPathRenderer::onDrawPath(const DrawPathArgs& args) { |
1620 SkASSERT(!args.fAntiAlias); | 1620 SkASSERT(!args.fAntiAlias); |
1621 const GrRenderTarget* rt = args.fPipelineBuilder->getRenderTarget(); | 1621 const GrRenderTarget* rt = args.fPipelineBuilder->getRenderTarget(); |
1622 if (NULL == rt) { | 1622 if (nullptr == rt) { |
1623 return false; | 1623 return false; |
1624 } | 1624 } |
1625 | 1625 |
1626 SkIRect clipBoundsI; | 1626 SkIRect clipBoundsI; |
1627 args.fPipelineBuilder->clip().getConservativeBounds(rt, &clipBoundsI); | 1627 args.fPipelineBuilder->clip().getConservativeBounds(rt, &clipBoundsI); |
1628 SkRect clipBounds = SkRect::Make(clipBoundsI); | 1628 SkRect clipBounds = SkRect::Make(clipBoundsI); |
1629 SkMatrix vmi; | 1629 SkMatrix vmi; |
1630 if (!args.fViewMatrix->invert(&vmi)) { | 1630 if (!args.fViewMatrix->invert(&vmi)) { |
1631 return false; | 1631 return false; |
1632 } | 1632 } |
(...skipping 19 matching lines...) Expand all Loading... |
1652 bool result = viewMatrix.invert(&vmi); | 1652 bool result = viewMatrix.invert(&vmi); |
1653 if (!result) { | 1653 if (!result) { |
1654 SkFAIL("Cannot invert matrix\n"); | 1654 SkFAIL("Cannot invert matrix\n"); |
1655 } | 1655 } |
1656 vmi.mapRect(&clipBounds); | 1656 vmi.mapRect(&clipBounds); |
1657 GrStrokeInfo strokeInfo = GrTest::TestStrokeInfo(random); | 1657 GrStrokeInfo strokeInfo = GrTest::TestStrokeInfo(random); |
1658 return TessellatingPathBatch::Create(color, path, strokeInfo, viewMatrix, cl
ipBounds); | 1658 return TessellatingPathBatch::Create(color, path, strokeInfo, viewMatrix, cl
ipBounds); |
1659 } | 1659 } |
1660 | 1660 |
1661 #endif | 1661 #endif |
OLD | NEW |