一种误差可控的参数曲面网格生成方法

1.本发明涉及计算机图形处理技术领域，尤其涉及一种误差可控的参数曲面网格生成方法。


背景技术：

2.参数表示和网格表示都是表示三维几何形状的重要方法，它们在计算机辅助设计(cad)和计算机辅助工程(cae)中发挥着至关重要的作用。参数表示具有连续、精确的特点，是cad系统中几何建模的常用表示。网格表示则为离散表示，是cae系统中物理仿真计算的常用表示。cad设计得到的参数模型在导入cae进行仿真计算前，通常还需利用参数曲面网格生成方法实现表示方式转换。
3.在cad系统中，边界表示(boundary representation)的参数曲面模型十分常见，这些模型通常以iges、step格式存贮，并且是大部分曲面造型技术所运用的基础几何表示方式。从边界表示的模型生成网格是数值模拟、快速成型、计算流体力学、可视化等众多领域关注的重点问题。然而，目前的主流cad软件如open cascade、netgen、gmesh等在网格生成过程中仍然会产生错误网格结构，如退化三角形、网格缝隙等，并且无法控制生成网格的误差。尽管错误网格结构可以使用网格修复技术进行修复，但修复结果往往存在较大误差。
4.导致网格生成产生错误网格结构的原因之一是边界表示的模型本身不水密。由于边界表示模型上两个面片的共边是在两片参数曲面的参数域上分别存储的，因此会受到计算机截断误差的影响产生缝隙。此外，设计误差、布尔运算求交误差、不同cad软件的不同精度要求导致的误差等都会破坏模型水密性。因此，网格生成流程必须对模型的重边和重点进行特殊处理。目前修复模型水密性通常采取两种手段，一种是通过局部网格编辑操作填补、合并网格上的缝隙，该方法仅适用于缝合间距较小的缝隙，且无法识别在几何上互相重合的网格边，另一种是首先通过全局重构建模型的隐式曲面，再对该曲面进行离散化来生成水密网格，该过程能保证输出水密网格，但该类算法会模糊网格的尖点、硬边界、薄板等重要特征，导致生成网格模型存在较大误差。此外，这两类方法都不能保证生成网格中存在与参数曲面边界线对应的网格边，不利于模型的查看和修改。
5.对于物理仿真等应用来说，面网格模型除了需要保持水密性，还需要尽可能地降低误差和分辨率并提升网格三角面片质量，这一目标可采用网格简化的方法实现。基于局部网格编辑的网格简化算法可使用连续参数曲面的表征，也可使用离散网格曲面的表征。使用参数曲面表征的好处是几何精度高，能快速计算曲面点的位置、切向量、曲率等属性，但其相关几何计算通常是非线性的，存在数值稳定性问题，且投影点计算较为耗时。使用网格曲面表征的好处是投影计算方便，相关几何计算为线性的，快速有效，但存在一定的离散误差。目前大部分网格简化算法仅利用网格表征进行计算，无法精确控制离散化过程中的误差。
6.因此，提出一种误差可控的参数曲面网格生成方法，来解决现有技术存在的困难，是本领域技术人员亟需解决的问题。


技术实现要素：

