一種交互式呈現(xiàn)漸進網(wǎng)格算法

求 偉， 張 帆

（武警杭州指揮學院，杭州 310023）

0 引言

計算機圖形學中，常用Hoppe提出的漸進網(wǎng)格數(shù)據(jù)結構實現(xiàn)對復雜模型的細節(jié)分層。漸進網(wǎng)格由一個粗略的基網(wǎng)格和逐漸增加細節(jié)內容到網(wǎng)格中去的頂點分裂信息兩部分組成。漸進網(wǎng)格可以基于觀測標準，根據(jù)需要把細節(jié)加入到網(wǎng)格中，減少呈現(xiàn)時間；能在不同細節(jié)層次間實現(xiàn)光滑變化等等。然而，漸進網(wǎng)格數(shù)據(jù)必須同時全部裝入內存，在呈現(xiàn)包含上百萬個三角網(wǎng)格模型時，可能需要幾個G內存空間，超出了當前許多機器主內存；另外大模型產(chǎn)生漸進網(wǎng)格耗時長。網(wǎng)格適應內存需求，不僅是簡單的理論問題。本文從不把整個模型裝入內存出發(fā)，在呈現(xiàn)方面進行了改進：通過系統(tǒng)平臺裝載當前需要的細節(jié)數(shù)據(jù)，減少內存需求，加快呈現(xiàn)速度，同時又不以輸出品質為代價，實現(xiàn)漸進網(wǎng)格交互式呈現(xiàn)模型快速算法。

1 有關研究

交互式呈現(xiàn)呈現(xiàn)大模型方面技術有很多，如結構預排和點呈現(xiàn)。許多結構預排算法，不必把整個模型數(shù)據(jù)裝載入內存，允許對模型進行交互；把數(shù)據(jù)放入分級結構中，執(zhí)行內存管理，在適當?shù)臅r間預取數(shù)據(jù)。重點在對內部重建上，模型通常由離散小片組成。因為典型地使用靜態(tài)標準表示細節(jié)，有很多的解決方法，內存管理較容易。最后，依靠厚度可見選擇，使用方法對內部進行處理。本算法在許多方面不同于結構預排，如模型由大塊組成，采用連續(xù)變化的細節(jié)分層，而在厚度方面沒有設計要求。點呈現(xiàn)技術使用點代替多邊形呈現(xiàn)基本的原始的網(wǎng)格，是呈現(xiàn)大模型一個相當困難的技術。僅管已經(jīng)有一些算法成功把這一技術應用于大模型，但得到的圖象質量與采用多邊形表示的還是有所不同，不一定能滿足某些特殊要求。而且，現(xiàn)有的用于多邊形呈現(xiàn)模型的加速器或設備驅動程序優(yōu)化技術，不能優(yōu)化點呈現(xiàn)。

2 交互式呈現(xiàn)設計

漸進網(wǎng)格可能包含了很多的細節(jié)，數(shù)量非常大，不能適應主存儲器，其實用戶需求可能沒有那么多，并不需要把整個網(wǎng)格裝載入內存。例如，觀測者離網(wǎng)格很遠，可以只用基網(wǎng)格表示模型；需要放大網(wǎng)格的某一部分，只要裝載特定部分的細節(jié)等等。因此，考慮視點位置和屏幕空間誤差，給定特定的位置和方向，在呈現(xiàn)時，只要裝載漸進網(wǎng)格需要的部分，減少內存需求。接下來只要解決：怎樣快速決定網(wǎng)格需要裝載的部分；怎樣裝載和卸載網(wǎng)格，防止編碼訪問網(wǎng)格當前不用裝載的部分。

2.1 模型前期處理

簡單介紹模型前期處理，使用可以處理任意網(wǎng)格的Voronoi結構分割原始網(wǎng)格，輸入時把模型分成相鄰小塊，同時對每一塊進行簡化；在分級時，把已簡化的分塊合并成原來大的塊。算法如下：

1）給定一個需要縫合的分塊列表。在同一時間處理這些輸入塊，每遇到一個頂點就基于它的位置把它加入表中。2）如果這個點已存在表中，那么這個點是雙重點，如在同一塊中被兩個面使用，或在邊界上被多個塊用到的點，對雙重點進行處理。3）如果一個頂點不是雙重點，那么給它指派一個ID。如果是雙重點，使用前面已指派過的ID。這樣，合并后網(wǎng)格與原始網(wǎng)格具有相同頂點，可順利地被調配，再次作為獨立頂點處理。

