三维体数据分割算法及实现

三维体数据分割算法及实现

本文基于分裂合并分割算法，提出了两种新的分割算法：基于八叉树的分裂合并算法和基于自适应包围盒的分裂合并算法。下面将对这两种算法进行描述。

1 分裂合并法分析

区域生长法的原理是根据种子像素点(体数据中为体素点)向其周围扩散，对区域周围的每一个像素/体素进行分析。区域生长法需要用额外的内存区域来保存待生长的像素/体素点，并且算法的时间复杂度较大。区域生长的过程中，需要以像素/体素为单位一圈一圈地向外扩张。对于体数据来说，区域生长法花费较多的运算时间。

分裂合并的基本思想是：先将整幅图像或体数据依据某种规则分裂出很多个形状规则的子区域，子区域内的像素或体素特征具有一致性，然后合并特征相似的子区域，从而实现分割的目的^[2]。体数据分裂后的各子区域是一个立方体的体素集合，集合内所有体素属于同一区域组织。分裂的同时需要对子区域生成连通图，即将体数据中分裂区域之间的邻接关系以图的形式表达出来。合并的工作与区域生长法相似，先选择一个区域生长的种子点，确定该种子点所在的正方体分裂区域；然后以该区域为中心，对其所有相邻的子区域进行判断；如果相邻区域与该区域是同一组织则进行合并。该算法实际是以立方体节点为最小单位对种子点进行生长，因此其运算效率要优于区域生长法。在区域分裂时需要生成区域邻接图，通过邻接图表示各子区域间的相邻关系。在区域合并时，需要通过邻接图来查找等待合并的子区域。

分裂的子区域结构需要包含以下几种数据：

（1）空间包围盒。用来记录子区域的大小和位置；

（2）内部数据特征值。可以记录所包含体素的灰度特征，分布情况等；

（3）相邻节点。每个非边界节点至少有6个相邻节点（每个立方体面一个）。在区域合并时需要判断该节点的所有相邻节点。

分裂子区域结构为如下代码中的结构体BoxNode。该结构中保存着其数据区域、特征值、与之相邻的子区域。

struct BoxNode //节点包围盒结构体，每一个节点表示一个分裂后的子区域

{

Point ptStart; //节点的开始位置

Point ptEnd; //节点的结束位置

WORD voxelValue; //体素值

long nMergeRagion; //该节点的合并区域，未合并时值为-1

std::set<BoxNode*> setNeighbours; //相邻节点指针集合

void AddNeighbour(BoxNode* nodePtr) //添加相邻节点

{setNeighbours.insert(nodePtr); }

void RemoveNeighbour(BoxNode* nodePtr) //移除相邻节点

{setNeighbours.erase(nodePtr);}

};

2 基于八叉树的分裂算法

对于二维图像来说，可以采用四叉树的方式对其进行分裂：首先选取区域一致性准则(如像素灰度值)，然后根据这一准则将图像等分成四个区域，并分别判断这些区域是否满足一致性准则；如果不满足一致性，则继续分裂^[24]。本课题所研究的是对三维体数据的分割，因此对其分裂时将基于二维的四叉树方法扩展为针对三维的八叉树。

八叉树是每个非叶节点有且仅有8个子节点的一种树形结构体，它是表现一个被立方体封装的三维物体的理想结构^[5]。对于有着物体密集的数据集合，八叉树能够快速的进行数据管理、可视化裁剪、光线跟踪等三维空间操作。八叉树的根节点包含一个立方体，它封闭着全部体数据。每个节点的子节点是8个相同大小的立方体，它们将父节点等分为八份。如图5-6所示。

a.初始节点 b.第一次分裂 c.第二次分裂

图5- 6八叉树模型

用Volume表示整个体数据区域，Ｐ表示区域特征一致性测度的谓词逻辑，从最高层开始，将Volume分裂成8个相同的正方体子区域Volume_i，对于任一个区域Volume_i如果P(Volume_i)为false就将继续对Volume_i进行8等分，直至P(Volume_i)为true或Volume_i为单个体素为止。对于一个2ⁿ 2ⁿ 2ⁿ的体数据，最多可以分解至n层，第n层数据区域为单个体素。对于本文实验所采用的医学图像来说，图像分辨率为512 512。在对XOY平面上进行分裂时最多可以分解至第8层。假如断层数目为M,那么处理时将Ｚ轴方向上的断层个数设为2^k,使得2^k<= M< 2^(k+1)。在八叉树分裂的同时需要生成区域邻接图，即每次分裂后，新生成的8个节点是上下左右相邻的，然后判断每个新生成节点与原相邻节点是否相邻。

