并行网格生成技术

并行网格生成技术分类基于以下三种网格生成技术：Delaunay网格前沿法，边细分法。并行网格生成将原始网格生成问题划分成N个子问题来求解。子问题的求解可分为以下三种形式：紧耦合，部分耦合，无耦合。并行网格生成中的难点在于1•维持并行算法的稳定性，使得并行算法的结果正确。2•代码重用：将原始算法移植为并行算法时不需要改动原始算法代码，并且能保证并行算法的正确性。基于Delaunay的方法空洞算法：Algorithm1(BW(城曲i,1・Input:MeshMoaninitialmeshandasetofnpointsfori=1,nComputethecavityofofthepointpiComputetheballBiofpointpi财+i—Mi-Ci+BiendfbrOutput:AnewmeshM=上述算法并行化后引发如下问题:

图(a)中两个空洞相交，使得产生的三角剖分边相交。图(b)中两个空洞共享一条边，使得最终产生的剖分可能不满足德劳内空圆准则。紧耦合算法:ParallelOptimisticDelaunayMeshingMethod(PODM)PODM算法对子网格划分没有要求，这个算法通过重新划分子网格边界来保证算法稳定性。如下图(a)所示，空洞扩展到子区域之外时，将通过子区域之间的通信来保证算法的正确性。因此，这个算法是紧耦合的，不具备代码重用性。图(a)是空洞扩展到子区域之外的情况。图(b)是并行插入时的同步时间图。无耦合算法:ParallelProjectiveDelaunayMeshing(PPDM)PPDM算法的基本思想是预先计算出Delaunay-admissible子区域边界。即，最终生成的Delaunay剖分将包括这个边界。

这样，每个子网格就可以完全独立的计算各自剖分。因此，这个算法是无耦合并且是可完全代码复用的。生成Delaunay-admissible子区域边界的基本思想如下：先生成三维点集的一个凸壳。首先用InertiaAxis分割法将凸壳用平面II分成两个近似相等的部分。然后搜索所有三角面(PQR)GR的部分。然后搜索所有三角面(PQR)GR3（如上图），使得存在一个空球，球心在平面II上，球面经过P,Q,R且球内不包含其它任何点。这样，这些三角面就构成了一个Delaunay-admissible边界。部分耦合算法:ParralelConstrainedDelaunayMeshing(PCDM)methodProcaucfIg ® ⑹何 ⑹ (/)基于前沿法的并行算法ParrallelAdvancingFrontTchnique(PAFT)■■■■Boundary CurrenlFront•OldFront■■■■Boundary CurrenlFront•OldFront图(a)并行网格生成fj丁……—于羊!rdi■ii.aiE-iiw_i>rr 1(jPAFT算法如下:While存在活动面(可扩展的边界)：对这些活动点构造一个八叉树维持包含活动点的八叉树，扩展活动边界。For(ISHFT=0;ISHFT