[發(fā)明專利]一種基于kd樹的實(shí)時(shí)大規(guī)模地形可視化實(shí)現(xiàn)方法

有效

• 申請(qǐng)?zhí)枺?/td>: 201210411616.9
• 申請(qǐng)日: 2012-10-24
• 公開（公告）號(hào): CN103077549A
• 公開（公告）日: 2013-05-01
• 發(fā)明（設(shè)計(jì)）人: 裴海龍;姚定忠
• 申請(qǐng)（專利權(quán)）人: 華南理工大學(xué)
• 主分類號(hào): G06T17/00
• 分類號(hào): G06T17/00
• 代理公司: 廣州市華學(xué)知識(shí)產(chǎn)權(quán)代理有限公司 44245
• 代理人: 蔡茂略

技術(shù)領(lǐng)域

本發(fā)明涉及大規(guī)模地形點(diǎn)云的三維可視化的技術(shù)領(lǐng)域，特別涉及一種基于kd樹的實(shí)時(shí)大規(guī)模地形可視化方法。

背景技術(shù)

地形點(diǎn)云三維可視化，就是根據(jù)計(jì)算機(jī)圖形學(xué)的原理，將三維地形數(shù)據(jù)（包括離散的點(diǎn)云和點(diǎn)間形成的三角形片集的點(diǎn)序列）經(jīng)過視圖變換、模型變換、投影變換和視區(qū)變換等一系列操作，最后在二維的屏幕上顯示出來。而當(dāng)?shù)匦螖?shù)據(jù)量很大時(shí)，要進(jìn)行變換的操作數(shù)量也會(huì)隨之劇增，這就需要使用一些提高地形數(shù)據(jù)三維可視化效率的算法，才能滿足其實(shí)時(shí)顯示的要求。

業(yè)界對(duì)高效的地形數(shù)據(jù)三維可視化研究的成果主要集中在LOD模型構(gòu)造算法上面，對(duì)三維可視化的其他研究還包括地形數(shù)據(jù)剔除技術(shù)和三維引擎的優(yōu)化使用等。

LOD模型構(gòu)造算法，能夠根據(jù)需求動(dòng)態(tài)地調(diào)整顯示對(duì)象模型的精度，大大減小可視化的數(shù)據(jù)量，以達(dá)到提高可視化效率的目的。這種算法的關(guān)鍵是如何建立一個(gè)高效的多分辨率模型，涉及到二叉樹、四叉樹、kd樹等空間劃分方法、各種內(nèi)存管理技術(shù)和各種Delaunay三角網(wǎng)更新或者規(guī)則點(diǎn)云分布三角網(wǎng)構(gòu)建方法等。

地形數(shù)據(jù)剔除技術(shù)，能夠在地形數(shù)據(jù)不會(huì)被顯示的時(shí)候?qū)⑵涮蕹床话l(fā)往圖形硬件去繪制，以大幅減少可視化的數(shù)據(jù)量，達(dá)到提升顯示速度的目的。該技術(shù)的關(guān)鍵是如何高效地定位可見的地形數(shù)據(jù)。

三維引擎的優(yōu)化使用，能夠在顯示地形數(shù)據(jù)量不變的情況下大大的減小傳輸?shù)臄?shù)據(jù)量和重復(fù)計(jì)算量，以大大提升顯示速度的目的。常見的優(yōu)化有三角形條帶化和OpenGL頂點(diǎn)數(shù)組和索引數(shù)組的使用。

現(xiàn)有的基于TIN的高質(zhì)量的海量地形點(diǎn)云可視化算法，基本是采用了記錄三角網(wǎng)簡(jiǎn)化的過程信息。雖然避開了實(shí)時(shí)進(jìn)行Delaunay三角網(wǎng)的更新這一復(fù)雜的過程，但是復(fù)雜性仍然非常高，效率不理想。

本發(fā)明的方法，正是在具有基于TIN可視化算法的高質(zhì)量顯示的同時(shí)，很好地改善了效率。

發(fā)明內(nèi)容

本發(fā)明的目的在于克服現(xiàn)有技術(shù)的缺點(diǎn)與不足，提供一種復(fù)雜性低、可視化效率高的基于kd樹的實(shí)時(shí)大規(guī)模地形可視化實(shí)現(xiàn)方法。

