最优映射计算与网格生成

发布时间：2018-11-03 13:16

【摘要】：在科学研究、工程计算、文化娱乐中,数字几何数据扮演着越来越重要的角色。使用数学模型和算法来分析与处理数字几何数据的过程称作数字几何处理。这是一个包含计算机科学、应用数学和工程学等学科的交叉性研究课题。常见的研究内容包括模型获取、模型重建、网格生成、形状分析与理解、映射计算和几何建模等。我们的研究针对数字几何处理中的两个子课题：最优映射计算和最优网格生成。其中最优映射计算是一个重要的课题,它是许多计算机图形学应用的核心,比如网格参数化、网格变形、网格质量提高、六面体网格生成。最优网格生成是网格数据处理的基石,比如在有限元方法,对各向异性网格和六面体网格有很强的需求,因为它们能获得比各向同性网格和四面体网格更好的计算精度。最优映射计算可以作为网格生成的后处理技术,用于提高网格的质量。本文从优化的角度设计了新颖的能量函数和优化方法,将它们成功地应用到了最优网格映射计算、各向异性网格生成和多立方体结构(PolyCube)自动生成这三个课题,具体如下：一个好的映射算法需要保证无翻转、低形变和计算高效性。现有的算法不能同时保证这些特性。本文设计了一个增强的形变最小化能量(Advanced Most-Isometric ParameterizationS, AMIPS),并使用非精确块坐标轮换下降算法(inexact Block Coordinate Descent, inexact BCD)来快速地计算无翻转的最优映射。AMIPS能量函数继承了传统的形变最小化能量(Most-Isometric ParameterizationS, MIPS)的保证无翻转的性质,同时能控制最大的形变。inexact BCD优化算法能避免优化过程过早地陷入局部最小。结合AMIPS能量函数与inexact BCD优化算法,本文提高了映射的计算效率和质量。在网格参数化、二维三角形网格与三维四面体网格变形、二维与三维无网格变形、各向异性四面体和六面体网格质量提高等应用中充分体现了我们算法的优越性。但是AMIPS算法同样存在缺点：比如不能支持存在很多控制点的网格变形,而且对初始映射比较敏感。本文提出了一个组装分离网格单元的方法来计算无翻转的最优映射。我们的方法接受任意的网格映射作为输入,该输入映射可以存在众多翻转的网格单元。我们首先将网格的所有网格单元分离,保持每个网格单元上的映射是低形变的,然后通过同时优化形变和分离顶点之间的距离来计算无翻转的最优映射。由于使用了每个网格单元上的仿射变换作为优化变量,我们可以通过求解一个无约束的非线性非凸优化问题来得到最优映射。同样在平面网格参数化、网格变形等应用中体现了我们算法的鲁棒性和高效性。在几何建模、物理模拟和机械工程等应用中,各向异性网格是非常重要的。本文提出了局部凸函数三角化(Local Convex Triangulation, LCT)方法,用于生成高质量的各向异性网格。输入一个曲面,或者一个三维空间区域作为定义域,和在定义域上的已知黎曼度量场,我们将各向异性网格生成问题转化为一个函数逼近问题。在每个网格单元上构造局部凸函数,它的Hessian矩阵局部上和输入的黎曼度量一致。我，，们利用交替更新网格顶点位置和改变网格连接关系的策略来降低函数逼近误差。我们的LCT方法推广了最优Dealunay三角化(Optimal Delaunay Triangulation, ODT),可以接受一般化的黎曼度量场作为输入和适用于剧烈变化的黎曼度量场和存在尖锐特征的网格。从二维平面区域、三维空间区域和三维曲面上生成的各向异性网格来看,我们算法效率高,结果网格质量高。在物理模拟和机械工程等应用中,六面体网格往往比四面体网格有着较好的性质,比如更少的网格单元、更高的计算精度。本文通过高质量多立方体(Poly-Cube)结构来生成六面体网格。多立方体结构要求网格的表面三角形的法向和X,Y,Z轴严格对齐。之前的算法不能同时保证无翻转、低形变、奇异性可控和计算高效这四个性质。本文使用inexact BCD算法来优化表面法向光滑与对齐能量,用来驱动网格变形并自动地消除极限点,以自动生成高质量的多立方体结构。我们引入光滑函数的核宽度来控制多立方体结构的奇异性。inexact BCD算法的高效率使本文的自动化算法的效率远远高于现在最先进的算法。从多立方体映射的形变和六而体网格牛成的结果来看,我们算法的质量和效率相比于当前最先进的算法都有较大提升。
[Abstract]:Digital geometry plays an increasingly important role in scientific research, engineering calculation and cultural entertainment. The process of using mathematical models and algorithms to analyze and process digital geometry data is called digital geometry processing. This is a cross-cutting research subject, including computer science, applied mathematics and engineering. Common research contents include model acquisition, model reconstruction, grid generation, shape analysis and understanding, mapping calculation and geometric modeling. Our research is directed to two sub-topics in digital geometry: optimal mapping calculation and optimal mesh generation. The optimal mapping calculation is an important task, and it is the core of many computer graphics applications, such as mesh parameterization, mesh deformation, mesh quality enhancement and hexahedral mesh generation. Optimal grid generation is the cornerstone of grid data processing, for example, in finite element method, it has strong demand for anisotropic mesh and hexahedral mesh, because they can obtain better calculation accuracy than isotropic grid and tetrahedron grid. Optimal mapping calculations can be used as post-processing techniques for grid generation to improve the quality of the grid. In this paper, a novel energy function and optimization method are designed from the viewpoint of optimization, and they are successfully applied to the optimal mesh mapping calculation, anisotropic mesh generation and multi-cubic structure (Polygon) to automatically generate these three topics, as follows: A good mapping algorithm needs to ensure no inversion, low deformation and high computational efficiency. existing algorithms do not guarantee these characteristics at the same time. In this paper, an enhanced deformation minimizing energy (AMIPS) is designed, and a non-accurate block coordinate rotation descent algorithm (inact BCD) is used to rapidly calculate the optimal mapping without inversion. The AMIPS energy function inherits the traditional deformation minimization energy (MIPS) to ensure the non-turning property, and also can control the maximum deformation. The inact BCD optimization algorithm avoids the optimization process to fall into local minimum prematurely. Combined with the AMIPS energy function and the inact BCD optimization algorithm, this paper improves the efficiency and quality of mapping. The advantages of our algorithm are fully reflected in the application of mesh parameterization, two-dimensional triangular mesh and three-dimensional tetrahedral mesh deformation, two-dimensional and three-dimensional non-mesh deformation, anisotropic tetrahedron and hexahedral mesh quality improvement. However, the AMPS algorithm also suffers from the disadvantage that, for example, there is no support for grid deformation with many control points and is sensitive to initial mapping. In this paper, a method of assembling and separating grid cells is presented to calculate the optimal mapping without inversion. our approach accepts arbitrary mesh mapping as input that may be present with numerous flip-grid cells. we first separate all grid cells of the grid, keep the mapping on each grid cell low, and then calculate the optimal mapping without inversion by simultaneously optimizing the distance between the deformation and the separation vertex. Since the affine transformation on each grid cell is used as the optimization variable, we can get the optimal mapping by solving an unconstrained nonlinear non-convex optimization problem. The robustness and efficiency of our algorithm are also embodied in the application of planar mesh parameterization, grid deformation and so on. Anisotropic grids are very important in geometric modeling, physical simulation and mechanical engineering. Local Contex Triangulation (LCT) method is proposed for the generation of high-quality anisotropic grids. An anisotropic mesh generation problem is transformed into a function approximation problem by entering a surface, or a three-dimensional space region as a domain, and a known Riemann metric field on the domain. A locally convex function is constructed on each mesh cell, whose Hessian matrix is locally coincident with the input Riemann metric. I use the strategy of alternately updating the grid vertex position and changing the mesh connection relationship to reduce the function approximation error. Our LCT method extends the optimal Dealunay Triangulation (ODT), and can accept generalized Riemann metric fields as inputs and grids suitable for sharp variations of the Riemann metric field and the presence of sharp features. From the two-dimensional plane region, the three-dimensional space region and the anisotropic grid generated on the three-dimensional curved surface, we have high algorithm efficiency and high grid quality. In applications such as physical simulation and mechanical engineering, hexahedral meshes tend to have better properties than tetrahedral grids, such as fewer grid cells and higher calculation accuracy. In this paper, a hexahedral mesh is generated by high quality multi-cube structure. The multi-cube structure requires strict alignment with the X, Y, and Z axes of the surface triangle of the grid. The previous algorithm can not guarantee the four properties of non-inversion, low deformation, singularity controllability and calculation. This paper uses the inact BCD algorithm to optimize the surface method to smooth and align energy, which is used to drive the deformation of the mesh and eliminate the limit points automatically, so as to automatically generate the high-quality multi-cube structure. We introduce the kernel width of smooth function to control the singularity of multi-cube structure. The high efficiency of the inact BCD algorithm makes the efficiency of this algorithm far higher than that of the most advanced algorithm. The quality and efficiency of our algorithm are greatly improved compared with the most advanced algorithms in terms of the deformation of multi-cubic mapping and the results of six-and-body grid cattle.
【学位授予单位】：中国科学技术大学
【学位级别】：博士
【学位授予年份】：2016
【分类号】：TP391.7

【相似文献】