李 琳， 謝文軍， 劉曉平

（合肥工業(yè)大學(xué)計(jì)算機(jī)與信息學(xué)院可視化與協(xié)同計(jì)算(VCC)研究室，安徽 合肥 230009）

模型分割技術(shù)是計(jì)算機(jī)圖形學(xué)中幾何處理的一個(gè)關(guān)鍵問題，它是很多應(yīng)用和研究工作的基礎(chǔ)，包括三維檢索與建模、網(wǎng)格變形、網(wǎng)格壓縮和簡(jiǎn)化、紋理映射、骨架提取與動(dòng)畫生成等。由于它是一個(gè)很重要的共性問題，所以研究工作自90年代以來從未間斷。國(guó)內(nèi)外近幾年都有綜述性文獻(xiàn)對(duì)它進(jìn)行廣泛而深入的探討和展望[1-3]。Ariel Shamir[2]將網(wǎng)格分割分為塊分割和部件分割兩種情況，認(rèn)為部件分割均需要產(chǎn)生有意義的結(jié)果，因而部件分割大都基于人類感知利用其結(jié)構(gòu)性分解為語義部件。部件分割有一個(gè)重要的應(yīng)用目的是基于實(shí)例的建模[4]，就是從已有的三維模型中分割出所需要的部件用來替換正在制作模型的同樣部件。

在游戲和電影電視動(dòng)畫中經(jīng)常使用的三維角色模型制作周期長(zhǎng)，樣式單調(diào)，且現(xiàn)有的復(fù)雜建模工具難以對(duì)角色模型的部件進(jìn)行重用，參考基于實(shí)例的建模方式，角色模型的分割是進(jìn)行三維角色模型快速?gòu)?fù)用，從而提高建模效率，豐富角色多樣性的首要解決問題。由于模型分割的應(yīng)用面非常廣泛，從而導(dǎo)致了面向不同的應(yīng)用所采用的技術(shù)與方法眾多，Ariel Shamir在文獻(xiàn)中列舉了 10種技術(shù)以及在技術(shù)中可以稱之為參考的16種特征屬性[2]。在游戲和影視動(dòng)畫中經(jīng)常使用的三維角色模型除了三維網(wǎng)格，設(shè)計(jì)師還必須為角色設(shè)計(jì)用于動(dòng)畫的骨骼，并建立起網(wǎng)格模型與骨骼之間的關(guān)聯(lián)——蒙皮信息，相比于只從三維網(wǎng)格上尋找分割特征屬性的技術(shù)，角色模型有著額外適合分割的語義特征屬性——骨骼和蒙皮，但由于其特殊的應(yīng)用領(lǐng)域與構(gòu)成要素，使得沒有研究關(guān)注此類模型的分割問題。但是在 Ariel提到的模型分割技術(shù)中，有一類基于骨骼特征或運(yùn)動(dòng)序列的分割在利用骨骼語義的想法上有著相似性，即認(rèn)為動(dòng)畫中運(yùn)動(dòng)屬性相似的點(diǎn)應(yīng)該屬于一個(gè)語義部件。文獻(xiàn)[5]通過拓?fù)湎嗨魄蠼獬龌镜墓羌芫€，然后使用與骨骼垂直的連續(xù)截面掃掠三維模型表面，產(chǎn)生頂點(diǎn)分割以達(dá)到模型分解為語義部件的目的；文獻(xiàn)[6]對(duì)一段給定模型的運(yùn)動(dòng)序列進(jìn)行主成份分析給出統(tǒng)一表示，然后匹配頂點(diǎn)間運(yùn)動(dòng)相關(guān)性，考察相似度來分割模型頂點(diǎn)。這些方法因?yàn)橹痪哂腥S模型信息，因此求解骨架或運(yùn)動(dòng)關(guān)聯(lián)度非常困難，而且對(duì)模型的復(fù)雜性以及骨架的清晰度也有一定的要求；而動(dòng)畫角色模型的自身屬性為各種復(fù)雜模型的分割創(chuàng)造了優(yōu)厚的先天條件，適應(yīng)性更強(qiáng)。

