基于虛擬場(chǎng)景的繪制算法★

趙瑩，韓燮

(中北大學(xué)電子與計(jì)算機(jī)科學(xué)技術(shù)學(xué)院， 山西 太原 030051)

0 引言

近年來(lái)隨著計(jì)算機(jī)圖形、圖像學(xué)技術(shù)的發(fā)展，虛擬場(chǎng)景的構(gòu)建已取得了較好的效果，但構(gòu)建大規(guī)模且復(fù)雜的虛擬場(chǎng)景仍是耗時(shí)費(fèi)力的工作。針對(duì)虛擬場(chǎng)景耗時(shí)費(fèi)力的問(wèn)題，點(diǎn)繪制技術(shù)引起人們的關(guān)注，它具有基于幾何繪制方式的繪制質(zhì)量、靈活性和內(nèi)存需求和基于圖像繪制方式的繪制速度。但點(diǎn)繪制仍然存在許多不足之處，考濾到物體還有其它不同的構(gòu)成形式例如面和體數(shù)據(jù)，由此可以研究以不同的元素作為繪制的基元，來(lái)提高存儲(chǔ)效率、繪制性能、繪制質(zhì)量等，使構(gòu)建的虛擬場(chǎng)景呈現(xiàn)出更真實(shí)的效果。

1 點(diǎn)繪制

基于幾何模型的繪制通常把掃描所得的數(shù)據(jù)生成三角片網(wǎng)格，但當(dāng)模型高度復(fù)雜時(shí)此方法就不實(shí)用了?；趫D像的繪制技術(shù)使用圖像作為繪制基本元素，這種方法的不足是要占用大量的內(nèi)存空間，并且與視點(diǎn)相關(guān)。綜合上述兩種技術(shù)的優(yōu)缺點(diǎn)，人們提出了基于點(diǎn)的繪制技術(shù)，將點(diǎn)作為繪制的基本元素，摒棄了傳統(tǒng)的三角片表示方法，只記錄點(diǎn)的信息，這些點(diǎn)又不同于基于圖像技術(shù)的輸入像素，而包含了附加的幾何信息，并且點(diǎn)采樣與視點(diǎn)無(wú)關(guān)。

基于點(diǎn)的計(jì)算機(jī)圖形學(xué)(Point-Based Graphics，PBG)的一般流程可以概括為點(diǎn)的獲取、點(diǎn)的處理與建模、點(diǎn)的繪制3個(gè)階段[1]。首先利用三維掃描設(shè)備對(duì)物理對(duì)象進(jìn)行數(shù)字化采樣，得到原始的數(shù)據(jù)；然后轉(zhuǎn)化為適合于后期處理與造型的表示形式；最后采用合適的繪制方法將模型顯示出來(lái)。基于點(diǎn)的處理流程如圖1所示。

圖1 基于點(diǎn)的處理流程

點(diǎn)繪制技術(shù)關(guān)鍵工作是由離散點(diǎn)在屏幕上重構(gòu)沒(méi)有空洞的連續(xù)表面。根據(jù)重構(gòu)表面采用的不同技術(shù),基于點(diǎn)的繪制算法可以分為兩大類(lèi)：圖像空間的點(diǎn)繪制算法(表面足跡法)[6]和物體空間的點(diǎn)繪制算法(QSplat)[7]。表面足跡法注重的是繪制的質(zhì)量，但計(jì)算量比較大，導(dǎo)致繪制速度降低。QSplat方法將模型距視點(diǎn)較遠(yuǎn)的多個(gè)點(diǎn)合并為一個(gè)點(diǎn)來(lái)處理，這樣大大提高了繪制效率，但由于沒(méi)有考慮繪制質(zhì)量，會(huì)在輪廓線區(qū)域處產(chǎn)生嚴(yán)重的走樣。因此，張龍等在2005年提出了一個(gè)針對(duì)大規(guī)模點(diǎn)模型的實(shí)時(shí)高質(zhì)量繪制算法[2]，該算法采用與視點(diǎn)遠(yuǎn)近相關(guān)的關(guān)系進(jìn)行自適應(yīng)繪制。對(duì)于遠(yuǎn)處的點(diǎn)，將它們“合并”為較大的點(diǎn)，用比較模糊的繪制模式來(lái)繪制；對(duì)于近處的點(diǎn)，則用比較細(xì)致的繪制模式來(lái)繪制。在不損失繪制質(zhì)量的前提下同時(shí)也簡(jiǎn)化了計(jì)算，很好地融合了繪制質(zhì)量和繪制效率。

