Recast 学习记录之一：三角形光栅化

序

本文根据 Sample_SoloMesh::handleBuild 中的 Step 2. Rasterize input polygon soup 进行源码解析。

rcCreateHeightfield 创建高度场

HeightField 和 span 的概念可以看看 CritterAI 对高度场的介绍 。

其实就是将模型按照包围盒确定的大小，划分为 cell 网格，每一个网格都使用链表保存垂直方向上的所有 cell。y 轴上连续的 cell 被合并为一个 span，称为 solid span。

rcMarkWalkableTriangles 标记可行走三角形

参数 walkableSlopeAngle 用于指定倾斜角度小于多少的平面才是可以行走的，RecastDemo 中使用的是 45°。

代码中 walkableThr 由 cosf(walkableSlopeAngle/180.0f*RC_PI) 计算得到，然后计算出三角形的单位法线向量 norm，最后用 if (norm[1] > walkableThr) 判断三角形面是否可以行走。推导过程如下：

已知三角形逆时针顺序三个点的坐标，我们可以得到同一点出发的两个向量，叉乘可以得到三角形的法线向量。设与 x-z 轴平面的夹角为，那么其在 y 轴上的分量即可求得。如果是个单位向量，那么可得。

又设三角形平面与 x-z 轴平面的夹角为，那么可得。又由三角函数公式可得，。

然后我们就能够算出一个平面的倾斜角度是否小于 walkableSlopeAngle 了。

显然当时，，此时三角形面可以行走。

又因为三角形的顶点是有顺序的，所以一个给定的三角形面可以根据其法线向量的 y 轴分量正负值确定其是正面朝上还是朝下。对于面朝下的那些三角形，计算得出的法线向量 y 轴分量会小于 0，此时其三角形表面也是不可行走的。

至此，就用三角形单位法线向量的 y 轴分量和求出了三角形平面是否满足倾斜角度的要求。

图画的不太好，将就看吧。。。

rcRasterizeTriangles 将三角形进行光栅化处理

将三角形做了行走标记处理后，下一步就要将三角形进行光栅化处理了。

这一步的核心是要判断三维空间里，一个三角形面与哪些格子相交。如果三角形面与一个格子有任意相交的地方，则需要将这个格子进行体素化处理。

Recast 中使用 rcRasterizeTriangles 函数来处理三角形的光栅化，函数本身只是遍历所有的三角形，其重点是 rasterizeTri（单个三角形的光栅化）及其调用的 dividePoly（将多边形沿轴线切割为两个多边形）这两个函数。

rasterizeTri 中通过两层 for 循环调用 dividePoly 实现先 z 轴后 x 轴的两方向切割，逐步在 x-z 轴上将三角形切割成一个一个 cellSize 大小的块。

第一次外层 for 循环在 z 轴上进行切割后如图，这时候我们得到了一个 z 轴上最大长度为 cellSize 的多边形：

然后内层 for 循环在 x 轴上继续切割，得到多边形：

然后我们就可以遍历的四个顶点，找出其 y 轴上的最小、最大值，就可以作为 span 的高度，将其添加到高度场中。

接着继续切割，直到整个三角形被完全切割完毕：

dividePoly 将一个凸多边形，按轴线切割为两个凸多边形

dividePoly 的参数 axis 用于指明要从哪个轴上进行切割，x 为轴上要进行切割的坐标。

函数进行切割的步骤如下：

1. 遍历多边形的每一条边 j-i；
2. 判断边的两个顶点与切割线的位置关系；
3. 如果两个顶点一左一右或者其中一个在切割线上，那么在与切割线的交点处生成一个新的顶点，将其同时添加到 out1 和 out2 两个多边形中。对于 i 点，根据其在切割线左右两种情况，将其添加到 out1 或者 out2 中；
4. 如果两个顶点都在切割线的同一边，那么将点 i 添加到其与切割线左右关系对应的多边形中；
5. 如果两个顶点都在切割线上，那么将点 i 同时添加到 out1 和 out2 两个多边形中。

举个栗子，有如下的三角形和切割线：

首先遍历边 AB，其两个端点在切割线的两边。这种情况增加点 D，同时添加到 out1 和 out2 中，然后将 B 添加到 out1 中，此时 out1{DB}, out2{D}。

然后遍历边 BC，其两个端点同样在切割线的两边。增加点 E，同时添加到 out1 和 out2 中，然后将 C 添加到 out2 中，此时 out1{DBE}, out2{DEC}。

最后遍历 CA，因为两个端点都在切割线的右边，所以此时将 A 添加到 out2 中，得到 out1{DBE}, out2{DECA}。遍历完毕，两个多边形都切割了出来。

addSpan solid span 的添加与合并

addSpan 用于将新添加的 solid span 根据其高度插入到有序链表中的合适位置，逻辑很直白。

需要注意的是，如果新添加的 span 与老的 span 存在重叠，将老的 span 合并到新 span 里：

1. 如果两个 span 的顶部高度差在合并范围 flagMergeThr 以内，则使用两个 span 中 area 较大的值（其实就是 RC_WALKABLE_AREA 了）。

2. 如果两个 span 的顶部高度差在合并范围 flagMergeThr 以外，则使用新增 span 的 area 值。

上述的流程结束后，Recast 就将由三角形面构成的模型转换为了由 solid span 构成的体素空间——高度场，并且每一个 span 上都标记了其表面是否可供行走。如果止于这一步，再依靠 walkableClimb 进行格子的邻接判断，那么我们就已经得到了一个基于格子的导航网格。