1， 引言：
目前在許多導航類産品中地圖引擎的使用已經很多見了，特别是随着近些年硬體技術的發展，加上許多三維的圖形繪圖軟硬體庫的支援，使得三維地圖引擎的使用也變得比較常見了。對于一款好的産品，三維地圖引擎中的地形跟蹤算法是一個不可或缺的環節。
本文的目的是想介紹一種三維地形跟蹤算法，以及在程式中的具體實作過程。使得人們對地形跟蹤算法有深入了解，進而能夠更好的掌握三維地圖引擎開發的原理和本質。
2， 地形跟蹤算法分析與設計：
2.1、三維地形跟蹤簡介：
在現實世界中我們每當觀察一個物體時都會有視線的概念存在。我們所處不同的位置，向着不同的方向，看出去的物體景色都是不一樣的。比如同是一座山，你在山腳下和坐在飛機上看出去的内容是不同的。是以地點的選擇決定了眼中看到的事物。
所謂的地點，在三維的數字化世界中我們可以虛拟成一個坐标，一系列連續坐标的組合便形成了一條跟蹤的軌迹，而這個過程也稱為是三維地形跟蹤的過程。
三維地形跟蹤的方式有很多，我們通常用跟蹤算法模拟出需要的地形跟蹤方式。比如飛機、船隻、汽車等等。不同的實體模型實作的地形跟蹤算法也是不同的。比如同樣是車，卡車和自行車所模拟出的感覺是不一樣的；同樣是船，快艇和油輪的行駛感覺也有差別。一套完善的實體模型在三維地形跟蹤算法中很重要。
2.2、三維地形跟蹤算法的設計思路：
在本文中我們想模拟出的是最基本的地形跟蹤方式：貼着地形進行運動。隻要不出現視線穿越物體的情況并且盡量貼近地形即可。我們采用山地地形，地形有一定的起伏，但幅度并不是很大。
我們使用相機來表示玩家的視點，相機前面是預先渲染好的地形。玩家駕駛的汽車必須在地表前進，不能穿越地面，是以需要計算相機所在的地形高度，并将視點相應的往上移。如下圖：
通常的做法是取目前位置所在單元格内的四個點的高度平均值作為相機的高度，也就有如下的公式：
高度 = k*（V0+V1+V2+V3）/4
其中V0到V3代表單元格四個頂點的高度，k代表縮放系數。
咋一看這種方式還是比較理想的。但是細一想就會出現問題：我們所在的單元格其實是由兩個三角形組成的，而由于地形的關系這兩個三角形可能不是在一個平面上，四個點的高度值也可能相差較大。使用四點高度平均之後的高度值時，當我們從高度低的位置向一個高度比較大的位置移動時，會産生平均高度值小于目前位置的實際高度值的情況，也就會看到穿越地形的現象發生。這在現實中最常見的情況就是我們從山腳下向一個很陡的山坡上行進時，由于高度的巨大差距造成了我們看到的景象一下子穿越了地形。
在實際的三維地形使用過程中，如果遇到了穿越地形現象的發生肯定是不能允許的。是以我們可以使用一種改進的方法加以改善。上面的算法是将相機所處單元格四點的高度取平均值，改進之後我們可以把單元格中的兩個三角形各看成一個平面，因為組成三維地形圖最基本的單元便是三角形，至于三角形如何劃分可以遵循給出的資料内容。具體的操作流程可以這樣：
1） 判斷相機位置處在單元格的哪個三角形中。
2） 将相機所在的三角形組成一個新的矩形平面。
3） 求相機所在該平面的高度。
4） 将該高度設為目前相機的高度。
其中的難點是如何求相機所在矩形平面的高度。
在三維坐标中，矩形四點的高度并不一緻。也就是說矩形平面可能不平行于任意兩個坐标軸組成的平面。我們可以先将相機坐标投影到矩形的兩條直角邊上，然後再求投影坐标的高度。求出兩個值之後，我們選擇其中較大的一個值作為目前相機點的高度值。平面圖是這樣的：
其中，V0V1V2V3’就是一個新的矩形平面。V0、V1、V2是單元格的三個頂點。V3’是配合矩形平面生成的一個新的頂點。P是目前相機的位置，而P1和P2是P點對于V0V1和V1V2兩條線段的投影。計算出P1和P2兩點的高度之後我們取較大的一個作為P點的高度即可。
那麼我們如何求得P1和P2的高度哪？其實可以用簡單的平面幾何的方法解決這一問題。我們假設各點的三維坐标分别為V0(x0,y0,z0)，V1(x1,y1,z1)，V2(x2,y2,z2)，P(xp0,yp0,zp0)，以上都是已知的參數。P1和P2的坐标分别是P1(xp1,yp1,zp1)，P2(xp2,yp2,zp2)，其中xp1=xp0，zp2=zp0我們要求的便是yp1和yp2。對于Z軸的平面投影是這樣的：
由V0V1Q組成的三角形，我們要求的是P1的y坐标。這下簡單了吧。是以可以得出公式：
P1R/V1Q = V0R/V0Q
根據已知參數可得： P1R = （（xp0 – x0）/（x1 – x0））*（y1 – y0）
由此可得： yp1 = （（（xp0 – x0）/（x1 – x0））*（y1 – y0） + y0）
這樣，一邊投影的高度坐标就算出來了。同樣的方法，我們可以算出P2的高度坐标yp2。由公式可以得到：
yp2 = （（（zp0 – z1）/（z2 – z1））*（y2 – y1） + y1）
然後，比較yp1和yp2的值，取大的一個作為P的高度值yp0便可以了。當然，在求值的過程中還有一些細節問題需要我們注意。比如上面的公式都是在y0<y1和y1<y2的情況下得到的，當y0>y1或者y1>y2時情況是不一樣的，但是思路是一樣的。是以通過這一套運算我們便能求出目前相機的高度了。然後再配合一系列的投影變換，我們的三維地形跟蹤便算完成了。
3， 地形跟蹤算法源碼分析：
在具體源碼的實作過程中，我們采用了OpenGL的三維圖形庫，使用VC++6.0作為開發平台。具體的實作代碼和注釋如下：
//以下是計算目前相機位置的x和z坐标
gCamara.position[0] += 5*sin(gCamara.dir[2]*PI/180);
gCamara.position[2] += 5*cos(gCamara.dir[2]*PI/180);
gCamara.target[0] += 5*sin(gCamara.dir[2]*PI/180);
gCamara.target[2] += 5*cos(gCamara.dir[2]*PI/180);
if(gCamara.position[2]<0) return; //當相機的坐标出了資料的表示區域不需要處理
//以下是根據目前的坐标系坐标獲得對應資料的坐标
float row_vstep,colum_vstep;
float deltaX,deltaZ,average1,average2;
float k1,k2;
colum_vstep = (float)(TERRAIN_WIDTH)/(float)(HEIGHTMAP_WIDTH-1);
row_vstep = (float)(TERRAIN_HEIGHT)/(float)(HEIGHTMAP_HEIGHT-1);
int cell_x = (gCamara.position[0] + HEIGHTMAP_WIDTH/2) / colum_vstep;
int cell_y = (gCamara.position[2] + HEIGHTMAP_WIDTH/2) /row_vstep;
int v0 = cell_x + cell_y*HEIGHTMAP_WIDTH;
int v1 = v0 + 1;
int v2 = v1 + HEIGHTMAP_WIDTH;
int v3 = v0 + HEIGHTMAP_WIDTH;
//獲得目前相機所處單元格的四點坐标
//計算斜率，判斷目前點處在哪個三角形中
k1=((gCamara.position[2]-gOpenGlPosition.pPositionList[v0].PositionZ)/(gCamara.position[0]-gOpenGlPosition.pPositionList[v0].PositionX));
k2=((gOpenGlPosition.pPositionList[v2].PositionZ-gOpenGlPosition.pPositionList[v0].PositionZ)/(gOpenGlPosition.pPositionList[v2].PositionX-gOpenGlPosition.pPositionList[v0].PositionX));
if(k1<k2) //在一個三角形中
{
//判斷投影三角形中V0和V1兩點y坐标的位置
//進而決定deltaX的取值 if(gOpenGlPosition.pPositionList[v1].PositionY<gOpenGlPosition.pPositionList[ v0].PositionY)
{
deltaX=(gOpenGlPosition.pPositionList[v1].PositionX-gCamara.position[0]);
}
else
{
deltaX=(gCamara.position[0]-gOpenGlPosition.pPositionList[v0].PositionX);
}
//計算一個投影三角形y坐标的高度差 average1=(deltaX/(gOpenGlPosition.pPositionList[v1].PositionX-gOpenGlPosition .pPositionList[v0].PositionX))*(gOpenGlPosition.pPositionList[v1].Posi
tionY - gOpenGlPosition.pPositionList[v0].PositionY);
//判斷投影三角形中V1和V2兩點y坐标的位置
//進而決定deltaZ的取值
if(gOpenGlPosition.pPositionList[v2].PositionY<gOpenGlPosition.pPositionList[v
1].PositionY)
{
deltaZ=(gOpenGlPosition.pPositionList[v2].PositionZ - gCamara.position[2]);
}
else
{
deltaZ=(gCamara.position[2] - gOpenGlPosition.pPositionList[v1].PositionZ);
}
//計算另一個投影三角形y坐标的高度差
average2=(deltaZ/(gOpenGlPosition.pPositionList[v2].PositionZ-gOpenGlPosition.
pPositionList[v1].PositionZ))*(gOpenGlPosition.pPositionList[v2].PositionY - gOpenGlPosition.pPositionList[v1].PositionY);
//高度差都是正值，取絕對值較大的那個
if(average1<0) average1 *= (-1);
if(average2<0) average2 *= (-1);
if(average1 > average2) average2 = average1;
//計算目前相機位置的y坐标
gCamara.position[1]=(gOpenGlPosition.pPositionList[v0].PositionY+gOpenGlPosi
tion.pPositionList[v2].PositionY+gOpenGlPosition.pPositionList[v1].PositionY)/3 + average2 + 50;
gCamara.target[1] = gCamara.position[1];
}
else //在另一個三角形中
{
//判斷投影三角形中V2和V3兩點y坐标的位置
//進而決定deltaX的取值
if(gOpenGlPosition.pPositionList[v2].PositionY<gOpenGlPosition.pPositionList[
v 3].PositionY)
{
deltaX=(gOpenGlPosition.pPositionList[v2].PositionX- gCamara.position[0]);
}
else
{
deltaX=(gCamara.position[0]-gOpenGlPosition.pPositionList[v3].PositionX);
}
//計算一個投影三角形y坐标的高度差 average1=(deltaX/(gOpenGlPosition.pPositionList[v2].PositionX-gOpenGlPosition .pPositionList[v3].PositionX))*(gOpenGlPosition.pPositionList[v2].Posi
tionY - gOpenGlPosition.pPositionList[v3].PositionY);
//判斷投影三角形中V3和V0兩點y坐标的位置
//進而決定deltaZ的取值
if(gOpenGlPosition.pPositionList[v3].PositionY<gOpenGlPosition.pPositionList[v 0].PositionY)
{
deltaZ=(gOpenGlPosition.pPositionList[v3].PositionZ - gCamara.position[2]);
}
else
{
deltaZ=(gCamara.position[2] - gOpenGlPosition.pPositionList[v0].PositionZ);
}
//計算另一個投影三角形y坐标的高度差
average2=(deltaZ/(gOpenGlPosition.pPositionList[v3].PositionZ-gOpenGlPosition.
pPositionList[v0].PositionZ))*(gOpenGlPosition.pPositionList[v3].PositionY - gOpenGlPosition.pPositionList[v0].PositionY);
//高度差都是正值，取絕對值較大的那個
if(average1<0) average1 *= (-1);
if(average2<0) average2 *= (-1);
if(average1 > average2) average2 = average1;
//計算目前相機位置的y坐标
gCamara.position[1]=(gOpenGlPosition.pPositionList[v0].PositionY+gOpenGlPosi
tion.pPositionList[v3].PositionY+gOpenGlPosition.pPositionList[v2].PositionY)/3 + average2 + 50;
gCamara.target[1] = gCamara.position[1];
}
以上程式實作之後的效果截圖是這樣的：
4， 結語：
随着三維地圖引擎技術在國内的迅猛發展，地圖引擎市場逐漸成為一個新興的增值亮點，掌握地形引擎跟蹤算法的設計和開發技術将是廣大開發人員的必修課，希望本文對三維地圖引擎的跟蹤算法軟體設計構架和對應算法的研究能夠起到一定的抛磚引玉的作用。