三维网格模型四面体化方法

摘要

本发明公开了一种三维网格模型四面体化方法，包括以下步骤：(1)、模型初始位置预处理；(2)、构建体心立方结构；(3)、计算节点符号及两端节点符号相反的四面体边的切点；(4)、切点移动；(5)、边界重四面体化。本发明公开的三维模型四面体化方法，基于体心立方的网格四面体化算法，增加了三维模型主成分分析的预处理，改进了模型边界切点的移动方式转向模型特征点移动，并对最终的四面体网格使用了密度能量误差函数来优化节点的位置。三维模型运用主成分分析后，提高了初始四面体单元的质量；改进切点向模型特征点移动保证了四面体化后模型的局部特征；密度能量误差函数优化了最终四面体网格的质量。

主权项

一种三维网格模型四面体化方法，包括以下步骤：(1)、模型初始位置预处理根据三维网格模型数据中面的法向，运用表面法向主成分分析法(NPCA)提取三维网格模型的主要成分；(2)、构建体心立方结构根据三维网格模型表面曲率，自适应构建基于欧式距离变换的细分八叉树结构的体心立方，得到初始四面体；(3)、计算节点符号及两端节点符号相反的四面体边的切点计算体心立方的节点符号及切点，其中，节点符号计算方法为：根据角度权伪法矢量判断节点在三维网格模型内部或外部，定义位于三维网格模型内部的节点的符号为正，位于三维网格模型外部的节点的符号为负，位于三维网格模型表面的节点的符号为零；或者，定义位于三维网格模型外部的节点的符号为正，位于三维网格模型内部的节点的符号为负，位于三维网格模型表面的节点的符号为零；切点计算方法为：模型中节点符号不同的边所在的三角面组成一个三角面集合，分别计算每条节点符号不同的边与这些三角面所在的平面的交点，切点为在三角面内的交点；(4)、切点移动分别计算切点和两端节点之间的距离与边长的比值，比值小于阈值的切点进行移动，切点移动方向为三维网格模型表面的特征点，且该特征点对应的虚拟原点与切点之间的距离最小；其中，切点移动方向的确定方法为：计算切点所在三维网格三角面的特征点，使用拉普拉斯算法计算各特征点对应的拉普拉斯坐标虚拟原点，计算切点和各虚拟原点之间的距离，移动方向为与切点距离最小的虚拟原点对应的特征点，所述拉普拉斯算法具体为：三维网格上某一点的拉普拉斯坐标定义为该点指向其相邻点的所有向量之和，拉普拉斯坐标具有平移不变性，使用网格上相邻顶点的线性组合来表示顶点的网格坐标，描述网格的细节特性和局部特征，具体的拉普拉斯坐标公式表示如下：${\sigma }_i=\underset{j\in N\left(i\right)}{\Sigma }{w}_{ij}(v_i-v_j)$其中N(i)＝{j{i,j}∈E}是与顶点v_i的相邻的顶点的集合，w_ij表示顶点v_i和v_j之间的权重，满足等式(5)、边界重四面体化基于网格质量的密度能量误差函数对四面体的边界重新四面体化，构成逼近模型的四面体网格；其中，基于网格质量的密度能量误差函数如下：$E_{ODT}=\frac{1}{4}\underset{i}{\Sigma }{x_i}^2\left({\Sigma }_{T_j\in {\Omega }_i}{q}_j\right|T_j\left|\right)-{\int }_M{x}^{2}dx$其中，M是整个网格空间，E_ODT是网格空间M的密度能量误差，x_i是网格节点的当前位置，Ω_i是以x_i为中心节点的星型结构，T_j是星型结构Ω_i中的网格单元，x是网格空间M中的任意位置，q_j是网格单元T_j的网格质量；|T_j|是T_j的面积，通过求解上式的极小值可得优化后节点的位置为：${x_i}^{*}=\frac{1}{{\Sigma }_{T_j\in {\Omega }_i}{q}_j\left|T_j\right|}\underset{T_j\in {\Omega }_i}{\Sigma }{q}_j\left|T_j\right|c_j$其中x_i^＊是x_i的优化后的位置，c_j是T_j的外接圆圆心，Ω_i是以x_i为中心节点的星型结构，T_j是星型结构Ω_i中的网格单元，x是网格空间M中的任意位置，q_j是网格单元T_j的网格质量；在四面体网格中，网格单元的质量函数可设为：$q=\sqrt{24}\frac{r}{l_{max}}$其中r为四面体的内接球半径，l_max是四面体的最长边。