1.1 --- /dev/null Thu Jan 01 00:00:00 1970 +0000
1.2 +++ b/gfx/skia/trunk/src/core/SkEdge.cpp Wed Dec 31 06:09:35 2014 +0100
1.3 @@ -0,0 +1,467 @@
1.4 +
1.5 +/*
1.6 + * Copyright 2006 The Android Open Source Project
1.7 + *
1.8 + * Use of this source code is governed by a BSD-style license that can be
1.9 + * found in the LICENSE file.
1.10 + */
1.11 +
1.12 +
1.13 +#include "SkEdge.h"
1.14 +#include "SkFDot6.h"
1.15 +#include "SkMath.h"
1.16 +
1.17 +/*
1.18 + In setLine, setQuadratic, setCubic, the first thing we do is to convert
1.19 + the points into FDot6. This is modulated by the shift parameter, which
1.20 + will either be 0, or something like 2 for antialiasing.
1.21 +
1.22 + In the float case, we want to turn the float into .6 by saying pt * 64,
1.23 + or pt * 256 for antialiasing. This is implemented as 1 << (shift + 6).
1.24 +
1.25 + In the fixed case, we want to turn the fixed into .6 by saying pt >> 10,
1.26 + or pt >> 8 for antialiasing. This is implemented as pt >> (10 - shift).
1.27 +*/
1.28 +
1.29 +static inline SkFixed SkFDot6ToFixedDiv2(SkFDot6 value) {
1.30 + // we want to return SkFDot6ToFixed(value >> 1), but we don't want to throw
1.31 + // away data in value, so just perform a modify up-shift
1.32 + return value << (16 - 6 - 1);
1.33 +}
1.34 +
1.35 +/////////////////////////////////////////////////////////////////////////
1.36 +
1.37 +int SkEdge::setLine(const SkPoint& p0, const SkPoint& p1, const SkIRect* clip,
1.38 + int shift) {
1.39 + SkFDot6 x0, y0, x1, y1;
1.40 +
1.41 + {
1.42 + float scale = float(1 << (shift + 6));
1.43 + x0 = int(p0.fX * scale);
1.44 + y0 = int(p0.fY * scale);
1.45 + x1 = int(p1.fX * scale);
1.46 + y1 = int(p1.fY * scale);
1.47 + }
1.48 +
1.49 + int winding = 1;
1.50 +
1.51 + if (y0 > y1) {
1.52 + SkTSwap(x0, x1);
1.53 + SkTSwap(y0, y1);
1.54 + winding = -1;
1.55 + }
1.56 +
1.57 + int top = SkFDot6Round(y0);
1.58 + int bot = SkFDot6Round(y1);
1.59 +
1.60 + // are we a zero-height line?
1.61 + if (top == bot) {
1.62 + return 0;
1.63 + }
1.64 + // are we completely above or below the clip?
1.65 + if (NULL != clip && (top >= clip->fBottom || bot <= clip->fTop)) {
1.66 + return 0;
1.67 + }
1.68 +
1.69 + SkFixed slope = SkFDot6Div(x1 - x0, y1 - y0);
1.70 + const int dy = SkEdge_Compute_DY(top, y0);
1.71 +
1.72 + fX = SkFDot6ToFixed(x0 + SkFixedMul(slope, dy)); // + SK_Fixed1/2
1.73 + fDX = slope;
1.74 + fFirstY = top;
1.75 + fLastY = bot - 1;
1.76 + fCurveCount = 0;
1.77 + fWinding = SkToS8(winding);
1.78 + fCurveShift = 0;
1.79 +
1.80 + if (clip) {
1.81 + this->chopLineWithClip(*clip);
1.82 + }
1.83 + return 1;
1.84 +}
1.85 +
1.86 +// called from a curve subclass
1.87 +int SkEdge::updateLine(SkFixed x0, SkFixed y0, SkFixed x1, SkFixed y1)
1.88 +{
1.89 + SkASSERT(fWinding == 1 || fWinding == -1);
1.90 + SkASSERT(fCurveCount != 0);
1.91 +// SkASSERT(fCurveShift != 0);
1.92 +
1.93 + y0 >>= 10;
1.94 + y1 >>= 10;
1.95 +
1.96 + SkASSERT(y0 <= y1);
1.97 +
1.98 + int top = SkFDot6Round(y0);
1.99 + int bot = SkFDot6Round(y1);
1.100 +
1.101 +// SkASSERT(top >= fFirstY);
1.102 +
1.103 + // are we a zero-height line?
1.104 + if (top == bot)
1.105 + return 0;
1.106 +
1.107 + x0 >>= 10;
1.108 + x1 >>= 10;
1.109 +
1.110 + SkFixed slope = SkFDot6Div(x1 - x0, y1 - y0);
1.111 + const int dy = SkEdge_Compute_DY(top, y0);
1.112 +
1.113 + fX = SkFDot6ToFixed(x0 + SkFixedMul(slope, dy)); // + SK_Fixed1/2
1.114 + fDX = slope;
1.115 + fFirstY = top;
1.116 + fLastY = bot - 1;
1.117 +
1.118 + return 1;
1.119 +}
1.120 +
1.121 +void SkEdge::chopLineWithClip(const SkIRect& clip)
1.122 +{
1.123 + int top = fFirstY;
1.124 +
1.125 + SkASSERT(top < clip.fBottom);
1.126 +
1.127 + // clip the line to the top
1.128 + if (top < clip.fTop)
1.129 + {
1.130 + SkASSERT(fLastY >= clip.fTop);
1.131 + fX += fDX * (clip.fTop - top);
1.132 + fFirstY = clip.fTop;
1.133 + }
1.134 +}
1.135 +
1.136 +///////////////////////////////////////////////////////////////////////////////
1.137 +
1.138 +/* We store 1<<shift in a (signed) byte, so its maximum value is 1<<6 == 64.
1.139 + Note that this limits the number of lines we use to approximate a curve.
1.140 + If we need to increase this, we need to store fCurveCount in something
1.141 + larger than int8_t.
1.142 +*/
1.143 +#define MAX_COEFF_SHIFT 6
1.144 +
1.145 +static inline SkFDot6 cheap_distance(SkFDot6 dx, SkFDot6 dy)
1.146 +{
1.147 + dx = SkAbs32(dx);
1.148 + dy = SkAbs32(dy);
1.149 + // return max + min/2
1.150 + if (dx > dy)
1.151 + dx += dy >> 1;
1.152 + else
1.153 + dx = dy + (dx >> 1);
1.154 + return dx;
1.155 +}
1.156 +
1.157 +static inline int diff_to_shift(SkFDot6 dx, SkFDot6 dy)
1.158 +{
1.159 + // cheap calc of distance from center of p0-p2 to the center of the curve
1.160 + SkFDot6 dist = cheap_distance(dx, dy);
1.161 +
1.162 + // shift down dist (it is currently in dot6)
1.163 + // down by 5 should give us 1/2 pixel accuracy (assuming our dist is accurate...)
1.164 + // this is chosen by heuristic: make it as big as possible (to minimize segments)
1.165 + // ... but small enough so that our curves still look smooth
1.166 + dist = (dist + (1 << 4)) >> 5;
1.167 +
1.168 + // each subdivision (shift value) cuts this dist (error) by 1/4
1.169 + return (32 - SkCLZ(dist)) >> 1;
1.170 +}
1.171 +
1.172 +int SkQuadraticEdge::setQuadratic(const SkPoint pts[3], int shift)
1.173 +{
1.174 + SkFDot6 x0, y0, x1, y1, x2, y2;
1.175 +
1.176 + {
1.177 + float scale = float(1 << (shift + 6));
1.178 + x0 = int(pts[0].fX * scale);
1.179 + y0 = int(pts[0].fY * scale);
1.180 + x1 = int(pts[1].fX * scale);
1.181 + y1 = int(pts[1].fY * scale);
1.182 + x2 = int(pts[2].fX * scale);
1.183 + y2 = int(pts[2].fY * scale);
1.184 + }
1.185 +
1.186 + int winding = 1;
1.187 + if (y0 > y2)
1.188 + {
1.189 + SkTSwap(x0, x2);
1.190 + SkTSwap(y0, y2);
1.191 + winding = -1;
1.192 + }
1.193 + SkASSERT(y0 <= y1 && y1 <= y2);
1.194 +
1.195 + int top = SkFDot6Round(y0);
1.196 + int bot = SkFDot6Round(y2);
1.197 +
1.198 + // are we a zero-height quad (line)?
1.199 + if (top == bot)
1.200 + return 0;
1.201 +
1.202 + // compute number of steps needed (1 << shift)
1.203 + {
1.204 + SkFDot6 dx = ((x1 << 1) - x0 - x2) >> 2;
1.205 + SkFDot6 dy = ((y1 << 1) - y0 - y2) >> 2;
1.206 + shift = diff_to_shift(dx, dy);
1.207 + SkASSERT(shift >= 0);
1.208 + }
1.209 + // need at least 1 subdivision for our bias trick
1.210 + if (shift == 0) {
1.211 + shift = 1;
1.212 + } else if (shift > MAX_COEFF_SHIFT) {
1.213 + shift = MAX_COEFF_SHIFT;
1.214 + }
1.215 +
1.216 + fWinding = SkToS8(winding);
1.217 + //fCubicDShift only set for cubics
1.218 + fCurveCount = SkToS8(1 << shift);
1.219 +
1.220 + /*
1.221 + * We want to reformulate into polynomial form, to make it clear how we
1.222 + * should forward-difference.
1.223 + *
1.224 + * p0 (1 - t)^2 + p1 t(1 - t) + p2 t^2 ==> At^2 + Bt + C
1.225 + *
1.226 + * A = p0 - 2p1 + p2
1.227 + * B = 2(p1 - p0)
1.228 + * C = p0
1.229 + *
1.230 + * Our caller must have constrained our inputs (p0..p2) to all fit into
1.231 + * 16.16. However, as seen above, we sometimes compute values that can be
1.232 + * larger (e.g. B = 2*(p1 - p0)). To guard against overflow, we will store
1.233 + * A and B at 1/2 of their actual value, and just apply a 2x scale during
1.234 + * application in updateQuadratic(). Hence we store (shift - 1) in
1.235 + * fCurveShift.
1.236 + */
1.237 +
1.238 + fCurveShift = SkToU8(shift - 1);
1.239 +
1.240 + SkFixed A = SkFDot6ToFixedDiv2(x0 - x1 - x1 + x2); // 1/2 the real value
1.241 + SkFixed B = SkFDot6ToFixed(x1 - x0); // 1/2 the real value
1.242 +
1.243 + fQx = SkFDot6ToFixed(x0);
1.244 + fQDx = B + (A >> shift); // biased by shift
1.245 + fQDDx = A >> (shift - 1); // biased by shift
1.246 +
1.247 + A = SkFDot6ToFixedDiv2(y0 - y1 - y1 + y2); // 1/2 the real value
1.248 + B = SkFDot6ToFixed(y1 - y0); // 1/2 the real value
1.249 +
1.250 + fQy = SkFDot6ToFixed(y0);
1.251 + fQDy = B + (A >> shift); // biased by shift
1.252 + fQDDy = A >> (shift - 1); // biased by shift
1.253 +
1.254 + fQLastX = SkFDot6ToFixed(x2);
1.255 + fQLastY = SkFDot6ToFixed(y2);
1.256 +
1.257 + return this->updateQuadratic();
1.258 +}
1.259 +
1.260 +int SkQuadraticEdge::updateQuadratic()
1.261 +{
1.262 + int success;
1.263 + int count = fCurveCount;
1.264 + SkFixed oldx = fQx;
1.265 + SkFixed oldy = fQy;
1.266 + SkFixed dx = fQDx;
1.267 + SkFixed dy = fQDy;
1.268 + SkFixed newx, newy;
1.269 + int shift = fCurveShift;
1.270 +
1.271 + SkASSERT(count > 0);
1.272 +
1.273 + do {
1.274 + if (--count > 0)
1.275 + {
1.276 + newx = oldx + (dx >> shift);
1.277 + dx += fQDDx;
1.278 + newy = oldy + (dy >> shift);
1.279 + dy += fQDDy;
1.280 + }
1.281 + else // last segment
1.282 + {
1.283 + newx = fQLastX;
1.284 + newy = fQLastY;
1.285 + }
1.286 + success = this->updateLine(oldx, oldy, newx, newy);
1.287 + oldx = newx;
1.288 + oldy = newy;
1.289 + } while (count > 0 && !success);
1.290 +
1.291 + fQx = newx;
1.292 + fQy = newy;
1.293 + fQDx = dx;
1.294 + fQDy = dy;
1.295 + fCurveCount = SkToS8(count);
1.296 + return success;
1.297 +}
1.298 +
1.299 +/////////////////////////////////////////////////////////////////////////
1.300 +
1.301 +static inline int SkFDot6UpShift(SkFDot6 x, int upShift) {
1.302 + SkASSERT((x << upShift >> upShift) == x);
1.303 + return x << upShift;
1.304 +}
1.305 +
1.306 +/* f(1/3) = (8a + 12b + 6c + d) / 27
1.307 + f(2/3) = (a + 6b + 12c + 8d) / 27
1.308 +
1.309 + f(1/3)-b = (8a - 15b + 6c + d) / 27
1.310 + f(2/3)-c = (a + 6b - 15c + 8d) / 27
1.311 +
1.312 + use 16/512 to approximate 1/27
1.313 +*/
1.314 +static SkFDot6 cubic_delta_from_line(SkFDot6 a, SkFDot6 b, SkFDot6 c, SkFDot6 d)
1.315 +{
1.316 + SkFDot6 oneThird = ((a << 3) - ((b << 4) - b) + 6*c + d) * 19 >> 9;
1.317 + SkFDot6 twoThird = (a + 6*b - ((c << 4) - c) + (d << 3)) * 19 >> 9;
1.318 +
1.319 + return SkMax32(SkAbs32(oneThird), SkAbs32(twoThird));
1.320 +}
1.321 +
1.322 +int SkCubicEdge::setCubic(const SkPoint pts[4], const SkIRect* clip, int shift)
1.323 +{
1.324 + SkFDot6 x0, y0, x1, y1, x2, y2, x3, y3;
1.325 +
1.326 + {
1.327 + float scale = float(1 << (shift + 6));
1.328 + x0 = int(pts[0].fX * scale);
1.329 + y0 = int(pts[0].fY * scale);
1.330 + x1 = int(pts[1].fX * scale);
1.331 + y1 = int(pts[1].fY * scale);
1.332 + x2 = int(pts[2].fX * scale);
1.333 + y2 = int(pts[2].fY * scale);
1.334 + x3 = int(pts[3].fX * scale);
1.335 + y3 = int(pts[3].fY * scale);
1.336 + }
1.337 +
1.338 + int winding = 1;
1.339 + if (y0 > y3)
1.340 + {
1.341 + SkTSwap(x0, x3);
1.342 + SkTSwap(x1, x2);
1.343 + SkTSwap(y0, y3);
1.344 + SkTSwap(y1, y2);
1.345 + winding = -1;
1.346 + }
1.347 +
1.348 + int top = SkFDot6Round(y0);
1.349 + int bot = SkFDot6Round(y3);
1.350 +
1.351 + // are we a zero-height cubic (line)?
1.352 + if (top == bot)
1.353 + return 0;
1.354 +
1.355 + // are we completely above or below the clip?
1.356 + if (clip && (top >= clip->fBottom || bot <= clip->fTop))
1.357 + return 0;
1.358 +
1.359 + // compute number of steps needed (1 << shift)
1.360 + {
1.361 + // Can't use (center of curve - center of baseline), since center-of-curve
1.362 + // need not be the max delta from the baseline (it could even be coincident)
1.363 + // so we try just looking at the two off-curve points
1.364 + SkFDot6 dx = cubic_delta_from_line(x0, x1, x2, x3);
1.365 + SkFDot6 dy = cubic_delta_from_line(y0, y1, y2, y3);
1.366 + // add 1 (by observation)
1.367 + shift = diff_to_shift(dx, dy) + 1;
1.368 + }
1.369 + // need at least 1 subdivision for our bias trick
1.370 + SkASSERT(shift > 0);
1.371 + if (shift > MAX_COEFF_SHIFT) {
1.372 + shift = MAX_COEFF_SHIFT;
1.373 + }
1.374 +
1.375 + /* Since our in coming data is initially shifted down by 10 (or 8 in
1.376 + antialias). That means the most we can shift up is 8. However, we
1.377 + compute coefficients with a 3*, so the safest upshift is really 6
1.378 + */
1.379 + int upShift = 6; // largest safe value
1.380 + int downShift = shift + upShift - 10;
1.381 + if (downShift < 0) {
1.382 + downShift = 0;
1.383 + upShift = 10 - shift;
1.384 + }
1.385 +
1.386 + fWinding = SkToS8(winding);
1.387 + fCurveCount = SkToS8(-1 << shift);
1.388 + fCurveShift = SkToU8(shift);
1.389 + fCubicDShift = SkToU8(downShift);
1.390 +
1.391 + SkFixed B = SkFDot6UpShift(3 * (x1 - x0), upShift);
1.392 + SkFixed C = SkFDot6UpShift(3 * (x0 - x1 - x1 + x2), upShift);
1.393 + SkFixed D = SkFDot6UpShift(x3 + 3 * (x1 - x2) - x0, upShift);
1.394 +
1.395 + fCx = SkFDot6ToFixed(x0);
1.396 + fCDx = B + (C >> shift) + (D >> 2*shift); // biased by shift
1.397 + fCDDx = 2*C + (3*D >> (shift - 1)); // biased by 2*shift
1.398 + fCDDDx = 3*D >> (shift - 1); // biased by 2*shift
1.399 +
1.400 + B = SkFDot6UpShift(3 * (y1 - y0), upShift);
1.401 + C = SkFDot6UpShift(3 * (y0 - y1 - y1 + y2), upShift);
1.402 + D = SkFDot6UpShift(y3 + 3 * (y1 - y2) - y0, upShift);
1.403 +
1.404 + fCy = SkFDot6ToFixed(y0);
1.405 + fCDy = B + (C >> shift) + (D >> 2*shift); // biased by shift
1.406 + fCDDy = 2*C + (3*D >> (shift - 1)); // biased by 2*shift
1.407 + fCDDDy = 3*D >> (shift - 1); // biased by 2*shift
1.408 +
1.409 + fCLastX = SkFDot6ToFixed(x3);
1.410 + fCLastY = SkFDot6ToFixed(y3);
1.411 +
1.412 + if (clip)
1.413 + {
1.414 + do {
1.415 + if (!this->updateCubic()) {
1.416 + return 0;
1.417 + }
1.418 + } while (!this->intersectsClip(*clip));
1.419 + this->chopLineWithClip(*clip);
1.420 + return 1;
1.421 + }
1.422 + return this->updateCubic();
1.423 +}
1.424 +
1.425 +int SkCubicEdge::updateCubic()
1.426 +{
1.427 + int success;
1.428 + int count = fCurveCount;
1.429 + SkFixed oldx = fCx;
1.430 + SkFixed oldy = fCy;
1.431 + SkFixed newx, newy;
1.432 + const int ddshift = fCurveShift;
1.433 + const int dshift = fCubicDShift;
1.434 +
1.435 + SkASSERT(count < 0);
1.436 +
1.437 + do {
1.438 + if (++count < 0)
1.439 + {
1.440 + newx = oldx + (fCDx >> dshift);
1.441 + fCDx += fCDDx >> ddshift;
1.442 + fCDDx += fCDDDx;
1.443 +
1.444 + newy = oldy + (fCDy >> dshift);
1.445 + fCDy += fCDDy >> ddshift;
1.446 + fCDDy += fCDDDy;
1.447 + }
1.448 + else // last segment
1.449 + {
1.450 + // SkDebugf("LastX err=%d, LastY err=%d\n", (oldx + (fCDx >> shift) - fLastX), (oldy + (fCDy >> shift) - fLastY));
1.451 + newx = fCLastX;
1.452 + newy = fCLastY;
1.453 + }
1.454 +
1.455 + // we want to say SkASSERT(oldy <= newy), but our finite fixedpoint
1.456 + // doesn't always achieve that, so we have to explicitly pin it here.
1.457 + if (newy < oldy) {
1.458 + newy = oldy;
1.459 + }
1.460 +
1.461 + success = this->updateLine(oldx, oldy, newx, newy);
1.462 + oldx = newx;
1.463 + oldy = newy;
1.464 + } while (count < 0 && !success);
1.465 +
1.466 + fCx = newx;
1.467 + fCy = newy;
1.468 + fCurveCount = SkToS8(count);
1.469 + return success;
1.470 +}
