（机械设计及理论专业论文）catmullclark细分曲面的实现及求交技术研究.pdf

大连理工大学硕士学位论文 摘要 随着工业产品的设计不断朝着多样化、特殊化、拓扑结构复杂化方向发展，现在的 参数曲面造型方法的局限性越来越明显，因为参数曲面表示方法在构造复杂拓扑结构的 物体表面时，需要对曲面片进行裁剪或拼接，不仅费时，而且有数值误差。而细分曲面 可以克服参数曲面的不足，能够表示任意拓扑结构的曲面，算法简单，已经成为研究热 点。在诸多细分模式中，c a t m u l l c l a r k 细分曲面的正则形式是三次均匀b 样条曲面， 能够与n u r b s 曲面相互转化，最有可能应用于未来的c a d c a m 造型系统。当然，要使其 真正应用到c a d c a m 系统中还有很多问题要解决，细分曲面的求交就是其中很关键的问 题之一。本文就是针对c a t m u l l c l a r k 细分曲面，对其求交进行研究，为三维曲面造型 和数控加工奠定基础。主要工作如下： 1 用c + + 、o p e n g l 编程实现c a t m u l l c l a r k 细分算法。使用一种简单的数据结构， 首先对每个顶点进行编号，控制网格的边和面，存储其顶点的编号的信息，便于在细分 的过程中，根据边和面找到其对应的顶点编号，从而获得点的信息，最后给出了算法实 现的实例。 2 应用轴向包围盒和二部图对c a t m u l l c l a r k 细分曲面进行相交性检测。对以控 制网格曲面片卜邻域的所有顶点建立轴向包围盒，对可能相交的曲面片将其编号存储于 二部图。随着细分层次的加深，根据上一层次的二部图进行相交性检测，并建立新的二 部图。 3 提出以二面角为精度控制方法进行交线计算。当控制网格的某一曲面片逾期卜 邻域曲面片的夹角的最大值满足给定的精度时，停止细分，根据四边形曲面片的几何关 系求出交点，将交点相连，得到满足给定精度要求的两个细分曲面之间的相交曲线。 关键词：c a t m u l l - c l a r k 细分；轴向包围盒；二部图；求交技术 c a t m u l l - c l a r k 细分衄面的求交技术研究 r e s e a r c ho ni m p l e m e n t a t i o na n di n t e r s e c t i o nt e c h n o l o g yo f c a t m u l l c l a r ks u b d i v i s i o ns u r f a c e a b s t r a c t w i t ht h ed e v e l o p m e n to ft h ei n d u s t r i a lp r o d u c t sd e s i g nh e a d i n gi n t od i v e r s i f i c a t i o n , s p e c i a l i z a t i o n , t o p o l o g yc o m p l i c a t i o n , t h ep a r a m e t e rs u r f a c e sl i m i t a t i o ni sb e c o m i n gm o r e a n dm o r eo b v i o u s t r i m m i n ga n dj o i n i n go fp a t c h e sa r en e e d e dw h i l ec o n s t r u c t i n g c o m p l i c a t e dt o p o l o g ys u r f a c e s 埘t 1 1t h em e t h o do fp a r a m e t e rs u r f a c e ，w h i c hi s n o to n l y t i m e c o n s u m i n g , b u ta l s oh a sd a t a - e r r o r c o m p a r i n g 研mt h ep a r a m e t e rs u r f a c e s ，s u b d i v i s i o n s u r f a c ec a r lc o n q u e rt h ed e f i c i e n c ya b o v e ，d e s c r i b e sa r b i t r a r yt o p o l o g ys u r f a c ea n dh a s b e c o m eah o t - l l i t a m o n gc u r r e n ts u b d i v i s i o ns c h e m e s ，t h er e g u l a rf o r mo fc a t m u l l - c l a r k s c h e m ei sb i c u b i c b s p l i n es u r f a c e ，a n dc a nb et r a n s f o r m e di n t on u i 出s t h e r e f o r e c a t m u l l - c l a r ks c h e m ew i l lm o s tp o s s i b l yb eu s e di nt h ef u t u r ec a d c a ms y s t e m s b u t t h e r ea r es t i l lm a n yp r o b l e m st os o l v eb e f o r ei t su s ei nc a d c a ma n di n t e r s e c t i o ni so n eo f t h ec r u c i a lp r o b l e m s t l l i st h e s i sm a i n l yr e s e a r c h so nt h ec a t m u l l - c l a r ks u b d i v i s i o ns u r f a c e s i n t e r s e c t i o n ，w h i c hi st h ef o u n d a t i o no f3 ds u r f a c em o d e l i n ga n dn ct o o lp a t hg e n e r a t i o n t h em a i nc o n t e n t sa r ea sf o l l o w s ： 1 c a t m u l l - c l a r ks c h e m ei si m p l e m e n t e di nt h ec o m p u t e rw i t hc + + a n do p e n g l 弧e d a t as t r u c t u r ei ss i m p l ea n dc o n v e n i e n t f i r s to fa l l ，e a c hv e r t e xi st a g g e d 谢n 1an u m b e r t h e n t h ei n f o r m a t i o no fc o r r e s p o n d i n gv e r t e x e sf o re a c hl i n ea n de a c hf a c ei ss t o r e d ，s ot h a tt h e i n f o r m a t i o no fv e r t e x e sc a l lb ee a s i l ya c h i e v e da c c o r d i n gt ot h ec o r r e s p o n d i n gl i n ea n df a c e d u r i n gt h es u b d i v i s i o np r o c e s s f i n a l l y ，a l le x a m p l ei sd e m o n s t r a t e du s i n gt h i ss c h e m e 2 d e t e c tt h ei n t e r s e c t i o no fc a t m u l l c l a r ks c h e m e sw i t ha x i s - a l i g e db o u d i n gb o x e sa n d b i p a r t i t eg r a p h c o n s t r u c ta x i s a l i g e db o u d i n gb o x f o rt h ep a t c h e sa n dt h e i r1 - n e i g h b o u r h o o d v e r t e x e s ，t h e ns t o r et h en u m b e r so ft h ep a t c h e st h a tp o t e n t i a l l yi n t e r s e c t w 池t h ep a t c h e s b e i n gs u b d i v i d e d ，c o n s t r u c tn e wb i p a r t i t eg r a p ha c c o r d i n g t ot h ea b o v eo n e 3 p r o p o s eap r e c i s i o nc o n t r o lm e t h o do fd i h e d r a la n g l ef o ri n t e r s e c t i o n1 i n ec o m p u t a t i o n 珊1 i l et h eb i g g e s ta n g l eb e t w e e nt h ep a t c ha n di t s1 - n e i g h b o r h o o dp a t c h e sc o m e st ot h eg i v e n p r e c i s i o n ，s t o ps u b d i v i d i n ga n dc o m p u t et h ei n t e r s e c t e dp o i n t sa c c o r d i n gt ot h eq u a d r i l a t e r a l p a t c h e s g e o m e t r i c a lr e l a t i o n f i n a l l y ，c o n n e c tt h ei n t e r s e c t e dp o i n t st og e tt h ei n t e r s e c t e d c u r v e k e yw o r d s ：c a t m u l l c l a r ks u b d i v i s i o n ；a x i s a l i g n e db o u n d i n gb o x e s ；b i p a r t i t eg r a p h ； i n t e r s e c t i o nt e c h n o l o g y 大连理工大学学位论文独创性声明 作者郑重声明：所呈交的学位论文，是本人在导师的指导下进行研究 工作所取得的成果。尽我所知，除文中已经注明引用内容和致谢的地方外， 本论文不包含其他个人或集体已经发表的研究成果，也不包含其他已申请 学位或其他用途使用过的成果。与我一同工作的同志对本研究所做的贡献 均已在论文中做了明确的说明并表示了谢意。 若有不实之处，本人愿意承担相关法律责任。 作者签名： 日期：翌& 年三月止日 大连理工大学硕士学位论文 大连理工大学学位论文版权使用授权书 本人完全了解学校有关学位论文知识产权的规定，在校攻读学位期间 论文工作的知识产权属于大连理工大学，允许论文被查阅和借阅。学校有 权保留论文并向国家有关部门或机构送交论文的复印件和电子版，可以将 本学位论文的全部或部分内容编入有关数据库进行检索，耳以采用影印、 缩印、或扫描等复制手段保存和汇编本学位论文。 学位论文题 作者签名： 导师签名： 大连理工大学硕士学位论文 1绪论 近年来，由于三维扫描仪的普及和大规模复杂几何对象在计算机图形学、c a d 和计 算机动画中广泛使用，使得细分曲面( s u b d i v i s i o ns u r f a c e s ) 越来越受到研究者的重视。 因为细分造型技术可以从任意形状的几何网格构造出表面光滑的几何对象，而无需考虑 其几何连通性和拓扑结构。由于采用其它造型方法，如目前比较流行的n u r b s 曲面在表 示复杂的几何对象存在许多难题，而细分曲面造型技术可以方便快速地构造出复杂的几 何对象，因此成为造型技术的研究热点。 曲面求交是c a d c a m 领域最重要同时也是最复杂的问题之一，被广泛应用于曲面裁 剪、数控加工刀位轨迹计算以及实体造型中的拼合等多种运算中。本章就细分曲面以及 曲面求交作一概述，包括细分曲面的起源、国内外研究进展以及目前参数曲面求交的状 况和细分曲面求交的一些探索性研究，随后提出课题研究的意义以及内容。 1 1 细分曲面概述 1 1 1 造型方法简述 曲面造型技术主要研究曲面的表示、曲面与曲面之间求交以及曲面拼接，以及曲面 变形、曲面重建、曲面简化、曲面转换和曲面等距等问题【l 】。在曲面的表示方法上，曲 面造型技术大致可以分为以下几类：多边形造型；隐式曲面造型技术；变形曲面造型技 术；参数曲面造型技术；细分曲面造型技术；其他曲面造型技术等。 多边形造型是用多边形表示或者近似表示物体曲面的物体造型方法，多边形造型非 常适合于扫描线渲染。主要优点是它比其它的表示方法处理速度快，但用多边形表示物 体也有很多缺点。多边形没有办法精确地表示曲面，因此为了实现较好的观察效果必须 使用大量的多边形进行近似，复杂模型的使用带来处理速度的降低。 所谓隐式曲面，是指采用隐式方程 f ( x ，y ，z ) = 0 表示几何对象的表面。当函数f ( x ，y ，z ) 是多项式时，它定义了一张代数曲面。另外隐式 曲面方面的把三维空间分为三个区域，即 f ( x ，y ，z ) 0 因此很容易判别某个点是在曲面的内侧，外侧或曲面上。工程中许多常用的简单曲面， 例如平面、球面、柱面以及环面等都很容易用隐函数表示。虽然隐式曲面具有较好的光 c a l m u l l - c l a r k 细分曲面的实现及求交技术研究 滑性，但是用隐式曲面表示复杂拓扑形体时，需要用到大量的基本体素，用户难以对此 有效控制，这就给交互设计带来一定的困难，所以难以进行形体的细节造型设计。 变形曲面造型技术，b a r r 率先将变形思想引入到几何造型领域，它模拟了力学中 常见的几种变形，如拉伸、均匀张缩、扭转和弯曲等，并给了这些变形的数学表示，应 用b a r r 的方法，可生成许多类型的三维几何形状，由于该法仅能用于特定的几何形状， 一般其为非自由型变形1 2 。以后，许多学者探索如何将变形造型方法融合到传统的 c a d c a m 系统以及如何进行自由变形。1 9 8 6 年，s e d e r b e r g 和p a r r y 提出了一种崭新的 变形算法，称为自由变形( f r e e - f o r md e f o r m a t i o n ) ，简称f f d 3 1 。该算法假定物体具 有很好的弹性，在外力的作用下易于发生变形，应用该法进行造型，需先构造一个长方 体的框架，将物体置于框架之中，当框架受到外力作用而变形时，物体的形状亦随之改 变。s e d e r b e r g 等研究了f f d 方法的连续性控制、局部变形、体积控制以及应用，并得 出了许多有益的结论。变形曲面造型方法特别适用于生成柔软体的几何对象，如海水、 云和脸部表情等，对工程中的自由曲面造型并不适用，工程中常用的是刚性体。目前的 许多商用动画软件如s o f t i m a g e 、3 d m a x 、m a y a 等都有类似于f f d 的功能1 4 j 。 参双口回造型技术主要涉及到参数曲面的表示，是目前c a d c a m 系统中曲面的主 要表示方法。参数曲面是指把曲面或曲线表示成参数的矢量函数形式。它是描述几何形 状的重要工具。最早由c o o n s 、b e z i e r 、f e r g u s o n 、s c h o e n b e r g 等提出并逐步完善，现已 形成一个理论严密、内容丰富具有很大实用价值的图形学领域里的一个分支。它广泛应 用于飞机、汽车、轮船等具有复杂结构的产品表面设计。参数曲面表示主要研究矩形域 上的张量积，或三角域上的b e m s t e i n b e z i e r 曲面。其主要优点有：简洁性，参数曲 面表示通过用少量的控制顶点及形状参数描述曲面的形状及特征，而传统的多边形网格 表示需要用大量的多边形描述几何表面。这对于曲率较大的区域，参数曲面表示方法尤 为突出；灵活的局部修改，参数曲面具有良好的局部可控性；方便的精度控制，对于参 数曲面，可以通过误差分析动态地控制曲面的绘制精度，因而可以方便地生成具有多分 辨特征的几何模型。尽管参数曲面具有以上优点，但是由于它是通过简单的曲面面片拼 接生成复杂几何对象表面，因而参数曲面的拼接往往涉及到复杂的约束求解，使得它在 实际应用中受到一定程度的限制。 随着被设计的几何对象不断朝着多样化、特殊化、拓扑结构复杂化方向发展，参数 曲面的局限性也越来越明显。由于单一的参数曲面仅限于表示在拓扑上等价于一张纸或 一张圆柱面的曲面，因此难以表示复杂拓扑结构的自由曲面。细分方法正是在这种需求 推动下快速发展起来的，细分方法是基于网格细化的离散曲面表示方法，它可以从任意 大连理工大学硕士学位论文 拓扑网格构造光滑曲面。其基本思想是：定义一个网格序列的极限，网格序列采用一定 的细分规则，在给定的初始网格中插入新的顶点，从而不断细化出新的网格，重复运用 细分规则，在极限时，该网格收敛于一个光滑曲线( 或者曲面) i s 。大有后来居上的创新 之势。这种曲面造型方法在生动逼真的特征动画和雕塑曲面的设计加工中如鱼得水，得 到了高度的运用。在1 9 9 8 年s i g g r a p h 会议的报告中，有十篇有关曲面造型的论文，除 了有一篇是介绍几何体的变形方法以外，其余九篇均是关于曲面离散造型的算法或者在 离散型曲面上精确求值及进行参数化的工作。特别是，有三篇论文都与c a t m u l l 和c l a r k 在1 9 7 8 年所创立的用网格细分产生离散曲面的方法( 以下简称c _ c 法) 紧密相关。从这 里我们可以看出当今国际图形界在曲面造型理论研究和实际应用中的热点所在。这三篇 论文是j s i a m 的“c - c 细分曲面在任意参数上的精确求值 【6 】、t s e d e r b e r g 和浙江大 学郑建民的“对c - c 细分曲面作推广的非均匀递归细分曲面川7 1 及t d e r o s e 的“特征动 画中的c - c 细分曲面川引。在1 9 9 8 年荣获奥斯卡大奖的电影作品中，有一个短篇赫然在 列，这就是美国著名的p i x a r 动画电影制片厂选送的作品“g e r i sg a m e ”。动画片描 述了一个名叫g e r i 的老头，在公园里自己对自己下国际象棋，千方百计想取胜的诙谐 故事。动画中人物和景色的造型细致生动，与故事情节浑然一体，使观众得到真正的视 觉美的享受。而这部动画片制作中的曲面设计者就是t d e r o s e 。d e r o s e 在s i g g r a p h 9 8 大会上报告的论文中，讲到选用c - c 细分曲面作为g e r i 老头特征造型模型的背景。 目前确实已经存在一些商用系统，诸如a l i a s - w a v e f r o n t 和s o f t i m a g e 等可以作到这一 点，但是它们至少会遇到以下困难：修剪是昂贵的，而且有数值误差；要在曲面的接缝 处保持光滑，即使是近似的光滑也是困难的，因为模型是活动的。而细分曲面有潜力克 服以上两个困难，它们无须修剪，活动模型的平滑度被自动地保证。d e r o s e 成功地应 用了c - c 细分曲面造型法，同时发明了构造光滑的变半径的轮廓线及合成物的实际技术， 提出了在服饰模型中碰撞检测新的有效算法，构造了关于细分曲面的光滑因子场方法。 凭借这些数学和软件基础，他形象逼真地表现了g e r i 老头的头壳、手指和衣服，包括 茄克衫、裤子、领带和鞋。这些都是传统的n u r b s 连续曲面造型所不易做到的。 1 1 2 细分方法在c a d 造型中的应用 虽然细分曲面在动画造型系统中已经获得了广泛的应用，但是在工程曲面造中的应 用才刚刚起步，这是因为两种应用领域所追求的目标曲面要求不一样，动画造型希望模 型具有较好的光顺性等视觉效果，工程曲面造型要求模型具有较高的几何精度和连续性 等内在质量。对于c a d 系统来说，细分技术还有许多问题需要解决：使用细分方法表示 传统的曲线曲面，以及相互转换；细分曲线曲面的参数化方法、直接计算；细分操作中 的精度控制；细分曲线曲面的裁剪、求交等运算；细分表示的非连续特征；常见造型方 c a t m u u - c l a r k 细分曲面的实现及求交技术研究 法的细分表示；曲线曲面的细分方法重建；细分曲线曲面的等距；自适应细分；高精度 细分曲面快速显示；细分曲线曲面的连续性分析。 在c a d 领域中，常通过插值和逼近手段建立目标曲面。在细分曲面插值方面，已有 的细分曲面插值方法可以分为两类：一种是构造新的细分规则或修改已有的几何规则， 使得细分曲面经过初始控制网格的部分或全部顶点；另一种则是利用已有细分方法，通 过构造适当的初始控制网格使细分曲面满足插值条件。虽然插值型细分曲面( 如蝶形细 分) 具有天生的插值能力，但是插值细分曲面的光顺性并不理想。h a l s t e a d 等人也对逼 近型的c a t m u l l c l a r k 细分曲面上的光顺插值进行了研究，不过该方法所求出的能量在 奇异点处不收敛1 。n a s r 提出插值于d o o s a b i n 细分曲面顶点法向量的细分曲面插值方 法n 们。l e v i n 通过组合细分构造了能插值任意曲线的细分方法，并将其应用于n 边孔洞 的修补问题u 。 在细分曲面逼近方面，多数细分曲面逼近方法与多分辨率分析方法类似，其局限性 是初始控制网格的生成还没有能够做到完全自动化，其中h o p p e 和s u z u k i 对点云数据 的细分曲面逼近进行了一些有益的探索，但是拟合的细分曲面不能准确反映模型的细节 特征f 1 2 1 。m a 研究了基于c a t r n u l l c l a r k 细分的点云数据b 样条曲面逼近方法【1 3 1 。 为了与实体造型系统相融合，细分曲面的求交和裁剪一直是有待于解决的难题。仿 造参数曲面的离散求交方法，n a s r i 曾提出一种基于d o o s a b i n 细分曲面边界生成方法 的d o o s a b i n 曲面求交算法，只是获得近似的细分曲面交线【1 4 】。利用细分曲面的多分 辨率特性，b i e n n a n n 等人对细分曲面的逻辑运算作了尝试性研究【1 5 】。 由于传统细分方法起源于均匀样条，所以无法精确表示工业设计中常用的旋转曲面 和二次曲面。s e d e r b e r g 等人提出的非均匀有理细分方法虽然可解决以上表示问题，不 过非均匀有理细分方法始终存在实现复杂以及数值计算的不稳定性问题，文献 1 6 】对其 进行了连续性分析。虽然m a i l l o t 1 7 】和z h a n g 1 8 j 提出了能生成旋转曲面的细分方法，但 是细分算法都相当复杂。用细分曲面精确表示几何模型仍然是细分曲面应用研究的重要 内容。 1 2 曲面求交概述 1 2 1目前的曲面求交方法 求交问题包括曲面曲面求交，曲面平面求交，曲面曲线求交，曲面直线求交，曲线 曲线求交，曲线直线求交等子问题。其中最重要、难度也最大的当属曲面曲面求交问题， 其他求交问题可以应用曲面曲面求交的思想予以解决。所谓曲面求交就是指给定两张曲 大连理工大学硕士学位论文 面，通过一定的算法求得两张曲面所有交线( 相交情况包括切点和切线) 的过程。曲面 求交算法大致有三点要求：稳定，鉴于曲面求交的重要性，求交算法必须满足稳定性要 求，其中包括不会导致求交失败及能够找到所有交线段；准确，求得的交线必须符合给 定的容差要求，否则得到的交线没有任何意义；快速，由于在c a d c a m 系统中需要进 行大量的求交运算，因此求交算法的运算速度具有至关重要的意义。 国外在这方面的研究始于6 0 年代，发表的论文专著非常丰富。s o u t h 和k e l l y 使用 网格法计算双三次曲面片等高线的方法进行求交【1 9 】。s e d e r b e r g 和o w e n 等提出将参数 曲面转化为代数方程，并应用求解代数方程组的方法来处理参数曲面的求交问题【2 0 l 。 d o k k e n 等人则利用b e z i e r 等曲面所有的离散分割性，利用小平面片逼近的方法纯几何 地处理曲面的交线【2 1 1 。s a b i n 和b a m b i l l 等人提出根据交线的代数几何性质采取迭代和 追踪相结合的方法沿着曲线走向去寻找下一交点，从而提出所有的交线1 2 2 。由于使用单 一的方法无法适应复杂情况的求交，k o p a r k a r 等人提出结合多种方法去解决曲面的求交 问题 2 3 1 。 国内自7 0 年代以来，由于开发几何造型及数控加工系统的需要，对曲面求交问题 也进行了大量的研究工作。北京航空航天大学在7 0 年代完成了用代数法及对分法进行 曲面求交的软件包。彭群生应用离散分割的思想解决b 样条曲面的求交1 2 4 。汪国昭、张 定华提出了适用于b e z i e r 曲面求交的离散分割层次的确定方法【2 5 】。姜寿山、马德昌、雷 毅和陶建伟等在曲面求交领域也作了许多有效的工作【2 6 j 。 曲面可以用代数方程和参数方程两种形式来表达，因此可以将曲面求交问题归纳为 三种类型：代数代数曲面求交；代数参数曲面求交：参数参数曲面求交。对于代数 代数曲面及代数参数曲面求交问题，均可以转化为比较经典的一元高次方程来求解，较 易处理，参数参数曲面求交则较为复杂，无法直接转化为一元高次方程。对于参数曲面 与参数曲面的求交，目前的方法可以分为如下几类： ( 1 ) 代数法，也称为解析法。其主导思想是充分利用有关代数曲面的求交的现有成果， 将其应用到自由曲面的求交中。通常是指将自由曲线曲面的参数表达是精确或近 似地转化为代数方程的形式，从而将参数参数曲面求交问题转化为代数代数曲 面或代数参数曲面求交问题，并利用求解一元高次方程得到交线。这种方法在计 算低幂次( 二次以下) 曲面偏见的交线时可以获得较好的效果。但对于三次以上 的自由曲面，特别是有理曲面的求交，交线代数方程的阶数将非常高，对于一般 参数曲面，这种方法求交，无论是准确性、稳定性还是计算效率均难以保证，因 此实际应用较少。 c a l m u l l - c l a r k 细分曲面的实现及求交技术研究 ( 2 )网格离散法。该法的基本思想是先将瞳面离散为由小平面片组成的网格，当网格 足够细密时，可以认为已经非常接近真实曲面，对分别表示不同曲面的两张网格， 利用平面片求交法求得交线，并以此交线近似代表曲面间的交线，该法原理简明， 便于实现，适用范围广，任意参数曲面均可利用该法求交。但为获得精确的交线， 则必须生成非常细密的网格，这将导致占用内存多，计算花费大。因此，实际工 作中很少单一使用网格法，而常将其与其他方法结合使用。 ( 3 ) 分割法。该法与网格离散法有些相似之处，都是以小平面片的交线代替曲面的交 线，所不同的是分割法不是将曲面直接离散，而是基于d i v i d e c o n q u e r 思想，亦 称测试离散思想，即在对两曲面片离散之前，先利用曲面片的凸包进行相交测 试，并只对凸包相交的曲面片进行细分。将凸包相交的曲面片细分为四个子曲面 片，对两张曲面的子曲面片重复前述过程，直至子曲面片满足求交的精度要求， 而后以平面片的交线代替曲面片的交线。分割法只对可能相交的曲面片细分，既 减少了需要的存储空间，又加快了测试和求交速度，因而其效率显著优于网格离 散法。但分割法需要应用曲面的凸包性和分割性，故仅适用于b e z i e r 和b 样条曲 面，而难以应用于如c o o n s 曲面和等距面等其他参数曲面。分割求交的精度比较 低，这是因为平面片的交线偏离真实交线的误差比较大。实际应用中，分割法也 需要与其他方法结合才能获得比较满意的效果。 ( 4 ) 迭代法。迭代法本身并不能构成一个独立的求交方法，与所有不动点迭代法一样， 应用迭代法求交线之前，首先必须给出交点的初始估计值，而求交的初始估计值 必须通过其他求交方法得到。因此，迭代求交常同其他求交方法结合使用，作为 交点精化的一种手段。迭代法的主要过程是根据初始估计点的几何性质( 如坐标 位置、切矢、法矢、曲率等) 运用n e w t o n 方法得到一个较原估计点更接近于目 标点( 即精确交点) 的估计点。如此反复进行，直到求得的交点满足所要求的精 度。该法的优点是在初值比较好时其收敛速度非常快，而且能应用于任意参数曲 面，因此应用非常广泛，其主要缺点是初值的要求比较苛刻，初值选择不当有可 能导致迭代不收敛。 ( 5 ) 追踪法。追踪法最初是由m e l s o n 和m m a s e s 等人提出，其主要思想是：在已知某 一点位两交面交点的前提下，以该点为起点，沿着交线前进方向搜索下一个交点， 重复上述过程，直至求得交线上的所有交点，该法的优点是适用范围广，可用于 任意参数曲面，而且计算速度快，占用内存少。追踪法的关键是初始点的获得比 大连理工大学硕士学位论文 较困难，如何求得所有交线的初始点一直是人们的研究热点，也是追踪法的关键 所在，初始交点选取不当将导致追踪方法失败。 上述求交方法各有利弊，单纯使用任何一种方法都无法解决应用中可能遇到的各种 复杂情况，正因为如此，扬长避短，综合利用几种方法的思想逐渐为人们所接受，为了 保证实用性，目前的c a d c a m 软件都利用了综合方法。 细分曲面造型是新型的造型方法，目前并未真正用到c a d c a m 技术中，还处于研究 阶段，对于细分曲面的求交，一些学者进行了探索性的研究。下面就细分曲面的求交研 究作一概括。 1 2 2 细分曲面求交研究概况 目前，有关细分曲面求交以及布尔操作的研究文献比较少，国际上也只有n a s r i ， l i t k e ，l a n q u e t i n ，k r i s t j a n s s o n 等人在这一领域做了一些相关的探索。 n a s r i 的d o o - s a b i n 细分曲面求交是在基于d o o - s a b i n 细分曲面边界生成方法的基础 上，对于两张细分曲面控制网格，如果在一给定容差范围内它们都接近平面，则把它们 当作两平面求交，否则，将控制网格进行细分，然后再用递归方求出d o o - s a b i n 细分曲面 的交点刎。 l i t k e 采用组合细分方法对细分曲面进行剪裁，通过对控制网格细分、网格删除、 重新网格化来局部调整裁剪曲线附近的控制网格，虽然该方法能使得两个曲面插值于交 线，解决了n u r b s 中碰到的拓扑不一致与裂痕问题，但是所得到的只是一个近似的裁剪细 分曲面嘲。 l a n q u e t i n 提出细分曲面求交的大致方法有：选择法、网格法、图匹配法等几种， 但是并没有提出完整的求交算法，更没有去实现例。 利用细分曲面的多分辨率特性，b i e r m a n n 等人对细分曲面布尔运算作了尝试性研究， 该算法只能获得逼近结果且算法相当繁琐，离实际应用还很远啪1 。 国内的周海，区士颀，宾鸿赞等对实体初始三角网格进行操作，构造出一个新实体的 初始网格，然后采用l o o p 细分算法完成该实体的光滑曲面造型，在初始三角网格的求交 过程中使用注册机制对所得交点的拓扑约束关系进行分类推理，从而对浮点数值容差导 致的失误进行了有效控制和纠错，他们的细分曲面求交与裁减思路适合于基于三角网格 的碟形细分、3 细分等其他细分方法口卜铋。 郑立垠，张丽，张云鹏主要针对三角网格的细分曲面求交提出了一种有效的交线计 算的方法，该方法适用于任意三角网格的细分曲面中。在利用a a b b 和二部图进行初始控 制网格相交性检测后，利用该方法快速有效地求出细分曲面的交线口副。 c a l m u l l - c l a r k 细分曲面的实现及求交技术研究 郑立垠，张丽主要针对具有凸包特征的细分曲面提出了一种有效的求交的方法，该 方法适用于任意具有凸包特征的细分曲面中。该方法主要是利用二部图跟踪两个细分曲 面中可能相交的面。在应用二部图的基础上，选择半边数据结构，应用轴向包围盒法进 行相交检测，使得具有凸包特征的细分曲面的求交得以实现m 1 。 袁鸿针对基于平面四边形网格的c a t m u l l - c l a r k 细分曲面，在给定精度条件下，把对 细分曲面的求交转化为对一定细分层次控制网格的求交：首先构造两张控制网格上相交 四边形网格带及其卜邻域网格带，然后不断细分相交四边形网格带及其卜邻域网格带， 提高求交精度，其次求解出相交四边形网格的交点，并根据拓扑关系将其顺序连接起来 既得到两细分曲面之间的相交曲线，实现了细分曲面的求交啪1 。 1 2 3 细分曲面求交难点 可以看出目前细分曲面求交的研究比较少，细分曲面求交与参数曲面的求交有着很 大的不同，参数曲面的求交，可以根据其隐函数的形式来判断其是否相交，而细分曲面 并没有解析形式，给求交带来了很大的困难。通过比较参数曲面和细分曲面的研究状况， 可以得出细分曲面求交的难点如下： ( 1 ) 细分曲面没有解析形式，不能通过解方程来得出两曲面的交点的坐标。这是 制约其应用到c a d c a m 的最大的障碍。 ( 2 ) 细分曲面具有细分层次，初始控制网格相交，随着细分层次的加深，其并不 一定相交，初始控制网格不相交，随着细分层次的加深，其也可能相交( 如图1 1 ) 。 是否存在一种尺度来判断初始网格相交，细分过后的网格也相交，目前是一空白，不曾 有学者研究。 ( 3 ) 求交速度的问题。由于细分曲面随着细分层次的加深，细分曲面的曲面片数 量呈指数级增长，使得求交速度成为一重要问题。细分层次越大，需要进行判断是否相 交的曲面片数量也会越多。随着细分层次的加深，如何快速的排除不可能相交的曲面片。 是制约求交速度的重要因素。 ( 4 ) 求交精度问题。目前在细分曲面求交精度方面很少有人提及，只有袁鸿在求 交过程中使用了曲率的精度控制方法，没有统一的求交控制精度方法。精度是求交的关 键因素，若精度达不到，直接制约之后所有的运算，同时也会影响刀具轨迹的生成。 ( 5 ) 相交曲面片区域选择。目前的研究在进行细分曲面的相交性检测时，对某曲 面片选择凸壳或包围盒时，通常都是采用其卜邻域的顶点组，并未给出证明原因。精确 的选择方法是曲面片顶点周围的多大区域，目前没有定论。 大连理工大学硕士学位论文 ( a ) 初始控制网格( b ) 细分多次后 图11 初始和细分多次后细分曲面的相交性 f i g lii n t e r s e c t i o no f i n i t i a la n ds u b d i v i d e ds u b d i v i s i o ns u r f a c e 1 3 课题的背景和意义 曲面造型是计算机图形学和计算机辅助几何设计( c o m p u t e ra i d e dg e o m e 订i cd e s i g n ) 的一项重要内容，主要研究在计算机图象系统的环境下对曲面的表示、设计、显示和分 析。它源于飞机、船舶的外形放样工艺。经三十多年发展，现在它已经形成了以b e z i e r 和b 样条方法为代表的参数化特征设计和隐式代数曲面表示这两类方法为主体，以插值 ( i n t e r p o l a t i o n ) 、拟合( f i r i n g ) 、逼近( a p p r o x l m “o n ) 这三种手段为骨架的几何理论体系。 参数曲面表示是目前c a d c a m 系统中曲面的主要表示方法，尤其是在8 0 年代后期形 成的非均匀有理b 样条( n u r b s ) 的理论，把有理和非有理b e z i e r 及非有理b 样条曲线 曲面统一在n u r b s 标准之中，使得n u r b s 成为曲线曲面描述中的最为流行的技术。 1 9 9 1 年国际标准组织( i s o ) 颁布的工业数据交换标准s t e p ，将n u r b s 作为定义工业产 品几何形状的唯一数学描述方法。 n u r b s 尽管被国际标准化组织作为定义工业产品数据交换的s t e p 标准，在工业造型 和动面制作中得到了广泛的应用，但仍然存在着一些固有的缺陷。单一的n u r b s i 抽面与 其他参数曲面一样仅限于表示在拓扑上等价于一张纸、一张圆柱面或一张圆环面的曲 面，不能表示如人的头、手，自然花卉等复杂的任意拓扑结构的曲面。如果使用补片的 形式柬实现复杂光滑曲面的构造，则又带来t n u r b s 的修剪和拼接缝合问题。这种修剪 和拼接的计算是非常昂贵的，而且有数值误差，要在曲面的接缝处保持光滑即使是近 似的光滑也是困难的。如果模型是活动的则情况更是如此。而以网格细分( s u b d i v i s i o n ) 为特征的离散造型与传统的连续造型相比，大有后来居上的创新之势。细分造型有潜力 克服以上两个困难，它们将传统的样条补片推广为任意拓扑的结构，无须修剪和拼接， 活动模型的平滑度被自动地保证。而且，由于细分是基于递归的结构，可以非常自然的 。p c a t m u l l - c l a r k 细分曲面的实现及求交技术研究 实现分级渲染和误差范围内的逼近，特别适于多辨识分析。同时它还具有有限元分析所 要求的良好特性，适于3 d 曲面的数据重建，以及计算简单高效等优点 由于细分造型的诸多优点，在现有c a d 系统中引用细分造型的方法将能克服n u r b s 的 缺陷，在雕塑曲面等复杂形体的造型方面给用户带来非常大的方便，和n u r b s 相辅相成， 给c a d 系统带来更为强大的功能。对于c a d 系统来说，细分技术还有许多问题需要解决： 使用细分方法表示传统的曲线曲面，以及相互转换；细分曲线曲面的参数化方法、直接 计算；细分操作中的精度控制：细分曲线曲面的裁剪、求交等运算：细分表示的非连续 特征；常见造型方法的细分表示：曲线曲面的细分方法重建：细分曲线曲面的等距；自 适应细分：高精度细分曲面快速显示；细分曲线曲面的连续性分析。 在诸多细分模式中，c a t m u l l - c l a r k 细分曲面是b 样条曲面的推广，易于与n u r b s 曲面融合的特点，能更好的与数控加工相结合，最有可能应用于未来的c a d 造型系统， 本人就c a t m u l l - c l a r k 细分曲面，针对其真正应用到c a d 系统所用解决的问题之一求交 作探索性的研究，为其在未来的c a d 系统中应用奠定基础。 1 4 本文主要内容 本文共分四章，各章的主要内容如下： 第一章：绪论。对现有的曲面造型方法与细分曲面做了比较分析，总结出细分造型 方法的优点，并对细分曲面在c a d 系统中的应用作了概述。针对细分曲面应用到c a d 系 统中的问题，提出了自己的研究内容。 第二章：细分理论基础与典型曲面细分方法。介绍了与细分方法密切相关的数学基 础和一些重要概念。包括细分方法的分类，特点，收敛性和连续性，以及d o o s a b i n ， l o o p ，蝶形，k 0 b b e l t 和4 8 等细分模式，并提出了选择细分模式的原则。为后续章节 对细分方法的研究做铺垫。 第三章：对c a t m u l l - c l a r k 细分曲面进行了推导。c c 细分曲面最初是源于c h a i k i n 的细分曲线的思想，利用c h a i k i n 的细分公式与将二次b 样条曲面进行细分得到的结果 具有一致性。采用同样的方法对三次均匀b 样条曲线进行细分，并利用张量积的方式将 其推广到样条曲面，同样对曲面进行细分，得到的结果即为c a t m u l l c l a r k 细分曲面的正 则形式。 第四章：实现c a t m u l l - c l a r k 细分曲面算法。目前的边界表示方法采用翼边数据结果 和半边数据结构，针对本文的实际需要，提出一种简单的数据结构，利用c + + 、o p e n g l 编程进行了实现，并给出了实现实例。 大连理工大学硕士学位论文 第五章：针对工程实际中使用的细分曲面通常是用一定细分次数的控制网格来表示， 所以在给定精度的前提条件下，可以把对两张细分曲面的求交转化为一定细分次数上的 控制网格的求交。首先标记出初始控制网格中的相交四边形片，然后不断的通过细分算法 来缩小相交四边形片1 邻域网格带，来达到求交的精度。最后根据每个交点所在的四边 形网格片之间的拓扑关系；将它们按照一定的顺序连接起来，即可得到满足给定精度要求 的两张细分曲面之间的相交曲线。其求交步骤为：控制网格相交性检测、相交四边形网格 片的构造、精度控制、交线计算。对各步骤进行了详细分析。 c a t m u l l - c l a r k 细分曲面的实现及求交技术研究 2 细分曲面理论基础 2 1 基本概念 细分曲面是多边形网格的极限状态，在实现时也只能把它当作某一细分层次的多面 体来处理，可以说细分方法处理的就是多边形网格，因此有必要对多边形网格的有关概 念作较为形式化的处理。 2 1 1 网格相关概念 定义2 1由顶点、边和面构成的整个或部分多面体表面称为网格( m e s h ) 。如果所有网