【文章內容簡介】 ans)可以看作是三角帶的一種退化形式，只是其中所有的三角形都共享一個公共頂點。：　　V0，V1，V2，V3，V4五個頂點構成了表示三個三角形的三角形帶。注意描述三角形帶時，頂點的順序很重要，因為是遵循一定連接規(guī)則(順時針或逆時針)的。在OpenGL中生成最右方的三角形帶的代碼如下：　　 LOD地形網(wǎng)格簡化算法的基本思想及意義　　所謂地形網(wǎng)格的簡化是指通過算法減少提交到顯卡的頂點，以減少每幀同屏渲染的三角形數(shù)量，借以提高渲染速度?！　〖毠?jié)層次(LOD，levels of Details)技術是一種符合人視覺特性的網(wǎng)格簡化技術。我們知道，當場景中的物體離觀察者很遠的時候，它們經(jīng)過觀察、投影變換后在屏幕上往往只是幾個像素甚至是一個象素。我們完全沒有必要為這樣的物體去繪制它的全部細節(jié)，可以適當?shù)暮喜⒁恍┤切味粨p失畫面的視覺效果。對于一般的應用，我們通常會為同一個物體建立幾個不同細節(jié)層度的模型。這樣的技術應用在地形渲染中，也稱之為多分辨率地形(Multi—Resolution Terrain)。下圖就是一個多分辨率地形網(wǎng)格：　　在開發(fā)3D游戲時也有不采用基于LOD的地形網(wǎng)格簡化算法的做法。典型的游戲有韓國游戲公司開發(fā)的著名3D網(wǎng)游《奇跡》，每個Tile場景地形它用257257的高度圖構成，采用靜態(tài)載入場景數(shù)據(jù)的方案同樣產生出了美妙的場景。對于這么小的場景，當然沒有必要做地形網(wǎng)格的簡化，現(xiàn)在的一般顯卡足以能夠應付。之所以他能成功應用這種方式，是因為在設計場景時限制了地形的高低起伏，使地形趨于簡單，縮放標尺取得很大，同時用紋理和光照貼圖來彌補地形本質上的單調。另外，如果運用基于外存的動態(tài)數(shù)據(jù)載入算法，理論上也可以不用基于LOD的地形網(wǎng)格簡化算法。　　隨著3D游戲的成熟，玩家需要有更真實的體驗，因此地形變得更加復雜，場景變得更加巨大，地形的繪制需要很多數(shù)據(jù)參與，對系統(tǒng)資源消耗巨大。如果一點也不進行地形網(wǎng)格簡化，試想一個1025 X1025的場景就將生成2M個三角形，渲染大的場景時顯卡的處理能力很難跟上。在顯卡的數(shù)據(jù)吞吐能力有限的情況下，游戲場景渲染中普遍基于LOD的思想，減小繪制多邊形數(shù)目。它能在犧牲適量CPU資源的前提下大大減輕圖形卡的數(shù)據(jù)負載，使CPU與GPU之間沒有明顯的瓶頸，從而達到實時渲染大地形的目的?！　』贚OD的地形網(wǎng)格簡化算法分為動態(tài)LOD和靜態(tài)LOD算法。動態(tài)LOD算法是在每幀渲染之前都經(jīng)過計算重新確定送入顯卡的頂點。所有的頂點數(shù)據(jù)全部需要參與運算。ROAM算法和基于四叉樹的動態(tài)LOD算法都屬于此類，GeoMipMap算法則是靜態(tài)LOD算法的代表?！?ROAM算法　　1997年，Duchaineau提出了實時優(yōu)化適應性網(wǎng)格(ROAM，RealtimeOptimalAdaptive Meshes)算法瞳1，它是一種基于規(guī)則網(wǎng)格的連續(xù)LOD網(wǎng)格構造算法。其基本思想是在對地形進行三維顯示時，依據(jù)視點的位置和視線的方向等多種因素，對表示地形表面的三角形圖元進行一系列基于三角形二叉剖分分裂與合并，最終形成和原始表面近似且無縫無疊的簡化連續(xù)三角形表面?！　OAM的基礎是等腰直角三角形的一個性質。等腰直角三角形可以從直角頂點到斜邊引一條垂線，這條垂線把這個三角形分成了兩個小的等腰直角三角形，并無限制的遞歸分下去。而從另一個角度來看，這正好構成了一個二叉樹，每個三角形都是把它分開而生成的兩個小三角形的父母(parent)。根據(jù)這條性質，只要計算出哪些三角形需要被分割開、哪些三角形需要合并成為自己的父母，就可以做到控制LOD(分開就是增加LOD，合并就是減少LOD)?！?層三角形二叉樹和相應的層次結構?！　‘敯岩粋€三角形分成兩個的時候，會在斜邊上增加一個頂點，是由斜邊的兩個端點插值求得。不過高度卻不能插值。因為高度是按照相應的地圖數(shù)據(jù)來的(比如heightmap)。所以，就存在一個插值以后的高度和實際高度不匹配的問題(會產生裂縫)。為了解決這個問題，就需要調整Y軸上的值來升高或者降低這個頂點，這個頂點高度的調整距離就稱為誤差量。　　要確定一個三角形是否要被分割，就要看它是否能精確的描述地形的高度數(shù)據(jù)。如果可以的話，自然就不用分割了，多邊形越少越好。如果不能的話，就細化它，也就是分割掉，直到所有的小三角形都能夠精確表示地形數(shù)據(jù)為止。　　通過不停的分割，三角形越來越小，每個三角形在高度圖上所覆蓋的面積也越來越小。那么，總會分割到足夠小，使得三角形的面積和高度圖上一個點的面積之比為l：l，分到這里就不用再分了。通過檢查所有孩子的誤差量，我們就找到了一個描述三角形是否需要分割的精確方法。當遞歸的遍歷這棵樹以后，就能夠找到這棵樹里面的最大誤差量，就是所謂的largest error metri c。這個最大誤差量如果是O那就是完全符合實際高度了，這個值越大，就越不符合。　　用每個三角形的誤差量和鏡頭到該三角形的距離比較，用以判斷是否一個三角形需要分裂。用以給每個三角形做測試的值是人為定義的，這個值又叫錯誤容忍度(error metric tolerated)。通過錯誤容忍度對每個三角形做測試，小于這個容忍度的三角形就被留下(不分裂)，大于這個的就被分裂掉，然后再分別對被分裂的三角形的兩個兒子做分裂。如果加入了視角依賴(view—dependence)的話，就需要通過鏡頭到三角形的距離來調整這個容忍度了。鏡頭越遠，容忍度就越大，而鏡頭越近，容忍度就越小?！　〈怂惴ǖ膬?yōu)點在于：可動態(tài)的改變每個網(wǎng)格；可在渲染時控制每個網(wǎng)格的生成與否；可以和紋理坐標很好的結合在一起；可控制地形三角形的最大數(shù)目；可以根據(jù)坡度的不同自動調整LOD的細節(jié)程度，也就是說在地形坡度大的地方LOD細節(jié)程度高，在地形坡度小的地方LOD細節(jié)程度低；可以根據(jù)到觀察點的距離自動調整LOD的細節(jié)程度，也就是說在離觀察點近的地方LOD細節(jié)程度高，在離觀察點遠的地方LOD細節(jié)程度低?！　　　　　〈怂惴ㄊ荓indstrom提出的n劓，他用了一個叫四叉樹(Ouad Tree)的結構來描述地形，先把可視范圍內的地形分割成四等份矩形子塊，依靠計算判定因子檢測四個子塊，如果檢查到某個子塊的網(wǎng)格精度達到所要求的繪制精度就不需要往下再分割；否則就把此子塊再分割成四等份更小的子塊，依次遞歸分割下去，直到所有子塊中的矩形網(wǎng)格都達到渲染精度?！　　　　駥形裂縫的處理　　由于不同層次間的采樣間隔不同，在可視化過程中會出現(xiàn)縫隙，上方矩形具有較高的分辨率，而下方矩形的分辨率較低，這使得矩形間的連接處出現(xiàn)了末被覆蓋的區(qū)域(陰影處)，從而在地形繪制時就產生了“裂縫”。　　，在分辨率低的四叉樹區(qū)域節(jié)點上，四個方向均可能出現(xiàn)縫隙，所以必須依次用自身節(jié)點的分辨率大小比較四個方向上臨近節(jié)點的分辨率大小。如果前者小于后者，則必須通過在相鄰邊上加一條邊來實現(xiàn)裂縫的消除。當自身節(jié)點分辨率與相鄰節(jié)點的分辨率相差不止一級，那么還必須遞歸比較并添加邊，直到完全消除裂縫?！　　衽卸ㄊ欠窦毞帧　∽訅K離視點的距離和地形的平坦度共同確定是否需要進一步細分以達到所要求的渲染精度，從而使最終分割后的葉子節(jié)點達到最優(yōu)。離觀察者視點越近的地方細節(jié)越多，地形越不平坦細節(jié)越多?！　∽訅K離視點的距離d可以用公式表示如下：　　其中(Xl，Y1，Z1)為視點坐標，(XO，YO，ZO)為子塊的中心坐標。：　　對于圖中這個子塊的平坦度，先計算出高度值h卜h8，找出其中最大的高度值hMax，最小的高度值bMin，令err=hMax—hMin。err即是此子塊的平坦度?！　rr的值越大就意味著子塊越不平坦，網(wǎng)格細節(jié)應該越多?！　∽罱K，綜合考慮距離和平坦度兩個因素得出判斷是否細化的標準：　　如果err*r／d—kO則繼續(xù)細化，反之則不。(k為一個可變的控制值，r為子塊的i／2邊長，err為子塊平坦度，d為子塊到視點的距離)?！　　　?1)初始化頂點數(shù)組，建立完全四叉樹并初始化，使每個節(jié)點描述清楚自己對應的區(qū)域地形?！　?2)實時渲染：首先對每個四叉樹節(jié)點進行視錐體裁剪，確定進行渲染的四叉樹節(jié)點，再渲染這些節(jié)點。　　?！　。骸　∠扔嬎惚竟?jié)點所管理的地形區(qū)域離視點的距離，再計算其平坦度，兩者共同確定渲染精度值?！　「鶕?jù)渲染精度值和判定標準來確定是否需要進一步細分，對于需要細分的就按四叉樹思想遞歸細分，而不需要細分的就設置它的渲染標志位為真。，渲染標志位為真的節(jié)點，并判定本節(jié)點區(qū)域網(wǎng)格在渲染時是否會出現(xiàn)T型裂縫。判定方法是通過和四周相鄰的節(jié)點比較細節(jié)分辨率值，如果小于相鄰節(jié)點則做修補裂縫處理。　　(3)釋放資源?！　　　∫韵率?0251025大的高度圖用基于四叉樹的LOD算法在線框模式下生成的地形網(wǎng)格：.　　隨著圖形卡數(shù)據(jù)吞吐能力的不斷提高，每秒鐘處理上億個三角形己不再困難。很多計算，比如幾何變換和光柵處理都可以交給GPU去計算。所以在GPU數(shù)據(jù)吞吐量很大的情況下，如果一個算法在剔除渲染頂點的過程中占用了太多CPU資源，出現(xiàn)GPU等待CPU的情況，那么即使算法在剔除多余頂點方面做得很好，總體繪制效率也不是高效的。上面討論的兩種動態(tài)LOD算法(RoAM和基于四叉樹的動態(tài)LOD)都存在這方面的缺陷。并且，受硬件帶寬的限制，頻繁地傳輸海量頂點數(shù)據(jù)，使得時間集中消耗在數(shù)據(jù)“遷移過程中。過多的DP(Draw Primitive)也使得圖形卡不能發(fā)揮最大功效，造成資源極大浪費。所以要適應現(xiàn)代圖形卡的硬件架構，算法必須改進，幾何多重映射(GeoMipMap，Geometrical Mipmapping)等算法由此產生?！　”驹O計在GeoMipMap算法的基礎上，改進了原算法關于抑制不同細節(jié)分辨率模型之間突變的處理方法，使得在提高繪制效率的同時，保證了繪制圖形的質量。通過使用查表法的分塊網(wǎng)格頂點數(shù)據(jù)組織方式，使得CPU的工作進一步減輕。此外，本設計還利用了現(xiàn)代圖形卡的存儲功能來優(yōu)化地形的繪制?！　?GeoMipMap算法　　●基本思想　　GeoMipMap算法是Willem根據(jù)紋理多重映射的概念提出的H3，他把整個地形場景在XZ平面上進行分塊(block)，比如用3333的block把1025X 1025的地形表示為3232個block。每個分塊可用不同分辨率的網(wǎng)格模型來描述。在同一分塊內，網(wǎng)格模型的分辨率相同。采用隔行采樣的方式生成不同分辨率的網(wǎng)格。：　　不同的block之間互相拼接時，如果分辨率不同則可能產生裂縫。為了消除裂縫，在較高分辨率的block邊界上，忽略一些點作為網(wǎng)格頂點，：　　每個block分辨率是通過屏幕空間誤差H3來決定的。在地形數(shù)據(jù)預處理階段，取一個屏幕誤差閥值￡(一般取4個像素)，預先計算出當e等于4個像素時，視點到block的距離d和相應的block分辨率，并保存在查找表中。當實時繪制時，根據(jù)視點到每個block的距離查找表中的d，查找決定該block的網(wǎng)格分辨率?！　　駜?yōu)點和不足　　GeoMipMap算法的網(wǎng)格生成方式顯然和ROAM算法以及基于四叉樹的連續(xù)性LOD算法大不一樣。以基于四叉樹的連續(xù)性LOD算法為例，他是通過自頂向下的方式用四叉樹遞歸地將地形分成一個個小地形塊，越往下細分，地形塊越小，直至不能細分。當視點發(fā)生改變時，所有的頂點都必須重新參與細分的遞歸運算，這種算法能根據(jù)實際情況最大程度確定整個地形的網(wǎng)格分辨率，但計算量很大，并且遞歸層次很多，CPU的負載極大。而對于GeoMipMap算法來說，當　　視點改變時，只需要判斷可見的每一個block的網(wǎng)格分辨率應該是多少，block內部的頂點并不參與計算。雖然這種做法不能最大化減少進入渲染管道的頂點，減少三角形面片，但是增加的這些渲染頂點對現(xiàn)代圖形卡來說是不會影響繪制速度的。相反，由于他減小了實時繪制時模型簡化的計算復雜度，速度得到極大提高，所以他是符合現(xiàn)代圖形卡硬件架構的地形繪制算法。此外GeoMiaMap相對固定的三角形面片組織方式，也使得進入固定渲染管線的頂點能更好的組織成三角形帶，大大減少傳入圖形卡的頂點個數(shù)。　　但是，這種算法由于不是連續(xù)的LOD算法，也就是說LOD的粒度比較粗放，因此在block的網(wǎng)格分辨率發(fā)生改變時，會產生網(wǎng)格形狀的突變，使得在地形漫游時，圖形過渡不自然。雖然通過屏幕投影誤差來選擇block的網(wǎng)格分辨率可以使突變的效果有所減輕，但對用戶來說仍比較明顯。本設計通過線性插值的思想，使層次過渡由突變轉為逐步遞進，極大減小了這方面的不足。　　 GeoM i pMap優(yōu)化算法　　地形數(shù)據(jù)的總體組織和表示　　我們首先讀入一個場景的高度圖數(shù)據(jù)(heightmap)，保存在一個頂點線性表中，然后把這個場景在XZ平面上劃分成均勻大小的多個block。block的大小按需求而定，其邊長滿足2l+l，如99，1717，3333等。如果地勢總體比較平坦，我們可以選得大一點，如果對地形的細節(jié)要求較高我們可以選得小一點。本文以1717作為block的大小。block通過頂點索引所組成的三角形帶描述他負責的一片小的區(qū)域。整個場景用一棵完全四叉樹把這些blocks組織起來。實時渲染時完全四叉樹負責場景的裁剪，決定哪些blocks應該繪制，然后計算可見block的網(wǎng)格分辨率，從而得到整個地形要渲染的三角形面片。其數(shù)據(jù)組織圖如下所示：　　用面向對象的方式描述地形對象：　　當?shù)匦问浅蟮匦卫L制時，我們采用多線程機制加上場景緩沖池的方法實現(xiàn)大地形數(shù)據(jù)的動態(tài)調入和管理。每一個場景Tile作為動態(tài)加載單元，用一個緩沖池來管理，用單獨線程來維護。　　 block多分辨率網(wǎng)格模型的構造和數(shù)據(jù)組織　　Willem在他的論文中指出當細節(jié)層次不同時block的頂點取舍方法，以及為了避免出現(xiàn)T型裂縫，block的邊界頂點應該怎么調整。在他的思想基礎上，本設計提出一種基于查找表的block三角形帶生成方法。　　我們把block的中心地帶和邊界分開對待。在預處理階段就生成五個頂點索引表。：　　中心地帶索引表負責生成block中心的三角形條帶，其索引參數(shù)就是自身的網(wǎng)格分辨率。邊界索引表負責生成與其他block相鄰區(qū)域的三角形帶(防止T型裂縫)。索引參數(shù)有三個：自身的網(wǎng)格分辨率