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 "SkEdge.h"
11#include "SkFDot6.h"
12#include "SkMath.h"
13
14/*
15    In setLine, setQuadratic, setCubic, the first thing we do is to convert
16    the points into FDot6. This is modulated by the shift parameter, which
17    will either be 0, or something like 2 for antialiasing.
18
19    In the float case, we want to turn the float into .6 by saying pt * 64,
20    or pt * 256 for antialiasing. This is implemented as 1 << (shift + 6).
21
22    In the fixed case, we want to turn the fixed into .6 by saying pt >> 10,
23    or pt >> 8 for antialiasing. This is implemented as pt >> (10 - shift).
24*/
25
26static inline SkFixed SkFDot6ToFixedDiv2(SkFDot6 value) {
27    // we want to return SkFDot6ToFixed(value >> 1), but we don't want to throw
28    // away data in value, so just perform a modify up-shift
29    return value << (16 - 6 - 1);
30}
31
32/////////////////////////////////////////////////////////////////////////
33
34int SkEdge::setLine(const SkPoint& p0, const SkPoint& p1, const SkIRect* clip,
35                    int shift) {
36    SkFDot6 x0, y0, x1, y1;
37
38    {
39#ifdef SK_SCALAR_IS_FLOAT
40        float scale = float(1 << (shift + 6));
41        x0 = int(p0.fX * scale);
42        y0 = int(p0.fY * scale);
43        x1 = int(p1.fX * scale);
44        y1 = int(p1.fY * scale);
45#else
46        shift = 10 - shift;
47        x0 = p0.fX >> shift;
48        y0 = p0.fY >> shift;
49        x1 = p1.fX >> shift;
50        y1 = p1.fY >> shift;
51#endif
52    }
53
54    int winding = 1;
55
56    if (y0 > y1) {
57        SkTSwap(x0, x1);
58        SkTSwap(y0, y1);
59        winding = -1;
60    }
61
62    int top = SkFDot6Round(y0);
63    int bot = SkFDot6Round(y1);
64
65    // are we a zero-height line?
66    if (top == bot) {
67        return 0;
68    }
69    // are we completely above or below the clip?
70    if (NULL != clip && (top >= clip->fBottom || bot <= clip->fTop)) {
71        return 0;
72    }
73
74    SkFixed slope = SkFDot6Div(x1 - x0, y1 - y0);
75    const int dy  = SkEdge_Compute_DY(top, y0);
76
77    fX          = SkFDot6ToFixed(x0 + SkFixedMul(slope, dy));   // + SK_Fixed1/2
78    fDX         = slope;
79    fFirstY     = top;
80    fLastY      = bot - 1;
81    fCurveCount = 0;
82    fWinding    = SkToS8(winding);
83    fCurveShift = 0;
84
85    if (clip) {
86        this->chopLineWithClip(*clip);
87    }
88    return 1;
89}
90
91// called from a curve subclass
92int SkEdge::updateLine(SkFixed x0, SkFixed y0, SkFixed x1, SkFixed y1)
93{
94    SkASSERT(fWinding == 1 || fWinding == -1);
95    SkASSERT(fCurveCount != 0);
96//    SkASSERT(fCurveShift != 0);
97
98    y0 >>= 10;
99    y1 >>= 10;
100
101    SkASSERT(y0 <= y1);
102
103    int top = SkFDot6Round(y0);
104    int bot = SkFDot6Round(y1);
105
106//  SkASSERT(top >= fFirstY);
107
108    // are we a zero-height line?
109    if (top == bot)
110        return 0;
111
112    x0 >>= 10;
113    x1 >>= 10;
114
115    SkFixed slope = SkFDot6Div(x1 - x0, y1 - y0);
116    const int dy  = SkEdge_Compute_DY(top, y0);
117
118    fX          = SkFDot6ToFixed(x0 + SkFixedMul(slope, dy));   // + SK_Fixed1/2
119    fDX         = slope;
120    fFirstY     = top;
121    fLastY      = bot - 1;
122
123    return 1;
124}
125
126void SkEdge::chopLineWithClip(const SkIRect& clip)
127{
128    int top = fFirstY;
129
130    SkASSERT(top < clip.fBottom);
131
132    // clip the line to the top
133    if (top < clip.fTop)
134    {
135        SkASSERT(fLastY >= clip.fTop);
136        fX += fDX * (clip.fTop - top);
137        fFirstY = clip.fTop;
138    }
139}
140
141///////////////////////////////////////////////////////////////////////////////
142
143/*  We store 1<<shift in a (signed) byte, so its maximum value is 1<<6 == 64.
144    Note that this limits the number of lines we use to approximate a curve.
145    If we need to increase this, we need to store fCurveCount in something
146    larger than int8_t.
147*/
148#define MAX_COEFF_SHIFT     6
149
150static inline SkFDot6 cheap_distance(SkFDot6 dx, SkFDot6 dy)
151{
152    dx = SkAbs32(dx);
153    dy = SkAbs32(dy);
154    // return max + min/2
155    if (dx > dy)
156        dx += dy >> 1;
157    else
158        dx = dy + (dx >> 1);
159    return dx;
160}
161
162static inline int diff_to_shift(SkFDot6 dx, SkFDot6 dy)
163{
164    // cheap calc of distance from center of p0-p2 to the center of the curve
165    SkFDot6 dist = cheap_distance(dx, dy);
166
167    // shift down dist (it is currently in dot6)
168    // down by 5 should give us 1/2 pixel accuracy (assuming our dist is accurate...)
169    // this is chosen by heuristic: make it as big as possible (to minimize segments)
170    // ... but small enough so that our curves still look smooth
171    dist = (dist + (1 << 4)) >> 5;
172
173    // each subdivision (shift value) cuts this dist (error) by 1/4
174    return (32 - SkCLZ(dist)) >> 1;
175}
176
177int SkQuadraticEdge::setQuadratic(const SkPoint pts[3], int shift)
178{
179    SkFDot6 x0, y0, x1, y1, x2, y2;
180
181    {
182#ifdef SK_SCALAR_IS_FLOAT
183        float scale = float(1 << (shift + 6));
184        x0 = int(pts[0].fX * scale);
185        y0 = int(pts[0].fY * scale);
186        x1 = int(pts[1].fX * scale);
187        y1 = int(pts[1].fY * scale);
188        x2 = int(pts[2].fX * scale);
189        y2 = int(pts[2].fY * scale);
190#else
191        shift = 10 - shift;
192        x0 = pts[0].fX >> shift;
193        y0 = pts[0].fY >> shift;
194        x1 = pts[1].fX >> shift;
195        y1 = pts[1].fY >> shift;
196        x2 = pts[2].fX >> shift;
197        y2 = pts[2].fY >> shift;
198#endif
199    }
200
201    int winding = 1;
202    if (y0 > y2)
203    {
204        SkTSwap(x0, x2);
205        SkTSwap(y0, y2);
206        winding = -1;
207    }
208    SkASSERT(y0 <= y1 && y1 <= y2);
209
210    int top = SkFDot6Round(y0);
211    int bot = SkFDot6Round(y2);
212
213    // are we a zero-height quad (line)?
214    if (top == bot)
215        return 0;
216
217    // compute number of steps needed (1 << shift)
218    {
219        SkFDot6 dx = ((x1 << 1) - x0 - x2) >> 2;
220        SkFDot6 dy = ((y1 << 1) - y0 - y2) >> 2;
221        shift = diff_to_shift(dx, dy);
222        SkASSERT(shift >= 0);
223    }
224    // need at least 1 subdivision for our bias trick
225    if (shift == 0) {
226        shift = 1;
227    } else if (shift > MAX_COEFF_SHIFT) {
228        shift = MAX_COEFF_SHIFT;
229    }
230
231    fWinding    = SkToS8(winding);
232    //fCubicDShift only set for cubics
233    fCurveCount = SkToS8(1 << shift);
234
235    /*
236     *  We want to reformulate into polynomial form, to make it clear how we
237     *  should forward-difference.
238     *
239     *  p0 (1 - t)^2 + p1 t(1 - t) + p2 t^2 ==> At^2 + Bt + C
240     *
241     *  A = p0 - 2p1 + p2
242     *  B = 2(p1 - p0)
243     *  C = p0
244     *
245     *  Our caller must have constrained our inputs (p0..p2) to all fit into
246     *  16.16. However, as seen above, we sometimes compute values that can be
247     *  larger (e.g. B = 2*(p1 - p0)). To guard against overflow, we will store
248     *  A and B at 1/2 of their actual value, and just apply a 2x scale during
249     *  application in updateQuadratic(). Hence we store (shift - 1) in
250     *  fCurveShift.
251     */
252
253    fCurveShift = SkToU8(shift - 1);
254
255    SkFixed A = SkFDot6ToFixedDiv2(x0 - x1 - x1 + x2);  // 1/2 the real value
256    SkFixed B = SkFDot6ToFixed(x1 - x0);                // 1/2 the real value
257
258    fQx     = SkFDot6ToFixed(x0);
259    fQDx    = B + (A >> shift);     // biased by shift
260    fQDDx   = A >> (shift - 1);     // biased by shift
261
262    A = SkFDot6ToFixedDiv2(y0 - y1 - y1 + y2);  // 1/2 the real value
263    B = SkFDot6ToFixed(y1 - y0);                // 1/2 the real value
264
265    fQy     = SkFDot6ToFixed(y0);
266    fQDy    = B + (A >> shift);     // biased by shift
267    fQDDy   = A >> (shift - 1);     // biased by shift
268
269    fQLastX = SkFDot6ToFixed(x2);
270    fQLastY = SkFDot6ToFixed(y2);
271
272    return this->updateQuadratic();
273}
274
275int SkQuadraticEdge::updateQuadratic()
276{
277    int     success;
278    int     count = fCurveCount;
279    SkFixed oldx = fQx;
280    SkFixed oldy = fQy;
281    SkFixed dx = fQDx;
282    SkFixed dy = fQDy;
283    SkFixed newx, newy;
284    int     shift = fCurveShift;
285
286    SkASSERT(count > 0);
287
288    do {
289        if (--count > 0)
290        {
291            newx    = oldx + (dx >> shift);
292            dx    += fQDDx;
293            newy    = oldy + (dy >> shift);
294            dy    += fQDDy;
295        }
296        else    // last segment
297        {
298            newx    = fQLastX;
299            newy    = fQLastY;
300        }
301        success = this->updateLine(oldx, oldy, newx, newy);
302        oldx = newx;
303        oldy = newy;
304    } while (count > 0 && !success);
305
306    fQx         = newx;
307    fQy         = newy;
308    fQDx        = dx;
309    fQDy        = dy;
310    fCurveCount = SkToS8(count);
311    return success;
312}
313
314/////////////////////////////////////////////////////////////////////////
315
316static inline int SkFDot6UpShift(SkFDot6 x, int upShift) {
317    SkASSERT((x << upShift >> upShift) == x);
318    return x << upShift;
319}
320
321/*  f(1/3) = (8a + 12b + 6c + d) / 27
322    f(2/3) = (a + 6b + 12c + 8d) / 27
323
324    f(1/3)-b = (8a - 15b + 6c + d) / 27
325    f(2/3)-c = (a + 6b - 15c + 8d) / 27
326
327    use 16/512 to approximate 1/27
328*/
329static SkFDot6 cubic_delta_from_line(SkFDot6 a, SkFDot6 b, SkFDot6 c, SkFDot6 d)
330{
331    SkFDot6 oneThird = ((a << 3) - ((b << 4) - b) + 6*c + d) * 19 >> 9;
332    SkFDot6 twoThird = (a + 6*b - ((c << 4) - c) + (d << 3)) * 19 >> 9;
333
334    return SkMax32(SkAbs32(oneThird), SkAbs32(twoThird));
335}
336
337int SkCubicEdge::setCubic(const SkPoint pts[4], const SkIRect* clip, int shift)
338{
339    SkFDot6 x0, y0, x1, y1, x2, y2, x3, y3;
340
341    {
342#ifdef SK_SCALAR_IS_FLOAT
343        float scale = float(1 << (shift + 6));
344        x0 = int(pts[0].fX * scale);
345        y0 = int(pts[0].fY * scale);
346        x1 = int(pts[1].fX * scale);
347        y1 = int(pts[1].fY * scale);
348        x2 = int(pts[2].fX * scale);
349        y2 = int(pts[2].fY * scale);
350        x3 = int(pts[3].fX * scale);
351        y3 = int(pts[3].fY * scale);
352#else
353        shift = 10 - shift;
354        x0 = pts[0].fX >> shift;
355        y0 = pts[0].fY >> shift;
356        x1 = pts[1].fX >> shift;
357        y1 = pts[1].fY >> shift;
358        x2 = pts[2].fX >> shift;
359        y2 = pts[2].fY >> shift;
360        x3 = pts[3].fX >> shift;
361        y3 = pts[3].fY >> shift;
362#endif
363    }
364
365    int winding = 1;
366    if (y0 > y3)
367    {
368        SkTSwap(x0, x3);
369        SkTSwap(x1, x2);
370        SkTSwap(y0, y3);
371        SkTSwap(y1, y2);
372        winding = -1;
373    }
374
375    int top = SkFDot6Round(y0);
376    int bot = SkFDot6Round(y3);
377
378    // are we a zero-height cubic (line)?
379    if (top == bot)
380        return 0;
381
382    // are we completely above or below the clip?
383    if (clip && (top >= clip->fBottom || bot <= clip->fTop))
384        return 0;
385
386    // compute number of steps needed (1 << shift)
387    {
388        // Can't use (center of curve - center of baseline), since center-of-curve
389        // need not be the max delta from the baseline (it could even be coincident)
390        // so we try just looking at the two off-curve points
391        SkFDot6 dx = cubic_delta_from_line(x0, x1, x2, x3);
392        SkFDot6 dy = cubic_delta_from_line(y0, y1, y2, y3);
393        // add 1 (by observation)
394        shift = diff_to_shift(dx, dy) + 1;
395    }
396    // need at least 1 subdivision for our bias trick
397    SkASSERT(shift > 0);
398    if (shift > MAX_COEFF_SHIFT) {
399        shift = MAX_COEFF_SHIFT;
400    }
401
402    /*  Since our in coming data is initially shifted down by 10 (or 8 in
403        antialias). That means the most we can shift up is 8. However, we
404        compute coefficients with a 3*, so the safest upshift is really 6
405    */
406    int upShift = 6;    // largest safe value
407    int downShift = shift + upShift - 10;
408    if (downShift < 0) {
409        downShift = 0;
410        upShift = 10 - shift;
411    }
412
413    fWinding    = SkToS8(winding);
414    fCurveCount = SkToS8(-1 << shift);
415    fCurveShift = SkToU8(shift);
416    fCubicDShift = SkToU8(downShift);
417
418    SkFixed B = SkFDot6UpShift(3 * (x1 - x0), upShift);
419    SkFixed C = SkFDot6UpShift(3 * (x0 - x1 - x1 + x2), upShift);
420    SkFixed D = SkFDot6UpShift(x3 + 3 * (x1 - x2) - x0, upShift);
421
422    fCx     = SkFDot6ToFixed(x0);
423    fCDx    = B + (C >> shift) + (D >> 2*shift);    // biased by shift
424    fCDDx   = 2*C + (3*D >> (shift - 1));           // biased by 2*shift
425    fCDDDx  = 3*D >> (shift - 1);                   // biased by 2*shift
426
427    B = SkFDot6UpShift(3 * (y1 - y0), upShift);
428    C = SkFDot6UpShift(3 * (y0 - y1 - y1 + y2), upShift);
429    D = SkFDot6UpShift(y3 + 3 * (y1 - y2) - y0, upShift);
430
431    fCy     = SkFDot6ToFixed(y0);
432    fCDy    = B + (C >> shift) + (D >> 2*shift);    // biased by shift
433    fCDDy   = 2*C + (3*D >> (shift - 1));           // biased by 2*shift
434    fCDDDy  = 3*D >> (shift - 1);                   // biased by 2*shift
435
436    fCLastX = SkFDot6ToFixed(x3);
437    fCLastY = SkFDot6ToFixed(y3);
438
439    if (clip)
440    {
441        do {
442            if (!this->updateCubic()) {
443                return 0;
444            }
445        } while (!this->intersectsClip(*clip));
446        this->chopLineWithClip(*clip);
447        return 1;
448    }
449    return this->updateCubic();
450}
451
452int SkCubicEdge::updateCubic()
453{
454    int     success;
455    int     count = fCurveCount;
456    SkFixed oldx = fCx;
457    SkFixed oldy = fCy;
458    SkFixed newx, newy;
459    const int ddshift = fCurveShift;
460    const int dshift = fCubicDShift;
461
462    SkASSERT(count < 0);
463
464    do {
465        if (++count < 0)
466        {
467            newx    = oldx + (fCDx >> dshift);
468            fCDx    += fCDDx >> ddshift;
469            fCDDx   += fCDDDx;
470
471            newy    = oldy + (fCDy >> dshift);
472            fCDy    += fCDDy >> ddshift;
473            fCDDy   += fCDDDy;
474        }
475        else    // last segment
476        {
477        //  SkDebugf("LastX err=%d, LastY err=%d\n", (oldx + (fCDx >> shift) - fLastX), (oldy + (fCDy >> shift) - fLastY));
478            newx    = fCLastX;
479            newy    = fCLastY;
480        }
481
482        // we want to say SkASSERT(oldy <= newy), but our finite fixedpoint
483        // doesn't always achieve that, so we have to explicitly pin it here.
484        if (newy < oldy) {
485            newy = oldy;
486        }
487
488        success = this->updateLine(oldx, oldy, newx, newy);
489        oldx = newx;
490        oldy = newy;
491    } while (count < 0 && !success);
492
493    fCx         = newx;
494    fCy         = newy;
495    fCurveCount = SkToS8(count);
496    return success;
497}
498