一種基于三角剖分的產(chǎn)品造型混合方法

沙春發(fā)， 盧章平， 楊華春， 郭健宏

（江蘇大學(xué)圖形技術(shù)研究所，江蘇 鎮(zhèn)江 212013）

一種基于三角剖分的產(chǎn)品造型混合方法

沙春發(fā)， 盧章平， 楊華春， 郭健宏

（江蘇大學(xué)圖形技術(shù)研究所，江蘇 鎮(zhèn)江 212013）

提出一種為激發(fā)產(chǎn)品造型設(shè)計創(chuàng)意提供服務(wù)的形狀混合方法。首先，將初始模型、目標模型映射到單位球上；其次，提取目標模型的邊界特征；然后，根據(jù)提出的“三角剖分規(guī)則一”、“三角剖分規(guī)則二”求取中間模型的拓撲模型，從而建立中間模型與初始模型、目標模型的頂點及造型特征間的映射關(guān)系；最后，通過線性插值得到一系列造型各異的中間新造型。該方法無需合并給定模型的全部拓撲結(jié)構(gòu)，計算量少，生成的新模型數(shù)據(jù)量少；無需人工干涉，適合不具備形狀混合技術(shù)相關(guān)專業(yè)知識的工業(yè)設(shè)計師操作使用，生成的新模型能有效保留給定模型的視覺特征，可為產(chǎn)品造型的概念設(shè)計提供參考。

三維形狀混合；三角剖分規(guī)則；三角網(wǎng)格模型；產(chǎn)品造型設(shè)計

能融合給定產(chǎn)品模型的造型特征是三維形狀混合技術(shù)的重要特點。該過程可生成數(shù)量眾多的中間物體，這些新物體造型新穎，同時又保留了初始物體及目標物體上的視覺特征，可作為產(chǎn)品造型設(shè)計師的設(shè)計參考，激發(fā)設(shè)計靈感，提高設(shè)計效率。因此，該技術(shù)不僅在影視動畫、廣告?zhèn)髅降刃袠I(yè)得到應(yīng)用，在產(chǎn)品造型設(shè)計領(lǐng)域也得到了極大的關(guān)注。袁浩等[1]通過匹配產(chǎn)品局部特征線間的控制點實現(xiàn)形狀混合；李明珠[2]通過混合產(chǎn)品點云切片的方式實現(xiàn)了產(chǎn)品創(chuàng)新；Sanchez等[3]、Yang和Jüttler[4]及程豐備[5]提出了面向造型設(shè)計的自由曲面混合方法，這些方法需要適當?shù)娜藱C交互。蘇建寧等[6]將經(jīng)過三角化分的產(chǎn)品形態(tài)球面化，從而求取中間物體的拓撲結(jié)構(gòu)以實現(xiàn)產(chǎn)品造型混合。作者們在研究中，應(yīng)用各自的方法實現(xiàn)了產(chǎn)品造型創(chuàng)新。

除了點云、自由曲面等形式，三角網(wǎng)格模型是表達三維模型的重要方式。其在設(shè)計、制造、娛樂等行業(yè)的應(yīng)用十分廣泛，因此，不少專家學(xué)者開展了關(guān)于混合三角網(wǎng)格模型的研究工作。Alexa[7]和Kent等[8]提出了一種相似的混合方法，他們將原物體映射到單位球上然后合并拓撲結(jié)構(gòu)以獲得頂點間的映射關(guān)系。Alexa[7]的方法需要用戶指定特征點，以便在處理過程中對齊特征，能適應(yīng)任意非零虧格網(wǎng)格模型間的混合。Lee和Huang[9]、Gregory等[10]及王章野等[11]提出了相似的算法思路：通過交互的方法將原物體剖分為多個面片，并將面片映射到合適的多邊形上，再通過映射合并拓撲結(jié)構(gòu)以獲得頂點間匹配關(guān)系，最終獲得中間模型。通過這些方法混合得到的中間物體精度高，且可通過人工干預(yù)控制形狀混合的結(jié)果。

不同于影視動畫等行業(yè)，產(chǎn)品造型設(shè)計對該技術(shù)的要求有以下特征：首先，混合結(jié)果應(yīng)恰當保留原模型上的視覺特征，但是對混合精度要求不高，能滿足視覺效果即可；其次，在操作上無需復(fù)雜的人機交互，不要求用戶具備專業(yè)的形狀混合知識；再次，混合計算所需時間應(yīng)在設(shè)計師的忍耐范圍之內(nèi)；最后，生成的中間物體體量適中，便于后期修改、渲染等處理。因此，面向產(chǎn)品造型設(shè)計的需求，本文提出了一種基于三角剖分的三維模型混合方法。

