论文部分内容阅读
在科学研究、工程计算、文化娱乐中，数字几何数据扮演着越来越重要的角色。使用数学模型和算法来分析与处理数字几何数据的过程称作数字几何处理。这是一个包含计算机科学、应用数学和工程学等学科的交叉性研究课题。常见的研究内容包括模型获取、模型重建、网格生成、形状分析与理解、映射计算和几何建模等。我们的研究针对数字几何处理中的两个子课题:最优映射计算和最优网格生成。其中最优映射计算是一个重要的课题，它是许多计算机图形学应用的核心，比如网格参数化、网格变形、网格质量提高、六面体网格生成。最优网格生成是网格数据处理的基石，比如在有限元方法，对各向异性网格和六面体网格有很强的需求，因为它们能获得比各向同性网格和四面体网格更好的计算精度。最优映射计算可以作为网格生成的后处理技术，用于提高网格的质量。 本文从优化的角度设计了新颖的能量函数和优化方法，将它们成功地应用到了最优网格映射计算、各向异性网格生成和多立方体结构(PolyCube)自动生成这三个课题，具体如下: 一个好的映射算法需要保证无翻转、低形变和计算高效性。现有的算法不能同时保证这些特性。本文设计了一个增强的形变最小化能量(Advanced Most-Isometric ParameterizationS，AMIPS)，并使用非精确块坐标轮换下降算法(inexactBlock Coordinate Descent，inexact BCD)来快速地计算无翻转的最优映射。AMIPS能量函数继承了传统的形变最小化能量(Most-Isometric ParameterizationS，MIPS)的保证无翻转的性质，同时能控制最大的形变。inexact BCD优化算法能避免优化过程过早地陷入局部最小。结合AMIPS能量函数与inexact BCD优化算法，本文提高了映射的计算效率和质量。在网格参数化、二维三角形网格与三维四面体网格变形、二维与三维无网格变形、各向异性四面体和六面体网格质量提高等应用中充分体现了我们算法的优越性。 但是AMIPS算法同样存在缺点:比如不能支持存在很多控制点的网格变形，而且对初始映射比较敏感。本文提出了一个组装分离网格单元的方法来计算无翻转的最优映射。我们的方法接受任意的网格映射作为输入，该输入映射可以存在众多翻转的网格单元。我们首先将网格的所有网格单元分离，保持每个网格单元上的映射是低形变的，然后通过同时优化形变和分离顶点之间的距离来计算无翻转的最优映射。由于使用了每个网格单元上的仿射变换作为优化变量，我们可以通过求解一个无约束的非线性非凸优化问题来得到最优映射。同样在平面网格参数化、网格变形等应用中体现了我们算法的鲁棒性和高效性。 在几何建模、物理模拟和机械工程等应用中，各向异性网格是菲常重要的。本文提出了局部凸函数三角化(Local Convex Triangulation，LCT)方法，用于生成高质量的各向异性网格。输入一个曲面，或者一个三维空间区域作为定义域，和在定义域上的已知黎曼度量场，我们将各向异性网格生成问题转化为一个函数逼近问题。在每个网格单元上构造局部凸函数，它的Hessian矩阵局部上和输入的黎曼度量一致。我们利用交替更新网格顶点位置和改变网格连接关系的策略来降低函数逼近误差。我们的LCT方法推广了最优Dealunay三角化(OptimalDelaunay Triangulation，ODT)，可以接受一般化的黎曼度量场作为输入和适用于剧烈变化的黎曼度量场和存在尖锐特征的网格。从二维平面区域、三维空间区域和三维曲面上生成的各向异性网格来看，我们算法效率高，结果网格质量高。 在物理模拟和机械工程等应用中，六面体网格往往比四面体网格有着较好的性质，比如更少的网格单元、更高的计算精度。本文通过高质量多立方体(Poly-Cube)结构来生成六面体网格。多立方体结构要求网格的表面三角形的法向和X，Y，Z轴严格对齐。之前的算法不能同时保证无翻转、低形变、奇异性可控和计算高效这四个性质。本文使用inexactBCD算法来优化表面法向光滑与对齐能量，用来驱动网格变形并自动地消除极限点，以自动生成高质量的多立方体结构。我们引入光滑函数的核宽度来控制多立方体结构的奇异性。inexact BCD算法的高效率使本文的自动化算法的效率远远高于现在最先进的算法。从多立方体映射的形变和六面体网格生成的结果来看，我们算法的质量和效率相比于当前最先进的算法都有较大提升。