第6章：切片算法与路径规划

切片软件是3D打印工作流程的核心，它将三维模型转换为打印机可执行的层级路径指令。本章深入探讨切片算法的数学原理，从STL网格处理到复杂的非平面切片，构建对路径规划的系统性理解。我们将学习如何优化打印路径以平衡速度、质量和材料用量，并掌握支撑生成、自适应层高等高级技术。

6.1 STL网格处理与修复

6.1.1 STL文件格式与数据结构

STL (Standard Tessellation Language) 是3D打印最广泛使用的文件格式，通过三角面片逼近三维曲面。每个三角形由法向量和三个顶点定义：

$$\mathbf{T} = \{\mathbf{n}, \mathbf{v}_1, \mathbf{v}_2, \mathbf{v}_3\}$$ 其中法向量应满足右手定则： $$\mathbf{n} = \frac{(\mathbf{v}_2 - \mathbf{v}_1) \times (\mathbf{v}_3 - \mathbf{v}_1)}{|(\mathbf{v}_2 - \mathbf{v}_1) \times (\mathbf{v}_3 - \mathbf{v}_1)|}$$ STL文件有两种格式：

• ASCII格式：人类可读，体积大
• 二进制格式：紧凑存储，包含80字节文件头 + 4字节面片数 + 50字节×面片数

二进制STL结构：
┌─────────────────┐
│  80字节文件头    │
├─────────────────┤
│  4字节面片数(N)  │
├─────────────────┤
│  面片1 (50字节)  │
│  - 法向量(12B)   │
│  - 顶点1(12B)    │
│  - 顶点2(12B)    │
│  - 顶点3(12B)    │
│  - 属性(2B)      │
├─────────────────┤
│       ...       │
├─────────────────┤
│  面片N (50字节)  │
└─────────────────┘

6.1.2 网格缺陷检测

有效的3D打印需要"水密"（watertight）网格，即封闭的二维流形。常见缺陷包括：

1. 非流形边检测 边的流形性要求恰好被两个三角形共享： $$\text{Manifold}(e) \Leftrightarrow |\{f \in F : e \in \partial f\}| = 2$$ 非流形情况包括：

• T型连接：三个或更多面共享一条边
• 悬挂边：只有一个面使用该边
• 蝴蝶顶点：两个独立的面扇共享一个顶点

检测算法通过构建半边数据结构（Half-Edge）实现$O(n)$复杂度：

半边结构：
HE = {vertex, face, next, twin, edge}
检测：遍历所有半边，统计twin关系

2. 法向一致性检测 相邻三角形的法向应保持一致的朝向： $$\mathbf{n}_i \cdot \mathbf{n}_j > 0, \quad \forall (i,j) \in \text{Adjacent}$$ 使用广度优先搜索(BFS)传播法向方向：

3. 选择种子面片，确定其法向为正确方向

4. 传播到相邻面片，检查共享边的顶点顺序
5. 若顶点顺序相反则法向一致，否则需翻转

法向翻转的判定条件： $$\text{flip}(f_j) = \begin{cases} \text{true}, & \text{if } (v_1, v_2) \in f_i \land (v_2, v_1) \in f_j \\ \text{false}, & \text{if } (v_1, v_2) \in f_i \land (v_1, v_2) \in f_j \end{cases}$$

3. 孔洞检测 边界边只属于一个三角形： $$\text{Boundary}(E) = \{e \in E : |\text{faces}(e)| = 1\}$$ 孔洞的特征是形成闭合的边界环。使用并查集(Union-Find)识别连通的边界环：

• 时间复杂度：$O(n \alpha(n))$，其中$\alpha$是反阿克曼函数
• 空间复杂度：$O(n)$

4. 自相交检测 两个不相邻的三角形在空间中相交。使用空间分割加速：

• AABB树：$O(n \log n)$构建，$O(\log n)$查询
• 空间哈希：$O(n)$构建，$O(1)$平均查询

三角形相交测试使用Möller-Trumbore算法： $$\mathbf{p} = \mathbf{o} + t\mathbf{d} = (1-u-v)\mathbf{v}_0 + u\mathbf{v}_1 + v\mathbf{v}_2$$ 其中$t > 0, u \geq 0, v \geq 0, u+v \leq 1$时相交。

