【图形】八叉树算法取得图像最适应调色板

0xAA55

这次的算法是我的上一个帖子中的程序的完全重写版。之前的程序参考了微软的相关代码，那代码可读性不高，而且用起来麻烦。因此我重新写了这个代码。
八叉树算法用于产生最适合一副图像的256色调色板。这个算法使用一种八叉树的结构，通过建立八叉树，将颜色筛选出来，接近的颜色会被合并，而在图像中出现次数极少的颜色和出现次数很多的颜色都会被照顾到。
这次我写了个窗口，我用它来显示整个八叉树的产生过程。大家可以自己下载了然后修改使其能发展出一个完整的八叉树。因为我的代码是为了达到取得最适应调色板的目的（而不单纯只是为了建立八叉树），所以在树的产生过程中就有“砍树”的行为，一个是减少内存占用，一个是加速程序运行。
Bin在运行的时候，大家可以直接拖拽一个24位BMP文件到窗口内，然后它就会分析这个文件，取得它的像素，再产生八叉树、调色板。




颜色越多，最终产生的八叉树的深度就越小。
同时八叉树的展开程度决定了图像颜色的明暗度分布情况。
现在我写的这个库是这么用的：
1、包含我的.h
2、编译我的.c
#include"OctPal.h"
定义一个PalGenP类型的变量：PalGenP pGen;
初始化它。pGen=CreatePalGen(NULL);//其中的NULL可以换成你自己的错误处理程序。
然后不断调用AddColor(pGen,红色值,绿色值,蓝色值);将颜色添加到八叉树中。返回值是当前的八叉树所含颜色数。
可以通过检测pGen->NbLeaf判断颜色数量，然后调用ReduceColor(pGen);减少颜色的数量。ReduceColor的行为就是合并一些八叉树的树叶，将八叉树的级数一点点缩小，以筛选出应该被放入调色板的颜色。
最后调用GenPalette(pGen,接收颜色的回调函数,回调函数的参数);生成调色板。
详细的请看源码的内容。
OPConfig.h:

1. //=============================================================================
   
2. //作者：0xAA55
   
3. //网站：http://www.0xaa55.com
   
4. //请保留原作者信息，否则视为侵权。
   
5. //-----------------------------------------------------------------------------
   
6. #ifndef        _OCTREE_PALETTE_GENERATOR_CONFIG_
   
7. #define        _OCTREE_PALETTE_GENERATOR_CONFIG_
   
8. 
   
9. #ifndef        OPCall//调用约定
   
10. #define        OPCall                _cdecl
    
11. #endif
    
12. 
    
13. #ifndef        OPCallBack//回调函数调用约定
    
14. #define        OPCallBack        _cdecl
    
15. #endif
    
16. 
    
17. #ifndef        OPExpImp//导出导入的前缀
    
18. #define        OPExpImp
    
19. #endif
    
20. 
    
21. #ifndef        OPFunc//函数
    
22. #define        OPFunc(r,f)        OPExpImp r OPCall f
    
23. #endif
    
24. 
    
25. #endif

复制代码

OctPal.h:

1. //=============================================================================
   
2. //作者：0xAA55
   
3. //网站：http://www.0xaa55.com
   
4. //请保留原作者信息，否则视为侵权。
   
5. //-----------------------------------------------------------------------------
   
6. #ifndef        _OCTREE_PALETTE_GENERATOR_
   
7. #define        _OCTREE_PALETTE_GENERATOR_
   
8. 
   
9. #include"OPConfig.h"
   
10. #include<stddef.h>
    
11. 
    
12. #define        ColorBits 8
    
13. 
    
14. typedef enum
    
15. {
    
16.         OPErr_NoError,                        //没有出错
    
17.         OPErr_NoMemory,                        //内存不足
    
18.         OPErr_NoReducibleNodes        //没有可删减节点
    
19. }OPError,*OPErrorP;
    
20. 
    
21. typedef void(OPCallBack*FnOnError)(OPError);
    
22. 
    
23. typedef        unsigned char        ColorVal;//颜色值
    
24. typedef        unsigned int        ColorSum;//颜色统计值
    
25. typedef        struct _OctNode
    
26. {
    
27.         ColorSum        NbColors;
    
28.         ColorSum        RSum;
    
29.         ColorSum        GSum;
    
30.         ColorSum        BSum;
    
31.         int                        IsLeaf;
    
32.         struct _OctNode*pChild[8];//八叉树子节点(Index=红绿蓝三个颜色值各贡献一位)
    
33.         struct _OctNode*pNext;//下一个可删减节点
    
34. }OctreeNode,*OctreeNodeP;//八叉树节点
    
35. typedef        struct
    
