D3D遊戲程式設計系列（五）：自己動手編寫第一人稱射擊遊戲之室外場景的建構

結束了上一節即時戰略遊戲的講解，我們繼續來到第一人稱射擊遊戲的介紹，其實我感覺，真正要論遊戲的複雜性，第一人稱射擊遊戲絕對是最複雜的，尤其是室内場景的搭建和渲染，不過自己水準有限，而且也沒人幫我模組化，是以我們就已一個簡單的室外場景為例說明下。

首先，室外場景怎麼搭建，我們需要一個地圖，這個地圖的來源有很多種，我這裡介紹很簡單的一種，就是利用數組來建構地圖，形式如下：

int MapTemp[20][20]={

1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,

1,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,1,

1,0,0,0,1,1,1,1,0,0,0,0,1,1,1,1,0,0,0,1,

1,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,1,

1,0,0,0,1,1,1,1,0,0,0,0,1,1,1,1,0,0,0,1,

1,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,1,

1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,

};

其中0代表可以通行的路徑，1代表牆壁,那麼怎麼去應用這個地圖數組呢，首先，我們要構造牆壁和地面的Mesh對象，然後通過D3DXMatrixTranslation來建立一個位移矩陣，講Mesh移動到相應的位置上去。建構地圖的代碼如下：

for(int i=0;i<20;i++)
	{
		for(int j=0;j<20;j++)
		{
			D3DXMATRIX mat;
			D3DXMatrixTranslation(&mat,j*20,0,400-(i+1)*20);
			CString strId;
			strId.Format(L"%d %d",j*20,400-(i+1)*20);
			if(m_MapInfo[i][j]==0)
			{
				CDXEntity *pPath=new CDXEntity(&m_PathMesh,&mat);
				m_Root.AddEntity(pPath,strId);
			}else if(m_MapInfo[i][j]==1)
			{
				CDXEntity *pWall=new CDXEntity(&m_WallMesh,&mat);
				m_Root.AddEntity(pWall,strId);
			}
		}
	}

代碼還是很簡單的吧，好了，建構好地圖以後，我們怎麼來渲染呢，因為場景不大，是以我們可以直接渲染，但是我這裡沒有這樣做，而是用了八叉樹來做管理，這裡我就簡單介紹下室外的場景管理。

場景管理來說我了解的大緻分為三者：四叉樹，八叉樹，和bsp。四叉樹的應用非常廣，即可用于2d遊戲，也可用于3d遊戲，在室外簡單場景中，四叉樹是一個相對來說比較簡單，友善的管理，因為他将空間分為四個組成部分，室外場景往往沒有那麼複雜的構成，是以四個空間組成就已經夠用了。而八叉樹，則是可以将任意複雜的空間分割開來的一個場景管理結構，不僅可以應用與渲染，也可以很好的适用于物體的碰撞檢測，關于他，我推薦下面一篇文章：http://blog.csdn.net/zhanxinhang/article/details/6706217，這篇文章關于四叉樹和八叉樹的介紹寫的很好，大家可以看看，最後一個是bsp樹，它雖然是一個二叉樹，但是卻可以适用于任意次元的空間，而且有了它，我們可以進行多邊形裁剪甚至可以忽略z緩沖來做渲染的位置前後排序。而且這個也是在《3d遊戲大師程式設計技巧》裡做詳細介紹的，有興趣的讀者可以去翻一翻。

好了，回歸主題，我們在這個主要使用了八叉樹，也就是DXLib裡的CDXOctTree，關于八叉樹的建構如下所示：

