等邊折線的離散曲率表示及應(yīng)用

劉 婕， 張芳娟

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

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

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

(1)

其中

Circ(x)=(cosx, sinx)，

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

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

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

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

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

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

1.1 離散曲率的計算

平面曲線的離散曲率有多種計算方法[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)的距離以及由三個頂點(diǎn)Pi-1、Pi和Pi+1所確定的三角形的有向面積，由此定義的離散曲率跟平面曲線的曲率具有類似性質(zhì)，即該定義的離散曲率具有平移旋轉(zhuǎn)不變性，可以反映折線在頂點(diǎn)Pi處的彎曲方向。

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

(4)

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

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

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

因折線是等邊長的，故可通過簡化離散曲率計算公式(3)，得出簡化后的等邊折線重構(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共線，此時

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

(8)

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

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

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

2.1 方法描述

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

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

記時刻t的中間折線為

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

(9)

同樣采用線性插值,得出折線St首個頂點(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”的變形過程

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

3 結(jié)語

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