● 摘要
网格生成技术是科学数值计算的重要基础。Delaunay三角网格，因其具有一系列良好的性质，在数值计算中被广泛采用。但是，随着数值计算精度的不断提高，网格的生成规模也随之迅速增长，这些变化使传统的Delaunay三角化算法遇到新的挑战：一方面网格生成时间急剧增长；另一方面网格生成算法的不稳定性凸显出来。本文以课题组在限定Delaunay三角化生成算法的研究成果为基础，对大规模限定Delaunay三角化算法中遇到的问题进行了深入研究。
通过分析发现，当网格规模达到一定级别时，影响限定Delaunay三角化生成算法效率的主要瓶颈是：在“恢复限定条件在网格中存在”这一过程中，计算Voronoi边与限定条件交点的时间在总的生成时间中占相当大的比重。针对此问题，本文提出通过对限定条件建立空间索引的加速策略，分别引入八叉树和R树两种空间索引来加速求交算法，并设计了实验，对加速效果进行了对比、分析和验证。为了进一步提高效率，在引入空间索引的基础上，对原有的串行求交算法进行了基于GPU的并行改造，并利用Mapped Memory技术对算法进行了优化。
本文进一步分析了导致Delaunay三角化算法不稳定的主要因素，造成算法不稳定的主要原因是计算机截断误差以及由此带来的累积误差。针对这一问题，提出引入精确几何计算库的方案来提高算法的稳定性。在实际的生成算法中，分别引入了LEDA和Core两个精确计算库，使得限定Delaunay三角化生成算法的稳定性得到了提高。
为了提高计算几何算法的调试效率，本文还开发了基于MFC和OpenGL的可视化调试工具，这一基础工作使得计算几何算法中的几何元素能够在调试过程被实时可视化，极大地方便了算法调试，提高了调试效率。