void CDXOctNode::_Sort( CDXOctNode*  pNode,int iDepth)
{
	if(pNode->m_EntityList.size()<=1 || iDepth==iDepthNum)
	{
		return;
	}
	pNode->m_bSort=true;
	float x1=pNode->m_MinVec.x,y1=pNode->m_MinVec.y,z1=pNode->m_MinVec.z;
	float x2=pNode->m_MaxVec.x,y2=pNode->m_MaxVec.y,z2=pNode->m_MaxVec.z;
	pNode->m_pChildNode[0]=new CDXOctNode();
	pNode->m_pChildNode[0]->m_pParNode=pNode;
	pNode->m_pChildNode[0]->m_MinVec=D3DXVECTOR3(x1,y1+(y2-y1)/2,z1+(z2-z1)/2);
	pNode->m_pChildNode[0]->m_MaxVec=D3DXVECTOR3(x1+(x2-x1)/2,y2,z2);
	pNode->m_pChildNode[0]->m_strId.Format(_T("%d0"),iDepth);
	pNode->m_pChildNode[1]=new CDXOctNode();
	pNode->m_pChildNode[1]->m_pParNode=pNode;
	pNode->m_pChildNode[1]->m_MinVec=D3DXVECTOR3(x1+(x2-x1)/2,y1+(y2-y1)/2,z1+(z2-z1)/2);
	pNode->m_pChildNode[1]->m_MaxVec=D3DXVECTOR3(x2,y2,z2);
	pNode->m_pChildNode[1]->m_strId.Format(_T("%d1"),iDepth);
	pNode->m_pChildNode[2]=new CDXOctNode();
	pNode->m_pChildNode[2]->m_pParNode=pNode;
	pNode->m_pChildNode[2]->m_MinVec=D3DXVECTOR3(x1,y1+(y2-y1)/2,z1);
	pNode->m_pChildNode[2]->m_MaxVec=D3DXVECTOR3(x1+(x2-x1)/2,y2,z1+(z2-z1)/2);
	pNode->m_pChildNode[2]->m_strId.Format(_T("%d2"),iDepth);
	pNode->m_pChildNode[3]=new CDXOctNode();
	pNode->m_pChildNode[3]->m_pParNode=pNode;
	pNode->m_pChildNode[3]->m_MinVec=D3DXVECTOR3(x1+(x2-x1)/2,y1+(y2-y1)/2,z1);
	pNode->m_pChildNode[3]->m_MaxVec=D3DXVECTOR3(x2,y2,z1+(z2-z1)/2);
	pNode->m_pChildNode[3]->m_strId.Format(_T("%d3"),iDepth);
	pNode->m_pChildNode[4]=new CDXOctNode();
	pNode->m_pChildNode[4]->m_pParNode=pNode;
	pNode->m_pChildNode[4]->m_MinVec=D3DXVECTOR3(x1,y1,z1+(z2-z1)/2);
	pNode->m_pChildNode[4]->m_MaxVec=D3DXVECTOR3(x1+(x2-x1)/2,y1+(y2-y1)/2,z2);
	pNode->m_pChildNode[4]->m_strId.Format(_T("%d4"),iDepth);
	pNode->m_pChildNode[5]=new CDXOctNode();
	pNode->m_pChildNode[5]->m_pParNode=pNode;
	pNode->m_pChildNode[5]->m_MinVec=D3DXVECTOR3(x1+(x2-x1)/2,y1,z1+(z2-z1)/2);
	pNode->m_pChildNode[5]->m_MaxVec=D3DXVECTOR3(x2,y1+(y2-y1)/2,z2);
	pNode->m_pChildNode[5]->m_strId.Format(_T("%d5"),iDepth);
	pNode->m_pChildNode[6]=new CDXOctNode();
	pNode->m_pChildNode[6]->m_pParNode=pNode;
	pNode->m_pChildNode[6]->m_MinVec=D3DXVECTOR3(x1,y1,z1);
	pNode->m_pChildNode[6]->m_MaxVec=D3DXVECTOR3(x1+(x2-x1)/2,y1+(y2-y1)/2,z1+(z2-z1)/2);
	pNode->m_pChildNode[6]->m_strId.Format(_T("%d6"),iDepth);
	pNode->m_pChildNode[7]=new CDXOctNode();
	pNode->m_pChildNode[7]->m_pParNode=pNode;
	pNode->m_pChildNode[7]->m_MinVec=D3DXVECTOR3(x1+(x2-x1)/2,y1,z1);
	pNode->m_pChildNode[7]->m_MaxVec=D3DXVECTOR3(x2,y1+(y2-y1)/2,z1+(z2-z1)/2);
	pNode->m_pChildNode[7]->m_strId.Format(_T("%d7"),iDepth);
	list<CDXEntity*>::iterator it;
	for(it=pNode->m_EntityList.begin();it!=pNode->m_EntityList.end();)
	{
		for(int i=0;i<8;i++)
		{
			D3DXVECTOR3 min=pNode->m_pChildNode[i]->m_MinVec,max=pNode->m_pChildNode[i]->m_MaxVec;
			if(CDXHelper::CheckBoxCollide(min,max,(*it)->m_BoundMin,(*it)->m_BoundMax))
			{
				pNode->m_pChildNode[i]->m_EntityList.push_back((*it));
				//(*it)->m_NodeList.insert(pNode->m_pChildNode[i]);
			}
		}
		it=pNode->m_EntityList.erase(it);
	}
	iDepth++;
	for(int i=0;i<8;i++)
	{
		_Sort(pNode->m_pChildNode[i],iDepth);
	}
}

