手繪二維曲線自動生成三維模型研究

劉曉平， 吳 正， 李 琳

?

手繪二維曲線自動生成三維模型研究

劉曉平， 吳 正， 李 琳

（合肥工業大學計算機與信息學院VCC研究室, 安徽合肥 230009）

通過手繪創作三維模型是改變傳統三維模型制作方式的新興研究點；論文提出兩種由手繪二維曲線自動產生三維模型的算法，分別進行了詳細介紹和討論：算法一基于重心原理拓展曲線，并在曲線簇上進行網格重構，但此方法僅限于橢圓拓撲的曲線；算法二利用離散方法尋找軸線，該方法能夠生成更加多樣化的模型并側重于細節。通過算法實現效果的對比，驗證了兩種算法快速生成三維模型的有效性；最后展示了通過該文算法繪制的幾個卡通模型，并對進一步生成模型動畫進行了設想。

計算機圖形學；手繪建模；網格化；卡通模型

三維模型是在計算機中構造虛擬對象的基本元素，有很多方法可以得到三維模型。美術創作人員利用三維建模軟件如3DSMAX、MAYA按照一定的規則輸入參數或者交互操作構造三維模型，但是此類軟件一般操作很復雜，尤其對于自由曲面的構造；新出現的三維掃描儀可以得到現實景物的點云信息，但其數據量龐大，幾乎無法應用在實時系統中；近年來還出現了基于圖像的三維建模方法，成熟的技術大都體現在規則形體如樓房的構造上。簡便快速直觀的三維模型構造方法一直是圖形領域長期關注的問題。

在二維美術創作中，由手寫板進行輸入繪制二維圖像是美術人員的基本操作方式，這種方式接近于徒手繪圖，符合美工的操作習慣，同時在二維筆觸的識別與繪制方面也多有研究。由此得到啟發，在三維模型的創作中，是否也能夠利用手繪二維線條進行模型制作呢？很多學者開始了該方面的探索，較早的基于筆交互的建模系統SKETCH是一個基于鼠標的手勢理解的幾何建模體系，然而它所創建的幾何模型僅局限于簡單的圖形，而且使用者必須嚴格遵循煩瑣的操作順序。其后出現了一個有意義的突破——Teddy，它開發了一個通過簡單的輪廓繪制、填充、擠壓變形等操作獲得充分自由的三維圖形的“人性化”工具,但其局限于具有橢圓輪廓模型的創建；現在的Teddy仍然在發展之中，已經到了第五代，但是仍然不足以成為商業化軟件推廣使用。國內在這方面也開展了許多有意義的工作，文獻[6]將概念設計引入到三維模型的概念中，將基本的筆劃操作保存到模型庫，通過幾何約束推理的方法識別創建三維模型，然而該算法必須建立合適的推理庫，且操作不易理解。受陰影造型技術的啟發，文獻[7]提出了一種基于從明暗恢復形狀的手繪草圖三維建模方法，但由于需要對輪廓多邊形組成的區域進行填充，并計算填充區域內每個像素點的灰度值和距離場而使算法顯得非常復雜。由此可見，基于二維手繪產生三維模型是一個富有挑戰而且應用面廣影響力大的研究型問題，它的成熟將帶來整個三維世界傳統創作方式的徹底改變。

本文的主要工作是根據用戶繪制的一個封閉自由曲線作為創建三維模型的基礎輪廓，研究基于此輪廓線自動產生三維網格模型，達到平滑自由曲面的效果。由于一個三維網格模型需要點集信息與形成實體的面片信息，所以本文思想主要根據二維基礎輪廓線向空間擴展，生成新的三維點集和面片集；由此提出兩種基于手繪二維曲線生成三維模型的算法，分別為重心偏移法和軸線擴展法，與以上提及該方向的各種研究在思路上都有所不同；以下分別對這兩種算法進行了詳細的描述，并進行實驗比較兩種算法時間復雜度與生成模型的差異，給出兩種算法下豐富的建模效果，分析兩種算法的優勢與劣勢以及應用面的不同，最后給出一個具有挑戰性的發展方向。

1 基于重心的三維模型生成算法

該算法考慮在繪制平面兩邊分別存在著一個基準點，輪廓線上的每一點可以向該基準點以橢圓法則擴展。首先求取輪廓線的重心，并將重心向繪制平面兩邊移動一定的距離作為基準點，然后以輪廓線上的每一點分別與基準點作為橢圓的兩個端點插入新點，作為生成三維模型的組成點，網格化生成三角面片模型。

1.1 計算基準點

基準點以輪廓線重心為基礎，設輪廓線點集二維坐標分別為(,)，…，P(x,y)，則重心為的坐標為

其中（1）

重心求出后，將其沿垂直于輪廓線平面的方向移動一定的距離作為輪廓線的基準點。如圖1所示，點沿平面法向移動后得點。

(a) 二維輪廓線?????(b) M為輪廓線重心?????(c) 拔高作為輪廓線基準點

1.2 橢圓法則生成新點集