要注意的是，不能簡化塊邊界，如果允許簡化邊界，分塊邊拓撲會改變，而點和面相對線性無關，簡化算法也會失敗。合并處理無論在運行時間還是內存使用上都相當有效，采用表檢測雙重點只裝載一次基網(wǎng)格，占用時間少，內存使用也小。通常在最后內存需求最大，因為頂點分裂作為合并后的結果已發(fā)生了改變，必須進行重新編號后，還有面ID值。當然，對于要求不高的情況下，這一步也可以省略，或是以后的一個改進方向。

2.2 確定裝載對象

理想狀態(tài)下，給定一個觀測點，主存儲器要包含需要精確呈現(xiàn)的面和點。通常需要對網(wǎng)格逐面進行判斷確定裝載和卸載的數(shù)據(jù)，效率非常低。決定裝載哪些面需要很大開銷，每次裝載和卸載一個面設計不合理。另外，維持一致的數(shù)據(jù)結構會變得非常復雜。算法考慮不依靠面，在塊呈現(xiàn)上對數(shù)據(jù)進行裝載和卸載處理。在分塊層級上精化塊，簡化單個分塊時，輸出一系列頂點分裂。漸進網(wǎng)格中面、頂點和頂點分裂關系如圖1所示。

圖1 面、頂點和頂點分裂數(shù)組及分層呈現(xiàn)關系

每一層細節(jié)呈現(xiàn)，只是作為漸進網(wǎng)格面、頂點和頂點分裂這些數(shù)組中的一組元素進行存儲。明確觀測者的位置和方向，進行可見性檢查，確定網(wǎng)格中每一個分塊是否需要裝載。一個塊僅在：分塊位置可見或用戶需要分塊中的細節(jié)兩種情況下裝載。第二種情況與屏幕允許空間誤差容忍量，塊的最大殘留，觀測者和塊間最小距離等因素有關。確定最大誤差和最小距離的目的是防止裝載過于詳細的信息，而對觀測者位置來說微不足道。

確定當前是否要裝載一個分塊細節(jié)以外，在一定范圍內基于觀測者位置和方向會發(fā)生變化，還要確定在可能變化范圍內，下一步裝載分塊細節(jié)，在需要時裝載預取的塊細節(jié)?？紤]觀測位置和方向變化、確定可見性、最大誤差和最小距離等因素，需要大量計算，影響預取數(shù)據(jù)速度，精確要求卻不高?？梢愿鶕?jù)每個分塊都是一個立方體，對分塊細節(jié)設定一個近似空間范圍，在最后進行少量相交測試簡化計算。實驗數(shù)據(jù)表明這樣的處理是有效的，可以達到快速決定分塊細節(jié)是否需要裝載的目的。進行這個簡單測試后，在每個畫面呈現(xiàn)之前對所有的網(wǎng)格分塊細節(jié)進行循環(huán)，決定哪一塊裝載和卸載，工作量的大小和塊細節(jié)的數(shù)量有關。

2.3 裝載和卸載數(shù)據(jù)

確定一個分塊細節(jié)需要在內存處理后，執(zhí)行裝載和卸載，要保持數(shù)據(jù)結構的一致性，防止訪問沒有裝載的部分。漸進網(wǎng)格的數(shù)據(jù)結構粗略地組織如圖1所示，平行排列面，頂點和頂點分裂信息。每個頂點分裂有兩個面索引和兩個頂點索引與之相關聯(lián)。分塊細節(jié)按順序存儲，可以看作是行里的列元素，而裝載和卸載分塊細節(jié)可以看作是裝載和卸載數(shù)組的某個部分。對局部數(shù)組裝載，使用函數(shù)VirtualAlloc()和VirtualFree()，允許存儲整個數(shù)組虛擬地址空間，然后指派和釋放大量內存。單個塊細節(jié)呈現(xiàn)則使用鄰近區(qū)域的虛地址空間，因為要考慮減少內存沖突的可能性；以及不通過間接分層，訪問數(shù)組里特定元素。

下面是裝載一個分塊細節(jié)的步驟：

1）使用VirtualAlloc()給數(shù)組中需要的行指派內存；

