二叉空间分割

在 计算机科学中，二叉空间分割（英語：Binary space partitioning，简称BSP）是一种通过使用超平面作为分割，递归细分空间为两凸集的算法。这个过程将空间细分转化为了树结构，即所谓的二叉空间分割树（BSP树）。

二叉空间分割树（BSP tree）的生成过程

二叉空间分割算法是在1969年为3D计算机图形所开发，^[1]其结构使得场景中的物体包含有额外用于渲染的空间信息，例如可以将物体对象针对观察者位置快速的从前至后进行排序。其他BSP的应用包括：在 CAD中执行几何行动与形状(构造实体几何)，机器人技术和3D游戏中的碰撞探测，光线追踪和其他涉及处理复杂的空间场景的情形。

1993年，毁灭战士首次在游戏中使用二叉空间分割算法，此前John Carmack使用了最有效的1991年算法，通过使用专门的数据结构来记录屏幕上已经绘制的部分内容来描述前后渲染。在此之前，德军总部3D使用了光线投射。雷神之锤在1992年利用了一个能生成潜在可见集的预处理步骤开发。

参考文献

1. Schumacker, Robert A.; Brand, Brigitta; Gilliland, Maurice G.; Sharp, Werner H. Study for Applying Computer-Generated Images to Visual Simulation (报告). U.S. Air Force Human Resources Laboratory: 142. 1969. AFHRL-TR-69-14.