NavMesh的生成原理

本篇內容介紹了“NavMesh的生成原理”的有關知識，在實際案例的操作過程中，不少人都會遇到這樣的困境，接下來就讓小編帶領大家學習一下如何處理這些情況吧！希望大家仔細閱讀，能夠學有所成！

簡述

本篇文章介紹了NMGen的核心處理流程。NMGen用于生成多邊形數據，代表了導航網格的表面。有很多種網格生成方式，但是他們都包含了下面的一些步驟。

主要流程如下所示：

1. 體素化。從源幾何體構造實心的高度場，用來表示不可行走的空間。

2. 生成地區。將實心高度場的上表面中連續的區間合并為地區。

3. 生成輪廓。檢測地區的輪廓，并構造成簡單多邊形。

4. 生成多邊形網格。將輪廓分割成凸多邊形。

5. 生成高度細節。將多邊形網格三角化，得到高度細節。

一、Voxelization（體素化）

核心類：Heightfield

在體素（體素是空間中的一個有大小的點）化階段，源幾何體被轉換成高度場，用來表示不可行走的空間。一些不可走的表面在這個階段會被剔除掉（比如坡度過大的面 ）。

對于源幾何體上的每個三角形，使用“保守體素化算法”（Conservative Voxelization）分割成體素，并加入到高度場中。保守體素化算法確保了每個三角形面，都會被生成的體素完全包圍。

體素化階段后，實心高度場(solid heightfield)包含了很多的區間(span)，覆蓋了源幾何體上的所有面。

二、Region Generation（生成地區）

核心類：CompactHeightfield

這一階段的目標是，近一步定義實體表面上哪部分是可以行走的，以及將這些可行走的部分劃分成連續的地區，這些地區可以最終構成簡單多邊形。

首先，將實心的高度場，轉換成一個開放的高度場(open heightfield)，用來表示實體表面上那些可以行走的部分。一個開放的高度場，表示位于實體空間表面的地表部分。

在下圖中，綠色部分代表開放區間(span)中的地表。這相當于是實心高度場上所有可行走的上表面。注意那些墻，桌子下面的區域，以及走廊扶手上那些比較窄的區域，已經在實心高度場生成的時候被剔除掉了。一些不可行走的區域，比如桌面，樓梯扶手，墻邊較窄的位置，目前仍然顯示為可行走的。

然后，進一步剔除掉不可行走的區域。在計算完成的時候，開放區間中那些認為可以行走的部分，應該通過下面的測試： 
+ 該區域不能緊挨著障礙物(如，墻，家具等)（使用WalkableRadius作為距離閥值） 
+ 該區域在表面之上沒有足夠的開放空間(非碰撞區域)。（人在不碰撞到其他物體的情況下，能夠合法的移動）(使用WalkableHeight作為高度閥值)

為剩下的所有區間生成鄰接信息，用于把他們合并成一個大的面片。該算法使用一個最大垂直步長(WalkableStep4)來決定哪些區間是可以連在一起的。這允許一些特殊的結構能夠被考慮進來，比如樓梯，路邊，桌面等。例如，構成階梯的區間能夠當做鄰居被連接在一起，而桌面上的區間就不能和地板連接在一起。

下圖顯示的是地區。注意看階梯上的那些地區，盡管構成的區間并沒有直接相連。也需要注意那些桌子上，樓梯扶手，以及所有其他實心高度場上不可走的面，在這個階段后已經被成功剔除了(黑色表示被剔除的區間)。

在該階段后，這些相連的地區代表了可行走的面。

三、Contour Generation（生成輪廓）

核心類：ContourSet

輪廓就是沿著地區邊緣“行走”，構成簡單多邊形。這是從體素空間轉換回向量空間的第一步處理。

首先，從地區生成非常精細的多邊形。

然后，使用多種算法來完成下面的步驟：

+ 簡化相鄰多邊形的邊緣（地區之間的部分）

+ 簡化邊界(邊界是沒有鄰接或鄰接了障礙物的輪廓)(EdgeMaxDeviation)

+ 優化邊界的長度。（邊界如果太長，不能得到最優的三角形）

下圖展示了執行此算法后的輪廓

在該階段結尾，簡單多邊形代表了可行走的表面。

四、Convex Polygon Generation（生成凸多邊形）

核心類：PolyMesh

許多算法只能用于凸多邊形。因此，這一步需要把輪廓構成的簡單多邊形轉換成凸多邊形網格。

下圖中，你可以看到由輪廓形成的凸多邊形。

在該階段的結尾，一個凸多邊形網格代表了可以行走的表面。

五、Height Detail Generation（生成高度細節）

核心類：PolyMeshDetail

在這最后的階段，凸多邊形網格會被Delaunay三角化算法三角化，于是可以增加高度的細節。在多邊形的內部或者邊緣添加頂點，來確保網格與原始幾何體表面等價。(DetailSampleDistance和DetailMaxDeviation)

“NavMesh的生成原理”的內容就介紹到這里了，感謝大家的閱讀。如果想了解更多行業相關的知識可以關注億速云網站，小編將為大家輸出更多高質量的實用文章！