5. 退化三角形检测 面积接近零或形状极度扁平的三角形： $$\text{Degenerate}(T) = \begin{cases} \text{true}, & \text{if } \text{Area}(T) < \epsilon_{area} \text{ or } \text{AspectRatio}(T) > \tau \\ \text{false}, & \text{otherwise} \end{cases}$$ 长宽比计算： $$\text{AspectRatio} = \frac{\max(|e_1|, |e_2|, |e_3|)}{2 \cdot \text{Area} / \text{Perimeter}}$$

6.1.3 网格修复算法

孔洞填充算法（Advancing Front）：

1. 识别边界环 $B = \{e_1, e_2, ..., e_n\}$

2. 对每条边界边，计算最优填充三角形： $$\min_{\mathbf{v}} \left( \alpha \cdot \text{Area}(\triangle) + \beta \cdot \text{Distortion}(\triangle) \right)$$ 其中畸变度量： $$\text{Distortion}(\triangle) = \frac{\text{Perimeter}^2}{\text{Area}} - 12\sqrt{3}$$ 该值为0时表示等边三角形，值越大越畸变。

3. 迭代收缩边界直至闭合 - 选择得分最低的候选三角形 - 更新边界环 - 检查新三角形与现有网格的相交

最小面积三角剖分（Minimum Area Triangulation）： 对于平面孔洞，使用动态规划求解最优三角剖分： $$M[i,j] = \min_{i<k<j} \{M[i,k] + M[k,j] + \text{Area}(v_i, v_k, v_j)\}$$ 时间复杂度：$O(n^3)$，空间复杂度：$O(n^2)$

体积扩散法（Volume Diffusion）： 对于复杂孔洞，通过求解泊松方程填充： $$\nabla^2 \phi = 0$$ 边界条件：

• 孔洞边界：$\phi|_{\partial \Omega} = 0$
• 远场：$\phi|_{\infty} = 1$

等值面$\phi = 0.5$即为填充曲面，使用Marching Cubes提取三角网格。

自相交修复： 使用BSP树检测相交三角形对： $$\text{Intersect}(T_i, T_j) = \begin{cases} \text{true}, & \text{if } \exists \mathbf{p} \in T_i \cap T_j \\ \text{false}, & \text{otherwise} \end{cases}$$ 修复策略：

1. 局部重网格化：删除相交区域，重新三角剖分 - Delaunay三角剖分保证最大最小角 - 约束Delaunay保持原始特征边

2. 网格布尔运算： - 计算相交线 - 分割相交三角形 - 根据内外关系重组

3. 隐式曲面转换： - 转换为有向距离场(SDF) - 执行CSG运算 - 重新提取等值面

非流形修复：

1. 边分裂：将共享超过2个面的边分裂为多条边
2. 顶点分裂：将蝴蝶顶点分裂为多个独立顶点
3. 面片分离：将粘连的面片分离并填充间隙

鲁棒性网格修复流程：

1. 删除退化三角形
2. 合并重复顶点（ε-容差）
3. 修复非流形结构
4. 统一法向方向
5. 填充孔洞
6. 解决自相交
7. 优化网格质量

6.1.4 网格简化

使用二次误差度量（QEM）进行边收缩： $$\text{Error}(\mathbf{v}) = \mathbf{v}^T \mathbf{Q} \mathbf{v}$$ 其中 $\mathbf{Q}$ 是累积的平面方程矩阵： $$\mathbf{Q} = \sum_{p \in \text{planes}} \mathbf{p}\mathbf{p}^T$$ 详细的QEM算法：

1. 初始化误差矩阵： 对每个顶点$v$，其误差矩阵为相邻面片平面的二次型和： $$\mathbf{Q}_v = \sum_{f \in N(v)} \mathbf{K}_f$$ 其中平面$ax + by + cz + d = 0$的基础二次型： $$\mathbf{K} = \begin{bmatrix} a^2 & ab & ac & ad \\ ab & b^2 & bc & bd \\ ac & bc & c^2 & cd \\ ad & bd & cd & d^2 \end{bmatrix}$$

