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