切片软件是3D打印工作流程的核心，它将三维模型转换为打印机可执行的层级路径指令。本章深入探讨切片算法的数学原理，从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文件有两种格式：
二进制STL结构：
┌─────────────────┐
│ 80字节文件头 │
├─────────────────┤
│ 4字节面片数(N) │
├─────────────────┤
│ 面片1 (50字节) │
│ - 法向量(12B) │
│ - 顶点1(12B) │
│ - 顶点2(12B) │
│ - 顶点3(12B) │
│ - 属性(2B) │
├─────────────────┤
│ ... │
├─────────────────┤
│ 面片N (50字节) │
└─────────────────┘
有效的3D打印需要”水密”（watertight）网格，即封闭的二维流形。常见缺陷包括：
1. 非流形边检测 边的流形性要求恰好被两个三角形共享： \(\text{Manifold}(e) \Leftrightarrow |\{f \in F : e \in \partial f\}| = 2\)
非流形情况包括：
检测算法通过构建半边数据结构（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)传播法向方向：
法向翻转的判定条件： \(\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)识别连通的边界环：
4. 自相交检测 两个不相邻的三角形在空间中相交。使用空间分割加速：
三角形相交测试使用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}}\)
孔洞填充算法（Advancing Front）：
对每条边界边，计算最优填充三角形： \(\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时表示等边三角形，值越大越畸变。
最小面积三角剖分（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. 删除退化三角形
2. 合并重复顶点（ε-容差）
3. 修复非流形结构
4. 统一法向方向
5. 填充孔洞
6. 解决自相交
7. 优化网格质量
使用二次误差度量（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算法：
初始化误差矩阵： 对每个顶点$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}\)
边收缩代价： 边$(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}\)
若矩阵奇异，选择中点或端点。
优先队列维护：
特征保持简化： 加入特征边权重防止过度简化： \(\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$是敏感度参数。
拓扑保持约束：
局部曲率决定了层高选择。对于网格顶点，估计高斯曲率： \(K = \frac{2\pi - \sum_{i} \theta_i}{A/3}\)
其中 $\theta_i$ 是顶点处的角度，$A$ 是相邻三角形面积和。
离散曲率计算方法：
角度亏损法（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}\)
平均曲率通过离散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}$的对角。
主曲率计算： 通过平均和高斯曲率： \(\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)\)
其中：
梯度约束： 防止层高突变影响打印质量： \(\left|\frac{dh}{dz}\right| \leq \tan(\alpha_{\max})\)
其中$\alpha_{\max}$通常为5-10°。
给定最大允许误差 $\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)\)
其中：
约束条件：
| 平滑约束：$ | h(z+\Delta z) - h(z) | \leq \gamma \cdot \Delta z$ |
误差-速度权衡： 引入质量参数$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}\)
将高度离散化为 $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\)
完整的动态规划算法：
成本函数细化： \(\text{Cost}(z_j, z_i) = T_{\text{layer}} + E_{\text{approx}} + P_{\text{transition}}\)
其中：
| 过渡惩罚：$P_{\text{transition}} = \alpha \cdot | h_i - h_{i-1} | ^2$ |
候选层高集合 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 的成本
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)$
混合策略：
直线填充（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\)
常见旋转角度：
根据应力分布调整局部填充密度。给定主应力场 $\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）。
有限元分析集成：
应力场计算： 使用简化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}$是应变-位移矩阵。
von Mises应力： \(\sigma_{\text{VM}} = \sqrt{\frac{1}{2}[(\sigma_1-\sigma_2)^2 + (\sigma_2-\sigma_3)^2 + (\sigma_3-\sigma_1)^2]}\)
用于各向同性材料的屈服判据。
密度映射函数： SIMP法（Solid Isotropic Material with Penalization）： \(E(\rho) = E_0 \cdot \rho^p\)
其中$E_0$是实体材料的弹性模量。
梯度平滑： 防止密度突变： \(\nabla^2 \rho + \alpha(\rho_{\text{target}} - \rho) = 0\)
使用扩散方程平滑过渡。
自适应填充算法：
1. 输入：几何、载荷、边界条件
2. FEA分析获得应力场
3. 对每个切片层：
a. 插值应力到层平面
b. 计算密度场ρ(x,y)
c. 生成变密度填充路径
4. 输出：G-code
变间距填充实现：
Voronoi图法： 根据密度分布生成种子点，构建Voronoi图。
流线法： 求解梯度场： \(\mathbf{v} = -\nabla \phi\)
沿流线生成填充路径。
空间哈希法： 将区域划分为网格，每个网格使用局部密度： \(d_{i,j} = f(\rho_{i,j})\)
最小化抬笔次数的旅行商问题（TSP）变体。构建填充段的连接图： \(G = (V, E), \quad w(e_{ij}) = ||\mathbf{p}_i^{\text{end}} - \mathbf{p}_j^{\text{start}}||\)
启发式算法：
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倍最优
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)$，通常收敛快。
连接策略优化：
区域划分： 将填充区域划分为子区域，先内部优化再全局连接： \(\text{Total} = \sum_{i} \text{TSP}(R_i) + \text{Connect}(R_1, ..., R_k)\)
方向约束： 优先连接方向一致的线段： \(w'(e_{ij}) = w(e_{ij}) + \lambda \cdot |\theta_i - \theta_j|\)
其中$\theta$是线段方向角。
空行程优化： 利用空行程做填充： \(\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\)
使用负载均衡算法分配填充区域。
悬垂判定基于面片法向与构建方向的夹角： \(\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°。
使用泊松盘采样保证均匀分布： \(P(\mathbf{x}) \propto \exp\left(-\frac{d^2(\mathbf{x})}{2\sigma^2}\right)\)
其中 $d(\mathbf{x})$ 是到最近支撑点的距离。
最小生成树算法连接支撑点到基座：
其中 $F(h)$ 是高度 $h$ 处的累积负载。
非平面层由高度场函数定义： \(z = h(x, y)\)
满足打印头运动学约束： \(|\nabla h| \leq \tan(\alpha_{\max})\)
其中 $\alpha_{\max}$ 是喷嘴最大倾角。
每点的打印方向： \(\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}}\)
喷嘴锥体与已打印层的干涉检查： \(\text{Collision} = \{\mathbf{p} : ||\mathbf{p} - \mathbf{n}|| < r_{\text{nozzle}} \cdot \sin(\beta)\}\)
使用八叉树加速空间查询。
最小化切换次数的图着色问题。相邻区域的材料分配： \(\min \sum_{(i,j) \in E} \delta(m_i \neq m_j)\)
使用贪婪着色或模拟退火求解。
清洗体积与材料转换矩阵： \(V_{\text{purge}}(m_i \to m_j) = V_{\text{nozzle}} \cdot k_{ij}\)
其中 $k_{ij}$ 是经验系数（深色到浅色需要更多清洗）。
材料混合比例的sigmoid过渡： \(\alpha(s) = \frac{1}{1 + \exp(-k(s - s_0))}\)
其中 $s$ 是路径参数，$k$ 控制过渡锐度。
本章系统介绍了3D打印切片算法的核心数学原理：
关键概念：
核心公式：
| 非平面约束：$ | \nabla h | \leq \tan(\alpha_{\max})$ |
| 填充密度映射：$\rho(\mathbf{x}) = \rho_{\min} + (\rho_{\max} - \rho_{\min}) \cdot ( | \sigma_1 | /\sigma_{\max})^p$ |
算法复杂度：
习题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) 若允许并行打印（多喷头），如何修改算法？