2. 边收缩代价： 边$(v_1, v_2)$收缩到新顶点$\bar{v}$的代价： $$\text{Cost}(v_1, v_2) = \bar{\mathbf{v}}^T (\mathbf{Q}_1 + \mathbf{Q}_2) \bar{\mathbf{v}}$$ 最优收缩位置通过求解线性系统获得： $$\frac{\partial \text{Cost}}{\partial \bar{\mathbf{v}}} = 0 \Rightarrow \bar{\mathbf{v}} = -(\mathbf{Q}_1 + \mathbf{Q}_2)^{-1}_{3×3} \cdot \mathbf{b}$$ 若矩阵奇异，选择中点或端点。

3. 优先队列维护： - 使用最小堆维护所有边的收缩代价 - 每次选择代价最小的边收缩 - 更新相邻边的代价 - 时间复杂度：$O(n \log n)$

特征保持简化： 加入特征边权重防止过度简化： $$\mathbf{Q}_{\text{weighted}} = \mathbf{Q}_{\text{basic}} + \lambda \cdot \mathbf{Q}_{\text{feature}}$$ 特征检测基于二面角： $$\text{Feature}(e) = \begin{cases} \text{true}, & \text{if } \cos^{-1}(\mathbf{n}_1 \cdot \mathbf{n}_2) > \theta_{\text{crease}} \\ \text{false}, & \text{otherwise} \end{cases}$$ 自适应简化： 根据局部曲率调整简化率： $$\rho_{\text{local}} = \rho_{\text{base}} \cdot \exp(-k \cdot |\kappa|)$$ 其中$\kappa$是高斯曲率，$k$是敏感度参数。

拓扑保持约束：

• Link条件：确保收缩不改变拓扑
• 防止翻转：检查法向变化
• 体积保持：限制收缩导致的体积变化 $$\Delta V = \frac{1}{6} \sum_{f \in \text{affected}} \mathbf{v}_1 \cdot (\mathbf{v}_2 \times \mathbf{v}_3)$$

6.2 自适应层高算法

6.2.1 曲率分析

局部曲率决定了层高选择。对于网格顶点，估计高斯曲率： $$K = \frac{2\pi - \sum_{i} \theta_i}{A/3}$$ 其中 $\theta_i$ 是顶点处的角度，$A$ 是相邻三角形面积和。

离散曲率计算方法：

1. 角度亏损法（Angle Deficit）： 高斯曲率基于Gauss-Bonnet定理： $$K_v = \frac{2\pi - \sum_{f \in N(v)} \theta_f}{A_{\text{mixed}}}$$ 混合面积Voronoi/重心区域： $$A_{\text{mixed}} = \begin{cases} A_{\text{Voronoi}}, & \text{if all angles} < 90° \\ A_{\text{Barycentric}}/2, & \text{if obtuse at } v \\ A_{\text{Barycentric}}/4, & \text{if obtuse elsewhere} \end{cases}$$

2. 平均曲率通过离散Laplace-Beltrami算子： $$H = \frac{1}{2}|\nabla_S \mathbf{n}| = \frac{1}{4A_{\text{mixed}}} \sum_{j \in N(v)} (\cot \alpha_{ij} + \cot \beta_{ij})(\mathbf{v}_i - \mathbf{v}_j)$$ 其中$\alpha_{ij}, \beta_{ij}$是边$e_{ij}$的对角。

3. 主曲率计算： 通过平均和高斯曲率： $$\kappa_1, \kappa_2 = H \pm \sqrt{H^2 - K}$$ 主方向通过曲率张量的特征分解获得： $$\mathbf{T} = \sum_{e \in N(v)} w_e (\mathbf{d}_e \otimes \mathbf{d}_e) \kappa_e$$ 其中$\mathbf{d}_e$是边方向，$\kappa_e$是沿边的法曲率。

曲率自适应层高映射： 根据主曲率计算局部最大允许层高： $$h_{\max}(\mathbf{p}) = \min\left(2\sqrt{\frac{2\epsilon}{|\kappa_1|}}, 2\sqrt{\frac{2\epsilon}{|\kappa_2|}}, h_{\text{printer}}\right)$$ 其中：