36. {
    
37.         OctreeNodeP        pRoot;
    
38.         OctreeNodeP        pReducibleNodes[ColorBits];//可删减节点
    
39.         size_t                NbLeaf;
    
40.         ColorSum        NbColors;
    
41.         FnOnError        pfnOnError;
    
42. }PalGen,*PalGenP;
    
43. 
    
44. //=============================================================================
    
45. //函数：FnOnGetColor
    
46. //描述：取得调色板颜色的时候调用的用户回调函数
    
47. //-----------------------------------------------------------------------------
    
48. typedef void(OPCallBack*FnOnGetColor)
    
49. (
    
50.         ColorVal R,
    
51.         ColorVal G,
    
52.         ColorVal B,
    
53.         void*pUserData
    
54. );
    
55. 
    
56. //=============================================================================
    
57. //函数：CreatePalGen
    
58. //描述：分配内存，创建一个PalGen
    
59. //-----------------------------------------------------------------------------
    
60. OPFunc(PalGenP,CreatePalGen)(FnOnError);
    
61. 
    
62. //=============================================================================
    
63. //函数：DestroyPalGen
    
64. //描述：释放内存，彻底删除PalGen
    
65. //-----------------------------------------------------------------------------
    
66. OPFunc(void,DestroyPalGen)(PalGenP);
    
67. 
    
68. //=============================================================================
    
69. //函数：AddColor
    
70. //描述：将一个颜色添加到PalGen的八叉树里。返回当前颜色数
    
71. //-----------------------------------------------------------------------------
    
72. OPFunc(size_t,AddColor)
    
73. (
    
74.         PalGenP                pGen,
    
75.         ColorVal        R,
    
76.         ColorVal        G,
    
77.         ColorVal        B
    
78. );
    
79. 
    
80. //=============================================================================
    
81. //函数：ReduceColor
    
82. //描述：删减PalGen的八叉树颜色，返回剩余颜色数。
    
83. //-----------------------------------------------------------------------------
    
84. OPFunc(size_t,ReduceColor)(PalGenP pGen);
    
85. 
    
86. //=============================================================================
    
87. //函数：GenPalette
    
88. //描述：从PalGen中取得调色板
    
89. //-----------------------------------------------------------------------------
    
90. OPFunc(void,GenPalette)
    
91. (
    
92.         PalGenP                        pGen,
    
93.         FnOnGetColor        pfnOnGetColor,
    
94.         void                        *pUserData
    
95. );
    
96. 
    
97. #endif

复制代码

OctPal.c:

1. //=============================================================================
   
2. //作者：0xAA55
   
3. //网站：http://www.0xaa55.com
   
4. //请保留原作者信息，否则视为侵权。
   
5. //-----------------------------------------------------------------------------
   
6. #include"OctPal.h"
   
7. #include<stdio.h>
   
8. #include<malloc.h>
   
9. #include<memory.h>
   
10. 
    
11. //=============================================================================
    
12. //函数：DefOnError
    
13. //描述：默认的错误处理函数
    
14. //-----------------------------------------------------------------------------
    
15. static void OPCallBack DefOnError(OPError ErrNumber)
    
16. {
    
17.         //什么也不做
    
18. }
    
19. 
    
20. //=============================================================================
    
21. //函数：CreateNode
    
22. //描述：建立节点，函数会根据级数来判断它是否为叶子节点，如果不是，则“可删减”
    
23. //-----------------------------------------------------------------------------
    
24. static OctreeNodeP CreateNode
    
25. (
    
26.         size_t                Level,
    
27.         PalGenP                pGen
    
28. )
    
29. {
    
30.         OctreeNodeP pNode;
    
31.         pNode=(OctreeNodeP)malloc(sizeof(OctreeNode));
    
32.         if(!pNode)//错误汇报机制由调用者完成。
    
33.                 return NULL;
    
34. 
    
35.         memset(pNode,0,sizeof(OctreeNode));
    
36.         if(Level==ColorBits)
    
37.         {
    
38.                 //判断是否最深一级
    
39.                 pNode->IsLeaf=1;
    
40.                 pGen->NbLeaf++;
    
41.         }
    
42.         else
    
43.         {
    
44.                 //横向连结所有的节点
    
45.                 pNode->pNext=pGen->pReducibleNodes[Level];
    
46.                 pGen->pReducibleNodes[Level]=pNode;
    
47.         }
    
48.         return pNode;
    
49. }
    
50. 
    
51. //=============================================================================
    
52. //函数：GetTreePal
    
53. //描述：遍历八叉树，从中取得颜色，建立调色板。
    
54. //-----------------------------------------------------------------------------
    
55. static void GetTreePal
    
56. (
    
57.         OctreeNodeP                pNode,
    
58.         FnOnGetColor        pfnOnGetColor,
    
59.         void*                        pUserData
    
60. )
    
