michael@0: 
michael@0: /*
michael@0:  * Copyright 2006 The Android Open Source Project
michael@0:  *
michael@0:  * Use of this source code is governed by a BSD-style license that can be
michael@0:  * found in the LICENSE file.
michael@0:  */
michael@0: 
michael@0: 
michael@0: #include "SkEdge.h"
michael@0: #include "SkFDot6.h"
michael@0: #include "SkMath.h"
michael@0: 
michael@0: /*
michael@0:     In setLine, setQuadratic, setCubic, the first thing we do is to convert
michael@0:     the points into FDot6. This is modulated by the shift parameter, which
michael@0:     will either be 0, or something like 2 for antialiasing.
michael@0: 
michael@0:     In the float case, we want to turn the float into .6 by saying pt * 64,
michael@0:     or pt * 256 for antialiasing. This is implemented as 1 << (shift + 6).
michael@0: 
michael@0:     In the fixed case, we want to turn the fixed into .6 by saying pt >> 10,
michael@0:     or pt >> 8 for antialiasing. This is implemented as pt >> (10 - shift).
michael@0: */
michael@0: 
michael@0: static inline SkFixed SkFDot6ToFixedDiv2(SkFDot6 value) {
michael@0:     // we want to return SkFDot6ToFixed(value >> 1), but we don't want to throw
michael@0:     // away data in value, so just perform a modify up-shift
michael@0:     return value << (16 - 6 - 1);
michael@0: }
michael@0: 
michael@0: /////////////////////////////////////////////////////////////////////////
michael@0: 
michael@0: int SkEdge::setLine(const SkPoint& p0, const SkPoint& p1, const SkIRect* clip,
michael@0:                     int shift) {
michael@0:     SkFDot6 x0, y0, x1, y1;
michael@0: 
michael@0:     {
michael@0:         float scale = float(1 << (shift + 6));
michael@0:         x0 = int(p0.fX * scale);
michael@0:         y0 = int(p0.fY * scale);
michael@0:         x1 = int(p1.fX * scale);
michael@0:         y1 = int(p1.fY * scale);
michael@0:     }
michael@0: 
michael@0:     int winding = 1;
michael@0: 
michael@0:     if (y0 > y1) {
michael@0:         SkTSwap(x0, x1);
michael@0:         SkTSwap(y0, y1);
michael@0:         winding = -1;
michael@0:     }
michael@0: 
michael@0:     int top = SkFDot6Round(y0);
michael@0:     int bot = SkFDot6Round(y1);
michael@0: 
michael@0:     // are we a zero-height line?
michael@0:     if (top == bot) {
michael@0:         return 0;
michael@0:     }
michael@0:     // are we completely above or below the clip?
michael@0:     if (NULL != clip && (top >= clip->fBottom || bot <= clip->fTop)) {
michael@0:         return 0;
michael@0:     }
michael@0: 
michael@0:     SkFixed slope = SkFDot6Div(x1 - x0, y1 - y0);
michael@0:     const int dy  = SkEdge_Compute_DY(top, y0);
michael@0: 
michael@0:     fX          = SkFDot6ToFixed(x0 + SkFixedMul(slope, dy));   // + SK_Fixed1/2
michael@0:     fDX         = slope;
michael@0:     fFirstY     = top;
michael@0:     fLastY      = bot - 1;
michael@0:     fCurveCount = 0;
michael@0:     fWinding    = SkToS8(winding);
michael@0:     fCurveShift = 0;
michael@0: 
michael@0:     if (clip) {
michael@0:         this->chopLineWithClip(*clip);
michael@0:     }
michael@0:     return 1;
michael@0: }
michael@0: 
michael@0: // called from a curve subclass
michael@0: int SkEdge::updateLine(SkFixed x0, SkFixed y0, SkFixed x1, SkFixed y1)
michael@0: {
michael@0:     SkASSERT(fWinding == 1 || fWinding == -1);
michael@0:     SkASSERT(fCurveCount != 0);
michael@0: //    SkASSERT(fCurveShift != 0);
michael@0: 
michael@0:     y0 >>= 10;
michael@0:     y1 >>= 10;
michael@0: 
michael@0:     SkASSERT(y0 <= y1);
michael@0: 
michael@0:     int top = SkFDot6Round(y0);
michael@0:     int bot = SkFDot6Round(y1);
michael@0: 
michael@0: //  SkASSERT(top >= fFirstY);
michael@0: 
michael@0:     // are we a zero-height line?
michael@0:     if (top == bot)
michael@0:         return 0;
michael@0: 
michael@0:     x0 >>= 10;
michael@0:     x1 >>= 10;
michael@0: 
michael@0:     SkFixed slope = SkFDot6Div(x1 - x0, y1 - y0);
michael@0:     const int dy  = SkEdge_Compute_DY(top, y0);
michael@0: 
michael@0:     fX          = SkFDot6ToFixed(x0 + SkFixedMul(slope, dy));   // + SK_Fixed1/2
michael@0:     fDX         = slope;
michael@0:     fFirstY     = top;
michael@0:     fLastY      = bot - 1;
michael@0: 
michael@0:     return 1;
michael@0: }
michael@0: 
michael@0: void SkEdge::chopLineWithClip(const SkIRect& clip)
michael@0: {
michael@0:     int top = fFirstY;
michael@0: 
michael@0:     SkASSERT(top < clip.fBottom);
michael@0: 
michael@0:     // clip the line to the top
michael@0:     if (top < clip.fTop)
michael@0:     {
michael@0:         SkASSERT(fLastY >= clip.fTop);
michael@0:         fX += fDX * (clip.fTop - top);
michael@0:         fFirstY = clip.fTop;
michael@0:     }
michael@0: }
michael@0: 
michael@0: ///////////////////////////////////////////////////////////////////////////////
michael@0: 
michael@0: /*  We store 1<<shift in a (signed) byte, so its maximum value is 1<<6 == 64.
michael@0:     Note that this limits the number of lines we use to approximate a curve.
michael@0:     If we need to increase this, we need to store fCurveCount in something
michael@0:     larger than int8_t.
michael@0: */
michael@0: #define MAX_COEFF_SHIFT     6
michael@0: 
michael@0: static inline SkFDot6 cheap_distance(SkFDot6 dx, SkFDot6 dy)
michael@0: {
michael@0:     dx = SkAbs32(dx);
michael@0:     dy = SkAbs32(dy);
michael@0:     // return max + min/2
michael@0:     if (dx > dy)
michael@0:         dx += dy >> 1;
michael@0:     else
michael@0:         dx = dy + (dx >> 1);
michael@0:     return dx;
michael@0: }
michael@0: 
michael@0: static inline int diff_to_shift(SkFDot6 dx, SkFDot6 dy)
michael@0: {
michael@0:     // cheap calc of distance from center of p0-p2 to the center of the curve
michael@0:     SkFDot6 dist = cheap_distance(dx, dy);
michael@0: 
michael@0:     // shift down dist (it is currently in dot6)
michael@0:     // down by 5 should give us 1/2 pixel accuracy (assuming our dist is accurate...)
michael@0:     // this is chosen by heuristic: make it as big as possible (to minimize segments)
michael@0:     // ... but small enough so that our curves still look smooth
michael@0:     dist = (dist + (1 << 4)) >> 5;
michael@0: 
michael@0:     // each subdivision (shift value) cuts this dist (error) by 1/4
michael@0:     return (32 - SkCLZ(dist)) >> 1;
michael@0: }
michael@0: 
michael@0: int SkQuadraticEdge::setQuadratic(const SkPoint pts[3], int shift)
michael@0: {
michael@0:     SkFDot6 x0, y0, x1, y1, x2, y2;
michael@0: 
michael@0:     {
michael@0:         float scale = float(1 << (shift + 6));
michael@0:         x0 = int(pts[0].fX * scale);
michael@0:         y0 = int(pts[0].fY * scale);
michael@0:         x1 = int(pts[1].fX * scale);
michael@0:         y1 = int(pts[1].fY * scale);
michael@0:         x2 = int(pts[2].fX * scale);
michael@0:         y2 = int(pts[2].fY * scale);
michael@0:     }
michael@0: 
michael@0:     int winding = 1;
michael@0:     if (y0 > y2)
michael@0:     {
michael@0:         SkTSwap(x0, x2);
michael@0:         SkTSwap(y0, y2);
michael@0:         winding = -1;
michael@0:     }
michael@0:     SkASSERT(y0 <= y1 && y1 <= y2);
michael@0: 
michael@0:     int top = SkFDot6Round(y0);
michael@0:     int bot = SkFDot6Round(y2);
michael@0: 
michael@0:     // are we a zero-height quad (line)?
michael@0:     if (top == bot)
michael@0:         return 0;
michael@0: 
michael@0:     // compute number of steps needed (1 << shift)
michael@0:     {
michael@0:         SkFDot6 dx = ((x1 << 1) - x0 - x2) >> 2;
michael@0:         SkFDot6 dy = ((y1 << 1) - y0 - y2) >> 2;
michael@0:         shift = diff_to_shift(dx, dy);
michael@0:         SkASSERT(shift >= 0);
michael@0:     }
michael@0:     // need at least 1 subdivision for our bias trick
michael@0:     if (shift == 0) {
michael@0:         shift = 1;
michael@0:     } else if (shift > MAX_COEFF_SHIFT) {
michael@0:         shift = MAX_COEFF_SHIFT;
michael@0:     }
michael@0: 
michael@0:     fWinding    = SkToS8(winding);
michael@0:     //fCubicDShift only set for cubics
michael@0:     fCurveCount = SkToS8(1 << shift);
michael@0: 
michael@0:     /*
michael@0:      *  We want to reformulate into polynomial form, to make it clear how we
michael@0:      *  should forward-difference.
michael@0:      *
michael@0:      *  p0 (1 - t)^2 + p1 t(1 - t) + p2 t^2 ==> At^2 + Bt + C
michael@0:      *
michael@0:      *  A = p0 - 2p1 + p2
michael@0:      *  B = 2(p1 - p0)
michael@0:      *  C = p0
michael@0:      *
michael@0:      *  Our caller must have constrained our inputs (p0..p2) to all fit into
michael@0:      *  16.16. However, as seen above, we sometimes compute values that can be
michael@0:      *  larger (e.g. B = 2*(p1 - p0)). To guard against overflow, we will store
michael@0:      *  A and B at 1/2 of their actual value, and just apply a 2x scale during
michael@0:      *  application in updateQuadratic(). Hence we store (shift - 1) in
michael@0:      *  fCurveShift.
michael@0:      */
michael@0: 
michael@0:     fCurveShift = SkToU8(shift - 1);
michael@0: 
michael@0:     SkFixed A = SkFDot6ToFixedDiv2(x0 - x1 - x1 + x2);  // 1/2 the real value
michael@0:     SkFixed B = SkFDot6ToFixed(x1 - x0);                // 1/2 the real value
michael@0: 
michael@0:     fQx     = SkFDot6ToFixed(x0);
michael@0:     fQDx    = B + (A >> shift);     // biased by shift
michael@0:     fQDDx   = A >> (shift - 1);     // biased by shift
michael@0: 
michael@0:     A = SkFDot6ToFixedDiv2(y0 - y1 - y1 + y2);  // 1/2 the real value
michael@0:     B = SkFDot6ToFixed(y1 - y0);                // 1/2 the real value
michael@0: 
michael@0:     fQy     = SkFDot6ToFixed(y0);
michael@0:     fQDy    = B + (A >> shift);     // biased by shift
michael@0:     fQDDy   = A >> (shift - 1);     // biased by shift
michael@0: 
michael@0:     fQLastX = SkFDot6ToFixed(x2);
michael@0:     fQLastY = SkFDot6ToFixed(y2);
michael@0: 
michael@0:     return this->updateQuadratic();
michael@0: }
michael@0: 
michael@0: int SkQuadraticEdge::updateQuadratic()
michael@0: {
michael@0:     int     success;
michael@0:     int     count = fCurveCount;
michael@0:     SkFixed oldx = fQx;
michael@0:     SkFixed oldy = fQy;
michael@0:     SkFixed dx = fQDx;
michael@0:     SkFixed dy = fQDy;
michael@0:     SkFixed newx, newy;
michael@0:     int     shift = fCurveShift;
michael@0: 
michael@0:     SkASSERT(count > 0);
michael@0: 
michael@0:     do {
michael@0:         if (--count > 0)
michael@0:         {
michael@0:             newx    = oldx + (dx >> shift);
michael@0:             dx    += fQDDx;
michael@0:             newy    = oldy + (dy >> shift);
michael@0:             dy    += fQDDy;
michael@0:         }
michael@0:         else    // last segment
michael@0:         {
michael@0:             newx    = fQLastX;
michael@0:             newy    = fQLastY;
michael@0:         }
michael@0:         success = this->updateLine(oldx, oldy, newx, newy);
michael@0:         oldx = newx;
michael@0:         oldy = newy;
michael@0:     } while (count > 0 && !success);
michael@0: 
michael@0:     fQx         = newx;
michael@0:     fQy         = newy;
michael@0:     fQDx        = dx;
michael@0:     fQDy        = dy;
michael@0:     fCurveCount = SkToS8(count);
michael@0:     return success;
michael@0: }
michael@0: 
michael@0: /////////////////////////////////////////////////////////////////////////
michael@0: 
michael@0: static inline int SkFDot6UpShift(SkFDot6 x, int upShift) {
michael@0:     SkASSERT((x << upShift >> upShift) == x);
michael@0:     return x << upShift;
michael@0: }
michael@0: 
michael@0: /*  f(1/3) = (8a + 12b + 6c + d) / 27
michael@0:     f(2/3) = (a + 6b + 12c + 8d) / 27
michael@0: 
michael@0:     f(1/3)-b = (8a - 15b + 6c + d) / 27
michael@0:     f(2/3)-c = (a + 6b - 15c + 8d) / 27
michael@0: 
michael@0:     use 16/512 to approximate 1/27
michael@0: */
michael@0: static SkFDot6 cubic_delta_from_line(SkFDot6 a, SkFDot6 b, SkFDot6 c, SkFDot6 d)
michael@0: {
michael@0:     SkFDot6 oneThird = ((a << 3) - ((b << 4) - b) + 6*c + d) * 19 >> 9;
michael@0:     SkFDot6 twoThird = (a + 6*b - ((c << 4) - c) + (d << 3)) * 19 >> 9;
michael@0: 
michael@0:     return SkMax32(SkAbs32(oneThird), SkAbs32(twoThird));
michael@0: }
michael@0: 
michael@0: int SkCubicEdge::setCubic(const SkPoint pts[4], const SkIRect* clip, int shift)
michael@0: {
michael@0:     SkFDot6 x0, y0, x1, y1, x2, y2, x3, y3;
michael@0: 
michael@0:     {
michael@0:         float scale = float(1 << (shift + 6));
michael@0:         x0 = int(pts[0].fX * scale);
michael@0:         y0 = int(pts[0].fY * scale);
michael@0:         x1 = int(pts[1].fX * scale);
michael@0:         y1 = int(pts[1].fY * scale);
michael@0:         x2 = int(pts[2].fX * scale);
michael@0:         y2 = int(pts[2].fY * scale);
michael@0:         x3 = int(pts[3].fX * scale);
michael@0:         y3 = int(pts[3].fY * scale);
michael@0:     }
michael@0: 
michael@0:     int winding = 1;
michael@0:     if (y0 > y3)
michael@0:     {
michael@0:         SkTSwap(x0, x3);
michael@0:         SkTSwap(x1, x2);
michael@0:         SkTSwap(y0, y3);
michael@0:         SkTSwap(y1, y2);
michael@0:         winding = -1;
michael@0:     }
michael@0: 
michael@0:     int top = SkFDot6Round(y0);
michael@0:     int bot = SkFDot6Round(y3);
michael@0: 
michael@0:     // are we a zero-height cubic (line)?
michael@0:     if (top == bot)
michael@0:         return 0;
michael@0: 
michael@0:     // are we completely above or below the clip?
michael@0:     if (clip && (top >= clip->fBottom || bot <= clip->fTop))
michael@0:         return 0;
michael@0: 
michael@0:     // compute number of steps needed (1 << shift)
michael@0:     {
michael@0:         // Can't use (center of curve - center of baseline), since center-of-curve
michael@0:         // need not be the max delta from the baseline (it could even be coincident)
michael@0:         // so we try just looking at the two off-curve points
michael@0:         SkFDot6 dx = cubic_delta_from_line(x0, x1, x2, x3);
michael@0:         SkFDot6 dy = cubic_delta_from_line(y0, y1, y2, y3);
michael@0:         // add 1 (by observation)
michael@0:         shift = diff_to_shift(dx, dy) + 1;
michael@0:     }
michael@0:     // need at least 1 subdivision for our bias trick
michael@0:     SkASSERT(shift > 0);
michael@0:     if (shift > MAX_COEFF_SHIFT) {
michael@0:         shift = MAX_COEFF_SHIFT;
michael@0:     }
michael@0: 
michael@0:     /*  Since our in coming data is initially shifted down by 10 (or 8 in
michael@0:         antialias). That means the most we can shift up is 8. However, we
michael@0:         compute coefficients with a 3*, so the safest upshift is really 6
michael@0:     */
michael@0:     int upShift = 6;    // largest safe value
michael@0:     int downShift = shift + upShift - 10;
michael@0:     if (downShift < 0) {
michael@0:         downShift = 0;
michael@0:         upShift = 10 - shift;
michael@0:     }
michael@0: 
michael@0:     fWinding    = SkToS8(winding);
michael@0:     fCurveCount = SkToS8(-1 << shift);
michael@0:     fCurveShift = SkToU8(shift);
michael@0:     fCubicDShift = SkToU8(downShift);
michael@0: 
michael@0:     SkFixed B = SkFDot6UpShift(3 * (x1 - x0), upShift);
michael@0:     SkFixed C = SkFDot6UpShift(3 * (x0 - x1 - x1 + x2), upShift);
michael@0:     SkFixed D = SkFDot6UpShift(x3 + 3 * (x1 - x2) - x0, upShift);
michael@0: 
michael@0:     fCx     = SkFDot6ToFixed(x0);
michael@0:     fCDx    = B + (C >> shift) + (D >> 2*shift);    // biased by shift
michael@0:     fCDDx   = 2*C + (3*D >> (shift - 1));           // biased by 2*shift
michael@0:     fCDDDx  = 3*D >> (shift - 1);                   // biased by 2*shift
michael@0: 
michael@0:     B = SkFDot6UpShift(3 * (y1 - y0), upShift);
michael@0:     C = SkFDot6UpShift(3 * (y0 - y1 - y1 + y2), upShift);
michael@0:     D = SkFDot6UpShift(y3 + 3 * (y1 - y2) - y0, upShift);
michael@0: 
michael@0:     fCy     = SkFDot6ToFixed(y0);
michael@0:     fCDy    = B + (C >> shift) + (D >> 2*shift);    // biased by shift
michael@0:     fCDDy   = 2*C + (3*D >> (shift - 1));           // biased by 2*shift
michael@0:     fCDDDy  = 3*D >> (shift - 1);                   // biased by 2*shift
michael@0: 
michael@0:     fCLastX = SkFDot6ToFixed(x3);
michael@0:     fCLastY = SkFDot6ToFixed(y3);
michael@0: 
michael@0:     if (clip)
michael@0:     {
michael@0:         do {
michael@0:             if (!this->updateCubic()) {
michael@0:                 return 0;
michael@0:             }
michael@0:         } while (!this->intersectsClip(*clip));
michael@0:         this->chopLineWithClip(*clip);
michael@0:         return 1;
michael@0:     }
michael@0:     return this->updateCubic();
michael@0: }
michael@0: 
michael@0: int SkCubicEdge::updateCubic()
michael@0: {
michael@0:     int     success;
michael@0:     int     count = fCurveCount;
michael@0:     SkFixed oldx = fCx;
michael@0:     SkFixed oldy = fCy;
michael@0:     SkFixed newx, newy;
michael@0:     const int ddshift = fCurveShift;
michael@0:     const int dshift = fCubicDShift;
michael@0: 
michael@0:     SkASSERT(count < 0);
michael@0: 
michael@0:     do {
michael@0:         if (++count < 0)
michael@0:         {
michael@0:             newx    = oldx + (fCDx >> dshift);
michael@0:             fCDx    += fCDDx >> ddshift;
michael@0:             fCDDx   += fCDDDx;
michael@0: 
michael@0:             newy    = oldy + (fCDy >> dshift);
michael@0:             fCDy    += fCDDy >> ddshift;
michael@0:             fCDDy   += fCDDDy;
michael@0:         }
michael@0:         else    // last segment
michael@0:         {
michael@0:         //  SkDebugf("LastX err=%d, LastY err=%d\n", (oldx + (fCDx >> shift) - fLastX), (oldy + (fCDy >> shift) - fLastY));
michael@0:             newx    = fCLastX;
michael@0:             newy    = fCLastY;
michael@0:         }
michael@0: 
michael@0:         // we want to say SkASSERT(oldy <= newy), but our finite fixedpoint
michael@0:         // doesn't always achieve that, so we have to explicitly pin it here.
michael@0:         if (newy < oldy) {
michael@0:             newy = oldy;
michael@0:         }
michael@0: 
michael@0:         success = this->updateLine(oldx, oldy, newx, newy);
michael@0:         oldx = newx;
michael@0:         oldy = newy;
michael@0:     } while (count < 0 && !success);
michael@0: 
michael@0:     fCx         = newx;
michael@0:     fCy         = newy;
michael@0:     fCurveCount = SkToS8(count);
michael@0:     return success;
michael@0: }