在計算得重心并基于重心得到基準點后，則對于輪廓線上任一點，點與點可作為橢圓的兩個頂點構成四分之一橢圓曲線，如圖2(a)。

設，，則按照橢圓公式1，則為四分之一段橢圓。用平行于輪廓線的平面按一定的間隔切割這些橢圓曲線，則每一次切割都會與這些橢圓線形成的個交點，完成次切割操作后，就會得到×個具有分層結構的新點集，如圖2(b)。

(a) 橢圓法則 ??????????(b)生成的新點集

1.3 分層點云網格化

本算法最終形成的是三角面片模型，由于在點集生成過程中采取的切割橢圓線方法使得新點集存在著明顯的分層結構，因此簡化了網格化的難度。對于分層結構的點集，僅僅需要在相鄰層之間構建網格，并且除基準點外，其余各層上點的數目與原始輪廓線點的數目相同。各層的點具有一一對應的關系，因而進一步簡化了網格化的過程。構建網格的方法如圖3所示。

設由點集,, …,A組成，由點集,, …,B組成，則網格化為三角形的數目為2，第2(0≤≤-2)個三角形和第21個三角形分別為△ABB與△ABA，第2(1)和第2(-1)+1個三角形分別為△AB和△AB，如圖3所示。

(a) 相鄰曲線之間構網?????(b) 分層點集之間構網 ????? (c) 最終網格

2 基于軸線的三維模型生成算法

該算法考慮為輪廓線上的每一個點找一個基準點，基準點集近似該輪廓線的一條軸線，可看作該輪廓線的“骨骼”。首先從二維點中的某個符合條件的點出發，逐步向前，求解得二維曲線的一條或多條類似于軸的曲線，使二維曲線的每個點對應于軸線上的相應基準點擴展。

2.1 基準線求取

基準線的求取是該算法的基礎，它近似于輪廓線的軸線，存在于輪廓線的“中心”。對于給定的輪廓線，算法根據以下步驟求取基準點集：

如圖4所示，找到具有最小內角度的角點，從點開始，逐步求得輪廓線上其他點的基準點。設的兩個鄰接點為、，不妨設，則在上存在一點'，使得'，連接'，得到'的中點₂，則₂可以看作是和的中心線，并且取₂是的基準點。由于是起始點，其基準點為本身。

處理完起始點后，待求取基準點的點為、，此時和的方向由與決定，為了計算或對應的基準點，算法首先求取與的中心線。設與的向量分別為，，則它們的中心線向量()()。

作者用向量垂直于中心線的直線過或切割輪廓線（不妨設過點切割），則該直線與另一邊必交于一點（圖中交交于），則兩個交點的中點即為該點的基準點。在圖4中，的中點₁為的基準點。（如果直線在無交點，則過的直線必然與相交。）圖4中，可由方程(2)解出。

其中為垂直于中心線的向量。如解得0≤≤1，則說明在解得，否則過點切割輪廓線。

圖4 求解基準點的方法

找到的基準點后，待求取基準點的輪廓點為的后繼點以及，重復前項操作直至處理完每個輪廓線上點的基準點，如圖5所示。

圖5 依次求解得所有基準點

2.2 新三維點集生成

基準線生成后，算法按下面方法生成構成模型的三維點集。對于輪廓線上的每一點，其對應在基準線上的基準點為，將沿著輪廓線平面的法線方向移動的距離，定義為四分之一圓弧，圓心為未在法線方向拉升前的，以平行于輪廓線平面的平面按適當的間隔切割該圓弧，獲得的交點集為點擴展得到的新點集。處理完所有的輪廓線點后，即完成三維模型的新點集生成（見圖6）。

圖6 新點集生成的效果

2.3 點云網格化

由于該算法獲得的基準線上的基準點拉升的距離不等，所以生成的新點集沒有明顯的分層結構。但由于每個輪廓線點對應一組新點集，因此算法采用最小對角線法在相鄰的輪廓線點的對應點集之間構建網格。最小對角線法如圖7所示。設，為輪廓線上的相鄰點，其基準點為、，則在曲線上采集的點分別為，，…，P，在曲線上采集到的點分別為，，…，Q，使用最小對角線方法對兩條曲線進行縫合。過程如下：

在最小對角線法構建網格過程中，設待建三角形的一條邊為PQ為當前生長邊，此時第三個點的選取原則為對角線最小，即PQ<QP時，則第三個點為Q，否則第三個點為P。再以PQ或QP為新的生長邊繼續生成三角形。形成的網格如圖8所示。

圖7 最小對角線法

圖8 網格化效果

3 實驗結果分析

基于重心的三維模型生成算法計算較為簡單，能夠快速生成所需要的三維點和三角面片，對于圓形拓撲的輪廓線能夠生成較好的效果，輪廓線上小的擾動不會影響到總體的效果。

但基于重心的三維模型生成算法難以處理非橢圓形拓撲結構的輪廓線，并且將輪廓線上所有的點都相對于同一基準點擴展顯然不夠合理?；谳S線的三維模型生成算法則試圖找到一條或多條基準線，為每個輪廓線上的點找到一個基準點，有利于注重輪廓線的細節，并且擴展了算法的適用面。