7.有鉴于此，本发明提供了一种误差可控的参数曲面网格生成方法，利用网格局部编辑的方法来设计网格生成算法，将边界表示的参数曲面模型转换为满足误差要求的水密网格模型。
8.为了实现上述目的，本发明采用如下技术方案：
9.一种误差可控的参数曲面网格生成方法，包括以下步骤：
10.s1、输入边界表示参数曲面模型，对参数曲面模型进行均匀采样，得到初始化网格；
11.s2、优化边界采样点，得到初始优化网格；
12.s3、对初始优化网格的内部采样点进行优化，得到后优化网格；
13.s4、对后优化网格进行全局优化，生成最终网格。
14.上述的方法，可选的，s1中，按照三维曲线的长度对边界参数曲面模型进行均匀采样，对于表示同一共边的两条边界，采样点数一致。
15.上述的方法，可选的，s2中，对表示共边的两条边界中的一条进行优化，使边界线满足给定的距离误差要求，然后按照同样的长度比例对代表相同共边的另一条边界线进行同步网格局部编辑操作，以保持两条边界线顶点的配对关系；
16.在边界优化结束后，使用cdt生成初始优化网格。
17.上述的方法，可选的，共边的两条边界的优化方法采用以下公式：
[0018][0019]
其中，为边界线vavb的目标长度，为曲面在vc处的最小曲率半径，为边界线在vc处的曲率半径，e为给定的误差值。
[0020]
上述的方法，可选的，同步网格局部编辑操作为：对于表示同一共边的两条边界，其中一条边界线进行边分裂、边合并和采样点位置优化操作时，另一条边界线也按相同边长比例进行边分裂、边合并和采样点位置优化操作。
[0021]
上述的方法，可选的，s3中对初始优化网格的内部采样点进行优化，具体内容为：使用映射距离来判断网格与边界参数曲面模型的距离，使内部网格满足误差，即完成对初始优化网格的内部采样点的优化。
[0022]
上述的方法，可选的，使内部网格满足误差的方法采用以下公式：
[0023][0024]
其中，为顶点va的目标长度，la为相邻边的最小边长，为三角面重心到曲面的距离，为曲面处的最小曲率半径，e为给定的误差值，i＝1,2,...,na为va的相邻三角面。
[0025]
上述的方法，可选的，s4中对后优化网格进行全局优化的具体内容包括：
[0026]
s4.1狭长三角形优化；
[0027]
s4.2全局角度优化；
[0028]
s4.3全局误差优化。
[0029]
经由上述的技术方案可知，与现有技术相比，本发明提供了一种误差可控的参数曲面网格生成方法，具有以下有益效果：在网格生成过程中通过同步编辑网格共边的操作来保证生成网格的协调性，合并协调网格的匹配点生成水密网格；此外，针对误差要求设计了两个新目标边长计算方法，利用该目标边长进行网格局部编辑操作可生成满足误差要求的三角网格；在误差可控的基础上，综合利用连续参数曲面表征和离散网格曲面表征进行全局质量优化可获得高质量低误差的三角网格。
附图说明
[0030]
为了更清楚地说明本发明实施例或现有技术中的技术方案，下面将对实施例或现有技术描述中所需要使用的附图作简单地介绍，显而易见地，下面描述中的附图仅仅是本发明的实施例，对于本领域普通技术人员来讲，在不付出创造性劳动的前提下，还可以根据提供的附图获得其他的附图。
[0031]
图1为本发明提供的一种误差可控的参数曲面网格生成方法流程图；
[0032]
图2为本发明提供的步骤s1-s4中所用的网格局部编辑操作示意图；
[0033]
图3为本发明提供的步骤s1-s4的结果示意图；
[0034]
图4为本发明提供的不同误差要求下生成的鼠标网格模型结果图；
[0035]
图5为本发明提供的gmsh、netgen和本发明在齿轮模型上生成的网格模型结果对比图；
[0036]
图6为本发明提供的gmsh、netgen和本发明在蜂鸟模型上生成的网格模型结果对比图；
[0037]
图7为本发明提供的gmsh、netgen和本发明在涡轮模型上生成的网格模型结果对比图；
[0038]
图8为本发明提供的gmsh、netgen和本发明在鼠标模型上生成的网格模型结果对比图；
[0039]
图9为本发明提供的gmsh、netgen和本发明在枕头模型上生成的网格模型结果对比图。
具体实施方式
[0040]
下面将结合本发明实施例中的附图，对本发明实施例中的技术方案进行清楚、完整地描述，显然，所描述的实施例仅仅是本发明一部分实施例，而不是全部的实施例。基于本发明中的实施例，本领域普通技术人员在没有做出创造性劳动前提下所获得的所有其他实施例，都属于本发明保护的范围。
[0041]
参照图1所示，本发明公开了一种误差可控的参数曲面网格生成方法，包括以下步骤：
[0042]
s1、输入边界表示参数曲面模型，对参数曲面模型进行均匀采样，得到初始化网格；
[0043]
s2、优化边界采样点，得到初始优化网格；
[0044]
s3、对初始优化网格的内部采样点进行优化，得到后优化网格；
[0045]
s4、对后优化网格进行全局优化，生成最终网格。
[0046]
进一步的，s1中，按照三维曲线的长度对边界参数曲面模型进行均匀采样，对于表示同一共边的两条边界，采样点数一致。
[0047]
具体的，输入为边界表示的cad模型(iges或step格式)模型中包含n片边界表示的参数曲面然后需要用户提供一个给定的误差值e，代表曲面到三角网格的单边hausdorff距离。算法的输出为满足误差e的三角网格。
[0048]
s1利用参数域的等参线得到初始化网格(图3b所示)，具体内容为：首先在参数域内部生成等参线网格；然后按照三维曲线的长度对边界线进行均匀采样，对于表示同一共边的两条边界，保证其采样点数一致；最后利用受约束的delaunay三角剖分(cdt)生成初始化网格并通过曲面参数方程得到曲面网格。
[0049]
进一步的，s2中，对表示共边的两条边界中的一条进行优化，使边界线满足给定的距离误差要求，然后按照同样的长度比例对代表相同共边的另一条边界线进行同步网格局部编辑操作，以保持两条边界线顶点的配对关系；
[0050]
在边界优化结束后，使用cdt生成初始优化网格。
[0051]
进一步的，共边的两条边界的优化方法采用以下公式：
[0052][0053]
其中，为边界线vavb的目标长度，为曲面在vc处的最小曲率半径，为边界线在vc处的曲率半径，e为给定的误差值。
[0054]
进一步的，同步网格局部编辑操作为：对于表示同一共边的两条边界，其中一条边界线进行边分裂、边合并和采样点位置优化操作时，另一条边界线也按相同边长比例进行边分裂、边合并和采样点位置优化操作。
[0055]
具体的，s2中优化边界采样点的优化过程包含下述步骤：
[0056]
步骤s2.1计算目标边长：对边界线上的每条线段计算一个目标边长，使得当线段长度为目标边长时边界线能满足距离误差。给定顶点为的线段vavb，其对应的曲线为参数曲面与之间的一段交线。令为线段vavb对应曲线段的中点。为了使边长满足距离误差要求，首先计算曲面在vc处的最小曲率半径曲面在vc处的最小曲率半径和曲线段在vc处的曲率半径然后按以下方式计算线段vavb的目标长度的目标长度最后，为了避免生成的线段过长或过短，可将目标长度限制在给定范围[l
min
,l
max
]内。
[0057]
步骤s2.2边分裂优化：当线段vavb的边长l
ab
大于时，在线段vavb中间插入线段vavb对应曲线段的中点vc，并更新vc相邻线段的目标边长。
[0058]
步骤s2.3边合并优化：当线段vavb的边长l
ab
小于时，合并线段vavb到其对应曲线段的中点vc，并更新线段v
a-1
vc和vcv
b+1
的目标边长，其中v
a-1
为va的上一个采样点，vcv
b+1
为vb的下一个采样点。
[0059]
步骤s2.4采样点位置优化：对两条线段vavb和vbvd的公共点vb，根据目标边长和优化点vb的位置使其满足其中分别表示线段vavb和vbvd对应曲线段的长度。
[0060]
进一步的，s3中对初始优化网格的内部采样点进行优化，具体内容为：使用映射距离来判断网格与边界参数曲面模型的距离，使内部网格满足误差，即完成对初始优化网格的内部采样点的优化。
[0061]
进一步的，使内部网格满足误差的方法采用以下公式：
[0062][0063]
其中，为顶点va的目标长度，la为相邻边的最小边长，为三角面重心到曲面的距离，为曲面处的最小曲率半径，e为给定的误差值，i＝1,2,...,na为va的相邻三角面。
[0064]
具体的，s3中对初始优化网格的内部采样点进行优化，具体内容为：
[0065]
使用映射距离来估计网格与曲面的距离。曲面网格上三角形面片f的映射距离为f在参数域上的重心代表的曲面点p1和f的重心p2之间的距离。这一步的优化过程由算法2给出，算法中包含下述步骤。
[0066]
步骤s3.1计算目标边长：这一步的目的是对网格上的每一点va计算一个目标长度使得当网格每条边长不超过两边端点目标长度之和时，网格满足距离误差。对网格上的每一个顶点va，计算其相邻边的最小边长la。令为va的相邻三角面，为三角面的重心，为三角面重心到曲面的距离，为到曲面的投影点，为曲面处的最小曲率半径。则顶点va的目标长度为：
[0067]
步骤s3.2边分裂优化：vavb的边长l
ab
与目标边长满足时，对网格执行边分裂操作，即在边vavb中间插入边中点vc，并分裂与边vavb相邻的面片。在处理完所有网格边后，更新网格的目标边长。
[0068]
步骤s3.3边合并优化：当网格边vavb的边长l
ab
与目标边长满足时，合并线段vavb到线段vavb对应曲线段的中点vc。在处理完所有网格边后，更新网格的目标边长。
[0069]
步骤s3.4顶点度优化：网格顶点的相邻边数称为网格顶点的度，内部网格顶点的
目标度为6，边界网格顶点的目标度为其中θ为边界边之间的内部夹角。这一步的目标是使网格顶点的度尽量接近目标度。对于每一条网格边vavb，设其相邻三角形分别为vavbvc和vavbvd，其中四个网格点va,vb,vc,vd的度分别为da,db,dc,dd，目标度分别为oa,ob,oc,od。如果边翻转操作能够优化四个网格点的度，即|d
a-1-oa|+|d
b-1-ob|+|dc+1-oc|+|dd+1-od|＜|d
a-oa|+|d
b-ob|+|d
c-oc|+|d
d-od|，则翻转边vavb并更新网格的目标边长。
[0070]
步骤s3.5顶点位置优化：首先，对每个内部顶点va，计算所有相邻面片的重心然后根据每个面片的三个顶点va,的目标长度计算面片的权重其中为所有顶点的目标长度的平均值。最后，更新顶点va的位置：其中为三角面片的面积，p(p)表示空间点p到曲面的投影。
[0071]
步骤s3.6角度优化：这一步的目标为优化角度能量其中θi,i＝1,...,n
angle
为网格内部所有三角形的内角。对三角形对每条内部网格边vavb，检查边翻转是否能降低角度能量e
angle
，若可以则翻转边vavb。
[0072]
进一步的，s4中对后优化网格进行全局优化的具体内容包括：
[0073]
s4.1狭长三角形优化；
[0074]
s4.2全局角度优化；
[0075]
s4.3全局误差优化。
[0076]
具体的，s4.1狭长三角形优化
[0077]
这一步依旧在边界采样点固定的条件下，依次对每一片参数曲面进行优化，包含下述步骤。
[0078]
步骤s4.1.1边分裂优化：对所有包含角度小于15度的三角形f，计算其最短边的长度ls，如果三角形f中非边界边ei的长度大于2ls，则任选这样的一条的边进行分裂。分裂过程中记录新增的顶点数n
inserted
。
[0079]
步骤s4.1.2边合并优化：按照角度从小到大的顺序依次对小角的对边进行合并，当合并数量达到时结束合并。
[0080]
s4.2全局角度优化
[0081]
在这一步，首先对前述步骤得到的所有曲面片的网格进行合并生成水密网格mw，然后对mw进行全局优化。优化过程中参数曲面片顶点对应的网格点保持固定，参数曲面片边界对应的边界边保持标记，边界边上的端点始终位于曲面片的边界上。由于网格mw已足够接近曲面，全局优化的过程中可以使用空间点到mw的投影替代空间点到曲面的投影。全局优化包含下述步骤。
[0082]
步骤s4.2.1计算目标边长：与步骤s2.1不同，该步使用当前网格来估计顶点处的最小曲率半径ra而不是使用参数曲面来估计最小曲率半径。网格上每个顶点va的目标长度为：网格上的最小曲率半径ra可通过网格的平均曲率与高斯曲率求出。
[0083]
步骤s4.2.2边分裂优化：计算钝角三角形的个数n
obtuse
，对所有钝角三角形f，按照钝角从大到小的顺序分裂前个钝角三角形的其最长边，并记录新增的顶点数n
inserted
。对于最长边为曲面边界边的情况下，新增顶点需投影到曲面边界上。
[0084]
步骤s4.2.3边合并优化：按照角度从小到大的顺序依次对小角的对边进行合并，当合并数量达到n
inserted
时结束，此外，当合并边vavb的顶点包含边界边上的顶点时，合并顶点需投影到合并。当合并边vavb的顶点包含参数曲面的顶点va时，vavb被合并到va处对应的曲面边界上；当合并边的顶点包含两条不同边界边上的顶点时，取消合并。
[0085]
步骤s4.2.4顶点位置优化：这一步与步骤s3.5类似，不同之处为步骤s3.5中计算权重使用的目标边长改为步骤s4.2.1所得目标边长，且空间点到曲面的投影p(
·
)改为到水密网格mw的投影。
[0086]
s4.3全局误差优化
[0087]
网格误差全局优化阶段首先将全局角度优化中边分裂(步骤s4.2.2)的条件由钝角三角形改为误差较大三角形，称该边分裂步骤为优化误差的边分裂步骤，然后对以下步骤循环执行3-4次：优化误差的边分裂步骤、顶点度优化(步骤s3.4)、计算网格目标边长(步骤s4.2.1)和更新顶点位置优化(步骤s4.2.4)。
[0088]
图2展示了本发明步骤s1-s4中所用的网格局部编辑操作示意图，第一行为编辑前网格，第二行为编辑后网格；2a为边分裂、2b为边合并、2c为边翻转、2d为顶点位置优化。
[0089]
图3展示了本发明步骤s1-s4过程中的结果示意图，3a为s1输入的边界表示参数曲面模型，由六片参数曲面组成；3b为s1的网格初始化结果；3c为s2的边界采样点优化结果；3d为s3的内部采样点误差优化结果；3e为s4全局角度和误差优化结果。
[0090]
图4展示了不同的误差限制生成的不同分辨率的鼠标网格模型。对应的网格质量指标由表1给出。在不同给定误差下，本发明生成的网格模型均能满足误差要求。其中，4a为e＝0.03、4b为e＝0.12、4c为e＝0.3、4d为e＝0.6。
[0091]
表1不同误差要求生成的鼠标网格模型质量指标
[0092][0093]
其中，鼠标模型包围盒长度为229.36。e为输入的距离误差。|v|为模型顶点数。h为参数模型到网格模型的单边hausdorff距离。d为参数模型到网格模型的平均距离。θ
min
为网格最小角度。θ
max
为网格最大角度。为所有网格面片最小角的平均值。θ
＜30
°
％为最小角小于30度的三角形占比。
[0094]
图5-图9中，其中，5a、6a、7a、8a、9a分别表示gmsh生成的齿轮、蜂鸟、涡轮、鼠标和
枕头网格模型；5b、6b、7b、8b、9b分别表示netgen生成的齿轮、蜂鸟、涡轮、鼠标和枕头网格模型；5c、6c、7c、8c、9c分别表示本发明生成的齿轮、蜂鸟、涡轮、鼠标和枕头网格模型。其中，本发明生成图示网格所使用的误差指标e分别为0.2，1.0，0.06，0.12，0.4。对应的网格质量指标由表2给出。
[0095]
表2本算法与开源网格生成软件gmsh和netgen的比较
[0096][0097]
其中，l为模型包围盒对角线长度。p为模型面片数。|v|为模型顶点数。h为参数模型到网格模型的单边hausdorff距离。d为参数模型到网格模型的平均距离。θ
min
为网格最小角角度。θ
max
为网格最大角角度。为所有网格面片最小角的平均值。θ
＜30
°
％为最小角小于30度的三角形占比。
[0098]
表2指标显示本发明在网格分辨率大幅低于gmsh和netgen生成网格的情况下，仍能生成最大误差和平均误差都更低的网格，且网格均能误差要求。在网格角度质量上，本算法的最小角、最大角及小角三角形的占比这几个指标整体优于gmsh，且指标水平与netgen相当，同时本发明在鼠标和枕头模型上均具有最优的精度和质量指标。特别地，在图8的鼠标模型上，gmsh和netgen生成网格均不水密，而本发明生成网格为水密网格。
[0099]
对所公开的实施例的上述说明，使本领域专业技术人员能够实现或使用本发明。对这些实施例的多种修改对本领域的专业技术人员来说将是显而易见的，本文中所定义的一般原理可以在不脱离本发明的精神或范围的情况下，在其它实施例中实现。因此，本发明将不会被限制于本文所示的这些实施例，而是要符合与本文所公开的原理和新颖特点相一致的最宽的范围。

