笛卡尔网格下精确高效的壁面距离计算方法.pdf
《笛卡尔网格下精确高效的壁面距离计算方法.pdf》由会员分享,可在线阅读,更多相关《笛卡尔网格下精确高效的壁面距离计算方法.pdf(10页珍藏版)》请在咨信网上搜索。
1、对于笛卡尔网格方法,壁面距离是采用虚拟单元法精确处理物面边界的重要参数,同时也是网格自适应后制约流动计算效率的关键因素之一。针对现有壁面距离计算方法结果不精确、效率不高的问题,引入三角形参数化方法,将空间点到三角形物面离散网格的最小距离问题转换为约束条件下一维极值问题,仅需通过符号判断和少量加减乘运算,即可确定最小距离,计算精度和效率大幅提高;发展嵌套包围盒概念的 KDT(K-dimensionaltree)物面网格数据存储结构,优化 KDT 最近邻搜索算法中距物面较远数据点回溯过程,实现了最小距离对应的三角形的快速定位。运用球、导弹、DPW6 等三维几何构型对上述方法考核验证结果表明,计算得
2、到的壁面距离与解析值的误差在百万分之一以内,十亿量级网格规模下的单核计算效率接近已有文献中的并行计算效率。关键词:笛卡尔网格;壁面距离;计算效率;KDT;回溯方法中图分类号:V211.3文献标识码:Adoi:10.7638/kqdlxxb-2021.0359Accurate and efficient wall distance calculation method for Cartesian gridsMENGShuang1,2,ZHOUDan1,LIXueliang2,BILin2,3,*(1.Key Laboratory of Traffic Safety on Track(Centra
3、l South University),Ministry of Education,Changsha410075,China;2.State Key Laboratory of Aerodynamics,Mianyang621000,China;3.Computational Aerodynamics Institute of China Aerodynamics Research and Development Center,Mianyang621000,China)Abstract:ThewalldistanceofCartesiangridsisanessentialparameterf
4、ortheproperwalltreatmentusingghostcellsandisalsooneofthecriticalfactorsgoverningtheefficiencyoftheflowfieldsimulationaftermeshadaptation.Thispaperproposesatriangularparameterizationmethodthatconvertstheproblemofcomputingtheminimumdistancebetweenspatialpointsanddiscretizedtriangularmeshesonthesurface
5、intoaconstrainedone-dimensionalextremumproblem.Thissimplificationonlyrequiressymbolicjudgmentsandasmallnumberofaddition,subtraction and multiplication operations to obtain the minimal distance,yielding significantimprovementsintheaccuracyandefficiencycomparedtoexistingmethods.Meanwhile,aKDT(K-dimens
6、ionaltree)datastructurebasedonthenestedenclosingboxconceptisdevelopedtooptimizethebacktrackingofdatapointsfarfromthesurfaceintheKDTnearestneighborsearchalgorithm.Theapplicationofthismethodtothree-dimensional geometries such as spheres,missiles,and DPW6 demonstrates that the error between thecomputed
7、walldistanceandtheresolvedoneiswithinonemillionth.Moreover,thecomputationalcostsofusingasinglecoreforbillion-scalegridsarecomparabletothoseofparallelcomputationusingexistingmethods.Keywords:Cartesiangrid;walldistance;computationalefficiency;K-dimensionaltree;backtracking收稿日期:2021-11-08;修订日期:2022-03-
8、14;录用日期:2022-04-12;网络出版时间:2023-05-11基金项目:国家数值风洞工程(NNW2018-ZT1A02);中南大学研究生自主探索创新项目(206021722)作者简介:孟爽(1994),男,河南许昌人,博士研究生,研究方向:网格生成技术.E-mail:通信作者:毕林*,研究员,研究方向:转捩、湍流.E-mail:引用格式:孟爽,周丹,李雪亮,等.笛卡尔网格下精确高效的壁面距离计算方法J.空气动力学学报,2023,41(7):93101.MENGS,ZHOUD,LIXL,etal.Accurateandefficientwalldistancecalculationme
9、thodforCartesiangridsJ.ActaAerodynamicaSinica,2023,41(7):93101(inChinese).doi:10.7638/kqdlxxb-2021.0359第41卷第7期空气动力学学报Vol.41,No.72023年7月ACTA AERODYNAMICA SINICAJul.,2023符号说明符号说明G物面三角形单元集合NG中的元素个数i维度(本文指x、y、z三个维度)GiminGimax(,)几何的最小包围盒dKDT的深度u当前划分维(x,y,或z)Tcenter三角形中心KiminKimax(,)节点K对应的包围盒顶点KL节点K的左子节点K
10、R节点K的右子节点KLiminKLimax(,)节点K的左子节点对应的包围盒KRiminKRimax(,)节点K的右子节点对应的包围盒Kis节点K在第i维度上剖分面对应的值lmin最小距离Knearest最小距离对应的节点m剖分轴 0 引言笛卡尔网格可以不依赖物面网格直接生成,因具有自动化程度高、复杂外形适应性好、非定常/多尺度流动结构捕捉能力强等优势而广受关注1。壁面距离的精确高效计算对实现笛卡尔网格方法具有重要意义:一方面,由于笛卡尔网格的非贴体特性,通常采用虚拟单元法处理物面边界2-6,需要根据物面确定虚拟单元的壁面距离,寻找参考点并插值获得其物理量,壁面距离精确计算对虚拟单元物面处理精
11、准度有较大影响;另一方面,对于非定常流动或运动物体,笛卡尔网格会根据流场的变化或物体的运动进行自适应7-8,自适应后的网格壁面距离需重新计算,壁面距离计算效率成为制约流动计算效率的关键因素之一。目前,壁面距离的计算方式主要分为求解偏微分方程9-12和采用几何方法直接计算13-14两类。第一类方法,将最小距离转换为关于波传播问题的偏微分方程数值求解15,需要额外的计算花费,壁面距离计算精度受数值离散精度的影响,且对于复杂外形适应性较差。第二类方法是根据空间点与物面离散网格的几何关系计算壁面距离。通常为简单起见,在物面网格足够密的情况下,求解空间网格点的壁面距离时,一般采用空间点到物面网格中心的距
12、离代替最小距离。赵钟等16发现,这种近似距离会引起计算误差,不仅影响计算结果的精度,而且对计算稳定性造成影响。为提高计算精度,有学者发展了根据空间点关于物面网格所在平面投影点与物面网格的几何关系计算壁面距离的 3D 投影法16、通过坐标变换转化为二维问题的 2D 法17等,但这些方法涉及大量向量计算和关系判断,计算量较大。在几何方法求解壁面距离时,由于物面网格数目较大,计算效率的核心问题是如何快速定位到最短距离相关的物面网格,物面网格数据结构是关键。最常见的方法是将物面网格顺序存入数组,采用遍历法搜索物面点得到壁面距离。网格规模较小时,计算量尚在承受范围之内。但是对于三维复杂几何外形的流场计算
13、,物面网格数量可达到 O(105)O(106)量级,空间网格点可达到 O(108)O(109)量级,采用遍历法计算量达到 O(1013)O(1015)量级。此种规模的计算量对整个计算周期的影响是巨大的。Boger18提出采用 ADT(alternatingdigitaltree)二叉树数据结构存储物面网格,计算效率大幅提高,成为目前最常用的物面网格数据存储方式。但对于复杂外形,ADT 平衡性下降,计算效率仍然差强人意。郭中州等14采用 KDT(K-dimensionaltree)存储物面网格,解决了 ADT 平衡性问题,计算效率进一步提升,但对于离物面较远的空间点,在运用 KDT 最近邻搜索算
14、法时,超球面与分割面位置关系判断失准,需要反复回溯,计算量大。本文针对上述问题,引入三角形参数化方法,将空间点到三角形物面离散网格的最小距离问题转换为约束条件下一维极值问题;同时发展嵌套包围盒概念的 KDT 物面网格数据存储结构,优化 KDT 最近邻搜索算法中距物面较远数据点回溯过程,实现最小距离对应的三角形的快速定位。1 点到三角形最小距离精确算法T(s,t)=B+sE0+tE1(s,t)D=(s,t):s 0,t 0,s+t 1T(s,t)点到空间三角形最小距离的问题19可描述为点P 和三角形之间的最小距离,其中,B 为三角形的一个顶点,E0和 E1分别为此顶点对应的三角形两条边。点 P
15、和三角形内任一点距离的平方为椭圆函数:Q(s,t)=|T(s,t)P|2=as2+2bst+ct2+2ds+2et+f(1)(s,t)Da=E0E0b=E0E1c=E1E1d=E0(BP)e=E1(BP)f=(BP)(BP)其 中,。点 P 和三角形之间的关系如图 1 所示。94空气动力学学报第41卷Q(s,t)最小距离问题转换为在 D 内求连续可微函数的极值问题。令:Q=2(as+bt+d,bs+ct+e)(2)s=(becd)/(acb2)t=(bdae)/(acb2)Q=(0,0)(s,t)DT(s,t)Q=V0s+t=1当且时,有。如果,最小距离为点 P 到的距离;否则,最小距离出现在
16、 D 的边界上。为了找到正确的边界,采用三角形区域 D 将 s-t 平面划分为七个区域,如图 2 所示。其中区域对应三角形区域 D,表示 Q 对应的椭圆与相切。tst0s0Q=VV0Q=V0Q=011(s,t)图 2 用三角域D划分s-t平面以及不同等高线Fig.2 Partition of a s-t plane by triangle domain Dand distance contours(s,t)T(s,t)如果在区域,则与点 P 最近的点在三角形上。(s,t)s 0,1Q(s,t)s+t=1s0 0,1Q(s0,1s0)如果在区域,则与点 P 最近的点计算问题转换为在内等值线与直线
17、的接触问题(可能是相切,也可能是相交于两个端点),即寻找,使得达到极小值,这是个一维极值问题,仅需通过符号判断和少量加减乘运算即(s,t)可确定。在区域或区域时,处理方式与区域类似。(s,t)s 0,1Q(s,t)s+t=1s 0,1Q(s,t)s=0如果在区域,则与点 P 最近的点计算问题存在两种可能:1)在内等值线与直线的接触问题;2)在内等值线与直线的接触问题。如图 3 所示。ts101 Q Q图 3 以区域为中心的等高线与三角形接触的两种情况Fig.3 Two contour levels with centers in region touching the triangle在等值线
18、上的任何一点,Q 的方向均朝向椭圆内部。为简单起见,我们根据Q 沿顶点(0,1)的两条边的方向导数的符号进行判断:s+t=1(1,1)/2)Q(0,1)s+t=1s 0,11)对于边,顶点(0,1)处的方向导数为。如果值为负,最小值出现在边上。最小值的情形对应图 3 红色曲线,处理方式和在区域类似。s=0(0,1)Q(0,1)s=0(s,t)2)对 于 边,顶 点(0,1)处 的 方 向 导 数 为。如 果 值 为 负,最 小 值 出 现 在 边上。最小值的情形对应图 3 绿色曲线,处理方式和在区域类似。(s,t)(s,t)在区域或区域时,处理方式与在区域类似。stT(s,t)=B+sE0+t
19、E1 st求得 和 之后,将其带入即可得到点到三角形最小距离的交点,从而构建虚拟单元方法中的“镜像点”。此种方法将最小距离求解问题转换为一维极值问题,在计算距离时只在求 或时进行一次浮点除法,其他均为简单的符号判断或加减乘运算,相比于 3D 投影法16或 2D 法17,在保证计算精度的同时计算量相对较小。2 物面单元的存储 2.1 嵌套包围盒概念的 KDT 参数定义与文献 14 中只存储物面网格中心点不同,本文BT(s,t)PE0E1图 1 点P和三角形之间的关系Fig.1 The relationship between P and the triangle第7期孟爽等:笛卡尔网格下精确高效
20、的壁面距离计算方法95发展了基于嵌套包围盒概念的 KDT,不仅按逆时针顺序存储物面网格顶点信息(方便笛卡尔网格物面处理),还同时包含 KDT 节点对应所有物面网格的最小包围盒,KDT 节点从上到下形成嵌套包围盒形式。嵌套包围盒的引入保证 KDT 每个节点包含当前节点对应三角形的所有信息,且在最小距离查询时,仅需要通过与剖分面(剖分面的大小由包围盒确定)坐标对比,就可以快速排除与目标点距离大于当前最小距离的三角形,效率大幅提升。2.2 嵌套包围盒概念的 KDT 建立步骤步骤 1:在正式创建 KDT 之前,首先需要确定目标数据集 G 中三角形元素的数量 N。然后,需要根据这 N 个元素确定 G 的
21、最小包围盒,包围盒的两个顶点分为(Gimin,Gimax),其中i=1,2,3,其定义如图4 所示。zxyGimaxGimin图 4 几何外形包围盒Fig.4 Geometry bounding box步骤 2:创建一个空的 KDT 备用。步骤 3:若 N 为 1,则将此元素插入到当前 KDT的节点中去,同时,将此节点的左右子树均置空。步骤 4:若 N 为 2,则将第一个元素插入到当前KDT 的节点中去,同时规定第一维为划分维。此时,只有第二个元素尚未被插入到 KDT 中。将第二个元素中心点与第一个元素的中心点在第一维的值进行比较。若第二个元素大于第一个元素,则对当前节点的右子树进行步骤 3
22、的操作,同时当前节点的左子树置空;否则,对当前节点的左子树进行步骤 3 的操作,同时当前节点的右子树置空。此步骤中 d 加 1。步骤 5:若 N 大于 2,则首先确定划分维。为了保证 KDT 的平衡,划分维的确定是计算 N 个三角形的中心点 Tcenter在各个维度的方差,然后找出方差最大的维度即为划分维。然后将此 N 个元素中心点在方差最大的维度上按从小到大的顺序进行排序。将位于中间的元素插入到当前 KDT 的节点中去。小于此元素的将全部位于当前节点的左子树,大于此元素的将全部位于当前节点的右子树。对当前节点左子树和右子树的元素递归执行步骤 3 或步骤 4 或步骤 5,直至所有元素全部插入到
23、 KDT 中。值得注意的是,在向 KDT 中插入节点的同时,节点对应的包围盒也在进行同步划分。例如 KDT 根节点 对 应 的 包 围 盒 即 为 数 据 集 G 的 包 围 盒(Gimin,Gimax)。假设节点 K 对应的包围盒为(Kimin,Kimax),则K 的左子节点 KL 的包围盒(KLimin,KLimax)为:KLimin=Kimin,KLimax=Kimax,i,uKiu,i=u(3)K 的右子节点 KR 的包围盒(KRimin,KRimax)为:KRimin=Kimin,i,uKiu,i=u,KRimax=Kimax(4)由于节点包围盒表示此空间区域内所有三角形元素集合的最
24、小包围盒,而在进行空间区域剖分时的依据是三角形中心点确定的平面,所以节点包围盒与包围盒之间,剖分面与剖分面之间会存在相交的部分。这种相交只会出现在三维及以上的情况。2.3 创建 KDT 时间复杂度分析由于 KDT 是一个二叉树,所以对于给定的 N 个元素建成一个深度为 d 的最优 KDT 有:N=2d+2d1+20=(22d1)(5)d=log2(N+1)/2)Nlog2N则,这里的“”表示不小于其内部数值的最小整数。KDT 建立过程中需不断进行求中值和排序操作,且当树深为 d 时,不需对仅剩的一个元素进行求中值和排序等操作。对 N 个元素创建 KDT,时间复杂度为,这其中包括了求中值、排序以
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 笛卡尔 网格 精确 高效 距离 计算方法
1、咨信平台为文档C2C交易模式,即用户上传的文档直接被用户下载,收益归上传人(含作者)所有;本站仅是提供信息存储空间和展示预览,仅对用户上传内容的表现方式做保护处理,对上载内容不做任何修改或编辑。所展示的作品文档包括内容和图片全部来源于网络用户和作者上传投稿,我们不确定上传用户享有完全著作权,根据《信息网络传播权保护条例》,如果侵犯了您的版权、权益或隐私,请联系我们,核实后会尽快下架及时删除,并可随时和客服了解处理情况,尊重保护知识产权我们共同努力。
2、文档的总页数、文档格式和文档大小以系统显示为准(内容中显示的页数不一定正确),网站客服只以系统显示的页数、文件格式、文档大小作为仲裁依据,平台无法对文档的真实性、完整性、权威性、准确性、专业性及其观点立场做任何保证或承诺,下载前须认真查看,确认无误后再购买,务必慎重购买;若有违法违纪将进行移交司法处理,若涉侵权平台将进行基本处罚并下架。
3、本站所有内容均由用户上传,付费前请自行鉴别,如您付费,意味着您已接受本站规则且自行承担风险,本站不进行额外附加服务,虚拟产品一经售出概不退款(未进行购买下载可退充值款),文档一经付费(服务费)、不意味着购买了该文档的版权,仅供个人/单位学习、研究之用,不得用于商业用途,未经授权,严禁复制、发行、汇编、翻译或者网络传播等,侵权必究。
4、如你看到网页展示的文档有www.zixin.com.cn水印,是因预览和防盗链等技术需要对页面进行转换压缩成图而已,我们并不对上传的文档进行任何编辑或修改,文档下载后都不会有水印标识(原文档上传前个别存留的除外),下载后原文更清晰;试题试卷类文档,如果标题没有明确说明有答案则都视为没有答案,请知晓;PPT和DOC文档可被视为“模板”,允许上传人保留章节、目录结构的情况下删减部份的内容;PDF文档不管是原文档转换或图片扫描而得,本站不作要求视为允许,下载前自行私信或留言给上传者【自信****多点】。
5、本文档所展示的图片、画像、字体、音乐的版权可能需版权方额外授权,请谨慎使用;网站提供的党政主题相关内容(国旗、国徽、党徽--等)目的在于配合国家政策宣传,仅限个人学习分享使用,禁止用于任何广告和商用目的。
6、文档遇到问题,请及时私信或留言给本站上传会员【自信****多点】,需本站解决可联系【 微信客服】、【 QQ客服】,若有其他问题请点击或扫码反馈【 服务填表】;文档侵犯商业秘密、侵犯著作权、侵犯人身权等,请点击“【 版权申诉】”(推荐),意见反馈和侵权处理邮箱:1219186828@qq.com;也可以拔打客服电话:4008-655-100;投诉/维权电话:4009-655-100。