筆式三維草圖繪制中的輪廓線技術(shù)研究

摘要：詳細(xì)介紹了三維模型輪廓線技術(shù)及其檢測(cè)算法，并深入分析了輪廓線技術(shù)在三維草圖繪制中的作用；然后設(shè)計(jì)并實(shí)現(xiàn)了一個(gè)三維草圖繪制系統(tǒng)。該系統(tǒng)提供了用筆繪制三維模型的交互環(huán)境，通過(guò)輪廓線將三維模型與二維交互手勢(shì)聯(lián)系起來(lái)，使用戶(hù)可以自由靈活地操縱和控制三維模型，獲得自然、高效的交互體驗(yàn)。

關(guān)鍵詞：輪廓線； 筆式交互； 交互手勢(shì)； 三維模型； 草圖繪制

中圖分類(lèi)號(hào)：TP751文獻(xiàn)標(biāo)志碼：A

文章編號(hào)：1001-3695(2007)12-0357-04

交互技術(shù)是一種使用物理輸入和輸出設(shè)備來(lái)執(zhí)行人機(jī)對(duì)話的方式。基于筆的交互技術(shù)是人機(jī)交互領(lǐng)域重要的研究方向;筆式用戶(hù)界面是下一代用戶(hù)界面的研究熱點(diǎn)之一^[1]。它基于紙筆隱喻，將筆交互信息作用的對(duì)象劃分為三類(lèi)：紙（paper），通常代指整個(gè)交互界面；區(qū)域（region），可以是規(guī)則或非規(guī)則的操作區(qū)域；實(shí)體（entity），區(qū)域中的內(nèi)容^[2]。自然的交互與人性化是人機(jī)交互的發(fā)展趨勢(shì)^[3]，與鼠標(biāo)、鍵盤(pán)等傳統(tǒng)交互方式相比，基于筆的交互方式具有自然、和諧的交互特性，更符合用戶(hù)的交互習(xí)慣，更利于捕捉用戶(hù)的思想。按照使用筆式用戶(hù)界面的目的來(lái)說(shuō)，其應(yīng)用領(lǐng)域大體可以歸為四類(lèi)，即創(chuàng)造性工作、信息交流和共享、思想捕捉和筆交互增強(qiáng)^[4]。

傳統(tǒng)觀點(diǎn)認(rèn)為二維界面不適合進(jìn)行三維交互。因?yàn)槿S交互需要信息都具有六個(gè)自由度。近年來(lái)，隨著各種三維交互技術(shù)研究的深入，人們發(fā)現(xiàn)能夠獲得良好用戶(hù)性能的交互技術(shù)本質(zhì)上都是二維交互技術(shù)^[5]。本文提出的三維草圖繪制系統(tǒng)是一種基于筆的三維模型繪制的交互系統(tǒng)，輪廓線作為三維模型的二維輪廓，在其中扮演著核心的作用。輪廓線是三維模型與二維交互手勢(shì)的結(jié)合點(diǎn)。用戶(hù)通過(guò)自然、和諧的交互手勢(shì)進(jìn)行交互；通過(guò)三維模型的輪廓線將交互手勢(shì)的語(yǔ)義映射到模型上，從而實(shí)現(xiàn)對(duì)模型的操縱和控制。

輪廓線作為三維模型的重要特征，刻畫(huà)了三維模型的整體輪廓和大致形狀（圖1），包括外輪廓線、褶皺、邊界、陰影輪廓線和材質(zhì)邊界輪廓線等^[6]，一般由所在面的法向垂直于視線的點(diǎn)組成^[7]。其中外輪廓線是三維模型投影的多邊形閉包，它將三維模型從背景中區(qū)別出來(lái)。外輪廓線組成的多邊形區(qū)域包含三維模型的所有投影點(diǎn)，并且僅僅包含這些投影點(diǎn)。如果沒(méi)有特別指出，下文中提到的輪廓線均是指外輪廓線。

1輪廓線檢測(cè)技術(shù)

1．1概述

輪廓線檢測(cè)技術(shù)分為基于圖像空間的算法和基于圖形空間的算法兩大類(lèi)。前者是指在繪制完畢的三維模型的圖像上尋找并生成輪廓線，可以利用硬件如顏色緩存等得到快速、高效的算法，但是丟失了模型的三維拓?fù)湫畔ⅲ缓笳呤侵咐萌S模型的幾何拓?fù)湫畔?lái)檢測(cè)并生成基于視點(diǎn)的輪廓線，它可以生成復(fù)雜和精確的、具有幾何拓?fù)湫畔⒌妮喞€，但是計(jì)算復(fù)雜度高、運(yùn)算速度慢。

