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

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

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

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

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

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

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

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

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

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

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