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 SkDEBUGFAILF("assert(%s)", #cond); \
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 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);
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#include "src/core/SkPathView.h"
395
396// clipRect has not been shifted up
397void sk_fill_path(const SkPathView& 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 SkBasicEdgeBuilder builder(shiftEdgesUp);
408 int count = builder.buildEdges(path, pathContainedInClip ? nullptr : &shiftedClip);
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.fFillType, blitter, start_y, stop_y, proc, shiftedClip.right());
476 }
477}
478
479void sk_blit_above(SkBlitter* blitter, const SkIRect& ir, const SkRegion& clip) {
480 const SkIRect& cr = clip.getBounds();
481 SkIRect tmp;
482
483 tmp.fLeft = cr.fLeft;
484 tmp.fRight = cr.fRight;
485 tmp.fTop = cr.fTop;
486 tmp.fBottom = ir.fTop;
487 if (!tmp.isEmpty()) {
488 blitter->blitRectRegion(tmp, clip);
489 }
490}
491
492void sk_blit_below(SkBlitter* blitter, const SkIRect& ir, const SkRegion& clip) {
493 const SkIRect& cr = clip.getBounds();
494 SkIRect tmp;
495
496 tmp.fLeft = cr.fLeft;
497 tmp.fRight = cr.fRight;
498 tmp.fTop = ir.fBottom;
499 tmp.fBottom = cr.fBottom;
500 if (!tmp.isEmpty()) {
501 blitter->blitRectRegion(tmp, clip);
502 }
503}
504
505///////////////////////////////////////////////////////////////////////////////
506
507/**
508 * If the caller is drawing an inverse-fill path, then it pass true for
509 * skipRejectTest, so we don't abort drawing just because the src bounds (ir)
510 * is outside of the clip.
511 */
512SkScanClipper::SkScanClipper(SkBlitter* blitter, const SkRegion* clip,
513 const SkIRect& ir, bool skipRejectTest, bool irPreClipped) {
514 fBlitter = nullptr; // null means blit nothing
515 fClipRect = nullptr;
516
517 if (clip) {
518 fClipRect = &clip->getBounds();
519 if (!skipRejectTest && !SkIRect::Intersects(*fClipRect, ir)) { // completely clipped out
520 return;
521 }
522
523 if (clip->isRect()) {
524 if (!irPreClipped && fClipRect->contains(ir)) {
525#ifdef SK_DEBUG
526 fRectClipCheckBlitter.init(blitter, *fClipRect);
527 blitter = &fRectClipCheckBlitter;
528#endif
529 fClipRect = nullptr;
530 } else {
531 // only need a wrapper blitter if we're horizontally clipped
532 if (irPreClipped ||
533 fClipRect->fLeft > ir.fLeft || fClipRect->fRight < ir.fRight) {
534 fRectBlitter.init(blitter, *fClipRect);
535 blitter = &fRectBlitter;
536 } else {
537#ifdef SK_DEBUG
538 fRectClipCheckBlitter.init(blitter, *fClipRect);
539 blitter = &fRectClipCheckBlitter;
540#endif
541 }
542 }
543 } else {
544 fRgnBlitter.init(blitter, clip);
545 blitter = &fRgnBlitter;
546 }
547 }
548 fBlitter = blitter;
549}
550
551///////////////////////////////////////////////////////////////////////////////
552
553static bool clip_to_limit(const SkRegion& orig, SkRegion* reduced) {
554 // need to limit coordinates such that the width/height of our rect can be represented
555 // in SkFixed (16.16). See skbug.com/7998
556 const int32_t limit = 32767 >> 1;
557
558 SkIRect limitR;
559 limitR.setLTRB(-limit, -limit, limit, limit);
560 if (limitR.contains(orig.getBounds())) {
561 return false;
562 }
563 reduced->op(orig, limitR, SkRegion::kIntersect_Op);
564 return true;
565}
566
567// Bias used for conservative rounding of float rects to int rects, to nudge the irects a little
568// larger, so we don't "think" a path's bounds are inside a clip, when (due to numeric drift in
569// the scan-converter) we might walk beyond the predicted limits.
570//
571// This value has been determined trial and error: pick the smallest value (after the 0.5) that
572// fixes any problematic cases (e.g. crbug.com/844457)
573// NOTE: cubics appear to be the main reason for needing this slop. If we could (perhaps) have a
574// more accurate walker for cubics, we may be able to reduce this fudge factor.
575static const double kConservativeRoundBias = 0.5 + 1.5 / SK_FDot6One;
576
577/**
578 * Round the value down. This is used to round the top and left of a rectangle,
579 * and corresponds to the way the scan converter treats the top and left edges.
580 * It has a slight bias to make the "rounded" int smaller than a normal round, to create a more
581 * conservative int-bounds (larger) from a float rect.
582 */
583static inline int round_down_to_int(SkScalar x) {
584 double xx = x;
585 xx -= kConservativeRoundBias;
586 return sk_double_saturate2int(ceil(xx));
587}
588
589/**
590 * Round the value up. This is used to round the right and bottom of a rectangle.
591 * It has a slight bias to make the "rounded" int smaller than a normal round, to create a more
592 * conservative int-bounds (larger) from a float rect.
593 */
594static inline int round_up_to_int(SkScalar x) {
595 double xx = x;
596 xx += kConservativeRoundBias;
597 return sk_double_saturate2int(floor(xx));
598}
599
600/*
601 * Conservative rounding function, which effectively nudges the int-rect to be slightly larger
602 * than SkRect::round() might have produced. This is a safety-net for the scan-converter, which
603 * inspects the returned int-rect, and may disable clipping (for speed) if it thinks all of the
604 * edges will fit inside the clip's bounds. The scan-converter introduces slight numeric errors
605 * due to accumulated += of the slope, so this function is used to return a conservatively large
606 * int-bounds, and thus we will only disable clipping if we're sure the edges will stay in-bounds.
607 */
608static SkIRect conservative_round_to_int(const SkRect& src) {
609 return {
610 round_down_to_int(src.fLeft),
611 round_down_to_int(src.fTop),
612 round_up_to_int(src.fRight),
613 round_up_to_int(src.fBottom),
614 };
615}
616
617void SkScan::FillPath(const SkPathView& path, const SkRegion& origClip, 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.fBounds;
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 SkPathView& 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, SkBlitter* blitter) {
741 if (clip.isEmpty()) {
742 return;
743 }
744
745 SkRect r;
746 r.setBounds(pts, 3);
747 // If r is too large (larger than can easily fit in SkFixed) then we need perform geometric
748 // clipping. This is a bit of work, so we just call the general FillPath() to handle it.
749 // Use FixedMax/2 as the limit so we can subtract two edges and still store that in Fixed.
750 const SkScalar limit = SK_MaxS16 >> 1;
751 if (!SkRect::MakeLTRB(-limit, -limit, limit, limit).contains(r)) {
752 FillPath(SkPathView_triangle(pts, r), clip, blitter);
753 return;
754 }
755
756 SkIRect ir = conservative_round_to_int(r);
757 if (ir.isEmpty() || !SkIRect::Intersects(ir, clip.getBounds())) {
758 return;
759 }
760
761 SkAAClipBlitterWrapper wrap;
762 const SkRegion* clipRgn;
763 if (clip.isBW()) {
764 clipRgn = &clip.bwRgn();
765 } else {
766 wrap.init(clip, blitter);
767 clipRgn = &wrap.getRgn();
768 blitter = wrap.getBlitter();
769 }
770
771 SkScanClipper clipper(blitter, clipRgn, ir);
772 blitter = clipper.getBlitter();
773 if (blitter) {
774 sk_fill_triangle(pts, clipper.getClipRect(), blitter, ir);
775 }
776}
777