自己研究的一个场景物体剔除方法|游戏开发|中国IT实验室

自己研究的一个场景物体剔除方法

来源：ChinaITLab 收集整理　作者：　时间：2005-4-22

　　场景剔除方法
　　
　　首先将场景划分成N*M个等大的矩形区域，推荐正方形，每个区域有一个链表保存这个区域上的所有物体，然后用一个N*M的二维数组保存这些指针。进行视锥剔除的时候，首先根据摄象机的参数得到一个近似的三角形（三角形指的是可视区域在XZ平面上的投影区域），算出三角形三个顶点的坐标，然后利用三个顶点坐标可以算出在这个三角形内的，刚才划分的区域，然后将这些区域的链表拼接就得到了所有可见物体。
　　
　　基于这个方法，区域之间有物体跨越的话，可以很方便的对这两个区域链表处理，保证剔除不出错。
　　
　　原理简单，下面是代码实现
　　
　　bool IsInTriangle2D(D3DXVECTOR2 p1,D3DXVECTOR2 p2,D3DXVECTOR2 p3,D3DXVECTOR2 p,float Precision)//判断点p是否在点p1,p2,p3的三角形内，Precision是允许的误差范围，值越大，表示允许超出三角形的距离越大
　　{
　　double a=p2.x-p1.x,b=p3.x-p1.x,c=p2.y-p1.y,d=p3.y-p1.y;
　　double u=(a*(p.y-p1.y)/c+p1.x-p.x)/(a*d/c-b);
　　double v=(b*(p.y-p1.y)/d+p1.x-p.x)/(b*c/d-a);
　　if(u>=-Precision&&v>=-Precision&&u+v<=1+2*Precision)return true;
　　else
　　return false;
　　}
　　
　　void CCuller::ViewCull()
　　{
　　if(!m_isCull)return;//是否打开剔除
　　PObjectList* pNode=m_pCulledObject;//保存剔除后的物体
　　if(pNode!=NULL)//每次剔除的时候先删除上次剔除保留的链表
　　{
　　while(pNode->m_pNext!=NULL)
　　{
　　pNode=pNode->m_pNext;
　　delete m_pCulledObject;
　　m_pCulledObject=pNode;
　　}
　　delete m_pCulledObject;
　　m_pCulledObject=NULL;
　　}
　　float Distance=m_pCamera->GetDistance();//获得摄象机的观察距离，求近似三角形
　　float Angle=m_pCamera->GetAngleH()-90;//这个不用管，只是我自己游戏中的一个角度转换问题
　　static D3DXVECTOR2 p1,p2,p3;
　　int StartX,StartZ,EndX,EndZ;
　　
　　//根据摄象机算出可视范围近似三角形的三个顶点
　　p1.x=m_pCamera->GetPosition().x/CULL_RECT_WIDTH;//除以区域长宽的目的是将一个区域作为一个点来看
　　p1.y=m_pCamera->GetPosition().z/CULL_RECT_LONG;//可以理解我们划分的区域为一个像素，
　　p2.x=cos(AtoR(Angle+22.5))*Distance/CULL_RECT_WIDTH+p1.x;//观察范围的三角形也就是以这些像素表示的三角形了
　　p2.y=sin(AtoR(Angle+22.5))*Distance/CULL_RECT_LONG+p1.y;//这个不理解也不要紧，这些不是关键
　　p3.x=cos(AtoR(Angle-22.5))*Distance/CULL_RECT_WIDTH+p1.x;
　　p3.y=sin(AtoR(Angle-22.5))*Distance/CULL_RECT_LONG+p1.y;
　　//根据p1,p2,p3算出区域数组下标的范围
　　if(p1.x　　{
　　StartX=p1.x;
　　EndX=p2.x;
　　if(StartX>p3.x)
　　{
　　StartX=p3.x;
　　}
　　else
　　{
　　if(EndX　　{
　　EndX=p3.x;
　　}
　　}
　　}
　　else
　　{
　　StartX=p2.x;
　　EndX=p1.x;
　　if(StartX>p3.x)
　　{
　　StartX=p3.x;
　　}
　　else
　　{
　　if(EndX　　{
　　EndX=p3.x;
　　}
　　}
　　}
　　if(p1.y　　{
　　StartZ=p1.y;
　　EndZ=p2.y;
　　if(StartZ>p3.y)
　　{
　　StartZ=p3.y;
　　}
　　else
　　{
　　if(EndZ　　{
　　EndZ=p3.y;
　　}
　　}
　　}
　　else
　　{
　　StartZ=p2.y;
　　EndZ=p1.y;
　　if(StartZ>p3.y)
　　{
　　StartZ=p3.y;
　　}
　　else
　　{
　　if(EndZ　　{
　　EndZ=p3.y;
　　}
　　}
　　}
　　
　　//确保范围没超出地图，确保观察范围超出地图范围不出错
　　if(StartX<0)
　　{
　　StartX=0;
　　}
　　if(EndX>CULL_SIZE_WIDTH)
　　{
　　EndX=CULL_SIZE_WIDTH;
　　}
　　
　　if(StartZ<0)
　　{
　　StartZ=0;
　　}
　　if(EndZ>CULL_SIZE_LONG)
　　{
　　EndZ=CULL_SIZE_LONG;
　　}
　　for(int i=StartZ;i　　{
　　for(int j=StartX;j　　{
　　if(Area[i][j]->m_pObject!=NULL)
　　{
　　D3DXVECTOR2 p,pp1,pp2,pp3;
　　p.x=j;
　　p.y=i;
　　pp1=p-p1;
　　pp2=p-p2;
　　pp3=p-p3;
　　if(IsInTriangle2D(p1,p2,p3,p,0.038))////判断该点是否在三角形中，小于0为在三角形中，大于0外不在三角形中
　　{
　　if(m_pCulledObject==NULL)
　　{
　　m_pCulledObject=new PObjectList();
　　
　　m_pCulledObject->m_pObjectList=Area[i][j];//这个数组就是保存区域链表的数组Area[0][0]就保存的第0,0区域的链表
　　pNode=m_pCulledObject;
　　}
　　else
　　{
　　pNode->m_pNext=new PObjectList();
　　pNode=pNode->m_pNext;
　　pNode->m_pObjectList=Area[i][j];
　　}
　　}
　　}
　　
　　}
　　}
　　}
　　