DFFD自由變形算法實(shí)現(xiàn)過程

劉敏

(泉州財(cái)貿(mào)職業(yè)技術(shù)學(xué)校,福建泉州 362000)

DFFD自由變形算法實(shí)現(xiàn)過程

劉敏

(泉州財(cái)貿(mào)職業(yè)技術(shù)學(xué)校,福建泉州 362000)

本文主要從三維的Delaunay三角劃分、三維Voronoi圖和Sibson坐標(biāo)值三個(gè)方面對算法進(jìn)行全面分析。

自由變形算法 Delaunay三角劃分 Voronoi圖 Sibson局部坐標(biāo)

1 三維Dirichlet算法概述

為了實(shí)現(xiàn)人臉夸張化變形,就必須在三維上進(jìn)行變形,由于現(xiàn)今Dirichlet自由變形算法多應(yīng)用于二維問題中,因此必須將其推廣至三維上。我們可以對比其在二維時(shí)的Delaunay三角劃分和Voronoi圖形成來實(shí)現(xiàn)算法的三維推廣。

首先,Delaunay三角劃分時(shí)不再是劃分為三角形,而是劃分成四面體。其次,在形成Voronoi圖時(shí)選取的是不再是三角形的外接圓圓心,而是四面體的外接球球心。最后,Sibson坐標(biāo)的值是由中垂面切割后的體積與Voronoi單元體積之比。因此,算法總的步驟如下：

(1)設(shè)計(jì)控制點(diǎn)集合,從讀入的物體點(diǎn)中選取控制點(diǎn),不需要在控制點(diǎn)集合上定義任何特殊的拓?fù)浣Y(jié)構(gòu)。控制點(diǎn)可以在物體表面,也可以在物體的內(nèi)部,但是物體需要變形的部分必須包含在控制點(diǎn)集合的凸包內(nèi)。(2)對控制點(diǎn)進(jìn)行三角劃分,并保存三角劃分所形成的四面體集合。對所有物體點(diǎn)遍歷控制點(diǎn)的四面體集合,從而能夠找到影響物體點(diǎn)的控制點(diǎn)集合,即為Sibson鄰居。(3)對單個(gè)物體點(diǎn)的Sibson鄰居(即影響它的控制點(diǎn)集合)進(jìn)行三角劃分,根據(jù)三角劃分結(jié)果,計(jì)算物體所在Voronoi單元和Voronoi單元體積。(4)計(jì)算Sibson鄰居劃分物體點(diǎn)的Voronoi單元所形成的Voronoi圖以及相應(yīng)的體積,每個(gè)Sibson鄰居劃分求得的體積與物體點(diǎn)的Voronoi單元體積之比就是控制點(diǎn)相對于物體點(diǎn)的Sibson坐標(biāo)值。(5)對所有物體點(diǎn)遍歷(3),(4)操作,從而可以求出每個(gè)物體點(diǎn)的Sibson鄰居的坐標(biāo)值。(6)通過移動控制點(diǎn),然后查找受影響的物體點(diǎn),并根據(jù)Sibson坐標(biāo)值計(jì)算受影響點(diǎn)的新坐標(biāo)值,從而達(dá)到物體變形效果。

接下來,我們就按照上面步驟介紹如何在三維空間中進(jìn)行Delaunay三角劃分,以及如何形成Voronoi圖,從而利用這些結(jié)果計(jì)算出Sibson坐標(biāo)值。

2 三維Delaunay三角劃分

我們依舊按照二維Delaunay三角劃分的思想,采用超四面體的方法來進(jìn)行三角劃分。

首先,構(gòu)造一個(gè)包含所有控制點(diǎn)的超四面體,通過遍歷所有控制點(diǎn)找到其中含有x,y,z的最大值和最小值的點(diǎn)。然后通過以下公式構(gòu)造點(diǎn)

在構(gòu)造出超四面體之后,將進(jìn)行依次插入點(diǎn)對其進(jìn)行三角劃分,生成三角網(wǎng)格。具體步驟如下：

