動態(tài)四叉樹LOD地形的跳躍(poping)問題處理算法

動態(tài)四叉樹LOD地形的跳躍（poping）問題處理算法作者：宋睿QQ:59465140在我工作中應(yīng)用到地形跳躍（poping）消除處理，在網(wǎng)上又看到了程東哲先生的的文章《四叉樹LOD無限更新》，程先生在文章中提出解決跳躍（poping）思路并給出偽代碼，我在我程序中加入程先生跳躍（poping）消除思路，發(fā)現(xiàn)沒有解決跳躍（poping）問題，并產(chǎn)生了新的裂縫，我思考后，并查閱了其它資料，提出了自己的改進(jìn)算法，，在這里不對程先生《四叉樹LOD無限更新》，文章進(jìn)行評論，程先生在《地形制作全攻略》四叉樹具體實(shí)現(xiàn)算法是非常不錯。本文的跳躍（poping）處理算法，也是基于《focuson3dterrainprogramming》和《地形制作全攻略》上四叉樹1LOD算法。我的跳躍（poping）消除算法，主要參考了Yuanchenzhu的文章《real-timecontinuouslevel—of—DetailterrainRenderwithNestedSplittingSpace》，同時為了照顧第一次學(xué)習(xí)poping處理的讀者，保持文章的連貫性，可讀性，我全面闡述一下地形跳躍（poping）問題。1地形跳躍（poping）產(chǎn)生原因在動態(tài)四叉樹LOD系統(tǒng)中，由于試點(diǎn)移動使四叉樹層次突然變換，使頂點(diǎn)位置發(fā)生變化，導(dǎo)致頂點(diǎn)在地形中增加和減少，引起的這種結(jié)果，被稱為"頂點(diǎn)跳躍（vertexpoping）",當(dāng)跳躍距離過長，這就引起了地形不真實(shí)感，就必須解決這種現(xiàn)象。B3粉色闘團(tuán)懋產(chǎn)牛了POPTNCB3粉色闘團(tuán)懋產(chǎn)牛了POPTNC由于突然新增加頂點(diǎn)所以產(chǎn)生了POPING圖12處理技術(shù)好的處理方法，就是隨著試點(diǎn)移動，使定點(diǎn)平滑逐漸改變到在層次構(gòu)架中新位置使定點(diǎn)跳躍(ervertexpoping)得以隱藏，這種處理被稱為定點(diǎn)變形(ervertexMorphing)處理。我們假定當(dāng)前視點(diǎn)在SO點(diǎn)，當(dāng)視點(diǎn)移動到新點(diǎn)，我們假定這點(diǎn)是S1,那么S1和SO之間的距離，我定為B，B=S1-SO。如圖2間存在的差值，產(chǎn)生了頂點(diǎn)變形，由于頂點(diǎn)V0非平滑過度到VI,就發(fā)生了定點(diǎn)跳躍(vertexpoping)結(jié)果，為了能夠平滑過渡，那么我們就采用線性插值(由于地形是線性的，采用線性插值就可以了，當(dāng)然也可以其它插值，在文章《continuousLODTerrianMeshingUsingAdaptiveQuadtrees》提出雙線插值，大家可以找來參考一下。)，產(chǎn)生一個平穩(wěn)過渡位置值VP.VP=VO+t(V1-VO).3)插值參數(shù)確定。在四叉樹LOD地形算法中，我們知道只需要對四個進(jìn)行插值處理(參看程東哲的《地形全攻略》或《佛foucuson3dterrainprogramming》)如圖3中2、4、6、8點(diǎn)。我首先要建立以舊頂點(diǎn)位置存儲矩陣，在這里命名為oldVMatrix，用于存儲2、4、6、8點(diǎn)舊頂點(diǎn)位置，以及頂點(diǎn)1與頂點(diǎn)2之間中間點(diǎn)，頂點(diǎn)2與頂點(diǎn)23之間中間點(diǎn)，頂點(diǎn)3與頂點(diǎn)4之間中間點(diǎn)，頂點(diǎn)4與頂點(diǎn)5之間中間點(diǎn)，頂點(diǎn)5與頂點(diǎn)6之間中間點(diǎn)，頂點(diǎn)6與頂點(diǎn)7之間中間點(diǎn)，頂點(diǎn)7與頂點(diǎn)8之間中間點(diǎn)，頂點(diǎn)8與頂點(diǎn)1之間中間點(diǎn)的頂點(diǎn)位當(dāng)然前面提到這些點(diǎn)，存在有增加到地形和不增加到地形兩種可能性，但是在發(fā)生層次突變，這些點(diǎn)被增加到地形中，這個oldVMatrix中的值就是V0,而V1就是從實(shí)際位置矩陣中得到的值。我以頂點(diǎn)1、2、3為例，來說明舊頂點(diǎn)位置的求值，如果2點(diǎn)被增加到地形中，那就存儲2點(diǎn)位置值，如果2點(diǎn)沒有被增加到地形中，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);視點(diǎn)S到頂點(diǎn)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坐標(biāo)方面試點(diǎn)到定點(diǎn)是一條斜線(看圖4),為了簡化我們的計算公式，我就近當(dāng)視點(diǎn)移動后，的d、l都要發(fā)生變化，我們正好利用el的變化與試點(diǎn)距離B之間比值，用來做為插值因子，能很好做平滑過度。5算法實(shí)現(xiàn)5.1插值因子獲得為了讀者更好理解我的算法，我在這里給出偽代碼實(shí)現(xiàn)。voidUpDateLODNode(intiX,intiZ,intiEdgeLength)//當(dāng)前節(jié)點(diǎn)下標(biāo)和邊{if(iEdgeLength>3){VSAabb*pAabb=GetAABBMatrix(iX,iZ);;if(Cull(平截頭,6) ==true)//剪裁掉不可見的。{SetLODMatrix(iX,iZ,2);}else{floatfViewDistance,f;intiChildOffset;intiChildEdgeLength;intiBlend;//計算頂點(diǎn)到視點(diǎn)距離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處理最終渲染。以頂點(diǎn)2為例//處理poping插值 if(oldVMatrix,[getmatrixindex(iX,iZ-iedgeoffset)]!=0){Vertex.y=oldVMatrix,[iX,iZ-iedgeoffset)]*(1-t)+Vertex.y*t;}在渲染函數(shù)中加如入一個布爾變量如果頂點(diǎn)2填加布爾變量為正，不增加為負(fù)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-