虛擬世界中曲線運動軌跡的生成算法

寧方美

摘要 本文針對虛擬場景中物體運動的實際需求，實現了幾種曲線軌跡的生成算法，并深入探討各算法的優劣。用戶可以在交互方式下調整各算法的控制參數，并實時地觀察軌跡曲線。

【關鍵詞】虛擬現實 正弦函數 樣條曲線Catmull-Rom

當前虛擬現實技術在計算機領域已經得到了廣泛的發展，它可以提供視覺、聽覺、觸覺等感官的模擬，使用戶不用親臨現場就有如同身臨其境一般。近年來，虛擬現實技術在游戲、工程設計、醫學、文化傳播、旅游、教育等領域有著極為廣泛的應用。

在虛擬現實中，經常會將物體模型由空間中的一點移動到另外一點。如游戲中，非玩家角色（NPC）的自由移動。最常使用的辦法是直線運動，即線性插值。線性插值是數學、計算機圖形學等領域廣泛使用的一種簡單插值方法。假設物體在時刻0時處于起點位置P0，在時刻l時處于終點位置P1，那么時刻為t（0<t<1）時，物體所處的坐標位置為：

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

線性插值所實現的直線運動特點是快捷高效，但在應用中有時顯得過于簡單。其最大的問題在于物體所運動的軌跡可以被輕易的預測。在實際應用中尤其是在游戲中，為了提高游戲的復雜度，往往需要讓物體以非直線的方式進行移動。這就需要實現曲線運動軌跡的生成算法。

曲線運動軌跡的要求是：提供兩個坐標位置P。，P1分別表示模型的起始位置和終點位置，輸入一個參數t表示當前時刻。實現一個連續且可導的函數f（t），當t==0時返回起點位置Po，當t=1時返回起點位置P1;當t取O到1之間的值時，會返回坐標位置P+。

Pt= f（t） （2）

f（0）= P0

f（1）=P1

將Pt看做是一個二維坐標位置，其中含有兩個元素（Ptx，Pty）。算法實現時需要先得到兩個數據，一個是起點位置與終點位置的直線距離L;另一個是向量D，以表示運動軌跡的方向。D為一單位向量，其計算公式為：

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

本文將實現三種曲線運動軌跡生成算法分別是：

（1）使用正弦函數的曲線;

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

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

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

1 正弦函數曲線軌跡

在直角三角形ABC中，∠C=90°，AB是∠C的對邊c，BC是∠A的對邊a，AC是∠B的對邊b，正弦函數就是sinA=a/e，即sinA=BC/AB。而正弦函數是一種波浪形的曲線，其周期為2π。設置時刻t從0到1的變化中經歷n個正弦波浪周期?？梢詫⑶€函數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π）

當n取值為5時，得到如圖1的曲線軌跡圖。

可以發現軌跡有過于明顯的正弦波，各個波峰波谷均勻地擺布在軌跡中，這使得運動軌跡有些死板。為了解決這一問題，使用雙正弦波迭代處理的方式進行優化處理。將公式（4）做了如下改動：

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的曲線軌跡圖。

由于本文算法是以線性插值為基礎，在直線添加一個左右方向的偏移。所以算法的重點是如何實現一個左右方向偏移的函數k（t）。對于函數k（t）的要求是：k（0）=0;k（1）=1;且k（t）在O到1之間處處可導。通過函數k（t）可以將曲線軌跡函數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）

針對公式（4）和公式（5），其k（t）函數分別為：

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

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

使用正弦函數生成的曲線軌跡，依然是有一定規律的，本文后續內容將提供生成更靈活多變的軌跡算法。

2 高次方程曲線軌跡

整式方程未知數次數最高項次數高于2次的方程，稱為高次方程。高次方程的一般形式為：

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

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

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

a0=0 （10）

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

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

3 樣條插值曲線軌跡

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

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

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

在圖中，左邊控件用于設置左右偏移的距離值S[n]，通過8個控制點來生成Catmull-Rom樣條，最終實現曲線運動軌跡的生成。

4 總結

本文實現了三種曲線運動軌跡生成算法，第一種算法使用正弦函數生成了有規律的正弦波曲線軌跡;第二種算法使用使用高次方程生成的曲線軌跡雖然無規律但曲線難以控制，第三種使用Catmull-Rom樣條生成了靈活易控的曲線軌跡。通過比較發現采用第三種算法實現的軌跡生成可控性高、設置簡單、漫游平穩，無視覺抖動。

參考文獻

[1]方福前，孫永君，總需求和總供給沖擊對我國失業和產出動態關系的影響分析[J]，經濟理論與經濟管理，2009 （12）：5-12.

[2]裴玉，劉桂陽，師翊，虛擬現實中基于Hermite曲線實現固定漫游路徑算法與優化[J].黑龍江八一農墾大學學報，2014 （02）：71- 24.

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