Two Point Radial Gradients

This patch implements two point radial gradients with a a center point, a focal point, and two radii.  These are required for SVG and HTML5 canvas support.  The algorithm was implemented in fixed-point, like the regular radial gradient.  All tiling modes (clamp, mirror, repeat) have been implemented.

The 32-bit path is fully exercised by WebKit/Chrome layout tests, but the 16-bit path is not.  There are also no unit tests in this patch yet, since I wasn't sure how to go about that.

There is probably still some room for optimization.  In particular, the SkFixedSqrt could be inlined and/or unrolled.  I don't think it's possible to use the sqrt cache, since the discriminant exceeds the range provided (it gave me artifacts when I tried it).

[reed, 2009-09-02 20:08:39]

Nice to finally have one of these. Thanks.

http://codereview.appspot.com/112058/diff/1/3
File src/effects/SkGradientShader.cpp (left):

http://codereview.appspot.com/112058/diff/1/3#oldcode1110
Line 1110: 
Thanks for the detailed comment. I might have preferred just
/*
   very
   big
   comment
*/

http://codereview.appspot.com/112058/diff/1/3
File src/effects/SkGradientShader.cpp (right):

http://codereview.appspot.com/112058/diff/1/3#newcode1164
Line 1164: #define TWO_POINT_RADIAL(fx, fy, diffx, diffy, startRadius, sr2d,
diffRadius, foura, oneOverTwoA, posRoot) \
Does this really have to be a macro, instead of a method or a (inline) function?

http://codereview.appspot.com/112058/diff/1/3#newcode1237
Line 1237: if (proc == clamp_tileproc)
Given the large cost of each call to TWO_POINT_RADIAL, I wonder if special
casing each of these procs is worth the code expansion at all. Did you time just
one loop and call proc() directly?

[Stephen White, 2009-09-16 22:26:59]

responded to comments, more optimization

[Stephen White, 2009-09-16 22:30:26]

On 2009/09/02 20:08:39, reed wrote:
> Nice to finally have one of these. Thanks.
> 
> http://codereview.appspot.com/112058/diff/1/3
> File src/effects/SkGradientShader.cpp (left):
> 
> http://codereview.appspot.com/112058/diff/1/3#oldcode1110
> Line 1110: 
> Thanks for the detailed comment. I might have preferred just
> /*
>    very
>    big
>    comment
> */
> 

Done.

> http://codereview.appspot.com/112058/diff/1/3
> File src/effects/SkGradientShader.cpp (right):
> 
> http://codereview.appspot.com/112058/diff/1/3#newcode1164
> Line 1164: #define TWO_POINT_RADIAL(fx, fy, diffx, diffy, startRadius, sr2d,
> diffRadius, foura, oneOverTwoA, posRoot) \
> Does this really have to be a macro, instead of a method or a (inline)
function?

I used a macro initially, since MSVC is reluctant to inline things unless you
use __forceinline.  Changed it to an function, and it's actually faster.  Guess
MSVC is right in this case.

> http://codereview.appspot.com/112058/diff/1/3#newcode1237
> Line 1237: if (proc == clamp_tileproc)
> Given the large cost of each call to TWO_POINT_RADIAL, I wonder if special
> casing each of these procs is worth the code expansion at all. Did you time
just
> one loop and call proc() directly?

It's about a 7% speedup, which I think is worth it.

[reed, 2009-09-17 14:51:37]

Again, nice work.

I'd really like to start pulling each of these specialty subclasses into their
own impl files (same for radial, sweep, etc.), just to make the file more
readable. However, since that will necessitate also splitting out the shared
base class, lets do that after this is checked in.

If your timings are correct, we should definitely look into supporting a
float/double alternative impl if its that much faster (maybe also for radial and
sweep too). Again, something to do in a subsequent CL.

http://codereview.appspot.com/112058/diff/4001/5002
File src/effects/SkGradientShader.cpp (right):

http://codereview.appspot.com/112058/diff/4001/5002#newcode1141
Line 1141: 
(Sx - Ey)^2  ---> (Sy - Ey)^2  I presume

http://codereview.appspot.com/112058/diff/4001/5002#newcode1145
Line 1145: 
Just for my own benefit:

Dx = Sx - Ex
Dy = Sy - Ey
Dr = Sr - Dr
dx = x - Sx
dy = y - Sy

[Dx^2 + Dy^2 - Dr^2] * t^2
+ [Dx * dx + Dy * dy + Dr * Sr] * 2 * t
+ [dx^2 + dy^2 - Sr^2] = 0

