劉 婕， 張芳娟

(西安郵電大學(xué) 理學(xué)院， 陜西 西安 710121)

數(shù)學(xué)上的平面曲線由無(wú)窮多個(gè)點(diǎn)組成。在計(jì)算機(jī)圖形學(xué)中，由于受內(nèi)存資源所限，利用圖形系統(tǒng)根本無(wú)法繪制出真正數(shù)學(xué)意義上的平面曲線，而是采用有限個(gè)離散點(diǎn)對(duì)其實(shí)現(xiàn)近似表示。采用離散點(diǎn)位置坐標(biāo)顯式地表示平面曲線，有利于圖形系統(tǒng)快速高效地對(duì)其進(jìn)行繪制，但這種表示無(wú)法反映平面曲線內(nèi)在的幾何特征。

平面曲線有一個(gè)內(nèi)在幾何特征，那就是曲率。曲線微分幾何的基本定理表明[1]，在不考慮剛體運(yùn)動(dòng)變換的情形下，一條弧長(zhǎng)參數(shù)平面曲線C(s)完全可由其曲率κ(s)描述。也就是說(shuō)，兩條平面曲線具有相同的曲率κ(s)當(dāng)且僅當(dāng)其中任意一條曲線是另一條曲線的剛體運(yùn)動(dòng)變換。若用積分形式描述，即是

(1)

其中

Circ(x)=(cosx, sinx)，

φ0是C(s)在s=0處的切線與x軸的夾角?？梢钥闯?，φ0和C(0)確定了剛體運(yùn)動(dòng)變換，一旦這兩個(gè)參數(shù)以及曲率κ(s)給定了，則平面曲線C(s)就可通過(guò)方程(1)完全確定下來(lái)[2]。

考慮到實(shí)際平面曲線需要簡(jiǎn)化為離散形式，即平面折線或平面多邊形，才可以方便處理，本文引入一種離散曲率的定義方式[3]，并由此得出，若不考慮剛體運(yùn)動(dòng)變換，給定內(nèi)部頂點(diǎn)處的離散曲率和折線邊長(zhǎng)，即可完全確定一個(gè)平面等邊多邊形。此即曲線微分幾何基本定理在平面等邊多邊形情形下的一種離散形式。

可以證明，只要給定初始頂點(diǎn)和初始邊的方向，即可由離散曲率和邊長(zhǎng)值唯一確定一條平面等邊折線，此外，其頂點(diǎn)坐標(biāo)的解析表達(dá)式也容易獲得。平面等邊折線的這種離散曲率表示，可用于計(jì)算機(jī)動(dòng)畫(huà)中的變形(Morphing)。

變形是指從初始物體到目標(biāo)物體的連續(xù)光滑自然的變換，這里的物體可以是圖像[4-6]、曲線[2,7-8]、折線和多邊形[9-12]、網(wǎng)格[13-15]等。變形必須解決“對(duì)應(yīng)問(wèn)題”和“插值問(wèn)題”，即尋找初始和目標(biāo)物體的對(duì)應(yīng)關(guān)系，并實(shí)現(xiàn)兩者之間自然光滑地過(guò)渡。本文將基于平面等邊折線的離散曲率表示研究平面等邊折線的變形插值問(wèn)題。

1 平面等邊折線的離散曲率表示

折線的離散曲率對(duì)應(yīng)于曲線的曲率。若不考慮剛體運(yùn)動(dòng)變換，則給定離散曲率和邊長(zhǎng)，即可完全確定一條平面等邊折線。

1.1 離散曲率的計(jì)算

平面曲線的離散曲率有多種計(jì)算方法[3, 16-19]。

平面折線P=[P0P1…Pn]任一頂點(diǎn)Pi處的離散曲率Ci由該頂點(diǎn)及其相鄰兩頂點(diǎn)Pi-1和Pi+1決定，即[3]

(2)

其中

整理即得

(3)

其中

L=[(xi+1-xi-1)2+(yi+1-yi-1)2]3/2。