本文針對(duì)游戲和三維動(dòng)畫中已經(jīng)存在的三維角色模型，提出一種在蒙皮信息約束下的模型分割技術(shù)，通過已知的骨骼語義與約束，查找相應(yīng)的蒙皮信息，確定屬于某個(gè)語義部件的幾何數(shù)據(jù)，并根據(jù)一定的拓?fù)浼s束和分割規(guī)則對(duì)該數(shù)據(jù)進(jìn)行調(diào)整和優(yōu)化。與之前各類型的自動(dòng)分割方法比較，本文方法簡(jiǎn)單易用，適應(yīng)性強(qiáng)，但要求處理的對(duì)象是完整的角色模型。在實(shí)際應(yīng)用中，此類模型是游戲與動(dòng)畫的基礎(chǔ)，擁有大量的數(shù)據(jù)來源，本文的研究?jī)?nèi)容即來自一個(gè)游戲角色建模中的項(xiàng)目，將不同的角色通過分割重組為一個(gè)新的角色，從而加快建模速度，提高建模效率。

1 形式化表示與算法框架

文獻(xiàn)[2]中將模型分割總結(jié)為一個(gè)最優(yōu)化問題，將分割對(duì)象描述為一三元組M= ＜V,E,F＞（其中V——頂點(diǎn)、E——邊、F——面片），分割即是尋找使得判定條件J最大或者最小的幾何元素集合S，使得S可以分割出M的子集M' = ＜V',E',F'＞。由于傳統(tǒng)模型分割算法僅是針對(duì)靜態(tài)三維網(wǎng)格模型，因此點(diǎn)、邊、面表示方法已經(jīng)足夠，但是對(duì)于游戲與動(dòng)畫中使用的三維角色模型，還存在著骨骼和蒙皮信息，因此描述需要擴(kuò)充到五元組。

定義1角色模型C被定義為一個(gè)五元組C= ＜V,E,F,B,SK＞，其中頂點(diǎn)V= {pi|pi∈R3,1≤i≤m}，邊骨骼且三維模型為三角化封閉網(wǎng)格，除重心外任一骨骼僅有一關(guān)聯(lián)骨骼，蒙皮正確完整。

本文采取根據(jù)骨骼語義信息來選擇分割后的頂點(diǎn)集合，由于每個(gè)頂點(diǎn)i受各骨骼j影響的蒙皮約束信息ijr有所不同，需要給出一定的權(quán)值判定條件1J；由于三維部件模型拓?fù)浼s束關(guān)系，需要給出一定的條件限制2J；為了將分割出的模型利于組合，需要給出優(yōu)化規(guī)則3J。

定義 2角色模型C分割是一個(gè)最優(yōu)化問題，給出一個(gè)角色C與骨骼語義信息集合B' ，找到一個(gè)頂點(diǎn)集合V'可以將C分解為1C與2C兩個(gè)角色部件，并同時(shí)滿足條件規(guī)則集合

定義 3 角色部件pC也是一個(gè)五元組＞，其每一項(xiàng)都是被分割的源角色C的子集，且 ＜Vp,Ep,Fp＞構(gòu)成的三維模型符合三角化要求，不封閉但僅有一個(gè)缺口，任一骨骼僅有一關(guān)聯(lián)骨骼，蒙皮正確完整。

角色部件可以作為部件信息保存下來，并且因?yàn)槭且粋€(gè)完備的集合，可以多次使用。由上述定義及描述可以給出本文模型分割技術(shù)的算法框架，如圖1所示。

圖1 本文算法框架

2 基于骨骼與蒙皮的預(yù)分割策略

2.1 子樹選擇法

骨骼是動(dòng)畫角色的重要構(gòu)成部分，與三維網(wǎng)格模型相比，它帶有明顯的語義特征，骨骼間有著從屬關(guān)系，通常用樹來表示，如圖 2[7]，立方體線框表示犀牛的骨骼，左邊是所有骨骼所代表的樹。每一個(gè)BONE是樹節(jié)點(diǎn)，表示為：

