[發明專利]一種基于線性四叉樹的LOD模型生成方法

在審

• 申請號: 201510731608.6
• 申請日: 2015-10-30
• 公開（公告）號: CN105405166A
• 公開（公告）日: 2016-03-16
• 發明（設計）人: 高天寒;周嵩
• 申請（專利權）人: 東北大學
• 主分類號: G06T17/05
• 分類號: G06T17/05;G06T15/00
• 代理公司: 沈陽東大知識產權代理有限公司 21109
• 代理人: 胡曉男

技術領域

本發明屬于計算機圖形圖像學技術領域，特別涉及一種基于線性四叉樹的LOD模型生成方法。

背景技術

大規模地形場景的繪制以及三維真實感繪制技術一直是國內外計算機圖形學領域關注的熱點。在目前的渲染方法中，渲染的速度由地形模型中紋理面數量的多少決定，并且為渲染提供的光、質等渲染因子也受到模型中紋理面數量的限制，在此兩種因素的影響下對地形的繪制效果和渲染質感的影響進一步加深。而LOD(LevelofDetail，細節層次模型)技術正式為了解決此類問題而提出，LOD簡化技術在場景中的應用主要可分為兩類：一類是直接利用滿足誤差條件的頂點生成網格的細節層次模型；另一類是從DEM(DigitalElevationModel高程數據模型)柵格數據出發按四叉分割或者二叉分割的方式生成規整的三角形網格的基于規則網格的細節層次模型。現階段對基于規則網格的LOD算法絕大部分是從這兩個算法發展演變而來。

在大規模地形場景的渲染過程中，當視點距某一物體較近時，物體繪制所使用的像素較多，當視點距某一物體較遠時，物體繪制所使用的像素較少。基于此種情況，在地形的繪制過程中就沒有必要使用大量的多邊形片面去精確表示所占像素較少的物體細節。多細節層次技術可以更好的實現三維復雜模型的實時動態顯示效果，通過將三維物體通過用不同精度的模型進行表示，并在此過程中根據視點位置的變化而選擇不同精度的模型繪制成像，此種技術可以大大提高渲染的速度和效率。判斷通過三維可視化技術所繪制的場景是否能夠達到實時變化的效果主要著重于兩點：一是所采用的計算機本身硬件的性能高低；二是繪制物體的幾何目標是否簡單，這將直接決定實時可視化中的計算量。在目前的技術條件下受限于對計算機硬件依賴度比較大的計算機圖形制作系統的制圖能力還比較有限，在這種情況的影響下，對場景繪制渲染成像的過程中每幀所能繪制的原始幾何模型即三角形數量也變得十分有限。綜上所述情況，實時復雜場景特別是大規模地形繪制的關鍵所在就是探索如何有效的降低幾何模型的復雜度。

發明內容

針對現有技術存在的問題，本發明提供一種基于線性四叉樹的LOD模型生成方法。

本發明的技術方案是：

一種基于線性四叉樹的LOD模型生成方法，包括以下步驟：

步驟1、對待繪制地形進行線性四叉樹分割，每一個線性四叉樹節點代表一個分割的地形塊即地形節點，其中距視點近的地形區域分辨率較高且分割層級越大，而遠離視點的地形區域分辨率較低，分割層級越小；

步驟2、待繪制地形的數據存儲在二維數組中，線性四叉樹中每一個節點信息通過索引從該二維數組中讀?。煌瑫r建立一個和所述二維數組大小相同的標志數組，此標志數組指示線性四叉樹節點的狀態，如果一個線性四叉樹節點需要被繼續分割，則把相應的位置標記為1，否則標記為0；

步驟3、對線性四叉樹的葉結點信息進行存儲：將葉結點位置通過基于十進制的Morton編碼表示形成十進制矩陣，葉結點的大小用該葉結點的深度表示；

步驟4、引入希爾伯特填充曲線來組織地形節點，使線性四叉樹中的地形節點按照由頂向下、分辨率低到高的順序存儲進一個一維數組中；

步驟5、在考慮靜態誤差和動態誤差的基礎上建立地形節點評價機制：若當前地形節點的投影誤差大于設定的屏幕誤差閾值，則當前地形節點需要進一步分割，返回步驟1；否則，當前地形節點滿足投影誤差要求，停止分割；

步驟6、對不同分割層級的相鄰地形節點進行裂縫消除，得到基于線性四叉樹的LOD模型。

步驟3所述對線性四叉樹的葉結點信息進行存儲，具體如下：

步驟3-1、將葉結點位置通過基于十進制的Morton編碼表示形成十進制矩陣；

步驟3-2、將十進制矩陣的行號和列號分別轉換成偽碼；

步驟3-3、計算地形Morton編碼；

步驟3-4、使用Morton編碼進行統一編碼，每個葉結點都具有唯一識別的索引，將二維的地形數據轉化成一維，進而基于Morton編碼生成線性四叉樹。

所述步驟3-4的具體步驟如下：

步驟3-4-1、依次檢查分割后的四個地形塊的灰度值，若有一個地形塊的灰度值與其他不同，將這四個地形塊的灰度值暫時賦以一個標志值，否則，直接移動到下四個地形塊檢查；