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 "SkScan.h"
9 #include "SkBlitter.h"
10 #include "SkRasterClip.h"
11 #include "SkFDot6.h"
12 #include "SkLineClipper.h"
13
horiline(int x,int stopx,SkFixed fy,SkFixed dy,SkBlitter * blitter)14 static void horiline(int x, int stopx, SkFixed fy, SkFixed dy,
15 SkBlitter* blitter) {
16 SkASSERT(x < stopx);
17
18 do {
19 blitter->blitH(x, fy >> 16, 1);
20 fy += dy;
21 } while (++x < stopx);
22 }
23
vertline(int y,int stopy,SkFixed fx,SkFixed dx,SkBlitter * blitter)24 static void vertline(int y, int stopy, SkFixed fx, SkFixed dx,
25 SkBlitter* blitter) {
26 SkASSERT(y < stopy);
27
28 do {
29 blitter->blitH(fx >> 16, y, 1);
30 fx += dx;
31 } while (++y < stopy);
32 }
33
34 #ifdef SK_DEBUG
canConvertFDot6ToFixed(SkFDot6 x)35 static bool canConvertFDot6ToFixed(SkFDot6 x) {
36 const int maxDot6 = SK_MaxS32 >> (16 - 6);
37 return SkAbs32(x) <= maxDot6;
38 }
39 #endif
40
HairLineRgn(const SkPoint array[],int arrayCount,const SkRegion * clip,SkBlitter * origBlitter)41 void SkScan::HairLineRgn(const SkPoint array[], int arrayCount, const SkRegion* clip,
42 SkBlitter* origBlitter) {
43 SkBlitterClipper clipper;
44 SkIRect clipR, ptsR;
45
46 const SkScalar max = SkIntToScalar(32767);
47 const SkRect fixedBounds = SkRect::MakeLTRB(-max, -max, max, max);
48
49 SkRect clipBounds;
50 if (clip) {
51 clipBounds.set(clip->getBounds());
52 }
53
54 for (int i = 0; i < arrayCount - 1; ++i) {
55 SkBlitter* blitter = origBlitter;
56
57 SkPoint pts[2];
58
59 // We have to pre-clip the line to fit in a SkFixed, so we just chop
60 // the line. TODO find a way to actually draw beyond that range.
61 if (!SkLineClipper::IntersectLine(&array[i], fixedBounds, pts)) {
62 continue;
63 }
64
65 // Perform a clip in scalar space, so we catch huge values which might
66 // be missed after we convert to SkFDot6 (overflow)
67 if (clip && !SkLineClipper::IntersectLine(pts, clipBounds, pts)) {
68 continue;
69 }
70
71 SkFDot6 x0 = SkScalarToFDot6(pts[0].fX);
72 SkFDot6 y0 = SkScalarToFDot6(pts[0].fY);
73 SkFDot6 x1 = SkScalarToFDot6(pts[1].fX);
74 SkFDot6 y1 = SkScalarToFDot6(pts[1].fY);
75
76 SkASSERT(canConvertFDot6ToFixed(x0));
77 SkASSERT(canConvertFDot6ToFixed(y0));
78 SkASSERT(canConvertFDot6ToFixed(x1));
79 SkASSERT(canConvertFDot6ToFixed(y1));
80
81 if (clip) {
82 // now perform clipping again, as the rounding to dot6 can wiggle us
83 // our rects are really dot6 rects, but since we've already used
84 // lineclipper, we know they will fit in 32bits (26.6)
85 const SkIRect& bounds = clip->getBounds();
86
87 clipR.set(SkIntToFDot6(bounds.fLeft), SkIntToFDot6(bounds.fTop),
88 SkIntToFDot6(bounds.fRight), SkIntToFDot6(bounds.fBottom));
89 ptsR.set(x0, y0, x1, y1);
90 ptsR.sort();
91
92 // outset the right and bottom, to account for how hairlines are
93 // actually drawn, which may hit the pixel to the right or below of
94 // the coordinate
95 ptsR.fRight += SK_FDot6One;
96 ptsR.fBottom += SK_FDot6One;
97
98 if (!SkIRect::Intersects(ptsR, clipR)) {
99 continue;
100 }
101 if (!clip->isRect() || !clipR.contains(ptsR)) {
102 blitter = clipper.apply(origBlitter, clip);
103 }
104 }
105
106 SkFDot6 dx = x1 - x0;
107 SkFDot6 dy = y1 - y0;
108
109 if (SkAbs32(dx) > SkAbs32(dy)) { // mostly horizontal
110 if (x0 > x1) { // we want to go left-to-right
111 SkTSwap<SkFDot6>(x0, x1);
112 SkTSwap<SkFDot6>(y0, y1);
113 }
114 int ix0 = SkFDot6Round(x0);
115 int ix1 = SkFDot6Round(x1);
116 if (ix0 == ix1) {// too short to draw
117 continue;
118 }
119
120 SkFixed slope = SkFixedDiv(dy, dx);
121 SkFixed startY = SkFDot6ToFixed(y0) + (slope * ((32 - x0) & 63) >> 6);
122
123 horiline(ix0, ix1, startY, slope, blitter);
124 } else { // mostly vertical
125 if (y0 > y1) { // we want to go top-to-bottom
126 SkTSwap<SkFDot6>(x0, x1);
127 SkTSwap<SkFDot6>(y0, y1);
128 }
129 int iy0 = SkFDot6Round(y0);
130 int iy1 = SkFDot6Round(y1);
131 if (iy0 == iy1) { // too short to draw
132 continue;
133 }
134
135 SkFixed slope = SkFixedDiv(dx, dy);
136 SkFixed startX = SkFDot6ToFixed(x0) + (slope * ((32 - y0) & 63) >> 6);
137
138 vertline(iy0, iy1, startX, slope, blitter);
139 }
140 }
141 }
142
143 // we don't just draw 4 lines, 'cause that can leave a gap in the bottom-right
144 // and double-hit the top-left.
145 // TODO: handle huge coordinates on rect (before calling SkScalarToFixed)
HairRect(const SkRect & rect,const SkRasterClip & clip,SkBlitter * blitter)146 void SkScan::HairRect(const SkRect& rect, const SkRasterClip& clip,
147 SkBlitter* blitter) {
148 SkAAClipBlitterWrapper wrapper;
149 SkBlitterClipper clipper;
150 SkIRect r;
151
152 r.set(SkScalarToFixed(rect.fLeft) >> 16,
153 SkScalarToFixed(rect.fTop) >> 16,
154 (SkScalarToFixed(rect.fRight) >> 16) + 1,
155 (SkScalarToFixed(rect.fBottom) >> 16) + 1);
156
157 if (clip.quickReject(r)) {
158 return;
159 }
160 if (!clip.quickContains(r)) {
161 const SkRegion* clipRgn;
162 if (clip.isBW()) {
163 clipRgn = &clip.bwRgn();
164 } else {
165 wrapper.init(clip, blitter);
166 clipRgn = &wrapper.getRgn();
167 blitter = wrapper.getBlitter();
168 }
169 blitter = clipper.apply(blitter, clipRgn);
170 }
171
172 int width = r.width();
173 int height = r.height();
174
175 if ((width | height) == 0) {
176 return;
177 }
178 if (width <= 2 || height <= 2) {
179 blitter->blitRect(r.fLeft, r.fTop, width, height);
180 return;
181 }
182 // if we get here, we know we have 4 segments to draw
183 blitter->blitH(r.fLeft, r.fTop, width); // top
184 blitter->blitRect(r.fLeft, r.fTop + 1, 1, height - 2); // left
185 blitter->blitRect(r.fRight - 1, r.fTop + 1, 1, height - 2); // right
186 blitter->blitH(r.fLeft, r.fBottom - 1, width); // bottom
187 }
188
189 ///////////////////////////////////////////////////////////////////////////////
190
191 #include "SkPath.h"
192 #include "SkGeometry.h"
193 #include "SkNx.h"
194
195 #define kMaxCubicSubdivideLevel 6
196 #define kMaxQuadSubdivideLevel 5
197
compute_int_quad_dist(const SkPoint pts[3])198 static int compute_int_quad_dist(const SkPoint pts[3]) {
199 // compute the vector between the control point ([1]) and the middle of the
200 // line connecting the start and end ([0] and [2])
201 SkScalar dx = SkScalarHalf(pts[0].fX + pts[2].fX) - pts[1].fX;
202 SkScalar dy = SkScalarHalf(pts[0].fY + pts[2].fY) - pts[1].fY;
203 // we want everyone to be positive
204 dx = SkScalarAbs(dx);
205 dy = SkScalarAbs(dy);
206 // convert to whole pixel values (use ceiling to be conservative)
207 int idx = SkScalarCeilToInt(dx);
208 int idy = SkScalarCeilToInt(dy);
209 // use the cheap approx for distance
210 if (idx > idy) {
211 return idx + (idy >> 1);
212 } else {
213 return idy + (idx >> 1);
214 }
215 }
216
hairquad(const SkPoint pts[3],const SkRegion * clip,SkBlitter * blitter,int level,SkScan::HairRgnProc lineproc)217 static void hairquad(const SkPoint pts[3], const SkRegion* clip,
218 SkBlitter* blitter, int level, SkScan::HairRgnProc lineproc) {
219 SkASSERT(level <= kMaxQuadSubdivideLevel);
220
221 SkPoint coeff[3];
222 SkQuadToCoeff(pts, coeff);
223
224 const int lines = 1 << level;
225 Sk2s t(0);
226 Sk2s dt(SK_Scalar1 / lines);
227
228 SkPoint tmp[(1 << kMaxQuadSubdivideLevel) + 1];
229 SkASSERT((unsigned)lines < SK_ARRAY_COUNT(tmp));
230
231 tmp[0] = pts[0];
232 Sk2s A = Sk2s::Load(&coeff[0].fX);
233 Sk2s B = Sk2s::Load(&coeff[1].fX);
234 Sk2s C = Sk2s::Load(&coeff[2].fX);
235 for (int i = 1; i < lines; ++i) {
236 t += dt;
237 ((A * t + B) * t + C).store(&tmp[i].fX);
238 }
239 tmp[lines] = pts[2];
240 lineproc(tmp, lines + 1, clip, blitter);
241 }
242
abs(const Sk2s & value)243 static inline Sk2s abs(const Sk2s& value) {
244 return Sk2s::Max(value, -value);
245 }
246
max_component(const Sk2s & value)247 static inline SkScalar max_component(const Sk2s& value) {
248 SkScalar components[2];
249 value.store(components);
250 return SkTMax(components[0], components[1]);
251 }
252
compute_cubic_segs(const SkPoint pts[4])253 static inline int compute_cubic_segs(const SkPoint pts[4]) {
254 Sk2s p0 = from_point(pts[0]);
255 Sk2s p1 = from_point(pts[1]);
256 Sk2s p2 = from_point(pts[2]);
257 Sk2s p3 = from_point(pts[3]);
258
259 const Sk2s oneThird(1.0f / 3.0f);
260 const Sk2s twoThird(2.0f / 3.0f);
261
262 Sk2s p13 = oneThird * p3 + twoThird * p0;
263 Sk2s p23 = oneThird * p0 + twoThird * p3;
264
265 SkScalar diff = max_component(Sk2s::Max(abs(p1 - p13), abs(p2 - p23)));
266 SkScalar tol = SK_Scalar1 / 8;
267
268 for (int i = 0; i < kMaxCubicSubdivideLevel; ++i) {
269 if (diff < tol) {
270 return 1 << i;
271 }
272 tol *= 4;
273 }
274 return 1 << kMaxCubicSubdivideLevel;
275 }
276
lt_90(SkPoint p0,SkPoint pivot,SkPoint p2)277 static bool lt_90(SkPoint p0, SkPoint pivot, SkPoint p2) {
278 return SkVector::DotProduct(p0 - pivot, p2 - pivot) >= 0;
279 }
280
281 // The off-curve points are "inside" the limits of the on-curve pts
quick_cubic_niceness_check(const SkPoint pts[4])282 static bool quick_cubic_niceness_check(const SkPoint pts[4]) {
283 return lt_90(pts[1], pts[0], pts[3]) &&
284 lt_90(pts[2], pts[0], pts[3]) &&
285 lt_90(pts[1], pts[3], pts[0]) &&
286 lt_90(pts[2], pts[3], pts[0]);
287 }
288
hair_cubic(const SkPoint pts[4],const SkRegion * clip,SkBlitter * blitter,SkScan::HairRgnProc lineproc)289 static void hair_cubic(const SkPoint pts[4], const SkRegion* clip, SkBlitter* blitter,
290 SkScan::HairRgnProc lineproc) {
291 const int lines = compute_cubic_segs(pts);
292 SkASSERT(lines > 0);
293 if (1 == lines) {
294 SkPoint tmp[2] = { pts[0], pts[3] };
295 lineproc(tmp, 2, clip, blitter);
296 return;
297 }
298
299 SkPoint coeff[4];
300 SkCubicToCoeff(pts, coeff);
301
302 const Sk2s dt(SK_Scalar1 / lines);
303 Sk2s t(0);
304
305 SkPoint tmp[(1 << kMaxCubicSubdivideLevel) + 1];
306 SkASSERT((unsigned)lines < SK_ARRAY_COUNT(tmp));
307
308 tmp[0] = pts[0];
309 Sk2s A = Sk2s::Load(&coeff[0].fX);
310 Sk2s B = Sk2s::Load(&coeff[1].fX);
311 Sk2s C = Sk2s::Load(&coeff[2].fX);
312 Sk2s D = Sk2s::Load(&coeff[3].fX);
313 for (int i = 1; i < lines; ++i) {
314 t += dt;
315 (((A * t + B) * t + C) * t + D).store(&tmp[i].fX);
316 }
317 tmp[lines] = pts[3];
318 lineproc(tmp, lines + 1, clip, blitter);
319 }
320
haircubic(const SkPoint pts[4],const SkRegion * clip,SkBlitter * blitter,int level,SkScan::HairRgnProc lineproc)321 static inline void haircubic(const SkPoint pts[4], const SkRegion* clip,
322 SkBlitter* blitter, int level, SkScan::HairRgnProc lineproc) {
323 if (quick_cubic_niceness_check(pts)) {
324 hair_cubic(pts, clip, blitter, lineproc);
325 } else {
326 SkPoint tmp[13];
327 SkScalar tValues[3];
328
329 int count = SkChopCubicAtMaxCurvature(pts, tmp, tValues);
330 for (int i = 0; i < count; i++) {
331 hair_cubic(&tmp[i * 3], clip, blitter, lineproc);
332 }
333 }
334 }
335
compute_quad_level(const SkPoint pts[3])336 static int compute_quad_level(const SkPoint pts[3]) {
337 int d = compute_int_quad_dist(pts);
338 /* quadratics approach the line connecting their start and end points
339 4x closer with each subdivision, so we compute the number of
340 subdivisions to be the minimum need to get that distance to be less
341 than a pixel.
342 */
343 int level = (33 - SkCLZ(d)) >> 1;
344 // sanity check on level (from the previous version)
345 if (level > kMaxQuadSubdivideLevel) {
346 level = kMaxQuadSubdivideLevel;
347 }
348 return level;
349 }
350
hair_path(const SkPath & path,const SkRasterClip & rclip,SkBlitter * blitter,SkScan::HairRgnProc lineproc)351 static void hair_path(const SkPath& path, const SkRasterClip& rclip, SkBlitter* blitter,
352 SkScan::HairRgnProc lineproc) {
353 if (path.isEmpty()) {
354 return;
355 }
356
357 SkAAClipBlitterWrapper wrap;
358 const SkRegion* clip = NULL;
359
360 {
361 const SkIRect ibounds = path.getBounds().roundOut().makeOutset(1, 1);
362
363 if (rclip.quickReject(ibounds)) {
364 return;
365 }
366 if (!rclip.quickContains(ibounds)) {
367 if (rclip.isBW()) {
368 clip = &rclip.bwRgn();
369 } else {
370 wrap.init(rclip, blitter);
371 blitter = wrap.getBlitter();
372 clip = &wrap.getRgn();
373 }
374 }
375 }
376
377 SkPath::Iter iter(path, false);
378 SkPoint pts[4];
379 SkPath::Verb verb;
380 SkAutoConicToQuads converter;
381
382 while ((verb = iter.next(pts, false)) != SkPath::kDone_Verb) {
383 switch (verb) {
384 case SkPath::kMove_Verb:
385 break;
386 case SkPath::kLine_Verb:
387 lineproc(pts, 2, clip, blitter);
388 break;
389 case SkPath::kQuad_Verb:
390 hairquad(pts, clip, blitter, compute_quad_level(pts), lineproc);
391 break;
392 case SkPath::kConic_Verb: {
393 // how close should the quads be to the original conic?
394 const SkScalar tol = SK_Scalar1 / 4;
395 const SkPoint* quadPts = converter.computeQuads(pts,
396 iter.conicWeight(), tol);
397 for (int i = 0; i < converter.countQuads(); ++i) {
398 int level = compute_quad_level(quadPts);
399 hairquad(quadPts, clip, blitter, level, lineproc);
400 quadPts += 2;
401 }
402 break;
403 }
404 case SkPath::kCubic_Verb: {
405 haircubic(pts, clip, blitter, kMaxCubicSubdivideLevel, lineproc);
406 } break;
407 case SkPath::kClose_Verb:
408 break;
409 case SkPath::kDone_Verb:
410 break;
411 }
412 }
413 }
414
HairPath(const SkPath & path,const SkRasterClip & clip,SkBlitter * blitter)415 void SkScan::HairPath(const SkPath& path, const SkRasterClip& clip, SkBlitter* blitter) {
416 hair_path(path, clip, blitter, SkScan::HairLineRgn);
417 }
418
AntiHairPath(const SkPath & path,const SkRasterClip & clip,SkBlitter * blitter)419 void SkScan::AntiHairPath(const SkPath& path, const SkRasterClip& clip, SkBlitter* blitter) {
420 hair_path(path, clip, blitter, SkScan::AntiHairLineRgn);
421 }
422
423 ///////////////////////////////////////////////////////////////////////////////
424
FrameRect(const SkRect & r,const SkPoint & strokeSize,const SkRasterClip & clip,SkBlitter * blitter)425 void SkScan::FrameRect(const SkRect& r, const SkPoint& strokeSize,
426 const SkRasterClip& clip, SkBlitter* blitter) {
427 SkASSERT(strokeSize.fX >= 0 && strokeSize.fY >= 0);
428
429 if (strokeSize.fX < 0 || strokeSize.fY < 0) {
430 return;
431 }
432
433 const SkScalar dx = strokeSize.fX;
434 const SkScalar dy = strokeSize.fY;
435 SkScalar rx = SkScalarHalf(dx);
436 SkScalar ry = SkScalarHalf(dy);
437 SkRect outer, tmp;
438
439 outer.set(r.fLeft - rx, r.fTop - ry,
440 r.fRight + rx, r.fBottom + ry);
441
442 if (r.width() <= dx || r.height() <= dx) {
443 SkScan::FillRect(outer, clip, blitter);
444 return;
445 }
446
447 tmp.set(outer.fLeft, outer.fTop, outer.fRight, outer.fTop + dy);
448 SkScan::FillRect(tmp, clip, blitter);
449 tmp.fTop = outer.fBottom - dy;
450 tmp.fBottom = outer.fBottom;
451 SkScan::FillRect(tmp, clip, blitter);
452
453 tmp.set(outer.fLeft, outer.fTop + dy, outer.fLeft + dx, outer.fBottom - dy);
454 SkScan::FillRect(tmp, clip, blitter);
455 tmp.fLeft = outer.fRight - dx;
456 tmp.fRight = outer.fRight;
457 SkScan::FillRect(tmp, clip, blitter);
458 }
459
HairLine(const SkPoint pts[],int count,const SkRasterClip & clip,SkBlitter * blitter)460 void SkScan::HairLine(const SkPoint pts[], int count, const SkRasterClip& clip,
461 SkBlitter* blitter) {
462 if (clip.isBW()) {
463 HairLineRgn(pts, count, &clip.bwRgn(), blitter);
464 } else {
465 const SkRegion* clipRgn = NULL;
466
467 SkRect r;
468 r.set(pts, count);
469 r.outset(SK_ScalarHalf, SK_ScalarHalf);
470
471 SkAAClipBlitterWrapper wrap;
472 if (!clip.quickContains(r.roundOut())) {
473 wrap.init(clip, blitter);
474 blitter = wrap.getBlitter();
475 clipRgn = &wrap.getRgn();
476 }
477 HairLineRgn(pts, count, clipRgn, blitter);
478 }
479 }
480
AntiHairLine(const SkPoint pts[],int count,const SkRasterClip & clip,SkBlitter * blitter)481 void SkScan::AntiHairLine(const SkPoint pts[], int count, const SkRasterClip& clip,
482 SkBlitter* blitter) {
483 if (clip.isBW()) {
484 AntiHairLineRgn(pts, count, &clip.bwRgn(), blitter);
485 } else {
486 const SkRegion* clipRgn = NULL;
487
488 SkRect r;
489 r.set(pts, count);
490
491 SkAAClipBlitterWrapper wrap;
492 if (!clip.quickContains(r.roundOut().makeOutset(1, 1))) {
493 wrap.init(clip, blitter);
494 blitter = wrap.getBlitter();
495 clipRgn = &wrap.getRgn();
496 }
497 AntiHairLineRgn(pts, count, clipRgn, blitter);
498 }
499 }
500