1 方法描述

1.1 方法原理

對于三角網(wǎng)格模型，形狀混合的本質(zhì)就是初始模型與目標模型之間對應(yīng)的頂點及位置隨參數(shù)變化相互靠攏的過程。這個過程有2個步驟：①求取中間模型的拓撲模型，并記錄其與初始模型和目標模型的映射關(guān)系；②通過插值相互映射的空間坐標求取新物體?？捎檬?1)描述該過程。

式(1)中，S、T為給定的初始模型和目標模型，M為混合得到的新物體，為新物體的拓撲模型；f(t)和g(t)是隨參數(shù)t變化的控制函數(shù)，分別控制M體現(xiàn)S、T造型特征程度的權(quán)重，f(t)值越大，則M上初始模型造型特征越明顯，反之亦然；符號?描述了各頂點對應(yīng)在S、T上的具體位置；符號°是求M上頂點坐標的插值方法。

1.2 方法的關(guān)鍵步驟

基于上述原理，簡述基于三角剖分的三維模型混合方法，其主要步驟如下：

(1) 將S、T映射到單位球上，分別得到S′、T′。映射過程需保持原模型上各頂點間的空間相對位置關(guān)系不變，且要求S′、T′上的三角面片沒有折疊。

(2) 在單位球空間中，將T′頂點映射到S′上，并按照設(shè)定的三角剖分規(guī)則一剖分 S'上相關(guān)的三角面片，得到初始的中間模型的拓撲模型 M′。映射過程中求取并記錄M′與S、T上頂點的對應(yīng)關(guān)系，求取并記錄M′上的頂點對應(yīng)在S、T的位置坐標。

(3) 求取目標模型T的特征邊，并按照其次序標記在T′中的對應(yīng)邊為E′。

(4) 按照次序?qū)′映射到M′，按照設(shè)定的三角剖分規(guī)則二求取新點并剖分相應(yīng)的三角面片，得到最終的拓撲模型。同樣，映射過程中需求取并記錄新點在 S、T上的對應(yīng)位置。此時，與 S、T的映射關(guān)系即可確定。

(5) 按照混合算法，設(shè)置M具備給定模型造型特征的權(quán)重，利用式(1)求取 M各頂點坐標，可得到一系列中間物體。

該方法通過剖分S′上三角面片，使S上造型特征得以保留；通過插入 T′上頂點以及特征邊到 S′中，保留T上造型特征。

1.2.1 模型球面化

Kent等[8]首先將零虧格的三維模型投影到單位球上，然后計算頂點間空間位置關(guān)系，最后通過插值實現(xiàn)三維物體的形狀混合。Shapiro和 Ayellet[12]按一定次序?qū)⒛Ｐ晚旤c逐步刪除簡化為凸四面體，然后按照逆向順序?qū)⑾鄳?yīng)頂點添加回模型得到零虧格的凸多面體模型，再采用Kent等[8]的方法混合模型。Alexa[7]使用松弛迭代的方法處理單位球面映射。周昆等[13]詳述了一種累進式的映射算法。姚建強和何援軍[14]提出了使用切割線分解封閉網(wǎng)格，并按照分割邊界將子網(wǎng)格映射到球面的方法。

為降低操作難度，提高該技術(shù)的可用性，本文舍棄了需要人工干涉的球面映射方法，按照下列步驟將模型球面化。

首先，將模型以中心投影的方法投影至單位球上。用k表示該模型，設(shè)其中心點為o、模型頂點為v，球面化后的模型為k′。使中心點o與單位球球心重合，單位化向量ov 即可獲得映射結(jié)果那么，單位化后頂點v′之間的連線可構(gòu)成k′上三角面片，初步完成球面化。

其中，i*是點′的鄰域，d為′的度。式(2)表示：如果某個局部有折疊現(xiàn)象存在，則將該局部所有點的坐標替換為其鄰域的坐標均值。坐標替代時，應(yīng)始終保持頂點在單位球上。

當折疊處理完畢或式(3)得到滿足時，迭代停止。式(3)表示：如果一次完整的迭代中，頂點的新坐標與原坐標的距離足夠小，此時迭代收斂慢，繼續(xù)迭代意義不大，則終止迭代。每次迭代都檢測式(3)的達成情況會消耗大量時間，可間隔一定次數(shù)的迭代再進行檢測；也可迭代一定次數(shù)后即停止，經(jīng)過實例測試，可將其設(shè)為300次。