圖2 骨骼樹的從屬關(guān)系

骨骼的名字代表了角色的某個(gè)部件的一部分，比如Thigh表示上腿骨、Tail表示尾巴根。在角色部件的分割中，往往需要切割出更大程度的語義所表示的部件，比如下肢，則需要上腿骨、下腿骨、腳掌、腳趾等骨骼所代表的部分總集，如圖2中的白色矩形表示的范疇。在骨骼的層次關(guān)系中，其父子關(guān)系反映了動(dòng)作相關(guān)性，具有相關(guān)性運(yùn)動(dòng)趨勢(shì)的頂點(diǎn)可以認(rèn)為是代表了一定語義范疇的部件概念，因此，當(dāng)用戶給出一個(gè)骨骼語義，可以以該骨骼為根結(jié)點(diǎn)搜索該子樹上所有結(jié)點(diǎn)并加入到骨骼選擇集合中，從而找到該骨骼所聯(lián)動(dòng)或代表的語義部件。搜索骨骼集合B'可以采用樹的深度遍歷算法。算法描述如下：

2.2 蒙皮權(quán)重對(duì)選擇頂點(diǎn)的影響

蒙皮(SKIN)是一種模型頂點(diǎn)受骨骼影響而產(chǎn)生動(dòng)畫的技術(shù)，受骨骼影響程度越明顯的頂點(diǎn)i相應(yīng)于這個(gè)骨骼j的蒙皮約束信息ijr就越大，關(guān)節(jié)處往往受到上下兩根骨骼的影響，如圖3所示，受上腿骨影響的頂點(diǎn)顏色越偏藍(lán)色調(diào)代表蒙皮值越小。蒙皮數(shù)據(jù)SK=（其中i是頂點(diǎn)數(shù)目，j是骨骼數(shù)目）是一個(gè)龐大的稀疏矩陣，可以從其第j列找到受j骨骼影響的所有頂點(diǎn)，由于影響權(quán)重不同，因此挑選規(guī)則成為影響分割取舍的重要參數(shù)化約束條件；由于每次搜索到的骨骼集合一般不止一個(gè)骨骼j，因此對(duì)于頂點(diǎn)i計(jì)算新權(quán)重)，相應(yīng)的規(guī)則變?yōu)镴1:ri≥R。初始R值可以采取折半方法取50，根據(jù)調(diào)節(jié)R值來尋求一個(gè)較為滿意的區(qū)域結(jié)果，但并不一定存在完全正確和最優(yōu)的解。

圖3為根據(jù)上腿骨找犀牛相關(guān)頂點(diǎn)所產(chǎn)生的結(jié)果?？梢园l(fā)現(xiàn)，選擇后的頂點(diǎn)集合一般并不符合角色部件的拓?fù)錀l件，多數(shù)情況下有可能有孤立點(diǎn)、孤立線（如圖3）、孤立面；或者即使連通也是低連通，其中會(huì)有橋[8]；如果切割產(chǎn)生了多個(gè)缺口（下文稱缺口環(huán)），則給后來使用這個(gè)部件再組合新角色制造了一定的困難，這時(shí)就需要在預(yù)分割的基礎(chǔ)上進(jìn)行頂點(diǎn)求解與優(yōu)化，使之滿足拓?fù)浼s束，并且能夠減少缺口環(huán)，使分割口盡量規(guī)則圓滑。

圖3 骨骼選擇頂點(diǎn)的結(jié)果

3 拓?fù)湟?guī)則與優(yōu)化目標(biāo)

3.1 拓?fù)浼s束

