从零开始学习导航网格#4 recast代码分析之solomesh(上)

温馨提示：
由于没有系统严谨的学习过相关理论，所以我在描述一些概念的时候可能会自己造一些名词，也不保证我的理解就是正确的。希望各位带哥海涵。
另外整个项目的代码量很大，算法细节也很多，全部展开分析是一个浩大的工程，我应该没有足够的时间精力来做这件事，只能记录下主流程以及我觉得需要拆解的点。
再有，为了能够顺畅的理解项目的思路和代码，可能需要学习一些基础的计算几何和图形学的知识，我在这篇文章中会有相应的整理

///正文开始
当一次寻路发生的时候，我们一般需要知道两个信息：
1.地图上哪些区域是可行走的
2.这些可行走区域之间的联通关系是什么样的
从这个角度来看，导航网格算是一种数据结构，用某种方式来描述地图的上述两种信息
在实际应用中，导航网格是以邻接的凸多边形集合来表示的
在独立的凸多边形内部，保证任意两点直线可达

而寻路关键是通过算法找到一组多边形，这组多边形满足这样的条件：
第一个和最后一个多边形包含了寻路的起始点和终点
中间的多边形负责所有多边形的连通性

因此导航网格寻路可以粗略的分成两大部分：
1.将3D场景转化为邻接的凸多边形集合
2.在凸多边形集合上寻路

在RecastNavigation项目中，
Recast工程对应第一部分
Detour工程对应第二部分
而RecastDemo是一个GUI程序，可以直观的验证导航网格的生成和寻路的过程

配置参数 struct rcConfig

如何输入一个3D场景 class InputGeom

生成导航网格可以从bool Sample_SoloMesh::handleBuild()这个函数开始看起（也就是在demo程序的界面上点击“build"之后的回调函数）

Step 1. Initialize build config.

根据配置初始化参数，并计算出网格的大小
其中最重要的参数是这几个：
场景尺寸（包围盒）
所有的的顶点（顶点个数&&顶点坐标集合）
所有的三角形面（三角形个数&&三角形集合）
另外这里的半径已经被转换为以体素大小作为单位
m_cfg.walkableRadius = (int)ceilf(m_agentRadius / m_cfg.cs);

Step 2. Rasterize input polygon soup.

体素化
体素化的概念在第一篇中已经有所讲述，这里再提一下，可以用2D图形的光栅化最类比理解，其实就是为了找到3维空间中的三角形面与那些体素盒子相交

光栅化

具体步骤：

a.标记所有三角形面是否可行走

rcMarkWalkableTriangles计算所有三角形的法线，与最大可行走角度做比较，并将结果存入m_triareas[]这个标记数组中

b.创建高度场

c.光栅化三角形面

rcRasterizeTriangles这个函数是重点，它主要做了这些事：
遍历所有三角形，调用rasterizeTri，将每个初始的三角形面转换成空间内的体素集
注意这里每个三角形之间是相互独立的，也许某一组三角形可以围成了一个多面体，但这里已经不再有"多面体"的概念，而是将地图的信息全部拆解到三角形面，再进一步拆解到体素盒子

1.找到三角形的AABB（注意是3维空间内的三角形）
2.计算三角形的高度（y轴）范围
3.按xz坐标网格切割三角形
俯视图如下（注意只是俯视图，实际上应该是3维空间的切割）

切割俯视图

在分割三角形时代码中有这样一个数组

float buf[7*3*4];
float *in = buf, *inrow = buf+7*3, *p1 = inrow+7*3, *p2 = p1+7*3;

解释一下7 3 4这三个数字
4：有4份对应的数据，用来存放输入的图形和分割后的图形
3：对应一个顶点的x y z 坐标值
7：一个三角形在分割时会被切4刀（即一个正方形格子的4条边），所以切完最多可能会变成一个7边形，也就是最多需要存7个顶点

这里有一个重要的函数:
用一条直线将一个凸多边形分成两个凸多边形

static void dividePoly(const float* in, int nin,
                      float* out1, int* nout1,
                      float* out2, int* nout2,
                      float x, int axis)

参数axis取值[0,2],对应表示x,y,z轴
枚举所有边，判断边的顶点坐标是在轴的同侧还是不同侧，
若是同侧则将两个顶点都加入对应的新多边形
若是在不同侧，则新生成一个分割点，将分割点（复制成两份）加入两个新多边形

4.找到切割后的多边形对应的span,根据对应的三角形面的可行走情况设置span的可行走属性，并把这个span根据xz的投影坐标添加入到高度场中

这里要特别说明两点
1.span在合并的时候，如果同一个span，有的面是可行走，有的是不可行走，在合并之后会变成可行走

// Merge flags.
if (rcAbs((int)s->smax - (int)cur->smax) <= flagMergeThr)
    s->area = rcMax(s->area, cur->area);

2.如果一个面是完全垂直于xz平面且与x轴或者z轴平行，在切割时会怎么样
不妨假设Xmax=Xmin,这时在x轴方向的切割只有一次即x=Xmax，并且dividePoly会判定所有三角形的边都在分割线的同一侧，分割的结果是一个原三角形和一个空集合