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

摘要：詳細介紹了三維模型輪廓線技術及其檢測算法，并深入分析了輪廓線技術在三維草圖繪制中的作用；然后設計并實現了一個三維草圖繪制系統。該系統提供了用筆繪制三維模型的交互環境，通過輪廓線將三維模型與二維交互手勢聯系起來，使用戶可以自由靈活地操縱和控制三維模型，獲得自然、高效的交互體驗。

關鍵詞：輪廓線； 筆式交互； 交互手勢； 三維模型； 草圖繪制

中圖分類號：TP751文獻標志碼：A

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

交互技術是一種使用物理輸入和輸出設備來執行人機對話的方式?；诠P的交互技術是人機交互領域重要的研究方向;筆式用戶界面是下一代用戶界面的研究熱點之一^[1]。它基于紙筆隱喻，將筆交互信息作用的對象劃分為三類：紙（paper），通常代指整個交互界面；區域（region），可以是規則或非規則的操作區域；實體（entity），區域中的內容^[2]。自然的交互與人性化是人機交互的發展趨勢^[3]，與鼠標、鍵盤等傳統交互方式相比，基于筆的交互方式具有自然、和諧的交互特性，更符合用戶的交互習慣，更利于捕捉用戶的思想。按照使用筆式用戶界面的目的來說，其應用領域大體可以歸為四類，即創造性工作、信息交流和共享、思想捕捉和筆交互增強^[4]。

傳統觀點認為二維界面不適合進行三維交互。因為三維交互需要信息都具有六個自由度。近年來，隨著各種三維交互技術研究的深入，人們發現能夠獲得良好用戶性能的交互技術本質上都是二維交互技術^[5]。本文提出的三維草圖繪制系統是一種基于筆的三維模型繪制的交互系統，輪廓線作為三維模型的二維輪廓，在其中扮演著核心的作用。輪廓線是三維模型與二維交互手勢的結合點。用戶通過自然、和諧的交互手勢進行交互；通過三維模型的輪廓線將交互手勢的語義映射到模型上，從而實現對模型的操縱和控制。

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

1輪廓線檢測技術

1．1概述

輪廓線檢測技術分為基于圖像空間的算法和基于圖形空間的算法兩大類。前者是指在繪制完畢的三維模型的圖像上尋找并生成輪廓線，可以利用硬件如顏色緩存等得到快速、高效的算法，但是丟失了模型的三維拓撲信息；后者是指利用三維模型的幾何拓撲信息來檢測并生成基于視點的輪廓線，它可以生成復雜和精確的、具有幾何拓撲信息的輪廓線，但是計算復雜度高、運算速度慢。

當面的法向和視線方向的夾角為銳角時，這個面稱為前向面，反之稱為后向面，前向面和后向面的公共邊稱為輪廓邊。判定面是否為前向面的公式如下：

1．2檢測算法相關研究

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

1．3草圖系統中輪廓線的特點

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

a）輪廓線是基于圖形空間的，交互過程中需要輪廓線與交互手勢的運算，因此輪廓線需要具有幾何拓撲信息。

b）輪廓線是實時生成的，并且具有較高的檢測速度。

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

d）輪廓線消除了不可見的線段，上述的各種算法大多僅僅檢測出哪些邊是輪廓邊，并沒有將不可見的輪廓邊舍棄。這種方法可以適用于非真實感繪制，但是在草圖系統圖形交互中并不適用。

e）輪廓線是多邊形表示的，即輪廓線是由首尾相接的線段組成，通過舍棄不可見的輪廓邊以及內部的輪廓邊，生成的輪廓線恰好是一個多邊形。這樣有利于與手勢的比較和運算。

1．4草圖系統中的輪廓線檢測算法

根據輪廓線的特點，草圖系統基于brute－force算法，實現了基于圖形空間的精確的輪廓線檢測算法。草圖系統可以實時地檢測出三維模型的輪廓線，如圖1所示，即是兩種三維模型在不同視點下檢測出的外輪廓線。

本文實現的輪廓線檢測算法，建立的三維模型具有豐富拓撲信息的結構；每個頂點保存所有的鄰邊；每條邊保存它的兩個端點以及相鄰的兩個三角形；每個三角形保存它的三個頂點以及三條邊；整個三維模型保存所有頂點、邊、三角形的信息。三維模型數據結構如下：

3．3組合

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

組合操作的交互手勢為用筆按住子模型拖動，移動到主模型的某個位置上。若兩個模型相交，則完成組合操作；否則組合失敗。在拖動子模型過程中，需要實時判定兩個模型是否相交。這可以通過判定兩個模型的輪廓線是否相交來實現。

3．4裁剪

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

基于筆的裁剪手勢設計為：直接畫出一條裁剪線將三維模型的輪廓分割成兩部分；要求裁剪線的起點和終點均在模型外。第一次經過的模型即是被裁剪的對象，如圖7所示。

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

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

3．5幾何變換

三維模型的幾何變換包括平移、旋轉和縮放等，是三維模型交互操作的重要部分。平移操作的典型手勢是按住三維模型后通過拖動筆來移動位置。首先判定按下時筆的坐標點是否在輪廓線內，然后根據拖動的軌跡移動。旋轉操作的典型手勢是先選取要操作的模型，然后在模型外拖動筆來進行連續的旋轉。旋轉的角度根據筆軌跡的方向來確定，在旋轉過程中可以僅僅顯示模型的輪廓線，而不必顯示整個模型。這樣就提高了刷新速度。與縮放窗口類似，通過在三維模型的輪廓周圍拖動筆來實現實時的縮放效果。如圖8所示，三維模型輪廓線與閉合虛線之間的區域即是縮放的有效區域。筆在該區域內時激活縮放操作，并根據筆在輪廓線的位置確定縮放方向。

4結束語

本文詳細介紹了目前三維模型輪廓線的理論和檢測算法，設計并實現了一個基于筆式用戶界面的三維草圖繪制系統，并深入分析和展現了輪廓線技術在二維交互手勢與三維模型之間的作用。實驗結果表明，本文實現的三維草圖繪制系統通過輪廓線將三維模型與二維的交互動作結合起來，設計的手勢簡單清晰，便于用戶使用和記憶，使得交互的過程自然和諧，符合用戶的交互習慣。但是，本文實現的系統依賴于輪廓線的實時檢測。這就對輪廓線的檢測算法提出了很高的要求，需要尋找實時性很高的算法。另外，本文設計的有些手勢因為簡單而區分度不太明顯，需要進一步研究用戶的交互習慣，進行交互手勢的改進和優化。

參考文獻：

[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.人機交互:以用戶為中心的設計

和評估[M].北京:清華大學出版社，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]王翱宇，唐敏，童若鋒，等.非真實感繪制中輪廓線檢測技術綜述[J].計算機應用與軟件，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]付永剛.三維用戶界面和三維交互技術研究[D].北京:中國科學院軟件研究所，2005.

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

“本文中所涉及到的圖表、注解、公式等內容請以PDF格式閱讀原文”