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

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

2、格變形、網(wǎng)格質(zhì)量提高、六面體網(wǎng)格生成。最優(yōu)網(wǎng)格生成是網(wǎng)格數(shù)據(jù)處理的基石，比如在有限元方法，對各向異性網(wǎng)格和六面體網(wǎng)格有很強(qiáng)的需求，因為它們能獲得比各向同性網(wǎng)格和四面體網(wǎng)格更好的計算精度。最優(yōu)映射計算可以作為網(wǎng)格生成的后處理技術(shù)，用于提高網(wǎng)格的質(zhì)量。
　　本文從優(yōu)化的角度設(shè)計了新穎的能量函數(shù)和優(yōu)化方法，將它們成功地應(yīng)用到了最優(yōu)網(wǎng)格映射計算、各向異性網(wǎng)格生成和多立方體結(jié)構(gòu)(PolyCube)自動生成這三個課題，具體如下:
　　一

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

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

5、存在很多控制點的網(wǎng)格變形，而且對初始映射比較敏感。本文提出了一個組裝分離網(wǎng)格單元的方法來計算無翻轉(zhuǎn)的最優(yōu)映射。我們的方法接受任意的網(wǎng)格映射作為輸入，該輸入映射可以存在眾多翻轉(zhuǎn)的網(wǎng)格單元。我們首先將網(wǎng)格的所有網(wǎng)格單元分離，保持每個網(wǎng)格單元上的映射是低形變的，然后通過同時優(yōu)化形變和分離頂點之間的距離來計算無翻轉(zhuǎn)的最優(yōu)映射。由于使用了每個網(wǎng)格單元上的仿射變換作為優(yōu)化變量，我們可以通過求解一個無約束的非線性非凸優(yōu)化問題來得到最優(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)格。輸入一個曲面，或者一個三維空間區(qū)域作為定義域，和在定義域上的已知黎曼度量場，我們將各向異性網(wǎng)格生成問題轉(zhuǎn)化為一個函數(shù)逼近問題。在每個網(wǎng)格單元上構(gòu)造局部凸函數(shù)，它的Hessian

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

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