Constructing the Bayer Matrix and Extending it to 3D
There is a pattern, which I have really only ever heard called the Bayer pattern, or Bayer matrix. I’m not sure what its origins are, but from what I can gather, it has significant applications in quantization of color data, because it is used both for dithering of output image data ( for both functional an aesthetic purpose ) and for design of the subpixel arrangement of the color sensors on digital cameras. An application for it, that I’ve recently become aware of is to amortize the cost of updating a grid, often a texture, over some power of two number of updates. This is very well illustrated by this shadertoy example, which shows the offset texels in each 4x4 neighborhood in sequence, till all are shown, then resets. That array:
0, 8, 2, 10, 12, 4, 14, 6, 3, 11, 1, 9, 15, 7, 13, 5
Basically what we are doing is deciding on this particular order in which we cover this 2d, NxN neighborhood, and saying this is the order in which I will pass offsets to the program. This offsets the whole compute dispatch, which is going to have each invocation separated by a corresponding N pixels, so that each offset in 0..N keeps it in its little NxN box. You can see that with a 2x2 neighborhood, this completes in 4 updates, a 4x4 neighborhood in 16 updates, 8x8 in 64, and larger patterns follow this same power of two sizing, but are really not practical for a lot of realtime applications. The delay between full updates is often too long to be practical, it becomes visible and undesirable. For example, at 16x16, when it is over the span of 256 frames, a full update is well over 4 full seconds at 60fps.
When constructing these larger patterns, I found something that I haven’t seen anyone else talking much about – how exactly this matrix is constructed. By taking four copies of the 4x4 pattern, and arranging them in 2d, with the given ordering, interleaving their patterns, I can create an 8x8 pattern. To put it another way – NM being the M’th entry of sequence N, with our sequences arranged as in the 0, 1, 2, 3 pattern above, pulling from each in turn, the new order is constructed as:
00, 10, 20, 30, 01, 11, 21, 31, … , 316So that’s great, you have a recursive way in which you can can construct these larger patterns, but what about smaller patterns, down to a single texel? It’s the same pattern. You can follow it. The 0, 1, 2, 3 pattern above is actually the 2x2 case, and a single texel is a single offset, degenerate case. So it follows by math induction that you when you have this pattern going from your 1x1 pattern to a 2x2 pattern, in a way that can be repeated for N+1, that can be generalized to whatever sized pattern you want to do.
There is a bit of complication having to switch back and forth between the representations of offset and order, so I wrote myself a little index #define, so that I could keep everything in a flat array the whole time. At the end, you can treat the numeric ordering as array indices for the output list, doing a triple for loop over the flat 3d array. Your three array indices are the loop control variables, 0..N. Sample code of my quick implementation here.
I got to thinking – and this is one of those questions that has been percolating in the back of my mind since shortly after I became aware of this pattern – is there a 3d analog? And if not, what would it take to create one? At this point, having rederived the 2d case, I was under the impression that this same process can be employed to create one. I designed a set of offsets, which went in similar diagonal patterns to the 0, 1, 2, 3 pattern above and generated what I believe to be a 3d analog to this Bayer matrix, again, at whatever power of two dimension you would want. If one were so inclined, they might refer to it as the Baker matrix – but I digress. You can see the proposed ordering on the cube below - use it the same way as outlined above.
This pattern sees application in a number of different places. I used it this time, to order to control the offsets in the 8x8x8 neighborhood used to amortize the update of the lighting calculations in Aquaria. There, I had better luck randomly ordering the list of offsets - the 3d matrix constucted this way highlights aliasing near the edges of spheres – not great – but I’m going to play with it more, and see if it has any practical applications. One that I want to explore is using it for dithering, on voxels, quantizing the values in the same way that you would do thresholded dithering, where each texel in this tiling pattern serves as a quantization threshold for the corresponding pixel.
