付 彤，曲慧雁

（1.吉林工程技术师范学院，吉林 长春 130052；

2.吉林农业大学信息技术学院，吉林 长春 130037）

最小距离分裂算法在NURBS曲面间的改进

付 彤1，曲慧雁2

（1.吉林工程技术师范学院，吉林 长春 130052；

2.吉林农业大学信息技术学院，吉林 长春 130037）

基于分裂算法中最小距离在NURBS曲面间的应用研究，提出了以包围体来代替包围盒（AABB）的思想，在求凸包间距离时选取了GJK算法，并对分裂算法进行了改进，从而在算法精度以及算法速度方面实现了极大地提高.

凸包；分裂；GIK算法；NURBS曲面

0 引言

随着计算机技术的发展，特别是虚拟现实技术的不断发展，碰撞检测已经成为计算机动画、计算几何等研究领域的重要组成部分.因用户间交互以及物体运动，使得虚拟环境下，物体之间的碰撞时常发生，考虑到此环境下对真实性保护的要求，对两物体间碰撞发生的可能性必须给出及时的判断，因而需要计算两物体之间的距离.

进行精确的碰撞检测，对于提高虚拟环境的沉浸感有着至关重要的作用，而虚拟环境自身的复杂性和实时性对碰撞检测提出了更高的要求.碰撞检测主要依据虚拟空间中的任意两个不可刺穿的物体不能存在于相同位置的空间区域这一命题.目前碰撞检测算法有三类：包围盒层次法、空间剖分法、距离向量法［1－4］.空间多面体间距离成为求解问题的焦点，目前其对于凸多面体的空间距离研究较多.如：文献［5-6］对于两凸多面体间提出了距离求解的快速算法，分别是GJK算法和LC算法.在碰撞检测中，作者以参数曲面为基础进行了研究，做出了一些成就.文献［7］主要研究表面为自由曲面物体的应用问题.国际标准组织（ISO）于1991年对于工业用品制定了STEP标准，其中数学中唯一用以定义的自由型曲线和曲面的方法就是NURBS，而NURBS方法恰恰可以定义绝大多数的自由曲线和曲面.目前能见到的有关曲面间距离的研究关于自由型的还比较少，而关于有理Bezier，其有向曲面间距离算法的研究在文献［8］中已经给出，并且该研究成果是前所未有的.

本文采用增量算法对凸包围多面体与曲面控制点进行求解，将GJK算法应用与凸多面体的距离求解综合起来，用包围体代替原来的包围盒算法，改进了原有的分裂算法.

1 理论背景

1.1 NURBS曲面简介

NURBS曲面的表达式

其中：Vi，j为控制顶点，Wi，j为权因子，Bi，k（u）和Bj，l（v）分别为沿u向具有k次和沿v向具有l次的B样条的基函数.

递推公式如下：

其中：k为幂的次数，ui（i＝0，1，…，m）为节点.

此外，文中还约定：端节点重复度对于u向矢量与v向矢量分别为k＋1与1＋1，从而在几何性质上NURBS曲面由于端节点和Bezier曲面同次有理，有相同的角点.

1.2 分裂曲面原理介绍

节点插入算法在分裂NURBS曲面中是核心环节.先给出节点插入在B样条中的算法：

由算法容易得出，在新节点插入后，其矢量就会增加一个新区间；并且控制点每增加一个，对新控制顶点必须重新计算全因子.对同一节点而言，若节点有k次重复（B样条中基函数幂次为k），在相应节点处对NURBS曲线进行分段，具体算法见文献［9-10］.该分割算法基于NURBS曲面进行了拓展.NURBS曲面中，要求分别插入u和v方向节点，对控制顶点进行计算，要把曲面分成4份，并对生成的新拆分的子曲面片重新分配控制顶点.

1.3 实现分裂算法的具体过程

需要对插入uknot和vkont的位置进行寻找，并对其重复度分别进行计算.节点插入后，赋值给分裂后的曲面控制顶点，并赋值给相应的权因子.给出分裂算法的流程如下：

