本发明涉及三维绕流，具体涉及一种自适应笛卡尔网格快速生成优化方法。
背景技术：
1、随着实际应用中物体结构复杂程度的提升,为降低计算流体力学数值模拟过程中网格生成部分的资源开销并缩短整体计算任务周期,减少人工干预,研究全自动,高效的笛卡尔网格生成算法具有重要意义。通常而言，笛卡尔网格的各向同性使得在相同的模拟精度下，笛卡尔网格的数量会明显高于贴体网格数目。而确定网格类型和壁面距离的计算过程涉及大量的数值计算，可以通过大规模并行技术来解决。但当几何外形很复杂、网格规模很大时，使用传统的遍历来实现的方法仍然会导致巨大的计算负担。对于内外单元的判断，已提出多种行之有效的方法，但仍然存在难以并行实现、计算量随网格规模增大剧增、特殊情况难以准确判断的问题。
2、目前三维绕流问题中存在很多复杂外形几何信息，面对这类复杂外形几何信息，尚未有有效的方法来快速生成适合浸入边界法的各向同性自适应笛卡尔网格。
3、专利公开号为cn116894282b的发明中公开了一种空间点集与多连通网格区域拓扑关系的识别方法及系统，该方法，通过辅助三角形的构造，对点集内元素与多连通网格区域的相对位置进行识别；以及，通过射线与辅助三角形最近交点进行属性分析。该发明解决了现有技术存在的可靠性低、鲁棒性差等问题。然而，该发明需要将网格区域分解至多个处理器，确定投影方向，将三维信息变成平面二维才能建树，采用射线法判断内外时需要经过n*m次判定，并且这些判定里包含了大量无用的相交判断，因此，该发明的空间点集与多连通网格区域拓扑关系的识别过程计算过程复杂，识别速度慢，难以将其应用在复杂外形几何信息的笛卡尔网格的快速生成上。
技术实现思路
1、本发明的目的是为了提供一种自适应笛卡尔网格快速生成优化方法，结合kd树的特点，提出了一种通过在kd中树进行物面距离查找来加速壁面计算和相交单元判断的算法，和一种通过在kd树中对投影点进行查找来加速内外单元判断的算法。同时，因投影方向的多种选择避免了传统射线法边穿过、拐点穿过导致重复计数的问题。本发明能够快速且自动化生成适合浸入边界法的各向同性自适应笛卡尔网格。
2、为实现上述技术目的，本发明采取的技术方案为：
3、一种自适应笛卡尔网格快速生成优化方法，所述快速生成优化方法包括以下步骤：
4、步骤1、基于三维绕流问题中存在的复杂外形几何信息，构建三维复杂外形物面几何模型stl文件；
5、步骤2、读取三维复杂外形物面几何模型stl文件中所有物面三角单元，同时得到每个三角单元三个维度的最大值和最小值，构建三维空间包围盒，使用三维空间包围盒建立kd树；
6、步骤3、将步骤1模型中的流场计算区域划分为等距笛卡尔网格，并作为几何自适应初始背景网格，即初始笛卡尔网格；
7、步骤4、将需要进行判断的笛卡尔网格单元，在kd树中进行距离查找，并使用基于分离轴理论的网格相交判定算法判断是否该笛卡尔网格单元与物面相交并对相交的笛卡尔网格单元进行标记并记录下相交三角形对应的序号，在查找结束时得到网格单元与物面的最近距离；
8、步骤5、在步骤4的基础上，对除去相交单元的笛卡尔网格，在kd树中进行点查找，并使用改进射线算法进行笛卡尔网格单元的内外判定，将不与物面三角单元相交的笛卡尔网格单元分类为完全处于物体内部的单元和完全处于流场中的单元；
9、步骤6、设立缓冲区，对包含相交单元在内的缓冲区进行各向同性加密；
10、步骤7、重复步骤4到步骤6进行网格加密并判断单元种类，重复加密次数与流场分辨率相关。
11、进一步地，步骤2中，kd树为k维的二叉树，其中的每一个节点都是k维的数据，数据结构包括{node-data，range，split，left，right，parent}；node-data表示数据集中的某个数据点，是k维矢量；range表示节点所代表的空间范围；split表示垂直于分割超平面的方向轴序号；left表示由位于节点分割超平面左子空间内所有数据点所构成的kd树；right表示由位于节点分割超平面右子空间内所有数据点所构成的kd树；parent表示父节点。
12、进一步地，步骤2中，使用三维空间包围盒建立kd树时，数据点为三角单元包围盒，分割的方向轴根据当前节点的层数按x, y, z轴顺序更新，建立过程包括以下步骤：
13、步骤21、初始化分割轴，选取x轴；
14、步骤22、得到数据集的空间范围，初始化节点的空间范围；
15、步骤23、确定节点，对当前数据按分割轴维度进行检索，找到中位数数据，并将其放入到当前节点上；
16、步骤24、在当前分割轴维度，所有小于中位数的值划分到左支中，所有大于等于中位数的值划分到右支中；
17、步骤25、根据左支和右支的数据，更新左支和右支的空间范围；
18、步骤26、更新左支和右支的分割轴，根据节点的层数，按x, y, z轴顺序更新；
19、步骤27、对左支的数据进行处理，确定左支的子节点；对右支的数据进行处理，确定右支的子节点。
20、进一步地，步骤4中，将需要进行判断的笛卡尔网格单元，在kd树中进行距离查找的过程包括以下步骤：
21、步骤41、针对要判断的笛卡尔网格单元，选取相应的物面三角单元；其中，初始的笛卡尔网格单元进行判断时，随机选取一物面三角单元；其余由加密产生的新的笛卡尔网格单元进行判断时，选取上一级的笛卡尔网格单元距离最近的物面三角单元knearest；
22、步骤42、计算要判断的笛卡尔网格单元到选取的物面三角单元的距离l；
23、步骤43、进入kd树开始查找；
24、步骤44、以网格单元中心坐标为原点，向x、y和z三个维度的正负两个方向均伸长l长度，做一笛卡尔网格单元包围盒；
25、步骤45、比较笛卡尔网格单元包围盒与当前节点存储的空间范围是否有重合，若没有重合区域，则停止向下查找，执行回溯操作；若有重合，则转入步骤46；
26、步骤46、比较l与h的大小，若l<h,则使用基于分离轴理论的网格相交判定算法判断是否笛卡尔网格单元与物面相交，h是一与网格尺寸有关的量,h=2h+maxh，其中h为当前笛卡尔网格单元尺寸，maxh为所有物面三角单元包围盒的最大尺寸；若判断为相交，将当前笛卡尔网格单元标记为相交单元；若当前节点不为叶子单元，则转入步骤47，向下进行前序查找；
27、步骤47、进入子树，计算笛卡尔网格单元与当前节点存储的物面三角单元的距离newh；若newh<l，则更新l和knearest；
28、步骤48、重复步骤44至步骤47直到kd树查找结束；
29、步骤49、得到笛卡尔网格单元与物面的最短距离l和对应的最近的物面三角单元knearest；若是相交单元，则查找结束时，当前笛卡尔网格单元标记为相交单元。
30、进一步地，需要进行判断的笛卡尔网格单元包括：初始笛卡尔网格单元、由相交单元加密产生的新的网格单元和由网格2:1平衡条件而产生的新的网格单元；
31、网格2:1平衡条件是指，相邻笛卡尔网格单元间边长之比不可大于2。
32、进一步地，在每一次加密操作后对全局网格进行平衡操作以产生新的网格单元，具体包括以下步骤：
33、对全局笛卡尔网格按边循环，对于不符合2:1平衡条件的网格，对边长大的一侧笛卡尔网格单元进行局部加密，直至符合2:1平衡条件，并对新生成的笛卡尔网格单元赋一标记。
34、进一步地，步骤5中，在步骤4的基础上，对除去相交单元的笛卡尔网格单元，在kd树中进行点查找，并使用改进射线算法进行网格内外判定的过程包括以下步骤：
35、步骤51、除去判断为相交单元的其余所有笛卡尔网格单元，得到新的需要判断的笛卡尔网格单元；
36、步骤52、选择投影方向，投影方向包括x,y,z轴正负方向共六个方向；
37、步骤53、将需要判断的笛卡尔网格单元的中心点o坐标向投影方向投影到流场边界，得到一个边界投影点o1和一个二维点o2；
38、步骤54、使用二维点o2在kd树中查找；查找过程包括：
39、步骤541、判断节点的空间范围在投影方向上是否包含二维点o2，若不包含，则停止向下查找转而进行回溯；若包含，则转入步骤542；
40、步骤542、继续判断节点存储的三角单元包围盒在投影方向上是否包含二维点o2，若包含，则转入步骤543，对该三角单元进行判断；
41、步骤543、连接中心点o和边界投影点o1做一线段，使用改进射线法判定线段是否穿过该三角单元，若穿过，判断线段是否从三角单元的边界或顶点穿过时，若是，转入步骤544，否则，线段与三角单元集合的相交次数加1；
42、步骤 544、更换投影方向为坐标轴正负方向中的其余方向，转入步骤53；
43、步骤 55、若当前节点不为叶子单元则进入子树，向下进行前序查找，转入步骤53，直至整个kd树查找结束；
44、步骤56、在kd树中查找结束后，若线段与三角单元集合的相交次数为偶数，则该笛卡尔网格单元处于物体外部，为流场单元；反之网格单元为内部单元。
45、与现有技术相比，本发明的有益效果如下：
46、本发明的目的是为了提供一种自适应笛卡尔网格快速生成优化方法，基于三维绕流问题中存在的几何信息，采用三角形组成的表面集合作为输入并生成三角单元包围盒来构建kd树。将笛卡尔网格单元在kd树中进行距离查找，并使用基于分离轴理论的网格相交判定算法判断是否与物面相交，同时查找结束得到物面距离，而后将需要判断内外的笛卡尔网格单元中点可选择的向不同方向流场边界投影作为参考点，在kd树中进行点查找，并连接中点和参考点使用改进射线算法进行内外判断；另外，采用基于单元的网格剖分方法对包含相交单元在内的缓冲区进行各向同性加密。因此，本发明可以快速且高效鲁棒地生成符合浸入边界方法和流场计算分辨率需要的自适应笛卡尔网格。
1.一种自适应笛卡尔网格快速生成优化方法，其特征在于，所述快速生成优化方法包括以下步骤：
2.根据权利要求1所述的自适应笛卡尔网格快速生成优化方法，其特征在于，步骤2中，kd树为k维的二叉树，其中的每一个节点都是k维的数据，数据结构包括{node-data，range，split，left，right，parent}；node-data表示数据集中的某个数据点，是k维矢量；range表示节点所代表的空间范围；split表示垂直于分割超平面的方向轴序号；left表示由位于节点分割超平面左子空间内所有数据点所构成的kd树；right表示由位于节点分割超平面右子空间内所有数据点所构成的kd树；parent表示父节点。
3.根据权利要求1所述的自适应笛卡尔网格快速生成优化方法，其特征在于，步骤2中，使用三维空间包围盒建立kd树时，数据点为三角单元包围盒，分割的方向轴根据当前节点的层数按x, y, z轴顺序更新，建立过程包括以下步骤：
4.根据权利要求1所述的自适应笛卡尔网格快速生成优化方法，其特征在于，步骤4中，将需要进行判断的笛卡尔网格单元，在kd树中进行距离查找的过程包括以下步骤：
5.根据权利要求1所述的自适应笛卡尔网格快速生成优化方法，其特征在于，需要进行判断的笛卡尔网格单元包括：初始笛卡尔网格单元、由相交单元加密产生的新的网格单元和由网格2:1平衡条件而产生的新的网格单元；
6.根据权利要求5所述的自适应笛卡尔网格快速生成优化方法，其特征在于，在每一次加密操作后对全局网格进行平衡操作以产生新的网格单元，具体包括以下步骤：
7.根据权利要求1所述的自适应笛卡尔网格快速生成优化方法，其特征在于，步骤5中，在步骤4的基础上，对除去相交单元的笛卡尔网格单元，在kd树中进行点查找，并使用改进射线算法进行网格内外判定的过程包括以下步骤：
