3.2 核心算法与数据结构

3.2 核心算法与数据结构

本节摘要：SOURCE 3.2：求交、布尔、约束求解、空间索引构成几何智能的数学根基。

几何算法的"底层八股"

CAD 系统的一切高级功能，最终都要落到几类基础算法上。它们像是"几何世界的底层八股"——每个 CAD 内核都必须把这几件事做到又快又稳：

布尔运算：实体建模的代数基石

布尔运算（并/交/差）的流程是：求交 → 分类 → 裁剪 → 重建拓扑。

1. 求交：找出两个实体表面的相交曲线；
2. 分类：判断每条边、每个面在对方实体内部还是外部；
3. 裁剪：去掉被裁掉的部分；
4. 重建拓扑：缝合新边界，生成合法实体。

其中求交是最难的一步：两个曲面可能相切（交线退化）、可能重合（无数交线）、可能仅在一个点接触。稳定的内核必须处理这些退化情况，否则布尔运算会出现"差集后留下碎面"或"布尔失败"。

约束求解：草图与参数的"裁判"

约束求解器维护草图自由度：DOF = 方程数 - 未知数；欠约束时模型漂移，过约束则求解失败。草图上的每个约束都是一个方程：

• 水平约束：两点 y 坐标相等；
• 尺寸约束：两点距离 = 给定值；
• 相切约束：两曲线切线平行。

求解器把约束方程组联立求解，确定各几何实体的位置。

# 用伪代码感受"自由度"的判定
class SketchSolver:
    def solve(self, entities, constraints):
        n_unknowns = sum(e.free_dof() for e in entities)   # 未知数
        n_equations = len(constraints)                      # 方程数
        dof = n_unknowns - n_equations
        if dof > 0:
            return ("欠约束", dof)   # 模型会漂移，需补约束
        if dof < 0:
            return ("过约束", -dof)  # 矛盾方程，求解失败
        return ("完全定义", 0)       # 理想状态：唯一解
​

这就是为什么 CAD 在草图底部显示"完全定义"字样——它告诉你约束方程数与未知数恰好相等。欠约束与过约束都会让设计变得不可控。

空间索引：大装配的加速器

大装配（10⁵+ 零件）依赖轻量化 LOD 与引用实例化，避免内存爆炸。而"拾取零件""干涉检查""碰撞检测"这类高频操作，不能对每个零件做全量遍历，必须用空间索引：

• R-tree：把几何对象按包围盒组织成树，查询时剪枝——只深入可能相交的分支；
• Octree：把空间八等分递归细分，常用于网格与点云场景。

class RTree:
    def query(self, box):
        # 从根节点开始，只深入与查询框相交的子节点
        return [obj for node in self.walk(box) for obj in node.overlap(box)]

    def walk(self, box):
        stack = [self.root]
        while stack:
            node = stack.pop()
            if not node.mbr.intersects(box):
                continue                # 剪枝：不相交就不深入
            if node.is_leaf:
                yield node
            else:
                stack.extend(node.children)
​

索引的意义在于把"每帧遍历百万对象"降为"每帧访问几十个节点"。没有它，大装配的旋转、拾取会卡到无法使用。

网格化：精确几何与显示/仿真的桥

B-rep/NURBS 精确但计算贵，网格化把它们离散为三角面片供渲染与 FEM 使用。关键质量指标：

自适应的原则：曲率大、特征小的地方加密，平坦区域稀疏——这样用最少三角形达到指定弦偏差。

数值容差：一切稳健性的来源

几何计算使用浮点数，两个"数学上相等"的点在计算机里可能相差 1e-9。因此所有内核都定义容差（Tolerance）：距离小于容差的点视为重合、相切度小于某角的视为相切。

• 容差太小 → 本应重合的点被当成分离，布尔/求交失败；
• 容差太大 → 本应分开的面被焊在一起，生成坏几何。

曲面求交：退化情况专项

曲面-曲面求交是 CAD 内核对稳健性要求最高的一环，因为它要处理大量退化情况：

以"圆柱面与平面"为例：两者相交通常得到椭圆或圆，但若圆柱与平面相切，交线退化为一条直线；若平面穿过圆柱轴线，交线是两个半圆。内核必须对每一种情况都给出确定结果，否则布尔运算会在"半途"失败。

# 求交的退化判定伪代码
def intersect_surfaces(s1, s2, tol):
    if surfaces_coplanar(s1, s2):
        return INTERSECTION_IS_REGION   # 局部重合，返回公共区域
    if tangency_detected(s1, s2, tol):
        return INTERSECTION_IS_POINT    # 相切，退化交点
    return compute_intersection_curve(s1, s2)  # 正常求交
​

网格化中的自适应细分

网格化的核心矛盾是"精度 vs 数量"。自适应细分策略按曲率决定密度：

• 曲率大处（圆角、棱线附近）加密三角形；
• 平坦处（大平面）用大三角形。

给定弦偏差容差后，自适应算法用"细分—检测—再细分"的循环逼近目标。实践上，一个弦偏差 0.01mm 的汽车外板网格，面片数可能是粗网格的几十倍——所以 CAD 都提供"质量档位"（草稿/标准/精细），供不同阶段选用。

大装配性能：三层优化组合

大装配（10⁵+ 零件）依赖轻量化 LOD 与引用实例化，避免内存爆炸。工业实践把优化分成三层：

视锥裁剪是基础中的基础：只渲染摄像机视锥内的零件，其余直接跳过。包围盒测试让"拾取零件"从"遍历所有面"降为"检测几十个盒子"——先把零件的大包围盒排序，命中后再精确求交。

空间索引：R-tree 的工程细节

空间索引支撑大装配拾取。R-tree 的工程实现有两条关键原则：

1. 最小包围矩形（MBR）：每个树节点保存其所有子对象的包围盒，查询时若 MBR 与查询框不相交则整体剪枝；
2. 节点容量：每个节点通常容纳 4-8 个子项，容量太小则树过高、遍历慢，太大则剪枝不彻底。

插入时，R-tree 按"MBR 扩张最小"的原则选择分支；必要时分裂节点保持平衡。对静态装配体还可以预构建一次索引，后续查询全部走索引——这是 CAD 在旋转视图时"从卡顿到流畅"的分水岭。

⚠️ 常见坑：忽略数值容差导致「理论上相交却求交失败」。

💡 关键直觉：CAD 性能 = 数据结构 + 容差策略。

一节小结

• 布尔与求交是内核核心
• 约束求解连接草图与参数
• 空间索引支撑大装配交互
• 网格化要在精度与数量间权衡
• 容差是稳健性的分水岭