2 面繪制

面繪制技術(shù)實(shí)際上是把體數(shù)據(jù)用一種逼近面形式表示，其基本過(guò)程是確定物體的輪廓，并由一系列等值面表示出來(lái)，從而進(jìn)一步由傳統(tǒng)的圖形學(xué)技術(shù)進(jìn)行繪制。由于面繪制的繪制過(guò)程中需要構(gòu)造等值面，生成中間圖元，不是直接由體數(shù)據(jù)上繪制圖像，所以面繪制技術(shù)又被稱為間接體繪制。面繪制有很多種算法，各種算法的不同點(diǎn)在于所采用的物體近似表面的幾何單元不同或選擇的幾何單元尺度不同，典型算法有MC算法(Marching Cubes)、MT算法(Marching Tetrahedral)、剖分立方體法(Dividing Cubes)等[3]。

MC算法是把離散的三維數(shù)據(jù)場(chǎng)表示轉(zhuǎn)換為等值面的逼近三角面片表示,然后可以利用計(jì)算機(jī)圖形學(xué)技術(shù)或現(xiàn)有硬件加速技術(shù)完成等值面的近似表示。MC算法基本思想是將讀入的三維圖像看作一個(gè)個(gè)圖層，從相鄰兩個(gè)圖層分別取4個(gè)像素共8個(gè)頂點(diǎn)組成一個(gè)立方體，這樣就可以把圖像分成若干個(gè)小立方體。然后比較小立方體的頂點(diǎn)與給定閾值的大小關(guān)系，將立方體的頂點(diǎn)以1或0標(biāo)記，頂點(diǎn)大于閾值為1，小于閾值為0。其中有一部分立方體與閾值所在的等值面是相交的，采用插值計(jì)算出立方體邊與等值面的交點(diǎn)，然后將交點(diǎn)連接起來(lái)以形成三維圖形。理論上每個(gè)頂點(diǎn)共有2種狀態(tài)，所以等值面分布總共有256種狀態(tài)，然而由于立方體的對(duì)稱性，經(jīng)過(guò)旋轉(zhuǎn)和翻轉(zhuǎn)后只有15種情況。

MC算法步驟如下：

(1)構(gòu)建索引表，該表指明等值面與體素的哪條邊相交，共256種相交關(guān)系。

(2)構(gòu)建體素，從相鄰兩個(gè)層圖中取8個(gè)像素構(gòu)成一個(gè)體素，如圖2所示。

圖2 體素

(3)將每個(gè)像素與閾值進(jìn)行比較確定該像素是0還是1，并把這8個(gè)像素構(gòu)成的01串組成一個(gè)8位的體素索引表。

(4)用索引值在索引表里查找對(duì)應(yīng)關(guān)系，并求出與立方體每條邊的交點(diǎn)，交點(diǎn)構(gòu)成三角形面片。

(5)遍歷三維圖像的所有體素，重復(fù)執(zhí)行(2)到(4)。

MC算法提供了一種精確定義體素及等值面的生成方法，但也存在許多不足，許多學(xué)者對(duì)此進(jìn)行了改進(jìn)。MC算法是通過(guò)閾值分割來(lái)提取等值面，閾值分割對(duì)邊緣特征清晰的物體比較適用，對(duì)邊緣特征模糊的物體則難以得到較好的效果。針對(duì)這個(gè)問(wèn)題可以將目前計(jì)算機(jī)圖形學(xué)中比較成熟的圖像分割算法進(jìn)行比較，采用適合的算法作為MC算法的分割算法。另外MC算法的輸出是三角形網(wǎng)格，由于數(shù)據(jù)分布十分密集，由此建立的三維網(wǎng)格數(shù)量龐大，因此可以采取有效措施對(duì)MC算法輸出的模型進(jìn)行合理的簡(jiǎn)化，來(lái)提高空間和時(shí)間的效率。

