SkScan_Hairline.cpp revision 8a1c16ff38322f0210116fa7293eb8817c7e477e 
1/* libs/graphics/sgl/SkScan_Hairline.cpp
2**
3** Copyright 2006, The Android Open Source Project
4**
5** Licensed under the Apache License, Version 2.0 (the "License");
6** you may not use this file except in compliance with the License.
7** You may obtain a copy of the License at
8**
9**     http://www.apache.org/licenses/LICENSE-2.0
10**
11** Unless required by applicable law or agreed to in writing, software
12** distributed under the License is distributed on an "AS IS" BASIS,
13** WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
14** See the License for the specific language governing permissions and
15** limitations under the License.
16*/
17
18#include "SkScan.h"
19#include "SkBlitter.h"
20#include "SkRegion.h"
21#include "SkFDot6.h"
22
23static void horiline(int x, int stopx, SkFixed fy, SkFixed dy, SkBlitter* blitter)
24{
25    SkASSERT(x < stopx);
26
27    do {
28        blitter->blitH(x, fy >> 16, 1);
29        fy += dy;
30    } while (++x < stopx);
31}
32
33static void vertline(int y, int stopy, SkFixed fx, SkFixed dx, SkBlitter* blitter)
34{
35    SkASSERT(y < stopy);
36
37    do {
38        blitter->blitH(fx >> 16, y, 1);
39        fx += dx;
40    } while (++y < stopy);
41}
42
43void SkScan::HairLine(const SkPoint& pt0, const SkPoint& pt1, const SkRegion* clip, SkBlitter* blitter)
44{
45    SkBlitterClipper    clipper;
46
47    SkFDot6 x0 = SkScalarToFDot6(pt0.fX);
48    SkFDot6 y0 = SkScalarToFDot6(pt0.fY);
49    SkFDot6 x1 = SkScalarToFDot6(pt1.fX);
50    SkFDot6 y1 = SkScalarToFDot6(pt1.fY);
51
52    if (clip)
53    {
54        SkRect      r;
55        SkIRect     ir;
56        SkPoint     pts[2];
57
58        pts[0] = pt0;
59        pts[1] = pt1;
60        r.set(pts, 2);
61        r.roundOut(&ir);
62
63        // if we're given a horizontal or vertical line
64        // this rect could be empty (in area), in which case
65        // clip->quickReject() will always return true.
66        // hence we bloat the rect to avoid that case
67        if (ir.width() == 0)
68            ir.fRight += 1;
69        if (ir.height() == 0)
70            ir.fBottom += 1;
71
72        if (clip->quickReject(ir))
73            return;
74        if (clip->quickContains(ir))
75            clip = NULL;
76        else
77        {
78            blitter = clipper.apply(blitter, clip);
79        }
80    }
81
82    SkFDot6 dx = x1 - x0;
83    SkFDot6 dy = y1 - y0;
84
85    if (SkAbs32(dx) > SkAbs32(dy))  // mostly horizontal
86    {
87        if (x0 > x1)    // we want to go left-to-right
88        {
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        SkFixed slope = SkFixedDiv(dy, dx);
98        SkFixed startY = SkFDot6ToFixed(y0) + (slope * ((32 - x0) & 63) >> 6);
99
100        horiline(ix0, ix1, startY, slope, blitter);
101    }
102    else                // mostly vertical
103    {
104        if (y0 > y1)    // we want to go top-to-bottom
105        {
106            SkTSwap<SkFDot6>(x0, x1);
107            SkTSwap<SkFDot6>(y0, y1);
108        }
109        int iy0 = SkFDot6Round(y0);
110        int iy1 = SkFDot6Round(y1);
111        if (iy0 == iy1) // too short to draw
112            return;
113
114        SkFixed slope = SkFixedDiv(dx, dy);
115        SkFixed startX = SkFDot6ToFixed(x0) + (slope * ((32 - y0) & 63) >> 6);
116
117        vertline(iy0, iy1, startX, slope, blitter);
118    }
119}
120
121// we don't just draw 4 lines, 'cause that can leave a gap in the bottom-right
122// and double-hit the top-left.
123void SkScan::HairRect(const SkRect& rect, const SkRegion* clip, SkBlitter* blitter)
124{
125    SkBlitterClipper    clipper;
126    SkIRect             r;
127
128    r.set(SkScalarToFixed(rect.fLeft) >> 16,
129          SkScalarToFixed(rect.fTop) >> 16,
130          (SkScalarToFixed(rect.fRight) >> 16) + 1,
131          (SkScalarToFixed(rect.fBottom) >> 16) + 1);
132
133    if (clip)
134    {
135        if (clip->quickReject(r))
136            return;
137        if (!clip->quickContains(r))
138            blitter = clipper.apply(blitter, clip);
139    }
140
141    int width = r.width();
142    int height = r.height();
143
144    if ((width | height) == 0)
145        return;
146    if (width <= 2 || height <= 2)
147    {
148        blitter->blitRect(r.fLeft, r.fTop, width, height);
149        return;
150    }
151    // if we get here, we know we have 4 segments to draw
152    blitter->blitH(r.fLeft, r.fTop, width);                     // top
153    blitter->blitRect(r.fLeft, r.fTop + 1, 1, height - 2);      // left
154    blitter->blitRect(r.fRight - 1, r.fTop + 1, 1, height - 2); // right
155    blitter->blitH(r.fLeft, r.fBottom - 1, width);              // bottom
156}
157
158/////////////////////////////////////////////////////////////////////////////////////////////////
159
160#include "SkPath.h"
161#include "SkGeometry.h"
162
163static bool quad_too_curvy(const SkPoint pts[3])
164{
165    return true;
166}
167
168static int compute_int_quad_dist(const SkPoint pts[3]) {
169    // compute the vector between the control point ([1]) and the middle of the
170    // line connecting the start and end ([0] and [2])
171    SkScalar dx = SkScalarHalf(pts[0].fX + pts[2].fX) - pts[1].fX;
172    SkScalar dy = SkScalarHalf(pts[0].fY + pts[2].fY) - pts[1].fY;
173    // we want everyone to be positive
174    dx = SkScalarAbs(dx);
175    dy = SkScalarAbs(dy);
176    // convert to whole pixel values (use ceiling to be conservative)
177    int idx = SkScalarCeil(dx);
178    int idy = SkScalarCeil(dy);
179    // use the cheap approx for distance
180    if (idx > idy) {
181        return idx + (idy >> 1);
182    } else {
183        return idy + (idx >> 1);
184    }
185}
186
187static void hairquad(const SkPoint pts[3], const SkRegion* clip, SkBlitter* blitter, int level,
188                     void (*lineproc)(const SkPoint&, const SkPoint&, const SkRegion* clip, SkBlitter*))
189{
190#if 1
191    if (level > 0 && quad_too_curvy(pts))
192    {
193        SkPoint tmp[5];
194
195        SkChopQuadAtHalf(pts, tmp);
196        hairquad(tmp, clip, blitter, level - 1, lineproc);
197        hairquad(&tmp[2], clip, blitter, level - 1, lineproc);
198    }
199    else
200        lineproc(pts[0], pts[2], clip, blitter);
201#else
202    int count = 1 << level;
203    const SkScalar dt = SkFixedToScalar(SK_Fixed1 >> level);
204    SkScalar t = dt;
205    SkPoint prevPt = pts[0];
206    for (int i = 1; i < count; i++) {
207        SkPoint nextPt;
208        SkEvalQuadAt(pts, t, &nextPt);
209        lineproc(prevPt, nextPt, clip, blitter);
210        t += dt;
211        prevPt = nextPt;
212    }
213    // draw the last line explicitly to 1.0, in case t didn't match that exactly
214    lineproc(prevPt, pts[2], clip, blitter);
215#endif
216}
217
218static bool cubic_too_curvy(const SkPoint pts[4])
219{
220    return true;
221}
222
223static void haircubic(const SkPoint pts[4], const SkRegion* clip, SkBlitter* blitter, int level,
224                      void (*lineproc)(const SkPoint&, const SkPoint&, const SkRegion*, SkBlitter*))
225{
226    if (level > 0 && cubic_too_curvy(pts))
227    {
228        SkPoint tmp[7];
229
230        SkChopCubicAt(pts, tmp, SK_Scalar1/2);
231        haircubic(tmp, clip, blitter, level - 1, lineproc);
232        haircubic(&tmp[3], clip, blitter, level - 1, lineproc);
233    }
234    else
235        lineproc(pts[0], pts[3], clip, blitter);
236}
237
238#define kMaxCubicSubdivideLevel 6
239#define kMaxQuadSubdivideLevel  5
240
241static void hair_path(const SkPath& path, const SkRegion* clip, SkBlitter* blitter,
242                      void (*lineproc)(const SkPoint&, const SkPoint&, const SkRegion*, SkBlitter*))
243{
244    if (path.isEmpty())
245        return;
246
247    const SkIRect* clipR = NULL;
248
249    if (clip)
250    {
251        SkRect      bounds;
252        SkIRect     ibounds;
253
254        path.computeBounds(&bounds, SkPath::kFast_BoundsType);
255        bounds.roundOut(&ibounds);
256        ibounds.inset(-1, -1);
257
258        if (clip->quickReject(ibounds))
259            return;
260
261        if (clip->quickContains(ibounds))
262            clip = NULL;
263        else
264            clipR = &clip->getBounds();
265    }
266
267    SkPath::Iter    iter(path, false);
268    SkPoint         pts[4];
269    SkPath::Verb    verb;
270
271    while ((verb = iter.next(pts)) != SkPath::kDone_Verb)
272    {
273        switch (verb) {
274        case SkPath::kLine_Verb:
275            lineproc(pts[0], pts[1], clip, blitter);
276            break;
277        case SkPath::kQuad_Verb: {
278            int d = compute_int_quad_dist(pts);
279            /*  quadratics approach the line connecting their start and end points
280             4x closer with each subdivision, so we compute the number of
281             subdivisions to be the minimum need to get that distance to be less
282             than a pixel.
283             */
284            int level = (33 - SkCLZ(d)) >> 1;
285//          SkDebugf("----- distance %d computedLevel %d\n", d, computedLevel);
286            // sanity check on level (from the previous version)
287            if (level > kMaxQuadSubdivideLevel) {
288                level = kMaxQuadSubdivideLevel;
289            }
290            hairquad(pts, clip, blitter, level, lineproc);
291            break;
292        }
293        case SkPath::kCubic_Verb:
294            haircubic(pts, clip, blitter, kMaxCubicSubdivideLevel, lineproc);
295            break;
296        default:
297            break;
298        }
299    }
300}
301
302void SkScan::HairPath(const SkPath& path, const SkRegion* clip, SkBlitter* blitter)
303{
304    hair_path(path, clip, blitter, SkScan::HairLine);
305}
306
307void SkScan::AntiHairPath(const SkPath& path, const SkRegion* clip, SkBlitter* blitter)
308{
309    hair_path(path, clip, blitter, SkScan::AntiHairLine);
310}
311
312////////////////////////////////////////////////////////////////////////////////
313
314void SkScan::FrameRect(const SkRect& r, SkScalar diameter, const SkRegion* clip, SkBlitter* blitter)
315{
316    SkASSERT(diameter > 0);
317
318    if (r.isEmpty())
319        return;
320
321    SkScalar radius = diameter / 2;
322    SkRect   outer, tmp;
323
324    outer.set(  r.fLeft - radius, r.fTop - radius,
325                r.fRight + radius, r.fBottom + radius);
326
327    if (r.width() <= diameter || r.height() <= diameter)
328    {
329        SkScan::FillRect(outer, clip, blitter);
330        return;
331    }
332
333    tmp.set(outer.fLeft, outer.fTop, outer.fRight, outer.fTop + diameter);
334    SkScan::FillRect(tmp, clip, blitter);
335    tmp.fTop = outer.fBottom - diameter;
336    tmp.fBottom = outer.fBottom;
337    SkScan::FillRect(tmp, clip, blitter);
338
339    tmp.set(outer.fLeft, outer.fTop + diameter, outer.fLeft + diameter, outer.fBottom - diameter);
340    SkScan::FillRect(tmp, clip, blitter);
341    tmp.fLeft = outer.fRight - diameter;
342    tmp.fRight = outer.fRight;
343    SkScan::FillRect(tmp, clip, blitter);
344}
345
346