61. {
    
62.         if(pNode->IsLeaf)
    
63.                 pfnOnGetColor(
    
64.                         (ColorVal)(pNode->RSum/pNode->NbColors),
    
65.                         (ColorVal)(pNode->GSum/pNode->NbColors),
    
66.                         (ColorVal)(pNode->BSum/pNode->NbColors),
    
67.                         pUserData);
    
68.         else
    
69.         {
    
70.                 unsigned i;
    
71.                 for(i=0;i<8;i++)
    
72.                 {
    
73.                         if(pNode->pChild[i])
    
74.                                 GetTreePal(pNode->pChild[i],pfnOnGetColor,pUserData);
    
75.                 }
    
76.         }
    
77. }
    
78. 
    
79. //=============================================================================
    
80. //函数：DestroyTree
    
81. //描述：遍历八叉树，从最深级开始删除整个八叉树。
    
82. //-----------------------------------------------------------------------------
    
83. static void DestroyTree(OctreeNodeP pTree)
    
84. {
    
85.         unsigned i;
    
86.         for(i=0;i<8;i++)
    
87.         {
    
88.                 if(pTree->pChild[i])
    
89.                         DestroyTree(pTree->pChild[i]);
    
90.         }
    
91.         free(pTree);
    
92. }
    
93. 
    
94. //=============================================================================
    
95. //函数：CreatePalGen
    
96. //描述：分配内存，创建一个PalGen
    
97. //-----------------------------------------------------------------------------
    
98. OPFunc(PalGenP,CreatePalGen)(FnOnError pfnOnError)
    
99. {
    
100.         PalGenP pGen;
     
101.        
     
102.         pGen=(PalGenP)malloc(sizeof(PalGen));
     
103.         if(!pGen)
     
104.                 return NULL;
     
105.         memset(pGen,0,sizeof(PalGen));
     
106.        
     
107.         if(pfnOnError)
     
108.                 pGen->pfnOnError=pfnOnError;
     
109.         else
     
110.                 pGen->pfnOnError=DefOnError;
     
111. 
     
112.         //建立树根节点
     
113.         pGen->pRoot=CreateNode(0,pGen);
     
114.         if(!pGen->pRoot)
     
115.         {
     
116.                 free(pGen);
     
117.                 if(pfnOnError)
     
118.                         pfnOnError(OPErr_NoMemory);//汇报错误
     
119.                 return NULL;
     
120.         }
     
121. 
     
122.         return pGen;
     
123. }
     
124. 
     
125. //=============================================================================
     
126. //函数：AddColor
     
127. //描述：将一个颜色添加到PalGen的八叉树里。返回当前颜色数。
     
128. //-----------------------------------------------------------------------------
     
129. OPFunc(size_t,AddColor)
     
130. (
     
131.         PalGenP                pGen,
     
132.         ColorVal        R,
     
133.         ColorVal        G,
     
134.         ColorVal        B
     
135. )
     
136. {
     
137.         unsigned i,Index,Shift;
     
138.         OctreeNodeP pNode;
     
139.         OPError ErrNumber=OPErr_NoError;
     
140. 
     
141.         //树根节点必须存在，否则pGen无法初始化成功。见CreatePalGen函数实现。
     
142.         pNode=pGen->pRoot;
     
143. 
     
144.         //往下扩展树枝
     
145.         for(i=1;i<=ColorBits;i++)
     
146.         {
     
147.                 if(pNode->IsLeaf)//如果已经是树叶则不再扩展树枝。
     
148.                         break;
     
149.                 Shift=ColorBits-i;
     
150.                 Index=        ((R>>Shift)&1)<<0|
     
151.                                 ((G>>Shift)&1)<<1|
     
152.                                 ((B>>Shift)&1)<<2;
     
153.                 if(!(pNode->pChild[Index]))
     
154.                 {
     
155.                         pNode->pChild[Index]=CreateNode(i,pGen);
     
156.                         if(!(pNode->pChild[Index]))
     
157.                         {
     
158.                                 ErrNumber=OPErr_NoMemory;
     
159.                                 goto ErrorReturn;
     
160.                         }
     
161.                 }
     
162.                 pNode=pNode->pChild[Index];
     
163.         }
     
164. 
     
165.         //树叶统计颜色
     
166.         pNode->RSum+=(ColorSum)R;
     
167.         pNode->GSum+=(ColorSum)G;
     
168.         pNode->BSum+=(ColorSum)B;
     
169.         pNode->NbColors++;
     
170.         pGen->NbColors++;
     
171. 
     
172.         return 1;
     
173. ErrorReturn:
     
174.         pGen->pfnOnError(ErrNumber);
     
175.         return 0;
     
176. }
     
177. 
     
178. //=============================================================================
     
179. //函数：ReduceColor
     
180. //描述：删减PalGen的八叉树颜色，返回剩余颜色数。
     
181. //-----------------------------------------------------------------------------
     
