溫馨提示：
由于沒有系統(tǒng)嚴(yán)謹(jǐn)?shù)膶W(xué)習(xí)過相關(guān)理論，所以我在描述一些概念的時(shí)候可能會自己造一些名詞，也不保證我的理解就是正確的。希望各位帶哥海涵。
另外整個(gè)項(xiàng)目的代碼量很大，算法細(xì)節(jié)也很多，全部展開分析是一個(gè)浩大的工程，我應(yīng)該沒有足夠的時(shí)間精力來做這件事，只能記錄下主流程以及我覺得需要拆解的點(diǎn)。
再有，為了能夠順暢的理解項(xiàng)目的思路和代碼，可能需要學(xué)習(xí)一些基礎(chǔ)的計(jì)算幾何和圖形學(xué)的知識，我在這篇文章中會有相應(yīng)的整理

///正文開始
當(dāng)一次尋路發(fā)生的時(shí)候，我們一般需要知道兩個(gè)信息：
1.地圖上哪些區(qū)域是可行走的
2.這些可行走區(qū)域之間的聯(lián)通關(guān)系是什么樣的
從這個(gè)角度來看，導(dǎo)航網(wǎng)格算是一種數(shù)據(jù)結(jié)構(gòu)，用某種方式來描述地圖的上述兩種信息
在實(shí)際應(yīng)用中，導(dǎo)航網(wǎng)格是以鄰接的凸多邊形集合來表示的
在獨(dú)立的凸多邊形內(nèi)部，保證任意兩點(diǎn)直線可達(dá)

而尋路關(guān)鍵是通過算法找到一組多邊形，這組多邊形滿足這樣的條件：
第一個(gè)和最后一個(gè)多邊形包含了尋路的起始點(diǎn)和終點(diǎn)
中間的多邊形負(fù)責(zé)所有多邊形的連通性

因此導(dǎo)航網(wǎng)格尋路可以粗略的分成兩大部分：
1.將3D場景轉(zhuǎn)化為鄰接的凸多邊形集合
2.在凸多邊形集合上尋路

在RecastNavigation項(xiàng)目中，
Recast工程對應(yīng)第一部分
Detour工程對應(yīng)第二部分
而RecastDemo是一個(gè)GUI程序，可以直觀的驗(yàn)證導(dǎo)航網(wǎng)格的生成和尋路的過程

配置參數(shù) struct rcConfig

如何輸入一個(gè)3D場景 class InputGeom

生成導(dǎo)航網(wǎng)格可以從bool Sample_SoloMesh::handleBuild()這個(gè)函數(shù)開始看起（也就是在demo程序的界面上點(diǎn)擊“build"之后的回調(diào)函數(shù)）

Step 1. Initialize build config.

根據(jù)配置初始化參數(shù)，并計(jì)算出網(wǎng)格的大小
其中最重要的參數(shù)是這幾個(gè)：
場景尺寸（包圍盒）
所有的的頂點(diǎn)（頂點(diǎn)個(gè)數(shù)&&頂點(diǎn)坐標(biāo)集合）
所有的三角形面（三角形個(gè)數(shù)&&三角形集合）
另外這里的半徑已經(jīng)被轉(zhuǎn)換為以體素大小作為單位
m_cfg.walkableRadius = (int)ceilf(m_agentRadius / m_cfg.cs);

Step 2. Rasterize input polygon soup.

體素化
體素化的概念在第一篇中已經(jīng)有所講述，這里再提一下，可以用2D圖形的光柵化最類比理解，其實(shí)就是為了找到3維空間中的三角形面與那些體素盒子相交

光柵化

具體步驟：

a.標(biāo)記所有三角形面是否可行走

rcMarkWalkableTriangles計(jì)算所有三角形的法線，與最大可行走角度做比較，并將結(jié)果存入m_triareas[]這個(gè)標(biāo)記數(shù)組中

b.創(chuàng)建高度場

c.光柵化三角形面

rcRasterizeTriangles這個(gè)函數(shù)是重點(diǎn)，它主要做了這些事：
遍歷所有三角形，調(diào)用rasterizeTri，將每個(gè)初始的三角形面轉(zhuǎn)換成空間內(nèi)的體素集
注意這里每個(gè)三角形之間是相互獨(dú)立的，也許某一組三角形可以圍成了一個(gè)多面體，但這里已經(jīng)不再有"多面體"的概念，而是將地圖的信息全部拆解到三角形面，再進(jìn)一步拆解到體素盒子

1.找到三角形的AABB（注意是3維空間內(nèi)的三角形）
2.計(jì)算三角形的高度（y軸）范圍
3.按xz坐標(biāo)網(wǎng)格切割三角形
俯視圖如下（注意只是俯視圖，實(shí)際上應(yīng)該是3維空間的切割）

切割俯視圖

在分割三角形時(shí)代碼中有這樣一個(gè)數(shù)組

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

解釋一下7 3 4這三個(gè)數(shù)字
4：有4份對應(yīng)的數(shù)據(jù)，用來存放輸入的圖形和分割后的圖形
3：對應(yīng)一個(gè)頂點(diǎn)的x y z 坐標(biāo)值
7：一個(gè)三角形在分割時(shí)會被切4刀（即一個(gè)正方形格子的4條邊），所以切完最多可能會變成一個(gè)7邊形，也就是最多需要存7個(gè)頂點(diǎn)

這里有一個(gè)重要的函數(shù):
用一條直線將一個(gè)凸多邊形分成兩個(gè)凸多邊形

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

參數(shù)axis取值[0,2],對應(yīng)表示x,y,z軸
枚舉所有邊，判斷邊的頂點(diǎn)坐標(biāo)是在軸的同側(cè)還是不同側(cè)，
若是同側(cè)則將兩個(gè)頂點(diǎn)都加入對應(yīng)的新多邊形
若是在不同側(cè)，則新生成一個(gè)分割點(diǎn)，將分割點(diǎn)（復(fù)制成兩份）加入兩個(gè)新多邊形

4.找到切割后的多邊形對應(yīng)的span,根據(jù)對應(yīng)的三角形面的可行走情況設(shè)置span的可行走屬性，并把這個(gè)span根據(jù)xz的投影坐標(biāo)添加入到高度場中

這里要特別說明兩點(diǎn)
1.span在合并的時(shí)候，如果同一個(gè)span，有的面是可行走，有的是不可行走，在合并之后會變成可行走

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

2.如果一個(gè)面是完全垂直于xz平面且與x軸或者z軸平行，在切割時(shí)會怎么樣
不妨假設(shè)Xmax=Xmin,這時(shí)在x軸方向的切割只有一次即x=Xmax，并且dividePoly會判定所有三角形的邊都在分割線的同一側(cè)，分割的結(jié)果是一個(gè)原三角形和一個(gè)空集合