SkScan_Hairline.cpp revision fbfcd5602128ec010c82cb733c9cdc0a3254f9f3 
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
36static bool canConvertFDot6ToFixed(SkFDot6 x) {
37    const int maxDot6 = SK_MaxS32 >> (16 - 6);
38    return SkAbs32(x) <= maxDot6;
39}
40
41void SkScan::HairLineRgn(const SkPoint& pt0, const SkPoint& pt1,
42                         const SkRegion* clip, SkBlitter* blitter) {
43    SkBlitterClipper    clipper;
44    SkRect  r;
45    SkIRect clipR, ptsR;
46    SkPoint pts[2] = { pt0, pt1 };
47
48#ifdef SK_SCALAR_IS_FLOAT
49    // We have to pre-clip the line to fit in a SkFixed, so we just chop
50    // the line. TODO find a way to actually draw beyond that range.
51    {
52        SkRect fixedBounds;
53        const SkScalar max = SkIntToScalar(32767);
54        fixedBounds.set(-max, -max, max, max);
55        if (!SkLineClipper::IntersectLine(pts, fixedBounds, pts)) {
56            return;
57        }
58    }
59#endif
60
61    if (clip) {
62        // Perform a clip in scalar space, so we catch huge values which might
63        // be missed after we convert to SkFDot6 (overflow)
64        r.set(clip->getBounds());
65        if (!SkLineClipper::IntersectLine(pts, r, pts)) {
66            return;
67        }
68    }
69
70    SkFDot6 x0 = SkScalarToFDot6(pts[0].fX);
71    SkFDot6 y0 = SkScalarToFDot6(pts[0].fY);
72    SkFDot6 x1 = SkScalarToFDot6(pts[1].fX);
73    SkFDot6 y1 = SkScalarToFDot6(pts[1].fY);
74
75    SkASSERT(canConvertFDot6ToFixed(x0));
76    SkASSERT(canConvertFDot6ToFixed(y0));
77    SkASSERT(canConvertFDot6ToFixed(x1));
78    SkASSERT(canConvertFDot6ToFixed(y1));
79
80    if (clip) {
81        // now perform clipping again, as the rounding to dot6 can wiggle us
82        // our rects are really dot6 rects, but since we've already used
83        // lineclipper, we know they will fit in 32bits (26.6)
84        const SkIRect& bounds = clip->getBounds();
85
86        clipR.set(SkIntToFDot6(bounds.fLeft), SkIntToFDot6(bounds.fTop),
87                  SkIntToFDot6(bounds.fRight), SkIntToFDot6(bounds.fBottom));
88        ptsR.set(x0, y0, x1, y1);
89        ptsR.sort();
90
91        // outset the right and bottom, to account for how hairlines are
92        // actually drawn, which may hit the pixel to the right or below of
93        // the coordinate
94        ptsR.fRight += SK_FDot6One;
95        ptsR.fBottom += SK_FDot6One;
96
97        if (!SkIRect::Intersects(ptsR, clipR)) {
98            return;
99        }
100        if (clip->isRect() && clipR.contains(ptsR)) {
101            clip = NULL;
102        } else {
103            blitter = clipper.apply(blitter, clip);
104        }
105    }
106
107    SkFDot6 dx = x1 - x0;
108    SkFDot6 dy = y1 - y0;
109
110    if (SkAbs32(dx) > SkAbs32(dy)) { // mostly horizontal
111        if (x0 > x1) {   // we want to go left-to-right
112            SkTSwap<SkFDot6>(x0, x1);
113            SkTSwap<SkFDot6>(y0, y1);
114        }
115        int ix0 = SkFDot6Round(x0);
116        int ix1 = SkFDot6Round(x1);
117        if (ix0 == ix1) {// too short to draw
118            return;
119        }
120
121        SkFixed slope = SkFixedDiv(dy, dx);
122        SkFixed startY = SkFDot6ToFixed(y0) + (slope * ((32 - x0) & 63) >> 6);
123
124        horiline(ix0, ix1, startY, slope, blitter);
125    } else {              // mostly vertical
126        if (y0 > y1) {   // we want to go top-to-bottom
127            SkTSwap<SkFDot6>(x0, x1);
128            SkTSwap<SkFDot6>(y0, y1);
129        }
130        int iy0 = SkFDot6Round(y0);
131        int iy1 = SkFDot6Round(y1);
132        if (iy0 == iy1) { // too short to draw
133            return;
134        }
135
136        SkFixed slope = SkFixedDiv(dx, dy);
137        SkFixed startX = SkFDot6ToFixed(x0) + (slope * ((32 - y0) & 63) >> 6);
138
139        vertline(iy0, iy1, startX, slope, blitter);
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)
146void 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
194static bool quad_too_curvy(const SkPoint pts[3]) {
195    return true;
196}
197
198static 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 = SkScalarCeil(dx);
208    int idy = SkScalarCeil(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
217static void hairquad(const SkPoint pts[3], const SkRegion* clip, SkBlitter* blitter, int level,
218                     void (*lineproc)(const SkPoint&, const SkPoint&, const SkRegion* clip, SkBlitter*))
219{
220#if 1
221    if (level > 0 && quad_too_curvy(pts))
222    {
223        SkPoint tmp[5];
224
225        SkChopQuadAtHalf(pts, tmp);
226        hairquad(tmp, clip, blitter, level - 1, lineproc);
227        hairquad(&tmp[2], clip, blitter, level - 1, lineproc);
228    }
229    else
230        lineproc(pts[0], pts[2], clip, blitter);
231#else
232    int count = 1 << level;
233    const SkScalar dt = SkFixedToScalar(SK_Fixed1 >> level);
234    SkScalar t = dt;
235    SkPoint prevPt = pts[0];
236    for (int i = 1; i < count; i++) {
237        SkPoint nextPt;
238        SkEvalQuadAt(pts, t, &nextPt);
239        lineproc(prevPt, nextPt, clip, blitter);
240        t += dt;
241        prevPt = nextPt;
242    }
243    // draw the last line explicitly to 1.0, in case t didn't match that exactly
244    lineproc(prevPt, pts[2], clip, blitter);
245#endif
246}
247
248static bool cubic_too_curvy(const SkPoint pts[4])
249{
250    return true;
251}
252
253static void haircubic(const SkPoint pts[4], const SkRegion* clip, SkBlitter* blitter, int level,
254                      void (*lineproc)(const SkPoint&, const SkPoint&, const SkRegion*, SkBlitter*))
255{
256    if (level > 0 && cubic_too_curvy(pts))
257    {
258        SkPoint tmp[7];
259
260        SkChopCubicAt(pts, tmp, SK_Scalar1/2);
261        haircubic(tmp, clip, blitter, level - 1, lineproc);
262        haircubic(&tmp[3], clip, blitter, level - 1, lineproc);
263    }
264    else
265        lineproc(pts[0], pts[3], clip, blitter);
266}
267
268#define kMaxCubicSubdivideLevel 6
269#define kMaxQuadSubdivideLevel  5
270
271static void hair_path(const SkPath& path, const SkRasterClip& rclip, SkBlitter* blitter,
272                      void (*lineproc)(const SkPoint&, const SkPoint&, const SkRegion*, SkBlitter*))
273{
274    if (path.isEmpty()) {
275        return;
276    }
277
278    SkAAClipBlitterWrapper wrap;
279    const SkIRect* clipR = NULL;
280    const SkRegion* clip = NULL;
281
282    {
283        SkIRect ibounds;
284        path.getBounds().roundOut(&ibounds);
285        ibounds.inset(-1, -1);
286
287        if (rclip.quickReject(ibounds)) {
288            return;
289        }
290        if (!rclip.quickContains(ibounds)) {
291            clipR = &rclip.getBounds();
292            if (rclip.isBW()) {
293                clip = &rclip.bwRgn();
294            } else {
295                wrap.init(rclip, blitter);
296                blitter = wrap.getBlitter();
297                clip = &wrap.getRgn();
298            }
299        }
300    }
301
302    SkPath::Iter    iter(path, false);
303    SkPoint         pts[4];
304    SkPath::Verb    verb;
305
306    while ((verb = iter.next(pts, false)) != SkPath::kDone_Verb) {
307        switch (verb) {
308            case SkPath::kLine_Verb:
309                lineproc(pts[0], pts[1], clip, blitter);
310                break;
311            case SkPath::kQuad_Verb: {
312                int d = compute_int_quad_dist(pts);
313                /*  quadratics approach the line connecting their start and end points
314                 4x closer with each subdivision, so we compute the number of
315                 subdivisions to be the minimum need to get that distance to be less
316                 than a pixel.
317                 */
318                int level = (33 - SkCLZ(d)) >> 1;
319    //          SkDebugf("----- distance %d computedLevel %d\n", d, computedLevel);
320                // sanity check on level (from the previous version)
321                if (level > kMaxQuadSubdivideLevel) {
322                    level = kMaxQuadSubdivideLevel;
323                }
324                hairquad(pts, clip, blitter, level, lineproc);
325                break;
326            }
327            case SkPath::kCubic_Verb:
328                haircubic(pts, clip, blitter, kMaxCubicSubdivideLevel, lineproc);
329                break;
330            default:
331                break;
332        }
333    }
334}
335
336void SkScan::HairPath(const SkPath& path, const SkRasterClip& clip,
337                      SkBlitter* blitter) {
338    hair_path(path, clip, blitter, SkScan::HairLineRgn);
339}
340
341void SkScan::AntiHairPath(const SkPath& path, const SkRasterClip& clip,
342                          SkBlitter* blitter) {
343    hair_path(path, clip, blitter, SkScan::AntiHairLineRgn);
344}
345
346///////////////////////////////////////////////////////////////////////////////
347
348void SkScan::FrameRect(const SkRect& r, const SkPoint& strokeSize,
349                       const SkRasterClip& clip, SkBlitter* blitter) {
350    SkASSERT(strokeSize.fX >= 0 && strokeSize.fY >= 0);
351
352    if (strokeSize.fX < 0 || strokeSize.fY < 0) {
353        return;
354    }
355
356    const SkScalar dx = strokeSize.fX;
357    const SkScalar dy = strokeSize.fY;
358    SkScalar rx = SkScalarHalf(dx);
359    SkScalar ry = SkScalarHalf(dy);
360    SkRect   outer, tmp;
361
362    outer.set(r.fLeft - rx, r.fTop - ry,
363                r.fRight + rx, r.fBottom + ry);
364
365    if (r.width() <= dx || r.height() <= dx) {
366        SkScan::FillRect(outer, clip, blitter);
367        return;
368    }
369
370    tmp.set(outer.fLeft, outer.fTop, outer.fRight, outer.fTop + dy);
371    SkScan::FillRect(tmp, clip, blitter);
372    tmp.fTop = outer.fBottom - dy;
373    tmp.fBottom = outer.fBottom;
374    SkScan::FillRect(tmp, clip, blitter);
375
376    tmp.set(outer.fLeft, outer.fTop + dy, outer.fLeft + dx, outer.fBottom - dy);
377    SkScan::FillRect(tmp, clip, blitter);
378    tmp.fLeft = outer.fRight - dx;
379    tmp.fRight = outer.fRight;
380    SkScan::FillRect(tmp, clip, blitter);
381}
382
383void SkScan::HairLine(const SkPoint& p0, const SkPoint& p1,
384                      const SkRasterClip& clip, SkBlitter* blitter) {
385    if (clip.isBW()) {
386        HairLineRgn(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.inset(-SK_ScalarHalf, -SK_ScalarHalf);
394        r.roundOut(&ir);
395
396        SkAAClipBlitterWrapper wrap;
397        if (!clip.quickContains(ir)) {
398            wrap.init(clip, blitter);
399            blitter = wrap.getBlitter();
400            clipRgn = &wrap.getRgn();
401        }
402        HairLineRgn(p0, p1, clipRgn, blitter);
403    }
404}
405
406void SkScan::AntiHairLine(const SkPoint& p0, const SkPoint& p1,
407                          const SkRasterClip& clip, SkBlitter* blitter) {
408    if (clip.isBW()) {
409        AntiHairLineRgn(p0, p1, &clip.bwRgn(), blitter);
410    } else {
411        const SkRegion* clipRgn = NULL;
412        SkRect r;
413        SkIRect ir;
414        r.set(p0.fX, p0.fY, p1.fX, p1.fY);
415        r.sort();
416        r.roundOut(&ir);
417        ir.inset(-1, -1);
418
419        SkAAClipBlitterWrapper wrap;
420        if (!clip.quickContains(ir)) {
421            wrap.init(clip, blitter);
422            blitter = wrap.getBlitter();
423            clipRgn = &wrap.getRgn();
424        }
425        AntiHairLineRgn(p0, p1, clipRgn, blitter);
426    }
427}
428