移動圖形漸進傳輸引擎技術的製作方法
2023-05-29 20:00:16
專利名稱：移動圖形漸進傳輸引擎技術的製作方法
技術領域：
本發明涉及一種用於移動環境中的圖形漸進傳輸引擎系統。
背景技術：
1.圖形引擎和三維圖形應用程式接口圖形引擎又稱三維圖形加速引擎。隨著計算機軟、硬體突飛猛進的發展，計算機圖形學在各個行業的應用也得到迅速普及和深入。目前計算機圖形學已進入三維時代，三維圖形在人們周圍無所不在。
科學可視化、計算機動畫和虛擬實境已經成為近年來計算機圖形學的三大熱門話題，而這三大熱門話題的技術核心均為三維圖形。三維真實感圖形的生成一般包括場景造型、取景變換、視域裁剪、消除隱藏面及光強亮度計算等步驟，底層軟體都包括相應的算法實現。目前比較常見的三維圖形生成環境等都提供了相關API，使得軟體人員能方便地創建真實的三維場景。
三維圖形應用程式接口又寫作3D API(Three-Dimension ApplicationProgramming Interface)，是許多程序接口的集合。編程人員在設計3D軟體時，只要調用其API內的程序接口，即可通過API直接調用3D圖形加速晶片內的硬體運算能力，節約CPU資源，從而大幅度提高3D程序的設計效率。目前普遍應用的3D API有DirectX、OpenGL、Glide、Heidi等。
DirectX是微軟公司專為PC遊戲開發的API，與Windows 9X和Windows NT作業系統兼容性好，容易控制，可繞過圖形顯示接口(GDI)直接進行支持該API的各種低層操作，大大提高了遊戲的運行速度。Direct 3D是微軟公司多媒體應用軟體DirectX開發庫中的一個子系統，由一組底層和高層API組成，運行於Windows平臺，該圖形庫是以COM接口形式提供的，較為複雜，目前只能在Windows平臺上運用。
OpenGL(開放式圖形接口)是由Silicon Graphics公司開發，支持Windows9X、Windows NT、Macos、Beos、OS/2以及Unix等作業系統。OpenGL一直用於高檔圖形工作站，其3D功能很強，超過Directx，能最大限度地發揮3D晶片的巨大潛力。在OpenGL的1.2版中增加了對3DNow！標準的支持。
Glide是3Dfx(現在已被nVIDIA公司收購)為VOODOO系列3D加速卡設計的專為3D的API，可以最大限度發揮VOODOO系列晶片的3D圖形處理功能，由於不考慮兼容性，其工作效率遠比OpenGL和Direct高，所以Glide是各3D遊戲開發商的優先選用。
Heidi是一個由Autodesk公司提出來的規格。目前採用Heidi的應用程式包括3D Studio MAX動畫製作程序，Autodesk公司為AutoCAD開發的WHIP加速驅動程序。
2.圖形漸進傳輸技術(1)網格圖形的化簡和加細隨著科學技術的進步，在計算機圖形學、虛擬實境、計算機輔助設計技術、地理信息系統、醫學圖像系統等領域所構造和使用的模型越來越精細、越來越複雜，這些複雜的模型動輒就產生數以百萬計的面片，而史丹福大學的數字米開朗基羅計劃(digital Michelangelo project)中著名的大衛(David)雕像的三角面片更是高達20億。這些複雜的模型對計算機的存儲容量、處理速度、繪製速度、傳輸效率等都提出了很高的要求，然而在很多情況下，高解析度的模型並不總是必要的，模型的準確度以及需要處理的時間需要達到一個折衷點，因此必須用一些相對簡單的模型來代替原始模型，這就是對模型進行簡化。模型化簡是在保持原模型幾何形狀不變的前提下，採用適當的算法減少該模型的面片數、邊數和頂點數。化簡對於幾何模型的存儲、傳輸、處理，特別是對實時繪製有著重要的意義。早在20世紀70年代，就有學者討論網格模型的化簡問題，到90年代後，網格化簡得到了深入的研究，並出現了許多成功的應用。
網格模型化簡算法分類有多種，如根據拓撲結構是否保持可以分為拓撲結構保持形和非拓撲結構保持形；根據模型簡化的過程可以分為逐步求精和幾何化簡；根據誤差可控性可分為誤差受限和誤差不受限；根據視點相關性可以分為視點無關的化簡和視點相關的化簡。
由於網格模型大部分由三角面片表示，而且即使原始模型不是三角面片，也可以對其進行三角化，因此網格模型簡化的本質是在儘可能保持原始模型特徵的情況下，最大限度地減少原始模型的三角形和頂點的數目。通常包括兩個原則頂點最少原則，即在給定誤差上界的情況下，使得簡化模型的頂點數最少；誤差最小原則，給定簡化模型的頂點個數，使得簡化模型與原始模型之間的誤差最小。
網格模型的加細可以視作是網格化簡的逆過程，通過定義合適的化簡與加細算法，可以實現網格模型的無損化簡和恢復，這也是本文所要討論的一個重點。
(2)細分曲面模型和多解析度顯示細分曲面模式在三角網格簡化中的典型應用是構造多分辯率表示。
細分曲面(Subdivision surfaces)是一個網格序列的極限，網格序列則是通過採用一組規則(一般是加權平均)在給定初始網格中插入新頂點並不斷重複此過程而獲得。這種方法克服了參數曲面處理任意拓撲網格(Arbitrary topology meshes)存在的困難。因為，在不規則拓撲處只須採用特殊的細分規則就可以了，不存在拼接的問題。
另一方面，由於三維掃描儀(3D Scanner)、測距儀(Range finder)和CT等三維數據獲取設備的日益完善，為幾何形狀不能或難於用分析曲面表示的對象建模提供了有力的工具，例如醫學的人體器官建模、考古學中的古代器件和藝術領域的雕塑作品三維重構等等，離散曲面逐漸成為一種重要的幾何表示方法。細分模式作為從給定規則產生離散曲面的方法統一了傳統的參數曲面與多邊形兩種實體表面的表示。另外，由於實驗獲取的三維數據量一般都非常大，多解析度分析(Multiresolution analysis)成為有效地處理這類數據的重要手段。細分方法與多解析度分析、小波變換(Wavelet transformation)之間的深刻聯繫也是目前細分模式受到關注的一個重要原因。
在計算機圖形學、幾何造型及逆向工程等應用領域，往往採用大規模甚至超大規模的多邊形網格來表示複雜對象的表面形狀。從數據的獲取、處理到傳輸都面臨巨大的挑戰。多解析度模型(Multiresolution modeling)正是為了解決這樣的問題而提出的。所謂多解析度模型是一種曲面表示方法，這種表示可以支持物體表面從粗糙到細緻的各個層次的重構。按照這一定義，層次細節模型、累進網格表示都屬於多分辨模型。總的來說，各種文獻對多解析度分析和累進網格兩個概念的使用還是比較混亂。
層次細節模型(Level of Detail，縮寫為LOD)同時保存有物體的若干個從粗到細的幾何模型，因此不同模型間過渡時會出現跳躍，通過兩不同層次模型間的插值可起到平滑過渡的作用。對於網格模型而言，各種簡化算法如Schroeder的基於頂點刪除算法、Hoppe的基於能量優化方法、Hermann的基於三角形收縮方法和Garland的基於點對摺疊方法等等都可以用來構造LOD模型。
層次細節模型需要保存多個版本的數據，佔用比原始數據大得多的存儲空間，而且在不同細節模型間轉換時會出現跳躍現象，為此Hoppe提出累進網格模型(Progressive meshes)把任意拓撲網格表示為一種高效、無損且具有連續解析度的編碼。該編碼由一個粗糙的基網格和一系列細化變換組成。累進網格模型支持基於幾何變形(Geomorph)的平滑視覺過渡、累進傳輸、網格壓縮和適應性細化。接著Hoppe又提出了依賴於視點的累進網格模型，使得重構過程可以根據視點位置只對視錐內的部分進行細化，對於視錐外的部分則保持粗網格。Popovic和Hoppe利用更一般的細化技術構造累進網格，從而可以處理任意的三角剖分模型(如任意維數、無向、非流形、非正則模型)而且基網格總是一個頂點，不象原來的累進網格那樣當網格拓撲很複雜時基網格也很複雜，他們把這稱之為累進單純復形(Progressive simplicial complexes).Khodakovsky等人則把累進網格的思想應用到網格幾何壓縮(Geometry compression)。
上面的表示大型網格數據的方法都是基於點、邊或三角形面刪除的三角網格簡化算法，難於事先估計誤差界，表示也不夠緊湊，而且不能支持多尺度編輯，因此人們轉向研究基於小波的多辨率分析和細分曲面的表示方法。
(3)J2ME技術什麼是J2ME？當JAVA平臺發展到JAVA 2的版本以後，為了適應不同級別計算機硬體的開發需要，JAVA平臺形成了三個主要分支Java 2，Standard Edition(J2SE)，Java 2，Enterprise Edition(J2EE)，Java 2，Micro Edition(J2ME)準確地說，J2ME是為了支持象PDA、手機等小型的嵌入式或行動裝置而推出的一系列的技術和規範的總稱。J2ME針對嵌入式和行動裝置，提供了開發和運行應用程式的平臺，隨著新的規範的不斷推出和眾多製造商、軟體開發商的支持，J2ME正在飛速向前發展。
3.該傳輸引擎運行的硬體條件1)遊戲引擎的開發環境·普通臺式機，要求的基本配置·30MB hard disk·64MB system RAM·166MHz CPU·其硬體條件支持以下其中一個系統即可оMicrosoft Windows NT or Microsoft Windows 2000оMicrosoft Windows 98оSolarisTM8оLinux2)傳輸引擎的運行環境1.符合CLDC 1.0以及MIDP 1.0以上的帶有Java平臺的行動裝置2.256色或以上彩屏3.帶64k或以上內存
4.移動圖形漸進傳輸引擎根據以上的介紹，圖形的漸進傳輸的定義即是一個通過特定方法對原始圖形進行化簡、構造多解析度模型、提取細節特徵和誤差偏移量、逐步傳輸多解析度模型、添加細節特徵、修正誤差偏移量的過程，這個過程往往通過反覆的迭代，以獲得逐步精確的原始圖形。
本引擎目前是構建於Java平臺上，通過調用Java API結合特定算法實現。
5.相關產品和專利在PC平臺上的圖形圖像傳輸引擎已相對比較成熟，但針對於移動通信平臺上的在這一領域的研究很少，在專利檢索中對該技術的闡述並不多，我們在移動圖形漸進傳輸引擎技術上的研究很好的補充了專利空白。
行動裝置具體有以下兩個缺點1、運算速度不快，存儲空間不大，軟硬體平臺差異性大，顯示屏幕較小等；2、面對行動裝置的圖形顯示和傳輸應用設計剛起步，在與傳輸效率和顯示效果的平衡方面進行深入研究的較少。而以往的面對行動裝置的圖形傳輸產品中，一般採用直接傳輸技術。直接傳輸技術的優點有技術簡單，程序處理比較容易實現，配置內容較少，文件佔空間也較少，適合行動裝置空間小的特點。其缺點是傳輸速度完全依賴行動網路速度，無法實現圖形的逐步顯示，讓使用者有較長的等待時間，且容易在傳輸中斷後丟失傳輸內容，造成不必要的重傳。
發明內容
行動裝置有著資源相對貧乏，運算能力弱，傳輸帶寬小的缺點，而行動裝置在人們日常生活中所扮演的角色也越來越重要，為了緩和日益增長的數據傳輸需求與相對狹窄的網絡帶寬之間的矛盾，本發明提出了一種專門針對移動環境特點的圖形漸進傳輸引擎。該引擎的內容包括對複雜網格圖形的化簡、漸進傳輸和細節恢復等過程，並可推廣到具備網格性質的任意粒子系統上。
所述的移動圖形漸進傳輸引擎技術，包括對原始圖形進行化簡、構造多解析度模型、提取細節特徵和誤差偏移量、逐步傳輸多解析度模型、添加細節特徵、修正誤差偏移量的過程。
該引擎根據用戶設置的大致網絡傳輸速度，自動選擇一個圖形簡化算法和圖形層次，然後根據選定的算法逐步消去原始圖形中的部分頂點，並記錄模型簡化過程中原頂點和新頂點位置以及頂點間的連接關係的變動信息，從而生成了一個由原始模型的最簡化模型和一系列簡化信息組成的漸進網格表示模式進行傳輸；在接收終端實時繪製時，通過逆向跟蹤簡化信息序列，對每條簡化信息執行逆操作，逐步恢復所刪除的模型細節，實時得到原始模型的連續精度的簡化模型，並由此實現了多層次細節模型的平滑過渡。
上述的每一層網格都包括以下一些數據，但原始網格不包括誤差信息(i)層的標識(ii)網格數據，包括(a)頂點數目和每個頂點的坐標(b)面的數目和每個面的頂點序列(iii)誤差數據，包括誤差的數目和誤差信息，包括(a)誤差的標識，以確定誤差的修正目標頂點(b)誤差向量的坐標(c)兩個頂點的序列，以標識下一層的誤差位置漸進網格數據存放在數據鍊表中，接收終端通過逐次合併最後一層的網格數據和中間層的誤差數據，最終恢復出原始網格。
本發明所述的移動圖形漸進傳輸引擎的特點有以下兩方面1)可分步驟傳輸初始網格和細節層次，以達到減少單次傳輸量和提升顯示效果的目的。
2)可適用於行動裝置、智能家居、嵌入式設備等的環境，對系統的處理能力和網絡傳輸能力要求不高。
3)思路簡單，合理4)適應更多行動裝置硬體要求移動圖形漸進傳輸引擎系統是適用於嵌入式系統和手持行動裝置(手機、PDA等)上的，通過獨特的傳輸機制進行圖形的化簡、壓縮、編碼、傳輸、解碼、解壓、加細、恢復等一系列過程的傳輸管理模塊。使用者或其他功能模塊可方便地通過調用該傳輸引擎完成行動裝置等上的圖形漸進傳輸。
圖1為蝶形細分模式的面具；圖2為網格圖形中的黑色消去點圖示圖3為漸進網格的鍊表存儲格式；圖4球體的漸進化簡實例；圖5一個漸進網格圖形和誤差值的實例，其中，上方的圖是各個逐步簡化的網格圖形，其下方的圖是該網格圖形與前一層次的網格圖形的誤差。
具體實施例方式
1)移動圖形漸進傳輸引擎的基本結構對於使用者來說，本引擎相當於一個應用程式接口可供調用，用戶可設置大致的網絡傳輸速度，由引擎自動選擇一個圖形簡化算法和圖形層次。本引擎將根據選定的算法逐步消去原始圖形中的部分頂點，並記錄模型簡化過程中原頂點和新頂點位置以及頂點間的連接關係的變動信息，從而生成了一個由原始模型的最簡化模型和一系列簡化信息組成的漸進網格表示模式，漸進網格可以把任意拓撲的計算機網格圖形表示為一種高效、無損且具有連續解析度的編碼。在實時繪製時，通過逆向跟蹤簡化信息序列，對每條簡化信息執行逆操作，可以逐步恢復所刪除的模型細節，實時得到原始模型的連續精度的簡化模型，並由此實現了多層次細節模型的平滑過渡。
2)一種具體的實施方式-蝶形逆細分化簡算法，本算法僅僅是一種舉例，並不限制本發明的保護範圍，其他簡化算法包括邊裁剪法、點消去法和半邊裁剪法等也可以採用。
圖1是蝶形細分模式的生成面具，由圖中Q1，Q2，Q3，Q4，P1，P2，P3，P4共8點根據公式(1)可生成新的細分頂點PiPi=116[8(P1+P2)+2(P3+P4)-(Q1+Q2+Q3+Q4)]---(1)]]>下一步可通過公式(2)將一次化簡操作中的保留點和消去點區分開，將消去點表示為Odd1，保留點表示為Even1(Evenj-1，Oddj-1)＝Split(Mj) (2)如圖2中的黑色網格頂點均為消去點在正式刪除消去點之前，我們還需要計算消去點的相對位置並保存。消去點可根據周圍的若干個保留點，通過蝶形細分面具計算而得到一個近似點，通過公式(3)計算得到近似點和消去點之間的誤差，操作符P表示以公式(1)或改蝶形細分面具。
ej-1＝Oddj-1-P(Evenj-1) (3)為了減小几何誤差，我們還將定義一個新算子U來更新消去點周圍的保留點，那麼此次化簡後的網格Mj-1可由公式(4)得到Mj-1＝Evenj-1-U(ej-1)(4)ei是在公式(3)中計算得到的下面分析算子U的取法，從公式(1)可知Pi=12(P1+P2)+18(P3+P4)-116(Q1+Q2+Q3+Q4)---(5)]]>ΔP是對原始網格進行編輯前後的頂點P的誤差，由公式(5)可知根據距離P1的不同每個周圍點對誤差調整的影響權值也存在差異，而對距離大於3的周邊點的影響力不予考慮。
因此算子U的取法如公式(6)U(e)=valence(12e1+18e2-116e3)---(6)]]>λ是調整係數，這次取值為2，valence是每個將被更新的保留點的價，e′，i＝1，2，3表示距離保留點距離分別是1，2，3的消去點所產生的預測誤差。
網格的恢復可很快地通過下面的步驟實現
(1)回滾更新操作Evenj-1＝Mj-1-U(ej-1)(2)回滾預測操作Oddj-1＝ej-1+P(evenj-1)(3)合併誤差項Mj＝Merge(Evenj-1，Oddj-1)以上的算法可以實現原始網格的無損化簡和恢復。
漸進傳輸的實現即通過重複利用上述算法，將一個稠密網格M＝Mn逐步簡化為稀疏網格M0，如公式(7)所示Mn→Mn-1→Λ→M0(7)每一層網格都包括以下一些數據，但原始網格不包括誤差信息(i)層的標識(ii)網格數據，包括(a)頂點數目和每個頂點的坐標(b)面的數目和每個面的頂點序列(iii)誤差數據，包括誤差的數目和誤差信息，包括(a)誤差的標識，以確定誤差的修正目標頂點(b)誤差向量的坐標(c)兩個頂點的序列，以標識下一層的誤差位置漸進網格數據存放在如圖3所示的數據鍊表中，通過逐次合併最後一層的網格數據和中間層的誤差數據，最終可以恢復出原始網格。
當接收端收到最後一層的網格數據時，已可以顯示出較為粗糙的網格模型，如需要更精細的視覺效果，則可以逐步添加中間層的誤差數據。假如傳輸的原始網格是M0，通過一次分解可分為M1和第一次分解後的誤差S1，M1可通過同樣的方式分解為M2和S2，依此類推，最終得到Mn和一系列誤差Sn，Sn-1，Λ，S2，S1。進行漸進傳輸時，首先傳送簡化後的基礎網格Mn，再依次傳輸Sn，Sn-1，Λ，S2，S1，合併Mn和Sn可得到Mn-1，此時的顯示效果已經比基礎網格Mn有所提高；同理再合併Mn-1和Sn-1可得到Mn-2，進一步改進顯示效果，依次逐步合併下去，最終得到原始網格M0，此時整個漸進傳輸過程完成。
3.
與實施例下面是該引擎開發的細分圖形的傳輸過程Demo程序，
其中的兩個
圖4表示一個球體的漸進化簡和表示的過程，而圖5同時也將每次化簡所提取出的誤差值在圖形下方也表示了出來。圖4中，經過每次化簡後，從左往右每個圖形的表示多邊形數目是遞減的，從而有效地減少了圖形的表示數據量，達到減少傳輸信息的目的。
圖5中，經過每次化簡後，從左往右每個圖形的表示多邊形數目也是遞減的，同時也將被提取出來的誤差信息表示在每個圖形的下方，通過逆向合併中間圖形和誤差量，可以最終恢復為原始圖形。
圖形的化簡層次是根據當時網絡狀況和用戶選定的參數決定的，在發送端完成簡化後，才可以逐步傳輸基礎網格圖形和誤差量。
權利要求
1.一種移動圖形漸進傳輸引擎技術，包括對原始圖形進行化簡、構造多解析度模型、提取細節特徵和誤差偏移量、逐步傳輸多解析度模型、添加細節特徵、修正誤差偏移量的過程。
2.按權利要求1所述的移動圖形漸進傳輸引擎技術，其特徵在於該引擎根據用戶設置的大致網絡傳輸速度，自動選擇一個圖形簡化算法和圖形層次，然後根據選定的算法逐步消去原始圖形中的部分頂點，並記錄模型簡化過程中原頂點和新頂點位置以及頂點間的連接關係的變動信息，從而生成了一個由原始模型的最簡化模型和一系列簡化信息組成的漸進網格表示模式進行傳輸；在接收終端實時繪製時，通過逆向跟蹤簡化信息序列，對每條簡化信息執行逆操作，逐步恢復所刪除的模型細節，實時得到原始模型的連續精度的簡化模型，並由此實現了多層次細節模型的平滑過渡。
3.按權利要求2所述的移動圖形漸進傳輸引擎技術，其特徵在於每一層網格都包括以下一些數據，但原始網格不包括誤差信息(i)層的標識(ii)網格數據，包括(a)頂點數目和每個頂點的坐標(b)面的數目和每個面的頂點序列(iii)誤差數據，包括誤差的數目和誤差信息，包括(a)誤差的標識，以確定誤差的修正目標頂點(b)誤差向量的坐標(c)兩個頂點的序列，以標識下一層的誤差位置漸進網格數據存放在數據鍊表中，接收終端通過逐次合併最後一層的網格數據和中間層的誤差數據，最終恢復出原始網格。
全文摘要
本發明公開了移動圖形漸進傳輸引擎技術，其包括對原始圖形進行化簡、構造多解析度模型、提取細節特徵和誤差偏移量、逐步傳輸多解析度模型、添加細節特徵、修正誤差偏移量的過程。本發明所述的移動圖形漸進傳輸引擎系統是適用於嵌入式系統和手持行動裝置(手機、PDA等)上的，通過獨特的傳輸機制進行圖形的化簡、壓縮、編碼、傳輸、解碼、解壓、加細、恢復等一系列過程的傳輸管理模塊。使用者或其他功能模塊可方便地通過調用該傳輸引擎完成行動裝置等上的圖形漸進傳輸。
文檔編號G06T1/00GK1738247SQ200510035178
公開日2006年2月22日 申請日期2005年6月15日 優先權日2005年6月15日
發明者羅笑南, 胡秋生, 張勤, 周建國, 陳任, 張大捷 申請人:中山大學, 深圳Tcl工業研究院有限公司