3 體繪制

實(shí)際中有許多場(chǎng)景都不能用簡(jiǎn)單的面來(lái)表示，例如云、霧、水、火等，這些場(chǎng)景形成的數(shù)據(jù)中并不包含真實(shí)面。在這類(lèi)情況下面繪制技術(shù)就不適用了，所以有學(xué)者提出了體繪制技術(shù)。體繪制是以體素作為基本單元，直接由切片數(shù)據(jù)集生成三維體的圖像，也稱為直接體繪制。體繪制技術(shù)是一種基于光學(xué)映射的方法，這種方法通過(guò)模擬光線在物體內(nèi)部的一系列光學(xué)現(xiàn)象，使得到的體繪制圖像更具真實(shí)感、便于分析。

體繪制過(guò)程就是將離散分布的三維數(shù)據(jù)場(chǎng)，按照一定的規(guī)則轉(zhuǎn)換為圖形顯示設(shè)備幀緩存中的二維離散信號(hào)。直接體繪制算法很多，根據(jù)對(duì)空間數(shù)據(jù)的繪制次序不同主要分為兩類(lèi)：以圖像空間為序和以對(duì)象空間為序的算法，但是基本步驟大致相同。第一步是獲取體數(shù)據(jù)。根據(jù)應(yīng)用場(chǎng)合，數(shù)據(jù)的獲取方式可以有多種渠道。然后是數(shù)據(jù)分類(lèi)。數(shù)據(jù)分類(lèi)就是對(duì)每個(gè)體數(shù)據(jù)根據(jù)其標(biāo)量值賦予R，G，B，A等光學(xué)特性，這個(gè)過(guò)程將決定哪些體數(shù)據(jù)可見(jiàn)，哪些不可見(jiàn)。最后是繪制顯示。確定視點(diǎn)、投影類(lèi)型平行或透視、剖面位置等信息，將產(chǎn)生的幾何圖素和屬性轉(zhuǎn)換為可供顯示的圖像[4]。體繪制算法框架圖如圖3所示。

圖3 體繪制算法框架圖

本文介紹一種以圖像空間為序的典型算法光線投射法(Raycasting)[5]，它從圖像空間的每一個(gè)像素出發(fā)沿視線方向發(fā)出一條射線，這條射線穿過(guò)三維數(shù)據(jù)場(chǎng)，順著這條射線選擇多個(gè)等距的采樣點(diǎn)，并由距離某一采樣點(diǎn)最近的8個(gè)數(shù)據(jù)點(diǎn)的顏色值和不透明度值作三次線性插值，求出該采樣點(diǎn)的顏色值和不透明度值。然后再將每條射線上各采樣點(diǎn)的顏色值和不透明度值由前向后或由后向前加以合成，即可得到發(fā)出該射線的像素點(diǎn)處的顏色值，就可以在屏幕上得到最終的圖像[11]。

4 算法比較及實(shí)驗(yàn)結(jié)果

基于點(diǎn)模型表示與繪制具有拓?fù)浣Y(jié)構(gòu)簡(jiǎn)單、繪制體系簡(jiǎn)單、適于表示表面幾何及光照細(xì)節(jié)比較復(fù)雜的模型、適合混合繪制、較少冗余且有硬件支持等優(yōu)點(diǎn)。自適應(yīng)繪制算法很好地融合了繪制質(zhì)量和效率的要求，但仍有待于進(jìn)一步的研究。

面繪制只適用于繪制表面特征分明的物體，對(duì)過(guò)渡比較平緩的物體繪制效果不佳，而且面繪制只能顯示物質(zhì)的輪廓信息，內(nèi)部信息無(wú)法保留[8]。面繪制技術(shù)有許多應(yīng)用，如在醫(yī)學(xué)領(lǐng)域中可以用等值面表示，也可以使用等值面產(chǎn)生算法抽取各種人體組織。MC方法具有簡(jiǎn)單、易實(shí)現(xiàn)、速度快等優(yōu)點(diǎn)。

