src/third_party/skia/src/core/SkEdge.cpp

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