• $\epsilon$：最大允许弦高误差
• $\kappa_1, \kappa_2$：主曲率
• $h_{\text{printer}}$：打印机物理限制

梯度约束： 防止层高突变影响打印质量： $$\left|\frac{dh}{dz}\right| \leq \tan(\alpha_{\max})$$ 其中$\alpha_{\max}$通常为5-10°。

6.2.2 层高优化模型

给定最大允许误差 $\epsilon$，层高 $h$ 与局部曲率半径 $R$ 的关系： $$h_{\max} = 2\sqrt{2R\epsilon - \epsilon^2} \approx 2\sqrt{2R\epsilon}$$ 推导过程： 考虑圆弧被弦逼近的几何关系：

      R
     /|\
    / | \
   /  |  \
  /   ε   \
 /    |    \
------h------

根据勾股定理： $$R^2 = (R - \epsilon)^2 + (h/2)^2$$ $$R^2 = R^2 - 2R\epsilon + \epsilon^2 + h^2/4$$ $$h^2 = 8R\epsilon - 4\epsilon^2$$ $$h = 2\sqrt{2R\epsilon - \epsilon^2}$$ 当$\epsilon \ll R$时，$\epsilon^2$项可忽略。

多目标优化问题： $$\min_{h(z)} \left( w_1 \cdot T_{\text{print}} + w_2 \cdot E_{\text{surface}} + w_3 \cdot M_{\text{material}} \right)$$ 其中：

• 打印时间：$T_{\text{print}} = \sum_i \frac{A_i}{v \cdot h_i}$
• 表面误差：$E_{\text{surface}} = \sum_i \epsilon_i(h_i)$
• 材料用量：$M_{\text{material}} = \sum_i A_i \cdot w_{\text{extrusion}}$

约束条件：

• 层高范围：$h_{\min} \leq h(z) \leq h_{\max}$
• 平滑约束：$|h(z+\Delta z) - h(z)| \leq \gamma \cdot \Delta z$
• 喜嘴直径约束：$h \leq 0.8 \cdot d_{\text{nozzle}}$
• 层高量化：$h \in \{0.05, 0.10, 0.15, 0.20, 0.25, 0.30\}$mm

误差-速度权衡： 引入质量参数$Q \in [0,1]$： $$h_{\text{adaptive}}(z) = h_{\min} + (h_{\max}(z) - h_{\min}) \cdot (1 - Q)$$ $Q=1$时最高质量（最小层高），$Q=0$时最快速度（最大允许层高）。

局部细节保护： 对于关键特征（如螺纹、小孔），强制使用细层高： $$h_{\text{feature}}(z) = \begin{cases} h_{\min}, & \text{if } z \in Z_{\text{critical}} \\ h_{\text{adaptive}}(z), & \text{otherwise} \end{cases}$$

6.2.3 动态规划求解

将高度离散化为 $N$ 层，使用动态规划： $$DP[i] = \min_{j<i} \left( DP[j] + \text{Cost}(z_j, z_i) \right)$$ 其中： $$\text{Cost}(z_j, z_i) = \int_{z_j}^{z_i} \left( \frac{1}{v(z)} + \lambda \cdot e(z) \right) dz$$ 完整的动态规划算法：

1. 状态定义： - $DP[i]$：从底部到高度$z_i$的最优成本 - $\text{Parent}[i]$：记录最优路径的前驱层

2. 成本函数细化： $$\text{Cost}(z_j, z_i) = T_{\text{layer}} + E_{\text{approx}} + P_{\text{transition}}$$ 其中：

• 层打印时间：$T_{\text{layer}} = \frac{A(z_j, z_i)}{v_{\text{print}} \cdot (z_i - z_j)}$
• 逼近误差：$E_{\text{approx}} = \int_{z_j}^{z_i} \epsilon^2(z, h) dz$
• 过渡惩罚：$P_{\text{transition}} = \alpha \cdot |h_i - h_{i-1}|^2$

3. 离散化策略：

