劉敏

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

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

劉敏

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

本文主要從三維的Delaunay三角劃分、三維Voronoi圖和Sibson坐標值三個方面對算法進行全面分析。

自由變形算法 Delaunay三角劃分 Voronoi圖 Sibson局部坐標

1 三維Dirichlet算法概述

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

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

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

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

2 三維Delaunay三角劃分

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

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

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

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

3 三維Voronoi圖

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

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

我們需要知道物體點所在的Voronoi單元的體積以及每個控制點劃分得到的Voronoi單元的體積,相比即所謂的貢獻比例。

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

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

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

3.1 物體點的Voronoi單元的形成

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

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

3.2 控制點分割物體點的Voronoi單元

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

(1)我們就隨機選取一個控制點pi,以pi為頂點的棱E1設為

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

3.3 通過Sibson坐標來變形

根據(jù)公式,可以求得控制點的Sibson的局部坐標值

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

4 結(jié)語

本文介紹三維Delaunay三角劃分的具體過程和三維Voronoi圖的具體過程從而計算出Sibson局部坐標,通過細致的數(shù)學公式表達DFFD算法的實現(xiàn)步驟,從而實現(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-),性別:男,籍貫:江西豐城,學歷:碩士,職稱:高級講師,研究方向:計算機應用。