Unity-NavMesh詳解-其一

今天我們來詳細地探究一下Unity的NavMesh這一性能強大的組件：

NavMesh基本使用

NavMesh簡單地說本質上是一個自動尋路的AI組件，我們首先來學習基本的使用。

畫面中我已經添加好了地面，目標，障礙物以及玩家四個要素。

注意我們要進行NavMesh的一些前提工作：

在所有我們想要加入NavMesh網格導航的場景元素的static處選擇Navigation Static。

然后在window->ai處可以看到Navigation。

打開后如圖所示：

可以看到有四個部分，我們一部分一部分地來看：

Agent，我們可以理解為導航代理，簡單地說，如果我們借助NavMesh實現自動尋路，那么所有有自動尋路功能的對象都需要掛載NavMeshAgent，這個Agent定義的東西包括掛載對象在NavMesh網格中的半徑、高度、最大可跨越的臺階高度(Step Height)、最大坡度（對于這個對象而言，超過這個坡度的網格被視作不可到達），我們還可以為這個代理命名。

Areas，我們可以理解為導航的區域，因為NavMesh的底層是啟發式算法，我們需要預先設定好各個不同區域的移動成本(cost)，圖中的不同索引對應的就是不同區域的移動成本（0為可行走，1為不可行走）。

Bake，也就是烘焙。烘焙決定了我們會如何去根據場景中想要被NavMesh使用的具體情況來生成網格。

在這里我們可能要插入一下關于NavMesh的使用原理：

我們首先將場景中的設置為Navigation Static的物體的三角網格轉換為體素（立方體小格子），然后過濾掉不可行走的區域（根據Bake中設定的參數如最大坡度最大臺階高度等），生成一個高度場（此時在XZ平面是一個個大小相等的格子，而在Y軸則是一個個高度值）；然后我們將相鄰的體素合并成連續的可行走區域，之后我們再將體素的邊界轉化為一個個凹多邊形（因為很多復雜的情況可行走區域只能轉換成凹多邊形），然后再將凹多邊形轉換為凸多邊形（方便進行路徑搜索），凸多邊形最后會變成點和線的集合，也就是可行走區域最后會轉化成一個圖結構，在圖上我們就可以去使用尋路算法了。

而Bake本質上就是我們去執行NavMesh體素化時的一些考慮參數，比如我們可以看見的Agent的半徑、高度等，值得注意的是，我們這里的Agent 參數和之前Agent的Radius的參數意義并不相同：比如這里的Agent Radius代表的是Agent與其他物體（也包括其他Agent）之間的最小距離，換句話說就是防止兩個物體離得太近。除此之外還有生成離網鏈接等功能（離網鏈接即一些特殊情況下的路線）

這個模塊就比較簡單了，基本都是前面我們所說的內容。

現在我們只需要按下Bake鍵，就可以看到烘焙后的場景了：

可以看到有一層綠色籠罩在地面上，現在我們要做的是去實現一個基本的導航功能。

我們在Player身上掛載這個Nav Mesh Agent:是的，就是我們之前的Agent，可以看到我們的Agent Type就是我們之前定義的Humanoid，這里還有一些其他的參數如速度、角速度等。

有了Agent我們就可以導航了，不過我們還需要一個腳本來具體控制這個Player：