(1)插入第一個(gè)點(diǎn)時(shí),該點(diǎn)與超四面體的每一個(gè)面都形成一個(gè)四面體。記錄這三個(gè)四面體,將其存儲。(2)從第二點(diǎn)開始,插入點(diǎn)之后,判斷此點(diǎn)在哪個(gè)四面體的外接球內(nèi),將相對應(yīng)的四面體記錄,并刪除這些四面體中所包含的相同的面,從存儲四面體的數(shù)據(jù)結(jié)構(gòu)刪除這些四面體。這樣這些四面體去除相同面之后就形成一個(gè)多面體凸殼。(3)新插入的點(diǎn)與這個(gè)多面體凸殼的每個(gè)面都形成一個(gè)四面體,將這些四面體存儲。(4)重復(fù)(2),(3)步驟,直到所有點(diǎn)都插入。然后刪除超四面體和包含超四面體頂點(diǎn)的四面體,剩余的四面體集合即為控制點(diǎn)集合的三角劃分結(jié)果。該結(jié)果主要用來確定物體點(diǎn)的Sibson鄰居集合,即四面體的外接球包含該物體的四面體的頂點(diǎn)集合都為物體點(diǎn)的Sibson鄰居。

3 三維Voronoi圖

Voronoi圖是為Sibson坐標(biāo)的生成而鋪墊的,它是Delaunay三角劃分結(jié)果的對偶圖。在二維的Voronoi單元中,其Voronoi邊是由三角劃分結(jié)果的三角形邊的中垂線相交而成。Voronoi單元頂點(diǎn)則由這些中垂線的交點(diǎn)構(gòu)成,這些頂點(diǎn)也是三角形外接圓的圓心。通過最簡單的類比,我們可以知道,將一條線(A,B)放于三維空間中,要找距離A點(diǎn)比距離B點(diǎn)近的所有點(diǎn),則可以找到這條線的垂直平分面,將空間劃分為兩塊,包含A點(diǎn)的空間內(nèi)的所有點(diǎn)到達(dá)A點(diǎn)的距離比到達(dá)B點(diǎn)的距離近。而對于點(diǎn)集S由n個(gè)點(diǎn)組成距離iP比距離其他點(diǎn)更近的點(diǎn)的區(qū)域是包含iP的那n-1個(gè)半空間的交集。這n-1個(gè)半空間是由點(diǎn)與其他點(diǎn)的垂直平分面確定的。所以,我們得知：三維空間中Voronoi圖是一個(gè)多面體,多面體由三角劃分結(jié)果的四面體棱經(jīng)過其中垂面相交劃分而得到的,四面體四條邊的中垂面交點(diǎn)即為四面體外接球的球心,從而形成了Voronoi圖的頂點(diǎn)。因此,Voronoi圖是根據(jù)上步的Delaunay三角劃分結(jié)果而得來。

在DFFD算法中,Voronoi圖是用來求Sibson鄰居坐標(biāo)值的,根據(jù)公式

我們需要知道物體點(diǎn)所在的Voronoi單元的體積以及每個(gè)控制點(diǎn)劃分得到的Voronoi單元的體積,相比即所謂的貢獻(xiàn)比例。

首先討論如何生成物體點(diǎn)所在的Voronoi單元。在得到三角劃分結(jié)果后的具體步驟如下：

(1)通過物體點(diǎn)以及三角劃分的結(jié)果,找到影響該物體點(diǎn)的控制點(diǎn)集合,即通過三角劃分結(jié)果尋找其四面體的外接球包含物體點(diǎn),這些四面體的頂點(diǎn)即為要找的控制點(diǎn)集合。(2)將這些控制點(diǎn)重新進(jìn)行三角劃分。根據(jù)三角劃分的結(jié)果可以計(jì)算得到物體點(diǎn)的Voronoi單元。(3)重復(fù)(1),(2)步驟,則可以得到所有物體點(diǎn)的Voronoi單元。