候选层高集合 H = {0.05, 0.10, 0.15, 0.20, 0.25, 0.30} mm
对每个位置 z_i：
    对每个候选层高 h ∈ H：
        若 z_i - h ≥ z_{min} 且 h ≤ h_max(z_i)：
            计算从 z_i-h 到 z_i 的成本

4. 优化剪枝： - 可行性剪枝：跳过不满足曲率约束的层高 - 界限剪枝：若当前成本已超过已知最优解，放弃 - 单调性剪枝：利用成本函数的单调性

5. 回溯重建：

i = N
layers = []
while i > 0:
    layers.append((Parent[i], i))
    i = Parent[i]
return reverse(layers)

贪婪近似算法： 为减少计算复杂度，可使用贪婪策略：

z = 0
while z < z_max:
    h = min(h_max(z), h_printer_max)
    h = quantize(h)  # 量化到最近的标准层高
    z += h
    add_layer(z, h)

时间复杂度：$O(N)$ vs DP的$O(N^2)$

混合策略：

• 关键区域使用DP优化
• 简单区域使用贪婪算法
• 过渡区域使用线性插值

6.3 填充图案生成与优化

6.3.1 基础填充模式

直线填充（Rectilinear）： 方向角 $\theta$ 下的扫描线： $$y = x \tan(\theta) + k \cdot \frac{d}{\cos(\theta)}, \quad k \in \mathbb{Z}$$ 其中 $d$ 是线间距，与填充密度 $\rho$ 的关系： $$d = \frac{w}{\rho}$$ $w$ 是挤出线宽。实际挤出线宽计算： $$w = \frac{4 \cdot \text{flow} \cdot h}{\pi \cdot d_{\text{nozzle}}}$$ 其中 flow是挤出流量系数（通常为0.9-1.1）。

网格填充（Grid）： 正交的两组平行线：

奇数层：   偶数层：
|│|│|│|    ═══════
|│|│|│|    ═══════
|│|│|│|    ═══════

强度各向同性，但层间结合较弱。

三角填充（Triangular）： 三条方向的平行线，夭角60°： $$\theta_1 = 0°, \theta_2 = 60°, \theta_3 = 120°$$ 每三层循环一次，形成等边三角形网格。

蜂窝填充（Honeycomb）： 六边形网格的顶点坐标： $$\mathbf{v}_{i,j} = \begin{bmatrix} (i + 0.5 \cdot (j \bmod 2)) \cdot \sqrt{3}a \\ j \cdot 1.5a \end{bmatrix}$$ 其中 $a$ 是六边形边长。六边形填充的优势：

• 最优的强度-重量比（自然界启发）
• 各向同性较好
• 无直角转弯，打印平滑

Gyroid填充： 三重周期极小曲面(TPMS)： $$\sin(2\pi x/p) \cos(2\pi y/p) + \sin(2\pi y/p) \cos(2\pi z/p) + \sin(2\pi z/p) \cos(2\pi x/p) = t$$ 其中$p$是周期，$t$控制密度。特点：

• 完全各向同性
• 无支撑打印
• 优异的流体渗透性

填充方向优化： 每层旋转填充方向以减少各向异性： $$\theta_n = \theta_0 + n \cdot \Delta\theta$$ 常见旋转角度：

• 45°/-45°交替
• 67.5°递增（避免重复）
• 随机角度（最大各向同性）

6.3.2 强度优化填充

根据应力分布调整局部填充密度。给定主应力场 $\sigma_1(\mathbf{x})$，填充密度： $$\rho(\mathbf{x}) = \rho_{\min} + (\rho_{\max} - \rho_{\min}) \cdot \left(\frac{|\sigma_1(\mathbf{x})|}{\sigma_{\max}}\right)^p$$ 其中 $p$ 是惩罚因子（通常取2-3）。

有限元分析集成：

1. 应力场计算： 使用简化FEA求解： $$\mathbf{K} \mathbf{u} = \mathbf{f}$$ 其中$\mathbf{K}$是刚度矩阵，$\mathbf{u}$是位移，$\mathbf{f}$是外力。

