基于彈簧－質點模型的三角網格曲面展開算法及其應用

韓林，劉斌

（華僑大學 機電及自動化學院，福建 泉州 362021）

基于彈簧－質點模型的三角網格曲面展開算法及其應用

韓林，劉斌

（華僑大學 機電及自動化學院，福建 泉州 362021）

提出一種自調整初始展開方法，對基于彈簧－質點模型的展開優化算法進行改進，保證其初始展開平面的拓撲完整性 .同時，為了防止模型迭代發散，采用對能量釋放前后誤差進行判斷的方法，有效地遏制算法的發散.最后，將算法應用于制造領域，試驗結果表明算法可取得較高質量的展開平面.

彈簧－質點模型；自調整；初始展開；三角網格

在產品設計和制造領域中，許多產品的外形為數學意義上的不可展曲面（高斯曲率K≠0），例如船舶、汽車、飛機的外殼，鞋幫面和服裝等，但為了設計和制造產品，通常需要得到具有復雜三維曲面產品的二維展平外形圖.在計算機圖形（computer graphics，CG）領域中，由于曲面本身的復雜性，對曲面的某些操作需要借助曲面的二維展開結果來實現，如曲面參數化、紋理映射等.因此，對三維曲面的二維展開研究，具有重要的理論意義和工程應用價值.自20世紀80年代以來，曲面展開一直是CAD＆CG領域研究的熱點，國內外眾多學者針對不同應用領域，采用不同的展開方法進行了一系列的研究.在眾多展開方法中，幾何展平法以其變形小、計算高效（無需求解大量線性方程組）等優點，受到產品設計領域研究人員的青睞.Sorkine等［1］給出了由種子三角形開始，逐個展開曲面上三角形的方法；王昌凌等［2］給出了類似的方法；陳功等［3］也采用類似方法并進行改進 .針對能量釋放中的時間步長，嚴國彪等［4］提出了一種調整式.上述方法雖然解決了大部分曲面展開問題，但是對表面曲率變化較大的復雜曲面進行試驗時，仍存在一些問題，如初始幾何展開時，由于大量三角片的約束展開，出現構不成三角網格的情況；對初始展開平面利用彈簧－質點模型進行力學修正時，出現震蕩發散現象，等等.基于此，本文提出一種自調整初始展開方法，使算法更加健壯有效，并在進行能量釋放時，運用誤差對比，遏制算法的發散.

1 曲面展開的彈簧-質點模型

1.1 建立模型

非可展曲面到平面的近似展開可歸納為一個無約束的極值問題［5］.其基本思想是保持展開前后曲面上所有網格點之間距離變化最小，即將已知的曲面劃分成網格，將三維的網格點映射到二維平面上，實現近似展開.在初始幾何展開的基礎上建立彈簧－質點模型，進行能量釋放，該過程符合并展現了極值展開的這一基本思想.

三維網格曲面初始展開后，得到二維的三角網格平面，據此可以建立彈簧－質點模型，將網格上的點作為質點，邊作為彈簧 .圖1為P0與其一環鄰域的原始相對位置及變形后的受力情形 .圖1中：P0為質點，質點P0和其他點之間的連接邊視為彈簧.由于不可展曲面的初始展開存在變形，初始展開后P0與其一環鄰域的相對位置如圖1（b）所示，那么與P0相連的邊，由于變形（被壓縮或拉伸）而存儲能量.

在曲面展開成平面的過程中，如果平面網格中的邊比對應的空間網格邊長，則對質點產生拉力（圖1（b）中P1，P2，P5，P6對P0產生拉力）；反之，則施以推力（圖1（b）中P3，P4對P0產生推力）.質點P0在彈簧力的作用下向所受力的合力方向移動，最終會達到一個穩定的最優狀態.

在彈簧－質點模型中，系統的物理量與幾何量相對應，如力、彈性變形能及質量、面密度是由網格節點間的距離和三角片的面積確定的.由于能量是狀態的單值函數，與過程無關，所以能量的關系式比較容易列出.定義質點Pi的彈性變形能與彈性力為

圖1 質點P0的受力情況Fig.1 Stress in the particle P0

式（1）中：C為彈簧彈性變形系數；｜PiPj｜為曲面展開后的平面上Pi到Pj的距離；dj為空間曲面上的Pi到Pj的距離；nPiPj是從Pi指向Pj的單位矢量；n為質點Pi相鄰的質點數.

在曲面展開過程中，質點的運動可以用拉格朗日方程來描述，即

