基于TIN模型的LOD算法研究

摘 要:為了實現基于不規則三角網(TIN)地形模型的動態細節簡化模型，文中介紹了一種有效的方法，即在一種新的三角網數據結構基礎上，通過重復執行模型中邊的“折疊”(即頂點“合并”)操作，預先計算模型中每個頂點“重要性”值，根據“重要性”對模型的三角形和頂點列表進行重新排序并將結果存儲在數據結構中。在顯示過程中，根據對地形的精度要求和事先存儲的結果自適應地快速獲取所要顯示的頂點和三角形，實現TIN模型的實時動態構網顯示。基于該算法在兩個不同細節的TIN模型進行過渡時可以進行快速線性插值，實現了不同細節模型間的連續過渡。

關鍵詞:不規則三角網(TIN);細節分層(LOD);動態構網

中圖分類號:TP

文獻標識碼:A

文章編號:1672-3198(2010)09-0294-02

1 算法設計

LOD模型的建立，首先要面對模型簡化的問題。為了得到模型中每個頂點對模型幾何特征表現的價值，在模型簡化時吸收了Hoppe H的累進網格(Progressive Mesh)算法思想。這種方法通過重復應用簡單的邊的折疊(頂點到頂點的合并)操作來簡化一個復雜的模型。如果相鄰的LOD模型之間相差僅一個或兩個多邊形，則轉化的過程本身就可近似得到LOD模型的視覺連續性。另外，為了實現不規則三角網模型的實時動態構網，預先將所有可以事先完成的浮點計算任務提前做完并將結果存儲下來，在顯示時根據存儲的結果迅速恢復當前條件下的不規則三角網結構達到實時動態構網的目的。在兩個不同層次LOD模型進行過渡時進行線性插值，實現模型連續變換。算法的總體思路如下所述:

(1)讀入地形模型數據，建立三角形拓撲關系，將數據保存在一個頂點和三角形的列表中。

(2)計算模型中每個頂點的“合并”價值，按照頂點合并價值，將原始三角形和頂點列表進行重新排序，使最重要的點，即最能保留地形模型特征的點排在最前面，并將數據處理結果存儲起來。

(3)在視景顯示過程中，根據顯示精度或顯示要求，自適應地推算出所要顯示的頂點和三角形個數，按照存儲的三角形和頂點列表的順序，直接進行動態構網及顯示。在兩個LOD模型過渡時進行線性插值，實現連續平滑的過渡顯示。

1.1 數據結構

對于TIN三角網而言，其基本的要素是構成三角網的離散點和三角形，同時還要兼顧三角網生成時需要的拓撲關系和簡化時每個頂點相鄰的頂點和三角面，以及為了構網快速而建立的點索引列表。為此設計了頂點和三角形數據結構。基于這樣的數據結構，對于每個頂點可以知道其在點索引中的位置，在構網時是否滿足狄洛尼的條件以及用于網絡簡化時所必須知道的頂點周圍的鄰接點、鄰接三角形、折疊點以及折疊三角形、折疊代價值。頂點的ID號用來表示在按折疊值大小排號序號后的初始值，在另外建立的一個只有三角形點號的列表只需對這個序號進行排序即可。對于每個三角形，可以知道三角形的每條邊、相鄰三角形、法向量、在點分區中的位置以及為了建立拓撲關系所必須知道的三角形圓心。

1.2 邊的折疊價值的計算

對于三角形的簡化，核心是找到應該剔除的頂點。因此一個首要的原則是，當選中的邊折疊后，整個模型的改變最小。我們采用了HoppeH的累進格網思想來計算每個點的重要性。邊的折疊價值計算公式表示如1-2-1:

cost(u，v)=‖u-v‖×maxmin[(1-f#8226;nomal#8226;

nnomal)÷2]1-2-1

其中f∈Tu，n∈Tuv

其中，Tu是三角形數組中包含頂點u的三角形數組;Tuv是三角形數組中同時包含頂點u和頂點v的三角形數組。這樣既考慮了折疊邊長的影響，也考慮到了折疊邊的彎曲程度的影響，較好地反應了折疊邊的折疊度量。

1.3 頂點的折疊、移去和排序

對所有的頂點進行折疊代價值的計算并進行排序，記錄每個頂點和鄰近頂點組成的邊的折疊代價值。通過比較得出最小的一個，將其存儲在頂點的成員變量objdist和collaPSepoint中。然后再對所有頂點按折疊價值大小進行排序，把重新排序過的順序存放在頂點的ID中，再把這一順序放在新建的頂點列表中。對新頂點列表的第一個點進行折疊操作，在新頂點列表中找到這個點，將其刪去。然后將折疊三角形注上已經刪除標志，將刪除點的鄰接點中不包括當前點的鄰接點的點加到當前點中，將刪除點的鄰接三角形中不包括當前點的三角形加到當前三角形中，并把這些三角形頂點中的刪除點替換為當前點。最后對涉及到折疊邊兩點的鄰接點一一計算折疊值。并在新頂點列表中進行重新排序。然后依次折疊下一個折疊邊，直到滿足事先要求的頂點數或所有新頂點列表中的點均已進行折疊操作為止。

1.4 邊自交現象的消除

若不對折疊邊進行事先判斷，而折疊邊周圍的幾何形狀又恰恰非常不理想，則會出現邊的自交現象。經我們反復研究發現，邊自交現象僅和刪除點及其鄰居點組成的多邊形的形狀有關。因此可以把這個多邊形定義為影響多邊形，把組成折疊邊的兩點定義為折疊點和當前點(欲折疊到折疊點的點)，影響多邊形底邊與當前點組成的三角形定義為折疊后三角形。于是只有滿足下列兩個條件的影響多邊形在折疊后才不會發生折疊現象:

(1)折疊點和當前點不能出現在影響多邊形任一底邊的異側。

(2)除當前點外任何一個影響多邊形的頂點不能出現在折疊后三角形當前點與兩底邊點形成的扇形區域內。

基于以上定義，在邊折疊操作以前，先做一個預判，若刪去點后會出現邊的自交現象，就不進行邊的折疊操作。這樣就避免了點自交現象的出現，使構網能夠順利正確進行。

2 實驗

為了檢驗本算法的實用性，采用一組地形模型數據對算法進行了檢驗。實驗所用的設備主要配置為Intel(R) Core(TM)2 Duo CPU P8700，2G內存，ATI顯卡，操作系統是Windows XP，實驗時采用的分辨率為1280*800，32位的增強色。實驗主要測試算法的簡化效果以及對原始模型數據量的適應性。

3 結語

通過本算法，實現了基于不規則三角形連續LOD地形模型的快速構建和實時顯示。但在實驗過程中發現，在進行地形模型簡化過程中，有時會出現邊的自交現象。問題可能出現在顯示時進行邊的折疊操作僅僅考慮頂點和三角形數目的要求，而沒有考慮到在頂點變化的過程中網絡結構的優化，這需要在今后得到進一步解決。

參考文獻

[1]LINDSTROM P， KOLLER D，RIBARSKY W，et al. Real-time，continuous level of detail rendering of height fields[EB/OL]. 

[2]Hoppe H. Progressive meshes[A]. ACM Computer GraphicsProc. Annual Conference Serie(Siggraph’96)[C].1996:99-108.

[3]MARK DUCHAINEAUY，MURRAY WOLINSKY. ROAMing Terrain: Real-time Optimally Adapting Meshes[EB/OL]. 

[4]陳剛.虛擬地形環境的層次描述與實時渲染技術的研究[J].信息工程大學測繪學院， 2000.