利用反向光線彎曲實現(xiàn)體數(shù)據(jù)模型的自由變形模擬

摘 要：提出了一種用反向光線彎曲繪制體數(shù)據(jù)自由變形的方法，并將經(jīng)典的體繪制優(yōu)化技術(shù)引入到基于反向光線彎曲的變形體數(shù)據(jù)繪制算法中，避免了變形繪制過程中大量對繪制結(jié)果沒有貢獻(xiàn)的無效運算。實驗結(jié)果表明體數(shù)據(jù)變形繪制方法可明顯加快變形繪制模擬速度。

關(guān)鍵詞：體繪制；變形；算法優(yōu)化

中圖分類號：TP391.41文獻(xiàn)標(biāo)志碼：A

文章編號：1001-3695(2007)06-0178-03

體數(shù)據(jù)（Volume Data）的直接體繪制（Direct Volume Rendering）和變形模擬技術(shù)在醫(yī)學(xué)、天文學(xué)、地質(zhì)學(xué)和氣象學(xué)研究中有重要應(yīng)用價值。在科學(xué)計算和實際工程應(yīng)用中，待繪制的數(shù)據(jù)是非常龐大的，如果用直接體繪制方法對每個體元都進(jìn)行處理，則以普通桌面計算機(jī)的帶寬和處理能力遠(yuǎn)遠(yuǎn)無法取得實時或交互繪制速度。因此，從20世紀(jì)80年代以來，許多研究人員都在努力地尋求提高直接體繪制速度的方法。

本文提出的算法采用反向光線彎曲技術(shù)，并用曲線擬合技術(shù)自適應(yīng)地用較長的直線段逼近彎曲的光線。該算法既可避免對體數(shù)據(jù)進(jìn)行采樣生成變形后中間體數(shù)據(jù)的過程，也允許將靜態(tài)體數(shù)據(jù)繪制加速技術(shù)引入到體數(shù)據(jù)的變形模擬過程中，從而提高了繪制速度并且減少了變形以及繪制過程中兩次采樣可能帶來的圖像模糊。

1 相關(guān)的研究工作

在計算機(jī)圖形中進(jìn)行場景繪制時，光線是沿直線被反向跟蹤的。通常，在繪制一個連續(xù)變形的場景對象時，繪制場景前需要對場景對象的模型按一定規(guī)則進(jìn)行處理，生成各幀對應(yīng)時刻變形后場景對象的幾何模型，然后才能開始繪制過程。由于場景模型間存在相互遮擋和自身遮擋，場景對象通常只有很少一部分可見，對不可見部分的變形處理是多余的，這種處理方案顯然不具有高效性。

Barr［1］提出光線彎曲技術(shù)可以實現(xiàn)對場景對象變形的模擬，而不必對場景模型進(jìn)行真正的變形操作，從而能避免大量的對場景模型的不可見部分的變形處理過程。其基本思想是將待變形的物體保持原狀，而在跟蹤光線時，根據(jù)變形規(guī)則將空間中通過的光線沿與物體變形相反的方向進(jìn)行彎曲，從而使繪制結(jié)果看上去是場景對象發(fā)生了變形（圖1）。

Kurzion等人［2］提出的光線彎曲子（Ray Deflectors）采用了光線彎曲的思想。光線彎曲子是一個在某個特定形狀（如球形）的變形函數(shù)（圖1），且該函數(shù)只在它所包含空間內(nèi)起作用。光線彎曲子的作用是在光線跟蹤時，將光線向所預(yù)期場景對象的變形相反的方向進(jìn)行歪曲，實現(xiàn)虛擬變形。光線彎曲子中心的變形最大，而離中心越遠(yuǎn)則變形越小。采用不同的變形函數(shù)就可得到不同特性的光線彎曲子，從而實現(xiàn)不同的變形效果，如膨脹、擠壓和扭曲等。將不同特性的光線彎曲子組合起來，可以實現(xiàn)更為復(fù)雜的變形。此外，光線彎曲子的缺陷在于，不同的光線彎曲子組合方式（包括其空間相對位置、排列的先后順序）得到的變形效果可能截然不同，且難以預(yù)測。因此，光線彎曲子只適合通過不斷地調(diào)節(jié)不同光線彎曲子的組合方式，以交互方式來塑造變形效果。

為避免上述缺陷，筆者保留光線彎曲的思想，而將光線彎曲子的變形定義用自由變形技術(shù)來實現(xiàn)。這樣，可使變形成為可控、可預(yù)測的，且可方便地與有關(guān)變形計算模型，如有限元方法等［3］結(jié)合起來。實現(xiàn)具有物理真實感的體數(shù)據(jù)變形。

2 算法

采用自由變形技術(shù)，變形空間中的點在變形前后的空間位置是由FFD網(wǎng)格上的控制點按選定的內(nèi)插函數(shù)確定的。由Sederberg等人［4］提出的基本FFD算法采用基于Bernstein多項式的Bazier內(nèi)插函數(shù)。為了減少變形計算量，采用B樣條函數(shù)計算空間點在空間發(fā)生變形后的位置變化。基本依據(jù)是B樣條函數(shù)具有很好的局部性，其函數(shù)值只由有限個（由其階數(shù)決定）控制節(jié)點確定，而Bazier函數(shù)的取值與所有節(jié)點值有關(guān)。此外，用B樣條函數(shù)取代Bazier函數(shù)的另一個優(yōu)勢是在表達(dá)相同變形效果時，前者所需的控制節(jié)點數(shù)遠(yuǎn)遠(yuǎn)少于后者。

2.1 FFD空間中單個點的處理

2.2 連續(xù)彎曲光線的擬合算法

