3D中視錐的剪裁
2009-04-29 00:00:00楊曉華
電腦知識與技術 2009年36期
摘要:3D中提高游戲的幀速率的一個有效的辦法就是把我們視野范圍以外的物體不渲染出來，也就是我們通常所講的視錐的剪裁(View Frustum Culling)。
關鍵詞:3D;游戲;視錐;剪裁
中圖分類號:TP311 文獻標識碼:A 文章編號:1009-3044(2009)36-10292-03
3D游戲制作中游戲的速度至關重要，玩家是沒有耐心去玩畫面停頓的游戲，對游戲來說30幀/秒的速度已經能夠運行，60幀/秒是比較合適的。當然幀速率越高，游戲的畫面就越流暢，游戲的效果就越出眾。3D中提高游戲的幀速率的一個有效的辦法就是把我們視野范圍以外的物體不渲染出來也就是我們通常所講的視錐的剪裁(View Frustum Culling)。比如CS中某個時刻視野范圍中的場景和一張完整地圖，3D加載模型的時候是需要把整個地圖的場景全部加載進去，其實在游戲某一時刻視野范圍內只能看到的是非常小的一部分。如果不把看不見的部分剪裁掉就導致極大的資源浪費，直接影響游戲的幀速率。如果要進行剪裁首先要判斷哪些物體能看得見，哪些物體看不見，由3D的基本知識可知，所謂看得見的物體就在游戲中虛擬攝影機所確定的視錐范圍以內或與視錐相交的物體，如下圖所示:
圖1 視錐的范圍 圖2 視錐的剪裁
由上圖可以看出要做視錐裁減先要計算出構成視錐的六個面的平面方程，然后在判斷物體是否與六個平面的相交。
下面我們來推導一下視錐的六個面的平面方程，假設世界坐標系有一點V它經過視圖轉換和透視投影轉換后為V'，假設中的轉換矩陣為M，推導過程如下:
v=(x y z w=1) M=(mü) v′=(x′ y′ z′ w′)
根據3D的基礎知識可知，如果V在“未轉換”視錐范圍之內，那么V'也一定在視錐范圍之內。V在視錐范圍之內的條件是下面不等式的成立:
–w′ < x′ < w′<
–w′ < y′ < w′
0 < z′ < w′
由表1不等式可以得到:
–w′ < x′
–(v·col4)<(v·col1)
0<(v·col4)+(v·col1)
0 替換成為矩陣中的數據如下: x(m14+m11)+y(m24+m21)+z(m34+m31)+w(m44+m31) =0 3D空間我們通常設置W = 1 等式如下: x(m14+m11)+y(m24+m21)+z(m34+m31)+(m44+m31) =0 由于平面的公式如下: ax+by+cz+d=0 所以可以推出平面裁剪面的平面方程如下: a=m14+m11，b=m24+m21，c=m34+m31，d=m44+m41 六個面的平面方程如表2所示。 當然我們不可能拿每個物體上的所有點和視錐進行裁剪判斷，這樣做效率就太低下，還不如把所有的場景模型全部渲染出來。3D游戲中采用的是為每個物體模型做一個包圍盒或者包圍球。用它們的包圍盒或者包圍球來進行視錐的裁剪判斷。具體的代碼如下: #include \"D3DHeader.h\" //自己定義的頭文件包含D3D的基本頭文件 class CFrustum { private: D3DXPLANE m_Planes[6]; //定義六個平面 public: CFrustum(LPDIRECT3DDEVICE9 pDevice); ~CFrustum(void); bool TestPoint(FLOAT XPOS， FLOAT YPOS， FLOAT ZPOS); //測試一個點是否在視錐中 //測試盒子是否在視錐中 bool TestCube(float XCentre， float YCentre， float ZCentre， float Size); //測試矩形是否在視錐中 bool TestRectangle(float XCentre， float YCentre， float ZCentre， float XSize， float YSize， float ZSize); //測試球是否在視錐中 bool TestSphere(float XCentre， float YCentre， float ZCentre， float Radius); 測試一個Mesh是否在視錐中 bool TestMesh(LPD3DXBASEMESH pMesh); }; #include \".\\frustum.h\" //計算視錐中的六個平面方程 CFrustum::CFrustum(LPDIRECT3DDEVICE9 pDevice) { D3DXMATRIX Matrix， ViewMatrix， ProjectionMatrix; pDevice->GetTransform(D3DTS_VIEW， ViewMatrix); pDevice->GetTransform(D3DTS_PROJECTION， ProjectionMatrix); D3DXMatrixMultiply(Matrix， ViewMatrix， ProjectionMatrix); m_Planes[0].a = Matrix._14 + Matrix._13; m_Planes[0].b = Matrix._24 + Matrix._23; m_Planes[0].c = Matrix._34 + Matrix._33; m_Planes[0].d = Matrix._44 + Matrix._43; D3DXPlaneNormalize(m_Planes[0]， m_Planes[0]); m_Planes[1].a = Matrix._14 - Matrix._13; m_Planes[1].b = Matrix._24 - Matrix._23; m_Planes[1].c = Matrix._34 - Matrix._33; m_Planes[1].d = Matrix._44 - Matrix._43; D3DXPlaneNormalize(m_Planes[1]， m_Planes[1]); m_Planes[2].a = Matrix._14 + Matrix._11; m_Planes[2].b = Matrix._24 + Matrix._21; m_Planes[2].c = Matrix._34 + Matrix._31; m_Planes[2].d = Matrix._44 + Matrix._41; D3DXPlaneNormalize(m_Planes[2]， m_Planes[2]); m_Planes[3].a = Matrix._14 - Matrix._11; m_Planes[3].b = Matrix._24 - Matrix._21; m_Planes[3].c = Matrix._34 - Matrix._31; m_Planes[3].d = Matrix._44 - Matrix._41; D3DXPlaneNormalize(m_Planes[3]， m_Planes[3]); m_Planes[4].a = Matrix._14 - Matrix._12; m_Planes[4].b = Matrix._24 - Matrix._22; m_Planes[4].c = Matrix._34 - Matrix._32; m_Planes[4].d = Matrix._44 - Matrix._42; D3DXPlaneNormalize(m_Planes[4]， m_Planes[4]); m_Planes[5].a = Matrix._14 + Matrix._12; m_Planes[5].b = Matrix._24 + Matrix._22; m_Planes[5].c = Matrix._34 + Matrix._32; m_Planes[5].d = Matrix._44 + Matrix._42; D3DXPlaneNormalize(m_Planes[5]， m_Planes[5]); }CFrustum::~CFrustum(void) {} bool CFrustum::TestPoint(FLOAT XPOS， FLOAT YPOS， FLOAT ZPOS) {for(short Counter = 0; Counter < 6; Counter++) {//判斷一個點和一個平面的關系 if(D3DXPlaneDotCoord(m_Planes[Counter]， D3DXVECTOR3(XPOS， YPOS， ZPOS)) < 0.0f) return 1; } return true;} bool CFrustum::TestCube(float XCentre， float YCentre， float ZCentre， float Size) { for(short Counter = 0; Counter < 6; Counter++) { if(D3DXPlaneDotCoord(m_Planes[Counter]， D3DXVECTOR3(XCentre - Size， YCentre - Size， ZCentre - Size)) >= 0.0f) continue; if(D3DXPlaneDotCoord(m_Planes[Counter]， D3DXVECTOR3(XCentre + Size， YCentre - Size， ZCentre - Size)) >= 0.0f) continue; if(D3DXPlaneDotCoord(m_Planes[Counter]， D3DXVECTOR3(XCentre - Size， YCentre + Size， ZCentre - Size)) >= 0.0f) continue; if(D3DXPlaneDotCoord(m_Planes[Counter]， D3DXVECTOR3(XCentre + Size， YCentre + Size， ZCentre - Size)) >= 0.0f) continue; if(D3DXPlaneDotCoord(m_Planes[Counter]， D3DXVECTOR3(XCentre - Size， YCentre - Size， ZCentre + Size)) >= 0.0f) continue; if(D3DXPlaneDotCoord(m_Planes[Counter]， D3DXVECTOR3(XCentre + Size， YCentre - Size， ZCentre + Size)) >= 0.0f) continue; if(D3DXPlaneDotCoord(m_Planes[Counter]， D3DXVECTOR3(XCentre - Size， YCentre + Size， ZCentre + Size)) >= 0.0f) continue; if(D3DXPlaneDotCoord(m_Planes[Counter]， D3DXVECTOR3(XCentre + Size， YCentre + Size， ZCentre + Size)) >= 0.0f) continue; return 1; } return true;} bool CFrustum::TestRectangle(float XCentre， float YCentre， float ZCentre， float XSize， float YSize， float ZSize) { for(short Counter = 0; Counter < 6; Counter++) { if(D3DXPlaneDotCoord(m_Planes[Counter]， D3DXVECTOR3(XCentre - XSize， YCentre - YSize， ZCentre - ZSize)) >= 0.0f) continue; if(D3DXPlaneDotCoord(m_Planes[Counter]， D3DXVECTOR3(XCentre + XSize， YCentre - YSize， ZCentre - ZSize)) >= 0.0f) continue; if(D3DXPlaneDotCoord(m_Planes[Counter]， D3DXVECTOR3(XCentre - XSize， YCentre + YSize， ZCentre - ZSize)) >= 0.0f) continue; if(D3DXPlaneDotCoord(m_Planes[Counter]， D3DXVECTOR3(XCentre + XSize， YCentre + YSize， ZCentre - ZSize)) >= 0.0f) continue; if(D3DXPlaneDotCoord(m_Planes[Counter]， D3DXVECTOR3(XCentre - XSize， YCentre - YSize， ZCentre + ZSize)) >= 0.0f) continue; if(D3DXPlaneDotCoord(m_Planes[Counter]， D3DXVECTOR3(XCentre + XSize， YCentre - YSize， ZCentre + ZSize)) >= 0.0f) continue; if(D3DXPlaneDotCoord(m_Planes[Counter]， D3DXVECTOR3(XCentre - XSize， YCentre + YSize， ZCentre + ZSize)) >= 0.0f) continue; if(D3DXPlaneDotCoord(m_Planes[Counter]， D3DXVECTOR3(XCentre + XSize， YCentre + YSize， ZCentre + ZSize)) >= 0.0f) continue; return 1; } return true; } bool CFrustum::TestSphere(float XCentre， float YCentre， float ZCentre， float Radius) {for(short Counter = 0; Counter < 6; Counter++) { if(D3DXPlaneDotCoord(m_Planes[Counter]， D3DXVECTOR3(XCentre， YCentre， ZCentre)) < -Radius) return 1; } return true; } bool CFrustum::TestMesh(LPD3DXBASEMESH pMesh) { if(pMesh) { DWORD NumVertices = pMesh->GetNumVertices(); DWORD FVF = pMesh->GetFVF(); UINT FVFSize = D3DXGetFVFVertexSize(FVF); LPVOID ppData = NULL; //鎖定mesh中的頂點緩沖區 pMesh->LockVertexBuffer(D3DLOCK_READONLY， ppData); if(ppData) {D3DXVECTOR3 Centre(0，0，0); FLOAT Radius = 0; //計算出mesh的包圍球 D3DXComputeBoundingSphere((D3DXVECTOR3*)ppData， NumVertices， FVFSize， Centre， Radius); if(TestSphere(Centre.x， Centre.y， Centre.z， Radius)) {pMesh->UnlockVertexBuffer(); return true; }} pMesh->UnlockVertexBuffer(); //解鎖頂點緩沖區 }return 1; } 2 結束語 上面只是對視錐的裁剪基本方法進行了分析，真實在大型3D場景中進行視錐的裁剪還需要借助四叉數這種數據結構來進行管理裁剪，這樣才能達到真正意思上的提高效率。 參考文獻: [1] Bruce Eckel.Thinking in C++[M].劉宗田等，譯.北京:機械工業出版社，2000. [2] Steve Summit，C Programming FAQs[M].Addison-Wesley，1996. [3] Robert B，Murry.C++ Strategies and Tactics[M].Addison-Wesley，1993.
