（机械设计及理论专业论文）三角化曲面展开技术研究及其应用.pdf

摘要 合理地展开三维曲面是c a d & c g 领域中众多技术得以实现的重要基础。对于复杂的曲 面，很难用解析的方法展开。随着曲面造型和3 d 扫描技术的发展，高度复杂的模型表面可 以由三角化曲面表示，从而将该问题转化为三角化曲面的数值展开问题。尽管近二十年来 对三角化曲面展开的研究取得了很大的进展，但复杂曲面展开技术仍有很大的研究与应用 空间。 本文在分析研究历史和存在问题的基础上，归纳了影响三角化曲面展开效果的因素， 即曲面的可展程度、曲面的网格质量以及曲面的展开方式。在此基础上给出了相应的解决 方案：通过曲面切割提高曲面的可展程度；基于质点一弹簧模型的曲面准对称化展开算法展 开三角化曲面；基于双向映射的曲面层次网格化展开算法展开高度复杂的三角化曲面。两 种展开算法的有机结合在“横向”和“纵向”两个方面提高了对网格质量不高的复杂曲面 的展开能力 基于高斯曲率，给出了三角化曲面可展程度的衡量方法。曲面可展程度为合理地切割 曲面和合理地构建层次网格提供了指导。三角化曲面上的网格顶点和网格边被抽象为质点一 弹簧模型，用来控制网格形状。为了更好地减小曲面展开过程中的网格变形以及更好地在 层次网格构建过程中优化网格质量，在质点一弹簧模型一般形式的基础上，分别给出了带跨 边弹簧的质点弹簧模型和带约束弹簧的质点一弹簧模型。两种改进模型为有效降低曲面展开 结果中的变形能和网格质量对曲面展开结果的影响提供了模型支持。 提出了两种曲面切割算法，即切割区域自动识别的曲面交互切割算法和切割路径自动 生成的曲面自动切割算法在曲面交互切割算法中，给出了待切割曲面片的切割边界和切 割区域的自动识别机制，以较少的交互操作，智能地实现对复杂曲面的切割。定义了多种 切割线类型，对应不同的切割机制，提高了曲面切割的灵活性。在曲面自动切割算法中， 以提高曲面的可展程度为目标，给出了切割路径自动生成规则，进一步以避免短小切割边 界和切割路径尽可能光滑为约束条件，优化初始生成的切割路径由优化后的切割路径切 割曲面提高了切割效率和切割边界的光滑程度。 提出了基于质点弹簧模型的曲面准对称化展开算法。从中心三角形带开始，以三角形 带的形式准对称地展开网格曲面，展开过程中网格形状变形能从中心三角形带开始向两侧 均匀分布，变形能更容易释放。由带跨边弹簧的质点一弹簧改进模型模拟曲面展开过程中的 网格形状变形，以隐式欧拉方法显式化释放变形能，变形能释放过程既具有显式欧拉方法 的简洁性又具有隐式欧拉方法的稳定性。通过自适应矫正和约束矫正减少曲面展开结果中 三角形反折现象出现的几率。给出了自动检测并矫正曲面展开结果上重叠现象的方法。 提出了基于双向映射的曲面层次网格化展开算法。层次网格的构建集减少网格数目和 提高网格质量为一体，可以很好地展开复杂曲面并有效降低网格质量对曲面展开结果的影 响。建立了层次网格间的双向映射关系，避免层次网格构建过程中累积形状误差的产生。 通过边折叠简化网格，给出了保持曲面特征的边折叠规则。边折叠顺序由兼顾网格边长度 和两格边对曲面特征影响的顺序控制园子决定。在简化结果上。利用带约束弹簧的质点一弹 簧改进模型局部约束优化网格顶点一阶邻域内的网格质量，调整曲面上所有网格顶点，在 全局上优化网格质量。基于层次网格间的双向映射关系，给出了新的双向h a u s d o r f f 距离计 算方法，用来衡量和控制层次网格闻的形状误差。 以本文的研究成果为技术核心，开发了曲面展开系统e x 。e x 系统可以广泛应用于服装、 玩具、鞋样、汽车椅子等产品设计领域，并给出了相应的实例。 关键词：三角化曲面、质点弹簧模型、曲面展开、曲面切割、准对称带、层次网格、双向 映射、双向l h u s d o r f l 距离 a b s t r a c t s u r f a c ef l a t t e n i n gi sa l li m p o r t a n tb a s ef o rm a n yt e c h n o l o g i e sj nt h em 龃o fc a d & c g u n f o r t u n a t e l y , s e l d o mc o m p l e xs u r f a c e sc a n b ef l a t t e n e da n a l y t i c a l l y b e n e f i t e df r o mt h ea d v a n c e o f3 ds c a n i l i l l ga n dm o d e l i n g , h i g hc o m p l e xs u r f a c ：e sc a l lb ed e s c r i b e dw i t hu i a n g l e s t h e r e f o r e w ec a nf l a t t e nas l l r f s g en u m e r i c a l l yb ym e 柚so ff l a t t e n i n gt r i a n g l e s a l t h o u g h , i nt h el a s tt w o d e c a d e s ，g r e a tp r o g r e s sh a sb e e nm a d ei nt h es t u d yo f 仃i a n g u l a t e ds u r f a c ef l a t t e n i n g , f l a t t e n i n ga l l i 曲c o m p l e xs u r f a c er e m a i n sa no p e np r o b l e me v e nt o d a y o nt h eb a s eo fa n a l y s i so fi t sh i s t o r ya n dt h ep r o b l e m sr e m a i n e d , w ef i n do u tt h ef a c t o r s i n f l u e n c i n gt h er e s u l to fs u r f a f l a t t e n i n g t h e ya 地t h es u r f a g ed e v e l o p a b i l i t y , m e s hq u a l j 母， m e t h o df o rs u r f a c ef l a t t e n i n g c o n s e q u e n t l y , as w a t e g yt h a ti sh e l p f u lt oc o n q u e rt h o s e d i s a d v a n t a g ef a e l o r si sp r o p o s e d ：s u r f md e v e l o p a b i l i t yi si m p r o v e db ys u r f a c et r i m m i n g s u r f a c e sa r ef l a t t e n e dw i t hq u a s i - s y m m e t x i c a l l yd i s t r i b u t e dm a n g l es t r i p sb a s e do i lam a s s - s p r i n g m o d e l h i g hc o m p l e xs u r f a c e sa r ef l a t t e n e dw i t hh i e r a r c h ym e s h e sb a s e d0 1 1b i - m a p p i n g t h e i n t e g r a t i o no ft w os u r f a c ef l a 地碰i l ga l g o d t h m si m p r o v e st h ea b i l i t yo nf l a t t e n i n gh i g hc o m p l e x s u r f a c ew i t hl o wm e s hq u a l i t , f r o mt h ec r o s s w i s ea n df i a el o n g i t u d i n a lt w oa s p e c t s b a s e do i lg a u s s i a nc u r v a t u r e , am e t h o df o re v a l u a t i n gt h ed e v e l o p a b i l i t yo ft r i a n g u l a t e d 飘玎f h 淄i sp r e s e n t e d s u r f a c ed e v e l o p a b i l i t yp r o v i d e sg u i d e sf o rc u t t i n gs u r f a c * r e a s o n a b l ya n d c r e a t i n gh i e r a r c h ym e s hp r o p e r l y v e r t i c e sa n de d g e so i lt h et r i a n g 妇ls u l f a c ea na b s t r a c t e d i n t oa m a s s - s p r i n gm o d e lw h i c hi su s e dt oc o n t r o lt h es h a p eo fu i a n g l e s i no r d e rt om o r e e f f i c i e n t l yd - l e a s et h es h a p ed e f o r m a t i o no f t r i a n g l e s 州n gs u g f a t f l a u e n i i l ga n dd e c r e a s et h e i n f l u e n c eo fm e s hq u a l i t yi nt h ef l a t t e n i n gr e s u l t s , t w oi m p r o v e dm a s p r t n gm o d e l sm p r e s e n t e dr e s p e c t i v e l y , t h e ya r et h em o d e lw i t hac r o s s e ds p r i n ga n dt h em o d e lw i t ha c o n s t r a i n t s p r i n g w i 也廿l o s et w oi m p r o v e dm o d e l s , w e c a l le f f i c i e n t l yd e , c r e a s et h ed e f o r m a t i o ne n e r g yi n s u r f a c ef l a t t e n i n gr e s u l t sa n dd e c r e a s et h ei n f l u e n c eo f m e s hq u a l i t yi nt h ef l a t t e n i n gr e s u l t s t w oa l g o r i t h m sf o rt r i a n g u l a t e ds u r f a c e 岫i i l g 矾p r o p o s e d t h e y 锄t h ea l g o f i f l n no f i n t e r a c t i v es i n - f a c e 研m m i n gw i t h c 0 霉d z i i l gc i i l d n gr e g i o na u t o m a t i c a l l ya n dt h ea l g o r i t h mo f a u t o m a t i cs u r f a c et r i m m i n gb a s e do ng e n e r a t i n ga n do p t 砬j n gc u t t i n gp a t ha u t o m a t i c a l l y i nt h e i n t e r a c t i v es u r f a c et r i m m i n ga i g o r i f f a n , c t l c 吐n gi i l i a r gd r a w ni n 衄a c t i v e l yo i lm o d e ls f 缸t o o u t l i n et h es h a p eo f3 dp a t c h e s , t h e nb o u n d a r i e so fe a c hp a t c hi ss e a r c h e do u ta u t o m a t i c a l l yb y p i c k i n gap o i n ti n s i d et h ep a t c h , a n df i n a l l yt h ep a t c hi s t r i m m e do u ta u t o m a t i c a l l yw i t hi t s b o u n d a r i e s s e v e r a lt y p e so f c u t t i n gl i n e sw i md i f f e r e n tn i m m m gm e c h a n i s m sa 撑d c i i d w h i c h m a j i 酪t h ed e s i g nf l e x i b l e t h ea u t o m a t i cs i l l - f a c et r i m m i n ga l g o r i t h mr e g d sd e c r e a s i n gg a u s s i a n c u r v a t u r ea n di m p r o v i n gt h e d e v e l o p a b l i l yo f 仃i 粕g t l l 删s u r f a c e s a si t sg o a l ，r u l e sf o r a u t o m a t i c a l l yc r e a t ec u t t i n gp a t h so nt r i a n g u l a t e ds u r f h c em - ep r e s e n t e d m o r e o v 盯, c u t t i n gp a t h s a r eo p t i m i z e dw i t ht h ec e n s t t a i l i t so fa v o i d i n gs h o r t 咖i 1 1 9b o u n d a r i e sa n dc u t t i n gp a t h ss h o u l d b e s m o o t h 笛p o s s i b l e w i mt h o s er u l e s , c u t t i n gp a t h sb e c o m ec o n u o l l a b l e t r i a n g u l a t e d 吼 伍。鹤a l et r i m m e da u t o m a t i c a l l yb yt h eo p t i m i z e dc u t t i n gp a t h s , w h i c hi m p r o v et h ec u t t i n g e f f i c i e n c ya n dt h es m o o t h n e s so f b e u n c l a 】r i e so nc u t t i n gr e s u l t s t r i a n g u l a t e ds l t r f a c ei sf l a t t e n e dw i t hq u a s i - s y m m e t r i c a l l yd i s t r i b u t e du m g l es t r i p sb a s e do n am a s s - s p r i n gm o d e l f r o mt h ec e n t r a lw i a n g l es w i p , aw i a n g u l a t e ds u r f a c ei sf l a t t e n e do n es t r i p e b ya n o t h e r , a n dt h ed e f o r m a t i o ne n e r 科i ss y m m e t r i c a l l yd i s t r i b u t e do nb o t hs i d e so ft h ec 扛a l t r i 删es t r i p , w h i c hi sh e l p f u lt 0r e l e a s et h ed e f o r m a t i o ne n e r g y a ni m p r o v e dm a s s - s p r i n gm o d e l c o n t a i n i n gac r o s s e ds p r i n g i su s e dt os i m u l a t et h ed e f o r m a t i o no ft r i a n g l e sd u r i n gs u r f a c e f l a u e n i n g d e f o r m a t i o ne n e r g yi sr e l e a s e db ya p p r o x i m a t i n gt h ei m p l i c i te u l e rm e t h o dw i t h e x p l i c i te u l e rm e t h o d t h e r e f o r e ，t h ee n e r g yr e l e a s i n gp r o c e s so w n sb e t ht h es t a b i l i t yo fi m p l i c i t e u l e rm e t h o da n dt h ec o n c i s i o no fe x p l i c i te u l e rm e t h o d t or e d u c et h eo c a 盯咒n c eo f 妇n g l e f l i p p i n gi nf l a t t e n i n gr e s u l t s , ac o n s t r a i n e df l a t t e n i n gi t e r a t i o nm e t h o da n dal o c a lc o n e c t i o n m e t h o da r ep r e s e n t e d am e t h o df o rm r l o m a t i c a l l ys o l v i n gt h ep r o b l e mo fo v e r l a po i lt h e f l a t t e n i n gr e s u l t si sp r e s e n t e & h i g hc o m p l e xt r i a n g u l a t e d 吼h 触w i t hl o wm e s hq u a l i t yi sf l a t t e n e dw i t hh i e r a r c h ym e s h e s b a s e do nb i - m a p p i n g m e s hs i m p l i f i c a t i o na n do p t i m i z a t i o na 旭i n t e g n 壮e dt os e tu ph i e r a r c h y m e s h e s w 岫h i e r a r c h ym e s h e s w ec a ne f f i c i e n t l yf l a t t e nc o m p l e xs u r f a c e sa n dd e c r e a s et h e i n f l u e n c eo fm e s hq u a l j 锣o i lt h ef l a t t e n i n gr e s u l t s b i - m a p p i n gb e t w e e nt h e 删日ti _ l i e r a r c b y m e s h e si ss e tl j p ，w h i c ha v o i d sp r o d u c m ga c c m n u l 面v e 蜥e r r o rd i m n gm e s hs i m p l i f i c a t i o n a n do p f i m i z a t i o r lm e s hs i m p l i f i c a t i o ni sr e a l i z e db ye d g ec o l l a p s i n gw h i l ep r e s e r v i n gs u r f a c e s f e a t u r e e d g ec o l l a p s es e q u e n c et a k e se d g el e n g t l la n di t si n f l u e n c eo os u r f a s h a p ei n t o c o n s i d e r a t i o n b a s e do i la ni m p r o v e dm a s s s p r i n gm o d e lt h a tc o n t a i n sa m 仃a i ms p l 证岛w e a d j u s tt h ep o s i t i o no f e a c hv e r t e xo nt h es i m p l i f i e d $ 1 a f a c e $ t oo p t i m i z et h es h a p eq u a l i t yo fi t s a d j a c e n tw i a n g l e s w h e na l lo f t h ev e r t i c e sa 鹏o p t i m i z e d , m e s hq u a l i t yo i lt h es i m p l i f i e d $ u r f a c e $ a r eg l o b a l l yi m p r o v e d an e wm e t h o df o rc o m p i n gt w o - s i d eh a u s d o r f fd i s t a n c eb e t w e e nt w o a d j a c e n th i e r a r c h ym e s h e si sp r o p o s e db a s e do nb i - m a p p i n g a n dt w o - s i d eh a u s d o r f f d i s t s o r * i s u s e dt 0m e a s u r ea n dc o n t r o lt h es h a p eo r t d rb c 咖a d j a c e n t 量l i e 蛳h ym e s h e s w 曲t h er e s e a r c hr e s u l t so f t h i st h e s i s w ed e v e l o p e da s y s t e mn a m e de x e x 锄b ew i d e l y u s e di nt h ep r o d u c td e s i g ni n d u s w i e ss u c ha sg a r m e n t , t o y , s h o o , s e a ta n ds o0 1 1 k e y w o r d s ：t f i a i 】g u l 砒i 甜s l h f a c e ，m a s s - s p r i l l gm o d e l ，s u 舭ef l a t t e n i n g , s u r f a c et r i m m i n g q u a s i - s y m m e t r i ct r i a n g l es t r i p ，h i e r a r c h ym e s h , b i - m a p p i n g , t w o - s i d eh a u s d o r f f d i s t a n c e 独创性声明 本人声明所呈交的学位论文是本人在导师指导下进行的研究工作及取得的研究成 果。据我所知，除了文中特别加以标注和致谢的地方外，论文中不包含其他人已经发表 或撰写过的研究成果，也不包含为获得逝垄盘堂或其他教育机构的学位或证书而使 用过的材料。与我一同工作的同志对本研究所做的任何贡献均己在论文中作了明确的说 明并表示谢意。 学位论文作者签名：奢莠妊 签字口期：2od ，年，2 月p 日 学位论文版权使用授权书 7 本学位论文作者完全了解盘堑盘生有关保留、使用学位论文的规定，有权保 留并向国家有关部门或机构送交论文的复印件和磁糯，允许论文被查阅和借阅。本人授 权逝望盘堂可以将学位论文的全部或部分内容编八有关数据库进行检索，可以采用影 印、缩印或扫描等复伟i 手段保存、汇编学位论文。 ( 保密的学位论文在解密后适用本授权书1 学位论文作者签名： 鸯器括 导师签名 闰渺 ti 签字日期：2 m r 年) 月吕日 签字日期：阿年1 卜月占 e t 学位论文作者毕业后去问 工作单位： 通讯地址： 电话 邮编 第一章绪论 1 1 引言 曲面作为三维形体最直接的表达，一直来是c a d & c g 领域研究的热点对象。虽然利用 现有的三维造型和三维扫描技术可以模拟高度复杂的模型曲面，然而由于曲面本身的复杂 性，对曲面的某些复杂操作需要借助曲面的二维展开结果实现，如c o 领域中的纹理映射、 曲面融合等，服装、玩具等产品c a d 领域中为了确定缝制三维产品曲面所需的= 维材料的 轮廓，需要将三维曲面展开到二维平面。因而，对三维曲面的二维展开技术研究有着重要 的理论和应用意义 尽管早在公元2 世纪，希腊天文学家c l a u d i u s p t o l e m y ( 1 0 0 - 1 6 8 ) 就在他的著作g e o g r a p h y 中提出了利用经纬线展开圆球到二维平面的方法，但直到上世纪8 0 年代，对复杂曲面展开 问题的研究仍没有取得多大的进展，其主要的原因在于，大多数的复杂曲面很难用解析的 方法展开。近十几年来，随着复杂曲面网格表示技术的成熟，研究人员开始借助数值方法 展开三角化曲面并取得了实质性的进展，但复杂曲面展开技术仍有很大的研究空间。 本文对三角化曲面展开的研究以产品设计领域为背景。在产品设计领域中，大多数产 品的外形为数学意义上的不可展曲面，在曲面展开结果中，不可避免地存在着变形大的 变形使得按曲面展开结果裁剪出的材料覆盖到产品表面上时，产生大的应交，对于一般的 材料而言是不允许的。为了避免展开结果中出现过大的变形，通常将曲面切割成多个更小 的曲面片来处理，如足球的球面就是由若干个五边形和六边形缝制而成。合理地选择切割 方式，不仅可以有效降低曲面展开结果中的变形，同时也提高了曲面造型的灵活度。 通常曲面展开算法的展开效率和展开效果对曲面的几何形状复杂程度和曲面上网格的 形状质量敏感。曲面几何形状越复杂或曲面上狭长或细小的三角形越多，则在展开结果中 越容易引起大的变形，甚至影响曲面展开结果的正确性。合理地选择曲面展开方式和变形 能释放方法可以有效地提高曲面的展开效率和展开效果。 本文的研究内容覆盖了三角化曲面展开算法及其前置处理：为提高曲面可展程度和曲 面设计灵活度的曲面切割算法，以及为快速、稳定地展开曲面得到变形能最小化的基于质 点一弹簧模型的曲面准对称化展开算法和基于双向映射的曲面层次网格化展开算法。 以本文研究内容为核心技术，实现了一个三角化曲面处理软件一e x 系统，e x 可广泛应 浙江大学博士学位论文 用于服装、布绒玩具、鞋样、汽车椅子等众多产品设计领域。 1 2 曲面切割算法综述 曲面切割广泛用于曲面造型、图形编辑、医疗手术虚拟等领域中。通常，可以将曲面 切割算法归结为两类：视觉切割和几何切割。在视觉切割中，只有切割边界的其中一侧益 面被显示，切割后，没有显示的曲面并没有从几何上切割去，而只是在视觉上的一种消影 处理。相反，几何切割则是赋予被切割面新的几何描述。在曲面造型、图形编辑和医疗手 术虚拟现实等领域中大多采用几何切割法。 本文只讨论几何切割算法，然而只有少量的曲面可以通过解析求解两相交曲面来获取 切割边界，即使可能，实现起来往往也相当困难，因而必须借助于数值方法。按切割边界 生成方法的不同，可以将曲面切割技术分为交互切割和自动切割两大类。 1 2 1 曲面交互切割 曲面交互切割在众多领域有着其重要的应用：在产品设计领域中，由于工艺和力学特 性等要求，通常将不可展曲面分割成可展程度更高的若干个曲面片，以降低曲面展开结果 中的变形，如服装由众多的小裁片缝制而成。在曲面建模中，曲面切割是其中一个基本的 算法。在手术模拟中，肌体组织由空间网格模拟。虚拟的手术刀划过肌体组织时，将切割 并重新网格化肌体以模拟真实的手术情况。在不同的应用领域，曲面的切割处理方式也不 尽相同，大致可以将现有的曲面切割算法分为以下两类： ( _ )以曲面间的交线为切割边界 这类算法在曲面交互造型中有着重要的应用。在曲面造型过程中，当曲面两两相交时， 通常需要将交线转化为网格边，并在交线上重新网格化曲面衄1 ”to o d ”眠“2 “酬。 l o 给出了一种求解三角化曲面问交集的简单算法，切割后的曲面边界能够自动地拟合 交线曲1 删但是，在他们的算法中，在曲率较高的区域附近，计算所得的交点有可能不在 原始曲面上，而这在很多产品设计领域是不适合的受l o 的启发，c o e l h o 等给出了一种定 义在参数曲面上有限元网格问交集的计算方法 c o d “2 0 0 0 。l i 馏进一步的扩展了 c o e l h o2 0 0 0 的算法作，可以处理多个曲面相交的情况“2 ”，如图1 1 所示。最近，l o 等对算法m 1 9 9 5 】 做了进一步的拓展，从而可以胜任大量曲面之间交线的求取删。 2 浙江大学博士学位论文 图1 1 多个曲面之间的布尔运算1 一烈嘲 ( b ) 以交互绘制在曲面上的切割线为切割边界 这类算法在手术模拟中有着大量的应用皿妇1 9 9 9 脚“8 q 。2 0 0 2 “咖”，如图1 2 所示可以将这类算法的实现步骤概括如下； 其次，将切割曲线转化为曲面的切割网格边 首先，计算切割曲线与模型曲面之间的交点； 最后，将每条切割网格边转化成两条重合的 网格边，重新三角化被切割的三角形，新生成的网格曲面在切割线上不存在拓扑连续性。 在这类切割算法中，切割线既可以是开曲线也可以是闭曲线，如果是闭曲线，通常只考虑 简单的单连通区域。类似的算法还应用于网格曲面拉伸造型中删 圈1 2 虚拟手术中的曲面切割肚岬- 硝嘲 1 2 2 曲面自动切割 曲面自动切割算法大多应用于纹理映射等图形学领域【9 9 “2 0 0 0 翻”“w a n 9 2 0 0 4 b c m 2 0 0 2 。 为了获取曲面上各顶点的纹理坐标，通常需要将曲面展开到二维平面上。为了得到合理的 二维展开结果，需在以下两种情况下切割曲面： ( a )现有的展开算法大多只能处理非封闭网格曲面，当模型为封闭曲面时，需要对 模型作切割处理； ( b )曲面展开结果的变形程度直接影响三维曲面上纹理显示的效果，对于可展程度 3 浙江大学博士学位论文 较低的网格曲面，曲面切割处理是降低曲面展开变形的一种有效的途径 m u n k e 6 等人指出可以将任何封闭的曲面沿着特定的网格边切割成盘状拓扑曲面哪“ 2 0 0 0 1 。切割线的引入改变了曲面的边界，在切割线上曲面变得不连续。因此在有效降低曲面 展开结果变形的前提下，缩短切割线的长度通常是自动切割算法追求的目标。 p i p o n i 等人设计了一个交互系统，用户可以通过树状的网格边切割将一个亏格为零的曲 面切割成分块的曲面片脚”2 0 0 0 i 。s h e 行e r 等人【9 “冒2 0 0 1 b 与w a r i g 等人阳“曲】对网格曲面的 自动切割算法进行了研究，并应用于曲面展开算法中，以减少曲面展开结果中的变形。在 他们的算法中，以降低曲面高斯曲率为基本手段，由高斯曲率较高的内部顶点为起始点， 沿测地线距离下降最快的网格边向曲面边界作相应的切割线，以缩短切割线的长度，如图 1 3 所示。算法可以有效地减少展开结果中的变形。 ( a ) 三维牛模型( b ) 模型上切割线( c ) 切割线轮廓 图1 3 网格曲面上切割线自动生成r ”一删 1 3 曲面展开算法综述 曲面展开( 或网格曲面参数化) 算法建立了三维曲面与二维展开面之间的一一映射关 系，即y ( s ( 五y ，z ) ) = o ( x ，力，s c 帮，t l c 盂2 ，y 为映射关系，并保持三维曲面与 二维展开面之问拓扑同胚，如图1 4 所示 图1 4 三角化曲面展开 卜 近年来，网格曲面展开技术一直是c a d c g 领域的一大研究热点，并影响着纹理映射 4 浙江大学博士学位论文 阻m l ”i 劬h i 螂脚撇l 、曲面重新网格化陬1 9 鸭“1 9 9 s , 1 k a 2 0 0 1 、离散点三角化哪“田 以及产品设计【l i m 4 。血抛1 w i n 9 2 0 0 2 , “2 0 0 4 ，。”“3 1 等众多领域的发展 评价曲面的展开效果主要从网格边长度、网格内角和网格面积等基本几何属性的变形 来判断，理想的结果是维持这些基本几何属性不变，但这只有在曲面为可展曲面时才成立脚 - 枷州9 7 6 1 。就不可展曲面而言，展开结果中不可避免地存在着变形。所有曲面展开算法都围 绕解决一个或多个几何变量组合的变形最小化问题展开 在不同的应用领域，众多的学者提出了不同的算法大致可以将曲面展开算法划分为 平面参数化方法和网格曲面几何展平法。 1 3 1 平面参数化 以映射函数的形式建立三角化曲面与二维展开结果之间的一一对应关系，这种通过求 解方程组获取二维展开结果的方法被称为网格的参数化。 早在2 0 世纪6 0 年代，研究人员提出了三角化曲面的参数化研究m “1 9 6 0 l ，直到上世纪9 0 年代，该问题才得到了广泛、深入的研究，并成为图形学研究领域中的一大热点。f l o a t e r 等人脚”叫和彭群生等人【啦“i 对网格曲面平面参数化技术做了综述根据映射函数类型 的不同，又可将参数化方法分为线性和非线性参数化两类。 ( a ) 线性参数化 线性参数化算法是近年来研究最为广泛、深入的一类平面参数化算法。通常，这类算 法要求曲面为盘状拓扑结构，并有着相似的实现步骤【”瑚： 首先，将曲面边界网格顶点构成的空间多边形映射到二维凸多边形上； 然后，在二维映射域上，将内部网格顶点表达为其相邻网格顶点的凸组合，即对于 v m ，在二维域上的映射点为 y o ) = 2 ” ( ) ( 1 一1 ) 其中妒p ) 表述网格顶点v 的参数化结果，障示网格顶点集合，n 表示曲面内部的网格顶点， m ； e v ：【w ，v 】毋，e 为网格边的集合，a ，为系数，薹a * = 1 可以进一步将公 e r 式( 1 1 ) 改写为。 浙江大学博士学位论文 y ( v ) 一五棚( w ) = a 哪矿( ，) ， ，m ( 1 - - 2 ) m mm m 公式中：赡表示曲面边界上的网格顶点， w ，p 】e e 。进一步可以将公式( 1 2 ) 改写为： a x = b( 1 - - 3 ) 公式中：x = ( y 9 ) 卜n 为列向量，6 为列向量，其各元素由公式( 1 2 ) 中的右式表示， 么= ( 州一v n 为n x n 的矩阵，为内部网格顶点数目，并有 ll ，w = v 伽= 一五w ，m io ，o t h e r w i s e 求解线性方程组( 1 3 ) 可以快速地得到二维参数化结果，如图1 5 所示。 五，取值方法的不同，得到了不同的参数化结果。p i n k a l l 等人册枷1 蜘1 和e c k 等人阻d “9 蜘 通过最小化d i r c i l l e t 能量，给出了具有保角特性的五一取值。f l o 椭过共形映照和重心坐标 确定旯，得到保形的参数化结果呷”1 ”n o a a 2 0 0 2 o e s b r u n 等从离散微分几何出发，通过 最小化网格曲面某些本质度量的参数化变形设置五一，提出了网格的本质参数化方法，可以 得到很好的曲面展开效果陋蛔咄嘲 令一豳 m 1 5 线性参数化唧”2 嗍 上述线性参数化方法将曲面的网格边界固定在二维域上，因而参数化结果中的边界并 非自然边界。在参数化结果中的边界网格上存在很大的变形，如图1 6 所示。l e e 等人在待展 开曲面的边界上加上多层虚拟的三角形环作为虚拟边界，并对调整后的网格曲面线性参数 化展开，可以得到待展开曲面的非凸边界的平面参数化结果脚i 。虚拟网格环的层数越多， 得到在参数化结果的边界越接近于自然边界，但这毕竟是一种近似的表示为了得到边界 更为自然的参数化结果，一些学者提出了非线性的求解方法。 6 浙江大学博士学位论文 越圜瀚 ( a ) 3 d 曲面( b ) 圆形域线性参数化 ( c ) 矩形域线性参数化( d ) 非线性参数化 圈1 6 线性和非线性参数化结果变形比较唧螂硝田 ( b ) 非线性参数化 非线性参数化方法通过构造一个非线性的曲面展开变形能衡量函数，最小化曲面展开 结果变形。由于l i i 标函数的非线性，常采用迭代的方法逼近目标函数的最小值，得到边界 较为自然的展开结果。 h m 等人提出了近等形曲面参数化方法阿“一1 9 9 8 i ，在原始网格和相应的二维域参 数化三角形之间引入线性映射g ( 功= a x + 6 ，如图1 7 所示，在此基础上，通过求解一个带 约束的非线性系统七= 荟b ( 毋) ，扫( 昏) = 竺墅型堕 二气吉型甓斧i 型，得到e h l 有着自然边界的二维参数化结果，缸( 矛) 中相关字母的含义如图1 7 所示，其中 1 1 = y ( v 1 ) 一_ l c ( v 3 ) ，h = 矿( v 3 ) 一少( v 2 ) ，h = y ( ) 一y ( v 2 ) 。l a b s i k 等将该方法于曲面的 重新网格化嗍啷】。 t ( 均 l i ( v 1 ) 图1 7 三角形问线性映射岫脚血1 9 9 搴i 3 s h e 瞄人用三角形内角变形表示曲面展开效果：f ) = 叫( 彰一彰) 2 ，其中， j 1 1 j - i 彰是网格曲面上三角形内角彰在二维参数域上的目标值，叫为权重，月为网格个数“ 浙江大学博士学位论文 “”。算法与网格内角相关，而与网格顶点的具体坐标无关，在展开结果中任意选取一网格 边，并指定其二维坐标位置，则网格上其它顶点的二维坐标可以通过三角形正弦定理确定 算法中，虽然最小化f ( 口) 可以通过线性方法求取，但为了保证参数化结果的正确性通常需 要加入一些约束，有些约束则是非线性的，目标函数也因此变得非线性。 非线性参数化方法可以得到很好的网格曲面展开结果，但非线性方程组的求解大多采 用迭代逼近的方法，效率在某种程度上成为这类算法的瓶颈。 分片展开和基于累进网格的啦面展开方法是提高算法效率和降低展开结果变形的两种 有效的方法。l 6 v y 用最小二乘法逼近c a u c h y - l 五e m a n 方程，提出了一种仿射参数化算法 叫邮嗍，在他们的算法中，一个复杂的曲面将分解成相应的几小块，并利用目标函数最小 化三角形内角变形。在展开的过程中检测三角形反折现象，若发现存在三角形反折现象， 则将相应的分块再进步细分，直至三角形反折现象不再出现。s a n d e r 在累进网格的基础上 设计了两种非线性的变形度量来最小化网格表面上任意点在所有方向上的参数化伸缩变形 【s 删 对于盘状拓扑网格曲面，非线性参数化展开算法可以得到变性能最小、边界自然的展 开结果，但这类算法通常也只适合于求解盘状无“空洞”的网格曲面。当网格存在空洞时， 如图1 8 所示，需要先填补空洞后展开曲面，并在展开结果中去除空洞部分嘶一1 9 9 3 蛐 ”对于复杂曲面上空洞的填补在模型处理领域本身就是一个比较难的课题，填补空洞的 曲面形状也将影响模型的展开结果。由于上述原因，曲面参数化展开算法通常适用于计算 机图形学中的纹理映射、曲面重新网格化等领域，在产品设计中则很少应用。 1 3 2 几何展平法 图1 8 带。空洞一曲面的参数化展开【s “幽。2 l l 相对于纹理映射，产品设计领域对曲面展开结果的变形有着更为严格的要求。在产品 8 浙江大学博士学位论文 设计领域，有时需要展开带多个边界环的网格曲面，要求展开结果有着自然的边界且变形 尽可能小，网格曲面平面参数化算法很难胜任类似的情况。网格曲面几何展平法通过依次 将曲面上的三角形展开到二维平面，