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