[發明專利]一種基于kd樹的實時大規模地形可視化實現方法

有效

• 申請號: 201210411616.9
• 申請日: 2012-10-24
• 公開（公告）號: CN103077549A
• 公開（公告）日: 2013-05-01
• 發明（設計）人: 裴海龍;姚定忠
• 申請（專利權）人: 華南理工大學
• 主分類號: G06T17/00
• 分類號: G06T17/00
• 代理公司: 廣州市華學知識產權代理有限公司 44245
• 代理人: 蔡茂略

1.一種基于kd樹的實時大規模地形可視化實現方法，其特征在于，包括下述步驟：?

將地形按點云空間分塊，并利用kd樹分層，離線地建立LOD模型，所述建立LOD模型是負責由地形點云數據獲得多分辨率模型數據以及模型的各分辨率間切換；?

在線時利用外部存儲算法將離線構造的LOD模型數據載入內存，所述外部存儲算法負責將外存的LOD模型數據向內存調度；?

對內存中的LOD模型數據使用簡化的地形剔除技術，所述地形數據剔除技術負責剔除不可見的LOD模型數據，減少傳輸到圖形硬件的數據量；?

利用三維引擎優化技術對剔除后的數據進一步的減少傳輸到圖形硬件的數據量以及計算量。?

2.根據權利要求1所述的實時大規模地形可視化實現方法，其特征在于，所述建立LOD模型，包括建立離線LOD模型和建立在線的LOD模型兩部分，所述建立離線LOD模型需要讀取三次點云數據文件：第一次讀取獲得點的總數，根據提前限定的每個分塊內的點的最大點數，設定每個分塊的位置和大小；第二次讀取記錄前面設定的每個分塊的內點數；第三次讀取時用經典的逐點插入法進行Delaunay三角化，并將對應分塊記錄的點數遞減；當遞減為零時，查找對應分塊內外接圓越過分塊邊緣的三角形和它們的頂點，記錄為分割三角帶和點云包圍圈；對在分塊內而不在點云包圍圈內的點進行改進的kd樹空間劃分，獲得按照樹的層次順序排列的存儲在一維數組點云數據，將該點云數據、分割三角帶和點云包圍圈存儲到外存中；清除該分塊占用的內存，繼續讀取，直到所有點云數據讀完。?

3.根據權利要求2所述的基于kd樹的實時大規模地形可視化實現方法，其特征在于，所述的改進的kd樹空間劃分包括第一改進和第二改進，所述第一改進是kd樹的劃分方向改為要劃分區域的長軸方向；第二改進是kd樹的劃分點為滿足每次劃分盡量將不完整的一層向左子樹分布。?

4.根據權利要求2所述的基于kd樹的實時大規模地形可視化實現方法，其特征在于，所述的建立在線的LOD模型，包括簡化的模型分辨率決策準則和動態更新Delaunay三角網兩部分；所述簡化的模型分辨率決策準則根據每個分?塊內的點密度和分塊與視點的距離，計算出分塊需要切換至的模型分辨率，在長度為l的物體在與它相距d的視點的觀察下，被投影到屏幕上；且有如下的關系式：?

其中α為視角，N_p為屏幕在視點視野范圍內的縱向切線上的像素數目，n_p是該物體投影到屏幕上在該切線上占用的像素數目；?

當n_p＝1時，即此時物體投影到屏幕在切線上占用一個像素時，下式即為模型分辨率決策的基本準則，公式如下：?

此時，長度小于等于l的物體在屏幕上被壓縮在一個像素內，這時的物體的細節已經無法分辨了，所有在該物體上的點云只需用一個頂點表示即可。?

5.根據權利要求4所述的基于kd樹的實時大規模地形可視化實現方法，其特征在于，所述的動態更新Delaunay三角網使用一種成熟的插入和刪除點的Delaunay算法，同時在更新三角形的更新一個N×7的二位數組，其中N代表三角形的個數，7列分別是三角形的序號、三個頂點和三個頂點相對的相鄰三角形序號，該二維數組表示了整個三角網的拓撲結構。?

6.根據權利要求1所述的基于kd樹的實時大規模地形可視化實現方法，其特征在于，所述的外部存儲算法包括改進的數據預讀、視椎體投影的數據補充和增量計算三部分；所述改進的數據預讀使用了兩層的預讀區，即在一般預讀區外圍再設定一個分辨率更低的預讀區；所述的視椎體數據補充，是將視椎體映射到二維平面，然后找出與映射相交的分塊；所述的增量計算，是將由所述改進的數據預讀和所述的視椎體數據補充獲得的調度列表中的分塊中需要調度的數據，即對應需要分辨率的LOD模型數據和在內存中對應分塊中已有的數據做比較，算出需要調度的具體到一個點的數據。?

7.根據權利要求6所述的基于kd樹的實時大規模地形可視化實現方法，其特征在于，所述的地形數據剔除技術，與所述視椎體數據補充一致，并直接?使用其計算結果。?