应力计算： $$\boldsymbol{\sigma} = \mathbf{D} \mathbf{B} \mathbf{u}$$ 其中$\mathbf{D}$是材料矩阵，$\mathbf{B}$是应变-位移矩阵。

2. von Mises应力： $$\sigma_{\text{VM}} = \sqrt{\frac{1}{2}[(\sigma_1-\sigma_2)^2 + (\sigma_2-\sigma_3)^2 + (\sigma_3-\sigma_1)^2]}$$ 用于各向同性材料的屈服判据。

3. 密度映射函数： SIMP法（Solid Isotropic Material with Penalization）： $$E(\rho) = E_0 \cdot \rho^p$$ 其中$E_0$是实体材料的弹性模量。

4. 梯度平滑： 防止密度突变： $$\nabla^2 \rho + \alpha(\rho_{\text{target}} - \rho) = 0$$ 使用扩散方程平滑过渡。

自适应填充算法：

1. 输入：几何、载荷、边界条件
2. FEA分析获得应力场
3. 对每个切片层：
   a. 插值应力到层平面
   b. 计算密度场ρ(x,y)
   c. 生成变密度填充路径

4. 输出：G-code

变间距填充实现：

1. Voronoi图法： 根据密度分布生成种子点，构建Voronoi图。

2. 流线法： 求解梯度场： $$\mathbf{v} = -\nabla \phi$$ 沿流线生成填充路径。

3. 空间哈希法： 将区域划分为网格，每个网格使用局部密度： $$d_{i,j} = f(\rho_{i,j})$$

6.3.3 连续路径规划

最小化抬笔次数的旅行商问题（TSP）变体。构建填充段的连接图： $$G = (V, E), \quad w(e_{ij}) = ||\mathbf{p}_i^{\text{end}} - \mathbf{p}_j^{\text{start}}||$$ 启发式算法：

1. 最近邻算法：

current = 随机选择起点
unvisited = 所有填充段 - {current}
while unvisited 非空:
    next = argmin_{s ∈ unvisited} distance(current.end, s.start)
    添加连接 current → next
    current = next
    unvisited -= {next}

时间复杂度：$O(n^2)$ 近似比：约1.25倍最优

2. 2-opt优化： 迭代改进路径：

repeat:
    improved = false
    for i = 1 to n-1:
        for j = i+2 to n:
            if d(i,i+1) + d(j,j+1) > d(i,j) + d(i+1,j+1):
                翻转路径[i+1...j]
                improved = true
until not improved

每次迭代$O(n^2)$，通常收敛快。

3. Christofides算法： 保证1.5倍近似：

• 构建最小生成树(MST)
• 找奇度顶点的最小匹配
• 组合成欧拉回路
• 转换为哈密顿路径

连接策略优化：

1. 区域划分： 将填充区域划分为子区域，先内部优化再全局连接： $$\text{Total} = \sum_{i} \text{TSP}(R_i) + \text{Connect}(R_1, ..., R_k)$$

2. 方向约束： 优先连接方向一致的线段： $$w'(e_{ij}) = w(e_{ij}) + \lambda \cdot |\theta_i - \theta_j|$$ 其中$\theta$是线段方向角。

3. 空行程优化： 利用空行程做填充： $$\text{Combing} = \begin{cases} \text{direct}, & \text{if no collision} \\ \text{boundary}, & \text{otherwise} \end{cases}$$ 螺旋填充特例： 从外向内或从内向外的连续螺旋线： $$r(\theta) = r_0 - \frac{d \cdot \theta}{2\pi}$$ 完全消除空行程，但计算复杂。

并行填充规划： 对于多喇嘴或多材料： $$\min \max_{i \in \text{nozzles}} T_i$$ 使用负载均衡算法分配填充区域。

6.4 支撑结构自动生成

6.4.1 悬垂检测

悬垂判定基于面片法向与构建方向的夹角： $$\text{Overhang}(f) = \begin{cases} \text{true}, & \text{if } \mathbf{n}_f \cdot \mathbf{z} < \cos(\theta_c) \\ \text{false}, & \text{otherwise} \end{cases}$$ 临界角 $\theta_c$ 通常为45°。

6.4.2 支撑点采样