通過類比二維Voronoi圖我們可以知道：(1)共面的四面體的球心連線為Voronoi單元的一條棱;(2)共棱的四面體的球心共面,一次連接共棱的四面體的球心構(gòu)成的面即為Voronoi單元的一個(gè)面。

3.1 物體點(diǎn)的Voronoi單元的形成

根據(jù)上面得到的Voronoi單元的棱和面的生成方法,可知物體點(diǎn)的Voronoi單元的形成過程,具體步驟如下：

(1)從物體點(diǎn)的Sibson鄰居坐標(biāo)中選取一點(diǎn),設(shè)為pi,從保存Sibson鄰居集合的三角劃分結(jié)果的四面體所形成的凸包中(說明已經(jīng)去掉重復(fù)面),找到包含該控制點(diǎn)pi的第一個(gè)面,將該面設(shè)為已用,并從該面中找到一條以pi為點(diǎn)的邊pipj,將該面所在的四面體的外接球球心保存。(2)找到包含pipj邊的另一個(gè)面,把該面設(shè)為已用,并把該面對應(yīng)的四面體的外接球球心保存。(3)選擇此面上以p為頂點(diǎn)的另一條邊pipk。(4)重復(fù)(2),(3)依次找到包含pi的所有面,每個(gè)面對應(yīng)一個(gè)四面體的外接球球心(因?yàn)槭窃谕拱?所以一個(gè)面只會對應(yīng)一個(gè)四面體),依次連接這些球心可以形成一個(gè)多邊形,這個(gè)多邊形即為Voronoi單元的一個(gè)面。

3.2 控制點(diǎn)分割物體點(diǎn)的Voronoi單元

Sibson局部坐標(biāo)值為控制點(diǎn)所分割物體點(diǎn)Voronoi單元所剩下部分的體積與物體點(diǎn)的Voronoi單元體積之比。現(xiàn)在我們就來介紹如何用控制點(diǎn)分割物體點(diǎn)的Voronoi單元。具體步驟如下：

(1)我們就隨機(jī)選取一個(gè)控制點(diǎn)pi,以pi為頂點(diǎn)的棱E1設(shè)為

i pipj,使用下面方法求它的中垂面方程。由于我們已知pi的坐標(biāo)為pj的坐標(biāo)為。我們可以根據(jù)點(diǎn)法式來求垂直平分面,首先我們知道面的法線為且E1的中點(diǎn)為面上的點(diǎn),設(shè)中點(diǎn)為s,其坐標(biāo)為

3.3 通過Sibson坐標(biāo)來變形

根據(jù)公式,可以求得控制點(diǎn)的Sibson的局部坐標(biāo)值

對于給定控制點(diǎn)集合 Pn和其凸包內(nèi)的一點(diǎn)p的Sibson鄰居集合計(jì)算出p相對于Pn的Sibson局部坐標(biāo)當(dāng)移動Pn中一個(gè)或多個(gè)控制點(diǎn)后,假設(shè)控制點(diǎn)的新位置為控制點(diǎn)pi的位移Δpi可以等于0,那么凸包內(nèi)點(diǎn) p的新位置P′就由來確定。

4 結(jié)語

本文介紹三維Delaunay三角劃分的具體過程和三維Voronoi圖的具體過程從而計(jì)算出Sibson局部坐標(biāo),通過細(xì)致的數(shù)學(xué)公式表達(dá)DFFD算法的實(shí)現(xiàn)步驟,從而實(shí)現(xiàn)了DFFD自由變形算法。

This paper is divided, three-dimensional Voronoi diagram and Sibson coordinate values ??of the three aspects of a comprehensive analysis of algorithms from the three-dimensional Delaunay triangulation.

free-form deformation algorithm Delaunay triangulation Voronoi diagram Sibson local coordinate

劉敏(1974.10.16-),性別:男,籍貫:江西豐城,學(xué)歷:碩士,職稱:高級講師,研究方向:計(jì)算機(jī)應(yīng)用。