最優(yōu)映射計(jì)算和網(wǎng)格生成.pdf

1、在科學(xué)研究、工程計(jì)算、文化娛樂(lè)中，數(shù)字幾何數(shù)據(jù)扮演著越來(lái)越重要的角色。使用數(shù)學(xué)模型和算法來(lái)分析與處理數(shù)字幾何數(shù)據(jù)的過(guò)程稱(chēng)作數(shù)字幾何處理。這是一個(gè)包含計(jì)算機(jī)科學(xué)、應(yīng)用數(shù)學(xué)和工程學(xué)等學(xué)科的交叉性研究課題。常見(jiàn)的研究?jī)?nèi)容包括模型獲取、模型重建、網(wǎng)格生成、形狀分析與理解、映射計(jì)算和幾何建模等。我們的研究針對(duì)數(shù)字幾何處理中的兩個(gè)子課題:最優(yōu)映射計(jì)算和最優(yōu)網(wǎng)格生成。其中最優(yōu)映射計(jì)算是一個(gè)重要的課題，它是許多計(jì)算機(jī)圖形學(xué)應(yīng)用的核心，比如網(wǎng)格參數(shù)化、網(wǎng)

2、格變形、網(wǎng)格質(zhì)量提高、六面體網(wǎng)格生成。最優(yōu)網(wǎng)格生成是網(wǎng)格數(shù)據(jù)處理的基石，比如在有限元方法，對(duì)各向異性網(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)自動(dòng)生成這三個(gè)課題，具體如下:
　　一

3、個(gè)好的映射算法需要保證無(wú)翻轉(zhuǎn)、低形變和計(jì)算高效性?，F(xiàn)有的算法不能同時(shí)保證這些特性。本文設(shè)計(jì)了一個(gè)增強(qiáng)的形變最小化能量(Advanced Most-Isometric ParameterizationS，AMIPS)，并使用非精確塊坐標(biāo)輪換下降算法(inexactBlock Coordinate Descent，inexact BCD)來(lái)快速地計(jì)算無(wú)翻轉(zhuǎn)的最優(yōu)映射。AMIPS能量函數(shù)繼承了傳統(tǒng)的形變最小化能量(Most-Isometric

4、 ParameterizationS，MIPS)的保證無(wú)翻轉(zhuǎn)的性質(zhì)，同時(shí)能控制最大的形變。inexact BCD優(yōu)化算法能避免優(yōu)化過(guò)程過(guò)早地陷入局部最小。結(jié)合AMIPS能量函數(shù)與inexact BCD優(yōu)化算法，本文提高了映射的計(jì)算效率和質(zhì)量。在網(wǎng)格參數(shù)化、二維三角形網(wǎng)格與三維四面體網(wǎng)格變形、二維與三維無(wú)網(wǎng)格變形、各向異性四面體和六面體網(wǎng)格質(zhì)量提高等應(yīng)用中充分體現(xiàn)了我們算法的優(yōu)越性。
　　但是AMIPS算法同樣存在缺點(diǎn):比如不能支持

5、存在很多控制點(diǎn)的網(wǎng)格變形，而且對(duì)初始映射比較敏感。本文提出了一個(gè)組裝分離網(wǎng)格單元的方法來(lái)計(jì)算無(wú)翻轉(zhuǎn)的最優(yōu)映射。我們的方法接受任意的網(wǎng)格映射作為輸入，該輸入映射可以存在眾多翻轉(zhuǎn)的網(wǎng)格單元。我們首先將網(wǎng)格的所有網(wǎng)格單元分離，保持每個(gè)網(wǎng)格單元上的映射是低形變的，然后通過(guò)同時(shí)優(yōu)化形變和分離頂點(diǎn)之間的距離來(lái)計(jì)算無(wú)翻轉(zhuǎn)的最優(yōu)映射。由于使用了每個(gè)網(wǎng)格單元上的仿射變換作為優(yōu)化變量，我們可以通過(guò)求解一個(gè)無(wú)約束的非線(xiàn)性非凸優(yōu)化問(wèn)題來(lái)得到最優(yōu)映射。同樣在平面

6、網(wǎng)格參數(shù)化、網(wǎng)格變形等應(yīng)用中體現(xiàn)了我們算法的魯棒性和高效性。
　　在幾何建模、物理模擬和機(jī)械工程等應(yīng)用中，各向異性網(wǎng)格是菲常重要的。本文提出了局部凸函數(shù)三角化(Local Convex Triangulation，LCT)方法，用于生成高質(zhì)量的各向異性網(wǎng)格。輸入一個(gè)曲面，或者一個(gè)三維空間區(qū)域作為定義域，和在定義域上的已知黎曼度量場(chǎng)，我們將各向異性網(wǎng)格生成問(wèn)題轉(zhuǎn)化為一個(gè)函數(shù)逼近問(wèn)題。在每個(gè)網(wǎng)格單元上構(gòu)造局部凸函數(shù)，它的Hessian

7、矩陣局部上和輸入的黎曼度量一致。我們利用交替更新網(wǎng)格頂點(diǎn)位置和改變網(wǎng)格連接關(guān)系的策略來(lái)降低函數(shù)逼近誤差。我們的LCT方法推廣了最優(yōu)Dealunay三角化(OptimalDelaunay Triangulation，ODT)，可以接受一般化的黎曼度量場(chǎng)作為輸入和適用于劇烈變化的黎曼度量場(chǎng)和存在尖銳特征的網(wǎng)格。從二維平面區(qū)域、三維空間區(qū)域和三維曲面上生成的各向異性網(wǎng)格來(lái)看，我們算法效率高，結(jié)果網(wǎng)格質(zhì)量高。
　　在物理模擬和機(jī)械工程等應(yīng)

8、用中，六面體網(wǎng)格往往比四面體網(wǎng)格有著較好的性質(zhì)，比如更少的網(wǎng)格單元、更高的計(jì)算精度。本文通過(guò)高質(zhì)量多立方體(Poly-Cube)結(jié)構(gòu)來(lái)生成六面體網(wǎng)格。多立方體結(jié)構(gòu)要求網(wǎng)格的表面三角形的法向和X，Y，Z軸嚴(yán)格對(duì)齊。之前的算法不能同時(shí)保證無(wú)翻轉(zhuǎn)、低形變、奇異性可控和計(jì)算高效這四個(gè)性質(zhì)。本文使用inexactBCD算法來(lái)優(yōu)化表面法向光滑與對(duì)齊能量，用來(lái)驅(qū)動(dòng)網(wǎng)格變形并自動(dòng)地消除極限點(diǎn)，以自動(dòng)生成高質(zhì)量的多立方體結(jié)構(gòu)。我們引入光滑函數(shù)的核寬度來(lái)控