Abstract: With the rapid development of computer graphics, industrial design, natural science and other fields, the demand for high-quality scientific computing methods is increased. These scientific computing methods are inseparable from high-quality grid generation algorithms. For the commonly used orthogonal grid generation algorithms, whether they can reduce the computational amount and whether the manual intervention can be reduced are still the main challenges faced by them. Aiming at these challenges, for the single-connected target region, an automatic generation algorithm of orthogonal grid was proposed based on Long Short-Term Memory network (LSTM), one of the recurrent neural networks and Schwarz-Christoffel conformal mapping (SC mapping). Firstly, the basic conditions of the Gridgen-c tool based on SC mapping were used to transform the grid generation problem into an integer programming problem with linear constraints. Next, a classifier, which is capable of calculating the probability of the corner type of each vertex of the target polygonal region, was obtained by using the pre-processed GADM dataset and LSTM training. This classifier was able to greatly reduce the time complexity of integer programming problem, making the problem be solved quickly and automatically. Finally, the simple graphics areas, animated graphics areas and geographical boundary areas were taken as examples to conduct a grid generation experiment. Results show that for simple graphic areas, the proposed algorithm can reach the optimal solution on all examples. For animated graphic areas and geographical boundary areas with complex boundaries, the example grid results show that the proposed algorithm can make the calculation amount in these target areas reduced by 88.42% and 91.16% respectively, and can automatically generate better orthogonal grid.

Key words: orthogonal grid generation, recurrent neural network, single connected region, automation, conformal mapping

摘要： 随着计算机图形学、工业设计、自然科学等领域的飞速发展，对高质量的科学计算方法的需求随之增大，而这些科学计算的方法离不开高质量的网格生成算法。对于常用的正交网格生成算法，是否能减少计算量以及是否能降低的人工干预等问题仍是它们所面临的主要挑战。针对这些挑战，对于单连通的目标区域，提出了基于循环神经网络之一的长短期记忆网络（LSTM）和Schwarz-Christoffel共形映射（SC映射）的正交网格自动化生成算法。首先，利用基于SC映射的Gridgen-c工具的基本条件将网格生成问题转换为一个带线性限制条件的整数规划问题。接着，利用预处理后的GADM数据集和LSTM训练获得能计算目标多边形区域每个顶点转角类型的概率的分类器。该分类器可以大幅度降低整数规划问题的时间复杂度，使该问题能被自动化且快速地求解。最后以简单图形区域、动画图形区域、地理边界区域为样例，进行网格生成实验。结果表明：对于简单图形区域，所提算法均能达到最优解；而对于具有复杂边界的动画图形区域和地理边界区域，实例网格结果表明，所提算法能使这些目标区域的计算量分别降低88.42%和91.16%，且能自动化地生成较好的正交网格。

关键词: 正交网格生成, 循环神经网络, 单连通区域, 自动化, 共形映射