烘培代码在 rcBuildHeightfieldLayers 本质上是为每个tile生成高度上的不同layer 算法的关键是三层循环: for z 轴循环 for x 轴循环 for 高度span 循环 判断span和相邻span的连通性(x/z平面相邻cell) 如果联通, 则标注为同一个layer, 也就是在x/z平面上标注layer, 形成像是互不相交的面包片叠放的样子, 也有有坡度的layer 然后做了一些layer合并处理, 相邻的layer且在x/z平面不重叠且合并后高度差较小的, 可以合并为一个layer 同时layer记录了当前layer的上下高度范围, 边界(坐标系), 边界(体素), heights记录了layer内每个span相对于layer的体素下边界的高度差(体素单位) areas记录了layer内每个span的areas cons记录了layer和span的相邻关系 (注意代码里改了一些变量的命名, 过于简化的变量名不利于新手看懂代码)
(另外, 代码里把y改成了z, recast本身代码里体素遍历都是 x/y平面, 按Unity习惯, 改成了 x/z 平面遍历, y代表高度)
/// See the #rcConfig documentation for more information on the configuration parameters. /// /// @see rcAllocHeightfieldLayerSet, rcCompactHeightfield, rcHeightfieldLayerSet, rcConfig bool rcBuildHeightfieldLayers(rcContext* ctx, rcCompactHeightfield& chf, const int borderSize, const int walkableHeight, rcHeightfieldLayerSet& lset) { rcAssert(ctx); rcScopedTimer timer(ctx, RC_TIMER_BUILD_LAYERS); const int w = chf.width; const int h = chf.height; rcScopedDelete<unsigned char> srcReg((unsigned char*)rcAlloc(sizeof(unsigned char)*chf.spanCount, RC_ALLOC_TEMP)); if (!srcReg) { ctx->log(RC_LOG_ERROR, "rcBuildHeightfieldLayers: Out of memory 'srcReg' (%d).", chf.spanCount); return false; } memset(srcReg,0xff,sizeof(unsigned char)*chf.spanCount); const int nsweeps = chf.width; rcScopedDelete<rcLayerSweepSpan> sweeps((rcLayerSweepSpan*)rcAlloc(sizeof(rcLayerSweepSpan)*nsweeps, RC_ALLOC_TEMP)); if (!sweeps) { ctx->log(RC_LOG_ERROR, "rcBuildHeightfieldLayers: Out of memory 'sweeps' (%d).", nsweeps); return false; } // Partition walkable area into monotone regions. int prevCount[256]; unsigned char regId = 0; //注意这里是三层循环: // for z 平面 // for x 平面 // for y 平面 (高度) // 最内层是对每个y平面的处理, 在每个y层面上根据span在x/z的连接性做region分配和合并, 也就是layer的意义: 按高度分层. 像是切片面包. // 从3d视角看是, 遍历x/z平面的每个cell, 依次检查当前cell与相邻cell在高度上的切片span是否有联通的, 如果有联通就把x/z平面相邻的cell上region赋值为相同id. 让x/z平面形成region.高度上 for (int z = borderSize; z < h-borderSize; ++z) { // prevCount 记录的是当前x轴上的sweep和上一轮x循环(-z方向)的region相连的span数量. memset(prevCount,0,sizeof(int)*regId); //(按行扫描编号), 这个编号在y的循环体内, 也就是每扫描一行x则重置, 扫描完一行后后面会把sweepId变成regionId, 所以重置没问题. unsigned char nowSweepId = 0; for (int x = borderSize; x < w-borderSize; ++x) { const rcCompactCell& c = chf.cells[x+z*w]; for (int i = (int)c.index, ni = (int)(c.index+c.count); i < ni; ++i) { const rcCompactSpan& s = chf.spans[i]; if (chf.areas[i] == RC_NULL_AREA) continue; unsigned char sweepId = 0xff; //(-1, 0)方向如果有连接 // -x if (rcGetCon(s, 0) != RC_NOT_CONNECTED) { const int ax = x + rcGetDirOffsetX(0); const int ay = z + rcGetDirOffsetY(0); const int ai = (int)chf.cells[ax+ay*w].index + rcGetCon(s, 0); //如果连接的不是NULL_AREA且它的sweepId并不是未初始化状态(未设置, 默认值0xff) (sweepId存储在srcReg里) //那么把自己的sweepId也设置为相邻这个span的sweepId,因为是从左到右遍历, 所以-x是刚刚遍历过的,如果连接(x轴相邻的span)且有srcReg, 则设置为相同srcReg if (chf.areas[ai] != RC_NULL_AREA && srcReg[ai] != 0xff) sweepId = srcReg[ai]; } // 如果和左侧相邻span(-1, 0)没有连接, 或者连接的area是NULL, 或者sweepId无效, 则把自己的sweepId设置为新的id. (新分配一个扫描编号) if (sweepId == 0xff) { sweepId = nowSweepId++; sweeps[sweepId].nei = 0xff; sweeps[sweepId].ns = 0; } // 检查完-x方向. 再检查之前扫描过的z方向的邻居 (上一轮扫描过的) // 如果相连且sweepId不是0xff, 则判断是不是刚刚x方向新加的sweepId(还没邻居), 如果是则把z方向的这个邻居设置成自己的邻居 // 如果当前邻居是z方向的这个span, 则把ns++, 把邻居sweepId记录的数量也加1(prevCount[nrSweepId]++) // 如果当前邻居不是z方向这个span, 说明和-z这一行有两个邻居, 则把邻居置为无效值 // (0, -1) x/z平面的下面 -> -z, 注意源码是 x/y 平面, 这里原本注释写的 -y if (rcGetCon(s,3) != RC_NOT_CONNECTED) { const int ax = x + rcGetDirOffsetX(3); const int ay = z + rcGetDirOffsetY(3); const int ai = (int)chf.cells[ax+ay*w].index + rcGetCon(s, 3); const unsigned char nrRegId = srcReg[ai]; if (nrRegId != 0xff) { // Set neighbour when first valid neighbour is encoutered. if (sweeps[sweepId].ns == 0) sweeps[sweepId].nei = nrRegId; if (sweeps[sweepId].nei == nrRegId) { // Update existing neighbour sweeps[sweepId].ns++; prevCount[nrRegId]++; } else { // This is hit if there is nore than one neighbour. // Invalidate the neighbour. sweeps[sweepId].nei = 0xff; } } } srcReg[i] = sweepId; } } // Create unique ID. for (int i = 0; i < nowSweepId; ++i) { /// 如果邻居设置了, 而且邻居连接我的数量和我数量相同则说明我们是完全相临的, 可以合并, 否则意味着我的邻居可能还有其他sweepId和他相连. /// 类似下面, A先扫描完, 形成了一个完整连续的region=1, 再遍历B时, prevCount[1] = 4, (A行3个1和1个2), 但是sweeps[1] = 3, (B行3个1) /// 所以此时B行里的1和A行里的1不能合并了. 要给B行的1分配新的regionId /// /// <--- -x方向(左) /// | /// B: [1] [1] [1] [2] | -> 此处的1, 2都还是sweepId, 代表从左到右的扫描分割序号. /// A: [1] [1] [1] [1] [1] | -> 此时的1已经是regionId了. /// -z方向(下) /// /// /// B: [1] [1] | /// A: [1] [1] [1] | -> 这种情况可以合并, prevCount[A1].nei = 2, sweeps[B1].ns = 2 /// /// B: [1] [1] [1] [1] | /// A: [1] [1] [1] | -> 这种情况也可以合并, prevCount[A1].nei = 3, sweeps[B1].ns = 3, (B第四个[1]因为和下面无连接, 所以两边都不计数) /// /// If the neighbour is set and there is only one continuous connection to it, /// the sweep will be merged with the previous one, else new region is created. if (sweeps[i].nei != 0xff && prevCount[sweeps[i].nei] == (int)sweeps[i].ns) { sweeps[i].id = sweeps[i].nei; } else { if (regId == 255) { ctx->log(RC_LOG_ERROR, "rcBuildHeightfieldLayers: Region ID overflow."); return false; } sweeps[i].id = regId++; } } // 之前srcReg里记录的是sweepId, 现在改回regionId // Remap local sweep ids to region ids. for (int x = borderSize; x < w-borderSize; ++x) { const rcCompactCell& c = chf.cells[x+z*w]; for (int i = (int)c.index, ni = (int)(c.index+c.count); i < ni; ++i) { if (srcReg[i] != 0xff) srcReg[i] = sweeps[srcReg[i]].id; } } } // Allocate and init layer regions. const int nregs = (int)regId; rcScopedDelete<rcLayerRegion> regs((rcLayerRegion*)rcAlloc(sizeof(rcLayerRegion)*nregs, RC_ALLOC_TEMP)); if (!regs) { ctx->log(RC_LOG_ERROR, "rcBuildHeightfieldLayers: Out of memory 'regs' (%d).", nregs); return false; } memset(regs, 0, sizeof(rcLayerRegion)*nregs); for (int i = 0; i < nregs; ++i) { regs[i].layerId = 0xff; regs[i].ymin = 0xffff; regs[i].ymax = 0; } // Find region neighbours and overlapping regions. for (int z = 0; z < h; ++z) //遍历 z { for (int x = 0; x < w; ++x) //遍历 x/z 平面 { const rcCompactCell& c = chf.cells[x+z*w]; //记录y方向的区域id和数量 unsigned char lregs[RC_MAX_LAYERS]; int nlregs = 0; for (int i = (int)c.index, ni = (int)(c.index+c.count); i < ni; ++i) //遍历 y 方向 span { const rcCompactSpan& s = chf.spans[i]; const unsigned char regionId = srcReg[i]; if (regionId == 0xff) continue; //跳过没有区域的span regs[regionId].ymin = rcMin(regs[regionId].ymin, s.y); regs[regionId].ymax = rcMax(regs[regionId].ymax, s.y); // Collect all region layers. if (nlregs < RC_MAX_LAYERS) lregs[nlregs++] = regionId; // Update neighbours // 遍历4个方向, 记录邻居区域信息 (和自己不同区域) for (int dir = 0; dir < 4; ++dir) { if (rcGetCon(s, dir) != RC_NOT_CONNECTED) { const int ax = x + rcGetDirOffsetX(dir); const int ay = z + rcGetDirOffsetY(dir); const int ai = (int)chf.cells[ax+ay*w].index + rcGetCon(s, dir); const unsigned char nrReg = srcReg[ai]; if (nrReg != 0xff && nrReg != regionId) //邻居的region 和 自己不一样 { // Don't check return value -- if we cannot add the neighbor // it will just cause a few more regions to be created, which // is fine. addUnique(regs[regionId].neis, regs[regionId].nneis, RC_MAX_NEIS, nrReg); } } } } // 两层遍历高度(y)方向的区域 (两两检查), // Update overlapping regions. for (int i = 0; i < nlregs-1; ++i) { for (int j = i+1; j < nlregs; ++j) { if (lregs[i] != lregs[j]) { rcLayerRegion& ri = regs[lregs[i]]; rcLayerRegion& rj = regs[lregs[j]]; //在两个region的layers里记录该region在x/z平面上重叠的其他高度的regionId. 用于索引高度上的不同层. if (!addUnique(ri.layers, ri.nlayers, RC_MAX_LAYERS, lregs[j]) || !addUnique(rj.layers, rj.nlayers, RC_MAX_LAYERS, lregs[i])) { ctx->log(RC_LOG_ERROR, "rcBuildHeightfieldLayers: layer overflow (too many overlapping walkable platforms). Try increasing RC_MAX_LAYERS."); return false; } } } } } } // Create 2D layers from regions. unsigned char layerId = 0; static const int MAX_STACK = 64; unsigned char stack[MAX_STACK]; int nstack = 0; for (int i = 0; i < nregs; ++i) { rcLayerRegion& root = regs[i]; // Skip already visited. if (root.layerId != 0xff) continue; // Start search. // 分配 layerId root.layerId = layerId; root.base = 1; nstack = 0; stack[nstack++] = (unsigned char)i; //region序号入栈 while (nstack) { // Pop front rcLayerRegion& reg = regs[stack[0]]; nstack--; for (int j = 0; j < nstack; ++j) //移除stack第一个元素. stack[j] = stack[j+1]; const int nneis = (int)reg.nneis; for (int j = 0; j < nneis; ++j) { const unsigned char nei = reg.neis[j]; rcLayerRegion& nrReg = regs[nei]; // Skip already visited. if (nrReg.layerId != 0xff) continue; // Skip if the neighbour is overlapping root region. // 跳过 邻居是x/z重叠的不同高度的region if (contains(root.layers, root.nlayers, nei)) continue; // Skip if the height range would become too large. // 如果两个区域加起来的高度落差太大 跳过 (因为高度差不大的情况下会合并layer, 但是合并太多后会导致layer上下表面的高差越来越大, 这时候就要打断合并了) const int ymin = rcMin(root.ymin, nrReg.ymin); const int ymax = rcMax(root.ymax, nrReg.ymax); if ((ymax - ymin) >= 255) continue; if (nstack < MAX_STACK) { // Deepen 邻居入栈 stack[nstack++] = (unsigned char)nei; // Mark layer id // 将邻居的layerId设置为自己的layerId. 合并成一个layer nrReg.layerId = layerId; // Merge current layers to root. // 将邻居的高度layers也合并到自己的layers, (合并成一个layer了, 高度重叠区域信息也要合并). for (int k = 0; k < nrReg.nlayers; ++k) { if (!addUnique(root.layers, root.nlayers, RC_MAX_LAYERS, nrReg.layers[k])) { ctx->log(RC_LOG_ERROR, "rcBuildHeightfieldLayers: layer overflow (too many overlapping walkable platforms). Try increasing RC_MAX_LAYERS."); return false; } } root.ymin = rcMin(root.ymin, nrReg.ymin); // 更新合并后的layer上下表面. root.ymax = rcMax(root.ymax, nrReg.ymax); } } } layerId++; } // Merge non-overlapping regions that are close in height. // 合并高度上差异不大, 而且没有重叠的区域, 楼梯, 坡等 const unsigned short mergeHeight = (unsigned short)walkableHeight * 4; for (int i = 0; i < nregs; ++i) { rcLayerRegion& ri = regs[i]; if (!ri.base) continue; //只需要查询layer的 base region unsigned char newId = ri.layerId; for (;;) { unsigned char oldId = 0xff; for (int j = 0; j < nregs; ++j) //双层遍历 region 两两计算 { if (i == j) continue; rcLayerRegion& rj = regs[j]; if (!rj.base) continue; // Skip if the regions are not close to each other. // 两个区域的上下表面+合并高差 不重叠, 则无法合并 if (!overlapRange(ri.ymin,ri.ymax+mergeHeight, rj.ymin,rj.ymax+mergeHeight)) continue; // Skip if the height range would become too large. const int ymin = rcMin(ri.ymin, rj.ymin); const int ymax = rcMax(ri.ymax, rj.ymax); if ((ymax - ymin) >= 255) //合并后高差太大 跳过 continue; // Make sure that there is no overlap when merging 'ri' and 'rj'. bool overlap = false; // Iterate over all regions which have the same layerId as 'rj' for (int k = 0; k < nregs; ++k) { if (regs[k].layerId != rj.layerId) continue; // Check if region 'k' is overlapping region 'ri' // Index to 'regs' is the same as region id. // 和j相同layerId的区域, 判断是否和ri有重叠, 如果有重叠说明合并regionI 和 regionJ 后会导致用一个region在x/z平面出现重叠. 所以此时要break. 不能合并 if (contains(ri.layers,ri.nlayers, (unsigned char)k)) { overlap = true; break; } } // Cannot merge of regions overlap. if (overlap) continue; // Can merge i and j. oldId = rj.layerId; break; } // Could not find anything to merge with, stop. if (oldId == 0xff) break; // Merge for (int j = 0; j < nregs; ++j) { rcLayerRegion& rj = regs[j]; if (rj.layerId == oldId) { rj.base = 0; // Remap layerIds. rj.layerId = newId; // Add overlaid layers from 'rj' to 'ri'. // 合并之后, 同样也需要 将邻居的高度layers也合并到自己的layers, (合并成一个layer了, 高度重叠区域信息也要合并). for (int k = 0; k < rj.nlayers; ++k) { if (!addUnique(ri.layers, ri.nlayers, RC_MAX_LAYERS, rj.layers[k])) { ctx->log(RC_LOG_ERROR, "rcBuildHeightfieldLayers: layer overflow (too many overlapping walkable platforms). Try increasing RC_MAX_LAYERS."); return false; } } // Update height bounds. ri.ymin = rcMin(ri.ymin, rj.ymin); // 更新合并后的layer上下表面. ri.ymax = rcMax(ri.ymax, rj.ymax); } } } } // 合并后layerId不连续了, 所以这里要重新remap下, 保持layerId连续 // Compact layerIds unsigned char remap[256]; memset(remap, 0, 256); // Find number of unique layers. layerId = 0; for (int i = 0; i < nregs; ++i) remap[regs[i].layerId] = 1; for (int oldLayerId = 0; oldLayerId < 256; ++oldLayerId) { if (remap[oldLayerId]) remap[oldLayerId] = layerId++; else remap[oldLayerId] = 0xff; } // Remap ids. for (int i = 0; i < nregs; ++i) regs[i].layerId = remap[regs[i].layerId]; //从remap里查询oldLayerId对应的新layerId, 并赋值 // No layers, return empty. if (layerId == 0) return true; // Create layers. rcAssert(lset.layers == 0); const int lw = w - borderSize*2; const int lh = h - borderSize*2; // Build contracted bbox for layers. float bmin[3], bmax[3]; rcVcopy(bmin, chf.bmin); rcVcopy(bmax, chf.bmax); bmin[0] += borderSize*chf.cs; bmin[2] += borderSize*chf.cs; bmax[0] -= borderSize*chf.cs; bmax[2] -= borderSize*chf.cs; lset.nlayers = (int)layerId; lset.layers = (rcHeightfieldLayer*)rcAlloc(sizeof(rcHeightfieldLayer)*lset.nlayers, RC_ALLOC_PERM); if (!lset.layers) { ctx->log(RC_LOG_ERROR, "rcBuildHeightfieldLayers: Out of memory 'layers' (%d).", lset.nlayers); return false; } memset(lset.layers, 0, sizeof(rcHeightfieldLayer)*lset.nlayers); // Store layers. for (int i = 0; i < lset.nlayers; ++i) { unsigned char curId = (unsigned char)i; rcHeightfieldLayer* layer = &lset.layers[curId]; const int gridSize = sizeof(unsigned char)*lw*lh; //体素x/z空间size, 二维数组长度 layer->heights = (unsigned char*)rcAlloc(gridSize, RC_ALLOC_PERM); if (!layer->heights) { ctx->log(RC_LOG_ERROR, "rcBuildHeightfieldLayers: Out of memory 'heights' (%d).", gridSize); return false; } memset(layer->heights, 0xff, gridSize); layer->areas = (unsigned char*)rcAlloc(gridSize, RC_ALLOC_PERM); if (!layer->areas) { ctx->log(RC_LOG_ERROR, "rcBuildHeightfieldLayers: Out of memory 'areas' (%d).", gridSize); return false; } memset(layer->areas, 0, gridSize); layer->cons = (unsigned char*)rcAlloc(gridSize, RC_ALLOC_PERM); if (!layer->cons) { ctx->log(RC_LOG_ERROR, "rcBuildHeightfieldLayers: Out of memory 'cons' (%d).", gridSize); return false; } memset(layer->cons, 0, gridSize); // Find layer height bounds. int hmin = 0, hmax = 0; //上下表面高度 (体素单位) for (int j = 0; j < nregs; ++j) { if (regs[j].base && regs[j].layerId == curId) { hmin = (int)regs[j].ymin; hmax = (int)regs[j].ymax; //此处应该可以break ? } } layer->width = lw; layer->height = lh; layer->cs = chf.cs; layer->ch = chf.ch; // Adjust the bbox to fit the heightfield. rcVcopy(layer->bmin, bmin); rcVcopy(layer->bmax, bmax); layer->bmin[1] = bmin[1] + hmin*chf.ch; //体素高度转坐标高度 layer->bmax[1] = bmin[1] + hmax*chf.ch; layer->hmin = hmin; layer->hmax = hmax; // Update usable data region. layer->minx = layer->width; layer->maxx = 0; layer->miny = layer->height; layer->maxy = 0; // Copy height and area from compact heightfield. for (int z = 0; z < lh; ++z) { for (int x = 0; x < lw; ++x) { const int cx = borderSize+x; const int cz = borderSize+z; const rcCompactCell& c = chf.cells[cx+cz*w]; for (int j = (int)c.index, nj = (int)(c.index+c.count); j < nj; ++j) { const rcCompactSpan& span = chf.spans[j]; // Skip unassigned regions. if (srcReg[j] == 0xff) continue; // Skip of does nto belong to current layer. unsigned char lid = regs[srcReg[j]].layerId; if (lid != curId) continue; // Update data bounds. layer->minx = rcMin(layer->minx, x); layer->maxx = rcMax(layer->maxx, x); layer->miny = rcMin(layer->miny, z); layer->maxy = rcMax(layer->maxy, z); // Store height and area type. const int idx = x+z*lw; layer->heights[idx] = (unsigned char)(span.y - hmin); layer->areas[idx] = chf.areas[j]; // Check connection. unsigned char portal = 0; unsigned char con = 0; for (int dir = 0; dir < 4; ++dir) { if (rcGetCon(span, dir) != RC_NOT_CONNECTED) { const int ax = cx + rcGetDirOffsetX(dir); const int ay = cz + rcGetDirOffsetY(dir); const int ai = (int)chf.cells[ax+ay*w].index + rcGetCon(span, dir); unsigned char alid = srcReg[ai] != 0xff ? regs[srcReg[ai]].layerId : 0xff; // Portal mask if (chf.areas[ai] != RC_NULL_AREA && lid != alid) { portal |= (unsigned char)(1<<dir); // Update height so that it matches on both sides of the portal. const rcCompactSpan& as = chf.spans[ai]; if (as.y > hmin) layer->heights[idx] = rcMax(layer->heights[idx], (unsigned char)(as.y - hmin)); } // Valid connection mask // 相邻的同layer的span连接信息记录在 cons的低4位. (上下左右) if (chf.areas[ai] != RC_NULL_AREA && lid == alid) { const int nx = ax - borderSize; const int ny = ay - borderSize; if (nx >= 0 && ny >= 0 && nx < lw && ny < lh) con |= (unsigned char)(1<<dir); } } } layer->cons[idx] = (portal << 4) | con; //相邻的不同layer的信息记录在cons的高4位. } } } if (layer->minx > layer->maxx) layer->minx = layer->maxx = 0; if (layer->miny > layer->maxy) layer->miny = layer->maxy = 0; } return true; }
有两个文档也可以看一下, 看懂了上面的代码再去看文章就清楚多了. 如果不好理解代码. 可以结合文章图例一起看. 代码注释已经非常详细了, 只是没有图例
https://blog.csdn.net/zstu_zy/article/details/97247013
https ://www.jianshu.com/p/f6cd9b7696f6
标签:rcBuildHeightfieldLayers,layer,const,int,unsigned,Sample,++,recastnavigation,RC From: https://www.cnblogs.com/wmalloc/p/18260261