图5- 7基于八叉树的分裂算法流程图

基于八叉树分裂算法的步骤如下所述：

a.生成一个包含整个体数据的节点，该节点的开始位置为原点：

ptStart(0, 0, 0)；结束位置为体数据的最大值ptEnd(x_max, y_max, z_max)；

b. 对步骤a生成的节点进行特征一致性检测，如果不一致则该节点需要进行分裂处理，跳到步骤c，否则，跳到结束分裂；

c.将节点进行八叉树分裂处理，即由该节点分裂出八个新的子节点；

d.建立新生成的八个子节点的相邻关系，并更新新节点与旧节点的相邻关系；

e.对新生成的八个子节点分别做特征一致性检测，如果不一致，则对该节点进行步骤c的操作；

f.分裂完成。

基于八叉树分裂算法采用分治递归的策略，能够快速有效的对体数据进行分裂处理。由于该算法将一个问题拆分成8个子问题，所以可以采用并行的多CPU运算对其进行优化。但基于八叉树分裂算法会产生过度分裂的情况，假如体数据中一个特征一致性区域正好位于某个待分裂节点的中心位置，那么使用八叉树会将该区域分裂成八份。

3 基于自适应包围盒的分裂算法

为了解决区域的过度分裂的问题，本文提出一种基于自适应包围盒的分裂算法，能有效解决这一过度分裂问题。该算法的基本思想是一次性的遍历体数据中每个体素，找出所有具有特征值一致性的立方体区域，然后生成这些立方体区域的邻接图。

图5- 8基于自适应包围盒的分裂算法流程图

自适应包围盒的分裂算法的实现步骤如下所述：

a. 首先创建一个分裂区域子节点集合setNodes，和一个与体数据相同大小的数据区域NodeArray。NodeArray用于存放每个体素所在子节点的地址；还需要将NodeArray的数据内容设置为空；

b.依次遍历体数据中的每一个体素点Voxel(x_i, y_i,z_i)；当完成遍历后，跳转到步骤g。

c.判断Voxel(x_i,y_i,z_i)是否已经被扩展过；判断方法是看其对应NodeArray(x_i,y_i,z_i)中的值是否为空；如果是扩展过的，则返回步骤b;

d.创建一个子区域节点Node_j，该节点的起始位置为Voxel(x_i,y_i,z_i)；

e.分别对X、Y、Z三个坐标轴的正方向进行扩展，并判断新扩展的体素与Voxel(x_i,y_i,z_i)是否具有特征一致性；当某一方向出现不一致的体素时，则停止该方向的扩展；

f.步骤e完成后会得到节点Node_j的结束位置Voxel(x_i+m, y_i+n,z_i+k)；先将Node_j所包含的体素Voxel(x_s,y_s,z_s)所对应NodeArray(x_s,y_s,z_s)的值设置为Node_j的地址，再将其添加到子节点集合setNodes中；

g.在遍历完体数据中所有体素后，通过遍历NodeArray中的数据，生成子区域节点的相邻关系。

自适应包围盒的分裂算法能够只通过两次遍历体数据，就可以对体数据进行分裂；并且分裂后的区域不会有像八叉树那种过度分裂的情况。

4 节点合并算法

该阶段与区域生长算法很相似：首先选择一个种子点，获得该种子点所在的子区域V_merge。根据区域邻接图，对任意与V_merge相邻的子区域V_i，若P(V_merge U V_i)==true，则将其合并并将V_i的相邻子区域设为V_merge相邻的子区域。直至没有满足合并条件的相邻区域为止。

a.通过种子点的坐标位置找到种子点所在的子区域节点；然后创建一个待合并的队列，并将刚才找到的子区域节点放到该队列中；再将该子区域节点放到合并区域集合中；

b.从待合并队列中取出一个子区域节点；如果待合并队列为空则表示合并完成，跳转到步骤d;

