BSP（二叉空間分割Binary Space Partitioning）樹是另一種類型的空間分割技術，在遊戲工業上套用了，Doom是第一個使用BSP樹的商業遊戲。
基本介紹
- 中文名：二叉空間分割
- 外文名：Binary Space Partitioning
套用範圍,使用原理,BSP檔案格式,
套用範圍
儘管在今天BSP樹已經沒像過去那么受歡迎了，在廣泛地採用這項技術。當你看一下BSP在碰撞檢測方面那極度乾淨漂亮和高速的效率，立刻能讓你眼前一亮。不但BSP樹在多邊形剪下方面表現出色，而且還能讓我們有效地自由運用world-object式的碰撞檢測。BSP樹的遍歷是使用BSP的一個基本技術。碰撞檢測本質上減少了樹的遍歷或搜尋。這種方法很有用因為它能在早期排除大量的多邊形，所以在最後我們僅僅是對少數面進行碰撞檢測。
使用原理
正如我前面所說的，用找出兩個物體間的分隔面的方法適合於判斷兩個物體是否相交。如果分隔面存在，就沒有發生碰撞。因此我們遞歸地遍歷world樹並判斷分割面是否和包圍球或包圍盒相交。我們還可以通過檢測每一個物體的多邊形來提高精確度。進行這種檢測最簡單的一個方法是測試看看物體的所有部分是否都在分割面的一側。這種運算真的很簡單，我們用迪卡爾平面等式 ax + by + cz + d = 0 去判斷點位於平面的哪一側。如果滿足等式，點在平面上；如果ax + by + cz + d > 0那么點在平面的正面；如果ax + by + cz + d < 0點在平面的背面。
在碰撞沒發生的時候有一個重要的事情需要注意，就是一個物體（或它的包圍盒）必須在分割面的正面或背面。如果在平面的正面和背面都有頂點，說明物體與這個平面相交了。
不幸的是，我們還沒有一個很好的方法檢測在一個時間間隔內的碰撞。然而，我已經看到有另外的數據結構像BSP樹一樣開始廣泛使用了。
BSP檔案格式
是QUAKE 2用於存儲地圖的一種檔案格式，說得具體點，就是用於渲染Q2世界的。儘管有其他的信息包含在BSP檔案中，用於其他遊戲部分（如敵人AI，等等），在這篇文章中，我不將討論他們。如果你有這方面的知識，請告訴我，我的E-MAIL在下面。在這篇文章中難免有錯誤之處，請告訴我。
為了更清楚的描述BSP檔案格式，在這篇文章中將試圖對Q2渲染引擎進行技術方面的描述，讓我們假想這個渲染器使用的是基本的3D圖形技術，包含BSP樹結構。
