概述：
虛擬現實中場景的生成對實時性要求很高，LOD技術是一種有效的圖形生成加速方法。本文主要介紹了LOD技術的研究內容、LOD模型的生成算法以及LOD模型在虛擬場景生成中的選擇。最後，對LOD技術未來的研究方向作了展望。
相關信息
一、引言
虛擬現實技術是一種逼真地模擬人在自然環境中視覺、聽覺、觸覺及運動等行為的人機互動技術。它融合了計算機圖形學、多媒體技術、人工智慧、人機接口技術、數字圖像處理、網路技術、感測器技術以及高度並行的實時計算技術等多個信息技術分支。它的主要特徵是沉浸感、互動性和想像力。 它的要害技術包括：環境建模技術、立體聲合成和立體顯示技術、觸覺反饋、互動技術、系統集成技術。
虛擬現實中最重要的是人可以在隨意變化的互動控制下感受到場景的動態特性，也就是虛擬現實系統要求隨著人的活動即時生成相應的圖形畫面。有兩種重要指標衡量用戶對虛擬環境的沉浸效果和程度：一是動態特性，自然的動態特性要求每秒生成和顯示30幀圖形畫面，至少不能少於10幀，否則將會產生嚴重的不連續和跳動感。另一個指標是互動延遲，系統的圖形生成對用戶的互動動作做出反應的延遲時間不應大於0.1秒，最多不能大於1/4秒。以上兩種指標均依靠於系統生成圖形的速度。顯而易見，圖形生成速度是虛擬現實的重要瓶頸。
圖形生成的速度主要取決於圖形處理的軟硬體體系結構，非凡是硬體加速器的圖形處理能力以及圖形生成所採用的各種加速技術。雖然現今的圖形工作站得益於高速發展的CPU和專用圖形處理器性能得到很大的提高，但距離VR的需求仍有相當大的差距。考慮到VR對場景複雜度幾乎無限制的要求，在高質量圖形的實時生成要求下，如何從軟體著手，減少圖形畫面的複雜度，已成為VR圖形生成的主要目標。
1976年，Clark[1]提出了細節層次（Levels of Detail，簡稱LOD）模型的概念，認為當物體覆蓋螢幕較小區域時，可以使用該物體描述較粗的模型，並給出了一個用於可見面判定算法的幾何層次模型，以便對複雜場景進行快速繪製。1982年，Rubin[2]結合光線跟蹤算法，提出了複雜場景的層次表示算法及相關的繪製算法，從而使計算機能以較少的時間繪製複雜場景。
90年代初，圖形學方向上派生出虛擬現實和科學計算可視化等新研究領域。虛擬現實和互動式可視化等互動式圖形套用系統要求圖形生成速度達到實時，而計算機所提供的計算能力往往不能滿足複雜三維場景的實時繪製要求，因而研究人員提出多種圖形生成加速方法，LOD模型則是其中一種主要方法。這幾年在全世界範圍內形成了對LOD技術的研究熱潮，並且取得了很多有意義的研究結果。
二、LOD技術
1. LOD技術的概念和套用領域
LOD技術在不影響畫面視覺效果的條件下，通過逐次簡化景物的表面細節來減少場景的幾何複雜性，從而提高繪製算法的效率。該技術通常對每一原始多面體模型建立幾個不同逼近精度的幾何模型。與原模型相比，每個模型均保留了一定層次的細節。在繪製時，根據不同的表準選擇適當的層次模型來表示物體。LOD技術具有廣泛的套用領域。目前在實時圖像通信、互動式可視化、虛擬現實、地形表示、飛行模擬、碰撞檢測、限時圖形繪製等領域都得到了套用，已經成為一項要害技術。很多造型軟體和VR開發系統都開始支持LOD模型表示。
2.虛擬場景生成中LOD模型的選擇
恰當地選擇細節層次模型能在不損失圖形細節的條件下加速場景顯示，提高系統的回響能力。選擇的方法可以分為如下幾類：一類是側重於去掉那些不需要用圖形顯示硬體繪製的細節。一類是去掉那些無法用圖形硬體繪製的細節，如基於距離和物體尺寸標準的方法。另一類是去掉那些人類視覺覺察不到的細節，如基於偏心率，視野深度，運動速度等標準的方法。此外還有一種方法考慮的是保持恆定幀率。
（1）剔除法
在一些特定的情況下，場景中的一部分幾何形體是什麼時候都無法被觀察者看到的。在此情況下，圖形系統不再繪製這部分物體。
（2）距離標準
這種方法考慮的是物體到觀察者的距離。這個距離是從視點到物體內指定點的歐氏距離。這種方法的理論依據是當一個物體距離視點越遠，此物體能夠被觀察到的精細的細節部分就越少。這就意味著選擇較粗糙的細節層次來表示物體不會對顯示的逼真度有很大影響。
（3）尺寸標準
這種方法利用了人眼辨識物體的能力隨著物體尺寸的減小而減弱的特性。它考慮到待表示物體的尺寸，較小的物體用較粗糙的細節層次，較大的用較精細的細節層次。
（4）偏心率
此方法利用了人眼辨識物體的能力隨著物體逐漸遠離視域中心而減弱的特性。視網膜的中心對物體細節的分辨能力較強，視網膜邊緣的分辨能力較弱。根據這個原理，將顯示的場景分為具有較精細細節層次的中心部分（對應於眼睛視域的中心）和外圍部分（對應於視域的外圍部分）。
（5）視野深度
這種方法根據觀察者眼睛的焦距來為物體選擇合適的細節層次。在聚焦區域的前面或者後面的物體不被聚焦。
（6）運動速度
該方法是根據物體相對於觀察者視線的角速度選擇合適的細節層次。在螢幕上快速運動的物體看起來是模糊的，這些物體只在很短的時間內被看到，因而觀察者可能看不清它們。這樣就可以用較粗糙的細節層次來表示它們。
（7）固定幀率
保持一個較高並且穩定的幀率對於良好的互動性能是非常重要的。這就意味著一旦選定一個幀率，就要保持恆定，不能隨場景複雜度的改變而變化。
3.LOD模型的生成
（1）光照模型
這種方法利用光照技術得到物體的不同細節層次。例如，我們可以用較少的多邊形和改進的光照算法得到同包含較多的多邊形的表示相似的效果。
（2）紋理映射
該方法是適用一些紋理來表示不同的細節層次。具有精細細節層次的區域可以用一個帶有紋理的多邊形來代替。這個多邊形的紋理是從某個特定的視點和距離得到的這個區域的一幅圖像。
（3）多邊形簡化
多邊形簡化算法的目的是輸入一個由很多多邊形構成的精細模型，得到一個跟原模型相當相似的但包含較少數目的多邊形的簡化模型，並保持原模型重要的視覺特徵。大多數的細節層次簡化算法都屬於此類。
4.LOD細模型的實現方式
（1）靜態Lod
在預處理過程中產生一個物體的幾個離散的不同細節層次模型。實時繪製時根據特定的標準選擇合適的細節層次模型來表示物體。
（2）動態Lod
在動態Lod算法中生成一個數據結構，在實時繪製時可以從這個數據結構中抽取出所需的細節層次模型。從這個數據結構中可以得到大量不同解析度的細節層次模型，解析度甚至可以是連續變化的。
三、LOD模型生成算法的分類
由於人們通常用多邊形格線（特例為三角形格線）來描述場景中的圖形物體，因而LOD模型的生成就轉化為三維多邊形格線簡化問題。格線簡化的目的是把一個用多邊形格線表示的模型用一個近似的模型表示，近似模型基本保持了原模型的可視特徵，但頂點數目少於原始格線的頂點數目。多邊形格線簡化算法進行分類的方法有多種：
1.按是否保持拓撲結構分類
拓撲結構保持算法：較好的視覺逼真度，但是限制了簡化的程度，並且要求初始模型是流形。拓撲結構非保持算法：可實現大幅度地簡化，逼真度較差
2.按簡化機制不同分類
自適應細分型：首先建立原始模型的最簡化形式，然後根據一定的規則通過細分把細節信息增加到簡化模型中。不常用，因為構造最初格線的最簡模型相當困難，主要適用與均勻格線。
採樣型：類似於圖像處理的濾波方式，把幾何包圍盒中的一組頂點用一個代表頂點代替。適用於具有光滑表面的模型。
幾何元素刪除型：通過重複地把幾何元素從三角形中“移去”來得到簡化模型。這裡地移去包括：直接刪除、合併、摺疊。這類算法實現簡單，速度快。大多數的簡化算法都屬於這一類。
3.局部算法/全局算法
全局算法是指對整個物體模型或場景模型的簡化過程進行最佳化，而不僅僅根據局部的特徵來確定刪除不重要的元素。局部算法是指套用一組局部規則，僅考慮物體的某個局部區域的特徵對物體進行簡化。
四、典型的LOD模型生成算法概述
1．近平面合併法
Hinkler等的幾何最佳化方法[3]檢測出共面或近似共面的三角面片，將這些三角面片合併為大的多邊形，然後用較少數目的三角形將這個多邊形重新三角化。這個方法的步驟是（1）迅速地將面片分類為近似共面的集合（2）快速合併這些集合中的面片（3）簡單而且魯棒的三角化。面片分類依據的是他們的各自的法線之間的夾角。該算法的誤差衡量標準可以歸為全局誤差，但是由於它僅僅依據法線之間的夾角，它的誤差評估準確性較差。它不能保證一定誤差限制。
2．幾何元素（頂點/邊/面）刪除法
幾何元素刪除法由局部幾何最佳化機制驅動，要計算每次刪除產生的近似誤差。
Schroeder的頂點刪除算法[4]通過刪除滿足距離或者角度標準的頂點來減小三角格線的複雜度。刪除頂點留下的空洞要重新三角化填補。該算法速度快，但不能保證近似誤差。它估算局部誤差，未考慮新面片同原始格線的聯繫和誤差積累。
Hoppe漸進格線算法[5]包含基於邊摺疊的格線簡化方法、能量函式最佳化和新的多解析度表示。算法採用了單步和可逆的邊摺疊操作，可以將整個簡化過程存入一個多解析度數據結構（稱為漸進格線表示（PM））。PM方案由一個簡化格線Mk和一系列細化記錄（通過與從原始格線M0得到簡化格線Mk的簡化步驟的相反的步驟得到）, 這些細化記錄可以使格線Mk通過逐步求精得到任意精確度的格線Mi。在簡化過程中，將每條邊按照其摺疊的能量代價排序得到一個優先權佇列，通過這個佇列實現邊摺疊操作。該算法也是採用全局誤差度量。
3．重新劃分算法
Turk的重新劃分算法[6]先將一定數量的點分布到原有格線上 ,然後新點與老頂點生成一個中間格線 ,最後刪除中間格線中的老頂點 ,並對產生的多邊形區域進行局部三角化 ,形成以新點為頂點的三角形格線 .其中分布新點採用排斥力算法 ,即先隨機分布新點 ,然後計算新點之間的排斥力 ,根據排斥力在格線上移動這些新點 ,使它們重新分布 .排斥力的大小與新點之間的距離、新點所在三角形的曲率和面積有關。這種方法對那些較光滑的模型是很有效的 ,但對於那些不光滑的模型 ,效果較差; 由於根據排斥力重新分布新點 ,涉及到平面旋轉或投影 ,計算量和誤差都較大。
4．聚類算法
Rossignac等的頂點聚類算法[7]通過檢測併合並相鄰頂點的聚類來簡化格線。每個聚類被一個代表頂點取代，這個代表頂點可能是頂點聚類的中心或者是聚類中具有最大權值的頂點（定義頂點的權值是為了強調相對的視覺總要性）。然後，去處那些由於聚類操作引起的重疊或者退化的邊或者三角形。算法簡化引入的誤差由用戶定義的準確度控制，這個標準用來驅動聚類尺寸的選擇。該算法實現簡單、速度快，但是沒有考慮到保持原始格線的拓撲和幾何結構，有可能生成非常粗糙的近似格線。
5．小波分解算法
Eck等的基於小波變換的多解析度模型[8]使用了帶有修正項的基本格線，修正項稱為小波係數，用來表示模型在不同解析度情況下的細節特徵。算法的三個主要步驟：分割：輸入格線M被分成一些（數目較少）三角形的區域T1,......,Tn, 由此構成的低解析度三角格線稱為基本格線K0。參數化：對於每個三角區域Ti，根據它在基本格線K0上相應的表面進行局部參數化。重新採樣：對基本格線進行j次遞歸細分就得到格線Kj，並且通過使用參數化過程中建立的參數將Kj的頂點映射到3維空間中得到格線Kj的坐標。此算法可以處理任意拓撲結構的格線，而且可以提供：有界誤差、緊湊的多解析度表示和多解析度尺度下的格線編輯。
五、結束語
LOD技術在虛擬場景生成中具有非常要害的作用，本文討論了LOD技術的研究內容、LOD模型的生成算法和其在虛擬場景生成中的套用方式。LOD技術今後需要進一步研究的內容包括：簡化過程中模型表面屬性的處理以及特徵保持問題；建立統一的誤差評價測度；
不同細節層次之間的平滑過渡；視點相關的LOD生成算法研究等。
