虛擬世界中曲線運(yùn)動(dòng)軌跡的生成算法

寧方美

摘要 本文針對(duì)虛擬場(chǎng)景中物體運(yùn)動(dòng)的實(shí)際需求，實(shí)現(xiàn)了幾種曲線軌跡的生成算法，并深入探討各算法的優(yōu)劣。用戶可以在交互方式下調(diào)整各算法的控制參數(shù)，并實(shí)時(shí)地觀察軌跡曲線。

【關(guān)鍵詞】虛擬現(xiàn)實(shí) 正弦函數(shù) 樣條曲線Catmull-Rom

當(dāng)前虛擬現(xiàn)實(shí)技術(shù)在計(jì)算機(jī)領(lǐng)域已經(jīng)得到了廣泛的發(fā)展，它可以提供視覺、聽覺、觸覺等感官的模擬，使用戶不用親臨現(xiàn)場(chǎng)就有如同身臨其境一般。近年來，虛擬現(xiàn)實(shí)技術(shù)在游戲、工程設(shè)計(jì)、醫(yī)學(xué)、文化傳播、旅游、教育等領(lǐng)域有著極為廣泛的應(yīng)用。

在虛擬現(xiàn)實(shí)中，經(jīng)常會(huì)將物體模型由空間中的一點(diǎn)移動(dòng)到另外一點(diǎn)。如游戲中，非玩家角色（NPC）的自由移動(dòng)。最常使用的辦法是直線運(yùn)動(dòng)，即線性插值。線性插值是數(shù)學(xué)、計(jì)算機(jī)圖形學(xué)等領(lǐng)域廣泛使用的一種簡(jiǎn)單插值方法。假設(shè)物體在時(shí)刻0時(shí)處于起點(diǎn)位置P0，在時(shí)刻l時(shí)處于終點(diǎn)位置P1，那么時(shí)刻為t（0<t<1）時(shí)，物體所處的坐標(biāo)位置為：

Pt=P0+（P1-P0）*t （1）

線性插值所實(shí)現(xiàn)的直線運(yùn)動(dòng)特點(diǎn)是快捷高效，但在應(yīng)用中有時(shí)顯得過于簡(jiǎn)單。其最大的問題在于物體所運(yùn)動(dòng)的軌跡可以被輕易的預(yù)測(cè)。在實(shí)際應(yīng)用中尤其是在游戲中，為了提高游戲的復(fù)雜度，往往需要讓物體以非直線的方式進(jìn)行移動(dòng)。這就需要實(shí)現(xiàn)曲線運(yùn)動(dòng)軌跡的生成算法。

曲線運(yùn)動(dòng)軌跡的要求是：提供兩個(gè)坐標(biāo)位置P。，P1分別表示模型的起始位置和終點(diǎn)位置，輸入一個(gè)參數(shù)t表示當(dāng)前時(shí)刻。實(shí)現(xiàn)一個(gè)連續(xù)且可導(dǎo)的函數(shù)f（t），當(dāng)t==0時(shí)返回起點(diǎn)位置Po，當(dāng)t=1時(shí)返回起點(diǎn)位置P1;當(dāng)t取O到1之間的值時(shí)，會(huì)返回坐標(biāo)位置P+。

Pt= f（t） （2）

f（0）= P0

f（1）=P1

將Pt看做是一個(gè)二維坐標(biāo)位置，其中含有兩個(gè)元素（Ptx，Pty）。算法實(shí)現(xiàn)時(shí)需要先得到兩個(gè)數(shù)據(jù)，一個(gè)是起點(diǎn)位置與終點(diǎn)位置的直線距離L;另一個(gè)是向量D，以表示運(yùn)動(dòng)軌跡的方向。D為一單位向量，其計(jì)算公式為：

D=（P1-P0）/L （3）

本文將實(shí)現(xiàn)三種曲線運(yùn)動(dòng)軌跡生成算法分別是：

（1）使用正弦函數(shù)的曲線;

（2）使用高次方程的曲線;

（3）使用樣條插值的曲線。

三種算法都是在線性插值的基礎(chǔ)上，為直線添加一個(gè)左右方向的偏移，以生成曲線軌跡。

1 正弦函數(shù)曲線軌跡

在直角三角形ABC中，∠C=90°，AB是∠C的對(duì)邊c，BC是∠A的對(duì)邊a，AC是∠B的對(duì)邊b，正弦函數(shù)就是sinA=a/e，即sinA=BC/AB。而正弦函數(shù)是一種波浪形的曲線，其周期為2π。設(shè)置時(shí)刻t從0到1的變化中經(jīng)歷n個(gè)正弦波浪周期?？梢詫⑶€函數(shù)f（t）寫成：

Pf x=P0?x+D.X*L*t-D.y*sin（t*n*2π） （4）

Pt y=P0y+ D.y*L*t+D.x*sin（t*n*2π）

當(dāng)n取值為5時(shí)，得到如圖1的曲線軌跡圖。

