劉曉平， 吳 正， 李 琳

?

手繪二維曲線自動(dòng)生成三維模型研究

劉曉平， 吳 正， 李 琳

（合肥工業(yè)大學(xué)計(jì)算機(jī)與信息學(xué)院VCC研究室, 安徽合肥 230009）

通過手繪創(chuàng)作三維模型是改變傳統(tǒng)三維模型制作方式的新興研究點(diǎn)；論文提出兩種由手繪二維曲線自動(dòng)產(chǎn)生三維模型的算法，分別進(jìn)行了詳細(xì)介紹和討論：算法一基于重心原理拓展曲線，并在曲線簇上進(jìn)行網(wǎng)格重構(gòu)，但此方法僅限于橢圓拓?fù)涞那€；算法二利用離散方法尋找軸線，該方法能夠生成更加多樣化的模型并側(cè)重于細(xì)節(jié)。通過算法實(shí)現(xiàn)效果的對(duì)比，驗(yàn)證了兩種算法快速生成三維模型的有效性；最后展示了通過該文算法繪制的幾個(gè)卡通模型，并對(duì)進(jìn)一步生成模型動(dòng)畫進(jìn)行了設(shè)想。

計(jì)算機(jī)圖形學(xué)；手繪建模；網(wǎng)格化；卡通模型

三維模型是在計(jì)算機(jī)中構(gòu)造虛擬對(duì)象的基本元素，有很多方法可以得到三維模型。美術(shù)創(chuàng)作人員利用三維建模軟件如3DSMAX、MAYA按照一定的規(guī)則輸入?yún)?shù)或者交互操作構(gòu)造三維模型，但是此類軟件一般操作很復(fù)雜，尤其對(duì)于自由曲面的構(gòu)造；新出現(xiàn)的三維掃描儀可以得到現(xiàn)實(shí)景物的點(diǎn)云信息，但其數(shù)據(jù)量龐大，幾乎無法應(yīng)用在實(shí)時(shí)系統(tǒng)中；近年來還出現(xiàn)了基于圖像的三維建模方法，成熟的技術(shù)大都體現(xiàn)在規(guī)則形體如樓房的構(gòu)造上。簡(jiǎn)便快速直觀的三維模型構(gòu)造方法一直是圖形領(lǐng)域長(zhǎng)期關(guān)注的問題。

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

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

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

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

1.1 計(jì)算基準(zhǔn)點(diǎn)

基準(zhǔn)點(diǎn)以輪廓線重心為基礎(chǔ)，設(shè)輪廓線點(diǎn)集二維坐標(biāo)分別為(,)，…，P(x,y)，則重心為的坐標(biāo)為

其中（1）

重心求出后，將其沿垂直于輪廓線平面的方向移動(dòng)一定的距離作為輪廓線的基準(zhǔn)點(diǎn)。如圖1所示，點(diǎn)沿平面法向移動(dòng)后得點(diǎn)。

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

1.2 橢圓法則生成新點(diǎn)集

在計(jì)算得重心并基于重心得到基準(zhǔn)點(diǎn)后，則對(duì)于輪廓線上任一點(diǎn)，點(diǎn)與點(diǎn)可作為橢圓的兩個(gè)頂點(diǎn)構(gòu)成四分之一橢圓曲線，如圖2(a)。

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

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

1.3 分層點(diǎn)云網(wǎng)格化

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

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

(a) 相鄰曲線之間構(gòu)網(wǎng)?????(b) 分層點(diǎn)集之間構(gòu)網(wǎng) ????? (c) 最終網(wǎng)格

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

該算法考慮為輪廓線上的每一個(gè)點(diǎn)找一個(gè)基準(zhǔn)點(diǎn)，基準(zhǔn)點(diǎn)集近似該輪廓線的一條軸線，可看作該輪廓線的“骨骼”。首先從二維點(diǎn)中的某個(gè)符合條件的點(diǎn)出發(fā)，逐步向前，求解得二維曲線的一條或多條類似于軸的曲線，使二維曲線的每個(gè)點(diǎn)對(duì)應(yīng)于軸線上的相應(yīng)基準(zhǔn)點(diǎn)擴(kuò)展。

2.1 基準(zhǔn)線求取

基準(zhǔn)線的求取是該算法的基礎(chǔ)，它近似于輪廓線的軸線，存在于輪廓線的“中心”。對(duì)于給定的輪廓線，算法根據(jù)以下步驟求取基準(zhǔn)點(diǎn)集：

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

處理完起始點(diǎn)后，待求取基準(zhǔn)點(diǎn)的點(diǎn)為、，此時(shí)和的方向由與決定，為了計(jì)算或?qū)?yīng)的基準(zhǔn)點(diǎn)，算法首先求取與的中心線。設(shè)與的向量分別為，，則它們的中心線向量()()。

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

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

圖4 求解基準(zhǔn)點(diǎn)的方法

找到的基準(zhǔn)點(diǎn)后，待求取基準(zhǔn)點(diǎn)的輪廓點(diǎn)為的后繼點(diǎn)以及，重復(fù)前項(xiàng)操作直至處理完每個(gè)輪廓線上點(diǎn)的基準(zhǔn)點(diǎn)，如圖5所示。