NURBS曲面作为首次输入，并输入ukont和vkontu这两个u和v向所插入的节点

（1）取得ui和vi，即uknot和vkont处插入所对应的位置.

（2）取得ukont和vkont节点分别的重复度ur，vr.

（3）对节点进行插入，k-节点重复度即作为NURBS曲面次数的插入个数.由此得m＋k－ur与m＋k－vr这两个NURBS曲面1在插入节点沿控制顶点u向以及v向的个数.

（4）对于nurbs1这个子曲面，曲面1NURBS中控制顶点分别为［l，…，ui－ur］和［l，…，vi－vr］，即沿u和v向.

（5）对于nurbs2这个子曲面，其控制顶点分别为［ui－ur，…，m＋k－ur］和［l，…，vi－vr］，也为曲面1NURBS沿u和v向.

（6）对于nurbs3这个子曲面，其控制顶点为［l，…，ui－ur］和［vi－vr，…，n＋k＋vr］，也为曲面1 NURBS中沿u和v两个方向.

（7）对于nurbs4这个子曲面，得到控制顶点［ui－ur，…，m＋k－ur］和［vi－vr，…，n＋k＋vr］，也为曲面1NURBS中u和v方向.

（8）分别对各子曲面计算所生成的节点值.

以上的算法表明，对子曲面分裂后，控制顶点的数目不大于（等于只能取在控制顶点的数目恰好比NURBS曲面的次数多1这个条件下）原来曲面中控制顶点的个数.在插入节点计算中，不但要用到插入的节点，也要根据公式（1.2）—（1.5）来计算.

1.4 分裂算法应用于曲面NURBS的流程

先针对给出曲面间的最短距离，给出其上界的计算方法.在本文中的NURBS曲面的u向矢量和v向矢量中端节点的重复度分别取为k＋1和l＋1，故对NURBS曲面而言，也能有角点的相关几何性质，如果有角点，就必定在该曲面上.由此，在两曲面间，其角点间的距离最小值就必不小于曲面间距离的最小值.故把角点之间距离的最小值暂时当做是曲面之间距离最小值的上界，记为upper.

下面就将两曲面进行分裂，得到的新的子曲面片，我们对其两两配对.针对任意两个子曲面片位于每个子曲面对，以包围盒来计算控制顶点间的距离.若包围体间，其距离比upper大，那么一定找不到一个在曲面上的最短距离点存在于此子曲面对间，也就不需要再对这个子曲面对进行下一步的对比.否则，需要对已得到的子曲面对计算位于两子曲面中，角点之间的最短距离，并用它替代之前的upper，继续进行递归调用，达到分裂的层次hlevel为止.

由于分裂曲面后，都是在很靠近NURBS曲面得到的控制顶点，故对余下的节点逐一比对，找出可能有最短距离的那些子曲面上的控制点，并认为两NURBS曲面的最短距离即为控制顶点之间此前求出的最短距离，然后选取两个距离最近的控制顶点，在两NURBS曲面中，以其为近点对，对结果进行输出.

以上分裂算法中容易看出，搜索节点数过大主要是由于包围盒过大，并且求解曲面间距离时采取的递归算法，其本质就是搜索算法中的深度优先.尽管分裂算法裁剪了搜索树，但选择扩展节点却非常盲目，因而对于子曲面片，即使不大可能存在近点对，也极易引起扩展.

2 改进算法

2.1 改进算法在包围盒中的主要思想

计算曲面包围盒相对来说较难.但如果控制顶点中，其权因子w比0大，凸包性上就显现了NURBS曲面的优势，此时由控制顶点所构造的凸包中必然包含了该曲面.因此就选取这些控制顶点，用形成的包围体替代NURBS曲面上的点形成的包围盒，对于两个凸包的距离，凸多面体之间可以用计算最短距离的算法来求取，以此替代包围盒之间距离算法和包围盒算法.