182. OPFunc(size_t,ReduceColor)(PalGenP pGen)
     
183. {
     
184.         unsigned i;
     
185.         OctreeNodeP pNode;
     
186.         OPError ErrNumber=OPErr_NoError;
     
187. 
     
188.         //找到最深一级的可删减节点。
     
189.         for(i=ColorBits-1;i;i--)
     
190.         {
     
191.                 if(pGen->pReducibleNodes[i])
     
192.                         break;
     
193.         }
     
194.         if(!pGen->pReducibleNodes[i])
     
195.         {
     
196.                 ErrNumber=OPErr_NoReducibleNodes;
     
197.                 goto ErrorReturn;
     
198.         }
     
199. 
     
200.         //横向指定同级下一个可删减节点
     
201.         pNode=pGen->pReducibleNodes[i];
     
202.         pGen->pReducibleNodes[i]=pNode->pNext;
     
203. 
     
204.         //删减节点
     
205.         for(i=0;i<8;i++)
     
206.         {
     
207.                 if(pNode->pChild[i])
     
208.                 {
     
209.                         pNode->RSum+=pNode->pChild[i]->RSum;
     
210.                         pNode->GSum+=pNode->pChild[i]->GSum;
     
211.                         pNode->BSum+=pNode->pChild[i]->BSum;
     
212.                         pNode->NbColors+=pNode->pChild[i]->NbColors;
     
213.                         free(pNode->pChild[i]);
     
214.                         pNode->pChild[i]=NULL;
     
215.                         pGen->NbLeaf--;
     
216.                 }
     
217.         }
     
218.         pNode->IsLeaf=1;
     
219.         pGen->NbLeaf++;
     
220. 
     
221.         return pGen->NbLeaf;
     
222. ErrorReturn:
     
223.         pGen->pfnOnError(ErrNumber);
     
224.         return pGen->NbLeaf;
     
225. }
     
226. 
     
227. //=============================================================================
     
228. //函数：GenPalette
     
229. //描述：从PalGen中取得调色板
     
230. //-----------------------------------------------------------------------------
     
231. OPFunc(void,GenPalette)
     
232. (
     
233.         PalGenP                        pGen,
     
234.         FnOnGetColor        pfnOnGetColor,
     
235.         void                        *pUserData
     
236. )
     
237. {
     
238.         if(pGen->pRoot)
     
239.                 GetTreePal(pGen->pRoot,pfnOnGetColor,pUserData);
     
240. }
     
241. 
     
242. 
     
243. //=============================================================================
     
244. //函数：DestroyPalGen
     
245. //描述：释放内存，彻底删除PalGen
     
246. //-----------------------------------------------------------------------------
     
247. OPFunc(void,DestroyPalGen)(PalGenP pGen)
     
248. {
     
249.         if(pGen->pRoot)
     
250.                 DestroyTree(pGen->pRoot);
     
251.         free(pGen);
     
252. }

复制代码

Entry.c:

1. //=============================================================================
   
2. //作者：0xAA55
   
3. //网站：http://www.0xaa55.com
   
4. //请保留原作者信息，否则视为侵权。
   
5. //-----------------------------------------------------------------------------
   
6. #define        _USE_MATH_DEFINES
   
7. #include<math.h>
   
8. 
   
9. #include<tchar.h>
   
10. #include<stdio.h>
    
11. #include<stdarg.h>
    
12. #include<Windows.h>
    
13. 
    
14. #include"OctPal.h"
    
15. HWND        g_hWnd=NULL;                        //主窗口
    
16. HDC                g_hBackgroundDC=NULL;        //后台绘图句柄
    
17. HBITMAP        g_hBackgroundBMP=NULL;        //后台绘图的位图
    
18. PalGenP        g_pGen=NULL;                        //调色板生成器的存储数据
    
19. 
    
20. //=============================================================================
    
21. //函数：DbgPrint
    
22. //描述：打印调试信息。
    
23. //-----------------------------------------------------------------------------
    
24. void DbgPrint(char*szFmt,...)
    
25. {
    
26.         va_list ap;
    
27.         char szBuf[0x1000];
    
28. 
    
29.         va_start(ap,szFmt);
    
30. 
    
31.         vsprintf(szBuf,szFmt,ap);
    
32.         MessageBoxA(g_hWnd,szBuf,"DbgPrint",MB_ICONINFORMATION);
    
33. 
    
34.         va_end(ap);
    
35. }
    
36. 
    
37. //=============================================================================
    
38. //函数：DoEvents
    
39. //描述：处理窗口消息
    
40. //-----------------------------------------------------------------------------
    
41. int DoEvents()
    
