Binary Space Partitions
Binary Space Partitions
复制标题
二进制空间分区
DOI：
10.1007/978-1-4939-2864-4_511
复制
发表时间：
2016
期刊：
影响因子：
--
通讯作者：
Csaba D. Tóth
中科院分区：
文献类型：
--
作者：
A. Dumitrescu;Csaba D. Tóth
二进制空间划分（简称BSP）是一种通过超平面以递归方式将环境空间R细分为开凸集（称为单元）的方案。一个单元的每一步细分都会产生两个单元，在两个单元中，该过程可以独立于其他单元继续进行，直到满足停止条件。二叉递归树，也称为bsp树，传统上被用作计算机图形学中高效渲染多面体场景的数据结构。bsp树的每个节点v，除了叶子，对应一个cell Cv R和一个分区超平面Hv。根r的单元格是Cr D r，节点v的两个子节点对应于Cv \H v和Cv \HC v，其中Hv和HC v表示以Hv为界的开放半空间。参见图1。对于R中n个成对不相交（通常是多面体）对象的二进制空间划分是一个BSP，其中空间递归划分直到每个单元最多与一个对象相交。当bsp树作为数据结构使用时，每个叶子v存储在单元Cv中剪切的最多一个对象的片段，每个内部节点v存储位于Cv \Hv中的任何低维对象的片段。一组对象的BSP有两个感兴趣的参数：相应BSP树的大小和高度。理想情况下，BSP划分空间，使每个对象完全位于单个单元或切割超平面中，从而产生所谓的完美BSP[4]。然而，在大多数情况下，这是不可能的，并且超平面Hv将一些输入对象划分为碎片。假设输入对象是k维的，对于某些k d， BSP通常只存储k维片段，即在内部节点的叶细胞Cv或Cv \Hv中剪切的对象部分。
The binary space partition (for short, BSP) is a scheme for subdividing the ambient space R into open convex sets (called cells) by hyperplanes in a recursive fashion. Each subdivision step for a cell results in two cells, in which the process may continue, independently of other cells, until a stopping criterion is met. The binary recursion tree, also called BSP-tree, is traditionally used as a data structure in computer graphics for efficient rendering of polyhedral scenes. Each node v of the BSP-tree, except for the leaves, corresponds to a cell Cv R and a partitioning hyperplane Hv. The cell of the root r is Cr D R , and the two children of a node v correspond to Cv \H v and Cv \HC v , where H v and HC v denote the open half-spaces bounded by Hv. Refer to Fig. 1. A binary space partition for a set of n pairwise disjoint (typically polyhedral) objects in R is a BSP where the space is recursively partitioned until each cell intersects at most one object. When the BSP-tree is used as a data structure, every leaf v stores the fragment of at most one object clipped in the cell Cv, and every interior node v stores the fragments of any lower-dimensional objects that lie in Cv \Hv. A BSP for a set of objects has two parameters of interest: the size and the height of the corresponding BSP-tree. Ideally, a BSP partitions space so that each object lies entirely in a single cell or in a cutting hyperplane, yielding a so-called perfect BSP [4]. However, in most cases this is impossible, and the hyperplanes Hv partition some of the input objects into fragments. Assuming that the input objects are k-dimensional, for some k d , the BSP typically stores only k-dimensional fragments, i.e., object parts clipped in leaf cells Cv or in Cv \Hv at interior nodes.