定义2.1设S是空间中一个有限非空的点集，称闭凸集中包含了S最小的那个集合为S的凸壳，记作CH（S），并记BCH（S）为此凸壳的边界.

定义2.2设多面体为P，若表面都是平面图多边形围成的，每一对相交的面，其二面角在此多面体中都不大于π，那么称之为凸多面体.

因CH（S）是点集S的交，且包含了S的全体闭凸集，故BCH（S）作为空间点集S的边界，也为凸多面体.

对于成熟空间点集而言有很多凸包算法，文中在构成凸多面体时引入了增量算法.构造一个空间四面体，将其认为是初始的凸多面体，并逐次添加剩余顶点.若添加的顶点已经位于凸多面体之内，那么这个顶点就不用再添加.若是位于凸多面体的外部，就在计算后生成一个新凸多面体.以下对此过程重复，所有顶点遍历结束就生成了一个新的凸多面体.

2.2 位于凸多面体间的距离算法

在计算凸多面体之间的距离时，我们选取GJK算法.给出基本概念如下：

co（S）是位于凸多面体内部且以S为顶点的点.

定义2.4设凸多面体P与Q的 Minkowski差M＝｛x－y：x∈P，y∈Q｝.

容易得出，计算复杂度是P与Q的Minkowski差O（nm），其中P，Q的顶点数目分别为n，m.事实上，GJK算法中，完整的 Minkowski差不是必要的.特别需说明的是，对于两个凸多面体，它们的Minkowski差仍然为凸多面体.若两个凸多面体相交，则M中必然能找到原点.给出了Minkowski差的定义，那么从原点到M的最短距离便是P与Q之间最近的点的距离.故可通过求由原点至凸多面体M之间的距离作为P与Q间最短距离.

定义2.5对于凸多面体P，其支撑函数为

式中v为方向.该函数通过返回值形成P的一顶点.使用支撑函数，对点集P，便可找到v方向上的最大值的顶点.

对于P与Q的Minkowski差M，支撑函数为

（2.1）式表明，对于P和Q的Minkowski差M，其支撑函数差只要遍历P和Q的所有顶点而不用遍历整个Minkowski的差.

定义2.6在3维空间中仿射独立的点集，以其为顶点的凸多面体即为一个简单体（Simplex）.

借助P和Q的Minkowski差M的定义，计算凸多面体M到原点距离问题就是计算P与Q间的距离的最小值问题.

在对原点距离一个凸多面体的计算中，GJK算法给出了一简单体序列W，它们与原点之间的距离依次递减.而最初的W0，可以任意选取M中的一点充当.现在对于已存在的简单体Wi，来计算Wi＋1，即下一个简单体.先调用出支撑函数，返回顶点w，并添加到函数中，进而通过距离子算法来求得最近距离点v和W至原点的距离.与v无关的点删除，就是下一个简单体Wi＋1.

用该方法，一个与原点距离更短的简单体由此产生，对这一过程进行重复，直至在支撑函数不再有新的定点返回.因为针对三维空间，故序列W中对于每个元素至多只能取3个顶点.

2.3 算法改进后的流程

（1）首先对曲面1NURBS和曲面2NURBS这两个参数曲面进行输入，并输入上界upper，即两曲面间最短距离的边界，在本程序中，这里upper为全局变量.

（2）若曲面所分裂的层数已经到达hlevel，则进行点点比对以得到NURBS曲面1和NURBS曲面2，并以此控制顶点之间最短距离，若该距离比upper小，则记取pt1，pt2这两个对应点，返回.

（3）对分裂算法进行调用，对两NURBS曲面作分裂，得到nurbs1arr和nurbs2arr这两个子曲面数组.（4）求取nurbs1arr与nurbs2arr的全部曲面片包围盒.

（5）两两配对nurbs1arr与nurbs2arr的子曲面片，并在数组skarr内进行记录.求取每个子曲面对对其最近角点的距离，并在数组mptdis中记录.

（6）取得位于最近角点距离最小子曲面片对，同时记录nurbs1和nurbs2这两个对应的子曲面片对.

