基于逐点插入的delaunay四面体剖分并行算法研究

《基于逐点插入的delaunay四面体剖分并行算法研究》由会员上传分享，免费在线阅读，更多相关内容在学术论文-天天文库。

1、基于逐点插入的Delaunay四面体剖分并行算法研究Delaunay四而体剖分凭借生成网格的高质量性和良好逼近性，其并行网格生成技术备受业界关注。以逐点插入思想的Delaunay四面体网格剖分串行算法为基础，采用“网格生成串行算法+新并行策略”的方式，提出一种基于数据并行的Delaunay四面体剖分并行算法。同时在Limix+MPI平台上实现上述并行算法，取得了良好的计算效率。【关键词】Delaunay三角剖分网格生成并行算法并行策略1引言随着大型并行计算机软硬件技术的快速发展，网格剖分并行技术已成为科学工程计算领域研究的热点

2、之一。Delaunay三角剖分是三维空间数值模拟阶段最基本的逼近单元和3D复杂对象可视化处理屮最佳离散形式，剖分得到Delaunay三角网格具冇良好的数学特性与优化特性。基于逐点插入思想的Delaunay三角剖分，构成的网格唯一，性、网格质量都较好，并且满足Delaunay三角剖分的空圆准则，具有较高的执行效率。而基于逐点插入的Delaunay四面体剖分内部的并行，鍋合性是制约其并行效率的主要瓶颈，例如BW并行算法中插入点的冲突问题导致处理器之间较高的通信耗时，这是决定BW并行算法高低的主要因素。Yagawa等提出的自由网格法

3、(freemeshmethod.FMM),有效的规避了鍋合性的限制，充分利用网格的局部特性，适合大规模并行计算、负载均衡，不过局部网格生成的质量是决定剖分优劣的关键因素。地球物理勘探中，野外地层块实体断层之间耦合性很小（如图1所示地震层块体显示），并且可以通过野外放炮、检波一系列手段获取各个层面的数据点坐标，针对于此本文结合逐点插入算法和自由网格方法，提出了一种基于数据并行的Delaunay四面体剖分并行算法，此算法有效缩短了数据点同时插入时通信耗时，提高了网格剖分效率。2逐点插入Delaunay四面体剖分串行算法设计木文提出

4、的并行算法基于逐点插入算法，在此首先给出基于逐点插入的四血体剖分串行算法的具体实现过程。2.1数据结构定义三种数掘结构"Point〃结构、"Tetrahedral"结构、"Circumscribedsphere"结构，数据结构具体定义如下：2.1.1点Point三维情况下的数掘点川二维数组node[i]存储：记录第i个点的横坐标、纵坐标、竖坐标。2.1.2四面体Tetrahedral四面体信息存储在四面体信息矩阵中：tera_info[i],分别存储第i个四面体四个顶点编号和第i个四面体四个外邻四面体编号。2.1.3夕卜接球C

5、ircumscribedsphere三维Delaunay逐点插入算法在执行的过程中要不断搜索四面体外接球的信息，需要记录下外接球的圆心坐标与半径，用二维数组存储：tctra_circum[],存放第i个四面体外接球的球心横坐标、纵华标、竖绝标、四面体外接球半径。2.2算法流程图三维逐点插入Delaunay四面体剖分申行算法在木文中用于子块体网格剖分，具体实现过程如图2所示。3逐点插入Delaunay四面体剖分并行算法设计3.1并行算法基本思想首先对三维数据点限定在一个规则的长方体，然后将大块体分割为多个子块体，每一个子块体含有

6、上下两层数据点(相邻两个子块共享一层数据)，对每一子块体针对上下两层数据点采用三维逐点插入Delaunay剖分串行算法进行四面体网格生成。然后合并子块剖分之后得到的局部四面体网格，得到整体Delaunay四面体网格，如图3所示。3.2并行算法采用的并行策略将大块体按层分解为多个子块体，同时每一层数据点存储在一个数据文件屮，以下给出相关实现。MPICommrank(MPICO酮WORLD,&rank)；MPICommsize(MPICOMMWORLD,&size)；//为实现负载均衡，采用交叉数据分解方法for(inti=ran

7、k；i〈layer-1;i=i+proceSize)//layer是大块体被分成子块之后包含的总层数，proceSize启动的进程的总数量。{Delaunay_3d：:readdata(fileName[i]，node)；//fileName□中存储的是多个数据文件名称，一个数据文件储存一层三维点坐标信息。Delaunay_3d：:rcad_data(filcName[i+1],node)//读取第i与第i+1两相邻层数据，将数据点信息存储于二维数组node[][]中Delaunay_3d：:delaunay(node,nod

8、e_num_new,i+1);//包含i与i+1层数据的子块体采用前面给出的三维Delaunay四面体剖分串行算法进行网格剖分。}MPI_Finalize()；//?Y朿并行进程。3.3并行算法效率分析实验数据：如表所示，在野外采集七个层的仏86个三维点坐标信息，并按层将其存