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