（7）若nurbs1，nurbs2子曲面对的最近角点对距离比upper小，那么upper用该距离代替.

（8）按照最近角点距离对数组skarr进行排序.

（9）对曲面片数组skarr进行遍历，若子曲面片对之间包围盒的距离小于upper，则以子曲面nurbs1和nurbs2为参数，对本程序递归调用；否则返回.

3 实验结果

π1，π2为两个凸曲面，选取改进后的分裂算法（为方便起见，当分裂层次为7时，不再选用新算法），与原来的算法比较，计算两曲面间的最小距离，其结果如表1.

表1 改进前后分裂算法计算的最小距离对比

表中l代表分裂的层数，n是搜索节点的数目，t是计算所用的时间.明显看出，搜索节点数大量减少，改进包围盒算法后，大大提高了算法效率.根据表1的结果，分裂层数增加一层，就增加大约2倍搜索节点数.相对于包围盒，由于包围多面体最短距离更贴近曲面真实值，很大程度上减少了搜索节点的数目，算法速度得到了提高.当分裂层次为7时，由于不再选取包围体而是选取包围盒使搜索节点突然增加.

［1］ 周云波，闫清东，李宏才.虚拟环境中碰撞检测算法分析［J］.系统仿真学报，2006，18（1）：103-107.

［2］ NOBORIO H，FUKUDA S，ARIMOTO S.Fast interference check method using octree［J］.Advanced Robotics，1989，3（3）：193-212.

［3］ LIN M C，MANOCHA D，CANNY J F.Fast collision detection between geometric models technical report TR93-004［R］.North Carolina：Chapel Hill，1993.

［4］ GINO VAN DEN BER GEN.A fast and robust GJK implementation for collison detection of convex objects［EB／OR］.［1999-12-04］.http：／／www.win.tue.nl／cs／tt／gino／solid／index.html.

［5］ GIBERT E G，JOHNSON D W，KEERTHI S S.A fast procedure for computing the distance between complex objects in threedimensional space［J］.IEEETrans Robotics＆Automation，1988，4（2）：79-85.

［6］ MING C LIN，JOHN F CANNY.A fast algorithm for incremental distance caculation［C］／／Proceeding of the 1991IEEE International Conference on Robotics and Automation，California：Sacramento，1991：276-283.

［7］ TURNBULL C，CAMERON S.Computing distances between NURBS-defined convex objects［C］／／In Proceedings of IEEE International Conference on Robotics and Automation，Piscataway：1998.

［8］ FEDERICO THOMAS，CONLIN TURNBULL，STEPHEN.Computing signed distance between free-form objects［C］／／Procceding of the 2000IEEE International Conference On Robotics ＆ Automation，San Francisco，CA：2000：3713-3718.

［9］ 刘浩.NURBS曲面间的最短距离［D］.南京：南京航空航天大学，2002.

［10］ 朱心雄.自由曲线曲面造型技术［M］.北京：科学出版社，2000：65-72.

Improved algorithm on minimum distance splitting between the NURBS surfaces

FU Tong1，QU Hui-yan2

（1.Jilin Teachers Institute of Engineering and Technology，Changchun 130052，China；
2.College of Information Technology，Jilin Agricultural University，Changchun 130037，China）

Collision detection is the key technology of VR.And the distance of convex geometric is the important fact of collision detection.The proposed method based upon the technique of splitting the NURBS surfaces consists of the convex hull displaced of the convex box（AABB）and GJK algorithm are employed to improve the spilt algorithm's performance.The implement shows that the improved spilt algorithm is more precisely and quickly.

convex hull；spilt of NURBS surfaces；GJK algorithm；NURBS surfaces

TP 301.6

520·1040

A

1000-1832（2011）04-0049-05

2011-07-25

国家自然科学基金资助项目（61106068）；吉林省科技发展计划项目（201101115）.

付彤（1965—），女，副教授，主要从事计算方法研究.

陶 理）