一种针对非均匀有理B样条曲面的碰撞检测算法

一种针对非均匀有理B样条曲面的碰撞检测算法 摘要：提出了一种针对非均匀有理B样条(NuRBS)曲面的碰撞检测算法，它将节点反插技术引入到NURBS曲面细分中，通过控制点间距离测试进行精确碰撞检测，该算法首先插入几何意义较为清楚的控制顶点，反算出要插入的节点，再采用节点插入技术将曲面细分，然后为逐步细分的曲面控制点建立固定方向凸包(FDH)包围盒，以尽早排除不可能碰撞的情况，在到达一定细分层次后，进行曲面之间的距离测试，若距离小于某一阈值，则认为发生碰撞，通过虚拟环境中蝴蝶与玉米叶的碰撞实验表明，所提算法可以应用于由NURBS曲面表示的物体碰撞检测，在细分层次为5，阈值为0.0006时，可以使本例碰撞检测具有良好的精确性和实时性。 下载论文网关键词：碰撞检测；非均匀有理B样条曲面；曲面细分；固定方向凸包中图分类号：TP391文献标识码：A文章编号：0253-987X(2007)04-0389-04碰撞检测是虚拟现实领域的重要研究课题之一、人们要真实地模拟现实世界中物体的运动，对场景中的物体进行精确、实时碰撞检测是十分重要的在虚拟现实系统中，非均匀有理B样条(NURBS)方法在形状定义方面功能强、潜力大1，1991年国际标准组织(ISO)颁布的工业产品几何定义的STEP标准，就把NURBS作为唯一定义自由型曲线、曲面的数学方法，尽管国内外的许多专家和学者已在碰撞检测方面开展了不少有价值的研究工作，但大都针对凸多面体，而对自由曲面之间的碰撞检测问题缺乏有效的解决方法，针对这一问题，Page等人提出了一种NURBS曲面碰撞检测算法2，并采用曲面细分和OBB(Oriented Bounding Boxes)包围盒技术，从一定程度上解决了NURBS曲面碰撞检测问题，但这种方法存在一些不足，如算法在曲面细分时难以确定分裂位置，碰撞检测的判断不够精确等，为此，本文提出一种新的针对NURBS曲面的碰撞检测算法，它弥补了Page算法的不足，并可在NURBS曲面之间进行精确的实时碰撞检测。1NURBS曲面NURBS曲面方程有多种表示方式，这里给出它的有理分式的表示形式，一张次NURBS曲面3可表示为 式中：di,j(i=O，1，m；j=0，1，n)是控制顶点阵列;()i,j是与顶点di,j联系的权因子；ni,j(i=0，1，m)和i,j，(J=0，l，n)分别为()方向()次和方向()次规范B样条基，它们分别由()向和()向的节点矢量按德布尔递推公式决定。 NURBS曲面的一个重要性质就是由其控制点所形成的凸包将曲面完全包围2，在碰撞检测中可以利用这一性质，即用控制点建立的包围盒来代替曲面本身建立的包围盒，使计算变得简单。2算法实现算法主要包括3个主要过程：曲面细分，建立固定方向凸包(FDH)包围盒以及包围盒之间的相交测试，曲面之间的距离测试。2.1曲面细分在曲面细分的过程中，节点插入算法至关重要，Page算法就是在NURBS曲面的2个参数方向上通过直接插入节点矢量来实现曲面细分的，但是由于节点不具有清楚的几何意义，所以插入的位置有一定的盲目性，在插入节点后也很难预知曲面在何处分裂。本文算法采用节点反插和节点插入相结合的方法达到曲面细分，首先插入几何意义较为清楚的控制顶点，然后反算出要插入的节点，从而实现节点的反插，接着再利用节点插入技术，将曲面细分。为了将曲面较为均匀地一分为四，插入的控制顶点应在相应方向控制顶点序列中央的附近，初始控制顶点为d，取u方向控制顶点的插入位置在第m/2个与第m/2个控制顶点之间，m/2方向取在第n/2与第n/2个控制顶点之间。因此，在n/2方向插入的新控制顶点3于是从而有在反算出节点之后实现曲面细分，需要使用节点插入技术，对于NURBS曲线，在同一节点处，若节点重复度(即该节点重复的次数)为B样条基函数的幂次，则NURBS曲线在相应节点处分段4，类似地，若NURBS曲面的方向u和方向的节点重复次数分别与相应基函数幂次相同，曲面将会一分为四，新控制顶点被分配到拆分后生成的子曲面上，节点每插入一次，需要重新计算控制顶点，以u方向为例，假设节点插入的位置为ui，所插节点在u方向上的重复度为uR，根据文献4的节点插入算法，新的控制顶点曲面细分一次的算法描述如下。输入：NURBS曲面nurb。输出：细分后的4个NURBS曲面存于数组nurb4之中。步骤2：计算反插节点，得到节点重复度uRuR.步骤3重复插入节点，插入次数分别为k-uR、lR（、l分别是u方向与方向B样条基函数的幂次)，最后得到NURBS曲面数组nurb4。在实际应用中，应根据需要选取适当的细分层次L，即曲面细分的次数，使得曲面分裂为4l个子曲面。2.2 FDH包围盒曲面在每一次细分后都需要为其建立包围盒，以尽早排除不可能碰撞的情况，本文采用FDH包围盒。FDH是一种特殊的凸包5，它的所有面的法向量均来自一个固定的方向向量集合，令D=d1,d2,，dk是一个包含k个固定方向向量的集合，且对任意djD，必须存在djD，使得dj=-dj，一般来说，对象E的FDH可以通过计算E凸包中的顶点与固定方向集D中的各个方向的最大点积得到，根据前述的NURBS曲面的凸包性质，进行控制顶点与D中各个方向的点积运算，可以简化对象凸包的计算过程。在建立包围盒时，本文算法首先选定固定方向集D14=士(1,0,0),(0,1,0),(0,0,1),(1,1,1),(1,-1,1),(1,1,-1),(1,-l,-1)， 然后计算NURBS曲面的控制点di,j与固定方向集D中各个方向的最大点积，进而得到NURBS曲面的FDH，为了便于说明，以NURBS曲线和二维FDH为例来说明如何建立包围盒，如图1所示，空心圆点是NURBS曲线的控制点，并取D8=(1,O),(0,1),(1,1)，(-1，1)，将每一控制点坐标分别与每一固定方向坐标做点积运算，取最大值，便可得到控制点沿每一方向的最大延伸，从而得到控制点的FDH包围盒，即该NURBS曲线的FDH包围盒。 在建立了2个NURBS曲面FDH包围盒之后，可进行包围盒相交测试，本文采用投影重叠测试，即如果2个包围盒在k/2个固定轴的任一轴上的投影区间不重叠，就可以判定这2个包围盒不重叠，包围的曲面也必定不相交，如果在所有方向上的投影区间都重叠，可认为2个包围盒相交。2.3 NURBS曲面之间的距离测试在Page算法中，碰撞检测的最终结果由到达一定的细分层次之后包围盒是否相交来决定，若包围盒相交则认为曲面相交，这样，在某些情况下的碰撞检测结果不够精确，因为对曲面建立的包围盒很难像凸多面体包围盒那样有较好的紧密性。包围盒相交而曲线间距较大的情况如图2所示，以二维情况为例，这2个曲线的包围盒相交，但2条曲线之间的距离较大，三维情况也是如此，当2个NURBS曲面的包围盒相交时，很可能2个曲面还相距甚远。为了弥补包围盒在紧密性上的不足，当细分层次为L时，本文算法对包围盒相交情况下的曲面加入了距离测试6，即判断2个曲面控制点之间的最小距离，距离测试算法如图3所示，当测试距离小于某一阈值T时，才认为2个曲面相交，即可检测到碰撞，从而避免了发生曲面之间距离较大的情况，2个曲面之间的距离测试可通过Distance-Test(nurb1，nurb2)函数来实现，其中nurb1nurb2是待测的2个NURBS曲面。3 实验与分析采用VC+、OpenGL在PC机(PIV 3.0GHz，1 GB内存，MSI RADEON X600 PRO显卡)上实现了本文的NURBS曲面碰撞检测算法，算法的测试场景，即一只蝴蝶在一株玉米的叶片之间运动，玉米静止，蝴蝶的运动可以人为控制，使其与玉米叶发生碰撞，玉米叶与蝴蝶都是采用NURBS曲面建模，每一片玉米叶的控制点数目为175，蝴蝶的控制点数目为81。为了取最佳的细分层次L和距离测试中的T，使场景中的碰撞检测有较好的实时性和精确性，可以进行以下实验：将蝴蝶移动到与某一叶片非常近的位置固定不动，取不同的L进行碰撞检测，并记录平均碰撞检测时间t和距离测试中的最小距离mind当L在38之间时，t和mind如表1所示。从表1可以看出：随着L的增大，t在增加，并且增加的倍数越来越大，而mind的变化却越来越小由本文算法的mind计算可知，L的增加使得控制点更加密集，mind也就越来越接近2个曲面实际的最短距离，这样一来，碰撞检测的结果就越精确，根据以上分析，碰撞检测的实时性和精确性不可能同时达到最理想状态，对实时性要求较高的场合，L可偏小，而对精确性要求较高的场合，L应偏大。从表1知，若将L=7,8时的mind值看作精确值，那么当L=5时，mind已接近精确值，且t也比较小，mind的误差为O.0004，若考虑到其他一些不确定因素，T可取O.0006.因此，当L=5，T=O.0006时，采用本文算法可以使本例的碰撞检测具有良好的效果。与Page算法相比，本文算法具有较好的精确性和实时性，原因如下。(1)在曲面细分中引入了节点反插技术，因为插入了具有清晰几何意义的控制顶点，所以可以人为控制每一次细分，使之尽量均匀，从而减少了细分层次，缩短了平均碰撞检测时间。(2)采用了简单、有效的FDH包围盒，可以尽早排除不相交的情况。(3)通过控制点之间的距离测试进行精确碰撞检测，避免了由于包围盒不紧密而造成的碰撞检测结果不精确的问题。4 结束语本文提出了一种针对NURBS曲面的碰撞检测算法，该算法将节点反插技术引入到曲面细分之中，通过对建立的简单、有效曲面的FDH包围盒进行初步碰撞检测，再通过曲面控制点之间的距离测试进行精确碰撞检测，所提算法可以应用于虚拟场景的NURBS曲面物体碰撞检测，特别是对精确性和实时性要求比较高的场合，可增强虚拟现实系统的逼真感，本文算法也有一定的局限性，它只能应用于NUBRS曲面的碰撞检测，因此还需进一步完善，以应用于其他的自由曲面。参考文献：1 刘晓东，罗轶先，郭新宇，等，基于NURKS曲面的玉米叶生长过程中的形态建模J计算机工程与应用，2004,40(14)：201-203Liu Xiaodong，Luo Yixian，Guo Xinyu，et a1Themodeling of maize leaf during the growing processbased on NURBSJComputer Engineering and Ap-plications,2004,40(14)：201-2032 Page F，Guibault FCollision detection algorithm forNURBS surfaces in interactive applicationsCca-nadian Conference on Electrical and Computer Engi-neeringPiscataway，USA：IEEE,2003：1417-14203 施法中计算机辅助设计与非均匀有理B样条M北京：高等教育出版社，2001：435-4494 朱心雄自由曲线曲面造型技术M北京：科学出版社，2000：155-1575 魏迎梅，王涌，吴泉源，等碰撞检测中的固定方向凸包包围盒的研究J软件学报，2001，12(7)：1056-1063Wei YingrneiWang Yong，Wu Quanyuan，et a1Re-search on fixed direction hull bounding volume in colli-sion detectionJJournal 0f Software，2001，12(7)：1056-10636 刘 浩NURJ3S曲面间的最短距离D南京：南京航空航天大学计算数学系，2002。