【www.rjdtv.com--计算机网络论文】

　　三角形网格是数值模拟、计算机仿真和计算机图形学中常用的二维网格； 一方面， 三角网格拓扑连接非常灵活； 另一方面， Delaunay 三角剖分这一基础算法使得三角形网格易于生成和构造。 这就使得三角形网格的应用比较广泛， 如网格变形领域会更多地采用三角形网格[2]. 但是， 相比于三角形网格， 四边形网格具有更高的计算精度和计算效率； 而且四边形网格研究可作为六面体网格研究[3]的基础。 因此， 四边形网格正得到学术界越来越多的关注。 然而， 由于几何形状与拓扑连接的限制， 以及缺乏 Delaunay 三角剖分这样的基础算法支撑， 直接生成的四边形网格质量较差。 同时， 大量的工程实践以及数值分析也充分证明， 网格的质量直接影响到数值模拟和仿真的精度及效率， 因此进行网格后处理， 即网格优化是十分必要的[4-6].
　　
　　常用的网格质量优化方法大体分为2类： 一类是几何优化[7-10], 也称作修匀， 即不改变网格的拓扑连接关系， 只是通过移动或调整节点的位置来达到改善网格质量的目的。 Mesquite[11]就是一个网格几何优化的开源库， 其包含了几乎所有的几何优化算法。 另一类是拓扑优化[12-18], 它通过改变节点之间的连接方式来提高网格质量。 本文重点关注四边形网格的拓扑优化。 节点之间连接方式可以用“度”表达， “度”定义为包含该节点的单元的数目。 对于四边形网格而言， 内部节点度的最优值为 4, 边界节点度的最优值与外围度有关。 设边界节点的外角为a , 则其外围度outern 定义为最接近 的整数； 边界节点度的最优值为outer4- n . 度为最优值的节点称为规则点， 反之称为不规则点。 一般而言， 规则点附近的单元质量较好。 在本文中，拓扑优化的目标是减少不规则点的数量。
　　
　　目前学术界已有很多关于四边形网格拓扑优化的研究工作[12-18], 但是从消除不规则点的角度来做拓扑优化的工作不多。 相关的工作总结如下。
　　
　　Canann 等[16]提出一种基于清理操作的拓扑修改方法， 目前流行的商业有限元软件 ANSYS 就是采用这种方法优化四边形网格。 这种方法虽然效率高、易于实现， 但是只能处理有限的区域和较少的网格构型， 所以效果有限。 ANSYS 生成后的网格依然有大量不规则点， 如第 4 节的算例所示。
　　
　　Bunin[15]提出了另一种方法： 首先找到问题点，接着搜索到其邻域以及边界多边形， 然后用一种特殊方式剖分边界多边形， 如果得到的网格质量优于原始网格则用其替代原始网格。 由于它是一种纯拓扑的方法， 几何信息难免会丢失， 从而生成一些反转单元； 并且， 它只能处理逻辑边数为 3, 4,5 的邻域， 适用范围有限。
　　
　　Peng 等[12]提出了一系列连接性编辑操作， 理论上， 这些操作可以优化出完美的四边形网格。 但是其未实现自动化， 其核心操作需要用户参与绕过一些特征线， 以避免几何特征的破坏。
　　
　　针对上述不足， Liu 等[1]提出了基于小多边形重连（small polygon reconnection, SPR）的网格优化技术来解决四边形网格度优化的问题。 其主要思想是： 首先通过不规则点周围单元构造一个待重剖分的小多边形， 然后再利用 SPR 操作得到小多边形较好的连接方式， 并替换小多边形内原来的网格。 但是， 原来的SPR操作只能处理围绕不规则点的2层单元大小的多边形。 本文提出了一种加速策略， 利用它可以处理 4~5 层单元， 使得其消除不规则点的能力得到加强。 另外， 原来的SPR操作只能处理平面四边形网格， 本文将其拓展到可以处理曲面四边形网格。
　　
　　1 基于 SPR 的网格优化技术概述
　　
　　为了给读者一个总体印象， 本节先介绍用 SPR进行网格优化的基本框架和算法细节。
　　
　　基本思想前文已经提到过： 围绕每个不规则点构造一个多边形， 寻找剖分这个多边形最好的网格， 通过局部改善达到全局优化的目的。 图 1a[1]中有许多不规则点， 对每个点先找出2层邻接单元构成一个小多边形， 采用 SPR 操作寻找最好的连接方式（意味着不规则点最少）， 并替代图 1b[1]所示原有的连接方式。 所有的不规则点扫描完毕， 即完成一次网格拓扑优化； 接着用 Mesquite 修匀技术做几何优化， 再拓扑优化， 如此迭代， 直至收敛。基于 SPR 的网格优化技术流程见算法 1.
　　 　 　　
　　SPR 操作是基于 SPR 的网格优化技术中的基本操作， 它的目标是找到一个给定的多边形的最佳剖分， 其原理是搜索所有可行解得出最优解。 求单个的可行解时， 采用的是图2所示前沿推进方式。
　　
　　即从多边形上挖掉一个四边形， 形成一个较小的新多边形。 然后再从这个新的多边形上挖掉一个四边形， 直至剩下的区域为空， 就找到一个解。 若它好于已有的解， 则记录下来。可行解的整个搜索过程用递归方式来组织。 　　
　　理论上有 O（n!）个可行解， 其中 n 是多边形的节点数。 SPR 操作的算法复杂度很高， 其效率直接关系到基于SPR的网格优化的效率。 为此， 本文加入了2 类检测来剪枝： 1） 可行性检测。 四边形不能是凹的， 不能与多边形边界相交； 2） 不规则点数检测。
　　
　　搜索过程中， 会加入一个允许不规则点数（allowedirregular node number, AIN）的变量， AIN 定义为多边形所允许的不规则点数， 它的初始值为初始网格的不规则点数。 随着解越来越好， AIN 的值越来越小。 在构造一个解的过程中， 会持续计算当前的不规则点数。 如果当前的不规则点多于 AIN, 那么构造过程就终止。
　　
　　构造四边形时需要4个节点， 算法会先选取边界的一条边作为基本挖掘边， 然后从其余的边界节点或内部节点中选择另外 2 个点。 这 2 个点有很多种选择， 每种选择都需要进行尝试并比较。 当多边形较大节点很多时， 搜寻的规模会很大， 这一步就会特别费时。 为此， 原来的程序限定一个小多边形只能包含不规则点周围的2层单元， 从而保证多边形不会过大。 但是与此同时， 这个限定也限制了其消除不规则点的能力。 为了处理更大的多边形，如 3 层到 4 层单元构成的多边形， 需要加快求解速度。
　　
　　2 基于 SPR 的网格优化技术的加速策略

    通过对原来 SPR 算法运行过程的观察， 本文发现了一个有规律的现象， 将得到的最优解按照单元的产生顺序显示出来， 会发现每个单元基本都是从当前多边形前沿的最小角处割下的单元。
　　