當(dāng)面的法向和視線方向的夾角為銳角時(shí)，這個(gè)面稱(chēng)為前向面，反之稱(chēng)為后向面，前向面和后向面的公共邊稱(chēng)為輪廓邊。判定面是否為前向面的公式如下：

1．2檢測(cè)算法相關(guān)研究

Buchanan等人^[8]提出了一種基于邊緩存的算法，每條邊通過(guò)兩個(gè)位(分別是front flag和back flag)來(lái)保存該邊相鄰的兩個(gè)多邊形是否為前向。通過(guò)遍歷每個(gè)多邊形，若多邊形為前向，則該多邊形的所有邊的front flag位與1作異或；否則該多邊形的所有邊的back flag位與1作異或，最終所有兩個(gè)位都是1的邊均是輪廓邊。因?yàn)槿S模型多邊形的數(shù)目肯定小于邊的數(shù)目，故該算法的時(shí)間效率優(yōu)于brute－force算法，但是效率提高相當(dāng)有限。Markosian等人^[9]提出了一種隨機(jī)算法來(lái)檢測(cè)輪廓線。該算法的基本思想是三維模型邊的兩面角(dihedral)度數(shù)大時(shí)具有更高的成為輪廓邊的概率。其中邊的兩面角是指該邊的兩個(gè)相鄰面向內(nèi)的夾角。該算法首先將三維模型的所有邊依據(jù)其兩面角的大小進(jìn)行排序，再隨機(jī)取出一些邊，然后檢測(cè)這些邊是否真的是輪廓邊。因?yàn)槭请S機(jī)地檢測(cè)一些邊而不是檢測(cè)所有邊，該算法的時(shí)間效率比brute－force算法有了較大改進(jìn)。但是它主要的缺陷是在某些時(shí)刻會(huì)丟失一些輪廓邊，并且當(dāng)視點(diǎn)變化很大或三維模型很大時(shí)，上下幀間的輪廓線可能變化很大。Kirsanov等人^[10]提出的算法可以生成復(fù)雜三維模型簡(jiǎn)單的、近似的輪廓線。它首先生成原始模型的簡(jiǎn)化了的近似模型的精確輪廓線，再生成原始模型的輪廓線。Gooch等人^[11]、Benichou和Elber^[12]提出了一種利用高斯球(Gauss map)來(lái)計(jì)算三維模型輪廓線的算法。該算法速度較快，但是它的不足之處是僅僅適用于正交投影中。

1．3草圖系統(tǒng)中輪廓線的特點(diǎn)

從上述研究可以看出，各種輪廓線檢測(cè)算法都有自己的特點(diǎn)和局限性，適應(yīng)各種不同的需要。在本文提出的三維草圖繪制系統(tǒng)中，需要設(shè)計(jì)適合圖形交互和二維手勢(shì)運(yùn)算的輪廓線。下面詳細(xì)分析了草圖系統(tǒng)中輪廓線及輪廓線檢測(cè)算法的特點(diǎn)：

a）輪廓線是基于圖形空間的，交互過(guò)程中需要輪廓線與交互手勢(shì)的運(yùn)算，因此輪廓線需要具有幾何拓?fù)湫畔ⅰ?/p>

b）輪廓線是實(shí)時(shí)生成的，并且具有較高的檢測(cè)速度。

c）輪廓線是精確的。精確的含義是指輪廓線包含三維模型的所有投影點(diǎn)，且僅僅包含這些投影點(diǎn)。

d）輪廓線消除了不可見(jiàn)的線段，上述的各種算法大多僅僅檢測(cè)出哪些邊是輪廓邊，并沒(méi)有將不可見(jiàn)的輪廓邊舍棄。這種方法可以適用于非真實(shí)感繪制，但是在草圖系統(tǒng)圖形交互中并不適用。

e）輪廓線是多邊形表示的，即輪廓線是由首尾相接的線段組成，通過(guò)舍棄不可見(jiàn)的輪廓邊以及內(nèi)部的輪廓邊，生成的輪廓線恰好是一個(gè)多邊形。這樣有利于與手勢(shì)的比較和運(yùn)算。

1．4草圖系統(tǒng)中的輪廓線檢測(cè)算法