體繪制在許多應(yīng)用中能產(chǎn)生高質(zhì)量的圖像，并且已經(jīng)特別成功地應(yīng)用在可視化中。與面繪制方法相比，直接體繪制的主要優(yōu)點(diǎn)是可以表示對(duì)象體的內(nèi)部信息，但計(jì)算量大，包括體數(shù)據(jù)的采樣、重構(gòu)、重采樣、組合、繪制等操作。光線投射法優(yōu)點(diǎn)是圖像質(zhì)量高，缺點(diǎn)是會(huì)造成重復(fù)計(jì)算且內(nèi)存開(kāi)銷(xiāo)較大[9]。3類(lèi)繪制方法的優(yōu)缺點(diǎn)比較如表1所示。

表1 3類(lèi)繪制方法比較

本文使用基線為12cm，焦距為3.8mm的雙目相機(jī)拍攝一個(gè)比較圓滑的瓶子，獲取深度數(shù)據(jù)，根據(jù)不同算法所繪制出的圖像如圖4所示。

圖4 繪制結(jié)果

可視化的應(yīng)用越來(lái)越廣泛，研究人員也重視起了這方面的研究。虛擬場(chǎng)景的繪制方法有多種，人們可以根據(jù)場(chǎng)景和物體的復(fù)雜性、光照情況及用戶的需求選擇適合的繪制算法。隨著虛擬現(xiàn)實(shí)技術(shù)的發(fā)展，虛擬場(chǎng)景繪制技術(shù)的研究也不斷的進(jìn)步，它的研究已經(jīng)廣泛地應(yīng)用于虛擬場(chǎng)景的生成、物體表示、虛擬仿真等領(lǐng)域[10]。這些不斷增長(zhǎng)的應(yīng)用領(lǐng)域要求我們能夠更加深入地研究虛擬場(chǎng)景生成的技術(shù)，開(kāi)發(fā)出更加快速、高效的算法。

[1]高秀芬,陳福民.基于點(diǎn)的圖形繪制技術(shù)[J].計(jì)算機(jī)工程與應(yīng)用,2005（9）:20-22.

[2]張龍,董朝,陳為,等.大規(guī)模點(diǎn)模型的實(shí)時(shí)高質(zhì)量繪制[J].計(jì)算機(jī)學(xué)報(bào),2005,28(2):241-249.

[3]唐占紅, 於時(shí)才.面繪制三維重建原理及其改進(jìn)算法研究[J].計(jì)算機(jī)工程與設(shè)計(jì),2009,30(9):2225-2228.

[4]尹學(xué)松,張謙,吳國(guó)華,等.四種體繪制算法的分析與評(píng)價(jià)[J]. 計(jì)算機(jī)工程與應(yīng)用,2004（16）:97-100.

[5]洪歧,張樹(shù)生,王靜,等.體繪制技術(shù)[J].計(jì)算機(jī)應(yīng)用研究 ,2004（10）:16-19.

[6]Ren L., Pfister H., Zwicker M.. Object space ewa surface splatting:A hardware accelerated approach to high quality point rendering[J].Computer Graphics Forum,2002,21(3):461-470.

[7]Rusinkiewicz S, Levoy M. Qsplat: A multiresolution point rendering system for large meshes[C].Proceedings of ACM SIGGRAPH.2000:343-352.

[8]張翔,張大志,田金文,等.基于相關(guān)性的快速體繪制研究[J].計(jì)算機(jī)工程與科學(xué),2005,27(2):33-35.

[9]孫薇薇,張樺. 三種體繪制算法的比較[J].天津理工大學(xué)學(xué)報(bào),2005,21(4):9-11.

[10]全紅艷.基于幾何與圖像結(jié)合的虛擬場(chǎng)景繪制技術(shù)研究[D].哈爾濱:哈爾濱工業(yè)大學(xué),2006.

[11]丁慶木,張虹.圖像體繪制算法的分析與評(píng)價(jià)[J].系統(tǒng)仿真學(xué)報(bào),2007,19(4):897-900.