圖5 依次求解得所有基準(zhǔn)點(diǎn)

2.2 新三維點(diǎn)集生成

基準(zhǔn)線生成后，算法按下面方法生成構(gòu)成模型的三維點(diǎn)集。對(duì)于輪廓線上的每一點(diǎn)，其對(duì)應(yīng)在基準(zhǔn)線上的基準(zhǔn)點(diǎn)為，將沿著輪廓線平面的法線方向移動(dòng)的距離，定義為四分之一圓弧，圓心為未在法線方向拉升前的，以平行于輪廓線平面的平面按適當(dāng)?shù)拈g隔切割該圓弧，獲得的交點(diǎn)集為點(diǎn)擴(kuò)展得到的新點(diǎn)集。處理完所有的輪廓線點(diǎn)后，即完成三維模型的新點(diǎn)集生成（見圖6）。

圖6 新點(diǎn)集生成的效果

2.3 點(diǎn)云網(wǎng)格化

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

在最小對(duì)角線法構(gòu)建網(wǎng)格過程中，設(shè)待建三角形的一條邊為PQ為當(dāng)前生長(zhǎng)邊，此時(shí)第三個(gè)點(diǎn)的選取原則為對(duì)角線最小，即PQ<QP時(shí)，則第三個(gè)點(diǎn)為Q，否則第三個(gè)點(diǎn)為P。再以PQ或QP為新的生長(zhǎng)邊繼續(xù)生成三角形。形成的網(wǎng)格如圖8所示。

圖7 最小對(duì)角線法

圖8 網(wǎng)格化效果

3 實(shí)驗(yàn)結(jié)果分析

基于重心的三維模型生成算法計(jì)算較為簡(jiǎn)單，能夠快速生成所需要的三維點(diǎn)和三角面片，對(duì)于圓形拓?fù)涞妮喞€能夠生成較好的效果，輪廓線上小的擾動(dòng)不會(huì)影響到總體的效果。

但基于重心的三維模型生成算法難以處理非橢圓形拓?fù)浣Y(jié)構(gòu)的輪廓線，并且將輪廓線上所有的點(diǎn)都相對(duì)于同一基準(zhǔn)點(diǎn)擴(kuò)展顯然不夠合理?；谳S線的三維模型生成算法則試圖找到一條或多條基準(zhǔn)線，為每個(gè)輪廓線上的點(diǎn)找到一個(gè)基準(zhǔn)點(diǎn)，有利于注重輪廓線的細(xì)節(jié)，并且擴(kuò)展了算法的適用面。

重心偏移法和軸線擴(kuò)展法的時(shí)間復(fù)雜度都是()，能夠?qū)崟r(shí)生成三維模型，其中為輪廓線點(diǎn)的個(gè)數(shù)，為生成新點(diǎn)集時(shí)切割曲線的層數(shù)。圖9展示了兩種算法生成模型的效果，左邊為軸線擴(kuò)展法，右側(cè)為重心偏移法?？梢姡谙嗤?jí)別的時(shí)間復(fù)雜度下，軸線擴(kuò)展法對(duì)于非橢圓結(jié)構(gòu)的輪廓線具有更好的生成效果。

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

4 總結(jié)與展望

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

圖10 生成的卡通模型展示

本文的工作只是手繪產(chǎn)生三維模型的一個(gè)開始，作者將對(duì)算法進(jìn)一步改進(jìn)，以適應(yīng)于更多的復(fù)雜情況。而在第二種算法中出現(xiàn)的“軸線”，將對(duì)產(chǎn)生以骨骼為基礎(chǔ)的三維動(dòng)畫有著極大的價(jià)值，進(jìn)一步研究基于軸線的動(dòng)畫序列的產(chǎn)生，最終形成從手繪建模到動(dòng)畫生成的一整套系統(tǒng)是作者最終的目標(biāo)。

[1] 任秉銀, 陳皓暉. 任意拓?fù)浣Y(jié)構(gòu)復(fù)雜曲面模型重構(gòu)新方法[J]. 機(jī)械工程學(xué)報(bào), 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] 韓 麗, 唐 棣. 手繪輸入的三維建模和編輯技術(shù)[J]. 計(jì)算機(jī)輔助設(shè)計(jì)與圖形學(xué)學(xué)報(bào), 2008, 20: 946-951.

[7] 謝 浩, 費(fèi)廣正, 吳明峰, 等. 從明暗恢復(fù)形狀的手繪草圖三維建模算法[J]. 工程圖學(xué)學(xué)報(bào), 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

國(guó)家自然科學(xué)基金國(guó)際（地區(qū)）合作交流資助項(xiàng)目（60573174）；特種顯示技術(shù)教育部重點(diǎn)實(shí)驗(yàn)室開放課題基金

劉曉平（1964-），男，山東濟(jì)南人，教授，主要研究方向?yàn)榻！⒎抡媾c協(xié)同計(jì)算。