使用泊松盘采样保证均匀分布： $$P(\mathbf{x}) \propto \exp\left(-\frac{d^2(\mathbf{x})}{2\sigma^2}\right)$$ 其中 $d(\mathbf{x})$ 是到最近支撑点的距离。

6.4.3 树状支撑生成

最小生成树算法连接支撑点到基座：

1. 初始化：每个支撑点为独立节点
2. 迭代合并最近的分支对
3. 分支半径根据负载递增： $$r(h) = r_0 \cdot \sqrt[3]{\frac{F(h)}{F_0}}$$ 其中 $F(h)$ 是高度 $h$ 处的累积负载。

6.5 非平面切片数学

6.5.1 曲面层定义

非平面层由高度场函数定义： $$z = h(x, y)$$ 满足打印头运动学约束： $$|\nabla h| \leq \tan(\alpha_{\max})$$ 其中 $\alpha_{\max}$ 是喷嘴最大倾角。

6.5.2 法向量场构建

每点的打印方向： $$\mathbf{d}(x,y) = \frac{[-\partial h/\partial x, -\partial h/\partial y, 1]^T}{\sqrt{1 + (\partial h/\partial x)^2 + (\partial h/\partial y)^2}}$$

6.5.3 碰撞检测

喷嘴锥体与已打印层的干涉检查： $$\text{Collision} = \{\mathbf{p} : ||\mathbf{p} - \mathbf{n}|| < r_{\text{nozzle}} \cdot \sin(\beta)\}$$ 使用八叉树加速空间查询。

6.6 多材料路径规划

6.6.1 材料切换优化

最小化切换次数的图着色问题。相邻区域的材料分配： $$\min \sum_{(i,j) \in E} \delta(m_i \neq m_j)$$ 使用贪婪着色或模拟退火求解。

6.6.2 清洗塔体积优化

清洗体积与材料转换矩阵： $$V_{\text{purge}}(m_i \to m_j) = V_{\text{nozzle}} \cdot k_{ij}$$ 其中 $k_{ij}$ 是经验系数（深色到浅色需要更多清洗）。

6.6.3 渐变过渡

材料混合比例的sigmoid过渡： $$\alpha(s) = \frac{1}{1 + \exp(-k(s - s_0))}$$

其中 $s$ 是路径参数，$k$ 控制过渡锐度。

本章小结

本章系统介绍了3D打印切片算法的核心数学原理：

关键概念：

• STL网格的流形性要求和修复算法
• 基于曲率的自适应层高优化
• 填充图案的强度-密度关系
• 支撑结构的力学分析
• 非平面切片的运动学约束
• 多材料打印的组合优化

核心公式：

1. 层高-曲率关系：$h_{\max} = 2\sqrt{2R\epsilon}$
2. QEM网格简化：$\text{Error}(\mathbf{v}) = \mathbf{v}^T \mathbf{Q} \mathbf{v}$
3. 悬垂判定：$\mathbf{n}_f \cdot \mathbf{z} < \cos(\theta_c)$
4. 非平面约束：$|\nabla h| \leq \tan(\alpha_{\max})$
5. 填充密度映射：$\rho(\mathbf{x}) = \rho_{\min} + (\rho_{\max} - \rho_{\min}) \cdot (|\sigma_1|/\sigma_{\max})^p$

算法复杂度：

• 网格修复：$O(n \log n)$（BSP树构建）
• 自适应层高：$O(N^2)$（动态规划）
• TSP路径优化：$O(n^2)$（启发式）
• 支撑生成：$O(n \log n)$（MST）

练习题

基础题

习题6.1 STL网格验证 给定一个包含1000个三角形的STL文件，其中有15条边只被一个三角形使用，8条边被三个三角形共享。计算： a) 这个网格有多少个孔洞？ b) 有多少条非流形边？ c) 修复后理论上应该增加多少个三角形？

提示：欧拉公式 $V - E + F = 2 - 2g$，其中$g$是亏格（孔洞数）

习题6.2 层高计算 打印一个半径$R = 50$mm的球体上半部分，最大允许台阶误差$\epsilon = 0.1$mm。 a) 在赤道处（最大曲率）的最优层高是多少？ b) 在45°纬度处的最优层高？ c) 使用固定0.2mm层高需要多少层？使用自适应层高最少需要多少层？

