针对复杂边界表示模型的高效自适应笛卡尔网格生成方法

《Graphical Models》：Efficient adaptive Cartesian mesh generation for complex boundary representation models

笛卡尔网格生成方法通过自动划分网格提高复杂几何建模效率，研究提出直接处理CAD原始几何的框架，包含四步细化机制、层次化存储和高效交集检测。采用3D ADT树优化查询性能，结合曲率、邻近度、缓冲层和2:1邻域比准则实现自适应细化，测试显示复杂模型可达百万级单元/秒生成速度，并验证了该方法在流体模拟中的适用性。

　　随着高性能计算和数值模拟技术的不断进步，对复杂几何体进行网格生成的挑战日益突出。传统的贴体网格生成方法通常需要用户与计算机之间的大量交互以修复几何结构，并且频繁调整算法参数以生成满足计算需求的网格。因此，能够实现完全自动化的笛卡尔网格技术逐渐受到重视。笛卡尔网格由于其轴对齐的特性，可以直接生成非密封或“脏”几何体的网格，并支持基于几何或流动的自适应网格细化（AMR）。这种能力提高了复杂几何体问题的求解效率，降低了计算需求。然而，由于其非贴体（非共形）的特性，为了确保准确性和守恒性，必须使用特殊的算法来重建边界附近的物理量。常见的方法包括浸入边界法（IBM）和格子玻尔兹曼法（LBM）。

笛卡尔网格的生成和存储在数据结构方面有多种选择。其中，基于八叉树的数据结构因其简单的层次结构而受到青睐，每个节点代表一个网格单元，可以被细化为八个子节点。另一种基于莫顿编码技术的方法也得到了广泛研究，它利用哈希表或红黑树对八叉树节点进行索引。八叉树结构有助于实现多级和多网格策略，但其限制在于只能等距地分割单元，即在三个维度上均等划分。相比之下，各向异性细化允许在任意一个、两个或三个方向上进行单元划分，因此提供了更大的灵活性。然而，非结构化数据结构虽然对存储空间需求更高，但相较于八叉树结构，其额外的空间需求在存储未知数和几何信息时可以忽略不计。

在笛卡尔网格生成过程中，确定哪些单元与几何表面相交是实现基于几何的自适应网格细化的关键步骤。通常，模拟的初始输入几何体是使用边界表示法（BRep）的计算机辅助设计（CAD）模型，这些模型由非均匀有理B样条（NURBS）组成，用于表示连续表面。标准做法是将CAD模型转换为三角面片模型，再基于这些面片进行笛卡尔网格生成。然而，这种方法不仅依赖于外部软件，无法保证离散化表面的质量，还会在转换后丢失表面片信息，从而无法充分利用原始几何数据进行网格生成。

在存储表面三角形和检测三角形与单元相交的方法选择上，数据结构的选择和相交检测方法对性能有显著影响。如果表面三角形被线性存储，那么在确定单元与表面相交时，需要遍历所有三角形。为了减少不必要的计算，可以使用多个二叉搜索树来组织表面三角形，基于其空间位置进行存储。这种方法能够缩小搜索范围，提高相交检测的效率。其中，替代数字树（ADT）通过递归将区间分成两个等长的子区间，并在每个树层切换维度，从而存储多维数据。ADT不仅可以处理有限大小的对象，还可以处理点。在某些研究中，三角形的重心被用作ADT中的表示，而另一种方法则是将三角形的轴对齐包围盒（AABB）视为六维点，并将其插入ADT中。这种方法能够有效识别给定集合中与指定范围相交的对象。相比之下，K维树（KDT）本质上是一种平衡二叉树，通过选择中位数将数据集均分为左右子树，适用于管理异构对象集合。然而，KDT的构造成本相对较高。

在本文中，我们提出了一种改进的非结构化数据表示方法，以及一种基于二叉搜索树的分层相交检测方法，以及一种四步细化机制，以实现几何自适应和平滑的单元过渡。通过有机地结合这些主要创新，我们开发了一种全新的自适应笛卡尔网格生成器，能够直接处理由NURBS表示的CAD基本体和面片边界。本文第二部分提供了所提出的自适应笛卡尔网格生成方法的概述，详细描述了每个步骤在第三部分进行介绍。第四部分通过几个典型测试案例对所提出方法的性能进行了评估，展示了新细化策略的有效性和鲁棒性。最后，第五部分提供了结论。

在生成自适应笛卡尔网格的过程中，需要对初始网格单元进行分类，分为相交单元、内部单元和外部单元。为了提高自适应细化过程的效果，我们计算了每个三角形与其他表面的接近程度，以便在后续的单元细化过程中进行比较。随后，我们构建了一个高效的二叉搜索树，例如ADT或KDT，以快速识别与初始网格单元相交的所有三角形。为了进一步优化自适应细化过程，我们引入了缓冲层和遵循2:1的限制，即相邻单元的尺寸比不超过2:1，且相邻单元的细化层级差最多为1，从而进一步优化笛卡尔网格。

在细化过程中，选择哪些单元进行细化是关键。本文提出了一种四步机制，以确定需要细化的单元。首先，基于表面曲率和对感兴趣特征的接近度选择单元。此外，我们实施了缓冲层，并遵循2:1的限制，以进一步优化笛卡尔网格。通过这些步骤，我们能够实现高效且灵活的网格生成。其中，数据结构的更新、相交检测、细化标准和单元分类对网格生成性能有显著影响。这些关键方面将在以下段落中深入讨论。