為了對(duì)預(yù)分割后的頂點(diǎn)集合進(jìn)一步處理，可以將該頂點(diǎn)集合V'構(gòu)成的三維網(wǎng)格看作一三元組M' = ＜V',E',F'＞ ，邊集E' = {eij|eij∈E∧i,j∈V'}，面集F' = {fijk|fijk∈F∧i,j,k∈V'}。該網(wǎng)格必須滿足定義 3中對(duì)角色部件的拓?fù)湟?guī)則J2：所有頂點(diǎn)連通，每個(gè)點(diǎn)都是三角面片的頂點(diǎn)，不封閉但僅有一個(gè)缺口環(huán)。

三維網(wǎng)格是全封閉的必要條件是每一條邊都被兩個(gè)面所擁有，那么在預(yù)分割后的三維網(wǎng)格中出現(xiàn)的只在一個(gè)面上的邊或者沒有面包含的邊都是由于網(wǎng)格分離而造成的，因此很容易檢測(cè)出沒有封閉的切口處，如果切口處恰巧是一個(gè)頭尾相連的環(huán)，那么切口是滿足拓?fù)湟蟮?，否則認(rèn)為切口出現(xiàn)了孤立點(diǎn)、線、面、橋或多個(gè)環(huán)的可能性，如圖4所示。由于蒙皮信息的連續(xù)性，一般是延著環(huán)狀切口向外延伸出現(xiàn)少量孤立或由橋連接的點(diǎn)集，或者切割到一些突起或凹陷的部分而產(chǎn)生多余缺口環(huán)。針對(duì)這種特點(diǎn)，在將切口處的頂點(diǎn)和邊轉(zhuǎn)化為圖 (, )G V E后，用以下算法來解決這一問題，主要是去除多余點(diǎn)集，并修補(bǔ)多余產(chǎn)生的缺口環(huán)，其中檢測(cè)橋與連通集算法使用文獻(xiàn)[8]中的圖的深度遍歷，而修補(bǔ)網(wǎng)格缺口的算法采用文獻(xiàn)[9]中的最小二乘網(wǎng)格修補(bǔ)算法，由于在切割過程中形成的多余缺口都非常小也沒有孤島現(xiàn)象，所構(gòu)造的矩陣也很小，因而計(jì)算也不復(fù)雜。

圖4 切口處的可能性

Step 7與切口環(huán)在M'中連通的環(huán)為多余的缺口環(huán)，因此修補(bǔ)之。

采用切口部分進(jìn)行預(yù)先判斷調(diào)整，避免了采用整個(gè)M'作為圖來處理的復(fù)雜性。通過以上處理，縮小了頂點(diǎn)集合V'的范圍，由此產(chǎn)生的新三維網(wǎng)格M' = ＜V',E',F'＞已具備了構(gòu)成定義 3中角色部件的網(wǎng)格拓?fù)錀l件，可以達(dá)到分割的要求了。

3.2 優(yōu)化目標(biāo)

為了滿足角色部件模型的重組連接，希望三維網(wǎng)格的缺口環(huán)比較規(guī)整圓滑，文獻(xiàn)[10]對(duì)網(wǎng)格分割結(jié)果提出了一種一般化的優(yōu)化方法，這種優(yōu)化方法在面片上產(chǎn)生新折線，但該方法的效果與網(wǎng)格密度有非常直接的關(guān)系。在本文處理對(duì)象網(wǎng)格較稀疏的情況下，可以根據(jù)該文獻(xiàn)提及的凹度最小原則，對(duì)3.1中產(chǎn)生的三維網(wǎng)格M'進(jìn)一步優(yōu)化。

圖5 凸起和凹陷

如圖5是經(jīng)過J1、J2規(guī)則處理后的犀牛右后腿相關(guān)聯(lián)的網(wǎng)格，可以發(fā)現(xiàn)明顯的凸起和凹陷破壞了邊緣平滑，對(duì)任意 3個(gè)連續(xù)的頂點(diǎn)(v1，v2，v3)考察其凹度，有以下3種情況需要調(diào)整：

1） 凹度>α度，v1v2v3形成邊緣三角形，則為凸起，去除v2點(diǎn)可改善；(α>180)

2） 凹度<β度，v1v2v3不是三角形，則為凹陷，連接v1v3可改善；(β<180)

