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