http://codereview.appspot.com/112058/diff/4001/5002#newcode1206
Line 1206: fSr2D2 = SkScalarSquare(fStartRadius);
 -1  ---> - SK_Scalar1 (or SkIntToScalar(1))

http://codereview.appspot.com/112058/diff/4001/5002#newcode1207
Line 1207: fA = SkScalarSquare(fDiff.fX) + SkScalarSquare(fDiff.fY) - 1;
SkScalarInvert(fA * 2);

http://codereview.appspot.com/112058/diff/4001/5002#newcode1217
Line 1217: // Zero difference between radii:  fill with transparent black.
Don't understand this.

side-note: if this is necessary, better to call sk_bzero(dstC, count *
sizeof(*dstC))

http://codereview.appspot.com/112058/diff/4001/5002#newcode1266
Line 1266: }
We can't fold the mirror and repeat cases into just one which calls proc(t) ?

http://codereview.appspot.com/112058/diff/4001/5002#newcode1309
Line 1309: }
I'd be curious to see if we get a proportional speed win by having this
entry-point (esp. since we're not dithering in the loops). This is optional, and
if the loops are really fast, it helps rather than calling shapeSpan() and then
down-sampling the result (done by the caller).

[Stephen White, 2009-09-22 14:48:04]

New version uploading now.

http://codereview.appspot.com/112058/diff/4001/5002
File src/effects/SkGradientShader.cpp (right):

http://codereview.appspot.com/112058/diff/4001/5002#newcode1141
Line 1141: 
On 2009/09/17 14:51:38, reed wrote:
> (Sx - Ey)^2  ---> (Sy - Ey)^2  I presume

Done.

http://codereview.appspot.com/112058/diff/4001/5002#newcode1145
Line 1145: 
On 2009/09/17 14:51:38, reed wrote:
> Just for my own benefit:
> 
> Dx = Sx - Ex
> Dy = Sy - Ey
> Dr = Sr - Dr
> dx = x - Sx
> dy = y - Sy
> 
> [Dx^2 + Dy^2 - Dr^2] * t^2
> + [Dx * dx + Dy * dy + Dr * Sr] * 2 * t
> + [dx^2 + dy^2 - Sr^2] = 0
> 

Yep, that's clearer.  Done.

http://codereview.appspot.com/112058/diff/4001/5002#newcode1206
Line 1206: fSr2D2 = SkScalarSquare(fStartRadius);
On 2009/09/17 14:51:38, reed wrote:
>  -1  ---> - SK_Scalar1 (or SkIntToScalar(1))

Done.

http://codereview.appspot.com/112058/diff/4001/5002#newcode1207
Line 1207: fA = SkScalarSquare(fDiff.fX) + SkScalarSquare(fDiff.fY) - 1;
On 2009/09/17 14:51:38, reed wrote:
> SkScalarInvert(fA * 2);

Done.

http://codereview.appspot.com/112058/diff/4001/5002#newcode1217
Line 1217: // Zero difference between radii:  fill with transparent black.
On 2009/09/17 14:51:38, reed wrote:
> Don't understand this.

Since we're dividing by fDiffRadius, it better not be zero.  Technically, I
suppose it should probably do something more clever for same radius but
different centers, I'm sure what the behaviour should be.

> side-note: if this is necessary, better to call sk_bzero(dstC, count *
> sizeof(*dstC))

Done.

http://codereview.appspot.com/112058/diff/4001/5002#newcode1266
Line 1266: }
On 2009/09/17 14:51:38, reed wrote:
> We can't fold the mirror and repeat cases into just one which calls proc(t) ?

We lose around 5% perf to the function ptr.

http://codereview.appspot.com/112058/diff/4001/5002#newcode1309
Line 1309: }
On 2009/09/17 14:51:38, reed wrote:
> I'd be curious to see if we get a proportional speed win by having this
> entry-point (esp. since we're not dithering in the loops). This is optional,
and
> if the loops are really fast, it helps rather than calling shapeSpan() and
then
> down-sampling the result (done by the caller).

You mean, is it worth it to have a 16-bit path?  To be honest, I couldn't even
figure out how to exercise this from WebKit.  If you want me to remove it, I'm
fine with that.

[Stephen White, 2009-09-22 15:01:04]

responded to comments

[reed, 2009-09-22 15:20:12]

Lets remove the 16bit path for now.

Wow, 5% just for the function-ptr instead of the function. Would never have
guessed.

LGTM

[Stephen White, 2009-09-22 16:01:46]

Removed shadeSpan16