重心偏移法和軸線擴展法的時間復雜度都是()，能夠實時生成三維模型，其中為輪廓線點的個數，為生成新點集時切割曲線的層數。圖9展示了兩種算法生成模型的效果，左邊為軸線擴展法，右側為重心偏移法?？梢?，在相同級別的時間復雜度下，軸線擴展法對于非橢圓結構的輪廓線具有更好的生成效果。

另外，基于軸線的三維模型生成算法中形成的軸線可以用來設計模型的動畫序列，為擴展到動畫功能提供了必要的條件。

4 總結與展望

近兩年，拋棄鼠標與鍵盤，直接通過筆觸與手勢與計算機進行交互已經成為人機交互的主要方式，APPLE IPHONE和即將到來的WINDOWS7無一不體現著這一理念。本文提出的方法正是順應這一交互手段，提出一種新的創建三維光滑曲面模型的方法，用戶不需要操作控制點或者進行復雜的編輯操作就可以得到理想的結果，信手涂鴉的方式適用于非專業人士或者是靈感形成階段的記錄。本文方法所產生的結果非常適合于各種卡通對象的繪制，為卡通模型的制作提供了一種簡潔快速的創作途徑，由于卡通模型是動漫創作的重要組成部分，因此本文的研究對動漫行業也具有非常重要的意義和實用價值。圖10是利用本文算法生成的卡通模型實例。

圖10 生成的卡通模型展示

本文的工作只是手繪產生三維模型的一個開始，作者將對算法進一步改進，以適應于更多的復雜情況。而在第二種算法中出現的“軸線”，將對產生以骨骼為基礎的三維動畫有著極大的價值，進一步研究基于軸線的動畫序列的產生，最終形成從手繪建模到動畫生成的一整套系統是作者最終的目標。

[1] 任秉銀, 陳皓暉. 任意拓撲結構復雜曲面模型重構新方法[J]. 機械工程學報, 2003, 39(10): 162-166.

[2] Levoy M, Pulli K, Curless B, et al. The digital michelangelo project: 3D scanning of large statues [C]//Siggraph, 2000: 131-144.

[3] Esteban C H, Schmitt F. Silhouette and stereo fusion for 3D object modeling [J]. Computer Vision and Image Understanding, 2004, 96: 367-392.

[4] Zeleznik R C, Herndon K P, Hughes J F. SKETCH: an interface for sketching 3D scenes [C]//Computer Graphics Proceedings, Annual Conference Series, ACM SIGGRAPH, New Orleans, 1996: 163-170.

[5] Igorashi T, Mat suoka S, Tanaka H. Teddy: a sketching interface for 3D freeform design [C]//Computer Graphics Proceedings, Annual Conference Series, ACM SIGGRAPH, Los Angels, 1999: 409-416.

[6] 韓 麗, 唐 棣. 手繪輸入的三維建模和編輯技術[J]. 計算機輔助設計與圖形學學報, 2008, 20: 946-951.

[7] 謝 浩, 費廣正, 吳明峰, 等. 從明暗恢復形狀的手繪草圖三維建模算法[J]. 工程圖學學報, 2006, 27(4): 57-65.

[8] Eggli L, Hsu C, Elber G, et al. Inferring 3D models from freehand sketches and constraints [J]. Computer-Aided Design, 1997, 29(2): 101-112.

[9] Ku D C, Qin S F, Wright D K. Interpretation of overt racing freehand sketching for geometric shapes [C]//Proceedings of Computer Graphics, Visualization and Computer Vision 'WSCG', Plzen, 2006: 263-270.

[10] Qin S F, Wright D K. Progressive surface modelling scheme from unorganised curves [J]. Computer Aided Design, 2006, 38(10): 1113-1122.

Automatic Generation of 3D Model Based on Sketch

LIU Xiao-ping, WU Zheng, LI Lin

( VCC Division, School of Computer and Information, Hefei University of Technology, Hefei Anhui 230009, China )

Creating 3D model based on sketch is an emerging research that changes traditional modeling pattern. Two algorithms of automatic generation of 3D model based on 2D curve sketching are introduced and discussed in detail in this paper. The first one expands the curve based barycenter, then reconstructs a mesh from curve-cluster, which, however, is limited in application to only ellipse-like topology curves. The second one finds its axis using discrete method, so more diversified models focusing on details can be generated. The comparison of realization effects of the two algorithms shows that they are effective for fast generation of 3D. Finally, several cartoon models created by the algorithms are displayed, and generation of model animation are desired for further.

computer graphics; sketch-based modeling; triangulation; cartoon model

TP 391

A

1003-0158(2011)03-0017-06

2009-12-12

國家自然科學基金國際（地區）合作交流資助項目（60573174）；特種顯示技術教育部重點實驗室開放課題基金

劉曉平（1964-），男，山東濟南人，教授，主要研究方向為建模、仿真與協同計算。