3） 凹度>β度，v1v2v3不是三角形，則考察連接v1v3后的新三角面與鄰接面是否構(gòu)成凸起。

因此提出優(yōu)化規(guī)則J3為：缺口環(huán)上任意 3個(gè)連續(xù)的頂點(diǎn) (v1,v2,v3)，不存在邊e=v1v3使得缺口更平滑。將缺口環(huán)的頂點(diǎn)集合設(shè)置為Vjoint= (v1,v2…vn)，對(duì)相鄰三點(diǎn)vi vi+1vi+2(i=1…n-2)進(jìn)行判斷并區(qū)分上述情況進(jìn)行調(diào)整，由于去點(diǎn)或加邊會(huì)使Vjoint發(fā)生變化，可能會(huì)有新的凸起和凹陷，因此該過程應(yīng)該重復(fù)進(jìn)行，直到?jīng)]有調(diào)整情況發(fā)生。

上述調(diào)整規(guī)則中的α和β屬于經(jīng)驗(yàn)數(shù)據(jù)，在本文中經(jīng)過大量測(cè)試認(rèn)為α=240，β=150較好。

第3）種情況比較特別，因?yàn)樵趯?shí)際應(yīng)用過程中經(jīng)常出現(xiàn)切割到模型上局部凸起部位，融合后則應(yīng)封閉這個(gè)區(qū)間?？疾爝@部分因素，發(fā)現(xiàn)若連接v1v3后，新生成的三角面△v1v2v3與相鄰兩面的夾角較大，則認(rèn)為該切口處面片不平滑有突起，則在M'中產(chǎn)生新邊與三角形，使切口更緊密平滑；若夾角很小，一般認(rèn)為<30度，則認(rèn)為仍屬于面片平滑過渡，不處理之。

該優(yōu)化方法對(duì)平整有尖角凸起或凹陷的邊緣比較有效，而對(duì)于邊緣緩慢變化的趨勢(shì)無法抑制，處理后的網(wǎng)格缺口環(huán)并不能完全接近一個(gè)平面，對(duì)于分割后的兩個(gè)部件的融合提出了較高的要求，但平整尖角避免了重組時(shí)模型融合產(chǎn)生狹長(zhǎng)三角面片，而且該方法當(dāng)切割到模型上突起部位后會(huì)將之閉合，有利于后期的模型融合。

4 算法應(yīng)用實(shí)例

將本文算法應(yīng)用到幾十個(gè)數(shù)據(jù)完備的動(dòng)畫角色部件的選擇中，通過設(shè)計(jì)者指定關(guān)鍵骨骼，程序迅速找出其子骨骼并由蒙皮信息進(jìn)行預(yù)分割，進(jìn)而通過拓?fù)錂z查與優(yōu)化得到分割結(jié)果，所費(fèi)時(shí)間不超過0.1秒，如圖6展示的不同動(dòng)畫角色的分割效果。測(cè)試對(duì)象與經(jīng)過的規(guī)則如表1所示。

表1 測(cè)試對(duì)象與經(jīng)過的規(guī)則

圖6 動(dòng)畫角色切割結(jié)果

經(jīng)過實(shí)際應(yīng)用中的動(dòng)畫角色的測(cè)試，發(fā)現(xiàn)有70%到80%的部件選擇只經(jīng)過預(yù)分割就能很好的滿足角色部件拓?fù)涞囊?，尤其是骨骼分明的昆蟲和體型瘦弱的角色，而部件不分明的動(dòng)畫角色如體型肥大的角色在預(yù)分割后多數(shù)并不滿足拓?fù)湟?，需要進(jìn)一步處理，而對(duì)于切口處的優(yōu)化幾乎90%以上的部件都會(huì)發(fā)生，對(duì)于切口處范圍比較小的部件，通常在本文優(yōu)化方法下切口會(huì)繼續(xù)填補(bǔ)得更小，甚至通過優(yōu)化產(chǎn)生閉合，如螞蟻的腿、骨龍的翅膀。對(duì)于這種情況，可以設(shè)法動(dòng)態(tài)改變?chǔ)轮?；如果不可避免地被閉合，那么在使用該分割部件的時(shí)候需要注意，在本文相關(guān)項(xiàng)目所涉及的模型融合中，一般是以切口較大的模型作為融合參照，因此，無切口或者切口較小的網(wǎng)格部件在與相同模型融合時(shí)并無太大不同。