　　这意味着， 在求解过程中， 新单元基本上是由当前前沿上最小角的2条边以及一个附加点构成的。 这个发现启发了本节的改进算法。
　　
　　算法改进前后的最大区别是， 改进后算法（见算法 3）将最小角的 2 条边作为基本挖掘边来形成新的四边形； 而改进前算法（见算法 2）只是以边界上的一条边作为挖掘边， 如图 3 所示。
　　 　　
　　选择了前沿中最小角的2条边后， 只需要再选择一个节点就可以构成一个四边形， 其算法复杂度是 O（n）； 接着再递归处理剩下的小多边形， 改进前算法选择 2 个点复杂度是 O（n2）。 显然改进后算法复杂度要小很多。 从算法2和算法3可以看出，改进后的算法比改进前的算法选取点对的搜索方式减少了一层循环， 所以更有效率。 正是由于效率的提高， 改进后的算法可以处理多至4层单元的多边形。 不过需要指出， 改进后的算法得到的是近似最优解， 改进前的算法的解理论上会更好。 　　
　　图4表示一个小多边形改善前后网格。 测试这个小算例的结果： 改进前算法运行时间为 301 ms,改进后算法运行时间为 44 ms. 可见， 改进后算法效率远高于改进前算法， 这个算例可以说明算法效率的提高。
　　　　
　　结合新旧2个算法， 改进后网格优化流程如下：
　　
　　围绕所有不规则点构造两层单元的邻域， 用初始SPR 操作优化； 然后再围绕所有剩余的不规则点构造 3~4 层单元的邻域， 并用改进后的 SPR 操作优化。 这样可以消除的不规则点明显增多， 从而优化网格的拓扑结构。
　　
　　3 由平面拓展到曲面
　　
　　初始基于 SPR 的网格优化技术只能处理平面四边形网格， 其中节点坐标都是二维的， 其适用范围有限， 显然是不能满足实际工程的需要。 为此，本文的第二项改进是将基于 SPR 的网格优化技术的处理范围由平面拓展至曲面， 改进内容主要有以下 4 点。
　　
　　3.1 计算几何相关算法的推广
　　
　　在二维平面几何中， 很多计算几何的计算，如三角函数、点积、叉积等， 只需要涉及两个坐标； 而推广到三维， 就涉及三个坐标， 自然复杂了很多。
　　
　　可行性检测中需要判断三个节点是按顺时针排布还是逆时针排布。 下面以此为例来说明。
　　
　　图 5 所示 3 个点 A, B 和 C, 如果视角在纸面上方， 那么它们是逆时针排布； 如果从纸面下方看，那么它们是顺时针排布。 如果是二维情况， 这就不存在问题， 因为默认是从纸面上方看。 而且三维情况下， 则不存在默认方向。 因此， 本文对此的处理是加入每个节点的法向来辅助判断。 如果 B 点的法向量是朝上的， 那么 3 个点就是逆时针排布； 否则，就是顺时针排布。
　　 　 　　
　　3.2 平面性控制
　　
　　对于曲面三角形网格而言， 3 个点本身在一个平面上， 所以平面性自然满足； 而四边形的平面性如果不加以控制， 得到的结果会严重偏离原模型。
　　
　　考虑到平面四边形的内角和是 360°， 本文定义四边形的平面性度量为 　　
　　为平面四边形。 如果一个单元的 P 值越接近 1, 说明这个单元的平面性越好。
　　
　　为了保证优化后的网格单元的平面性， 在重连过程中， 本文设定一个阈值， 如果新生成的单元的 P 值小于该阈值， 则放弃。
　　
　　3.3 特征边控制
　　
　　特征边定义为曲面网格的边界以及内部比较尖锐的边。 特征边对保持模型的形状起着尤为关键的作用。 如果特征边在重连过程中变形、消失，都会丢失特征， 或多或少影响模型的形状， 进而影响计算、模拟和绘制的质量。
　　
　　在重连前， 将二面角小于 120°的边设为特征边。 在可行性检测的判断中， 增加判断构造的四边形是否与特征边相交的检测， 从而保证特征边不被破坏。 通过这种检测保证曲面特征不会丢失。
　　
　　3.4 曲面网格修匀
　　
　　Mesquite 本身只能进行平面网格和解析曲面网格的修匀。 对于一般的曲面网格， Mesquite 不能处理。 Mesquite 留有名为 domain 的接口来表达原曲面， 并将其作为修匀的参考。 也就是说， 每次修匀后， 如果节点偏离 domain, 就会将该节点投影到其距离 domain 的最近点。 本文利用 Mesquite 留有的 domain 的接口， 将点在曲面上投影点的程序嵌入， 实现了任意点在任意曲面的投影这一算法，并将其嵌入 Mesquite, 实现了任意曲面网格的修匀。
　　
　　4 测试结果与分析
　　
　　为了验证改进算法的有效性， 本文选用了若干算例在 CPU 为 Intel Core i5-4590 3.3 GHz、内存为 16 GB 的平台上进行了测试。
　　
　　对于网格的拓扑连接关系， 节点度的分布情况是衡量其质量好坏的重要标准。 为此， 本文统计了网格中具有非规则度的节点数。 网格中非规则节点数越少， 则网格的拓扑连接关系越好。 为了测试改进算法的效率， 本文统计了基于 SPR 的网格优化技术的运行时间。
　　
　　为了衡量优化前后网格质量，采用度量网格的最差单元质量以及平均单元质量的公式[19]为
　　
　　其中，minq 为四边形单元的最小角。 这个指标的最大值为 1, 其标准也为 1, 也就是说应用它来评估四边形网格单元质量所得的结果越是靠近 1, 网格单元的质量也就越好。
　　
　　4.1 平面算例
　　
　　本文针对平面情况测试了算例 1 和算例 2: 其中算例 1 模型边界为一个矩形， 内部有 5 个孔洞；算例 2 为一个地图型模型。 图 6 中算例 1 和 2 的模型采用 ANSYS 剖分得到的初始网格， 初始网格已经利用 Canann 等[16]算法进行过优化； 对 2 个算例的测试结果比较如表 1 所示。 　　
　　从表 1 可以看出， SPR 消除了 ANSYS 网格的很多不规则点， 优化后的网格看上去更流畅。 这得益于本文的加速策略， 使得 SPR 能处理较大的多边形区域。 单元质量用式（1）计算， 改进后算法单元的最差质量以及平均质量均有所提升， 说明单元质量是可以保证的。 但也注意到， SPR 的运行时间的还是比较长。 由于 SPR 的操作对象是一个个的小区域， 在并行上易于实现， 因此可以通过并行技术来进一步提高效率， 这是本文下一步的工作。ANSYS 运行时间很短， 故未在表中列出。
　　
　　4.2 曲面算例
　　
　　本文分别用 ANSYS 和 2 种基于全局参数化的方法生成初始曲面网格。 首先是测试ANSYS算例，先用 ANSYS 生成初始网格， 然后再用基于 SPR 的网格优化技术来优化。 算例 3 是 ANSYS 剖分 2 个半圆柱面贯穿的模型生成的初始网格， 如图 7a 所示， 图 7b 是基于 SPR 的网格优化技术优化后的网格。 从表 2 中可以看出， 改进后算法不规则点大幅度减少， 平均单元质量也有提高。 直观上， 优化后网格也比优化前网格光顺很多。
　　
　　图形学领域常采用基于全局参数化的方法做重网格化生成四边形网格， 其在可靠性、自动化程度、可控性和网格质量方面都取得了较大的成功。
　　
　　网格中存在的不规则点又称奇异点， 关键位置上的不规则点是用来保证曲面的特征的， 不能消除。
　　
　　但是依然存在着一些不必要的不规则点。 本文选取了图形学领域的 2 个顶尖小组的工作做对比。
　　
　　算例 4 模型采用的是 Stanford Bunny, 如图 8所示。 图 8a 是 Liu 等[14]采用共轭梯度场指导、大量人工参与的参数化方法生成的四边形网格。 它已经是一个非常规则的网格， 不过， SPR 仍然能够对它做一些优化。 从表 2 可以看出， SPR 优化后网格不规则点数由 92 减为 90; 优化过的地方看上去也更漂亮一些， 单元质量略有提高。
　　
　　Bommes 等[20]使用 MIQ 方法剖分 fertility 模型生成的网格如图 9a 所示。 图 9b 展示了基于 SPR 的网格优化技术优化后的网格。 从图 9 中可以看到，一个度为3的不规则点和一个度为5的不规则点被消除了。 从表 2 中可以看出， 优化后不规则点数减少了 2, 单元质量基本保持不变。
　　
　　4.3 算例比较与分析
　　
　　从上面的算例可以看出， 不管是 ANSYS 网格还是基于全局参数化的方法生成的网格， 本文提出的技术均可以优化： 不仅能减少不规则点， 还能基本保证单元质量不变。
　　
　　观察优化后网格可以发现， 若2个不规则点相距较远（如距离大于 3 个单元层）， 那么 SPR 技术消除不了它们。 毕竟 SPR 技术还是一个局部处理技术。 Peng 等[12-13]的连接性编辑可以将不规则点赶到一起， 所以， SPR 技术可以结合 Peng 等的方法，进一步提高优化能力。
　　
　　另外还可以发现， 对于 ANSYS 生成的网格，基于 SPR 的网格优化技术优化幅度很大； 对于基于全局参数化方法生成的网格， SPR 技术优化幅度较小。 分析其中的原因， 主要有： ANSYS 生成的网格是本文操作 ANSYS 全自动生成的， 并未有人工参与； 基于参数方法生成的网格是从文献[14]和文献[20]附录中下载的， 在生成过程中一定有相当的人工参与， 如一些参数的调整。 因此后者生成的网格本身质量要好很多。 另一方面， 在采用的算例中， 基于全局参数化方法生成的网格都是很有较多特征的曲面， 这些特征本身也需要不规则点来保持； 而在 ANSYS 生成的网格中只有很少的不规则点起这个作用， 基于 SPR 的网格优化技术在有限元网格中应用更大。
　　
　　5 结 语
　　
　　本文重新改造了基于 SPR 的网格优化技术：提出了加速策略使之能够处理更大的多边形； 并将其拓展以适用于处理曲面四边形网格。 数值实验表明， 改进后算法在增强了消除平面网格不规则点的能力的同时，可以消除曲面网格中的不规则点； 尤其可以较大幅度地优化 ANSYS 生成的网格，从而使其在工程上具有更大的应用价值。 下一步的工作是通过GPU并行以及与Peng等[12-13]的工作结合，进一步提高基于 SPR 的网格优化技术的优化能力。
　　
　　参考文献（References）：
　　
　　[1] Liu J F, Sun S L, Chen Y Q. A new method of quality im-provement for quadrilateral mesh based on small polygon re-connection[J]. Acta Mechanica Sinica, 2012, 28（1）： 140-145
　　
　　[2] Lin Tianjun, Guan Zhenqun, Chang Jihai, et al. An efficientmethod for unstructured dynamic mesh deformation-vertex-ballspring smoothing[J]. Journal of Computer-Aided Design &Computer Graphics, 2013, 25（11）： 1651-1657（in Chinese）（林天军， 关振群， 昌继海， 等。 高效的非结构动网格变形方法--点球弹簧修匀法[J]. 计算机辅助设计与图形学学报，2013, 25（11）： 1651-1657）
　　
　　[3] Xiao Zhoufang, Chen Jianjun, Cao Jian, et al. Automatic hexa-hedral mesh generation algorithm for many-to-many sweepvolumes[J]. Journal of Computer-Aided Design & ComputerGraphics, 2012, 24（8）： 989-996（in Chinese）（肖周芳， 陈建军， 曹 建， 等。 多源多目标扫掠体的全六面体网格自动生成算法[J]. 计算机辅助设计与图形学学报，2012, 24（8）： 989-996）
　　
　　[4] Huang Jin, Jiang Tengfei, Bao Hujun. Research progress onautomatic quadrilateral and hexahedral remeshing[J]. Journal ofComputer-Aided Design & Computer Graphics, 2015, 27（8）：1354-1362（in Chinese）（黄 劲， 江腾飞， 鲍虎军。 四边形与六面体自动重网格化技术研究综述[J]. 计算机辅助设计与图形学学报， 2015,27（8）： 1354-1362）
　　
　　[5] Guan Zhenqun, Song Chao, Gu Yuanxian, et al. Recent ad-vances of research on finite element mesh generation meth-ods[J]. Journal of Computer-Aided Design & Computer Graphics,2003, 15（1）： 1-14（in Chinese）（关振群， 宋 超， 顾元宪， 等。 有限元网格生成方法研究的新进展[J]. 计算机辅助设计与图形学学报， 2003, 15（1）： 1-14）
　　
　　[6] Yin Mengxiao, Xian Chuhua, Xiong Yunhui, et al. Properties ofhelical strips in quad mesh optimization[J]. Journal of Com-puter-Aided Design & Computer Graphics, 2014, 26（12）：2107-2114（in Chinese）（尹梦晓， 冼楚华， 熊 赟晖， 等。 四边形网格优化中的螺旋条带生成[J]. 计算机辅助设计与图形学学报， 2014, 26（12）：2107-2114）

本文来源：http://www.rjdtv.com/jisuanjilunwen/2136.html