（管理科学与工程专业论文）鞋底设计与优化排样系统的研究与实现.pdf

浙江_ t 业大学硕上学位论文 鞋底殴计与优化 ； | ：样系统的研究与实现 鞋底设计与优化排样系统的研究与实现 摘要 制鞋业是我国的一项传统产业，鞋类产量已经连续六年位居世界 首位。由于中国制鞋企业的信息化程度大多不高，造成制鞋企业生产 效率低下，设计水平不高，因此在国际市场上难以与发达国家相抗衡。 在当今国际化大环境下加快制鞋业信息化，才能增强我国制鞋业的国 际竞争力。目前制鞋c a d 技术，已经成为制鞋业信息化的核心部分。 制鞋c a d 设计系统是由鞋帮、鞋底设计，鞋楦2 d 3 d 设计，鞋样缩 放，优化排样、数控加工等部分组成。本文研究的主要内容是制鞋 c a d 设计系统中的鞋底设计和优化排样系统两个部分。 在鞋底的款式设计中，大多数款式的鞋底上要进行图案填充。传 统的区域填充算法包括扫描线算法、种子填充算法等，但是这些算法 要与区域轮廓进行求交运算，当轮廓为不规则曲线构成时，则使得计 算的复杂度增加。对此问题，在基于可行域方法的基础上，本文给出 了种基于可行域的图案填充方法，降低了几何复杂性对图案填充的 影响，能够处理任意形状区域内的填充。此外本文根据鞋底设计的买 际需求，在鞋底设计系统中提供了集成的绘图功能。 鞋样优化排样问题属于n p 完全问题。在以往优化排样的计算求 解方案中，人们般将优化模型的建立基于将板材当作无限长的条状 材料或将有限长宽的板料裁成若干条等宽的条状材料来处理。当将有 限长、宽的整体板料在冲压设备上进行双向送料冲裁时，上述优化模 浙江工业大学硕二 学位论文鞋底设计与优化排样系统的研究与实现 型将不适用。对此，在改进的多边形顶点算法的基础上，本文提出一 种二维优化自动排样算法，并以排样方式中最典型的对头双排为例分 析板材二维排样的整体优化问题，以在有限长、宽的整体板料上所能 冲裁出最大零件个数为目标，对鞋样二维排样的优化模型及相应的算 法进行研究。另外本文给出了制鞋c a d 设计系统中的数据管理模块， 该功能有效的提高了设计效率，缩短了设计周期。 本文在v c + 十和o p e n g l 环境下，实现了鞋底设计与优化排样系 统，在优化排样系统中计算出普通单排、对头单排、普通双排和对头 双排四种排样方式各自的结果，与传统手工的排样方法相比，缩短了 排样时间。 关键词：鞋样，c a d ，填充，优化排样 i l 浙江工业人学硕士学位论文鞋底设计与优化排样系统的研究与实现 d e v e l o p m e n to fs o l ed e s i g n l n g a n do p t l m a ll a y o u ts y s t e m a b s t r a c t t h es h o e m a k i n gi n d u s t r yi sat r a d i t i o n a l i n d u s t r yi no u rc o u n t r y t h eo u t p u to fs h o e so fc h i n ai st h em o s ti nt h ew o r l dd u r i n gp a s s e ds i x y e a r s b u tb e c a u s eo fl o wi n f o r m a t i o nl e v e l ，t h ee f f i c i e n c ya n dd e s i g n l e v e lo fo u rs h o e m a k i n g e n t e r p r i s e sa r ev e r yl o w , s ot h e yc a nn o tc o m p e t e w i t ht h e e n t e r p r i s e s i n d e v e l o p e d c o u n t r i e s u n d e r g l o b a l i n t e r n a t i o n a l i z a t i o nc i r c u m s t a n c e ，s h o e m a k i n gi n d u s t r ys h o u l di m p r o 、，e i n f o r m a t i o n a ll e v e ls ot h a ti t se f f i c i e n c ya n dd e s i g nl e v e lc a nb ei n c r e a s e d s h o ec a d s y s t e mh a v eb e e nt h ek e yp a r to fs h o e m a k i n gi n f o r m a t i o n a w h o l es h o ec a di n c l u d eu p p e r 、s o l ed e s i g na n d2 d 3 dd e s i g no fs h o e l a s t ；u p p e rp a t t e r n sd e s i g n ；o p t i m u ml a y o u t ；n cm a c h i n i n g t h er e s e a r c h c o n t e n to f t h i sa r t i c l ei ss o l ed e s i g na n do p t i m u ml a y o u to f t h es h o ec a d s y s t e m w h e nd e s i g np a t t e r no fs o l e ，a l m o s ts o l es h o u l df i l l p a t t e m t h e t r a d i t i o n a la l g o r i t h mi n c l u d e ds c a nl i n e a l g o r i t h ma n ds e e df i l l i n g a l g o r i t h m ，b u tt h e s ea l g o r i t h mw i l lc o m p u t ei n t e r s e c t i o nw i t ht h ee d g eo f t h er e g i o n t h er e g i o n se d g ec o m p o s e dw i t ht h ei r r e g u l a rl i n et h a t j l l l c a u s eh i g hl e v e lc o m p u t ec o m p l e x i t y f o rt h i sp r o b l e m ，o nt h eb a s eo f t h e f e a s i b l ea r e a ，t h i sa r t i c l eb r i n g sf o r w a r da na l g o r i t h mo ff i l l i n gp a t t e r n l l i 浙江工业大学硕十学位论文 鞋底设计与优化排样系统的研究与实现 b a s e df e a s i b l ea r e a t h i sa l g o r i t h mc u td o w nt h ee f f e c to fg e o m e t r y c o m p l e x i t y t o p a t t e r nf i l l i n g a n dc a nb eu s e dt of i l l a n yr e g i o n f u r t h e r m o r e ，a c c o r d i n gt ot h es o l ed e s i g nn e e d ，t h i sa r t i c l eo f f e rd r a w i n g f u n c t i o na s s e m b l yi nt h es h o ec a d s y s t e m t h e2 do p t i m u m l a y o u to ft h ep a t t e mi sn p cp r o b l e mt h a tp o s s e s s h i g hd e g r e ec o m p u t ec o m p l e x i t y f o ral o n gt i m e ，t h i sp r o b l e ma l w a y si s t h eh o tp r o b l e mi na u t o m a t i o nf i e l d a tf o r m e ra r t i c l eo f o p t i m u ml a y o u t ， o p t i m u mm o d e lf o u n d e do nt h ei n f i n i t el o n gp l a n km a t e r i a lo rp a r t i t i o n t h ep l a n ki n t oe q u a lw i d t hp l a n k b u tt h i sm o d e ld o e s n tf i tt od o u b l e d i r e c t i o nc u to f t h el i m i t e dl o n ga n dl i m i t e dw i d t h p l a n k f o rt h ep r o b l e m ， t h i s a r t i c l eb r i n g sf o r w a r dt oa nw h o l eo p t i m u ml a y o u ta l g o r i t h mb a s e d o nt h ei m p r o v e dp o l y g o nt o pa l g o r i t h m a n da n a l y z eo p t i m u ml a y o u t p r o b l e mo f w h o l eo p t i m u mw i t hd o u b l eo p p o s i t el a y o u ta sa e x a m p l e f o r t h ep u r p o s eo fm a xn u m b e ro fc u t t i n gp a t t e r n ，g i v et h eo p t i m u ml a y o u t m o d e lo ft h ep a t t e r na n dc o r r e s p o n da l g o r i t h m b e s i d e st h i s ，t h i sa r t i c l e i n t r o d u c e sd a t am a n a g e f u n c t i o n ，t h i sf u n c t i o n i m p r o v et h ed e s i g n e f f i c i e n c y , i n d u c et h ep e r i o do fd e s i g n t h ea r t i c l er e a l i z e st h e s er e s e a r c h e si nt h es h o ec a d s y s t e mt h a t c e r t i f i c a t et h ea b o v ea l g o r i t h m a n do p t i m a ll a y o u ts y s t e mh a v es i n g l e r o w 、d o u b l er o w 、p a i r - w i s es i n g l er o w l a y o u ta n dp a i r - w i s ed o u b l er o w l a y o u tt y p e st os a t i s f yv a r i o u sn e e d k e yw o r s ：s h o e s p a t t e r n ，c a d ，f i l l i n g ，o p t i m a ll a y o u t 学位论文原创性声明 本人郑重声明：所提交的学位论文是本人在导师的指导下，独立进行 研究工作所取得的研究成果。除文中已经加以标注引用的内容外，本论文 不包含其他个人或集体已经发表或撰写过的研究成果，也不含为获得浙 江工业大学或其它教育机构的学位证书而使用过的材料。对本文的研究作 出重要贡献的个人和集体，均已在文中以明确方式标明。本人承担本声明 的法律责任。 作者签名 巧班 日期：“年月多日 学位论文版权使用授权书 本学位论文作者完全了解学校有关保留、使用学位论文的规定，同意 学校保留并向国家有关部门或机构送交论文的复印件和电子版，允许论文 被查阅和借阅。本人授权浙江工业大学可以将本学位论文的全部或部分内 容编入有关数据库进行检索，可以采用影印、缩印或扫描等复制手段保存 和汇编本学位论文。 本学位论文属于 1 、保密口，在年解密后适用本授权书。 2 、不保密口。 ( 请在以上相应方框内打“”) 作者签名：了携 刷磁轹如c ； 日期：州年f月6 日 ， ， 日期：立o 萨r 月6 日 浙江工业火学硕十学位论文鞋底设计与优化排样系统的研究与实现 1 1 研究背景 第一章绪论 我国的制鞋产业具有悠久的历史，鞋业市场是一个巨大而且稳定的市场。据 统计，去年我国制鞋企业生产约了7 0 亿双鞋，其世界市场份额超过6 0 “3 。全 球鞋类年产量大约1 2 0 亿双。由中国生产的鞋类约有4 0 进入国际贸易市场，贸 易额达3 0 0 亿美元，约占全球鞋类贸易中的2 5 。但是，据我国海关统计，2 0 0 5 年卜3 月，我国赣类产品出口1 6 6 亿双，金额4 0 9 亿美元。其中成品鞋1 6 3 亿双，金额3 9 6 亿美元“1 。粗略算一下，出口鞋的价格约在每双2 5 美元左右， 即使换汇最高的皮鞋平均也才6 美元多，这个价钱是意大利鞋价的1 3 ，台湾鞋 价的一半。形成这种巨大差异的主要因素在于中国鞋业缺乏强大的、高水平的产 品设计开发能力，制鞋工业信息化水平低下，目前还处在- - 干中力n t - 贸易型的工业 发展阶段，靠廉价的劳动力、产量和规模获取效益，只注意一般意义上的产品质 量，鞋类产品在款式和质量上都不及国外，价格无法提升。当今时代，制鞋企业 生产的鞋样款式缺乏创新设计，仅靠价廉是很难长久占领市场的。产品的设计与 开发已成为我国制鞋工业再次腾飞的关键。1 。 传统的手工设计由于效率低下，设计周期长，对设计人员的素质要求高，圜 此很难适应制鞋行业的发展要求。国外( 例如意大利) 虽然已经推出制鞋设计专 业软件，但这些专业软件价格昂贵，很难为国内厂家所接受。市场上的a u t o c ：l d 和c o r e d r a w 等软件，虽然也可以用来设计鞋样，但由于他们是通目 c a d ( c o m p u t e r a i d e d d e s i g n ) 软件，其设计效率比较低。因此，国内多数厂家仍 只好采用手工的方法来设计鞋样。在这样的背景下，研究开发一套实用的制鞋 c a d 软件是非常有必要的。 1 2 研究的目的与意义 由于传统鞋底设计过多的依赖于设计师的经验，且设计成本高、周期长、不 利于修改，严重制约了制鞋行业的发展。在分析了国内中小型制鞋企业的传统手 浙江工业大学珂i - i - ：学位论文鞋底设计与优化排样系统的研究与实现 工做法之后，采用计算机辅助设计和数据库的方法，将信息技术引入到传统的鞋 底设计生产过程中，并准备开发一套适合国内中小型制鞋企业使用的鞋底设计系 统，帮助设计师傅利用计算机就能够方便快速的设计出各种各样的鞋底款式，从 而甩开传统的直尺、圆规等设计工具，使他们能够从传统的、繁琐的、效率低下 的设计过程中解放出来。此外该系统有助于提高我国传统制鞋业的生产、设计水 平，提高国产鞋的质量，提升制鞋行业的自动化程度和市场竞争力。 1 3 国内外研究现状 随着计算机技术的飞速发展和不断进步，其在许多领域辅助设计方面的使用 也越来越受到人们的重视。计算机辅助设计( c a d ) 在不同领域的应用和推广，对 于提高生产效率和缩短设计周期都起到了至关重要的作用。在鞋业款式设计方 面，c a d 技术也得到了有效的利用。制鞋业发达的英国、美国、意大利等国i l 上世纪7 0 年代就开始了制鞋c a d 技术的研究，自1 9 7 6 年欧美第一套制鞋c a d 系统问世，到1 9 8 1 年三家鞋厂采用制鞋c a d 系统，再到1 9 8 6 年五十多家鞋厂 采用，到2 0 0 0 年的时候此类系统在发达国家的普及率几乎达到1 0 0 “3 。相对于 国外，我国制鞋工业存在着机械化、自动化程度偏低的情况。我国大部分中小型 制鞋企业在鞋底的设计和扩缩等重要工序大都凭过往经验和行业通行做法进行 手工作业，信息化水平非常低，从而使得这些企业处于生产成本较高、生产效率 低下、产品缺乏国际竞争力的不利境况，很难适应当今的市场要求。这是因为舀 内的c a d c a m 系统发展跟不上，现在国内的c a d c a m 系统还是停留在初级 阶段。在c a d 辅助设计方面只能够进行简单的平面设计，以及样片缩放。硬件 方面，也没有国外的那么先进，只能切割纸板，还不能进行直接真皮切割。目前 国内只有少数大型制鞋企业曾引进了国外的制鞋c a d c a m 系统，原因是一方 面国外制鞋c a d 系统的进口价格都相当昂贵，另一方面，这些系统操作复杂 国内这方面的汉化没有跟上，相关技术人员又非常缺乏，所以对于规模普遍偏小 的国内制鞋企业来讲很难接受国外制鞋软件。还有些制鞋企业也借助 “p h o t o s h o p 、c o r e d r a w ”等软件进行鞋底设计，但这些是c a d 方面的通用软 件，设计效率低下，不适合制鞋师傅的一些特定需求”“3 。国内技术人员也曾经 在制鞋c a d 技术领域开展过研究，但却没有开发出一套实用的商品化的制鞋设 2 浙江工业大学硕士学位论文鞋底设计与优化排样系统的研究与实现 计软件m 。另外国内几家小型软件公司也开发了一些制鞋软件，如鞋匠铺、制鞋 之星”1 等，但这些软件功能单一，没有涉及鞋底设计，并且系统开放性差，制鞋 工程师很难对缩放后得到的样片进行有效管理。 1 4 本文主要工作 一套完整的鞋业c a d 系统，由鞋帮设计、鞋底、鞋楦设计、鞋样缩放、优 化排样等部分组成“1 。整个制鞋c a d 系统功能主要由四个模块组成。第一个模 块是三维鞋面设计，对鞋楦进行三维曲面重构，将重构曲面展平成二维样片；第 二个模块是平面鞋帮操作，实现对展平后的帮样轮廓的自动扩缩功能，并对样片 进行优化排样；第三个模块是鞋底操作包括鞋底花纹设计、图案填充以及鞋底花 纹的缩放功能。为配合以上模块的使用，系统最后实现了数据管理模块，其中包 括图档管理、系统管理、报表管理三部分功能。 本论文的工作主要体现在以下四个方面： 1 在制鞋c a d 系统中绘制鞋底花纹，为制鞋设计人员提供多种选择，方 便其设计鞋底款式。 2 研究分析了传统的区域填充算法，给出基于可行域的图案填充算法。 3 以常见排样方式中最典型的对头双排为例分析板材二维排样的整体优化 问题，结合余料的利用，建立t - - 维排样整体优化的合理数学模型。利 用改进的多边形顶点普通单排算法，分析计算模型中的未知排样参数， 并给出了与整体优化模型相匹配的整体优化排样算法。 4 数据管理功能的实现。该功能可以使用户方便的查询、添加、删除鞋样 图档以及相关的信息。 浙江t 业大学碗量学位论立 鞋底设计与优化排样系统的研究与实现 第二章总体框架设计 由于本文所研究的内容是制鞋c a d 系统里的子模块，所以有必要先来讲述 整个制鞋c a d 系统的框架设计以及这些子模块之问的关系。 2 1 系统功能 在论述系统架构之前，先对制鞋师傅的手工制鞋方法做一个大致的介绍，以 方便读者对本文内容的理解。 制鞋师傅用手工的方法设计一组全号的鞋子时，一般是先在中间号( 比如2 5 号) 的鞋棺上设计并描画好各部位鞋帮的轮廓( 如2 - l 所示) ，然后用纸片粘贴在 鞋楦上，根据所描画的鞋帮轮廓对纸片进行修整，修整完毕后就得到了一只鞋子 上全部帮片的形状然后展开纸帮片，对其进行缩放，从而得到镯i 垒号的鞋子 的所有纸帮片，虽后以这些纸帮片的形状在皮革原料上进行排样、裁剪，从而获 得制鞋所需的鞋帮。同理，鞋底也要依据中旬号鞋楦的形状先用纸片做好，然后 进行花纹设计、缩放，再用刻模机刻出鞋底模板，最后用机械设各加工出鞋底”“。 图2 1 鞋桓及鞋帮描线 理想的三维制鞋系统应该是先在计算机中建立鞋檀的立体模型，通过描线、 蒙皮的方式直接在上面设计鞋帮，然后将鞋帮分块展平后输出到二维图形设计部 分的自动缩放或排样系统进行处理o ”2 。三维图形和二维图形设计之间的接口 在于鞋帮曲面的展平“。本文的研究重点在于二维鞋样设计班及鞋帮样片的优化 排样，我们设计的系统架构如图2 2 所示。 排样，我们设计的系统架构如图2 ，2 所示。 浙江1 二业大学硕：i 二学位论文鞋底设| 十与优化排样系统的研究与实现 圈2 2 系统架构图 本文的目标是实现具有以下特点的鞋样部件c a d “”及优化排样系统： ( 1 ) 操作简便，人机界面和谐，系统能够根据标准样板快速生成全号样板 缩短新款鞋帮、鞋底的开发周期，使企业的产品更具有竞争力。 ( 2 ) 根据排样算法，对设计图样自动生成最佳的平面裁剪样板和各种生产报 表，以节省生产成本。 ( 3 ) 在鞋样编辑及排样过程中，采用数据库技术管理产品和材料的数据，提 供数据录入、修改和查询功能，减少人员工作强度，提高管理效率。 整个系统的功能模块如图2 - 3 所示： 图2 - 3 系统功能模块图 丁 | i 型鞭纛i e 熙 习耍鬲l |孤固一塑磊l | | | i 鲨 班回一 浙江工业火学硕士学位论文鞋底设计与优化排样系统的研究与实现 2 2 系统开发环境 本系统的二维鞋底图案编辑设计部分采用v c + + 和o p e n g l 图形库作为开发 工具。o p e n g l 作为一种开放的图形工具软件包，独立于窗口系统和操作系统， 它具有建模、变换、光线处理、色彩处理、动画及更先进的能力，灵活方便的实 现了二维和三维的高级图形技术，在性能上表现得异常优异。以o p e n g l 为基础 开发的应用程序可以十分方便的在各种平台间移植。o p e n g l 可以与v c + + 紧密 接口，便于实现各种图形算法，可保证算法的正确性和可靠性。 v i s u a lc + + 6 0 中的绘图是通过图形设备接口( g d i ) 调用相应的函数在设备 环境中来实现的，设备环境本身是一个“图形设备接口”对象，g d i 是组驻留 在w i n d o w s 核心的一个动态链接库中的函数，这些函数提供了画图函数的调用 和设备驱动程序之间的链接“。m i c r o s o f t 基本类( m f c ) 为设备环境提供了各种 包装，可以简化与g d i 对象的交互操作。标准设备环境类c d c 内容十分丰富 陔类可提供各种各样的绘画、坐标映射、剪辑等函数，以实现图形显示，其它所 有的专用设备环境类是以该类为基础、并对其功能进行扩展“”。 6 浙江工业大学倾士学位论文 鞋底设计与优化排样系统的研究0 实现 第三章鞋底花纹设计 本章对制鞋c a d 系统里鞋底花纹的绘制方法进行介绍。因为花纹绘制是鞋 底设计的重要组成部分，鞋底自动缩放的时候花纹必须同步缩放，而绘制花纹的 算法是对其进行缩放的基础”“，因此加以介绍。 鞋底花纹搭配得好，除了具有美观、防止打滑的功能，还可以自动去污。当 然，这要有足够多的花纹种类为基础。在我们的系统中，设计并实现了等距线、 折线、蛋形、腰子形等一批专用花纹，且能够对它们进行移动、复制、删除等编 辑操作，完全能够帮助制鞋师傅设计出高质量的鞋底款式。 3 1 等距线 根据已有的鞋底外轮廓，设定好两线之间的间隔距离，系统就会自动绘出鞋 底外轮廓线的等距线。在绘制等距线前，首先要确定鞋底曲线的数学形式，所以 我们先介绍鞋样轮廓曲线的表现形式。 3 1 1 鞋样轮廓曲线表示 本系统中的鞋样轮廓是由n u r b s “”“”形式来表示的。n u r b s 模型可用分 段有理b 样条多项式基函数定义”“，其形式是： q “) 二l - - 2 圳- - 面号 w ： u , 。t ( 如w ( 甜) 2 莩以 ( 以 ( 式3 1 ) 其中p 是特征多边形顶点位置矢量，+ ( “) 是k 次b 样条基函数，其定义形 式为： = 岳茎他：甜“， ( 式3 2 ) j脚：坠丛掣+坠必以。)(船3)ti + k - 1 一t t m t j 十1 1”“ 。为。样条基函数的次数，节点矢量t = t 1 ，对于女为b 样条基函数的次数，节点矢量，对于 浙江工业大学砸l 学位论文鞋底设计与优化排样系统的研究与实现 非周期函数，若有一个正实数d ，对于全部t j s 月，存在7 川一- 。d ，则称t 为均匀节点矢量，否则为非均匀节点矢量。在实际应用中取口= 0 ，= 1 ，由式( 3 3 ) 和节点矢量t 定义的“o ，1 区间上的整条n u r b s 曲线与b e z i e r 曲线相似，即曲 线过起、终点，且起、终点的切矢量控制多边形的第一条边和最后一条边。 3 1 2 等距线的绘制 这里采用一种参数优化的方法整体逼近构造n u r b s 曲线的等距线。等斑线 构造的基本过程为： 1 ) 根据端点处的连续性条件确定始终点以及相邻控制顶点的约束条件式 ( 3 7 ) ； 2 ) 根据原始曲线的曲率，按一定精度计算出一批精确等距点。 3 ) 把计算得到的精确等距点用最d , - 乘法拟合得到等距线； 4 ) 采用参数优化方法计算精确等距点的修正参数值，用新参数值重新拟合等 距线； 5 ) 对不满足精度的点，插入重节点，转入3 ) 重新构造等距线，直到满足精度 为止。 已知m 次n u r b s 曲线定义为 c ( 秘) = 音万荟nw f e “如w ( 群) = 车w f f “蛾“u m ，u n + 1 ， ( 式s ，。) 按上式其等距线为 c j ( “) = c ( u ) + d d v ( u ) ，z f “。，“。+ i ，( 式3 ，5 ) 现在构造一条m 次n u 如s 曲线s ( “) 来逼近曲线c o ( “) ，即 w n 。( 群) s ， s ( 扰) 2 鼍一，“ “。，甜州 ( 灿6 ) w , n 协( 扰) 由连续性条件有 浙江1 业大学硕上学位论文 鞋底设计与优化揶样系统的研究与实现 怪so燕：po+d3v(um),o， ( 式3 7 ) 按照精度要求，对c 。( “) 进行离散，离散后得到的点串对原曲线的逼近误差 按密切圆估计，用参数优化方法。4 ”5 1 提高整体拟合这些离散点串p ( f _ 0 ，l ，k ) 的精度。 在优化拟合后，应当对非优化点( 即取样点外的其他一些点) 进行误差估汁 即在c 。( “) 上取批点，考察这些点到s ( u ) 的局部最小距离d ，若d 大于指定误 差，则在相应节点区间插入一些新节点，熏复上述过程。 总体来说，用上述优化参数的方法得到n u r b s 等距曲线，具有以下特点： 1 ) 曲线的等距线数值稳定，计算省时； 2 ) 得到的逼近曲线具有保形性，保凸性等性质； 3 ) 算法规范简单，易于编程实现。 3 2 折线、波浪线 图3 - 1 等距线效果图 根据设定好的折线宽度和拐角个数，可以在鞋底轮廓内任意画出所需的折线 图形。折线的推导方程如下： 浙江工业大学硕学位论文鞋底设计与优化排样系统的研究与实现 图3 2 折线不意图 如图3 - 2 ，已知折线个数 、折线高度h 、起点坐标m ( 一，y 。) 、终点坐标 ( ：，y 2 ) 。设d 。= ( z 2 一z ，) 4 五n ，d ：= ( y ：一y 1 ) 丽，k d 。i d 2 ，则i 叮 得： 只点横坐标x p l = 置+ 吐+ h 4 x 2 + 1 ， 只点纵坐标y p l = y l + d 2 + h 足置2 + 1 ， 足点横坐标斗2 = _ + 2 x d ， 最点纵坐标y p 2 = y i + 2 x d 2 ， 同理可计算其余拐点的坐标，用直线段连接各拐点即得折线。 波浪线的推导过程同折线相似，只是用圆弧连接各点而成。 图3 - 3 折线效果图 1 0 ，、 浙江工业大学硕j 二学位论文 鞋底设计与优化排样系统的研究与实现 3 3 多边形 图3 - 4波浪线效果图 根据设定好的多边形边数，可以在鞋底轮廓内任意画出所需的多边形。多边 形的推导方程如下： 图3 - 5 多边形不意图 如图3 - 5 ，已知多边形的中，t b , 点g 和一个顶点p ( x 。，y 。) ，多边形的边数h 。设 另一个顶点m 的坐标为( x ：，y ：) ，中心点g 到顶点p 的距离为d ，线段g p 和j 塑 脚的夹角为目，线段卯与z 轴的夹角为口。则由式( 3 5 ) 可求得多边形的另一 个顶点m 。因为此多边形为正多边形，所以每个顶点都可以同理求出。求出所 有的顶点后，用直线段连接，就可绘制出多边形。 x 1 = h xc o s ( e ) x 2 = x 1 x c o s ( a 一目) ( 式3 5 j 【y 2 = x 1xs i n ( a 一目) 浙江工业大学硕士学位论文 鞋底设计与优化排样系统的研究与实现 3 4 五角星、六角星 图3 - 6多边形效果图 五角星的推导方程如下： 如图3 7 所示，已知中心点g 的坐标为( x 。，y ，) ，一个顶点p 的坐标为 ( x 2 ，y ：) 。设m 点的坐标为( x 3 ，y 3 ) ，点的坐标为( x 。，y 4 ) ，中心点g 到顶点p 的 距离为d ，线段g p 和边n p 的夹角为0 ，线段g p 与x 轴的夹角为口。则由式( 3 6 ) 可以求出m 点的坐标，由式( 3 7 ) 可以求出点的坐标。同理可以求出五角星的 其他各个顶点，之后用直线段将它们连接，就可绘制出五角星。 x3，=订x2-hx3xzlo)x缸口一-zlo)“2xzlo)yy h xc o s ( 3 z l o ) xs i n ( az l o ) e o s ( 2 x z l o ( 枷) 【3 = 2 一 一 ) 。 f l = h x e o s ( 8 ) x 4 = x c o s ( a 一口) ( 式3 7 ) l y 4 = l s i n ( a 一 y o 图3 7 五角星示意图 图3 - 8 六角星示意图 1 2 x 澎一 髫 浙江 _ 业大学硼士学位论文鞋底设汁与优化排样系统的研究与实现 六角星的推导方程如下： 如图3 8 所示，已知中心点g 的坐标为( x ，y ，) ，一个顶点p 的坐标为 ( x ：，y 2 ) 。设m 点的坐标为( 屯，y 。) ，n 点的坐标为0 。，y 。) ，中心点g 到顶点p 的 距离为d ，线段g p 和边n p 的夹角为0 ，线段g p 与一轴的夹角为口。则由式( 3 8 ) 可以求出肼的坐标，由式( 3 9 ) 可以求出的坐标。同理可以求出六角星的其他 各个顶点，之后用直线将它们连接，就可绘制出六角星。 x3=：x2，-一hx。cos(z刊-；,r6)(eos(z6)2)。2y3y h s i n ( a t6 ) ( c o s ( t r 6 ； ( 舶8 ) l= 2 一 一石 ) 2 ) f l = h c o s ( o ) x 4 = 上c o s ( o ! 一0 )( 式3 9 ) 【y 4 = 三s i n ( d 一口) 图3 - 9 五角星效果图 3 5 蛋形、腰子形 图3 一1 0 六角星效果图 对于蛋形和腰子形“”，可以实时的调整切圆半径的大小以控制它们的形状。 蛋形的推导方程如下： 浙江工业大学砸上学位论文鞋底殴计i i 优化排样系统的研究与实现 如图3 - 1 1 所示，已知圆1 的圆，g , 0 1 ( 工，y 1 ) 、半径r l 和圆2 的圆一t l , 0 2 ( x 2 ，y 2 ) 、 半径为r 。作两个半径为r ( r 要求满足：2 r r ，一r ： i o 0 2 1 ) 的圆与圆1 及 圆2 相切。如图4 - 9 所示。现在求切点：a 。，b 。，a ：，b ：的坐标。 4 - i = 1 0 1 0 2 1 ，= d 10 3 l = i o 。0 4 1 = r r 。，2 ：= 0 2 0 a i = 1 0 2 0 。1 = r - r ：。 由 图3 - 1 1 蛋形示意图 s i n 一置以及卜= 寄蝴圳。 c o s ( x 2 _ 产1 0 卢 1 0 1 0 2 1 ) 与圆l 和圆2 相切。如图4 - 1 0 所示。 现在求切点：a ，b ，a ：，b ：的坐标。 令，= l o t o z l ，= j o l 0 3 l = r 。一- ，：= 1 0 2 0 3 l = r 一r 2 ， 图3 一1 2 腰子形示意图 ，s = 1 0 1 0 4 f = r ：+ ，1 4 = i d 2 d 4 f = r ：+ r 2 。 x 由严。薯以及p = 筹，卜：黼 卜口= 罕l o 万1 【o p 万1 可以求出角度口，妒。5 ：是0 3 ，0 4 的坐标分别为 j 工3 = x l + l lc o s ( g r 一)f 工4 = x l + 屯c o s ( a p ) l y 3 = y l + f 1s i n ( a 一卢) 。【y 4 = y 1 + 1 3s i n ( a p ) 求出0 3 ，0 4 的坐标后，则很容易求得4 ，b ，a ：，b ：的坐标，方程式如下 j x l = x 3 + r 1 ( x 1 一x 3 ) i 】 l y l = y 3 + r i ( y 】一y 3 ) i i i x 22 x 3 + r ， i y 2 = y 3 + r ( x 2 一x 3 ) 1 2 ( y 2 一y 3 ) t 2 | z b l = x l 十1 ( z 一x 1 ) 屯 【y = y l + l 。( y 4 一y 1 ) j x 口22 2 2 + ，2 ( 工4 一x 2 ) l l l y 日2 = y 2 + r 2 ( y 4 一y 2 ) t 4 1 5 浙江工业大学硕士学位论文鞋底设计与优化排样系统的研究与实现 得到切点的坐标后，将相应的圆弧段连接起来即可得到腰子形。 图3 1 3 蛋形效果图 3 6 本章小结 图3 一1 4 腰子形效果图 在系统实现过程中，我们注意紧密的联系制鞋行业的实际情况，认真考虑了 剑鞋师傅的实际需求。在本章给出了多种常甩鞋底图案的计算机绘制方法，并且 在制鞋c a d 系统中加以实现，为鞋底款式设计提供了丰富的选择，从而帮助用 户更加方便、快速的设计鞋底款式。 1 6 浙江卫f k 火学碗：仁学位论文 鞋底设计与优化捌样系统的研究与实现 第四章鞋底图案填充 本章介绍的是此c a d 系统鞋底图案填充方法。在鞋底设计中，大多数款式 鞋子的设计都需要进行图案填充。而鞋底的图案填充属于区域填充，在此我们 先介绍区域填充的几种传统算法，其中包括有扫描线填充算法和种子填充算法。 4 1 区域填充 不论是在计算机图形学中，还是在计算机图像处理中，区域的填充都是一个 基本而又重要的操作。区域填充是指将符合四连通或八连通定义的区域内的一点 ( 常称为神予点) 赋予给定颜色，然后将这种颜色扩展到整个区域的过程。它 在计算机辅助设计、真实感图形显示以及图像处理等领域有着广泛的应用，其中 填充效率的提高是个非常关键的问题。 最简单、直观的区域填充算法是传统的递归算法，它具有程序简单、表达清 楚的优点，但由于存在多层递归，系统堆栈反复进出，就不可避免的造成了费时、 费内存的缺点。传统的区域填充算法有扫描线填充算法、种子填充算法、边标志 填充算法“”“” 3 3 1 o 4 1 1 扫描线填充 经典区域填充扫描线算法的基本思想。”是：首先利用区域在扫描线上的连赁 性，填充当前扫描线上的一个区段，然后利用相邻扫描线上区段的连贯性，在一l 下两条相邻扫描线上寻找新的区段，并以种子点堆栈的形式保存这些区段。反复 处理堆栈内的区段，直到保存的所有区段都处理完为止o “。这一过程可以分为如 下5 个步骤进行： 步骤1 ：( 初始化) 将算法设置的堆栈置为空，将给定的种子点( x ，y ) 压x 堆栈。 步骤2 ：( 出栈) 如果堆栈为空，算法结束：否则取栈顶元素( x ，y ) 作为种子点。 步骤3 ：( 区段填充) 从种子点( x ，y ) 开始沿纵坐标y 的当前扫描线向左右两个 方向逐个像素进行填色，其值置为n e w c o l o r ，直到到达边界为止。 步骤4 ：( 定范围) 以x l 和x ，分别表示在步骤3 中填充的区段两端点的横坐标。 步骤5 ：( 进栈) 分别确定当前扫描线的上下相邻两条的扫描线上位5 = x l ，x d 浙江t 业大学硕l 学位论文 鞋底设计与优化排样系统的研究与丈i 见 区域内的区段。如果这些区段内的像素的颜色值为n e w c o l o r 或者 b o u n d a r y c o l o r ( 边界上像素的颜色值) ，则不产生新的区段，直接转到步骤2 ，否 则取区段的右端点为种子点压入堆栈( 可能不止一个) ，再转到步骤2 继续执行。 扫描线填充算法是用一系列平行直线去切割轮廓线，通常有成对的交点出 现，每对交点就代表扫描线与轮廓线的一个相交区间：该算法的缺点是每条扫描 线要和轮廓线进行求交运算，并且得到的交点需排序运算3 “。 4 1 2 种子填充算法 如果在填充时先给出区域内的一点，称为种子点，在此基础上进行的区域填 充算法称为种子点填充算法。种子点填充算法可以分为简单的神子点填充算法 ( 又称为种子点区域填充的递归算法。7 1 ) 和扫描线种子点填充算法。由于简单的 种子点填充算法需要很大的存储空间做栈空间并且效率太低，因而效率稍高且只 需少量栈空间的扫描线种子点填充算法成为当前使用最广泛的种子点区域填充 算法。 扫描线种子填充算法。”的描述如下： 种子像素点入栈； 当栈非空时作如下4 步操作： 步骤l ：栈项像素出栈。 步骤2 ：沿扫描线对出栈像素的左右像素进行填充，直至遇到边界像素为止， 即每出栈一个像素，就对包含该像素的整个区间进行填充。 步骤3 ：上述区间内最左和最右的像素分别记为x l 和x ，。 步骤4 ：在x f 司 x l ，x | 】中检查与当前扫描线相邻的上下2 条扫描线的有关像 素是否全为边界像素或已填充的像素，若存在非边界、未填充的像素，则把每一 个区间的最右像素取作种子像素点入栈。 种子填充算法是在被填充的区域中预先设置一个种子像素，然后以该像素为 起点，按四向算法或八向算法搜索下一个像素，由此出发蔓延直到找到区域内所 有像素：该算法的缺点是种子点的找寻比较困难，有的像素可能被访问多次，并 且种子点的入栈和出栈也降低了算法的效率 4 0 1 。 浙江工业人学硕士学位论文鞋底设计与优化排样系统的研究与实现 4 1 3 边标志填充算法 多边形边标志填充算法“一般分为两步： 第一步，对多边形的边界进行标记，所采用的办法是进行直线扫描，判断某 扫描点是否是扫描线与多边形边的交点。 第二步，填充对每条与多边形相交的扫描线，依从左到右顺序，逐个访问该 扫描线上的像素。 使用一个布尔量i n s i d e 来指示当前点的状态，若点在多边形内，i n s i d e 为真。 若点在多边形外，则i n s i d e 为假。每当当前被访问的像素为被打上边标记的点， 就把i n s i d e 取反。对未打边标志的像素，i n s i d e 不变。对当前所访问的像素，对 i n s i d e 作了必要的操作后，若i n s i d e 为真，则把该像素置为多边形色。 边填充算法的基本思想是对于每一条扫描线和轮廓线的每个交点，将该扫描 线上交点右方的所有像素取补。它的优点在于简单，与边的顺序无关；缺点是每 个像素可能被访问多次，也需要各扫描线与每条边进行求交运算。 4 2 图案填充 前面介绍的区域填充算法，把区域内部的像素全部置成同一种颜色。但在实 际应用中，有时需要一种图案来填充平面区域。在鞋底区域中，经常需要图案填 充。通常的图案填充是对前述算法稍作修改来实现的：在确定了区域内一像素之 后，不是马上往该像素填色，而是先查询图案位图的对应位羲。但是扫描线填充， 种子填充算法、边填充算法均需要求解扫描线和轮廓线的交点，当区域为由不规 则曲线构成的任意形状时，则求解交点过程更为复杂。 4 2 1 基于可行域的图案填充算法 在文献 4 2 】中，提出了一种基于可行域的填充方法，避免了求解扫描线和区 域轮廓线交点的复杂过程。在此基础上，本章提出了基于可行域的图案填充算法 1 ，该算法避免了高复杂度的求交运算，并且可以填充任意形状的区域。 算法的基本思想：满足如以下方程组( 1 ) 的闭合区域内的点构成了一个可 行域，区域内待填充的点都位于可行域内。 浙江工业大学硕士学位论文鞋底设计与优化排样系统的研究i 实现 待填充的边界约束条件： ，( 工) = 0 x 一，i = l ，2 m( 式4 1 ) i ，珥sj ，p ， ( x ) = 0 是闭合图形的第i 段曲线方程。 满足( 4