一种基于粒子群算法的三角网格规范化方法

摘要

本发明公开了一种基于粒子群算法的三角网格规范化方法，该方法在保持网格几何特征的同时，能有效改善网格模型中的三角形质量。本发明通过引入粒子中心位置P_c、约束因子ξ以及自适应的惯性因子ω_a对粒子群算法改进，不仅能有效避免算法运行时陷入局部最优，而且能加快算法的收敛速度、实时调整算法的搜索范围；以顶点的局部拟合曲面为粒子群的搜索域，解决了大多算法规范化后三角网格模型体积收缩的问题；通过判断顶点调整前后的法向夹角是否在阈值内，来确定该顶点是否需要调整，从而保证了规范化后网格模型的细节特征不丢失。

主权项

一种基于粒子群算法的三角网格规范化方法，其特征在于：包括以下步骤：1)以顶点V_i为原点，V_i的法向量n_i为z轴的正向，建立一个局部坐标系，新坐标系下顶点V_i及其一阶邻域顶点集合N(V_i)拟合的三次曲面定义为；f(x,y)＝Ax³+By³+Cx²y+Dxy²+Ex²+Fy²+Gxy+Hx+Iy+J   (1)利用公式(1)对顶点V_i及其N(V_i)进行局部曲面拟合；公式中的A、B、C、D、E、F、G、H、I和J均表示系数；通过求解局部曲面方程进而得到拟合曲面方程f(x,y)的系数；(x，y，f(x,y))表示拟合曲面f(x,y)上任意一点的坐标；2)初始化粒子，将粒子的当前位置作为个体历史最优，按照公式(2)确定群体最优位置；$P_g^t=\left\{P_i^t\right|min\{f\left(P_1^t\right),f\left(P_2^t\right),\mathrm{...},f\left(P_m^t\right)\}\}---\left(2\right)$式中为整个种群在第t次迭代后的群体最优解；f(*)为适应度函数，m为种群规模；P_i^t为第i个粒子在第t次迭代时个体历史最优解，通过公式(3)得到；$P_i^t=\left\{X_i^n\right|min\{f\left(X_i^1\right),f\left(X_i^2\right),\mathrm{...},f\left(X_i^t\right)\}\}---\left(3\right)$粒子个体历史最优位置的选择方式通过公式(4)得到；$P_i^{t+1}=\left\{\begin{array}{c}{X}_i^{t+1},f\left(X_i^{t+1}\right)\le f\left(P_i^t\right)\\ P^t,f\left(X_i^{t+1}\right)>f\left(P_i^t\right)\end{array}\right.---\left(4\right)$公式(3)和(4)中，分别为第i个粒子在第t次迭代时的位置和第t+1次迭代时的位置；P_i^t、P_i^t+1分别为第i个粒子在第t和第t+1次迭代时个体历史最优解；并通过公式(5)计算粒子中心位置；$P_c^t=\left\{X_i^t\right|Med\{f\left(X_1^t\right),f\left(X_2^t\right),\mathrm{...},f\left(X_m^t\right)\}\}---\left(5\right)$式中，为第t次迭代时粒子群的中心位置，为第i个粒子在第t次迭代时的位置，f(*)为适应度函数，Med(*)为中值滤波函数，m为种群规模；3)使顶点V_i的新位置坐标满足公式(6)‑(10)的约束条件；$\Delta x=max\left\{\right|x_i|-|x_1^{V_i}|,|x_i|-|x_2^{V_i}|,\mathrm{...},|x_i|-|x_{V_{sum}}^{V_i}\left|\right\}---\left(6\right)$$\Delta y=max\left\{\right|y_i|-|y_1^{V_i}|,|y_i|-|y_2^{V_i}|,\mathrm{...},|y_i|-|y_{V_{sum}}^{V_i}\left|\right\}---\left(7\right)$${\tilde{x}}_i\in \{x_i-\Delta x,x_i+\Delta x\}---\left(8\right)$${\tilde{y}}_i\in \{y_i-\Delta y,y_i+\Delta y\}---\left(9\right)$${\tilde{z}}_i=f({\tilde{x}}_i,{\tilde{y}}_i)=A{{\tilde{x}}_i}^3+B{{\tilde{y}}_i}^3+C{{\tilde{x}}_i}^3{\tilde{y}}_i+D{\tilde{x}}_i{{\tilde{y}}_i}^2+E{{\tilde{x}}_i}^2+F{{\tilde{y}}_i}^2+G{\tilde{x}}_i{\tilde{y}}_i+H{\tilde{x}}_i+I{\tilde{y}}_i+J---\left(10\right)$公式(6)‑(10)中，为第i个顶点V_i的新位置坐标，j＝1,2,...,V_sum分别为顶点V_i一阶邻域的第j个顶点x轴和y轴的坐标值，Δx,Δy分别为顶点V_i调整时x轴和y轴坐标值的变化范围，V_sum为顶点V_i一阶邻域顶点的个数；4)对每个粒子的速度和位置按照公式(11)和(12)进行迭代更新；$V_i^{t+1}={\omega }_a{V}_i^t+c_1{r}_1(P_i^t-X_i^t)+c_2{r}_2(P_g^t-X_i^t)+c_3{r}_3(P_c^t-X_i^t)---\left(11\right)$$X_i^{t+1}=X_i^t+{\mathrm{\xi V}}_i^{t+1}---\left(12\right)$粒子的速度约束条件为：|V_i^t+1|≤V_max         (13)式中，为第t次迭代时粒子群的中心位置，c₁、c₂为学习因子，c₃为中心学习因子；r₁、r₂和r₃均服从(0，1)的随机分布；ω_a为自适应调整的惯性因子；ξ为约束因子；m为种群规模，V_max为粒子最大限制速度；ω_a＝ω_min+(ω_max‑ω_min)(E(x)‑E(x)_min)/(E(x)_max‑E(x)_min)    (14)式中，ω_min、ω_max分别为惯性因子的最小值和最大值；E(x)_max、E(x)_min分别为迭代过程中当前所有粒子适应度与目标之间误差的最大值和最小值；E(x)为当前粒子与目标之间的误差值；且为约束因子计算过程中的中间符号；5)将局部网格模型中三角形质量定义为算法目标函数，按照公式(16)计算每个粒子的适应度值；$\min Q\left(N^{V_i}\right)=1-Q_{ave}\left(N^{V_i}\right)=1-\left({\Sigma }_{k=1}^{T_{sum}}\frac{4\sqrt{3}{S}_k}{l_{k1}^2+l_{k2}^2+l_{k3}^2}\right)/T_{sum}---\left(16\right)$$Q_{ave}={\Sigma }_{k=1}^{T_{sum}}{Q}_k/T_{sum}---\left(17\right)$$Q_k=4\sqrt{3}{S}_k/(l_{k1}^2+l_{k2}^2+l_{k3}^2)---\left(18\right)$公式(16)‑(18)中，为适应度函数，为顶点V_i的一阶邻域三角形集合；T_sum为局部网格模型中三角形的个数，Q_k为第k个三角形的质量；S_k为第k个三角形面积；l_k1、l_k2、l_k3为第k个三角形的边长；Q_k描述了一个三角形的质量；然后分别按照公式(3)和(2)更新粒子的个体历史最优和群体历史最优，最后按照公式(5)重新计算粒子中心位置；6)若迭代结束或误差阈值满足条件，转到步骤7)，否则跳转到步骤3)；7)保存顶点的新位置坐标计算顶点新位置与原始位置的法向量之间的夹角并保存；8)若在阈值范围内，更新顶点位置和顶点的法向量信息，否则保持原顶点位置不变；9)若已遍历网格模型中的全部顶点，网格规范化结束，否则跳转到步骤1)。