SimLOD代码精读（二）建立Octree之Splitting Pass分裂阶段

SimLOD (Similarity-based Level of Detail) 是一种基于相似性的多层次细节（LOD）算法，主要用于大规模3D点云或网格数据的动态简化。它通过分析数据相似性来自适应地调整细节层次，在保持视觉保真度的同时显著提升渲染效率。

Code Link：m-schuetz/SimLOD: Simultaneous LOD Generation and Rendering for Point Clouds

Paper Link：

[2310.03567] SimLOD: Simultaneous LOD Generation and Rendering

SimLOD代码精读（一）建立Octree之Counting Pass计数阶段-CSDN博客 

Splitting Pass

  doSplitting 函数的主要功能是处理需要分裂的节点（spillingNodes），将每个节点分裂成 8 个子节点，并进行相应的初始化操作。同时，它还会处理点数据的回收和占用网格（OccupancyGrid）的分配。 注意！待分裂的节点中的点数据，在counting阶段已经加入到了spilling溢出缓冲区中，这里就不再进行拷贝了。 只需要把分裂节点的点数据清除，换成voxel数据。SplittingPass操作也是并行执行的。

        对所有待分裂的节点：

1）添加8个子节点，给子节点编号，值初始化，name初始化；

2）添加待分裂节点和8个子节点的继承关系；

3）待分裂节点中点数据清空，chunk回收另作他用；

4）待分裂节点的grid启用，换成voxel掩膜数据，使用128*128*128/32个int32来表示

        本文精读的代码位于 modules\progressive_octree\progressive_octree_voxels.cu。在代码中已加入了详细的注释