技术特征：
1.一种误差可控的参数曲面网格生成方法，其特征在于，包括以下步骤：s1、输入边界表示参数曲面模型，对参数曲面模型进行均匀采样，得到初始化网格；s2、优化边界采样点，得到初始优化网格；s3、对初始优化网格的内部采样点进行优化，得到后优化网格；s4、对后优化网格进行全局优化，生成最终网格。2.根据权利要求1所述的一种误差可控的参数曲面网格生成方法，其特征在于，s1中，按照三维曲线的长度对参数曲面模型进行均匀采样，对于表示同一共边的两条边界，采样点数一致。3.根据权利要求1所述的一种误差可控的参数曲面网格生成方法，其特征在于，s2中，对表示共边的两条边界中的一条进行优化，使边界线满足给定的距离误差要求，然后按照同样的长度比例对代表相同共边的另一条边界线进行同步网格局部编辑操作，以保持两条边界线顶点的配对关系；在边界优化结束后，使用cdt生成初始优化网格。4.根据权利要求3所述的一种误差可控的参数曲面网格生成方法，其特征在于，共边的两条边界的优化方法采用以下公式：其中，为边界线v
a
v
b
的目标长度，为曲面在v
c
处的最小曲率半径，为边界线在v
c
处的曲率半径，e为给定的误差值。5.根据权利要求3所述的一种误差可控的参数曲面网格生成方法，其特征在于，同步网格局部编辑操作为：对于表示同一共边的两条边界，其中一条边界线进行边分裂、边合并和采样点位置优化操作时，另一条边界线也按相同边长比例进行边分裂、边合并和采样点位置优化操作。6.根据权利要求1所述的一种误差可控的参数曲面网格生成方法，其特征在于，s3中对初始优化网格的内部采样点进行优化，具体内容为：使用映射距离来判断网格与边界参数曲面模型的距离，使内部网格满足误差，即完成对初始优化网格的内部采样点的优化。7.根据权利要求6所述的一种误差可控的参数曲面网格生成方法，其特征在于，使内部网格满足误差的方法采用以下公式：其中，为顶点v
a
的目标长度，l
a
为相邻边的最小边长，为三角面重心到曲面的距离，为曲面处的最小曲率半径，e为给定的误差值，i＝1,2,...,n
a
为v
a
的相邻三角面。8.根据权利要求1所述的一种误差可控的参数曲面网格生成方法，其特征在于，s4中对后优化网格进行全局优化的具体内容包括：s4.1狭长三角形优化；s4.2全局角度优化；
s4.3全局误差优化。

技术总结
本发明公开了一种误差可控的参数曲面网格生成方法，涉及计算机辅助几何设计技术领域。包括：S1、输入边界表示参数曲面模型，对参数曲面模型进行均匀采样，得到初始化网格；S2、优化边界采样点，得到初始优化网格；S3、对初始优化网格的内部采样点进行优化，得到后优化网格；S4、对后优化网格进行全局优化，生成最终网格。本发明在网格生成过程中通过同步编辑网格共边的操作来保证生成网格的协调性，合并协调网格的匹配点生成水密网格；此外，针对误差要求设计了两个新目标边长计算方法，利用该目标边长进行网格局部编辑操作可生成满足误差要求的三角网格。求的三角网格。求的三角网格。


技术研发人员：贾晓红 严冬明 曾铮
受保护的技术使用者：中国科学院数学与系统科学研究院
技术研发日：2023.07.04
技术公布日：2023/9/22