在表面三角形的生成和接近度计算中，我们提出了一种基于NURBS表面的分割线方法，以实现高质量的三角形划分。这种方法在处理“脏”几何体时表现出良好的鲁棒性。随后，我们对每个三角形的AABB进行了计算，并根据这些AABB与初始网格单元的相交情况筛选出候选三角形。为了减少计算量，我们使用了分层存储方法，将相交的三角形存储在单元中，这样子单元只需与父单元中的三角形进行相交检测，从而显著提高相交检测的效率。

在细化标准方面，我们提出了一种四步机制，以确定哪些单元需要细化。第一步是基于曲率标准，选择曲率变化较大的单元进行细化。第二步是基于接近度标准，识别接近其他表面片的单元。第三步是缓冲层标准，以实现从相交单元向外逐步扩展的标记过程。第四步是遵循2:1的限制，以确保相邻单元的尺寸比不超过2:1。这些标准的结合使得网格生成过程既高效又精确。

在单元分类方面，我们采用了一种基于洪水填充算法的方法，将生成的网格单元划分为内部或外部单元。这种方法利用了洪水填充算法的基本原理，即一旦确定一个单元的类型，其所有未标记的相邻单元都被视为具有相同的类型。由于相交单元将空间划分为内部和外部区域，因此只需要选择一个种子点即可使用洪水填充算法确定整个区域内的所有单元。与传统的射线投射方法相比，这种方法在处理多个封闭区域时同样有效。

通过多个测试案例，我们验证了所提出方法的性能。所有测试均在单核AMD EPYC 7302处理器（3.0 GHz，64 GB内存）上进行，每种情况执行5次测试，并记录最小运行时间以减少系统进程干扰，确保测量结果的准确性。我们评估了所提出方法在不同几何体上的效率。在测试中，我们发现随着细化层级的增加，曲率变化较大的区域会持续细化，这表明所提出的曲率标准有效地识别了具有显著几何变化的区域。同时，引入缓冲层后，单元尺寸的过渡更加平滑。

在F6飞机模型的测试中，我们评估了接近度标准对网格生成的影响。F6模型由58个NURBS表面片组成，生成了72,076个三角形。由于飞机机身和机翼尾缘处特征尺寸差异较大，我们设置了最大单元尺寸为50，最小单元尺寸为0.5，表明尺寸变化范围为两个数量级。根据这些尺寸，初始网格被设置为包含32、16和14个点，计划进行最多7次细化。缓冲层参数被设置为1，表明默认情况下会生成一个缓冲层。测试结果表明，当应用接近度标准时，F6模型的单元数量显著增加，而没有应用接近度标准时，单元数量则相对较少。这表明，应用接近度标准能够更有效地捕捉几何特征，提高网格的适应性。

在伦敦桥模型的测试中，我们评估了六种不同的二叉搜索树在不同细化层级下的性能。伦敦桥模型具有复杂的表面结构，生成了295,501个表面三角形。测试结果表明，ADT_3D方法在所有测试案例中均表现出最佳的效率，而KDT_ROUND_6D和KDT_VARIANCE_6D方法则在高细化层级下表现较差。此外，ADT_3D方法不需要计算中位数和方差，因此在整体性能上优于其他方法。

在本文的最后部分，我们使用了10个来自ABC数据集的CAD模型，生成了自适应笛卡尔网格。这些模型包括自相交、非流形表面和开放边界。所提出的方法展示了其在复杂几何体上的鲁棒性和几何适应性。为了验证所提出方法在流体模拟中的适用性，我们使用了LBM方法对静止球体上的流体流动进行了模拟。球体直径为1单位，计算域的长度为18单位，宽度和高度均为10单位。流体的雷诺数（Re）为200，表明流动处于湍流状态。流体的密度为1 kg/m3，动态粘度为0.005 Pa·s。LBM模拟采用了D3Q27方案和累积碰撞模型。空间离散化使用了均匀单元大小为0.1单位的笛卡尔网格。在壁面附近应用了所提出的方法进行自适应细化，以提高分辨率，最细的网格分辨率达到了0.00625单位（经过4次细化和12层缓冲）。时间离散化设置为0.001秒的时间步长，模拟总时长为20秒。生成的网格和最终的稳定速度场如图19所示。对于比较分析，表6展示了在Re=200时的阻力系数和回流区长度与先前数值模拟和实验数据的对比。结果表明，所提出的自适应笛卡尔网格生成方法在流体模拟中具有良好的适用性。

综上所述，本文提出了一种高效的自适应笛卡尔网格生成方法，适用于复杂边界表示模型。通过多种输入参数，可以实现对网格生成过程的全面控制，适用于连续和离散的任意CAD基本体。非结构化数据管理的实现使得该方法具有高度的灵活性和鲁棒性。高效二叉搜索树和相交三角形的分层存储显著减少了相交检测所需的计算时间。基于曲率、接近度、缓冲层和邻接比例的四步细化机制被提出，以优化适合流体模拟的网格。典型测试案例的结果表明，结合相交三角形存储的三维ADT方法在效率上表现最佳。结果表明，整个网格生成过程可以达到每秒生成10?个单元的速度，显示出对几何形状和离散化三角形数量的最小敏感性。此外，本文的研究还关注于各向异性细化方向的选择，这有望显著减少粘性模拟所需的网格尺寸。未来的工作将进一步提升单元和面片存储的数据管理效率。