home *** CD-ROM | disk | FTP | other *** search
/ Windows Graphics Programming / Feng_Yuan_Win32_GDI_DirectX.iso / Samples / include / Octree.h < prev    next >
Encoding:
C/C++ Source or Header  |  2000-05-11  |  4.6 KB  |  220 lines
  1. #pragma once
  2.  
  3. //-----------------------------------------------------------------------------------//
  4. //              Windows Graphics Programming: Win32 GDI and DirectDraw               //
  5. //                             ISBN  0-13-086985-6                                   //
  6. //                                                                                   //
  7. //  Written            by  Yuan, Feng                             www.fengyuan.com   //
  8. //  Copyright (c) 2000 by  Hewlett-Packard Company                www.hp.com         //
  9. //  Published          by  Prentice Hall PTR, Prentice-Hall, Inc. www.phptr.com      //
  10. //                                                                                   //
  11. //  FileName   : octree.h                                                             //
  12. //  Description: Octree color quantilization, color reduction                        //
  13. //  Version    : 1.00.000, May 31, 2000                                              //
  14. //-----------------------------------------------------------------------------------//
  15.  
  16. class KNode
  17. {
  18. public:
  19.     bool        IsLeaf;
  20.     unsigned    Pixels;
  21.     
  22.     unsigned    SigmaRed;
  23.     unsigned    SigmaGreen;
  24.     unsigned    SigmaBlue;
  25.     KNode *        Child[8];
  26.  
  27.     KNode(bool leaf)
  28.     {
  29.         IsLeaf     = leaf;
  30.         Pixels     = 0;
  31.         SigmaRed   = 0;
  32.         SigmaGreen = 0;
  33.         SigmaBlue  = 0;
  34.         memset(Child, 0, sizeof(Child));
  35.     }
  36.  
  37.     RemoveAll(void);
  38.  
  39.     int PickLeaves(RGBQUAD * pEntry, int * pFreq, int size);
  40. };
  41.  
  42.  
  43. class KOctree
  44. {
  45.     typedef enum { MAXMODE = 65536 };
  46.  
  47.     KNode   * pRoot;
  48.     int        TotalNode;
  49.     int        TotalLeaf;
  50.  
  51.     void Reduce(KNode * pTree, unsigned threshold);
  52.     
  53.  
  54. public:
  55.  
  56.     KOctree()
  57.     {
  58.         pRoot     = new KNode(false);
  59.         TotalNode = 1;
  60.         TotalLeaf = 0;
  61.     }
  62.  
  63.     ~KOctree()
  64.     {
  65.         if ( pRoot )
  66.         {
  67.             pRoot->RemoveAll();
  68.             pRoot = NULL;
  69.         }
  70.     }
  71.  
  72.     void AddColor (BYTE r, BYTE g, BYTE b);
  73.     void ReduceLeaves(int limit);
  74.     int  GenPalette(RGBQUAD *entry, int * Freq, int size);
  75.  
  76.     void Merge(KNode * pNode, KNode & target);
  77. };
  78.  
  79.  
  80. class KPaletteGen : public KPixelMapper
  81. {
  82.     KOctree octree;
  83.  
  84.     // return true if data changed
  85.     virtual bool MapRGB(BYTE & red, BYTE & green, BYTE & blue)
  86.     {
  87.         octree.AddColor(red, green, blue);
  88.  
  89.         return false;
  90.     }
  91.  
  92. public:
  93.  
  94.     void AddBitmap(KImage & dib)
  95.     {
  96.         dib.PixelTransform(* this);
  97.     }
  98.  
  99.     int GetPalette(RGBQUAD * pEntry, int * pFreq, int size)
  100.     {
  101.         return octree.GenPalette(pEntry, pFreq, size);
  102.     }
  103. };
  104.  
  105.  
  106. class KColorMatch
  107. {
  108. public:
  109.     
  110.     RGBQUAD   * m_Colors;
  111.     int            m_nEntries;
  112.  
  113.     int square(int i)
  114.     {
  115.         return i * i;
  116.     }
  117.  
  118. public:
  119.  
  120.     BYTE ColorMatch(int red, int green, int blue)
  121.     {
  122.         int  dis  = 0x7FFFFFFF;
  123.         BYTE best = 0;
  124.  
  125.         if (   red<0 )   red=0; else if (   red>255 )   red=255;
  126.         if ( green<0 ) green=0; else if ( green>255 ) green=255;
  127.         if (  blue<0 )  blue=0; else if (  blue>255 )  blue=255;
  128.  
  129.         for (int i=0; i<m_nEntries; i++)
  130.         {
  131.             int d = square(red - m_Colors[i].rgbRed);
  132.             if ( d>dis ) continue;
  133.  
  134.             d += square(green - m_Colors[i].rgbGreen);
  135.             if ( d>dis ) continue;
  136.  
  137.             d += square(blue - m_Colors[i].rgbBlue);
  138.  
  139.             if ( d < dis )
  140.             {
  141.                 dis = d;
  142.                 best = i;
  143.             }
  144.         }
  145.  
  146.         return best;
  147.     }
  148.  
  149.     void Setup(int nEntry, RGBQUAD * pColor)
  150.     {
  151.         m_nEntries   = nEntry;
  152.         m_Colors     = pColor;
  153.     }
  154.  
  155. };
  156.  
  157.  
  158. class KColorReduction : public KPixelMapper
  159. {
  160. protected:
  161.     int             m_nBPS;
  162.     BYTE       * m_pBits;
  163.     BYTE       * m_pPixel;
  164.     KColorMatch  m_Matcher;
  165.  
  166.     // return true if data changed
  167.     virtual bool MapRGB(BYTE & red, BYTE & green, BYTE & blue)
  168.     {
  169.         *m_pPixel ++ = m_Matcher.ColorMatch(red, green, blue);
  170.         return false;
  171.     }
  172.     
  173.     virtual bool StartLine(int line)
  174.     {
  175.         m_pPixel = m_pBits + line * m_nBPS; // first pixel of a scanline
  176.         return true;
  177.     }
  178.  
  179. public:
  180.  
  181.     BITMAPINFO * Convert8bpp(BITMAPINFO * pDIB);
  182. };
  183.  
  184.  
  185. class KErrorDiffusionColorReduction : public KColorReduction
  186. {
  187.     int             * red_error;
  188.     int             * green_error;
  189.     int             * blue_error;
  190.  
  191.     bool         m_bForward;
  192.  
  193.     virtual bool StartLine(int line)
  194.     {
  195.         m_pPixel = m_pBits + line * m_nBPS; // first pixel of a scanline
  196.  
  197.         m_bForward = (line & 1) == 0;
  198.  
  199.         return true;
  200.     }
  201.  
  202.     virtual void Map24bpp(BYTE * pBuffer, int width);
  203.  
  204. public:
  205.  
  206.     BITMAPINFO * Convert8bpp(BITMAPINFO * pDIB);
  207. };
  208.  
  209.  
  210. HPALETTE     CreateDIBPalette(const BITMAPINFO * pDIB);
  211. BITMAPINFO * IndexColorTable(BITMAPINFO * pDIB, HPALETTE hPal);
  212. HPALETTE     LUTCreatePalette(const BYTE * pRGB, int nSize, int nColor);
  213.  
  214. int             GenPalette(BITMAPINFO * pDIB, RGBQUAD * pEntry, int * pFreq, int size);
  215.  
  216. BITMAPINFO * Convert8bpp(BITMAPINFO * pDIB);
  217. BITMAPINFO * Convert8bpp_ErrorDiffusion(BITMAPINFO * pDIB);
  218.  
  219.  
  220.