Ｃａｔｍｕｌｌ－Ｒｏｍ插值算法在基于ＯｐｅｎＧＬ的三維地形繪制中的應用實現

摘要：文章對應用Catmull-Rom插值算法改進三維地形繪制顯示效果的過程進行了研究，在分析描述該算法后將其應用在具體的基于OpenGL的三維地形繪制實例中，通過工程實現的效果對比來看，Catmull-Rom插值算法將在很大程度上改進三維地形的繪制顯示的效果。

關鍵詞：Catmull-Rom插值算法；三維；OpenGL

中圖分類號：TP391文獻標識碼：A文章編號：1009-3044(2008)22-788-02

Catmull-Rom Interpolation Algorithm's Application and Realization in Drawing of OpenGL-based 3D Terrain

LIN Xia-fei1，WU Feng-ming2

(1.School of Electronic Science and Engineering of National University of Defense Technology， Changsha 410073，China;2. Information Section of Affiliated Union Hospital of Fujian Medical University， Fuzhou 350001， China)

Abstract: The article studied on the process of Catmull-Rom interpolation algorithm to improve show effecet of draw 3D terrain， the analysis and describe the algorithm and its application in specific OpenGL-based 3D terrain example， through projects to achieve the effect of contrast， Catmull-Rom interpolation algorithm will largely improve the 3D terrain's effect of show.

Key words: Catmull-Rom interpolation algorithm; 3D; OpenGL

1 引言

基于OpenGL的三維圖形制作的實質，是利用OpenGL提供的函數來繪制虛擬空間中的點、線、面，通過對這些最簡單圖元繪制、移動和組合加上光照效果并最終投射到計算機屏幕上，在視覺上形成與現實空間中相似的物體，從而在某種程度完成對現實世界的仿真顯示。

更深入一步分析，這些組成三維圖形的基本圖元的繪制其實又最終取決于OpenGL三維空間中點的坐標值，我們將這些點稱之為頂點。這并不難理解，因為最終所有的直線、曲線、平面或曲面最終都是由無數的頂點組成的。因此三維空間中頂點的數量多少決定了OpenGL所繪制的三維圖形與實物的相似程度。固定數量的頂點不足以顯示無限復雜的圖形，因此在三維圖形圖像顯示時我們經常可以看到圖形圖像出現與實物不相似的尖銳凸起和凹陷，這就是我們生活中經常談到的“馬賽克”現象。為了在一定程度上消除這種現象，使圖形顯示更為平滑，我們需要使用一些算法來改進圖形的顯示效果。

2 Catmull-Rom插值算法簡述

對圖形最常用的平滑處理有濾波和插值兩種，濾波處理雖然能夠得到圖形的平滑的三維顯示效果，但相對于原圖形，其內容發生改變，存在一定程度的失真，因此我們側重使用插值方法。而插值算法中使用較為廣泛的就是Catmull-Rom插值算法。

人們常常希望使用一條光滑的曲線來通過或者包含一個給定的點集，而這些點集其實就是圖形顯示時我們希望在空間里增加的頂點。圖1所示的Catmull-Rom樣條就是這樣一條曲線，其中P0、P1、P2和P3是控制點，而這個樣條最大的特點就是所生成的曲線一定通過所有的控制點。

定義一個浮點坐標t，t[0.0，1.0]，當t＝0.0時，即為P1點，當t＝1.0時即為P2點，當t在[0.0，1.0]間變化時，所描繪的曲線方程Q(t)為：

■（1）

該曲線是一種分3次的分段插值樣條，能夠保持C1連續。

3 Catmull-Rom插值算法在三維地形繪制中的應用

3.1 三維地形繪制原理

對于三維地形的繪制，通常采用經緯度線構成的規格化網格體逼近的方法。具體來說，就是將地圖要顯示的某塊區域的分成足夠多的網格，然后獲取每個網格的高程參數；接著根據網格的高程參數，算出頂點在三維空間中的位置，最后利用這些頂點描繪多邊形。這樣足夠多的多邊形連在一起就無限逼近于真實地形。此處我們使用的多邊形為三角形，其連接后的效果如圖2所示。

3.2 Catmull-Rom插值算法在三維地形繪制中的具體實現

既然OpenGL依賴于用空間點來描繪圖形，那么理論上空間點越多越密，描出的曲面就越光滑。因此在空間點不夠密集的情況下，我們應試圖用插值使空間點變得密集，而在原來的點和點之間所新插入的點值必須經過一定的計算，這樣才能使圖像過渡顯得更為自然。因此我們在此處就可以采用Catmull-Rom插值算法，該算法在一定程度上可以改善局部地形放大較大倍數后變得模糊和大范圍顯示地形時提高處理速度的問題。

