1
2 /*
3 * Copyright 2006 The Android Open Source Project
4 *
5 * Use of this source code is governed by a BSD-style license that can be
6 * found in the LICENSE file.
7 */
8
9
10 #include "SkScan.h"
11 #include "SkBlitter.h"
12 #include "SkRasterClip.h"
13 #include "SkFDot6.h"
14 #include "SkLineClipper.h"
15
horiline(int x,int stopx,SkFixed fy,SkFixed dy,SkBlitter * blitter)16 static void horiline(int x, int stopx, SkFixed fy, SkFixed dy,
17 SkBlitter* blitter) {
18 SkASSERT(x < stopx);
19
20 do {
21 blitter->blitH(x, fy >> 16, 1);
22 fy += dy;
23 } while (++x < stopx);
24 }
25
vertline(int y,int stopy,SkFixed fx,SkFixed dx,SkBlitter * blitter)26 static void vertline(int y, int stopy, SkFixed fx, SkFixed dx,
27 SkBlitter* blitter) {
28 SkASSERT(y < stopy);
29
30 do {
31 blitter->blitH(fx >> 16, y, 1);
32 fx += dx;
33 } while (++y < stopy);
34 }
35
HairLineRgn(const SkPoint & pt0,const SkPoint & pt1,const SkRegion * clip,SkBlitter * blitter)36 void SkScan::HairLineRgn(const SkPoint& pt0, const SkPoint& pt1,
37 const SkRegion* clip, SkBlitter* blitter) {
38 SkBlitterClipper clipper;
39 SkRect r;
40 SkIRect clipR, ptsR;
41 SkPoint pts[2] = { pt0, pt1 };
42
43 if (clip) {
44 // Perform a clip in scalar space, so we catch huge values which might
45 // be missed after we convert to SkFDot6 (overflow)
46 r.set(clip->getBounds());
47 if (!SkLineClipper::IntersectLine(pts, r, pts)) {
48 return;
49 }
50 }
51
52 SkFDot6 x0 = SkScalarToFDot6(pts[0].fX);
53 SkFDot6 y0 = SkScalarToFDot6(pts[0].fY);
54 SkFDot6 x1 = SkScalarToFDot6(pts[1].fX);
55 SkFDot6 y1 = SkScalarToFDot6(pts[1].fY);
56
57 if (clip) {
58 // now perform clipping again, as the rounding to dot6 can wiggle us
59 // our rects are really dot6 rects, but since we've already used
60 // lineclipper, we know they will fit in 32bits (26.6)
61 const SkIRect& bounds = clip->getBounds();
62
63 clipR.set(SkIntToFDot6(bounds.fLeft), SkIntToFDot6(bounds.fTop),
64 SkIntToFDot6(bounds.fRight), SkIntToFDot6(bounds.fBottom));
65 ptsR.set(x0, y0, x1, y1);
66 ptsR.sort();
67
68 // outset the right and bottom, to account for how hairlines are
69 // actually drawn, which may hit the pixel to the right or below of
70 // the coordinate
71 ptsR.fRight += SK_FDot6One;
72 ptsR.fBottom += SK_FDot6One;
73
74 if (!SkIRect::Intersects(ptsR, clipR)) {
75 return;
76 }
77 if (clip->isRect() && clipR.contains(ptsR)) {
78 clip = NULL;
79 } else {
80 blitter = clipper.apply(blitter, clip);
81 }
82 }
83
84 SkFDot6 dx = x1 - x0;
85 SkFDot6 dy = y1 - y0;
86
87 if (SkAbs32(dx) > SkAbs32(dy)) { // mostly horizontal
88 if (x0 > x1) { // we want to go left-to-right
89 SkTSwap<SkFDot6>(x0, x1);
90 SkTSwap<SkFDot6>(y0, y1);
91 }
92 int ix0 = SkFDot6Round(x0);
93 int ix1 = SkFDot6Round(x1);
94 if (ix0 == ix1) {// too short to draw
95 return;
96 }
97
98 SkFixed slope = SkFixedDiv(dy, dx);
99 SkFixed startY = SkFDot6ToFixed(y0) + (slope * ((32 - x0) & 63) >> 6);
100
101 horiline(ix0, ix1, startY, slope, blitter);
102 } else { // mostly vertical
103 if (y0 > y1) { // we want to go top-to-bottom
104 SkTSwap<SkFDot6>(x0, x1);
105 SkTSwap<SkFDot6>(y0, y1);
106 }
107 int iy0 = SkFDot6Round(y0);
108 int iy1 = SkFDot6Round(y1);
109 if (iy0 == iy1) { // too short to draw
110 return;
111 }
112
113 SkFixed slope = SkFixedDiv(dx, dy);
114 SkFixed startX = SkFDot6ToFixed(x0) + (slope * ((32 - y0) & 63) >> 6);
115
116 vertline(iy0, iy1, startX, slope, blitter);
117 }
118 }
119
120 // we don't just draw 4 lines, 'cause that can leave a gap in the bottom-right
121 // and double-hit the top-left.
122 // TODO: handle huge coordinates on rect (before calling SkScalarToFixed)
HairRect(const SkRect & rect,const SkRasterClip & clip,SkBlitter * blitter)123 void SkScan::HairRect(const SkRect& rect, const SkRasterClip& clip,
124 SkBlitter* blitter) {
125 SkAAClipBlitterWrapper wrapper;
126 SkBlitterClipper clipper;
127 SkIRect r;
128
129 r.set(SkScalarToFixed(rect.fLeft) >> 16,
130 SkScalarToFixed(rect.fTop) >> 16,
131 (SkScalarToFixed(rect.fRight) >> 16) + 1,
132 (SkScalarToFixed(rect.fBottom) >> 16) + 1);
133
134 if (clip.quickReject(r)) {
135 return;
136 }
137 if (!clip.quickContains(r)) {
138 const SkRegion* clipRgn;
139 if (clip.isBW()) {
140 clipRgn = &clip.bwRgn();
141 } else {
142 wrapper.init(clip, blitter);
143 clipRgn = &wrapper.getRgn();
144 blitter = wrapper.getBlitter();
145 }
146 blitter = clipper.apply(blitter, clipRgn);
147 }
148
149 int width = r.width();
150 int height = r.height();
151
152 if ((width | height) == 0) {
153 return;
154 }
155 if (width <= 2 || height <= 2) {
156 blitter->blitRect(r.fLeft, r.fTop, width, height);
157 return;
158 }
159 // if we get here, we know we have 4 segments to draw
160 blitter->blitH(r.fLeft, r.fTop, width); // top
161 blitter->blitRect(r.fLeft, r.fTop + 1, 1, height - 2); // left
162 blitter->blitRect(r.fRight - 1, r.fTop + 1, 1, height - 2); // right
163 blitter->blitH(r.fLeft, r.fBottom - 1, width); // bottom
164 }
165
166 ///////////////////////////////////////////////////////////////////////////////
167
168 #include "SkPath.h"
169 #include "SkGeometry.h"
170
quad_too_curvy(const SkPoint pts[3])171 static bool quad_too_curvy(const SkPoint pts[3]) {
172 return true;
173 }
174
compute_int_quad_dist(const SkPoint pts[3])175 static int compute_int_quad_dist(const SkPoint pts[3]) {
176 // compute the vector between the control point ([1]) and the middle of the
177 // line connecting the start and end ([0] and [2])
178 SkScalar dx = SkScalarHalf(pts[0].fX + pts[2].fX) - pts[1].fX;
179 SkScalar dy = SkScalarHalf(pts[0].fY + pts[2].fY) - pts[1].fY;
180 // we want everyone to be positive
181 dx = SkScalarAbs(dx);
182 dy = SkScalarAbs(dy);
183 // convert to whole pixel values (use ceiling to be conservative)
184 int idx = SkScalarCeil(dx);
185 int idy = SkScalarCeil(dy);
186 // use the cheap approx for distance
187 if (idx > idy) {
188 return idx + (idy >> 1);
189 } else {
190 return idy + (idx >> 1);
191 }
192 }
193
hairquad(const SkPoint pts[3],const SkRegion * clip,SkBlitter * blitter,int level,void (* lineproc)(const SkPoint &,const SkPoint &,const SkRegion * clip,SkBlitter *))194 static void hairquad(const SkPoint pts[3], const SkRegion* clip, SkBlitter* blitter, int level,
195 void (*lineproc)(const SkPoint&, const SkPoint&, const SkRegion* clip, SkBlitter*))
196 {
197 #if 1
198 if (level > 0 && quad_too_curvy(pts))
199 {
200 SkPoint tmp[5];
201
202 SkChopQuadAtHalf(pts, tmp);
203 hairquad(tmp, clip, blitter, level - 1, lineproc);
204 hairquad(&tmp[2], clip, blitter, level - 1, lineproc);
205 }
206 else
207 lineproc(pts[0], pts[2], clip, blitter);
208 #else
209 int count = 1 << level;
210 const SkScalar dt = SkFixedToScalar(SK_Fixed1 >> level);
211 SkScalar t = dt;
212 SkPoint prevPt = pts[0];
213 for (int i = 1; i < count; i++) {
214 SkPoint nextPt;
215 SkEvalQuadAt(pts, t, &nextPt);
216 lineproc(prevPt, nextPt, clip, blitter);
217 t += dt;
218 prevPt = nextPt;
219 }
220 // draw the last line explicitly to 1.0, in case t didn't match that exactly
221 lineproc(prevPt, pts[2], clip, blitter);
222 #endif
223 }
224
cubic_too_curvy(const SkPoint pts[4])225 static bool cubic_too_curvy(const SkPoint pts[4])
226 {
227 return true;
228 }
229
haircubic(const SkPoint pts[4],const SkRegion * clip,SkBlitter * blitter,int level,void (* lineproc)(const SkPoint &,const SkPoint &,const SkRegion *,SkBlitter *))230 static void haircubic(const SkPoint pts[4], const SkRegion* clip, SkBlitter* blitter, int level,
231 void (*lineproc)(const SkPoint&, const SkPoint&, const SkRegion*, SkBlitter*))
232 {
233 if (level > 0 && cubic_too_curvy(pts))
234 {
235 SkPoint tmp[7];
236
237 SkChopCubicAt(pts, tmp, SK_Scalar1/2);
238 haircubic(tmp, clip, blitter, level - 1, lineproc);
239 haircubic(&tmp[3], clip, blitter, level - 1, lineproc);
240 }
241 else
242 lineproc(pts[0], pts[3], clip, blitter);
243 }
244
245 #define kMaxCubicSubdivideLevel 6
246 #define kMaxQuadSubdivideLevel 5
247
hair_path(const SkPath & path,const SkRasterClip & rclip,SkBlitter * blitter,void (* lineproc)(const SkPoint &,const SkPoint &,const SkRegion *,SkBlitter *))248 static void hair_path(const SkPath& path, const SkRasterClip& rclip, SkBlitter* blitter,
249 void (*lineproc)(const SkPoint&, const SkPoint&, const SkRegion*, SkBlitter*))
250 {
251 if (path.isEmpty()) {
252 return;
253 }
254
255 SkAAClipBlitterWrapper wrap;
256 const SkIRect* clipR = NULL;
257 const SkRegion* clip = NULL;
258
259 {
260 SkIRect ibounds;
261 path.getBounds().roundOut(&ibounds);
262 ibounds.inset(-1, -1);
263
264 if (rclip.quickReject(ibounds)) {
265 return;
266 }
267 if (!rclip.quickContains(ibounds)) {
268 clipR = &rclip.getBounds();
269 if (rclip.isBW()) {
270 clip = &rclip.bwRgn();
271 } else {
272 wrap.init(rclip, blitter);
273 blitter = wrap.getBlitter();
274 clip = &wrap.getRgn();
275 }
276 }
277 }
278
279 SkPath::Iter iter(path, false);
280 SkPoint pts[4];
281 SkPath::Verb verb;
282
283 while ((verb = iter.next(pts)) != SkPath::kDone_Verb) {
284 switch (verb) {
285 case SkPath::kLine_Verb:
286 lineproc(pts[0], pts[1], clip, blitter);
287 break;
288 case SkPath::kQuad_Verb: {
289 int d = compute_int_quad_dist(pts);
290 /* quadratics approach the line connecting their start and end points
291 4x closer with each subdivision, so we compute the number of
292 subdivisions to be the minimum need to get that distance to be less
293 than a pixel.
294 */
295 int level = (33 - SkCLZ(d)) >> 1;
296 // SkDebugf("----- distance %d computedLevel %d\n", d, computedLevel);
297 // sanity check on level (from the previous version)
298 if (level > kMaxQuadSubdivideLevel) {
299 level = kMaxQuadSubdivideLevel;
300 }
301 hairquad(pts, clip, blitter, level, lineproc);
302 break;
303 }
304 case SkPath::kCubic_Verb:
305 haircubic(pts, clip, blitter, kMaxCubicSubdivideLevel, lineproc);
306 break;
307 default:
308 break;
309 }
310 }
311 }
312
HairPath(const SkPath & path,const SkRasterClip & clip,SkBlitter * blitter)313 void SkScan::HairPath(const SkPath& path, const SkRasterClip& clip,
314 SkBlitter* blitter) {
315 hair_path(path, clip, blitter, SkScan::HairLineRgn);
316 }
317
AntiHairPath(const SkPath & path,const SkRasterClip & clip,SkBlitter * blitter)318 void SkScan::AntiHairPath(const SkPath& path, const SkRasterClip& clip,
319 SkBlitter* blitter) {
320 hair_path(path, clip, blitter, SkScan::AntiHairLineRgn);
321 }
322
323 ///////////////////////////////////////////////////////////////////////////////
324
FrameRect(const SkRect & r,const SkPoint & strokeSize,const SkRasterClip & clip,SkBlitter * blitter)325 void SkScan::FrameRect(const SkRect& r, const SkPoint& strokeSize,
326 const SkRasterClip& clip, SkBlitter* blitter) {
327 SkASSERT(strokeSize.fX >= 0 && strokeSize.fY >= 0);
328
329 if (strokeSize.fX < 0 || strokeSize.fY < 0) {
330 return;
331 }
332
333 const SkScalar dx = strokeSize.fX;
334 const SkScalar dy = strokeSize.fY;
335 SkScalar rx = SkScalarHalf(dx);
336 SkScalar ry = SkScalarHalf(dy);
337 SkRect outer, tmp;
338
339 outer.set(r.fLeft - rx, r.fTop - ry,
340 r.fRight + rx, r.fBottom + ry);
341
342 if (r.width() <= dx || r.height() <= dx) {
343 SkScan::FillRect(outer, clip, blitter);
344 return;
345 }
346
347 tmp.set(outer.fLeft, outer.fTop, outer.fRight, outer.fTop + dy);
348 SkScan::FillRect(tmp, clip, blitter);
349 tmp.fTop = outer.fBottom - dy;
350 tmp.fBottom = outer.fBottom;
351 SkScan::FillRect(tmp, clip, blitter);
352
353 tmp.set(outer.fLeft, outer.fTop + dy, outer.fLeft + dx, outer.fBottom - dy);
354 SkScan::FillRect(tmp, clip, blitter);
355 tmp.fLeft = outer.fRight - dx;
356 tmp.fRight = outer.fRight;
357 SkScan::FillRect(tmp, clip, blitter);
358 }
359
HairLine(const SkPoint & p0,const SkPoint & p1,const SkRasterClip & clip,SkBlitter * blitter)360 void SkScan::HairLine(const SkPoint& p0, const SkPoint& p1,
361 const SkRasterClip& clip, SkBlitter* blitter) {
362 if (clip.isBW()) {
363 HairLineRgn(p0, p1, &clip.bwRgn(), blitter);
364 } else {
365 const SkRegion* clipRgn = NULL;
366 SkRect r;
367 SkIRect ir;
368 r.set(p0.fX, p0.fY, p1.fX, p1.fY);
369 r.sort();
370 r.inset(-SK_ScalarHalf, -SK_ScalarHalf);
371 r.roundOut(&ir);
372
373 SkAAClipBlitterWrapper wrap;
374 if (!clip.quickContains(ir)) {
375 wrap.init(clip, blitter);
376 blitter = wrap.getBlitter();
377 clipRgn = &wrap.getRgn();
378 }
379 HairLineRgn(p0, p1, clipRgn, blitter);
380 }
381 }
382
AntiHairLine(const SkPoint & p0,const SkPoint & p1,const SkRasterClip & clip,SkBlitter * blitter)383 void SkScan::AntiHairLine(const SkPoint& p0, const SkPoint& p1,
384 const SkRasterClip& clip, SkBlitter* blitter) {
385 if (clip.isBW()) {
386 AntiHairLineRgn(p0, p1, &clip.bwRgn(), blitter);
387 } else {
388 const SkRegion* clipRgn = NULL;
389 SkRect r;
390 SkIRect ir;
391 r.set(p0.fX, p0.fY, p1.fX, p1.fY);
392 r.sort();
393 r.roundOut(&ir);
394 ir.inset(-1, -1);
395
396 SkAAClipBlitterWrapper wrap;
397 if (!clip.quickContains(ir)) {
398 wrap.init(clip, blitter);
399 blitter = wrap.getBlitter();
400 clipRgn = &wrap.getRgn();
401 }
402 AntiHairLineRgn(p0, p1, clipRgn, blitter);
403 }
404 }
405