基于弹簧－质点模型的三角网格曲面展开算法及其应用

韩林，刘斌

（华侨大学 机电及自动化学院，福建 泉州 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）