（计算机科学与技术专业论文）雕塑实体造型系统中连续变化求交问题的相关技术研究.pdf

浙江大学博士学位论文： 雕塑实体造型系统中连续变化求交问题的相关技术研究 摘要 曲面求交技术一直是计算机辅助几何设计中实体造型的核心算法，本文对雕 塑实体造型系统中出现的连续变化曲面等距曲面和运动曲面求交问题进行 了深入的研究，讨论了基于雕塑实体模型的连续实体布尔操作运算。 作者首先回顾了实体造型系统中实体表示模型的发展历程以及它们各自的 特点，阐述了计算机辅助设计中曲面求交技术的分类、发展历史和它们各自的优 缺点，并对连续变化曲面求交的应用背景进行了综述。 等距曲面和运动曲面在c a d c a m 领域中有着重要的应用，在一些时间敏 感场合例如数控加工动态仿真，等距曲面和运动曲面等连续变化曲面求交运算已 成为这些系统的计算瓶颈，连续变化曲面求交问题的通常解法是采用曲面求交算 法反复迭代计算交线，没有考虑连续变化曲面交线之间的相似性进行求交简化， 效率上一直不能有很大的提高。本文通过对等距曲面交线结构进行了大量的分 析，从交线的形成和演化过程，揭示了等距曲面的交线拓扑结构和曲面上特征点 之间存在着本质的联系，提取等距曲面不同o f f s e t 距离交线环的相关性，并使用 特征点来标识交线环的拓扑信息，成功地将拓扑信息和跟踪法相结合，设计了一 种等距曲面求交优化算法。算法通过在曲面交线拓扑信息的指导下，确定交线分 支初始点的求取策略，根据交线环拓扑结构，动态调整交线环的局部搜索策略， 从而提高了交线环求解的演化效率。新算法在已知交线环拓扑信息的情况下不仅 自动解决了常规算法中难以克服的拓扑连接错误，而且对于常规算法中难以克服 的多分支奇异点等情况都能正确处理。 在分析了等距曲面求交问题的基础上，本文针对实体造型系统中较常用的运 动曲面求交问题也进行了研究，本文结合运动曲面自身的特点，找到了表征运动 曲面不同运动瞬间交线环演化规律的拓扑特征点，并提出了运动曲面优化求交算 法。 在分析以往雕塑实体模型数据结构的基础上，本文给出了一个运动雕塑实体 布尔操作算法，在保证鲁棒性和精确性的同时确保高效率是算法的目标。雕塑实 体模型通过裁剪曲面片和半边数据结构来表达几何和拓扑信息。结合前面提到的 连续变化曲面求交算法，在原有雕塑实体布尔操作的基础上，把连续变化曲面求 交技术应用到运动雕塑实体布尔操作中，利用连续运动中曲面交线相似性进行求 交简化，加快布尔操作计算时间，加入对连续运动实体的特殊处理，提升了运动 雕塑实体布尔操作的计算效率。同时采用层次求交和交线跟踪的方法，保证曲面 片分割和区域分类的一致性，从而克服了实践中常见的退化情况。在该算法的基 摘要 础上，本文也给出了扩展到非正则模型的布尔操作算法。 为了在某些限时操作下得到实时交互的速度，在运动雕塑实体布尔操作的基 础上，本文进一步提出了一个运动雕塑实体模型布尔操作的分布式并行算法。实 现了一个基于异构多机型的局域网的分布式运动雕塑实体布尔操作并行算法，提 出一个常用分布式雕塑实体布尔操作的并行模型，并在此基础上对算法进行改 造，实现了运动实体的分布式布尔操作。算法的主要工作是在串行算法的基础上 提取各个阶段的并行性，并对于不同的并行任务采用不同的负载均衡手段，将任 务分布到局域网上不同的处理器节点，以获得实时计算效果。对于常见的网络出 错情况，算法也进行了相应的处理，确保任务的最终完成。 关键词：计算机辅助几何设计、曲面求交、等距曲面、运动曲面、拓扑特征点、 有向距离、实体造型、跟踪法、半边数据结构、欧拉操作、裁剪曲面、分布式系 统、任务均衡。 浙江大学博士学位论文雕塑实体造型承统中连续变化求曼问题的相关技术研究 a b s t r a c t s u r f a c e s u r f a c ei n t e r s e c ta l g o r i t h m ( s s i ) i st h ek e r n e la n dk e ya l g o r i t h mo fs o l i d m o d e l i n gi nc o m p u t e ra i d e dd e s i g n t h i sd i s s e r t a t i o nm a k e ss c i e n t i f i cr e s e a r c h e so n c o n t i n u o u ss u r f a c ei n t e r s e c t ，a tt h es b n l et i m e ，i tp r e s e n t sa l g o r i t h ma n dd a t as t r u c t u r e t os u p p o r tt h ec o n t i n u o u sb o o l e a n o p e r a t i o n t h ed i s s e r t a t i o nr e v i e w st h eh i s t o r yo fs o l i dm o d e l i n g ，i ta n a l y z e sg e n e r a ls s i a l g o r i t h m ，a n ds u m m a r i z e sb a c k g r o u n d o f c o n t i n u o u ss s i o f r s e ts u r f a c ea n dm o t i o n a ls u r f a c ep l a yi m p o r t a n tr o l ei nc a d c a m i ns o m e t i m e - c r i t i c a l s i t u a t i o n ，c o n t i n u o u s s s ii s c o m p u t a t i o nb o t t l e n e c k o fs o m es o l i d m o d e l i n gs y s t e m c o n v e n t i o n a la p p r o a c hf o rs o l v i n gc o n t i n u o u s s s io f t e nu s e s i n t e r s e c t i o na l g o r i t h mi t e r a t i v e l yw i t h o u tt a k i n gt h ec h a r a c t e r i s t i co ft h es u r f a c ei n t o a c c o u n tt o s i m p l i f yc o m p u t a t i o n t h e d i s s e r t a t i o n a n a l y z e st h e i n t e r s e c tc u r v e s t r u c t u r eo f c o n t i n u es u r f a c e ，f r o mt h ep o i n to f i n t e r s e e tc u r v e se v o l u t i o n ，i td e s c r i b e s t h er e l a t i o n s h i pb e t w e e nt o p o l o g yo fo f f s e ts u r f a c ei n t e r s e c tc u r v ea n dt o p o l o g y t r a n s m i tp o i m ( t t p ) i t p r e s e n t sa l g o r i t h m st oe x t r a c tt h es i m i l a r i t yo f i n t e r s e c tc u r v e i nd i f f e r e n to f f s e td i s t a n c ea n du s e1 v r pt ol a b e lt h et o p o l o g yo fs u r f a c ei n t e r s e c t t h e a l g o r i t h m ss u c 9 3 e e di nc o m b i n a t i o no ft r a c i n gm e t h o da n dt o p o l o g yi n f o r m a t i o n ，a n d p r e s e n ta l lo p t i m i z e do f f s e ts s ia l g o r i t h m t h eo p t i m i z e da l g o r i t h mp r e - p r o c e s s e s s u r f a c e st oa c h i e v ema n dd e c i d e sc a l c u l a t i o ns t r a t e g yo f s t a r t i n gp o i n t sb y a n a l y z i n gt h ep r o p e r t i e so f t t po nt h es u r f a c e a c c o r d i n gt h et o p o l o g yo fi n t e r s e c t c h i v e ，i td y n a m i c a l l ya d j u s tt h el o c a lt r a c i n gs t r a t e g yt or e d u c et h es s ic o m p u t a t i o n t i m e i tc a no v e r c o m et h e d e g e n e r a t e c o n d i t i o n ss u c h a s l o o pl e a k i n g a n d s i n g u l a r i t i e s b a s e do no f f s e ts s ia l g o r i t h m ，t h ed i s s e r t a t i o np a ye m p h a s e so nm o t i o n a ls s i p r o b l e m i tu s e sp r o p e r t i e so fm o t i o n a i s u r f a c et of r e dt h ema n dp r o p o s e sa n o p t i m i z e dm o t i o n a ls s ia l g o r i t h m t h ea l g o r i t h r na l s oc a nr e d u c ec o m p u t a t i o nt i m e a n do v e r c o m et h ed e g e n e r a t ec o n d i t i o n s a f t e ra n a l y z i n gg e n e r a ld a t as t r u c t u r eo fc u r v e ds o l i dm o d e l i n g ，i tp r o p o s e sa b o o l e a n o p e r a t i o na l g o r i t h m f o rm o t i o n a lc u r v e ds o l i dm o d e l i n g ，t h eg o a lo f a l g o r i t h mi st oe r l s i , r ee f f e c t i v e l yr o b u s t l ya n da c c u r a t e l y t h et o p o l o g y a n d g e o m e t r y o fs o l i di s r e p r e s e n t e db yt r i m m e dc u r v es u r f a c ea n dh a l f - e d g ed a t as t r u c t u r e i t a _ d p l i e st h ec o n t i n u o u ss s im e n t i o n c da b o v et om o t i o n a is o l i db o o l e a no p e r a t i o n ，a n d u s e st h es i m i l a r i t yo fi n t e r s e c tc l , l r v et os i m p l i f ys s i p r o b l e m ，i tc a n s a v ec o m p u t a t i o n t i m e a tt h es a m e t i m e h i e r a r c h yi n t e r s e c t i o ni sa p p l i e df o r u n i f i e dc l a s s i f i c a t i o n ，a n d f o rt r a c i n gt h ei n t e r s e c t i o nc u l v et oo v e r c o m ed e g e n e r a t ec a s e st h a to c c u rf r e q u e n t l y i np r a c t i c e t h ed i s s e r t a t i o na i s oe x t e n d si tt ob o o l e a no p e r a t i o n sf o rn o n - m a n i f o i d 摘要 t om e e tt h ed e m a n do fs o m et i m e e r i t i c a ls i t u a t i o n t h ed i s s e r t a t i o np r e s e n t e da d i s t r i b u t e da l g o r i t h mf o rb o o l e a no p e r m i o n so fc u r v e ds o l i d s t h em a i nw o r ko ft h e a l g o r i t h me x t r a c t st h ep a r a l l e l i s ma ta l ls t a g e s ，a n dad y n a m i cl o a db a l a n c i n gs t r a t e g y i su s e d a l l o c a t e sw o r k st od i f f e r e n tc o m p u t a t i o nk n o ti n1 0 c a ln e t w o r k i ti m p l e m e n t s f ld i s t r i b u t e dm o t i o n a lc u r v e ds o l i db o o l e a n o p e r a t i o n i nl o c a ln e t w o r k t h e d i s s e r t a t i o nm o d i f i e st h ea b o v ea l g o r i t h mt os u p p o r tm o t i o n a lb o o l e a no p e r a t i o n so f c u r v e ds o l i d k e yw o r d ：c o m p u t e ra i d e dg e o m e t r yd e s i g n ，s u r f a c es u r f a c ei n t e r s e c t i o n ，o f f s e t s u r f a c e ，m o t i o n a ls u r f a c e ，t o p o l o g yt r a n s m i tp o i n t ，d i r e c t e dd i s t a n c e ，s o l i d m o d e l i n g ，t r a c i n gm e t h o d ，h a l f - e d g ed a t as t r u c t u r e ，e u l e r - o p e r a t i o n ，t r i m m e d s u r f a c e d i s t r i b u t es y s t e m , l o a db a l a n c e s t r a t e g y 浙江大学博士学位论文： 雕塑实体造型系统中连续变化术交问题的相关技术研究 第一章绪论 【本章摘要】本章对实体造型系统中的实体的表示模型、曲面求交技术、连续变化曲 面求交技术的背景、发展现状进行了综述。 c a d 技术产生于5 0 年代，在c a d 出现的初期，只被用于单纯的绘图，d 即绘图( d r a f t i n g ) ，而非设计( d e s i g n ) ，所以它只是传统绘图板在计算机上的 延伸。丽目前c a d 已远远超出了计算机辅助绘图的范畴，早已提升到了辅助设 计的高度，计算机辅助设计( c a d ) 技术是作为一门计算机应用学科而产生发展 起来的，是计算机应用的一大重要分支，其作用是帮助设计人员进行工程或产品 设计。随着全球工业的发展，c a d 领域也逐渐走向成熟，现已达到实用并趋于 成熟。 1 1c a d 历史回顾 c a d 作为一门学科起步于六十年代，但由于计算机本身发展的局限，应用 于工程的程序一般都是以批处理的形式出现，而且大多数仅限于工程计算，很难 实现如今c a d 系统普遍具有的用户交互能力，第一个具有划时代意义的c a d 系统是由s u t h e r l a n d 于1 9 6 3 年研制的二维绘图系统s k e t c h p a d 【s u t 6 3 】，尽管该系 统只具备简单的绘图功能，但这在当时被认为是一项超时代的工作。 进入七十年代，随着图形学技术的发展，在计算机上实现用户图形交互已成 为可能。1 9 7 3 年，b r a i d 研制成了第一个实体造型试验系统 b r a 7 3 1 ，此后他吸 收了b a u m g a r t 在研制机器人视觉景物造型系统g e o m e d 中的多面体建模技术 【b a u 7 4 】，逐步建立起用边界表示( b r e p ) 生成三维实体的理论体系，终于在 1 9 7 8 年开发了第一个实体造型软件r o m u l u s 施i 是限于当时计算机的硬件设备昂 贵和低效，整个七十年代c a d 仍缺乏广泛的应用。真正意义上的c a d 则是开 始于八十年代初，由于大规模集成电路的飞速发展，导致了计算机性能的极大提 高和生产成本的大幅降低，使得具有高性能的微机和工作站的价格能为广大企业 和用户所接受，再加上功能强大的外围设备，如大型图形显示器、绘图仪、激光 打印机的问世，从而促进了c a d 的深入发展和广泛应用，c a d 技术已进入实用 化阶段，广泛服务于机械、电子、宇航、建筑、纺织等的产品设计、造型设计、 结构设计、工艺过程设计等环节。到八十年代中期，出现了象i c a d 基于知识的 c a d 系统 w a n 9 0 ，这些系统基于a i 技术有效地将专家的设计制造知识应用于 实际设计过程，在相似产品设计方面，显示了较强的优势。当然，i c a d 不同于 开始于七十年代末、八十年代初的智能c a d 概念，它仍局限于产品的形状设计， 第一章蜡论 而根据y o s h i k a w a 的概括，作为智能c a d 在功能上应具有以下三个特征 y g 8 9 ： 完整性：在设计过程中的各个阶段均能辅助设计师的设计活动； 灵活性：对于设计过程中所涉及到的任何设计对象均能为设计师提供辅助手 段； 集成性：可于其他相关的信息处理系统如c a p p 、c a m 系统等协同运作。 目前，智能c a d 仍处于探索研究阶段。 八十年代末，出现以p r o e n g i n e r 为代表的参数化特征造型系统则成了新一 代c a d 系统的象征，它被认为是c a d 发展史上又一次质的飞跃。它以实体模 型为基础，提供用户特征设计手段，以参数驱动模型，允许设计者自由修改这些 参数，大大简化了产品的造型过程，并且极大地方便了系列产品的设计过程。正 是由于参数化特征造型技术的这种优越性，p r o e n g i n e e r 从推出一开始就广泛地 受到欢迎，p t c 公司也以该产品使之从一个名不见经传的小公司发展成目前 c a d 行业的第一大公司。p r o e n g i n e e r 的成功使得其他c a d 厂商也纷纷仿效， 使其产品具有参数化特征造型功能，目前做的较为成功的有s o l i d w o r k s ， u n i g r a p h i c s ，i - d e a s 和c a d d s 5 等。 1 2 实体模型技术 在传统的机械设计与加工中，技术人员通过二维工程图纸交换信息。使用计 算机以后，所有工程信息，如图形、尺寸、符号等，都是以数字形式存取和交换。 计算机图形的生成与手工在图板上绘图不同，必须先建立图形的数学模型和存储 数据结构，通过有关运算，才能把图形储存在计算机中或显示在计算机屏幕上。 正是由于将工程信息数字化，才使得计算机辅助工程的各个环节( 设计、分析计 算、工艺规划、数控加工、生产管理，即c a d c a e c a p p c a m 等) 使用同一个 产品数据模型，共享信息，从而实现c a d c a p p c a m 系统的集成。 自然界是一个由众多类婆i 三维几何形状构成的集合体，因此，在c a d c a m 系统中，三维几何造型技术引起了人们的极大关注。7 0 年代初期开始研究用计 算机直接描述三维物体的有效方法。伴随着各种c a d c a m 系统的更新换代， c a d c a m 所基于的几何模型也不断推陈出新，在c a d 刚刚起步时( 5 0 年代末一6 0 年代1 常用的几何模型是三维线框结构，它以线段、圆、弧及一些简单的曲线为 描述对象，利用产品形体的棱边和顶点来表示产品的几何形状。在这个时期，c a d 技术的出发点是用三视图来表达零件，以工程图纸为介质来进行技术交流，这就 是典型的二维计算机绘图技术。而对二维软件而言，线框模型的实现手段较为简 单，便于处理，具有图形显示速度快、容易修改等优点，因而得到了大量的应用。 然而由于线框模型的固有缺陷，它只能表达简单的几何信息，不能有效地表达几 浙江大学博士学位论文： 雕塑实体造型系统申连续变化求交问题的相关技术研究 何数据间的拓扑关系，对于同一时期兴起的数控加工技术不能提供形体的表面信 息，c a m 无法实现。为了满足复杂曲面造型及实体造型的需要，针对线框模型 的这些不足，相继出现表面造型和实体模型，表面造型是在线框造型的基础上发 展起来的，它用有向棱边围成的部分来描述形体表面，用形体表面的集合来定义 形体。表面造型的产生应归因于航空业与汽车业的迅猛发展。由于飞机及汽车制 造中遇到的大量自由曲面问题，在当时只能用多截面视图和特征纬线的方法来表 达，在制造上依赖于用油泥模型来近视模拟曲面，因而人们开始研究新的更先进 的描述手段光滑曲面，对此贡献最大的是法国的贝塞尔( b e z i e r ) ，他于1 9 7 1 年发明了一种用控制多边形定义曲线和曲面的方法；8 0 年代后期皮格尔( p i e 9 1 ) 和蒂勒( t i l l e r ) 提出非均匀有理b 样条( n t r r b s ) 方法，并成为当前自由曲线和曲面 描述的最广为流行的技术。n u r b s 可统一表示初等解析曲线和曲面以及有理与 非有理b e z i e r 、非有理b 样条曲线和曲面。由于表面造型比线框造型增加了有关 面边( 环边) 信息以及表面特征、棱边的连接方向等内容，从而可以满足曲面求交、 线面消隐、明暗色彩图、数控加工等应用，使在c a d 阶段建立的模型数据在c a m 阶段可用，表面造型在工程中得到广泛的应用。但由于曲面模型只能表达形体的 表面信息，对有限元及零件的物性计算等方面无从开展，满足不了工程优化设计 的需求。随着技术的进步，计算机辅助工程分折( c a e ) 的需求日益高涨，c a e 要 求能获得形体的完整信息，而线框和曲面模型对形体的表述都不完整，在此背景 下提出了实体造型技术。相比线框造型，实体造型增加了实体存在侧的明确定义， 给出了表面间的相互关系等拓扑信息。因而能够精确表达零件的全部属性，有助 于统一c a d 、c a m 和c a e 的模型表达，在设计和加工上可以减少数据的损失， 保持数据的完整性。实体造型常用的表示形式有构造实体几何( c s g ) 表示、边界 表示( b - - r e p ) 和扫描表示，其中最关键的运算有形体的求交运算、集合运算和欧 拉操作。实体造型技术起源于6 0 年代末，商用化始于1 9 7 9 年，s d r c 推出了世 界上第一个完全基于实体造型技术的c a d 、c a m 和c a e 一体化的软件 i - d e a s 。在实体造型技术上最成功的当属c v 公司。 上述三种模型的优缺点如表1 1 所示，事实上，为克服单模型的局限性， 在实用化的c a d 系统中经常会将这三种模型混合统一使用 w e i 8 8 ，m s n k 9 0 。 模型表示应用范围局限性 二维线框= 维绘图无观察参数的变化，不可能产生有 实际意义的形体 三维线框二维、三维线框绘匿不能表示实体，具有= 义性 曲面模型艺术图形，形体表面的表示数控加工不能表示实体 实体模型物性计算，有限元分析，稍用橐合运算构造形体只能产生正则形体，抽象形体的层 次较低 表1 1 表示形体的线框、曲面、实体模型比较 第一章绪论 1 。3 雕塑实体模型的表示方法 在六十年代末、七十年代初，v o e l k e r 等人 a p p 6 8 ，g n 7 1 ，v o e 7 4 ，v r 7 7 ，v o e 7 8 引入三维实体模型作为曲面模型的一种替代实现三维实体在计算机中的表示。实 体模型包含了足够的信息用于明确定义表面的哪一侧属于实体，所以它可以区分 空间点和实体之间的归属关系，解决了曲面模型等以往模型无法解决的物性计 算、有限元分析等问题。三维实体建模在计算机内部的表达方式( 数据的逻辑结 构) 有多种，常用的有边界表示法b r e p 、构造立体几何法c s g 、混合模式b r e p + c s g 和空间单元表示法。 1 3 1 构造实体几何法 构造实体几何法的基本概念是由r o c h e s t e r 大学生产自动化研究组v o e l c k e r 和r e q u i c h a 等人首先提出。构造实体几何( c o n s t r u c t i v es o l dg e o m e t r y ) ，简称 c s g 。c s g 使用一组有限的实体基元( s o l i dp r i m i t i v e s ) ，一组几何操作和一组布 尔操作( b o o l e a ns e t ) 来表达对象。通常c s g 树表示为一个二叉树，该树的叶 结点表示参与构造的一些基本体素，而中间结点代表了两棵子树的布尔操作。二 叉树的根结点即为所构造的物体。图1 1 为c s g 树实现一个圆柱体上放置一个 l 型物体的实体模型。 图1 1 一个实体的c s g 树 图1 - - 2 c s g 树对应的图形 h o f f m a n n h o f 8 9 定义了一些标准通用的实体基元有棱柱、球、圆柱体、圆 锥体和园环五种。一个基于c s g 树的造型系统中的基本体素是远远不止这些。 例如，b r l - - c a d d m 9 9 系统中，基本体素包括了椭球体、一般锥体、四面体 和其他一些体素 d m p 8 9 。这些体素是h o f f m a n n 定义基本体素的一种更加一般 的表现形式。例如，一般锥体包含了圆锥体和圆柱体，b r l - - c a d 系统中的三 种基本体素包含了所有h o f f m a n n 定义标准体素的全部，这样的体素库可以构造 出非常复杂的物体。 c s g 技术通过布尔运算将基本体素以一定的顺序来构造出复杂的形体。整 浙江大学博士学位论文： 雕塑实体造型系统中连续变化求交问题的相关技术研究 个造型过程则简单地表示为一棵二叉树，布尔运算包含了实体的并、交和差操作， 它不是传统意义上标准的并交差运算。它是正则的并、交、差运算。一个正则的 操作通常在标准操作符号后加星号( ) 加以表示，因此，正则的并、交、差可以 分别表示为u 、n + 、一，正则操作不考虑非正则操作中涉及到的孤立面、孤立 边和孤立点问题，图1 3 是一个说明它们之间区别的二维例子。虽然正则操作 不能保证产生的结果是一个流形体，但它可以保证操作的结果是一个闭合体或者 空集。 图1 3 二维正则布尔操作和非芷则布尔操作的区别 在基于c s g 描述的造型系统中，c s g 树还加入了坐标变换结点，物体子部 件可以在自己的局部坐标系中进行设计，然后通过坐标变换重新调整子部件的空 间摆放位置，它和其余子部件在不间的坐标系中进行布尔操作，产生最终的结果 物体。常用的坐标变换有平移、旋转和缩放。任何的空间变换都可以用这三种变 换进行组合而得到。由于坐标变换可以透过变换矩阵乘法进行合成，因此，在二 叉树模型中，变换数据可以从根结点传递到叶结点，如果采用变换传递的方法实 现坐标变换，那么，在c s g 造型系统中只需要对初始体素进行坐标变换，这样 比采用直接对合成中间物体进行变换简单多了。 形体的边界可通过边界定值计算的方法描述，边界定傻决定哪些组成面应被 裁去，哪些棱边或顶点被生成或被删除，边界元素重叠或位置一致时，边界定值 就把它们合并成一个简单元素。这样，就能用一个前后一致、无冗余的数据结构 描述一个实体边界。两个相连实体的相交处产生新的交线，通过边界定值能找出 这些交线，并对新实体实际棱边的交线( 新的交线在棱边与表面的交点处终止) 进行分类定义、然后对各顶点重新分类。 新实体各表面是由被连接的实体相交面产生，可以生成新的棱边及顶点，也 能删除某些类型的元素。用构造实体几何法描述复杂实体是十分简洁的，而且生 成速度很快，从实体表示法到边界表示法的转抉则需要进行大量计算( 包括整体 性计算、图形显示模型计算和其他应用内容) 。c s g 表示法与机械装配的方式类 似。对机械产品来说，先设计制造零件，然后将零件装配生成产品。用c s g 表 示构造几何形体时，则是先定义体素，然后通过布尔运算将体素拼合成所需要的 几何体。因此，一个几何体可视为拼合过程中的半成品，其特点是信息简单，处 5 第一章绪论 理方便，无冗余几何信息，并详细记录了构成几何体的原始特征和全部定义参数， 必要时还可以附加几何体和体素各种属性。c s g 表示的几何体具有唯一性和明 确性，但一个几何体的c s g 表示和描述方式却不是唯一的即可以用几种不同 c s g 树表示。c s g 表示法对于自动加工生产有着潜在的意义。 i 3 2 边界表示法b r e p 边界表示法b r e p ( b o u n d a r y r e p r e s e n t a t i o n s ) 是以物体边界为基础，定义和 描述几何形体的方法。这种方法能给出物体完整、显式的边界描述。其原理是： 每个物体全都由有限个面构成，每个面( 平面或曲面) 由有限条边围成的有限个 封闭域定义。或者说，物体的边界是有限个单元面的并集，而每一个单元面也必 须是有界的。用边界法描述实体，必须满足一定条件。一个理想、有效表面的条 件是：封闭、有向、不自交、有限和相连接，并能区分实体边界内、边界外和边 界上的点。 边界表示法强调物体的外表细节，建立了有效的数据结构，把面、顶点的信 息分层记录，并建立了层与层之间的关系。分层记录的信息包括相互独立相互联 系的两部分：一组是几何信息，一组为拓扑信息。几何信息是指欧氏空间中的位 置和大小，包括点的坐标，曲线和曲面韵数学方程等：拓扑信息是指几何体顶点、 边、面的数目、类型以及相互间的连通关系。根据这些明确的记录信息，可以知 道几何体表面的范围及其邻接情况。 为了有效地表示几何体的拓扑关系，斯坦福大学鲍姆加特( b q b a u m g a r t ) 于7 0 年代创造性地提出了翼边结构的方法，即以边为核心，每条边有上下两个 顶点，左右两上领面( 左邻面与右邻面) 以及与两个顶点相连的另外四条边，这 些边分别从两个领面的已知边出发，有规律地查询这个几何体的所有面、边和顶 点。 边界表示法允许绝大多数有关几何体结构的运算直接用面、边、点定义的数 据实现。这有利于生成和绘制线框图、投影图、有限元网格的划分和几何特性计 算，容易与二维绘图软件相衔接。实全的边界是实体与周围环境的主要界面。它 的外观决定于表面性质：形状、颜色纹理，即使是透明体，边界表面也影响光的 反射。实体的边界面也是指它与其它实体相接触的地方，如制造加工过程就是刀 具轨迹的包络面切除零件毛坯的过程。因此，实体的边界模型在实际工程得到了 广泛的应用。 实体造型技术是把自然界中的物体表示为计算机上处理的数据处理方法。它 的一个重要方面是如何构造实体模型，上面我们简单的讨论了物体在c a d 系统 浙江大学博士学位论文：雕塑实体造型系统申连续变化求交问题的相关技术研究 中的主流表示模型b - - r e p 和构造实体几何法，这两种方法可以有效的在计算机 中表示空间物体，但是为了构造复杂的三维实体，实体之间的布尔运算( 正则并、 交、差运算) 是必不可少的，早期基于b - - r e p 模型的造型器只支持多面体实体 模型，二次曲面模型和它们的布尔操作，在近十多年，在商用的c a d c a m c a e 系统中，自由曲面( 雕塑曲面) 显得越来越重要，大批的科研工作者t k a l 8 2 ，j a r 8 4 ， c k 8 3 ，v p 8 4 ，k g l 8 4 ，f h 8 5 ，f a r 8 6 对于把实体模型和几何数据进行集成进行了大 量的研究，对于建立基于雕塑曲面的实体表示模型和布尔操作，h o f 8 9 ，r r 9 2 ， c s 8 5 ，c a s 8 7 ，w e i 8 5 ，r v 8 2 ，c h a 8 7 ，m e n 9 2 做了大量的工作。但是在雕塑实体模 型上进行鲁棒、有效和快速的布尔操作一童以来是一个很大的难题，而在布尔操 作中最基本，最难实现的是实体表面之间交线的求取。h o f f m a n n h o f 8 9 1 ：”表示 和计算参数曲面片的交线是非常困难的，它阻碍了雕塑实体模型的发展”。 1 4 曲面求交技术 工业界迫切需要雕塑实体模型来表示一些具有自由曲面的c a d 产品，当时 出现了一些小的实验性c a d 系统，它们简单的支持一些雕塑曲面造型功能。 c h i y o l u r a 等 c k 8 3 第一次在他的d e s i g n b a s e 系统中引入了自由曲面，该系统具 有一定的曲线和曲面能力。但是在该系统中实体之间的布尔操作涉及到的曲面、 曲线求交问题都采用多面体的方法。o e i s o w g - e i 8 3 把曲面交线映射到平面，并 且使用子分的方法解决曲面求交问题。 r e q u i c h a 和v o e l e k e r r v 8 5 1 等人在 r o c h e s t e r 大学开发了p a d l 系统，该系统支持多面体实体模型和一些简单的曲 线功能。c a s a l e 等 c s 8 5 ，c a s 8 7 ，c b 8 9 】使用裁剪曲面产生雕塑实体的b - - r e p 表 示，该算法采用子分方法计算曲面交线，并且用精确的直线段表示裁剪边界， c h a n c h a 8 7 使用了二次曲面的特性和其他自由曲面设计工业部件。为了支持雕 塑实体设计，大量的技术 v p 8 4 ，k g l 8 4 ，t a w 9 1 ，s a t9 1 ，m e n 9 2 ，d u f 9 2 弓i 入 到了c a d 系统中，例如区间算术和s h e l l 表示法等。在这些系统中曲面之间交 线的求取采用了折中处理方法，其中有利用多面体来逼近曲面，然后利用现有的 多面体求交算法，这样曲面的精度没有办法达到工业设计的要求，而且数据模型 的数据量明显的增加。由于当时任何的系统没有真正解决实体模型布尔操作中涉 及的效率和稳定性瓶颈一曲面交线的求取。所以，当时的系统都不是真正意义上 支持自由曲面设计的c a d 系统。 在早期提出可以处理雕塑曲面求交的算法中，其中一些在处理速度上达到造 型系统要求的算法，通常缺少一定理论基础。而且这样的算法很难在一些复杂的 曲面上操作成功，而另外具有理论性基础的算法需要大量的计算时间，这对于交 互式的c a d c a m 系统来说是不允许的。 根据上面的评析可知，求两条参数曲线的交点和两张参数曲面的交线是计算 第一章绪论 机辅助几何设计及加工的一个基本问题。在实体造型中，无论是单体素拼合还是 表面形态描述法，都会遇到这类求交问题；至于在图形绘制和图纸输出中，更要 解决大量求交问题。由于c a d c a m 中大多数曲线曲面是用多项式或有理多项 式来表示的，它们的交就是这些多项式或有理多项式的方程组的解集，从而求交 从数学上来说属于非线性问题，是一个难题。对曲线曲面求交问题的最早的研究 可以追溯到古希腊时期，但是到目前为止，曲面求交中还有很多问题没有得到很 好的解决。十九世纪六十年代以前，曲面求交算法只停留在低阶曲面的实用化方 法研究，对于高阶曲面交线求取算法的研究只停留在理论性阶段，远远没有达到 实际应用的要求。解决这一难题的传统方法有代数法、微分方程法、几何法、同 伦法等。代数法主要适用于隐式和参数式分别表示的曲线曲面之间求交，对于参 数式表示的曲面求交问题，可以将参数式的各个分量代入隐式化，可以得到交线 的隐式表示，进一步用牛顿迭代法得到交线的数值解；微分方程法是构造微分方 程系统，使得满足某个初值条件的解就是欲求的曲面交线；几何法只适用于二次 曲面等特殊曲面，利用与坐标系无关的性质求得曲面交线。例如l e v i n l e v 7 9 1 证明了两张二次曲面的交线恒位于一个平面、对平面、双曲柱面、抛物柱面、 双曲抛物面这五种曲面之一上；同伦法利用多项式方程组所有解的原理，从简单 方程出发，逐步修正方程以逼近欲求的解。而随着计算机的出现和应用，诞生了 离散( s u b d i v i s i o na l g o r i t h m ) 求交和跟踪( m a r c h i n ga l g o r i t h m ) 求交这鼯大技术。 1 9 8 0 年，l a n e 和r i e s e n f e l d l r 8 0 首次提出了b e z i e r 和均匀b 样条曲线曲 面的离散求交方法，接着c o h e n ，l y c h e 等又提出了非均匀b 样条曲线曲面离散 求交的o s l o 算法 c l r s 0 。l a s s e t l 髂8 6 】，h o u g h t o n h e f s 8 5 ，d o k k e n d o k 8 5 等 也对离散求交技术作了深入的研究。离散求交法的基本思想是分割曲线进而化 “直”，分割平面进而化“平”。即把曲线分割成许多小段，直至每- , b 段都平直 得可以近似地当作直线，从而把曲线求交变换为折线求交；同样地，把平面分割 成许多小曲面片，直至每- 1 1 , 片都平坦得可以近似地当作平面片，从而把曲面求 交变化为一系列平面片的求交。由此可见，曲线曲面离散的算法和终判准则是离 散求交的两个关键问题。与传统的迭代法相比，离散求交的优点是能求得曲线曲 面的所有交点，没有遗漏现象；没有迭代过程；避免了导数的计算；简化了计算 程序，充分发挥了控制网格的作用。但是离散法也存在着难以克服的问题，分支 跳跃、漏掉内部交线环和拓扑连接混乱等问题一直困扰着离散法。最近几年仍有 大量的文献 w i l 8 5 ，s n 9 1 ，r r 9 2 ，r v 9 2 ，h o h 9 2 ，k m 9 4 ，h m p y 9 7 ，g k 9 7 ，t d l h 9 9 ，t d 0 0 讨论进行曲面求交计算，现行主要的曲面求交方法可以分为解析法、网格计算法、 跟踪法、隐函数法和分割法。隐函数法只对支持隐式曲面表示的c a d 系统适用， 解析法只能求取低阶曲面的交线，对于复杂的雕塑曲面解析法无能为力，剩下的 方法被广泛的应用于曲面求交，但是它们都是一些数字离散算法，它们计算所得 浙江大学博士学位论文：雕塑实体造型系统中连续变化求交问题的相关技术研究 的交线都是曲面交线的数值近似解，因此都存在难以解决的公差设置和求解精度 问题 t d 0 0 1 。跟踪法利用曲面的局部特性指导交线下一个交点的搜索，简化了求 交算法的设计复杂度。已经成为现行c a d 系统中曲面求交的主要方法，但是两 张曲面的交线可能是开曲线，也可能是闭曲线。开曲线的端点或同时在两张衄面 的边界向上，或在一张曲面的边界线上。若两张已知曲面的交线全为开曲线，则 只要取它们边界线上的一个交点为初始点，用跟踪法可以快速求得所有的交线。 但是闭曲线一般位于两个曲面片内，无端点可言，所以采用跟踪法求交时可能被 遗漏掉，防止遗漏的方法是化闭为开，一旦发现交线有可能为闭曲线时，就将曲 面分割为若干片子曲面，使得在各个子曲面间的交线是开曲线，继而求出各段开 曲线，再首尾相连形成闭交线。显然化闭为开的前提在于判断闭交线的存在，判 断闭交线是否存在的算法通常称为环检测，因此环检测和跟踪法结合可以高效、 鲁棒、精确的求取曲面交线，一般结合算法分