5 結(jié) 束 語

本文關(guān)注在影視動(dòng)畫與游戲行業(yè)中使用的動(dòng)畫角色的數(shù)據(jù)重用問題，針對(duì)三維網(wǎng)格分割這一計(jì)算機(jī)圖形學(xué)領(lǐng)域的經(jīng)典基礎(chǔ)問題，立足于動(dòng)畫角色較之三維模型更豐富的數(shù)據(jù)信息，提出了一種基于蒙皮約束的模型分割方法，根據(jù)蒙皮信息預(yù)分割后，再進(jìn)行拓?fù)渑袛嗯c切口優(yōu)化，產(chǎn)生符合模型重用要求的角色部件的三維網(wǎng)格。該方法已在與某游戲公司合作研發(fā)的動(dòng)畫角色部件組合系統(tǒng)中使用，其有效性和對(duì)動(dòng)畫角色的支持度得到了肯定，但同時(shí)，由于蒙皮制作的復(fù)雜，現(xiàn)代動(dòng)畫角色的三維網(wǎng)格頂點(diǎn)一般并不密集，而是通過各種紋理來表現(xiàn)其精細(xì)度，本文方法僅在該類對(duì)象上得到了充分驗(yàn)證，不能推廣到其它無蒙皮的三維網(wǎng)格模型，但拓?fù)錂z查的方法與切口優(yōu)化方案可以為其它網(wǎng)格分割算法所借鑒，其中，優(yōu)化方案部分值得進(jìn)一步研究和探討，對(duì)于后期的模型融合來說，切口優(yōu)化的最好效果為一標(biāo)準(zhǔn)圓環(huán)狀結(jié)構(gòu)。

[1]孫曉鵬, 李 華. 三維網(wǎng)格模型的分割及應(yīng)用技術(shù)綜述[J]. 計(jì)算機(jī)輔助設(shè)計(jì)與圖形學(xué)學(xué)報(bào), 2005, 17(8):1647-1655.

[2]Shamir A: A survey on mesh segmentation techniques [J].Computer Graphics Forum, 2008, 27(6): 1539-1556.

[3]Attene M, Kats S, Mortara M, et al. Mesh segmentation—— a comparative study [C]//Proceedings of the International Conference on Shape Modeling and Applications, Matsushima, Japan, 2006: 14-25.

[4]Funkhouser T, Kazhdan M, Shilane P, et al. Modelling by example [J]. ACM Transactions on Graphics, 2004,23(3): 652-663.

[5]Li X, Toon T, Tan T, et al. Decomposing polygon meshes for interactive applications[C]//Proceedings of the 2001 symposium on Interactive 3D Graphics(2001),2001: 35-42.

[6]Leet Y, Lin P H, Yans U, et al. Mesh decomposition using motion information from animation [C]//Proceedings of Computer Animation and Virtual Worlds (2005), 2005: 519-529.

[7]Autodesk, Inc. 3ds Max 8 Documentation [EB/OL].http://usa.autodesk.com/adsk/servlet/item?siteID=123112&id=9861621, 2010-3-31.

[8][美]Thomas H C 等. 算法導(dǎo)論[M]. 潘金貴, 等譯.北京: 機(jī)械工業(yè)出版社, 2006: 322-340.

[9]周明東, 林俊聰, 金小剛. 最小二乘網(wǎng)格的模型修補(bǔ)[J]. 工程圖學(xué)學(xué)報(bào), 2009, (5): 13-21.

[10]Lotan K, Ayellet T. Mesh Segmentation Refinement Pacific [J]. Graphics, 2009, 28(7): 1995-2003.