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/SkPath.h"
9#include "include/core/SkRegion.h"
10#include "include/private/SkMacros.h"
11#include "include/private/SkSafe32.h"
12#include "include/private/SkTemplates.h"
13#include "src/core/SkBlitter.h"
14#include "src/core/SkEdge.h"
15#include "src/core/SkEdgeBuilder.h"
16#include "src/core/SkGeometry.h"
17#include "src/core/SkQuadClipper.h"
18#include "src/core/SkRasterClip.h"
19#include "src/core/SkRectPriv.h"
20#include "src/core/SkScanPriv.h"
21#include "src/core/SkTSort.h"
22
23#include <utility>
24
25#define kEDGE_HEAD_Y SK_MinS32
26#define kEDGE_TAIL_Y SK_MaxS32
27
28#ifdef SK_DEBUG
29 static void validate_sort(const SkEdge* edge) {
30 int y = kEDGE_HEAD_Y;
31
32 while (edge->fFirstY != SK_MaxS32) {
33 edge->validate();
34 SkASSERT(y <= edge->fFirstY);
35
36 y = edge->fFirstY;
37 edge = edge->fNext;
38 }
39 }
40#else
41 #define validate_sort(edge)
42#endif
43
44static void insert_new_edges(SkEdge* newEdge, int curr_y) {
45 if (newEdge->fFirstY != curr_y) {
46 return;
47 }
48 SkEdge* prev = newEdge->fPrev;
49 if (prev->fX <= newEdge->fX) {
50 return;
51 }
52 // find first x pos to insert
53 SkEdge* start = backward_insert_start(prev, newEdge->fX);
54 // insert the lot, fixing up the links as we go
55 do {
56 SkEdge* next = newEdge->fNext;
57 do {
58 if (start->fNext == newEdge) {
59 goto nextEdge;
60 }
61 SkEdge* after = start->fNext;
62 if (after->fX >= newEdge->fX) {
63 break;
64 }
65 start = after;
66 } while (true);
67 remove_edge(newEdge);
68 insert_edge_after(newEdge, start);
69nextEdge:
70 start = newEdge;
71 newEdge = next;
72 } while (newEdge->fFirstY == curr_y);
73}
74
75#ifdef SK_DEBUG
76static void validate_edges_for_y(const SkEdge* edge, int curr_y) {
77 while (edge->fFirstY <= curr_y) {
78 SkASSERT(edge->fPrev && edge->fNext);
79 SkASSERT(edge->fPrev->fNext == edge);
80 SkASSERT(edge->fNext->fPrev == edge);
81 SkASSERT(edge->fFirstY <= edge->fLastY);
82
83 SkASSERT(edge->fPrev->fX <= edge->fX);
84 edge = edge->fNext;
85 }
86}
87#else
88 #define validate_edges_for_y(edge, curr_y)
89#endif
90
91#if defined _WIN32 // disable warning : local variable used without having been initialized
92#pragma warning ( push )
93#pragma warning ( disable : 4701 )
94#endif
95
96typedef void (*PrePostProc)(SkBlitter* blitter, int y, bool isStartOfScanline);
97#define PREPOST_START true
98#define PREPOST_END false
99
100static void walk_edges(SkEdge* prevHead, SkPathFillType fillType,
101 SkBlitter* blitter, int start_y, int stop_y,
102 PrePostProc proc, int rightClip) {
103 validate_sort(prevHead->fNext);
104
105 int curr_y = start_y;
106 int windingMask = SkPathFillType_IsEvenOdd(fillType) ? 1 : -1;
107
108 for (;;) {
109 int w = 0;
110 int left SK_INIT_TO_AVOID_WARNING;
111 SkEdge* currE = prevHead->fNext;
112 SkFixed prevX = prevHead->fX;
113
114 validate_edges_for_y(currE, curr_y);
115
116 if (proc) {
117 proc(blitter, curr_y, PREPOST_START); // pre-proc
118 }
119
120 while (currE->fFirstY <= curr_y) {
121 SkASSERT(currE->fLastY >= curr_y);
122
123 int x = SkFixedRoundToInt(currE->fX);
124
125 if ((w & windingMask) == 0) { // we're starting interval
126 left = x;
127 }
128
129 w += currE->fWinding;
130
131 if ((w & windingMask) == 0) { // we finished an interval
132 int width = x - left;
133 SkASSERT(width >= 0);
134 if (width > 0) {
135 blitter->blitH(left, curr_y, width);
136 }
137 }
138
139 SkEdge* next = currE->fNext;
140 SkFixed newX;
141
142 if (currE->fLastY == curr_y) { // are we done with this edge?
143 if (currE->fCurveCount > 0) {
144 if (((SkQuadraticEdge*)currE)->updateQuadratic()) {
145 newX = currE->fX;
146 goto NEXT_X;
147 }
148 } else if (currE->fCurveCount < 0) {
149 if (((SkCubicEdge*)currE)->updateCubic()) {
150 SkASSERT(currE->fFirstY == curr_y + 1);
151
152 newX = currE->fX;
153 goto NEXT_X;
154 }
155 }
156 remove_edge(currE);
157 } else {
158 SkASSERT(currE->fLastY > curr_y);
159 newX = currE->fX + currE->fDX;
160 currE->fX = newX;
161 NEXT_X:
162 if (newX < prevX) { // ripple currE backwards until it is x-sorted
163 backward_insert_edge_based_on_x(currE);
164 } else {
165 prevX = newX;
166 }
167 }
168 currE = next;
169 SkASSERT(currE);
170 }
171
172 if ((w & windingMask) != 0) { // was our right-edge culled away?
173 int width = rightClip - left;
174 if (width > 0) {
175 blitter->blitH(left, curr_y, width);
176 }
177 }
178
179 if (proc) {
180 proc(blitter, curr_y, PREPOST_END); // post-proc
181 }
182
183 curr_y += 1;
184 if (curr_y >= stop_y) {
185 break;
186 }
187 // now currE points to the first edge with a Yint larger than curr_y
188 insert_new_edges(currE, curr_y);
189 }
190}
191
192// return true if we're NOT done with this edge
193static bool update_edge(SkEdge* edge, int last_y) {
194 SkASSERT(edge->fLastY >= last_y);
195 if (last_y == edge->fLastY) {
196 if (edge->fCurveCount < 0) {
197 if (((SkCubicEdge*)edge)->updateCubic()) {
198 SkASSERT(edge->fFirstY == last_y + 1);
199 return true;
200 }
201 } else if (edge->fCurveCount > 0) {
202 if (((SkQuadraticEdge*)edge)->updateQuadratic()) {
203 SkASSERT(edge->fFirstY == last_y + 1);
204 return true;
205 }
206 }
207 return false;
208 }
209 return true;
210}
211
212// Unexpected conditions for which we need to return
213#define ASSERT_RETURN(cond) \
214 do { \
215 if (!(cond)) { \
216 SkASSERT(false); \
217 return; \
218 } \
219 } while (0)
220
221// Needs Y to only change once (looser than convex in X)
222static void walk_simple_edges(SkEdge* prevHead, SkBlitter* blitter, int start_y, int stop_y) {
223 validate_sort(prevHead->fNext);
224
225 SkEdge* leftE = prevHead->fNext;
226 SkEdge* riteE = leftE->fNext;
227 SkEdge* currE = riteE->fNext;
228
229 // our edge choppers for curves can result in the initial edges
230 // not lining up, so we take the max.
231 int local_top = std::max(leftE->fFirstY, riteE->fFirstY);
232 ASSERT_RETURN(local_top >= start_y);
233
234 while (local_top < stop_y) {
235 SkASSERT(leftE->fFirstY <= stop_y);
236 SkASSERT(riteE->fFirstY <= stop_y);
237
238 int local_bot = std::min(leftE->fLastY, riteE->fLastY);
239 local_bot = std::min(local_bot, stop_y - 1);
240 ASSERT_RETURN(local_top <= local_bot);
241
242 SkFixed left = leftE->fX;
243 SkFixed dLeft = leftE->fDX;
244 SkFixed rite = riteE->fX;
245 SkFixed dRite = riteE->fDX;
246 int count = local_bot - local_top;
247 ASSERT_RETURN(count >= 0);
248
249 if (0 == (dLeft | dRite)) {
250 int L = SkFixedRoundToInt(left);
251 int R = SkFixedRoundToInt(rite);
252 if (L > R) {
253 std::swap(L, R);
254 }
255 if (L < R) {
256 count += 1;
257 blitter->blitRect(L, local_top, R - L, count);
258 }
259 local_top = local_bot + 1;
260 } else {
261 do {
262 int L = SkFixedRoundToInt(left);
263 int R = SkFixedRoundToInt(rite);
264 if (L > R) {
265 std::swap(L, R);
266 }
267 if (L < R) {
268 blitter->blitH(L, local_top, R - L);
269 }
270 // Either/both of these might overflow, since we perform this step even if
271 // (later) we determine that we are done with the edge, and so the computed
272 // left or rite edge will not be used (see update_edge). Use this helper to
273 // silence UBSAN when we perform the add.
274 left = Sk32_can_overflow_add(left, dLeft);
275 rite = Sk32_can_overflow_add(rite, dRite);
276 local_top += 1;
277 } while (--count >= 0);
278 }
279
280 leftE->fX = left;
281 riteE->fX = rite;
282
283 if (!update_edge(leftE, local_bot)) {
284 if (currE->fFirstY >= stop_y) {
285 return; // we're done
286 }
287 leftE = currE;
288 currE = currE->fNext;
289 ASSERT_RETURN(leftE->fFirstY == local_top);
290 }
291 if (!update_edge(riteE, local_bot)) {
292 if (currE->fFirstY >= stop_y) {
293 return; // we're done
294 }
295 riteE = currE;
296 currE = currE->fNext;
297 ASSERT_RETURN(riteE->fFirstY == local_top);
298 }
299 }
300}
301
302///////////////////////////////////////////////////////////////////////////////
303
304// this guy overrides blitH, and will call its proxy blitter with the inverse
305// of the spans it is given (clipped to the left/right of the cliprect)
306//
307// used to implement inverse filltypes on paths
308//
309class InverseBlitter : public SkBlitter {
310public:
311 void setBlitter(SkBlitter* blitter, const SkIRect& clip, int shift) {
312 fBlitter = blitter;
313 fFirstX = clip.fLeft << shift;
314 fLastX = clip.fRight << shift;
315 }
316 void prepost(int y, bool isStart) {
317 if (isStart) {
318 fPrevX = fFirstX;
319 } else {
320 int invWidth = fLastX - fPrevX;
321 if (invWidth > 0) {
322 fBlitter->blitH(fPrevX, y, invWidth);
323 }
324 }
325 }
326
327 // overrides
328 void blitH(int x, int y, int width) override {
329 int invWidth = x - fPrevX;
330 if (invWidth > 0) {
331 fBlitter->blitH(fPrevX, y, invWidth);
332 }
333 fPrevX = x + width;
334 }
335
336 // we do not expect to get called with these entrypoints
337 void blitAntiH(int, int, const SkAlpha[], const int16_t runs[]) override {
338 SkDEBUGFAIL("blitAntiH unexpected");
339 }
340 void blitV(int x, int y, int height, SkAlpha alpha) override {
341 SkDEBUGFAIL("blitV unexpected");
342 }
343 void blitRect(int x, int y, int width, int height) override {
344 SkDEBUGFAIL("blitRect unexpected");
345 }
346 void blitMask(const SkMask&, const SkIRect& clip) override {
347 SkDEBUGFAIL("blitMask unexpected");
348 }
349 const SkPixmap* justAnOpaqueColor(uint32_t* value) override {
350 SkDEBUGFAIL("justAnOpaqueColor unexpected");
351 return nullptr;
352 }
353
354private:
355 SkBlitter* fBlitter;
356 int fFirstX, fLastX, fPrevX;
357};
358
359static void PrePostInverseBlitterProc(SkBlitter* blitter, int y, bool isStart) {
360 ((InverseBlitter*)blitter)->prepost(y, isStart);
361}
362
363///////////////////////////////////////////////////////////////////////////////
364
365#if defined _WIN32
366#pragma warning ( pop )
367#endif
368
369static bool operator<(const SkEdge& a, const SkEdge& b) {
370 int valuea = a.fFirstY;
371 int valueb = b.fFirstY;
372
373 if (valuea == valueb) {
374 valuea = a.fX;
375 valueb = b.fX;
376 }
377
378 return valuea < valueb;
379}
380
381static SkEdge* sort_edges(SkEdge* list[], int count, SkEdge** last) {
382 SkTQSort(list, list + count - 1);
383
384 // now make the edges linked in sorted order
385 for (int i = 1; i < count; i++) {
386 list[i - 1]->fNext = list[i];
387 list[i]->fPrev = list[i - 1];
388 }
389
390 *last = list[count - 1];
391 return list[0];
392}
393
394// clipRect has not been shifted up
395void sk_fill_path(const SkPath& path, const SkIRect& clipRect, SkBlitter* blitter,
396 int start_y, int stop_y, int shiftEdgesUp, bool pathContainedInClip) {
397 SkASSERT(blitter);
398
399 SkIRect shiftedClip = clipRect;
400 shiftedClip.fLeft = SkLeftShift(shiftedClip.fLeft, shiftEdgesUp);
401 shiftedClip.fRight = SkLeftShift(shiftedClip.fRight, shiftEdgesUp);
402 shiftedClip.fTop = SkLeftShift(shiftedClip.fTop, shiftEdgesUp);
403 shiftedClip.fBottom = SkLeftShift(shiftedClip.fBottom, shiftEdgesUp);
404
405 SkBasicEdgeBuilder builder(shiftEdgesUp);
406 int count = builder.buildEdges(path, pathContainedInClip ? nullptr : &shiftedClip);
407 SkEdge** list = builder.edgeList();
408
409 if (0 == count) {
410 if (path.isInverseFillType()) {
411 /*
412 * Since we are in inverse-fill, our caller has already drawn above
413 * our top (start_y) and will draw below our bottom (stop_y). Thus
414 * we need to restrict our drawing to the intersection of the clip
415 * and those two limits.
416 */
417 SkIRect rect = clipRect;
418 if (rect.fTop < start_y) {
419 rect.fTop = start_y;
420 }
421 if (rect.fBottom > stop_y) {
422 rect.fBottom = stop_y;
423 }
424 if (!rect.isEmpty()) {
425 blitter->blitRect(rect.fLeft << shiftEdgesUp,
426 rect.fTop << shiftEdgesUp,
427 rect.width() << shiftEdgesUp,
428 rect.height() << shiftEdgesUp);
429 }
430 }
431 return;
432 }
433
434 SkEdge headEdge, tailEdge, *last;
435 // this returns the first and last edge after they're sorted into a dlink list
436 SkEdge* edge = sort_edges(list, count, &last);
437
438 headEdge.fPrev = nullptr;
439 headEdge.fNext = edge;
440 headEdge.fFirstY = kEDGE_HEAD_Y;
441 headEdge.fX = SK_MinS32;
442 edge->fPrev = &headEdge;
443
444 tailEdge.fPrev = last;
445 tailEdge.fNext = nullptr;
446 tailEdge.fFirstY = kEDGE_TAIL_Y;
447 last->fNext = &tailEdge;
448
449 // now edge is the head of the sorted linklist
450
451 start_y = SkLeftShift(start_y, shiftEdgesUp);
452 stop_y = SkLeftShift(stop_y, shiftEdgesUp);
453 if (!pathContainedInClip && start_y < shiftedClip.fTop) {
454 start_y = shiftedClip.fTop;
455 }
456 if (!pathContainedInClip && stop_y > shiftedClip.fBottom) {
457 stop_y = shiftedClip.fBottom;
458 }
459
460 InverseBlitter ib;
461 PrePostProc proc = nullptr;
462
463 if (path.isInverseFillType()) {
464 ib.setBlitter(blitter, clipRect, shiftEdgesUp);
465 blitter = &ib;
466 proc = PrePostInverseBlitterProc;
467 }
468
469 // count >= 2 is required as the convex walker does not handle missing right edges
470 if (path.isConvex() && (nullptr == proc) && count >= 2) {
471 walk_simple_edges(&headEdge, blitter, start_y, stop_y);
472 } else {
473 walk_edges(&headEdge, path.getFillType(), blitter, start_y, stop_y, proc,
474 shiftedClip.right());
475 }
476}
477
478void sk_blit_above(SkBlitter* blitter, const SkIRect& ir, const SkRegion& clip) {
479 const SkIRect& cr = clip.getBounds();
480 SkIRect tmp;
481
482 tmp.fLeft = cr.fLeft;
483 tmp.fRight = cr.fRight;
484 tmp.fTop = cr.fTop;
485 tmp.fBottom = ir.fTop;
486 if (!tmp.isEmpty()) {
487 blitter->blitRectRegion(tmp, clip);
488 }
489}
490
491void sk_blit_below(SkBlitter* blitter, const SkIRect& ir, const SkRegion& clip) {
492 const SkIRect& cr = clip.getBounds();
493 SkIRect tmp;
494
495 tmp.fLeft = cr.fLeft;
496 tmp.fRight = cr.fRight;
497 tmp.fTop = ir.fBottom;
498 tmp.fBottom = cr.fBottom;
499 if (!tmp.isEmpty()) {
500 blitter->blitRectRegion(tmp, clip);
501 }
502}
503
504///////////////////////////////////////////////////////////////////////////////
505
506/**
507 * If the caller is drawing an inverse-fill path, then it pass true for
508 * skipRejectTest, so we don't abort drawing just because the src bounds (ir)
509 * is outside of the clip.
510 */
511SkScanClipper::SkScanClipper(SkBlitter* blitter, const SkRegion* clip,
512 const SkIRect& ir, bool skipRejectTest, bool irPreClipped) {
513 fBlitter = nullptr; // null means blit nothing
514 fClipRect = nullptr;
515
516 if (clip) {
517 fClipRect = &clip->getBounds();
518 if (!skipRejectTest && !SkIRect::Intersects(*fClipRect, ir)) { // completely clipped out
519 return;
520 }
521
522 if (clip->isRect()) {
523 if (!irPreClipped && fClipRect->contains(ir)) {
524#ifdef SK_DEBUG
525 fRectClipCheckBlitter.init(blitter, *fClipRect);
526 blitter = &fRectClipCheckBlitter;
527#endif
528 fClipRect = nullptr;
529 } else {
530 // only need a wrapper blitter if we're horizontally clipped
531 if (irPreClipped ||
532 fClipRect->fLeft > ir.fLeft || fClipRect->fRight < ir.fRight) {
533 fRectBlitter.init(blitter, *fClipRect);
534 blitter = &fRectBlitter;
535 } else {
536#ifdef SK_DEBUG
537 fRectClipCheckBlitter.init(blitter, *fClipRect);
538 blitter = &fRectClipCheckBlitter;
539#endif
540 }
541 }
542 } else {
543 fRgnBlitter.init(blitter, clip);
544 blitter = &fRgnBlitter;
545 }
546 }
547 fBlitter = blitter;
548}
549
550///////////////////////////////////////////////////////////////////////////////
551
552static bool clip_to_limit(const SkRegion& orig, SkRegion* reduced) {
553 // need to limit coordinates such that the width/height of our rect can be represented
554 // in SkFixed (16.16). See skbug.com/7998
555 const int32_t limit = 32767 >> 1;
556
557 SkIRect limitR;
558 limitR.setLTRB(-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.
574static 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 */
582static 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 */
593static 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 */
607static 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
616void 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
673void SkScan::FillPath(const SkPath& path, const SkIRect& ir,
674 SkBlitter* blitter) {
675 SkRegion rgn(ir);
676 FillPath(path, rgn, blitter);
677}
678
679///////////////////////////////////////////////////////////////////////////////
680
681static 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
700static 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
740void SkScan::FillTriangle(const SkPoint pts[], const SkRasterClip& clip,
741 SkBlitter* blitter) {
742 if (clip.isEmpty()) {
743 return;
744 }
745
746 SkRect r;
747 r.setBounds(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 = conservative_round_to_int(r);
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