42. {
    
43.         MSG msg;
    
44.         if(PeekMessage(&msg,g_hWnd,0,0,PM_REMOVE))
    
45.         {
    
46.                 if(msg.message==WM_QUIT)//遇到WM_QUIT消息返回0
    
47.                         return 0;
    
48.                 TranslateMessage(&msg);
    
49.                 DispatchMessage(&msg);
    
50.         }
    
51.         return 1;
    
52. }
    
53. 
    
54. //=============================================================================
    
55. //函数：OnGetColor
    
56. //描述：取得颜色的回调函数，用于生成调色板。
    
57. //-----------------------------------------------------------------------------
    
58. RGBQUAD g_Palette[256];
    
59. void OPCallBack OnGetColor
    
60. (
    
61.         ColorVal R,
    
62.         ColorVal G,
    
63.         ColorVal B,
    
64.         void*pUserData
    
65. )
    
66. {
    
67.         size_t Index=*(size_t*)pUserData;
    
68.         if(Index>=256)
    
69.                 return;
    
70.         g_Palette[Index].rgbRed=R;
    
71.         g_Palette[Index].rgbGreen=G;
    
72.         g_Palette[Index].rgbBlue=B;
    
73.         (*(size_t*)pUserData)++;
    
74. }
    
75. 
    
76. //=============================================================================
    
77. //函数：DrawTree
    
78. //描述：绘制产生的八叉树。八叉树足够大的时候绘图会变得很慢。
    
79. //-----------------------------------------------------------------------------
    
80. void DrawTree
    
81. (
    
82.         HDC hDC,
    
83.         OctreeNodeP pNode,
    
84.         float fAngle,
    
85.         float fX,
    
86.         float fY,
    
87.         float fLength,
    
88.         float fRadius,
    
89.         float fMaxSubAngle,
    
90.         int LeafMatch
    
91. )
    
92. {
    
93.         unsigned i;
    
94.        
    
95.         if(pNode->IsLeaf && LeafMatch)//如果是树叶而且只画树叶
    
96.         {
    
97.                 BYTE R,G,B;
    
98.                 HBRUSH hClrFill;
    
99.                 LOGBRUSH ClrFill;
    
100.                 R=(BYTE)(pNode->RSum/pNode->NbColors);
     
101.                 G=(BYTE)(pNode->GSum/pNode->NbColors);
     
102.                 B=(BYTE)(pNode->BSum/pNode->NbColors);
     
103.                 ClrFill.lbStyle=BS_SOLID;
     
104.                 ClrFill.lbColor=RGB(R,G,B);
     
105.                 hClrFill=CreateBrushIndirect(&ClrFill);
     
106.                 hClrFill=(HBRUSH)SelectObject(hDC,hClrFill);
     
107.                 Ellipse(hDC,
     
108.                         (int)(fX-fRadius),(int)(fY-fRadius),
     
109.                         (int)(fX+fRadius),(int)(fY+fRadius));
     
110.                 hClrFill=(HBRUSH)SelectObject(hDC,hClrFill);
     
111.                 DeleteObject(hClrFill);
     
112.         }
     
113.         else if(!pNode->IsLeaf)//如果不是树叶则处理下一级
     
114.         {
     
115.                 for(i=0;i<8;i++)
     
116.                 {
     
117.                         if(pNode->pChild[i])
     
118.                         {
     
119.                                 //计算下一个节点的位置
     
120.                                 float fSubAng=fAngle+((float)i-3.5f)*fMaxSubAngle/7.0f;
     
121.                                 float fSubX=fX+cosf(fAngle+fSubAng)*fLength;
     
122.                                 float fSubY=fY+sinf(fAngle+fSubAng)*fLength;
     
123.                                 if(!LeafMatch)//如果画树枝，则进行绘图操作。
     
124.                                 {
     
125.                                         MoveToEx(hDC,(int)fX,(int)fY,NULL);
     
126.                                         LineTo(hDC,
     
127.                                                 (int)fSubX,
     
128.                                                 (int)fSubY);
     
129.                                 }
     
130.                                 DrawTree(hDC,pNode->pChild[i],fSubAng,//递归下一个节点
     
131.                                         fSubX,fSubY,fLength,fRadius,fMaxSubAngle,LeafMatch);
     
132.                         }
     
133.                 }
     
134.         }
     
135. }
     
136. 
     
137. //=============================================================================
     
138. //函数：ParseBMPFile
     
139. //描述：分析BMP文件，产生八叉树，然后产生调色板
     
140. //-----------------------------------------------------------------------------
     
141. void ParseBMPFile(LPCTSTR szBMPFile)
     
