3D游戏技术 - 大型3D地图优化渲染技术

目录(?)[+]

技术简介：

如果需要渲染一个大型3D地图，由于数据量，需要渲染的东西非常多，所以尤其一些慢一点的机器就会变得非常卡。

如下面这些会造成帧率（FPS）下降的图：

这样的图：

还有这样的魔兽世界的图：

还有这样的图：

上图我是指她的背景图啦，O(∩_∩)O~

到底暴雪是如何让这些场景流畅地渲染的呢？

那就必须想办法提高渲染速度，也就是帧率（FPS）要提高，才能使得游戏流畅。

像魔兽这样大型的游戏具体是用什么技术的，那不敢确定，但是会用到的相关技术会有：

1 地图分块剔除

2 kd树

3 BSP树

4 LOD技术

等等，最后把场景优化到极致，才能创造出伟大的游戏。每一种技术都需要挺长篇幅介绍的，本文就分析第一种技术：地图分块剔除技术(Sub-Grid Culling)

地图分块剔除技术分析

1 3D投影剔除（Frustum Culling）

把一个大地图分隔成由多个小地图实现，那么本来需要调用一次就画成的地图，现在需要多次调用，但是我们可以利用Frustum Culling（3D投影剔除-我觉得比较满意的翻译名词吧）技术优化渲染。

Frustum Culling的思路是：

每一个小块地图，我们计算相对应的AABB包围体；

如果这个AABB和Frustum不相交，那么就不用画这个小块地图。

Frustum是下面的形状：

如下图：大三角形代表Frustum，小方格代表小块地图，灰色小方格代表与Frustum相交，需要渲染，但是白色地带就不与Frustum相交，所以都不需要渲染，那么我们可以看出这就省了很多渲染内容，也就速度大大提高了。

也可以不使用分格和AABB方法进行Frustum Culling：

把所有的组成地图的三角形输入显卡，让显卡自动裁剪不在Frustum中的三角形。但是其实这个裁剪发生在Clipping Stage，就差不多是渲染管道的最后的渲染工作了，那么这些不用渲染你的三角形就会通过大部分渲染管道，如：Vertex Shader，那么就浪费了很多计算呢时间。

使用分格和AABB的方法就可以简单的利用一个AABB相交测试就可以丢弃一个不用渲染的小块地图数据了，效率可以更大地提高。

掌握这个分块的数量也很重要。如下图：

这样就是更加精细的分块了。需要渲染的面积更小，但是相对而言节省的也不多，而精细的分块也需要花费更多的计算时间，如：画基本元几何图形的函数调用次数也更多了，还有AABB相交测试也增多；

所谓过犹不及，要掌握好度很重要。到底分多少个小地图块是合适的，就需要实际分析了。

而且这里的Frustum Culling主要是节省了vertex shading的计算时间，如果一个图形是主要花费在pixel shanding上的话，比如大量的particles需要渲染，那么这种Frustum Culling方法就不会有太大的提速效果。

2 小地图数据结构体：

首先需要定义一个结构体来表示小地图块的数据，如下：

structSubGrid
{
ID3DXMesh*mesh;
AABBbox;

//Forsorting.
booloperator<(constSubGrid&rhs)const;

conststaticintNUM_ROWS=33;
conststaticintNUM_COLS=33;
conststaticintNUM_TRIS=(NUM_ROWS-1)*(NUM_COLS-1)*2;
conststaticintNUM_VERTS=NUM_ROWS*NUM_COLS;
};

主要功能就是这个比较操作符，是根据该小地图块和Camera的距离来比较大小的。把所有的小地图块都按照离Camera的距离由进到远排序，那么就方便由进到远（前到后）的渲染方式渲染。这种方式的渲染可以提高速度，尤其是在渲染管道中pixel shader渲染是瓶颈的时候，当然如果vertex shader是瓶颈，那么就提高不明显。

基本原理就是：

