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

求 偉， 張 帆

（武警杭州指揮學(xué)院，杭州 310023）

0 引言

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

1 有關(guān)研究

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

2 交互式呈現(xiàn)設(shè)計(jì)

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

2.1 模型前期處理

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

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

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

2.2 確定裝載對(duì)象

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

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

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

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

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

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

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

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

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

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

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

1）對(duì)每一個(gè)要卸載的頂點(diǎn)，更新父頂點(diǎn)，表示它不能進(jìn)行分裂，也就不必裝載相關(guān)的子頂點(diǎn)和面。

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

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

3 呈現(xiàn)結(jié)果

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

圖2 觀測(cè)者由遠(yuǎn)至近移動(dòng)位置顯示的圖片效果

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

4 結(jié)束語(yǔ)

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

[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ù)點(diǎn)三維重構(gòu)關(guān)鍵技術(shù)研究與應(yīng)用[D].東南大學(xué),2003.

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

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

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

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