用BSP來對游戲中的室內(nèi)場景進(jìn)行分割是一個傳統(tǒng)但卻有效的手段，BSP創(chuàng)建的質(zhì)量決定了BSP在使用時的健壯性，因為之后要使用BSP進(jìn)行渲染、物理交互等操作。創(chuàng)建一個BSP的過程即簡單又煩瑣，雖然邏輯簡單，但是在分割結(jié)點的過程中也會產(chǎn)生不少問題，以下是本人創(chuàng)建BSP時的一些簡單經(jīng)驗總結(jié)。
BSP樹創(chuàng)建流程：
1. 得到場景的多邊形列表(多邊形何種方式組織無關(guān)緊要，只要含有足夠信息即可，我用的是索引。注：此多邊形列表要求有正向面的法線信息或正反面的標(biāo)識)。
2. 判斷當(dāng)前結(jié)點處的多邊形集合是否為凸集，若是則標(biāo)記當(dāng)前結(jié)點為葉子，否則繼續(xù)進(jìn)行下述操作（判斷凸集的方法應(yīng)該選擇分割面的方法相一致，否則相互矛盾容易出現(xiàn)無限分割的情況）。
3. 遍歷當(dāng)前結(jié)點多邊形集合中的所有多邊形所在的平面找到最優(yōu)的分割面(分割平面的選取原則也有很多種，可以自己根據(jù)情況選取，我用的是保證BSP樹的均衡的選取原則)。
4. 標(biāo)記所有與分割平面處于同一平面上的多邊形為已使用，子結(jié)點中不再使用這些多邊形進(jìn)行分割操作
5. 用最優(yōu)分割面對當(dāng)前結(jié)點的多邊形集合進(jìn)行歸類，將對應(yīng)的集合存放到子結(jié)點中（具體的操作應(yīng)與多邊形列表的組織關(guān)系相結(jié)合）。
需要注意的問題：
1. 若當(dāng)前多邊形集合為凸集則其應(yīng)該找不到分割平面，對于一個非凸集的多邊形集合則必能找到了下分割平面（此處情況常出現(xiàn)在分割面的選擇與凸集的判斷不一致的時候）。
2. 對與當(dāng)前分割平面重疊的多邊形的處理：若與當(dāng)前分割面同向，則放于前結(jié)點集合，若與當(dāng)前分割面反向，則放于后結(jié)點集合。
3. 對于一個凸集多邊形集合，則遍歷統(tǒng)計后(對于每個多邊形，與其余的多邊形進(jìn)行位置判斷)：front >= 0 , back = 0 , split = 0 , overlap_samedir >= 0 , overlap_diffdir = 0
4. 最優(yōu)分割面的選擇條件應(yīng)與凸集的判斷條件相一致，否則會出現(xiàn)對于一個非凸集而找不到分割面的錯誤情況。
下圖為一個場景的BSP分割結(jié)果(用面來渲染，不同的顏色表示不同的葉子結(jié)點)：
BSP創(chuàng)建之后即可進(jìn)行Portal的添加操作，待續(xù)。。。
http://blog.csdn.net/bugrunner/article/details/5259174