式（2）中：M，D和K分別為系統的質量矩陣、阻尼矩陣和剛度矩陣；gq為局部自由度與全局自由度之差引起的系統內力；fq為系統外力.

在彈簧－質系統中，質點運動中的時間間隔Δt很小，質點Pi的加速度可被認為是常量，則整個系統中的各個質點處于平衡 .利用歐拉法求解拉格朗日方程，可得到

式（3）中：mi是節點Pi的質量；ζ是曲面的面密度；fi（t）是作用在節點Pi上的彈性力；Ak是包含節點Pi的所有三角形中第k 個三角形的面積；¨q（t）是節點Pi的加速度；˙q（t）是節點Pi的速度；qi（t）是節點Pi在時間t的位置.這里，面密度ζ并非真正意義上的曲面面密度，在多數基于物理的模型中，ζ和C 只是使變形更為有效的參數［6］.

1.2 算法中的誤差及評判準則

一般采用面積誤差、邊長誤差和角度誤差作為展開精度的評定標準.本文的誤差計算方法主要為面積誤差和邊長誤差，計算式如下

式（4）中：ES，EC分別為相對面積誤差和相對邊長誤差；A，A′分別是曲面片展開前的實際面積和展開后所對應的面積；L，L′分別為曲面展開前網格的邊長實際長度和展開后網格的邊長所對應的長度.

2 網格曲面展開算法及其改進

2.1 曲面網格的初始展開

利用三角形法對曲面三角網格進行初始展開 .首先，從網格曲面上選取第1個三角片，該三角片稱為基三角片，將其不變形地展開到平面上；其次，以展開的三角片為基礎，將其相鄰的三角片依次展開，直到全部展開到平面上.此展開過程中，三角片展開分為約束三角片展開和無約束三角片展開.

大量實驗表明，基三角片的位置選取對初始展開的質量具有重要影響［7］，文中采用文獻［3］中所述方法，將基三角片選在網格中心.

2.1.1 無約束三角片展開 圖2為無約束三角片展開.假定在網格曲面上，T是與T1相鄰的三角片，Q1Q2是它們的公共邊.設三角片T1已經展開到二維平面上，而三角片T還未展開，即T的兩個點Q1和Q2的位置已經在二維平面確定（即2（b）中的P1和P2）.此時，三角片T上的第3點Q3可以由兩個圓的交點來確定，這兩圓分別以P1和P2為圓心，以r1，3和r2，3為半徑.r1，3和r2，3分別是三維網格中Q1Q3和Q2Q3的歐氏距離.

圖2（b）中的陰影三角片表示已經展開.當曲面是可展曲面時，三角片T在二維平面所確定的P3的位置，與其他包含點P3的三角片在二維平面所確定的位置一致，即不發生變形扭曲；當曲面是不可展曲面時，點位置有可能不一致，這時候就會有層疊和裂縫的現象產生 .因此，為保證拓撲完整，須采用約束三角片展開.

2.1.2 約束三角片展開 圖3為約束三角片展開 .在圖3（a）中，三角片T與己經展平的三角片T1和T2都有共邊時，由T2決定的Q3在二維平面上的位置為P′3，如圖3（b）所示（陰影部分表示已經展開的三角片）.如果采用無約束的三角片展開方法，那么由三角片T產生的兩圓的交點將為另一位置P″3，此時，可用一個平均位置來初步解決這種矛盾，從而產生Q3在平面上的唯一位置.此方法可以保證三維曲面上的點到二維平面上點的一一對應，但是會導致三角片的扭曲變形而產生誤差.

圖2 無約束三角片展開Fig.2 Unconstrained triangle flattening

圖3 約束三角片展開Fig.3 Constrained triangle flattening

2.1.3 自調整方法 由于約束三角片展開方法的大量使用，可能會出現從空間三角片取出的對應兩邊邊長與已經展開的當前邊的長度構不成三角形的情形.因此，針對此類情況，需要進行自調整，以保證拓撲完整.由約束三角片展開逐漸積累的誤差，往往會導致展開的中斷.誤差中斷的原因是｜P1P2｜＞r1＋r2或者｜P1P2｜＜｜r1－r2｜.此時3個長度不能構成三角形，也就無法通過交點計算出第3點的位置 .為了得到第3點，提出了一種簡單有效的自調整方法，如圖4所示.

圖4 自調整展開Fig.4 Self－adjustment flattening

