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
9 #ifndef SkScanPriv_DEFINED
10 #define SkScanPriv_DEFINED
11
12 #include "SkPath.h"
13 #include "SkScan.h"
14 #include "SkBlitter.h"
15
16 class SkScanClipper {
17 public:
18 SkScanClipper(SkBlitter* blitter, const SkRegion* clip, const SkIRect& bounds,
19 bool skipRejectTest = false);
20
getBlitter()21 SkBlitter* getBlitter() const { return fBlitter; }
getClipRect()22 const SkIRect* getClipRect() const { return fClipRect; }
23
24 private:
25 SkRectClipBlitter fRectBlitter;
26 SkRgnClipBlitter fRgnBlitter;
27 #ifdef SK_DEBUG
28 SkRectClipCheckBlitter fRectClipCheckBlitter;
29 #endif
30 SkBlitter* fBlitter;
31 const SkIRect* fClipRect;
32 };
33
34 void sk_fill_path(const SkPath& path, const SkIRect& clipRect,
35 SkBlitter* blitter, int start_y, int stop_y, int shiftEdgesUp,
36 bool pathContainedInClip);
37
38 // blit the rects above and below avoid, clipped to clip
39 void sk_blit_above(SkBlitter*, const SkIRect& avoid, const SkRegion& clip);
40 void sk_blit_below(SkBlitter*, const SkIRect& avoid, const SkRegion& clip);
41
42 template<class EdgeType>
remove_edge(EdgeType * edge)43 static inline void remove_edge(EdgeType* edge) {
44 edge->fPrev->fNext = edge->fNext;
45 edge->fNext->fPrev = edge->fPrev;
46 }
47
48 template<class EdgeType>
insert_edge_after(EdgeType * edge,EdgeType * afterMe)49 static inline void insert_edge_after(EdgeType* edge, EdgeType* afterMe) {
50 edge->fPrev = afterMe;
51 edge->fNext = afterMe->fNext;
52 afterMe->fNext->fPrev = edge;
53 afterMe->fNext = edge;
54 }
55
56 template<class EdgeType>
backward_insert_edge_based_on_x(EdgeType * edge)57 static void backward_insert_edge_based_on_x(EdgeType* edge) {
58 SkFixed x = edge->fX;
59 EdgeType* prev = edge->fPrev;
60 while (prev->fPrev && prev->fX > x) {
61 prev = prev->fPrev;
62 }
63 if (prev->fNext != edge) {
64 remove_edge(edge);
65 insert_edge_after(edge, prev);
66 }
67 }
68
69 // Start from the right side, searching backwards for the point to begin the new edge list
70 // insertion, marching forwards from here. The implementation could have started from the left
71 // of the prior insertion, and search to the right, or with some additional caching, binary
72 // search the starting point. More work could be done to determine optimal new edge insertion.
73 template<class EdgeType>
backward_insert_start(EdgeType * prev,SkFixed x)74 static EdgeType* backward_insert_start(EdgeType* prev, SkFixed x) {
75 while (prev->fPrev && prev->fX > x) {
76 prev = prev->fPrev;
77 }
78 return prev;
79 }
80
fitsInsideLimit(const SkRect & r,SkScalar max)81 static bool fitsInsideLimit(const SkRect& r, SkScalar max) {
82 const SkScalar min = -max;
83 return r.fLeft > min && r.fTop > min &&
84 r.fRight < max && r.fBottom < max;
85 }
86
overflows_short_shift(int value,int shift)87 static int overflows_short_shift(int value, int shift) {
88 const int s = 16 + shift;
89 return (SkLeftShift(value, s) >> s) - value;
90 }
91
92 /**
93 Would any of the coordinates of this rectangle not fit in a short,
94 when left-shifted by shift?
95 */
rect_overflows_short_shift(SkIRect rect,int shift)96 static int rect_overflows_short_shift(SkIRect rect, int shift) {
97 SkASSERT(!overflows_short_shift(8191, shift));
98 SkASSERT(overflows_short_shift(8192, shift));
99 SkASSERT(!overflows_short_shift(32767, 0));
100 SkASSERT(overflows_short_shift(32768, 0));
101
102 // Since we expect these to succeed, we bit-or together
103 // for a tiny extra bit of speed.
104 return overflows_short_shift(rect.fLeft, shift) |
105 overflows_short_shift(rect.fRight, shift) |
106 overflows_short_shift(rect.fTop, shift) |
107 overflows_short_shift(rect.fBottom, shift);
108 }
109
safeRoundOut(const SkRect & src,SkIRect * dst,int32_t maxInt)110 static bool safeRoundOut(const SkRect& src, SkIRect* dst, int32_t maxInt) {
111 const SkScalar maxScalar = SkIntToScalar(maxInt);
112
113 if (fitsInsideLimit(src, maxScalar)) {
114 src.roundOut(dst);
115 return true;
116 }
117 return false;
118 }
119
120 using FillPathFunc = std::function<void(const SkPath& path, SkBlitter* blitter, bool isInverse,
121 const SkIRect& ir, const SkRegion* clipRgn, const SkIRect* clipRect, bool forceRLE)>;
122
do_fill_path(const SkPath & path,const SkRegion & origClip,SkBlitter * blitter,bool forceRLE,const int SHIFT,FillPathFunc fillPathFunc)123 static inline void do_fill_path(const SkPath& path, const SkRegion& origClip, SkBlitter* blitter,
124 bool forceRLE, const int SHIFT, FillPathFunc fillPathFunc) {
125 if (origClip.isEmpty()) {
126 return;
127 }
128
129 const bool isInverse = path.isInverseFillType();
130 SkIRect ir;
131
132 if (!safeRoundOut(path.getBounds(), &ir, SK_MaxS32 >> SHIFT)) {
133 // Bounds can't fit in SkIRect; we'll return without drawing
134 return;
135 }
136 if (ir.isEmpty()) {
137 if (isInverse) {
138 blitter->blitRegion(origClip);
139 }
140 return;
141 }
142
143 // If the intersection of the path bounds and the clip bounds
144 // will overflow 32767 when << by SHIFT, we can't supersample,
145 // so draw without antialiasing.
146 SkIRect clippedIR;
147 if (isInverse) {
148 // If the path is an inverse fill, it's going to fill the entire
149 // clip, and we care whether the entire clip exceeds our limits.
150 clippedIR = origClip.getBounds();
151 } else {
152 if (!clippedIR.intersect(ir, origClip.getBounds())) {
153 return;
154 }
155 }
156 if (rect_overflows_short_shift(clippedIR, SHIFT)) {
157 SkScan::FillPath(path, origClip, blitter);
158 return;
159 }
160
161 // Our antialiasing can't handle a clip larger than 32767, so we restrict
162 // the clip to that limit here. (the runs[] uses int16_t for its index).
163 //
164 // A more general solution (one that could also eliminate the need to
165 // disable aa based on ir bounds (see overflows_short_shift) would be
166 // to tile the clip/target...
167 SkRegion tmpClipStorage;
168 const SkRegion* clipRgn = &origClip;
169 {
170 static const int32_t kMaxClipCoord = 32767;
171 const SkIRect& bounds = origClip.getBounds();
172 if (bounds.fRight > kMaxClipCoord || bounds.fBottom > kMaxClipCoord) {
173 SkIRect limit = { 0, 0, kMaxClipCoord, kMaxClipCoord };
174 tmpClipStorage.op(origClip, limit, SkRegion::kIntersect_Op);
175 clipRgn = &tmpClipStorage;
176 }
177 }
178 // for here down, use clipRgn, not origClip
179
180 SkScanClipper clipper(blitter, clipRgn, ir);
181 const SkIRect* clipRect = clipper.getClipRect();
182
183 if (clipper.getBlitter() == nullptr) { // clipped out
184 if (isInverse) {
185 blitter->blitRegion(*clipRgn);
186 }
187 return;
188 }
189
190 SkASSERT(clipper.getClipRect() == nullptr ||
191 *clipper.getClipRect() == clipRgn->getBounds());
192
193 // now use the (possibly wrapped) blitter
194 blitter = clipper.getBlitter();
195
196 if (isInverse) {
197 sk_blit_above(blitter, ir, *clipRgn);
198 }
199
200 SkASSERT(SkIntToScalar(ir.fTop) <= path.getBounds().fTop);
201
202 fillPathFunc(path, blitter, isInverse, ir, clipRgn, clipRect, forceRLE);
203
204 if (isInverse) {
205 sk_blit_below(blitter, ir, *clipRgn);
206 }
207 }
208
209 #endif
210