数据结构
网络
RDBMS
操作系统
Java
MS Excel
iOS
HTML
CSS
Android
Python
C语言编程
C++
C#
MongoDB
MySQL
Javascript
PHP
物理学
化学
生物学
数学
英语
经济学
心理学
社会学
时尚研究
法律研究数据结构中的BSP树
在计算机科学中，二进制空间分割（BSP）是一种方法，它通过使用超平面作为分割来递归地将空间细分为两个凸集。这种细分过程产生了对象在区域内表示为树形数据结构（称为BSP树）的形式。
二进制空间分割发明于1969年，当时是在3D计算机图形学的背景下发明的，其中BSP树的结构允许快速访问场景中对象的有关空间的信息，这些信息在渲染中很有用，例如相对于给定位置的观察者的对象从前到后的排序。BSP的其他应用包括：在CAD中对形状进行几何运算（构造实体几何），3D视频游戏和机器人技术中的碰撞检测，光线追踪以及其他涉及处理复杂空间场景的应用。
概述
二进制空间分割被视为一种递归地划分场景为两部分的通用过程，直到划分满足一个或多个要求。它可以被视为其他空间树结构（如k-d树和四叉树）的泛化，其中用于划分空间的超平面可以具有任何方向，而不是像k-d树或四叉树那样与坐标轴对齐。当在计算机图形学中实现以渲染由平面多边形组成的场景时，划分平面通常选择与场景中多边形定义的平面重合。划分平面的具体选择和完成划分过程的标准取决于BSP树的目的。例如，在计算机图形渲染中，场景被划分，直到且除非BSP树的每个节点仅包含可以以任意顺序渲染的多边形。当实现背面剔除时，因此每个节点都包含一组凸多边形，而当渲染双面多边形时，BSP树的每个节点仅包含单个平面中的多边形。在碰撞检测或光线追踪中，场景可以细分为一些易于进行碰撞或光线相交测试的基元。
生成
BSP树的典型实现是使用画家算法渲染多边形（即双面多边形，即没有背面剔除）。每个多边形都指定了一个正面和一个背面，可以任意选择，并且仅影响树的结构，而不影响所需的结果。这样的树是从场景中所有多边形的未排序列表构建的。从该多边形列表构建BSP树的递归算法是
- 从列表中选择一个多边形A。
- 在BSP树中构建一个节点N，并将A添加到该节点的多边形列表中。
- 对于列表中的每个其他多边形
- 如果该多边形完全位于包含A的平面的前面，则将该多边形移动到A前面的节点列表中。
- 如果该多边形完全位于包含A的平面的后面，则将该多边形移动到P后面的节点列表中。
- 如果该多边形与包含A的平面相交，则将其分成两个多边形，并将它们移动到分别位于P后面和前面的多边形列表中。
- 如果该多边形位于包含A的平面内，则将其添加到节点N的多边形列表中。
- 将此算法应用于位于A前面的多边形列表。
- 将此算法应用于位于A后面的多边形列表。
更新于： 2020年1月8日
1K+ 浏览量
广告