採用Direct3D實作四叉樹LOD之經驗
本文討論採用Direct3D9實作LOD地形渲染之問題，其中基於LOD中用得最廣泛實現最簡單的四叉樹方法。目前講四叉樹LOD的文章很多，但是幾乎皆無一例外基於OpenGL討論，雖說觀念是主要的，具體實作上，因為D3D比起OpenGL來很多操作的過程不同、比較廢事。關於LOD的完整觀念及實作方法以及跟用常規OpenGL的做法差不太多的部分(如視錐裁剪)，本文未有提及。
本文僅談了我自己做過的經驗，或許並非良方，尚祈拋磚引玉、先進明達不吝賜教是幸！
跟OpenGL比，用Direct3D實作LOD地型，比較麻煩之處在於前者可以任意次序任意數目隨時繪製頂點，而D3D只能從固定的Vertex Buffer中繪出，雖然有提供輔助之Index Buffer，然而他的使用機能跟Vertex Buffer類似也必須一次性填充後再繪出(而且灌之前還必須指定好頂點或者index之總數)，這對於實作LOD這類頂點輸出邏輯性隨機性很高之工作比較不利。
基於此，比較好的策略是採用固定之vb，裡頭存儲好2D之頂點陣列，後頭的繪製工作由填充ib來完成。為了能夠像OpenGL那樣隨機添入要繪製之頂點，我為ib做了一個class很簡單，裡頭包括有一個std裡頭的vector物件，這樣隨時只要將必要之頂點添進vector，完成後一次性灌入ib物件即可。其聲名如下：
class IndexBufferVector //用於給IndexBuffer不預確定總數可隨時添加之類別
{
protected:
LPDIRECT3DDEVICE9 lpD3DDev; //D3D設備指標
std::vector<WORD> IndexVector; //用於存儲index的vector
public:
LPDIRECT3DINDEXBUFFER9 lpIB; //indexbuffer物件
void Init(LPDIRECT3DDEVICE9 _lpD3DDev); //初始化
void AddIndex(WORD index); //依順序添加新的index進去
BOOL FillBufferWithVector(); //用vector中的頂點來重建並填充indexbuffer
int GetIndexNum(); //獲得當前vector中index的總數
void ClearVector(); //清空vector中的index
void Release(); //釋放
};
很簡單但是很實用，任何時候只需要用AddIndex()將需要的頂點index添入到vector物件中，繪製前只要呼叫FillBufferWithVector()即可。
這個問題解決後還有一個不爽的問題就是，用OpenGL時，每次採用TRIANGLE_FAN畫每個矩形塊，這種方法既直觀簡便又效能高
如上圖之矩形塊只要按照0, 1, 2, 3, 4次序繪出就完成了。但是對於整個地型是由多個矩形塊組成，不可能只引用一次畫TRIANGLE_FAN之過程，有幾個矩形就要畫幾次TRIANGLE_FAN，對於D3D的IB來說是一次性繪出的，似乎只能採用TRIANGLE_LIST去具體繪製每個三角形才有可能。雖然可以每次繪完一個TRIANGLE_FAN再重灌ib再繪，但是這樣每一frame就要重灌並重繪多次ib了，雖然我沒有試過，但是我想效能可能會比較低。
所以我採用了TRIANGLE_LIST，這樣做雖然需要灌更多的重複頂點數目，但是填ib跟繪製過成只需一次完成。這樣要繪完上圖的矩形就需要依次添入0, 1, 2, 0, 2, 3, 0, 3, 4, 0, 4, 1，但是這樣做又有一個問題，就是如上圖，比如經過探測，繪製上方三角型0, 1, 2時需要補一個頂點5，TRIANGLE_FAN的話只要在1,2間插一個5就是0,1,5,2即搞定了，但是TRIANGLE_LIST就麻煩一點，需要0,1,5,0,5,2，即中間要插入5,0,5三個index，0就是當前矩形中心點了。比方講在遞歸繪每一個矩形塊時，如下
void LODSystem::RenderQuad(int XPos, int YPos, int Size)
{
switch(quadinfo.At(XPos,YPos).state)
{
case DIVIDE: //這一塊若還能繼續細分的話
//對每個子塊進行遞歸
RenderQuad(XPos-Size/2, YPos-Size/2, Size/2);
RenderQuad(XPos+Size/2, YPos-Size/2, Size/2);
RenderQuad(XPos-Size/2, YPos+Size/2, Size/2);
RenderQuad(XPos+Size/2, YPos+Size/2, Size/2);
break;
case DRAW: //說名此塊已經不能在細分了，可以畫出了
IBV.AddIndex(IndexOf(XPos,YPos)); //中間
IBV.AddIndex(IndexOf(XPos-Size, YPos-Size)); //左上
RemedyTop(XPos, YPos, Size, IndexOf(XPos,YPos));
IBV.AddIndex(IndexOf(XPos+Size,YPos-Size)); //右上
IBV.AddIndex(IndexOf(XPos,YPos)); //中間
IBV.AddIndex(IndexOf(XPos+Size,YPos-Size)); //右上
RemedyRight(XPos, YPos, Size, IndexOf(XPos,YPos));
IBV.AddIndex(IndexOf(XPos+Size,YPos+Size)); //右下
IBV.AddIndex(IndexOf(XPos,YPos)); //中間
IBV.AddIndex(IndexOf(XPos+Size,YPos+Size)); //右下
RemedyBottom(XPos, YPos, Size, IndexOf(XPos,YPos));
IBV.AddIndex(IndexOf(XPos-Size,YPos+Size));//左下
IBV.AddIndex(IndexOf(XPos,YPos)); //中間
IBV.AddIndex(IndexOf(XPos-Size,YPos+Size));//左下
RemedyLeft(XPos, YPos, Size, IndexOf(XPos,YPos));
IBV.AddIndex(IndexOf(XPos-Size, YPos-Size)); //左上
break;
default:
break;
}
}
其中RemedyTop()等等就是用來探測並補充四個方向是否要根據相鄰矩形塊的解析度添補相應之頂點index用的(自身遞歸)。如下圖，萬一上面相鄰矩形塊之解析度比自身大2或者更多時，畫0, 1, 2這個三角形時要添補的就不光是5了，在5之前還要補6，就是0, 1, 6, 0, 6, 5, 0, 5, 2，可見每次補一個點時都要插入原矩形的中心點0(用TRIANGLE_FAN的話就根本不用管這些)，這就是為何我要
void RemedyTop(int XPos,int YPos,int Size, DWORD CenterIndex); //修補頂部
的最後添入一個CenterIndex參數用來傳遞原矩形之中心點index，這樣在這些遞歸過程中，無論已經遞歸了多少層，都能代代相傳準確繪出矩形中心頂點。比如
void LODSystem::RemedyTop(int XPos,int YPos,int Size, DWORD CenterIndex)
{
if(YPos-Size<=0) //越界了
return;
if(Size<1)
return; //解析度已經不可再分
if(quadinfo.At(XPos, YPos-2*Size).state==DIVIDE) //上一塊可分的話
{
RemedyTop(XPos-Size/2, YPos-Size/2, Size/2, CenterIndex); //子塊上若還可能有裂縫的話
//繪製此點
IBV.AddIndex(IndexOf(XPos, YPos-Size));
IBV.AddIndex(CenterIndex);
IBV.AddIndex(IndexOf(XPos, YPos-Size));
RemedyTop(XPos+Size/2, YPos-Size/2, Size/2, CenterIndex); //子塊上若還可能有裂縫的話
}
}
2004年7月