142. {
     
143.         BITMAPFILEHEADER BMFH;//BMP文件头
     
144.         BITMAPINFOHEADER BMIF;//BMP信息头
     
145. 
     
146.         size_t Pitch;//每行字节数
     
147.         RGBTRIPLE*LineData=NULL;//行像素数据
     
148.         size_t x,y,Index;//用于遍历的变量
     
149. 
     
150.         RECT rc;//窗口客户区域的左、上、右、下
     
151.         DWORD dwLastTick=0;//用于粗略计时
     
152. 
     
153.         FILE*fp=NULL;
     
154.         //打开文件进行读取
     
155.         fp=_tfopen(szBMPFile,TEXT("rb"));
     
156.         if(!fp)
     
157.                 goto ReadFail;
     
158.        
     
159.         //读取文件头
     
160.         if(fread(&BMFH,1,sizeof(BMFH),fp)!=sizeof(BMFH))goto ReadFail;
     
161.         if(fread(&BMIF,1,sizeof(BMIF),fp)!=sizeof(BMIF))goto ReadFail;
     
162. 
     
163.         //判断文件格式
     
164.         if(BMFH.bfType!='MB')
     
165.                 goto BadFormat;
     
166.         if(BMIF.biBitCount!=24)
     
167.                 goto Not24Bit;
     
168. 
     
169.         fseek(fp,BMFH.bfOffBits,SEEK_SET);
     
170. 
     
171.         //清空调色板
     
172.         memset(g_Palette,0,sizeof(g_Palette));
     
173. 
     
174.         //重置调色板生成器数据
     
175.         if(g_pGen)
     
176.                 DestroyPalGen(g_pGen);
     
177.         g_pGen=CreatePalGen(NULL);
     
178.         if(!g_pGen)
     
179.                 goto NoMem;
     
180.        
     
181.         //分配一行像素的内存用于读取
     
182.         Pitch=((BMIF.biWidth*BMIF.biBitCount-1)/32+1)*4;//4字节对齐
     
183.         LineData=(RGBTRIPLE*)malloc(Pitch);
     
184.         if(!LineData)
     
185.                 goto NoMem;
     
186. 
     
187.         //重绘窗口
     
188.         GetClientRect(g_hWnd,&rc);
     
189.         InvalidateRect(g_hWnd,&rc,TRUE);
     
190. 
     
191.         //遍历每一行
     
192.         y=BMIF.biHeight;
     
193.         do
     
194.         {
     
195.                 RGBTRIPLE*pPixel;//像素指针
     
196.                 fread(LineData,1,Pitch,fp);//读取一行像素
     
197.                 pPixel=LineData;//准备遍历这行的每一个像素
     
198. 
     
199.                 x=BMIF.biWidth;//遍历每一个像素
     
200.                 do
     
201.                 {
     
202.                         //添加像素颜色到八叉树
     
203.                         AddColor(g_pGen,pPixel->rgbtRed,
     
204.                                                         pPixel->rgbtGreen,
     
205.                                                         pPixel->rgbtBlue);
     
206.                         while(g_pGen->NbLeaf>256)//使眼色数量不超过256色
     
207.                                 ReduceColor(g_pGen);
     
208.                         pPixel++;
     
209.                 }while(--x);
     
210. 
     
211.                 //每处理一行像素，判断是否应该重绘屏幕
     
212.                 //最大重绘频率每秒钟100下。因为绘图需要消耗时间。
     
213.                 if(GetTickCount()-dwLastTick>=10)
     
214.                 {
     
215.                         dwLastTick=GetTickCount();
     
216.                         InvalidateRect(g_hWnd,&rc,FALSE);//重绘屏幕
     
217.                         if(!DoEvents())
     
218.                                 break;
     
219.                 }
     
220.         }while(--y);
     
221. 
     
222.         Index=0;
     
223.         GenPalette(g_pGen,OnGetColor,&Index);//产生调色板
     
224.         InvalidateRect(g_hWnd,&rc,FALSE);//最后重绘屏幕
     
225. 
     
226. CleanReturn:
     
227.         if(fp)//返回前清理内存
     
228.                 fclose(fp);
     
229.         free(LineData);
     
230.         return;
     
231. NoMem:
     
232.         MessageBox(g_hWnd,TEXT("内存不足。"),NULL,MB_ICONEXCLAMATION);
     
233.         goto CleanReturn;
     
234. ReadFail:
     
235.         MessageBox(g_hWnd,TEXT("读取文件失败。"),NULL,MB_ICONEXCLAMATION);
     
236.         goto CleanReturn;
     
237. BadFormat:
     
238.         MessageBox(g_hWnd,TEXT("不是BMP文件或格式错误。"),NULL,MB_ICONEXCLAMATION);
     
239.         goto CleanReturn;
     
240. Not24Bit:
     
241.         MessageBox(g_hWnd,TEXT("不是24位BMP文件。"),NULL,MB_ICONEXCLAMATION);
     
242.         goto CleanReturn;
     
243. }
     
244. 
     
245. LRESULT CALLBACK WndProc(HWND hWnd,UINT uMsg,WPARAM wp,LPARAM lp);//消息处理器
     