設Q1和Q2為空間曲面網格上同一個三角片上的兩點，P1和P2分別為Q1和Q2在二維展開平面上的對應點，點Q3是該三角片的第3點，r1和r2分別為Q1和Q2到Q3的歐氏距離，如圖4（d）所示.由于誤差的積累，展平到平面上的P1P2已經嚴重變形，如果仍然以r1和r2做為半徑，利用圓弧求交尋找第3點，則必然導致失敗，因為不滿足構成三角的條件；如果試圖改變P1P2的長度，就會影響到其他已經展開的三角片，從而引入更多誤差，得不償失.在保證點P1和P2位置不變的前提下，提出一種自動調整第3點P3的方法并提出調整因子、虛擬邊長等概念 .調整計算式為

式（5），（6）中：l稱為調整因子；r＇i為虛擬邊長（圖1（d）中的虛線）.

根據三角形相似的原理，通過調整后構成的三角形與原三角形相似，必然可以構成三角形 .此時，以Pi為圓心，以r＇1為半徑，就可確定第3點的位置，圖4（e）是用上述方法處理的結果.當｜P1P2｜＞r1＋r2時，l∈（1，＋∞）；當｜P1P2｜＜｜r1－r2｜時，l∈（0，1）.由于自調整方法所使用的量都可以在計算三角片的第3點時得到，因此，不增加算法的時間復雜度.經自調整之后雖然可以獲得第3點的位置，但是引起了三角片一定比例變形，這些變形將產生彈性能量，對此可以建立彈簧－質點模型，進行能量的釋放.

2.2 彈簧-質點模型的能量釋放

曲面上所有網格化三角形是根據上述方法展開為平面三角形后，得到曲面的初始展開平面網格.由式（1）～（3），即可根據各質點當前時刻的速度、位置、受力等迭代計算出下一時刻的各質點的加速度、速度、位置等信息，而循環終止的條件則是達到曲面展開的誤差閾值或者迭代次數達到了系統設定的最大值.用式（1）計算三角網格上的每個點的能量，通過釋放能量來改善展開的平面.如果整張展開網格曲面m個離散點，則所有離散點的展開變形能為

該值的大小反映曲面整體展開變形程度.為了減小展開的變形，需要能最大程度地減小變形能，進行變形能的釋放.大部分情況下，算法是收斂的，但是，當三角網格劃分的質量不佳時，容易造成算法的發散.

針對發散問題，采用了一種遏制發散的方法.該方法通過每次能量釋放后，計算相對誤差（相對面積誤差和相對邊長誤差），記錄當前誤差值（ES＋EC），并和前一次的誤差值（ES＋EC）＇進行比較，如果（ES＋EC）＜（ES＋EC）＇，表明變形能正在釋放，算法目前是收斂的；如果（ES＋EC）＞（ES＋ES）＇，并且記錄次數n.當大于設定的次數時，表明正在發散，結束能量釋放.

2.3 曲面展開的算法流程

曲面展開的算法流程圖，如圖5所示.算法有如下7個主要步驟.

（1）建立3個集合V，A和F.V為包含所有尚未展開的曲面三角形的集合；A為有序活動集合，即從集合V中挑選出來的三角形集合，這些三角形是與已展開三角形共邊而將要被展開的三角形；F為所有已展開到二維平面的三角形集合.對這3個集合進行初始化，把所有要展開的空間三角形添加到集合V中，置集合A和F為空.

（2）從V 集中選擇展開基三角形T0.一般在曲面的對稱中心或曲率較大的部位選擇該三角面片；然后，將該三角面片無約束展開在平面上任意位置，并將該基三角形從V 中刪除，直接加入到F中.

圖5 曲面展開的算法流程圖Fig.5 Algorithm flowchart of surface flattening

（3）在V集中尋找與基本三角形T0共邊的所有三角形｛Ti｝，將這些三角形加入到A集中，并從V中減去這些三角形.

（4）判斷A集是否為空.如果不為空，則從A集中取出下一個三角形Tj，并按步驟（5）或步驟（6）的方法展開；如果A集為空則判斷V 集是否為空，如果V 集為空則轉到步驟（7）執行，否則轉到步驟（3）執行.

（5）如果計算的第3點可以構成三角形 （其余兩點已在展開集F的某個三角形中），此時采用普通展開方法，并將三角形Ti加入到展開集F 中，從A中減去Ti，轉到步驟（4）.

（6）如果計算的第3點不能構成三角形，則采用自調整展開方法，調整后將三角形Ti加入到展開集F 中，從A中減去，然后轉到步驟（4）.