公式(3)僅涉及到兩點(diǎn)的距離以及由三個(gè)頂點(diǎn)Pi-1、Pi和Pi+1所確定的三角形的有向面積，由此定義的離散曲率跟平面曲線的曲率具有類似性質(zhì)，即該定義的離散曲率具有平移旋轉(zhuǎn)不變性，可以反映折線在頂點(diǎn)Pi處的彎曲方向。

1.2 由離散曲率和邊長(zhǎng)重構(gòu)等邊折線

(4)

并通過(guò)逐個(gè)迭代，求得折線的各頂點(diǎn)。

1.3 平面等邊折線重構(gòu)的唯一性

重構(gòu)出的平面等邊折線是唯一的，即在不考慮剛體運(yùn)動(dòng)變換的情形下，方程組(4)的解是唯一的。

因折線是等邊長(zhǎng)的，故可通過(guò)簡(jiǎn)化離散曲率計(jì)算公式(3)，得出簡(jiǎn)化后的等邊折線重構(gòu)算法，即

(5)

(6)

1.4 平面等邊折線的頂點(diǎn)坐標(biāo)表達(dá)式

由公式(6)和f(θi)=Ci≠0,可以得到

(7)

代入

得到方程組(5)的唯一解(xi+1,yi+1)。

若Ci=0,這意味著Pi+1與Pi,Pi-1共線，此時(shí)

因此，給定離散曲率C，邊長(zhǎng)值ρ，初始頂點(diǎn)P0(x0,y0)和初始邊與x軸夾角θ0,重構(gòu)出的平面等邊折線的頂點(diǎn)表達(dá)式為

(8)

其中θi由式(7)給出。

2 離散曲率表示在變形中的應(yīng)用

借助公式(1)重構(gòu)中間時(shí)刻的曲線[2]，將其應(yīng)用于變形所產(chǎn)生的過(guò)程自然光滑，但該方法計(jì)算復(fù)雜度較高，這是因?yàn)楣?1)一般無(wú)解析解，需要設(shè)計(jì)數(shù)值算法近似求解。以下嘗試借助公式(8),利用離散曲率重構(gòu)變形中間時(shí)刻的曲線。

2.1 方法描述

給定兩條平面等邊折線，分別記為

S0=[P00P01…P0n],
ST=[PT0PT1…PTn],

記時(shí)刻t的中間折線為

St=[Pt0Pt1…Ptn](0≤t≤T),

(9)

同樣采用線性插值,得出折線St首個(gè)頂點(diǎn)Pt0及其首條邊與x坐標(biāo)軸的夾角θt0，即

(10)

2.2 實(shí)驗(yàn)結(jié)果

以“U”到“S”的變形為例,驗(yàn)證所給方法的有效性，并與文獻(xiàn)[2,9]等方法所得結(jié)果進(jìn)行比較。實(shí)驗(yàn)結(jié)果如圖1所示。

圖1 “U”到“S”的變形過(guò)程

由實(shí)驗(yàn)結(jié)果可見(jiàn)，所給方法與文獻(xiàn)[2，9]方法的變形結(jié)果很接近，變形過(guò)程自然光滑。從計(jì)算復(fù)雜性角度來(lái)看，所給方法比文獻(xiàn)[9]方法復(fù)雜度略高，但比文獻(xiàn)[2]方法簡(jiǎn)單許多。當(dāng)然，在4種方法中，線性插值方法的復(fù)雜度最低，但在變形過(guò)程中出現(xiàn)扭曲和自交現(xiàn)象。

3 結(jié)語(yǔ)

給出曲線微分幾何有關(guān)曲率基本定理的一種離散形式，即平面等邊折線的離散曲率表示。證明了當(dāng)給定內(nèi)頂點(diǎn)處的離散曲率和折線的邊長(zhǎng)值時(shí)，只要再給定初始頂點(diǎn)和初始邊的方向就可以唯一確定一條平面等邊折線。同時(shí)給出了頂點(diǎn)的解析表達(dá)式，并將離散曲率表示用于平面等邊折線的變形。