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