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