c.依次对步骤b中取出的节点的相邻节点做一致性检测，如果检测通过，则将该相邻节点分别放到待合并队列和合并区域集合中；

d.完成合并操作。

  1 /****************************************************************
  2   File name   :  VolumeDataSplitMerge.CPP
  3   Author      :  叶峰
  4   Version     :  1.0a
  5   Create Date :  2011/12/01   
  6   Description :  
  7   Others      :  
  8 *****************************************************************/
  9 
 10 // --------------------------------------------------------------------------------------
 11 
 12 #include <Windows.h>
 13 #include <set>
 14 
 15 // --------------------------------------------------------------------------------------
 16 
 17 struct Point                    // 体数据中的体素点坐标
 18 {
 19     long x;
 20     long y;
 21     long z;
 22     Point()
 23     {
 24         x = 0; y = 0; z = 0;
 25     }
 26     Point(long _x, long _y, long _z)
 27     {
 28         x = _x; y = _y; z = _z;
 29     }
 30 };
 31 
 32 struct BoxNode                  // 节点包围盒结构体
 33 {
 34     Point ptStart;              // 节点的开始位置
 35     Point ptEnd;                // 节点的结束位置
 36     WORD voxelValue;            // 体素值
 37     bool isMergedTest;          // 用于判断该节点是否被合并
 38     std::set<BoxNode*> setNeighbours;       // 相邻节点指针集合
 39     void AddNeighbour(BoxNode* nodePtr)     // 添加相邻节点
 40     {
 41         setNeighbours.insert(nodePtr);  
 42     }
 43     void RemoveNeighbour(BoxNode* nodePtr)  // 移除相邻节点
 44     {
 45         setNeighbours.erase(nodePtr);
 46     }
 47 };
 48 
 49 // --------------------------------------------------------------------------------------
 50 
 51 WORD* g_pVolumeData;            // 体数据
 52 long g_dwX, g_dwY, g_dwZ;       // 体数据的大小
 53 WORD g_nThreshold;  
 54 std::set<BoxNode*> g_setSplitNodes; // 分裂出的所有区域节点的集合
 55 
 56 // --------------------------------------------------------------------------------------
 57 
 58 // 判断一个体素坐标点是否在一包围盒节点中
 59 inline bool IsPointInBox(const Point& point, const BoxNode& box)
 60 {
 61     return (point.x >= box.ptStart.x && point.x <= box.ptEnd.x &&
 62             point.y >= box.ptStart.y && point.y <= box.ptEnd.y &&
 63             point.z >= box.ptStart.z && point.z <= box.ptEnd.z);
 64 }
 65 
 66 // 获得一个坐标点的体素值
 67 inline WORD GetVoxelValue(const Point& point)
 68 {
 69     return g_pVolumeData[point.z*g_dwY*g_dwX + point.y*g_dwX + point.x];
 70 }
 71 inline WORD GetVoxelValue(long x, long y, long z)
 72 {
 73     return g_pVolumeData[z*g_dwY*g_dwX + y*g_dwX + x];
 74 }
 75 
 76 // 判断两个体素值是否相似
 77 inline bool IsSimilar(WORD value0, WORD value1)
 78 {
 79     if (value0 > value1)
 80         return (value0 - value1 <= g_nThreshold);
 81     else
 82         return (value1 - value0 <= g_nThreshold);
 83 }
 84 
 85 // 判断两个节点包围盒是否相邻
 86 inline bool IsNodeNeighbour(const BoxNode* nodePtr0, const BoxNode* nodePtr1)
 87 {
 88     if (nodePtr0->ptStart.x - 1 == nodePtr1->ptEnd.x)
 89     {
 90         if (nodePtr0->ptStart.y <= nodePtr1->ptEnd.y &&
 91             nodePtr0->ptEnd.y <= nodePtr1->ptStart.y &&
 92             nodePtr0->ptStart.z <= nodePtr1->ptEnd.z &&
 93             nodePtr0->ptEnd.z <= nodePtr1->ptStart.z)
 94         {
 95             return true;
 96         }
 97     }
 98     else if (nodePtr0->ptEnd.x + 1 == nodePtr1->ptStart.x)
 99     {
100         if (nodePtr0->ptStart.y <= nodePtr1->ptEnd.y &&
101             nodePtr0->ptEnd.y <= nodePtr1->ptStart.y &&
102             nodePtr0->ptStart.z <= nodePtr1->ptEnd.z &&
103             nodePtr0->ptEnd.z <= nodePtr1->ptStart.z)
104         {
105             return true;
106         }
107     }
108     else if (nodePtr0->ptStart.y - 1 == nodePtr1->ptEnd.y)
109     {
110         if (nodePtr0->ptStart.x <= nodePtr1->ptEnd.x &&
111             nodePtr0->ptEnd.x <= nodePtr1->ptStart.x &&
112             nodePtr0->ptStart.z <= nodePtr1->ptEnd.z &&
113             nodePtr0->ptEnd.z <= nodePtr1->ptStart.z)
114         {
115             return true;
116         }
117     }
118     else if (nodePtr0->ptEnd.y + 1 == nodePtr1->ptStart.y)
119     {
120         if (nodePtr0->ptStart.x <= nodePtr1->ptEnd.x &&
121             nodePtr0->ptEnd.x <= nodePtr1->ptStart.x &&
122             nodePtr0->ptStart.z <= nodePtr1->ptEnd.z &&
123             nodePtr0->ptEnd.z <= nodePtr1->ptStart.z)
124         {
125             return true;
126         }
127     }
128     else if (nodePtr0->ptStart.z - 1 == nodePtr1->ptEnd.z)
129     {
130         if (nodePtr0->ptStart.y <= nodePtr1->ptEnd.y &&
131             nodePtr0->ptEnd.y <= nodePtr1->ptStart.y &&
132             nodePtr0->ptStart.x <= nodePtr1->ptEnd.x &&
133             nodePtr0->ptEnd.x <= nodePtr1->ptStart.x)
134         {
135             return true;
136         }
137     }
138     else if (nodePtr0->ptEnd.z + 1 == nodePtr1->ptStart.z)
139     {
140         if (nodePtr0->ptStart.y <= nodePtr1->ptEnd.y &&
141             nodePtr0->ptEnd.y <= nodePtr1->ptStart.y &&
142             nodePtr0->ptStart.x <= nodePtr1->ptEnd.x &&
143             nodePtr0->ptEnd.x <= nodePtr1->ptStart.x)
144         {
145             return true;
146         }
147     }
148 
149     return false;
150 }
151 
152 // --------------------------------------------------------------------------------------
153 // 更新8叉树节点的相邻关系
154 void UpdateOctreeNodeNeighbour(BoxNode* oldNodePtr, BoxNode* newNodePtr)
155 {
156     BoxNode* nerghbourNodePtr;
157     std::set<BoxNode*>::iterator itor = oldNodePtr->setNeighbours.begin();
158     while (itor != oldNodePtr->setNeighbours.end())
159     {
160         nerghbourNodePtr = *itor;
161         nerghbourNodePtr->RemoveNeighbour(oldNodePtr);
162         if (IsNodeNeighbour(nerghbourNodePtr, newNodePtr))
163         {
164             nerghbourNodePtr->AddNeighbour(newNodePtr);
165             newNodePtr->AddNeighbour(nerghbourNodePtr);
166         }
167         itor++;
168     }
169 }
170 
171 // 使用8叉树法分裂体数据
172 void OctreeSplitVolumeData(BoxNode* nodePtr)
173 {
174     if (nodePtr == NULL)        // 当nodePtr为空指针时表示对整个体数据进行分裂
175     {
176         nodePtr = new BoxNode();
177         nodePtr->ptStart = Point(0, 0, 0);
178         nodePtr->ptEnd = Point(g_dwX - 1, g_dwY - 1, g_dwZ - 1);
179         nodePtr->voxelValue = GetVoxelValue(nodePtr->ptStart);
180         nodePtr->isMergedTest = false;
181     }
182 
183     bool shouldSplit = false;
184     // 判断是否需要分裂该节点
185     WORD voxelValue;
186     for (long z = nodePtr->ptStart.z; z <= nodePtr->ptEnd.z; z++)
187     {
188         for (long y = nodePtr->ptStart.y; y <= nodePtr->ptEnd.y; y++)
189         {
190             for (long x = nodePtr->ptStart.x; x <= nodePtr->ptEnd.x; x++)
191             {
192                 voxelValue = GetVoxelValue(x, y, z);
193                 if (!IsSimilar(voxelValue, nodePtr->voxelValue))
194                 {
195                     shouldSplit = true;
196                     break;
197                 }
198             }
199             if (shouldSplit)
200                 break;
201         }
202         if (shouldSplit)
203             break;
204     }
205 
206     if (!shouldSplit)
207     {
208         return;
209     }
210 
211     Point ptSplit;          // 分裂点
212     ptSplit.x = (nodePtr->ptStart.x + nodePtr->ptEnd.x)/2;
213     ptSplit.y = (nodePtr->ptStart.y + nodePtr->ptEnd.y)/2;
214     ptSplit.z = (nodePtr->ptStart.z + nodePtr->ptEnd.z)/2;
215 
216     // 8分原节点
217     BoxNode* nodeSplitPtr[8];
218     for (long i = 0; i < 8; i++)
219     {
220         nodeSplitPtr[i] = new BoxNode();
221         nodeSplitPtr[i]->ptStart = nodePtr->ptStart;
222         nodeSplitPtr[i]->ptEnd = ptSplit;
223 
224         if (i & 1)      // X轴向变化
225         {
226             nodeSplitPtr[i]->ptStart.x = ptSplit.x + 1;
227             nodeSplitPtr[i]->ptEnd.x = nodePtr->ptEnd.x;
228             if (nodeSplitPtr[i]->ptStart.x > nodeSplitPtr[i]->ptEnd.x) // 非法的分裂点
229             {
230                 delete nodeSplitPtr[i];
231                 nodeSplitPtr[i] = NULL;
232                 continue;
233             }
234         }
235         if (i & 2)      // Y轴向变化
236         {
237             nodeSplitPtr[i]->ptStart.y = ptSplit.y + 1;
238             nodeSplitPtr[i]->ptEnd.y = nodePtr->ptEnd.y;
239             if (nodeSplitPtr[i]->ptStart.y > nodeSplitPtr[i]->ptEnd.y) // 非法的分裂点
240             {
241                 delete nodeSplitPtr[i];
242                 nodeSplitPtr[i] = NULL;
243                 continue;
244             }
245         }
246         if (i & 4)      // Z轴向变化
247         {
248             nodeSplitPtr[i]->ptStart.z = ptSplit.z + 1;
249             nodeSplitPtr[i]->ptEnd.z = nodePtr->ptEnd.z;
250             if (nodeSplitPtr[i]->ptStart.z > nodeSplitPtr[i]->ptEnd.z) // 非法的分裂点
251             {
252                 delete nodeSplitPtr[i];
253                 nodeSplitPtr[i] = NULL;
254                 continue;
255             }
256         }
257 
258         nodeSplitPtr[i]->voxelValue = nodePtr->voxelValue;
259         nodeSplitPtr[i]->isMergedTest = false;
260         UpdateOctreeNodeNeighbour(nodePtr, nodeSplitPtr[i]);
261     }
262 
263     for (long i = 0; i < 8; i++)
264     {
265         if (nodeSplitPtr[i])
266         {
267             for (long j = 0; j < 8; j++)
268             {
269                 if (i != j && nodeSplitPtr[j])
270                 {
271                     // 添加相邻关系
272                     nodeSplitPtr[i]->AddNeighbour(nodeSplitPtr[j]);
273                 }
274             }
275             g_setSplitNodes.insert(nodeSplitPtr[i]);
276         }
277     }
278 
279     // 删除旧的节点
280     delete nodePtr;
281     g_setSplitNodes.erase(nodePtr);
282 
283     // 递归处理分裂的节点
284     for (long i = 0; i < 8; i++)
285     {
286         if (nodeSplitPtr[i])
287         {
288             OctreeSplitVolumeData(nodeSplitPtr[i]);
289         }
290     }
291 }
292 
293 // --------------------------------------------------------------------------------------
294 void UpdateVoxelNodePtr(BoxNode* nodePtr, BoxNode** listVoxelNodePtr)
295 {
296     for (long z = nodePtr->ptStart.z; z <= nodePtr->ptEnd.z; z++)
297         for (long y = nodePtr->ptStart.y; y <= nodePtr->ptEnd.y; y++)
298             for (long x = nodePtr->ptStart.x; x <= nodePtr->ptEnd.x; x++)
299                 listVoxelNodePtr[z*g_dwY*g_dwX + y*g_dwX + x] = nodePtr;
300 }
301 
302 // 自适应包围盒法分裂体数据
303 void AdaptableSplitVolumeData()
304 {
305     // 记录每一个体素点所在的节点包围盒
306     BoxNode** listVoxelNodePtr = (BoxNode**)malloc(sizeof(BoxNode*)*g_dwX*g_dwY*g_dwZ);
307     memset(listVoxelNodePtr, 0, sizeof(BoxNode*)*g_dwX*g_dwY*g_dwZ);
308 
309     for (long z = 0; z < g_dwZ; z++)
310     {
311         for (long y = 0; y < g_dwY; y++)
312         {
313             for (long x = 0; x < g_dwX; x++)
314             {
315                 if (listVoxelNodePtr[z*g_dwY*g_dwX + y*g_dwX + x] != NULL)
316                 {
317                     continue;
318                 }
319 
320                 BoxNode* nodePtr = new BoxNode();
321                 nodePtr->ptStart = Point(x, y, z);
322                 nodePtr->ptEnd = nodePtr->ptStart;
323                 nodePtr->voxelValue = GetVoxelValue(nodePtr->ptStart);
324                 nodePtr->isMergedTest = false;
325 
326                 // 扩张该节点
327                 bool xExtend = true;
328                 bool yExtend = true;
329                 bool zExtend = true;
330                 long extend;
331                 WORD voxelValue;
332                 while (xExtend || yExtend || zExtend)
333                 {
334                     if (xExtend)        // X轴方向扩张
335                     {
336                         extend = nodePtr->ptEnd.x + 1;
337                         if (extend == g_dwX)
338                         {
339                             xExtend = false;
340                         }
341                         else
342                         {
343                             for (long _z = nodePtr->ptStart.z; _z <= nodePtr->ptEnd.z; _z++)
344                             {
345                                 for (long _y = nodePtr->ptStart.y; _y <= nodePtr->ptEnd.y; _y++)
346                                 {
347                                     voxelValue = GetVoxelValue(extend, _y, _z);
348                                     if (!IsSimilar(voxelValue, nodePtr->voxelValue))
349                                     {
350                                         xExtend = false;
351                                         break;
352                                     }
353                                 }
354                                 if (!xExtend)
355                                 {
356                                     break;
357                                 }
358                             }
359 
360                             if (xExtend)
361                             {
362                                 nodePtr->ptEnd.x++;
363                             }
364                         }
365                     }
366 
367                     if (yExtend)        // Y轴方向扩张
368                     {
369                         extend = nodePtr->ptEnd.y + 1;
370                         if (extend == g_dwY)
371                         {
372                             yExtend = false;
373                         }
374                         else
375                         {
376                             for (long _z = nodePtr->ptStart.z; _z <= nodePtr->ptEnd.z; _z++)
377                             {
378                                 for (long _x = nodePtr->ptStart.x; _x <= nodePtr->ptEnd.x; _x++)
379                                 {
380                                     voxelValue = GetVoxelValue(_x, extend, _z);
381                                     if (!IsSimilar(voxelValue, nodePtr->voxelValue))
382                                     {
383                                         yExtend = false;
384                                         break;
385                                     }
386                                 }
387                                 if (!yExtend)
388                                 {
389                                     break;
390                                 }
391                             }
392 
393                             if (yExtend)
394                             {
395                                 nodePtr->ptEnd.y++;
396                             }
397                         }
398                     }
399                 }
400 
401                 if (zExtend)        // Z轴方向扩张
402                 {
403                     extend = nodePtr->ptEnd.z + 1;
404                     if (extend == g_dwZ)
405                     {
406                         zExtend = false;
407                     }
408                     else
409                     {
410                         for (long _x = nodePtr->ptStart.x; _x <= nodePtr->ptEnd.x; _x++)
411                         {
412                             for (long _y = nodePtr->ptStart.y; _y <= nodePtr->ptEnd.y; _y++)
413                             {
414                                 voxelValue = GetVoxelValue(_x, _y, extend);
415                                 if (!IsSimilar(voxelValue, nodePtr->voxelValue))
416                                 {
417                                     zExtend = false;
418                                     break;
419                                 }
420                             }
421                             if (!zExtend)
422                             {
423                                 break;
424                             }
425                         }
426 
427                         if (zExtend)
428                         {
429                             nodePtr->ptEnd.z++;
430                         }
431                     }
432                 }
433 
434                 UpdateVoxelNodePtr(nodePtr, listVoxelNodePtr);
435                 g_setSplitNodes.insert(nodePtr);
436             }
437         }
438     }
439 
440     // 生成节点的相邻关系
441     BoxNode* nodePtr;
442     BoxNode* nodeNext;
443     for (long z = 0; z < g_dwZ - 1; z++)
444     {
445         for (long y = 0; y < g_dwY - 1; y++)
446         {
447             for (long x = 0; x < g_dwX - 1; x++)
448             {
449                 nodePtr = listVoxelNodePtr[z*g_dwY*g_dwX + y*g_dwX + x];
450                 nodeNext = listVoxelNodePtr[z*g_dwY*g_dwX + y*g_dwX + x + 1];
451                 if (nodePtr != nodeNext)
452                 {
453                     nodePtr->AddNeighbour(nodeNext);
454                     nodeNext->AddNeighbour(nodePtr);
455                 }
456                 nodeNext = listVoxelNodePtr[z*g_dwY*g_dwX + (y + 1)*g_dwX + x];
457                 if (nodePtr != nodeNext)
458                 {
459                     nodePtr->AddNeighbour(nodeNext);
460                     nodeNext->AddNeighbour(nodePtr);
461                 }
462                 nodeNext = listVoxelNodePtr[(z + 1)*g_dwY*g_dwX + y*g_dwX + x];
463                 if (nodePtr != nodeNext)
464                 {
465                     nodePtr->AddNeighbour(nodeNext);
466                     nodeNext->AddNeighbour(nodePtr);
467                 }
468             }
469         }
470     }
471 
472     free(listVoxelNodePtr);
473 }
474 
475 // --------------------------------------------------------------------------------------
476 
477 // 合并体数据
478 void MergeSplitVolumeData(IN const Point& ptStart,          // 输入起始点坐标
479                           OUT std::set<BoxNode*>& setMerge  // 输出合并的节点集合 
480                           )
481 {
482     setMerge.clear();
483 
484     // 由起始点坐标查找起始节点
485     BoxNode* pStartNode = NULL;
486     std::set<BoxNode*>::iterator itor = g_setSplitNodes.begin();
487     while(itor != g_setSplitNodes.end())
488     {
489         if (IsPointInBox(ptStart, *(*itor)))
490         {
491             pStartNode = *itor;
492             break;
493         }
494         itor++;
495     }
496     if (!pStartNode)
497     {
498         return;
499     }
500 
501     std::set<BoxNode*> setExtending;        // 正在扩张中的节点集合
502     std::set<BoxNode*> setExtendNext;       // 下一步需要扩张的节点集合
503     setExtending.insert(pStartNode);
504 
505     WORD voxelValue = pStartNode->voxelValue;
506     BoxNode* pCurrentNode;
507 
508     while(setExtending.size() > 0)
509     {
510         setExtendNext.clear();
511         std::set<BoxNode*>::iterator itor = setExtending.begin();
512         while (itor != setExtending.end())
513         {
514             pCurrentNode = *itor;
515             pCurrentNode->isMergedTest = true;
516             if (IsSimilar(voxelValue, (*itor)->voxelValue))
517             {
518                 setMerge.insert(*itor);
519 
520                 std::set<BoxNode*>::iterator itor2 = pCurrentNode->setNeighbours.begin();
521                 while(itor2 != pCurrentNode->setNeighbours.end())
522                 {
523                     if (!(*itor2)->isMergedTest)
524                     {
525                         setExtendNext.insert((*itor2));
526                     }
527                 }
528             }
529             itor++;
530         }
531 
532         setExtending = setExtendNext;
533     }
534 }