提示：球面任意点曲率半径等于球半径

习题6.3 填充密度 一个100×100×10mm的板件，承受中心集中载荷。使用线性填充，线宽0.4mm。 a) 20%填充密度时，线间距是多少？ b) 若中心区域应力是边缘的4倍，使用$p=2$的密度映射，中心和边缘的填充密度分别应该是多少？（假设$\rho_{\min}=10\%, \rho_{\max}=80\%$）

挑战题

习题6.4 支撑优化 设计一个算法，为倾斜45°的100mm长悬臂梁生成最少材料的支撑结构。梁截面10×10mm，材料密度$\rho$，重力加速度$g$。 a) 推导支撑柱半径随高度的变化函数 b) 比较均匀支撑vs树状支撑的材料用量 c) 考虑打印时间，如何权衡支撑密度？

提示：考虑力矩平衡和材料强度极限

习题6.5 非平面切片 设计一个鞍形表面$z = x^2/a^2 - y^2/b^2$的非平面切片策略，其中$a=b=100$mm，打印范围$[-50,50]×[-50,50]$mm。 a) 计算表面的最大梯度 b) 若喷嘴最大倾角30°，哪些区域可以非平面打印？ c) 设计过渡区域的混合策略

习题6.6 多材料TSP 4种材料打印一个10×10网格图案，每个格子随机分配材料。清洗矩阵对称，对角线为0，非对角线元素在[1,5]范围。 a) 证明这是NP-hard问题 b) 设计一个贪婪算法估计清洗次数下界 c) 若允许并行打印（多喷头），如何修改算法？

常见陷阱与错误

STL处理陷阱

1. 容差问题：浮点误差导致顶点不重合 - 解决：使用$\epsilon$-邻域合并顶点
2. 法向反转：CAD导出时法向不一致 - 解决：统一重新计算法向
3. 自相交：布尔运算产生的退化几何 - 解决：局部重新三角化

切片算法陷阱

1. Z轴缝隙：起始点对齐造成强度弱点 - 解决：随机化或螺旋化起始点
2. 薄壁消失：壁厚小于喷嘴直径 - 解决：动态调整挤出宽度
3. 尖角过挤出：路径急转弯处材料堆积 - 解决：动态流量补偿

支撑生成陷阱

1. 过度支撑：边缘效应导致不必要的支撑 - 解决：形态学腐蚀预处理
2. 支撑粘接：接触面积过大难以去除 - 解决：接触点而非接触面设计
3. 振动传递：细长支撑的共振 - 解决：增加横向连接

性能优化陷阱

1. 内存爆炸：高分辨率模型的完整mesh存储 - 解决：流式处理或空间哈希
2. 冗余计算：每层重复相同的几何查询 - 解决：增量更新数据结构
3. 数值稳定性：极小特征的舍入误差累积 - 解决：使用有理数运算或区间算术

最佳实践检查清单

切片前检查

• [ ] STL文件流形性验证
• [ ] 单位和尺度确认
• [ ] 模型方向优化（最小支撑）
• [ ] 薄壁特征识别
• [ ] 打印体积边界检查

参数配置

• [ ] 层高符合喷嘴直径（0.25-0.75倍）
• [ ] 首层高度和流量补偿
• [ ] 填充与壁厚平衡（3-4周长）
• [ ] 支撑密度与悬垂角度匹配
• [ ] 回抽参数与材料匹配

路径优化

• [ ] 最小化空行程
• [ ] 避免跨越已打印区域
• [ ] 外壁优先保证表面质量
• [ ] 尖角减速设置
• [ ] 桥接专用参数

质量保证

• [ ] 预览层视图检查
• [ ] 估算时间和材料用量
• [ ] 碰撞和干涉检测
• [ ] 首层附着优化
• [ ] 关键特征尺寸验证

高级特性

• [ ] 自适应层高启用判断
• [ ] 变密度填充应用
• [ ] 模糊皮肤/表面纹理
• [ ] 多材料切换优化
• [ ] 后处理脚本集成