代替引言

我仍在构建Unity中的过程几何学的节点图：我最近完成了循环和连接性，很多东西已经工作了。布尔运算是下一个目标：并集、交集、差集、将两个网格表面边界的体积上的集合运算。所有我最近做的东西中，这是最困难的。

几年前，我在以前的工作中需要简单的布尔运算。我当时还不完全理解它们有多难，所以我开始使用一种天真实现。这个项目已经发布很久了，但它留下了一个未完成的感觉：我知道我做错了。

我在大学学习了13年前，计算几何学只浅尝辄止地教导了我——我必须自己填补的知识空白。所以我回到它：我武装自己30年的论文，依赖于Claude Opus来帮助我处理难题（它比我更好地解释了它们，比许多论文的作者更好），并坐下来写布尔运算。接下来是它们的结果：它们为什么通常会破裂，以及如何防止它们。

基于浮点数的布尔实现会在输入配置的退化情况下破裂：两个表面在同一平面上，一个操作数的边缘在另一个操作数的表面上，共享的顶点或边缘。这些在建模中是最常见的配置，破裂的特征是：开放的缝隙、翻转的片段、额外或缺失的表面、无限循环以跟踪轮廓。

核心的需求是通过构建实现的鲁棒性：组合结果在退化输入配置下是正确的。遗憾的是，我没有发明任何新东西，所以接下来是简短的——破裂机制和解决它们的解决方案，我从各种来源中提取的（来源在结尾）。

三种类型的破裂

每种破裂都可以归结为三种类型，每种类型都有自己的解决方案。

断言错误。内核反复计算具有以下形式的有符号数量的值：“哪边的平面上的一个点？”在零附近，浮点运算返回错误的符号，从而导致矛盾的拓扑。这是破裂的最常见来源，是完全可消除的：精确断言始终返回正确的符号。

构造漂移。两个表面的交点的坐标是近似计算的，同一个点从A面的一侧和B面的一侧计算出来，位于两个不同的位置，从而导致缝隙的破裂和在后续的焊接中错误的顶点合并。通过计算每个交点一次并将其存储为共享的对象，使两侧都引用它，破裂被消除了。

分类错误。传统上，一个片段是否属于第二个操作数的内部是通过决定它是否与该操作数的边缘或顶点相交来决定的。通过一个边缘或顶点的射线会返回错误的交叉数，并且在触摸表面、平行面的表面和开放的网格上，这种情况经常发生。通过将交叉数替换为环数来消除这种破裂。

天真的实现往往会降低精度 epsilon，仅仅将破裂从一个输入配置转移到另一个输入配置，并消除任何类型的破裂。因此，分解为两个保证：拓扑的鲁棒性（组合结果在退化的配置下是正确的：平行性、共享的边缘、精确的触摸、自相交、洞）和输出浮点坐标的几何精确度——第二种是较弱的，并且在单独的部分中讨论。通过将输入推入“通用位置”以回避退化性，我拒绝了这种方法：它改变了输入本身，行为非确定性，失败地在触摸和平行配置上，这在CSG建模中是大多数情况。

内核内部

上述三种类型的破裂也确定了解决方案的计划：每种破裂都有自己的机制，我将它们逐一讨论。但是，让我们先看看内核实际上如何处理两个网格。

要将两个相交的立方体合并，内核会找到曲线，表面在这些曲线上相交，找到这些曲线上的边缘，切割两个操作数的面，创建每个操作数的面碎片。然后，对于每个碎片，决定它是否位于另一个固体内或外部。并集保留了两个操作数的外部碎片，并沿着交点曲线将它们连接起来——缝隙。整个管道是一系列阶段：精确断言、标准交点表、面碎片排列、碎片分类、提取、缝隙连接。断言和插入交点到面是从Cherchi等人（2022年，MIT许可下的公开参考实现）[1]中提取的；分类器我替换了——更多信息在第三个机制中。

管道中的每个几何决策都是断言：一个有符号问题的形式“这个点位于哪一侧的平面？”或“这些段是否相交？”，回答为正、负或零。它正是当零时，浮点会返回错误的符号，而所有三种类型的破裂都从这些错误中生长。现在是三个机制的顺序。

第一个破裂，断言错误，是通过Shewchuk的精确断言（orient2d / orient3d，公共领域）[3]关闭的：管道中的每个断言都是正确的。它们在两次迭代中计算。快速过滤器将断言作为普通的浮点数，同时估计结果是否太接近零，无法信任；如果太接近零，精确路径就会激活——在扩展中进行算术，一个数字被存储为多个浮点数的总和，这样每个运算的舍入误差就被保留在较低阶项中。我的输入是float32，因此结果很少会接近零，几乎所有的东西都可以通过快速过滤器解决；精确路径在扩展中使用的只是偶尔。

