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    // We have to pre-clip the line to fit in a SkFixed, so we just chop
51    // the line. TODO find a way to actually draw beyond that range.
52    {
53        SkRect fixedBounds;
54        const SkScalar max = SkIntToScalar(32767);
55        fixedBounds.set(-max, -max, max, max);
56        if (!SkLineClipper::IntersectLine(pts, fixedBounds, pts)) {
57            return;
58        }
59    }
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 int compute_int_quad_dist(const SkPoint pts[3]) {
195    // compute the vector between the control point ([1]) and the middle of the
196    // line connecting the start and end ([0] and [2])
197    SkScalar dx = SkScalarHalf(pts[0].fX + pts[2].fX) - pts[1].fX;
198    SkScalar dy = SkScalarHalf(pts[0].fY + pts[2].fY) - pts[1].fY;
199    // we want everyone to be positive
200    dx = SkScalarAbs(dx);
201    dy = SkScalarAbs(dy);
202    // convert to whole pixel values (use ceiling to be conservative)
203    int idx = SkScalarCeilToInt(dx);
204    int idy = SkScalarCeilToInt(dy);
205    // use the cheap approx for distance
206    if (idx > idy) {
207        return idx + (idy >> 1);
208    } else {
209        return idy + (idx >> 1);
210    }
211}
212
213typedef void (*LineProc)(const SkPoint&, const SkPoint&, const SkRegion*,
214                         SkBlitter*);
215
216static void hairquad(const SkPoint pts[3], const SkRegion* clip,
217                     SkBlitter* blitter, int level, LineProc lineproc) {
218    if (level > 0) {
219        SkPoint tmp[5];
220
221        SkChopQuadAtHalf(pts, tmp);
222        hairquad(tmp, clip, blitter, level - 1, lineproc);
223        hairquad(&tmp[2], clip, blitter, level - 1, lineproc);
224    } else {
225        lineproc(pts[0], pts[2], clip, blitter);
226    }
227}
228
229static void haircubic(const SkPoint pts[4], const SkRegion* clip,
230                      SkBlitter* blitter, int level, LineProc lineproc) {
231    if (level > 0) {
232        SkPoint tmp[7];
233
234        SkChopCubicAt(pts, tmp, SK_Scalar1/2);
235        haircubic(tmp, clip, blitter, level - 1, lineproc);
236        haircubic(&tmp[3], clip, blitter, level - 1, lineproc);
237    } else {
238        lineproc(pts[0], pts[3], clip, blitter);
239    }
240}
241
242#define kMaxCubicSubdivideLevel 6
243#define kMaxQuadSubdivideLevel  5
244
245static int compute_quad_level(const SkPoint pts[3]) {
246    int d = compute_int_quad_dist(pts);
247    /*  quadratics approach the line connecting their start and end points
248     4x closer with each subdivision, so we compute the number of
249     subdivisions to be the minimum need to get that distance to be less
250     than a pixel.
251     */
252    int level = (33 - SkCLZ(d)) >> 1;
253    // sanity check on level (from the previous version)
254    if (level > kMaxQuadSubdivideLevel) {
255        level = kMaxQuadSubdivideLevel;
256    }
257    return level;
258}
259
260static void hair_path(const SkPath& path, const SkRasterClip& rclip,
261                      SkBlitter* blitter, LineProc lineproc) {
262    if (path.isEmpty()) {
263        return;
264    }
265
266    SkAAClipBlitterWrapper wrap;
267    const SkRegion* clip = NULL;
268
269    {
270        SkIRect ibounds;
271        path.getBounds().roundOut(&ibounds);
272        ibounds.inset(-1, -1);
273
274        if (rclip.quickReject(ibounds)) {
275            return;
276        }
277        if (!rclip.quickContains(ibounds)) {
278            if (rclip.isBW()) {
279                clip = &rclip.bwRgn();
280            } else {
281                wrap.init(rclip, blitter);
282                blitter = wrap.getBlitter();
283                clip = &wrap.getRgn();
284            }
285        }
286    }
287
288    SkPath::Iter    iter(path, false);
289    SkPoint         pts[4];
290    SkPath::Verb    verb;
291    SkAutoConicToQuads converter;
292
293    while ((verb = iter.next(pts, false)) != SkPath::kDone_Verb) {
294        switch (verb) {
295            case SkPath::kMove_Verb:
296                break;
297            case SkPath::kLine_Verb:
298                lineproc(pts[0], pts[1], clip, blitter);
299                break;
300            case SkPath::kQuad_Verb:
301                hairquad(pts, clip, blitter, compute_quad_level(pts), lineproc);
302                break;
303            case SkPath::kConic_Verb: {
304                // how close should the quads be to the original conic?
305                const SkScalar tol = SK_Scalar1 / 4;
306                const SkPoint* quadPts = converter.computeQuads(pts,
307                                                       iter.conicWeight(), tol);
308                for (int i = 0; i < converter.countQuads(); ++i) {
309                    int level = compute_quad_level(quadPts);
310                    hairquad(quadPts, clip, blitter, level, lineproc);
311                    quadPts += 2;
312                }
313                break;
314            }
315            case SkPath::kCubic_Verb:
316                haircubic(pts, clip, blitter, kMaxCubicSubdivideLevel, lineproc);
317                break;
318            case SkPath::kClose_Verb:
319                break;
320            case SkPath::kDone_Verb:
321                break;
322        }
323    }
324}
325
326void SkScan::HairPath(const SkPath& path, const SkRasterClip& clip,
327                      SkBlitter* blitter) {
328    hair_path(path, clip, blitter, SkScan::HairLineRgn);
329}
330
331void SkScan::AntiHairPath(const SkPath& path, const SkRasterClip& clip,
332                          SkBlitter* blitter) {
333    hair_path(path, clip, blitter, SkScan::AntiHairLineRgn);
334}
335
336///////////////////////////////////////////////////////////////////////////////
337
338void SkScan::FrameRect(const SkRect& r, const SkPoint& strokeSize,
339                       const SkRasterClip& clip, SkBlitter* blitter) {
340    SkASSERT(strokeSize.fX >= 0 && strokeSize.fY >= 0);
341
342    if (strokeSize.fX < 0 || strokeSize.fY < 0) {
343        return;
344    }
345
346    const SkScalar dx = strokeSize.fX;
347    const SkScalar dy = strokeSize.fY;
348    SkScalar rx = SkScalarHalf(dx);
349    SkScalar ry = SkScalarHalf(dy);
350    SkRect   outer, tmp;
351
352    outer.set(r.fLeft - rx, r.fTop - ry,
353                r.fRight + rx, r.fBottom + ry);
354
355    if (r.width() <= dx || r.height() <= dx) {
356        SkScan::FillRect(outer, clip, blitter);
357        return;
358    }
359
360    tmp.set(outer.fLeft, outer.fTop, outer.fRight, outer.fTop + dy);
361    SkScan::FillRect(tmp, clip, blitter);
362    tmp.fTop = outer.fBottom - dy;
363    tmp.fBottom = outer.fBottom;
364    SkScan::FillRect(tmp, clip, blitter);
365
366    tmp.set(outer.fLeft, outer.fTop + dy, outer.fLeft + dx, outer.fBottom - dy);
367    SkScan::FillRect(tmp, clip, blitter);
368    tmp.fLeft = outer.fRight - dx;
369    tmp.fRight = outer.fRight;
370    SkScan::FillRect(tmp, clip, blitter);
371}
372
373void SkScan::HairLine(const SkPoint& p0, const SkPoint& p1,
374                      const SkRasterClip& clip, SkBlitter* blitter) {
375    if (clip.isBW()) {
376        HairLineRgn(p0, p1, &clip.bwRgn(), blitter);
377    } else {
378        const SkRegion* clipRgn = NULL;
379        SkRect r;
380        SkIRect ir;
381        r.set(p0.fX, p0.fY, p1.fX, p1.fY);
382        r.sort();
383        r.inset(-SK_ScalarHalf, -SK_ScalarHalf);
384        r.roundOut(&ir);
385
386        SkAAClipBlitterWrapper wrap;
387        if (!clip.quickContains(ir)) {
388            wrap.init(clip, blitter);
389            blitter = wrap.getBlitter();
390            clipRgn = &wrap.getRgn();
391        }
392        HairLineRgn(p0, p1, clipRgn, blitter);
393    }
394}
395
396void SkScan::AntiHairLine(const SkPoint& p0, const SkPoint& p1,
397                          const SkRasterClip& clip, SkBlitter* blitter) {
398    if (clip.isBW()) {
399        AntiHairLineRgn(p0, p1, &clip.bwRgn(), blitter);
400    } else {
401        const SkRegion* clipRgn = NULL;
402        SkRect r;
403        SkIRect ir;
404        r.set(p0.fX, p0.fY, p1.fX, p1.fY);
405        r.sort();
406        r.roundOut(&ir);
407        ir.inset(-1, -1);
408
409        SkAAClipBlitterWrapper wrap;
410        if (!clip.quickContains(ir)) {
411            wrap.init(clip, blitter);
412            blitter = wrap.getBlitter();
413            clipRgn = &wrap.getRgn();
414        }
415        AntiHairLineRgn(p0, p1, clipRgn, blitter);
416    }
417}
418