第03章：CSG 与 BSP 树核心原理

前两章我们已经能”用”OpenCSG.NET 了。本章暂时离开 API，深入理解它背后的两大基石——CSG（构造实体几何） 的表示方法，以及BSP 树（二叉空间分割树） 如何实现布尔运算。理解原理不是为了炫技，而是为了让你在遇到”孔挖不干净”“面片穿插”“结果为空”等问题时，能从根本上判断原因。本章不要求你记住代码细节，重点是建立心智模型。

3.1 实体是如何被表示的：边界表示（B-rep）

OpenCSG.NET 用边界表示法（Boundary Representation，B-rep） 描述一个实体：一个实体 Solid 就是一组多边形 Polygon 的集合，这些多边形首尾相接、围成一个封闭的、有内外之分的表面。

Solid  =  { Polygon, Polygon, Polygon, ... }
Polygon = 有序顶点列表 + 所在平面 + 共享属性
Vertex  = 空间位置(Vector3D) + 纹理坐标(Vector2D)

几个关键约定，贯穿整个库：

• 多边形必须是凸的：每个 Polygon 都被假定为平面凸多边形。非凸或带洞的形状必须先拆分成多个凸多边形。
• 法线朝外：多边形顶点按逆时针（从外部看） 排列，由此计算出的平面法线指向实体外部。法线的朝向定义了”哪一侧是实体内部”。这是布尔运算能区分内外的根本依据。
• 表面必须封闭且流形：一个合法实体的表面应当是”水密”的——没有裸露的边、没有自相交。布尔运算的输入若不满足这一点，结果可能不可预测。

理解 B-rep 的意义在于：OpenCSG.NET 从不存储”体积”或”内部填充”，它只存储表面。所谓”这个点在实体内部还是外部”，是通过”它在各个边界多边形的哪一侧”推断出来的。这正是 BSP 树要解决的问题。

3.2 布尔运算的集合语义

CSG 的三种布尔运算，本质是三维点集的集合运算。设实体 A、B 分别代表它们所占据的空间点集：

一个重要推论：差集与交集可以用并集和取反表达。事实上 csg.js 系的实现正是基于这个思想——只要能做”用 B 的表面裁剪 A 的多边形”和”翻转实体内外”，三种运算就都能搭出来。下面就来看这两个原子操作。

3.3 BSP 树：把空间一分为二

3.3.1 什么是 BSP 树

BSP 树是一种递归地用平面把空间切开的数据结构。在 CSG 里，我们用实体 B 的每个多边形所在的平面，来构建一棵 BSP 树。树的每个节点持有：

• 一个分割平面（取自某个多边形）；
• 落在该平面上的共面多边形列表；
• front（前方，法线正侧） 子树；
• back（后方，法线负侧） 子树。

构建时，我们拿一堆多边形，选第一个的平面作分割面，然后把其余每个多边形按它相对分割面的位置分类：

• 完全在前方 → 丢进 front 子树；
• 完全在后方 → 丢进 back 子树；
• 恰好共面 → 留在当前节点；
• 横跨平面（spanning） → 沿平面切成两半，一半归 front，一半归 back。

递归地对 front、back 子树重复，直到没有多边形可分。最终，这棵树把整个空间划分成了许多凸区域，而且——关键点——树”知道”任意一片多边形是在实体 B 的内部还是外部。

3.3.2 平面对多边形的分割：五种关系

一切的核心，是”一个平面与一个多边形的位置关系”判断。OpenCSG.NET 在 Plane.SplitPolygon 里用一个容差 EPSILON = 1e-5 把每个顶点分类为”前 / 后 / 共面”，再综合出多边形的整体类型：

“横跨”是最精妙的一步：算法会计算多边形每条边与分割面的交点，在交点处插入新顶点，把一个多边形切成”前半”和”后半”两个新多边形。正因为有这一步，布尔运算的结果才能在两个形体的交界处产生精确的新边界，而不是简单地丢弃或保留整片多边形。

精度约定：整个库的几何比较都以 Plane.EPSILON = 1e-5 为容差。凡是”是否共面”“是否重合”的判断都在这个尺度上进行。这意味着你的模型尺寸不宜过小（例如所有坐标都在 1e-4 量级），否则容差会吃掉真实差异；也不宜配合极大坐标做布尔（见 3.5 的原点居中修复）。

3.4 三种布尔运算的算法流程

有了 BSP 树，我们就能定义两个原子操作：

• ClipTo(other)——用另一棵树 other 代表的实体，裁掉当前树中”落在 other 内部”的多边形部分。
• Invert()——翻转实体的内外：所有多边形法线反向，front/back 子树互换。翻转后，”内部”变”外部”，于是”裁掉内部”就变成了”裁掉外部”。

OpenCSG.NET 的 Solid 把它们组合成三种运算（以下为源码 Solid.cs 中的真实序列，a、b 是分别由两个实体构建的 BSP 树）：

并集 UnionSubLocal：

a.ClipTo(b)          // 裁掉 a 落在 b 内部的部分
b.ClipTo(a)          // 裁掉 b 落在 a 内部的部分
b.Invert()           // 翻转 b
b.ClipTo(a)          // 再裁一次，去掉两者内部重合的面
b.Invert()           // 翻回来
结果 = a 的所有多边形 + b 的所有多边形

直觉：把 A、B 相互”啃掉”埋在对方内部的表面，剩下的就是并集的外壳。

差集 SubtractSub（A − B）：

a.Invert()           // 先把 A 翻里为外
a.ClipTo(b)
b.ClipTo(a, true)    // 反向裁剪（第二参数控制共面处理）
a.AddPolygons(b.AllPolygons())
a.Invert()           // 再翻回来

