从体素到路径：手把手用C++实现一个简化版的Recast导航网格生成器

从体素到路径：手把手用C++实现一个简化版的Recast导航网格生成器

1. 导航网格生成的核心原理

在现代游戏开发和机器人路径规划中，导航网格（NavMesh）已经成为场景寻路的黄金标准。与传统的路点系统相比，导航网格能够更精确地描述可行走区域，支持动态避障，并提供更自然的移动路径。Recast作为开源的导航网格生成库，其核心思想是将3D场景体素化，通过一系列算法处理最终生成凸多边形组成的导航表面。

理解Recast的工作原理需要把握三个关键视角：空间离散化、区域连通性和几何简化。空间离散化通过体素化将连续3D空间转换为离散的高度场；区域连通性分析确保可行走区域的连续性；几何简化则将复杂的体素数据转化为简洁的凸多边形网格。这种从微观到宏观的处理流程，既保证了导航精度，又优化了运行时性能。

2. 基础数据结构设计

2.1 高度场表示

struct Heightfield { int width; // x轴方向体素数 int depth; // z轴方向体素数 float cellSize; // 体素底面边长 float cellHeight; // 体素高度 Span** spans; // 各列高度区间链表 };

高度场是场景的离散化表示，每个网格列维护一个高度区间（Span）链表：

struct Span { int smin, smax; // 高度区间上下界 int area; // 区域标识（可行走/不可行走） Span* next; // 下一高度区间 };

2.2 体素化实现

体素化过程将三角形网格转换为高度场表示，核心是计算三角形与体素列的相交：

void rasterizeTriangle(Heightfield& hf, const Vector3& v0, const Vector3& v1, const Vector3& v2) { // 计算三角形包围盒的体素范围 int minX = clamp((int)((min3(v0.x,v1.x,v2.x)-hf.bmin[0])/hf.cs), 0, hf.width-1); int maxX = clamp((int)((max3(v0.x,v1.x,v2.x)-hf.bmin[0])/hf.cs), 0, hf.width-1); // 遍历每个可能相交的体素列 for (int z = minZ; z <= maxZ; ++z) { for (int x = minX; x <= maxX; ++x) { // 计算三角形在当前体素列的高度投影范围 float spanMin, spanMax; if (calcTriangleHeightSpan(v0, v1, v2, x, z, spanMin, spanMax)) { addSpan(hf, x, z, spanMin, spanMax); } } } }

3. 区域生成算法

3.1 分水岭算法简化实现

原始分水岭算法计算复杂度较高，我们可以采用简化版的区域生长算法：

void buildRegions(Heightfield& hf) { int regionId = 1; std::vector<Int2> stack; // 遍历所有高度区间 for (int z = 0; z < hf.depth; ++z) { for (int x = 0; x < hf.width; ++x) { for (Span* s = hf.spans[x + z*hf.width]; s; s = s->next) { if (s->area == WALKABLE && s->region == 0) { // 开始新区域生长 stack.emplace_back(x, z); s->region = regionId; while (!stack.empty()) { Int2 p = stack.back(); stack.pop_back(); // 检查4-连通邻居 const int nx[4] = {p.x-1, p.x+1, p.x, p.x}; const int nz[4] = {p.z, p.z, p.z-1, p.z+1}; for (int i = 0; i < 4; ++i) { if (nx[i] < 0 || nz[i] < 0 || nx[i] >= hf.width || nz[i] >= hf.depth) continue; Span* ns = findSpanAt(hf, nx[i], nz[i], s->smin); if (ns && ns->area == WALKABLE && ns->region == 0) { ns->region = regionId; stack.emplace_back(nx[i], nz[i]); } } } regionId++; } } } } }

3.2 区域过滤策略

4. 轮廓生成与简化

4.1 轮廓提取算法

void buildContours(const Heightfield& hf, ContourSet& cs) { for (int z = 0; z < hf.depth; ++z) { for (int x = 0; x < hf.width; ++x) { for (Span* s = hf.spans[x + z*hf.width]; s; s = s->next) { if (s->region == 0) continue; // 检查四个方向的邻居 for (int dir = 0; dir < 4; ++dir) { if (isRegionBoundary(hf, x, z, s, dir)) { traceContour(hf, x, z, s, dir, cs); } } } } } }

4.2 轮廓简化算法

采用Douglas-Peucker算法的变种进行轮廓简化：

void simplifyContour(Contour& contour, float maxError) { std::vector<bool> keep(contour.size(), false); keep[0] = keep.back() = true; // 递归简化曲线段 simplifySegment(contour, 0, contour.size()-1, maxError, keep); // 构建简化后的轮廓 Contour simplified; for (size_t i = 0; i < contour.size(); ++i) { if (keep[i]) simplified.push_back(contour[i]); } contour = std::move(simplified); }

5. 凸多边形生成

5.1 三角剖分实现

void triangulateContour(const Contour& contour, Mesh& mesh) { // 耳切法三角剖分 std::list<int> indices(contour.begin(), contour.end()); while (indices.size() > 3) { auto it = findEarVertex(indices, contour); if (it == indices.end()) break; // 添加三角形 auto prev = (it == indices.begin()) ? std::prev(indices.end()) : std::prev(it); auto next = std::next(it); if (next == indices.end()) next = indices.begin(); mesh.addTriangle(contour[*prev], contour[*it], contour[*next]); indices.erase(it); } // 添加最后一个三角形 if (indices.size() == 3) { mesh.addTriangle(contour[indices.front()], contour[*(std::next(indices.begin()))], contour[indices.back()]); } }

5.2 凸多边形合并

合并相邻三角形形成更大的凸多边形：

void mergePolygons(Mesh& mesh, int maxVertsPerPoly) { bool merged = true; while (merged) { merged = false; // 寻找最佳合并对 int bestPair[2] = {-1, -1}; float bestScore = 0; for (int i = 0; i < mesh.polyCount; ++i) { for (int j = i+1; j < mesh.polyCount; ++j) { if (canMerge(mesh, i, j, maxVertsPerPoly)) { float score = calcMergeScore(mesh, i, j); if (score > bestScore) { bestScore = score; bestPair[0] = i; bestPair[1] = j; } } } } // 执行合并 if (bestPair[0] != -1) { mergePolys(mesh, bestPair[0], bestPair[1]); merged = true; } } }

6. 性能优化技巧

6.1 空间划分加速

struct TileCache { struct Tile { int x, z; std::vector<Span> spans; }; std::vector<Tile> tiles; int tileSize = 32; // 每块Tile包含的体素数 void build(const Heightfield& hf) { int tileW = (hf.width + tileSize - 1) / tileSize; int tileH = (hf.depth + tileSize - 1) / tileSize; tiles.resize(tileW * tileH); // 并行处理每个Tile #pragma omp parallel for for (int z = 0; z < tileH; ++z) { for (int x = 0; x < tileW; ++x) { processTile(hf, x, z); } } } };

6.2 可视化调试方法

实现简单的网格可视化帮助调试：

void debugDrawHeightfield(const Heightfield& hf) { for (int z = 0; z < hf.depth; ++z) { for (int x = 0; x < hf.width; ++x) { for (Span* s = hf.spans[x + z*hf.width]; s; s = s->next) { // 绘制体素框 drawBox(x*hf.cellSize, s->smin*hf.cellHeight, z*hf.cellSize, (x+1)*hf.cellSize, s->smax*hf.cellHeight, (z+1)*hf.cellSize, s->area == WALKABLE ? GREEN : RED); // 标记区域ID if (s->region > 0) { drawText((x+0.5f)*hf.cellSize, (s->smin+0.5f)*hf.cellHeight, (z+0.5f)*hf.cellSize, std::to_string(s->region)); } } } } }