前腐后继 发表于 2006-12-8 18:57:00

[转帖] 自己研究的一个场景物体剔除方法

<br/><br/>场景剔除方法<br/>首先将场景划分成N*M个等大的矩形区域,推荐正方形,每个区域有一个链表保存这个区域 <p></p><p>上的所有物体,然后用一个N*M的二维数组保存这些指针。进行视锥剔除的时候,首先根据</p><p>摄象机的参数得到一个近似的三角形(三角形指的是可视区域在XZ平面上的投影区域),算</p><p>出三角形三个顶点的坐标,然后利用三个顶点坐标可以算出在这个三角形内的,刚才划分的</p><p>区域,然后将这些区域的链表拼接就得到了所有可见物体。<br/>基于这个方法,区域之间有物体跨越的话,可以很方便的对这两个区域链表处理,保证剔除</p><p>不出错<br/>原理简单,下面是代码实现</p><p>bool&nbsp;IsInTriangle2D(D3DXVECTOR2&nbsp;p1,D3DXVECTOR2&nbsp;p2,D3DXVECTOR2&nbsp;p3,D3DXVECTOR2&nbsp;</p><p>p,float&nbsp;Precision)//判断点p是否在点p1,p2,p3的三角形内,Precision是允许的误差范围</p><p>,值越大,表示允许超出三角形的距离越大<br/>{<br/>double&nbsp;a=p2.x-p1.x,b=p3.x-p1.x,c=p2.y-p1.y,d=p3.y-p1.y;<br/>double&nbsp;u=(a*(p.y-p1.y)/c+p1.x-p.x)/(a*d/c-b);<br/>double&nbsp;v=(b*(p.y-p1.y)/d+p1.x-p.x)/(b*c/d-a);<br/>if(u&gt;=-Precision&amp;&amp;v&gt;=-Precision&amp;&amp;u+v&lt;=1+2*Precision)return&nbsp;true;<br/>else&nbsp;<br/>return&nbsp;false;<br/>}<br/>void&nbsp;CCuller::ViewCull()<br/>{<br/>if(!m_isCull)return;//是否打开剔除<br/>PObjectList*&nbsp;pNode=m_pCulledObject;//保存剔除后的物体<br/>if(pNode!=NULL)//每次剔除的时候先删除上次剔除保留的链表<br/>{<br/>while(pNode-&gt;m_pNext!=NULL)<br/>{<br/>pNode=pNode-&gt;m_pNext;<br/>delete&nbsp;m_pCulledObject;<br/>m_pCulledObject=pNode;<br/>}<br/>delete&nbsp;m_pCulledObject;<br/>m_pCulledObject=NULL;<br/>}<br/>float&nbsp;Distance=m_pCamera-&gt;GetDistance();//获得摄象机的观察距离,求近似三</p><p>角形<br/>float&nbsp;Angle=m_pCamera-&gt;GetAngleH()-90;//这个不用管,只是我自己游戏中的一</p><p>个角度转换问题<br/>static&nbsp;D3DXVECTOR2&nbsp;p1,p2,p3;<br/>int&nbsp;StartX,StartZ,EndX,EndZ;<br/>//根据摄象机算出可视范围近似三角形的三个顶点<br/>p1.x=m_pCamera-&gt;GetPosition().x/CULL_RECT_WIDTH;//除以区域长宽的目的是将</p><p>一个区域作为一个点来看<br/>p1.y=m_pCamera-&gt;GetPosition().z/CULL_RECT_LONG;//可以理解我们划分的区域</p><p>为一个像素,<br/>p2.x=cos(AtoR(Angle+22.5))*Distance/CULL_RECT_WIDTH+p1.x;//观察范围的三</p><p>角形也就是以这些像素表示的三角形了<br/>p2.y=sin(AtoR(Angle+22.5))*Distance/CULL_RECT_LONG+p1.y;//这个不理解也不</p><p>要紧,这些不是关键<br/>p3.x=cos(AtoR(Angle-22.5))*Distance/CULL_RECT_WIDTH+p1.x;<br/>p3.y=sin(AtoR(Angle-22.5))*Distance/CULL_RECT_LONG+p1.y;<br/>//根据p1,p2,p3算出区域数组下标的范围<br/>if(p1.x&lt;p2.x)<br/>{<br/>StartX=p1.x;<br/>EndX=p2.x;<br/>if(StartX&gt;p3.x)<br/>{<br/>StartX=p3.x;<br/>}<br/>else<br/>{<br/>if(EndX&lt;p3.x)<br/>{<br/>EndX=p3.x;<br/>}<br/>}<br/>}<br/>else<br/>{<br/>StartX=p2.x;<br/>EndX=p1.x;<br/>if(StartX&gt;p3.x)<br/>{<br/>StartX=p3.x;<br/>}<br/>else<br/>{<br/>if(EndX&lt;p3.x)<br/>{<br/>EndX=p3.x;<br/>}<br/>}<br/>}<br/>if(p1.y&lt;p2.y)<br/>{<br/>StartZ=p1.y;<br/>EndZ=p2.y;<br/>if(StartZ&gt;p3.y)<br/>{<br/>StartZ=p3.y;<br/>}<br/>else<br/>{<br/>if(EndZ&lt;p3.y)<br/>{<br/>EndZ=p3.y;<br/>}<br/>}<br/>}<br/>else<br/>{<br/>StartZ=p2.y;<br/>EndZ=p1.y;<br/>if(StartZ&gt;p3.y)<br/>{<br/>StartZ=p3.y;<br/>}<br/>else<br/>{<br/>if(EndZ&lt;p3.y)<br/>{<br/>EndZ=p3.y;<br/>}<br/>}<br/>}<br/>//确保范围没超出地图,确保观察范围超出地图范围不出错<br/>if(StartX&lt;0)<br/>{<br/>StartX=0;<br/>}<br/>if(EndX&gt;CULL_SIZE_WIDTH)<br/>{<br/>EndX=CULL_SIZE_WIDTH;<br/>}<br/><br/>if(StartZ&lt;0)<br/>{<br/>StartZ=0;<br/>}<br/>if(EndZ&gt;CULL_SIZE_LONG)<br/>{<br/>EndZ=CULL_SIZE_LONG;<br/>}<br/>for(int&nbsp;i=StartZ;i&lt;EndZ;i++)<br/>{<br/>for(int&nbsp;j=StartX;j&lt;EndX;j++)<br/>{<br/>if(Area-&gt;m_pObject!=NULL)<br/>{<br/>D3DXVECTOR2&nbsp;p,pp1,pp2,pp3;<br/>p.x=j;<br/>p.y=i;<br/>pp1=p-p1;<br/>pp2=p-p2;<br/>pp3=p-p3;<br/>if(IsInTriangle2D(p1,p2,p3,p,0.038))////判断该点</p><p>是否在三角形中,小于0为在三角形中,大于0外不在三角形中<br/>{<br/>if(m_pCulledObject==NULL)<br/>{<br/>m_pCulledObject=new&nbsp;</p><p>PObjectList();<br/></p><p>m_pCulledObject-&gt;m_pObjectList=Area;//这个数组就是保存区域链表的数组Area就保存的第0,0区域的链表<br/>pNode=m_pCulledObject;<br/>}<br/>else<br/>{<br/>pNode-&gt;m_pNext=new&nbsp;</p><p>PObjectList();<br/>pNode=pNode-&gt;m_pNext;<br/>pNode-&gt;m_pObjectList=Area;<br/>}<br/>}<br/>}<br/><br/>}<br/>}<br/>}<br/><br/><br/><img src="http://images.gameres.com/bbs/style/snow/image/attachment.gif" border="0" alt=""/>本主题包含附件: <img src="http://images.gameres.com/bbs/image/fileicon/jpg.gif" border="0" alt=""/><font color="#9c0000">sf_2005416233830.jpg</font> (27844bytes)<br/><br/><img src="http://bbs.gameres.com/upload/sf_2005416233830.jpg" border="0" alt=""/></p><p>忘了说了,AtoR()是自定义的将角度转成弧度的函数<br/></p><div align="right"><img src="http://images.gameres.com/bbs/style/snow/image/ok.gif" border="0" alt=""/>郑群 2005-4-16 23:43:19</div>
页: [1]
查看完整版本: [转帖] 自己研究的一个场景物体剔除方法