\nWhen doing dithering, one operation you have to do for every\npixel is map it (more accurately, map a modified version of it)\nto the nearest color in your available palette.\nSince this is part of the dithering inner loop, you need this operation\nto be as fast as possible.¹\nA common technique for this is to precompute the nearest palette index\nfor a dense sampling of colors.\nAny time you need to convert a pixel,\nyou can find a nearby entry in the sampling\nand look up the precomputed nearest palette index.\nThis won’t give you the absolute best match for colors\nthat are very close to the halfway point between two palette colors,\nbut error diffusion dithering is an approximation anyway;\nif you choose your dense sampling to be “dense enough”, these errors\nare small and are accounted for in the error diffusion algorithm.\n<\/p>\n
\nBut how do you build up this table mapping each color in your\ndense sampling to the palette?\nOne way is to call\n \nBut there is a way to do that,\nand that’s the idea kernel for today.\nAfter all, GDI does it when you do a 24-bit to 8-bit blit.\nYou can harness this energy with the aid of DIB sections:\nCreate a source bitmap that consists of all the color values\nin your dense sample and a destination bitmap that is an 8bpp DIB\nsection with your palette as its color table.\nBlit the source onto the destination, and the result is a\ndestination that is exactly the mapping table you need!\n<\/p>\n \nLet’s code this up.\nFor the sake of illustration, our dense sampling will consist of\n32768 data points distributed throughout the 555 color space.\nIn that way, we can take an RGB value and map it to our 8-bit\npalette by means of the following expression:\n<\/p>\n \nSince bitmaps are two-dimensional, we can’t generate a\nthree-dimensional table like the one given above.\nLet’s view it not as a\n32 × 32 × 32\narray but rather as a one-dimensional array with 32768 elements.\n(This is, after all, how it’s represented in memory anyway, so\nit’s not like we’re really changing anything physically.)\nWith that minor change of point of view,\nwe’re ready to generate the desired table:\n<\/p>\n \nNearly all of this function is just preparation for the actual work\nthat happens at the very end.\n<\/p>\n \nFirst, we get the colors in the palette and have the annoying job\nof converting them from \nNext, we create our destination bitmap,\nan 8bpp bitmap with the palette entries\nas the color table, one pixel tall and 32768 pixels wide.\nSince this is a DIB section, GDI gives us a pointer\n( \nBuilding the source “bitmap” involves a few tricks.\nThe naive approach is to have a 32768-element array of \nThe first trick is to realize that we’re just manually converting\nour 555 pixel data into RGB, something GDI is perfectly capable\nof doing on its own.\nWhy not save ourselves some effort and just give GDI the 555 bitmap\nand let it do the conversion from 555 to RGB itself.\n(Besides, it might not even need to do that conversion;\nwho knows, maybe there’s a 555-to-8bpp optimized blit code path\ninside GDI we can take advantage of.)\nUsing a 555 bitmap gives us this loop instead:\n<\/p>\n \nThe second trick is strength-reducing this triple loop to simply\n<\/p>\n \nNow that we have the bitmap data and the \nAnd wow, that’s exactly the format we want in our \nIf you think about it in just the right way, this all becomes obvious.\nYou just have to realize that\n \nFootnote 1:\nYou might consider taking the technique in this article\nin another direction and simply blitting the entire 24bpp bitmap\nto a palettized DIB, thereby avoiding the intermediate translation\ntable.\nThe problem with this technique is that parenthetical “more\naccurately, map a modified version of it”.\nThe colors that need to be mapped to the palette are typically\nnot the ones in the source bitmap but instead have been modified\nin some way by the dithering algorithm.\nIn the case of an error-diffusion dither,\nthe color values being mapped aren’t even known until the preceding\npixels have already been dithered.\nAs a result, you can’t blit all the pixels at once since you don’t\neven know what color values you need to map until you have the result of\nprevious mappings.\n<\/p>\n \n[Updated 9:30am to fix 6’s, 3’s, 5’s and 10’s. -Raymond]<\/p>\n","protected":false},"excerpt":{"rendered":" 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 […]<\/p>\n","protected":false},"author":1069,"featured_media":111744,"comment_status":"open","ping_status":"closed","sticky":false,"template":"","format":"standard","meta":{"_acf_changed":false,"footnotes":""},"categories":[1],"tags":[25],"class_list":["post-28983","post","type-post","status-publish","format-standard","has-post-thumbnail","hentry","category-oldnewthing","tag-code"],"acf":[],"blog_post_summary":" 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 […]<\/p>\n","_links":{"self":[{"href":"https:\/\/devblogs.microsoft.com\/oldnewthing\/wp-json\/wp\/v2\/posts\/28983","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/devblogs.microsoft.com\/oldnewthing\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/devblogs.microsoft.com\/oldnewthing\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/devblogs.microsoft.com\/oldnewthing\/wp-json\/wp\/v2\/users\/1069"}],"replies":[{"embeddable":true,"href":"https:\/\/devblogs.microsoft.com\/oldnewthing\/wp-json\/wp\/v2\/comments?post=28983"}],"version-history":[{"count":0,"href":"https:\/\/devblogs.microsoft.com\/oldnewthing\/wp-json\/wp\/v2\/posts\/28983\/revisions"}],"wp:featuredmedia":[{"embeddable":true,"href":"https:\/\/devblogs.microsoft.com\/oldnewthing\/wp-json\/wp\/v2\/media\/111744"}],"wp:attachment":[{"href":"https:\/\/devblogs.microsoft.com\/oldnewthing\/wp-json\/wp\/v2\/media?parent=28983"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/devblogs.microsoft.com\/oldnewthing\/wp-json\/wp\/v2\/categories?post=28983"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/devblogs.microsoft.com\/oldnewthing\/wp-json\/wp\/v2\/tags?post=28983"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}GetNearestPaletteIndex<\/code>\nfor every pixel in the dense sampling.\nBut the dense sampling by its nature has a large number of entries,\nand each call to GetNearestPaletteIndex<\/code> is a ring transition.\nIf only there were a way to do a bulk call to\nGetNearestPaletteIndex<\/code> where you pass a whole bunch of\nCOLORREF<\/code>s at once.\n<\/p>\n\nextern BYTE table[32][32][32];\nindex = table[red >> 3][green >> 3][blue >> 3];\n<\/pre>\n
\nvoid CreateMappingTable(HPALETTE hpal)\n{\n struct {\n BITMAPINFOHEADER bmiHeader;\n union {\n RGBQUAD bmiColors[256]; \/\/ when in palette mode\n DWORD rgMasks[3]; \/\/ when in BI_BITFIELDS mode\n };\n } bmi;\n PALETTEENTRY rgpe[256];\n UINT cColors = GetPaletteEntries(hpal, 0, 256, rgpe);\n if (cColors) {\n for (UINT i = 0; i < cColors; i++) {\n bmi.bmiColors[i].rgbRed = rgpe[i].peRed;\n bmi.bmiColors[i].rgbBlue = rgpe[i].peBlue;\n bmi.bmiColors[i].rgbGreen = rgpe[i].peGreen;\n bmi.bmiColors[i].rgbReserved = 0;\n }\n bmi.bmiHeader.biSize = sizeof(bmi.bmiHeader);\n bmi.bmiHeader.biWidth = 32768;\n bmi.bmiHeader.biHeight = 1;\n bmi.bmiHeader.biPlanes = 1;\n bmi.bmiHeader.biBitCount = 8;\n bmi.bmiHeader.biCompression = BI_RGB;\n bmi.bmiHeader.biSizeImage = 32768;\n bmi.bmiHeader.biClrImportant = cColors;\n bmi.bmiHeader.biClrUsed = 0;\n bmi.bmiHeader.biXPelsPerMeter = 0;\n bmi.bmiHeader.biYPelsPerMeter = 0;\n void *pv8bpp;\n HBITMAP hbmTable = CreateDIBSection(NULL, (BITMAPINFO*)&bmi,\n DIB_RGB_COLORS, &pv8bpp, NULL, 0);\n if (hbmTable) {\n WORD rgw555[32768];\n for (int i = 0; i < 32768; i++) {\n rgw555[i] = (WORD)i;\n }\n bmi.bmiHeader.biSize = sizeof(bmi.bmiHeader);\n bmi.bmiHeader.biWidth = 32768;\n bmi.bmiHeader.biHeight = 1;\n bmi.bmiHeader.biPlanes = 1;\n bmi.bmiHeader.biBitCount = 16;\n bmi.bmiHeader.biCompression = BI_BITFIELDS;\n bmi.bmiHeader.biSizeImage = sizeof(rgw555);\n bmi.bmiHeader.biClrImportant = 0;\n bmi.bmiHeader.biClrUsed = 0;\n bmi.bmiHeader.biXPelsPerMeter = 0;\n bmi.bmiHeader.biYPelsPerMeter = 0;\n bmi.rgMasks[0] = 0x7C00; \/\/ 5 red\n bmi.rgMasks[1] = 0x03E0; \/\/ 5 green\n bmi.rgMasks[2] = 0x001F; \/\/ 5 blue\n if (SetDIBits(NULL, hbmTable, 0, 1, rgw555,\n (BITMAPINFO*)&bmi, DIB_RGB_COLORS)) {\n CopyMemory(table, pv8bpp, 32768);\n }\n DeleteObject(hbmTable);\n }\n }\n}\n<\/pre>\nPALETTEENTRY<\/code> structures\n(which is what GetPaletteEntries<\/code> gives you)\nto RGBQUAD<\/code> entries (which is what\nCreateDIBSection<\/code> wants).\nWhy the two can’t use the same format I will never know.\n<\/p>\npv8bpp<\/code>) to the actual bits in memory.\nSince we specified a 1 × 32768 bitmap,\nthe format of the pixel data is just a sequence of 32768\nbytes, each one corresponding to a palette index.\nWow, that’s exactly the format we want for our final table!\n<\/p>\nRGBQUAD<\/code>s,\neach one describing one of the pixels in our dense sample set.\nFilling that array would have gone something like this:\n<\/p>\n\nfor (r = 0; r < 31; r++)\n for (g = 0; g < 31; g++)\n for (b = 0; b < 31; b++) {\n rgrgb[(r << 10) | (g << 5) | b].rgbRed = r << 3;\n rgrgb[(r << 10) | (g << 5) | b].rgbGreen = g << 3;\n rgrgb[(r << 10) | (g << 5) | b].rgbBlue = b << 3;\n rgrgb[(r << 10) | (g << 5) | b].rgbReserved = 0;\n }\n<\/pre>\n\nfor (r = 0; r < 31; r++)\n for (g = 0; g < 31; g++)\n for (b = 0; b < 31; b++)\n rgw555[(r << 10) | (g << 5) | b] = (r << 10) | (g << 5) | b;\n<\/pre>\n
\nfor (i = 0; i < 32768; i++) {\n rgw555[i] = i;\n}\n<\/pre>\nBITMAPINFO<\/code>\nthat describes it, we can use SetDIBits<\/code> to make GDI\ndo all the work.\nThe function takes our “bitmap”\n(one row of 32768 pixels, each in a different color and\ncollectively exhausting our dense sample set)\nand sets it into our DIB section.\nBy the magic of BitBlt<\/code>,\neach pixel is mapped to the nearest matching color in the\ndestination palette, and its index is stored as the pixel value.\n<\/p>\ntable<\/code>!\nA little CopyMemory<\/code> action and we’re home free.\n<\/p>\nBitBlt<\/code>\n(or here one of its moral equivalents, SetDIBits<\/code>)\ndoes more than just copy bits; it maps colors too.\nAnd then realize that you can extract the results of that mapping\nvia a DIB section.\nSince you’re handing in an entire bitmap instead of just a single\ncolor, you can map all 32768 colors at once.\n<\/p>\n