背景
在介紹層次細節算法之前，先來看兩幅圖檔。
圖一
圖二
這兩幅圖檔是用層次細節算法也即LOD算法繪制的地形網格。為了更清晰的看清地形網格的結構，我沒有給其貼上紋理。這兩幅圖檔看上去給人第一感覺就是分辨率不同，圖一分辨率較低，圖二分辨率很高。圖一圖二是由同一個程式生成的，圖一時在調節系數為1的情況下生成的，圖二是在調節系數為25的情況下生成的。為了增加對比度，我故意把兩幅圖檔的分辨率調節的差别很大。這個地形網格如果達到全分辨率的話将會是513像素*513像素。然而讀者看到的圖檔并沒有達到全分辨率。為什麼呢？大家想一下，在現實世界中，人眼的視角是有一個範圍的并不能看到360度範圍的場景；随着視線的往遠處移動，看到的東西越來越模糊；大家在想一下另外一個問題，把圖檔貼到一個物體上，如果這個物體的表面是平的，那麼任務肯定非常容易完成，如果物體表面凸凹不平，那麼你就不能把圖檔直接貼在上面，你必須把圖檔簡稱小的片段然後在艱難的貼在物體表面。同理層次細節算法就是模拟上述現實場景的技術，隻不過我們将換一套專有名詞來描述。上述地形網格在滿足下面三個條件時候被繪制，一，不在照相機視景體内的網格部分将不會被繪制；二，距離相機視點遠的地方網格以低分辨率來繪制，近的地方以高分辨率來繪制；三，粗糙的部分以高分辨率繪制，平坦的部分以較低的分辨率來繪制。這三個條件合稱節點評價系統。
地形高程圖
在層次細節地形繪制的過程中，每一個頂點坐标(x,y,z)被分為兩部分處理,(x,z)與y兩個部分。至于為什麼這樣做，當你看完本篇文章之後你就會明白。在OpenGL裡面Y軸是垂直向上的，是以頂點的y坐标值代表頂點的高度。高程圖就是存儲y坐标值得，其中一種方法就是使用raw格式的檔案。raw格式檔案是8為的，也就是說把raw格式的圖檔看成width*hight大小的矩形的話，其中每個元素表示一個8位的資料，範圍是0到256。在層次細節算法中要求地形的大小必須是正方形，而且必須滿足邊長的像素數為(2的n次方)+1;後文大家會明白為什麼會有這兩個限制。本文我們使用.raw格式的高程圖，其制作方法有很多，本文介紹一種最簡單的方法，用photoshop生成，如果要想生成自己想要的那種地形需要使用專業的方法來生成高程圖，本文使用的是随機生成的高程圖。方法很簡單，打開PS快捷鍵crtl+N建立一個513*513像素大小的項目，确定後從工具欄裡選擇濾鏡->渲染->分層雲彩,然後存儲為選擇.raw格式，至此高程圖就完成了。下面給出加載高程圖的程式代碼：
void GLLod::loadRawFile(LPSTR strName, int nSize)
{
FILE *pFile=NULL;
pFile=fopen(strName,"rb");
if(pFile==NULL)
{
MessageBox(NULL,TEXT("不能打開高度圖檔案"),TEXT("錯誤"),MB_OK);
return;
}
fread(pHeightMap,1,nSize,pFile);
int result=ferror(pFile);
if(result)
{
MessageBox(NULL,TEXT("讀取資料失敗"),TEXT("錯誤"),MB_OK);
}
fclose(pFile);
}
從高程圖中得到坐标(x,z)處的高度值的程式代碼：
int GLLod::getRawHeight(int x, int z)
{
int xx=x%(map_size+1);
int zz=z%(map_size+1);
if(!pHeightMap) return 0;
return pHeightMap[xx+(zz*(map_size+1))];
}
層次細節算法(LOD算法)
現在要步入正題了，我将會向大家介紹層次細節算法的原理。LOD算法采用的是四叉樹的結構來處理的。
我們看上圖，網格一是最初始的沒有分割的正方形，其邊長是
如果以像素表示邊長的話那麼邊上有
個像素。那麼在這裡我們可以看出每一個網格的邊長是5個像素，若每個像素間的距離為一的話，那麼每個網格的邊長是4，下文中我們預設每個像素間的距離唯一。将網格一等分為4個小網格，那麼這四個小網格是原網格的四個兒子節點，繼續劃分，圖二中的每個兒子網格繼續劃分為四個兒子。我們可以有選擇的劃分某些網格，每個網格一旦劃分的話，就必需劃分為四個相等的小網格。這種劃分方法很明顯是符合四叉樹的，隻不過這個四叉樹每個節點要麼有四個兒子，要麼沒有兒子。上面描述的網格是在x-z平面上，至此還沒有考慮y坐标呢。等劃分到一定标準的時候就會在此基礎上考慮y坐标，這個時候就可以渲染了，不過距離這一步還有很遠的距離。這個劃分結束的标準就是前文中所說的節點評價系統。下面我們就來詳細講述節點評價系統。
節點評價系統
相機裁剪上面我們劃分了網格一，直至網格三，但是那個劃分是盲目的，接下來我們就必需按照一定的标準有目的的劃分。來看幾副圖檔。
圖一
圖二
圖三
途中的紅色線代表照相機(也可以了解為人的眼睛)的視野範圍，及時隻有一小部分在相機視野内，我們就需要對其進行劃分，顯然圖一的正方形在視野内，對其劃分得到圖二中的網格，這個時候可以發現圖二中的最右邊的兩個兒子網格仍然在視野内，是以對其繼續劃分，最左邊兩個兒子網格不在視野内，是以不必劃分也即被裁剪掉了，于是得到了圖三中的網格。現在呈現給讀者的是平面的，實際上考慮y軸坐标的話，網格節點是一個三維的，為了友善我們以平面的方式來闡述，實際上是三維的。那麼如何進行三維的裁剪呢？在筆者的前一篇文章《3D坐标系、矩陣運算、視景體與裁剪》中對其算法進行了描述，這裡隻給出代碼。
int GLFrustum::isAabbInFrustum( AABB &aabb)
{
//aabb是一個AABB包圍盒
calculateFrustumPlanes();//計算平截頭體的六個面的方程
bool insect=false;//相機裁剪的标志
for(int i=0;i<6;i++)
{
//接下來3個if語句是軸分離的方法調整aabb包圍盒
if(g_frustumPlanes[i][0]<0.0f)
{
int temp=aabb.min[0];
aabb.min[0]=aabb.max[0];
aabb.max[0]=temp;
}
if(g_frustumPlanes[i][1]<0.0f)
{
int temp=aabb.min[1];
aabb.min[1]=aabb.max[1];
aabb.max[1]=temp;
}
if(g_frustumPlanes[i][2]<0)
{
int temp=aabb.min[2];
aabb.min[2]=aabb.max[2];
aabb.max[2]=temp;
}
if((g_frustumPlanes[i][0]*aabb.min[0]+g_frustumPlanes[i][1]*aabb.min[1]+g_frustumPlanes[i][2]*aabb.min[2]+g_frustumPlanes[i][3])>0.0f)
{
return 0;//不可見
}
if((g_frustumPlanes[i][0]*aabb.max[0]+g_frustumPlanes[i][1]*aabb.max[1]+g_frustumPlanes[i][2]*aabb.max[2]+g_frustumPlanes[i][3])>=0.0f)
{
insect=true;//裁剪
}
}
if(insect) return 1;//裁剪
return 2;//完全可見
}
這其中的calculateFrustumPlanes();是用來計算平截頭體的六個面的方程讀者可以點選這裡了解詳情。
視點距離上面的相機裁剪部分說在視野範圍内的繼續劃分，那麼視野内的那部分是不是一直繼續劃分呢？當然不是，過度的劃分并不會帶來視覺上的改觀而會增加GPU的處理負擔，試想如果有1000萬個頂點的話，那處理起來是非常消耗GPU的。根據常識，在現實世界中我們看遠處的物體會感覺到模糊，看近處的會感覺比較清晰，同樣LOD算法裡也是采用這個理念，距離視點遠的網格節點就不必要繼續劃分，而近處的網格則要繼續劃分。
如圖一個小兔子的眼睛看着右上角的網格，我們定義距離L是眼睛到網格中心的距離，d是目标網格的邊長。滿足條件
的時候網格繼續劃分，否則不需要繼續劃分。C1是一個可以根據實際渲染情況調節的值因子。圖一 圖二就是不同調節因子所形成的兩幅地形網格。
粗糙程度
在物體粗糙的部分需要繼續劃分以更好的顯示，而平坦的部分則不需要做過多的劃分，比如一個平面直接貼紋理就行了，做過多的劃分是沒有意義的。
那麼怎麼定義網格的粗糙程度呢？如圖所示，如果在xz平面考慮問題的話，那麼網格的每個節點的邊都是在一個平面上的，如果考慮y坐标的話原來是直線的邊會變成曲線，我們以每個網格四條邊的起伏程度和中心點的起伏程度的最大值來定義網格的粗糙度。舉個例子在上圖中dh4的值是那條邊的兩個頂點的y坐标值相加再除以2以後減去邊的中點的y坐标值得到dh4,這個dh4就是所在邊的起伏度，同樣方法計算dh1 dh2 dh3。中心點需要計算兩次，因為中心點所在的邊有兩條，分别是對應的兩個對角線。這6個值計算出來後選擇其中最大的作為粗糙度。設粗糙度為DHmax,那麼滿足
條件時繼續劃分，否則不劃分。其中C2是可以調節的因子。這個條件可以和上一個條件合并得到
。
總結來說if(相機裁剪通過&&視點-粗糙值合适) then 劃分節點，否則不劃分。
消除裂縫如果僅僅做到上面所說的是不是就可以渲染地形了呢？答案是否定的，因為這樣會産生裂縫。什麼是裂縫呢？我們來看兩幅圖檔就可以知道了。
地形一
地形二
為了友善大家觀察，每一副圖檔部分網格以線框的模式渲染另一部分以填充的方式渲染。圖一是正常的，圖二卻有許多列縫。這是什麼原因呢？為了弄明白這一點我們先放一放，看另外一個問題，網格是怎麼渲染的呢？
如圖是一個即将送往3D API渲染的網格節點。共有九個節點，中心點是0點，另外還有8個點。在OpenGL裡這個網格将會以三角形扇的方式進行渲染，比如032是一個三角形，021又是一個三角形。但是這樣渲染是有問題的，看接下來的圖檔：
在上面這個圖中左右兩個網格的劃分層次相差為1，也就是右側的網格比左側的多劃分一次。這時候問題出現了，當以頂點1 2 3渲染三角形和以頂點2 4 5渲染三角形以及以頂點5 4 3渲染三角形時候就出現了裂縫。圖上面是在xz平面上看不出問題，但是當給頂點賦予y坐标值的時候問題就出現了，因為點4可能和點2 點3不在一個高度，是以點2 點4點3組成的可能是一條折線。假如點2 點3的高度相同，點4比點2 點3 高，那麼點2 點3 點4便組成了一個三角形，這個三角形就是地形二上面的裂縫。大家可以看下比較大的裂縫會發現正好是個三角形，這就是很多諸如點2 點3 點4組成的三角形裂縫。那麼怎麼解決這個問題呢？可以在點1 點4之間增加一條線段，這個處理起來比較麻煩，本文采取的是将點4點5組成的線段取消，也即删除點4，這個時候裂縫便會消失，如地形一那樣。但是我們忽略了一個問題，這個還是比較棘手的問題，我們再看一張圖檔：
在這幅圖裡面，右側的網格比左側的網格多劃分了2次，這個時候頂點3 頂點6 頂點5 頂點4組成的邊比先前那個例子更加複雜了。即使删除點5，點3 點6 點4仍然可能組成一個三角形裂縫。點6不能删除，因為點6是正方形網格的頂點，删除它就等于删除網格了，是以隻能删除邊的中點。這下怎麼辦呢？如果有一種方法保證左右兩側的兩個正方形網格劃分層次相差小于等于1，那麼就可以按照前文所說的那樣通過删除點來消除三角形裂縫。能做到這一點嗎？答案是肯定的。假設左側的網格劃分值為f1右側的父親網格為f2當f2的父親網格需要劃分的時候必須保證f1也劃分。即滿足表達式;f2<f1<1的情況下可以被劃分。也即
因為d2=2d1是以化簡以後得到
現在問題集中在L2和L1的比值。看圖：
從視點做垂直于xz平面的直線交予xz面與O點。此時有
代入後得到
也就是說DHmax2>DHmax1的話就可以滿足上式，進而消除三角形裂縫。如何使得DHmax2>DHmax1呢？可以這樣做，對于左邊的正方形網格求緊貼其四條邊的邊長為其一半的8個小正方形的DHmax值，再與其自身的DHmax比較，并将最大值當初該網格的DHmax值。這樣就可以保證右側的小正方形父親被劃分時候左側的大的正方形網格也被劃分，這樣就可以保證他們的劃分層次相差小于等于1。如此便不會出現三角形裂縫。調整DHmax的函數代碼是：
void GLLod::modifyDHMatrix()
{
int edgeLength=2;
while(edgeLength<=map_size)
{
int halfEdgeLength=edgeLength>>1;
int halfChildEdgeLength=edgeLength>>2;
for(int z=halfEdgeLength;z<map_size;z+=edgeLength)
{
for(int x=halfEdgeLength;x<map_size;x+=edgeLength)
if(edgeLength==2)
{
int DH6[6];
DH6[0]=abs(((getRawHeight(x-halfEdgeLength,z+halfEdgeLength)+getRawHeight(x+halfEdgeLength,z+halfEdgeLength))>>1)-getRawHeight(x,z+halfEdgeLength));
DH6[1]=abs(((getRawHeight(x+halfEdgeLength,z+halfEdgeLength)+getRawHeight(x+halfEdgeLength,z-halfEdgeLength))>>1)-getRawHeight(x+halfEdgeLength,z));
DH6[2]=abs(((getRawHeight(x-halfEdgeLength,z-halfEdgeLength)+getRawHeight(x+halfEdgeLength,z-halfEdgeLength))>>1)-getRawHeight(x,z-halfEdgeLength));
DH6[3]=abs(((getRawHeight(x-halfEdgeLength,z+halfEdgeLength)+getRawHeight(x-halfEdgeLength,z-halfEdgeLength))>>1)-getRawHeight(x-halfEdgeLength,z));
DH6[4]=abs(((getRawHeight(x-halfEdgeLength,z-halfEdgeLength)+getRawHeight(x+halfEdgeLength,z+halfEdgeLength))>>1)-getRawHeight(x,z));
DH6[5]=abs(((getRawHeight(x+halfEdgeLength,z-halfEdgeLength)+getRawHeight(x-halfEdgeLength,z+halfEdgeLength))>>1)-getRawHeight(x,z));
int DHMax=DH6[0];
for(int i=1;i<6;i++)
{
if(DHMax<DH6[i])
DHMax=DH6[i];
}
setDHMatrix(x,z,DHMax);
}
else
{
int DH14[14];
int numDH=0;
int neighborX;
int neighborZ;
neighborX=x-edgeLength;
neighborZ=z;
if(neighborX>0)
{
DH14[numDH]=getDHMatrix(neighborX+halfChildEdgeLength,neighborZ-halfChildEdgeLength);
numDH++;
DH14[numDH]=getDHMatrix(neighborX+halfChildEdgeLength,neighborZ+halfChildEdgeLength);
numDH++;
}
neighborX=x;
neighborZ=z-edgeLength;
if(neighborZ>0)
{
DH14[numDH]=getDHMatrix(neighborX-halfChildEdgeLength,neighborZ+halfChildEdgeLength);
numDH++;
DH14[numDH]=getDHMatrix(neighborX+halfChildEdgeLength,neighborZ+halfChildEdgeLength);
numDH++;
}
neighborX=x+edgeLength;
neighborZ=z;
if(neighborX<map_size)
{
DH14[numDH]=getDHMatrix(neighborX-halfChildEdgeLength,neighborZ-halfChildEdgeLength);
numDH++;
DH14[numDH]=getDHMatrix(neighborX-halfChildEdgeLength,neighborZ+halfChildEdgeLength);
numDH++;
}
neighborX=x;
neighborZ=z+edgeLength;
if(neighborZ<map_size)
{
DH14[numDH]=getDHMatrix(neighborX-halfChildEdgeLength,neighborZ-halfChildEdgeLength);
numDH++;
DH14[numDH]=getDHMatrix(neighborX+halfChildEdgeLength,neighborZ-halfChildEdgeLength);
numDH++;
}
DH14[numDH]=abs(((getRawHeight(x-halfEdgeLength,z+halfEdgeLength)+getRawHeight(x+halfEdgeLength,z+halfEdgeLength))>>1)-getRawHeight(x,z+halfEdgeLength));
numDH++;
DH14[numDH]=abs(((getRawHeight(x+halfEdgeLength,z+halfEdgeLength)+getRawHeight(x+halfEdgeLength,z-halfEdgeLength))>>1)-getRawHeight(x+halfEdgeLength,z));
numDH++;
DH14[numDH]=abs(((getRawHeight(x-halfEdgeLength,z-halfEdgeLength)+getRawHeight(x+halfEdgeLength,z-halfEdgeLength))>>1)-getRawHeight(x,z-halfEdgeLength));
numDH++;
DH14[numDH]=abs(((getRawHeight(x-halfEdgeLength,z+halfEdgeLength)+getRawHeight(x-halfEdgeLength,z-halfEdgeLength))>>1)-getRawHeight(x-halfEdgeLength,z));
numDH++;
DH14[numDH]=abs(((getRawHeight(x-halfEdgeLength,z-halfEdgeLength)+getRawHeight(x+halfEdgeLength,z+halfEdgeLength))>>1)-getRawHeight(x,z));
numDH++;
DH14[numDH]=abs(((getRawHeight(x+halfEdgeLength,z-halfEdgeLength)+getRawHeight(x-halfEdgeLength,z+halfEdgeLength))>>1)-getRawHeight(x,z));
numDH++;
int DHMax=DH14[0];
for(int i=1;i<14;i++)
{
if(DHMax<DH14[i])
DHMax=DH14[i];
}
setDHMatrix(x,z,DHMax);
}
}
edgeLength=edgeLength<<1;
}
}
生成地形網格的代碼如下：
void GLLod::updateQuadTreeNode(int centerX, int centerZ,int edgeLength,int child)
{
if(edgeLength>2)
{
if(isObjectCulled(centerX,centerZ,edgeLength))
{
quadNode[centerX+centerZ*(map_size+1)].blend=2;
}
else
{
float fViewDistance,f;
int halfChildEdgeLength;
int childEdgeLength;
int blend;
int centerQuad[3];
centerQuad[0]=centerX;
centerQuad[2]=centerZ;
centerQuad[1]=getRawHeight(centerX,centerZ);
fViewDistance=frustum.distanceOfTwoPoints(centerQuad);
f=fViewDistance/(edgeLength*mfMinResolution*(max(mfDetailLevel*getDHMatrix(centerX,centerZ),1.0f)));
if(f<1.0f)
blend=1;
else
blend=0;
int temp=centerX+centerZ*(map_size+1);
quadNode[temp].blend=blend;
quadNode[temp].centerX=centerX;
quadNode[temp].centerY=centerQuad[1];
quadNode[temp].centerZ=centerZ;
quadNode[temp].child=child;
quadNode[temp].edgeLength=edgeLength;
if(blend==1)
{
int halfChildEdgeLength=edgeLength>>2;
int childEdgeLength=edgeLength>>1;
updateQuadTreeNode(centerX-halfChildEdgeLength,centerZ-halfChildEdgeLength,childEdgeLength,1);
updateQuadTreeNode(centerX+halfChildEdgeLength,centerZ-halfChildEdgeLength,childEdgeLength,2);
updateQuadTreeNode(centerX-halfChildEdgeLength,centerZ+halfChildEdgeLength,childEdgeLength,3);
updateQuadTreeNode(centerX+halfChildEdgeLength,centerZ+halfChildEdgeLength,childEdgeLength,4);
}
}
}
}
現在具體渲染的時候如何選擇頂點還沒講，現在已經很晚了，以後再寫吧。。
郵箱：[email protected]歡迎指出文中的錯誤之處。