上回說到將空間內(nèi)的span都打上了區(qū)域標(biāo)記
到目前為止，可行走區(qū)域都是以span為粒度表示的（一個(gè)一個(gè)的小方格），現(xiàn)在我們要根據(jù)區(qū)域標(biāo)記來合并這些“小方格”，形成整片的連續(xù)區(qū)域
Step 5. Trace and simplify region contours.
a.遍歷緊縮高度場中的span,根據(jù)regid（區(qū)域標(biāo)記）求出每個(gè)span與周圍相鄰span的區(qū)域關(guān)系，用一個(gè)4位的2進(jìn)制數(shù)來表示：
若與某個(gè)方向的鄰居區(qū)域相同，則對(duì)應(yīng)的標(biāo)記記為0，這樣最后得到的flag若為0，則表示是一個(gè)區(qū)域內(nèi)部的span(4面都是自己人),否則就是一個(gè)區(qū)域邊界上的span
這樣處理完之后，就明確知道了哪些span是區(qū)域的邊界
這里要特別區(qū)分一個(gè)咬文嚼字的問題：
“區(qū)域的邊界”和“邊界區(qū)域”是兩個(gè)不同的概念。邊界區(qū)域在recast中的定義為：
the region is a border region and its spans are considered unwalkable.
是整個(gè)包圍盒外面的4塊區(qū)域，被認(rèn)為是不可行走的
b.遍歷所有作為區(qū)域邊界的span，在遍歷的過程中得到區(qū)域邊界的輪廓頂點(diǎn)集
具體流程是這樣的：
以一個(gè)邊界span作為起始位置，順時(shí)針方向判斷它的4條邊：
若當(dāng)前邊是區(qū)域分界邊，則將邊的一個(gè)頂點(diǎn)加入到輪廓頂點(diǎn)集中，并繼續(xù)判斷下一條邊
若當(dāng)前邊不是區(qū)域分界邊，則移動(dòng)到與這條邊相鄰的span中（這個(gè)span是在同一個(gè)區(qū)域內(nèi)），重新判斷新的span的邊
具體的實(shí)現(xiàn)在這個(gè)函數(shù)中
static void walkContour(int x, int y, int i,
rcCompactHeightfield& chf,
unsigned char* flags, rcIntArray& points)
rcIntArray& points是輸出的輪廓頂點(diǎn)集，每個(gè)元素是一個(gè)四元組：(x,y,z,r)
特別注意這里的第四個(gè)參數(shù)，r表示對(duì)應(yīng)的鄰接區(qū)域id以及一些附加細(xì)節(jié)信息（是否是邊界區(qū)域的頂點(diǎn)、是否是區(qū)域邊界頂點(diǎn)）
頂點(diǎn)的xz坐標(biāo)好處理，高度值y的計(jì)算是通過這個(gè)函數(shù)
static int getCornerHeight(int x, int y, int i, int dir,
const rcCompactHeightfield& chf,
bool& isBorderVertex)
它做的事情是考慮以一個(gè)頂點(diǎn)為中心的4塊相鄰格子的span，取這4個(gè)span中高度最高的span作為頂點(diǎn)高度
（注意下圖是一開始的實(shí)心高度域，鐵子們自行腦補(bǔ)一下緊縮高度域）
c.執(zhí)行完walkContour后就得到了輪廓頂點(diǎn)集，但是這個(gè)集合中的點(diǎn)可能非常多（區(qū)域是基于體素的粒度，所以現(xiàn)在的邊是由許多長度為體素格子邊長的短邊拼接成的）
所以需要簡化輪廓線
有兩個(gè)頂點(diǎn)集：
rcIntArray points 原始輪廓頂點(diǎn)集合
rcIntArray simplified 簡化頂點(diǎn)集合(需要保留下來的點(diǎn))
簡化的策略是：
首先不同區(qū)域的過渡點(diǎn)需要保留，放到simplified中
然后對(duì)于simplified中的每個(gè)相鄰點(diǎn)對(duì)(假設(shè)記為AB)，檢查points中位置在AB之間的點(diǎn)，若這些點(diǎn)到AB的距離大于某個(gè)值maxError
則將其中距離最遠(yuǎn)的點(diǎn)加入到simplified中，重復(fù)這個(gè)過程直到所有點(diǎn)距離簡化的輪廓線都不超過maxError
至此我們就將體素方格化表示的可行走區(qū)域轉(zhuǎn)化成了由頂點(diǎn)集合表示
