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
36void 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)
123void 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
171static bool quad_too_curvy(const SkPoint pts[3]) {
172    return true;
173}
174
175static 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
194static 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
225static bool cubic_too_curvy(const SkPoint pts[4])
226{
227    return true;
228}
229
230static 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
248static 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
313void SkScan::HairPath(const SkPath& path, const SkRasterClip& clip,
314                      SkBlitter* blitter) {
315    hair_path(path, clip, blitter, SkScan::HairLineRgn);
316}
317
318void SkScan::AntiHairPath(const SkPath& path, const SkRasterClip& clip,
319                          SkBlitter* blitter) {
320    hair_path(path, clip, blitter, SkScan::AntiHairLineRgn);
321}
322
323///////////////////////////////////////////////////////////////////////////////
324
325void 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
360void 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
383void 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