1/*
2 * Copyright 2006 The Android Open Source Project
3 *
4 * Use of this source code is governed by a BSD-style license that can be
5 * found in the LICENSE file.
6 */
7
8#include "SkScan.h"
9#include "SkBlitter.h"
10#include "SkRasterClip.h"
11#include "SkFDot6.h"
12#include "SkLineClipper.h"
13
14static void horiline(int x, int stopx, SkFixed fy, SkFixed dy,
15                     SkBlitter* blitter) {
16    SkASSERT(x < stopx);
17
18    do {
19        blitter->blitH(x, fy >> 16, 1);
20        fy += dy;
21    } while (++x < stopx);
22}
23
24static void vertline(int y, int stopy, SkFixed fx, SkFixed dx,
25                     SkBlitter* blitter) {
26    SkASSERT(y < stopy);
27
28    do {
29        blitter->blitH(fx >> 16, y, 1);
30        fx += dx;
31    } while (++y < stopy);
32}
33
34#ifdef SK_DEBUG
35static bool canConvertFDot6ToFixed(SkFDot6 x) {
36    const int maxDot6 = SK_MaxS32 >> (16 - 6);
37    return SkAbs32(x) <= maxDot6;
38}
39#endif
40
41void SkScan::HairLineRgn(const SkPoint array[], int arrayCount, const SkRegion* clip,
42                         SkBlitter* origBlitter) {
43    SkBlitterClipper    clipper;
44    SkIRect clipR, ptsR;
45
46    const SkScalar max = SkIntToScalar(32767);
47    const SkRect fixedBounds = SkRect::MakeLTRB(-max, -max, max, max);
48
49    SkRect clipBounds;
50    if (clip) {
51        clipBounds.set(clip->getBounds());
52    }
53
54    for (int i = 0; i < arrayCount - 1; ++i) {
55        SkBlitter* blitter = origBlitter;
56
57        SkPoint pts[2];
58
59        // We have to pre-clip the line to fit in a SkFixed, so we just chop
60        // the line. TODO find a way to actually draw beyond that range.
61        if (!SkLineClipper::IntersectLine(&array[i], fixedBounds, pts)) {
62            continue;
63        }
64
65        // Perform a clip in scalar space, so we catch huge values which might
66        // be missed after we convert to SkFDot6 (overflow)
67        if (clip && !SkLineClipper::IntersectLine(pts, clipBounds, pts)) {
68            continue;
69        }
70
71        SkFDot6 x0 = SkScalarToFDot6(pts[0].fX);
72        SkFDot6 y0 = SkScalarToFDot6(pts[0].fY);
73        SkFDot6 x1 = SkScalarToFDot6(pts[1].fX);
74        SkFDot6 y1 = SkScalarToFDot6(pts[1].fY);
75
76        SkASSERT(canConvertFDot6ToFixed(x0));
77        SkASSERT(canConvertFDot6ToFixed(y0));
78        SkASSERT(canConvertFDot6ToFixed(x1));
79        SkASSERT(canConvertFDot6ToFixed(y1));
80
81        if (clip) {
82            // now perform clipping again, as the rounding to dot6 can wiggle us
83            // our rects are really dot6 rects, but since we've already used
84            // lineclipper, we know they will fit in 32bits (26.6)
85            const SkIRect& bounds = clip->getBounds();
86
87            clipR.set(SkIntToFDot6(bounds.fLeft), SkIntToFDot6(bounds.fTop),
88                      SkIntToFDot6(bounds.fRight), SkIntToFDot6(bounds.fBottom));
89            ptsR.set(x0, y0, x1, y1);
90            ptsR.sort();
91
92            // outset the right and bottom, to account for how hairlines are
93            // actually drawn, which may hit the pixel to the right or below of
94            // the coordinate
95            ptsR.fRight += SK_FDot6One;
96            ptsR.fBottom += SK_FDot6One;
97
98            if (!SkIRect::Intersects(ptsR, clipR)) {
99                continue;
100            }
101            if (!clip->isRect() || !clipR.contains(ptsR)) {
102                blitter = clipper.apply(origBlitter, clip);
103            }
104        }
105
106        SkFDot6 dx = x1 - x0;
107        SkFDot6 dy = y1 - y0;
108
109        if (SkAbs32(dx) > SkAbs32(dy)) { // mostly horizontal
110            if (x0 > x1) {   // we want to go left-to-right
111                SkTSwap<SkFDot6>(x0, x1);
112                SkTSwap<SkFDot6>(y0, y1);
113            }
114            int ix0 = SkFDot6Round(x0);
115            int ix1 = SkFDot6Round(x1);
116            if (ix0 == ix1) {// too short to draw
117                continue;
118            }
119
120            SkFixed slope = SkFixedDiv(dy, dx);
121            SkFixed startY = SkFDot6ToFixed(y0) + (slope * ((32 - x0) & 63) >> 6);
122
123            horiline(ix0, ix1, startY, slope, blitter);
124        } else {              // mostly vertical
125            if (y0 > y1) {   // we want to go top-to-bottom
126                SkTSwap<SkFDot6>(x0, x1);
127                SkTSwap<SkFDot6>(y0, y1);
128            }
129            int iy0 = SkFDot6Round(y0);
130            int iy1 = SkFDot6Round(y1);
131            if (iy0 == iy1) { // too short to draw
132                continue;
133            }
134
135            SkFixed slope = SkFixedDiv(dx, dy);
136            SkFixed startX = SkFDot6ToFixed(x0) + (slope * ((32 - y0) & 63) >> 6);
137
138            vertline(iy0, iy1, startX, slope, blitter);
139        }
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#include "SkNx.h"
194
195#define kMaxCubicSubdivideLevel 6
196#define kMaxQuadSubdivideLevel  5
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 = SkScalarCeilToInt(dx);
208    int idy = SkScalarCeilToInt(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,
218                     SkBlitter* blitter, int level, SkScan::HairRgnProc lineproc) {
219    SkASSERT(level <= kMaxQuadSubdivideLevel);
220
221    SkPoint coeff[3];
222    SkQuadToCoeff(pts, coeff);
223
224    const int lines = 1 << level;
225    Sk2s t(0);
226    Sk2s dt(SK_Scalar1 / lines);
227
228    SkPoint tmp[(1 << kMaxQuadSubdivideLevel) + 1];
229    SkASSERT((unsigned)lines < SK_ARRAY_COUNT(tmp));
230
231    tmp[0] = pts[0];
232    Sk2s A = Sk2s::Load(&coeff[0].fX);
233    Sk2s B = Sk2s::Load(&coeff[1].fX);
234    Sk2s C = Sk2s::Load(&coeff[2].fX);
235    for (int i = 1; i < lines; ++i) {
236        t += dt;
237        ((A * t + B) * t + C).store(&tmp[i].fX);
238    }
239    tmp[lines] = pts[2];
240    lineproc(tmp, lines + 1, clip, blitter);
241}
242
243static inline Sk2s abs(const Sk2s& value) {
244    return Sk2s::Max(value, -value);
245}
246
247static inline SkScalar max_component(const Sk2s& value) {
248    SkScalar components[2];
249    value.store(components);
250    return SkTMax(components[0], components[1]);
251}
252
253static inline int compute_cubic_segs(const SkPoint pts[4]) {
254    Sk2s p0 = from_point(pts[0]);
255    Sk2s p1 = from_point(pts[1]);
256    Sk2s p2 = from_point(pts[2]);
257    Sk2s p3 = from_point(pts[3]);
258
259    const Sk2s oneThird(1.0f / 3.0f);
260    const Sk2s twoThird(2.0f / 3.0f);
261
262    Sk2s p13 = oneThird * p3 + twoThird * p0;
263    Sk2s p23 = oneThird * p0 + twoThird * p3;
264
265    SkScalar diff = max_component(Sk2s::Max(abs(p1 - p13), abs(p2 - p23)));
266    SkScalar tol = SK_Scalar1 / 8;
267
268    for (int i = 0; i < kMaxCubicSubdivideLevel; ++i) {
269        if (diff < tol) {
270            return 1 << i;
271        }
272        tol *= 4;
273    }
274    return 1 << kMaxCubicSubdivideLevel;
275}
276
277static bool lt_90(SkPoint p0, SkPoint pivot, SkPoint p2) {
278    return SkVector::DotProduct(p0 - pivot, p2 - pivot) >= 0;
279}
280
281// The off-curve points are "inside" the limits of the on-curve pts
282static bool quick_cubic_niceness_check(const SkPoint pts[4]) {
283    return lt_90(pts[1], pts[0], pts[3]) &&
284           lt_90(pts[2], pts[0], pts[3]) &&
285           lt_90(pts[1], pts[3], pts[0]) &&
286           lt_90(pts[2], pts[3], pts[0]);
287}
288
289static void hair_cubic(const SkPoint pts[4], const SkRegion* clip, SkBlitter* blitter,
290                       SkScan::HairRgnProc lineproc) {
291    const int lines = compute_cubic_segs(pts);
292    SkASSERT(lines > 0);
293    if (1 == lines) {
294        SkPoint tmp[2] = { pts[0], pts[3] };
295        lineproc(tmp, 2, clip, blitter);
296        return;
297    }
298
299    SkPoint coeff[4];
300    SkCubicToCoeff(pts, coeff);
301
302    const Sk2s dt(SK_Scalar1 / lines);
303    Sk2s t(0);
304
305    SkPoint tmp[(1 << kMaxCubicSubdivideLevel) + 1];
306    SkASSERT((unsigned)lines < SK_ARRAY_COUNT(tmp));
307
308    tmp[0] = pts[0];
309    Sk2s A = Sk2s::Load(&coeff[0].fX);
310    Sk2s B = Sk2s::Load(&coeff[1].fX);
311    Sk2s C = Sk2s::Load(&coeff[2].fX);
312    Sk2s D = Sk2s::Load(&coeff[3].fX);
313    for (int i = 1; i < lines; ++i) {
314        t += dt;
315        (((A * t + B) * t + C) * t + D).store(&tmp[i].fX);
316    }
317    tmp[lines] = pts[3];
318    lineproc(tmp, lines + 1, clip, blitter);
319}
320
321static inline void haircubic(const SkPoint pts[4], const SkRegion* clip,
322                      SkBlitter* blitter, int level, SkScan::HairRgnProc lineproc) {
323    if (quick_cubic_niceness_check(pts)) {
324        hair_cubic(pts, clip, blitter, lineproc);
325    } else {
326        SkPoint  tmp[13];
327        SkScalar tValues[3];
328
329        int count = SkChopCubicAtMaxCurvature(pts, tmp, tValues);
330        for (int i = 0; i < count; i++) {
331            hair_cubic(&tmp[i * 3], clip, blitter, lineproc);
332        }
333    }
334}
335
336static int compute_quad_level(const SkPoint pts[3]) {
337    int d = compute_int_quad_dist(pts);
338    /*  quadratics approach the line connecting their start and end points
339     4x closer with each subdivision, so we compute the number of
340     subdivisions to be the minimum need to get that distance to be less
341     than a pixel.
342     */
343    int level = (33 - SkCLZ(d)) >> 1;
344    // sanity check on level (from the previous version)
345    if (level > kMaxQuadSubdivideLevel) {
346        level = kMaxQuadSubdivideLevel;
347    }
348    return level;
349}
350
351static void hair_path(const SkPath& path, const SkRasterClip& rclip, SkBlitter* blitter,
352                      SkScan::HairRgnProc lineproc) {
353    if (path.isEmpty()) {
354        return;
355    }
356
357    SkAAClipBlitterWrapper wrap;
358    const SkRegion* clip = NULL;
359
360    {
361        const SkIRect ibounds = path.getBounds().roundOut().makeOutset(1, 1);
362
363        if (rclip.quickReject(ibounds)) {
364            return;
365        }
366        if (!rclip.quickContains(ibounds)) {
367            if (rclip.isBW()) {
368                clip = &rclip.bwRgn();
369            } else {
370                wrap.init(rclip, blitter);
371                blitter = wrap.getBlitter();
372                clip = &wrap.getRgn();
373            }
374        }
375    }
376
377    SkPath::Iter    iter(path, false);
378    SkPoint         pts[4];
379    SkPath::Verb    verb;
380    SkAutoConicToQuads converter;
381
382    while ((verb = iter.next(pts, false)) != SkPath::kDone_Verb) {
383        switch (verb) {
384            case SkPath::kMove_Verb:
385                break;
386            case SkPath::kLine_Verb:
387                lineproc(pts, 2, clip, blitter);
388                break;
389            case SkPath::kQuad_Verb:
390                hairquad(pts, clip, blitter, compute_quad_level(pts), lineproc);
391                break;
392            case SkPath::kConic_Verb: {
393                // how close should the quads be to the original conic?
394                const SkScalar tol = SK_Scalar1 / 4;
395                const SkPoint* quadPts = converter.computeQuads(pts,
396                                                       iter.conicWeight(), tol);
397                for (int i = 0; i < converter.countQuads(); ++i) {
398                    int level = compute_quad_level(quadPts);
399                    hairquad(quadPts, clip, blitter, level, lineproc);
400                    quadPts += 2;
401                }
402                break;
403            }
404            case SkPath::kCubic_Verb: {
405                haircubic(pts, clip, blitter, kMaxCubicSubdivideLevel, lineproc);
406            } break;
407            case SkPath::kClose_Verb:
408                break;
409            case SkPath::kDone_Verb:
410                break;
411        }
412    }
413}
414
415void SkScan::HairPath(const SkPath& path, const SkRasterClip& clip, SkBlitter* blitter) {
416    hair_path(path, clip, blitter, SkScan::HairLineRgn);
417}
418
419void SkScan::AntiHairPath(const SkPath& path, const SkRasterClip& clip, SkBlitter* blitter) {
420    hair_path(path, clip, blitter, SkScan::AntiHairLineRgn);
421}
422
423///////////////////////////////////////////////////////////////////////////////
424
425void SkScan::FrameRect(const SkRect& r, const SkPoint& strokeSize,
426                       const SkRasterClip& clip, SkBlitter* blitter) {
427    SkASSERT(strokeSize.fX >= 0 && strokeSize.fY >= 0);
428
429    if (strokeSize.fX < 0 || strokeSize.fY < 0) {
430        return;
431    }
432
433    const SkScalar dx = strokeSize.fX;
434    const SkScalar dy = strokeSize.fY;
435    SkScalar rx = SkScalarHalf(dx);
436    SkScalar ry = SkScalarHalf(dy);
437    SkRect   outer, tmp;
438
439    outer.set(r.fLeft - rx, r.fTop - ry,
440                r.fRight + rx, r.fBottom + ry);
441
442    if (r.width() <= dx || r.height() <= dx) {
443        SkScan::FillRect(outer, clip, blitter);
444        return;
445    }
446
447    tmp.set(outer.fLeft, outer.fTop, outer.fRight, outer.fTop + dy);
448    SkScan::FillRect(tmp, clip, blitter);
449    tmp.fTop = outer.fBottom - dy;
450    tmp.fBottom = outer.fBottom;
451    SkScan::FillRect(tmp, clip, blitter);
452
453    tmp.set(outer.fLeft, outer.fTop + dy, outer.fLeft + dx, outer.fBottom - dy);
454    SkScan::FillRect(tmp, clip, blitter);
455    tmp.fLeft = outer.fRight - dx;
456    tmp.fRight = outer.fRight;
457    SkScan::FillRect(tmp, clip, blitter);
458}
459
460void SkScan::HairLine(const SkPoint pts[], int count, const SkRasterClip& clip,
461                      SkBlitter* blitter) {
462    if (clip.isBW()) {
463        HairLineRgn(pts, count, &clip.bwRgn(), blitter);
464    } else {
465        const SkRegion* clipRgn = NULL;
466
467        SkRect r;
468        r.set(pts, count);
469        r.outset(SK_ScalarHalf, SK_ScalarHalf);
470
471        SkAAClipBlitterWrapper wrap;
472        if (!clip.quickContains(r.roundOut())) {
473            wrap.init(clip, blitter);
474            blitter = wrap.getBlitter();
475            clipRgn = &wrap.getRgn();
476        }
477        HairLineRgn(pts, count, clipRgn, blitter);
478    }
479}
480
481void SkScan::AntiHairLine(const SkPoint pts[], int count, const SkRasterClip& clip,
482                          SkBlitter* blitter) {
483    if (clip.isBW()) {
484        AntiHairLineRgn(pts, count, &clip.bwRgn(), blitter);
485    } else {
486        const SkRegion* clipRgn = NULL;
487
488        SkRect r;
489        r.set(pts, count);
490
491        SkAAClipBlitterWrapper wrap;
492        if (!clip.quickContains(r.roundOut().makeOutset(1, 1))) {
493            wrap.init(clip, blitter);
494            blitter = wrap.getBlitter();
495            clipRgn = &wrap.getRgn();
496        }
497        AntiHairLineRgn(pts, count, clipRgn, blitter);
498    }
499}
500