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樹一樣開始廣泛使用了。

是QUAKE 2用於存儲地圖的一種文件格式，說得具體點，就是用於渲染Q2世界的。儘管有其他的信息包含在BSP文件中，用於其他遊戲部分（如敵人AI，等等），在這篇文章中，我不將討論他們。如果你有這方面的知識，請告訴我，我的E-MAIL在下面。在這篇文章中難免有錯誤之處，請告訴我。

為了更清楚的描述BSP文件格式，在這篇文章中將試圖對Q2渲染引擎進行技術方面的描述，讓我們假想這個渲染器使用的是基本的3D圖形技術，包含BSP樹結構。

我們在這篇文章中描述的是Q2的BSP文件格式，這個文件格式由Kingpin使用（他建立了Q2引擎）。對於Q1和Q3的文件格式，雖然他們很相同，但還是有點不兼容。不管怎樣，BSP的文件結構和技術不是很難，這篇文章將對於那些對這些格式感興趣的人。"