User:RyuBAI/二叉空间分割

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

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

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

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

概述

[[Category:带有C代码示例的条目]] [[Category:三维计算机图形学]] [[Category:二叉树]]