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

Side by Side Diff: src/core/SkScan_Path.cpp

Issue 882733004: Faster edge re-sort (Closed) Base URL: https://skia.googlesource.com/skia.git@master
Patch Set: Created 5 years, 10 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/core/SkLineClipper.cpp ('k') | no next file » | 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 2006 The Android Open Source Project 2 * Copyright 2006 The Android Open Source Project
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 "SkScanPriv.h" 8 #include "SkScanPriv.h"
9 #include "SkBlitter.h" 9 #include "SkBlitter.h"
10 #include "SkEdge.h" 10 #include "SkEdge.h"
(...skipping 27 matching lines...) Expand all
38 } 38 }
39 #else 39 #else
40 #define validate_sort(edge) 40 #define validate_sort(edge)
41 #endif 41 #endif
42 42
43 static inline void remove_edge(SkEdge* edge) { 43 static inline void remove_edge(SkEdge* edge) {
44 edge->fPrev->fNext = edge->fNext; 44 edge->fPrev->fNext = edge->fNext;
45 edge->fNext->fPrev = edge->fPrev; 45 edge->fNext->fPrev = edge->fPrev;
46 } 46 }
47 47
48 static inline void swap_edges(SkEdge* prev, SkEdge* next) { 48 static inline void insert_edge_after(SkEdge* edge, SkEdge* afterMe) {
49 SkASSERT(prev->fNext == next && next->fPrev == prev); 49 edge->fPrev = afterMe;
50 50 edge->fNext = afterMe->fNext;
51 // remove prev from the list 51 afterMe->fNext->fPrev = edge;
52 prev->fPrev->fNext = next; 52 afterMe->fNext = edge;
53 next->fPrev = prev->fPrev;
54
55 // insert prev after next
56 prev->fNext = next->fNext;
57 next->fNext->fPrev = prev;
58 next->fNext = prev;
59 prev->fPrev = next;
60 } 53 }
61 54
62 static void backward_insert_edge_based_on_x(SkEdge* edge SkDECLAREPARAM(int, cur r_y)) { 55 static void backward_insert_edge_based_on_x(SkEdge* edge SkDECLAREPARAM(int, cur r_y)) {
63 SkFixed x = edge->fX; 56 SkFixed x = edge->fX;
64 57
65 for (;;) { 58 SkEdge* prev = edge->fPrev;
66 SkEdge* prev = edge->fPrev; 59 while (prev->fX > x) {
67 60 prev = prev->fPrev;
68 // add 1 to curr_y since we may have added new edges (built from curves) 61 }
69 // that start on the next scanline 62 if (prev->fNext != edge) {
70 SkASSERT(prev && prev->fFirstY <= curr_y + 1); 63 remove_edge(edge);
71 64 insert_edge_after(edge, prev);
72 if (prev->fX <= x) {
73 break;
74 }
75 swap_edges(prev, edge);
76 } 65 }
77 } 66 }
78 67
79 static void insert_new_edges(SkEdge* newEdge, int curr_y) { 68 static void insert_new_edges(SkEdge* newEdge, int curr_y) {
80 SkASSERT(newEdge->fFirstY >= curr_y); 69 SkASSERT(newEdge->fFirstY >= curr_y);
81 70
82 while (newEdge->fFirstY == curr_y) { 71 while (newEdge->fFirstY == curr_y) {
83 SkEdge* next = newEdge->fNext; 72 SkEdge* next = newEdge->fNext;
84 backward_insert_edge_based_on_x(newEdge SkPARAM(curr_y)); 73 backward_insert_edge_based_on_x(newEdge SkPARAM(curr_y));
85 newEdge = next; 74 newEdge = next;
(...skipping 20 matching lines...) Expand all
106 #pragma warning ( push ) 95 #pragma warning ( push )
107 #pragma warning ( disable : 4701 ) 96 #pragma warning ( disable : 4701 )
108 #endif 97 #endif
109 98
110 typedef void (*PrePostProc)(SkBlitter* blitter, int y, bool isStartOfScanline); 99 typedef void (*PrePostProc)(SkBlitter* blitter, int y, bool isStartOfScanline);
111 #define PREPOST_START true 100 #define PREPOST_START true
112 #define PREPOST_END false 101 #define PREPOST_END false
113 102
114 static void walk_edges(SkEdge* prevHead, SkPath::FillType fillType, 103 static void walk_edges(SkEdge* prevHead, SkPath::FillType fillType,
115 SkBlitter* blitter, int start_y, int stop_y, 104 SkBlitter* blitter, int start_y, int stop_y,
116 PrePostProc proc) { 105 PrePostProc proc, int rightClip) {
117 validate_sort(prevHead->fNext); 106 validate_sort(prevHead->fNext);
118 107
119 int curr_y = start_y; 108 int curr_y = start_y;
120 // returns 1 for evenodd, -1 for winding, regardless of inverse-ness 109 // returns 1 for evenodd, -1 for winding, regardless of inverse-ness
121 int windingMask = (fillType & 1) ? 1 : -1; 110 int windingMask = (fillType & 1) ? 1 : -1;
122 111
123 for (;;) { 112 for (;;) {
124 int w = 0; 113 int w = 0;
125 int left SK_INIT_TO_AVOID_WARNING; 114 int left SK_INIT_TO_AVOID_WARNING;
126 bool in_interval = false; 115 bool in_interval = false;
(...skipping 49 matching lines...) Expand 10 before | Expand all | Expand 10 after
176 if (newX < prevX) { // ripple currE backwards until it is x-sort ed 165 if (newX < prevX) { // ripple currE backwards until it is x-sort ed
177 backward_insert_edge_based_on_x(currE SkPARAM(curr_y)); 166 backward_insert_edge_based_on_x(currE SkPARAM(curr_y));
178 } else { 167 } else {
179 prevX = newX; 168 prevX = newX;
180 } 169 }
181 } 170 }
182 currE = next; 171 currE = next;
183 SkASSERT(currE); 172 SkASSERT(currE);
184 } 173 }
185 174
175 // was our right-edge culled away?
176 if (in_interval) {
177 int width = rightClip - left;
178 if (width > 0) {
179 blitter->blitH(left, curr_y, width);
180 }
181 }
182
186 if (proc) { 183 if (proc) {
187 proc(blitter, curr_y, PREPOST_END); // post-proc 184 proc(blitter, curr_y, PREPOST_END); // post-proc
188 } 185 }
189 186
190 curr_y += 1; 187 curr_y += 1;
191 if (curr_y >= stop_y) { 188 if (curr_y >= stop_y) {
192 break; 189 break;
193 } 190 }
194 // now currE points to the first edge with a Yint larger than curr_y 191 // now currE points to the first edge with a Yint larger than curr_y
195 insert_new_edges(currE, curr_y); 192 insert_new_edges(currE, curr_y);
(...skipping 227 matching lines...) Expand 10 before | Expand all | Expand 10 after
423 *last = list[count - 1]; 420 *last = list[count - 1];
424 return list[0]; 421 return list[0];
425 } 422 }
426 423
427 // clipRect may be null, even though we always have a clip. This indicates that 424 // clipRect may be null, even though we always have a clip. This indicates that
428 // the path is contained in the clip, and so we can ignore it during the blit 425 // the path is contained in the clip, and so we can ignore it during the blit
429 // 426 //
430 // clipRect (if no null) has already been shifted up 427 // clipRect (if no null) has already been shifted up
431 // 428 //
432 void sk_fill_path(const SkPath& path, const SkIRect* clipRect, SkBlitter* blitte r, 429 void sk_fill_path(const SkPath& path, const SkIRect* clipRect, SkBlitter* blitte r,
433 int start_y, int stop_y, int shiftEdgesUp, 430 int start_y, int stop_y, int shiftEdgesUp, const SkRegion& cli pRgn) {
434 const SkRegion& clipRgn) {
435 SkASSERT(blitter); 431 SkASSERT(blitter);
436 432
437 SkEdgeBuilder builder; 433 SkEdgeBuilder builder;
438 434
439 int count = builder.build(path, clipRect, shiftEdgesUp); 435 // If we're convex, then we need both edges, even the right edge is past the clip
436 const bool cullToTheRight = !path.isConvex();
437
438 int count = builder.build(path, clipRect, shiftEdgesUp, cullToTheRight);
440 SkEdge** list = builder.edgeList(); 439 SkEdge** list = builder.edgeList();
441 440
442 if (count < 2) { 441 if (count < 2) {
443 if (path.isInverseFillType()) { 442 if (path.isInverseFillType()) {
444 /* 443 /*
445 * Since we are in inverse-fill, our caller has already drawn above 444 * Since we are in inverse-fill, our caller has already drawn above
446 * our top (start_y) and will draw below our bottom (stop_y). Thus 445 * our top (start_y) and will draw below our bottom (stop_y). Thus
447 * we need to restrict our drawing to the intersection of the clip 446 * we need to restrict our drawing to the intersection of the clip
448 * and those two limits. 447 * and those two limits.
449 */ 448 */
(...skipping 46 matching lines...) Expand 10 before | Expand all | Expand 10 after
496 495
497 if (path.isInverseFillType()) { 496 if (path.isInverseFillType()) {
498 ib.setBlitter(blitter, clipRgn.getBounds(), shiftEdgesUp); 497 ib.setBlitter(blitter, clipRgn.getBounds(), shiftEdgesUp);
499 blitter = &ib; 498 blitter = &ib;
500 proc = PrePostInverseBlitterProc; 499 proc = PrePostInverseBlitterProc;
501 } 500 }
502 501
503 if (path.isConvex() && (NULL == proc)) { 502 if (path.isConvex() && (NULL == proc)) {
504 walk_convex_edges(&headEdge, path.getFillType(), blitter, start_y, stop_ y, NULL); 503 walk_convex_edges(&headEdge, path.getFillType(), blitter, start_y, stop_ y, NULL);
505 } else { 504 } else {
506 walk_edges(&headEdge, path.getFillType(), blitter, start_y, stop_y, proc ); 505 int rightEdge;
506 if (clipRect) {
507 rightEdge = clipRect->right();
508 } else {
509 rightEdge = SkScalarRoundToInt(path.getBounds().right()) << shiftEdg esUp;
510 }
511
512 walk_edges(&headEdge, path.getFillType(), blitter, start_y, stop_y, proc , rightEdge);
507 } 513 }
508 } 514 }
509 515
510 void sk_blit_above(SkBlitter* blitter, const SkIRect& ir, const SkRegion& clip) { 516 void sk_blit_above(SkBlitter* blitter, const SkIRect& ir, const SkRegion& clip) {
511 const SkIRect& cr = clip.getBounds(); 517 const SkIRect& cr = clip.getBounds();
512 SkIRect tmp; 518 SkIRect tmp;
513 519
514 tmp.fLeft = cr.fLeft; 520 tmp.fLeft = cr.fLeft;
515 tmp.fRight = cr.fRight; 521 tmp.fRight = cr.fRight;
516 tmp.fTop = cr.fTop; 522 tmp.fTop = cr.fTop;
(...skipping 207 matching lines...) Expand 10 before | Expand all | Expand 10 after
724 clipRgn = &wrap.getRgn(); 730 clipRgn = &wrap.getRgn();
725 blitter = wrap.getBlitter(); 731 blitter = wrap.getBlitter();
726 } 732 }
727 733
728 SkScanClipper clipper(blitter, clipRgn, ir); 734 SkScanClipper clipper(blitter, clipRgn, ir);
729 blitter = clipper.getBlitter(); 735 blitter = clipper.getBlitter();
730 if (blitter) { 736 if (blitter) {
731 sk_fill_triangle(pts, clipper.getClipRect(), blitter, ir); 737 sk_fill_triangle(pts, clipper.getClipRect(), blitter, ir);
732 } 738 }
733 } 739 }
OLDNEW
« no previous file with comments | « src/core/SkLineClipper.cpp ('k') | no next file » | no next file with comments »

Powered by Google App Engine
This is Rietveld 408576698