BSP树与网格布尔操作

这篇文章的主题是介绍 BSP 树合并的意义。 它没有描述实体的网格表示和 BSP 树表示之间的转换，如果你想使用 BSP 树进行网格布尔运算，则必须执行此转换 – 你必须将网格转换为 BSP 树表示 ，进行树合并，然后转换回网格。

许多文本以不太精确的方式介绍 BSP 树。 直观上，这些解释是有道理的，但你可能不清楚是否想说服自己这些细节是可行且合理的。 我将尝试为 BSP 树提供更严格的基础，这有望证明我们将要做的许多后续操作（例如合并）的合理性。 为了简单起见，以下所有概念都将在二维平面 中讨论。

1、BSP 树作为实体对象的描述

在本节中，我将尝试描述 BSP 树如何对应于空间中的区域。

首先，让我们从用线分隔平面或在更高维度中用超平面分隔平面的想法开始。 假设我们有线 A1...An – 每条线对应一个法向量  ni 和一个值 vi，使得 Ai = {x:ni·x=vi}，其中 · 表示标准点积。 我们将对应于 Ai 的正半平面表示为  Ai+ = {x:ni·x>vi}。 对于 Ai- 也是如此。

现在可以合理地将这些线对平面的所有“分离”描述为：

即这些线的分隔只是各个半平面的交点。 这里有 2^n 个组合对应于这种类型的某些集合，但请注意，所有不同的组合都是成对不相交的。

举个例子 - 对于 n=3 和直线 A_1、 A_2 和 A_3 ，很明显：

其中一些集合也可能是空的。 我们也可以说通过使用 n 各 布尔值数组将平面分割成各种子集。 换句话说，我们可以定义从  n 个布尔值数组到这些子集的映射，例如：

因此每个集合对应于布尔数组中的某个元素。

描述这些集合的另一种方法是使用树结构。 这类似于如何使用二元决策树来描述一组二元选择。 每个节点对应一条线 Ai，左边的子节点对应的是与 Ai- 相交。 但请注意，我们确实必须选择一些顺序。 作为树描述的示例，我们假设只有一条直线 A1 ， 那么描述平面分离的更组合方式将是 {(0),(1)}，而树描述将是根节点 A 和 两个未命名叶节点 – 左叶节点对应 到 Ai-。 这可能有点令人困惑——这样一棵树的叶子实际上与节点的类型不同。 如果有帮助，你可以使用不同的颜色或其他东西来命名叶节点。

假设我们想要描述由如上所述的各种交点 ：

换句话说，其中一些交点的并集。 描述某些此类子集 M 的一种方法是简单地为每个子集分配值 0 或 1，其中 1 对应于包含在 M 中的交集，而 0 对应于 到 M^c 中的交集（ M 的补集）。

例如，用 fM 表示赋值，等式 fM(0,0,1) = 1 意味着包含在 M 中的：

同样，我们可以通过为之前描述的树的某些叶子分配值（同样是 0 或 1）来描述这些包含。 关键是我们可以组合地或使用树来描述 M。 请注意，由于半平面的某些交点是空的，因此我们为它们分配什么值并不重要。 这意味着某些不同的分配 f,h实际上可以对应于相同的子集 M。 从现在开始，我们将这样的树称为 BSP 树，其叶节点中包含值。

2、BSP树的合并

我们现在可以通过二叉树  TM 来描述平面分离的各种子集，其中叶节点对应于我们的集合 M 内部或外部的半平面的相应交集。

现在，如果我们想要描述发生的情况，例如，如果我们想要将我们的集合 M 与其他集合 N 相交，而该集合也由其他由分隔平面的其他线组成的树来描述，该怎么办？

从代数上来说：

其中 Si是半平面的单元/交点，使得它们的叶节点在我们的树 TM中具有值 1。 所以：

现在很容易检查，如果我们只考虑将  TN 的每个叶节点替换为 TM 的值 1，并将 TN 的每个叶节点替换为值 0 的树具有相同节点 结构为 TM，但所有叶子都是 0，我们将有一棵对应于集合 N 和几何M的交集 的树。

这就是合并 bsp 树的全部内容。 我们只需将新树添加到原始树的每片叶子上。 我们必须考虑我们正在执行的操作（如上面的示例中的交集，我们本质上忽略了原始树中值为 0 的叶子），但所有操作的本质始终相同 - 你只需添加新树 根据操作，在每片叶子上进行一些轻微的修改。

这最终会起作用，因为生成的树叶实际上只对应于交集：

其中 Bm 是分隔与树 M 相对应的平面的线。 使用分布性的 ：

我们看到合并结果中所有值为 1 的叶子的并集确实对应 到 M（ TM 中所有值为 1 的叶子的并集）和 N（ TN 中值为 {1} 的所有叶子的并集）的交集。

到目前为止，我们所处理的只是一个完美平衡的二叉树——在每个级别中，恰好有 2^i 个节点（或最终级别中的叶子）。 然而，请注意，如果一个节点的两个子节点都是具有相同值的叶子，我们可以做一个非常自然的减少——在某种意义上，我们可以删除叶子，然后简单地写下值而不是节点。 此外，如果叶子对应于空集，我们可以将分配/值更改为我们喜欢的任何内容。 这意味着如果其中一个叶子对应于一个空集，我们总是可以将该叶子的父节点减少到与另一个叶子中相同的值。 这些减少对于计算效率显然很重要。

