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

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

Issue 1316233002: Style Change: NULL->nullptr (Closed) Base URL: https://skia.googlesource.com/skia.git@master
Patch Set: 2015-08-27 (Thursday) 10:25:06 EDT Created 5 years, 3 months ago
Use n/p to move between diff chunks; N/P to move between comments. Draft comments are only viewable by you.
Jump to:
View unified diff | Download patch
« no previous file with comments | « src/gpu/GrTargetCommands.h ('k') | src/gpu/GrTest.cpp » ('j') | no next file with comments »
Toggle Intra-line Diffs ('i') | Expand Comments ('e') | Collapse Comments ('c') | Show Comments Hide Comments ('s')
OLDNEW
1 /* 1 /*
2 * Copyright 2015 Google Inc. 2 * Copyright 2015 Google Inc.
3 * 3 *
4 * Use of this source code is governed by a BSD-style license that can be 4 * Use of this source code is governed by a BSD-style license that can be
5 * found in the LICENSE file. 5 * found in the LICENSE file.
6 */ 6 */
7 7
8 #include "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
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
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
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
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
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
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
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
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
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
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
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
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
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
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
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
OLDNEW
« no previous file with comments | « src/gpu/GrTargetCommands.h ('k') | src/gpu/GrTest.cpp » ('j') | no next file with comments »

Powered by Google App Engine
This is Rietveld 408576698