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