内核是用Burst编写的——Unity的编译器，它将C#的一个子集转换为原生代码：原生集合，热路径上的管理分配。浮点模式保持严格，而不是Fast。Fast允许代数重排和融合指令（FMA——在一步中执行乘法和加法，仅一次舍入而不是两次）；Shewchuk的扩展依赖于与之相反的内容——它们捕获每个运算的舍入误差到单独的尾部浮点中；这只会持续到每个乘法和加法都被舍入并且按顺序进行。FMA和重排会破坏捕获：尾部不再精确，到界限时断言的符号可能会错误。所以，Fast是关闭的。

第二种破裂，构造漂移，是通过隐式点（Attene）[4]关闭的。一个交点没有坐标，保持符号——“面T和段S的交点”；断言关于它会通过相同的过滤器。没有坐标意味着没有构造漂移：第二种破裂类型是通过构造消除的。

第三种破裂，分类错误，是通过将环数代替交叉数来关闭的。要告诉一个碎片是否位于第二个操作数的内部，简单的方法是从点射出一个射线，计算它与表面的交叉数：奇数表示内部，偶数表示外部。通过一个边缘或顶点的射线会被错误计算，触摸和平行面的表面上这种情况会不断发生。环数问同样的问题，强壮地：它测量表面如何围绕点旋转——对于一个封闭的体，这是一个整数，1表示内部，0表示外部，表面通过射线的面不会引入任何不确定性。环数形式主义是从Zhou等人（2016年）[2]中提取的：它覆盖了自相交和开口输入，一个二进制内部/外部位从射线无法处理的。

内核决定从操作数本身中选择哪种变体——它是否具有平衡的导向的标准边缘，彼此平衡（一个条件比正式封闭更广泛）。如果它们平衡，操作数是封闭的，还是开放但沿其缝隙连接的：环数字段是整数，值是通过一个单独的精确射线获取的，正确即使在自相交的情况下，成员资格是非零规则（w != 0）。如果没有平衡，操作数确实是开放的；那么，泛化环数（GWN）[5]适用——表面在点处所包围的体积的分数——与严格阈值w > 0.5一起（“点被封闭的多了”）。这将开放的脏网格（自相交、非多面体）从输入错误转变为普通支持的输入。

属性：源头和物质化

布尔运算会产生点，它们在输入A或输入B中没有——所有缝隙点在交点处。它们没有地方从哪里获取UV、法线或颜色。鲁棒的实现通常会在三角形汤中工作，仅仅保留位置，并将这个问题置之不理：属性要么丢失，要么在单独的阶段中缝合——通过最接近的源顶点查找。然而，我需要属性与几何学一起旅行，并缝隙点获得其自身的诚实。这些结构已经在引擎中了。

机制被称为源头（我称之为如此）。每个输出点和每个顶点都携带一个短的“我来自哪里”的列表——源元素和权重的对。一个顶点被复制为是——一个权重为1的条目。一个点在切割边缘上产生——两个条目：边缘的端点与切割参数的权重。一个源三角形内的交点——三个条目：三角形的顶点与巴里森权重（u、v、w）。权重在所有阶段都合成：如果三角形的顶点本身是混合的，列表会进一步增加，直到源输入顶点。

物质化重新播放这些列表，仅仅知道它们实际上所持有的通道。所有浮点类似物——UV、法线、切线、颜色——是通过权重的线性混合；离散数据（一个整数ID和类似之）取主导源；群成员资格是所有贡献者之间的AND。通道没有硬编码到内核中：添加一个新属性，它会在其自身上乘以物质化——没有任何编辑。

单独的点和顶点域映射到缝隙的结构。一个缝隙点是共享的位置，但它的收敛的顶点属于片段A和B，并且保留了它们自己的列表：A面的UV保留在A面的顶点上，B面的UV保留在B面的顶点上，没有在缝隙上进行平均。一个“顶点只有”表示法将需要在缝隙上强制水密性——通过复制位置并在距离焊接中；这里缝隙是通过构造关闭的，两个侧引用一个点的那一刻。每个操作数是单独分解的，碎片是物质化的，然后缝隙点的两侧是通过标准点表连接的——通过精确的索引匹配，而不是通过容差。

将输出“钉”到浮点