可以發(fā)現(xiàn)軌跡有過于明顯的正弦波，各個(gè)波峰波谷均勻地?cái)[布在軌跡中，這使得運(yùn)動(dòng)軌跡有些死板。為了解決這一問題，使用雙正弦波迭代處理的方式進(jìn)行優(yōu)化處理。將公式（4）做了如下改動(dòng)：

P，x=P0?x+D.x*L*t-D.y*sin（t*n*2π）*sin（t*π） （5）

Pt y=P0?y+D.y*L*t+D.x*sin（t*n*2π）*sin（t*π）

圖2為n取值為5的曲線軌跡圖。

由于本文算法是以線性插值為基礎(chǔ)，在直線添加一個(gè)左右方向的偏移。所以算法的重點(diǎn)是如何實(shí)現(xiàn)一個(gè)左右方向偏移的函數(shù)k（t）。對(duì)于函數(shù)k（t）的要求是：k（0）=0;k（1）=1;且k（t）在O到1之間處處可導(dǎo)。通過函數(shù)k（t）可以將曲線軌跡函數(shù)f（t）改為：

P，x=P0.x+D.x*L*t-D.y*k（t） （6）

Pty=P0y+D.y*L*t +D.x*k（t）

針對(duì)公式（4）和公式（5），其k（t）函數(shù)分別為：

k（t）=sin（t*n*2π） （7）

k（t）=sin（t*n*2π）+sin（t*π） （8）

使用正弦函數(shù)生成的曲線軌跡，依然是有一定規(guī)律的，本文后續(xù)內(nèi)容將提供生成更靈活多變的軌跡算法。

2 高次方程曲線軌跡

整式方程未知數(shù)次數(shù)最高項(xiàng)次數(shù)高于2次的方程，稱為高次方程。高次方程的一般形式為：

y=anxn+a（n-1）x（n-1）+…+a1x+a0?（9）

高次方程函數(shù)是一種處處可導(dǎo)的函數(shù)，并且n次方程會(huì)有n-1個(gè)曲線拐點(diǎn)，因此從理論上說可以用它來生成曲線運(yùn)動(dòng)軌跡。圖3為方程y=-0.05x5+0.15x4+0.15x3-0.3x2+ 0.1生成的圖形。

可以將左右偏移函數(shù)k（t）也設(shè)置成一個(gè)高次方程，為滿足k（0）=0;k（1）=1要求，則高次函數(shù)中：

a0=0 （10）

a1=--an-ann-1…-a2

使用高次方程的缺點(diǎn)是，通過參數(shù)的設(shè)置無法直觀地得到曲線的形態(tài)。此外n次方程有n-l個(gè)拐點(diǎn)，但這些拐點(diǎn)不容易設(shè)置到0到1之間。

3 樣條插值曲線軌跡

鑒于高次方程的缺點(diǎn)，本文又實(shí)現(xiàn)一種使用樣條插值的曲線。樣條方程是一類分段光滑、并且在各段交接處也有一定光滑性的函數(shù)。樣條一詞來源于工程繪圖人員為了將一些指定點(diǎn)連接成一條光順曲線所使用的工具，即富有彈性的細(xì)木條或薄鋼條。由這樣的樣條形成的曲線在連接點(diǎn)處具有連續(xù)的坡度與曲率。分段低次多項(xiàng)式、在分段處具有一定光滑性的函數(shù)插值就是模擬以上原理發(fā)展起來的，它克服了高次多項(xiàng)式插值可能出現(xiàn)的振蕩現(xiàn)象，具有較好的數(shù)值穩(wěn)定性和收斂性。

在具體實(shí)現(xiàn)中，需要為曲線提供n個(gè)額外的偏移距離值。即提供一個(gè)大小為n的數(shù)組S[n]，以表示在時(shí)刻i/n時(shí)的曲線左右偏移距離。通過樣條插值的方式實(shí)現(xiàn)左右偏移函數(shù)k（t）。本文使用的樣條函數(shù)為Catmull-Rom，雖然它不及B樣條圓潤(rùn)，但它的特點(diǎn)是經(jīng)過每一個(gè)控制點(diǎn)。其算法公式如下：

生成曲線軌跡如圖4所示。

在圖中，左邊控件用于設(shè)置左右偏移的距離值S[n]，通過8個(gè)控制點(diǎn)來生成Catmull-Rom樣條，最終實(shí)現(xiàn)曲線運(yùn)動(dòng)軌跡的生成。

4 總結(jié)

本文實(shí)現(xiàn)了三種曲線運(yùn)動(dòng)軌跡生成算法，第一種算法使用正弦函數(shù)生成了有規(guī)律的正弦波曲線軌跡;第二種算法使用使用高次方程生成的曲線軌跡雖然無規(guī)律但曲線難以控制，第三種使用Catmull-Rom樣條生成了靈活易控的曲線軌跡。通過比較發(fā)現(xiàn)采用第三種算法實(shí)現(xiàn)的軌跡生成可控性高、設(shè)置簡(jiǎn)單、漫游平穩(wěn)，無視覺抖動(dòng)。

參考文獻(xiàn)

[1]方福前，孫永君，總需求和總供給沖擊對(duì)我國(guó)失業(yè)和產(chǎn)出動(dòng)態(tài)關(guān)系的影響分析[J]，經(jīng)濟(jì)理論與經(jīng)濟(jì)管理，2009 （12）：5-12.

[2]裴玉，劉桂陽(yáng)，師翊，虛擬現(xiàn)實(shí)中基于Hermite曲線實(shí)現(xiàn)固定漫游路徑算法與優(yōu)化[J].黑龍江八一農(nóng)墾大學(xué)學(xué)報(bào)，2014 （02）：71- 24.

[3]http：//zh.wikipedia.org/wiki/樣條函數(shù)，