高性能非结构化四面体网格解耦并行生成算法

针对大规模科学计算领域非结构化网格生成问题,提出一种基于AFT-Delaunay方法的三维复杂域解耦并行四面体网格生成算法.该算法以待剖分三维域的闭合的表面三角形网格为输入,采用边界一致约束Delaunay剖分方法串行地生成较小规模的初始四面体网格;采用界面优先策略扩展三维AFT-Delaunay方法,以几何分界面为参考指引前沿推进方向,在分界面处生成一层由四面体单元构成的有厚度的"墙",递归、并行地将初始四面体网格分割成完全解耦的子区域;此时,各子区域均为不含内部节点的四面体网格,继续利用AFT-Delaunay方法解耦并行地生成各子区域内部四面体网格.算例结果表明,文中算法很好地解决了分界面处网格质量差的难题以及收敛性问题,具有较好的并行效率及几何适应性,可在PC平台全自动地完成108量级的非结构四面体网格生成.     

基于OpenMP的三维并行Delaunay网格生成算法及实现

针对大多数并行Delaunay网格生成算法无法充分利用多核共享内存结构的问题,在原有面向共享内存的二维并行算法基础上,根据三维问题的特点提出基于OpenMP的三维并行Delaunay网格生成算法。算法采用划分求解区域为方格的方法实现候选点集的划分和并行插点。使用OpenMP对算法进行实现,并利用多种实现技术避免线程间的同步等待,提升算法效率。实验结果表明,本文算法及所采用的实现技术可以在三维条件下快速生成大量网格单元,具有较高的并行效率,同时能够保证良好的网格质量。     

面向共享内存结构的并行Delaunay网格生成算法

针对目前大多数并行Delaunay网格生成算法对共享内存结构利用不充分,不能够利用超级计算机多层次体系结构优势的情况,提出了一种充分利用共享内存结构的基于算法并行模式的并行Delaunay网格生成算法。通过对候选点集进行高效划分来实现插点操作的并行,增大了一次选择之后进行并行插点的点集规模。使用OpenMP并行模型对所提出算法进行并行实现,并和串行开源软件Triangle进行了对比。实验结果表明算法能够将候选点集划分成互不冲突的子集进行并行处理,在保证网格质量的同时具有较好的并行效率。     

海量点云曲面增量拓扑重建

针对现有的曲面重建算法难以兼顾大规模采样数据的重建效率与重建曲面拓扑正确性的问题,提出一种基于局部Delaunay网格剖分的曲面增量重建算法.该算法采用波前扩展的策略,通过波前环的扩张、分裂、重叠面片的消除等步骤,将局部重建过程传播至每个样点的邻近区域,获得插值于采样点集的二维定向流形网格曲面,实现整个采样点集的增量拓扑重建;在曲面局部重建过程中,分别基于局部区域的Cocone算法与二维投影点集的Delaunay网格剖分方法重建曲面的尖锐区域与平坦区域,其中局部区域重建曲面网格的边界的正确性由区域之外的少量辅助样点保护.实验结果表明,文中算法具有较高的重建效率,适用于封闭和非封闭海量点云数据的重建;且在采样密度符合要求的情况下,重建的网格曲面与原表面拓扑同构.     

海量点云曲面增量拓扑重建EI北大核心CSCD

针对现有的曲面重建算法难以兼顾大规模采样数据的重建效率与重建曲面拓扑正确性的问题,提出一种基于局部Delaunay网格剖分的曲面增量重建算法.该算法采用波前扩展的策略,通过波前环的扩张、分裂、重叠面片的消除等步骤,将局部重建过程传播至每个样点的邻近区域,获得插值于采样点集的二维定向流形网格曲面,实现整个采样点集的增量拓扑重建;在曲面局部重建过程中,分别基于局部区域的Cocone算法与二维投影点集的Delaunay网格剖分方法重建曲面的尖锐区域与平坦区域,其中局部区域重建曲面网格的边界的正确性由区域之外的少量辅助样点保护.实验结果表明,文中算法具有较高的重建效率,适用于封闭和非封闭海量点云数据的重建;且在采样密度符合要求的情况下,重建的网格曲面与原表面拓扑同构.     

曲线约束Delaunay三角剖分及在地形构建中的应用

针对采用约束Delaunay三角剖分算法构建地形时如何确保地形数据中的曲线约束条件在剖分结果中存在的问题,提出提取能够反映地形自身几何特征的特征点的方法对约束曲线进行直线段逼近,并对允许逼近误差的取值给予分析和验证。实现了使用较少的点对约束曲线进行最大程度逼近;在解决约束直线段不在Delaunay三角剖分中的问题时,提出在原约束曲线上进行加特征点细分的方法;针对地形数据量大构网时间长的问题,改进Delaunay三角网格生成算法。实验结果表明算法能够确保约束曲线在网格中存在,提高了对原曲线的逼近程度且提高了运算效率。算法可以实现对复杂区域的正确处理。     