假設我們現在在3×3的網格中使用Catmull-Rom插值算法。因為Catmull-Rom算法是一種3次的分段插值樣條，所以我們取4個點進行3次的分段插值。所以插值樣條的控制點在OpenGL三維空間中我們分別取其坐標為P0(0，0，z1)，P1(1，0，z2)，P2(2，0，z3)，P3(3，0，z4)，并將其代入公式1：

此時P0、P1、P2、P3的點已取，而t值取[0.0，1.0]區間的數。例如Catmull-Rom取5階插值，則每階單位間隔為0.2。如t起始取0，接下來第二次插值t取0.2，第三次t取0.4依次類推。

首先我們取t＝0時，在y=0平面上，根據P0、P1、P2、P3可以得出Q(0)的值，此處我們令Q(0)為Q0。接著我們來到y=1平面，同樣我們再取P0’(0，1，z1)，P1'(1，1，z2)，P2'(2，1，z3)，P3'(3，1，z4)，同樣根據公式5-1可以得出Q1，依次類推在y=2時可以得出Q2值、在y=3時可以得出Q3的值。

此時經計算得出的Q0、Q1、Q2、Q3四個點在同一個樣條上（即這四個點一定在同一個平面上），此處根據我們在y=0、y=1、y=2、y=3處分別取的四組控制點P0、P1、P2、P3的值，最后計算出Q0、Q1、Q2、Q3四個點的值均在x＝1平面上。接著將得到的Q0、Q1、Q2、Q3四個點分別看作新的插值樣條的控制點P0、P1、P2、P3，這樣根據公式1可以得出第一個插值點R0的值。

簡單來說相當于我們由4個P點得到1個Q點，由4個Q點得到1個R點，相當于取16個P點才得出1個R點。圖3給出了示意概圖，其中在與x軸平行方向應有4組Catmull-Rom樣條曲線，為使圖看上去不至于過于雜亂，因此只給出其中第一組。

按過程來講，我們整個計算R值的過程經過兩次的Catmull-Rom插值計算：第一次在x方向上，由4組P值得到1組Q值（每組均為4個點）；第二次在y方向上，由這組Q值得到1個R值。我們將這兩次計算所用的公式中的t分別取值為t1和t2，可以看出若t1在[0.0，1.0]上等間隔取5個值，而t2同樣在[0.0，1.0]上等間距取5個值，這個過程我們稱之為Catmull-Rom的5階插值，這樣t1和t2排列組合就可以得到25組值，如表1所示。

表1 Catmull-Rom算法的5階插值取值表

■

4 Catmull-Rom插值算法在三維地形繪制中的實現效果對比

以下是用OpenGL實現的沒有采用Catmull-Rom插值算法和采用Catmull-Rom插值算法所繪制出的隨機三維地形效果圖的對比：

■

圖4 沒有采用Catmull-Rom插值算法得出的圖形 圖5 采用Catmull-Rom插值算法得出的圖形

以下同樣是用OpenGL實現的Catmull-Rom插值算法6階插值和60階插值得出隨機三維地形效果圖對比：

(下轉第793頁)

（上接第789頁）■

圖6 采用60階Catmull-Rom插值算法得出的圖形 圖7采用6階Catmull-Rom插值算法得出的圖形

由以上對比可以看出采用了Catmull-Rom插值算法繪制出的圖形比沒有采用Catmull-Rom插值算法繪制出的圖形顯得更平滑，而在同樣采用Catmull-Rom插值算法繪制圖形時，插值的階數越高得出的圖形越平滑。

5 結束語

顯而易見，Catmull-Rom插值算法在三維地形的繪制中的應用可以使我們在計算機處理圖形能力固定的情況下，依然能夠靈活地處理各種分辨率經度的圖形：其既可以讓局部地形不斷放大而圖形不模糊；也可以讓大范圍地形顯示時不必讀出電子地圖上每個頂點的數據，而只需讀其中一些點的值，然后通過插值來補充頂點（前提是不超出對地形精度要求容忍值）。因此Catmull-Rom插值算法的使用將在很大程度上改進我們的三維地形的繪制顯示的效果。

參考文獻：

[1] 和平鴿工作室.OpenGL高級編程與可視化系統開發—高級編程篇[M].2版.北京：水利水電出版社，2006:140-142.

[2] 葉家鳴，錢萌，程樹林.基于Catmull-Rom插值算法的二維圖像的三維顯示[J].計算機技術與發展，2007，(10):234-235.

[3] Samuel R B. 3D計算機圖形學（OpenGL版）[M].唐龍，譯.北京：清華大學出版社，2006:47-51.