Using DIB sections to perform bulk color mapping
17th Nov 2006, 00:11 GMT
When doing dithering, one operation you have to do for every pixel is map it (more accurately, map a modified version of it) to the nearest color in your available palette. Since this is part of the dithering inner loop, you need this operation to be as fast as possible.¹ A common technique for this is to precompute the nearest palette index for a dense sampling of colors. Any time you need to convert a pixel, you can find a nearby entry in the sampling and look up the precomputed nearest palette index. This won't give you the absolute best match for colors that are very close to the halfway point between two palette colors, but error diffusion dithering is an approximation anyway; if you choose your dense sampling to be "dense enough", these errors are small and are accounted for in the error diffusion algorithm. But how do you build up this table mapping each color in your dense sampling to the palette? One way is to call GetNearestPaletteIndex for every pixel in the dense sampling. But the dense sampling by its nature has a large number of entries, and each call to GetNearestPaletteIndex is a ring transition. If only there were a way to do a bulk call to GetNearestPaletteIndex where you pass a whole bunch of COLORREFs at once. But there is a way to do that, and that's the idea kernel for today. After all, GDI does it when you do a 24-bit to 8-bit blit. You can harness this energy with the aid of DIB sections: Create a source bitmap that consists of all the color values in your dense sample and a destination bitmap that is an 8bpp DIB section with your palette as its color table. Blit the source onto the destination, and the result is a destination that is exactly the mapping table you need! Let's code this up. For the sake of illustration, our dense sampling will consist of 32768 data points distributed throughout the 555 color space. In that way, we can take an RGB value and map it to our 8-bit palette by means of the following expression: extern BYTE table[32][32][32]; index = table[red >> 3][green >> 3][blue >> 3]; Since bitmaps are two-dimensional, we can't generate a three-dimensional table like the one given above. Let's view it not as a 32 × 32 × 32 array but rather as a one-dimensional array with 32768 elements. (This is, after all, how it's represented in memory anyway, so it's not like we're really changing anything physically.) With that minor change of point of view, we're ready to generate the desired table: void CreateMappingTable(HPALETTE hpal) { struct { BITMAPINFOHEADER bmiHeader; union { RGBQUAD bmiColors[256]; // when in palette mode DWORD rgMasks[3]; // when in BI_BITFIELDS mode }; } bmi; PALETTEENTRY rgpe[256]; UINT cColors = GetPaletteEntries(hpal, 0, 256, rgpe); if (cColors) { for (UINT i = 0; i < cColors; i++) { bmi.bmiColors[i].rgbRed = rgpe[i].peRed; bmi.bmiColors[i].rgbBlue = rgpe[i].peBlue; bmi.bmiColors[i].rgbGreen = rgpe[i].peGreen; bmi.bmiColors[i].rgbReserved = 0; } bmi.bmiHeader.biSize = sizeof(bmi.bmiHeader); bmi.bmiHeader.biWidth = 32768; bmi.bmiHeader.biHeight = 1; bmi.bmiHeader.biPlanes = 1; bmi.bmiHeader.biBitCount = 8; bmi.bmiHeader.biCompression = BI_RGB; bmi.bmiHeader.biSizeImage = 32768; bmi.bmiHeader.biClrImportant = cColors; bmi.bmiHeader.biClrUsed = 0; bmi.bmiHeader.biXPelsPerMeter = 0; bmi.bmiHeader.biYPelsPerMeter = 0; void *pv8bpp; HBITMAP hbmTable = CreateDIBSection(NULL, (BITMAPINFO*)&bmi, DIB_RGB_COLORS, &pv8bpp, NULL, 0); if (hbmTable) { WORD rgw555[32768]; for (int i = 0; i < 32768; i++) { rgw555[i] = (WORD)i; } bmi.bmiHeader.biSize = sizeof(bmi.bmiHeader); bmi.bmiHeader.biWidth = 32768; bmi.bmiHeader.biHeight = 1; bmi.bmiHeader.biPlanes = 1; bmi.bmiHeader.biBitCount = 16; bmi.bmiHeader.biCompression = BI_BITFIELDS; bmi.bmiHeader.biSizeImage = sizeof(rgw555); bmi.bmiHeader.biClrImportant = 0; bmi.bmiHeader.biClrUsed = 0; bmi.bmiHeader.biXPelsPerMeter = 0; bmi.bmiHeader.biYPelsPerMeter = 0; bmi.rgMasks[0] = 0x7C00; // 5 red bmi.rgMasks[1] = 0x03E0; // 5 green bmi.rgMasks[2] = 0x001F; // 5 blue if (SetDIBits(NULL, hbmTable, 0, 1, rgw555, (BITMAPINFO*)&bmi, DIB_RGB_COLORS)) { CopyMemory(table, pv8bpp, 32768); } DeleteObject(hbmTable); } } } Nearly all of this function is just preparation for the actual work that happens at the very end. First, we get the colors in the palette and have the annoying job of converting them from PALETTEENTRY structures (which is what GetPaletteEntries gives you) to RGBQUAD entries (which is what CreateDIBSection wants). Why the two can't use the same format I will never know. Next, we create our destination bitmap, an 8bpp bitmap with the palette entries as the color table, one pixel tall and 32768 pixels wide. Since this is a DIB section, GDI gives us a pointer (pv8bpp) to the actual bits in memory. Since we specified a 1 × 32768 bitmap, the format of the pixel data is just a sequence of 32768 bytes, each one corresponding to a palette index. Wow, that's exactly the format we want for our final table! Building the source "bitmap" involves a few tricks. The naive approach is to have a 32768-element array of RGBQUADs, each one describing one of the pixels in our dense sample set. Filling that array would have gone something like this: for (r = 0; r < 31; r++) for (g = 0; g < 31; g++) for (b = 0; b < 31; b++) { rgrgb[(r