[發明專利]顧及拓撲的三維地理空間實體群的線消隱方法

有效

• 申請號: 201410583209.5
• 申請日: 2014-10-27
• 公開（公告）號: CN104392489A
• 公開（公告）日: 2015-03-04
• 發明（設計）人: 虞昌彬;李霖;趙志剛;賀彪
• 申請（專利權）人: 武漢大學
• 主分類號: G06T17/05
• 分類號: G06T17/05
• 代理公司: 武漢科皓知識產權代理事務所(特殊普通合伙) 42222
• 代理人: 嚴彥

技術領域

本發明涉及三維地理空間數據組織與可視化的技術領域，尤其是涉及一種顧及拓撲的三維地理空間數據的線消隱方法。

背景技術

用計算機生成三維形體的真實感圖形，是計算機圖形學研究重點之一。真實感圖形在仿真模擬、幾何造型、科學計算可視化等多個領域具有廣泛應用，其生成過程涉及消隱。消隱，就是運用某種技術手段判別物體的隱藏部分(不可見的線或面)并將其從畫面中消除或用虛線繪制的過程，也稱可見性測試。消隱后的圖形，稱為Shaded?Picture或者Half-tone?Picture，與物體的可見性判定(Visibility?Determination)在原則上等價。采用消隱后的二維線框圖形來表達真實的三維圖形，輸入數據為三維實體群，輸出數據為二維線框。因為輸出數據是線框，面在輸出結果中是不表達的，所以核心是線狀實體在最終輸出結果中的可見或不可見表達。消隱的過程，其實是不斷趨近最真實的面與線可見性判定的過程。

之所以消隱在真實感圖形生成過程中非常重要，是因為：(1)三維信息在經過二維投影變換后失去了深度信息，往往導致圖形表達的二義性，需要在繪制二維圖形同時通過隱藏物體的不可見部分來輔助展現三維立體形態；(2)消隱是生成真實感圖形的重要組成部分，它為后續的光照模型設置、表面渲染(包括紋理映射)提供了基礎。

消隱方法至今研究眾多。面對迄今為止眾多的消隱算法研究，分類方法也有所不同，可歸納如下：(1)根據消隱方法分類，包括物空間消隱和像空間消隱；(2)根據消隱對象分類，包括線消隱和面消隱；(3)根據實現途徑分類，包括計算機軟件實現和硬件實現。現有多采用第一種和第二種分類方法，特別是第一種分類方法。具體的，物空間消隱以三維場景中對象為處理單元，在所有對象之間進行比較，除去不可見部分。物空間消隱多用于線消隱，也用于面消隱。像空間消隱以構成圖形的每一個像素為處理單元，針對場景中所有在該像素上有投影的表面，確定其中相對于觀察點的可見表面，用該表面顏色填充該像素。像空間消隱多用于面消隱。

自從Robert于1963年提出處理隱藏線、Weiler等于1977年提出處理隱藏面的算法以來，消隱算法層出不窮。針對現有大量的針對消隱處理的文獻研究，往往采用像空間、物空間、像空間和物空間結合這三個分類。

針對基于像空間的諸多消隱算法，其中Z緩沖器算法最為有名，它也是最為目前常用的作用于像空間的隱藏面消除算法，它在工業界被廣泛采用，可通過硬件實現。例如，OpenGL作為工業界事實上的標準，其采用的就是Z緩沖器算法。針對基于像空間的消隱算法，以像素為基本研究單位，與完全基于物空間的消隱算法相比其涉及計算幾何內容較少，其本質上屬于圖形圖像學領域。故而，完全基于像空間的消隱算法、結合像空間和物空間的消隱算法不是本發明的研究重點，基于物空間的消隱算法才是本發明的借鑒對象。

此外，針對完全基于像空間、結合像空間和物空間的消隱方法，它們的算法復雜度與環境復雜度無關(如與三維實體包含了多少面片、多少線段無關)，只與輸出設備的像素分辨率有關，故而無法在圖像縮放時依然保持足夠清晰度，可視化效果不理想；相對的，針對完全基于物空間的消隱方法(包括Apprel方法、Loutrel方法、Galimberti方法、Mononari方法等)的空間復雜度，都與環境復雜度的平方呈現正相關，在圖像縮放時依然保持足夠清晰度，可視化效果理想。這也是本發明的重點參考對象是基于物空間的消隱方法的原因。

按照不同消隱客體分類，還包括針對機械零件、針對曲面、針對地形、針對地質柵欄等消隱。還有許多研究關注如何設計應用于消隱的數據模型或數據結構，基于現有不同數據結構能夠實現一定程度的物空間消隱，但各自存在局限性，因為受本身數據結構的局限較大(之后詳述)。

由上可見，有的研究注重消隱方法的輸入數據類型(如針對機械零件、針對曲面、針對地形、針對地質柵欄)，有的研究注重輸出結果的表達形式(如P緩沖器算法中輸出結果的不同類型表達)，有的研究注重應用于消隱的數據結構設計(如半邊結構、B-rep結構、B-rep與CSG結合、有限元組織形式)，更多的研究關注消隱方法的設計原理(如各類物空間算法、像空間算法、物空間與像空間結合算法)。