2）在數(shù)據(jù)文件中尋找分塊細節(jié)的開始處，讀取數(shù)據(jù)，寫入數(shù)組，位置在網(wǎng)格文件第一次裝載時已存儲；

3）對每個裝載的頂點，更新父頂點表示當前可以進行分裂。也就是它的子頂點都裝載進內存了，而每個父頂點的ID是存貯在硬盤數(shù)據(jù)文件中的。

卸載一個分塊細節(jié)類似，步驟如下：

1）對每一個要卸載的頂點，更新父頂點，表示它不能進行分裂，也就不必裝載相關的子頂點和面。

2）使用VirtualFree()給數(shù)組中需要的行釋放內存。

要注意的是，利用虛地址空間來存儲數(shù)組，整個網(wǎng)格大小受到可用的地址空間數(shù)量的限制。在32位以下的操作系統(tǒng)，網(wǎng)格大小不能超過2GB，64位以上則不受這個限制，當前硬件技術的發(fā)展可以完全不受這一限制影響。

3 呈現(xiàn)結果

本算法呈現(xiàn)過程中，內存使用比其它裝載整個網(wǎng)格的算法要低。呈現(xiàn)效果需要使用多種的數(shù)據(jù)檢測，也會因很多因素而不同，如觀測者的需要，創(chuàng)建網(wǎng)格時塊尺寸的選擇、簡化參數(shù)的使用等。在一個特定觀測場合試驗，如圖2，依次為觀測者由遠至近移動位置顯示的圖片效果，以及呈現(xiàn)的面和所需的內存，沒有裝載模型中不需要呈現(xiàn)的部分，減少了內存使用，結果表明使用部分數(shù)組裝載得到了預期效果。

圖2 觀測者由遠至近移動位置顯示的圖片效果

呈現(xiàn)速度方面，部分數(shù)組每一塊需要被裝載時，如果每塊細節(jié)特別小會引起一個短暫停，可通過執(zhí)行塊異步塊裝載設計消除。簡化預處理時，所做的一些選擇，也會直接影響呈現(xiàn)結果。在分塊大小以及一些參數(shù)等方面進行認真選擇很有必要，否則，可能會出現(xiàn)一個非常大的基網(wǎng)格，或是在每一分塊呈現(xiàn)太多太少的數(shù)據(jù)，反而可能降低呈現(xiàn)速度。

4 結束語

當前呈現(xiàn)時沒有限定內存，如果在這方面進行一定研究，將會帶來更多便利?？紤]可以動態(tài)調整屏幕空間誤差，當可用內存變低時就逐漸增加，減少裝載塊呈現(xiàn)。另外，考慮觀測者的速度和加速度，改進塊裝載和卸載設計，呈現(xiàn)將可能只需要預取塊，對合理使用系統(tǒng)內存更有效。

[1] Hoppe H,Progressive meshes,ACM SIGGRAPH 96 Conference Proceedings,ACM SIGGRAPH,1996,99–108,121–26.

[2] Stephan Bischoff, Leif Kobbelt, Teaching meshes,subdivision and multiresolution techniques,Computer-Aided Design 36 (2004)1483–1500.

[3] Josef Kohout, Selected Problems of Parallel Computer Graphics,Technical Report No.DCSE/TR-2004-02,March,2004.

[4] Hong Tzong Yau,Chuan Chu Kuo,Chin Hsiung Yeh,Extension of surface reconstruction algorithm to the global stitching and repairing of STL models,Computer Aided Design 35(2003)477-486.

[5] Peter Szinek,Optimized Subdivision Surface Displaying,Master Thesis of Comenius University Bratislava, Faculty of Mathematics,Physics and Informatics,Department of Geometry,Bratislava,April 2003.

[6] 鄭君立,海量數(shù)據(jù)點三維重構關鍵技術研究與應用[D].東南大學,2003.

[7] 陳濤.逆向工程中數(shù)據(jù)分塊和規(guī)則曲面擬合算法的研究[D].南京航空航天大學,2004.

[8] 王霄.逆向工程技術及其應用[M].化學工業(yè)出版社,2004.

[9] 戴靜.逆向工程數(shù)據(jù)處理關鍵技術研究[D].南京理工大學,2003.

[10]張杰.由散亂點生成三角網(wǎng)格曲面的算法研究與實現(xiàn)[D].北京大學,2003.