Simple GPU based dithering

Simple GPU based dithering:

If dithering is turned on, apply an effect that filters the pixel through
the following pipeline:

for each channel c, add a random value between 0 and 1 to the floating point representation (32-bit) of c.
This is enough to bump some channels up a notch after quantization and creates a small dithering pattern.

Committed: https://skia.googlesource.com/skia/+/f461a8fdf642ba713dcdfb217534652df1eac278

[egdaniel, 2014-06-11 14:05:10]

One other thought (and probably todo in a follow up CL), as you showed me this
doesn't work great for non shallow gradients. Is there a way we could use a
similar approach to this but also take into account the derivative of the input
color to get a rate of change and then possibly use this value to set the range
for our hi/low values?

https://codereview.chromium.org/321253002/diff/1/gm/shallowgradient.cpp
File gm/shallowgradient.cpp (right):

https://codereview.chromium.org/321253002/diff/1/gm/shallowgradient.cpp#newco...
gm/shallowgradient.cpp:69: paint.setDither(true);
You may want to consider adding this gm to the gm exception list with this cl so
that you don't turn all the bots red when you commit it. And then you can
rebaseline after it has landed.

[robertphillips, 2014-06-11 14:14:33]

1gtm - but I defer to Brian and Greg

https://codereview.chromium.org/321253002/diff/1/src/gpu/effects/GrDitherEffe...
File src/gpu/effects/GrDitherEffect.cpp (right):