三维地质构造的三角形格架式网格生成方法

三维油气运聚模拟计算方法需要在构造模型的约束下生成三维地质格架式网格。针对这一需求对现有网格生成方法进行了分析对比,并在此基础上提出一套三角形格架式网格生成方法。该方法采用了限定Delaunay三角剖分技术生成基础的地质层面模型,同时提出协同剖分算法来解决地层面网格在公共交线处的几何拓扑一致性问题,并表明了算法的正确性,最后给出地质层面的剖分实例。实验结果表明了该方法在工程实践中的有效性。     

Delaunay四面体网格并行生成算法研究进展

纵观近20年国内外Delaunay四面体网格并行生成算法的发展,依据其并行框架分为区域分解模式和基于节点模式,其中区域分解模式根据通信复杂程度进一步分为耦合的和非耦合的;对典型算法中网格质量传承性、串行代码嵌入率、扩展性、负载平衡和容错性等性能进行分析,结合数值测试结果总结了各类模式算法的优缺点.最后,针对各类模式算法的特点探讨了Delaunay四面体网格并行生成技术的发展趋势.     

三维不规则三角网格的精确裁剪算法

给出了一种基于约束Delaunay三角剖分的三维不规则三角网格的精确裁剪算法。算法结合TIN数据的生成特点,首先将TIN投影到二维平面,然后利用约束Delaunay三角剖分把裁剪多边形的每条边嵌入三角网中,再利用边-三角形的拓扑关系删除裁剪多边形外部多余三角形,最后利用边-点的拓扑关系对裁剪多边形顶点高程进行插值,使生成裁剪后的TIN模型。对不同复杂程度的三维TIN模型进行裁剪实验,发现二维投影策略极大地提高了三维TIN裁剪效率。算法的程序实现简单,且符合工程需求。     

二维复杂限定Delaunay三角化算法

针对包括曲线边界和内部带有曲线限定条件的二维Delaunay三角化问题,提出了一种细化算法.首先给出了曲线段的逼近边定义,以保证限定曲线在网格中的存在;然后证明了该算法的收敛性和最终曲线的逼近边集合与原曲线的拓扑一致性,并且生成的网格符合Delaunay优化准则;最后给出了算法的应用实例,验证了其有效性.     

三维约束Delaunay三角化的实现

分析了约束Delaunay三角化中存在的边界一致性问题,给出了约束Delaunay三角化的理论依据,重点探讨了三维约束Delaunay三角化的可行性条件和范围,同时,给出了三维有限域约束Delaunay三角化的实现方法及其在石油地质勘探数据和机械零件方面的网格剖分实例.这种算法在复杂对象的科学计算和工程分析中发挥了重要作用.     

任意多介质区域变尺寸有限元网格自动剖分

以Bowyer／watson算法为基础，结合Lawson算法等对有限元网格进行Delaunay剖分，引入节点间距函数，在区域内通过布置约束点和边来控制特定位置网格的尺寸，并实现网格的尺寸均匀过渡．采用了多种优化技术对生成的网格进行优化。对Bowyer／Watson算法和Delaunay剖分的一些缺陷及问题作了探讨，并提出了相应的处理办法。编写的网格自动剖分软件具有良好。的可视化界面，其图形生成、显示及修改功能十分完善，极大地提高了有限元网格剖分的效率和准确性.     

基于Qi算法的Delaunay三角网逐点插入法

Delaunay三角网在很多领域都有着广泛的应用,快速高效地生成Delaunay三角网十分重要。逐点插入法是构建Delaunay三角网中使用最广泛的方法之一。本文深入研究了使用逐点插入法构建不带约束条件Delaunay三角网的过程。在使用该方法生成Delaunay三角网中建立结点拓扑关系这一影响构网效率的关键步骤中引入了Qi算法,简化了该方法生成Delaunay三角网的复杂度。然后在向Delaunay三角网内插入约束边的过程中,再次引入Qi算法,从而提高了构网的效率。为了验证上述模型,我们在Microsoft Visual Studio 2005开发环境下,以C#为开发工具,采用底层开发模式实现了改进的逐点插入法,实验证明引入Qi算法能够提高逐点插入法Delaunay三角网构建及插入约束边的效率。     

高效可靠的边界层网格分块层进生成算法