直觉：把 A 翻转后当作”补集”，用 B 去裁，最后再翻回来，等价于”A 减去 A∩B”。

交集 IntersectSub（A ∩ B）：

a.Invert()
b.ClipTo(a)
b.Invert()
a.ClipTo(b)
b.ClipTo(a)
a.AddPolygons(b.AllPolygons())
a.Invert()

直觉：交集 = 补(补A ∪ 补B)，通过两次翻转与互裁实现。

你不需要背诵这些序列，但记住一个事实：三种运算都建立在”构建 BSP 树 → 相互裁剪 → 翻转 → 合并多边形”这套统一机制上。这也解释了为什么 CSG 的计算量主要取决于多边形数量——形体分辨率越高（球/圆柱面数越多），布尔越慢。

3.5 两个工程级增强：原点居中与迭代式遍历

OpenCSG.NET 相比朴素的 csg.js 移植，有两处关键的工程增强，它们来自上游 Csg 与 DotNetCsg（见第 1 章血统）。理解它们能帮你避开真实项目中的两类”疑难杂症”。

3.5.1 原点居中的 Union（浮点精度修复）

浮点数在绝对值很大时精度会显著下降。如果你在坐标 (49256, 12000, 5) 附近做布尔运算，1e-5 的容差相对于 49256 已经小到几乎无意义，分割面判断会失真，导致结果出现破面或多余碎片。

OpenCSG.NET 的 Solid.Union 为此做了原点居中处理：先计算所有参与实体的合并包围盒中心，把几何整体平移到原点附近，在那里完成布尔运算，最后再平移回原来的位置。源码 Union 方法的核心就是：

center = 合并包围盒中心
result = (this 平移 -center)
for each other:
    result = result 与 (other 平移 -center) 做局部并集
result = result.Retesselated().Canonicalized()
return result 平移回 +center

这个修复由测试 LargeCoordinateUnionTest 专门守护——它用 (-49256, 12000, 5) 这类大坐标验证并集不丢面。实践建议：即便有此修复，也应尽量让模型工作在原点附近的合理数量级，把”放到最终位置”留到最后一步。

3.5.2 迭代式 BSP（避免栈溢出）

朴素 csg.js 的 BSP 构建、裁剪、遍历都是递归的。对高分辨率、多层布尔的复杂模型，递归深度可能很大，在 .NET 上会触发 StackOverflowException——而这种异常无法被 catch，会直接崩溃进程。

OpenCSG.NET 的 Tree.cs 采用了来自 DotNetCsg 的迭代式实现：用显式的栈/队列模拟递归，把树的构建与遍历改写成循环。这样无论模型多复杂，都不会因递归过深而崩溃。第 12 章会深入这部分源码（包括为 0/1/N 个子多边形做的微优化 PolygonTreeNodeList）。

3.6 规范化与共面重划分：布尔之后的收尾

布尔运算切割多边形后，会产生大量碎片、近似重合的顶点、以及本可合并的共面小多边形。为了让结果干净、可靠、可复用，Solid 在每次布尔的最后一步会调用两个收尾流程（源码里的 Retesselated() 与 Canonicalized()）：

• Canonicalize（规范化）：用容差 1e-5 把近似重合的顶点、近似相同的平面吸附到同一个共享实例上。这样后续判断”两个多边形是否共面”就能用引用相等快速完成，也消除了浮点抖动。
• Retesselate（共面重划分）：把切割后共面且相邻的碎多边形，用扫描线算法重新合并成更少、更规整的多边形，减少面数、改善网格质量。

Solid 上用两个布尔标志 IsCanonicalized / IsRetesselated 记录当前状态，避免重复计算——如果一个实体已经规范化过，再次调用会直接跳过。这是一种惰性缓存优化。

3.7 把原理对应回你的代码

理解了原理，回头看第 2 章那个法兰盘程序，很多”经验法则”就有了解释：

• 为什么挖孔圆柱要比盘体高一点？——如果孔的顶面与盘体顶面精确共面，SplitPolygon 会把它们判为”COPLANAR”，共面处理比横跨复杂，容易残留薄面或产生歧义。让孔略微超出，就把”共面”变成了干净的”横跨”，结果更稳。
• 为什么复用同一个孔模板没问题？——所有返回 Solid 的方法都产生新对象（B-rep 是不可变的），原模板不受影响。
• 为什么高分辨率球做布尔明显变慢？——布尔计算量随多边形数量增长，分辨率翻倍，面数和裁剪工作量都会大幅上升。
• 为什么坐标别太大？——大坐标会削弱 1e-5 容差的有效性；虽然 Union 有原点居中修复，但把模型放在原点附近始终是最稳妥的。

3.8 本章小结

• OpenCSG.NET 用边界表示（B-rep） 描述实体：实体 = 一组凸、法线朝外、封闭的多边形。
• 三种布尔运算对应点集的并、差、交；差集与交集可由并集与取反推导。
• BSP 树用多边形所在平面递归分割空间，核心是 Plane.SplitPolygon 的五类关系判断（共面前/共面后/前/后/横跨），容差为 EPSILON = 1e-5。
• 三种运算统一建立在 ClipTo（互裁）+ Invert（翻转内外）+ 合并多边形之上。
• 两个工程增强至关重要：原点居中 Union（大坐标精度修复，LargeCoordinateUnionTest 守护）与迭代式 BSP（避免栈溢出）。
• 每次布尔以 Canonicalize（顶点/平面吸附） 与 Retesselate（共面合并） 收尾，并用标志位做惰性缓存。

下一章我们回到具体代码，逐一拆解构成这一切的数学与几何基础类型：Vector3D、Matrix4x4、Plane、Polygon、Vertex。