（计算数学专业论文）参数化设计中确定参数有效范围的dm分解算法的研究.pdf

中文摘要 中文摘要 计算机辅助设计( c o m p u t e ra i d e dd e s i g n ，简称c a d ) 是一种利用计算机的硬件 和软件来进行产品的建模、修改、分析和优化的设计活动，它广泛的应用在科研 和生活的各个领域中。现在它的应用水平已经成为衡量一个国家科技现代化和工 业现代化水平的重要标志之一。 c a d 技术的发展经历了四次重大的技术创新，其中变量化技术是第四次技术 创新，而几何约束求解是参数化技术和变量化技术的核心。目前，几何约束求解 的方法主要有四种：基于数值的，基于符号的，基于规则的和基于图论的。在实 际的工程设计中，我们需要对给定的草图进行分析，进而得到满足设计者需求的 模型。 基于参数模型的c a d 系统的一个非常重要的优点是允许设计者随时改变参数 值来达到对草图的修改。然而，在修改参数值时，常常由于给定的参数值不合理， 而导致无法重新生成几何图形。所以，确定参数的有效范围对于几何约束求解是 非常必要的。 本文利用d m 分解算法和吴方法从代数可解的角度给出一个确定几何约束求 解中参数的有效范围的算法。该算法对于提高几何约束求解的交互性和准确性有 着重要的作用，并且使得几何约束求解的研究更具有实际意义。 关键词：几何约束求解；几何体；d m 分解；吴方法；参数的有效范围 黑龙江大学硕士学位论文 a b s t r a c t c o m p u t e ra i d e dd e s i g nt e c h n o l o g yi sak i n do ft e c h n o l o g yt h a tu s eh a r d w a r ea n d s o f t w a r eo fc o m p u t e rt od om o d e l i n g ，m o d i 瓢a n a l y z eo ro p t i m i z ew o r k i tw i d e l y a p p l i e st oa l lk i n d so f f i e l do fs c i e n t i f i cr e s e a r c ha n d l i v i n gl i f e ，t h ea p p l i c a t i o nl e v e lo f c a dt e c h n o l o g yh a sa l r e a d yb e c o m eo n eo ft h em o s ti m p o r t a n ts y m b o l st oe s t i m a t et h e s c i e n c ea n dt e c h n o l o g ya n dt h ei n d u s t r ym o d e r n i z a t i o no fac o u n t r y t h ed e v e l o p m e n to fc a d t e c h n o l o g yh a sg o n et h r o u g hf o u rs i g n i f i c a n tt e c h n o l o g y i n n o v a t i o n s ，t h el a s ti n n o v a t i o ni st h ea p p e a r a n c eo fv a r i a b l et e c h n o l o g y g e o m e t r i c c o n s t r a i n ts o l v i n gi st h ec o r eo fp a r a m e t r i ct e c h n o l o g ya n dv a r i a b l et e c h n o l o g y a t p r e s e n t , t h e r ea r ef o u rb a s i ca p p r o a c h e st og e o m e t r i cc o n s t r a i n ts o l v i n g ：n u m e r i c a l a p p r o a c h ，s y m b o l i ca p p r o a c h ，r u l e - b a s e da p p r o a c ha n dg r a p h b a s e da p p r o a c h a t p r a c t i c a le n g i n e e r i n g ，wn e e da n a l y z et h eg i v e nd e s i g ng r a p h ，t h e np r o d u c eg e o m e t r i c m o d e ls a t i s f i e dd e s i g n e r sd e m a n d a v e r yi m p o r t a n ta d v a n t a g eo fc a ds y s t e mb a s e dp a r a m e t r i cm o d e li st h a ti t a l l o w sc h a n g ep a r a m e t e rv a l u e sr a n d o mt on l o d i 黟d e s i g ng r a p h h o w e v e rw h e nw e c h a n g ep a r a m e t e rv a l u e s ，o f t e ni tc a nn o tp r o d u c eg e o m e t r yg r a p hd u et oi r r a t i o n a l p a r a m e t e r t h e r e f o r ed e t e r m i n i n gp a r a m e t r i ce f f e c t i v er a n g ei sv e r yp r e r e q u i s i t ef o r g e o m e t r i cc o n s t r a i n t s f r o ma l g e b r as o l u b l ea s p e c t , t h et h e s i su s e r sd m d e c o m p o s i t i o na n dw u m e t h o d t og i v ea na p p r o a c h ，w h i c hc a nd e t e r m i n ep a r a m e t r i ce f f e c t i v er a n g ef o rg e o m e t r i c c o n s t r a i n t s t h i sa p p r o a c hh a v ei m p o r t a n tr o l et oi m p r o v ea l t e m a t i o na n da c c u r a c yf o r g e o m e t r i cc o n s t r a i n t s , a n dm a k i n gi t i sm o r ep r a c t i c a ls i g n i f i c a n c ef o rt h er e s e a r c ho f g e o m e t r i cc o n s t m i n ts o l v i n g k e y w o r d s ：g e o m e t r i cc o n s t r a i n ts o l v i n g ；g e o m e t r i cp r i m i t i v e ；d md e c o m p o s i t i o n ； w u m e t h o d ；p a r a m e t r i ce f f e c t i v er a n g e ； 1 1 独创性声明 独创性声明 本人声明所呈交的学位论文是本人在导师指导下进行的研究工作及取得的研 究成果。据我所知，除了文中特别加以标注和致谢的地方外，论文中不包含其他 人已经发表或撰写过的研究成果，也不包含为获得墨垄堑太堂或其他教育机构的 学位或证书而使用过的材料。 学位论文作者签名： 刍2 旋 签字日期：文唧年妒，j 胡 学位论文版权使用授权书 本人完全了解墨蕴堑太堂有关保留、使用学位论文的规定，同意学校保留并 向国家有关部门或机构送交论文的复印件和电子版，允许论文被查阅和借阅。本 人授权墨蕉堑盔堂可以将学位论文的全部或部分内容编入有关数据库进行检索， 可以采用影印、缩印或其他复制手段保存、汇编本 学位论文作者签名： 二t j 旋 签字日期：云叩年户，户 学位论文作者毕业后去向： 工作单位： 通讯地址： 导师签名： 签字日期：a j 7 r 年r 月，日 电话： 邮编： 第1 章绪论 1 1c a d 的发展历史 第1 章绪论 设计一直是人类认识和改造世界的重要活动。周围世界的广泛领域，飞机、 轮船、建筑、器皿、家具乃至计算机程序，一切人类的创造物无不需要设计。设 计过程是由信息检索、分析、计算、综合、修改及文件编制等诸多环节构成，其 中形状的分析、综合、修改及图纸绘制是最具特色的典型设计环节。 随着计算机的出现，1 9 6 3 年，美国麻省理工大学的2 4 岁的研究生i e s u t h e r l a n d 首次提出了计算机辅助设计【l 】( c o m p u t e ra i d e dd e s i g n ) 的概念，它是 指利用计算机的硬件和软件进行的设计活动，包括使用计算机的数据库、程序库 及通信等技术来完成设计过程的信息检索、分析、计算、综合、修改及文本编制 工作。它可以将远非单纯人脑所能承担的设计和制造任务当作日常工作来处理， 其处理的复杂程度，将随着一代一代计算机硬件和软件系统的更新而不断提高。 c a d 的技术经历了四次重大的技术创新：第一次c a d 技术创新是2 0 世纪7 0 年代出现的曲面造型技术。这次技术创新改变了以往只能借助于油泥模型来近似 表达曲面的落后的工作方式。首次实现了以计算机完整描述产品零件的主要信息。 第二次c a d 技术创新是2 0 世纪8 0 年代初期的实体造型技术。这项技术能够精确 表述零部件的全部属性，例如重心、质量和惯性矩等，在理论上有助于统一c a d 、 c a e 、c a m 的模型表达，给设计者带来了惊人的方便性。第三次c a d 技术创新是 2 0 世纪8 0 年代后期的参数化实体造型技术，这项创新技术首次引入了约束的概念。 参数化实体造型技术将一组参数与控制零部件几何图形的一组结构尺寸序列相对 应，当赋予不同的参数值时，就可以产生一系列具有相似几何图形的零部件。参 数化实体造型技术的特点是：基于特征的设计、全尺寸约束、全数据相关、尺寸 驱动设计的修改。第四次c a d 技术创新是2 0 世纪9 0 年代后期出现的变量化技术。 这是参数化设计的一次飞跃。变量化设计将整个设计草图当作一个完整的系统来 考虑，与构造过程的顺序无关。变量化技术还将草图中的控制尺寸和拓扑关系都 黑龙江大学硕士学位论文 用约束来表示，这使得设计初期的草图可以不是完全定义的，而将没有完全定义 的控制尺寸和拓扑关系用变量储存起来，暂时以当前的绘制尺寸赋值。设计者可 以在任何阶段对草图中的任何尺寸和拓扑关系进行重新定义，同时这种重新定义 也不必牵涉草图中所有的几何实体的改动。变量化技术提供的灵活更改模型的方 式，有效地支持了c a d 的概念化设计，可以使设计者的创造性和想象力得到更充 分的发挥。 c a d 技术的引入从根本上改变了过去的手工绘图、发图、凭图纸组织整个生 产过程的技术管理方式，将它变为在图形工作站上交互设计，用数据文件发送产 品定义，在统一的数字化产品的模型下进行产品的设计打样、分析计算、工艺规 划、装备设计、数据加工、质量控制、编印产品维修手册、组织备件订货供应等 等。大大提高了设计的效率和质量，降低了成本，缩短了产品的研制周期，在整 个生产系统中起着举足轻重的作用。今天，c a d 已经渗透到工程技术和人类生活 的几乎所有领域，并日益向纵向发展。 1 2 智能c a d 的发展历史 智能c a d 是人工智能( a r t i f i c a li n t e l l i g e n t ，简称a i ) 和c a d 技术相结合的 - - f l 综合性研究领域，其英文名为i n t e l l i g e n tc a d ，或简称i c a d 。它将触的理 论和技术用于c a d 之中，使c a d 系统能够在某种程度上具有设计师般的智能和 思维方法，从而把设计自动化引向深入，这是c a d 技术在学术上的一个重要方向。 理想的智能c a d 系统是人类提出设计要求，由电脑模拟设计师，自动设计出 形式多种多样的且能够满足要求的设计方案来。然而，传统的图形交互技术中， 机器都处于绝对的被动状态，即“拨一拨，动一动 ，因而操作呆板而繁琐。采用 触技术后，系统可以以用户输入的信息为基础，通过电脑已具备的常识和推理， 自动获得更多的信息，从而使得交互变得简单。 智能c a d 系统的主要目标是支持设计师在设计过程中的思维。“真正”实现 具有创造性的设计过程，而不仅仅是一个重演的过程。认知科学、人工智能和c a d 的发展将智能c a d 的研究引入一个崭新的天地。另外，智能交互、智能表示和自 第1 章绪论 动数据获取也是智能c a d 的研究课题之一。为了实现智能c a d 的这些目标和要 求，人们提出了面向方案形成过程的i c a d 方法。众所周知，方案是一个设计的 核心，方案有粗有细，它表示设计结果或接近设计结果。方案的形成过程可以看 成是一个约束满足问题，即所有的设计要求与限制都被看成对变量的约束，而最 终方案则是满足所有约束条件后的设计方案。求解的过程则是基于约束进行的。 这一设计方案被称为基于约束满足的设计方法。1 9 6 3 年，i e s u t h e r l a n d 在他的 s k e t c h p a d 系统中第一个采用了基于约束满足的交互设计方法。除了这一设计方法 之外，还有基于理论的设计方法，基于搜索的设计方法和基于综合的设计方法。 概括而言，智能c a d 的研究中存在着三个前沿问题：首先，要解决方案的形成； 第二是围绕着设计对象、设计知识的表达展开的研究；第三是围绕智能c a d 系统 的自动作图功能研究，即几何约束求解。 1 3 几何约束求解技术的引入 工程应用中，大多数机械设计都来源于草图和现有的图形。在设计过程中， 用户一开始并不关心图形的精确尺寸，而只是粗略地勾画零件的大致形状，而且， 用户也可能在现有图形的基础上，作细微的改进。尺寸的调整是非常普遍的，因 为尺寸可以决定零件的几何形状，尺寸的改变可以生成不同的几何图形。而传统 的交互作图系统，虽能较充分发挥设计师的能力，但是，图形一旦生成就很难进 行尺寸的调整，没有继承性。另外，由于概念设计和初步设计阶段要靠设计者的 知识和经验再加以思考来完成，而这些知识和经验往往不能用精确的数字模型和 算法来描述，传统的交互作图系统对此很难胜任。为了弥补传统c a d 系统的不足， 更好的满足概念化设计的要求，提高设计效率，2 0 世纪8 0 年代后期，l i n 和g o s s a r d 等人提出了参数化设计1 2 , 3 】。参数化设计的基本原理就是系统在设计过程中自动的 捕获用户的设计意图，从而将用户设计中的各个设计对象以及对象之间的关系用 参数记录下来，而当用户修改图纸中尺寸标注和设计参数时，系统能够自动对图 纸进行必要的修改，使图纸中反映用户设计意图的设计对象之间的关系依旧得以 维持。这种技术以其强有力的草图设计和图纸尺寸驱动功能，已成为实现产品的 1 黑龙江大学硕士学位论文 初步设计、系列设计以及变异设计的核心技术。参数化技术首次引入了约束的概 念，它是一种基于约束的设计方法。参数化技术将一组参数( 约束) 与控制零部 件几何图形的一组结构尺寸序列相对应，当赋予不同的参数值时，就可以产生一 系列具有相似几何图形的零部件。而后，1 9 9 7 年s d r c 公司又推出了变量化设计， 这是参数化技术的一次飞跃 4 1 。变量化技术将整个设计草图当作一个完整的系统来 考虑，与构造过程的顺序无关。变量化技术还将草图中的控制尺寸和拓扑关系都 用约束来表示，这使得设计初期的草图可以不是完全定义的，而将没有完全定义 的控制尺寸和拓扑关系用变量存储起来，暂时以当前的绘制尺寸赋值，设计者可 以在任何阶段对草图中的任何尺寸和拓扑关系进行重新定义，同时这种重新定义 也不必牵涉草图中所有的几何图形的改动。变量化技术提供的灵活更改模型的方 式有效地支持了c a d 的概念化设计【5 】，可以使设计者的创造力和想象力得到更充 分的发挥。 基于约束的设计是智能c a d 的一个重要标志。基于约束的参数化和变量化设 计系统把问题描述与问题求解技术分离成相互独立的两部分，使得该类设计方法 较其它方法更具有明显的优势，它的主要功能包括： ( 1 ) 从几何参数化模型能自动地导出精确的几何模型。它不要求输入精确图形， 只要求输入一个草图，标注一些几何元素的约束，再通过改变约束条件来自动导 出精确的几何模型。 ( 2 ) 通过修改局部参数来达到自动地修改精确的几何模型的目的。大致形状相 似的一系列零件，只需修改一下参数，便可以生成新的零件，这可大大地提高生 产效率。 基于约束的参数化和变量化的设计系统，有以下的优点： ( 1 ) 用户可以任意方式组合，以任意顺序定义几何约束和工程约束。基于约束 的设计具有统一处理这些约束的能力，并能适合广泛意义上的工程设计。 ( 2 ) 基于约束的设计，能很快地记录设计者的意图，允许多个不同应用领域的 用户完成同一项设计任务。 ( 3 ) 基于约束的设计，能够求解过强约束或约束不足问题，而且允许用户集中 4 第1 章绪论 im_i i 地考虑某一部分的细节设计。 ( 4 ) 基于约束的设计，能全面给出解的过程，便于用户整体考虑。 ( 5 ) 基于约束的设计，具有很好的人机交互功能，能够充分地利用交互特性， 逐步地确定设计过程，给出全部的设计解。 参数化设计和变量化设计的核心就是几何约束求解，几何约束求解是指在输 入一个草图以后，用户可以随时在需要的时候，以任意的方式任意的顺序重新输 入几何约束，然后由计算机自动导出精确的满足用户要求的几何图形的过程。几 何约束求解方法的好坏和成熟与否，是衡量一个基于约束的设计系统是否优良的 关键。除了在机械设计中的一个应用外，几何约束求解技术在连杆生成、计算机 视觉、机器人以及几何定理证明中都有相当多的应用。 1 4 几何约束求解的基本概念 定义1 4 1 几何体：一个几何图形中最基本最具有特征的几何元素。例如：二 维中的点、直线、线段、圆、圆弧和三维中的平面、球面、曲面等等。 定义1 4 2 几何约束：两个或多个几何体之间具有的几何关系。例如：点与点 之间的距离，直线与直线之间的角度，两条直线垂直，直线与圆的相切等等。 通常将几何约束作如下分类： ( 1 ) 几何形式的几何约束：包括尺寸约束和拓扑约束。 尺寸约束：一般是由用户显示输入的。通常包括两点之间的距离、直线与直 线之间的角度、点到线的距离、半径约束和两条平行直线之间的距离等等。 拓扑约束：一般是隐含的，是由系统根据草图自动建立的。通常包括水平约 束、竖直约束、两条直线平行和垂直、三点共线