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

在審

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

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

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

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

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

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

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

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

2.根據權利要求1所述的基于線性四叉樹的LOD模型生成方法，其特征在于，步驟3所述對線性四叉樹的葉結點信息進行存儲，具體如下：

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

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

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

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

3.根據權利要求2所述的基于線性四叉樹的LOD模型生成方法，其特征在于，所述步驟3-4的具體步驟如下：

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

步驟3-4-2、第一輪完成以后再依次檢查四個地形塊的灰度值，直至最后，分割的所有地形塊的左上角的灰度值都相同，然后將帶有標志的灰度值依次序統一保存，即生成線性四叉樹，并記錄葉結點的地址碼和對應的灰度值，遍歷地形節點的計算量僅與地形區域大小呈線性關系，葉結點的地址碼即灰度值數組的序號。

4.根據權利要求1所述的基于線性四叉樹的LOD模型生成方法，其特征在于，所述地形節點評價機制的建立方法如下：

步驟5-1、根據人眼的可見角度、投影平面的高度、世界坐標系的單位長度與屏幕坐標系的單位長度之比值、地形節點的幾何誤差、地形塊的中心點到視點的距離確定地形節點的投影誤差；

步驟5-2、利用地形節點的投影向量與視線方向的夾角對地形節點的投影誤差進行修正；

步驟5-3、根據地形節點的投影誤差的修正值，確定線性四叉樹分割準則即地形節點評價機制：若當前地形節點的投影誤差大于設定的屏幕誤差閾值，則當前地形節點需要進一步分割，返回步驟1；否則，當前地形節點滿足投影誤差要求，停止分割。