（计算数学专业论文）nurbs曲面间最小距离算法研究及其计算机实现.pdf

摘要 本文深入细致地研究了任意两张n u r b s 曲面间最小距离的求解问题，通过 大量实验分析，对分裂算法和遗传算法提出了改进思路和方法，有效地解决了自 由型曲面间最小距离计算问题。 首先，根据曲面的分裂以及包围体的思想，介绍了一般n u r b s 曲面间最短距 离的分裂算法，给出了算法的详细流程。并且，根据分裂算法的特点，综合使用 求解n u r b s 曲面控制顶点的凸包围多面体的增量算法和求解凸多面体之间距离 的g j k 算法替代了包围盒( a a b b ) 算法，对于分裂算法做了改进。还使用了“一 致代价法”的思想改进搜索过程，提高7 算法的收敛速度和精度。在一定精度要 求下本文的方法比文 1 6 的速度快。 然后，运用遗传算法给出了任意两张n u r b s 曲面之间最短距离的求解。针对 遗传算法的群体多样性过低的缺点。提出了两种改进方法，使得群体始终充满多 样性。使算法在较小的群体数目下仍能以较快的速度逼近全局最优值。本文不仅 将文献 1 1 的结果推广到了n u r b s 曲面的情形，而且使遗传算法计算更加稳定， 收敛速度有了明显提高。 最后，对于分裂算法和遗传算法做了算法分析和对比，并且给出了大量实例 以验证算法效果。研究了时间复杂性，给出了两种算法各自的优缺点。 以上的算法都在计算机上用c + + 语言得以实现，结果表明，本文改进的算法 快速、有效。 关键词：最小距离n u r b s 曲面分裂凸包增量算法g j k 算法遗 传算法 a b s t r a c t t h i st h e s i sp r o p o s e st w oa l g o r i t h m sf o rt h em i n i m u md i s t a n c eb e t w e e n g e n e r a ln u r b ss u r f a c e sr e s p e c t i v e l y f i r s t l y ，b a s e du p o nt h et e c h n i q u eo fs p l i t t i n gt h en u r b ss u r f a c e sa n d b o u n d i n gc o n t a i n e r s ，as p l i ta l g o r i t h mi sa p p l i e dt oc a l e u l a t et h em i n i m u m d i s t a n c eb e t w e e nt w og e n e r a ln u r b ss u r f a c e s t h e n ，i n c r e m e n t a la l g o r i t h m f o rc o n v e xh u l la n dg j ka l g o r i t h ma r e e m p l o y e d t o i m p r o v et h es p i l t a l g o r i t h m sp e r f o r m a n c e t h e n ，t h et h o u g h to fu n i f o r m c o s ts e a r c hi s a p p l i e dt oi m p r o v et h ea l g o r i t h m t h ei m p l e m e n ts h o w st h a tt h ei m p r o v e d s p l i ta l g o r i t h mi sm o r eq u i c k l y s e c o n d l y ，t h eg e n e t i ca l g o r i t h mi se m p l o y e dt oc a l c u l a t et h em i n i m u m d i s t a n c eb e t w e e nt w og e n e r a ln u r b ss u r f a c e s t h e n ，t w om e t h o d sa r ea p p l i e d t ok e e pt h ed i v e r s i f i e dv a r i e t yo fc o l o n y ：r e s e r v et w os p e c i a lu n i t si n n e wp o p u l a t i o na n di n c r e a s et h em u t a t i o nf a c t o r t h i sm a k e si t p o s s i b l e t oa p p r o a c ht h eg l o b a l o p t i m a lv a l u ew i t hl e s sn u m b e ro fu n i t s i n c o m p a r i s o nw i t ht h es t a n d a r dg e n e t i ca l g o r i t h m ，t h i se n h a n c e dg e n e t i c a l g o r i t h mi s m o r eq u i c k l ya n dr e l i a b l y f i n a l l y t h i sp a p e rm a k e sc o m p a r i s o nb e t w e e nt h e s et w oa l g o r i t h m s ， a n de s t i m a t e st h ec o m p u t a t i o n a lc o m p l e x i t yo ft h e s ea l g o r i t h m sa n d p o i n t s o u tt h ed i s a d v a n t a g ea n da d v a n t a g eo ft h e s et w oa l g o r i t h m s m a n ye x a m p l e s a r ec a l c u l a t e du s i n gt h e s et w oa l g o r i t h m s t h ep r o g r a m so ft h ea b o v ea l g o r i t h m sa r ed e v e l o p e db yc + + l a n g u a g e i ti ss h o w e dt h a tt h ea l g o r i t h m sa r er o b u s ta n de f f i c i e n tb yc o m p u t a t i o n t h em i n i m u md i s t a n c eb e t w e e nn u r b ss u r f a c e s k e yw o r d s ：m i n i m u md i s t a n c e n u r b ss u r f a c e si n c r e m e n t a la l g o r i t h m c o n v e xh u l l g j ka l g o r i t h m s p l i to fn u r b ss u r f a c eg e n e t i ca l g o r i t h m 南京航空航天大学硕士论文 第一章引言 1 1 距离求解问题现状 距离求解问题是机器人技术、计算机仿真、工业设计等方面遇到的一个关键问题， 如机器人无碰撞路径运动规划、实时碰撞检测等等问题，都需要涉及到物体之间的距 离计算和两个物体之间是否发生碰撞。 目前距离求解问题的研究主要集中在空间多面体，特别是空间凸多面体间的距离 求解上。因为多面体形状规则，计算简单。其中，g i b e r t ，j o h n s o n & k e e r t h i l l l 和 l i n c a n n y 口】于1 9 8 8 年和1 9 9 1 年分别提出了求解两个凸多面体之间距离的快速算 法：g j k 算法和l c 算法。对于一般多面体，q u i n l a n 6 1 于1 9 9 5 年利用包围球的概念提 出了一般多面体之间距离的算法。 在实际应用中，以自由曲面作为表面的物体是越来越多，比如涡轮叶片、船的外 壳、汽车表面、飞机机身等等。现在的主流造型系统都直接采用自由型曲线、曲面模 型。其中，n u r b s 方法在形状定义方面有强大的功能和潜力。1 9 9 1 年，国际标准组织 ( i s o ) 颁布的工业产品几何定义的s t e p 标准，就把n u r b s 作为唯一定义自由型曲线、 曲面的数学方法。近几年来，主流商业c a d 软件纷纷推出了n u r b s 功能。因此，讨论 n u r b s 曲面之间的距离无疑是非常有意义的。 对于相对凸的曲面，可以首先估计出近似的近点对，然后使用n e w t o n r a p h s o n 迭代解来精化解。但是这种方法有非常大的局限性：曲面必须是相对凸的，否则算法 就可能会收敛到局部优化解。c o l i n t u m b u u & s t e p h e n c a m e r o n f ”1 甚至提出了基于g j k 算法的以凸n u r b s 曲面为边界的三维空间体之间距离的算法。但是，在实际应用中， 曲面相对凸的情况是很少见的。所以该算法并没有普遍意义。 不象相对凸的曲面那样有良好的几何性质可以利用，一般形状和任意位置下的两 张n u r b s 曲面，距离求解是非常复杂和困难的。为计算它们之间的距离，2 0 0 2 年， 刘浩“”提出了一种分裂算法：运用n u r b s 曲面的分裂技术分别将n u r b s 曲面一分为四， 对每一张子曲面片做 7 - c a x 包围盒，然后进行配对，根据盒子之间的距离，排除不 可能存在近点对的曲面对，而对可能存在近点对的予曲面对继续分裂。当达到一定的 分裂层次，用控制网格点进行点点比较得到曲面之间一对距离最近点。但由于使用长 方体包围盒近似代替子曲面，包围盒之间距离与子曲面之间实际距离往往相差很大， 导致搜索节点数过大，计算速度得不到保证。此外，该算法虽然对搜索树进行了裁剪， 但在选择扩展节点时完全是盲目的，可能首先扩展的是不大可能存在近点对的子曲面 片，增加了不必要的搜索，自然影响了算法速度。 n u r b s 曲面间最小距离算法研究及其计算机实现 除了分裂算法外，2 0 0 2 年，文 1 1 提出了求取b 样条曲面间最小距离的遗传算法。 这是一个求最小距离比较新的一种思路。遗传算法的应用非常广泛。从搜索角度，应 用遗传算法求曲面间最小距离，具有许多独特的优点： 1 不必非常明确描述问题的全部特征，通用性强，能很快适应问题和环境的变化； 对领域知识依赖程度低，不受搜索空间限制性假设的约束，不必要求连续性、可导或 单峰等。 2 从多点进行搜索，如同在搜索空间上覆盖的一张网，搜索的全局性强，不易陷入 局部最优；具有隐并行性，非常适合于并行计算。 但是遗传算法的本身的性质也决定了该算法不够稳定，算法很有可能会收敛到次 优解而非最优解。因此也存在有待改进的地方。 本文对上述两种算法进行大量实验和分析，发现问题，提出改进思路和方法，试 图给出任意n u r b s 曲面间最小距离求解的有效算法。本文主要研究内容为： i 引进n u r b s 曲面间最小距离分裂算法，研究分析该算法的存在的问题，运 用n u r b s 曲面的凸包性和对算法流程搜索方法的改进，提出包围体替代包围盒思想， 使用增量算法求凸包、g j k 算法求凸包之间距离，给出改进的分裂算法，并使用“一 致代价搜索法”的思想改进搜索算法，提高算法的逼近精度和速度。 2 介绍遗传算法的原理，给出任意n u r b s 曲面间最小距离求解的遗传算法， 进一步提出增加特殊个体和增大突变概率的方法克服遗传算法的群体多样性过低的 不足，使算法在较小的群体数目下仍能以较快的速度逼近全局最优值，以便获得更加 稳定；收敛速度更快的最小距离算法。 3 给出算法分析和结果对比，运用大量实例以验证算法的效果，算法时间复杂 性探讨，对于分裂算法，引入了穿透率和实际分支因素两个概念对改进前后的算法进 行对比分析；对于遗传算法，则主要对比稳定性和迭代次数。而且，还对分裂算法和 遗传算法作比较，讨论它们在实际应用中的可行性和适用性。 本文共分为五章，第一章是引言，介绍距离求解的现状和本文的研究工作等，第 二章详细介绍分裂算法并且对分裂算法作改进。第三章采用遗传算法求解n u r b s 曲面 之间的最短距离，考察算法的稳定性，探讨提高算法的速度和效率。第四章是对算法 的分析对比，进行大量的实验验证算法的效果。最后一章是对本文的总结和对以后工 作的展望。 1 2 n u r b s 曲面简介 1 2 1n u r b s 曲面的表达式定义为： 南京航空航天大学硕士论文 b i , k 0 玛，小弦，i ， p ( u ，v ) = 等等- 一( 1 1 ) b i , k 0 觋( v 弦， i - oy = o 式中v j ，为控制顶点，彬，为权因子，e 。0 ) 和口川( v ) 分别为沿“向的七次和沿v 向的， 次日样条基函数，由下列递推公式定义： 啪) = ：；，嚣细+ 1 e 。0 ) = j 尘：! l e 卜0 ) + 生盐l 竺e + 。一- ) ，女1 “+ i 一“ “j + “一甜l + l = 0 式中k 为幂次；虬( f = o ，1 ，m ) 为节点。 另外，本文约定：u 向矢量和v 向矢量中端节点的重复度分别取为k + 1 和“1 以 便使n u r b s 曲面具有角点几何性质。n u r b s 曲面还有凸包性：曲面完全被包容在由控 制顶点组成的凸多面体内。 由于在主流商业软件中n u r b s 曲面曲线一般都是三次的，所以本文中所有的 n u r b s 曲面的次数都是三次的。但是，对于其他次数的n u r b s 曲面本文提出的算法也 可以使用。 1 2 2 d e - b o o r 算法 一般应用中，可以采用( 1 1 ) 求取曲面上的点。但是d e - b o o r 更加快速简洁。以 下是b 样条的d e b o o r 算法公式： p 0 ) = 嘭m 卜。( “) = = 钟，“ x 2 ( 2 5 ) 【x i y 2x l y 2 定理2 1 设空间中有两个长方体p 和q ，其信息分别为p ：( x p m i n 儿。，邵。) 与 ( 都一，炸m “，却一) ，q ：( x q 。，y g 。，“。) 与( 一，y 口。，z 口。) ，为了方便，记： ， ： x p 。，x p 】，印： y p 。，y p 。】，：【z p 。i n ，z p m “】； k ： 吻。j ，一】，b ： y q “n , y 口。】，k ： 幻。，一】： 则p ，q 之间的距离是：d i s = f 2 ( k ，k ) + d 2 ( ，一，b ) + d 2 ( k ，k ) 】j ( 2 6 ) 。 根据以上的定义，可以得到两个包围盒之间的距离。如果两个包围盒相交则距 离值为0 。 2 3 4 算法实验 从上面的算法可以看出，随着分裂层次的增大，所得到的最短距离也随之就越精 确。但是，计算所需的时间也会明显增大。为了考察该算法的效率，对以下算例一做 了实验，实验平台为v i s u a lc + + 6 0 ，p e n t i u m41 5 g ，w i n d o w s x p ，绘图平台为o p e n g l 。 算例一：设，为凸曲面，：为任意一张曲面，应用分裂算法求该两曲面间的最小距 o 南京航空航天大学硕士论文 离，分裂层次= 6 。结果如图2 - 3 图2 - 3 分裂算法n u r b s 曲面间的最小距离 为了了解分裂层次，和计算时间，以及计算结果d 的关系，下面做了一些实验。 算法实验一：对算例一取分裂层次从3 - 8 的情况试验；设参照结果露：通过两n u r b 8 曲面在每个方向上各取4 0 0 个顶点，然后点点对比所得到的结果。计算结果见表2 1 。 表2 - 1 不同分裂层的计算结果( 行为搜索节点数) fdn t ( s ) 正 31 5 3 5 4 3 32 8 10 0 2 01 5 4 2 0 8 4 41 5 3 9 4 7 31 0 6 90 i 0 01 5 4 2 0 8 4 51 5 4 1 5 1 83 6 5 5o 3 2 1 1 5 4 2 0 8 4 6l - 5 4 1 9 6 61 3 1 6 7l _ 1 6 l1 5 4 2 0 8 4 71 5 4 2 0 5 44 8 2 5 5 4 2 7 61 5 4 2 0 8 4 81 5 4 2 0 7 71 7 0 3 9 81 5 9 6 31 5 4 2 0 8 4 实验一分析：随着分裂层次的增加，得到的结果的精度也有了一定的提高。但是，搜 索节点数几乎每增加一分裂层就要增加4 5 倍，计算时间也随之大幅 增长。另外，可以看出，搜索节点与所需时间是成正比的。在上面的例 子中，如果分裂层次达到7 8 层，搜索节点数会变得很大，需要花费 的时间也变得基本不可接受。因此，如果对算法的时间要求比较高，本 n u r b s 曲面间最小距离算法研究及其计算机实现 算法只能求得两曲面之间的不是十分精确的最短距离；如果需要更加精 确的距离，虽然可以采用本算法，但是算法所需的时间将很长。 2 4 分裂算法的不足以及改进思路 2 4 1 分裂算法的不足 分析分裂算法不难发现，包围盒的过大是搜索节点数过大的主要原因之一( 见图 2 - 4 ) 。虽然两条曲线仍相距较远，但是两个包围盒的距离却很近，这样就造成了不必 要的搜索，从而使得整个算法变慢。 图2 - 4 二维空间自由型物体的包围盒过大的情形 另外，从2 。2 节的算法流程可以看出，如果采用递归算法求解曲面间距离，算法 本质上是一个深度优先的搜索算法。虽然分裂算法对搜索树进行了裁剪，但是在选择 扩展节点时分裂算法完全是盲目的，这样就很有可能首先扩展不大可能存在近点对的 子曲面片。另外，如何选择最短距离的上界值u p p e r 也是一个需要改进的地方。如果 得到了比较大的u p p e r 值，则第一层的分裂节点数会比较多，这就直接造成了搜索树 的过大，影响了搜索速度。 2 4 2 包围盒改进的基本思路 从上面的分析可以看出，包围盒对曲面包围的越紧，则包围盒之间的距离与曲面 之间实际距离也越近，这样就可以大量裁剪搜索树，从而减少搜索节点的数目，减少 搜索所需的时间。理想的包围盒是越贴近n u r b s 曲面越妤，但是由于包围盒的性质， 想要作出比较贴近曲面的包围盒是几乎不可能的。因此需要采用别的包围体技术。注 意到，当控制顶点的权因子w 大于0 时，n u r b s 曲面有很好的凸包性，即曲面必然位 1 2 南京航空航天大学硕士论文 于它的控制顶点形成的凸包中。如果用控制顶点形成的凸包代替包围盒，然后用计算 凸多面体之间最短的距离的算法求解两个凸包的距离，就可以替代包围盒算法以及包 围盒之间距离算法。图2 - 5 给出了图2 - 4 情形的包围体间的最短距离。 图2 - 5 包围体之间的距离 比较图2 4 与图2 - 5 可以看出，包围多面体比原先采用的包围盒的距离要大得多 这样就可以减少很多不必要得对比，自然可节省算法的大量时间。 2 4 3 搜索算法改进的思路 如果我们在扩展搜索节点时首先扩展可能存在近点对的曲面片对，则算法速度可 以得到进一步提高。本文将按照一致代价搜索法的思想，首先选择代价最小的节点进 行扩展。 对于上界值u p p e r ，本文则是分别在两个曲面上取一些点，然后通过点点对比得 出u p p e r 值。 2 。5 包围体的改进 2 5 2 空间点集的凸包算法 目前，成熟的空间点集的凸包算法有很多，比如卷包算法，分治算法等等。本文 采用了增量算法。首先介绍几个基本概念 定义2 2 设s 是空间中的有限非空点集，则称包含s 的最小闭凸集为s 的凸壳，记 为c h ( s ) ，该凸壳的边界记为b c h ( s ) 。 定义2 3 设p 为一个多面体，如果该多面体的表面都平面凸多边形围成，而且该多 面体每一对相交的面由体内测量的二面角均小于或等于，r ，则称该多面体是凸多面 体。 n u r b s 曲面间最小距离算法研究及其计算机实现 由于点集s 的凸壳c h ( s ) 是包含s 的所有闭凸集的交，因此空间点集s 的边界 b c h ( s ) 是一个凸多面体。 多面体实际上指的是它的表面和由表面所围成的空间，但在本文，也将多面体理 解为它的表面，并且，如果不特别指明，对凸壳和凸壳的边界这两个术语不加区别。 另外，因为三角形计算简便，在本文中使用的凸多面体的表面都为三角形。 定义2 4 设有空间三角形a b c ，三个顶点口，b ，c 按逆时针排列。则由右手定则确定的 正向( 与外方向法线方向一致) 称为在空间三角形a b c 之上，相反的方向称之为在空 间三角形a b c 之下。 设空间三角形a b c 的三个顶点口，b ，c ( 按逆时针排列) 的坐标为( 一，y 。，：，) ， ( x ：，y 2 , ：2 ) ，( 屯，y 3 ，白) ，三角形外的点p 坐标为o ，y ，z ) ，则由四阶行列式： lx y ： l x ly l毛 p 2y 22 2 f 墨y 3毛 ( 2 7 ) 的值为正，0 ，负可以确定p 是在空间三角形d 幻所在的平面万之上，面上还是之下。 如果三角形顶点排列顺序改变，则三角形之上之下也要随之改变。如图2 6 ： p p 在三角形之上 p p 在三角形之下 图2 - 6 空间三角形的方向 增量算法的主要概念是首先构造一个空间4 面体作为初始凸多面体，然后将剩下 的顶点依次添加进去。如果新添加的顶点在凸多面体内部，则该顶点不用添加到凸多 面之内。如果在凸多面体之外，则需要经过计算，生成新的凸多面体。然后重复该过 程，直到遍历了所有的顶点，形成一个凸多面体。 南京航空航天大学硕士论文 首先，要生成初始凸多面体c 乩( s ) ，即一个空间四面体。算法的主要思想就是 要找到不共面的四个顶点，然后产生四面体的面。需要注意的是，如果没有找到不共 面的四个顶点，则说明该点集处在一个平面上。另外，对于初始凸多面体的顶点的选 择，可以首先考虑在x ，y ，z 轴上取值最大最小值的点，这样可以使得较多的顶点在 c h o ( s ) 中，从而进一步提高算法的速度。 在找至- i j c h o ( s ) 的四个顶点以后，需要产生初始凸多面体c l i o ( s ) 的面，即产生四 个空间三角形：要使得每个三角形的三个顶点按逆时针排列，而且由右手定则确定的 正向( 与外方向法线方向一致) 朝向初始凸多面体c h 。( s ) 的外面。然后，需要将剩 下的顶点加到凸多面体中。这个过程比生成c 日。( s ) 的过程要复杂的多。 首先我们来看看往凸多面体c h ( s ) 中添加一个顶点的算法。算法的大致思路是： 假设已经生成了凸多面体c h 。( s ) ，对于要加入的顶点p ，首先要判断该点是否已 经在c h 。( s ) 之内，如果已经在c h 。( $ 之内，则不需要添加该点，算法可以直接 返回；如果在c h 。( s ) 之外，则需要找出那些点所在其上面的三角形集合品。和点p ， 在其下面的三角形集合品：。然后找出s 。与爵：相接的环h ，如图2 - 7 ： h 图2 7 s 。与s r 2 相接的环以及b 的位置 接着删去品中的所有元素。最后将h 中的顶点与p ，按一定顺序连接，注意要保证生 成的三角形的外方向的法线方向朝向凸多面体外部，最后再删去集合中孤立的顶点。 往c h 。( s ) 加入顶点p ，的算法的详细流程如下： n u r b s 曲面间最小距离算法研究及其计算机实现 程序四： 输入为新加入的顶点见。 1 ) 遍c h 。( s ) 中的每个面，根据( 3 1 ) 判断n 是在其上还是下，如果在其上，则 将其序号添加到链表v i s i b l e 中，否则添加到链表i n v i s 中。 2 ) 如果i n v i s 的个数为0 ，则表明c h 。( s ) 所有的三角形对于p ，都在下面，即点p ， 在c h 。( s ) 内部，程序返回。 3 ) 寻找v i s i b l e 的每个元素所对应的三角形正与i n v i s 中的元素对应的三角形集合 中相邻的三角形z ( 可能不止一个) ，然后将瓦与z 的公共边添加到h 中。 4 ) 删去v i s i b l e 所有的元素对应的三角形。 5 ) 将h 中的元素的顶点与p ，按定顺序相连。 6 ) 删去孤立的顶点 这样我们就得到了将n 添加到c h 。( s ) 后生成的多边形明，( s ) 。该算法必须注 意一个问题，即如果p ，与c h 。( s ) 的三角形有共面，即( 2 7 ) 的值为0 的情况。 如果出现这种情况，只需认为p ，在此三角形的下面即可。这种情况下会出现生成 的凸多面体中有同面的三角形的情况，但是这不影响求凸多面体算法的进行，也 不会影响求两个凸多面体之间距离的算法。 有了往c h 。( s ) 添加一个顶点和生成初始凸多面体的算法，只需先生成初始凸多 面体，然后将s 中所有的点遍历一遍，对每个顶点调用程序三，就得到了s 的凸壳的 边界：凸多面体c h ，( s ) 。 2 5 3 凸多面体之间距离算法 凸多面体之间的距离一直是碰撞检测领域中重要的研究课题。目前，比较成熟快 速的算法有l c 算法以及g j k 算法。本文采用了g j k 算法求取凸多面体之间的距离。 实验表明，该算法快速稳定。 首先介绍基本概念： 定义2 5 设有空间点集s = p ，p f ) ，p ，p ，仿射独立，定义： t 6 南京航空航天大学硕士论文 a f f ( s ) = p ，：p ，s ， + + 丑= 1 l l t ij 定义2 6 设有空间点集s = p ，p ，) ，p ，p ，仿射独立，定义： 。( s ) ：圭丑p ，：见。s ， + + ：1 ， 0 1 l 冲lj c o ( s ) 即为以s 为顶点的凸多面体之内的点。 定义2 7 设有凸多面体尸，q ，定义p ，q 的m i n k o w s k i 差为m = 缸一y ：x p ，y q ) 可以看出求得尸，9 的m i n k o w s k i 差的计算复杂度为o ( n m ) n ，m 分别为p ，q 的顶 点数。但是在g j k 算法里，并不需要求得完整的m i n k o w s k i 差。需要指出的是，两个 凸多面体的m i n k o w s k i 差还是凸多面体。如果两个凸面体相交，那么原点必然在肘中。 定义了m i n k o w s k i 差，则尸，9 最近的点之间的距离可以理解为从原点到肘的最短距 离。因此，求解p ，q 之间的最短距离可以转化为求解从原点到凸多面体m 的距离。 定义2 ，8 定义凸多面体p 的支撑函数为： 品( v ) = m a x p v ：p p ) 其中v 是一个方向，函数的返回值是j p 的一个顶点。通过支撑函数，可以找到点 集p 里v 方向上的值最大的顶点。 对于p ，9 的m i n k o w s k i 差m ，支撑函数是这样的： & ( v ) = s ，( v ) 一s e ( - v ) ( 2 8 ) 可以看出，p ，q 的m i n k o w s k i 差m 的支撑函数不需要遍历整个m i n k o w s k i 差。 而只需要遍历p ，q 的所有顶点即可。 定义2 9 一个简单体( s i m p l e x ) 为3 维空间中仿射独立的点集为顶点的凸多面体。 一个3 维空间中的简单体可以有l ，2 ，3 ，4 个顶点。分别为一个顶点，线段，三角 形和四面体。 定义了p ，q 的m i n k o w s k i 差肘之后，求取尸，g 之间的最短距离问题就变成了求 取凸多面体m 到原点的距离问题。 对于求取一个凸多面体到原点的距离，g j k 算法会产生一个简单体序列矽，它们 ! ! ! 堕堂亘塑墨! ：堕壹簦鎏婴塞墨茎生曼塑窭婴 距离原点的距离是递减的。对于初始的，只需选择m 中的任意一点即可。假设已 经得到了一个简单体彬，要求得下一个简单体嘭首先要调用支撑函数返回一个 顶点w ，然后将w 添加到矿中。接着根据距离子算法计算出彬到原点的距离以及最 近距离点v 。然后删去形中与v 无关的点，即得到了彬。 这样，就会产生一个距离更加接近原点的简单体彬。然后重复这一过程直到支 撑函数不再返回新的顶点为止。由于是三维空间，所以序列w 中的每个元素都最多 只有3 个顶点。 值得注意的是，g i k 算法并不是只对凸多面体有效，而是可以求解任意凸体之间 的距离，不管凸体的边界是什么样子。比如 图2 - 8 二维空间凸体到原点距离 下面详细介绍一下距离子算法，即从求解一个简单体到原点的距离以及最短距离 南京航空航天大学硕士论文 点。 该算法的主要目的就是要确定和最近距离点相关的简单体上的点以及相关的参 数。为了实现这个目的，必须要遍历所有简单体上的顶点的子集所构成的简单体才能 得到最近距离点。 假设简单体有v 个顶点，那么就会一共有： a = v ! 烈( v 一刚 个子集、因为v 不会大于4 ，所以，在最多的情况，也只会有1 6 个子集。 一个空间简单体中的点的表示如下： v = z ，1 a j p ，：p ，e s ， + + 丑= ， 0 c z 。， v = ，：，s ， + + 丑= 1 ， ( 2 9 l ，= jj 这样，下一步的工作就是要确定a ，。 。求解 ，丑可以通过解以下线性方程 得到： 爿五= b 其中： a = 1 ( z 2 一石1 ) x i ( z 2 一x i ) 工 ( 工2 一x 1 ) z l ( z 2 一x 1 ) z ，b = 这里，本文使用了克莱姆法则的递归方式求解此方程： = a ，( x ) i a ( x )( 2 1 0 ) 其中，( x ) ：，( x ) ，而，( x ) 的定义为： e “ a ，( 只) ) = l( 2 1 1 ) a j ( x y p 脚= a 。( x ) ( p ，p 女一p ，p ，) ( 2 1 2 ) i e l x 其中，g i t ，k 是以中任意但是固定的一点，这里不妨取七= m i n ( i ) 。求解出的 ( z ) 还必须满足以下条件： 1 ) 。( z ) 0 对于i ，： ( 2 1 3 ) 2 ) a j ( z y p ， ) 0 ，对于_ ，隹，。( 2 1 4 ) n u r b s 曲面间最小距离算法研究及其计算机实现 这样，根据以上就可以求解出 ，- 。如果有两个或者两个以上的子集满足以 上条件，则要选择元素个数最少的子集为结果。 以下是距离子算法程序的流程： 程序匾： 输入为一个3 维空间点集 得到点集的所有子集 对每个子集以 f 使用( 2 1 1 ) 和( 2 1 2 ) 之对应的 ，饵) ；f ei x 如果满足( 2 - 1 3 ) 和( 2 1 4 ) ，则根据( 2 1 0 ) 求出 ， ，记录下该子集，。到，。中 对，。进行遍历，得到元素个数最少的，： 返回与以对应 ，丑。 该算法中的中的元素最大情况下只会有4 个，所以子集数只有1 6 个。因此该 算法执行速度相当快。 下面是g j k 算法的主程序流程： 程序玄： 初始矽为空集 取m 中的任意一点v w h i l e ( v 0 ) d o 以一v 为输入参数，使用公式( 2 8 ) ，即计算& ( 一v ) 返回m 中的一点。 i f ( 达到终止条件) b r e a k ： 将w 添加到形中： 以为参数调用程序四，得到 ， 以及对应的的子集职。： 矽：= 彬“： 将w 和 ，一带入( 2 9 ) 计算v 南京航空航天大学硕士论文 ) 返回v 在得到由两个子曲面片的控制顶点构成的凸多面体之间的最短距离之后，就可以 求得两张子曲面片的包围凸多面体之间的距离。但是，我们也同时可以看出，使用凸 多面体作为包围体以后的算法时间消耗比较大。为了减少增量算法及g j k 算法的次 数，本文采用了这样两种方法： 1 ) 先比较两个曲面片的控制顶点的包围盒，如果包围盒之间的距离小于给定的上界 u p p e r ，则再产生凸多面体，求取凸多面体之间的距离，然后用这个值和u p p e r 对比，如果还小于u p p e r ，则对曲面片对进行进一步分裂对比。 2 ) 如果分裂层次较大而且曲面片的控制顶点又比较多，则包围多面体与包围盒之间 的差距不大，依然采用包围盒算法。 2 6 改进搜索方法 从2 2 节的算法流程可以看出，如果采用递归算法求解曲面间距离，算法本质上 是一个深度优先的搜索算法。如果我们按照一致代价搜索法的思想，首先选择代价最 小的节点进行扩展，则算法速度可以得到进一步提高。 如何知道哪个节点是“代价最小”? 根据自由曲面距离问题的特点，本文选择了 最近角点对之间距离作为该节点的“代价”。这样，在进行子曲面片配对之后，要按 照最近角点对之间距离的大小顺序对曲面片进行进一步分裂。 另外，对于两曲面之间最短距离的上界值u p p e r ，如果能够确定一个较小的上界 值，则在第一次分裂时可以排除掉很多的子曲面片对。因此，本文采用的方法：在每 个曲面上取1 0 0 个顶点，然后进行点点对比，取最小的距离为上界值u p p e r 。根据实 验，这样取上界值所需的时间在0 0 1 秒以下，基本可以忽略不计。 下面是改进后递归算法的流程： 程序一： 1 ) 输入参数为n u r b s 曲面l ，n u r b s 曲面2 ，以及两曲面之间最短距离的上界：u p p e r ， 在本程序中，u p p e r 是作为一个全局变量存在的。 2 ) 如果曲面的分裂层次达到h l e v e l ，则通过点点对比得到两曲面：n u r b s 曲面1 ， n u r b s 曲面2 之间的控制顶点的最短距离，如果此距离小于u p p e r ，则以此距离替 代u p p e r ，并记录下对应的两个点：p t l 和p t 2 ，返回。 3 ) 调用程序一分裂两n u r b s 曲面，得到两子曲面数组：n u r b s i a r r n u r b s 2 a r r 。 4 ) 得到n u r b s l a r r 和n u r b s 2 a r r 中所有曲面片的包围盒。 5 ) 将n u r b s l a r r 和n u r b s 2 a r r 中的予曲面片两两配对，将其记录在数组s k a r r 中。 对于每个子曲面对求取最近角点距离，将其记录在数组m p t d is 中。 n u r b s 曲面间最小距离算法研究及其计算机实现 6 ) 得到最近角点距离最小的子曲面片对，并记录下与之对应的予曲面片对：n u r b s l ， n u r n h s 2 。 7 ) 如果子曲面对n u r b s l 和n u r b s 2 的最近角点对的距离小于u p p e r ，则以此距离替 代u p p e r 。 8 ) 对数组s k a r r 按照最近角点距离进行排序。 9 ) 遍历子曲面片数组s k a r r ，如果子曲面片对之间包围盒的距离小于u p p e r ，则再进 一步比较包围凸多面体之间距离，如果该距离还小于u p p e r ，则以子曲面n u r b s l 和n u r b s 2 为参数，递归调用本程序；否则返回。 经过实验，对搜索算法改进后是可以提高算法的整体速度的。但是其对速度的贡 献远不及改进包围盒对算法速度的贡献。 2 7 算法实验 采用改进后的分裂算法，对2 3 4 节的算例一进行计算，为便于比较将改进前后 的计算结果立表2 2 。 表2 2 分裂算法和改进的分裂算法计算结果 分裂算法改进的分裂算法 ，疗 k s ) 疗 ，( s ) 32 8 10 0 2 02 50 0 8 0 41 0 6 90 1 0 04 3o 1 8 0 53 6 5 50 3 2 17 30 2 4 1 61 3 1 6 71 1 6 11 7 8o 4 l o 74 8 2 5 54 2 7 61 4 4 6o 4 4 l 8 1 7 0 3 9 81 5 9 6 31 3 9 2 3o i 8 4 1 可以看出，对于算例一，对包围盒算法进行改进以后，算法的效率有了很大的提 高。主要是搜索节点数大量减少，根据上面的结果，每增加一层分裂层数搜索节点数 只增加了大约2 倍。这主要是因为包围多面体相对于包围盒更加贴近曲面，从而使褥 计算出来的曲面之间的最短距离的下界更加贴近于实际的最短距离，最终使得搜索节 点的数目有了很大的减少，从而提高了算法的速度。而最后分裂层次达到7 时搜索节 点的突然增加，则是因为不继续采用包围多面体雨改用包围盒得到的结果。 还应该指出，改进的分裂算法里每个搜索节点中的计算量较大。设胆为空间点集 数目，凸多面体生成的增量算法时间复杂度为o ( n 2 ) 。计算凸多面体之间距离的g j k 南京航空航天大学硕士论文 算法的速度较快，与”基本是线性关系，因此，一个搜索节点的时间复杂度为o ( n 2 ) 。 而分裂算法每个搜索节点的计算量较少。如果分裂层次较低，则算法的搜索节点数也 较少。本章的改进算法虽然搜索节点较少，但是时间耗费依然比分裂算法大。但是如 果搜索层数l 5 ，改进的分裂算法的优势就体现出来。 因为分裂层次越大，所得的结果越精确，而本算法又能保证相对较高的速度。 所以如果需要得到较精确的结果，需采用改进后的分裂算法。 n u r b s 曲面间晟小距离算法研究及其计算机实现 第三章n u r b s 曲面间距离求解的遗传算法 遗传算法是一种仿生算法，即模拟生命演化的算法。它是从一个初始种群出发， 不断重复执行选择、杂交和变异的过程，使种群进化越来越接近某一目标。该算法具 有很强的通用性。本章应用遗传算法求取任意n u r b s 曲面之间最小距离。首先介绍 遗传算法的基本原理，给出遗传算法流程，计算任意n u r b s 曲面之间最小距离，分 析计算结果，给出增加特殊个体和突变概率的方法，避免群体缺乏必要的多样性，获 得更好的算法效果。 3 1 遗传算法基本原理 遗传算法的特点是它的算法中不包含待解决问题所特有的性质，不需要知道求解 问题本身内部的性质。它是从改变基因的配置来实现问题的整体优化的，因而属于自 上而下的优化方法。下面是基因算法的主要流程： 1 ) 构造适应度函数。 2 ) 随机的产生初试种群，将种群中的每个个体转化为二进制编码。 3 ) 通过选择，杂交，变异生成后代群体。 4 ) 判断群体进化是否收敛，如果没有收敛，跳到第三步。 5 ) 输出最优解。 适应度是遗传算法中描述个体性能的主要指标。一般个体适应度值越大，个体性 能越好；反之，个体适应度值越小，个体性能就越差。在遗传算法中，适应度的 值必须是大于0 的数。 由于遗传算法是依据适应度的值对个体进行优胜劣汰的，因此，将无约束的优化 问题的目标函数与个体的适应度建立映射关系，即可在群体进化过程中实现对优化问 题目标函数的寻优。 初始种群的个体一般是随机给出的，然后转换成二进制串。在本文中，二进制串 是用字符串表示的。 选择即从上代群体中选择一定数量的个体，并将为参与下代群体繁殖的父代个 体。选择个体的原则是使适应度大的个体被选择的机会较大，本文中采用竞赛法选择 个体。 杂交是仿照生物学中杂交的原理，将两个个体的染色体的部分字符交换来产生下 一代个体。 突变是根据一定的概率，将染色体的部分字符进行补运算，即将l 变成0 ，0 变 成1 。 判断群体进化是否收敛是根据迭代次数或者对个体最大适应值的评估做出判断 的。本文中采取后一种t 即如果个体最大适应值在一定迭代次数内不发生变化的话， 南京航空航天人学硕士论文 算法结束。 3 2n u r b s 曲面间最小距离遗传算法 3 2 1 遗传算法类说明 本文采用了c + + 语言实现了遗传算法求取两张n u r b s 曲面之间的最短距离，构造 了遗传算法类：g a 。这里首先对于g a 的类变量做一简单说明： c n u r b s * m _ p n u r b s l ：n u r b s 曲面1 c n u r b s 半m p n u r b s 2 ：n u r b s 曲面2 i n tm _ l e n g t h ：染色体长度 f l o a tmc m a x ；一个足够大的整数，保证适应度算法的结果肯定为正 f l o a tmm a t i n g p r o b a b i l i t y ：杂交比例，本文取0 8 f l o a tm _ m u t a t i o n p r o b a b i l i t y ：突变比例，本文取0 0 1 i n t m _ m a t i n g c o u n t ：杂交次数 i n tm _ m u t a t i o n c o u n t ：图标次数 i n tm _ g e n e r a t i o n c o u n t ：迭代次数 c s t r i n g a r r a ymp o p u l a t i o n ：种群，是一个字符串数组 c s t r i n g a r r a