NavMesh的生成原理

本篇內(nèi)容介紹了“NavMesh的生成原理”的有關(guān)知識(shí)，在實(shí)際案例的操作過程中，不少人都會(huì)遇到這樣的困境，接下來就讓小編帶領(lǐng)大家學(xué)習(xí)一下如何處理這些情況吧！希望大家仔細(xì)閱讀，能夠?qū)W有所成！

簡述

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

主要流程如下所示：

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

2. 生成地區(qū)。將實(shí)心高度場的上表面中連續(xù)的區(qū)間合并為地區(qū)。

3. 生成輪廓。檢測地區(qū)的輪廓，并構(gòu)造成簡單多邊形。

4. 生成多邊形網(wǎng)格。將輪廓分割成凸多邊形。

5. 生成高度細(xì)節(jié)。將多邊形網(wǎng)格三角化，得到高度細(xì)節(jié)。

一、Voxelization（體素化）

核心類：Heightfield

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

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

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

二、Region Generation（生成地區(qū)）

核心類：CompactHeightfield

這一階段的目標(biāo)是，近一步定義實(shí)體表面上哪部分是可以行走的，以及將這些可行走的部分劃分成連續(xù)的地區(qū)，這些地區(qū)可以最終構(gòu)成簡單多邊形。

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

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

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

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

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

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

三、Contour Generation（生成輪廓）

核心類：ContourSet

輪廓就是沿著地區(qū)邊緣“行走”，構(gòu)成簡單多邊形。這是從體素空間轉(zhuǎn)換回向量空間的第一步處理。

首先，從地區(qū)生成非常精細(xì)的多邊形。

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

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

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

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

下圖展示了執(zhí)行此算法后的輪廓

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

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

核心類：PolyMesh

許多算法只能用于凸多邊形。因此，這一步需要把輪廓構(gòu)成的簡單多邊形轉(zhuǎn)換成凸多邊形網(wǎng)格。

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

在該階段的結(jié)尾，一個(gè)凸多邊形網(wǎng)格代表了可以行走的表面。

五、Height Detail Generation（生成高度細(xì)節(jié)）

核心類：PolyMeshDetail

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

“NavMesh的生成原理”的內(nèi)容就介紹到這里了，感謝大家的閱讀。如果想了解更多行業(yè)相關(guān)的知識(shí)可以關(guān)注億速云網(wǎng)站，小編將為大家輸出更多高質(zhì)量的實(shí)用文章！