using System.Collections;
using System.Collections.Generic;
using UnityEngine;
using UnityEngine.AI;public class PlayerControl : MonoBehaviour
{public NavMeshAgent nav; //獲取導航網格代理組件，通過此組件來告知AI目標public Transform target; //目標的位置private void Update(){nav.SetDestination(target.position); //每幀更新目標位置}}

填好參數之后，運行就可以看到：運行前：

運行后：

那么我們的基本的NavMesh就使用成功了。

一些其他的基本的Unity的NavMesh的內容大家可以在這里找到，這個博主寫的更多是一些具體應用的方面，大家可以在這里查缺補漏。詳解Unity中的Nav Mesh|導航尋路系統（一）_navmesh-CSDN博客

Recast Navigation

Unity的NavMesh的底層其實是基于我們的Recast Navigation實現的，這里有大神的帖子：

Recast Navigation源碼分析：導航網格Navmesh的生成原理 - 知乎 (zhihu.com)

RecastNavigation 是一個的導航尋路工具集，它包括了幾個子集：

所以我們如果想要理解Recast Navigation，就只需要搞明白三件事情：怎么根據輸入生成導航網格、怎么在導航網格上自動尋路、怎么針對一群人自動尋路。

如何生成導航網格？

接下來讓我們來一個一個過程地展開介紹：

體素化：

我們可以把像素看作2D平面的最小單位，那么體素就是3D空間內的最小單位。在生成導航網格的最開始，我們把3D空間中的物體變成一個個體素，將基于邊界的表現形式（例如：多邊形模型，曲面等）轉換成為體積的表現形式（例如：體素塊）并構建一個高度場。

高度場：

體素化之后的3D空間就像一個個用積木塊拼湊出來的空間一樣，而高度場則是將整個體素空間壓縮成一個二維平面與一個高度值；體素化之后的體素空間內每一個體素都會包含高度信息，我們的高度場本質上只是把這個高度單獨提出來作為信息之后再去除掉高度維度，這樣就保留了高度信息的同時壓縮了維度。

高度場是容納所有體素格子的AABB包圍盒，在可視化之后可以看到，我們會按照CellSize對這個包圍盒進行XZ方向均勻的一個切割(關于CellSize，基本的原則是CellSize越大則計算開銷越小，CellSize越小則越精細)，按照CellHeight接著對包圍盒的高度進行均勻切割。切割后的一個個像素塊就是一個個體素塊，正常情況下我們用俯視的角度看到的應該是在XZ平面均勻分布的一個個方形，這些方形中存放著這個體素的高度區間的集合（Span），這個就是我們的高度場。

Span:

對于高度場中的一列體素，我們一般只會去關注他是否是“實心”的，有的話就代表這個體素的空間是有障礙的。我們會合并一列體素中的連續的實心體素，稱為一個Span。

搜索鄰居：

在NavMesh生成中，鄰居搜索的核心目標是識別可行走區域的連通性，即判斷哪些體素（或高度區間）可以相互連接形成連續的可行走表面。總的來說，搜索鄰居的過程需要我們在高度場中的高度和平面綜合考慮才可，我們會首先找到每一個體素塊高度差值不超過預設值的體素塊（預設值如Unity的最大臺階高度），然后再在XZ平面檢查是否是鄰接關系，最后判斷是否是連續的可行走區域。

實體高度場：

體素化的最終目的就是為了創建一個實體的高度場，這個實體的高度場會表面具體哪里有障礙，同時也表明了連通的可行走區域。

需要注意的是，在之前我們的措辭中并沒有說明關于從貼圖轉換到體積表達的具體過程其實就是把構成貼圖的三角形轉換成立方體，而這個過程中我們采取的策略是“保守體素化”：保證生成的體素將原來的幾何圖形全部包圍。

生成實體高度場之后，我們就需要去考慮一些預設值的影響了，如最大坡度，最大可達臺階高度等，將實體高度場中不符合要求的部分過濾掉。

裁剪多邊形表面是否可行走：

對于每一個Span，我們去判斷該Span頂部體素的幾何體的斜率是否低于可行走表面的最大坡度即可判斷該表面是否可以通過：

相關源碼如下：

/// The maximum slope that is considered walkable. [Limits: 0 <= value < 90] [Units: Degrees] float walkableSlopeAngle;//標記可行走三角面
void rcMarkWalkableTriangles(rcContext* ctx, const float walkableSlopeAngle,const float* verts, int nv,const int* tris, int nt,unsigned char* areas)
{rcIgnoreUnused(ctx);rcIgnoreUnused(nv);const float walkableThr = cosf(walkableSlopeAngle/180.0f*RC_PI);// 三角形面的法向量float norm[3];for (int i = 0; i < nt; ++i){// 三角形三個頂點的索引const int* tri = &tris[i*3];// 計算垂直與三角形面的法向量，傳入的參數是三角形三個頂點地址calcTriNormal(&verts[tri[0]*3], &verts[tri[1]*3], &verts[tri[2]*3], norm);// Check if the face is walkable.if (norm[1] > walkableThr)areas[i] = RC_WALKABLE_AREA;}
}static void calcTriNormal(const float* v0, const float* v1, const float* v2, float* norm)
{float e0[3], e1[3];rcVsub(e0, v1, v0);rcVsub(e1, v2, v0);rcVcross(norm, e0, e1);rcVnormalize(norm);
}

float walkableSlopeAngle;

顯然這是我們定義的可行走的最大坡度，這里是度數制。

	rcIgnoreUnused(ctx);rcIgnoreUnused(nv);

這兩句是一個顯式告訴編譯器忽略未使用的參數ctx和nv，因為一般來說如果出現未使用的參數時編譯器可能會拋出警告，這個相當于告訴編譯器自己故意定義了參數而不使用。

	const float walkableThr = cosf(walkableSlopeAngle/180.0f*RC_PI);

這句代碼用于將設定的最大可行走坡度轉換為弧度制之后的余弦值。

原理大致如圖：

?可以看到我們三個點組成的三角形的法向量的y軸分量其實就是這個三角形的坡度。

static void calcTriNormal(const float* v0, const float* v1, const float* v2, float* norm)
{float e0[3], e1[3];rcVsub(e0, v1, v0);rcVsub(e1, v2, v0);rcVcross(norm, e0, e1);rcVnormalize(norm);
}

這個函數中使用的rcVsub，rcVcross，rcVnormalize分別代表向量的減法，叉乘和歸一化，這里的諸多操作其實就是計算三角形的法向量：v0,v1,v2三個float變量代表三個頂點，我們通過相減得到兩個邊向量，然后兩個邊向量叉乘得到法向量，法向量歸一化之后就是單位法向量。

		// Check if the face is walkable.if (norm[1] > walkableThr)areas[i] = RC_WALKABLE_AREA;

如果計算三角形單位法向量的函數得到的單位法向量的y分量大于我們的余弦值，則證明這個坡度是可行走的（角度越大余弦值越小）。

光珊化三角形，添加span到實體高度場：

獲取到具體可行走的多邊形后，我們就要將這些多邊形添加到實體高度場了，但是現在的問題是我們的多邊形——其實是由一個個三維的三角形組成的——是一個非常難以處理的內容，我們不知道如何去把這個多邊形放置在合適位置的高度場上。

如果你直接去處理多邊形本身，那當然非常難以處理，誤差可能很大。我們要做的是將這個多邊形分割成一個個三角形，然后再將這一個個三角形轉換成實體高度場需要的X-Z軸與高度信息，這里就牽扯到一個切割凸多邊形的問題：我們的一個個三角形在X-Z軸的平面對應的體素格子里可能是一個個凸多邊形。

從遍歷凸多邊形的每條邊開始，通過檢測每條邊與分割線的空間關系來切割多邊形：??

若邊的兩個端點均位于分割線同側，則保留該邊，將其起點加入對應側的新多邊形頂點集；
若邊跨越分割線?（端點分居兩側），則計算交點并分割該邊——交點同時加入兩側新多邊形，起點按位置歸屬分配至具體子多邊形；
遇端點落在分割線上時，將其同步標記為上下兩個新多邊形的共享頂點。
?最終按序連接每側的保留邊、分割點和交點，生成兩個邊界連續的子凸多邊形。??

此流程通過沿X/Z軸方向每隔cellsize單位設置平行分割線（如圖中五邊形被網格線切割所示），將三角形表面遞歸分解為與網格列對齊的片段，繼而通過取各片段頂點的最小Y值（體素下沿）和最大Y值（體素上沿），實現三維表面到體素化格子（x,z坐標+Y軸區間）的無損轉換，為導航網格生成奠定數據基礎。

上圖為例，可以看到一個三維空間中的三角形，我們現在要做的事是把這個三角形轉換成X-Z空間與高度信息的形式。

?可以看到對于X-Z空間的一個體素格子來說，這個三角形的高度信息對應的就是這兩個高度的體素格子與三角形的實際交點。

現在我們向實體高度場中添加span：

與多邊形相交的網格列。
裁剪多邊形的最小-最大高度范圍（網格列被阻擋的部分）。

我們根據獲得的最小最大高度范圍來判斷該span是否為可行走：

如果新span不與網格列中的任何已經存在的span相交，則會創建一個新span。如果新span與已經存在的span相交或被已經存在的span所包含，則合并這兩個span。
當新span與已經存在的span合并時，必須評估生成的聚合span是否是可行走的。這個“可行走標志”只適用于span的頂部表面。如果設置了，就意味著span頂部表示多邊形，該多邊形有足夠低的斜率是可行走的。
如果新span的頂部高于它正在合并到的span，則新span的可行走標志用于聚合span；如果新span的頂部低于它正在合并到的span，那么我們不關心新span的標志，新span的標志被丟棄。
如果新span的頂部與其合并到的span處于同一高度，則如果其中任意一個被認為是可行走的，聚合span就被標記為可行走。

一句話：看哪個span高，高的span能行走就走，否則就不能走。

這樣我們的體素化過程就大體完成了：

體素化過程始于建立高度場這一基礎數據結構，它將空間按配置的精度（cellSize、cellHeight）劃分為網格，并在每個網格位置（x,z）存儲稱為 ?Span? 的高度區間鏈表（每個Span記錄下界?smin?和上界?smax）。通過分析輸入三角面片，系統裁剪多邊形表面并基于坡度參數（walkableSlopeAngle）初步判斷其是否可行走。核心操作是 ?光柵化三角形?：將每個三角形分割為與網格列對齊的凸多邊形片段，計算其頂點Y值范圍（即Span的smin/smax），并將這些攜帶可行走標記的Span添加到實體高度場中（處理Span重疊與合并）。最終生成的實體高度場完整記錄了三維場景中所有實體（障礙）占據的空間及其表面的可行走屬性。為準備后續區域生成，算法會對實體高度場進行搜索鄰居操作：在垂直方向過濾不滿足Agent高度（walkableHeight）的Span，并在水平方向檢測滿足可攀爬高度差（walkableClimb）的相鄰Span連接關系，該步驟實質上是在轉換數據為開放高度場（CompactHeightfield）?? 并預計算連通性，為導航網格的洪水填充區域劃分奠定基礎。

篩選可走表面

span有一個標志，指示其頂面是否被認為是可行走的。但是此標志僅根據與span相交的多邊形的斜率來設置。現在是進行更多過濾的好時機。此過濾從某些span中刪除可行走標志。

Recast Navigation中給出了三種過濾方法：

篩選低垂的可行走障礙

為了在低洼區域形成可走區域。比如樓梯，將不可走標記為可走。

算法比較簡單：迭代每一列，從下往上遍歷span，對于同列任意兩個相鄰的span1（下）和span2（上），當span1可走，并且span2不可走的時候，計算這兩個span的上表面高度差Diff，如果Diff小于配置參數“walkableClimb”，則將span2設置為“可走”。

顯然比較常見的場景就是從低向高的攀爬場景，只要兩個span的高度差不大于參數就允許行走。

void rcFilterLowHangingWalkableObstacles(rcContext* ctx, const int walkableClimb, rcHeightfield& solid)
{rcAssert(ctx);rcScopedTimer timer(ctx, RC_TIMER_FILTER_LOW_OBSTACLES);const int w = solid.width;const int h = solid.height;for (int y = 0; y < h; ++y){for (int x = 0; x < w; ++x){rcSpan* ps = 0;bool previousWalkable = false;unsigned char previousArea = RC_NULL_AREA; for (rcSpan* s = solid.spans[x + y*w]; s; ps = s, s = s->next){const bool walkable = s->area != RC_NULL_AREA;  // 如果當前跨度不可行走，但其下方有可行走跨度，則將其上方的跨度也標記為可行走。if (!walkable && previousWalkable){if (rcAbs((int)s->smax - (int)ps->smax) <= walkableClimb)s->area = previousArea;}// Copy walkable flag so that it cannot propagate// past multiple non-walkable objects.previousWalkable = walkable;previousArea = s->area;}}}
}

過濾可行走的低高度區間

這個是同列相鄰兩區間之間距離的校驗，保證最小可通過距離，可走變不可走。如果在span上方有太近的障礙物，那么span的頂面是不能穿越的。也就是說span的頂部與其上方span的底部至少有一個最小距離（最高的agent可以站在span上而不會與上方的障礙物發生碰撞）。想象一張桌子放在地板上，桌子下面的地板表面是平的，但由于桌子比較矮，不能在桌子底下行走，所以不能被認為是可穿越的（traversable）。

迭代每一列，從下往上遍歷span，如果當前span不可走，直接跳過。
否則，計算當前span_B的上表面和其上相鄰的span_A的下表面之間的高度差Diff。span_A不存在的話，高度差Diff設為無窮大。
如果“高度差Diff”小于“walkableHeight”，則將當前span的標識位置為“不可走”。

void rcFilterWalkableLowHeightSpans(rcContext* ctx, int walkableHeight, rcHeightfield& solid)
{rcAssert(ctx);rcScopedTimer timer(ctx, RC_TIMER_FILTER_WALKABLE);const int w = solid.width;const int h = solid.height;const int MAX_HEIGHT = 0xffff;//從上面沒有足夠空間讓 agent 站在那里的 span 中移除可行走標志。for (int y = 0; y < h; ++y){for (int x = 0; x < w; ++x){for (rcSpan* s = solid.spans[x + y*w]; s; s = s->next){const int bot = (int)(s->smax);const int top = s->next ? (int)(s->next->smin) : MAX_HEIGHT;if ((top - bot) <= walkableHeight)s->area = RC_NULL_AREA;}}}
}

過濾有效區間和陡峭區間

同列相鄰兩區間之間距離的校驗，保證最小可通過距離。可走變不可走，這種過濾器會首先查找當前span的所有“有效鄰居區間”。需要注意的是：如果當前span已經不可走，則直接跳過了。

當前迭代區間為span1，遍歷四個方向的軸鄰居列，從下往上迭代軸鄰居列的高度區間span2。
假設span1的上面還與其有同列相鄰的span4，span2上面有與其同列相鄰的span3。如果span3或span4不存在，則認為其高度為無窮大。
計算max(span1, span2)和min(span3, span4)的差值H，如果diff大于“配置可走高度walkableHeight”，則認為span2是一個“有效鄰居區間”。可以證明，每一個軸鄰居列上最多只會存在一個“有效鄰居區間”。

可以很明顯的看出，“有效鄰居區間”限定了兩種情況：

找到所有“有效鄰居區間”后，過濾器會繼續過濾“峭壁區間”。

如果有任意軸鄰居列上沒有任何“高度區間”，則認為當前span是”峭壁區間“。
如果有任意軸鄰居列上沒有”有效鄰居區間“，則認為當前span是“峭壁區間”。
如果有任意軸鄰居列上存在“有效鄰居區間”span2，span2的上表面低于span的上表面，且span和span2的上表面高度差Diff大于配置參數“可爬坡高度”，則認為當前span是”峭壁區間”。
如果當前span本來可走，且判斷為“峭壁區間”，則設置為“不可走”。

找不到峭壁區間后，還會進行一層間接峭壁區間的判斷。

所有上表面高于span上表面的“有效鄰居區間”中，上表面最高的“有效鄰居區間”的上表面高度設為a。
所有上表面低于span上表面的“有效鄰居區間”中，上表面最低的“有效鄰居區間”的上表面高度設為b。
如果a減b大于配置參數“爬坡高度walkableClimb”，則認為當前span處于峭壁上--間接峭壁區間。
如果當前span本來可走，且判斷為“間接峭壁區間”，則置為“不可走”。

void rcFilterLedgeSpans(rcContext* ctx, const int walkableHeight, const int walkableClimb,rcHeightfield& solid)
{rcAssert(ctx);rcScopedTimer timer(ctx, RC_TIMER_FILTER_BORDER);const int w = solid.width;const int h = solid.height;const int MAX_HEIGHT = 0xffff;// 標記邊界Spanfor (int y = 0; y < h; ++y){for (int x = 0; x < w; ++x){for (rcSpan* s = solid.spans[x + y*w]; s; s = s->next){// 跳過不可走spanif (s->area == RC_NULL_AREA)continue;const int bot = (int)(s->smax);const int top = s->next ? (int)(s->next->smin) : MAX_HEIGHT;// 查找鄰居的最小高度int minh = MAX_HEIGHT;// Min and max height of accessible neighbours.int asmin = s->smax;int asmax = s->smax;for (int dir = 0; dir < 4; ++dir){int dx = x + rcGetDirOffsetX(dir);int dy = y + rcGetDirOffsetY(dir);//跳過越界的鄰居if (dx < 0 || dy < 0 || dx >= w || dy >= h){minh = rcMin(minh, -walkableClimb - bot);continue;}// From minus infinity to the first span.rcSpan* ns = solid.spans[dx + dy*w];int nbot = -walkableClimb;int ntop = ns ? (int)ns->smin : MAX_HEIGHT;//如果 spans 之間的間隙太小，則跳過 neightbourif (rcMin(top,ntop) - rcMax(bot,nbot) > walkableHeight)minh = rcMin(minh, nbot - bot);//其余的跨度for (ns = solid.spans[dx + dy*w]; ns; ns = ns->next){nbot = (int)ns->smax;ntop = ns->next ? (int)ns->next->smin : MAX_HEIGHT;// 如果Span之間的間隙太小，則跳過 neightbourif (rcMin(top,ntop) - rcMax(bot,nbot) > walkableHeight){minh = rcMin(minh, nbot - bot);// 查找最小/最大可訪問鄰居高度if (rcAbs(nbot - bot) <= walkableClimb){if (nbot < asmin) asmin = nbot;if (nbot > asmax) asmax = nbot;}}}}//如果下降到任何鄰居Span小于 walkableClimb，將Span標記為RC_NULL_AREAif (minh < -walkableClimb){s->area = RC_NULL_AREA;}//如果所有鄰居之間的差異太大，我們在陡坡上，將Span標記為RC_NULL_AREAelse if ((asmax - asmin) > walkableClimb){s->area = RC_NULL_AREA;}}}}
}

通過這三層過濾后就可以進行下一個步驟了。

劃分可走表面為簡單區域

我們在一個步驟中獲取了具體可行走的表面，現在對于可行走表面我們需要一些步驟將可通過的區域分割成可以最終形成簡單多邊形的相鄰的span（表面）區域。

創建開放高度場CompactHeightField

什么是開放高度場？和實體高度場有什么聯系和區別？

無論是用實體高度場還是開放高度場，只是數據結構的不同，在邏輯上沒有任何差別，Recast采用了開放高度場的數據結構進行體素化之后的所有算法。換句話說，再進行體素化構建實體高度場后，進行了一步實體高度場到開放高度場的轉換。注意，開放高度場是在整個體素化過程結束之后才轉換的，此時已經經過了高度區間的合并和過濾，換句話說，其實此時實體高度區間的下表面已經沒有任何意義了。至于為什么選擇開放高度場，更多的考慮可能是Recast關心的是場景中的“無實體障礙可通過空間”，而不關心“實體空間”。但是需要理解，本質上，使用哪一個高度場并沒有什么區別。

因此，open span使用“地板（floor）”和“天花板（ceiling）”的術語。open span的地板是其關聯的solid span的頂部。 open span的天花板是它所屬的列中下一個更高的solid span的底部。如果沒有更高的solid span，則open span的天花板是任意的最大值，例如整數的最大值。

CompactHeightField也叫緊縮高度場。我們不只關心實體空間，許多算法都是在solid span上方的空間上操作的。對于導航網格的生成來說，solid span的上表面是其最重要的部分，需要注意的是，開放高度場不是實體空間的簡單反轉。如果一個高度場列不包含任何solid span，則它也沒有任何open span。最低的solid span以下的區域也被忽略，只有solid span上方的空間由open span來表示。

看起來有點眼花撩亂了可能，但其實說白了實體高度場就是可以拿來給角色踩的那一層，就是你現實生活中腳下的部分；開放高度場則是從你腳下的那一層到你頭頂的那一層，也就是你人物本身可以移動的高度部分，如果你頭頂沒有東西那就是無限大——代表云，天空或者太陽。

開放高度場的創建相對簡單，循環遍歷所有實體span，如果span被標記為可通過，則確定它的最高值與其所在列中下一個更高span的最低值之間的開放空間。這些值分別形成了新的開放span的地板和天花板。如果一個實體span是它所在列中最高的span，則其關聯的開放span將其天花板設置為任意高值（例如 Integer.MAX_VALUE）。新生成的開放span形成所謂的開放高度場：

bool rcBuildCompactHeightfield(rcContext* ctx, const int walkableHeight, const int walkableClimb,rcHeightfield& hf, rcCompactHeightfield& chf)
{const int w = hf.width;const int h = hf.height;const int spanCount = rcGetHeightFieldSpanCount(ctx, hf);//這里省略一些非核心代碼......const int MAX_HEIGHT = 0xffff;// 填充rcCompactCell和rcCompactSpanint idx = 0;for (int y = 0; y < h; ++y){for (int x = 0; x < w; ++x){const rcSpan* s = hf.spans[x + y*w];// If there are no spans at this cell, just leave the data to index=0, count=0.if (!s) continue;rcCompactCell& c = chf.cells[x+y*w];c.index = idx;c.count = 0;while (s){if (s->area != RC_NULL_AREA){const int bot = (int)s->smax;const int top = s->next ? (int)s->next->smin : MAX_HEIGHT;chf.spans[idx].y = (unsigned short)rcClamp(bot, 0, 0xffff);chf.spans[idx].h = (unsigned char)rcClamp(top - bot, 0, 0xff);chf.areas[idx] = s->area;idx++;c.count++;}s = s->next;}}}return true;
}

創建鄰居鏈接?

我們現在有一個開放高度場，里面充滿了不相關的開放span。下一步是找出哪些span形成了連續span的潛在表面。這是通過創建軸鄰居鏈接（axis-neighbor links）來實現的。對于每個span，搜索其軸相鄰列以查找候選對象。如果滿足以下兩個條件，則相鄰列中的span被視為鄰居span：

1. 兩個span的頂部上升或下降的步長小于 walkableClimb的值。這允許將樓梯臺階和路緣這樣的表面檢測為有效的鄰居。

這里又涉及到這個參數?walkableClimb了，這個參數的意義就是幫助我們正確的設置可行走高度差異的，一般來說，walkableClimb 應該大于 cellHeight 的兩倍(walkableClimb > cellHeight * 2)。否則體素場的分辨率可能不夠高，無法準確檢測可通過的窗臺（ledge）。窗臺可以合并，有效地將它們的臺階高度加倍。對于樓梯來說，這尤其是個問題。（為什么樓梯這么難處理）

2.?當前span的地板和潛在鄰居span的天花板之間的開放空間間隙足夠大（大于walkableHeight）。

例如，如果agent要從一個span跨到另一個span，它會用頭撞到鄰居的天花板上嗎？這是與潛在鄰居之間的間隙檢查。我們已經知道地板到天花板的高度對于每個單獨的span來說都是足夠的，該檢查是在構建實體高度場時進行的。但是不能保證在潛在鄰居之間移動時的間隙滿足相同的高度要求。

bool rcBuildCompactHeightfield(rcContext* ctx, const int walkableHeight, const int walkableClimb,rcHeightfield& hf, rcCompactHeightfield& chf)
{//創建鄰居鏈接const int MAX_LAYERS = RC_NOT_CONNECTED-1; //static const int RC_NOT_CONNECTED = 0x3f , 最多63層int tooHighNeighbour = 0;for (int y = 0; y < h; ++y){for (int x = 0; x < w; ++x){const rcCompactCell& c = chf.cells[x+y*w];for (int i = (int)c.index, ni = (int)(c.index+c.count); i < ni; ++i){rcCompactSpan& s = chf.spans[i];for (int dir = 0; dir < 4; ++dir){rcSetCon(s, dir, RC_NOT_CONNECTED); //先設置默認值RC_NOT_CONNECTED二進制是 111111const int nx = x + rcGetDirOffsetX(dir);const int ny = y + rcGetDirOffsetY(dir);// First check that the neighbour cell is in bounds.if (nx < 0 || ny < 0 || nx >= w || ny >= h)continue;// 檢查當前span的所有鄰居span，看這個span是否和當前span有鄰居關系const rcCompactCell& nc = chf.cells[nx+ny*w];for (int k = (int)nc.index, nk = (int)(nc.index+nc.count); k < nk; ++k){const rcCompactSpan& ns = chf.spans[k];const int bot = rcMax(s.y, ns.y);const int top = rcMin(s.y+s.h, ns.y+ns.h);//檢查2個span間的gap是否滿足walkableHeight和walkableClimb的限制if ((top - bot) >= walkableHeight && rcAbs((int)ns.y - (int)s.y) <= walkableClimb){// Mark direction as walkable.const int lidx = k - (int)nc.index;if (lidx < 0 || lidx > MAX_LAYERS){tooHighNeighbour = rcMax(tooHighNeighbour, lidx);continue;}rcSetCon(s, dir, lidx);break;}}}}}}return true;
}

根據walkableRadius剔除邊緣

我們現在獲取了一系列連貫的開放高度場，但是還需要小小的優化一下：我們的人物模型本身也是有一定體積的，如果允許人物的模型中心移動到最邊緣處可能會出現穿模的情況，所以具體的做法就是在所有的邊緣處加上一層小小的剔除效果，即將障礙物周圍可行走區域按radius值適當擴散不可行走區域。

此時的做法是對每一個“可走高度區間”加上一個“邏輯距離dist”的概念。該距離在邏輯上標識當前高度區間距離某個最近邊界的距離。做兩遍掃描，計算出每個span離邊緣的距離,放到char*類型的dist 中。每次操作都是用小值替換大值，第一遍掃描從左上角往右下角，第二遍從右下角往左上角。這樣就能保證每個位置的span計算出來的離邊緣距離的準確性。然后再將離邊距離小于兩倍半徑的span從可行走的span中剔除。

 從左下到右上遍歷
for (int y = 0; y < h; ++y)
{for (int x = 0; x < w; ++x){const rcCompactCell& c = chf.cells[x+y*w];for (int i = (int)c.index, ni = (int)(c.index+c.count); i < ni; ++i){const rcCompactSpan& s = chf.spans[i];if (rcGetCon(s, 0) != RC_NOT_CONNECTED){// (-1,0)	左鄰居const int ax = x + rcGetDirOffsetX(0);const int ay = y + rcGetDirOffsetY(0);const int ai = (int)chf.cells[ax+ay*w].index + rcGetCon(s, 0);const rcCompactSpan& as = chf.spans[ai];// 軸鄰居距離+2nd = (unsigned char)rcMin((int)dist[ai]+2, 255);if (nd < dist[i])dist[i] = nd;// (-1,-1) 左下鄰居if (rcGetCon(as, 3) != RC_NOT_CONNECTED){const int aax = ax + rcGetDirOffsetX(3);const int aay = ay + rcGetDirOffsetY(3);const int aai = (int)chf.cells[aax+aay*w].index + rcGetCon(as, 3);// 斜方向的鄰居距離+3nd = (unsigned char)rcMin((int)dist[aai]+3, 255);if (nd < dist[i])dist[i] = nd;}}if (rcGetCon(s, 3) != RC_NOT_CONNECTED){// (0,-1) 下鄰居const int ax = x + rcGetDirOffsetX(3);const int ay = y + rcGetDirOffsetY(3);const int ai = (int)chf.cells[ax+ay*w].index + rcGetCon(s, 3);const rcCompactSpan& as = chf.spans[ai];nd = (unsigned char)rcMin((int)dist[ai]+2, 255);if (nd < dist[i])dist[i] = nd;// (1,-1) 右下鄰居if (rcGetCon(as, 2) != RC_NOT_CONNECTED){const int aax = ax + rcGetDirOffsetX(2);const int aay = ay + rcGetDirOffsetY(2);const int aai = (int)chf.cells[aax+aay*w].index + rcGetCon(as, 2);nd = (unsigned char)rcMin((int)dist[aai]+3, 255);if (nd < dist[i])dist[i] = nd;}}}}
}

根據ConvexVolume標記體素Area掩碼

我們完成了開放高度場之后，還要考慮場景內的物體是否影響可行走問題，這涉及到了動態避障問題，我們在這里先介紹ConvexVolume——在Recast Navigation中，ConvexVolume（凸體體積）是一個用于動態標記導航網格特定區域的功能模塊，主要用于定義自定義可行走區域、障礙物或特殊地形屬性。

static const int MAX_CONVEXVOL_PTS = 12;
struct ConvexVolume
{float verts[MAX_CONVEXVOL_PTS*3];//Volume頂點數據float hmin;//Volume高度最低值float hmax;//Volume高度最高值int nverts;//Volume頂點數int area;  //區域類型,可自定義類型，比如Ground,Water,Grass等等
};

這是凸體體積的數據結構。

void rcMarkConvexPolyArea(rcContext* ctx, const float* verts, const int nverts,const float hmin, const float hmax, unsigned char areaId,rcCompactHeightfield& chf)
{// 遍歷多邊形范圍內的體素for (int z = minz; z <= maxz; ++z){for (int x = minx; x <= maxx; ++x){const rcCompactCell& c = chf.cells[x+z*chf.width];for (int i = (int)c.index, ni = (int)(c.index+c.count); i < ni; ++i){rcCompactSpan& s = chf.spans[i];if (chf.areas[i] == RC_NULL_AREA)continue;if ((int)s.y >= miny && (int)s.y <= maxy){float p[3];p[0] = chf.bmin[0] + (x+0.5f)*chf.cs; p[1] = 0;p[2] = chf.bmin[2] + (z+0.5f)*chf.cs; if (pointInPoly(nverts, verts, p))  //判斷點是否在poly范圍內{chf.areas[i] = areaId; //設置體素area類型}}}}}
}

該函數是 Recast Navigation 中用于標記凸多邊形區域內體素區域類型的關鍵函數，其作用是為導航網格生成預定義特殊區域（如水域、草地等）。其中：

Shape Height = Volume高度最高值hmax - Volume高度最低值hmin，Shape Descent = 坐標y最低值 - Volume高度最低值hmin，Shape Descent代表坐標面下沉值。

創建區域

?到目前為止，所有的一切都是在為區域創建做準備。區域（region）是一組連續的span，表示可走表面的范圍。它應該滿足盡量大的、連續的、不重疊的、中間沒有“洞”的“區域，區域的一個重要方面是，當投影到xz平面上時，它們會形成簡單的多邊形。Recast里提供了三種方式的區域切分方法：

分水嶺算法（Watershed）

分水嶺算法（watershed algorithm）用于初始區域的創建。使用分水嶺類比，距離邊界最遠的span代表分水嶺中的最低點，邊界span代表可能的最高水位（和盆地的概念類似）。主循環從分水嶺的最低點開始迭代，然后隨著每個循環遞增，直到達到允許的最高水位。這從最低點開始緩慢地“淹沒”span。在循環的每次迭代期間，都會定位出低于當前水位的span，并嘗試將它們添加到現有區域或創建新的區域。在區域擴展（region expansion）階段，如果新淹沒的span與一個已經存在的區域接壤，則通常會將其添加到該區域中。任何在區域擴展階段，殘留下來的新淹沒的span都被用作創建新區域的種子。

分水嶺算法通常用于圖形處理領域，基于圖像的灰度值來分割圖像。這里唯一的不同點是用距離域來取代灰度值。距離域是指每個區間與可行走區域邊緣的最近距離。距離域越大，等同于地勢越低。

經典的Recast分區
創建最好的細分
通常最慢，一般用于離線處理，適合大地圖
將Heightfield劃分為沒有孔或重疊的良好區域。
在某些極端情況下，此方法創建會產生孔洞和重疊
- 當小的障礙物靠近較大的開放區域時，可能會出現孔（三角剖分可以解決此問題）
- 如果您有狹窄的螺旋形走廊（即樓梯），則可能會發生重疊，這會使三角剖分失敗
如果是預處理網格，通常是最佳選擇，如果您有較大的開放區域，這種方法也適用。

這個算法的詳細過程比較復雜，涉及到距離場的建立等內容，我這里感覺詳細介紹太占篇幅，建議大家自己去查閱。

單調分區

單調算法，注重效率，在性能上是最快的
能將高度場劃分為無洞和重疊的區域
創建長而細的多邊形，有時會導致路徑走彎
如果要快速生成導航網格，請使用此選項

按層分區

分層算法，折中思想，效果與性能都處于上述兩種算法之間
將heighfield劃分為非重疊區域
依靠三角剖分來處理孔（因此比單調分區要慢）
產生比單調分區更好的三角形
沒有分水嶺分區的特殊情況
速度可能很慢，并且會產生一些難看的鑲嵌效果（仍然比單調效果更好），如果您的開放區域較大且障礙物較小（如果使用瓷磚則沒有問題）
用于中小型瓷磚的導航網格的好選擇

階段總結

注意：Region 雖然是不重疊且沒有洞的區域，但仍然有可能是凹多邊形，無法保證 Region 內任意兩點在二維平面一定可以直線到達。后續需要進行輪廓生成和凸多邊形生成，為尋路做準備。

輪廓生成（Contour Generation）

在經過區域生成之后，region的描述是以span為顆粒度的，復雜度是否可以更簡化一下？此時區域與區域之間的分界就是非常重要的信息了。其實我們只需要region的輪廓，而輪廓（Contour）就是描述區域邊界的概念。

這個階段生成表示源幾何體的可行走表面的簡單多邊形（凸多邊形和凹多邊形）。輪廓仍然以體素空間為單位表示，但這是從體素空間（voxel space）回到向量空間（vector space）的過程中的第一步。

搜索區域邊緣

從開放高度場結構轉向輪廓結構時，最大的概念變化是從關注span的表面（surface）轉變為關注span的邊（edges）。

對于輪廓，我們關心span的邊，有兩種類型的邊：

區域邊（region ）：區域邊是其鄰居位于另一個區域中的span的邊
內部邊（internal）：內部邊是其鄰居在同一區域中的span的邊

在此步驟中，我們希望將邊分類為區域邊或內部邊。這些信息很容易找到。我們遍歷所有span，對于每個span，我們檢查所有軸鄰居，如果軸鄰居與當前span不在同一區域中，則該邊將被標記為區域邊。

// Mark boundaries.
for (int y = 0; y < h; ++y)
{for (int x = 0; x < w; ++x){const rcCompactCell& c = chf.cells[x+y*w];for (int i = (int)c.index, ni = (int)(c.index+c.count); i < ni; ++i){unsigned char res = 0;const rcCompactSpan& s = chf.spans[i];//如果span不存在region的ID,或者是邊界，就不考慮這種spanif (!chf.spans[i].reg || (chf.spans[i].reg & RC_BORDER_REG)){flags[i] = 0;continue;}for (int dir = 0; dir < 4; ++dir){unsigned short r = 0;if (rcGetCon(s, dir) != RC_NOT_CONNECTED){const int ax = x + rcGetDirOffsetX(dir);const int ay = y + rcGetDirOffsetY(dir);const int ai = (int)chf.cells[ax+ay*w].index + rcGetCon(s, dir);r = chf.spans[ai].reg;}//周圍鄰居所屬的region和當前span的region相同，說明是連通的，標記為1if (r == chf.spans[i].reg)res |= (1 << dir);}//flags保存每個span四個方向是否為邊界, 值是按位保存：1是邊界（區域邊），0不是邊界（內部邊）flags[i] = res ^ 0xf; //不連通的方向標記為1}}
}

查找區域輪廓

我們根據上一個步驟獲取的區域邊來繪制出區域的輪廓：

找到區域任意一個區域邊A，以當前區域邊開始算法。
如果當前是區域邊，將當前區域邊添加到輪廓中，然后順時針旋轉90度，繼續判斷旋轉后的邊。
如果當前是內部邊，則進入到共當前邊的鄰居內，然后逆時針旋轉90度，繼續判斷旋轉后的邊。
直到回到區域邊A為止，結束，此時依次添加進輪廓中的所有邊界邊全部查找完畢。

看起來有點不知所云，用幾張圖展示一下這個過程：

找到了一條區域的邊。

旋轉了九十度之后找到了又一條區域邊，加入輪廓。直到找到一條內部邊后，我們根據此時箭頭的方向步進到相鄰的span中。

進入新的span中先逆時針旋轉判斷邊，又是一個內部邊，那就進去之后再逆時針旋轉九十度，發現是區域邊了，又順時針旋轉...不斷循環往復直到我們回到起始span且面對起始方向。

遍歷的過程我們還要不斷地提取輪廓點，提取的規則如下：

體素左方是邊界，輪廓點取其上方體素。
體素上方是邊界，輪廓點取其右上方體素。
體素右方是邊界，輪廓點取其右方體素。
體素下方是邊界，輪廓點取其自身。

這樣做的目的是，使得各個區域的輪廓線多邊形的邊互相重合，因為最終生成的navimesh數據多邊形之間是共用一個邊的，最終效果如下圖所示：

相關代碼：

static void walkContour(int x, int y, int i,rcCompactHeightfield& chf,unsigned char* flags, rcIntArray& points)
{// 找到第一個區域邊的方向dirunsigned char dir = 0;while ((flags[i] & (1 << dir)) == 0)dir++;unsigned char startDir = dir;int starti = i;const unsigned char area = chf.areas[i];int iter = 0;while (++iter < 40000)  //迭代次數限制{// dir方向指向區域邊界，則保存輪廓點后，順時針旋轉后再循環嘗試if (flags[i] & (1 << dir))  //當前邊是區域邊{// Choose the edge cornerbool isBorderVertex = false;bool isAreaBorder = false;//默認輪廓點取其自身。int px = x;int py = getCornerHeight(x, y, i, dir, chf, isBorderVertex);int pz = y;// 為了使相鄰region walk出來的輪廓一樣，所以并不一定是以自身為輪廓，而是按照一下規則switch(dir){case 0: pz++; break;       //1. 體素左方是邊界，輪廓點取其上方體素。case 1: px++; pz++; break; //2. 體素上方是邊界，輪廓點取其右上方體素。case 2: px++; break;       //3. 體素右方是邊界，輪廓點取其右方體素。}int r = 0;const rcCompactSpan& s = chf.spans[i];if (rcGetCon(s, dir) != RC_NOT_CONNECTED){const int ax = x + rcGetDirOffsetX(dir);const int ay = y + rcGetDirOffsetY(dir);const int ai = (int)chf.cells[ax+ay*chf.width].index + rcGetCon(s, dir);r = (int)chf.spans[ai].reg;if (area != chf.areas[ai]) // area的邊界isAreaBorder = true;   }if (isBorderVertex)r |= RC_BORDER_VERTEX;if (isAreaBorder)r |= RC_AREA_BORDER;//添加到輪廓中points.push(px);points.push(py);points.push(pz);points.push(r);//去掉該dir上的邊界標記flags[i] &= ~(1 << dir);//然后順時針旋轉90度，繼續判斷旋轉后的邊dir = (dir+1) & 0x3; }else   // // 如果不是區域邊界，當前邊是內部邊，則移動到鄰居內，并將dir逆時針旋轉{int ni = -1;const int nx = x + rcGetDirOffsetX(dir);const int ny = y + rcGetDirOffsetY(dir);const rcCompactSpan& s = chf.spans[i];if (rcGetCon(s, dir) != RC_NOT_CONNECTED){const rcCompactCell& nc = chf.cells[nx+ny*chf.width];ni = (int)nc.index + rcGetCon(s, dir);}if (ni == -1){// Should not happen.return;}//進入到共當前邊的鄰居內x = nx;y = ny;i = ni;dir = (dir+3) & 0x3; //然后逆時針旋轉90度，等待繼續判斷旋轉后的邊}if (starti == i && startDir == dir) //我們回到起始span，面對起始方向，結束查找{break;}}
}

從邊到頂點

我們真正需要的內容不是邊而是頂點，對于X-Z軸空間的點來說選取非常簡單，取組成邊的兩個頂點即可：

確定頂點的y值就比較棘手了。這就是我們回歸3D可視化的地方。在下面的例子中，我們選擇哪個頂點?

選擇最高的y值有兩個原因：它確保最終頂點(x, y, z)位于源網格表面的上方。它還提供了一個通用的選擇機制，以便所有使用該頂點的輪廓將使用相同的高度。

簡化輪廓

我們已經為所有區域生成了輪廓。到這一步時，輪廓點由一系列連續的點組成的，在這些點里，有一些點是共線的，有一些點忽略后與最終輪廓形狀差距不大。下面是一個宏觀的視角。請注意，有兩種類型的輪廓部分（contour sections）：

兩個相鄰區域之間門戶（portal）的部分，即連接兩個有效區域之間的邊界邊。
與“無效”區域接壤的部分。無效區域被稱為“空區域”（null region），我在這里使用同樣的術語。

秉持著沒活硬整的態度，我們當然要繼續優化。

即使在直線輪廓上，構成邊的每個span都有一個頂點。顯然，答案是否定的。唯一真正必需的頂點是那些在區域連接中發生變化的頂點。

去除一些對輪廓形狀影響不大的點，得到更加絲滑的輪廓，可以有效減少鋸齒輪廓。

這里約定一種頂點的概念：強制性頂點（Mandatory Vertices），它的含義是區域連接發生變化的頂點，可以看出有兩種頂點：

連接有效區域的邊界邊上的頂點
連接有效區域和無效區域邊界上的頂點

考慮一種特殊情況，可以很容易證明出，并不是所有的區域都有“強制性頂點”，此時如何進行上述算法呢？很簡單，隨便找兩個相對較遠的頂點作為強制性頂點即可。Recast的做法是，使用連接有效區域和無效區域邊界上的頂點，從輪廓點中選擇最左下和最右上的兩個點作為初始簡化點。

區域-區域門戶（region-region portals）的簡化很容易。我們丟棄除強制性頂點（mandatory vertices）之外的所有頂點：

// Add initial points.
bool hasConnections = false;
for (int i = 0; i < points.size(); i += 4)
{// point索引：0=x 1=y 2=z 3=r// 在之前的walkContour中產生，r的低16位如果是0，說明邊界是不可行走的，否則該point有鄰居regionif ((points[i+3] & RC_CONTOUR_REG_MASK) != 0){hasConnections = true;break;}
}// 如果輪廓有鄰居region
if (hasConnections)
{for (int i = 0, ni = points.size()/4; i < ni; ++i){//下一個pointint ii = (i+1) % ni;//鄰近的兩個輪廓點接壤不同的regionconst bool differentRegs = (points[i*4+3] & RC_CONTOUR_REG_MASK) != (points[ii*4+3] & RC_CONTOUR_REG_MASK);//鄰近的兩個輪廓點里，一個接壤其他region，另一個接壤不可行走const bool areaBorders = (points[i*4+3] & RC_AREA_BORDER) != (points[ii*4+3] & RC_AREA_BORDER);// 總之鄰近的兩個輪廓點接壤不是同一個region，則記錄這個點if (differentRegs || areaBorders){simplified.push(points[i*4+0]);simplified.push(points[i*4+1]);simplified.push(points[i*4+2]);simplified.push(i);}}
}

幫助我們找到初始的簡化點。

// 如果不連接任何region則沒有simplified點，那么選擇左下和右上的兩個點作為simplified點
if (simplified.size() == 0)
{int llx = points[0];int lly = points[1];int llz = points[2];int lli = 0;int urx = points[0];int ury = points[1];int urz = points[2];int uri = 0;for (int i = 0; i < points.size(); i += 4){int x = points[i+0];int y = points[i+1];int z = points[i+2];if (x < llx || (x == llx && z < llz)){llx = x;lly = y;llz = z;lli = i/4;}if (x > urx || (x == urx && z > urz)){urx = x;ury = y;urz = z;uri = i/4;}}simplified.push(llx);simplified.push(lly);simplified.push(llz);simplified.push(lli);simplified.push(urx);simplified.push(ury);simplified.push(urz);simplified.push(uri);
}

根據maxSimplificationError參數來決定丟棄哪些頂點以得到簡化的線段——代表網格的邊可以偏離源幾何體的最大距離，較低的值將導致網格邊緣更準確地遵循 xz 平面的幾何輪廓，但會增加三角形數量。
不建議將值設為0，因為它會導致最終網格中的多邊形數量大幅增加，處理成本很高。

現在從強制頂點（mandatory vertices）開始，將最遠頂點添加回來，這樣原始頂點與簡化邊之間的距離都不會超過maxSimplificationError。

下面的圖中展示這一過程：

首先找到左下和右上兩個點

如果簡化后的邊長度超過了maxSimplificationError我們把離簡化邊最遠的點加回來。

重復這個過程，直到不再有頂點到簡化邊的距離超過允許值：

相關代碼：

// Add points until all raw points are within
// error tolerance to the simplified shape.
const int pn = points.size()/4;
for (int i = 0; i < simplified.size()/4; )
{int ii = (i+1) % (simplified.size()/4);// simplified索引：0=x 1=y 2=z 3=在points中的索引int ax = simplified[i*4+0];int az = simplified[i*4+2];int ai = simplified[i*4+3];int bx = simplified[ii*4+0];int bz = simplified[ii*4+2];int bi = simplified[ii*4+3];// Find maximum deviation from the segment.float maxd = 0;int maxi = -1;// ci、endi為points中的索引，cinc為索引每次遍歷的偏移方向// ci=從此索引開始遍歷，endi=從此索引遍歷結束int ci, cinc, endi;// 選擇偏左下的點為遍歷的起點，偏右上的點為遍歷的終點if (bx > ax || (bx == ax && bz > az)){// 沿著正方向cinc = 1;ci = (ai+cinc) % pn;endi = bi;}else{// 沿著負方向cinc = pn-1;ci = (bi+cinc) % pn;endi = ai;rcSwap(ax, bx);rcSwap(az, bz);}// 考慮有效區域和有效區域連接，或者有效區域和空區域的邊界情況. if ((points[ci*4+3] & RC_CONTOUR_REG_MASK) == 0 ||(points[ci*4+3] & RC_AREA_BORDER)){while (ci != endi){//計算點到直線的距離float d = distancePtSeg(points[ci*4+0], points[ci*4+2], ax, az, bx, bz);if (d > maxd){maxd = d;maxi = ci;}ci = (ci+cinc) % pn;}}// 找到離簡化邊最遠的點，如果它到簡化輪廓的距離超過了maxError，則將頂點添加回輪廓if (maxi != -1 && maxd > (maxError*maxError)){// Add space for the new point.simplified.resize(simplified.size()+4);const int n = simplified.size()/4;for (int j = n-1; j > i; --j){simplified[j*4+0] = simplified[(j-1)*4+0];simplified[j*4+1] = simplified[(j-1)*4+1];simplified[j*4+2] = simplified[(j-1)*4+2];simplified[j*4+3] = simplified[(j-1)*4+3];}// Add the point.simplified[(i+1)*4+0] = points[maxi*4+0];simplified[(i+1)*4+1] = points[maxi*4+1];simplified[(i+1)*4+2] = points[maxi*4+2];simplified[(i+1)*4+3] = maxi;}else{++i;}
}

效果如圖：

長邊輪廓二分為短邊

區域-區域之間的輪廓已經簡化完成了，而針對區域-空區域之間的輪廓簡化還有別的做法：使用maxEdgeLen參數重新插入頂點，以確保沒有線段超過最大長度，它是通過檢測長邊，然后將它們分成兩半來實現這一點的。它會繼續這個過程，直到檢測不到過長的邊為止。

// Split too long edges.
if (maxEdgeLen > 0 && (buildFlags & (RC_CONTOUR_TESS_WALL_EDGES|RC_CONTOUR_TESS_AREA_EDGES)) != 0)
{for (int i = 0; i < simplified.size()/4; ){const int ii = (i+1) % (simplified.size()/4);const int ax = simplified[i*4+0];const int az = simplified[i*4+2];const int ai = simplified[i*4+3];const int bx = simplified[ii*4+0];const int bz = simplified[ii*4+2];const int bi = simplified[ii*4+3];// Find maximum deviation from the segment.int maxi = -1;int ci = (ai+1) % pn;// Tessellate only outer edges or edges between areas.bool tess = false;// Wall edges. 不可行走邊界if ((buildFlags & RC_CONTOUR_TESS_WALL_EDGES) && (points[ci*4+3] & RC_CONTOUR_REG_MASK) == 0)tess = true;// Edges between areas. region邊界if ((buildFlags & RC_CONTOUR_TESS_AREA_EDGES) && (points[ci*4+3] & RC_AREA_BORDER))tess = true;if (tess){int dx = bx - ax;int dz = bz - az;if (dx*dx + dz*dz > maxEdgeLen*maxEdgeLen)  //線段超過最大長度maxEdgeLen，就分為兩個線段{// Round based on the segments in lexilogical order so that the// max tesselation is consistent regardles in which direction// segments are traversed.const int n = bi < ai ? (bi+pn - ai) : (bi - ai);// ai與bi相差n個索引if (n > 1) // n > 1，說明ai bi之間有輪廓點，可切分{if (bx > ax || (bx == ax && bz > az))maxi = (ai + n/2) % pn;elsemaxi = (ai + (n+1)/2) % pn;}}}// If the max deviation is larger than accepted error,// add new point, else continue to next segment.if (maxi != -1)  // maxi位置的點插入到simplified中{// Add space for the new point.simplified.resize(simplified.size()+4);const int n = simplified.size()/4;for (int j = n-1; j > i; --j){simplified[j*4+0] = simplified[(j-1)*4+0];simplified[j*4+1] = simplified[(j-1)*4+1];simplified[j*4+2] = simplified[(j-1)*4+2];simplified[j*4+3] = simplified[(j-1)*4+3];}// Add the point.simplified[(i+1)*4+0] = points[maxi*4+0];simplified[(i+1)*4+1] = points[maxi*4+1];simplified[(i+1)*4+2] = points[maxi*4+2];simplified[(i+1)*4+3] = maxi;}else{++i;}}
}

檢查和合并空洞

首先我們要檢查空洞（為什么還要考慮空洞問題呢？在Recast Navigation中，?輪廓生成后仍需檢查空洞，根本原因在于區域劃分階段無法完全消除所有空洞風險，且輪廓生成過程可能引入新的空洞問題）。

首先我們要知道一個關于三角形叉乘和面積的關系：如果是順時針方向，求取的面積值是負的，如果是逆時針方向，求取的面積值是正的。

而正常輪廓線的頂點是順時針存儲，空洞輪廓線的頂點是逆時針存儲（在查找輪廓中完成）：

所以根據叉乘算出每個輪廓多邊形的有向面積，如果結果為小于0，則為輪廓點的順序為逆時針，這個輪廓就是一個空洞。

int nholes = 0;
for (int i = 0; i < cset.nconts; ++i)
{rcContour& cont = cset.conts[i];// If the contour is wound backwards, it is a hole.winding[i] = calcAreaOfPolygon2D(cont.verts, cont.nverts) < 0 ? -1 : 1;if (winding[i] < 0)nholes++;
}

現在我們找到空洞之后，就要去合并空洞：

找到空洞的左下方頂點B4
將輪廓線所有頂點與B4相連，如果連線與輪廓線、空洞都不相交，則連線構成1條對角線。上圖滿足條件的有A5B4，A5B4，A4B4
選擇其中長度最短的1條對角線A5B4，將空洞合并到輪廓線中

最終輪廓線的頂點序列為A5、A6、A1、A2、A3、A4、A5、B4、B1、B2、B3、B4。(如果包含多個空洞的話，將空洞按左下方頂點排序，依次迭代將外圍輪廓與空洞進行合并。)

階段總結

在這個階段結束時，我們有形成簡化多邊形的輪廓。頂點仍然在體素空間中，但是我們正在回到向量空間的路上。

凸多邊形生成（Convex Polygon Generation）

有了輪廓的數據之后，就有了一片區域的邊，那么此時就需要對區域進行更加詳細的定位，例如尋路是要具體尋到某一個點，并且區域內部任意兩點并不是一定直線聯通的，所以要將區域劃分成更加細化的可以描述整個區域面的信息的數據。此時采用的是將區域劃分成一些凸多邊形的集合，這些凸多邊形的并集就是整個區域。本階段是從由輪廓表示的簡單多邊形生成凸多邊形。這也是我們從體素空間回到向量空間的地方。

本階段的主要任務如下：

輪廓的頂點在體素空間中，這意味著它們的坐標采用整數格式并表示到高度場原點的距離。因此輪廓頂點數據被轉換為原始源幾何體的向量空間坐標。
每個輪廓完全獨立于所有其他輪廓。在此階段，我們合并重復的數據并將所有內容合并到一個單一網格中。
輪廓只能保證表示簡單的多邊形，包括凸多邊形和凹多邊形。凹多邊形對導航網格來說是沒有用的（凸多邊形中，任意兩點間的直線路徑必然完全位于多邊形內部，確保AI移動時不會穿越障礙物。而凹多邊形存在“凹陷”區域（內角>180°），兩點間的直線可能穿出多邊形邊界，進入未知區域（如墻體或懸崖），導致路徑失效或角色卡死），所以我們根據需要細分輪廓以獲得凸多邊形。
我們收集指示每個多邊形的哪些邊連接到另一個多邊形的連接信息（多邊形鄰居信息）。

坐標轉換和頂點數據合并是相對簡單的過程，所以我不會在這里討論它們。如果您對這些算法感興趣，可以查看文檔詳盡的源代碼。這里我們將專注于凸多邊形的細分。對每個輪廓會執行以下步驟：

對每個輪廓進行三角面化（triangulate）。
合并三角形以形成最大可能的凸多邊形。

我們通過生成鄰居連接信息來結束這個階段。

三角形剖分（Triangulation）

針對凹多邊形的三角劃分：耳裁法（為什么這里又是針對凹多邊形呢？其實這個方法也適用于凸多邊形而且更簡單）

每次迭代凹多邊形，將其分成兩部分，一個三角形和剩余的部分。然后迭代“剩余的部分”，繼續劃分，直到沒有三角形可以劃分位置。
算法的核心點是如何對每次的“剩余多邊形”劃分出一個三角形。
采用的方法很簡單，基于“任意不共線三點構成三角形”的理論，每次尋找多邊形相鄰的兩條邊，如果其不共直線，那么連接這兩條邊的三個端點，就可以形成一個三角形。
但是需要注意的是，這樣形成的三角形可能會是多邊形外部的，注意區分剔除即可。

從所有潛在的候選者中，選擇具有最短的新邊的那個。新邊被稱為“分割邊”（partition edges），或簡稱為“分割”（partition）。該過程繼續處理剩余的頂點，直到三角形剖分完成。

為了提高性能，三角形剖分在輪廓的 xz 平面投影上運行。

首先我們要構建可能的切割邊：
三角形剖分是通過沿著輪廓的邊往前走（walking the edges of the contour）來完成的，以任意端點開始，沿著一個方向依次去找兩個邊，如果兩個邊不共線，則連接兩邊不重合的點，形成一條連線，稱為“分割邊”。對每一個點進行該過程，會形成很多分割邊，剔除那些在多邊形外部的分割邊，剩余的就是有效分割邊。

在上述所有有效分割邊中，找出一條最短的分割邊，然后將該分割邊與“形成該分割邊的其他兩條多邊形邊”形成一個三角形。此時就將凹多邊形劃分出了一個三角形。剩余多邊形繼續重新劃分“分割邊”(每進行一次分割就要重新分割)，重復該過程即可。

使用最短分割邊的原因是，在概率上試圖每次分出去一個盡可能小的三角形，以此增加最終分割的三角形的數量，進而增強分割后的信息量。

相關代碼：

/// 三角形剖分
/// n verts頂點個數
/// verts 頂點數據
/// indices 頂點索引
/// tris 三角形的索引
/// 返回值 三角形的個數
static int triangulate(int n, const int* verts, int* indices, int* tris)
{int ntris = 0;int* dst = tris;// The last bit of the index is used to indicate if the vertex can be removed.for (int i = 0; i < n; i++){int i1 = next(i, n);int i2 = next(i1, n);//i1 是一個耳尖點，并且與所有的邊都不相交if (diagonal(i, i2, n, verts, indices))indices[i1] |= 0x80000000;}while (n > 3){int minLen = -1;int mini = -1;// 找最小的耳朵for (int i = 0; i < n; i++){int i1 = next(i, n);if (indices[i1] & 0x80000000){// i1是耳尖點，找到最小的p0到p2的距離const int* p0 = &verts[(indices[i] & 0x0fffffff) * 4];const int* p2 = &verts[(indices[next(i1, n)] & 0x0fffffff) * 4];int dx = p2[0] - p0[0];int dy = p2[2] - p0[2];int len = dx*dx + dy*dy;if (minLen < 0 || len < minLen){minLen = len;mini = i;}}}if (mini == -1){// We might get here because the contour has overlapping segments, like this:////  A o-o=====o---o B//   /  |C   D|    \.//  o   o     o     o//  :   :     :     :// We'll try to recover by loosing up the inCone test a bit so that a diagonal// like A-B or C-D can be found and we can continue.minLen = -1;mini = -1;for (int i = 0; i < n; i++){int i1 = next(i, n);int i2 = next(i1, n);if (diagonalLoose(i, i2, n, verts, indices)){const int* p0 = &verts[(indices[i] & 0x0fffffff) * 4];const int* p2 = &verts[(indices[next(i2, n)] & 0x0fffffff) * 4];int dx = p2[0] - p0[0];int dy = p2[2] - p0[2];int len = dx*dx + dy*dy;if (minLen < 0 || len < minLen){minLen = len;mini = i;}}}if (mini == -1){// The contour is messed up. This sometimes happens// if the contour simplification is too aggressive.return -ntris;}}int i = mini;int i1 = next(i, n);int i2 = next(i1, n);*dst++ = indices[i] & 0x0fffffff;*dst++ = indices[i1] & 0x0fffffff;*dst++ = indices[i2] & 0x0fffffff;ntris++;// Removes P[i1] by copying P[i+1]...P[n-1] left one index.n--;for (int k = i1; k < n; k++)indices[k] = indices[k+1];if (i1 >= n) i1 = 0;i = prev(i1,n);// Update diagonal flags.// 判斷i點是否為耳尖點if (diagonal(prev(i, n), i1, n, verts, indices))indices[i] |= 0x80000000;elseindices[i] &= 0x0fffffff;// 判斷i1點是否為耳尖點if (diagonal(i, next(i1, n), n, verts, indices))indices[i1] |= 0x80000000;elseindices[i1] &= 0x0fffffff;}// Append the remaining triangle.// 把最后的三個點加入到tris*dst++ = indices[0] & 0x0fffffff;*dst++ = indices[1] & 0x0fffffff;*dst++ = indices[2] & 0x0fffffff;ntris++;return ntris;
}

這里還得補充一下檢測有效分割邊的做法：

使用內角算法和邊相交算法，兩種算法來確定一組三個頂點是否可以形成有效的內部三角形。第一種算法（內角算法）很快，可以快速剔除完全位于多邊形之外的分割邊。如果分割邊在多邊形內部，則使用更昂貴的算法來確保它不與任何現有多邊形的邊相交。

合并為凸多邊形（凸多邊形化）

合并只能發生在從單個輪廓創建的多邊形之間。不會嘗試合并來自相鄰輪廓的多邊形。

請注意，我已切換到一般形式的“多邊形”（polygon）而不是三角形（triangle）。雖然初始合并將在三角形之間進行，但隨著合并過程的進行，非三角形多邊形可能會相互合并。

該過程如下：

找出所有可以合并的多邊形。
從該列表中，選擇共享邊最長的兩個多邊形并將它們合并。
重復這個過程直到沒有可以進行的合并。

如果滿足以下所有條件，則可以合并兩個多邊形：

多邊形共享一條邊。
合并后的多邊形仍然是凸多邊形。
合并后的多邊形的邊數不會超過maxVertsPerPoly

為什么是最長邊：這是一種“偽貪心”思想，試圖從概率上使每次合并的多邊形更大，從而減少合并后多邊形的數量，數量越少，后續的Detour算法越簡單。

如何確定合并后的多邊形是否為凸多邊形：此檢查的關鍵就是保證合并后的多邊形所有內角不超過180度。

合并多邊形ABC和多邊形ADC，兩者的公共邊是AC，前提條件是，∠ABC和∠ADC都是小于180度的。問題是證明合并后的∠BAD和∠BCD在什么情況下會小于180度，在什么情況下會大于180度。

采用的方式是，連接BD作為參考線。BD產生的條件，從公共邊兩端點中選擇一點A，點A在兩個多邊形中分別有兩條邊，選擇不是公共邊的那一條，即圖中的AB和AD作為“校驗邊”，此時連接兩條校驗邊的另外一個端點B和D，形成參考線。

形成參考線后，只需要保證公共邊兩端點分屬在參考線的兩側，即證明以剛才選擇點A所形成的內角∠BAD是一個小于180度的角。

然后再以公共邊另外一個端點C重復上述過程，證明∠BCD是否滿足條件。

其實很好理解，用公共邊一個端點和參考線一定可以形成一個三角形，只需要判斷這個三角形的當前內角是合并多邊形的內角還是外角就可以了。而當公共邊的兩端點在參考線兩側的時候，恰好對應的是內角。至于以公共邊的兩端點來進行這個校驗，是因為我們保證了，合并之前的多邊形都是凸多邊形，意味著所有不參與合并的角本來就是滿足條件的，不需要檢查了，而參與合并的角，就是公共邊兩端點的角。

一定要理解：上述算法的所有思路，都是建立在合并之前的兩個多邊形都是凸多邊形的基礎上。

// Merge polygons.
if (nvp > 3)
{for(;;){// Find best polygons to merge.int bestMergeVal = 0; //共邊的長度值int bestPa = 0, bestPb = 0, bestEa = 0, bestEb = 0;for (int j = 0; j < npolys-1; ++j){         unsigned short* pj = &polys[j*nvp];for (int k = j+1; k < npolys; ++k){unsigned short* pk = &polys[k*nvp];int ea, eb;// 返回可合并的邊的長度int v = getPolyMergeValue(pj, pk, mesh.verts, ea, eb, nvp);// 找到最長的邊進行合并if (v > bestMergeVal){bestMergeVal = v;bestPa = j;bestPb = k;bestEa = ea;bestEb = eb;}}}if (bestMergeVal > 0){// Found best, merge.unsigned short* pa = &polys[bestPa*nvp];unsigned short* pb = &polys[bestPb*nvp];//pa和pb合并成一個，最后放到pa里mergePolyVerts(pa, pb, bestEa, bestEb, tmpPoly, nvp);//最后的poly放到pbunsigned short* lastPoly = &polys[(npolys-1)*nvp];if (pb != lastPoly)memcpy(pb, lastPoly, sizeof(unsigned short)*nvp);npolys--;}else{// Could not merge any polygons, stop.break;}}
}

構建邊的鄰接關系

雖然有了凸多邊形信息，但是每個凸多邊形的鄰接關系是不知道的，因此這一步的目的就是要遍歷整個網格中的所有多邊形并生成鄰接信息（connection information），方便后續尋路使用。

struct rcEdge
{unsigned short vert[2];     // 邊的兩個點unsigned short polyEdge[2]; // 鄰接的兩個多邊形的邊的索引unsigned short poly[2];     // 鄰接的兩個多邊形的索引
};

這是鄰接邊的數據結構。

遍歷多邊形，初始化邊信息rcEdge，每條邊兩個頂點的索引v0、索引v1，保證v0<v1
再進行一次遍歷，這次篩選出頂點索引v0 > 頂點索引v1形成的邊，如果兩個頂點與某個rcEdge相同，則補全rcEdge的鄰接信息
最后把rcEdge信息保存到mesh.polys中，每個poly用長度為2*maxVertsPerPoly的short表示，[0, maxVertsPerPoly)表示多邊形的頂點索引，[maxVertsPerPoly, 2*maxVertsPerPoly)表示頂點鄰接的多邊形索引

階段總結

許多算法只能用于凸多邊形。因此，這一步將構成輪廓的簡單多邊形細分為凸多邊形網格。這是通過使用一個適用于簡單多邊形的三角形劃分（triangulation），然后再將三角形合并為最大可能的凸多邊形來實現的。

?詳細網格生成（Detailed Mesh Generation）

構建導航網格的第五個也是最后一個階段，即生成具有詳細高度信息的三角形網格。

為什么要執行這一步？

在三維空間中，多邊形網格可能無法充分遵循源網格的高度輪廓，無論拆分單元的粒度有多小，都不可能完全擬合原實物空間，總是存在誤差。而經過多步針對“體素塊”的操作后，這些誤差可能被放大，導致了Mesh導航面其實只是“原場景”的一個“大概表面”。比如樓梯。此時就需要，在Mesh多邊形的基礎上，去對比“原場景表面”，然后對Mesh多邊形進行再加工——添加高度細節，使其最大限度的貼合原場景表面，減少誤差。

該階段的主要步驟如下，對于每個多邊形：

對多邊形的外殼邊緣（hull edges）進行采樣。向任何偏離高度補丁數據超過detailSampleMaxError的邊添加頂點。
對多邊形執行Delaunay 三角形剖分。
對多邊形的內部表面進行采樣。如果表面與高度補丁數據的偏差超過 detailSampleMaxError的值，則添加頂點。更新新頂點的三角形剖分。

這個階段增加了高度細節，這樣細節網格（detail mesh）將在所有軸上與源網格的表面相匹配。為了實現這一點，我們遍歷所有多邊形，并在多邊形與源網格過度偏離時沿著多邊形的邊和其表面插入頂點。

從技術上來講，從尋路的角度來看，這一步不是必需的。凸多邊形網格是生成適合使用尋路算法的圖所需要的全部，而在上一階段創建的多邊形網格提供了所有必要的數據。這尤其適用于使用物理或ray-casting將agent放置在源網格表面的情況。事實上，Recast Navigation的Detour庫只使用多邊形網格來尋路。這個階段生成的高度細節被認為是可選的，當包含它時，它僅用于完善由各種Detour函數返回的點的位置。

同樣重要的是要注意，這個過程仍然只會產生原始網格表面的一個更好的近似。體素化過程已經決定了精確的位置是不可能的。除此之外，由于搜索性能和內存的考慮，過多的高度細節通常比太少的細節更糟糕。

因為CSDN現在又非常卡了，加上這部分內容并不是必須的，容我偷個懶就不介紹這部分的內容了，大家有興趣的可以去看知乎原文：(99+ 封私信 / 80 條消息) Recast Navigation源碼分析：導航網格Navmesh的生成原理 - 知乎 (zhihu.com)

?這篇文章里還提到了關于NavMesh里的一些缺點：

（1）RecastNavigation所有操作都基于地表面，因此，對空中的對象的交互，用它是無法完成的。現在國產武俠類 MMORPG 里大行其道的輕功、甚至御劍飛行，是無法只單純依賴 RecastNavigation 的數據去實現的。特別是對于某些具有層次錯落結構的地形，就非常容易出現掉到兩片導航網格的夾縫里的情況。這類機制的實現需要其他場景數據的支持，通常這時會結合其他引擎，如physx

（2）像《塞爾達傳說：曠野之息》的爬山、《忍者龍劍傳》的踩墻這種機制，則會在生成導航網格的階段就會遇到麻煩。因為設計前提2的存在，RecastNavigation 是無法對與地面夾角小于或等于90°的墻面生成導航網格的。因此需要從另外的機制、設計上去規避或處理。不過，Unity 2017 已經可以支持了在各種角度的墻面生成導航網格了：Ceiling and Wall Navigation in Unity3D

當然，這篇文章成文時間是22年，很有可能他說的這些內容都已經實現了。我去翻了下原作者的其他文章，他顯然食言了呀，沒有做Recast Navigation后續的內容了，只有關于構建導航網絡的解析，我后續會繼續研究NavMesh的內容的，就放在后續來講解吧。