1 /*
2 * Copyright 2006 The Android Open Source Project
3 *
4 * Use of this source code is governed by a BSD-style license that can be
5 * found in the LICENSE file.
6 */
7
8 #include "SkScanPriv.h"
9 #include "SkBlitter.h"
10 #include "SkEdge.h"
11 #include "SkEdgeBuilder.h"
12 #include "SkGeometry.h"
13 #include "SkPath.h"
14 #include "SkQuadClipper.h"
15 #include "SkRasterClip.h"
16 #include "SkRegion.h"
17 #include "SkTemplates.h"
18 #include "SkTSort.h"
19
20 #define kEDGE_HEAD_Y SK_MinS32
21 #define kEDGE_TAIL_Y SK_MaxS32
22
23 #ifdef SK_DEBUG
validate_sort(const SkEdge * edge)24 static void validate_sort(const SkEdge* edge) {
25 int y = kEDGE_HEAD_Y;
26
27 while (edge->fFirstY != SK_MaxS32) {
28 edge->validate();
29 SkASSERT(y <= edge->fFirstY);
30
31 y = edge->fFirstY;
32 edge = edge->fNext;
33 }
34 }
35 #else
36 #define validate_sort(edge)
37 #endif
38
remove_edge(SkEdge * edge)39 static inline void remove_edge(SkEdge* edge) {
40 edge->fPrev->fNext = edge->fNext;
41 edge->fNext->fPrev = edge->fPrev;
42 }
43
insert_edge_after(SkEdge * edge,SkEdge * afterMe)44 static inline void insert_edge_after(SkEdge* edge, SkEdge* afterMe) {
45 edge->fPrev = afterMe;
46 edge->fNext = afterMe->fNext;
47 afterMe->fNext->fPrev = edge;
48 afterMe->fNext = edge;
49 }
50
backward_insert_edge_based_on_x(SkEdge * edge SkDECLAREPARAM (int,curr_y))51 static void backward_insert_edge_based_on_x(SkEdge* edge SkDECLAREPARAM(int, curr_y)) {
52 SkFixed x = edge->fX;
53
54 SkEdge* prev = edge->fPrev;
55 while (prev->fX > x) {
56 prev = prev->fPrev;
57 }
58 if (prev->fNext != edge) {
59 remove_edge(edge);
60 insert_edge_after(edge, prev);
61 }
62 }
63
64 // Start from the right side, searching backwards for the point to begin the new edge list
65 // insertion, marching forwards from here. The implementation could have started from the left
66 // of the prior insertion, and search to the right, or with some additional caching, binary
67 // search the starting point. More work could be done to determine optimal new edge insertion.
backward_insert_start(SkEdge * prev,SkFixed x)68 static SkEdge* backward_insert_start(SkEdge* prev, SkFixed x) {
69 while (prev->fX > x) {
70 prev = prev->fPrev;
71 }
72 return prev;
73 }
74
insert_new_edges(SkEdge * newEdge,int curr_y)75 static void insert_new_edges(SkEdge* newEdge, int curr_y) {
76 if (newEdge->fFirstY != curr_y) {
77 return;
78 }
79 SkEdge* prev = newEdge->fPrev;
80 if (prev->fX <= newEdge->fX) {
81 return;
82 }
83 // find first x pos to insert
84 SkEdge* start = backward_insert_start(prev, newEdge->fX);
85 // insert the lot, fixing up the links as we go
86 do {
87 SkEdge* next = newEdge->fNext;
88 do {
89 if (start->fNext == newEdge) {
90 goto nextEdge;
91 }
92 SkEdge* after = start->fNext;
93 if (after->fX >= newEdge->fX) {
94 break;
95 }
96 start = after;
97 } while (true);
98 remove_edge(newEdge);
99 insert_edge_after(newEdge, start);
100 nextEdge:
101 start = newEdge;
102 newEdge = next;
103 } while (newEdge->fFirstY == curr_y);
104 }
105
106 #ifdef SK_DEBUG
validate_edges_for_y(const SkEdge * edge,int curr_y)107 static void validate_edges_for_y(const SkEdge* edge, int curr_y) {
108 while (edge->fFirstY <= curr_y) {
109 SkASSERT(edge->fPrev && edge->fNext);
110 SkASSERT(edge->fPrev->fNext == edge);
111 SkASSERT(edge->fNext->fPrev == edge);
112 SkASSERT(edge->fFirstY <= edge->fLastY);
113
114 SkASSERT(edge->fPrev->fX <= edge->fX);
115 edge = edge->fNext;
116 }
117 }
118 #else
119 #define validate_edges_for_y(edge, curr_y)
120 #endif
121
122 #if defined _WIN32 && _MSC_VER >= 1300 // disable warning : local variable used without having been initialized
123 #pragma warning ( push )
124 #pragma warning ( disable : 4701 )
125 #endif
126
127 typedef void (*PrePostProc)(SkBlitter* blitter, int y, bool isStartOfScanline);
128 #define PREPOST_START true
129 #define PREPOST_END false
130
walk_edges(SkEdge * prevHead,SkPath::FillType fillType,SkBlitter * blitter,int start_y,int stop_y,PrePostProc proc,int rightClip)131 static void walk_edges(SkEdge* prevHead, SkPath::FillType fillType,
132 SkBlitter* blitter, int start_y, int stop_y,
133 PrePostProc proc, int rightClip) {
134 validate_sort(prevHead->fNext);
135
136 int curr_y = start_y;
137 // returns 1 for evenodd, -1 for winding, regardless of inverse-ness
138 int windingMask = (fillType & 1) ? 1 : -1;
139
140 for (;;) {
141 int w = 0;
142 int left SK_INIT_TO_AVOID_WARNING;
143 bool in_interval = false;
144 SkEdge* currE = prevHead->fNext;
145 SkFixed prevX = prevHead->fX;
146
147 validate_edges_for_y(currE, curr_y);
148
149 if (proc) {
150 proc(blitter, curr_y, PREPOST_START); // pre-proc
151 }
152
153 while (currE->fFirstY <= curr_y) {
154 SkASSERT(currE->fLastY >= curr_y);
155
156 int x = SkFixedRoundToInt(currE->fX);
157 w += currE->fWinding;
158 if ((w & windingMask) == 0) { // we finished an interval
159 SkASSERT(in_interval);
160 int width = x - left;
161 SkASSERT(width >= 0);
162 if (width)
163 blitter->blitH(left, curr_y, width);
164 in_interval = false;
165 } else if (!in_interval) {
166 left = x;
167 in_interval = true;
168 }
169
170 SkEdge* next = currE->fNext;
171 SkFixed newX;
172
173 if (currE->fLastY == curr_y) { // are we done with this edge?
174 if (currE->fCurveCount < 0) {
175 if (((SkCubicEdge*)currE)->updateCubic()) {
176 SkASSERT(currE->fFirstY == curr_y + 1);
177
178 newX = currE->fX;
179 goto NEXT_X;
180 }
181 } else if (currE->fCurveCount > 0) {
182 if (((SkQuadraticEdge*)currE)->updateQuadratic()) {
183 newX = currE->fX;
184 goto NEXT_X;
185 }
186 }
187 remove_edge(currE);
188 } else {
189 SkASSERT(currE->fLastY > curr_y);
190 newX = currE->fX + currE->fDX;
191 currE->fX = newX;
192 NEXT_X:
193 if (newX < prevX) { // ripple currE backwards until it is x-sorted
194 backward_insert_edge_based_on_x(currE SkPARAM(curr_y));
195 } else {
196 prevX = newX;
197 }
198 }
199 currE = next;
200 SkASSERT(currE);
201 }
202
203 // was our right-edge culled away?
204 if (in_interval) {
205 int width = rightClip - left;
206 if (width > 0) {
207 blitter->blitH(left, curr_y, width);
208 }
209 }
210
211 if (proc) {
212 proc(blitter, curr_y, PREPOST_END); // post-proc
213 }
214
215 curr_y += 1;
216 if (curr_y >= stop_y) {
217 break;
218 }
219 // now currE points to the first edge with a Yint larger than curr_y
220 insert_new_edges(currE, curr_y);
221 }
222 }
223
224 // return true if we're done with this edge
update_edge(SkEdge * edge,int last_y)225 static bool update_edge(SkEdge* edge, int last_y) {
226 SkASSERT(edge->fLastY >= last_y);
227 if (last_y == edge->fLastY) {
228 if (edge->fCurveCount < 0) {
229 if (((SkCubicEdge*)edge)->updateCubic()) {
230 SkASSERT(edge->fFirstY == last_y + 1);
231 return false;
232 }
233 } else if (edge->fCurveCount > 0) {
234 if (((SkQuadraticEdge*)edge)->updateQuadratic()) {
235 SkASSERT(edge->fFirstY == last_y + 1);
236 return false;
237 }
238 }
239 return true;
240 }
241 return false;
242 }
243
walk_convex_edges(SkEdge * prevHead,SkPath::FillType,SkBlitter * blitter,int start_y,int stop_y,PrePostProc proc)244 static void walk_convex_edges(SkEdge* prevHead, SkPath::FillType,
245 SkBlitter* blitter, int start_y, int stop_y,
246 PrePostProc proc) {
247 validate_sort(prevHead->fNext);
248
249 SkEdge* leftE = prevHead->fNext;
250 SkEdge* riteE = leftE->fNext;
251 SkEdge* currE = riteE->fNext;
252
253 #if 0
254 int local_top = leftE->fFirstY;
255 SkASSERT(local_top == riteE->fFirstY);
256 #else
257 // our edge choppers for curves can result in the initial edges
258 // not lining up, so we take the max.
259 int local_top = SkMax32(leftE->fFirstY, riteE->fFirstY);
260 #endif
261 SkASSERT(local_top >= start_y);
262
263 for (;;) {
264 SkASSERT(leftE->fFirstY <= stop_y);
265 SkASSERT(riteE->fFirstY <= stop_y);
266
267 if (leftE->fX > riteE->fX || (leftE->fX == riteE->fX &&
268 leftE->fDX > riteE->fDX)) {
269 SkTSwap(leftE, riteE);
270 }
271
272 int local_bot = SkMin32(leftE->fLastY, riteE->fLastY);
273 local_bot = SkMin32(local_bot, stop_y - 1);
274 SkASSERT(local_top <= local_bot);
275
276 SkFixed left = leftE->fX;
277 SkFixed dLeft = leftE->fDX;
278 SkFixed rite = riteE->fX;
279 SkFixed dRite = riteE->fDX;
280 int count = local_bot - local_top;
281 SkASSERT(count >= 0);
282 if (0 == (dLeft | dRite)) {
283 int L = SkFixedRoundToInt(left);
284 int R = SkFixedRoundToInt(rite);
285 if (L < R) {
286 count += 1;
287 blitter->blitRect(L, local_top, R - L, count);
288 }
289 local_top = local_bot + 1;
290 } else {
291 do {
292 int L = SkFixedRoundToInt(left);
293 int R = SkFixedRoundToInt(rite);
294 if (L < R) {
295 blitter->blitH(L, local_top, R - L);
296 }
297 left += dLeft;
298 rite += dRite;
299 local_top += 1;
300 } while (--count >= 0);
301 }
302
303 leftE->fX = left;
304 riteE->fX = rite;
305
306 if (update_edge(leftE, local_bot)) {
307 if (currE->fFirstY >= stop_y) {
308 break;
309 }
310 leftE = currE;
311 currE = currE->fNext;
312 }
313 if (update_edge(riteE, local_bot)) {
314 if (currE->fFirstY >= stop_y) {
315 break;
316 }
317 riteE = currE;
318 currE = currE->fNext;
319 }
320
321 SkASSERT(leftE);
322 SkASSERT(riteE);
323
324 // check our bottom clip
325 SkASSERT(local_top == local_bot + 1);
326 if (local_top >= stop_y) {
327 break;
328 }
329 }
330 }
331
332 ///////////////////////////////////////////////////////////////////////////////
333
334 // this guy overrides blitH, and will call its proxy blitter with the inverse
335 // of the spans it is given (clipped to the left/right of the cliprect)
336 //
337 // used to implement inverse filltypes on paths
338 //
339 class InverseBlitter : public SkBlitter {
340 public:
setBlitter(SkBlitter * blitter,const SkIRect & clip,int shift)341 void setBlitter(SkBlitter* blitter, const SkIRect& clip, int shift) {
342 fBlitter = blitter;
343 fFirstX = clip.fLeft << shift;
344 fLastX = clip.fRight << shift;
345 }
prepost(int y,bool isStart)346 void prepost(int y, bool isStart) {
347 if (isStart) {
348 fPrevX = fFirstX;
349 } else {
350 int invWidth = fLastX - fPrevX;
351 if (invWidth > 0) {
352 fBlitter->blitH(fPrevX, y, invWidth);
353 }
354 }
355 }
356
357 // overrides
blitH(int x,int y,int width)358 void blitH(int x, int y, int width) override {
359 int invWidth = x - fPrevX;
360 if (invWidth > 0) {
361 fBlitter->blitH(fPrevX, y, invWidth);
362 }
363 fPrevX = x + width;
364 }
365
366 // we do not expect to get called with these entrypoints
blitAntiH(int,int,const SkAlpha[],const int16_t runs[])367 void blitAntiH(int, int, const SkAlpha[], const int16_t runs[]) override {
368 SkDEBUGFAIL("blitAntiH unexpected");
369 }
blitV(int x,int y,int height,SkAlpha alpha)370 void blitV(int x, int y, int height, SkAlpha alpha) override {
371 SkDEBUGFAIL("blitV unexpected");
372 }
blitRect(int x,int y,int width,int height)373 void blitRect(int x, int y, int width, int height) override {
374 SkDEBUGFAIL("blitRect unexpected");
375 }
blitMask(const SkMask &,const SkIRect & clip)376 void blitMask(const SkMask&, const SkIRect& clip) override {
377 SkDEBUGFAIL("blitMask unexpected");
378 }
justAnOpaqueColor(uint32_t * value)379 const SkPixmap* justAnOpaqueColor(uint32_t* value) override {
380 SkDEBUGFAIL("justAnOpaqueColor unexpected");
381 return nullptr;
382 }
383
384 private:
385 SkBlitter* fBlitter;
386 int fFirstX, fLastX, fPrevX;
387 };
388
PrePostInverseBlitterProc(SkBlitter * blitter,int y,bool isStart)389 static void PrePostInverseBlitterProc(SkBlitter* blitter, int y, bool isStart) {
390 ((InverseBlitter*)blitter)->prepost(y, isStart);
391 }
392
393 ///////////////////////////////////////////////////////////////////////////////
394
395 #if defined _WIN32 && _MSC_VER >= 1300
396 #pragma warning ( pop )
397 #endif
398
operator <(const SkEdge & a,const SkEdge & b)399 static bool operator<(const SkEdge& a, const SkEdge& b) {
400 int valuea = a.fFirstY;
401 int valueb = b.fFirstY;
402
403 if (valuea == valueb) {
404 valuea = a.fX;
405 valueb = b.fX;
406 }
407
408 return valuea < valueb;
409 }
410
sort_edges(SkEdge * list[],int count,SkEdge ** last)411 static SkEdge* sort_edges(SkEdge* list[], int count, SkEdge** last) {
412 SkTQSort(list, list + count - 1);
413
414 // now make the edges linked in sorted order
415 for (int i = 1; i < count; i++) {
416 list[i - 1]->fNext = list[i];
417 list[i]->fPrev = list[i - 1];
418 }
419
420 *last = list[count - 1];
421 return list[0];
422 }
423
424 // clipRect may be null, even though we always have a clip. This indicates that
425 // the path is contained in the clip, and so we can ignore it during the blit
426 //
427 // clipRect (if no null) has already been shifted up
428 //
sk_fill_path(const SkPath & path,const SkIRect * clipRect,SkBlitter * blitter,int start_y,int stop_y,int shiftEdgesUp,const SkRegion & clipRgn)429 void sk_fill_path(const SkPath& path, const SkIRect* clipRect, SkBlitter* blitter,
430 int start_y, int stop_y, int shiftEdgesUp, const SkRegion& clipRgn) {
431 SkASSERT(blitter);
432
433 SkEdgeBuilder builder;
434
435 // If we're convex, then we need both edges, even the right edge is past the clip
436 const bool canCullToTheRight = !path.isConvex();
437
438 int count = builder.build(path, clipRect, shiftEdgesUp, canCullToTheRight);
439 SkASSERT(count >= 0);
440
441 SkEdge** list = builder.edgeList();
442
443 if (0 == count) {
444 if (path.isInverseFillType()) {
445 /*
446 * Since we are in inverse-fill, our caller has already drawn above
447 * our top (start_y) and will draw below our bottom (stop_y). Thus
448 * we need to restrict our drawing to the intersection of the clip
449 * and those two limits.
450 */
451 SkIRect rect = clipRgn.getBounds();
452 if (rect.fTop < start_y) {
453 rect.fTop = start_y;
454 }
455 if (rect.fBottom > stop_y) {
456 rect.fBottom = stop_y;
457 }
458 if (!rect.isEmpty()) {
459 blitter->blitRect(rect.fLeft << shiftEdgesUp,
460 rect.fTop << shiftEdgesUp,
461 rect.width() << shiftEdgesUp,
462 rect.height() << shiftEdgesUp);
463 }
464 }
465 return;
466 }
467
468 SkEdge headEdge, tailEdge, *last;
469 // this returns the first and last edge after they're sorted into a dlink list
470 SkEdge* edge = sort_edges(list, count, &last);
471
472 headEdge.fPrev = nullptr;
473 headEdge.fNext = edge;
474 headEdge.fFirstY = kEDGE_HEAD_Y;
475 headEdge.fX = SK_MinS32;
476 edge->fPrev = &headEdge;
477
478 tailEdge.fPrev = last;
479 tailEdge.fNext = nullptr;
480 tailEdge.fFirstY = kEDGE_TAIL_Y;
481 last->fNext = &tailEdge;
482
483 // now edge is the head of the sorted linklist
484
485 start_y = SkLeftShift(start_y, shiftEdgesUp);
486 stop_y = SkLeftShift(stop_y, shiftEdgesUp);
487 if (clipRect && start_y < clipRect->fTop) {
488 start_y = clipRect->fTop;
489 }
490 if (clipRect && stop_y > clipRect->fBottom) {
491 stop_y = clipRect->fBottom;
492 }
493
494 InverseBlitter ib;
495 PrePostProc proc = nullptr;
496
497 if (path.isInverseFillType()) {
498 ib.setBlitter(blitter, clipRgn.getBounds(), shiftEdgesUp);
499 blitter = &ib;
500 proc = PrePostInverseBlitterProc;
501 }
502
503 if (path.isConvex() && (nullptr == proc)) {
504 SkASSERT(count >= 2); // convex walker does not handle missing right edges
505 walk_convex_edges(&headEdge, path.getFillType(), blitter, start_y, stop_y, nullptr);
506 } else {
507 int rightEdge;
508 if (clipRect) {
509 rightEdge = clipRect->right();
510 } else {
511 rightEdge = SkScalarRoundToInt(path.getBounds().right()) << shiftEdgesUp;
512 }
513
514 walk_edges(&headEdge, path.getFillType(), blitter, start_y, stop_y, proc, rightEdge);
515 }
516 }
517
sk_blit_above(SkBlitter * blitter,const SkIRect & ir,const SkRegion & clip)518 void sk_blit_above(SkBlitter* blitter, const SkIRect& ir, const SkRegion& clip) {
519 const SkIRect& cr = clip.getBounds();
520 SkIRect tmp;
521
522 tmp.fLeft = cr.fLeft;
523 tmp.fRight = cr.fRight;
524 tmp.fTop = cr.fTop;
525 tmp.fBottom = ir.fTop;
526 if (!tmp.isEmpty()) {
527 blitter->blitRectRegion(tmp, clip);
528 }
529 }
530
sk_blit_below(SkBlitter * blitter,const SkIRect & ir,const SkRegion & clip)531 void sk_blit_below(SkBlitter* blitter, const SkIRect& ir, const SkRegion& clip) {
532 const SkIRect& cr = clip.getBounds();
533 SkIRect tmp;
534
535 tmp.fLeft = cr.fLeft;
536 tmp.fRight = cr.fRight;
537 tmp.fTop = ir.fBottom;
538 tmp.fBottom = cr.fBottom;
539 if (!tmp.isEmpty()) {
540 blitter->blitRectRegion(tmp, clip);
541 }
542 }
543
544 ///////////////////////////////////////////////////////////////////////////////
545
546 /**
547 * If the caller is drawing an inverse-fill path, then it pass true for
548 * skipRejectTest, so we don't abort drawing just because the src bounds (ir)
549 * is outside of the clip.
550 */
SkScanClipper(SkBlitter * blitter,const SkRegion * clip,const SkIRect & ir,bool skipRejectTest)551 SkScanClipper::SkScanClipper(SkBlitter* blitter, const SkRegion* clip,
552 const SkIRect& ir, bool skipRejectTest) {
553 fBlitter = nullptr; // null means blit nothing
554 fClipRect = nullptr;
555
556 if (clip) {
557 fClipRect = &clip->getBounds();
558 if (!skipRejectTest && !SkIRect::Intersects(*fClipRect, ir)) { // completely clipped out
559 return;
560 }
561
562 if (clip->isRect()) {
563 if (fClipRect->contains(ir)) {
564 fClipRect = nullptr;
565 } else {
566 // only need a wrapper blitter if we're horizontally clipped
567 if (fClipRect->fLeft > ir.fLeft || fClipRect->fRight < ir.fRight) {
568 fRectBlitter.init(blitter, *fClipRect);
569 blitter = &fRectBlitter;
570 }
571 }
572 } else {
573 fRgnBlitter.init(blitter, clip);
574 blitter = &fRgnBlitter;
575 }
576 }
577 fBlitter = blitter;
578 }
579
580 ///////////////////////////////////////////////////////////////////////////////
581
clip_to_limit(const SkRegion & orig,SkRegion * reduced)582 static bool clip_to_limit(const SkRegion& orig, SkRegion* reduced) {
583 const int32_t limit = 32767;
584
585 SkIRect limitR;
586 limitR.set(-limit, -limit, limit, limit);
587 if (limitR.contains(orig.getBounds())) {
588 return false;
589 }
590 reduced->op(orig, limitR, SkRegion::kIntersect_Op);
591 return true;
592 }
593
594 /**
595 * Variant of SkScalarRoundToInt, identical to SkDScalarRoundToInt except when the input fraction
596 * is 0.5. In this case only, round the value down. This is used to round the top and left
597 * of a rectangle, and corresponds to the way the scan converter treats the top and left edges.
598 */
round_down_to_int(SkScalar x)599 static inline int round_down_to_int(SkScalar x) {
600 double xx = x;
601 xx += 0.5;
602 double floorXX = floor(xx);
603 return (int)floorXX - (xx == floorXX);
604 }
605
606 /**
607 * Variant of SkRect::round() that explicitly performs the rounding step (i.e. floor(x + 0.5))
608 * using double instead of SkScalar (float). It does this by calling SkDScalarRoundToInt(),
609 * which may be slower than calling SkScalarRountToInt(), but gives slightly more accurate
610 * results. Also rounds top and left using double, flooring when the fraction is exactly 0.5f.
611 *
612 * e.g.
613 * SkScalar left = 0.5f;
614 * int ileft = SkScalarRoundToInt(left);
615 * SkASSERT(0 == ileft); // <--- fails
616 * int ileft = round_down_to_int(left);
617 * SkASSERT(0 == ileft); // <--- succeeds
618 * SkScalar right = 0.49999997f;
619 * int iright = SkScalarRoundToInt(right);
620 * SkASSERT(0 == iright); // <--- fails
621 * iright = SkDScalarRoundToInt(right);
622 * SkASSERT(0 == iright); // <--- succeeds
623 */
round_asymmetric_to_int(const SkRect & src,SkIRect * dst)624 static void round_asymmetric_to_int(const SkRect& src, SkIRect* dst) {
625 SkASSERT(dst);
626 dst->set(round_down_to_int(src.fLeft), round_down_to_int(src.fTop),
627 SkDScalarRoundToInt(src.fRight), SkDScalarRoundToInt(src.fBottom));
628 }
629
FillPath(const SkPath & path,const SkRegion & origClip,SkBlitter * blitter)630 void SkScan::FillPath(const SkPath& path, const SkRegion& origClip,
631 SkBlitter* blitter) {
632 if (origClip.isEmpty()) {
633 return;
634 }
635
636 // Our edges are fixed-point, and don't like the bounds of the clip to
637 // exceed that. Here we trim the clip just so we don't overflow later on
638 const SkRegion* clipPtr = &origClip;
639 SkRegion finiteClip;
640 if (clip_to_limit(origClip, &finiteClip)) {
641 if (finiteClip.isEmpty()) {
642 return;
643 }
644 clipPtr = &finiteClip;
645 }
646 // don't reference "origClip" any more, just use clipPtr
647
648 SkIRect ir;
649 // We deliberately call round_asymmetric_to_int() instead of round(), since we can't afford
650 // to generate a bounds that is tighter than the corresponding SkEdges. The edge code basically
651 // converts the floats to fixed, and then "rounds". If we called round() instead of
652 // round_asymmetric_to_int() here, we could generate the wrong ir for values like 0.4999997.
653 round_asymmetric_to_int(path.getBounds(), &ir);
654 if (ir.isEmpty()) {
655 if (path.isInverseFillType()) {
656 blitter->blitRegion(*clipPtr);
657 }
658 return;
659 }
660
661 SkScanClipper clipper(blitter, clipPtr, ir, path.isInverseFillType());
662
663 blitter = clipper.getBlitter();
664 if (blitter) {
665 // we have to keep our calls to blitter in sorted order, so we
666 // must blit the above section first, then the middle, then the bottom.
667 if (path.isInverseFillType()) {
668 sk_blit_above(blitter, ir, *clipPtr);
669 }
670 sk_fill_path(path, clipper.getClipRect(), blitter, ir.fTop, ir.fBottom,
671 0, *clipPtr);
672 if (path.isInverseFillType()) {
673 sk_blit_below(blitter, ir, *clipPtr);
674 }
675 } else {
676 // what does it mean to not have a blitter if path.isInverseFillType???
677 }
678 }
679
FillPath(const SkPath & path,const SkIRect & ir,SkBlitter * blitter)680 void SkScan::FillPath(const SkPath& path, const SkIRect& ir,
681 SkBlitter* blitter) {
682 SkRegion rgn(ir);
683 FillPath(path, rgn, blitter);
684 }
685
686 ///////////////////////////////////////////////////////////////////////////////
687
build_tri_edges(SkEdge edge[],const SkPoint pts[],const SkIRect * clipRect,SkEdge * list[])688 static int build_tri_edges(SkEdge edge[], const SkPoint pts[],
689 const SkIRect* clipRect, SkEdge* list[]) {
690 SkEdge** start = list;
691
692 if (edge->setLine(pts[0], pts[1], clipRect, 0)) {
693 *list++ = edge;
694 edge = (SkEdge*)((char*)edge + sizeof(SkEdge));
695 }
696 if (edge->setLine(pts[1], pts[2], clipRect, 0)) {
697 *list++ = edge;
698 edge = (SkEdge*)((char*)edge + sizeof(SkEdge));
699 }
700 if (edge->setLine(pts[2], pts[0], clipRect, 0)) {
701 *list++ = edge;
702 }
703 return (int)(list - start);
704 }
705
706
sk_fill_triangle(const SkPoint pts[],const SkIRect * clipRect,SkBlitter * blitter,const SkIRect & ir)707 static void sk_fill_triangle(const SkPoint pts[], const SkIRect* clipRect,
708 SkBlitter* blitter, const SkIRect& ir) {
709 SkASSERT(pts && blitter);
710
711 SkEdge edgeStorage[3];
712 SkEdge* list[3];
713
714 int count = build_tri_edges(edgeStorage, pts, clipRect, list);
715 if (count < 2) {
716 return;
717 }
718
719 SkEdge headEdge, tailEdge, *last;
720
721 // this returns the first and last edge after they're sorted into a dlink list
722 SkEdge* edge = sort_edges(list, count, &last);
723
724 headEdge.fPrev = nullptr;
725 headEdge.fNext = edge;
726 headEdge.fFirstY = kEDGE_HEAD_Y;
727 headEdge.fX = SK_MinS32;
728 edge->fPrev = &headEdge;
729
730 tailEdge.fPrev = last;
731 tailEdge.fNext = nullptr;
732 tailEdge.fFirstY = kEDGE_TAIL_Y;
733 last->fNext = &tailEdge;
734
735 // now edge is the head of the sorted linklist
736 int stop_y = ir.fBottom;
737 if (clipRect && stop_y > clipRect->fBottom) {
738 stop_y = clipRect->fBottom;
739 }
740 int start_y = ir.fTop;
741 if (clipRect && start_y < clipRect->fTop) {
742 start_y = clipRect->fTop;
743 }
744 walk_convex_edges(&headEdge, SkPath::kEvenOdd_FillType, blitter, start_y, stop_y, nullptr);
745 // walk_edges(&headEdge, SkPath::kEvenOdd_FillType, blitter, start_y, stop_y, nullptr);
746 }
747
FillTriangle(const SkPoint pts[],const SkRasterClip & clip,SkBlitter * blitter)748 void SkScan::FillTriangle(const SkPoint pts[], const SkRasterClip& clip,
749 SkBlitter* blitter) {
750 if (clip.isEmpty()) {
751 return;
752 }
753
754 SkRect r;
755 SkIRect ir;
756 r.set(pts, 3);
757 r.round(&ir);
758 if (ir.isEmpty() || !SkIRect::Intersects(ir, clip.getBounds())) {
759 return;
760 }
761
762 SkAAClipBlitterWrapper wrap;
763 const SkRegion* clipRgn;
764 if (clip.isBW()) {
765 clipRgn = &clip.bwRgn();
766 } else {
767 wrap.init(clip, blitter);
768 clipRgn = &wrap.getRgn();
769 blitter = wrap.getBlitter();
770 }
771
772 SkScanClipper clipper(blitter, clipRgn, ir);
773 blitter = clipper.getBlitter();
774 if (blitter) {
775 sk_fill_triangle(pts, clipper.getClipRect(), blitter, ir);
776 }
777 }
778