一个界限并没有在一般情况下解决，而不是我。管道内部的所有内容都是精确计算的，但输出需要一个普通的Unity网格——位置在float3中。因此，在最后一步，精确点必须被舍入到浮点，舍入可能会带回精确算术所救的麻烦。通过在最后一位上推动一个点，它可能会再次将两个面推入触摸或交叉（一个微小的交点），或将一个三角形扁平化到一个细长的斜面——退化地薄，接近零的面积。一个将浮点坐标在3D中舍入的算法，并且同时保证终止并且结果清洁（称为3D“钉”舍入）尚未被证明。CGAL（2025年）[6]的实践配方是：循环：舍入、查找剩余的自相交、在那些地方局部重新解决排列、重复。

我的路径更短。一次舍入，循环检查——一个精确的自相交检测器，但仅限于缝隙面，即布尔运算本身产生的新面；这是正好是在哪里问题可能会出现，而其余的网格舍入从未触及。剩余的任何东西我都会将细长的斜面收缩到小于浮点分辨率。最后，一个狭窄的案例集仍然存在：一个缝隙点在舍入后恰好落在邻近多边形的边界线上，偏差小于或等于一个ULP（ULP是两个相邻可代表的浮点之间的距离，即在该坐标尺度上精度限制）。这样的残余对我不会掩盖，也不会转换为异常——它们会公开进入统计中。对于布尔运算在曲面几何学上，非零的残余是正常的；一个硬零只有在坐标在浮点中完全可表示时才会期望（二进制的形式k/2^n）。

管道是实现的，选择了将其覆盖的测试——所有阶段：精确断言、标准交点表、面排列、碎片分类、提取、缝隙连接。平行对、共享的边缘和顶点、精确的触摸和开放的网格管道处理在主路径上；自相交通过同样的机制。

自相交

自相交的操作数是质量要求的一部分：管道必须接受脏输入。因此，分类会寻找不仅是A和B之间的接触，还有A与自身的接触：相邻的边缘对会被跳过，触摸在共享的顶点上会被抑制，在一个干净的网格中不会出现接触。同样的机制上面同样的操作——解释一个网格的自相交。

机械上，它是相同的管道。只在输入A中寻找接触，而操作数B是虚拟的：一个零三角形集和一个空快照。整个管道（排列、碎片分类、提取）仍然以正常的方式运行，只有B阶段在循环边界处都会折叠；一个空B带有环数0，联合断言简化为“A内部”。有两个模式：Resolve会规范自相交的体（自相交：保留边界，体从内部到外部切换时；平行的折叠通过符号入口取消）。Imprint会保留整个表面，只会在自相交缝隙上切割面。开放的输入在Resolve模式下会通过不受影响——没有什么需要解释。

在图中，这是两个节点。Detect Self Intersections会将几何学传递给它，放置自相交的多边形到一个组中（selfIntersections默认），并在一个单独的Count端口输出它们的数量。Resolve Self Intersections有一个模式（Resolve / Imprint），碎片连接，缝隙组名。对管道的成本是四个故意的无动作编辑和一个新文件：二进制管道的字节保持不变，测试集将作为保证来防止回归。未覆盖的案例是被称为的真实案例：平行的自相交（平行的面，相交的边缘，相交的顶点）Resolve不会处理。

这个操作本身是副产品。自相交必须被解决，以保证布尔运算的质量；而由于A被检查自相交的方式与B被检查自相交的方式相同，Detect和Resolve节点几乎是免费的——一个很好的，实用的奖励。

来源

  1. Cherchi, Pellacini, Attene, Livesu。Interactive and Robust Mesh Booleans。SIGGRAPH Asia 2022。https://arxiv.org/abs/2205.14151——MIT许可下的参考实现：https://github.com/gcherchi/InteractiveAndRobustMeshBooleans
  2. Zhou, Grinspun, Zorin, Jacobson。Mesh Arrangements for Solid Geometry。SIGGRAPH 2016。https://www.cs.columbia.edu/cg/mesh-arrangements/
  3. Shewchuk。适应精度浮点运算和快速鲁棒判据的计算几何学。1997年，公共领域。https://www.cs.cmu.edu/~quake/robust.html
  4. Attene。间接判据的几何构造。计算机辅助设计，2020年。https://arxiv.org/abs/2105.09772
  5. Jacobson, Kavan, Sorkine-Hornung。使用泛化环数的鲁棒内部-外部分段。SIGGRAPH 2013。https://igl.ethz.ch/projects/winding-number/
  6. Loriot, Valque (CGAL / GeometryFactory)。修复三角形汤中的自相交。2025年。https://www.cgal.org/2025/06/13/autorefine-and-snap/