为了提高复杂3D外形的边界层网格生成速度,提出一种基于离散中轴面的前沿分块层进算法.以闭合的边界三角形网格作为输入,在内部生成只含边界点的约束Delaunay三角化背景网格,聚集所有四面体的外心构成离散的中轴面.根据边界面片离中轴面的距离,将边界面片分为2类:快速推进的开阔区域面片和逐层推进的狭窄区域面片.在IntelXeonX5650CPU的单核上对NASA通用研究模型的边界层网格剖分结果表明,该算法的剖分效率是传统层进法或膨胀法的10倍以上,且完成106量级边界面片的分块只用了若干秒.     

一种基于Delaunay背景图改进的网格变形方法

针对Delaunay网格变形方法中因计算网格点在背景网格中映射不够精细导致的大变形失效问题,提出了一种改进后的网格变形方法,旨在进一步提高大变形情形时变形后的网格质量。该方法将原始的Delaunay网格变形方法中的背景网格远场边界进行加密,增加了映射背景网格单元的数量,改善了计算网格在背景网格中的映射精细程度,从而提升了变形后网格的质量。通过一正方形网格变形基础算例和30P30N三段翼型流场网格变形算例分别进行了测试与验证,结果表明该改进方法可以在保证计算效率的前提下,显著提升大变形时变形后的网格质量。与原始的Delaunay网格变形方法相比较,改进后的网格变形方法变形能力较强,所生成网格质量较高。     

一种精度可控的CAD网格模型及轻量化算法的研究

针对现有三维CAD系统中,CAD网格模型显示精度固定,难以动态调整以及细分后网格数量过多等瓶颈问题,在原始模型基础上,结合CAD模型中边、面等几何与拓扑信息,提出了一种精度可控的三维CAD网格模型.根据该模型的结构特点,采用曲面内部插值与边界曲线插值相结合的轻量化分类细分算法来实现模型精度调整,并有效控制细分后的网格数量,可满足三维CAD系统对模型精度可控、减少网格数量的需要.     

带虚拟边约束的面部表情基生成方法

针对网格形变迁移算法在生成面部表情基时可能出现的模型表面穿透问题,本文提出一种带虚拟边约束的面部表情基生成算法.该算法基于一组模板表情基,可以为不同的对象目标生成个性化的人脸表情基.首先,算法依据顶点之间的距离信息检测出人脸模型中可能发生模型表面穿透的区域,在这些区域添加新的顶点连接关系,本文称为虚拟边;然后以这些虚拟边约束网格形变迁移算法,在生成表情基的同时防止模型发生表面穿透现象.在不同人脸模型上的实验结果表明,算法添加虚拟边的精度和效率优于手动操作以及之前提出的相关算法,并且虚拟边约束可以有效防止表情迁移过程中的模型穿透问题.最后,本文实验为不同的人脸网格生成了表情基,并应用生成的表情基进行表情迁移,实验结果验证了本文提出的带虚拟边约束的面部表情基生成方法的有效性.     

约束三角剖分在雨量等值线的应用

雨量等值线在水文、防汛领域应用广泛,Delaunay三角剖分具有空外接圆和最大的最小角度两个良好性质,对于非规则分布的离散点数据进行三角剖分内插是生成等值线的最常用的算法,但实际应用中往往都术是凸壳进行三角化,而是有限定边（或限定点）对三角剖分进行约束。该文在标准Delaunay三角剖分基础上,分析了逐点插入法的基本原理,基于此提出了一种解决有限定边的约束三角网格剖分生成等值线的方法,给出了限定边进行三角剖分的算法,同时对边界采用网格加密和邻域内插算子进行边界附件插值,提高等值线的边界拟合精度,并在雨量等值线生成中得到较好应用。     

约束数据域的Delaunay三角剖分算法研究及应用

研究了一种约束Delaunay三角网生成算法,它充分利用分治算法与生长算法的优点,对离散点、构网中实时生成的边及三角形采用分块进行网格索引,有效地减少了搜索目标点、边及三角形的时间,从而提高了构网速度,并将该算法用于地面模型的构建中,实现了地形三维可视化。     

一种快速的三维有限元网格生成方法

针对三维有限元网格的生成的速度较慢并且网格质量不高的问题,提出了一种基于约束波前法的三维有限元网格生成算法。算法的主要思想是用背景网格提高网格单元的可控性,避免网格单元生成时验证有效性的计算量,从而快速生成高质量的三维有限元网格。算法首先借助八叉树方法生成背景网格,其次利用背景网格的密度对模型表面进行三角剖分得到初始波前,然后依据背景网格的特征生成实体网格单元,最后对得到的结果进行优化。实验证明结合了八叉树和推进波前法的三维网格生成算法降低了波前法的时间复杂度,将其效率提高了20%,而且能得到更高质量的网格。