https://codereview.chromium.org/321253002/diff/1/src/gpu/effects/GrDitherEffe...
src/gpu/effects/GrDitherEffect.cpp:96: builder->fsCodeAppendf("\t\tfloat r = "
magic numbers?

https://codereview.chromium.org/321253002/diff/1/src/gpu/effects/GrDitherEffe...
src/gpu/effects/GrDitherEffect.cpp:101: // distance from the input channel
kSuffixes ?

[robertphillips, 2014-06-11 14:15:50]

https://codereview.chromium.org/321253002/diff/1/src/gpu/effects/GrDitherEffe...
File src/gpu/effects/GrDitherEffect.cpp (right):

https://codereview.chromium.org/321253002/diff/1/src/gpu/effects/GrDitherEffe...
src/gpu/effects/GrDitherEffect.cpp:87: 
// for each channel c:
// 1. Compute quantized colors [low, high] that c is between
// 2. Pick high by flipping a coin weighted by (c - low)

[bsalomon, 2014-06-11 14:20:16]

Any idea how it affects perf? Might be good to have a bench with
dither/non-dithered variants. In terms of triggering this, I thought the
sw-rasterizer did some special dithering for gradients independent of the
paint's dither setting. We should check on that and see if we can/should be
consistent.

[egdaniel, 2014-06-11 14:26:24]

https://codereview.chromium.org/321253002/diff/1/src/gpu/effects/GrDitherEffe...
File src/gpu/effects/GrDitherEffect.cpp (right):

https://codereview.chromium.org/321253002/diff/1/src/gpu/effects/GrDitherEffe...
src/gpu/effects/GrDitherEffect.cpp:96: builder->fsCodeAppendf("\t\tfloat r = "
On 2014/06/11 14:14:32, robertphillips wrote:
> magic numbers?

Probably should add a comment to describe it, but this one line rand number
generator is often used in glsl shaders. Basically it creates a zig zag function
then the sin adds some extra noise all the zig zags (if I remember right). But
yeah at least some explanation should be added.

[robertphillips, 2014-06-11 17:20:24]

https://codereview.chromium.org/321253002/diff/1/src/gpu/SkGr.cpp
File src/gpu/SkGr.cpp (right):

https://codereview.chromium.org/321253002/diff/1/src/gpu/SkGr.cpp#newcode469
src/gpu/SkGr.cpp:469: 
Wrap this in SK_IGNORE_GPU_DITHER and add it to
gyp/skia_for_chromium_defines.gypi? This will allow us to land this and roll it
into Chromium without having to worry about layout test regressions. Once it is
rolled we can rebaseline the Blink layout tests and remove the flag.

[krajcevski, 2014-06-11 22:33:19]

Regarding Brian's issues:

1. We spoke to Mike and it seems like it's OK to not dither unless dithering is
specifically turned on.

2. I measured the perf of this change and in all cases it increases the time it
takes to render gradients by 2X. For some, like the sweep, this still does way
better than raster, but for others, like a linear gradient, this pushes the
performance worse than raster, and that's probably not good. This is even with
skipping the dithering for the alpha channel.


I have a few more things to try:

1. I didn't realize that the fragment position was in device space. With that,
we can try an ordered dithering algorithm that should be much faster (it avoids
the nasty rand at the beginning and the bool->float cast per channel).

2. The bench that I wrote is firing the assert in SkGr.cpp that says (NULL !=
target). Given a context, is there any reliable way to determine what the
rendering target is? It seems like the only way to get at that would be from the
SkDevice, which seems janky.

https://codereview.chromium.org/321253002/diff/1/src/gpu/SkGr.cpp
File src/gpu/SkGr.cpp (right):

https://codereview.chromium.org/321253002/diff/1/src/gpu/SkGr.cpp#newcode469
src/gpu/SkGr.cpp:469: 
On 2014/06/11 17:20:24, robertphillips wrote:
> Wrap this in SK_IGNORE_GPU_DITHER and add it to
> gyp/skia_for_chromium_defines.gypi? This will allow us to land this and roll
it
> into Chromium without having to worry about layout test regressions. Once it
is
> rolled we can rebaseline the Blink layout tests and remove the flag.

Done.

https://codereview.chromium.org/321253002/diff/1/src/gpu/effects/GrDitherEffe...
File src/gpu/effects/GrDitherEffect.cpp (right):

https://codereview.chromium.org/321253002/diff/1/src/gpu/effects/GrDitherEffe...
src/gpu/effects/GrDitherEffect.cpp:87: 
On 2014/06/11 14:15:50, robertphillips wrote:
> // for each channel c:
> // 1. Compute quantized colors [low, high] that c is between
> // 2. Pick high by flipping a coin weighted by (c - low)

Done.

https://codereview.chromium.org/321253002/diff/1/src/gpu/effects/GrDitherEffe...
src/gpu/effects/GrDitherEffect.cpp:96: builder->fsCodeAppendf("\t\tfloat r = "
On 2014/06/11 14:26:24, egdaniel wrote:
> On 2014/06/11 14:14:32, robertphillips wrote:
> > magic numbers?
> 
> Probably should add a comment to describe it, but this one line rand number
> generator is often used in glsl shaders. Basically it creates a zig zag
function
> then the sin adds some extra noise all the zig zags (if I remember right). But
> yeah at least some explanation should be added. 

I added a comment for this.

https://codereview.chromium.org/321253002/diff/1/src/gpu/effects/GrDitherEffe...
src/gpu/effects/GrDitherEffect.cpp:101: // distance from the input channel
On 2014/06/11 14:14:32, robertphillips wrote:
> kSuffixes ?

Done.

[bsalomon, 2014-06-12 16:24:11]

https://codereview.chromium.org/321253002/diff/50001/src/gpu/SkGr.cpp
File src/gpu/SkGr.cpp (right):

https://codereview.chromium.org/321253002/diff/50001/src/gpu/SkGr.cpp#newcode469
src/gpu/SkGr.cpp:469: if (NULL == target) {
I'd like to understand how this happens. Falling back to the draw state's RT
doesn't seem right.

[krajcevski, 2014-06-12 18:48:35]

I think we figured out the thing that was causing context->getRenderTarget() to
return null. With that change, I was able to put my bench up for review too. 2x2
ordered dithering seems to create not too terrible shallow gradients while
maintaining perf better than raster on linear gradients. The randomized
dithering seems to produce better results, but ends up being slower than raster
on linear gradients although still significantly faster on all other gradients.

[bsalomon, 2014-06-12 19:59:54]

https://codereview.chromium.org/321253002/diff/90001/src/gpu/effects/GrDither...
File src/gpu/effects/GrDitherEffect.cpp (right):

https://codereview.chromium.org/321253002/diff/90001/src/gpu/effects/GrDither...
src/gpu/effects/GrDitherEffect.cpp:135: builder->fsCodeAppendf("\t\tint x =
int(%s.x + 0.5) & 1;\n", builder->fragmentPosition());
ES2 doesn't have integer types. We may need to have an alternate implementation.

[krajcevski, 2014-06-18 22:21:50]

OK, so after trying to figure out a clever way to generate the matrix, I simply
used the random value generated from the previous algorithm and just added that
to each channel instead of using it as a weighted value. It turns out the sin
function isn't that crucial for generating seemingly good random data (we're not
doing cryptography here.) This seems to produce pretty decent results at a
decent perf:

gradient_linear_clamp_shallow
8888:  cmsecs =   1247.57
GPU:  cmsecs =    746.64  gmsecs =    737.34

gradient_linear_clamp_shallow_dither
8888:  cmsecs =   1250.47
GPU:  cmsecs =    938.65  gmsecs =    936.05

[bsalomon, 2014-06-19 13:33:27]

Does this make it possible to produce values that aren't valid premul colors
(i.e. r, g, or b > a). I'm curious to see what the additive noise looks like
against pure white or pure black . The gradient image you emailed looked really
good.

https://codereview.chromium.org/321253002/diff/130001/src/gpu/SkGr.cpp
File src/gpu/SkGr.cpp (right):

https://codereview.chromium.org/321253002/diff/130001/src/gpu/SkGr.cpp#newcod...
src/gpu/SkGr.cpp:522: {
Can you add a comment that this block is here to restore the context state after
asNewEffect is called. I'm just concerned that we'll forget why this was done
and remove what appear to be unnecessary braces.

[egdaniel, 2014-06-19 13:41:28]

https://codereview.chromium.org/321253002/diff/130001/bench/GradientBench.cpp
File bench/GradientBench.cpp (right):

https://codereview.chromium.org/321253002/diff/130001/bench/GradientBench.cpp...
bench/GradientBench.cpp:251: fDither = true;
can we just do fDither = dither? Then no need for the else branch.

[krajcevski, 2014-06-19 13:51:43]

So, if we add the random offset to the alpha, we maintain valid premul (provided
that we received valid premul)...

if a >= x then a+r >= x+r

https://codereview.chromium.org/321253002/diff/130001/bench/GradientBench.cpp
File bench/GradientBench.cpp (right):

https://codereview.chromium.org/321253002/diff/130001/bench/GradientBench.cpp...
bench/GradientBench.cpp:251: fDither = true;
On 2014/06/19 13:41:28, egdaniel wrote:
> can we just do fDither = dither? Then no need for the else branch.

Done.

https://codereview.chromium.org/321253002/diff/130001/src/gpu/SkGr.cpp
File src/gpu/SkGr.cpp (right):

https://codereview.chromium.org/321253002/diff/130001/src/gpu/SkGr.cpp#newcod...
src/gpu/SkGr.cpp:522: {
On 2014/06/19 13:33:27, bsalomon wrote:
> Can you add a comment that this block is here to restore the context state
after
> asNewEffect is called. I'm just concerned that we'll forget why this was done
> and remove what appear to be unnecessary braces.

Done.

[bsalomon, 2014-06-19 18:08:27]

lgtm

[krajcevski, 2014-06-19 20:37:46]

The CQ bit was checked by krajcevski@google.com

[commit-bot: I haz the power, 2014-06-19 20:38:24]

CQ is trying da patch. Follow status at
 https://skia-tree-status.appspot.com/cq/krajcevski@google.com/321253002/170001

[commit-bot: I haz the power, 2014-06-19 20:38:26]

The CQ bit was unchecked by commit-bot@chromium.org

[commit-bot: I haz the power, 2014-06-19 20:38:27]

Failed to apply patch for bench/GradientBench.cpp:
While running git apply --index -p1;
  error: patch failed: bench/GradientBench.cpp:200
  error: bench/GradientBench.cpp: patch does not apply

Patch:       bench/GradientBench.cpp
Index: bench/GradientBench.cpp
diff --git a/bench/GradientBench.cpp b/bench/GradientBench.cpp
index
fa07bce4fd1f1404f686b9ee44584765782b226e..13582899bb23eab4c65138b61f99cd1bf6664eda
100644
--- a/bench/GradientBench.cpp
+++ b/bench/GradientBench.cpp
@@ -34,12 +34,15 @@ static const SkColor gColors[] = {
     SK_ColorRED, SK_ColorGREEN, SK_ColorBLUE, SK_ColorWHITE, SK_ColorBLACK, //
10 lines, 50 colors
 };
 
+static const SkColor gShallowColors[] = { 0xFF555555, 0xFF444444 };
+
 // We have several special-cases depending on the number (and spacing) of
colors, so
 // try to exercise those here.
 static const GradData gGradData[] = {
     { 2, gColors, NULL, "" },
     { 50, gColors, NULL, "_hicolor" }, // many color gradient
     { 3, gColors, NULL, "_3color" },
+    { 2, gShallowColors, NULL, "_shallow" },
 };
 
 /// Ignores scale
@@ -200,12 +203,22 @@ static const char* geomtypename(GeomType gt) {
 class GradientBench : public SkBenchmark {
     SkString fName;
     SkShader* fShader;
+    bool fDither;
     enum {
         W   = 400,
         H   = 400,
         kRepeat = 15,
     };
 public:
+    SkShader* makeShader(GradType gradType, GradData data, SkShader::TileMode
tm, float scale) {
+        const SkPoint pts[2] = {
+            { 0, 0 },
+            { SkIntToScalar(W), SkIntToScalar(H) }
+        };
+
+        return gGrads[gradType].fMaker(pts, data, tm, scale);
+    }
+
     GradientBench(GradType gradType,
                   GradData data = gGradData[0],
                   SkShader::TileMode tm = SkShader::kClamp_TileMode,
@@ -224,15 +237,25 @@ public:
 
         fName.append(data.fName);
 
-        const SkPoint pts[2] = {
-            { 0, 0 },
-            { SkIntToScalar(W), SkIntToScalar(H) }
-        };
-
-        fShader = gGrads[gradType].fMaker(pts, data, tm, scale);
+        fDither = false;
+        fShader = this->makeShader(gradType, data, tm, scale);
         fGeomType = geomType;
     }
 
+    GradientBench(GradType gradType, GradData data, bool dither) {
+        const char *tmname = tilemodename(SkShader::kClamp_TileMode);
+        fName.printf("gradient_%s_%s", gGrads[gradType].fName, tmname);
+        fName.append(data.fName);
+
+        fDither = dither;
+        if (dither) {
+            fName.appendf("_dither");
+        }
+
+        fShader = this->makeShader(gradType, data, SkShader::kClamp_TileMode,
1.0f);
+        fGeomType = kRect_GeomType;
+    }
+
     virtual ~GradientBench() {
         fShader->unref();
     }
@@ -247,6 +270,9 @@ protected:
         this->setupPaint(&paint);
 
         paint.setShader(fShader);
+        if (fDither) {
+            paint.setDither(true);
+        }
 
         SkRect r = { 0, 0, SkIntToScalar(W), SkIntToScalar(H) };
         for (int i = 0; i < loops * kRepeat; i++) {
@@ -304,6 +330,16 @@ DEF_BENCH( return new
GradientBench(kConicalOutZero_GradType); )
 DEF_BENCH( return new GradientBench(kConicalOutZero_GradType, gGradData[1]); )
 DEF_BENCH( return new GradientBench(kConicalOutZero_GradType, gGradData[2]); )
 
+// Dithering
+DEF_BENCH( return new GradientBench(kLinear_GradType, gGradData[3], true); )
+DEF_BENCH( return new GradientBench(kLinear_GradType, gGradData[3], false); )
+DEF_BENCH( return new GradientBench(kRadial_GradType, gGradData[3], true); )
+DEF_BENCH( return new GradientBench(kRadial_GradType, gGradData[3], false); )
+DEF_BENCH( return new GradientBench(kSweep_GradType, gGradData[3], true); )
+DEF_BENCH( return new GradientBench(kSweep_GradType, gGradData[3], false); )
+DEF_BENCH( return new GradientBench(kConical_GradType, gGradData[3], true); )
+DEF_BENCH( return new GradientBench(kConical_GradType, gGradData[3], false); )
+
 ///////////////////////////////////////////////////////////////////////////////
 
 class Gradient2Bench : public SkBenchmark {

[krajcevski, 2014-06-19 20:44:18]

The CQ bit was checked by krajcevski@google.com

[commit-bot: I haz the power, 2014-06-19 20:44:25]

CQ is trying da patch. Follow status at
 https://skia-tree-status.appspot.com/cq/krajcevski@google.com/321253002/170002

[commit-bot: I haz the power, 2014-06-19 21:14:14]

Change committed as f461a8fdf642ba713dcdfb217534652df1eac278

[tomhudson, 2016-04-22 16:36:01]

Nearly two years later, this is still disabled in Chrome. Is there something
blocking it from use there?