[Pixman] [PATCH] Ordered dithering with blue noise, v2

[basile-pixman]

From: Basile Clement 

On some screens (typically low quality laptop screens), using Bayer
ordered dithering has been observed to cause color changes depending on
*where the gradient is rendered on the screen*, causing visible
flickering when moving an image on the screen.

To alleviate the issue, this patch adds support for ordered dithering
using a 64x64 matrix tuned from blue noise.  In addition to being devoid
of the positional dependency on screen, the blue noise matrix also
generates more pleasing and less discernable patterns.  As such, it is
now the method used for PIXMAN_DITHER_GOOD and PIXMAN_DITHER_BEST
dithering methods.

The 64x64 blue noise matrix has been generated using the provided
`pixman/dither/make-blue-noise.c` script, which uses the
void-and-cluster method.

Changes since v1 (thanks Bill):
 - Use uint16_t for the blue noise matrix for lower memory usage
 - Use bitwise computation for array index
---
 demos/dither.c   |   1 +
 pixman/dither/blue-noise-64x64.h |  77 
 pixman/dither/make-blue-noise.c  | 679 +++
 pixman/pixman-bits-image.c   |  14 +-
 pixman/pixman.h  |   1 +
 test/tolerance-test.c|   1 +
 test/utils.c |   1 +
 7 files changed, 773 insertions(+), 1 deletion(-)
 create mode 100644 pixman/dither/blue-noise-64x64.h
 create mode 100644 pixman/dither/make-blue-noise.c

diff --git a/demos/dither.c b/demos/dither.c
index d4271e6..d72c250 100644
--- a/demos/dither.c
+++ b/demos/dither.c
@@ -78,6 +78,7 @@ static const named_int_t dithers[] =
 {
 { "None",   PIXMAN_REPEAT_NONE },
 { "Bayer 8x8",  PIXMAN_DITHER_ORDERED_BAYER_8 },
+{ "Blue noise 64x64",   PIXMAN_DITHER_ORDERED_BLUE_NOISE_64 },
 };
 
 static int
