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