基于STL文件的曲面网格优化与代数多层网格法研究

摘要

三维网格生成在科学与工程计算、逆向工程和几何造型等众多领域有着广泛的应用．曲面网格的质量是影响四面体网格质量的重要因素，为获得高质量的曲面网格一般需要进行网格优化处理．与平面网格优化不同，曲面网格优化更为复杂，它通常包括曲面网格特征线提取、曲面网格重分、曲面Delaunay和CVT网格的生成与优化等．现在虽然有许多相关的研究工作，但是还不太成熟，如还没有一种统一、有效的特征线提取方法；对于一般曲面网格，还没有一种普适的曲面Delaunay和CVT网格定义以及相应的网格生成算法等等．因此，如何利用基于STL文件的曲面网格特性，给出更有效、更健壮的特征线提取方法以及曲面Delaunay和CVT网格的生成算法是一项值得关注的研究工作．另外，曲面网格的质量还会影响四面体网格生成算法的复杂性，如一般需要进行边界还原等。
　　 因此，如何给出一种边界自动还原的四面体网格生成算法也是一项重要的研究工作。
　　 偏微分方程数值求解在科学工程计算与数值仿真中起着十分重要的作用，如何快速求解偏微分方程离散化系统是其中的瓶颈问题之一．代数多层网格(AMG)法是目前国际上求解偏微分方程离散化系统最有效的方法之一．四面体网格的质量与AMG法的效率密切相关，因此，针对四面体网格下的二阶椭圆边值问题离散化系统，设计高效AMG法(或基于AMG预条件子的KryIov子空间迭代法)是一项有意义的工作。
　　 本文针对上述问题进行了深入研究，获得了一批算法和理论结果，文章主要由以下四个部分组成：
　　 第一部分，比较系统地研究了基于STL文件的曲面网格特征线提取方法．首先，针对STL文件给出一种新的曲面网格快速重建算法；其次，针对由基本几何曲面所构成的组合曲面网格，提出一种建立基本几何曲面网格二面角阈值数据库的思想，给出了一种白适应获取特征线阈值的组合曲面网格特征线提取算法；然后，针对一般曲面网格，在基于特征线阈值的基础上，结合G1插值法、边长比值法、断点连接法，以及利用曲面网格分割的思想，给出了若干特征线提取算法。
　　 数值实验表明了新算法的有效性和健壮性，并且能获得更丰富的特征信息。
　　 第二部分，首先，针对已确定特征线的基于STL文件的曲面网格进行网格重分处理；然后，利用重分网格的特性，引入了新的更为简洁的曲面Delaunay和CVT网格的定义，并给出了相应的生成算法．数值实验表明，我们的新算法能够生成高质量的曲面CVT网格。
　　 第三部分，首先，利用曲面CVT网格，并结合已有的四面体网格生成技术，给出一种边界自动还原的四面体网格生成算法；接着，给出了一种四面体网格的并行生成算法，从而提高了生成四面体网格的效率。
　　 第四部分，首先，通过考察不同质量的四面体网格对AMG—PCG法的影响，发现新的高质量四面体网格能大幅度提高求解二阶椭圆边值问题的线性有限元方程的AMG—PCG法效率；接着，针对高次有限元方程，设计了一种基于辅助变分问题的新的并行AMG预条件子，并从理论上严格证明了该预条件子的条件数的一致有界性．数值实验验证了理论结果的正确性及相应预条件共轭梯度(PCG)法的高效性和健壮性。