三維空間中的Dirichlet自由變形算法

1、第36卷 第3期 電 子 科 技 大 學(xué) 學(xué) 報(bào) V ol.36 No.3 2007年6月 Journal of University of Electronic Science and Technology of China Jun. 2007三維空間中的Dirichlet 自由變形算法郭際香,蒲曉蓉,章 毅(電子科技大學(xué)計(jì)算機(jī)科學(xué)與工程學(xué)院 成都 610054【摘要】自由變形是與物體表示無關(guān)的變形方法的重要分支,被廣泛地應(yīng)用于計(jì)算機(jī)動(dòng)畫和幾何建模領(lǐng)域中。Dirichlet 自由變形是眾多自由變形方法中的一種,相比其他的自由變形方法,它有更大的靈活性,能夠任意設(shè)置控制點(diǎn)。Dirichlet

2、自由變形算法在二維空間已獲得了廣泛的應(yīng)用,但在三維空間中的應(yīng)用卻非常少。該文研究Dirichlet 自由變形算法在三維空間的實(shí)現(xiàn)問題,將Dirichlet 自由變形算法應(yīng)用到三維空間中的頭像變形中,獲得了較好的變形效果。關(guān) 鍵 詞 Delaunay 三角劃分; 自由變形; Sibson 局部坐標(biāo); V oronoi 圖 中圖分類號(hào) TP391 文獻(xiàn)標(biāo)識(shí)碼 ADirichlet Free-Form Deformation in Three-Dimensional SpaceGUO Ji-xiang ,PU Xiao-rong ,ZHANG Yi(School of Computer Scienc

3、e and Engineering, University of Electronic Science and Technology of China Chengdu 610054Abstract Free Form Deformations (FFDs have been extensively applied in computer animation and geometric modeling. FFD is an important branch of deformation methods which independent of object representation. Di

4、richlet Free-Form Deformation (DFFD belongs to one of the FFDs. Comparing with other FFDs, it gives deformation more flexibility and has the ability to place control points arbitrarily. DFFD has been extensively applied in two-dimensional space, but seldom in three-dimensional space. This paper stud

5、ies the application of DFFD in three-dimensional space. Good deformation results have been obtained by applying DFFD to 3D head-deformation.Key words Delaunay triangulation; free-form deformation; Sibson local coordinate; V oronoi diagrams收稿日期:2005 06 16基金項(xiàng)目:國(guó)家自然科學(xué)基金資助項(xiàng)目(60471055作者簡(jiǎn)介:郭際香(1981 ,女,碩士生

6、,主要從事三維物體變形方面的研究;蒲曉蓉(1969 ,女,副教授,主要從事計(jì)算智能及生物特征識(shí)別方面的研究;章 毅(1963 ,男,博士,教授,博士生導(dǎo)師,主要從事計(jì)算智能方面的研究.自由變形1(Free Form Deformations ,FFD算法是目前物體變形方法中最實(shí)用的方法之一。FFD 方法不對(duì)物體直接變形,而是對(duì)物體所嵌入的空間進(jìn)行變形。FFD 方法中的控制框架的形狀為平行六面體,它通過移動(dòng)控制框架頂點(diǎn)使物體產(chǎn)生變形,達(dá)到對(duì)嵌入的物體產(chǎn)生變形。Dirichlet 自由變形算法(Dirichlet Free-Form Deformation ,DFFD是FFD 諸多改進(jìn)算法中應(yīng)用較

7、廣泛的一種,該方法剔除了對(duì)控制框架的限制,對(duì)復(fù)雜物體的形變產(chǎn)生很好的效果。目前關(guān)于DFFD 算法的二維應(yīng)用已經(jīng)有許多介紹,但該算法在三維空間的使用還較少。本文結(jié)合在使用該方法做三維人臉變形過程遇到的難點(diǎn)和相應(yīng)的解決方法,來論述DFFD 算法在三維空間的實(shí)現(xiàn)。1 DFFD 算法的二維實(shí)現(xiàn) DFFD 2的思想是:給定控制點(diǎn)集合P n 和其凸包內(nèi)的一點(diǎn)p ,可以確定p 的Sibson 鄰居集合P n =p i |,并計(jì)算出p 相對(duì)于P 0i n n 的Sibson 局部坐標(biāo)u i (。當(dāng)移動(dòng)P 0i n n 中一個(gè)或多個(gè)控制點(diǎn)后,假設(shè)控制點(diǎn)的新位置,控制點(diǎn)的位移(0i i i P p p i n =

8、+i p i p 可以等于0。那么凸包內(nèi)點(diǎn)p 的 新位置P 就由0ni i i p u p =和來確定。p p p =+在實(shí)際應(yīng)用中,可以根據(jù)需要對(duì)物體的不同部位設(shè)置控制點(diǎn),然后通過移動(dòng)這些控制點(diǎn)對(duì)物體局部或整體產(chǎn)生形變。DFFD 算法的關(guān)鍵就是求物體點(diǎn)的Sibson 坐標(biāo)3,在計(jì)算Sibson 坐標(biāo)中會(huì)用到Delaunay 三角劃分4和求V oronoi 圖5(簡(jiǎn)稱V 圖。Sibson 局部坐標(biāo)3也稱為自然鄰居坐標(biāo)(Natural Neighbor Coordinate,在V 圖的基礎(chǔ)上就可以定義Sibson 局部坐標(biāo)。下面以圖示簡(jiǎn)單地介紹在二維空間如何求一個(gè)點(diǎn)的Sibson 局部坐標(biāo)。圖1

9、所示是點(diǎn)集P =p 1, p 2, p 3,p 4,的V 圖,p 是點(diǎn)集P 的凸包內(nèi)任意一點(diǎn);圖2所示是加入點(diǎn)p 后的V 圖,由于p 1, p 2, p 3, p 4所在的V 單元電子科技大學(xué)學(xué)報(bào)第36卷574都與p所在的V單元相鄰,所以它們都是p的Sibson鄰居;圖3是圖1和圖2的疊加,表示加入點(diǎn)p之后V圖的變化,陰影部分為p4對(duì)點(diǎn)p所在的V單元的貢獻(xiàn),該貢獻(xiàn)與點(diǎn)p所在V單元中的面積比例就是p相對(duì)與p4的Sibson局部坐標(biāo)。p4p2p3 Pp1p4Pp3p2p1圖1 p1,p2,p4的V圖圖2 p1,p2,p4和P的V圖pp3p2p1圖3 p4對(duì)點(diǎn)P的V圖的貢獻(xiàn)2 Dirichlet自由

10、變形算法的三維實(shí)現(xiàn)DFFD算法在二維空間已經(jīng)獲得了廣泛的應(yīng)用,但在三維空間中的應(yīng)用卻非常少。由圖1圖3可知Dirichlet自由變形算法在二維空間顯得簡(jiǎn)單、直觀。但由于算法涉及到的數(shù)學(xué)內(nèi)容較多,推廣到三維空間后由于幾何上的變化,如Delaunay劃分的結(jié)果將由三角形變?yōu)樗拿骟w,V圖也由多邊形變?yōu)槎嗝骟w,導(dǎo)致生成V圖的過程變得相當(dāng)復(fù)雜,對(duì)求每個(gè)控制點(diǎn)所在V圖(即劃分得到多面體的一部分帶來很大的難度,因此三維空間中DFFD算法實(shí)現(xiàn)的難度、復(fù)雜度都比較大。本文通過六個(gè)步驟,對(duì)DFFD在三維空間的實(shí)現(xiàn)做一詳細(xì)的論述:(1 設(shè)計(jì)控制點(diǎn)集合,不需要在控制點(diǎn)集合上定義特殊的拓?fù)浣Y(jié)構(gòu)?？刂泣c(diǎn)可以在待變物體的表

11、面上,也可以在物體的內(nèi)部,但是物體需要變形的部分必須包含在控制點(diǎn)集合的凸包內(nèi);(2 設(shè)計(jì)好控制點(diǎn)后,遍歷物體的每個(gè)點(diǎn),根據(jù)Delaunay三角劃分(Delaunay Triangulation, DT的結(jié)果,找出每個(gè)點(diǎn)相應(yīng)的Sibson鄰居集合;(3 對(duì)每個(gè)物體和它的Sibson 鄰居,求出V圖劃分,及相應(yīng)V圖的面積(體積;(4 根據(jù)上面的結(jié)果,求出每個(gè)點(diǎn)的Sibson局部坐標(biāo);(5 移動(dòng)控制點(diǎn),可以用任意方法移動(dòng)一個(gè)或一組控制點(diǎn);(6 計(jì)算出物體上點(diǎn)的位移和新位置,從而達(dá)到物體局部(整體的變形。2.1三維Delaunay三角劃分實(shí)現(xiàn)俄國(guó)數(shù)學(xué)家Delaunay曾經(jīng)指出:對(duì)于平面域上的N個(gè)散亂點(diǎn)

12、集,存在且僅存在一種三角剖分,使得所有三角形的最小內(nèi)角之和為最大,稱之為Delaunay 三角劃分。Delaunay三角劃分的實(shí)現(xiàn)有多種方法,本文中采用文獻(xiàn)4的算法。但該算法只介紹了DT劃分在二維的實(shí)現(xiàn),本文把它推廣到三維空間中來使用,其思想即是由一個(gè)已存在的三角形網(wǎng)格,逐步加入新點(diǎn)生成,因此首先在三維空間中構(gòu)造一個(gè)包含所有要?jiǎng)澐贮c(diǎn)的超四面體。超四面體通過尋找三個(gè)方向軸上的最小、最大值計(jì)算得到。在構(gòu)造出超四面體后,進(jìn)行空間所有點(diǎn)的三角劃分,即依次插入要?jiǎng)澐值拿總€(gè)點(diǎn),生成三角網(wǎng)格。插入點(diǎn)的規(guī)則如下:(1 插入第一個(gè)點(diǎn)時(shí),該點(diǎn)和每個(gè)面生成一個(gè)四面體,即此次劃分生成四個(gè)四面體;(2 以后每插入一個(gè)點(diǎn)

13、,首先判斷該點(diǎn)包含在哪些四面體的外接球內(nèi),找出包含該點(diǎn)的四面體,然后刪除這些四面體中重復(fù)的面,剩余的面即是這些四面體的外圍,為一個(gè)多面體(對(duì)應(yīng)于二維中的多邊形,然后新插入的點(diǎn)和這個(gè)多面體的每個(gè)面形成一個(gè)四面體,即插入新點(diǎn)后三角劃分的結(jié)果。重復(fù)步驟(1、(2直至所有的點(diǎn)都完成。然后刪掉超四面體,則為三角劃分的結(jié)果。該結(jié)果主要用來求每個(gè)物體點(diǎn)的Sibson鄰居,而物體點(diǎn)的Sibson鄰居即是那些外接球包含該點(diǎn)的四面體的頂點(diǎn)的集合。2.2三維V圖的實(shí)現(xiàn)V圖實(shí)際就是DT劃分的對(duì)偶圖。把二維V圖性質(zhì)進(jìn)一步推廣、論證得到三維空間中V圖的性質(zhì):V 圖的面即是三角劃分后四面體的兩個(gè)頂點(diǎn)的中垂面,V圖的頂點(diǎn)是三

14、角劃分得到的四面體的外接球的球心,那么從DT劃分結(jié)果就可得到V圖的劃分。在DFFD算法中V圖主要用來計(jì)算Sibson坐標(biāo),需要知道物體點(diǎn)所在的V圖及每個(gè)控制點(diǎn)劃分得到V圖和它們相應(yīng)的體積,進(jìn)而求出該物體點(diǎn)的Sibson 局部坐標(biāo)值。2.2.1 物體點(diǎn)V圖的生成由上面得到的V圖性質(zhì),本文提出物體點(diǎn)V圖的生成算法如下:首先通過物體點(diǎn)DT劃分的結(jié)果找出影響每個(gè)點(diǎn)的控制點(diǎn)集合,即物體點(diǎn)的Sibson鄰居,對(duì)這些控制點(diǎn)重新進(jìn)行三角劃分;加入物體點(diǎn)后的三角劃分,根據(jù)DT劃分的思想直接去掉控制點(diǎn)三角劃分結(jié)果中四面體的重復(fù)面,把物體點(diǎn)和每個(gè)面連接即得到的物體點(diǎn)和其控制點(diǎn)的三角劃分結(jié)果?？刂泣c(diǎn)的三角劃分結(jié)果去掉

15、重復(fù)面后為一個(gè)外圍的多第3期郭際香等: 三維空間中的Dirichlet自由變形算法575面體,保存這個(gè)多面體每個(gè)面的頂點(diǎn)的下標(biāo)到數(shù)組ArrCtrlFacet中,用于求每個(gè)控制點(diǎn)所在的V圖。下面論述如何通過控制點(diǎn)和物體點(diǎn)三角劃分的結(jié)果來構(gòu)造物體點(diǎn)所在的V圖。經(jīng)過論證得到如下結(jié)論:(1 共面的四面體的球心連線,該線為V圖多面體的一條棱;(2 共棱的四面體的球心共面,連接共棱的四面體的球心成面即為V圖多面體的一個(gè)面。由求得的Sibson坐標(biāo),可以得出物體點(diǎn)的V圖由該點(diǎn)與其鄰居點(diǎn)的中垂線構(gòu)成,同理三維空間則為物體點(diǎn)和每個(gè)控制點(diǎn)的中垂面構(gòu)成。下面以一個(gè)控制點(diǎn)為例介紹物體點(diǎn)的V圖生成,對(duì)所有的控制點(diǎn)按如下

16、步驟進(jìn)行操作,就生成最終的V圖結(jié)果:(1 設(shè)a i為一控制點(diǎn),在ArrCtrlFacet中,找一個(gè)包含該控制點(diǎn)的面,然后在該面上找一條邊E1為a i a j,并把該面設(shè)為已用,避免重復(fù)使用,保存該面相應(yīng)的四面體的球心于數(shù)組pArr中;(2 尋找包含E1的另一個(gè)面,把該面相應(yīng)的四面體的球心存于數(shù)組pArr中,然后選擇該面上以a i為頂點(diǎn)的另外一條邊a i a m=E1;(3 重復(fù)步驟(2依次找到包含頂點(diǎn)a的所有面,每個(gè)面對(duì)應(yīng)一個(gè)四面體的球心,依續(xù)連接這些球心成一個(gè)多邊形,則為V圖的一個(gè)面。上面的步驟,保證了共面的四面體的兩個(gè)球心連成線,而共棱的四面體的球心依次連成形成V圖一個(gè)面。因此對(duì)剩余的控制

17、點(diǎn)重復(fù)上面三個(gè)步驟,將會(huì)得到物體點(diǎn)所在V圖(一個(gè)多面體。2.2.2 控制點(diǎn)分割物體點(diǎn)V圖的算法Sibson局部坐標(biāo)為每個(gè)控制點(diǎn)所分割的物體點(diǎn)V圖的體積與物體點(diǎn)V圖體積之比,下面仍以一個(gè)控制點(diǎn)a i為例闡述每個(gè)控制點(diǎn)分割物體點(diǎn)V圖的算法:(1 首先找到和控制點(diǎn)a i相關(guān)的棱,并把相應(yīng)的頂點(diǎn),存放于數(shù)組ArrCtrlPoint中;(2 對(duì)每一條和a i相關(guān)的棱E1設(shè)為a i a j,求該棱的中垂面方程,中垂面表達(dá)式為:Ax+By+Cy+D =0;(3 用該中垂面切多面體,得到離控制點(diǎn)a i近的那一部分的區(qū)域。具體做法為:用中垂面切多面體的每個(gè)面,保留頂點(diǎn)全位于中垂面正側(cè)的面,丟掉頂點(diǎn)全位于中垂面負(fù)

18、側(cè)的面,對(duì)于和中垂面相交的面,根據(jù)面上的頂點(diǎn)和中垂面的關(guān)系(正側(cè)、負(fù)側(cè)、在面上做如下處理:求出面和中垂面的交線,與位于正側(cè)的點(diǎn)構(gòu)成新的面,丟掉負(fù)側(cè)的點(diǎn);(4 找與控制點(diǎn)相關(guān)的另一條棱a i a m,重復(fù)步驟(2、(3,將得到該控制點(diǎn)相應(yīng)的V 圖,求該V圖的體積和物體點(diǎn)V圖的體積之比即為該控制點(diǎn)的Sibson局部坐標(biāo)。通過上面的步驟可以求出三維空間每個(gè)物體點(diǎn)的Sibson局部坐標(biāo):(n i n iinVol V P p IV P puVol V P p=(1 式中Vol(為返回給定V單元的體積。3 3D人臉變形的實(shí)現(xiàn)及結(jié)果本文將DFFD算法應(yīng)用于三維的人臉變形,在應(yīng)用過程中,對(duì)人臉的四個(gè)部位:臉頰、鼻子、額頭、下巴分別設(shè)置了相應(yīng)的控制點(diǎn),通過移動(dòng)這些控制點(diǎn)來達(dá)到對(duì)這些部位的變形。圖4中第一張為一中性的人臉,后面的圖為拖動(dòng)這些部位的控制點(diǎn)產(chǎn)生的變形效果。由于控制點(diǎn)設(shè)置不是很多,所以頭像的差別不是很大,但是各個(gè)部位的變形結(jié)果還是很明顯,效果也很好。如果設(shè)置更多的控制點(diǎn),可生成可區(qū)分性較大的人臉。 圖4 3D人臉的變形結(jié)果