/*** @param nodes				所有的节点起始地址* @param spillingNodes		溢出的节点=需要分裂的节点* @param numSpillingNodes	溢出节点的个数** @return 返回说明         这里好像没有给出返回值呢*     -<em>false</em> fail   *     -<em>true</em> succeed */
bool doSplitting(Node* nodes, Node** spillingNodes, uint32_t* numSpillingNodes){auto grid = cg::this_grid();// 注意！待分裂的节点中的点数据，在counting阶段已经加入到了spilling溢出缓冲区中，这里就不再进行拷贝了。// 只需要把分裂节点的点数据清除，换成voxel数据。// split the spilling nodes// PRINT("split %i spilling nodes \n", *numSpillingNodes);// 遍历所有需要分裂的节点，并创建8个子节点// spillNodeIndex 是当前正在处理的节点的索引。取值为0,1,2,...,*numSpillingNodes-1processRange(*numSpillingNodes, [&](int spillNodeIndex){Node* spillingNode = spillingNodes[spillNodeIndex];// create child nodes 总的节点数+8，注意childOffset是+8之前的numNodes值uint32_t childOffset = atomicAdd(&stats->numNodes, 8);// 对这8个子节点进行初始化for(int i = 0; i < 8; i++){// 三位二进制数，从高位到低位分别对应X、Y、Z轴// 例如，XYZ坐标索引为000b，则子节点索引为0 cx=0,cy=0,cz=0// 例如，XYZ坐标索引为100b，则子节点索引为4 cx=1,cy=0,cz=0int cx = (i >> 2) & 1;int cy = (i >> 1) & 1;int cz = (i >> 0) & 1;Node child;child.counter = 0;    // 子节点目前一定是叶子节点，点计数初始化为0 为啥有一个counter，还有一个numPoints？child.numPoints = 0;  // 子节点目前没有点，点数初始化为0child.points = nullptr;memset(&child.children, 0, 8 * sizeof(Node*)); // 初始化子节点的指针数组child.level = spillingNode->level + 1; // 子节点的层级等于父节点的层级+1// 子节点的X坐标等于父节点的X坐标乘以2加上cx// 以X方向为例，这是因为每增加一层，X方向的坐标索引区间会加一倍，比如第1层X坐标只有0或1，// 第2层X坐标有0、1、2或3，第3层X坐标有0、1、2、3、4、5、6、7，以此类推。child.X = 2 * spillingNode->X + cx; child.Y = 2 * spillingNode->Y + cy;child.Z = 2 * spillingNode->Z + cz;child.countIteration = 0; // 当前节点第几遍参与计数，子节点刚刚生成，还没有参与计数，初始化为0// 给节点起名字，这里的名字是有讲究的，因为节点的名字是由它所在的层级和子节点的索引组成的// 起名字的时候，先copy父节点的名字，然后在level位置上加上子节点的索引，比如000b的父节点的名字叫做0，// 这样的话，也可以根据名字直接得出这个节点到根节点的追溯路径memcpy(&child.name[0], &spillingNode->name[0], 20);child.name[child.level] = i + '0'; // // child.voxels = Array<Point>();child.numVoxels = 0; // 节点对应的有效立方块数目初始化为0child.numVoxelsStored = 0; // 当前存储的Voxel数目初始化为0nodes[childOffset + i] = child; // 给nodes总表的新节点赋值spillingNode->children[i] = &nodes[childOffset + i]; // 给分裂节点（作为父节点）的子节点赋值}// return chunks to chunkQueue// 将溢出节点中的所有点数据 (node->points) 并行拷贝到全局数组 spilledPointsChunk* chunk = spillingNode->points;while(chunk != nullptr){Chunk* next = chunk->next;chunk->next = nullptr;int32_t oldIndex = atomicAdd(&stats->numAllocatedChunks, -1); // numAllocatedChunks维护当前使用的Chunk数目// stats->numAllocatedChunks与chunkQueue的实际使用长度保持一致int32_t newIndex = oldIndex - 1;chunkQueue[newIndex] = chunk;chunk = next;}spillingNode->numPoints = 0;spillingNode->points = nullptr;// allocate occupancy grid for the spilled node// 分裂之后，节点不再存点了，改存立方体，立方体的数目为128*128*128，使用128*128*128个bit存储，若用int32存储的话，// 需要int32的数量为128*128*128/32=65536，每个bit表示一个立方体的状态，if(spillingNode->grid == nullptr){spillingNode->grid = (OccupancyGrid*)allocator_persistent->alloc(sizeof(OccupancyGrid));}});grid.sync();// clear the newly allocated occupancy grids// 对新生成的所有voxel进行初始化，全部清零，numElements表示需要清零的元素数目// 其值为*numSpillingNodes * (128*128*128 / 32u);// 其中*numSpillingNodes表示需要分裂的节点数目，128*128*128表示每个节点对应的立方体数目，32u表示使用int32进行存储uint32_t numElements = *numSpillingNodes * (GRID_NUM_CELLS / 32u);// numElements = 1;// PRINT("clear new occupancy grids, %u elements \n", numElements);grid.sync();processRange(numElements, [&](int cellIndex){int gridIndex = cellIndex / (GRID_NUM_CELLS / 32u);int localCellIndex = cellIndex % (GRID_NUM_CELLS / 32u);Node* spillingNode = spillingNodes[gridIndex];spillingNode->grid->values[localCellIndex] = 0;});
}void expand(Node* root, Point* points, int numPoints, float3 octreeMin, float3 octreeMax, float octreeSize,Node* nodes, Node** spillingNodes, uint32_t* numSpillingNodes,Point* spilledPoints, uint32_t* numSpilledPoints,uint32_t batchIndex
){auto grid = cg::this_grid();for(int i = 0; i < 20; i++){ // 计数-分裂-计数-分裂，交替进行，最多迭代执行20遍grid.sync();bool isFinished = doCounting(root, points, numPoints, octreeMin, octreeMax, octreeSize,nodes, spillingNodes, numSpillingNodes, spilledPoints, numSpilledPoints,batchIndex + 1);grid.sync();// 待分裂节点数为0，跳出循环，expand阶段结束。if(isFinished) break;doSplitting(nodes, spillingNodes, numSpillingNodes);grid.sync();}grid.sync();
}