（计算机软件与理论专业论文）三角网格面及其上曲线等距方法研究.pdf

河海大学顿士学位研究生论文摘要 摘要 等距是c a d c a m 中的一个重要操作，在数控加工、机器人技术、实体造型 等领域有广泛的应用。虽然单一曲线曲面等距技术已被广泛研究并取得了丰硕成 果，但组合曲面及其上曲线等距方法研究还不多。由于曲线曲面的离散化表示广 泛应用于许多工业领域和图形系统，本文对三角刚格丽及其上的离散曲线等距方 法进行了系统分析和研究。 三角网格面上的离散曲线圆角等距较尖角等距应用更广泛，但目前还没有理 想的圆角等距方法。本文提出一个三角网格面上离散曲线等距的新方法来实现圆 角等距。首先计算原始曲线中各线段端点的等距轨迹线，根据等距轨迹线所经过 的三角面对原始边离散，使得离散后每段线段的等距线仍在一个三角面上，实现 边的快速等距；其次用近似圆弧段连接等距形成的断裂，利用干涉连贯性和干涉 边特性在等距过程中去除局部无效环：最后，拓展了平面上单调链求交的扫描线 算法，通过对初步等距线求交去除全局无效环。 目前的三角网格面等距算法，或者采用尖角等距避免断裂和局部干涉，或者 结合3 轴数控加工特点在2 d ( 生成刀具轨迹的驱动平面) 巾去除无效区域。本文 采用顶点多向量实现等距断裂处理，且利用局部干涉区域连贯性在等距过程中去 除局部无效区域，提出一个三角网格面等距新算法。该方法的特点是有效处理顶 点和边等距实现圆角缝合断裂，并利用干涉区域连贯性提高了局部无效区域确定 效率。 本文在v i s u a lc + + 6 0 和a c i s 系统下实现了本文的三角网格面等距算法及三 角网格面上曲线等距算法，实验表明所提出算法可行有效，特别是局部无效区域 的确定是高效的。 关键词组合曲线，组合曲面，三角网格面，等距，白交 三角网格面及其上曲线等距方法研究 a b s t r a c t o f f s e ti sa ni m p o r t a n to p e r a t i o ni nc a d c a m ，a n dh a db e e nw i d e l yu s e di n v a r i o u s 印p l i c a t i o n s ，s u c ha sn u m e r i c a lc o n t r o lm a c h i n i n g ，s o l i dm o d e l i n g ，r o b o t i c se t e l o t so fe f f e c t i v eo f f s e t t i n gm e t h o d sf o rs i n g l ec u r v e s u r f a c eh a v eb e e np r o p o s e d ，b u t t h es t u d yf o rc o m p o u n dc u r v e s u r f a c eo f f s e t t i n gh a sj u s tb e g u n f o rt h et r i a n g u l a rm e s h i sw i d e l yu s e di ni n d u s t r ya n dc o m p u t e rg r a p h i c ss y s t e m s ，t h i st h e s i sf o c u s e so nt h e o f f s e tm e t h o d sf o rt r i a n g u l a rm e s h e sa n dc u r v e so nt h e m r o u n do f f s e tf o rc u r v e so nt r i a n g u l a rm e s hh a sm o r ea p p l i c a t i o n st h a ns h a r po f f s e t ， b u tt h e r ei sn oe f f e c t i v er o u n do f f s e tm e t h o dn o w t h i st h e s i sp r o p o s e san e wr o u n d o f f s e tm e t h o d f i r s t l y , c o m p u t eo f f s e t t i n gt r o c h o i d sf o ra l le n d so fo r i g i n a lc u r v e s ， d i v i d et h eo r i g i n a lc u r v e si n t om o r en e wl i n es e g m e n t sa c c o r d i n gt ot h eo f f s e t t i n g t r o c h o i d ss ot h a te v e r yo f f s e t t i n gc u r v ef o rn e wl i n es e g m e n t si si nat r i a n g u l a rf a c e ； t h e n ，c o n n e c tt h eg a p sg e n e r a t e dd u r i n go f f s e t t i n gu s i n ga p p r o x i m a t ea r cs e g m e n t s ， d e l e t el o c a li n v a l i dl o o p su t i l i z i n gi n t e r f e r e n c ec o n t i n u i t y ；f i n a l l y , e x t e n dt h es w e e p l i n em e t h o do fp o l y g o n a lc h a i n si n t e r s e c t i o n ，d e l e t eg l o b a li n v a l i dl o o p sb yf i n d i n g g l o b a li n t e r s e c t i o n s t h ep r e s e n to f f s e tm e t h o d sf o rt r i a n g u l a rm e s he i t h e ru s es h a r po f f s e tt oa v o i d g a p sa n dl o c a li n t e r f e r e n c e so rm a k eu s eo ff e a t h e r so f3 - a x i sm a c h i n i n gt od e l e t e i n t e r f e r e n c ei n2 dc l s u r f a c e an e wo f f s e tm e t h o df o rt r i a n g u l a rm e s hi sp r e s e n ti n t h i st h e s i s u s i n gm u l t i p l en o r m a lv e c t o r so fav e r t e xt od e a l 谢t 1 1g a p sa n dc o n t i n u i t yt o d e l e t el o c a li n v a l i da r e a s t h ec h a r a c t e r i s t i co ft h i sm e t h o da r eu s i n gp r o p e r t i e so f v e r t e x e sa n de d g e st oc o n n e c tg a p sr o u n d l ya n du t i l i z i n gi n t e r f e r e n c ec o n t i n u i t yt o i m p r o v et h ee f f i c i e n c yo fd e l e t i n gl o c a li n v a l i da r e a s t h i st h e s i sr e a l i z e dt h en e wm e t h o d si nt h ee n v i r o n m e n to fv c + + 6 0a n da c i s e x p e r i m e n t ss h o wt h a tt h ep r o p o s e dm e t h o d sa r ee f f e c t i v e ；e s p e c i a l l yt h a td e l e t i n gf o r l o c a li n v a l i da r e a si se f f i c i e n t l y k e y w o r d s ：c o m p o u n dc u r v e s u r f a c e ，t r i a n g u l a rm e s h ，o f f s e t t i n g ，s e l f - i n t e r s e c t i o n i i 学位论文独创性声明： 本人所呈交的学位论文是我个人在导师指导下进行的研究工作 及取得的研究成果。尽我所知，除了文中特别加以标注和致谢的地方 外，论文中不包含其他人已经发表或撰写过的研究成果。与我一同工 作的同事对本研究所做的任何贡献均已在论文中作了明确的说明并 表示了谢意。如不实，本人负全部责任。 论文作者( 签名) ：鎏! 盈弱”眸，3 b 印日 学位论文使用授权说明： 河海大学、中国科学技术信息研究所( 含万方数据库) 、国家图 书馆、中国学术期刊( 光盘版) 电子杂志社有权保留本人所送交学位 论文的复印件或电子文档，可以采用影印、缩印或其他复制手段保存 论文。本人电子文档的内容和纸质论文的内容相一致。除在保密期内 的保密论文外，允许论文被查阅和借阅。论文全部或部分内容的公布 ( 包括刊登) 授权河海大学研究生院办理。 论文作者( 签名) ：鎏迅益芦1 年哆月刁日 河海大学硕士研究生论文第一章绪论 第一章绪论 等距主要是对线面实现平移操作，等距曲线曲面也称为平行曲线曲面，定 义为沿原始曲线，曲面的法向与原始曲线曲面距离一定的点的集合【1 1 等距技术 在数控加工中的刀具轨迹生成，带厚度薄片实体的计算机辅助设计，机器人的路 径规划，实体造型中的混合操作等众多领域有着广泛的应用。 目前已有的成果主要集中在单一曲线曲面等距研究上，对组合曲线曲面等 距研究尚很初步。这里的单一曲线曲面指c 1 ( 一阶参数) 连续的曲线曲面，组 合曲线曲面为c o 连续的曲线曲面。但随着应用领域需求( 如数控加工中大多数 产品的外形是组合曲面) 范围的扩大，组合曲线曲面等距逐渐成为了研究热点 1 1 等距的分类 根据等距对象的不同，等距可分为点等距、线等距、面等距、体等距其中 线包括单一曲线与组合曲线，面包括单一曲面和组合曲面。根据等距的不同实现 方法，等距可分为几何等距法和拓扑等距法两大类【2 】。几何等距法研究的是等距 曲线曲面的精确和逼近生成方法，它针对单一曲线曲面；拓扑等距法是在几何 造型系统中生成等距实体的拓扑操作方法，它以等距曲线曲面技术为基础，研 究组合曲线曲面的等距方法。本节针对等距对象分类阐述，等距方法的进展下 一节介绍。 1 , 1 1 点等距 点等距是把点沿其法向等距一定的距离。仅就一个点而言其法向可以是任意 方向，因此，在平面上一个点的等距结果是一个以原始点为圆心，以等距值为半 径的圆，在3 d 中则是以原始点为圆心的球面。一般来说点总是依附在线或面上， 其等距法向由线或面在该点处的法向确定，这时的线上点或面上点根据当前的线 等距或面等距给出相应的等距操作。 1 1 2 线等距 在等距操作中，线一般指平面曲线和曲面曲线，这些曲线又可以分为单一曲 线和组合曲线。 1 单一平面曲线 平面曲线上的点的等距方向，一种是线在该点处的法线方向；另一种是线所 在平面在该点处的法向。平面曲线上所有点的等距点集合即是平面曲线的等距曲 线。如图1 1 ( a ) 所示，细虚线是原始曲线沿线法向的等距线，租虚线是沿平面法 向的等距线，虚箭头表示线的法向，实箭头表示平面法向 三角网格面及其上曲线等距方法研究 2 单一曲面曲线 曲面曲线上点的等距方向，一种是在该点处测地方向，也即是曲面上正交于 曲线的方向；另一种是曲线所在曲面在该点处的法向方向。曲面曲线的等距曲线 是曲线上所有点的等距点的集合。如图1 1 ( b ) 所示，粗曲线是沿测地方向的等距 线，细虚线是沿曲面法向的等距线，虚箭头表示测地方向，实箭头表示曲面法向 一 ( a ) 平面曲线 图1 1 单一曲线等距 ( ”曲面曲线 3 组合曲线 组合曲线( 包括组合平面曲线与组合曲面曲线) 等距是多条单一曲线等距的 组合，但是，一般情况下组合曲线的曲线段元素等距并不能直接生成组合等距曲 线，这是因为曲线段元素等距会产生断裂和自交。断裂发生在曲线不光滑的凸向 连接处。自交有2 种形式：一种是对应于原始组合曲线上一条连续曲线的自交， 称为局部自交，发生在不光滑的凹向连接处；另一种是对应于原始组合曲线上一 对连续曲线的自交，称为全局自交，发生在不相邻且过于相近的曲线段元素之间。 如图1 2 所示，( a ) 是组合曲线产生的断裂，虚线部分是断裂的不同处理方法( 延 长线求交、弧连接、直线段连接) ；( b ) 是组合曲线等距产生的局部自交，( c ) 是 组合曲线等距产生的全局自交。 ( a ) 等距断裂( b ) 局部自交( c ) 全局自交 图1 2 组合曲线等距 1 1 3 面等距 与线一样，在等距操作中面可以分为平面和曲面，此面可以是单一面，也可 以是组合面。在三维图形的真实感显示中往往很多曲面会用组合三角面来逼近显 2 ， 人 解 ，灸 河海大学硕士研究生论文第一章绪论 示，即所谓的三角网格面，利用三角面来逼近图形显示效率高且处理简单。 1 单一面 无论是单一平面还是单一曲面，其上一点的等距方向是面在该点处的法向， 其等距面是原始面上所有点的等距点的集合。如图1 3 所示，( a ) 是仅含凸点的曲 面等距，( b ) 是含有凸点和凹点的曲面等距。 图1 3 单一曲面等距 2 组合面 组合面等距是其组成面片元素的等距面的组合，与组合曲线一样，组合曲面 等距也会产生断裂和自交。如图1 4 所示，( a ) 是组合曲面等距产生的断裂，粗虚 线是面片元素等距后的面，细虚线表示断裂的不同连接( 平面直接连接、柱面连 接、延长等距面片元素求交) ；f b ) 是等距产生的局部自交，细虚线为交线。 本文根据断裂处理方式把组合监线曲面等距分为尖角等距和圆角等距，尖 角等距通过延长等距线等距面求交缝合断裂，圆角等距则用圆弧柱面、球面或 近似球面连接断裂。 c a ) 图1 4 组合曲面等距 1 1 4 体等距 等距体是对一个实体的等距离扩展或缩小，对实体等距扩展一定距离以后， 其扩展部分中的点到原始等距体边界的距离小于等于等距值；反之，对实体等距 缩小一定距离后，原始等距体中到其边界的距离小于等于等距值的部分被减去 3 三角网格面及其上曲线等距方法研究 等距体可以通过等距原实体的表面( 封闭的组合曲面) 来实现。由于组合曲面等 距会产生断裂和自交，则体用组合曲面实现等距也会碰到这两个问题。 如图1 5 所示，图中虚线表示原始长方体的线框，实线表示等距体的线框， 图( a ) 中的长方体通过等距其六个面，然后延伸等距面求交而得；目f l o ) v e 的等距 体表面由长方体的六个等距面和连接断裂的柱面和球面组成( 图中仅画出了部分 面) 圆画 图1 5 体的等距 1 2 等距的方法 有关等距方法的研究已有3 0 0 多年的历史，学者们提出了大量的方法，这些 方法归纳起来大致分为两类：几何等距法和拓扑等距法。已有的研究成果主要集 中在几何等距研究上，对拓扑等距研究尚很初步。 1 2 1 几何等距法 几何等距法主要研究单一曲线曲面的等距曲线曲面的精确和逼近生成方 法，传统的等距研究主要集中在这方面。 f a r o u k i 和s a k k a l i s t m 提出了一类特殊的曲线称为p h 曲线，这类等距曲线可 以精确表示；p o t t m a n n 4 1 根据同样的原则提出了p h 曲面( 具有有理等距曲面的 一类有理曲面) 的概念。m a r t i n 5 】证明了d u p i n 曲面( 曲率线为圆弧的曲面) 的 等距曲面也是d u p i n 曲面。吕伟 6 q 正n 了抛物面、椭球面和双曲面的等距魄面是 有理的。p o t t m a n n l t ) j 正明了不可展有理直纹面的等距曲面在整个空间是可有理化 的。f a r o u k i 8 】给出了三类简单实体( 凸多面体、旋转体和拉伸体) 表面的等距曲 面的精确计算。 但是精确表示方法只适用于特殊的曲线曲面，对于更为复杂的曲线曲面生 成其等距曲线等距曲面颇为困难，所以大多采用逼近算法，包括( 1 ) 移动控制 顶点或控制多边形的方法f 9 】；( 2 ) 基于插值或拟合的方法，用3 次h e r m i t e 曲线、 最b - 乘逼近、3 次b 样条插值等逼近等距曲线曲面【i o 】；( 3 ) 基于逼近基圆算 法【i l 】。 4 河海大学硕士研究生论文第一章绪论 l e e h i 提出先用二次b 6 z i e r 曲线段逼近基圆，再与基曲线卷积产生逼近等距 线的方法，该方法很有特色地解决了整体误差问题，然而等距逼近曲线有大量的 控制顶点，并且等距逼近曲线的次数很高。寿华好等【1 2 1 给出了一种基于刘徽割圆 术的平面n u r b s 等距线逼近算法，用正多边形来逼近等距圆，将正多边形沿着 基曲线的扫掠区域边界作为等距曲线的逼近曲线，该算法降低了逼近等距曲线的 次数，但是当精度要求较高时数据量较大，并且在计算凹向等距线时需要求交运 算f a r o u l d ”】利用双三次h e r m i t e 多项式曲面来插值逼近等距曲面。1 9 9 9 年， p i e g l 和y i u e r 1 4 l 提出了一种新的基于插值n u r b s 等距曲线曲面逼近方法，他们 首先判断曲面上包含平面片或旋转面片( 球面、环面、锥面和柱面等的部分) ，然 后根据曲率大小对其它曲面片部分的等距面片进行采样，利用n u r b s 曲面进 行插值，最后在允许误差范围内去除不需要的控制节点。该算法比以前算法减少 了控制项点数( 这是衡量等距曲线曲面算法质量的一个重要指标) ，并且误差控 制有严格的理论基础( f i l i p 提出的利用二阶导矢在允许误差范围内逼近曲线曲 面的定理) ，但是没考虑自交问题。r a v i 等【1 5 】基于p i e m 和t i l l e r 的算法【1 4 l 提出了 一般n i 爪b s 曲面的避免自交的等距算法。该算法只适用于单个g 1 连续曲面， r a v i 等【1 6 】把该算法扩展到了裁剪曲面的等距中。s u n 、n e e 和l c e f l 刀提出在等距 之前修改在等距曲线曲面自交点处对应的原始曲线曲面嗌率来实现局部自交的 删除。 曲面上的曲线等距不同于平面上的曲线等距，曲面上曲线等距操作的距离是 基于测地方向计算的，一个有效的方法是先计算曲线上采样点的等距点，再对这 些采样等距点进行插值求得逼近等距线。p a t r i k a l a k i s 和b a r d i s l l 8 1 首次给出了 n u r b s 曲面曲线上的测地等距方法，测地方程由四个一阶非线性微分方程组成， 选取原始曲面曲线上的点沿测地方向( 和原始曲面曲线正交曲面曲线) 等距，等 距曲线由b 样条曲线在参数空间插值等距点完成。t a m 等【1 9 1 提出一个基于采样插 值的曲面曲线等距方法，沿法平面( 与切线垂直的平面) 与曲面求交获得等距曲 线，自交检查和删除是利用干涉边的连贯性。h a t n a 等【2 0 】提出一个在参数空间利 用环的方向性删除无效环的等距方法，此方法需要大量迭代和自交计算，并且不 能处理开曲线。 1 2 2 拓扑等距法 拓扑等距法是在几何造型系统中生成等距实体的拓扑操作方法，它以等距曲 线曲面技术为基础，研究组合曲线曲面的等距。单一曲线曲面或组合曲线曲面 都可以由一系列直线段，平面面片( 多边形) 来逼近，即离散的曲线曲面。由于 离散表示能达到很高的精度，且直线段或平面面片的等距实现比较简单，所以组 合曲线曲面等距方法一般是针对离散曲线曲面的。 三角网格面及其上曲线等距方法研究 平面上组合曲线的等距操作是人们早就关注的问题，平面组合曲线的离散形 式也可以看成是近似多边形。现有多边形等距方法可以分为三类：边等距法 ( p a i r - w i s eo f f s e t ) 、v o r o n o i 图法【2 1 】和基于像素法( p i x e l - b a s e d ) 圈。其中v o r o n o i 图法效率较高，但算法不稳定；基于像素法可以避免自交，且可以应用于2 d 和 3 d ，但是为达到一定精度，需巨额计算。由于各自的缺陷，后两类方法较少为 人们所关注。 边等距法的一般过程分成如下三步：首先对多边形的每条边沿等距方向作等 距，然后用圆弧段连接断开的等距边生成初步等距线；其次检查初步等距线的自 交点；最后删除无效环。此种方法简单、直观，其问题关键在于如何确定各等距 段中的非干涉部分，许多学者提出了一些有效的算法，如s u h 等i 矧根据等距环 的走向来判定各环是否存在干涉；h a n s e n 和a r b a b 2 4 提出了干涉标志量来简化 等距线中干涉段的判断；方向【2 5 l 改进了h a n s e n 方法；k a l m a n o v i c h 和n i m e v i c h 刚 提出了可以处理多边形和开环的等距方法，然而这些方法仍然存在着求交量大和 不稳定的问题。c h o i 和p a r k 2 7 】提出了一个新的边等距法，从多边形顶点出发在 初步等距线构造以前就把所有局部无效环删除掉；再用一个扩展的扫描线算法确 定是否存在全局无效环。该方法的特点是避免了多边形中局部干涉部分的等距操 作，从而减少了计算量，但对全局干涉部分仍需通过等距操作后再剔除。通过分 析全局无效环存在的几何特性，陈正鸣【2 3 】瞄】提出了一个基于网格技术的多边形 等距方法，它避免了多边形中所有干涉区域的等距操作，大大提高了效率。 h o l l a 等例提出了基于网格面的组合曲面曲线等距方法。曲线表示为网格上 的离散线段，采用增量方法来避免局部自交；而全局自交则通过求交检测来删除。 该方法可以消除局部自交，但要在等距后通过求交来确定全局无效环；该方法效 率较高，但是由于点的等距方向是角平分线方向，所以该方法是尖角等距方法， 只能应用于少数等距应用领域。 组合曲面等距算法目前比较少，主要是多面体等距算法【3 1 】和三角网格面等距 算法f 3 2 - 3 4 。多面体等距算法直接用柱面和球面缝合断裂。三角网格面等距方法分 为单向量等距算法和多向量等距方法，在单向量等距方法中每个顶点沿一个方向 等距，处理简单，但是不精确的致命缺陷使得其应用范围非常小；多向量等距法 对断裂处理精确，并且直接处理为三角网格面，形式统一，但是没有给出无效区 域的消除方法。 体等距方法主要有包络面法、基于点等距法和基于线等距法。包络面法即是 通过等距体的表面( 封闭组合曲面) 实现体的等距。基于点的方法【3 5 】【3 6 1 通常利 用z - m a p 方法生成离散点获取体的等距表面，要想达到一定的精度，耗费的空间 非常大；i n u i 3 6 1 利用3 d 绘制硬件中多面体隐藏面消除算法快速生成实体等距表 面，但其精度取决于硬件网格分辨率，不能按需要控制。基于线的方法【3 l 】是结合 3 轴数控加工刀具轨迹生成方法，把各个等距面的求交问题转化为驱动平面上的 6 河海大学硕士研究生论文第一章绪论 交线间的求交。 1 3 等距技术应用背景 等距技术广泛应用于型腔加1 1 3 叼【3 卿和数控加工中的刀具轨迹生成 3 9 4 3 、带 厚度薄片实体( 如汽车车身、箱包等) 的计算机辅助设计、机器人技术中机械手 可及范围的表示、快速成型、实体造型等领域【槔垌。 数控加工中刀具轨迹生成是等距技术的最重要的应用之一。在复杂衄面数控 加工中，如何确定各类刀具( 球头刀、平底刀、环形刀等) 的无干涉刀具轨迹，至 今仍是一个十分棘手的难题【4 3 】。近年来，在汽车、造船、飞机、特平机械等工业 领域，自由曲面得到了广泛应用。随着用户对产品要求的不断提高，这些益面越 来越复杂，使得其加工变得更加困难和费时，寻求高效和精确的刀具加工路径产 生方法自然成为当前的研究焦点之一，对零件表面等距是研究的方法之一。 平面组合曲线等距可以解决型腔加工中刀具加工路径干涉问题，生成二维轮 廓加工的无干涉刀具轨迹，如图1 6 所示，p a r k 【4 刀用c h o i 和p a r k 的边等距法鲫 生成了型腔的无欠切刀具轨迹。 ( a ) 轿车车门模型( b ) 型腔加工刀具轨迹 图i 6 组合曲线等距应用 3 d 数控加工中，在刀具轨迹生成之前计算c l s u r f a c e ( 刀位数据面) 可以 有效的避免干涉【3 5 1 。c l s u r f a c e 虽然可以通过倒置刀具扫掠体【3 5 】或z - m a p 方法获 得，但是倒置刀具扫掠体计算太复杂，z - m a p 方法要达到一定的精度耗费空间非 常大；现在一般用等距曲面或三角网格面求取c l $ u l - f a c e j u n 3 1 j 和p a f k 【4 s 1 分别 利用c l - s u r f a c e 得到了多面体和雕塑曲面的无干涉刀具轨迹。k i m 等 4 9 】基于顶 点多向量等距法刚提出了针对一般刀具( 包括a p t 中定义的球头刀、圆角刀、 平底刀和由曲线定义的刀具) 的一般等距算法( 等距方向不一定是法向的等距) 。 进一步拓展了三角网格面等距在数控加工中的应用。如图1 7 所示，( a ) 是s t l ( s t e r o l i t h o g r a p h y 文件) 形式的零件；( b ) 是用球头刀加工该零件时的c l - s u r f a c e ， ( c ) 是用平底刀加工该零件时的c l - s u f f a c e ；( d ) 是环形刀加工该零件的轨迹 目前平面组合曲线等距方法相对已经成熟，但是曲面组合曲线、组合曲面等 7 三角网格面及其上曲线等距方法研究 距研究还在初步阶段。曲面组合曲线只有尖角等距方法，应用更多的圆角等距还 没有比较好的算法；组合曲面圆角等距，还没有在3 d 中直接消除干涉的方法； 这也限制了曲线曲面等距的应用，所以研究组合曲线曲面在3 d 中快速去除无 效区域的方法还是有意义的。 ( a ) s t l 零件模型 ( c ) 平底刀c l - s u r f a c e 图1 7 组合曲面等距应用 ( b ) 球头刀c l - s u r f a c e ( d ) 环形刀加工轨迹 1 4 本文的主要工作 目前还没有理想的曲面组合曲线圆角等距方法，尖角等距虽然可以避免等距 断裂和自交，但应用范围有限；在现有的组合曲面等距算法中，每一种算法都是 处理了等距中的部分问题，且针对不同的应用需求，各种组合曲面等距算法也都 存在着这样或那样的缺陷。因此，研究提出更好的新的曲面组合曲线、组合曲面 等距算法，或对现有的算法进行改进，以拓展曲面组合曲线、组合曲面等距应用 范围，提高算法的效率和易用性，具有非常重要的意义。 鉴于离散表示曲线曲面的优点，本文提出的等距算法建立在离散曲面组合 曲线、组合曲面之上，即是实现三角网格面上的组合空间折线、三角网格面的圆 角等距。本文主要工作如下： 1 对几种典型的组合曲线曲面等距算法进行了研究、介绍及对比。 2 提出了一个新的曲面组合曲线的圆角等距算法。 3 完善了基于顶点多向量的三角网格面等距算法，可以精确处理断裂，适 应所有类型的顶点，且简化了尖边处理复杂度 4 给出了一种在三角网格面等距过程中利用干涉区域连贯性消除局部无效 8 河海大学硕士研究生论文第一章绪论 区域的方法。 5 在v c + + 6 0 1 5 0 5 1 1 和a c i s 环境睁2 】【5 3 1 实现了所提出的算法，进行了测试与 评估。 1 5 章节安排 本文的章节安排如下： 第一章：概述等距的研究内容、研究方法和应用背景。 第二章：介绍几个典型的组合曲线曲面等距算法。 第三章：提出了一种新的三角网格面上组合曲线的等距方法。 第四章：提出了一个在3 d 空间消除干涉的三角网格面圆角等距算法。 第五章：阐述算法实现模块、数据结构，给出算法测试与评估结果。 第六章：对全文工作进行了总结，并对进一步需要研究的工作作展望。 9 三角网格面及其上曲线等距方法研究 第二章组合曲线，曲面的典型等距算法 单一曲线曲面等距算法从最初的针对特殊曲线曲面的有理等距【3 ，到针对 一般自由曲线曲面的等距的逼近 9 - 1 6 l ，在等距过程中消除干涉区域，最后，到在 等距前修改曲线曲面的曲率避免等距中出现的问题【l ”，相对已经比较成熟。组 合曲线曲面等距应用广泛，但研究尚很初步，本章主要介绍几个典型的组合曲 线曲面等距算法：c h o i 的多边形等距算法【2 7 】，h o l l a 的离散网格面上组合曲线等 距算法【3 0 】，j u n 的多面体模型等距算法口”，0 u 的顶点单向量等距算法【3 3 】和k i m 等 的顶点多向量等距算法刚。本文的研究正是基于这些算法的，因此对这些算法进 行了深入的分析。 2 1 组合曲线等距 平面组合曲线等距研究主要集中于多边形等距上，算法分为三类：边等距法、 v o r o n o i 图法和基于像素法。v o r o n o i 图法计算不稳定，基于像素法要达到一定精 度需要巨额计算，所以一般常用的是边等距法，而其中比较典型的算法是c h o i 和p a r k 的多边形等距算法【明。典型的曲面组合曲线等距算法是h o l l a 的离散网 格面上组合曲线等距算法【3 0 1 。 2 1 1c h o i 多边形等距算法 c h o i 的算法是一个新的边等距算法，该方法将无效环分为局部无效环( 对 应于原始组合曲线上一条连续线段的无效环) 和全局无效环( 对应于原始组合曲 线上一对连续线段的无效环) ，利用干涉边的连贯性消除无效环，从而避免了以 往的边等距算法所需的大量的不必要求交计算。 2 1 1 1 算法步骤 所有局部无效环都对应一个凹点，且干涉边具有连贯性，本算法利用此性质 在等距前消除所有的局部干涉区域，然后实现初步等距，求出初步等距线的自交 点，再利用干涉连贯性确定出所有的全局干涉区域算法具体步骤如下： 1 删除组合曲线中所有会引起局部干涉的部分。 2 对处理后的组合曲线等距，得到初步等距线。 3 求出初步等距线的自交点 4 应用干涉连贯性和所求的自交点删除所有全局干涉环。 5 等距线剩余部分即为有效等距线。 其中第一步与第四步是算法的核心部分，第一步具体实现是：从一个凹点关 联的两线段反向逐个检测，直到出现非干涉区域，即确定出非干涉区域的边界， 对所有凹点执行同样的操作，就可以确定出所有引起局部干涉的部分。第五步实 1 0 河海大学硕士研究生论文 第二章组合曲纷曲面的典型等距算法 现与第一步类似，只是选择自交点所在的两个线段反向逐个检测，确定无效区域。 如图2 1 所示，( a ) 是原始组合曲线； 是确定出局部干涉部分后的组合曲线；( c ) 是初步等距线与全局自交点；( d ) 是确定出全局干涉环后的组合曲线。 ( a ) 原始组合曲线 - ( b ) 局部干涉确定 公- ，- 岔岔 ( c ) 全局自交点( d ) 全局干涉确定 图2 1 多面体等距生成刀具轨迹过程 2 1 1 2 存在问题 该算法稳定性好，效率也较以前的边等距算法有很大提高，但仍存在下面的 问题： 1 全局干涉部分在形成初步等距线时仍需等距，增加了计算量。 2 删除全局无效环需要求取初步等距线的自交点，这需要大量的求交计算。 3 不能处理带有孤岛的( 内环) 的封闭组合曲线。 2 1 2h o l l a 网格面上组合曲线等距算法 不同于传统曲面曲线等距算法( 参数形式的自由曲线等距算法) ，该算法【3 0 l 实现离散网格面上的离散组合曲线等距，且属于尖角等距。 2 1 2 1 算法步骤 组合曲线是c o 连续的，不光滑连接点在两个关联的线段上的法向不同，因 此等距产生断裂和局部自交( 断裂发生在尖凸连接处，局部自交发生在尖凹连接 处) 。该算法选取不光滑连接点的两个等距方向的角平分线作为该点的等距方向， 且分层次等距，从而实现避免局部自交和断裂的曲面组合曲线测地等距图2 2 是该算法的一个图示，其中包括原始曲线、各层等距线以及端点的等距方向。假 设等距值为d ，算法具体步骤如下： 1 计算离散组合曲线所有端点的等距方向 2 分层实现等距。 2 1 计算组合曲线可以等距的距离。 2 2 根据等距距离计算出中间等距点。 三角网格面及其上曲线等距方法研究 2 _ 3 若总等距值( 每层实现的等距值之和) 小于d ，则更新所有端点的 等距方向，转到2 1 继续分层等距；否则到3 。 3 检测并消除全局无效环。 在2 1 中组合曲线可以等距的距离，是指可以避免局部自交和在离散网格面 上等距且不大于d 的最大可以等距的距离( 也是所有端点中可以等距距离的最 小值) 。要避免局部自交和在网格面上等距，每个端点的等距方向要与其穿过的 边( 网格面中三角形的边) 和相邻端点上的等距方向求交。根据交点和等距因子 ( 等距曲线和原始曲线沿等距方向的距离和沿垂直方向的距离之比) ，计算出端 点的可以等距的距离。s t e p 3 的全部无效环消除需要显式的求交确定，通过每段 线段的等距线和其它所有线段的等距线求交实现判断。 合并点 等距方向 图2 2 组合曲线等距图例 2 1 2 2 存在问题 该算法给出了离散网格面上点的测地等距方法，可以在等距过程中消除局部 无效环，且和离散网格面的质量无关，但是该算法还存在如下一些问题： 1 全局无效环的删除需要大量的求交计算，降低了算法的效率。 2 尖角等距算法应用范围有限。 3 对尖端点处理不精确，尖端点处的等距距离与线段上的其它点的等距距 离不相等。 2 2 组合曲面等距 组合曲面等距算法主要有基于多面体模型的等距算法和基于三角网格面的 等距算法多面体模型等距是针对体的表面( 封闭组合曲面) 等距；三角网格面 是一种特殊的组合曲面，其所有的曲面组成元素均是三角面。一般用三角网格面 来逼近原始曲面相对于其它多边形逼近来说有精度高、处理简单的特性，在业界 受到广泛关注，特别是图形的真实感显示上应用极其广泛。 多面体模型等距主要有基于点的等距 3 5 3 6 1 和基于线的等距。基于点的等距 通常利用z - m a p 方法生成离散点集合，获取等距表面，该方法较耗费时间和空 河海大学硕士研究生论文 第二章组合曲线曲面的典型等距算法 间，现在一般不使用；基于线的等距方法是结合3 轴n c 具体应用和其特点提出 的方法，典型的算法是j u n 的多面体模型等距算法【3 1 1 三角网格面等距算法主要 是顶点单向量等距法和顶点多向量等距法，其中比较典型的算法是q u 的顶点单 向量等距算法【3 3 】和k i m 的顶点多向量等距算法 3 4 1 。 2 2 ij u n 的多面体模型等距算法 基于线的多面体模型等距算法【3 1 l 是根据等距定义等距的最基本的方法，比较 直观。基本思想是先等距多面体模型中每个面，再用柱面和球面缝合凸连接处的 等距断裂，最后再结合3 轴数控加工特点，把各个等距面间的求交问题转化为驱 动平面上交线间的求交，从而在2 d 中消除干涉，生成无干涉的刀具轨迹线。 2 2 i i 算法步骤 ( a ) 原始模型( b ) 等距模型 ( c ) 含有干涉的c i , - c u r v ( d ) 刀具轨迹 图2 3 多面体等距生成刀具轨迹过程 算法思想比较简单，图2 3 描述的是该算法步骤中的几个结果图。算法具体 步骤如下： 1 建立s t l 形式( 模型表面为三角网格面形式) 多面体模型的拓扑结构。 2 确定原始模型中的边、顶点的凹凸性( 定义见第三章) 。 3 等距多面体中的每一个面、凸边、凸点。 4 定义生成刀具轨迹的驱动平面，并且切割等距面，形成一系列的刀位曲 线( e l - c u r v e s ) 。 5 分类、裁剪刀位曲线( 即消除干涉部分) ，连接裁剪后的刀位曲线段形成刀 具轨迹。 三角网格面及其上曲线等距方法研究 其中第三步，是完成面片元素的等距并缝合断裂。如图2 4 所示，( a ) 凸边等 距形成柱面( 柱面边界圆弧用二次b e z i e r 曲线表示) ，缝合了凸边两关联三角面 等距形成的断裂；( b ) 凸点等距形成球面( 边界是其所关联的凸边等距形成的柱 面边界圆弧) ，缝合了凸点关联面、边等距形成的断裂。第四步和第五步是在结 合数控加工特性在2 d 中消除c l 曲线之间的干涉，p a r k l 4 8 1 提出了更快速的在2 d 中消除c l 曲线干涉的方法。由于本文是在3 d 中消除无效区域，在此不再阐述 第四、第五步 凼沙眵 ( a ) 凸边等距 图2 4 凸边、凸点等距 ( b ) 凸点等距 图2 5 顶点重构步骤 该算法中的凸点不只是原始模型中的凸点，还包括经过处理后是凸点的顶点 表2 1 给出了顶点类型的判断依据。由于凸点等距形成的球面边界仅由与之关联 的凸边等距有关，所以对于关联边数目多于4 的顶点的重构，就是逐步去除关联 边中的平边和凹边，具体构步骤如图2 5 所示从图中可以看出e 1 在原图( a ) 中 是凸边，在去除相邻的凹边后，其凹凸性改变( ”，再次去除凹边后剩余边均为 凸边( c ) 。可以在( d ) 中看出e 1 等距结果柱面c 1 是被干涉的，即e l 对形成球面边 界是无效的。 2 2 1 2 存在问题 该算法非常直观，并且能精确处理等距产生的断裂，输入模型采用的是一般 的c a d 软件都支持的s t l 格式但是仍存在一些不足： 1 在处理断裂的过程中，引入的柱面和球面边界是用二次b e z i e r 曲线表示 的，而直接等距的面仍是三角网格形式，这就引起了等距后模型表示法的不统一 2 没有给出有效的在3 d 中消除干涉的方法，而只能结合特殊应用采取特殊 方法处理。 3 等距的干涉是结合3 轴数控加工特点在2 d 中消除的，这也限制了该算法 1 4 河海大学硕士研究生论文 第二章组合曲线，曲面的典型等距算法 只能用于截平面法生成刀具轨迹。 4 在2 d 中去除干涉是通过曲线求交完成的，效率较低。 表2 1 顶点性质的判定 边数目边性质点性质 产生球面 3均为凸边 均为凹边 均为平边 4 多于3 个凸边 否则 多于4重构直到只剩下凸边，边数目大于3 否则 凸 凹 凸 马鞍点、凹或平 凸 马鞍点、凹或平 是 否 否 是 否 是 否 2 2 2q u 顶点单向量等距法 基于顶点的单向量等距法，用顶点的等距代替面的等距避免三角网格面等距 断裂和自交。q u 的算法嗍是对k o c 的算法圈的改进，虽然同样基于顶点的等距， 但顶点上的等距向量取值更精确。k o c 算法中顶点的等距向量是顶点所有关联面 法向的平均值，q u 的算法中顶点的等距向量是顶点关联面法向加权计算所得值 图2 6 顶点单向量等距图2 7 顶点多向量等距 1 算法思想 首先按给定的权值计算三角网格面中所有顶点的加权向量，然后每个顶点沿 加权向量等距一定距离，再将所有等距点按原始点的拓扑结构形成三角网格面。 由于等距前后顶点数不变，且拓扑结构一样，所以等距不会产生断裂和局部自交。 如图2 6 是六棱锥的等距结果图，阴影图是原始实体，线框图表示等距实体。 2 存在问题 该算法的特点是等距效率较高，实现简单，而且能避免等距断裂和局部自交。 但是也存在一些问题： ( 1 ) 顶点处等距距离和面的等距距离不一致，在快速成型中造成壳的厚度不 一致，如图2 6 所示 1 5 三角网格面及其上曲线等距方法研究 ( 2 ) 该算法不适合等距距离较大的情况，此时有些三角面全无效，而该算法 等距前后顶点数不变，所以会有干涉。 ( 3 ) 该算法不能避免全局干涉。 ( 4 ) 尖角等距适用范围有限。 2 2 3k i m 顶点多向量等距法 仅直接等距三角网格面的面片元素，非光滑连接处会产生断裂和自交；基于 顶点的单向量等距法虽然可以避免一些问题，但是对尖边、尖顶点等距不精确； 于是k i m 提出了顶点多向量等距法【州。 2 2 3 1 算法步骤 该算法将点、边、面等距结合，来解决顶点单向量等距不精确问题。由于断 裂是由非光滑连接处等距产生的，对尖边、尖点多向量等距可以缝合断裂，且是 精确等距。如图2 7 所示，阴影图是原始实体，线框表示的是等距实体。具体步 骤如下： 1 等距三角网格面中的每个三角面片元素，可以通过等距其三个顶点实现。 2 等距三角网格面中的所有边，凸边等距为柱面。 3 等距三角网格面中的所有顶点，凸点等距为球面。 4 用一系列平面切割等距后的面片( 包括三角面、柱面、球面) ，消除切割 面与等距面交线中的干涉。 其中第二步和第三步等距边和顶点都要用到顶点上的向量，确定方法如图 2 8 所示，( a ) 图中顶点v 的三个关联面法向分别是n f l 、n f 2 、n f 3 且相互之间 的叉乘小于指定值，则v 是平滑点，只有一个向量n i ，该向量取n f l 、n f 2 、 n f 3 的平均值；( b ) 图中顶点v 关联面为5 个，顶点向量n 1 设置为其中