1 更新像素（pixel)的时候，渲染器都进行了depth testing(深度测试），只有在距离镜头进的物体才会被渲染，否则就不渲染。

2 如果排序好的物体，前面渲染的物体都是距离近的，那么后面渲染的物体如果被前面的物体挡住了，那么就根本不需要渲染了。

3 如果不是排序好的话，前面渲染了距离远的物体，那么后面渲染的物体距离镜头更加近，就需要重新更新当前像素，造成重复浪费渲染。

boolTerrain::SubGrid::operator<(constSubGrid&rhs)const
{
D3DXVECTOR3d1=box.center()-gCamera->pos();
D3DXVECTOR3d2=rhs.box.center()-gCamera->pos();
returnD3DXVec3LengthSq(&d1)<D3DXVec3LengthSq(&d2);
}

3 计算出Frustum：

Frustum是从投影矩阵抽出来的。因为Frustum就是由投影矩阵定义的，也可以说两者都在实际上是一致的：

如投影示意图：

Frustum：

其实是概念上不一样，但是实际上一样的东西。不过应用也不一样。

下面是从投影矩阵抽出Frustum的程序：

voidCamera::buildWorldFrustumPlanes()
{
//Note:Extractthefrustumplanesinworldspace.

D3DXMATRIXVP=mView*mProj;

D3DXVECTOR4col0(VP(0,0),VP(1,0),VP(2,0),VP(3,0));
D3DXVECTOR4col1(VP(0,1),VP(1,1),VP(2,1),VP(3,1));
D3DXVECTOR4col2(VP(0,2),VP(1,2),VP(2,2),VP(3,2));
D3DXVECTOR4col3(VP(0,3),VP(1,3),VP(2,3),VP(3,3));

//Planesfaceinward.
mFrustumPlanes[0]=(D3DXPLANE)(col2);//near
mFrustumPlanes[1]=(D3DXPLANE)(col3-col2);//far
mFrustumPlanes[2]=(D3DXPLANE)(col3+col0);//left
mFrustumPlanes[3]=(D3DXPLANE)(col3-col0);//right
mFrustumPlanes[4]=(D3DXPLANE)(col3-col1);//top
mFrustumPlanes[5]=(D3DXPLANE)(col3+col1);//bottom

for(inti=0;i<6;i++)
D3DXPlaneNormalize(&mFrustumPlanes[i],&mFrustumPlanes[i]);
}

其中的数学原理却是比较复杂的，需要相当的图形学基础。

4 Frustum和AABB包围体的碰撞检测

下面是检测Frustum六个平面与AABB包围体碰撞的代码：

boolCamera::isVisible(constAABB&box)const
{
//Testassumesfrustumplanesfaceinward.

D3DXVECTOR3P;
D3DXVECTOR3Q;

//N*Q*P
//|//
//|//
//-----/-----Plane-----/-----Plane
////|
////|
//*P*QN
//
//PQformsdiagonalmostcloselyalignedwithplanenormal.

//Foreachfrustumplane,findtheboxdiagonal(therearefourmain
//diagonalsthatintersecttheboxcenterpoint)thatpointsinthe
//samedirectionasthenormalalongeachaxis(i.e.,thediagonal
//thatismostalignedwiththeplanenormal).Thentestifthebox
//isinfrontoftheplaneornot.
for(inti=0;i<6;++i)
{
//Foreachcoordinateaxisx,y,z...
for(intj=0;j<3;++j)
{
//MakePQpointinthesamedirectionastheplanenormalonthisaxis.
if(mFrustumPlanes[i][j]>=0.0f)
{
P[j]=box.minPt[j];
Q[j]=box.maxPt[j];
}
else
{
P[j]=box.maxPt[j];
Q[j]=box.minPt[j];
}
}

//Ifboxisinnegativehalfspace,itisbehindtheplane,andthus,completely
//outsidethefrustum.NotethatbecausePQpointsroughlyinthedirectionofthe
//planenormal,wecandeducethatifQisoutsidethenPisalsooutside--thuswe
//onlyneedtotestQ.
if(D3DXPlaneDotCoord(&mFrustumPlanes[i],&Q)<0.0f)//outside
returnfalse;
}
returntrue;
}

因为Frustum有六个平面，所以要循环检测六次，只要任何一次AABB包围体是在平面负面的，那么就返回false，表示没有在Frustum内。

这样检测可以不用考虑这些平面并不是无限延伸的，而是当作一般平面来检测，简化了计算。

因为每个平面四面都有被其他平面包围着，如果AABB与该平面在Frustum外相交，那么AABB就会是在其他四个平面任一个平面的负面，所以会在和其他平面检测的时候，检测出来该AABB不在Frustum内。

可以参考我另外一个关于平面和AABB包围体碰撞检测的博客：http://blog.csdn.net/kenden23/article/details/16916327

5 最后就是渲染：

voidTerrain::draw()
{
//Frustumcullsub-grids.
std::list<SubGrid>visibleSubGrids;
for(UINTi=0;i<mSubGrids.size();++i)
{
if(gCamera->isVisible(mSubGrids[i].box))
visibleSubGrids.push_back(mSubGrids[i]);
}

//Sortfront-to-backfromcamera.
visibleSubGrids.sort();

mFX->SetMatrix(mhViewProj,&gCamera->viewProj());
mFX->SetTechnique(mhTech);
UINTnumPasses=0;
mFX->Begin(&numPasses,0);
mFX->BeginPass(0);

for(std::list<SubGrid>::iteratoriter=visibleSubGrids.begin();iter!=visibleSubGrids.end();++iter)
HR(iter->mesh->DrawSubset(0));

mFX->EndPass();
mFX->End();
}

渲染步骤：

1 先检测是否可见，即是否与Frustum相交，相交的放入一个list容器中。

std::list<SubGrid>visibleSubGrids;
for(UINTi=0;i<mSubGrids.size();++i)
{
if(gCamera->isVisible(mSubGrids[i].box))
visibleSubGrids.push_back(mSubGrids[i]);
}

2 按照离镜头的远近排序：

//Sortfront-to-backfromcamera.
visibleSubGrids.sort();

3 最后就是逐个小地图块渲染

for(std::list<SubGrid>::iteratoriter=visibleSubGrids.begin();iter!=visibleSubGrids.end();++iter)
HR(iter->mesh->DrawSubset(0));

其他代码是Shader渲染设置。

6 实现地图分块剔除技术关键步骤总结：

1 地图分块，定义好保存数据的结构体，包含AABB包围体

2 根据投影矩阵，计算Frustum

3 检测Frustum和小地图块的AABB包围体是否碰撞，保存好碰撞的小地图块

4 根据离镜头远近排序可见的（即碰撞的）小地图块，按循序渲染

下面是应用了本技术的效果图：

技术简介：

如果需要渲染一个大型3D地图，由于数据量，需要渲染的东西非常多，所以尤其一些慢一点的机器就会变得非常卡。

如下面这些会造成帧率（FPS）下降的图：

这样的图：

还有这样的魔兽世界的图：

还有这样的图：

上图我是指她的背景图啦，O(∩_∩)O~

到底暴雪是如何让这些场景流畅地渲染的呢？

那就必须想办法提高渲染速度，也就是帧率（FPS）要提高，才能使得游戏流畅。

像魔兽这样大型的游戏具体是用什么技术的，那不敢确定，但是会用到的相关技术会有：

1 地图分块剔除

2 kd树

3 BSP树

4 LOD技术

等等，最后把场景优化到极致，才能创造出伟大的游戏。每一种技术都需要挺长篇幅介绍的，本文就分析第一种技术：地图分块剔除技术(Sub-Grid Culling)

地图分块剔除技术分析

1 3D投影剔除（Frustum Culling）

把一个大地图分隔成由多个小地图实现，那么本来需要调用一次就画成的地图，现在需要多次调用，但是我们可以利用Frustum Culling（3D投影剔除-我觉得比较满意的翻译名词吧）技术优化渲染。

Frustum Culling的思路是：

每一个小块地图，我们计算相对应的AABB包围体；

如果这个AABB和Frustum不相交，那么就不用画这个小块地图。

Frustum是下面的形状：

如下图：大三角形代表Frustum，小方格代表小块地图，灰色小方格代表与Frustum相交，需要渲染，但是白色地带就不与Frustum相交，所以都不需要渲染，那么我们可以看出这就省了很多渲染内容，也就速度大大提高了。

也可以不使用分格和AABB方法进行Frustum Culling：

把所有的组成地图的三角形输入显卡，让显卡自动裁剪不在Frustum中的三角形。但是其实这个裁剪发生在Clipping Stage，就差不多是渲染管道的最后的渲染工作了，那么这些不用渲染你的三角形就会通过大部分渲染管道，如：Vertex Shader，那么就浪费了很多计算呢时间。

使用分格和AABB的方法就可以简单的利用一个AABB相交测试就可以丢弃一个不用渲染的小块地图数据了，效率可以更大地提高。

掌握这个分块的数量也很重要。如下图：

这样就是更加精细的分块了。需要渲染的面积更小，但是相对而言节省的也不多，而精细的分块也需要花费更多的计算时间，如：画基本元几何图形的函数调用次数也更多了，还有AABB相交测试也增多；

所谓过犹不及，要掌握好度很重要。到底分多少个小地图块是合适的，就需要实际分析了。

而且这里的Frustum Culling主要是节省了vertex shading的计算时间，如果一个图形是主要花费在pixel shanding上的话，比如大量的particles需要渲染，那么这种Frustum Culling方法就不会有太大的提速效果。

2 小地图数据结构体：

首先需要定义一个结构体来表示小地图块的数据，如下：

structSubGrid
{
ID3DXMesh*mesh;
AABBbox;

//Forsorting.
booloperator<(constSubGrid&rhs)const;

conststaticintNUM_ROWS=33;
conststaticintNUM_COLS=33;
conststaticintNUM_TRIS=(NUM_ROWS-1)*(NUM_COLS-1)*2;
conststaticintNUM_VERTS=NUM_ROWS*NUM_COLS;
};

主要功能就是这个比较操作符，是根据该小地图块和Camera的距离来比较大小的。把所有的小地图块都按照离Camera的距离由进到远排序，那么就方便由进到远（前到后）的渲染方式渲染。这种方式的渲染可以提高速度，尤其是在渲染管道中pixel shader渲染是瓶颈的时候，当然如果vertex shader是瓶颈，那么就提高不明显。

基本原理就是：

1 更新像素（pixel)的时候，渲染器都进行了depth testing(深度测试），只有在距离镜头进的物体才会被渲染，否则就不渲染。

2 如果排序好的物体，前面渲染的物体都是距离近的，那么后面渲染的物体如果被前面的物体挡住了，那么就根本不需要渲染了。

3 如果不是排序好的话，前面渲染了距离远的物体，那么后面渲染的物体距离镜头更加近，就需要重新更新当前像素，造成重复浪费渲染。

boolTerrain::SubGrid::operator<(constSubGrid&rhs)const
{
D3DXVECTOR3d1=box.center()-gCamera->pos();
D3DXVECTOR3d2=rhs.box.center()-gCamera->pos();
returnD3DXVec3LengthSq(&d1)<D3DXVec3LengthSq(&d2);
}

3 计算出Frustum：

Frustum是从投影矩阵抽出来的。因为Frustum就是由投影矩阵定义的，也可以说两者都在实际上是一致的：

如投影示意图：

Frustum：

其实是概念上不一样，但是实际上一样的东西。不过应用也不一样。

下面是从投影矩阵抽出Frustum的程序：

voidCamera::buildWorldFrustumPlanes()
{
//Note:Extractthefrustumplanesinworldspace.

D3DXMATRIXVP=mView*mProj;

D3DXVECTOR4col0(VP(0,0),VP(1,0),VP(2,0),VP(3,0));
D3DXVECTOR4col1(VP(0,1),VP(1,1),VP(2,1),VP(3,1));
D3DXVECTOR4col2(VP(0,2),VP(1,2),VP(2,2),VP(3,2));
D3DXVECTOR4col3(VP(0,3),VP(1,3),VP(2,3),VP(3,3));

//Planesfaceinward.
mFrustumPlanes[0]=(D3DXPLANE)(col2);//near
mFrustumPlanes[1]=(D3DXPLANE)(col3-col2);//far
mFrustumPlanes[2]=(D3DXPLANE)(col3+col0);//left
mFrustumPlanes[3]=(D3DXPLANE)(col3-col0);//right
mFrustumPlanes[4]=(D3DXPLANE)(col3-col1);//top
mFrustumPlanes[5]=(D3DXPLANE)(col3+col1);//bottom

for(inti=0;i<6;i++)
D3DXPlaneNormalize(&mFrustumPlanes[i],&mFrustumPlanes[i]);
}

其中的数学原理却是比较复杂的，需要相当的图形学基础。

4 Frustum和AABB包围体的碰撞检测

下面是检测Frustum六个平面与AABB包围体碰撞的代码：

boolCamera::isVisible(constAABB&box)const
{
//Testassumesfrustumplanesfaceinward.

D3DXVECTOR3P;
D3DXVECTOR3Q;

//N*Q*P
//|//
//|//
//-----/-----Plane-----/-----Plane
////|
////|
//*P*QN
//
//PQformsdiagonalmostcloselyalignedwithplanenormal.

//Foreachfrustumplane,findtheboxdiagonal(therearefourmain
//diagonalsthatintersecttheboxcenterpoint)thatpointsinthe
//samedirectionasthenormalalongeachaxis(i.e.,thediagonal
//thatismostalignedwiththeplanenormal).Thentestifthebox
//isinfrontoftheplaneornot.
for(inti=0;i<6;++i)
{
//Foreachcoordinateaxisx,y,z...
for(intj=0;j<3;++j)
{
//MakePQpointinthesamedirectionastheplanenormalonthisaxis.
if(mFrustumPlanes[i][j]>=0.0f)
{
P[j]=box.minPt[j];
Q[j]=box.maxPt[j];
}
else
{
P[j]=box.maxPt[j];
Q[j]=box.minPt[j];
}
}

//Ifboxisinnegativehalfspace,itisbehindtheplane,andthus,completely
//outsidethefrustum.NotethatbecausePQpointsroughlyinthedirectionofthe
//planenormal,wecandeducethatifQisoutsidethenPisalsooutside--thuswe
//onlyneedtotestQ.
if(D3DXPlaneDotCoord(&mFrustumPlanes[i],&Q)<0.0f)//outside
returnfalse;
}
returntrue;
}

因为Frustum有六个平面，所以要循环检测六次，只要任何一次AABB包围体是在平面负面的，那么就返回false，表示没有在Frustum内。

这样检测可以不用考虑这些平面并不是无限延伸的，而是当作一般平面来检测，简化了计算。

因为每个平面四面都有被其他平面包围着，如果AABB与该平面在Frustum外相交，那么AABB就会是在其他四个平面任一个平面的负面，所以会在和其他平面检测的时候，检测出来该AABB不在Frustum内。

可以参考我另外一个关于平面和AABB包围体碰撞检测的博客：http://blog.csdn.net/kenden23/article/details/16916327

5 最后就是渲染：

voidTerrain::draw()
{
//Frustumcullsub-grids.
std::list<SubGrid>visibleSubGrids;
for(UINTi=0;i<mSubGrids.size();++i)
{
if(gCamera->isVisible(mSubGrids[i].box))
visibleSubGrids.push_back(mSubGrids[i]);
}

//Sortfront-to-backfromcamera.
visibleSubGrids.sort();

mFX->SetMatrix(mhViewProj,&gCamera->viewProj());
mFX->SetTechnique(mhTech);
UINTnumPasses=0;
mFX->Begin(&numPasses,0);
mFX->BeginPass(0);

for(std::list<SubGrid>::iteratoriter=visibleSubGrids.begin();iter!=visibleSubGrids.end();++iter)
HR(iter->mesh->DrawSubset(0));

mFX->EndPass();
mFX->End();
}

渲染步骤：

1 先检测是否可见，即是否与Frustum相交，相交的放入一个list容器中。

std::list<SubGrid>visibleSubGrids;
for(UINTi=0;i<mSubGrids.size();++i)
{
if(gCamera->isVisible(mSubGrids[i].box))
visibleSubGrids.push_back(mSubGrids[i]);
}

2 按照离镜头的远近排序：

//Sortfront-to-backfromcamera.
visibleSubGrids.sort();

3 最后就是逐个小地图块渲染

for(std::list<SubGrid>::iteratoriter=visibleSubGrids.begin();iter!=visibleSubGrids.end();++iter)
HR(iter->mesh->DrawSubset(0));

其他代码是Shader渲染设置。

6 实现地图分块剔除技术关键步骤总结：

1 地图分块，定义好保存数据的结构体，包含AABB包围体

2 根据投影矩阵，计算Frustum

3 检测Frustum和小地图块的AABB包围体是否碰撞，保存好碰撞的小地图块

4 根据离镜头远近排序可见的（即碰撞的）小地图块，按循序渲染

下面是应用了本技术的效果图：