246. //=============================================================================
     
247. //函数：_tWinMain
     
248. //描述：整个程序的入口点
     
249. //-----------------------------------------------------------------------------
     
250. int APIENTRY _tWinMain
     
251. (
     
252.         HINSTANCE hInst,
     
253.         HINSTANCE hPrevInst,
     
254.         LPTSTR szCmdLine,
     
255.         int nShowCmd
     
256. )
     
257. {
     
258.         WNDCLASSEX WndClass;
     
259.         ATOM ClassAtom=0;
     
260.         MSG msg;
     
261. 
     
262.         //注册窗口类
     
263.         memset(&WndClass,0,sizeof(WndClass));
     
264.         WndClass.cbSize=sizeof(WndClass);
     
265.     WndClass.lpfnWndProc=WndProc;
     
266.     WndClass.hInstance=hInst;
     
267.         WndClass.hIcon=LoadIcon(NULL,MAKEINTRESOURCE(IDI_APPLICATION));
     
268.     WndClass.hCursor=LoadCursor(NULL,MAKEINTRESOURCE(IDC_ARROW));
     
269.     WndClass.hbrBackground=(HBRUSH)(COLOR_BTNFACE+1);
     
270.     WndClass.lpszClassName=TEXT("NormalWindow");
     
271.     WndClass.hIconSm=LoadIcon(NULL,MAKEINTRESOURCE(IDI_APPLICATION));
     
272.         ClassAtom=RegisterClassEx(&WndClass);
     
273.         if(!ClassAtom)
     
274.                 goto Cleanup;
     
275. 
     
276.         //创建窗口
     
277.         g_hWnd=CreateWindowEx(0,(LPCTSTR)ClassAtom,TEXT("主窗口"),
     
278.                 WS_OVERLAPPEDWINDOW,
     
279.                 CW_USEDEFAULT,CW_USEDEFAULT,CW_USEDEFAULT,CW_USEDEFAULT,
     
280.                 NULL,NULL,hInst,NULL);
     
281.         if(!g_hWnd)
     
282.                 goto Cleanup;
     
283. 
     
284.         //显示窗口
     
285.         ShowWindow(g_hWnd,nShowCmd);
     
286.         UpdateWindow(g_hWnd);
     
287. 
     
288.         //设置窗口允许接收拖拽文件。
     
289.         DragAcceptFiles(g_hWnd,TRUE);
     
290. 
     
291.         //消息循环
     
292.         while(GetMessage(&msg,NULL,0,0))
     
293.         {
     
294.                 TranslateMessage(&msg);
     
295.                 DispatchMessage(&msg);
     
296.         }
     
297. 
     
298.         if(g_hBackgroundBMP)
     
299.                 DeleteObject(g_hBackgroundBMP);
     
300.         if(g_hBackgroundDC)
     
301.                 ReleaseDC(g_hWnd,g_hBackgroundDC);
     
302. 
     
303.         if(g_pGen)
     
304.                 DestroyPalGen(g_pGen);
     
305.         UnregisterClass((LPCTSTR)ClassAtom,hInst);
     
306.         return 0;
     
307. Cleanup:
     
308.         if(ClassAtom)
     
309.                 UnregisterClass((LPCTSTR)ClassAtom,hInst);
     
310.         MessageBox(NULL,TEXT("启动程序失败。"),
     
311.                 TEXT("无法启动程序"),MB_ICONEXCLAMATION);
     
312.         return 1;
     
313. }
     
314. 
     
315. //=============================================================================
     
316. //函数：WndProc
     
317. //描述：窗口消息处理程序
     
318. //-----------------------------------------------------------------------------
     
319. LRESULT CALLBACK WndProc(HWND hWnd,UINT uMsg,WPARAM wp,LPARAM lp)
     