在未做任何優(yōu)化的體繪制過程中，由觀測者發(fā)出的每條光線在體數(shù)據(jù)空間中被均勻采樣，然后將各采樣點處求得的光線強(qiáng)度根據(jù)體元的透明度組合起來，得到各光線所對應(yīng)的像元亮度值。鑒于體數(shù)據(jù)尺寸通常太大，難以實現(xiàn)交互和實時實現(xiàn)，人們提出了各種優(yōu)化技術(shù)減少體繪制的運算量。最有效的方法有Spaceleaping［5，6］、earlyray termination［5］和自適應(yīng)步長采樣［7］。其中，Spaceleaping和自適應(yīng)步長采樣均在盡可能保證圖像質(zhì)量的前提下，設(shè)法減少體數(shù)據(jù)空間中的冗余采樣點，使平均采樣步長加長，從而加速體繪制過程。

在基于光線彎曲的體繪制過程中，彎曲的光線可以用等長的折線段擬合。為了減少誤差，使變形面平滑，用等長的折線段擬合彎曲的光線時，折線段的長度要根據(jù)最大變形強(qiáng)度來確定。顯然，采用這種方法擬合彎曲光線，會在沒有變形或變形幅度很小的區(qū)域浪費相當(dāng)多的資源來進(jìn)行復(fù)雜的變形運算；同時，基于非均勻采樣步長的體繪制加速算法在用等長的折線段擬合彎曲的光線時也將無法實現(xiàn)。為了避免上述缺陷，設(shè)計了如下根據(jù)空間變形強(qiáng)度自動用非等長折線段擬合彎曲光線的算法。

下面討論如何估計出沿光線各采樣點處的度量變形強(qiáng)度的局部斜率。考慮到使用的是3階B樣條FFD， 因此可以在采樣點的鄰域中用兩條二次多項式曲線擬合彎曲的光線（對平面曲線則只要用一條二次多項式曲線），進(jìn)而根據(jù)二次多項式擬合的曲線估計出彎曲光線的局部曲率。

2.3 繪制優(yōu)化算法的實現(xiàn)

采用光線彎曲的思想繪制變形的體數(shù)據(jù)的過程中，體數(shù)據(jù)本身沒有發(fā)生任何改變；同時，彎曲的光線是用盡可能長的直線段來逼近的，對其中任一個小的光線段的處理與普通體繪制是完全相同的。基于距離編碼的優(yōu)化算法，如空間跳躍(SpaceLeaping)［5，6］技術(shù)，可以直接在該算法中實現(xiàn)。唯一的限制是，當(dāng)某個采樣點對應(yīng)的體元的距離編碼值大于擬合彎曲光線的折線段的剩余長度時，可跳躍距離被限制為折線段的剩余長度。與普通體繪制一樣，在采用光線彎曲繪制變形的體數(shù)據(jù)時，沿光線對體數(shù)據(jù)的采樣仍是跟蹤光線從前向后進(jìn)行的，同樣存在前面的不透明體元遮擋后續(xù)體元的現(xiàn)象。因此，可以與普通體繪制一樣，用光線提前終止的方法加速繪制過程。

3 實驗結(jié)果

圖3是體數(shù)據(jù)Engine的繪制結(jié)果。圖3(a)為未變形的情況。圖3(b)用光線彎曲算法繪制，但彎曲的光線是用等長線段擬合的，線段長度為2個體元單位。繪制結(jié)果顯示在變形幅度大的區(qū)域，本應(yīng)光滑的表面顯得很粗糙。圖3(c)也是用光線彎曲算法繪制的，但連續(xù)彎曲光線是用本文提出的基于局部曲率的逼近算法擬合的，擬合光線的線段平均長度為1.9個體元單位。通過對比可見，在擬合光線的線段平均長度很接近的情況下，該算法可以將連續(xù)變形的表面繪制得很光滑。

實驗結(jié)果證實，空間跳躍和光線提前終止同樣可以加快基于光線彎曲的體繪制過程。表1給出了優(yōu)化算法對幾組變形體數(shù)據(jù)的加速情況。對于靜態(tài)體數(shù)據(jù)的繪制，空間跳躍和光線提前終止結(jié)合起來通常可達(dá)到10倍左右的加速比［5］。

表1的結(jié)果顯示，對不同特性的體數(shù)據(jù)，空間跳躍和光線提前終止結(jié)合起來可對基于光線彎曲的體數(shù)據(jù)變形繪制過程加快2.34－6.56倍，這比對靜態(tài)體數(shù)據(jù)的繪制取得的加速比低很多。這種加速比的降低是由于前述空間跳躍距離受到擬合彎曲光線的折線段長度的限制引起的。盡管如此，體繪制非常耗費計算時間，能取得2.34－6.56倍的加速比仍是令人滿意的。

4 結(jié)束語

本文提出了一種用反向光線彎曲繪制體數(shù)據(jù)自由變形的方法，并將經(jīng)典的體繪制優(yōu)化技術(shù)引入到變形繪制算法中，避免了變形繪制過程中大量對繪制結(jié)果沒有貢獻(xiàn)的無效運算，得到了一種快速體數(shù)據(jù)自由變形模擬方案。用均勻B樣條FFD確定彎曲光線路徑的方法有效地避免了光線彎曲子難以描述復(fù)雜變形的缺陷，可模擬任意復(fù)雜的體數(shù)據(jù)變形。實驗結(jié)果表明，該體數(shù)據(jù)變形繪制方法在繪制速度上具有很大提高。

本文中所涉及到的圖表、注解、公式等內(nèi)容請以PDF格式閱讀原文。