根據(jù)輪廓線的特點(diǎn)，草圖系統(tǒng)基于brute－force算法，實(shí)現(xiàn)了基于圖形空間的精確的輪廓線檢測(cè)算法。草圖系統(tǒng)可以實(shí)時(shí)地檢測(cè)出三維模型的輪廓線，如圖1所示，即是兩種三維模型在不同視點(diǎn)下檢測(cè)出的外輪廓線。

本文實(shí)現(xiàn)的輪廓線檢測(cè)算法，建立的三維模型具有豐富拓?fù)湫畔⒌慕Y(jié)構(gòu)；每個(gè)頂點(diǎn)保存所有的鄰邊；每條邊保存它的兩個(gè)端點(diǎn)以及相鄰的兩個(gè)三角形；每個(gè)三角形保存它的三個(gè)頂點(diǎn)以及三條邊；整個(gè)三維模型保存所有頂點(diǎn)、邊、三角形的信息。三維模型數(shù)據(jù)結(jié)構(gòu)如下：

3．3組合

兩個(gè)模型的組合操作是指將兩個(gè)相交的模型組合成一個(gè)模型；添加上去的模型作為子模型，被添加的模型作為主模型，如圖6所示。

組合操作的交互手勢(shì)為用筆按住子模型拖動(dòng)，移動(dòng)到主模型的某個(gè)位置上。若兩個(gè)模型相交，則完成組合操作；否則組合失敗。在拖動(dòng)子模型過(guò)程中，需要實(shí)時(shí)判定兩個(gè)模型是否相交。這可以通過(guò)判定兩個(gè)模型的輪廓線是否相交來(lái)實(shí)現(xiàn)。

3．4裁剪

草圖系統(tǒng)中的裁剪是指將三維模型切割成兩部分并舍棄其中一部分。本文提出的基于自由裁剪線的裁剪算法可以使用戶(hù)實(shí)現(xiàn)更自然的裁剪操作。

基于筆的裁剪手勢(shì)設(shè)計(jì)為：直接畫(huà)出一條裁剪線將三維模型的輪廓分割成兩部分；要求裁剪線的起點(diǎn)和終點(diǎn)均在模型外。第一次經(jīng)過(guò)的模型即是被裁剪的對(duì)象，如圖7所示。

裁剪算法簡(jiǎn)述如下：將二維裁剪線投影到三維模型上，產(chǎn)生一條覆蓋在三維模型表面上的封閉曲線，該曲線將三維模型的表面分為兩部分；然后將三維模型上所有與封閉曲線相交的邊分裂成兩個(gè)部分，并且生成封閉曲線內(nèi)的裁剪截面；最后將封閉曲線兩側(cè)的所有多邊形三角化，生成兩個(gè)新的完整的三維模型。

裁剪算法將三維模型分為兩部分后，還要確定舍棄哪一部分。根據(jù)一般情況下的用戶(hù)心理，應(yīng)當(dāng)是舍棄相對(duì)小的三維模型。由于裁剪線肯定將輪廓線劃分為兩部分，可以計(jì)算輪廓線兩部分的面積；然后可以裁剪掉面積較小的那一部分。

3．5幾何變換

三維模型的幾何變換包括平移、旋轉(zhuǎn)和縮放等，是三維模型交互操作的重要部分。平移操作的典型手勢(shì)是按住三維模型后通過(guò)拖動(dòng)筆來(lái)移動(dòng)位置。首先判定按下時(shí)筆的坐標(biāo)點(diǎn)是否在輪廓線內(nèi)，然后根據(jù)拖動(dòng)的軌跡移動(dòng)。旋轉(zhuǎn)操作的典型手勢(shì)是先選取要操作的模型，然后在模型外拖動(dòng)筆來(lái)進(jìn)行連續(xù)的旋轉(zhuǎn)。旋轉(zhuǎn)的角度根據(jù)筆軌跡的方向來(lái)確定，在旋轉(zhuǎn)過(guò)程中可以?xún)H僅顯示模型的輪廓線，而不必顯示整個(gè)模型。這樣就提高了刷新速度。與縮放窗口類(lèi)似，通過(guò)在三維模型的輪廓周?chē)蟿?dòng)筆來(lái)實(shí)現(xiàn)實(shí)時(shí)的縮放效果。如圖8所示，三維模型輪廓線與閉合虛線之間的區(qū)域即是縮放的有效區(qū)域。筆在該區(qū)域內(nèi)時(shí)激活縮放操作，并根據(jù)筆在輪廓線的位置確定縮放方向。

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

