（机械设计及理论专业论文）服装cad中区域搜索与裁片缝合技术的研究与实现.pdf

浙江大掌硕士掌位论文 摘要 摘要 服装c a d 系统从二维向三维转变，是三维计算机技术成熟与服装个性化定制的 一个必然趋势与结果。虽然有关的研究工作已经蓬勃展开，但要达到实用的水平还有 很多工作要做。本论文研究了切割区域搜索与二维裁片缝合的实现技术，阐述了三维 服装原型还原成可以裁剪、缝合的二维裁片以及二维裁片缝合成三维服装展示服装成 型效果的中心环节。 服装的三维裁剪完全是基于人体模型进行的，利用三维裁剪获得的裁片加工制成 的衣服更符合人体。切割区域的自动搜索是三维裁剪中的一个重要问题，论文第二章 从曲面切割出发，对切割区域自动搜索进行详细定义，并给出了普通切割区域的搜索 方法，兼顾搜索速度与搜索结果精度。针对带桥边或省道的切割区域给出了新的搜索 算法，从而解决了服装、玩具设计中的存在特殊切割线的区域搜索问题。最后还给出 了几个实例来比较算法的效率和精度。 二维裁片的预处理是裁片缝合的基础。论文第三章首先对曲面展开算法做了简单 介绍，在弹簧一质点模型和几何展平法的基础上，完成曲面片三维到二维的映射；然 后介绍了裁片边界线生成方法，通过三维切割线经过网格顶点的信息构建裁片边界线 信息，再利用三次样条曲线生成裁片最终边界线；最后描述了缝合信息的获取方法， 在搜索公共切割线前提下，对裁片边界线进行离散处理，获得离散点集等相关信息。 二维裁片缝合是检查服装设计效果的有效手段。论文第四章介绍了常用的 d e l a u n a y 三角化算法，并通过实例比较了这些算法。针对重三角化后的网格形状不尽 完美的情况，提出了利用网格边交换与网格边能量优化的方法来优化网格。同时利用 重心坐标把裁片顶点从二维映射到三维上；利用共享边界线的信息把分散的裁片重新 缝合到三维人体上。整个处理流程简单、高效且易于实现，有效的保证了缝合结果的 准确性。 基于上述研究工作，论文第五章介绍l o o k s t a i l o r x 系统框架，并对系统开发环境 作简要介绍，同时详细介绍了上述研究工作在该系统中的应用。 最后，在第六章总结本文的工作，并对项目课题研究的发展前景从技术上和应用 上作了展望。 关键词：服装c a d 、区域搜索、边界生成、d e l a u n a y 三角化，网格优化，裁片缝合 浙江大掌硕士掌位论文 a b s t r a c t a b s t r a c t i ti sa l li n e v i t a b l en e n df o rg c a ds y s t e mt oc o n v e r tf r o m2 dt o3 dd u et o3 d c o m p u t e rt e c h n o l o g y sm a t u r i t ya n d t h en e c e s s i t yo f c u s t o m i z e dg a r m e n t a l t h o u g hr e l a t e d r e s e a r c hh a sv i g o r o u s l ye x p a n d e d , al o to f w o r kn e e d st od ot oa c h i e v et h ep r a c t i c a ll e v e l i nt h i st h e s i s , w er e s e a r c h e dt h et e e h n o l o g i e so fc u t t i n gr e g i o ns e a r c h i n ga n d2 dp a t t e r n s e w i n g ，a n da l s oe l a b o r a t e dt h ee s s e n t i a lp r o c e s sa b o u tt h ep r o t o t y p eo f3 dg a r m e n t f l a t t e n e dt oc u t t a b l ea n ds e w a b l e2 dp a t t e r n s 嚣w e l la s2 dp a t t e r n ss e w e dt o3 dg a r m e n t f o rd e m o n s l r a t i n gg a r m e n tm o d e l i n ge f f e c t 3 dc u t t i n go fg a r m e n ti sc o m p l e t e l yb a s e do nt h em a n i k i i l ；h e n c eg a r m e n tm a d eb y p a t t e r n sw h i c hw e r eo b t a i n e df r o m3 dc u t t i n gc o n f o r m st ot h eh u m a nb o d y a u t o m a t i c r e g i o ns e a r c h i n gi sak e yp r o b l e mo f3 dc u t t i n g i nc h a p t e r2 ，s t a r t e df r o ms u r f a v 圮 t r i n u n i n g ，t h i n g sa b o u ta u t o m a t i c a lr e g i o ns e a r c h i n ga r ed e f i n e dw i t hd e t a i l s i na d d i t i o n , a s e a r c h i n ga l g o r i t h mf o rn o r m a lc u t t i n gr e g i o ni sp r e s e n t e d , w h i c hc o n s i d e r ss e a r c h i n g s p e e da n da c c u r a c y an e ws e a r c h i n ga l g o r i t h m f o rc u t t i n gr e g i o nw i t hd a r t so r s u p e r - l i n e si sp r o p o s e d , w h i c hs o l v e dt h ep r o b l e ma b o u tr e g i o ns e a r c h i n gw i t hs p e c i a l c 嘣i n gl i n e si ng a r m e n to r j o yd e s i g n f i n a l l y ，s e v e r a le x a m p l e sa g i v e dt oc o m p a r et h e e f f i c i e n c ya n dt h ep r e c i s i o no f t h ea l g o r i t h n 2 dp a t t e r np r e t r e a t m e n ti st h ef o u n d a t i o no fp a t t e r ns e w i n g i nc h a p t e r3 ，飘f a c e f l a t t e n i n ga l g o r i t h m sh a v eb e e ni n t r o d u c e db r i e f l y b a s e do nt h em a s s s p r i n gm o d e la n d g e o m e t r i c a lf l a t t e n i n ga l g o r i t h m , 鱿l r f a c em a p p i n gf r o m3 d t o2 da r ei m p l e m e n t e d a l s o m e t h o do fb u i l d i n gb o u n d a r yo fp a t t e r n si sp r e s e n t e d a l g o r i t h mg e t st h ei n f o r m a t i o no f b o u n d a r yl i n e sf r o m3 dc u t t i n gl i n ea n dc r e a t e st h eb o u n d a r yl i n e su s i n gc u b i cb s p l i n e i n t h ee n d , m e t h o do f g e t t i n gs e w i n gi n f o r m a t i o ni sd e p i c t e d b o u n d a r yl i n e sa r ed i s c r c t i z e d i n t op o i n t 鳅i nt h ep r e c o n d i t i o no f s e a r c h i n gc o m m o nc u t t i n gl i n e 2 dp a t t e r ns e w i n gi sa na v a i l a b l em e t h o df o ri n s p e c t i o nt h eg a r m e n td e s i g ne f f e c t i n c h a p t e r4 ，r e g u l a rd e l a u n a yt r i a n g u l a t i o nm e t h o d sa r ei n t r o d u c e da n dc o m p a r e dt h r o u g h s e v e r a li n s t a l l c e s i nv i e wo ft h em e s hi sn o tt o p - q u a l i t ya f t e rr e - t r i a n g u l a t e d , e d g e e x c h a n g ea n de d g ee n e r g yo p t i m i z a t i o na st h em e s ho p t i m i z a t i o nm e t h o d sa r ep r o p o s e d m e a n t i m e ，m e s hv e r t i c e sa r em a p p e df r o m2 dt o3 db yu s i n gb a r y e e n t c rc o o r d i n a t e sa n d d i s p e r s i v ep ；i t i 舢a 地s e w e dt om a n i k i nb yu s i n gi n f o r m a t i o no fs h a r e db o u n d a r yl i n e a m o n gm e s h e s t h ee n t i r ep r o c e s sf l o wi ss i m p l e , e f f e c t i v ea n de a s yt oi m p l e m e n t i ta l s o g u a r a n t e e st h ea c c u r a c yo f s e w i n gr c s u l l 。、 浙江大掌硕士掌位论文 a b s t r a c t b a s e d0 1 1t b ea b o v e 溉a l - c h , l o o k s t a i l o r xs y s t e m 盎卸i si n 打o d u c e di nc t m p t e r5 b r i e fi n t r o d u c t i o no nd e v e l o p m e n te n v i r o n m e n to f t h i ss y s t e ma n dd e t a i l e dd e s c r i p t i o n0 1 1 a p p l i c a t i o no f t h e a b o v er e s e a r c h ul o o k s t a i l o r xs y s t e mr r ep r o v i d e da sw e l l f i n a y , c 蛔p t e r6i n c l 眦t e sas u m m a r yo ft h ea u t h o r sr e s e a r c ha n dt h ep r o s p e c t s ， s e p a r a t e l yf r o mt h ep e r s p e c t i v e so f t e c h n o l o g ya n da p p l i c a t i o n , o f t h i sp r o j e c t k e y w o r d s ：c r a r m e n tc a d ，r e g i o ns e a r c h i n g ，b o u n d a r sb u i l d i n g , d e l a u n a yl r i a n g u l a t i o n , m e s ho p t i m i z a t i o n , p a t t e r ns e w i n g m 糌j 坐啦百峥明 9 9 9 7 8 0 本人声明所呈交的学位论文是本人在导师指导下进行的研究工作及取得的研究成 果。据我所知，除了文中特别加以标注和致谢的地方外，论文中不包含其他人已经发表 或撰写过的研究成果，也不包含为获得逝鎏盘堂或其他教育机构的学位或证书而使 用过的材料。与我一同工作的同志对本研究所做的任何贡献均已在论文中作了明确的说 明并表示谢意。 学位论文作者签名： 私产 签字日期：妒易年弓月f 日 学位论文版权使用授权书 本学位论文作者完全了解迸望盘茎有关保留、使用学位论文的规定，有权保 留并向国家有关部门或机构送交论文的复印件和磁盘，允许论文被查阅和借阅。本人授 权盘鎏盘茎可以将学位论文的全部或部分内容编入有关数据库进行检索，可以采用影 印、缩印或扫描等复制手段保存、汇编学位论文。 ( 保密的学位论文在解密后适用本授权书) 学位论文作者签名：导师签名： 闭砧 签字日期：1 唧6 年弓月1 日 签字日期：7 珊b 年弓月1 日 学位论文作者毕业后去向： 工作单位： 通讯地址： 电话： 邮编： 浙江大掌硕士掌位论文 第一章绪论 第1 章绪论 【摘要】介绍论文的研究背景扣意义；对服装c a d 系统相关技术的研究现状进 行介绍；指出服装c a d 中存在的一些问题和不足：阐述本文的研究思路与总体结构 1 1 引言 近年来，计算机辅助设计( c o m p u t e r a i d e dd e s i g n ，简称c a d ) 技术在服装行业 的应用十分广泛，自c a d 技术诞生以来，服装加工的生产效率和产品质量得到了大 幅度的提高。为了适应服装生产模式向“多品种、小批量、高质量、快交货”方向的 发展趋势，服装产业的竞争已逐步转变成资本和高科技的竞纠u 。因此对市场的快速 反应，对产品优质、廉价地制造将是2 l 世纪服装市场竞争的焦点。这种生产需求所 产生的原动力推动了服装c a d ( c o m p u t e r a i d e dg a r m e n td e s i g n ，简称g c a d ) 技术 的迅速发展，在服装行业的现代化进程中起到了重要的作用。 平面裁剪本身是以公式计算为主，其立体效果往往缺乏有效的控制。现代服装设 计既需要满足美学要求，穿着舒适合身，又需要符合加工工艺，加强服装设计与人体 表面特征的联系。而由平面裁剪发展到立体裁剪是解决上述问题的有效措施，这就使 得服装的立体裁剪日益被重视起来翻。立体裁剪即指设计师在人台模型上利用布料直 接进行服装的构思与设计，这种裁剪的方法是完全基于人台模型来进行的，服装款式 设计与裁片的结构设计相互衔接，利用立体裁剪获得平面裁片图并加工制作的服装更 能适合人体。由于立体裁剪所具有的这一显著优越性，使得基于立体裁剪来研制和开 发三维服装c a d 系统成为当前主要发展趋势闭。 在服装电子商务方面，随着计算机网络的发展，用户可以将自己的三维人体数据 传输给厂商，厂商根据客户的要求及体型设计出款式及版型，并模拟服装穿着效果【4 1 。 这种方式与人们传统的服装购物过程很相似。而日前电子商务平台不能为用户提供试 穿的功能，因此用户对服装的整体着装效果缺乏直观感受。可以看出，将二维裁片缝 合在人体上，展现服装的真实效果对促进服装电子商务的发展具有重大意义 因此，如何利用计算机图形学和服装几何学最新技术，建立三维服装模型，支持 三维裁剪和二维裁片缝合技术，已成为当前的研究热点之，这也正是本文所要探讨 的问题。 浙江大掌硕士掌位论文第一章绪论 1 2 研究现状 纵观服装设计的发展，三维立体服装设计的思路与方法在直观性、合体性、真实 感等诸多方面显现出明显的优势，已经成为服装设计的发展方向之一目前的三维服 装c a d 系统包括三维人体测量与人体模型建立、三维服装设计、服装真实感模拟与 动画演示、三维裁剪与展开等技术1 5 1 1 6 1 ，囊括了多学科领域的知识和方法。理想的 g - c a d 系统应包括的功能模块如图1 1 所示。 里i ig c a d 系统的功能与结构阿 国际上最早出现的c - c a d 系统是美国于1 9 7 2 年研制的m a r c o n 系统。在此基 础上，美国g e r b e r i n 公司、加拿大p a d 系统嘲，法国l e c t r a 公司【9 】，西班牙i n v e s t r o n i c a 公司【姗，日本t o r a y 公司【l l 】等企业先后研制出一系列g c a d 产品并推向国际市场 国内虽起步较晚，但从8 0 年代中期开始，至今也已开发出不少g c a d 系统，如：杭 州“爱科”、浙江大学“智能服装c a d 设计及面料设计系统”、杭州衣尚数码的 “l o o k s t a i l o r x ”等等。这些系统各具特色，既有二维服装c a d 系统，也涵盖了三维 服装c a d 系统。 在三维服装c a d 技术方面，国内外学者进行了深入的研究。瑞士的t h a l m a n n 等领导的m i r a l a b t l 习研究小组、英国的bkh i n d s 和jm c c a r t n e y 1 3 1 1 4 1 、日本的h 2 浙江大掌硕士学位论文第一章绪论 o l m b e 、hi m a o k a l ”】都分别提出了各自的三维服装设计技术，并在3 dg c a d 系统中 得到了实际应用。 现阶段影响三维服装c a d 技术发展的关键问题之一是如何应用计算机实现服装 曲面的几何造型及其在平面上的展开，因此，许多研究人员关于可展面的构造以及曲 面的展开方面的研究也属于可以借鉴的范畴。在服装可展曲面的构造方面，研究人员 提出了一些方法【1 6 】【1 7 1 【1 8 】【1 9 】【2 们。这些方法大致可分为两类，其一是按照给出的边界条 件构造出可展面片，其二是将原本非可展曲面改造成为可展曲面。曲面展开 ( f l a t t e n i n g ) 问题，一直是c - c a d 研究领域的一大热点，评价曲面的展开效果主要 通过曲面几何属性的变形来判断，因此曲面展开算法都围绕解决一个或多个几何变量 组合的变形最小化问题展开。在不同的应用领域，众多学者提出了不同的曲面展开算 法口1 】阱】嘲阱】删。这些算法大致划分为平面参数化方法和几何展平法两类。 同时，基于物理的几何造型方法也被广泛地用于对服装材料的造型与仿真当中， 针对这问题不少研究人员进行了深入的研究，并提出了许多不同的算法 2 5 1 1 2 6 2 7 2 8 2 9 。基于物理的技术需要考虑的因素比较多，以织物的物理性质为例，由 于缺乏有效的测量手段，参数值的确定成为困难之一。另外许多学者对在服装载片二 维- - 维映射问题做了很多工作，其思路包括纯几何的映射方法【涠、基于缝合力裁片 自动变形方法即】、裁片与曲面之间的几何对应关系方法【3 l 】、基于有限元方法口2 】、弹 簧质点变形模型的映射方法 5 8 1 等等。 可以看出，经过各国研究人员的努力，三维服装c a d 相关技术已经初具雏形。 无论是服装几何造型、可展曲面的构造和展开方法的研究，还是服装材料仿真、服装 载片二维仨维映射等问题都得到了深入的研究。当前技术背景下，能否探索一种更 符合服装设计要求三维服装c a d 系统框架，研究服装的三维裁剪以及更为完善的二 维裁片缝合流程成为三维服装c a d 技术中需要重点解决的研究课题。 t 3 研究思路 根据服装设计的全过程，本文构建了如图1 2 所示的g c a d 系统服装设计工作流 程图，图中展现了g c a d 系统服装设计的主要研究内容，并指出了a ，b ，c 三种传 统服装设计途径。各途径的差别在于得到最终2 d 裁片的过程中所采取的方法不同： a 途径不经过3 i ) 效果仿真与设计，直接得到最终裁片，属计算机辅助2 1 ) 服装设计； b 、c 途径属3 d 服装设计，其中b 途径由一套初始2 d 裁片，映射到3 d 人体模型上， 再对其“缝合”而得到最终裁片，而c 途径不经2 d 裁片设计，直接进行结构设计， 然后经过裁剪和展开得到最终裁片。 3 浙江大国明瘦士掌位论文 第一章绪论 a2 d 服装设计 图1 2g c a d 系统服装设计沉程 以上三种传统流程都有其固有的缺点，本文构建了新流程d ，使得服装设计流程 更为合理。服装设计师从3 d 人台测量与建模出发，经过3 d 服装初始化和变形后， 在3 d 服装模型上切割和展开得到2 d 裁片；2 d 裁片经过必要的修正后缝合成3 d 衣 服，如果符合设计师的要求则把修正后的裁片作为最终的裁片送到工厂加工，否则继 续修正，直到获得满意的效果。新设计流程从3 d 出发而后又通过3 d 一2 d 一3 d 的过 程验证了设计的好坏与否，更重要的是它增强了用户与o c a d 系统的交互能力，使 得用户在每个阶段都有可能对最终的结果旌加必要的影响。 本文正要研究新设计流程中的两个部分，其一是三维服装裁剪，这一部分主要介 绍切割区域搜索的方法；其二是二维裁片缝合，这一部分主要介绍裁片缝合的框架和 流程。为了实现这两个功能模块主要的思路有以下几点： 1 曲面切割区域自动搜索 依托前人所做的工作，研究具有特殊切割线的曲面区域自动搜索算法，比如桥边 和省道。通过复制桥边、省道与基域三角形曲面片的交点，在基域切割过程中利用相 邻三角形内共享网格边上交点的连续性来区分原线段上的交点和复制交点，最终完成 对基域的切割这种算法对曲面切割线中的桥边和省道搜索更加智能，适合特殊、复 杂的服装玩具等产品设计领域。 2 展开裁片边界生成和缝合信息获取 现存的展开算法中，几何展平法能很好的处理拓扑结构复杂曲面。采用几何展平 法展开的初始展开的曲面片没有包含边界信息，然而在裁片缝合与裁片加工时都需要 边界信息。初步想法是利用三维切割线经过网格顶点的信息构建裁片边界线信息，再 利用三次样条曲线生成裁片最终边界线。在边界生成后利用裁片之间切割线的依存关 系离散裁片边界线，获取离散点集，提取边界线缝合信息，这些信息被作为网格重三 角化和边界对齐的基础。 3 边界约束的二维d e l a 瑚y 三角化 展开后的二维裁片其边界三角形不规整，存在一些狭长的三角形，需要重新 4 浙江大掌硕士掌位论文 第一章绪论 d e l a u n a y 三角化。重三角化必须保持裁片的边界，并且也需要保持裁片可能存在的 “洞”等特征区域。基于平面三角化已经有很成熟的算法，初步设想：先离散出二维 边界点，由这些边界点约束边界，用边界约束的d e i a i i n a y 三角化算法得到初始的网 格，然后在初始网格的基础上进一步细化：可以尝试中点剖分算法，也可尝试顶点插 入算法来细化网格。 4 三角网格优化 d e l a 哪y 三角化后的网格形状并没有达到最优，需要调整的网格边长度和优化每 个顶点连接网格边的数目。因为网格采用弹簧一质点模型，多次弹簧能量均衡迭代能 使网格边趋向一致；利用边交换算法能改善顶点与网格边的邻接关系，使得每个内部 的三角形趋向与正三角形而达到优化目的。 5 裁片网格顶点映射和边界对齐 重三角化后的网格顶点只带有二维平面域的信息，需要把它映射到三维空间域 上，以获得网格在三维空间的确切位置，完成服装的缝合。根据拓扑不变性原则，可 以利用三角形重心坐标与顶点坐标之间的关系求出裁片网格顶点的三维位置。具有共 享边界线的裁片在缝合时需要把由共享边界线离散出的顶点缝合在一起，然而由于展 开算法和边界拟合算法有一定的误差，裁片边界之间并不能完全对应。现在可以由缝 合点集信息出发，完成裁片之间共享边界的对齐，让所有对应的边界线达到几何上的 等同但又不明显的改变裁片边界形状位置。 t 4 研究内容 根据图1 2 所构建的g c a d 系统和的新设计流程，结合本文所要研究的内容，拟 从以下几个方面进行研究，第二章至第六章的内容说明如下： 第二章简单介绍三维裁剪，主要介绍切割区域搜索算法。在给出切割线类型定义 的基础上，探讨切割区域的自动搜索等问题，并给出带桥边、省道特殊切割线区域自 动搜索的算法。 第三章从曲面的可展性出发，简要介绍曲面展开的方法。利用几何展平方法对上 一章提到的切割区域展开，给出二维裁片边界生成的方法。并确立裁片与裁片之间切 割线的依存关系，离散裁片边界线，提取缝合信息，这将作为裁片缝合的基础。 第四章主要介绍二维裁片的缝合的框架和流程。首先介绍常用d e l a l l n a ：y 兰角化 算法并给出实例比较各种算法的优劣，利用上一章中确定裁片边界离散点的数目和位 置，对裁片进行三角剖分，并针对剖分后裁片的网格进行优化。然后把优化后裁片网 格顶点的= 维坐标映射到三维坐标上，在裁片之间的网格顶点边界对齐后把所有裁片 5 浙江大掌硕士学位论文第一章绪论 缝合到三维人体上。 。 第五章介绍l o o k s t a i l o r x 系统框架，并对系统开发环境作简要介绍，同时详细介 绍了上述研究工作在该系统中的应用。 第六章为上述五章的总结及未来展望，总结本文的研究工作，并对项目课题研究 的发展前景从技术上和应用上作了展望。 8 浙江大学硕士掌位论文 第二章切割区域自动搜索 第2 章切割区域自动搜索 【摘要l 本文的研究以服装，玩具等产品的3 d 设计为背景为了得到缝制这些 模型所需要的材料形状，通常需要将模型曲面切割成多个曲面片，并展开到二维平面 上本章主要介绍模型曲面切割和切割后区域的自动搜索 曲面切割广泛应用于曲面造型、图形编辑、医疗虚拟手术等领域。曲面切割算法 通常可以归结为两类：视觉切割与几何切割。在视觉切割中，切割实体在几何上没有 被切除，只是在视觉上做了消影处理。相反，几何切割则是割裂了实体的几何联系， 赋予被切割面新的几何描述。在产品设计等领域，几何切割法应用较广泛。然而几何 切割法中只有少量的曲面可以通过解析求解两相交曲面来获取切割边界，而且实现起 来往往也比较困难，因而必须借助于高效的数值方法。 曲面切割对曲面三维到二维的展开有重要的意义。对封闭曲面而言，切割是曲面 得以展开的必要步骤。对于曲面可展程度不高的曲面，为了得到变形能较小的展开结 果，对曲面进行切割也是必不可少的处理过程。因此曲面切割在许多领域有极其重要 的应用。在产品设计等领域，构造可展曲面时，通常采用切割后的局部曲面拼接来解 决曲面的可展化问题，以降低曲面展开结果的变形程度，比如服装就是由众多小裁片 缝制而成。在曲面建模中，曲面切割是构造不规则边界曲面的重要手段在虚拟手术 中，曲面切割将重新网格化肌体以模拟真实的手术情况。在不同的应用领域，曲面切 割处理方式也不尽相同，现有的曲面切割算法大致可以分为以下两类： 丸自然成形类：以曲面之间的交线为切割边界 在曲面造型过程中，当两曲面相交时，通常需要将交线转化为网格边，并在交线 上重新网格化曲面。这类算法在曲面的布尔操作和曲面交互造型中有着重要的应用 【3 3 】口4 】嗍 b 人工绘制类：以交互绘制在曲面上的切割线为切割边界 切割线的映射过程如下：首先，计算切割曲线与曲面网格边的交点；其次，将切 割曲线转化为曲面的切割网格边；最后，将每条切割网格边转化成两条重合的网格边， 重新三角化被切割的三角形，新生成的网格曲面在切割线上不存在拓扑连续性。在这 类切割算法中，切割线既可以是开曲线也可以是闭曲线，如果是闭曲线，通常只考虑 简单的单连通区域。这种算法在手术模型中有着大量的应用【3 6 | 3 7 1 1 3 s 1 。类似的算法还 应用于网格曲面拉伸造型中网。 在服装裁剪等领域，设计者往往将多个曲面片的切割边界同时绘制在曲面上，然 后逐个切割曲面片快速的提取出待切割曲面片的切割边界是提高切割效率的关键因 7 浙江大掌硕士学位论文第二章切割区域自动搜索 素之一现有的曲面交互切割算法中，切割线或者通过曲面之间的求交运算获取，或 者假定事先已经确定。对于需要经常修改切割线的场合，比如服装、玩具设计等领域 这种方法在处理上存在许多不便之，处。因而有必要提出一种操作更加简便迅速，处理 过程更为智能的曲面交互切割算法。 已有的曲面交互切割算法中存在一些问题。首先，现存算法中的切割线类型单一， 为了更灵活的切割曲面，有必要提供更多类型的切割线。其次，由于操作习惯，设计 者往往一次将多个曲面片的切割线绘制在模型表面上，然后逐个选取曲面片做裁剪处 理。因此，这对区域的自动搜索提出了较高的要求。l i 等人【柏】给出的基于区域自动 搜索的三角化网格曲面切割算法，很好的解决了上述问题，在服装、玩具等产品设计 领域中有实用的价值。该算法中，曲面片的边界由绘制在模型曲面上的切割线组成。 通过在曲面片上拾取一点，算法将自动搜索出构成曲面片边界的封闭切割线环，模型 上与曲面片相关的三角形形成曲面片的基域，以及基域上的桥边和省道；由封闭切割 线环对基域切割可以得到最终的切割结果。算法对桥边和省道只做了初步的偏移复制 处理。在由复杂桥边和省道构成的基域中，由于偏移的误差，最终得到的切割结果跟 理论上的结果相比有较大的偏差 在l i 等人研究的基础上，本章提出了处理桥边和省道的新算法【6 3 】：通过复制桥 边和省道与基域三角形曲面片的交点，在基域切割过程中利用相邻三角形内共享网格 边上交点的连续性来区分原线段上的交点和复制交点，最终完成对基域的切割。 2 1 相关定义 2 1 。1 普通切割线 绘制在模型表面的普通切割线由连续的小线段组成，每条小线段的两个端点位于 同一个三角形内，或者为切割线与网格边的交点，或者为切割线的端点。每条切割线 上存储以下信息： 切割线端点的坐标； 切割线所经过的三角形的m 号； 与切割线相交的网格边d 号，以及交点的坐标； 切割线本身的m 号； 切割线类型； 与其他相交切割线的交点和d 号。 对于带边界的模型曲面，曲面边界也作为普通切割线处理。 对于模型上的网格边，由上述信息，可以方便地找出与其相交的切割线信息。 8 浙江大掌硕士掌位嵌瞄赶第二章切割区域自动搜索 、 2 _ 1 2 切割线环、曲面片、基域 要获取一个封闭切割线环需要获得一条起始切割线。从起始切割线开始，沿着切 割线方向搜索相邻切割线，若下一条相邻切割线为起始切割线且两切割线方向相同则 认为已经搜索到封闭切割线环。通常，在搜索过程中，若发现下一切割线即为起始切 割线，则可以认为搜索结束，但当封闭切割线环上存在2 1 3 小节中所述的桥边时， 搜索切割线环的终止条件需附加上起始切割线的方向与终了切割线的方向相同。 曲面片通过由切割线交织构成的封闭切割线环对模型曲面的切割获取。在模型曲 面上，位于封闭切割线环内部及与封闭切割线环相交的三角形构成曲面片的基域。 2 1 。3 桥边 如果在基域上存在一切割线连接两封闭切割线环，则称这样的切割线为桥边。桥 边并不是一种单独类型的切割线，它是由普通切割线转化而来的。在绘制普通切割线 时并不能确定此切割线会转化为桥边。只有在区域搜索后，根据切割线与切割线环之 间的关系才能决定是否把当前切割线类型转化为桥边。在本次区域搜索过程中被指定 为桥边的切割线不一定在下一次区域搜索过程中也被指定为桥边。 一条桥边将两个封闭的切割线环合并成一个封闭的切割线环。如图2 1 ( a ) ，连接 圆台上底面封闭切割线环与下底面封闭切割线环的切割线即为一条桥边。图2 1 ( b ) 、 ( c ) 分别显示了在桥边作用下图2 1 ( a ) 的切割和展开结果，在本章中采用文献【4 l 】提到的 算法展开切割曲面。 域固鼎 ( a ) 桥边( b ) 切割结果( c ) 展开结果 图2 1 桥边处理 根据切割线环封闭条件，桥边在封闭切割线环搜索过程中，将被访问两次，图 2 1 ( a ) 中的箭头显示了切割线的搜索过程，图中耶为拾取点。由此，可以将桥边看成 由两条重合的切割线组成。桥边在封闭切割线环搜索以及后续的对基域切割过程中， 将被特殊地处理。 2 1 4 省道 服装裁剪过程中，服装面料近似于锥面的折叠缝合称为省道。在服装等工业设计 中，省道有着重要的应用。省道在平面裁片上呈三角形状，沿着省道边界缝制将使裁 9 浙江犬增幽页士掌位论文第二章切割区域自动搜索 片产生立体的效果，如图2 2 所示。当曲面片在展开结果上存在很大的变形时，通常 需要在曲面高斯曲率较高的部位添加相应的省道。 省道有一些特有的绘制和连接规则。省道不能与省道或普通切割线相交；省道的 每个端点最多只能连接一条省道；省道的两个端点不能同时连接在普通切割线上，既 省道不能作为桥边处理。 作为特殊的切割线，省道与普通的切割线有着不同的标记。在封闭切割线环搜索 和顶点标记过程中，省道将不作为普通切割线处理。待切割曲面上的省道在基域被搜 索出来后，通过检测省道上记录的被切割的三角形是否在基域内部获取。 与对桥边的处理相似，省道在后续的基域切割中也将被特殊处理。 ( a ) 带省道的曲面切割 2 2 普通切割区域自动搜索 ( b ) 展开结果( c ) 缝合结果 图2 2 省道处理 绘制在模型表面的切割线相互连接、交错，给区域的自动搜索增加了难度。尤其 是切割线中存在桥边和省道时，区域的处理更为复杂。本节主要讨论不带桥边和省道 的普通切割区域自动搜索问题，在文献【钟】中已经本节问题做了研究。为了表述的完整 性，本节简要介绍普通切割区域自动搜索的方法，这对带桥边和省道的特殊切割区域 自动搜索具有指导意义。 2 2 1 切割线环获取 普通切割线与处理 首先，如果一条切割线与其它切割线存在交点，则在交点将切割线打断成相应的 两条；其次，一条切割线的端点与其它切割线之间不存在相邻关系，则在基域搜索和 切割过程中忽略该切割线；最后，建立切割线之间的邻接关系。如图2 3 所示，如果 在模型表面上绘制如图2 3 ( a ) 所示的切割线，则在经过上述处理后将得到如图2 3 0 ) 所示的切割线。通过预处理，每条切割线在端点上与其它切割线相邻，使得在切割过 程中，从一条切割线开始可以找出包含该切割的一个封闭切割线环 1 0 浙江大掌硕士掌位论文第二章切割区域自动搜索 ( a ) 模型表面上绘制的切割线( b ) 处理后的切割线 图2 , 3 切割线在曲面切割过程中的处理 起始切割线获取 要获取一个封闭切割线环，首先需要获取该切割线环上的一条切割线，称这样的 切割线为起始切割线。在切割过程中，当在曲面上拾取一点p o ，则起始切割线通过以 下算法获取： 1 得到包含即的三角形幻； 2 t o 与切割线相交，如图2 4 ( a ) ，从p o 分别向t o 的三个顶点引辅助线，直到得 到一条与切割线相交的辅助线( 工l ，如表示切割线) 。若存在这样的辅助线，则计算 该辅助线与所有与之相交的切割线的交点，选择交点与朋最接近的切割线为起始切 割线；若不存在这样的辅助线，如图2 4 所示，在t o 上任取一条与切割线相交的网 格边句以及e i 上的一顶点畸。在所有与白相交的切割线中，选取交点与吁最近的一条 为起始切割线。 3 t o 不与切割线相交，如图2 4 ( c ) 所示。则取t o 上的一网格顶点为起始点，通过 广度优先的方法 4 0 l 搜索相邻网格边，直到找到一条与切割线相交的网格边，设该网格 边为即e ，上相应的搜索顶点为崎，在与e l 相交的所有切割线中，选取一条交点与吁 最近的切割线为始切割线。 凌。醯啦 ( a ) 辅助线与切割线相交( ”辅助线不与切割线相交( c ) 三角形不与切割线相交 圈2 4 切割线在曲面切割过程中的处理 切割线环搜索 在曲面片搜索过程中，每条与曲面片相关的切割线均赋予相应的方向，令外部切 割线环以逆时针为正方向，内部环以顺时针为正方向，也即当我们沿着切割线方向走 时，被切割曲面片始终在左手边。由此，当确定了一条切割线厶的方向后，则可得 到与上，相交的网格边上的顶点崎在曲面片内部的必要条件：吩必须在厶的左边同 时，若已确定一个网格顶点在曲面片的内部，则可以通过该条件来判断切割线的方向。 、 在封闭切割线环搜索过程中，若当前切割线厶在其端点飓上与多条切割线相邻， 浙江大掌硕士掌位葭誓赶第二章切割区域自动搜索 则在叼上选取与厶左侧有最小夹角的相邻切割线为封闭切割线环的下一条切割线 如图2 5 所示，厶是当前切割线，如，厶，厶为工i 末端连接的切割线，根据连接点 所在三角形的法向量隶得这些切割线与l l 的夹角，厶与厶形成的夹角最乏卜，因而选 取厶为切割线环上的下一条切割线。 图2 5 切割线环上下一条切割线的确定 从起始切割线开始，沿着切割线方向搜索相邻切割线，若最后能回到起始切割线 且两次搜索中割线方向相同则可认为封闭切割线环已经找到。 通常，在搜索过程中，若发现下一切割线即为起始切割线，则可以认为搜索结束， 但当封闭切割线环上存在2 1 3 小节中所述的桥边时，搜索切割线环的终止条件需附 加上起始切割线的方向与终了切割线的方向相同。 2 2 2 切割线环上网格顶点标记 在曲面切割多边形获取过程中，需要对网格顶点与切割线环的关系做出判定。通 常，这种位置关系可以用网格顶点相对于切割线环的内外关系来描述。 对于每条与封闭切割线环相交的网格边e ， a ) 如果e t 与切割线之间只有一个交点，则相对于交点位置，将e ，的两顶点分为 外部顶点，标记为“1 ”和内部顶点，标记为“l ”。如图2 6 所示，将1 ，l 、 屹分别标记为“1 ”、“1 ”。 b ) 如果网格边与封闭切割线环之间存在多个交点，在切割线环上与网格边相交 的切割线中，分别找出交点与网格边的两端点有着最近距离的切割线。若网 格边上的顶点在相应的切割线的右边，则该顶点为外部顶点，标记为“一l ”； 网格边上的顶点在相应的切割线的左边，且不存在其它切割线与该顶点到相 应交点之间的线段相交，则设置该顶点为内部顶点，标记为“l ”。如图2 6 所示，网格边v l v ，的两顶点分别位于封闭切割线环风的右边，将v l 、i ，3 分别 标记为“1 ”。 1 2 浙江大学硕士掌位铽誓第二章切割区域自动搜索 圈2 6 网格项点内外标记 2 2 3 切割区域搜索算法描述 通过以上几个步骤的介绍，现在给出具体的普通切割区域搜索算法： s t 印1 初始化模型上所有网格顶点标记为“0 ”，访问标记为“蜘s e ”；初始化所 有切割线的访问标记为“僦”； s t e p 2 在曲面片上拾取一点，获取起始切割线岛，并令上0 为当前切割线厶； s t e p 3 以厶为起始切割线，获取封闭切割线环鼠，令展上切割线的访问标记为 “们” 。 s t e p 4 标记与风相交的两格边上的顶点； s t e p 5 搜索其它切割线环 对每条与及相交的网格边白，检测其两端点。若存在标记为“0 ”的端点1 ，表 示还存在其它未访问的切割线环与白有交点，则从所有己访问过的与e l 存在交点的切 割线中，找出与v 最近的交点，设交点为p ，在所有未访问过的切割线中，找出与啊 存在交点，且交点到p 距离最近的切割线，令此切割线为厶跳转s t y 3 。 s t y 6 标记内部网格顶点 利用“广度优先”算法【柏】，检测所有与标记为“1 ”的网格顶点相邻的网格边。 设当前处理的网格顶点为v i ，与之相邻的一条网格边为e j ，白上的另一个顶点为 a 若的标记为。0 ”，如果自不与任何切割线相交，则瞻为一内部顶点，标记 为“1 ”；否则，在所有与白相交且访问标记为“白l s e ”的切割线中，选取与 e t 交点到v l 距离最近的切割线为厶，跳转戳印3 ； b 若h 的标记为“1 ”，若岛与封闭切割线环相交( 如图2 6 中，网格边v 6 v 7 相 对于切割线环岛) ，在所有与e j 相交且访问标记为“僦”的切割线中，选 取与毋的交点到砖最近的切割线为厶，跳转s t y 3 。 2 2 4 切割区域内部多边形获取与三角化 一 相对于构成曲面片边界的封闭切割线环，可将基域上的三角形分成两种类型： ( 1 ) 与切割线环相交的三角形；( 2 ) 不与切割线环相交的三角形前者只有一部分 1 3 浙江大国明页士学位论文第二章切割区域自动搜索 属于曲面片，称为基域的边界三角形；后者则完全在曲面片内，称为基域的内部三角 形。要获取曲面片，首先需提取基域边界三角形在曲面片内的部分，并以多边形形式 存储；然后三角化这些多边形，新生成的三角形和基域的内部三角形构成了最终的曲 面片。切割线在基域边界三角形上的端点和交点构成新生成的三角形的顶点。因而在 曲面切割之前，对这些切割线的端点及交点赋予新网格顶点i d ：然后对基域的边界 三角形逐个处理： s t 印1 初始化三角形的顶点以及在此三角形上切割线的端点、交点的访问标志为 “伽s e ”： s