（7）進行能量的釋放，并計算面積誤差ES，邊長誤差EC和所有離散點的展開變形能E（φ）.令當前的誤差值和前一次的誤差值比較，判斷是否發散，同時判斷它們的值是否是在閥值內，若誤差都小于閥值或者迭代發散，則結束；若大于閥值且不發散，則回到步驟（3）重新進行能量釋放，直到超過迭代次數N為止.

3 曲面展開的應用

在皮鞋生產過程中，為了確定縫制三維鞋幫曲面所需的二維材料的輪廓，包括直接從鞋楦設計中取得的曲面還原成符合質量要求，可以直接投入批量生產的二維鞋樣，都需要用到曲面展開的方法.將上述三維曲面的展平算法應用于楦面展平中，結果如圖6所示.該曲面的頂點數是1 139個，三角片個數是2 129，采取改進算法后，其面積誤差為0.041 4，邊長誤差為0.006 3，基本符合精度要求.

圖6 曲面展開技術應用于鞋幫設計Fig.6 Application of surface flattening technology in shoe pattern design

在板料成形中，預估坯料是縮短設計與生產周期的關鍵步驟之一.因此，將曲面展開算法應用于板料拉延成形中的坯料預估，如圖7所示.該曲面頂點數是757個，三角片個數是1 146，采取改進算法后，其面積誤差為0.056 2，邊長誤差為0.040 7，平均相對誤差為0.048.用商業軟件DYNAFORM對該模型進行模擬展開，相對誤差是0.034 0.表明，改進算法基本實現了板料成型毛坯料的快速估計.

圖7 曲面展開技術應用于坯料預估Fig.7 Application of surface flattening technology in prediction of the blank shape

4 結束語

針對幾何展開／力學修正的曲面展開算法中存在的不足，提出一種新的改進算法，并將算法應用于某些制造領域 .試驗結果表明，算法可取得較高質量的展開平面.該算法不僅可以適用于可展曲面的展開，對于復雜不可展曲面也可實現較高精度的展開，具有較強的通用性.

［1］SORKINE O，COHEN－OR D，GOLDENTHAL R，et al.Bounded－distortion piecewise mesh parameterization［C］∥Proceedings of the IEEE Visualization Conference.Boston：IEEE，2002.

［2］王弘，王昌凌.基于能量模型的曲面展開通用算法［J］.計算機輔助設計與圖形學學報，2001，13（6）：556－560.

［3］陳功，周來水，安魯陵，等.一種通用的復雜曲面展開方法研究［J］.中國機械工程，2007，18（24）：2914－2920.

［4］嚴國彪，劉斌.一種基于能量模型的曲面展開改進算法［J］.華僑大學學報：自然科學版，2011，32（2）：135－139.

［5］蘇步青，華宣積，忻元龍.實用微分幾何引論［M］.北京：科學出版社，2010.

［6］WANG C C L，SMITH S S F，YUEN M M F.Surface flattening based on energy model［J］.CAD Computer Aided Design，2002，34（11）：823－833.

［7］毛昕，毛普元，孫靜.自由曲面最佳展開基點的幾何屬性［J］.工程圖學學報，2008，29（2）：98－103.

［8］張敬濤，楊光，任海英.曲面展平算法在鞋樣設計中的應用［J］.工程圖學學報，2007，28（3）：13－17.

［9］毛國棟，孫炳楠，徐浩祥.基于彈簧－質點系統的薄膜結構曲面展開算法［J］.浙江大學學報：工學版，2005，39（8）：1238－1242.

［10］雷軍鵬.一種基于能量法的自由曲面展開算法［J］.機械設計與制造，2007（4）：28－30.

An Algorithm of Triangular Mesh Surface Flattening Based on Spring－Mass Model and Its Application

HAN Lin，LIU Bin
（College of Mechanical Engineering and Automation，Huaqiao University，Quanzhou 362021，China）

To improve the algorithm of surface flattening optimization based on the spring－mass model，this paper presents a self－adjustment initial flattening method，which could retain topological completeness of initial flattening plane.Meanwhile，in order to avoid the divergence of the model iterations，the method is used in which the errors before and after the energy releasing are determined，to eliminate effectively the divergence of the algorithm.Finally the algorithm is applied in the field of manufacturing industry and the results have shown that the flattening plane with higher quality can be obtained using the algorithm.

spring－mass model；self－adjustment；initial flattening；triangular mesh

黃曉楠 英文審校：鄭亞青）

TP 391

A

1000－5013（2011）06－0601－06

2011－04－22

劉斌（1972－），男，副教授，主要從事數字化設計與制造計算機輔助幾何設計的研究.E－mail：mold＿bin＠hqu.edu.cn.

福建省科技計劃重點項目（2009H0032）