1.2.2 求解映射

圖1 頂點的位置關(guān)系

計算式(4)：

如果式(5)成立，那么頂點 vT′i與三角面 FS′j才是相關(guān)的，否則彼此不存在映射關(guān)系。

解方程組式(6)可得k1、k2、k3。此時，易求得對應(yīng)在FSi上的坐標值。

(2) 如果 α 、 β 、λ中有兩個值為0，則p與三角面 FS′i某一頂點重合：

(3) 如果 α 、 β 、λ中僅有一個值為0，則p落在′的一個邊上。假設(shè)β為 0，由圖 1(b)可知：p在、的連線上，點p位于射線ovTi上，可得到式(7)：

解方程得k1、k2，也可求對應(yīng)在FSi上的位置。同樣可求解其他情況。

1.2.3 三角剖分規(guī)則一

按照“三角剖分規(guī)則一”，依次將T′上頂點插入到S′中以得到中間模型的初始拓撲模型M′。根據(jù)上文所述，頂點的映射位置有下列3種可能：

(1) 映射位置位于某一個三角面片內(nèi)部時，則將相應(yīng)的三角面Δv1v2v3剖分為3個部分Δv1v2vp、Δv2v3vp、Δv3v1vp，如圖2所示。

圖2 映射位置位于三角面內(nèi)部

(2) 映射落在某一個邊上（圖3）。此時，模型上有兩個相鄰的三角面片與該映射相關(guān)。那么，剖分三角面片 Δv1v2v3為 Δv1vpv3、Δv2vpv1；剖分三角面片Δv3v2v4為Δv4v3vp、Δv2v4vp。

圖3 映射落在一個邊上

(3) 映射位置與某頂點重合時，不做任何三角剖分。

1.2.4 三角剖分規(guī)則二

中間模型的初始拓撲模型M′是由 T′的頂點插入到S′得到的，能確保S上的視覺特征得到保留，但是T上有部分特征丟失。因此，需要提取T模型的造型特征并將之插入到 M′中。陳杰[15]在文中提到尖銳區(qū)域邊界特征是產(chǎn)品造型視覺特征的重要表現(xiàn)形式，并把該類特征的提取方法歸為3類：頂點曲率法、二面角法和法矢夾角法。二面角法經(jīng)過不斷的改進與發(fā)展，具備了結(jié)構(gòu)簡單、計算迅速的特點[16-19]。

本文采用了劉勝蘭等[19]闡述的方法提取三角網(wǎng)格模型 T的特征邊，然后將其在 T′中的相應(yīng)邊E′依次插入到 M′中，以獲得最終拓撲模型。插入過程中按照“三角剖分規(guī)則二”求取新頂點并剖分相關(guān)三角面，具體內(nèi)容如下。

(1) 由 1.2.2節(jié)可知，一個特征邊落在三角面上的情況有 3種可能：邊在一個三角面內(nèi)部；邊的一個端點映射于三角面片內(nèi)部，另一個端點落在其邊上或與其某端點重合；邊的端點都在三角面的邊上或者與其端點重合，分別如圖4(a)、(b)、(c)所示。

圖4 特征邊落在三角面上的情況

這3種情況下，特征邊與三角面的邊界不相交，因此并不產(chǎn)生新的頂點。經(jīng)過“三角剖分規(guī)則一”的處理，相應(yīng)三角面片已經(jīng)得到剖分，視覺特征已經(jīng)得到保留。

(2) 當且僅當特征邊的兩個端點分別位于三角面內(nèi)部及外部時，需要計算新點，并求取其在給定模型中的對應(yīng)位置，同時剖分相應(yīng)的三角面。

① 計算新點。

如圖5所示，設(shè)特征邊vE1vE2與Δv1v3v2的邊v2v3穿越交叉，則新點p在Δov3v2與ΔovE2vE1交線的延長線上，且線op分別與邊vE1vE2、邊v2v3相交，可列方程組式(8)。

圖5 新點位置

解方程可得k1、k2，如果k1、k2使式(9)成立，那么點p即為新點（如果k1、k2值為1或者0，那么新點剛好與三角面相應(yīng)頂點重合），否則求該特征邊與三角面其他兩個邊的相交情況，直至確定新點p。由k1、k2可求p對應(yīng)在S、T上的位置坐標。

