动态四叉树LOD地形的跳跃(poping)问题处理算法

动态四叉树LOD地形的跳跃（poping）问题处理算法作者：宋睿QQ:59465140在我工作中应用到地形跳跃（poping）消除处理，在网上又看到了程东哲先生的的文章《四叉树LOD无限更新》，程先生在文章中提出解决跳跃（poping）思路并给出伪代码，我在我程序中加入程先生跳跃（poping）消除思路，发现没有解决跳跃（poping）问题，并产生了新的裂缝，我思考后，并查阅了其它资料，提出了自己的改进算法，，在这里不对程先生《四叉树LOD无限更新》，文章进行评论，程先生在《地形制作全攻略》四叉树具体实现算法是非常不错。本文的跳跃（poping）处理算法，也是基于《focuson3dterrainprogramming》和《地形制作全攻略》上四叉树1LOD算法。我的跳跃（poping）消除算法，主要参考了Yuanchenzhu的文章《real-timecontinuouslevel—of—DetailterrainRenderwithNestedSplittingSpace》，同时为了照顾第一次学习poping处理的读者，保持文章的连贯性，可读性，我全面阐述一下地形跳跃（poping）问题。1地形跳跃（poping）产生原因在动态四叉树LOD系统中，由于试点移动使四叉树层次突然变换，使顶点位置发生变化，导致顶点在地形中增加和减少，引起的这种结果，被称为"顶点跳跃（vertexpoping）",当跳跃距离过长，这就引起了地形不真实感，就必须解决这种现象。B3粉色闘團懋产牛了POPTNCB3粉色闘團懋产牛了POPTNC由于突然新增加顶点所以产生了POPING图12处理技术好的处理方法，就是随着试点移动，使定点平滑逐渐改变到在层次构架中新位置使定点跳跃(ervertexpoping)得以隐藏，这种处理被称为定点变形(ervertexMorphing)处理。我们假定当前视点在SO点，当视点移动到新点，我们假定这点是S1,那么S1和SO之间的距离，我定为B，B=S1-SO。如图2间存在的差值，产生了顶点变形，由于顶点V0非平滑过度到VI,就发生了定点跳跃(vertexpoping)结果，为了能够平滑过渡，那么我们就采用线性插值(由于地形是线性的，采用线性插值就可以了，当然也可以其它插值，在文章《continuousLODTerrianMeshingUsingAdaptiveQuadtrees》提出双线插值，大家可以找来参考一下。)，产生一个平稳过渡位置值VP.VP=VO+t(V1-VO).3)插值参数确定。在四叉树LOD地形算法中，我们知道只需要对四个进行插值处理(参看程东哲的《地形全攻略》或《佛foucuson3dterrainprogramming》)如图3中2、4、6、8点。我首先要建立以旧顶点位置存储矩阵，在这里命名为oldVMatrix，用于存储2、4、6、8点旧顶点位置，以及顶点1与顶点2之间中间点，顶点2与顶点23之间中间点，顶点3与顶点4之间中间点，顶点4与顶点5之间中间点，顶点5与顶点6之间中间点，顶点6与顶点7之间中间点，顶点7与顶点8之间中间点，顶点8与顶点1之间中间点的顶点位当然前面提到这些点，存在有增加到地形和不增加到地形两种可能性，但是在发生层次突变，这些点被增加到地形中，这个oldVMatrix中的值就是V0,而V1就是从实际位置矩阵中得到的值。我以顶点1、2、3为例，来说明旧顶点位置的求值，如果2点被增加到地形中，那就存储2点位置值，如果2点没有被增加到地形中，oldVMatrix矩阵中就存储值等于（vl+V3）/2,也就是V1和V3位置相加平均值，然后求1与2之间的存储值为（vl+v2）/2,2与3之间存储值为（V2+V3）/2,以后依此类推，不多赘述。4）插值因子确定t=clamp(f(s,v)/B,0,1)f(s,v)=L-r;L=sqrt((s.x-v.x)*(s.x-v.x)+(s.y-v.y)*(s.y-v.y)+(2(s.z-v.z)*(2(s.z-v.z)))

r=d*K*Max(C&H,1);视点S到顶点V的距离L=sqrt((s.x-v.x)*(s.x-v.x)+(s.y-v.y)*(s.y-v.y)+(2(s.z-v.z)*(2(s.z-v.z)))，我们可以近似的简化为L=(s.x-v.x)+(s.y-v.y)+(2(s.z-v.z)),为什么要采用2倍的(s.z—v.z),因为在这z坐标方面试点到定点是一条斜线(看图4),为了简化我们的计算公式，我就近当视点移动后，的d、l都要发生变化，我们正好利用el的变化与试点距离B之间比值，用来做为插值因子，能很好做平滑过度。5算法实现5.1插值因子获得为了读者更好理解我的算法，我在这里给出伪代码实现。voidUpDateLODNode(intiX,intiZ,intiEdgeLength)//当前节点下标和边{if(iEdgeLength>3){VSAabb*pAabb=GetAABBMatrix(iX,iZ);;if(Cull(平截头,6) ==true)//剪裁掉不可见的。{SetLODMatrix(iX,iZ,2);}else{floatfViewDistance,f;intiChildOffset;intiChildEdgeLength;intiBlend;//计算顶点到视点距离fViewDistance=(float)(fabs(m_fViewX-m_pVertex[iX+iZ*m_nSize].x)+fabs(m_fViewY-m_pVertex[iX+iZ*m_nSize].y)+fabs(m_fViewZ-m_pVertex[iX+iZ*m_nSize].z));f=fViewDistance/TMart;if(f<1.0f)iBlend=1;else{iBlend=0；}SetLODMatrix(iX,iZ,iBlend);iChildOffset=((iEdgeLength-1)>>2);iChildEdgeLength=(iEdgeLength+1)>>1;if(iBlend==1){//lowerleftUpDateLODNode(iX-iChildOffset,iZ-iChildOffset,iChildEdgeLength);//lowerrightUpDateLODNode(iX+iChildOffset,iZ-iChildOffset,iChildEdgeLength);//upperleftUpDateLODNode(iX-iChildOffset,iZ+iChildOffset,iChildEdgeLength);//upperrightUpDateLODNode(iX+iChildOffset,iZ+iChildOffset,iChildEdgeLength);}else{//计算插值因子tMatrix[ix,iz]二插值因子；}//ifBlend}//ifCUll}else//这里做了更改{SetLODMatrix(iX,iZ,0);}}5.2处理最终渲染。以顶点2为例//处理poping插值 if(oldVMatrix,[getmatrixindex(iX,iZ-iedgeoffset)]!=0){Vertex.y=oldVMatrix,[iX,iZ-iedgeoffset)]*(1-t)+Vertex.y*t;}在渲染函数中加如入一个布尔变量如果顶点2填加布尔变量为正，不增加为负if(布尔变量=七rue){oldVMatrix,[iX,iZ-iedgeoffset]=Vertex.y;}elseoldVMatrix,[iX,iZ-iedgeoffset]=(Vertex1.y+Vertex3.y)/2;}if(iedgelength>3){oldVMatrix[iX-iedgeoffset/2,iZ-