Ordered dithering matrix generation

[makew0rld]

Hello!

I was wondering how you are generating ordered dithering matrices (bayer) that are not "square". For example I can choose 4x1 in the web app.

This appears to be done here: https://github.com/ShadowfaxRodeo/dither-me-this/blob/main/src/functions/bayer-matrix.js

Could you explain this code, and your source for it?

[DitheringIdiot]

Hello!

I'm cheating. I took the 16 x 16 matrix from this wikipedia article: https://en.wikipedia.org/wiki/Ordered_dithering

Then I take a subset of that 16x16 grid starting from the top left corner. So 3x2 is the first 3 columns and 2 rows of the 16x16 matrix.

Unless it's a 4x4 or 8x8 then I have the proper ones already worked out.

I spent a very long time trying to work out how to do this properly but gave up.

There is an explanation on how to do this properly on this site: https://bisqwit.iki.fi/story/howto/dither/jy/

Probably not the answer you we're looking for but I hope it helps!

[makew0rld]

Thanks. I assume you're referring to this section specifically: https://bisqwit.iki.fi/story/howto/dither/jy/#Appendix%202ThresholdMatrix

I did some research on your "algorithm" and found some weird things. Like for the 4x2 matrix listed on the site, it equals (when divided) the left two columns of the 4x4 matrix, which would make it seem like the way you are doing things is bad, because you'd be taking the top two rows. But it's not even equal to the two columns in order, so you can't just do some rotation. It matches up in this weird curly way. Look:

  X=4, Y=2:
       0   4   2   6 | 1/8
       3   7   1   5 |

  X=4, Y=4:
       0  12   3  15 | 1/16
       8   4  11   7 |
       2  14   1  13 |
      10   6   9   5 |

If you divide each matrix, the top row of 4x2 corresponds (in order) to these numbers in 4x4: 0, 8, 4, 12. And the bottom row of 4x2: 6, 14, 2, 10.

If you point to each of these numbers, you can see how it curls. Now, is this good or bad? Is the curling important or a quirk of the bit math in the example code on the site? I have no idea. But I'm more inclined to believe that Joel Yliluoma is correct, considering the quality of the other work on that page.

In my opinion the easiest solution to this is not to try and calculate pseudo-toroidal distance and do a 2D matrix sort (yikes) as your code comments show, but to just copy the bit math in the example code on the site, under the part that mentions "easily be extended for other rectangular matrices". Here it is:

    for(unsigned M=0; M<=3; ++M)
    for(unsigned L=0; L<=3; ++L)
    {
        const unsigned xdim = 1 << M;
        const unsigned ydim = 1 << L;
        printf(" X=%u, Y=%u:\n", xdim,ydim);
        for(unsigned y=0; y<ydim; ++y)
        {
            printf("   ");
            for(unsigned x=0; x<xdim; ++x)
            {
                unsigned v = 0, offset=0, xmask = M, ymask = L;                         
                if(M==0 || (M > L && L != 0))
                {
                    unsigned xc = x ^ ((y << M) >> L), yc = y;
                    for(unsigned bit=0; bit < M+L; )
                    {
                        v |= ((yc >> --ymask)&1) << bit++;
                        for(offset += M; offset >= L; offset -= L)
                            v |= ((xc >> --xmask)&1) << bit++;
                    }
                }
                else
                {   
                    unsigned xc = x, yc = y ^ ((x << L) >> M);
                    for(unsigned bit=0; bit < M+L; )
                    {
                        v |= ((xc >> --xmask)&1) << bit++;
                        for(offset += L; offset >= M; offset -= M)
                            v |= ((yc >> --ymask)&1) << bit++;
                    }
                }
                printf("%4d", v);
            }
            printf(" |");
            if(y == 0) printf(" 1/%u", xdim * ydim);
            printf("\n");
        }
    }

Note that M and L are the powers of the side lengths with base 2 for X and Y respectively. So 4x2 has M=2, L=1, because 2^2 = 4 and 2^1 = 2. And note that this code generates multiple matrices.

The disadvantage of this is that you can't generate matrices where the side lengths aren't powers of two. While that's unfortunate, I don't think you were really getting those matrices with your previously method anyway. At least this way it's correct.

You could also just create the irregular ones by hand, I guess by calculating the pseudo-toroidal distance yourself and just moving them around? Joel has provided 5x3 and 3x3 on the site, saying he designed them by hand.

Edit: note the bit math is all done on unsigned 16-bit integers.

If you end up doing this, let me know if you need any help. I've just re-implemented and tested this code in Go, which is far from JS, but will be more helpful than C. I can share it here if you'd like,