② 依據(jù)“三角剖分規(guī)則二”插入新點。

由算法步驟可知，需在“三角剖分規(guī)則一”已經(jīng)被執(zhí)行的基礎(chǔ)上執(zhí)行“三角剖分規(guī)則二”。

首先，按照次序遍歷特征邊，將第一個產(chǎn)生新點的特征邊作為起始邊。設(shè)v′T1v′T2為起始邊，計算可得新點 vN1，如果新點在邊上，則按照“三角剖分規(guī)則一”剖分相應(yīng)三角面；如果新點與三角面的某端點重合，不做三角剖分，如圖6所示。

圖6 三角剖分規(guī)則

完成一個完整特征邊的插入后，將下一條滿足條件的特征邊作為起始邊繼續(xù)插入。按照此方法，全部特征邊可插入到模型M′，從而得到。

1.2.5 插值計算

2 實驗及分析

驗證平臺為手提筆記本電腦，其操作系統(tǒng)為Windows XP，CPU為雙核Celeron 2.0 GHz，內(nèi)存為2 GB。原型系統(tǒng)開發(fā)平臺為Visual C++6.0，采用OpenGL圖形函數(shù)庫，結(jié)合MFC對該方法進行驗證。

圖 7和圖 8給出了幾組模型間混合的結(jié)果，表1分別給出了相關(guān)數(shù)據(jù)。

圖7 分別從3個視角展示了方體和柱體的混合結(jié)果(M由左至右對應(yīng)的t值分別為0.2，0.4，0.6，0.8)

圖8 馬頭和水滴、自由形和汽車兩對模型間形狀混合的結(jié)果(M由左至右對應(yīng)的t值分別為0.2，0.4，0.6，0.8)

(1) 形狀混合結(jié)果。從圖7和圖8可看出形狀混合結(jié)果良好，得到的新物體較好地融合了初始模型和目標模型的視覺特征；混合過程中丟失的視覺特征較少，對模型的視覺效果影響不大；混合可連續(xù)生成中間物體，中間物體造型新穎。

表1 實驗的相關(guān)數(shù)據(jù)

(2) 中間模型的體量。本方法無需合并S、T的所有拓撲結(jié)構(gòu)，中間模型三角面片數(shù)量適中，沒有成倍數(shù)增長，適合工業(yè)設(shè)計師后期處理與操作。

(3) 算法耗時。一方面，算法無需合并S、T的全部拓撲結(jié)構(gòu)，減少了計算的工作量；另一方面，無需人工干涉，節(jié)省了以小時為單位的人機交互時間，所需時間合理。

(4) 算法操作。算法無需復(fù)雜的人工干涉，不要求使用者具備專門的形狀混合技術(shù)知識，操作簡單，易于掌握。

3 結(jié) 束 語

本文提出的三維網(wǎng)格模型混合方法基于兩種三角剖分的規(guī)則，生成的中間物體在精度上較其他方法差，但對視覺效果沒有影響，基本能滿足產(chǎn)品造型設(shè)計師的使用要求，且具備操作簡單、耗時少的特點。該方法生成的系列中間物體造型新穎又能有效保留給定模型的視覺特征，對產(chǎn)品造型創(chuàng)新及激發(fā)設(shè)計師設(shè)計靈感有積極作用。目前，該方法比較適合為產(chǎn)品概念創(chuàng)新提供形態(tài)參考，但還不能處理復(fù)雜產(chǎn)品模型，比如具有分型、孔洞的模型，也不能處理特別細長的模型。為了進一步推廣該技術(shù)的使用，這方面的工作還需深入。

[1] 袁 浩, 薛澄歧, 盧章平, 等. 基于局部形態(tài)融合的產(chǎn)品創(chuàng)新設(shè)計研究[J]. 包裝工程, 2011, 32(20): 30-33.

[2] 李明珠. 形狀混合的理論與應(yīng)用研究[D]. 鎮(zhèn)江: 江蘇大學(xué), 2007.

[3] Sanchez M, Fryazinov O, Vilbrandt T, et al. Morphological shape generation through user-controlled group metamorphosis [J]. Computers & Graphics, 2013, 37(6): 620-627.

[4] Yang Huaiping, Jüttler B. 3D shape metamorphosis based on T-spline level sets [J]. The Visual Computer, 2007, 23(12): 1015-1025.

