NavMesh生成核心是可行走区域的平面凸多边形剖分；输入为静态场景几何，输出为互不重叠、覆盖通行地面的凸多边形，需先统一世界空间并依法线朝向、高度范围等语义过滤可行走面。
NavMesh 生成的核心其实是「可行走区域的平面多边形剖分」
不是建模，也不是路径搜索——手写 NavMesh 生成管线，第一步必须明确：输入是静态场景的几何（通常是三角网格或凸体集合），输出是一组互不重叠、覆盖所有可通行地面的凸多边形（常为三角形或凸多边形）。关键判断点在于：哪些面法线接近向上、哪些面高度在角色站立容忍范围内、哪些区域被障碍物遮挡或太窄无法通行。跳过这层语义理解直接“连通图分割”，后续路径查询必然失效。
从输入网格提取可行走面（Ground Face Extraction）
常见错误是直接对整个 OBJ 或 glTF 模型做三角面遍历，却忽略 Z 轴朝向、缩放和坐标系差异。实际操作中需先统一到世界空间，再过滤：
-
abs(dot(face_normal, up_vector)) > 0.9（比如up_vector = {0,1,0}，阈值太低会漏掉缓坡，太高会剔除合理斜坡） -
face_center.y在[min_walkable_y, max_walkable_y]区间内（避免把天花板或地下管道当路面） - 排除面积
的退化三角形（浮点误差易导致后续布尔运算崩溃） - 若输入含多个子网格（如 Unity 的 MeshFilter），需先合并顶点索引空间，否则相邻地块无法连接
用约束 Delaunay 三角剖分合并可行走面（CDT）
单纯合并三角面只是碎片，必须重新剖分为更大、更少、更利于寻路的凸区域。标准做法是：将所有可行走面边缘投影到 XY 平面 → 提取外轮廓 + 内孔洞（如柱子底座）→ 构造带约束的折线集 → 调用 CDT 库（如 Triangle 或 CGAL::Constrained_Delaunay_triangulation_2）。注意：
- 投影前必须保证所有点
z值已归一化（否则孔洞偏移，生成悬空多边形） - 约束边不能有自交或重复端点，否则
Triangle会静默失败并返回空结果 - CDT 输出的是三角形，但 NavMesh 通常需要凸多边形以减少边数；可在 CDT 后做
edge collapse或adjacent triangle merge（仅当共边且两三角形夹角 - 不要用
std::vector<:array>></:array>存原始顶点——改用std::vector<point_2></point_2>（CGAL）或double[2]（Triangle），避免 float 精度引发拓扑错误
构建导航图（Navigation Graph）并导出为运行时结构
生成多边形后，真正影响运行时性能的是邻接关系组织方式。别直接存“每个多边形连哪些邻居”——容易查重、难更新。推荐：
- 为每条多边形边分配唯一
edge_id，用std::unordered_map<uint64_t std::pair>></uint64_t>映射边哈希（如(min_vtx_id ）到左右多边形 ID - 每个 NavMesh 多边形结构至少含：
vertices（局部索引）、area_type（walkable / water / ladder）、flags（是否可跳跃边缘） - 导出时剥离冗余信息：删除未被任何边引用的顶点；合并共线且无中间顶点的边；用
uint16_t存索引（除非顶点数 > 65535） - 如果目标引擎有 runtime rebuild 需求（如破坏地形），必须保留原始可行走面与最终多边形的映射表，否则无法增量更新
最易被忽略的是：没有预留「高度场采样容差」。即使所有面法线达标，角色脚底仍可能因浮点抖动卡进缝隙。务必在生成后对每个多边形做 min_z 和 max_z 扫描，并在运行时查询时加 ±0.1 单位缓冲。
C++免费学习笔记（深入）：立即使用
在学习笔记中，你将探索 C++ 的入门与实战技巧！
