基于虛擬場景的繪制算法★

趙瑩，韓燮

(中北大學電子與計算機科學技術學院， 山西 太原 030051)

0 引言

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

1 點繪制

基于幾何模型的繪制通常把掃描所得的數據生成三角片網格，但當模型高度復雜時此方法就不實用了。基于圖像的繪制技術使用圖像作為繪制基本元素，這種方法的不足是要占用大量的內存空間，并且與視點相關。綜合上述兩種技術的優缺點，人們提出了基于點的繪制技術，將點作為繪制的基本元素，摒棄了傳統的三角片表示方法，只記錄點的信息，這些點又不同于基于圖像技術的輸入像素，而包含了附加的幾何信息，并且點采樣與視點無關。

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

圖1 基于點的處理流程

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

2 面繪制

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

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

MC算法步驟如下：

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

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

圖2 體素

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

(4)用索引值在索引表里查找對應關系，并求出與立方體每條邊的交點，交點構成三角形面片。

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

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

3 體繪制

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

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

圖3 體繪制算法框架圖

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

4 算法比較及實驗結果

基于點模型表示與繪制具有拓撲結構簡單、繪制體系簡單、適于表示表面幾何及光照細節比較復雜的模型、適合混合繪制、較少冗余且有硬件支持等優點。自適應繪制算法很好地融合了繪制質量和效率的要求，但仍有待于進一步的研究。

面繪制只適用于繪制表面特征分明的物體，對過渡比較平緩的物體繪制效果不佳，而且面繪制只能顯示物質的輪廓信息，內部信息無法保留[8]。面繪制技術有許多應用，如在醫學領域中可以用等值面表示，也可以使用等值面產生算法抽取各種人體組織。MC方法具有簡單、易實現、速度快等優點。

體繪制在許多應用中能產生高質量的圖像，并且已經特別成功地應用在可視化中。與面繪制方法相比，直接體繪制的主要優點是可以表示對象體的內部信息，但計算量大，包括體數據的采樣、重構、重采樣、組合、繪制等操作。光線投射法優點是圖像質量高，缺點是會造成重復計算且內存開銷較大[9]。3類繪制方法的優缺點比較如表1所示。

表1 3類繪制方法比較

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

圖4 繪制結果

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

[1]高秀芬,陳福民.基于點的圖形繪制技術[J].計算機工程與應用,2005（9）:20-22.

[2]張龍,董朝,陳為,等.大規模點模型的實時高質量繪制[J].計算機學報,2005,28(2):241-249.

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

[4]尹學松,張謙,吳國華,等.四種體繪制算法的分析與評價[J]. 計算機工程與應用,2004（16）:97-100.

[5]洪歧,張樹生,王靜,等.體繪制技術[J].計算機應用研究 ,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]張翔,張大志,田金文,等.基于相關性的快速體繪制研究[J].計算機工程與科學,2005,27(2):33-35.

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

[10]全紅艷.基于幾何與圖像結合的虛擬場景繪制技術研究[D].哈爾濱:哈爾濱工業大學,2006.

[11]丁慶木,張虹.圖像體繪制算法的分析與評價[J].系統仿真學報,2007,19(4):897-900.