论文部分内容阅读
摘 要：在对三维图像进行有限元数值模拟解析时，为了对连续的计算区域进行数值计算，达到模拟仿真的效果，必须先对三维图像进行网格剖分。Delaunay三角网格剖分算法是生成网格的一种有效方法。本文介绍了Delaunay三角网格剖分算法，以及在约束条件下的网格细分，最后给出了该算法在三维实体造型中的应用。
关键词：三角剖分；网格生成；网格细分
Abstract： In the simulation analysis of the 3D finite element numerical， in order to carry out the numerical calculation for the calculation of continuous area， achieve the simulation results， we must first on the 3D mesh. Delaunay triangulation algorithm is an effective method to generate mesh. This paper introduces the Delaunay triangulation algorithm， and in the condition of mesh subdivision， finally the application of the algorithm in 3D solid modeling are given in this paper.
Keywords： triangulation，mesh generation，mesh subdivision
1、引言
网格生成是有限元模拟计算的先决条件，有限元计算的效率和精确度在很大程度上受生成的网格质量的影响。在进行电磁场有限元仿真计算时，首先需要创建三维实体模型，然后需要根据一些限定的约束条件生成网格，对于几何形状复杂的模型，要自动生成满足约束条件的，高质量的网格是一项极其困难的事情，而Delaunay三角网格剖分算法是研究最多的，应用最广泛的一种方法，它可以生成满足约束条件的高质量的网格，并可以对整体网格或者局部网格进行细化处理。本文主要研究Delaunay网格剖分算法在三维区域内的网格剖分情况。
2、Delaunay三角网格剖分
2.1 算法概述
网格生成是指将计算区域（平面区域、三维区域或者空间曲面）分割为有限个单元区域，大多数的数值模拟计算方法和微分方程的数值解法都需要事先构造一个高质量的网格，Delaunay三角剖分是一种比较常用的网格剖分方法。剖分开的一块块碎片要求满足下面的条件：（1）每块碎片都是一个三角形，在三维区域内，每个单元区域都是一个四面体；（2）面上任何两个这样的三角形，要么不相交，要么恰好相交于一条公共边且不能同时交两条或者两条以上的边。在三维区域内，每个四面体单元要么不相交，要么恰好相交有一个公共的面，且不能同时交两个或者两个以上的面。
该算法包含以下步骤：（1）准备工作：输入生成网格的约束条件，以及需要进行网格剖分处理的三维实体模型，生成边界节点和在实体模型内部插入内部节点；（2）初始网格生成：对边界多边形进三角划分，生成仅包含边界点和内部点的初始网格；（3）网格细化：采用Delaunay优化平分方法在初始网格内部生成和插入新的节点，生成新的更密集的网格。（4）网格优化：根据生成网格的形状因子，调整插入或者生成的节点，从而调整生成网格的形状，生成高质量的网格。
2.2、网格生成
连通区域边界可用简单多边形近似，根据网格密度离散该近似多边形，并做三角划分，得到一个包含所有边界节点和边界边的粗略初始网格。在后期的网格细化中，新的节点与单元均位于实体模型内部，不会生成域外节点或者域外单元，因而网格具有良好的几何相容性。细化阶段边界边保持不变，保证了网格边界的完整性，因此无需考虑边界恢复问题。
初始化好网格后，根据网格密度这一限制约束条件，也就是网格中节点之间的距离，将不满足这一约束条件的网格进行细化处理，生成内部节点，连接新的三角单元，同时还要考虑网格单元的形状质量。对网格的整体或者局部进行加密，使网格更符合有限元模拟计算的要求，从而使得求解更为精确。
网格细化可以采用最长边平分的方法。采用最长边平分方法对初始网格中一个尺寸过大的单元，找出该单元的最长边，连接最长边的中点与对顶点，共享该边的相邻单元同时被一分为二。该方法以三角形单元为基本检查单元，简单易实现，且细化的质量较好。如下图，选择一条最长边α，取该边的中点Q，连接中点与对顶点P，这样就插入了一个节点Q，生成一条边PQ，将网格进行细化。
2.3、网格质量评价
在进行网格剖分时，往往需要对三角形或者四面体的形状进行分析和调整，使三角形尽量是等边三角形，四面体尽量是正四面体，从而提高整个网格的质量。一般常用三角形的形状因子来描述三角形的质量，其定义为：α=2r/R，其中r、R分别是三角形的内切圆半径和外接圆半径，0≤α≤1，其值越大，表明三角形质量越好。在实际应用中常用以下式子来进行判断：α=（a+b+c）×（b+c-a）×（a+c-b）/abc，其中a、b、c为三角形的长度。如下图是一些常见三角形的形态：
因此，在实际应用中，根据生成的三角形网格，或者四面体网格的形状，调整插入的点的位置，从而调整三角形或者四面体的形状，生成高质量的网格。
3、三维实体造型中应用
下面以一个立方体为例子，给出生成网格的具体情况，以及细分网格的情况。最后给出根据约束条件（网格棱边长度最大值有限制）生成网格的实例。
从图中可以看出采用Delaunay三角网格剖分算法，根据约束条件可以自动生成网格，且保持边界的完整性，并能根据生成网格的质量调整网格，从而生成高质量的网格。
4、结束语
从文中可以看出，Delaunay三角剖分算法取得了良好的效果，且具有较强的自适应性，能对电磁场二维有限元数值模拟计算进行高质量的网格剖分，有利于生成高质量的有限元网格。
参考文献
（1） 徐磊，张强 基于SIFT特征提取与Delaunay三角网格剖分算法在图像匹配中的研究 [J].数字技术与应用 算法分析 2013，5（2）：153-155
（2） 陈中贵，曹娟，杨晨晖 构造最优的Delaunay三角剖分的拓扑优化方法[J].计算机辅助设计与图形学学报 2011，23（12）：1967-1974
（3） 陈进超，王绪本，熊鹏，闵刚 一种含约束条件的二维自适应三角剖分新算法[J].物探化探计算技术 2009，31（1）：74-77
（4） 王永会，吴刚 大量约束边条件下构建约束Delaunay三角网的研究[J].测绘科学 2009，34（supp1）：117-118
（5） 陈欣、熊岳山 复杂平面区域的三角网格生成算法[J].国防科技大学学报 2008，30（4）：94-97
关键词：三角剖分；网格生成；网格细分
Abstract： In the simulation analysis of the 3D finite element numerical， in order to carry out the numerical calculation for the calculation of continuous area， achieve the simulation results， we must first on the 3D mesh. Delaunay triangulation algorithm is an effective method to generate mesh. This paper introduces the Delaunay triangulation algorithm， and in the condition of mesh subdivision， finally the application of the algorithm in 3D solid modeling are given in this paper.
Keywords： triangulation，mesh generation，mesh subdivision
1、引言
网格生成是有限元模拟计算的先决条件，有限元计算的效率和精确度在很大程度上受生成的网格质量的影响。在进行电磁场有限元仿真计算时，首先需要创建三维实体模型，然后需要根据一些限定的约束条件生成网格，对于几何形状复杂的模型，要自动生成满足约束条件的，高质量的网格是一项极其困难的事情，而Delaunay三角网格剖分算法是研究最多的，应用最广泛的一种方法，它可以生成满足约束条件的高质量的网格，并可以对整体网格或者局部网格进行细化处理。本文主要研究Delaunay网格剖分算法在三维区域内的网格剖分情况。
2、Delaunay三角网格剖分
2.1 算法概述
网格生成是指将计算区域（平面区域、三维区域或者空间曲面）分割为有限个单元区域，大多数的数值模拟计算方法和微分方程的数值解法都需要事先构造一个高质量的网格，Delaunay三角剖分是一种比较常用的网格剖分方法。剖分开的一块块碎片要求满足下面的条件：（1）每块碎片都是一个三角形，在三维区域内，每个单元区域都是一个四面体；（2）面上任何两个这样的三角形，要么不相交，要么恰好相交于一条公共边且不能同时交两条或者两条以上的边。在三维区域内，每个四面体单元要么不相交，要么恰好相交有一个公共的面，且不能同时交两个或者两个以上的面。
该算法包含以下步骤：（1）准备工作：输入生成网格的约束条件，以及需要进行网格剖分处理的三维实体模型，生成边界节点和在实体模型内部插入内部节点；（2）初始网格生成：对边界多边形进三角划分，生成仅包含边界点和内部点的初始网格；（3）网格细化：采用Delaunay优化平分方法在初始网格内部生成和插入新的节点，生成新的更密集的网格。（4）网格优化：根据生成网格的形状因子，调整插入或者生成的节点，从而调整生成网格的形状，生成高质量的网格。
2.2、网格生成
连通区域边界可用简单多边形近似，根据网格密度离散该近似多边形，并做三角划分，得到一个包含所有边界节点和边界边的粗略初始网格。在后期的网格细化中，新的节点与单元均位于实体模型内部，不会生成域外节点或者域外单元，因而网格具有良好的几何相容性。细化阶段边界边保持不变，保证了网格边界的完整性，因此无需考虑边界恢复问题。
初始化好网格后，根据网格密度这一限制约束条件，也就是网格中节点之间的距离，将不满足这一约束条件的网格进行细化处理，生成内部节点，连接新的三角单元，同时还要考虑网格单元的形状质量。对网格的整体或者局部进行加密，使网格更符合有限元模拟计算的要求，从而使得求解更为精确。
网格细化可以采用最长边平分的方法。采用最长边平分方法对初始网格中一个尺寸过大的单元，找出该单元的最长边，连接最长边的中点与对顶点，共享该边的相邻单元同时被一分为二。该方法以三角形单元为基本检查单元，简单易实现，且细化的质量较好。如下图，选择一条最长边α，取该边的中点Q，连接中点与对顶点P，这样就插入了一个节点Q，生成一条边PQ，将网格进行细化。
2.3、网格质量评价
在进行网格剖分时，往往需要对三角形或者四面体的形状进行分析和调整，使三角形尽量是等边三角形，四面体尽量是正四面体，从而提高整个网格的质量。一般常用三角形的形状因子来描述三角形的质量，其定义为：α=2r/R，其中r、R分别是三角形的内切圆半径和外接圆半径，0≤α≤1，其值越大，表明三角形质量越好。在实际应用中常用以下式子来进行判断：α=（a+b+c）×（b+c-a）×（a+c-b）/abc，其中a、b、c为三角形的长度。如下图是一些常见三角形的形态：
因此，在实际应用中，根据生成的三角形网格，或者四面体网格的形状，调整插入的点的位置，从而调整三角形或者四面体的形状，生成高质量的网格。
3、三维实体造型中应用
下面以一个立方体为例子，给出生成网格的具体情况，以及细分网格的情况。最后给出根据约束条件（网格棱边长度最大值有限制）生成网格的实例。
从图中可以看出采用Delaunay三角网格剖分算法，根据约束条件可以自动生成网格，且保持边界的完整性，并能根据生成网格的质量调整网格，从而生成高质量的网格。
4、结束语
从文中可以看出，Delaunay三角剖分算法取得了良好的效果，且具有较强的自适应性，能对电磁场二维有限元数值模拟计算进行高质量的网格剖分，有利于生成高质量的有限元网格。
参考文献
（1） 徐磊，张强 基于SIFT特征提取与Delaunay三角网格剖分算法在图像匹配中的研究 [J].数字技术与应用 算法分析 2013，5（2）：153-155
（2） 陈中贵，曹娟，杨晨晖 构造最优的Delaunay三角剖分的拓扑优化方法[J].计算机辅助设计与图形学学报 2011，23（12）：1967-1974
（3） 陈进超，王绪本，熊鹏，闵刚 一种含约束条件的二维自适应三角剖分新算法[J].物探化探计算技术 2009，31（1）：74-77
（4） 王永会，吴刚 大量约束边条件下构建约束Delaunay三角网的研究[J].测绘科学 2009，34（supp1）：117-118
（5） 陈欣、熊岳山 复杂平面区域的三角网格生成算法[J].国防科技大学学报 2008，30（4）：94-97