微分網(wǎng)格處理技術(shù).pdf

1、自上個(gè)世紀(jì)八十年代以來(lái)，三維模型編輯領(lǐng)域發(fā)生了兩次大的技術(shù)突破。第一次突破發(fā)生在八十年代，稱之為自由變形(Free-formDeformation)技術(shù)，以操縱代理模型為手段來(lái)進(jìn)行模型編輯。第二次突破發(fā)生在九十年代，稱之為多分辨率編輯(Multi-resolutionEditing)技術(shù)，以操縱簡(jiǎn)化模型為手段來(lái)進(jìn)行網(wǎng)格編輯。這兩次技術(shù)突破為三維幾何建模提供了強(qiáng)大動(dòng)力，尤其是發(fā)展相當(dāng)成熟的自由變形技術(shù)已經(jīng)成為商業(yè)造型軟件不可或缺的組成部分

2、。 然而，隨著三維掃描技術(shù)的快速進(jìn)步，幾何模型的精度和數(shù)據(jù)復(fù)雜程度達(dá)到了新的高度，這些三維模型包含著十分豐富的幾何細(xì)節(jié)，在精確刻畫局部幾何特征的同時(shí)也為模型的編輯處理提出了新的挑戰(zhàn)——幾何細(xì)節(jié)在編輯過(guò)程中難以有效保持。針對(duì)具有豐富幾何細(xì)節(jié)的三維掃描數(shù)據(jù)，我們和國(guó)內(nèi)外其他同行一道，提出了新的幾何表示方法和計(jì)算模型來(lái)迎接挑戰(zhàn)，我們將這些算法統(tǒng)稱為微分域方法。比之于前兩次技術(shù)突破，微分域方法的優(yōu)勢(shì)主要體現(xiàn)在幾何編輯過(guò)程中細(xì)節(jié)特征的有效

3、保持方面，因此該技術(shù)特別適合于編輯三維掃描數(shù)據(jù)。目前，盡管微分域方法仍在進(jìn)一步的深化研究之中，但一些國(guó)外學(xué)者已經(jīng)將其視為三維模型編輯領(lǐng)域中的第三次技術(shù)突破，而本文的工作正是這次新突破中的主要組成部分之一。 不同于傳統(tǒng)方法，本文提出的微分網(wǎng)格處理技術(shù)不再將三維幾何模型視為歐氏空間中的連續(xù)或離散點(diǎn)集，而是將其視為定義在三維域網(wǎng)格上的標(biāo)量場(chǎng)。相應(yīng)地，幾何處理算法從空間點(diǎn)集或其控制點(diǎn)集的直接坐標(biāo)操縱轉(zhuǎn)化為間接的微分屬性操縱。我們承認(rèn)直接

4、操縱頂點(diǎn)的空間坐標(biāo)簡(jiǎn)單易行且具有幾何直觀性，但是與微分屬性相比，頂點(diǎn)坐標(biāo)缺乏刻畫局部幾何特征的能力。正是這一點(diǎn)導(dǎo)致了基于直接坐標(biāo)操縱的傳統(tǒng)編輯算法在編輯過(guò)程中難以做到幾何細(xì)節(jié)特征的有效保持，而保持幾何細(xì)節(jié)恰好是微分處理算法的優(yōu)勢(shì)所在。 我們的網(wǎng)格處理框架以離散流形上的泊松方程為理論基礎(chǔ)，將用戶編輯操作映射為對(duì)定義在域網(wǎng)格上的梯度場(chǎng)的操縱以及對(duì)邊界條件的修改，最終的編輯結(jié)果則通過(guò)泊松方程重建得到。之所以采用梯度場(chǎng)操縱加泊松重建的編

5、輯框架，主要基于如下的兩點(diǎn)考慮：其一，梯度作為微分屬性可以方便地進(jìn)行局部修改，而隨后的重建過(guò)程可使得局部的梯度修改產(chǎn)生全局的編輯效果，通常傳統(tǒng)方法要做到這一點(diǎn)需要進(jìn)行大量的人工交互。其二，由于基于最小二乘優(yōu)化的重建過(guò)程具有均勻分布逼近誤差的特點(diǎn)，使得梯度局部調(diào)整產(chǎn)生的瑕疵能被有效地?cái)U(kuò)散到整個(gè)幾何模型上，從而產(chǎn)生高質(zhì)量的處理結(jié)果。這兩點(diǎn)直接導(dǎo)致了微分網(wǎng)格處理技術(shù)能夠以較少的交互操作來(lái)產(chǎn)生高質(zhì)量的編輯結(jié)果。 在微分網(wǎng)格處理框架下，我