320. {
     
321.         switch(uMsg)
     
322.         {
     
323.         case WM_CREATE:
     
324.         case WM_SIZING:
     
325.         case WM_SIZE:
     
326.                 {
     
327.                         RECT rc;
     
328.                         HDC hDC;
     
329. 
     
330.                         hDC=GetDC(hWnd);
     
331.                         GetClientRect(hWnd,&rc);
     
332. 
     
333.                         //重新生成后台画板
     
334.                         if(g_hBackgroundBMP)
     
335.                                 DeleteObject(g_hBackgroundBMP);
     
336.                         if(g_hBackgroundDC)
     
337.                                 ReleaseDC(hWnd,g_hBackgroundDC);
     
338.                         g_hBackgroundDC=CreateCompatibleDC(hDC);
     
339.                         g_hBackgroundBMP=CreateCompatibleBitmap
     
340.                                 (hDC,rc.right-rc.left,rc.bottom-rc.top);
     
341.                         SelectObject(g_hBackgroundDC,g_hBackgroundBMP);
     
342.                         if(hDC)
     
343.                                 ReleaseDC(hWnd,hDC);
     
344.                        
     
345.                         //刷白画板
     
346.                         FillRect(g_hBackgroundDC,&rc,(HBRUSH)(COLOR_BTNFACE+1));
     
347.                         InvalidateRect(hWnd,&rc,FALSE);
     
348.                         break;
     
349.                 }
     
350.         case WM_PAINT:
     
351.                 {
     
352.                         PAINTSTRUCT ps;
     
353.                         HDC hDC;
     
354.                         HBRUSH hBrush;
     
355.                         RECT rc;
     
356.                         TCHAR szTitle[256];
     
357. 
     
358.                         size_t x,y,Index;
     
359.                        
     
360.                         //绘图时，先绘制到画板上，再把画板覆盖到窗口上。
     
361. 
     
362.                         GetClientRect(hWnd,&rc);
     
363.                         hDC=BeginPaint(hWnd,&ps);
     
364. 
     
365.                         FillRect(g_hBackgroundDC,&rc,(HBRUSH)(COLOR_BTNFACE+1));
     
366. 
     
367.                         Index=0;
     
368.                         //先画调色板
     
369.                         for(y=0;y<16;y++)
     
370.                         {
     
371.                                 for(x=0;x<16;x++)
     
372.                                 {
     
373.                                         hBrush=CreateSolidBrush(RGB(
     
374.                                                 g_Palette[Index].rgbRed,
     
375.                                                 g_Palette[Index].rgbGreen,
     
376.                                                 g_Palette[Index].rgbBlue));
     
377.                                         hBrush=(HBRUSH)SelectObject(g_hBackgroundDC,hBrush);
     
378. 
     
379.                                         //调色板，每个颜色8x8
     
380.                                         Rectangle(g_hBackgroundDC,x*8,y*8,x*8+8,y*8+8);
     
381. 
     
382.                                         hBrush=(HBRUSH)SelectObject(g_hBackgroundDC,hBrush);
     
383.                                         DeleteObject(hBrush);
     
384.                                         Index++;
     
385.                                 }
     
386.                         }
     
387.                         //然后画八叉树
     
388.                         if(g_pGen && g_pGen->pRoot)
     
389.                         {
     
390.                                 float        fRootX=(float)(rc.right)*0.5f,
     
391.                                                 fRootY=(float)(rc.bottom)*0.75f;
     
392.                                 //先画树枝
     
393.                                 DrawTree(g_hBackgroundDC,g_pGen->pRoot,
     
394.                                         -(float)M_PI_4,fRootX,fRootY,40,4,(float)(M_PI*0.125),0);
     
395.                                 //后画树叶
     
396.                                 DrawTree(g_hBackgroundDC,g_pGen->pRoot,
     
397.                                         -(float)M_PI_4,fRootX,fRootY,40,4,(float)(M_PI*0.125),1);
     
398.                         }
     
399.                        
     
400.                         BitBlt(hDC,0,0,rc.right-rc.left,rc.bottom-rc.top,
     
401.                                 g_hBackgroundDC,0,0,SRCCOPY);
     
402.                         EndPaint(hWnd,&ps);
     
403. 
     
404.                         _stprintf(szTitle,TEXT("%u"),g_pGen->NbLeaf);
     
405.                         SetWindowText(hWnd,szTitle);
     
406.                 }
     
407.                 break;
     
408.         case WM_DESTROY:
     
409.                 PostQuitMessage(0);
     
410.                 return 0;
     
411.         case WM_DROPFILES:
     
412.                 {
     
413.                         TCHAR*pszDropFileName;
     
414.                         size_t cbDropFileName;
     
415.                         //取得第0个拖入文件的文件名长度
     
416.                         cbDropFileName=DragQueryFile((HDROP)wp,0,NULL,0)+1;//添加'\0'结尾
     
417.                         //分配内存并取得第0个拖入文件名
     
418.                         pszDropFileName=(TCHAR*)malloc(cbDropFileName*sizeof(TCHAR));
     
419.                         if(pszDropFileName)
     
420.                         {
     
421.                                 DragQueryFile((HDROP)wp,0,pszDropFileName,cbDropFileName);
     
422.                                 DragFinish((HDROP)wp);
     
423.                                 ParseBMPFile(pszDropFileName);
     
424.                                 free(pszDropFileName);
     
425.                         }
     
426.                 }
     
427.                 return 0;
     
428.         }
     
429.         return DefWindowProc(hWnd,uMsg,wp,lp);
     
430. }

复制代码

BIN: OctreePalette_exe.7z (44.1 KB, 下载次数: 58)

2015-2-5 14:28 上传

点击文件名下载附件

SRC: OctreePalette.7z (90.99 KB, 下载次数: 86)

2015-2-5 14:28 上传

点击文件名下载附件