[5] 程豐備. 一類曲面幾何變形方法及其在產(chǎn)品設(shè)計中的應(yīng)用[D]. 杭州: 浙江大學(xué), 2014.

[6] 蘇建寧, 吳江華, 劉 蕓, 等. 基于球面調(diào)和映射的三維產(chǎn)品形態(tài)融合方法研究[J]. 圖學(xué)學(xué)報, 2014, 35(3): 417-422.

[7] Alexa M. Merging polyhedral shapes with scattered features [J]. The Visual Computer, 2000, 16(1): 26-37.

[8] Kent J R, Carlson W E, Parent R E. Shape transformation for polyhedral objects [J]. Computer Graphics (ACM), 1992, 26(2): 47-54.

[9] Lee T Y, Huang P H. Fast and intuitive metamorphosis of 3D polyhedral models using SMCC mesh merging scheme [J]. IEEE Transactions on Visualization & Computer Graphics, 2003, 9(1): 85-98.

[10] Gregory A, State A, Lin M C, et al. Interactive surface decomposition for polyhedral morphing [J]. The Visual Computer, 1999, 15(9): 453-470.

[11] 王章野, 鮑虎軍, 彭群生. 交互三維形狀過渡技術(shù)[J].軟件學(xué)報, 1998, 9(9): 665-670.

[12] Shapiro A, Ayellet T. Polyhedron realization for shape transformation [J]. The Visual Computer, 1998, 14(8-9): 429-444.

[13] 周 昆, 鮑虎軍, 石教英. 統(tǒng)一的數(shù)字幾何處理框架[J].計算機學(xué)報, 2002, 25(9): 904-909.

[14] 姚建強, 何援軍. 三角網(wǎng)格曲面的球面參數(shù)化[J]. 工程圖學(xué)學(xué)報, 2010, 31(4): 77-80.

[15] 陳 杰. 反求工程中基于混合過渡特征的三角網(wǎng)格模型數(shù)據(jù)處理技術(shù)研究[D]. 福州: 福州大學(xué), 2011.

[16] Sunil V B, Pande S. Automatic recognition of features from freeform surface CAD models [J]. Computer-Aided Design, 2008, 40(4): 502-517.

[17] Yang Shengyuan, Shu Shi. Robust feature extraction for the composite surface mesh from STL file [C]//The 9thInternational Conference for Young Computer Scientists. Hunan, China, 2008: 1373-1378.

[18] Peng Y H, Gao C H. A novel boundary extraction algorithm on triangular meshes of STL model [J]. Advanced Materials Research, 2010, 97-101: 2929-2934.

[19] 劉勝蘭, 周儒榮, 張麗艷. 三角網(wǎng)格模型的特征線提取[J]. 計算機輔助設(shè)計與圖形學(xué)學(xué)報, 2003, 15(4): 444-453.

A Metamorphosis Method Based on Triangular Decomposition for Product Shape Design

Sha Chunfa, Lu Zhangping, Yang Huachun, Guo Jianhong
(Graphic Technology Institute, Jiangsu University, Zhenjiang Jiangsu 212013, China)

This paper presented a metamorphosis method based on triangular decomposition for product shape design. Firstly, two given triangular mesh models were projected on to the surface of a unit sphere. Secondly, the edge characteristics were calculated. Then the topological model of new models was got based on the two kinds of triangular decomposition rulers proposed in this paper. So, the spatial relationships of vertexes and shape features between the middle model and two given models could be built. Lastly, the new models were made with linear interpolation. Testes indicated that the proposed approach needed no topological merging and artificial interference and could preserve the visual features of the given models effectively. It was shown that these characters were suitable for industrial designers who had no special knowledge about the metamorphosis technologies to create new shapes for product form design.

3D metamorphosis; triangular decomposition rulers; triangular mesh model; product shape design

TB 472

A

2095-302X(2015)05-0734-06

2015-05-18；定稿日期：2015-06-10

高等學(xué)校博士學(xué)科點專項科研基金資助項目(20113227110007)；江蘇省普通高校研究生科研創(chuàng)新計劃資助項目(CXLX11_0566)；江蘇大學(xué)“842T工程”項目

沙春發(fā)(1982-)，男，江蘇淮安人，博士研究生。主要研究方向為計算機輔助工業(yè)設(shè)計。E-mail：shachunfa@ujs.edu.cn

盧章平(1958-)，男，江蘇揚州人，教授，博士。主要研究方向為計算機圖形理論及應(yīng)用等。E-mail：lzping@ujs.edu.cn