blob: 4271f4e4b4e856787545b92ad3cbd99d4d6f55a6 [file] [log] [blame]
David Ghandehari9e5b5872016-07-28 09:50:04 -07001/*
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
Xiaoming Shi73dfa202020-03-12 11:31:35 -07008#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>
David Ghandehari9e5b5872016-07-28 09:50:04 -070024
David Ghandehari9e5b5872016-07-28 09:50:04 -070025#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
David Ghandehari9e5b5872016-07-28 09:50:04 -070044static void insert_new_edges(SkEdge* newEdge, int curr_y) {
Andrew Top200ce4b2018-01-29 13:43:50 -080045 if (newEdge->fFirstY != curr_y) {
46 return;
David Ghandehari9e5b5872016-07-28 09:50:04 -070047 }
Andrew Top200ce4b2018-01-29 13:43:50 -080048 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);
David Ghandehari9e5b5872016-07-28 09:50:04 -070073}
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
Andrew Top200ce4b2018-01-29 13:43:50 -080091#if defined _WIN32 // disable warning : local variable used without having been initialized
David Ghandehari9e5b5872016-07-28 09:50:04 -070092#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, SkPath::FillType fillType,
101 SkBlitter* blitter, int start_y, int stop_y,
Andrew Top200ce4b2018-01-29 13:43:50 -0800102 PrePostProc proc, int rightClip) {
David Ghandehari9e5b5872016-07-28 09:50:04 -0700103 validate_sort(prevHead->fNext);
104
105 int curr_y = start_y;
106 // returns 1 for evenodd, -1 for winding, regardless of inverse-ness
107 int windingMask = (fillType & 1) ? 1 : -1;
108
109 for (;;) {
110 int w = 0;
111 int left SK_INIT_TO_AVOID_WARNING;
David Ghandehari9e5b5872016-07-28 09:50:04 -0700112 SkEdge* currE = prevHead->fNext;
113 SkFixed prevX = prevHead->fX;
114
115 validate_edges_for_y(currE, curr_y);
116
117 if (proc) {
118 proc(blitter, curr_y, PREPOST_START); // pre-proc
119 }
120
121 while (currE->fFirstY <= curr_y) {
122 SkASSERT(currE->fLastY >= curr_y);
123
124 int x = SkFixedRoundToInt(currE->fX);
Xiaoming Shi73dfa202020-03-12 11:31:35 -0700125
126 if ((w & windingMask) == 0) { // we're starting interval
127 left = x;
128 }
129
David Ghandehari9e5b5872016-07-28 09:50:04 -0700130 w += currE->fWinding;
Xiaoming Shi73dfa202020-03-12 11:31:35 -0700131
David Ghandehari9e5b5872016-07-28 09:50:04 -0700132 if ((w & windingMask) == 0) { // we finished an interval
David Ghandehari9e5b5872016-07-28 09:50:04 -0700133 int width = x - left;
134 SkASSERT(width >= 0);
Xiaoming Shi73dfa202020-03-12 11:31:35 -0700135 if (width > 0) {
David Ghandehari9e5b5872016-07-28 09:50:04 -0700136 blitter->blitH(left, curr_y, width);
Xiaoming Shi73dfa202020-03-12 11:31:35 -0700137 }
David Ghandehari9e5b5872016-07-28 09:50:04 -0700138 }
139
140 SkEdge* next = currE->fNext;
141 SkFixed newX;
142
143 if (currE->fLastY == curr_y) { // are we done with this edge?
Xiaoming Shi73dfa202020-03-12 11:31:35 -0700144 if (currE->fCurveCount > 0) {
145 if (((SkQuadraticEdge*)currE)->updateQuadratic()) {
David Ghandehari9e5b5872016-07-28 09:50:04 -0700146 newX = currE->fX;
147 goto NEXT_X;
148 }
Xiaoming Shi73dfa202020-03-12 11:31:35 -0700149 } else if (currE->fCurveCount < 0) {
150 if (((SkCubicEdge*)currE)->updateCubic()) {
151 SkASSERT(currE->fFirstY == curr_y + 1);
152
David Ghandehari9e5b5872016-07-28 09:50:04 -0700153 newX = currE->fX;
154 goto NEXT_X;
155 }
156 }
157 remove_edge(currE);
158 } else {
159 SkASSERT(currE->fLastY > curr_y);
160 newX = currE->fX + currE->fDX;
161 currE->fX = newX;
162 NEXT_X:
163 if (newX < prevX) { // ripple currE backwards until it is x-sorted
Andrew Top200ce4b2018-01-29 13:43:50 -0800164 backward_insert_edge_based_on_x(currE);
David Ghandehari9e5b5872016-07-28 09:50:04 -0700165 } else {
166 prevX = newX;
167 }
168 }
169 currE = next;
170 SkASSERT(currE);
171 }
172
Xiaoming Shi73dfa202020-03-12 11:31:35 -0700173 if ((w & windingMask) != 0) { // was our right-edge culled away?
Andrew Top200ce4b2018-01-29 13:43:50 -0800174 int width = rightClip - left;
175 if (width > 0) {
176 blitter->blitH(left, curr_y, width);
177 }
178 }
179
David Ghandehari9e5b5872016-07-28 09:50:04 -0700180 if (proc) {
181 proc(blitter, curr_y, PREPOST_END); // post-proc
182 }
183
184 curr_y += 1;
185 if (curr_y >= stop_y) {
186 break;
187 }
188 // now currE points to the first edge with a Yint larger than curr_y
189 insert_new_edges(currE, curr_y);
190 }
191}
192
Xiaoming Shi73dfa202020-03-12 11:31:35 -0700193// return true if we're NOT done with this edge
David Ghandehari9e5b5872016-07-28 09:50:04 -0700194static bool update_edge(SkEdge* edge, int last_y) {
195 SkASSERT(edge->fLastY >= last_y);
196 if (last_y == edge->fLastY) {
197 if (edge->fCurveCount < 0) {
198 if (((SkCubicEdge*)edge)->updateCubic()) {
199 SkASSERT(edge->fFirstY == last_y + 1);
Xiaoming Shi73dfa202020-03-12 11:31:35 -0700200 return true;
David Ghandehari9e5b5872016-07-28 09:50:04 -0700201 }
202 } else if (edge->fCurveCount > 0) {
203 if (((SkQuadraticEdge*)edge)->updateQuadratic()) {
204 SkASSERT(edge->fFirstY == last_y + 1);
Xiaoming Shi73dfa202020-03-12 11:31:35 -0700205 return true;
David Ghandehari9e5b5872016-07-28 09:50:04 -0700206 }
207 }
Xiaoming Shi73dfa202020-03-12 11:31:35 -0700208 return false;
David Ghandehari9e5b5872016-07-28 09:50:04 -0700209 }
Xiaoming Shi73dfa202020-03-12 11:31:35 -0700210 return true;
David Ghandehari9e5b5872016-07-28 09:50:04 -0700211}
212
Xiaoming Shi73dfa202020-03-12 11:31:35 -0700213// Unexpected conditions for which we need to return
214#define ASSERT_RETURN(cond) \
215 do { \
216 if (!(cond)) { \
217 SkASSERT(false); \
218 return; \
219 } \
220 } while (0)
221
222// Needs Y to only change once (looser than convex in X)
223static void walk_simple_edges(SkEdge* prevHead, SkBlitter* blitter, int start_y, int stop_y) {
David Ghandehari9e5b5872016-07-28 09:50:04 -0700224 validate_sort(prevHead->fNext);
225
226 SkEdge* leftE = prevHead->fNext;
227 SkEdge* riteE = leftE->fNext;
228 SkEdge* currE = riteE->fNext;
229
David Ghandehari9e5b5872016-07-28 09:50:04 -0700230 // our edge choppers for curves can result in the initial edges
231 // not lining up, so we take the max.
232 int local_top = SkMax32(leftE->fFirstY, riteE->fFirstY);
Xiaoming Shi73dfa202020-03-12 11:31:35 -0700233 ASSERT_RETURN(local_top >= start_y);
David Ghandehari9e5b5872016-07-28 09:50:04 -0700234
Xiaoming Shi73dfa202020-03-12 11:31:35 -0700235 while (local_top < stop_y) {
David Ghandehari9e5b5872016-07-28 09:50:04 -0700236 SkASSERT(leftE->fFirstY <= stop_y);
237 SkASSERT(riteE->fFirstY <= stop_y);
238
David Ghandehari9e5b5872016-07-28 09:50:04 -0700239 int local_bot = SkMin32(leftE->fLastY, riteE->fLastY);
240 local_bot = SkMin32(local_bot, stop_y - 1);
Xiaoming Shi73dfa202020-03-12 11:31:35 -0700241 ASSERT_RETURN(local_top <= local_bot);
David Ghandehari9e5b5872016-07-28 09:50:04 -0700242
243 SkFixed left = leftE->fX;
244 SkFixed dLeft = leftE->fDX;
245 SkFixed rite = riteE->fX;
246 SkFixed dRite = riteE->fDX;
247 int count = local_bot - local_top;
Xiaoming Shi73dfa202020-03-12 11:31:35 -0700248 ASSERT_RETURN(count >= 0);
249
David Ghandehari9e5b5872016-07-28 09:50:04 -0700250 if (0 == (dLeft | dRite)) {
251 int L = SkFixedRoundToInt(left);
252 int R = SkFixedRoundToInt(rite);
Xiaoming Shi73dfa202020-03-12 11:31:35 -0700253 if (L > R) {
254 std::swap(L, R);
255 }
David Ghandehari9e5b5872016-07-28 09:50:04 -0700256 if (L < R) {
257 count += 1;
258 blitter->blitRect(L, local_top, R - L, count);
David Ghandehari9e5b5872016-07-28 09:50:04 -0700259 }
260 local_top = local_bot + 1;
261 } else {
262 do {
263 int L = SkFixedRoundToInt(left);
264 int R = SkFixedRoundToInt(rite);
Xiaoming Shi73dfa202020-03-12 11:31:35 -0700265 if (L > R) {
266 std::swap(L, R);
267 }
David Ghandehari9e5b5872016-07-28 09:50:04 -0700268 if (L < R) {
269 blitter->blitH(L, local_top, R - L);
270 }
Xiaoming Shi73dfa202020-03-12 11:31:35 -0700271 // Either/both of these might overflow, since we perform this step even if
272 // (later) we determine that we are done with the edge, and so the computed
273 // left or rite edge will not be used (see update_edge). Use this helper to
274 // silence UBSAN when we perform the add.
275 left = Sk32_can_overflow_add(left, dLeft);
276 rite = Sk32_can_overflow_add(rite, dRite);
David Ghandehari9e5b5872016-07-28 09:50:04 -0700277 local_top += 1;
278 } while (--count >= 0);
279 }
280
281 leftE->fX = left;
282 riteE->fX = rite;
283
Xiaoming Shi73dfa202020-03-12 11:31:35 -0700284 if (!update_edge(leftE, local_bot)) {
David Ghandehari9e5b5872016-07-28 09:50:04 -0700285 if (currE->fFirstY >= stop_y) {
Xiaoming Shi73dfa202020-03-12 11:31:35 -0700286 return; // we're done
David Ghandehari9e5b5872016-07-28 09:50:04 -0700287 }
288 leftE = currE;
289 currE = currE->fNext;
Xiaoming Shi73dfa202020-03-12 11:31:35 -0700290 ASSERT_RETURN(leftE->fFirstY == local_top);
David Ghandehari9e5b5872016-07-28 09:50:04 -0700291 }
Xiaoming Shi73dfa202020-03-12 11:31:35 -0700292 if (!update_edge(riteE, local_bot)) {
David Ghandehari9e5b5872016-07-28 09:50:04 -0700293 if (currE->fFirstY >= stop_y) {
Xiaoming Shi73dfa202020-03-12 11:31:35 -0700294 return; // we're done
David Ghandehari9e5b5872016-07-28 09:50:04 -0700295 }
296 riteE = currE;
297 currE = currE->fNext;
Xiaoming Shi73dfa202020-03-12 11:31:35 -0700298 ASSERT_RETURN(riteE->fFirstY == local_top);
David Ghandehari9e5b5872016-07-28 09:50:04 -0700299 }
300 }
301}
302
303///////////////////////////////////////////////////////////////////////////////
304
305// this guy overrides blitH, and will call its proxy blitter with the inverse
306// of the spans it is given (clipped to the left/right of the cliprect)
307//
308// used to implement inverse filltypes on paths
309//
310class InverseBlitter : public SkBlitter {
311public:
312 void setBlitter(SkBlitter* blitter, const SkIRect& clip, int shift) {
313 fBlitter = blitter;
314 fFirstX = clip.fLeft << shift;
315 fLastX = clip.fRight << shift;
316 }
317 void prepost(int y, bool isStart) {
318 if (isStart) {
319 fPrevX = fFirstX;
320 } else {
321 int invWidth = fLastX - fPrevX;
322 if (invWidth > 0) {
323 fBlitter->blitH(fPrevX, y, invWidth);
324 }
325 }
326 }
327
328 // overrides
Andrew Top200ce4b2018-01-29 13:43:50 -0800329 void blitH(int x, int y, int width) override {
David Ghandehari9e5b5872016-07-28 09:50:04 -0700330 int invWidth = x - fPrevX;
331 if (invWidth > 0) {
332 fBlitter->blitH(fPrevX, y, invWidth);
333 }
334 fPrevX = x + width;
335 }
336
337 // we do not expect to get called with these entrypoints
Andrew Top200ce4b2018-01-29 13:43:50 -0800338 void blitAntiH(int, int, const SkAlpha[], const int16_t runs[]) override {
David Ghandehari9e5b5872016-07-28 09:50:04 -0700339 SkDEBUGFAIL("blitAntiH unexpected");
340 }
Andrew Top200ce4b2018-01-29 13:43:50 -0800341 void blitV(int x, int y, int height, SkAlpha alpha) override {
David Ghandehari9e5b5872016-07-28 09:50:04 -0700342 SkDEBUGFAIL("blitV unexpected");
343 }
Andrew Top200ce4b2018-01-29 13:43:50 -0800344 void blitRect(int x, int y, int width, int height) override {
David Ghandehari9e5b5872016-07-28 09:50:04 -0700345 SkDEBUGFAIL("blitRect unexpected");
346 }
Andrew Top200ce4b2018-01-29 13:43:50 -0800347 void blitMask(const SkMask&, const SkIRect& clip) override {
David Ghandehari9e5b5872016-07-28 09:50:04 -0700348 SkDEBUGFAIL("blitMask unexpected");
349 }
Andrew Top200ce4b2018-01-29 13:43:50 -0800350 const SkPixmap* justAnOpaqueColor(uint32_t* value) override {
David Ghandehari9e5b5872016-07-28 09:50:04 -0700351 SkDEBUGFAIL("justAnOpaqueColor unexpected");
Andrew Top200ce4b2018-01-29 13:43:50 -0800352 return nullptr;
David Ghandehari9e5b5872016-07-28 09:50:04 -0700353 }
354
355private:
356 SkBlitter* fBlitter;
357 int fFirstX, fLastX, fPrevX;
358};
359
360static void PrePostInverseBlitterProc(SkBlitter* blitter, int y, bool isStart) {
361 ((InverseBlitter*)blitter)->prepost(y, isStart);
362}
363
364///////////////////////////////////////////////////////////////////////////////
365
Andrew Top200ce4b2018-01-29 13:43:50 -0800366#if defined _WIN32
David Ghandehari9e5b5872016-07-28 09:50:04 -0700367#pragma warning ( pop )
368#endif
369
David Ghandehari9e5b5872016-07-28 09:50:04 -0700370static bool operator<(const SkEdge& a, const SkEdge& b) {
371 int valuea = a.fFirstY;
372 int valueb = b.fFirstY;
373
374 if (valuea == valueb) {
375 valuea = a.fX;
376 valueb = b.fX;
377 }
378
379 return valuea < valueb;
380}
David Ghandehari9e5b5872016-07-28 09:50:04 -0700381
382static SkEdge* sort_edges(SkEdge* list[], int count, SkEdge** last) {
David Ghandehari9e5b5872016-07-28 09:50:04 -0700383 SkTQSort(list, list + count - 1);
David Ghandehari9e5b5872016-07-28 09:50:04 -0700384
385 // now make the edges linked in sorted order
386 for (int i = 1; i < count; i++) {
387 list[i - 1]->fNext = list[i];
388 list[i]->fPrev = list[i - 1];
389 }
390
391 *last = list[count - 1];
392 return list[0];
393}
394
Andrew Top200ce4b2018-01-29 13:43:50 -0800395// clipRect has not been shifted up
396void sk_fill_path(const SkPath& path, const SkIRect& clipRect, SkBlitter* blitter,
397 int start_y, int stop_y, int shiftEdgesUp, bool pathContainedInClip) {
David Ghandehari9e5b5872016-07-28 09:50:04 -0700398 SkASSERT(blitter);
399
Andrew Top200ce4b2018-01-29 13:43:50 -0800400 SkIRect shiftedClip = clipRect;
Xiaoming Shi73dfa202020-03-12 11:31:35 -0700401 shiftedClip.fLeft = SkLeftShift(shiftedClip.fLeft, shiftEdgesUp);
402 shiftedClip.fRight = SkLeftShift(shiftedClip.fRight, shiftEdgesUp);
403 shiftedClip.fTop = SkLeftShift(shiftedClip.fTop, shiftEdgesUp);
404 shiftedClip.fBottom = SkLeftShift(shiftedClip.fBottom, shiftEdgesUp);
David Ghandehari9e5b5872016-07-28 09:50:04 -0700405
Xiaoming Shi73dfa202020-03-12 11:31:35 -0700406 SkBasicEdgeBuilder builder(shiftEdgesUp);
407 int count = builder.buildEdges(path, pathContainedInClip ? nullptr : &shiftedClip);
Andrew Top200ce4b2018-01-29 13:43:50 -0800408 SkEdge** list = builder.edgeList();
David Ghandehari9e5b5872016-07-28 09:50:04 -0700409
Andrew Top200ce4b2018-01-29 13:43:50 -0800410 if (0 == count) {
David Ghandehari9e5b5872016-07-28 09:50:04 -0700411 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 */
Andrew Top200ce4b2018-01-29 13:43:50 -0800418 SkIRect rect = clipRect;
David Ghandehari9e5b5872016-07-28 09:50:04 -0700419 if (rect.fTop < start_y) {
420 rect.fTop = start_y;
421 }
422 if (rect.fBottom > stop_y) {
423 rect.fBottom = stop_y;
424 }
425 if (!rect.isEmpty()) {
426 blitter->blitRect(rect.fLeft << shiftEdgesUp,
427 rect.fTop << shiftEdgesUp,
428 rect.width() << shiftEdgesUp,
429 rect.height() << shiftEdgesUp);
430 }
431 }
David Ghandehari9e5b5872016-07-28 09:50:04 -0700432 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 SkEdge* edge = sort_edges(list, count, &last);
438
Andrew Top200ce4b2018-01-29 13:43:50 -0800439 headEdge.fPrev = nullptr;
David Ghandehari9e5b5872016-07-28 09:50:04 -0700440 headEdge.fNext = edge;
441 headEdge.fFirstY = kEDGE_HEAD_Y;
442 headEdge.fX = SK_MinS32;
443 edge->fPrev = &headEdge;
444
445 tailEdge.fPrev = last;
Andrew Top200ce4b2018-01-29 13:43:50 -0800446 tailEdge.fNext = nullptr;
David Ghandehari9e5b5872016-07-28 09:50:04 -0700447 tailEdge.fFirstY = kEDGE_TAIL_Y;
448 last->fNext = &tailEdge;
449
450 // now edge is the head of the sorted linklist
451
Andrew Top200ce4b2018-01-29 13:43:50 -0800452 start_y = SkLeftShift(start_y, shiftEdgesUp);
453 stop_y = SkLeftShift(stop_y, shiftEdgesUp);
454 if (!pathContainedInClip && start_y < shiftedClip.fTop) {
455 start_y = shiftedClip.fTop;
David Ghandehari9e5b5872016-07-28 09:50:04 -0700456 }
Andrew Top200ce4b2018-01-29 13:43:50 -0800457 if (!pathContainedInClip && stop_y > shiftedClip.fBottom) {
458 stop_y = shiftedClip.fBottom;
David Ghandehari9e5b5872016-07-28 09:50:04 -0700459 }
460
461 InverseBlitter ib;
Andrew Top200ce4b2018-01-29 13:43:50 -0800462 PrePostProc proc = nullptr;
David Ghandehari9e5b5872016-07-28 09:50:04 -0700463
464 if (path.isInverseFillType()) {
Andrew Top200ce4b2018-01-29 13:43:50 -0800465 ib.setBlitter(blitter, clipRect, shiftEdgesUp);
David Ghandehari9e5b5872016-07-28 09:50:04 -0700466 blitter = &ib;
467 proc = PrePostInverseBlitterProc;
468 }
469
Andrew Top200ce4b2018-01-29 13:43:50 -0800470 // count >= 2 is required as the convex walker does not handle missing right edges
471 if (path.isConvex() && (nullptr == proc) && count >= 2) {
Xiaoming Shi73dfa202020-03-12 11:31:35 -0700472 walk_simple_edges(&headEdge, blitter, start_y, stop_y);
David Ghandehari9e5b5872016-07-28 09:50:04 -0700473 } else {
Andrew Top200ce4b2018-01-29 13:43:50 -0800474 walk_edges(&headEdge, path.getFillType(), blitter, start_y, stop_y, proc,
475 shiftedClip.right());
David Ghandehari9e5b5872016-07-28 09:50:04 -0700476 }
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,
Xiaoming Shi73dfa202020-03-12 11:31:35 -0700513 const SkIRect& ir, bool skipRejectTest, bool irPreClipped) {
Andrew Top200ce4b2018-01-29 13:43:50 -0800514 fBlitter = nullptr; // null means blit nothing
515 fClipRect = nullptr;
David Ghandehari9e5b5872016-07-28 09:50:04 -0700516
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()) {
Xiaoming Shi73dfa202020-03-12 11:31:35 -0700524 if (!irPreClipped && fClipRect->contains(ir)) {
Andrew Top200ce4b2018-01-29 13:43:50 -0800525#ifdef SK_DEBUG
526 fRectClipCheckBlitter.init(blitter, *fClipRect);
527 blitter = &fRectClipCheckBlitter;
528#endif
529 fClipRect = nullptr;
David Ghandehari9e5b5872016-07-28 09:50:04 -0700530 } else {
531 // only need a wrapper blitter if we're horizontally clipped
Xiaoming Shi73dfa202020-03-12 11:31:35 -0700532 if (irPreClipped ||
533 fClipRect->fLeft > ir.fLeft || fClipRect->fRight < ir.fRight) {
David Ghandehari9e5b5872016-07-28 09:50:04 -0700534 fRectBlitter.init(blitter, *fClipRect);
535 blitter = &fRectBlitter;
Andrew Top200ce4b2018-01-29 13:43:50 -0800536 } else {
537#ifdef SK_DEBUG
538 fRectClipCheckBlitter.init(blitter, *fClipRect);
539 blitter = &fRectClipCheckBlitter;
540#endif
David Ghandehari9e5b5872016-07-28 09:50:04 -0700541 }
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) {
Xiaoming Shi73dfa202020-03-12 11:31:35 -0700554 // 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;
David Ghandehari9e5b5872016-07-28 09:50:04 -0700557
558 SkIRect limitR;
Xiaoming Shi73dfa202020-03-12 11:31:35 -0700559 limitR.setLTRB(-limit, -limit, limit, limit);
David Ghandehari9e5b5872016-07-28 09:50:04 -0700560 if (limitR.contains(orig.getBounds())) {
561 return false;
562 }
563 reduced->op(orig, limitR, SkRegion::kIntersect_Op);
564 return true;
565}
566
Xiaoming Shi73dfa202020-03-12 11:31:35 -0700567// 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;
Andrew Top200ce4b2018-01-29 13:43:50 -0800576
577/**
Xiaoming Shi73dfa202020-03-12 11:31:35 -0700578 * 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 */
Andrew Top200ce4b2018-01-29 13:43:50 -0800583static inline int round_down_to_int(SkScalar x) {
584 double xx = x;
Xiaoming Shi73dfa202020-03-12 11:31:35 -0700585 xx -= kConservativeRoundBias;
586 return sk_double_saturate2int(ceil(xx));
Andrew Top200ce4b2018-01-29 13:43:50 -0800587}
588
589/**
Xiaoming Shi73dfa202020-03-12 11:31:35 -0700590 * 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.
Andrew Top200ce4b2018-01-29 13:43:50 -0800593 */
594static inline int round_up_to_int(SkScalar x) {
595 double xx = x;
Xiaoming Shi73dfa202020-03-12 11:31:35 -0700596 xx += kConservativeRoundBias;
597 return sk_double_saturate2int(floor(xx));
Andrew Top200ce4b2018-01-29 13:43:50 -0800598}
599
Xiaoming Shi73dfa202020-03-12 11:31:35 -0700600/*
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.
Andrew Top200ce4b2018-01-29 13:43:50 -0800607 */
Xiaoming Shi73dfa202020-03-12 11:31:35 -0700608static 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 };
Andrew Top200ce4b2018-01-29 13:43:50 -0800615}
616
David Ghandehari9e5b5872016-07-28 09:50:04 -0700617void SkScan::FillPath(const SkPath& path, const SkRegion& origClip,
618 SkBlitter* blitter) {
619 if (origClip.isEmpty()) {
620 return;
621 }
622
623 // Our edges are fixed-point, and don't like the bounds of the clip to
624 // exceed that. Here we trim the clip just so we don't overflow later on
625 const SkRegion* clipPtr = &origClip;
626 SkRegion finiteClip;
627 if (clip_to_limit(origClip, &finiteClip)) {
628 if (finiteClip.isEmpty()) {
629 return;
630 }
631 clipPtr = &finiteClip;
632 }
Xiaoming Shi73dfa202020-03-12 11:31:35 -0700633 // don't reference "origClip" any more, just use clipPtr
David Ghandehari9e5b5872016-07-28 09:50:04 -0700634
Xiaoming Shi73dfa202020-03-12 11:31:35 -0700635
636 SkRect bounds = path.getBounds();
637 bool irPreClipped = false;
638 if (!SkRectPriv::MakeLargeS32().contains(bounds)) {
639 if (!bounds.intersect(SkRectPriv::MakeLargeS32())) {
640 bounds.setEmpty();
641 }
642 irPreClipped = true;
643 }
644
645 SkIRect ir = conservative_round_to_int(bounds);
David Ghandehari9e5b5872016-07-28 09:50:04 -0700646 if (ir.isEmpty()) {
647 if (path.isInverseFillType()) {
648 blitter->blitRegion(*clipPtr);
649 }
650 return;
651 }
652
Xiaoming Shi73dfa202020-03-12 11:31:35 -0700653 SkScanClipper clipper(blitter, clipPtr, ir, path.isInverseFillType(), irPreClipped);
David Ghandehari9e5b5872016-07-28 09:50:04 -0700654
655 blitter = clipper.getBlitter();
656 if (blitter) {
657 // we have to keep our calls to blitter in sorted order, so we
658 // must blit the above section first, then the middle, then the bottom.
659 if (path.isInverseFillType()) {
660 sk_blit_above(blitter, ir, *clipPtr);
661 }
Andrew Top200ce4b2018-01-29 13:43:50 -0800662 SkASSERT(clipper.getClipRect() == nullptr ||
663 *clipper.getClipRect() == clipPtr->getBounds());
664 sk_fill_path(path, clipPtr->getBounds(), blitter, ir.fTop, ir.fBottom,
665 0, clipper.getClipRect() == nullptr);
David Ghandehari9e5b5872016-07-28 09:50:04 -0700666 if (path.isInverseFillType()) {
667 sk_blit_below(blitter, ir, *clipPtr);
668 }
669 } else {
670 // what does it mean to not have a blitter if path.isInverseFillType???
671 }
672}
673
674void SkScan::FillPath(const SkPath& path, const SkIRect& ir,
675 SkBlitter* blitter) {
676 SkRegion rgn(ir);
677 FillPath(path, rgn, blitter);
678}
679
680///////////////////////////////////////////////////////////////////////////////
681
682static int build_tri_edges(SkEdge edge[], const SkPoint pts[],
683 const SkIRect* clipRect, SkEdge* list[]) {
684 SkEdge** start = list;
685
686 if (edge->setLine(pts[0], pts[1], clipRect, 0)) {
687 *list++ = edge;
688 edge = (SkEdge*)((char*)edge + sizeof(SkEdge));
689 }
690 if (edge->setLine(pts[1], pts[2], clipRect, 0)) {
691 *list++ = edge;
692 edge = (SkEdge*)((char*)edge + sizeof(SkEdge));
693 }
694 if (edge->setLine(pts[2], pts[0], clipRect, 0)) {
695 *list++ = edge;
696 }
697 return (int)(list - start);
698}
699
700
701static void sk_fill_triangle(const SkPoint pts[], const SkIRect* clipRect,
702 SkBlitter* blitter, const SkIRect& ir) {
703 SkASSERT(pts && blitter);
704
705 SkEdge edgeStorage[3];
706 SkEdge* list[3];
707
708 int count = build_tri_edges(edgeStorage, pts, clipRect, list);
709 if (count < 2) {
710 return;
711 }
712
713 SkEdge headEdge, tailEdge, *last;
714
715 // this returns the first and last edge after they're sorted into a dlink list
716 SkEdge* edge = sort_edges(list, count, &last);
717
Andrew Top200ce4b2018-01-29 13:43:50 -0800718 headEdge.fPrev = nullptr;
David Ghandehari9e5b5872016-07-28 09:50:04 -0700719 headEdge.fNext = edge;
720 headEdge.fFirstY = kEDGE_HEAD_Y;
721 headEdge.fX = SK_MinS32;
722 edge->fPrev = &headEdge;
723
724 tailEdge.fPrev = last;
Andrew Top200ce4b2018-01-29 13:43:50 -0800725 tailEdge.fNext = nullptr;
David Ghandehari9e5b5872016-07-28 09:50:04 -0700726 tailEdge.fFirstY = kEDGE_TAIL_Y;
727 last->fNext = &tailEdge;
728
729 // now edge is the head of the sorted linklist
730 int stop_y = ir.fBottom;
731 if (clipRect && stop_y > clipRect->fBottom) {
732 stop_y = clipRect->fBottom;
733 }
734 int start_y = ir.fTop;
735 if (clipRect && start_y < clipRect->fTop) {
736 start_y = clipRect->fTop;
737 }
Xiaoming Shi73dfa202020-03-12 11:31:35 -0700738 walk_simple_edges(&headEdge, blitter, start_y, stop_y);
David Ghandehari9e5b5872016-07-28 09:50:04 -0700739}
740
741void SkScan::FillTriangle(const SkPoint pts[], const SkRasterClip& clip,
742 SkBlitter* blitter) {
743 if (clip.isEmpty()) {
744 return;
745 }
746
747 SkRect r;
Xiaoming Shi73dfa202020-03-12 11:31:35 -0700748 r.setBounds(pts, 3);
749 // If r is too large (larger than can easily fit in SkFixed) then we need perform geometric
750 // clipping. This is a bit of work, so we just call the general FillPath() to handle it.
751 // Use FixedMax/2 as the limit so we can subtract two edges and still store that in Fixed.
752 const SkScalar limit = SK_MaxS16 >> 1;
753 if (!SkRect::MakeLTRB(-limit, -limit, limit, limit).contains(r)) {
754 SkPath path;
755 path.addPoly(pts, 3, false);
756 FillPath(path, clip, blitter);
757 return;
758 }
759
760 SkIRect ir = conservative_round_to_int(r);
David Ghandehari9e5b5872016-07-28 09:50:04 -0700761 if (ir.isEmpty() || !SkIRect::Intersects(ir, clip.getBounds())) {
762 return;
763 }
764
765 SkAAClipBlitterWrapper wrap;
766 const SkRegion* clipRgn;
767 if (clip.isBW()) {
768 clipRgn = &clip.bwRgn();
769 } else {
770 wrap.init(clip, blitter);
771 clipRgn = &wrap.getRgn();
772 blitter = wrap.getBlitter();
773 }
774
775 SkScanClipper clipper(blitter, clipRgn, ir);
776 blitter = clipper.getBlitter();
777 if (blitter) {
778 sk_fill_triangle(pts, clipper.getClipRect(), blitter, ir);
779 }
780}