diff --git a/pixman/dither/blue-noise-64x64.h b/pixman/dither/blue-noise-64x64.h
new file mode 100644
index 000..93c8805
--- /dev/null
+++ b/pixman/dither/blue-noise-64x64.h
@@ -0,0 +1,77 @@
+/* WARNING: This file is generated by make-blue-noise.c
+ * Please edit that file instead of this one.
+ */
+
+#ifndef BLUE_NOISE_64X64_H
+#define BLUE_NOISE_64X64_H
+
+#include 
+
+static const uint16_t dither_blue_noise_64x64[4096] = {
+3039, 1368, 3169, 103, 2211, 1248, 2981, 668, 2633, 37, 3963, 2903, 384, 
2564, 3115, 1973, 3348, 830, 2505, 1293, 3054, 1060, 1505, 3268, 400, 1341, 
593, 3802, 3384, 429, 4082, 1411, 2503, 3863, 126, 1292, 1887, 2855, 205, 2094, 
2977, 1899, 3924, 356, 3088, 2500, 3942, 1409, 2293, 1734, 3732, 1291, 3227, 
277, 2054, 786, 2871, 411, 2425, 1678, 3986, 455, 2879, 2288,
+388, 1972, 3851, 778, 2768, 3697, 944, 2123, 1501, 3533, 937, 1713, 1381, 
3888, 156, 1242, 516, 2888, 1607, 3676, 632, 2397, 3804, 2673, 1898, 3534, 
2593, 1777, 1170, 2299, 3013, 1838, 523, 3053, 1647, 3601, 3197, 959, 1520, 
3633, 893, 2437, 3367, 2187, 1258, 137, 1965, 401, 3546, 643, 3087, 2498, 733, 
2786, 3371, 4053, 1266, 1977, 3663, 183, 2570, 2107, 1183, 3708,
+907, 2473, 1151, 3363, 1527, 1902, 232, 3903, 3060, 496, 2486, 3206, 2165, 
861, 2387, 3653, 2101, 3972, 132, 2162, 3437, 1827, 215, 895, 3114, 271, 969, 
2932, 197, 1598, 878, 3696, 1140, 2120, 904, 2431, 302, 3846, 2675, 481, 3187, 
66, 1440, 650, 3833, 2826, 3435, 901, 2936, 2111, 250, 1875, 3609, 1174, 1747, 
162, 2346, 3420, 913, 3172, 1383, 752, 3298, 1735,
+3540, 2938, 249, 2324, 526, 3099, 2561, 1324, 2347, 1861, 1200, 3702, 257, 
3442, 1514, 2999, 992, 1766, 2735, 1163, 478, 2943, 1279, 3635, 2177, 1464, 
3672, 2386, 3871, 3340, 2690, 64, 3489, 2811, 3999, 633, 1948, 1243, 2269, 
1807, 1143, 2750, 3729, 1790, 2363, 1053, 1537, 2636, 4065, 1076, 1476, 3869, 
450, 2200, 2676, 658, 2979, 1548, 544, 1913, 2838, 3911, 116, 2698,
+517, 1295, 3997, 1739, 3665, 1083, 3509, 599, 3400, 118, 2956, 720, 2689, 
1907, 567, 2523, 284, 3397, 711, 3219, 2450, 3985, 1665, 2549, 562, 3011, 1855, 
729, 1355, 528, 1908, 2456, 1384, 337, 1540, 2654, 3138, 3513, 703, 4080, 3314, 
2047, 855, 3037, 209, 3317, 577, 1828, 17, 2336, 3193, 2748, 962, 3441, 1450, 
3246, 1075, 3878, 2615, 3497, 1033, 2310, 1442, 2183,
+1654, 3254, 2061, 738, 2832, 148, 2030, 1670, 909, 3850, 2109, 1533, 4046, 
1085, 3098, 3897, 1378, 2248, 3829, 1495, 1966, 23, 797, 3427, 1124, 4057, 95, 
2787, 2190, 3074, 3950, 742, 3194, 1999, 3386, 1113, 16, 1657, 2804, 201, 1543, 
383, 2559, 1325, 3604, 2068, 2493, 3771, 1284, 3460, 710, 1716, 2447, 80, 3811, 
2032, 347, 2227, 15, 1689, 397, 3084, 662, 3798,
+973, 43, 2608, 3143, 1459, 2423, 4066, 2770, 3191, 1283, 2630, 314, 3235, 
2289, 72, 1822, 2840, 924, 350, 2653, 1057, 3715, 2235, 2775, 346, 2083, 1553, 
3292, 1081, 274, 1686, 1188, 2327, 3743, 578, 2234, 3916, 2519, 1011, 3056, 
2207, 3438, 3890, 537, 1617, 837, 3094, 373, 2795, 1980, 276, 3951, 1353, 3015, 
844, 1724, 3651, 2923, 1316, 4092, 2504, 3627, 1936, 2854,
+2461, 3929, 1193, 421, 3746, 820, 1180, 286, 2261, 532, 3625, 1812, 802, 
1327, 3527, 670, 3730, 2025, 3124, 3565, 529, 

Re: [Pixman] Dithering patches, v2

[Basile Clement]

There is less calculation, but the noise matrix takes up cache space
(about half a modern CPU's L1) and hence increases memory pressure.  The
actual performance relationship is probably hardware dependent, but on
my laptop doing a quick check with patched lowlevel-blt-bench:

 - Bayer is ~8% faster than blue noise
 - Bayer is only ~5% faster if I use `dither_blue_noise_64x64[((y &
0x3f) << 6) | (x & 0x3f)]` in the index computation, which I would have
expected GCC to do automatically but oh well.
 - Both are about the same speed with uint16_t array for the blue noise
(halves memory consumption).

I will make those two changes (they are clearly desirable) and re-post
the blue noise patch.  Since this is in a write-back loop which should
be memory-bound in general, I think it makes sense to keep Bayer as FAST
dithering -- but I'm not opposed to removing it.

- Basile

On 4/22/19 8:12 PM, Bill Spitzak wrote:
> Is the "blue noise" version actually slower than the Bayer? Seems to
> be doing a bit less calculation but it reading the array of weights.
> The removal of the need for the pattern offset seems like a win.
>
> On Mon, Apr 22, 2019 at 9:27 AM Matt Turner  > wrote:
>
> On Fri, Apr 19, 2019 at 4:52 PM Bryce Harrington
> mailto:br...@bryceharrington.org>> wrote:
> > Inkscape would love to see Basile's dithering patches included.  Our
> > testing shows that they make a huge quality difference for our
> users;
> > this solves a critical need.
> >
> > Mc and I have done some preliminary investigation into how to
> plumb this
> > into Cairo, and would love to hear your review of Basile's
> approach to
> > the problem.
>
> I don't feel like I'm experienced enough with that side of pixman to
> offer meaningful comments. I've Cc'd Søren in the hopes that he
> remains interested enough in the project to review the patches that
> Basile says implement the approach Søren described.
> ___
> Pixman mailing list
> Pixman@lists.freedesktop.org 
> https://lists.freedesktop.org/mailman/listinfo/pixman
>
>
> ___
> Pixman mailing list
> Pixman@lists.freedesktop.org
> https://lists.freedesktop.org/mailman/listinfo/pixman
___
Pixman mailing list
Pixman@lists.freedesktop.org
https://lists.freedesktop.org/mailman/listinfo/pixman

Re: [Pixman] Dithering patches, v2

[Bill Spitzak]

Is the "blue noise" version actually slower than the Bayer? Seems to be
doing a bit less calculation but it reading the array of weights. The
removal of the need for the pattern offset seems like a win.

On Mon, Apr 22, 2019 at 9:27 AM Matt Turner  wrote:

> On Fri, Apr 19, 2019 at 4:52 PM Bryce Harrington
>  wrote:
> > Inkscape would love to see Basile's dithering patches included.  Our
> > testing shows that they make a huge quality difference for our users;
> > this solves a critical need.
> >
> > Mc and I have done some preliminary investigation into how to plumb this
> > into Cairo, and would love to hear your review of Basile's approach to
> > the problem.
>
> I don't feel like I'm experienced enough with that side of pixman to
> offer meaningful comments. I've Cc'd Søren in the hopes that he
> remains interested enough in the project to review the patches that
> Basile says implement the approach Søren described.
> ___
> Pixman mailing list
> Pixman@lists.freedesktop.org
> https://lists.freedesktop.org/mailman/listinfo/pixman
___
Pixman mailing list
Pixman@lists.freedesktop.org
https://lists.freedesktop.org/mailman/listinfo/pixman

Re: [Pixman] Dithering patches, v2

[Matt Turner]

On Fri, Apr 19, 2019 at 4:52 PM Bryce Harrington
 wrote:
> Inkscape would love to see Basile's dithering patches included.  Our
> testing shows that they make a huge quality difference for our users;
> this solves a critical need.
>
> Mc and I have done some preliminary investigation into how to plumb this
> into Cairo, and would love to hear your review of Basile's approach to
> the problem.

I don't feel like I'm experienced enough with that side of pixman to
offer meaningful comments. I've Cc'd Søren in the hopes that he
remains interested enough in the project to review the patches that
Basile says implement the approach Søren described.
___
Pixman mailing list
Pixman@lists.freedesktop.org
https://lists.freedesktop.org/mailman/listinfo/pixman