（计算机应用技术专业论文）面向局部修改的多边形中轴高效生成方法研究.pdf

摘要 中轴( m a ) 和申轴交换( m a t ) 蹩物体的一种表示方法，它在外形分析、 极器入路径规划、耀像分辑、鸯限元分辑等方嚣有篱重要的应用馀篡。 传统的中轴算法众多，但是它们存在着一个不足，就怒不支持局部避改。就 是当对物体矫形送行局部更改的时候，需要爨新计箨整个物体静中辘，这样就大 大浪费了物体原毒中辘孛的一数寄曩镶息。 本文利用中轴的半连续性和区域可分性，提出了一种熬于布尔并差操作的平 面多边形支持局部修改的中轴象成方法。并程a c i s 系统主实现了该方法。 该箕法其蠢如f 特点： ( 1 ) 支持局部修改。很好地利用了原有物体的中轴信息，大大减少了重复 计算。 ( 2 ) 续会a c i s 毒尔并差操终，髅随遗墼过稷中豹京尔操终一步步地生 成中轴。 本文的章节是这么组织的： 第一章麓述了中辘豹定义与孛轴算法背景，并按照孛霉囊生成髯法的特点遴葶亍 了简单的分类介绍。 第二章讲述了本文方法的理论基确，并诫明了本文算法的正确性。 第三章游述7 簿法豹其馁步骤，对一些特殊壤熬进孬了进一步豹分辑。 笫四章结合a c i s 系统，讨论了本文方法的实现。 第五章给出了些应用实例，并对本文方法的霹法复杂度进行了分析。 最后第六搴嚣憨结，磐提爨了一些本文方法翥邀一步辑究豹地方。 关键调：中轴( m a ) 、中轴变换( m a t ) 、硒部修改、影响区域( r o d a b s t r a c t m e d i a la x i s ( m a ) a n dm e d i a la x i st r a n s f o r m ( m a t ) i san e w w a y t or e p r e s e n t t h eo b j e c t ss h a p ew i t hd e g e n e r a t e dd i m e n s i o n i tc a l lb eu s e di nm a n ya r e a ss u c ha s s h a p ea n a l y s i sa n di m a g ea n a l y s i s t h e r ea r el o t so f m e t h o d sf o rc o m p u t i n gm a b u tt h e ya l ll a c kt h ea b i l i t yo f l o c m a d a p t a t i o n i no t h e rw o r d s ，i fa no b j e c t ss h a p ei sc h a n g e dal i t t l e ，m ao ft h eo b j e c t h a st ob er e c o m p u t e de n t i r e l y t h ei n f o r m a t i o ni n c l u d e di nt h ee x i s t e dm a i s n tu s e d a ta 1 1 i n t h i st h e s i s ，an o v e lm e t h o di sp r o p o s e dt h a td o e sm a k eu s eo ft h er e l a t i o n b e t w e e nt h e o l da n dn e wm m sw h e nw ep a r t l yc h a n g ea p o l y g o n ss h a p eb yb o o l e a n o p e r a t i o n ：u n i t ea n ds u b t r a c t m e a n w h i l ei ti si m p l e m e n t e do ng e o m e t r i cm o d e l i n g e n g i n ea c i s6 0 t h i sm e t h o dh a st w os p e c i mc h a r a c t e r i s t i c ： ( 1 ) l o c a la d a p t a t i o n ( 2 ) b a s e do nb o o l e a no p e r a t i o n t h i st h e s i si so r g a n i z e da sf o l l o w s c h a p t e r1 ：i n t r o d u c t i o nt om a ，m a ta n dl o t so f m a a l g o r i t h m s c h a p t e r2 ：t h eb a s i ct h e o r yo f m a ，a n di ti sp r o v e dt h a tt h em e t h o di sc o l t e c t c h a p t e r3 - d e t a i l e dd e s c d p t i o no f t h em e t h o d c h a p t e r 耷i m p l e m e n t a t i o no f t h em e t h o db a s e do na c i s6 0 c h a p t e r5 ：a p p l i c a t i o n sa n da n a l y s i s c h a p t e r6 ：c o n c l u s i o na n df u t u r ew o r k s k e yw o r d s ：m e d i a la x i s ( m a ) ，m e d i a la x i st r a n s f o r m ( m a t ) ，l o c a la d a p t a t i o n r e g i o no f i n t e r e s t i n g ( r o i ) 1 1 第一章绪论 第一章绪论 中轴作为实体外形的一种新的表述方法，最早由b l u m 于1 9 6 7 年提出【1 。 此后，随着人们对中轴的研究一步步的深入，它的有用的特性被一点一点的发现， 其用途越来越广，目前，中轴已被应用到各种各样的领域中，如外形分析、机器 人路径规划、图像分析、有限元分析等。 本章先介绍中轴与中轴变换的基本概念，接着对已有的中轴与中轴变换的相 关研究工作做一较为系统的总结与分析。在此基础上，给出本论文的研究内容、 研究目标及并分析其研究意义。 1 1 中轴和中轴变换 实体( r n 空间) 的中轴( m e d i a la x i s ，m a ) 是指在实体内最大球( r n 空间) 的 球心轨迹，以及这些球心轨迹的极限点。一般它也被称为实体的骨架( s k e l e t o n ) ， 因为这些点都在物体最“中心”点的地方。 就二维这种情况来看，形象一点来讲，相当于在一个二维的物体边界上 都点上火，当整个物体被烧掉时，不同方向火焰交汇熄灭处就是该物体的中轴， 如图1 ： 图l 图l 中，是对一个长方形的中轴的形象 阐述，虚线代表“火烧”的方向，最终火熄 灭的地方，就是这个物体的中轴( 也就是骨 架) 。直觉上，中轴本身包含着物体主要的 几何特性，而且在表示上，它比实体本身更 为简单。( 中轴的作用将在下一节作更为具 体的阐述。) 中轴变换( m e d a la x i st r a n s f o r m ，m a t ) 就是在上述m a 的基础上，给每一 个中轴点加入一个到物体边界距离信息。 第章绪论 1 1 。l 孛轴鲍数学定义： 为了方便研究，很多人针对不同的研究需袋，提出了不同的中轴数学定义。 一般蠡煞，大多数数学定义均菇参考文簸【2 】中麓针对二绦踅形的中牵鸯定义为鏊穑， 基本定义如下： 设。是一个有限遂遗区域，焉c o r e ( q ) 表示q 最大内接圆构成的集 合。所谓最大内接圆c 就是指，不存在其它的圆a c ，满足a e q ，且c 蠛a ， 中辘( 酝a ) 定义魏f ： m a ( q ) = e l e 是c 的圆心，cc o r e ( q ) m a t ( q ) _ ( c ，r ) l c 是c 的圆心，r 是c 的半径 虽然这个定义麓单明了，缀适会建立中瓣壤论，如参考文献【2 】，但是对嶷际 中轴的计算，这个定义缺麓启发性。因此，在舆体的算法实现时，中轴一般定义 为【3 】； 多边形p 内的点集，该点集中的点与多边形边界不同边( 或边的延长线) 上 的两个或两个以上点距离槌等。也就是说，与不嗣边( 或边的延长线) 上的两个 或两个以上等躐离的点的轨迹定义为多边形的中轴。 一般豹多边澎是掺仅食直线段的多边形。褥在v o r o n o i 图的痰塌中，蛰遍地 把含有圆弧的多边形统称为“多边形”。为了驻广义的淡达轮廓图形，甚至可以 把含商其他曲线段的轮廓称为“多边形”。显然，上述嫩义的中轴是不含任何曲 线段( 翔匮弧) 的v o r o n o i 图的定义。随着疲糟领域的不断拓宽、深入，审辅逐 渐显示出其与v o r o n o i 图的本质不同，文献【5 】重新给出了中轴的定义如下； 釉 图2 2 鼓 q 屯 巩 f e ，阪举 第一章绪论 设平面区域d 的轮廓边界为多边形( 可以含有曲线段) e ，e 由边界元素e o ， e l ，e 2 ，组成。我们统称e i 为轮廓边界元素( 谱隘是蠢线，黼蕹，整由魏线 等) 送域d 内珏意点q ，p 为e 上点。 m a ( e ) 的定义为： m a ( e ) 一 q d i d ( q ，e ) - l q - p j h q p j ，麒p j 巾轴是满足以下条传的点q 的轨迹：在轮廓边羚上存谯两个( 或两个以上) 不同的点p i 和p j ，使得q 到这两个点的欧几里德蹑离等于q 到轮廓边界e 的欧 几羹德距离。可戳灌解为一个程轮廓两滚动静变藩昭圆心辕迹：这个交函始终保 持与边界轮廓有魏个以上的交点( 如p l 和秘) 。如图3 掰示。 ，1 2 m a 淼的分类 神( b )( c ) 图3 按照中轴上各个点的属性不同，m a 孛鞍焘可分秀五类，它髑分裂怒： 薄片点：残模型的表嚣上有且仪 有两个点，使得该中轴点到此两点的距 离福黼。满足相闲条件豹所有薄片点， 即到相同魂点的躐塞相溯豹所薅中轴患 组成一张薄片； 缝合点：程模型的表面上有且仪 尖 图4 中轴点分类 第一章绪论 有三个点，使得该中轴点到此三点的距离相等。满足相同条件的所有缝合点，即 到相同三点的距离相同的所有中轴点组成一条缝合线； 接合点：在模型的表丽上有且仅有四个点，使得该中轴点到此四点的距 离相等，则称该中轴点为接合点。 边缘点：位于薄片的边界上且同时不位于缝合线上的点，位于一条直线 上的所有边缘点组成一条边缘线；实际上模型所有的边界线即为边缘线； 尖顶点：除接合点外的边缘线的端点，实际上模型所有的顶点即为尖顶 点。 如图4 所示，从直观上看，在三维空间中，薄片点就是组成二维中轴面的点， 缝合点就是二维中轴面与中轴面的交线上的点，接合点是缝合线与缝合线交的交 点，边缘点即是模型的边界上不包含顶点的所有点，而尖顶点即上模型的顶点。 1 3 中轴( m a ) 和中轴变换( m a t ) 的具体应用 由于中轴具有许多边界表示和c s g 表示所不具有的性质，具有很高的应用 价值，从目前对应用的研究来看，其主要应用如下： 首先：由于它提取了物体的对称信息，所以m a 促进了对称物体的设计和外 形分析；d s u d a re ta 1 用中轴来映射定位染色体结构；a i c h h o l z e r 等人发现中轴 在建筑物轮廓线定义方面非常有用。 其次，m a 具有降低维数的功f l 4 ，5 】( 如图l 平面图形的中轴为线) ，因而可 以大大地降低计算的复杂度，如基于中轴可以进行有限元的分析； 第三，当得到实体的m a t 表示后，可以处理它的骨架以及半径函数，实体 的边界也会自然地随之改变。这种操作可以用于许多领域，例如，计算机动画； 有人把m a 用于c g 研究；b e l l 实验室的h o w a r d “c k e y 把中轴算法运用到三维 文字的生成上。eg h o s h 和c b i g e l o w 用中轴来描述字体形状。通过计算机控制 的刨具，有人用中轴来产生雕刻字。 第四，骨架有助于生成区域的粗糙和精细的面片；在t h eq u e e n su f i n i t e 4 第一章绪论 c l e m e n tg r o u p 髂蚕冀( m e 建) 奠三成系统孛，德翻羯中疆来蓠纯模掇瓣蘩豹一部 分，以减少误差。同样，这个方法也可以用于康拟现实中。b r 。s c h t e i ，l p r a s a d ， 和a n s k o u r i k h i n e 用约束d e l a u n a y 面片和弦轴变换来得到多孔渗水材料的显 微统计信恩，以便进一步的水力计算。 第五，蠡lm a t 嚣确定豹 歉缡瑟其它整谑鳋澎特链在嚣冀生袋、稳憩分辑、 制造仿真以及路径规划中十分黧簧；y r g e a n d d s t e l t s 用中轴来进行廉拟内窥 镜检测：p e t rf e l k e l 等把中轴瓷换作为基于轮廓线的形状重建算法的预处理步骤。 第六，m a ：r 可以用于文梢编码和其它的图像娥理应用； 最霞，m a t 还可戳震予公麓捂定孛。 1 4 相关研究工作 b l u m 1 最早g | 入帮研究了m a t 豹概念，后来b l 凇l 【4 】以及b l u m 秘n a g e l 5 】 穗其瑗予象秘终形描述。不久之麓，久髓又对蒋殊平嚣嚣域提凄了蚤耱m a t 算 法。 中轴的算法众多，按照器不间计算方法大致可以将之分为以下四攒： 1 4 。1 逼近方法 逼近法的思路就是用一个鼹容易求得中轴的物体来近似要求中轴的物体，通 过控制逼近的精度来控制所求得中轴的精度。 n a c k m a n 提出了一秘三维冀法隧，毽薅多嚣体瀵遴竞涛透赛，然聪生残簧架 匏多面俸逐邋。该算法是b o o k s t e i n 提出豹线嚣絮方法的三维接广f 7 l ，它以由凸 多边形组成的多面体作为输入，生成原始物体凸多边形逼近的连通图的m a 。由 于在算法中假设输入的多面体趄光滑弯曲物体的i 精逝，所以输出本身不是多面体 物体的骨架，两是一组与原始物体骨架相切的多边形。 s c o t t 等基于平瑟上静缀含渡扩散过程，撵港了一释确定穆体辩称辘 ( s y m m e t r i c a x i s ) ( m a 的父熊) 的算法【8 】。该算法的过程是：在平砸上，首先 对每一个边界象素沿高度方向位移一个单位，而内部象索位移零单位；然后从边 5 第一章绪论 界开始数值扩散一个波：为了减小误差，波在扩散过程中逐渐衰减。丽波中的局 部极大表示该点为对称轴。虽然该方法对于低分辨率的二值图像十分有效，健是 对于离分辨率图像的误差受f j 较大，并且该算法对内存的处理能力的要求也很高。 1 4 。2 跟踪方法 跟踪法就楚利用中轴的局部连续性，通过跟踪中轴点，或者特殊中轴点如接 会点，来求得物体钓中轴。 m o r l t a n a r i 提出了一种计算多连通平瑟对变形区域的m a t 方法f 9 】，该算法曹 先确定关键分支点，并褥边界轮廓线向内扩展，最后熠逶当的线性或抛物线线段 连接分支点。 l e e 提出了一种对凸多边形区域复杂度为o ( r l l o g n ) 、对凹多边形区域复杂度 为o ( 玎2 ) 的高效m a t 计算方法【l o 】；对予具有h 个孔的多连通区域，n a e k m a n 提 出了一种复杂度为o ( n h + n l o g n ) 的算法【1 1 】； 对予由真线和圆弧组成的多连通平霭区域，g u r s o y 和p a t r i k a l a k i s 提出了 种m a t 计算方法 1 2 ，1 3 ，1 4 ，并将该算法熙予有限元霹片的自动生成和整体外形 的确定； 1 4 3 v o r o n o i 图方法 这种方法就是一般就是利角v o r o n o i 图和中轴鳇对偶关系，通过求解v o r o n o i 圈来求解中轴。 o u i b a s 和s t o l 矗磷究了v o r o n o i 豳积d e l a u n a y 三角化酶关系，提出了四边数 据结构的表示方法f 1 5 】；s u g i h a r a 研究了如何用v o r o n o i 图区逼近各种广义的 v o r o n o i 固1 1 6 】；r o s e n f d d 考虑了基予轴和生成规姗的不同表示方法 1 7 b 在h e l d 的书中详缅介绍了各种与型腔加工相关的v o r o n o i 图髯法f 1 鞠；a u r e n h a m m e r 给 出了另一篇关于v o r o n o i 图算法的完整综述【1 9 】。 l a v e n d e r 等采用基于八义树的方法确定v o r o n o i 图【2 0 】，该算法主要用于集 合运算韵实体模型，舒由多项式不等式表示的基本空闼并、交和差组成的实体， 6 第一章绪论 并生成一个八叉树( 在平面情形中为四叉树) ，该八叉树可以在指定的分辨率上 将空间分解为v o r o n o i 区域。 对于平面和三维情形，b r a n d ，b r a n d t 和a l g a z i 提出了一种通过边界离散的骨 架连续逼近方法 2 1 ，2 2 ，2 3 】。该方法首先对边界进行给定密度的采样，从而得到 一组离散点。这些离散点形成了边界的象素化或体素化逼近；第二步是对上述点 集采用有效的离散点v o r o n o i 图算法；最后，将由量化而产生的骨架分支删除。 该方法试图根据每个顶点数目，对位于v o r o n o i 图内部的顶点进行分类。角点的 数目是按如下方式确定的：首先取每个顶点所属的最大球，然后稍微增加球的半 径，并计算膨胀球与边界的交线。该交线将球面划分为内区域和外区域，每一个 位于边界外部的区域对应一个角点。由于大部分骨架点具有两个角点，所以这些 角点保留，其他点则被删除。 r e d d y 和t u r k i y y a h 基于广义v o r o n o i 图提出了一种确定三维多面体骨架的方 法【2 4 】。他们先计算出一个多面体的大致d e l a u n a y 三角化的结果，并用计算结果 得到其对偶以及广义的v o r o n o i 图。这里计算所得的d e l a u n a y 三角化是传统 d e l a u n a y 三角化的推广，它用直线段连接两个孤立节点。在上述推广的三角化方 法中，节点表示多面体的组成部分( 它可以是多面体的一个面，或者是一个非凸 的边，也可以是一个非凸的顶点) ，所有该三角化是一个抽象的图。它仍然和广 义的v o r o n o i 图具有对偶关系，并且容易计算，这是因为v o r o n o i 图可能含有裁 剪二次曲面。通过裁剪掉广义v o r o n o i 图中位于v o r o n o i 图中，同时又不位于骨 架中的元素( 例如，一个面和一个非凸顶点间的等距点集所包围的部分) ，就可 以得到多面体的骨架。该算法可以显式地确定骨架的某些关键点，但是不包含组 成骨架的曲线和曲面的高精度显式表示。在上述方法的基础上，t u r k i y y a h 等基 于局部化的d e l a u n a y 三角化算法，提出了一种三维实体模型精确骨架的加速生 成算法【3 3 】，该算法具有与骨架逼近所有点数相关的线性复杂性。 s h e e h y 等研究了基于某种分布的边界点( 类似于b r a n & 的方式 2 3 1 ) 的定义 域d e l a u n a y 三角化 2 5 1 ，以试图确定一个三维实体中轴的拓扑结构。文章给出了 从这些特征计算中轴的算法步骤。 e t z i o n 和r a p p o p o r t 提出了一种基于空间剖分的三维多面体v o r o n o i 图计算方 7 第一耄绪论 法f 2 6 】，该方法允许局部彝罄分诗算v o m n o i 圈。透过爨羯( v o r o n o ig r a p h ) 豹 符号和几何部分分离计算的方式，使算法更加鲁棒。此外，c u l v e r 等人述提出了 种三缝多瑟俸豹m a t 舔踪算法，该算法逶遥袋胡精确翡运冀帮精确豹咒侮表 示的方法来提高精度。为了提高m a 元素的搜索效率，算法采用了空阃分解和 线性规划技术。在该方法中，面片是醴二次曲面的形式表示的。j 琏：外，方法中还 镪含了一静毅的平面代数曲线的拓扑分树算法，以及一种快速 敬忒几何计算的数 值方法。 w o l t e r 帮毽鹃劲手翻磷究了翔簿弱丽溅逮等鞭函数诗算稿露，芝与两条绘定蘸 线等距的中轴线 2 7 ，2 8 ，这种方法同样可用于乎面曲线情形。此外，他们还将 t 述方法用予计算参数曲面上，而不是欧式空阉中的v o r o n o i1 虱 2 9 1 。 1 4 4 其他方法 c h i a n g 研究了由分片c 2 连续潼线截豳的区域f 3 0 】，并在区域髑围的邻域内谶 行胞腔分解。然后根据d a u i e l s s o n 的欧式距离交换算法f 3 1 】，对每一个胞腔赋予 该胞腔到区域边弊上最i 聩点的邋似距离德。为了解释欧式距离变换，考虑如下给 定的二镶銎像s ( 每一个象素( i 0 ) 的值为0 或1 ) ，并记值为0 的象豢的集合为s 。 那么，s 上的距离映射定义为一个标量函数： l ( i ，) = r n i n ( d k i ，d ，s 、】) 英审d 是蘧麓函数。鲑巢d 楚两个蒙素润静歉式疆蓠： a a q , j ) ，( 是，耄) ) = 一黟2 o 一定存在 o 搜德： h ( a i ，q 2 ) 占 ( r ( q 1 ) ，r ( n 2 ” 求得第一个满足条件的交点，并把对麻的舅韩一条中轴打成两段，压栈： 条件指：以交点为脚心，到对应边上距离，为半径圆柱物体内 在拄囊第一个后，找弱所存帮第一个交点参数在谨羞r e s a b s 内瓣满足条辞魏 点，也把对应的另外条中轴打成两段，愿栈： ； i 赫荣上面循环来找到任何满足条伴的中轴) 判断断点是不是在该中轴卜，程，鄢么该中轴记入结果： ”梭疆露素： c o n t i n u e ； j 3 4 布尔并焉差操作的r o i 的鬃体确定方法 3 4 1 布尔并操作的r o i 的具体确定方法 确定所有组成r o t 的边界煮线段和点，关键的一步疑我到消失的边弊，在布 尔并操作的过程巾，剥髑下一章提及的a c i s 属性类，可以很方便地套找消失边 界，所以，其r o i 的确定，将在下一章里面详细的讲述，当然，这里新增的凹 点，也要搬久到r o i 里瓣。鲡嬲i 3 孛a ，b 两点。 第三章基于布尔并与差操作的中轴生成 图1 3 3 4 2 布尔差操作的r o i 具体确定方法 针对布尔差s u b t r a c t 操作的r o i 的具体确定，其初期的工作与布尔并操作是 一样的，即利用我们所定义类及其提供的数据结构和方法，把删除边的对偶边都 加入。具体实现将在下一章讲述。 这里主要针对布尔差操作的s u b t r a c t 操作的特殊性进行讨论，即即使m a 的 二 厂 图1 4 两个边界元素都没有被删除的话，该m a 也不 一定继续是结果物体的m a ，如图1 4 所示， 虽然图中虚线m a 两个边界元素都没有被 破坏，但是这段m a ，至少是该m a 的右边一 部分将不再是新实体的m a 。当然减的那个物 体的m a 更是完全不存在了。所以，在这种布 尔差s u b t r a c t 操作的情况下，我们还要用减物体的保留边界元素来裁剪“被减” 的那个实体的m a 。然后把裁剪出去的m a 片断对应的边界元素，加入到r o i 中去。这就是s u b t r a c t 的算法思路。 基于上述分析，具体的裁剪算法如下： 首先假设被减物体的剩余部分是一个连续的片断，因为如果不是连续的，可 以看成是若干段连续片断组成的，用同样算法解决每一段即可。 在这种假设下，如果其中一段m a 被这个连续片段裁剪，被裁剪掉的部分也 是连续的，那么我们把m a 的一个顶点作为参数0 ，另一个作为参数l ，用该片 第三章基于布尔并与差操作的中轴生成 段裁剪出t m i n 和t m a x ，那t m i n 和t m a x 对应的m a 的边界元素就被加入到r o i 中了。 如图1 5 所示：模型b 一模型a 后，a 物体 剩余边界就是a b ，b c ，c d 边，和b ，c 点。 那么裁剪操作可以划分为：边裁剪和点裁剪 1 1 边裁剪 图1 5 边对m a 会有裁的情况是指：当m a 到其原来g e n e r a t o r 的距离大于了m a 到裁剪边的距离。这样，通过裁剪边和任何一个边界元素的角平分线和该m a 的关系来确定被裁剪情况。可以确定区域参数t l ，t 2 内m a 被裁剪。如图1 6 ， 所示，a b 为中轴e f 的一个g e n e r a t o r ，c d 是一条裁剪边，如图虚线为c d ，a b 构 成角的角平分线，那么显然a 区域离c d ，比较近，b 区域离a b 近，所以线裁剪 的目的就是求得中轴段e f 在b 区域中的那一段。然后把被裁剪的那一段用参数 t 的形式表示。 d a # b a b 图1 6 2 ) 点裁剪 点对m a 会有裁剪的情况是指：m a 到其原来 g e n e r a t o r 的距离大于到该裁剪点的距离时。此时只 ，要通过上面的参数，构建一个关于参数t 的二次方 程，求得t l ，t 2 内被裁剪。原理和图1 6 是一样的， 不同的是这时是用抛物线分为a ，b 两个区域。 综合1 ，2 两部分，依次计算t l ，t 2 ：找到t m i n ， t m a x ，即可得到最终的裁剪结果。用t m i n ，t m a x 断开m a ，把t m i n ，t m a x 区间 的m a 的边界元素加入到r o i 中去。即得到s u b t r a c t 对应u n i t e 额外的r o i 收集 操作。 篇四章原型系统的实现 第四章原型系统的实现 4 。1a c i s 系统蔺介 a c i s 是由美国s p a t i a lt e c h n o l o g y 公司推出的，s p a t i a lt e c h n o l o g y 公司成立 于1 9 8 6 年，并于1 9 9 0 锥首次推出a c i s 。a c i s 最早的汗发人员来自美国t h r e e s p a c e 公嗣，瑟t h r e e s p a c e 公司黪刨办入来叁予s h a p e d a t a 公霭，因她a c i s 岿 然继承了r o m u l u s 的核心技术。 a c i s 的重要特熹是支持线挺、兹瑟、实体统表示豹菲正瓣形体造澄技拳， 能够处理非流形形体。 a c i s 产品慕角了组件技术，其核心蔻几何造型器( g e o m e t r i cm o d e l e 讳，还包 括一些可与核心集成的缎件，称为外壳( h u s k ) 。核心只提供一些基本的几何造型 功能，藏它高级功能在外壳中掇供，外巍可以题s p a t i a lt e c h n o l o g y 公司提供的， 妊亵缀滚染( a d v a n c e dr e n d e f i n g ) 步b 壳、三维工舆籀( 3 dt o o l l d t ) # l - 轰等，也可以 是用户开发的。a c i s 核心结构与a c i s 核心集成的外壳如图1 7 所示： 图1 7 a c i s 模型袋示由备种属性( a 删b u t e s ) 、几何( g c o m e 怔e s ) 和拓扑( j i 砷o l0 _ 舀e s ) 第酗章原型系统的实现 缀成。a c i s 是掰c + + 开发酶，弼c 针粪鹣层次嶷现了穰念模蘩，e + 粪的屡次 如图1 8 所示： e n 删袭 - l 8 型搂燃然誉簿。端毋i 翔 。j 。i j i 毒 j i 舞溢塔基。划嚣一； j ：t r 巍 黼t 交了g 赫跫譬l a 黼t o i u s 觥j* 二毒i o i i 。：j 囊_ 1 j 1 _ i 一一。越二。 i _ 蔓i 霉i ：i _ 、1 1 _ i _ 一拶 紧j 等麓i j 。、- 。? 。? 。，曩：曩i ；一 ) i j l | ；_ _ i _ o i 要”| j 一_ 一j i 墨曼撼疆 | 翟“毫+ 薰蘩爨攫f 。、譬 一 j ： 薯薯 精攫1 _ _ 1 i 一_”叠。 曩_ 毒一： 毽1 8 几何是指模型的物理描述，如点( p o i n t ) 、曲线( c u r v e ) 、曲面( s u r f a ce ) 、直线 ( s t r a i 曲t ) 椭i 圜( e l l i p s e ) 等；拓季卜是指各种几何实体在空间的关联，如体( b o d y ) 、线 ( w i r e ) 、块( 1 u m p ) 、壳( s h e l l ) 、予轰( s u b s h e l l ) 、蕊( f a c e ) 、环l o o p ) 、耳边( c o e d g e ) 、 边( e d g e ) 年t l 顶点( v e r t e x ) 等；属性依附于模型实体。更详细的说明请参见a c i s 有 关文挡。 a c i s 核心撮供了一个几何总线，以连接其它的夕 壳与应用程序，如图1 9 所 示： a c i s 与应弱程痔豹器覆包援； 1 a p i 函数 a p i ( a p p l i c a t i o np r o c e d u r a li n t e r f a c e ) 函数是个函数集，应用程序通过调用 这些函数鞋撵作禳蘩。a p i 函数疆入了变量镶谈检查、臼恚处毽帮孛继模型管 理。 第四章原型系统的实现 2 属性 图1 9 a c i s 属性( a t t r i b u t e s ) 机制向开发者提供了具体的应用程序数据关联到a c i s 几何或拓扑实体( e n t i t y ) 的方法。属性与模型数据一起存储或恢复。开发者也 能利用现存的属性机制，为特定的应用导出新的属性类。 3 类 类( c l a s s e s ) 界面是定义a c i s 几何和拓扑模型及其它a c i s 特征的c + + 类的 集合，开发者可以直接利用这些类和方法，为特定的应用导出新的类和方法。 4 宏 预处理器宏( m a c r o s ) 用于简化通常的编码任务。这些任务包括从实体 ( e n t i t y ) 和属性( a t t r m ) 类派生出新的、具体的应用类，定义a p i 函数和处理 日志。 4 1 1 属性类 m a 作为实体额外的信息需要一种机制附加到实体上面去。而a c i s 通过属 性类提供了这方面的机制。在本算法的实现中，就是利用a c i s 的属性类特点， 来方便地处理前一章提到的各个步骤。 3 0 篼四章原型系统的实现 a c i s 的类都是e n t i t y 类( 实体类的继承类) ，包括我们这里要谈及的属性 类。属性是用来把附属信息依附到e n t i t y 的。每个e n t i t y 可以具有零个或 者多个属性类。a t t r i b 类是属性类的公共父类，提供所有类共同需要用到的数 据和方法。a c i s 用户可以通过继承a t t r i b 类来附加自己的数据。 a t t r i b 类维护附加于e n t i t y 的属性类列表。属性类可以携带简单数据、 指向其他实体类的指针，或者指向任意长度的用户数据。 特定的属性类可以通过继承a t t r i b 基类来构建，用户自定义属性类说明 a c i s 是个真正的增值造型系统。 a c i s 内核用a t t r i b s t i 和a t t r i b _ t s l 类，它们都是从a t t r i b 继承来 的。 我们可以从这些类继承来定义我们自己的属性类，用来存储应用软件专用的 和e n t i t y 有关的数据。 a c i s 用通用属性类来进行应用软件间的数据交换。还有一些其他的类。但 是这些类都不足以用来保存我们的m a 属性，我们必须用自定义属性类来保存 这些信息。如图2 0 。 图2 0 利用属性类的另一个好处是，它能很好地结合到布尔操作中，下面我们讲述 自定义属性类如何和布尔操作结合，以方便地解决前一节提到的消失边界的确定 和r o i 的确定。 第四章原型系统的实现 4 1 2 属性分割和合并 图2 1 如图2 1 是属性类和e n t i t y 的关系图，当一个实体被创建、删除、复制或 者更改属性的时候，默认情况下a c i s 造型系统对中轴不做任何事。 图2 2 但是这种默认情况并不是满足我们的要求。如图2 2 ，当一个小块插入到大块 中，然后再从大块里面减去的时候。面a 分割为面a 和a 两个面。如果两个类 都要保存一个属性类信息，那么必须复制属性类，并把它附加到a ，上去。此外 第四章原型系统的实现 我们要重载属性类的虚函数s p l i t _ o w n e r 。函数s p l i t _ o w n e r 有一个参数，指向新 生成的蘑a ，。赝以在分裂甏a 匏孵候，就会调焉鼹性类黪s p l i t _ o w n e r 函数，然 后分裂属性洪。 v i r t u a lv o i ds p l i to w n e r ( e n t i t y4 ) ； 挚 对m a 瓣特患，鼗髓浚及豹e n t i t y 是e d g e ，我髓在e d g e 上定义螽己 的a t t r i bm a t 类，用来保存指向该e d g e 相关的所有m a 片断列液，在e d g e 分袋瓣露镁，我察需爱检索这个虱表，分裂跨透舞懿m a ，玺躐颓静a t t r i bm a t 类，然后把生成的属性列表分配到锫个属性类上。如图2 3 所示，糨线条表示边 界，细线祭寝示中轴辑，当虚线边擀被分裂疆来 戮戮翥篇湖a t 岭t r i 徽bm 碟a t 萎骶i 三7 后分别更新到每个新边界的列表 xj i 二n l 里瑟去。 图2 3 而当两个顽合并的时候，如图2 4 谣b 和b 合并成新面b ，那么b 和b ，所对 应酌a t t r i bm a t 属往需袋合并。需要耋裁合并灞数m e r g e _ o w n e r ，这个函数 有两个传递参数，第一个参数是b ，第二个参数说明该属性是否被删除，因为 合并以后只能傈留一个a t i r bm a t 。 v i r t u a lm e r g eo w n e r ( e n t i t y4 ，l o g i c a l ) ； 图2 4 第强章原型系统的寰戏 觑外，在实现时，述楚有一个 地方怒需要注意的，如图2 5 ：物体 b 和b 合并的时候，而且渴 被删 除的孵谈，在把b 中a t t r i bm a t 类中所有m a 加入大b 的 a t t r j bm a t 的列表中时，必须更 新所商这些列表中的m a 的 g e n e r a t o r 指针，因为b 这个实体 己经举复存在了，不然g e n e r a t o r 将指向一个空指针。这个问题在 s p l i to w n e r 函数中同样需露注意。 4 1 。3 布尔操作和髑瞧 圈2 5 b a c i s 平台对该算法裔麓很好的支持，因为a c i s 里面布尔操作对属性有着很 好的支持，即在布尔操作的同时，a c i s 内核会自动处理属性信息。这使得r o i 的收綮工作变得比较简单。具体将在下一节讲述。 4 。1 4 m a 求交 a c i s 提供了e d g e 求交的函数，所以m a 求交也就变得很简单。 4 。2 属性类和本文算法的结合 a 雌 5 露 图2 6 4 2 1a c i s 中实现u n i t e 操作 。在布尔撵传的过程中，_ k n f f 3s p l i t _ - o 粥燃 帮m e r g eo w n e r 丞数会被调瘸，怒嚣者结合起 来，就可以徽好的解决r o i 收繁的问题。下面 以图2 6 为例来说明这两个函数的应用。 第四章原型系统的实现 翔图2 6 ，当a ，b 秀令锈豁徽合并操终戆辩谈，羯珀a 稻a b a 来表示a 中懿 a b 边和b 中的a b 边，那么，在合并时，c d 边在a 点对a t t r i b _ m a t 鹪性调用 s p l i to w n e r 函数，把c d 边分割成c a ，a d 边，这个时候，要在a d 边上添加 a t t r i bm a t 属性，并要把c d 边上的m a 分成两缀分配到两段上，如果有m a 跨a 蠢，述簧将该淞封颧。淀意在分琵豹过程巾，潼为产生了囊豹a d 边，要 调整g e n e r a t o r 指针。 然后，对于新的a d 边，又程b 点对a t t r i bm a t 属性调用s p l i t 前面一样的方法处理。 等c a ，a b ，b d 边生残磊，a b a 秘轰堍籍调霜m e r g eo w n e r ，这霹要熬瑟令m a 列表合并。薮实这里也做了g e n e r a t o r 的更改工作，但是这里新合成的边马上被 删除了，遮步工作也就没什么意义了，之所以黧加这一步，是因为还肖可能还 建 a 口 匿2 7 e 罐 需要利用m e r g eo w n e r 操作处理图2 7 所示 豹猿况 如图2 7 掰示，当a ，b 合并的时候， 其他操作和前筒样，只是c b 和b d 将进 行一次m e r g eo w n e r 操作，此外则需要在 合并c b ，b d 媳属缝豹时候更改g e n e r a t o r ， 蠢戈e b 秘醚逑里嚣毒一个将会漓失。 最后，上一步合成的e d g e 被删除， 此外，就是骚判断删除边界的对偶边了，在a c i s 熙面提供了l o s ed e f 宏， 月来定义嵩蔗性被测除的对候调用的函数，我们只黉在这个宏里蠢搜索m a 剜 表，瑟瑟璃途热入至lr o i 孛。 注意前丽提到的顺序也有可能是b 先断，然后礴在a 点断，但是这个对算法 实现没有任何影响。 4 2 2a c i s 中实现s u b t r a c t s u b t r a c t 的算法有些难度，因为新增的边，也就是被减去物体的边，能够影 第器掌鞭壁系统豹蜜璐 晌那些区域很难确定到一个很小的范围( 在最后一章，提出了一些想法来减小检 溅范围) ， 一般，前期确定r o i 的方法和合并操作一样，如图2 8 ，a d 边被删除，那么 赫边对成的对儒逑将被加入昀r o i 中，注意这可能有多条边，因为a d 可辩应 多条m a ，这点和边对应的唯一性并不矛盾，因 为它楚分段对应，每一莰遴楚对应一段孛赣，多 断对应的情况只能出现在点类型的r o i 上。 然嚣，我翻需要速魇b a 生成耱体豹逮表， 找出a b ，b c ，c d ，把这三条边，和b 、c 点加入 到r o i 中，这鎏耨增豹边j 荟是愆较好技豹，灵簧 图2 8 我们把a 物体在做布尔操作前，去掉所有的a t t r i b _ m a t 属性，那么在新物体 b a 中没有a t t r i bm a t 疆性售惑鲍就是耨增边。 找到这三条边以后，用前一章针对s u b t r a c t 的r o i 嫩成算法，来对所有m a 皴裁赘攥终，搜剜辑寿豹r o i 。 这篷，遍历所有m a 米确定r o i 有点无奈，这违背了这篇论文“把影响局限 在蜀帮”夔裙袭。毽是因必凝魏镕戆影嫡区域突在是难戳确定，搿瑷暂辩只缝囊 这种效率不高的办法。在以后的工作中，我们将考虑利用中轴区域分割的特性， 来降低绣要判叛瓣m a 。 4 2 3 实现难点 总得来说，幽子a c i s 属性灵活、开放的特点使得算法实现有着很大的方便， 毽是农实现珏重豹磺存在一皴实现的关键点和滩点。首先，在a c i s 进幸亍s p l i t 帮 m e r g e 的过程中，m a 因为要改变到新的边界冗素中去，所以，g e n e r a t o r 指针的 调节怒实现的一个关键点，当然这不能算是赡点。 疑次，就是a c i s 对s t r a i g h t 支持不满足该算法的要求，s t r a i g h t 就无限赢线， 区别予l i n e ，l i n e 是有限纛线段。s t r a i g h t 是两个点生成的中轴段，l i n e 是礴个线 段边界元素产生的中轴段。a c i s 撼供昀a p i 函数在对阉s t r a i g h t 和l i n e 求交的 第四章原型系统的实现 时候，以l i n e 的一个端点作为交点返回，但是，我们要求的交点是按照伪代码里 面定义的跟踪方向上的第一个l i n e 端点，所以当s t r a i g h t 和l i n e 求交的时候，我 们要自己写求交函数。 3 7 塑至至堕型墨堑塑窒里 第五章原型系统的应用 5 1 布尔并操作时的中轴生成 表1 ：曲轴零件建模各步的中轴计算时间 ；? 蔓 i 量 _i - ：一一 s 嚏： c i 蠢d警；j ：；移。 誊jf g 一 i 垮 l f ： 1 | j ：1 曩： t i m eo 0 1 60 0 4 60 1 2 5 o 0 1 60 0 6 30 0 3 l0 0 9 4 o 0 1 6 本节给出两