動態三維場景虛擬地形可視性快速判別方法與流程
2023-06-18 05:35:51 1
本發明涉及一種動態三維場景虛擬地形可視性快速判別方法，是一種通過正向階段式並行掃描實現動態三維場景虛擬地形中點對點的可視性快速判別方法，屬於三維圖形繪製技術領域。
背景技術：
地形是自然場景最重要的組成部分之一，地形渲染是真實感繪製的主要研究內容。數字高程模型（digitalelevationmodel，dem）是一種離散數字地貌模型,基於dem的地形交互式可視化是科學可視化、飛行模擬、虛擬實境、交互式3d遊戲的重要研究內容。在理論上，地形可視性判別需計算來自各個方向上頂點的遮擋關係。對於一個尺寸為n×n的高度場虛擬地形，如果一個方位角方向的所有高度場點都被認為是接收點，計算的時間複雜度將達到o（n3）。傳統方法採用主要的思想是生成一條連接兩個檢測點的線段，也稱作「視線」（lineofsight，los），判斷該線段與地形多邊形是否相交。對於一個包含n個實體的環境，需要在每幀做o（n2）數量級的檢查計算，在三維動態場景中，無法實時的檢測點的可視域。如果在並行掃描的基礎上，有效減少求交測試次數，則能提高可視域的判斷速度，進而改進繪製速度。
在實際動態三維場景中，隨著視點的變化，視點的可視域是隨時發生變化的，但虛擬地形高程點之間的相對位置關係是不會發生變化的。因此，可以將高程點之間的相對位置關係通過掃描和預計算的方式存儲，以減少動態場景的計算量。
技術實現要素：
本發明的目的在於提供一種動態三維場景虛擬地形可視性快速判別方法，該方法通過設計一個虛擬地形的代理包圍盒，快速檢測測試線與場景的交點；通過設計階段式並行高度場掃描算法，預計算場景中任一點的最大視界角，有效的降低了傳統掃描方法的複雜性，提高了對三維虛擬場景中虛擬地形的點對點的可視性判別效率。
本發明的技術解決方案是這樣實現的：一種動態三維場景虛擬地形可視性快速判別方法，其特徵在於：方法由三部分構成，第一部分針對初始虛擬地形構造代理包圍盒；設計一個可見性函數，隨機抽取幾何圖元的基本點的局部最大和最小值，通過可見性函數與用於近似檢測測試線與虛擬地形的相交。
第二部分針對虛擬地形生成k條並行掃描線，計算最大視界角；將n×n的高度場剖面分成若干片段，每個片段具有一個高程值，掃描從片段初始點起，建立2n-1條線程，每條線程並行計算掃描點或高程點在當前掃描方向上的視界角；高度場設點p0為初始掃描點，第一步掃描高程點p1，建立p0到高程點p1的測試線a001，計算初始掃描點p0的視界角b001並存儲；第二步掃描高程點p2，建立初始掃描點p0到p2a002，計算視界角，並比較和的大小，如果，則更新初始掃描點p0的視界角為b001；依次類推，每加入一個新的掃描點，檢查並更新前述各個掃描點的視界角b001。
第三部分針對最大視界角的存儲與搜索，構造可視域；緩存中存儲線程上每個點在該方向的最大視界角b001；為近似估算任意掃描點的視域範圍，k向掃描算法分別沿k個方向並行掃描高度場，當k=3時的8個掃描方向；最後，通過任一點的k個方向視界角b001，估計該點的可視範圍信息。
所述的第一部分針對初始虛擬地形構造代理包圍盒，具體步驟如下：
設場景中任意兩點x和y的可見性函數為v(x,y)，點x和y之間存在的幾何圖元集為，對單一圖元可見性函數表示為:
（1）
對於n個幾何圖元集的可見性函數可表示為多個可見性函數的點乘,即
（2）
因此，建立代理包圍盒將利用近似幾何圖元集代替p，則近似可見性表示為公式（5.31）。
（3）
為減少p』代替p造成的判斷錯誤,建立以下判斷及糾錯措施：類型1：且時，；類型2：且時，；類型3：且時，；類型4：且時，；
所述的第二部分針對虛擬地形生成k條並行掃描線，計算最大視界角，具體步驟如下：
step201：設置掃描方向數k和k個方向上的掃描線數目k*sn（sn=2n-1）；
step202：在計算機系統的內存中，創建一個包含2n-1個hell類型的變量的數組par；
step203：利用正向階段式掃描方法c001，從初始視點p1出發，依次連接視點和該方向上的所有格網點，計算初始視點與其它各個高程點的視界角b001，存儲最大視界角，並將最大視界角對應的頂點記為活高程點pk。計算方法為公式（4）。
（4）
step204：比較新的視界角與已有的最大視界角的大小，更新p0的視界角為最大值，存儲為b001。
step205：掃描第二個測試點p2，僅測試該點與活高程點pk之間的各點，即step104中下一個高程點的視界角掃描範圍限定在前一個高程點的最大視界角所在點之內。存儲p2的最大視界角點為第二個高程點pm，以此類推，下一個測試點的計算範圍限定在該點與活高程點pm之間。
在高程模型中設兩個相鄰視點p1和p2，其中p1的活高程點為m1,m2是與m1相鄰的下一個目標點，和分別為p1與m1，m2的夾角，和分別為p2與m1，m2的夾角，當時兩個相鄰視點p1、p2和兩個相鄰目標點的全部位置及角度的9種關係如圖6所示。如果p2為p1的下一個掃描點，則一定存在且的關係，因此階段式掃描方式正確。
所述的第三部分針對最大視界角的存儲與搜索，構造可視域是利用樹型數據結構hell構造可視性搜索樹，該結構的每個結點p包含數據域data和指針域pi，其中數據域data存儲掃描點位置坐標，指針域pi（i=1..n）分為指向其雙親結點的指針和指向其孩子結點的指針，雙親節點存儲p的最大視界角所在點，其孩子節點存儲以為最大視界角的高程點。hell結構的根結點為該掃描線上的初始掃描點。因此，hell樹型結構表示了全部高程點之間的可視性關係。具體步驟如下：
step301：從初始掃描點p開始，存儲其最大視界角所在點r為其hell類型雙親結點，設置雙親r的第一個孩子指針指向p。
step302：沿著一個掃描線方向尋找下一個掃描點q，存儲其最大視界角所在點r為其hell型雙親結點，設置雙親r的第二個孩子指針指向q，依此類推。
step303：沿著k個方向分別掃描，建立k個樹型結構hell，存儲每個掃描點的最大視界角點b001。
step304：選擇場景中任意一點p，搜索k個樹型存儲結構hell;
step305：搜索hell結構中p點的k個最大視界角所在點及值；
step306：以觀測點p為初始平面所在點，連接k各最大視界角所在點，作為p的視域範圍。
本發明的積極效果是分布式虛擬地形近似可視域的計算方法，該方法設計了一個虛擬地形的代理包圍盒，並改進了已有的並行高度場掃描算法，使得並行掃描算法的掃描複雜性從o（n2）降為o（nlogn），實現了虛擬地形的點間可見性和可視域近似計算，提高了虛擬地形的動態更新效率。
附圖說明
圖1為代理包圍盒視線類型。
圖2為高度場剖面示意圖。
圖3為視界角計算示意圖。
圖4為k=4時的8個掃描方向示意圖。
圖5為階段式掃描示意圖。
圖6為枚舉相鄰視點p1，p2間的9種視界角關係。
圖7hell樹的創建過程示意圖。
圖8為hell樹結構示意圖。
圖9近似視域構成示意圖。
具體實施方式
為了使本方法的特徵和優點更加清楚明白，下面結合具體實施例對本方法作進一步的描述。在本實施例中，考慮了兩種地形數據：1）dem真實數據，2）基於perlin噪聲生成的虛擬地形數據。計算機系統的cpu選擇intel（r）xeon(r)cpue5620@雙核2.40ghz，內存選擇金士頓8gbddr31333，硬碟選擇buffalohd-ce1.5tu2；顯卡選擇nvidiaquadrok5000，計算機作業系統選用windows7，軟體編程工具選用vc++2010。
一種動態三維場景虛擬地形可視性快速判別方法，其特徵在於：方法由三部分構成，第一部分，針對初始虛擬地形構造代理包圍盒。設計一個可見性函數，隨機抽取幾何圖元的基本點的局部最大和最小值，通過可見性函數與用於近似檢測測試線與虛擬地形的相交（圖1）。
第二部分針對虛擬地形生成k條並行掃描線，計算最大視界角。將n×n的高度場剖面分成若干片段，每個片段具有一個高程值，掃描從片段初始點起，建立2n-1條線程，每條線程並行計算掃描點或高程點在當前掃描方向上的視界角；高度場設點p0為初始掃描點，第一步掃描高程點p1，建立p0到高程點p1的測試線a001，計算初始掃描點p0的視界角b001並存儲；第二步掃描高程點p2，建立初始掃描點p0到p2a002，計算視界角，並比較和的大小，如果，則更新初始掃描點p0的視界角為b001；依次類推，每加入一個新的掃描點，檢查並更新前述各個掃描點的視界角b001（圖2）。
第三部分針對最大視界角的存儲與搜索，構造可視域。緩存中存儲線程上每個點在該方向的最大視界角b001（圖3）；為近似估算任意掃描點的視域範圍，k向掃描算法分別沿k個方向並行掃描高度場，當k=3時的8個掃描方向（圖4）；最後，通過任一點的k個方向視界角b001，估計該點的可視範圍信息。
所述的第一部分針對初始虛擬地形構造代理包圍盒，具體步驟如下：
設場景中任意兩點x和y的可見性函數為v(x,y)，點x和y之間存在的幾何圖元集為，對單一圖元可見性函數表示為:
（1）
對於n個幾何圖元集的可見性函數可表示為多個可見性函數的點乘,即
（2）
因此，建立代理包圍盒將利用近似幾何圖元集代替p，則近似可見性表示為公式（5.31）。
（3）
為減少p』代替p造成的判斷錯誤,建立以下判斷及糾錯措施：類型1：且時，；類型2：且時，；類型3：且時，；類型4：且時，（圖1）。
所述的第二部分針對虛擬地形生成k條並行掃描線，計算最大視界角，具體步驟如下：
step201：設置掃描方向數k和k個方向上的掃描線數目k*sn（sn=2n-1）；
step202：在計算機系統的內存中，創建一個包含2n-1個hell類型的變量的數組par；
step203：利用正向階段式掃描方法c001，從初始視點p1出發，依次連接視點和該方向上的所有格網點，計算初始視點與其它各個高程點的視界角b001，存儲最大視界角，並將最大視界角對應的頂點記為活高程點pk。計算方法為公式（4）。
（4）
step204：比較新的視界角與已有的最大視界角的大小，更新p0的視界角為最大值，存儲為b001。
step205：掃描第二個測試點p2，僅測試該點與活高程點pk之間的各點，即step104中下一個高程點的視界角掃描範圍限定在前一個高程點的最大視界角所在點之內。存儲p2的最大視界角點為第二個高程點pm，以此類推，下一個測試點的計算範圍限定在該點與活高程點pm之間，見圖5。
在高程模型中設兩個相鄰視點p1和p2，其中p1的活高程點為m1,m2是與m1相鄰的下一個目標點，和分別為p1與m1，m2的夾角，和分別為p2與m1，m2的夾角，當時兩個相鄰視點p1、p2和兩個相鄰目標點的全部位置及角度的9種關係如圖6所示。如果p2為p1的下一個掃描點，則一定存在且的關係，因此階段式掃描方式正確。
所述的第三部分針對最大視界角的存儲與搜索，構造可視域。本方法利用樹型數據結構hell構造可視性搜索樹，該結構的每個結點p包含數據域data和指針域pi，其中數據域data存儲掃描點位置坐標，指針域pi（i=1..n）分為指向其雙親結點的指針和指向其孩子結點的指針，雙親節點存儲p的最大視界角所在點，其孩子節點存儲以為最大視界角的高程點（圖6，圖7）。hell結構的根結點為該掃描線上的初始掃描點。因此，hell樹型結構表示了全部高程點之間的可視性關係。具體步驟如下：
step301：從初始掃描點p開始，存儲其最大視界角所在點r為其hell類型雙親結點，設置雙親r的第一個孩子指針指向p。
step302：沿著一個掃描線方向尋找下一個掃描點q，存儲其最大視界角所在點r為其hell型雙親結點，設置雙親r的第二個孩子指針指向q。依此類推（見圖7與圖8）。
step303：沿著k個方向分別掃描，建立k個樹型結構hell，存儲每個掃描點的最大視界角點b001。
step304：選擇場景中任意一點p，搜索k個樹型存儲結構hell;
step305：搜索hell結構中p點的k個最大視界角所在點及值；
step306：以觀測點p為初始平面所在點，連接k各最大視界角所在點，作為p的視域範圍（圖9）。
在本實施例中，代理包圍盒利用簡單的幾個圖元代表複雜的幾何形狀，來控制求交計算次數。
當值為0時，才生成掃描測試線。當問題的規模為n時，已有掃描方法的時間複雜性表示為o（n2），而改進的掃描算法在平均情況下，將比較次數分成了n段logn次比較。因此，將掃描數量級從o(n2)降為o(nlogn)。