為了達(dá)到上述目的，本發(fā)明采用以下技術(shù)方案：

一種基于kd樹的實(shí)時(shí)大規(guī)模地形可視化實(shí)現(xiàn)方法，包括下述步驟：

將地形按點(diǎn)云空間分塊，并利用kd樹分層，離線地建立LOD模型，所述建立LOD模型是負(fù)責(zé)由地形點(diǎn)云數(shù)據(jù)獲得多分辨率模型數(shù)據(jù)以及模型的各分辨率間切換；

在線時(shí)利用外部存儲(chǔ)算法將離線構(gòu)造的LOD模型數(shù)據(jù)載入內(nèi)存，所述外部存儲(chǔ)算法負(fù)責(zé)將外存的LOD模型數(shù)據(jù)向內(nèi)存調(diào)度；

對(duì)內(nèi)存中的LOD模型數(shù)據(jù)使用簡(jiǎn)化的地形剔除技術(shù)，所述地形數(shù)據(jù)剔除技術(shù)負(fù)責(zé)剔除不可見的LOD模型數(shù)據(jù)，減少傳輸?shù)綀D形硬件的數(shù)據(jù)量；

利用三維引擎優(yōu)化技術(shù)對(duì)剔除后的數(shù)據(jù)進(jìn)一步的減少傳輸?shù)綀D形硬件的數(shù)據(jù)量以及計(jì)算量。

優(yōu)選的，所述建立LOD模型，包括建立離線LOD模型和建立在線的LOD模型兩部分，所述建立離線LOD模型需要讀取三次點(diǎn)云數(shù)據(jù)文件：第一次讀取獲得點(diǎn)的總數(shù)，根據(jù)提前限定的每個(gè)分塊內(nèi)的點(diǎn)的最大點(diǎn)數(shù)，設(shè)定每個(gè)分塊的位置和大小；第二次讀取記錄前面設(shè)定的每個(gè)分塊的內(nèi)點(diǎn)數(shù)；第三次讀取時(shí)用經(jīng)典的逐點(diǎn)插入法進(jìn)行Delaunay三角化，并將對(duì)應(yīng)分塊記錄的點(diǎn)數(shù)遞減；當(dāng)遞減為零時(shí)，查找對(duì)應(yīng)分塊內(nèi)外接圓越過分塊邊緣的三角形和它們的頂點(diǎn)，記錄為分割三角帶和點(diǎn)云包圍圈；對(duì)在分塊內(nèi)而不在點(diǎn)云包圍圈內(nèi)的點(diǎn)進(jìn)行改進(jìn)的kd樹空間劃分，獲得按照樹的層次順序排列的存儲(chǔ)在一維數(shù)組點(diǎn)云數(shù)據(jù)，將該點(diǎn)云數(shù)據(jù)、分割三角帶和點(diǎn)云包圍圈存儲(chǔ)到外存中；清除該分塊占用的內(nèi)存，繼續(xù)讀取，直到所有點(diǎn)云數(shù)據(jù)讀完。

優(yōu)選的，所述的改進(jìn)的kd樹空間劃分包括第一改進(jìn)和第二改進(jìn)，所述第一改進(jìn)是kd樹的劃分方向改為要?jiǎng)澐謪^(qū)域的長(zhǎng)軸方向；第二改進(jìn)是kd樹的劃分點(diǎn)為滿足每次劃分盡量將不完整的一層向左子樹分布。

優(yōu)選的，所述的建立在線的LOD模型，包括簡(jiǎn)化的模型分辨率決策準(zhǔn)則和動(dòng)態(tài)更新Delaunay三角網(wǎng)兩部分；所述簡(jiǎn)化的模型分辨率決策準(zhǔn)則根據(jù)每個(gè)分塊內(nèi)的點(diǎn)密度和分塊與視點(diǎn)的距離，計(jì)算出分塊需要切換至的模型分辨率，在長(zhǎng)度為l的物體在與它相距d的視點(diǎn)的觀察下，被投影到屏幕上；且有如下的關(guān)系式：