【摘要】：在科學(xué)研究、工程計(jì)算、文化娛樂中,數(shù)字幾何數(shù)據(jù)扮演著越來越重要的角色。使用數(shù)學(xué)模型和算法來分析與處理數(shù)字幾何數(shù)據(jù)的過程稱作數(shù)字幾何處理。這是一個包含計(jì)算機(jī)科學(xué)、應(yīng)用數(shù)學(xué)和工程學(xué)等學(xué)科的交叉性研究課題。常見的研究內(nèi)容包括模型獲取、模型重建、網(wǎng)格生成、形狀分析與理解、映射計(jì)算和幾何建模等。我們的研究針對數(shù)字幾何處理中的兩個子課題：最優(yōu)映射計(jì)算和最優(yōu)網(wǎng)格生成。其中最優(yōu)映射計(jì)算是一個重要的課題,它是許多計(jì)算機(jī)圖形學(xué)應(yīng)用的核心,比如網(wǎng)格參數(shù)化、網(wǎng)格變形、網(wǎng)格質(zhì)量提高、六面體網(wǎng)格生成。最優(yōu)網(wǎng)格生成是網(wǎng)格數(shù)據(jù)處理的基石,比如在有限元方法,對各向異性網(wǎng)格和六面體網(wǎng)格有很強(qiáng)的需求,因?yàn)樗鼈兡塬@得比各向同性網(wǎng)格和四面體網(wǎng)格更好的計(jì)算精度。最優(yōu)映射計(jì)算可以作為網(wǎng)格生成的后處理技術(shù),用于提高網(wǎng)格的質(zhì)量。本文從優(yōu)化的角度設(shè)計(jì)了新穎的能量函數(shù)和優(yōu)化方法,將它們成功地應(yīng)用到了最優(yōu)網(wǎng)格映射計(jì)算、各向異性網(wǎng)格生成和多立方體結(jié)構(gòu)(PolyCube)自動生成這三個課題,具體如下：一個好的映射算法需要保證無翻轉(zhuǎn)、低形變和計(jì)算高效性�，F(xiàn)有的算法不能同時保證這些特性。本文設(shè)計(jì)了一個增強(qiáng)的形變最小化能量(Advanced Most-Isometric ParameterizationS, AMIPS),并使用非精確塊坐標(biāo)輪換下降算法(inexact Block Coordinate Descent, inexact BCD)來快速地計(jì)算無翻轉(zhuǎn)的最優(yōu)映射。AMIPS能量函數(shù)繼承了傳統(tǒng)的形變最小化能量(Most-Isometric ParameterizationS, MIPS)的保證無翻轉(zhuǎn)的性質(zhì),同時能控制最大的形變。inexact BCD優(yōu)化算法能避免優(yōu)化過程過早地陷入局部最小。結(jié)合AMIPS能量函數(shù)與inexact BCD優(yōu)化算法,本文提高了映射的計(jì)算效率和質(zhì)量。在網(wǎng)格參數(shù)化、二維三角形網(wǎng)格與三維四面體網(wǎng)格變形、二維與三維無網(wǎng)格變形、各向異性四面體和六面體網(wǎng)格質(zhì)量提高等應(yīng)用中充分體現(xiàn)了我們算法的優(yōu)越性。但是AMIPS算法同樣存在缺點(diǎn)：比如不能支持存在很多控制點(diǎn)的網(wǎng)格變形,而且對初始映射比較敏感。本文提出了一個組裝分離網(wǎng)格單元的方法來計(jì)算無翻轉(zhuǎn)的最優(yōu)映射。我們的方法接受任意的網(wǎng)格映射作為輸入,該輸入映射可以存在眾多翻轉(zhuǎn)的網(wǎng)格單元。我們首先將網(wǎng)格的所有網(wǎng)格單元分離,保持每個網(wǎng)格單元上的映射是低形變的,然后通過同時優(yōu)化形變和分離頂點(diǎn)之間的距離來計(jì)算無翻轉(zhuǎn)的最優(yōu)映射。由于使用了每個網(wǎng)格單元上的仿射變換作為優(yōu)化變量,我們可以通過求解一個無約束的非線性非凸優(yōu)化問題來得到最優(yōu)映射。同樣在平面網(wǎng)格參數(shù)化、網(wǎng)格變形等應(yīng)用中體現(xiàn)了我們算法的魯棒性和高效性。在幾何建模、物理模擬和機(jī)械工程等應(yīng)用中,各向異性網(wǎng)格是非常重要的。本文提出了局部凸函數(shù)三角化(Local Convex Triangulation, LCT)方法,用于生成高質(zhì)量的各向異性網(wǎng)格。輸入一個曲面,或者一個三維空間區(qū)域作為定義域,和在定義域上的已知黎曼度量場,我們將各向異性網(wǎng)格生成問題轉(zhuǎn)化為一個函數(shù)逼近問題。在每個網(wǎng)格單元上構(gòu)造局部凸函數(shù),它的Hessian矩陣局部上和輸入的黎曼度量一致。我，，們利用交替更新網(wǎng)格頂點(diǎn)位置和改變網(wǎng)格連接關(guān)系的策略來降低函數(shù)逼近誤差。我們的LCT方法推廣了最優(yōu)Dealunay三角化(Optimal Delaunay Triangulation, ODT),可以接受一般化的黎曼度量場作為輸入和適用于劇烈變化的黎曼度量場和存在尖銳特征的網(wǎng)格。從二維平面區(qū)域、三維空間區(qū)域和三維曲面上生成的各向異性網(wǎng)格來看,我們算法效率高,結(jié)果網(wǎng)格質(zhì)量高。在物理模擬和機(jī)械工程等應(yīng)用中,六面體網(wǎng)格往往比四面體網(wǎng)格有著較好的性質(zhì),比如更少的網(wǎng)格單元、更高的計(jì)算精度。本文通過高質(zhì)量多立方體(Poly-Cube)結(jié)構(gòu)來生成六面體網(wǎng)格。多立方體結(jié)構(gòu)要求網(wǎng)格的表面三角形的法向和X,Y,Z軸嚴(yán)格對齊。之前的算法不能同時保證無翻轉(zhuǎn)、低形變、奇異性可控和計(jì)算高效這四個性質(zhì)。本文使用inexact BCD算法來優(yōu)化表面法向光滑與對齊能量,用來驅(qū)動網(wǎng)格變形并自動地消除極限點(diǎn),以自動生成高質(zhì)量的多立方體結(jié)構(gòu)。我們引入光滑函數(shù)的核寬度來控制多立方體結(jié)構(gòu)的奇異性。inexact BCD算法的高效率使本文的自動化算法的效率遠(yuǎn)遠(yuǎn)高于現(xiàn)在最先進(jìn)的算法。從多立方體映射的形變和六而體網(wǎng)格牛成的結(jié)果來看,我們算法的質(zhì)量和效率相比于當(dāng)前最先進(jìn)的算法都有較大提升。
[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.
【學(xué)位授予單位】：中國科學(xué)技術(shù)大學(xué)
【學(xué)位級別】：博士
【學(xué)位授予年份】：2016
【分類號】：TP391.7

【相似文獻(xiàn)】

相關(guān)期刊論文 前10條

1 江雄心;萬平榮;;整體規(guī)劃技術(shù)在三維有限元網(wǎng)格生成中的應(yīng)用[J];鍛壓技術(shù);2006年06期

2 趙廣文;;數(shù)值網(wǎng)格生成方法[J];航空計(jì)算技術(shù);1992年03期

3 買買提明·艾尼,古麗巴哈爾·瓦哈甫;用局部阻尼波形法的自連貫網(wǎng)格生成法[J];計(jì)算機(jī)輔助設(shè)計(jì)與圖形學(xué)學(xué)報(bào);2005年06期

4 賈超;張樹壯;;支持裂紋擴(kuò)展的三維有限元網(wǎng)格生成算法[J];計(jì)算機(jī)工程與應(yīng)用;2006年31期

5 聶玉峰;常升;;基于節(jié)點(diǎn)的局部網(wǎng)格生成算法[J];計(jì)算力學(xué)學(xué)報(bào);2006年02期

6 孫春華;陳雪芳;姜左;Hagiwara Ichiro;;基于Gregory法的N邊域非自交結(jié)構(gòu)網(wǎng)格生成[J];計(jì)算機(jī)應(yīng)用;2007年12期

7 盧章平,趙泉;基于“邊折疊”的可逆累進(jìn)網(wǎng)格生成算法的研究[J];工程圖學(xué)學(xué)報(bào);2004年01期

8 蒙茂洲;;功能強(qiáng)大的網(wǎng)格生成軟件——TrueGrid[J];CAD/CAM與制造業(yè)信息化;2010年01期

9 陳蔚蔚;聶玉峰;張偉偉;王磊;;高質(zhì)量點(diǎn)集的快速局部網(wǎng)格生成算法[J];計(jì)算力學(xué)學(xué)報(bào);2012年05期

10 胡洋瑞;龍永春;周浩;張莉;吳開騰;;基于改進(jìn)陣面推進(jìn)法的三維網(wǎng)格生成算法研究[J];內(nèi)江師范學(xué)院學(xué)報(bào);2013年08期

相關(guān)會議論文 前10條

1 郭高娟;劉劍飛;;狹窄區(qū)域的邊界層網(wǎng)格生成[A];北京力學(xué)會第20屆學(xué)術(shù)年會論文集[C];2014年

2 陳建軍;鄭耀;;并行三維非結(jié)構(gòu)性網(wǎng)格生成[A];中國力學(xué)學(xué)會學(xué)術(shù)大會'2009論文摘要集[C];2009年

3 張艷英;蘇杰先;崔明根;;多維流場的貼體網(wǎng)格生成方法[A];第一屆全國流體動力及控制工程學(xué)術(shù)會議論文集[C];2000年

4 盧笙;葉友達(dá);;空天飛行器建模及計(jì)算網(wǎng)格生成[A];計(jì)算流體力學(xué)研究進(jìn)展——第十二屆全國計(jì)算流體力學(xué)會議論文集[C];2004年

5 梁義;陳建軍;陳立崗;鄭耀;;二維并行網(wǎng)格生成及劃分[A];慶祝中國力學(xué)學(xué)會成立50周年暨中國力學(xué)學(xué)會學(xué)術(shù)大會’2007論文摘要集（下）[C];2007年

6 劉周;周偉江;;適于粘性計(jì)算的自適應(yīng)笛卡爾網(wǎng)格生成[A];全國計(jì)算物理學(xué)會第六屆年會和學(xué)術(shù)交流會論文摘要集[C];2007年

7 洪方文;張志榮;韋喜忠;黃國富;;轉(zhuǎn)子+導(dǎo)管系統(tǒng)的網(wǎng)格生成研究[A];2008年船舶水動力學(xué)學(xué)術(shù)會議暨中國船舶學(xué)術(shù)界進(jìn)入ITTC30周年紀(jì)念會論文集[C];2008年

8 劉劍飛;;網(wǎng)格生成研究進(jìn)展[A];北京力學(xué)會第18屆學(xué)術(shù)年會論文集[C];2012年

9 韓旭里;劉新儒;包崇兵;;帶形狀控制參數(shù)的網(wǎng)格生成方法[A];中國計(jì)算機(jī)圖形學(xué)進(jìn)展2008--第七屆中國計(jì)算機(jī)圖形學(xué)大會論文集[C];2008年

10 肖涵山;陳作斌;劉剛;程克明;;基于STL文件的自適應(yīng)笛卡爾網(wǎng)格生成[A];計(jì)算流體力學(xué)研究進(jìn)展——第十二屆全國計(jì)算流體力學(xué)會議論文集[C];2004年

相關(guān)博士學(xué)位論文 前4條

1 傅孝明;最優(yōu)映射計(jì)算與網(wǎng)格生成[D];中國科學(xué)技術(shù)大學(xué);2016年

2 梁義;自適應(yīng)表面網(wǎng)格生成研究[D];浙江大學(xué);2009年

3 黃橙;用于邊界面法的三維體網(wǎng)格生成方法[D];湖南大學(xué);2014年

4 張沐陽;高質(zhì)量可控四邊網(wǎng)格生成技術(shù)[D];浙江大學(xué);2011年

相關(guān)碩士學(xué)位論文 前10條

1 高宇海;基于時域有限差分方法的網(wǎng)格生成新方法[D];國防科學(xué)技術(shù)大學(xué);2011年

2 曹建;適應(yīng)復(fù)雜外形粘性流動模擬的混合網(wǎng)格生成算法[D];浙江大學(xué);2013年

3 金雋;網(wǎng)格生成算法研究和軟件實(shí)現(xiàn)[D];復(fù)旦大學(xué);2008年

4 王敏;三維復(fù)雜形體表面網(wǎng)格生成方法研究[D];南京理工大學(xué);2005年

5 常升;基于節(jié)點(diǎn)的局部網(wǎng)格生成算法研究[D];西北工業(yè)大學(xué);2006年

6 褚江;非結(jié)構(gòu)動網(wǎng)格生成方法研究[D];南京理工大學(xué);2006年

7 韓宏偉;非結(jié)構(gòu)性網(wǎng)格生成及其后處理技術(shù)研究和實(shí)現(xiàn)[D];浙江大學(xué);2008年

8 張永華;葉輪機(jī)CFD網(wǎng)格生成[D];南京航空航天大學(xué);2007年

9 王彩玲;基于CAD三維表面網(wǎng)格生成與應(yīng)用[D];南京理工大學(xué);2004年

10 曾麗娟;面向自適應(yīng)參數(shù)曲面網(wǎng)格生成的非結(jié)構(gòu)單元尺寸場理論及算法[D];浙江大學(xué);2014年

本文編號：2307898