可以看出八叉樹的建構是一個深度遞歸的過程，遞歸結束的條件比較多，我這裡是當節點裡的物體為0或者為1的時候停止往下分割或者是當遞歸的深度等于最大遞歸深度的時候停止劃分，應該來說代碼還是比較容易了解的，我相信大家也能明白。值得一提的是八叉樹對空間的規劃還是比較費時的，是以我們應當在初始化的時候來做空間的分割動作。

劃分好以後，我們該如何去渲染呢，這裡不得不提一下視錐這個概念，什麼是視錐，我們知道，3d空間裡的坐标結果世界變換，視圖變換和投影變換以後會被變換到一個x【-1,1】，y【-1,1】，z【0,1】這樣的齊次裁剪空間裡，這裡面的點才是有效點，會經過視口變換到螢幕上去，那麼我們怎麼剔選出這些有效點呢，于是我們就需要将這個齊次裁剪空間進行逆變換，把他逆變換到世界坐标系中，然後我們就可以從成百上千的物體中剔選出我們真正可以觀察到的物體來做渲染，這樣可以極大的提高渲染效率。

D3DXPLANE Planes[6];
	D3DXMATRIX Matrix,matView,matProj;
	pDevice->GetTransform(D3DTS_PROJECTION,&matProj);
	pDevice->GetTransform(D3DTS_VIEW,&matView);
	Matrix=matView*matProj;
	Planes[0].a=Matrix._14+Matrix._13;
	Planes[0].b=Matrix._24+Matrix._23;
	Planes[0].c=Matrix._34+Matrix._33;
	Planes[0].d=Matrix._44+Matrix._43;
	D3DXPlaneNormalize(&Planes[0],&Planes[0]);
	Planes[1].a=Matrix._14-Matrix._13;
	Planes[1].b=Matrix._24-Matrix._23;
	Planes[1].c=Matrix._34-Matrix._33;
	Planes[1].d=Matrix._44-Matrix._43;
	D3DXPlaneNormalize(&Planes[1],&Planes[1]);
	Planes[2].a=Matrix._14+Matrix._11;
	Planes[2].b=Matrix._24+Matrix._21;
	Planes[2].c=Matrix._34+Matrix._31;
	Planes[2].d=Matrix._44+Matrix._41;
	D3DXPlaneNormalize(&Planes[2],&Planes[2]);
	Planes[3].a=Matrix._14-Matrix._11;
	Planes[3].b=Matrix._24-Matrix._21;
	Planes[3].c=Matrix._34-Matrix._31;
	Planes[3].d=Matrix._44-Matrix._41;
	D3DXPlaneNormalize(&Planes[3],&Planes[3]);
	Planes[4].a=Matrix._14-Matrix._12;
	Planes[4].b=Matrix._24-Matrix._22;
	Planes[4].c=Matrix._34-Matrix._32;
	Planes[4].d=Matrix._44-Matrix._42;
	D3DXPlaneNormalize(&Planes[4],&Planes[4]);
	Planes[5].a=Matrix._14+Matrix._12;
	Planes[5].b=Matrix._24+Matrix._22;
	Planes[5].c=Matrix._34+Matrix._32;
	Planes[5].d=Matrix._44+Matrix._42;
	D3DXPlaneNormalize(&Planes[5],&Planes[5]);