6、們給出了一系列具體的應(yīng)用算法，包括網(wǎng)格變形、網(wǎng)格融合、網(wǎng)格光順和網(wǎng)格形狀插值。這些算法的共性問(wèn)題是如何將用戶的編輯意圖有效地轉(zhuǎn)換成對(duì)梯度場(chǎng)的操縱以及對(duì)邊界條件的修改。與同類其它算法相比，這些應(yīng)用算法在編輯結(jié)果的質(zhì)量上都有著質(zhì)的提升。例如，在相同的用戶交互下，以三維掃描數(shù)據(jù)為編輯對(duì)象，采用我們提出的泊松網(wǎng)格變形算法和網(wǎng)格融合算法生成的編輯結(jié)果都要顯著優(yōu)于采用商業(yè)造型軟件MayaTM中的自由變形工具WIRE所生成的相應(yīng)結(jié)果，這一點(diǎn)已經(jīng)得到W

7、IRE工具的設(shè)計(jì)者KaranSingh的認(rèn)可。此外，采用泊松形狀插值算法生成的過(guò)渡序列由于能夠正確地表達(dá)模型之間的相對(duì)旋轉(zhuǎn)關(guān)系，因而可以顯著減少關(guān)鍵幀動(dòng)畫中所需要的關(guān)鍵幀的數(shù)量。 采用微分網(wǎng)格處理技術(shù)并不是無(wú)代價(jià)的，由于離散泊松方程實(shí)質(zhì)上是一個(gè)稀疏線性系統(tǒng)，其未知數(shù)個(gè)數(shù)與興趣區(qū)域的自由頂點(diǎn)個(gè)數(shù)成正比，所以泊松方程的數(shù)值求解成為整個(gè)框架的瓶頸問(wèn)題。為此，我們提出了由兩個(gè)層面組成的加速技術(shù)。其一，通過(guò)矩陣Cholesky分解，我們將

8、方程的系數(shù)矩陣進(jìn)行預(yù)先分解并將其存儲(chǔ)起來(lái)，這樣整個(gè)編輯過(guò)程只需要根據(jù)新的邊界條件進(jìn)行快速回代即可，該方案使得在目前的個(gè)人電腦上，可以交互編輯中等規(guī)模的幾何模型。其二，對(duì)于較大規(guī)模的幾何模型，直接求解計(jì)算代價(jià)過(guò)高乃至不可能完成(維數(shù)過(guò)高會(huì)導(dǎo)致內(nèi)存無(wú)法容下泊松方程)，因此，我們?cè)O(shè)計(jì)了一套累進(jìn)求解方法。該方法首先將原始模型進(jìn)行累進(jìn)簡(jiǎn)化至頂點(diǎn)個(gè)數(shù)滿足交互編輯的需求，簡(jiǎn)化過(guò)程中各個(gè)層次之間的幾何細(xì)節(jié)通過(guò)一套相似變換不變系數(shù)進(jìn)行編碼記錄。對(duì)于變形后

9、的物體，該技術(shù)可以通過(guò)求解一系列的局部泊松方程來(lái)完成整個(gè)重建過(guò)程，最后得到原始模型的編輯結(jié)果。 圖層概念的提出曾經(jīng)使得圖像處理軟件在系統(tǒng)設(shè)計(jì)上有了質(zhì)的飛躍，然而三維模型的數(shù)據(jù)特點(diǎn)使得現(xiàn)有的網(wǎng)格編輯系統(tǒng)難以引入層模型。我們?cè)诰庉嫾夹g(shù)上取得的新突破，使得重新設(shè)計(jì)網(wǎng)格編輯系統(tǒng)的架構(gòu)成為可能?；谖⒎直硎痉椒ǎ覀兲岢隽艘粋€(gè)新的以“幾何層”為核心的網(wǎng)格表示和編輯系統(tǒng)，該系統(tǒng)借鑒了圖像處理軟件中的“圖層”模型，為編輯操作提供了新的空間維度

10、。相應(yīng)地，我們給出了網(wǎng)格模型的幾何層表示、分解、屬性操縱和合成方法，使得復(fù)雜的編輯任務(wù)能夠分解成為一系列獨(dú)立的分層操作，從而增加了系統(tǒng)的靈活性，提高了編輯效率。 最后，我們簡(jiǎn)要列出本文的主要貢獻(xiàn)：·三維網(wǎng)格的微分表示方法以及基于該表示方法的通用幾何處理算法框架?！せ谔荻葓?chǎng)操縱和泊松重建的微分網(wǎng)格處理算法，具體包括網(wǎng)格變形、網(wǎng)格融合、網(wǎng)格光順和網(wǎng)格形狀插值算法。 ·適用于巨型幾何模型處理的泊松方程累進(jìn)求解技術(shù)，其核心是具