二叉空間分割

二叉空間分割樹（BSP tree）的生成過程

在 計算機科學中，二叉空間分割（英語：Binary space partitioning，簡稱BSP）是一種通過使用超平面作為分割，遞歸細分空間為兩凸集的算法。這個過程將空間細分轉化為了樹結構，即所謂的二叉空間分割樹（BSP樹）。

二叉空間分割算法是在1969年為3D計算機圖形所開發，其結構使得場景中的物體包含有額外用於渲染的空間信息，例如可以將物體對象針對觀察者位置快速的從前至後進行排序。其他BSP的應用包括：在 CAD中執行幾何行動與形狀(構造實體幾何)，機器人技術和3D遊戲中的碰撞探測，光線追蹤和其他涉及處理複雜的空間場景的情形。

1993年，毀滅戰士首次在遊戲中使用二叉空間分割算法，此前John Carmack使用了最有效的1991年算法，通過使用專門的資料結構來記錄屏幕上已經繪製的部分內容來描述前後渲染。在此之前，德軍總部3D使用了光線投射。雷神之錘在1992年利用了一個能生成潛在可見集的預處理步驟開發。