為什麼視錐的建構是上面這樣的呢，這裡面有一定的數學推導過程，http://blog.sina.com.cn/s/blog_4db3fe550100kyc5.html，這篇文章我相信可以解決各位的疑惑，我在此就不做累述。

好了，視錐已經建構完成，存在于世界坐标系裡，下面便是判斷物體是否在視錐裡，因為我們的物體都是從局部坐标系經過世界變換到世界坐标系裡的，難道要我們還要依次去計算每個頂點變換後的位置嗎，這樣顯然效率很低，我在這裡用了碰撞盒的技術，我們隻要預先計算好一個物體的碰撞盒，就算這個物體經過了怎麼樣的變換，我們隻要相應的去變換這個碰撞盒，然後去計算碰撞盒的頂點位置并重新調整碰撞盒，便可以得出這個物體的大概實際位置以及所占空間的大小，雖然這個方法不能說很精确，但是确實是一種很快捷，效率也很高的方法。我在這裡給出判斷物體是否在視錐裡的代碼，同樣是一個深度遞歸，和八叉樹的建構有些類似。

void CDXOctNode::_Render( CDXOctNode* pNode,D3DXPLANE* Planes,bool bCheck )
{
	if(bCheck)
	{
		bool bFullContained;
		if(_CheckInFrustum(pNode->m_MinVec,pNode->m_MaxVec,Planes,&bFullContained))
		{
				if(pNode->m_bSort==true)
				{
					for(int i=0;i<8;i++)
					{
						_Render(pNode->m_pChildNode[i],Planes,!bFullContained);
					}
				}else
				{
					if(pNode->m_EntityList.size()>0)
					{
						list<CDXEntity*>::iterator it;
						for(it=pNode->m_EntityList.begin();it!=pNode->m_EntityList.end();it++)
						{
							CDXEntity *pEntity=*it;
							bool bFull;
							if(_CheckInFrustum(pEntity->m_BoundMin,pEntity->m_BoundMax,Planes,&bFull))
							{
								pEntity->Render();
							}
						}
					}
				}

		}
	}else
	{
		if(pNode->m_bSort==true)
		{
			for(int i=0;i<8;i++)
			{
				_Render(pNode->m_pChildNode[i],Planes,false);
			}
		}else
		{
			if(pNode->m_EntityList.size()>0)
			{
				list<CDXEntity*>::iterator it;
				for(it=pNode->m_EntityList.begin();it!=pNode->m_EntityList.end();it++)
				{
					CDXEntity *pEntity=*it;
					pEntity->Render();
				}
			}
		}
	}
	
	
}

最後所有需要渲染的物體會儲存在一個渲染清單裡，然後做相應的變換并渲染。當然我這個八叉樹渲染做的也有很多不足的地方，比如說材質的切換，這個是一個非常消耗資源的操作，如何可以把相同的材質的頂點統一渲染，那麼渲染的效率必将提升一個檔次。

文章有不足之處，還望各位多多指正。

D3D遊戲程式設計系列（五）：自己動手編寫第一人稱射擊遊戲之室外場景的建構

繼續閱讀

d3d10檢視紋理資料全面總結

unity飛機大戰（2）一些細節問題對象池補充幀動畫的播放遊戲暫停碰撞檢測遊戲界面遊戲分數的存儲總結

web開發場景

Unity3D中手勢及重力加速度(神廟逃亡操作)

魔獸世界開發商動視暴雪迎來首個中國東家：騰訊

PCL筆記四：k-d tree和八叉樹；近鄰搜尋；半徑搜尋；體素内搜尋；空間變化檢測；一：近鄰搜尋二、八叉樹octree點雲壓縮三、基于八叉樹的空間劃分及搜尋操作四、無序點雲資料集的空間變化檢測

D3DLOCK_NOOVERWRITE。D3DLOCK_DISCARD lock 和unlock

八叉樹建立地圖并實作路徑規劃導航

Unity 3D遊戲開發學習筆記（1）井字棋

YUV和RGB調節色彩公式

1.6.5重載操作符

1.6.8矢量函數

3D engine - RealmForgeScreenshots:

錄影機、觀察矩陣與取景變換

立方體畫家消隐算法與Z-Buffer消隐算法比較

opengl 和direct3d坐标系的差別