本文詳細(xì)介紹了目前三維模型輪廓線的理論和檢測(cè)算法，設(shè)計(jì)并實(shí)現(xiàn)了一個(gè)基于筆式用戶(hù)界面的三維草圖繪制系統(tǒng)，并深入分析和展現(xiàn)了輪廓線技術(shù)在二維交互手勢(shì)與三維模型之間的作用。實(shí)驗(yàn)結(jié)果表明，本文實(shí)現(xiàn)的三維草圖繪制系統(tǒng)通過(guò)輪廓線將三維模型與二維的交互動(dòng)作結(jié)合起來(lái)，設(shè)計(jì)的手勢(shì)簡(jiǎn)單清晰，便于用戶(hù)使用和記憶，使得交互的過(guò)程自然和諧，符合用戶(hù)的交互習(xí)慣。但是，本文實(shí)現(xiàn)的系統(tǒng)依賴(lài)于輪廓線的實(shí)時(shí)檢測(cè)。這就對(duì)輪廓線的檢測(cè)算法提出了很高的要求，需要尋找實(shí)時(shí)性很高的算法。另外，本文設(shè)計(jì)的有些手勢(shì)因?yàn)楹?jiǎn)單而區(qū)分度不太明顯，需要進(jìn)一步研究用戶(hù)的交互習(xí)慣，進(jìn)行交互手勢(shì)的改進(jìn)和優(yōu)化。

參考文獻(xiàn)：

[1]ZIEGLER J. Interactive techniques[J]. ACM Computer Survey， 1996，28(1):185－187.

[2]DAI G， TIAN F， LI J. Researches on pen－based user interface[C]//HARRIS D， DUFFY V， SMITH M， et al. Human－centered computing: cognitive， social and ergonomic aspects. Proc of the 10th International Conference on Human－Computer Interaction(HCI Interna－tional 2003). Crete:[s.n.]， 2003:22-27.

[3]董建明，傅利民，SALVENDY G.人機(jī)交互:以用戶(hù)為中心的設(shè)計(jì)

和評(píng)估[M].北京:清華大學(xué)出版社，2002.

[4]LI Yang. Research on pen－based user interfaces， theory， technique and implementation[D]. Beijing: Institute of Software， 2002.

[5]POUPYREV I， WEGHORST S， BILLINGHURST M， et al. A framework and testbed for studying manipulation techniques for immersive VR[C]//Proc of VRST’97. Lausanne:[s.n.]， 1997:21-28.

[6]王翱宇，唐敏，童若鋒，等.非真實(shí)感繪制中輪廓線檢測(cè)技術(shù)綜述[J].計(jì)算機(jī)應(yīng)用與軟件，2006，23(5):102－104.

[7]ISENBERG T， FREUDENBERG B， HALPER N， et al. A develo－pers’ guide to silhouette algorithms for polygonal models[J]. Computer Graphics and Applications， 2003，23(4):28-37.

[8]BUCHANAN J W， SOUSA M C. The edge buffer: a data structure for easy silhouette rendering[C]//Proc of the 1st International Sympo－sium on Non－photorealistic Animation and Rendering. Annual:[s.n.]， 2000:39-42.

[9]MARKOSIAN L， KOWALSKI M A， GOLDSTEIN D， et al. Real－time non－photorealistic rendering[C]//Proc of the 24th Annual Conference on Computer Graphics and Interactive Techniques. 1997:415-420.

[10]KIRSANOV D， SANDER P V， GORTLER S J. Simple silhouettes over complex surface[C]//Proc of Eurographics/ACM SIGGRAPH Symposium on Geometry Processing. 1999:102－106.

[11]GOOCH B， SLOAN P P J， GOOCH A， et al. Interactive technical illustration[C]//Proc of Symposium on Interactive 3D Graphics. New York: ACM Press， 1999:31-38.

[12]BENICHOU F， ELBER G. Output sensitive extraction of silhouettes from polygonal geometry: pacific graphics[C]//Proc of the 7th Paci－fic Conference on Computer Graphics and Applications. Washington D C: IEEE Computer Society， 1999.

[13]付永剛.三維用戶(hù)界面和三維交互技術(shù)研究[D].北京:中國(guó)科學(xué)院軟件研究所，2005.

[14]王文成，吳恩華.判斷檢測(cè)點(diǎn)是否在多邊形或多面體內(nèi)的新方法[J].軟件學(xué)報(bào)，2000，11(12):1614－1619.

“本文中所涉及到的圖表、注解、公式等內(nèi)容請(qǐng)以PDF格式閱讀原文”