我将留给读者检查以简化形式处理两棵树然后合并它们，与首先以非简化形式合并它们然后再简化它们。

3、简化过程的优化

上面的文本试图解释 BSP 树合并的完整基础知识。 它还说明了减少是一个合理的概念。 然而，让你正在使用或即将渲染的树采用简化形式显然是有用且更高效的，否则 BSP 树将具有指数级数量的节点。 但如何做到这一点呢？

如何将树转换为简化形式？ 或者，如果以简化形式合并两棵树，如何有效地将合并结果保持为简化形式？ 让我们来讨论一下合并案例。

首先，在合并期间跳过将树插入到所有叶子中（当你进行交集时，将新树插入到值为 0 的叶子中是没有意义的，因为它会减少到 0 - 这只是 为了清楚起见，在上一节中完成了）。

其次，当你将新树放入旧树或减少时，希望以某种方式确定所在的节点是否对应于空节点（如果是，可以减少到父节点）。 类似地，如果你只是减少一棵树，你只需要弄清楚你所在的节点是否对应于空集。 不知何故，找出一组节点/叶子是否为空是你真正可以做的减少操作。

换句话说，减少树的一种方法是从根开始，递归地沿着树向下走，跟踪所在节点的区域有多大，如果该区域为空则停止。

那么你到底是如何做到这一点的呢？ 嗯，有很多方法。 Bruce Naylor 关于 BSP 树合并的原始论文使用了相对复杂的递归树分区排序方法。 对于那些难以理解它并且感兴趣的人 - 本质上，如果你有一棵以某条直线 A 开头的树，并且想将其按 H 分割（即创建一棵以 H 开头的新树 并且有 A 作为左子树和右子树），首先要弄清楚 H 如何分割 A 的左子树和右子树，因此你实际上创建了两棵树，其根为 H，子树为 A 的孩子。 一旦完成，你就构建了最终的树——你稍微改变了树的顺序。 我怀疑这个解释会有多大帮助，所以不要过多地试图理解这一点。

找到空区域的另一种方法是简单地将其视为线性编程问题 - 遍历树，并迭代检查所在的节点/叶子是否对应于空集。 M. Lysenko 发表了一篇论文，在这个方向上使用了 Seidel 算法（一种增量检查通过半平面添加交集是否会导致空集的算法），结果似乎不错。 我已经想到了一些其他可能的方法来解决这个问题，我可能会在稍后的另一篇文章中分享一些对此的想法。 Seidel 的算法 {O(n)} 运行时间界限基于预期值，我没有尝试检查方差是什么，所以我不确定它在游戏之类的东西中是否不会出现问题，在游戏中你不这样做 不希望 fps 下降。 但话又说回来，如果花费的时间太长，你可以通过将计算分散到几个帧来保证安全。

最后，可以通过迭代剪切正在使用的网格来检查所在的节点是否为空。 由于在将 BSP 树转换回网格/边界表示之前你可能对合并大量 BSP 树不感兴趣（因为可能需要能够访问每次合并的结果网格），因此不妨开始 使用一些网格（例如对应于整个平面的大立方体），并在沿着树遍历时迭代地剪辑它，每个节点在内存中保存生成的网格。 由于无论如何在渲染网格之前你都需要迭代地裁剪网格，因此不妨使用此信息来检查所在的节点/叶子是否对应于空白空间。 在这里，你要做的就是检查所在的节点/叶子的网格在你的空间中是否没有体积（即在 3D 中，它是一个平面，或者它只是没有顶点等）。 这是我在我的小型 openGL BSP-tree CSG 项目中实现的，它似乎工作得很好。

4、其他优化及问题

关于 BSP 树合并还有各种其他问题以及可以改进的地方。 这篇文章也不适用于子超平面，就像几乎所有其他 BSP 树文本一样。 在我看来，在这篇文章（BSP 树合并）的上下文中，它们似乎没有必要，但它们是一个对于涉及 BSP 树的各种问题可能有效的概念。 它们看起来大多像形式主义/符号之类的东西——这篇文章中的简化概念在某种意义上消除了对它们的需要。

使用 BSP 树时还存在许多其他重要问题 - 对于某些事情，尝试找到一个平衡良好的 BSP 树可能是值得的。 我们使用的线分割平面的顺序很重要，并且简化的树可能或多或少是平衡的，所以这是你可能需要考虑的事情。 然后就是从网格到 BSP 树的转换的整个问题。 有多种方法可以以或多或少有效/漂亮的方式做到这一点，并且可能有很多关于此类主题的论文。 尽管如此，这篇文章的重点只是简单介绍 BSP 树、它们的意义以及它们如何用于网格上的布尔运算。 我希望这篇文章对这方面的人有用。

原文链接：BSP trees for mesh boolean operations

BimAnt翻译整理，转载请标明出处